<\/title> \n<meta charset=\"UTF-8\" \/> \n<meta name=\"generator\" content=\"TeX4ht (http:\/\/www.cse.ohio-state.edu\/~gurari\/TeX4ht\/)\" \/>\n<link rel=\"stylesheet\" type=\"text\/css\" href=\"GradientDescentNonSC.css\" \/>\n<\/p>\n<a href=\"http:\/\/www.aarondefazio.com\/tangentially\/?p=32\">The previous post<\/a> detailed a bunch of different ways of proving the convergence rate \nof gradient descent:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-rel\">=<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>\u03b1<\/mi><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><mo \nclass=\"MathClass-punc\">,<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n for strongly convex problems. This post considers the non-strongly convex, but \nstill convex case.\n<\/p>\n<h3 class=\"likesectionHead\"><a \n id=\"x1-1000\"><\/a>Rehash of Basic Lemmas<\/h3>\n<\/p>\nThese hold for any <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>x<\/mi><\/math> \nand <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>y<\/mi><\/math>. \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>L<\/mi><\/math> \nthe Lipschitz smoothness constant. These are completely \nstandard, see Nesterov’s book [<a \nhref=\"#Xnes-book\">2<\/a>]<\/span> for proofs. We use the notation \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/math> for an arbitrary \nminimizer of <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>f<\/mi><\/math>.\n<\/p>\n<table class=\"equation\">\n<tr>\n<td> <a \n id=\"x1-1001r1\"><\/a> \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" class=\"equation\">\n <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>y<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>x<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">+<\/mo> <mfenced separators=\"\" \nopen=\"\u27e8\" close=\"\u27e9\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>x<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><mo \nclass=\"MathClass-punc\">,<\/mo><mi \n>y<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>x<\/mi><\/mrow><\/mfenced> <mo \nclass=\"MathClass-bin\">+<\/mo> <mfrac><mrow \n><mi \n>L<\/mi><\/mrow> \n<mrow \n><mn>2<\/mn><\/mrow><\/mfrac><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><mi \n>x<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>y<\/mi><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/math><\/td>\n<td class=\"eq-no\">(1)<\/td>\n<\/tr>\n<\/table>\n<table class=\"equation\">\n<tr>\n<td> <a \n id=\"x1-1002r2\"><\/a> \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" class=\"equation\">\n <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>y<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-rel\">\u2265<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>x<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">+<\/mo> <mfenced separators=\"\" \nopen=\"\u27e8\" close=\"\u27e9\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>x<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><mo \nclass=\"MathClass-punc\">,<\/mo><mi \n>y<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>x<\/mi><\/mrow><\/mfenced> <mo \nclass=\"MathClass-bin\">+<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><mn>2<\/mn><mi \n>L<\/mi><\/mrow><\/mfrac><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>x<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>y<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/math><\/td>\n<td class=\"eq-no\">(2)<\/td>\n<\/tr>\n<\/table>\n<table class=\"equation\">\n<tr>\n<td> <a \n id=\"x1-1003r3\"><\/a> \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" class=\"equation\">\n <mfenced separators=\"\" \nopen=\"\u27e8\" close=\"\u27e9\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>x<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>y<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><mo \nclass=\"MathClass-punc\">,<\/mo><mi \n>x<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>y<\/mi><\/mrow><\/mfenced> <mo \nclass=\"MathClass-rel\">\u2265<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><mi \n>L<\/mi><\/mrow><\/mfrac><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>x<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>y<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/math><\/td>\n<td class=\"eq-no\">(3)<\/td>\n<\/tr>\n<\/table>\n<\/p>\n\n<h3 class=\"sectionHead\">1 <\/span> <a \n id=\"x1-20001\"><\/a>Proximal Style Convergence Proof<\/h3>\n<\/p>\nThe following argument gives a proof of convergence that is well suited to \nmodi\ufb01cation for proving the convergence of proximal gradient methods. We start by \nproving a useful lemma:\n<\/p>\n<div class=\"newtheorem\">\n<\/p>\n \n<a \n id=\"x1-2001r1\"><\/a> \nLemma 1.<\/span> <\/span>For any <\/span><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/math> \nand <\/span><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>y<\/mi><\/math>,<\/span> \nwhen <\/span><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-rel\">=<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><mi \n>L<\/mi><\/mrow><\/mfrac><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/math>:<\/span>\n<\/p>\n<div class=\"par-math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mfrac><mrow \n><mn>2<\/mn><\/mrow> \n<mrow \n><mi \n>L<\/mi><\/mrow><\/mfrac> <mfenced separators=\"\" \nopen=\"[\" close=\"]\" ><mrow><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>y<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced> <mo \nclass=\"MathClass-rel\">\u2265<\/mo><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><mi \n>y<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo><msup><mrow \n><mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>y<\/mi><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p><\/div>\n<\/p>\n\n<div class=\"proof\">\n<\/p>\n \nProof.<\/span> <\/span>We start with the Lipschitz upper bound around <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/math> \nof <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/math>:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">+<\/mo> <mfenced separators=\"\" \nopen=\"\u27e8\" close=\"\u27e9\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><mo \nclass=\"MathClass-punc\">,<\/mo><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced> <mo \nclass=\"MathClass-bin\">+<\/mo> <mfrac><mrow \n><mi \n>L<\/mi><\/mrow> \n<mrow \n><mn>2<\/mn><\/mrow><\/mfrac><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n Now we bound <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/math> \nusing the negated convexity lower bound of <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>y<\/mi><\/math> \naround <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>x<\/mi><\/math> \n(i.e. <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>y<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-rel\">\u2265<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">+<\/mo> <mfenced separators=\"\" \nopen=\"\u27e8\" close=\"\u27e9\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><mo \nclass=\"MathClass-punc\">,<\/mo><mi \n>y<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced><\/math>):\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>y<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">+<\/mo> <mfenced separators=\"\" \nopen=\"\u27e8\" close=\"\u27e9\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><mo \nclass=\"MathClass-punc\">,<\/mo><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">+<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>y<\/mi><\/mrow><\/mfenced> <mo \nclass=\"MathClass-bin\">+<\/mo> <mfrac><mrow \n><mi \n>L<\/mi><\/mrow> \n<mrow \n><mn>2<\/mn><\/mrow><\/mfrac><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n Negating, rearranging and multiplying through by \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" > <mfrac><mrow \n><mn>2<\/mn><\/mrow>\n<mrow \n><mi \n>L<\/mi><\/mrow><\/mfrac><\/math> \ngives:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mfrac><mrow \n><mn>2<\/mn><\/mrow> \n<mrow \n><mi \n>L<\/mi><\/mrow><\/mfrac> <mfenced separators=\"\" \nopen=\"[\" close=\"]\" ><mrow><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>y<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced> <mo \nclass=\"MathClass-rel\">\u2265<\/mo> <mfrac><mrow \n><mn>2<\/mn><\/mrow> \n<mrow \n><mi \n>L<\/mi><\/mrow><\/mfrac> <mfenced separators=\"\" \nopen=\"\u27e8\" close=\"\u27e9\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><mo \nclass=\"MathClass-punc\">,<\/mo><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>y<\/mi><\/mrow><\/mfenced> <mo \nclass=\"MathClass-bin\">+<\/mo><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n Now we replace <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/math> \nusing <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-rel\">=<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><mi \n>L<\/mi><\/mrow><\/mfrac><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/math>:<\/p>\n<\/p>\n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" >\n<mtable \nclass=\"eqnarray-star\" columnalign=\"right center left\" >\n<mtr><mtd \nclass=\"eqnarray-1\"> <mfrac><mrow \n><mn>2<\/mn><\/mrow>\n<mrow \n><mi \n>L<\/mi><\/mrow><\/mfrac> <mfenced separators=\"\" \nopen=\"[\" close=\"]\" ><mrow><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>y<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><\/mtd><mtd \nclass=\"eqnarray-2\"> <mo \nclass=\"MathClass-rel\">\u2265<\/mo><\/mtd><mtd \nclass=\"eqnarray-3\"> <mn>2<\/mn> <mfenced separators=\"\" \nopen=\"\u27e8\" close=\"\u27e9\" ><mrow><mi \n>y<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><mspace width=\"0.3em\" class=\"thinspace\"\/><mo \nclass=\"MathClass-punc\">,<\/mo><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfenced> <mo \nclass=\"MathClass-bin\">\u2212<\/mo><msup><mrow \n><mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n> <\/mtd><mtd \nclass=\"eqnarray-4\"> <mtext class=\"eqnarray\"><\/mtext><\/mtd>\n<\/mtr><mtr><mtd \nclass=\"eqnarray-1\"> <\/mtd><mtd \nclass=\"eqnarray-2\"> <mo \nclass=\"MathClass-rel\">=<\/mo><\/mtd><mtd \nclass=\"eqnarray-3\"> <mn>2<\/mn> <mfenced separators=\"\" \nopen=\"\u27e8\" close=\"\u27e9\" ><mrow><mi \n>y<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">+<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><mspace width=\"0.3em\" class=\"thinspace\"\/><mo \nclass=\"MathClass-punc\">,<\/mo><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfenced> <mo \nclass=\"MathClass-bin\">\u2212<\/mo><msup><mrow \n><mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><\/mtd><mtd \nclass=\"eqnarray-4\"> <mtext class=\"eqnarray\"><\/mtext><\/mtd>\n<\/mtr><mtr><mtd \nclass=\"eqnarray-1\"> <\/mtd><mtd \nclass=\"eqnarray-2\"> <mo \nclass=\"MathClass-rel\">=<\/mo><\/mtd><mtd \nclass=\"eqnarray-3\"> <mn>2<\/mn> <mfenced separators=\"\" \nopen=\"\u27e8\" close=\"\u27e9\" ><mrow><mi \n>y<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><mo \nclass=\"MathClass-punc\">,<\/mo><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfenced> <mo \nclass=\"MathClass-bin\">+<\/mo> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfenced> <msup><mrow \n><mo \nclass=\"MathClass-punc\">.<\/mo><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n> <\/mtd><mtd \nclass=\"eqnarray-4\"> <mtext class=\"eqnarray\"><\/mtext><\/mtd> <\/mtr><\/mtable>\n<\/math> \n<\/p>\n\n<\/p>\n Now we complete the square using the quadratic \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><mi \n>y<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">+<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n> <mo \nclass=\"MathClass-rel\">=<\/mo><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><mi \n>y<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n> <mo \nclass=\"MathClass-bin\">+<\/mo> <mn>2<\/mn> <mfenced separators=\"\" \nopen=\"\u27e8\" close=\"\u27e9\" ><mrow><mi \n>y<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><mo \nclass=\"MathClass-punc\">,<\/mo><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfenced> <mo \nclass=\"MathClass-bin\">+<\/mo><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><\/math>. So \nwe have: \n<\/p>\n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" >\n<mtable \nclass=\"eqnarray-star\" columnalign=\"right center left\" >\n<mtr><mtd \nclass=\"eqnarray-1\"> <mfrac><mrow \n><mn>2<\/mn><\/mrow>\n<mrow \n><mi \n>L<\/mi><\/mrow><\/mfrac> <mfenced separators=\"\" \nopen=\"[\" close=\"]\" ><mrow><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>y<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><\/mtd><mtd \nclass=\"eqnarray-2\"> <mo \nclass=\"MathClass-rel\">\u2265<\/mo><\/mtd><mtd \nclass=\"eqnarray-3\"> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><mi \n>y<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">+<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfenced> <mo \nclass=\"MathClass-bin\">\u2212<\/mo><msup><mrow \n><mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><mi \n>y<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><\/mtd><mtd \nclass=\"eqnarray-4\"> <mtext class=\"eqnarray\"><\/mtext><\/mtd>\n<\/mtr><mtr><mtd \nclass=\"eqnarray-1\"> <\/mtd><mtd \nclass=\"eqnarray-2\"> <mo \nclass=\"MathClass-rel\">=<\/mo><\/mtd><mtd \nclass=\"eqnarray-3\"> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><mi \n>y<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfenced> <mo \nclass=\"MathClass-bin\">\u2212<\/mo><msup><mrow \n><mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><mi \n>y<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><mo \nclass=\"MathClass-punc\">.<\/mo> <\/mtd><mtd \nclass=\"eqnarray-4\"> <mtext class=\"eqnarray\"><\/mtext><\/mtd> <\/mtr><\/mtable>\n<\/math> \n<\/p>\n\n \u25a1\n<\/p>\n<\/p><\/div>\n<\/p>\n Using this lemma, the proof is quite simple. We apply it with \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>y<\/mi> <mo \nclass=\"MathClass-rel\">=<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/math>:\n<\/p>\n<div class=\"par-math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n><msup><mrow \n>\n <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo><msup><mrow \n><mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n> <mo \nclass=\"MathClass-rel\">\u2264<\/mo><mo \nclass=\"MathClass-bin\">\u2212<\/mo><mfrac><mrow \n><mn>2<\/mn><\/mrow>\n<mrow \n><mi \n>L<\/mi><\/mrow><\/mfrac> <mfenced separators=\"\" \nopen=\"[\" close=\"]\" ><mrow><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n Now we sum this between <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mn>0<\/mn><\/math> \nand <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>k<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mn>1<\/mn><\/math>. \nThe left hand side telescopes:\n<\/p>\n<div class=\"par-math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n><msup><mrow \n>\n <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo><msup><mrow \n><mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mn>0<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n> <mo \nclass=\"MathClass-rel\">\u2264<\/mo><mo \nclass=\"MathClass-bin\">\u2212<\/mo><mfrac><mrow \n><mn>2<\/mn><\/mrow>\n<mrow \n><mi \n>L<\/mi><\/mrow><\/mfrac><munderover accentunder=\"false\" accent=\"false\"><mrow \n><mo mathsize=\"big\" \n>\u2211<\/mo>\n <\/mrow><mrow \n><mi \n>r<\/mi><mo \nclass=\"MathClass-rel\">=<\/mo><mn>0<\/mn><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">\u2212<\/mo><mn>1<\/mn><\/mrow><\/munderover \n> <mfenced separators=\"\" \nopen=\"[\" close=\"]\" ><mrow><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>r<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n Now we use the fact that gradient descent <\/span>is a descent method, which implies that \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>r<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/math> for all \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>r<\/mi> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mi \n>k<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mn>1<\/mn><\/math>. \nSo:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n><msup><mrow \n>\n <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo><msup><mrow \n><mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mn>0<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n> <mo \nclass=\"MathClass-rel\">\u2264<\/mo><mo \nclass=\"MathClass-bin\">\u2212<\/mo><mfrac><mrow \n><mn>2<\/mn><mi \n>k<\/mi><\/mrow>\n<mrow \n><mi \n>L<\/mi><\/mrow><\/mfrac> <mfenced separators=\"\" \nopen=\"[\" close=\"]\" ><mrow><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n Now we just drop the <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><\/math> \nterm since it is positive and small. Leaving:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mfrac><mrow \n><mi \n>L<\/mi><\/mrow> \n<mrow \n><mn>2<\/mn><mi \n>k<\/mi><\/mrow><\/mfrac><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n\n<h4 class=\"likesubsectionHead\"><a \n id=\"x1-30001\"><\/a>Comments<\/h4>\n<\/p>\nAs far as I know, this proof is fairly modern [<a \nhref=\"#Xbeckt-gradient\">1<\/a>]<\/span>. Notice that \nunlike the strongly convex case, the quantity we are bounding \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/math> does \nnot appear on both sides of the bound. Unfortunately, without strong convexity \nthere is necessarily a looseness to the bounds, and this takes the form of \nbounding function value by distance to solution, with a large wiggle-factor. One \nthing that is perhaps a little confusing is the use of distance to solution \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>x<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/math>, \nwhen it is not unique, as there are potentially multiple minimizers for<\/p>\nnon-strongly convex problems. The bound in fact holds for any chosen minimizer \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/math>. I \nfound this to be a little confusing at \ufb01rst.\n<\/p>\n<\/p>\n\n<h3 class=\"sectionHead\">2 <\/span> <a \n id=\"x1-40002\"><\/a>Older Style Proof<\/h3>\n<\/p>\nThis proof is from Nesterov [<a \nhref=\"#Xnes-book\">2<\/a>]<\/span>. I’m not sure of the original source for it.\n<\/p>\n<\/p>\n We start with the function value descent equation, using \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>w<\/mi> <mo \nclass=\"MathClass-punc\">:<\/mo><mo \nclass=\"MathClass-rel\">=<\/mo> <mfenced separators=\"\" \nopen=\"[\" close=\"]\" ><mrow><mi \n>\u03b1<\/mi> <mfenced separators=\"\" \nopen=\"(\" close=\")\" ><mrow><mn>1<\/mn> <mo \nclass=\"MathClass-bin\">\u2212<\/mo><mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><mn>2<\/mn><\/mrow><\/mfrac><mi \n>\u03b1<\/mi><mi \n>L<\/mi><\/mrow><\/mfenced><\/mrow><\/mfenced> <mo \nclass=\"MathClass-punc\">:<\/mo><\/math>\n<\/p>\n<div class=\"par-math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>w<\/mi><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n We introduce the simpli\ufb01ed notation <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-rel\">=<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/math> \nso that we have <\/p>\n<table class=\"equation\">\n<tr>\n<td> <a \n id=\"x1-4001r4\"><\/a> \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" class=\"equation\">\n <msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>w<\/mi><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/math><\/td>\n<td class=\"eq-no\">(4)<\/td>\n<\/tr>\n<\/table>\n<\/p>\n Now using the convexity lower bound around \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/math> evaluated \nat <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/math>, \nnamely:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mfenced separators=\"\" \nopen=\"\u27e8\" close=\"\u27e9\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><mo \nclass=\"MathClass-punc\">,<\/mo><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><mo \nclass=\"MathClass-punc\">,<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n and applying Cauchy-Schwarz (note the spelling! there is no \u201ct\u201d in Schwarz) to \nit: \n<\/p>\n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" >\n<mtable \nclass=\"eqnarray-star\" columnalign=\"right center left\" >\n<mtr><mtd \nclass=\"eqnarray-1\"> <msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mtd><mtd \nclass=\"eqnarray-2\"> <mo \nclass=\"MathClass-rel\">\u2264<\/mo><\/mtd><mtd \nclass=\"eqnarray-3\"> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced> <\/mtd><mtd \nclass=\"eqnarray-4\"> <mtext class=\"eqnarray\"><\/mtext><\/mtd>\n<\/mtr><mtr><mtd \nclass=\"eqnarray-1\"> <\/mtd><mtd \nclass=\"eqnarray-2\"> <mo \nclass=\"MathClass-rel\">\u2264<\/mo><\/mtd><mtd \nclass=\"eqnarray-3\"> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><mo \nclass=\"MathClass-punc\">.<\/mo><\/mtd><mtd \nclass=\"eqnarray-4\"> <mtext class=\"eqnarray\"><\/mtext><\/mtd> <\/mtr><\/mtable>\n<\/math> \n<\/p>\n\n<\/p>\n The last line is because gradient descent method descends in \niterate distance each step. We now introduce the additional notation \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msub><mrow \n><mi \n>r<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-rel\">=<\/mo> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/math>. \nUsing this notation and rearranging gives:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mo \nclass=\"MathClass-bin\">\u2212<\/mo><mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced> <mo \nclass=\"MathClass-rel\">\u2264<\/mo><mo \nclass=\"MathClass-bin\">\u2212<\/mo><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><mo \nclass=\"MathClass-bin\">\u2215<\/mo><msub><mrow \n><mi \n>r<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><\/msub \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n We plug this into the function descent equation (Eq <a \nhref=\"#x1-4001r4\">4<\/a>) above to get:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mfrac><mrow \n><mi \n>w<\/mi><\/mrow> \n<mrow \n><msubsup><mrow \n><mi \n>r<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msubsup \n><\/mrow><\/mfrac><msubsup><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msubsup \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n We now divide this through by <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/math>:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mn>1<\/mn> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mfrac><mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow> \n<mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfrac> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mfrac><mrow \n><mi \n>w<\/mi><\/mrow> \n<mrow \n><msubsup><mrow \n><mi \n>r<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msubsup \n><\/mrow><\/mfrac> <mfrac><mrow \n><msubsup><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msubsup \n><\/mrow> \n<mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfrac>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n Then divide through by <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/math> \nalso:\n<\/p>\n<div class=\"par-math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfrac> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfrac> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mfrac><mrow \n><mi \n>w<\/mi><\/mrow> \n<mrow \n><msubsup><mrow \n><mi \n>r<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msubsup \n><\/mrow><\/mfrac> <mfrac><mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow> \n<mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfrac><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n Now we use the fact that gradient descent is a descent method again, which implies \nthat <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" > <mfrac><mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow>\n<mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfrac> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mn>1<\/mn><mo \nclass=\"MathClass-punc\">,<\/mo><\/math> \nso:\n<\/p>\n<div class=\"par-math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfrac> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfrac> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mfrac><mrow \n><mi \n>w<\/mi><\/mrow> \n<mrow \n><msubsup><mrow \n><mi \n>r<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msubsup \n><\/mrow><\/mfrac><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mo \nclass=\"MathClass-rel\">\u2234<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfrac> <mo \nclass=\"MathClass-rel\">\u2265<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfrac> <mo \nclass=\"MathClass-bin\">+<\/mo> <mfrac><mrow \n><mi \n>w<\/mi><\/mrow> \n<mrow \n><msubsup><mrow \n><mi \n>r<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msubsup \n><\/mrow><\/mfrac><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n We then chain this inequality for each \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>k<\/mi><\/math>:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfrac> <mo \nclass=\"MathClass-rel\">\u2265<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfrac> <mo \nclass=\"MathClass-bin\">+<\/mo> <mfrac><mrow \n><mi \n>w<\/mi><\/mrow> \n<mrow \n><msubsup><mrow \n><mi \n>r<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msubsup \n><\/mrow><\/mfrac> <mo \nclass=\"MathClass-rel\">\u2265<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">\u2212<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfrac> <mo \nclass=\"MathClass-bin\">+<\/mo> <mn>2<\/mn> <mfrac><mrow \n><mi \n>w<\/mi><\/mrow>\n<mrow \n><msubsup><mrow \n><mi \n>r<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msubsup \n><\/mrow><\/mfrac> <mo \nclass=\"MathClass-rel\">\u2265<\/mo><mo \nclass=\"MathClass-rel\">\u22ef<\/mo> <mo \nclass=\"MathClass-rel\">\u2265<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><\/msub \n><\/mrow><\/mfrac> <mo \nclass=\"MathClass-bin\">+<\/mo> <mfrac><mrow \n><mi \n>w<\/mi><\/mrow> \n<mrow \n><msubsup><mrow \n><mi \n>r<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msubsup \n><\/mrow><\/mfrac><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>k<\/mi> <mo \nclass=\"MathClass-bin\">+<\/mo> <mn>1<\/mn><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mo \nclass=\"MathClass-rel\">\u2234<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfrac> <mo \nclass=\"MathClass-rel\">\u2265<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><\/msub \n><\/mrow><\/mfrac> <mo \nclass=\"MathClass-bin\">+<\/mo> <mfrac><mrow \n><mi \n>w<\/mi><\/mrow> \n<mrow \n><msubsup><mrow \n><mi \n>r<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msubsup \n><\/mrow><\/mfrac><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>k<\/mi> <mo \nclass=\"MathClass-bin\">+<\/mo> <mn>1<\/mn><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n To get the \ufb01nal convergence rate we invert both sides:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mfrac><mrow \n><mfenced separators=\"\" \nopen=\"[\" close=\"]\" ><mrow><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mn>0<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><\/mrow> \n<mrow \n><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n> <mo \nclass=\"MathClass-bin\">+<\/mo> <mi \n>w<\/mi> <mfenced separators=\"\" \nopen=\"[\" close=\"]\" ><mrow><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><mi \n>k<\/mi><\/mrow><\/mfrac><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n This is quite a complex expression. To simplify even further, we can get rid of the \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/math> \nterms on the right hand side using the Lipschitz upper bound about \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/math>:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mfrac><mrow \n><mi \n>L<\/mi><\/mrow> \n<mrow \n><mn>2<\/mn><\/mrow><\/mfrac><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><mi \n>x<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n Plugging in the step size <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>\u03b1<\/mi> <mo \nclass=\"MathClass-rel\">=<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><mi \n>L<\/mi><\/mrow><\/mfrac><\/math> \ngives <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>w<\/mi> <mo \nclass=\"MathClass-rel\">=<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><mn>2<\/mn><mi \n>L<\/mi><\/mrow><\/mfrac><\/math>, \nyielding the following simpler convergence rate:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mfrac><mrow \n><mn>2<\/mn><mi \n>L<\/mi><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><\/mrow> \n <mrow \n><mi \n>k<\/mi> <mo \nclass=\"MathClass-bin\">+<\/mo> <mn>4<\/mn><\/mrow><\/mfrac> <mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n Compared to the rate from the previous proof, \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mfrac><mrow \n><mi \n>L<\/mi><\/mrow> \n<mrow \n><mn>2<\/mn><mi \n>k<\/mi><\/mrow><\/mfrac><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><\/msup \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><\/math>, this is slightly \nbetter at <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>k<\/mi> <mo \nclass=\"MathClass-rel\">=<\/mo> <mn>1<\/mn><\/math>, \nand worse thereafter.\n<\/p>\n<\/p>\n\n<h4 class=\"likesubsectionHead\"><a \n id=\"x1-50002\"><\/a>Comments<\/h4>\n<\/p>\nI don’t like this proof. It’s feels like a random sequence of steps when \nyou \ufb01rst look at it. The way the proof uses inverse quantities like \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" > <mfrac><mrow \n><mn>1<\/mn><\/mrow>\n<mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfrac><\/math> \nis also confusing. The key equation is really the direct bound on \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>\u0394<\/mi><\/math>:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mfrac><mrow \n><mi \n>w<\/mi><\/mrow> \n<mrow \n><msubsup><mrow \n><mi \n>r<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msubsup \n><\/mrow><\/mfrac><msubsup><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msubsup \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n Often this is the kind of equation you encounter when proving the properties of \ndual methods for example. Equations of this kind can be encountered when applying<\/p>\nproximal methods to non-di\ufb00erentiable functions also. It is also quite a clear \nstatement about what is going on in terms of per-step convergence, a property that is \nless clear in the previous proof.\n<\/p>\n<\/p>\n\n<h3 class=\"sectionHead\">3 <\/span> <a \n id=\"x1-60003\"><\/a>Gradient Concentration<\/h3>\n<\/p>\nWhen we don’t even have convexity, just Lipschitz smoothness, we can still prove \nsomething about convergence of the gradient norm. The Lipschitz upper bound holds \nwithout the requirement of convexity:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>y<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>x<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">+<\/mo> <mfenced separators=\"\" \nopen=\"\u27e8\" close=\"\u27e9\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>x<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><mo \nclass=\"MathClass-punc\">,<\/mo><mi \n>y<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>x<\/mi><\/mrow><\/mfenced> <mo \nclass=\"MathClass-bin\">+<\/mo> <mfrac><mrow \n><mi \n>L<\/mi><\/mrow> \n<mrow \n><mn>2<\/mn><\/mrow><\/mfrac><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><mi \n>x<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>y<\/mi><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n Recall that from minimizing this bound with respect to \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>y<\/mi><\/math> we \ncan prove the equation:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-rel\">\u2265<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><mn>2<\/mn><mi \n>L<\/mi><\/mrow><\/mfrac><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n Examine this equation carefully. We have a bound on each gradient encountered \nduring the optimization in terms of the di\ufb00erence in function values between steps. \nThe sequence of function values is bounded below, so in fact we have a hard bound \non the sum of the encountered gradient norms. E\ufb00ectively, we chain (telescope) the \nabove inequality over steps:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">\u2212<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">+<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-rel\">\u2265<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><mn>2<\/mn><mi \n>L<\/mi><\/mrow><\/mfrac><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n> <mo \nclass=\"MathClass-bin\">+<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><mn>2<\/mn><mi \n>L<\/mi><\/mrow><\/mfrac><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">\u2212<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mo \nclass=\"MathClass-punc\">.<\/mo><mo \nclass=\"MathClass-punc\">.<\/mo><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-rel\">\u2265<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><mn>2<\/mn><mi \n>L<\/mi><\/mrow><\/mfrac><munderover accentunder=\"false\" accent=\"false\"><mrow \n><mo mathsize=\"big\" \n>\u2211<\/mo>\n <\/mrow><mrow \n><mi \n>i<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/munderover \n><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>i<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n Now since <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-rel\">\u2265<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/math>:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <munderover accentunder=\"false\" accent=\"false\"><mrow \n><mo mathsize=\"big\" \n>\u2211<\/mo>\n <\/mrow><mrow \n><mi \n>i<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/munderover \n><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>i<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mn>2<\/mn><mi \n>L<\/mi> <mfenced separators=\"\" \nopen=\"(\" close=\")\" ><mrow><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mn>0<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n Now to make this bound a little more concrete, we can put it in terms of the gradient \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msub><mrow \n><mi \n>g<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/math> \nwith the smallest norm seen during the minimization \n(<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" > <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>g<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>g<\/mi><\/mrow><mrow \n><mi \n>i<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced><\/math> for all \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>i<\/mi><\/math>), so \nthat <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msubsup><mrow \n><mo \nclass=\"MathClass-op\"> \u2211<\/mo>\n <\/mrow><mrow \n><mi \n>i<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msubsup \n><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>i<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n> <mo \nclass=\"MathClass-rel\">\u2265<\/mo> <mi \n>k<\/mi><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>g<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><\/math>, \nso:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n><msup><mrow \n>\n <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>g<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mfrac><mrow \n><mn>2<\/mn><mi \n>L<\/mi><\/mrow> \n <mrow \n><mi \n>k<\/mi><\/mrow><\/mfrac> <mfenced separators=\"\" \nopen=\"(\" close=\")\" ><mrow><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n\n<h4 class=\"likesubsectionHead\"><a \n id=\"x1-70003\"><\/a>Comments<\/h4>\n<\/p>\nNotice that the core technique used in this proof is the same as the last 2 proofs. \nWe have a single step inequality bounding one of the quantities we care \nabout. By summing that inequality over each step of minimization, one side \nof the inequality telescopes. We get an equality saying the the sum of the \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>k<\/mi><\/math> versions \nof that quantity (one from each step) is less then some \ufb01xed constant independent of \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>k<\/mi><\/math>, for any \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>k<\/mi><\/math>. The convergence rate is \nthus of the form <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mn>1<\/mn><mo \nclass=\"MathClass-bin\">\u2215<\/mo><mi \n>k<\/mi><\/math>, because \nthe summation of the <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>k<\/mi><\/math> \nquantities \ufb01ts in a \ufb01xed bound.\n<\/p>\n<\/p>\n Almost any proof for an optimization method that applies in the non-convex case \nuses a similar proof technique. There is just not that many assumptions to work \nwith, so the options are limited.\n<\/p>\n<\/p>\n\n<h3 class=\"likesectionHead\"><a \n id=\"x1-80003\"><\/a>References<\/h3>\n<\/p>\n\n<div class=\"thebibliography\">\n \n [1]\u00a0\u00a0\u00a0<\/span><\/span><a \n id=\"Xbeckt-gradient\"><\/a>Amir Beck and Marc Teboulle. Gradient-based algorithms with \n applications to signal recovery problems. Convex Optimization in Signal<\/span> \n Processing and Communications<\/span>, 2009.<\/p>\n \n [2]\u00a0\u00a0\u00a0<\/span><\/span><a \n id=\"Xnes-book\"><\/a>Yu. Nesterov. Introductory Lectures On Convex Programming<\/span>. Springer, \n 1998.\n<\/p>\n<\/p><\/div>\n","protected":false},"excerpt":{"rendered":"The previous post detailed a bunch of different ways of proving the convergence rate of gradient descent: xk+1 = xk \u2212 \u03b1f\u2032(x k), for strongly convex problems. This post considers the non-strongly convex, but still convex case. Rehash of Basic Lemmas These hold for any x and y. L the Lipschitz smoothness constant. These are … <a href=\"https:\/\/www.aarondefazio.com\/tangentially\/?p=35\" class=\"more-link\">Continue reading The Many Ways to Analyse Gradient Descent: Part 2<\/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\/35"}],"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=35"}],"version-history":[{"count":2,"href":"https:\/\/www.aarondefazio.com\/tangentially\/index.php?rest_route=\/wp\/v2\/posts\/35\/revisions"}],"predecessor-version":[{"id":37,"href":"https:\/\/www.aarondefazio.com\/tangentially\/index.php?rest_route=\/wp\/v2\/posts\/35\/revisions\/37"}],"wp:attachment":[{"href":"https:\/\/www.aarondefazio.com\/tangentially\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=35"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.aarondefazio.com\/tangentially\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=35"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.aarondefazio.com\/tangentially\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=35"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}

{"id":35,"date":"2015-10-15T22:52:58","date_gmt":"2015-10-15T22:52:58","guid":{"rendered":"http:\/\/www.aarondefazio.com\/tangentially\/?p=35"},"modified":"2019-04-29T21:08:02","modified_gmt":"2019-04-29T21:08:02","slug":"the-many-ways-to-analyse-gradient-descent-part-2","status":"publish","type":"post","link":"https:\/\/www.aarondefazio.com\/tangentially\/?p=35","title":{"rendered":"The Many Ways to Analyse Gradient Descent: Part 2"},"content":{"rendered":"

\n
\n <\/title> \n<meta charset=\"UTF-8\" \/> \n<meta name=\"generator\" content=\"TeX4ht (http:\/\/www.cse.ohio-state.edu\/~gurari\/TeX4ht\/)\" \/>\n<link rel=\"stylesheet\" type=\"text\/css\" href=\"GradientDescentNonSC.css\" \/>\n<\/p>\n<a href=\"http:\/\/www.aarondefazio.com\/tangentially\/?p=32\">The previous post<\/a> detailed a bunch of different ways of proving the convergence rate \nof gradient descent:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-rel\">=<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>\u03b1<\/mi><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><mo \nclass=\"MathClass-punc\">,<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n for strongly convex problems. This post considers the non-strongly convex, but \nstill convex case.\n<\/p>\n<h3 class=\"likesectionHead\"><a \n id=\"x1-1000\"><\/a>Rehash of Basic Lemmas<\/h3>\n<\/p>\nThese hold for any <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>x<\/mi><\/math> \nand <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>y<\/mi><\/math>. \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>L<\/mi><\/math> \nthe Lipschitz smoothness constant. These are completely \nstandard, see Nesterov’s book [<a \nhref=\"#Xnes-book\">2<\/a>]<\/span> for proofs. We use the notation \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/math> for an arbitrary \nminimizer of <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>f<\/mi><\/math>.\n<\/p>\n<table class=\"equation\">\n<tr>\n<td> <a \n id=\"x1-1001r1\"><\/a> \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" class=\"equation\">\n <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>y<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>x<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">+<\/mo> <mfenced separators=\"\" \nopen=\"\u27e8\" close=\"\u27e9\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>x<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><mo \nclass=\"MathClass-punc\">,<\/mo><mi \n>y<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>x<\/mi><\/mrow><\/mfenced> <mo \nclass=\"MathClass-bin\">+<\/mo> <mfrac><mrow \n><mi \n>L<\/mi><\/mrow> \n<mrow \n><mn>2<\/mn><\/mrow><\/mfrac><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><mi \n>x<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>y<\/mi><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/math><\/td>\n<td class=\"eq-no\">(1)<\/td>\n<\/tr>\n<\/table>\n<table class=\"equation\">\n<tr>\n<td> <a \n id=\"x1-1002r2\"><\/a> \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" class=\"equation\">\n <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>y<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-rel\">\u2265<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>x<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">+<\/mo> <mfenced separators=\"\" \nopen=\"\u27e8\" close=\"\u27e9\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>x<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><mo \nclass=\"MathClass-punc\">,<\/mo><mi \n>y<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>x<\/mi><\/mrow><\/mfenced> <mo \nclass=\"MathClass-bin\">+<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><mn>2<\/mn><mi \n>L<\/mi><\/mrow><\/mfrac><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>x<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>y<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/math><\/td>\n<td class=\"eq-no\">(2)<\/td>\n<\/tr>\n<\/table>\n<table class=\"equation\">\n<tr>\n<td> <a \n id=\"x1-1003r3\"><\/a> \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" class=\"equation\">\n <mfenced separators=\"\" \nopen=\"\u27e8\" close=\"\u27e9\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>x<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>y<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><mo \nclass=\"MathClass-punc\">,<\/mo><mi \n>x<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>y<\/mi><\/mrow><\/mfenced> <mo \nclass=\"MathClass-rel\">\u2265<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><mi \n>L<\/mi><\/mrow><\/mfrac><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>x<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>y<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/math><\/td>\n<td class=\"eq-no\">(3)<\/td>\n<\/tr>\n<\/table>\n<\/p>\n\n<h3 class=\"sectionHead\">1 <\/span> <a \n id=\"x1-20001\"><\/a>Proximal Style Convergence Proof<\/h3>\n<\/p>\nThe following argument gives a proof of convergence that is well suited to \nmodi\ufb01cation for proving the convergence of proximal gradient methods. We start by \nproving a useful lemma:\n<\/p>\n<div class=\"newtheorem\">\n<\/p>\n \n<a \n id=\"x1-2001r1\"><\/a> \nLemma 1.<\/span> <\/span>For any <\/span><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/math> \nand <\/span><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>y<\/mi><\/math>,<\/span> \nwhen <\/span><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-rel\">=<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><mi \n>L<\/mi><\/mrow><\/mfrac><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/math>:<\/span>\n<\/p>\n<div class=\"par-math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mfrac><mrow \n><mn>2<\/mn><\/mrow> \n<mrow \n><mi \n>L<\/mi><\/mrow><\/mfrac> <mfenced separators=\"\" \nopen=\"[\" close=\"]\" ><mrow><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>y<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced> <mo \nclass=\"MathClass-rel\">\u2265<\/mo><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><mi \n>y<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo><msup><mrow \n><mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>y<\/mi><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p><\/div>\n<\/p>\n\n<div class=\"proof\">\n<\/p>\n \nProof.<\/span> <\/span>We start with the Lipschitz upper bound around <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/math> \nof <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/math>:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">+<\/mo> <mfenced separators=\"\" \nopen=\"\u27e8\" close=\"\u27e9\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><mo \nclass=\"MathClass-punc\">,<\/mo><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced> <mo \nclass=\"MathClass-bin\">+<\/mo> <mfrac><mrow \n><mi \n>L<\/mi><\/mrow> \n<mrow \n><mn>2<\/mn><\/mrow><\/mfrac><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n Now we bound <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/math> \nusing the negated convexity lower bound of <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>y<\/mi><\/math> \naround <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>x<\/mi><\/math> \n(i.e. <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>y<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-rel\">\u2265<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">+<\/mo> <mfenced separators=\"\" \nopen=\"\u27e8\" close=\"\u27e9\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><mo \nclass=\"MathClass-punc\">,<\/mo><mi \n>y<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced><\/math>):\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>y<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">+<\/mo> <mfenced separators=\"\" \nopen=\"\u27e8\" close=\"\u27e9\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><mo \nclass=\"MathClass-punc\">,<\/mo><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">+<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>y<\/mi><\/mrow><\/mfenced> <mo \nclass=\"MathClass-bin\">+<\/mo> <mfrac><mrow \n><mi \n>L<\/mi><\/mrow> \n<mrow \n><mn>2<\/mn><\/mrow><\/mfrac><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n Negating, rearranging and multiplying through by \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" > <mfrac><mrow \n><mn>2<\/mn><\/mrow>\n<mrow \n><mi \n>L<\/mi><\/mrow><\/mfrac><\/math> \ngives:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mfrac><mrow \n><mn>2<\/mn><\/mrow> \n<mrow \n><mi \n>L<\/mi><\/mrow><\/mfrac> <mfenced separators=\"\" \nopen=\"[\" close=\"]\" ><mrow><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>y<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced> <mo \nclass=\"MathClass-rel\">\u2265<\/mo> <mfrac><mrow \n><mn>2<\/mn><\/mrow> \n<mrow \n><mi \n>L<\/mi><\/mrow><\/mfrac> <mfenced separators=\"\" \nopen=\"\u27e8\" close=\"\u27e9\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><mo \nclass=\"MathClass-punc\">,<\/mo><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>y<\/mi><\/mrow><\/mfenced> <mo \nclass=\"MathClass-bin\">+<\/mo><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n Now we replace <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/math> \nusing <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-rel\">=<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><mi \n>L<\/mi><\/mrow><\/mfrac><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/math>:<\/p>\n<\/p>\n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" >\n<mtable \nclass=\"eqnarray-star\" columnalign=\"right center left\" >\n<mtr><mtd \nclass=\"eqnarray-1\"> <mfrac><mrow \n><mn>2<\/mn><\/mrow>\n<mrow \n><mi \n>L<\/mi><\/mrow><\/mfrac> <mfenced separators=\"\" \nopen=\"[\" close=\"]\" ><mrow><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>y<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><\/mtd><mtd \nclass=\"eqnarray-2\"> <mo \nclass=\"MathClass-rel\">\u2265<\/mo><\/mtd><mtd \nclass=\"eqnarray-3\"> <mn>2<\/mn> <mfenced separators=\"\" \nopen=\"\u27e8\" close=\"\u27e9\" ><mrow><mi \n>y<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><mspace width=\"0.3em\" class=\"thinspace\"\/><mo \nclass=\"MathClass-punc\">,<\/mo><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfenced> <mo \nclass=\"MathClass-bin\">\u2212<\/mo><msup><mrow \n><mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n> <\/mtd><mtd \nclass=\"eqnarray-4\"> <mtext class=\"eqnarray\"><\/mtext><\/mtd>\n<\/mtr><mtr><mtd \nclass=\"eqnarray-1\"> <\/mtd><mtd \nclass=\"eqnarray-2\"> <mo \nclass=\"MathClass-rel\">=<\/mo><\/mtd><mtd \nclass=\"eqnarray-3\"> <mn>2<\/mn> <mfenced separators=\"\" \nopen=\"\u27e8\" close=\"\u27e9\" ><mrow><mi \n>y<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">+<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><mspace width=\"0.3em\" class=\"thinspace\"\/><mo \nclass=\"MathClass-punc\">,<\/mo><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfenced> <mo \nclass=\"MathClass-bin\">\u2212<\/mo><msup><mrow \n><mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><\/mtd><mtd \nclass=\"eqnarray-4\"> <mtext class=\"eqnarray\"><\/mtext><\/mtd>\n<\/mtr><mtr><mtd \nclass=\"eqnarray-1\"> <\/mtd><mtd \nclass=\"eqnarray-2\"> <mo \nclass=\"MathClass-rel\">=<\/mo><\/mtd><mtd \nclass=\"eqnarray-3\"> <mn>2<\/mn> <mfenced separators=\"\" \nopen=\"\u27e8\" close=\"\u27e9\" ><mrow><mi \n>y<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><mo \nclass=\"MathClass-punc\">,<\/mo><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfenced> <mo \nclass=\"MathClass-bin\">+<\/mo> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfenced> <msup><mrow \n><mo \nclass=\"MathClass-punc\">.<\/mo><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n> <\/mtd><mtd \nclass=\"eqnarray-4\"> <mtext class=\"eqnarray\"><\/mtext><\/mtd> <\/mtr><\/mtable>\n<\/math> \n<\/p>\n\n<\/p>\n Now we complete the square using the quadratic \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><mi \n>y<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">+<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n> <mo \nclass=\"MathClass-rel\">=<\/mo><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><mi \n>y<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n> <mo \nclass=\"MathClass-bin\">+<\/mo> <mn>2<\/mn> <mfenced separators=\"\" \nopen=\"\u27e8\" close=\"\u27e9\" ><mrow><mi \n>y<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><mo \nclass=\"MathClass-punc\">,<\/mo><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfenced> <mo \nclass=\"MathClass-bin\">+<\/mo><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><\/math>. So \nwe have: \n<\/p>\n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" >\n<mtable \nclass=\"eqnarray-star\" columnalign=\"right center left\" >\n<mtr><mtd \nclass=\"eqnarray-1\"> <mfrac><mrow \n><mn>2<\/mn><\/mrow>\n<mrow \n><mi \n>L<\/mi><\/mrow><\/mfrac> <mfenced separators=\"\" \nopen=\"[\" close=\"]\" ><mrow><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>y<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><\/mtd><mtd \nclass=\"eqnarray-2\"> <mo \nclass=\"MathClass-rel\">\u2265<\/mo><\/mtd><mtd \nclass=\"eqnarray-3\"> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><mi \n>y<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">+<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfenced> <mo \nclass=\"MathClass-bin\">\u2212<\/mo><msup><mrow \n><mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><mi \n>y<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><\/mtd><mtd \nclass=\"eqnarray-4\"> <mtext class=\"eqnarray\"><\/mtext><\/mtd>\n<\/mtr><mtr><mtd \nclass=\"eqnarray-1\"> <\/mtd><mtd \nclass=\"eqnarray-2\"> <mo \nclass=\"MathClass-rel\">=<\/mo><\/mtd><mtd \nclass=\"eqnarray-3\"> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><mi \n>y<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfenced> <mo \nclass=\"MathClass-bin\">\u2212<\/mo><msup><mrow \n><mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><mi \n>y<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><mo \nclass=\"MathClass-punc\">.<\/mo> <\/mtd><mtd \nclass=\"eqnarray-4\"> <mtext class=\"eqnarray\"><\/mtext><\/mtd> <\/mtr><\/mtable>\n<\/math> \n<\/p>\n\n \u25a1\n<\/p>\n<\/p><\/div>\n<\/p>\n Using this lemma, the proof is quite simple. We apply it with \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>y<\/mi> <mo \nclass=\"MathClass-rel\">=<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/math>:\n<\/p>\n<div class=\"par-math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n><msup><mrow \n>\n <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo><msup><mrow \n><mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n> <mo \nclass=\"MathClass-rel\">\u2264<\/mo><mo \nclass=\"MathClass-bin\">\u2212<\/mo><mfrac><mrow \n><mn>2<\/mn><\/mrow>\n<mrow \n><mi \n>L<\/mi><\/mrow><\/mfrac> <mfenced separators=\"\" \nopen=\"[\" close=\"]\" ><mrow><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n Now we sum this between <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mn>0<\/mn><\/math> \nand <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>k<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mn>1<\/mn><\/math>. \nThe left hand side telescopes:\n<\/p>\n<div class=\"par-math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n><msup><mrow \n>\n <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo><msup><mrow \n><mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mn>0<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n> <mo \nclass=\"MathClass-rel\">\u2264<\/mo><mo \nclass=\"MathClass-bin\">\u2212<\/mo><mfrac><mrow \n><mn>2<\/mn><\/mrow>\n<mrow \n><mi \n>L<\/mi><\/mrow><\/mfrac><munderover accentunder=\"false\" accent=\"false\"><mrow \n><mo mathsize=\"big\" \n>\u2211<\/mo>\n <\/mrow><mrow \n><mi \n>r<\/mi><mo \nclass=\"MathClass-rel\">=<\/mo><mn>0<\/mn><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">\u2212<\/mo><mn>1<\/mn><\/mrow><\/munderover \n> <mfenced separators=\"\" \nopen=\"[\" close=\"]\" ><mrow><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>r<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n Now we use the fact that gradient descent <\/span>is a descent method, which implies that \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>r<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/math> for all \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>r<\/mi> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mi \n>k<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mn>1<\/mn><\/math>. \nSo:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n><msup><mrow \n>\n <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo><msup><mrow \n><mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mn>0<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n> <mo \nclass=\"MathClass-rel\">\u2264<\/mo><mo \nclass=\"MathClass-bin\">\u2212<\/mo><mfrac><mrow \n><mn>2<\/mn><mi \n>k<\/mi><\/mrow>\n<mrow \n><mi \n>L<\/mi><\/mrow><\/mfrac> <mfenced separators=\"\" \nopen=\"[\" close=\"]\" ><mrow><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n Now we just drop the <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><\/math> \nterm since it is positive and small. Leaving:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mfrac><mrow \n><mi \n>L<\/mi><\/mrow> \n<mrow \n><mn>2<\/mn><mi \n>k<\/mi><\/mrow><\/mfrac><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n\n<h4 class=\"likesubsectionHead\"><a \n id=\"x1-30001\"><\/a>Comments<\/h4>\n<\/p>\nAs far as I know, this proof is fairly modern [<a \nhref=\"#Xbeckt-gradient\">1<\/a>]<\/span>. Notice that \nunlike the strongly convex case, the quantity we are bounding \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/math> does \nnot appear on both sides of the bound. Unfortunately, without strong convexity \nthere is necessarily a looseness to the bounds, and this takes the form of \nbounding function value by distance to solution, with a large wiggle-factor. One \nthing that is perhaps a little confusing is the use of distance to solution \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>x<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/math>, \nwhen it is not unique, as there are potentially multiple minimizers for<\/p>\nnon-strongly convex problems. The bound in fact holds for any chosen minimizer \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/math>. I \nfound this to be a little confusing at \ufb01rst.\n<\/p>\n<\/p>\n\n<h3 class=\"sectionHead\">2 <\/span> <a \n id=\"x1-40002\"><\/a>Older Style Proof<\/h3>\n<\/p>\nThis proof is from Nesterov [<a \nhref=\"#Xnes-book\">2<\/a>]<\/span>. I’m not sure of the original source for it.\n<\/p>\n<\/p>\n We start with the function value descent equation, using \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>w<\/mi> <mo \nclass=\"MathClass-punc\">:<\/mo><mo \nclass=\"MathClass-rel\">=<\/mo> <mfenced separators=\"\" \nopen=\"[\" close=\"]\" ><mrow><mi \n>\u03b1<\/mi> <mfenced separators=\"\" \nopen=\"(\" close=\")\" ><mrow><mn>1<\/mn> <mo \nclass=\"MathClass-bin\">\u2212<\/mo><mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><mn>2<\/mn><\/mrow><\/mfrac><mi \n>\u03b1<\/mi><mi \n>L<\/mi><\/mrow><\/mfenced><\/mrow><\/mfenced> <mo \nclass=\"MathClass-punc\">:<\/mo><\/math>\n<\/p>\n<div class=\"par-math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>w<\/mi><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n We introduce the simpli\ufb01ed notation <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-rel\">=<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/math> \nso that we have <\/p>\n<table class=\"equation\">\n<tr>\n<td> <a \n id=\"x1-4001r4\"><\/a> \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" class=\"equation\">\n <msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>w<\/mi><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/math><\/td>\n<td class=\"eq-no\">(4)<\/td>\n<\/tr>\n<\/table>\n<\/p>\n Now using the convexity lower bound around \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/math> evaluated \nat <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/math>, \nnamely:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mfenced separators=\"\" \nopen=\"\u27e8\" close=\"\u27e9\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><mo \nclass=\"MathClass-punc\">,<\/mo><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><mo \nclass=\"MathClass-punc\">,<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n and applying Cauchy-Schwarz (note the spelling! there is no \u201ct\u201d in Schwarz) to \nit: \n<\/p>\n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" >\n<mtable \nclass=\"eqnarray-star\" columnalign=\"right center left\" >\n<mtr><mtd \nclass=\"eqnarray-1\"> <msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mtd><mtd \nclass=\"eqnarray-2\"> <mo \nclass=\"MathClass-rel\">\u2264<\/mo><\/mtd><mtd \nclass=\"eqnarray-3\"> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced> <\/mtd><mtd \nclass=\"eqnarray-4\"> <mtext class=\"eqnarray\"><\/mtext><\/mtd>\n<\/mtr><mtr><mtd \nclass=\"eqnarray-1\"> <\/mtd><mtd \nclass=\"eqnarray-2\"> <mo \nclass=\"MathClass-rel\">\u2264<\/mo><\/mtd><mtd \nclass=\"eqnarray-3\"> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><mo \nclass=\"MathClass-punc\">.<\/mo><\/mtd><mtd \nclass=\"eqnarray-4\"> <mtext class=\"eqnarray\"><\/mtext><\/mtd> <\/mtr><\/mtable>\n<\/math> \n<\/p>\n\n<\/p>\n The last line is because gradient descent method descends in \niterate distance each step. We now introduce the additional notation \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msub><mrow \n><mi \n>r<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-rel\">=<\/mo> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/math>. \nUsing this notation and rearranging gives:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mo \nclass=\"MathClass-bin\">\u2212<\/mo><mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced> <mo \nclass=\"MathClass-rel\">\u2264<\/mo><mo \nclass=\"MathClass-bin\">\u2212<\/mo><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><mo \nclass=\"MathClass-bin\">\u2215<\/mo><msub><mrow \n><mi \n>r<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><\/msub \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n We plug this into the function descent equation (Eq <a \nhref=\"#x1-4001r4\">4<\/a>) above to get:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mfrac><mrow \n><mi \n>w<\/mi><\/mrow> \n<mrow \n><msubsup><mrow \n><mi \n>r<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msubsup \n><\/mrow><\/mfrac><msubsup><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msubsup \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n We now divide this through by <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/math>:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mn>1<\/mn> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mfrac><mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow> \n<mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfrac> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mfrac><mrow \n><mi \n>w<\/mi><\/mrow> \n<mrow \n><msubsup><mrow \n><mi \n>r<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msubsup \n><\/mrow><\/mfrac> <mfrac><mrow \n><msubsup><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msubsup \n><\/mrow> \n<mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfrac>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n Then divide through by <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/math> \nalso:\n<\/p>\n<div class=\"par-math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfrac> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfrac> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mfrac><mrow \n><mi \n>w<\/mi><\/mrow> \n<mrow \n><msubsup><mrow \n><mi \n>r<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msubsup \n><\/mrow><\/mfrac> <mfrac><mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow> \n<mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfrac><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n Now we use the fact that gradient descent is a descent method again, which implies \nthat <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" > <mfrac><mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow>\n<mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfrac> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mn>1<\/mn><mo \nclass=\"MathClass-punc\">,<\/mo><\/math> \nso:\n<\/p>\n<div class=\"par-math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfrac> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfrac> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mfrac><mrow \n><mi \n>w<\/mi><\/mrow> \n<mrow \n><msubsup><mrow \n><mi \n>r<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msubsup \n><\/mrow><\/mfrac><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mo \nclass=\"MathClass-rel\">\u2234<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfrac> <mo \nclass=\"MathClass-rel\">\u2265<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfrac> <mo \nclass=\"MathClass-bin\">+<\/mo> <mfrac><mrow \n><mi \n>w<\/mi><\/mrow> \n<mrow \n><msubsup><mrow \n><mi \n>r<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msubsup \n><\/mrow><\/mfrac><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n We then chain this inequality for each \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>k<\/mi><\/math>:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfrac> <mo \nclass=\"MathClass-rel\">\u2265<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfrac> <mo \nclass=\"MathClass-bin\">+<\/mo> <mfrac><mrow \n><mi \n>w<\/mi><\/mrow> \n<mrow \n><msubsup><mrow \n><mi \n>r<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msubsup \n><\/mrow><\/mfrac> <mo \nclass=\"MathClass-rel\">\u2265<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">\u2212<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfrac> <mo \nclass=\"MathClass-bin\">+<\/mo> <mn>2<\/mn> <mfrac><mrow \n><mi \n>w<\/mi><\/mrow>\n<mrow \n><msubsup><mrow \n><mi \n>r<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msubsup \n><\/mrow><\/mfrac> <mo \nclass=\"MathClass-rel\">\u2265<\/mo><mo \nclass=\"MathClass-rel\">\u22ef<\/mo> <mo \nclass=\"MathClass-rel\">\u2265<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><\/msub \n><\/mrow><\/mfrac> <mo \nclass=\"MathClass-bin\">+<\/mo> <mfrac><mrow \n><mi \n>w<\/mi><\/mrow> \n<mrow \n><msubsup><mrow \n><mi \n>r<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msubsup \n><\/mrow><\/mfrac><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>k<\/mi> <mo \nclass=\"MathClass-bin\">+<\/mo> <mn>1<\/mn><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mo \nclass=\"MathClass-rel\">\u2234<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><\/mfrac> <mo \nclass=\"MathClass-rel\">\u2265<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><\/msub \n><\/mrow><\/mfrac> <mo \nclass=\"MathClass-bin\">+<\/mo> <mfrac><mrow \n><mi \n>w<\/mi><\/mrow> \n<mrow \n><msubsup><mrow \n><mi \n>r<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msubsup \n><\/mrow><\/mfrac><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>k<\/mi> <mo \nclass=\"MathClass-bin\">+<\/mo> <mn>1<\/mn><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n To get the \ufb01nal convergence rate we invert both sides:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mfrac><mrow \n><mfenced separators=\"\" \nopen=\"[\" close=\"]\" ><mrow><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mn>0<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><\/mrow> \n<mrow \n><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n> <mo \nclass=\"MathClass-bin\">+<\/mo> <mi \n>w<\/mi> <mfenced separators=\"\" \nopen=\"[\" close=\"]\" ><mrow><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><mi \n>k<\/mi><\/mrow><\/mfrac><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n This is quite a complex expression. To simplify even further, we can get rid of the \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/math> \nterms on the right hand side using the Lipschitz upper bound about \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/math>:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mfrac><mrow \n><mi \n>L<\/mi><\/mrow> \n<mrow \n><mn>2<\/mn><\/mrow><\/mfrac><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><mi \n>x<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n Plugging in the step size <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>\u03b1<\/mi> <mo \nclass=\"MathClass-rel\">=<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><mi \n>L<\/mi><\/mrow><\/mfrac><\/math> \ngives <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>w<\/mi> <mo \nclass=\"MathClass-rel\">=<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><mn>2<\/mn><mi \n>L<\/mi><\/mrow><\/mfrac><\/math>, \nyielding the following simpler convergence rate:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mfrac><mrow \n><mn>2<\/mn><mi \n>L<\/mi><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><\/mrow> \n <mrow \n><mi \n>k<\/mi> <mo \nclass=\"MathClass-bin\">+<\/mo> <mn>4<\/mn><\/mrow><\/mfrac> <mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n Compared to the rate from the previous proof, \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mfrac><mrow \n><mi \n>L<\/mi><\/mrow> \n<mrow \n><mn>2<\/mn><mi \n>k<\/mi><\/mrow><\/mfrac><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><\/msup \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><\/math>, this is slightly \nbetter at <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>k<\/mi> <mo \nclass=\"MathClass-rel\">=<\/mo> <mn>1<\/mn><\/math>, \nand worse thereafter.\n<\/p>\n<\/p>\n\n<h4 class=\"likesubsectionHead\"><a \n id=\"x1-50002\"><\/a>Comments<\/h4>\n<\/p>\nI don’t like this proof. It’s feels like a random sequence of steps when \nyou \ufb01rst look at it. The way the proof uses inverse quantities like \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" > <mfrac><mrow \n><mn>1<\/mn><\/mrow>\n<mrow \n><msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfrac><\/math> \nis also confusing. The key equation is really the direct bound on \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>\u0394<\/mi><\/math>:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <msub><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mfrac><mrow \n><mi \n>w<\/mi><\/mrow> \n<mrow \n><msubsup><mrow \n><mi \n>r<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msubsup \n><\/mrow><\/mfrac><msubsup><mrow \n><mi \n>\u0394<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msubsup \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n Often this is the kind of equation you encounter when proving the properties of \ndual methods for example. Equations of this kind can be encountered when applying<\/p>\nproximal methods to non-di\ufb00erentiable functions also. It is also quite a clear \nstatement about what is going on in terms of per-step convergence, a property that is \nless clear in the previous proof.\n<\/p>\n<\/p>\n\n<h3 class=\"sectionHead\">3 <\/span> <a \n id=\"x1-60003\"><\/a>Gradient Concentration<\/h3>\n<\/p>\nWhen we don’t even have convexity, just Lipschitz smoothness, we can still prove \nsomething about convergence of the gradient norm. The Lipschitz upper bound holds \nwithout the requirement of convexity:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>y<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>x<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">+<\/mo> <mfenced separators=\"\" \nopen=\"\u27e8\" close=\"\u27e9\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><mi \n>x<\/mi><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><mo \nclass=\"MathClass-punc\">,<\/mo><mi \n>y<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>x<\/mi><\/mrow><\/mfenced> <mo \nclass=\"MathClass-bin\">+<\/mo> <mfrac><mrow \n><mi \n>L<\/mi><\/mrow> \n<mrow \n><mn>2<\/mn><\/mrow><\/mfrac><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><mi \n>x<\/mi> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>y<\/mi><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n Recall that from minimizing this bound with respect to \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>y<\/mi><\/math> we \ncan prove the equation:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-rel\">\u2265<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><mn>2<\/mn><mi \n>L<\/mi><\/mrow><\/mfrac><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n Examine this equation carefully. We have a bound on each gradient encountered \nduring the optimization in terms of the di\ufb00erence in function values between steps. \nThe sequence of function values is bounded below, so in fact we have a hard bound \non the sum of the encountered gradient norms. E\ufb00ectively, we chain (telescope) the \nabove inequality over steps:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">\u2212<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">+<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-rel\">\u2265<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><mn>2<\/mn><mi \n>L<\/mi><\/mrow><\/mfrac><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n> <mo \nclass=\"MathClass-bin\">+<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><mn>2<\/mn><mi \n>L<\/mi><\/mrow><\/mfrac><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">\u2212<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mo \nclass=\"MathClass-punc\">.<\/mo><mo \nclass=\"MathClass-punc\">.<\/mo><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-rel\">\u2265<\/mo> <mfrac><mrow \n><mn>1<\/mn><\/mrow> \n<mrow \n><mn>2<\/mn><mi \n>L<\/mi><\/mrow><\/mfrac><munderover accentunder=\"false\" accent=\"false\"><mrow \n><mo mathsize=\"big\" \n>\u2211<\/mo>\n <\/mrow><mrow \n><mi \n>i<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/munderover \n><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>i<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n Now since <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><mo \nclass=\"MathClass-bin\">+<\/mo><mn>1<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-rel\">\u2265<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/math>:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n>\n <munderover accentunder=\"false\" accent=\"false\"><mrow \n><mo mathsize=\"big\" \n>\u2211<\/mo>\n <\/mrow><mrow \n><mi \n>i<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/munderover \n><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mi \n>i<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mn>2<\/mn><mi \n>L<\/mi> <mfenced separators=\"\" \nopen=\"(\" close=\")\" ><mrow><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n>\n<mn>0<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n Now to make this bound a little more concrete, we can put it in terms of the gradient \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msub><mrow \n><mi \n>g<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/math> \nwith the smallest norm seen during the minimization \n(<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" > <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>g<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>g<\/mi><\/mrow><mrow \n><mi \n>i<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced><\/math> for all \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>i<\/mi><\/math>), so \nthat <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><msubsup><mrow \n><mo \nclass=\"MathClass-op\"> \u2211<\/mo>\n <\/mrow><mrow \n><mi \n>i<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msubsup \n><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msup><mrow \n><mi \n>f<\/mi><\/mrow><mrow \n><mi \n>\u2032<\/mi><\/mrow><\/msup \n><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mi \n>i<\/mi><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n> <mo \nclass=\"MathClass-rel\">\u2265<\/mo> <mi \n>k<\/mi><msup><mrow \n> <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>g<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n><\/math>, \nso:\n<\/p>\n<div class=\"math-display\"><math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"block\" ><mrow \n><msup><mrow \n>\n <mfenced separators=\"\" \nopen=\"\u2225\" close=\"\u2225\" ><mrow><msub><mrow \n><mi \n>g<\/mi><\/mrow><mrow \n><mi \n>k<\/mi><\/mrow><\/msub \n><\/mrow><\/mfenced> <\/mrow><mrow \n><mn>2<\/mn><\/mrow><\/msup \n> <mo \nclass=\"MathClass-rel\">\u2264<\/mo> <mfrac><mrow \n><mn>2<\/mn><mi \n>L<\/mi><\/mrow> \n <mrow \n><mi \n>k<\/mi><\/mrow><\/mfrac> <mfenced separators=\"\" \nopen=\"(\" close=\")\" ><mrow><mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msub><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mn>0<\/mn><\/mrow><\/msub \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow> <mo \nclass=\"MathClass-bin\">\u2212<\/mo> <mi \n>f<\/mi><mrow ><mo \nclass=\"MathClass-open\">(<\/mo><mrow><msup><mrow \n><mi \n>x<\/mi><\/mrow><mrow \n><mo \nclass=\"MathClass-bin\">\u2217<\/mo><\/mrow><\/msup \n><\/mrow><mo \nclass=\"MathClass-close\">)<\/mo><\/mrow><\/mrow><\/mfenced><mo \nclass=\"MathClass-punc\">.<\/mo>\n<\/mrow><\/math><\/div>\n<\/p>\n\n<\/p>\n\n<h4 class=\"likesubsectionHead\"><a \n id=\"x1-70003\"><\/a>Comments<\/h4>\n<\/p>\nNotice that the core technique used in this proof is the same as the last 2 proofs. \nWe have a single step inequality bounding one of the quantities we care \nabout. By summing that inequality over each step of minimization, one side \nof the inequality telescopes. We get an equality saying the the sum of the \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>k<\/mi><\/math> versions \nof that quantity (one from each step) is less then some \ufb01xed constant independent of \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>k<\/mi><\/math>, for any \n<math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>k<\/mi><\/math>. The convergence rate is \nthus of the form <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mn>1<\/mn><mo \nclass=\"MathClass-bin\">\u2215<\/mo><mi \n>k<\/mi><\/math>, because \nthe summation of the <math \n xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" \ndisplay=\"inline\" ><mi \n>k<\/mi><\/math> \nquantities \ufb01ts in a \ufb01xed bound.\n<\/p>\n<\/p>\n Almost any proof for an optimization method that applies in the non-convex case \nuses a similar proof technique. There is just not that many assumptions to work \nwith, so the options are limited.\n<\/p>\n<\/p>\n\n<h3 class=\"likesectionHead\"><a \n id=\"x1-80003\"><\/a>References<\/h3>\n<\/p>\n\n<div class=\"thebibliography\">\n \n [1]\u00a0\u00a0\u00a0<\/span><\/span><a \n id=\"Xbeckt-gradient\"><\/a>Amir Beck and Marc Teboulle. Gradient-based algorithms with \n applications to signal recovery problems. Convex Optimization in Signal<\/span> \n Processing and Communications<\/span>, 2009.<\/p>\n \n [2]\u00a0\u00a0\u00a0<\/span><\/span><a \n id=\"Xnes-book\"><\/a>Yu. Nesterov. Introductory Lectures On Convex Programming<\/span>. Springer, \n 1998.\n<\/p>\n<\/p><\/div>\n","protected":false},"excerpt":{"rendered":"The previous post detailed a bunch of different ways of proving the convergence rate of gradient descent: xk+1 = xk \u2212 \u03b1f\u2032(x k), for strongly convex problems. This post considers the non-strongly convex, but still convex case. Rehash of Basic Lemmas These hold for any x and y. L the Lipschitz smoothness constant. These are … <a href=\"https:\/\/www.aarondefazio.com\/tangentially\/?p=35\" class=\"more-link\">Continue reading The Many Ways to Analyse Gradient Descent: Part 2<\/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\/35"}],"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=35"}],"version-history":[{"count":2,"href":"https:\/\/www.aarondefazio.com\/tangentially\/index.php?rest_route=\/wp\/v2\/posts\/35\/revisions"}],"predecessor-version":[{"id":37,"href":"https:\/\/www.aarondefazio.com\/tangentially\/index.php?rest_route=\/wp\/v2\/posts\/35\/revisions\/37"}],"wp:attachment":[{"href":"https:\/\/www.aarondefazio.com\/tangentially\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=35"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.aarondefazio.com\/tangentially\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=35"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.aarondefazio.com\/tangentially\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=35"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}