mlsanityData to 14 Oct 2026

Beyond Ordinary Lipschitz Constraints: Differentially Private Stochastic Optimization with Tsybakov Noise Condition

arXiv 2509.04668 ↗First posted 4 Sep 2025cs.LGcited by 2

Not on the map. Why?

Abstract (arXiv)

We study Stochastic Convex Optimization in the Differential Privacy model (DP-SCO). Unlike previous studies, here we assume the population risk function satisfies the Tsybakov Noise Condition (TNC) with some parameter θ>1, where the Lipschitz constant of the loss could be extremely large or even unbounded, but the ℓ2-norm gradient of the loss has bounded k-th moment with k≥ 2. For the Lipschitz case with θ≥ 2, we first propose an (varepsilon, δ)-DP algorithm whose utility bound is TildeOleft(left(tilder2k(frac1√n+(frac√dnvarepsilon))^frack-1kright)^fracθθ-1right) in high probability, where n is the sample size, d is the model dimension, and tilder2k is a term that only depends on the 2k-th moment of the gradient. It is notable that such an upper bound is independent of the Lipschitz constant. We then extend to the case where θ≥ barθ> 1 for some known constant barθ. Moreover, when the privacy budget varepsilon is small enough, we show an upper bound of tildeOleft(left(tilderk(frac1√n+(frac√dnvarepsilon))^frack-1kright)^fracθθ-1right) even if the loss function is not Lipschitz. For the lower bound, we show that for any θ≥ 2, the private minimax rate for ρ-zero Concentrated Differential Privacy is lower bounded by Omegaleft(left(tilderk(frac1√n+(frac√dn√ρ))^frack-1kright)^fracθθ-1right).

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 33 of its 56 references that are in the map. First posted on arXiv 4 Sep 2025.

Builds on

33 of 56 references.

References · 33

  1. 2016Deep Learning with Differential Privacycited by 2,728
  2. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
  3. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
  4. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 346
  5. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 186
  6. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 153
  7. 2018Differentially Private Empirical Risk Minimization Revisited: Faster and More Generalcited by 128
  8. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 98
  9. 2020Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shufflingcited by 96
  10. 2020Private Mean Estimation of Heavy-Tailed Distributionscited by 73
  11. 2021Robust and Differentially Private Mean Estimationcited by 66
  12. 2020Differentially Private Assouad, Fano, and Le Camcited by 55
21 more
  1. 2020On Differentially Private Stochastic Convex Optimization with Heavy-tailed Datacited by 51
  2. 2015Fast rates in statistical and online learningcited by 47
  3. 2021Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Datacited by 47
  4. 2021Private Adaptive Gradient Methods for Convex Optimizationcited by 46
  5. 2021High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Datacited by 42
  6. 2021Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Banditscited by 25
  7. 2021Adapting to Function Difficulty and Growth Conditions in Private Optimizationcited by 20
  8. 2018Empirical Risk Minimization in Non-interactive Local Differential Privacy: Efficiency and High Dimensional Casecited by 19
  9. 2020Propose, Test, Release: Differentially private estimation with high probabilitycited by 15
  10. 2021Faster Rates of Private Stochastic Convex Optimizationcited by 12
  11. 2018Fast Rates of ERM and Stochastic Approximation: Adaptive to Error Bound Conditionscited by 9
  12. 2022Quantizing Heavy-tailed Data in Statistical Estimation: (Near) Minimax Rates, Covariate Quantization, and Uniform Recoverycited by 9
  13. 2022Differentially Private ℓ1-norm Linear Regression with Heavy-tailed Datacited by 8
  14. 2023Differentially Private Stochastic Convex Optimization in (Non)-Euclidean Space Revisitedcited by 8
  15. 2018Noninteractive Locally Private Learning of Linear Models via Polynomial Approximationscited by 7
  16. 2023On Private and Robust Banditscited by 6
  17. 2024Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductionscited by 6
  18. 2023Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewardscited by 4
  19. 2025Nearly Optimal Differentially Private ReLU Regressioncited by 3
  20. 2015Algorithmic Connections Between Active Learning and Stochastic Convex Optimizationcited by 1
  21. 2025Differentially Private Sparse Linear Regression with Heavy-tailed Responsescited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Understanding the Impact of Differentially Private Training on Memorization of Long-Tailed Datacited by 1
  2. 2026Differentially Private Non-convex Distributionally Robust Optimizationcited by 1