mlsanityData to 7 Oct 2026

Differentially Private SGDA for Minimax Problems

arXiv 2201.09046 ↗First posted 22 Jan 2022cs.LG cs.CRcited by 23

Not on the map. Why?

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.

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

Builds on

35 of 71 references.

References · 35

  1. 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,283
  2. 2016Deep Learning with Differential Privacycited by 2,682
  3. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  4. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  5. 2019Agnostic Federated Learningcited by 451
  6. 2019Fair Resource Allocation in Federated Learningcited by 389
  7. 2017Certifying Some Distributional Robustness with Principled Adversarial Trainingcited by 333
  8. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
  9. 2014RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Responsecited by 262
  10. 2018Differentially Private Generative Adversarial Networkcited by 235
  11. 2018Subsampled R'enyi Differential Privacy and Analytical Moments Accountantcited by 234
  12. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 183
23 more
  1. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  2. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 152
  3. 2020Minimax Pareto Fairness: A Multi Objective Perspectivecited by 152
  4. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  5. 2017Collecting Telemetry Data Privatelycited by 147
  6. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 118
  7. 2014Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Boundscited by 104
  8. 2017Stability and Generalization of Learning Algorithms that Converge to Global Optimacited by 100
  9. 2017Data-Dependent Stability of Stochastic Gradient Descentcited by 90
  10. 2020Robust Optimization for Fairness with Noisy Protected Groupscited by 78
  11. 2020Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problemscited by 75
  12. 2018Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learningcited by 62
  13. 2019Stochastic AUC Maximization with Deep Neural Networkscited by 61
  14. 2020On Differentially Private Stochastic Convex Optimization with Heavy-tailed Datacited by 51
  15. 2020Train simultaneously, generalize better: Stability of gradient-based minimax learnerscited by 43
  16. 2013One-Pass AUC Optimizationcited by 42
  17. 2020Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problemscited by 37
  18. 2021Stability and Generalization of Stochastic Gradient Methods for Minimax Problemscited by 35
  19. 2017Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problemscited by 32
  20. 2020Generalization Bounds for Stochastic Saddle Point Problemscited by 27
  21. 2020Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Boundscited by 26
  22. 2021Differentially Private SGD with Non-Smooth Lossescited by 22
  23. 2021Optimal Algorithms for Differentially Private Stochastic Monotone Variational Inequalities and Saddle-Point Problemscited by 17

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 7; 2023: 6; 2024: 4; 2025: 4; 2026: 2.

23 papers.

Sort:

By area:

  1. 2023Certified Minimax Unlearning with Generalization Rates and Deletion Capacitycited by 29
  2. 2022Bring Your Own Algorithm for Optimal Differentially Private Stochastic Minimax Optimizationcited by 22
  3. 2022What is a Good Metric to Study Generalization of Minimax Learners?cited by 16
  4. 2022Stochastic Differentially Private and Fair Learningcited by 16
  5. 2022Fair Federated Learning via Bounded Group Losscited by 12
  6. 2023Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gapcited by 11
  7. 2024Differentially Private Worst-group Risk Minimizationcited by 9
  8. 2023Stability and Generalization of the Decentralized Stochastic Gradient Descent Ascent Algorithmcited by 8
  9. 2022Differentially Private Temporal Difference Learning with Stochastic Nonconvex-Strongly-Concave Optimizationcited by 7
  10. 2024Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problemscited by 7
  11. 2022Generalization Bounds of Nonconvex-(Strongly)-Concave Stochastic Minimax Optimizationcited by 6
  12. 2024Stability and Generalization in Free Adversarial Trainingcited by 5
11 more
  1. 2025Improved Rates of Differentially Private Nonconvex-Strongly-Concave Minimax Optimizationcited by 5
  2. 2023Differentially Private Non-Convex Optimization under the KL Condition with Optimal Ratescited by 4
  3. 2022Stability and Generalization of Differentially Private Minimax Problemscited by 2
  4. 2023Fairness-aware Federated Minimax Optimization with Convergence Guaranteecited by 2
  5. 2024Private Algorithms for Stochastic Saddle Points and Variational Inequalities: Beyond Euclidean Geometrycited by 2
  6. 2023Fairness-aware Differentially Private Collaborative Filteringcited by 1
  7. 2026Differentially Private Non-convex Distributionally Robust Optimizationcited by 1
  8. 2025Differentially Private Equilibrium Finding in Polymatrix Gamescited by 0
  9. 2025Private Rate-Constrained Optimization with Applications to Fair Learningcited by 0
  10. 2025Enhancing Privacy in Decentralized Min-Max Optimization: A Differentially Private Approachcited by 0
  11. 2026Finding Differentially Private Second Order Stationary Points in Stochastic Minimax Optimizationcited by 0