# Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problems

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 56 references that are in the map.
- First posted on arXiv 5 Mar 2024.

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

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Fair Resource Allocation in Federated Learning](https://mlsanity.com/paper/1905.10497/) (2019)
- [Data-driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations](https://mlsanity.com/paper/1505.05116/) (2015)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry](https://mlsanity.com/paper/2103.01516/) (2021)
- [Fingerprinting Codes and the Price of Approximate Differential Privacy](https://mlsanity.com/paper/1311.3158/) (2013)
- [Differentially Private Fair Learning](https://mlsanity.com/paper/1812.02696/) (2018)
- [Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2103.01278/) (2021)
- [Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings](https://mlsanity.com/paper/2107.05585/) (2021)
- [Dual Query: Practical Private Query Release for High Dimensional Data](https://mlsanity.com/paper/1402.1526/) (2014)
- [Stochastic Bias-Reduced Gradient Methods](https://mlsanity.com/paper/2106.09481/) (2021)
- [Private Empirical Risk Minimization Beyond the Worst Case: The Effect of the Constraint Set Geometry](https://mlsanity.com/paper/1411.5417/) (2014)
- [Differentially Private SGDA for Minimax Problems](https://mlsanity.com/paper/2201.09046/) (2022)
- [Fully Adaptive Composition in Differential Privacy](https://mlsanity.com/paper/2203.05481/) (2022)
- [Bring Your Own Algorithm for Optimal Differentially Private Stochastic Minimax Optimization](https://mlsanity.com/paper/2206.00363/) (2022)
- [Frank-Wolfe Algorithms for Saddle Point Problems](https://mlsanity.com/paper/1610.07797/) (2016)
- [Optimal Algorithms for Differentially Private Stochastic Monotone Variational Inequalities and Saddle-Point Problems](https://mlsanity.com/paper/2104.02988/) (2021)
- [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)
- [Distributed Learning with Sublinear Communication](https://mlsanity.com/paper/1902.11259/) (2019)
- [Differentially Private Worst-group Risk Minimization](https://mlsanity.com/paper/2402.19437/) (2024)
- [Learning Energy Networks with Generalized Fenchel-Young Losses](https://mlsanity.com/paper/2205.09589/) (2022)
- [ℓp Testing and Learning of Discrete Distributions](https://mlsanity.com/paper/1412.2314/) (2014)
- [Differentially Private Online-to-Batch for Smooth Losses](https://mlsanity.com/paper/2210.06593/) (2022)
- [Stability and Generalization of Differentially Private Minimax Problems](https://mlsanity.com/paper/2204.04858/) (2022)

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

- [Mirror, Mirror of the Flow: How Does Regularization Shape Implicit Bias?](https://mlsanity.com/paper/2504.12883/) (2025)
- [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)
- [Private Rate-Constrained Optimization with Applications to Fair Learning](https://mlsanity.com/paper/2505.22703/) (2025)
- [Mirror Descent Linearized Augmented Lagrangian Methods for Nonconvex Constrained Stochastic Zeroth-Order Optimization](https://mlsanity.com/paper/2504.09409/) (2025)
- [Minimax optimal differentially private synthetic data for smooth queries](https://mlsanity.com/paper/2602.01607/) (2026)
- [Fixed-Parameter Tractability of Private Synthetic Data Generation](https://mlsanity.com/paper/2606.11283/) (2026)

## Abstract (arXiv)

We study the problem of differentially-private (DP) stochastic (convex-concave) saddle-points in the ℓ1 setting. We propose (varepsilon, δ)-DP algorithms based on stochastic mirror descent that attain nearly dimension-independent convergence rates for the expected duality gap, a type of guarantee that was known before only for bilinear objectives. For convex-concave and first-order-smooth stochastic objectives, our algorithms attain a rate of √log(d)/n + (log(d)3/2/[nvarepsilon])1/3, where d is the dimension of the problem and n the dataset size. Under an additional second-order-smoothness assumption, we show that the duality gap is bounded by √log(d)/n + log(d)/√nvarepsilon with high probability, by using bias-reduced gradient estimators. This rate provides evidence of the near-optimality of our approach, since a lower bound of √log(d)/n + log(d)3/4/√nvarepsilon exists. Finally, we show that combining our methods with acceleration techniques from online learning leads to the first algorithm for DP Stochastic Convex Optimization in the ℓ1 setting that is not based on Frank-Wolfe methods. For convex and first-order-smooth stochastic objectives, our algorithms attain an excess risk of √log(d)/n + log(d)7/10/[nvarepsilon]2/5, and when additionally assuming second-order-smoothness, we improve the rate to √log(d)/n + log(d)/√nvarepsilon. Instrumental to all of these results are various extensions of the classical Maurey Sparsification Lemma citePisier:1980, which may be of independent interest.