{ "cells": [ { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# TOPIC 3 \n", "\n", "# Optimality, convexity, and gradient descent\n", "\n", "## 1 Background: Jacobian and Hessian; introduction to automatic differentiation\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 10, 2020 \n", "*Copyright:* © 2020 Sebastien Roch\n", "***" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "We further review the differential calculus of several variables. We highlight a few key results that will play an important role: the Chain Rule and the Mean Value Theorem. We also give a brief introduction to automatic differentiation; we will come back later in this topic to the mathematical theory behind it." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### 1.1 Mean value theorem" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "Recalll that a point $\\mathbf{x} \\in \\mathbb{R}^d$ is an interior point of a set $A \\subseteq \\mathbb{R}^d$ if there exists an $r > 0$ such that $B_r(\\mathbf{x}) \\subseteq A$, where the open $r$-ball around $\\mathbf{x} \\in \\mathbb{R}^d$ is the set of points within Euclidean distance $r$ of $\\mathbf{x}$, that is,\n", "\n", "$$\n", "B_r(\\mathbf{x}) = \\{\\mathbf{y} \\in \\mathbb{R}^d \\,:\\, \\|\\mathbf{y} - \\mathbf{x}\\| < r\\}.\n", "$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "![Open set](https://upload.wikimedia.org/wikipedia/commons/thumb/d/de/Open_set_-_example.png/320px-Open_set_-_example.png)\n", "\n", "([Source](https://commons.wikimedia.org/wiki/File:Open_set_-_example.png))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "Recall that the derivative of a function of a real variable is the rate of change of the function with respect to the change in the variable.\n", "\n", "**Definition (Derivative):** Let $f : D \\to \\mathbb{R}$ where $D \\subseteq \\mathbb{R}$ and let $x_0 \\in D$ be an interior point of $D$. The derivative of $f$ at $x_0$ is \n", "\n", "$$\n", "f'(x_0) \n", "= \\frac{\\mathrm{d} f (x_0)}{\\mathrm{d} x}\n", "= \\lim_{h \\to 0} \\frac{f(x_0 + h) - f(x_0)}{h}\n", "$$\n", "\n", "provided the limit exists. $\\lhd$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "![Derivative](https://upload.wikimedia.org/wikipedia/commons/thumb/0/0f/Tangent_to_a_curve.svg/320px-Tangent_to_a_curve.svg.png)\n", "\n", "([Source](https://commons.wikimedia.org/wiki/File:Tangent_to_a_curve.svg))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "Earlier in the course, we proved a key insight about the derivative of $f$ at $x_0$: it tells us where to find smaller values." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "***\n", "\n", "**Lemma (Descent Direction):** Let $f : D \\to \\mathbb{R}$ with $D \\subseteq \\mathbb{R}$ and let $x_0 \\in D$ be an interior point of $D$ where $f'(x_0)$ exists. If $f'(x_0) > 0$, then there is an open ball $B_\\delta(x_0) \\subseteq D$ around $x_0$\n", "such that for each $x$ in $B_\\delta(x_0)$:\n", "\n", "(a) $f(x) > f(x_0)$ if $x > x_0$,\n", "(b) $f(x) < f(x_0)$ if $x < x_0$.\n", "\n", "If instead $f'(x_0) < 0$, the opposite holds.\n", "\n", "***" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "One implication of the *Descent Direction Lemma* is the *Mean Value Theorem*, which will lead us later to *Taylor's Theorem*. First, an important special case:\n", "\n", "***\n", "\n", "**Theorem (Rolle):** Let $f : [a,b] \\to \\mathbb{R}$ be a continuous function and assume that its derivative exists on $(a,b)$. If $f(a) = f(b)$ then there is $a < c < b$ such that $f'(c) = 0$.\n", "\n", "***" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "*Proof idea:* Look at an extremum and use the *Descent Direction Lemma* to get a contradiction.\n", "\n", "![Rolle](https://upload.wikimedia.org/wikipedia/commons/thumb/a/a9/RTCalc.svg/320px-RTCalc.svg.png)\n", "\n", "([Source](https://commons.wikimedia.org/wiki/File:RTCalc.svg))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "*Proof:* If $f(x) = f(a)$ for all $x \\in (a, b)$, then $f'(x) = 0$ on $(a, b)$ and we are done. So assume there is $y \\in (a, b)$ such that $f(y) \\neq f(a)$. Assume without loss of generality that $f(y) > f(a)$ (otherwise consider the function $-f$). By the *Extreme Value Theorem*, $f$ attains a maximum value at some $c \\in [a,b]$. By our assumption, $a$ and $b$ cannot be the location of the maximum and it must be that $c \\in (a, b)$. \n", "\n", "We claim that $f'(c) = 0$. We argue by contradiction. Suppose $f'(c) > 0$. By the *Descent Direction Lemma*, there is a $\\delta > 0$ such that $f(x) > f(c)$ for all $x \\in B_\\delta(c)$, a contradiction. A similar argument holds if $f'(c) < 0$. That concludes the proof. $\\square$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "***\n", "\n", "**Theorem (Mean Value):** Let $f : [a,b] \\to \\mathbb{R}$ be a continuous function and assume that its derivative exists on $(a,b)$. Then there is $a < c < b$ such that\n", "\n", "$$\n", "f(b) = f(a) + (b-a)f'(c),\n", "$$\n", "\n", "or put differently\n", "\n", "$$\n", "\\frac{f(b) - f(a)}{b-a} = f'(c).\n", "$$\n", "\n", "\n", "***" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "*Proof idea:* Apply *Rolle* to \n", "\n", "$$\n", "\\phi(x) = f(x) - \\left[f(a) + \\frac{f(b) - f(a)}{b - a} (x-a)\\right].\n", "$$\n", "\n", "![Mean value](https://upload.wikimedia.org/wikipedia/commons/thumb/e/ee/Mvt2.svg/272px-Mvt2.svg.png)\n", "\n", "([Source](https://commons.wikimedia.org/wiki/File:Mvt2.svg))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "*Proof:* Let $\\phi(x) = f(x) - f(a) - \\frac{f(b) - f(a)}{b - a} (x-a)$. Note that $\\phi(a) = \\phi(b) = 0$ and $\\phi'(x) = f'(x) - \\frac{f(b) - f(a)}{b - a}$ for all $x \\in (a, b)$. Thus, by *Rolle*, there is $c \\in (a, b)$ such that $\\phi'(c) = 0$. That implies $\\frac{f(b) - f(a)}{b - a} = \\phi'(c)$ and plugging into $\\phi(b)$ gives the result. $\\square$\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### 1.2 Jacobian" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "Recall the partial derivative and the gradient:\n", "\n", "**Definition (Partial Derivative):** Let $f : D \\to \\mathbb{R}$ where $D \\subseteq \\mathbb{R}^d$ and let $\\mathbf{x}_0 \\in D$ be an interior point of $D$. The partial derivative of $f$ at $\\mathbf{x}_0$ with respect to $x_i$ is \n", "\n", "$$\n", "\\frac{\\partial f (\\mathbf{x}_0)}{\\partial x_i} \n", "= \\lim_{h \\to 0} \\frac{f(\\mathbf{x}_0 + h \\mathbf{e}_i) - f(\\mathbf{x}_0)}{h}\n", "$$\n", "\n", "provided the limit exists. If $\\frac{\\partial f (\\mathbf{x}_0)}{\\partial x_i}$ exists and is continuous in an open ball around $\\mathbf{x}_0$ for all $i$, then we say that $f$ continuously differentiable at $\\mathbf{x}_0$. $\\lhd$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "**Definition (Gradient):** Let $f : D \\to \\mathbb{R}$ where $D \\subseteq \\mathbb{R}^d$ and let $\\mathbf{x}_0 \\in D$ be an interior point of $D$. Assume $f$ is continuously differentiable at $\\mathbf{x}_0$. The vector\n", "\n", "$$\n", "\\nabla f(\\mathbf{x}_0) \n", "= \\left(\\frac{\\partial f (\\mathbf{x}_0)}{\\partial x_1}, \\ldots, \\frac{\\partial f (\\mathbf{x}_0)}{\\partial x_d}\\right)^T\n", "$$\n", "\n", "is called the gradient of $f$ at $\\mathbf{x}_0$. $\\lhd$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "For vector-valued functions, we have the following generalization." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "**Definition (Jacobian):** Let $\\mathbf{f} = (f_1, \\ldots, f_m) : D \\to \\mathbb{R}^m$ where $D \\subseteq \\mathbb{R}^d$ and let $\\mathbf{x}_0 \\in D$ be an interior point of $D$ where $\\frac{\\partial f_j (\\mathbf{x}_0)}{\\partial x_i}$ exists for all $i, j$. The Jacobian of $\\mathbf{f}$ at $\\mathbf{x}_0$ is the $d \\times m$ matrix\n", "\n", "$$\n", "\\mathbf{J}_{\\mathbf{f}}(\\mathbf{x}_0)\n", "= \\begin{pmatrix}\n", "\\frac{\\partial f_1 (\\mathbf{x}_0)}{\\partial x_1}\n", "& \\ldots & \\frac{\\partial f_1 (\\mathbf{x}_0)}{\\partial x_d}\\\\\n", "\\vdots & \\ddots & \\vdots\\\\\n", "\\frac{\\partial f_m (\\mathbf{x}_0)}{\\partial x_1}\n", "& \\ldots & \\frac{\\partial f_m (\\mathbf{x}_0)}{\\partial x_d}\n", "\\end{pmatrix}.\n", "$$\n", "\n", "For a real-valued function $f : D \\to \\mathbb{R}$, the Jacobian reduces to the row vector\n", "\n", "$$\n", "\\mathbf{J}_{f}(\\mathbf{x}_0)\n", "= \\nabla f(\\mathbf{x}_0)^T\n", "$$\n", "\n", "where $\\nabla f(\\mathbf{x}_0)$ is the gradient of $f$ at $\\mathbf{x}_0$. $\\lhd$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "Functions are often obtained from the composition of simpler ones. We will use the standard notation $h = g \\circ f$ for the function $h(\\mathbf{x}) = g(f(\\mathbf{x}))$.\n", "\n", "***\n", "\n", "**Lemma (Composition of Continuous Functions):** Let $\\mathbf{f} : D_1 \\to \\mathbb{R}^m$, where $D_1 \\subseteq \\mathbb{R}^d$, and let $\\mathbf{g} : D_2 \\to \\mathbb{R}^p$, where $D_2 \\subseteq \\mathbb{R}^m$. Assume that $\\mathbf{f}$ is continuous at $\\mathbf{x}_0$ and that $\\mathbf{g}$ is continuous $\\mathbf{f}(\\mathbf{x}_0)$. Then $g \\circ f$ is continuous at $\\mathbf{x}_0$.\n", "\n", "***\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "*Exercise:* Prove the Composition of Continuous Functions Lemma. $\\lhd$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "The chain rule gives a formula for the Jacobian of a composition. We will use the vector notation $\\mathbf{h} = \\mathbf{g} \\circ \\mathbf{f}$ for the function $\\mathbf{h}(\\mathbf{x}) = \\mathbf{g} (\\mathbf{f} (\\mathbf{x}))$.\n", "\n", "***\n", "\n", "**Theorem (Chain Rule):** Let $\\mathbf{f} : D_1 \\to \\mathbb{R}^m$, where $D_1 \\subseteq \\mathbb{R}^d$, and let $\\mathbf{g} : D_2 \\to \\mathbb{R}^p$, where $D_2 \\subseteq \\mathbb{R}^m$. Assume that $\\mathbf{f}$ is continuously differentiable at $\\mathbf{x}_0$, an interior point of $D_1$, and that $\\mathbf{g}$ is continuously differentiable at $\\mathbf{f}(\\mathbf{x}_0)$, an interior point of $D_2$. Then\n", "\n", "$$\n", "\\mathbf{J}_{\\mathbf{g} \\circ \\mathbf{f}}(\\mathbf{x}_0)\n", "= \\mathbf{J}_{\\mathbf{g}}(\\mathbf{f}(\\mathbf{x}_0))\n", "\\,\\mathbf{J}_{\\mathbf{f}}(\\mathbf{x}_0)\n", "$$\n", "\n", "as a product of matrices.\n", "\n", "***" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "*Proof:* To simplify the notation, we begin with a special case. Suppose that $f$ is a real-valued function of $\\mathbf{x} = (x_1, \\ldots, x_m)$ whose components are themselves functions of $t \\in \\mathbb{R}$. Assume $f$ is continuously differentiable at $\\mathbf{x}(t)$. To compute the [total derivative](https://en.wikipedia.org/wiki/Total_derivative) $\\frac{\\mathrm{d} f(t)}{\\mathrm{d} t}$, let $\\Delta x_k = x_k(t + \\Delta t) - x_k(t)$, $x_k = x_k(t)$ and\n", "\n", "$$\n", "\\Delta f \n", "= \n", "f(x_1 + \\Delta x_1, \\ldots, x_m + \\Delta x_m)\n", "-\n", "f(x_1, \\ldots, x_m).\n", "$$\n", "\n", "We seek to compute the limit $\\lim_{\\Delta t \\to 0} \\frac{\\Delta f}{\\Delta t}$. To relate this limit to partial derivatives of $f$, we re-write $\\Delta f$ as a telescoping sum where each term involves variation of a single variable $x_k$. That is,\n", "\n", "\n", "\\begin{align*}\n", "\\Delta f\n", "= \n", "& [f(x_1 + \\Delta x_1, \\ldots, x_m + \\Delta x_m)\n", "-\n", "f(x_1, x_2 + \\Delta x_2, \\ldots, x_m + \\Delta x_m)]\\\\\n", "&+ [f(x_1, x_2 + \\Delta x_2, \\ldots, x_m + \\Delta x_m)\n", "-\n", "f(x_1, x_2, x_3 + \\Delta x_3, \\ldots, x_m + \\Delta x_m)]\\\\\n", "&+ \\cdots + \n", "[f(x_1, \\cdots, x_{m-1}, x_m + \\Delta x_m)\n", "-\n", "f(x_1, \\ldots, x_m)].\n", "\\end{align*}\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "Applying the *Mean Value Theorem* to each term gives\n", "\n", "\n", "\\begin{align*}\n", "\\Delta f\n", "= \n", "& \\Delta x_1 \n", "\\frac{\\partial f(x_1 + \\theta_1 \\Delta x_1, x_2 + \\Delta x_2, \\ldots, x_m + \\Delta x_m)}\n", "{\\partial x_1}\\\\\n", "&+ \\Delta x_2 \n", "\\frac{\\partial f(x_1, x_2 + \\theta_2 \\Delta x_2, x_3 + \\Delta x_3, \\ldots, x_m + \\Delta x_m)}\n", "{\\partial x_2}\\\\\n", "&+ \\cdots + \\Delta x_m\n", "\\frac{\\partial f(x_1, \\cdots, x_{m-1}, x_m + \\theta_m \\Delta x_m)}\n", "{\\partial x_m}\n", "\\end{align*}\n", "\n", "\n", "where $0 < \\theta_k < 1$ for $k=1,\\ldots,m$. Dividing by $\\Delta t$, taking the limit $\\Delta t \\to 0$ and using the fact that $f$ is continuously differentiable, we get\n", "\n", "$$\n", "\\frac{\\mathrm{d} f (t)}{\\mathrm{d} t}\n", "= \\sum_{k=1}^m \\frac{\\partial f(\\mathbf{x}(t))}\n", "{\\partial x_k} \\frac{\\mathrm{d} x_k(t)}{\\mathrm{d} t}.\n", "$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "Going back to the general case, the same argument shows that\n", "\n", "$$\n", "\\frac{\\partial h_i(\\mathbf{x}_0)}{\\partial x_j}\n", "= \\sum_{k=1}^m \\frac{\\partial g_i(\\mathbf{f}(\\mathbf{x}_0))}\n", "{\\partial f_k} \\frac{\\partial f_k(\\mathbf{x}_0)}{\\partial x_j}\n", "$$\n", "\n", "where the notation $\\frac{\\partial g}\n", "{\\partial f_k}$ indicates the partial derivative of $g$ with respect to its $k$-th component. In matrix form, the claim follows. $\\square$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "**NUMERICAL CORNER** We illustrate the use of [automatic differentiation](https://en.wikipedia.org/wiki/Automatic_differentiation) to compute gradients. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "Quoting [Wikipedia](https://en.wikipedia.org/wiki/Automatic_differentiation):\n", "\n", "> In mathematics and computer algebra, automatic differentiation (AD), also called algorithmic differentiation or computational differentiation, is a set of techniques to numerically evaluate the derivative of a function specified by a computer program. AD exploits the fact that every computer program, no matter how complicated, executes a sequence of elementary arithmetic operations (addition, subtraction, multiplication, division, etc.) and elementary functions (exp, log, sin, cos, etc.). By applying the chain rule repeatedly to these operations, derivatives of arbitrary order can be computed automatically, accurately to working precision, and using at most a small constant factor more arithmetic operations than the original program. Automatic differentiation is distinct from symbolic differentiation and numerical differentiation (the method of finite differences). Symbolic differentiation can lead to inefficient code and faces the difficulty of converting a computer program into a single expression, while numerical differentiation can introduce round-off errors in the discretization process and cancellation." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "We will use the [Flux.jl](https://github.com/FluxML/Flux.jl) package. The gradient function takes another Julia function f and a set of arguments, and returns the gradient with respect to each argument. Here is an example." ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "# Julia version: 1.5.1\n", "ENV[\"JULIA_CUDA_SILENT\"] = true # silences warning about GPUs\n", "\n", "using Flux" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "f(x, y) = 3x^2 + exp(x) + y;" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "df(x, y) = gradient(f, x, y);" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "(8.718281828459045, 1.0)" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "df(1., 2.) # answer is (6 + e, 1)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "We get the same answer by setting each parameter in the call to gradient." ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "slideshow": { "slide_type": "skip" } }, "outputs": [ { "data": { "text/plain": [ "8.718281828459045" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "gradient(f, 1., 2.)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "The input parameters can also be vectors, which allows to consider function of large numbers of variables. " ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "g(z) = sum(z.^2);" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "3-element Array{Float64,1}:\n", " 2.0\n", " 4.0\n", " 6.0" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "gradient(g, [1., 2., 3.]) # gradient is (2 z_1, 2 z_2, 2 z_3)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "Finally, the function params can also be used to specify the parameters with respect to which derivatives are to be taken. Here is a typical example." ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "loss (generic function with 1 method)" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "predict(X) = X*theta # classifier with parameter vector θ\n", "loss(X, y) = sum((predict(X) - y).^2) # loss function" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "2-element Array{Float64,1}:\n", " 1.9560808628127127\n", " 1.6881129851496863" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(X, y) = (randn(3, 2), [1., 0., 1.]); # dataset (features, labels)\n", "theta = ones(2) # parameter assignment\n", "gradient(() -> loss(X, y), params(theta))[theta]" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### 1.3 Further derivatives" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "Partial derivatives measure the rate of change of a function along the axes. More generally:\n", "\n", "**Definition (Directional Derivative):** Let $f : D \\to \\mathbb{R}$ where $D \\subseteq \\mathbb{R}^d$, let $\\mathbf{x}_0 \\in D$ be an interior point of $D$ and let $\\mathbf{v} \\in \\mathbb{R}^d$ be a unit vector. The directional derivative of $f$ at $\\mathbf{x}_0$ in the direction $\\mathbf{v}$ is \n", "\n", "$$\n", "\\frac{\\partial f (\\mathbf{x}_0)}{\\partial \\mathbf{v}} \n", "= \\lim_{h \\to 0} \\frac{f(\\mathbf{x}_0 + h \\mathbf{v}) - f(\\mathbf{x}_0)}{h}\n", "$$\n", "\n", "provided the limit exists. $\\lhd$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "Note that taking $\\mathbf{v} = \\mathbf{e}_i$ recovers the $i$-th partial derivative\n", "\n", "$$\n", "\\frac{\\partial f (\\mathbf{x}_0)}{\\partial \\mathbf{e}_i} \n", "= \\lim_{h \\to 0} \\frac{f(\\mathbf{x}_0 + h \\mathbf{e}_i) - f(\\mathbf{x}_0)}{h}\n", "= \\frac{\\partial f (\\mathbf{x}_0)}{\\partial x_i}.\n", "$$\n", "\n", "Conversely, a general directional derivative can be expressed in terms of the partial derivatives.\n", "\n", "***\n", "\n", "**Theorem (Directional Derivative from Gradient):** Let $f : D \\to \\mathbb{R}$ where $D \\subseteq \\mathbb{R}^d$, let $\\mathbf{x}_0 \\in D$ be an interior point of $D$ and let $\\mathbf{v} \\in \\mathbb{R}^d$ be a unit vector. Assume that $f$ is continuously differentiable at $\\mathbf{x}_0$. Then the directional derivative of $f$ at $\\mathbf{x}_0$ in the direction $\\mathbf{v}$ is given by\n", "\n", "$$\n", "\\frac{\\partial f (\\mathbf{x}_0)}{\\partial \\mathbf{v}} \n", "= \\mathbf{J}_f(\\mathbf{x}_0) \\,\\mathbf{v}\n", "= \\nabla f(\\mathbf{x}_0)^T \\mathbf{v}.\n", "$$\n", "\n", "***" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "*Proof idea:* To bring out the partial derivatives, we re-write the directional derivative as the derivative of a composition of $f$ with an affine function. We then use the chain rule." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "*Proof:* Consider the composition $\\beta(h) = f(\\boldsymbol{\\alpha}(h))$ where $\\boldsymbol{\\alpha}(h) = \\mathbf{x}_0 + h \\mathbf{v}$. Observe that $\\boldsymbol{\\alpha}(0)= \\mathbf{x}_0$ and $\\beta(0)= f(\\mathbf{x}_0)$. Then, by definition of the derivative,\n", "\n", "$$\n", "\\frac{\\mathrm{d} \\beta(0)}{\\mathrm{d} h}\n", "= \\lim_{h \\to 0} \\frac{\\beta(h) - \\beta(0)}{h}\n", "= \\lim_{h \\to 0} \\frac{f(\\mathbf{x}_0 + h \\mathbf{v}) - f(\\mathbf{x}_0)}{h}\n", "= \\frac{\\partial f (\\mathbf{x}_0)}{\\partial \\mathbf{v}}.\n", "$$\n", "\n", "Applying the *Chain Rule*, we arrive at \n", "\n", "$$\n", "\\frac{\\mathrm{d} \\beta(0)}{\\mathrm{d} h}\n", "= \\mathbf{J}_\\beta(0)\n", "= \\mathbf{J}_f(\\boldsymbol{\\alpha}(0)) \n", "\\,\\mathbf{J}_{\\boldsymbol{\\alpha}}(0)\n", "= \\mathbf{J}_f(\\mathbf{x}_0) \n", "\\,\\mathbf{J}_{\\boldsymbol{\\alpha}}(0).\n", "$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "It remains to compute $\\mathbf{J}_{\\boldsymbol{\\alpha}}(0)$. By the linearity of derivatives (proved in a preivous exercise), \n", "\n", "$$\n", "\\frac{\\partial \\alpha_i(h)}{\\partial h} \n", "= [x_{0,i} + h v_i]' = v_i\n", "$$\n", "\n", "where we denote $\\boldsymbol{\\alpha} = (\\alpha_1, \\ldots, \\alpha_d)^T$ and $\\mathbf{x}_0 = (x_{0,1}, \\ldots, x_{0,d})^T$. So $\\mathbf{J}_{\\boldsymbol{\\alpha}}(0) = \\mathbf{v}$ and we get finally\n", "\n", "$$\n", "\\frac{\\mathrm{d} \\beta(0)}{\\mathrm{d} h}\n", "= \\mathbf{J}_f(\\mathbf{x}_0)\\,\\mathbf{v}, \n", "$$\n", "\n", "as claimed. $\\square$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "One can also define higher-order derivatives. We start with the single-variable case, where $f : D \\to \\mathbb{R}$ with $D \\subseteq \\mathbb{R}$ and $x_0 \\in D$ is an interior point of $D$. . Note that, if $f'$ exists in $D$, then it is itself a function of $x$. Then the second derivative at $x_0$ is\n", "\n", "$$\n", "f''(x_0)\n", "= \\frac{\\mathrm{d}^2 f(x_0)}{\\mathrm{d} x^2}\n", "= \\lim_{h \\to 0} \\frac{f'(x_0 + h) - f'(x_0)}{h}\n", "$$\n", "\n", "provided the limit exists." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "We can also take higher-order derivatives. We will restrict ourselves to the second order.\n", "\n", "**Definition (Second Partial Derivatives and Hessian):** Let $f : D \\to \\mathbb{R}$ where $D \\subseteq \\mathbb{R}^d$ and let $\\mathbf{x}_0 \\in D$ be an interior point of $D$. Assume that $f$ is continuously differentiable in an open ball around $\\mathbf{x}_0$. Then $\\partial f(\\mathbf{x})/\\partial x_i$ is itself a function of $\\mathbf{x}$ and its partial derivative with respect to $x_j$, if it exists, is denoted by\n", "\n", "$$\n", "\\frac{\\partial^2 f(\\mathbf{x}_0)}{\\partial x_j \\partial x_i}\n", "= \\lim_{h \\to 0} \\frac{\\partial f(\\mathbf{x}_0 + h \\mathbf{e}_j)/\\partial x_i - \\partial f(\\mathbf{x}_0)/\\partial x_i}{h}.\n", "$$\n", "\n", "To simplify the notation, we write this as $\\partial^2 f(\\mathbf{x}_0)/\\partial x_i^2$ when $j = i$. If $\\partial^2 f(\\mathbf{x})/\\partial x_j \\partial x_i$ and $\\partial^2 f(\\mathbf{x})/\\partial x_i^2$ exist and are continuous in an open ball around $\\mathbf{x}_0$ for all $i, j$, we say that $f$ is twice continuously differentiable at $\\mathbf{x}_0$.\n", "\n", "The Jacobian of the gradient $\\nabla f$ is called the Hessian and is denoted by\n", "\n", "$$\n", "\\mathbf{H}_f(\\mathbf{x}_0)\n", "= \\begin{pmatrix}\n", "\\frac{\\partial^2 f(\\mathbf{x}_0)}{\\partial x_1^2} \n", "& \\cdots \n", "& \\frac{\\partial^2 f(\\mathbf{x}_0)}{\\partial x_d \\partial x_1}\\\\\n", "\\vdots & \\ddots & \\vdots\\\\\n", "\\frac{\\partial^2 f(\\mathbf{x}_0)}{\\partial x_1 \\partial x_d} \n", "& \\cdots \n", "& \\frac{\\partial^2 f(\\mathbf{x}_0)}{\\partial x_d^2}\n", "\\end{pmatrix}.\n", "$$\n", "\n", "$\\lhd$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "When $f$ is twice continuously differentiable at $\\mathbf{x}_0$, its Hessian is a symmetric matrix.\n", "\n", "***\n", "\n", "**Theorem (Symmetry of the Hessian):** Let $f : D \\to \\mathbb{R}$ where $D \\subseteq \\mathbb{R}^d$ and let $\\mathbf{x}_0 \\in D$ be an interior point of $D$. Assume that $f$ is twice continuously differentiable at $\\mathbf{x}_0$. Then for all $i \\neq j$\n", "\n", "$$\n", "\\frac{\\partial^2 f(\\mathbf{x}_0)}{\\partial x_j \\partial x_i}\n", "= \\frac{\\partial^2 f(\\mathbf{x}_0)}{\\partial x_i \\partial x_j}.\n", "$$\n", "\n", "***" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "*Proof idea:* Two applications of the *Mean Value Theorem* show that the limits can be interchanged." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "*Proof:* By definition of the partial derivative,\n", "\n", "\n", "\\begin{align*}\n", "\\frac{\\partial^2 f(\\mathbf{x}_0)}{\\partial x_j \\partial x_i}\n", "&= \\lim_{h_j \\to 0} \\frac{\\partial f(\\mathbf{x}_0 + h_j \\mathbf{e}_j)/\\partial x_i - \\partial f(\\mathbf{x}_0)/\\partial x_i}{h_j}\\\\\n", "&= \\lim_{h_j \\to 0} \\lim_{h_i \\to 0} \\frac{1}{h_j h_i}\n", "\\left\\{\n", "[f(\\mathbf{x}_0 + h_j \\mathbf{e}_j + h_i \\mathbf{e}_i)\n", "- f(\\mathbf{x}_0 + h_j \\mathbf{e}_j)]\n", "- [f(\\mathbf{x}_0 + h_i \\mathbf{e}_i)\n", "- f(\\mathbf{x}_0)]\n", "\\right\\}\\\\\n", "&= \\lim_{h_j \\to 0} \\lim_{h_i \\to 0} \\frac{1}{h_i}\n", "\\left\\{\n", "\\frac{[f(\\mathbf{x}_0 + h_i \\mathbf{e}_i + h_j \\mathbf{e}_j)\n", "- f(\\mathbf{x}_0 + h_i \\mathbf{e}_i)]\n", "- [f(\\mathbf{x}_0 + h_j \\mathbf{e}_j)\n", "- f(\\mathbf{x}_0)]}{h_j}\n", "\\right\\}\\\\\n", "&= \\lim_{h_j \\to 0} \\lim_{h_i \\to 0} \\frac{1}{h_i}\n", "\\left\\{\\frac{\\partial}{\\partial x_j}[f(\\mathbf{x}_0 + h_i \\mathbf{e}_i + \\theta_j h_j \\mathbf{e}_j)\n", "- f(\\mathbf{x}_0 + \\theta_j h_j \\mathbf{e}_j)]\n", "\\right\\}\\\\\n", "&= \\lim_{h_j \\to 0} \\lim_{h_i \\to 0} \\frac{1}{h_i}\n", "\\left\\{\\partial f(\\mathbf{x}_0 + h_i \\mathbf{e}_i + \\theta_j h_j \\mathbf{e}_j)/\\partial x_j\n", "- \\partial f(\\mathbf{x}_0 + \\theta_j h_j \\mathbf{e}_j)/\\partial x_j\n", "\\right\\}\n", "\\end{align*}\n", "\n", "\n", "for some $\\theta_j \\in (0,1)$. Note that, on the third line, we rearranged the terms and, on the fourth line, we applied the Mean Value Theorem to $f(\\mathbf{x}_0 + h_i \\mathbf{e}_i + h_j \\mathbf{e}_j) - f(\\mathbf{x}_0 + h_j \\mathbf{e}_j)$ as a continuously differentiable function of $h_j$. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "Because $\\partial f/\\partial x_j$ is continuously differentiable in an open ball around $\\mathbf{x}_0$, a second application of the Mean Value Theorem gives for some $\\theta_i \\in (0,1)$\n", "\n", "\n", "\\begin{align*}\n", "&\\lim_{h_j \\to 0} \\lim_{h_i \\to 0} \\frac{1}{h_i}\n", "\\left\\{\\partial f(\\mathbf{x}_0 + h_i \\mathbf{e}_i + \\theta_j h_j \\mathbf{e}_j)/\\partial x_j\n", "- \\partial f(\\mathbf{x}_0 + \\theta_j h_j \\mathbf{e}_j)/\\partial x_j\n", "\\right\\}\\\\\n", "&= \\lim_{h_j \\to 0} \\lim_{h_i \\to 0} \n", "\\frac{\\partial}{\\partial x_i}\\left[\\partial f(\\mathbf{x}_0 + \\theta_j h_j \\mathbf{e}_j + \\theta_i h_i \\mathbf{e}_i)/\\partial x_j\\right]\\\\\n", "&= \\lim_{h_j \\to 0} \\lim_{h_i \\to 0} \\frac{\\partial^2 f(\\mathbf{x}_0 + \\theta_j h_j \\mathbf{e}_j + \\theta_i h_i \\mathbf{e}_i)}{\\partial x_i \\partial x_j}.\n", "\\end{align*}\n", "\n", "\n", "The claim then follows from the continuity of $\\partial^2 f/\\partial x_i \\partial x_j$. $\\square$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "**Example:** Consider again 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", "Recall that the gradient of $f$ is\n", "\n", "$$\n", "\\nabla f(\\mathbf{x})\n", "= \\frac{1}{2}[P + P^T] \\,\\mathbf{x}\n", "+ \\mathbf{q}.\n", "$$\n", "\n", "Each component of $\\nabla f$ is an affine function of $\\mathbf{x}$, so by our previous result the gradient of $\\nabla f$ is\n", "\n", "$$\n", "\\mathbf{H}_f = \\frac{1}{2}[P + P^T].\n", "$$\n", "\n", "Observe that this is indeed a symmetric matrix. $\\lhd$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "**NUMERICAL CORNER** We return to [automatic differentiation](https://en.wikipedia.org/wiki/Automatic_differentiation). " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "Each component of the output of gradient(f, x, y) is itself a function and can also be differentiated to obtain the second derivative." ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "slideshow": { "slide_type": "slide" } }, "outputs": [ { "data": { "text/plain": [ "f (generic function with 1 method)" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "f(x, y) = x * y + x^2 + exp(x) * cos(y)" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "dfdx(x, y) = gradient(f, x, y)\n", "dfdy(x, y) = gradient(f, x, y);" ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "1.0" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "dfdx(0., 0.) # answer is 1 (see example is next notebook)" ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "df2dx2 (generic function with 1 method)" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "df2dx2(x, y) = gradient(dfdx, x, y)" ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "3.0" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "df2dx2(0., 0.) # answer is 3 (see example is next notebook)" ] } ], "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 }