{ "cells": [ { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# TOPIC 3 \n", "\n", "# Optimality, convexity, and gradient descent\n", "\n", "## 4 Gradient descent\n", "\n", "***\n", "*Course:* [Math 535](http://www.math.wisc.edu/~roch/mmids/) - Mathematical Methods in Data Science (MMiDS) \n", "*Author:* [Sebastien Roch](http://www.math.wisc.edu/~roch/), Department of Mathematics, University of Wisconsin-Madison \n", "*Updated:* Oct 17, 2020 \n", "*Copyright:* © 2020 Sebastien Roch\n", "***" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "We consider a natural approach for solving optimization problems numerically: a class of algorithms known as descent methods. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "Let $f : \\mathbb{R}^d \\to \\mathbb{R}$ is continuously differentiable. We restrict ourselves to unconstrained minimization problems of the form\n", "\n", "$$\n", "\\min_{\\mathbf{x} \\in \\mathbb{R}^d} f(\\mathbf{x}).\n", "$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Ideally one would like to identify a global minimizer of $f$. A naive approach might be to evaluate $f$ at a large number of points $\\mathbf{x}$, say on a dense grid. However, even if we were satisfied with an approximate solution and limited ourselves to a bounded subset of the domain of $f$, this type of [exhaustive search](https://en.wikipedia.org/wiki/Brute-force_search) is wasteful and impractical in large dimension $d$, as the number of points interrogated grows exponentially with $d$. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "A less naive approach might be to find all stationary points of $f$, that is, those $\\mathbf{x}$'s such that $\\nabla f(\\mathbf{x}) = \\mathbf{0}$. And then choose that $\\mathbf{x}$ among them that produces the smallest value of $f(\\mathbf{x})$. This indeed works in many problems, like the following example we have encountered previously. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "**Example:** Consider the least-squares problem\n", "\n", "$$\n", "\\min_{\\mathbf{x} \\in \\mathbb{R}^d} \\|A \\mathbf{x} - \\mathbf{b}\\|^2\n", "$$\n", "\n", "where $A \\in \\mathbb{R}^{n \\times d}$ has full column rank. In particular, $d \\leq n$. The objective function is a quadratic function\n", "\n", "$$\n", "f(\\mathbf{x}) \n", "= \\|A \\mathbf{x} - \\mathbf{b}\\|^2\n", "= (A \\mathbf{x} - \\mathbf{b})^T(A \\mathbf{x} - \\mathbf{b})\n", "= \\mathbf{x}^T A^T A \\mathbf{x} - 2 \\mathbf{b}^T A \\mathbf{x} + \\mathbf{b}^T \\mathbf{b}.\n", "$$\n", "\n", "By a previous example,\n", "\n", "$$\n", "\\nabla f(\\mathbf{x})\n", "= 2 A^T A \\mathbf{x} - 2 A^T \\mathbf{b}\n", "$$\n", "\n", "where we used that $A^T A$ is symmetric." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "So the stationary points satisfy \n", "\n", "$$\n", "A^T A \\mathbf{x} = A^T \\mathbf{b}\n", "$$\n", "\n", "which you may recognize as the normal equations for the least-squares problem. We have previously shown that there is a unique solution to this system when $A$ has full column rank. Moreover, this optimization problem is convex. Indeed, by our previous example, the Hessian of $f$ is\n", "\n", "$$\n", "\\mathbf{H}_f(\\mathbf{x})\n", "= 2 A^T A.\n", "$$\n", "\n", "This Hessian is positive semidefinite since, for any $\\mathbf{z} \\in \\mathbf{R}^d$,\n", "\n", "$$\n", "\\langle \\mathbf{z}, 2 A^T A \\mathbf{z}\\rangle \n", "= 2 (A \\mathbf{z})^T (A \\mathbf{z})\n", "= 2 \\|A \\mathbf{z}\\|^2 \\geq 0.\n", "$$\n", "\n", "So any local minimizer, which is necessarily a stationary point, is also a global minimizer. So we have found all global minimizers. $\\lhd$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "Unfortunately, identifying stationary points often leads to systems of nonlinear equations that do not have explicit solutions. Hence we resort to a different approach." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### 4.1 Steepest descent" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "In steepest descent, we attempt to find smaller and smaller values of $f$ by successively following directions in which $f$ decreases. As we have seen in the proof of the *First-Order Necessary Condition*, $- \\nabla f$ provides such a direction. In fact, it is the direction of steepest descent in the following sense. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "Recall from the *Descent Direction and Directional Derivative Lemma* that $\\mathbf{v}$ is a descent direction at $\\mathbf{x}_0$ if the directional derivative of $f$ at $\\mathbf{x}_0$ in the direction $\\mathbf{v}$ is negative.\n", "\n", "***\n", "\n", "**Lemma (Steepest Descent):** Let $f : \\mathbb{R}^d \\to \\mathbb{R}$ be continuously differentiable at $\\mathbf{x}_0$. For any unit vector $\\mathbf{v} \\in \\mathbb{R}^d$,\n", "\n", "$$\n", "\\frac{\\partial f (\\mathbf{x}_0)}{\\partial \\mathbf{v}} \n", "\\geq \\frac{\\partial f (\\mathbf{x}_0)}{\\partial \\mathbf{v}^*} \n", "$$\n", "\n", "where\n", "\n", "$$\n", "\\mathbf{v}^*\n", "= - \\frac{\\nabla f(\\mathbf{x}_0)}{\\|\\nabla f(\\mathbf{x}_0)\\|}.\n", "$$\n", "\n", "***" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "*Proof idea:* This is an immediate application of the *Chain Rule* and *Cauchy-Schwarz*." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "*Proof:* By the *Chain Rule* and *Cauchy-Schwarz*,\n", "\n", "\n", "\\begin{align*}\n", "\\frac{\\partial f (\\mathbf{x}_0)}{\\partial \\mathbf{v}} \n", "&= \\nabla f(\\mathbf{x}_0)^T \\mathbf{v}\\\\\n", "&\\leq \\|\\nabla f(\\mathbf{x}_0)\\| \\|\\mathbf{v}\\|\\\\\n", "&= \\|\\nabla f(\\mathbf{x}_0)\\|\\\\\n", "&= \\nabla f(\\mathbf{x}_0)^T \\left(- \\frac{\\nabla f(\\mathbf{x}_0)}{\\|\\nabla f(\\mathbf{x}_0)\\|}\\right)\\\\\n", "&= \\frac{\\partial f (\\mathbf{x}_0)}{\\partial \\mathbf{v}^*}.\n", "\\end{align*}\n", "\n", "\n", "$\\square$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "At each interation of steepest descent, we take a step in the direction of the negative of the gradient, that is,\n", "\n", "$$\n", "\\mathbf{x}^{k+1}\n", "= \\mathbf{x}^k - \\alpha_k \\nabla f(\\mathbf{x}^k),\n", "\\quad k=0,1,2\\ldots\n", "$$\n", "\n", "for a sequence of steplengths $\\alpha_k > 0$. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "In general, we will not be able to guarantee that a global minimizer is reached in the limit, even if one exists. Our goal for now is more modest: to find a point where the gradient of $f$ approximately vanishes." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "**NUMERICAL CORNER** We implement steepest descent in Julia. We assume that a function f and its gradient grad_f are provided. We first code the basic descent step with a steplength parameter beta." ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "# Julia version: 1.5.1\n", "using Plots, Statistics" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [ { "data": { "text/plain": [ "desc_update (generic function with 1 method)" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function desc_update(grad_f, x, β)\n", " return x .- β*grad_f(x)\n", "end" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "mmids_gd (generic function with 1 method)" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function mmids_gd(f, grad_f, x0; β=1e-3, niters=1e6)\n", " \n", " xk = x0 # initialization\n", " for _ = 1:niters\n", " xk = desc_update(grad_f, xk, β) # gradient step\n", " end\n", " \n", " return xk, f(xk)\n", "end" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "We illustrate on a simple example." ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "f(x) = (x-1)^2+10\n", "xgrid = LinRange(-5,5,100)\n", "plot(xgrid, f.(xgrid), lw=2, legend=false)" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [ { "data": { "text/plain": [ "grad_f (generic function with 1 method)" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "grad_f(x) = 2*(x-1)" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "scrolled": true, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "(0.9999999999999722, 10.0)" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "mmids_gd(f, grad_f, 0)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "We found a global minmizer in this case." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "The next example shows that a different local minimizer may be reached depending on the starting point." ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "f(x) = 4*(x-1)^2*(x+1)^2 - 2*(x-1)\n", "xgrid = LinRange(-2,2,100)\n", "plot(xgrid, f.(xgrid), lw=2, label=\"f\", ylim=(-1,10), legend=:bottomleft)" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [ { "data": { "text/plain": [ "grad_f (generic function with 1 method)" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "grad_f(x) = 8*(x-1)*(x+1)^2 + 8*(x-1)^2*(x+1) - 2" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "plot!(xgrid, grad_f.(xgrid), lw=2, label=\"grad_f\", ylim=(-10,10))" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [ { "data": { "text/plain": [ "(1.057453770738375, -0.0590145651028224)" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "mmids_gd(f, grad_f, 0)" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "(-0.9304029265558538, 3.933005966859003)" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "mmids_gd(f, grad_f, -2)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "In the final example, we end up at a stationary point that is not a local minimizer. Here both the first and second derivatives are zero. This is known as a [saddle point](https://en.wikipedia.org/wiki/Saddle_point)." ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "f(x) = x^3\n", "xgrid = LinRange(-2,2,100)\n", "plot(xgrid, f.(xgrid), lw=2, label=\"f\", ylim=(-10,10), legend=:bottomright)" ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "grad_f(x) = 3*x^2\n", "plot!(xgrid, grad_f.(xgrid), lw=2, label=\"grad\", ylim=(-10,10))" ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [ { "data": { "text/plain": [ "(0.00033327488712690107, 3.701755838398568e-11)" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "mmids_gd(f, grad_f, 2)" ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "(-Inf, -Inf)" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "mmids_gd(f, grad_f, -2)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### 4.2 Convergence analysis" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "In this section, we prove some results about the convergence of steepest descent. We start with the smooth case. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "#### 4.2.1 Smooth case" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "We will use the following notation. Let $A, B \\in \\mathbb{R}^{d \\times d}$ be symmetric matrices. Recall that $A \\succeq 0$ means that $A$ is PSD. We write $A \\preceq B$ (respectively $A \\succeq B$) to indicate that $B - A \\succeq 0$ (respectively $A - B \\succeq 0$). We will need the following statement, whose proof is left as an exercise." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "*Exercise:* Let $A \\in \\mathbb{R}^{d \\times d}$ be a symmetric matrix. Show that $A \\preceq M I_{d \\times d}$ if and only if the eigenvalues of $A$ are at most $M$. Similarly, $m I_{d \\times d} \\preceq A$ if and only if the eigenvalues of $A$ are at least $m$. [Hint: Observe that the eigenvectors of $A$ are also eigenvectors of the identity matrix $I_{d \\times d}$.] $\\lhd$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "**Definition (Smooth Function):** Let $f : \\mathbb{R}^d \\to \\mathbb{R}$ be twice continuously differentiable. We say that $f$ is $L$-smooth if \n", "\n", "$$\n", "- L I_{d \\times d} \\preceq \\mathbf{H}_f(\\mathbf{x}) \\preceq L I_{d \\times d},\n", "\\quad \\forall \\mathbf{x} \\in \\mathbb{R}^d.\n", "$$ \n", "\n", "$\\lhd$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "***\n", "\n", "**Lemma (Quadratic Bound for Smooth Functions):** Let $f : \\mathbb{R}^d \\to \\mathbb{R}$ be twice continuously differentiable. Then $f$ is $L$-smooth if and only if for all $\\mathbf{x}, \\mathbf{y} \\in \\mathbb{R}^d$ it holds that\n", "\n", "$$\n", "\\left|f(\\mathbf{y})\n", "- \\{f(\\mathbf{x}) \n", "+ \\nabla f(\\mathbf{x})^T(\\mathbf{y} - \\mathbf{x})\\}\\right|\n", "\\leq \\frac{L}{2} \\|\\mathbf{y} - \\mathbf{x}\\|^2.\n", "$$\n", "\n", "***" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "*Proof idea:* We apply the *Multivariate Taylor's Theorem*, then use the extremal characterization of the eigenvalues to bound the second-order term." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "*Proof:* By the *Multivariate Taylor's Theorem*, for any $\\alpha > 0$ there is $\\xi_\\alpha \\in (0,1)$\n", "\n", "$$\n", "f(\\mathbf{x} + \\alpha \\mathbf{p})\n", "= f(\\mathbf{x}) \n", "+ \\alpha \\nabla f(\\mathbf{x})^T \\mathbf{p}\n", "+ \\frac{1}{2} \\alpha^2 \\mathbf{p}^T \n", "\\,\\mathbf{H}_f(\\mathbf{x} + \\xi_\\alpha \\alpha \\mathbf{p})\n", "\\,\\mathbf{p}\n", "$$\n", "\n", "where $\\mathbf{p} = \\mathbf{y} - \\mathbf{x}$.\n", "\n", "If $f$ is L-smooth, then at $\\alpha = 1$ by *Courant-Fischer*\n", "\n", "$$\n", "- L \\|\\mathbf{p}\\|^2\n", "\\leq \\mathbf{p}^T \n", "\\,\\mathbf{H}_f(\\mathbf{x} + \\xi_1 \\mathbf{p})\n", "\\,\\mathbf{p}\n", "\\leq L \\|\\mathbf{p}\\|^2.\n", "$$\n", "\n", "That implies the inequality in the statement." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "On the other hand, if that inequality holds, by combining with the Taylor expansion above we get\n", "\n", "$$\n", "\\left|\\,\\frac{1}{2} \\alpha^2 \\mathbf{p}^T \n", "\\,\\mathbf{H}_f(\\mathbf{x} + \\xi_\\alpha \\alpha \\mathbf{p})\n", "\\,\\mathbf{p}\\,\\right|\n", "\\leq \\frac{L}{2} \\alpha^2 \\|\\mathbf{p}\\|^2\n", "$$\n", "\n", "where we used that $\\|\\alpha \\mathbf{p}\\| = \\alpha \\|\\mathbf{p}\\|$ by homogeneity of the norm. Dividing by $\\alpha^2/2$, then taking $\\alpha \\to 0$ and using the continuity of the Hessian gives\n", "\n", "$$\n", "\\left|\\,\n", "\\mathbf{p}^T \n", "\\,\\mathbf{H}_f(\\mathbf{x})\n", "\\,\\mathbf{p}\n", "\\,\\right|\n", "\\leq L \\|\\mathbf{p}\\|^2.\n", "$$\n", "\n", "By *Courant-Fischer* again, that implies that $f$ is $L$-smooth. $\\square$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "We show next that, in the smooth case, steepest descent with an appropriately chosen steplength produces a sequence of points whose objective values decrease and whose gradients vanish in the limit. We also give a quantitative convergence rate." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "***\n", "\n", "**Theorem (Convergence of Steepest Descent in Smooth Case):** Suppose that $f : \\mathbb{R}^d \\to \\mathbb{R}$ is $L$-smooth and bounded from below, that is, there $\\bar{f} > - \\infty$ such that $f(\\mathbf{x}) \\geq \\bar{f}$, $\\forall \\mathbf{x} \\in \\mathbb{R}^d$. Then steepest descent with $\\alpha = 1/L$ started from any $\\mathbf{x}^0$ produces a sequence $\\mathbf{x}^t$, $t=1,2,\\ldots$ such that\n", "\n", "$$\n", "f(\\mathbf{x}^{t+1}) \\leq f(\\mathbf{x}^t),\n", "\\quad \\forall t\n", "$$\n", "\n", "and\n", "\n", "$$\n", "\\lim_{t \\to +\\infty} \\|\\nabla f(\\mathbf{x}^t)\\| = 0.\n", "$$\n", "\n", "Moreover, after $H$ steps, there is a $t$ in $\\{0,\\ldots,H\\}$ such that\n", "\n", "$$\n", "\\|\\nabla f(\\mathbf{x}^t)\\|\n", "\\leq \\sqrt{\\frac{2 L \\left[f(\\mathbf{x}^0) - \\bar{f}\\right]}{H}}.\n", "$$\n", "\n", "***" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "The heart of the proof is the following fundamental inequality. It also explains the choice of steplength." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "***\n", "\n", "**Lemma (Descent Guarantee in the Smooth Case):** Suppose that $f : \\mathbb{R}^d \\to \\mathbb{R}$ is $L$-smooth. For any $\\mathbf{x} \\in \\mathbb{R}^d$,\n", "\n", "$$\n", "f(\\mathbf{x} - (1/L)\\nabla f(\\mathbf{x}))\n", "\\leq f(\\mathbf{x}) - \\frac{1}{2 L} \\|\\nabla f(\\mathbf{x})\\|^2.\n", "$$\n", "\n", "***" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "*Proof idea (Descent Guarantee in the Smooth Case):* Intuitively, the *Quadratic Bound for Smooth Functions* shows that $f$ is well approximated by a quadratic function in a neighborhood of $\\mathbf{x}$ whose size depends on the smoothness parameter $L$. Choosing a step that minimizes this approximation leads to a guaranteed improvement." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "*Proof (Descent Guarantee in the Smooth Case):* By the *Quadratic Bound for Smooth Functions*, letting $\\mathbf{p} = - \\nabla f(\\mathbf{x})$\n", "\n", "\n", "\\begin{align*}\n", "f(\\mathbf{x} + \\alpha \\mathbf{p})\n", "&\\leq f(\\mathbf{x}) + \\nabla f(\\mathbf{x})^T (\\alpha \\mathbf{p})\n", "+ \\frac{L}{2} \\|\\alpha \\mathbf{p}\\|^2\\\\\n", "&= f(\\mathbf{x}) - \\alpha \\|\\nabla f(\\mathbf{x})\\|^2\n", "+ \\alpha^2 \\frac{L}{2} \\|\\nabla f(\\mathbf{x})\\|^2\\\\\n", "&= f(\\mathbf{x}) + \n", "\\left( - \\alpha + \\alpha^2 \\frac{L}{2} \\right) \n", "\\|\\nabla f(\\mathbf{x})\\|^2.\n", "\\end{align*}\n", "\n", "\n", "The quadratic function in parentheses is convex and minimized at the stationary point $\\alpha$ satisfying\n", "\n", "$$\n", "\\frac{\\mathrm{d}}{\\mathrm{d} \\alpha}\\left( - \\alpha + \\alpha^2 \\frac{L}{2} \\right)\n", "= -1 + \\alpha L = 0. \n", "$$\n", "\n", "Taking $\\alpha = 1/L$ and replacing in the inequality above gives\n", "\n", "$$\n", "f(\\mathbf{x} -(1/L) \\nabla f(\\mathbf{x}))\n", "\\leq f(\\mathbf{x}) - \\frac{1}{2L}\\|\\nabla f(\\mathbf{x})\\|^2 \n", "$$\n", "\n", "as claimed. $\\square$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "We give a numerical example below using a special case of logistic regression. But first a calculus exercise." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "*Exercise:* For $a \\in [-1,1]$ and $b \\in \\{0,1\\}$, let $\\hat{f}(x, a) = \\sigma(x a)$ where \n", "\n", "$$\n", "\\sigma(t) = \\frac{1}{1 + e^{-t}}\n", "$$\n", "\n", "be a classifier parametrized by $x \\in \\mathbb{R}$. For a dataset $a_i \\in [-1,1]$ and $b_i \\in \\{0,1\\}$, $i=1,\\ldots,n$, let the cross-entropy loss be\n", "\n", "$$\n", "\\mathcal{L}(x, \\{(a_i, b_i)\\}_{i=1}^n)\n", "= \\frac{1}{n} \\sum_{i=1}^n \\ell(x, a_i, b_i)\n", "$$\n", "\n", "where\n", "\n", "$$\n", "\\ell(x, a, b) = - b \\log(\\hat{f}(x, a))\n", "- (1-b) \\log(1 - \\hat{f}(x, a)).\n", "$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "(a) Show that $\\sigma'(t) = \\sigma(t)(1- \\sigma(t))$ for all $t \\in \\mathbb{R}$.\n", "\n", "(b) Use (a) to show that\n", "\n", "$$\n", "\\frac{\\partial}{\\partial x} \\mathcal{L}(x, \\{(a_i, b_i)\\}_{i=1}^n)\n", "= - \\frac{1}{n} \\sum_{i=1}^n (b_i - \\hat{f}(x,a_i)) \\,a_i.\n", "$$\n", "\n", "(c) Use (b) to show that\n", "\n", "$$\n", "\\frac{\\partial^2}{\\partial x^2} \\mathcal{L}(x, \\{(a_i, b_i)\\}_{i=1}^n)\n", "= \\frac{1}{n} \\sum_{i=1}^n \\hat{f}(x,a_i) \\,(1 - \\hat{f}(x,a_i)) \\,a_i^2.\n", "$$\n", "\n", "(d) Use (c) to show that, for any dataset $\\{(a_i, b_i)\\}_{i=1}^n$, $\\mathcal{L}$ is $1$-smooth as a function of $x$. $\\lhd$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "**NUMERICAL CORNER** We illustrate numerically the exercise above on a random dataset. The functions $\\hat{f}$, $\\mathcal{L}$ and $\\frac{\\partial}{\\partial x}\\mathcal{L}$ are defined next." ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "n = 10000\n", "a = 2*rand(n) .- 1\n", "b = rand(0:1,n)\n", "fhat(x) = 1 ./ ( 1 .+ exp.(-x.*a))\n", "loss(x) = mean(-b.*log.(fhat(x)) - (1 .- b).*log.(1 .- fhat(x)))\n", "grad(x) = -mean((b .- fhat(x)).*a)\n", "x = LinRange(-1,1,100)\n", "plot(x, loss.(x), lw=2, label=\"loss\", legend=:bottomright)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "We plot next the upper and lower bounds in the *Quadratic Bound for Smooth Functions* around $x = x_0$. By the previous exercise, we can take $L=1$. Observe that minimizing the upper quadratic bound leads to a decrease in $\\mathcal{L}$." ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "scrolled": false, "slideshow": { "slide_type": "slide" } }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x0 = -0.3\n", "x = LinRange(x0-0.05,x0+0.05,100)\n", "upper = loss(x0) .+ (x .- x0)*grad(x0) .+ (1/2)*(x .- x0).^2 # upper approximation\n", "lower = loss(x0) .+ (x .- x0)*grad(x0) .- (1/2)*(x .- x0).^2 # lower approximation\n", "plot(x, loss.(x), lw=2, label=\"loss\")\n", "plot!(x, upper, lw=2, label=\"upper\")\n", "plot!(x, lower, lw=2, label=\"lower\")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "$\\lhd$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "We return to the proof of the theorem. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "*Proof idea (Convergence of Steepest Descent in Smooth Case):* We use a telescoping argument to write $f(\\mathbf{x}^H)$ as a sum of stepwise increments, each of which can be bounded by the previous lemma. Because $f(\\mathbf{x}^H)$ is bounded from below, it then follows that the gradients must vanish in the limit." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "*Proof (Convergence of Steepest Descent in Smooth Case):* By the *Descent Guarantee in the Smooth Case*, \n", "\n", "$$\n", "f(\\mathbf{x}^{t+1}) \\leq f(\\mathbf{x}^t) - \\frac{1}{2 L}\\|\\nabla f(\\mathbf{x}^t)\\|^2\n", "\\leq f(\\mathbf{x}^t),\n", "\\quad \\forall t.\n", "$$\n", "\n", "Furthermore, using a telescoping sum, we get\n", "\n", "\n", "\\begin{align*}\n", "f(\\mathbf{x}^H)\n", "&= f(\\mathbf{x}^0) + \\sum_{t=0}^{H-1} [f(\\mathbf{x}^{t+1}) - f(\\mathbf{x}^t)]\\\\\n", "&= f(\\mathbf{x}^0) - \\frac{1}{2 L}\\sum_{t=0}^{H-1} \\|\\nabla f(\\mathbf{x}^t)\\|^2. \n", "\\end{align*}\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "Rearranging and using $f(\\mathbf{x}^H) \\geq \\bar{f}$ leads to\n", "\n", "$$\n", "\\sum_{t=0}^{H-1} \\|\\nabla f(\\mathbf{x}^t)\\|^2\n", "\\leq 2L [f(\\mathbf{x}^0) - \\bar{f}].\n", "$$\n", "\n", "So as $H \\to +\\infty$, we must have $\\|\\nabla f(\\mathbf{x}^H)\\|^2 \\to 0$. We also get the more quantitative bound\n", "\n", "$$\n", "\\min_{t=0,\\ldots, H-1} \\|\\nabla f(\\mathbf{x}^t)\\|^2 \\leq \\frac{2L [f(\\mathbf{x}^0) - \\bar{f}]}{H}\n", "$$\n", "\n", "as the minimum is necessarily less or equal than the average. That proves the last claim. $\\square$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "#### 4.2.2 Smooth and strongly convex case\n", "\n", "With stronger assumptions, we can obtained stronger convergence results. One such assumption is strong convexity, which we define next. Compare the definition with that of a smooth function." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "**Definition (Strongly Convex Function):** Let $f : \\mathbb{R}^d \\to \\mathbb{R}$ be twice continuously differentiable and let $m > 0$. We say that $f$ is $m$-strongly convex if \n", "\n", "$$\n", "\\mathbf{H}_f(\\mathbf{x}) \\succeq m I_{d \\times d},\n", "\\quad \\forall \\mathbf{x} \\in \\mathbb{R}^d.\n", "$$ \n", "\n", "$\\lhd$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "*Exercise:* Consider the quadratic function \n", "\n", "$$\n", "f(\\mathbf{x})\n", "= \\frac{1}{2} \\mathbf{x}^T P \\mathbf{x} + \\mathbf{q}^T \\mathbf{x} + r\n", "$$\n", "\n", "where $P$ is symmetric. Show that, if $P$ is positive definite, then $f$ is strongly convex. $\\lhd$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "The proof of the following lemma is left as an exercise." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "***\n", "\n", "**Lemma (Quadratic Bound for Strongly Convex Functions):** Let $f : \\mathbb{R}^d \\to \\mathbb{R}$ be twice continuously differentiable. Then $f$ is $m$-strongly convex if and only if for all $\\mathbf{x}, \\mathbf{y} \\in \\mathbb{R}^d$ it holds that\n", "\n", "$$\n", "f(\\mathbf{y})\n", "\\geq f(\\mathbf{x}) \n", "+ \\nabla f(\\mathbf{x})^T(\\mathbf{y} - \\mathbf{x})\n", "+ \\frac{m}{2} \\|\\mathbf{y} - \\mathbf{x}\\|^2.\n", "$$\n", "\n", "***" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "*Exercise:* Prove the *Quadratic Bound for Strongly Convex Functions*. [Hint: Adapt the proof of the *Quadratic Bound for Smooth Functions*.] $\\lhd$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "The previous lemma immediately leads to the following fundamental result." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "***\n", "\n", "**Theorem (Global Minimizer of Strongly Convex Functions):** Let $f : \\mathbb{R}^d \\to \\mathbb{R}$ be twice continuously differentiable and $m$-strongly convex with $m>0$. If $\\nabla f(\\mathbf{x}^*) = \\mathbf{0}$, then $\\mathbf{x}^*$ is a unique global minimizer of $f$.\n", "\n", "***" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "*Proof:* If $\\nabla f(\\mathbf{x}^*) = \\mathbf{0}$, by the *Quadratic Bound for Strongly Convex Functions*, \n", "\n", "$$\n", "f(\\mathbf{y})\n", "\\geq f(\\mathbf{x}^*) \n", "+ \\nabla f(\\mathbf{x}^*)^T(\\mathbf{y} - \\mathbf{x}^*)\n", "+ \\frac{m}{2} \\|\\mathbf{y} - \\mathbf{x}^*\\|^2\n", "> f(\\mathbf{x}^*) \n", "$$\n", "\n", "for all $\\mathbf{y} \\neq \\mathbf{x}^*$, which proves the claim. $\\square$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "We are now ready to prove our convergence result for smooth, strongly convex functions. We will show something stronger this time. We will control the value of $f$ itself and obtain a much faster rate of convergence. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "If $f$ is $m$-strongly convex and has a global minimizer $\\mathbf{x}^*$, then the global minimizer is unique and characterized by $\\nabla f(\\mathbf{x}^*) = \\mathbf{0}$. Strong convexity allows us to relate the value of the function at a point $\\mathbf{x}$ and the gradient of $f$ at that point. This is proved in the following lemma, which is key to our convergence results." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "***\n", "\n", "**Lemma (Relating $f$ and $\\nabla f$):** Let $f : \\mathbb{R}^d \\to \\mathbb{R}$ be twice continuously differentiable, $m$-strongly convex with a global minimizer at $\\mathbf{x}^*$. Then for any $\\mathbf{x} \\in \\mathbb{R}^d$\n", "\n", "$$\n", "f(\\mathbf{x}) - f(\\mathbf{x}^*) \\leq \\frac{\\|\\nabla f(\\mathbf{x})\\|^2}{2 m}.\n", "$$\n", "\n", "***" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "*Proof:* By the *Quadratic Bound for Strongly Convex Functions*, \n", "\n", "\n", "\\begin{align*}\n", "f(\\mathbf{x}^*)\n", "&\\geq f(\\mathbf{x}) + \\nabla f(\\mathbf{x})^T (\\mathbf{x}^* - \\mathbf{x})\n", "+ \\frac{m}{2} \\|\\mathbf{x}^* - \\mathbf{x}\\|^2\\\\\n", "&= f(\\mathbf{x}) + \\nabla f(\\mathbf{x})^T \\mathbf{w}\n", "+ \\frac{1}{2} \\mathbf{w}^T (m I_{d \\times d}) \\mathbf{w}\n", "\\end{align*}\n", "\n", "\n", "where on the second line we defined $\\mathbf{w} = \\mathbf{x}^* - \\mathbf{x}$. The right-hand side is a quadratic function in $\\mathbf{w}$ (for $\\mathbf{x}$ fixed). So the inequality is still valid if we replace $\\mathbf{w}$ with the global minimizer $\\mathbf{w}^*$ of that quadratic function." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "The matrix $m I_{d \\times d}$ is positive definite since its eigenvalues are all equal to $m > 0$. By a previous example, we know that\n", "\n", "$$\n", "\\mathbf{w}^* \n", "= - (m I_{d \\times d})^{-1} \\nabla f(\\mathbf{x})\n", "= - \\frac{1}{m} \\nabla f(\\mathbf{x}).\n", "$$\n", "\n", "So, replacing $\\mathbf{w}$ with $\\mathbf{w}^*$, we have the inequality\n", "\n", "\n", "\\begin{align*}\n", "f(\\mathbf{x}^*) \n", "& \\geq f(\\mathbf{x}) + \\nabla f(\\mathbf{x})^T \\left\\{- \\frac{1}{m} \\nabla f(\\mathbf{x})\\right\\}\n", "+ \\frac{1}{2} \\left\\{- \\frac{1}{m} \\nabla f(\\mathbf{x})\\right\\}^T (m I_{d \\times d}) \\left\\{- \\frac{1}{m} \\nabla f(\\mathbf{x})\\right\\}\\\\\n", "& = f(\\mathbf{x}) - \\frac{1}{2m} \\|\\nabla f(\\mathbf{x})\\|^2.\n", "\\end{align*}\n", "\n", "\n", "Rearranging gives the claim. $\\square$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "We can now state our convergence result." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "***\n", "\n", "**Theorem (Convergence of Steepest Descent in Smooth Case):** Suppose that $f : \\mathbb{R}^d \\to \\mathbb{R}$ is $L$-smooth and $m$-strongly convex with a global minimizer at $\\mathbf{x}^*$. Then steepest descent with $\\alpha = 1/L$ started from any $\\mathbf{x}^0$ produces a sequence $\\mathbf{x}^t$, $t=1,2,\\ldots$ such that\n", "\n", "$$\n", "\\lim_{t \\to +\\infty} f(\\mathbf{x}^t) = f(\\mathbf{x}^*).\n", "$$\n", "\n", "Moreover, after $H$ steps, we have\n", "\n", "$$\n", "f(\\mathbf{x}^H) - f(\\mathbf{x}^*)\n", "\\leq \\left(1 - \\frac{m}{L}\\right)^H [f(\\mathbf{x}^0) - f(\\mathbf{x}^*)].\n", "$$\n", "\n", "***" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Observe that $f(\\mathbf{x}^H) - f(\\mathbf{x}^*)$ decreases exponentially fast in $H$." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "*Proof idea (Convergence of Steepest Descent in Smooth Case):* We apply the *Descent Guarantee for Smooth Functions* together with the lemma above. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "*Proof (Convergence of Steepest Descent in Smooth Case):* By the *Descent Guarantee for Smooth Functions* together and the lemma above, we have for all $t$\n", "\n", "$$\n", "f(\\mathbf{x}^{t+1})\n", "\\leq f(\\mathbf{x}^t) - \\frac{1}{2L} \\|\\nabla f(\\mathbf{x}^t)\\|^2\n", "\\leq f(\\mathbf{x}^t) - \\frac{m}{L} [f(\\mathbf{x}^t) - f(\\mathbf{x}^*)].\n", "$$\n", "\n", "Subtracting $f(\\mathbf{x}^*)$ on both sides gives\n", "\n", "$$\n", "f(\\mathbf{x}^{t+1}) - f(\\mathbf{x}^*)\n", "\\leq \\left(1 - \\frac{m}{L}\\right)[f(\\mathbf{x}^t) - f(\\mathbf{x}^*)].\n", "$$\n", "\n", "Recursing gives the claim. $\\square$" ] } ], "metadata": { "kernelspec": { "display_name": "Julia 1.5.1", "language": "julia", "name": "julia-1.5" }, "language_info": { "file_extension": ".jl", "mimetype": "application/julia", "name": "julia", "version": "1.5.1" } }, "nbformat": 4, "nbformat_minor": 2 }