The Cost of a Reductions Approach to Private Fair Optimization

2019/06/23 by Daniel Alabi, Alabi, Daniel
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Law, Economics, and Judicial Systems #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Privacy-Preserving Technologies in Data

paper · pdf · doi:10.48550/arxiv.1906.09613

openalex publication_date 2019/06/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Through the lens of information-theoretic reductions, we examine a reductions approach to fair optimization and learning where a black-box optimizer is used to learn a fair model for classification or regression. Quantifying the complexity, both statistically and computationally, of making such models satisfy the rigorous definition of differential privacy is our end goal. We resolve a few open questions and show applicability to fair machine learning, hypothesis testing, and to optimizing non-standard measures of classification loss. Furthermore, our sample complexity bounds are tight amongst all strategies that jointly minimize a composition of functions. The reductions approach to fair optimization can be abstracted as the constrained group-objective optimization problem where we aim to optimize an objective that is a function of losses of individual groups, subject to some constraints. We give the first polynomial-time algorithms to solve the problem with (ε, 0) or (ε, δ) differential privacy guarantees when defined on a convex decision set (for example, the ℓ_P unit ball) with convex constraints and losses. Accompanying information-theoretic lower bounds for the problem are presented. In addition, compared to a previous method for ensuring differential privacy subject to a relaxed form of the equalized odds fairness constraint, the (ε, δ)-differentially private algorithm we present provides asymptotically better sample complexity guarantees, resulting in an exponential improvement in certain parameter regimes. We introduce a class of bounded divergence linear optimizers, which could be of independent interest, and specialize to pure and approximate differential privacy.

Citations

• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting
• Playing Games with Approximation Algorithms
• Smooth minimization of non-smooth functions
• Equality of Opportunity in Supervised Learning
• High probability generalization bounds for uniformly stable algorithms\n with nearly optimal rate

Related

• Private Rate-Constrained Optimization with Applications to Fair Learning
• Differentially Private Fair Learning
• Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds
• Privacy-Preserving Convex Optimization: When Differential Privacy Meets Stochastic Programming
• The Impact of Differential Privacy on Group Disparity Mitigation