"""Bishop and Bishop (2024), Chapter 7: Gradient Descent.

Reproduces the figures of Chapter 7 of C. M. Bishop and H. Bishop, Deep Learning: Foundations and
Concepts (Springer, 2024), pp. 209-232, written from scratch with numpy, PyTorch (autograd only, for
the small MNIST networks) and matplotlib, and supplies the reference numbers of the three browser
demonstrations. Every algorithm is a short function meant to be read next to the lecture notes
(ch07-gradient-descent.html):

* Section 7.1, error surfaces: four two-dimensional error functions with analytic gradients
  (SURFACES: an elongated quadratic 'valley' with condition number kappa and rotation angle theta,
  a curved 'banana' valley, a surface with a local and a global minimum 'twomin', and a 'saddle').
* Sections 7.2-7.3, the optimisers, all written as explicit updates: gradient descent (7.16),
  momentum (7.31), Nesterov momentum (7.34), AdaGrad (7.39)-(7.40), RMSProp (7.41)-(7.42) and
  Adam (7.43)-(7.47), with the learning-rate schedules (7.36)-(7.38) (opt_step, optimise_2d).
  The same update functions act on numpy arrays and on lists of torch tensors (train_mlp).
* Section 7.3, convergence on a quadratic: gd_factor, heavy_ball_roots, nesterov_roots,
  spectral_radius, optimal_gd, optimal_heavy_ball and quad_eigen_path (the eigen-coordinate
  iteration (7.27)-(7.29) and its two-step momentum versions).
* Section 7.2.4, mini-batches: softmax-regression per-example gradients and the exact variance of
  a mini-batch mean drawn without replacement (minibatch_variance).
* Section 7.2.5, initialisation: depth_stats propagates a batch forwards and a random output
  gradient backwards through a deep fully connected network with weights N(0, (g^2)/M), with
  optional batch or layer normalisation (7.52)-(7.55), (7.58)-(7.60), and records the root mean
  square of the pre-activations, the backpropagated errors and the weight gradients per layer.
* Section 7.4, normalisation: batchnorm_forward/backward and layernorm_forward/backward give the
  normalisation layers and their gradients in closed form (checked against autograd).
* JSRandom: the seeded generator DK.rng of the browser demos (mulberry32 uniforms and Box-Muller
  normals). optimise_2d, quad_eigen_path and depth_stats(..., js=True) use only that generator and
  plain floating-point arithmetic, so optimizer-paths-demo.html, step-size-demo.html and
  initialization-depth-demo.html reproduce them number for number.

Figures reproduced: 7.1, 7.2, 7.3, 7.4, 7.5, 7.6, 7.7 and 7.8. All eight are schematic in the book;
here each is computed from an explicit function, data set or simulation (7.1: the surface 'twomin';
7.2: a quadratic with given Hessian; 7.3 and 7.6: gradient descent without and with momentum on an
elongated quadratic; 7.4 and 7.5: one-dimensional runs on low- and high-curvature quadratics; 7.7: a
simulated two-variable data set; 7.8: the statistics of an actual mini-batch of pre-activations).
No figure of the chapter is skipped: the chapter has no photographs or reprinted images.

Supplementary figures (our own, numbered 7.S1-7.S6; they illustrate the gaps filled in the notes):
7.S1 activation and gradient statistics through depth for several initialisation scales;
7.S2 contraction factors versus learning rate and iterations versus condition number;
7.S3 variance of the mini-batch gradient versus batch size, and SGD versus batch gradient descent;
7.S4 the optimisers on a small MNIST network; 7.S5 training a deep network with and without batch
and layer normalisation; 7.S6 bias correction of an exponentially weighted moving average.

Run `python3 ch07_gradient_descent.py --list`, `python3 ch07_gradient_descent.py` (all figures,
about two minutes on one CPU thread) or `python3 ch07_gradient_descent.py --fig 7.3 7.S1`.
Files go to ../img/ch07/; slow MNIST results are cached in cache/.
"""
import math
import os

for _v in ("OPENBLAS_NUM_THREADS", "MKL_NUM_THREADS", "OMP_NUM_THREADS"):
    os.environ.setdefault(_v, "1")

import numpy as np  # noqa: E402
import matplotlib.pyplot as plt  # noqa: E402
from matplotlib.patches import FancyArrowPatch  # noqa: E402

import common  # noqa: E402
from common import savefig, run, panel_label  # noqa: E402

HERE = os.path.dirname(os.path.abspath(__file__))
CACHE_DIR = os.path.join(HERE, "cache")
CH = 7
M32 = 0xFFFFFFFF
DELTA = 1e-8          # the stabiliser delta of (7.40), (7.42), (7.47)


# =========================================================================== the demos' generator
def _imul(a, b):
    return (a * b) & M32


class JSRandom:
    """The seeded random numbers of the browser demos (DK.rng in courses/demo-kit.js).

    Uniforms come from the mulberry32 generator and normals from the Box-Muller transform, the
    second normal of each pair being cached, exactly as in JavaScript.
    """

    def __init__(self, seed):
        self.a = int(seed) & M32
        self.spare = None

    def u(self):
        a = (self.a + 0x6D2B79F5) & M32
        self.a = a
        t = _imul(a ^ (a >> 15), 1 | a)
        t = ((t + _imul(t ^ (t >> 7), 61 | t)) & M32) ^ t
        return ((t ^ (t >> 14)) & M32) / 4294967296.0

    def _pos(self):
        x = 0.0
        while x == 0.0:
            x = self.u()
        return x

    def norm(self):
        if self.spare is not None:
            s, self.spare = self.spare, None
            return s
        r = math.sqrt(-2.0 * math.log(self._pos()))
        th = 2.0 * math.pi * self.u()
        self.spare = r * math.sin(th)
        return r * math.cos(th)

    def normals(self, n):
        return np.array([self.norm() for _ in range(int(n))])


# =========================================================================== Section 7.1: surfaces
def _valley(w, kappa=25.0, theta=0.0):
    """E = (lam_min u^2 + lam_max v^2)/2 with u, v the coordinates along the eigenvectors
    u1 = (cos t, sin t) (eigenvalue lam_min = 1/kappa) and u2 = (-sin t, cos t) (lam_max = 1)."""
    t = theta * math.pi / 180.0
    c, s = math.cos(t), math.sin(t)
    lmin, lmax = 1.0 / kappa, 1.0
    u = c * w[0] + s * w[1]
    v = -s * w[0] + c * w[1]
    E = 0.5 * (lmin * u * u + lmax * v * v)
    g = np.array([lmin * u * c - lmax * v * s, lmin * u * s + lmax * v * c])
    return E, g


def _banana(w, **kw):
    """A curved valley (a scaled Rosenbrock function) with its minimum E = 0 at (1, 1)."""
    x, y = w[0], w[1]
    E = (1 - x) ** 2 + 5 * (y - x * x) ** 2
    g = np.array([-2 * (1 - x) - 20 * x * (y - x * x), 10 * (y - x * x)])
    return E, g


def _twomin(w, **kw):
    """(x^2 - 1)^2 + 0.3 x + 1.5 (y - 0.4 x)^2: a global minimum near (-1.04, -0.41), a local one
    near (0.96, 0.38) and a saddle point near (0.075, 0.03) between them."""
    x, y = w[0], w[1]
    d = y - 0.4 * x
    E = (x * x - 1) ** 2 + 0.3 * x + 1.5 * d * d
    g = np.array([4 * x * (x * x - 1) + 0.3 - 1.2 * d, 3 * d])
    return E, g


def _saddle(w, **kw):
    """x^2/2 - y^2/2 + y^4/4: a saddle point at the origin and two minima (0, +-1) with E = -1/4."""
    x, y = w[0], w[1]
    E = 0.5 * x * x - 0.5 * y * y + 0.25 * y ** 4
    g = np.array([x, -y + y ** 3])
    return E, g


SURFACES = {"valley": _valley, "banana": _banana, "twomin": _twomin, "saddle": _saddle}


def twomin_minima():
    """The three stationary points of 'twomin' on the line y = 0.4 x (roots of 4x^3 - 4x + 0.3)."""
    xs = np.sort(np.roots([4.0, 0.0, -4.0, 0.3]).real)
    return [(x, 0.4 * x) for x in xs]


def surface_min(name, kappa=25.0, theta=0.0):
    """The global minimum value of each surface (used to plot E - E_min on a log scale)."""
    if name == "twomin":
        return min(_twomin(np.array(p))[0] for p in twomin_minima())
    return {"valley": 0.0, "banana": 0.0, "saddle": -0.25}[name]


# =========================================================================== Sections 7.2-7.3: optimisers
def schedule(kind, eta0, tau):
    """Learning rate at step tau (0, 1, 2, ...): (7.36) linear to eta0/20 over K = 200 steps, then
    constant; (7.37) power law with s = 20, c = 1 written with a negative exponent, eta0 (1 + tau/s)^(-c);
    (7.38) exponential eta0 c^(tau/s) with c = 0.5, s = 50 (the rate halves every 50 steps)."""
    if kind == "linear":
        K, etaK = 200.0, eta0 / 20.0
        return (1 - tau / K) * eta0 + (tau / K) * etaK if tau < K else etaK
    if kind == "power":
        return eta0 * (1 + tau / 20.0) ** (-1.0)
    if kind == "exponential":
        return eta0 * 0.5 ** (tau / 50.0)
    return eta0


def new_state(w):
    """Optimiser state: v (momentum), s and r (first and second moments), t (Adam's step count)."""
    z = np.zeros_like(w)
    return {"v": z.copy(), "s": z.copy(), "r": z.copy(), "t": 0}


def opt_update(method, w, g, st, eta, mu=0.9, b1=0.9, b2=0.999):
    """One update of w given the gradient g (already evaluated at the right point; for Nesterov
    momentum that is the look-ahead point w + mu v). Works elementwise on numpy arrays or tensors.
    Returns the new w; the state st is updated in place."""
    if method == "gd":                              # (7.16)
        return w - eta * g
    if method in ("momentum", "nesterov"):         # (7.31) and (7.34): v = -eta g + mu v, w = w + v
        st["v"] = -eta * g + mu * st["v"]
        return w + st["v"]
    if method == "adagrad":                         # (7.39)-(7.40)
        st["r"] = st["r"] + g * g
        return w - eta * g / (st["r"] ** 0.5 + DELTA)
    if method == "rmsprop":                         # (7.41)-(7.42), beta = b2
        st["r"] = b2 * st["r"] + (1 - b2) * g * g
        return w - eta * g / (st["r"] ** 0.5 + DELTA)
    if method == "adam":                            # (7.43)-(7.47), with the sign of Algorithm 7.4 corrected
        st["t"] += 1
        st["s"] = b1 * st["s"] + (1 - b1) * g
        st["r"] = b2 * st["r"] + (1 - b2) * g * g
        sh = st["s"] / (1 - b1 ** st["t"])
        rh = st["r"] / (1 - b2 ** st["t"])
        return w - eta * sh / (rh ** 0.5 + DELTA)
    raise ValueError(method)


METHODS = ("gd", "momentum", "nesterov", "adagrad", "rmsprop", "adam")


def optimise_2d(surface, method, w0, steps, eta, mu=0.9, b1=0.9, b2=0.999, noise=0.0, seed=1,
                sched="constant", kappa=25.0, theta=0.0):
    """Run an optimiser on a 2-D surface: returns the path (steps + 1, 2) and the errors E(w).

    noise > 0 adds sigma * N(0, 1) to each gradient component (x first, then y), drawn from
    JSRandom(seed): a stand-in for mini-batch noise. Identical to the page optimizer-paths-demo.html.
    """
    f = SURFACES[surface]
    rng = JSRandom(seed)
    w = np.array(w0, dtype=float)
    st = new_state(w)
    path, errs = [w.copy()], [f(w, kappa=kappa, theta=theta)[0]]
    for tau in range(steps):
        eta_t = schedule(sched, eta, tau)
        at = w + mu * st["v"] if method == "nesterov" else w
        g = f(at, kappa=kappa, theta=theta)[1]
        if noise > 0:
            g = np.array([g[0] + noise * rng.norm(), g[1] + noise * rng.norm()])
        w = opt_update(method, w, g, st, eta_t, mu, b1, b2)
        if not np.all(np.isfinite(w)) or np.abs(w).max() > 1e6:
            break
        path.append(w.copy())
        errs.append(f(w, kappa=kappa, theta=theta)[0])
    return np.array(path), np.array(errs)


# =========================================================================== Section 7.3: quadratic theory
def gd_factor(eta, lam):
    """Per-step factor 1 - eta lambda of the eigen-coordinate alpha_i under gradient descent (7.27)."""
    return 1.0 - eta * np.asarray(lam, dtype=float)


def heavy_ball_roots(eta, mu, lam):
    """Roots of r^2 - (1 + mu - eta lam) r + mu = 0: the two modes of momentum (7.31) on lambda."""
    T = 1.0 + mu - eta * lam
    return np.roots([1.0, -T, mu])


def nesterov_roots(eta, mu, lam):
    """Roots of r^2 - (1 + mu)(1 - eta lam) r + mu (1 - eta lam) = 0 (Nesterov momentum (7.34))."""
    q = 1.0 - eta * lam
    return np.roots([1.0, -(1.0 + mu) * q, mu * q])


def spectral_radius(method, eta, mu, lams):
    """Largest |root| over the eigenvalues lams: the asymptotic contraction per step."""
    out = 0.0
    for lam in np.atleast_1d(lams):
        if method == "gd":
            r = abs(1.0 - eta * lam)
        elif method == "momentum":
            r = np.abs(heavy_ball_roots(eta, mu, lam)).max()
        else:
            r = np.abs(nesterov_roots(eta, mu, lam)).max()
        out = max(out, r)
    return out


def optimal_gd(lmin, lmax):
    """eta* = 2/(lmin + lmax) and the rate (kappa - 1)/(kappa + 1)."""
    k = lmax / lmin
    return 2.0 / (lmin + lmax), (k - 1.0) / (k + 1.0)


def optimal_heavy_ball(lmin, lmax):
    """Polyak's parameters: eta* = 4/(sqrt(lmax) + sqrt(lmin))^2, mu* = ((sqrt k - 1)/(sqrt k + 1))^2,
    with rate sqrt(mu*) = (sqrt k - 1)/(sqrt k + 1)."""
    sk = math.sqrt(lmax / lmin)
    rate = (sk - 1.0) / (sk + 1.0)
    return 4.0 / (math.sqrt(lmax) + math.sqrt(lmin)) ** 2, rate ** 2, rate


def quad_eigen_path(lams, alpha0, steps, method, eta, mu=0.0):
    """Gradient descent, momentum or Nesterov on E = sum_i lam_i alpha_i^2 / 2 in eigen-coordinates.
    Returns alpha (steps + 1, n). Identical to step-size-demo.html."""
    lams = np.asarray(lams, dtype=float)
    a = np.array(alpha0, dtype=float)
    v = np.zeros_like(a)
    out = [a.copy()]
    for _ in range(steps):
        if method == "gd":
            a = a - eta * lams * a
        elif method == "momentum":
            v = -eta * lams * a + mu * v
            a = a + v
        else:
            v = -eta * lams * (a + mu * v) + mu * v
            a = a + v
        out.append(a.copy())
    return np.array(out)


def iterations_to(tol, rate):
    """Steps needed for rate^T < tol."""
    return math.log(tol) / math.log(rate) if 0 < rate < 1 else float("inf")


# =========================================================================== Section 7.2.4: mini-batches
def softmax_grads(W, X, T):
    """Per-example gradients of the softmax cross-entropy E_n = -sum_k t_nk ln y_nk for a linear
    model a = W x (x includes a constant 1): grad_n = (y_n - t_n) x_n^T, returned as (N, K*D)."""
    A = X @ W.T
    A -= A.max(1, keepdims=True)
    Y = np.exp(A)
    Y /= Y.sum(1, keepdims=True)
    return ((Y - T)[:, :, None] * X[:, None, :]).reshape(len(X), -1)


def softmax_loss(W, X, T):
    A = X @ W.T
    m = A.max(1, keepdims=True)
    lse = (m[:, 0] + np.log(np.exp(A - m).sum(1)))
    return float(np.mean(lse - (A * T).sum(1)))


def minibatch_variance(G, B):
    """Exact E||g_B - g||^2 for the mean of B per-example gradients drawn without replacement from
    the N rows of G: (sigma^2 / B) (N - B)/(N - 1), sigma^2 = (1/N) sum_n ||g_n - g||^2."""
    N = len(G)
    s2 = ((G - G.mean(0)) ** 2).sum(1).mean()
    return s2 / B * (N - B) / (N - 1), s2


def mnist_softmax_data(N=2000, seed=0):
    X, y = common.mnist(train=True)
    rng = np.random.default_rng(seed)
    idx = rng.choice(len(X), N, replace=False)
    Xb = np.hstack([X[idx], np.ones((N, 1))])
    return Xb, np.eye(10)[y[idx]]


# =========================================================================== Section 7.4: normalisation
def batchnorm_forward(A, delta=1e-5, axis=0):
    """(7.52)-(7.54): normalise each column (axis=0, batch norm over the mini-batch) or each row
    (axis=1, layer norm (7.58)-(7.60) over the units). Returns a_hat and the cache."""
    mu = A.mean(axis, keepdims=True)
    var = ((A - mu) ** 2).mean(axis, keepdims=True)
    sd = np.sqrt(var + delta)
    Ah = (A - mu) / sd
    return Ah, (Ah, sd)


def batchnorm_backward(G, cache, axis=0):
    """Gradient through (7.54): dE/da = (1/sd) [g - mean(g) - a_hat mean(g a_hat)], the means over the
    normalised axis (K items for batch norm, M units for layer norm)."""
    Ah, sd = cache
    return (G - G.mean(axis, keepdims=True) - Ah * (G * Ah).mean(axis, keepdims=True)) / sd


def layernorm_forward(A, delta=1e-5):
    return batchnorm_forward(A, delta, axis=1)


def layernorm_backward(G, cache):
    return batchnorm_backward(G, cache, axis=1)


# =========================================================================== Section 7.2.5: initialisation
def _act(name, a):
    if name == "relu":
        return np.maximum(a, 0.0), (a > 0).astype(float)
    if name == "tanh":
        t = np.tanh(a)
        return t, 1.0 - t * t
    return a, np.ones_like(a)


def _matmul_rowwise(Z, W):
    """a[n, i] = sum_j W[i, j] z[n, j], summing j in increasing order as the JavaScript loops do."""
    N, M = Z.shape
    out = np.zeros((N, W.shape[0]))
    for j in range(M):
        out += Z[:, j:j + 1] * W[:, j][None, :]
    return out


def depth_stats(L=10, M=64, B=100, act="relu", gain=math.sqrt(2.0), norm="none", seed=1, js=False):
    """Push a batch of B standard-normal inputs (dimension M) through L layers of M units,
    a^(l) = W^(l) z^(l-1) (7.19), weights N(0, eps^2) with eps = gain / sqrt(M) (He: gain sqrt 2),
    optional normalisation of a^(l) before the activation (7.54) (gamma = 1, beta = 0), then
    backpropagate a random output gradient dE/dz^(L) ~ N(0, 1).

    Returns per-layer root mean squares of a^(l), z^(l), delta^(l) = dE/da^(l) and dE/dW^(l)/B, and
    the fraction of active ReLU units. With js=True every normal number comes from JSRandom(seed) in
    the order X, W^(1), ..., W^(L), G (row-major) and sums are taken in the browser's order: this is
    initialization-depth-demo.html.
    """
    eps = gain / math.sqrt(M)
    if js:
        r = JSRandom(seed)
        X = r.normals(B * M).reshape(B, M)
        Ws = [eps * r.normals(M * M).reshape(M, M) for _ in range(L)]
        G = r.normals(B * M).reshape(B, M)
        mm = _matmul_rowwise
    else:
        r = np.random.default_rng(seed)
        X = r.standard_normal((B, M))
        Ws = [eps * r.standard_normal((M, M)) for _ in range(L)]
        G = r.standard_normal((B, M))
        mm = lambda Z, W: Z @ W.T  # noqa: E731
    Z, caches = X, []
    rms = lambda x: float(np.sqrt(np.mean(x * x)))  # noqa: E731
    out = {"a": [], "z": [], "active": [], "delta": [], "gradW": []}
    for W in Ws:
        A = mm(Z, W)
        if norm == "batch":
            P, c = batchnorm_forward(A, axis=0)
        elif norm == "layer":
            P, c = batchnorm_forward(A, axis=1)
        else:
            P, c = A, None
        Zn, dh = _act(act, P)
        caches.append((Z, c, dh))
        out["a"].append(rms(A))
        out["z"].append(rms(Zn))
        out["active"].append(float((P > 0).mean()))
        Z = Zn
    gz = G
    deltas, gws = [], []
    for l in range(L - 1, -1, -1):
        Zprev, c, dh = caches[l]
        gp = gz * dh
        ga = gp if c is None else batchnorm_backward(gp, c, axis=0 if norm == "batch" else 1)
        deltas.append(rms(ga))
        gws.append(rms(ga.T @ Zprev / B))
        gz = ga @ Ws[l] if not js else _matmul_rowwise(ga, Ws[l].T)
    out["delta"] = deltas[::-1]
    out["gradW"] = gws[::-1]
    return {k: np.array(v) for k, v in out.items()}


def relu_second_moment_theory(L, gain):
    """Predicted E[(a^(l))^2] for ReLU without normalisation: gain^2 (gain^2/2)^(l-1), l = 1..L."""
    return np.array([gain ** 2 * (gain ** 2 / 2.0) ** (l - 1) for l in range(1, L + 1)])


# =========================================================================== small MNIST networks (torch)
def _mnist_subset(n=5000):
    X, y = common.mnist(train=True)
    return X[:n].astype(np.float32), y[:n]


def train_mlp(hidden, method, eta, steps, B=50, mu=0.9, b1=0.9, b2=0.999, norm="none", gain=math.sqrt(2.0),
              seed=0, n=5000, eval_every=10):
    """Train a ReLU network 784-hidden-10 with softmax cross-entropy on the first n MNIST training
    images, using our optimiser updates (opt_update) on the parameters; torch only computes gradients.
    norm in {'none', 'batch', 'layer'} inserts (7.52)-(7.55) before each ReLU with learnable gamma, beta.
    Returns the steps and the full-training-set loss every eval_every steps (nan once it diverges)."""
    torch = common.torch_setup(seed, threads=1)
    X, y = _mnist_subset(n)
    Xt, yt = torch.tensor(X), torch.tensor(y)
    sizes = [784] + list(hidden) + [10]
    params = []
    g = torch.Generator().manual_seed(seed)
    for i in range(len(sizes) - 1):
        fan_in = sizes[i]
        W = (torch.randn(sizes[i + 1], fan_in, generator=g) * (gain / math.sqrt(fan_in))).requires_grad_()
        b = torch.zeros(sizes[i + 1], requires_grad=True)
        params += [W, b]
        if norm != "none" and i < len(sizes) - 2:
            params += [torch.ones(sizes[i + 1], requires_grad=True), torch.zeros(sizes[i + 1], requires_grad=True)]

    def forward(Xb):
        h, k = Xb, 0
        for i in range(len(sizes) - 1):
            W, b = params[k], params[k + 1]
            k += 2
            a = h @ W.T + b
            if i < len(sizes) - 2:
                if norm != "none":
                    gam, bet = params[k], params[k + 1]
                    k += 2
                    ax = 0 if norm == "batch" else 1
                    mu_ = a.mean(ax, keepdim=True)
                    var = ((a - mu_) ** 2).mean(ax, keepdim=True)
                    a = gam * (a - mu_) / torch.sqrt(var + 1e-5) + bet
                h = torch.relu(a)
            else:
                h = a
        return h

    def full_loss():
        with torch.no_grad():
            if norm == "batch":       # evaluate in mini-batches of B, as the network is trained
                tot = 0.0
                for i in range(0, n, 500):
                    tot += float(torch.nn.functional.cross_entropy(forward(Xt[i:i + 500]), yt[i:i + 500], reduction="sum"))
                return tot / n
            return float(torch.nn.functional.cross_entropy(forward(Xt), yt))

    states = [{"v": torch.zeros_like(p), "s": torch.zeros_like(p), "r": torch.zeros_like(p), "t": 0} for p in params]
    order = np.random.default_rng(seed).permutation(n)
    pos, hist_s, hist_l = 0, [0], [full_loss()]
    for step in range(1, steps + 1):
        if pos + B > n:
            order = np.random.default_rng(seed + step).permutation(n)
            pos = 0
        idx = torch.tensor(order[pos:pos + B])
        pos += B
        if method == "nesterov":                    # gradient at the look-ahead point w + mu v
            with torch.no_grad():
                for p, s in zip(params, states):
                    p += mu * s["v"]
        loss = torch.nn.functional.cross_entropy(forward(Xt[idx]), yt[idx])
        grads = torch.autograd.grad(loss, params)
        with torch.no_grad():
            for p, gr, s in zip(params, grads, states):
                if method == "nesterov":
                    p -= mu * s["v"]
                p.copy_(opt_update(method, p, gr, s, eta, mu, b1, b2))
        if step % eval_every == 0:
            L_ = full_loss()
            hist_s.append(step)
            hist_l.append(L_ if math.isfinite(L_) and L_ < 50 else float("nan"))
            if not math.isfinite(hist_l[-1]):
                break
    return np.array(hist_s), np.array(hist_l)


def _cached(name, fn):
    os.makedirs(CACHE_DIR, exist_ok=True)
    path = os.path.join(CACHE_DIR, name + ".npz")
    if os.path.exists(path):
        d = np.load(path, allow_pickle=True)
        return d["res"].item()
    res = fn()
    np.savez(path, res=np.array(res, dtype=object))
    return res


# =========================================================================== figures
def _contours(ax, f, xlim, ylim, levels, n=300, **kw):
    xs = np.linspace(*xlim, n)
    ys = np.linspace(*ylim, n)
    Xg, Yg = np.meshgrid(xs, ys)
    Z = np.vectorize(lambda a, b: f(np.array([a, b]))[0])(Xg, Yg)
    ax.contour(Xg, Yg, Z, levels=levels, **kw)
    return Xg, Yg, Z


def fig_7_1(out_dir=None):
    """Figure 7.1: an error surface over a two-dimensional weight space, with a local minimum, the global minimum and a gradient."""
    from mpl_toolkits.mplot3d import Axes3D  # noqa: F401
    fig = plt.figure(figsize=(5.4, 4.3))
    ax = fig.add_subplot(111, projection="3d")
    xs = np.linspace(-1.5, 1.4, 90)
    ys = np.linspace(-1.0, 1.0, 70)
    Xg, Yg = np.meshgrid(xs, ys)
    Z = np.vectorize(lambda a, b: _twomin(np.array([a, b]))[0])(Xg, Yg)
    ax.plot_surface(Xg, Yg, Z, cmap="Reds", alpha=0.5, linewidth=0, antialiased=True, rstride=2, cstride=2)
    ax.contour(Xg, Yg, Z, levels=12, zdir="z", offset=-1.0, cmap="Greys", linewidths=0.5)
    pts = twomin_minima()
    wB, wA = pts[0], pts[2]           # global (left) and local (right) minima
    wC = (0.5, -0.7)
    for (p, lab, col) in ((wA, r"$\mathbf{w}_A$", common.BLUE), (wB, r"$\mathbf{w}_B$", common.BLUE), (wC, r"$\mathbf{w}_C$", common.BLUE)):
        e = _twomin(np.array(p))[0]
        ax.plot([p[0], p[0]], [p[1], p[1]], [-1.0, e], color=col, lw=1.4)
        ax.scatter([p[0]], [p[1]], [-1.0], color="k", s=10)
        ax.text(p[0], p[1] - 0.25, -1.25, lab, fontsize=10)
    g = _twomin(np.array(wC))[1]
    g = 0.5 * g / np.linalg.norm(g)
    ax.quiver(wC[0], wC[1], -1.0, g[0], g[1], 0.0, color=common.GREEN, lw=2, arrow_length_ratio=0.3)
    ax.text(wC[0] + g[0] + 0.1, wC[1] + g[1] - 0.1, -1.0, r"$\nabla E$", color=common.GREEN, fontsize=10)
    ax.set_xlabel(r"$w_1$", labelpad=-6)
    ax.set_ylabel(r"$w_2$", labelpad=-6)
    ax.set_zlabel(r"$E(\mathbf{w})$", labelpad=-6)
    ax.set_xticklabels([])
    ax.set_yticklabels([])
    ax.set_zticklabels([])
    ax.set_zlim(-1.0, float(Z.max()))
    ax.view_init(elev=28, azim=-70)
    return savefig(fig, CH, "fig7-1", out_dir)


def fig_7_2(out_dir=None):
    """Figure 7.2: contours of a quadratic error near a minimum are ellipses aligned with the Hessian's eigenvectors."""
    lam = np.array([0.6, 2.4])
    th = math.radians(30)
    U = np.array([[math.cos(th), -math.sin(th)], [math.sin(th), math.cos(th)]])    # columns u1, u2
    H = U @ np.diag(lam) @ U.T
    f = lambda w: (0.5 * w @ H @ w, H @ w)  # noqa: E731
    fig, ax = plt.subplots(figsize=(4.4, 3.6))
    C = 0.5                                     # contour E - E* = C: semi-axes sqrt(2C/lambda_i)
    _contours(ax, f, (-2.0, 2.0), (-1.6, 1.6), [C * 0.25, C, C * 2.25], colors=common.RED, linewidths=1.2)
    for i, (col, name) in enumerate(((common.BLUE, r"$\mathbf{u}_1$"), (common.GREEN, r"$\mathbf{u}_2$"))):
        L = math.sqrt(2 * C / lam[i])
        ax.add_patch(FancyArrowPatch((0, 0), tuple(U[:, i] * L), arrowstyle="-|>", mutation_scale=12, color=col, lw=1.5))
        ax.annotate(name, U[:, i] * L * 1.15 + np.array([0.0, 0.04]), color=col, fontsize=11, ha="center")
        lab = r"semi-axis $\sqrt{2C/\lambda_%d}$" % (i + 1)
        if i == 0:
            ax.annotate(lab, (1.05, -0.05), fontsize=8.5, color=col)
        else:
            ax.annotate(lab, (-1.95, 0.75), fontsize=8.5, color=col)
    ax.plot(0, 0, "ko", ms=3)
    ax.annotate(r"$\mathbf{w}^\star$", (0.05, -0.18), fontsize=11)
    ax.set_xlabel(r"$w_1$")
    ax.set_ylabel(r"$w_2$")
    ax.set_aspect("equal")
    ax.set_title(r"$\lambda_1 = 0.6,\ \lambda_2 = 2.4$; middle contour $E - E(\mathbf{w}^\star) = C = 0.5$", fontsize=8.5)
    return savefig(fig, CH, "fig7-2", out_dir)


FIG73 = dict(kappa=20.0, theta=0.0, w0=(-4.2, 0.9), eta=1.85)


def _valley_axes(ax, kappa, xlim=(-4.6, 0.8), ylim=(-1.15, 1.15)):
    f = lambda w: _valley(w, kappa=kappa)  # noqa: E731
    xs = np.linspace(*xlim, 300)
    ys = np.linspace(*ylim, 200)
    Xg, Yg = np.meshgrid(xs, ys)
    Z = 0.5 * (Xg ** 2 / kappa + Yg ** 2)
    ax.contourf(Xg, Yg, Z, levels=[0, 0.02, 0.08, 0.18, 0.32, 0.5, 0.72, 1.0], cmap="Reds_r", alpha=0.55)
    ax.plot(0, 0, "k+", ms=8)
    ax.add_patch(FancyArrowPatch((0, 0), (0.7, 0), arrowstyle="-|>", mutation_scale=10, color="k", lw=1))
    ax.add_patch(FancyArrowPatch((0, 0), (0, 0.55), arrowstyle="-|>", mutation_scale=10, color="k", lw=1))
    ax.annotate(r"$\mathbf{u}_1$", (0.45, 0.07), fontsize=10)
    ax.annotate(r"$\mathbf{u}_2$", (0.06, 0.6), fontsize=10)
    ax.set_xlim(*xlim)
    ax.set_ylim(*ylim)
    ax.set_aspect("equal")
    ax.set_xticks([])
    ax.set_yticks([])
    return f


def fig_7_3(out_dir=None):
    """Figure 7.3: fixed-step gradient descent oscillates across a long valley."""
    p = FIG73
    fig, ax = plt.subplots(figsize=(5.6, 2.2))
    _valley_axes(ax, p["kappa"])
    path, _ = optimise_2d("valley", "gd", p["w0"], 25, p["eta"], kappa=p["kappa"])
    ax.plot(path[:, 0], path[:, 1], "-", color=common.BLUE, lw=1.3)
    ax.plot(path[:, 0], path[:, 1], "o", color=common.BLUE, ms=2.5)
    ax.set_title(r"gradient descent, $\eta = %.2f$, $\lambda_{\max} = 1$, $\lambda_{\min} = 1/%d$, 25 steps" % (p["eta"], p["kappa"]), fontsize=9)
    return savefig(fig, CH, "fig7-3", out_dir)


def fig_7_6(out_dir=None):
    """Figure 7.6: with a momentum term the same valley is traversed much faster."""
    p = FIG73
    fig, ax = plt.subplots(figsize=(5.6, 2.2))
    _valley_axes(ax, p["kappa"])
    pg, _ = optimise_2d("valley", "gd", p["w0"], 25, p["eta"], kappa=p["kappa"])
    pm, _ = optimise_2d("valley", "momentum", p["w0"], 25, 0.7, mu=0.6, kappa=p["kappa"])
    ax.plot(pg[:, 0], pg[:, 1], "-", color=common.GREY, lw=0.8, alpha=0.7, label="no momentum (Figure 7.3)")
    ax.plot(pm[:, 0], pm[:, 1], "-o", color=common.BLUE, lw=1.3, ms=2.5, label=r"momentum, $\eta = 0.7$, $\mu = 0.6$")
    ax.legend(fontsize=7.5, loc="lower right", framealpha=0.9)
    ax.set_title("the same 25 steps from the same start, with momentum (7.31)", fontsize=9)
    return savefig(fig, CH, "fig7-6", out_dir)


def _one_d(ax, lam, eta, mu, w0, steps, title, xlim):
    xs = np.linspace(*xlim, 300)
    ax.plot(xs, 0.5 * lam * xs ** 2, color=common.RED, lw=1.5)
    for (m, col, lab, dy) in ((0.0, common.GREY, "no momentum", 0.0), (mu, common.BLUE, r"momentum $\mu = %.1f$" % mu, 0.0)):
        w, v, pts = w0, 0.0, [w0]
        for _ in range(steps):
            v = -eta * lam * w + m * v
            w = w + v
            pts.append(w)
        pts = np.array(pts)
        E = 0.5 * lam * pts ** 2
        ax.plot(pts, E, "o", color=col, ms=4 if m else 5, mfc="none" if not m else col, label=lab)
        for k in range(min(3, steps)):
            ax.add_patch(FancyArrowPatch((pts[k], E[k]), (pts[k + 1], E[k + 1]), arrowstyle="-|>", mutation_scale=8,
                                         color=col, lw=1.0, connectionstyle="arc3,rad=%s" % ("-0.25" if m else "0.25")))
    ax.set_xlabel(r"$w$")
    ax.set_ylabel(r"$E(w)$")
    ax.set_title(title, fontsize=9)
    ax.legend(fontsize=7.5, loc="upper center")


def fig_7_4(out_dir=None):
    """Figure 7.4: on a surface of low curvature, momentum enlarges the effective learning rate."""
    fig, ax = plt.subplots(figsize=(4.6, 3.0))
    _one_d(ax, lam=0.1, eta=1.0, mu=0.6, w0=-4.0, steps=4,
           title=r"low curvature: $E = \lambda w^2/2$, $\lambda = 0.1$, $\eta = 1$, 4 steps", xlim=(-4.4, 1.0))
    return savefig(fig, CH, "fig7-4", out_dir)


def fig_7_5(out_dir=None):
    """Figure 7.5: when gradient descent oscillates, momentum hardly changes the effective learning rate."""
    fig, ax = plt.subplots(figsize=(4.6, 3.0))
    _one_d(ax, lam=1.0, eta=1.8, mu=0.6, w0=-2.0, steps=3,
           title=r"high curvature: $\lambda = 1$, $\eta = 1.8$ ($\eta\lambda$ close to 2), 3 steps", xlim=(-2.3, 2.3))
    return savefig(fig, CH, "fig7-5", out_dir)


def normalization_data(seed=7, N=25):
    """Two input variables on different scales (Figure 7.7): x1 ~ N(4, 2.5^2), x2 ~ N(0, 4.5^2)."""
    rng = np.random.default_rng(seed)
    return np.column_stack([4 + 2.5 * rng.standard_normal(N), 4.5 * rng.standard_normal(N)])


def standardize(X, mu=None, sd=None):
    """(7.48)-(7.50); pass the training mu and sd to transform validation or test data."""
    mu = X.mean(0) if mu is None else mu
    sd = np.sqrt(((X - mu) ** 2).mean(0)) if sd is None else sd
    return (X - mu) / sd, mu, sd


def fig_7_7(out_dir=None):
    """Figure 7.7: input data before (red circles) and after (blue crosses) normalisation to zero mean and unit variance."""
    X = normalization_data()
    Xn, _, _ = standardize(X)
    fig, ax = plt.subplots(figsize=(3.4, 3.4))
    ax.plot(X[:, 0], X[:, 1], "o", color=common.RED, ms=5, label="original")
    ax.plot(Xn[:, 0], Xn[:, 1], "x", color=common.BLUE, ms=5, mew=1.4, label="normalised")
    ax.set_xlim(-11, 11)
    ax.set_ylim(-11, 11)
    ax.set_xticks([-10, 0, 10])
    ax.set_yticks([-10, 0, 10])
    ax.set_xlabel(r"$x_1$")
    ax.set_ylabel(r"$x_2$")
    ax.set_aspect("equal")
    ax.legend(fontsize=8, loc="lower left")
    return savefig(fig, CH, "fig7-7", out_dir)


def fig_7_8(out_dir=None):
    """Figure 7.8: batch normalisation averages over the mini-batch for each unit; layer normalisation over the units for each example."""
    rng = np.random.default_rng(8)
    K, M = 8, 6
    A = rng.normal(size=(K, M)) * np.array([0.5, 2.0, 1.0, 3.0, 0.8, 1.5]) + np.array([1.0, -2.0, 0.0, 3.0, -1.0, 0.5])
    fig, axes = plt.subplots(1, 2, figsize=(7.4, 3.4))
    for ax, axis, title, lab in ((axes[0], 0, "batch normalisation (7.52)-(7.54)", "a"), (axes[1], 1, "layer normalisation (7.58)-(7.60)", "b")):
        ax.imshow(A, cmap="RdBu_r", vmin=-6, vmax=6, aspect="auto")
        mu = A.mean(axis)
        sd = A.std(axis)
        if axis == 0:
            ax.add_patch(plt.Rectangle((1.5, -0.5), 1, K, fill=False, ec=common.GREEN, lw=2.2))
            for j in range(M):
                ax.text(j, K - 0.5 + 0.55, r"%.1f" % mu[j], ha="center", va="top", fontsize=7.5, color=common.GREEN)
                ax.text(j, K - 0.5 + 1.15, r"%.1f" % sd[j], ha="center", va="top", fontsize=7.5, color=common.PURPLE)
            ax.text(-0.6, K - 0.5 + 0.55, r"$\mu_i$", ha="right", va="top", fontsize=9, color=common.GREEN)
            ax.text(-0.6, K - 0.5 + 1.15, r"$\sigma_i$", ha="right", va="top", fontsize=9, color=common.PURPLE)
        else:
            ax.add_patch(plt.Rectangle((-0.5, 2.5), M, 1, fill=False, ec=common.GREEN, lw=2.2))
            for n in range(K):
                ax.text(M - 0.5 + 0.15, n, r"%.1f" % mu[n], ha="left", va="center", fontsize=7.5, color=common.GREEN)
                ax.text(M - 0.5 + 0.85, n, r"%.1f" % sd[n], ha="left", va="center", fontsize=7.5, color=common.PURPLE)
            ax.text(M - 0.5 + 0.15, -0.95, r"$\mu_n$", ha="left", fontsize=9, color=common.GREEN)
            ax.text(M - 0.5 + 0.85, -0.95, r"$\sigma_n$", ha="left", fontsize=9, color=common.PURPLE)
        for n in range(K):
            for j in range(M):
                ax.text(j, n, "%.1f" % A[n, j], ha="center", va="center", fontsize=6.5, color="k")
        ax.set_xticks(range(M))
        ax.set_xticklabels([str(j + 1) for j in range(M)])
        ax.set_yticks(range(K))
        ax.set_yticklabels([str(n + 1) for n in range(K)])
        ax.set_xlabel(r"hidden unit $i$")
        ax.set_ylabel(r"example $n$ in the mini-batch")
        ax.set_title(title, fontsize=9)
        ax.set_xlim(-0.5, M - 0.5 + (1.6 if axis == 1 else 0))
        ax.set_ylim(K - 0.5 + (1.9 if axis == 0 else 0), -0.5 - (0.6 if axis == 1 else 0))
    fig.tight_layout()
    return savefig(fig, CH, "fig7-8", out_dir)


# ========== supplementary figures
def _avg_stats(L, M, B, act, gain, norm, seeds=(1, 2, 3, 4)):
    """Mean over a few random networks of the per-layer squared rms values."""
    runs = [depth_stats(L, M, B, act, gain, norm, seed=s) for s in seeds]
    return {k: np.mean([r[k] ** 2 for r in runs], axis=0) for k in ("a", "delta")}


def fig_7_s1(out_dir=None):
    """Figure 7.S1: activation and gradient statistics through 30 layers for several initialisation scales."""
    L, M, B = 30, 256, 256
    ls = np.arange(1, L + 1)
    fig, axes = plt.subplots(1, 3, figsize=(10.2, 3.1))
    gains = ((1.0, common.RED, r"$g = 1$ ($\epsilon^2 = 1/M$)"), (math.sqrt(2), common.BLUE, r"$g = \sqrt{2}$ (He)"), (1.6, common.GREEN, r"$g = 1.6$"))
    for gain, col, lab in gains:
        s = _avg_stats(L, M, B, "relu", gain, "none")
        axes[0].semilogy(ls, s["a"], "o", ms=3, color=col, label=lab)
        axes[0].semilogy(ls, relu_second_moment_theory(L, gain), "-", lw=1, color=col)
        axes[2].semilogy(ls, s["delta"], "o-", ms=3, lw=1, color=col, label=lab)
    s = _avg_stats(L, M, B, "relu", 1.0, "batch")
    axes[0].semilogy(ls, s["a"], "s", ms=3, mfc="none", color=common.PURPLE, label=r"$g = 1$ with batch norm")
    axes[2].semilogy(ls, s["delta"], "s-", ms=3, lw=1, mfc="none", color=common.PURPLE, label=r"$g = 1$ with batch norm")
    for gain, col in ((0.8, common.RED), (1.0, common.BLUE), (1.5, common.GREEN)):
        s = _avg_stats(L, M, B, "tanh", gain, "none")
        axes[1].semilogy(ls, s["a"], "o-", ms=3, lw=1, color=col, label=r"$g = %.1f$" % gain)
    axes[0].set_title(r"ReLU: $\mathrm{E}[(a^{(l)})^2]$ (dots) and theory $g^2(g^2/2)^{l-1}$", fontsize=8.5)
    axes[1].set_title(r"tanh: $\mathrm{E}[(a^{(l)})^2]$", fontsize=8.5)
    axes[2].set_title(r"ReLU: backpropagated $\mathrm{E}[(\delta^{(l)})^2]$", fontsize=8.5)
    for ax in axes:
        ax.set_xlabel(r"layer $l$")
        ax.legend(fontsize=7)
    axes[0].set_ylim(1e-5, 1e4)
    axes[2].set_ylim(1e-5, 1e5)
    fig.tight_layout()
    return savefig(fig, CH, "fig7-s1", out_dir)


def fig_7_s2(out_dir=None):
    """Figure 7.S2: per-direction contraction |1 - eta lambda| versus eta, and iterations to converge versus condition number."""
    lmin, lmax = 0.1, 1.0
    etas = np.linspace(0, 2.2, 600)
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 3.2))
    ax = axes[0]
    ax.plot(etas, np.abs(1 - etas * lmin), color=common.BLUE, label=r"$|1-\eta\lambda_{\min}|$")
    ax.plot(etas, np.abs(1 - etas * lmax), color=common.RED, label=r"$|1-\eta\lambda_{\max}|$")
    ax.plot(etas, np.maximum(np.abs(1 - etas * lmin), np.abs(1 - etas * lmax)), "k--", lw=1, label="the slower of the two")
    e_opt, r_opt = optimal_gd(lmin, lmax)
    ax.plot(e_opt, r_opt, "ko", ms=4)
    ax.annotate(r"$\eta^\star = 2/(\lambda_{\min}+\lambda_{\max})$" + "\n" + r"rate $(\kappa-1)/(\kappa+1)$", (e_opt, r_opt), xytext=(0.04, 0.12), fontsize=8, arrowprops=dict(arrowstyle="->", lw=0.7))
    ax.axvline(2 / lmax, color=common.GREY, lw=0.8, ls=":")
    ax.text(2 / lmax + 0.02, 1.1, r"$2/\lambda_{\max}$", fontsize=8, color=common.GREY)
    ax.axhline(1, color=common.GREY, lw=0.6)
    ax.set_xlabel(r"learning rate $\eta$")
    ax.set_ylabel("contraction per step")
    ax.set_ylim(0, 1.25)
    ax.set_title(r"$\lambda_{\min} = 0.1$, $\lambda_{\max} = 1$ ($\kappa = 10$)", fontsize=9)
    ax.legend(fontsize=7.5, loc="lower right")
    ax = axes[1]
    ks = np.logspace(0.3, 4, 40)
    tol = 1e-6
    it_gd = [iterations_to(tol, optimal_gd(1.0 / k, 1.0)[1]) for k in ks]
    it_hb = [iterations_to(tol, optimal_heavy_ball(1.0 / k, 1.0)[2]) for k in ks]
    it_gdmax = [iterations_to(tol, 1 - 2 * 0.95 / k) for k in ks]
    ax.loglog(ks, it_gdmax, color=common.GREY, label=r"gradient descent, $\eta = 0.95 \times 2/\lambda_{\max}$")
    ax.loglog(ks, it_gd, color=common.RED, label=r"gradient descent, $\eta^\star$")
    ax.loglog(ks, it_hb, color=common.BLUE, label=r"heavy ball, $(\eta^\star, \mu^\star)$")
    # simulated check at a few condition numbers: steps until max |alpha_i| < tol
    for k in (10.0, 100.0, 1000.0):
        lams = np.array([1.0 / k, 1.0])
        e, rate = optimal_gd(1.0 / k, 1.0)
        a = quad_eigen_path(lams, [1.0, 1.0], 40000, "gd", e)
        n_gd = int(np.argmax(np.abs(a).max(1) < tol))
        e2, m2, _ = optimal_heavy_ball(1.0 / k, 1.0)
        a2 = quad_eigen_path(lams, [1.0, 1.0], 40000, "momentum", e2, m2)
        n_hb = int(np.argmax(np.abs(a2).max(1) < tol))
        ax.plot(k, n_gd, "o", color=common.RED, ms=4)
        ax.plot(k, n_hb, "o", color=common.BLUE, ms=4)
    ax.set_xlabel(r"condition number $\kappa = \lambda_{\max}/\lambda_{\min}$")
    ax.set_ylabel(r"steps to reduce the error by $10^{-6}$")
    ax.set_title(r"lines: $\ln(10^{-6})/\ln(\mathrm{rate})$; dots: simulated", fontsize=9)
    ax.legend(fontsize=7, loc="upper left")
    fig.tight_layout()
    return savefig(fig, CH, "fig7-s2", out_dir)


def fig_7_s3(out_dir=None):
    """Figure 7.S3: mini-batch gradient variance versus batch size, and SGD versus batch gradient descent per epoch."""
    X, T = mnist_softmax_data(2000, seed=0)
    N = len(X)
    W = np.zeros((10, X.shape[1]))
    for _ in range(20):          # a partly trained model, so the gradient is not trivial
        W -= 0.5 * softmax_grads(W, X, T).mean(0).reshape(W.shape)
    G = softmax_grads(W, X, T)
    gbar = G.mean(0)
    Bs = np.array([1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000])
    rng = np.random.default_rng(3)
    mc = []
    for B in Bs:
        d = [np.sum((G[rng.choice(N, B, replace=False)].mean(0) - gbar) ** 2) for _ in range(300)]
        mc.append(np.mean(d))
    exact = np.array([minibatch_variance(G, B)[0] for B in Bs])
    s2 = minibatch_variance(G, 1)[1]
    fig, axes = plt.subplots(1, 2, figsize=(8.8, 3.3))
    ax = axes[0]
    ax.loglog(Bs[:-1], mc[:-1], "o", color=common.BLUE, ms=4, label="simulated (300 batches each)")
    ax.loglog(Bs[:-1], exact[:-1], "-", color=common.RED, lw=1.2, label=r"exact: $\frac{\sigma^2}{B}\,\frac{N-B}{N-1}$")
    ax.loglog(Bs, s2 / Bs, ":", color=common.GREY, label=r"$\sigma^2/B$ (with replacement)")
    ax.set_xlabel(r"batch size $B$")
    ax.set_ylabel(r"$\mathrm{E}\,\|\widehat{\mathbf{g}}_B - \nabla E\|^2$")
    ax.set_title("softmax regression, $N = 2000$ MNIST digits (at $B = N$ it is 0)", fontsize=9)
    ax.legend(fontsize=7.5)
    ax = axes[1]
    for B, col in ((1, common.BLUE), (10, common.GREEN), (100, common.ORANGE), (N, common.RED)):
        Wb = np.zeros_like(W)
        r = np.random.default_rng(5)
        xs, ls_ = [0.0], [softmax_loss(Wb, X, T)]
        seen = 0
        for ep in range(4):
            order = r.permutation(N)
            for i in range(0, N, B):
                idx = order[i:i + B]
                Wb -= 0.1 * softmax_grads(Wb, X[idx], T[idx]).mean(0).reshape(W.shape)
                seen += len(idx)
                if (seen % max(B, 100)) == 0 or i + B >= N:
                    xs.append(seen / N)
                    ls_.append(softmax_loss(Wb, X, T))
        ax.plot(xs, ls_, "-", color=col, lw=1.3, label=("batch gradient descent" if B == N else "mini-batch $B = %d$" % B))
    ax.set_xlabel("epochs (passes through the data)")
    ax.set_ylabel("training error (mean cross-entropy)")
    ax.set_title(r"same learning rate $\eta = 0.1$ for the mean gradient", fontsize=9)
    ax.set_yscale("log")
    ax.legend(fontsize=7.5)
    fig.tight_layout()
    return savefig(fig, CH, "fig7-s3", out_dir)


S4_RUNS = [("gd", 0.1, 0.0, r"SGD, $\eta = 0.1$", common.GREY),
           ("gd", 0.01, 0.0, r"SGD, $\eta = 0.01$", "#bbbbbb"),
           ("momentum", 0.01, 0.9, r"momentum, $\eta = 0.01$, $\mu = 0.9$", common.BLUE),
           ("nesterov", 0.01, 0.9, r"Nesterov, $\eta = 0.01$, $\mu = 0.9$", common.CYAN),
           ("adagrad", 0.02, 0.0, r"AdaGrad, $\eta = 0.02$", common.ORANGE),
           ("rmsprop", 0.001, 0.0, r"RMSProp, $\eta = 10^{-3}$, $\beta = 0.9$", common.GREEN),
           ("adam", 0.001, 0.0, r"Adam, $\eta = 10^{-3}$", common.RED)]


def s4_results():
    def go():
        res = {}
        for (m, eta, mu, lab, col) in S4_RUNS:
            b2 = 0.9 if m == "rmsprop" else 0.999
            res[lab] = train_mlp([100], m, eta, 600, B=50, mu=mu, b2=b2, seed=0)
        return res
    return _cached("ch07_s4_optimisers", go)


def fig_7_s4(out_dir=None):
    """Figure 7.S4: the optimisers of Section 7.3 training a 784-100-10 ReLU network on 5000 MNIST digits."""
    res = s4_results()
    fig, ax = plt.subplots(figsize=(5.6, 3.4))
    for (m, eta, mu, lab, col) in S4_RUNS:
        s, l = res[lab]
        ax.plot(s, l, color=col, lw=1.4, label=lab)
    ax.set_yscale("log")
    ax.set_xlabel(r"step (mini-batches of $B = 50$; 100 steps = one epoch)")
    ax.set_ylabel("training error (mean cross-entropy)")
    ax.legend(fontsize=7, ncol=1)
    ax.set_title("the same network, initialisation and mini-batch order for every optimiser", fontsize=8.5)
    return savefig(fig, CH, "fig7-s4", out_dir)


S5_ETAS = [0.01, 0.03, 0.1, 0.3, 1.0, 3.0]


def s5_results():
    def go():
        res = {}
        for norm in ("none", "batch", "layer"):
            for eta in S5_ETAS:
                res[(norm, eta)] = train_mlp([64] * 10, "gd", eta, 300, B=50, norm=norm, gain=1.0, seed=1)
        return res
    return _cached("ch07_s5_normalisation", go)


def fig_7_s5(out_dir=None):
    """Figure 7.S5: a 10-hidden-layer ReLU network trained by SGD with and without batch and layer normalisation."""
    res = s5_results()
    cols = {"none": common.GREY, "batch": common.BLUE, "layer": common.GREEN}
    labs = {"none": "no normalisation", "batch": "batch normalisation", "layer": "layer normalisation"}
    fig, axes = plt.subplots(1, 2, figsize=(8.8, 3.3))
    for norm in ("none", "batch", "layer"):
        s, l = res[(norm, 0.1)]
        axes[0].plot(s, l, color=cols[norm], lw=1.4, label=labs[norm])
        fin = [res[(norm, e)][1][-1] if len(res[(norm, e)][1]) == 31 else np.nan for e in S5_ETAS]
        axes[1].semilogx(S5_ETAS, fin, "o-", color=cols[norm], lw=1.2, ms=4, label=labs[norm])
    axes[0].set_yscale("log")
    axes[0].set_xlabel("SGD step ($B = 50$)")
    axes[0].set_ylabel("training error")
    axes[0].set_title(r"$\eta = 0.1$; weights $N(0, 1/M)$ (half the He variance)", fontsize=8.5)
    axes[0].legend(fontsize=7.5)
    axes[1].set_xlabel(r"learning rate $\eta$")
    axes[1].set_ylabel("training error after 300 steps")
    axes[1].set_title(r"$\ln 10 = 2.30$ is chance level (a dead or diverged network)", fontsize=8.5)
    axes[1].set_yscale("log")
    axes[1].legend(fontsize=7.5)
    fig.tight_layout()
    return savefig(fig, CH, "fig7-s5", out_dir)


def ewma(x, beta, correct=False):
    """mu_n = beta mu_{n-1} + (1 - beta) x_n with mu_0 = 0 (7.66); correct=True divides by 1 - beta^n (7.68)."""
    out, m = [], 0.0
    for n, xn in enumerate(x, start=1):
        m = beta * m + (1 - beta) * xn
        out.append(m / (1 - beta ** n) if correct else m)
    return np.array(out)


def fig_7_s6(out_dir=None):
    """Figure 7.S6: an exponentially weighted moving average started at zero is biased towards zero; dividing by 1 - beta^n removes the bias."""
    rng = np.random.default_rng(6)
    n, R = 80, 4000
    xs = 1.0 + 0.5 * rng.standard_normal((R, n))
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 3.0))
    for ax, beta in ((axes[0], 0.9), (axes[1], 0.99)):
        raw = np.array([ewma(x, beta) for x in xs[:400]])
        cor = np.array([ewma(x, beta, True) for x in xs[:400]])
        t = np.arange(1, n + 1)
        ax.plot(t, xs[0], ".", color="#bbbbbb", ms=3, label=r"one sequence $x_n$")
        ax.plot(t, raw.mean(0), color=common.RED, lw=1.5, label=r"average of $\mu_n$ (400 runs)")
        ax.plot(t, 1 - beta ** t, "k:", lw=1.2, label=r"$(1-\beta^n)\,\mathrm{E}[x]$")
        ax.plot(t, cor.mean(0), color=common.BLUE, lw=1.5, label=r"average of $\widehat{\mu}_n = \mu_n/(1-\beta^n)$")
        ax.set_title(r"$\beta = %s$, $x_n \sim N(1, 0.5^2)$" % beta, fontsize=9)
        ax.set_xlabel(r"$n$")
        ax.set_ylim(-0.1, 2.2)
    axes[0].legend(fontsize=7, loc="upper right")
    fig.tight_layout()
    return savefig(fig, CH, "fig7-s6", out_dir)


FIGURES = {"7.1": fig_7_1, "7.2": fig_7_2, "7.3": fig_7_3, "7.4": fig_7_4, "7.5": fig_7_5, "7.6": fig_7_6,
           "7.7": fig_7_7, "7.8": fig_7_8,
           "7.S1": fig_7_s1, "7.S2": fig_7_s2, "7.S3": fig_7_s3, "7.S4": fig_7_s4, "7.S5": fig_7_s5, "7.S6": fig_7_s6}


if __name__ == "__main__":
    run(FIGURES, CH)
