# How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimization

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 45 of its 64 references that are in the map.
- First posted on arXiv 17 Feb 2024.

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

- [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)
- [Extracting Training Data from Large Language Models](https://mlsanity.com/paper/2012.07805/) (2020)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Large Language Models Can Be Strong Differentially Private Learners](https://mlsanity.com/paper/2110.05679/) (2021)
- [Differentially Private Fine-tuning of Language Models](https://mlsanity.com/paper/2110.06500/) (2021)
- [Loss landscapes and optimization in over-parameterized non-linear systems and neural networks](https://mlsanity.com/paper/2003.00307/) (2020)
- [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)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [An Alternative View: When Does SGD Escape Local Minima?](https://mlsanity.com/paper/1802.06175/) (2018)
- [A Geometric Analysis of Phase Retrieval](https://mlsanity.com/paper/1602.06664/) (2016)
- [The Landscape of Empirical Risk for Non-convex Losses](https://mlsanity.com/paper/1607.06534/) (2016)
- [Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry](https://mlsanity.com/paper/2103.01516/) (2021)
- [Fingerprinting Codes and the Price of Approximate Differential Privacy](https://mlsanity.com/paper/1311.3158/) (2013)
- [Gradient Descent Learns Linear Dynamical Systems](https://mlsanity.com/paper/1609.05191/) (2016)
- [SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation](https://mlsanity.com/paper/2006.10311/) (2020)
- [Efficient Private ERM for Smooth Objectives](https://mlsanity.com/paper/1703.09947/) (2017)
- [Robust Bi-Tempered Logistic Loss Based on Bregman Divergences](https://mlsanity.com/paper/1906.03361/) (2019)
- [How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD](https://mlsanity.com/paper/1801.02982/) (2018)
- [Between Pure and Approximate Differential Privacy](https://mlsanity.com/paper/1501.06095/) (2015)
- [Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2103.01278/) (2021)
- [Public Data-Assisted Mirror Descent for Private Model Training](https://mlsanity.com/paper/2112.00193/) (2021)
- [Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings](https://mlsanity.com/paper/2107.05585/) (2021)
- [SGD Converges to Global Minimum in Deep Learning via Star-convex Path](https://mlsanity.com/paper/1901.00451/) (2019)
- [Uniform Convergence of Gradients for Non-Convex Learning and Optimization](https://mlsanity.com/paper/1810.11059/) (2018)
- [Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond](https://mlsanity.com/paper/1906.11985/) (2019)
- [On exponential convergence of SGD in non-convex over-parametrized learning](https://mlsanity.com/paper/1811.02564/) (2018)
- [Faster Rates of Convergence to Stationary Points in Differentially Private Optimization](https://mlsanity.com/paper/2206.00846/) (2022)

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

- [Private Heterogeneous Federated Learning Without a Trusted Server Revisited: Error-Optimal and Communication-Efficient Algorithms for Convex Losses](https://mlsanity.com/paper/2407.09690/) (2024)
- [Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2410.05880/) (2024)
- [Faster Algorithms for User-Level Private Stochastic Convex Optimization](https://mlsanity.com/paper/2410.18391/) (2024)
- [Convex Approximation of Two-Layer ReLU Networks for Hidden State Differential Privacy](https://mlsanity.com/paper/2407.04884/) (2024)
- [Differentially Private Bilevel Optimization](https://mlsanity.com/paper/2409.19800/) (2024)
- [Adaptive Batch Size for Privately Finding Second-Order Stationary Points](https://mlsanity.com/paper/2410.07502/) (2024)
- [Memory-Efficient Differentially Private Training with Gradient Random Projection](https://mlsanity.com/paper/2506.15588/) (2025)
- [Differentially Private Bilevel Optimization: Efficient Algorithms with Near-Optimal Rates](https://mlsanity.com/paper/2506.12994/) (2025)
- [Optimization, Generalization and Differential Privacy Bounds for Gradient Descent on Kolmogorov-Arnold Networks](https://mlsanity.com/paper/2601.22409/) (2026)
- [On the Inherent Privacy of Zeroth Order Projected Gradient Descent](https://mlsanity.com/paper/2507.05610/) (2025)

## Abstract (arXiv)

We provide a simple and flexible framework for designing differentially private algorithms to find approximate stationary points of non-convex loss functions. Our framework is based on using a private approximate risk minimizer to "warm start" another private algorithm for finding stationary points. We use this framework to obtain improved, and sometimes optimal, rates for several classes of non-convex loss functions. First, we obtain improved rates for finding stationary points of smooth non-convex empirical loss functions. Second, we specialize to quasar-convex functions, which generalize star-convex functions and arise in learning dynamical systems and training some neural nets. We achieve the optimal rate for this class. Third, we give an optimal algorithm for finding stationary points of functions satisfying the Kurdyka-Lojasiewicz (KL) condition. For example, over-parameterized neural networks often satisfy this condition. Fourth, we provide new state-of-the-art rates for stationary points of non-convex population loss functions. Fifth, we obtain improved rates for non-convex generalized linear models. A modification of our algorithm achieves nearly the same rates for second-order stationary points of functions with Lipschitz Hessian, improving over the previous state-of-the-art for each of the above problems.