# Differentially Private SGDA for Minimax Problems

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 71 references that are in the map.
- First posted on arXiv 22 Jan 2022.

## Builds on (most cited first, 30 of 35)

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Agnostic Federated Learning](https://mlsanity.com/paper/1902.00146/) (2019)
- [Fair Resource Allocation in Federated Learning](https://mlsanity.com/paper/1905.10497/) (2019)
- [Certifying Some Distributional Robustness with Principled Adversarial Training](https://mlsanity.com/paper/1710.10571/) (2017)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [Subsampled R'enyi Differential Privacy and Analytical Moments Accountant](https://mlsanity.com/paper/1808.00087/) (2018)
- [Differentially Private Generative Adversarial Network](https://mlsanity.com/paper/1802.06739/) (2018)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [Minimax Pareto Fairness: A Multi Objective Perspective](https://mlsanity.com/paper/2011.01821/) (2020)
- [Collecting Telemetry Data Privately](https://mlsanity.com/paper/1712.01524/) (2017)
- [Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods](https://mlsanity.com/paper/1902.08297/) (2019)
- [Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08157/) (2020)
- [Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds](https://mlsanity.com/paper/1405.7085/) (2014)
- [Stability and Generalization of Learning Algorithms that Converge to Global Optima](https://mlsanity.com/paper/1710.08402/) (2017)
- [Data-Dependent Stability of Stochastic Gradient Descent](https://mlsanity.com/paper/1703.01678/) (2017)
- [Robust Optimization for Fairness with Noisy Protected Groups](https://mlsanity.com/paper/2002.09343/) (2020)
- [Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems](https://mlsanity.com/paper/2001.03724/) (2020)
- [Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learning](https://mlsanity.com/paper/1810.02060/) (2018)
- [Stochastic AUC Maximization with Deep Neural Networks](https://mlsanity.com/paper/1908.10831/) (2019)
- [On Differentially Private Stochastic Convex Optimization with Heavy-tailed Data](https://mlsanity.com/paper/2010.11082/) (2020)
- [Train simultaneously, generalize better: Stability of gradient-based minimax learners](https://mlsanity.com/paper/2010.12561/) (2020)
- [One-Pass AUC Optimization](https://mlsanity.com/paper/1305.1363/) (2013)
- [Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2002.09621/) (2020)
- [Stability and Generalization of Stochastic Gradient Methods for Minimax Problems](https://mlsanity.com/paper/2105.03793/) (2021)

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

- [Certified Minimax Unlearning with Generalization Rates and Deletion Capacity](https://mlsanity.com/paper/2312.10336/) (2023)
- [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)
- [Stochastic Differentially Private and Fair Learning](https://mlsanity.com/paper/2210.08781/) (2022)
- [Fair Federated Learning via Bounded Group Loss](https://mlsanity.com/paper/2203.10190/) (2022)
- [Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gap](https://mlsanity.com/paper/2302.12909/) (2023)
- [Stability and Generalization of the Decentralized Stochastic Gradient Descent Ascent Algorithm](https://mlsanity.com/paper/2310.20369/) (2023)
- [Differentially Private Worst-group Risk Minimization](https://mlsanity.com/paper/2402.19437/) (2024)
- [Differentially Private Temporal Difference Learning with Stochastic Nonconvex-Strongly-Concave Optimization](https://mlsanity.com/paper/2201.10447/) (2022)
- [Generalization Bounds of Nonconvex-(Strongly)-Concave Stochastic Minimax Optimization](https://mlsanity.com/paper/2205.14278/) (2022)
- [Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problems](https://mlsanity.com/paper/2403.02912/) (2024)
- [Stability and Generalization in Free Adversarial Training](https://mlsanity.com/paper/2404.08980/) (2024)
- [Improved Rates of Differentially Private Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2503.18317/) (2025)
- [Differentially Private Non-Convex Optimization under the KL Condition with Optimal Rates](https://mlsanity.com/paper/2311.13447/) (2023)
- [Stability and Generalization of Differentially Private Minimax Problems](https://mlsanity.com/paper/2204.04858/) (2022)
- [Fairness-aware Federated Minimax Optimization with Convergence Guarantee](https://mlsanity.com/paper/2307.04417/) (2023)
- [Private Algorithms for Stochastic Saddle Points and Variational Inequalities: Beyond Euclidean Geometry](https://mlsanity.com/paper/2411.05198/) (2024)
- [Fairness-aware Differentially Private Collaborative Filtering](https://mlsanity.com/paper/2303.09527/) (2023)
- [Private Rate-Constrained Optimization with Applications to Fair Learning](https://mlsanity.com/paper/2505.22703/) (2025)
- [Differentially Private Non-convex Distributionally Robust Optimization](https://mlsanity.com/paper/2602.16155/) (2026)
- [Differentially Private Equilibrium Finding in Polymatrix Games](https://mlsanity.com/paper/2503.09538/) (2025)
- [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)

## Abstract (arXiv)

Stochastic gradient descent ascent (SGDA) and its variants have been the workhorse for solving minimax problems. However, in contrast to the well-studied stochastic gradient descent (SGD) with differential privacy (DP) constraints, there is little work on understanding the generalization (utility) of SGDA with DP constraints. In this paper, we use the algorithmic stability approach to establish the generalization (utility) of DP-SGDA in different settings. In particular, for the convex-concave setting, we prove that the DP-SGDA can achieve an optimal utility rate in terms of the weak primal-dual population risk in both smooth and non-smooth cases. To our best knowledge, this is the first-ever-known result for DP-SGDA in the non-smooth case. We further provide its utility analysis in the nonconvex-strongly-concave setting which is the first-ever-known result in terms of the primal population risk. The convergence and generalization results for this nonconvex setting are new even in the non-private setting. Finally, numerical experiments are conducted to demonstrate the effectiveness of DP-SGDA for both convex and nonconvex cases.