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

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

## 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 (most cited first, 30 of 33)

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [Differentially Private Empirical Risk Minimization Revisited: Faster and More General](https://mlsanity.com/paper/1802.05251/) (2018)
- [High probability generalization bounds for uniformly stable algorithms with nearly optimal rate](https://mlsanity.com/paper/1902.10710/) (2019)
- [Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling](https://mlsanity.com/paper/2012.12803/) (2020)
- [Private Mean Estimation of Heavy-Tailed Distributions](https://mlsanity.com/paper/2002.09464/) (2020)
- [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (2021)
- [Differentially Private Assouad, Fano, and Le Cam](https://mlsanity.com/paper/2004.06830/) (2020)
- [On Differentially Private Stochastic Convex Optimization with Heavy-tailed Data](https://mlsanity.com/paper/2010.11082/) (2020)
- [Fast rates in statistical and online learning](https://mlsanity.com/paper/1507.02592/) (2015)
- [Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data](https://mlsanity.com/paper/2106.01336/) (2021)
- [Private Adaptive Gradient Methods for Convex Optimization](https://mlsanity.com/paper/2106.13756/) (2021)
- [High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data](https://mlsanity.com/paper/2107.11136/) (2021)
- [Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Bandits](https://mlsanity.com/paper/2106.02575/) (2021)
- [Adapting to Function Difficulty and Growth Conditions in Private Optimization](https://mlsanity.com/paper/2108.02391/) (2021)
- [Empirical Risk Minimization in Non-interactive Local Differential Privacy: Efficiency and High Dimensional Case](https://mlsanity.com/paper/1802.04085/) (2018)
- [Propose, Test, Release: Differentially private estimation with high probability](https://mlsanity.com/paper/2002.08774/) (2020)
- [Faster Rates of Private Stochastic Convex Optimization](https://mlsanity.com/paper/2108.00331/) (2021)
- [Fast Rates of ERM and Stochastic Approximation: Adaptive to Error Bound Conditions](https://mlsanity.com/paper/1805.04577/) (2018)
- [Quantizing Heavy-tailed Data in Statistical Estimation: (Near) Minimax Rates, Covariate Quantization, and Uniform Recovery](https://mlsanity.com/paper/2212.14562/) (2022)
- [Differentially Private ℓ1-norm Linear Regression with Heavy-tailed Data](https://mlsanity.com/paper/2201.03204/) (2022)
- [Differentially Private Stochastic Convex Optimization in (Non)-Euclidean Space Revisited](https://mlsanity.com/paper/2303.18047/) (2023)
- [Noninteractive Locally Private Learning of Linear Models via Polynomial Approximations](https://mlsanity.com/paper/1812.06825/) (2018)
- [On Private and Robust Bandits](https://mlsanity.com/paper/2302.02526/) (2023)
- [Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions](https://mlsanity.com/paper/2406.02789/) (2024)
- [Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewards](https://mlsanity.com/paper/2306.01121/) (2023)

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

- [Understanding the Impact of Differentially Private Training on Memorization of Long-Tailed Data](https://mlsanity.com/paper/2602.03872/) (2026)
- [Differentially Private Non-convex Distributionally Robust Optimization](https://mlsanity.com/paper/2602.16155/) (2026)

## 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).