# Uniform Convergence of Gradients for Non-Convex Learning and Optimization

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

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Oct 2018.

## Built on by (most cited first, 30 of 38)

- [Decentralized Federated Averaging](https://mlsanity.com/paper/2104.11375/) (2021)
- [Learning Single-Index Models with Shallow Neural Networks](https://mlsanity.com/paper/2210.15651/) (2022)
- [Faster Rates of Convergence to Stationary Points in Differentially Private Optimization](https://mlsanity.com/paper/2206.00846/) (2022)
- [Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problems](https://mlsanity.com/paper/2206.07082/) (2022)
- [Simple Stochastic and Online Gradient Descent Algorithms for Pairwise Learning](https://mlsanity.com/paper/2111.12050/) (2021)
- [Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Function](https://mlsanity.com/paper/2205.12856/) (2022)
- [Generalization Guarantees for Neural Architecture Search with Train-Validation Split](https://mlsanity.com/paper/2104.14132/) (2021)
- [Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods](https://mlsanity.com/paper/2302.11962/) (2023)
- [Sign-RIP: A Robust Restricted Isometry Property for Low-rank Matrix Recovery](https://mlsanity.com/paper/2102.02969/) (2021)
- [How many Neurons do we need? A refined Analysis for Shallow Networks trained with Gradient Descent](https://mlsanity.com/paper/2309.08044/) (2023)
- [How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimization](https://mlsanity.com/paper/2402.11173/) (2024)
- [Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability](https://mlsanity.com/paper/2209.13262/) (2022)
- [Finite-Sample Analysis of Learning High-Dimensional Single ReLU Neuron](https://mlsanity.com/paper/2303.02255/) (2023)
- [Thinking Outside the Ball: Optimal Learning with Gradient Descent for Generalized Linear Stochastic Convex Optimization](https://mlsanity.com/paper/2202.13328/) (2022)
- [Generalization Bounds of Nonconvex-(Strongly)-Concave Stochastic Minimax Optimization](https://mlsanity.com/paper/2205.14278/) (2022)
- [Replicable Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2509.08660/) (2025)
- [Continuized Acceleration for Quasar Convex Functions in Non-Convex Optimization](https://mlsanity.com/paper/2302.07851/) (2023)
- [High Probability Analysis for Non-Convex Stochastic Optimization with Clipping](https://mlsanity.com/paper/2307.13680/) (2023)
- [Clip Body and Tail Separately: High Probability Guarantees for DPSGD with Heavy Tails](https://mlsanity.com/paper/2405.17529/) (2024)
- [From inexact optimization to learning via gradient concentration](https://mlsanity.com/paper/2106.05397/) (2021)
- [Machine Learning and the Future of Bayesian Computation](https://mlsanity.com/paper/2304.11251/) (2023)
- [Differentially Private Non-Convex Optimization under the KL Condition with Optimal Rates](https://mlsanity.com/paper/2311.13447/) (2023)
- [Failure of uniform laws of large numbers for subdifferentials and beyond](https://mlsanity.com/paper/2511.16568/) (2025)
- [Parallel Momentum Methods Under Biased Gradient Estimations](https://mlsanity.com/paper/2403.00853/) (2024)
- [Stability and Sharper Risk Bounds with Convergence Rate tildeO(1/n2)](https://mlsanity.com/paper/2410.09766/) (2024)
- [Smooth Quasar-Convex Optimization with Constraints](https://mlsanity.com/paper/2510.01943/) (2025)
- [Noisy Truncated SGD: Optimization and Generalization](https://mlsanity.com/paper/2103.00075/) (2021)
- [Improved Learning Rates for Stochastic Optimization](https://mlsanity.com/paper/2107.08686/) (2021)
- [Learning Rates for Nonconvex Pairwise Learning](https://mlsanity.com/paper/2111.05232/) (2021)
- [From Optimization Dynamics to Generalization Bounds via Lojasiewicz Gradient Inequality](https://mlsanity.com/paper/2202.10670/) (2022)

## Abstract (arXiv)

We investigate 1) the rate at which refined properties of the empirical risk---in particular, gradients---converge to their population counterparts in standard non-convex learning tasks, and 2) the consequences of this convergence for optimization. Our analysis follows the tradition of norm-based capacity control. We propose vector-valued Rademacher complexities as a simple, composable, and user-friendly tool to derive dimension-free uniform convergence bounds for gradients in non-convex learning problems. As an application of our techniques, we give a new analysis of batch gradient descent methods for non-convex generalized linear models and non-convex robust regression, showing how to use any algorithm that finds approximate stationary points to obtain optimal sample complexity, even when dimension is high or possibly infinite and multiple passes over the dataset are allowed. Moving to non-smooth models we show----in contrast to the smooth case---that even for a single ReLU it is not possible to obtain dimension-independent convergence rates for gradients in the worst case. On the positive side, it is still possible to obtain dimension-independent rates under a new type of distributional assumption.