Private Rate-Constrained Optimization with Applications to Fair Learning
Authors: Mohammad Yaghini
Tudor Cebere
Michael Menart
Aurélien Bellet
Nicolas Papernot
Venue: ICLR 2026 Poster (2026)
Keywords: differential privacy
fairness
machine learning
Primary area: alignment, fairness, safety, privacy, and societal considerations

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. We show that the additional privacy cost of incorporating these constraints reduces to privately estimating a histogram over the mini-batch at each step. We prove 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.

Published as a conference paper at ICLR 2026
PRIVATE RATE-CONSTRAINED OPTIMIZATION WITH APPLICATIONS TO FAIR LEARNING
Mohammad Yaghini
Tudor Cebere"
University of Toronto & Vector Institute mohammad, yaghi i ni @mail .utorntoocca ca
PreMeDICaL team, Inria, Idesp. Inserm Université de Montpellier tudor. nria.
Michael Menart
Aurélien Bellet
University of Toronto & Vector Institute menart 28osu. menart.28osu. edu
PreMeDICaL team, Inria, Idesp, Inserm Université de Montpellier aure ien, be @ nri fr
Nicolas Papernot
University of Toronto & Vector Institute & Inria nicolas. nicolla.pppeete .paperaoteutooroot..o
ABSTRACT
Many problems 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, de- pend on aggregate statistics across groups, creating inter-sample dependencies that violate this decomposability. To address this, we develop RaCO-DP, DP variant of Stochastic Gradient Descent-Asee Ascent (SGDA) that solves the Lagrangian formu- lation of rate constraint problems. Through careful design, the extra privacy cost incurred by incorporating these constraints in approach is limited to that of pri- vately estimating a histogram over each mini-batch at every step. We prove the con- vergence of our algorithm through novel analysis of SGDA that leverages the lin- car 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-uility-faime performance on neural networks.
INTRODUCTION
From fair learning (Zafar al. 2017 Goel et al. 2018 1 Agarwal al., 2018 Cotter al. 2019a) to robust optimization (Chen et (201 Cotter et al. 2019b) and cost-sensitive learning (Mienye & Sun] 2021 Cotter 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 prediction rates across subsets of the training data. For instance, ensuring fairness in resume screening system might require similar rates of positive out- comes (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, decision-suppon system may need to strictly limit its false negative rate, egg., 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 at- tacks (Shokri et al. 2017) and disclose personal data without consent (Sweeney 2002). Without
"Equal contribution
Code available http::/gghhiaa..ommc/cccraaaabbh

---

Published as a conference paper at ICLR 2026
proper safeguards, these risks can harm individuals, undermine trust in Al 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 (Jagielki
et et 2019; Mozannar et al., 2020; Tran et al., 2023, Berrada et al. 2023 Lowy et al. 2023). Methods tailored 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 faimess, 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 the widely used DP-SGD algorithm (Song 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 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 rate constraints.
To address the challenge of privately enforcing rate constraints, we propose generalized rate con- straints. Generalized rate constraints allow us express all rate constraints in common form based on statistics (i.c., 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 al., 2019b) by extending to scenarios with multiple output classes.
With generalized rate constraints at hand, we introduce RaCO-DP, framework for optimizing machine learning models under rate constraints with differential privacy (DP). RaCO-DP a differentially private variant of the Stochastic Gradient Descent Ascent (SGDA) algorithm which leverages 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 statisties 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, 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.
method converges to approximate stationarity point. To
As a concrete application, we study private learning under various constraints, including demographic parity (Dwork 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 (Lwy et al. 2023) in accuracy-fainee fainness--- privacy trade-offs. We further demonstrate that RaCO-DP scales beyond convex models, achieving strong performance for deep neural networks 1 6 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 ACSEmp oyment 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 DIFTERENTIAL PRIVACY
Differential Privacy (DP) (woork et al. (006) has become the de facto standard in privacy-preserve ML thanks to the robustness of its guarantees, its desirable behaviour under post- pooccessnnssing and composition, and its extensive algorithmic framework. We recall the definition below and refer to
2

---

Published as a conference paper at ICLR 2026
Dwork & Roth (2014) for more details. Let X, 3 be the input and output spaces, respectively. We fix some m E IN and denote by DD the space (œ' x 3 of datasets size m.
Definition 2.1 (Differential Privacy). mechanism M D + O (E.6)-DP if for all datasets D, D' E "D differing in one datapoint and for all events O: P(M(D) E E S P(M(()) E E +
In the above definition, & E (0, 1) can be thought of as the failure probability, and = > 0 the privacy loss; smaller and 6 correspond to stronger privacy guarantees.
Differentially Private Stochastic Gradient Descent (DP-SGD) (Song et al.
2013b Bassily et al.
et al.; 2016) serves the foundational algorithm in private ML. Given training dataset
D and model parameters 0 E RR, DP-SGD aims to privately solve (in the sense of definition 2. the empirical risk minimization problem mingeRd {(0), where {())
TDj ΣxeD {(0; and & (0,
loss function differentiable in DP-SGD follows the standard SGD update, but guarantees differential privacy by (i) capping each data point's influence the gradient through gradient clipping, and (ii) injecting Gaussian noise into the clipped gradients.
Each iteration / E [T] of DP-SGD incurs privacy loss (Et, 6,). Privacy composition (Dwork et al. 2006 Kairouz et al. 2015) and privacy accounting (Abadi et al. (016;) Gopi et al. [021 Doroshenko
al. 2022) are techniques that aggregate these per-step privacy losses into total privacy guarantec
0)
that holds for the entire optimization process.
2.2
CONSTRAINED OPTIMIZATION VIA LAGRANGIAN
In this work, aim to solve constrained empirical risk minimization problems of the form:
milloerd {e(0) 1 Eren ( s.t. E (0) g5-
where r Rd + R+ are the constraint functions and E (R+)² are slack parameters. We focus
on inequality constraints, equality constraints are generally infeasible under differential privacy CCummings et al. 2019).
Due to the difficulty of solving [T] directly, we instead solve an equivalent min-max optimization
problem with respect to the Lagrangian:
min max {C(0, A) = (()) R(0, A)}, where: R(B,A) (TT,())) -1))
BERd XEλ
Here, L C (R+)² are the Lagrange multipliers, often referred to as the dual parameter, while is the primal parameter. One of the simplest algorithms to solve (2) is the generalization of (S)GD
known as (Stochastic) Gradient Descent-Ascent, (S)GDA (Nemirovski et al. 2009).
Definition 2.2 (GDA). At each iteration
g(++1) <- g(t) no ()) )()) and ( - (A + nx VxC000, ,())))
(3)
where Th and yл are step sizes and 1I performs orthogonal projection onto A. The stochastic version (SGDA) replaces exact gradients with stochastic estimates.
2.3 RATE CONSTRAINTS
In this work, we focus on constraints that relate to prediction behavior over subsets of the dataset. Consider model h X x Rd + R that maps inputs from feature space X' to real-valued prediction scores over the label set y {I,..., .. K} using parameters 0 E Rd. Formally, (hard) prediction rates count the number of points in dataset D for which the model predicts certain label & ): phard (D; D ΣxED [ e (M(0=)),)<(K)
As the indicator function is non-differentiable and thus challenging to optimize, we will use dif- ferentiable versions of these constraints. We rely on the tempered softmax function o, (=)x where the temperature parameter 7 E R- controls the sharpness of the probability distribution. This allows us define soft prediction rates:
exp(-T**)
> exp(-7z))
Pr( ExeD or
for & E y
(4)
3

---

Published as a conference paper at ICLR 2026
Observe that lim 0=( P (D:0).
Rate constraints, as defined by /oh et al. (2016) and Cotter et al. (2019b) for binary classification ()' = {0, 11), are linear combinations of classifier's prediction rates across different data partitions:
Everor a Pi 0) + P,D, 5.
(5)
Q > 0, Ogg By E are mixing coefficients, D1, Do S and y the slack parameter. Examples of rate constraints in this form include ensuring that the fraction of positive predictions across different demographic groups stays within a specified threshold, or requiring the model to achieve minimum level of precision recall for both classes (Cotter et al. 2019a).
Such constraints are limited to binary classification, and a multiclass generalization is not immediate. More critically, it is unclear how to evaluate rate constraints in (5) while efficiently preserving privacy. These are issues we address in the next section.
3 PRIVATE LEARNING WITH GENERALIZED RATE CONSTRAINTS
Generalized rate constraints. We propose a generalized form of rate constraints that (i) applies to the multi-class setting and (ii) exploits shared structure to enable accurate private estimation.
This shared structure is a partition (Di..., Do} of the dataset D for some Q > O, which we refer to as the "global" partition. We then allow each rate constraint to incorporate prediction rates any recombination of sub-datasets in the global partition. This structure is flexible, as it allows each rate constraint to have its own "local" datasets, provided that each of these datasets can be formed as a union of sets from the global partition. For example, in the context of fairness constraints, the global partition corresponds to the the sensitive groups (c.g.. Asian, Black, Caucasian), and local datasets for one of the constraint is [Asian, Non-Asian) where Non-Asian = (Black, Caucasian): See Figure !
Glokel
Ds
RIN
D
4- (2.3) 2 U.D.
(2)
(1.3) J.
Tx
199
4 4- (3)
(1:2:: D,
Figure Each rate constraint of the form (6) builds local datasets based on the global partition. A class-1 1 (class-O) prediction is shown with blue (red) square. Pre- diction rates Po, Pi are shown as fractions. As an example, let D1, D2. and D3 be the set of Asian, Black, and Caucasian individuals in the dataset, respectively. Con- straint P1 builds its local datasets as {{D1), ). ( }, i.e. (Asian, Non-Asian), from the global parti- tion (D,, D2, D3) using the set of index subsets I (21,22}.
Formally, given this global partition, we assume for each j E [J] there exists family of subsets of (Q), denoted I, S 2 and
weight vector aj E I such that the constraint F can
be written in the following form P
(y( EiET, Ek (LTTAP(
(6)
Assuming such global partition is not restrictive, the trivial partition D, = 2, (with Q = [D) can always be used. How- ever, Section 4 will show, smaller partition size Q enables a better privacy-utility trade-off through more effective noise use.
Remark 1. For common rate constraints, the best global par- rition will be readily apparent (see the application to fairness below). The smallest global par- tition can however be defined explicitly. Let Di....,Do be the (possibly non-disjoint) subsets of D over which the functions T1,..,T" T, compute prediction rate as per Eq. ( Then the smallest global partition assigns any two data points x and x' in the same Dg if and only if {Vg E [Q], (x, x') D,, E (0, x1)2
Note that each rate constraint F is uniquely defined by the subset family I, and vector ay. Both parameters are public, specifying only the constraint's structure and containing no sensitive data.
Application to fair learning. Group faimess in machine learning aims prevent models from making biased decisions across different sensitive groups. We show below our general form of rate constraints
4 allows to capture the popular group fairness notion of demographic parity (Barocas et al.! 2023)
With some abuse of notation, we denote by Oj.IA the entry of ay corresponding subset 7 and lahel At
4

---

Published as a conference paper at ICLR 2026
More generally, all common group faimess measures can be formulated rate constraints (Cotter et al. 2019b). We provide details on formulating other faimess notions in Appendix A
Definition 3.1 (Demographic Parity), Assume feature vector I E X contains sensitive attribute, denoted as Z, laking values in 2 C Z. A classifier h((;-)) satisfies demographic parity w.r.t. 7 if Pr[Y k Z =] Pr|Y for all z E Z, Y) where Y = X).
In practice, probabilities are replaced by empirical rates Pa. With slack 7, this gives Pa(D[Z - =};0) - (D + z}:0) 7,
E 2 y
leading to J - / | constraints of the form (6) The global partition has size Q = |2] with elements D2 D =]. For the constraint indexed by (z,y) y) E E x>), we take I = [|= and define [{{=),y = 1, {1 = 11 with all other components zero.
Objective. With these definitions in place, we can now state our objective: solve problem with generalized rate constraints of the form under DP.
4 RACO-DP: PRIVATE BATE-CONSTRAINEE OPTIMIZATION
We introduce RaCO-DP (Algorithm D. an al- gorithm for rate-constrained optimization that ex- tends SGDA (Definition 2.2) to satisfy DP. Each iteration of RaCO-DP operates mini-batch B(4) and consists of three key components that we will describe in detail in this section:
Algorithm RaCO-DP
Require: Dataset D, Parameter Og, learning rates yoo 7/x- Gaussian noise variance a, Laplace parameter b, clipping norm C, sampling rate r, slack parameter vector 7, loss function ((0:-)
1: Initialize A + [0]
1. Private histogram computation: For each
2: for each t E "o...., - do
class k E [K] and part g [Q] of the parti- tion, we privately estimate the sum of model predictions (h((;;; 2))x over the points in the mini-batch (tt) that belong to Dg, storing these counts in a histogram (+) (Section 4.1
3: B(t) +- Poisonnaample(Drr)
Private Histogram:
5:
H(t))
Σ (h(((();;)) + Lap(E)
xED,nB(s)
Primal Update:
2(0) Gaussian(O, l2o²)
2. Private primal updates: We derive per-sample gradients for the primal update of SGDA based on post-processing the histogram H()) We then clip, average and privatize these gradients using the Gaussian mechanism (Section 4.2)
7:
Va E B(t) set In,0 as (sce also Bq L0
(t)
1 vel(O(); x +V (1)) (1)) x)
8:
90 (t) + (EOEBO clip(1..) (0) C
r| )) + Z
3. Private dual updates: We compute all con- straint values by again
01++1) +- -0()) 1096 (t)
the his- togram H1), allowing us to perform the dual up- date at no additional privacy cost (Section 4.3
Dual Update:
loX²);; + -ppos (f)(t) Tj, YjE
10:
11: (++1) + (2(1 + +m
(1)) Eqn.
12: end for
4.1 PRIVATE HISTOGRAM COMPUTATION
13: return ((T)
Our algorithm's primal and dual updates compute prediction rates across dataset partition parts Dj Do for each class. To track these prediction rates privately, we construct histogram H E RQx K that counts (soft) model predictions for each combination of part q and class k. For given model parameter 6, each sample z; in the mini-batch (*) belongs to exactly one part D, of the partition but can influence the counts of all К classes through the softmax probabilities (h((0; x))) This non-private histogram is constructed by accumulating these softmax vectors:
(8) To make this histogram differentially private, we use the Laplace mechanism (Dwork et al. 2006). The l sensitivity of (+) is 1, each sample belongs to one element of the global partition and its softmax predictions sum across classes. Thus, we achieve e-DP by adding Laplace noise each element:
q.b ED,nBO (h((0xz))).
((()) q.k
(1(1) + Lap(1/e)) Vy E [Q), y.
5

---

Published as a conference paper at ICLR 2026
Remark 2. We focus the Laplace mechanism for simplicity, but note that our framework can readily accommodate other differentially private histogram mechanisms that may provide better utility in some regimes, e.g., when the histogram is high-dimensional and sparse (Wilkins et al. 2024
In the following sections, we will see that 11 contains all the necessary information to compute the quantities related to the rate constraints required for both the primal and dual updates, thereby avoiding additional privacy costs that would arise from composing multiple queries.
4.2 PRIVATELY COMPUTING THE PRIMAL GRADIENT
A key requirement in DP-SGDA is that each sample has a bounded contribution to gradient updates. To satisfy this RaCO-DP, we decompose the Lagrangian into per-sample terms. While the loss (()) naturally decomposes as in standard DP-SGD, the regularizer It is more challenging.
Given a mini-batch B, define B-r B n y D:) and recall that Ij and 0j E R denote the
family of subsets and weight vector associated with constraint r'y. The minibatch-level regularieer is,
R(O, A: B)
Σ IEL;
P...AP((BBr:0)) -
Σ x
Σ
0j,.k Brul
(h(0;z))))
IEL, RE
Note that this may be biased estimate of R(0, A) due to the normalization term |Bz] We account for this bias in our convergence analysis (Section 5).
We would like a per-sample decomposition of R(O, x: B). The main obstacle in such a decomposition are the quantities /Brll, which depend on the entire mini-batch. We overcome this by first noting that
|Barl= = Eier E. H leading to the following per-sample regularizer estimator at point x E D:
fn H, = (> Σ
O...kh 1rre o (1(0;2))) -7)))) -s5)
H SET WIEK
Σ
JEIJKICK
and thus the overall per-sample gradient is given by, Vol(Sar)
EjE EiGT, Enje(K]
agare 1 =))
(10)
L Σ EET k2c(K)
1 1,k
Then, since H depends on the mini-batch B, we use instead its differentially private version Q.. Note that the normalizing term r| is necessary to correctly implement clipping in Line of Algorithm
Remark 3. For specific constraints, the estimation of |Brrl can be further refined. For example, when each Ij itself a partition of [Q], the sensitivity of E, Ens i,k2 at most 1, and adding Laplace noise directly results in a tighter estimate of |Bos
With this per-sample decomposition, we can apply standard DP-SGD techniques: clipping per-sample gradients, averaging them over the mini-batch, and adding Gaussian noise to preserve privacy.
4.3 PRIVATELY COMPUTING THE CONSTRAINT DUAL GRADIENT
For each constraint F and corresponding slack parameter 7/, the gradient the Lagrangian w.r. À is:
VxC(o(t), X (0())) B()) Tij
(11)
The dual update in RaCO-DP thus requires evaluating rate constraints on the current mini-batch B(A), incurring a privacy cost. To avoid this additional cost, we introduce a post- post-processing function 1g x K + R that operates directly on the private histogram (*). This function replaces each
sum of model predictions
Eie BBB) (h((;; 24)) with the corresponding histogram count (t).
q.k²
Jg.LA, Eier A
(1)(0)))) = Eiez, EmeejK] E.er Σize(K] A
(12)
As (7 is already DP, the post-processing property ensures this step incurs additional privacy cost.

---

Published as a conference paper at ICLR 2026
Remark 4. As standard in private optimization, mini-batches B(t) constructed via Poisson sam- pling, with each datapoint included with probability r. This allows us to leverage privacy amplification by subsampling (Kastviswanathan al.] 2017 Balle et al. 2018 for the Laplace mechanism in his- togram computation (Section 4. 11 and the Gaussian mechanism for per-sample gradients (Section (42)
RaCO-DP's efficiency relies on private histogram H enabling per-sample gradient computation and private constraint evaluation, key to handling rate constraints under DP. The privacy guarantees of Algorithm follow from composing the subsampled Laplace and Gaussian mechanisms over T steps.
Theorem 4.1. Let b 2 2 max & (Vllo((T/)) } and 10 maxxx {
(log(T/6) r|D]c
CvT log(T/5)
}. then
Algorithm 7 is 5).P).
The proof is in Appendix We present this result primarily for to provide intuition about parameter scaling. In our experiments, we use a tighter privacy accountant that improves both constants and logarithmic factors. Additionally, in our convergence analysis, offer a more detailed examination when the Lagrangian is Lipschitz and the algorithm is run without clipping.
5 CONVERGENCE AND UTILITY ANALYSIS
Consider the function defined (0) maxxea [C(6, })}. Ideally, would want to show that Algorithm| approximately minimizes 4. However, due to the fact that may be non-convex, finding an approximate minimizer is intractable in general. In fact, because the constraint functions, (Ty). may be non-convex in 8, if A (R+)² then even finding point where O is finite may be intractable. As such, we must make two standard concessions. First, we will assume is compact convex set of bounded diameter. Intuitively, this bounds the penalty applied when the constraints are satisfied. Further, instead of guaranteeing that Algorithm [ will show the algorithm finds an approximate stationary point. We note that stationarity a standard convergence measure in non-convex optimization, and provide more discussion in Appendix D.I Our subsequent analysis in fact provides for slightly stronger, but more technical, notion of stationarity than we provide here; see Appendix D.6 for more details.
finds an approximate minimizer of h we
Definition 5.1. (a,, v) -stationary point) A point 0 is an (a, v)-stationary point 3f s.t. 10- 8'1 S v and min ||=||| I a, with de the subdifferential of 4.
When the loss is Lipschitz and smooth, SGDA converges to an approximate stationary point of + LLn al., 2020). Unfortunately, Algorithm| may have biased gradients, and the scale of noise present in Go and 9x may vary dramatically depending on d and J. Thus, our main goal in this section is two-fold. First, we aim to formally show that despite using biased gradients, Algorithm [ provably finds an approximate stationary point. Specifically, when the error in the primal updates (w.r.t. ||- (12) is at most To and the error in the dual updates is at most TA (w.r.t. || olo)))),, we show SGDA on a nonconvex-lines
т VTA + ) Appendix D.6 Second, we characterize the impact of the noise go and タA added due to privacy. This involves correctly balancing the number of iterations 7 with the scale of noise needed to ensure privacy, which increases with T. This leads to the following result for Algorithm [ run without clipping.
loss finds stationary point roughly with
T O T4
Theorem 5.2 (Informal), Let = min (ID,I) Assume h(6;z) and e(O) are both Lipsehitz and smooth. Then, under appropriate choices of parameters, Algorithm D is (e, 8D-DP and with probability at least - P there exists E [T' s.t. O₂ is (a, a) -ttationar point of & with.
JKn log(?) )
dlog( TE
K (og(og()) logt( (JKN)
(ne)
up to dependence on problem constants. We provide a complete statement and full proof in Appendix D.2 In Appendix DD.7 we derive Lipschitz and smoothness constants for from those of the classifier.
7

---

Published as a conference paper at ICLR 2026
1.00
SCDA
Ro (c-MM)
Demographis Disparity
0.08
Tean (2025) DI-FERRI
BRCOOU (MEN))
Demographit Disparity
0.6
(auns) SGDA (Nam-Prrcca)
Ru00 DP
Aocuracy
0.95
0.06
0.4
0.90
0.04
0.2
0.85
0.02
0.80
0.00
0.0
0.1
0.075
0.05
0.050
0.075
0.100
0.24
0.32
0.48 0.56 Test Error
0.40
Demographic Parity (7)
Test Error
(a) CelebA
(b) Parkinsons
(c) Folktables
Figure 2: Cormess-utilipg trade-off for RaCO-DP over three benchmarks under demographic parity constraints training: (a) 6esNet16 (5 runs), (b) and (c) logistic regression with (20 runs)
There are several key steps involved in achieving this result. First, we provide a general convergence proof for SGDA under the assumption that gradients have bounded error (Theorem D.55). Notably, in contrast to previous analyses, this result I) allows for biased gradients; 2) depends on the to error in the dual gradient estimate (rather than the & error); and 3) achieves faster convergence (in terms of by leveraging the linear structure of the dual. To point (3), our analysis shows SGDA this setting can converge fast as T174 instead of T77 (shown by Lin et al. 2020),, essentially matching the rate observed in comparable minimization (rather than min-max) Settings. See Theorem D.5 for this specific result. The next step in proving Theorem to control the error of the gradient estimates while balancing the noise necessary for privacy. We show that this error scales proportional
to Ó VeT 1 in the primal and Ō loT +
log in the dual. We defer the reader to detailed accounting of this error.
Lemma D.4 in Appendix D
6 EXPERIMENTS
We empirically demonstrate that RaCO-DP:
(i) achieves SOTA performance on standard tabular benchmarks; (ii) scales for deep neural networks, maintaining high utility under strong privacy guarantees; (iii) scales to a large number of constraints, and (iv) is computationally efficient.
Setup. We evaluate RaCO-DP on three constraint types: demographic parity (on Adult (Becker & Kohavi 1996), Credit - Card (Yhh) 2009), Parkinsons Little (2077), ACSEmployment (Ding negative rate (on Adult, Heart Alex Teboul), and equalized odds (on Credit -ardd)) We benchmark against DP-FERMI (Lowy al. 2023). Tran et al. (2021), and Jagielski et al.] (2019). reporting their results from Lowy et al. (202)) where available. In settings without prior DP work (e.g.. FNR constraints, deep networks Ce lebA), we use non-private SGDA as reference. All DP methods use 8 = 10-5, with privacy loss tracked via the numerical accountant Doroshenko al. (002)). Full implementation and hyperparameter details are in Appendix E.2 For constraint definitions, see Appendix A
et al. 2021), CelebA (Liu et al. 2015)).
Tabular data. On standard tabular benchmarks, Figure 2b (together with Figure Figure 5 and Figure 6 in Appendix E.3) shows that across multiple datasets (Adult, Credit-Care Parkinsons) and fairness constraints (demographic parity and equalized odds), RaCO-DP trains logistic regression models that consistently achieve higher accuracy at any fixed fairness disparity compared all baselines under the same privacy budgets. Additional ablations for small values provided in Appendix E.8
Neural networks. To demonstrate that RaCO-DP applicable to large, non-convex models, we train a ResNetl6 (He et al. 2016) (6.4M parameters) on CelebA under demographic parity constraints. As shown in Figure 2a RaCO-DP achieves 90% accuracy with only a 10% demographic disparity gap for 1. This result is close the non-private model's 95% accuracy, showing that RaCO-DP a practical tool for implementing fairness constraints in deep learning pipelines without prohibitive loss in utility. Hyperparameter and training details are in Appendix H.7
8

---

Published as a conference paper at ICLR 2026
Scaling. To evaluate performance under large constraint set, train a logistic regression on ACSEmployment enforcing demographic parity across 18 groups simultaneously. Saareeeessssa our method achieves competitive utility- fairness trade-off even under strong privacy (E 1), confirming its effectiveness.
F shows
Matching non-private rates. We observe that RaCO-DP nearly matches non-private accuracy some- times, especially for logistic regression on tasks such as Adult, t, Credit and P Parkinsons (see Appendix E.3 In these cases, the sample size is large relative the model's dimensionality, and convergence is fast (often within a few dozen updates). This allows training with large batches that reduce noise and still benefit from privacy amplification by subsampling. It also keeps the noise multiplier a (and Laplace parameter b) small, since the privacy budget is spread across only handful of steps. These favorable conditions (large datasets, low-dimensional models, and rapid convergence) explain why the privacy gap narrows, consistent with prior observations (Song et al., (0T3a). Once we employ higher-capacity models like ResNet16 on CelebA (see Figure 2a). the gap widens.
Satisfiability. The results in Figure 3 demonstrate that RacO-DP consistently achieves the pre-specified constraint values 7 as measured by the hard rate constraints. This marks a significant improvement over existing approaches, which typically rely on indirect hyperparameter tuning to influence constraint satisfaction. Our direct Lagrangian formulation offers practitioners a simpler and more reliable method for constraint optimization. Additionally, these results show that tempered-sigmoid temperature t = is sufficient to enforce hard constraints in practice.
Computational efficiency. We benchmark the average time per step for SGD, DP-SGD, RaCO-DP, and DP-FERMI via their public code (Gupta 2023). On identical hardware, RaCO-DP trains ihree orders of magnitude faster than DP-FERMI on Adult (Appendix E.5
Taget (him)
0:20
Test Hard Constroint
0.05
0.15-
0.15
0.10
Limitations. Koloskova et al. (2023) shows that gradient clip- ping biases SGD, which in our setting can push convergence outside the feasible set, making the clipping norm C' a critical hyperparameter. To illustrate this general issue (not specific to RaCO-DP), we impose a strict FNR = 0 constraint in logistic re- gression on Adult t without DP noise (o = 0, x)). As shown E norms below 12.5 prevent RaCO- DP from meeting the constraint, though weaker constraints allow smaller norms. Another limitation is the use of soft constraints for the dual update. Hard constraints can be applied in practice, although this departs from the theoretical guarantees of RaCO-DP; shown in Appendix E.4 this modification offers limited utility benefits.
0.00
0:445
0.66
0.100
16
1.77
0.175
0.080
0
Test Error
in Figure Ra of Appendix
Figure 3: Constraint satisfaction
on Adult.
7 RELATED WORK
To the best of our knowledge, private learning under general rate constraints has not been explored in prior work, except in the specific case of group fairness constraints. Accordingly, we review related work at the intersection of differential privacy and fairness, a key application area where early research has identified fundamental trade-off's between these two objectives (Cummings et 2019).
Existing work can be grouped into three main categories. A first line of research (Bagdasaryan an et al. Farrand et al.) 2020; Suriyakumar et al., [20T Tran al. 2021 Kulynych al. 2022 Esipova et al. 2022; Tran & Fioretto| 2023) Mangold et al. 2023) examines how privacy mechanisms can inadver- tently harm fairness. For instance, EEipova et al. (2022) characterizes the disparate impact of DDD due to gradient misalignment caused by clipping. The second line of work focuses on protecting the privacy of sensitive attributes used to enforce fairness constraints (Jagielski et al. 2019, Mozannar al., 2020 Tran et al. 2023). Unlike standard DP, which protects the entire dataset, privacy for sen- sitive attributes requires injecting less noise, leading to improved model performance. However, this approach has significant limitations. Individuals can still be re- identified through their non-sensitive attributes, and if sensitive and non-sensitive features are correlated, an adversary may still be able to infer sensitive attributes. Due to these vulnerabilities, such works are not directly comparable to ours.
The third line of work, closest to ours, seeks to jointly enforce DP and group faimess (Berradal
et al. 2023 Lowy al. 2023). Berrada al. (0023) use DP-SGD without fairness mitigation,

---

Published as a conference paper at ICLR 2026
finding well-generalized models show major privacy-fairees trade-off. However, their notion of fairesss is error disparity, arguably measuring subpopulation generalization. Our work shows that while mitigation is needed for demographic parity, appropriate algorithm design surmount the maimess--rivann trade-off. Lowy et al. (023) propose proxy objective for stochastic optimization of group fairness measures. In contrast, RaCO-DP supports broad range of rate constraints that can be frrely combined, without needing a task-specific objective. While its theoretical convergence rate is slower, RaCO-DP offers greater generality, complicating direct comparisons. Notably, Lowy et al. (2023) presents results for both sensitive attribute DP and standard DP (Definition 2.1 but their public code and evaluations focus on the weaker notion. Despite a stronger privacy guarantee, RaCO-DP achieves superior privacy-fairness trade-offs. We note that in contrast to Lowy et al. (2023), which seeks to satisfy the fairness objective by running an optimization procedure on proxy objective, our optimization algorithm more directly targets the rate constraint of interest.
Fairness aside, SGDA well-studied for minimax optimization (Nemirovski et al. 2009 |Heusel et al.) Lin et al. 2020), with Yang et al. (2022) proposing its first DP analogue. Private minmax optimization has been heavily studied recently (Boob & Guzmán 2023 Zhang et al. 2022 Bassily et al. 2023
2024 Gonzalez et al. 2024), though work non-convex losses is limited to (Lowy al. 2023).
CONCLUSION
We introduced DP algorithm using private histograms for training rate-constrained models. RaCO- DP demonstrates strong performance across various datasets and constraint types, often nearing non-private baselines while meeting privacy and constraint criteria. Our findings suggest that privacy- fairness trade-offs may be less significant than previously believed. Future work could explore private learning under individual fairesss constraints, which cannot be formulated as rate constraints.
ACKNOWLEDGMENTS
We would like acknowledge our sponsors, who support research with financial and in-kind contributions: Apple, CIFAR through the Canada CIFAR AI Chair, Meta, Microsoft, NSERC through the Discovery Grant and an Alliance Grant with ServiceNow and DRDC, the Ontario Early Researcher Award, the Schmidt Sciences foundation through the A12050 Early Career Fellow program. Resources used in preparing this research were provided, in part, by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institute. Michael Menart is also supported by the Natural Sciences and Engineering Research Council of Canada (NSERC), grant RGPIN-2021-03220
The work of Tudor Cehere and Aurélien Bellet is supported by grant ANR-20- CF23-0015 (Project PRIDE) and the ANR 22-PECY-0002 IPOP (Interdisciplinary Project on Privacy) project of the Cybersecurity PEPR. Tudor Cebere is also sponsored by Google Fellowship. This work was performed using HPC resources from GENCI-IDRIS (Grant 2023-AD01 401401
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS), 2016.
Alekh Agarwal, Alina Beygelzimer, Miroslav Dudik, John Langford, and Hanna Wallach. A reductions approach fair classification. In Proceedings of the 35th International Conference on Machine Learning, Proceedings of Machine Learning Research. PMLR, 2018
Alex Teboul. Heart disease health indicators dataset.
URL https: htttp:::/www.kagglle.. com/
Fugene Bagdasaryan, Omid Poursaeed, and Vitaly Shmatikov. Differential Privacy Has Disparate Impact on Model Accuracy. In Advances in Neural Information Processing Systems.
Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. Advances in neural information processing systems, 31, 2018.
10

---

Published as a conference paper at ICLR 2026
Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness and Machine Learning: Limitations and Opportumities. MIT Press, 2023.
Raef Bassily, Adam D. Smith, and Abhradeep Thakurta. Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds. In FOCS, 2014.
Raef Bassily, Cristóbal Guzmán, and Michael Menart. Differentially private algorithms for the stochastic saddle point problem with optimal rates for the strong gap. In Proceedings of Thirty Sixth Conference on Learning Theory, Proceedings of Machine Learning Research, 2023.
Raef Bassily, Cristóbal A Guzmán, and Michael Menart. Private algorithms for stochastic saddle points and variational inequalities: Beyond euclidean geometry. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Barry Becker and Ronny Kohavi. Adult. UCI Machine Learning Repository, 1996.
Leonard Berrada, Soham De. Judy Hanwen Shen, Jamie Hayes, Robert Stanforth, David Stutz, Push- meet Kohli, Samuel L. Smith, and Borja Balle. Unlocking Accuracy and Fairness in Differentially Private Image Classification, 2023.
Digvijay Boob and Cristóbal Guzmán. Optimal algorithms for differentially private stochastic monotone variational inequalities and saddle-point problems. Mathematical Programming, 2023.
Robert S. Chen, Brendan Lucier, Yaron Singer, and Vasilis Syrgkanis. Robust optimization for non-convex objectives. In NIPS, 2017.
Lynn Chua, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Amer Sinha, and Chiyuan Zhang. Scalable dp-sgd: Shuffling vs. poisson subsampling, arXiv preprint arXiv:2411.04205. 2024.
Andrew Cotter, Maya Gupta, Heinrich Jiang, Nathan Srebro, Karthik Sridharan, Serena Wang, Blake Woodworth, and Scungil You. Training Well-Generalizing Classifiers for Fairness Metrics and Other Data-Dependent Constraints. In Proceedings of the 36th International Conference Machine Learning. PMLR, 2019a.
Andrew Cotter, Heinrich Jiang, Serena Wang, Taman Narayan, Seungil You, Karthik Sridharan, and Maya R. Gupta. Optimization with non-differentiable constraints with applications to fairness, recall, churn, and other goals. Journal of Machine Learning Research, 2019b.
Rachel Cummings, Varun Gupta, Dhamma Kimpara, and Jamie Morgenstern. On the compatibility of privacy and fairness. In Adjunct publication of the 27th conference on user modeling, adaptation and personalization, 2019.
Damek Davis and Dmitriy Drusvyatskiy. Stochastic model-based minimization of weakly convex functions. SIAM Journal on Optimization, 2019.
Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring adult: New datasets for fair machine learning, Advances in Neural Information Processing Systems, 34, 2021.
Vadym Doroshenko, Badih Ghazi, Pritish Kamath, Ravi Kumar, and Pasin Manurangsi. Con- nect the dots: Tighter discrete approximations of privacy loss distributions. arXiv preprint arXiv:2207.04338. 2022.
Cynthia Dwork and Aaron Roth. The Algorithmic Foundations of Differential Privacy. Foundations and Trends@ in Theoretical Computer Science, 2014.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography, 2006.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Faimess through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, 2012.
11

---

Published as a conference paper at ICLR 2026
Maria S Esipova, Atiyeh Ashari Ghomi, Yaqiao Luo, and Jesse C Cresswell. Disparate impact in differential privacy from gradient misalignment. In The Eleventh International Conference on Learning Representations, 2022.
Tom Farrand, Fatemehsadat Mireshghallah, Sahib Singh, and Andrew Trask. Neither private nor fair: Impact data imbalance on utility and fairness in differential privacy. Proceedings of the 2020 Workshop Privacy-Presencee Machine Learning in Practice, 2020.
Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, and Chiyuan Zhang. Deep learning with label differential privacy. In Advances Neural Information Processing Systems, volume 34, 2021.
Naman Goel, Mohammad Yaghini, and Boi Faltings. Non-Discriminatory Machine Learning through Convex Fairness Criteria. In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, 2018.
Gabriel Goh, Andrew Cotter, Maya Gupta, and Michael P Friedlander. Satisfying real-world goals with dataset constraints. Advances in neural information processing systems, 29, 2016.
Tomas Gonzalez, Cristobal Guzman, and Courtney Paquette. Mirror descent algorithms with nearly dimension-indepeedeen rates for differentially-privee stochastic saddle-point problems extended abstract. In Proceedings of Thirty Seventh Conference on Learning Theory, Proceedings Machine Learning Research, 2024.
Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz. Numerical composition of differential privacy. In Advances in Neural Information Processing Systems, volume 34, 2021.
Devansh
Gupta.
2023.
URL
Moritz
Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29, 2016.
Kaiming Hc. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 20/6 IEEE Conference Computer Vision and Pattern Recognition (CVPR), 2016.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. GANs Trained by Two Time-Scale Update Rule Converge to Local Nash Equilibrium. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc.
Hans Hofmann. Statlog (German Credit Data). UCI Machine Learning Repository, 1994.
Matthew Jagielski, Michael Kearns, Jieming Mao, Alina Oprea, Aaron Roth, Saeed Charifi-Malvajerte and Jonathan Ullman. Differentially private fair learning. In International Conference on Machine Learning. PMLR, 2019.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International conference machine learning. PMLR, 2015.
Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can learn privately? SIAM Journal on Computing, 40, 2011.
Anastasia Koloskova, Hadrien Hendrikx, and Sebastian U Stich. Revisiting gradient clipping: Stochastic bias and tight convergence guarantees. In International Conference on Machine Learning. PMLR, 2023.
Bogdan Kulynych, Yao-Yuan Yang, Yaodong Yu, Jarost Bt asiok, and Preetum Nakkiran. What you see is what you get: Principled deep learning via distributional generalization. In Advances in Neural Information Processing Systems, 2022.
Christian Janos Lebeda, Matthew Regehr. Gautam Kamath, and Thomas Steinke. Avoiding pit- falls for privacy accounting of subsampled mechanisms under composition. arXiv preprint arXiv:2405.20769 2024.
12

---

Published as a conference paper at ICLR 2026
Tianyi Lin, Chi Jin, and Michael Jordan. On Gradient Descent Ascent for Nonconvex-Coneee Minimax Problems. In Proceedings of the 37th International Conference on Machine Learning. PMLR. 2020.
Max Little. Parkinsons. UCI Machine Learning Repository, 2007.
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of International Conference on Computer Vision (ICCV), December 2015.
Andrew Lowy, Devansh Gupta, and Meisam Razaviyayn. Stochastic differentially private and fair
learning. In The Eleventh International Conference on Learning Representations, 2023.
Paul Mangold, Michaël Perrot, Aurélien Bellet, and Marc Tommasi. Differential Privacy has Bounded Impact on Fairness in Classification. In ICML, 2023.
lbomoiye Domor Mienye and Yanxia Sun. Performance analysis of cost-sensitive learning methods with application to imbalanced medical data. Informatics in Medicine Unlocked, 2021.
Hussein Mozannar, Mesrob Ohannessian, and Nathan Srebro. Fair learning with private demographic data. In International Conference Machine Learning. PMLR, 2020.
A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. 2009.
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE Symposium Security and Privacy (SP), 2017.
Shuang Song, Kamalika Chaudhuri, and Anand D. Sarwate. Stochastic gradient descent with differentially private updates. In 2013 IEEE Global Conference on Signal and Information Processing, pp. 245-248, 2013a. doi: 10. 1009/GooalSIIP22033.666663
Shuang Song. Kamalika Chaudhuri, and Anand D. Sarwate. Stochastic gradient descent with differentially private updates. In 2013 IEEE Global Conference on Signal and Information Processing, 2013b.
Vinith M. Suriyakumar, Nicolas Papernot, Anna Goldenberg, and Marzyeh Ghassemi. Chasing Your Long Tails: Differentially Private Prediction in Health Care Settings, In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transpurency, 2021.
Latanya Sweeney. K-anonymity: A model for protecting privacy. 2002.
Cuong Tran and Ferdinando Fioretto. On the Fairness Impacts of Private Ensembles Models. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, 2023.
Cuong Tran, My Dinh, and Ferdinando Fioretto. Differentially Private Empirical Risk Minimization under the Faimnsss Lens. In Advances in Neural Information Processing Systems, volume 34, 2021.
Cuong Tran, Keyu Zhu, Ferdinando Fioretto, and Pascal Van Hentenryck. Sf-pate: Scalable, fair, and private aggregation of teacher ensembles. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI-23. International Joint Conferences on Artificial Intelligence Organization, 2023.
Arjun Wilkins, Daniel Kifer, Danfeng Zhang, and Brian Karrer. Exact privacy analysis of the gaussian sparse histogram mechanism. Journal of Privacy and Confidentiality, 14(1), 2024.
Zhenhuan Yang, Shu Hu, Yunwen Lei, Kush Varshney, Siwei Lyu, and Yiming Ying. Differentially private SGDA for minimax problems. In The 38th Conference on Uncertainty in Artificial Intelligence, 2022.
1-Cheng Yeh. Default of Credit Card Clients. UCI Machine Learning Repository, 2009.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rogriguez, and Krishna P. Gummadi. Fair- ness Constraints: Mechanisms for Fair Classification. In Proceedings the 20th International Conference on Artificial Intelligence and Statistics, 2017.
Liang Zhang, Kiran Koshy Thekumparampil, Sewoong Oh, and Niao He. Bring your algo- rithm for optimal differentially private stochastic minimax optimization. In Advances in Neural Information Processing Systems, volume 35. Curran Associates, Inc., 2022.
13

---

Published as a conference paper at ICLR 2026
A APPLICATION TO OTHER RATE CONSTRAINTS
A.1 FAIRNESS CONSTRAINTS
Faimess in machine learning aims prevent models from making biased decisions based on sensitive attributes. We aim to train a classifier under fairness constraints by formulating a constrained optimization problem. We consider two popular group faimess |Barocas al. (2023) metrics: demographic parity and equality of odds. All group fairness measures can be formulated as rate- constraints Cotter al. (2019h), for individual fairness (Dwork al. 2012) is easier bound the per-sample contribution and privatize it with clipping and noising in the style of DP-SGD, thus rale-constrained solution is not required, hence we focus on group fairness metries.
Definition A.1 (Demographic Parity). A classifier -():-) satisfies demographic parity with respect to sensitive attribute Z E = {1,... B1) if the probability of predicting any class k is independent of Z:
Pr|y = = 2| Pr(f = =k], V2 E 2,
where Y = h((;z)) 2) is the predicted label.
In practice, we do not have access to the true probabilities, so it is common to estimate them by empirical prediction rates Pt. Using a slack parameter 7, this gives:
Pa(D = 2|: 0) - Pa(D[Z + 2}:0) 7 V2E2
(13)
Demographic parity thus leads to J || | rate constraints of the form specified in Eqn. 6 The global partition of size Q = || with elements D. = DIZ = z]. V2 E 2, and for the constraint corresponding to elements
2 and y E V/ have I [1 2}. The associated vector has ( 1 and [112][==),
11 with the rest of the components set to 0.
Definition A.2 (Equality of Odds). A classifier h(0;-) satisfies equality of odds if the probability of predicting any class is conditionally independent of the sensitive attribute Z given the ground truth:
Pr|f k Y k', Z Pr|y
k. Z 2'}. Vz's Z,Vk, e
(14)
We note that the original notion of equalized odds is for binary sensitive attribute. For non-binary sensitive attributes, we can extend equalized odds to equalize rates between all subpopulations (as above), or we can consider counter-factual definition of equalized odds:
- k - Pty k. 2.
(15)
In the above formulation, we seek to achieve equal odds for each subpopulation compared to other subpopulations combined (e.g. white vs. non-white, etc.). It is clear that in the binary sensitive attribute, the definitions are the same. Our framework can handle either variant by changing the adjusting the local partitioning (see Section 3 but adopt the counter- factual definition.
We observe that the only difference between the equality of odds and demographic parity is the additional conditioning the ground truth, which will reflect as the additional predicate Y k in our base rates to define the following constraint:
Pa = K. K = 2]: P&(DlY = == <y Vz Z,Vk,
(16)
Equality of odds leads to J= 1 x 2 number of constraints. With regards to implementing Eqn. (6). use global partition with | x |Z| where each element is the subset of D with some fixed ground truth label & and class z. The constraint for some & [K] and E Z then has I which specifies the local partition {D\Y- k. Z =], D k. Z + 21} with the corresponding vector having a +1 coefficient corresponding to a prediction rate of D k Z 2].
Many other group fairness constraints exist but they are all reducible base rate constraints in similar manner. Note the similarity between Equations ( and (16), where the only difference the additional conditioning on ground truth labels Y in equality of odds.
14

---

Published as a conference paper at ICLR 2026
Objective
Formula
Number of Constraints
y (predicted),
Demographic Parity
Pe(D[Z =]: PA(DI + =]:0) 5
Va é (sens.)
yk, k e (predicted
Equality of Odds
PL(DIY - K2 - - =]:0) PuiD(y - - +12722;00 $7
and g.t.) Va Z (sens. attr.)
False Negative Rate
PA + R);0) 57
Vk (predicted)
Table I: Rate Constraints. Given dataset D, CD( the prediction counts for class k, and (D(D) = DD) is the prediction rate. D[prec] indicates the subset of D where predicate pred is true, e.g.. D y, 2| is the subset of D with sensitive attribute (sen. attr.) Z and ground truth (g.t.) labels Y y.
A.2 FALSE NEGATIVE RATE
Definition A.3. (False Negative Rate (FNR)) A classifier's false negative rate (FNR) measures how often it incorrectly predicts negative for samples that are actually positive. More formally, classifier satisfies a false negative rate constraint if
for k: E [[I]] PR # k):0) S 54
(17)
Assuming the constraint is well-defined, FNR leads = | rate constraints of the form in Eqn. 6 with the global partition of size Q Y with elements D, = DJY = y), E y. For the constraint corresponding to fixed E V we have I = (!/v) with an associated (<V/v) 1.
15

---

Published as a conference paper at ICLR 2026
B PRIVACY ANALYSIS
C Clog(T/6) OVTlog(TT8) and b 2 max
ry (oggo/()
Theorem B.1. Let 2 10x
then
r/
Algorithm 7 is (e,
Proof. The lz-sensitivity of (EzeBo) clip(1200 nlo))) is clearly at most C Thus the standard FIDT guarantees of the Gaussian mechanism ensures (ge1, 2 )-P w.r.t. the minibatch, where 61 S r log(1/8) and ô1 27 Similarly, because [D1. DQ} is partition, the & ei-sensitvv
(0)
min rV/ST of the histogram at most 1, and so the guarantees of the Laplace mechanism ensure (2e,, DP w.r.t. to the minibatch. By composition, the combined mechanism is (41; ) w.r.t. the minibatch. Since this mechanism acts Poisson subsampled portion of the dataset and e' < 1. the
privacy w.r.t. the overall dataset (E2, (2) with e2 rε1 S
and d2 S 27
rd Now
/8T (1g
applying advanced composition, the overall privacy of Algorithm 1 over ' rounds is (E3, d3)-DP with <3 (887)o S and 63 s (T + 1)62 I 8.
C TECHNICAL LEMMAS
Lemma C.I. Let X and Y be sums of kx and ky zero-centered Laplace random variables with scale parameter b, respectively, and let pxx pa >
O,
Pe
1, kx I ky. For any p E 1), if I
Jy 2 4ky b In 2p
then it holds that,
ux
X Y
4
{8)
P
<
In
-
2 1
(18)
BY
Bly
Proof. We have,
XX +
P
<E
MY +
Y
NY
X
PXY
<GpY +Y> Hx 2
P
+
(triangle inequality)
MY
+Y
BY
(NY +Y)
P
2X
+
2
<epy
Mx +Y>
(conditioning on jy + Y
MY
n2
2
2
2X
2Y
P
MY
+
(using Mr S Myy
BY
2'
NY
2
P
|
НYE
P M
PYE
P
Y
<
py
(Negation & Union Bound)
4
4
2
CYC
PYC
1
2 - 2 exp(
- 2 exp(
exp(
(concentration for Laplace Vs & Laplace CDF)
4ky
4kxb
2
ky
2 - eexp(
MYE - 2
expp
MYE
1
exp(
PaY
(ky 2 kx)
4kyb
4kxb
2
kyb
4 eexp(
PYE
1
exp(
NY
4kyb
2
kyb
PYC
2 - 4 4exp(-
4ky-b'
the last inequality uses that py 2 4ky bln (1))
Now setting
4ky In
yeilds,
ny
p
Mx +
px
4ky 4kybln(8/p)
P.
(19)
By
Y
Py
H4y
n
16

---

Published as a conference paper at ICLR 2026
Lemma C.2 (Error of sampled rates), Let Ex with E [0, and -x;cx," x
where
r|X]
X, obtained by performing Poisson sampling on X with probability r. 1f 2 log(1/p) then (up to an order):
log(1/p) r|x
P p-lpl= S
21-8
(20)
Proof. We have,
P Plp
prl [
Σx,xx X;
Exex Bern(r)xx r x|
P
50
(X, Poisson (X, r))
X
P
Σ
X,
Σ
Bern(r) X; Scr
X,EX
X,EX
e,2 1x|
2 1 exp
(Bernstein Ineq.)
2 (Var(Exxe) X,X Bern(r) [X] /3)
2,22 |X|
2 1 exp
(X; E [0. 1}; Var(Bern(r)) = r(1 -r))
2r((1 - -r) -r)r) cr/3)
2
2 2 exp
r(1 - r) s 1/4
21/4 + t/33)
log(1/p)
log(1/p)
e 2 2 maxx
x|X
x|X
log(1/p)
2 2/
(using the assumption that |X|r > log(1/p))
r|x
D MISSING DETAILS FROM SECTION 5
D.1 ADDITIONAL BACKGROUND ON STATIONARY POINT DEFINITION
For a smooth function f + R, a standard notion (first order) stationarity would involve bounding the norm of the gradient. However, for non-smooth functions, this notion does not accurately capture convergence. For example, if (0) = ||@]]. a point may be arbitrarily close to the minimum, but still have gradient norm 1. To address this discrepancy, alternative notions of stationarity for non-smooth functions have been introduced, such as Definition 5.1 In the example where f(() = ||@|| this relaxation allows points which are close the cusp at 0 O, whereas bound on the gradient norm would allow only the point 0 = 0 for any non-trivial bound on the gradient. In fact, our convergence proof yields a slightly stronger notion of stationarity known as proximal near stationarity Davis Drusvyatskiy (2019). We elect to present Definition 5.1 as it requires less background information.
D.2 PROOF OF THEOREM 5.2
In this section we will detail the proof of Theorem 5.2 and provide a more precise theorem statement. Before doing so, will introduce some important notation.
HEl For any [ [Q], let D = U Dr. Given a subset B D, define Bri = Bn (., and recall that sel
I, and aj E [ denote the corresponding family of susbets of [Q] and weight vector associated with constraint 3, Let = min (1))..
Let ||A]] be the & diameter of A. Let G₁ and G₁, be the & Lipschitz constants w.r.t. of h and l respectively. Similarly, let 3r and Bh, be the corresponding fg-smoothness constants. We recall
17

---

Published as a conference paper at ICLR 2026
the temperature parameter of the softmax is denoted Let c maxje([] ||ysll Note that many rate constraint only compare two prediction rates, and so cj is typically at most 2. Define
(()) ming { (0') e| 8' }²] and e ((u) ming (((8) and Lo [(Os. Ao)
minx,0 {C(X, } (see Section D.6 for more details these quantities). We more complete version of convergence result.
present the
. 8log(J Then, under appropriate choices of parameters, Algorithml run without clipping (c, 6DDD and with probability at least - p there exists E [7) S.I. Og is an (a, 0z (/(22))) point of d with
Theorem D.1. Assume n 2 max (20.JT) 8 In )
= == 1/4 +VBu++++
((
(Vlloggn/)) Vog(())joJK)))) 1/3
K A /og(m/0((oo(JKK///) (ne)
where G = Ge + GallAll and 3 = Be + 2CT max
GRVD, + -Bh))
Proving this statement will involve several major steps. First, Section D.4 we derive the necessary noise levels needed to ensure that Algorithm| is private. Second, in Section D.5 we bound the error in the gradients at each time step. Next, in Section D.6 we give a general convergence rate for SGDA derive the overall Lipschitz
under the condition that the gradients have bounded error. Finally, and smoothness constants L. based on the base smoothness and Lipschitz constants in Section D.7 These results are then combined in Section DD3 obtain the final result.
In one final remark, we note the following fact will used in several places.
Lemma D.2. Let 2 4log [ D(pp) and E [T]. With probability at least 1 p it holds for every j E [J] and T E I, that [B(] 2 Tm..
Proof. By Lemma
we have for any j [J] and E I,,
P Trlpii-IBh) 2 VriDi(log(1/7) S:
Thus since [r} 2 n 2 log D)pp), holds with probability at least a. for every j E [J] and
E I that |Bul 2 r|Dıl (og))|log(11) 2 0.5r| 2 0.5r
D.3 PROOF OF THEOREM D.I
With the previously established results, theorem statement. Specifically, we set,
verify setting of parameters which proves the
4/3
GVTlog(T/O)
TVTooogTTO
mE
TEE
T min
Va
K
me
Note that by Theorem D.3
this ensures that Algorithm is (c, DDD so long as r 2 /T.
Using Lemma D.4 can now instantiate Theorem D.5
For Tq we have,
KKblog p)
log
JKn p
TA
+ a
rn
rm
JKn log
èi K T (Tg() log( (J JKn/p)
=0
+ Ci
nc
rm
18

---

conditional on Published as a conference paper at ICLR 2026
Setting TA the quantity above, write the bound тØ as,
+ 4G, 4Gg//og(4/p)
4G AGeylog(4/9)
To = 0 Vilo
+ +-AlII-GATT)
Vr|D]
Vr|DI
Vlog(1/p) dT (T/p(T))))))))o log (Tg())))
G
+ ||A
ne
Vr|D
Now, in the non-trivial regime where Ta I G, Theorem
D.5 implies that for large enough,
( + +
1/4
VBLu
0
T 1
71/4
VT VVlog(T/ (5) (og(JKK//))) 1/3
-0
((BnSCe) 1/4
+VBLo+G) +G) ((
+BBLO
K1/4 v / //
(/c)
D.4 PRIVACY OF ALGORITHM| UNDER LIPSCHITZNESS
Theorem D.3. Assume h and are Ge and GA Lipschitz. Then for some universal constant e and TV Tog(( (6)
c(ci [[]T Ge) max log(T/5)
CVT (og(T and b 2 2 max
f then
TI3E
RE
Algorithm 7 is (c.
Proof. First, by Lemma D.2 and the conditions of Theorem D.I probability at least 1 - 6, for every t E [ [J] and I [7] it holds that Bhul > 0.5r Consequently, the concentration of Laplace noise and the conditions of Theorem D.1 imply Σier E A 2 0.25rn with
probability at least 1 26. Conditional on this event, the fz-sensitivity of (ErEBro) g(.)) is at most
+ eirGa since then,
0.25rm
AAag.LK (blo0((((0:))))
c/|AA|TGr
Σ Σ
Σ
KEK 0.25rn
0.25rn
j=1
Thus, the scale of Gaussian noise implies that the releasing the primal gradient is (2 (6)1)16)-DD -DP w.r.t. the minibatch, where 6 S min / /ogg(1/6 and ò1 $. From here one can follow the
same steps as in the proof of Theorem 4.1 to obtain an overall privacy of (c, 8)-DP conditional on the previously mentioned event that each Bry is large. Since this event happens with probability least
1 - 25, we obtain final overall privacy guarantee of (e,
D.5 BOUNDING GRADIENT ERROR
Lemma D.4. Let p [0, and [T]. Under the assumptions of Theorem D.1 g(t) X10 it holds with probability at least 1 2p that,
AGe/Tog( log(1/p)
l1 voL(O!)) xx /
Vr
8ci Kblooog(/4JJKn/p +
log
S.KK
||A|ITOO
P
m
log 8JKn
8c, Kbloo(((6JJKK//)
(10 (0000000000100
+a1
19

---

Published as a conference paper at ICLR 2026
Proof. We will bound each term separately.
Error of the Dual Gradient.
We start with the following bound,
- E Os.Ik Eier H!)
P [10 Vxc(o (,.(0"1,1")11 1|, 2 2 =
)1x
Σ /EJ, k=1
1V
Σ
H(t)
EE
like
IETREEK
K
E1er
11
1 [10 P
Pa(Di)
Σ Σ
A!!
123 k=1
1,k2
iETR2EK
(21)
We thus have for any + = that,
P (Di: E1Er (
E1Er Hitt)
IV
P
PA(Bri)
Hit)
Σ Σ Hitt)
iETKZER 1.02
1ETKEE
Pa(DD) PL(mn)) PM(Bri) Eier Alt))
$1 P
Σ Σ A
2
Pa(Bri) Eier 11(1)
$ 1
P Pa(n)l Ci
V
2 1
Σ Σ 17(0
Eier i
s P P +
61 P
Pa
IV
21
Σ Σ
L,k2
EETKEK
We will start by bounding Pl Pa((Br) Eier f1 Σ Σ H:0 LEikgEK
for any fixed / and k. Observe that
conditional on Bor), the sampling process is equivalent to drawing B samples uniformly at random from [Dr without replacement. Therefore by Lemma C.I we have,
Eier
1.k (
4K b (ogg66g
Pa((ni)
Brul 5
P
Σ Σ
(1(t) 1,k2
Baul
4JKn
iETKZEK
Now by Lemma D.2 P P[ $ 51
$ 4.KK and so,
EiEr A
8Kblog(16J/kn/p)
P
Pa(in))
Σ ΣΣ H
rn
2J
EETEEK
Thus suffices to have 61 Se, (og()G)(nnn)))
rm
Looking now at the statistical error term and applying Lemma C.2
we obtain:
log
2J
P 2JKn
P ( - P
<
(22)
r|Drl
log( 2(ke) r|Dr
log
log( 248g m
Observing that
<
one can see suffices for 62 C1
20

---

Published as a conference paper at ICLR 2026
Plugging 61 + 62 back into Eqn. 21 obtain
Sc/blog(16//K/pp
log
2J p
1
Vxc(O
1oo
+c
77
776
K
1 [ * #0
Sp. p. JKn
P
FEJ,
This proves the claim.
Error Primal Gradient. First observe that
ll0e VoL(00)) < ||z + Vol(0d)) ||
Vel(0();)))
D
xE
+ VeR(o(0),200
Σ
R(((0) A H. x)
ZEB
For ğo RRd, using the concentration of Gaussian noise obtain,
PIIZ 2 a / /llo(///)))))))) S 0
For the second term, by Bernstein's 's inequality we have
02/2
P
Σ
vol(0,>;.;) - -r( Ae)
2 S exp
aG,/3 (-aGr/3 + GD max fr, 1/2]
VEBI
Thus with probability at least one has that,
Gi Gev (oVlog(4/p)
Ge log(4/p)
Σ
Vol(o, x.
Vol(Oe, Ar) S max
r D|
vr|D)
r D
And so r|D| > (4)p) we have with probability at least 1 - p/4 that,
Vol(o())
1
Σ
vol(o(0;)))
4G / (og((//))
r|D
Vr[D
ZE BE0)
For the regularizer we have,
(oR(0( ,100=
Σ R( 200 H,
ZEB(O)
ΣΣΣ Σ j=l TeT, [[E[
A Cy 1rr (1():))))
ΣΣΣ Σ rED TEI, krglk]
A ag.tk, 1
Vo (h(02))))
Σ Σ
H(t)
Σ Σ 1(())
EEf kzE(K)
NET kg
ΣΣ> Σ
dy 1
1ΣΣ Σ #=D TET, KTE[K]
\ aj,, 1peBmll
7Gh
Σ
Σ
Σ Σ iT!))
TE7, k
1e7 kse[K]
fEf k2E[K]
Drl
Brd
ajI.k
Σ
(
Σ
Σ 1
7G
JEL, k
1,82
NEI
NET kgE(A)
Σ
Σ Σ
CJSA Dr
Σ Σ
ag.L. Bri
TGr
Σ Σ 1,kg
Σ
Σ
j=l
Ie4, k
IEZ, kL
iikg
kg
P
21

---

Published as a conference paper at ICLR 2026
The term inside the absolute value can be bounded using the same analysis used in bounding the dual gradient error. Thus we have with probability at least y that,
Se1 Kolog((6AJK////
log
8JKn
Vo
E xEB
7 H,, x,
||A|IIGGA
+a
rm
rn
Combining the above bounds yields the claimed bound on the primal gradient error.
D.6 CONVERGENCE OF SGDA
The overall structure of convergence proof is similar that Lin et al. (2020), but with several significant modifications. Most significantly, our proof explicitly leverages the linear structure of the dual to improve the convergence rate for application. This linear structure also allows analysis to depend on an || Ilso bound on the gradient eπror when A has bounded || || diameter. This in contrast previously existing analysis which depend on the || ll2 error of the dual gradient, which could be much worse in our case due to the noise added for privacy. Separately, our analysis also differs from Lin al. 2020) in that accounts for potential bias in the gradient estimates and tracks the disparate impact the scale of noise in yo and yA may have on the convergence rate.
Lin
In order to present our proof, we start with some necessary preliminaries. Let $(0) = maxλeλ {C(0, })}. Let & denote the Moreau envelope of with parameter 23. That is, (0) ming (0') + 33 - - Let (t) = ((0()) - L()(), (()) for all / E (0...., T)- Further, we define X0)))= = arg max (C(0. A)}. We denote the proximal operator of a function as (f) = arg min, {f(0') + 210 31 is known that under the condition that f is 3-smooth and A is bounded, that & is differentiable with V 23(00 prox4/[2s] (0)), and that any point 0 for which which
V (0)l S is an ( -stationnry point with respect to Lemma 3.8). Also, under these conditions, & is G-Lipschitz. We 2020) for more details on these statements.
Definition 5. see Lin et al. (2020
defer the reader towards Lin et al.
We present the following statement, which gives a convergence rate for Algorithm Min terms of the amount of noise added.
Theorem D.5. Define Lo (00) { (5(0)} } and Co [(Oo, Ao) minnx (C(A, 0)} Assume C(:,)) is B-smooth, ((,, is G-Lipschitz for all E and L(0,-) linear for all 0 E Rd. Conditional on the event that for all E (0...., - 1}, 11 VoL(O(t), ,((0))) S and 19
VxL(00) {(1) S Tx, when Algorithm / is run with yn > 1oGiG-TO) and no V 27 B there exists E {O...., T - 1} such that 0g is (a, (233) stationary point with
Ts
a= (0o0(GP + +1
1/4
VBC VT
+
II +
T1/4
We will prove this statement by showing that Algorithm finds a point where the gradient of & small. Note this is sufficient as Lin et al. 2020 Lemma 3.8) implies that a point, 0, for which [[)(()) < a is (a, ( point with respect Definition 5.1
We will break the majority the proof into three distinct lemmas. The first lemma gives a bound on the decrease in $.
Lemma D.6. Under the assumptions of Theorem D.5 the iterates of Algorithm satisfy for any E [T -1,
$(8(1)) ((((t-1)) < (V + 28 (1 23 + +//) + 2n (23)
22

---

Published as a conference paper at ICLR 2026
Proof. Let ((t-1) prox (B(-11)) By the definition of the Moreau envelope we have
$ (((()) S ()((-1)) + B1(0(-1) + 100)
(24)
Using the update rule we have
[]((--1) - 0| 110(t-1) - 0(0 + -1090
(e- 11
110 1) - -0(-11) 12 + 227 (0(t-1)- 0(t-1),
-((-1) 900 111-1)) n 11166-11112
|100 1) - g/a-1) +
+ 2no ( (0(t-1) - g(t-1), VoL(o( 12 110-1)))
2noo (ő(-1)) ,((-1) 90 (1-1) VoL(O(t-1) )(-11) 21 + +5)
Plugging this back into Eqn. (4) and using the definition of the Moreau envelope we obtain,
)(((()) I ((((t-1)) + 2890 (Bi-1) - p(c-1),
VoL(O ((10)11)))
+ 28
- - "221 (e-1)_
VoL(0(t-1), (1 + 2. + Ti)
(25)
By way of bounding the third term on the RHS above, we use Young's inequality to derive,
2 (ou-")- g(t-1), ge 1-11) VoL(OUL-)) ))- S 8110 -1 11- + 2no 119 1-11 VoL(O 11111)11
Plugging this into the above, we now have the following derivation.
8(0(0)- ((((t-1))
$ 231 (gu-1) (((-))0((-1) VoL(Ou-) (()))))))))))))) + 8'100 -00-011 +29m + + 2
( 28n ((00-11) ",0-1)) c(B(t-1) (1-11)) + 33 |1 11 - - + GG + +7)) + 210
s 23no
(((()11) - c( (
)(--1) + 33 p - (gc-1112) + 231iie" + + 27
((00-1)) + +(0((-11) 1) -((0(-1)) C(ple-1) ((-11)+ + 33 p glt 1112²)
233
4
+ 2
(G" + TH) + 27
(44)
1 2,31j0
(-110--1) 01t 1
2 (t-1)
3/ |²t- 0
33
(C² + -3) + 2n
7o.
[| 1/1-19 23 (1-1) + (G + Tう) + 2707ē
(112)
Till (V 23 (t-1) + 2 GC + Th) + 2 Th
Above, (i) uses the fact that ((1-1) is generated by the proximal operator. Inequality (ii) uses the fact the definitions of the Moreau envelope and A (t-1), i.e. | 0(t-1)112 = 4 Equality (iit) uses properties of the Moreau envelope.
The next two lemmas pertain to bounding the A (1)) terms.
Lemma D.7. Under the conditions of Theorem D.5 for any E [T] and s S l 1 one has,
A 1t-1) < GO + r2)(2t - 2s- 1) +
|| (B(+)) - ((0113) + 2|| 117x 1 (122(0(0)) - (1-1))1
21/2
+ + 1(0le-1), (((111))]
(26)
23

---

Published as a conference paper at ICLR 2026
Proof. Let - 1. By adding and subtracting terms we have
= (t-1)=
(C(0l (0(t-1)) 2(0(t-)) (xx(0 (C(0 ,10)) C(0(t-1), (
+ -((000-1) (10)- C( (1 + (C(0(=))) ()(0(=))) - _(0(--1) 1,]
< (2(00-1), (2 L(((e-1) x x0 + (=(00-"))
X -2(0(0)) -((00=11x'(0001) [)()))
+ (C(00)) ) - -(((0-1), ,2 ( (C(0(-)), (0) =((()) 1111]= + (E(0((-1) x-(0(=)))
s G(G 10)12110( - 1100 - 110 o || + (C(0()) (110) ((0lt-1), ,(((111)
+ [[(()(-1) X' )) L(0't-1) (()))
< +noG(G++
2s 1) + ((() c(0(e-1), )| + (E(0(t x (0(00)) -((((-11) -1 ((())))]
X To complete the lemma, will bound the loss difference [(((t-1), (0(11)) L((((-1), 1(10). Since L(((t-1),,) .)) is linear we have, 1(((t-1),
1(1=1))- (((-1)) - C(Blt-1), 1), 119) = (1 (1((-1)-((0 VXL(0(--1) (110))
< { - -(00, + (1 - 11),, 1) -
1 ( (A(-1) - -100, 90) + 11 VAC(o((- ((11) - 92 )1o00
(1)
(N1-1) - A10) \10, (0) + +|AIIITT
Now a standard analysis using the fact that (1 + 9
is projected orthogonaly onto A we have
0 < [| - 10 < - - (0le-))) - (1-1) 211x
1
|| (0(--11))) - 10 + A ( 200) - 1²))
21/A
Now by plugging back into the above yields,
C(0(e-1), (((-1)) - ((0(e-1)2(0))
1 (x-(0())- 11)) x()o(()) + 11A11172 + 2 11 - 1 (2- 1000
-1(1-1112-
2n12
2712
Using concavity we obtain,
((((())) - (()(t-1), ,))) - (2^(0())) - -100 - (=(0r(-),x(0))) + +1AA1117
1
| - 10-
1 11 (0le-111 110
+ 2m1>
2n1x
1x-(0(=11) - 11- _ (2<(0(t-1))) - -2001 + A|I
2//x
2njx
Plugging this back into the starting inequality achieves the claimed bound.
Lemma D.8. Under the conditions of Theorem D.5
it holds that,
T-1
Go + To) + 2|AA|I +
[(OT, AT) L((0,,
Σ A
T 1
T
Proof. For any 8 E [T] and M E [T] one has by analyzing the telescoping sum created from Eqn. (26)
that
$+MM
(t) S G + T0)M²
1 (11(0)) 20(0(0))12 + |1(++t))= + 2.M I
211x
+ +IC(000+M), ((++M)
- C(8()), (1(006+)),,(+++0))) (
Sn00(G +² 7 |AAl/ -2M + (2(00+tM)) ((4.20)) -
STGG(G + |||| + + (2(000100, ((0+MM) - ((O(O), ((00))
24

---

Published as a conference paper at ICLR 2026
By applying this inequality over disjoint "blocks" of iterates, of which there most T/M, can use this to obtain,
Σ
v S
Mrx |AIR + 2 + Lo
T
T
=
We can now set M
||]
to obtain the desired inequality.
v / G(G+Ta)
can now prove the main theorem statement.
Proof of Theorem D.5 Recall d = -00) -ming {6(0)} and Lo L(0o, Ao) minnx, {2(2,
Summing over Eqn.
obtains,
(00 S (00) + 28m
Σ
( + +T + T8) + noT
n
(0(00))
Which implies for any M [T),
(
4
88
(--1
Σ A
+ +4 + + 4T
T
noT
T
1=
8,3
Tg) + +4rØ
ToT
Gn To)
ABI + 88L0
13
11x
Inequality (i) above uses Eqn.
26 Setting 1/ 2
yields,
1
T-
4 <
83L0
+ 837 + + 4T + 16631AA117x +
T
noT
T
Setting n7
2T yields,
16 3 + +
16,30o
v (B(t))))
+ 163 +
T
VT
T
Finally, this implies the claimed convergence.
(#h02 ( +13) 1/1
1 T
Σ |
+ To + BIIA|ITTA +
V3Lo
71/4
VT
D.7 REGULARITY PROPERTIES OF LAGRANGIAN
We will use the following standard fact about composing Lipschitz and/or smooth functions.
Lemma D.9. Let Rd + Rk be GR -ipschiti and Smostooth and g R² + R be Gy LipLichhi and Syoohh Then g h is (GnGg) and (Gv3g + +333k)-smoothh
25

---

Published as a conference paper at ICLR 2026
Proof. Let Jn, (0) denote the Jacobian of h at 0. Since h is GA. Lipschitz, the spectral norm of the Jacobian is at most G₁, [0) S Gh. Observe Vog(h(0)) VV(h(()) (0). Thus [Vog(h(0))] I [V((h(0))] ( I G.G..
For the second part of the claim, observe that,
(Vg((h(0) Vog(h(O'))l <
[I[Vg(h(0)) - VVg(h))))J[() + Vg(h(0))J,, (x')l)
- (Gh,, + GyBh))l0 1l
In the following, assume the predictor h is G -i--iisscitz and Bmosto with respect h, and similarly for with parameters Ge and 3r. Our aim is to derive regularity parameters for the Lagrangian given these base parameters. Note that the function which outputs one coordinate the tempered soft max is r-Lipschitz and r-smooth.
XXQ be a bounded set of diameter at most ||A|| w.r.t. -1. Assume for any j [J] that the vector associated with rate constraint satisfies ||a]]] I C1 for some constant c. Then L(:, X) is G-Lipschitz with = G. + CrGal|A|p for any X E A and L is 3-smooth with
Lemma D.10. Let A C. (R+))xxQ
3g + 2cr max JI + +.)))
Before presenting the proof, we that Ge and Be could also be further decomposed using the Lipschitz/smoothness constants of l and h via Lemma D.9 However, as these parameters are not affected by our approach in the way the regularity parameters of the regularizer are, we omit these more specific details.
Proof. Let for I [ [Q] let D, = User Dy. To establish Lipschitzness w.r.t 0, we have for any 0, À that
K J.I.k
VoC(O, > | + Σ
Σ
VoPA(Dr;0)
1=1
IEJ;
k
max S GG + ||l|ac1
(5:00)))):0)1)
Note that for any S C D and & E [K] that TGr. Plugging this into the above achieved the claimed Lipschitz parameter.
Exes E (o(o,(((0;z)))ll1 -
To prove smooth, we have for any 0,0' of IRd and X' E A,
|V A) VL X)I < 2 A)
= =2 - VoC(O, V= 1 + 22/ V VAC(8,)))1
26

---

Published as a conference paper at ICLR 2026
Bounding each term we have,
- - VoL(0, -
[Aj -g) Σ Σ
Air (D 8)
TETT
- SarGh - X
SarGA VJIA X112.
[VC(0, - VXc(O, =
J Σ
VoC(0,1) Voc(O', X)1I (Vo((0) Vol(0')|+
Σ
X3
TEJ;
12 Bel10 - 0'11 + ||Alicc (GNT + + 0'11
$ (3: + c, [llAlII + T3x))110- -811
[V>c(0,)) VAC X)II S
Σ
1/
ajgk (Pa(h(0;)) Px(1((=)))
i=1
TET,
A=1
(0) G
|||| 0+ 0'll
Above, in (i) we have used the fact that P& is the composition of Gi-Liphchitz and 3n-smo function with a --Lipschitz and r-smooth function, resulting in a + --moooh function. Similarly, in (ii), we have used the fact that P& the composition of two Lipschitz functions. resulting in another Lipschitz function.
Ultimately we obtain that [[VC X) - VL(00, 22 is bounded by.
max { ( [Be ||A]Icc] + 7 32 [ar||||] (110 (10- 0'12 + 1|a - 1113).
This implies that f is 3-smooth with 3 = Br + 2c1T max ( [IV + +
E ADDITIONAL EXPERIMENTAL DETAILS
E. DATASET AND PRE-PRSCES DETAILS
We evaluate RaCO-DP on tabular fairness and privacy benchmark datasets from Lowy et al. (2023), namely, Adult (Becker Kohavi, 1996), German Credit Card (Hotmann 1994). and Park nsons (Little) 2007). The classification task for Credit Card and Park i nsons "whether the user will default payment the next month", and "whether the total UPDRS score of the patient is greater than the median not," respectively. For Adult, t, the task is "whether the individual will make more than $50K." " In all tasks, the sensitive attribute is gender.
To evaluate on more diverse subgroups. we also evaluate RaCO-DP on folkstables which is the 2018 yearly American Community Survey. We use the python package 'folktables' (Ding et al. 2021) to download and process the data for the Alabama ("AL") state in the US. We choose "5 -year horizon and choose survey option to be 'person." We adopt the experimental setup of Lowy et al. (2023) (including classification task, pre-processing, etc.) and report the baselines results directly from the official repository (Gupta 2023).
We also present results the Heart Disease Health Indicators dataset Alex Teboul (21 risk factors).
To prove the scalability of RaCO-DP on neural network, we train a ResNet16 He et al. (016) on the CelebA dataset. CelebA (CelehFaces Aurrbutes Dataset) is a large-scale face dataset containing
27

---

Published as a conference paper at ICLR 2026
Dataset
SGD
DP-SGD
RaCO-DP
DP-FERMI
Adult
0.018 + 0.001 ms
0.037 0.001 ms
0.064 + 0.010 ms 0.055 = 0.003 ms
85 + 10 ms
CreditCard 0.020 = 0.005 ms
0.035 0.004 ms
88 + 14 ms
Table 2: Computational overhead comparison terms of wall-time clock.
200,000 celebrity images, each annotated with 40 attribute labels (c.g. smiling, eyeglasses, or hair color) and five landmark locations, widely used for training and testing in computer vision tasks such as face recognition. For the fairness constraints, CelebA used with gender as the sensitive attribute.
E.2 HYPERPARAMETER TUNING AND ACCOUNTING
Our hyperparameter selection process follows a two-phase approach. In the first phase, we run hyperparameter search over predefined ranges: Gaussian noise variance
[3. 6]. Laplace parameter b E 10.1, 0.5). learning rates Tjo 1JA E [10-1, [01]. mini-batch size B E [256, 1256). and softmax temperature
[1, 10). We constrain the dual variables À be non-negative by setting the projection set A = (IR (R+)". For each configuration, we target a specific constraint value and evaluate performance across five different seeds, selecting the hyperparameters that achieve the best validation accuracy while satisfying the constraint. In the second phase, we use the best hyperparameters identified through 200 optimization runs to train new models. We report test accuracy and constraint satisfaction for each model based the checkpoint that achieved the highest validation accuracy while satisfying the constraints on the train set.
Recent work by Lebeda et al. (2024) and [Chua et al. (2024) shows that the common use of shuffled fixed-size mini-batches can violate guarantees from privacy accountants, which assume Poisson sampling. Therefore, we use Poisson sampling for the mini-batches.
E.3 REGULARRIATION-PPVAAYYYYA
TRADE-OFFS
Demographic Parity. In Figure we compare fairness-utility trade-off's of RaCO-DP against baseline methods on logistic regression models trained with demographic parity constraints across the Adult, Credit-Care
and P Parkin kinsons datasets. We evaluate range of privacy budgets e E {0.5, 2, 9}. Consistent with the main results in Section 6 RaCO-DP significantly narrows the gap to the non-private baseline and Pareto-dominates existing private baselines.
the flexibility of our framework beyond fairness constraints by enforcing limits false negative rate (FNR, i.e., recall). Controlling FNR is particularly important in medical settings. For example, on the Heart t dataset, XGBoost achieves 90% accuracy but suffers from an FNR of 90%. Non-private SGDA reduces FNR 58% with 87.5% accuracy, while DP-RaCO nearly matches this trade- off with 60% FNR at the same accuracy (Figure 5b). We also observe that once the constraint threshold is pushed beyond a certain point, RaCO-DP fails to further reduce FNR, an effect discussed in Section (Limitations) and analyzed in Appendix E.6
False Negative Rates.
Equalized Odds. In Figure 6 we show results on Cred Ca rd dataset for logistic regression trained under equalized odds constraints. The performance trends mirror those under demographic parity. Note that the DP-FERMI results are taken directly from Lowy et al. (2023) and not re-run; as reported, both mean and variance remain unchanged across privacy levels {0.5, 1,3,9.
E.4 HARD VS. SOFT CONSTRAINTS
Figure 8b compares soft and hard constraints for the dual update. Notably, the soft constraint (with tuned softmax temperature т) achieves similar performance compared to its hard constraint coun- terpart (solid dots) for most target values while maintaining similar levels of constraint satisfaction. This suggests that using soft constraints for the dual update does not significantly impact utility or constraint enforcement.
28

---

Published as a conference paper at ICLR 2026
== 0.5
0=
0'
Denographit Disparity
0.15
0.10
0.05
0.00
0.15
0.20
0.15
0.20
0.15
0.20
0.15
0.20
Test Error
Test Error
Test Error
Test Error
RaCO-DI DP (ouns)
SGDA
Tran (2021)
DP PERMI
Jaginiski et (2019)
(a) Adult
0.5
3
9
Demographit Disparity
0.020
0.015
0.005
0.175
0.200 Test Error
0.175
0.200
0.175
0.200
0.175
0.200
Test Error
Test Error
Test Error
RaCO-DP (ours)
SCDA
Tran (2021)
FPRFERMI
Jagsclala (2019)
(b) Credit-Card
0.5
1
Demographit Disparity
0.08
0.06
0.04
0.02
0.00
0.05
0.10
0.05
0.10
0.05
0.10
0.05
0.10
Test Error
Test Error
Test Error
Test Error
(ouns)
(2021)
Jagiekaa (2019)
(c) Parki inenns
Figure 4: Fairness-utility trade-off's under demographic parity constraints for logistic regression on three benchmark datasets. RaCO-DP consistently reduces the gap to non-private performance and outperforms private baselines across privacy budgets & E (0.5, 1, 9}.
29

---

Published as a conference paper at ICLR 2026
c: 0.5
9
0.3
False Nogative Rate
0.2
0.1
0.0
0.2
0.4
0.2
0.4
0.2
0.4
0.2
0.4
Test Error
Test Error
Test Error
Test Error
RaCO-DP (ours)
SGDA
(a) Adult
0.5
False Negative Rate
0.8
0.6
0.4
0.2
0.4
0.2
0.4
0.2
0.2
0.4
Test Error
Test Error
Test Error
Test Error
RaCO-DP (ours)
SGDA
(b) Heart
Figure 5: Performance Performance-privacy trade-offs under false negative rate (FNR) constraint. On the Heart dataset, RaCO-DP achieves accuracy-FNR trade-offs competitive with non-private baselines.
0.5
0.05
Odds Disparty
0.04
0.03
0.02
0.01
0.175
0.180
0.185
0.175
0.180
0.185
0.175
0.180
0.185
0.175
0.180
0.185
Test Error
Test Error
Test Error
Test Error
RaCO-DP (ours)
DP-FERMI
Credit-Card
Figure 6: caamess--tility trade-offs under equalized odds constraints for logistic regression on the
Credit c-Card dataset. Results for DP-FERMI are taken from Lowy et (203)).
30

---

Published as a conference paper at ICLR 2026
0.5
0.6
Demographi Disparity
0.4
0.2
0.0
0.2
0.4
0.2
0.4
0.2
0.4
Test Error
Test Error
Test Error
RaCO-DP (ours)
SGDA
Figure Fairness-utility utility trade-offs under demographic parity for logistic regression on the ACSEmployment dataset.
Fairness
0.200
Targ 008
0.7
RxOD-DP
Test Hard Constrshut
Tags 0.1
0.150
Tago 1 0.10
0.6
Tarpet 0.2
0.125
Achieved (Soft)
0.5
(lard)
0.100
0.4
0.075
4
0.050
0.025
0.000
0.145
0.130
0.138
0.000
0.109
0.770
0.173
0.180
5.0
17.5
Error
(a) False Negative Catt-Constrained Classification Adult. The clipping norm C' plays critical role in satisfying a pessimistic constraint (y 0). even with out noise related to differential privacy (a 0, oc).
(b) Hard Soft Constraints on Adult. Trade-off be- tween test error and demographic parity. Dashed lines show target constraints, with soft (hollow circles) and hard (solid dots) implementations achieving similar performance.
Figure Constraint Analysis on Adult Dataset. (a) Effect of clipping norm on false negative rate-constrained classification. (b) Comparison of hard vs. soft demographic parity constraints.
31

---

Published as a conference paper at ICLR 2026
E.5 COMPUTE PERFORMANCE
We provide a computational comparison between methods in Table where we report the mean time of computing an SGD step, compared to a DP-SGD step and RacO-DP step on an eight-core CPU machine on Adult and Credit-Cart on a batch size of 512. For reference, we also report the mean time of DP-FERMI step using the publicly available implementation.
RaCO-DP is 3 orders of magnitude faster to train than DP-FERMI on the same machine. Our algorithm builds on DP-SGD with the only additional overhead being computing the dual updates, which scales linearly in the number of constraints.
We note that our method's s extra cost over standard DP-SGD computing the dual update, which, if implemented naively, scales linearly in the number of constraints Q. implying Q extra backward passes to compute the gradients the worst case. However, practice, we can compute the gradient only for the active constraints (A(s) 0), which can significantly reducing the computational costs.
E.6 IMPACT OF THE CLIPPING NORM
Figure Sa shows how the clipping threshold C' affects RaCO-DP when we enforce a pessimistic constraint of FNR < 0 on the ADULT dataset, in a non-private setting (o = 0, small clipping norm (C 2) the empirical FNR violation is still above 0.6, confirming that the bias introduced by clipping alone can drive the iterates far outside the feasible set. As the threshold increases, this bias shrinks rapidly; once C 2 12.5, the FNR aligns with the target (red line), and the constraint is consistently satisfied.
oo). With a
These results demonstrate that obstacle to satisfying the chosen constraints for RaCO-DP the bias from clipping and nor the DP noise. Therefore, we stress that tuning C' is an important aspect when applying RaCO-DP in practice.
E.7 DEEP LEARNING EXPERIMENT
We further evaluate RaCO-DP on deep neural networks by training a ResNet16 He al. (2016)
on CelebA under demographic parity constraints, Following common practice in private training Berrada al. (023), replace batch normalization with group normalization (16 groups) avoid reliance on batch statistics, which interact poorly with privacy constraints due to their reliance on batch-level statistics. Models are trained with a batch size of 256. For non-private baselines, we use learning rate of 0.01, while private models require a larger learning rate (0.2) to compensate for the effect of gradient clipping. For & and ε 9, we add Gaussian noise with a = 1.2 and 0.6, respectively. and set the Laplace noise scale b = 0.5. All results averaged over five random seeds. Figure Figure [a reports accuracy under varying disparity thresholds y E 0.1, 0.075, 0.053. highlighting that RaCO-DP maintains strong utility even under striet fairness and privacy requirements.
E.8 EXPERIMENTS ON LOW EPSILON
In figure Figure 9 we employ RaCO-DP to train a logis- tie regression on Adult with demographic parity con- straints at three restrictive privacy-budget settings: & E (0.01, 0.1, 1}. From utility perspective, tightening the privacy budget from 6 = to ε = 0.1 results in only a modest decrease in accuracy of approximately three per- centage points (Ne 85% to zs 82%). Even under stringent budget of = 0.01, the most accurate model maintains an accuracy of about 80%. From a fairness perspective, smaller budgets lead to wider 95% confidence intervals (CIs) for the disparity metric 7; the CI width increases from roughly 0.05 at = 0.1 to about 0.10 at E = 0.01, with mean y 0.17. The corresponding mean disparity gap between ε = 0.01 and = 0.1 can be as large as 0.15 (15%), reflecting the greater noise introduced at lower e. Overall, DP-RaCO exhibits graceful
Misclussffiatton Ervor
Privary Level (+)
0.4
==000 0.01
=0.1
0.3
0.2
0.0
0.1
0.2
0.3
Disparity Bound y
Figure 9:
Variance in fairness-uiilin trade-off's at small privacy budgets.
32

---

Published as a conference paper at ICLR 2026
degradation:
while very small budgets (= 0.01) exacerbate the accuracy fairness trade-off, moderate budget (5 0.1) achieves reliable performance with a narrow CI (+= =0.05).
F BROADER IMPACT
An important takeaway from our work that privacy and robustness criteria (such as the absence of performance disparities for underrepresented groups) not inherently at odds with each other. This realization calls into question the practice of broadening the concept of privacy-utility trade-offs to include trade-offs with other robustness criteria. In high-risk decision-making systems that require both privacy and robustness, the responsibility for achieving such robustness falls on the beneficiaries of automated pecision-mmking systems (governments and private institutions), well algorithm designers. These stakeholders must take care not to mistakenly attribute a lack of robustness to privacy mitigations, or a lack of privacy robustness requirements.
Our work contributes to the existing literature in algorithmic fairness and privacy, and as such, adopts and further formalizes their computational interpretations of these human values. important to note that these interpretations, while useful in the contexts we have explored, are by means collectively exhaustive. Specifically, the use of our algorithm does not ensure privacy in the broad sense, but rather in the limited sense of differential privacy, which protects the privacy of individuals whose data has been collected for training. Given technical complexities of correctly implementing differential privacy, inappropriate tuning of model parameters lead to a false sense of privacy and, worse, may exploited for privacy-washing washing by malicious actors in charge.
outside its intended context can
33


Reviews:
[{"review_id": "uVH51xzZBr", "reviewer": "Reviewer_MESD", "summary": "This work gives an algorithm for differentially private optimization in the setting of machine learning where we have \"rate constraints,\" i.e., constraints that limit how the model predicts across different parts of the dataset. The main application is to fairness. As I understand it, no prior work considers this exact problem even non-privately, but we can compare with prior DP algorithms for important special instances. (The rate constraints here are adapted to multiclass classification and, unlike Cotter et al. (2019), use a differentiable notion of rate.)\n\nAlgorithmically, we solve a Lagrangian formulation of this problem with a DP version of stochastic gradient descent-ascent: we privately update the primal parameters, then the dual parameters, then we project them back to the feasible space. Before this, for each step, we run a private histogram to estimate the current model's predictions on the current mini-batch.\n\nWe get a theoretical convergence analysis (which seems to have to deal with several nontrivial obstacles) and experiments, where the proposed approach appears to essentially dominate prior work.", "questions": "How are the rate constraints provided to Algorithm 1? Does the global partition depend on the rate constraints, or is it also supplied to the algorithm?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This seems like a very solid contribution. There's been a lot of work on DP optimization in both minmax and fairness settings, and this seems like it contains technical ideas that will be useful elsewhere. The algorithm will surely be an experimental baseline for future work.", "weaknesses": "I feel the presentation of the paper could be improved. Here are some areas I had particular difficulty:\n1. The rate constraints here adapt the Cotter et al. (2019b) definition by extending it to multiclass, but also working with soft decisions. The latter is a major point in their paper and may be an important distinction in the context of fairness [see 1]. \n1. We also consider constraints that may look at overlapping parts of the dataset. I am still somewhat confused about this: am I given the rate constraints and then have to come up with the dataset partition myself? Does the manner in which I do this depend on the data?\n1. Section 3: the example partition is Hispanic, Black, or Caucasian. This is actively confusing, since often \"Hispanic\" is treated as an ethnicity distinct from a race, so for example on the US Census one can be \"Hispanic Black\" or \"Non-Hispanic White.\"\n1. Section 4: what's the obstacle in obtaining the per-sample decomposition? What non-trivial operation is happening here?\n\nThese were the main issues I ran into when reading the paper. They caused a fair bit of difficulty in forming my evaluation of it.\n\n\n[1] Canetti, Ran, et al. \"From soft classifiers to hard decisions: How fair can we be?.\" Proceedings of the conference on fairness, accountability, and transparency. 2019.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "L1lXhKRU0m", "reviewer": "Reviewer_AG8J", "summary": "This paper proposes RaCO-DP, a DP variant of the stochastic gradient descent–ascent algorithm for solving the Lagrangian formulation of rate-constrained problems. This paper proposes an algorithm that enforces fairness and differential privacy simultaneously. They formulate “fairness” as a rate-constrained problem in empirical risk minimization. However, previous formulations apply only to binary classification tasks. \n\nThis paper proposes generalized rate constraints that can handle multi-class classification. For privately solving the ERM with generalized rate constraints, they propose RaCO-DP, a DP variant of the stochastic gradient descent–ascent algorithm. Specifically, they leverage the fact that the rate-constraint objective can be expressed as a function of a histogram of model predictions, and that this histogram is easy to privatize (its sensitivity is 1) with the Laplace mechanism. RaCO-DP first computes a private histogram of the predictions, and then combines it with DP-SGD–style updates in the descent and ascent steps. \n\nUnder standard assumptions in non-convex optimization, they prove that their algorithm achieves convergence to an approximate stationary point with a rate comparable to those in related minimization settings. They also provide experimental results showing that their algorithm achieves better fairness–accuracy trade-offs than previous algorithms across different privacy levels.", "questions": "The convergence guarantee Theorem 5.2 does not depend on the rate constraint parameters. What are the dependencies? \n\nHow valid is the bounded dual space assumption (section 5)? Since a compact $\\Lambda$ caps penalties, it can induce violations to the rate constraints.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper is clearly written and easy to read.\n* It has significance as it generalizes prior fairness constraints that previously limited to the binary classification setting to the multiclass setting. It also proposes a novel DP algorithm that leverages a private histogram; empirically, the method achieves a better privacy–fairness trade-off, and the paper also provides a theoretical convergence analysis for the algorithm.\n* It provides experimental investigations and ablations over different hyperparameter choices and privacy budgets. It also shows that it is computationally more efficient than prior work, with only ~2× per-step overhead compared with DP-SGD (and large speedups over DP-FERMI).", "weaknesses": "The method’s performance can degrade substantially when the smallest subgroup is tiny, because DP noise makes its histogram estimates inaccurate. The paper offers only limited discussion of this case.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "M1ygrES5RX", "reviewer": "Reviewer_vscK", "summary": "RaCO-DP is a novel framework for optimizing machine learning models under rate constraints with differential privacy, DP variant of SGDA.", "questions": "Improve presentation of results adding details regarding which datasets RaCO-DP exactly achieved a new SOTA on.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "- Formal convergence analysis of RaCO-DP,\n- New SOTA claimed to be achieved on standard benchmarks for tabular datasets: CelebA, Parkinsons, ACSEmployment,\n- Scales to multiple sensitive groups (tested up to 18),\n- Scales beyond convex models to deep learning model (ResNet16 on CelebA),\n- Stronger privacy guarantees than former approaches,\n- Allows to specify directly maximum disparity.", "weaknesses": "- Results section is not clear, which exactly datasets displayed results achieving SOTA?\n- Authors didn't run the experiments for SOTA but compared with published data from Lowy et al.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iY3BdavFZf", "reviewer": "Reviewer_sEj5", "summary": "This paper tackles the challenge of training machine learning models under rate-based constraints (e.g. group fairness metrics like demographic parity, equalized odds) while ensuring differential privacy (DP). The authors propose RaCO-DP, a differentially private stochastic gradient descent-ascent method for solving the Lagrangian of constrained optimization problems that involve group-level rate constraints. A key innovation is the use of generalized rate constraints, which unify various constraint types as computations on subgroup histograms. By privately estimating these subgroup statistics at each training step (with calibrated noise), the method enforces constraints with minimal extra privacy cost. The paper provides a rigorous theoretical analysis, proving that RaCO-DP converges to an approximate stationary point even for non-convex problems. Empirically, the approach is evaluated on multiple fairness-sensitive benchmarks (enforcing demographic parity, false negative rate limits, and equalized odds) across tabular datasets (Adult, Credit, Parkinsons, ACSEmployment) and a deep learning task (CelebA with ResNet16). Results show that RaCO-DP achieves state-of-the-art trade-offs between accuracy, fairness, and privacy – Pareto-dominating prior private fairness methods under the same privacy budgets. Notably, the method scales to scenarios with many subgroups (18 in one experiment) and maintains high utility even under stringent privacy (e.g. $\\varepsilon=1$) on a deep neural network. In summary, this work introduces the first general DP framework for rate-constrained learning, demonstrating strong theoretical guarantees and improved privacy–utility–fairness performance in fair ML applications.", "questions": "1. RaCO-DP enforces constraints up to a slack $\\gamma$. In practice, if a user needs to guarantee a strict constraint ($\\gamma$ very close to 0), what is the advised approach? The discussion in the paper suggests using hard constraints in the dual update breaks theory and gives limited benefit. Could the authors clarify the observed impact of using hard constraints: did it ever significantly improve fairness or was it truly negligible? Also, in scenarios like requiring zero disparity or error ($\\gamma=0$), does RaCO-DP struggle due to noise? It would help to know if there’s an inherent limit to how tight a constraint can be made under DP noise before performance collapses (as hinted by the FNR=0 case).\n\n2. The paper notes that the gradient clipping norm $C$ is critical and can affect the feasibility of constraints. How did you select the clipping norm in experiments, and how sensitive are the results to this choice? Is there a heuristic or adaptive strategy you can recommend for choosing $C$ to balance privacy (noise) and constraint satisfaction? Understanding this would help practitioners avoid the issue of failing to meet a constraint due to overly aggressive clipping.\n\n3. The method privately computes a histogram of subgroup counts per batch. How does the privacy budget consumption scale with the number of groups or constraints? For instance, in the ACSEmployment case with 18 subgroups, was there a noticeable increase in noise or decrease in accuracy relative to cases with fewer groups? Some discussion on scaling to a larger number of constraints (or larger partitions $Q$) under DP would be insightful. For example, does each additional subgroup simply incur a small constant cost, or do variance and utility trade-offs worsen significantly?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Novelty and Generality: The paper bridges a significant gap by presenting the first general DP optimization framework for arbitrary rate constraints, beyond prior work that focused almost exclusively on fairness constraints. This general formulation means the method could apply to a wide range of constrained ML tasks (fairness, robustness, cost-sensitive learning) under DP, marking a clear advancement in differentially private optimization.\n\n - Algorithmic Innovation: The proposed RaCO-DP algorithm (DP-SGDA) cleverly overcomes the core challenge that rate-based constraints depend on global group statistics (violating per-sample DP assumptions). The solution – privately computing subgroup histograms each mini-batch – ensures constraints can be evaluated and optimized without leaking individual data, at a privacy cost equivalent to a histogram query per step. This design exploits the linear structure of the dual (Lagrange multiplier) updates to contain noise growth. It’s an elegant extension of DP-SGD to constrained problems, and the authors describe it clearly with a unified “generalized rate constraint” formulation and examples.\n\n - Theoretical Rigor: The paper provides a solid theoretical foundation. The authors prove convergence of RaCO-DP to an approximate stationary point even for non-convex objectives. The analysis is non-trivial – it accounts for the bias introduced by noisy gradient estimates and leverages the linear structure of the constraints to improve convergence speed. Such theoretical guarantees (with formal proofs in the appendix) lend credibility to the approach and are a notable strength, as prior DP-fairness works often lacked convergence analysis.\n\n - Empirical Performance: The method shows excellent empirical results on multiple benchmarks. Across standard tabular datasets, RaCO-DP consistently achieves higher accuracy for the same fairness level (or lower disparity for the same accuracy) compared to prior approaches like DP-FERMI. In other words, it Pareto-dominates the previous state-of-the-art in the accuracy–fairness–privacy trade-off. For example, on a deep learning task (CelebA, ResNet16), RaCO-DP reaches ~90% accuracy with only a 10% demographic parity gap under strong privacy ($\\varepsilon=1$), which is very close to the non-private model’s 95% accuracy. These are impressive results, demonstrating that the privacy cost of fairness constraints can be kept low.", "weaknesses": "- Soft Constraint Enforcement: RaCO-DP uses a Lagrangian (dual ascent) approach, effectively treating constraints in a soft manner during training. While this is standard in constrained optimization, it means the model might violate constraints transiently or converge to a point that satisfies them only approximately (within the allowed slack $\\gamma$). The authors themselves discuss that using “hard” constraint enforcement (always projecting onto the constraint set) would break their theoretical guarantees, and empirically gave only limited gains. This is a minor weakness in the sense that the final solutions do seem to meet the constraints to the desired degree, but strictly enforcing constraints at all times isn’t supported by the core algorithm. In scenarios where absolutely no constraint violation can be tolerated, additional measures might be needed (at the cost of privacy or convergence guarantees).\n\n - Hyperparameter Sensitivity (Clipping): The approach inherits the need for per-sample gradient clipping from DP-SGD, which can introduce bias. In constrained optimization, an improperly tuned clipping norm can even prevent satisfying the constraints. The authors note that clipping can push the solution outside the feasible set, making the choice of clip norm “a critical hyperparameter”. In practice, this likely requires careful tuning or expert knowledge to get right – a potential drawback for ease of use. The paper does illustrate this issue (showing that overly small clip norms fail a strict FNR=0 constraint) and acknowledges it as a general DP limitation, but it remains a practical challenge.\n\n - Scope of Experiments: While the method is formulated generally, the empirical evaluation is focused primarily on group fairness scenarios. All reported experiments enforce fairness-related constraints; other applications (like robust optimization or cost-sensitive learning mentioned in the motivation) are not demonstrated. This leaves a gap in showing the framework’s generality in practice. For example, it would strengthen the paper to see at least one non-fairness use-case or a discussion of how the method would handle a different type of rate constraint. As is, the results convincingly cover fairness, but the general claim is not fully backed by experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)