{
 "cells": [
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "---\n",
    "execute:\n",
    "  enabled: false\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-multivariable-calculus-md-1 fw=all -->\n",
    "\n",
    "# Multivariable Calculus\n",
    "\n",
    "A deep network's loss is a function of millions to billions of weights, yet\n",
    "training rests on a single question asked over and over: how does the loss\n",
    "change when we nudge the parameters? that section\n",
    "answered this for one variable. This section lifts that local-linear picture to\n",
    "many variables. The central object is the *gradient*, and we will see three\n",
    "things about it that the rest of deep learning leans on: it is the multivariable\n",
    "derivative (a first-order approximation), it points in the direction of steepest\n",
    "change (which is why we descend along it), and organizing the chain rule around\n",
    "it *is* the backpropagation algorithm. We close with the *Hessian*, the\n",
    "second-order term that tells a minimum from a saddle.\n",
    "\n",
    "## From Partial Derivatives to the Gradient\n",
    "\n",
    "### Partial Derivatives\n",
    "\n",
    "The one observation we already have is this: if we change a *single* weight\n",
    "$w_1$ and freeze the rest, we are back to a function of one variable, and\n",
    "that section applies verbatim:\n",
    "\n",
    "$$L(w_1+\\epsilon_1, w_2, \\ldots, w_N) \\approx L(w_1, w_2, \\ldots, w_N) + \\epsilon_1 \\frac{\\partial}{\\partial w_1} L(w_1, w_2, \\ldots, w_N).$$\n",
    "\n",
    "The derivative in one variable *while holding the others fixed* is the *partial\n",
    "derivative*, written $\\frac{\\partial}{\\partial w_1}$. The new idea is what\n",
    "happens when we perturb several coordinates at once.\n",
    "\n",
    "### The Gradient\n",
    "\n",
    "Suppose we perturb every coordinate, replacing each $w_i$ by $w_i + \\epsilon_i$.\n",
    "Apply the equation one coordinate at a time. Changing $w_1$\n",
    "contributes $\\epsilon_1\\frac{\\partial L}{\\partial w_1}$; changing $w_2$\n",
    "contributes $\\epsilon_2\\frac{\\partial L}{\\partial w_2}$, and so on. The\n",
    "corrections that involve *two* perturbations, like\n",
    "$\\epsilon_1\\epsilon_2\\frac{\\partial^2 L}{\\partial w_1 \\partial w_2}$, are\n",
    "products of small quantities (second order), and we discard them exactly as we\n",
    "discarded $\\epsilon^2$ in one variable. What survives is a single sum:\n",
    "\n",
    "$$\n",
    "L(w_1+\\epsilon_1, \\ldots, w_N+\\epsilon_N) \\approx L(w_1, \\ldots, w_N) + \\sum_{i=1}^N \\epsilon_i \\frac{\\partial L}{\\partial w_i}.\n",
    "$$\n",
    "\n",
    "That sum on the right is a dot product. Collecting the perturbations and the\n",
    "partials into vectors,\n",
    "\n",
    "$$\n",
    "\\boldsymbol{\\epsilon} = [\\epsilon_1, \\ldots, \\epsilon_N]^\\top\n",
    "\\quad\\textrm{and}\\quad\n",
    "\\nabla_{\\mathbf{w}} L = \\left[\\frac{\\partial L}{\\partial w_1}, \\ldots, \\frac{\\partial L}{\\partial w_N}\\right]^\\top,\n",
    "$$\n",
    "\n",
    "we obtain the multivariable analogue of the linear approximation,\n",
    "\n",
    "$$L(\\mathbf{w} + \\boldsymbol{\\epsilon}) \\approx L(\\mathbf{w}) + \\boldsymbol{\\epsilon}\\cdot \\nabla_{\\mathbf{w}} L(\\mathbf{w}).$$\n",
    "\n",
    "The vector $\\nabla_{\\mathbf{w}} L$ is the *gradient* of $L$. Equation\n",
    "the equation has exactly the shape of the one-dimensional\n",
    "$f(x+\\epsilon) \\approx f(x) + \\epsilon f'(x)$, with the scalar derivative\n",
    "replaced by the gradient and ordinary multiplication replaced by a dot product.\n",
    "The gradient *is* the derivative in many dimensions: it is the unique vector\n",
    "whose dot product with a perturbation gives the first-order change in $L$. We\n",
    "treat $\\nabla_{\\mathbf{w}} L$ as a column vector throughout; the layout\n",
    "conventions that make this choice precise are settled in\n",
    "that section.\n",
    "\n",
    "The coordinate-at-a-time argument tacitly assumed the partials behave well\n",
    "*jointly*. The definition keeps the two ideas separate: $L$ is called\n",
    "*differentiable* at $\\mathbf{w}$ if the linear approximation\n",
    "the equation holds with an error vanishing faster than\n",
    "$\\|\\boldsymbol{\\epsilon}\\|$. A sufficient condition, and the one we rely on in\n",
    "practice, is that the partials exist and are *continuous* near $\\mathbf{w}$.\n",
    "Existence of the $N$ partials alone is not enough: $f(x, y) = 2xy/(x^2+y^2)$ with\n",
    "$f(0,0) = 0$ has both partials equal to zero at the origin, yet equals $1$\n",
    "everywhere on the diagonal $x = y \\neq 0$, so no linear approximation can hold\n",
    "there. The losses in this book are built from pieces smooth enough that this\n",
    "hypothesis costs nothing.\n",
    "\n",
    "### Directional Derivatives\n",
    "\n",
    "Reading the equation for a perturbation $\\boldsymbol{\\epsilon} =\n",
    "h\\,\\mathbf{u}$ of size $h$ along a unit direction $\\mathbf{u}$ shows what the\n",
    "gradient says about *any* direction at once:\n",
    "\n",
    "$$\n",
    "\\frac{L(\\mathbf{w} + h\\,\\mathbf{u}) - L(\\mathbf{w})}{h} \\;\\xrightarrow{\\;h\\to 0\\;}\\; \\mathbf{u}\\cdot\\nabla_{\\mathbf{w}} L(\\mathbf{w}).\n",
    "$$\n",
    "\n",
    "The rate of change of $L$ as we move along $\\mathbf{u}$, the *directional\n",
    "derivative*, is the projection of the gradient onto $\\mathbf{u}$. The single\n",
    "vector $\\nabla_{\\mathbf{w}} L$ thus encodes the slope in every direction\n",
    "simultaneously. The next section turns this one identity into the geometry of\n",
    "gradient descent.\n",
    "\n",
    "First, let us check that the equation really does approximate $L$."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "multivariable-calculus-imports"
   },
   "source": [
    "%matplotlib inline\n",
    "from d2l import jax as d2l\n",
    "import jax\n",
    "from jax import numpy as jnp\n",
    "import math"
   ],
   "execution_count": 1,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-multivariable-calculus-md-2 fw=all -->\n",
    "\n",
    "Take\n",
    "\n",
    "$$\n",
    "f(x, y) = \\log(e^x + e^y), \\qquad \\nabla f (x, y) = \\left[\\frac{e^x}{e^x+e^y}, \\frac{e^y}{e^x+e^y}\\right]^\\top.\n",
    "$$\n",
    "\n",
    "At the point $(0, \\log 2)$ we have $f = \\log 3$ and $\\nabla f = [\\tfrac13, \\tfrac23]^\\top$,\n",
    "so the equation predicts\n",
    "$f(\\epsilon_1, \\log 2 + \\epsilon_2) \\approx \\log 3 + \\tfrac13\\epsilon_1 + \\tfrac23\\epsilon_2$.\n",
    "We compare this against the true value for a small step. The check is plain\n",
    "scalar arithmetic."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "multivariable-calculus-higher-dimensional-differentiation"
   },
   "source": [
    "def f(x, y):\n",
    "    return math.log(math.exp(x) + math.exp(y))\n",
    "\n",
    "def grad_f(x, y):\n",
    "    s = math.exp(x) + math.exp(y)\n",
    "    return [math.exp(x) / s, math.exp(y) / s]\n",
    "\n",
    "epsilon = [0.01, -0.03]\n",
    "x0, y0 = 0, math.log(2)\n",
    "approx = f(x0, y0) + sum(e * g for e, g in zip(epsilon, grad_f(x0, y0)))\n",
    "true_value = f(x0 + epsilon[0], y0 + epsilon[1])\n",
    "print(f'approximation: {approx:.6f}, true value: {true_value:.6f}')"
   ],
   "execution_count": 2,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "approximation: 1.081946, true value: 1.082124\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-multivariable-calculus-md-3 fw=all -->\n",
    "\n",
    "The two agree to about three decimal places, with a gap of $1.8\\times10^{-4}$.\n",
    "The gap is not noise, and its size is itself a lesson: a first-order model\n",
    "discards terms of order $\\|\\boldsymbol{\\epsilon}\\|^2$, and here\n",
    "$\\|\\boldsymbol{\\epsilon}\\|^2 = 10^{-3}$: shrink the step tenfold and the gap\n",
    "shrinks a hundredfold. The discarded term has a name and a formula (the Hessian\n",
    "quadratic $\\tfrac12\\boldsymbol{\\epsilon}^\\top\\mathbf{H}f\\,\\boldsymbol{\\epsilon}$),\n",
    "which we develop at the end of this section.\n",
    "\n",
    "The same example models a workflow we will use constantly: whenever we derive a\n",
    "gradient by hand, we check it against automatic differentiation. Here\n",
    "autograd should reproduce $\\nabla f(0, \\log 2) = [\\tfrac13, \\tfrac23]^\\top$."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "mdl-multivariable-calculus-directional-derivatives-1"
   },
   "source": [
    "# Check the hand-derived gradient at (0, log 2): [1/3, 2/3]\n",
    "grad = jax.grad(jax.scipy.special.logsumexp)(jnp.array([0.0, math.log(2.0)]))\n",
    "print(f'autograd gradient: {grad}')"
   ],
   "execution_count": 3,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "autograd gradient: [0.33333334 0.6666667 ]\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-multivariable-calculus-md-4 fw=all -->\n",
    "\n",
    "Up to display precision, the printout is our hand-computed\n",
    "$[\\tfrac13, \\tfrac23]^\\top$.\n",
    "\n",
    "## The Geometry of Gradients\n",
    "\n",
    "### Steepest Descent\n",
    "\n",
    "Equation the equation tells us how $L$ changes in *any* direction,\n",
    "so we can ask which direction makes it decrease fastest. This is the geometric\n",
    "content of gradient descent, first introduced in that section:\n",
    "\n",
    "1. Start from some initial parameters $\\mathbf{w}$.\n",
    "2. Find the unit direction $\\mathbf{v}$ along which $L$ decreases most rapidly.\n",
    "3. Take a small step that way: $\\mathbf{w} \\leftarrow \\mathbf{w} + \\eta\\mathbf{v}$.\n",
    "4. Repeat.\n",
    "\n",
    "Everything hinges on step 2. Write the gradient's effect on a unit direction\n",
    "$\\mathbf{v}$ using the geometric form of the dot product from\n",
    "that section,\n",
    "\n",
    "$$\n",
    "L(\\mathbf{w} + \\mathbf{v}) - L(\\mathbf{w}) \\approx \\mathbf{v}\\cdot \\nabla_{\\mathbf{w}} L(\\mathbf{w}) = \\|\\nabla_{\\mathbf{w}} L(\\mathbf{w})\\|\\cos(\\theta),\n",
    "$$\n",
    "\n",
    "where $\\theta$ is the angle between $\\mathbf{v}$ and the gradient. The direction\n",
    "enters only through $\\cos\\theta$.\n",
    "\n",
    "**Proposition (steepest ascent and descent).** *At any point where\n",
    "$\\nabla L \\neq \\mathbf{0}$, among all unit vectors $\\mathbf{v}$ the directional\n",
    "derivative $\\mathbf{v}\\cdot\\nabla L$ is largest when $\\mathbf{v}$ points along\n",
    "$+\\nabla L$ and smallest when it points along $-\\nabla L$. Thus $+\\nabla L$ is\n",
    "the direction of steepest ascent and $-\\nabla L$ the direction of steepest\n",
    "descent.*\n",
    "\n",
    "**Proof.** By Cauchy–Schwarz (the equation) applied to the\n",
    "unit vector $\\mathbf{v}$,\n",
    "\n",
    "$$\n",
    "-\\|\\nabla L\\| \\;\\le\\; \\mathbf{v}\\cdot\\nabla L \\;\\le\\; \\|\\nabla L\\|,\n",
    "$$\n",
    "\n",
    "and the Cauchy–Schwarz equality criterion (equality holds exactly for\n",
    "collinear vectors) says each bound is attained exactly\n",
    "when $\\mathbf{v}$ is collinear with $\\nabla L$. The upper bound $+\\|\\nabla L\\|$\n",
    "is reached by $\\mathbf{v} = \\nabla L/\\|\\nabla L\\|$ and the lower bound\n",
    "$-\\|\\nabla L\\|$ by $\\mathbf{v} = -\\nabla L/\\|\\nabla L\\|$. $\\blacksquare$\n",
    "\n",
    "In the $\\cos\\theta$ picture this is simply $\\theta = 0$ versus $\\theta = \\pi$.\n",
    "Steepest descent therefore steps along $-\\nabla_{\\mathbf{w}} L$, and\n",
    "the informal recipe becomes the gradient-descent update\n",
    "\n",
    "$$\n",
    "\\mathbf{w} \\leftarrow \\mathbf{w} - \\eta\\,\\nabla_{\\mathbf{w}} L(\\mathbf{w}).\n",
    "$$\n",
    "\n",
    "Every optimizer in this book, from momentum through RMSProp to Adam\n",
    "(that section), modifies *how* the step along the gradient is\n",
    "computed, but they all inherit this core idea: read the gradient, move against\n",
    "it.\n",
    "\n",
    "### Gradients and Level Sets\n",
    "\n",
    "The same expression $L(\\mathbf{w} + \\mathbf{v}) - L(\\mathbf{w}) \\approx\n",
    "\\|\\nabla L\\|\\cos\\theta$ also reveals what the gradient is *geometrically*, not\n",
    "just which way to step. Consider moving along a *level set*, the set of points\n",
    "where $L$ keeps a fixed value $c$. To first order, $L$ does not change along\n",
    "such a direction, so the directional derivative vanishes.\n",
    "\n",
    "**Proposition (gradients are normal to level sets).** *At any point, $\\nabla L$\n",
    "is orthogonal to every direction tangent to the level set\n",
    "$\\{\\mathbf{x} : L(\\mathbf{x}) = c\\}$ through that point.*\n",
    "\n",
    "**Proof.** A direction $\\mathbf{v}$ is *tangent* to the level set at\n",
    "$\\mathbf{x}$ if $\\mathbf{v} = \\boldsymbol{\\gamma}'(0)$ for some differentiable\n",
    "curve $\\boldsymbol{\\gamma}(t)$ lying in the level set with\n",
    "$\\boldsymbol{\\gamma}(0) = \\mathbf{x}$. Along such a curve\n",
    "$L(\\boldsymbol{\\gamma}(t)) = c$ for all $t$, so the derivative of\n",
    "$t \\mapsto L(\\boldsymbol{\\gamma}(t))$ at $t = 0$ vanishes. To first order\n",
    "$\\boldsymbol{\\gamma}(t) = \\mathbf{x} + t\\mathbf{v} + o(t)$, so by\n",
    "the equation that derivative is $\\mathbf{v}\\cdot\\nabla L(\\mathbf{x})$.\n",
    "Hence $\\mathbf{v}\\cdot\\nabla L = 0$; by the definition of orthogonality from\n",
    "that section, $\\mathbf{v}\\perp\\nabla L$.\n",
    "$\\blacksquare$\n",
    "\n",
    "So on a contour map the gradient is the arrow crossing the contours at right\n",
    "angles, pointing toward higher ground, and it is longest where the contours\n",
    "bunch together, exactly where $L$ changes fastest, as drawn in\n",
    "the figure. Gradient descent slides *downhill across\n",
    "the contours*, always perpendicular to them.\n",
    "\n",
    "![Contours of a scalar field $L$ with its gradient $\\nabla L$ drawn at several points: each arrow crosses the contours at a right angle, points toward higher values, and is longest where the contours bunch together, where $L$ changes fastest.](../img/mdl-cal-gradient-field.svg)\n",
    "\n",
    "### Tangent Planes and Linearization\n",
    "\n",
    "The level-set picture lives in the *base plane*, where the gradient is the arrow\n",
    "normal to the contours. There is a companion picture one dimension up, on the\n",
    "*graph* $z = f(\\mathbf{x})$ itself. Reading the equation as an\n",
    "equation for the height $z$ rather than as an approximation gives the\n",
    "*linearization* of $f$ at $\\mathbf{x}_0$,\n",
    "\n",
    "$$\n",
    "z = f(\\mathbf{x}_0) + \\nabla f(\\mathbf{x}_0)\\cdot(\\mathbf{x}-\\mathbf{x}_0),\n",
    "$$\n",
    "\n",
    "a linear function of $\\mathbf{x}$ whose graph is a plane (a hyperplane in higher\n",
    "dimensions). It passes through the point $(\\mathbf{x}_0, f(\\mathbf{x}_0))$ and\n",
    "matches every first-order slope of $f$ there, so it is the *tangent plane* to the\n",
    "surface: the two-dimensional analogue of the tangent line, and the surface's\n",
    "best linear approximation near $\\mathbf{x}_0$.\n",
    "\n",
    "Rewrite\n",
    "the equation as $\\nabla f(\\mathbf{x}_0)\\cdot(\\mathbf{x}-\\mathbf{x}_0) - (z - f(\\mathbf{x}_0)) = 0$:\n",
    "this says the augmented vector $[\\nabla f(\\mathbf{x}_0),\\, -1]^\\top$ is normal,\n",
    "*in graph space*, to the tangent plane; the gradient is normal to the surface\n",
    "once we account for the height direction. Drop the height coordinate, projecting\n",
    "that normal straight down onto the base plane, and we recover $\\nabla f$ crossing\n",
    "the level curves at right angles. the figure shows both at\n",
    "once: the tangent plane riding the surface, and the gradient's shadow meeting the\n",
    "contours square on.\n",
    "\n",
    "![A surface $z = f(\\mathbf{x})$ with its tangent plane at a point, and the gradient $\\nabla f$ projected onto the base plane, where it crosses the level curves of $f$ at right angles. The tangent plane is the graph-space view of the linearization; the perpendicular crossing is the base-plane view, two faces of the same first-order approximation.](../img/mdl-cal-tangent-plane.svg)\n",
    "\n",
    "### Critical Points and the First-Order Test\n",
    "\n",
    "Throughout this book we minimize losses numerically, because the functions that\n",
    "arise in deep learning are far too complex to minimize in closed form. But the\n",
    "geometry above gives a cheap, exact *necessary* condition that every minimum\n",
    "must satisfy.\n",
    "\n",
    "Suppose someone hands us a point $\\mathbf{x}_0$ and claims it minimizes $L$. Is\n",
    "the claim even plausible? Read the equation at $\\mathbf{x}_0$: if\n",
    "$\\nabla L(\\mathbf{x}_0) \\neq \\mathbf{0}$, then stepping along\n",
    "$-\\nabla L(\\mathbf{x}_0)$ strictly decreases $L$, so $\\mathbf{x}_0$ cannot be a\n",
    "minimum. Contrapositively, **a minimum forces $\\nabla L(\\mathbf{x}_0) =\n",
    "\\mathbf{0}$.** Points where the gradient vanishes are called *critical points*.\n",
    "\n",
    "This is occasionally enough to optimize by hand. For example,\n",
    "\n",
    "$$\n",
    "f(x) = 3x^4 - 4x^3 - 12x^2, \\qquad f'(x) = 12x(x-2)(x+1),\n",
    "$$\n",
    "\n",
    "has critical points $x = -1, 0, 2$ with values $-5, 0, -32$, so the minimum is\n",
    "at $x = 2$, as the plot confirms."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "multivariable-calculus-a-note-on-mathematical-optimization"
   },
   "source": [
    "import numpy as onp\n",
    "x = onp.arange(-2, 3, 0.01)\n",
    "f = (3 * x**4) - (4 * x**3) - (12 * x**2)\n",
    "\n",
    "d2l.plot(x, f, 'x', 'f(x)')"
   ],
   "execution_count": 4,
   "outputs": [
    {
     "output_type": "display_data",
     "data": {
      "image/svg+xml": "<?xml version=\"1.0\" encoding=\"utf-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n  \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<svg xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"251.482813pt\" height=\"183.35625pt\" viewBox=\"0 0 251.482813 183.35625\" xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\">\n <metadata>\n  <rdf:RDF xmlns:dc=\"http://purl.org/dc/elements/1.1/\" xmlns:cc=\"http://creativecommons.org/ns#\" xmlns:rdf=\"http://www.w3.org/1999/02/22-rdf-syntax-ns#\">\n   <cc:Work>\n    <dc:type rdf:resource=\"http://purl.org/dc/dcmitype/StillImage\"/>\n    <dc:date>2026-07-19T13:53:18.842197</dc:date>\n    <dc:format>image/svg+xml</dc:format>\n    <dc:creator>\n     <cc:Agent>\n      <dc:title>Matplotlib v3.10.8, https://matplotlib.org/</dc:title>\n     </cc:Agent>\n    </dc:creator>\n   </cc:Work>\n  </rdf:RDF>\n </metadata>\n <defs>\n  <style type=\"text/css\">*{stroke-linejoin: round; stroke-linecap: butt}</style>\n </defs>\n <g id=\"figure_1\">\n  <g id=\"patch_1\">\n   <path d=\"M -0 183.35625 \nL 251.482813 183.35625 \nL 251.482813 0 \nL -0 0 \nz\n\" style=\"fill: #ffffff\"/>\n  </g>\n  <g id=\"axes_1\">\n   <g id=\"patch_2\">\n    <path d=\"M 48.982813 145.8 \nL 244.282813 145.8 \nL 244.282813 7.2 \nL 48.982813 7.2 \nz\n\" style=\"fill: #ffffff\"/>\n   </g>\n   <g id=\"matplotlib.axis_1\">\n    <g id=\"xtick_1\">\n     <g id=\"line2d_1\">\n      <path d=\"M 57.860085 145.8 \nL 57.860085 7.2 \n\" clip-path=\"url(#pae75c5aca7)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_2\">\n      <defs>\n       <path id=\"mc4c2ad168b\" d=\"M 0 0 \nL 0 3.5 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#mc4c2ad168b\" x=\"57.860085\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_1\">\n      <!-- −2 -->\n      <g transform=\"translate(50.488991 160.398438) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-2212\" d=\"M 678 2272 \nL 4684 2272 \nL 4684 1741 \nL 678 1741 \nL 678 2272 \nz\n\" transform=\"scale(0.015625)\"/>\n        <path id=\"DejaVuSans-32\" d=\"M 1228 531 \nL 3431 531 \nL 3431 0 \nL 469 0 \nL 469 531 \nQ 828 903 1448 1529 \nQ 2069 2156 2228 2338 \nQ 2531 2678 2651 2914 \nQ 2772 3150 2772 3378 \nQ 2772 3750 2511 3984 \nQ 2250 4219 1831 4219 \nQ 1534 4219 1204 4116 \nQ 875 4013 500 3803 \nL 500 4441 \nQ 881 4594 1212 4672 \nQ 1544 4750 1819 4750 \nQ 2544 4750 2975 4387 \nQ 3406 4025 3406 3419 \nQ 3406 3131 3298 2873 \nQ 3191 2616 2906 2266 \nQ 2828 2175 2409 1742 \nQ 1991 1309 1228 531 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-2212\"/>\n       <use xlink:href=\"#DejaVuSans-32\" transform=\"translate(83.789062 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_2\">\n     <g id=\"line2d_3\">\n      <path d=\"M 93.440337 145.8 \nL 93.440337 7.2 \n\" clip-path=\"url(#pae75c5aca7)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_4\">\n      <g>\n       <use xlink:href=\"#mc4c2ad168b\" x=\"93.440337\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_2\">\n      <!-- −1 -->\n      <g transform=\"translate(86.069243 160.398438) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-31\" d=\"M 794 531 \nL 1825 531 \nL 1825 4091 \nL 703 3866 \nL 703 4441 \nL 1819 4666 \nL 2450 4666 \nL 2450 531 \nL 3481 531 \nL 3481 0 \nL 794 0 \nL 794 531 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-2212\"/>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(83.789062 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_3\">\n     <g id=\"line2d_5\">\n      <path d=\"M 129.020588 145.8 \nL 129.020588 7.2 \n\" clip-path=\"url(#pae75c5aca7)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_6\">\n      <g>\n       <use xlink:href=\"#mc4c2ad168b\" x=\"129.020588\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_3\">\n      <!-- 0 -->\n      <g transform=\"translate(125.839338 160.398438) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-30\" d=\"M 2034 4250 \nQ 1547 4250 1301 3770 \nQ 1056 3291 1056 2328 \nQ 1056 1369 1301 889 \nQ 1547 409 2034 409 \nQ 2525 409 2770 889 \nQ 3016 1369 3016 2328 \nQ 3016 3291 2770 3770 \nQ 2525 4250 2034 4250 \nz\nM 2034 4750 \nQ 2819 4750 3233 4129 \nQ 3647 3509 3647 2328 \nQ 3647 1150 3233 529 \nQ 2819 -91 2034 -91 \nQ 1250 -91 836 529 \nQ 422 1150 422 2328 \nQ 422 3509 836 4129 \nQ 1250 4750 2034 4750 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-30\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_4\">\n     <g id=\"line2d_7\">\n      <path d=\"M 164.600839 145.8 \nL 164.600839 7.2 \n\" clip-path=\"url(#pae75c5aca7)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_8\">\n      <g>\n       <use xlink:href=\"#mc4c2ad168b\" x=\"164.600839\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_4\">\n      <!-- 1 -->\n      <g transform=\"translate(161.419589 160.398438) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-31\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_5\">\n     <g id=\"line2d_9\">\n      <path d=\"M 200.181091 145.8 \nL 200.181091 7.2 \n\" clip-path=\"url(#pae75c5aca7)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_10\">\n      <g>\n       <use xlink:href=\"#mc4c2ad168b\" x=\"200.181091\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_5\">\n      <!-- 2 -->\n      <g transform=\"translate(196.999841 160.398438) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-32\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_6\">\n     <g id=\"line2d_11\">\n      <path d=\"M 235.761342 145.8 \nL 235.761342 7.2 \n\" clip-path=\"url(#pae75c5aca7)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_12\">\n      <g>\n       <use xlink:href=\"#mc4c2ad168b\" x=\"235.761342\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_6\">\n      <!-- 3 -->\n      <g transform=\"translate(232.580092 160.398438) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-33\" d=\"M 2597 2516 \nQ 3050 2419 3304 2112 \nQ 3559 1806 3559 1356 \nQ 3559 666 3084 287 \nQ 2609 -91 1734 -91 \nQ 1441 -91 1130 -33 \nQ 819 25 488 141 \nL 488 750 \nQ 750 597 1062 519 \nQ 1375 441 1716 441 \nQ 2309 441 2620 675 \nQ 2931 909 2931 1356 \nQ 2931 1769 2642 2001 \nQ 2353 2234 1838 2234 \nL 1294 2234 \nL 1294 2753 \nL 1863 2753 \nQ 2328 2753 2575 2939 \nQ 2822 3125 2822 3475 \nQ 2822 3834 2567 4026 \nQ 2313 4219 1838 4219 \nQ 1578 4219 1281 4162 \nQ 984 4106 628 3988 \nL 628 4550 \nQ 988 4650 1302 4700 \nQ 1616 4750 1894 4750 \nQ 2613 4750 3031 4423 \nQ 3450 4097 3450 3541 \nQ 3450 3153 3228 2886 \nQ 3006 2619 2597 2516 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-33\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_7\">\n     <!-- x -->\n     <g transform=\"translate(143.673438 174.076563) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-78\" d=\"M 3513 3500 \nL 2247 1797 \nL 3578 0 \nL 2900 0 \nL 1881 1375 \nL 863 0 \nL 184 0 \nL 1544 1831 \nL 300 3500 \nL 978 3500 \nL 1906 2253 \nL 2834 3500 \nL 3513 3500 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-78\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"matplotlib.axis_2\">\n    <g id=\"ytick_1\">\n     <g id=\"line2d_13\">\n      <path d=\"M 48.982813 115.875 \nL 244.282813 115.875 \n\" clip-path=\"url(#pae75c5aca7)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_14\">\n      <defs>\n       <path id=\"ma446b69a01\" d=\"M 0 0 \nL -3.5 0 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#ma446b69a01\" x=\"48.982813\" y=\"115.875\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_8\">\n      <!-- −20 -->\n      <g transform=\"translate(20.878125 119.674219) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-2212\"/>\n       <use xlink:href=\"#DejaVuSans-32\" transform=\"translate(83.789062 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(147.412109 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_2\">\n     <g id=\"line2d_15\">\n      <path d=\"M 48.982813 76.5 \nL 244.282813 76.5 \n\" clip-path=\"url(#pae75c5aca7)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_16\">\n      <g>\n       <use xlink:href=\"#ma446b69a01\" x=\"48.982813\" y=\"76.5\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_9\">\n      <!-- 0 -->\n      <g transform=\"translate(35.620313 80.299219) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-30\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_3\">\n     <g id=\"line2d_17\">\n      <path d=\"M 48.982813 37.125 \nL 244.282813 37.125 \n\" clip-path=\"url(#pae75c5aca7)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_18\">\n      <g>\n       <use xlink:href=\"#ma446b69a01\" x=\"48.982813\" y=\"37.125\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_10\">\n      <!-- 20 -->\n      <g transform=\"translate(29.257813 40.924219) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-32\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_11\">\n     <!-- f(x) -->\n     <g transform=\"translate(14.798438 85.121094) rotate(-90) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-66\" d=\"M 2375 4863 \nL 2375 4384 \nL 1825 4384 \nQ 1516 4384 1395 4259 \nQ 1275 4134 1275 3809 \nL 1275 3500 \nL 2222 3500 \nL 2222 3053 \nL 1275 3053 \nL 1275 0 \nL 697 0 \nL 697 3053 \nL 147 3053 \nL 147 3500 \nL 697 3500 \nL 697 3744 \nQ 697 4328 969 4595 \nQ 1241 4863 1831 4863 \nL 2375 4863 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-28\" d=\"M 1984 4856 \nQ 1566 4138 1362 3434 \nQ 1159 2731 1159 2009 \nQ 1159 1288 1364 580 \nQ 1569 -128 1984 -844 \nL 1484 -844 \nQ 1016 -109 783 600 \nQ 550 1309 550 2009 \nQ 550 2706 781 3412 \nQ 1013 4119 1484 4856 \nL 1984 4856 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-29\" d=\"M 513 4856 \nL 1013 4856 \nQ 1481 4119 1714 3412 \nQ 1947 2706 1947 2009 \nQ 1947 1309 1714 600 \nQ 1481 -109 1013 -844 \nL 513 -844 \nQ 928 -128 1133 580 \nQ 1338 1288 1338 2009 \nQ 1338 2731 1133 3434 \nQ 928 4138 513 4856 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-66\"/>\n      <use xlink:href=\"#DejaVuSans-28\" transform=\"translate(35.205078 0)\"/>\n      <use xlink:href=\"#DejaVuSans-78\" transform=\"translate(74.21875 0)\"/>\n      <use xlink:href=\"#DejaVuSans-29\" transform=\"translate(133.398438 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"line2d_19\">\n    <path d=\"M 57.860085 13.5 \nL 59.9949 24.25648 \nL 62.129715 33.892631 \nL 64.26453 42.477139 \nL 66.399346 50.076852 \nL 68.534161 56.756784 \nL 70.313173 61.666416 \nL 72.092186 66.0168 \nL 73.871198 69.842635 \nL 75.650211 73.177734 \nL 77.429224 76.055026 \nL 79.208236 78.50655 \nL 80.987249 80.563463 \nL 82.766261 82.256034 \nL 84.545274 83.613647 \nL 86.324286 84.6648 \nL 88.103299 85.437104 \nL 89.882311 85.957284 \nL 91.661324 86.251182 \nL 93.440337 86.34375 \nL 95.575152 86.222902 \nL 97.709967 85.886657 \nL 100.200584 85.272818 \nL 103.047005 84.348983 \nL 106.960832 82.83189 \nL 116.923303 78.842604 \nL 120.125525 77.830444 \nL 122.971945 77.13914 \nL 125.818365 76.685234 \nL 128.308983 76.509386 \nL 130.799601 76.56001 \nL 133.290218 76.852583 \nL 135.780836 77.39918 \nL 138.271453 78.208471 \nL 140.762071 79.285723 \nL 143.252689 80.6328 \nL 145.743306 82.248162 \nL 148.233924 84.126867 \nL 151.080344 86.585556 \nL 153.926764 89.359284 \nL 157.128987 92.826555 \nL 160.331209 96.619841 \nL 164.245037 101.622447 \nL 169.226272 108.399592 \nL 180.611953 124.070869 \nL 184.169978 128.493666 \nL 187.016398 131.680982 \nL 189.507015 134.136534 \nL 191.641831 135.942324 \nL 193.420843 137.203789 \nL 195.199856 138.216626 \nL 196.978868 138.954229 \nL 198.402078 139.327697 \nL 199.825288 139.492952 \nL 201.248498 139.435145 \nL 202.671708 139.139065 \nL 204.094919 138.58914 \nL 205.518129 137.769432 \nL 206.941339 136.663642 \nL 208.364549 135.255109 \nL 209.787759 133.526806 \nL 211.210969 131.461346 \nL 212.634179 129.040979 \nL 214.057389 126.247589 \nL 215.836401 122.203108 \nL 217.615414 117.51 \nL 219.394427 112.130493 \nL 221.173439 106.025933 \nL 222.952452 99.156776 \nL 224.731464 91.482594 \nL 226.866279 81.15271 \nL 229.001095 69.530976 \nL 231.13591 56.54248 \nL 233.270725 42.110473 \nL 235.40554 26.156369 \nL 235.40554 26.156369 \n\" clip-path=\"url(#pae75c5aca7)\" style=\"fill: none; stroke: #1f77b4; stroke-width: 1.5; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_3\">\n    <path d=\"M 48.982813 145.8 \nL 48.982813 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_4\">\n    <path d=\"M 244.282813 145.8 \nL 244.282813 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_5\">\n    <path d=\"M 48.982813 145.8 \nL 244.282813 145.8 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_6\">\n    <path d=\"M 48.982813 7.2 \nL 244.282813 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n  </g>\n </g>\n <defs>\n  <clipPath id=\"pae75c5aca7\">\n   <rect x=\"48.982813\" y=\"7.2\" width=\"195.3\" height=\"138.6\"/>\n  </clipPath>\n </defs>\n</svg>\n"
     },
     "metadata": {}
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-multivariable-calculus-md-5 fw=all -->\n",
    "\n",
    "But not every critical point is an extremum: $x = 0$ above is a local maximum,\n",
    "and in higher dimensions a critical point can be a saddle. Telling these apart\n",
    "needs *second*-order information, the Hessian we develop below.\n",
    "\n",
    "### Optimizing on a Constraint\n",
    "\n",
    "The first-order test answers \"where can an unconstrained minimum be?\" One more\n",
    "turn of the same geometry answers the constrained question that pervades machine\n",
    "learning: minimize a loss *subject to* keeping some quantity fixed, say\n",
    "$g(\\mathbf{x}) = c$. Now we are no longer free to step in any direction: the\n",
    "admissible moves are exactly those tangent to the constraint surface\n",
    "$\\{g = c\\}$. At a constrained optimum $\\mathbf{x}^\\star$, *no* admissible\n",
    "direction can lower $f$ to first order: otherwise we would slide along the\n",
    "constraint and improve. By the equation that means\n",
    "$\\nabla f(\\mathbf{x}^\\star)$ has zero component along every direction tangent to\n",
    "$\\{g = c\\}$; it is orthogonal to that surface. But we proved above that\n",
    "$\\nabla g$ is *also* orthogonal to $\\{g = c\\}$. One hypothesis makes the\n",
    "geometry rigorous: provided $\\nabla g(\\mathbf{x}^\\star) \\neq \\mathbf{0}$, the\n",
    "standard *constraint qualification*, the implicit function theorem (stated in\n",
    "that section; see [@Rudin.1976]) guarantees that\n",
    "$\\{g = c\\}$ really is a smooth surface of codimension one near\n",
    "$\\mathbf{x}^\\star$ (one equation removes one degree of freedom, leaving an\n",
    "$(n{-}1)$-dimensional surface) with a single normal direction; it also supplies\n",
    "the fact, used tacitly above, that every tangent direction is realized by a\n",
    "curve lying in $\\{g = c\\}$, so \"sliding along the constraint\" is a legitimate\n",
    "move. Two vectors normal to the same surface must be parallel, so at the\n",
    "constrained optimum\n",
    "\n",
    "$$\n",
    "\\nabla f(\\mathbf{x}^\\star) = \\lambda\\,\\nabla g(\\mathbf{x}^\\star)\n",
    "$$\n",
    "\n",
    "for some scalar $\\lambda$, the *Lagrange multiplier*. This single picture, the\n",
    "contours of $f$ kissing the constraint surface where their gradients align\n",
    "(the figure), is\n",
    "the first-order condition for constrained optimization, the seed of the KKT\n",
    "conditions and of duality. We meet it again in full force in\n",
    "that section.\n",
    "\n",
    "![Lagrange multipliers as tangency. At the constrained optimum the level set of $f$ is tangent to the constraint curve $g = c$ and the two gradients align, $\\nabla f = \\lambda \\nabla g$. At a non-optimal feasible point the gradients disagree, so $\\nabla f$ keeps a component along the constraint and sliding along it still improves $f$.](../img/mdl-cal-lagrange-tangency.svg)\n",
    "\n",
    "## The Multivariate Chain Rule\n",
    "\n",
    "Neural networks are deep compositions of simple functions, so computing\n",
    "gradients means differentiating compositions. Consider four inputs $w, x, y, z$\n",
    "flowing through intermediate quantities to a scalar output:\n",
    "\n",
    "$$\\begin{aligned}f(u, v) & = (u+v)^{2} \\\\u(a, b) & = (a+b)^{2}, \\qquad v(a, b) = (a-b)^{2}, \\\\a(w, x, y, z) & = (w+x+y+z)^{2}, \\qquad b(w, x, y, z) = (w+x-y-z)^2.\\end{aligned}$$\n",
    "\n",
    "The dependencies form a graph (the figure): each node is a value,\n",
    "each edge a direct functional dependence.\n",
    "\n",
    "![The function relations of the equation, drawn as a graph where nodes are values and edges show direct functional dependence.](../img/mdl-cal-chain-net1.svg)\n",
    "\n",
    "We *could* substitute everything and differentiate the resulting monster\n",
    "directly, but $\\frac{\\partial f}{\\partial w}$ alone expands into a page of\n",
    "repeated subexpressions, and $\\frac{\\partial f}{\\partial x}$ would repeat most\n",
    "of them again. That waste is precisely what the chain rule organizes away.\n",
    "\n",
    "### The Rule as a Sum Over Paths\n",
    "\n",
    "Take the simplest composite step, $f(u(a,b), v(a,b))$, and perturb $a$ by a\n",
    "small $\\epsilon$. Each intermediate moves by its partial,\n",
    "$u \\to u + \\epsilon\\frac{\\partial u}{\\partial a}$ and\n",
    "$v \\to v + \\epsilon\\frac{\\partial v}{\\partial a}$, and feeding those into the\n",
    "first-order expansion of $f$ gives\n",
    "\n",
    "$$\n",
    "f\\!\\left(u + \\epsilon\\tfrac{\\partial u}{\\partial a},\\, v + \\epsilon\\tfrac{\\partial v}{\\partial a}\\right)\n",
    "\\approx f(u, v) + \\epsilon\\left[\\frac{\\partial f}{\\partial u}\\frac{\\partial u}{\\partial a} + \\frac{\\partial f}{\\partial v}\\frac{\\partial v}{\\partial a}\\right].\n",
    "$$\n",
    "\n",
    "Reading off the coefficient of $\\epsilon$ gives the multivariate chain rule,\n",
    "\n",
    "$$\n",
    "\\frac{\\partial f}{\\partial a} = \\frac{\\partial f}{\\partial u}\\frac{\\partial u}{\\partial a} + \\frac{\\partial f}{\\partial v}\\frac{\\partial v}{\\partial a}.\n",
    "$$\n",
    "\n",
    "In words, there are two *pathways* by which $a$\n",
    "influences $f$: $a \\to u \\to f$ and $a \\to v \\to f$. Each path contributes the\n",
    "*product* of the derivatives along its edges, and the total derivative is the\n",
    "*sum* over paths. This is the whole rule.\n",
    "\n",
    "In general, to differentiate the output with respect to an input we **sum, over\n",
    "every directed path from that input to the output, the product of the edge\n",
    "derivatives along the path.**\n",
    "\n",
    "To see the rule at work on a graph that is not a tree, consider a\n",
    "*different* composition (its own dependency graph, unrelated to\n",
    "the equation) in which one intermediate feeds the output both\n",
    "directly and through a later node:\n",
    "\n",
    "$$\\begin{aligned}u(x, y) & = x + y, \\qquad v(x, y) = x - y, \\\\a(u) & = u^2, \\qquad b(v) = v^2, \\\\f(a, u, b) & = a + u + b.\\end{aligned}$$\n",
    "\n",
    "These relations are exactly the edges drawn in the figure:\n",
    "$u$ and $v$ each depend on the input $y$; $a$ depends on $u$ and $b$ on $v$; and\n",
    "the output $f$ depends on $a$, on $b$, and *also directly on $u$*: the skip-like\n",
    "edge that gives the middle path below. Tracing every directed route from $y$ to\n",
    "$f$ (namely $y\\to u\\to a\\to f$, the direct $y\\to u\\to f$, and\n",
    "$y\\to v\\to b\\to f$), the rule gives\n",
    "\n",
    "$$\n",
    "\\frac{\\partial f}{\\partial y} = \\frac{\\partial f}{\\partial a} \\frac{\\partial a}{\\partial u} \\frac{\\partial u}{\\partial y} + \\frac{\\partial f}{\\partial u} \\frac{\\partial u}{\\partial y} + \\frac{\\partial f}{\\partial b} \\frac{\\partial b}{\\partial v} \\frac{\\partial v}{\\partial y}.\n",
    "$$\n",
    "\n",
    "![A second, distinct dependency graph, the equation: the input $y$ reaches the output $f$ by three directed paths ($y\\to u\\to a\\to f$, the direct skip $y\\to u\\to f$, and $y\\to v\\to b\\to f$), and the chain rule sums their contributions.](../img/mdl-cal-chain-net2.svg)\n",
    "\n",
    "Here every edge derivative is elementary\n",
    "($\\partial f/\\partial a = \\partial f/\\partial u = \\partial f/\\partial b = 1$,\n",
    "$\\partial a/\\partial u = 2u$, $\\partial u/\\partial y = 1$, and so on), so the\n",
    "sum-over-paths value is checkable by hand: it collapses to\n",
    "$2u + 1 - 2v = 2(x+y) + 1 - 2(x-y) = 1 + 4y$. This \"sum over paths\" view is\n",
    "exactly how gradients flow through a network, and\n",
    "it explains why architectural choices that open or close paths, such as the\n",
    "gates of an LSTM (that section) or the skip connections of a residual\n",
    "block (that section), shape learning by controlling that gradient flow.\n",
    "\n",
    "### The Backpropagation Algorithm\n",
    "\n",
    "Return to the equation and ask for $\\frac{\\partial f}{\\partial\n",
    "w}$. Applying the chain rule the obvious way pushes $w$ forward through the\n",
    "graph,\n",
    "\n",
    "$$\n",
    "\\frac{\\partial f}{\\partial w} = \\frac{\\partial f}{\\partial u}\\frac{\\partial u}{\\partial w} + \\frac{\\partial f}{\\partial v}\\frac{\\partial v}{\\partial w}, \\qquad\n",
    "\\frac{\\partial u}{\\partial w} = \\frac{\\partial u}{\\partial a}\\frac{\\partial a}{\\partial w}+\\frac{\\partial u}{\\partial b}\\frac{\\partial b}{\\partial w}, \\quad \\ldots\n",
    "$$\n",
    "\n",
    "and the single-step partials are all elementary,\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\frac{\\partial f}{\\partial u} = 2(u+v), & \\quad\\frac{\\partial f}{\\partial v} = 2(u+v), \\\\\n",
    "\\frac{\\partial u}{\\partial a} = 2(a+b), & \\quad\\frac{\\partial u}{\\partial b} = 2(a+b), \\\\\n",
    "\\frac{\\partial v}{\\partial a} = 2(a-b), & \\quad\\frac{\\partial v}{\\partial b} = -2(a-b), \\\\\n",
    "\\frac{\\partial a}{\\partial w} = 2(w+x+y+z), & \\quad\\frac{\\partial b}{\\partial w} = 2(w+x-y-z).\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "In code this is a tidy forward sweep through the graph."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "multivariable-calculus-the-backpropagation-algorithm-1"
   },
   "source": [
    "# Compute the value of the function from inputs to outputs\n",
    "w, x, y, z = 1, 1, -2, 1\n",
    "a, b = (w + x + y + z)**2, (w + x - y - z)**2\n",
    "u, v = (a + b)**2, (a - b)**2\n",
    "f = (u + v)**2\n",
    "print(f'f at {w}, {x}, {y}, {z} is {f}')\n",
    "\n",
    "# Compute the single step partials\n",
    "df_du, df_dv = 2*(u + v), 2*(u + v)\n",
    "du_da, du_db, dv_da, dv_db = 2*(a + b), 2*(a + b), 2*(a - b), -2*(a - b)\n",
    "da_dw, db_dw = 2*(w + x + y + z), 2*(w + x - y - z)\n",
    "\n",
    "# Compute the final result from inputs to outputs\n",
    "du_dw, dv_dw = du_da*da_dw + du_db*db_dw, dv_da*da_dw + dv_db*db_dw\n",
    "df_dw = df_du*du_dw + df_dv*dv_dw\n",
    "print(f'df/dw at {w}, {x}, {y}, {z} is {df_dw}')"
   ],
   "execution_count": 5,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "f at 1, 1, -2, 1 is 26896\ndf/dw at 1, 1, -2, 1 is 73472\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-multivariable-calculus-md-6 fw=all -->\n",
    "\n",
    "This computes one derivative, $\\frac{\\partial f}{\\partial w}$. The trouble is\n",
    "that it gives us *no head start* on $\\frac{\\partial f}{\\partial x}$: by keeping\n",
    "$\\partial w$ in every denominator, we organized the work around \"how $w$ affects\n",
    "everything.\" But in deep learning we want the opposite: how *one* loss is\n",
    "affected by *every* parameter. So we keep $\\partial f$ in every *numerator*\n",
    "instead, walking the graph from the output backward:\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\frac{\\partial f}{\\partial a} & = \\frac{\\partial f}{\\partial u}\\frac{\\partial u}{\\partial a}+\\frac{\\partial f}{\\partial v}\\frac{\\partial v}{\\partial a}, \\qquad\n",
    "\\frac{\\partial f}{\\partial b} = \\frac{\\partial f}{\\partial u}\\frac{\\partial u}{\\partial b}+\\frac{\\partial f}{\\partial v}\\frac{\\partial v}{\\partial b}, \\\\\n",
    "\\frac{\\partial f}{\\partial w} & = \\frac{\\partial f}{\\partial a}\\frac{\\partial a}{\\partial w} + \\frac{\\partial f}{\\partial b}\\frac{\\partial b}{\\partial w}, \\qquad (\\textrm{and likewise for } x, y, z).\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "Computing $\\frac{\\partial f}{\\partial u}, \\frac{\\partial f}{\\partial v}$ once,\n",
    "then $\\frac{\\partial f}{\\partial a}, \\frac{\\partial f}{\\partial b}$, then all\n",
    "four input derivatives, *reuses* every intermediate. One backward sweep yields\n",
    "the gradient with respect to all inputs at once."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "multivariable-calculus-the-backpropagation-algorithm-2"
   },
   "source": [
    "# Compute the value of the function from inputs to outputs\n",
    "w, x, y, z = 1, 1, -2, 1\n",
    "a, b = (w + x + y + z)**2, (w + x - y - z)**2\n",
    "u, v = (a + b)**2, (a - b)**2\n",
    "f = (u + v)**2\n",
    "print(f'f at {w}, {x}, {y}, {z} is {f}')\n",
    "\n",
    "# Compute the derivative using the decomposition above\n",
    "# First compute the single step partials\n",
    "df_du, df_dv = 2*(u + v), 2*(u + v)\n",
    "du_da, du_db, dv_da, dv_db = 2*(a + b), 2*(a + b), 2*(a - b), -2*(a - b)\n",
    "da_dw, db_dw = 2*(w + x + y + z), 2*(w + x - y - z)\n",
    "da_dx, db_dx = 2*(w + x + y + z), 2*(w + x - y - z)\n",
    "da_dy, db_dy = 2*(w + x + y + z), -2*(w + x - y - z)\n",
    "da_dz, db_dz = 2*(w + x + y + z), -2*(w + x - y - z)\n",
    "\n",
    "# Now compute how f changes when we change any value from output to input\n",
    "df_da, df_db = df_du*du_da + df_dv*dv_da, df_du*du_db + df_dv*dv_db\n",
    "df_dw, df_dx = df_da*da_dw + df_db*db_dw, df_da*da_dx + df_db*db_dx\n",
    "df_dy, df_dz = df_da*da_dy + df_db*db_dy, df_da*da_dz + df_db*db_dz\n",
    "\n",
    "print(f'df/dw at {w}, {x}, {y}, {z} is {df_dw}')\n",
    "print(f'df/dx at {w}, {x}, {y}, {z} is {df_dx}')\n",
    "print(f'df/dy at {w}, {x}, {y}, {z} is {df_dy}')\n",
    "print(f'df/dz at {w}, {x}, {y}, {z} is {df_dz}')"
   ],
   "execution_count": 6,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "f at 1, 1, -2, 1 is 26896\ndf/dw at 1, 1, -2, 1 is 73472\ndf/dx at 1, 1, -2, 1 is 73472\ndf/dy at 1, 1, -2, 1 is -68224\ndf/dz at 1, 1, -2, 1 is -68224\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-multivariable-calculus-md-7 fw=all -->\n",
    "\n",
    "Two sanity checks are visible in the printout. The derivatives with respect to\n",
    "$w$ and $x$ agree, as do those with respect to $y$ and $z$, as they must,\n",
    "since $f$ reaches its inputs only through the sums $w+x$ and $y+z$. And the two\n",
    "pairs differ in both magnitude and sign, so the sweep is genuinely telling the\n",
    "four paths through the graph apart.\n",
    "\n",
    "Computing derivatives *from $f$ back toward the inputs*, rather than forward from\n",
    "the inputs, is what gives the algorithm its name: *backpropagation*\n",
    "[@Rumelhart.Hinton.Williams.ea.1988]. It is two\n",
    "passes: a *forward pass* that evaluates the function and records the single-step\n",
    "partials, and a *backward pass* that accumulates $\\frac{\\partial f}{\\partial\n",
    "\\cdot}$ from output to input. This is exactly how the deep learning library\n",
    "obtains the gradient of the loss with respect to *every* weight in a\n",
    "single sweep, and it is what the one-line autograd call in the cell below runs\n",
    "under the hood."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "multivariable-calculus-the-backpropagation-algorithm-3"
   },
   "source": [
    "# Define the function to differentiate\n",
    "def f_comp(w, x, y, z):\n",
    "    a, b = (w + x + y + z)**2, (w + x - y - z)**2\n",
    "    u, v = (a + b)**2, (a - b)**2\n",
    "    return ((u + v)**2).squeeze()\n",
    "\n",
    "w, x, y, z = jnp.array([1.]), jnp.array([1.]), jnp.array([-2.]), jnp.array([1.])\n",
    "\n",
    "# Compute gradients with respect to all four arguments\n",
    "grad_f = jax.grad(f_comp, argnums=(0, 1, 2, 3))\n",
    "w_grad, x_grad, y_grad, z_grad = grad_f(w, x, y, z)\n",
    "\n",
    "print(f'df/dw at {w}, {x}, {y}, {z} is {w_grad}')\n",
    "print(f'df/dx at {w}, {x}, {y}, {z} is {x_grad}')\n",
    "print(f'df/dy at {w}, {x}, {y}, {z} is {y_grad}')\n",
    "print(f'df/dz at {w}, {x}, {y}, {z} is {z_grad}')"
   ],
   "execution_count": 7,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "df/dw at [1.], [1.], [-2.], [1.] is [73472.]\ndf/dx at [1.], [1.], [-2.], [1.] is [73472.]\ndf/dy at [1.], [1.], [-2.], [1.] is [-68224.]\ndf/dz at [1.], [1.], [-2.], [1.] is [-68224.]\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-multivariable-calculus-md-8 fw=all -->\n",
    "\n",
    "The library's answer matches our hand-computed backward pass. Why backprop is\n",
    "reverse-mode automatic differentiation, a chain of vector–Jacobian products,\n",
    "and when to prefer it over forward mode is the\n",
    "subject of that section.\n",
    "\n",
    "## Second-Order Structure: the Hessian\n",
    "\n",
    "The gradient is a first-order, linear approximation; to know whether a critical\n",
    "point is a minimum we need the *curvature*, which lives in the second\n",
    "derivatives. A function of $n$ variables has $n^2$ second partials,\n",
    "\n",
    "$$\n",
    "\\frac{\\partial^2 f}{\\partial x_i \\partial x_j} = \\frac{\\partial}{\\partial x_i}\\left(\\frac{\\partial}{\\partial x_j} f\\right),\n",
    "$$\n",
    "\n",
    "collected into the *Hessian* matrix\n",
    "\n",
    "$$\\mathbf{H}_f = \\begin{bmatrix} \\frac{\\partial^2 f}{\\partial x_1 \\partial x_1} & \\cdots & \\frac{\\partial^2 f}{\\partial x_1 \\partial x_n} \\\\ \\vdots & \\ddots & \\vdots \\\\ \\frac{\\partial^2 f}{\\partial x_n \\partial x_1} & \\cdots & \\frac{\\partial^2 f}{\\partial x_n \\partial x_n} \\\\ \\end{bmatrix}.$$\n",
    "\n",
    "These $n^2$ entries are not independent: the Hessian is symmetric, a result\n",
    "known as the Clairaut–Schwarz theorem [@Rudin.1976].\n",
    "\n",
    "**Proposition (symmetry of the Hessian; Clairaut–Schwarz).** *If the mixed partials of\n",
    "$f$ exist and are continuous, then for all $i, j$,*\n",
    "\n",
    "$$\n",
    "\\frac{\\partial^2 f}{\\partial x_i \\partial x_j} = \\frac{\\partial^2 f}{\\partial x_j \\partial x_i},\n",
    "\\qquad\\textrm{equivalently}\\qquad \\mathbf{H}_f = \\mathbf{H}_f^\\top.\n",
    "$$\n",
    "\n",
    "**Proof.** Both mixed partials are limits of the *same* quantity, the\n",
    "symmetric second difference\n",
    "\n",
    "$$\n",
    "\\Delta_h = \\frac{f(\\mathbf{x}+h\\mathbf{e}_i+h\\mathbf{e}_j) - f(\\mathbf{x}+h\\mathbf{e}_i) - f(\\mathbf{x}+h\\mathbf{e}_j) + f(\\mathbf{x})}{h^2},\n",
    "$$\n",
    "\n",
    "which is symmetric in $i$ and $j$ by inspection. Indeed, write\n",
    "$g(t) = f(\\mathbf{x}+t\\mathbf{e}_i+h\\mathbf{e}_j) - f(\\mathbf{x}+t\\mathbf{e}_i)$,\n",
    "so that $\\Delta_h = \\bigl(g(h)-g(0)\\bigr)/h^2$; two applications of the mean\n",
    "value theorem (first along $x_i$, then along $x_j$) give\n",
    "$\\Delta_h = \\frac{\\partial^2 f}{\\partial x_j \\partial x_i}(\\boldsymbol{\\xi}_h)$\n",
    "at some point $\\boldsymbol{\\xi}_h$ within distance $2h$ of $\\mathbf{x}$.\n",
    "Swapping the roles of $i$ and $j$ leaves $\\Delta_h$ unchanged and gives\n",
    "$\\Delta_h = \\frac{\\partial^2 f}{\\partial x_i \\partial x_j}(\\boldsymbol{\\xi}'_h)$\n",
    "at another nearby point. Let $h \\to 0$: by continuity the two expressions\n",
    "converge to the two mixed partials at $\\mathbf{x}$, and since they are equal\n",
    "for every $h$, the limits agree. $\\blacksquare$\n",
    "\n",
    "Symmetry matters because it puts the Hessian in the world of symmetric matrices,\n",
    "where the spectral theorem and positive-definiteness from\n",
    "that section apply, which is exactly what the\n",
    "second-derivative test will use.\n",
    "\n",
    "### The Second-Order Taylor Approximation\n",
    "\n",
    "Just as the gradient gives the best linear fit, the Hessian gives the best\n",
    "*quadratic* fit. To see how the coefficients enter, read them off an exact\n",
    "quadratic. Let $f(x_1, x_2) = a + b_1x_1 + b_2x_2 + c_{11}x_1^{2} + c_{12}x_1x_2 + c_{22}x_2^{2}$.\n",
    "Evaluating the value, gradient, and Hessian the equation at the\n",
    "origin gives\n",
    "\n",
    "$$\n",
    "f(0,0) = a, \\qquad\n",
    "\\nabla f (0,0) = \\begin{bmatrix}b_1 \\\\ b_2\\end{bmatrix}, \\qquad\n",
    "\\mathbf{H} f (0,0) = \\begin{bmatrix}2 c_{11} & c_{12} \\\\ c_{12} & 2c_{22}\\end{bmatrix},\n",
    "$$\n",
    "\n",
    "and these recover the polynomial exactly:\n",
    "$f(\\mathbf{x}) = f(0) + \\nabla f(0) \\cdot \\mathbf{x} + \\tfrac12\\mathbf{x}^\\top \\mathbf{H} f(0)\\, \\mathbf{x}$.\n",
    "\n",
    "For a general $f$, twice differentiable near a base point $\\mathbf{x}_0$, the\n",
    "same assembly is no longer exact, but restricting $f$ to a line shows exactly\n",
    "how close it comes. Fix a displacement $\\boldsymbol{\\delta} = \\mathbf{x} -\n",
    "\\mathbf{x}_0$ and let $g(t) = f(\\mathbf{x}_0 + t\\boldsymbol{\\delta})$, a\n",
    "function of the single variable $t$. By the multivariate chain rule,\n",
    "$g'(t) = \\nabla f(\\mathbf{x}_0 + t\\boldsymbol{\\delta})\\cdot\\boldsymbol{\\delta}$\n",
    "and $g''(t) = \\boldsymbol{\\delta}^\\top \\mathbf{H} f(\\mathbf{x}_0 +\n",
    "t\\boldsymbol{\\delta})\\,\\boldsymbol{\\delta}$, so $g'(0)$ and $g''(0)$ are\n",
    "exactly the gradient term and the Hessian quadratic form at $\\mathbf{x}_0$.\n",
    "Now apply the single-variable Lagrange remainder the equation,\n",
    "established in the previous section, to $g$ on $[0, 1]$ with $n = 1$: there is\n",
    "a $\\tau \\in (0, 1)$ with\n",
    "\n",
    "$$\n",
    "f(\\mathbf{x}) = g(1) = g(0) + g'(0) + \\tfrac{1}{2}g''(\\tau) = f(\\mathbf{x}_0) + \\nabla f(\\mathbf{x}_0)\\cdot\\boldsymbol{\\delta} + \\tfrac{1}{2}\\boldsymbol{\\delta}^\\top \\mathbf{H} f(\\mathbf{x}_0 + \\tau\\boldsymbol{\\delta})\\,\\boldsymbol{\\delta}.\n",
    "$$\n",
    "\n",
    "This identity is exact; its only blemish is that the Hessian is evaluated at\n",
    "an intermediate point $\\mathbf{x}_0 + \\tau\\boldsymbol{\\delta}$ rather than at\n",
    "$\\mathbf{x}_0$. When the second partials are continuous, moving the evaluation\n",
    "point back to $\\mathbf{x}_0$ changes the quadratic term by\n",
    "$o(\\|\\boldsymbol{\\delta}\\|^2)$, giving the *second-order Taylor approximation*\n",
    "\n",
    "$$\n",
    "f(\\mathbf{x}) \\approx f(\\mathbf{x}_0) + \\nabla f (\\mathbf{x}_0) \\cdot (\\mathbf{x}-\\mathbf{x}_0) + \\frac{1}{2}(\\mathbf{x}-\\mathbf{x}_0)^\\top \\mathbf{H} f (\\mathbf{x}_0) (\\mathbf{x}-\\mathbf{x}_0).\n",
    "$$\n",
    "\n",
    "This is the best-approximating quadratic to $f$ near $\\mathbf{x}_0$ in a\n",
    "precise sense: its error vanishes faster than $\\|\\mathbf{x}-\\mathbf{x}_0\\|^2$,\n",
    "and it is the only quadratic with that property. For smoother $f$ (three\n",
    "continuous derivatives) the error is *third order* in the step. To see it in\n",
    "numbers, take $f(x, y) = xe^{-x^2-y^2}$. Assembling its value,\n",
    "gradient, and Hessian at $\\mathbf{x}_0 = [-1, 0]^\\top$ via\n",
    "the equation gives the approximating quadratic\n",
    "$q(x, y) = e^{-1}\\bigl(-1 - (x+1) + (x+1)^2 + y^2\\bigr)$.\n",
    "the figure plots the surface against this quadratic;\n",
    "near $[-1, 0]^\\top$ they hug each other and peel apart only as we move away.\n",
    "\n",
    "![The surface $z = xe^{-x^2-y^2}$ (blue) and its second-order Taylor quadratic at the base point $(-1, 0)^\\top$ (orange). The two agree in value, slope, and curvature there, so they are nearly indistinguishable in a neighborhood of the base point and separate only farther out.](../img/mdl-cal-taylor-quadratic.svg)\n",
    "\n",
    "The figure asserts agreement; we can check it numerically, exactly as\n",
    "we checked the gradient above. Evaluating $f$ and its quadratic $q$ at a few\n",
    "points stepping away from the base point, the gap should stay tiny nearby and\n",
    "grow with distance."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "multivariable-calculus-hessians"
   },
   "source": [
    "def f(x, y):\n",
    "    return x * math.exp(-x**2 - y**2)\n",
    "\n",
    "def quad(x, y):  # 2nd-order Taylor of f at the base point (-1, 0)\n",
    "    return math.exp(-1) * (-1 - (x + 1) + (x + 1)**2 + y**2)\n",
    "\n",
    "for d in [0.0, 0.05, 0.1, 0.3]:  # step d in each coordinate from (-1, 0)\n",
    "    x, y = -1 + d, d\n",
    "    print(f'step {d:.2f}: f = {f(x, y):.6f}, '\n",
    "          f'quadratic = {quad(x, y):.6f}, gap = {abs(f(x, y) - quad(x, y)):.6f}')"
   ],
   "execution_count": 8,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "step 0.00: f = -0.367879, quadratic = -0.367879, gap = 0.000000\nstep 0.05: f = -0.384315, quadratic = -0.384434, gap = 0.000119\nstep 0.10: f = -0.396388, quadratic = -0.397310, gap = 0.000921\nstep 0.30: f = -0.391929, quadratic = -0.412025, gap = 0.020096\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-multivariable-calculus-md-9 fw=all -->\n",
    "\n",
    "The gap vanishes at the base point and is third order in the step (doubling the\n",
    "step roughly multiplies it by eight), the third-order behavior promised above.\n",
    "Iterating this idea, repeatedly fitting the local quadratic and jumping to *its*\n",
    "minimum, is Newton's method, which that section introduced in one\n",
    "variable; that section develops it as a practical optimizer.\n",
    "\n",
    "### The Second-Derivative Test\n",
    "\n",
    "We can now finish the story the first-order test left open: at a critical point,\n",
    "the Hessian decides whether we sit at a minimum, a maximum, or a saddle. At a\n",
    "critical point $\\mathbf{x}_0$ the gradient term in the equation\n",
    "vanishes, so the local picture is purely quadratic,\n",
    "\n",
    "$$\n",
    "f(\\mathbf{x}) - f(\\mathbf{x}_0) \\approx \\frac{1}{2}(\\mathbf{x}-\\mathbf{x}_0)^\\top \\mathbf{H} f (\\mathbf{x}_0)(\\mathbf{x}-\\mathbf{x}_0).\n",
    "$$\n",
    "\n",
    "Stepping a unit direction $\\mathbf{v}$ away from $\\mathbf{x}_0$ makes the\n",
    "right-hand side $\\tfrac12\\mathbf{v}^\\top\\mathbf{H}\\mathbf{v}$: the scalar\n",
    "$\\mathbf{v}^\\top\\mathbf{H}\\mathbf{v}$ is the *second directional derivative* of\n",
    "$f$ along $\\mathbf{v}$, the second-order analogue of $\\mathbf{v}\\cdot\\nabla f$,\n",
    "and at a critical point, where the slope term is gone, it is the curvature of\n",
    "$f$ along $\\mathbf{v}$. Whether $f$ goes up or down as we leave $\\mathbf{x}_0$\n",
    "is governed entirely by the sign of this quadratic form, that is, by the\n",
    "*definiteness* of the symmetric matrix $\\mathbf{H}$. The classification is read straight off the\n",
    "eigenvalues of $\\mathbf{H}$ via the PSD/PD criterion of\n",
    "that section:\n",
    "\n",
    "* $\\mathbf{H} \\succ 0$ (all eigenvalues positive): $f$ curves *upward* in every\n",
    "  direction. Quantitatively, the quadratic term is at least\n",
    "  $\\tfrac12\\lambda_{\\min}\\|\\mathbf{v}\\|^2$ for a step $\\mathbf{v}$, where\n",
    "  $\\lambda_{\\min} > 0$ is the smallest eigenvalue, and this dominates the\n",
    "  approximation's $o(\\|\\mathbf{v}\\|^2)$ error for all small $\\mathbf{v}$, so\n",
    "  $\\mathbf{x}_0$ is a strict local **minimum**.\n",
    "* $\\mathbf{H} \\prec 0$ (all eigenvalues negative): $f$ curves downward\n",
    "  everywhere, so $\\mathbf{x}_0$ is a local **maximum**.\n",
    "* $\\mathbf{H}$ *indefinite* (eigenvalues of both signs): $f$ rises along some\n",
    "  directions and falls along others: a **saddle**.\n",
    "* $\\mathbf{H} \\succeq 0$ with a zero eigenvalue (semidefinite): the quadratic is\n",
    "  flat along that eigenvector and second order is *inconclusive*; the behavior\n",
    "  is decided by higher-order terms.\n",
    "\n",
    "These local shapes (the bowl, the saddle, and the flat-bottomed trough of the\n",
    "semidefinite case) are exactly the quadratic-form surfaces drawn in\n",
    "the figure.\n",
    "\n",
    "This is the multivariable generalization of the single-variable test $f'' > 0$:\n",
    "there, curvature is a single number; here it is a matrix, and \"positive\n",
    "curvature\" becomes \"positive definite.\" Identity the equation makes\n",
    "the upward-curving picture precise, writing the quadratic form as a weighted sum\n",
    "of squares over the eigenvector directions with the eigenvalues as weights.\n",
    "\n",
    "The test is one we can run. The surface of the figure,\n",
    "$f(x, y) = xe^{-x^2-y^2}$, has exactly two critical points: setting\n",
    "$\\frac{\\partial f}{\\partial x} = (1 - 2x^2)\\,e^{-x^2-y^2}$ and\n",
    "$\\frac{\\partial f}{\\partial y} = -2xy\\,e^{-x^2-y^2}$ to zero forces $y = 0$ and\n",
    "$x = \\pm 1/\\sqrt{2}$. The next cell assembles each Hessian from symmetric second\n",
    "differences (the same quantity $\\Delta_h$ that proved the Clairaut–Schwarz\n",
    "theorem), reads\n",
    "off the eigenvalues of a $2 \\times 2$ symmetric matrix in closed form, and\n",
    "prints the classification."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "mdl-multivariable-calculus-the-second-derivative-test"
   },
   "source": [
    "# Classify the critical points (+-1/sqrt(2), 0) of f(x, y) = x e^(-x^2-y^2)\n",
    "def hessian(f, x, y, h=1e-4):  # symmetric second differences\n",
    "    fxx = (f(x + h, y) - 2 * f(x, y) + f(x - h, y)) / h**2\n",
    "    fyy = (f(x, y + h) - 2 * f(x, y) + f(x, y - h)) / h**2\n",
    "    fxy = (f(x + h, y + h) - f(x + h, y - h)\n",
    "           - f(x - h, y + h) + f(x - h, y - h)) / (4 * h**2)\n",
    "    return fxx, fxy, fyy\n",
    "\n",
    "for x0 in [-1 / math.sqrt(2), 1 / math.sqrt(2)]:\n",
    "    fxx, fxy, fyy = hessian(f, x0, 0.0)\n",
    "    mid, r = (fxx + fyy) / 2, math.sqrt(((fxx - fyy) / 2)**2 + fxy**2)\n",
    "    lo, hi = mid - r, mid + r  # eigenvalues of [[fxx, fxy], [fxy, fyy]]\n",
    "    kind = 'minimum' if lo > 0 else 'maximum' if hi < 0 else 'saddle'\n",
    "    print(f'at ({x0:+.4f}, 0): eigenvalues {lo:+.3f}, {hi:+.3f} -> {kind}')"
   ],
   "execution_count": 9,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "at (-0.7071, 0): eigenvalues +0.858, +1.716 -> minimum\nat (+0.7071, 0): eigenvalues -1.716, -0.858 -> maximum\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-multivariable-calculus-md-10 fw=all -->\n",
    "\n",
    "At $(-1/\\sqrt{2}, 0)$ both eigenvalues are positive ($\\mathbf{H} \\succ 0$, a\n",
    "strict local minimum) and at $(+1/\\sqrt{2}, 0)$ both are negative, a local\n",
    "maximum; a saddle would show one eigenvalue of each sign, as in\n",
    "Exercise 5. This five-line loop is the second-derivative test as a program:\n",
    "differentiate twice (here numerically; autograd Hessians appear in\n",
    "that section), extract eigenvalues, read the signs.\n",
    "\n",
    "The eigenvalue picture also explains why, in high dimension, saddles are the\n",
    "rule rather than the exception: a minimum requires *all* $n$ eigenvalues to be\n",
    "positive at once, and if the signs at a random critical point behaved like\n",
    "independent coin flips, that would happen with probability $2^{-n}$. The\n",
    "coin-flip heuristic can be made precise: for random Gaussian landscapes the\n",
    "statistics of critical points can be computed exactly and minima are\n",
    "exponentially outnumbered by saddles [@Bray.Dean.2007], and the critical\n",
    "points actually encountered while training deep networks are overwhelmingly\n",
    "saddles too [@Dauphin.Pascanu.Gulcehre.ea.2014], one reason gradient\n",
    "methods fare better in practice than the old fear of \"getting stuck in a bad\n",
    "local minimum\" suggests.\n",
    "\n",
    "With the Hessian in hand, the one-variable toolkit has been fully lifted:\n",
    "gradient for slope, Hessian for curvature, and the chain rule organized\n",
    "backward for the computation. What has *not* yet been lifted is the function\n",
    "itself: everything above differentiated a *scalar* loss, while real layers map\n",
    "vectors to vectors and carry matrix parameters, so the derivative becomes a\n",
    "matrix of partials, the *Jacobian*, with the gradient and Hessian as special\n",
    "cases. One caution for that road: the Mean Value Theorem of\n",
    "that section does *not* survive the passage to vector-valued maps;\n",
    "only an inequality remains, the mean value inequality [@Rudin.1976]. The\n",
    "Jacobian machinery, the layout conventions, and how it all yields\n",
    "backpropagation as reverse-mode automatic differentiation are the subject of\n",
    "that section.\n",
    "\n",
    "## Summary\n",
    "\n",
    "* The *gradient* $\\nabla_{\\mathbf{w}} L$ is the derivative in many dimensions: it\n",
    "  gives the first-order change $L(\\mathbf{w}+\\boldsymbol{\\epsilon}) \\approx\n",
    "  L(\\mathbf{w}) + \\boldsymbol{\\epsilon}\\cdot\\nabla_{\\mathbf{w}} L$, and its dot\n",
    "  product with a unit direction is the rate of change along that direction.\n",
    "* By Cauchy–Schwarz, $+\\nabla L$ is the direction of steepest ascent and\n",
    "  $-\\nabla L$ of steepest descent, and the gradient is everywhere orthogonal to\n",
    "  the level sets of $L$: the geometry behind gradient descent.\n",
    "* The multivariate *chain rule* sums, over every path from an input to the\n",
    "  output, the product of edge derivatives. Organizing it from the output\n",
    "  backward reuses every intermediate, giving *backpropagation*: a forward pass\n",
    "  followed by a backward pass that yields the gradient with respect to all\n",
    "  parameters at once.\n",
    "* The symmetric *Hessian* supplies the second-order Taylor approximation; at a\n",
    "  critical point its definiteness, read from its eigenvalues, distinguishes a\n",
    "  minimum, a maximum, and a saddle.\n",
    "\n",
    "## Exercises\n",
    "1. Let $L(x, y) = \\log(e^x + e^y)$. Compute the gradient, and verify that the\n",
    "   sum of its components is always $1$. What does that say about the directions\n",
    "   in which $L$ grows fastest?\n",
    "2. For $f(x, y) = x^2 + 2y^2$, compute $\\nabla f$ and verify at a sample point on\n",
    "   the ellipse $f = c$ that the gradient is orthogonal to the level curve.\n",
    "3. Prove directly from the equation that at a local minimum the\n",
    "   gradient must vanish.\n",
    "4. Let $f(x, y) = x^3 - 3x + y^2$. Show that the critical points are\n",
    "   $(\\pm 1, 0)$. By examining $f$ along the lines $y = 0$ and $x = \\pm 1$,\n",
    "   determine whether each is a minimum, a maximum, or a saddle, and confirm by\n",
    "   computing the Hessian there.\n",
    "5. Classify the critical point of $f(x, y) = x^2 - y^2$ by inspecting the\n",
    "   eigenvalues of its (constant) Hessian. Why is this point a saddle?\n",
    "6. Give a two-variable $f$ whose Hessian at a critical point is positive\n",
    "   *semidefinite* (one zero eigenvalue) yet the point is not a local minimum.\n",
    "   Why does the second-derivative test go silent here?\n",
    "7. Suppose we minimize $f(\\mathbf{x}) = g(\\mathbf{x}) + h(\\mathbf{x})$. Interpret\n",
    "   the condition $\\nabla f = \\mathbf{0}$ geometrically in terms of $\\nabla g$ and\n",
    "   $\\nabla h$.\n",
    "8. Use the Lagrange condition the equation to maximize\n",
    "   $f(x, y) = xy$ subject to $g(x, y) = x + y = 1$. First check that\n",
    "   $\\nabla g \\neq \\mathbf{0}$ everywhere, so the condition applies; then solve\n",
    "   $\\nabla f = \\lambda \\nabla g$ together with the constraint, and confirm your\n",
    "   answer by eliminating $y = 1 - x$ and maximizing in one variable. Finally,\n",
    "   replace the constraint by $x + y = 1 + \\delta$ and show that the maximum\n",
    "   value changes by $\\lambda\\delta$ to first order: the multiplier prices the\n",
    "   constraint."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-multivariable-calculus-md-11 fw=jax -->\n",
    "\n",
    "[Discussions](https://d2l.discourse.group/t/1091)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "name": "d2l-jax",
   "display_name": "d2l (JAX)",
   "language": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
