Technical Summary: Private Rate-Constrained Optimization with Applications to Fair Learning

Problem Statement

Many critical machine learning tasks, ranging from group fairness (e.g., demographic parity, equalized odds) to robust optimization and cost-sensitive learning, can be formulated as constrained minimization problems. These problems require minimizing overall model error subject to rate constraints, which enforce specific conditions on prediction rates across subpopulations (e.g., ensuring similar positive outcome rates across gender groups).

A significant challenge arises when applying Differential Privacy (DP) to these problems. Standard DP optimization techniques, such as DP-SGD, rely on objectives that decompose over individual examples, allowing for per-example gradient clipping and noise addition. However, rate constraints depend on aggregate statistics across groups, creating inter-sample dependencies that violate this decomposability. Existing private learning methods have largely focused on specific fairness constraints or rely on proxy objectives that do not extend to the broader family of rate constraints found in practice. There is a lack of a general DP framework capable of handling arbitrary rate-constrained problems while maintaining formal privacy guarantees.

Methodology: RaCO-DP

To address the incompatibility between rate constraints and standard DP-SGD, the authors propose RaCO-DP, a differentially private variant of the Stochastic Gradient Descent-Ascent (SGDA) algorithm. The method solves the Lagrangian formulation of the rate-constrained problem.

Key Technical Components

1. Generalized Rate Constraints:
   The authors introduce a generalized form of rate constraints applicable to multi-class settings. These constraints are defined based on a "global partition" of the dataset ($D_1, \dots, D_Q$) and allow each constraint to operate on any recombination of these sub-datasets. This structure enables the efficient private estimation of necessary statistics.

2. Private Histogram Computation:
   The core innovation lies in computing a private histogram at each training step. For a mini-batch $B^{(t)}$, the algorithm calculates soft prediction rates for each class $k$ within each partition $D_q$.

   • Instead of computing constraints directly on the raw data, the algorithm aggregates softmax predictions into a histogram $H^{(t)}$.
   • To ensure privacy, Laplace noise is added to this histogram. Since the $\ell_1$-sensitivity of the histogram is 1 (each sample belongs to exactly one partition and its softmax probabilities sum to 1), adding Laplace noise provides $\epsilon$-DP for the histogram itself.

3. Primal and Dual Updates via Post-Processing:

   • Primal Update (Model Parameters $\theta$): The algorithm derives per-sample gradients for the Lagrangian by post-processing the private histogram $\hat{H}^{(t)}$. This allows the regularizer term (derived from constraints) to be decomposed into per-sample terms, enabling standard DP-SGD techniques: clipping per-sample gradients, averaging, and adding Gaussian noise.
   • Dual Update (Lagrange Multipliers $\lambda$): The constraint values required for the dual ascent are computed by post-processing the same private histogram $\hat{H}^{(t)}$. Because the histogram is already privatized, the post-processing property of DP ensures that evaluating the constraints and updating $\lambda$ incurs no additional privacy cost.

4. Convergence Analysis:
   The paper provides a novel convergence analysis for SGDA in the presence of biased gradient estimates and privacy noise.

   • The analysis leverages the linear structure of the dual parameter to achieve faster convergence rates compared to previous non-convex min-max analyses.
   • It proves that RaCO-DP converges to an approximate stationary point even for non-convex optimization problems, with error bounds dependent on the privacy budget, dataset size, and noise scales.

Key Contributions

• General Framework: Introduction of the first general DP framework for arbitrary rate-constrained problems, moving beyond the narrow scope of fairness-specific methods.
• Algorithmic Innovation: Development of RaCO-DP, which utilizes private histograms to decouple the privacy cost of constraint evaluation from the gradient computation, avoiding the need for multiple private queries.
• Theoretical Guarantees: A formal convergence proof for SGDA under DP with biased gradients, demonstrating convergence to an approximate stationary point for non-convex-linear losses.
• Scalability: Demonstration that the method scales to deep neural networks (ResNet16) and handles a large number of simultaneous constraints (up to 18 subgroup constraints).

Experimental Results

The authors evaluate RaCO-DP on four standard benchmarks (Adult, Credit-Card, Parkinsons, CelebA) and various constraint types (Demographic Parity, Equalized Odds, False Negative Rate).

• Utility-Fairness-Privacy Trade-off: RaCO-DP consistently Pareto-dominates existing private learning approaches (e.g., DP-FERMI, Tran et al., Jagielski et al.). It achieves higher accuracy at any fixed fairness disparity compared to baselines under the same privacy budgets.
• Deep Learning Performance: On the CelebA dataset with a ResNet16 model, RaCO-DP achieves 90% accuracy with only a 10% demographic disparity gap at $\epsilon=1$, approaching the performance of non-private models (95% accuracy).
• Constraint Satisfaction: Unlike prior methods that rely on indirect hyperparameter tuning, RaCO-DP allows practitioners to directly specify the maximum disparity ($\gamma$). The method consistently achieves these pre-specified constraint values.
• Computational Efficiency: RaCO-DP is approximately three orders of magnitude faster than DP-FERMI on tabular data, as it avoids the heavy computational overhead of the proxy objective used in prior work.
• Low Privacy Budgets: The method exhibits graceful degradation; even at stringent privacy budgets ($\epsilon=0.01$), it maintains reasonable accuracy (approx. 80%) and satisfies constraints, though with wider variance in disparity metrics.

Significance and Claims

The paper claims that RaCO-DP bridges a critical gap in trustworthy machine learning by enabling private optimization for a broad class of rate-constrained problems, including but not limited to fairness.

• Redefining Trade-offs: The results suggest that the privacy-fairness trade-off may be less significant than previously believed. By using an appropriate algorithmic design (private histograms and Lagrangian formulation), it is possible to achieve strong performance in utility, privacy, and constraint satisfaction simultaneously.
• Direct Control: The framework offers practitioners a more reliable and direct method for enforcing constraints compared to indirect penalization-based methods, allowing for explicit specification of fairness or safety limits.
• Broader Applicability: By generalizing beyond binary classification and specific fairness metrics, the approach opens the door to private learning in medical settings (e.g., limiting false negative rates) and other domains where aggregate rate constraints are critical.

The authors conclude that while their work focuses on group fairness and rate constraints, the methodology provides a robust foundation for future exploration into individual fairness and other robustness criteria within the differential privacy framework.