Research map / Optimization / Nonconvex and smooth optimization
Private Algorithms for Stochastic Saddle Points and Variational Inequalities: Beyond Euclidean Geometry
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Systematic study of differentially private stochastic saddle point problems and variational inequalities in non-Euclidean (ℓp/ℓq) geometries, using a new generalization analysis of recursive regularization to get near-optimal strong gap rates.
Problem
Differentially private stochastic saddle point problems (SSPs) and stochastic variational inequalities (SVIs) in general (non-Euclidean) geometries, where prior DP rates were known mainly for Euclidean setups.
Approach
Extends recursive regularization to ℓp/ℓq geometries using a stability-implies-generalization argument applied to population-saddle-point-centered functions, avoiding generalization bounds on the strong gap itself; for SVIs, adds a relative-stationarity accuracy measure and random-iterate selection in stochastic mirror prox.
Key results
- Achieves strong SP-gap Õ(1/√n + √d/(nε)) for any p,q in [1,2] for DP ℓp/ℓq convex-concave SSPs, matching lower bounds up to logs.
- Obtains first strong VI-gap Õ(1/√n + √d/(nε)) for monotone bounded Lipschitz SVIs in ℓp setups, p in [1,2], near optimal for p-1=Ω(1).
- Gradient evaluations Õ(min{n²ε^1.5/√d, n^1.5}); for p=2 near-linear time via accelerated SVRG.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Extend recursive regularization from Euclidean geometry to ℓ_p/ℓ_q geometry | DP stochastic saddle point problems · Lipschitz convex-concave SSP, ℓ_p/ℓ_q setup (p,q∈[1,2]) | strong SP-gap: \tilde{O}\big(\frac{1}{\sqrt{n}} + \frac{\sqrt{d}}{n\epsilon}\big) | Helped |
| Adapt recursive regularization and its analysis to stochastic variational inequalities | DP stochastic variational inequalities · Monotone, bounded, Lipschitz SVI, ℓ_p setup (p∈[1,2]) | strong VI-gap: \tilde{O}\br{\frac{1}{\sqrt{n}} + \frac{\sqrt{d}}{n\epsilon}} | Helped |
| Use accelerated SVRG with Gaussian noise | DP SVI algorithm in the ℓ_2 setting · Lipschitz SVI, ℓ_2 setup | gradient evaluations: O(n + \smooth n\log(n/\delta)) | Helped |
| Use the proposed method instead of the prior Euclidean DP SVI approach | DP stochastic variational inequalities · Euclidean SVI | strong VI-gap: \big(\frac{1}{n^{1/3}} + \frac{\sqrt{d}}{n^{2/3}\epsilon}\big) -> \tilde{O}\Big(\kappa^{3.5}\rad\lip\big(\frac{\sqrt{d\l | Helped |
Surprising findings
- The VI-gap does not upper bound the SP-gap in general, even when the operator is a saddle operator (example with f=z²).
Limitations
- Rates hold only up to logarithmic factors and a kappa factor (at most log d) for non-Euclidean norms.
- Near optimality for SVIs established only for p-1=Ω(1); for p near 1 the lower bound does not match.
Experimental setup
Metrics: strong SP-gap strong VI-gap
Baselines: Euclidean DP SSP recursive regularization DP SVI prior work (Euclidean)
Builds on: recursive regularization stochastic mirror prox uniform argument stability moments accountant
Closest papers by meaning
- Dealing With Unbounded Gradients in Stochastic Saddle-point Optimization (ICML 2024 · similarity 0.88)
- Stochastic Variance Reduction Methods for Saddle-Point Problems (NeurIPS 2016 · similarity 0.88)
- Adaptive and Universal Algorithms for Variational Inequalities with Optimal Convergence (AAAI 2022 · similarity 0.88)
- Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions (NeurIPS 2024 · similarity 0.88)
- Second-Order Convergence in Private Stochastic Non-Convex Optimization (NeurIPS 2025 · similarity 0.87)
- On Linear Convergence in Smooth Convex-Concave Bilinearly-Coupled Saddle-Point Optimization: Lower Bounds and Optimal Algorithms (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.