Convex Optimization: Algorithms and Complexity

Chapter 1 Introduction

We are interested in algorithms that take as input a convex set $\mathcal{X}$ and a convex function $f$ and output an approximate minimum of $f$ over $\mathcal{X}$. We write compactly the problem of finding the minimum of $f$ over $\mathcal{X}$ as

In the following we will make more precise how the set of constraints $\mathcal{X}$ and the objective function $f$ are specified to the algorithm. Before that we proceed to give a few important examples of convex optimization problems in machine learning.

Many fundamental convex optimization problems in machine learning take the following form:

In classification one has $\mathcal{Y}=\{-1,1\}$. Taking $f_{i}(x)=\max(0,1-y_{i}x^{\top}w_{i})$ (the so-called hinge loss) and $\mathcal{R}(x)=\|x\|_{2}^{2}$ one obtains the SVM problem. On the other hand taking $f_{i}(x)=\log(1+\exp(-y_{i}x^{\top}w_{i}))$ (the logistic loss) and again $\mathcal{R}(x)=\|x\|_{2}^{2}$ one obtains the (regularized) logistic regression problem.

Our last two examples are of a slightly different flavor. In particular the design variable $x$ is now best viewed as a matrix, and thus we denote it by a capital letter $X$. The sparse inverse covariance estimation problem can be written as follows, given some empirical covariance matrix $Y$,

Intuitively the above problem is simply a regularized maximum likelihood estimator (under a Gaussian assumption).

Finally we introduce the convex version of the matrix completion problem. Here our data set consists of observations of some of the entries of an unknown matrix $Y$, and we want to “complete" the unobserved entries of $Y$ in such a way that the resulting matrix is “simple" (in the sense that it has low rank). After some massaging (see Candès and Recht (2009)) the (convex) matrix completion problem can be formulated as follows:

where $\Omega\subset[n]^{2}$ and $(Y_{i,j})_{(i,j)\in\Omega}$ are given.

2 Basic properties of convexity

A basic result about convex sets that we shall use extensively is the Separation Theorem.

Note that if $\mathcal{X}$ is not closed then one can only guarantee that $w^{\top}x_{0}\leq w^{\top}x,\forall x\in\mathcal{X}$ (and $w\neq 0$). This immediately implies the Supporting Hyperplane Theorem ($\partial\mathcal{X}$ denotes the boundary of $\mathcal{X}$, that is the closure without the interior):

We introduce now the key notion of subgradients.

The set of subgradients of $f$ at $x$ is denoted $\partial f(x)$.

To put it differently, for any $x\in\mathcal{X}$ and $g\in\partial f(x)$, $f$ is above the linear function $y\mapsto f(x)+g^{\top}(y-x)$. The next result shows (essentially) that a convex functions always admit subgradients.

It is obvious that a function is convex if and only if its epigraph is a convex set.

The first claim is almost trivial: let $g\in\partial f((1-\gamma)x+\gamma y)$, then by definition one has

which clearly shows that $f$ is convex by adding the two (appropriately rescaled) inequalities.

Clearly, by letting $t$ tend to infinity, one can see that $b\leq 0$. Now let us assume that $x$ is in the interior of $\mathcal{X}$. Then for $\varepsilon>0$ small enough, $y=x+\varepsilon a\in\mathcal{X}$, which implies that $b$ cannot be equal to (recall that if $b=0$ then necessarily $a\neq 0$ which allows to conclude by contradiction). Thus rewriting (1.2) for $t=f(y)$ one obtains

Thus $a/|b|\in\partial f(x)$ which concludes the proof of the second claim.

Finally let $f$ be a convex and differentiable function. Then by definition:

which shows that $\nabla f(x)\in\partial f(x)$.

3 Why convexity?

The key to the algorithmic success in minimizing convex functions is that these functions exhibit a local to global phenomenon. We have already seen one instance of this in Proposition 1.2.4, where we showed that $\nabla f(x)\in\partial f(x)$: the gradient $\nabla f(x)$ contains a priori only local information about the function $f$ around $x$ while the subdifferential $\partial f(x)$ gives a global information in the form of a linear lower bound on the entire function. Another instance of this local to global phenomenon is that local minima of convex functions are in fact global minima:

Let $f$ be convex. If $x$ is a local minimum of $f$ then $x$ is a global minimum of $f$. Furthermore this happens if and only if $0\in\partial f(x)$.

Clearly $0\in\partial f(x)$ if and only if $x$ is a global minimum of $f$. Now assume that $x$ is local minimum of $f$. Then for $\gamma$ small enough one has for any $y$,

which implies $f(x)\leq f(y)$ and thus $x$ is a global minimum of $f$.

The nice behavior of convex functions will allow for very fast algorithms to optimize them. This alone would not be sufficient to justify the importance of this class of functions (after all constant functions are pretty easy to optimize). However it turns out that surprisingly many optimization problems admit a convex (re)formulation. The excellent book Boyd and Vandenberghe (2004) describes in great details the various methods that one can employ to uncover the convex aspects of an optimization problem. We will not repeat these arguments here, but we have already seen that many famous machine learning problems (SVM, ridge regression, logistic regression, LASSO, sparse covariance estimation, and matrix completion) are formulated as convex problems.

We conclude this section with a simple extension of the optimality condition “$0\in\partial f(x)$” to the case of constrained optimization. We state this result in the case of a differentiable function for sake of simplicity.

Let $f$ be convex and $\mathcal{X}$ a closed convex set on which $f$ is differentiable. Then

The “if" direction is trivial by using that a gradient is also a subgradient. For the “only if" direction it suffices to note that if $\nabla f(x)^{\top}(y-x)<0$, then $f$ is locally decreasing around $x$ on the line to $y$ (simply consider $h(t)=f(x+t(y-x))$ and note that $h^{\prime}(0)=\nabla f(x)^{\top}(y-x)$).

4 Black-box model

A zeroth order oracle takes as input a point $x\in\mathcal{X}$ and outputs the value of $f$ at $x$.

A first order oracle takes as input a point $x\in\mathcal{X}$ and outputs a subgradient of $f$ at $x$.

In this context we are interested in understanding the oracle complexity of convex optimization, that is how many queries to the oracles are necessary and sufficient to find an $\varepsilon$-approximate minima of a convex function. To show an upper bound on the sample complexity we need to propose an algorithm, while lower bounds are obtained by information theoretic reasoning (we need to argue that if the number of queries is “too small" then we don’t have enough information about the function to identify an $\varepsilon$-approximate solution).

The black-box model was essentially developed in the early days of convex optimization (in the Seventies) with Nemirovski and Yudin (1983) being still an important reference for this theory (see also Nemirovski (1995)). In the recent years this model and the corresponding algorithms have regained a lot of popularity, essentially for two reasons:

It is possible to develop algorithms with dimension-free oracle complexity which is quite attractive for optimization problems in very high dimension.

Many algorithms developed in this model are robust to noise in the output of the oracles. This is especially interesting for stochastic optimization, and very relevant to machine learning applications. We will explore this in details in Chapter 6.

Chapter 2, Chapter 3 and Chapter 4 are dedicated to the study of the black-box model (noisy oracles are discussed in Chapter 6). We do not cover the setting where only a zeroth order oracle is available, also called derivative free optimization, and we refer to Conn et al. (2009); Audibert et al. (2011) for further references on this.

5 Structured optimization

The black-box model described in the previous section seems extremely wasteful for the applications we discussed in Section 1.1. Consider for instance the LASSO objective: $x\mapsto\|Wx-y\|_{2}^{2}+\|x\|_{1}$. We know this function globally, and assuming that we can only make local queries through oracles seem like an artificial constraint for the design of algorithms. Structured optimization tries to address this observation. Ultimately one would like to take into account the global structure of both $f$ and $\mathcal{X}$ in order to propose the most efficient optimization procedure. An extremely powerful hammer for this task are the Interior Point Methods. We will describe this technique in Chapter 5 alongside with other more recent techniques such as FISTA or Mirror Prox.

We briefly describe now two classes of optimization problems for which we will be able to exploit the structure very efficiently, these are the LPs (Linear Programs) and SDPs (Semi-Definite Programs). Ben-Tal and Nemirovski (2001) describe a more general class of Conic Programs but we will not go in that direction here.

6 Overview of the results and disclaimer

The overarching aim of this monograph is to present the main complexity theorems in convex optimization and the corresponding algorithms. We focus on five major results in convex optimization which give the overall structure of the text: the existence of efficient cutting-plane methods with optimal oracle complexity (Chapter 2), a complete characterization of the relation between first order oracle complexity and curvature in the objective function (Chapter 3), first order methods beyond Euclidean spaces (Chapter 4), non-black box methods (such as interior point methods) can give a quadratic improvement in the number of iterations with respect to optimal black-box methods (Chapter 5), and finally noise robustness of first order methods (Chapter 6). Table 1.1 can be used as a quick reference to the results proved in Chapter 2 to Chapter 5, as well as some of the results of Chapter 6 (this last chapter is the most relevant to machine learning but the results are also slightly more specific which make them harder to summarize).

An important disclaimer is that the above selection leaves out methods derived from duality arguments, as well as the two most popular research avenues in convex optimization: (i) using convex optimization in non-convex settings, and (ii) practical large-scale algorithms. Entire books have been written on these topics, and new books have yet to be written on the impressive collection of new results obtained for both (i) and (ii) in the past five years.

A few of the blatant omissions regarding (i) include (a) the theory of submodular optimization (see Bach (2013)), (b) convex relaxations of combinatorial problems (a short example is given in Section 6.6), and (c) methods inspired from convex optimization for non-convex problems such as low-rank matrix factorization (see e.g. Jain et al. (2013) and references therein), neural networks optimization, etc.

With respect to (ii) the most glaring omissions include (a) heuristics (the only heuristic briefly discussed here is the non-linear conjugate gradient in Section 2.4), (b) methods for distributed systems, and (c) adaptivity to unknown parameters. Regarding (a) we refer to Nocedal and Wright (2006) where the most practical algorithms are discussed in great details (e.g., quasi-newton methods such as BFGS and L-BFGS, primal-dual interior point methods, etc.). The recent survey Boyd et al. (2011) discusses the alternating direction method of multipliers (ADMM) which is a popular method to address (b). Finally (c) is a subtle and important issue. In the entire monograph the emphasis is on presenting the algorithms and proofs in the simplest way, and thus for sake of convenience we assume that the relevant parameters describing the regularity and curvature of the objective function (Lipschitz constant, smoothness constant, strong convexity parameter) are known and can be used to tune the algorithm’s own parameters. Line search is a powerful technique to replace the knowledge of these parameters and it is heavily used in practice, see again Nocedal and Wright (2006). We observe however that from a theoretical point of view (c) is only a matter of logarithmic factors as one can always run in parallel several copies of the algorithm with different guesses for the values of the parametersNote that this trick does not work in the context of Chapter 6.. Overall the attitude of this text with respect to (ii) is best summarized by a quote of Thomas Cover: “theory is the first term in the Taylor series of practice”, Cover (1992).

Chapter 2 Convex optimization in finite dimension

As we will see these algorithms have an oracle complexity which is linear (or quadratic) in the dimension, hence the title of the chapter (in the next chapter the oracle complexity will be independent of the dimension). An interesting feature of the methods discussed here is that they only need a separation oracle for the constraint set $\mathcal{X}$. In the literature such algorithms are often referred to as cutting plane methods. In particular these methods can be used to find a point $x\in\mathcal{X}$ given only a separating oracle for $\mathcal{X}$ (this is also known as the feasibility problem).

We consider the following simple iterative algorithmAs a warm-up we assume in this section that $\mathcal{X}$ is known. It should be clear from the arguments in the next section that in fact the same algorithm would work if initialized with $\mathcal{S}_{1}\supset\mathcal{X}$.: let $\mathcal{S}_{1}=\mathcal{X}$, and for $t\geq 1$ do the following:

Query the first order oracle at $c_{t}$ and obtain $w_{t}\in\partial f(c_{t})$. Let

If stopped after $t$ queries to the first order oracle then we use $t$ queries to a zeroth order oracle to output

This procedure is known as the center of gravity method, it was discovered independently on both sides of the Wall by Levin (1965) and Newman (1965).

Before proving this result a few comments are in order.

To attain an $\varepsilon$-optimal point the center of gravity method requires $O(n\log(2B/\varepsilon))$ queries to both the first and zeroth order oracles. It can be shown that this is the best one can hope for, in the sense that for $\varepsilon$ small enough one needs $\Omega(n\log(1/\varepsilon))$ calls to the oracle in order to find an $\varepsilon$-optimal point, see Nemirovski and Yudin (1983) for a formal proof.

The rate of convergence given by Theorem 2.1.1 is exponentially fast. In the optimization literature this is called a linear rate as the (estimated) error at iteration $t+1$ is linearly related to the error at iteration $t$.

The last and most important comment concerns the computational complexity of the method. It turns out that finding the center of gravity $c_{t}$ is a very difficult problem by itself, and we do not have computationally efficient procedure to carry out this computation in general. In Section 6.7 we will discuss a relatively recent (compared to the 50 years old center of gravity method!) randomized algorithm to approximately compute the center of gravity. This will in turn give a randomized center of gravity method which we will describe in detail.

We now turn to the proof of Theorem 2.1.1. We will use the following elementary result from convex geometry:

Let $x^{*}$ be such that $f(x^{*})=\min_{x\in\mathcal{X}}f(x)$. Since $w_{t}\in\partial f(c_{t})$ one has

which clearly implies that one can never remove the optimal point from our sets in consideration, that is $x^{*}\in\mathcal{S}_{t}$ for any $t$. Without loss of generality we can assume that we always have $w_{t}\neq 0$, for otherwise one would have $f(c_{t})=f(x^{*})$ which immediately conludes the proof. Now using that $w_{t}\neq 0$ for any $t$ and Lemma 2.1.2 one clearly obtains

2 The ellipsoid method

Recall that an ellipsoid is a convex set of the form

We give now a simple geometric lemma, which is at the heart of the ellipsoid method.

By doing a quick picture, one can see that it makes sense to look for an ellipsoid $\mathcal{E}$ that would be centered at $c=-tw$, with $t\in$ (presumably $t$ will be small), and such that one principal direction is $w$ (with inverse squared semi-axis $a>0$), and the other principal directions are all orthogonal to $w$ (with the same inverse squared semi-axes $b>0$). In other words we are looking for $\mathcal{E}=\{x:(x-c)^{\top}H^{-1}(x-c)\leq 1\}$ with

Now we have to express our constraints on the fact that $\mathcal{E}$ should contain the half Euclidean ball $\{x\in\mathcal{B}:x^{\top}w\leq 0\}$. Since we are also looking for $\mathcal{E}$ to be as small as possible, it makes sense to ask for $\mathcal{E}$ to "touch" the Euclidean ball, both at $x=-w$, and at the equator $\partial\mathcal{B}\cap w^{\perp}$. The former condition can be written as:

As one can see from the above two equations, we are still free to choose any value for $t\in[0,1/2)$ (the fact that we need $t<1/2$ comes from $b=1-\left(\frac{t}{t-1}\right)^{2}>0$). Quite naturally we take the value that minimizes the volume of the resulting ellipsoid. Note that

where $f(h)=h^{2}(2h-h^{2})^{n-1}$. Elementary computations show that the maximum of $f$ (on $$) is attained at$h=1+\frac{1}{n}$(which corresponds to$t=\frac{1}{n+1}$), and the value is

where the lower bound follows again from elementary computations. Thus we showed that, for $\mathcal{E}_{0}=\mathcal{B}$, (2.3) and (2.4) are satisfied with the ellipsoid given by the set of points $x$ satisfying:

Applying Sherman-Morrison formula to (2.8) one can recover (2.6) which concludes the proof.

Let $\mathcal{E}_{t+1}=\{x:(x-c_{t+1})^{\top}H_{t+1}^{-1}(x-c_{t+1})\leq 1\}$ be the ellipsoid given in Lemma 2.2.1 that contains $\{x\in\mathcal{E}_{t}:(x-c_{t})^{\top}w_{t}\leq 0\}$, that is

If stopped after $t$ iterations and if $\{c_{1},\ldots,c_{t}\}\cap\mathcal{X}\neq\emptyset$, then we use the zeroth order oracle to output

The following rate of convergence can be proved with the exact same argument than for Theorem 2.1.1 (observe that at step $t$ one can remove a point in $\mathcal{X}$ from the current ellipsoid only if $c_{t}\in\mathcal{X}$).

For $t\geq 2n^{2}\log(R/r)$ the ellipsoid method satisfies $\{c_{1},\ldots,c_{t}\}\cap\mathcal{X}\neq\emptyset$ and

We observe that the oracle complexity of the ellipsoid method is much worse than the one of the center gravity method, indeed the former needs $O(n^{2}\log(1/\varepsilon))$ calls to the oracles while the latter requires only $O(n\log(1/\varepsilon))$ calls. However from a computational point of view the situation is much better: in many cases one can derive an efficient separation oracle, while the center of gravity method is basically always intractable. This is for instance the case in the context of LPs and SDPs: with the notation of Section 1.5 the computational complexity of the separation oracle for LPs is $O(mn)$ while for SDPs it is $O(\max(m,n)n^{2})$ (we use the fact that the spectral decomposition of a matrix can be done in $O(n^{3})$ operations). This gives an overall complexity of $O(\max(m,n)n^{3}\log(1/\varepsilon))$ for LPs and $O(\max(m,n^{2})n^{6}\log(1/\varepsilon))$ for SDPs. We note however that the ellipsoid method is almost never used in practice, essentially because the method is too rigid to exploit the potential easiness of real problems (e.g., the volume decrease given by (2.4) is essentially always tight).

3 Vaidya’s cutting plane method

We focus here on the feasibility problem (it should be clear from the previous sections how to adapt the argument for optimization). We have seen that for the feasibility problem the center of gravity has a $O(n)$ oracle complexity and unclear computational complexity (see Section 6.7 for more on this), while the ellipsoid method has oracle complexity $O(n^{2})$ and computational complexity $O(n^{4})$. We describe here the beautiful algorithm of Vaidya (1989, 1996) which has oracle complexity $O(n\log(n))$ and computational complexity $O(n^{4})$, thus getting the best of both the center of gravity and the ellipsoid method. In fact the computational complexity can even be improved further, and the recent breakthrough Lee et al. (2015) shows that it can essentially (up to logarithmic factors) be brought down to $O(n^{3})$.

This section, while giving a fundamental algorithm, should probably be skipped on a first reading. In particular we use several concepts from the theory of interior point methods which are described in Section 5.3.

We also consider the volumetric barrier $v$ defined by

The intuition is clear: $v(x)$ is equal to the logarithm of the inverse volume of the Dikin ellipsoid (for the logarithmic barrier) at $x$. It will be useful to spell out the hessian of the logarithmic barrier:

3.2 Vaidya’s algorithm

If for some $i\in[m_{t}]$ one has $\sigma_{i}^{(t)}=\min_{j\in[m_{t}]}\sigma_{j}^{(t)}<\varepsilon$, then $(A^{(t+1)},b^{(t+1)})$ is defined by removing the $i^{th}$ row in $(A^{(t)},b^{(t)})$ (in particular $m_{t+1}=m_{t}-1$).

Then we define $(A^{(t+1)},b^{(t+1)})$ by adding to $(A^{(t)},b^{(t)})$ the row given by $(c^{(t)},\beta^{(t)})$ (in particular $m_{t+1}=m_{t}+1$).

It can be shown that the volumetric barrier is a self-concordant barrier, and thus it can be efficiently minimized with Newton’s method. In fact it is enough to do one step of Newton’s method on $v_{t}$ initialized at $x_{t-1}$, see Vaidya (1989, 1996) for more details on this.

3.3 Analysis of Vaidya’s method

The construction of Vaidya’s method is based on a precise understanding of how the volumetric barrier changes when one adds or removes a constraint to the polytope. This understanding is derived in Section 2.3.4. In particular we obtain the following two key inequalities: If case 1 happens at iteration $t$ then

We show now how these inequalities imply that Vaidya’s method stops after $O(n\log(nR/r))$ steps. First we claim that after $2t$ iterations, case 2 must have happened at least $t-1$ times. Indeed suppose that at iteration $2t-1$, case 2 has happened $t-2$ times; then $\nabla^{2}F(x)$ is singular and the leverage scores are infinite, so case 2 must happen at iteration $2t$. Combining this claim with the two inequalities above we obtain:

Since $\mathcal{E}(x,1)$ is always included in the polytope we have that $-v_{0}(x_{0})$ is at most the logarithm of the volume of the initial polytope which is $O(n\log(R))$. This clearly concludes the proof as the procedure will necessarily stop when the volume is below $\exp(n\log(r))$ (we also used the trivial bound $m_{t}\leq n+1+t$).

3.4 Constraints and the volumetric barrier

The leverage scores $\sigma_{i}$ and $\widetilde{\sigma}_{i}$ are closely related:

First we observe that by Sherman-Morrison’s formula $(A+uv^{\top})^{-1}=A^{-1}-\frac{A^{-1}uv^{\top}A^{-1}}{1+A^{-1}[u,v]}$ one has

This immediately proves $\widetilde{\sigma}_{i}(x)\leq\sigma_{i}(x)$. It also implies the inequality $\widetilde{\sigma}_{i}(x)\geq(1-\sigma_{m+1}(x))\sigma_{i}(x)$ thanks the following fact: $A-\frac{Auu^{\top}A}{1+A[u,u]}\succeq(1-A[u,u])A$. For the last inequality we use that $A+\frac{Auu^{\top}A}{1+A[u,u]}\preceq\frac{1}{1-A[u,u]}A$ together with

We now assume the following key result, which was first proven by Vaidya. To put the statement in context recall that for a self-concordant barrier $f$ the suboptimality gap $f(x)-\min f$ is intimately related to the Newton decrement $\|\nabla f(x)\|_{(\nabla^{2}f(x))^{-1}}$. Vaidya’s inequality gives a similar claim for the volumetric barrier. We use the version given in [Theorem 2.6, Anstreicher (1998)] which has slightly better numerical constants than the original bound. Recall also the definition of $Q$ from (2.10).

Let $\lambda(x)=\|\nabla v(x)\|_{Q(x)^{-1}}$ be an approximate Newton decrement, $\varepsilon=\min_{i\in[m]}\sigma_{i}(x)$, and assume that $\lambda(x)^{2}\leq\frac{2\sqrt{\varepsilon}-\varepsilon}{36}$. Then

We also denote $\widetilde{\lambda}$ for the approximate Newton decrement of $\widetilde{v}$. The goal for the rest of the section is to prove the following theorem which gives the precise understanding of the volumetric barrier we were looking for.

Let $\varepsilon:=\min_{i\in[m]}\sigma_{i}(x^{*})$, $\delta:=\sigma_{m+1}(x^{*})/\sqrt{\varepsilon}$ and assume that $\frac{\left(\delta\sqrt{\varepsilon}+\sqrt{\delta^{3}\sqrt{\varepsilon}}\right)^{2}}{1-\delta\sqrt{\varepsilon}}<\frac{2\sqrt{\varepsilon}-\varepsilon}{36}$. Then one has

On the other hand assuming that $\widetilde{\sigma}_{m+1}(\widetilde{x}^{*})=\min_{i\in[m+1]}\widetilde{\sigma}_{i}(\widetilde{x}^{*})=:\varepsilon$ and that $\varepsilon\leq 1/4$, one has

Before going into the proof let us see briefly how Theorem 2.3.4 give the two inequalities stated at the beginning of Section 2.3.3. To prove (2.12) we use (2.14) with $\delta=1/5$ and $\varepsilon\leq 0.006$, and we observe that in this case the right hand side of (2.14) is lower bounded by $\frac{1}{20}\sqrt{\varepsilon}$. On the other hand to prove (2.11) we use (2.15), and we observe that for $\varepsilon\leq 0.006$ the right hand side of (2.15) is upper bounded by $\varepsilon$.

We start with the proof of (2.14). First observe that by factoring $(\nabla^{2}F(x))^{1/2}$ on the left and on the right of $\nabla^{2}\widetilde{F}(x)$ one obtains

To bound the suboptimality gap of $x^{*}$ in $\widetilde{v}$ we will invoke Theorem 2.3.3 and thus we have to upper bound the approximate Newton decrement $\widetilde{\lambda}$. Using [(2.16), Lemma 2.3.6] below one has

We now turn to the proof of (2.15). Following the same steps as above we immediately obtain

To invoke Theorem 2.3.3 it remains to upper bound $\lambda(\widetilde{x}^{*})$. Using [(2.17), Lemma 2.3.6] below one has

We can apply Theorem 2.3.3 since the assumption $\varepsilon\leq 1/4$ implies that $\left(\frac{2\varepsilon}{1-\varepsilon}\right)^{2}\leq\frac{2\sqrt{\varepsilon}-\varepsilon}{36}$. This concludes the proof of (2.15).

Furthermore if $\widetilde{\sigma}_{m+1}(x)=\min_{i\in[m+1]}\widetilde{\sigma}_{i}(x)$ then one also has

We start with the proof of (2.16). First observe that by Lemma 2.3.1 one has $\widetilde{Q}(x)\succeq(1-\sigma_{m+1}(x))Q(x)$ and thus by definition of the Newton decrement

We now use that $Q(x)\succeq(\min_{i\in[m]}\sigma_{i}(x))\nabla^{2}F(x)$ to obtain

By Lemma 2.3.1 one has $\widetilde{\sigma}_{m+1}(x)\leq{\sigma}_{m+1}(x)$ and thus we see that it only remains to prove

The above inequality follows from a beautiful calculation of Vaidya (see [Lemma 12, Vaidya (1996)]), starting from the identity

We now turn to the proof of (2.17). Following the same steps as above we immediately obtain

Using Lemma 2.3.1 together with the assumption $\widetilde{\sigma}_{m+1}(x)=\min_{i\in[m+1]}\widetilde{\sigma}_{i}(x)$ yields (2.17), thus concluding the proof.

4 Conjugate gradient

Equation (2.20) is true by construction for $i=t$, and for $i\leq t-1$ it follows by induction, assuming (2.20) at $t=1$ and using the following formula:

which concludes the proof of $x_{n}=x^{*}$.

In order to have a proper black-box method it remains to describe how to build iteratively the orthogonal set $\{p_{0},\ldots,p_{n-1}\}$ based only on gradient evaluations of $f$. A natural guess to obtain a set of orthogonal directions (w.r.t. $\langle\cdot,\cdot\rangle_{A}$) is to take $p_{0}=\nabla f(x_{0})$ and for $t\geq 1$,

Furthermore using the definition (2.22) and $\langle\nabla f(x_{t}),p_{t-1}\rangle=0$ one also has

Thus we arrive at the following rewriting of the (linear) conjugate gradient algorithm, where we recall that $x_{0}$ is some fixed starting point and $p_{0}=\nabla f(x_{0})$,

Observe that the algorithm defined by (2.23) and (2.24) makes sense for an arbitary convex function, in which case it is called the non-linear conjugate gradient. There are many variants of the non-linear conjugate gradient, and the above form is known as the Fletcher-–Reeves method. Another popular version in practice is the Polak-Ribière method which is based on the fact that for the general non-quadratic case one does not necessarily have $\langle\nabla f(x_{t+1}),\nabla f(x_{t})\rangle=0$, and thus one replaces (2.24) by

We refer to Nocedal and Wright (2006) for more details about these algorithms, as well as for advices on how to deal with the line search in (2.23).

Finally we also note that the linear conjugate gradient method can often attain an approximate solution in much fewer than $n$ steps. More precisely, denoting $\kappa$ for the condition number of $A$ (that is the ratio of the largest eigenvalue to the smallest eigenvalue of $A$), one can show that linear conjugate gradient attains an $\varepsilon$ optimal point in a number of iterations of order $\sqrt{\kappa}\log(1/\varepsilon)$. The next chapter will demistify this convergence rate, and in particular we will see that (i) this is the optimal rate among first order methods, and (ii) there is a way to generalize this rate to non-quadratic convex functions (though the algorithm will have to be modified).

Chapter 3 Dimension-free convex optimization

where $\eta>0$ is a fixed step-size parameter. The rationale behind (3.1) is to make a small step in the direction that minimizes the local first order Taylor approximation of $f$ (also known as the steepest descent direction).

As we shall see, methods of the type (3.1) can obtain an oracle complexity independent of the dimensionOf course the computational complexity remains at least linear in the dimension since one needs to manipulate gradients.. This feature makes them particularly attractive for optimization in very high dimension.

The following lemma will prove to be useful in our study. It is an easy corollary of Proposition 1.3.3, see also Figure 3.1.

which also implies $\|\Pi_{\mathcal{X}}(y)-x\|^{2}+\|y-\Pi_{\mathcal{X}}(y)\|^{2}\leq\|y-x\|^{2}$.

Unless specified otherwise all the proofs in this chapter are taken from Nesterov (2004a) (with slight simplification in some cases).

In this section we assume that $\mathcal{X}$ is contained in an Euclidean ball centered at $x_{1}\in\mathcal{X}$ and of radius $R$. Furthermore we assume that $f$ is such that for any $x\in\mathcal{X}$ and any $g\in\partial f(x)$ (we assume $\partial f(x)\neq\emptyset$), one has $\|g\|\leq L$. Note that by the subgradient inequality and Cauchy-Schwarz this implies that $f$ is $L$-Lipschitz on $\mathcal{X}$, that is $|f(x)-f(y)|\leq L\|x-y\|$.

In this context we make two modifications to the basic gradient descent (3.1). First, obviously, we replace the gradient $\nabla f(x)$ (which may not exist) by a subgradient $g\in\partial f(x)$. Secondly, and more importantly, we make sure that the updated point lies in $\mathcal{X}$ by projecting back (if necessary) onto it. This gives the projected subgradient descent algorithmIn the optimization literature the term “descent” is reserved for methods such that $f(x_{t+1})\leq f(x_{t})$. In that sense the projected subgradient descent is not a descent method. which iterates the following equations for $t\geq 1$:

This procedure is illustrated in Figure 3.2. We prove now a rate of convergence for this method under the above assumptions.

The projected subgradient descent method with $\eta=\frac{R}{L\sqrt{t}}$ satisfies

Using the definition of subgradients, the definition of the method, and the elementary identity $2a^{\top}b=\|a\|^{2}+\|b\|^{2}-\|a-b\|^{2}$, one obtains

Now note that $\|g_{s}\|\leq L$, and furthermore by Lemma 3.0.1

Summing the resulting inequality over $s$, and using that $\|x_{1}-x^{*}\|\leq R$ yield

Plugging in the value of $\eta$ directly gives the statement (recall that by convexity $f((1/t)\sum_{s=1}^{t}x_{s})\leq\frac{1}{t}\sum_{s=1}^{t}f(x_{s})$).

We will show in Section 3.5 that the rate given in Theorem 3.1.1 is unimprovable from a black-box perspective. Thus to reach an $\varepsilon$-optimal point one needs $\Theta(1/\varepsilon^{2})$ calls to the oracle. In some sense this is an astonishing result as this complexity is independentObserve however that the quantities $R$ and $L$ may dependent on the dimension, see Chapter 4 for more on this. of the ambient dimension $n$. On the other hand this is also quite disappointing compared to the scaling in $\log(1/\varepsilon)$ of the center of gravity and ellipsoid method of Chapter 2. To put it differently with gradient descent one could hope to reach a reasonable accuracy in very high dimension, while with the ellipsoid method one can reach very high accuracy in reasonably small dimension. A major task in the following sections will be to explore more restrictive assumptions on the function to be optimized in order to have the best of both worlds, that is an oracle complexity independent of the dimension and with a scaling in $\log(1/\varepsilon)$.

Finally we observe that the step-size recommended by Theorem 3.1.1 depends on the number of iterations to be performed. In practice this may be an undesirable feature. However using a time-varying step size of the form $\eta_{s}=\frac{R}{L\sqrt{s}}$ one can prove the same rate up to a $\log t$ factor. In any case these step sizes are very small, which is the reason for the slow convergence. In the next section we will see that by assuming smoothness in the function $f$ one can afford to be much more aggressive. Indeed in this case, as one approaches the optimum the size of the gradients themselves will go to , resulting in a sort of “auto-tuning" of the step sizes which does not happen for an arbitrary convex function.

2 Gradient descent for smooth functions

We say that a continuously differentiable function $f$ is $\beta$-smooth if the gradient $\nabla f$ is $\beta$-Lipschitz, that is

Before embarking on the proof we state a few properties of smooth convex functions.

We represent $f(x)-f(y)$ as an integral, apply Cauchy-Schwarz and then $\beta$-smoothness:

This gives in particular the following important inequality to evaluate the improvement in one step of gradient descent:

The next lemma, which improves the basic inequality for subgradients under the smoothness assumption, shows that in fact $f$ is convex and $\beta$-smooth if and only if (3.4) holds true. In the literature (3.4) is often used as a definition of smooth convex functions.

Let $z=y-\frac{1}{\beta}(\nabla f(y)-\nabla f(x))$. Then one has

Using (3.5) and the definition of the method one has

In particular, denoting $\delta_{s}=f(x_{s})-f(x^{*})$, this shows:

We will prove that $\|x_{s}-x^{*}\|$ is decreasing with $s$, which with the two above displays will imply

Let us see how to use this last inequality to conclude the proof. Let $\omega=\frac{1}{2\beta\|x_{1}-x^{*}\|^{2}}$, thenThe last step in the sequence of implications can be improved by taking $\delta_{1}$ into account. Indeed one can easily show with (3.4) that $\delta_{1}\leq\frac{1}{4\omega}$. This improves the rate of Theorem 3.2.1 from $\frac{2\beta\|x_{1}-x^{*}\|^{2}}{t-1}$ to $\frac{2\beta\|x_{1}-x^{*}\|^{2}}{t+3}$.

Thus it only remains to show that $\|x_{s}-x^{*}\|$ is decreasing with $s$. Using Lemma 3.2.4 one immediately gets

We use this as follows (together with $\nabla f(x^{*})=0$)

We now come back to the constrained problem

Similarly to what we did in Section 3.1 we consider the projected gradient descent algorithm, which iterates $x_{t+1}=\Pi_{\mathcal{X}}(x_{t}-\eta\nabla f(x_{t}))$.

The key point in the analysis of gradient descent for unconstrained smooth optimization is that a step of gradient descent started at $x$ will decrease the function value by at least $\frac{1}{2\beta}\|\nabla f(x)\|^{2}$, see (3.5). In the constrained case we cannot expect that this would still hold true as a step may be cut short by the projection. The next lemma defines the “right" quantity to measure progress in the constrained case.

Let $x,y\in\mathcal{X}$, $x^{+}=\Pi_{\mathcal{X}}\left(x-\frac{1}{\beta}\nabla f(x)\right)$, and $g_{\mathcal{X}}(x)=\beta(x-x^{+})$. Then the following holds true:

Indeed the above inequality is equivalent to

which follows from Lemma 3.0.1. Now we use (3.7) as follows to prove the lemma (we also use (3.4) which still holds true in the constrained case)

Let $f$ be convex and $\beta$-smooth on $\mathcal{X}$. Then projected gradient descent with $\eta=\frac{1}{\beta}$ satisfies

We will prove that $\|x_{s}-x^{*}\|$ is decreasing with $s$, which with the two above displays will imply

Thus it only remains to show that $\|x_{s}-x^{*}\|$ is decreasing with $s$. Using Lemma 3.2.7 one can see that $g_{\mathcal{X}}(x_{s})^{\top}(x_{s}-x^{*})\geq\frac{1}{2\beta}\|g_{\mathcal{X}}(x_{s})\|^{2}$ which implies

3 Conditional gradient descent, aka Frank-Wolfe

We describe now an alternative algorithm to minimize a smooth convex function $f$ over a compact convex set $\mathcal{X}$. The conditional gradient descent, introduced in Frank and Wolfe (1956), performs the following update for $t\geq 1$, where $(\gamma_{s})_{s\geq 1}$ is a fixed sequence,

In words conditional gradient descent makes a step in the steepest descent direction given the constraint set $\mathcal{X}$, see Figure 3.3 for an illustration. From a computational perspective, a key property of this scheme is that it replaces the projection step of projected gradient descent by a linear optimization over $\mathcal{X}$, which in some cases can be a much simpler problem.

Let $f$ be a convex and $\beta$-smooth function w.r.t. some norm $\|\cdot\|$, $R=\sup_{x,y\in\mathcal{X}}\|x-y\|$, and $\gamma_{s}=\frac{2}{s+1}$ for $s\geq 1$. Then for any $t\geq 2$, one has

The following inequalities hold true, using respectively $\beta$-smoothness (it can easily be seen that (3.4) holds true for smoothness in an arbitrary norm), the definition of $x_{s+1}$, the definition of $y_{s}$, and the convexity of $f$:

Rewriting this inequality in terms of $\delta_{s}=f(x_{s})-f(x^{*})$ one obtains

A simple induction using that $\gamma_{s}=\frac{2}{s+1}$ finishes the proof (note that the initialization is done at step $2$ with the above inequality yielding $\delta_{2}\leq\frac{\beta}{2}R^{2}$).

Next we describe an application where the three properties of conditional gradient descent (projection-free, norm-free, and sparse iterates) are critical to develop a computationally efficient procedure.

This assumption is met for many combinatorial dictionaries. For instance the dictionary elements could be vector of incidence of spanning trees in some fixed graph, in which case the linear optimization problem can be solved with a greedy algorithm.

First let us study the computational complexity of the $t^{th}$ step of conditional gradient descent. Observe that

To derive a rate of convergence it remains to study the smoothness of $f$. This can be done as follows:

Putting together (3.11) and (3.12) we proved that one can get an $\varepsilon$-optimal solution to (3.10) with a computational effort of $O(m^{2}p(n)/\varepsilon+m^{4}/\varepsilon^{2})$ using the conditional gradient descent.

4 Strong convexity

Of course this definition does not require differentiability of the function $f$, and one can replace $\nabla f(x)$ in the inequality above by $g\in\partial f(x)$. It is immediate to verify that a function $f$ is $\alpha$-strongly convex if and only if $x\mapsto f(x)-\frac{\alpha}{2}\|x\|^{2}$ is convex (in particular if $f$ is twice differentiable then the eigenvalues of the Hessians of $f$ have to be larger than $\alpha$). The strong convexity parameter $\alpha$ is a measure of the curvature of $f$. For instance a linear function has no curvature and hence $\alpha=0$. On the other hand one can clearly see why a large value of $\alpha$ would lead to a faster rate: in this case a point far from the optimum will have a large gradient, and thus gradient descent will make very big steps when far from the optimum. Of course if the function is non-smooth one still has to be careful and tune the step-sizes to be relatively small, but nonetheless we will be able to improve the oracle complexity from $O(1/\varepsilon^{2})$ to $O(1/(\alpha\varepsilon))$. On the other hand with the additional assumption of $\beta$-smoothness we will prove that gradient descent with a constant step-size achieves a linear rate of convergence, precisely the oracle complexity will be $O(\frac{\beta}{\alpha}\log(1/\varepsilon))$. This achieves the objective we had set after Theorem 3.1.1: strongly-convex and smooth functions can be optimized in very large dimension and up to very high accuracy.

Before going into the proofs let us discuss another interpretation of strong-convexity and its relation to smoothness. Equation (3.13) can be read as follows: at any point $x$ one can find a (convex) quadratic lower bound $q_{x}^{-}(y)=f(x)+\nabla f(x)^{\top}(y-x)+\frac{\alpha}{2}\|x-y\|^{2}$ to the function $f$, i.e. $q_{x}^{-}(y)\leq f(y),\forall y\in\mathcal{X}$ (and $q_{x}^{-}(x)=f(x)$). On the other hand for $\beta$-smoothness (3.4) implies that at any point $y$ one can find a (convex) quadratic upper bound $q_{y}^{+}(x)=f(y)+\nabla f(y)^{\top}(x-y)+\frac{\beta}{2}\|x-y\|^{2}$ to the function $f$, i.e. $q_{y}^{+}(x)\geq f(x),\forall x\in\mathcal{X}$ (and $q_{y}^{+}(y)=f(y)$). Thus in some sense strong convexity is a dual assumption to smoothness, and in fact this can be made precise within the framework of Fenchel duality. Also remark that clearly one always has $\beta\geq\alpha$.

We consider here the projected subgradient descent algorithm with time-varying step size $(\eta_{t})_{t\geq 1}$, that is

The following result is extracted from Lacoste-Julien et al. (2012).

Let $f$ be $\alpha$-strongly convex and $L$-Lipschitz on $\mathcal{X}$. Then projected subgradient descent with $\eta_{s}=\frac{2}{\alpha(s+1)}$ satisfies

Coming back to our original analysis of projected subgradient descent in Section 3.1 and using the strong convexity assumption one immediately obtains

Multiplying this inequality by $s$ yields

Now sum the resulting inequality over $s=1$ to $s=t$, and apply Jensen’s inequality to obtain the claimed statement.

4.2 Strongly convex and smooth functions

As we will see now, having both strong convexity and smoothness allows for a drastic improvement in the convergence rate. We denote $\kappa=\frac{\beta}{\alpha}$ for the condition number of $f$. The key observation is that Lemma 3.2.7 can be improved to (with the notation of the lemma):

Let $f$ be $\alpha$-strongly convex and $\beta$-smooth on $\mathcal{X}$. Then projected gradient descent with $\eta=\frac{1}{\beta}$ satisfies for $t\geq 0$,

Using (3.14) with $y=x^{*}$ one directly obtains

We now show that in the unconstrained case one can improve the rate by a constant factor, precisely one can replace $\kappa$ by $(\kappa+1)/4$ in the oracle complexity bound by using a larger step size. This is not a spectacular gain but the reasoning is based on an improvement of (3.6) which can be of interest by itself. Note that (3.6) and the lemma to follow are sometimes referred to as coercivity of the gradient.

Let $\varphi(x)=f(x)-\frac{\alpha}{2}\|x\|^{2}$. By definition of $\alpha$-strong convexity one has that $\varphi$ is convex. Furthermore one can show that $\varphi$ is $(\beta-\alpha)$-smooth by proving (3.4) (and using that it implies smoothness). Thus using (3.6) one gets

which gives the claimed result with straightforward computations. (Note that if $\alpha=\beta$ the smoothness of $\varphi$ directly implies that $\nabla f(x)-\nabla f(y)=\alpha(x-y)$ which proves the lemma in this case.)

First note that by $\beta$-smoothness (since $\nabla f(x^{*})=0$) one has

5 Lower bounds

We prove here various oracle complexity lower bounds. These results first appeared in Nemirovski and Yudin (1983) but we follow here the simplified presentation of Nesterov (2004a). In general a black-box procedure is a mapping from “history" to the next query point, that is it maps $(x_{1},g_{1},\ldots,x_{t},g_{t})$ (with $g_{s}\in\partial f(x_{s})$) to $x_{t+1}$. In order to simplify the notation and the argument, throughout the section we make the following assumption on the black-box procedure: $x_{1}=0$ and for any $t\geq 0$, $x_{t+1}$ is in the linear span of $g_{1},\ldots,g_{t}$, that is

Let $t\leq n$, $L,R>0$. There exists a convex and $L$-Lipschitz function $f$ such that for any black-box procedure satisfying (3.15),

There also exists an $\alpha$-strongly convex and $L$-lipschitz function $f$ such that for any black-box procedure satisfying (3.15),

Note that the above result is restricted to a number of iterations smaller than the dimension, that is $t\leq n$. This restriction is of course necessary to obtain lower bounds polynomial in $1/t$: as we saw in Chapter 2 one can always obtain an exponential rate of convergence when the number of calls to the oracle is larger than the dimension.

We consider the following $\alpha$-strongly convex function:

Next we describe the first order oracle for this function: when asked for a subgradient at $x$, it returns $\alpha x+\gamma e_{i}$ where $i$ is the first coordinate that satisfies $x(i)=\max_{1\leq j\leq t}x(j)$. In particular when asked for a subgradient at $x_{1}=0$ it returns $e_{1}$. Thus $x_{2}$ must lie on the line generated by $e_{1}$. It is easy to see by induction that in fact $x_{s}$ must lie in the linear span of $e_{1},\ldots,e_{s-1}$. In particular for $s\leq t$ we necessarily have $x_{s}(t)=0$ and thus $f(x_{s})\geq 0$.

It remains to compute the minimal value of $f$. Let $y$ be such that $y(i)=-\frac{\gamma}{\alpha t}$ for $1\leq i\leq t$ and $y(i)=0$ for $t+1\leq i\leq n$. It is clear that $0\in\partial f(y)$ and thus the minimal value of $f$ is

Wrapping up, we proved that for any $s\leq t$ one must have

Taking $\gamma=L/2$ and $R=\frac{L}{2\alpha}$ we proved the lower bound for $\alpha$-strongly convex functions (note in particular that $\|y\|^{2}=\frac{\gamma^{2}}{\alpha^{2}t}=\frac{L^{2}}{4\alpha^{2}t}\leq R^{2}$ with these parameters). On the other taking $\alpha=\frac{L}{R}\frac{1}{1+\sqrt{t}}$ and $\gamma=L\frac{\sqrt{t}}{1+\sqrt{t}}$ concludes the proof for convex functions (note in particular that $\|y\|^{2}=\frac{\gamma^{2}}{\alpha^{2}t}=R^{2}$ with these parameters).

We proceed now to the smooth case. As we will see in the following proofs we restrict our attention to quadratic functions, and it might be useful to recall that in this case one can attain the exact optimum in $n$ calls to the oracle (see Section 2.4). We also recall that for a twice differentiable function $f$, $\beta$-smoothness is equivalent to the largest eigenvalue of the Hessians of $f$ being smaller than $\beta$ at any point, which we write

Furthermore $\alpha$-strong convexity is equivalent to

Let $t\leq(n-1)/2$, $\beta>0$. There exists a $\beta$-smooth convex function $f$ such that for any black-box procedure satisfying (3.15),

We consider now the following $\beta$-smooth convex function:

Similarly to what happened in the proof Theorem 3.5.1, one can see here too that $x_{s}$ must lie in the linear span of $e_{1},\ldots,e_{s-1}$ (because of our assumption on the black-box procedure). In particular for $s\leq t$ we necessarily have $x_{s}(i)=0$ for $i=s,\ldots,n$, which implies $x_{s}^{\top}A_{2t+1}x_{s}=x_{s}^{\top}A_{s}x_{s}$. In other words, if we denote

Thus it simply remains to compute the minimizer $x^{*}_{k}$ of $f_{k}$, its norm, and the corresponding function value $f_{k}^{*}$.

The point $x^{*}_{k}$ is the unique solution in the span of $e_{1},\ldots,e_{k}$ of $A_{k}x=e_{1}$. It is easy to verify that it is defined by $x^{*}_{k}(i)=1-\frac{i}{k+1}$ for $i=1,\ldots,k$. Thus we immediately have:

Note that for large values of the condition number $\kappa$ one has

Furthermore since $f$ is $\alpha$-strongly convex, one has

Thus it only remains to compute $x^{*}$. This can be done by differentiating $f$ and setting the gradient to , which gives the following infinite set of equations

It is easy to verify that $x^{*}$ defined by $x^{*}(i)=\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^{i}$ satisfy this infinite set of equations, and the conclusion of the theorem then follows by straightforward computations.

6 Geometric descent

So far our results leave a gap in the case of smooth optimization: gradient descent achieves an oracle complexity of $O(1/\varepsilon)$ (respectively $O(\kappa\log(1/\varepsilon))$ in the strongly convex case) while we proved a lower bound of $\Omega(1/\sqrt{\varepsilon})$ (respectively $\Omega(\sqrt{\kappa}\log(1/\varepsilon))$). In this section we close these gaps with the geometric descent method which was recently introduced in Bubeck et al. (2015b). Historically the first method with optimal oracle complexity was proposed in Nemirovski and Yudin (1983). This method, inspired by the conjugate gradient (see Section 2.4), assumes an oracle to compute plane searches. In Nemirovski (1982) this assumption was relaxed to a line search oracle (the geometric descent method also requires a line search oracle). Finally in Nesterov (1983) an optimal method requiring only a first order oracle was introduced. The latter algorithm, called Nesterov’s accelerated gradient descent, has been the most influential optimal method for smooth optimization up to this day. We describe and analyze this method in Section 3.7. As we shall see the intuition behind Nesterov’s accelerated gradient descent (both for the derivation of the algorithm and its analysis) is not quite transparent, which motivates the present section as geometric descent has a simple geometric interpretation loosely inspired from the ellipsoid method (see Section 2.2).

We focus here on the unconstrained optimization of a smooth and strongly convex function, and we prove that geometric descent achieves the oracle complexity of $O(\sqrt{\kappa}\log(1/\varepsilon))$, thus reducing the complexity of the basic gradient descent by a factor $\sqrt{\kappa}$. We note that this improvement is quite relevant for machine learning applications. Consider for example the logistic regression problem described in Section 1.1: this is a smooth and strongly convex problem, with a smoothness of order of a numerical constant, but with strong convexity equal to the regularization parameter whose inverse can be as large as the sample size. Thus in this case $\kappa$ can be of order of the sample size, and a faster rate by a factor of $\sqrt{\kappa}$ is quite significant. We also observe that this improved rate for smooth and strongly convex objectives also implies an almost optimal rate of $O(\log(1/\varepsilon)/\sqrt{\varepsilon})$ for the smooth case, as one can simply run geometric descent on the function $x\mapsto f(x)+\varepsilon\|x\|^{2}$.

In Section 3.6.1 we describe the basic idea of geometric descent, and we show how to obtain effortlessly a geometric method with an oracle complexity of $O(\kappa\log(1/\varepsilon))$ (i.e., similar to gradient descent). Then we explain why one should expect to be able to accelerate this method in Section 3.6.2. The geometric descent method is described precisely and analyzed in Section 3.6.3.

Rewriting the definition of strong convexity (3.13) as

one obtains an enclosing ball for the minimizer of $f$ with the $0^{th}$ and $1^{st}$ order information at $x$:

Furthermore recall that by smoothness (see (3.5)) one has $f(x^{+})\leq f(x)-\frac{1}{2\beta}\|\nabla f(x)\|^{2}$ which allows to shrink the above ball by a factor of $1-\frac{1}{\kappa}$ and obtain the following:

Thus we see that in the strategy described above, the radius squared of the enclosing ball for $x^{*}$ shrinks by a factor $1-\frac{1}{\kappa}$ at each iteration, thus matching the rate of convergence of gradient descent (see Theorem 3.4.3).

6.2 Acceleration

Thus it only remains to deal with the caveat noted above, which we do via a line search. In turns this line search might shift the new ball (3.16), and to deal with this we shall need the following strengthening of the above set inclusion (we refer to Bubeck et al. (2015b) for a simple proof of this result):

6.3 The geometric descent method

and $c_{t+1}$ (respectively $R^{2}_{t+1}$) be the center (respectively the squared radius) of the ball given by (the proof of) Lemma 3.6.1 which contains

Formulas for $c_{t+1}$ and $R^{2}_{t+1}$ are given at the end of this section.

We will prove a stronger claim by induction that for each $t\geq 0$, one has

The case $t=0$ follows immediately by (3.16). Let us assume that the above display is true for some $t\geq 0$. Then using $f(x_{t+1}^{+})\leq f(x_{t+1})-\frac{1}{2\beta}\|\nabla f(x_{t+1})\|^{2}\leq f(x_{t}^{+})-\frac{1}{2\beta}\|\nabla f(x_{t+1})\|^{2},$ one gets

Thus it only remains to observe that the squared radius of the ball given by Lemma 3.6.1 which encloses the intersection of the two above balls is smaller than $\left(1-\frac{1}{\sqrt{\kappa}}\right)R_{t}^{2}-\frac{2}{\alpha}(f(x_{t+1}^{+})-f(x^{*}))$. We apply Lemma 3.6.1 after moving $c_{t}$ to the origin and scaling distances by $R_{t}$. We set $\varepsilon=\frac{1}{\kappa}$, $g=\frac{\|\nabla f(x_{t+1})\|}{\alpha}$, $\delta=\frac{2}{\alpha}\left(f(x_{t+1}^{+})-f(x^{*})\right)$ and $a={x_{t+1}^{++}-c_{t}}$. The line search step of the algorithm implies that $\nabla f(x_{t+1})^{\top}(x_{t+1}-c_{t})=0$ and therefore, $\|a\|=\|x_{t+1}^{++}-c_{t}\|\geq\|\nabla f(x_{t+1})\|/\alpha=g$ and Lemma 3.6.1 applies to give the result.

One can use the following formulas for $c_{t+1}$ and $R^{2}_{t+1}$ (they are derived from the proof of Lemma 3.6.1). If $|\nabla f(x_{t+1})|^{2}/\alpha^{2}<R_{t}^{2}/2$ then one can tate $c_{t+1}=x_{t+1}^{++}$ and $R_{t+1}^{2}=\frac{|\nabla f(x_{t+1})|^{2}}{\alpha^{2}}\left(1-\frac{1}{\kappa}\right)$. On the other hand if $|\nabla f(x_{t+1})|^{2}/\alpha^{2}\geq R_{t}^{2}/2$ then one can tate

7 Nesterov’s accelerated gradient descent

We describe here the original Nesterov’s method which attains the optimal oracle complexity for smooth convex optimization. We give the details of the method both for the strongly convex and non-strongly convex case. We refer to Su et al. (2014) for a recent interpretation of the method in terms of differential equations, and to Allen-Zhu and Orecchia (2014) for its relation to mirror descent (see Chapter 4).

Nesterov’s accelerated gradient descent, illustrated in Figure 3.6, can be described as follows: Start at an arbitrary initial point $x_{1}=y_{1}$ and then iterate the following equations for $t\geq 1$,

Let $f$ be $\alpha$-strongly convex and $\beta$-smooth, then Nesterov’s accelerated gradient descent satisfies

We define $\alpha$-strongly convex quadratic functions $\Phi_{s},s\geq 1$ by induction as follows:

Intuitively $\Phi_{s}$ becomes a finer and finer approximation (from below) to $f$ in the following sense:

The above inequality can be proved immediately by induction, using the fact that by $\alpha$-strong convexity one has

Equation (3.18) by itself does not say much, for it to be useful one needs to understand how “far" below $f$ is $\Phi_{s}$. The following inequality answers this question:

The rest of the proof is devoted to showing that (3.19) holds true, but first let us see how to combine (3.18) and (3.19) to obtain the rate given by the theorem (we use that by $\beta$-smoothness one has $f(x)-f(x^{*})\leq\frac{\beta}{2}\|x-x^{*}\|^{2}$):

In particular $\Phi_{s+1}$ is by definition minimized at $v_{s+1}$ which can now be defined by induction using the above identity, precisely:

Using the form of $\Phi_{s}$ and $\Phi_{s+1}$, as well as the original definition (3.17) one gets the following identity by evaluating $\Phi_{s+1}$ at $x_{s}$:

Finally we show by induction that $v_{s}-x_{s}=\sqrt{\kappa}(x_{s}-y_{s})$, which concludes the proof of (3.20) and thus also concludes the proof of the theorem:

where the first equality comes from (3.21), the second from the induction hypothesis, the third from the definition of $y_{s+1}$ and the last one from the definition of $x_{s+1}$.

7.2 The smooth case

In this section we show how to adapt Nesterov’s accelerated gradient descent for the case $\alpha=0$, using a time-varying combination of the elements in the primary sequence $(y_{t})$. First we define the following sequences:

(Note that $\gamma_{t}\leq 0$.) Now the algorithm is simply defined by the following equations, with $x_{1}=y_{1}$ an arbitrary initial point,

Let $f$ be a convex and $\beta$-smooth function, then Nesterov’s accelerated gradient descent satisfies

We follow here the proof of Beck and Teboulle (2009). We also refer to Tseng (2008) for a proof with simpler step-sizes.

Using the unconstrained version of Lemma 3.2.7 one obtains

Now multiplying (3.23) by $(\lambda_{s}-1)$ and adding the result to (3.24), one obtains with $\delta_{s}=f(y_{s})-f(x^{*})$,

Multiplying this inequality by $\lambda_{s}$ and using that by definition $\lambda_{s-1}^{2}=\lambda_{s}^{2}-\lambda_{s}$, as well as the elementary identity $2a^{\top}b-\|a\|^{2}=\|b\|^{2}-\|b-a\|^{2}$, one obtains

Putting together (3.25) and (3.26) one gets with $u_{s}=\lambda_{s}x_{s}-(\lambda_{s}-1)y_{s}-x^{*}$,

Summing these inequalities from $s=1$ to $s=t-1$ one obtains:

By induction it is easy to see that $\lambda_{t-1}\geq\frac{t}{2}$ which concludes the proof.

Chapter 4 Almost dimension-free convex optimization in non-Euclidean spaces

We also define the Bregman divergence associated to $f$ as

The following identity will be useful several times:

$\Phi$ is strictly convex and differentiable.

The gradient of $\Phi$ diverges on the boundary of $\mathcal{D}$, that is

Property (i) and (iii) ensures the existence and uniqueness of this projection (in particular since $x\mapsto D_{\Phi}(x,y)$ is locally increasing on the boundary of $\mathcal{D}$). The following lemma shows that the Bregman divergence essentially behaves as the Euclidean norm squared in terms of projections (recall Lemma 3.0.1).

Let $x\in\mathcal{X}\cap\mathcal{D}$ and $y\in\mathcal{D}$, then

The proof is an immediate corollary of Proposition 1.3.3 together with the fact that $\nabla_{x}D_{\Phi}(x,y)=\nabla\Phi(x)-\nabla\Phi(y)$.

2 Mirror descent

See Figure 4.1 for an illustration of this procedure.

Let $\Phi$ be a mirror map $\rho$-strongly convex on $\mathcal{X}\cap\mathcal{D}$ w.r.t. $\|\cdot\|$. Let $R^{2}=\sup_{x\in\mathcal{X}\cap\mathcal{D}}\Phi(x)-\Phi(x_{1})$, and $f$ be convex and $L$-Lipschitz w.r.t. $\|\cdot\|$. Then mirror descent with $\eta=\frac{R}{L}\sqrt{\frac{2\rho}{t}}$ satisfies

Let $x\in\mathcal{X}\cap\mathcal{D}$. The claimed bound will be obtained by taking a limit $x\rightarrow x^{*}$. Now by convexity of $f$, the definition of mirror descent, equation (4.1), and Lemma 4.1.1, one has

which concludes the proof up to trivial computation.

We observe that one can rewrite mirror descent as follows:

This last expression is often taken as the definition of mirror descent (see Beck and Teboulle (2003)). It gives a proximal point of view on mirror descent: the method is trying to minimize the local linearization of the function while not moving too far away from the previous point, with distances measured via the Bregman divergence of the mirror map.