# Private Rate-Constrained Optimization with Applications to Fair Learning

arXiv: https://arxiv.org/abs/2505.22703 · HTML: https://mlsanity.com/paper/2505.22703/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 41 of its 60 references that are in the map.
- First posted on arXiv 28 May 2025.

## Builds on (most cited first, 30 of 41)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Deep Learning Face Attributes in the Wild](https://mlsanity.com/paper/1411.7766/) (2014)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/1610.05820/) (2016)
- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018)
- [Retiring Adult: New Datasets for Fair Machine Learning](https://mlsanity.com/paper/2108.04884/) (2021)
- [Differential Privacy Has Disparate Impact on Model Accuracy](https://mlsanity.com/paper/1905.12101/) (2019)
- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences](https://mlsanity.com/paper/1807.01647/) (2018)
- [Numerical Composition of Differential Privacy](https://mlsanity.com/paper/2106.02848/) (2021)
- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [Deep Learning with Label Differential Privacy](https://mlsanity.com/paper/2102.06062/) (2021)
- [Hyperparameter Tuning with Renyi Differential Privacy](https://mlsanity.com/paper/2110.03620/) (2021)
- [Optimization with Non-Differentiable Constraints with Applications to Fairness, Recall, Churn, and Other Goals](https://mlsanity.com/paper/1809.04198/) (2018)
- [Revisiting Gradient Clipping: Stochastic bias and tight convergence guarantees](https://mlsanity.com/paper/2305.01588/) (2023)
- [Differentially Private Fair Learning](https://mlsanity.com/paper/1812.02696/) (2018)
- [Satisfying Real-world Goals with Dataset Constraints](https://mlsanity.com/paper/1606.07558/) (2016)
- [Neither Private Nor Fair: Impact of Data Imbalance on Utility and Fairness in Differential Privacy](https://mlsanity.com/paper/2009.06389/) (2020)
- [Training Well-Generalizing Classifiers for Fairness Metrics and Other Data-Dependent Constraints](https://mlsanity.com/paper/1807.00028/) (2018)
- [Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions](https://mlsanity.com/paper/2207.04380/) (2022)
- [Fair Learning with Private Demographic Data](https://mlsanity.com/paper/2002.11651/) (2020)
- [Chasing Your Long Tails: Differentially Private Prediction in Health Care Settings](https://mlsanity.com/paper/2010.06667/) (2020)
- [Robust Optimization for Non-Convex Objectives](https://mlsanity.com/paper/1707.01047/) (2017)
- [Disparate Impact in Differential Privacy from Gradient Misalignment](https://mlsanity.com/paper/2206.07737/) (2022)
- [Differentially Private SGDA for Minimax Problems](https://mlsanity.com/paper/2201.09046/) (2022)
- [Bring Your Own Algorithm for Optimal Differentially Private Stochastic Minimax Optimization](https://mlsanity.com/paper/2206.00363/) (2022)
- [Differential Privacy has Bounded Impact on Fairness in Classification](https://mlsanity.com/paper/2210.16242/) (2022)
- [Optimal Algorithms for Differentially Private Stochastic Monotone Variational Inequalities and Saddle-Point Problems](https://mlsanity.com/paper/2104.02988/) (2021)

## Built on by (most cited first, 1 of 1)

- [Evolution of Optimization Methods: Algorithms, Scenarios, and Evaluations](https://mlsanity.com/paper/2604.12968/) (2026)

## Abstract (arXiv)

Many problems in trustworthy ML can be expressed as constraints on prediction rates across subpopulations, including group fairness constraints (demographic parity, equalized odds, etc.). In this work, we study such constrained minimization problems under differential privacy (DP). Standard DP optimization techniques like DP-SGD rely on objectives that decompose over individual examples, enabling per-example gradient clipping and noise addition. Rate constraints, however, depend on aggregate statistics across groups, creating inter-sample dependencies that violate this decomposability. To address this, we develop RaCO-DP, a DP variant of Stochastic Gradient Descent-Ascent (SGDA) that solves the Lagrangian formulation of rate constraint problems. Through careful design, the extra privacy cost incurred by incorporating these constraints in our approach is limited to that of privately estimating a histogram over each mini-batch at every step. We prove the convergence of our algorithm through a novel analysis of SGDA that leverages the linear structure of the dual parameter. Empirical results show that our method Pareto-dominates existing private learning approaches under group fairness constraints and also achieves strong privacy-utility-fairness performance on neural networks.