Research map / Optimization / Nonconvex and smooth optimization
Improved Rates of Differentially Private Nonconvex-Strongly-Concave Minimax Optimization
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 DP finite-sum minimax optimization in the nonconvex-strongly-concave setting, analyzing DP-SGDA and proposing PrivateDiff Minimax, which uses gradient-difference accumulation with adaptive noise to reach an O~(d^{1/3}/(nε)^{2/3}) stationarity bound.
Problem
Differentially private minimax optimization with nonconvex-strongly-concave losses (e.g., deep AUC maximization), where prior DP utility bounds for gradient norm were weaker than DP-ERM with nonconvex loss.
Approach
Adds noise scaled to the norm of consecutive iterate differences by accumulating clipped stochastic gradient differences (variance-reduction-style estimator with periodic restarts), so later iterations need less noise; y is updated by clipped mini-batch SGA with output perturbation.
Key results
- PrivateDiff Minimax achieves a utility bound of O~(d^{1/3}/(nε)^{2/3}), improving on DP-SGDA's O~(d^{1/4}/(nε)^{1/2}) and matching the best known DP-ERM nonconvex rate.
- On MNIST at epsilon=0.5, PrivateDiff reaches AUC 0.9608 versus 0.8837 for DP-SGDA.
- On imbalanced MNIST at epsilon=0.5, PrivateDiff reaches AUC 0.9033 versus 0.7739 for DP-SGDA.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace DP-SGDA with PrivateDiff Minimax | AUC maximization · Fashion-MNIST, MNIST, Imbalanced Fashion-MNIST, and Imbalanced MNIST (ε=0.5, 1, 5, 10) | AUC: Fashion-MNIST ε=0.5: 0.9203 -> 0.9569; MNIST ε=0.5: 0.8837 -> 0.9608 | Helped |
| Replace DP-SGDA with PrivateDiff Minimax | AUC maximization · Imbalanced Fashion-MNIST (ε=0.5, 1, 5, 10) | AUC: 0.8398 -> 0.9442 | Helped |
| Replace DP-SGDA with PrivateDiff Minimax | AUC maximization · Imbalanced MNIST (ε=0.5, 1, 5, 10) | AUC: 0.7739 -> 0.9033 | Helped |
| Use gradient-difference accumulation to reduce the private gradient estimator's noise | DP minimax optimization · Nonconvex-strongly-concave minimax optimization | gradient norm: \tilde{O}(\frac{d^{1/4}}{\sqrt{n\epsilon}}) -> \widetilde{O}(\frac{d^{1 / 3}}{(n \epsilon )^{2 / 3}}) | Helped |
| Increase the privacy budget ε | DP-SGDA and PrivateDiff Minimax · Fashion-MNIST and MNIST | AUC | Helped |
Limitations
- Upper bound only matches DP-ERM rate; gap to lower bound remains (lower bound Omega(sqrt(d log(1/δ))/(nε)))
- Requires many inner SGA iterations and parameter choices (restart interval, batch size) tied to theory
- Experiments limited to MNIST-type datasets with a small MLP in the main text
Experimental setup
Datasets: MNIST Fashion-MNIST
Benchmarks: MNIST Fashion-MNIST imbalanced MNIST imbalanced Fashion-MNIST
Metrics: AUC gradient norm gradient variance
Baselines: DP-SGDA
Builds on: DP-SGD DP-SGDA moment accountant SGDA (non-private NC-SC analysis)
Closest papers by meaning
- Differentially Private Optimization with Sparse Gradients (NeurIPS 2024 · similarity 0.91)
- Bring Your Own Algorithm for Optimal Differentially Private Stochastic Minimax Optimization (NeurIPS 2022 · similarity 0.90)
- Faster Algorithms for User-Level Private Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.90)
- Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates (AAAI 2025 · similarity 0.90)
- Improved Differentially Private and Lazy Online Convex Optimization: Lower Regret without Smoothness Requirements (ICML 2024 · similarity 0.89)
- Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions (NeurIPS 2024 · similarity 0.88)
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.