# Variance-reduced Clipping for Non-convex Optimization

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 37 references that are in the map.
- First posted on arXiv 2 Mar 2023.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Deep contextualized word representations](https://mlsanity.com/paper/1802.05365/) (2018)
- [Convolutional Sequence to Sequence Learning](https://mlsanity.com/paper/1705.03122/) (2017)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Why gradient clipping accelerates training: A theoretical justification for adaptivity](https://mlsanity.com/paper/1905.11881/) (2019)
- [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)
- [Regularizing and Optimizing LSTM Language Models](https://mlsanity.com/paper/1708.02182/) (2017)
- [Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1603.06160/) (2016)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [Improved Analysis of Clipping Algorithms for Non-convex Optimization](https://mlsanity.com/paper/2010.02519/) (2020)
- [Robustness to Unbounded Smoothness of Generalized SignSGD](https://mlsanity.com/paper/2208.11195/) (2022)
- [Variance Reduction for Faster Non-Convex Optimization](https://mlsanity.com/paper/1603.05643/) (2016)
- [Stochastic Nested Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1806.07811/) (2018)
- [Non-convex Finite-Sum Optimization Via SCSG Methods](https://mlsanity.com/paper/1706.09156/) (2017)
- [On the Ineffectiveness of Variance Reduced Optimization for Deep Learning](https://mlsanity.com/paper/1812.04529/) (2018)
- [Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD](https://mlsanity.com/paper/2302.06570/) (2023)
- [ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/1902.05679/) (2019)
- [Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization](https://mlsanity.com/paper/2206.13033/) (2022)
- [ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computation](https://mlsanity.com/paper/2103.01447/) (2021)
- [Differentially Private Learning with Per-Sample Adaptive Clipping](https://mlsanity.com/paper/2212.00328/) (2022)
- [Stochastic Recursive Gradient Algorithm for Nonconvex Optimization](https://mlsanity.com/paper/1705.07261/) (2017)
- [A Communication-Efficient Distributed Gradient Clipping Algorithm for Training Deep Neural Networks](https://mlsanity.com/paper/2205.05040/) (2022)
- [Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization](https://mlsanity.com/paper/2002.05359/) (2020)
- [Convergence of Stein Variational Gradient Descent under a Weaker Smoothness Condition](https://mlsanity.com/paper/2206.00508/) (2022)
- [Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization](https://mlsanity.com/paper/2211.01851/) (2022)

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

- [Convergence of Adam Under Relaxed Assumptions](https://mlsanity.com/paper/2304.13972/) (2023)
- [Convex and Non-convex Optimization Under Generalized Smoothness](https://mlsanity.com/paper/2306.01264/) (2023)
- [Adam-family Methods for Nonsmooth Optimization with Convergence Guarantees](https://mlsanity.com/paper/2305.03938/) (2023)
- [On Convergence of Adam for Stochastic Optimization under Relaxed Assumptions](https://mlsanity.com/paper/2402.03982/) (2024)
- [Bilevel Optimization under Unbounded Smoothness: A New Algorithm and Convergence Analysis](https://mlsanity.com/paper/2401.09587/) (2024)
- [Revisiting Convergence of AdaGrad with Relaxed Assumptions](https://mlsanity.com/paper/2402.13794/) (2024)
- [On the Convergence of Adam under Non-uniform Smoothness: Separability from SGDM and Beyond](https://mlsanity.com/paper/2403.15146/) (2024)
- [Convergence Guarantees for RMSProp and Adam in Generalized-smooth Non-convex Optimization with Affine Noise Variance](https://mlsanity.com/paper/2404.01436/) (2024)
- [Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under (L0, L1)-Smoothness](https://mlsanity.com/paper/2502.07923/) (2025)
- [Gradient-Variation Online Learning under Generalized Smoothness](https://mlsanity.com/paper/2408.09074/) (2024)
- [Convergence and Privacy of Decentralized Nonconvex Optimization with Gradient Clipping and Communication Compression](https://mlsanity.com/paper/2305.09896/) (2023)
- [An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness](https://mlsanity.com/paper/2409.19212/) (2024)
- [MGDA Converges under Generalized Smoothness, Provably](https://mlsanity.com/paper/2405.19440/) (2024)
- [A Nearly Optimal Single Loop Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness](https://mlsanity.com/paper/2412.20017/) (2024)
- [Adaptive Gradient Normalization and Independent Sampling for (Stochastic) Generalized-Smooth Optimization](https://mlsanity.com/paper/2410.14054/) (2024)
- [Error Feedback under (L0,L1)-Smoothness: Normalization and Momentum](https://mlsanity.com/paper/2410.16871/) (2024)
- [On the Interaction of Batch Noise, Adaptivity, and Compression, under (L0,L1)-Smoothness: An SDE Approach](https://mlsanity.com/paper/2506.00181/) (2025)
- [A Stochastic Quasi-Newton Method for Non-convex Optimization with Non-uniform Smoothness](https://mlsanity.com/paper/2403.15244/) (2024)
- [On the Convergence of Adam-Type Algorithm for Bilevel Optimization under Unbounded Smoothness](https://mlsanity.com/paper/2503.03908/) (2025)
- [Extended convexity and smoothness and their applications in deep learning](https://mlsanity.com/paper/2410.05807/) (2024)
- [Revisiting Convergence: Shuffling Complexity Beyond Lipschitz Smoothness](https://mlsanity.com/paper/2507.08913/) (2025)
- [Provably Convergent Decentralized Optimization over Directed Graphs under Generalized Smoothness](https://mlsanity.com/paper/2601.03566/) (2026)

## Abstract (arXiv)

Gradient clipping is a standard training technique used in deep learning applications such as large-scale language modeling to mitigate exploding gradients. Recent experimental studies have demonstrated a fairly special behavior in the smoothness of the training objective along its trajectory when trained with gradient clipping. That is, the smoothness grows with the gradient norm. This is in clear contrast to the well-established assumption in folklore non-convex optimization, a.k.a. L--smoothness, where the smoothness is assumed to be bounded by a constant L globally. The recently introduced (L0,L1)--smoothness is a more relaxed notion that captures such behavior in non-convex optimization. In particular, it has been shown that under this relaxed smoothness assumption, SGD with clipping requires O(ε-4) stochastic gradient computations to find an ε--stationary solution. In this paper, we employ a variance reduction technique, namely SPIDER, and demonstrate that for a carefully designed learning rate, this complexity is improved to O(ε-3) which is order-optimal. Our designed learning rate comprises the clipping technique to mitigate the growing smoothness. Moreover, when the objective function is the average of n components, we improve the existing O(nε-2) bound on the stochastic gradient complexity to O(√n ε-2 + n), which is order-optimal as well. In addition to being theoretically optimal, SPIDER with our designed parameters demonstrates comparable empirical performance against variance-reduced methods such as SVRG and SARAH in several vision tasks.