Private Rate-Constrained Optimization with Applications to Fair Learning

• URL: http://arxiv.org/abs/2505.22703v1
• Date: Wed, 28 May 2025 17:55:01 GMT
• Title: Private Rate-Constrained Optimization with Applications to Fair Learning
• Authors: Mohammad Yaghini, Tudor Cebere, Michael Menart, Aurélien Bellet, Nicolas Papernot,
• Abstract summary: We study constrained problems under differential privacy (DP)<n>We develop RaCO-DP, a variant of the Gradient Descent-Ascent (SGDA) algorithm which solves the Lagrangian formulation of rate constraint problems.
• Score: 39.172158806012966
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Many problems in trustworthy ML can be formulated as minimization of the model error under constraints on the prediction rates of the model for suitably-chosen marginals, including most group fairness constraints (demographic parity, equality of odds, etc.). In this work, we study such constrained minimization problems under differential privacy (DP). Standard DP optimization techniques like DP-SGD rely on the loss function's decomposability into per-sample contributions. However, rate constraints introduce inter-sample dependencies, violating the decomposability requirement. To address this, we develop RaCO-DP, a DP variant of the Stochastic Gradient Descent-Ascent (SGDA) algorithm which solves the Lagrangian formulation of rate constraint problems. We demonstrate that the additional privacy cost of incorporating these constraints reduces to privately estimating a histogram over the mini-batch at each optimization step. We prove the convergence of our algorithm through a novel analysis of SGDA that leverages the linear structure of the dual parameter. Finally, empirical results on learning under group fairness constraints demonstrate that our method Pareto-dominates existing private learning approaches in fairness-utility trade-offs.

Related papers

• Statistical Inference for Conditional Group Distributionally Robust Optimization with Cross-Entropy Loss [9.054486124506521]
  We study multi-source unsupervised domain adaptation, where labeled data are drawn from multiple source domains and only unlabeled data from a target domain.<n>We propose a novel Conditional Conditional Optimization (CG-DRO) framework that learns a classifier by minimizing the worst-case cross-entropy loss over the convex combinations of the conditional outcome distributions from the sources.<n>We establish fast statistical convergence rates for the estimator by constructing two surrogate minimax optimization problems that serve as theoretical bridges.
  arXiv  Detail & Related papers  (2025-07-14T04:21:23Z)
• Locally Private Nonparametric Contextual Multi-armed Bandits [10.579415536953132]
  We address the challenge of nonparametric contextual multi-armed bandits (MAB) under local differential privacy (LDP)<n>We develop a uniform-confidence-bound-type estimator, showing its minimax optimality supported by a matching minimax lower bound.
  arXiv  Detail & Related papers  (2025-03-11T07:00:57Z)
• The Cost of Shuffling in Private Gradient Based Optimization [40.31928071333575]
  We show that data shuffling results in worse empirical excess risk for textitDP-ShuffleG compared to DP-SGD.<n>We propose textitInterleaved-ShuffleG, a hybrid approach that integrates public data samples in private optimization.
  arXiv  Detail & Related papers  (2025-02-05T22:30:00Z)
• Convex Approximation of Two-Layer ReLU Networks for Hidden State Differential Privacy [4.887917220146243]
  We show that it is possible to privately train convex problems with privacy-utility trade-offs comparable to those of 2-layer ReLU networks trained with DP gradient descent (DP-SGD)<n>This enables the use of existing hidden state privacy analyses and provides accurate privacy bounds also for the noisy cyclic mini-batch gradient descent (NoisyCGD)<n> Empirical results on benchmark classification tasks demonstrate that NoisyCGD can achieve privacy-utility trade-offs on par with DP-SGD applied to 2-layer ReLU networks.
  arXiv  Detail & Related papers  (2024-07-05T22:43:32Z)
• Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learning [132.7040981721302]
  We study the Constrained Convex Decision Process (MDP), where the goal is to minimize a convex functional of the visitation measure. Design algorithms for a constrained convex MDP faces several challenges, including handling the large state space.
  arXiv  Detail & Related papers  (2024-02-16T16:35:18Z)
• Model-Based Epistemic Variance of Values for Risk-Aware Policy Optimization [59.758009422067]
  We consider the problem of quantifying uncertainty over expected cumulative rewards in model-based reinforcement learning. We propose a new uncertainty Bellman equation (UBE) whose solution converges to the true posterior variance over values. We introduce a general-purpose policy optimization algorithm, Q-Uncertainty Soft Actor-Critic (QU-SAC) that can be applied for either risk-seeking or risk-averse policy optimization.
  arXiv  Detail & Related papers  (2023-12-07T15:55:58Z)
• Online Bootstrap Inference with Nonconvex Stochastic Gradient Descent Estimator [0.0]
  In this paper, we investigate the theoretical properties of gradient descent (SGD) for statistical inference in the context of convex problems. We propose two coferential procedures which may contain multiple error minima.
  arXiv  Detail & Related papers  (2023-06-03T22:08:10Z)
• Stochastic Methods for AUC Optimization subject to AUC-based Fairness Constraints [51.12047280149546]
  A direct approach for obtaining a fair predictive model is to train the model through optimizing its prediction performance subject to fairness constraints. We formulate the training problem of a fairness-aware machine learning model as an AUC optimization problem subject to a class of AUC-based fairness constraints. We demonstrate the effectiveness of our approach on real-world data under different fairness metrics.
  arXiv  Detail & Related papers  (2022-12-23T22:29:08Z)
• Quantization for decentralized learning under subspace constraints [61.59416703323886]
  We consider decentralized optimization problems where agents have individual cost functions to minimize subject to subspace constraints. We propose and study an adaptive decentralized strategy where the agents employ differential randomized quantizers to compress their estimates. The analysis shows that, under some general conditions on the quantization noise, the strategy is stable both in terms of mean-square error and average bit rate.
  arXiv  Detail & Related papers  (2022-09-16T09:38:38Z)
• Modeling the Second Player in Distributionally Robust Optimization [90.25995710696425]
  We argue for the use of neural generative models to characterize the worst-case distribution. This approach poses a number of implementation and optimization challenges. We find that the proposed approach yields models that are more robust than comparable baselines.
  arXiv  Detail & Related papers  (2021-03-18T14:26:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.