# Optimal Algorithms for Differentially Private Stochastic Monotone Variational Inequalities and Saddle-Point Problems arXiv: https://arxiv.org/abs/2104.02988 · HTML: https://mlsanity.com/paper/2104.02988/ ## 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 (most cited first, 21 of 21) - [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016) - [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017) - [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015) - [Fair Resource Allocation in Federated Learning](https://mlsanity.com/paper/1905.10497/) (2019) - [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016) - [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) - [Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds](https://mlsanity.com/paper/1405.7085/) (2014) - [High probability generalization bounds for uniformly stable algorithms with nearly optimal rate](https://mlsanity.com/paper/1902.10710/) (2019) - [Sharper bounds for uniformly stable algorithms](https://mlsanity.com/paper/1910.07833/) (2019) - [On the convergence of single-call stochastic extra-gradient methods](https://mlsanity.com/paper/1908.08465/) (2019) - [Fairness risk measures](https://mlsanity.com/paper/1901.08665/) (2019) - [Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry](https://mlsanity.com/paper/2103.01516/) (2021) - [Between Pure and Approximate Differential Privacy](https://mlsanity.com/paper/1501.06095/) (2015) - [Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2103.01278/) (2021) - [Train simultaneously, generalize better: Stability of gradient-based minimax learners](https://mlsanity.com/paper/2010.12561/) (2020) - [Simple and optimal methods for stochastic variational inequalities, I: operator extrapolation](https://mlsanity.com/paper/2011.02987/) (2020) - [Generalization Bounds for Stochastic Saddle Point Problems](https://mlsanity.com/paper/2006.02067/) (2020) - [Private Multiplicative Weights Beyond Linear Queries](https://mlsanity.com/paper/1407.1571/) (2014) - [A Proximal-Point Algorithm with Variable Sample-sizes (PPAWSS) for Monotone Stochastic Variational Inequality Problems](https://mlsanity.com/paper/1909.13424/) (2019) ## Built on by (most cited first, 17 of 17) - [Certified Minimax Unlearning with Generalization Rates and Deletion Capacity](https://mlsanity.com/paper/2312.10336/) (2023) - [Differentially Private SGDA for Minimax Problems](https://mlsanity.com/paper/2201.09046/) (2022) - [Bring Your Own Algorithm for Optimal Differentially Private Stochastic Minimax Optimization](https://mlsanity.com/paper/2206.00363/) (2022) - [Stochastic Differentially Private and Fair Learning](https://mlsanity.com/paper/2210.08781/) (2022) - [Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gap](https://mlsanity.com/paper/2302.12909/) (2023) - [How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimization](https://mlsanity.com/paper/2402.11173/) (2024) - [Private Heterogeneous Federated Learning Without a Trusted Server Revisited: Error-Optimal and Communication-Efficient Algorithms for Convex Losses](https://mlsanity.com/paper/2407.09690/) (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) - [Improved Rates of Differentially Private Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2503.18317/) (2025) - [Optimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimization](https://mlsanity.com/paper/2310.17759/) (2023) - [Private Algorithms for Stochastic Saddle Points and Variational Inequalities: Beyond Euclidean Geometry](https://mlsanity.com/paper/2411.05198/) (2024) - [Private Rate-Constrained Optimization with Applications to Fair Learning](https://mlsanity.com/paper/2505.22703/) (2025) - [First-order methods for Stochastic Variational Inequality problems with Function Constraints](https://mlsanity.com/paper/2304.04778/) (2023) - [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) ## 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.