Beyond Convexity: Stochastic Quasi-Convex Optimization

By Elad Hazan, Kfir Yehuda Levy, Shai Shalev-Shwartz. 2015

207 citations recorded by the source corpus.

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 concept 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.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Management Science and Operations Research

Citations in the corpus

AutoML-Zero: Evolving Machine Learning Algorithms From Scratch (2020, methodology): “The normalized gradient is a commonly used heuristic in non-convex optimization [29, 41], which could help with the vanishing and exploding gradient problem [98, 63].”
Stochastic Variance Reduction for Nonconvex Optimization (2016, background): “Finally, we note another interesting example, stochastic optimization of locally quasi-convex functions (Hazan et al., 2015), wherein actually a O (1 / 2 ) convergence in function value is shown.”
Sampling Matters in Deep Embedding Learning (2017, background): “[12, 20] for more discussions about the benefits of using gradients of a fixed length.”
Online Batch Selection for Faster Training of Neural Networks (2015, methodology): “Following the notation of Hazan et al. (2015), we deﬁne a loss function ψ : R n → R for each training datapoint; the distribution of training datapoints then induces a Algorithm 1 The original AdaDelta algorithm 1: given ρ = 0 .”
The Power of Normalization: Faster Evasion of Saddle Points (2016, background): “Recently, a stochastic version of NGD was explored in the context of stochastic quasi-convex optimization, Hazan et al. (2015).”
SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator (2018, methodology): “However, NGD has been less popular due to its requirement of accessing the full gradient and its norm at each update.”
Differentially Private Empirical Risk Minimization Revisited: Faster and More General (2018, background): “It will be interesting to know the bound for functions satisfying other conditions (such as general Gradient-dominated functions [24], quasi-convex and locally-Lipschitz in [16]) under the differential privacy model.”
Why Gradient Clipping Accelerates Training: A Theoretical Justification for Adaptivity (2019, background): “Hazan et al. (2015) studied the convergence of normalized gradient descent for quasi-convex functions.”
Momentum Improves Normalized SGD (2020, methodology): “In order to fix this, one must decrease the variance in the stochastic gradient oracle by employing a very large batch size, usually on the order of T (You et al., 2019; Hazan et al., 2015).”
BLOCK-NORMALIZED GRADIENT METHOD: AN EMPIRICAL STUDY FOR TRAINING DEEP NEURAL NETWORK (2018, methodology): “In this paper, we propose a generic framework using the mini-batch stochastic normalized gradient as the updating direction (like [Hazan et al., 2015, Levy, 2016]) and the step size is either constant or adaptive to each coordinate as in [Duchi et al., 2011, Kingma and Ba, 2014].”
Why ADAM Beats SGD for Attention Models (2019, background): “Another direction of related work is normalized gradient descent, which has been studied for quasi-convex and non-convex settings (Levy, 2016; Hazan et al., 2015; Zhang et al., 2019).”
Theoretical properties of the global optimizer of two layer neural network (2017, background): “In fact, several authors have shown that for such neural networks with monotone activations, gradient based methods will converge to the global optimum for diﬀerent assumptions and settings [17, 11, 12, 13].”
Why are Adaptive Methods Good for Attention Models? (2020, background): “Another direction of related work is normalized gradient descent, which has been studied for quasi-convex and non-convex settings [12, 15].”
Adaptive Methods for Nonconvex Optimization (2018, background): “Normalized variants of SGD have been studied recently in nonconvex settings [10, 3].”
Normalized Direction-preserving Adam (2017, background): “This, and other similar schemes (Hazan et al., 2015; Yu et al., 2017) make the optimization less susceptible to vanishing and exploding gradients.”