{
 "cells": [
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "---\n",
    "execute:\n",
    "  enabled: false\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-concentration-generalization-md-1 fw=all -->\n",
    "\n",
    "# Concentration and Generalization\n",
    "\n",
    "Every guarantee this chapter has offered so far decays *polynomially*.\n",
    "Chebyshev's inequality the equation caps the miss probability of a\n",
    "sample mean at $\\sigma^2/(nt^2)$, a rate of $1/n$, and the tests and\n",
    "confidence intervals of that section traded that finite-sample\n",
    "bound away for Gaussian *approximations* that are only exact in the limit. The\n",
    "truth is far better: when the data are bounded, the probability that an\n",
    "average strays from its mean decays *exponentially* in $n$, and this section\n",
    "proves it. The main book bounded the error of a test-set\n",
    "estimate with Hoeffding's inequality (that section),\n",
    "quoting it on faith; here we prove it. The same machinery\n",
    "then explains the strange geometry of high dimension teased in\n",
    "that section (thin shells, near-orthogonal random\n",
    "directions) and carries us to\n",
    "the question all of it serves: *generalization*. A learner that picks its\n",
    "function after seeing the data voids the single-function guarantee, and the\n",
    "repair (uniform convergence, first over finite classes and then through\n",
    "Rademacher complexity) is the promised mechanics behind the classical\n",
    "generalization bounds of that section. The section closes\n",
    "where the classical story visibly breaks and something more interesting\n",
    "appears: interpolation and *double descent*, reproduced from scratch in\n",
    "twenty-six lines and explained by the very quantity that the Rademacher\n",
    "calculation says is the true capacity knob: the norm of the solution.\n",
    "\n",
    "Every computation in this section is a matter of tails, norms, and least\n",
    "squares, so the worked cells below use plain NumPy, imported as `onp`, with\n",
    "`d2l` for plotting."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "mdl-concentration-generalization-concentration-and-generalization"
   },
   "source": [
    "%matplotlib inline\n",
    "from d2l import jax as d2l\n",
    "import jax\n",
    "import numpy as onp  # the worked cells compute with plain NumPy"
   ],
   "execution_count": 1,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-concentration-generalization-md-2 fw=all -->\n",
    "\n",
    "## From Chebyshev to Chernoff\n",
    "\n",
    "### Polynomial Tails Are Not Enough\n",
    "\n",
    "Recall the ladder built in that section. Markov's\n",
    "inequality the equation turns a bare mean into a tail bound; feeding\n",
    "it the squared deviation sharpens it into Chebyshev's inequality\n",
    "the equation. Applied to a sample mean $\\bar X$ of $n$ i.i.d.\n",
    "draws with variance $\\sigma^2$, Chebyshev gives\n",
    "\n",
    "$$\n",
    "P\\bigl(|\\bar X - \\mu| \\ge t\\bigr) \\le \\frac{\\sigma^2}{n\\,t^2},\n",
    "$$\n",
    "\n",
    "and this was enough to prove consistency in that section. But\n",
    "look at what it takes. To certify a miss probability of $10^{-6}$ at fixed $t$\n",
    "we must grow $n$ by a factor of a *million* relative to certifying $10^{0}$:\n",
    "the bound decays only like $1/n$. Meanwhile the exact tail of, say, a fair\n",
    "coin's head-frequency collapses *exponentially* fast; we will compute it\n",
    "below and watch Chebyshev fall behind by eight orders of magnitude at\n",
    "$n=1{,}000$ and about forty-three at $n=5{,}000$. The\n",
    "Gaussian machinery of that section (the $z$-test, the\n",
    "$1.96\\,\\hat\\sigma/\\sqrt n$ interval) implicitly knows this, since Gaussian\n",
    "tails decay like $e^{-t^2/2}$, but it gets the rate from an approximation that\n",
    "is only exact as $n\\to\\infty$. What we want is a bound with the *Gaussian\n",
    "rate* and the *finite-sample validity* of Chebyshev. The obstruction is easy to\n",
    "name: Chebyshev sees only the second moment. A tail bound that decays like\n",
    "$e^{-ct^2}$ must see *every* moment at once, and there is a single function\n",
    "that packages them all.\n",
    "\n",
    "### The Chernoff Method\n",
    "\n",
    "The *moment generating function* (MGF) of a random variable $X$ is\n",
    "$M(\\lambda)=E[e^{\\lambda X}]$; expanding the exponential shows its Taylor\n",
    "coefficients are the moments $E[X^k]$ scaled by $1/k!$, so bounding $M$ bounds\n",
    "every moment simultaneously. The *Chernoff method* is Markov's inequality\n",
    "applied not to $X$ but to $e^{\\lambda X}$ (a monotone transform, so the event\n",
    "is unchanged), followed by an optimization over the free parameter: for any\n",
    "$\\lambda>0$,\n",
    "\n",
    "$$\n",
    "P(X \\ge t)\n",
    " = P\\bigl(e^{\\lambda X} \\ge e^{\\lambda t}\\bigr)\n",
    " \\le e^{-\\lambda t}\\,E\\bigl[e^{\\lambda X}\\bigr],\n",
    "\\qquad\\textrm{hence}\\qquad\n",
    "P(X \\ge t) \\le \\inf_{\\lambda > 0}\\, e^{-\\lambda t}\\, M(\\lambda).\n",
    "$$\n",
    "\n",
    "That is the whole method. Its power appears the moment $X$ is a *sum* of\n",
    "independent terms: the MGF of a sum factors into a *product* of MGFs (the\n",
    "expectation of a product of independent variables is the product of\n",
    "expectations), so the exponent in the equation grows linearly in\n",
    "$n$, and optimizing $\\lambda$ then turns that linear-in-$n$ exponent into the\n",
    "exponential decay we are after. Everything below is this one display with a\n",
    "good bound on the MGF plugged in. For bounded variables the sharpest generic\n",
    "MGF bound is a lemma of Hoeffding; we prove it carefully because it is the\n",
    "engine of the whole section.\n",
    "\n",
    "### Hoeffding's Lemma and Hoeffding's Inequality\n",
    "\n",
    "**Proposition (Hoeffding's lemma).** *Let $X$ be a random variable with\n",
    "$E[X]=0$ taking values in $[a,b]$. Then for every $\\lambda\\in\\mathbb{R}$,*\n",
    "\n",
    "$$\n",
    "E\\bigl[e^{\\lambda X}\\bigr] \\le \\exp\\!\\left(\\frac{\\lambda^2 (b-a)^2}{8}\\right).\n",
    "$$\n",
    "\n",
    "**Proof.** Let $\\psi(\\lambda)=\\log E[e^{\\lambda X}]$, the cumulant generating\n",
    "function; for bounded $X$ it is finite and smooth, and differentiating under\n",
    "the expectation is routine. Then $\\psi(0)=0$, and\n",
    "\n",
    "$$\n",
    "\\psi'(\\lambda) = \\frac{E[X e^{\\lambda X}]}{E[e^{\\lambda X}]},\n",
    "\\qquad\\textrm{so}\\qquad\n",
    "\\psi'(0) = E[X] = 0 .\n",
    "$$\n",
    "\n",
    "The first derivative has a probabilistic reading that does all the work:\n",
    "$\\psi'(\\lambda)$ is the mean of $X$ under the *tilted* distribution\n",
    "$p_\\lambda(x) \\propto e^{\\lambda x}\\,p(x)$, a genuine probability\n",
    "distribution still supported inside $[a,b]$. Differentiating once more,\n",
    "\n",
    "$$\n",
    "\\psi''(\\lambda)\n",
    " = \\frac{E[X^2 e^{\\lambda X}]}{E[e^{\\lambda X}]}\n",
    " - \\left(\\frac{E[X e^{\\lambda X}]}{E[e^{\\lambda X}]}\\right)^{\\!2}\n",
    " = \\operatorname{Var}_{\\lambda}(X),\n",
    "$$\n",
    "\n",
    "the variance of $X$ under the tilt. Now use the fact that *any* random\n",
    "variable $Y$ supported in $[a,b]$ has variance at most $(b-a)^2/4$: variance\n",
    "is the smallest expected squared deviation over all centers (the mean\n",
    "minimizes it), and every point of $[a,b]$ lies within $(b-a)/2$ of the\n",
    "midpoint, so\n",
    "\n",
    "$$\n",
    "\\operatorname{Var}(Y)\n",
    " \\le E\\!\\left[\\Bigl(Y - \\tfrac{a+b}{2}\\Bigr)^{\\!2}\\right]\n",
    " \\le \\left(\\frac{b-a}{2}\\right)^{\\!2}.\n",
    "$$\n",
    "\n",
    "Hence $\\psi''(\\lambda) \\le (b-a)^2/4$ for *every* $\\lambda$. Taylor's theorem\n",
    "with Lagrange remainder finishes it: for some $\\xi$ between $0$ and $\\lambda$,\n",
    "\n",
    "$$\n",
    "\\psi(\\lambda)\n",
    " = \\psi(0) + \\lambda\\,\\psi'(0) + \\frac{\\lambda^2}{2}\\,\\psi''(\\xi)\n",
    " \\le \\frac{\\lambda^2 (b-a)^2}{8},\n",
    "$$\n",
    "\n",
    "and exponentiating gives the equation. $\\blacksquare$\n",
    "\n",
    "The lemma says a bounded, centered variable has an MGF *no worse than a\n",
    "Gaussian's* with standard deviation $(b-a)/2$: compare the Gaussian identity\n",
    "$E[e^{\\lambda X}]=e^{\\lambda^2\\sigma^2/2}$ for $X\\sim\\mathcal N(0,\\sigma^2)$,\n",
    "an integral done by completing the square. Feeding the lemma into\n",
    "the Chernoff method yields Hoeffding's inequality, in four lines.\n",
    "\n",
    "**Proposition (Hoeffding's inequality).** *Let $X_1,\\ldots,X_n$ be independent\n",
    "random variables with $X_i\\in[a,b]$, and let $\\bar X = \\frac1n\\sum_i X_i$.\n",
    "Then for every $t>0$,*\n",
    "\n",
    "$$\n",
    "P\\bigl(|\\bar X - E[\\bar X]| \\ge t\\bigr)\n",
    " \\le 2\\exp\\!\\left(-\\frac{2 n t^2}{(b-a)^2}\\right).\n",
    "$$\n",
    "\n",
    "**Proof.** Write $Z_i = X_i - E[X_i]$; each is centered and supported in an\n",
    "interval of length $b-a$, so the lemma applies. For any $\\lambda>0$, Chernoff\n",
    "the equation plus independence (the MGF of the sum is the product\n",
    "of MGFs) gives\n",
    "\n",
    "$$\n",
    "P(\\bar X - E[\\bar X] \\ge t)\n",
    " = P\\Bigl(\\sum_i Z_i \\ge nt\\Bigr)\n",
    " \\le e^{-\\lambda n t} \\prod_{i=1}^n E\\bigl[e^{\\lambda Z_i}\\bigr]\n",
    " \\le \\exp\\!\\left(-\\lambda n t + \\frac{n\\lambda^2 (b-a)^2}{8}\\right).\n",
    "$$\n",
    "\n",
    "The exponent is a parabola in $\\lambda$, minimized at\n",
    "$\\lambda = 4t/(b-a)^2$, where its value is $-2nt^2/(b-a)^2$. Applying the same\n",
    "argument to $-Z_i$ bounds the lower tail identically, and the *union bound*\n",
    "(the probability that at least one of several events occurs is at most the\n",
    "sum of their probabilities) applied to the two tails supplies the factor $2$.\n",
    "$\\blacksquare$\n",
    "\n",
    "This is the inequality of [@Hoeffding.1963], and it pays the main book's\n",
    "debt. that section used exactly\n",
    "the equation (with losses in $[0,1]$, so $b-a=1$) to certify a\n",
    "test-set estimate of the error rate: demanding\n",
    "$P(|\\epsilon_{\\mathcal D}(f)-\\epsilon(f)|\\ge 0.01)\\le 0.05$ and solving\n",
    "$2e^{-2nt^2}\\le\\delta$ for $n$ gives $n = \\log(2/\\delta)/(2t^2) \\approx\n",
    "18{,}445$: the \"roughly 18,500 examples\" quoted there, now a theorem rather\n",
    "than a citation. Note what the bound does *not* need: no Gaussianity, no\n",
    "variance estimate, no asymptotics. It needs only boundedness and independence,\n",
    "and it holds at every finite $n$.\n",
    "\n",
    "Inverting the inequality gives the form a practitioner actually reaches for.\n",
    "Set the right-hand side of the equation equal to $\\delta$ and\n",
    "solve for $t$: with probability at least $1-\\delta$,\n",
    "\n",
    "$$\n",
    "\\bigl|\\bar X - E[\\bar X]\\bigr|\n",
    " \\le (b-a)\\sqrt{\\frac{\\log(2/\\delta)}{2n}} .\n",
    "$$\n",
    "\n",
    "This is a *finite-sample confidence interval* in the exact sense of\n",
    "that section, with the same $1/\\sqrt n$ half-width scaling as\n",
    "the Gaussian interval the equation. But where that\n",
    "interval's coverage was asymptotic (and, as the coverage audit there measured,\n",
    "slightly optimistic at finite $n$), this one is a guarantee at every $n$. The\n",
    "trade-off is the constant: Hoeffding allows for the most adversarial\n",
    "distribution\n",
    "on $[a,b]$, so the range $b-a$ stands where the Gaussian interval enjoys the\n",
    "estimated $\\hat\\sigma$, and when the true spread is much smaller than the\n",
    "range the interval is correspondingly conservative, slack that Bernstein's\n",
    "inequality, below, is designed to recover. Keep\n",
    "the equation in view; it is the statement we will\n",
    "upgrade from one function to entire function classes in the second half of\n",
    "the section.\n",
    "\n",
    "### Sub-Gaussian and Sub-Exponential Variables\n",
    "\n",
    "The proof used only one property of the summands: an MGF bounded by a\n",
    "Gaussian's. That property deserves a name, because it is the right abstraction\n",
    "for everything that follows. A random variable $X$ is **sub-Gaussian** with\n",
    "*variance proxy* $\\sigma^2$ if\n",
    "\n",
    "$$\n",
    "E\\bigl[e^{\\lambda (X - E[X])}\\bigr] \\le \\exp\\!\\left(\\frac{\\lambda^2\\sigma^2}{2}\\right)\n",
    "\\qquad\\textrm{for all } \\lambda\\in\\mathbb{R}.\n",
    "$$\n",
    "\n",
    "The Chernoff method converts the equation directly into the\n",
    "two-sided tail $P(|X-E[X]|\\ge t)\\le 2e^{-t^2/(2\\sigma^2)}$, by the same\n",
    "optimization as above. Three families matter to us. A *Gaussian*\n",
    "$\\mathcal N(\\mu,\\sigma^2)$ is sub-Gaussian with proxy exactly $\\sigma^2$ (the\n",
    "MGF identity holds with equality). A *bounded* variable on $[a,b]$ is\n",
    "sub-Gaussian with proxy $(b-a)^2/4$; that is Hoeffding's lemma. And a\n",
    "*Rademacher* variable, a uniform random sign $\\varepsilon\\in\\{-1,+1\\}$, is\n",
    "sub-Gaussian with proxy $1$: $E[e^{\\lambda\\varepsilon}]=\\cosh\\lambda\\le\n",
    "e^{\\lambda^2/2}$, a term-by-term comparison of Taylor series left as exercise\n",
    "1. Sub-Gaussianity is closed under averaging: if $X_1,\\ldots,X_n$ are\n",
    "independent with proxy $\\sigma^2$, then $\\bar X$ is sub-Gaussian with proxy\n",
    "$\\sigma^2/n$ (the MGF product argument again), so *every* sub-Gaussian\n",
    "average concentrates at the Hoeffding rate.\n",
    "\n",
    "Not everything is sub-Gaussian. The *square* of a Gaussian (a $\\chi^2$\n",
    "variable, hence squared norms of Gaussian vectors) has a right tail decaying\n",
    "like $e^{-t/2}$, too heavy for the equation: its MGF is finite\n",
    "only for $\\lambda<\\tfrac12$, so no bound of the form\n",
    "the equation, which must hold for *all* $\\lambda$, is possible.\n",
    "Such variables are called **sub-exponential**: $X$ is sub-exponential with\n",
    "parameters $(\\nu,\\alpha)$ if\n",
    "\n",
    "$$\n",
    "E\\bigl[e^{\\lambda (X - E[X])}\\bigr] \\le \\exp\\!\\left(\\frac{\\lambda^2\\nu^2}{2}\\right)\n",
    "\\qquad\\textrm{for } |\\lambda| \\le \\frac{1}{\\alpha},\n",
    "$$\n",
    "\n",
    "a Gaussian-type MGF bound restricted to a window of $\\lambda$. The Chernoff\n",
    "optimization then splits at the window's edge: small deviations use an\n",
    "interior $\\lambda$ and get a Gaussian rate, while large deviations clamp\n",
    "$\\lambda$ at $1/\\alpha$ and get an exponential (not squared-exponential)\n",
    "rate. **Bernstein's inequality** packages both regimes: if the $X_i$ are\n",
    "independent with\n",
    "$\\operatorname{Var}(X_i)\\le\\sigma^2$ and $|X_i - E[X_i]|\\le M$, then\n",
    "\n",
    "$$\n",
    "P\\bigl(|\\bar X - E[\\bar X]| \\ge t\\bigr)\n",
    " \\le 2\\exp\\!\\left(-\\frac{n t^2}{2\\bigl(\\sigma^2 + M t/3\\bigr)}\\right),\n",
    "$$\n",
    "\n",
    "which we state without proof [@Boucheron.Lugosi.Massart.2013]. Read it as\n",
    "the variance-aware refinement of Hoeffding: for small $t$ the denominator is\n",
    "essentially $2\\sigma^2$ and the bound matches the CLT's Gaussian tail with the\n",
    "*true* variance, often far smaller than the worst case $(b-a)^2/4$ that\n",
    "Hoeffding must assume, while for large $t$ the $Mt/3$ term takes over and the\n",
    "decay is exponential in $t$, which is the best a bounded-but-skewed sum can\n",
    "do. We will lean on exactly this small-deviation sharpness when we prove norm\n",
    "concentration below.\n",
    "\n",
    "### The Tail Race in Code\n",
    "\n",
    "Claims about rates deserve a measurement. For the fair coin we can compute the\n",
    "tail $P(|\\hat p - \\tfrac12| \\ge 0.1)$ *exactly* (a finite binomial\n",
    "sum, which we evaluate in log-space so that $n=5{,}000$ does not underflow)\n",
    "and race it against Chebyshev ($\\sigma^2=\\tfrac14$, so the bound is\n",
    "$25/n$ at $t=0.1$) and Hoeffding ($2e^{-2nt^2}=2e^{-0.02n}$). No sampling is\n",
    "involved; every number below is deterministic."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "mdl-concentration-generalization-the-tail-race-in-code"
   },
   "source": [
    "t = 0.1  # deviation of the head-frequency from 1/2\n",
    "\n",
    "def exact_tail(n):  # P(|p_hat - 1/2| >= t): binomial sum in log-space\n",
    "    k = onp.arange(n + 1)\n",
    "    log_pmf = n * onp.log(0.5) + onp.concatenate(\n",
    "        ([0.0], onp.cumsum(onp.log((n - k[1:] + 1) / k[1:]))))\n",
    "    in_tail = log_pmf[onp.abs(k / n - 0.5) >= t - 1e-12]  # fp-safe boundary\n",
    "    m = in_tail.max()\n",
    "    return onp.exp(m) * onp.exp(in_tail - m).sum()  # stable log-sum-exp\n",
    "\n",
    "print(f'{\"n\":>6} {\"exact\":>10} {\"Chebyshev\":>10} {\"Hoeffding\":>10}')\n",
    "for n in (10, 100, 1000, 5000):\n",
    "    print(f'{n:6d} {exact_tail(n):10.2e} {0.25 / (n * t**2):10.2e} '\n",
    "          f'{2 * onp.exp(-2 * n * t**2):10.2e}')\n",
    "\n",
    "ns = onp.arange(10, 701, 10)\n",
    "d2l.plot(ns, [onp.array([exact_tail(n) for n in ns]),\n",
    "              0.25 / (ns * t**2), 2 * onp.exp(-2 * ns * t**2)],\n",
    "         'n', 'P(|p_hat - 1/2| >= 0.1)',\n",
    "         legend=['exact', 'Chebyshev', 'Hoeffding'], yscale='log')"
   ],
   "execution_count": 2,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "     n      exact  Chebyshev  Hoeffding\n    10   7.54e-01   2.50e+00   1.64e+00\n   100   5.69e-02   2.50e-01   2.71e-01\n  1000   2.73e-10   2.50e-02   4.12e-09\n  5000   1.30e-45   5.00e-03   7.44e-44\n"
     ]
    },
    {
     "output_type": "display_data",
     "data": {
      "image/svg+xml": "<?xml version=\"1.0\" encoding=\"utf-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n  \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<svg xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"254.2pt\" height=\"183.35625pt\" viewBox=\"0 0 254.2 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:54:57.201709</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.2 183.35625 \nL 254.2 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.7 145.8 \nL 247 145.8 \nL 247 7.2 \nL 51.7 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.00415 145.8 \nL 58.00415 7.2 \n\" clip-path=\"url(#p19ea13a4c5)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_2\">\n      <defs>\n       <path id=\"m7283738726\" d=\"M 0 0 \nL 0 3.5 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m7283738726\" x=\"58.00415\" 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(54.8229 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 109.466601 145.8 \nL 109.466601 7.2 \n\" clip-path=\"url(#p19ea13a4c5)\" 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=\"#m7283738726\" x=\"109.466601\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_2\">\n      <!-- 200 -->\n      <g transform=\"translate(99.922851 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       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_3\">\n     <g id=\"line2d_5\">\n      <path d=\"M 160.929051 145.8 \nL 160.929051 7.2 \n\" clip-path=\"url(#p19ea13a4c5)\" 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=\"#m7283738726\" x=\"160.929051\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_3\">\n      <!-- 400 -->\n      <g transform=\"translate(151.385301 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       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_4\">\n     <g id=\"line2d_7\">\n      <path d=\"M 212.391502 145.8 \nL 212.391502 7.2 \n\" clip-path=\"url(#p19ea13a4c5)\" 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=\"#m7283738726\" x=\"212.391502\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_4\">\n      <!-- 600 -->\n      <g transform=\"translate(202.847752 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       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_5\">\n     <!-- n -->\n     <g transform=\"translate(146.18125 174.076563) scale(0.1 -0.1)\">\n      <defs>\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      </defs>\n      <use xlink:href=\"#DejaVuSans-6e\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"matplotlib.axis_2\">\n    <g id=\"ytick_1\">\n     <g id=\"line2d_9\">\n      <path d=\"M 51.7 124.470829 \nL 247 124.470829 \n\" clip-path=\"url(#p19ea13a4c5)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_10\">\n      <defs>\n       <path id=\"md7cabffc98\" d=\"M 0 0 \nL -3.5 0 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#md7cabffc98\" x=\"51.7\" y=\"124.470829\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_6\">\n      <!-- $\\mathdefault{10^{-6}}$ -->\n      <g transform=\"translate(21.2 128.270047) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-31\" d=\"M 794 531 \nL 1825 531 \nL 1825 4091 \nL 703 3866 \nL 703 4441 \nL 1819 4666 \nL 2450 4666 \nL 2450 531 \nL 3481 531 \nL 3481 0 \nL 794 0 \nL 794 531 \nz\n\" transform=\"scale(0.015625)\"/>\n        <path id=\"DejaVuSans-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_11\">\n      <path d=\"M 51.7 89.781279 \nL 247 89.781279 \n\" clip-path=\"url(#p19ea13a4c5)\" 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=\"#md7cabffc98\" x=\"51.7\" y=\"89.781279\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_7\">\n      <!-- $\\mathdefault{10^{-4}}$ -->\n      <g transform=\"translate(21.2 93.580498) 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_13\">\n      <path d=\"M 51.7 55.091729 \nL 247 55.091729 \n\" clip-path=\"url(#p19ea13a4c5)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_14\">\n      <g>\n       <use xlink:href=\"#md7cabffc98\" x=\"51.7\" y=\"55.091729\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_8\">\n      <!-- $\\mathdefault{10^{-2}}$ -->\n      <g transform=\"translate(21.2 58.890948) 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_15\">\n      <path d=\"M 51.7 20.40218 \nL 247 20.40218 \n\" clip-path=\"url(#p19ea13a4c5)\" 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=\"#md7cabffc98\" x=\"51.7\" y=\"20.40218\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_9\">\n      <!-- $\\mathdefault{10^{0}}$ -->\n      <g transform=\"translate(27.1 24.201399) 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=\"text_10\">\n     <!-- P(|p_hat - 1/2| &gt;= 0.1) -->\n     <g transform=\"translate(14.842187 133.190625) rotate(-90) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-50\" d=\"M 1259 4147 \nL 1259 2394 \nL 2053 2394 \nQ 2494 2394 2734 2622 \nQ 2975 2850 2975 3272 \nQ 2975 3691 2734 3919 \nQ 2494 4147 2053 4147 \nL 1259 4147 \nz\nM 628 4666 \nL 2053 4666 \nQ 2838 4666 3239 4311 \nQ 3641 3956 3641 3272 \nQ 3641 2581 3239 2228 \nQ 2838 1875 2053 1875 \nL 1259 1875 \nL 1259 0 \nL 628 0 \nL 628 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-28\" d=\"M 1984 4856 \nQ 1566 4138 1362 3434 \nQ 1159 2731 1159 2009 \nQ 1159 1288 1364 580 \nQ 1569 -128 1984 -844 \nL 1484 -844 \nQ 1016 -109 783 600 \nQ 550 1309 550 2009 \nQ 550 2706 781 3412 \nQ 1013 4119 1484 4856 \nL 1984 4856 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-7c\" d=\"M 1344 4891 \nL 1344 -1509 \nL 813 -1509 \nL 813 4891 \nL 1344 4891 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-70\" d=\"M 1159 525 \nL 1159 -1331 \nL 581 -1331 \nL 581 3500 \nL 1159 3500 \nL 1159 2969 \nQ 1341 3281 1617 3432 \nQ 1894 3584 2278 3584 \nQ 2916 3584 3314 3078 \nQ 3713 2572 3713 1747 \nQ 3713 922 3314 415 \nQ 2916 -91 2278 -91 \nQ 1894 -91 1617 61 \nQ 1341 213 1159 525 \nz\nM 3116 1747 \nQ 3116 2381 2855 2742 \nQ 2594 3103 2138 3103 \nQ 1681 3103 1420 2742 \nQ 1159 2381 1159 1747 \nQ 1159 1113 1420 752 \nQ 1681 391 2138 391 \nQ 2594 391 2855 752 \nQ 3116 1113 3116 1747 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-5f\" d=\"M 3263 -1063 \nL 3263 -1509 \nL -63 -1509 \nL -63 -1063 \nL 3263 -1063 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-68\" 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 4863 \nL 1159 4863 \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-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-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-20\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-2d\" d=\"M 313 2009 \nL 1997 2009 \nL 1997 1497 \nL 313 1497 \nL 313 2009 \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-3e\" d=\"M 678 3150 \nL 678 3719 \nL 4684 2266 \nL 4684 1747 \nL 678 294 \nL 678 863 \nL 3897 2003 \nL 678 3150 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-3d\" d=\"M 678 2906 \nL 4684 2906 \nL 4684 2381 \nL 678 2381 \nL 678 2906 \nz\nM 678 1631 \nL 4684 1631 \nL 4684 1100 \nL 678 1100 \nL 678 1631 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-2e\" d=\"M 684 794 \nL 1344 794 \nL 1344 0 \nL 684 0 \nL 684 794 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-29\" d=\"M 513 4856 \nL 1013 4856 \nQ 1481 4119 1714 3412 \nQ 1947 2706 1947 2009 \nQ 1947 1309 1714 600 \nQ 1481 -109 1013 -844 \nL 513 -844 \nQ 928 -128 1133 580 \nQ 1338 1288 1338 2009 \nQ 1338 2731 1133 3434 \nQ 928 4138 513 4856 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-50\"/>\n      <use xlink:href=\"#DejaVuSans-28\" transform=\"translate(60.302734 0)\"/>\n      <use xlink:href=\"#DejaVuSans-7c\" transform=\"translate(99.316406 0)\"/>\n      <use xlink:href=\"#DejaVuSans-70\" transform=\"translate(133.007812 0)\"/>\n      <use xlink:href=\"#DejaVuSans-5f\" transform=\"translate(196.484375 0)\"/>\n      <use xlink:href=\"#DejaVuSans-68\" transform=\"translate(246.484375 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(309.863281 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(371.142578 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(410.351562 0)\"/>\n      <use xlink:href=\"#DejaVuSans-2d\" transform=\"translate(442.138672 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(478.222656 0)\"/>\n      <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(510.009766 0)\"/>\n      <use xlink:href=\"#DejaVuSans-2f\" transform=\"translate(573.632812 0)\"/>\n      <use xlink:href=\"#DejaVuSans-32\" transform=\"translate(607.324219 0)\"/>\n      <use xlink:href=\"#DejaVuSans-7c\" transform=\"translate(670.947266 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(704.638672 0)\"/>\n      <use xlink:href=\"#DejaVuSans-3e\" transform=\"translate(736.425781 0)\"/>\n      <use xlink:href=\"#DejaVuSans-3d\" transform=\"translate(820.214844 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(904.003906 0)\"/>\n      <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(935.791016 0)\"/>\n      <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(999.414062 0)\"/>\n      <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(1031.201172 0)\"/>\n      <use xlink:href=\"#DejaVuSans-29\" transform=\"translate(1094.824219 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"line2d_17\">\n    <path d=\"M 60.577273 22.530083 \nL 63.150395 25.57176 \nL 65.723518 28.064721 \nL 68.29664 30.315792 \nL 70.869763 32.426922 \nL 73.442885 34.445602 \nL 76.016008 36.398137 \nL 78.58913 38.300751 \nL 81.162253 40.164216 \nL 83.735375 41.996075 \nL 86.308498 43.801835 \nL 88.881621 45.585649 \nL 91.454743 47.350728 \nL 94.027866 49.099615 \nL 96.600988 50.834355 \nL 99.174111 52.556625 \nL 101.747233 54.267811 \nL 104.320356 55.96908 \nL 106.893478 57.661417 \nL 109.466601 59.345667 \nL 112.039723 61.02256 \nL 114.612846 62.692727 \nL 117.185968 64.356721 \nL 119.759091 66.01503 \nL 122.332213 67.668084 \nL 124.905336 69.316265 \nL 127.478458 70.959916 \nL 130.051581 72.599344 \nL 132.624704 74.234825 \nL 135.197826 75.866608 \nL 137.770949 77.49492 \nL 140.344071 79.119967 \nL 142.917194 80.741938 \nL 145.490316 82.361004 \nL 148.063439 83.977323 \nL 150.636561 85.59104 \nL 153.209684 87.202291 \nL 155.782806 88.811197 \nL 158.355929 90.417874 \nL 160.929051 92.022429 \nL 163.502174 93.62496 \nL 166.075296 95.225559 \nL 168.648419 96.824312 \nL 171.221542 98.421299 \nL 173.794664 100.016596 \nL 176.367787 101.610272 \nL 178.940909 103.202394 \nL 181.514032 104.793024 \nL 184.087154 106.38222 \nL 186.660277 107.970037 \nL 189.233399 109.556528 \nL 191.806522 111.14174 \nL 194.379644 112.72572 \nL 196.952767 114.308513 \nL 199.525889 115.890159 \nL 202.099012 117.470699 \nL 204.672134 119.050168 \nL 207.245257 120.628604 \nL 209.818379 122.206039 \nL 212.391502 123.782505 \nL 214.964625 125.358035 \nL 217.537747 126.932655 \nL 220.11087 128.506395 \nL 222.683992 130.07928 \nL 225.257115 131.651337 \nL 227.830237 133.222589 \nL 230.40336 134.79306 \nL 232.976482 136.362771 \nL 235.549605 137.931744 \nL 238.122727 139.5 \n\" clip-path=\"url(#p19ea13a4c5)\" style=\"fill: none; stroke: #1f77b4; stroke-width: 1.5; stroke-linecap: square\"/>\n   </g>\n   <g id=\"line2d_18\">\n    <path d=\"M 60.577273 13.5 \nL 63.150395 18.721297 \nL 65.723518 21.775561 \nL 68.29664 23.942595 \nL 70.869763 25.623477 \nL 73.442885 26.996858 \nL 76.016008 28.158035 \nL 78.58913 29.163892 \nL 81.162253 30.051121 \nL 83.735375 30.844775 \nL 86.308498 31.562722 \nL 88.881621 32.218156 \nL 91.454743 32.821097 \nL 94.027866 33.379333 \nL 96.600988 33.899038 \nL 99.174111 34.38519 \nL 101.747233 34.841859 \nL 104.320356 35.272419 \nL 106.893478 35.679693 \nL 109.466601 36.066072 \nL 112.039723 36.433596 \nL 114.612846 36.784019 \nL 117.185968 37.118863 \nL 119.759091 37.439453 \nL 122.332213 37.746955 \nL 124.905336 38.042394 \nL 127.478458 38.326682 \nL 130.051581 38.60063 \nL 132.624704 38.864964 \nL 135.197826 39.120335 \nL 137.770949 39.367333 \nL 140.344071 39.606487 \nL 142.917194 39.838282 \nL 145.490316 40.063157 \nL 148.063439 40.281512 \nL 150.636561 40.493716 \nL 153.209684 40.700106 \nL 155.782806 40.900991 \nL 158.355929 41.096657 \nL 160.929051 41.28737 \nL 163.502174 41.473373 \nL 166.075296 41.654893 \nL 168.648419 41.832142 \nL 171.221542 42.005317 \nL 173.794664 42.174599 \nL 176.367787 42.34016 \nL 178.940909 42.502161 \nL 181.514032 42.660751 \nL 184.087154 42.81607 \nL 186.660277 42.968252 \nL 189.233399 43.11742 \nL 191.806522 43.263692 \nL 194.379644 43.407177 \nL 196.952767 43.54798 \nL 199.525889 43.686199 \nL 202.099012 43.821928 \nL 204.672134 43.955254 \nL 207.245257 44.086261 \nL 209.818379 44.215029 \nL 212.391502 44.341633 \nL 214.964625 44.466144 \nL 217.537747 44.58863 \nL 220.11087 44.709157 \nL 222.683992 44.827785 \nL 225.257115 44.944574 \nL 227.830237 45.05958 \nL 230.40336 45.172856 \nL 232.976482 45.284454 \nL 235.549605 45.394423 \nL 238.122727 45.50281 \n\" clip-path=\"url(#p19ea13a4c5)\" style=\"fill: none; stroke-dasharray: 5.55,2.4; stroke-dashoffset: 0; stroke: #bf00bf; stroke-width: 1.5\"/>\n   </g>\n   <g id=\"line2d_19\">\n    <path d=\"M 60.577273 16.68743 \nL 63.150395 18.193978 \nL 65.723518 19.700526 \nL 68.29664 21.207074 \nL 70.869763 22.713622 \nL 73.442885 24.22017 \nL 76.016008 25.726718 \nL 78.58913 27.233266 \nL 81.162253 28.739814 \nL 83.735375 30.246362 \nL 86.308498 31.75291 \nL 88.881621 33.259458 \nL 91.454743 34.766006 \nL 94.027866 36.272554 \nL 96.600988 37.779102 \nL 99.174111 39.28565 \nL 101.747233 40.792198 \nL 104.320356 42.298746 \nL 106.893478 43.805294 \nL 109.466601 45.311842 \nL 112.039723 46.81839 \nL 114.612846 48.324938 \nL 117.185968 49.831486 \nL 119.759091 51.338034 \nL 122.332213 52.844582 \nL 124.905336 54.35113 \nL 127.478458 55.857678 \nL 130.051581 57.364226 \nL 132.624704 58.870774 \nL 135.197826 60.377322 \nL 137.770949 61.88387 \nL 140.344071 63.390418 \nL 142.917194 64.896966 \nL 145.490316 66.403514 \nL 148.063439 67.910062 \nL 150.636561 69.41661 \nL 153.209684 70.923158 \nL 155.782806 72.429706 \nL 158.355929 73.936254 \nL 160.929051 75.442802 \nL 163.502174 76.94935 \nL 166.075296 78.455898 \nL 168.648419 79.962446 \nL 171.221542 81.468994 \nL 173.794664 82.975542 \nL 176.367787 84.48209 \nL 178.940909 85.988638 \nL 181.514032 87.495186 \nL 184.087154 89.001734 \nL 186.660277 90.508282 \nL 189.233399 92.01483 \nL 191.806522 93.521378 \nL 194.379644 95.027926 \nL 196.952767 96.534474 \nL 199.525889 98.041022 \nL 202.099012 99.54757 \nL 204.672134 101.054118 \nL 207.245257 102.560666 \nL 209.818379 104.067214 \nL 212.391502 105.573762 \nL 214.964625 107.08031 \nL 217.537747 108.586858 \nL 220.11087 110.093406 \nL 222.683992 111.599954 \nL 225.257115 113.106502 \nL 227.830237 114.61305 \nL 230.40336 116.119598 \nL 232.976482 117.626146 \nL 235.549605 119.132694 \nL 238.122727 120.639242 \n\" clip-path=\"url(#p19ea13a4c5)\" style=\"fill: none; stroke-dasharray: 9.6,2.4,1.5,2.4; stroke-dashoffset: 0; stroke: #008000; stroke-width: 1.5\"/>\n   </g>\n   <g id=\"patch_3\">\n    <path d=\"M 51.7 145.8 \nL 51.7 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 247 145.8 \nL 247 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.7 145.8 \nL 247 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.7 7.2 \nL 247 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.7 140.8 \nL 146.059375 140.8 \nQ 148.059375 140.8 148.059375 138.8 \nL 148.059375 95.765625 \nQ 148.059375 93.765625 146.059375 93.765625 \nL 58.7 93.765625 \nQ 56.7 93.765625 56.7 95.765625 \nL 56.7 138.8 \nQ 56.7 140.8 58.7 140.8 \nz\n\" style=\"fill: #ffffff; opacity: 0.8; stroke: #cccccc; stroke-linejoin: miter\"/>\n    </g>\n    <g id=\"line2d_20\">\n     <path d=\"M 60.7 101.864063 \nL 70.7 101.864063 \nL 80.7 101.864063 \n\" style=\"fill: none; stroke: #1f77b4; stroke-width: 1.5; stroke-linecap: square\"/>\n    </g>\n    <g id=\"text_11\">\n     <!-- exact -->\n     <g transform=\"translate(88.7 105.364063) scale(0.1 -0.1)\">\n      <defs>\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-78\" d=\"M 3513 3500 \nL 2247 1797 \nL 3578 0 \nL 2900 0 \nL 1881 1375 \nL 863 0 \nL 184 0 \nL 1544 1831 \nL 300 3500 \nL 978 3500 \nL 1906 2253 \nL 2834 3500 \nL 3513 3500 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-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      </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     </g>\n    </g>\n    <g id=\"line2d_21\">\n     <path d=\"M 60.7 116.542188 \nL 70.7 116.542188 \nL 80.7 116.542188 \n\" style=\"fill: none; stroke-dasharray: 5.55,2.4; stroke-dashoffset: 0; stroke: #bf00bf; stroke-width: 1.5\"/>\n    </g>\n    <g id=\"text_12\">\n     <!-- Chebyshev -->\n     <g transform=\"translate(88.7 120.042188) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-43\" d=\"M 4122 4306 \nL 4122 3641 \nQ 3803 3938 3442 4084 \nQ 3081 4231 2675 4231 \nQ 1875 4231 1450 3742 \nQ 1025 3253 1025 2328 \nQ 1025 1406 1450 917 \nQ 1875 428 2675 428 \nQ 3081 428 3442 575 \nQ 3803 722 4122 1019 \nL 4122 359 \nQ 3791 134 3420 21 \nQ 3050 -91 2638 -91 \nQ 1578 -91 968 557 \nQ 359 1206 359 2328 \nQ 359 3453 968 4101 \nQ 1578 4750 2638 4750 \nQ 3056 4750 3426 4639 \nQ 3797 4528 4122 4306 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-62\" d=\"M 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\nM 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 \nL 1159 0 \nL 581 0 \nL 581 4863 \nL 1159 4863 \nL 1159 2969 \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-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-76\" d=\"M 191 3500 \nL 800 3500 \nL 1894 563 \nL 2988 3500 \nL 3597 3500 \nL 2284 0 \nL 1503 0 \nL 191 3500 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-43\"/>\n      <use xlink:href=\"#DejaVuSans-68\" transform=\"translate(69.824219 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(133.203125 0)\"/>\n      <use xlink:href=\"#DejaVuSans-62\" transform=\"translate(194.726562 0)\"/>\n      <use xlink:href=\"#DejaVuSans-79\" transform=\"translate(258.203125 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(317.382812 0)\"/>\n      <use xlink:href=\"#DejaVuSans-68\" transform=\"translate(369.482422 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(432.861328 0)\"/>\n      <use xlink:href=\"#DejaVuSans-76\" transform=\"translate(494.384766 0)\"/>\n     </g>\n    </g>\n    <g id=\"line2d_22\">\n     <path d=\"M 60.7 131.220313 \nL 70.7 131.220313 \nL 80.7 131.220313 \n\" style=\"fill: none; stroke-dasharray: 9.6,2.4,1.5,2.4; stroke-dashoffset: 0; stroke: #008000; stroke-width: 1.5\"/>\n    </g>\n    <g id=\"text_13\">\n     <!-- Hoeffding -->\n     <g transform=\"translate(88.7 134.720313) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-48\" d=\"M 628 4666 \nL 1259 4666 \nL 1259 2753 \nL 3553 2753 \nL 3553 4666 \nL 4184 4666 \nL 4184 0 \nL 3553 0 \nL 3553 2222 \nL 1259 2222 \nL 1259 0 \nL 628 0 \nL 628 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-6f\" d=\"M 1959 3097 \nQ 1497 3097 1228 2736 \nQ 959 2375 959 1747 \nQ 959 1119 1226 758 \nQ 1494 397 1959 397 \nQ 2419 397 2687 759 \nQ 2956 1122 2956 1747 \nQ 2956 2369 2687 2733 \nQ 2419 3097 1959 3097 \nz\nM 1959 3584 \nQ 2709 3584 3137 3096 \nQ 3566 2609 3566 1747 \nQ 3566 888 3137 398 \nQ 2709 -91 1959 -91 \nQ 1206 -91 779 398 \nQ 353 888 353 1747 \nQ 353 2609 779 3096 \nQ 1206 3584 1959 3584 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-66\" d=\"M 2375 4863 \nL 2375 4384 \nL 1825 4384 \nQ 1516 4384 1395 4259 \nQ 1275 4134 1275 3809 \nL 1275 3500 \nL 2222 3500 \nL 2222 3053 \nL 1275 3053 \nL 1275 0 \nL 697 0 \nL 697 3053 \nL 147 3053 \nL 147 3500 \nL 697 3500 \nL 697 3744 \nQ 697 4328 969 4595 \nQ 1241 4863 1831 4863 \nL 2375 4863 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-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-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-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-48\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(75.195312 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(136.376953 0)\"/>\n      <use xlink:href=\"#DejaVuSans-66\" transform=\"translate(197.900391 0)\"/>\n      <use xlink:href=\"#DejaVuSans-66\" transform=\"translate(233.105469 0)\"/>\n      <use xlink:href=\"#DejaVuSans-64\" transform=\"translate(268.310547 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(331.787109 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(359.570312 0)\"/>\n      <use xlink:href=\"#DejaVuSans-67\" transform=\"translate(422.949219 0)\"/>\n     </g>\n    </g>\n   </g>\n  </g>\n </g>\n <defs>\n  <clipPath id=\"p19ea13a4c5\">\n   <rect x=\"51.7\" 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-concentration-generalization-md-3 fw=all -->\n",
    "\n",
    "At $n=10$ both\n",
    "bounds are vacuous (above $1$) while the exact tail is $0.75$: nothing\n",
    "concentrates in ten flips. At $n=100$ Chebyshev ($0.25$) is actually a shade\n",
    "*tighter* than Hoeffding ($0.27$): for small $n$ the comparison is between\n",
    "constants, and Chebyshev's use of the true variance $\\tfrac14$ helps it. But\n",
    "rates always beat constants. By $n=1{,}000$ the exact tail is\n",
    "$2.7\\times10^{-10}$ and Hoeffding certifies $4.1\\times10^{-9}$, within a\n",
    "factor of about $15$ (one order of magnitude), while Chebyshev still allows a\n",
    "miss probability of\n",
    "$2.5\\%$, off by *eight orders of magnitude*; at $n=5{,}000$ the gap has grown\n",
    "to about forty-three orders. The log-scale plot makes the geometry plain: the\n",
    "exact tail\n",
    "and Hoeffding's bound are parallel straight lines (exponential decay;\n",
    "Hoeffding's exponent $2t^2=0.02$ is close to the optimal rate,\n",
    "which *large-deviations theory* identifies as the Kullback--Leibler divergence\n",
    "$\\mathrm{KL}(0.6\\,\\|\\,0.5)\\approx 0.0201$, an information-theoretic measure of\n",
    "how distinguishable two distributions are; that section\n",
    "develops both), while Chebyshev's gentle curve is\n",
    "polynomial decay that no constant can rescue.\n",
    "\n",
    "## Probability in High Dimension\n",
    "\n",
    "Concentration governs more than sample means over datasets. The coordinates of\n",
    "a random *vector* are also \"many independent contributions\", so the same\n",
    "inequalities govern the geometry of high-dimensional space, and that geometry\n",
    "is where deep learning lives. The phenomenon has a name: **concentration of\n",
    "measure**, the fact that in high dimension any sufficiently well-behaved\n",
    "function of many independent coordinates is nearly constant, with fluctuations\n",
    "exponentially rare. This section quantifies it.\n",
    "that section stated two facts\n",
    "while cataloguing the multivariate Gaussian: the norm of a\n",
    "$d$-dimensional standard Gaussian locks onto $\\sqrt d$, and two independent\n",
    "draws are nearly orthogonal. Here we give both facts their quantitative\n",
    "treatment.\n",
    "\n",
    "### Norm Concentration\n",
    "\n",
    "**Proposition (norm concentration).** *Let\n",
    "$\\mathbf x\\sim\\mathcal N(\\mathbf 0,\\mathbf I_d)$. For every $0<\\varepsilon\\le 1$,*\n",
    "\n",
    "$$\n",
    "P\\!\\left(\\Bigl|\\frac{\\|\\mathbf x\\|}{\\sqrt d} - 1\\Bigr| \\ge \\varepsilon\\right)\n",
    " \\le 2\\exp\\!\\left(-\\frac{d\\,\\varepsilon^2}{8}\\right).\n",
    "$$\n",
    "\n",
    "**Proof sketch.** The squared norm $\\|\\mathbf x\\|^2=\\sum_{i=1}^d x_i^2$ is a\n",
    "sum of $d$ i.i.d. variables $x_i^2$ with mean $1$: exactly a sample-mean\n",
    "problem, except the summands are unbounded, so Hoeffding does not apply\n",
    "directly. They are, however, sub-exponential, precisely the small-$\\lambda$\n",
    "regime defined above. The MGF is\n",
    "explicit, $E[e^{\\lambda(x_i^2-1)}] = e^{-\\lambda}/\\sqrt{1-2\\lambda}$ for\n",
    "$\\lambda<\\tfrac12$, and a one-line series comparison (which we state and skip;\n",
    "see [@Vershynin.2018], §2.7) shows\n",
    "\n",
    "$$\n",
    "E\\bigl[e^{\\lambda (x_i^2 - 1)}\\bigr] \\le e^{2\\lambda^2}\n",
    "\\qquad\\textrm{for } |\\lambda| \\le \\tfrac14 .\n",
    "$$\n",
    "\n",
    "This is sub-exponentiality with $\\nu^2=4$ and $\\alpha=4$. Chernoff with this\n",
    "bound gives, for any $0<\\lambda\\le\\tfrac14$,\n",
    "\n",
    "$$\n",
    "P\\Bigl(\\sum_i (x_i^2 - 1) \\ge d\\varepsilon\\Bigr)\n",
    " \\le \\exp\\bigl(-\\lambda d \\varepsilon + 2 d \\lambda^2\\bigr),\n",
    "$$\n",
    "\n",
    "and the unconstrained minimizer $\\lambda=\\varepsilon/4$ is admissible\n",
    "precisely when $\\varepsilon\\le 1$, yielding $e^{-d\\varepsilon^2/8}$; the lower\n",
    "tail and the factor $2$ follow as in Hoeffding's inequality. Finally convert\n",
    "squares to norms: writing $z=\\|\\mathbf x\\|/\\sqrt d\\ge 0$, if $|z-1|\\ge\\varepsilon$\n",
    "then $|z^2-1|=|z-1|\\,(z+1)\\ge\\varepsilon$, so the norm event implies the\n",
    "squared-norm event and inherits its bound.\n",
    "\n",
    "First, the *fluctuation of $\\|\\mathbf x\\|$ is of constant\n",
    "order*: the bound says deviations of $\\|\\mathbf x\\|$ from $\\sqrt d$ beyond\n",
    "$\\varepsilon\\sqrt d$ are exponentially rare in $d$, and a finer analysis puts\n",
    "the standard deviation of $\\|\\mathbf x\\|$ near $1/\\sqrt2$ *independently of\n",
    "$d$*. A standard Gaussian in $\\mathbb{R}^d$ is therefore a **thin shell** of\n",
    "radius $\\sqrt d$ and thickness $O(1)$; the mental picture of a fuzzy ball\n",
    "around the origin fails in high dimension. Second, the mode is not the mass:\n",
    "the density is largest at the\n",
    "origin, yet the volume of a radius-$r$ shell grows like $r^{d-1}$, and the\n",
    "fight between decaying density and exploding volume is settled overwhelmingly\n",
    "at $r\\approx\\sqrt d$. In $d=784$ (an MNIST-sized Gaussian) a typical draw has\n",
    "norm within a few percent of $28$; a draw with norm below $14$ has probability at most $2e^{-24}$ by\n",
    "the equation, so it is extraordinarily unlikely in an\n",
    "ordinary experiment.\n",
    "\n",
    "### Near-Orthogonality Revisited\n",
    "\n",
    "The second fact is the cosine. that section\n",
    "proved that the cosine between independent random directions has mean $0$ and\n",
    "standard deviation $\\approx 1/\\sqrt d$; that section\n",
    "restated it for Gaussians. Concentration puts that \"typical\" statement into\n",
    "the same exponential frame as everything else in this section, and the\n",
    "mechanism is *Hoeffding again*. Fix a unit vector\n",
    "$\\mathbf u$ and let the coordinates of $\\mathbf x$ be independent, centered,\n",
    "and of unit variance, either uniform random signs $x_i\\in\\{-1,+1\\}$ or\n",
    "standard Gaussians (the former are bounded, the latter sub-Gaussian with\n",
    "proxy $1$ via the equation; either property suffices below).\n",
    "The inner product $\\langle\\mathbf x,\\mathbf u\\rangle=\\sum_i\n",
    "u_i x_i$ is a sum of independent terms, the $i$-th bounded by $|u_i|$, and the\n",
    "general Hoeffding inequality for non-identical ranges (exercise 2) gives\n",
    "\n",
    "$$\n",
    "P\\bigl(|\\langle\\mathbf x,\\mathbf u\\rangle| \\ge s\\bigr)\n",
    " \\le 2\\exp\\!\\left(-\\frac{s^2}{2\\sum_i u_i^2}\\right) = 2 e^{-s^2/2},\n",
    "$$\n",
    "\n",
    "since $\\sum_i u_i^2=1$. The inner product with any fixed direction is $O(1)$,\n",
    "while the unit-variance coordinates pin the norm of $\\mathbf x$ to\n",
    "$\\approx\\sqrt d$: exactly $\\sqrt d$ for random signs, and within\n",
    "$(1\\pm\\varepsilon)\\sqrt d$ for Gaussians by\n",
    "the equation. The cosine is therefore $O(1/\\sqrt d)$\n",
    "with exponentially high probability: taking\n",
    "$s=\\varepsilon\\sqrt d$, a cosine larger than $\\approx\\varepsilon$ has\n",
    "probability at most $\\approx 2e^{-d\\varepsilon^2/2}$. High-dimensional space\n",
    "holds exponentially many pairwise-nearly-orthogonal directions: a union bound\n",
    "over the fewer than $m^2$ pairs among $m$ independent draws keeps every\n",
    "pairwise cosine below $\\approx\\varepsilon$ whenever\n",
    "$2m^2 e^{-d\\varepsilon^2/2}<1$, which allows $m$ of order\n",
    "$e^{d\\varepsilon^2/4}$, so *random directions come nearly orthogonal by\n",
    "default, exponentially many at a time*.\n",
    "\n",
    "### Three Consequences for Deep Learning\n",
    "\n",
    "**Initialization scales.** LeCun and He initialization\n",
    "[@He.Zhang.Ren.ea.2015] draw the weight rows of\n",
    "a layer with variance $1/d$ (or $2/d$ for ReLU), and the standard telling\n",
    "(that section) checks variances: each pre-activation\n",
    "$\\langle\\mathbf w,\\mathbf x\\rangle$ has variance $\\|\\mathbf x\\|^2/d\\approx 1$.\n",
    "For a **single wide random layer**, analogous concentration results can make\n",
    "this variance calculation representative: under independence or weak-dependence\n",
    "and tail assumptions, the empirical activation norm is close to its expectation\n",
    "with high probability. Iterating the statement through a deep nonlinear network\n",
    "is a different problem. Dependencies accumulate across layers, and preserving\n",
    "mean variance does not guarantee controlled singular values or dynamical\n",
    "isometry. A forward-pass norm check is therefore a useful diagnostic, not a\n",
    "proof that all signals remain stable through depth.\n",
    "\n",
    "**Distance concentration and nearest neighbors.** For two independent draws\n",
    "the difference $\\mathbf x-\\mathbf y$ is again a Gaussian vector, now with\n",
    "coordinate variance $2$, so the equation applies to it\n",
    "verbatim: each pairwise distance lands in $(1\\pm\\varepsilon)\\sqrt{2d}$ except\n",
    "with probability $2e^{-d\\varepsilon^2/8}$. Among $n$ unstructured points there\n",
    "are fewer than $n^2$ pairs, and a union bound puts *every* distance in that\n",
    "shell as soon as\n",
    "\n",
    "$$\n",
    "n^2 \\cdot 2e^{-d\\varepsilon^2/8} \\le \\delta,\n",
    "\\qquad\\textrm{i.e.}\\qquad\n",
    "d \\ \\ge\\ \\frac{8}{\\varepsilon^2}\\log\\frac{2n^2}{\\delta} :\n",
    "$$\n",
    "\n",
    "a dimension only *logarithmic* in the number of points suffices to flatten the\n",
    "entire distance matrix into a band of relative width $\\varepsilon$. (File the\n",
    "move away for the next section: a union bound converting one exponential tail\n",
    "into a simultaneous guarantee over many objects, with only a logarithmic\n",
    "increase in the deviation, is\n",
    "precisely how learning bounds are built.) The nearest and farthest neighbor of\n",
    "a query then differ by a vanishing relative margin (the contrast\n",
    "$(d_{\\max}-d_{\\min})/d_{\\min}$ collapses) and nearest-neighbor retrieval\n",
    "degenerates into noise-ranking. Real embeddings\n",
    "escape because they are structured: semantic similarity places data near a\n",
    "low-dimensional set inside $\\mathbb{R}^d$, so observed distance histograms are\n",
    "far broader than the concentration prediction, and the size of that gap is one\n",
    "gauge of how much structure an embedding carries.\n",
    "\n",
    "**The thin shell and the mean.** The shell picture corrects a beginner's\n",
    "mental model that matters in generative modeling: the \"most likely point\" of a\n",
    "high-dimensional Gaussian prior (the origin) is nowhere near a *typical*\n",
    "point. Decoders are trained on inputs of norm $\\approx\\sqrt d$, so evaluating\n",
    "one at the mean, or at the midpoint of two latent draws (norm\n",
    "$\\approx\\sqrt{d/2}$, well inside the shell), feeds it an input unlike anything\n",
    "it saw in training; this is why latent-space interpolation is done along the\n",
    "sphere rather than the chord. The shell is also why the MVN cell of\n",
    "that section saw norm ratios pinned to $1.000$: it was\n",
    "measuring means; the cell below measures the *whole distribution*.\n",
    "\n",
    "### Measuring the Shell\n",
    "\n",
    "The distributions chapter verified the *means* of the norm ratio and the\n",
    "cosine. Concentration makes distributional claims: what *fraction* of the\n",
    "mass sits inside the shell $(1\\pm\\varepsilon)\\sqrt d$, and how badly\n",
    "nearest-neighbor contrast collapses. Those are what we measure, at\n",
    "$\\varepsilon=0.1$."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "mdl-concentration-generalization-measuring-the-shell"
   },
   "source": [
    "rng = onp.random.default_rng(0)\n",
    "eps, num_pts = 0.1, 10000\n",
    "for d in (2, 20, 200, 2000):\n",
    "    x = rng.standard_normal((num_pts, d))\n",
    "    ratio = onp.linalg.norm(x, axis=1) / onp.sqrt(d)\n",
    "    shell = onp.mean(onp.abs(ratio - 1) <= eps)      # mass in the 10% shell\n",
    "    query, points = x[0], x[1:201]                   # 1 query, 200 neighbors\n",
    "    dist = onp.linalg.norm(points - query, axis=1)\n",
    "    contrast = (dist.max() - dist.min()) / dist.min()\n",
    "    print(f'd={d:5d}:  mass within (1±0.1)·sqrt(d): {shell:6.1%},   '\n",
    "          f'NN contrast (d_max-d_min)/d_min = {contrast:6.3f}')"
   ],
   "execution_count": 3,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "d=    2:  mass within (1±0.1)·sqrt(d):  14.8%,   NN contrast (d_max-d_min)/d_min = 29.440\nd=   20:  mass within (1±0.1)·sqrt(d):  47.6%,   NN contrast (d_max-d_min)/d_min =  1.234\nd=  200:  mass within (1±0.1)·sqrt(d):  95.4%,   NN contrast (d_max-d_min)/d_min =  0.239\n"
     ]
    },
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "d= 2000:  mass within (1±0.1)·sqrt(d): 100.0%,   NN contrast (d_max-d_min)/d_min =  0.079\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-concentration-generalization-md-4 fw=all -->\n",
    "\n",
    "In $d=2$ the \"shell\" holds under $15\\%$ of the mass: low dimension really is\n",
    "a fuzzy ball, and the nearest and farthest of $200$ points differ by a factor\n",
    "of $30$. By $d=200$ the same $\\pm10\\%$ shell already captures $95\\%$ of the\n",
    "mass, close to what the equation's Gaussian-rate reading\n",
    "predicts ($\\pm 2$ standard deviations at $\\sigma\\approx 1/\\sqrt{2d}=0.05$),\n",
    "and at $d=2000$ the empirical mass is $100.0\\%$: not one of ten thousand draws\n",
    "left the shell. The nearest-neighbor contrast tells the matching story,\n",
    "collapsing from $29.4$ to $0.08$: in $d=2000$ the farthest of two hundred\n",
    "random points is only $8\\%$ farther than the nearest, so \"nearest\" no longer\n",
    "means much.\n",
    "\n",
    "## From One Estimate to Uniform Convergence\n",
    "\n",
    "### The Function Chosen After the Data\n",
    "\n",
    "Return to learning, where a subtlety voids everything proved so far.\n",
    "Hoeffding's inequality certifies the empirical risk of **one fixed function**:\n",
    "choose $f$, *then* draw the sample $S=\\{(\\mathbf x_i,y_i)\\}_{i=1}^n$, and the\n",
    "empirical risk $\\hat R(f)=\\frac1n\\sum_i \\ell(f(\\mathbf x_i),y_i)$ sits within\n",
    "$t$ of the true risk $R(f)=E[\\ell(f(\\mathbf x),y)]$ except with probability\n",
    "$2e^{-2nt^2}$. A test set works exactly because it respects this order: the\n",
    "model was frozen before the test data were drawn. But a *learner* violates the\n",
    "order by construction: it searches a class $\\mathcal F$ and returns the\n",
    "$\\hat f$ that makes $\\hat R$ small *on the sample it saw*. The empirical risk\n",
    "of $\\hat f$ is a minimum of fluctuating quantities, selected precisely where\n",
    "the fluctuation is most favorable, and its optimism is not covered by any\n",
    "single-function bound. The quantity that must concentrate is the *worst case\n",
    "over the class*,\n",
    "\n",
    "$$\n",
    "\\sup_{f\\in\\mathcal F}\\ \\bigl|\\hat R(f) - R(f)\\bigr|,\n",
    "$$\n",
    "\n",
    "because if this supremum is at most $t$ then *every* function's empirical risk\n",
    "is trustworthy to $t$, including whichever one the learner happens to pick.\n",
    "Bounds on this supremum are called **uniform convergence** bounds, and they\n",
    "are the classical mechanics that that section waves at.\n",
    "The *test-set reuse* discussed in\n",
    "that section is the same trap: an analyst who\n",
    "evaluates many models on one test set and reports the best is a learner whose\n",
    "\"class\" is the set of models tried. The bound we prove next quantifies this\n",
    "when the pool of models is fixed *before* the test data are drawn; what\n",
    "happens when it is not, we take up right after the proof.\n",
    "\n",
    "### Finite Classes: the Union Bound\n",
    "\n",
    "For a finite class the repair is one line of probability.\n",
    "\n",
    "**Proposition (finite-class uniform convergence).** *Let $\\mathcal F$ be\n",
    "finite, let the loss take values in $[0,1]$, and let $S$ be an i.i.d. sample\n",
    "of size $n$. Then with probability at least $1-\\delta$,*\n",
    "\n",
    "$$\n",
    "\\bigl|\\hat R(f) - R(f)\\bigr|\n",
    " \\le \\sqrt{\\frac{\\log(2|\\mathcal F|/\\delta)}{2n}}\n",
    "\\qquad\\textrm{simultaneously for every } f\\in\\mathcal F .\n",
    "$$\n",
    "\n",
    "**Proof.** For each fixed $f$, $\\hat R(f)$ is an average of $n$ i.i.d. terms\n",
    "in $[0,1]$, so Hoeffding the equation gives\n",
    "$P(|\\hat R(f)-R(f)|\\ge t)\\le 2e^{-2nt^2}$. The probability that *any* of the\n",
    "$|\\mathcal F|$ bad events occurs is at most the sum of their probabilities\n",
    "(the union bound again), i.e. $2|\\mathcal F|e^{-2nt^2}$. Setting this to\n",
    "$\\delta$ and solving for $t$ gives the claim. $\\blacksquare$\n",
    "\n",
    "Read the bound the way a practitioner should: $\\log|\\mathcal F|$ **is the\n",
    "price of choice**. Guaranteeing one function puts $\\log(2/\\delta)$ in the\n",
    "numerator; guaranteeing the freedom to pick among $|\\mathcal F|$ adds\n",
    "$\\log|\\mathcal F|$: one extra bit of sample information per bit of selection\n",
    "freedom. Since the deviation shrinks like the square root, the\n",
    "sample size needed grows only *logarithmically* in the class size, which is\n",
    "why choosing among even thousands of hyperparameter configurations on a\n",
    "$10{,}000$-point validation set is tolerable: $t$ grows only from\n",
    "$\\sqrt{\\log(2/\\delta)/2n}\\approx 0.014$ to\n",
    "$\\sqrt{\\log(2\\cdot 2000/\\delta)/2n}\\approx 0.024$ at $\\delta=0.05$. Even a\n",
    "*million* models widen the guarantee only to $\\approx 0.030$, a factor of\n",
    "$2.18$ over the single-function interval. But mind the hypothesis doing the\n",
    "work: the union bound treats $\\mathcal F$ as fixed *before* the sample is\n",
    "drawn, so this arithmetic covers a pre-registered pool of candidates. A\n",
    "leaderboard is different. When each submission is chosen after seeing earlier\n",
    "scores on the same test set, the models are data-dependent functions, the\n",
    "proposition's \"for each fixed $f$\" fails, and the equation\n",
    "does not apply; guarantees then degrade much faster, and analyzing how is the\n",
    "subject of *adaptive data analysis* [@Dwork.Feldman.Hardt.ea.2015]. This\n",
    "is that section's test-set-reuse warning, now\n",
    "with both its constant and its boundary.\n",
    "\n",
    "### Rademacher Complexity\n",
    "\n",
    "Real hypothesis classes are infinite (every $\\mathbf w\\in\\mathbb{R}^d$ is a\n",
    "different linear classifier), so the union bound stalls. The classical escapes\n",
    "either *discretize* the class (covering numbers: replace $\\mathcal F$ by the\n",
    "finitely many centers of small balls that cover it, and union-bound over\n",
    "those) or count its effective\n",
    "behaviors on $n$ points (the VC dimension of [@Vapnik.Chervonenkis.1971],\n",
    "sketched in\n",
    "that section). The modern tool is more\n",
    "direct, and it starts from a question a machine learner can act on: **how well\n",
    "can the class correlate with pure noise?** Let\n",
    "$\\varepsilon_1,\\ldots,\\varepsilon_n$ be i.i.d. Rademacher variables (fair\n",
    "random signs) and define the **empirical Rademacher complexity** of a class\n",
    "$\\mathcal F$ on the sample $S=(\\mathbf x_1,\\ldots,\\mathbf x_n)$ as\n",
    "\n",
    "$$\n",
    "\\widehat{\\mathfrak R}_S(\\mathcal F)\n",
    " = E_{\\boldsymbol\\varepsilon}\\!\\left[\\,\n",
    "   \\sup_{f\\in\\mathcal F}\\ \\frac1n \\sum_{i=1}^n \\varepsilon_i\\, f(\\mathbf x_i)\n",
    " \\right],\n",
    "$$\n",
    "\n",
    "with $\\mathfrak R_n(\\mathcal F)=E_S[\\widehat{\\mathfrak R}_S(\\mathcal F)]$ its\n",
    "average over samples. The random signs are fictitious labels with *no signal\n",
    "whatsoever*; the supremum asks how large a sample correlation the class can\n",
    "manufacture with them anyway. A class that can chase arbitrary coin flips\n",
    "($\\widehat{\\mathfrak R}\\approx 1$) can chase the noise in real labels too and\n",
    "its empirical risks mean little; a class that cannot\n",
    "($\\widehat{\\mathfrak R}\\to 0$) has empirical means that track true means. That\n",
    "intuition is a theorem:\n",
    "\n",
    "**Uniform convergence via Rademacher complexity**\n",
    "[@Bartlett.Mendelson.2002]. *For $\\mathcal F$ taking values in $[0,1]$,\n",
    "with probability at least $1-\\delta$ over the sample,*\n",
    "\n",
    "$$\n",
    "R(f) \\le \\hat R(f) + 2\\,\\mathfrak R_n(\\mathcal F)\n",
    " + \\sqrt{\\frac{\\log(1/\\delta)}{2n}}\n",
    "\\qquad\\textrm{simultaneously for every } f\\in\\mathcal F .\n",
    "$$\n",
    "\n",
    "In this statement $\\mathcal F$ is the *loss* class: its members are the\n",
    "functions $(\\mathbf x,y)\\mapsto\\ell(f(\\mathbf x),y)$, which do take values in\n",
    "$[0,1]$; the bookkeeping paragraph at the end of this subsection converts\n",
    "between it and the predictor class.\n",
    "We do not give the full proof, but its central move, *symmetrization* (the\n",
    "step that conjures coin flips out of a statement that contains none), is short\n",
    "enough to sketch, and it explains the factor $2$. Introduce a *ghost sample*\n",
    "$S'$: a second, fictitious dataset of size $n$, independent of $S$, that\n",
    "exists only inside the analysis. Since $R(f)=E_{S'}[\\hat R_{S'}(f)]$, Jensen's\n",
    "inequality (that section) bounds the expected uniform deviation\n",
    "by a comparison of two concrete samples,\n",
    "\n",
    "$$\n",
    "E_S\\Bigl[\\sup_{f} \\bigl(R(f) - \\hat R_S(f)\\bigr)\\Bigr]\n",
    " \\le E_{S,S'}\\Bigl[\\sup_{f} \\frac1n \\sum_{i=1}^n\n",
    " \\bigl(\\ell'_i(f) - \\ell_i(f)\\bigr)\\Bigr],\n",
    "$$\n",
    "\n",
    "with $\\ell_i,\\ell'_i$ the losses on the $i$-th real and ghost points. Now the\n",
    "trick: $S$ and $S'$ are i.i.d., so swapping the $i$-th real and ghost points\n",
    "leaves the joint distribution unchanged, which means each difference\n",
    "$\\ell'_i-\\ell_i$ can be multiplied by an independent random sign\n",
    "$\\varepsilon_i$ *for free*. Splitting the signed sum into its two halves\n",
    "leaves $2\\,E[\\sup_f \\frac1n\\sum_i \\varepsilon_i \\ell_i(f)] =\n",
    "2\\,\\mathfrak R_n(\\ell\\circ\\mathcal F)$: the unknown truth has vanished, and a\n",
    "correlation with coin flips stands in its place. The final step from this\n",
    "statement *in expectation* to the high-probability form\n",
    "the equation is *McDiarmid's inequality*\n",
    "[@McDiarmid.1989], the extension of\n",
    "Hoeffding from sums to any function that no single coordinate can move much\n",
    "(here, changing one sample point moves the supremum by at most $1/n$); it is\n",
    "stated in exercise 3, where it also puts an error bar on the bootstrap.\n",
    "Sanity-check the theorem at its ends. A singleton class has $\\widehat{\\mathfrak R}=0$ (the expectation of\n",
    "$\\frac1n\\sum\\varepsilon_i f(\\mathbf x_i)$ is $0$ with nothing to optimize) and\n",
    "the equation collapses to one-sided Hoeffding. A finite\n",
    "class obeys $\\mathfrak R_n \\le \\sqrt{2\\log|\\mathcal F|/n}$ (Massart's lemma\n",
    "[@Boucheron.Lugosi.Massart.2013]),\n",
    "recovering the equation up to constants; for binary\n",
    "classes the growth-function/VC machinery is exactly a bound on how \"finite\"\n",
    "the class effectively is on $n$ points, giving\n",
    "$\\mathfrak R_n\\lesssim\\sqrt{d_{\\mathrm{VC}}\\log n / n}$\n",
    "[@boucheron2005theory]. At the other end, the class of *all* functions\n",
    "into $[-1,1]$ matches every sign pattern perfectly,\n",
    "$\\widehat{\\mathfrak R}=1$, and the bound is vacuous, as it must be, since\n",
    "that class can memorize anything.\n",
    "\n",
    "### The Linear Class in Closed Form\n",
    "\n",
    "Rademacher complexity would be a definition without teeth if it could not be\n",
    "*computed*. For the class deep learning cares most about, linear functions\n",
    "with a norm constraint, the computation is four lines, and its conclusion\n",
    "drives the rest of the section.\n",
    "\n",
    "**Proposition (Rademacher complexity of a norm-bounded linear class).** *Let\n",
    "$\\mathcal F=\\{\\mathbf x\\mapsto\\langle\\mathbf w,\\mathbf x\\rangle :\n",
    "\\|\\mathbf w\\|_2\\le B\\}$ and suppose the sample satisfies\n",
    "$\\|\\mathbf x_i\\|_2\\le r$ for all $i$. Then*\n",
    "\n",
    "$$\n",
    "\\widehat{\\mathfrak R}_S(\\mathcal F) \\le \\frac{B\\,r}{\\sqrt n}.\n",
    "$$\n",
    "\n",
    "**Proof.** The supremum is explicit: by linearity and Cauchy--Schwarz (with\n",
    "equality at $\\mathbf w$ aligned to the sum),\n",
    "\n",
    "$$\n",
    "\\sup_{\\|\\mathbf w\\|\\le B}\\ \\frac1n\\sum_{i=1}^n\n",
    " \\varepsilon_i \\langle\\mathbf w,\\mathbf x_i\\rangle\n",
    " = \\sup_{\\|\\mathbf w\\|\\le B}\\ \\frac1n\n",
    "   \\Bigl\\langle\\mathbf w,\\ \\sum_i \\varepsilon_i\\mathbf x_i\\Bigr\\rangle\n",
    " = \\frac Bn\\,\\Bigl\\|\\sum_{i=1}^n \\varepsilon_i\\mathbf x_i\\Bigr\\| .\n",
    "$$\n",
    "\n",
    "Jensen's inequality (that section; the square root is concave)\n",
    "moves the expectation inside the square:\n",
    "\n",
    "$$\n",
    "E_{\\boldsymbol\\varepsilon}\\Bigl\\|\\sum_i\\varepsilon_i\\mathbf x_i\\Bigr\\|\n",
    " \\le \\sqrt{E_{\\boldsymbol\\varepsilon}\\Bigl\\|\\sum_i\\varepsilon_i\\mathbf x_i\\Bigr\\|^2}\n",
    " = \\sqrt{\\sum_{i,j} E[\\varepsilon_i\\varepsilon_j]\\,\n",
    "   \\langle\\mathbf x_i,\\mathbf x_j\\rangle}\n",
    " = \\sqrt{\\sum_i \\|\\mathbf x_i\\|^2}\n",
    " \\le r\\sqrt n,\n",
    "$$\n",
    "\n",
    "the cross terms vanishing because independent signs have\n",
    "$E[\\varepsilon_i\\varepsilon_j]=0$ for $i\\ne j$. Multiplying by $B/n$ gives\n",
    "$Br/\\sqrt n$. $\\blacksquare$\n",
    "\n",
    "Now look at what is *absent* from the equation: the\n",
    "dimension $d$. A linear class over a million features and over ten features\n",
    "has the *same* bound only when both its weight-radius $B$ and input-radius $r$\n",
    "match. Thus parameter count does not appear explicitly; capacity in this bound\n",
    "is controlled by the **product** $Br$. Changing or adding features can change\n",
    "$r$, so weight norm alone is not an invariant measure of capacity. This single line is the\n",
    "theory behind weight decay (that section): shrinking\n",
    "$\\|\\mathbf w\\|$ shrinks $B$, which shrinks the one term in\n",
    "the equation the learner can control. Hold on to it; it\n",
    "is also the key that unlocks double descent in the final section, where the\n",
    "*norm* of an interpolating solution will fall even as its parameter count\n",
    "grows.\n",
    "\n",
    "One bookkeeping step stitches the two propositions together.\n",
    "the equation wants the complexity of the *loss* class\n",
    "$\\ell\\circ\\mathcal F$ (the functions whose empirical means we actually\n",
    "compare), while the equation computes that of the\n",
    "*predictor* class $\\mathcal F$. The bridge is the *contraction principle*\n",
    "[@Boucheron.Lugosi.Massart.2013]: composing every $f\\in\\mathcal F$ with\n",
    "one fixed $L$-Lipschitz function $\\phi$ multiplies the Rademacher complexity\n",
    "by at most $L$ after centering $\\phi(0)=0$; subtracting the constant\n",
    "$\\phi(0)$ does not affect the signed complexity. Thus\n",
    "$\\widehat{\\mathfrak R}_S(\\phi\\circ\\mathcal F)\\le\n",
    "L\\,\\widehat{\\mathfrak R}_S(\\mathcal F)$. Margin losses (the hinge, the\n",
    "clipped square, the logistic) are Lipschitz in the prediction, so the loss\n",
    "class of the norm-bounded linear model inherits the bound\n",
    "$L\\,Br/\\sqrt n$ and the norm-controls-capacity conclusion survives the\n",
    "composition intact.\n",
    "\n",
    "### Why the Bounds Go Vacuous, and Why the Language Survives\n",
    "\n",
    "Apply this machinery to a modern network\n",
    "and the numbers are useless. [@zhang2021understanding] trained standard\n",
    "architectures to zero training error on CIFAR-10 with *randomly shuffled\n",
    "labels* (on ImageNet, random-label training still reaches near-perfect\n",
    "*training* accuracy): the class realized by \"this architecture, trained by\n",
    "SGD\" can correlate essentially perfectly with coin flips, so its Rademacher\n",
    "complexity on such\n",
    "samples is essentially $1$ and the equation certifies\n",
    "nothing; norm-based refinements, evaluated at the sizes practitioners use,\n",
    "yield bounds orders of magnitude above the trivial bound of $1$. This is a\n",
    "fact about *these bounds*, the ones that take\n",
    "uniform convergence over the entire representable class.\n",
    "The same experiment shows the same network generalizing on real\n",
    "labels, so what needs explaining is a property of the *reached* solution, not\n",
    "the reachable set, and the modern program is to shrink the class to\n",
    "\"functions the optimizer actually finds on data like this\" and measure *its*\n",
    "complexity. Uniform convergence remains the right language for saying what a\n",
    "generalization guarantee even is; what failed is the crude choice of\n",
    "$\\mathcal F$, and the last section of this chapter shows, in a model small\n",
    "enough to solve, exactly how a giant class can reliably deliver small-norm,\n",
    "well-generalizing solutions.\n",
    "\n",
    "### Coin Flips in Code\n",
    "\n",
    "Both halves of the story are measurable. First we estimate\n",
    "$\\widehat{\\mathfrak R}_S$ for the norm-bounded linear class by Monte Carlo:\n",
    "the proof gave the supremum in closed form,\n",
    "$\\frac Bn\\|\\sum_i\\varepsilon_i\\mathbf x_i\\|$, so we just average that norm\n",
    "over random sign draws and compare against $Br/\\sqrt n$. Then we exhibit the\n",
    "Zhang phenomenon in miniature: a class rich enough to *interpolate* (here,\n",
    "minimum-norm least squares on $p=2n$ random features, via the pseudoinverse of\n",
    "that section) achieves correlation $1$ with every coin\n",
    "flip it is shown."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "mdl-concentration-generalization-coin-flips-in-code"
   },
   "source": [
    "rng = onp.random.default_rng(0)\n",
    "n, d, B, num_sigma = 50, 20, 1.0, 2000\n",
    "X = rng.standard_normal((n, d))\n",
    "X /= onp.linalg.norm(X, axis=1, keepdims=True)     # ||x_i|| = r = 1\n",
    "signs = rng.choice([-1.0, 1.0], size=(num_sigma, n))\n",
    "sup_corr = B * onp.linalg.norm(signs @ X, axis=1) / n  # closed-form supremum\n",
    "print(f'Monte-Carlo Rademacher complexity  = {sup_corr.mean():.4f}')\n",
    "print(f'bound B*r/sqrt(n)                  = {B / onp.sqrt(n):.4f}')\n",
    "\n",
    "# The Zhang phenomenon in miniature: an interpolating class hits corr = 1\n",
    "Phi = rng.standard_normal((n, 2 * n))        # p = 2n features: interpolation\n",
    "W = onp.linalg.pinv(Phi) @ signs.T           # min-norm fit to every flip set\n",
    "corr = onp.mean(signs.T * (Phi @ W), axis=0)     # (1/n) sum_i eps_i f(x_i)\n",
    "w_norm = onp.linalg.norm(W, axis=0).mean()\n",
    "r_phi = onp.linalg.norm(Phi, axis=1).mean()\n",
    "print(f'correlation of min-norm fits with coin flips = {corr.mean():.4f}')\n",
    "print(f'norm it costs: mean ||w|| = {w_norm:.2f};  implied capacity bound '\n",
    "      f'B*r/sqrt(n) = {w_norm * r_phi / onp.sqrt(n):.2f}')"
   ],
   "execution_count": 4,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "Monte-Carlo Rademacher complexity  = 0.1390\nbound B*r/sqrt(n)                  = 0.1414\ncorrelation of min-norm fits with coin flips = 1.0000\nnorm it costs: mean ||w|| = 1.00;  implied capacity bound B*r/sqrt(n) = 1.41\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-concentration-generalization-md-5 fw=all -->\n",
    "\n",
    "The Monte-Carlo estimate is $0.1390$ against the bound $0.1414$: the\n",
    "Cauchy--Schwarz/Jensen argument is nearly tight, losing under $2\\%$ (the only\n",
    "slack is Jensen's step, and $\\|\\sum\\varepsilon_i\\mathbf x_i\\|$ has small\n",
    "relative fluctuation: concentration again). So a unit-norm linear class on\n",
    "fifty unit-norm points can fake a correlation of about $0.14$ with pure noise,\n",
    "and no more: its empirical risks are meaningful. The interpolating class, by\n",
    "contrast, scores a correlation of exactly $1.0000$ on every one of the two\n",
    "thousand sign patterns; it is the all-functions endpoint of the theorem, in\n",
    "twenty features and fifty points. The norm it needed is printed next to it:\n",
    "the\n",
    "sign-fitting solutions need norm about $1.0$ on features of norm about $10$,\n",
    "so the smallest linear class containing them has capacity bound\n",
    "$Br/\\sqrt n\\approx 1.41 > 1$, vacuous, exactly as the previous subsection\n",
    "said it must be. The two prints summarize the section: the capacity that\n",
    "matters is the norm the fit actually uses on the data.\n",
    "\n",
    "## Interpolation and Double Descent\n",
    "\n",
    "### The U-Curve, Revisited\n",
    "\n",
    "The classical picture of generalization is the U-curve, and this chapter\n",
    "derived it in full: the bias--variance decomposition\n",
    "the equation of that section splits the test\n",
    "error into a falling squared-bias term and a rising variance term as capacity\n",
    "grows, with a sweet spot between. Uniform convergence tells the same story in\n",
    "different units: more capacity means more Rademacher complexity in the bound.\n",
    "Both tellings tacitly assume the interesting regime is the one where the model\n",
    "*cannot* fit the training data perfectly. Modern practice lives on the other\n",
    "side. Networks are routinely trained to (near-)zero training error, that is,\n",
    "they *interpolate*, and past the **interpolation threshold**, where parameters\n",
    "suffice to fit every training point, the classical curves have nothing more to\n",
    "say: empirical risk is identically zero for every model in sight, and the\n",
    "observed test error *falls again* as capacity keeps growing. This second fall\n",
    "is **double descent** [@Belkin.Hsu.Ma.ea.2019; @nakkiran2021deep].\n",
    "that section surveys the phenomenon across deep models;\n",
    "this section is its mathematical home: we now build the smallest model that\n",
    "exhibits it, locate the peak exactly, and explain both descents with the tools\n",
    "already on the table.\n",
    "\n",
    "### The Minimum-Norm Mechanism\n",
    "\n",
    "The smallest such model is **random-features regression**\n",
    "[@Rahimi.Recht.2007]. Fix a feature map\n",
    "built from randomness (ours will be $\\phi(\\mathbf x)=\\mathrm{ReLU}\n",
    "(\\mathbf V\\mathbf x)$ with a random frozen $\\mathbf V$, a one-hidden-layer\n",
    "network whose first layer is never trained) and fit only the linear head\n",
    "$\\mathbf w\\in\\mathbb{R}^p$ by least squares on $n$ training points. The\n",
    "feature count $p$ is a capacity dial we can sweep straight through the\n",
    "threshold $p=n$, and the fitted model changes character three times along the\n",
    "way. Write $\\boldsymbol\\Phi\\in\\mathbb{R}^{n\\times p}$ for the feature matrix\n",
    "and fit $\\mathbf w=\\boldsymbol\\Phi^{+}\\mathbf y$ with the pseudoinverse of\n",
    "that section, which returns the least-squares solution\n",
    "for $p<n$ and the **minimum-norm interpolant** for $p\\ge n$.\n",
    "\n",
    "*Below the threshold* ($p<n$) the system is overdetermined: the fit cannot\n",
    "match all $n$ labels, residual noise is averaged rather than reproduced, and\n",
    "the classical U-curve logic applies verbatim: bias falls and variance rises\n",
    "with $p$.\n",
    "\n",
    "*At the threshold* ($p=n$) the feature matrix is square, and interpolation\n",
    "requires inverting it: $\\mathbf w=\\boldsymbol\\Phi^{-1}\\mathbf y$. A random\n",
    "square matrix is almost surely invertible but almost never *well*\n",
    "invertible: its smallest singular value $\\sigma_{\\min}$ is typically tiny,\n",
    "and the condition-number lens of that section says\n",
    "what happens next: the solution acquires a component of size\n",
    "$\\langle\\mathbf u_{\\min},\\mathbf y\\rangle/\\sigma_{\\min}$ along the worst\n",
    "direction. The labels' noise, which a regression is supposed to average away,\n",
    "is instead *divided by a near-zero number*. The solution norm explodes and the\n",
    "test error spikes. This is the peak of double descent, and it is a\n",
    "conditioning event.\n",
    "\n",
    "*Beyond the threshold* ($p>n$) interpolation is easy: infinitely many\n",
    "$\\mathbf w$ fit exactly, and the pseudoinverse picks the smallest. With\n",
    "*nested* features (each model uses the first $p$\n",
    "columns of one master matrix) this yields an exact monotonicity: any\n",
    "interpolant\n",
    "available at $p$ is still available at $p+1$ by padding with a zero, so the\n",
    "feasible set only grows and\n",
    "\n",
    "$$\n",
    "\\bigl\\|\\mathbf w^{(p+1)}_{\\min}\\bigr\\| \\le \\bigl\\|\\mathbf w^{(p)}_{\\min}\\bigr\\| :\n",
    "$$\n",
    "\n",
    "**more nested features let the minimum-norm interpolant get no larger.** This is\n",
    "a useful part of the mechanism, but it is not by itself a Rademacher-complexity\n",
    "proof of the second descent. The bound the equation depends\n",
    "on $Br$: as $p$ grows here, $\\|\\mathbf w\\|$ falls while the random-feature\n",
    "norm $\\|\\boldsymbol\\phi(\\mathbf x)\\|$ grows. Moreover, selecting the radius\n",
    "from the fitted, data-dependent solution requires a localized or\n",
    "algorithm-dependent argument. The experiment below therefore tracks solution\n",
    "norm as a diagnostic correlated with test error, not as a complete capacity\n",
    "certificate.\n",
    "\n",
    "### Double Descent in Twenty-Six Lines\n",
    "\n",
    "Now the full double-descent curve, from scratch. Forty training points\n",
    "from a noisy linear teacher in fifteen dimensions; ReLU random features with\n",
    "nested columns; the head fit by `pinv`: least squares below the threshold,\n",
    "minimum-norm interpolation above it. We sweep $p$ from $2$ to $400$ straight\n",
    "through $p=n=40$, and we track the two quantities the mechanism says to watch:\n",
    "the test error and $\\|\\mathbf w\\|$. Medians over $20$ independent runs keep\n",
    "the curve readable."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "mdl-concentration-generalization-double-descent-in-twenty-five-lines"
   },
   "source": [
    "rng = onp.random.default_rng(0)\n",
    "n, n_test, d_in, p_max, trials, noise = 40, 500, 15, 400, 20, 0.1\n",
    "p_grid = onp.array([2, 5, 10, 15, 20, 25, 30, 35, 38, 40, 42, 45, 50, 60,\n",
    "                    80, 120, 200, 400])\n",
    "test_mse, train_mse, w_norm = (onp.zeros((trials, len(p_grid)))\n",
    "                               for _ in range(3))\n",
    "for tr in range(trials):\n",
    "    beta = rng.standard_normal(d_in)\n",
    "    beta /= onp.linalg.norm(beta)                    # teacher: y = <beta, x>\n",
    "    X, X_te = (rng.standard_normal((m, d_in)) for m in (n, n_test))\n",
    "    y = X @ beta + noise * rng.standard_normal(n)    # noisy training labels\n",
    "    y_te = X_te @ beta\n",
    "    V = rng.standard_normal((p_max, d_in)) / onp.sqrt(d_in)\n",
    "    Phi, Phi_te = onp.maximum(X @ V.T, 0), onp.maximum(X_te @ V.T, 0)\n",
    "    for j, p in enumerate(p_grid):                   # nested feature prefixes\n",
    "        w = onp.linalg.pinv(Phi[:, :p]) @ y  # least-squares/min-norm solution\n",
    "        test_mse[tr, j] = onp.mean((Phi_te[:, :p] @ w - y_te) ** 2)\n",
    "        train_mse[tr, j] = onp.mean((Phi[:, :p] @ w - y) ** 2)\n",
    "        w_norm[tr, j] = onp.linalg.norm(w)\n",
    "med = [onp.median(a, axis=0) for a in (test_mse, train_mse, w_norm)]\n",
    "for j, p in enumerate(p_grid):\n",
    "    print(f'p={p:3d}  test MSE={med[0][j]:9.4f}  train MSE={med[1][j]:9.2e}'\n",
    "          f'  ||w||={med[2][j]:7.2f}')\n",
    "d2l.plot(p_grid, [med[0], med[2]], 'number of random features p',\n",
    "         'median over 20 runs', legend=['test MSE', '||w|| of the fit'],\n",
    "         xscale='log', yscale='log')"
   ],
   "execution_count": 5,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "p=  2  test MSE=   1.0378  train MSE= 8.67e-01  ||w||=   0.32\np=  5  test MSE=   0.9627  train MSE= 7.70e-01  ||w||=   0.77\np= 10  test MSE=   0.7728  train MSE= 4.64e-01  ||w||=   1.68\np= 15  test MSE=   0.6782  train MSE= 2.81e-01  ||w||=   1.97\np= 20  test MSE=   0.7156  train MSE= 1.54e-01  ||w||=   2.15\np= 25  test MSE=   0.6905  train MSE= 8.10e-02  ||w||=   2.37\np= 30  test MSE=   0.6893  train MSE= 4.32e-02  ||w||=   2.70\np= 35  test MSE=   1.5061  train MSE= 1.32e-02  ||w||=   3.75\np= 38  test MSE=   2.1205  train MSE= 5.00e-03  ||w||=   4.61\np= 40  test MSE=  33.6376  train MSE= 1.00e-28  ||w||=  18.52\np= 42  test MSE=   1.9858  train MSE= 1.15e-29  ||w||=   4.96\np= 45  test MSE=   1.1249  train MSE= 7.16e-30  ||w||=   3.64\np= 50  test MSE=   0.6466  train MSE= 7.35e-30  ||w||=   2.42\np= 60  test MSE=   0.3507  train MSE= 5.36e-30  ||w||=   1.70\np= 80  test MSE=   0.1824  train MSE= 5.72e-30  ||w||=   1.18\np=120  test MSE=   0.1121  train MSE= 7.99e-30  ||w||=   0.83\np=200  test MSE=   0.0796  train MSE= 9.07e-30  ||w||=   0.59\np=400  test MSE=   0.0604  train MSE= 7.00e-30  ||w||=   0.39\n"
     ]
    },
    {
     "output_type": "display_data",
     "data": {
      "image/svg+xml": "<?xml version=\"1.0\" encoding=\"utf-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n  \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<svg xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"253.878125pt\" height=\"183.35625pt\" viewBox=\"0 0 253.878125 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:54:58.378247</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 253.878125 183.35625 \nL 253.878125 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 114.18731 145.8 \nL 114.18731 7.2 \n\" clip-path=\"url(#p01848b40eb)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_2\">\n      <defs>\n       <path id=\"md47f4bd891\" d=\"M 0 0 \nL 0 3.5 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#md47f4bd891\" x=\"114.18731\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_1\">\n      <!-- $\\mathdefault{10^{1}}$ -->\n      <g transform=\"translate(105.38731 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        <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-31\" transform=\"translate(0 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(128.203125 38.965625) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_2\">\n     <g id=\"line2d_3\">\n      <path d=\"M 191.346432 145.8 \nL 191.346432 7.2 \n\" clip-path=\"url(#p01848b40eb)\" 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=\"#md47f4bd891\" x=\"191.346432\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_2\">\n      <!-- $\\mathdefault{10^{2}}$ -->\n      <g transform=\"translate(182.546432 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-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=\"xtick_3\">\n     <g id=\"line2d_5\">\n      <defs>\n       <path id=\"m7583a666ce\" d=\"M 0 0 \nL 0 2 \n\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m7583a666ce\" x=\"60.255398\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_4\">\n     <g id=\"line2d_6\">\n      <g>\n       <use xlink:href=\"#m7583a666ce\" x=\"73.842445\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_5\">\n     <g id=\"line2d_7\">\n      <g>\n       <use xlink:href=\"#m7583a666ce\" x=\"83.482608\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_6\">\n     <g id=\"line2d_8\">\n      <g>\n       <use xlink:href=\"#m7583a666ce\" x=\"90.960099\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_7\">\n     <g id=\"line2d_9\">\n      <g>\n       <use xlink:href=\"#m7583a666ce\" x=\"97.069655\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_8\">\n     <g id=\"line2d_10\">\n      <g>\n       <use xlink:href=\"#m7583a666ce\" x=\"102.23521\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_9\">\n     <g id=\"line2d_11\">\n      <g>\n       <use xlink:href=\"#m7583a666ce\" x=\"106.709818\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_10\">\n     <g id=\"line2d_12\">\n      <g>\n       <use xlink:href=\"#m7583a666ce\" x=\"110.656702\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_11\">\n     <g id=\"line2d_13\">\n      <g>\n       <use xlink:href=\"#m7583a666ce\" x=\"137.41452\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_12\">\n     <g id=\"line2d_14\">\n      <g>\n       <use xlink:href=\"#m7583a666ce\" x=\"151.001567\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_13\">\n     <g id=\"line2d_15\">\n      <g>\n       <use xlink:href=\"#m7583a666ce\" x=\"160.64173\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_14\">\n     <g id=\"line2d_16\">\n      <g>\n       <use xlink:href=\"#m7583a666ce\" x=\"168.119222\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_15\">\n     <g id=\"line2d_17\">\n      <g>\n       <use xlink:href=\"#m7583a666ce\" x=\"174.228777\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_16\">\n     <g id=\"line2d_18\">\n      <g>\n       <use xlink:href=\"#m7583a666ce\" x=\"179.394333\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_17\">\n     <g id=\"line2d_19\">\n      <g>\n       <use xlink:href=\"#m7583a666ce\" x=\"183.86894\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_18\">\n     <g id=\"line2d_20\">\n      <g>\n       <use xlink:href=\"#m7583a666ce\" x=\"187.815824\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_19\">\n     <g id=\"line2d_21\">\n      <g>\n       <use xlink:href=\"#m7583a666ce\" x=\"214.573642\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_20\">\n     <g id=\"line2d_22\">\n      <g>\n       <use xlink:href=\"#m7583a666ce\" x=\"228.160689\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_21\">\n     <g id=\"line2d_23\">\n      <g>\n       <use xlink:href=\"#m7583a666ce\" x=\"237.800852\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_22\">\n     <g id=\"line2d_24\">\n      <g>\n       <use xlink:href=\"#m7583a666ce\" x=\"245.278344\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_3\">\n     <!-- number of random features p -->\n     <g transform=\"translate(75.117969 174.076563) scale(0.1 -0.1)\">\n      <defs>\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-75\" d=\"M 544 1381 \nL 544 3500 \nL 1119 3500 \nL 1119 1403 \nQ 1119 906 1312 657 \nQ 1506 409 1894 409 \nQ 2359 409 2629 706 \nQ 2900 1003 2900 1516 \nL 2900 3500 \nL 3475 3500 \nL 3475 0 \nL 2900 0 \nL 2900 538 \nQ 2691 219 2414 64 \nQ 2138 -91 1772 -91 \nQ 1169 -91 856 284 \nQ 544 659 544 1381 \nz\nM 1991 3584 \nL 1991 3584 \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-62\" d=\"M 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\nM 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 \nL 1159 0 \nL 581 0 \nL 581 4863 \nL 1159 4863 \nL 1159 2969 \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-72\" d=\"M 2631 2963 \nQ 2534 3019 2420 3045 \nQ 2306 3072 2169 3072 \nQ 1681 3072 1420 2755 \nQ 1159 2438 1159 1844 \nL 1159 0 \nL 581 0 \nL 581 3500 \nL 1159 3500 \nL 1159 2956 \nQ 1341 3275 1631 3429 \nQ 1922 3584 2338 3584 \nQ 2397 3584 2469 3576 \nQ 2541 3569 2628 3553 \nL 2631 2963 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-20\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-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-66\" d=\"M 2375 4863 \nL 2375 4384 \nL 1825 4384 \nQ 1516 4384 1395 4259 \nQ 1275 4134 1275 3809 \nL 1275 3500 \nL 2222 3500 \nL 2222 3053 \nL 1275 3053 \nL 1275 0 \nL 697 0 \nL 697 3053 \nL 147 3053 \nL 147 3500 \nL 697 3500 \nL 697 3744 \nQ 697 4328 969 4595 \nQ 1241 4863 1831 4863 \nL 2375 4863 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-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-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-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-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-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-6e\"/>\n      <use xlink:href=\"#DejaVuSans-75\" transform=\"translate(63.378906 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6d\" transform=\"translate(126.757812 0)\"/>\n      <use xlink:href=\"#DejaVuSans-62\" transform=\"translate(224.169922 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(287.646484 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(349.169922 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(390.283203 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(422.070312 0)\"/>\n      <use xlink:href=\"#DejaVuSans-66\" transform=\"translate(483.251953 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(518.457031 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(550.244141 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(591.357422 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(652.636719 0)\"/>\n      <use xlink:href=\"#DejaVuSans-64\" transform=\"translate(716.015625 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(779.492188 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6d\" transform=\"translate(840.673828 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(938.085938 0)\"/>\n      <use xlink:href=\"#DejaVuSans-66\" transform=\"translate(969.873047 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(1005.078125 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(1066.601562 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(1127.880859 0)\"/>\n      <use xlink:href=\"#DejaVuSans-75\" transform=\"translate(1167.089844 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(1230.46875 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(1269.332031 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(1330.855469 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(1382.955078 0)\"/>\n      <use xlink:href=\"#DejaVuSans-70\" transform=\"translate(1414.742188 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"matplotlib.axis_2\">\n    <g id=\"ytick_1\">\n     <g id=\"line2d_25\">\n      <path d=\"M 51.378125 129.452364 \nL 246.678125 129.452364 \n\" clip-path=\"url(#p01848b40eb)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_26\">\n      <defs>\n       <path id=\"mef4bc1acf1\" d=\"M 0 0 \nL -3.5 0 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#mef4bc1acf1\" x=\"51.378125\" y=\"129.452364\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_4\">\n      <!-- $\\mathdefault{10^{-1}}$ -->\n      <g transform=\"translate(20.878125 133.251582) 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.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-31\" transform=\"translate(186.855469 38.965625) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_2\">\n     <g id=\"line2d_27\">\n      <path d=\"M 51.378125 83.5638 \nL 246.678125 83.5638 \n\" clip-path=\"url(#p01848b40eb)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_28\">\n      <g>\n       <use xlink:href=\"#mef4bc1acf1\" x=\"51.378125\" y=\"83.5638\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_5\">\n      <!-- $\\mathdefault{10^{0}}$ -->\n      <g transform=\"translate(26.778125 87.363019) 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_3\">\n     <g id=\"line2d_29\">\n      <path d=\"M 51.378125 37.675236 \nL 246.678125 37.675236 \n\" clip-path=\"url(#p01848b40eb)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_30\">\n      <g>\n       <use xlink:href=\"#mef4bc1acf1\" x=\"51.378125\" y=\"37.675236\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_6\">\n      <!-- $\\mathdefault{10^{1}}$ -->\n      <g transform=\"translate(26.778125 41.474455) 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-31\" transform=\"translate(128.203125 38.965625) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_4\">\n     <g id=\"line2d_31\">\n      <defs>\n       <path id=\"mcaad94f47c\" d=\"M 0 0 \nL -2 0 \n\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#mcaad94f47c\" x=\"51.378125\" y=\"143.266198\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_5\">\n     <g id=\"line2d_32\">\n      <g>\n       <use xlink:href=\"#mcaad94f47c\" x=\"51.378125\" y=\"139.632684\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_6\">\n     <g id=\"line2d_33\">\n      <g>\n       <use xlink:href=\"#mcaad94f47c\" x=\"51.378125\" y=\"136.560592\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_7\">\n     <g id=\"line2d_34\">\n      <g>\n       <use xlink:href=\"#mcaad94f47c\" x=\"51.378125\" y=\"133.899425\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_8\">\n     <g id=\"line2d_35\">\n      <g>\n       <use xlink:href=\"#mcaad94f47c\" x=\"51.378125\" y=\"131.552109\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_9\">\n     <g id=\"line2d_36\">\n      <g>\n       <use xlink:href=\"#mcaad94f47c\" x=\"51.378125\" y=\"115.63853\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_10\">\n     <g id=\"line2d_37\">\n      <g>\n       <use xlink:href=\"#mcaad94f47c\" x=\"51.378125\" y=\"107.557955\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_11\">\n     <g id=\"line2d_38\">\n      <g>\n       <use xlink:href=\"#mcaad94f47c\" x=\"51.378125\" y=\"101.824695\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_12\">\n     <g id=\"line2d_39\">\n      <g>\n       <use xlink:href=\"#mcaad94f47c\" x=\"51.378125\" y=\"97.377634\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_13\">\n     <g id=\"line2d_40\">\n      <g>\n       <use xlink:href=\"#mcaad94f47c\" x=\"51.378125\" y=\"93.74412\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_14\">\n     <g id=\"line2d_41\">\n      <g>\n       <use xlink:href=\"#mcaad94f47c\" x=\"51.378125\" y=\"90.672028\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_15\">\n     <g id=\"line2d_42\">\n      <g>\n       <use xlink:href=\"#mcaad94f47c\" x=\"51.378125\" y=\"88.010861\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_16\">\n     <g id=\"line2d_43\">\n      <g>\n       <use xlink:href=\"#mcaad94f47c\" x=\"51.378125\" y=\"85.663545\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_17\">\n     <g id=\"line2d_44\">\n      <g>\n       <use xlink:href=\"#mcaad94f47c\" x=\"51.378125\" y=\"69.749966\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_18\">\n     <g id=\"line2d_45\">\n      <g>\n       <use xlink:href=\"#mcaad94f47c\" x=\"51.378125\" y=\"61.669391\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_19\">\n     <g id=\"line2d_46\">\n      <g>\n       <use xlink:href=\"#mcaad94f47c\" x=\"51.378125\" y=\"55.936132\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_20\">\n     <g id=\"line2d_47\">\n      <g>\n       <use xlink:href=\"#mcaad94f47c\" x=\"51.378125\" y=\"51.48907\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_21\">\n     <g id=\"line2d_48\">\n      <g>\n       <use xlink:href=\"#mcaad94f47c\" x=\"51.378125\" y=\"47.855557\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_22\">\n     <g id=\"line2d_49\">\n      <g>\n       <use xlink:href=\"#mcaad94f47c\" x=\"51.378125\" y=\"44.783465\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_23\">\n     <g id=\"line2d_50\">\n      <g>\n       <use xlink:href=\"#mcaad94f47c\" x=\"51.378125\" y=\"42.122297\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_24\">\n     <g id=\"line2d_51\">\n      <g>\n       <use xlink:href=\"#mcaad94f47c\" x=\"51.378125\" y=\"39.774982\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_25\">\n     <g id=\"line2d_52\">\n      <g>\n       <use xlink:href=\"#mcaad94f47c\" x=\"51.378125\" y=\"23.861402\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_26\">\n     <g id=\"line2d_53\">\n      <g>\n       <use xlink:href=\"#mcaad94f47c\" x=\"51.378125\" y=\"15.780827\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_27\">\n     <g id=\"line2d_54\">\n      <g>\n       <use xlink:href=\"#mcaad94f47c\" x=\"51.378125\" y=\"10.047568\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_7\">\n     <!-- median over 20 runs -->\n     <g transform=\"translate(14.798438 128.521094) rotate(-90) scale(0.1 -0.1)\">\n      <defs>\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-76\" d=\"M 191 3500 \nL 800 3500 \nL 1894 563 \nL 2988 3500 \nL 3597 3500 \nL 2284 0 \nL 1503 0 \nL 191 3500 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-6d\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(97.412109 0)\"/>\n      <use xlink:href=\"#DejaVuSans-64\" transform=\"translate(158.935547 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(222.412109 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(250.195312 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(311.474609 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(374.853516 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(406.640625 0)\"/>\n      <use xlink:href=\"#DejaVuSans-76\" transform=\"translate(467.822266 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(527.001953 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(588.525391 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(629.638672 0)\"/>\n      <use xlink:href=\"#DejaVuSans-32\" transform=\"translate(661.425781 0)\"/>\n      <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(725.048828 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(788.671875 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(820.458984 0)\"/>\n      <use xlink:href=\"#DejaVuSans-75\" transform=\"translate(861.572266 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(924.951172 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(988.330078 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"line2d_55\">\n    <path d=\"M 60.255398 82.824519 \nL 90.960099 84.321779 \nL 114.18731 88.699293 \nL 127.774357 91.303473 \nL 137.41452 90.233252 \nL 144.892011 90.945162 \nL 151.001567 90.979035 \nL 156.167122 75.402301 \nL 158.922903 68.584186 \nL 160.64173 13.5 \nL 162.276678 69.892398 \nL 164.588614 81.217401 \nL 168.119222 92.253232 \nL 174.228777 104.447913 \nL 183.86894 117.474973 \nL 197.455987 127.175828 \nL 214.573642 133.998771 \nL 237.800852 139.5 \n\" clip-path=\"url(#p01848b40eb)\" style=\"fill: none; stroke: #1f77b4; stroke-width: 1.5; stroke-linecap: square\"/>\n   </g>\n   <g id=\"line2d_56\">\n    <path d=\"M 60.255398 106.499772 \nL 90.960099 88.900545 \nL 114.18731 73.179852 \nL 127.774357 70.078491 \nL 137.41452 68.33305 \nL 144.892011 66.347437 \nL 151.001567 63.785069 \nL 156.167122 57.227689 \nL 158.922903 53.118747 \nL 160.64173 25.396874 \nL 162.276678 51.661382 \nL 164.588614 57.840579 \nL 168.119222 65.91951 \nL 174.228777 72.978608 \nL 183.86894 80.197827 \nL 197.455987 87.358738 \nL 214.573642 94.223691 \nL 237.800852 102.352464 \n\" clip-path=\"url(#p01848b40eb)\" 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 157.834375 140.8 \nQ 159.834375 140.8 159.834375 138.8 \nL 159.834375 110.121875 \nQ 159.834375 108.121875 157.834375 108.121875 \nL 58.378125 108.121875 \nQ 56.378125 108.121875 56.378125 110.121875 \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_57\">\n     <path d=\"M 60.378125 116.220313 \nL 70.378125 116.220313 \nL 80.378125 116.220313 \n\" style=\"fill: none; stroke: #1f77b4; stroke-width: 1.5; stroke-linecap: square\"/>\n    </g>\n    <g id=\"text_8\">\n     <!-- test MSE -->\n     <g transform=\"translate(88.378125 119.720313) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-4d\" d=\"M 628 4666 \nL 1569 4666 \nL 2759 1491 \nL 3956 4666 \nL 4897 4666 \nL 4897 0 \nL 4281 0 \nL 4281 4097 \nL 3078 897 \nL 2444 897 \nL 1241 4097 \nL 1241 0 \nL 628 0 \nL 628 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-53\" d=\"M 3425 4513 \nL 3425 3897 \nQ 3066 4069 2747 4153 \nQ 2428 4238 2131 4238 \nQ 1616 4238 1336 4038 \nQ 1056 3838 1056 3469 \nQ 1056 3159 1242 3001 \nQ 1428 2844 1947 2747 \nL 2328 2669 \nQ 3034 2534 3370 2195 \nQ 3706 1856 3706 1288 \nQ 3706 609 3251 259 \nQ 2797 -91 1919 -91 \nQ 1588 -91 1214 -16 \nQ 841 59 441 206 \nL 441 856 \nQ 825 641 1194 531 \nQ 1563 422 1919 422 \nQ 2459 422 2753 634 \nQ 3047 847 3047 1241 \nQ 3047 1584 2836 1778 \nQ 2625 1972 2144 2069 \nL 1759 2144 \nQ 1053 2284 737 2584 \nQ 422 2884 422 3419 \nQ 422 4038 858 4394 \nQ 1294 4750 2059 4750 \nQ 2388 4750 2728 4690 \nQ 3069 4631 3425 4513 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-45\" d=\"M 628 4666 \nL 3578 4666 \nL 3578 4134 \nL 1259 4134 \nL 1259 2753 \nL 3481 2753 \nL 3481 2222 \nL 1259 2222 \nL 1259 531 \nL 3634 531 \nL 3634 0 \nL 628 0 \nL 628 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-74\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(39.208984 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(100.732422 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(152.832031 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(192.041016 0)\"/>\n      <use xlink:href=\"#DejaVuSans-4d\" transform=\"translate(223.828125 0)\"/>\n      <use xlink:href=\"#DejaVuSans-53\" transform=\"translate(310.107422 0)\"/>\n      <use xlink:href=\"#DejaVuSans-45\" transform=\"translate(373.583984 0)\"/>\n     </g>\n    </g>\n    <g id=\"line2d_58\">\n     <path d=\"M 60.378125 130.942188 \nL 70.378125 130.942188 \nL 80.378125 130.942188 \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_9\">\n     <!-- ||w|| of the fit -->\n     <g transform=\"translate(88.378125 134.442188) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-7c\" d=\"M 1344 4891 \nL 1344 -1509 \nL 813 -1509 \nL 813 4891 \nL 1344 4891 \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-68\" 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 4863 \nL 1159 4863 \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      </defs>\n      <use xlink:href=\"#DejaVuSans-7c\"/>\n      <use xlink:href=\"#DejaVuSans-7c\" transform=\"translate(33.691406 0)\"/>\n      <use xlink:href=\"#DejaVuSans-77\" transform=\"translate(67.382812 0)\"/>\n      <use xlink:href=\"#DejaVuSans-7c\" transform=\"translate(149.169922 0)\"/>\n      <use xlink:href=\"#DejaVuSans-7c\" transform=\"translate(182.861328 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(216.552734 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(248.339844 0)\"/>\n      <use xlink:href=\"#DejaVuSans-66\" transform=\"translate(309.521484 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(344.726562 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(376.513672 0)\"/>\n      <use xlink:href=\"#DejaVuSans-68\" transform=\"translate(415.722656 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(479.101562 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(540.625 0)\"/>\n      <use xlink:href=\"#DejaVuSans-66\" transform=\"translate(572.412109 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(607.617188 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(635.400391 0)\"/>\n     </g>\n    </g>\n   </g>\n  </g>\n </g>\n <defs>\n  <clipPath id=\"p01848b40eb\">\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-concentration-generalization-md-6 fw=all -->\n",
    "\n",
    "*The classical\n",
    "regime plays out first*: test error falls from $1.04$ at $p=2$ to its\n",
    "classical sweet spot of about $0.68$ around $p=15$, then creeps up as\n",
    "variance grows, the familiar U. *The interpolation threshold shows up in the\n",
    "train column*: at $p=40=n$ the training error drops from\n",
    "$5\\times10^{-3}$ to $10^{-28}$ (exact interpolation, up to floating\n",
    "point) and precisely there the test error erupts to $33.6$, fifty times its\n",
    "classical minimum, while $\\|\\mathbf w\\|$ jumps to $18.5$: the near-singular\n",
    "square system dividing noise by $\\sigma_{\\min}$, just as promised. *Then the\n",
    "second descent*: from $p=42$ onward the norm falls monotonically ($4.96$,\n",
    "$3.64$, $2.42$, $1.70$, $1.18$, down to $0.39$ at $p=400$; the nesting\n",
    "guarantees this) and the test error tracks it down through $0.65$ at\n",
    "$p=50$ and $0.18$ at $p=80$ to $0.060$ at $p=400$: *ten times better than the\n",
    "best underparameterized model*. Note also which curve did *not* move: train\n",
    "error is zero up to floating point everywhere past the threshold (the table\n",
    "prints $10^{-28}$), so no\n",
    "empirical-risk-based criterion can tell these models apart; the solution norm\n",
    "distinguishes them in this experiment. The Rademacher calculation motivates\n",
    "looking beyond parameter count, but its relevant product also includes feature\n",
    "norms and does not by itself predict this test curve. The best model in this\n",
    "entire experiment is the most overparameterized one, fitting noisy data\n",
    "*exactly*, with ten times more parameters than data points.\n",
    "\n",
    "### Benign Overfitting\n",
    "\n",
    "One puzzle remains inside the mechanism. The $p=400$ model interpolates its\n",
    "noisy labels (it reproduces every corrupted $y_i$ exactly), yet its test\n",
    "error is the best on the table. When does fitting noise *not* hurt? The\n",
    "minimum-norm solution splits across the spectrum of the feature matrix: the\n",
    "*signal* is captured along the few directions with large singular values,\n",
    "while interpolating the residual *noise* is distributed (because minimizing\n",
    "the norm spreads it) across the many directions with small singular values,\n",
    "where each contaminates predictions at new points only faintly. Overfitting is\n",
    "**benign** when the spectrum has this shape: a few strong directions to carry\n",
    "the signal, plus a large reservoir of weak directions that absorb and\n",
    "*average out* the noise, in effect performing implicit regularization without\n",
    "a regularizer. [@Bartlett.Long.Lugosi.Tsigler.2020] make this exact for\n",
    "linear regression, characterizing benignity via two effective ranks of the\n",
    "covariance, and [@Belkin.Hsu.Ma.ea.2019] frame the modern regime it\n",
    "explains; [@Bartlett.Montanari.Rakhlin.2021] survey the fast-growing\n",
    "theory. For deep networks the picture is instructive but not settled: features\n",
    "there are *learned*, reshaping the spectrum during training, and a theory that\n",
    "predicts a given network's test error from first principles remains open.\n",
    "\n",
    "## Summary\n",
    "\n",
    "* The *Chernoff method* (Markov's inequality applied to $e^{\\lambda X}$,\n",
    "  then optimized over $\\lambda$) converts a bound on the moment generating\n",
    "  function into an exponential tail bound; for sums of independent variables\n",
    "  the MGF factorizes, which is where the exponential-in-$n$ decay comes from.\n",
    "* *Hoeffding's lemma* bounds the MGF of a centered variable on $[a,b]$ by\n",
    "  $e^{\\lambda^2(b-a)^2/8}$ (proof: the second derivative of the log-MGF is a\n",
    "  tilted variance, at most $(b-a)^2/4$), and *Hoeffding's inequality* follows:\n",
    "  $P(|\\bar X-E\\bar X|\\ge t)\\le 2e^{-2nt^2/(b-a)^2}$, the finite-sample bound\n",
    "  behind the main book's test-set arithmetic, exponentially sharper than\n",
    "  Chebyshev's $1/n$. Inverted, it gives the finite-sample confidence interval\n",
    "  the equation.\n",
    "  *Sub-Gaussian* variables are those obeying such an MGF\n",
    "  bound; *Bernstein's inequality* refines the constant using the true\n",
    "  variance and covers the sub-exponential case (squares, norms).\n",
    "* In high dimension, concentration is geometry (*concentration of measure*):\n",
    "  $\\|\\mathbf x\\|/\\sqrt d$\n",
    "  concentrates at $1$ with failure probability $2e^{-d\\varepsilon^2/8}$, so a\n",
    "  Gaussian is a *thin shell*, random directions are *near-orthogonal*\n",
    "  ($\\cos\\approx 1/\\sqrt d$), pairwise distances concentrate (degrading\n",
    "  nearest-neighbor contrast). In a single wide random layer, related\n",
    "  concentration can make the variance calculation representative, but stability\n",
    "  across many nonlinear layers needs additional dependence and Jacobian control.\n",
    "* Hoeffding certifies one *pre-chosen* function; a learner chooses *after*\n",
    "  seeing data, so guarantees must hold *uniformly* over the class. For finite\n",
    "  classes the union bound gives deviation\n",
    "  $\\sqrt{\\log(2|\\mathcal F|/\\delta)/2n}$, valid for a pool of models fixed\n",
    "  before the data are drawn; genuinely adaptive test-set reuse voids the\n",
    "  union bound, and its guarantees degrade faster (adaptive data analysis).\n",
    "* *Rademacher complexity* (how well a class can correlate with random\n",
    "  signs) bounds uniform deviations:\n",
    "  $R(f)\\le\\hat R(f)+2\\mathfrak R_n(\\mathcal F)+\\sqrt{\\log(1/\\delta)/2n}$. For\n",
    "  the linear class $\\{\\|\\mathbf w\\|\\le B\\}$ on data with $\\|\\mathbf x\\|\\le r$\n",
    "  it computes to $Br/\\sqrt n$: parameter count is absent when the weight and\n",
    "  data radii are held fixed. A class rich enough to fit arbitrary random signs\n",
    "  has complexity near its maximum and yields a vacuous bound; the failure belongs to the crude class choice, and uniform\n",
    "  convergence survives as the language of guarantees.\n",
    "* *Double descent*: sweeping random features through the interpolation\n",
    "  threshold $p=n$, test error follows the classical U, spikes at $p=n$ (a\n",
    "  near-singular system divides noise by $\\sigma_{\\min}$), then descends again\n",
    "  while the minimum-norm interpolant shrinks with added nested features. This\n",
    "  norm trend is a mechanism and diagnostic; a formal capacity explanation must\n",
    "  also track feature norms and the data-dependent selection of the solution. Interpolating noise is *benign* when a few strong\n",
    "  spectral directions carry the signal and many weak ones absorb the noise.\n",
    "\n",
    "## Exercises\n",
    "\n",
    "1. Prove that a Rademacher variable is sub-Gaussian with variance proxy $1$:\n",
    "   show $\\cosh\\lambda\\le e^{\\lambda^2/2}$ by comparing the two Taylor series\n",
    "   term by term ($(2k)!\\ge 2^k k!$). Conclude via the Chernoff method that an\n",
    "   average of $n$ fair random signs satisfies\n",
    "   $P(|\\bar\\varepsilon|\\ge t)\\le 2e^{-nt^2/2}$.\n",
    "2. The proof of the equation assumed a common range $[a,b]$.\n",
    "   Redo it for independent $X_i\\in[a_i,b_i]$ to obtain\n",
    "   $P(|\\bar X-E\\bar X|\\ge t)\\le\n",
    "   2\\exp\\bigl(-2n^2t^2/\\sum_i(b_i-a_i)^2\\bigr)$, and check that it reduces to\n",
    "   the equation when the ranges agree. This weighted version is\n",
    "   the one the near-orthogonality argument used, with weights $u_i$.\n",
    "3. **McDiarmid's inequality** [@McDiarmid.1989] extends Hoeffding from\n",
    "   sums to arbitrary\n",
    "   functions with *bounded differences*: if changing the $i$-th argument of\n",
    "   $g(x_1,\\ldots,x_n)$ moves its value by at most $c_i$, then\n",
    "   $P(|g - E[g]|\\ge t)\\le 2\\exp\\bigl(-2t^2/\\sum_i c_i^2\\bigr)$. Take this\n",
    "   statement on faith (its proof needs martingales). (i) Recover Hoeffding's\n",
    "   inequality from it. (ii) The bootstrap of that section\n",
    "   computes a statistic of $n$ data points; argue that if that statistic has\n",
    "   bounded differences $c_i=c/n$, the bootstrap's *ideal* target (the\n",
    "   statistic's deviation from its mean) already concentrates at rate\n",
    "   $e^{-2nt^2/c^2}$, and check the median of a sample does *not* have small\n",
    "   bounded differences in general.\n",
    "4. Compute the Rademacher complexity of the $\\ell_1$-ball class\n",
    "   $\\mathcal F=\\{\\mathbf x\\mapsto\\langle\\mathbf w,\\mathbf x\\rangle:\n",
    "   \\|\\mathbf w\\|_1\\le B\\}$ on data with $\\|\\mathbf x_i\\|_\\infty\\le r$. The\n",
    "   supremum step now uses the duality between the $\\ell_1$ and $\\ell_\\infty$\n",
    "   norms, giving $\\frac Bn E\\|\\sum_i\\varepsilon_i\\mathbf x_i\\|_\\infty$; bound\n",
    "   the expected max of $d$ sub-Gaussian coordinates to conclude\n",
    "   $\\widehat{\\mathfrak R}_S\\le Br\\sqrt{2\\log(2d)/n}$. Why does dimension now\n",
    "   enter, and only logarithmically?\n",
    "5. Rerun the double-descent sweep with ridge regression,\n",
    "   $\\mathbf w_\\lambda=(\\boldsymbol\\Phi^\\top\\boldsymbol\\Phi+\n",
    "   \\lambda\\mathbf I)^{-1}\\boldsymbol\\Phi^\\top\\mathbf y$, for\n",
    "   $\\lambda\\in\\{10^{-8},10^{-4},10^{-2},1\\}$. Watch the interpolation peak\n",
    "   melt as $\\lambda$ grows, and explain why using\n",
    "   that section: the ridge term lifts\n",
    "   $\\sigma_{\\min}^2$ to $\\sigma_{\\min}^2+\\lambda$, capping the noise\n",
    "   amplification. Verify numerically that as $\\lambda\\to0$ the ridge solution\n",
    "   converges to the pseudoinverse (minimum-norm) solution.\n",
    "6. In the double-descent experiment, vary the label noise\n",
    "   ($\\textrm{noise}\\in\\{0,\\ 0.1,\\ 0.5,\\ 1.0\\}$) and measure the height and\n",
    "   location of the peak. Confirm that the peak stays at $p=n$ (its location\n",
    "   is a rank condition, independent of the labels) while its height grows\n",
    "   with the noise variance, and explain both observations with the\n",
    "   $\\sigma_{\\min}$ mechanism. What happens to the peak when\n",
    "   $\\textrm{noise}=0$, and why is it not entirely gone?\n",
    "7. Use the equation to find the smallest dimension $d$\n",
    "   at which the shell $(1\\pm 0.01)\\sqrt d$ is guaranteed to hold at least\n",
    "   $99\\%$ of a standard Gaussian's mass, then estimate the true smallest $d$\n",
    "   by simulation. How large is the gap, and which side of the story (rate or\n",
    "   constant) does it come from?\n",
    "8. An analyst fixes a pool of $m$ models *before* seeing the data, evaluates\n",
    "   all of them on one validation set of $n$ points\n",
    "   (losses in $[0,1]$), and reports the best score. Apply\n",
    "   the equation with $\\mathcal F$ the pre-registered pool to\n",
    "   bound how *optimistic* the reported score can be, and evaluate the bound\n",
    "   at $m=10$, $10^3$, and $10^6$ with $n=10{,}000$ and $\\delta=0.05$. At what\n",
    "   $m$ does the guaranteed accuracy degrade past $\\pm 0.02$? Compare with the\n",
    "   Bonferroni discussion of multiple testing in that section:\n",
    "   which bound is doing the same job, and where do the two analyses differ?\n",
    "   Finally, explain why none of this applies verbatim when each model is\n",
    "   chosen after seeing the previous models' scores\n",
    "   [@Dwork.Feldman.Hardt.ea.2015].\n",
    "\n",
    "[Discussions](https://d2l.discourse.group/t/concentration-and-generalization)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "name": "d2l-jax",
   "display_name": "d2l (JAX)",
   "language": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
