Natasha: Faster Non-Convex Stochastic Optimization Via Strongly Non-Convex Parameter

Introduction

We study the problem of composite nonconvex minimization:

where each $f_{i}(x)$ is nonconvex but smooth, and $\psi(\cdot)$ is proper convex, possibly nonsmooth. We are interested in finding a point $x$ that is an approximate local minimum of $F(x)$.

The finite-sum structure $f(x)=\frac{1}{n}\sum_{i=1}^{n}f_{i}(x)$ arises prominently in large-scale machine learning tasks. In particular, when minimizing loss over a training set, each example $i$ corresponds to one loss function $f_{i}(\cdot)$ in the summation. This finite-sum structure allows one to perform stochastic gradient descent with respect to a random $\nabla f_{i}(x)$.

The so-called proximal term $\psi(x)$ adds more generality to the model. For instance, if $\psi(x)$ is the indicator function of a convex set, then problem (1.1) becomes constraint minimization; if $\psi(x)=\|x\|_{1}$, then we can allow problem (1.1) to perform feature selection. In general, $\psi(x)$ has to be a simple function where the projection operation $\operatornamewithlimits{arg\,min}_{x}\{\psi(x)+\frac{1}{2\eta}\|x-x_{0}\|^{2}\}$ is efficiently computable. At a first reading of this paper, one can assume $\psi(x)\equiv 0$ for simplicity.

Many nonconvex machine learning problems fall into problem (1.1). Most notably, training deep neural networks and classifications with sigmoid loss correspond to (1.1) where neither $f_{i}(x)$ or $f(x)$ is convex. However, our understanding to this challenging nonconvex problem is very limited.

Let $L$ be the smoothness parameter for each $f_{i}(x)$, meaning all the eigenvalues of $\nabla^{2}f_{i}(x)$ lie in $[-L,L]$.This definition also applies to functions $f(x)$ that are not twice differentiable, see Section LABEL:sec:pre for details. We denote by $\sigma\in[0,L]$ the bounded nonconvexity parameter of $f(x)=\frac{1}{n}\sum_{i=1}^{n}f_{i}(x)$, meaning that Previous authors also refer to this notion as “approximate convex”, “almost convex”, “hypo-convex”, “semi-convex”, or “weakly-convex.” We call it $\sigma$-nonconvex to stress the point that $\sigma$ can be as large as $L$ (recall any $L$-smooth function is automatically $L$-nonconvex). In our earlier versions of this paper, we have called $\sigma$ the “strong nonconvexity” parameter, but were told by some readers that it is a bad notion. We have renamed it since then, but kept the paper title unchanged.

all the eigenvalues of $\nabla^{2}f(x)$ lie in $[-\sigma,L]$.

We say $f(x)$ is of $\sigma$-bounded nonconvexity (or just $\sigma$-nonconvex for short). This parameter $\sigma$ should be reminiscent of the strong-convexity parameter $\mu$ for convex optimization, where all the eigenvalues of $\nabla^{2}f(x)$ lie in $[\mu,L]$ for some $\mu>0$.

We wish to find an $\varepsilon$-approximate stationary point (a.k.a. critical point) of $F(x)$, that is

a point $x$ satisfying $\|\mathcal{G}(x)\|\leq\varepsilon$

where $\mathcal{G}(x)$ is the so-called gradient mapping of $F(x)$ (see Section LABEL:sec:pre for a formal definition). In the special case of $\psi(\cdot)\equiv 0$, one has $\mathcal{G}(x)=\nabla f(x)$.

Since $f(\cdot)$ is of $\sigma$-bounded nonconvexity, at least when $\psi(\cdot)\equiv 0$, any $\varepsilon$-approximate stationary point is automatically also an $(\varepsilon,\sigma)$-approximate local minimum— meaning that the Hessian of the output point $\nabla^{2}f(x)\succeq-\sigma\mathbf{I}$ is approximately positive semidefinite (PSD).

2 Motivations and Remarks

We focus on optimization with bounded nonconvexity because introducing this parameter $\sigma$ allows us to perform a more refined study of non-convex optimization. If $\sigma$ equals $L$ then optimization with $L$-bounded nonconvexity is equivalent to the general non-convex (smooth) optimization. We hope that this encourages a new way to compare nonconvex algorithms.

We focus only on finding stationary points as opposed to local minima, because in recent studies [Allenzhu2017-natasha2, AABHM2016, CarmonDHS2016, Allenzhu2018-sgd3] —see Appendix LABEL:sec:intro:reduction— it is shown that finding $(\varepsilon,\delta)$-approximate local minima reduces to finding $\varepsilon$-approximate stationary points in functions of $O(\delta)$-bounded nonconvexity.

Parameter $\sigma$ is often not constant and can be much smaller than $L$. For instance, second-order methods often find $(\varepsilon,\sqrt{\varepsilon})$-approximate local minima [nesterov2008cubic] and this corresponds to $\sigma=\sqrt{\varepsilon}$.

3 Known Results

Despite the widespread use of nonconvex models in machine learning and related fields, our understanding to non-convex optimization is still very limited. Until recently, nearly all research papers have been mostly focusing on either $\sigma=0$ or $\sigma=L$:

If $\sigma=0$, the accelerated SVRG method [Shalev-Shwartz2015-SDCAwithoutDual, AY2015-univr] finds $x$ satisfying $F(x)-F(x^{*})\leq\varepsilon$, in gradient complexity \widetilde{O}\big{(}n+n^{3/4}\sqrt{L/\varepsilon}\big{)}.We use $\widetilde{O}$ to hide poly-logarithmic factors in $n,L,1/\varepsilon$. This result studies convex $f(x)$ and is irrelevant to this paper.

If $\sigma=L$, the SVRG method [AH2016-nonconvex] finds an $\varepsilon$-approximate stationary point of $F(x)$ in gradient complexity $O(n+n^{2/3}L/\varepsilon^{2})$.

If $\sigma=L$, full gradient descent (GD) finds an $\varepsilon$-approximate stationary point of $F(x)$ in gradient complexity $O(nL/\varepsilon^{2})$.

If $\sigma=L$, stochastic gradient descent (SGD) finds an $\varepsilon$-approximate stationary point of $F(x)$ in gradient complexity $O(L/\varepsilon^{2}+L\mathcal{V}/\varepsilon^{4})$ where $\mathcal{V}$ is the variance of the stochastic gradient.The non-convex convergence rates of GD/SGD are not hard to prove. The rate for GD was recorded in Nesterov2004, and was perhaps first established by Polayk in 1960s. The rate for SGD first dates back to GhadimiLan2013stochastic.

To the best of our knowledge, even if $0<\sigma\ll L$, it is not clear whether SGD, GD, or SVRG can take advantage of $\sigma$.Even when $\sigma=0$, the task of finding a point with $\|\nabla f(x)\|\leq\varepsilon$ is a non-trivial task, see [Nesterov2012make]. Very recently, it was observed by two independent groups [AABHM2016, CarmonDHS2016] —although implicitly, see Section LABEL:sec:acc— that for minimizing functions of $\sigma$-bounded nonconvexity, one can repeatedly regularize $F(x)$ to make it $\sigma$-strongly convex, and then apply the accelerated SVRG method to minimize this regularized function. Under mild assumption $\sigma\geq\varepsilon^{2}$, this approach

finds an $\varepsilon$-approximate stationary point in gradient complexity \widetilde{O}\big{(}\frac{n\sigma+n^{3/4}\sqrt{L\sigma}}{\varepsilon^{2}}\big{)}.

We call this method repeatSVRG in this paper. Unfortunately, repeatSVRG is even slower than the vanilla SVRG for $\sigma=L$ by a factor $n^{1/3}$, see Figure 1a.

4 Our New Results

In this paper, we focus on offline methods which are algorithms that run in gradient complexity polynomial in $n$, but at most quadratically in $\varepsilon^{-1}$. For instance, SGD is not offline.

We identify an interesting dichotomy with respect to the spectrum of the nonconvexity parameter $\sigma\in[0,L]$. In particular, we showed that if $\sigma\geq L/\sqrt{n}$, then our new method Natasha1 finds an $\varepsilon$-approximate stationary point of $F(x)$ in gradient complexity

In other words, together with repeatSVRG, we have improved the (offline) gradient complexity for nonconvex optimization of $\sigma$-bounded nonconvexity to We remark here that this is under mild assumptions for $\varepsilon$ being sufficiently small. For instance, the result of [AABHM2016, CarmonDHS2016] requires $\varepsilon^{2}\leq\sigma$. In our result, the term $n\log\frac{1}{\varepsilon}$ disappears when $\varepsilon^{6}\leq L^{2}\sigma/n$.

and the first term in the $\min$ is smaller if $\sigma<L/\sqrt{n}$ and the second term is smaller if $\sigma>L/\sqrt{n}$. We illustrate our performance improvement in Figure 1a. Our result matches that of SVRG for $\sigma=L$, and has a simpler analysis.

5 Our Extensions

Mini-Batch Setting. Our result generalizes trivially to the mini-batch stochastic setting, where in each iteration one computes $\nabla f_{i}(x)$ for $b$ random choices of index $i\in[n]$ and average them. The stated gradient complexities of Natasha1 and