{"id":32,"date":"2015-10-09T04:09:07","date_gmt":"2015-10-09T04:09:07","guid":{"rendered":"http:\/\/www.aarondefazio.com\/tangentially\/?p=32"},"modified":"2016-11-10T08:42:16","modified_gmt":"2016-11-10T08:42:16","slug":"the-many-ways-to-analyse-gradient-descent","status":"publish","type":"post","link":"https:\/\/www.aarondefazio.com\/tangentially\/?p=32","title":{"rendered":"The Many Ways to Analyse Gradient Descent"},"content":{"rendered":"

Consider the classical gradient descent method:<\/p>\n

\n x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n> =<\/mo> x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n> \u2212<\/mo> \u03b1<\/mi>f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow>.<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

<\/p>\n

It’s a thing of beauty isn’t it? While it’s not used directly in practice any more,
\nthe proof techniques used in its analysis are the building blocks behind the theory of
\nmore advanced optimization methods. I know of 8 di\ufb00erent ways of proving its
\nconvergence rate. Each of the proof techniques are interesting in their own right, but
\nmost books on convex optimization give just a single proof of convergence, then move
\nonto greater things. But to do research in modern convex optimization you should
\nknow them all.\n<\/p>\n

<\/p>\n

The purpose of this series of posts is to detail each of these proof techniques and
\nwhat applications they have to more advanced methods. This post will cover the
\nproofs under strong convexity assumptions, and the next post will cover the
\nnon-strongly convex case. Unlike most proofs in the literature, we will go into detail
\nof every step, so that these proofs can be used as a reference (don’t cite this post
\ndirectly though, cite the original source preferably, or the technical notes version). If
\nyou are aware of any methods I’ve not covered, please leave a comment with a
\nreference so I can update this post.<\/p>\n

<\/p>\n

For most of the proofs we end with a statement like
\nA<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n> \u2264<\/mo> (<\/mo>1<\/mn> \u2212<\/mo> \u03b3<\/mi><\/mrow>)<\/mo><\/mrow>A<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/math>,
\nwhere A<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/math>
\nis some quantity of interest, like distance to solution or function value
\nsub-optimality. A full proof requires chaining these inequalities for each
\nk<\/mi><\/math>, giving something
\nof the form A<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n> \u2264<\/mo> (<\/mo>1<\/mn> \u2212<\/mo> \u03b3<\/mi><\/mrow>)<\/mo><\/mrow><\/mrow>k<\/mi><\/mrow><\/msup \n>A<\/mi><\/mrow>0<\/mn><\/mrow><\/msub \n><\/math>.
\nWe leave this step as a given.\n<\/p>\n

<\/a>Basic lemmas<\/h3>\n

<\/p>\n

These hold for any x<\/mi><\/math>
\nand y<\/mi><\/math>. Here
\n\u03bc<\/mi><\/math> is the strong convexity
\nconstant and L<\/mi><\/math>
\nthe Lipschitz smoothness constant. These are completely
\nstandard, see Nesterov’s book [7<\/a>] for proofs. We use the notation
\nx<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/math> for the unique
\nminimizer of f<\/mi><\/math>
\n(for strongly convex problems).\n<\/p>\n\n\n
<\/a>
\n\n f<\/mi>(<\/mo>y<\/mi><\/mrow>)<\/mo><\/mrow> \u2264<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>)<\/mo><\/mrow> +<\/mo> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>)<\/mo><\/mrow>,<\/mo>y<\/mi> \u2212<\/mo> x<\/mi><\/mrow><\/mfenced> +<\/mo> L<\/mi><\/mrow> \n2<\/mn><\/mrow><\/mfrac> x<\/mi> \u2212<\/mo> y<\/mi><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n>.<\/mo>\n<\/math><\/td>\n		(1)<\/td>\n<\/tr>\n<\/table>\n\n\n
<\/a><\/p>\n

\n f<\/mi>(<\/mo>y<\/mi><\/mrow>)<\/mo><\/mrow> \u2265<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>)<\/mo><\/mrow> +<\/mo> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>)<\/mo><\/mrow>,<\/mo>y<\/mi> \u2212<\/mo> x<\/mi><\/mrow><\/mfenced> +<\/mo> \u03bc<\/mi><\/mrow> \n2<\/mn><\/mrow><\/mfrac> x<\/mi> \u2212<\/mo> y<\/mi><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n>.<\/mo>\n<\/math><\/td>\n

(2)<\/td>\n<\/tr>\n<\/table>\n\n\n
<\/a>
\n\n f<\/mi>(<\/mo>y<\/mi><\/mrow>)<\/mo><\/mrow> \u2265<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>)<\/mo><\/mrow> +<\/mo> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>)<\/mo><\/mrow>,<\/mo>y<\/mi> \u2212<\/mo> x<\/mi><\/mrow><\/mfenced> +<\/mo> 1<\/mn><\/mrow> \n2<\/mn>L<\/mi><\/mrow><\/mfrac> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>y<\/mi><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n>.<\/mo>\n<\/math><\/td>\n		(3)<\/td>\n<\/tr>\n<\/table>\n\n\n
<\/a>
\n\n f<\/mi>(<\/mo>y<\/mi><\/mrow>)<\/mo><\/mrow> \u2264<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>)<\/mo><\/mrow> +<\/mo> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>)<\/mo><\/mrow>,<\/mo>y<\/mi> \u2212<\/mo> x<\/mi><\/mrow><\/mfenced> +<\/mo> 1<\/mn><\/mrow> \n2<\/mn>\u03bc<\/mi><\/mrow><\/mfrac> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>y<\/mi><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n>.<\/mo>\n<\/math><\/td>\n		(4)<\/td>\n<\/tr>\n<\/table>\n\n\n
<\/a>
\n\n f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>y<\/mi><\/mrow>)<\/mo><\/mrow>,<\/mo>x<\/mi> \u2212<\/mo> y<\/mi><\/mrow><\/mfenced> \u2265<\/mo> 1<\/mn><\/mrow> \nL<\/mi><\/mrow><\/mfrac> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>y<\/mi><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n>.<\/mo>\n<\/math><\/td>\n		(5)<\/td>\n<\/tr>\n<\/table>\n\n\n
<\/a><\/p>\n

\n f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>y<\/mi><\/mrow>)<\/mo><\/mrow>,<\/mo>x<\/mi> \u2212<\/mo> y<\/mi><\/mrow><\/mfenced> \u2265<\/mo> \u03bc<\/mi> x<\/mi> \u2212<\/mo> y<\/mi><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n>.<\/mo>\n<\/math><\/td>\n

(6)<\/td>\n<\/tr>\n<\/table>\n

<\/p>\n

\n

1 <\/span> <\/a>Function Value Descent<\/h3>\n

<\/p>\n

There is a very simple proof involving just the function values. We start
\nby showing that the function value descent is controlled by the gradient
\nnorm:\n<\/p>\n

\n<\/p>\n


\n<\/a>
\nLemma 1.<\/span> <\/span>For any given <\/span>\u03b1<\/mi><\/math>,<\/span>
\nthe change in function value between steps can be bounded as follows:<\/span>\n<\/p>\n
\n f<\/mi>(<\/mo>x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2265<\/mo> \u03b1<\/mi> 1<\/mn> \u2212<\/mo>1<\/mn><\/mrow> \n2<\/mn><\/mrow><\/mfrac>\u03b1<\/mi>L<\/mi><\/mrow><\/mfenced> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n>,<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

<\/p>\n

in particular, if <\/span>\u03b1<\/mi> =<\/mo> 1<\/mn><\/mrow> \nL<\/mi><\/mrow><\/mfrac><\/math>
\nwe have <\/span>f<\/mi>(<\/mo>x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2265<\/mo> 1<\/mn><\/mrow> \n2<\/mn>L<\/mi><\/mrow><\/mfrac> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n><\/math>.<\/span>\n<\/p>\n<\/p><\/div>\n

<\/p>\n

\n

\n<\/p>\n


\nProof.<\/span> <\/span>We start with (1<\/a>), the Lipschitz upper bound about x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/math>:\n<\/p>\n
\n f<\/mi>(<\/mo>x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2264<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> +<\/mo> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow>,<\/mo>x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced> +<\/mo> L<\/mi><\/mrow> \n2<\/mn><\/mrow><\/mfrac> x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow>2<\/mn><\/mrow><\/msup \n>.<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

<\/p>\n

Now we plug in the step equation
\nx<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n> =<\/mo> \u2212<\/mo>\u03b1<\/mi>f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> :<\/mo><\/math>\n<\/p>\n
\n f<\/mi>(<\/mo>x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2264<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> \u03b1<\/mi> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n> +<\/mo> \u03b1<\/mi><\/mrow>2<\/mn><\/mrow><\/msup \n>L<\/mi><\/mrow> \n2<\/mn><\/mrow><\/mfrac> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n>,<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

<\/p>\n

Negating and rearranging gives:\n<\/p>\n

\n \u2234<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2265<\/mo> \u03b1<\/mi> 1<\/mn> \u2212<\/mo>1<\/mn><\/mrow> \n2<\/mn><\/mrow><\/mfrac>\u03b1<\/mi>L<\/mi><\/mrow><\/mfenced> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n>.<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n \u25a1\n<\/p>\n<\/p><\/div>\n

<\/p>\n

Now since we are considering strongly convex problems, we actually have found
\na bound on the gradient norm in terms of function value. We apply (4<\/a>):
\nf<\/mi>(<\/mo>y<\/mi><\/mrow>)<\/mo><\/mrow> \u2264<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>)<\/mo><\/mrow> +<\/mo> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>)<\/mo><\/mrow>,<\/mo>y<\/mi> \u2212<\/mo> x<\/mi><\/mrow><\/mfenced> +<\/mo> 1<\/mn><\/mrow> \n2<\/mn>\u03bc<\/mi><\/mrow><\/mfrac> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>y<\/mi><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n><\/math> using
\nx<\/mi> =<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/math>,
\ny<\/mi> =<\/mo> x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/math>:\n<\/p>\n
\n f<\/mi>(<\/mo>x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2264<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow>)<\/mo><\/mrow> +<\/mo> 1<\/mn><\/mrow> \n2<\/mn>\u03bc<\/mi><\/mrow><\/mfrac> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n>,<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

\n \u2234<\/mo> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced> \u2265<\/mo> 2<\/mn>\u03bc<\/mi> f<\/mi>(<\/mo>x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced>.<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

<\/p>\n

So combining these two results:\n<\/p>\n

\n f<\/mi>(<\/mo>x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2265<\/mo> 1<\/mn><\/mrow> \n2<\/mn>L<\/mi><\/mrow><\/mfrac> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n> \u2265<\/mo> \u03bc<\/mi><\/mrow> \nL<\/mi><\/mrow><\/mfrac> f<\/mi>(<\/mo>x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced>.<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

<\/p>\n

We then negate, add & subtract f<\/mi>(<\/mo>x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow>)<\/mo><\/mrow><\/math>,
\nthen rearrange:\n<\/p>\n
\n f<\/mi>(<\/mo>x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2264<\/mo>\u2212<\/mo>\u03bc<\/mi><\/mrow>\nL<\/mi><\/mrow><\/mfrac> f<\/mi>(<\/mo>x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced>,<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

\n \u2234<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> +<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow>)<\/mo><\/mrow> \u2264<\/mo>\u2212<\/mo>\u03bc<\/mi><\/mrow>\nL<\/mi><\/mrow><\/mfrac> f<\/mi>(<\/mo>x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced>,<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

\n \u2234<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow>)<\/mo><\/mrow> \u2264<\/mo> 1<\/mn> \u2212<\/mo>\u03bc<\/mi><\/mrow> \nL<\/mi><\/mrow><\/mfrac><\/mrow><\/mfenced> f<\/mi>(<\/mo>x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced>.<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

<\/p>\n

Note that this function value style proof requires the step size<\/p>\n

\u03b1<\/mi> =<\/mo> 1<\/mn><\/mrow> \nL<\/mi><\/mrow><\/mfrac><\/math> or smaller,
\ninstead of \u03b1<\/mi> =<\/mo> 2<\/mn><\/mrow> \n\u03bc<\/mi>+<\/mo>L<\/mi><\/mrow><\/mfrac><\/math>,
\nwhich we shall see gives the fastest convergence when using some of the other proof
\ntechniques below.\n<\/p>\n

<\/p>\n

\n

<\/a>Comments<\/h4>\n

<\/p>\n

This proof (when \u03b1<\/mi> =<\/mo> 1<\/mn><\/mrow> \nL<\/mi><\/mrow><\/mfrac><\/math>
\nis used) treats gradient descent as an upper bound minimization scheme. Such
\nmethods, sometimes known under the Majorization-Minimization nomenclature [3<\/a>],
\nare quite widespread in optimization. They can be applied to non-convex problems
\neven, although the convergence rates in that case are necessarily weak. Likewise this
\nproof gives the weakest convergence rate of the proof techniques presented in this
\npost, but it is perhaps the simplest. Upper bound minimization techniques
\nhave recently seen interesting applications in 2nd order optimization, in the
\nform of Nesterov’s cubicly regularized Newton’s method [9<\/a>]. For stochastic
\noptimization, the MISO method is also a upper bound minimization scheme [6<\/a>]. For
\nnon-smooth problems, an interesting application of the MM approach is
\nin minimizing convex problems with non-convex regularizers of the form
\n\u03bb<\/mi>log<\/mo> x<\/mi><\/mrow><\/mfenced> +<\/mo> 1<\/mn><\/mrow><\/mfenced><\/math>, in
\nthe form of reweighted L1 regularization [5<\/a>].\n<\/p>\n

<\/p>\n

\n

2 <\/span> <\/a>Iterate Descent<\/h3>\n

<\/p>\n

There is also a simple proof involving just the distance of the iterates
\nx<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/math> to the solution. Using
\nthe de\ufb01nition of the step x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n> =<\/mo> \u2212<\/mo>\u03b1<\/mi>f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow><\/math>:<\/p>\n

<\/p>\n

\n\n x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n><\/mtd> =<\/mo><\/mtd> x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n> \u2212<\/mo> \u03b1<\/mi>f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n> <\/mtd> <\/mtext><\/mtd>\n<\/mtr> <\/mtd> =<\/mo><\/mtd> x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n> \u2212<\/mo> 2<\/mn>\u03b1<\/mi> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow>,<\/mo>x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced> +<\/mo> \u03b1<\/mi><\/mrow>2<\/mn><\/mrow><\/msup \n> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n>.<\/mo><\/mtd> <\/mtext><\/mtd> <\/mtr><\/mtable>\n<\/math>
\n<\/p>\n

\n

<\/p>\n

We now apply both the inner product bounds (5<\/a>)
\n f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>y<\/mi><\/mrow>)<\/mo><\/mrow>,<\/mo>x<\/mi> \u2212<\/mo> y<\/mi><\/mrow><\/mfenced> \u2265<\/mo> 1<\/mn><\/mrow> \nL<\/mi><\/mrow><\/mfrac> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>y<\/mi><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n><\/math>and (6<\/a>)
\n f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>y<\/mi><\/mrow>)<\/mo><\/mrow>,<\/mo>x<\/mi> \u2212<\/mo> y<\/mi><\/mrow><\/mfenced> \u2265<\/mo> \u03bc<\/mi> x<\/mi> \u2212<\/mo> y<\/mi><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n><\/math> , in the following
\nnegated forms, using f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow>)<\/mo><\/mrow> =<\/mo> 0<\/mn><\/math>:\n<\/p>\n
\n \u2212<\/mo>f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow>,<\/mo>x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced>\u2264<\/mo>\u2212<\/mo>1<\/mn><\/mrow>\nL<\/mi><\/mrow><\/mfrac> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n>,<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

\n \u2212<\/mo>f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow>,<\/mo>x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced>\u2264<\/mo>\u2212<\/mo>\u03bc<\/mi> x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n>.<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

<\/p>\n

The inner product term has a weight
\n2<\/mn>\u03b1<\/mi><\/math>, and we apply each
\nof these with weight \u03b1<\/mi><\/math>,
\ngiving:\n<\/p>\n
\n x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n> \u2264<\/mo> 1<\/mn> \u2212<\/mo> \u03b1<\/mi>\u03bc<\/mi><\/mrow><\/mfenced> x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n> +<\/mo> \u03b1<\/mi> \u03b1<\/mi> \u2212<\/mo> 1<\/mn><\/mrow> \nL<\/mi><\/mrow><\/mfrac><\/mrow><\/mfenced> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n>.<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

<\/p>\n

Now if we take \u03b1<\/mi> =<\/mo> 1<\/mn><\/mrow> \nL<\/mi><\/mrow><\/mfrac>,<\/mo><\/math>
\nthen the last term cancels and we have:\n<\/p>\n
\n x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n> \u2264<\/mo> 1<\/mn> \u2212<\/mo>\u03bc<\/mi><\/mrow> \nL<\/mi><\/mrow><\/mfrac><\/mrow><\/mfenced> x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n>.<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

<\/p>\n

This proof is not as tight as possible. Instead of splitting the inner product term
\nand applying both bounds (5) and (6), we can apply the following stronger combined
\nbound from Nesterov’s Book [7<\/a>]: <\/p>\n\n\n
<\/a>
\n\n f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>y<\/mi><\/mrow>)<\/mo><\/mrow>,<\/mo>x<\/mi> \u2212<\/mo> y<\/mi><\/mrow><\/mfenced> \u2265<\/mo> \u03bc<\/mi>L<\/mi><\/mrow> \n\u03bc<\/mi> +<\/mo> L<\/mi><\/mrow><\/mfrac> x<\/mi> \u2212<\/mo> y<\/mi><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n> +<\/mo> 1<\/mn><\/mrow> \n\u03bc<\/mi> +<\/mo> L<\/mi><\/mrow><\/mfrac> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>y<\/mi><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n>.<\/mo>\n<\/math><\/td>\n		(7)<\/td>\n<\/tr>\n<\/table>\n

<\/p>\n

Doing so yields:\n<\/p>\n

\n x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n> \u2264<\/mo> 1<\/mn> \u2212<\/mo>2<\/mn>\u03b1<\/mi>\u03bc<\/mi>L<\/mi><\/mrow> \n\u03bc<\/mi> +<\/mo> L<\/mi><\/mrow><\/mfrac><\/mrow><\/mfenced> x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n> +<\/mo> \u03b1<\/mi> \u03b1<\/mi> \u2212<\/mo> 2<\/mn><\/mrow> \n\u03bc<\/mi> +<\/mo> L<\/mi><\/mrow><\/mfrac><\/mrow><\/mfenced> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n>.<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

<\/p>\n

Now clearly to cancel out the gradient norm term we can take
\n\u03b1<\/mi> =<\/mo> 2<\/mn><\/mrow> \n\u03bc<\/mi>+<\/mo>L<\/mi><\/mrow><\/mfrac><\/math>,
\nwhich yields the convergence rate:
\n<\/p>\n

\n\n x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n><\/mtd> \u2264<\/mo><\/mtd> 1<\/mn> \u2212<\/mo> 4<\/mn>\u03bc<\/mi>L<\/mi><\/mrow> \n \u03bc<\/mi> +<\/mo> L<\/mi><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n><\/mrow><\/mfrac><\/mrow><\/mfenced> x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n><\/mtd> <\/mtext><\/mtd>\n<\/mtr> <\/mtd> \u2248<\/mo><\/mtd> 1<\/mn> \u2212<\/mo>4<\/mn>\u03bc<\/mi><\/mrow> \n L<\/mi><\/mrow><\/mfrac> <\/mrow><\/mfenced> x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n>.<\/mo> <\/mtd> <\/mtext><\/mtd> <\/mtr><\/mtable>\n<\/math>
\n<\/p>\n

\n

<\/p>\n

\n

<\/a>Comments<\/h4>\n

<\/p>\n

This proof technique is the building block of the standard stochastic
\ngradient descent (SGD) proof. The above proof is mostly based on
\nNesterov’s book, I’m not sure what the original citation is. It has a
\nnice geometric interpretation, as the bound on the inner product term
\n f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow>,<\/mo>x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/math> can
\neasily be illustrated in 2 dimensions, say on a white-board. It’s e\ufb00ectively a statement
\non the angles that gradients in convex problems can take. To get the strongest
\nbound using this technique, the complex bound in Equation 7<\/a> has to be
\nused. That stronger bound is not really straight-forward, and perhaps too
\ntechnical (in my opinion) to use in a textbook proof of the convergence
\nrate.<\/p>\n

<\/p>\n

\n

3 <\/span> <\/a>Using the Second Fundamental Theorem of Calculus<\/h3>\n

<\/p>\n

Recall the second fundamental theorem of calculus:\n<\/p>\n

\n f<\/mi>(<\/mo>y<\/mi><\/mrow>)<\/mo><\/mrow> =<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>)<\/mo><\/mrow> +<\/mo> \u222b\n <\/mo><\/mrow>x<\/mi><\/mrow>y<\/mi><\/mrow><\/msubsup \n>f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>z<\/mi><\/mrow>)<\/mo><\/mrow>d<\/mi>z<\/mi>.<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

<\/p>\n

This can be applied along intervals in higher dimensions.
\nThe case we care about is applying it to the \ufb01rst derivatives of
\nf<\/mi><\/math>,
\ngiving an integral involving the Hessian:\n<\/p>\n
\n f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>y<\/mi><\/mrow>)<\/mo><\/mrow> =<\/mo> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>)<\/mo><\/mrow> +<\/mo> \u222b\n <\/mo><\/mrow>0<\/mn><\/mrow>1<\/mn><\/mrow><\/msubsup \n> f<\/mi><\/mrow>\u2032<\/mi>\u2032<\/mi><\/mrow><\/msup \n>x<\/mi> +<\/mo> \u03c4<\/mi>(<\/mo>y<\/mi> \u2212<\/mo> x<\/mi><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced>,<\/mo>y<\/mi> \u2212<\/mo> x<\/mi><\/mrow><\/mfenced>d<\/mi>\u03c4<\/mi>.<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

<\/p>\n

We abuse the angle bracket notation here to apply to matrix-vector products as
\nwell as the usual dot-product. Using this result gives an interesting proof of
\nconvergence of gradient descent that doesn’t rely on the usual convexity
\nlemmas. This proof bounds the distance to solution, just like the previous
\nproof.\n<\/p>\n

\n

<\/p>\n


\n<\/a>
\nLemma 2.<\/span> <\/span>For any positive <\/span>t<\/mi><\/math>:<\/span>\n<\/p>\n
\n x<\/mi> \u2212<\/mo> y<\/mi> +<\/mo> t<\/mi> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>y<\/mi><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow><\/mfenced> \u2264<\/mo> max<\/mo> 1<\/mn> \u2212<\/mo> t<\/mi>L<\/mi><\/mrow><\/mfenced>,<\/mo> 1<\/mn> \u2212<\/mo> t<\/mi>\u03bc<\/mi><\/mrow><\/mfenced><\/mrow><\/mfenced> x<\/mi> \u2212<\/mo> y<\/mi><\/mrow><\/mfenced>.<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n<\/p><\/div>\n

<\/p>\n

\n

\n<\/p>\n


\nProof.<\/span> <\/span>We start by applying the second fundamental theorem of calculus in the above
\nform:<\/p>\n

<\/p>\n

\n\n x<\/mi> \u2212<\/mo> y<\/mi> +<\/mo> t<\/mi> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>y<\/mi><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow><\/mfenced><\/mtd> =<\/mo><\/mtd> x<\/mi> \u2212<\/mo> y<\/mi> +<\/mo> t<\/mi>\u222b\n <\/mo><\/mrow>0<\/mn><\/mrow>1<\/mn><\/mrow><\/msubsup \n> f<\/mi><\/mrow>\u2032<\/mi>\u2032<\/mi><\/mrow><\/msup \n>x<\/mi> +<\/mo> \u03c4<\/mi>(<\/mo>y<\/mi> \u2212<\/mo> x<\/mi><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced>,<\/mo>y<\/mi> \u2212<\/mo> x<\/mi><\/mrow><\/mfenced>d<\/mi>\u03c4<\/mi><\/mrow><\/mfenced><\/mtd> <\/mtext><\/mtd>\n<\/mtr> <\/mtd> =<\/mo><\/mtd> \u222b\n <\/mo><\/mrow>0<\/mn><\/mrow>1<\/mn><\/mrow><\/msubsup \n> t<\/mi>f<\/mi><\/mrow>\u2032<\/mi>\u2032<\/mi><\/mrow><\/msup \n>x<\/mi> +<\/mo> \u03c4<\/mi>(<\/mo>y<\/mi> \u2212<\/mo> x<\/mi><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced> \u2212<\/mo> I<\/mi>,<\/mo>y<\/mi> \u2212<\/mo> x<\/mi><\/mrow><\/mfenced>d<\/mi>\u03c4<\/mi><\/mrow><\/mfenced> <\/mtd> <\/mtext><\/mtd>\n<\/mtr> <\/mtd> \u2264<\/mo><\/mtd> \u222b\n <\/mo><\/mrow>0<\/mn><\/mrow>1<\/mn><\/mrow><\/msubsup \n> t<\/mi>f<\/mi><\/mrow>\u2032<\/mi>\u2032<\/mi><\/mrow><\/msup \n>x<\/mi> +<\/mo> \u03c4<\/mi>(<\/mo>y<\/mi> \u2212<\/mo> x<\/mi><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced> \u2212<\/mo> I<\/mi>,<\/mo>y<\/mi> \u2212<\/mo> x<\/mi><\/mrow><\/mfenced><\/mrow><\/mfenced>d<\/mi>\u03c4<\/mi> <\/mtd> <\/mtext><\/mtd>\n<\/mtr> <\/mtd> \u2264<\/mo><\/mtd> \u222b\n <\/mo><\/mrow>0<\/mn><\/mrow>1<\/mn><\/mrow><\/msubsup \n> t<\/mi>f<\/mi><\/mrow>\u2032<\/mi>\u2032<\/mi><\/mrow><\/msup \n>x<\/mi> +<\/mo> \u03c4<\/mi>(<\/mo>y<\/mi> \u2212<\/mo> x<\/mi><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced> \u2212<\/mo> I<\/mi><\/mrow><\/mfenced> x<\/mi> \u2212<\/mo> y<\/mi><\/mrow><\/mfenced>d<\/mi>\u03c4<\/mi> <\/mtd> <\/mtext><\/mtd>\n<\/mtr> <\/mtd> \u2264<\/mo><\/mtd> max<\/mo><\/mrow>z<\/mi><\/mrow><\/munder \n> t<\/mi>f<\/mi><\/mrow>\u2032<\/mi>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>z<\/mi><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> I<\/mi><\/mrow><\/mfenced> x<\/mi> \u2212<\/mo> y<\/mi><\/mrow><\/mfenced>.<\/mo> <\/mtd> <\/mtext><\/mtd> <\/mtr><\/mtable>\n<\/math>
\n<\/p>\n

\n

<\/p>\n

Now we examine the eigenvalues of
\nf<\/mi><\/mrow>\u2032<\/mi>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>z<\/mi><\/mrow>)<\/mo><\/mrow><\/math>. the minimum one
\nis at least \u03bc<\/mi><\/math> and the
\nmaximum at most L<\/mi><\/math>.
\nAn examination of the possible range of the eigenvalues of
\n(<\/mo>t<\/mi>f<\/mi><\/mrow>\u2032<\/mi>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>z<\/mi><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> I<\/mi><\/mrow>)<\/mo><\/mrow><\/math> gives
\n max<\/mo> 1<\/mn> \u2212<\/mo> t<\/mi>L<\/mi><\/mrow><\/mfenced>,<\/mo> 1<\/mn> \u2212<\/mo> t<\/mi>\u03bc<\/mi><\/mrow><\/mfenced><\/mrow><\/mfenced><\/math>. \u25a1\n<\/p>\n<\/p><\/div>\n

<\/p>\n

Using this lemma gives a simple proof along the lines of the iterate descent
\nproof.\n<\/p>\n

<\/p>\n

First, note that x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/math>
\nis in the right form for direct application of this lemma after substituting in the step
\nequation:<\/p>\n

<\/p>\n

\n\n x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mtd> =<\/mo><\/mtd> x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n> +<\/mo> \u03b1<\/mi> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow><\/mfenced> <\/mtd> <\/mtext><\/mtd>\n<\/mtr> <\/mtd> \u2264<\/mo><\/mtd> max<\/mo> 1<\/mn> \u2212<\/mo> \u03b1<\/mi>L<\/mi><\/mrow><\/mfenced>,<\/mo> 1<\/mn> \u2212<\/mo> \u03b1<\/mi>\u03bc<\/mi><\/mrow><\/mfenced><\/mrow><\/mfenced> x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced>.<\/mo><\/mtd> <\/mtext><\/mtd> <\/mtr><\/mtable>\n<\/math>
\n<\/p>\n

\n

<\/p>\n

Note we introduced f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow>)<\/mo><\/mrow><\/math>
\nfor \u201cfree\u201d, as it’s of course equal to zero. The next step is optimize this bound in terms of
\n\u03b1<\/mi><\/math>. Note that
\nL<\/mi><\/math> is always
\nlarger than \u03bc<\/mi><\/math>, so
\nwe take the 1<\/mn> \u2212<\/mo> \u03b1<\/mi>L<\/mi><\/mrow><\/mfenced><\/math>
\nabsolute value as negative, and the other positive, and match their magnitudes:\n<\/p>\n
\n \u2212<\/mo>1<\/mn> +<\/mo> \u03b1<\/mi>L<\/mi> =<\/mo> 1<\/mn> \u2212<\/mo> \u03b1<\/mi>\u03bc<\/mi>,<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

\n \u2234<\/mo> \u03b1<\/mi>(<\/mo>L<\/mi> +<\/mo> \u03bc<\/mi><\/mrow>)<\/mo><\/mrow> =<\/mo> 2<\/mn>,<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

\n \u2234<\/mo> \u03b1<\/mi> =<\/mo> 2<\/mn><\/mrow> \nL<\/mi> +<\/mo> \u03bc<\/mi><\/mrow><\/mfrac>.<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

<\/p>\n

Which gives the convergence rate:\n<\/p>\n

\n x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced>\u2264<\/mo> L<\/mi> \u2212<\/mo> \u03bc<\/mi><\/mrow>\nL<\/mi> +<\/mo> \u03bc<\/mi><\/mrow><\/mfrac><\/mrow><\/mfenced> x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced>.<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

<\/p>\n

Note that this rate is in terms of the distance to solution directly, rather than its
\nsquare like in the previous proof. Converting to squared norm gives the same rate as
\nbefore.\n<\/p>\n

<\/p>\n

\n

<\/a>Comments<\/h4>\n

<\/p>\n

This proof technique has a linear-algebra feel to it, and is perhaps most comfortable
\nto people with that background. The absolute values make it ugly in my opinion
\nthough. This proof technique is the building block used in the standard proof of the
\nconvergence of the heavy ball method for strongly convex problems [10<\/a>]. It doesn’t
\nappear to have many other applications, and so is probably the least seen of
\nthe techniques in this document. The main use of this kind of argument
\nis in lower complexity bounds, where we often do some sort of eigenvalue
\nanalysis.\n<\/p>\n

<\/p>\n

\n

4 <\/span> <\/a>Lyapunov Style<\/h3>\n

<\/p>\n

The above results prove convergence of either the iterates or the function value
\nseparately. There is an interesting proof involving the sum of the two quantities. First
\nwe start with with the iterate convergence:\n<\/p>\n

<\/p>\n

\n<\/p>\n

\n\n x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n><\/mtd> =<\/mo><\/mtd> x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n>\u2212<\/mo> \u03b1<\/mi>f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n> <\/mtd> <\/mtext><\/mtd>\n<\/mtr> <\/mtd> =<\/mo><\/mtd> x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n> \u2212<\/mo> 2<\/mn>\u03b1<\/mi> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow>,<\/mo>x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced> +<\/mo> \u03b1<\/mi><\/mrow>2<\/mn><\/mrow><\/msup \n> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n>.<\/mo><\/mtd> <\/mtext><\/mtd> <\/mtr><\/mtable>\n<\/math><\/p>\n

<\/p>\n

\n

<\/p>\n

Now we use the function descent amount equation (Lemma 1<\/a>) to bound the gradient norm
\nterm: 1<\/mn><\/mrow>\nc<\/mi><\/mrow><\/mfrac> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n> \u2264<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow><\/math> , where we
\nhave de\ufb01ned c<\/mi> =<\/mo> 1<\/mn>\u2215<\/mo> \u03b1<\/mi> 1<\/mn> \u2212<\/mo>1<\/mn><\/mrow> \n2<\/mn><\/mrow><\/mfrac>\u03b1<\/mi>L<\/mi><\/mrow><\/mfenced><\/mrow><\/mfenced><\/math>:\n<\/p>\n
\n x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n> \u2264<\/mo> x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n> +<\/mo> c<\/mi>\u03b1<\/mi><\/mrow>2<\/mn><\/mrow><\/msup \n> f<\/mi>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced> \u2212<\/mo> 2<\/mn>\u03b1<\/mi> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow>,<\/mo>x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced>.<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

<\/p>\n

Now we use the strong convexity lower bound (2<\/a>) in a rearranged form:
\n<\/p>\n

\n\n f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow>,<\/mo>x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n>\u2212<\/mo> x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced><\/mtd> \u2264<\/mo><\/mtd> f<\/mi>(<\/mo>x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo>\u03bc<\/mi><\/mrow> \n2<\/mn><\/mrow><\/mfrac> x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n>,<\/mo><\/mtd> <\/mtext><\/mtd> <\/mtr><\/mtable>\n<\/math>
\n<\/p>\n

\nto simplify:\n<\/p>\n

\n x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n> \u2264<\/mo> 1<\/mn> \u2212<\/mo> \u03b1<\/mi>\u03bc<\/mi><\/mrow><\/mfenced> x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n> +<\/mo> c<\/mi>\u03b1<\/mi><\/mrow>2<\/mn><\/mrow><\/msup \n> f<\/mi>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced> +<\/mo> 2<\/mn>\u03b1<\/mi> f<\/mi>(<\/mo>x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced>.<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

<\/p>\n

Now rearranging further:\n<\/p>\n

\nx<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n>+<\/mo>c<\/mi>\u03b1<\/mi><\/mrow>2<\/mn><\/mrow><\/msup \n> f<\/mi>(<\/mo>x<\/mi><\/mrow>\nk<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced> \u2264<\/mo> 1<\/mn> \u2212<\/mo> \u03b1<\/mi>\u03bc<\/mi><\/mrow><\/mfenced> x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n>+<\/mo>c<\/mi>\u03b1<\/mi><\/mrow>2<\/mn><\/mrow><\/msup \n> \u2212<\/mo> 2<\/mn>\u03b1<\/mi><\/mrow><\/mfenced> f<\/mi>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced>.<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

<\/p>\n

Now this equation gives a descent rate for the weighted sum of
\n x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n><\/math> and
\nf<\/mi>(<\/mo>x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow>)<\/mo><\/mrow>.<\/mo><\/math> The
\nbest rate is given by matching the two convergence rates, that of the iterate distance
\nterms:\n<\/p>\n
\n 1<\/mn> \u2212<\/mo> \u03b1<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n>\u03bc<\/mi>,<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

<\/p>\n

and that of the function value terms, which changes from
\nc<\/mi>\u03b1<\/mi><\/mrow>2<\/mn><\/mrow><\/msup \n><\/math> to
\nc<\/mi>\u03b1<\/mi><\/mrow>2<\/mn><\/mrow><\/msup \n> \u2212<\/mo> 2<\/mn>\u03b1<\/mi><\/math>:
\n<\/p>\n

\n\n c<\/mi>\u03b1<\/mi><\/mrow>2<\/mn><\/mrow><\/msup \n> \u2212<\/mo> 2<\/mn>\u03b1<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow>\n c<\/mi>\u03b1<\/mi><\/mrow>2<\/mn><\/mrow><\/msup \n><\/mrow><\/mfrac> <\/mtd> =<\/mo><\/mtd> 1<\/mn> \u2212<\/mo> 2<\/mn><\/mrow> \nc<\/mi>\u03b1<\/mi><\/mrow><\/mfrac> <\/mtd> <\/mtext><\/mtd>\n<\/mtr> <\/mtd> =<\/mo><\/mtd> 1<\/mn> \u2212<\/mo> 2<\/mn> 1<\/mn> \u2212<\/mo>1<\/mn><\/mrow> \n2<\/mn><\/mrow><\/mfrac>\u03b1<\/mi>L<\/mi><\/mrow><\/mfenced><\/mtd> <\/mtext><\/mtd>\n<\/mtr> <\/mtd> =<\/mo><\/mtd> \u03b1<\/mi>L<\/mi> \u2212<\/mo> 1<\/mn>.<\/mo> <\/mtd> <\/mtext><\/mtd> <\/mtr><\/mtable>\n<\/math>
\n<\/p>\n

\n

<\/p>\n

Matching these two rates:\n<\/p>\n

\n 1<\/mn> \u2212<\/mo> \u03b1<\/mi>\u03bc<\/mi> =<\/mo> \u03b1<\/mi>L<\/mi> \u2212<\/mo> 1<\/mn>,<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

\n \u2234<\/mo> 2<\/mn> =<\/mo> \u03b1<\/mi>(<\/mo>\u03bc<\/mi> +<\/mo> L<\/mi><\/mrow>)<\/mo><\/mrow>,<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

\n \u2234<\/mo> \u03b1<\/mi> =<\/mo> 2<\/mn><\/mrow> \n\u03bc<\/mi> +<\/mo> L<\/mi><\/mrow><\/mfrac>.<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

<\/p>\n

Using this derived value for \u03b1<\/mi><\/math><\/p>\n

gives a convergence rate of 1<\/mn> \u2212<\/mo> 2<\/mn>\u03bc<\/mi><\/mrow> \n\u03bc<\/mi>+<\/mo>L<\/mi><\/mrow><\/mfrac><\/math>.
\nI.e.\n<\/p>\n
\nx<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n>+<\/mo>c<\/mi>\u03b1<\/mi><\/mrow>2<\/mn><\/mrow><\/msup \n> f<\/mi>(<\/mo>x<\/mi><\/mrow>\nk<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced> \u2264<\/mo> 1<\/mn> \u2212<\/mo> 2<\/mn>\u03bc<\/mi><\/mrow> \n\u03bc<\/mi> +<\/mo> L<\/mi><\/mrow><\/mfrac><\/mrow><\/mfenced> x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n> +<\/mo> c<\/mi>\u03b1<\/mi><\/mrow>2<\/mn><\/mrow><\/msup \n> f<\/mi>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow><\/mfenced>.<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

<\/p>\n

and therefore after k<\/mi><\/math>
\nsteps:\n<\/p>\n
\n x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n> +<\/mo> c<\/mi>\u03b1<\/mi><\/mrow>2<\/mn><\/mrow><\/msup \n> f<\/mi>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced> \u2264<\/mo> 1<\/mn> \u2212<\/mo> 2<\/mn>\u03bc<\/mi><\/mrow> \n\u03bc<\/mi> +<\/mo> L<\/mi><\/mrow><\/mfrac><\/mrow><\/mfenced><\/mrow>k<\/mi><\/mrow><\/msup \n> x<\/mi><\/mrow>\n0<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n> +<\/mo> c<\/mi>\u03b1<\/mi><\/mrow>2<\/mn><\/mrow><\/msup \n> f<\/mi>(<\/mo>x<\/mi><\/mrow>\n0<\/mn><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow><\/mfenced>.<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

<\/p>\n

The constants can be simpli\ufb01ed to:\n<\/p>\n

<\/p>\n

\n

<\/p>\n

\n\n c<\/mi>\u03b1<\/mi><\/mrow>2<\/mn><\/mrow><\/msup \n><\/mtd> =<\/mo><\/mtd> \u03b1<\/mi><\/mrow>2<\/mn><\/mrow><\/msup \n><\/mrow><\/p>\n

\u03b1<\/mi> 1<\/mn> \u2212<\/mo>1<\/mn><\/mrow> \n2<\/mn><\/mrow><\/mfrac>\u03b1<\/mi>L<\/mi><\/mrow><\/mfenced><\/mrow><\/mfrac><\/mtd> <\/mtext><\/mtd>\n<\/mtr> <\/mtd> =<\/mo><\/mtd> \u03b1<\/mi><\/mrow>\n1<\/mn> \u2212<\/mo>1<\/mn><\/mrow> \n2<\/mn><\/mrow><\/mfrac>\u03b1<\/mi>L<\/mi><\/mrow><\/mfrac> <\/mtd> <\/mtext><\/mtd>\n<\/mtr> <\/mtd> =<\/mo><\/mtd> \u03b1<\/mi><\/mrow>\n1<\/mn> \u2212<\/mo> L<\/mi><\/mrow> \n\u03bc<\/mi>+<\/mo>L<\/mi><\/mrow><\/mfrac><\/mrow><\/mfrac> <\/mtd> <\/mtext><\/mtd>\n<\/mtr> <\/mtd> =<\/mo><\/mtd> \u03b1<\/mi><\/mrow>\n \u03bc<\/mi><\/mrow>\n\u03bc<\/mi>+<\/mo>L<\/mi><\/mrow><\/mfrac><\/mrow><\/mfrac> <\/mtd> <\/mtext><\/mtd>\n<\/mtr> <\/mtd> =<\/mo><\/mtd> 2<\/mn><\/mrow>\n\u03bc<\/mi><\/mrow><\/mfrac>.<\/mo> <\/mtd> <\/mtext><\/mtd> <\/mtr><\/mtable>\n<\/math>
\n<\/p>\n

\n

<\/p>\n

Now we use: f<\/mi>(<\/mo>x<\/mi><\/mrow>0<\/mn><\/mrow><\/msup \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow>)<\/mo><\/mrow> \u2264<\/mo> L<\/mi><\/mrow> \n2<\/mn><\/mrow><\/mfrac> x<\/mi><\/mrow>0<\/mn><\/mrow><\/msup \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n><\/math>
\non the right, and we just drop the function value term altogether on the
\nleft:\n<\/p>\n

<\/p>\n

\n

<\/p>\n

\n\n x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n><\/mtd> \u2264<\/mo><\/mtd> 1<\/mn> \u2212<\/mo> 2<\/mn>\u03bc<\/mi><\/mrow> \n\u03bc<\/mi> +<\/mo> L<\/mi><\/mrow><\/mfrac><\/mrow><\/mfenced><\/mrow>k<\/mi><\/mrow><\/msup \n>\u03bc<\/mi> +<\/mo> L<\/mi><\/mrow>\n \u03bc<\/mi><\/mrow><\/mfrac> x<\/mi><\/mrow>0<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n>.<\/mo><\/mtd> <\/mtext><\/mtd> <\/mtr><\/mtable>\n<\/math>
\n<\/p>\n

\n

<\/p>\n

If we instead use the more robust step size
\n 1<\/mn><\/mrow>\nL<\/mi><\/mrow><\/mfrac><\/math>, which doesn’t
\nrequire knowledge of \u03bc<\/mi><\/math>,
\nthen a simple calculation shows that we instead get
\nc<\/mi> =<\/mo> 2<\/mn>L<\/mi><\/math>, and
\nso:
\n<\/p>\n

\n\n x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n><\/mtd> \u2264<\/mo><\/mtd> 1<\/mn> \u2212<\/mo>\u03bc<\/mi><\/mrow> \nL<\/mi><\/mrow><\/mfrac><\/mrow><\/mfenced><\/mrow>k<\/mi><\/mrow><\/msup \n> x<\/mi><\/mrow>\n0<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n> +<\/mo> 2<\/mn><\/mrow> \nL<\/mi><\/mrow><\/mfrac> f<\/mi>(<\/mo>x<\/mi><\/mrow>0<\/mn><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow><\/mfenced>,<\/mo><\/mtd> <\/mtext><\/mtd>\n<\/mtr> <\/mtd> \u2264<\/mo><\/mtd> 1<\/mn> \u2212<\/mo>\u03bc<\/mi><\/mrow> \nL<\/mi><\/mrow><\/mfrac><\/mrow><\/mfenced><\/mrow>k<\/mi><\/mrow><\/msup \n>2<\/mn> x<\/mi><\/mrow>\n0<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n>.<\/mo> <\/mtd> <\/mtext><\/mtd> <\/mtr><\/mtable>\n<\/math>
\n<\/p>\n

\n

<\/p>\n

The right hand side is obviously a much tighter bound then when
\n2<\/mn>\u2215<\/mo>(<\/mo>\u03bc<\/mi> +<\/mo> L<\/mi><\/mrow>)<\/mo><\/mrow><\/math> is<\/p>\n

used, but the geometric rate is roughly twice as slow.\n<\/p>\n

<\/p>\n

\n

<\/a>Comments<\/h4>\n

<\/p>\n

This proof technique has seen a lot of application lately. It is used for the SAGA
\n[2<\/a>]and SVRG [4<\/a>] methods, and can be applied to accelerated method even, such as
\nthe accelerated coordinate descent theory [8<\/a>]. The Lyapunov function analysis
\ntechnique is of great general utility, and so it is worth studying carefully. It is covered
\nperhaps best in Polyak’s book [10<\/a>].\n<\/p>\n

<\/p>\n

\n

5 <\/span> <\/a>Gradient Norm Descent<\/h3>\n

<\/p>\n

In the strongly convex case, it is actually possible to show that the gradient norm decreases
\nat least linearly as well as the function value and iterates. This requires a \ufb01xed step size
\nof \u03b1<\/mi> =<\/mo> 1<\/mn><\/mrow> \nL<\/mi><\/mrow><\/mfrac><\/math>, as
\nit is not true when line searches are used.\n<\/p>\n
\n<\/p>\n


\n<\/a>
\nLemma 3.<\/span> <\/span>For <\/span>\u03b1<\/mi> =<\/mo> 1<\/mn><\/mrow> \nL<\/mi><\/mrow><\/mfrac><\/math>:<\/span>\n<\/p>\n
\n x<\/mi><\/mrow>k<\/mi>+<\/mo>2<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow>2<\/mn><\/mrow><\/msup \n> \u2264<\/mo> 1<\/mn> \u2212<\/mo>\u03bc<\/mi><\/mrow> \nL<\/mi><\/mrow><\/mfrac><\/mrow><\/mfenced> x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow>2<\/mn><\/mrow><\/msup \n>.<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

<\/p>\n

Note that <\/span> x<\/mi><\/mrow>k<\/mi>+<\/mo>2<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow>2<\/mn><\/mrow><\/msup \n> =<\/mo> 1<\/mn><\/mrow> \nL<\/mi><\/mrow>2<\/mn><\/mrow><\/msup \n><\/mrow><\/mfrac> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n><\/math>
\nand <\/span> x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow>2<\/mn><\/mrow><\/msup \n> =<\/mo> 1<\/mn><\/mrow> \nL<\/mi><\/mrow>2<\/mn><\/mrow><\/msup \n><\/mrow><\/mfrac> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n><\/math>.<\/span><\/p>\n<\/p><\/div>\n

<\/p>\n

\n

\n<\/p>\n


\nProof.<\/span> <\/span>We start by expanding in terms of the step equation
\nx<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n> =<\/mo> x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n> \u2212<\/mo> \u03b1<\/mi>f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow>.<\/mo><\/math>
\n<\/p>\n

\n\n x<\/mi><\/mrow>k<\/mi>+<\/mo>2<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow>2<\/mn><\/mrow><\/msup \n><\/mtd> =<\/mo><\/mtd> x<\/mi><\/mrow>\nk<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n> \u2212<\/mo> \u03b1<\/mi>f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n> +<\/mo> \u03b1<\/mi>f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n> <\/mtd> <\/mtext><\/mtd>\n<\/mtr> <\/mtd> =<\/mo><\/mtd> x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow>2<\/mn><\/mrow><\/msup \n> +<\/mo> \u03b1<\/mi><\/mrow>2<\/mn><\/mrow><\/msup \n> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n><\/mtd> <\/mtext><\/mtd>\n<\/mtr> <\/mtd> <\/mtd> +<\/mo>2<\/mn>\u03b1<\/mi> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow>,<\/mo>x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced> .<\/mo> <\/mtd> <\/mtext><\/mtd> <\/mtr><\/mtable>\n<\/math>
\n<\/p>\n

\n

<\/p>\n

Now applying both inner product bounds (5) and (6):\n<\/p>\n

\n w<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n> \u2212<\/mo> w<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow>2<\/mn><\/mrow><\/msup \n> \u2264<\/mo> 1<\/mn> \u2212<\/mo> \u03b1<\/mi>\u03bc<\/mi><\/mrow><\/mfenced> x<\/mi><\/mrow>\nk<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow>2<\/mn><\/mrow><\/msup \n> +<\/mo> \u03b1<\/mi> \u03b1<\/mi> \u2212<\/mo> 1<\/mn><\/mrow> \nL<\/mi><\/mrow><\/mfrac><\/mrow><\/mfenced> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n>.<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

<\/p>\n

So for \u03b1<\/mi> =<\/mo> 1<\/mn><\/mrow> \nL<\/mi><\/mrow><\/mfrac><\/math>
\nthis simpli\ufb01es to:\n<\/p>\n
\n x<\/mi><\/mrow>k<\/mi>+<\/mo>2<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow>2<\/mn><\/mrow><\/msup \n> \u2264<\/mo> 1<\/mn> \u2212<\/mo>\u03bc<\/mi><\/mrow> \nL<\/mi><\/mrow><\/mfrac><\/mrow><\/mfenced> x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow>2<\/mn><\/mrow><\/msup \n>.<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n \u25a1\n<\/p>\n<\/p><\/div>\n

<\/p>\n

Chaining this result (Lemma 3<\/a>) over
\nk<\/mi><\/math>
\ngives:<\/p>\n

<\/p>\n

\n\n x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow>2<\/mn><\/mrow><\/msup \n><\/mtd> \u2264<\/mo><\/mtd> 1<\/mn> \u2212<\/mo>\u03bc<\/mi><\/mrow> \nL<\/mi><\/mrow><\/mfrac><\/mrow><\/mfenced><\/mrow>k<\/mi><\/mrow><\/msup \n> x<\/mi><\/mrow>\n1<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>0<\/mn><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow>2<\/mn><\/mrow><\/msup \n> <\/mtd> <\/mtext><\/mtd>\n<\/mtr> <\/mtd> =<\/mo><\/mtd> 1<\/mn> \u2212<\/mo>\u03bc<\/mi><\/mrow> \nL<\/mi><\/mrow><\/mfrac><\/mrow><\/mfenced><\/mrow>k<\/mi><\/mrow><\/msup \n> 1<\/mn><\/mrow>\nL<\/mi><\/mrow>2<\/mn><\/mrow><\/msup \n><\/mrow><\/mfrac> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\n0<\/mn><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n>.<\/mo><\/mtd> <\/mtext><\/mtd> <\/mtr><\/mtable>\n<\/math>
\n<\/p>\n

\n

<\/p>\n

We now use f<\/mi>(<\/mo>x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow>)<\/mo><\/mrow> \u2264<\/mo> 1<\/mn><\/mrow> \n2<\/mn>\u03bc<\/mi><\/mrow><\/mfrac> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n> =<\/mo> L<\/mi><\/mrow>2<\/mn><\/mrow><\/msup \n><\/mrow> \n2<\/mn>\u03bc<\/mi><\/mrow><\/mfrac> x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow>2<\/mn><\/mrow><\/msup \n> :<\/mo><\/math>\n<\/p>\n
\n f<\/mi>(<\/mo>x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi>(<\/mo>x<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/mrow>)<\/mo><\/mrow> \u2264<\/mo> 1<\/mn> \u2212<\/mo>\u03bc<\/mi><\/mrow> \nL<\/mi><\/mrow><\/mfrac><\/mrow><\/mfenced><\/mrow>k<\/mi><\/mrow><\/msup \n> 1<\/mn><\/mrow> \n2<\/mn>\u03bc<\/mi><\/mrow><\/mfrac> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\n0<\/mn><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow>2<\/mn><\/mrow><\/msup \n>.<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

<\/p>\n

\n

<\/a>Comments<\/h4>\n

<\/p>\n

This technique is probably the weirdest of those listed here. It has seen
\napplication in proving the convergence rate of MISO under some di\ufb00erent
\nstochastic orderings [1<\/a>]. While clearly a primal result, this proof has some
\ncomponents normally seen in the proof for a dual method. The gradient
\nf<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow><\/math> is
\ne\ufb00ectively the dual iterate. Another interesting property is that the portion of the
\nproof concerning the gradient’s convergence uses the strong convexity between<\/p>\n

x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n><\/math> and
\nx<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/math>,
\nwhereas the other proofs considered all use the degree of strong convexity between
\nx<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/math> and
\nx<\/mi><\/mrow>\u2217<\/mo><\/mrow><\/msup \n><\/math>.\n<\/p>\n

<\/p>\n

This proof technique can’t work when line searches are used, as bounding the
\ninner product:\n<\/p>\n

\n \u03b1<\/mi> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow>,<\/mo>x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced> ,<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

<\/p>\n

would fail if \u03b1<\/mi><\/math>
\nchanged between steps, as it would become
\n \u03b1<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n>f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> \u03b1<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n>f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow>,<\/mo>x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n> \u2212<\/mo> x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced><\/math>,
\nwhich is a weird expression to work with.\n<\/p>\n

<\/p>\n

\n

<\/a>References<\/h3>\n

<\/p>\n

\n

\n


\n <\/a>[1] \u00a0\u00a0\u00a0<\/span><\/span>Aaron Defazio. New Optimization Methods for Machine Learning<\/span>. PhD
\n thesis, Australian National University, 2014.\n <\/p>\n


\n <\/a>[2] \u00a0\u00a0\u00a0<\/span><\/span>Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A
\n fast incremental gradient method with support for non-strongly convex
\n composite objectives. Advances in Neural Information Processing Systems<\/span>
\n 27 (NIPS 2014)<\/span>, 2014.\n <\/p>\n


\n <\/a>[3] \u00a0\u00a0\u00a0<\/span><\/span>David\u00a0R. Hunter and Kenneth Lange. Quantile regression via an mm
\n algorithm. Journal of Computational and Graphical Statistics<\/span>, 9, 2000.\n <\/p>\n


\n <\/a>[4] \u00a0\u00a0\u00a0<\/span><\/span>Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent
\n using predictive variance reduction. NIPS<\/span>, 2013.\n <\/p>\n


\n <\/a>[5] \u00a0\u00a0\u00a0<\/span><\/span>Qiang Liu and Alexander Ihler. Learning scale free networks by
\n reweighted l1 regularization. AISTATS<\/span>, 2011.\n <\/p>\n


\n <\/a>[6] \u00a0\u00a0\u00a0<\/span><\/span>Julien Mairal. Incremental majorization-minimization optimization
\n with application to large-scale machine learning. Technical report, INRIA
\n Grenoble Rh\u00c3\u017dne-Alpes \/ LJK Laboratoire Jean Kuntzmann, 2014.\n <\/p>\n


\n <\/a>[7] \u00a0\u00a0\u00a0<\/span><\/span>Yu. Nesterov. Introductory Lectures On Convex Programming<\/span>. Springer,
\n 1998.\n <\/p>\n


\n <\/a>[8] \u00a0\u00a0\u00a0<\/span><\/span>Yu. Nesterov. E\ufb03ciency of coordinate descent methods on huge-scale
\n optimization problems. Technical report, CORE, 2010.\n <\/p>\n


\n <\/a>[9] \u00a0\u00a0\u00a0<\/span><\/span>Yu. Nesterov and B.T. Polyak. Cubic regularization of newton method
\n and its global performance. Mathematical Programming<\/span>, 108(1):177\u2013205,
\n 2006.\n <\/p>\n


\n<\/a>[10] \u00a0\u00a0\u00a0<\/span><\/span>Boris Polyak. Introduction to Optimization<\/span>. Optimization Software,
\n Inc., Publications Division., 1987.\n<\/p>\n<\/p><\/div>\n","protected":false},"excerpt":{"rendered":"

Consider the classical gradient descent method: xk+1 = xk \u2212 \u03b1f\u2032(x k). It’s a thing of beauty isn’t it? While it’s not used directly in practice any more, the proof techniques used in its analysis are the building blocks behind the theory of more advanced optimization methods. I know of 8 di\ufb00erent ways of proving … Continue reading The Many Ways to Analyse Gradient Descent<\/span> →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/www.aarondefazio.com\/tangentially\/index.php?rest_route=\/wp\/v2\/posts\/32"}],"collection":[{"href":"https:\/\/www.aarondefazio.com\/tangentially\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.aarondefazio.com\/tangentially\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.aarondefazio.com\/tangentially\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.aarondefazio.com\/tangentially\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=32"}],"version-history":[{"count":4,"href":"https:\/\/www.aarondefazio.com\/tangentially\/index.php?rest_route=\/wp\/v2\/posts\/32\/revisions"}],"predecessor-version":[{"id":101,"href":"https:\/\/www.aarondefazio.com\/tangentially\/index.php?rest_route=\/wp\/v2\/posts\/32\/revisions\/101"}],"wp:attachment":[{"href":"https:\/\/www.aarondefazio.com\/tangentially\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=32"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.aarondefazio.com\/tangentially\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=32"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.aarondefazio.com\/tangentially\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=32"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}