Private Rate-Constrained Optimization with Applications to Fair Learning
Mohammad Yaghini, Tudor Cebere, Michael Menart, Aurélien Bellet, Nicolas Papernot · 2025
Read Private Rate-Constrained Optimization with Applications to Fair Learning by Mohammad Yaghini, Tudor Cebere, Michael Menart, Aurélien Bellet, Nicolas Papernot (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-22703.txt.
Introduction
Mohammad Yaghini and co-authors solve fair learning tasks under strict privacy rules, in a paper from 2025. Fair rules cap how often a model says yes for each group, but those caps rest on group wide sums, which breaks the per case form that private training needs.
Their method pairs a rise and fall training dance with a private count of each batch group mix. That count is the sole added privacy cost. A fresh proof shows the method settles well, thanks to the straight shape of the fair rule side. In tests it beat past private fair methods on the full trade off.
Catalog record
| CREATOR | Mohammad Yaghini, Tudor Cebere, Michael Menart, Aurélien Bellet, Nicolas Papernot |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 108 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-22703
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Private Rate-Constrained Optimization with Applications to Fair Learning Mohammad Yaghini, Tudor Cebere, Michael Menart, Aurélien Bellet, Nicolas Papernot Abstract 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 1 1 1 Code is available at: https://github.com/cleverhans-lab/dp-raco 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. 1 Introduction From fair learning ( Zafar et al., 2017 ; Goel et al., 2018 ; Agarwal et al., 2018 ; Cotter et al., 2019a ) to robust optimization ( Chen et al., 2017 ; Cotter et al., 2019b ) and cost-sensitive learning ( Mienye and Sun, 2021 ; Cotter et al., 2019b ) , many Machine Learning (ML) tasks can be formulated as constrained optimization problems. In such problems, the goal is to minimize the model’s overall error subject to rate constraints , which enforce conditions on prediction rates across subsets of the training data. For instance, ensuring fairness in a resume screening system might require similar rates of positive outcomes (e.g., resumes selected for human review) across gender groups, a criterion known as equalized odds ( Hardt et al., 2016 ) . Similarly, in a medical setting, a decision-support system may need to strictly limit its false negative rate, e.g., to reduce the risk of misdiagnosing cancerous tumours as benign. These learning tasks often require training models on sensitive data, such as employee or patient records in our examples. Publicly releasing these models can expose data owners to privacy attacks ( Shokri et al., 2017 ) and disclose personal data without consent ( Sweeney, 2002 ) . Without proper safeguards, these risks can harm individuals, undermine trust in AI systems, and discourage data sharing in critical applications like medical research. Despite recent advances, differentially private (DP) constrained optimization has focused almost exclusively on fairness constraints ( Jagielski et al., 2019 ; Mozannar et al., 2020 ; Tran et al., 2023 ; Berrada et al., 2023 ; Lowy et al., 2023 ) . Methods tailored to fairness do not extend to the broader family of rate constraints that arise in practice. We bridge this gap with the first general DP framework for arbitrary rate-constrained problems. Our approach expands DP’s reach to previously incompatible applications and pushes the Pareto frontier of utility, privacy, and constraint satisfaction, including fairness, beyond the state of the art. Differential Privacy (DP) is the standard framework for private data analysis that has been successfully applied to training and releasing unconstrained models with formal privacy guarantees. A key approach is the widely used DP-SGD algorithm ( Song et al., 2013b ; Bassily et al., 2014 ; Abadi et al., 2016 ) , which ensures DP by clipping per-sample gradients and adding calibrated noise to the averaged gradient. This process bounds each data sample’s influence. Incorporating rate constraints presents a challenge, however, because unlike typical training losses, these constraint functions (or their regularizer counterparts) do not readily decompose into per-sample terms . This fundamental incompatibility with per-sample processing makes it difficult to integrate them with standard DP-SGD and its variants. Our key contribution is the introduction of a DP optimization algorithm that overcomes this limitation, enabling private optimization subject to rate constraints. To address the challenge of privately enforcing rate constraints, we propose generalized rate constraints . Generalized rate constraints allow us to express all rate constraints in a common form based on statistics (i.e., histograms) on disjoint subgroups within the dataset. This common structure is the key to our privacy solution: it allows us to efficiently gather all the necessary information to evaluate these constraints under DP. Beyond its advantages for privacy, our method offers greater flexibility compared to prior work ( Cotter et al., 2019b ) by extending to scenarios with multiple output classes. With generalized rate constraints at hand, we introduce RaCO-DP , a framework for optimizing machine learning models under rate constraints with differential privacy (DP). RaCO-DP is a differentially private variant of the Stochastic Gradient Descent Ascent (SGDA) algorithm which leverages a Langrangian formulation and generalized rate constraints to overcome the decomposability obstacle. Our core insight exploits the structure provided by these constraints: we can efficiently compute differentially private statistics (e.g., histograms) for these subgroups. By privatizing these statistics at each step, we enable private evaluation of the constraint function, and its per-sample constraint gradients. We provide a formal convergence analysis of RaCO-DP , proving that even for non-convex optimization problems, our method converges to an approximate stationarity point. To achieve this, we introduce a novel approach to analyzing SGDA that accounts for bias in gradient estimates and exploits the linear structure of the dual update to enhance convergence speed. As a concrete application, we study private learning under various constraints, including demographic parity ( Dwork et al., 2012 ) , false negative rate, and equalized odds. Our method achieves new state-of-the-art (SOTA) results on four standard benchmarks and Pareto-dominates the prior best approach ( Lowy et al., 2023 ) in accuracy–fairness–privacy trade-offs. We further demonstrate that RaCO-DP scales beyond convex models, achieving strong performance for deep neural networks (ResNet16 He et al. (2016) on CelebA Liu et al. (2015) ). We also validate its effectiveness on tasks involving multiple sensitive groups (demographic parity on the ACSEmployment dataset), scaling to 18 subgroup constraints. Additionally, our method offers two advantages over existing approaches explicitly designed for fairness constraints. First, it provides stronger privacy guarantees than prior approaches that only consider the privacy of the sensitive label ( Jagielski et al., 2019 ; Tran et al., 2023 ) , akin to label privacy ( Ghazi et al., 2021 ) . Second, it allows practitioners to directly specify the maximum disparity, unlike previous penalization-based methods, such as ( Lowy et al., 2023 ) , which offer only indirect control over the desired fairness level via hyperparameter tuning. 2 Background 2.1 Differential Privacy Differential Privacy (DP) ( Dwork et al., 2006 ) has become the de facto standard in privacy-preserving ML thanks to the robustness of its guarantees, its desirable behaviour under post-processing and composition, and its extensive algorithmic framework. We recall the definition below and refer to Dwork and Roth (2014) for more details. Let \mathcal{X},\mathcal{Y} be the input and output spaces, respectively. We fix some m\in\mathbb{N} and denote by \mathcal{D} the space (\mathcal{X}\times\mathcal{Y})^{m} of datasets of size m . Definition 2.1 (Differential Privacy)