Following the steepest direction

This content is available as a PDF here.

Contents

Suppose that you want to solve the problem

$$\underset{x\in [-1,1{]}^d}{min}f(x),$$

and you want to achieve a $ϵ$-precision on the objective function $f$, i.e., you want to obtain an estimate $\hat{x}\in {\mathbb{R}}^d$ of $x^{\star }=0$ such that $\Vert \hat{x}-x^{\star }\Vert \le ϵ$. Since $f$ is continuous, you cannot have access to all values $f(x)$ when $x$ describes the constraints $[-1,1{]}^d$, but you can allow yourself multiples calls to the “oracle” $f(x)$ in order to achieve this precision.

A naive way to do so is to consider a discretization of $[-1,1]$ of precision $ϵ$, that is

$$G_{ϵ}=\{kϵ\mid k\in \{-\lfloor {ϵ}^{-1}\rfloor ,\dots ,\lfloor {ϵ}^{-1}\rfloor \}\},$$

and $G_{ϵ}^d=G_{ϵ}\times \cdots \times G_{ϵ}$ its counterpart in dimension $d$. It is easy to see that taking $\hat{x}$ the minimizers of $f$ over $G_{ϵ}^d$ satisfies the property $\Vert \hat{x}-x^{\star }\Vert \le Lϵ$ as soon as $f$ is $L$-Lipchitz. So what’s the deal?

The issue is that the size of $G_{ϵ}^d$ grows exponentially fast with the dimension $d$. In dimension 1, one needs to perform $2\lfloor {ϵ}^{-1}\rfloor$ evaluations of $f$, but in dimension $d$, one needs $2\lfloor {ϵ}^{-1}{\rfloor }^d$! This quantity gets prohibilitively large in a too fast manner: say you look at a very modest precision of $ϵ={10}^{-2}$, then in dimension $d=1$, only 200 computations of $f$ are needed, whereas in dimension $d=10$, you already need 200000000000000000000 evaluations (that’s 20 zeros).

This is known as the curse of dimensionality, a term introduced by (Bellman, Richard E., 1961) [Chapter V] for optimal control and (over)used since then in the optimization, statistics and machine learning communities (Donoho, David L, 2000). Summary: we need to be (slightly) more clever.

1 Descent direction

Consider the class of algorithms of the form

$$x^{(t+1)}=x^{(t)}+{\eta }^{(t)}{u}^{(t+1)},$$

how to “optimaly choose” the direction $u^{(t+1)}$ such that $x^{(t+1)}$ is closer to a minimum of $f$?

Observe that if $f$ is differentiable, this property is equivalent to $⟨\mathrm{\nabla }f(x),u⟩<0$. The negative gradient $-\mathrm{\nabla }f(\overline{x})$ is the direction of steepest descent at the point $\overline{x}$.

2 The gradient descent (GD) algorithm

Proposition 1 gives birth to what is known as the gradient descent algorithm or gradient descent method.

• Require: Initialization $x^{(0)}\in {\mathbb{R}}^d$, step-size policy ${\eta }^{(t)}>0$.

• for $t=1,\cdots$ do

• $x^{(t+1)}\leftarrow x^{(t)}-{\eta }^{(t)}\mathrm{\nabla }f(x^{(t)})$

• end for

The choice of the step-sizes ${\eta }^{(k)}$ is crucial, and there is several way to do it.

• • Predetermined. In this case, the sequence $({\eta }^{(t)})$ is chosen beforehand, either with a constant step size ${\eta }^{(t)}=\eta \in {\mathbb{R}}_{>0}$ or with a given function of $t$, ${\eta }^{(t)}=g(t)$, e.g., $g(t)=\eta (k+1{)}^{-1/2}$ for some $\eta >0$. For some classes of optimization problem, it is possible to provide guarantees depending on the choice of $g$.

• • Oracle. This is the “optimal” descent that a gradient descent method can produce, defined by

$${\eta }_{\mathrm{oracle}}^{(t)}=\arg \underset{\eta \ge 0}{min}f(x^{(t)}-\eta \mathrm{\nabla }f(x^{(t)})).$$

Remark that this choice is only theoretical since it involves a new optimization problem that may be nonsolvable in closed form.

• • Backtracking rule. Another time…

3 Rates of convegence

Means of convergence

In optimization, we consider several types of (worst-case) convergences:

• • Convergence in norms of the iterates.

Assuming that there exists a minimizer $x^{\star }$, the convergence in norms (for a given norm, typically the Euclidean one) looks at an $ϵ$-solution in the sense of

$$r^{(t)}=\Vert x^{(t)}-x^{\star }\Vert \le ϵ.$$

Note that there may be several minimizers, but we only consider one given minimzier.

• • Convergence to the set of minimizers.

Here, we look at the distance to any minimizer:

$$r^{(t)}=d(x^{(t)},\mathcal{S})=\underset{x^{\star }\in \mathcal{S}}{inf}\Vert x^{(t)}-x^{\star }\Vert \le ϵ,$$

where $\mathcal{S}$ is the set of minimizer.

• • Convergence in value (0-order).

Assuming that the infimum of the problem is given by $f^{\ast }=\underset{x\in \mathrm{dom}f}{inf}f(x)$, an $ϵ$-solution is given by

$$r^{(t)}=f(x^{(t)})-f^{\ast }\le ϵ,$$

and assuming $x^{\star }$ is a solution, this is the quantity $r^{(t)}=f(x^{(t)})-f(x^{\star })$.

• • First-order convergence.

If $f$ is differentiable, one can looks at the gradient of the iterates as

$$r^{(t)}=\Vert \mathrm{\nabla }f(x^{(t)})\Vert \le ϵ.$$

The idea is to use the first-order condition, and say that the more $\mathrm{\nabla }f(x^{(t)})$, the closer we are from a critical point of $f$ if $f$ is nonconvex, and closer from a global minima if $f$ is convex.

Rates versus complexity

To be more precise, we consider $R$-rate below, there is an alternative definition ($Q$-convergence).

• • Sublinear rates.

We say that $r^{(t)}$ enjoys a sublinear rate if it has an upper bound written as a power function of $t$, i.e. $r^{(t)}\le c{t}^{-\alpha }$ where $c>0$ and $\alpha >0$. Typical examples are stochastic gradient descent enjoying a $O(1/\sqrt{t})$ rate for convex functions or the gradient descent enjoying a $O(1/t)$ rate for convex $L$-smooth functions. In term of complexity, if $r^{(t)}$ enjoys a $c{t}^{-\alpha }$ rate, its complexity bound is $(\frac{c}{ϵ}{)}^{1/\alpha }$. For instance, the SGD for convex functions has complexity $O((\frac{c}{ϵ}{)}^2)$.

• • Linear rates.

We say that $r^{(t)}$ enjoys a linear rate if it has an upper bound written as an exponential function of $t$, i.e. $r^{(t)}\le c{e}^{-qt}$ for $c>0$ and $q\in (0,1]$. Note that typically, we don’t obtain directly the exponential function in proofs, but an even more precise one: $r^{(t)}\le c(1-q{)}^t$ that is directly bounded by $c{e}^{-qt}$. In term of complexity, we have the bound $\frac{1}{q}(\log c+\log \frac{1}{ϵ})$.

• • Quadratic rates.

We say that $r^{(t)}$ enjoys a quadratic rate if it has an upper bound written as $r^{(t)}\le c(r^{(t)}{)}^2$ for $c>0$. In term of complexity, we have the bound $\log \log \frac{1}{ϵ}$: each iteration doubles the precision of the estimate! Note that quadratic rates are a special case of a wider class known as superlinear convergence.

4 Explicit analysis of the gradient descent: ordinary least-squares

This part is heavily inspired from (Bach, Francis, 2021, chapter V). Let $n,p\ge 1$, $A\in {\mathbb{R}}^{n\times p}$ and $y\in {\mathbb{R}}^n$. The least-square estimator is defined by the problem

$$\begin{array}{}\text{(1)}& \arg \underset{x\in {\mathbb{R}}^p}{min}f(x)=\frac{1}{2n}\Vert Ax-y{\Vert }_2^2.\end{array}$$

The objective $f$ is twice differentiable, its gradient reads

$$\mathrm{\nabla }f(x)=\frac{1}{n}{A}^{\mathrm{\top }}(Ax-y)\in {\mathbb{R}}^p,$$

and its Hessian is constant on the whole space:

$${\mathrm{\nabla }}^{2}f(x)=H=\frac{1}{n}{A}^{\mathrm{\top }}A\in {\mathbb{R}}^{p\times p}.$$

Note that there is at least one minimizer to the problem (1). The first-order condition for a potential minimizer $x^{\star }$ is given by

$$H{x}^{\star }=\frac{1}{n}{A}^{\mathrm{\top }}y.$$

A necessary, and sufficient condition, to have exactly one minimizer is that $H$ is invertible.

The following lemma shows that, providing the knowledge of $H$, the $t$-iterates of the gradient descent with fixed step-size is computable in closed-form.

Convergence in norm

We denote by $\mu$ the smallest eigenvalue of $H$, $L$ its largest, and we let $\kappa =\frac{L}{\mu }$ its condition number. We have $0\le \mu \le L$ and $\kappa \ge 1$.

Using (2), we have

$$\Vert x^{(t)}-x^{\star }{\Vert }^2=⟨x^{(0)}-x^{\star },(I-\eta H{)}^{2t}(x^{(0)}-x^{\star })⟩.$$

Remark that the eigenvalues of $(I-\eta H{)}^{2t}$ are exactly given by $(1-\eta \lambda {)}^{2t}$ where $\lambda$ is an eigenvalue of $H$. Since all eigenvalues of $H$ are contained in $[\mu ,L]$, one also can bound any $\rho \in \mathrm{eigen}((I-\eta H{)}^{2t})$ by

$$|\rho |\le {(\underset{\lambda \in [\mu ,L]}{max}|1-\eta \lambda |)}^{2t}.$$

Suppose that there is multiple minimizers. In this case, $H$ is not invertible and the smallest eigenvalue $\mu$ is equal to 0. Hence, there exists $v$ such that $(I-\eta H)v=v$. Choose $x^{\star }$ a minimizer. Using $x^{(0)}=v+x^{\star }$, we have

$$\Vert x^{(t)}-x^{\star }{\Vert }^2=⟨v+x^{\star }-x^{\star },(I-\eta H{)}^{2t}(v+x^{\star }-x^{\star })⟩=⟨v,(I-\eta H{)}^{2t}v⟩=\Vert v{\Vert }_2^2.$$

Hence, the method is not necessarly convergent, depending on the initialization.

The situation is different when we assume that there is a unique minimizer.

Choice independant from the strong-convexity constant $\mu$: It is possible to chose a smaller stepsize (hence slower) by taking the suboptimal value $\eta =1/L$. In this case, we get

$$\underset{\lambda \in [\mu ,L]}{max}|1-\eta \lambda |=1-\frac{\mu }{L}=1-\frac{1}{\kappa }.$$

In both cases, we obtained a linear (or geometric, or exponential depending on the community) rate

$$\Vert x^{(t)}-x^{\star }{\Vert }^2\le c^{2t}\Vert x^{(0)}-x^{\star }{\Vert }^2,$$

where $c=\frac{\kappa -1}{\kappa +1}$ or $c=1-\frac{1}{\kappa }$ depending on the choice of the step-size.

It is possible to also speaks in term of iteration complexity. Assuming the choice of $\eta =1/L$, observe that

$${(1-\frac{1}{\kappa })}^{2t}\le \exp (-\frac{1}{\kappa }{)}^{2t}=\exp (-\frac{2t}{\kappa }).$$

Thus, to obtain a fraction $ϵ\Vert x^{(0)}-x^{\star }{\Vert }^2$ it is necessary to perform $t$ iterations defined by

$$ϵ=\exp (-\frac{2t}{\kappa })\iff t=\frac{\kappa }{2}\log \frac{1}{ϵ}.$$

Convergence in value

As we say, if $\mu =0$, one cannot establish the convergence of the iterates. But the story is different for the convergence in value.

[^gradient_descent-1]: Note the presence of $H$ after $(I-\eta H{)}^{2t}$.

5 Convergence of gradient descent for nonconvex functions

Unfortunately, not every functions are quadratic, and we need to deep diver in the analysis of the gradient descent algorithm to understand its behavior on generic function. We are going to explore several class of functions that leads to different rates, either in norm or in objective values. We start with some “weak” results on function with limited regularity and without convexity assumptions.

Coercive continuously differentiable function

The following proposition show a very weak result without any quantification of the rate of convergence of gradient descent.

Remark that if in addition $f$ has a unique critical point, i.e., a unique global minimizer, then $x^{(t)}$ converges to this global minimizer.

Reminders on $L$-smooth functions

Recall that a (full-domain) differentiable function $f:{\mathbb{R}}^n\to \mathbb{R}$ is said to be $L$-smooth if $\mathrm{\nabla }f$ is $L$-Lipschitz. $L$-smoothness is important in optimization because it ensures a quadratic upper bound of the function.

Smooth function bounded from below

The previous result was rather weak. Consider now a function $f:{\mathbb{R}}^d\to \mathbb{R}$ that is $L$-smooth, but not necessarly convex. In addition, we suppose that $f$ has full domain and is bounded from below on ${\mathbb{R}}^d$. The following proposition gives a $O(1/\sqrt{T})$ rate for the 1st-order optimality using a constant step-size. A similar proof is doable for the oracle or the backtracking gradient descent.

Note that we cannot say anything in this context about the rate of convergence of $f(x^{(t)})$ or $(x^{(t)})$! One can show that $\eta =\frac{1}{L}$ is the optimal rate with respect to the bound in (6).

6 Convergence of gradient descent for convex functions

Co-coercivity of the gradient of a convex $L$-smooth function

Convex $L$-smooth functions are co-coercive. This result is sometimes coined Baillon–Haddad theorem [@baillon1977quelquesproprietes], but one shall note that the original contributionis much more general than its application to the gradient.

Convex $L$-smooth function

When $f$ is supposed to be convex, we can have a rate of convergence in objective values.

Strongly convex $L$-smooth function

When $f$ is both $L$-smooth and $\mu$-strongly convex, we have the following “strenghened” co-coercivity.

We now prove the linear convergence of gradient descent when dealing with strongly convex functions.