# Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gap

arXiv: https://arxiv.org/abs/2302.12909 · HTML: https://mlsanity.com/paper/2302.12909/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 43 references that are in the map.
- First posted on arXiv 24 Feb 2023.

## Builds on (most cited first, 26 of 26)

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Agnostic Federated Learning](https://mlsanity.com/paper/1902.00146/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Practical and Private (Deep) Learning without Sampling or Shuffling](https://mlsanity.com/paper/2103.00039/) (2021)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [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)
- [Stochastic Variance Reduction Methods for Saddle-Point Problems](https://mlsanity.com/paper/1605.06398/) (2016)
- [How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD](https://mlsanity.com/paper/1801.02982/) (2018)
- [Stability and Convergence Trade-off of Iterative Optimization Algorithms](https://mlsanity.com/paper/1804.01619/) (2018)
- [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)
- [Stability and Generalization of Stochastic Gradient Methods for Minimax Problems](https://mlsanity.com/paper/2105.03793/) (2021)
- [The Complexity of Making the Gradient Small in Stochastic Convex Optimization](https://mlsanity.com/paper/1902.04686/) (2019)
- [Faster Rates of Convergence to Stationary Points in Differentially Private Optimization](https://mlsanity.com/paper/2206.00846/) (2022)
- [Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization](https://mlsanity.com/paper/1409.3257/) (2014)
- [Generalization Bounds for Stochastic Saddle Point Problems](https://mlsanity.com/paper/2006.02067/) (2020)
- [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)
- [PAC-Bayes bounds for stable algorithms with instance-dependent priors](https://mlsanity.com/paper/1806.06827/) (2018)
- [Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimization](https://mlsanity.com/paper/2104.13326/) (2021)
- [Optimal Algorithms for Differentially Private Stochastic Monotone Variational Inequalities and Saddle-Point Problems](https://mlsanity.com/paper/2104.02988/) (2021)
- [Differentially Private Generalized Linear Models Revisited](https://mlsanity.com/paper/2205.03014/) (2022)
- [What is a Good Metric to Study Generalization of Minimax Learners?](https://mlsanity.com/paper/2206.04502/) (2022)
- [Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods](https://mlsanity.com/paper/2202.04640/) (2022)

## Built on by (most cited first, 12 of 12)

- [Certified Minimax Unlearning with Generalization Rates and Deletion Capacity](https://mlsanity.com/paper/2312.10336/) (2023)
- [Differentially Private Worst-group Risk Minimization](https://mlsanity.com/paper/2402.19437/) (2024)
- [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)
- [Private Algorithms for Stochastic Saddle Points and Variational Inequalities: Beyond Euclidean Geometry](https://mlsanity.com/paper/2411.05198/) (2024)
- [On the Gradient Complexity of Private Optimization with Private Oracles](https://mlsanity.com/paper/2511.13999/) (2025)
- [Private Rate-Constrained Optimization with Applications to Fair Learning](https://mlsanity.com/paper/2505.22703/) (2025)
- [Differentially Private Bilevel Optimization: Efficient Algorithms with Near-Optimal Rates](https://mlsanity.com/paper/2506.12994/) (2025)
- [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)
- [Optimal Rates for Pure varepsilon-Differentially Private Stochastic Convex Optimization with Heavy Tails](https://mlsanity.com/paper/2604.06492/) (2026)
- [Generalization Analysis of Biased Stochastic Gradient Methods for Minimax Problems](https://mlsanity.com/paper/2610.19322/) (2026)

## Abstract (arXiv)

We show that convex-concave Lipschitz stochastic saddle point problems (also known as stochastic minimax optimization) can be solved under the constraint of (ε,δ)-differential privacy with strong (primal-dual) gap rate of tilde Obig(frac1√n + frac√dnεbig), where n is the dataset size and d is the dimension of the problem. This rate is nearly optimal, based on existing lower bounds in differentially private stochastic optimization. Specifically, we prove a tight upper bound on the strong gap via novel implementation and analysis of the recursive regularization technique repurposed for saddle point problems. We show that this rate can be attained with Obig(minbigfracn2ε1.5√d, n3/2bigbig) gradient complexity, and tildeO(n) gradient complexity if the loss function is smooth. As a byproduct of our method, we develop a general algorithm that, given a black-box access to a subroutine satisfying a certain α primal-dual accuracy guarantee with respect to the empirical objective, gives a solution to the stochastic saddle point problem with a strong gap of tildeO(α+frac1√n). We show that this α-accuracy condition is satisfied by standard algorithms for the empirical saddle point problem such as the proximal point method and the stochastic gradient descent ascent algorithm. Further, we show that even for simple problems it is possible for an algorithm to have zero weak gap and suffer from Omega(1) strong gap. We also show that there exists a fundamental tradeoff between stability and accuracy. Specifically, we show that any Delta-stable algorithm has empirical gap Omegabig(frac1Delta nbig), and that this bound is tight. This result also holds also more specifically for empirical risk minimization problems and may be of independent interest.