mlsanityData to 14 Oct 2026

Bring Your Own Algorithm for Optimal Differentially Private Stochastic Minimax Optimization

arXiv 2206.00363 ↗First posted 1 Jun 2022cs.LG cs.CR math.OCcited by 22

Not on the map. Why?

Abstract (arXiv)

We study differentially private (DP) algorithms for smooth stochastic minimax optimization, with stochastic minimization as a byproduct. The holy grail of these settings is to guarantee the optimal trade-off between the privacy and the excess population loss, using an algorithm with a linear time-complexity in the number of training samples. We provide a general framework for solving differentially private stochastic minimax optimization (DP-SMO) problems, which enables the practitioners to bring their own base optimization algorithm and use it as a black-box to obtain the near-optimal privacy-loss trade-off. Our framework is inspired from the recently proposed Phased-ERM method [22] for nonsmooth differentially private stochastic convex optimization (DP-SCO), which exploits the stability of the empirical risk minimization (ERM) for the privacy guarantee. The flexibility of our approach enables us to sidestep the requirement that the base algorithm needs to have bounded sensitivity, and allows the use of sophisticated variance-reduced accelerated methods to achieve near-linear time-complexity. To the best of our knowledge, these are the first near-linear time algorithms with near-optimal guarantees on the population duality gap for smooth DP-SMO, when the objective is (strongly-)convex--(strongly-)concave. Additionally, based on our flexible framework, we enrich the family of near-linear time algorithms for smooth DP-SCO with the near-optimal privacy-loss trade-off.

Key facts. Cited by 22 papers in the map (data through 14 Oct 2026). Builds on 29 of its 51 references that are in the map. First posted on arXiv 1 Jun 2022.

Builds on

29 of 51 references.

References · 29

  1. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,415
  2. 2019Advances and Open Problems in Federated Learningcited by 3,046
  3. 2016Deep Learning with Differential Privacycited by 2,728
  4. 2020Extracting Training Data from Large Language Modelscited by 2,189
  5. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
  6. 2013The Composition Theorem for Differential Privacycited by 297
  7. 2019Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networkscited by 293
  8. 2018Differentially Private Generative Adversarial Networkcited by 235
  9. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 220
  10. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 186
  11. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 173
  12. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 153
17 more
  1. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 135
  2. 2018Differentially Private Empirical Risk Minimization Revisited: Faster and More Generalcited by 128
  3. 2018Privacy Amplification by Iterationcited by 100
  4. 2021Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometrycited by 83
  5. 2021Differential Privacy Dynamics of Langevin Diffusion and Noisy Gradient Descentcited by 73
  6. 2017Efficient Private ERM for Smooth Objectivescited by 61
  7. 2016Stochastic Variance Reduction Methods for Saddle-Point Problemscited by 60
  8. 2021Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settingscited by 45
  9. 2020Train simultaneously, generalize better: Stability of gradient-based minimax learnerscited by 44
  10. 2021Stability and Generalization of Stochastic Gradient Methods for Minimax Problemscited by 36
  11. 2020Generalization Bounds for Stochastic Saddle Point Problemscited by 28
  12. 2021Stochastic Bias-Reduced Gradient Methodscited by 25
  13. 2022Differentially Private SGDA for Minimax Problemscited by 23
  14. 2021Optimal Algorithms for Differentially Private Stochastic Monotone Variational Inequalities and Saddle-Point Problemscited by 17
  15. 2021Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimizationcited by 16
  16. 2022Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methodscited by 15
  17. 2022Stability and Generalization of Differentially Private Minimax Problemscited by 2

Built on by

Cited by year (2026 to 14 Oct)

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

22 papers.

Sort:

By area:

  1. 2023Certified Minimax Unlearning with Generalization Rates and Deletion Capacitycited by 29
  2. 2023DPZero: Private Fine-Tuning of Language Models without Backpropagationcited by 26
  3. 2022Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimizationcited by 20
  4. 2022Stochastic Differentially Private and Fair Learningcited by 16
  5. 2023Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gapcited by 12
  6. 2024How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimizationcited by 10
  7. 2023Near Optimal Private and Robust Linear Regressioncited by 9
  8. 2024Differentially Private Worst-group Risk Minimizationcited by 9
  9. 2024Private Heterogeneous Federated Learning Without a Trusted Server Revisited: Error-Optimal and Communication-Efficient Algorithms for Convex Lossescited by 8
  10. 2024Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problemscited by 7
  11. 2025Differentially Private Learners for Heterogeneous Treatment Effectscited by 5
  12. 2025Improved Rates of Differentially Private Nonconvex-Strongly-Concave Minimax Optimizationcited by 5
10 more
  1. 2024Faster Algorithms for User-Level Private Stochastic Convex Optimizationcited by 4
  2. 2023Optimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimizationcited by 3
  3. 2024Private Algorithms for Stochastic Saddle Points and Variational Inequalities: Beyond Euclidean Geometrycited by 2
  4. 2025PrivATE: Differentially Private Confidence Intervals for Average Treatment Effectscited by 2
  5. 2024Optimal Rates for O(1)-Smooth DP-SCO with a Single Epoch and Large Batchescited by 1
  6. 2025Private Rate-Constrained Optimization with Applications to Fair Learningcited by 1
  7. 2026Differentially Private Non-convex Distributionally Robust Optimizationcited by 1
  8. 2025Differentially Private Equilibrium Finding in Polymatrix Gamescited by 0
  9. 2025Enhancing Privacy in Decentralized Min-Max Optimization: A Differentially Private Approachcited by 0
  10. 2026Finding Differentially Private Second Order Stationary Points in Stochastic Minimax Optimizationcited by 0