mlsanityData to 14 Oct 2026

Differentially Private Stochastic Convex Optimization in (Non)-Euclidean Space Revisited

arXiv 2303.18047 ↗First posted 31 Mar 2023cs.LG cs.CR math.OCcited by 8

Not on the map. Why?

Abstract (arXiv)

In this paper, we revisit the problem of Differentially Private Stochastic Convex Optimization (DP-SCO) in Euclidean and general ℓpd spaces. Specifically, we focus on three settings that are still far from well understood: (1) DP-SCO over a constrained and bounded (convex) set in Euclidean space; (2) unconstrained DP-SCO in ℓpd space; (3) DP-SCO with heavy-tailed data over a constrained and bounded set in ℓpd space. For problem (1), for both convex and strongly convex loss functions, we propose methods whose outputs could achieve (expected) excess population risks that are only dependent on the Gaussian width of the constraint set rather than the dimension of the space. Moreover, we also show the bound for strongly convex functions is optimal up to a logarithmic factor. For problems (2) and (3), we propose several novel algorithms and provide the first theoretical results for both cases when 1<p<2 and 2≤ p≤ ∞.

Key facts. Cited by 8 papers in the map (data through 14 Oct 2026). Builds on 22 of its 41 references that are in the map. First posted on arXiv 31 Mar 2023.

Builds on

22 of 41 references.

References · 22

  1. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
  2. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 186
  3. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 153
  4. 2018Differentially Private Empirical Risk Minimization Revisited: Faster and More Generalcited by 128
  5. 2016Relatively-Smooth Convex Optimization by First-Order Methods, and Applicationscited by 108
  6. 2020Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shufflingcited by 96
  7. 2021Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometrycited by 83
  8. 2014A Proximal Stochastic Gradient Method with Progressive Variance Reductioncited by 78
  9. 2020On Differentially Private Stochastic Convex Optimization with Heavy-tailed Datacited by 51
  10. 2021Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 51
  11. 2021Public Data-Assisted Mirror Descent for Private Model Trainingcited by 49
  12. 2021Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Datacited by 47
10 more
  1. 2021High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Datacited by 42
  2. 2019Algorithms of Robust Stochastic Optimization Based on Mirror Descent Methodcited by 32
  3. 2014Private Empirical Risk Minimization Beyond the Worst Case: The Effect of the Constraint Set Geometrycited by 24
  4. 2022Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variancecited by 24
  5. 2021Adapting to Function Difficulty and Growth Conditions in Private Optimizationcited by 20
  6. 2021Faster Rates of Private Stochastic Convex Optimizationcited by 12
  7. 2022Differentially Private ℓ1-norm Linear Regression with Heavy-tailed Datacited by 8
  8. 2022Uniform Stability for First-Order Empirical Risk Minimizationcited by 8
  9. 2016Lower Bounds for Differential Privacy from Gaussian Widthcited by 3
  10. 2022On Private Online Convex Optimization: Optimal Algorithms in ℓp-Geometry and High Dimensional Contextual Banditscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 5; 2026: 2.

8 papers.

  1. 2025Improved Rates of Differentially Private Nonconvex-Strongly-Concave Minimax Optimizationcited by 5
  2. 2025Nearly Optimal Differentially Private ReLU Regressioncited by 3
  3. 2025Second-Order Convergence in Private Stochastic Non-Convex Optimizationcited by 3
  4. 2025Understanding Private Learning From Feature Perspectivecited by 3
  5. 2025Beyond Ordinary Lipschitz Constraints: Differentially Private Stochastic Optimization with Tsybakov Noise Conditioncited by 2
  6. 2026Understanding the Impact of Differentially Private Training on Memorization of Long-Tailed Datacited by 1
  7. 2026Differentially Private Non-convex Distributionally Robust Optimizationcited by 1
  8. 2024Privacy-Preserving Dynamic Assortment Selectioncited by 0