Intuition Behind Accelerated First Order Methods

Question

$\newcommand{\prox}{\operatorname{prox}}$ $\newcommand{\argmin}{\operatorname{argmin}}$

Suppose that we want to solve the following convex optimization problem:

$\min_{x \in \mathbb{R}^n} g(x) + h(x)$

where we assumed that $g(x)$ is convex and differentiable, $h(x)$ is convex (here I am trying to be as non-specific as possible). Then recall that the generalized gradient descent can be formulated as follows:

Step $0$: choose initial $x^{0} \in \mathbb{R}^n$

Step $k: k \ge 1$: $x^{(k)} = \prox_h (x^{(k-1)} - t_k \nabla g(x^{(k-1)}), t_k)$

where $\prox$ is a proximal operator defined as $\prox_h(y,t) := \argmin \limits_{x \in \mathbb{R}^n} h(x) + \frac{1}{2t} \|y-x\|^2$

It is known that if $\nabla g(x)$ is Lipschitz continuous and proximal operator can be evaluated, the convergence rate of will be $O(1/k)$. This result can be accelerated to achieve $O(1/k^2)$.

First time proposed by Nesterov in 1983 for smooth functions, the idea of acceleration still remains an active topic of research (for non-smooth, composite functions, etc.). It is not easy to read Nesterov's works (very mathematical), but in order to get an understanding of the concept it is sufficient to look at ISTA (Iterative Tthresholding Algorithms) and FISTA (Fast Iterative Thresholding Algorithms). In particular, my questions below will be based on FISTA's example:

Roughly speaking, acceleration is achieved by introducing one more sequence of numbers $y_k$ constructed as a specific linear combination of $x_k$ and $x_{k-1}$; proximal function operates then on $y_{k}$ instead of $x_k$. In case of FISTA we have:

$t_{k+1} = \frac{1 + \sqrt{1 + 4t^2_k}}{2}$

$y_{k+1} = x_k + \frac{t_k - 1}{t_{k+1}}(x_k - x_{k-1})$

Note, that the sequence $t_k$ satisfies $t^2_k = t^2_{k+1} - t_{k+1}$; this is justified in the proof of the convergence for this algorithm.

Is there any intuitive way to explain, interpret such an approach? Why such a specific combination works and brings such a perceptible improvement to the convergence rate? Can we find an intuitive way to interpret $t$? Probably somebody is actually familiar with Nesterov's works and have more knowledge that I do about some other reasons why $t_k$ is given in this form at first place?

Answer 1

I asked this question myself while trying to understand accelerated methods, asked around, and was pointed to this paper by a professor to help gain some intuition: http://statweb.stanford.edu/~candes/papers/NIPS2014.pdf

To summarize: Su et. al. take Nesterov's accelerated gradient method and take the step size to be infinitesimally small to derive the following ODE $$\ddot{X} + \frac{3}{t} \dot{X} + \nabla f(X) = 0$$ with initial conditions $X(0) = x_0$ and $\dot{X}(0) = 0$. By analyzing this ODE, we can get a better idea about what Nesterov's accelerated gradient method is doing. Hope this resource is helpful!

Answer 2

I think the best intuition up to now, is the geometric interpretation of the algorithm by Sebastin Bubeck. It is based on the idea that based on the information available, we know the optimal $x^*$, reside in the intersection of two circles which can be identified from current point $x_k$. For seeing how it is please go to Convex Optimization: Algorithms and Complexity. Also, on his weblog, he described the algorithm simpler, here: I'm a bandit

Answer 3

Some form of short interpretation is given by Prof. L. Vandenberghe, UCLA, here http://www.seas.ucla.edu/~vandenbe/236C/lectures/fgrad.pdf

Slide 5; though not very informative, given the lack of answers, I am just going to think of it as extrapolation.

Answer 4

Amir Beck himself said in one of his lectures that there is no intuition to be gained - the algebra simply checks out. So while intuitions are nice, sometimes it might be reasonable not to try too hard to get them..

Either way, in Nesterovs lecture notes (page 68) he more or less constructs the extrapolation parameter via estimate sequences of functions. This might be easier to read than his original paper (still not easy) and give some intuition.