# Differentially Private Worst-group Risk Minimization

arXiv: https://arxiv.org/abs/2402.19437 · HTML: https://mlsanity.com/paper/2402.19437/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 21 references that are in the map.
- First posted on arXiv 29 Feb 2024.

## Builds on (most cited first, 15 of 15)

- [Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalization](https://mlsanity.com/paper/1911.08731/) (2019)
- [Agnostic Federated Learning](https://mlsanity.com/paper/1902.00146/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Practical and Private (Deep) Learning without Sampling or Shuffling](https://mlsanity.com/paper/2103.00039/) (2021)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [High probability generalization bounds for uniformly stable algorithms with nearly optimal rate](https://mlsanity.com/paper/1902.10710/) (2019)
- [On-Demand Sampling: Learning Optimally from Multiple Distributions](https://mlsanity.com/paper/2210.12529/) (2022)
- [Active Sampling for Min-Max Fairness](https://mlsanity.com/paper/2006.06879/) (2020)
- [Generalization Bounds for Stochastic Saddle Point Problems](https://mlsanity.com/paper/2006.02067/) (2020)
- [Minimax Demographic Group Fairness in Federated Learning](https://mlsanity.com/paper/2201.08304/) (2022)
- [Differentially Private SGDA for Minimax Problems](https://mlsanity.com/paper/2201.09046/) (2022)
- [Bring Your Own Algorithm for Optimal Differentially Private Stochastic Minimax Optimization](https://mlsanity.com/paper/2206.00363/) (2022)
- [What is a Good Metric to Study Generalization of Minimax Learners?](https://mlsanity.com/paper/2206.04502/) (2022)
- [Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gap](https://mlsanity.com/paper/2302.12909/) (2023)

## Built on by (most cited first, 9 of 9)

- [Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problems](https://mlsanity.com/paper/2403.02912/) (2024)
- [Improved Rates of Differentially Private Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2503.18317/) (2025)
- [Private Algorithms for Stochastic Saddle Points and Variational Inequalities: Beyond Euclidean Geometry](https://mlsanity.com/paper/2411.05198/) (2024)
- [Differentially Private Non-convex Distributionally Robust Optimization](https://mlsanity.com/paper/2602.16155/) (2026)
- [Enhancing Privacy in Decentralized Min-Max Optimization: A Differentially Private Approach](https://mlsanity.com/paper/2508.07505/) (2025)
- [Finding Differentially Private Second Order Stationary Points in Stochastic Minimax Optimization](https://mlsanity.com/paper/2602.01339/) (2026)
- [Adaptive Sampling and Clipping for Private Worst-Case Group Optimization](https://mlsanity.com/paper/2602.10820/) (2026)
- [The Privacy Price of Tail-Risk Learning: Effective Tail Sample Size in Differentially Private CVaR Optimization](https://mlsanity.com/paper/2605.16219/) (2026)
- [The Privacy-Hallucination Tradeoff in Differentially Private Language Models](https://mlsanity.com/paper/2609.00492/) (2026)

## Abstract (arXiv)

We initiate a systematic study of worst-group risk minimization under (ε, δ)-differential privacy (DP). The goal is to privately find a model that approximately minimizes the maximal risk across p sub-populations (groups) with different distributions, where each group distribution is accessed via a sample oracle. We first present a new algorithm that achieves excess worst-group population risk of tildeO(fracp√dKε + √fracpK), where K is the total number of samples drawn from all groups and d is the problem dimension. Our rate is nearly optimal when each distribution is observed via a fixed-size dataset of size K/p. Our result is based on a new stability-based analysis for the generalization error. In particular, we show that Delta-uniform argument stability implies tildeO(Delta + frac1√n) generalization error w.r.t. the worst-group risk, where n is the number of samples drawn from each sample oracle. Next, we propose an algorithmic framework for worst-group population risk minimization using any DP online convex optimization algorithm as a subroutine. Hence, we give another excess risk bound of tildeOleft( √fracd1/2ε K +√fracpKε2 right). Assuming the typical setting of ε=Theta(1), this bound is more favorable than our first bound in a certain range of p as a function of K and d. Finally, we study differentially private worst-group empirical risk minimization in the offline setting, where each group distribution is observed by a fixed-size dataset. We present a new algorithm with nearly optimal excess risk of tildeO(fracp√dKε).