mlsanityData to 14 Oct 2026

Optimal Algorithms for Differentially Private Stochastic Monotone Variational Inequalities and Saddle-Point Problems

arXiv 2104.02988 ↗First posted 7 Apr 2021math.OC cs.LG stat.MLcited by 17

Not on the map. Why?

Abstract (arXiv)

In this work, we conduct the first systematic study of stochastic variational inequality (SVI) and stochastic saddle point (SSP) problems under the constraint of differential privacy (DP). We propose two algorithms: Noisy Stochastic Extragradient (NSEG) and Noisy Inexact Stochastic Proximal Point (NISPP). We show that a stochastic approximation variant of these algorithms attains risk bounds vanishing as a function of the dataset size, with respect to the strong gap function; and a sampling with replacement variant achieves optimal risk bounds with respect to a weak gap function. We also show lower bounds of the same order on weak gap function. Hence, our algorithms are optimal. Key to our analysis is the investigation of algorithmic stability bounds, both of which are new even in the nonprivate case. The dependence of the running time of the sampling with replacement algorithms, with respect to the dataset size n, is n2 for NSEG and tildeO(n3/2) for NISPP.

Key facts. Cited by 17 papers in the map (data through 14 Oct 2026). Builds on 21 of its 60 references that are in the map. First posted on arXiv 7 Apr 2021.

Builds on

21 of 60 references.

References · 21

  1. 2016Deep Learning with Differential Privacycited by 2,728
  2. 2017Renyi Differential Privacycited by 650
  3. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
  4. 2019Fair Resource Allocation in Federated Learningcited by 394
  5. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 346
  6. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 186
  7. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 173
  8. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 153
  9. 2014Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Boundscited by 107
  10. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 98
  11. 2019Sharper bounds for uniformly stable algorithmscited by 93
  12. 2019On the convergence of single-call stochastic extra-gradient methodscited by 89
9 more
  1. 2019Fairness risk measurescited by 85
  2. 2021Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometrycited by 83
  3. 2015Between Pure and Approximate Differential Privacycited by 56
  4. 2021Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 51
  5. 2020Train simultaneously, generalize better: Stability of gradient-based minimax learnerscited by 44
  6. 2020Simple and optimal methods for stochastic variational inequalities, I: operator extrapolationcited by 35
  7. 2020Generalization Bounds for Stochastic Saddle Point Problemscited by 28
  8. 2014Private Multiplicative Weights Beyond Linear Queriescited by 17
  9. 2019A Proximal-Point Algorithm with Variable Sample-sizes (PPAWSS) for Monotone Stochastic Variational Inequality Problemscited by 2

Built on by

Cited by year

Citing papers per year: 2022: 5; 2023: 4; 2024: 4; 2025: 4.

17 papers.

Sort:

By area:

  1. 2023Certified Minimax Unlearning with Generalization Rates and Deletion Capacitycited by 29
  2. 2022Differentially Private SGDA for Minimax Problemscited by 23
  3. 2022Bring Your Own Algorithm for Optimal Differentially Private Stochastic Minimax Optimizationcited by 22
  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. 2024Private Heterogeneous Federated Learning Without a Trusted Server Revisited: Error-Optimal and Communication-Efficient Algorithms for Convex Lossescited by 8
  8. 2022Differentially Private Temporal Difference Learning with Stochastic Nonconvex-Strongly-Concave Optimizationcited by 7
  9. 2022Generalization Bounds of Nonconvex-(Strongly)-Concave Stochastic Minimax Optimizationcited by 7
  10. 2024Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problemscited by 7
  11. 2025Improved Rates of Differentially Private Nonconvex-Strongly-Concave Minimax Optimizationcited by 5
  12. 2023Optimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimizationcited by 3
5 more
  1. 2024Private Algorithms for Stochastic Saddle Points and Variational Inequalities: Beyond Euclidean Geometrycited by 2
  2. 2025Private Rate-Constrained Optimization with Applications to Fair Learningcited by 1
  3. 2023First-order methods for Stochastic Variational Inequality problems with Function Constraintscited by 0
  4. 2025Differentially Private Equilibrium Finding in Polymatrix Gamescited by 0
  5. 2025Enhancing Privacy in Decentralized Min-Max Optimization: A Differentially Private Approachcited by 0