14
$\begingroup$

$\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-thresholding algorithms) and FISTA (Fast iterative-thresholding algorithms) here http://mechroom.technion.ac.il/~becka/papers/71654.pdf. 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?

$\endgroup$
  • 2
    $\begingroup$ I should know this, because I use Nesterov's method frequently, but I can't think of a good intuitive explanation off hand. If I wasn't so busy I would look over my optimization notes and figure this out...if no one answers in the next few days I will. $\endgroup$ – icurays1 Aug 21 '14 at 4:58
  • 4
    $\begingroup$ Heck, I've co-authored a peer-reviewed journal article on accelerated first-order methods and I don't have a good intuition about why the "acceleration" works. $\endgroup$ – Michael Grant Aug 21 '14 at 17:51
  • 2
    $\begingroup$ I've also spent a lot of time working with these methods and I don't have good intuition for it either. I'm not sure if anyone does. But if someone has a nice answer it will be very interesting. $\endgroup$ – littleO Aug 24 '14 at 22:49
  • 3
    $\begingroup$ Here's the best I can do in the span of a comment. Assume the following: 1) all you know about the function is that it is continuously differentiable with Lipschitz constant $L$; and 2) at each step, you are allowed to use a linear combination of the current gradient and all previous gradients to construct your step. Now set it up as a game: you decide what your linear combination will be, and the "devil" will construct the worst possible function for that linear combination. The best you can do, it turns out, are various "optimal" methods that achieve $O(1/k^2)$ complexity. $\endgroup$ – Michael Grant Aug 25 '14 at 21:12
  • 3
    $\begingroup$ Well, Nesterov did it this way, so how hard can it be? :-) $\endgroup$ – Michael Grant Aug 27 '14 at 16:48
4
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ But thinking of it as extrapolation doesn't explain the very special term $\frac{k-1}{k+2}$ that appears in the FISTA iteration. $\endgroup$ – littleO Oct 10 '14 at 10:30
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.