{
 "cells": [
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "---\n",
    "execute:\n",
    "  enabled: false\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-single-variable-calculus-md-1 fw=all -->\n",
    "\n",
    "# Single Variable Calculus\n",
    "\n",
    "In that section, we met the basic elements of differential calculus. This section goes deeper, building the one-variable theory we actually lean on in deep learning: the derivative as a *local linear model*, the rules that compute it mechanically, and three things that local model is *for*: it hands us gradient descent, it explains curvature through the second derivative and Taylor series, and it tells us what to do at the corners of a function like $\\mathrm{ReLU}$ where the model breaks down.\n",
    "\n",
    "## The Derivative\n",
    "\n",
    "Differential calculus is, at heart, the study of how a function behaves under a *small change* of its input. To see why this is the question deep learning cares about, picture a neural network whose weights are stacked into one long vector $\\mathbf{w} = (w_1, \\ldots, w_n)$, and write $L(\\mathbf{w})$ for its loss on a training set. This $L$ is hopelessly complicated (it encodes the performance of *every* model of the given architecture), so we cannot simply read off the minimizing $\\mathbf{w}$. Instead we initialize $\\mathbf{w}$ randomly and repeatedly take a small step against the gradient,\n",
    "\n",
    "$$\n",
    "\\mathbf{w} \\leftarrow \\mathbf{w} - \\eta\\, \\nabla L(\\mathbf{w}),\n",
    "$$\n",
    "\n",
    "where $\\nabla L(\\mathbf{w})$ (the *gradient*, defined in that section) collects the derivative of $L$ with respect to each weight, and $\\eta > 0$ is a small *step size*. Everything in this section is in service of one question: *which way is downhill, and by how much?* We answer it first for a single weight: freeze every weight but one, call the free one $x \\in \\mathbb{R}$, and study the one-variable slice $f(x) = L(w_1, \\ldots, x, \\ldots, w_n)$.\n",
    "\n",
    "### Zooming In: Every Smooth Curve Looks Like a Line\n",
    "\n",
    "Take a point $x$ and nudge it to $x + \\epsilon$ for a tiny $\\epsilon$ (if it helps, picture $\\epsilon = 10^{-7}$). Plot any familiar function, say $f(x) = \\sin(x^x)$ on $[0,3]$, and it wiggles in a complicated way; but zoom in on a small window around a point and the wiggles flatten out, until on a small enough scale the graph is indistinguishable from a *straight line*. the figure shows this for three successively smaller windows.\n",
    "\n",
    "![The same smooth curve viewed over shrinking $x$-ranges: as we zoom in around the base point it flattens onto its tangent line.](../img/mdl-cal-zoom-sequence.svg)\n",
    "\n",
    "This is the observation single-variable calculus is built on: *locally, a smooth function is a line.* So as we shift $x$ by a little, $f(x)$ shifts by a little too, and the only thing left to pin down is the proportionality: is the output change half the input change? Twice? That ratio is the slope of the line we zoomed in on.\n",
    "\n",
    "### The Difference Quotient and the Derivative\n",
    "\n",
    "To measure that slope we compare the change in output to the change in input,\n",
    "\n",
    "$$\n",
    "\\frac{f(x+\\epsilon) - f(x)}{(x+\\epsilon) - x} = \\frac{f(x+\\epsilon) - f(x)}{\\epsilon},\n",
    "$$\n",
    "\n",
    "the slope of the *secant* line through $(x, f(x))$ and $(x+\\epsilon, f(x+\\epsilon))$. As $\\epsilon$ shrinks, the second point slides toward the first and the secant rotates into the tangent line we saw under the microscope; the figure shows this rotation. We can watch the slope settle down in code. We use the following imports throughout the section.\n",
    "\n",
    "![The difference quotient is the slope of the secant through $(x, f(x))$ and $(x+\\epsilon, f(x+\\epsilon))$; as $\\epsilon \\to 0$ the second point slides toward the first and the secant rotates into the tangent line, whose slope is the derivative $f'(x)$.](../img/mdl-cal-secant-to-tangent.svg)"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "single-variable-calculus-imports"
   },
   "source": [
    "%matplotlib inline\n",
    "import math\n",
    "import numpy as onp\n",
    "from d2l import torch as d2l\n",
    "import torch"
   ],
   "execution_count": 1,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-single-variable-calculus-md-2 fw=all -->\n",
    "\n",
    "Take $f(x) = x^2 + 1701(x-4)^3$ and evaluate the difference quotient at $x = 4$ for shrinking $\\epsilon$."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "single-variable-calculus-differential-calculus-4"
   },
   "source": [
    "# Define our function\n",
    "def f(x):\n",
    "    return x**2 + 1701*(x-4)**3\n",
    "\n",
    "# Slope of the secant through x=4, for shrinking epsilon\n",
    "for epsilon in [0.1, 0.001, 0.0001, 0.00001]:\n",
    "    print(f'epsilon = {epsilon:.5f} -> {(f(4+epsilon) - f(4)) / epsilon:.5f}')"
   ],
   "execution_count": 2,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "epsilon = 0.10000 -> 25.11000\nepsilon = 0.00100 -> 8.00270\nepsilon = 0.00010 -> 8.00012\nepsilon = 0.00001 -> 8.00001\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-single-variable-calculus-md-3 fw=all -->\n",
    "\n",
    "The numbers march toward $8$, and the smaller $\\epsilon$ gets the closer they sit. The cubic is there to make the convergence *visible*: expanding $f(4+\\epsilon) - f(4) = 8\\epsilon + \\epsilon^2 + 1701\\,\\epsilon^3$, the difference quotient is $8 + \\epsilon + 1701\\,\\epsilon^2$, so the cubic contributes a $1701\\,\\epsilon^2$ error: a hefty $17$ at $\\epsilon = 0.1$ (which is why the top row sits so far off) but a negligible $1.7\\times10^{-7}$ once $\\epsilon$ reaches $10^{-5}$. So the slope we are after at $x = 4$ is $8$, written\n",
    "\n",
    "$$\n",
    "\\lim_{\\epsilon \\rightarrow 0}\\frac{f(4+\\epsilon) - f(4)}{\\epsilon} = 8.\n",
    "$$\n",
    "\n",
    "The table only ever creeps toward that limit; the framework's automatic differentiation (that section) applies exact differentiation rules instead, evaluated in floating-point arithmetic, so there is no $\\epsilon$ and no truncation error (only rounding remains). Asking the framework for the slope of the very same $f$ at $x = 4$ returns $8$ on the nose. This is the machinery the differentiation rules below formalize, and that we rebuild from scratch in that section."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "single-variable-calculus-autograd-check"
   },
   "source": [
    "# Autograd computes the limit exactly: f'(4) = 8\n",
    "x = torch.tensor(4.0, requires_grad=True)\n",
    "f(x).backward()\n",
    "print(f\"autograd: f'(4) = {x.grad.item():.1f}\")"
   ],
   "execution_count": 3,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "autograd: f'(4) = 8.0\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-single-variable-calculus-md-4 fw=all -->\n",
    "\n",
    "This very computation, the *method of finite differences*, measures the effect of a weight on the loss directly: perturb the weight, re-run the network, watch the loss move. It costs an extra evaluation of $L$ per weight (or two, for the centered differences that halve the truncation error), so with even a few thousand parameters it is thousands of forward passes for a single gradient. The *backpropagation algorithm* popularized in 1986 by @Rumelhart.Hinton.Williams.ea.1988 removes that bottleneck: it delivers the effect of *all* weights at once, at a small constant multiple of the cost of one forward pass, the *cheap-gradient principle* [@Griewank.Walther.2008]. Backpropagation is the chain rule (below) run in reverse over the network.\n",
    "\n",
    "The slope is itself a function of $x$, so we name it. The **derivative** of $f$ is\n",
    "\n",
    "$$\\frac{df}{dx}(x) = \\lim_{\\epsilon \\rightarrow 0}\\frac{f(x+\\epsilon) - f(x)}{\\epsilon},$$\n",
    "\n",
    "when the limit exists. (When it fails to, as at the corner of $\\mathrm{ReLU}$, we will need the refinement of that section.) Many notations denote this same object, and all of them appear in the literature:\n",
    "\n",
    "$$\n",
    "\\frac{df}{dx} = \\frac{d}{dx}f = f' = D_xf = f_x.\n",
    "$$\n",
    "\n",
    "We default to $\\frac{df}{dx}$, switching to $\\frac{d}{dx}f$ when differentiating a bulky expression such as $\\frac{d}{dx}\\left[x^4+\\cos\\left(\\frac{x^2+1}{2x-1}\\right)\\right]$.\n",
    "\n",
    "### The Small-Change Identity\n",
    "\n",
    "Rearranging the definition gives an identity that turns knowledge of the derivative into a prediction of the function's values nearby. Since the quotient approaches the derivative, for small $\\epsilon$\n",
    "\n",
    "$$\n",
    "\\frac{f(x+\\epsilon) - f(x)}{\\epsilon} \\approx \\frac{df}{dx}(x)\n",
    "\\quad\\Longrightarrow\\quad\n",
    "f(x+\\epsilon) \\approx f(x) + \\epsilon \\frac{df}{dx}(x).\n",
    "$$\n",
    "\n",
    "Read it aloud: *nudge the input by $\\epsilon$ and the output moves by $\\epsilon$ times the derivative.* The derivative is the exchange rate between an input change and the output change it buys. We will use the symbol \"$\\approx$\" throughout to mean \"equal up to terms that vanish faster than $\\epsilon$ as $\\epsilon \\to 0$\"; formally, we write $o(\\epsilon)$ for any quantity with $o(\\epsilon)/\\epsilon \\to 0$ as $\\epsilon \\to 0$, so the equation reads $f(x+\\epsilon) = f(x) + \\epsilon \\frac{df}{dx}(x) + o(\\epsilon)$. Almost everything that follows (the differentiation rules, gradient descent, Taylor series) is an application of the equation.\n",
    "\n",
    "## Computing Derivatives\n",
    "\n",
    "A fully formal course would build every derivative from the limit the equation. We take the working mathematician's route instead: a short table of derivatives for the elementary functions, plus a handful of *rules* for combining them, from which any expression built out of sums, products, quotients, and compositions can be differentiated mechanically.\n",
    "\n",
    "### A Table of Common Derivatives\n",
    "\n",
    "As in that section, most derivatives reduce to a few core ones, repeated here for reference.\n",
    "\n",
    "* **Derivative of constants.** $\\frac{d}{dx}c = 0$.\n",
    "* **Derivative of linear functions.** $\\frac{d}{dx}(ax) = a$.\n",
    "* **Power rule.** $\\frac{d}{dx}x^n = nx^{n-1}$.\n",
    "* **Derivative of exponentials.** $\\frac{d}{dx}e^x = e^x$.\n",
    "* **Derivative of the logarithm.** $\\frac{d}{dx}\\log(x) = \\frac{1}{x}$.\n",
    "* **Derivative of sine.** $\\frac{d}{dx}\\sin(x) = \\cos(x)$.\n",
    "* **Derivative of cosine.** $\\frac{d}{dx}\\cos(x) = -\\sin(x)$.\n",
    "\n",
    "(That $e^x$ is its own derivative is the small-change identity in disguise: $e^{x+\\epsilon} = e^x e^{\\epsilon} \\approx e^x(1 + \\epsilon)$, so the coefficient of $\\epsilon$ is $e^x$ itself. This takes the first-order expansion $e^{\\epsilon} \\approx 1 + \\epsilon$ as given, since that expansion *is* the table entry at $x = 0$; the aside is intuition for the entry, not an independent proof of it.)\n",
    "\n",
    "### Four Rules from One Identity\n",
    "\n",
    "Storing a derivative for every conceivable function is hopeless. What makes calculus tractable is that derivatives respect the ways we *build* functions (adding, multiplying, dividing, and composing), so any expression assembled from the table can be differentiated by following the matching rules:\n",
    "\n",
    "* **Sum rule.** $\\frac{d}{dx}\\left(g(x) + h(x)\\right) = \\frac{dg}{dx}(x) + \\frac{dh}{dx}(x)$.\n",
    "* **Product rule.** $\\frac{d}{dx}\\left(g(x)\\, h(x)\\right) = g(x)\\frac{dh}{dx}(x) + \\frac{dg}{dx}(x)h(x)$.\n",
    "* **Quotient rule.** $\\frac{d}{dx}\\left(\\frac{g(x)}{h(x)}\\right) = \\frac{\\frac{dg}{dx}(x)h(x) - g(x)\\frac{dh}{dx}(x)}{h(x)^2}$, valid wherever $h(x)\\neq 0$.\n",
    "* **Chain rule.** $\\frac{d}{dx}g(h(x)) = \\frac{dg}{dh}(h(x))\\cdot \\frac{dh}{dx}(x)$.\n",
    "\n",
    "Each of these is one line of the small-change identity the equation. The recipe never varies: write $f(x+\\epsilon)$, expand every factor to first order in $\\epsilon$, and read off the coefficient of $\\epsilon$: that coefficient *is* the derivative, because the equation says $f(x+\\epsilon) \\approx f(x) + \\epsilon f'(x)$.\n",
    "\n",
    "**Sum rule.** Expanding each summand,\n",
    "\n",
    "$$\n",
    "f(x+\\epsilon) = g(x+\\epsilon) + h(x+\\epsilon)\n",
    "\\approx \\Bigl(g(x) + h(x)\\Bigr) + \\epsilon\\left(\\frac{dg}{dx}(x) + \\frac{dh}{dx}(x)\\right),\n",
    "$$\n",
    "\n",
    "so the coefficient of $\\epsilon$, the derivative, is $\\frac{dg}{dx}(x) + \\frac{dh}{dx}(x)$. Two changes simply add. $\\blacksquare$\n",
    "\n",
    "**Product rule.** Expanding both factors and multiplying out,\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "f(x+\\epsilon) = g(x+\\epsilon)\\,h(x+\\epsilon)\n",
    "&\\approx \\left(g(x) + \\epsilon g'(x)\\right)\\left(h(x) + \\epsilon h'(x)\\right) \\\\\n",
    "&= g(x)h(x) + \\epsilon\\Bigl(g(x)h'(x) + g'(x)h(x)\\Bigr) + \\underbrace{\\epsilon^2\\, g'(x)h'(x)}_{\\textrm{higher order}}.\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "The $\\epsilon^2$ term is a *higher-order term*: with $\\epsilon = 10^{-7}$ it is $10^{-14}$, dwarfed by the $\\epsilon$ term, and it vanishes faster than $\\epsilon$ as $\\epsilon \\to 0$. Dropping it, the coefficient of $\\epsilon$ gives $g(x)h'(x) + g'(x)h(x)$. The lopsided shape, *differentiate one factor, leave the other alone, then swap*, is exactly the two ways a rectangle of sides $g$ and $h$ grows when both sides stretch. (If you want to avoid \"$\\approx$\" entirely, divide the line above by $\\epsilon$: the difference quotient equals $g(x)h'(x)+g'(x)h(x) + \\epsilon\\,g'(x)h'(x)$, whose last term goes to $0$.) $\\blacksquare$\n",
    "\n",
    "**Chain rule.** Compose, then expand the *inner* function first and feed the result into the *outer* one:\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "f(x+\\epsilon) = g\\bigl(h(x+\\epsilon)\\bigr)\n",
    "&\\approx g\\!\\left(h(x) + \\epsilon\\, h'(x)\\right)\n",
    "&&\\text{(inner: small-change identity)}\\\\\n",
    "&\\approx g(h(x)) + \\epsilon\\, h'(x)\\, \\frac{dg}{dh}(h(x))\n",
    "&&\\text{(outer: small-change identity, with step } \\epsilon h'(x)).\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "The coefficient of $\\epsilon$ is $\\frac{dg}{dh}(h(x))\\, h'(x)$: a change in $x$ moves $h$ by $\\epsilon h'(x)$, and that in turn moves $g$ by its own derivative times that step: *the rates multiply*. The one subtlety is the second line, where we fed the *variable* step $\\epsilon h'(x)$ into $g$'s small-change identity: because $g$ is differentiable at $h(x)$, its error term is $o(\\text{step}) = o(\\epsilon h'(x))$ in the $o(\\cdot)$ notation we fixed after the equation, which is still $o(\\epsilon)$ and so vanishes faster than the $\\epsilon$ we keep. (The borderline case $h'(x) = 0$, where the step degenerates, is handled by the standard error-function form of the proof: write $g(h(x)+s) = g(h(x)) + (g'(h(x)) + r(s))\\,s$ with $r(s)\\to 0$, substitute $s = \\epsilon h'(x) + o(\\epsilon)$, and the same coefficient drops out.) This chaining of local linear factors, applied across the layers of a network, is the backpropagation we met above. (The quotient rule is the product and chain rules applied to $g\\cdot h^{-1}$; we leave it as Exercise 2.) $\\blacksquare$\n",
    "\n",
    "The chain rule also gives the derivative of an **inverse function**. If $g$ undoes $f$, meaning $g(f(x)) = x$, then differentiating both sides gives $g'(f(x))\\,f'(x) = 1$, so $g'(y) = 1/f'(g(y))$ wherever $f'(g(y)) \\neq 0$: the slope of the inverse is the *reciprocal* slope, read at the matching point (the graph of $g$ is the graph of $f$ flipped across the diagonal, which turns rise-over-run upside down). This is where the logarithm's entry in the table comes from: $\\log$ undoes $e^x$, so $\\frac{d}{dx}\\log(x) = 1/e^{\\log x} = 1/x$. The deep-learning instance is the sigmoid $\\sigma(x) = 1/(1+e^{-x})$, with $\\sigma' = \\sigma(1-\\sigma)$, and its inverse the *logit* $\\log\\frac{p}{1-p}$, whose derivative $\\frac{1}{p(1-p)}$ is exactly the reciprocal of $\\sigma'$ evaluated at the matching point.\n",
    "\n",
    "Together these rules let us differentiate essentially anything in closed form. For instance,\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\frac{d}{dx}\\left[\\log\\left(1+(x-1)^{10}\\right)\\right] & = \\left(1+(x-1)^{10}\\right)^{-1}\\frac{d}{dx}\\left[1+(x-1)^{10}\\right]\\\\\n",
    "& = \\left(1+(x-1)^{10}\\right)^{-1}\\left(\\frac{d}{dx}[1] + \\frac{d}{dx}[(x-1)^{10}]\\right) \\\\\n",
    "& = \\left(1+(x-1)^{10}\\right)^{-1}\\left(0 + 10(x-1)^9\\frac{d}{dx}[x-1]\\right) \\\\\n",
    "& = 10\\left(1+(x-1)^{10}\\right)^{-1}(x-1)^9 \\\\\n",
    "& = \\frac{10(x-1)^9}{1+(x-1)^{10}}.\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "Where each line has used the following rules:\n",
    "\n",
    "1. The chain rule and derivative of logarithm.\n",
    "2. The sum rule.\n",
    "3. The derivative of constants, chain rule, and power rule.\n",
    "4. The sum rule, derivative of linear functions, derivative of constants.\n",
    "\n",
    "Two lessons follow. First, *anything* assembled from sums, products, constants, powers, exponentials, and logarithms can be differentiated mechanically. Second, doing so by hand is tedious and error-prone, which is exactly why automatic differentiation (that section) mechanizes it.\n",
    "\n",
    "## Linear Approximation and Gradient Descent\n",
    "\n",
    "The small-change identity is the bridge from computing derivatives to using them for optimization. We first read it geometrically as the *tangent line*, then turn it into the gradient-descent step.\n",
    "\n",
    "### The Tangent Line\n",
    "\n",
    "Reading the equation as a function of the displacement, the line\n",
    "\n",
    "$$\n",
    "f(x+\\epsilon) \\approx f(x) + \\epsilon \\frac{df}{dx}(x)\n",
    "$$\n",
    "\n",
    "passes through $(x, f(x))$ with slope $\\frac{df}{dx}(x)$: it is the *tangent* at $x$, the best straight-line model of $f$ nearby and the limit of the rotating secants of the figure. Drawing the tangent at several points of $\\sin$, using $\\frac{d}{dx}\\sin(x) = \\cos(x)$, shows each line hugging the curve in a neighborhood and peeling away as we move off."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "single-variable-calculus-linear-approximation"
   },
   "source": [
    "import numpy as onp\n",
    "# Compute sin\n",
    "xs = onp.arange(-onp.pi, onp.pi, 0.01)\n",
    "plots = [onp.sin(xs)]\n",
    "\n",
    "# Compute some linear approximations. Use d(sin(x)) / dx = cos(x)\n",
    "for x0 in [-1.5, 0, 2]:\n",
    "    plots.append(onp.sin(x0) + (xs - x0) * onp.cos(x0))\n",
    "\n",
    "d2l.plot(xs, plots, 'x', 'f(x)', ylim=[-1.5, 1.5])"
   ],
   "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=\"254.660937pt\" height=\"187.155469pt\" viewBox=\"0 0 254.660937 187.155469\" 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:41:08.159128</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 187.155469 \nL 254.660937 187.155469 \nL 254.660937 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 52.160938 149.599219 \nL 247.460938 149.599219 \nL 247.460938 10.999219 \nL 52.160938 10.999219 \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 93.312826 149.599219 \nL 93.312826 10.999219 \n\" clip-path=\"url(#p12d81a8d4e)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_2\">\n      <defs>\n       <path id=\"mcec53c4d22\" d=\"M 0 0 \nL 0 3.5 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#mcec53c4d22\" x=\"93.312826\" y=\"149.599219\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_1\">\n      <!-- −2 -->\n      <g transform=\"translate(85.941732 164.197656) 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 149.855964 149.599219 \nL 149.855964 10.999219 \n\" clip-path=\"url(#p12d81a8d4e)\" 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=\"#mcec53c4d22\" x=\"149.855964\" y=\"149.599219\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_2\">\n      <!-- 0 -->\n      <g transform=\"translate(146.674714 164.197656) 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_3\">\n     <g id=\"line2d_5\">\n      <path d=\"M 206.399103 149.599219 \nL 206.399103 10.999219 \n\" clip-path=\"url(#p12d81a8d4e)\" 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=\"#mcec53c4d22\" x=\"206.399103\" y=\"149.599219\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_3\">\n      <!-- 2 -->\n      <g transform=\"translate(203.217853 164.197656) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-32\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_4\">\n     <!-- x -->\n     <g transform=\"translate(146.851563 177.875781) 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_7\">\n      <path d=\"M 52.160938 149.599219 \nL 247.460938 149.599219 \n\" clip-path=\"url(#p12d81a8d4e)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_8\">\n      <defs>\n       <path id=\"m1ed93afae0\" d=\"M 0 0 \nL -3.5 0 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m1ed93afae0\" x=\"52.160938\" y=\"149.599219\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_5\">\n      <!-- −1.5 -->\n      <g transform=\"translate(20.878125 153.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        <path id=\"DejaVuSans-2e\" d=\"M 684 794 \nL 1344 794 \nL 1344 0 \nL 684 0 \nL 684 794 \nz\n\" transform=\"scale(0.015625)\"/>\n        <path id=\"DejaVuSans-35\" d=\"M 691 4666 \nL 3169 4666 \nL 3169 4134 \nL 1269 4134 \nL 1269 2991 \nQ 1406 3038 1543 3061 \nQ 1681 3084 1819 3084 \nQ 2600 3084 3056 2656 \nQ 3513 2228 3513 1497 \nQ 3513 744 3044 326 \nQ 2575 -91 1722 -91 \nQ 1428 -91 1123 -41 \nQ 819 9 494 109 \nL 494 744 \nQ 775 591 1075 516 \nQ 1375 441 1709 441 \nQ 2250 441 2565 725 \nQ 2881 1009 2881 1497 \nQ 2881 1984 2565 2268 \nQ 2250 2553 1709 2553 \nQ 1456 2553 1204 2497 \nQ 953 2441 691 2322 \nL 691 4666 \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       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(147.412109 0)\"/>\n       <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(179.199219 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_2\">\n     <g id=\"line2d_9\">\n      <path d=\"M 52.160938 126.499219 \nL 247.460938 126.499219 \n\" clip-path=\"url(#p12d81a8d4e)\" 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=\"#m1ed93afae0\" x=\"52.160938\" y=\"126.499219\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_6\">\n      <!-- −1.0 -->\n      <g transform=\"translate(20.878125 130.298438) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-2212\"/>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(83.789062 0)\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(147.412109 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(179.199219 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_3\">\n     <g id=\"line2d_11\">\n      <path d=\"M 52.160938 103.399219 \nL 247.460938 103.399219 \n\" clip-path=\"url(#p12d81a8d4e)\" 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=\"#m1ed93afae0\" x=\"52.160938\" y=\"103.399219\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_7\">\n      <!-- −0.5 -->\n      <g transform=\"translate(20.878125 107.198437) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-2212\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(83.789062 0)\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(147.412109 0)\"/>\n       <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(179.199219 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_4\">\n     <g id=\"line2d_13\">\n      <path d=\"M 52.160938 80.299219 \nL 247.460938 80.299219 \n\" clip-path=\"url(#p12d81a8d4e)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_14\">\n      <g>\n       <use xlink:href=\"#m1ed93afae0\" x=\"52.160938\" y=\"80.299219\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_8\">\n      <!-- 0.0 -->\n      <g transform=\"translate(29.257812 84.098438) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-30\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(95.410156 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_5\">\n     <g id=\"line2d_15\">\n      <path d=\"M 52.160938 57.199219 \nL 247.460938 57.199219 \n\" clip-path=\"url(#p12d81a8d4e)\" 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=\"#m1ed93afae0\" x=\"52.160938\" y=\"57.199219\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_9\">\n      <!-- 0.5 -->\n      <g transform=\"translate(29.257812 60.998437) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-30\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(95.410156 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_6\">\n     <g id=\"line2d_17\">\n      <path d=\"M 52.160938 34.099219 \nL 247.460938 34.099219 \n\" clip-path=\"url(#p12d81a8d4e)\" 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=\"#m1ed93afae0\" x=\"52.160938\" y=\"34.099219\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_10\">\n      <!-- 1.0 -->\n      <g transform=\"translate(29.257812 37.898438) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-31\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(95.410156 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_7\">\n     <g id=\"line2d_19\">\n      <path d=\"M 52.160938 10.999219 \nL 247.460938 10.999219 \n\" clip-path=\"url(#p12d81a8d4e)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_20\">\n      <g>\n       <use xlink:href=\"#m1ed93afae0\" x=\"52.160938\" y=\"10.999219\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_11\">\n      <!-- 1.5 -->\n      <g transform=\"translate(29.257812 14.798438) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-31\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(95.410156 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_12\">\n     <!-- f(x) -->\n     <g transform=\"translate(14.798438 88.920313) 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_21\">\n    <path d=\"M 61.03821 80.299219 \nL 69.519681 93.952252 \nL 74.043132 100.809621 \nL 77.718436 106.003098 \nL 81.111024 110.413939 \nL 84.220897 114.078156 \nL 87.048054 117.056014 \nL 89.592495 119.42285 \nL 92.136936 121.472999 \nL 94.398662 123.016017 \nL 96.660387 124.285793 \nL 98.639397 125.166274 \nL 100.618407 125.826996 \nL 102.597417 126.264724 \nL 104.576427 126.477312 \nL 106.555437 126.46372 \nL 108.534446 126.224015 \nL 110.513456 125.759369 \nL 112.492466 125.072061 \nL 114.471476 124.165454 \nL 116.733202 122.86655 \nL 118.994927 121.29536 \nL 121.256653 119.461935 \nL 123.801094 117.100544 \nL 126.345535 114.441263 \nL 129.172692 111.163387 \nL 132.282565 107.202895 \nL 135.675153 102.513224 \nL 139.633173 96.643132 \nL 144.439339 89.096745 \nL 162.250428 60.687413 \nL 166.208448 55.042092 \nL 169.601036 50.592677 \nL 172.710909 46.887927 \nL 175.538065 43.869352 \nL 178.082507 41.463064 \nL 180.626948 39.371137 \nL 182.888673 37.789303 \nL 185.150399 36.479387 \nL 187.412125 35.449768 \nL 189.391134 34.784005 \nL 191.370144 34.341176 \nL 193.349154 34.12345 \nL 195.328164 34.131892 \nL 197.307174 34.366462 \nL 199.286184 34.82601 \nL 201.265193 35.508286 \nL 203.244203 36.409949 \nL 205.505929 37.703342 \nL 207.767654 39.269203 \nL 210.02938 41.097517 \nL 212.573821 43.453457 \nL 215.118262 46.107647 \nL 217.945419 49.380337 \nL 221.055292 53.335759 \nL 224.44788 58.020725 \nL 228.4059 63.886504 \nL 233.212067 71.429469 \nL 238.583665 80.152058 \nL 238.583665 80.152058 \n\" clip-path=\"url(#p12d81a8d4e)\" style=\"fill: none; stroke: #1f77b4; stroke-width: 1.5; stroke-linecap: square\"/>\n   </g>\n   <g id=\"line2d_22\">\n    <path d=\"M 61.03821 131.748308 \nL 238.583665 111.2249 \nL 238.583665 111.2249 \n\" clip-path=\"url(#p12d81a8d4e)\" style=\"fill: none; stroke-dasharray: 5.55,2.4; stroke-dashoffset: 0; stroke: #bf00bf; stroke-width: 1.5\"/>\n   </g>\n   <g id=\"line2d_23\">\n    <path d=\"M 83.854548 188.155469 \nL 199.606105 -1 \nL 199.606105 -1 \n\" clip-path=\"url(#p12d81a8d4e)\" style=\"fill: none; stroke-dasharray: 9.6,2.4,1.5,2.4; stroke-dashoffset: 0; stroke: #008000; stroke-width: 1.5\"/>\n   </g>\n   <g id=\"line2d_24\">\n    <path d=\"M 148.624122 -1 \nL 238.583665 60.176679 \nL 238.583665 60.176679 \n\" clip-path=\"url(#p12d81a8d4e)\" style=\"fill: none; stroke-dasharray: 1.5,2.475; stroke-dashoffset: 0; stroke: #ff0000; stroke-width: 1.5\"/>\n   </g>\n   <g id=\"patch_3\">\n    <path d=\"M 52.160938 149.599219 \nL 52.160938 10.999219 \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 247.460938 149.599219 \nL 247.460938 10.999219 \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 52.160938 149.599219 \nL 247.460938 149.599219 \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 52.160938 10.999219 \nL 247.460938 10.999219 \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=\"p12d81a8d4e\">\n   <rect x=\"52.160938\" y=\"10.999219\" width=\"195.3\" height=\"138.6\"/>\n  </clipPath>\n </defs>\n</svg>\n"
     },
     "metadata": {}
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-single-variable-calculus-md-5 fw=all -->\n",
    "\n",
    "### The Gradient-Descent Step\n",
    "\n",
    "So far we have *observed* $\\epsilon$; now we get to *choose* it. In the small-change identity the equation the step $\\epsilon$ is ours to pick, and we want to pick it so that $f$ goes *down*. The identity already predicts the effect of any step: a step $\\epsilon$ changes the output by about $\\epsilon\\, f'(x)$. To make that change negative, point the step opposite the slope: take $\\epsilon = -\\eta\\, f'(x)$ for a step size $\\eta > 0$, and, *if the step is not too large*, the descent is guaranteed.\n",
    "\n",
    "The qualification matters. The small-change identity by itself only describes the first-order *model*; turning \"the model goes down\" into \"$f$ really goes down\" needs control on how fast the slope can change over the step, which is exactly the curvature. The standard hypothesis is that $f'$ is **$L$-Lipschitz** near $x$, meaning $|f'(u) - f'(v)| \\le L\\,|u-v|$ for $u,v$ in a neighborhood, so the slope cannot swing by more than $L$ per unit of $x$. (If $f$ is twice differentiable this just says $|f''| \\le L$ there.) Under that single assumption the first-order *guess* becomes a genuine *inequality*, the descent lemma of smooth optimization [@Nesterov.2018].\n",
    "\n",
    "**Proposition (descent lemma).** *Suppose $f'$ is $L$-Lipschitz on a neighborhood of $x$. Then for every step size $\\eta > 0$ small enough that the segment stays in that neighborhood,*\n",
    "\n",
    "$$\n",
    "f\\bigl(x - \\eta\\, f'(x)\\bigr) \\;\\le\\; f(x) - \\eta\\left(1 - \\tfrac{L\\eta}{2}\\right)[f'(x)]^2.\n",
    "$$\n",
    "\n",
    "*In particular $f$ strictly decreases whenever $0 < \\eta < 2/L$ and $f'(x) \\neq 0$, and the guaranteed decrease is largest at the step $\\eta = 1/L$, where the bound reads $f(x - \\tfrac1L f'(x)) \\le f(x) - \\tfrac{1}{2L}[f'(x)]^2$.*\n",
    "\n",
    "**Proof.** Write the exact change in $f$ along the step as an integral of the slope, using the fundamental theorem of calculus (which we take on faith until that section), then add and subtract the slope at the base point:\n",
    "\n",
    "$$\n",
    "f(x+s) - f(x) = \\int_0^1 f'(x + t s)\\, s \\, dt = f'(x)\\, s + \\int_0^1 \\bigl(f'(x + t s) - f'(x)\\bigr) s\\, dt.\n",
    "$$\n",
    "\n",
    "Bounding the remaining integrand with the Lipschitz hypothesis, $|f'(x+ts) - f'(x)| \\le L\\,|ts| = Lt|s|$, and using $\\int_0^1 t\\, dt = \\tfrac12$ gives $f(x+s) \\le f(x) + f'(x)\\,s + \\tfrac{L}{2}s^2$. Now insert the descent step $s = -\\eta\\,f'(x)$:\n",
    "\n",
    "$$\n",
    "f\\bigl(x - \\eta\\, f'(x)\\bigr) \\le f(x) - \\eta\\,[f'(x)]^2 + \\tfrac{L}{2}\\eta^2 [f'(x)]^2 = f(x) - \\eta\\left(1 - \\tfrac{L\\eta}{2}\\right)[f'(x)]^2.\n",
    "$$\n",
    "\n",
    "The bracket $1 - L\\eta/2$ is positive exactly for $\\eta < 2/L$, and as a function of $\\eta$ the whole coefficient $\\eta(1 - L\\eta/2)$ is maximized at $\\eta = 1/L$. $\\blacksquare$\n",
    "\n",
    "the figure turns the proof into a picture. The inequality in its middle, $f(x+s) \\le f(x) + f'(x)\\,s + \\tfrac{L}{2}s^2$, says the Lipschitz hypothesis erects a *quadratic ceiling* over the graph, touching it at the base point. Whatever $f$ does underneath, stepping to the ceiling's minimizer (which is exactly the gradient step with $\\eta = 1/L$, at $s = -f'(x)/L$) lands where even the ceiling has dropped by $\\tfrac{1}{2L}[f'(x)]^2$, so $f$, trapped below it, must have dropped at least as much. The guarantee is a worst-case floor: in the figure the function falls much further than the parabola promises.\n",
    "\n",
    "![With an $L$-Lipschitz slope the function is trapped beneath the quadratic upper bound $f(x) + f'(x)s + \\frac{L}{2}s^2$, which touches the graph at the base point. The gradient step with $\\eta = 1/L$ lands exactly at the parabola's minimizer, where the ceiling, and hence $f$ beneath it, sits at least $\\frac{1}{2L}f'(x)^2$ below the starting value. Here $f(x) = \\sin(2x)$ with $L = 4$: the actual drop far exceeds the guaranteed one, which is the point, since the lemma is a worst-case floor.](../img/mdl-cal-descent-lemma.svg)\n",
    "\n",
    "The leading term $-\\eta\\,[f'(x)]^2$ is the first-order promise of the equation; the new $+\\tfrac{L}{2}\\eta^2[f'(x)]^2$ is the *curvature tax* the model ignored, and the lemma shows the tax stays strictly below the first-order gain as long as $\\eta < 2/L$. The square is still the whole point: *whatever* the sign of the slope, moving against it lowers $f$, by an amount proportional to the slope *squared*, steepest where the function is steepest, vanishing only where $f'(x) = 0$. Iterating the step is **gradient descent**, the one-dimensional version of the loop that trains every network in this book,\n",
    "\n",
    "$$\n",
    "x_{t+1} = x_t - \\eta\\, f'(x_t),\n",
    "$$\n",
    "\n",
    "which is exactly the weight update $\\mathbf{w} \\leftarrow \\mathbf{w} - \\eta\\,\\nabla L(\\mathbf{w})$ from the introduction, one coordinate at a time. the figure shows a single step: stand at $x$, follow the tangent downhill by $-\\eta f'(x)$, and land lower on the curve.\n",
    "\n",
    "![One gradient-descent step on a 1-D bowl. At $x$ the tangent line has slope $f'(x)$; the step $-\\eta f'(x)$ moves opposite the slope and lands at $x - \\eta f'(x)$, lower on the curve, with the drop equal to $\\eta f'(x)^2$ to first order.](../img/mdl-cal-gd-step.svg)\n",
    "\n",
    "Two consequences follow. The descent stalls *exactly* at the **stationary condition** $f'(x) = 0$: the update stops moving and the equation predicts no further decrease, which is why $f'(x) = 0$ is the equation we solve to find candidate minima. And the descent lemma pins down what \"too large a step\" means: the guaranteed decrease holds only for $\\eta < 2/L$, and at $\\eta = 2/L$ the curvature tax exactly cancels the first-order gain. Push $\\eta$ past $2/L$ and the bound flips sign: a single step can overshoot the minimum and *increase* $f$, the failure mode analyzed at length in that section. So the Lipschitz constant $L$ of the slope (the curvature, which the second derivative measures next) is precisely what sets how large $\\eta$ may safely be.\n",
    "\n",
    "We can see all of this on the simplest example, $f(x) = x^2$, whose slope is $f'(x) = 2x$. The gradient-descent step becomes\n",
    "\n",
    "$$\n",
    "x_{t+1} = x_t - \\eta\\,(2x_t) = (1 - 2\\eta)\\, x_t,\n",
    "$$\n",
    "\n",
    "a simple geometric recursion with closed form $x_t = (1-2\\eta)^t x_0$. So the iterates converge to the minimum $x = 0$ exactly when $|1 - 2\\eta| < 1$, i.e. for $0 < \\eta < 1$. This is the descent lemma made exact: here $f'' \\equiv 2$ so $L = 2$ and the safe range $\\eta < 2/L = 1$ is precisely the convergence threshold. Within it, tiny $\\eta$ creeps in monotonically, the optimal $\\eta = 1/L = \\tfrac12$ jumps to the minimum in one step, $\\tfrac12 < \\eta < 1$ overshoots and oscillates inward, $\\eta = 1$ oscillates forever between $\\pm x_0$, and $\\eta > 1$ diverges. The next code cell runs the recursion for a sweep of step sizes, prints where each lands after ten steps, and plots the five trajectories $x_t$."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "single-variable-calculus-gradient-descent"
   },
   "source": [
    "# Gradient descent on f(x) = x^2 from x0 = 1, for several step sizes\n",
    "def gd(eta, steps=10, x0=1.0):\n",
    "    xs = [x0]\n",
    "    for _ in range(steps):\n",
    "        xs.append(xs[-1] - eta * (2 * xs[-1]))  # x <- x - eta * f'(x)\n",
    "    return xs\n",
    "\n",
    "etas = [0.05, 0.5, 0.9, 1.0, 1.1]\n",
    "trajectories = [gd(eta) for eta in etas]\n",
    "for eta, xs in zip(etas, trajectories):\n",
    "    print(f'eta = {eta:.2f} -> x_10 = {xs[-1]:+.5f}')\n",
    "d2l.plot(list(range(11)), trajectories, 'step t', 'x_t', ylim=[-2.5, 2.5],\n",
    "         legend=[f'eta = {eta}' for eta in etas],\n",
    "         fmts=('-', 'm--', 'g-.', 'r:', 'c-'))"
   ],
   "execution_count": 5,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "eta = 0.05 -> x_10 = +0.34868\neta = 0.50 -> x_10 = +0.00000\neta = 0.90 -> x_10 = +0.10737\neta = 1.00 -> x_10 = +1.00000\neta = 1.10 -> x_10 = +6.19174\n"
     ]
    },
    {
     "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=\"245.120313pt\" height=\"183.35625pt\" viewBox=\"0 0 245.120313 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:41:08.280273</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 245.120313 183.35625 \nL 245.120313 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 42.620312 145.8 \nL 237.920313 145.8 \nL 237.920313 7.2 \nL 42.620312 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 51.497585 145.8 \nL 51.497585 7.2 \n\" clip-path=\"url(#p9b631f9f97)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_2\">\n      <defs>\n       <path id=\"m06ccef3087\" d=\"M 0 0 \nL 0 3.5 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m06ccef3087\" x=\"51.497585\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_1\">\n      <!-- 0 -->\n      <g transform=\"translate(48.316335 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_2\">\n     <g id=\"line2d_3\">\n      <path d=\"M 87.006676 145.8 \nL 87.006676 7.2 \n\" clip-path=\"url(#p9b631f9f97)\" 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=\"#m06ccef3087\" x=\"87.006676\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_2\">\n      <!-- 2 -->\n      <g transform=\"translate(83.825426 160.398438) scale(0.1 -0.1)\">\n       <defs>\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-32\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_3\">\n     <g id=\"line2d_5\">\n      <path d=\"M 122.515767 145.8 \nL 122.515767 7.2 \n\" clip-path=\"url(#p9b631f9f97)\" 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=\"#m06ccef3087\" x=\"122.515767\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_3\">\n      <!-- 4 -->\n      <g transform=\"translate(119.334517 160.398438) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-34\" d=\"M 2419 4116 \nL 825 1625 \nL 2419 1625 \nL 2419 4116 \nz\nM 2253 4666 \nL 3047 4666 \nL 3047 1625 \nL 3713 1625 \nL 3713 1100 \nL 3047 1100 \nL 3047 0 \nL 2419 0 \nL 2419 1100 \nL 313 1100 \nL 313 1709 \nL 2253 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-34\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_4\">\n     <g id=\"line2d_7\">\n      <path d=\"M 158.024858 145.8 \nL 158.024858 7.2 \n\" clip-path=\"url(#p9b631f9f97)\" 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=\"#m06ccef3087\" x=\"158.024858\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_4\">\n      <!-- 6 -->\n      <g transform=\"translate(154.843608 160.398438) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-36\" d=\"M 2113 2584 \nQ 1688 2584 1439 2293 \nQ 1191 2003 1191 1497 \nQ 1191 994 1439 701 \nQ 1688 409 2113 409 \nQ 2538 409 2786 701 \nQ 3034 994 3034 1497 \nQ 3034 2003 2786 2293 \nQ 2538 2584 2113 2584 \nz\nM 3366 4563 \nL 3366 3988 \nQ 3128 4100 2886 4159 \nQ 2644 4219 2406 4219 \nQ 1781 4219 1451 3797 \nQ 1122 3375 1075 2522 \nQ 1259 2794 1537 2939 \nQ 1816 3084 2150 3084 \nQ 2853 3084 3261 2657 \nQ 3669 2231 3669 1497 \nQ 3669 778 3244 343 \nQ 2819 -91 2113 -91 \nQ 1303 -91 875 529 \nQ 447 1150 447 2328 \nQ 447 3434 972 4092 \nQ 1497 4750 2381 4750 \nQ 2619 4750 2861 4703 \nQ 3103 4656 3366 4563 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-36\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_5\">\n     <g id=\"line2d_9\">\n      <path d=\"M 193.533949 145.8 \nL 193.533949 7.2 \n\" clip-path=\"url(#p9b631f9f97)\" 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=\"#m06ccef3087\" x=\"193.533949\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_5\">\n      <!-- 8 -->\n      <g transform=\"translate(190.352699 160.398438) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-38\" d=\"M 2034 2216 \nQ 1584 2216 1326 1975 \nQ 1069 1734 1069 1313 \nQ 1069 891 1326 650 \nQ 1584 409 2034 409 \nQ 2484 409 2743 651 \nQ 3003 894 3003 1313 \nQ 3003 1734 2745 1975 \nQ 2488 2216 2034 2216 \nz\nM 1403 2484 \nQ 997 2584 770 2862 \nQ 544 3141 544 3541 \nQ 544 4100 942 4425 \nQ 1341 4750 2034 4750 \nQ 2731 4750 3128 4425 \nQ 3525 4100 3525 3541 \nQ 3525 3141 3298 2862 \nQ 3072 2584 2669 2484 \nQ 3125 2378 3379 2068 \nQ 3634 1759 3634 1313 \nQ 3634 634 3220 271 \nQ 2806 -91 2034 -91 \nQ 1263 -91 848 271 \nQ 434 634 434 1313 \nQ 434 1759 690 2068 \nQ 947 2378 1403 2484 \nz\nM 1172 3481 \nQ 1172 3119 1398 2916 \nQ 1625 2713 2034 2713 \nQ 2441 2713 2670 2916 \nQ 2900 3119 2900 3481 \nQ 2900 3844 2670 4047 \nQ 2441 4250 2034 4250 \nQ 1625 4250 1398 4047 \nQ 1172 3844 1172 3481 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-38\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_6\">\n     <g id=\"line2d_11\">\n      <path d=\"M 229.04304 145.8 \nL 229.04304 7.2 \n\" clip-path=\"url(#p9b631f9f97)\" 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=\"#m06ccef3087\" x=\"229.04304\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_6\">\n      <!-- 10 -->\n      <g transform=\"translate(222.68054 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-31\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_7\">\n     <!-- step t -->\n     <g transform=\"translate(125.905469 174.076563) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-73\" d=\"M 2834 3397 \nL 2834 2853 \nQ 2591 2978 2328 3040 \nQ 2066 3103 1784 3103 \nQ 1356 3103 1142 2972 \nQ 928 2841 928 2578 \nQ 928 2378 1081 2264 \nQ 1234 2150 1697 2047 \nL 1894 2003 \nQ 2506 1872 2764 1633 \nQ 3022 1394 3022 966 \nQ 3022 478 2636 193 \nQ 2250 -91 1575 -91 \nQ 1294 -91 989 -36 \nQ 684 19 347 128 \nL 347 722 \nQ 666 556 975 473 \nQ 1284 391 1588 391 \nQ 1994 391 2212 530 \nQ 2431 669 2431 922 \nQ 2431 1156 2273 1281 \nQ 2116 1406 1581 1522 \nL 1381 1569 \nQ 847 1681 609 1914 \nQ 372 2147 372 2553 \nQ 372 3047 722 3315 \nQ 1072 3584 1716 3584 \nQ 2034 3584 2315 3537 \nQ 2597 3491 2834 3397 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-74\" d=\"M 1172 4494 \nL 1172 3500 \nL 2356 3500 \nL 2356 3053 \nL 1172 3053 \nL 1172 1153 \nQ 1172 725 1289 603 \nQ 1406 481 1766 481 \nL 2356 481 \nL 2356 0 \nL 1766 0 \nQ 1100 0 847 248 \nQ 594 497 594 1153 \nL 594 3053 \nL 172 3053 \nL 172 3500 \nL 594 3500 \nL 594 4494 \nL 1172 4494 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-65\" d=\"M 3597 1894 \nL 3597 1613 \nL 953 1613 \nQ 991 1019 1311 708 \nQ 1631 397 2203 397 \nQ 2534 397 2845 478 \nQ 3156 559 3463 722 \nL 3463 178 \nQ 3153 47 2828 -22 \nQ 2503 -91 2169 -91 \nQ 1331 -91 842 396 \nQ 353 884 353 1716 \nQ 353 2575 817 3079 \nQ 1281 3584 2069 3584 \nQ 2775 3584 3186 3129 \nQ 3597 2675 3597 1894 \nz\nM 3022 2063 \nQ 3016 2534 2758 2815 \nQ 2500 3097 2075 3097 \nQ 1594 3097 1305 2825 \nQ 1016 2553 972 2059 \nL 3022 2063 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-70\" d=\"M 1159 525 \nL 1159 -1331 \nL 581 -1331 \nL 581 3500 \nL 1159 3500 \nL 1159 2969 \nQ 1341 3281 1617 3432 \nQ 1894 3584 2278 3584 \nQ 2916 3584 3314 3078 \nQ 3713 2572 3713 1747 \nQ 3713 922 3314 415 \nQ 2916 -91 2278 -91 \nQ 1894 -91 1617 61 \nQ 1341 213 1159 525 \nz\nM 3116 1747 \nQ 3116 2381 2855 2742 \nQ 2594 3103 2138 3103 \nQ 1681 3103 1420 2742 \nQ 1159 2381 1159 1747 \nQ 1159 1113 1420 752 \nQ 1681 391 2138 391 \nQ 2594 391 2855 752 \nQ 3116 1113 3116 1747 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-20\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-73\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(52.099609 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(91.308594 0)\"/>\n      <use xlink:href=\"#DejaVuSans-70\" transform=\"translate(152.832031 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(216.308594 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(248.095703 0)\"/>\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 42.620312 131.94 \nL 237.920313 131.94 \n\" clip-path=\"url(#p9b631f9f97)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_14\">\n      <defs>\n       <path id=\"mde17d34046\" d=\"M 0 0 \nL -3.5 0 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#mde17d34046\" x=\"42.620312\" y=\"131.94\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_8\">\n      <!-- −2 -->\n      <g transform=\"translate(20.878125 135.739219) 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       </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=\"ytick_2\">\n     <g id=\"line2d_15\">\n      <path d=\"M 42.620312 104.22 \nL 237.920313 104.22 \n\" clip-path=\"url(#p9b631f9f97)\" 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=\"#mde17d34046\" x=\"42.620312\" y=\"104.22\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_9\">\n      <!-- −1 -->\n      <g transform=\"translate(20.878125 108.019219) scale(0.1 -0.1)\">\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=\"ytick_3\">\n     <g id=\"line2d_17\">\n      <path d=\"M 42.620312 76.5 \nL 237.920313 76.5 \n\" clip-path=\"url(#p9b631f9f97)\" 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=\"#mde17d34046\" x=\"42.620312\" y=\"76.5\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_10\">\n      <!-- 0 -->\n      <g transform=\"translate(29.257812 80.299219) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-30\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_4\">\n     <g id=\"line2d_19\">\n      <path d=\"M 42.620312 48.78 \nL 237.920313 48.78 \n\" clip-path=\"url(#p9b631f9f97)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_20\">\n      <g>\n       <use xlink:href=\"#mde17d34046\" x=\"42.620312\" y=\"48.78\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_11\">\n      <!-- 1 -->\n      <g transform=\"translate(29.257812 52.579219) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-31\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_5\">\n     <g id=\"line2d_21\">\n      <path d=\"M 42.620312 21.06 \nL 237.920313 21.06 \n\" clip-path=\"url(#p9b631f9f97)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_22\">\n      <g>\n       <use xlink:href=\"#mde17d34046\" x=\"42.620312\" y=\"21.06\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_12\">\n      <!-- 2 -->\n      <g transform=\"translate(29.257812 24.859219) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-32\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_13\">\n     <!-- x_t -->\n     <g transform=\"translate(14.520312 83.919531) rotate(-90) 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       <path id=\"DejaVuSans-5f\" d=\"M 3263 -1063 \nL 3263 -1509 \nL -63 -1509 \nL -63 -1063 \nL 3263 -1063 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-78\"/>\n      <use xlink:href=\"#DejaVuSans-5f\" transform=\"translate(59.179688 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(109.179688 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"line2d_23\">\n    <path d=\"M 51.497585 48.78 \nL 69.252131 51.552 \nL 87.006676 54.0468 \nL 104.761222 56.29212 \nL 122.515767 58.312908 \nL 140.270312 60.131617 \nL 158.024858 61.768455 \nL 175.779403 63.24161 \nL 193.533949 64.567449 \nL 211.288494 65.760704 \nL 229.04304 66.834634 \n\" clip-path=\"url(#p9b631f9f97)\" style=\"fill: none; stroke: #1f77b4; stroke-width: 1.5; stroke-linecap: square\"/>\n   </g>\n   <g id=\"line2d_24\">\n    <path d=\"M 51.497585 48.78 \nL 69.252131 76.5 \nL 87.006676 76.5 \nL 104.761222 76.5 \nL 122.515767 76.5 \nL 140.270312 76.5 \nL 158.024858 76.5 \nL 175.779403 76.5 \nL 193.533949 76.5 \nL 211.288494 76.5 \nL 229.04304 76.5 \n\" clip-path=\"url(#p9b631f9f97)\" style=\"fill: none; stroke-dasharray: 5.55,2.4; stroke-dashoffset: 0; stroke: #bf00bf; stroke-width: 1.5\"/>\n   </g>\n   <g id=\"line2d_25\">\n    <path d=\"M 51.497585 48.78 \nL 69.252131 98.676 \nL 87.006676 58.7592 \nL 104.761222 90.69264 \nL 122.515767 65.145888 \nL 140.270312 85.58329 \nL 158.024858 69.233368 \nL 175.779403 82.313305 \nL 193.533949 71.849356 \nL 211.288494 80.220515 \nL 229.04304 73.523588 \n\" clip-path=\"url(#p9b631f9f97)\" style=\"fill: none; stroke-dasharray: 9.6,2.4,1.5,2.4; stroke-dashoffset: 0; stroke: #008000; stroke-width: 1.5\"/>\n   </g>\n   <g id=\"line2d_26\">\n    <path d=\"M 51.497585 48.78 \nL 69.252131 104.22 \nL 87.006676 48.78 \nL 104.761222 104.22 \nL 122.515767 48.78 \nL 140.270312 104.22 \nL 158.024858 48.78 \nL 175.779403 104.22 \nL 193.533949 48.78 \nL 211.288494 104.22 \nL 229.04304 48.78 \n\" clip-path=\"url(#p9b631f9f97)\" style=\"fill: none; stroke-dasharray: 1.5,2.475; stroke-dashoffset: 0; stroke: #ff0000; stroke-width: 1.5\"/>\n   </g>\n   <g id=\"line2d_27\">\n    <path d=\"M 51.497585 48.78 \nL 69.252131 109.764 \nL 87.006676 36.5832 \nL 104.761222 124.40016 \nL 122.515767 19.019808 \nL 140.270312 145.47623 \nL 157.408093 -1 \nM 158.538829 -1 \nL 175.779403 175.825772 \nL 190.146549 -1 \nM 196.356782 -1 \nL 208.90699 184.35625 \nM 213.273081 184.35625 \nL 223.731588 -1 \n\" clip-path=\"url(#p9b631f9f97)\" style=\"fill: none; stroke: #00bfbf; stroke-width: 1.5; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_3\">\n    <path d=\"M 42.620312 145.8 \nL 42.620312 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 237.920313 145.8 \nL 237.920313 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 42.620312 145.8 \nL 237.920313 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 42.620312 7.2 \nL 237.920313 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"legend_1\">\n    <g id=\"patch_7\">\n     <path d=\"M 49.620312 140.8 \nL 134.823438 140.8 \nQ 136.823438 140.8 136.823438 138.8 \nL 136.823438 66.409375 \nQ 136.823438 64.409375 134.823438 64.409375 \nL 49.620312 64.409375 \nQ 47.620312 64.409375 47.620312 66.409375 \nL 47.620312 138.8 \nQ 47.620312 140.8 49.620312 140.8 \nz\n\" style=\"fill: #ffffff; opacity: 0.8; stroke: #cccccc; stroke-linejoin: miter\"/>\n    </g>\n    <g id=\"line2d_28\">\n     <path d=\"M 51.620312 72.507813 \nL 61.620312 72.507813 \nL 71.620312 72.507813 \n\" style=\"fill: none; stroke: #1f77b4; stroke-width: 1.5; stroke-linecap: square\"/>\n    </g>\n    <g id=\"text_14\">\n     <!-- eta = 0.05 -->\n     <g transform=\"translate(79.620312 76.007813) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-61\" d=\"M 2194 1759 \nQ 1497 1759 1228 1600 \nQ 959 1441 959 1056 \nQ 959 750 1161 570 \nQ 1363 391 1709 391 \nQ 2188 391 2477 730 \nQ 2766 1069 2766 1631 \nL 2766 1759 \nL 2194 1759 \nz\nM 3341 1997 \nL 3341 0 \nL 2766 0 \nL 2766 531 \nQ 2569 213 2275 61 \nQ 1981 -91 1556 -91 \nQ 1019 -91 701 211 \nQ 384 513 384 1019 \nQ 384 1609 779 1909 \nQ 1175 2209 1959 2209 \nL 2766 2209 \nL 2766 2266 \nQ 2766 2663 2505 2880 \nQ 2244 3097 1772 3097 \nQ 1472 3097 1187 3025 \nQ 903 2953 641 2809 \nL 641 3341 \nQ 956 3463 1253 3523 \nQ 1550 3584 1831 3584 \nQ 2591 3584 2966 3190 \nQ 3341 2797 3341 1997 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-3d\" d=\"M 678 2906 \nL 4684 2906 \nL 4684 2381 \nL 678 2381 \nL 678 2906 \nz\nM 678 1631 \nL 4684 1631 \nL 4684 1100 \nL 678 1100 \nL 678 1631 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-2e\" d=\"M 684 794 \nL 1344 794 \nL 1344 0 \nL 684 0 \nL 684 794 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-35\" d=\"M 691 4666 \nL 3169 4666 \nL 3169 4134 \nL 1269 4134 \nL 1269 2991 \nQ 1406 3038 1543 3061 \nQ 1681 3084 1819 3084 \nQ 2600 3084 3056 2656 \nQ 3513 2228 3513 1497 \nQ 3513 744 3044 326 \nQ 2575 -91 1722 -91 \nQ 1428 -91 1123 -41 \nQ 819 9 494 109 \nL 494 744 \nQ 775 591 1075 516 \nQ 1375 441 1709 441 \nQ 2250 441 2565 725 \nQ 2881 1009 2881 1497 \nQ 2881 1984 2565 2268 \nQ 2250 2553 1709 2553 \nQ 1456 2553 1204 2497 \nQ 953 2441 691 2322 \nL 691 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-65\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(61.523438 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(100.732422 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(162.011719 0)\"/>\n      <use xlink:href=\"#DejaVuSans-3d\" transform=\"translate(193.798828 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(277.587891 0)\"/>\n      <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(309.375 0)\"/>\n      <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(372.998047 0)\"/>\n      <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(404.785156 0)\"/>\n      <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(468.408203 0)\"/>\n     </g>\n    </g>\n    <g id=\"line2d_29\">\n     <path d=\"M 51.620312 87.185938 \nL 61.620312 87.185938 \nL 71.620312 87.185938 \n\" style=\"fill: none; stroke-dasharray: 5.55,2.4; stroke-dashoffset: 0; stroke: #bf00bf; stroke-width: 1.5\"/>\n    </g>\n    <g id=\"text_15\">\n     <!-- eta = 0.5 -->\n     <g transform=\"translate(79.620312 90.685938) scale(0.1 -0.1)\">\n      <use xlink:href=\"#DejaVuSans-65\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(61.523438 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(100.732422 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(162.011719 0)\"/>\n      <use xlink:href=\"#DejaVuSans-3d\" transform=\"translate(193.798828 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(277.587891 0)\"/>\n      <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(309.375 0)\"/>\n      <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(372.998047 0)\"/>\n      <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(404.785156 0)\"/>\n     </g>\n    </g>\n    <g id=\"line2d_30\">\n     <path d=\"M 51.620312 101.864063 \nL 61.620312 101.864063 \nL 71.620312 101.864063 \n\" style=\"fill: none; stroke-dasharray: 9.6,2.4,1.5,2.4; stroke-dashoffset: 0; stroke: #008000; stroke-width: 1.5\"/>\n    </g>\n    <g id=\"text_16\">\n     <!-- eta = 0.9 -->\n     <g transform=\"translate(79.620312 105.364063) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-39\" d=\"M 703 97 \nL 703 672 \nQ 941 559 1184 500 \nQ 1428 441 1663 441 \nQ 2288 441 2617 861 \nQ 2947 1281 2994 2138 \nQ 2813 1869 2534 1725 \nQ 2256 1581 1919 1581 \nQ 1219 1581 811 2004 \nQ 403 2428 403 3163 \nQ 403 3881 828 4315 \nQ 1253 4750 1959 4750 \nQ 2769 4750 3195 4129 \nQ 3622 3509 3622 2328 \nQ 3622 1225 3098 567 \nQ 2575 -91 1691 -91 \nQ 1453 -91 1209 -44 \nQ 966 3 703 97 \nz\nM 1959 2075 \nQ 2384 2075 2632 2365 \nQ 2881 2656 2881 3163 \nQ 2881 3666 2632 3958 \nQ 2384 4250 1959 4250 \nQ 1534 4250 1286 3958 \nQ 1038 3666 1038 3163 \nQ 1038 2656 1286 2365 \nQ 1534 2075 1959 2075 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-65\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(61.523438 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(100.732422 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(162.011719 0)\"/>\n      <use xlink:href=\"#DejaVuSans-3d\" transform=\"translate(193.798828 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(277.587891 0)\"/>\n      <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(309.375 0)\"/>\n      <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(372.998047 0)\"/>\n      <use xlink:href=\"#DejaVuSans-39\" transform=\"translate(404.785156 0)\"/>\n     </g>\n    </g>\n    <g id=\"line2d_31\">\n     <path d=\"M 51.620312 116.542188 \nL 61.620312 116.542188 \nL 71.620312 116.542188 \n\" style=\"fill: none; stroke-dasharray: 1.5,2.475; stroke-dashoffset: 0; stroke: #ff0000; stroke-width: 1.5\"/>\n    </g>\n    <g id=\"text_17\">\n     <!-- eta = 1.0 -->\n     <g transform=\"translate(79.620312 120.042188) scale(0.1 -0.1)\">\n      <use xlink:href=\"#DejaVuSans-65\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(61.523438 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(100.732422 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(162.011719 0)\"/>\n      <use xlink:href=\"#DejaVuSans-3d\" transform=\"translate(193.798828 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(277.587891 0)\"/>\n      <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(309.375 0)\"/>\n      <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(372.998047 0)\"/>\n      <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(404.785156 0)\"/>\n     </g>\n    </g>\n    <g id=\"line2d_32\">\n     <path d=\"M 51.620312 131.220313 \nL 61.620312 131.220313 \nL 71.620312 131.220313 \n\" style=\"fill: none; stroke: #00bfbf; stroke-width: 1.5; stroke-linecap: square\"/>\n    </g>\n    <g id=\"text_18\">\n     <!-- eta = 1.1 -->\n     <g transform=\"translate(79.620312 134.720313) scale(0.1 -0.1)\">\n      <use xlink:href=\"#DejaVuSans-65\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(61.523438 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(100.732422 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(162.011719 0)\"/>\n      <use xlink:href=\"#DejaVuSans-3d\" transform=\"translate(193.798828 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(277.587891 0)\"/>\n      <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(309.375 0)\"/>\n      <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(372.998047 0)\"/>\n      <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(404.785156 0)\"/>\n     </g>\n    </g>\n   </g>\n  </g>\n </g>\n <defs>\n  <clipPath id=\"p9b631f9f97\">\n   <rect x=\"42.620312\" 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-single-variable-calculus-md-6 fw=all -->\n",
    "\n",
    "The printout and the picture tell the same story, one regime per curve: $\\eta = 0.05$ creeps toward $0$ monotonically, $\\eta = 0.5$ lands on it in a single step, $\\eta = 0.9$ converges while zig-zagging across the minimum, $\\eta = 1.0$ bounces between $\\pm 1$ forever, and $\\eta = 1.1$ oscillates with *growing* amplitude: it has left the plotting window within a handful of steps and reaches $|x_{10}| \\approx 6.2$. The threshold $\\eta = 2/L$ separating the last two regimes is exactly where the descent lemma's guarantee expires.\n",
    "\n",
    "## Curvature and Taylor Series\n",
    "\n",
    "The first derivative gave us the best *line* through a point. Its own derivative, the second derivative, measures how the slope itself bends, which is what distinguishes a minimum from a maximum and what limited the step size above. Pushing the idea to higher derivatives yields the *Taylor series*, the best polynomial model of a function.\n",
    "\n",
    "### Higher-Order Derivatives and Curvature\n",
    "\n",
    "The derivative $\\frac{df}{dx}$ is itself a function, so nothing stops us from differentiating it again. Doing so yields the *second derivative*, $\\frac{d^2f}{dx^2} = \\frac{d}{dx}\\!\\left(\\frac{df}{dx}\\right)$: the derivative *operator* applied twice, **not** the square of $\\frac{df}{dx}$. It is the rate of change of the rate of change: how the slope itself is changing. Repeating gives the $n$-th derivative,\n",
    "\n",
    "$$\n",
    "f^{(n)}(x) = \\frac{d^{n}f}{dx^{n}} = \\left(\\frac{d}{dx}\\right)^{n} f.\n",
    "$$\n",
    "\n",
    "What does the second derivative *tell* us? Its **sign** is the direction the curve bends, and read *locally* this is the classifier we need for optimization. Suppose $x_0$ is a stationary point, $f'(x_0) = 0$. Then the definition of the second derivative collapses to $f''(x_0) = \\lim_{h \\to 0} f'(x_0+h)/h$; if that limit is positive, the quotient $f'(x_0+h)/h$ is positive for all small $h \\neq 0$, so $f'(x_0+h)$ shares the sign of $h$: just left of $x_0$ the slope is negative ($f$ falling), just right of $x_0$ it is positive ($f$ rising). The function dips and turns back up, so $x_0$ is a **local minimum**. Symmetrically, $f''(x_0) < 0$ makes the slope positive then negative, so $f$ rises and turns back down and $x_0$ is a **local maximum**. This is the **second-derivative test**, and it certifies *only the neighborhood* of $x_0$, not the whole function; the global picture, when $f$ is convex, is the subject of that section.\n",
    "\n",
    "The three constant-curvature functions show what each sign *means*, even though most functions have a varying $f''$. A positive constant $f''$ keeps the slope increasing everywhere, so $f'$ runs from negative through zero to positive and the graph is a single upward bowl (the figure), exactly the bowl that gradient descent rolls into.\n",
    "\n",
    "![A constant positive second derivative keeps the first derivative increasing, so the function curves upward; near a point where the slope crosses zero this is the local-minimum shape of the second-derivative test.](../img/mdl-cal-pos-second.svg)\n",
    "\n",
    "A negative constant $f''$ keeps the slope decreasing, running from positive through zero to negative: the upward dome of a maximum (the figure).\n",
    "\n",
    "![A constant negative second derivative keeps the first derivative decreasing, so the function curves downward into the local-maximum shape.](../img/mdl-cal-neg-second.svg)\n",
    "\n",
    "And a zero $f''$ leaves the slope unchanged: $f$ rises or falls at a fixed rate and is a straight **line** with no curvature at all (the figure), the borderline the test cannot decide.\n",
    "\n",
    "![A zero second derivative keeps the first derivative constant, so the function is a straight line: no curvature, and the borderline case where the second-derivative test is inconclusive.](../img/mdl-cal-zero-second.svg)\n",
    "\n",
    "In short, the *sign* of the second derivative at a stationary point decides minimum versus maximum: positive curves up into a min, negative curves down into a max, zero is undecided. (This is the one-dimensional shadow of the Hessian eigenvalue test for many variables in that section.)\n",
    "\n",
    "### The Mean Value Theorem\n",
    "\n",
    "We have been spending the derivative freely: a vanishing slope marks a candidate extremum, a negative slope means the function is falling. Both deductions read information about $f$ *itself* off its derivative at single points, and the one theorem that licenses every such reading is the **Mean Value Theorem**. Its statement is a picture (the figure): draw the secant chord joining the endpoints of the graph over $[a,b]$; somewhere inside, the tangent runs *parallel* to it. The average rate of change is achieved exactly, as an instantaneous rate, at some interior point.\n",
    "\n",
    "![Over the interval from $a$ to $b$, the secant chord through the endpoints has slope equal to the average rate of change; the Mean Value Theorem says some interior point $\\xi$ has a tangent of that same slope, parallel to the chord.](../img/mdl-cal-mvt.svg)\n",
    "\n",
    "**Proposition (Mean Value Theorem).** *If $f$ is continuous on $[a,b]$ and differentiable on $(a,b)$, then there is a point $\\xi \\in (a,b)$ with*\n",
    "\n",
    "$$\n",
    "f'(\\xi) = \\frac{f(b) - f(a)}{b - a}.\n",
    "$$\n",
    "\n",
    "**Proof.** First take the flat case $f(a) = f(b)$ (Rolle's theorem). We grant ourselves one fact from real analysis, the **extreme value theorem**: a continuous function on a closed interval attains a maximum and a minimum [@Rudin.1976]. If both occur at the endpoints then $f$ is constant and $f' \\equiv 0$ inside; otherwise an extremum sits at some interior $\\xi$, say a maximum, so $f(\\xi + \\epsilon) - f(\\xi) \\le 0$ on both sides. The difference quotient is then $\\le 0$ for $\\epsilon > 0$ and $\\ge 0$ for $\\epsilon < 0$, and since $f$ is differentiable at $\\xi$ both one-sided limits equal $f'(\\xi)$; a number that is both $\\le 0$ and $\\ge 0$ is zero, so $f'(\\xi) = 0$ (a minimum is symmetric). For the general case, subtract off the chord: the tilted function $g(x) = f(x) - \\frac{f(b)-f(a)}{b-a}(x - a)$ has $g(a) = g(b) = f(a)$, so the flat case gives a $\\xi$ with $g'(\\xi) = 0$, which is exactly the equation. $\\blacksquare$\n",
    "\n",
    "Two corollaries are the facts we already used. If $f' > 0$ throughout an interval then for any $x_1 < x_2$ in it, the equation gives $f(x_2) - f(x_1) = f'(\\xi)(x_2 - x_1) > 0$ for some $\\xi$ between them, so $f$ is **increasing**: a positive slope really does mean the function climbs, and the sign of $f'$ governs monotonicity. And if $f$ has a *constant* sign of $f'$ on each side of a stationary point, the theorem turns that into the rise-and-fall behaviour the second-derivative test read off. The Mean Value Theorem is the formal bridge from *the derivative at a point* to *the behaviour of the function on an interval*.\n",
    "\n",
    "### The Best Quadratic, and the Taylor Idea\n",
    "\n",
    "The first derivative built the best line; the second lets us build the best *parabola*. Consider a generic quadratic $g(x) = ax^2 + bx + c$, for which\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\frac{dg}{dx}(x) & = 2ax + b \\\\\n",
    "\\frac{d^2g}{dx^2}(x) & = 2a.\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "A quadratic has three free coefficients, so we can match three pieces of information about $f$ at a base point $x_0$: its value, slope, and curvature. Demanding $g(x_0) = f(x_0)$, $g'(x_0) = f'(x_0)$, and $g''(x_0) = f''(x_0)$ pins down $a$, $b$, $c$ uniquely and produces the best local *quadratic* model, just as the tangent was the best local *line*. For $f(x) = \\sin(x)$ at base point $x_0$, using $\\frac{d}{dx}\\sin(x) = \\cos(x)$ and $\\frac{d^2}{dx^2}\\sin(x) = -\\sin(x)$, the model reads\n",
    "\n",
    "$$\n",
    "g(x) = \\sin(x_0) + \\cos(x_0)\\,(x - x_0) - \\tfrac{1}{2}\\sin(x_0)\\,(x-x_0)^2,\n",
    "$$\n",
    "\n",
    "a parabola that hugs the curve over a visibly wider window than the tangent lines we plotted above, because it captures curvature as well as slope; the figure draws all three together. We will make the \"wider window\" claim quantitative, and verify it in code, once the Taylor remainder is on the table. But first, the quadratic model changes how we optimize.\n",
    "\n",
    "![The sine curve with its two local models at $x_0$: the tangent line matches value and slope, while the best parabola also matches curvature and stays close over a wider window before peeling away.](../img/mdl-cal-best-parabola.svg)\n",
    "\n",
    "### Newton's Method\n",
    "\n",
    "The best quadratic is a better *optimizer*. Gradient descent treats the local model as a line, and a line has no minimum, so we had to be told how far to walk down it by the step size $\\eta$. The quadratic model has a minimum of its own, and we can simply jump there. Writing the model at the current iterate $x_t$ (with $f''(x_t) > 0$ so it opens upward),\n",
    "\n",
    "$$\n",
    "q(x) = f(x_t) + f'(x_t)\\,(x - x_t) + \\tfrac{1}{2}f''(x_t)\\,(x - x_t)^2,\n",
    "$$\n",
    "\n",
    "and solving $q'(x) = f'(x_t) + f''(x_t)(x - x_t) = 0$ for $x$ gives the update of **Newton's method**:\n",
    "\n",
    "$$\n",
    "x_{t+1} = x_t - \\frac{f'(x_t)}{f''(x_t)}.\n",
    "$$\n",
    "\n",
    "Read against the gradient-descent loop the equation, this is the same step with the hand-tuned $\\eta$ replaced by the *curvature-adapted* step size $1/f''(x_t)$: sharp curvature prescribes caution, gentle curvature boldness. On $f(x) = x^2$ it sets $\\eta = 1/f'' = \\tfrac12$, exactly the one-shot optimal step we found by hand. Its speed in general is a theorem we state without proof: if $f''$ is Lipschitz near a local minimizer $x^\\star$ with $f''(x^\\star) > 0$, and the iteration starts close enough to $x^\\star$, then it converges *quadratically*, roughly doubling the number of correct digits per step [@Nocedal.Wright.2006]. The price is the curvature itself: where $f''(x_t) \\le 0$ the model's \"minimum\" is a maximum or does not exist and the raw step must be safeguarded, and in $n$ dimensions $f''$ becomes the Hessian matrix, so each step requires solving an $n \\times n$ linear system. How this trade plays out at deep-learning scale, and why first-order methods win there anyway, is taken up in that section.\n",
    "\n",
    "The quadratic convergence is easy to watch. Take $f(x) = \\tfrac14 x^4 - x$, whose stationarity condition $f'(x) = x^3 - 1 = 0$ has the root $x^* = 1$; the next cell iterates the equation from $x_0 = 2$ and prints the error at each step."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "mdl-single-variable-calculus-newton-s-method"
   },
   "source": [
    "# Newton's method on f(x) = x^4/4 - x: solve f'(x) = x^3 - 1 = 0, root x* = 1\n",
    "x = 2.0\n",
    "for t in range(6):\n",
    "    print(f't = {t}: x = {x:.12f}, error = {abs(x - 1):.1e}')\n",
    "    x = x - (x**3 - 1) / (3 * x**2)  # x - f'(x) / f''(x)"
   ],
   "execution_count": 6,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "t = 0: x = 2.000000000000, error = 1.0e+00\nt = 1: x = 1.416666666667, error = 4.2e-01\nt = 2: x = 1.110534409842, error = 1.1e-01\nt = 3: x = 1.010636768405, error = 1.1e-02\nt = 4: x = 1.000111557304, error = 1.1e-04\nt = 5: x = 1.000000012443, error = 1.2e-08\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-single-variable-calculus-md-7 fw=all -->\n",
    "\n",
    "Read the error column's exponents: after a couple of settling-in steps they go $10^{-2} \\to 10^{-4} \\to 10^{-8}$: each step roughly *squares* the previous error, doubling the number of correct digits. Contrast the $\\eta$-sweep above, where gradient descent shrinks the error by the same fixed factor $|1 - 2\\eta|$ every step: geometric convergence gains a fixed number of digits per step, Newton doubles them. Matching yet *more* derivatives with higher-degree polynomials is the Taylor series, to which we now turn.\n",
    "\n",
    "### Taylor Series\n",
    "\n",
    "The *Taylor series* generalizes the tangent and the best parabola: given the value and first $n$ derivatives of $f$ at a base point $x_0$, find the degree-$n$ polynomial that matches all of them. The quadratic case, rewritten in displacement from $x_0$, is\n",
    "\n",
    "$$\n",
    "f(x) \\approx f(x_0) + \\frac{df}{dx}(x_0)(x-x_0) + \\frac{1}{2}\\frac{d^2f}{dx^2}(x_0)(x-x_0)^{2}.\n",
    "$$\n",
    "\n",
    "The factor $\\tfrac12$ is bookkeeping: differentiating $(x-x_0)^2$ twice produces a $2$, and dividing by $2$ leaves the coefficient equal to $f''(x_0)$, while all lower terms differentiate to zero at $x_0$. The same accounting at degree $3$ produces a $3! = 6$,\n",
    "\n",
    "$$\n",
    "f(x) \\approx f(x_0) + \\frac{df}{dx}(x_0)(x-x_0) + \\frac{\\frac{d^2f}{dx^2}(x_0)}{2}(x-x_0)^{2} + \\frac{\\frac{d^3f}{dx^3}(x_0)}{6}(x-x_0)^3,\n",
    "$$\n",
    "\n",
    "and in general the $i$-th term carries an $i!$, giving the degree-$n$ **Taylor polynomial**\n",
    "\n",
    "$$\n",
    "P_n(x) = \\sum_{i = 0}^{n} \\frac{f^{(i)}(x_0)}{i!}(x-x_0)^{i},\n",
    "$$\n",
    "\n",
    "the best degree-$n$ polynomial approximation to $f$ near $x_0$.\n",
    "\n",
    "How good is it? The machinery of the Mean Value Theorem answers exactly.\n",
    "\n",
    "**Proposition (Lagrange remainder).** *If $f$ is $(n+1)$-times differentiable on an open interval containing $x_0$ and $x$, then*\n",
    "\n",
    "$$\n",
    "f(x) = P_n(x) + R_n(x), \\qquad R_n(x) = \\frac{f^{(n+1)}(\\xi)}{(n+1)!}\\,(x - x_0)^{n+1},\n",
    "$$\n",
    "\n",
    "*for some $\\xi$ strictly between $x_0$ and $x$. The case $n = 0$ is the Mean Value Theorem the equation itself, $f(x) = f(x_0) + f'(\\xi)(x - x_0)$.*\n",
    "\n",
    "**Proof.** Fix $x \\neq x_0$ and make the *base point* the variable: for $t$ between $x_0$ and $x$, let\n",
    "\n",
    "$$\n",
    "G(t) = f(x) - \\sum_{k=0}^{n} \\frac{f^{(k)}(t)}{k!}\\,(x-t)^k - M\\,\\frac{(x-t)^{n+1}}{(n+1)!},\n",
    "$$\n",
    "\n",
    "where the constant $M$ is chosen so that $G(x_0) = 0$. Since $G(x_0) = f(x) - P_n(x) - M\\,(x-x_0)^{n+1}/(n+1)!$, the claim the equation is exactly that this $M$ equals $f^{(n+1)}(\\xi)$ for some interior $\\xi$. We also have $G(x) = 0$: at $t = x$ every power of $(x - t)$ vanishes and the $k = 0$ term leaves $f(x) - f(x)$. Because $f$ is $(n+1)$-times differentiable, $G$ is differentiable between $x_0$ and $x$, so Rolle's theorem (the flat case established in that section) gives a $\\xi$ strictly between $x_0$ and $x$ with $G'(\\xi) = 0$. Now differentiate $G$ in $t$. By the product rule, the $k$-th summand contributes $\\frac{f^{(k+1)}(t)}{k!}(x-t)^k - \\frac{f^{(k)}(t)}{(k-1)!}(x-t)^{k-1}$ for $k \\ge 1$, and the $k = 0$ term contributes $f'(t)$; the second half of each summand cancels the first half of the one before it, so the sum telescopes to its last surviving piece, $\\frac{f^{(n+1)}(t)}{n!}(x-t)^n$. Hence\n",
    "\n",
    "$$\n",
    "G'(t) = -\\frac{f^{(n+1)}(t)}{n!}\\,(x-t)^n + M\\,\\frac{(x-t)^n}{n!},\n",
    "$$\n",
    "\n",
    "and setting $t = \\xi$, where $(x - \\xi)^n \\neq 0$, forces $M = f^{(n+1)}(\\xi)$. $\\blacksquare$\n",
    "\n",
    "The remainder is one term *past* the polynomial, evaluated at an unknown interior $\\xi$ instead of at $x_0$. It makes \"the approximation improves near $x_0$\" quantitative: the error shrinks like $|x - x_0|^{n+1}$, so each extra matched derivative adds another power of closeness. The case $n = 1$ is the curvature tax we already met ($R_1 = \\tfrac12 f''(\\xi)(x-x_0)^2$ is exactly the $\\tfrac{L}{2}\\eta^2$ term bounded in the descent lemma the equation), and the same quadratic remainder is what Newton's method (that section) drives to zero by stepping to the minimum of $P_2$ rather than $P_1$.\n",
    "\n",
    "That rate is checkable, and checking it is the promised quantitative version of the \"wider window\" claim from the figure. The next cell takes $f(x) = e^x$ at $x_0 = 0$, measures the worst error of $P_n$ over a window $|x| \\le h$, and then halves the window: if the error scales like $h^{n+1}$, halving $h$ should divide it by $2^{n+1}$, i.e. by $4$ for the tangent line, $8$ for the best quadratic, $16$ for the cubic."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "single-variable-calculus-taylor-error-rate"
   },
   "source": [
    "# Max error of the degree-n Taylor polynomial of e^x on the window |x| <= h.\n",
    "# Lagrange predicts error ~ h^(n+1): halving h should divide it by 2^(n+1)\n",
    "def taylor_error(n, h, m=1000):\n",
    "    coeffs = [1.0, 1.0, 1 / 2, 1 / 6]  # 1/k! for k = 0, ..., 3\n",
    "    err = 0.0\n",
    "    for i in range(-m, m + 1):\n",
    "        x = h * i / m\n",
    "        err = max(err, abs(math.exp(x) - sum(coeffs[k] * x**k\n",
    "                                             for k in range(n + 1))))\n",
    "    return err\n",
    "\n",
    "for n in [1, 2, 3]:\n",
    "    e1, e2 = taylor_error(n, 0.2), taylor_error(n, 0.1)\n",
    "    print(f'n = {n}: max error {e1:.1e} (h = 0.2) vs {e2:.1e} (h = 0.1), '\n",
    "          f'ratio = {e1 / e2:.1f}, prediction 2^{n + 1} = {2**(n + 1)}')"
   ],
   "execution_count": 7,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "n = 1: max error 2.1e-02 (h = 0.2) vs 5.2e-03 (h = 0.1), ratio = 4.1, prediction 2^2 = 4\nn = 2: max error 1.4e-03 (h = 0.2) vs 1.7e-04 (h = 0.1), ratio = 8.2, prediction 2^3 = 8\nn = 3: max error 6.9e-05 (h = 0.2) vs 4.3e-06 (h = 0.1), ratio = 16.3, prediction 2^4 = 16\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-single-variable-calculus-md-8 fw=all -->\n",
    "\n",
    "The measured ratios $4.1$, $8.2$, $16.3$ sit right on the predicted $4$, $8$, $16$: the tangent line's error falls fourfold per halving while the cubic's falls sixteenfold, the wider-window effect measured. (The slight overshoot is also predicted: the remainder's $e^{\\xi}$ factor is a touch larger over the wider window.)\n",
    "\n",
    "Letting $n \\to \\infty$ gives the full *Taylor series*. Call $f$ **real analytic** at $x_0$ if its Taylor series there converges on a neighborhood of $x_0$ *and* its sum equals $f$ throughout that neighborhood. For such functions, $\\cos(x)$ and $e^{x}$ among them, the infinitely many terms reproduce the function exactly:\n",
    "\n",
    "$$\n",
    "f(x) = \\sum_{n = 0}^\\infty \\frac{f^{(n)}(x_0)}{n!}(x-x_0)^{n}.\n",
    "$$\n",
    "\n",
    "Two separate things can go wrong, which is why the definition demands both. The series can fail to converge away from $x_0$; and even where it converges, its sum can differ from $f$, since convergence of the series is not the same as convergence *to $f$*. Being infinitely differentiable (smooth) guarantees neither. The classic counterexample is $f(x) = e^{-1/x^2}$ (with $f(0) = 0$), which is smooth everywhere yet has $f^{(n)}(0) = 0$ for every $n$; its Taylor series at $x_0 = 0$ is identically zero: it converges on the *whole line*, but to the zero function, reproducing $f$ only at $x = 0$ itself (the figure). So an infinite radius of convergence guarantees nothing about agreement with $f$. In practice we mostly use the *finite* truncations $P_n$, whose error the equation we can bound directly, and which sharpen the closer $x$ is to $x_0$.\n",
    "\n",
    "![The smooth function $f(x) = e^{-1/x^2}$ has every derivative equal to zero at the origin, so its Taylor series there is identically zero. The series converges everywhere yet agrees with $f$ only at $x = 0$: smooth does not imply analytic.](../img/mdl-cal-smooth-not-analytic.svg)\n",
    "\n",
    "Take $f(x) = e^{x}$ as an example. Since $e^{x}$ is its own derivative, we know that $f^{(n)}(x) = e^{x}$. Therefore, $e^{x}$ can be reconstructed by taking the Taylor series at $x_0 = 0$, i.e.,\n",
    "\n",
    "$$\n",
    "e^{x} = \\sum_{n = 0}^\\infty \\frac{x^{n}}{n!} = 1 + x + \\frac{x^2}{2} + \\frac{x^3}{6} + \\cdots.\n",
    "$$\n",
    "\n",
    "Plotting $P_1$, $P_2$, and $P_5$ against $e^x$ shows each higher degree tracking the curve farther from the base point."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "single-variable-calculus-taylor-series"
   },
   "source": [
    "# This calculation is backend-neutral, so one NumPy cell serves every tab.\n",
    "xs = onp.arange(0, 3, 0.01)\n",
    "ys = onp.exp(xs)\n",
    "P1 = 1 + xs\n",
    "P2 = 1 + xs + xs**2 / 2\n",
    "P5 = 1 + xs + xs**2 / 2 + xs**3 / 6 + xs**4 / 24 + xs**5 / 120\n",
    "\n",
    "d2l.plot(xs, [ys, P1, P2, P5], 'x', 'f(x)', legend=[\n",
    "    \"Exponential\", \"Degree 1 Taylor Series\", \"Degree 2 Taylor Series\",\n",
    "    \"Degree 5 Taylor Series\"])"
   ],
   "execution_count": 8,
   "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=\"243.103125pt\" height=\"183.35625pt\" viewBox=\"0 0 243.103125 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:41:08.447425</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 243.103125 183.35625 \nL 243.103125 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 40.603125 145.8 \nL 235.903125 145.8 \nL 235.903125 7.2 \nL 40.603125 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 49.480398 145.8 \nL 49.480398 7.2 \n\" clip-path=\"url(#p06fc2111a4)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_2\">\n      <defs>\n       <path id=\"m5b3b41b35a\" d=\"M 0 0 \nL 0 3.5 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m5b3b41b35a\" x=\"49.480398\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_1\">\n      <!-- 0 -->\n      <g transform=\"translate(46.299148 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_2\">\n     <g id=\"line2d_3\">\n      <path d=\"M 108.860148 145.8 \nL 108.860148 7.2 \n\" clip-path=\"url(#p06fc2111a4)\" 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=\"#m5b3b41b35a\" x=\"108.860148\" 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(105.678898 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-31\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_3\">\n     <g id=\"line2d_5\">\n      <path d=\"M 168.239899 145.8 \nL 168.239899 7.2 \n\" clip-path=\"url(#p06fc2111a4)\" 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=\"#m5b3b41b35a\" x=\"168.239899\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_3\">\n      <!-- 2 -->\n      <g transform=\"translate(165.058649 160.398438) scale(0.1 -0.1)\">\n       <defs>\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-32\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_4\">\n     <g id=\"line2d_7\">\n      <path d=\"M 227.61965 145.8 \nL 227.61965 7.2 \n\" clip-path=\"url(#p06fc2111a4)\" 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=\"#m5b3b41b35a\" x=\"227.61965\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_4\">\n      <!-- 3 -->\n      <g transform=\"translate(224.4384 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_5\">\n     <!-- x -->\n     <g transform=\"translate(135.29375 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_9\">\n      <path d=\"M 40.603125 112.813117 \nL 235.903125 112.813117 \n\" clip-path=\"url(#p06fc2111a4)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_10\">\n      <defs>\n       <path id=\"m9f4305e7a5\" d=\"M 0 0 \nL -3.5 0 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m9f4305e7a5\" x=\"40.603125\" y=\"112.813117\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_6\">\n      <!-- 5 -->\n      <g transform=\"translate(27.240625 116.612336) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-35\" d=\"M 691 4666 \nL 3169 4666 \nL 3169 4134 \nL 1269 4134 \nL 1269 2991 \nQ 1406 3038 1543 3061 \nQ 1681 3084 1819 3084 \nQ 2600 3084 3056 2656 \nQ 3513 2228 3513 1497 \nQ 3513 744 3044 326 \nQ 2575 -91 1722 -91 \nQ 1428 -91 1123 -41 \nQ 819 9 494 109 \nL 494 744 \nQ 775 591 1075 516 \nQ 1375 441 1709 441 \nQ 2250 441 2565 725 \nQ 2881 1009 2881 1497 \nQ 2881 1984 2565 2268 \nQ 2250 2553 1709 2553 \nQ 1456 2553 1204 2497 \nQ 953 2441 691 2322 \nL 691 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-35\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_2\">\n     <g id=\"line2d_11\">\n      <path d=\"M 40.603125 79.454513 \nL 235.903125 79.454513 \n\" clip-path=\"url(#p06fc2111a4)\" 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=\"#m9f4305e7a5\" x=\"40.603125\" y=\"79.454513\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_7\">\n      <!-- 10 -->\n      <g transform=\"translate(20.878125 83.253732) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-31\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_3\">\n     <g id=\"line2d_13\">\n      <path d=\"M 40.603125 46.095909 \nL 235.903125 46.095909 \n\" clip-path=\"url(#p06fc2111a4)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_14\">\n      <g>\n       <use xlink:href=\"#m9f4305e7a5\" x=\"40.603125\" y=\"46.095909\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_8\">\n      <!-- 15 -->\n      <g transform=\"translate(20.878125 49.895128) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-31\"/>\n       <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(63.623047 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_4\">\n     <g id=\"line2d_15\">\n      <path d=\"M 40.603125 12.737306 \nL 235.903125 12.737306 \n\" clip-path=\"url(#p06fc2111a4)\" 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=\"#m9f4305e7a5\" x=\"40.603125\" y=\"12.737306\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_9\">\n      <!-- 20 -->\n      <g transform=\"translate(20.878125 16.536524) 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_10\">\n     <!-- f(x) -->\n     <g transform=\"translate(14.798437 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_17\">\n    <path d=\"M 49.480398 139.5 \nL 60.168753 138.184221 \nL 69.669513 136.798303 \nL 78.576476 135.281363 \nL 86.889641 133.644827 \nL 94.609008 131.905739 \nL 101.734578 130.086871 \nL 108.860148 128.036103 \nL 115.391921 125.927329 \nL 121.923694 123.57335 \nL 127.861669 121.196659 \nL 133.799644 118.570008 \nL 139.143821 115.970637 \nL 144.487999 113.126471 \nL 149.832176 110.014459 \nL 154.582556 107.003026 \nL 159.332936 103.740781 \nL 164.083317 100.206832 \nL 168.833697 96.378551 \nL 173.584077 92.231424 \nL 177.740659 88.320312 \nL 181.897242 84.125611 \nL 186.053824 79.626761 \nL 190.210407 74.801707 \nL 194.366989 69.626797 \nL 198.523572 64.076663 \nL 202.680154 58.1241 \nL 206.836737 51.739927 \nL 210.99332 44.89285 \nL 215.149902 37.549303 \nL 218.712687 30.832468 \nL 222.275472 23.700287 \nL 225.838257 16.127076 \nL 227.025852 13.5 \nL 227.025852 13.5 \n\" clip-path=\"url(#p06fc2111a4)\" style=\"fill: none; stroke: #1f77b4; stroke-width: 1.5; stroke-linecap: square\"/>\n   </g>\n   <g id=\"line2d_18\">\n    <path d=\"M 49.480398 139.5 \nL 227.025852 119.551555 \nL 227.025852 119.551555 \n\" clip-path=\"url(#p06fc2111a4)\" style=\"fill: none; stroke-dasharray: 5.55,2.4; stroke-dashoffset: 0; stroke: #bf00bf; stroke-width: 1.5\"/>\n   </g>\n   <g id=\"line2d_19\">\n    <path d=\"M 49.480398 139.5 \nL 60.168753 138.191008 \nL 70.857108 136.665853 \nL 81.545463 134.924534 \nL 92.233818 132.967051 \nL 102.922173 130.793404 \nL 113.610528 128.403594 \nL 124.892681 125.646505 \nL 136.174834 122.648568 \nL 147.456986 119.409781 \nL 158.739139 115.930145 \nL 170.021292 112.20966 \nL 181.303444 108.248326 \nL 192.585597 104.046142 \nL 203.86775 99.60311 \nL 215.149902 94.919228 \nL 226.432055 89.994498 \nL 227.025852 89.72863 \nL 227.025852 89.72863 \n\" clip-path=\"url(#p06fc2111a4)\" style=\"fill: none; stroke-dasharray: 9.6,2.4,1.5,2.4; stroke-dashoffset: 0; stroke: #008000; stroke-width: 1.5\"/>\n   </g>\n   <g id=\"line2d_20\">\n    <path d=\"M 49.480398 139.5 \nL 60.168753 138.184221 \nL 69.669513 136.798318 \nL 78.576476 135.281501 \nL 86.889641 133.645463 \nL 94.609008 131.907738 \nL 101.734578 130.091781 \nL 108.860148 128.046879 \nL 115.391921 125.947843 \nL 121.923694 123.610166 \nL 127.861669 121.256701 \nL 133.799644 118.664625 \nL 139.737619 115.811856 \nL 145.081796 113.001921 \nL 150.425974 109.943217 \nL 155.770151 106.616163 \nL 161.114329 103.000001 \nL 165.864709 99.525182 \nL 170.615089 95.788307 \nL 175.365469 91.772292 \nL 180.115849 87.459226 \nL 184.866229 82.830342 \nL 189.616609 77.865999 \nL 194.366989 72.545662 \nL 199.117369 66.847876 \nL 203.273952 61.535105 \nL 207.430535 55.900612 \nL 211.587117 49.928216 \nL 215.7437 43.601148 \nL 219.900282 36.902045 \nL 224.056865 29.812933 \nL 227.025852 24.500226 \nL 227.025852 24.500226 \n\" clip-path=\"url(#p06fc2111a4)\" style=\"fill: none; stroke-dasharray: 1.5,2.475; stroke-dashoffset: 0; stroke: #ff0000; stroke-width: 1.5\"/>\n   </g>\n   <g id=\"patch_3\">\n    <path d=\"M 40.603125 145.8 \nL 40.603125 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 235.903125 145.8 \nL 235.903125 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 40.603125 145.8 \nL 235.903125 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 40.603125 7.2 \nL 235.903125 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"legend_1\">\n    <g id=\"patch_7\">\n     <path d=\"M 47.603125 73.9125 \nL 192.159375 73.9125 \nQ 194.159375 73.9125 194.159375 71.9125 \nL 194.159375 14.2 \nQ 194.159375 12.2 192.159375 12.2 \nL 47.603125 12.2 \nQ 45.603125 12.2 45.603125 14.2 \nL 45.603125 71.9125 \nQ 45.603125 73.9125 47.603125 73.9125 \nz\n\" style=\"fill: #ffffff; opacity: 0.8; stroke: #cccccc; stroke-linejoin: miter\"/>\n    </g>\n    <g id=\"line2d_21\">\n     <path d=\"M 49.603125 20.298438 \nL 59.603125 20.298438 \nL 69.603125 20.298438 \n\" style=\"fill: none; stroke: #1f77b4; stroke-width: 1.5; stroke-linecap: square\"/>\n    </g>\n    <g id=\"text_11\">\n     <!-- Exponential -->\n     <g transform=\"translate(77.603125 23.798438) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-45\" d=\"M 628 4666 \nL 3578 4666 \nL 3578 4134 \nL 1259 4134 \nL 1259 2753 \nL 3481 2753 \nL 3481 2222 \nL 1259 2222 \nL 1259 531 \nL 3634 531 \nL 3634 0 \nL 628 0 \nL 628 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-70\" d=\"M 1159 525 \nL 1159 -1331 \nL 581 -1331 \nL 581 3500 \nL 1159 3500 \nL 1159 2969 \nQ 1341 3281 1617 3432 \nQ 1894 3584 2278 3584 \nQ 2916 3584 3314 3078 \nQ 3713 2572 3713 1747 \nQ 3713 922 3314 415 \nQ 2916 -91 2278 -91 \nQ 1894 -91 1617 61 \nQ 1341 213 1159 525 \nz\nM 3116 1747 \nQ 3116 2381 2855 2742 \nQ 2594 3103 2138 3103 \nQ 1681 3103 1420 2742 \nQ 1159 2381 1159 1747 \nQ 1159 1113 1420 752 \nQ 1681 391 2138 391 \nQ 2594 391 2855 752 \nQ 3116 1113 3116 1747 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-6f\" d=\"M 1959 3097 \nQ 1497 3097 1228 2736 \nQ 959 2375 959 1747 \nQ 959 1119 1226 758 \nQ 1494 397 1959 397 \nQ 2419 397 2687 759 \nQ 2956 1122 2956 1747 \nQ 2956 2369 2687 2733 \nQ 2419 3097 1959 3097 \nz\nM 1959 3584 \nQ 2709 3584 3137 3096 \nQ 3566 2609 3566 1747 \nQ 3566 888 3137 398 \nQ 2709 -91 1959 -91 \nQ 1206 -91 779 398 \nQ 353 888 353 1747 \nQ 353 2609 779 3096 \nQ 1206 3584 1959 3584 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-6e\" d=\"M 3513 2113 \nL 3513 0 \nL 2938 0 \nL 2938 2094 \nQ 2938 2591 2744 2837 \nQ 2550 3084 2163 3084 \nQ 1697 3084 1428 2787 \nQ 1159 2491 1159 1978 \nL 1159 0 \nL 581 0 \nL 581 3500 \nL 1159 3500 \nL 1159 2956 \nQ 1366 3272 1645 3428 \nQ 1925 3584 2291 3584 \nQ 2894 3584 3203 3211 \nQ 3513 2838 3513 2113 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-65\" d=\"M 3597 1894 \nL 3597 1613 \nL 953 1613 \nQ 991 1019 1311 708 \nQ 1631 397 2203 397 \nQ 2534 397 2845 478 \nQ 3156 559 3463 722 \nL 3463 178 \nQ 3153 47 2828 -22 \nQ 2503 -91 2169 -91 \nQ 1331 -91 842 396 \nQ 353 884 353 1716 \nQ 353 2575 817 3079 \nQ 1281 3584 2069 3584 \nQ 2775 3584 3186 3129 \nQ 3597 2675 3597 1894 \nz\nM 3022 2063 \nQ 3016 2534 2758 2815 \nQ 2500 3097 2075 3097 \nQ 1594 3097 1305 2825 \nQ 1016 2553 972 2059 \nL 3022 2063 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-74\" d=\"M 1172 4494 \nL 1172 3500 \nL 2356 3500 \nL 2356 3053 \nL 1172 3053 \nL 1172 1153 \nQ 1172 725 1289 603 \nQ 1406 481 1766 481 \nL 2356 481 \nL 2356 0 \nL 1766 0 \nQ 1100 0 847 248 \nQ 594 497 594 1153 \nL 594 3053 \nL 172 3053 \nL 172 3500 \nL 594 3500 \nL 594 4494 \nL 1172 4494 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-69\" d=\"M 603 3500 \nL 1178 3500 \nL 1178 0 \nL 603 0 \nL 603 3500 \nz\nM 603 4863 \nL 1178 4863 \nL 1178 4134 \nL 603 4134 \nL 603 4863 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-61\" d=\"M 2194 1759 \nQ 1497 1759 1228 1600 \nQ 959 1441 959 1056 \nQ 959 750 1161 570 \nQ 1363 391 1709 391 \nQ 2188 391 2477 730 \nQ 2766 1069 2766 1631 \nL 2766 1759 \nL 2194 1759 \nz\nM 3341 1997 \nL 3341 0 \nL 2766 0 \nL 2766 531 \nQ 2569 213 2275 61 \nQ 1981 -91 1556 -91 \nQ 1019 -91 701 211 \nQ 384 513 384 1019 \nQ 384 1609 779 1909 \nQ 1175 2209 1959 2209 \nL 2766 2209 \nL 2766 2266 \nQ 2766 2663 2505 2880 \nQ 2244 3097 1772 3097 \nQ 1472 3097 1187 3025 \nQ 903 2953 641 2809 \nL 641 3341 \nQ 956 3463 1253 3523 \nQ 1550 3584 1831 3584 \nQ 2591 3584 2966 3190 \nQ 3341 2797 3341 1997 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-6c\" d=\"M 603 4863 \nL 1178 4863 \nL 1178 0 \nL 603 0 \nL 603 4863 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-45\"/>\n      <use xlink:href=\"#DejaVuSans-78\" transform=\"translate(63.183594 0)\"/>\n      <use xlink:href=\"#DejaVuSans-70\" transform=\"translate(122.363281 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(185.839844 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(247.021484 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(310.400391 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(371.923828 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(435.302734 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(474.511719 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(502.294922 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6c\" transform=\"translate(563.574219 0)\"/>\n     </g>\n    </g>\n    <g id=\"line2d_22\">\n     <path d=\"M 49.603125 34.976562 \nL 59.603125 34.976562 \nL 69.603125 34.976562 \n\" style=\"fill: none; stroke-dasharray: 5.55,2.4; stroke-dashoffset: 0; stroke: #bf00bf; stroke-width: 1.5\"/>\n    </g>\n    <g id=\"text_12\">\n     <!-- Degree 1 Taylor Series -->\n     <g transform=\"translate(77.603125 38.476562) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-44\" d=\"M 1259 4147 \nL 1259 519 \nL 2022 519 \nQ 2988 519 3436 956 \nQ 3884 1394 3884 2338 \nQ 3884 3275 3436 3711 \nQ 2988 4147 2022 4147 \nL 1259 4147 \nz\nM 628 4666 \nL 1925 4666 \nQ 3281 4666 3915 4102 \nQ 4550 3538 4550 2338 \nQ 4550 1131 3912 565 \nQ 3275 0 1925 0 \nL 628 0 \nL 628 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-67\" d=\"M 2906 1791 \nQ 2906 2416 2648 2759 \nQ 2391 3103 1925 3103 \nQ 1463 3103 1205 2759 \nQ 947 2416 947 1791 \nQ 947 1169 1205 825 \nQ 1463 481 1925 481 \nQ 2391 481 2648 825 \nQ 2906 1169 2906 1791 \nz\nM 3481 434 \nQ 3481 -459 3084 -895 \nQ 2688 -1331 1869 -1331 \nQ 1566 -1331 1297 -1286 \nQ 1028 -1241 775 -1147 \nL 775 -588 \nQ 1028 -725 1275 -790 \nQ 1522 -856 1778 -856 \nQ 2344 -856 2625 -561 \nQ 2906 -266 2906 331 \nL 2906 616 \nQ 2728 306 2450 153 \nQ 2172 0 1784 0 \nQ 1141 0 747 490 \nQ 353 981 353 1791 \nQ 353 2603 747 3093 \nQ 1141 3584 1784 3584 \nQ 2172 3584 2450 3431 \nQ 2728 3278 2906 2969 \nL 2906 3500 \nL 3481 3500 \nL 3481 434 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-72\" d=\"M 2631 2963 \nQ 2534 3019 2420 3045 \nQ 2306 3072 2169 3072 \nQ 1681 3072 1420 2755 \nQ 1159 2438 1159 1844 \nL 1159 0 \nL 581 0 \nL 581 3500 \nL 1159 3500 \nL 1159 2956 \nQ 1341 3275 1631 3429 \nQ 1922 3584 2338 3584 \nQ 2397 3584 2469 3576 \nQ 2541 3569 2628 3553 \nL 2631 2963 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-20\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-54\" d=\"M -19 4666 \nL 3928 4666 \nL 3928 4134 \nL 2272 4134 \nL 2272 0 \nL 1638 0 \nL 1638 4134 \nL -19 4134 \nL -19 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-79\" d=\"M 2059 -325 \nQ 1816 -950 1584 -1140 \nQ 1353 -1331 966 -1331 \nL 506 -1331 \nL 506 -850 \nL 844 -850 \nQ 1081 -850 1212 -737 \nQ 1344 -625 1503 -206 \nL 1606 56 \nL 191 3500 \nL 800 3500 \nL 1894 763 \nL 2988 3500 \nL 3597 3500 \nL 2059 -325 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-53\" d=\"M 3425 4513 \nL 3425 3897 \nQ 3066 4069 2747 4153 \nQ 2428 4238 2131 4238 \nQ 1616 4238 1336 4038 \nQ 1056 3838 1056 3469 \nQ 1056 3159 1242 3001 \nQ 1428 2844 1947 2747 \nL 2328 2669 \nQ 3034 2534 3370 2195 \nQ 3706 1856 3706 1288 \nQ 3706 609 3251 259 \nQ 2797 -91 1919 -91 \nQ 1588 -91 1214 -16 \nQ 841 59 441 206 \nL 441 856 \nQ 825 641 1194 531 \nQ 1563 422 1919 422 \nQ 2459 422 2753 634 \nQ 3047 847 3047 1241 \nQ 3047 1584 2836 1778 \nQ 2625 1972 2144 2069 \nL 1759 2144 \nQ 1053 2284 737 2584 \nQ 422 2884 422 3419 \nQ 422 4038 858 4394 \nQ 1294 4750 2059 4750 \nQ 2388 4750 2728 4690 \nQ 3069 4631 3425 4513 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-73\" d=\"M 2834 3397 \nL 2834 2853 \nQ 2591 2978 2328 3040 \nQ 2066 3103 1784 3103 \nQ 1356 3103 1142 2972 \nQ 928 2841 928 2578 \nQ 928 2378 1081 2264 \nQ 1234 2150 1697 2047 \nL 1894 2003 \nQ 2506 1872 2764 1633 \nQ 3022 1394 3022 966 \nQ 3022 478 2636 193 \nQ 2250 -91 1575 -91 \nQ 1294 -91 989 -36 \nQ 684 19 347 128 \nL 347 722 \nQ 666 556 975 473 \nQ 1284 391 1588 391 \nQ 1994 391 2212 530 \nQ 2431 669 2431 922 \nQ 2431 1156 2273 1281 \nQ 2116 1406 1581 1522 \nL 1381 1569 \nQ 847 1681 609 1914 \nQ 372 2147 372 2553 \nQ 372 3047 722 3315 \nQ 1072 3584 1716 3584 \nQ 2034 3584 2315 3537 \nQ 2597 3491 2834 3397 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-44\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(77.001953 0)\"/>\n      <use xlink:href=\"#DejaVuSans-67\" transform=\"translate(138.525391 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(202.001953 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(240.865234 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(302.388672 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(363.912109 0)\"/>\n      <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(395.699219 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(459.322266 0)\"/>\n      <use xlink:href=\"#DejaVuSans-54\" transform=\"translate(491.109375 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(535.693359 0)\"/>\n      <use xlink:href=\"#DejaVuSans-79\" transform=\"translate(596.972656 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6c\" transform=\"translate(656.152344 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(683.935547 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(745.117188 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(786.230469 0)\"/>\n      <use xlink:href=\"#DejaVuSans-53\" transform=\"translate(818.017578 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(881.494141 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(943.017578 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(984.130859 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(1011.914062 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(1073.4375 0)\"/>\n     </g>\n    </g>\n    <g id=\"line2d_23\">\n     <path d=\"M 49.603125 49.654687 \nL 59.603125 49.654687 \nL 69.603125 49.654687 \n\" style=\"fill: none; stroke-dasharray: 9.6,2.4,1.5,2.4; stroke-dashoffset: 0; stroke: #008000; stroke-width: 1.5\"/>\n    </g>\n    <g id=\"text_13\">\n     <!-- Degree 2 Taylor Series -->\n     <g transform=\"translate(77.603125 53.154687) scale(0.1 -0.1)\">\n      <use xlink:href=\"#DejaVuSans-44\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(77.001953 0)\"/>\n      <use xlink:href=\"#DejaVuSans-67\" transform=\"translate(138.525391 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(202.001953 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(240.865234 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(302.388672 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(363.912109 0)\"/>\n      <use xlink:href=\"#DejaVuSans-32\" transform=\"translate(395.699219 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(459.322266 0)\"/>\n      <use xlink:href=\"#DejaVuSans-54\" transform=\"translate(491.109375 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(535.693359 0)\"/>\n      <use xlink:href=\"#DejaVuSans-79\" transform=\"translate(596.972656 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6c\" transform=\"translate(656.152344 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(683.935547 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(745.117188 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(786.230469 0)\"/>\n      <use xlink:href=\"#DejaVuSans-53\" transform=\"translate(818.017578 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(881.494141 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(943.017578 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(984.130859 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(1011.914062 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(1073.4375 0)\"/>\n     </g>\n    </g>\n    <g id=\"line2d_24\">\n     <path d=\"M 49.603125 64.332813 \nL 59.603125 64.332813 \nL 69.603125 64.332813 \n\" style=\"fill: none; stroke-dasharray: 1.5,2.475; stroke-dashoffset: 0; stroke: #ff0000; stroke-width: 1.5\"/>\n    </g>\n    <g id=\"text_14\">\n     <!-- Degree 5 Taylor Series -->\n     <g transform=\"translate(77.603125 67.832813) scale(0.1 -0.1)\">\n      <use xlink:href=\"#DejaVuSans-44\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(77.001953 0)\"/>\n      <use xlink:href=\"#DejaVuSans-67\" transform=\"translate(138.525391 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(202.001953 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(240.865234 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(302.388672 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(363.912109 0)\"/>\n      <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(395.699219 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(459.322266 0)\"/>\n      <use xlink:href=\"#DejaVuSans-54\" transform=\"translate(491.109375 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(535.693359 0)\"/>\n      <use xlink:href=\"#DejaVuSans-79\" transform=\"translate(596.972656 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6c\" transform=\"translate(656.152344 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(683.935547 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(745.117188 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(786.230469 0)\"/>\n      <use xlink:href=\"#DejaVuSans-53\" transform=\"translate(818.017578 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(881.494141 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(943.017578 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(984.130859 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(1011.914062 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(1073.4375 0)\"/>\n     </g>\n    </g>\n   </g>\n  </g>\n </g>\n <defs>\n  <clipPath id=\"p06fc2111a4\">\n   <rect x=\"40.603125\" 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-single-variable-calculus-md-9 fw=all -->\n",
    "\n",
    "Taylor series matter here in two ways. *Theoretically*, replacing an unwieldy function by its low-degree polynomial makes it tractable: the first-order term is what gave us gradient descent, the second-order term is the curvature behind Newton's method and step-size limits. *Numerically*, the same local-polynomial idea underlies elementary-function libraries, but production implementations do more than truncate the Taylor series at the input: they first reduce the argument to a small interval and then evaluate a carefully chosen polynomial or rational approximation with controlled error.\n",
    "\n",
    "## When the Tangent Fails\n",
    "\n",
    "Everything so far rested on the \"zoom in and see a line\" picture: a smooth function looks linear up close, so the limit the equation exists. But the activation that built modern deep learning, $\\mathrm{ReLU}(x) = \\max(0, x)$, has a *corner* at the origin, and so does $|x|$. At a corner the microscope never settles on one line, and the ordinary derivative is undefined. This section says exactly what goes wrong, what to use instead, and why stochastic gradient descent (gradient descent driven by gradients estimated on random minibatches of data, that section) is unaffected in practice.\n",
    "\n",
    "### One-Sided Derivatives\n",
    "\n",
    "The trouble is visible directly in the difference quotient the equation. For $f(x) = |x|$ at $x = 0$,\n",
    "\n",
    "$$\n",
    "\\frac{|0+\\epsilon| - |0|}{\\epsilon} = \\frac{|\\epsilon|}{\\epsilon} =\n",
    "\\begin{cases} +1 & \\epsilon > 0, \\\\ -1 & \\epsilon < 0. \\end{cases}\n",
    "$$\n",
    "\n",
    "The two sides give different limits, so no single number is *the* slope: approaching from the right the function rises with slope $+1$, from the left it falls with slope $-1$. These are the **one-sided derivatives** $f'_+(0) = +1$ and $f'_-(0) = -1$. The ordinary two-sided derivative exists only when they agree. For $\\mathrm{ReLU}$ at $0$ the same computation gives $f'_-(0) = 0$ (flat on the left) and $f'_+(0) = 1$ (slope $1$ on the right). Note there is no limit to take: for $|x|$ at $0$ the two quotients are the *constants* $\\pm 1$, the same at every $\\epsilon$, so the next cell prints them once. It then asks the question this section turns on: what does autograd return at the corner, where no true derivative exists?"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "single-variable-calculus-one-sided"
   },
   "source": [
    "# One-sided difference quotients of |x| at 0: constants, no limit needed\n",
    "epsilon = 1e-4\n",
    "print(f'right quotient: {(abs(epsilon) - abs(0)) / epsilon:+.1f}, '\n",
    "      f'left quotient: {(abs(-epsilon) - abs(0)) / -epsilon:+.1f}')\n",
    "\n",
    "# What autograd returns at the corner, where no derivative exists\n",
    "for name, fn in [('d|x|/dx', torch.abs), (\"ReLU'\", torch.relu)]:\n",
    "    x = torch.tensor(0.0, requires_grad=True)\n",
    "    fn(x).backward()\n",
    "    print(f\"{name} at 0: autograd returns {x.grad.item():.1f}\")"
   ],
   "execution_count": 9,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "right quotient: +1.0, left quotient: -1.0\nd|x|/dx at 0: autograd returns 0.0\nReLU' at 0: autograd returns 0.0\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-single-variable-calculus-md-10 fw=all -->\n",
    "\n",
    "Autograd does not refuse. For both $\\frac{d}{dx}|x|$ and $\\mathrm{ReLU}'$ at $0$ it returns the fixed value $0$: one particular slope, chosen by convention, from the set of candidates we now define.\n",
    "\n",
    "### Subgradients and Optimality\n",
    "\n",
    "The fix is to stop insisting on a *single* tangent and allow *all* the lines that stay below the graph. A number $g$ is a **subgradient** of a convex function $f$ (one whose every chord lies on or above its graph) at $x$ if\n",
    "\n",
    "$$\n",
    "f(y) \\ge f(x) + g\\,(y - x) \\quad \\textrm{for all } y,\n",
    "$$\n",
    "\n",
    "i.e. the line through $(x, f(x))$ with slope $g$ is a global underestimate of $f$. The set of all such slopes is the **subdifferential** $\\partial f(x)$ [@Rockafellar.1970]. Away from a corner it is the single ordinary slope; at a corner it is the whole interval *between* the one-sided derivatives, the \"fan\" of supporting lines shown in the figure:\n",
    "\n",
    "$$\n",
    "\\partial |x|(0) = [-1, 1], \\qquad \\partial\\, \\mathrm{ReLU}(0) = [0, 1].\n",
    "$$\n",
    "\n",
    "Off the corner each function is differentiable and the subdifferential collapses to the single ordinary slope; at the corner, the $0$ that autograd returned above is one element of each set.\n",
    "\n",
    "![Two corners and their subdifferentials: the fan of supporting lines through the origin of $|x|$ (left) and of $\\mathrm{ReLU}$ (right), with slopes running over $\\partial|x|(0)$ and $\\partial\\,\\mathrm{ReLU}(0)$ respectively. Off each corner there is a single tangent and the subdifferential collapses to the ordinary derivative.](../img/mdl-cal-relu-corner.svg)\n",
    "\n",
    "The subgradient restores the optimality test. For differentiable $f$ a minimum requires $f'(x) = 0$; the subgradient version is the inclusion\n",
    "\n",
    "$$\n",
    "0 \\in \\partial f(x).\n",
    "$$\n",
    "\n",
    "This is no harder to prove than its smooth cousin: taking $g = 0$ in the equation reads $f(y) \\ge f(x)$ for all $y$, which is precisely the statement that $x$ is a global minimum. For $|x|$ at $0$ we have $0 \\in [-1,1] = \\partial|x|(0)$, correctly certifying the origin as the minimum even though no derivative exists there, exactly the case the smooth test $f'(x)=0$ cannot reach.\n",
    "\n",
    "### Why SGD Shrugs\n",
    "\n",
    "Corners do not, in practice, break training. To see why, look at what autograd actually does at them. One clarification first, so the convexity above is not over-read: a deep network's loss surface is wildly *non*-convex, while the subdifferential the equation is a *convex*-function notion. The kinks in a network come from convex building blocks ($|x|$, $\\mathrm{ReLU}$, the hinge loss $\\max(0, 1-x)$), and what autograd does at each kink is simple: it returns *one fixed element* of that piece's subdifferential (the deep-learning libraries' convention is $\\mathrm{ReLU}'(0) = 0$, as the cell above showed) and lets the chain rule propagate that choice through the surrounding, nonconvex composition.\n",
    "\n",
    "Two caveats apply. First, even for a convex function a subgradient step need not be a *descent* step: at the minimum of $|x|$ the perfectly valid subgradient $g = \\tfrac12 \\in \\partial|x|(0)$ sends the update to $x = -\\eta/2$ and *increases* the function; the subgradient method of convex optimization converges by shrinking its step sizes, not by descending monotonically [@Nesterov.2018]. Second, the chain rule carries no warranty at kinks: chaining per-kink choices can produce a number that is not a subgradient of the composite *at all*. The simplest failure is the identity in disguise\n",
    "\n",
    "$$\n",
    "g(x) = \\mathrm{ReLU}(x) - \\mathrm{ReLU}(-x) = x \\quad \\textrm{for all } x,\n",
    "$$\n",
    "\n",
    "whose only correct slope at $0$ is $1$. The chain rule gives $g'(x) = \\mathrm{ReLU}'(x) + \\mathrm{ReLU}'(-x)$, which is indeed $1$ everywhere *except* at the kink, where the fixed convention makes it $0 + 0 = 0$. The next cell runs exactly this computation."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "mdl-single-variable-calculus-why-sgd-shrugs"
   },
   "source": [
    "# g(x) = relu(x) - relu(-x) is the identity, so the true slope at 0 is 1\n",
    "x = torch.tensor(0.0, requires_grad=True)\n",
    "g = torch.relu(x) - torch.relu(-x)\n",
    "g.backward()\n",
    "print(f\"autograd: g'(0) = {x.grad.item():.1f}  (true slope: 1.0)\")"
   ],
   "execution_count": 10,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "autograd: g'(0) = 0.0  (true slope: 1.0)\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-single-variable-calculus-md-11 fw=all -->\n",
    "\n",
    "Autograd reports slope $0$ for a function that *is* the identity: the per-kink convention $\\mathrm{ReLU}'(0) = 0$, chained, produces a number that is not a subgradient of $g$ at $0$ at all. What automatic differentiation computes at nonsmooth points is, in general, an element of a *conservative field* [@Bolte.Pauwels.2021], a relaxed gradient notion that agrees with the true derivative everywhere outside a *measure-zero* set, one so small it can be covered by intervals of arbitrarily small total length (that section makes such size-zero statements precise). That a Lipschitz function even *has* a derivative outside a measure-zero set is **Rademacher's theorem** [@Rademacher.1919]. Under the definability/path-differentiability assumptions studied by\n",
    "@Bolte.Pauwels.2021, together with bounded iterates and the usual\n",
    "stochastic-approximation conditions on steps and gradient noise, SGD driven by\n",
    "such a conservative field converges to an appropriate stationary set almost\n",
    "surely. This is a conditional theorem, not a guarantee for every nonsmooth\n",
    "program.\n",
    "\n",
    "Why does training tolerate the occasional bad chained value? The usual picture is that a network's kinks (the points where some $\\mathrm{ReLU}$ input is exactly zero) form a measure-zero set, and a randomly drawn point lands in a measure-zero set with probability zero, provided the draw comes from a distribution with a density (an *absolutely continuous* one). Take this as a heuristic picture rather than a theorem: we have not proved that the kink set of a whole network is measure zero, and in floating-point arithmetic the argument fails outright, since the floats are a countable set on which every representable value, exact zeros included, carries positive probability. The rigorous backstop is the conservative-field convergence result quoted above. The convex-analysis machinery is developed further in that section; the lesson here is that the local-linear program survives at corners because almost every step of stochastic training differentiates a locally smooth function, and the conservative-field theory covers the steps that do land on a kink.\n",
    "\n",
    "## Summary\n",
    "\n",
    "* The derivative is the *local linear model* of a function: $f(x+\\epsilon) \\approx f(x) + \\epsilon f'(x)$. It is the slope of the line a smooth curve flattens onto when we zoom in, and the limit of difference quotients.\n",
    "* The derivatives of elementary functions, combined with the sum, product, and chain rules, differentiate any expression mechanically. Each rule is the small-change identity expanded to first order; the chain rule run in reverse over a network is backpropagation.\n",
    "* Choosing the step $\\epsilon = -\\eta f'(x)$ in the local model predicts a decrease of $\\eta[f'(x)]^2$. When the slope is $L$-Lipschitz the *descent lemma* turns this into a genuine guarantee $f(x - \\eta f'(x)) \\le f(x) - \\eta(1 - L\\eta/2)[f'(x)]^2$, a strict drop for $0 < \\eta < 2/L$ (best at $\\eta = 1/L$). Descent stalls at the stationary points $f'(x) = 0$, and a step past $2/L$ can *increase* $f$ when curvature overwhelms the first-order gain.\n",
    "* The second derivative is curvature: its sign decides minimum vs. maximum, and Taylor series extend the line and parabola to the best polynomial model of any order.\n",
    "* At corners like $\\mathrm{ReLU}(0)$ the derivative is undefined, but the *subdifferential* supplies a set of valid slopes ($\\partial|x|(0) = [-1,1]$) and optimality becomes $0 \\in \\partial f(x)$. Autograd returns one fixed element per kink ($\\mathrm{ReLU}'(0) = 0$); chained through a composition that value can fail to be a subgradient at the kinks themselves. Conservative-field theory supplies convergence results under additional structural, boundedness, step-size, and noise assumptions.\n",
    "\n",
    "## Exercises\n",
    "\n",
    "1. Compute the derivative of $x^3 - 4x + 1$, and of $\\log\\!\\left(\\frac{1}{x}\\right)$ for $x > 0$.\n",
    "2. Derive the quotient rule from the product and chain rules by writing $\\frac{g(x)}{h(x)} = g(x)\\cdot\\left(h(x)\\right)^{-1}$ and using the power rule with $n = -1$ for the outer function. Check your result on $\\tan(x) = \\frac{\\sin(x)}{\\cos(x)}$: you should find $\\frac{d}{dx}\\tan(x) = \\frac{1}{\\cos^2(x)}$.\n",
    "3. True or false: if $f'(x) = 0$ then $f$ has a maximum or a minimum at $x$. If false, give a counterexample and the test that distinguishes the cases.\n",
    "4. Find the minimum of $f(x) = x\\log(x)$ for $x \\ge 0$ (take the limiting value $f(0) = 0$).\n",
    "5. The first-order model predicts $f(x - \\eta f'(x)) \\approx f(x) - \\eta[f'(x)]^2$. Starting from the small-change identity, derive this prediction and name the term it discards. Then extend the descent lemma to the vector case: for $f: \\mathbb{R}^n \\to \\mathbb{R}$ with an $L$-Lipschitz gradient ($\\|\\nabla f(\\mathbf{u}) - \\nabla f(\\mathbf{v})\\| \\le L\\|\\mathbf{u} - \\mathbf{v}\\|$), show that $f(\\mathbf{x} - \\eta\\nabla f(\\mathbf{x})) \\le f(\\mathbf{x}) - \\eta\\left(1 - \\tfrac{L\\eta}{2}\\right)\\|\\nabla f(\\mathbf{x})\\|^2$. (*Hint:* repeat the proof of the equation along the segment $\\mathbf{x} + t\\mathbf{s}$ with $\\mathbf{s} = -\\eta\\nabla f(\\mathbf{x})$, bounding the integral with the Cauchy--Schwarz inequality.)\n",
    "6. For $f(x) = x^2$, find *all* step sizes $\\eta$ for which gradient descent from $x_0 \\neq 0$ converges to the minimum, and the one $\\eta$ that reaches it in a single step. (*Hint:* use $x_{t+1} = (1-2\\eta)x_t$.)\n",
    "7. Give a function $f$ and a step size $\\eta$ for which a single gradient-descent step *increases* $f$, and explain the failure: which hypothesis of the descent lemma the equation is violated, or is $\\eta$ simply past $2/L$? (*Hint:* $f(x) = x^2$ with $\\eta > 1$ already does it.)\n",
    "8. Relate the one-dimensional update $x \\leftarrow x - \\eta f'(x)$ to the vector update $\\mathbf{w} \\leftarrow \\mathbf{w} - \\eta\\nabla L(\\mathbf{w})$ from the introduction.\n",
    "9. Compute the subdifferentials $\\partial\\,\\mathrm{ReLU}(0)$ and $\\partial|x|(0)$. Which of $\\{0,\\, 0.5,\\, 1\\}$ are valid subgradients of $\\mathrm{ReLU}$ at $0$? Sketch the subdifferential of the hinge loss $\\max(0, 1 - x)$.\n",
    "10. Use the degree-$5$ Taylor polynomial of $e^x$ at $x_0 = 0$ to estimate $e$, and compare with the true value."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-single-variable-calculus-md-12 fw=pytorch -->\n",
    "\n",
    "[Discussions](https://d2l.discourse.group/t/1088)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "name": "d2l-pytorch",
   "display_name": "d2l (PyTorch)",
   "language": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
