Nesterov’s Accelerated Gradient Descent for Smooth and Strongly Convex Optimization

Posted on March 6, 2014 by Sebastien Bubeck

    \[\]

About a year ago I described Nesterov’s Accelerated Gradient Descent in the context of smooth optimization. As I mentioned previously this has been by far the most popular post on this blog. Today I have decided to revisit this post to give a slightly more geometrical proof (though unfortunately still magical in various parts). I will focus on unconstrained optimization of a smooth and strongly convex function f (in the previous post I dealt only with the smooth case). Precisely f is \alpha-strongly convex and \beta-smooth, and we denote by Q=\beta / \alpha the condition number of f. As explained in this post, in this case the basic gradient descent algorithm requires O(Q \log(1/\epsilon)) iterations to reach \epsilon-accuracy. As we shall see below Nesterov’s Accelerated Gradient Descent attains the improved oracle complexity of O(\sqrt{Q} \log(1/\epsilon)). This is particularly relevant in Machine Learning applications since the strong convexity parameter \alpha can often be viewed as a regularization term, and 1/\alpha can be as large as the sample size. Thus reducing the number of step from “\mathrm{sample \; size}” to “\sqrt{\mathrm{sample \; size}}” can be a huge deal, especially in large scale applications.

Without further due let’s get to the algorithm, which can be described quite succintly. Note that everything written below is simply a condensed version of the calculations appearing on pages 71–81 in Nesterov 2004’s book. Start at an arbitrary initial point x_1 = y_1 and then iterate the following equations for s \geq 1,

    \begin{eqnarray*} y_{s+1} & = & x_s - \frac{1}{\beta} \nabla f(x_s) , \\ x_{s+1} & = & \left(1 + \frac{\sqrt{Q}-1}{\sqrt{Q}+1} \right) y_{s+1} - \frac{\sqrt{Q}-1}{\sqrt{Q}+1} y_s . \end{eqnarray*}

Theorem Let f be \alpha-strongly convex and \beta-smooth, then Nesterov’s Accelerated Gradient Descent satisfies

    \[f(y_t) - f(x^*) \leq \frac{\alpha + \beta}{2} \|x_1 - x^*\|^2 \exp\left(- \frac{t-1}{\sqrt{Q}} \right).\]

Proof: We define \alpha-strongly convex quadratic functions \Phi_s, s \geq 1 by induction as follows:

(1)   \begin{eqnarray*} \Phi_1(x) & = & f(x_1) + \frac{\alpha}{2} \|x-x_1\|^2 , \notag \\ \Phi_{s+1}(x) & = & \left(1 - \frac{1}{\sqrt{Q}}\right) \Phi_s(x) \notag \\ & & + \frac{1}{\sqrt{Q}} \left(f(x_s) + \nabla f(x_s)^{\top} (x-x_s) + \frac{\alpha}{2} \|x-x_s\|^2 \right). \end{eqnarray*}

Intuitively \Phi_s becomes a finer and finer approximation (from below) to f in the following sense:

(2)   \begin{equation*} \Phi_{s+1}(x) \leq f(x) + \left(1 - \frac{1}{\sqrt{Q}}\right)^s (\Phi_1(x) - f(x)). \end{equation*}

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

    \[f(x_s) + \nabla f(x_s)^{\top} (x-x_s) + \frac{\alpha}{2} \|x-x_s\|^2 \leq f(x) .\]

Equation (2) 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:

(3)   \begin{equation*} f(y_s) \leq \min_{x \in \mathbb{R}^n} \Phi_s(x) . \end{equation*}

The rest of the proof is devoted to showing that (3) holds true, but first let us see how to combine (2) and (3) 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):

    \begin{eqnarray*} f(y_t) - f(x^*) & \leq & \Phi_t(x^*) - f(x^*) \\ & \leq & \left(1 - \frac{1}{\sqrt{Q}}\right)^{t-1} (\Phi_1(x^*) - f(x^*)) \\ & \leq & \frac{\alpha + \beta}{2} \|x_1-x^*\|^2 \left(1 - \frac{1}{\sqrt{Q}}\right)^{t-1} . \end{eqnarray*}

We now prove (3) by induction (note that it is true at s=1 since x_1=y_1). Let \Phi_s^* = \min_{x \in \mathbb{R}^n} \Phi_s(x). Using the definition of y_{s+1} (and \beta-smoothness), convexity, and the induction hypothesis, one gets

    \begin{align*} & f(y_{s+1}) \\ & \leq f(x_s) - \frac{1}{2 \beta} \| \nabla f(x_s) \|^2 \\ & = \left(1 - \frac{1}{\sqrt{Q}}\right) f(y_s) + \left(1 - \frac{1}{\sqrt{Q}}\right)(f(x_s) - f(y_s)) + \frac{f(x_s)}{\sqrt{Q}} - \frac{1}{2 \beta} \| \nabla f(x_s) \|^2 \\ & \leq \left(1 - \frac{1}{\sqrt{Q}}\right) \Phi_s^* + \left(1 - \frac{1}{\sqrt{Q}}\right) \nabla f(x_s)^{\top} (x_s - y_s) + \frac{f(x_s)}{\sqrt{Q}} - \frac{1}{2 \beta} \| \nabla f(x_s) \|^2 . \end{align*}

Thus we now have to show that

(4)   \begin{equation*} \Phi_{s+1}^* \geq \left(1 - \frac{1}{\sqrt{Q}}\right) \Phi_s^* + \left(1 - \frac{1}{\sqrt{Q}}\right) \nabla f(x_s)^{\top} (x_s - y_s) + \frac{f(x_s)}{\sqrt{Q}} - \frac{1}{2 \beta} \| \nabla f(x_s) \|^2 . \end{equation*}

To prove this inequality we have to understand better the functions \Phi_s. First note that \nabla^2 \Phi_s(x) = \alpha \mathrm{I}_n (immediate by induction) and thus \Phi_s has to be of the following form:

    \[\Phi_s(x) = \Phi_s^* + \frac{\alpha}{2} \|x - v_s\|^2 ,\]

for some v_s \in \mathbb{R}^n. Now observe that by differentiating (1) and using the above form of \Phi_s one obtains

    \[\nabla \Phi_{s+1}(x) = \alpha \left(1 - \frac{1}{\sqrt{Q}}\right) (x-v_s) + \frac{1}{\sqrt{Q}} \nabla f(x_s) + \frac{\alpha}{\sqrt{Q}} (x-x_s) .\]

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:

(5)   \begin{equation*} v_{s+1} = \left(1 - \frac{1}{\sqrt{Q}}\right) v_s + \frac{1}{\sqrt{Q}} x_s - \frac{1}{\alpha \sqrt{Q}} \nabla f(x_s) . \end{equation*}

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

(6)   \begin{equation*} \Phi_{s+1}^* + \frac{\alpha}{2} \|x_s - v_{s+1}\|^2 = \left(1 - \frac{1}{\sqrt{Q}}\right) \Phi_s^* + \frac{\alpha}{2} \left(1 - \frac{1}{\sqrt{Q}}\right) \|x_s - v_s\|^2 + \frac{1}{\sqrt{Q}} f(x_s) . \end{equation*}

Note that thanks to (5) one has

    \begin{eqnarray*} \|x_s - v_{s+1}\|^2 & = & \left(1 - \frac{1}{\sqrt{Q}}\right)^2 \|x_s - v_s\|^2 + \frac{1}{\alpha^2 Q} \|\nabla f(x_s)\|^2 \\ & & - \frac{2}{\alpha \sqrt{Q}} \left(1 - \frac{1}{\sqrt{Q}}\right) \nabla f(x_s)^{\top}(v_s-x_s) , \end{eqnarray*}

which combined with (6) yields

    \begin{eqnarray*} \Phi_{s+1}^* & = & \left(1 - \frac{1}{\sqrt{Q}}\right) \Phi_s^* + \frac{1}{\sqrt{Q}} f(x_s) + \frac{\alpha}{2 \sqrt{Q}} \left(1 - \frac{1}{\sqrt{Q}}\right) \|x_s - v_s\|^2 \\ & & \qquad - \frac{1}{2 \beta} \| \nabla f(x_s) \|^2 + \frac{1}{\sqrt{Q}} \left(1 - \frac{1}{\sqrt{Q}}\right) \nabla f(x_s)^{\top}(v_s-x_s) . \end{eqnarray*}

Finally we show by induction that v_s - x_s = \sqrt{Q}(x_s - y_s), which concludes the proof of (4) and thus also concludes the proof of the theorem:

    \begin{eqnarray*} v_{s+1} - x_{s+1} & = & \left(1 - \frac{1}{\sqrt{Q}}\right) v_s + \frac{1}{\sqrt{Q}} x_s - \frac{1}{\alpha \sqrt{Q}} \nabla f(x_s) - x_{s+1} \\ & = & \sqrt{Q} x_s - (\sqrt{Q}-1) y_s - \frac{\sqrt{Q}}{\beta} \nabla f(x_s) - x_{s+1} \\ & = & \sqrt{Q} y_{s+1} - (\sqrt{Q}-1) y_s - x_{s+1} \\ & = & \sqrt{Q} (x_{s+1} - y_{s+1}) , \end{eqnarray*}

where the first equality comes from (5), 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}.

\Box

This entry was posted in Optimization. Bookmark the permalink.

13 Responses to "Nesterov’s Accelerated Gradient Descent for Smooth and Strongly Convex Optimization"

  • By Bo Liu November 1, 2017 - 10:53 pm

    Hi Prof. Bubeck

    I remember you had a nice summary of the ODE interpretation (of the Nesterov’s ACG work) line of work, including Weijie Su’s work and others’ work before in one of your blog post. Do you remember which blog it is? I googled, but did not find it. Thanks a lot!

    Reply
  • By Anonymous November 1, 2017 - 8:40 pm

    Thank you for this blog post. Has anyone developed a distributed version of this algorithm, which could be used for a multi-agent system?

    Reply
  • By Charles Nutter October 28, 2016 - 3:46 am

    I am investigation the Nesterov’s Accelerated Gradient Descent for Smooth and Strongly Convex Optimization for application to optimize setting of gate parameters in LSTM RNN blocks. Finding the best estimate of the minimum is very important esp. when considering possible zig-zagging near the minimum. After reading the proof above it appears that most of my concerns are addressed. But, the method appears dangerous accurate and pleasing fast. Could you comment on its applicability to gate and weights design of LSTM blocks? We have only so much time to settle on a useful minimum. Is there an improvement to Nesterov’s method.

    Reply
  • By Bikash July 14, 2016 - 11:37 am

    Hi Prof Bubeck,

    Thanks for this blog article. This helps alot to understand Nesterov’s method. I have been exploring and reading about Nesterov’s convergence bound for quite some time now. I have a question: Are there some examples of simple and strongly convex functions for which Nesterov’s bound is better than the strongly convex bound and worse than the convex quadratic bound.

    best,
    Bikash

    Reply
    • By Sebastien Bubeck July 27, 2016 - 2:22 pm

      I’m not sure I understand the question correctly but you can check Section 5.3 here https://arxiv.org/abs/1602.04847 , I think the example we give could answer your question.

  • By Xiang Cheng December 29, 2015 - 5:39 am

    Hi,

    Is there any way to generalize this acceleration to functions which are smooth/strongly convex in some non-euclidean norm (e.g. l1)?

    L2 has the nice property that the lower bound is always quadratic, whose center is shifted in a way that is easy to compute. In contrast, the lower bound for L1 turns into something complicated very quickly.

    Does there exist any other norm for which the lower bound is easily update-able?

    Reply
  • By [Unfinished] Gradient-based optimization algorithms for training in machine learning and EDA global placement process | Exponentials July 14, 2015 - 5:27 pm

    […] [2] Sebastien Bubeck,  Nesterov’s Accelerated Gradient Descent for Smooth and Strongly Convex Optimization, https://blogs.princeton.edu/imabandit/2014/03/06/nesterovs-accelerated-gradient-descent-for-smooth-a… […]

    Reply
  • By He Sun May 2, 2014 - 5:35 pm

    Just Updating what I am thinking, the idea of nesterov’s method may be cannot match incremental idea, because we’d like to obtain the near optimal for each function component in online learning problem by some sort of line search rules. Moreover, each function component is homogenous, but not share the gradient in the same direction. However, for nesterov’s method, we seems to move more ambitious based on the previous step because we incorporate x_{k-1}. Therefore, it seems hard to combine these two. Am I right about this?

    Thanks,
    He

    Reply
  • By He Sun May 2, 2014 - 5:17 pm

    Hi Prof. Bubeck,

    Thank you for help. I read the paper.

    Two more questions.

    1. I feel like PARTAN and nesterov’s method share the same idea in the sense that they both perform a gradient step and an extrapolation step. But the difference is PARTAN needs two exact line searches. So my question is, can PARTAN also achieves the same complexity as nesterov’s method?

    2. For online learning problem, can we implement incremental version of nesterov’s method to deal with data on-the-fly? That sounds very cool if we can derive some theoretical results of it.

    Thanks,
    He

    Reply
  • By He Sun April 22, 2014 - 7:16 pm

    Hi Prof. Bubeck,

    I am a graduate student taking convex optimization course at MIT. Your post attracts me a lot. A specific question, how to compute condition number in practice? For other approximated setting for Q, will it achieve the optimal complexity too?

    Thanks,
    -He

    Reply
    • By Sebastien Bubeck April 23, 2014 - 11:36 am

      There is a huge literature on how to estimate the parameters such as smoothness/Lipschitzness/strong convexity as you go. You can start by taking a look at Nesterov’s book (see also the Beck and Teboulle FISTA paper).

Leave a reply