{
 "nbformat": 4,
 "nbformat_minor": 5,
 "metadata": {
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3",
   "language": "python"
  },
  "language_info": {
   "name": "python"
  },
  "colab": {
   "name": "learnrate.ipynb"
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "# learning rate \u2014 Python demo\n\nNumerical companion to the entry [learning rate](https://dictionaryofml.org/terms/learnrate.html) of the [Dictionary of Applied Machine Learning](https://dictionaryofml.org/): it recomputes what the entry states and prints one line per check.\n\nShows what the learning rate of a gradient step does to the HYPOTHESIS MAP and to the set of model parameters that a fixed number of gradient steps can reach. One gradient step of GD on the average squared error loss of a linear model moves the fitted line by an amount proportional to the learning rate; a learning rate above 2/L makes the loss grow; and T steps with learning rate eta stay inside a ball around the initial parameters whose radius grows with eta. Self-contained (numpy and matplotlib only), fixed seed.\n\nRequires NumPy and Matplotlib only, and uses fixed seeds, so the printed numbers reproduce exactly. Generated from [`pythondemos/learnrate.py`](https://dictionaryofml.org/terms/learnrate.py); CC BY 4.0."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "# Notebook shim: the script resolves output paths relative to __file__,\n# which a notebook kernel does not define; everything lands in the\n# working directory instead.\nimport os\n__file__ = os.path.join(os.getcwd(), \"learnrate.py\")\nos.makedirs(\"pythondemos\", exist_ok=True)"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "\"\"\"\nlearnrate.py \u2014 numerical companion to the glossary entry 'learning rate'.\n\nPurpose\n-------\nShows what the learning rate of a gradient step does to the HYPOTHESIS\nMAP and to the set of model parameters that a fixed number of gradient\nsteps can reach.  One gradient step of GD on the average squared error\nloss of a linear model moves the fitted line by an amount proportional\nto the learning rate; a learning rate above 2/L makes the loss grow; and\nT steps with learning rate eta stay inside a ball around the initial\nparameters whose radius grows with eta.  Self-contained (numpy and\nmatplotlib only), fixed seed.\n\nSetup\n-----\nTraining set: m = 4 consecutive days with feature x = morning minimum\ntemperature (degrees C) and label y = maximum daytime temperature\n(degrees C); synthetic values drawn around y = 6.7 + 0.76 x.  Hypothesis\nmap h(x) = w1 x + w2, i.e. a linear model with the feature vector (x, 1).\nObjective f(w) = average squared error loss on the training set, whose\nHessian is (2/m) X^T X with largest eigenvalue L.  Initial parameters\nw = (0.3, 2.0), a poor line below the data.\n\nBlocks\n------\n[B-data]  The training set, the initial hypothesis map and f at the\n          initial parameters; L is reported.\n[B-step]  One gradient step for three learning rates, 0.1/L, 1.5/L and\n          2.5/L.  The change of the prediction at any x is eta times the\n          product of the gradient with (x, 1), so the largest change of\n          the line over the plotted range is exactly 15 times larger for\n          1.5/L than for 0.1/L; the first two steps lower f, the third\n          (above the threshold 2/L) raises it.\n[B-reach] T = 10 gradient steps for the learning rates 0.1/L, 0.5/L and\n          1.5/L.  Every iterate stays within the distance\n          eta * sum_t ||grad f(w^(t))|| of the initial parameters, a\n          radius that grows with eta; with 0.1/L the ERM solution lies\n          outside that ball, with 1.5/L inside it.\n\nOutputs\n-------\nlearnrate_data.csv  : x, y of the 4 training days.\nlearnrate_lines.csv : x grid with h_before (initial line), h_small,\n                      h_large, h_toolarge (after one step with 0.1/L,\n                      1.5/L, 2.5/L).\nlearnrate_balls.csv : 91 points on each of the three circles of [B-reach]\n                      (columns xs,ys / xm,ym / xl,yl) in the (w1, w2)\n                      plane.\nlearnrate_reach.csv : one row per learning rate of [B-reach]: eta_over_L,\n                      radius, w1_T, w2_T, plus the initial parameters and\n                      the ERM solution as rows tagged in the first column.\nlearnrate.png       : matplotlib preview of the two figures (checking\n                      only).\n\"\"\"\n\nimport numpy as np\nimport matplotlib\n\nmatplotlib.use(\"Agg\")\nimport matplotlib.pyplot as plt\n\nfrom pathlib import Path\n\nOUT_DIR = Path(__file__).parent\n\nreport = []\n\n\ndef check(name, ok):\n    report.append((name, bool(ok)))\n    print(f\"  [{'ok' if ok else 'FAIL'}] {name}\")\n\n\nrng = np.random.default_rng(0)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-data]** The training set, the initial hypothesis map and f at the initial parameters; L is reported."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "m = 4\nx = np.array([2.1, 3.4, 4.0, 5.6])              # four consecutive days\ny = 6.7 + 0.76 * x + 0.6 * rng.standard_normal(m)\nX = np.c_[x, np.ones(m)]                        # feature vectors (x, 1)\n\n\ndef h(w, xs):\n    return w[0] * xs + w[1]\n\n\ndef f(w):\n    return float(np.mean((y - X @ w) ** 2))\n\n\ndef grad(w):\n    return -(2.0 / m) * X.T @ (y - X @ w)\n\n\nw0 = np.array([0.3, 2.0])\nH = (2.0 / m) * X.T @ X\nL = float(np.linalg.eigvalsh(H).max())\nw_erm = np.linalg.lstsq(X, y, rcond=None)[0]\ncheck(f\"[B-data]  m={m} days, f(w0)={f(w0):.2f}, L={L:.1f}, \"\n      f\"ERM solution w=({w_erm[0]:.2f}, {w_erm[1]:.2f})\",\n      f(w0) > 10.0 and L > 0)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-step]** One gradient step for three learning rates, 0.1/L, 1.5/L and 2.5/L. The change of the prediction at any x is eta times the product of the gradient with (x, 1), so the largest change of the line over the plotted range is exactly 15 times larger for 1.5/L than for 0.1/L; the first two steps lower f, the third (above the threshold 2/L) raises it."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "etas = {\"small\": 0.1 / L, \"large\": 1.5 / L, \"toolarge\": 2.5 / L}\ng = grad(w0)\nw_after = {k: w0 - e * g for k, e in etas.items()}\nxg = np.linspace(0.0, 8.0, 81)\nd = {k: np.abs(h(w_after[k], xg) - h(w0, xg)).max() for k in etas}\ncheck(f\"[B-step]  largest change of the line: {d['small']:.2f} (0.1/L) vs \"\n      f\"{d['large']:.2f} (1.5/L), ratio {d['large'] / d['small']:.1f}\",\n      abs(d[\"large\"] / d[\"small\"] - 15.0) < 1e-6)\ncheck(f\"[B-step]  f: {f(w0):.2f} -> {f(w_after['small']):.2f} (0.1/L), \"\n      f\"{f(w_after['large']):.2f} (1.5/L), {f(w_after['toolarge']):.2f} \"\n      f\"(2.5/L, above 2/L: f grows)\",\n      f(w_after[\"small\"]) < f(w0) and f(w_after[\"large\"]) < f(w0)\n      and f(w_after[\"toolarge\"]) > f(w0))"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-reach]** T = 10 gradient steps for the learning rates 0.1/L, 0.5/L and 1.5/L. Every iterate stays within the distance eta * sum_t ||grad f(w^(t))|| of the initial parameters, a radius that grows with eta; with 0.1/L the ERM solution lies outside that ball, with 1.5/L inside it."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "T = 10\nreach = {}\nfor tag, c in ((\"s\", 0.1), (\"m\", 0.5), (\"l\", 1.5)):\n    eta = c / L\n    w = w0.copy(); path = 0.0\n    for _ in range(T):\n        gt = grad(w); path += eta * np.linalg.norm(gt); w = w - eta * gt\n    reach[tag] = (c, path, w)\ndist_erm = float(np.linalg.norm(w_erm - w0))\ncheck(f\"[B-reach] T={T}: radius {reach['s'][1]:.2f} (0.1/L), \"\n      f\"{reach['m'][1]:.2f} (0.5/L), {reach['l'][1]:.2f} (1.5/L); \"\n      f\"||w_ERM - w0|| = {dist_erm:.2f}\",\n      all(np.linalg.norm(reach[t][2] - w0) <= reach[t][1] + 1e-9\n          for t in reach)\n      and reach[\"s\"][1] < dist_erm < reach[\"l\"][1])\n\n# ---------------------------------------------------------------- CSV\nwith open(OUT_DIR / \"learnrate_data.csv\", \"w\") as fh:\n    fh.write(\"x,y\\n\")\n    for a, b in zip(x, y):\n        fh.write(f\"{a:.3f},{b:.3f}\\n\")\nwith open(OUT_DIR / \"learnrate_lines.csv\", \"w\") as fh:\n    fh.write(\"x,h_before,h_small,h_large,h_toolarge\\n\")\n    for i, a in enumerate(xg):\n        fh.write(f\"{a:.3f},{h(w0, a):.3f},{h(w_after['small'], a):.3f},\"\n                 f\"{h(w_after['large'], a):.3f},{h(w_after['toolarge'], a):.3f}\\n\")\nang = np.linspace(0.0, 2.0 * np.pi, 91)\nwith open(OUT_DIR / \"learnrate_balls.csv\", \"w\") as fh:\n    fh.write(\"xs,ys,xm,ym,xl,yl\\n\")\n    for a in ang:\n        row = []\n        for t in (\"s\", \"m\", \"l\"):\n            r = reach[t][1]\n            row += [f\"{w0[0] + r * np.cos(a):.4f}\", f\"{w0[1] + r * np.sin(a):.4f}\"]\n        fh.write(\",\".join(row) + \"\\n\")\nwith open(OUT_DIR / \"learnrate_reach.csv\", \"w\") as fh:\n    fh.write(\"tag,eta_over_L,radius,w1,w2\\n\")\n    fh.write(f\"init,0,0,{w0[0]:.4f},{w0[1]:.4f}\\n\")\n    fh.write(f\"erm,0,0,{w_erm[0]:.4f},{w_erm[1]:.4f}\\n\")\n    for t in (\"s\", \"m\", \"l\"):\n        c, r, w = reach[t]\n        fh.write(f\"{t},{c},{r:.4f},{w[0]:.4f},{w[1]:.4f}\\n\")\n\n# -------------------------------------------------------------- preview\nfig, (ax, ax2) = plt.subplots(1, 2, figsize=(9.6, 4.0))\nax.plot(x, y, \"ko\", ms=5, label=\"training set (4 days)\")\nax.plot(xg, h(w0, xg), \"k-\", lw=1.4, label=\"before the step\")\nax.plot(xg, h(w_after[\"small\"], xg), \"k--\", lw=1.2, label=\"after, learning rate 0.1/L\")\nax.plot(xg, h(w_after[\"large\"], xg), \"k:\", lw=1.6, label=\"after, learning rate 1.5/L\")\nax.plot(xg, h(w_after[\"toolarge\"], xg), \"-.\", color=\"0.5\", lw=1.4,\n        label=\"after, learning rate 2.5/L (loss grows)\")\nax.set_xlabel(\"morning minimum temperature $x$\")\nax.set_ylabel(\"maximum daytime temperature $y$\")\nax.set_title(\"one gradient step, three learning rates\")\nax.legend(frameon=False, fontsize=7)\nfor t, ls in ((\"s\", \"-\"), (\"m\", \"--\"), (\"l\", \":\")):\n    c, r, w = reach[t]\n    ax2.plot(w0[0] + r * np.cos(ang), w0[1] + r * np.sin(ang), \"k\", ls=ls, lw=1.1,\n             label=f\"reachable in {T} steps, learning rate {c}/L\")\nax2.plot([w0[0]], [w0[1]], \"ks\", ms=5, label=\"initial parameters\")\nax2.plot([w_erm[0]], [w_erm[1]], \"k*\", ms=9, label=\"ERM solution\")\nax2.set_xlabel(\"slope $w_1$\")\nax2.set_ylabel(\"intercept $w_2$\")\nax2.set_title(\"parameters reachable in 10 steps\")\nax2.legend(frameon=False, fontsize=7)\nfig.tight_layout()\nfig.savefig(OUT_DIR / \"learnrate.png\", dpi=110)\n\nn_ok = sum(ok for _, ok in report)\nprint(f\"\\n{n_ok}/{len(report)} checks pass\")\nprint(f\"wrote {OUT_DIR / 'learnrate_data.csv'}, {OUT_DIR / 'learnrate_lines.csv'}, \"\n      f\"{OUT_DIR / 'learnrate_balls.csv'}, {OUT_DIR / 'learnrate_reach.csv'}, \"\n      f\"{OUT_DIR / 'learnrate.png'}\")\nif n_ok != len(report):\n    raise SystemExit(1)"
  }
 ]
}