# Differentially Private SGD with Non-Smooth Losses

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 50 references that are in the map.
- First posted on arXiv 22 Jan 2021.

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

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/1610.05820/) (2016)
- [The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networks](https://mlsanity.com/paper/1802.08232/) (2018)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [Collecting Telemetry Data Privately](https://mlsanity.com/paper/1712.01524/) (2017)
- [Concentrated Differential Privacy](https://mlsanity.com/paper/1603.01887/) (2016)
- [Differentially Private Empirical Risk Minimization Revisited: Faster and More General](https://mlsanity.com/paper/1802.05251/) (2018)
- [Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08157/) (2020)
- [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013)
- [Sharper bounds for uniformly stable algorithms](https://mlsanity.com/paper/1910.07833/) (2019)
- [Algorithmic stability and hypothesis complexity](https://mlsanity.com/paper/1702.08712/) (2017)
- [Simultaneous Model Selection and Optimization through Parameter-free Stochastic Learning](https://mlsanity.com/paper/1406.3816/) (2014)
- [Unregularized Online Learning Algorithms with General Loss Functions](https://mlsanity.com/paper/1503.00623/) (2015)
- [Optimal Rates for Multi-pass Stochastic Gradient Methods](https://mlsanity.com/paper/1605.08882/) (2016)
- [Learning from Data with Heterogeneous Noise using SGD](https://mlsanity.com/paper/1412.5617/) (2014)

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

- [Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization](https://mlsanity.com/paper/2206.13033/) (2022)
- [Differentially Private SGDA for Minimax Problems](https://mlsanity.com/paper/2201.09046/) (2022)
- [Differentially Private Learning with Per-Sample Adaptive Clipping](https://mlsanity.com/paper/2212.00328/) (2022)
- [Stability and Generalization for Markov Chain Stochastic Gradient Methods](https://mlsanity.com/paper/2209.08005/) (2022)
- [Tangent Transformers for Composition, Privacy and Removal](https://mlsanity.com/paper/2307.08122/) (2023)
- [Differentially Private Coordinate Descent for Composite Empirical Risk Minimization](https://mlsanity.com/paper/2110.11688/) (2021)
- [Minibatch and Local SGD: Algorithmic Stability and Linear Speedup in Generalization](https://mlsanity.com/paper/2310.01139/) (2023)
- [Privacy Auditing Synthetic Data Release through Local Likelihood Attacks](https://mlsanity.com/paper/2508.21146/) (2025)
- [Stability and Generalization for Randomized Coordinate Descent](https://mlsanity.com/paper/2108.07414/) (2021)
- [High-Dimensional Private Empirical Risk Minimization by Greedy Coordinate Descent](https://mlsanity.com/paper/2207.01560/) (2022)
- [Characterizing the Training Dynamics of Private Fine-tuning with Langevin diffusion](https://mlsanity.com/paper/2402.18905/) (2024)
- [Sharper Utility Bounds for Differentially Private Models](https://mlsanity.com/paper/2204.10536/) (2022)
- [Stability and Generalization of Differentially Private Minimax Problems](https://mlsanity.com/paper/2204.04858/) (2022)
- [Statistical Inference for Differentially Private Stochastic Gradient Descent](https://mlsanity.com/paper/2507.20560/) (2025)
- [Differentially Private Stochastic Gradient Descent with Low-Noise](https://mlsanity.com/paper/2209.04188/) (2022)
- [Noise is All You Need: Private Second-Order Convergence of Noisy SGD](https://mlsanity.com/paper/2410.06878/) (2024)
- [Enhancing DP-SGD through Non-monotonous Adaptive Scaling Gradient Weight](https://mlsanity.com/paper/2411.03059/) (2024)
- [Optimization, Generalization and Differential Privacy Bounds for Gradient Descent on Kolmogorov-Arnold Networks](https://mlsanity.com/paper/2601.22409/) (2026)
- [Neural Network-Based Parameter Estimation for Non-Autonomous Differential Equations with Discontinuous Signals](https://mlsanity.com/paper/2507.06267/) (2025)
- [Enhancing Differentially Private Linear Regression via Public Second-Moment](https://mlsanity.com/paper/2508.18037/) (2025)
- [Balancing Utility and Privacy: Dynamically Private SGD with Random Projection](https://mlsanity.com/paper/2509.09485/) (2025)
- [Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise and H"older Smoothness](https://mlsanity.com/paper/2609.12785/) (2026)

## Abstract (arXiv)

In this paper, we are concerned with differentially private stochastic gradient descent (SGD) algorithms in the setting of stochastic convex optimization (SCO). Most of the existing work requires the loss to be Lipschitz continuous and strongly smooth, and the model parameter to be uniformly bounded. However, these assumptions are restrictive as many popular losses violate these conditions including the hinge loss for SVM, the absolute loss in robust regression, and even the least square loss in an unbounded domain. We significantly relax these restrictive assumptions and establish privacy and generalization (utility) guarantees for private SGD algorithms using output and gradient perturbations associated with non-smooth convex losses. Specifically, the loss function is relaxed to have an α-H"older continuous gradient (referred to as α-H"older smoothness) which instantiates the Lipschitz continuity (α=0) and the strong smoothness (α=1). We prove that noisy SGD with α-H"older smooth losses using gradient perturbation can guarantee (ε,δ)-differential privacy (DP) and attain optimal excess population risk OBig(frac√dlog(1/δ)nε+frac1√nBig), up to logarithmic terms, with the gradient complexity  O( n2-αover 1+α+ n). This shows an important trade-off between α-H"older smoothness of the loss and the computational complexity for private SGD with statistically optimal performance. In particular, our results indicate that α-H"older smoothness with α≥ 1/2 is sufficient to guarantee (ε,δ)-DP of noisy SGD algorithms while achieving optimal excess risk with the linear gradient complexity O(n).