# Beyond Convexity: Stochastic Quasi-Convex Optimization

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

## Key facts

- Cited by 76 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jul 2015.

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

- [Training Deep Learning Models with Norm-Constrained LMOs](https://mlsanity.com/paper/2502.07529/) (2025)
- [Revisiting Gradient Clipping: Stochastic bias and tight convergence guarantees](https://mlsanity.com/paper/2305.01588/) (2023)
- [Robustness to Unbounded Smoothness of Generalized SignSGD](https://mlsanity.com/paper/2208.11195/) (2022)
- [MARS: Unleashing the Power of Variance Reduction for Training Large Models](https://mlsanity.com/paper/2411.10438/) (2024)
- [Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies](https://mlsanity.com/paper/2302.01734/) (2023)
- [Clipped Hyperbolic Classifiers Are Super-Hyperbolic Classifiers](https://mlsanity.com/paper/2107.11472/) (2021)
- [Toward Understanding Why Adam Converges Faster Than SGD for Transformers](https://mlsanity.com/paper/2306.00204/) (2023)
- [From Gradient Clipping to Normalization for Heavy Tailed SGD](https://mlsanity.com/paper/2410.13849/) (2024)
- [Leveraging Non-uniformity in First-order Non-convex Optimization](https://mlsanity.com/paper/2105.06072/) (2021)
- [Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping](https://mlsanity.com/paper/2412.19529/) (2024)
- [Implicit Bias of Spectral Descent and Muon on Multiclass Separable Data](https://mlsanity.com/paper/2502.04664/) (2025)
- [Mitigating Memorization of Noisy Labels by Clipping the Model Prediction](https://mlsanity.com/paper/2212.04055/) (2022)
- [Stability and Convergence of Stochastic Gradient Clipping: Beyond Lipschitz Continuity and Smoothness](https://mlsanity.com/paper/2102.06489/) (2021)
- [DoWG Unleashed: An Efficient Universal Parameter-Free Gradient Descent Method](https://mlsanity.com/paper/2305.16284/) (2023)
- [Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature](https://mlsanity.com/paper/2102.04168/) (2021)
- [Implicit Bias and Fast Convergence Rates for Self-attention](https://mlsanity.com/paper/2402.05738/) (2024)
- [Robust Training of Neural Networks Using Scale Invariant Architectures](https://mlsanity.com/paper/2202.00980/) (2022)
- [Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methods](https://mlsanity.com/paper/2305.12475/) (2023)
- [On the Convergence of Step Decay Step-Size for Stochastic Optimization](https://mlsanity.com/paper/2102.09393/) (2021)
- [A Communication-Efficient Distributed Gradient Clipping Algorithm for Training Deep Neural Networks](https://mlsanity.com/paper/2205.05040/) (2022)
- [Analyzing and Improving the Optimization Landscape of Noise-Contrastive Estimation](https://mlsanity.com/paper/2110.11271/) (2021)
- [Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise](https://mlsanity.com/paper/2206.01095/) (2022)
- [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)
- [Preconditioned Norms: A Unified Framework for Steepest Descent, Quasi-Newton and Adaptive Methods](https://mlsanity.com/paper/2510.10777/) (2025)
- [MARS-M: When Variance Reduction Meets Matrices](https://mlsanity.com/paper/2510.21800/) (2025)
- [Deriving Hyperparameter Scaling Laws via Modern Optimization Theory](https://mlsanity.com/paper/2603.15958/) (2026)
- [Gradient Multi-Normalization for Stateless and Scalable LLM Training](https://mlsanity.com/paper/2502.06742/) (2025)
- [Why Do Local Methods Solve Nonconvex Problems?](https://mlsanity.com/paper/2103.13462/) (2021)
- [EPISODE: Episodic Gradient Clipping with Periodic Resampled Corrections for Federated Learning with Heterogeneous Data](https://mlsanity.com/paper/2302.07155/) (2023)
- [High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise](https://mlsanity.com/paper/2310.18784/) (2023)

## Abstract (arXiv)

Stochastic convex optimization is a basic and well studied primitive in machine learning. It is well known that convex and Lipschitz functions can be minimized efficiently using Stochastic Gradient Descent (SGD). The Normalized Gradient Descent (NGD) algorithm, is an adaptation of Gradient Descent, which updates according to the direction of the gradients, rather than the gradients themselves. In this paper we analyze a stochastic version of NGD and prove its convergence to a global minimum for a wider class of functions: we require the functions to be quasi-convex and locally-Lipschitz. Quasi-convexity broadens the con- cept of unimodality to multidimensions and allows for certain types of saddle points, which are a known hurdle for first-order optimization methods such as gradient descent. Locally-Lipschitz functions are only required to be Lipschitz in a small region around the optimum. This assumption circumvents gradient explosion, which is another known hurdle for gradient descent variants. Interestingly, unlike the vanilla SGD algorithm, the stochastic normalized gradient descent algorithm provably requires a minimal minibatch size.