"""Murphy (2023), Chapter 6: Optimization (with Supplement Chapter 7, "Optimization").

Companion code for Chapter 6 of K. P. Murphy, Probabilistic Machine Learning: Advanced Topics
(MIT Press, 2023; December 2025 draft), pp. 261-342 of the book and Supplement Chapter 7, written
from scratch with numpy, scipy and matplotlib, to be read next to the lecture notes
(../ch06-optimization.html). scikit-learn is only used to load data.

Methods (each is a plain function below)
* Section 6.2, automatic differentiation: forward-mode (JVP) and reverse-mode (VJP) differentiation of
  circuits with fan-out (circuit_forward, circuit_jvp, circuit_vjp, jacobian_by_jvp, jacobian_by_vjp).
* Section 6.3, stochastic optimisation: learning-rate schedules (lr_piecewise, lr_exponential,
  lr_polynomial), the score-function and reparameterisation estimators (sfe_grad, reparam_grad), the
  Gumbel-max and Gumbel-softmax samplers (gumbel_softmax_samples).
* Section 6.4, natural gradient: Fisher matrix of a Gaussian, KL quadratic approximation, steepest
  descent against natural gradient on the coupled Gaussian of (6.91) (ngd_example).
* Section 6.5, bound optimisation: the fixed-curvature MM step, EM for a multivariate normal with
  missing data (mvn_em), EM for Student-t regression (student_em), variational EM on a latent-bit
  model (VEM).
* Section 6.6, Bayesian optimisation: a Gaussian-process surrogate (GP), probability of improvement,
  expected improvement, upper confidence bound and Thompson sampling, the Branin function.
* Section 6.7, derivative-free optimisation: steepest-ascent, random-restart and tabu search on the
  8-queens problem, grid against random search, CMA-ES (cmaes), the cross-entropy method.
* Section 6.8, optimal transport: exact discrete OT by linear programming (ot_lp), Sinkhorn in the
  log domain (sinkhorn), the Bures metric and the Gaussian Monge map, the one-dimensional quantile
  coupling.
* Section 6.9, submodular optimisation: the greedy algorithm, facility location, coverage, graph cut,
  log-determinant, a brute-force submodularity test.
* Supplement 7.1, proximal methods: soft thresholding, block thresholding, singular value
  thresholding, projections (box, PSD cone, simplex), the Moreau envelope, ISTA and FISTA, ADMM for the
  lasso and for robust PCA, truncated SGD.
* Supplement 7.3, conjugate duality: the conjugates of exp(-x) and log sigmoid, the exponential
  upper and the quadratic lower bound on the sigmoid.
* Supplement 7.4, the Bayesian learning rule: natural-parameter updates for a Gaussian q.

Data. scikit-learn's breast-cancer and iris data are used for the demonstrations (hyperparameter
search and one-dimensional optimal transport). Everything else is simulated with fixed seeds.
The book's own point sets are not available, so those figures are close stand-ins, not copies.

Figures. Reproduced here: 6.2, 6.3, 6.5, 6.6, 6.7, 6.8, 6.9, 6.10, 6.11, 6.12, 6.17, 6.18, 6.19, 6.20 and, from the
supplement, S7.1(b), S7.2 (a CPU-sized stand-in), S7.3 (a synthetic stand-in), S7.4/S7.5, S7.6.
Skipped, with the reason:
  6.1   the circuit with fan-out (a hand-drawn diagram; the algorithm it illustrates is circuit_vjp);
  6.4   the straight-through estimator diagram of an MLP (a hand-drawn schematic);
  6.13, 6.14, 6.15, 6.16  the genetic algorithm on 8-queens, the 8-queens boards, genetic-programming
        trees and the BOA diagram (hand-drawn schematics; the 8-queens search statistics of the text
        are reproduced instead as figx6-a);
  S7.2 original: a ResNet on CIFAR-10 needs a GPU-scale run; the stability claim is shown on a small
        interpolating least-squares problem (figS7-2);
  S7.3 original: surveillance video frames; the same ADMM runs on synthetic frames (figS7-3);
  S7.7  the sharp-versus-flat-minimum schematic of the Bayesian learning rule.
Extra figures for the gaps filled in the notes: figx6-a (8-queens search), figx6-b (ISTA, FISTA, ADMM),
figx6-c (variance of gradient estimators), figx6-d (Sinkhorn), figx6-e (Student-t EM regression).
Run `python3 ch06_optimization.py --list`, `python3 ch06_optimization.py` (all figures) or
`python3 ch06_optimization.py --fig 6.6`. Files go to ../img/ch06/; the data used by the browser
demonstrations go to ../data/ch06-*.json.
"""
import itertools
import json
import os
import sys

os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")
import numpy as np
from scipy import linalg, optimize, special, stats

import common
from common import BLUE, CYAN, GREEN, GREY, MAGENTA, ORANGE, PURPLE, RED, savefig
import matplotlib.pyplot as plt

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


# =========================================================================== 6.2 automatic differentiation
UNARY = {
    "sin": (np.sin, np.cos),
    "exp": (np.exp, np.exp),
    "tanh": (np.tanh, lambda x: 1 - np.tanh(x) ** 2),
    "sq": (lambda x: x * x, lambda x: 2 * x),
    "log": (np.log, lambda x: 1.0 / x),
}


def circuit_forward(nodes, x):
    """Evaluate a circuit: nodes is a list of (op, parents) in topological order, node 0 is the input."""
    vals = []
    for op, pa in nodes:
        if op == "in":
            v = np.asarray(x, float)
        elif op in UNARY:
            v = UNARY[op][0](vals[pa[0]])
        elif op == "add":
            v = vals[pa[0]] + vals[pa[1]]
        elif op == "mul":
            v = vals[pa[0]] * vals[pa[1]]
        elif op == "sum":
            v = np.sum(vals[pa[0]])
        else:
            raise ValueError(op)
        vals.append(v)
    return vals


def circuit_jvp(nodes, x, v):
    """Forward mode (Algorithm 6.3): returns f(x) and the Jacobian-vector product df(x)[v]."""
    vals = circuit_forward(nodes, x)
    tans = []
    for op, pa in nodes:
        if op == "in":
            d = np.asarray(v, float)
        elif op in UNARY:
            d = UNARY[op][1](vals[pa[0]]) * tans[pa[0]]
        elif op == "add":
            d = tans[pa[0]] + tans[pa[1]]
        elif op == "mul":
            d = tans[pa[0]] * vals[pa[1]] + vals[pa[0]] * tans[pa[1]]
        else:  # sum
            d = np.sum(tans[pa[0]])
        tans.append(d)
    return vals[-1], tans[-1]


def circuit_vjp(nodes, x, u):
    """Reverse mode (Algorithm 6.4): f(x) and the vector-Jacobian product df(x)^T u; the cotangents arriving
    along the several outgoing edges of a node (fan-out) are summed."""
    vals = circuit_forward(nodes, x)
    ct = [None] * len(nodes)
    ct[-1] = np.asarray(u, float)

    def acc(i, val):
        ct[i] = val if ct[i] is None else ct[i] + val

    for t in range(len(nodes) - 1, 0, -1):
        op, pa = nodes[t]
        c = ct[t]
        if c is None:
            continue
        if op in UNARY:
            acc(pa[0], UNARY[op][1](vals[pa[0]]) * c)
        elif op == "add":
            acc(pa[0], c)
            acc(pa[1], c)
        elif op == "mul":
            acc(pa[0], c * vals[pa[1]])
            acc(pa[1], c * vals[pa[0]])
        else:  # sum
            acc(pa[0], c * np.ones_like(vals[pa[0]]))
    return vals[-1], ct[0]


def jacobian_by_jvp(nodes, x):
    """One JVP per input coordinate (n passes): the columns of the Jacobian."""
    n = len(x)
    return np.stack([np.atleast_1d(circuit_jvp(nodes, x, np.eye(n)[i])[1]) for i in range(n)], axis=1)


def jacobian_by_vjp(nodes, x, m):
    """One VJP per output coordinate (m passes): the rows of the Jacobian."""
    return np.stack([circuit_vjp(nodes, x, np.eye(m)[j])[1] for j in range(m)], axis=0)


# example circuit of Figure 6.1(a): f(x) = c(a(x), b(a(x))) with a = sin, b = exp, c = elementwise product, then summed
FIG61_NODES = [("in", ()), ("sin", (0,)), ("exp", (1,)), ("mul", (1, 2)), ("sum", (3,))]
FIG61_VEC = FIG61_NODES[:-1]   # vector-valued output (no final sum)


# =========================================================================== 6.3 stochastic optimisation
def lr_piecewise(t, eta0=1.0, gamma=0.9, milestones=(34, 67)):
    return eta0 * gamma ** np.searchsorted(np.asarray(milestones), t, side="right")


def lr_exponential(t, eta0=1.0, lam=0.05):
    return eta0 * np.exp(-lam * np.asarray(t, float))


def lr_polynomial(t, eta0=1.0, alpha=0.5, beta=0.1):
    return eta0 * (beta * np.asarray(t, float) + 1.0) ** (-alpha)


def fig_6_2(out=None):
    """Learning-rate schedules: piecewise constant, exponential decay and polynomial decay."""
    t = np.arange(0, 101)
    fig, axes = common.panel_grid(1, 3, size=(3.1, 2.5))
    for ax, y, ttl, lab in zip(axes[0], (lr_piecewise(t), lr_exponential(t), lr_polynomial(t)),
                               ("piecewise constant", "exponential decay", "polynomial decay"), "abc"):
        ax.plot(t, y, color=BLUE)
        ax.set_title(ttl)
        ax.set_xlabel("step $t$")
        common.panel_label(ax, lab, "upper right")
    axes[0, 0].set_ylabel("learning rate")
    savefig(fig, CH, "fig6-2", out)


def sfe_grad(mu, v, S, rng, baseline=False):
    """Score-function (REINFORCE) estimate of d/d(mu, v) E[z^2 - 3z], z ~ N(mu, v), from S samples (6.58)."""
    z = mu + np.sqrt(v) * rng.standard_normal(S)
    Lt = z ** 2 - 3 * z
    if baseline:
        Lt = Lt - Lt.mean()
    s_mu = (z - mu) / v
    s_v = -0.5 / v + 0.5 * (z - mu) ** 2 / v ** 2
    return np.array([np.mean(Lt * s_mu), np.mean(Lt * s_v)])


def reparam_grad(mu, v, S, rng):
    """Reparameterisation (pathwise) estimate of the same gradient, z = mu + sqrt(v) eps (6.64)."""
    eps = rng.standard_normal(S)
    z = mu + np.sqrt(v) * eps
    dL = 2 * z - 3
    return np.array([np.mean(dL), np.mean(dL * eps / (2 * np.sqrt(v)))])


def exact_grad(mu, v):
    """Exact gradient of E[z^2 - 3z] = mu^2 + v - 3 mu: (2 mu - 3, 1); Bonnet and Price give the same."""
    return np.array([2 * mu - 3, 1.0])


def fig_x6_c(out=None):
    """Variance of the score-function and reparameterisation gradient estimators (the example of 6.3.5.1)."""
    rng = np.random.default_rng(0)
    mu, v = 1.0, 0.5
    Ss = np.array([1, 2, 5, 10, 20, 50, 100, 200, 500])
    res = {k: [] for k in ("sfe", "sfe+baseline", "reparam")}
    for S in Ss:
        for key, fn in (("sfe", lambda: sfe_grad(mu, v, S, rng)), ("sfe+baseline", lambda: sfe_grad(mu, v, S, rng, True)),
                        ("reparam", lambda: reparam_grad(mu, v, S, rng))):
            g = np.array([fn() for _ in range(3000)])
            res[key].append(g.var(0) if not (key == "sfe+baseline" and S == 1) else np.full(2, np.nan))
    fig, axes = common.panel_grid(1, 2, size=(3.4, 2.7))
    for j, nm in enumerate(("$\\mu$", "$v$")):
        ax = axes[0, j]
        for key, c, ls in (("sfe", RED, "-"), ("sfe+baseline", ORANGE, "--"), ("reparam", BLUE, "-")):
            ax.loglog(Ss, np.array(res[key])[:, j], color=c, ls=ls, marker="o", ms=3, label=key.replace("sfe", "score function"))
        ax.loglog(Ss, np.array(res["sfe"])[0, j] / Ss, color=GREY, ls=":", lw=1, label="$1/S$")
        ax.set_xlabel("samples $S$")
        ax.set_ylabel("variance of $\\partial/\\partial$" + nm)
        common.panel_label(ax, "ab"[j], "lower left")
    axes[0, 0].legend(fontsize=7)
    savefig(fig, CH, "figx6-c", out)


def gumbel_softmax_samples(log_alpha, tau, n, rng):
    """Samples from the Gumbel-softmax (concrete) distribution (6.79)."""
    g = -np.log(-np.log(rng.uniform(size=(n, len(log_alpha)))))
    z = (np.asarray(log_alpha) + g) / tau
    z -= z.max(1, keepdims=True)
    e = np.exp(z)
    return e / e.sum(1, keepdims=True)


def gumbel_max_samples(log_alpha, n, rng):
    g = -np.log(-np.log(rng.uniform(size=(n, len(log_alpha)))))
    return np.argmax(np.asarray(log_alpha) + g, axis=1)


def fig_6_3(out=None):
    """The Gumbel-softmax distribution on K = 7 states at several temperatures."""
    rng = np.random.default_rng(3)
    alpha = np.array([0.05, 0.15, 0.4, 0.1, 0.1, 0.1, 0.1])
    alpha = alpha / alpha.sum()
    la = np.log(alpha)
    taus = (0.1, 0.5, 1.0, 10.0)
    fig, axes = common.panel_grid(2, 5, size=(1.9, 1.7))
    ks = np.arange(1, 8)
    axes[0, 0].bar(ks, alpha, color=BLUE)
    d = np.zeros(7)
    d[gumbel_max_samples(la, 1, rng)[0]] = 1
    axes[1, 0].bar(ks, d, color=RED)
    axes[0, 0].set_title("categorical", fontsize=8.5)
    for j, tau in enumerate(taus, start=1):
        Z = gumbel_softmax_samples(la, tau, 40000, rng)
        axes[0, j].bar(ks, Z.mean(0), color=BLUE)
        axes[1, j].bar(ks, Z[0], color=RED)
        axes[0, j].set_title("$\\tau=%g$" % tau, fontsize=8.5)
    for ax in axes.ravel():
        ax.set_ylim(0, 1)
        ax.set_xticks([1, 4, 7])
        ax.tick_params(labelsize=7)
    axes[0, 0].set_ylabel("$E[z]$", fontsize=8)
    axes[1, 0].set_ylabel("sample $z$", fontsize=8)
    savefig(fig, CH, "fig6-3", out)


# =========================================================================== 6.4 natural gradient
def gauss_kl(mu1, s1, mu2, s2):
    """KL(N(mu1, s1^2) || N(mu2, s2^2))."""
    return np.log(s2 / s1) + (s1 ** 2 + (mu1 - mu2) ** 2) / (2 * s2 ** 2) - 0.5


def fisher_gauss_musigma(mu, s):
    """Fisher information matrix of N(mu, s^2) in the parameters (mu, s): diag(1/s^2, 2/s^2)."""
    return np.diag([1 / s ** 2, 2 / s ** 2])


NGD_J = np.array([[3.0, 1.0 / 3.0], [1.0 / 3.0, 0.0]])   # mean of the coupled Gaussian (6.91) is J theta
NGD_F = NGD_J.T @ NGD_J                                  # its Fisher matrix (6.94)


def ngd_example(theta0=(1.0, -1.0), n_iter=60, eta_sd=None, eta_ng=0.2):
    """Steepest descent against natural gradient on the cross entropy L(theta) = theta' F theta / 2 of (6.91)-(6.94)."""
    F = NGD_F
    if eta_sd is None:
        eta_sd = 1.0 / np.linalg.eigvalsh(F).max()
    th_sd = [np.array(theta0, float)]
    th_ng = [np.array(theta0, float)]
    for _ in range(n_iter):
        th_sd.append(th_sd[-1] - eta_sd * F @ th_sd[-1])
        th_ng.append(th_ng[-1] - eta_ng * np.linalg.solve(F, F @ th_ng[-1]))
    loss = lambda th: 0.5 * th @ F @ th
    return np.array(th_sd), np.array(th_ng), np.array([loss(t) for t in th_sd]), np.array([loss(t) for t in th_ng])


def fig_6_5(out=None):
    """Shifting the mean of a Gaussian by a fixed amount matters more when the variance is small."""
    fig, axes = common.panel_grid(1, 2, size=(3.3, 2.3))
    x = np.linspace(-6, 6, 400)
    delta = 1.0
    for ax, s, lab in zip(axes[0], (0.6, 2.0), "ab"):
        ax.plot(x, stats.norm.pdf(x, 0, s), color=BLUE)
        ax.plot(x, stats.norm.pdf(x, delta, s), color=BLUE, ls=":")
        ax.set_title("$\\sigma=%g$,  KL $=%.2f$" % (s, gauss_kl(0, s, delta, s)), fontsize=9)
        ax.set_xlabel("$y$")
        common.panel_label(ax, lab, "upper left")
    savefig(fig, CH, "fig6-5", out)


def fig_6_6(out=None):
    """Natural gradient against steepest descent on the coupled Gaussian of (6.91); gradient fields in theta and phi."""
    th_sd, th_ng, l_sd, l_ng = ngd_example()
    F = NGD_F
    w, V = np.linalg.eigh(F)
    Fh = V @ np.diag(np.sqrt(w)) @ V.T
    fig, axes = common.panel_grid(2, 2, size=(3.4, 3.0))
    ax = axes[0, 0]
    g1, g2 = np.meshgrid(np.linspace(-0.4, 1.2, 80), np.linspace(-1.2, 0.4, 80))
    Z = 0.5 * (F[0, 0] * g1 ** 2 + 2 * F[0, 1] * g1 * g2 + F[1, 1] * g2 ** 2)
    ax.contour(g1, g2, Z, levels=np.array([0.01, 0.05, 0.2, 0.8, 3, 6]), colors="0.75", linewidths=0.8)
    ax.plot(*th_sd.T, ".-", color=RED, ms=3, lw=0.8, label="steepest descent")
    ax.plot(*th_ng[:25].T, ".-", color=BLUE, ms=3, lw=0.8, label="natural gradient")
    ax.plot(0, 0, "k*", ms=8)
    ax.set_xlabel("$\\theta_1$")
    ax.set_ylabel("$\\theta_2$")
    ax.legend(fontsize=7, loc="lower left")
    common.panel_label(ax, "a", "upper right")
    ax = axes[0, 1]
    ax.semilogy(l_sd, color=RED, label="steepest descent")
    ax.semilogy(l_ng, color=BLUE, label="natural gradient")
    ax.set_xlabel("iteration")
    ax.set_ylabel("$L(\\theta_t)$")
    ax.legend(fontsize=7)
    common.panel_label(ax, "b", "lower left")
    ax = axes[1, 0]
    a1, a2 = np.meshgrid(np.linspace(-0.4, 1.2, 14), np.linspace(-1.2, 0.4, 14))
    G = np.stack([a1.ravel(), a2.ravel()])
    grad = F @ G
    nrm = np.linalg.norm(grad, axis=0) + 1e-12
    ax.quiver(a1, a2, -(grad[0] / nrm).reshape(a1.shape), -(grad[1] / nrm).reshape(a1.shape), color=GREY, angles="xy", scale=25)
    ax.set_xlabel("$\\theta_1$")
    ax.set_ylabel("$\\theta_2$")
    common.panel_label(ax, "c", "upper right")
    ax = axes[1, 1]
    P = Fh @ G
    q1, q2 = np.meshgrid(np.linspace(P[0].min(), P[0].max(), 14), np.linspace(P[1].min(), P[1].max(), 14))
    nrm = np.hypot(q1, q2) + 1e-12
    ax.quiver(q1, q2, -q1 / nrm, -q2 / nrm, color=GREY, angles="xy", scale=25)   # grad of |phi|^2/2 is phi
    ax.set_xlabel("$\\phi_1$")
    ax.set_ylabel("$\\phi_2$")
    common.panel_label(ax, "d", "upper right")
    savefig(fig, CH, "fig6-6", out)


# =========================================================================== 6.5 bound optimisation (MM and EM)
def mm_logistic_step(w, X, y, B=None):
    """One bound-optimisation step for binary logistic regression (maximising the log likelihood), (6.134)-(6.135):
    w <- w + 4 (X'X)^{-1} g with g = X'(y - mu); B = -X'X/4 is the fixed lower bound on the Hessian."""
    mu = common.sigmoid(X @ w)
    g = X.T @ (y - mu)
    if B is None:
        B = -0.25 * X.T @ X
    return w - np.linalg.solve(B, g)


def newton_logistic_step(w, X, y):
    mu = common.sigmoid(X @ w)
    g = X.T @ (y - mu)
    H = -(X.T * (mu * (1 - mu))) @ X
    return w - np.linalg.solve(H, g)


def _mix_loglik(theta, x, mu2=4.0, pi=0.5):
    return np.logaddexp(np.log(pi) + stats.norm.logpdf(x, theta, 1.0), np.log(1 - pi) + stats.norm.logpdf(x, mu2, 1.0)).sum()


def _mix_Q(theta, theta_t, x, mu2=4.0, pi=0.5):
    """Q(theta, theta_t) = ELBO with q = posterior at theta_t, (6.147), for the mixture pi N(x|theta,1) + (1-pi) N(x|mu2,1)."""
    l1 = np.log(pi) + stats.norm.logpdf(x, theta_t, 1.0)
    l2 = np.log(1 - pi) + stats.norm.logpdf(x, mu2, 1.0)
    r1 = np.exp(l1 - np.logaddexp(l1, l2))
    r2 = 1 - r1
    a1 = np.log(pi) + stats.norm.logpdf(x, theta, 1.0)
    a2 = np.log(1 - pi) + stats.norm.logpdf(x, mu2, 1.0)
    with np.errstate(divide="ignore", invalid="ignore"):
        h = -(np.where(r1 > 0, r1 * np.log(r1), 0) + np.where(r2 > 0, r2 * np.log(r2), 0))
    return (r1 * a1 + r2 * a2 + h).sum()


def mix_em_step(theta_t, x, mu2=4.0, pi=0.5):
    l1 = np.log(pi) + stats.norm.logpdf(x, theta_t, 1.0)
    l2 = np.log(1 - pi) + stats.norm.logpdf(x, mu2, 1.0)
    r1 = np.exp(l1 - np.logaddexp(l1, l2))
    return (r1 * x).sum() / r1.sum()


MIX_MU2 = 3.0


def fig_6_7(out=None):
    """A bound-optimisation (MM) algorithm: the surrogate Q touches the log likelihood at theta_t and is maximised."""
    rng = np.random.default_rng(2)
    x = np.concatenate([rng.normal(-0.5, 1.0, 12), rng.normal(2.0, 1.0, 14)])
    th = np.linspace(-4, 3, 500)
    ll = np.array([_mix_loglik(t, x, MIX_MU2) for t in th])
    t0 = -3.0
    t1 = mix_em_step(t0, x, MIX_MU2)
    t2 = mix_em_step(t1, x, MIX_MU2)
    fig, ax = plt.subplots(figsize=(4.8, 3.0))
    ax.plot(th, ll, color=RED, ls="--", label="$\\ell(\\theta)$")
    for tt, c, nm in ((t0, BLUE, "$Q(\\theta,\\theta_t)$"), (t1, GREEN, "$Q(\\theta,\\theta_{t+1})$")):
        q = np.array([_mix_Q(t, tt, x, MIX_MU2) for t in th])
        ax.plot(th, q, color=c, ls="-" if c == BLUE else ":", label=nm)
        ax.plot(tt, _mix_loglik(tt, x, MIX_MU2), "o", color=c, ms=4)
    for tt in (t0, t1, t2):
        ax.axvline(tt, color=GREY, lw=0.5)
    lo = ll.max() - 60
    ax.set_ylim(lo, ll.max() + 6)
    for tt, nm in ((t0, "$\\theta_t$"), (t1, "$\\theta_{t+1}$"), (t2, "$\\theta_{t+2}$")):
        ax.text(tt, lo + 1, nm, fontsize=8, va="bottom", ha="center", bbox=dict(fc="white", ec="none", pad=0.5))
    ax.set_xlabel("$\\theta$")
    ax.legend(fontsize=8, loc="upper left")
    savefig(fig, CH, "fig6-7", out)


def mvn_loglik_obs(X, mu, S):
    """Log likelihood of the observed entries of X (nan = missing) under N(mu, S)."""
    ll = 0.0
    for x in X:
        o = ~np.isnan(x)
        ll += common.gauss_logpdf(x[o][None, :], mu[o], S[np.ix_(o, o)])[0]
    return ll


def mvn_impute(X, mu, S):
    """E[z_n | x_n, theta] for the missing entries, and the conditional covariances V_n."""
    N, D = X.shape
    Ey = X.copy()
    Vs = np.zeros((N, D, D))
    for n in range(N):
        v = ~np.isnan(X[n])
        h = ~v
        if h.any():
            K = np.linalg.solve(S[np.ix_(v, v)], S[np.ix_(v, h)]).T
            Ey[n, h] = mu[h] + K @ (X[n, v] - mu[v])
            Vs[n][np.ix_(h, h)] = S[np.ix_(h, h)] - K @ S[np.ix_(v, h)]
    return Ey, Vs


def mvn_em(X, n_iter=200, tol=1e-10):
    """EM for a multivariate normal with values missing at random, (6.152)-(6.164). Returns (mu, Sigma, log-lik history)."""
    N, D = X.shape
    mu = np.nanmean(X, 0)
    S = np.diag(np.nanvar(X, 0))
    hist = [mvn_loglik_obs(X, mu, S)]
    for _ in range(n_iter):
        Ey, Vs = mvn_impute(X, mu, S)
        mu = Ey.mean(0)
        Eyy = (Ey.T @ Ey + Vs.sum(0)) / N
        S = Eyy - np.outer(mu, mu)
        hist.append(mvn_loglik_obs(X, mu, S))
        if abs(hist[-1] - hist[-2]) < tol:
            break
    return mu, S, np.array(hist)


def mvn_missing_data(N=100, D=10, frac=0.5, seed=1):
    rng = np.random.default_rng(seed)
    A = rng.normal(size=(D, 4)) * 0.8
    S = A @ A.T + 0.35 * np.eye(D)
    mu = rng.normal(size=D) * 0.5
    Z = rng.multivariate_normal(mu, S, size=N)
    M = rng.uniform(size=(N, D)) < frac
    M[M.all(1), 0] = False
    X = np.where(M, np.nan, Z)
    return Z, X, M, mu, S


def fig_6_8(out=None):
    """Imputation with a multivariate Gaussian: true values against imputed values, true and EM-estimated parameters."""
    Z, X, M, mu, S = mvn_missing_data()
    muh, Sh, _ = mvn_em(X)
    fig, axes = common.panel_grid(2, 4, size=(2.2, 2.0))
    for row, (m_, S_, ttl) in enumerate(((mu, S, "true parameters"), (muh, Sh, "EM estimates"))):
        Ey, _ = mvn_impute(X, m_, S_)
        for d in range(4):
            ax = axes[row, d]
            mk = M[:, d]
            ax.plot(Z[mk, d], Ey[mk, d], ".", color=BLUE, ms=3)
            lim = [min(Z[mk, d].min(), Ey[mk, d].min()), max(Z[mk, d].max(), Ey[mk, d].max())]
            ax.plot(lim, lim, color=GREY, lw=0.6)
            r2 = 1 - ((Z[mk, d] - Ey[mk, d]) ** 2).sum() / ((Z[mk, d] - Z[mk, d].mean()) ** 2).sum()
            ax.set_title("$R^2=%.2f$" % r2, fontsize=8)
            ax.set_xlabel("truth", fontsize=8)
            if d == 0:
                ax.set_ylabel("imputed\n(%s)" % ttl, fontsize=8)
    fig.subplots_adjust(hspace=0.65, wspace=0.4)
    savefig(fig, CH, "fig6-8", out)


# ---- Student-t regression by EM (6.5.5) and its Gaussian scale mixture
def student_em(X, y, nu=4.0, n_iter=200, tol=1e-12):
    """EM for linear regression with a Student-t likelihood, (6.165)-(6.170). Returns w, sigma2, weights, log-lik history."""
    N = len(y)
    w = np.linalg.lstsq(X, y, rcond=None)[0]
    s2 = np.mean((y - X @ w) ** 2)
    hist = []
    for _ in range(n_iter):
        r = y - X @ w
        delta = r ** 2 / s2
        lam = (nu + 1) / (nu + delta)
        W = X.T * lam
        w = np.linalg.solve(W @ X, W @ y)
        s2 = np.sum(lam * (y - X @ w) ** 2) / N
        hist.append(student_loglik(w, s2, X, y, nu))
        if len(hist) > 1 and abs(hist[-1] - hist[-2]) < tol:
            break
    r = y - X @ w
    return w, s2, (nu + 1) / (nu + r ** 2 / s2), np.array(hist)


def student_loglik(w, s2, X, y, nu):
    return stats.t.logpdf((y - X @ w) / np.sqrt(s2), nu).sum() - 0.5 * len(y) * np.log(s2)


def fig_x6_e(out=None):
    """Robust linear regression: least squares against Student-t likelihood fitted by EM (Section 6.5.5)."""
    rng = np.random.default_rng(4)
    n = 40
    x = rng.uniform(-3, 3, n)
    y = 1.0 + 0.8 * x + 0.4 * rng.standard_normal(n)
    y[[3, 11, 25, 31]] += np.array([6, -7, 8, 7])
    X = np.stack([np.ones(n), x], 1)
    w_ls = np.linalg.lstsq(X, y, rcond=None)[0]
    w_t, s2, lam, hist = student_em(X, y, nu=2.0)
    fig, axes = common.panel_grid(1, 2, size=(3.5, 2.8))
    ax = axes[0, 0]
    sc = ax.scatter(x, y, c=lam, cmap="viridis_r", s=18, vmin=0, vmax=1)
    xs = np.array([-3, 3])
    ax.plot(xs, w_ls[0] + w_ls[1] * xs, color=RED, label="least squares")
    ax.plot(xs, w_t[0] + w_t[1] * xs, color=BLUE, label="Student-t, EM")
    ax.legend(fontsize=7, loc="upper left")
    ax.set_xlabel("$x$")
    ax.set_ylabel("$y$")
    cb = fig.colorbar(sc, ax=ax, location="top", fraction=0.05, pad=0.03)
    cb.set_label("weight $\\lambda_n$", fontsize=8)
    common.panel_label(ax, "a", "lower right")
    ax = axes[0, 1]
    ax.plot(hist, color=BLUE)
    ax.set_xlabel("EM iteration")
    ax.set_ylabel("log likelihood")
    common.panel_label(ax, "b", "lower right")
    fig.subplots_adjust(wspace=0.5)
    savefig(fig, CH, "figx6-e", out)


# ---- variational EM on a latent-bit model (Figure 6.9)
class LatentBits:
    """x_n = W z_n + noise, z_n in {0,1}^K with independent Bernoulli(pi) bits; K small enough to enumerate 2^K states."""

    def __init__(self, X, K):
        self.X, self.K = X, K
        self.Z = np.array(list(itertools.product([0, 1], repeat=K)), float)   # (2^K, K)

    def loglik(self, W, s2, pi):
        mu = self.Z @ W.T                                  # (2^K, D)
        D = self.X.shape[1]
        lp = (self.Z * np.log(pi) + (1 - self.Z) * np.log(1 - pi)).sum(1)
        d2 = ((self.X[:, None, :] - mu[None]) ** 2).sum(-1)
        lj = lp[None] - 0.5 * d2 / s2 - 0.5 * D * np.log(2 * np.pi * s2)
        return special.logsumexp(lj, axis=1).sum(), lj

    def em(self, W, s2, pi, n_iter, variational):
        X, K = self.X, self.K
        N, D = X.shape
        out = []
        M = np.full((N, K), 0.5)
        for _ in range(n_iter):
            ll, lj = self.loglik(W, s2, pi)
            if not variational:
                R = np.exp(lj - special.logsumexp(lj, axis=1, keepdims=True))
                Ez = R @ self.Z
                Ezz = np.einsum("ns,sk,sl->kl", R, self.Z, self.Z)
                bound = ll
            else:
                for _ in range(30):                         # mean-field coordinate ascent
                    for k in range(K):
                        resid = X - M @ W.T + np.outer(M[:, k], W[:, k])
                        a = np.log(pi[k] / (1 - pi[k])) + (resid @ W[:, k] - 0.5 * W[:, k] @ W[:, k]) / s2
                        M[:, k] = common.sigmoid(a)
                Ez = M
                Ezz = M.T @ M + np.diag((M * (1 - M)).sum(0))
                bound = self._elbo(W, s2, pi, M)
            out.append((ll, bound))
            W = np.linalg.solve(Ezz, Ez.T @ X).T
            s2 = float((np.sum(X ** 2) - 2 * np.sum((Ez @ W.T) * X) + np.trace(W.T @ W @ Ezz)) / (N * D))
            pi = np.clip(Ez.mean(0), 1e-3, 1 - 1e-3)
        ll, _ = self.loglik(W, s2, pi)
        out.append((ll, out[-1][1]))
        return np.array(out), (W, s2, pi)

    def _elbo(self, W, s2, pi, M):
        X = self.X
        N, D = X.shape
        mu = M @ W.T
        quad = ((X - mu) ** 2).sum() + ((M * (1 - M)) * (W ** 2).sum(0)).sum()
        Elogp = -0.5 * quad / s2 - 0.5 * N * D * np.log(2 * np.pi * s2) + (M * np.log(pi) + (1 - M) * np.log(1 - pi)).sum()
        Mc = np.clip(M, 1e-12, 1 - 1e-12)
        H = -(Mc * np.log(Mc) + (1 - Mc) * np.log(1 - Mc)).sum()
        return Elogp + H


def latent_bits_data(seed, N=60, D=3, K=3, corr=0.9):
    rng = np.random.default_rng(seed)
    base = rng.normal(size=(D, 1))
    W = corr * base + (1 - corr) * rng.normal(size=(D, K))
    Z = (rng.uniform(size=(N, K)) < 0.5).astype(float)
    X = Z @ W.T + 0.3 * rng.standard_normal((N, D))
    return X, W


def vem_curves(seed, n_iter=25):
    X, _ = latent_bits_data(seed)
    model = LatentBits(X, 3)
    rng = np.random.default_rng(seed + 100)
    W0 = rng.normal(size=(3, 3)) * 0.5
    args = (W0, 1.0, np.full(3, 0.5))
    ex, _ = model.em(*args, n_iter, False)
    va, _ = model.em(*args, n_iter, True)
    return ex, va


def fig_6_9(out=None):
    """Variational EM: the lower bound always increases, the likelihood need not (seeds fixed in VEM_SEEDS)."""
    fig, axes = common.panel_grid(1, 2, size=(3.4, 2.6))
    for ax, seed, lab in zip(axes[0], VEM_SEEDS, "ab"):
        ex, va = vem_curves(seed)
        ax.plot(va[:, 0], color=BLUE, label="true log-likelihood")
        ax.plot(va[:-1, 1], color=RED, ls="--", label="lower bound")
        ax.set_xlabel("iteration")
        common.panel_label(ax, lab, "lower right")
    axes[0, 0].legend(fontsize=7, loc="center right")
    savefig(fig, CH, "fig6-9", out)


VEM_SEEDS = (1, 37)


# =========================================================================== 6.6 Bayesian optimisation
def rbf_kernel(A, B, ell=0.2, s2=1.0):
    A = np.atleast_2d(A)
    B = np.atleast_2d(B)
    ell = np.asarray(ell, float)
    d2 = (((A[:, None, :] - B[None, :, :]) / ell) ** 2).sum(-1)
    return s2 * np.exp(-0.5 * d2)


class GP:
    """Zero-mean Gaussian-process regression with an RBF kernel (inputs in R^d, observation noise `noise`)."""

    def __init__(self, X, y, ell=0.2, s2=1.0, noise=1e-6):
        self.X = np.asarray(X, float)
        if self.X.ndim == 1:
            self.X = self.X[:, None]
        self.y = np.asarray(y, float)
        self.ell, self.s2, self.noise = ell, s2, noise
        K = rbf_kernel(self.X, self.X, ell, s2) + noise * np.eye(len(self.y))
        self.L = np.linalg.cholesky(K)
        self.alpha = linalg.cho_solve((self.L, True), self.y)

    def predict(self, Xs):
        Xs = np.asarray(Xs, float)
        if Xs.ndim == 1:
            Xs = Xs[:, None]
        Ks = rbf_kernel(Xs, self.X, self.ell, self.s2)
        mu = Ks @ self.alpha
        v = linalg.solve_triangular(self.L, Ks.T, lower=True)
        var = np.maximum(self.s2 - (v ** 2).sum(0), 1e-12)
        return mu, np.sqrt(var)

    def sample(self, Xs, n, rng):
        Xs = np.asarray(Xs, float)
        if Xs.ndim == 1:
            Xs = Xs[:, None]
        Ks = rbf_kernel(Xs, self.X, self.ell, self.s2)
        mu = Ks @ self.alpha
        v = linalg.solve_triangular(self.L, Ks.T, lower=True)
        C = rbf_kernel(Xs, Xs, self.ell, self.s2) - v.T @ v
        Lc = np.linalg.cholesky(C + 1e-8 * np.eye(len(Xs)))
        return mu[None] + (Lc @ rng.standard_normal((len(Xs), n))).T


def acq_pi(mu, sd, M):
    return stats.norm.cdf((mu - M) / sd)                       # (6.174)


def acq_ei(mu, sd, M):
    g = (mu - M) / sd
    return sd * (g * stats.norm.cdf(g) + stats.norm.pdf(g))   # (6.177)


def acq_ucb(mu, sd, beta=2.0):
    return mu + beta * sd


def branin(x1, x2):
    """The Branin function (to be minimised) on [-5, 10] x [0, 15]."""
    a, b, c = 1.0, 5.1 / (4 * np.pi ** 2), 5 / np.pi
    r, s, t = 6.0, 10.0, 1 / (8 * np.pi)
    return a * (x2 - b * x1 ** 2 + c * x1 - r) ** 2 + s * (1 - t) * np.cos(x1) + s


def f_bo1d(x):
    """A smooth one-dimensional test function on [0, 1] with two local maxima."""
    x = np.asarray(x, float)
    return np.sin(3.0 * x * np.pi) * 0.5 + np.exp(-((x - 0.72) / 0.12) ** 2) * 1.1 + 0.3 * x


def fig_6_10(out=None):
    """Three steps of sequential Bayesian optimisation with a GP surrogate and the expected-improvement acquisition."""
    grid = np.linspace(0, 1, 400)
    X = np.array([0.12, 0.45])
    fig, axes = common.panel_grid(3, 1, size=(5.0, 2.0))
    fg = f_bo1d(grid)
    for row in range(3):
        y = f_bo1d(X)
        mean, sd_ = fg.mean(), fg.std()
        gp = GP(X, (y - mean) / sd_, ell=0.12, s2=1.0, noise=1e-6)
        mu, sd = gp.predict(grid)
        M = ((y - mean) / sd_).max()
        ei = acq_ei(mu, sd, M)
        xn = grid[np.argmax(ei)]
        ax = axes[row, 0]
        ax.plot(grid, fg, "k:", lw=1)
        ax.plot(grid, mu * sd_ + mean, "k-", lw=1)
        ax.fill_between(grid, (mu - 1.96 * sd) * sd_ + mean, (mu + 1.96 * sd) * sd_ + mean, color=BLUE, alpha=0.2)
        ax.plot(X, y, "ko", ms=4)
        ax2 = ax.twinx()
        ax2.fill_between(grid, 0, ei / ei.max(), color=GREEN, alpha=0.5)
        ax2.plot(xn, 1.0, "^", color=RED, ms=7)
        ax2.set_ylim(0, 3.0)
        ax2.set_yticks([])
        ax.set_ylabel("$t=%d$" % len(X))
        X = np.append(X, xn)
    axes[2, 0].set_xlabel("$x$")
    savefig(fig, CH, "fig6-10", out)


def fig_6_11(out=None):
    """The Branin function, a GP fitted to 20 evaluations, and three acquisition functions (PI, EI, UCB)."""
    rng = np.random.default_rng(5)
    n = 70
    u = np.linspace(0, 1, n)
    U1, U2 = np.meshgrid(u, u)
    lo, hi = np.array([-5.0, 0.0]), np.array([10.0, 15.0])
    P = np.stack([U1.ravel(), U2.ravel()], 1)
    fx = -branin(lo[0] + (hi[0] - lo[0]) * P[:, 0], lo[1] + (hi[1] - lo[1]) * P[:, 1])
    Xd = rng.uniform(size=(20, 2))
    yd = -branin(lo[0] + (hi[0] - lo[0]) * Xd[:, 0], lo[1] + (hi[1] - lo[1]) * Xd[:, 1])
    m_, s_ = yd.mean(), yd.std()
    gp = GP(Xd, (yd - m_) / s_, ell=0.25, s2=1.0, noise=1e-6)
    mu, sd = gp.predict(P)
    M = ((yd - m_) / s_).max()
    acqs = [("probability of improvement", acq_pi(mu, sd, M)), ("expected improvement", acq_ei(mu, sd, M)), ("upper confidence bound", acq_ucb(mu, sd, 2.0))]
    fig, axes = common.panel_grid(2, 3, size=(2.5, 2.3))
    panels = [("objective $-f$", fx), ("GP posterior mean", mu * s_ + m_), ("GP posterior sd", sd * s_)] + acqs
    for ax, (ttl, Z) in zip(axes.ravel(), panels):
        ax.imshow(Z.reshape(n, n), origin="lower", extent=[0, 1, 0, 1], cmap="viridis", aspect="auto")
        ax.plot(Xd[:, 0], Xd[:, 1], "wo", ms=3, mec="k", mew=0.4)
        ax.set_title(ttl, fontsize=8)
        ax.set_xticks([])
        ax.set_yticks([])
    for ax, (ttl, Z) in zip(axes[1], acqs):
        j = np.argmax(Z)
        ax.plot(P[j, 0], P[j, 1], "w^", ms=7, mec="k", mew=0.5)
    savefig(fig, CH, "fig6-11", out)


def bayesopt_1d(f, grid, n_init, n_iter, acq="ei", ell=0.12, noise=1e-6, beta=2.0, seed=0):
    """Sequential model-based optimisation (Algorithm 6.5) of f on a grid with a GP surrogate. Returns the queried indices."""
    rng = np.random.default_rng(seed)
    idx = list(rng.choice(len(grid), n_init, replace=False))
    for _ in range(n_iter):
        X = grid[idx]
        y = f(X)
        m_, s_ = y.mean(), y.std() + 1e-12
        gp = GP(X, (y - m_) / s_, ell=ell, s2=1.0, noise=noise)
        mu, sd = gp.predict(grid)
        M = ((y - m_) / s_).max()
        if acq == "ei":
            a = acq_ei(mu, sd, M)
        elif acq == "pi":
            a = acq_pi(mu, sd, M)
        elif acq == "ucb":
            a = acq_ucb(mu, sd, beta)
        else:
            a = gp.sample(grid, 1, rng)[0]
        a = np.where(np.isin(np.arange(len(grid)), idx), -np.inf, a)
        idx.append(int(np.argmax(a)))
    return np.array(idx)


def bayesopt_table(y, init_idx, n_total, acq="ei", ell=0.15, beta=2.0, noise=1e-6):
    """Bayesian optimisation over a tabulated objective y on an equally spaced grid in [0, 1] (the browser demonstration uses the
    same rule): start from init_idx, add the arg-max of the acquisition over the not yet queried grid points until n_total are queried."""
    y = np.asarray(y, float)
    grid = np.linspace(0, 1, len(y))
    idx = list(init_idx)
    while len(idx) < n_total:
        yo = y[idx]
        mu_y, sd_y = yo.mean(), yo.std() + 1e-12
        gp = GP(grid[idx], (yo - mu_y) / sd_y, ell=ell, s2=1.0, noise=noise)
        mu, sd = gp.predict(grid)
        M = ((yo - mu_y) / sd_y).max()
        a = {"ei": lambda: acq_ei(mu, sd, M), "pi": lambda: acq_pi(mu, sd, M), "ucb": lambda: acq_ucb(mu, sd, beta)}[acq]()
        a = np.where(np.isin(np.arange(len(grid)), idx), -np.inf, a)
        idx.append(int(np.argmax(a)))
    return idx


# =========================================================================== 6.7 derivative-free optimisation
def queens_attacks(s):
    """Number of attacking pairs of queens; s[c] is the row of the queen in column c."""
    s = np.asarray(s)
    n = len(s)
    i, j = np.triu_indices(n, 1)
    return int(np.sum((s[i] == s[j]) | (np.abs(s[i] - s[j]) == (j - i))))


def queens_neighbours(s):
    n = len(s)
    for c in range(n):
        for r in range(n):
            if r != s[c]:
                t = s.copy()
                t[c] = r
                yield t


def hill_climb_queens(s, rng):
    """Steepest ascent with random tie breaking, (6.187). Returns (solved, steps)."""
    cur = queens_attacks(s)
    steps = 0
    while cur > 0:
        nb = list(queens_neighbours(s))
        sc = np.array([queens_attacks(t) for t in nb])
        best = sc.min()
        if best >= cur:
            return False, steps
        s = nb[rng.choice(np.flatnonzero(sc == best))]
        cur = best
        steps += 1
    return True, steps


def tabu_queens(s, rng, tenure=40, c_max=60):
    """Tabu search (Algorithm 6.6): best non-tabu neighbour, even if worse; stop after c_max steps without progress."""
    best = queens_attacks(s)
    tabu = [tuple(s)]
    c = 0
    t = 0
    while best > 0 and c < c_max:
        nb = [u for u in queens_neighbours(s) if tuple(u) not in tabu]
        sc = np.array([queens_attacks(u) for u in nb])
        s = nb[rng.choice(np.flatnonzero(sc == sc.min()))]
        tabu.append(tuple(s))
        tabu = tabu[-tenure:]
        if sc.min() < best:
            best = sc.min()
            c = 0
        else:
            c += 1
        t += 1
    return best == 0, t


def queens_stats(n_runs=4000, seed=0, n_tabu=400):
    rng = np.random.default_rng(seed)
    succ, st_ok, st_bad = 0, [], []
    for _ in range(n_runs):
        ok, st = hill_climb_queens(rng.integers(0, 8, 8), rng)
        if ok:
            succ += 1
            st_ok.append(st)
        else:
            st_bad.append(st)
    tabu_ok, tabu_ok_steps, tabu_bad_steps = 0, [], []
    for _ in range(n_tabu):
        ok, st = tabu_queens(rng.integers(0, 8, 8), rng)
        if ok:
            tabu_ok += 1
            tabu_ok_steps.append(st)
        else:
            tabu_bad_steps.append(st)
    return dict(p_hill=succ / n_runs, steps_ok=float(np.mean(st_ok)), steps_bad=float(np.mean(st_bad)),
                p_tabu=tabu_ok / n_tabu, tabu_ok=float(np.mean(tabu_ok_steps)) if tabu_ok_steps else float("nan"),
                tabu_bad=float(np.mean(tabu_bad_steps)) if tabu_bad_steps else float("nan"), n_runs=n_runs, n_tabu=n_tabu)


def fig_x6_a(out=None):
    """8-queens: success of steepest-ascent hill climbing, random restarts and tabu search (Section 6.7.1)."""
    st = queens_stats(2500, 0, 250)
    p = st["p_hill"]
    R = 1.0 / p
    exp_steps = st["steps_ok"] + (R - 1) * st["steps_bad"]
    fig, axes = common.panel_grid(1, 2, size=(3.4, 2.6))
    ax = axes[0, 0]
    ax.bar(["hill climbing", "tabu search"], [st["p_hill"], st["p_tabu"]], color=[BLUE, GREEN])
    ax.set_ylim(0, 1.1)
    ax.set_ylabel("fraction of runs that solve 8-queens")
    for i, v in enumerate((st["p_hill"], st["p_tabu"])):
        ax.text(i, v + 0.02, "%.2f" % v, ha="center", fontsize=8)
    common.panel_label(ax, "a", "upper right")
    ax = axes[0, 1]
    rng = np.random.default_rng(7)
    tot = []
    for _ in range(600):
        steps = 0
        while True:
            ok, s_ = hill_climb_queens(rng.integers(0, 8, 8), rng)
            steps += s_
            if ok:
                break
        tot.append(steps)
    ax.hist(tot, bins=range(0, 90, 4), color=BLUE)
    ax.axvline(np.mean(tot), color=RED)
    ax.set_xlabel("total steps with random restarts")
    ax.set_ylabel("runs")
    ax.set_title("mean %.1f (formula %.1f)" % (np.mean(tot), exp_steps), fontsize=8.5)
    common.panel_label(ax, "b", "upper right")
    savefig(fig, CH, "figx6-a", out)


def fig_6_12(out=None):
    """Grid search against random search when only one of two hyperparameters matters (the idea of Figure 6.12)."""
    rng = np.random.default_rng(1)
    fig, axes = common.panel_grid(1, 3, size=(2.9, 2.6))
    n = 9
    g = (np.arange(3) + 0.5) / 3
    G = np.array([(a, b) for a in g for b in g])
    R = rng.uniform(size=(n, 2))
    for ax, P, ttl, lab in ((axes[0, 0], G, "grid layout", "a"), (axes[0, 1], R, "random layout", "b")):
        ax.plot(P[:, 0], P[:, 1], "ko", ms=4)
        ax.set_xlim(0, 1)
        ax.set_ylim(0, 1)
        ax.set_xlabel("important parameter")
        ax.set_ylabel("unimportant parameter")
        ax.set_title("%s: %d distinct values" % (ttl, len(np.unique(P[:, 0].round(6)))), fontsize=8.5)
        common.panel_label(ax, lab, "upper right")
    ax = axes[0, 2]
    budgets = np.array([4, 9, 16, 25, 36, 49, 64])
    res_g, res_r = [], []
    cs = rng.uniform(0.15, 0.85, 4000)               # random location of the important peak
    for b in budgets:
        k = int(round(np.sqrt(b)))
        xg = (np.arange(k) + 0.5) / k
        res_g.append(np.mean(1 - np.exp(-((xg[None, :] - cs[:, None]) / 0.05) ** 2).max(1)))
        xr = rng.uniform(size=(len(cs), b))
        res_r.append(np.mean(1 - np.exp(-((xr - cs[:, None]) / 0.05) ** 2).max(1)))
    ax.loglog(budgets, res_g, "o-", color=RED, ms=3, label="grid")
    ax.loglog(budgets, res_r, "o-", color=BLUE, ms=3, label="random")
    ax.set_xlabel("evaluations")
    ax.set_ylabel("shortfall of best value")
    ax.legend(fontsize=7)
    common.panel_label(ax, "c", "lower left")
    savefig(fig, CH, "fig6-12", out)


def cmaes(f, x0, sigma0, lam=None, iters=30, seed=0):
    """A compact CMA-ES (Hansen 2016 tutorial): rank-one and rank-mu covariance updates, cumulative step-size control.
    Returns a list of dicts with the population and the Gaussian (mean, sigma^2 C) in each generation."""
    rng = np.random.default_rng(seed)
    n = len(x0)
    lam = lam or 4 + int(3 * np.log(n))
    mu = lam // 2
    w = np.log(mu + 0.5) - np.log(np.arange(1, mu + 1))
    w /= w.sum()
    mueff = 1.0 / np.sum(w ** 2)
    cc = (4 + mueff / n) / (n + 4 + 2 * mueff / n)
    cs = (mueff + 2) / (n + mueff + 5)
    c1 = 2 / ((n + 1.3) ** 2 + mueff)
    cmu = min(1 - c1, 2 * (mueff - 2 + 1 / mueff) / ((n + 2) ** 2 + mueff))
    damps = 1 + 2 * max(0, np.sqrt((mueff - 1) / (n + 1)) - 1) + cs
    chiN = np.sqrt(n) * (1 - 1 / (4 * n) + 1 / (21 * n * n))
    m = np.array(x0, float)
    sigma = sigma0
    C = np.eye(n)
    pc = np.zeros(n)
    ps = np.zeros(n)
    hist = []
    for g in range(iters):
        D2, B = np.linalg.eigh(C)
        D = np.sqrt(np.maximum(D2, 1e-20))
        z = rng.standard_normal((lam, n))
        y = z @ (B * D).T
        x = m + sigma * y
        fx = np.array([f(xi) for xi in x])
        hist.append(dict(mean=m.copy(), sigma=sigma, C=C.copy(), pop=x.copy(), fx=fx.copy()))
        order = np.argsort(fx)
        yw = (w[:, None] * y[order[:mu]]).sum(0)
        m = m + sigma * yw
        invsqrtC = B @ np.diag(1 / D) @ B.T
        ps = (1 - cs) * ps + np.sqrt(cs * (2 - cs) * mueff) * (invsqrtC @ yw)
        hsig = np.linalg.norm(ps) / np.sqrt(1 - (1 - cs) ** (2 * (g + 1))) / chiN < 1.4 + 2 / (n + 1)
        pc = (1 - cc) * pc + hsig * np.sqrt(cc * (2 - cc) * mueff) * yw
        yk = y[order[:mu]]
        C = (1 - c1 - cmu) * C + c1 * (np.outer(pc, pc) + (1 - hsig) * cc * (2 - cc) * C) + cmu * (yk.T * w) @ yk
        sigma *= np.exp((cs / damps) * (np.linalg.norm(ps) / chiN - 1))
    hist.append(dict(mean=m.copy(), sigma=sigma, C=C.copy(), pop=None, fx=None))
    return hist


def cem(f, mu0, S0, n_pop=60, n_elite=12, iters=20, seed=0):
    """The cross-entropy method with a Gaussian model (Section 6.7.5), minimising f."""
    rng = np.random.default_rng(seed)
    mu, S = np.array(mu0, float), np.array(S0, float)
    hist = [(mu.copy(), S.copy())]
    for _ in range(iters):
        X = rng.multivariate_normal(mu, S, n_pop)
        fx = np.array([f(x) for x in X])
        E = X[np.argsort(fx)[:n_elite]]
        mu = E.mean(0)
        S = np.cov(E.T, bias=True) + 1e-10 * np.eye(len(mu))
        hist.append((mu.copy(), S.copy()))
    return hist


def _banana(x):
    return (1 - x[0]) ** 2 + 8 * (x[1] - x[0] ** 2) ** 2


def fig_6_17(out=None):
    """CMA-ES on a two-dimensional function (a stretched Rosenbrock valley): populations and fitted Gaussians."""
    hist = cmaes(_banana, [-1.5, 2.0], 0.5, lam=14, iters=40, seed=3)
    gens = (0, 4, 10, 20, 35)
    fig, axes = common.panel_grid(1, len(gens), size=(2.2, 2.3))
    gx, gy = np.meshgrid(np.linspace(-2.2, 2.2, 150), np.linspace(-0.6, 3.2, 150))
    Z = (1 - gx) ** 2 + 8 * (gy - gx ** 2) ** 2
    for ax, g in zip(axes[0], gens):
        ax.contour(gx, gy, np.log10(Z + 1e-3), levels=12, colors="0.8", linewidths=0.6)
        h = hist[g]
        ax.plot(h["pop"][:, 0], h["pop"][:, 1], "o", color=BLUE, ms=2.5)
        ex, ey = common.ellipse_xy(h["mean"], h["sigma"] ** 2 * h["C"], 1.0)
        ax.plot(ex, ey, color=ORANGE, ls="--", lw=1.2)
        ax.plot(1, 1, "k*", ms=6)
        ax.set_title("generation %d" % g, fontsize=8)
        ax.set_xlim(-2.2, 2.2)
        ax.set_ylim(-0.6, 3.2)
        ax.set_xticks([])
        ax.set_yticks([])
    savefig(fig, CH, "fig6-17", out)


# =========================================================================== 6.8 optimal transport
def ot_lp(a, b, C):
    """Exact discrete optimal transport (Kantorovich LP (6.192)); returns the plan P and the cost <P, C>."""
    n, m = C.shape
    A = np.zeros((n + m, n * m))
    for i in range(n):
        A[i, i * m:(i + 1) * m] = 1
    for j in range(m):
        A[n + j, j::m] = 1
    res = optimize.linprog(C.ravel(), A_eq=A, b_eq=np.concatenate([a, b]), bounds=(0, None), method="highs")
    P = res.x.reshape(n, m)
    return P, float((P * C).sum())


def sinkhorn(a, b, C, gamma, n_iter=2000, tol=1e-10):
    """Sinkhorn in the log domain, (6.217). Returns plan, potentials (f, g), the iteration count and the marginal error."""
    f = np.zeros(len(a))
    g = np.zeros(len(b))
    la, lb = np.log(a), np.log(b)
    err = np.inf
    for it in range(1, n_iter + 1):
        f = gamma * (la - special.logsumexp((g[None, :] - C) / gamma, axis=1))
        g = gamma * (lb - special.logsumexp((f[:, None] - C) / gamma, axis=0))
        P = np.exp((f[:, None] + g[None, :] - C) / gamma)
        err = np.abs(P.sum(1) - a).sum()          # the column marginals are exact after the g update
        if err < tol:
            break
    return P, f, g, it, err


def shannon(p):
    p = np.asarray(p, float)
    p = p[p > 0]
    return float(-(p * np.log(p)).sum())


def ot_reg_primal(P, C, a, b, gamma):
    """The regularised objective (6.214): <P, C> - gamma H(P) + gamma (H(a) + H(b)) = <P, C> + gamma KL(P || a b')."""
    return float((P * C).sum() - gamma * shannon(P) + gamma * (shannon(a) + shannon(b)))


def ot_reg_dual(f, g, C, a, b, gamma):
    """The dual (6.215): f'a + g'b - gamma (e^{f/gamma})' K e^{g/gamma} + gamma (1 + H(a) + H(b)), K = e^{-C/gamma}."""
    K = np.exp(-C / gamma)
    return float(f @ a + g @ b - gamma * np.exp(f / gamma) @ K @ np.exp(g / gamma) + gamma * (1 + shannon(a) + shannon(b)))


def ot_1d_monotone(x, a, y, b):
    """The monotone (north-west corner) coupling of two weighted point sets on the line; optimal for every convex cost."""
    ix, iy = np.argsort(x), np.argsort(y)
    a2, b2 = a[ix].copy(), b[iy].copy()
    P = np.zeros((len(x), len(y)))
    i = j = 0
    while i < len(a2) and j < len(b2):
        m = min(a2[i], b2[j])
        P[ix[i], iy[j]] += m
        a2[i] -= m
        b2[j] -= m
        if a2[i] <= 1e-15:
            i += 1
        if b2[j] <= 1e-15:
            j += 1
    return P


def bures_w2sq(m1, S1, m2, S2):
    """Squared 2-Wasserstein distance between two Gaussians, (6.210)-(6.211)."""
    r = linalg.sqrtm(S1)
    cross = linalg.sqrtm(r @ S2 @ r).real
    return float(np.sum((m1 - m2) ** 2) + np.trace(S1 + S2 - 2 * cross))


def gaussian_monge_matrix(S1, S2):
    """The matrix A of the optimal map T(x) = A (x - m1) + m2 between N(m1, S1) and N(m2, S2), (6.212)."""
    r = linalg.sqrtm(S1).real
    ri = np.linalg.inv(r)
    return ri @ linalg.sqrtm(r @ S2 @ r).real @ ri


def fig_6_18(out=None):
    """Optimal matching, the Kantorovich plan between weighted point clouds, and a Monge map in one dimension."""
    rng = np.random.default_rng(2)
    fig, axes = common.panel_grid(1, 3, size=(3.1, 2.8))
    ax = axes[0, 0]
    X = rng.uniform(0, 1, (5, 2)) * [1, 1]
    Y = rng.uniform(0, 1, (5, 2)) + [0.0, 0.0]
    from scipy.optimize import linear_sum_assignment
    C = ((X[:, None] - Y[None]) ** 2).sum(-1) ** 0.5
    r, c = linear_sum_assignment(C)
    for i, j in zip(r, c):
        ax.plot([X[i, 0], Y[j, 0]], [X[i, 1], Y[j, 1]], color=GREY, lw=1)
    ax.plot(*X.T, "o", color=BLUE, ms=6)
    ax.plot(*Y.T, "s", color=RED, ms=6)
    ax.set_title("optimal matching", fontsize=9)
    ax.set_xticks([])
    ax.set_yticks([])
    common.panel_label(ax, "a", "upper right")
    ax = axes[0, 1]
    X = rng.uniform(0, 1, (6, 2))
    Y = rng.uniform(0, 1, (4, 2))
    a = rng.dirichlet(np.ones(6) * 3)
    b = rng.dirichlet(np.ones(4) * 3)
    C = ((X[:, None] - Y[None]) ** 2).sum(-1)
    P, cost = ot_lp(a, b, C)
    for i in range(6):
        for j in range(4):
            if P[i, j] > 1e-9:
                ax.plot([X[i, 0], Y[j, 0]], [X[i, 1], Y[j, 1]], color=GREY, lw=0.5 + 14 * P[i, j])
    ax.scatter(*X.T, s=700 * a, color=BLUE, zorder=3)
    ax.scatter(*Y.T, s=700 * b, color=RED, marker="s", zorder=3)
    ax.set_title("Kantorovich plan", fontsize=9)
    ax.set_xticks([])
    ax.set_yticks([])
    common.panel_label(ax, "b", "upper right")
    ax = axes[0, 2]
    x = np.linspace(-4, 5, 500)
    pdf_mu = lambda t: 0.5 * stats.norm.pdf(t, -1.2, 0.6) + 0.5 * stats.norm.pdf(t, 1.0, 0.8)
    cdf_mu = lambda t: 0.5 * stats.norm.cdf(t, -1.2, 0.6) + 0.5 * stats.norm.cdf(t, 1.0, 0.8)
    T = stats.norm.ppf(np.clip(cdf_mu(x), 1e-9, 1 - 1e-9), 2.0, 1.0)
    ax.fill_between(x, 0, pdf_mu(x), color=BLUE, alpha=0.4, label="$\\mu$")
    ax.fill_between(x, 0, stats.norm.pdf(x, 2.0, 1.0), color=RED, alpha=0.3, label="$\\nu$")
    ax.plot(x, (T - T.min()) / (T.max() - T.min()) * 0.8, color="k", lw=1.2, label="$T=Q_\\nu\\circ F_\\mu$ (rescaled)")
    ax.set_title("Monge map in 1-D", fontsize=9)
    ax.legend(fontsize=6.5, loc="upper left")
    ax.set_xlim(-4, 5)
    common.panel_label(ax, "c", "upper right")
    savefig(fig, CH, "fig6-18", out)


def fig_x6_d(out=None):
    """Entropic optimal transport between two histograms: the Sinkhorn plan for several gamma, and the cost against gamma."""
    x = np.linspace(0, 1, 50)
    a = 0.6 * stats.norm.pdf(x, 0.25, 0.06) + 0.4 * stats.norm.pdf(x, 0.6, 0.08)
    b = 0.5 * stats.norm.pdf(x, 0.4, 0.07) + 0.5 * stats.norm.pdf(x, 0.8, 0.05)
    a, b = a / a.sum(), b / b.sum()
    C = (x[:, None] - x[None, :]) ** 2
    P0, c0 = ot_lp(a, b, C)
    fig, axes = common.panel_grid(1, 4, size=(2.3, 2.3))
    for ax, gam, lab in zip(axes[0, :3], (0.1, 0.01, 0.001), "abc"):
        P, f, g, it, err = sinkhorn(a, b, C, gam, 20000, 1e-9)
        ax.imshow(P.T, origin="lower", extent=[0, 1, 0, 1], cmap="Blues", aspect="auto")
        ax.set_title("$\\gamma=%g$" % gam, fontsize=9)
        ax.set_xlabel("source")
        ax.set_ylabel("target")
        common.panel_label(ax, lab, "upper right")
    ax = axes[0, 3]
    gs = np.logspace(-3, 0, 10)
    costs, iters = [], []
    for gam in gs:
        P, f, g, it, err = sinkhorn(a, b, C, gam, 20000, 1e-9)
        costs.append((P * C).sum())
        iters.append(it)
    ax.semilogx(gs, costs, "o-", color=BLUE, ms=3, label="$\\langle P_\\gamma,C\\rangle$")
    ax.axhline(c0, color=RED, label="exact OT")
    ax.set_xlabel("$\\gamma$")
    ax.legend(fontsize=7)
    common.panel_label(ax, "d", "lower right")
    fig.subplots_adjust(wspace=0.45)
    savefig(fig, CH, "figx6-d", out)


# =========================================================================== 6.9 submodular optimisation
def greedy_max(f, n, k):
    """The greedy algorithm (6.223) for max f(X) s.t. |X| <= k, f monotone submodular on subsets of range(n)."""
    X = []
    for _ in range(k):
        best, bv = None, -np.inf
        base = f(X)
        for v in range(n):
            if v not in X:
                g = f(X + [v]) - base
                if g > bv:
                    best, bv = v, g
        X.append(best)
    return X


def facility_location(sim):
    """f(A) = sum_v max_{a in A} sim[a, v] (0 for the empty set)."""
    def f(A):
        return float(sim[list(A)].max(0).sum()) if len(A) else 0.0
    return f


def coverage_fn(sets):
    def f(A):
        return float(len(set().union(*[sets[a] for a in A]))) if len(A) else 0.0
    return f


def graph_cut_fn(W):
    n = len(W)

    def f(A):
        A = list(A)
        mask = np.zeros(n, bool)
        mask[A] = True
        return float(W[np.ix_(mask, ~mask)].sum())
    return f


def logdet_fn(M):
    def f(A):
        A = list(A)
        return float(np.linalg.slogdet(M[np.ix_(A, A)])[1]) if len(A) else 0.0
    return f


def submodularity_violation(f, n):
    """Largest violation of f(X) + f(Y) >= f(X u Y) + f(X n Y) over all pairs of subsets (brute force; n <= 8)."""
    subsets = [frozenset(c) for r in range(n + 1) for c in itertools.combinations(range(n), r)]
    val = {S: f(sorted(S)) for S in subsets}
    worst = -np.inf
    for X in subsets:
        for Y in subsets:
            worst = max(worst, val[X | Y] + val[X & Y] - val[X] - val[Y])
    return float(worst)


def brute_force_max(f, n, k):
    return max(f(list(c)) for c in itertools.combinations(range(n), k))


TCLM = {"": 0, "c": 3, "l": 1, "m": 1, "t": 2, "cl": 4, "cm": 5, "ct": 4, "lm": 2, "lt": 5, "mt": 5,
        "clm": 6, "clt": 7, "cmt": 8, "lmt": 7, "clmt": 9}   # the coffee, lemon, milk, tea values of Figure 6.19


def tclm(A):
    return TCLM["".join(sorted(A, key="clmt".index))]


def fig_6_19(out=None):
    """The value function on subsets of {coffee, lemon, milk, tea} as a lattice, with the three kinds of relationship."""
    fig, ax = plt.subplots(figsize=(6.4, 3.6))
    layers = [[""], ["c", "l", "m", "t"], ["cl", "cm", "ct", "lm", "lt", "mt"], ["clm", "clt", "cmt", "lmt"], ["clmt"]]
    pos = {}
    for r, L in enumerate(layers):
        for k, s in enumerate(L):
            pos[s] = ((k + 0.5) / len(L) * 4 - 2, r)
    for s in pos:
        for v in "clmt":
            if v not in s:
                t = "".join(sorted(s + v, key="clmt".index))
                ax.plot([pos[s][0], pos[t][0]], [pos[s][1], pos[t][1]], color="0.8", lw=0.8, zorder=1)
    for s, (x, y) in pos.items():
        ax.text(x, y, "{%s}\n%d" % (",".join(s) if s else "", TCLM[s]), ha="center", va="center", fontsize=7,
                bbox=dict(boxstyle="round,pad=0.25", fc="white", ec=BLUE), zorder=2)
    ax.set_xlim(-2.4, 2.4)
    ax.set_ylim(-0.5, 4.5)
    ax.axis("off")
    savefig(fig, CH, "fig6-19", out)


def fig_6_20(out=None):
    """Greedy facility-location selection of 10 out of 1000 planar points against three random 10-subsets."""
    rng = np.random.default_rng(6)
    centres = rng.uniform(-4, 4, (7, 2))
    P = np.concatenate([c + rng.normal(0, 0.55, (143, 2)) for c in centres])[:1000]
    D = np.linalg.norm(P[:, None] - P[None], axis=-1)
    sim = np.exp(-D)
    f = facility_location(sim)
    sel = greedy_max(f, len(P), 10)
    fig, axes = common.panel_grid(1, 4, size=(2.5, 2.5))
    ax = axes[0, 0]
    ax.plot(*P.T, ".", color="0.75", ms=2)
    ax.plot(*P[sel].T, "*", color=GREEN, ms=9)
    for k, i in enumerate(sel):
        ax.text(P[i, 0] + 0.15, P[i, 1] + 0.1, str(k + 1), fontsize=6.5)
    ax.set_title("greedy, $f=%.0f$" % f(sel), fontsize=8.5)
    for j in range(1, 4):
        ax = axes[0, j]
        R = list(rng.choice(len(P), 10, replace=False))
        ax.plot(*P.T, ".", color="0.75", ms=2)
        ax.plot(*P[R].T, "*", color=ORANGE, ms=9)
        ax.set_title("random, $f=%.0f$" % f(R), fontsize=8.5)
    for ax in axes[0]:
        ax.set_xticks([])
        ax.set_yticks([])
    savefig(fig, CH, "fig6-20", out)


# =========================================================================== Supplement 7.1 proximal methods
def soft_threshold(x, lam):
    return np.sign(x) * np.maximum(np.abs(x) - lam, 0.0)                      # (7.26)


def block_soft_threshold(x, lam):
    n = np.linalg.norm(x)
    return np.zeros_like(x) if n <= lam else (1 - lam / n) * x                # (7.28)


def svt(A, lam):
    U, s, Vt = np.linalg.svd(A, full_matrices=False)
    return (U * np.maximum(s - lam, 0)) @ Vt                                   # (7.31)


def proj_psd(A):
    w, V = np.linalg.eigh((A + A.T) / 2)
    return (V * np.maximum(w, 0)) @ V.T                                        # (7.32)


def proj_simplex(x):
    """Euclidean projection onto the probability simplex by sorting: (x - nu)_+ with the right nu, (7.33)."""
    u = np.sort(x)[::-1]
    css = np.cumsum(u) - 1
    k = np.arange(1, len(x) + 1)
    rho = np.flatnonzero(u - css / k > 0)[-1]
    nu = css[rho] / (rho + 1)
    return np.maximum(x - nu, 0)


def moreau_abs(x, eta=1.0):
    """Moreau envelope of |x|: the Huber function (7.9)."""
    x = np.asarray(x, float)
    return np.where(np.abs(x) <= eta, x ** 2 / (2 * eta), np.abs(x) - eta / 2)


def moreau_numeric(f, x, eta=1.0):
    z = np.linspace(-10, 10, 400001)
    return np.min(f(z) + (z - x) ** 2 / (2 * eta))


def ista(A, b, lam, n_iter=500, accel=False):
    """ISTA (7.56) or, with accel=True, FISTA, for 1/2 ||A theta - b||^2 + lam ||theta||_1. Returns the objective history."""
    L = np.linalg.norm(A, 2) ** 2
    th = np.zeros(A.shape[1])
    z = th.copy()
    tk = 1.0
    obj = lambda t: 0.5 * np.sum((A @ t - b) ** 2) + lam * np.abs(t).sum()
    hist = [obj(th)]
    for _ in range(n_iter):
        th_new = soft_threshold(z - A.T @ (A @ z - b) / L, lam / L)
        if accel:
            tk_new = (1 + np.sqrt(1 + 4 * tk * tk)) / 2
            z = th_new + (tk - 1) / tk_new * (th_new - th)
            tk = tk_new
        else:
            z = th_new
        th = th_new
        hist.append(obj(th))
    return th, np.array(hist)


def admm_lasso(A, b, lam, rho=1.0, n_iter=500):
    """ADMM in the scaled form (7.66)-(7.68) for the lasso, with L_s = 1/2||A x - b||^2 and L_r = lam ||z||_1."""
    n = A.shape[1]
    x = np.zeros(n)
    z = np.zeros(n)
    u = np.zeros(n)
    M = np.linalg.inv(A.T @ A + rho * np.eye(n))
    obj = lambda t: 0.5 * np.sum((A @ t - b) ** 2) + lam * np.abs(t).sum()
    hist = [obj(z)]
    for _ in range(n_iter):
        x = M @ (A.T @ b + rho * (z - u))
        z = soft_threshold(x + u, lam / rho)
        u = u + x - z
        hist.append(obj(z))
    return z, np.array(hist)


def lasso_problem(seed=0, n=100, d=200, k=10, noise=0.1):
    rng = np.random.default_rng(seed)
    A = rng.normal(size=(n, d)) / np.sqrt(n)
    th = np.zeros(d)
    th[rng.choice(d, k, replace=False)] = rng.normal(size=k) * 2
    b = A @ th + noise * rng.normal(size=n)
    return A, b, th


def fig_x6_b(out=None):
    """Proximal methods on a lasso problem: ISTA, FISTA and ADMM (objective gap against iterations)."""
    A, b, th = lasso_problem()
    lam = 0.1
    _, h_ista = ista(A, b, lam, 2000)
    _, h_fista = ista(A, b, lam, 2000, accel=True)
    _, h_admm = admm_lasso(A, b, lam, 1.0, 2000)
    fstar = min(h_ista.min(), h_fista.min(), h_admm.min())
    fig, axes = common.panel_grid(1, 2, size=(3.4, 2.7))
    ax = axes[0, 0]
    for h, c, nm in ((h_ista, RED, "ISTA"), (h_fista, BLUE, "FISTA"), (h_admm, GREEN, "ADMM ($\\rho=1$)")):
        ax.loglog(np.arange(1, len(h) + 1), np.maximum(h - fstar, 1e-14), color=c, label=nm)
    ax.set_xlabel("iteration")
    ax.set_ylabel("objective gap")
    ax.legend(fontsize=7)
    common.panel_label(ax, "a", "lower left")
    ax = axes[0, 1]
    th_hat, _ = ista(A, b, lam, 3000, accel=True)
    ax.stem(np.flatnonzero(th), th[th != 0], linefmt="k-", markerfmt="ko", basefmt=" ", label="true")
    nz = np.flatnonzero(th_hat)
    ax.plot(nz, th_hat[nz], "x", color=BLUE, label="lasso")
    ax.set_xlabel("coordinate")
    ax.legend(fontsize=7)
    common.panel_label(ax, "b", "upper right")
    savefig(fig, CH, "figx6-b", out)


def rpca_admm(A, gL, gS, n_iter=500, eta=1.0):
    """Robust PCA by the ADMM matrix-decomposition scheme (7.69)-(7.73) with J = 3 blocks:
    X1 = L (nuclear norm), X2 = S (l1 norm), X3 = A - L - S (squared Frobenius norm). Returns L, S and the objective history."""
    J = 3
    X = [np.zeros_like(A), np.zeros_like(A), A.copy()]
    U = np.zeros_like(A)
    obj = lambda L, S: np.sum((A - L - S) ** 2) + gL * np.linalg.svd(L, compute_uv=False).sum() + gS * np.abs(S).sum()
    hist = []
    for _ in range(n_iter):
        Xbar = sum(X) / J
        V = [Xj - Xbar + A / J - U for Xj in X]
        X = [svt(V[0], eta * gL), soft_threshold(V[1], eta * gS), V[2] / (1 + 2 * eta)]
        Xbar = sum(X) / J
        U = U + Xbar - A / J
        hist.append(obj(X[0], X[1]))
    return X[0], X[1], np.array(hist)


def synthetic_video(h=24, w=32, T=40, seed=0):
    """Frames = static low-rank background + a small bright block moving across: columns of the data matrix are frames."""
    rng = np.random.default_rng(seed)
    yy, xx = np.mgrid[0:h, 0:w]
    bg = 0.4 + 0.3 * np.sin(2 * np.pi * xx / w) * np.cos(np.pi * yy / h)
    frames, fg = [], []
    for t in range(T):
        f = np.zeros((h, w))
        cx = int(2 + (w - 8) * t / (T - 1))
        f[8:14, cx:cx + 5] = 1.0
        fg.append(f)
        frames.append(bg + 0.9 * f + 0.01 * rng.normal(size=(h, w)))
    return np.array(frames).reshape(T, -1).T, bg.ravel(), np.array(fg).reshape(T, -1).T, (h, w)


def fig_S7_3(out=None):
    """Robust PCA by ADMM on synthetic frames (a CPU-sized stand-in for the surveillance video of Supplement Figure 7.3)."""
    A, bg, fg, (h, w) = synthetic_video()
    L, S, hist = rpca_admm(A, 6.0, 0.35, 300)
    fig, axes = common.panel_grid(3, 4, size=(1.9, 1.5))
    for r, t in enumerate((5, 20, 34)):
        for c, (M, ttl) in enumerate(((A, "frame"), (L, "low rank"), (S, "sparse"), (np.abs(S) > 0.25, "mask"))):
            ax = axes[r, c]
            ax.imshow(M[:, t].reshape(h, w), cmap="gray", vmin=0 if c != 2 else -0.2, vmax=1)
            ax.set_xticks([])
            ax.set_yticks([])
            if r == 0:
                ax.set_title(ttl, fontsize=8)
    savefig(fig, CH, "figS7-3", out)


def truncated_sgd(A, y, eta, n_epoch, truncate, seed=0):
    """SGD for the sum of 1/2 (a_n' theta - y_n)^2 with the plain step or the truncated step (7.40) with A_t = I."""
    rng = np.random.default_rng(seed)
    n, d = A.shape
    th = np.zeros(d)
    losses = [0.5 * np.mean((A @ th - y) ** 2)]
    for _ in range(n_epoch):
        for i in rng.permutation(n):
            r = A[i] @ th - y[i]
            g = r * A[i]
            Lt = 0.5 * r * r
            gg = g @ g
            step = min(eta, Lt / gg) if (truncate and gg > 0) else eta
            th = th - step * g
        losses.append(0.5 * np.mean((A @ th - y) ** 2))
        if not np.isfinite(losses[-1]) or losses[-1] > 1e12:
            losses[-1] = np.inf
            break
    return np.array(losses)


def fig_S7_2(out=None):
    """Truncated SGD is stable for any step size on an interpolation problem (a CPU-sized stand-in for Supplement Figure 7.2)."""
    rng = np.random.default_rng(0)
    n, d = 60, 120
    A = rng.normal(size=(n, d))
    y = A @ rng.normal(size=d) / np.sqrt(d)
    etas = np.logspace(-3.5, 0.5, 25)
    fin_plain = [truncated_sgd(A, y, e, 20, False)[-1] for e in etas]
    fin_trunc = [truncated_sgd(A, y, e, 20, True)[-1] for e in etas]
    fig, ax = plt.subplots(figsize=(4.4, 2.9))
    fp = np.array(fin_plain, float)
    ft = np.array(fin_trunc, float)
    ok = np.isfinite(fp) & (fp < 1e3)
    ax.loglog(etas[ok], fp[ok], "o-", color=RED, ms=3, label="SGD")
    ax.loglog(etas[~ok], np.full((~ok).sum(), 2e2), "x", color=RED, ms=5, label="SGD diverged")
    ax.loglog(etas, ft, "o-", color=BLUE, ms=3, label="truncated SGD")
    ax.set_ylim(1e-9, 1e3)
    ax.set_xlabel("step size $\\eta$")
    ax.set_ylabel("loss after 20 epochs")
    ax.legend(fontsize=8)
    ax.axvline(2 / np.max((A ** 2).sum(1)), color=GREY, lw=0.8, ls=":")
    savefig(fig, CH, "figS7-2", out)


# =========================================================================== Supplement 7.3 conjugate duality
def conj_numeric(f, lam, grid):
    return np.max(lam * grid - f(grid))


def fig_S7_4(out=None):
    """Linear lower bounds lambda x - f*(lambda) of a non-convex function, tight at the point where the slope matches."""
    f = lambda x: 0.2 * x ** 2 + 0.8 * np.sin(1.5 * x) * 0 + 0.6 * np.cos(1.7 * x) + 0.5
    xs = np.linspace(-3.5, 3.5, 1000)
    fig, ax = plt.subplots(figsize=(4.4, 2.9))
    ax.plot(xs, f(xs), color=RED, label="$f(x)$")
    for lam, c in ((-0.8, BLUE), (0.4, GREEN), (1.2, PURPLE)):
        fs = conj_numeric(f, lam, xs)
        ax.plot(xs, lam * xs - fs, color=c, lw=1.0, ls="--", label="$\\lambda=%g$" % lam)
        x_t = xs[np.argmax(lam * xs - f(xs))]
        ax.plot(x_t, f(x_t), "o", color=c, ms=4)
    ax.set_ylim(-4, 5)
    ax.legend(fontsize=7, ncol=2)
    ax.set_xlabel("$x$")
    savefig(fig, CH, "figS7-4", out)


def fig_S7_5(out=None):
    """The conjugate of exp(-x), (7.85), and its linear lower bounds."""
    xs = np.linspace(-1, 3.5, 300)
    fig, axes = common.panel_grid(1, 2, size=(3.3, 2.6))
    ax = axes[0, 0]
    ax.plot(xs, np.exp(-xs), color=RED)
    for lam, c in ((-0.25, BLUE), (-0.6, GREEN), (-1.5, PURPLE)):
        xl = -np.log(-lam)
        fd = -lam * np.log(-lam) + lam
        ax.plot(xs, lam * xs - fd, color=c, lw=1, label="$\\lambda=%g$" % lam)
        ax.plot(xl, np.exp(-xl), "o", color=c, ms=4)
    ax.set_ylim(0, 2.5)
    ax.legend(fontsize=7)
    ax.set_xlabel("$x$")
    common.panel_label(ax, "a", "upper right")
    ax = axes[0, 1]
    lam = np.linspace(-3, -0.02, 300)
    ax.plot(lam, -lam * np.log(-lam) + lam, color=BLUE, label="$f^\\dagger(\\lambda)$")
    ax.set_xlabel("$\\lambda$")
    ax.legend(fontsize=7)
    common.panel_label(ax, "b", "lower right")
    savefig(fig, CH, "figS7-5", out)


def sigmoid_upper(x, eta):
    """Exponential upper bound (7.102): sigma(x) <= exp(eta x - f+(eta)), f+(eta) = -eta ln eta - (1-eta) ln(1-eta)."""
    return np.exp(eta * x + eta * np.log(eta) + (1 - eta) * np.log(1 - eta))


def sigmoid_lower(x, xi):
    """Quadratic lower bound (7.110) of Jaakkola and Jordan: sigma(xi) exp((x - xi)/2 - lambda(xi)(x^2 - xi^2))."""
    lam = np.tanh(xi / 2) / (4 * xi)
    return common.sigmoid(xi) * np.exp((x - xi) / 2 - lam * (x ** 2 - xi ** 2))


def fig_S7_6(out=None):
    """Exponential upper bounds and a quadratic lower bound on the sigmoid."""
    x = np.linspace(-6, 6, 400)
    fig, axes = common.panel_grid(1, 2, size=(3.3, 2.6))
    ax = axes[0, 0]
    ax.plot(x, common.sigmoid(x), color="k")
    for eta, c in ((0.2, BLUE), (0.7, RED)):
        ax.plot(x, np.minimum(sigmoid_upper(x, eta), 1.3), color=c, ls="--", label="$\\eta=%g$" % eta)
    ax.set_ylim(0, 1.2)
    ax.legend(fontsize=7)
    ax.set_xlabel("$x$")
    common.panel_label(ax, "a", "upper left")
    ax = axes[0, 1]
    ax.plot(x, common.sigmoid(x), color="k")
    ax.plot(x, sigmoid_lower(x, 2.5), color=RED, ls="--", label="$\\xi=2.5$")
    ax.axvline(2.5, color=GREY, lw=0.5)
    ax.axvline(-2.5, color=GREY, lw=0.5)
    ax.set_ylim(0, 1.05)
    ax.legend(fontsize=7)
    ax.set_xlabel("$x$")
    common.panel_label(ax, "b", "upper left")
    savefig(fig, CH, "figS7-6", out)


def fig_S7_1(out=None):
    """The Moreau envelope of |x| (the Huber function) and the proximal operators of the l1 norm."""
    x = np.linspace(-3, 3, 400)
    fig, axes = common.panel_grid(1, 2, size=(3.3, 2.6))
    ax = axes[0, 0]
    ax.plot(x, np.abs(x), "k", label="$|x|$")
    ax.plot(x, moreau_abs(x, 1.0), color=RED, ls=":", label="Moreau envelope, $\\eta=1$")
    x0 = 1.5
    z = np.linspace(-1.5, 3, 200)
    ax.plot(z, np.abs(z) + 0.5 * (z - x0) ** 2, color="0.6", lw=0.8, label="$f^1_{x_0}(z)$")
    zs = soft_threshold(x0, 1.0)
    ax.plot(zs, abs(zs) + 0.5 * (zs - x0) ** 2, "x", color=RED, ms=7)
    ax.plot(x0, abs(x0), "ks", ms=4)
    ax.set_ylim(0, 3)
    ax.legend(fontsize=6.5, loc="upper center")
    common.panel_label(ax, "a", "lower right")
    ax = axes[0, 1]
    for lam, c in ((0.5, BLUE), (1.0, RED)):
        ax.plot(x, soft_threshold(x, lam), color=c, label="$\\lambda=%g$" % lam)
    ax.plot(x, x, color="0.7", lw=0.6)
    ax.set_xlabel("$x$")
    ax.set_ylabel("prox$_{\\lambda\\|\\cdot\\|_1}(x)$")
    ax.legend(fontsize=7)
    common.panel_label(ax, "b", "lower right")
    savefig(fig, CH, "figS7-1", out)


# =========================================================================== Supplement 7.4 the Bayesian learning rule
def nat_params(m, v):
    """Natural parameters of N(m, v): (m/v, -1/(2v))."""
    return np.array([m / v, -0.5 / v])


def mean_params(m, v):
    """Moment parameters of N(m, v): (m, v + m^2)."""
    return np.array([m, v + m * m])


def blr_gaussian_step(m, S, grad_exp, hess_exp, eta):
    """One natural-gradient step on the BLR objective (7.121) for q = N(m, S^{-1}), (7.144) and (7.147)."""
    S_new = (1 - eta) * S + eta * hess_exp
    m_new = m - eta * np.linalg.solve(S_new, grad_exp)
    return m_new, S_new


# =========================================================================== data exported for the demonstrations
def export_json():
    from sklearn import datasets
    from sklearn.linear_model import LogisticRegression
    from sklearn.model_selection import cross_val_score
    from sklearn.pipeline import make_pipeline
    from sklearn.preprocessing import StandardScaler
    os.makedirs(DATA_OUT, exist_ok=True)
    r = lambda a, k=6: np.round(np.asarray(a, float), k).tolist()
    # --- natural gradient demo: sepal length of the 50 iris versicolor
    iris = datasets.load_iris()
    x = iris.data[iris.target == 1, 0]
    d1 = dict(x=r(x, 2), mean=float(x.mean()), sd=float(x.std()),
              F=r(NGD_F, 9), J=r(NGD_J, 9), ref={})
    th_sd, th_ng, l_sd, l_ng = ngd_example(n_iter=60, eta_ng=0.2)
    d1["ref"]["coupled"] = dict(loss_sd_10=float(l_sd[10]), loss_sd_60=float(l_sd[60]), loss_ng_10=float(l_ng[10]), loss_ng_60=float(l_ng[60]),
                                theta_ng_10=r(th_ng[10]), theta_sd_10=r(th_sd[10]))
    with open(os.path.join(DATA_OUT, "ch06-ngd.json"), "w") as f:
        json.dump(d1, f, separators=(",", ":"))
    # --- Bayesian optimisation demo: 5-fold CV log-loss of logistic regression against log10 C on the breast-cancer data
    bc = datasets.load_breast_cancer()
    grid = np.linspace(-4, 2, 61)
    cv = []
    for lc in grid:
        mdl = make_pipeline(StandardScaler(), LogisticRegression(C=10 ** lc, max_iter=2000))
        cv.append(cross_val_score(mdl, bc.data, bc.target, cv=5, scoring="neg_log_loss").mean())
    d2 = dict(logC=r(grid, 4), score=r(cv, 6), ref={})
    grid1 = np.linspace(0, 1, 101)
    y1 = f_bo1d(grid1)
    yc = np.asarray(cv)
    refs = {}
    for nm, yy, ini, n_tot, acq, ell in (("cv_ei", yc, [6, 30], 10, "ei", 0.15), ("cv_ucb", yc, [6, 30], 10, "ucb", 0.15),
                                         ("syn_ei", y1, [12, 45], 9, "ei", 0.1), ("syn_ei_long", y1, [12, 45], 9, "ei", 0.5),
                                         ("cv_pi", yc, [6, 30], 10, "pi", 0.15)):
        idx = bayesopt_table(yy, ini, n_tot, acq, ell)
        refs[nm] = dict(idx=idx, best=float(yy[idx].max()), opt=float(yy.max()))
    Xr = np.array([0.12, 0.45, 0.9])
    gp = GP(Xr, f_bo1d(Xr) - 0.5, ell=0.15, s2=1.0, noise=1e-4)
    mu, sd = gp.predict(np.array([0.3, 0.7]))
    d2["f1d"] = r(y1, 8)
    d2["ref"] = dict(runs=refs, gp_mu=r(mu, 10), gp_sd=r(sd, 10), ei=r(acq_ei(mu, sd, 0.0), 10))
    with open(os.path.join(DATA_OUT, "ch06-bayesopt.json"), "w") as f:
        json.dump(d2, f, separators=(",", ":"))
    # --- optimal transport demo: petal length of the three iris species
    pl = {nm: r(iris.data[iris.target == k, 2], 2) for k, nm in enumerate(("setosa", "versicolor", "virginica"))}
    d3 = dict(petal_length=pl, ref={})
    a = np.full(50, 1 / 50)
    for (i, j) in ((1, 2),):
        xs = np.sort(iris.data[iris.target == i, 2])
        ys = np.sort(iris.data[iris.target == j, 2])
        C = (xs[:, None] - ys[None, :]) ** 2
        P0, c0 = ot_lp(a, a, C)
        d3["ref"]["w2sq_versicolor_virginica"] = c0
        for gam in (0.5, 0.1, 0.02):
            P, f_, g_, it, err = sinkhorn(a, a, C, gam, 100000, 1e-10)
            d3["ref"]["sinkhorn_cost_gamma_%g" % gam] = float((P * C).sum())
            d3["ref"]["sinkhorn_iters_gamma_%g" % gam] = int(it)
    with open(os.path.join(DATA_OUT, "ch06-ot.json"), "w") as f:
        json.dump(d3, f, separators=(",", ":"))
    print("wrote ch06-*.json")


FIGURES = {
    "6.2": fig_6_2, "6.3": fig_6_3, "6.5": fig_6_5, "6.6": fig_6_6, "6.7": fig_6_7, "6.8": fig_6_8, "6.9": fig_6_9,
    "6.10": fig_6_10, "6.11": fig_6_11, "6.12": fig_6_12, "6.17": fig_6_17, "6.18": fig_6_18, "6.19": fig_6_19, "6.20": fig_6_20,
    "S7.1": fig_S7_1, "S7.2": fig_S7_2, "S7.3": fig_S7_3, "S7.4": fig_S7_4, "S7.5": fig_S7_5, "S7.6": fig_S7_6,
    "x6.a": fig_x6_a, "x6.b": fig_x6_b, "x6.c": fig_x6_c, "x6.d": fig_x6_d, "x6.e": fig_x6_e,
}


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()
