1 Introduction↩︎

From fair learning [1]–[4] to robust optimization [5], [6] and cost-sensitive learning [6], [7], many Machine Learning (ML) tasks can be formulated as constrained optimization problems. In such problems, the goal is to minimize the model’s overall error subject to rate constraints, which enforce conditions on prediction rates across subsets of the training data. For instance, ensuring fairness in a resume screening system might require similar rates of positive outcomes (e.g., resumes selected for human review) across gender groups, a criterion known as equalized odds [8]. Similarly, in a medical setting, a decision-support system may need to strictly limit its false negative rate, e.g., to reduce the risk of misdiagnosing cancerous tumours as benign.

These learning tasks often require training models on sensitive data, such as employee or patient records in our examples. Publicly releasing these models can expose data owners to privacy attacks [9] and disclose personal data without consent [10]. Without proper safeguards, these risks can harm individuals, undermine trust in AI systems, and discourage data sharing in critical applications like medical research. Despite recent advances, differentially private (DP) constrained optimization has focused almost exclusively on fairness constraints [11]–[15]. Methods tailored to fairness do not extend to the broader family of rate constraints that arise in practice. We bridge this gap with the first general DP framework for arbitrary rate-constrained problems. Our approach expands DP’s reach to previously incompatible applications and pushes the Pareto frontier of utility, privacy, and constraint satisfaction, including fairness, beyond the state of the art.

Differential Privacy (DP) is the standard framework for private data analysis that has been successfully applied to training and releasing unconstrained models with formal privacy guarantees. A key approach is the widely used DP-SGD algorithm [16]–[18], which ensures DP by clipping per-sample gradients and adding calibrated noise to the averaged gradient. This process bounds each data sample’s influence. Incorporating rate constraints presents a challenge, however, because unlike typical training losses, these constraint functions (or their regularizer counterparts) do not readily decompose into per-sample terms. This fundamental incompatibility with per-sample processing makes it difficult to integrate them with standard DP-SGD and its variants. Our key contribution is the introduction of a DP optimization algorithm that overcomes this limitation, enabling private optimization subject to rate constraints.

To address the challenge of privately enforcing rate constraints, we propose generalized rate constraints. Generalized rate constraints allow us to express all rate constraints in a common form based on statistics (i.e., histograms) on disjoint subgroups within the dataset. This common structure is the key to our privacy solution: it allows us to efficiently gather all the necessary information to evaluate these constraints under DP. Beyond its advantages for privacy, our method offers greater flexibility compared to prior work [6] by extending to scenarios with multiple output classes.

With generalized rate constraints at hand, we introduce RaCO-DP, a framework for optimizing machine learning models under rate constraints with differential privacy (DP). RaCO-DP is a differentially private variant of the Stochastic Gradient Descent Ascent (SGDA) algorithm which leverages a Langrangian formulation and generalized rate constraints to overcome the decomposability obstacle. Our core insight exploits the structure provided by these constraints: we can efficiently compute differentially private statistics (e.g., histograms) for these subgroups. By privatizing these statistics at each step, we enable private evaluation of the constraint function, and its per-sample constraint gradients. We provide a formal convergence analysis of RaCO-DP, proving that even for non-convex optimization problems, our method converges to an approximate stationarity point. To achieve this, we introduce a novel approach to analyzing SGDA that accounts for bias in gradient estimates and exploits the linear structure of the dual update to enhance convergence speed.

As a concrete application, we study private learning under various constraints, including demographic parity [19], 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 [15] in accuracy–fairness–privacy trade-offs. We further demonstrate that RaCO-DP scales beyond convex models, achieving strong performance for deep neural networks (ResNet16 [20] on CelebA [21]). We also validate its effectiveness on tasks involving multiple sensitive groups (demographic parity on the ACSEmployment dataset), scaling to 18 subgroup constraints. Additionally, our method offers two advantages over existing approaches explicitly designed for fairness constraints. First, it provides stronger privacy guarantees than prior approaches that only consider the privacy of the sensitive label [11], [13], akin to label privacy [22]. Second, it allows practitioners to directly specify the maximum disparity, unlike previous penalization-based methods, such as [15], which offer only indirect control over the desired fairness level via hyperparameter tuning.

2 Background↩︎

2.1 Differential Privacy↩︎

Differential Privacy (DP) [23] has become the de facto standard in privacy-preserving ML thanks to the robustness of its guarantees, its desirable behaviour under post-processing and composition, and its extensive algorithmic framework. We recall the definition below and refer to [24] for more details. Let \(\mathcal{X},\mathcal{Y}\) be the input and output spaces, respectively. We fix some \(m\in \mathbb{N}\) and denote by \(\mathcal{D}\) the space \((\mathcal{X}\times \mathcal{Y})^m\) of datasets of size \(m\).

In the above definition, \(\delta\in(0,1)\) can be thought of as the failure probability, and \(\varepsilon>0\) the privacy loss; smaller \(\epsilon\) and \(\delta\) correspond to stronger privacy guarantees.

Differentially Private Stochastic Gradient Descent (DP-SGD) [16]–[18] serves as the foundational algorithm in private ML. Given a training dataset \(D\in\mathcal{D}\) and model parameters \(\theta\in\mathbb{R}^d\), DP-SGD aims to privately solve (in the sense of 1) the empirical risk minimization problem \(\min_{\theta\in\mathbb{R}^d} \ell(\theta)\), where \(\ell(\theta)=\frac{1}{|D|}\sum_{x\in D} \ell(\theta;x)\) and \(\ell(\theta,\cdot)\) is a loss function differentiable in \(\theta\). DP-SGD follows the standard SGD update, but guarantees differential privacy by (i) capping each data point’s influence on the gradient through gradient clipping, and (ii) injecting Gaussian noise into the clipped gradients.

Each iteration \(t \in [T]\) of DP-SGD incurs a privacy loss \((\varepsilon_t,\delta_t)\). Privacy composition [23], [25] and privacy accounting [18], [26], [27] are techniques that aggregate these per-step privacy losses into a total privacy guarantee \((\varepsilon, \delta)\) that holds for the entire optimization process.

2.2 Constrained Optimization via Lagrangian↩︎

In this work, we aim to solve constrained empirical risk minimization problems of the form: \[\begin{align} \label{eq:constrained-optimization} \textstyle \min_{\theta\in\mathbb{R}^d} \left\{ \ell(\theta) := \frac{1}{|D|}\sum_{x\in D} \ell(\theta;x) \right\} \quad \text{s.t.} \quad \forall j\in[J], \; \Gamma_j(\theta) \leq \gamma_j. \end{align}\tag{1}\] where \(\Gamma_j: \mathbb{R}^d \mapsto \re^+\) are the constraint functions and \(\gamma \in (\re^+)^{J}\) are slack parameters. We focus on inequality constraints, as equality constraints are generally infeasible under differential privacy [28].

Due to the difficulty of solving 1 directly, we instead solve an equivalent min-max optimization problem with respect to the Lagrangian: \[\begin{align} \textstyle \text{\quad}& \min_{\theta\in\re^d} \max_{\lambda \in \Lambda} \bc{\cL(\theta,\lambda) := \ell(\theta) + R(\theta, \lambda)}, \label{eq:minmax} && \text{where: } R(\theta, \lambda) = \textstyle\sum_{j=1}^{J}\lambda_j (\Gamma_j(\theta) - \gamma_j). \end{align}\tag{2}\] Here, \(\lambda\in \Lambda \subseteq (\re^+)^{J}\) are the Lagrange multipliers, often referred to as the dual parameter, while \(\theta\) 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 [29].

2.3 Rate Constraints↩︎

In this work, we focus on constraints that relate to prediction behavior over subsets of the dataset. Consider a model \(h: \mathcal{X} \times \mathbb{R}^d \mapsto \re^K\) that maps inputs from feature space \(\mathcal{X}\) to real-valued prediction scores over the label set \(\mathcal{Y}=\{1,\dots,K\}\) using parameters \(\theta \in \mathbb{R}^d\). Formally, (hard) prediction rates count the number of points in a dataset \(D\) for which the model predicts a certain label \(k\in\cY\): \(\textstyle P^{\text{hard}}_k(D; \theta) = \frac{1}{|D|} \sum_{x \in D} \mathbb{1}_{[\argmax_{k'\in[K]}\{h(\theta; x)_{k'}\} = k]}.\)

As the indicator function is non-differentiable and thus challenging to optimize, we will use differentiable versions of these constraints. We rely on the tempered softmax function \(\sigma_\tau(z)_k = \frac{\exp(-\tau z_k)}{\sum_{l=1}^K \exp(-\tau z_l)}\), where the temperature parameter \(\tau \in \mathbb{R}^+\) controls the sharpness of the probability distribution. This allows us to define soft prediction rates: \[\textstyle P_k(D ; \theta, \tau) = \frac{1}{|D|} \sum_{x \in D} \sigma_\tau(h(\theta; x))_k, \quad \text{ for } k \in \cY. \label{eq:rate-soft-func-general}\tag{4}\]

Observe that \(\lim_{\tau \rightarrow \infty} P_k(D; \theta,\tau) = P^{\text{hard}}_k(D; \theta)\).

Rate constraints, as defined by [30] and [6] for binary classification (\(\cY = \{0, 1\}\)), are linear combinations of a classifier’s prediction rates across different data partitions: \[\label{eq:rate-cotter} \textstyle\sum_{q \in [Q]} \alpha_q P_1(D_q, \theta) + \beta_q P_0(D_q, \theta) \leq \gamma,\tag{5}\] \(Q>0\), \(\alpha_q,\beta_q\in\mathbb{R}\) are mixing coefficients, \(D_1,...,D_Q\subseteq D\) and \(\gamma\) is 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 a minimum level of precision or recall for both classes [4]. 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.

None

This shared structure is a partition \(\bc{D_1,...,D_Q}\) of the dataset \(D\) for some \(Q>0\), which we refer to as the “global” partition. We then allow each rate constraint to incorporate prediction rates over 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 (e.g., Asian, Black, Caucasian), and local datasets for one of the constraint is {Asian, Non-Asian} where \(\text{Non-\textcolor{teal}{Asian}} = \{\text{Black}, \text{Caucasian}\}\). See 1.

Formally, given this global partition, we assume for each \(j\in [J]\) there exists a family of subsets of \([Q]\), denoted \(\lpar_j \subseteq 2^{[Q]}\), and a weight vector \(\alpha_j\in \re^{|\lpar_j|\cdot K}\), such that the constraint \(\Gamma_j\) can be written in the following form:³ \[\begin{align} &\textstyle\Gamma_j(\theta) = \sum_{I\in \lpar_j} \sum_{k=1}^K \alpha_{j,I,k} P_k(\cup_{i \in I} D_{i}; \theta). \label{eq:rate-soft-general} \end{align}\tag{6}\]

Assuming such a global partition is not restrictive, as the trivial partition \(D_q=x_q\) (with \(Q=|D|\)) can always be used. However, as Section 4 will show, a smaller partition size \(Q\) enables a better privacy-utility trade-off through more effective noise use.

Note that each rate constraint \(\Gamma_j\) is uniquely defined by the subset family \(\lpar_j\) and vector \(\alpha_j\). Both parameters are public, specifying only the constraint’s structure and containing no sensitive data.

Application to fair learning. Group fairness in machine learning aims to 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 [31]. More generally, all common group fairness measures can be formulated as rate constraints [6]. We provide details on formulating other fairness notions in 10.

In practice, probabilities are replaced by empirical rates \(P_k\). With slack \(\gamma\), this gives \[\begin{align} P_k(D[Z=z];\theta)-P_k(D[Z\neq z];\theta)\leq \gamma, \quad \forall z\in\cZ, k\in\cY, \label{eq:const-dem-parity} \end{align}\tag{7}\] leading to \(J=|\cZ|\cdot|\cY|\) constraints of the form 6 . The global partition has size \(Q=|\cZ|\) with elements \(D_z=D[Z=z]\). For the constraint indexed by \((z,y)\in\cZ\times\cY\), we take \(\lpar=(\{z\},[|\cZ|]\setminus z)\) and define \(\alpha_{\{z\},y}=1\), \(\alpha_{\{[|\cZ|]\setminus z\},y}=-1\), with all other components zero.

Objective. With these definitions in place, we can now state our objective: solve problem 2 with generalized rate constraints of the form 6 under DP.

4 RaCO-DP: Private Rate-Constrained Optimization↩︎

We introduce RaCO-DP(2), an algorithm for rate-constrained optimization that extends SGDA (2) to satisfy DP. Each iteration \(t\) of RaCO-DP operates on a mini-batch \(B^{(t)}\) and consists of three key components that we will describe in detail in this section:

1. Private histogram computation: For each class \(k\in[K]\) and part \(q\in[Q]\) of the partition, we privately estimate the sum of model predictions \(\sigma(h(\theta_t; x))_k\) over the points \(x\) in the mini-batch \(B^{(t)}\) that belong to \(D_q\), storing these counts in a histogram \(H^{(t)}\) (4.1).

2. Private primal updates: We derive per-sample gradients for the primal update of SGDA based on post-processing the histogram \(H^{(t)}\). We then clip, average and privatize these gradients using the Gaussian mechanism (4.2).

3. Private dual updates: We compute all constraint values by again post-processing the histogram \(H^{(t)}\), allowing us to perform the dual update at no additional privacy cost (4.3).

4.1 Private Histogram Computation↩︎

Our algorithm’s primal and dual updates compute prediction rates across dataset partition parts \(D_1, \dots, D_Q\) for each class. To track these prediction rates privately, we construct a histogram \(H^{(t)} \in \mathbb{R}^{Q \times K}\) that counts (soft) model predictions for each combination of part \(q\) and class \(k\). For a given model parameter \(\theta\), each sample \(x_i\) in the mini-batch \(B^{(t)}\) belongs to exactly one part \(D_q\) of the partition but can influence the counts of all \(K\) classes through the softmax probabilities \(\sigma(h(\theta; x))_k\). This non-private histogram is constructed by accumulating these softmax vectors:

\[\textstyle H^{(t)}_{q,k} = \sum_{D_q \cap B^{(t)}} \sigma(h(\theta;x_i))_k.\]

To make this histogram differentially private, we use the Laplace mechanism [23]. The \(\ell_1\) sensitivity of \(H^{(t)}\) is \(1\), as each sample belongs to one element of the global partition and its softmax predictions sum to \(1\) across classes. Thus, we achieve \(\varepsilon\)-DP by adding Laplace noise to each element: \[\hat{H}^{(t)}_{q,k} = H^{(t)}_{q,k} + \operatorname{Lap}(1/\varepsilon), \quad \forall q \in [Q], k \in \mathcal{Y}.\]

In the following sections, we will see that \(\hat{H}^{(t)}\) 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 in RaCO-DP, we decompose the Lagrangian into per-sample terms. While the loss \(\ell(\theta)\) naturally decomposes as in standard DP-SGD, the regularizer \(R\) is more challenging.

Given a mini-batch \(B\), define \(B_{\cap I} = B \cap (\underset{i \in I}{\cup}D_i)\) and recall that \(\lpar_j\) and \(\alpha_j \in \re^{|\lpar_j|\times K}\) denote the family of subsets and weight vector associated with constraint \(\Gamma_j\). The minibatch-level regularizer is, \[\begin{align} R(\theta, \lambda; B) \!=\! \sum_{j = 1}^J \lambda_j \Big(\big(\sum_{I \in \lpar_j} \sum^K_k \alpha_{j,I,k} P_k(B_{\cap I};\theta)\big) \!-\! \gamma_j\Big) \!=\! \sum_{j = 1}^J \lambda_j \Big(\big(\sum_{I \in \lpar_j} \! \sum^K_k \!\sum_{x \in B_{\cap I}} \frac{\alpha_{j,I,k}}{|B_{\cap I}|} \sigma (h(\theta; x)_k\big) \!-\!\gamma_j\Big). \end{align}\]

Note that this may be a biased estimate of \(R(\theta, \lambda)\) due to the normalization term \(|B_{\cap I}|\). We account for this bias in our convergence analysis (5). We would like a per-sample decomposition of \(R(\theta,\lambda;B)\). The main obstacle in such a decomposition are the quantities \(|B_{\cap I}|\), which depend on the entire mini-batch. We overcome this by first noting that \(|B_{\cap I}| = \sum_{i \in I} \sum_k H^{(t)}_{i, k}\), leading to the following per-sample regularizer estimator at point \(x\in D\): \[\begin{align} \label{eq:per-sample-general-adjusted} \textstyle &\hat{R}(\theta, \lambda; H, x) = \sum_{j = 1}^J \! \lambda_j\Big( \big( \! \sum_{I \in \lpar_j} \! \sum_{k_1 \in K} \frac{\alpha_{j, I, k_1} ~ \mathbb{1}_{[x \in B_{\cap I}]}}{\underset{i \in I}{\sum}~\underset{k_2 \in K}{\sum} H^{(t)}_{i, k_2}} \sigma(h( \theta; x))_{k_1} \big) -\gamma_j \Big), \end{align}\tag{8}\] and thus the overall per-sample gradient is given by, \[\label{eq:per-sample-gradient-general} \textstyle \frac{\nabla_\theta \ell(\theta;x)}{r|D|} + \sum_{j = 1}^J \sum_{I \in \lpar_j} \! \sum_{k_1 \in [K]} \!\frac{\lambda_j ~ \alpha_{j, I, k_1} ~ \mathbb{1}_{[x \in B_{\cap I}]}}{\underset{i \in I}{\sum}~\underset{k_2 \in [K]}{\sum} H^{(t)}_{i, k_2}}\nabla_\theta [\sigma(h( \theta; x))_{k_1}].\tag{9}\] Then, since \(H\) depends on the mini-batch \(B\), we use instead its differentially private version \(\hat{H}\). Note that the normalizing term \(\frac{1}{r|D|}\) is necessary to correctly implement clipping in Line [line:clipping] of Algorithm 2.

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 \(\Gamma_j\) and corresponding slack parameter \(\gamma_j\), the gradient of the Lagrangian w.r.t \(\lambda\) is: \[\nabla_\lambda \mathcal{L}(\theta^{(t)},\lambda^{(t)})_j = \Gamma_j(\theta^{(t)}; B^{(t)}) - \gamma_j, \label{eq:dual-update-general}\tag{10}\] The dual update in RaCO-DP thus requires evaluating rate constraints on the current mini-batch \(B^{(t)}\), incurring a privacy cost. To avoid this additional cost, we introduce a post-processing function \(\Gamma^\text{post}_j: \mathbb{R}^{Q\times K} \mapsto \mathbb{R}\) that operates directly on the private histogram \(\hat{H}^{(t)}\). This function replaces each sum of model predictions \(\sum_{i\in D_q\cap B^{(t)}} \sigma(h(\theta; x_i))_k\) with the corresponding histogram count \(\hat{H}^{(t)}_{q,k}\): \[\label{eq:gamma-post} \textstyle\Gamma^\text{post}_j(\hat{H}^{(t)}) = \sum_{I \in \lpar_j} \sum_{k_1 \in [K]} \frac{ \alpha_{j, I, k_1} \sum_{i\in I} \hat{H}_{i,k_1}^{(t)}}{\sum_{i \in I} \sum_{k_2 \in [K]} \hat{H}_{i, k_2}^{(t)}}.\tag{11}\] As \(\hat{H}^{(t)}\) is already DP, the post-processing property ensures this step incurs no additional privacy cost.

RaCO-DP’s efficiency relies on a private histogram \(H^{(t)}\) enabling per-sample gradient computation and private constraint evaluation, key to handling rate constraints under DP. The privacy guarantees of Algorithm 2 follow from composing the subsampled Laplace and Gaussian mechanisms over \(T\) steps.

The proof is in Appendix 11. 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, we 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 as \(\maxfunc(\theta) = \max_{\lambda\in\Lambda}\bc{\cL(\theta,\lambda)}\). Ideally, one would want to show that Algorithm 2 approximately minimizes \(\maxfunc\). However, due to the fact that \(\maxfunc\) may be non-convex, finding an approximate minimizer is intractable in general. In fact, because the constraint functions, \(\bc{\Gamma_j}\), may be non-convex in \(\theta\), if \(\Lambda = (\re^+)^{J}\) then even finding a point where \(\Phi\) is finite may be intractable. As such, we must make two standard concessions. First, we will assume \(\Lambda\) is a compact convex set of bounded diameter. Intuitively, this bounds the penalty applied when the constraints are not satisfied. Further, instead of guaranteeing that Algorithm 2 finds an approximate minimizer of \(\Phi\), we will show the algorithm finds an approximate stationary point. We note that stationarity is a standard convergence measure in non-convex optimization, and provide more discussion in Appendix 13.1. Our subsequent analysis in fact provides for a slightly stronger, but more technical, notion of stationarity than we provide here; see Appendix 13.6 for more details.

When the loss is Lipschitz and smooth, SGDA converges to an approximate stationary point of \(\maxfunc\) [35]. Unfortunately, Algorithm 2 may have biased gradients, and the scale of noise present in \(\hat{g}_\theta\) and \(\hat{g}_\lambda\) may vary dramatically depending on \(d\) and \(\lambdadim\). Thus, our main goal in this section is two-fold. First, we aim to formally show that despite using biased gradients, Algorithm 2 provably finds an approximate stationary point. Specifically, when the error in the primal updates (w.r.t. \(\|\cdot\|_2)\) is at most \(\tau_\theta\) and the error in the dual updates is at most \(\tau_\lambda\) (w.r.t. \(\|\cdot\|_\infty)\), we show SGDA on a nonconvex-linear loss finds a stationary point roughly with \(\alpha = O(\frac{\sqrt{1+\tau_\theta}}{T^{1/4}}+\tau_\theta + \sqrt{\tau_\lambda} + \frac{1}{\sqrt{T}})\); see Appendix 13.6. Second, we characterize the impact of the noise in \(\hat{g}_\theta\) and \(\hat{g}_\lambda\) added due to privacy. This involves correctly balancing the number of iterations \(T\) with the scale of noise needed to ensure privacy, which increases with \(T\). This leads to the following result for Algorithm 2 run without clipping.

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 6). Notably, in contrast to previous analyses, this result 1) allows for biased gradients; 2) depends on the \(\ell_\infty\) error in the dual gradient estimate (rather than the \(\ell_2\) error); and 3) achieves faster convergence (in terms of \(T\)) by leveraging the linear structure of the dual. To point (3), our analysis shows SGDA in this setting can converge as fast as \(\frac{1}{T^{1/4}}\) instead of \(\frac{1}{T^{1/6}}\) [35], essentially matching the rate observed in comparable minimization (rather than min-max) settings. See Theorem 6 for this specific result. The next step in proving Theorem 2 is to control the error of the gradient estimates while balancing the noise necessary for privacy. We show that this error scales proportional to \(\tilde{O}\big(\frac{\sqrt{d T}}{n\epsilon} + \frac{1}{\sqrt{n}}\big)\) in the primal and \(\tilde{O}\big(\frac{\sqrt{KT}\log J}{n\epsilon} + \sqrt{\frac{\log J}{n\epsilon}}\big)\) in the dual. We defer the reader to Lemma 4 in Appendix 13 for a more detailed accounting of this error.

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 [36], Credit-Card [37], Parkinsons [38], ACSEmployment [39], CelebA [21]), false negative rate (on Adult, Heart [40]), and equalized odds (on Credit-Card). We benchmark against DP-FERMI [15], [41], and [11], reporting their results from [15] where available. In settings without prior DP work (e.g., FNR constraints, deep networks on CelebA), we use non-private SGDA as a reference. All DP methods use \(\delta=10^{-5}\), with privacy loss tracked via the numerical accountant of [27]. Full implementation and hyperparameter details are in 14.2. For constraint definitions, see 10.

Tabular data. On standard tabular benchmarks, 3 (b) (together with 5, 6, and 7 in 14.3) shows that across multiple datasets (Adult, Credit-Card, 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 to all baselines under the same privacy budgets. Additional ablations for small \(\varepsilon\) values are provided in 14.8.

Neural networks. To demonstrate that RaCO-DP is applicable to large, non-convex models, we train a ResNet16 [20] (6.4M parameters) on CelebA under demographic parity constraints. As shown in 3 (a), RaCO-DP achieves 90% accuracy with only a 10% demographic disparity gap for \(\varepsilon=1\). This result is close to the non-private model’s 95% accuracy, showing that RaCO-DP is a practical tool for implementing fairness constraints in deep learning pipelines without a prohibitive loss in utility. Hyperparameter and training details are in 14.7.

Scaling. To evaluate performance under a large constraint set, we train a logistic regression on ACSEmployment, enforcing demographic parity across 18 groups simultaneously. 3 (c) shows our method achieves a competitive utility–fairness trade-off even under strong privacy (\(\varepsilon=1\)), confirming its effectiveness.

Matching non-private rates. We observe that RaCO-DP nearly matches non-private accuracy sometimes, especially for logistic regression on tasks such as Adult, Credit-Card, and Parkinsons (see  14.3). In these cases, the sample size is large relative to 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 \(\sigma\) (and Laplace parameter \(b\)) small, since the privacy budget is spread across only a handful of steps. These favorable conditions (large datasets, low-dimensional models, and rapid convergence) explain why the privacy gap narrows, consistent with prior observations [42]. Once we employ higher-capacity models like ResNet16 on CelebA (see 3 (a)), the gap widens.

Satisfiability. The results in 4 demonstrate that RaCO-DP consistently achieves the pre-specified constraint values \(\gamma\) 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 \(\tau=1\) 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 [43]. On identical hardware, RaCO-DP trains three orders of magnitude faster than DP-FERMI on Adult (14.5).

Limitations. [44] shows that gradient clipping 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 \(\text{FNR}=0\) constraint in logistic regression on Adult without DP noise (\(\sigma=0\), \(b=\infty\)). As shown in 9 (a) of 14, 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; as shown in 14.4, this modification offers limited utility benefits.

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-offs between these two objectives [28].

Existing work can be grouped into three main categories. A first line of research [41], [45]–[51] examines how privacy mechanisms can inadvertently harm fairness. For instance, [49] characterizes the disparate impact of DP-SGD 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 [11]–[13]. Unlike standard DP, which protects the entire dataset, privacy for sensitive 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 fairness [14], [15]. [14] use DP-SGD without fairness mitigation, finding well-generalized models show no major privacy-fairness trade-off. However, their notion of fairness is error disparity, arguably measuring subpopulation generalization. Our work shows that while mitigation is needed for demographic parity, appropriate algorithm design can surmount the fairness-privacy trade-off. [15] propose a proxy objective for stochastic optimization of group fairness measures. In contrast, RaCO-DP supports a broad range of rate constraints that can be freely combined, without needing a task-specific objective. While its theoretical convergence rate is slower, RaCO-DP offers greater generality, complicating direct comparisons. Notably, [15] presents results for both sensitive attribute DP and standard DP (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 [15], which seeks to satisfy the fairness objective by running an optimization procedure on a proxy objective, our optimization algorithm more directly targets the rate constraint of interest.

Fairness aside, SGDA is well-studied for minimax optimization [29], [35], [52], with [53] proposing its first DP analogue. Private minmax optimization has been heavily studied recently [54]–[58], though work on non-convex losses is limited to [15].

8 Conclusion↩︎

We introduced a 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 fairness constraints, which cannot be formulated as rate constraints.

9 Acknowledgments↩︎

We would like to acknowledge our sponsors, who support our 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 AI2050 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-03206. The work of Tudor Cebere and Aurélien Bellet is supported by grant ANR-20-CE23-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 a Google Fellowship. This work was performed using HPC resources from GENCI–IDRIS (Grant 2023-AD011014018R1).

10 Application to Other Rate Constraints↩︎

10.1 Fairness Constraints↩︎

Fairness in machine learning aims to 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 fairness [31] metrics: demographic parity and equality of odds. All group fairness measures can be formulated as rate-constraints [6], for individual fairness [19] it is easier to bound the per-sample contribution and privatize it with clipping and noising in the style of DP-SGD, thus a rate-constrained solution is not required, hence we focus on group fairness metrics.

In practice, we do not have access to the true probabilities, so it is common to estimate them by empirical prediction rates \(P_k\). Using a slack parameter \(\gamma\), this gives: \[P_k(D[Z=z]; \theta) - P_k(D[Z \neq z]; \theta) \leq \gamma \quad \forall z \in \cZ, \forall k \in \cY\] Demographic parity thus leads to \(J=|\cZ|\cdot|\cY|\) rate constraints of the form specified in Eqn. 6 . The global partition is of size \(Q=|\cZ|\) with elements \(D_z = D[Z=z]\), \(\forall z\in\cZ\), and for the constraint corresponding to elements \(z\in\cZ\) and \(y\in \cY\), we have \(\lpar = \bc{\bc{z},[|\cZ|]\setminus z}\). The associated vector \(\alpha\) has \(\alpha_{\bc{z},y} = 1\) and \(\alpha_{\bc{[|\cZ|]\setminus z},y}=-1\), with the rest of the components set to \(0\).

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 a counter-factual definition of equalized odds: \[\Pr[\hat{Y} = k \mid Y=k', Z = z] = \Pr[Y=k', \hat{Y} = k, Z \neq z], \quad \forall, z \in \cZ, \forall k,k' \in \cY\] 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 3) but we adopt the counter-factual definition.

We observe that the only difference between the equality of odds and demographic parity is the additional conditioning on the ground truth, which we will reflect as the additional predicate \(Y=k'\) in our base rates to define the following constraint: \[P_k(D[Y = k', Z=z]; \theta) - P_k(D[Y=k', Z=z']; \theta) \leq \gamma \quad \forall z \in \cZ, \forall k,k' \in \cY \label{eq:const-equality-of-odds}\tag{12}\] Equality of odds leads to \(J=|\cY|^2 \times |\cZ|\) number of constraints. With regards to implementing Eqn. 6 , we can use a global partition with \(|\cY| \times |\cZ|\) where each element is the subset of \(D\) with some fixed ground truth label \(k\) and class \(z\). The constraint for some \(k\in[K]\) and \(z\in \cZ\) then has \(\cI\) which specifies the local partition \(\bc{D[Y=k,Z=z], D[Y=k,Z\neq z]}\) with the corresponding vector \(\alpha\) having a \(+1\) coefficient corresponding to a prediction rate of \(D[Y=k',Z=z]\).

Many other group fairness constraints exist but they are all reducible to base rate constraints in a similar manner. Note the similarity between Equations 7 and 12 , where the only difference is the additional conditioning on ground truth labels \(Y\) in equality of odds.

10.2 False Negative Rate↩︎

Assuming the constraint is well-defined, FNR leads \(J = \left| \cY \right|\) rate constraints of the form in Eqn. 6 , with the global partition of size \(Q = \left|Y\right|\) with elements \(D_y = D[Y =y], y \in \cY\). For the constraint corresponding to a fixed \(y \in \cY\), we have \(\cI = \{\mathcal{Y} / y\}\) with an associated \(\alpha_{\{\cY / y\}, y} = 1\).

11 Privacy Analysis↩︎

12 Technical Lemmas↩︎

13 Missing Details from Section 5↩︎

13.1 Additional Background on Stationary Point Definition↩︎

For a smooth function \(f:\theta\mapsto \re\), a standard notion of (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 \(f(\theta)= \|\theta\|\), 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 4. In the example where \(f(\theta)=\|\theta\|\), this relaxation allows points which are close to the cusp at \(\theta = \mathbf{0}\), whereas a bound on the gradient norm would allow only the point \(\theta = \mathbf{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 [59]. We elect to present Definition 4 as it requires less background information.

13.2 Proof of Theorem 2↩︎

In this section we will detail the proof of Theorem 2 and provide a more precise theorem statement. Before doing so, we will introduce some important notation.

For any \(I\subseteq [Q]\), let \(D_I = \underset{i \in I}{\cup}D_i\). Given a subset \(B\subset D\), define \(B_{\cap I} = B \cap (\underset{i \in I}{\cup}D_i)\) and recall that \(\lpar_j\) and \(\alpha_j \in \re^{|\lpar_j|\times K}\) denote the corresponding family of susbets of \([Q]\) and weight vector associated with constraint \(\Gamma_j\). Let \(\minsize = \min_{q\in[Q]}\bc{|D_q|}\).

Let \(\|\Lambda\|_1\) be the \(\ell_1\) diameter of \(\Lambda\). Let \(\lip_\ell\) and \(\lip_h\) be the \(\ell_2\) Lipschitz constants w.r.t. \(\theta\) of \(h\) and \(\ell\) respectively. Similarly, let \(\smooth_\ell\) and \(\smooth_h\) be the corresponding \(\ell_2\)-smoothness constants. We recall the temperature parameter of the softmax is denoted as \(\tau\). Let \(c_1 = \max_{j\in[J]}{\|\alpha_j\|}\). Note that many rate constraint only compare two prediction rates, and so \(c_1\) is typically at most \(2\). Define \(\mormaxfunc(\theta) = \min_{\theta'}\bc{\Phi(\theta') + \smooth\|\theta-\theta'\|^2}\) and \(\mornot = \mormaxfunc(\theta_0) - \min_\theta \bc{\mormaxfunc(\theta)}\) and \(\lossnot = \cL(\theta_0,\lambda_0) - \min_{\lambda,\theta}\bc{\cL(\lambda,\theta)}\) (see Section 13.6 for more details on these quantities). We can now present the more complete version of convergence result.

Proving this statement will involve several major steps. First, in Section 13.4 we derive the necessary noise levels needed to ensure that Algorithm 2 is private. Second, in Section 13.5 we bound the error in the gradients at each time step. Next, in Section 13.6 we give a general convergence rate for SGDA under the condition that the gradients have bounded error. Finally, we derive the overall Lipschitz and smoothness constants of \(\cL\) based on the base smoothness and Lipschitz constants in Section 13.7. These results are then combined in Section 13.3 to obtain the final result.

In one final remark, we note the following fact will be used in several places.

13.3 Proof of Theorem 4↩︎

With the previously established results, we can now verify a setting of parameters which proves the theorem statement. Specifically, we set, \[\begin{align} T = \min\bc{\br{\frac{n\epsilon}{\sqrt{d}}}^{4/3}, \frac{n\epsilon}{K}}, && \sigma = \frac{\lip\sqrt{T}\log(T/\delta)}{n\epsilon}, && b = \frac{r\sqrt{T\log(T/\delta)}}{\epsilon}. \end{align}\] Note that by Theorem 5, this ensures that Algorithm 2 is \((\epsilon,\delta)\)-DP so long as \(r \geq \frac{1}{\sqrt{T}}\).

Using Lemma 4 can now instantiate Theorem 6. For \(\tau_\theta\) we have, \[\begin{align} \tau_\lambda &= O\br{\frac{c_1 K b \log(J K \minsize/\rho)}{r \minsize} + c_1 \sqrt{\frac{\log\left(\frac{J K \minsize}{\rho}\right)}{r\minsize}}} \\ &= O\br{\frac{c_1 K \sqrt{T} \log(T/\delta) \log(J K \minsize/\rho)}{\minsize\epsilon} + c_1 \sqrt{\frac{\log\left(\frac{J K \minsize}{\rho}\right)}{r\minsize}}}. \\ \end{align}\] Setting \(\tau_\lambda\) as the quantity above, we can write the bound on \(\tau_\theta\) as, \[\begin{align} \tau_\theta &= O\br{\sqrt{d}\sigma \sqrt{\log(4T/\rho)} + \frac{4\lip_\ell\sqrt{\log(4/\rho)}}{\sqrt{r |D|}} + \frac{4\lip_\ell\sqrt{\log(4/\rho)}}{\sqrt{r |D|}} + |\Lambda\|_1 \tau \lip_h \tau_\theta} \\ &= O\br{\lip\br{\frac{\sqrt{dT\log(T/\rho)}\log(T/\delta)}{n\epsilon} + \frac{\sqrt{\log(1/\rho)}}{\sqrt{r |D|}}} + \|\Lambda\|_1 \tau \lip_h \tau_\theta}. \end{align}\] Now, in the non-trivial regime where \(\tau_\theta \leq G\), Theorem 6 implies that for \(r\) large enough, \[\begin{align} \alpha &= O\br{\frac{\br{\mornot\smooth(\lip^2+\thetagraderr^2)}^{1/4}}{T^{1/4}} + \thetagraderr + \sqrt{\beta\rad\lambdagraderr} + \frac{\sqrt{\smooth\lossnot}}{\sqrt{T}} } \\ &= O\Bigg(\br{\br{\mornot\smooth\lip^2}^{1/4} + \sqrt{\smooth\lossnot} + \lip}\bigg(\Big(\frac{\sqrt{d}\log(T/\delta)\sqrt{\log(JK\minsize/\rho)}}{n\epsilon}\Big)^{1/3} \\ &+ \frac{K^{1/4}\sqrt{\beta\|\Lambda\|_1}\sqrt{\log(T/\delta)}(\log(JK\minsize/\rho))^{1/4}}{(n\epsilon)^{1/4}}\bigg)\Bigg). \end{align}\]

13.4 Privacy of Algorithm 2 under Lipschitzness↩︎

13.5 Bounding Gradient Error↩︎

13.6 Convergence of SGDA↩︎

The overall structure of our convergence proof is similar to that of [35], but with several significant modifications. Most significantly, our proof explicitly leverages the linear structure of the dual to improve the convergence rate for our application. This linear structure also allows our analysis to depend on an \(\|\cdot\|_\infty\) bound on the gradient error when \(\Lambda\) has bounded \(\|\cdot\|_1\) diameter. This in contrast to previously existing analysis which depend on the \(\|\cdot\|_2\) 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 [35] in that it accounts for potential bias in the gradient estimates and tracks the disparate impact the scale of noise in \(g_\theta\) and \(g_\lambda\) may have on the convergence rate.

In order to present our proof, we start with some necessary preliminaries. Let \(\maxfunc(\theta)=\max_{\lambda\in\Lambda}\bc{\cL(\theta,\lambda)}\). Let \(\mormaxfunc\) denote the Moreau envelope of \(\maxfunc\) with parameter \(2\beta\). That is, \(\mormaxfunc(\theta) = \min_{\theta'}\bc{\Phi(\theta') + \smooth\|\theta-\theta'\|^2}\). Let \(\Delta^{(t)} = \Phi(\theta^{(t)}) - \cL(\theta^{(t)},\lambda^{(t)})\) for all \(t\in\bc{0,...,T}\). Further, we define \(\lambda^*(\theta) = \argmax_{\lambda\in\Lambda}\bc{\cL(\theta,\lambda)}\). We denote the proximal operator of a function \(f\) as \(\prox_f(\theta) = \argmin_{\theta}\bc{f(\theta')+\frac{1}{2}\|\theta-\theta'\|^2}\). It is known that under the condition that \(f\) is \(\smooth\)-smooth and \(\Lambda\) is bounded, that \(\mormaxfunc\) is differentiable with \(\nabla \mormaxfunc(\theta) = 2\smooth(\theta-\prox_{\maxfunc/[2\smooth]}(\theta))\), and that any point \(\theta\) for which which \(\|\nabla \mormaxfunc(\theta)\|\leq \alpha\) is an \((\alpha,\alpha/[2/\smooth])\)-stationary point with respect to Definition 4; see [35]. Also, under these conditions, \(\maxfunc\) is \(\lip\)-Lipschitz. We defer the reader towards [35] for more details on these statements.

We present the following statement, which gives a convergence rate for Algorithm 2 in terms of the amount of noise added.

We will prove this statement by showing that Algorithm 2 finds a point where the gradient of \(\mormaxfunc\) is small. Note this is sufficient as [35] implies that a point, \(\theta\), for which \(\|\nabla \mormaxfunc(\theta)\| \leq \alpha\) is an \((\alpha,\alpha/[2\smooth])\)-stationary point with respect to Definition 4.

We will break the majority of the proof into three distinct lemmas. The first lemma gives a bound on the decrease in \(\mormaxfunc\).

The next two lemmas pertain to bounding the \(\Delta^{(t)}\) terms.

We can now prove the main theorem statement.

13.7 Regularity Properties of Lagrangian↩︎

We will use the following standard fact about composing Lipschitz and/or smooth functions.

In the following, we assume the predictor \(h\) is \(\lip_h\)-Lipschitz and \(\smooth_h\)-smooth with respect to \(h\), and similarly for \(\ell\) with parameters \(\lip_\ell\) and \(\smooth_\ell\). 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 \(\tau\)-Lipschitz and \(\tau\)-smooth.

Before presenting the proof, we note that \(\lip_\ell\) and \(\smooth_\ell\) could also be further decomposed using the Lipschitz/smoothness constants of \(\ell\) and \(h\) via Lemma 8. 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.

14 Additional Experimental Details↩︎

14.1 Dataset and Pre-Processing Details↩︎

We evaluate RaCO-DP on tabular fairness and privacy benchmark datasets from [15], namely, Adult [36], German Credit Card [60], and Parkinsons [38]. The classification task for Credit Card and Parkinsons is “whether the user will default payment the next month”, and “whether the total UPDRS score of the patient is greater than the median or not,” respectively. For Adult, 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’ [39] to download and process the data for the Alabama (“AL”) state in the US. We choose a “5”-year horizon and choose survey option to be ‘person.’ We adopt the experimental setup of [15] (including classification task, pre-processing, etc.) and report the baselines results directly from the official repository [43].

We also present results on the Heart Disease Health Indicators dataset [40] (21 risk factors).

To prove the scalability of RaCO-DP on neural network, we train a ResNet16 [20] on the CelebA dataset. CelebA (CelebFaces Attributes Dataset) is a large-scale face dataset containing over 200,000 celebrity images, each annotated with 40 attribute labels (e.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 is used with gender as the sensitive attribute.

14.2 Hyperparameter Tuning and Accounting↩︎

Our hyperparameter selection process follows a two-phase approach. In the first phase, we run a hyperparameter search over predefined ranges: Gaussian noise variance \(\sigma \in [3, 6]\), Laplace parameter \(b \in [0.1, 0.5]\), learning rates \(\eta_\theta, \eta_\lambda \in [10^{-4}, 0.1]\), mini-batch size \(B \in [256, 1256]\), and softmax temperature \(\tau \in [1, 10]\). We constrain the dual variables \(\lambda\) to be non-negative by setting the projection set \(\Lambda = (\mathbb{R}^+)^J\). For each configuration, we target a specific constraint value \(\gamma\) 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 20 new models. We report test accuracy and constraint satisfaction for each model based on the checkpoint that achieved the highest validation accuracy while satisfying the constraints on the train set.

Recent work by [61] and [62] 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.

14.3 Regularization–Privacy–Accuracy Trade-offs↩︎

Demographic Parity. In 5, we compare fairness–utility trade-offs of RaCO-DP against baseline methods on logistic regression models trained with demographic parity constraints across the Adult, Credit-Card, and Parkinsons datasets. We evaluate a range of privacy budgets \(\varepsilon \in \{0.5, 1, 2, 9\}\). Consistent with the main results in 6, RaCO-DP significantly narrows the gap to the non-private baseline and Pareto-dominates existing private baselines.

False Negative Rates. 6 illustrates the flexibility of our framework beyond fairness constraints by enforcing limits on false negative rate (FNR, i.e., \(1-\text{recall}\)). Controlling FNR is particularly important in medical settings. For example, on the Heart dataset, XGBoost achieves 90% accuracy but suffers from an FNR of 90%. Non-private SGDA reduces FNR to 58% with 87.5% accuracy, while DP-RaCO nearly matches this trade-off with 60% FNR at the same accuracy (6 (b)). 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 6 (Limitations) and analyzed in 14.6.

Equalized Odds. In 7, we show results on the Credit-Card 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 [15] and not re-run; as reported, both mean and variance remain unchanged across privacy levels \(\varepsilon \in \{0.5, 1, 3, 9\}\).

14.4 Hard vs. Soft constraints↩︎

9 (b) compares soft and hard constraints for the dual update. Notably, the soft constraint (with tuned softmax temperature \(\tau\)) achieves similar performance compared to its hard constraint counterpart (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.

14.5 Compute Performance↩︎

We provide a computational comparison between methods in 2, where we report the mean time of computing an SGD step, compared to a DP-SGD step and a RaCO-DP step on an eight-core CPU machine on Adult and Credit-Card on a batch size of 512. For reference, we also report the mean time of a 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 extra cost over standard DP-SGD is 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 in the worst case. However, in practice, we can compute the gradient only for the active constraints (\(\lambda_{(i)} > 0\)), which can significantly reducing the computational costs.

14.6 Impact of the clipping norm↩︎

Figure 9 (a) shows how the clipping threshold \(C\) affects RaCO-DP when we enforce a pessimistic constraint of \(\text{FNR} <0\) on the Adult dataset, in a non-private setting (\(\sigma = 0,\; b=\infty\)). With a small clipping norm (\(C\le 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 \ge 12.5\), the FNR aligns with the target (red line), and the constraint is consistently satisfied.

These results demonstrate that an obstacle to satisfying the chosen constraints for our RaCO-DP is the bias from clipping and not the DP noise. Therefore, we stress that tuning \(C\) is an important aspect when applying RaCO-DP in practice.

14.7 Deep learning experiment↩︎

We further evaluate RaCO-DP on deep neural networks by training a ResNet16 [20] on CelebA under demographic parity constraints. Following common practice in private training  [14], we replace batch normalization with group normalization (16 groups) to 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 a learning rate of \(0.01\), while private models require a larger learning rate (\(0.2\)) to compensate for the effect of gradient clipping. For \(\varepsilon=1\) and \(\varepsilon=9\), we add Gaussian noise with \(\sigma=1.2\) and \(\sigma=0.6\), respectively, and set the Laplace noise scale \(b=0.5\). All results are averaged over five random seeds. Figure  3 (a) reports accuracy under varying disparity thresholds \(\gamma \in \{1, 0.1, 0.075, 0.05\}\), highlighting that RaCO-DP maintains strong utility even under strict fairness and privacy requirements.

14.8 Experiments on low epsilon↩︎

In figure 10 we employ RaCO-DP to train a logistic regression on Adult with demographic parity constraints at three restrictive privacy-budget settings: \(\varepsilon \in \{ 0.01, 0.1, 1\}\). From a utility perspective, tightening the privacy budget from \(\varepsilon = 1\) to \(\varepsilon = 0.1\) results in only a modest decrease in accuracy of approximately three percentage points (\(\approx 85\%\) to \(\approx 82\%\)). Even under a stringent budget of \(\varepsilon = 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 \(\gamma\): the CI width increases from roughly \(0.05\) at \(\varepsilon = 0.1\) to about \(0.10\) at \(\varepsilon = 0.01\), with a mean \(\gamma \approx 0.17\). The corresponding mean disparity gap between \(\varepsilon = 0.01\) and \(\varepsilon = 0.1\) can be as large as \(0.15\) (\(15\%\)), reflecting the greater noise introduced at lower \(\varepsilon\). Overall, DP-RaCO exhibits graceful degradation: while very small budgets (\(\varepsilon = 0.01\)) exacerbate the accuracy–fairness trade-off, a moderate budget (\(\varepsilon = 0.1\)) achieves reliable performance with a narrow CI (\(\approx \pm 0.05\)).

15 Broader Impact↩︎

An important takeaway from our work is that privacy and robustness criteria (such as the absence of performance disparities for underrepresented groups) are 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 decision-making systems (governments and private institutions), as well as algorithm designers. These stakeholders must take care not to mistakenly attribute a lack of robustness to privacy mitigations, or a lack of privacy to 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. It is important to note that these interpretations, while useful in the contexts we have explored, are by no 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 the technical complexities of correctly implementing differential privacy, inappropriate tuning of model parameters or use outside its intended context can lead to a false sense of privacy—and, worse, may be exploited for privacy-washing by malicious actors in charge.

References↩︎

---

1. Code is available at: https://github.com/cleverhans-lab/dp-raco↩︎

2. Equal contribution↩︎

3. With some abuse of notation, we denote by \(\alpha_{j,I,k}\) the entry of \(\alpha_j\) corresponding to subset \(I\) and label \(k\).↩︎