mlsanityData to 14 Oct 2026

Improved Rates of Differentially Private Nonconvex-Strongly-Concave Minimax Optimization

arXiv 2503.18317 ↗First posted 24 Mar 2025cs.LGcited by 5

Not on the map. Why?

Abstract (arXiv)

In this paper, we study the problem of (finite sum) minimax optimization in the Differential Privacy (DP) model. Unlike most of the previous studies on the (strongly) convex-concave settings or loss functions satisfying the Polyak-Lojasiewicz condition, here we mainly focus on the nonconvex-strongly-concave one, which encapsulates many models in deep learning such as deep AUC maximization. Specifically, we first analyze a DP version of Stochastic Gradient Descent Ascent (SGDA) and show that it is possible to get a DP estimator whose l2-norm of the gradient for the empirical risk function is upper bounded by tildeO(fracd1/4(nε)1/2), where d is the model dimension and n is the sample size. We then propose a new method with less gradient noise variance and improve the upper bound to tildeO(fracd1/3(nε)2/3), which matches the best-known result for DP Empirical Risk Minimization with non-convex loss. We also discussed several lower bounds of private minimax optimization. Finally, experiments on AUC maximization, generative adversarial networks, and temporal difference learning with real-world data support our theoretical analysis.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 37 of its 61 references that are in the map. First posted on arXiv 24 Mar 2025.

Builds on

37 of 61 references.

References · 37

  1. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,305
  2. 2016Deep Learning with Differential Privacycited by 2,728
  3. 2017Generative Adversarial Networks: An Overviewcited by 590
  4. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
  5. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 270
  6. 2018Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergencescited by 242
  7. 2020Differentially Private Learning Needs Better Features (or Much More Data)cited by 235
  8. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 186
  9. 2020Large-Scale Methods for Distributionally Robust Optimizationcited by 179
  10. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  11. 2021On the Convergence and Robustness of Adversarial Trainingcited by 130
  12. 2018Differentially Private Empirical Risk Minimization Revisited: Faster and More Generalcited by 128
25 more
  1. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  2. 2022AUC Maximization in the Era of Big Data and AI: A Surveycited by 100
  3. 2020Large-scale Robust Deep AUC Maximization: A New Surrogate Loss and Empirical Studies on Medical Image Classificationcited by 86
  4. 2020Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problemscited by 77
  5. 2020A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problemscited by 57
  6. 2019Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applicationscited by 55
  7. 2020On Differentially Private Stochastic Convex Optimization with Heavy-tailed Datacited by 51
  8. 2021A Novel Convergence Analysis for Algorithms of the Adam Familycited by 50
  9. 2021High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Datacited by 42
  10. 2022Federated Minimax Optimization: Improved Convergence Analyses and Algorithmscited by 37
  11. 2022Faster Rates of Convergence to Stationary Points in Differentially Private Optimizationcited by 32
  12. 2019Efficient Privacy-Preserving Stochastic Nonconvex Optimizationcited by 27
  13. 2020Alternating proximal-gradient steps for (stochastic) nonconvex-concave minimax problemscited by 26
  14. 2022Differentially Private SGDA for Minimax Problemscited by 23
  15. 2022SAPD+: An Accelerated Stochastic Method for Nonconvex-Concave Minimax Problemscited by 23
  16. 2022Bring Your Own Algorithm for Optimal Differentially Private Stochastic Minimax Optimizationcited by 22
  17. 2021Optimal Algorithms for Differentially Private Stochastic Monotone Variational Inequalities and Saddle-Point Problemscited by 17
  18. 2023LibAUC: A Deep Learning Library for X-Risk Optimizationcited by 15
  19. 2023Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gapcited by 12
  20. 2022Momentum Aggregation for Private Non-convex ERMcited by 10
  21. 2023DIFF2: Differential Private Optimization via Gradient Differences for Nonconvex Distributed Learningcited by 10
  22. 2024Differentially Private Worst-group Risk Minimizationcited by 9
  23. 2023Differentially Private Stochastic Convex Optimization in (Non)-Euclidean Space Revisitedcited by 8
  24. 2022Differentially Private Temporal Difference Learning with Stochastic Nonconvex-Strongly-Concave Optimizationcited by 7
  25. 2024Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problemscited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 3; 2026: 2.

5 papers.

  1. 2025Second-Order Convergence in Private Stochastic Non-Convex Optimizationcited by 3
  2. 2025Attributing Data for Sharpness-Aware Minimizationcited by 2
  3. 2025Differentially Private Sparse Linear Regression with Heavy-tailed Responsescited by 1
  4. 2026Differentially Private Non-convex Distributionally Robust Optimizationcited by 1
  5. 2026Finding Differentially Private Second Order Stationary Points in Stochastic Minimax Optimizationcited by 0