# Momentum Aggregation for Private Non-convex ERM

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 53 references that are in the map.
- First posted on arXiv 12 Oct 2022.

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

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences](https://mlsanity.com/paper/1807.01647/) (2018)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Practical and Private (Deep) Learning without Sampling or Shuffling](https://mlsanity.com/paper/2103.00039/) (2021)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [Momentum Improves Normalized SGD](https://mlsanity.com/paper/2002.03305/) (2020)
- [Differentially Private Empirical Risk Minimization Revisited: Faster and More General](https://mlsanity.com/paper/1802.05251/) (2018)
- [Random Reshuffling: Simple Analysis with Vast Improvements](https://mlsanity.com/paper/2006.05988/) (2020)
- [Strongly Adaptive Online Learning](https://mlsanity.com/paper/1502.07073/) (2015)
- [Privacy Amplification by Iteration](https://mlsanity.com/paper/1808.06651/) (2018)
- [Stochastic Nested Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1806.07811/) (2018)
- [Efficient Private ERM for Smooth Objectives](https://mlsanity.com/paper/1703.09947/) (2017)
- [Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2103.01278/) (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)
- [Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations](https://mlsanity.com/paper/2006.13476/) (2020)
- [Efficient Privacy-Preserving Stochastic Nonconvex Optimization](https://mlsanity.com/paper/1910.13659/) (2019)
- [Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds](https://mlsanity.com/paper/2006.13501/) (2020)
- [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)
- [Tight Dimension Independent Lower Bound on the Expected Convergence Rate for Diminishing Step Sizes in SGD](https://mlsanity.com/paper/1810.04723/) (2018)
- [Better SGD using Second-order Momentum](https://mlsanity.com/paper/2103.03265/) (2021)
- [Applications of artificial intelligence in drug development using real-world data](https://mlsanity.com/paper/2101.08904/) (2021)

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

- [DPZero: Private Fine-Tuning of Language Models without Backpropagation](https://mlsanity.com/paper/2310.09639/) (2023)
- [Gradient Descent with Linearly Correlated Noise: Theory and Applications to Differential Privacy](https://mlsanity.com/paper/2302.01463/) (2023)
- [Private (Stochastic) Non-Convex Optimization Revisited: Second-Order Stationary Points and Excess Risks](https://mlsanity.com/paper/2302.09699/) (2023)
- [DIFF2: Differential Private Optimization via Gradient Differences for Nonconvex Distributed Learning](https://mlsanity.com/paper/2302.03884/) (2023)
- [How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimization](https://mlsanity.com/paper/2402.11173/) (2024)
- [Private Zeroth-Order Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2406.19579/) (2024)
- [Improved Rates of Differentially Private Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2503.18317/) (2025)
- [Reevaluating Theoretical Analysis Methods for Optimization in Deep Learning](https://mlsanity.com/paper/2407.01825/) (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)

## Abstract (arXiv)

We introduce new algorithms and convergence guarantees for privacy-preserving non-convex Empirical Risk Minimization (ERM) on smooth d-dimensional objectives. We develop an improved sensitivity analysis of stochastic gradient descent on smooth objectives that exploits the recurrence of examples in different epochs. By combining this new approach with recent analysis of momentum with private aggregation techniques, we provide an (ε,δ)-differential private algorithm that finds a gradient of norm tilde Oleft(fracd1/3(ε N)2/3right) in Oleft(fracN7/3ε4/3d2/3right) gradient evaluations, improving the previous best gradient bound of tilde Oleft(fracd1/4√ε Nright).