{
 "cells": [
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "---\n",
    "execute:\n",
    "  enabled: false\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-convexity-md-1 fw=all -->\n",
    "\n",
    "# Convex Sets and Convex Functions\n",
    "\n",
    "Convexity is the line between \"gradient descent provably finds the answer\" and \"we\n",
    "hope.\" For a convex problem, *every local minimum is global*, there are no saddle\n",
    "points or spurious basins to get stuck in, and the rates of\n",
    "that section come with global guarantees.\n",
    "Convexity tells you which deep-learning sub-problems are *easy* (the last-layer\n",
    "softmax/logistic loss in the logits, projections onto constraint sets, the\n",
    "$\\ell_1$ and $\\ell_2$ regularizers, the SVM dual of\n",
    "that section), and it tells you precisely\n",
    "what you forfeit by stacking nonlinear layers. This section develops the three\n",
    "equivalent lenses for recognizing a convex function, Jensen's inequality, the\n",
    "global convergence guarantees that follow, a calculus for certifying\n",
    "convexity without computing a single Hessian, and a reality check on why deep\n",
    "networks are non-convex and what we keep anyway.\n",
    "\n",
    "We lean on that section (inner products,\n",
    "hyperplanes, half-spaces), that section and\n",
    "that section (derivatives, the Hessian, positive\n",
    "semidefiniteness), and that section (the descent\n",
    "lemma and the condition number $\\kappa = L/\\mu$). The standard reference is\n",
    "@Boyd.Vandenberghe.2004, chapters 2--3; @Nesterov.2018 is the\n",
    "source for the convergence theory. All code in this section is plain NumPy;\n",
    "every demonstration is a handful of lines."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "convexity-imports"
   },
   "source": [
    "%matplotlib inline\n",
    "from d2l import torch as d2l\n",
    "import numpy as np"
   ],
   "execution_count": 1,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-convexity-md-2 fw=all -->\n",
    "\n",
    "## Convex Sets\n",
    "\n",
    "### Segments That Stay Inside\n",
    "\n",
    "The definition is visual: a set is convex when the segment between any two of its\n",
    "points stays inside it. Formally, $C \\subseteq \\mathbb{R}^n$ is **convex** if\n",
    "\n",
    "$$\n",
    "\\theta \\mathbf{x} + (1 - \\theta)\\, \\mathbf{y} \\in C\n",
    "\\qquad \\textrm{for all } \\mathbf{x}, \\mathbf{y} \\in C \\textrm{ and all } \\theta \\in [0, 1].\n",
    "$$\n",
    "\n",
    "As $\\theta$ runs from $1$ to $0$, the point $\\theta\\mathbf{x} + (1-\\theta)\\mathbf{y}$\n",
    "walks the straight segment from $\\mathbf{x}$ to $\\mathbf{y}$; convexity demands\n",
    "the walk never leaves the set. the figure\n",
    "contrasts a convex set, where every chord lies within, with a non-convex\n",
    "crescent, where a chord between two of its points slips outside; it also shows\n",
    "the two convex sets deep learning uses most, the probability simplex (a\n",
    "hyperplane cut of the nonnegative orthant) and a half-space.\n",
    "\n",
    "![Convex versus non-convex sets. Left: a convex set, where the segment between any two points stays inside. Middle: a non-convex crescent, where a chord between two of its points passes outside the set. Right: the probability simplex $\\{\\mathbf{p}\\succeq0,\\ \\mathbf{1}^\\top\\mathbf{p}=1\\}$ and a half-space $\\{\\mathbf{x}:\\mathbf{a}^\\top\\mathbf{x}\\leq b\\}$, both convex.](../img/mdl-opt-convex-vs-nonconvex-set.svg)\n",
    "\n",
    "A quick non-example calibrates the definition. The annulus\n",
    "$\\{\\mathbf{x} : 1 \\le \\|\\mathbf{x}\\| \\le 2\\}$ contains $(\\pm \\tfrac32, 0)$, but\n",
    "their midpoint is the origin, which the annulus excludes: the chord tunnels\n",
    "through the hole. Holes, dents, and disconnected pieces are exactly what\n",
    "the equation forbids.\n",
    "\n",
    "### The Catalog Deep Learning Uses\n",
    "\n",
    "Four families of convex sets cover most of what this book touches, and each is\n",
    "convex for a one-line reason.\n",
    "\n",
    "* **Hyperplanes and half-spaces.** For the hyperplane\n",
    "  $\\{\\mathbf{x} : \\mathbf{a}^\\top\\mathbf{x} = b\\}$ and the half-space\n",
    "  $\\{\\mathbf{x} : \\mathbf{a}^\\top\\mathbf{x} \\le b\\}$, the check is linearity:\n",
    "  $\\mathbf{a}^\\top(\\theta\\mathbf{x} + (1-\\theta)\\mathbf{y}) = \\theta\\, \\mathbf{a}^\\top\\mathbf{x} + (1-\\theta)\\, \\mathbf{a}^\\top\\mathbf{y}$,\n",
    "  and an average of two numbers equal to $b$ (or at most $b$) is again equal to\n",
    "  $b$ (or at most $b$).\n",
    "* **Norm balls.** For any norm, $\\{\\mathbf{x} : \\|\\mathbf{x}\\| \\le r\\}$ is\n",
    "  convex by the triangle inequality plus homogeneity:\n",
    "  $\\|\\theta\\mathbf{x} + (1-\\theta)\\mathbf{y}\\| \\le \\theta\\|\\mathbf{x}\\| + (1-\\theta)\\|\\mathbf{y}\\| \\le r$.\n",
    "  This covers the $\\ell_2$ balls of weight decay and gradient clipping and the\n",
    "  $\\ell_1$ balls of sparsity-inducing regularization alike.\n",
    "* **The probability simplex.**\n",
    "  $\\Delta = \\{\\mathbf{p} : \\mathbf{p} \\succeq 0,\\ \\mathbf{1}^\\top\\mathbf{p} = 1\\}$,\n",
    "  where attention weights, class probabilities, and mixture weights live.\n",
    "* **The positive semidefinite cone.**\n",
    "  $\\mathbb{S}^n_+ = \\{A = A^\\top : \\mathbf{z}^\\top A \\mathbf{z} \\ge 0 \\textrm{ for all } \\mathbf{z}\\}$,\n",
    "  home of covariance matrices and of every Hessian this section will certify.\n",
    "\n",
    "A notational convention, used throughout this part: the symbol $\\succeq$ (and\n",
    "its mirror $\\preceq$) carries two senses, *elementwise* for vectors, as in\n",
    "$\\mathbf{p} \\succeq 0$ above, and the *semidefinite order* for symmetric\n",
    "matrices, as in $A \\succeq 0$; the type of the operands says which is meant.\n",
    "\n",
    "The last two families we have not yet justified, because the shortest proofs\n",
    "use the one structural fact every catalog needs.\n",
    "\n",
    "### New Convex Sets from Old\n",
    "\n",
    "**Proposition (intersections preserve convexity).** *Let $\\{C_i\\}_{i \\in I}$ be\n",
    "any family of convex sets, finite or infinite. Then\n",
    "$C = \\bigcap_{i \\in I} C_i$ is convex.*\n",
    "\n",
    "**Proof.** Take $\\mathbf{x}, \\mathbf{y} \\in C$ and $\\theta \\in [0, 1]$. For\n",
    "every $i$, both points lie in the convex set $C_i$, so\n",
    "$\\theta\\mathbf{x} + (1-\\theta)\\mathbf{y} \\in C_i$. A point in every $C_i$ is a\n",
    "point in their intersection. $\\blacksquare$\n",
    "\n",
    "Unions have no such guarantee: $[0,1] \\cup [2,3]$ is a union of two convex\n",
    "intervals whose chord from $1$ to $2$ leaves the set. Convexity survives *and*,\n",
    "not *or*.\n",
    "\n",
    "The proposition certifies most of the catalog. The probability simplex is the intersection of\n",
    "one hyperplane ($\\mathbf{1}^\\top\\mathbf{p} = 1$) with $n$ half-spaces\n",
    "($-p_i \\le 0$), hence convex with no further work. The PSD cone is the\n",
    "intersection of *infinitely many* half-spaces, one per test vector: for each\n",
    "fixed $\\mathbf{z}$, the condition $\\mathbf{z}^\\top A \\mathbf{z} \\ge 0$ is\n",
    "*linear* in the entries of $A$, so\n",
    "$\\mathbb{S}^n_+ = \\bigcap_{\\mathbf{z}} \\{A : \\mathbf{z}^\\top A \\mathbf{z} \\ge 0\\}$\n",
    "is convex, a fact we will lean on when Hessians enter. More generally, every\n",
    "**polyhedron** $\\{\\mathbf{x} : A\\mathbf{x} \\preceq \\mathbf{b}\\}$, the\n",
    "feasible set of the constrained problems in\n",
    "that section, is a finite intersection\n",
    "of half-spaces.\n",
    "\n",
    "Two more constructions round out the toolkit. Affine maps preserve convexity in\n",
    "both directions: images and preimages of convex sets under\n",
    "$\\mathbf{x} \\mapsto A\\mathbf{x} + \\mathbf{b}$ are convex, because affine maps\n",
    "send segments to segments. And any point cloud $S$ generates a smallest convex\n",
    "superset, its **convex hull**: the intersection of every convex set containing\n",
    "$S$ (convex by the proposition), or concretely the set of all weighted averages\n",
    "$\\sum_i \\theta_i \\mathbf{x}_i$ with $\\theta_i \\ge 0$, $\\sum_i \\theta_i = 1$.\n",
    "The two descriptions coincide: the average set is itself a convex set\n",
    "containing $S$, so it contains the intersection, and the reverse inclusion\n",
    "(every convex superset contains all weighted averages) is Exercise 4's\n",
    "induction. The\n",
    "simplex is the convex hull of the coordinate vectors: every probability\n",
    "distribution is an average of certainties.\n",
    "\n",
    "## Convex Functions: Three Lenses\n",
    "\n",
    "### The Chord Lens\n",
    "\n",
    "A function $f : C \\to \\mathbb{R}$ on a convex domain $C$ is **convex** if its\n",
    "graph lies on or below every chord:\n",
    "\n",
    "$$\n",
    "f\\left(\\theta \\mathbf{x} + (1 - \\theta)\\, \\mathbf{y}\\right)\n",
    "\\;\\le\\; \\theta f(\\mathbf{x}) + (1 - \\theta) f(\\mathbf{y})\n",
    "\\qquad \\textrm{for all } \\mathbf{x}, \\mathbf{y} \\in C,\\ \\theta \\in [0, 1].\n",
    "$$\n",
    "\n",
    "The left side evaluates $f$ at a point of the segment; the right side is the\n",
    "height of the chord joining $(\\mathbf{x}, f(\\mathbf{x}))$ to\n",
    "$(\\mathbf{y}, f(\\mathbf{y}))$ above that same point. If the inequality is strict\n",
    "whenever $\\mathbf{x} \\neq \\mathbf{y}$ and $\\theta \\in (0, 1)$, $f$ is **strictly\n",
    "convex**; if $-f$ is convex, $f$ is **concave**. Note that the domain must be\n",
    "convex for the definition to even parse: the point\n",
    "$\\theta\\mathbf{x} + (1-\\theta)\\mathbf{y}$ has to be somewhere $f$ is defined.\n",
    "\n",
    "Sets and functions are one theory: $f$ is convex exactly when its\n",
    "**epigraph** $\\{(\\mathbf{x}, t) : t \\ge f(\\mathbf{x})\\}$, the region on and\n",
    "above the graph, is a convex set. Chords between points of the epigraph stay\n",
    "above the graph precisely when the equation holds. This dictionary\n",
    "lets every fact about convex sets generate a fact about convex functions, and we\n",
    "will use it shortly.\n",
    "\n",
    "### The First-Order Lens\n",
    "\n",
    "The chord lens needs no derivatives. When $f$ is differentiable, an equivalent\n",
    "test reads the tangent instead of the chord: the first-order Taylor\n",
    "approximation at any point is a *global under-estimator*,\n",
    "\n",
    "$$\n",
    "f(\\mathbf{y}) \\;\\ge\\; f(\\mathbf{x}) + \\nabla f(\\mathbf{x})^\\top (\\mathbf{y} - \\mathbf{x})\n",
    "\\qquad \\textrm{for all } \\mathbf{x}, \\mathbf{y} \\in C.\n",
    "$$\n",
    "\n",
    "The two lenses are two ways of looking at the same picture, shown in\n",
    "the figure. The chord lens reads off the definition\n",
    "directly: the chord joining any two points on the graph lies *above* the graph.\n",
    "The first-order lens reads the slope: the tangent at any point lies *below* the\n",
    "graph. This is the property gradient methods exploit: a single gradient\n",
    "evaluation at $\\mathbf{x}$ hands you a certificate about *every other point in\n",
    "the domain*, however far away. In particular, if $\\nabla f(\\mathbf{x}) = \\mathbf{0}$,\n",
    "then the equation says $f(\\mathbf{y}) \\ge f(\\mathbf{x})$ for\n",
    "all $\\mathbf{y}$: a stationary point of a convex function is already a global\n",
    "minimum. We return to this in that section.\n",
    "\n",
    "![Two equivalent lenses on convexity. Left (chord lens): the chord joining two points lies above the graph, so $f(\\theta\\mathbf{x}+(1-\\theta)\\mathbf{y})\\le\\theta f(\\mathbf{x})+(1-\\theta)f(\\mathbf{y})$. Right (first-order lens): the tangent at a point lies below the graph, so $f(\\mathbf{y})\\ge f(\\mathbf{x})+\\nabla f(\\mathbf{x})^\\top(\\mathbf{y}-\\mathbf{x})$.](../img/mdl-opt-chord-above-graph.svg)\n",
    "\n",
    "### The Second-Order Lens\n",
    "\n",
    "When $f$ is twice differentiable on an open convex domain there is a third\n",
    "test, usually the easiest to run: $f$ is convex if and only if its Hessian is\n",
    "positive semidefinite everywhere. On a lower-dimensional or closed domain, the\n",
    "test applies on the relative interior with the appropriate continuity at the\n",
    "boundary,\n",
    "\n",
    "$$\n",
    "\\nabla^2 f(\\mathbf{x}) \\succeq 0 \\qquad \\textrm{for all } \\mathbf{x} \\in C.\n",
    "$$\n",
    "\n",
    "In one dimension this is the calculus-class criterion $f''(x) \\ge 0$: the\n",
    "graph curves upward. In $n$ dimensions it says every one-dimensional slice\n",
    "curves upward, since\n",
    "$\\mathbf{v}^\\top \\nabla^2 f(\\mathbf{x})\\, \\mathbf{v}$ is the second derivative\n",
    "of $f$ along the line through $\\mathbf{x}$ in direction $\\mathbf{v}$\n",
    "(that section). Three instant applications: the\n",
    "quadratic $\\tfrac12\\mathbf{x}^\\top A \\mathbf{x} + \\mathbf{b}^\\top\\mathbf{x}$\n",
    "(with $A$ symmetric) has constant Hessian $A$, so it is convex iff\n",
    "$A \\succeq 0$; the least-squares loss\n",
    "$\\tfrac12\\|X\\mathbf{w} - \\mathbf{y}\\|^2$ has Hessian $X^\\top X$, a Gram matrix,\n",
    "always PSD (that section); and\n",
    "$e^x$, $-\\log x$, and $x \\log x$ are convex on their domains because their\n",
    "second derivatives $e^x$, $1/x^2$, and $1/x$ are positive.\n",
    "\n",
    "**Proposition (the three lenses agree).** *Let $f$ be differentiable on an open\n",
    "convex domain $C$. Then the chord condition the equation and the\n",
    "first-order condition the equation are equivalent. If $f$ is\n",
    "twice differentiable, both are equivalent to\n",
    "$\\nabla^2 f(\\mathbf{x}) \\succeq 0$ on $C$.*\n",
    "\n",
    "**Proof.** *(Chord $\\Rightarrow$ first-order.)* Fix $\\mathbf{x}, \\mathbf{y}$ and\n",
    "$\\theta \\in (0, 1]$. Rewriting the equation at the point\n",
    "$\\mathbf{x} + \\theta(\\mathbf{y} - \\mathbf{x})$ and subtracting $f(\\mathbf{x})$,\n",
    "\n",
    "$$\n",
    "\\frac{f(\\mathbf{x} + \\theta(\\mathbf{y} - \\mathbf{x})) - f(\\mathbf{x})}{\\theta}\n",
    "\\;\\le\\; f(\\mathbf{y}) - f(\\mathbf{x}).\n",
    "$$\n",
    "\n",
    "As $\\theta \\downarrow 0$ the left side converges to the directional derivative\n",
    "$\\nabla f(\\mathbf{x})^\\top(\\mathbf{y} - \\mathbf{x})$, giving\n",
    "the equation.\n",
    "\n",
    "*(First-order $\\Rightarrow$ chord.)* Let\n",
    "$\\mathbf{z} = \\theta\\mathbf{x} + (1-\\theta)\\mathbf{y}$ and apply the\n",
    "under-estimator at $\\mathbf{z}$ twice, once toward each endpoint:\n",
    "\n",
    "$$\n",
    "f(\\mathbf{x}) \\ge f(\\mathbf{z}) + \\nabla f(\\mathbf{z})^\\top(\\mathbf{x} - \\mathbf{z}),\n",
    "\\qquad\n",
    "f(\\mathbf{y}) \\ge f(\\mathbf{z}) + \\nabla f(\\mathbf{z})^\\top(\\mathbf{y} - \\mathbf{z}).\n",
    "$$\n",
    "\n",
    "Multiply by $\\theta$ and $1 - \\theta$ and add: the gradient terms combine to\n",
    "$\\nabla f(\\mathbf{z})^\\top(\\theta\\mathbf{x} + (1-\\theta)\\mathbf{y} - \\mathbf{z}) = 0$,\n",
    "leaving exactly the equation.\n",
    "\n",
    "*(Second-order $\\Rightarrow$ first-order.)* Restrict to the segment:\n",
    "$g(t) = f(\\mathbf{x} + t(\\mathbf{y} - \\mathbf{x}))$ has\n",
    "$g''(t) = (\\mathbf{y} - \\mathbf{x})^\\top \\nabla^2 f(\\mathbf{x} + t(\\mathbf{y} - \\mathbf{x}))\\,(\\mathbf{y} - \\mathbf{x}) \\ge 0$.\n",
    "Taylor's theorem with the Lagrange remainder\n",
    "(that section) gives\n",
    "$g(1) = g(0) + g'(0) + \\tfrac12 g''(\\tau)$ for some $\\tau \\in (0, 1)$, and\n",
    "dropping the nonnegative remainder is the equation.\n",
    "\n",
    "*(First-order $\\Rightarrow$ second-order.)* Suppose instead\n",
    "$\\mathbf{v}^\\top \\nabla^2 f(\\mathbf{x})\\, \\mathbf{v} < 0$ for some $\\mathbf{x}$\n",
    "and $\\mathbf{v}$. Expanding along that direction,\n",
    "\n",
    "$$\n",
    "f(\\mathbf{x} + t\\mathbf{v}) = f(\\mathbf{x}) + t\\, \\nabla f(\\mathbf{x})^\\top\\mathbf{v}\n",
    "+ \\frac{t^2}{2}\\, \\mathbf{v}^\\top \\nabla^2 f(\\mathbf{x})\\, \\mathbf{v} + o(t^2),\n",
    "$$\n",
    "\n",
    "so for small enough $t > 0$ the left side drops strictly below the tangent value\n",
    "$f(\\mathbf{x}) + t \\nabla f(\\mathbf{x})^\\top\\mathbf{v}$, contradicting\n",
    "the equation. $\\blacksquare$\n",
    "\n",
    "The practical reading: *pick whichever lens is cheapest to check*. The chord\n",
    "lens needs no smoothness (it certifies $\\|\\mathbf{x}\\|_1$ and the hinge loss,\n",
    "where Hessians do not exist); the first-order lens is what optimization proofs\n",
    "consume; the second-order lens is the usual test for smooth losses, where\n",
    "checking convexity means checking a matrix is PSD, the territory of\n",
    "that section.\n",
    "\n",
    "### Strong Convexity\n",
    "\n",
    "Convexity bounds curvature from below by zero. Two refinements sharpen the\n",
    "geometry. $f$ is **strictly convex** if the chord inequality is strict, ruling\n",
    "out flat segments. More quantitatively, $f$ is **$\\mu$-strongly convex** (for\n",
    "$\\mu > 0$) if $f(\\mathbf{x}) - \\tfrac{\\mu}{2}\\|\\mathbf{x}\\|^2$ is convex, or\n",
    "equivalently, in the first-order lens,\n",
    "\n",
    "$$\n",
    "f(\\mathbf{y}) \\;\\ge\\; f(\\mathbf{x}) + \\nabla f(\\mathbf{x})^\\top(\\mathbf{y} - \\mathbf{x})\n",
    "+ \\frac{\\mu}{2}\\, \\|\\mathbf{y} - \\mathbf{x}\\|^2,\n",
    "$$\n",
    "\n",
    "or, in the second-order lens, $\\nabla^2 f \\succeq \\mu I$ everywhere. Strong\n",
    "convexity says the graph pulls away from its tangents at least quadratically,\n",
    "like a bowl with a guaranteed minimum\n",
    "curvature. Paired with the $L$-smoothness of\n",
    "that section ($\\nabla^2 f \\preceq L I$), the\n",
    "function is sandwiched between two quadratics, and the ratio $\\kappa = L/\\mu$\n",
    "is precisely the condition number that governed convergence speed there. A\n",
    "useful source of strong convexity: adding the ridge penalty\n",
    "$\\tfrac{\\lambda}{2}\\|\\mathbf{w}\\|^2$ to any convex loss makes the sum\n",
    "$\\lambda$-strongly convex, one more service weight decay performs.\n",
    "\n",
    "### The Subgradient\n",
    "\n",
    "The losses $\\|\\mathbf{x}\\|_1$ and $\\max(0, 1 - z)$ have corners, so\n",
    "the equation cannot be checked as written: there is no\n",
    "gradient at the kink. that section already\n",
    "repaired this in one dimension with the subgradient the equation,\n",
    "computed $\\partial |x|(0) = [-1, 1]$ there, and proved the optimality test\n",
    "$0 \\in \\partial f(x^\\star)$ (the equation). The vector form is the\n",
    "same idea: a vector $\\mathbf{g}$\n",
    "is a **subgradient** of $f$ at $\\mathbf{x}$ if it provides the same global\n",
    "under-estimate a gradient would:\n",
    "\n",
    "$$\n",
    "f(\\mathbf{y}) \\;\\ge\\; f(\\mathbf{x}) + \\mathbf{g}^\\top (\\mathbf{y} - \\mathbf{x})\n",
    "\\qquad \\textrm{for all } \\mathbf{y},\n",
    "$$\n",
    "\n",
    "and the set of all subgradients at $\\mathbf{x}$ is written\n",
    "$\\partial f(\\mathbf{x})$. Where $f$ is differentiable it collapses to the\n",
    "singleton $\\{\\nabla f(\\mathbf{x})\\}$; at a corner it fans out\n",
    "(the figure), as it did for $|x|$, and, for the\n",
    "hinge $\\max(0, 1 - z)$ at $z = 1$, $\\partial f(1) = [-1, 0]$. The optimality\n",
    "criterion survives verbatim: $\\mathbf{x}^\\star$ minimizes $f$ iff\n",
    "$\\mathbf{0} \\in \\partial f(\\mathbf{x}^\\star)$. That subgradients *exist* is\n",
    "the one fact this section takes on faith:\n",
    "\n",
    "**Granted fact (supporting hyperplane).** *A convex $f$ has at least one\n",
    "subgradient at every interior point of its domain; geometrically, a supporting\n",
    "line (a supporting hyperplane, in $n$ dimensions) fits under the graph. We take\n",
    "this on faith; see [@Rockafellar.1970] (or @Boyd.Vandenberghe.2004,\n",
    "section 2.5).*\n",
    "\n",
    "Subgradients preserve the supporting-hyperplane, Jensen, and\n",
    "local-equals-global arguments at ReLU-style kinks. Optimization algorithms need\n",
    "their own analysis: a subgradient step need not decrease the objective, and the\n",
    "standard subgradient method uses diminishing steps and has slower rates than\n",
    "smooth gradient descent.\n",
    "\n",
    "![At the kink of $f(x) = |x|$ the gradient does not exist, but the subgradient fans out into a set: every slope $g \\in \\left(-1, 1\\right)$ tucks a supporting line under the V, and the two extreme slopes $\\pm 1$ lie along the branches themselves, so $\\partial f(0)$ is the whole interval from $-1$ to $1$. The zero-slope member (orange) is the optimality certificate $0 \\in \\partial f(0)$: the corner is a provable minimum, no gradient required.](../img/mdl-opt-subgradient-fan.svg)\n",
    "\n",
    "### Checking the Lenses Numerically\n",
    "\n",
    "Theory says the three lenses certify the same functions; the code checks all\n",
    "three on the least-squares loss\n",
    "$f(\\mathbf{w}) = \\tfrac12\\|X\\mathbf{w} - \\mathbf{y}\\|^2$ in two weights:\n",
    "random chords, random tangents, and the eigenvalues of the Hessian."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "convexity-three-lenses"
   },
   "source": [
    "rng = np.random.default_rng(0)\n",
    "X = rng.normal(size=(20, 2))                   # design matrix, 20 points\n",
    "y = rng.normal(size=20)\n",
    "f = lambda w: 0.5 * ((X @ w - y) ** 2).sum()\n",
    "grad = lambda w: X.T @ (X @ w - y)\n",
    "worst_chord, worst_tangent = -np.inf, -np.inf\n",
    "for _ in range(1000):\n",
    "    u, v = rng.normal(size=(2, 2)) * 3.0       # random pair of weight vectors\n",
    "    t = rng.uniform()\n",
    "    worst_chord = max(worst_chord,             # f(chord point) - chord height\n",
    "                      f(t * u + (1 - t) * v) - (t * f(u) + (1 - t) * f(v)))\n",
    "    worst_tangent = max(worst_tangent,         # tangent value - f\n",
    "                        f(u) + grad(u) @ (v - u) - f(v))\n",
    "print(f'worst chord violation over 1000 trials:   {worst_chord:.2e}')\n",
    "print(f'worst tangent violation over 1000 trials: {worst_tangent:.2e}')\n",
    "print('Hessian eigenvalues:', np.linalg.eigvalsh(X.T @ X).round(4))"
   ],
   "execution_count": 2,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "worst chord violation over 1000 trials:   -2.46e-03\nworst tangent violation over 1000 trials: -4.95e-02\nHessian eigenvalues: [ 6.273  18.6557]\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-convexity-md-3 fw=all -->\n",
    "\n",
    "All three lenses report the same verdict. The worst chord \"violation\" across a\n",
    "thousand random trials is $-2.46 \\times 10^{-3}$ and the worst tangent\n",
    "violation is $-4.95 \\times 10^{-2}$, both *negative*, meaning the graph\n",
    "stayed below every sampled chord and above every sampled tangent with room to\n",
    "spare; and the Hessian's eigenvalues, $6.273$ and $18.6557$, are positive.\n",
    "(Sampling can only ever refute convexity, never prove it; the Hessian check is\n",
    "the one that constitutes a proof, since $X^\\top X$ is the same matrix at every\n",
    "$\\mathbf{w}$.)\n",
    "\n",
    "## Jensen's Inequality\n",
    "\n",
    "The chord definition compares $f$ at a two-point average against the average of\n",
    "$f$ at the two points. Nothing about the argument is special to *two*: applying\n",
    "the equation repeatedly (Exercise 4) gives the finite form\n",
    "\n",
    "$$\n",
    "f\\left(\\sum_i \\theta_i \\mathbf{x}_i\\right) \\;\\le\\; \\sum_i \\theta_i\\, f(\\mathbf{x}_i),\n",
    "\\qquad \\theta_i \\ge 0,\\ \\sum_i \\theta_i = 1,\n",
    "$$\n",
    "\n",
    "and a set of nonnegative weights summing to one is exactly a probability\n",
    "distribution. The full generalization replaces averages by expectations; the\n",
    "probabilistic chapters of this book use it constantly.\n",
    "\n",
    "**Proposition (Jensen's inequality).** *Let $f$ be convex and let $X$ be a\n",
    "random vector taking values in $f$'s domain, with $\\mathbb{E}[X]$ finite and in\n",
    "the domain's interior, and read $\\mathbb{E}[f(X)]$ as an extended real number\n",
    "(the value $+\\infty$ is allowed, and makes the inequality trivially true).\n",
    "Then*\n",
    "\n",
    "$$\n",
    "f\\left(\\mathbb{E}[X]\\right) \\;\\le\\; \\mathbb{E}\\left[f(X)\\right].\n",
    "$$\n",
    "\n",
    "*If $f$ is strictly convex, equality holds if and only if $X = \\mathbb{E}[X]$\n",
    "almost surely.*\n",
    "\n",
    "**Proof.** Let $\\boldsymbol{\\mu} = \\mathbb{E}[X]$ and pick a subgradient\n",
    "$\\mathbf{g} \\in \\partial f(\\boldsymbol{\\mu})$; the granted fact (supporting\n",
    "hyperplane) provides one at an interior point. The supporting-line inequality\n",
    "the equation holds\n",
    "pointwise for every outcome:\n",
    "\n",
    "$$\n",
    "f(X) \\;\\ge\\; f(\\boldsymbol{\\mu}) + \\mathbf{g}^\\top (X - \\boldsymbol{\\mu}).\n",
    "$$\n",
    "\n",
    "Take expectations of both sides: the linear term has mean zero, leaving\n",
    "$\\mathbb{E}[f(X)] \\ge f(\\boldsymbol{\\mu})$. For strictly convex $f$ the\n",
    "supporting line touches the graph only at $\\boldsymbol{\\mu}$: if it also\n",
    "touched at some $\\mathbf{x} \\neq \\boldsymbol{\\mu}$, strict convexity at the\n",
    "midpoint would force\n",
    "$f\\bigl(\\tfrac{\\mathbf{x} + \\boldsymbol{\\mu}}{2}\\bigr)\n",
    "< \\tfrac12 f(\\mathbf{x}) + \\tfrac12 f(\\boldsymbol{\\mu})$, which equals the\n",
    "(affine) supporting line's value there, contradicting that the line\n",
    "under-estimates $f$ everywhere. So the pointwise\n",
    "inequality is strict on the event $X \\neq \\boldsymbol{\\mu}$; equality in\n",
    "expectation therefore forces that event to have probability zero. $\\blacksquare$\n",
    "\n",
    "Two ingredients, and notice *which* two: the first-order lens (in subgradient\n",
    "form, so no smoothness is needed) plus linearity of expectation. A mnemonic for the\n",
    "direction: the graph bends upward, so spreading $X$ out can only push the\n",
    "average of $f(X)$ up; *the function of the mean undershoots the mean of the\n",
    "function*. For concave $f$ the inequality flips:\n",
    "$\\mathbb{E}[f(X)] \\le f(\\mathbb{E}[X])$.\n",
    "\n",
    "The corollary that information theory is built on follows immediately.\n",
    "that section, the KL divergence's definitional home\n",
    "(with its $0 \\log 0$ and support conventions), restates it as Gibbs'\n",
    "inequality and builds the\n",
    "entropy ceiling $H(X) \\le \\log k$ and the nonnegativity of mutual information\n",
    "on it.\n",
    "\n",
    "**Corollary (nonnegativity of KL divergence).** *For probability distributions\n",
    "$p$ and $q$ on a common finite alphabet (with $q(x) > 0$ where $p(x) > 0$),*\n",
    "\n",
    "$$\n",
    "D_{\\mathrm{KL}}(p \\,\\|\\, q) \\;=\\; \\sum_x p(x) \\log \\frac{p(x)}{q(x)} \\;\\ge\\; 0,\n",
    "$$\n",
    "\n",
    "*with equality if and only if $p = q$.*\n",
    "\n",
    "**Proof.** Apply Jensen's inequality to the strictly convex function $-\\log$\n",
    "and the random variable $R = q(X)/p(X)$ with $X \\sim p$:\n",
    "\n",
    "$$\n",
    "D_{\\mathrm{KL}}(p \\,\\|\\, q)\n",
    "= \\mathbb{E}_p\\left[-\\log R\\right]\n",
    "\\;\\ge\\; -\\log \\mathbb{E}_p[R]\n",
    "= -\\log \\sum_{x : p(x) > 0} p(x)\\, \\frac{q(x)}{p(x)}\n",
    "\\;\\ge\\; -\\log 1 = 0,\n",
    "$$\n",
    "\n",
    "since $\\sum_{x : p(x) > 0} q(x) \\le 1$. By the equality case, the bound is tight\n",
    "iff $R$ is almost surely constant and the $q$-mass off $p$'s support is zero,\n",
    "i.e., $q = c\\,p$ with $c = 1$: $p = q$. $\\blacksquare$\n",
    "\n",
    "The same one-liner with the concave $\\log$ yields the classical\n",
    "**arithmetic--geometric mean inequality**: for positive $x_1, \\ldots, x_n$,\n",
    "concavity gives\n",
    "$\\log\\bigl(\\tfrac1n \\sum_i x_i\\bigr) \\ge \\tfrac1n \\sum_i \\log x_i$, and\n",
    "exponentiating,\n",
    "\n",
    "$$\n",
    "\\frac{1}{n} \\sum_{i=1}^n x_i \\;\\ge\\; \\left(\\prod_{i=1}^n x_i\\right)^{1/n},\n",
    "$$\n",
    "\n",
    "with equality iff all $x_i$ coincide ($\\log$ is strictly concave). Jensen also\n",
    "explains a gap you have already trained on: the evidence lower bound of\n",
    "that section is Jensen applied to the concave $\\log$ of an\n",
    "expectation, and the slack in the ELBO *is* the Jensen gap. The cell makes the\n",
    "inequality concrete three ways: a Monte Carlo estimate of\n",
    "$\\mathbb{E}[e^X]$ versus $e^{\\mathbb{E}[X]}$, a bulk test of AM--GM, and the\n",
    "KL corollary on a thousand random distribution pairs."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "convexity-jensen-mc"
   },
   "source": [
    "rng = np.random.default_rng(1)\n",
    "z = rng.normal(size=1_000_000)                 # X ~ N(0, 1)\n",
    "print(f'E[exp(X)] = {np.exp(z).mean():.4f}  vs  exp(E[X]) = {np.exp(z.mean()):.4f}'\n",
    "      f'  (theory: sqrt(e) = {np.exp(0.5):.4f} vs 1)')\n",
    "u = rng.uniform(0.1, 10.0, size=(100_000, 5))  # AM-GM from concavity of log\n",
    "am, gm = u.mean(axis=1), np.exp(np.log(u).mean(axis=1))\n",
    "print(f'AM >= GM in all trials: {bool((am >= gm).all())},'\n",
    "      f'  smallest AM/GM ratio = {(am / gm).min():.4f}')\n",
    "p = rng.dirichlet(np.ones(10), size=1000)      # 1000 random distribution pairs\n",
    "q = rng.dirichlet(np.ones(10), size=1000)\n",
    "print(f'min KL(p||q) = {(p * np.log(p / q)).sum(axis=1).min():.4f} >= 0,'\n",
    "      f'  max |KL(p||p)| = {np.abs((p * np.log(p / p)).sum(axis=1)).max():.1e}')"
   ],
   "execution_count": 3,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "E[exp(X)] = 1.6466  vs  exp(E[X]) = 0.9998  (theory: sqrt(e) = 1.6487 vs 1)\nAM >= GM in all trials: True,  smallest AM/GM ratio = 1.0002\nmin KL(p||q) = 0.1331 >= 0,  max |KL(p||p)| = 0.0e+00\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-convexity-md-4 fw=all -->\n",
    "\n",
    "With $X \\sim \\mathcal{N}(0, 1)$ and the convex $f(x) = e^x$, a million samples\n",
    "give $\\mathbb{E}[e^X] \\approx 1.6466$ against\n",
    "$e^{\\mathbb{E}[X]} \\approx 0.9998$; the true values are\n",
    "$\\sqrt{e} \\approx 1.6487$ and $1$, a Jensen gap of $0.65$ that no amount of\n",
    "sampling will close, because it is geometry, not noise. AM $\\ge$ GM holds in\n",
    "all $10^5$ random draws (smallest ratio $1.0002$), and across a thousand random\n",
    "pairs of distributions on ten symbols the smallest KL divergence is $0.1331$,\n",
    "comfortably nonnegative, while $D_{\\mathrm{KL}}(p\\,\\|\\,p)$ prints as\n",
    "`0.0e+00`: the equality case, exact at machine resolution.\n",
    "\n",
    "## Why Convexity Matters\n",
    "\n",
    "### Every Local Minimum Is Global\n",
    "\n",
    "Here is the central theorem of the section, with the picture first.\n",
    "the figure shows why convexity is the dividing\n",
    "line for optimization. On a convex objective, gradient descent reaches the\n",
    "single global minimum no matter where it starts; on a non-convex objective the\n",
    "same algorithm slides into whichever basin it happens to start in, separated by\n",
    "a saddle, and the local minimum on one side is *not* the global one.\n",
    "\n",
    "![Why convexity matters. Left: a convex objective has one global minimum, and gradient descent from any start reaches it. Right: a non-convex objective with two local minima separated by a saddle; gradient descent lands in different minima depending on its starting point, so a local minimum need not be global.](../img/mdl-opt-local-equals-global.svg)\n",
    "\n",
    "**Proposition (local minima are global).** *Let $f$ be convex on a convex set\n",
    "$C$ and let $\\mathbf{x}^\\star$ be a local minimum: $f(\\mathbf{x}^\\star) \\le f(\\mathbf{z})$\n",
    "for all feasible $\\mathbf{z}$ within some radius $r > 0$ of $\\mathbf{x}^\\star$.\n",
    "Then $f(\\mathbf{x}^\\star) \\le f(\\mathbf{y})$ for* every *$\\mathbf{y} \\in C$.\n",
    "Moreover the set of minimizers is convex, and if $f$ is differentiable on open\n",
    "$C$, then any stationary point ($\\nabla f = \\mathbf{0}$) is a global minimum.*\n",
    "\n",
    "**Proof.** Take any $\\mathbf{y} \\in C$ and slide from $\\mathbf{x}^\\star$ toward\n",
    "it: for small $\\theta > 0$ the point\n",
    "$\\mathbf{z}_\\theta = (1 - \\theta)\\mathbf{x}^\\star + \\theta\\mathbf{y}$ is\n",
    "feasible (convexity of $C$) and within $r$ of $\\mathbf{x}^\\star$, so local\n",
    "minimality and the chord inequality give\n",
    "\n",
    "$$\n",
    "f(\\mathbf{x}^\\star) \\;\\le\\; f(\\mathbf{z}_\\theta)\n",
    "\\;\\le\\; (1 - \\theta) f(\\mathbf{x}^\\star) + \\theta f(\\mathbf{y}).\n",
    "$$\n",
    "\n",
    "Subtract $(1-\\theta)f(\\mathbf{x}^\\star)$ and divide by $\\theta$:\n",
    "$f(\\mathbf{x}^\\star) \\le f(\\mathbf{y})$. The minimizer set is the sublevel set\n",
    "$\\{\\mathbf{x} \\in C : f(\\mathbf{x}) \\le f^\\star\\}$, and every sublevel set of a\n",
    "convex function is convex by the chord inequality. The stationary-point claim is\n",
    "the equation read at $\\mathbf{x}$ with\n",
    "$\\nabla f(\\mathbf{x}) = \\mathbf{0}$. $\\blacksquare$\n",
    "\n",
    "Read the proof's geometry: a convex function cannot ambush you. If anywhere in\n",
    "the domain there were a strictly better point, the chord toward it would already\n",
    "be descending *inside your local neighborhood*, so \"no local improvement\"\n",
    "instantly means \"no improvement anywhere.\" Saddle points and spurious basins,\n",
    "the failure modes that haunt deep loss surfaces, are structurally impossible.\n",
    "One more consequence follows:\n",
    "\n",
    "**Proposition (uniqueness).** *A strictly convex $f$ has at most one minimizer;\n",
    "a continuous, strongly convex $f$ on a closed convex set has exactly one.*\n",
    "\n",
    "**Proof.** If $\\mathbf{x} \\neq \\mathbf{y}$ were both minimizers with value\n",
    "$f^\\star$, the strict chord inequality at $\\theta = \\tfrac12$ would give\n",
    "$f\\bigl(\\tfrac{\\mathbf{x} + \\mathbf{y}}{2}\\bigr) < f^\\star$, a contradiction.\n",
    "Strong convexity adds existence. Write $f = h + \\tfrac{\\mu}{2}\\|\\cdot\\|^2$ with\n",
    "$h$ convex, fix an interior point $\\mathbf{x}_0$ and a subgradient\n",
    "$\\mathbf{g} \\in \\partial h(\\mathbf{x}_0)$ (the granted fact supplies one), and\n",
    "add the quadratic back: expanding\n",
    "$\\|\\mathbf{y}\\|^2 = \\|\\mathbf{x}_0\\|^2 + 2\\mathbf{x}_0^\\top(\\mathbf{y} - \\mathbf{x}_0) + \\|\\mathbf{y} - \\mathbf{x}_0\\|^2$\n",
    "turns $h(\\mathbf{y}) \\ge h(\\mathbf{x}_0) + \\mathbf{g}^\\top(\\mathbf{y} - \\mathbf{x}_0)$\n",
    "into\n",
    "\n",
    "$$\n",
    "f(\\mathbf{y}) \\;\\ge\\; f(\\mathbf{x}_0)\n",
    "+ (\\mathbf{g} + \\mu\\mathbf{x}_0)^\\top (\\mathbf{y} - \\mathbf{x}_0)\n",
    "+ \\frac{\\mu}{2}\\, \\|\\mathbf{y} - \\mathbf{x}_0\\|^2,\n",
    "$$\n",
    "\n",
    "the subgradient form of the equation, valid with no\n",
    "differentiability assumed. So $f$ grows at least quadratically away from\n",
    "$\\mathbf{x}_0$ and its sublevel sets are bounded; a continuous function on a\n",
    "closed bounded set attains its minimum. $\\blacksquare$\n",
    "\n",
    "The continuity hypothesis is automatic in the interior, where convex functions\n",
    "are always continuous; it matters only at the boundary of the closed\n",
    "set, where a convex function may jump upward and the minimum can fail to be\n",
    "attained.\n",
    "\n",
    "The code runs the dividing line as an experiment: the same gradient-descent\n",
    "loop, the same step size, the same $500$ random starting points, on a convex\n",
    "bowl $f(x) = (x - \\tfrac12)^2$ and on the tilted double well\n",
    "$g(x) = (x^2 - 1)^2 + x/2$."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "convexity-basins"
   },
   "source": [
    "def gd(grad_fn, x, eta=0.05, steps=600):\n",
    "    for _ in range(steps):\n",
    "        x = x - eta * grad_fn(x)\n",
    "    return x\n",
    "\n",
    "rng = np.random.default_rng(2)\n",
    "inits = rng.uniform(-1.5, 1.5, size=500)       # 500 random starting points\n",
    "bowl = gd(lambda x: 2 * (x - 0.5), inits)      # convex: f(x) = (x - 1/2)^2\n",
    "g = lambda x: (x**2 - 1)**2 + 0.5 * x          # non-convex: tilted double well\n",
    "well = gd(lambda x: 4 * x * (x**2 - 1) + 0.5, inits)\n",
    "left, right = well[well < 0], well[well > 0]\n",
    "print(f'convex bowl: all {bowl.size} runs end at x = {bowl.mean():.6f}'\n",
    "      f'  (spread {np.ptp(bowl):.1e})')\n",
    "print(f'double well: {left.size} runs -> x = {left.mean():.4f}'\n",
    "      f'  (g = {g(left.mean()):.4f})')\n",
    "print(f'             {right.size} runs -> x = {right.mean():.4f}'\n",
    "      f'  (g = {g(right.mean()):.4f})')"
   ],
   "execution_count": 4,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "convex bowl: all 500 runs end at x = 0.500000  (spread 6.7e-16)\ndouble well: 271 runs -> x = -1.0575  (g = -0.5148)\n             229 runs -> x = 0.9304  (g = 0.4833)\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-convexity-md-5 fw=all -->\n",
    "\n",
    "On the bowl, all $500$ runs collapse onto $x = 0.5$ with a spread of\n",
    "$6.7 \\times 10^{-16}$, machine epsilon; the histogram of outcomes is a single\n",
    "spike. On the double well the histogram has two bars: $271$ runs find the global\n",
    "minimum at $x \\approx -1.06$ with $g \\approx -0.515$, while the other $229$ are\n",
    "captured by the local minimum at $x \\approx 0.93$ with $g \\approx 0.483$,\n",
    "nearly a full unit worse, and no amount of further descent will fix it. Nothing\n",
    "about the *algorithm* changed between the two lines; convexity is a property of\n",
    "the objective, and it alone decides whether the starting point matters.\n",
    "\n",
    "### From Local Steps to Global Rates\n",
    "\n",
    "that section proved the **descent lemma**\n",
    "the equation: for $L$-smooth $f$, the gradient step\n",
    "$\\mathbf{x}_{t+1} = \\mathbf{x}_t - \\tfrac{1}{L} \\nabla f(\\mathbf{x}_t)$\n",
    "achieves\n",
    "$f(\\mathbf{x}_{t+1}) \\le f(\\mathbf{x}_t) - \\tfrac{1}{2L} \\|\\nabla f(\\mathbf{x}_t)\\|^2$.\n",
    "By itself this guarantees only that gradients eventually vanish, a\n",
    "*stationary* point, which in general may be a saddle or a poor local minimum.\n",
    "Convexity upgrades the guarantee from \"somewhere flat\" to \"the global optimum,\n",
    "this fast.\" The next two theorems are the main results of the section, and both\n",
    "proofs are short enough to carry with you [@Nesterov.2018].\n",
    "\n",
    "**Proposition (gradient descent on smooth convex functions).** *Let $f$ be\n",
    "convex and $L$-smooth with a minimizer $\\mathbf{x}^\\star$. Gradient descent with\n",
    "$\\eta = 1/L$ satisfies, for every $k \\ge 1$,*\n",
    "\n",
    "$$\n",
    "f(\\mathbf{x}_k) - f(\\mathbf{x}^\\star) \\;\\le\\; \\frac{L\\, \\|\\mathbf{x}_0 - \\mathbf{x}^\\star\\|^2}{2k}.\n",
    "$$\n",
    "\n",
    "**Proof.** Chain the descent lemma into the first-order lens\n",
    "the equation aimed at the optimum,\n",
    "$f(\\mathbf{x}_t) - f(\\mathbf{x}^\\star) \\le \\nabla f(\\mathbf{x}_t)^\\top(\\mathbf{x}_t - \\mathbf{x}^\\star)$:\n",
    "\n",
    "$$\n",
    "f(\\mathbf{x}_{t+1}) - f(\\mathbf{x}^\\star)\n",
    "\\;\\le\\; \\nabla f(\\mathbf{x}_t)^\\top (\\mathbf{x}_t - \\mathbf{x}^\\star) - \\frac{1}{2L} \\|\\nabla f(\\mathbf{x}_t)\\|^2.\n",
    "$$\n",
    "\n",
    "Completing the square turns the right side into a difference of distances:\n",
    "\n",
    "$$\n",
    "\\nabla f(\\mathbf{x}_t)^\\top (\\mathbf{x}_t - \\mathbf{x}^\\star) - \\frac{1}{2L} \\|\\nabla f(\\mathbf{x}_t)\\|^2\n",
    "= \\frac{L}{2} \\left( \\|\\mathbf{x}_t - \\mathbf{x}^\\star\\|^2\n",
    "- \\left\\|\\mathbf{x}_t - \\mathbf{x}^\\star - \\tfrac{1}{L}\\nabla f(\\mathbf{x}_t)\\right\\|^2 \\right),\n",
    "$$\n",
    "\n",
    "and the second norm is exactly $\\|\\mathbf{x}_{t+1} - \\mathbf{x}^\\star\\|^2$.\n",
    "Summing over $t = 0, \\ldots, k-1$, the right side telescopes:\n",
    "\n",
    "$$\n",
    "\\sum_{t=0}^{k-1} \\left( f(\\mathbf{x}_{t+1}) - f(\\mathbf{x}^\\star) \\right)\n",
    "\\;\\le\\; \\frac{L}{2} \\left( \\|\\mathbf{x}_0 - \\mathbf{x}^\\star\\|^2 - \\|\\mathbf{x}_k - \\mathbf{x}^\\star\\|^2 \\right)\n",
    "\\;\\le\\; \\frac{L}{2}\\, \\|\\mathbf{x}_0 - \\mathbf{x}^\\star\\|^2.\n",
    "$$\n",
    "\n",
    "The descent lemma makes $f(\\mathbf{x}_t)$ nonincreasing, so the last term of the\n",
    "sum is the smallest: $k \\left(f(\\mathbf{x}_k) - f(\\mathbf{x}^\\star)\\right)$ is at\n",
    "most the sum, which gives the equation. $\\blacksquare$\n",
    "\n",
    "Two remarks. The bound is *dimension-free*: a million parameters cost no more\n",
    "iterations than two, one reason first-order methods scale to\n",
    "neural networks. And the telescoping display has a bonus reading: every bracket\n",
    "is nonnegative (its left factor is $f(\\mathbf{x}_{t+1}) - f^\\star \\ge 0$), so\n",
    "$\\|\\mathbf{x}_t - \\mathbf{x}^\\star\\|$ never increases: the iterates march\n",
    "monotonically closer to the optimum.\n",
    "\n",
    "With strong convexity, the sublinear $O(1/k)$ sharpens to a geometric decay.\n",
    "\n",
    "**Proposition (linear rate under strong convexity).** *Let $f$ be\n",
    "$\\mu$-strongly convex and $L$-smooth, with minimizer $\\mathbf{x}^\\star$.\n",
    "Gradient descent with $\\eta = 1/L$ satisfies*\n",
    "\n",
    "$$\n",
    "f(\\mathbf{x}_k) - f(\\mathbf{x}^\\star)\n",
    "\\;\\le\\; \\left(1 - \\frac{\\mu}{L}\\right)^{k} \\left( f(\\mathbf{x}_0) - f(\\mathbf{x}^\\star) \\right).\n",
    "$$\n",
    "\n",
    "**Proof.** First, strong convexity links the gradient's size to the remaining\n",
    "suboptimality. Minimize both sides of the equation over\n",
    "$\\mathbf{y}$: the left side's infimum is $f(\\mathbf{x}^\\star)$, and the right\n",
    "side is a quadratic in $\\mathbf{y}$ minimized at\n",
    "$\\mathbf{y} = \\mathbf{x} - \\tfrac{1}{\\mu}\\nabla f(\\mathbf{x})$, where it equals\n",
    "$f(\\mathbf{x}) - \\tfrac{1}{2\\mu}\\|\\nabla f(\\mathbf{x})\\|^2$. Hence\n",
    "\n",
    "$$\n",
    "\\frac12\\, \\|\\nabla f(\\mathbf{x})\\|^2 \\;\\ge\\; \\mu \\left( f(\\mathbf{x}) - f(\\mathbf{x}^\\star) \\right)\n",
    "\\qquad \\textrm{for all } \\mathbf{x}.\n",
    "$$\n",
    "\n",
    "Now feed the equation into the descent lemma:\n",
    "\n",
    "$$\n",
    "f(\\mathbf{x}_{t+1}) - f(\\mathbf{x}^\\star)\n",
    "\\;\\le\\; f(\\mathbf{x}_t) - f(\\mathbf{x}^\\star) - \\frac{1}{2L} \\|\\nabla f(\\mathbf{x}_t)\\|^2\n",
    "\\;\\le\\; \\left(1 - \\frac{\\mu}{L}\\right) \\left( f(\\mathbf{x}_t) - f(\\mathbf{x}^\\star) \\right),\n",
    "$$\n",
    "\n",
    "and iterate $k$ times. $\\blacksquare$\n",
    "\n",
    "The contraction factor is $1 - 1/\\kappa$ with $\\kappa = L/\\mu$ the condition\n",
    "number: reaching accuracy $\\epsilon$ costs $O(\\kappa \\log(1/\\epsilon))$\n",
    "iterations, against $O(1/\\epsilon)$ without strong convexity. This is the\n",
    "global, every-start version of the per-mode contraction that\n",
    "that section measured on quadratics. File away\n",
    "one observation for the end of this section: the second half of the proof\n",
    "never used convexity at all. It consumed only the inequality\n",
    "the equation, a fact we will exploit when convexity itself is gone.\n",
    "\n",
    "Both rates can be measured. The cell runs gradient descent at $\\eta = 1/L$ on\n",
    "the least-squares\n",
    "toy of the `#convexity-three-lenses` cell (strongly convex, with $\\mu$ and\n",
    "$L$ read off the eigenvalues of $X^\\top X$) and prints the per-step\n",
    "contraction of $f - f^\\star$ next to the theorem's promise:"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "convexity-rate-check"
   },
   "source": [
    "mu, L = np.linalg.eigvalsh(X.T @ X)[[0, -1]]   # curvature floor and ceiling\n",
    "w_star = np.linalg.solve(X.T @ X, X.T @ y)     # the unique minimizer\n",
    "w, gaps = np.zeros(2), []\n",
    "for _ in range(25):                            # gradient descent at eta = 1/L\n",
    "    w -= grad(w) / L\n",
    "    gaps.append(f(w) - f(w_star))\n",
    "r = np.array(gaps[1:]) / np.array(gaps[:-1])\n",
    "print(f'mu = {mu:.4f}, L = {L:.4f}:  the theorem promises '\n",
    "      f'contraction <= 1 - mu/L = {1 - mu / L:.4f}')\n",
    "print('measured per-step contraction of f - f*:', r[::6].round(4))\n",
    "print(f'worst step: {r.max():.4f}  (the bound holds at every step)')"
   ],
   "execution_count": 5,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "mu = 6.2730, L = 18.6557:  the theorem promises contraction <= 1 - mu/L = 0.6637\nmeasured per-step contraction of f - f*: [0.4406 0.4406 0.4406 0.4406]\nworst step: 0.4406  (the bound holds at every step)\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-convexity-md-6 fw=all -->\n",
    "\n",
    "The measured contraction is $0.4406$ at every step, safely inside the promised\n",
    "$1 - \\mu/L = 0.6637$, and the gap between the two is itself informative. On\n",
    "a pure quadratic the slow mode's *distance* to the optimum contracts by\n",
    "exactly $1 - \\mu/L$ per step, and the value gap, being quadratic in the\n",
    "distance, contracts by its square: $(1 - \\mu/L)^2 = 0.4406$, precisely the\n",
    "printed figure. So the theorem's bound is valid across the whole smooth\n",
    "strongly convex class, but on quadratics it is loose by exactly a square. On\n",
    "any particular function you may contract faster than the bound, never slower.\n",
    "\n",
    "## Recognizing Convexity and Its Limits\n",
    "\n",
    "### A Calculus of Convex Functions\n",
    "\n",
    "Most convexity proofs in practice are assembled from parts rather than computed\n",
    "from Hessians: a small set of operations preserves convexity, and\n",
    "real losses are built from convex atoms by exactly these operations.\n",
    "\n",
    "1. **Nonnegative weighted sums.** If $f_1, \\ldots, f_m$ are convex and\n",
    "   $w_i \\ge 0$, then $\\sum_i w_i f_i$ is convex: multiply the chord inequality\n",
    "   for each $f_i$ by $w_i$ and add. (An average of losses over a training set is\n",
    "   a nonnegative weighted sum.)\n",
    "2. **Affine pre-composition.** If $f$ is convex then so is\n",
    "   $\\mathbf{x} \\mapsto f(A\\mathbf{x} + \\mathbf{b})$: affine maps send the\n",
    "   segment between $\\mathbf{x}$ and $\\mathbf{y}$ to the segment between their\n",
    "   images, with the same $\\theta$, so the chord inequality transfers verbatim.\n",
    "   (A loss that is convex in a model's *output* is convex in the *weights of a\n",
    "   linear model* producing that output.)\n",
    "3. **Pointwise maximum and supremum.** If each $f_i$ is convex, so is\n",
    "   $\\max_i f_i$, and the proof is the epigraph dictionary in action: the\n",
    "   epigraph of a max is the *intersection* of the epigraphs, and intersections\n",
    "   of convex sets are convex. The upper envelope of any family of lines is\n",
    "   convex, however large the family.\n",
    "4. **Monotone convex composition.** If $g$ is convex and $h$ is convex *and\n",
    "   nondecreasing*, then $h(g(\\mathbf{x}))$ is convex (in one dimension:\n",
    "   $(h \\circ g)'' = h''(g)\\,(g')^2 + h'(g)\\, g'' \\ge 0$, each summand\n",
    "   nonnegative). The monotonicity hypothesis is essential:\n",
    "   $h(t) = t^2$ and $g(x) = x^2 - 1$ compose to the double well we just watched\n",
    "   trap gradient descent.\n",
    "\n",
    "This calculus certifies most of the convex losses in this book in one line\n",
    "each. The hinge loss $\\max(0, 1 - y\\,\\mathbf{w}^\\top\\mathbf{x})$ is a maximum\n",
    "of two affine functions of $\\mathbf{w}$ (rules 3 and 2). The $\\ell_1$ norm\n",
    "$\\|\\mathbf{w}\\|_1 = \\sum_i \\max(w_i, -w_i)$ is a sum of maxima of affine\n",
    "functions (rules 1, 3, 2). The logistic loss\n",
    "$\\log(1 + e^{-y\\,\\mathbf{w}^\\top\\mathbf{x}})$ is the convex\n",
    "$t \\mapsto \\log(1 + e^t)$ (second derivative\n",
    "$\\sigma'(t) = \\sigma(t)(1-\\sigma(t)) > 0$) pre-composed with an affine map, then\n",
    "summed over data. Ridge-regularized anything is \"convex plus\n",
    "$\\lambda$-strongly convex,\" hence strongly convex (rule 1 applied to\n",
    "the equation). The one absence from the\n",
    "list, compositions with *nonlinear, non-monotone* inner maps, is where\n",
    "deep networks will exit the theory below.\n",
    "\n",
    "### Log-Sum-Exp and the Softmax Covariance\n",
    "\n",
    "The canonical worked case, the function behind every softmax cross-entropy\n",
    "loss, deserves its own proposition. Define\n",
    "$\\mathrm{lse}(\\mathbf{x}) = \\log \\sum_{i=1}^n e^{x_i}$, the smooth maximum of\n",
    "that section.\n",
    "\n",
    "**Proposition (log-sum-exp is convex).** *The Hessian of $\\mathrm{lse}$ at\n",
    "$\\mathbf{x}$ is*\n",
    "\n",
    "$$\n",
    "\\nabla^2 \\mathrm{lse}(\\mathbf{x}) = \\mathrm{diag}(\\mathbf{s}) - \\mathbf{s}\\mathbf{s}^\\top,\n",
    "\\qquad \\mathbf{s} = \\mathrm{softmax}(\\mathbf{x}),\n",
    "$$\n",
    "\n",
    "*which is the covariance matrix of the one-hot encoding of a class drawn from\n",
    "$\\mathbf{s}$, hence PSD, hence $\\mathrm{lse}$ is convex.*\n",
    "\n",
    "**Proof.** Differentiating once gives\n",
    "$\\partial\\, \\mathrm{lse} / \\partial x_i = e^{x_i} / \\sum_j e^{x_j} = s_i$: the\n",
    "gradient of $\\mathrm{lse}$ *is* the softmax. Differentiating again gives the\n",
    "softmax Jacobian the equation, derived in\n",
    "that section, which is the claimed\n",
    "matrix. Now let $I$ be a random index with $\\Pr(I = i) = s_i$ and let\n",
    "$\\mathbf{e}_I$ be its one-hot vector. Then\n",
    "$\\mathbb{E}[\\mathbf{e}_I] = \\mathbf{s}$ and\n",
    "$\\mathbb{E}[\\mathbf{e}_I \\mathbf{e}_I^\\top] = \\mathrm{diag}(\\mathbf{s})$, so\n",
    "$\\mathrm{Cov}(\\mathbf{e}_I) = \\mathrm{diag}(\\mathbf{s}) - \\mathbf{s}\\mathbf{s}^\\top$\n",
    "is exactly the Hessian. Covariances are PSD; directly,\n",
    "\n",
    "$$\n",
    "\\mathbf{v}^\\top \\nabla^2 \\mathrm{lse}\\, \\mathbf{v}\n",
    "= \\sum_i s_i v_i^2 - \\left(\\sum_i s_i v_i\\right)^2\n",
    "= \\mathbb{E}\\left[v_I^2\\right] - \\left(\\mathbb{E}[v_I]\\right)^2\n",
    "= \\mathrm{Var}(v_I) \\;\\ge\\; 0. \\;\\blacksquare\n",
    "$$\n",
    "\n",
    "The corollary you use daily: the cross-entropy loss *in the logits*,\n",
    "$\\ell(\\mathbf{z}) = \\mathrm{lse}(\\mathbf{z}) - z_y$ for true class $y$, is\n",
    "log-sum-exp plus an affine function, hence convex. Softmax regression\n",
    "(that section) composes it with the affine map\n",
    "$\\mathbf{z} = W\\mathbf{x} + \\mathbf{b}$, so the loss is convex in the weights\n",
    "(rule 2): the last layer of a classifier is always a convex problem, whatever\n",
    "the features feeding it. The same softmax machinery is also the core of\n",
    "attention: a head's weights are exactly this map applied to scaled\n",
    "query--key scores (that section), with the same\n",
    "Jacobian $\\mathrm{diag}(\\mathbf{s}) - \\mathbf{s}\\mathbf{s}^\\top$ appearing in\n",
    "its backward pass. The Hessian formula also predicts one *zero*\n",
    "eigenvalue, in the direction $\\mathbf{1}$: a variance $\\mathrm{Var}(v_I)$\n",
    "vanishes when $v$ is constant, which is the shift invariance\n",
    "$\\mathrm{lse}(\\mathbf{x} + c\\mathbf{1}) = \\mathrm{lse}(\\mathbf{x}) + c$, the\n",
    "very identity that powers the numerically stable softmax of\n",
    "that section. The cell verifies all of it:\n",
    "the eigenvalues, the covariance identity by Monte Carlo, and the flat direction."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "convexity-lse-hessian"
   },
   "source": [
    "lse = lambda x: x.max() + np.log(np.exp(x - x.max()).sum())\n",
    "rng = np.random.default_rng(3)\n",
    "x = rng.normal(size=6)                         # six logits\n",
    "s = np.exp(x - lse(x))                         # softmax(x)\n",
    "H = np.diag(s) - np.outer(s, s)                # analytic Hessian of lse\n",
    "print('eigenvalues of H:', np.linalg.eigvalsh(H).round(6))\n",
    "draws = rng.choice(len(x), size=200_000, p=s)  # class I ~ Categorical(s)\n",
    "onehot = np.eye(len(x))[draws]\n",
    "print(f'max |H - covariance of one-hot samples| = '\n",
    "      f'{np.abs(H - np.cov(onehot.T)).max():.4f}')\n",
    "print(f'max |H @ 1| = {np.abs(H.sum(axis=1)).max():.1e}  (flat shift direction)')"
   ],
   "execution_count": 6,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "eigenvalues of H: [-0.        0.008103  0.052497  0.063313  0.099101  0.284324]\nmax |H - covariance of one-hot samples| = 0.0006\nmax |H @ 1| = 1.8e-16  (flat shift direction)\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-convexity-md-7 fw=all -->\n",
    "\n",
    "Every eigenvalue is nonnegative, from $0.284324$ down to one numerical zero,\n",
    "the predicted flat direction, confirmed by\n",
    "$\\|H\\mathbf{1}\\|_\\infty \\approx 1.8 \\times 10^{-16}$. And the empirical\n",
    "covariance of $200{,}000$ one-hot draws matches the analytic Hessian to within\n",
    "$0.0006$: the Hessian of log-sum-exp really is a covariance matrix you can\n",
    "sample from.\n",
    "\n",
    "### The Convex Conjugate\n",
    "\n",
    "One more construction completes the toolkit, and it is the bridge between this\n",
    "section and both duality (that section)\n",
    "and the variational representations of information theory. From here on we\n",
    "allow $f$ to take the value $+\\infty$; convexity for such an extended-real\n",
    "function is read on its epigraph (the chord inequality is required wherever\n",
    "the values are finite), and the conjugates below produce $+\\infty$ naturally.\n",
    "The **convex\n",
    "conjugate** (or Fenchel--Legendre transform) of $f : \\mathbb{R}^n \\to \\mathbb{R} \\cup \\{+\\infty\\}$\n",
    "is\n",
    "\n",
    "$$\n",
    "f^*(\\mathbf{y}) \\;=\\; \\sup_{\\mathbf{x}} \\;\\left( \\mathbf{y}^\\top \\mathbf{x} - f(\\mathbf{x}) \\right).\n",
    "$$\n",
    "\n",
    "Geometrically, $f^*(\\mathbf{y})$ asks: among all affine functions with slope\n",
    "$\\mathbf{y}$, how high can one be pushed while staying below the graph of $f$?\n",
    "(It records the negative of that intercept.) The conjugate thus encodes $f$ by\n",
    "its supporting lines instead of its values, and for **closed** convex $f$\n",
    "(closed meaning the epigraph is a closed set, equivalently $f$ is lower\n",
    "semicontinuous) the\n",
    "encoding is lossless: $f^{**} = f$ (@Boyd.Vandenberghe.2004, section\n",
    "3.3). For non-convex $f$ the double transform returns the largest\n",
    "closed convex function below it, the **convex envelope**, which is what\n",
    "convex *relaxations* optimize in place of $f$.\n",
    "\n",
    "Two properties are immediate. First, $f^*$ is *always* convex, whatever\n",
    "$f$ is: for fixed $\\mathbf{x}$ the expression\n",
    "$\\mathbf{y}^\\top\\mathbf{x} - f(\\mathbf{x})$ is affine in $\\mathbf{y}$, and rule\n",
    "3 says a supremum of affine functions is convex. The same one-line argument,\n",
    "in the next section, makes the dual function of\n",
    "that section concave, and no coincidence: for\n",
    "linearly constrained problems the dual function *is* a conjugate in disguise.\n",
    "Second, the definition rearranges into the **Fenchel--Young inequality**,\n",
    "\n",
    "$$\n",
    "\\mathbf{y}^\\top \\mathbf{x} \\;\\le\\; f(\\mathbf{x}) + f^*(\\mathbf{y})\n",
    "\\qquad \\textrm{for all } \\mathbf{x}, \\mathbf{y},\n",
    "$$\n",
    "\n",
    "with equality exactly when $\\mathbf{x}$ attains the supremum; for\n",
    "differentiable $f$, when $\\mathbf{y} = \\nabla f(\\mathbf{x})$.\n",
    "\n",
    "The simplest example sets the pattern: for $f(\\mathbf{x}) = \\tfrac12\\|\\mathbf{x}\\|^2$,\n",
    "the supremum of $\\mathbf{y}^\\top\\mathbf{x} - \\tfrac12\\|\\mathbf{x}\\|^2$ sits at\n",
    "$\\mathbf{x} = \\mathbf{y}$, giving $f^*(\\mathbf{y}) = \\tfrac12\\|\\mathbf{y}\\|^2$:\n",
    "the squared norm is its own conjugate, and Fenchel--Young becomes the familiar\n",
    "$\\mathbf{y}^\\top\\mathbf{x} \\le \\tfrac12\\|\\mathbf{x}\\|^2 + \\tfrac12\\|\\mathbf{y}\\|^2$.\n",
    "\n",
    "The pair that matters for deep learning is **log-sum-exp $\\leftrightarrow$\n",
    "negative entropy**. Compute\n",
    "$\\mathrm{lse}^*(\\mathbf{p}) = \\sup_{\\mathbf{x}} \\mathbf{p}^\\top\\mathbf{x} - \\mathrm{lse}(\\mathbf{x})$.\n",
    "If $\\mathbf{p}$ has a negative coordinate, send that $x_i \\to -\\infty$ and the\n",
    "objective blows up; if $\\mathbf{1}^\\top\\mathbf{p} \\neq 1$, march $\\mathbf{x} = c\\mathbf{1}$\n",
    "off to $\\pm\\infty$ and shift invariance does the same. So the supremum is finite\n",
    "only for $\\mathbf{p}$ in the simplex, where stationarity demands\n",
    "$\\mathrm{softmax}(\\mathbf{x}) = \\mathbf{p}$, solved by\n",
    "$\\mathbf{x} = \\log \\mathbf{p}$, and the value is\n",
    "$\\sum_i p_i \\log p_i$. The stationarity argument covers $\\mathbf{p}$ in the\n",
    "relative interior of the simplex (softmax outputs are strictly positive); for\n",
    "boundary $\\mathbf{p}$, with some $p_i = 0$, no maximizer exists, but sending\n",
    "those $x_i \\to -\\infty$ approaches the same value, so the formula holds on the\n",
    "whole simplex with the convention $0 \\log 0 = 0$. Therefore\n",
    "\n",
    "$$\n",
    "\\mathrm{lse}^*(\\mathbf{p}) =\n",
    "\\begin{cases}\n",
    "\\sum_i p_i \\log p_i = -H(\\mathbf{p}), & \\mathbf{p} \\in \\Delta, \\\\\n",
    "+\\infty, & \\textrm{otherwise,}\n",
    "\\end{cases}\n",
    "\\qquad \\textrm{and dually} \\qquad\n",
    "\\mathrm{lse}(\\mathbf{x}) = \\max_{\\mathbf{p} \\in \\Delta} \\left( \\mathbf{p}^\\top \\mathbf{x} + H(\\mathbf{p}) \\right).\n",
    "$$\n",
    "\n",
    "Read the dual formula as: log-sum-exp is the best *entropy-bonused*\n",
    "score over all distributions, and the maximizing $\\mathbf{p}$ is the softmax.\n",
    "Two consequences are already on this page. Softmax is the gradient of\n",
    "$\\mathrm{lse}$, proved in the Hessian proposition above; and softmax is the\n",
    "*maximum-entropy* answer, since dropping the bonus leaves\n",
    "$\\max_{\\mathbf{p} \\in \\Delta} \\mathbf{p}^\\top\\mathbf{x}$, whose maximizer is a\n",
    "hard, one-hot $\\arg\\max$, and the entropy term is what softens it. The identity\n",
    "is also the prototype\n",
    "for the variational representations of divergences: Donsker--Varadhan and the\n",
    "$f$-GAN duals in that section are this same\n",
    "conjugate trick applied to KL and its relatives.\n",
    "\n",
    "### Proximal Operators\n",
    "\n",
    "The conjugate encodes a convex function by its supporting lines; one last\n",
    "construction turns convex functions into *algorithm components*, unifying\n",
    "gradient steps with the projections that\n",
    "that section will build on. The **proximal operator** of\n",
    "a convex $f$ is\n",
    "\n",
    "$$\n",
    "\\mathrm{prox}_{f}(\\mathbf{z}) \\;=\\; \\mathop{\\mathrm{argmin}}_{\\mathbf{x}}\\; \\left( f(\\mathbf{x}) + \\tfrac12\\, \\|\\mathbf{x} - \\mathbf{z}\\|^2 \\right),\n",
    "$$\n",
    "\n",
    "well defined for the closed convex $f$ we use: the objective is $1$-strongly\n",
    "convex, so the uniqueness proposition above rules out a second minimizer, and\n",
    "closedness supplies the existence that an indicator (which is not continuous)\n",
    "would otherwise put in doubt. The prox moves toward lower $f$ but pays\n",
    "quadratically for straying from\n",
    "$\\mathbf{z}$. Two special cases calibrate the definition. If $f = 0$, the prox\n",
    "is the identity. If $f$ is the *indicator* of a closed convex set $C$ (zero on\n",
    "$C$, $+\\infty$ outside), then minimizing forces $\\mathbf{x} \\in C$ and the\n",
    "prox is the nearest feasible point:\n",
    "$\\mathrm{prox}_f = \\Pi_C$, the projection operator on which\n",
    "that section will build projected gradient descent.\n",
    "Proximal operators are projections,\n",
    "generalized from sets to functions.\n",
    "\n",
    "The example that matters for sparsity is $f(x) = \\lambda |x|$ (the operator\n",
    "acts coordinate-wise on $\\lambda\\|\\cdot\\|_1$, so one dimension suffices). The\n",
    "objective $\\lambda|x| + \\tfrac12 (x - z)^2$ has a kink at $0$, and the\n",
    "subgradient optimality criterion $0 \\in \\partial(\\cdot)$\n",
    "(the equation of that section, restated\n",
    "for vectors in that section) dispatches it in three lines: if the\n",
    "minimizer $x \\neq 0$, stationarity reads $\\lambda\\,\\mathrm{sign}(x) + x - z = 0$,\n",
    "i.e. $x = z - \\lambda\\,\\mathrm{sign}(z)$, consistent only when $|z| > \\lambda$;\n",
    "if $x = 0$, the criterion asks $z \\in [-\\lambda, \\lambda]$; and the two cases\n",
    "splice into one formula,\n",
    "\n",
    "$$\n",
    "\\mathrm{prox}_{\\lambda|\\cdot|}(z) \\;=\\; \\mathrm{sign}(z)\\, \\max\\left(|z| - \\lambda,\\, 0\\right).\n",
    "$$\n",
    "\n",
    "This is **soft-thresholding**, the same solution Exercise 3 derives from the\n",
    "subdifferential, now recognized as a prox. Inputs smaller than $\\lambda$ are\n",
    "snapped to *exactly* zero; larger ones are shrunk by $\\lambda$. This is the\n",
    "mechanism by which $\\ell_1$ regularization produces genuinely sparse weights\n",
    "where $\\ell_2$ only shrinks them.\n",
    "\n",
    "The resulting algorithm is one line long. For a composite objective\n",
    "$g(\\mathbf{x}) + h(\\mathbf{x})$ with $g$ smooth and $h$ convex but kinked\n",
    "(the lasso [@Tibshirani.1996], with $g$ the least-squares term and\n",
    "$h = \\lambda\\|\\cdot\\|_1$, is\n",
    "the prototype), alternate a gradient step on the smooth part with a prox on\n",
    "the kinked part:\n",
    "\n",
    "$$\n",
    "\\mathbf{x}_{k+1} = \\mathrm{prox}_{\\eta h}\\left(\\mathbf{x}_k - \\eta\\, \\nabla g(\\mathbf{x}_k)\\right).\n",
    "$$\n",
    "\n",
    "This is **ISTA**, the proximal-gradient method. It converges at the same\n",
    "$O(1/k)$ rate as plain gradient descent, kink notwithstanding (a theorem we\n",
    "quote rather than prove; see @Beck.Teboulle.2009), and it contains\n",
    "the projected gradient descent of\n",
    "that section as the special case where\n",
    "$h$ is an indicator. The cell verifies the equation\n",
    "against brute-force minimization, then runs twenty ISTA steps on a tiny lasso\n",
    "and watches exact zeros appear:"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "convexity-prox-ista"
   },
   "source": [
    "lam = 0.7\n",
    "prox = lambda z, t: np.sign(z) * np.maximum(np.abs(z) - t, 0.0)\n",
    "zs = np.linspace(-3.0, 3.0, 13)\n",
    "grid = np.linspace(-5.0, 5.0, 200001)          # brute-force argmin on a grid\n",
    "brute = np.array([grid[np.argmin(lam * np.abs(grid) + 0.5 * (grid - z)**2)]\n",
    "                  for z in zs])\n",
    "print('max |prox - brute-force argmin| =',\n",
    "      f'{np.abs(prox(zs, lam) - brute).max():.1e}')\n",
    "rng = np.random.default_rng(5)                 # a tiny lasso problem\n",
    "A = rng.normal(size=(30, 8))\n",
    "b = A @ np.array([2.0, 0, 0, -1.5, 0, 0, 0, 1.0]) + 0.05 * rng.normal(size=30)\n",
    "eta = 1.0 / np.linalg.eigvalsh(A.T @ A).max()\n",
    "w = np.zeros(8)\n",
    "for _ in range(20):                            # ISTA: gradient step, then prox\n",
    "    w = prox(w - eta * A.T @ (A @ w - b), eta * lam)\n",
    "print('w after 20 ISTA steps:', w.round(3))\n",
    "print('exact zeros:', int((w == 0).sum()), 'of 8 coordinates')"
   ],
   "execution_count": 7,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "max |prox - brute-force argmin| = 8.9e-16\nw after 20 ISTA steps: [ 1.964  0.     0.    -1.462  0.     0.     0.     0.963]\nexact zeros: 5 of 8 coordinates\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-convexity-md-8 fw=all -->\n",
    "\n",
    "The closed form matches the brute-force minimizer to grid resolution, and\n",
    "after twenty proximal-gradient steps five of the eight coordinates are\n",
    "*exactly* zero, snapped there by the $\\max$ in\n",
    "the equation, while the three nonzero coordinates sit\n",
    "near the planted values $(2.0, -1.5, 1.0)$. No amount of plain gradient\n",
    "descent can produce an exact zero (a smooth step lands wherever the arithmetic\n",
    "falls); the prox is the piece of the algorithm that *knows about the kink*,\n",
    "and one application per step suffices for sparsity.\n",
    "\n",
    "### Coordinate and Block Coordinate Descent\n",
    "\n",
    "A full gradient updates every coordinate at once. When parameters or examples\n",
    "are sparse, touching one coordinate or one block can be much cheaper. Suppose\n",
    "$f$ has coordinate-wise smoothness constants $L_j$:\n",
    "\n",
    "$$\n",
    "f(\\mathbf x+t\\mathbf e_j)\n",
    "\\le f(\\mathbf x)+t\\,\\partial_jf(\\mathbf x)+\\tfrac12L_jt^2.\n",
    "$$\n",
    "\n",
    "Minimizing this one-dimensional upper bound gives the **coordinate-descent**\n",
    "step\n",
    "\n",
    "$$\n",
    "x_j\\leftarrow x_j-\\frac{1}{L_j}\\partial_jf(\\mathbf x),\n",
    "$$\n",
    "\n",
    "with all other coordinates fixed. The method can cycle through coordinates,\n",
    "choose the largest partial derivative, or sample $j$. Randomized selection\n",
    "avoids adversarial orderings and has a clean representative guarantee: for a\n",
    "$\\mu$-strongly convex objective, sampling coordinate $j$ proportional to\n",
    "$L_j$ and taking the equation contracts expected\n",
    "suboptimality at a rate governed by\n",
    "$1-\\mu/\\sum_jL_j$. The comparison with full-gradient descent is not “one\n",
    "iteration versus one iteration”: a coordinate step reads and changes much\n",
    "less state, so work, memory traffic, and sparsity determine the useful unit.\n",
    "\n",
    "For a positive-definite quadratic\n",
    "\n",
    "$$\n",
    "f(\\mathbf x)=\\tfrac12\\mathbf x^\\top A\\mathbf x-\\mathbf b^\\top\\mathbf x,\n",
    "$$\n",
    "\n",
    "we can minimize the chosen coordinate *exactly*:\n",
    "\n",
    "$$\n",
    "x_j\\leftarrow x_j-\\frac{(A\\mathbf x-\\mathbf b)_j}{A_{jj}}.\n",
    "$$\n",
    "\n",
    "Maintaining the residual $\\mathbf r=A\\mathbf x-\\mathbf b$ makes a coordinate\n",
    "update cheap: after changing $x_j$ by $\\delta$, update\n",
    "$\\mathbf r\\leftarrow\\mathbf r+\\delta A_{:j}$. On a sparse matrix this touches\n",
    "only the nonzeros in column $j$. A full cyclic sweep is the Gauss--Seidel\n",
    "iteration for $A\\mathbf x=\\mathbf b$."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "mdl-convexity-coordinate-descent"
   },
   "source": [
    "d_cd = 40\n",
    "A_cd = (2 * np.eye(d_cd) - 0.95 * np.eye(d_cd, k=1)\n",
    "        - 0.95 * np.eye(d_cd, k=-1))             # SPD, strongly coupled\n",
    "b_cd = np.ones(d_cd)\n",
    "x_star_cd = np.linalg.solve(A_cd, b_cd)\n",
    "f_cd = lambda x: 0.5 * x @ A_cd @ x - b_cd @ x\n",
    "f_star_cd = f_cd(x_star_cd)\n",
    "L_cd = np.linalg.eigvalsh(A_cd)[-1]\n",
    "x_gd, x_cd = np.zeros(d_cd), np.zeros(d_cd)\n",
    "r_cd = A_cd @ x_cd - b_cd\n",
    "gap_gd, gap_cd = [], []\n",
    "for sweep in range(1, 101):\n",
    "    x_gd -= (A_cd @ x_gd - b_cd) / L_cd           # one full gradient\n",
    "    for j in range(d_cd):                         # one coordinate sweep\n",
    "        delta = -r_cd[j] / A_cd[j, j]\n",
    "        x_cd[j] += delta\n",
    "        r_cd += delta * A_cd[:, j]\n",
    "    gap_gd.append(f_cd(x_gd) - f_star_cd)\n",
    "    gap_cd.append(f_cd(x_cd) - f_star_cd)\n",
    "d2l.plot(np.arange(1, 101), [gap_gd, gap_cd], 'sweep', 'optimality gap',\n",
    "         legend=[r'gradient descent, step $1/L$', 'exact coordinate sweep'],\n",
    "         yscale='log')"
   ],
   "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=\"254.544602pt\" height=\"183.35625pt\" viewBox=\"0 0 254.544602 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:42:10.965626</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 254.544602 183.35625 \nL 254.544602 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 51.378125 145.8 \nL 246.678125 145.8 \nL 246.678125 7.2 \nL 51.378125 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 58.462009 145.8 \nL 58.462009 7.2 \n\" clip-path=\"url(#p6f25aceaf8)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_2\">\n      <defs>\n       <path id=\"mc35090d5ad\" d=\"M 0 0 \nL 0 3.5 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#mc35090d5ad\" x=\"58.462009\" 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(55.280759 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 94.329778 145.8 \nL 94.329778 7.2 \n\" clip-path=\"url(#p6f25aceaf8)\" 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=\"#mc35090d5ad\" x=\"94.329778\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_2\">\n      <!-- 20 -->\n      <g transform=\"translate(87.967278 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       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_3\">\n     <g id=\"line2d_5\">\n      <path d=\"M 130.197546 145.8 \nL 130.197546 7.2 \n\" clip-path=\"url(#p6f25aceaf8)\" 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=\"#mc35090d5ad\" x=\"130.197546\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_3\">\n      <!-- 40 -->\n      <g transform=\"translate(123.835046 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       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_4\">\n     <g id=\"line2d_7\">\n      <path d=\"M 166.065315 145.8 \nL 166.065315 7.2 \n\" clip-path=\"url(#p6f25aceaf8)\" 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=\"#mc35090d5ad\" x=\"166.065315\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_4\">\n      <!-- 60 -->\n      <g transform=\"translate(159.702815 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       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_5\">\n     <g id=\"line2d_9\">\n      <path d=\"M 201.933084 145.8 \nL 201.933084 7.2 \n\" clip-path=\"url(#p6f25aceaf8)\" 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=\"#mc35090d5ad\" x=\"201.933084\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_5\">\n      <!-- 80 -->\n      <g transform=\"translate(195.570584 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       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_6\">\n     <g id=\"line2d_11\">\n      <path d=\"M 237.800852 145.8 \nL 237.800852 7.2 \n\" clip-path=\"url(#p6f25aceaf8)\" 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=\"#mc35090d5ad\" x=\"237.800852\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_6\">\n      <!-- 100 -->\n      <g transform=\"translate(228.257102 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       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_7\">\n     <!-- sweep -->\n     <g transform=\"translate(133.007031 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-77\" d=\"M 269 3500 \nL 844 3500 \nL 1563 769 \nL 2278 3500 \nL 2956 3500 \nL 3675 769 \nL 4391 3500 \nL 4966 3500 \nL 4050 0 \nL 3372 0 \nL 2619 2869 \nL 1863 0 \nL 1184 0 \nL 269 3500 \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      </defs>\n      <use xlink:href=\"#DejaVuSans-73\"/>\n      <use xlink:href=\"#DejaVuSans-77\" transform=\"translate(52.099609 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(133.886719 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(195.410156 0)\"/>\n      <use xlink:href=\"#DejaVuSans-70\" transform=\"translate(256.933594 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 51.378125 125.52577 \nL 246.678125 125.52577 \n\" clip-path=\"url(#p6f25aceaf8)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_14\">\n      <defs>\n       <path id=\"m5d6a2971b3\" d=\"M 0 0 \nL -3.5 0 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m5d6a2971b3\" x=\"51.378125\" y=\"125.52577\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_8\">\n      <!-- $\\mathdefault{10^{-6}}$ -->\n      <g transform=\"translate(20.878125 129.324989) 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-31\" transform=\"translate(0 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-2212\" transform=\"translate(128.203125 39.046875) scale(0.7)\"/>\n       <use xlink:href=\"#DejaVuSans-36\" transform=\"translate(186.855469 39.046875) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_2\">\n     <g id=\"line2d_15\">\n      <path d=\"M 51.378125 98.24913 \nL 246.678125 98.24913 \n\" clip-path=\"url(#p6f25aceaf8)\" 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=\"#m5d6a2971b3\" x=\"51.378125\" y=\"98.24913\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_9\">\n      <!-- $\\mathdefault{10^{-4}}$ -->\n      <g transform=\"translate(20.878125 102.048349) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(0 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-2212\" transform=\"translate(128.203125 38.965625) scale(0.7)\"/>\n       <use xlink:href=\"#DejaVuSans-34\" transform=\"translate(186.855469 38.965625) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_3\">\n     <g id=\"line2d_17\">\n      <path d=\"M 51.378125 70.972491 \nL 246.678125 70.972491 \n\" clip-path=\"url(#p6f25aceaf8)\" 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=\"#m5d6a2971b3\" x=\"51.378125\" y=\"70.972491\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_10\">\n      <!-- $\\mathdefault{10^{-2}}$ -->\n      <g transform=\"translate(20.878125 74.771709) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(0 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-2212\" transform=\"translate(128.203125 39.046875) scale(0.7)\"/>\n       <use xlink:href=\"#DejaVuSans-32\" transform=\"translate(186.855469 39.046875) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_4\">\n     <g id=\"line2d_19\">\n      <path d=\"M 51.378125 43.695851 \nL 246.678125 43.695851 \n\" clip-path=\"url(#p6f25aceaf8)\" 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=\"#m5d6a2971b3\" x=\"51.378125\" y=\"43.695851\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_11\">\n      <!-- $\\mathdefault{10^{0}}$ -->\n      <g transform=\"translate(26.778125 47.49507) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(0 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(128.203125 39.046875) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_5\">\n     <g id=\"line2d_21\">\n      <path d=\"M 51.378125 16.419211 \nL 246.678125 16.419211 \n\" clip-path=\"url(#p6f25aceaf8)\" 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=\"#m5d6a2971b3\" x=\"51.378125\" y=\"16.419211\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_12\">\n      <!-- $\\mathdefault{10^{2}}$ -->\n      <g transform=\"translate(26.778125 20.21843) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(0 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-32\" transform=\"translate(128.203125 39.046875) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_13\">\n     <!-- optimality gap -->\n     <g transform=\"translate(14.798438 112.716406) rotate(-90) scale(0.1 -0.1)\">\n      <defs>\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-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-6d\" d=\"M 3328 2828 \nQ 3544 3216 3844 3400 \nQ 4144 3584 4550 3584 \nQ 5097 3584 5394 3201 \nQ 5691 2819 5691 2113 \nL 5691 0 \nL 5113 0 \nL 5113 2094 \nQ 5113 2597 4934 2840 \nQ 4756 3084 4391 3084 \nQ 3944 3084 3684 2787 \nQ 3425 2491 3425 1978 \nL 3425 0 \nL 2847 0 \nL 2847 2094 \nQ 2847 2600 2669 2842 \nQ 2491 3084 2119 3084 \nQ 1678 3084 1418 2786 \nQ 1159 2488 1159 1978 \nL 1159 0 \nL 581 0 \nL 581 3500 \nL 1159 3500 \nL 1159 2956 \nQ 1356 3278 1631 3431 \nQ 1906 3584 2284 3584 \nQ 2666 3584 2933 3390 \nQ 3200 3197 3328 2828 \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       <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-20\" 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      </defs>\n      <use xlink:href=\"#DejaVuSans-6f\"/>\n      <use xlink:href=\"#DejaVuSans-70\" transform=\"translate(61.181641 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(124.658203 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(163.867188 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6d\" transform=\"translate(191.650391 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(289.0625 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6c\" transform=\"translate(350.341797 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(378.125 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(405.908203 0)\"/>\n      <use xlink:href=\"#DejaVuSans-79\" transform=\"translate(445.117188 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(504.296875 0)\"/>\n      <use xlink:href=\"#DejaVuSans-67\" transform=\"translate(536.083984 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(599.560547 0)\"/>\n      <use xlink:href=\"#DejaVuSans-70\" transform=\"translate(660.839844 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"line2d_23\">\n    <path d=\"M 60.255398 13.5 \nL 62.048786 13.849399 \nL 63.842175 14.196165 \nL 65.635563 14.54102 \nL 67.428951 14.88437 \nL 69.22234 15.226482 \nL 71.015728 15.567543 \nL 72.809117 15.907695 \nL 74.602505 16.247046 \nL 76.395894 16.585684 \nL 78.189282 16.92368 \nL 79.98267 17.261094 \nL 81.776059 17.597976 \nL 83.569447 17.93437 \nL 85.362836 18.270312 \nL 87.156224 18.605836 \nL 88.949613 18.94097 \nL 90.743001 19.27574 \nL 92.536389 19.610168 \nL 94.329778 19.944276 \nL 96.123166 20.278082 \nL 97.916555 20.611603 \nL 99.709943 20.944854 \nL 101.503332 21.277849 \nL 103.29672 21.610601 \nL 105.090108 21.943122 \nL 106.883497 22.275422 \nL 108.676885 22.607513 \nL 110.470274 22.939403 \nL 112.263662 23.271101 \nL 114.057051 23.602615 \nL 115.850439 23.933954 \nL 117.643827 24.265124 \nL 119.437216 24.596131 \nL 121.230604 24.926983 \nL 123.023993 25.257685 \nL 124.817381 25.588243 \nL 126.61077 25.918662 \nL 128.404158 26.248947 \nL 130.197546 26.579103 \nL 131.990935 26.909134 \nL 133.784323 27.239045 \nL 135.577712 27.56884 \nL 137.3711 27.898522 \nL 139.164489 28.228096 \nL 140.957877 28.557565 \nL 142.751265 28.886931 \nL 144.544654 29.216199 \nL 146.338042 29.545372 \nL 148.131431 29.874452 \nL 149.924819 30.203442 \nL 151.718208 30.532346 \nL 153.511596 30.861164 \nL 155.304985 31.189901 \nL 157.098373 31.518558 \nL 158.891761 31.847138 \nL 160.68515 32.175643 \nL 162.478538 32.504075 \nL 164.271927 32.832435 \nL 166.065315 33.160727 \nL 167.858704 33.488952 \nL 169.652092 33.817112 \nL 171.44548 34.145209 \nL 173.238869 34.473243 \nL 175.032257 34.801218 \nL 176.825646 35.129134 \nL 178.619034 35.456994 \nL 180.412423 35.784798 \nL 182.205811 36.112548 \nL 183.999199 36.440245 \nL 185.792588 36.767892 \nL 187.585976 37.095488 \nL 189.379365 37.423036 \nL 191.172753 37.750537 \nL 192.966142 38.077992 \nL 194.75953 38.405401 \nL 196.552918 38.732767 \nL 198.346307 39.06009 \nL 200.139695 39.387372 \nL 201.933084 39.714612 \nL 203.726472 40.041814 \nL 205.519861 40.368976 \nL 207.313249 40.696101 \nL 209.106637 41.02319 \nL 210.900026 41.350242 \nL 212.693414 41.67726 \nL 214.486803 42.004243 \nL 216.280191 42.331193 \nL 218.07358 42.658111 \nL 219.866968 42.984997 \nL 221.660356 43.311852 \nL 223.453745 43.638677 \nL 225.247133 43.965473 \nL 227.040522 44.292239 \nL 228.83391 44.618978 \nL 230.627299 44.94569 \nL 232.420687 45.272374 \nL 234.214075 45.599033 \nL 236.007464 45.925666 \nL 237.800852 46.252274 \n\" clip-path=\"url(#p6f25aceaf8)\" style=\"fill: none; stroke: #1f77b4; stroke-width: 1.5; stroke-linecap: square\"/>\n   </g>\n   <g id=\"line2d_24\">\n    <path d=\"M 60.255398 14.474231 \nL 62.048786 15.782705 \nL 63.842175 17.080117 \nL 65.635563 18.370098 \nL 67.428951 19.654605 \nL 69.22234 20.934853 \nL 71.015728 22.211671 \nL 72.809117 23.485658 \nL 74.602505 24.757265 \nL 76.395894 26.026844 \nL 78.189282 27.294677 \nL 79.98267 28.560993 \nL 81.776059 29.825983 \nL 83.569447 31.089808 \nL 85.362836 32.352606 \nL 87.156224 33.614493 \nL 88.949613 34.875573 \nL 90.743001 36.135937 \nL 92.536389 37.395664 \nL 94.329778 38.654826 \nL 96.123166 39.913486 \nL 97.916555 41.171702 \nL 99.709943 42.429525 \nL 101.503332 43.687003 \nL 103.29672 44.944178 \nL 105.090108 46.20109 \nL 106.883497 47.457774 \nL 108.676885 48.714265 \nL 110.470274 49.970591 \nL 112.263662 51.226782 \nL 114.057051 52.482864 \nL 115.850439 53.738861 \nL 117.643827 54.994795 \nL 119.437216 56.250688 \nL 121.230604 57.506559 \nL 123.023993 58.762426 \nL 124.817381 60.018307 \nL 126.61077 61.274218 \nL 128.404158 62.530173 \nL 130.197546 63.786187 \nL 131.990935 65.042273 \nL 133.784323 66.298443 \nL 135.577712 67.55471 \nL 137.3711 68.811084 \nL 139.164489 70.067575 \nL 140.957877 71.324194 \nL 142.751265 72.580949 \nL 144.544654 73.83785 \nL 146.338042 75.094903 \nL 148.131431 76.352118 \nL 149.924819 77.609502 \nL 151.718208 78.86706 \nL 153.511596 80.124801 \nL 155.304985 81.382729 \nL 157.098373 82.640851 \nL 158.891761 83.899171 \nL 160.68515 85.157696 \nL 162.478538 86.416429 \nL 164.271927 87.675376 \nL 166.065315 88.93454 \nL 167.858704 90.193925 \nL 169.652092 91.453535 \nL 171.44548 92.713374 \nL 173.238869 93.973443 \nL 175.032257 95.233747 \nL 176.825646 96.494287 \nL 178.619034 97.755066 \nL 180.412423 99.016087 \nL 182.205811 100.277351 \nL 183.999199 101.53886 \nL 185.792588 102.800615 \nL 187.585976 104.062618 \nL 189.379365 105.324871 \nL 191.172753 106.587373 \nL 192.966142 107.850126 \nL 194.75953 109.113131 \nL 196.552918 110.376388 \nL 198.346307 111.639897 \nL 200.139695 112.903659 \nL 201.933084 114.167674 \nL 203.726472 115.43194 \nL 205.519861 116.696459 \nL 207.313249 117.961231 \nL 209.106637 119.226253 \nL 210.900026 120.491526 \nL 212.693414 121.75705 \nL 214.486803 123.022822 \nL 216.280191 124.288842 \nL 218.07358 125.555111 \nL 219.866968 126.821626 \nL 221.660356 128.088386 \nL 223.453745 129.355388 \nL 225.247133 130.622634 \nL 227.040522 131.890119 \nL 228.83391 133.157845 \nL 230.627299 134.425806 \nL 232.420687 135.694005 \nL 234.214075 136.962434 \nL 236.007464 138.231103 \nL 237.800852 139.5 \n\" clip-path=\"url(#p6f25aceaf8)\" style=\"fill: none; stroke-dasharray: 5.55,2.4; stroke-dashoffset: 0; stroke: #bf00bf; stroke-width: 1.5\"/>\n   </g>\n   <g id=\"patch_3\">\n    <path d=\"M 51.378125 145.8 \nL 51.378125 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 246.678125 145.8 \nL 246.678125 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 51.378125 145.8 \nL 246.678125 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 51.378125 7.2 \nL 246.678125 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 58.378125 140.8 \nL 221.778125 140.8 \nQ 223.778125 140.8 223.778125 138.8 \nL 223.778125 110.421875 \nQ 223.778125 108.421875 221.778125 108.421875 \nL 58.378125 108.421875 \nQ 56.378125 108.421875 56.378125 110.421875 \nL 56.378125 138.8 \nQ 56.378125 140.8 58.378125 140.8 \nz\n\" style=\"fill: #ffffff; opacity: 0.8; stroke: #cccccc; stroke-linejoin: miter\"/>\n    </g>\n    <g id=\"line2d_25\">\n     <path d=\"M 60.378125 116.521875 \nL 70.378125 116.521875 \nL 80.378125 116.521875 \n\" style=\"fill: none; stroke: #1f77b4; stroke-width: 1.5; stroke-linecap: square\"/>\n    </g>\n    <g id=\"text_14\">\n     <!-- gradient descent, step $1/L$ -->\n     <g transform=\"translate(88.378125 120.021875) scale(0.1 -0.1)\">\n      <defs>\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-64\" d=\"M 2906 2969 \nL 2906 4863 \nL 3481 4863 \nL 3481 0 \nL 2906 0 \nL 2906 525 \nQ 2725 213 2448 61 \nQ 2172 -91 1784 -91 \nQ 1150 -91 751 415 \nQ 353 922 353 1747 \nQ 353 2572 751 3078 \nQ 1150 3584 1784 3584 \nQ 2172 3584 2448 3432 \nQ 2725 3281 2906 2969 \nz\nM 947 1747 \nQ 947 1113 1208 752 \nQ 1469 391 1925 391 \nQ 2381 391 2643 752 \nQ 2906 1113 2906 1747 \nQ 2906 2381 2643 2742 \nQ 2381 3103 1925 3103 \nQ 1469 3103 1208 2742 \nQ 947 2381 947 1747 \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-63\" d=\"M 3122 3366 \nL 3122 2828 \nQ 2878 2963 2633 3030 \nQ 2388 3097 2138 3097 \nQ 1578 3097 1268 2742 \nQ 959 2388 959 1747 \nQ 959 1106 1268 751 \nQ 1578 397 2138 397 \nQ 2388 397 2633 464 \nQ 2878 531 3122 666 \nL 3122 134 \nQ 2881 22 2623 -34 \nQ 2366 -91 2075 -91 \nQ 1284 -91 818 406 \nQ 353 903 353 1747 \nQ 353 2603 823 3093 \nQ 1294 3584 2113 3584 \nQ 2378 3584 2631 3529 \nQ 2884 3475 3122 3366 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-2c\" d=\"M 750 794 \nL 1409 794 \nL 1409 256 \nL 897 -744 \nL 494 -744 \nL 750 256 \nL 750 794 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-2f\" d=\"M 1625 4666 \nL 2156 4666 \nL 531 -594 \nL 0 -594 \nL 1625 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-Oblique-4c\" d=\"M 1075 4666 \nL 1709 4666 \nL 909 525 \nL 3181 525 \nL 3078 0 \nL 172 0 \nL 1075 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-67\" transform=\"translate(0 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(63.476562 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(104.589844 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-64\" transform=\"translate(165.869141 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(229.345703 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(257.128906 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(318.652344 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(382.03125 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(421.240234 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-64\" transform=\"translate(453.027344 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(516.503906 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(578.027344 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-63\" transform=\"translate(630.126953 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(685.107422 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(746.630859 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(810.009766 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-2c\" transform=\"translate(849.21875 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(881.005859 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(912.792969 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(964.892578 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(1004.101562 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-70\" transform=\"translate(1065.625 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(1129.101562 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(1160.888672 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-2f\" transform=\"translate(1224.511719 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-Oblique-4c\" transform=\"translate(1258.203125 0.015625)\"/>\n     </g>\n    </g>\n    <g id=\"line2d_26\">\n     <path d=\"M 60.378125 131.220313 \nL 70.378125 131.220313 \nL 80.378125 131.220313 \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     <!-- exact coordinate sweep -->\n     <g transform=\"translate(88.378125 134.720313) 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-65\"/>\n      <use xlink:href=\"#DejaVuSans-78\" transform=\"translate(59.773438 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(118.953125 0)\"/>\n      <use xlink:href=\"#DejaVuSans-63\" transform=\"translate(180.232422 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(235.212891 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(274.421875 0)\"/>\n      <use xlink:href=\"#DejaVuSans-63\" transform=\"translate(306.208984 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(361.189453 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(422.371094 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(483.552734 0)\"/>\n      <use xlink:href=\"#DejaVuSans-64\" transform=\"translate(522.916016 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(586.392578 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(614.175781 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(677.554688 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(738.833984 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(778.042969 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(839.566406 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(871.353516 0)\"/>\n      <use xlink:href=\"#DejaVuSans-77\" transform=\"translate(923.453125 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(1005.240234 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(1066.763672 0)\"/>\n      <use xlink:href=\"#DejaVuSans-70\" transform=\"translate(1128.287109 0)\"/>\n     </g>\n    </g>\n   </g>\n  </g>\n </g>\n <defs>\n  <clipPath id=\"p6f25aceaf8\">\n   <rect x=\"51.378125\" 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-convexity-md-9 fw=all -->\n",
    "\n",
    "This coupled quadratic is deliberately unfavorable to independent coordinates:\n",
    "changing one affects its neighbors. Even so, exact coordinate minimization\n",
    "uses the fresh residual after each update and advances much faster per sweep\n",
    "than the conservative global step $1/L$. Different matrices can reverse that\n",
    "comparison; the point is the mechanism, not a universal ranking.\n",
    "\n",
    "The same idea extends in two directions. **Block coordinate descent** updates a\n",
    "layer, feature group, or matrix block by solving a small subproblem, exploiting\n",
    "structure that scalar coordinates miss. For a composite objective\n",
    "$f(\\mathbf x)+\\lambda\\|\\mathbf x\\|_1$, the coordinate subproblem includes the\n",
    "nonsmooth term and its exact update is soft-thresholding, the proximal operator\n",
    "of the equation. This is why coordinate methods are\n",
    "natural for sparse regression and matrix factorization: each cheap local solve\n",
    "can create exact zeros, whereas an ordinary smooth gradient step cannot.\n",
    "\n",
    "Coordinate descent is not the default for dense end-to-end neural training:\n",
    "accelerators are built for large matrix operations, not sequential scalar\n",
    "updates. It remains important for sparse linear models, embedding tables,\n",
    "alternating minimization, and inner problems where a block has a closed-form or\n",
    "very cheap solve.\n",
    "\n",
    "### Reality Check: Deep Networks Are Non-Convex\n",
    "\n",
    "The convexity calculus had one missing rule,\n",
    "composition with non-monotone nonlinear maps, and a neural network is nothing\n",
    "but a tower of such compositions. The loss surface of a deep network in its\n",
    "*parameters* is not convex, and a two-parameter \"network\" already shows why.\n",
    "Take $f(a, b) = (ab - 1)^2$: a linear model with two stacked scalar weights and\n",
    "a squared loss. Its global minima form the hyperbola $\\{ab = 1\\}$, a\n",
    "*non-convex set*. But our local-equals-global proposition proved the minimizer\n",
    "set of any convex function is convex; therefore $f$ cannot be convex, and\n",
    "indeed the average of the minimizers $(1, 1)$ and $(-1, -1)$ is the origin,\n",
    "where $f = 1$ sits strictly above the minimum $0$. Real networks inherit this\n",
    "structurally: permuting the hidden units of a layer (with their weights) leaves\n",
    "the computed function unchanged, so every minimum comes with combinatorially\n",
    "many symmetric copies scattered across parameter space. Generically the copies\n",
    "are distinct and averaging two of them raises the loss, exactly as the midpoint\n",
    "of $(1, 1)$ and $(-1, -1)$ did for $(ab - 1)^2$, and a minimizer set that\n",
    "contains distinct copies but not their averages cannot be convex. Deep\n",
    "architectures rule out convexity structurally.\n",
    "\n",
    "What survives? More than the worst case suggests, and the\n",
    "linear-rate proof already told us where to look. Its second half consumed only\n",
    "the inequality the equation, known as the\n",
    "**Polyak--Łojasiewicz (PL) condition** (after Polyak and Łojasiewicz, who\n",
    "introduced it independently in 1963 [@Polyak.1963; @Lojasiewicz.1963]):\n",
    "\n",
    "$$\n",
    "f \\textrm{ is } L\\textrm{-smooth} \\;\\;\\textrm{and}\\;\\;\n",
    "\\frac12\\, \\|\\nabla f(\\mathbf{x})\\|^2 \\;\\ge\\; \\mu \\left( f(\\mathbf{x}) - f^\\star \\right)\n",
    "\\;\\;\\textrm{for all } \\mathbf{x}\n",
    "\\qquad \\Longrightarrow \\qquad\n",
    "\\textrm{GD converges linearly to } f^\\star,\n",
    "$$\n",
    "\n",
    "with no convexity required [@Karimi.Nutini.Schmidt.2016] (smoothness\n",
    "stays in the hypothesis; it is what powers the descent lemma half of the\n",
    "argument). PL says the\n",
    "gradient cannot be small unless the *value* is nearly optimal: flat spots\n",
    "exist only at the bottom. Strong convexity implies PL (that was the first half\n",
    "of the proof), but the converse fails: PL functions can have multiple minima,\n",
    "plateaus of minimizers, and wild non-convexity, as long as every stationary\n",
    "point is global. The standard example is $f(x) = x^2 + 3\\sin^2 x$, whose second\n",
    "derivative dips to $-4$, so it is not convex, yet it satisfies PL globally.\n",
    "The cell verifies both claims on $[-5, 5]$ and then runs gradient descent,\n",
    "watching the suboptimality gap $f(x_k) - f^\\star$ shrink by a near-constant\n",
    "factor per step, the signature of a linear rate."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "convexity-pl-rate"
   },
   "source": [
    "f = lambda x: x**2 + 3 * np.sin(x)**2          # nonconvex; f* = 0 at x = 0\n",
    "df = lambda x: 2 * x + 3 * np.sin(2 * x)\n",
    "xs = np.linspace(-5, 5, 100001)\n",
    "xs = xs[np.abs(xs) > 1e-3]                     # avoid 0/0 at the minimizer\n",
    "print(f'PL constant on [-5, 5]: mu = {(0.5 * df(xs)**2 / f(xs)).min():.4f}')\n",
    "print(f\"min f'' = {(2 + 6 * np.cos(2 * xs)).min():.2f}  (f is not convex)\")\n",
    "x, gaps = 4.5, []\n",
    "for _ in range(80):                            # gradient descent, eta = 1/16\n",
    "    x -= df(x) / 16.0\n",
    "    gaps.append(f(x))\n",
    "ratios = np.array(gaps[1:]) / np.array(gaps[:-1])\n",
    "print('successive gap ratios:', ratios[::16].round(4))"
   ],
   "execution_count": 9,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "PL constant on [-5, 5]: mu = 0.1755\nmin f'' = -4.00  (f is not convex)\nsuccessive gap ratios: [0.6293 0.2907 0.25   0.25   0.25  ]\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-convexity-md-10 fw=all -->\n",
    "\n",
    "The numerically measured PL constant on $[-5, 5]$ is $\\mu \\approx 0.1755$: the\n",
    "function is non-convex (the minimum of $f''$ is $-4.00$) yet PL. The window\n",
    "suffices for the global claim, because the ratio\n",
    "$\\tfrac12 f'(x)^2 / f(x)$ only grows outside it, tending to $2$ as\n",
    "$|x| \\to \\infty$; Exercise 7 completes the argument. Under\n",
    "gradient descent the successive gap ratios start at $0.6293$ while the iterate\n",
    "crosses the slow middle stretch, then settle at exactly $0.25$: a constant\n",
    "contraction, i.e. linear convergence, on a non-convex function. (The asymptotic\n",
    "$0.25$ is no mystery: near the minimum $f$ looks like $\\tfrac12 f''(0) x^2$ with\n",
    "$f''(0) = 8$, each step scales $x$ by $1 - 8/16 = \\tfrac12$, and the gap is\n",
    "quadratic in $x$.) Conditions of PL type are one current explanation for why\n",
    "heavily over-parameterized networks train so reliably: near interpolation, wide\n",
    "networks have been argued to satisfy local PL-style inequalities\n",
    "[@Liu.Zhu.Belkin.2022], so first-order methods converge fast to global\n",
    "*training-loss* minima even though the loss surface is nothing like convex.\n",
    "\n",
    "Non-convexity has one more consequence the convex theory never had to face:\n",
    "*which* global minimum you reach is up for grabs, and the optimizer itself does\n",
    "the choosing. When many minimizers exist, gradient descent picks\n",
    "systematically: it has an **implicit bias**. The simplest case is\n",
    "underdetermined least squares: started from $\\mathbf{w}_0 = \\mathbf{0}$, every\n",
    "gradient $X^\\top(X\\mathbf{w} - \\mathbf{y})$ lies in the row space of $X$, so\n",
    "the iterates never leave it, and the limit is the *minimum-norm* interpolant,\n",
    "the same solution the pseudoinverse computes\n",
    "(that section; Exercise 8 has you verify it, and Exercise 9\n",
    "of that section has you derive it). For\n",
    "logistic regression on separable data, gradient descent's direction converges\n",
    "to the maximum-margin separator [@Soudry.Hoffer.Nacson.ea.2018], the\n",
    "SVM solution of that section, obtained\n",
    "without ever being asked for. Which minimum an optimizer prefers is part of\n",
    "what a\n",
    "trained model *is*, and it is one reason architecture-plus-optimizer, not\n",
    "architecture alone, determines generalization.\n",
    "\n",
    "This chapter's relationship to practice, then: convex theory\n",
    "is the *idealization* that the working optimizer approximates, not a literal\n",
    "description of deep training. The losses are convex in the last layer and in\n",
    "many sub-problems (projections, duals); the proofs (descent\n",
    "lemma, PL, rates) are the instruments we carry into non-convex territory; and\n",
    "where the instruments lose their guarantees, they usually keep their shape:\n",
    "the same step sizes, the same contraction heuristics, the same role for\n",
    "curvature and conditioning.\n",
    "\n",
    "## Summary\n",
    "\n",
    "* A set is **convex** when every chord stays inside; half-spaces, norm balls,\n",
    "  the simplex, and the PSD cone are the working catalog, and **intersection**\n",
    "  preserves convexity (unions do not), which certifies the simplex,\n",
    "  the PSD cone, and every polyhedral feasible set.\n",
    "* A function is convex by any of **three equivalent lenses**: chord above graph,\n",
    "  tangent below graph (the global under-estimator gradient methods exploit), or\n",
    "  PSD Hessian. **Strong convexity** ($\\nabla^2 f \\succeq \\mu I$) adds a\n",
    "  curvature floor; **subgradients** extend the tangent lens to kinked losses\n",
    "  like $\\ell_1$ and the hinge, with $\\partial |x|(0) = [-1, 1]$.\n",
    "* **Jensen's inequality** $f(\\mathbb{E}[X]) \\le \\mathbb{E}[f(X)]$ is the chord\n",
    "  inequality lifted to expectations; its two-line proof is a supporting line\n",
    "  plus linearity of expectation. It yields AM--GM, the ELBO gap, and\n",
    "  $D_{\\mathrm{KL}} \\ge 0$ with equality iff the distributions coincide, the\n",
    "  cornerstone that section builds on.\n",
    "* For convex $f$, **every local minimum is global** (and stationary\n",
    "  $\\Rightarrow$ optimal); strict convexity gives uniqueness. Gradient descent's\n",
    "  local progress becomes a global rate: $O(L\\|\\mathbf{x}_0 - \\mathbf{x}^\\star\\|^2 / k)$\n",
    "  for smooth convex $f$, and a linear rate $(1 - \\mu/L)^k$ under strong\n",
    "  convexity, both dimension-free.\n",
    "* A short **calculus** (nonnegative sums, affine pre-composition, pointwise\n",
    "  max, monotone composition) certifies hinge, $\\ell_1$, logistic, and softmax\n",
    "  cross-entropy without touching a Hessian; log-sum-exp is convex because its\n",
    "  Hessian **is the softmax covariance**, and its conjugate is negative entropy,\n",
    "  the identity behind softmax-as-maximum-entropy and the variational duals\n",
    "  of that section. **Proximal operators** generalize\n",
    "  projections from sets to functions; soft-thresholding is the prox of\n",
    "  $\\lambda|\\cdot|$, and one prox per step (ISTA) optimizes kinked composite\n",
    "  losses at gradient descent's rate. **Coordinate descent** minimizes one\n",
    "  coordinate or block at a time; on quadratics it is an exact one-dimensional\n",
    "  solve, and with $\\ell_1$ regularization that solve becomes soft-thresholding.\n",
    "* Deep networks are **non-convex by construction** (permutation symmetry makes\n",
    "  the minimizer set non-convex), but the **PL condition** preserves linear\n",
    "  convergence without convexity, and gradient descent's **implicit bias**\n",
    "  (min-norm, max-margin) decides which of the many minima you get.\n",
    "\n",
    "## Exercises\n",
    "\n",
    "1. Prove that every norm ball $\\{\\mathbf{x} : \\|\\mathbf{x}\\| \\le r\\}$ is convex\n",
    "   directly from the triangle inequality, and exhibit two convex sets whose\n",
    "   union is not convex. Then show the set of *strictly* positive definite\n",
    "   matrices is convex, and explain why the PSD cone is its closure.\n",
    "2. Certify each of the following by naming the lens or calculus rule that does\n",
    "   it in one line: (a) $x \\log x$ on $x > 0$; (b) the hinge loss\n",
    "   $\\sum_i \\max(0, 1 - y_i\\,\\mathbf{w}^\\top\\mathbf{x}_i)$ in $\\mathbf{w}$;\n",
    "   (c) $\\|A\\mathbf{x} - \\mathbf{b}\\|_1$; (d) the *pointwise minimum* of two\n",
    "   convex functions: convex or not? Prove or give a counterexample.\n",
    "3. Compute the full subdifferential $\\partial f(x)$ of $f(x) = |x|$ at every\n",
    "   $x \\in \\mathbb{R}$, and verify the optimality criterion\n",
    "   $0 \\in \\partial f(x^\\star)$ picks out $x^\\star = 0$. Then show that for\n",
    "   $f(\\mathbf{w}) = \\tfrac12\\|\\mathbf{w} - \\mathbf{z}\\|^2 + \\lambda\\|\\mathbf{w}\\|_1$\n",
    "   the criterion yields the soft-thresholding solution\n",
    "   $w_i^\\star = \\mathrm{sign}(z_i) \\max(|z_i| - \\lambda, 0)$.\n",
    "4. Prove Jensen's finite form\n",
    "   $f(\\sum_i \\theta_i \\mathbf{x}_i) \\le \\sum_i \\theta_i f(\\mathbf{x}_i)$ by\n",
    "   induction on the number of points, starting from the chord inequality.\n",
    "   Use it (with $-\\log$) to derive the full\n",
    "   harmonic--geometric--arithmetic mean chain\n",
    "   $\\textrm{HM} \\le \\textrm{GM} \\le \\textrm{AM}$ for positive numbers.\n",
    "5. A function is **quasiconvex** if all its sublevel sets are convex. Show\n",
    "   every convex function is quasiconvex, and that $x \\mapsto \\sqrt{|x|}$ is\n",
    "   quasiconvex but not convex, so convex sublevel sets alone do *not* imply\n",
    "   the chord inequality. Which step of the local-equals-global proof still\n",
    "   works for quasiconvex functions, and which fails?\n",
    "6. In the $O(1/k)$ proof, we observed that\n",
    "   $\\|\\mathbf{x}_t - \\mathbf{x}^\\star\\|$ is nonincreasing. Verify this\n",
    "   numerically for gradient descent on\n",
    "   $f(\\mathbf{w}) = \\tfrac12\\|X\\mathbf{w} - \\mathbf{y}\\|^2$ (reuse the data of\n",
    "   the `#convexity-three-lenses` cell). The `#convexity-rate-check` cell\n",
    "   measured the value-gap contraction at $\\eta = 1/L$ and found exactly\n",
    "   $(1 - \\mu/L)^2$; predict what the contraction becomes at the more\n",
    "   aggressive $\\eta = 2/(\\mu + L)$ of\n",
    "   that section, then verify by modifying\n",
    "   the cell.\n",
    "7. Show that the Polyak--Łojasiewicz condition the equation implies\n",
    "   every stationary point is a global minimizer, and that strong convexity\n",
    "   implies PL (reproduce the proof). Then show PL does *not* imply convexity by\n",
    "   verifying the PL inequality for $f(x) = x^2 + 3\\sin^2 x$ analytically on a\n",
    "   neighborhood of $0$, or numerically on $[-5, 5]$, as the\n",
    "   `#convexity-pl-rate` cell did.\n",
    "8. **Implicit bias, verified.** Exercise 9 of\n",
    "   that section derives, on paper, that\n",
    "   gradient descent on the underdetermined least-squares loss\n",
    "   $\\tfrac12\\|X\\mathbf{w} - \\mathbf{y}\\|^2$ started at\n",
    "   $\\mathbf{w}_0 = \\mathbf{0}$ stays in the row space of $X$ and converges to\n",
    "   the minimum-$\\ell_2$-norm interpolant $X^+\\mathbf{y}$. This exercise is the\n",
    "   laboratory half: with a random $4 \\times 10$ system, (a) compare the GD\n",
    "   limit against `np.linalg.pinv`; (b) track the component of the iterates\n",
    "   *orthogonal* to the row space and confirm it stays at exactly zero;\n",
    "   (c) restart GD from a nonzero $\\mathbf{w}_0$ with a component off the row\n",
    "   space. What changes in the limit, and why?\n",
    "\n",
    "9. **Coordinate descent as Gauss--Seidel.** Derive\n",
    "   the equation, then show that one cyclic sweep is\n",
    "   Gauss--Seidel applied to $A\\mathbf x=\\mathbf b$. Modify the NumPy cell to use\n",
    "   randomized coordinates, compare equal numbers of coordinate updates, and\n",
    "   construct a matrix for which cyclic ordering is substantially worse.\n",
    "\n",
    "## Discussions\n",
    "\n",
    "Within this part, this section is load-bearing in both directions.\n",
    "that section proved what smoothness alone\n",
    "buys (stationarity); here convexity upgraded those rates to global guarantees,\n",
    "and the PL condition showed how much of the upgrade survives without convexity.\n",
    "that section consumes nearly everything\n",
    "above: convex feasible sets for projections, KKT sufficiency and Slater's\n",
    "condition require convex objectives and constraints, the dual function's\n",
    "concavity is the sup-of-affine rule, and its linear-constraint duals are\n",
    "convex conjugates. Beyond the chapter, Jensen's inequality and the\n",
    "log-sum-exp/negative-entropy pair are the analytic engine of\n",
    "that section and the variational bounds of\n",
    "that section, and the main book's\n",
    "that section, that section, and that section\n",
    "all stand on results proved here.\n",
    "\n",
    "[Discussions](https://d2l.discourse.group/t/convexity)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "name": "d2l-pytorch",
   "display_name": "d2l (PyTorch)",
   "language": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
