# Beyond Uniform Lipschitz Condition in Differentially Private Optimization

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 70 references that are in the map.
- First posted on arXiv 21 Jun 2022.

## Builds on (most cited first, 30 of 31)

- [DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter](https://mlsanity.com/paper/1910.01108/) (2019)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Opacus: User-Friendly Differential Privacy Library in PyTorch](https://mlsanity.com/paper/2109.12298/) (2021)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [Unlocking High-Accuracy Differentially Private Image Classification through Scale](https://mlsanity.com/paper/2204.13650/) (2022)
- [Differentially Private Learning with Adaptive Clipping](https://mlsanity.com/paper/1905.03871/) (2019)
- [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)
- [The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning](https://mlsanity.com/paper/1712.06559/) (2017)
- [Understanding Gradient Clipping in Private SGD: A Geometric Perspective](https://mlsanity.com/paper/2006.15429/) (2020)
- [Differentially Private Empirical Risk Minimization Revisited: Faster and More General](https://mlsanity.com/paper/1802.05251/) (2018)
- [Tempered Sigmoid Activations for Deep Learning with Differential Privacy](https://mlsanity.com/paper/2007.14191/) (2020)
- [Hyperparameter Tuning with Renyi Differential Privacy](https://mlsanity.com/paper/2110.03620/) (2021)
- [Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry](https://mlsanity.com/paper/2103.01516/) (2021)
- [Understanding Clipping for Federated Learning: Convergence and Client-Level Differential Privacy](https://mlsanity.com/paper/2106.13673/) (2021)
- [Efficient Private ERM for Smooth Objectives](https://mlsanity.com/paper/1703.09947/) (2017)
- [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)
- [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)
- [Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings](https://mlsanity.com/paper/2107.05585/) (2021)
- [From error bounds to the complexity of first-order descent methods for convex functions](https://mlsanity.com/paper/1510.08234/) (2015)
- [High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data](https://mlsanity.com/paper/2107.11136/) (2021)
- [Large Scale Transfer Learning for Differentially Private Image Classification](https://mlsanity.com/paper/2205.02973/) (2022)
- [Subgradient methods for sharp weakly convex functions](https://mlsanity.com/paper/1803.02461/) (2018)
- [Faster Rates of Convergence to Stationary Points in Differentially Private Optimization](https://mlsanity.com/paper/2206.00846/) (2022)
- [Dynamic Differential-Privacy Preserving SGD](https://mlsanity.com/paper/2111.00173/) (2021)
- [Efficient Privacy-Preserving Stochastic Nonconvex Optimization](https://mlsanity.com/paper/1910.13659/) (2019)
- [Private Empirical Risk Minimization Beyond the Worst Case: The Effect of the Constraint Set Geometry](https://mlsanity.com/paper/1411.5417/) (2014)
- [Private Non-smooth Empirical Risk Minimization and Stochastic Convex Optimization in Subquadratic Steps](https://mlsanity.com/paper/2103.15352/) (2021)

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

- [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy](https://mlsanity.com/paper/2303.00654/) (2023)
- [Revisiting Gradient Clipping: Stochastic bias and tight convergence guarantees](https://mlsanity.com/paper/2305.01588/) (2023)
- [Gradient Descent with Linearly Correlated Noise: Theory and Applications to Differential Privacy](https://mlsanity.com/paper/2302.01463/) (2023)
- [DIFF2: Differential Private Optimization via Gradient Differences for Nonconvex Distributed Learning](https://mlsanity.com/paper/2302.03884/) (2023)
- [Convergence and Privacy of Decentralized Nonconvex Optimization with Gradient Clipping and Communication Compression](https://mlsanity.com/paper/2305.09896/) (2023)
- [BadGD: A unified data-centric framework to identify gradient descent vulnerabilities](https://mlsanity.com/paper/2405.15979/) (2024)
- [Differentially Private Federated Learning With Time-Adaptive Privacy Spending](https://mlsanity.com/paper/2502.18706/) (2025)
- [Private Stochastic Optimization With Large Worst-Case Lipschitz Parameter](https://mlsanity.com/paper/2209.07403/) (2022)
- [Towards Understanding Generalization and Stability Gaps between Centralized and Decentralized Federated Learning](https://mlsanity.com/paper/2310.03461/) (2023)
- [Data Deletion for Linear Regression with Noisy SGD](https://mlsanity.com/paper/2410.09311/) (2024)
- [Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates](https://mlsanity.com/paper/2408.09891/) (2024)
- [On Theoretical Limits of Learning with Label Differential Privacy](https://mlsanity.com/paper/2502.14309/) (2025)
- [Scaled Supervision is an Implicit Lipschitz Regularizer](https://mlsanity.com/paper/2503.14813/) (2025)
- [Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite Lp Moments](https://mlsanity.com/paper/2606.06855/) (2026)
- [Efficient Private SCO for Heavy-Tailed Data via Averaged Clipping](https://mlsanity.com/paper/2206.13011/) (2022)
- [Private Blind Model Averaging - Distributed, Non-interactive, and Convergent](https://mlsanity.com/paper/2211.02003/) (2022)
- [Balancing Utility and Privacy: Dynamically Private SGD with Random Projection](https://mlsanity.com/paper/2509.09485/) (2025)
- [Amplified Patch-Level Differential Privacy for Free via Random Cropping](https://mlsanity.com/paper/2603.24695/) (2026)
- [Rethinking the Personalized Relaxed Initialization in the Federated Learning: Consistency and Generalization](https://mlsanity.com/paper/2604.12768/) (2026)

## Abstract (arXiv)

Most prior results on differentially private stochastic gradient descent (DP-SGD) are derived under the simplistic assumption of uniform Lipschitzness, i.e., the per-sample gradients are uniformly bounded. We generalize uniform Lipschitzness by assuming that the per-sample gradients have sample-dependent upper bounds, i.e., per-sample Lipschitz constants, which themselves may be unbounded. We provide principled guidance on choosing the clip norm in DP-SGD for convex over-parameterized settings satisfying our general version of Lipschitzness when the per-sample Lipschitz constants are bounded; specifically, we recommend tuning the clip norm only till values up to the minimum per-sample Lipschitz constant. This finds application in the private training of a softmax layer on top of a deep network pre-trained on public data. We verify the efficacy of our recommendation via experiments on 8 datasets. Furthermore, we provide new convergence results for DP-SGD on convex and nonconvex functions when the Lipschitz constants are unbounded but have bounded moments, i.e., they are heavy-tailed.