"""Murphy (2022), Chapter 8: Optimization.

Companion code for Chapter 8 of K. P. Murphy, Probabilistic Machine Learning: An Introduction
(MIT Press, 2022; April 2025 draft), pp. 275-320, written from scratch with numpy, scipy and
matplotlib (PyTorch only for the small network of Figure 8.17), to be read next to the lecture notes
(../ch08-optimization.html). scipy is only used to confirm the implementations.

Methods
* Section 8.1: test functions and their gradients and Hessians, subgradients of |x| and of the hinge loss.
* Section 8.2, first-order methods: gradient descent with a constant step (8.15), exact line search for a
  quadratic (8.26), Armijo backtracking (8.27), heavy-ball momentum (8.30)-(8.31), Nesterov's method
  (8.35)-(8.38): gd, gd_exact_quadratic, armijo, gd_armijo, heavy_ball, nesterov.
* Section 8.3, second-order methods: Newton's method (Algorithm 8.1), BFGS with the inverse update (8.48),
  the trust-region subproblem (8.49)-(8.52) solved exactly, and a trust-region method: newton, bfgs,
  tr_subproblem, trust_region, damped_newton.
* Section 8.4, stochastic gradient descent: the least mean squares algorithm (8.60), learning-rate
  schedules (8.62)-(8.64), warm-up and cyclical schedules, iterate averaging (8.65), SVRG (8.66), SAGA
  (8.67), AdaGrad (8.69)-(8.71), RMSProp (8.72)-(8.74), Adam (8.77)-(8.81), AMSGrad, Yogi (8.83) and
  ADOPT. Mulberry32 reproduces the random numbers of the browser demonstrations exactly.
* Section 8.5, constrained optimisation: a small quadratic-programming solver that enumerates active
  sets and checks the KKT conditions (8.103)-(8.106), and the simplex method for linear programs.
* Section 8.6, proximal methods: projection on a box (8.126) and on the l1 ball, soft thresholding
  (8.133)-(8.135), the quantisation prox (8.143), ISTA and FISTA for the lasso.
* Section 8.7, bound optimisation: the EM algorithm for a Gaussian mixture, MLE and MAP (8.160)-(8.174)
  (with the corrected covariance update, see the notes), the mean-shift MM step for a kernel density
  and the Newton step it is compared with, EM for the multivariate Student distribution (Exercise 8.2).

Data. Figure 8.16 uses 21 simulated points (the book's own points are not available; the truth
(1.45, 0.92) is the book's). Figure 8.17 uses a 5000-image subset of MNIST and two epochs on the CPU
instead of FashionMNIST. Figure 8.24 uses the 82 galaxy velocities of Roeder (1990), as distributed with
the R package MASS, as the empirical density. Figure 8.25 uses the Old Faithful data (standardised).
Figure 8.S3 uses two features of the Wisconsin breast-cancer data from scikit-learn.

Figures. Reproduced here: 8.1, 8.2, 8.4-8.12, 8.14-8.27 (the illustrations 8.2, 8.4, 8.5, 8.8, 8.9,
8.15, 8.21, 8.22 and 8.23 are redrawn from computed examples of my own). Skipped, with the reason:
  8.3  hand-drawn examples of convex and non-convex sets (nothing is computed);
  8.13 a sketch of the Nesterov look-ahead vector diagram (nothing is computed; Figure 8.S2 shows the
       method on a quadratic instead).
Supplementary figures for the gaps filled in the notes:
  8.S1 steepest descent with exact line search against the Kantorovich bound (8.29);
  8.S2 gradient descent, heavy ball and Nesterov on an ill-conditioned quadratic with the theoretical rates;
  8.S3 SGD, iterate averaging, SVRG and SAGA on a finite-sum logistic regression;
  8.S4 Adam does not converge on the online problem of Reddi et al. (2018), while AMSGrad and ADOPT do;
  8.S5 proximal operators, and ISTA against FISTA and the subgradient method on the lasso;
  8.S6 EM for the multivariate Student distribution (Exercise 8.2).
Run `python3 ch08_optimization.py --list`, `python3 ch08_optimization.py` (all figures, about two
minutes) or `python3 ch08_optimization.py --fig 8.11`. Files go to ../img/ch08/; the data used by the
browser demonstrations go to ../data/ch08-*.json.
"""
import json
import os
import sys

os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")

import numpy as np
from scipy import stats

sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
import common  # noqa: E402
from common import BLUE, GREEN, GREY, MAGENTA, ORANGE, PURPLE, RED, plt, savefig  # noqa: E402

CH = 8
HERE = os.path.dirname(os.path.abspath(__file__))
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))

# Radial velocities (km/s) of 82 galaxies in the Corona Borealis region (Roeder 1990), the data set
# `galaxies` of the R package MASS.
GALAXIES = np.array([
    9172, 9350, 9483, 9558, 9775, 10227, 10406, 16084, 16170, 18419, 18552, 18600, 18927, 19052, 19070,
    19330, 19343, 19349, 19440, 19473, 19529, 19541, 19547, 19663, 19846, 19856, 19863, 19914, 19918,
    19973, 19989, 20166, 20175, 20179, 20196, 20215, 20221, 20415, 20629, 20795, 20821, 20846, 20875,
    20986, 21137, 21492, 21701, 21814, 21921, 21960, 22185, 22209, 22242, 22249, 22314, 22374, 22495,
    22746, 22747, 22888, 22914, 23206, 23241, 23263, 23484, 23538, 23542, 23666, 23706, 23711, 24129,
    24285, 24289, 24366, 24717, 24990, 25633, 26690, 26995, 32065, 32789, 34279], float)


def faithful(standardize=True):
    """Old Faithful (272 x 2: eruption minutes, waiting minutes), read from the companion course data."""
    path = os.path.normpath(os.path.join(HERE, "..", "..", "ml", "code", "data", "faithful.csv"))
    X = np.loadtxt(path, delimiter=",", skiprows=1)
    if standardize:
        X = (X - X.mean(0)) / X.std(0)
    return X


# =========================================================================== random numbers shared with the demos
class Mulberry32:
    """The generator of DK.rng in ../../demo-kit.js (mulberry32), bit for bit, so that the browser
    demonstrations and this module draw the same sample indices."""

    def __init__(self, seed):
        self.a = seed & 0xFFFFFFFF

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

    def index(self, n):
        return int(np.floor(self.u() * n))


# =========================================================================== Section 8.1: test functions
def tilted_double_well(x, tilt=0.4):
    """(x^2 - 1)^2 + tilt x: a global minimum near -1 and a local one near +1 (Figure 8.1a)."""
    return (x ** 2 - 1) ** 2 + tilt * x


def valley(th):
    """The book's (8.19): 0.5 (t1^2 - t2)^2 + 0.5 (t1 - 1)^2, minimum 0 at (1, 1). Not convex (see notes)."""
    t1, t2 = th[0], th[1]
    return 0.5 * (t1 ** 2 - t2) ** 2 + 0.5 * (t1 - 1) ** 2


def valley_grad(th):
    t1, t2 = th
    u = t1 ** 2 - t2
    return np.array([2 * t1 * u + (t1 - 1), -u])


def valley_hess(th):
    t1, t2 = th
    return np.array([[6 * t1 ** 2 - 2 * t2 + 1, -2 * t1], [-2 * t1, 1.0]])


def rosen(th, b=10.0):
    """A Rosenbrock function (1 - t1)^2 + b (t2 - t1^2)^2 (b = 10 keeps the plots readable)."""
    return (1 - th[0]) ** 2 + b * (th[1] - th[0] ** 2) ** 2


def rosen_grad(th, b=10.0):
    t1, t2 = th
    return np.array([-2 * (1 - t1) - 4 * b * t1 * (t2 - t1 ** 2), 2 * b * (t2 - t1 ** 2)])


def rosen_hess(th, b=10.0):
    t1, t2 = th
    return np.array([[2 - 4 * b * (t2 - t1 ** 2) + 8 * b * t1 ** 2, -4 * b * t1], [-4 * b * t1, 2 * b]])


def saddle_fn(th):
    """A non-convex function with a saddle at the origin and two minima at (+-1, 0) (tilted): used for
    Figure 8.15 and the trust-region demonstration: x^4/4 - x^2/2 + 0.1 x + y^2/2 + 0.2 x y."""
    x, y = th
    return 0.25 * x ** 4 - 0.5 * x ** 2 + 0.1 * x + 0.5 * y ** 2 + 0.2 * x * y


def saddle_grad(th):
    x, y = th
    return np.array([x ** 3 - x + 0.1 + 0.2 * y, y + 0.2 * x])


def saddle_hess(th):
    x, y = th
    return np.array([[3 * x ** 2 - 1, 0.2], [0.2, 1.0]])


def quad_fns(A, b, c=0.0):
    """f(t) = 0.5 t'At + b't + c with gradient At + b and Hessian A."""
    A = np.asarray(A, float)
    b = np.asarray(b, float)
    return (lambda t: 0.5 * t @ A @ t + b @ t + c), (lambda t: A @ t + b), (lambda t: A)


def demo_quad_A(kappa, angle=np.pi / 6):
    """The quadratic of the Newton/BFGS demo: A = R diag(1, kappa) R' with R a rotation by 30 degrees."""
    c, s = np.cos(angle), np.sin(angle)
    return np.array([[c * c + kappa * s * s, (1 - kappa) * c * s], [(1 - kappa) * c * s, s * s + kappa * c * c]])


def subdiff_abs(x):
    """(8.14): the subdifferential of |x| as an interval (lo, hi)."""
    return (-1.0, -1.0) if x < 0 else ((1.0, 1.0) if x > 0 else (-1.0, 1.0))


def subdiff_hinge(x):
    """Exercise 8.1: the subdifferential of (1 - x)_+ as an interval."""
    return (-1.0, -1.0) if x < 1 else ((0.0, 0.0) if x > 1 else (-1.0, 0.0))


# =========================================================================== Section 8.2: first-order methods
def gd(grad, x0, eta, n):
    """(8.15) with d_t = -g_t and a constant step: returns the n + 1 iterates."""
    x = np.array(x0, float)
    path = [x.copy()]
    for _ in range(n):
        x = x - eta * grad(x)
        path.append(x.copy())
    return np.array(path)


def gd_exact_quadratic(A, b, x0, n):
    """Steepest descent with the exact step (8.26) on 0.5 x'Ax + b'x."""
    A = np.asarray(A, float)
    x = np.array(x0, float)
    path = [x.copy()]
    for _ in range(n):
        g = A @ x + b
        if g @ g < 1e-30:
            break
        eta = (g @ g) / (g @ A @ g)       # (8.26) with d = -g
        x = x - eta * g
        path.append(x.copy())
    return np.array(path)


def armijo(f, x, d, g, eta0=1.0, c=1e-4, rho=0.5, max_halvings=60):
    """Backtracking until (8.27): f(x + eta d) <= f(x) + c eta d'g. Returns eta and the number of trials."""
    fx, slope, eta = f(x), d @ g, eta0
    for k in range(max_halvings):
        if f(x + eta * d) <= fx + c * eta * slope:
            return eta, k + 1
        eta *= rho
    return eta, max_halvings


def gd_armijo(f, grad, x0, n, eta0=1.0, c=1e-4, rho=0.5):
    x = np.array(x0, float)
    path = [x.copy()]
    for _ in range(n):
        g = grad(x)
        eta, _ = armijo(f, x, -g, g, eta0, c, rho)
        x = x - eta * g
        path.append(x.copy())
    return np.array(path)


def heavy_ball(grad, x0, eta, beta, n):
    """(8.30)-(8.31): m_t = beta m_{t-1} + g_{t-1}, x_t = x_{t-1} - eta m_t."""
    x = np.array(x0, float)
    m = np.zeros_like(x)
    path = [x.copy()]
    for _ in range(n):
        m = beta * m + grad(x)
        x = x - eta * m
        path.append(x.copy())
    return np.array(path)


def nesterov(grad, x0, eta, beta, n):
    """(8.35)-(8.36): look ahead by beta (x_t - x_{t-1}), then take a gradient step there."""
    x = np.array(x0, float)
    xprev = x.copy()
    path = [x.copy()]
    for _ in range(n):
        look = x + beta * (x - xprev)
        xprev, x = x, look - eta * grad(look)
        path.append(x.copy())
    return np.array(path)


def nesterov_momentum_form(grad, x0, eta, beta, n):
    """(8.37)-(8.38): m_{t+1} = beta m_t - eta grad(x_t + beta m_t), x_{t+1} = x_t + m_{t+1}."""
    x = np.array(x0, float)
    m = np.zeros_like(x)
    path = [x.copy()]
    for _ in range(n):
        m = beta * m - eta * grad(x + beta * m)
        x = x + m
        path.append(x.copy())
    return np.array(path)


def kantorovich_rate(A):
    """(8.29): ((lmax - lmin) / (lmax + lmin))^2."""
    ev = np.linalg.eigvalsh(A)
    return ((ev[-1] - ev[0]) / (ev[-1] + ev[0])) ** 2


# =========================================================================== Section 8.3: second-order methods
def newton(grad, hess, x0, n, f=None, line_search=False):
    """Algorithm 8.1. With line_search=False this is the pure Newton step (eta = 1)."""
    x = np.array(x0, float)
    path = [x.copy()]
    for _ in range(n):
        g, H = grad(x), hess(x)
        d = np.linalg.solve(H, -g)
        eta = armijo(f, x, d, g)[0] if line_search else 1.0
        x = x + eta * d
        path.append(x.copy())
    return np.array(path)


def bfgs(f, grad, x0, n, eta0=1.0, c=1e-4, rho=0.5):
    """BFGS with the inverse-Hessian update (8.48), C_0 = I, and Armijo backtracking.
    The update is skipped when y's <= 1e-12 (it would destroy positive definiteness)."""
    x = np.array(x0, float)
    D = len(x)
    C = np.eye(D)
    g = grad(x)
    path, Cs = [x.copy()], [C.copy()]
    for _ in range(n):
        if g @ g < 1e-28:
            path.append(x.copy())
            continue
        d = -C @ g
        eta, _ = armijo(f, x, d, g, eta0, c, rho)
        xn = x + eta * d
        gn = grad(xn)
        s, y = xn - x, gn - g
        sy = s @ y
        if sy > 1e-12:
            V = np.eye(D) - np.outer(s, y) / sy
            C = V @ C @ V.T + np.outer(s, s) / sy          # (8.48)
        x, g = xn, gn
        path.append(x.copy())
        Cs.append(C.copy())
    return np.array(path), Cs


def bfgs_B_update(B, s, y):
    """(8.44): the direct update of the Hessian approximation."""
    Bs = B @ s
    return B + np.outer(y, y) / (y @ s) - np.outer(Bs, Bs) / (s @ Bs)


def bfgs_C_update(C, s, y):
    """(8.48): the update of the inverse-Hessian approximation."""
    sy = s @ y
    V = np.eye(len(s)) - np.outer(s, y) / sy
    return V @ C @ V.T + np.outer(s, s) / sy


def tr_subproblem(g, H, r, tol=1e-12):
    """min_d g'd + 0.5 d'Hd subject to ||d|| <= r, solved exactly through the eigendecomposition of H:
    d(lam) = -(H + lam I)^{-1} g with lam >= max(0, -lambda_min) and lam (r - ||d||) = 0 (the Tikhonov
    damping form (8.52)). Returns d and lam. The 'hard case' (g orthogonal to the bottom eigenvector) is
    handled by adding a multiple of that eigenvector."""
    ev, V = np.linalg.eigh(H)
    gt = V.T @ g
    lo = max(0.0, -ev[0])

    def dnorm(lam):
        return np.sqrt(np.sum((gt / (ev + lam)) ** 2))

    if ev[0] > 0 and dnorm(0.0) <= r:
        return -V @ (gt / ev), 0.0
    # hard case: ||d(lam)|| stays below r as lam -> -lambda_min
    if abs(gt[0]) < 1e-12 and ev[0] <= 0:
        mask = np.abs(ev - ev[0]) > 1e-12
        dd = np.zeros_like(gt)
        dd[mask] = -gt[mask] / (ev[mask] - ev[0])
        if np.linalg.norm(dd) <= r:
            tau = np.sqrt(max(r ** 2 - dd @ dd, 0.0))
            dd[np.argmin(ev)] = tau
            return V @ dd, -ev[0]
    a = lo + 1e-14
    while dnorm(a) < r:            # numerical safety
        a = lo + (a - lo) / 10
        if a - lo < 1e-300:
            break
    bnd = lo + np.linalg.norm(g) / r + 1.0
    for _ in range(200):           # bisection on ||d(lam)|| = r (decreasing in lam)
        mid = 0.5 * (a + bnd)
        if dnorm(mid) > r:
            a = mid
        else:
            bnd = mid
        if bnd - a < tol * (1 + bnd):
            break
    lam = 0.5 * (a + bnd)
    return -V @ (gt / (ev + lam)), lam


def trust_region(f, grad, hess, x0, n, r0=0.5, rmax=2.0, eta_acc=0.1):
    """A standard trust-region method: solve (8.49)-(8.50) in a ball, compare the actual decrease with the
    decrease predicted by the quadratic model (ratio rho), shrink the radius (r/4) if rho < 1/4, enlarge it
    (2r, at most rmax) if rho > 3/4 and the step reached the boundary, accept the step if rho > eta_acc.
    Returns the iterates and the radii used."""
    x = np.array(x0, float)
    r = r0
    path, radii = [x.copy()], []
    for _ in range(n):
        g, H = grad(x), hess(x)
        if g @ g < 1e-24:
            break
        d, _ = tr_subproblem(g, H, r)
        pred = -(g @ d + 0.5 * d @ H @ d)
        ared = f(x) - f(x + d)
        rho = ared / pred if pred > 0 else -1.0
        radii.append(r)
        if rho > eta_acc:
            x = x + d
        if rho < 0.25:
            r = 0.25 * r
        elif rho > 0.75 and abs(np.linalg.norm(d) - r) < 1e-8:
            r = min(2 * r, rmax)
        path.append(x.copy())
    return np.array(path), np.array(radii)


def damped_newton(grad, hess, x0, n, lam):
    """Newton with Tikhonov damping (8.52): x <- x - (H + lam I)^{-1} g, lam fixed."""
    x = np.array(x0, float)
    path = [x.copy()]
    for _ in range(n):
        H = hess(x) + lam * np.eye(len(x))
        x = x - np.linalg.solve(H, grad(x))
        path.append(x.copy())
    return np.array(path)


# =========================================================================== Section 8.4: SGD
def lms_data(seed=0, n=21):
    """21 points y = 1.45 + 0.92 x + noise, x ~ Unif(-2, 2), noise sd 0.5 (a stand-in for the data of the
    book's Figure 11.2). Returns the design matrix with a column of ones, and y."""
    rng = np.random.default_rng(seed)
    x = rng.uniform(-2, 2, n)
    y = 1.45 + 0.92 * x + rng.normal(0, 0.5, n)
    return np.column_stack([np.ones(n), x]), y


def lms(X, y, w0, n_iter, eta0=0.5, t0=3.0, seed=1):
    """(8.60): one example per step, taken in a fresh random order each epoch, with the schedule
    eta_t = eta0 t0 / (t0 + t). Returns the iterates and the mean squared error after each step."""
    rng = np.random.default_rng(seed)
    w = np.array(w0, float)
    N = len(y)
    path, rss = [w.copy()], [np.mean((X @ w - y) ** 2)]
    order = rng.permutation(N)
    for t in range(n_iter):
        if t > 0 and t % N == 0:
            order = rng.permutation(N)
        i = order[t % N]
        eta = eta0 * t0 / (t0 + t)
        w = w - eta * (X[i] @ w - y[i]) * X[i]
        path.append(w.copy())
        rss.append(np.mean((X @ w - y) ** 2))
    return np.array(path), np.array(rss)


def sched_piecewise(t, eta0=1.0, gamma=0.9, milestones=(25, 50, 75)):
    """(8.62) with eta_i = eta0 gamma^i (step decay)."""
    t = np.asarray(t)
    return eta0 * gamma ** np.sum(t[..., None] > np.asarray(milestones), axis=-1)


def sched_exp(t, eta0=1.0, lam=0.1):
    """(8.63)."""
    return eta0 * np.exp(-lam * np.asarray(t, float))


def sched_poly(t, eta0=1.0, alpha=0.5, beta=1.0):
    """(8.64)."""
    return eta0 * (beta * np.asarray(t, float) + 1) ** (-alpha)


def sched_warmup_cosine(t, peak=0.3, warm=5, total=20):
    """Linear warm-up to `peak` over `warm` steps, then a cosine decay to 0 at `total`."""
    t = np.asarray(t, float)
    up = peak * t / warm
    down = 0.5 * peak * (1 + np.cos(np.pi * np.clip((t - warm) / (total - warm), 0, 1)))
    return np.where(t < warm, up, down)


def sched_cyclic(t, lo=0.1, hi=1.0, half=10, decay=0.97):
    """Triangular cyclical schedule between lo and a maximum that decays geometrically per step."""
    t = np.asarray(t, float)
    cyc = np.floor(1 + t / (2 * half))
    x = np.abs(t / half - 2 * cyc + 1)
    return lo + (hi - lo) * np.maximum(0, 1 - x) * decay ** t


# == a finite-sum problem: L2-regularised logistic regression, used by Figure 8.S3 and the SGD demo
def bc_data():
    """Two standardised features of the breast-cancer data (mean texture, mean smoothness), labels in
    {0, 1} (1 = malignant)."""
    from sklearn.datasets import load_breast_cancer
    d = load_breast_cancer()
    names = list(d.feature_names)
    X = d.data[:, [names.index("mean texture"), names.index("mean smoothness")]]
    X = (X - X.mean(0)) / X.std(0)
    y = (d.target == 0).astype(float)
    return X, y


LOGREG_LAM = 0.01


def logreg_loss(w, X, y, lam=LOGREG_LAM):
    """(1/N) sum_n [log(1 + e^{a_n}) - y_n a_n] + (lam/2)||w||^2 with a_n = w'x_n (no intercept)."""
    a = X @ w
    return np.mean(np.logaddexp(0, a) - y * a) + 0.5 * lam * w @ w


def logreg_grad_n(w, x, yn, lam=LOGREG_LAM):
    """Gradient of the n-th term L_n (so that the mean of the L_n is logreg_loss)."""
    return (common.sigmoid(x @ w) - yn) * x + lam * w


def logreg_grad(w, X, y, lam=LOGREG_LAM):
    return X.T @ (common.sigmoid(X @ w) - y) / len(y) + lam * w


def logreg_opt(X, y, lam=LOGREG_LAM):
    """The minimiser by Newton's method (the loss is strongly convex)."""
    w = np.zeros(X.shape[1])
    for _ in range(50):
        p = common.sigmoid(X @ w)
        H = (X * (p * (1 - p))[:, None]).T @ X / len(y) + lam * np.eye(X.shape[1])
        w = w - np.linalg.solve(H, logreg_grad(w, X, y, lam))
    return w


def run_stochastic(method, X, y, w0, epochs, eta, seed=1, batch=1, schedule="constant", decay=1.0,
                   beta1=0.9, beta2=0.999, eps=1e-8, lam=LOGREG_LAM):
    """One run of a stochastic method on the finite sum above, with sample indices from Mulberry32(seed)
    (sampling with replacement, as in the browser demo). method is one of 'sgd', 'avg' (SGD plus the
    running Polyak-Ruppert average (8.65)), 'svrg' (8.66, snapshot each epoch), 'saga' (8.67), 'adam'
    (8.77)-(8.81), 'gd' (full gradient, one step per epoch). One epoch = N gradient evaluations of single
    examples (svrg: N steps after a full gradient; gd: one full step).
    schedule: 'constant', 'sqrt' (eta / sqrt(1 + decay k)), 'inv' (eta / (1 + decay k)) with k the
    step counter. Returns the loss after each epoch (of the average for 'avg')."""
    rng = Mulberry32(seed)
    N = len(y)
    w = np.array(w0, float)
    out = [logreg_loss(w, X, y, lam)]
    k = 0
    wbar = w.copy()
    m = np.zeros_like(w)
    v = np.zeros_like(w)
    if method == "saga":
        table = np.array([logreg_grad_n(w, X[i], y[i], lam) for i in range(N)])
        gavg = table.mean(0)

    def step(k):
        if schedule == "sqrt":
            return eta / np.sqrt(1.0 + decay * k)
        if schedule == "inv":
            return eta / (1.0 + decay * k)
        return eta

    steps_per_epoch = N // batch
    for ep in range(epochs):
        if method == "gd":
            w = w - step(ep) * logreg_grad(w, X, y, lam)
            out.append(logreg_loss(w, X, y, lam))
            continue
        if method == "svrg":
            snap = w.copy()
            mu = logreg_grad(snap, X, y, lam)
        for _ in range(steps_per_epoch):
            idx = [rng.index(N) for _ in range(batch)]
            if method in ("sgd", "avg", "adam"):
                g = np.mean([logreg_grad_n(w, X[i], y[i], lam) for i in idx], axis=0)
            elif method == "svrg":
                g = np.mean([logreg_grad_n(w, X[i], y[i], lam) - logreg_grad_n(snap, X[i], y[i], lam)
                             for i in idx], axis=0) + mu
            elif method == "saga":
                i = idx[0]
                gi = logreg_grad_n(w, X[i], y[i], lam)
                g = gi - table[i] + gavg
                gavg = gavg + (gi - table[i]) / N
                table[i] = gi
            k += 1
            if method == "adam":
                m = beta1 * m + (1 - beta1) * g
                v = beta2 * v + (1 - beta2) * g * g
                mh = m / (1 - beta1 ** k)
                vh = v / (1 - beta2 ** k)
                w = w - step(k - 1) * mh / (np.sqrt(vh) + eps)
            else:
                w = w - step(k - 1) * g
            if method == "avg":
                wbar = wbar + (w - wbar) / k        # (8.65): running mean of theta_1..theta_k
        out.append(logreg_loss(wbar if method == "avg" else w, X, y, lam))
    return np.array(out), (wbar if method == "avg" else w)


# == adaptive methods on the online problem of Reddi, Kale and Kumar (2018)
def reddi_online(method, T=60000, C=3.0, alpha=0.5, beta1=0.0, beta2=None, eps=1e-8):
    """f_t(x) = C x if t mod 3 == 1, else -x, on x in [-1, 1] (t = 1, 2, ...). The average loss is
    minimised at x = -1. Steps alpha / sqrt(t), projected on [-1, 1]. beta2 defaults to 1/(1 + C^2), the
    value in Reddi et al.'s Theorem 1. Returns the iterates."""
    if beta2 is None:
        beta2 = 1.0 / (1.0 + C ** 2)
    x, m, v, vhat = 1.0, 0.0, 0.0, 0.0
    xs = np.empty(T)
    for t in range(1, T + 1):
        g = C if t % 3 == 1 else -1.0
        eta = alpha / np.sqrt(t)
        if method == "sgd":
            x = x - eta * g
        elif method == "adam":                 # (8.77)-(8.79), beta1 = 0 by default, no bias correction
            m = beta1 * m + (1 - beta1) * g
            v = beta2 * v + (1 - beta2) * g * g
            x = x - eta * m / (np.sqrt(v) + eps)
        elif method == "amsgrad":              # keep the running maximum of v
            m = beta1 * m + (1 - beta1) * g
            v = beta2 * v + (1 - beta2) * g * g
            vhat = max(vhat, v)
            x = x - eta * m / (np.sqrt(vhat) + eps)
        elif method == "yogi":                 # (8.83)
            m = beta1 * m + (1 - beta1) * g
            v = v + (1 - beta2) * g * g * np.sign(g * g - v)
            x = x - eta * m / (np.sqrt(v) + eps)
        elif method == "adopt":                # normalise by the previous second moment, then average
            if t == 1:
                v = g * g
                xs[0] = x
                continue
            m = beta1 * m + (1 - beta1) * g / max(np.sqrt(v), eps)
            x = x - eta * m
            v = beta2 * v + (1 - beta2) * g * g
        x = min(1.0, max(-1.0, x))
        xs[t - 1] = x
    return xs


# =========================================================================== Section 8.5: constrained optimisation
def qp_kkt(H, c, A=None, b=None, Ceq=None, d=None, tol=1e-9):
    """min 0.5 t'Ht + c't s.t. A t <= b, Ceq t = d, with H positive definite, by enumerating the active
    sets: for each subset S of the inequalities solve the KKT system with the rows of S as equalities and
    keep the first solution that is feasible with mu >= 0 (8.103)-(8.106). Fine for the tiny problems of the
    figures and the demo (with H positive definite the KKT point is the unique global minimiser).
    Returns theta, mu (one per inequality, zero for inactive ones), lam (one per equality)."""
    from itertools import combinations
    H = np.asarray(H, float)
    c = np.asarray(c, float)
    D = len(c)
    A = np.zeros((0, D)) if A is None else np.asarray(A, float)
    b = np.zeros(0) if b is None else np.asarray(b, float)
    Ceq = np.zeros((0, D)) if Ceq is None else np.asarray(Ceq, float)
    d = np.zeros(0) if d is None else np.asarray(d, float)
    m, p = len(b), len(d)
    for size in range(0, min(m, D - p) + 1):
        for S in combinations(range(m), size):
            E = np.vstack([Ceq, A[list(S)]]) if (p + size) else np.zeros((0, D))
            e = np.concatenate([d, b[list(S)]])
            k = len(e)
            K = np.block([[H, E.T], [E, np.zeros((k, k))]])
            rhs = np.concatenate([-c, e])
            try:
                sol = np.linalg.solve(K, rhs)
            except np.linalg.LinAlgError:
                continue
            th, mult = sol[:D], sol[D:]
            lam, muS = mult[:p], mult[p:]
            if np.all(A @ th <= b + tol) and np.all(muS >= -tol):
                mu = np.zeros(m)
                mu[list(S)] = muS
                return th, mu, lam
    raise RuntimeError("no KKT point found")


def kkt_residuals(H, c, th, mu, A, b, lam=None, Ceq=None):
    """Stationarity (8.104), primal feasibility (8.103), dual feasibility (8.105), complementary slackness
    (8.106), as maximum absolute violations."""
    stat = H @ th + c + A.T @ mu + (Ceq.T @ lam if Ceq is not None else 0)
    return dict(stationarity=float(np.abs(stat).max()), primal=float(max(0, (A @ th - b).max())),
                dual=float(max(0, -mu.min())), slackness=float(np.abs(mu * (A @ th - b)).max()))


def simplex(c, A, b, max_iter=100):
    """min c'x s.t. Ax <= b, x >= 0, with b >= 0 (the slack basis is feasible), by the tableau simplex
    method with Bland's rule. Returns x, the optimal value and the list of vertices visited."""
    A = np.asarray(A, float)
    b = np.asarray(b, float)
    c = np.asarray(c, float)
    m, n = A.shape
    T = np.zeros((m + 1, n + m + 1))
    T[:m, :n], T[:m, n:n + m], T[:m, -1] = A, np.eye(m), b
    T[m, :n] = c
    basis = list(range(n, n + m))

    def point():
        x = np.zeros(n + m)
        for i, j in enumerate(basis):
            x[j] = T[i, -1]
        return x[:n]

    visited = [point()]
    for _ in range(max_iter):
        cand = [j for j in range(n + m) if T[m, j] < -1e-12]
        if not cand:
            break
        j = min(cand)                                   # Bland: smallest entering index
        col = T[:m, j]
        ratios = [(T[i, -1] / col[i], basis[i], i) for i in range(m) if col[i] > 1e-12]
        if not ratios:
            raise RuntimeError("unbounded")
        _, _, i = min(ratios)
        T[i] /= T[i, j]
        for r in range(m + 1):
            if r != i:
                T[r] -= T[r, j] * T[i]
        basis[i] = j
        visited.append(point())
    x = point()
    return x, float(c @ x), np.array(visited)


# =========================================================================== Section 8.6: proximal methods
def proj_box(th, lo, hi):
    """(8.126)."""
    return np.minimum(np.maximum(th, lo), hi)


def proj_l1_ball(v, r=1.0):
    """Euclidean projection on {||t||_1 <= r} (sort-based algorithm of Duchi et al. 2008): soft
    thresholding at the level tau that makes the l1 norm equal r."""
    v = np.asarray(v, float)
    if np.abs(v).sum() <= r:
        return v.copy()
    u = np.sort(np.abs(v))[::-1]
    cs = np.cumsum(u)
    k = np.nonzero(u * np.arange(1, len(u) + 1) > (cs - r))[0][-1]
    tau = (cs[k] - r) / (k + 1)
    return np.sign(v) * np.maximum(np.abs(v) - tau, 0)


def soft_threshold(th, lam):
    """(8.134)-(8.135): sign(t) (|t| - lam)_+."""
    th = np.asarray(th, float)
    return np.sign(th) * np.maximum(np.abs(th) - lam, 0.0)


def prox_quant(th, lam):
    """(8.143): sign(t) + sign(t - sign(t)) (|t - sign(t)| - lam)_+, the prox of lam ||t - sign(t)||_1
    (with sign(0) = +1)."""
    th = np.asarray(th, float)
    s = np.where(th >= 0, 1.0, -1.0)
    r = th - s
    return s + np.sign(r) * np.maximum(np.abs(r) - lam, 0.0)


def prox_numeric(fun, th, eta=1.0, grid=np.linspace(-3, 3, 600001)):
    """argmin_z fun(z) + (z - th)^2 / (2 eta) on a fine grid (scalar th), for checking."""
    vals = fun(grid) + (grid - th) ** 2 / (2 * eta)
    return grid[np.argmin(vals)]


def demo_H(a, angle=np.pi / 6):
    """The Hessian of the KKT/proximal demo: H = 2 R diag(1, a) R' (a = 1 gives 2I, the book's example)."""
    return 2 * demo_quad_A(a, angle)


DEMO_SETS = {
    "l1": (np.array([[1.0, 1.0], [1.0, -1.0], [-1.0, 1.0], [-1.0, -1.0]]), "rows of (8.113)"),
    "box": (np.array([[1.0, 0.0], [0.0, 1.0], [-1.0, 0.0], [0.0, -1.0]]), "|t_i| <= r"),
}


def lasso2_exact(H, c, rho):
    """argmin 0.5 (t - c)'H(t - c) + rho ||t||_1 for H positive definite, by checking the optimality
    conditions 0 in H(t - c) + rho * subdifferential(||t||_1) on every support and sign pattern.
    Returns t and the subgradient element u (so that H(t - c) + rho u = 0)."""
    from itertools import product
    D = len(c)
    Hc = H @ c
    for pattern in product((0, 1, -1), repeat=D):
        F = [i for i in range(D) if pattern[i] != 0]
        t = np.zeros(D)
        if F:
            sgn = np.array([pattern[i] for i in F], float)
            t[F] = np.linalg.solve(H[np.ix_(F, F)], Hc[F] - rho * sgn)
            if np.any(np.sign(t[F]) != sgn):
                continue
        u = -(H @ (t - c)) / rho
        Z = [i for i in range(D) if pattern[i] == 0]
        if np.all(np.abs(u[Z]) <= 1 + 1e-12):
            return t, u
    raise RuntimeError("no solution found")


def demo_problem(mode, a, c, r):
    """Exact solution of the demo problem min 0.5 (t - c)'H(t - c) subject to the set of `mode`
    (l1 ball or box of radius r, the line t1 + t2 = r) or with the penalty r ||t||_1 (mode 'lasso').
    Returns theta, multipliers."""
    H = demo_H(a)
    c = np.asarray(c, float)
    if mode in DEMO_SETS:
        A = DEMO_SETS[mode][0]
        th, mu, _ = qp_kkt(H, -H @ c, A, r * np.ones(4))
        return th, mu
    if mode == "line":
        th, _, lam = qp_kkt(H, -H @ c, Ceq=np.array([[1.0, 1.0]]), d=np.array([r]))
        return th, lam
    return lasso2_exact(H, c, r)


def demo_pgd(mode, a, c, r, eta_scale, n, x0=(-1.5, 1.5)):
    """Projected (or, for 'lasso', proximal) gradient descent for the demo problem with step
    eta = eta_scale / lambda_max(H). Returns the n + 1 iterates."""
    H = demo_H(a)
    c = np.asarray(c, float)
    eta = eta_scale / np.linalg.eigvalsh(H)[-1]
    x = np.array(x0, float)
    P = [x.copy()]
    for _ in range(n):
        z = x - eta * H @ (x - c)
        if mode == "l1":
            x = proj_l1_ball(z, r)
        elif mode == "box":
            x = proj_box(z, -r, r)
        elif mode == "line":
            x = z - (z.sum() - r) / 2 * np.ones(2)
        else:
            x = soft_threshold(z, eta * r)
        P.append(x.copy())
    return np.array(P)


def lasso_obj(w, X, y, lam):
    return 0.5 * np.mean((X @ w - y) ** 2) + lam * np.abs(w).sum()


def ista(X, y, lam, n, fista=False):
    """Proximal gradient (8.119) for 0.5 mean (Xw - y)^2 + lam ||w||_1 with step 1/L, L = lambda_max(X'X/N);
    fista=True adds Nesterov's extrapolation (Beck and Teboulle 2009)."""
    N = len(y)
    L = np.linalg.eigvalsh(X.T @ X / N)[-1]
    w = np.zeros(X.shape[1])
    z, t = w.copy(), 1.0
    hist = [lasso_obj(w, X, y, lam)]
    for _ in range(n):
        p = z if fista else w
        wn = soft_threshold(p - X.T @ (X @ p - y) / N / L, lam / L)
        if fista:
            tn = 0.5 * (1 + np.sqrt(1 + 4 * t * t))
            z = wn + (t - 1) / tn * (wn - w)
            t = tn
        w = wn
        hist.append(lasso_obj(w, X, y, lam))
    return w, np.array(hist)


def subgradient_lasso(X, y, lam, n, a=0.05):
    """The subgradient method with steps a / sqrt(k + 1), reporting the best value so far."""
    N = len(y)
    w = np.zeros(X.shape[1])
    best = [lasso_obj(w, X, y, lam)]
    for k in range(n):
        g = X.T @ (X @ w - y) / N + lam * np.sign(w)
        w = w - a / np.sqrt(k + 1) * g
        best.append(min(best[-1], lasso_obj(w, X, y, lam)))
    return w, np.array(best)


# =========================================================================== Section 8.7: bound optimisation
def gmm_loglik(X, pis, mus, Sigmas):
    lp = np.column_stack([np.log(pis[k]) + common.gauss_logpdf(X, mus[k], Sigmas[k]) for k in range(len(pis))])
    return float(common.logsumexp(lp, axis=1).sum()), lp


def em_gmm(X, pis, mus, Sigmas, n_iter, prior=None, tol=None):
    """EM for a Gaussian mixture. E step (8.160); M step (8.165)-(8.167) for the MLE, or with
    prior=dict(alpha, S0, nu0) the MAP updates (8.170) and
        Sigma_k = (S0 + r_k Sigma_hat_k) / (nu0 + r_k + D + 2)
    (the book's (8.173) omits the factor r_k, see the notes). Returns the history of
    (pis, mus, Sigmas, responsibilities, log-likelihood). Raises np.linalg.LinAlgError when a covariance
    stops being positive definite."""
    X = np.asarray(X, float)
    N, D = X.shape
    pis, mus, Sigmas = np.array(pis, float), np.array(mus, float), np.array(Sigmas, float)
    K = len(pis)
    hist = []
    for it in range(n_iter + 1):
        ll, lp = gmm_loglik(X, pis, mus, Sigmas)
        R = np.exp(lp - common.logsumexp(lp, axis=1)[:, None])
        hist.append((pis.copy(), mus.copy(), Sigmas.copy(), R, ll))
        if it == n_iter or (tol is not None and it > 0 and ll - hist[-2][4] < tol):
            break
        rk = R.sum(0)
        if prior is None:
            pis = rk / N
        else:
            a = np.asarray(prior["alpha"], float)
            pis = (rk + a - 1) / (N + a.sum() - K)
        for k in range(K):
            mus[k] = R[:, k] @ X / rk[k]
            Z = X - mus[k]
            Shat = (R[:, k, None] * Z).T @ Z / rk[k]
            if prior is None:
                Sigmas[k] = Shat
            else:
                Sigmas[k] = (prior["S0"] + rk[k] * Shat) / (prior["nu0"] + rk[k] + D + 2)
            np.linalg.cholesky(Sigmas[k])
    return hist


def em_bound_1d(y, theta, theta_t, sigma=1.0):
    """For the symmetric 1-D mixture 0.5 N(-theta, s^2) + 0.5 N(theta, s^2), return the log-likelihood
    l(theta) and the EM lower bound Q(theta, theta_t) = sum_n sum_k r_nk log(p(y_n, z_n=k | theta)/r_nk),
    which touches l at theta_t (Section 8.7.2)."""
    def comp(th):
        return np.column_stack([np.log(0.5) + stats.norm.logpdf(y, -th, sigma),
                                np.log(0.5) + stats.norm.logpdf(y, th, sigma)])
    lt = comp(theta_t)
    R = np.exp(lt - common.logsumexp(lt, axis=1)[:, None])
    th = np.atleast_1d(theta)
    ll = np.array([common.logsumexp(comp(v), axis=1).sum() for v in th])
    Q = np.array([np.sum(R * (comp(v) - np.log(np.maximum(R, 1e-300)))) for v in th])
    return ll, Q, R


def em_step_1d(y, theta_t, sigma=1.0):
    """The M step for em_bound_1d: theta = sum_n (r_n2 - r_n1) y_n / N."""
    _, _, R = em_bound_1d(y, np.array([theta_t]), theta_t, sigma)
    return float(np.mean((R[:, 1] - R[:, 0]) * y))


def kde(x, data, h):
    """Gaussian kernel density estimate and its first two derivatives at x."""
    u = (np.atleast_1d(x)[:, None] - data[None, :]) / h
    phi = np.exp(-0.5 * u ** 2) / np.sqrt(2 * np.pi) / h
    p = phi.mean(1)
    dp = (-u / h * phi).mean(1)
    d2p = ((u ** 2 - 1) / h ** 2 * phi).mean(1)
    return p, dp, d2p


def mm_minorizer(x, x0, data, h):
    """The quadratic lower bound of the kernel density at x0 used by the mean-shift MM step: from the
    convexity of exp(-v/2) in v = ((x - x_i)/h)^2."""
    w = np.exp(-0.5 * ((x0 - data) / h) ** 2) / np.sqrt(2 * np.pi) / h / len(data)
    v0 = ((x0 - data) / h) ** 2
    xx = np.atleast_1d(x)[:, None]
    v = ((xx - data[None, :]) / h) ** 2
    return (w[None, :] * (1 - 0.5 * (v - v0[None, :]))).sum(1)


def mean_shift_step(x0, data, h):
    w = np.exp(-0.5 * ((x0 - data) / h) ** 2)
    return float(w @ data / w.sum())


def newton_step_max(x0, data, h):
    """The Newton step for a stationary point of the density: x0 - p'(x0) / p''(x0)."""
    _, dp, d2p = kde(x0, data, h)
    return float(x0 - dp[0] / d2p[0])


def mvt_logpdf(X, mu, Sigma, nu):
    D = X.shape[1]
    L = np.linalg.cholesky(Sigma)
    Z = np.linalg.solve(L, (X - mu).T)
    delta = (Z ** 2).sum(0)
    from scipy.special import gammaln
    return (gammaln((nu + D) / 2) - gammaln(nu / 2) - 0.5 * D * np.log(nu * np.pi)
            - np.log(np.diag(L)).sum() - 0.5 * (nu + D) * np.log1p(delta / nu))


def em_student(X, nu=4.0, n_iter=100, estimate_nu=False):
    """Exercise 8.2: EM for the multivariate Student distribution as a scale mixture of Gaussians,
    x | z ~ N(mu, Sigma / z), z ~ Gamma(nu/2, rate nu/2). E step: E[z_n] = (nu + D) / (nu + delta_n);
    M step: mu = sum w_n x_n / sum w_n, Sigma = (1/N) sum w_n (x_n - mu)(x_n - mu)'. With estimate_nu
    the degrees of freedom solve the one-dimensional equation of the ECM step (Liu and Rubin 1995).
    Returns mu, Sigma, nu and the log-likelihood after each iteration."""
    from scipy.optimize import brentq
    from scipy.special import digamma
    X = np.asarray(X, float)
    N, D = X.shape
    mu = X.mean(0)
    Sigma = np.cov(X.T, bias=True)
    lls = [mvt_logpdf(X, mu, Sigma, nu).sum()]
    for _ in range(n_iter):
        L = np.linalg.cholesky(Sigma)
        Z = np.linalg.solve(L, (X - mu).T)
        delta = (Z ** 2).sum(0)
        w = (nu + D) / (nu + delta)                                  # E[z_n | x_n]
        Elogz = digamma((nu + D) / 2) - np.log((nu + delta) / 2)      # E[log z_n | x_n]
        mu = w @ X / w.sum()
        C = X - mu
        Sigma = (w[:, None] * C).T @ C / N
        if estimate_nu:
            const = 1 + np.mean(Elogz - w)

            def eq(v):
                return np.log(v / 2) - digamma(v / 2) + const
            nu = brentq(eq, 1e-3, 1e4) if eq(1e-3) * eq(1e4) < 0 else 1e4
        lls.append(mvt_logpdf(X, mu, Sigma, nu).sum())
    return mu, Sigma, nu, np.array(lls)


# =========================================================================== helpers for plots
def _contour(ax, f, xr, yr, levels=30, n=300, logspace=False, cmap="viridis", lw=0.7):
    xs = np.linspace(*xr, n)
    ys = np.linspace(*yr, n)
    XX, YY = np.meshgrid(xs, ys)
    Z = f(np.stack([XX, YY]))
    if logspace:
        zmin = Z.min()
        lv = zmin + np.geomspace(1e-3, Z.max() - zmin, levels)
        ax.contour(XX, YY, Z, levels=lv, cmap=cmap, linewidths=lw)
    else:
        ax.contour(XX, YY, Z, levels=levels, cmap=cmap, linewidths=lw)
    ax.set_xlim(xr)
    ax.set_ylim(yr)


def _path(ax, P, color=RED, label=None, ms=3.5, lw=1.2):
    ax.plot(P[:, 0], P[:, 1], "-o", color=color, ms=ms, lw=lw, label=label, mfc=color, mec="white", mew=0.4)


# =========================================================================== figures: Section 8.1
def fig_8_1(out=None):
    """Local and global minima in 1-D; a saddle point in 2-D."""
    fig = plt.figure(figsize=(8.0, 3.2))
    ax = fig.add_subplot(1, 2, 1)
    x = np.linspace(-1.6, 1.6, 801)
    f = tilted_double_well(x)
    ax.plot(x, f, color=BLUE)
    from scipy.optimize import minimize_scalar
    gl = minimize_scalar(tilted_double_well, bounds=(-1.6, 0), method="bounded").x
    lo = minimize_scalar(tilted_double_well, bounds=(0, 1.6), method="bounded").x
    ax.plot([gl], [tilted_double_well(gl)], "o", color=RED)
    ax.plot([lo], [tilted_double_well(lo)], "o", color=ORANGE)
    ax.annotate("global minimum", xy=(gl, tilted_double_well(gl)), xytext=(-1.4, 1.6),
                arrowprops=dict(arrowstyle="->", color="k"), fontsize=9)
    ax.annotate("local minimum", xy=(lo, tilted_double_well(lo)), xytext=(0.15, 2.2),
                arrowprops=dict(arrowstyle="->", color="k"), fontsize=9)
    ax.set_xlabel(r"$\theta$")
    ax.set_ylabel(r"$\mathcal{L}(\theta)$")
    ax.set_ylim(-0.8, 3.2)
    common.panel_label(ax, "a")
    ax3 = fig.add_subplot(1, 2, 2, projection="3d")
    g = np.linspace(-2, 2, 41)
    XX, YY = np.meshgrid(g, g)
    ax3.plot_surface(XX, YY, XX ** 2 - YY ** 2, cmap="coolwarm", linewidth=0, alpha=0.85, rstride=1, cstride=1)
    ax3.scatter([0], [0], [0], color="k", s=25)
    ax3.text(0.2, 0.2, 0.8, "saddle point", fontsize=9)
    ax3.set_xlabel(r"$\theta_1$")
    ax3.set_ylabel(r"$\theta_2$")
    ax3.set_zlabel(r"$\theta_1^2-\theta_2^2$")
    ax3.view_init(28, -60)
    ax3.text2D(0.02, 0.92, "(b)", transform=ax3.transAxes)
    fig.tight_layout()
    savefig(fig, CH, "fig8-1", out)


def _f82(x):
    return 0.6 * np.sin(2 * x) + 0.12 * x ** 2


def fig_8_2(out=None):
    """Constrained maximisation of a non-convex 1-D function on three feasible sets."""
    from scipy.optimize import brentq, minimize_scalar
    x = np.linspace(-4, 4, 1601)
    fig, axes = plt.subplots(1, 3, figsize=(9.0, 2.7), sharey=True)
    # (a) a feasible interval around a local maximum where f is concave
    a = (0.1, 1.4)
    # (b) an interval around the local minimum near 2.1 with equal heights at both ends
    xm = minimize_scalar(_f82, bounds=(1.6, 2.6), method="bounded").x
    lft = 1.45
    rgt = brentq(lambda t: _f82(t) - _f82(lft), xm, 3.0)
    for ax, iv, title in ((axes[0], a, "unique global maximum"), (axes[1], (lft, rgt), "two global maxima"),
                          (axes[2], None, "no global maximum")):
        ax.plot(x, _f82(x), color=BLUE)
        if iv is not None:
            for v in iv:
                ax.axvline(v, color="k", ls=":", lw=1)
            xi = np.linspace(iv[0], iv[1], 2001)
            fi = _f82(xi)
            best = fi.max()
            arg = xi[np.abs(fi - best) < 1e-6 * max(1, abs(best))]
            pts = [arg[0]] if iv is a else [iv[0], iv[1]]
            ax.plot(pts, _f82(np.array(pts)), "o", color=RED)
            ax.axvspan(iv[0], iv[1], color=GREY, alpha=0.12)
        ax.set_title(title)
        ax.set_xlabel(r"$\theta$")
    axes[0].set_ylabel(r"$f(\theta)$")
    for ax, l in zip(axes, "abc"):
        common.panel_label(ax, l)
    fig.tight_layout()
    savefig(fig, CH, "fig8-2", out)


def fig_8_4(out=None):
    """(a) The epigraph of a convex function. (b) A convex function as the supremum of the lines
    lam x - f*(lam) (here f = x^2, f*(lam) = lam^2 / 4)."""
    fig, axes = plt.subplots(1, 2, figsize=(7.4, 3.0))
    x = np.linspace(-2, 2, 401)
    f = 0.5 * x ** 2 + 0.3 * x + 0.2
    ax = axes[0]
    ax.fill_between(x, f, 3.2, color=GREEN, alpha=0.35, label="epigraph")
    ax.plot(x, f, color="k")
    ax.text(-0.5, 2.3, r"epi $f$", fontsize=11)
    ax.set_ylim(-0.2, 3.2)
    ax.set_xlabel("$x$")
    ax.set_ylabel("$f(x)$")
    common.panel_label(ax, "a", "upper right")
    ax = axes[1]
    ax.plot(x, x ** 2, color=BLUE, lw=2.2, label=r"$f(x)=x^2$")
    for lam in np.linspace(-3, 3, 7):
        ax.plot(x, lam * x - lam ** 2 / 4, color=RED, lw=0.9)
    ax.plot([], [], color=RED, lw=0.9, label=r"$\lambda x - f^*(\lambda)$")
    ax.set_ylim(-1.5, 4)
    ax.set_xlabel("$x$")
    ax.legend(loc="upper center", fontsize=8)
    common.panel_label(ax, "b", "upper left")
    fig.tight_layout()
    savefig(fig, CH, "fig8-4", out)


def fig_8_5(out=None):
    """(a) A chord of a convex function lies above it. (b) A function with a local minimum A and a global
    minimum B, neither convex nor concave."""
    fig, axes = plt.subplots(1, 2, figsize=(7.4, 3.0))
    x = np.linspace(-1.5, 2.5, 401)
    f = lambda t: 0.6 * t ** 2 - 0.4 * t + 0.3  # noqa: E731
    ax = axes[0]
    ax.plot(x, f(x), color=BLUE)
    xa, xb, lam = -1.0, 2.0, 0.35
    ax.plot([xa, xb], [f(xa), f(xb)], color=RED)
    xm = lam * xa + (1 - lam) * xb
    ax.plot([xm, xm], [f(xm), lam * f(xa) + (1 - lam) * f(xb)], "k:", lw=1)
    ax.plot([xa, xb, xm, xm], [f(xa), f(xb), f(xm), lam * f(xa) + (1 - lam) * f(xb)], "o", color="k", ms=3.5)
    ax.text(xa, f(xa) + 0.25, "$x$", ha="center")
    ax.text(xb, f(xb) + 0.25, "$y$", ha="center")
    ax.text(xm + 0.05, 0.5 * (f(xm) + lam * f(xa) + (1 - lam) * f(xb)), r"$\lambda x+(1-\lambda)y$", fontsize=8)
    ax.set_xlabel("$x$")
    common.panel_label(ax, "a", "upper center")
    ax = axes[1]
    g = lambda t: 0.5 * (t ** 2 - 1) ** 2 - 0.25 * t  # noqa: E731
    x = np.linspace(-1.7, 1.8, 401)
    ax.plot(x, g(x), color=BLUE)
    from scipy.optimize import minimize_scalar
    A = minimize_scalar(g, bounds=(-1.7, 0), method="bounded").x
    B = minimize_scalar(g, bounds=(0, 1.8), method="bounded").x
    ax.plot([A, B], [g(A), g(B)], "o", color=RED)
    ax.text(A, g(A) - 0.25, "A", ha="center")
    ax.text(B, g(B) - 0.25, "B", ha="center")
    ax.set_ylim(-0.7, 1.6)
    ax.set_xlabel("$x$")
    common.panel_label(ax, "b", "upper center")
    fig.tight_layout()
    savefig(fig, CH, "fig8-5", out)


def fig_8_6(out=None):
    """The quadratic form x'Ax for positive definite, negative definite, singular positive semidefinite
    and indefinite A."""
    mats = [("positive definite", np.array([[2.0, 0.5], [0.5, 1.0]])),
            ("negative definite", -np.array([[2.0, 0.5], [0.5, 1.0]])),
            ("positive semidefinite, singular", np.array([[1.0, 1.0], [1.0, 1.0]])),
            ("indefinite", np.array([[1.0, 0.0], [0.0, -1.0]]))]
    g = np.linspace(-1, 1, 31)
    XX, YY = np.meshgrid(g, g)
    fig = plt.figure(figsize=(7.2, 6.2))
    for k, (name, A) in enumerate(mats):
        ax = fig.add_subplot(2, 2, k + 1, projection="3d")
        Z = A[0, 0] * XX ** 2 + 2 * A[0, 1] * XX * YY + A[1, 1] * YY ** 2
        ax.plot_wireframe(XX, YY, Z, color="k", linewidth=0.35, rstride=2, cstride=2)
        ax.set_title("(%s) %s" % ("abcd"[k], name), fontsize=9.5)
        ax.set_xlabel("$x_1$")
        ax.set_ylabel("$x_2$")
        ax.set_zticks([])
        ax.view_init(25, -55)
    fig.tight_layout()
    savefig(fig, CH, "fig8-6", out)


def fig_8_7(out=None):
    """A smooth and a non-smooth function on [-1, 1]."""
    x = np.linspace(-1, 1, 801)
    fig, axes = plt.subplots(1, 2, figsize=(7.0, 2.7), sharey=True)
    axes[0].plot(x, 0.8 * x ** 2 + 0.05, color=BLUE)
    axes[0].set_title("smooth function")
    axes[1].plot(x, np.abs(x), color=BLUE)
    axes[1].set_title("non-smooth function (kink at 0)")
    for ax, l in zip(axes, "ab"):
        ax.set_xlabel("$x$")
        common.panel_label(ax, l, "upper center")
    fig.tight_layout()
    savefig(fig, CH, "fig8-7", out)


def _f88(x):
    return 0.5 * np.sin(2 * x) + 0.3 * x


def fig_8_8(out=None):
    """A Lipschitz function (L = 1.3) stays outside the double cone |y - f(x0)| > L |x - x0| wherever the
    cone is placed on its graph."""
    L = 1.3
    x = np.linspace(-3, 3, 1201)
    fig, axes = plt.subplots(1, 2, figsize=(7.4, 3.0), sharey=True)
    for ax, x0, l in ((axes[0], -0.6, "a"), (axes[1], 1.4, "b")):
        y0 = _f88(x0)
        up = y0 + L * np.abs(x - x0)
        dn = y0 - L * np.abs(x - x0)
        ax.fill_between(x, up, 4, color=RED, alpha=0.12)
        ax.fill_between(x, -4, dn, color=RED, alpha=0.12)
        ax.plot(x, up, color=RED, lw=0.8)
        ax.plot(x, dn, color=RED, lw=0.8)
        ax.plot(x, _f88(x), color=BLUE, lw=1.8)
        ax.plot([x0], [y0], "ko", ms=4)
        ax.set_ylim(-3, 3)
        ax.set_xlim(-3, 3)
        ax.set_xlabel("$x$")
        common.panel_label(ax, l)
    axes[0].set_ylabel("$f(x)$")
    fig.tight_layout()
    savefig(fig, CH, "fig8-8", out)


def fig_8_9(out=None):
    """Subgradients of f(x) = max(x^2 / 2, 2x - 1.5): the tangent at a smooth point x1 and two of the
    supporting lines at the kink x2 = 1 (slopes 1.2 and 1.8 in the subdifferential [1, 2])."""
    f = lambda t: np.maximum(0.5 * t ** 2, 2 * t - 1.5)  # noqa: E731
    x = np.linspace(-1.5, 2.6, 601)
    fig, ax = plt.subplots(figsize=(4.6, 3.2))
    ax.plot(x, f(x), color="k", lw=1.8, label="$f(x)$")
    x1, x2 = -0.8, 1.0
    ax.plot(x, f(x1) + x1 * (x - x1), color=BLUE, ls="--", lw=1, label=r"$f(x_1)+g_1(x-x_1)$, $g_1=f'(x_1)$")
    for gval, ls in ((1.2, "-."), (1.8, ":")):
        ax.plot(x, f(x2) + gval * (x - x2), color=RED, ls=ls, lw=1.2, label=r"$f(x_2)+g(x-x_2)$, $g=%.1f$" % gval)
    ax.plot([x1, x2], [f(x1), f(x2)], "ko", ms=4)
    ax.text(x1, f(x1) - 0.45, "$x_1$", ha="center")
    ax.text(x2 + 0.05, f(x2) - 0.45, "$x_2$", ha="center")
    ax.set_ylim(-1.5, 3.2)
    ax.legend(fontsize=7.5, loc="upper left")
    ax.set_xlabel("$x$")
    fig.tight_layout()
    savefig(fig, CH, "fig8-9", out)


def fig_8_10(out=None):
    """|x| and its subdifferential (8.14)."""
    fig, axes = plt.subplots(1, 2, figsize=(7.0, 2.7))
    x = np.linspace(-1.5, 1.5, 301)
    axes[0].plot(x, np.abs(x), color="k")
    axes[0].set_title(r"$f(x)=|x|$")
    axes[1].plot([-1.5, 0], [-1, -1], color="k", lw=2)
    axes[1].plot([0, 1.5], [1, 1], color="k", lw=2)
    axes[1].plot([0, 0], [-1, 1], color="k", lw=2)
    axes[1].set_ylim(-1.6, 1.6)
    axes[1].set_title(r"$\partial f(x)$")
    for ax in axes:
        ax.axhline(0, color=GREY, lw=0.6)
        ax.axvline(0, color=GREY, lw=0.6)
        ax.set_xlabel("$x$")
    fig.tight_layout()
    savefig(fig, CH, "fig8-10", out)


# =========================================================================== figures: Section 8.2
def fig_8_11(out=None):
    """Steepest descent with a constant step on (8.19), 20 steps from (0, 0)."""
    fig, axes = plt.subplots(1, 2, figsize=(7.6, 3.3))
    for ax, eta, l in ((axes[0], 0.1, "a"), (axes[1], 0.6, "b")):
        _contour(ax, valley, (0, 2), (-0.5, 2.5), levels=25, logspace=True)
        P = gd(valley_grad, [0.0, 0.0], eta, 20)
        _path(ax, P)
        ax.plot([1], [1], "*", color=GREEN, ms=11)
        ax.set_title(r"step size $\eta=%.1f$" % eta)
        ax.set_xlabel(r"$\theta_1$")
        common.panel_label(ax, l, "lower right")
    axes[0].set_ylabel(r"$\theta_2$")
    fig.tight_layout()
    savefig(fig, CH, "fig8-11", out)


A_BIG = np.array([[20.0, 5.0], [5.0, 2.0]])
A_SMALL = np.array([[20.0, 5.0], [5.0, 16.0]])
B_QUAD = np.array([-14.0, -6.0])


def worst_start(A, box=1.9):
    """A start for which exact-line-search steepest descent on t'At + b't attains the rate (8.29) at every
    step: the gradient at the start has equal components on the two eigenvectors of A (the Kantorovich
    worst case), scaled to lie in the plotting box."""
    H = 2 * A
    xs = -np.linalg.solve(H, B_QUAD)
    ev, V = np.linalg.eigh(H)
    best = None
    for sgn in (1, -1):
        e = np.linalg.solve(H, V[:, 0] + sgn * V[:, 1])
        for direction in (1, -1):
            # largest s with xs + s*direction*e inside the box
            u = direction * e
            smax = min([(box - xs[i]) / u[i] if u[i] > 0 else (-box - xs[i]) / u[i] for i in range(2) if u[i] != 0])
            cand = xs + smax * u
            if best is None or np.linalg.norm(cand - xs) > np.linalg.norm(best - xs):
                best = cand
    return best


X0_QUAD = None  # set below by worst_start(A_BIG)


def quad_book(A):
    """The figure's quadratic f(t) = t'At + b't + c (Hessian 2A; same condition number as A)."""
    return quad_fns(2 * A, B_QUAD, 10.0)


X0_QUAD = worst_start(A_BIG)


def fig_8_12(out=None):
    """Steepest descent with exact line search on t'At + b't + c for a badly and a well conditioned A."""
    fig, axes = plt.subplots(1, 2, figsize=(7.6, 3.4))
    for ax, A, l in ((axes[0], A_BIG, "a"), (axes[1], A_SMALL, "b")):
        f, _, _ = quad_book(A)
        _contour(ax, lambda T: np.einsum("i...,ij,j...->...", T, A, T) + np.einsum("i,i...->...", B_QUAD, T) + 10,
                 (-2, 2), (-2, 2), levels=30)
        P = gd_exact_quadratic(2 * A, B_QUAD, X0_QUAD, 20)
        _path(ax, P)
        ax.set_title(r"condition number of A = %.3f" % np.linalg.cond(A))
        ax.set_xlabel(r"$\theta_1$")
        common.panel_label(ax, l, "lower right")
    axes[0].set_ylabel(r"$\theta_2$")
    fig.tight_layout()
    savefig(fig, CH, "fig8-12", out)


def fig_8_S1(out=None):
    """Suboptimality of steepest descent with exact line search against the bound (8.29)."""
    fig, ax = plt.subplots(figsize=(4.8, 3.3))
    for A, col, name in ((A_BIG, RED, "a"), (A_SMALL, BLUE, "b")):
        f, _, _ = quad_book(A)
        xs = -np.linalg.solve(2 * A, B_QUAD)
        P = gd_exact_quadratic(2 * A, B_QUAD, X0_QUAD, 60)
        gap = np.array([f(p) - f(xs) for p in P])
        gap = gap[gap > 1e-15]
        mu = kantorovich_rate(A)
        t = np.arange(len(gap))
        ax.semilogy(t, gap, "o-", color=col, ms=3, label=r"$\kappa=%.2f$" % np.linalg.cond(A))
        ax.semilogy(t, gap[0] * mu ** t, "--", color=col, lw=1, label=r"bound $\mu^t$, $\mu=%.3f$" % mu)
    ax.set_xlabel("iteration $t$")
    ax.set_ylabel(r"$\mathcal{L}(\theta_t)-\mathcal{L}(\theta^*)$")
    ax.set_ylim(1e-14, 1e3)
    ax.set_xlim(0, 60)
    ax.legend(fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig8-S1", out)


def fig_8_S2(out=None):
    """Gradient descent, heavy ball and Nesterov on a quadratic with condition number 100, each with the
    tuned parameters, and (dashed) the theoretical rates for the distance to the optimum: (kappa-1)/(kappa+1),
    (sqrt(kappa)-1)/(sqrt(kappa)+1) and the guarantee (1 - 1/sqrt(kappa))^(t/2) of Nesterov's method."""
    lmin, lmax = 1.0, 100.0
    A = np.diag([lmin, lmax])
    grad = lambda t: A @ t  # noqa: E731
    x0 = np.array([1.0, 1.0])
    n = 150
    k = lmax / lmin
    runs = [("gradient descent, $\\eta=2/(L+m)$", gd(grad, x0, 2 / (lmin + lmax), n), (k - 1) / (k + 1), GREY),
            ("heavy ball (Polyak)", heavy_ball(grad, x0, 4 / (np.sqrt(lmax) + np.sqrt(lmin)) ** 2,
                                              ((np.sqrt(k) - 1) / (np.sqrt(k) + 1)) ** 2, n),
             (np.sqrt(k) - 1) / (np.sqrt(k) + 1), RED),
            ("Nesterov, $\\eta=1/L$", nesterov(grad, x0, 1 / lmax, (np.sqrt(k) - 1) / (np.sqrt(k) + 1), n),
             np.sqrt(1 - 1 / np.sqrt(k)), BLUE)]
    fig, ax = plt.subplots(figsize=(5.0, 3.3))
    for name, P, rate, col in runs:
        err = np.linalg.norm(P, axis=1)
        ax.semilogy(err, color=col, label=name)
        ax.semilogy(err[0] * rate ** np.arange(n + 1), ls="--", color=col, lw=0.8)
    ax.set_xlabel("iteration $t$")
    ax.set_ylabel(r"$\|\theta_t-\theta^*\|$")
    ax.set_ylim(1e-12, 10)
    ax.legend(fontsize=7.5)
    fig.tight_layout()
    savefig(fig, CH, "fig8-S2", out)


# =========================================================================== figures: Section 8.3
def _L814a(t):
    return np.log1p(np.exp(2 * t)) - 1.2 * t + 0.08 * t ** 2


def fig_8_14(out=None):
    """(a) One Newton step on a convex function: the quadratic model at theta_t and its minimiser. (b)
    On a non-convex function, where L'' < 0, the Newton step goes to a maximum of the model, towards a
    local maximum of L."""
    fig, axes = plt.subplots(1, 2, figsize=(7.6, 3.1))
    ax = axes[0]
    t = np.linspace(-3, 3, 601)
    f = _L814a
    df = lambda s: 2 * common.sigmoid(2 * s) - 1.2 + 0.16 * s  # noqa: E731
    d2f = lambda s: 4 * common.sigmoid(2 * s) * (1 - common.sigmoid(2 * s)) + 0.16  # noqa: E731
    tt = -1.0
    q = f(tt) + df(tt) * (t - tt) + 0.5 * d2f(tt) * (t - tt) ** 2
    tn = tt - df(tt) / d2f(tt)
    ax.plot(t, f(t), color=RED, label=r"$\mathcal{L}(\theta)$")
    ax.plot(t, q, "--", color=BLUE, label=r"$\mathcal{L}_{\rm quad}(\theta)$")
    for v, lab in ((tt, r"$\theta_t$"), (tn, r"$\theta_t+d_t$")):
        ax.axvline(v, color="k", ls=":", lw=0.8)
        ax.text(v, -0.15, lab, ha="center", va="top", transform=ax.get_xaxis_transform(), fontsize=9)
    ax.plot([tt, tn], [f(tt), f(tn)], "ko", ms=3.5)
    ax.set_ylim(-0.5, 4)
    ax.legend(fontsize=8)
    common.panel_label(ax, "a", "upper center")
    ax = axes[1]
    t = np.linspace(-4, 13, 801)
    g = lambda s: (s ** 3 - 15 * s ** 2) / 100  # noqa: E731
    dg = lambda s: (3 * s ** 2 - 30 * s) / 100  # noqa: E731
    d2g = lambda s: (6 * s - 30) / 100  # noqa: E731
    tt = 2.0
    q = g(tt) + dg(tt) * (t - tt) + 0.5 * d2g(tt) * (t - tt) ** 2
    tn = tt - dg(tt) / d2g(tt)
    ax.plot(t, g(t), color=RED)
    ax.plot(t, q, "--", color=BLUE)
    for v, lab in ((tt, r"$\theta_t$"), (tn, r"$\theta_{t+1}$")):
        ax.axvline(v, color="k", ls=":", lw=0.8)
        ax.text(v, -0.15, lab, ha="center", va="top", transform=ax.get_xaxis_transform(), fontsize=9)
    ax.plot([tt, tn], [g(tt), g(tn)], "ko", ms=3.5)
    ax.set_ylim(-6, 2)
    common.panel_label(ax, "b", "upper right")
    for ax in axes:
        ax.set_xticks([])
    fig.tight_layout()
    savefig(fig, CH, "fig8-14", out)


def fig_8_15(out=None):
    """A trust-region method on the non-convex saddle_fn from (0.05, 1.6), where the Hessian is indefinite:
    each circle is the trust region of one step and each step solves (8.49) exactly in it."""
    P, radii = trust_region(saddle_fn, saddle_grad, saddle_hess, [0.05, 1.6], 12, r0=0.5, rmax=0.5)
    Pn = newton(saddle_grad, saddle_hess, [0.05, 1.6], 8)
    fig, ax = plt.subplots(figsize=(4.8, 4.2))
    _contour(ax, saddle_fn, (-1.8, 1.8), (-1.2, 2.0), levels=30, logspace=True, cmap="Greys")
    for p, r in zip(P[:-1], radii):
        ax.add_patch(plt.Circle(p, r, fill=True, color=BLUE, alpha=0.06))
        ax.add_patch(plt.Circle(p, r, fill=False, color=BLUE, lw=0.7))
    _path(ax, P, color=BLUE, label="trust region")
    _path(ax, Pn, color=RED, label="pure Newton", ms=3)
    ax.set_aspect("equal")
    ax.set_xlabel(r"$\theta_1$")
    ax.set_ylabel(r"$\theta_2$")
    ax.legend(fontsize=8, loc="upper right")
    fig.tight_layout()
    savefig(fig, CH, "fig8-15", out)


# =========================================================================== figures: Section 8.4
def fig_8_16(out=None):
    """The LMS algorithm (8.60) on 21 simulated points, from (-0.5, 2), 30 steps."""
    X, y = lms_data()
    w_ls = np.linalg.lstsq(X, y, rcond=None)[0]
    P, rss = lms(X, y, [-0.5, 2.0], 30)
    fig, axes = plt.subplots(1, 2, figsize=(7.8, 3.3))
    ax = axes[0]
    _contour(ax, lambda T: np.mean((X @ T.reshape(2, -1) - y[:, None]) ** 2, axis=0).reshape(T.shape[1:]),
             (-1, 3), (-1, 2.6), levels=12)
    ax.plot(P[:, 0], P[:, 1], "-o", color="k", ms=3, lw=1)
    ax.plot(*w_ls, "x", color=RED, ms=10, mew=2.5)
    ax.set_title("LMS trajectory")
    ax.set_xlabel(r"$\theta_0$ (intercept)")
    ax.set_ylabel(r"$\theta_1$ (slope)")
    common.panel_label(ax, "a", "lower right")
    ax = axes[1]
    ax.plot(rss, "-o", color="k", ms=3)
    ax.axhline(np.mean((X @ w_ls - y) ** 2), color=RED, ls="--", lw=1)
    ax.set_title("mean squared error against iteration")
    ax.set_xlabel("iteration")
    common.panel_label(ax, "b", "upper right")
    fig.tight_layout()
    savefig(fig, CH, "fig8-16", out)


def lr_range_test(n_train=5000, batch=50, lr_min=1e-5, lr_max=10.0, seed=0):
    """Train a 784-128-10 ReLU network with plain SGD for 2 epochs (200 minibatches of 50) while the
    learning rate grows geometrically from lr_min to lr_max; return the learning rates and losses."""
    cache = os.path.join(HERE, "cache", "ch08_lr_range.npz")
    if os.path.exists(cache):
        z = np.load(cache)
        return z["lrs"], z["losses"]
    torch = common.torch_setup(seed)
    X, y = common.mnist(train=True)
    rng = np.random.default_rng(seed)
    idx = rng.choice(len(y), n_train, replace=False)
    X = torch.tensor(X[idx], dtype=torch.float32)
    y = torch.tensor(y[idx])
    net = torch.nn.Sequential(torch.nn.Linear(784, 128), torch.nn.ReLU(), torch.nn.Linear(128, 10))
    opt = torch.optim.SGD(net.parameters(), lr=lr_min)
    steps = 2 * n_train // batch
    lrs = np.geomspace(lr_min, lr_max, steps)
    losses = []
    for s in range(steps):
        if s % (n_train // batch) == 0:
            perm = torch.randperm(n_train)
        b = perm[(s % (n_train // batch)) * batch:((s % (n_train // batch)) + 1) * batch]
        for gparam in opt.param_groups:
            gparam["lr"] = float(lrs[s])
        loss = torch.nn.functional.cross_entropy(net(X[b]), y[b])
        opt.zero_grad()
        loss.backward()
        opt.step()
        losses.append(float(loss) if np.isfinite(float(loss)) else np.nan)
    losses = np.array(losses)
    os.makedirs(os.path.dirname(cache), exist_ok=True)
    np.savez(cache, lrs=lrs, losses=losses)
    return lrs, losses


def fig_8_17(out=None):
    """Training loss against the learning rate in a learning-rate range test (MNIST subset, small MLP)."""
    lrs, losses = lr_range_test()
    beta, m, smooth = 0.9, 0.0, []
    for t, v in enumerate(np.nan_to_num(losses, nan=np.nanmax(losses)), start=1):
        m = beta * m + (1 - beta) * min(v, 15)
        smooth.append(m / (1 - beta ** t))
    fig, ax = plt.subplots(figsize=(5.0, 3.2))
    ax.semilogx(lrs, np.minimum(losses, 15), color=BLUE, lw=1, label="raw loss")
    ax.semilogx(lrs, smooth, color=ORANGE, lw=1.6, label="EWMA, bias corrected")
    ax.set_xlabel("learning rate")
    ax.set_ylabel("training loss")
    ax.set_ylim(0, 15)
    ax.legend(fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig8-17", out)


def fig_8_18(out=None):
    """Piecewise constant, exponential and polynomial learning-rate schedules (8.62)-(8.64)."""
    t = np.arange(100)
    fig, axes = plt.subplots(1, 3, figsize=(9.0, 2.6))
    axes[0].step(t, sched_piecewise(t), where="post", color=BLUE)
    axes[0].set_title(r"piecewise constant, $\gamma=0.9$")
    axes[1].plot(t, sched_exp(t), color=BLUE)
    axes[1].set_title(r"exponential, $\lambda=0.1$")
    axes[2].plot(t, sched_poly(t), color=BLUE)
    axes[2].set_title(r"polynomial, $\alpha=0.5,\ \beta=1$")
    for ax, l in zip(axes, "abc"):
        ax.set_xlabel("$t$")
        common.panel_label(ax, l, "upper right")
    axes[0].set_ylabel(r"$\eta_t$")
    fig.tight_layout()
    savefig(fig, CH, "fig8-18", out)


def fig_8_19(out=None):
    """(a) Linear warm-up then cosine decay. (b) A triangular cyclical schedule with decaying maximum."""
    fig, axes = plt.subplots(1, 2, figsize=(7.6, 2.7))
    t = np.linspace(0, 30, 601)
    axes[0].plot(t, sched_warmup_cosine(t), color=BLUE)
    axes[0].set_xlabel("epoch")
    axes[0].set_ylabel(r"$\eta_t$")
    t = np.arange(0, 100)
    axes[1].plot(t, sched_cyclic(t), color=BLUE)
    axes[1].set_xlabel("iteration")
    for ax, l in zip(axes, "ab"):
        common.panel_label(ax, l, "upper right")
    fig.tight_layout()
    savefig(fig, CH, "fig8-19", out)


SGD_EPOCHS = 30
SGD_RUNS = [  # (label, method, eta, schedule, decay)
    ("SGD, constant step 0.1", "sgd", 0.1, "constant", 0.0),
    ("SGD, step 0.5/(1 + k/100)", "sgd", 0.5, "inv", 1 / 100),
    ("SGD (step 0.1) + iterate averaging", "avg", 0.1, "constant", 0.0),
    ("SVRG, step 0.2", "svrg", 0.2, "constant", 0.0),
    ("SAGA, step 0.2", "saga", 0.2, "constant", 0.0),
    ("full-batch GD, step 4", "gd", 4.0, "constant", 0.0),
]


def sgd_comparison(seed=1):
    X, y = bc_data()
    w_star = logreg_opt(X, y)
    Ls = logreg_loss(w_star, X, y)
    res = {}
    for lab, meth, eta, sch, dec in SGD_RUNS:
        curve, w = run_stochastic(meth, X, y, [0.0, 0.0], SGD_EPOCHS, eta, seed=seed, schedule=sch, decay=dec)
        res[lab] = (curve - Ls, w)
    return res, w_star, Ls


def fig_8_S3(out=None):
    """Suboptimality against passes through the data for SGD (constant and decaying step), SGD with
    iterate averaging, SVRG, SAGA and full-batch gradient descent, on L2-regularised logistic regression."""
    res, _, _ = sgd_comparison()
    cols = [GREY, ORANGE, PURPLE, RED, BLUE, GREEN]
    fig, ax = plt.subplots(figsize=(5.4, 3.5))
    for (lab, *_), col in zip(SGD_RUNS, cols):
        ax.semilogy(np.maximum(res[lab][0], 1e-16), color=col, label=lab)
    ax.set_xlabel("epochs (passes through the 569 examples)")
    ax.set_ylabel(r"$\mathcal{L}(\theta)-\mathcal{L}(\theta^*)$")
    ax.set_ylim(1e-15, 1)
    ax.legend(fontsize=7.5, loc="lower left")
    fig.tight_layout()
    savefig(fig, CH, "fig8-S3", out)


def fig_8_S4(out=None):
    """The online problem of Reddi et al. (2018): Adam (beta1 = 0, beta2 = 1/(1 + C^2)) drifts to the worst
    point x = 1; SGD, AMSGrad, Yogi and ADOPT reach the optimum x = -1."""
    T = 30000
    fig, ax = plt.subplots(figsize=(5.2, 3.3))
    for meth, col in (("adam", RED), ("amsgrad", BLUE), ("yogi", ORANGE), ("adopt", PURPLE), ("sgd", GREY)):
        xs = reddi_online(meth, T=T)
        ax.plot(np.arange(1, T + 1), xs, color=col, label=meth.upper() if meth != "adopt" else "ADOPT",
                lw=1.2)
    ax.set_xscale("log")
    ax.set_ylim(-1.1, 1.1)
    ax.set_xlabel("iteration $t$")
    ax.set_ylabel("$x_t$")
    ax.legend(fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig8-S4", out)


# =========================================================================== figures: Section 8.5
def fig_8_20(out=None):
    """(a) min t1^2 + t2^2 s.t. t1 + t2 = 1. (b) min (t1 - 3/2)^2 + (t2 - 1/8)^2 s.t. |t1| + |t2| <= 1."""
    fig, axes = plt.subplots(1, 2, figsize=(7.8, 3.6))
    ax = axes[0]
    th, _, lam = qp_kkt(2 * np.eye(2), np.zeros(2), Ceq=np.array([[1.0, 1.0]]), d=np.array([1.0]))
    for r in (0.3, 0.5, np.linalg.norm(th), 0.9, 1.1):
        ax.add_patch(plt.Circle((0, 0), r, fill=False, color=RED, lw=1))
    s = np.linspace(-1, 2, 2)
    ax.plot(s, 1 - s, color=BLUE, lw=1.6)
    ax.plot(*th, "ko", ms=6)
    ax.annotate(r"$\theta^*=(%.1f, %.1f)$" % tuple(th), xy=th, xytext=(0.8, 1.2), fontsize=9,
                arrowprops=dict(arrowstyle="->"))
    ax.text(-0.9, 1.6, r"$\theta_1+\theta_2=1$", color=BLUE, fontsize=9)
    ax.set_xlim(-1.3, 1.6)
    ax.set_ylim(-1.3, 1.9)
    ax.set_aspect("equal")
    common.panel_label(ax, "a", "lower left")
    ax = axes[1]
    A = np.array([[1, 1], [1, -1], [-1, 1], [-1, -1]], float)
    b = np.ones(4)
    c0 = np.array([1.5, 0.125])
    th, mu, _ = qp_kkt(2 * np.eye(2), -2 * c0, A, b)
    for r in (0.15, 0.3, np.linalg.norm(th - c0), 0.75):
        ax.add_patch(plt.Circle(c0, r, fill=False, color=RED, lw=1))
    ax.plot([1, 0, -1, 0, 1], [0, 1, 0, -1, 0], color=BLUE, lw=1.6)
    ax.plot(*th, "ko", ms=6)
    ax.plot(*c0, "+", color=RED, ms=8)
    ax.text(c0[0], c0[1] + 0.12, r"$(3/2, 1/8)$", ha="center", fontsize=8.5)
    ax.annotate(r"$\theta^*=(1,0)$, $\mu^*=(%.3f, %.3f, 0, 0)$" % (mu[0], mu[1]), xy=th, xytext=(-1.3, -1.45),
                fontsize=8.5, arrowprops=dict(arrowstyle="->"))
    ax.set_xlim(-1.4, 2.4)
    ax.set_ylim(-1.6, 1.4)
    ax.set_aspect("equal")
    common.panel_label(ax, "b", "upper left")
    for ax in axes:
        ax.axhline(0, color=GREY, lw=0.5)
        ax.axvline(0, color=GREY, lw=0.5)
        ax.set_xlabel(r"$\theta_1$")
        ax.set_ylabel(r"$\theta_2$")
    fig.tight_layout()
    savefig(fig, CH, "fig8-20", out)


LP_A = np.array([[1.0, 2.0], [3.0, 1.0], [1.0, -1.0], [-1.0, 2.0], [0.0, 1.0]])
LP_B = np.array([8.0, 12.0, 3.0, 6.0, 3.5])
LP_C = np.array([-1.0, -1.5])


def lp_vertices():
    """The vertices of {Ax <= b, x >= 0} (by brute force over pairs of constraints), in angular order."""
    A = np.vstack([LP_A, -np.eye(2)])
    b = np.concatenate([LP_B, np.zeros(2)])
    V = []
    for i in range(len(b)):
        for j in range(i + 1, len(b)):
            M = A[[i, j]]
            if abs(np.linalg.det(M)) < 1e-12:
                continue
            v = np.linalg.solve(M, b[[i, j]])
            if np.all(A @ v <= b + 1e-9) and not any(np.allclose(v, w) for w in V):
                V.append(v)
    V = np.array(V)
    c = V.mean(0)
    return V[np.argsort(np.arctan2(V[:, 1] - c[1], V[:, 0] - c[0]))]


def fig_8_21(out=None):
    """(a) A polytope cut out by half-planes. (b) The linear objective c'x, its level line at the optimum
    and the vertices visited by the simplex method."""
    V = lp_vertices()
    x, val, visited = simplex(LP_C, LP_A, LP_B)
    fig, axes = plt.subplots(1, 2, figsize=(7.8, 3.5))
    s = np.linspace(-1, 6, 2)
    for ax in axes:
        for a, bb in zip(LP_A, LP_B):
            if abs(a[1]) > 1e-12:
                ax.plot(s, (bb - a[0] * s) / a[1], color=GREY, lw=0.8)
            else:
                ax.axvline(bb / a[0], color=GREY, lw=0.8)
        ax.axhline(0, color=GREY, lw=0.8)
        ax.axvline(0, color=GREY, lw=0.8)
        ax.fill(V[:, 0], V[:, 1], color=BLUE, alpha=0.2)
        ax.plot(np.r_[V[:, 0], V[0, 0]], np.r_[V[:, 1], V[0, 1]], color=BLUE, lw=1.4)
        ax.set_xlim(-0.6, 5.2)
        ax.set_ylim(-0.6, 4.6)
        ax.set_aspect("equal")
        ax.set_xlabel(r"$\theta_1$")
    axes[0].set_ylabel(r"$\theta_2$")
    common.panel_label(axes[0], "a", "upper right")
    ax = axes[1]
    for lev in (val, val * 0.6, val * 0.3):
        ax.plot(s, (lev - LP_C[0] * s) / LP_C[1], color=RED, lw=1.4 if lev == val else 0.7,
                ls="-" if lev == val else "--")
    ax.annotate("", xy=(4.4, 3.6), xytext=(3.9, 2.85), arrowprops=dict(arrowstyle="->", color=RED, lw=1.5))
    ax.plot(visited[:, 0], visited[:, 1], "-o", color="k", ms=4, lw=1)
    ax.plot(*x, "o", color=RED, ms=7)
    common.panel_label(ax, "b", "upper right")
    fig.tight_layout()
    savefig(fig, CH, "fig8-21", out)


def fig_8_22(out=None):
    """Projected gradient descent on the box [0, 1]^2 for a quadratic whose unconstrained minimum lies
    outside the box; the first step is drawn as gradient step plus projection."""
    A = np.array([[3.0, 1.0], [1.0, 1.5]])
    m = np.array([1.7, 1.2])
    f = lambda T: 0.5 * np.einsum("i...,ij,j...->...", T - m.reshape(2, *([1] * (T.ndim - 1))), A,  # noqa: E731
                                  T - m.reshape(2, *([1] * (T.ndim - 1))))
    grad = lambda t: A @ (t - m)  # noqa: E731
    lo, hi, eta = np.zeros(2), np.ones(2), 0.35
    x = np.array([0.2, 0.15])
    P, raw = [x.copy()], []
    for _ in range(12):
        z = x - eta * grad(x)
        raw.append(z)
        x = proj_box(z, lo, hi)
        P.append(x.copy())
    P = np.array(P)
    th, mu, _ = qp_kkt(A, -A @ m, np.vstack([np.eye(2), -np.eye(2)]), np.r_[hi, -lo])
    fig, ax = plt.subplots(figsize=(4.6, 4.0))
    _contour(ax, f, (-0.4, 2.2), (-0.4, 1.8), levels=16, logspace=True, cmap="Greys")
    ax.add_patch(plt.Rectangle((0, 0), 1, 1, color="#8fd3e8", alpha=0.45))
    ax.annotate("", xy=raw[0], xytext=P[0], arrowprops=dict(arrowstyle="->", color=RED, lw=1.5))
    ax.annotate("", xy=P[1], xytext=raw[0], arrowprops=dict(arrowstyle="->", color=GREEN, lw=1.3, ls="--"))
    ax.text(*(raw[0] + [0.04, 0.02]), r"$\theta'=\theta-\eta\nabla\mathcal{L}(\theta)$", fontsize=8.5, color=RED)
    ax.text(P[1][0] + 0.03, P[1][1] - 0.12, r"${\rm proj}_{\mathcal{C}}(\theta')$", fontsize=8.5, color=GREEN)
    ax.plot(P[:, 0], P[:, 1], "-o", color="k", ms=3, lw=0.8)
    ax.plot(*m, "+", color=RED, ms=9)
    ax.plot(*th, "*", color=BLUE, ms=11)
    ax.text(0.45, 0.45, r"$\mathcal{C}$", fontsize=14)
    ax.set_aspect("equal")
    ax.set_xlabel(r"$\theta_1$")
    ax.set_ylabel(r"$\theta_2$")
    fig.tight_layout()
    savefig(fig, CH, "fig8-22", out)


# =========================================================================== figures: Section 8.6
def diabetes_lasso():
    from sklearn.datasets import load_diabetes
    X, y = load_diabetes(return_X_y=True)
    X = (X - X.mean(0)) / X.std(0)
    y = (y - y.mean()) / y.std()
    return X, y


def fig_8_S5(out=None):
    """(a) Soft thresholding (8.134) and the quantisation prox (8.143) for lam = 0.3. (b) The lasso on the
    diabetes data (lam = 0.05): ISTA, FISTA and the subgradient method."""
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 3.3))
    ax = axes[0]
    t = np.linspace(-2.5, 2.5, 1001)
    ax.plot(t, t, color=GREY, lw=0.8, ls=":", label="identity")
    ax.plot(t, soft_threshold(t, 0.3), color=BLUE, label=r"soft threshold, $\lambda=0.3$")
    ax.plot(t, prox_quant(t, 0.3), color=RED, label=r"quantisation prox, $\lambda=0.3$")
    ax.set_xlabel(r"$\theta$")
    ax.set_ylabel(r"${\rm prox}(\theta)$")
    ax.legend(fontsize=7.5)
    common.panel_label(ax, "a", "lower right")
    ax = axes[1]
    X, y = diabetes_lasso()
    lam = 0.05
    n = 300
    _, hi = ista(X, y, lam, 5000, fista=True)
    fstar = hi[-1]
    _, h1 = ista(X, y, lam, n)
    _, h2 = ista(X, y, lam, n, fista=True)
    _, h3 = subgradient_lasso(X, y, lam, n)
    ax.loglog(np.arange(1, n + 2), h1 - fstar + 1e-16, color=BLUE, label="ISTA (proximal gradient)")
    ax.loglog(np.arange(1, n + 2), h2 - fstar + 1e-16, color=RED, label="FISTA")
    ax.loglog(np.arange(1, n + 2), h3 - fstar + 1e-16, color=GREY, label="subgradient (best so far)")
    ax.set_xlabel("iteration $k$")
    ax.set_ylabel(r"$F(w_k)-F^*$")
    ax.set_ylim(1e-12, 1)
    ax.legend(fontsize=7.5, loc="lower left")
    common.panel_label(ax, "b", "upper right")
    fig.tight_layout()
    savefig(fig, CH, "fig8-S5", out)


# =========================================================================== figures: Section 8.7
def em_bound_data(seed=3, n=40):
    rng = np.random.default_rng(seed)
    z = rng.random(n) < 0.5
    return np.where(z, rng.normal(-1.0, 1.0, n), rng.normal(1.0, 1.0, n))


def fig_8_23(out=None):
    """Bound optimisation: the log-likelihood of a symmetric two-component mixture as a function of the
    mean separation theta, the EM lower bounds Q(theta, theta_t) and Q(theta, theta_{t+1}), and the
    iterates theta_t, theta_{t+1}, theta_{t+2}."""
    y = em_bound_data()
    th = np.linspace(-0.2, 2.6, 400)
    t0 = 0.15
    t1 = em_step_1d(y, t0)
    t2 = em_step_1d(y, t1)
    ll, Q0, _ = em_bound_1d(y, th, t0)
    _, Q1, _ = em_bound_1d(y, th, t1)
    fig, ax = plt.subplots(figsize=(5.0, 3.4))
    ax.plot(th, ll, "-.", color=RED, lw=1.8, label=r"$\ell(\theta)$")
    ax.plot(th, Q0, color=BLUE, label=r"$Q(\theta,\theta_t)$")
    ax.plot(th, Q1, ":", color=GREEN, lw=1.8, label=r"$Q(\theta,\theta_{t+1})$")
    lo = ll.min() - 5
    for v, lab in ((t0, r"$\theta_t$"), (t1, r"$\theta_{t+1}$"), (t2, r"$\theta_{t+2}$")):
        ax.plot([v, v], [lo, em_bound_1d(y, np.array([v]), v)[0][0]], "k:", lw=0.8)
        ax.text(v, lo - 1.5, lab, ha="center", va="top", fontsize=9)
    ax.set_ylim(lo - 4, ll.max() + 3)
    ax.set_xlabel(r"$\theta$", labelpad=12)
    ax.legend(fontsize=8, loc="lower right")
    fig.tight_layout()
    savefig(fig, CH, "fig8-23", out)


GAL_H = 1.0  # bandwidth in thousands of km/s


def fig_8_24(out=None):
    """The MM (mean-shift) quadratic lower bound and Newton's quadratic approximation of a kernel density
    estimate of the galaxy velocities: (a) Newton overshoots the maximum; (b) Newton heads for a minimum
    and lowers the objective. Circle: start; square: one MM step; diamond: one Newton step."""
    data = GALAXIES / 1000
    h = GAL_H
    x = np.linspace(5, 37, 1601)
    p = kde(x, data, h)[0]
    fig, axes = plt.subplots(1, 2, figsize=(8.2, 3.3), sharey=True)
    for ax, x0, l, xl in ((axes[0], 18.8, "a", (12, 28)), (axes[1], 18.0, "b", (12, 28))):
        q = mm_minorizer(x, x0, data, h)
        p0, d1, d2 = kde(x0, data, h)
        newt = p0 + d1 * (x - x0) + 0.5 * d2 * (x - x0) ** 2
        xm = mean_shift_step(x0, data, h)
        xn = newton_step_max(x0, data, h)
        ax.plot(x, p, ":", color="k", lw=1.4, label="density estimate")
        ax.plot(x, q, color=BLUE, label="MM lower bound")
        ax.plot(x, newt, "--", color=RED, label="Newton quadratic")
        ax.plot([x0], [p0[0]], "o", mfc="white", mec="k", ms=7)
        ax.plot([xm], [kde(xm, data, h)[0][0]], "s", color=BLUE, ms=6)
        ax.plot([xn], [kde(xn, data, h)[0][0]], "D", color=RED, ms=6)
        ax.set_xlim(xl)
        ax.set_ylim(0, 0.17)
        ax.set_xlabel("velocity (1000 km/s)")
        common.panel_label(ax, l, "upper right")
    axes[0].set_ylabel("density")
    axes[0].legend(fontsize=7.5, loc="upper left")
    fig.tight_layout()
    savefig(fig, CH, "fig8-24", out)


EM_FAITHFUL_ITERS = (0, 10, 25, 30, 35, 40)


def em_faithful():
    X = faithful(True)
    mus = np.array([[-1.0, 1.0], [1.0, -1.0]])
    hist = em_gmm(X, [0.5, 0.5], mus, [np.eye(2), np.eye(2)], 40)
    return X, hist


def fig_8_25(out=None):
    """EM for a two-component GMM on the standardised Old Faithful data, from mu1 = (-1, 1),
    mu2 = (1, -1), Sigma_k = I; colour = responsibility (red to blue)."""
    X, hist = em_faithful()
    fig, axes = plt.subplots(2, 3, figsize=(8.4, 5.4), sharex=True, sharey=True)
    for ax, it in zip(axes.ravel(), EM_FAITHFUL_ITERS):
        pis, mus, Sig, R, ll = hist[it]
        col = R[:, [0]] * np.array([0.84, 0.15, 0.16]) + R[:, [1]] * np.array([0.12, 0.37, 0.75])
        ax.scatter(X[:, 0], X[:, 1], c=np.clip(col, 0, 1), s=8, lw=0)
        for k, c in ((0, RED), (1, BLUE)):
            ax.plot(*common.ellipse_xy(mus[k], Sig[k], 1.0), color=c, lw=1.4)
            ax.plot(*mus[k], "x", color=c, ms=7)
        ax.set_title("iteration %d" % it)
        ax.set_xlim(-2.2, 2.2)
        ax.set_ylim(-2.4, 2.4)
    fig.tight_layout()
    savefig(fig, CH, "fig8-25", out)


def gmm_failure_rates(dims=tuple(range(10, 101, 10)), n=100, K=3, trials=5, n_iter=30, seed=0):
    """For each dimension D run EM (MLE and MAP) on n points from K well-separated Gaussians, 5 trials, and
    report the fraction of trials where EM breaks down (a covariance stops being positive definite or the
    log-likelihood is not finite)."""
    rng = np.random.default_rng(seed)
    out = {"mle": [], "map": []}
    for D in dims:
        fails = {"mle": 0, "map": 0}
        for _ in range(trials):
            M = rng.normal(0, 3, (K, D))
            z = rng.integers(0, K, n)
            X = M[z] + rng.normal(0, 1, (n, D))
            init = X[rng.choice(n, K, replace=False)]
            s2 = X.var(0)
            prior = dict(alpha=np.ones(K), S0=np.diag(s2) / K ** (2.0 / D), nu0=D + 2)
            for key, pr in (("mle", None), ("map", prior)):
                try:
                    with np.errstate(all="ignore"):
                        hist = em_gmm(X, np.ones(K) / K, init.copy(), np.array([np.diag(s2)] * K), n_iter, prior=pr)
                    if not np.isfinite(hist[-1][4]):
                        fails[key] += 1
                except (np.linalg.LinAlgError, FloatingPointError, ValueError):
                    fails[key] += 1
        out["mle"].append(fails["mle"] / trials)
        out["map"].append(fails["map"] / trials)
    return np.array(dims), out


def fig_8_26(out=None):
    """(a) A singularity of the GMM likelihood: one component collapses onto a single point.
    (b) Fraction of EM runs (5 per dimension, N = 100) that break down, MLE against MAP."""
    fig, axes = plt.subplots(1, 2, figsize=(8.0, 3.2))
    ax = axes[0]
    pts = np.array([-2.2, -1.5, -0.9, -0.4, 0.3, 0.8, 1.6, 2.4])
    x = np.linspace(-3.5, 3.5, 2001)
    spike = 0.25 * stats.norm.pdf(x, pts[2], 0.05)
    broad = 0.75 * stats.norm.pdf(x, 0.2, 1.4)
    ax.plot(x, spike + broad, color=RED)
    ax.plot(x, broad, ":", color=BLUE)
    ax.plot(pts, np.zeros_like(pts), "o", color=GREEN, ms=5)
    ax.set_xlabel("$x$")
    ax.set_ylabel("$p(x)$")
    common.panel_label(ax, "a", "upper right")
    ax = axes[1]
    dims, rates = gmm_failure_rates()
    ax.plot(dims, rates["mle"], "-o", color=RED, ms=4, label="MLE")
    ax.plot(dims, rates["map"], ":s", color="k", ms=4, label="MAP")
    ax.set_xlabel("dimensionality $D$")
    ax.set_ylabel("fraction of EM runs that fail")
    ax.set_ylim(-0.05, 1.05)
    ax.legend(fontsize=8)
    common.panel_label(ax, "b", "center right")
    fig.tight_layout()
    savefig(fig, CH, "fig8-26", out)
    return dims, rates


def fig_8_27(out=None):
    """(a) 200 points from 0.5 N(-10, 5^2) + 0.5 N(10, 5^2). (b) The likelihood surface in (mu1, mu2)
    with the other parameters at their true values: two symmetric modes."""
    rng = np.random.default_rng(4)
    z = rng.random(200) < 0.5
    y = np.where(z, rng.normal(-10, 5, 200), rng.normal(10, 5, 200))
    fig, axes = plt.subplots(1, 2, figsize=(8.0, 3.4))
    axes[0].hist(y, bins=15, color=BLUE, edgecolor="white")
    axes[0].set_xlabel("$y$")
    common.panel_label(axes[0], "a", "upper left")
    g = np.linspace(-15.5, 19.5, 141)
    M1, M2 = np.meshgrid(g, g)
    ll = np.logaddexp(np.log(0.5) + stats.norm.logpdf(y[:, None, None], M1, 5),
                      np.log(0.5) + stats.norm.logpdf(y[:, None, None], M2, 5)).sum(0)
    ax = axes[1]
    ax.contour(M1, M2, ll, levels=ll.max() - np.geomspace(0.5, ll.max() - ll.min(), 18)[::-1], cmap="viridis",
               linewidths=0.8)
    i = np.unravel_index(np.argmax(ll), ll.shape)
    ax.plot(M1[i], M2[i], "r+", ms=9)
    ax.plot(M2[i], M1[i], "r+", ms=9)
    ax.set_xlabel(r"$\mu_1$")
    ax.set_ylabel(r"$\mu_2$")
    ax.set_aspect("equal")
    common.panel_label(ax, "b", "upper left")
    fig.tight_layout()
    savefig(fig, CH, "fig8-27", out)


def student_data(seed=5, n=150):
    """Bivariate Gaussian data with 10 gross outliers."""
    rng = np.random.default_rng(seed)
    X = rng.multivariate_normal([0, 0], [[1, 0.6], [0.6, 1]], n)
    X[:10] = rng.uniform(-8, 8, (10, 2))
    return X


def fig_8_S6(out=None):
    """Exercise 8.2: EM for the bivariate Student distribution on data with outliers: (a) the fitted
    Gaussian and Student ellipses, (b) the log-likelihood increases at every EM iteration (nu fixed at 4,
    and estimated)."""
    X = student_data()
    mu4, S4, _, ll4 = em_student(X, 4.0, 60)
    mun, Sn, nun, lln = em_student(X, 4.0, 60, estimate_nu=True)
    mg, Sg = X.mean(0), np.cov(X.T, bias=True)
    fig, axes = plt.subplots(1, 2, figsize=(8.0, 3.4))
    ax = axes[0]
    ax.plot(X[:, 0], X[:, 1], ".", color=GREY, ms=4)
    ax.plot(*common.ellipse_xy(mg, Sg, 2.0), color=RED, label="Gaussian MLE")
    ax.plot(*common.ellipse_xy(mun, Sn * nun / (nun - 2), 2.0), color=BLUE,
            label=r"Student MLE ($\hat\nu=%.2f$)" % nun)
    ax.set_aspect("equal")
    ax.legend(fontsize=7.5, loc="upper left")
    common.panel_label(ax, "a", "lower right")
    ax = axes[1]
    ax.plot(ll4, color=ORANGE, label=r"$\nu=4$ fixed")
    ax.plot(lln, color=BLUE, label=r"$\nu$ estimated (ECM)")
    ax.set_xlabel("EM iteration")
    ax.set_ylabel("log-likelihood")
    ax.legend(fontsize=8)
    common.panel_label(ax, "b", "lower right")
    fig.tight_layout()
    savefig(fig, CH, "fig8-S6", out)


FIGURES = {"8.1": fig_8_1, "8.2": fig_8_2, "8.4": fig_8_4, "8.5": fig_8_5, "8.6": fig_8_6, "8.7": fig_8_7,
           "8.8": fig_8_8, "8.9": fig_8_9, "8.10": fig_8_10, "8.11": fig_8_11, "8.12": fig_8_12,
           "8.14": fig_8_14, "8.15": fig_8_15, "8.16": fig_8_16, "8.17": fig_8_17, "8.18": fig_8_18,
           "8.19": fig_8_19, "8.20": fig_8_20, "8.21": fig_8_21, "8.22": fig_8_22, "8.23": fig_8_23,
           "8.24": fig_8_24, "8.25": fig_8_25, "8.26": fig_8_26, "8.27": fig_8_27,
           "8.S1": fig_8_S1, "8.S2": fig_8_S2, "8.S3": fig_8_S3, "8.S4": fig_8_S4, "8.S5": fig_8_S5,
           "8.S6": fig_8_S6}


# =========================================================================== demo data
def export_json():
    """Data for the browser demonstrations: the two breast-cancer features and labels of the
    finite-sum logistic regression (SGD and variance-reduction demo)."""
    os.makedirs(DATA_OUT, exist_ok=True)
    X, y = bc_data()
    X = np.round(X, 6)                 # the demo works with the rounded values, so the optimum is computed on them
    w = logreg_opt(X, y)
    d = dict(X=[[float(a) for a in r] for r in X], y=[int(v) for v in y], lam=LOGREG_LAM,
             features=["mean texture (standardised)", "mean smoothness (standardised)"],
             label="1 = malignant", w_star=[float(v) for v in w], L_star=float(logreg_loss(w, X, y)))
    path = os.path.join(DATA_OUT, "ch08-logreg.json")
    with open(path, "w") as f:
        json.dump(d, f, separators=(",", ":"))
    print("wrote", os.path.relpath(path, os.getcwd()))


if __name__ == "__main__":
    if "--json" in sys.argv:
        export_json()
    else:
        common.run(FIGURES, CH)
        if "--fig" not in sys.argv and "--list" not in sys.argv:
            export_json()
