Research map / Learning theory and algorithms / Sample complexity
Differentially Private Worst-group Risk Minimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies differentially private worst-group risk minimization, giving a stability-based minimax phased-ERM algorithm, a DP online-convex-optimization framework, and a private multiplicative-reweighting method for the offline empirical setting.
Problem
Privately finding a model that minimizes the maximum population risk across p groups with different distributions, accessed via sample oracles, under (epsilon, delta)-DP.
Approach
Shows that Delta-uniform argument stability of regularized minimax solutions yields O~(Delta + 1/sqrt(n)) worst-group generalization error, and uses this with a Gaussian-noised phased-ERM scheme to get near-optimal private excess worst-group risk; also reduces the problem to a zero-sum game solved by any DP-OCO algorithm plus an EXP3-style Laplace-privatized group player.
Key results
- Minimax Phased ERM achieves excess worst-group population risk O~(sqrt(p/K) + p sqrt(d)/(K eps)).
- DP-OCO framework gives O~(sqrt(sqrt(d)/(eps K)) + sqrt(p/(K eps^2))) excess risk.
- Offline Noisy-SGD-MGR achieves nearly optimal excess empirical worst-group risk O~(p sqrt(d)/(K eps)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Minimax Phased ERM for worst-group population risk minimization under differential privacy | Worst-group population risk minimization · Sample-oracle setting | excess worst-group population risk: O\left(MD\left(\log^{\frac{11}{4}} (K)\sqrt{\frac{ p}{K} } + \frac{\log^{\frac{5}{2}} (K)p\sqrt{d \log (1/\delta)}}{K\ep | Helped |
| Use the DP-FTRL framework as the population-risk minimizer | Worst-group population risk minimization · Sample-oracle setting | excess worst-group population risk: O\left(ML\sqrt{\frac{d^{\frac{1}{2}}\log^2(1/\delta)\log(K)}{\epsilon K}} +\frac{B\log(K)}{\epsilon}\sqrt{\frac{p\log(p) | Helped |
| Use the DP-FTRL framework instead of Minimax Phased ERM | Worst-group population risk minimization · Sample-oracle setting, ε = Θ(1) and p ≥ max{√d, K/d} or √(K/d^{1/2}) ≤ p ≤ √d | excess worst-group population risk | Helped |
| Use Noisy-SGD-MGR for private empirical worst-group risk minimization | Worst-group empirical risk minimization · Offline setting | excess worst-group empirical risk: O\bigg(\frac{MLp\sqrt{d\log(1/\delta)\log(K/\delta)}}{K\epsilon} + \frac{Bp\sqrt{\log(p)\log(1/\delta)}\log(\frac{K\epsi | Helped |
| Replace multiplicative group reweighting with active group selection | Private empirical worst-group risk minimization · Offline setting | excess worst-group empirical risk: \Tilde{O}\left(\sqrt{\frac{MLBp}{K\epsilon}}+\frac{MLp\sqrt{d}}{K\epsilon}\right) | Hurt |
| Remove privacy noise and use the regularization-based method | Worst-group population risk minimization · Offline setting | excess worst-group population risk: \tilde{O}\left(\sqrt{\frac{p}{K}}\right) | Helped |
Surprising findings
- The stability-based generalization bound avoids the sqrt(Delta) rate known for strong-duality-gap analyses in L2/L2 stochastic saddle-point problems.
Limitations
- Optimal rate for worst-group population risk in general is left open.
- Rates hold up to logarithmic factors and in specific regimes of p, d, K.
Experimental setup
Metrics: excess worst-group risk
Baselines: DP stochastic saddle point methods non-private worst-group lower bound
Builds on: phased ERM DP-FTRL EXP3 stability-based generalization analysis
Closest papers by meaning
- Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates (AAAI 2025 · similarity 0.88)
- Locally Optimal Private Sampling: Beyond the Global Minimax (NeurIPS 2025 · similarity 0.88)
- Faster Algorithms for User-Level Private Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.87)
- Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyond (ICML 2024 · similarity 0.87)
- Optimal Differentially Private Model Training with Public Data (ICML 2024 · similarity 0.86)
- Optimal Survey Design for Private Mean Estimation (ICML 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.