5D Library › Information Geometry, the Fisher Information Metric and Natural-Gradient Optimisation on Statistical Manifolds · 中文

Chapter 4 The Natural Gradient: Invariance, Speed and Approximation

“Steepest” is relative to a metric

Gradient descent, θ←θ−η∇L\theta \leftarrow \theta – \eta\nabla L, is described as “descending along the steepest direction”. But “steepest” first requires a rule for measuring the size of a step: the gradient direction is the one that decreases the loss most among steps of fixed length in the Euclidean metric. Change the parameters and the Euclidean length changes, and so does the steepest direction. Strictly speaking, the gradient ∂iL\partial_i L is a covector, transforming by J⊤J^\top, while a parameter increment is a tangent vector, transforming by J−1J^{-1}; subtracting one from the other gives a result that depends on the coordinates.

If the step length is measured instead by the Fisher metric of the statistical manifold, the problem becomes: decrease L(θ+dθ)L(\theta + d\theta) as much as possible subject to 12dθ⊤Gdθ=ε2\tfrac12 d\theta^\top G\, d\theta = \varepsilon^2 (i.e. a KL change of about ε2\varepsilon^2 in the distribution). A Lagrange multiplier gives

dθ∝−G(θ)−1∇L(θ),d\theta \;\propto\; -\,G(\theta)^{-1}\nabla L(\theta) ,

which Amari called the natural gradient (Amari 1998). G−1G^{-1} “raises” the covector to a tangent vector, so G−1∇LG^{-1}\nabla L is a geometric object that does not depend on coordinates.

Evidence

What Amari’s 1998 paper says. “Natural gradient works efficiently in learning” appeared in Neural Computation, volume 10, issue 2, pages 251–276 (Amari 1998). It defines the steepest-descent direction in a Riemannian parameter space; proves that online (sample-by-sample) natural-gradient learning is asymptotically Fisher-efficient, i.e. its estimation error attains the Cramér–Rao bound of Chapter 2; and argues that the natural gradient may make the “plateau” phenomenon in multilayer-perceptron learning disappear or become less serious. Kakade later applied the idea to policy gradients in reinforcement learning (Kakade 2001), Pascanu and Bengio discussed its relation to other second-order methods for deep networks (Pascanu and Bengio 2014), and Ollivier and co-authors generalised it into a family of optimisation algorithms built on invariance principles (Ollivier et al. 2017).

The author’s framework says Amari 1998 gave “a proof that the natural gradient removes coordinate-dependent oscillation in ill-conditioned valleys”. After checking, this should be restated as a weaker fact that does hold: when the Fisher matrix equals the Hessian of the loss — for instance when the negative log-likelihood is quadratic in the parameters, or for generalised linear models with canonical link (logistic regression, Poisson regression) — a natural-gradient step is a Newton step, and Newton’s method reaches the minimum of a quadratic in one step regardless of the condition number. When the loss is the negative log-likelihood of an exponential family whose natural parameter is the network output (for example squared error or softmax cross-entropy), the Fisher matrix equals the generalised Gauss–Newton matrix (a curvature approximation that is always positive semi-definite) (Martens 2020); this is still not the Hessian. In general the two are not equal, and for general non-convex problems there is no guarantee of “removing oscillation”.

Invariance: exact for the flow, first-order for steps

In what sense is the natural gradient invariant? Consider the continuous-time flow θ̇=−G−1∇L\dot\theta = -G^{-1}\nabla L. In new coordinates ξ\xi, ξ̇=−Gξ−1∇ξL=−(J⊤GJ)−1J⊤∇θL=−J−1G−1∇θL=J−1θ̇\dot\xi = -G_\xi^{-1}\nabla_\xi L = -(J^\top G J)^{-1}J^\top\nabla_\theta L = -J^{-1}G^{-1}\nabla_\theta L = J^{-1}\dot\theta, so the two trajectories describe the same path of distributions. But an actual algorithm takes a discrete step: θk+1=θk−ηG−1∇L\theta_{k+1} = \theta_k – \eta G^{-1}\nabla L is a straight line in parameter space, and a straight line in one coordinate system is generally a curve in another. Discrete steps in two coordinate systems therefore agree only to first order; they differ by O(η2)O(\eta^2) per step, accumulating to O(η)O(\eta) over a fixed time. Martens’s 2020 review calls this “approximate parametrisation invariance” (Martens 2020). The exception is an affine (linear) reparametrisation: straight lines map to straight lines and GG transforms as J⊤GJJ^\top GJ, so discrete natural-gradient steps correspond one to one and invariance is exact; the first-order statement concerns non-linear reparametrisations, which is what charts B, C and D in the program below are relative to A.

Calculation

# Is the natural gradient "parametrisation invariant"? Fit N(mu, sigma^2) to data with
# mean 1 and variance 4 (average negative log-likelihood), starting at (0, 0.5), in four
# coordinate systems: A (mu, sigma), B (mu, log sigma), C (mu, sigma^2) and D the
# expectation parameters (mu, mu^2 + sigma^2). K steps of size eta, eta * K = 2 fixed.
# The natural-gradient FLOW is the same in every chart; discrete steps differ by O(eta).
# Plain gradient descent differs by O(1). At eta = 1 the chart matters a great deal.
import math

M, V = 1.0, 4.0
CHARTS = {   # to (mu, sigma), from (mu, sigma), Jacobian d(mu, sigma)/d(theta)
    "A (mu, sigma)": (lambda t: t, lambda m, s: (m, s),
                      lambda t: ((1, 0), (0, 1))),
    "B (mu, log s)": (lambda t: (t[0], math.exp(t[1])), lambda m, s: (m, math.log(s)),
                      lambda t: ((1, 0), (0, math.exp(t[1])))),
    "C (mu, s^2)": (lambda t: (t[0], math.sqrt(t[1])), lambda m, s: (m, s * s),
                    lambda t: ((1, 0), (0, 0.5 / math.sqrt(t[1])))),
    "D expectation": (lambda t: (t[0], math.sqrt(t[1] - t[0] ** 2)),
                      lambda m, s: (m, m * m + s * s),
                      lambda t: ((1, 0), (-t[0] / math.sqrt(t[1] - t[0] ** 2),
                                          0.5 / math.sqrt(t[1] - t[0] ** 2))))}

def grad_ms(m, s):                       # gradient of log s + ((M-m)^2 + V)/(2 s^2)
    q = (M - m) ** 2 + V
    return (-(M - m) / s ** 2, 1 / s - q / s ** 3)

def run(chart, eta, K, natural=True):
    to, frm, jac = CHARTS[chart]; t = list(frm(0.0, 0.5))
    for _ in range(K):
        m, s = to(t); gm, gs = grad_ms(m, s); J = jac(t)
        g = [J[0][0] * gm + J[1][0] * gs, J[0][1] * gm + J[1][1] * gs]   # J' grad
        if natural:                                       # F = J' diag(1/s^2, 2/s^2) J
            a = (J[0][0] ** 2 + 2 * J[1][0] ** 2) / s ** 2
            b = (J[0][0] * J[0][1] + 2 * J[1][0] * J[1][1]) / s ** 2
            d = (J[0][1] ** 2 + 2 * J[1][1] ** 2) / s ** 2
            det = a * d - b * b; g = [(d * g[0] - b * g[1]) / det,
                                      (a * g[1] - b * g[0]) / det]
        t = [t[0] - eta * g[0], t[1] - eta * g[1]]
        try:
            m, s = to(t)
        except (ValueError, OverflowError):
            return None
        if not (s > 0) or abs(m) > 1e6:
            return None
    return to(t)

def kl(a, b):
    return math.log(b[1] / a[1]) + (a[1] ** 2 + (a[0] - b[0]) ** 2) / (2 * b[1] ** 2) - .5

flow = run("A (mu, sigma)", 1e-4, 20_000)
print(f"reference flow (A, eta 1e-4, 20,000 steps) at time 2: mu {flow[0]:.4f},"
      f" sigma {flow[1]:.4f}")
for natural in (True, False):
    print(("natural gradient" if natural else "plain gradient") +
          ": KL(flow || end point) per chart; spread = largest KL between charts")
    print("     eta     K    " + "  ".join(f"{c:>13s}" for c in CHARTS) + "   spread")
    for eta in (1.0, 0.5, 0.1, 0.02, 0.004):
        K = round(2 / eta); ends = [run(c, eta, K, natural) for c in CHARTS]
        cells = [f"{kl(flow, e):13.2e}" if e else f"{'diverged':>13s}" for e in ends]
        ok = [e for e in ends if e]
        spr = max(kl(a, b) for a in ok for b in ok) if len(ok) > 1 else float("nan")
        print(f"   {eta:5.3f} {K:5d}    " + "  ".join(cells) + f"  {spr:8.1e}")
one = run("D expectation", 1.0, 1)
print(f"one natural step of size 1 in chart D lands on (mu, sigma) = ({one[0]:.4f},"
      f" {one[1]:.4f}), the MLE")
# reference flow (A, eta 1e-4, 20,000 steps) at time 2: mu 0.8647, sigma 1.8999
# natural gradient: KL(flow || end point) per chart; spread = largest KL between charts
#      eta     K    A (mu, sigma)  B (mu, log s)    C (mu, s^2)  D expectation   spread
#    1.000     2         1.60e-01       7.17e+00       4.84e-03       4.84e-03   2.1e+06
#    0.500     4         1.57e-02       2.17e+00       1.98e-03       1.51e-03   9.5e+01
#    0.100    20         2.17e-04       7.23e-04       7.89e-05       5.81e-05   4.5e-04
#    0.020   100         7.49e-06       1.45e-05       3.10e-06       2.27e-06   6.5e-06
#    0.004   500         2.83e-07       5.43e-07       1.16e-07       8.44e-08   2.5e-07
# plain gradient: KL(flow || end point) per chart; spread = largest KL between charts
#      eta     K    A (mu, sigma)  B (mu, log s)    C (mu, s^2)  D expectation   spread
#    1.000     2         2.51e+00       1.62e+01       8.50e-01       7.07e-01   2.4e+13
#    0.500     4         1.83e+00       6.17e+00       4.59e-01       3.80e-01   7.4e+04
#    0.100    20         3.54e-01       1.79e-02       1.03e-02       8.62e-03   9.0e-01
#    0.020   100         1.50e-02       1.88e-02       9.98e-02       1.56e-01   1.8e-01
#    0.004   500         1.32e-02       1.89e-02       1.09e-01       1.67e-01   1.9e-01
# one natural step of size 1 in chart D lands on (mu, sigma) = (1.0000, 2.0000), the MLE

The program fits the same normal distribution in four coordinate systems — (μ,σ)(\mu, \sigma), (μ,log⁡σ)(\mu, \log\sigma), (μ,σ2)(\mu, \sigma^2) and the expectation parameters (μ,μ2+σ2)(\mu, \mu^2 + \sigma^2) — with total “time” ηK=2\eta K = 2 fixed. The reference continuous flow reaches μ=0.8647\mu = 0.8647, σ=1.8999\sigma = 1.8999 at time 2. With the natural gradient, the KL gap between each chart’s end point and the reference flow shrinks quickly with the step size: of order 10−410^{-4} at η=0.1\eta = 0.1 and 10−710^{-7} at η=0.004\eta = 0.004 (KL is a squared distance, so it falls like η2\eta^2); the largest KL gap between charts falls from 4.5×10−44.5\times10^{-4} to 2.5×10−72.5\times10^{-7}. Plain gradient descent is entirely different: even with a step size of 0.004, the end points in the four charts are 0.013 to 0.167 from the reference flow, and the gap between charts, 0.19, does not shrink with the step size — they follow essentially different paths.

With large steps the natural gradient’s invariance also fails visibly: at η=1\eta = 1 the gap between charts reaches 2.1×1062.1\times10^6 (the (μ,log⁡σ)(\mu, \log\sigma) chart overshoots badly in one step). The last line of the program shows the other side: in the expectation-parameter chart, one natural-gradient step of size 1 lands exactly on the maximum-likelihood estimate (1,2)(1, 2). That is no coincidence: for an exponential family, writing mm for the expectation parameters (to avoid a clash with the step size η\eta), the gradient of the negative log-likelihood with respect to them is Gm(m−m̂)G_m(m – \hat m), so the natural gradient Gm−1∇L=m−m̂G_m^{-1}\nabla L = m – \hat m. In other words, “which chart is best at step size 1” is a coordinate-dependent question — this is exactly where invariance does not hold.

A comparison on ill-conditioned logistic regression

The core claim of the author’s framework is that on ill-conditioned problems (large condition number) the natural gradient is faster than the ordinary gradient. The program below tests this on logistic regression and reports honestly where the natural gradient does not come out ahead. The condition number κ\kappa of the feature covariance is 1, 100 or 10,000, with the feature directions either along the axes or randomly rotated; the methods are gradient descent (the best of a few multiples of the step 1/L1/L), Adam (Kingma and Ba 2015) (the best of a few step sizes), the natural gradient (here Newton’s method) and preconditioning by the empirical Fisher. Besides the number of steps to reach the target, cost is counted by a stated rule: one gradient counts as 1 unit, and building and solving the d×dd\times d curvature matrix adds about d+d2/(3n)d + d^2/(3n) units. The accounting is the author’s model, not a measurement on any hardware.

Calculation

# Natural gradient against gradient descent, Adam and the empirical Fisher on logistic
# regression (n = 100, d = 3, then d = 12) whose feature covariance has condition number
# kappa, eigenvectors along the axes or rotated. Steps to reach L* + 1e-4 (cap 2,000) and
# cost in gradient-evaluation units (building and solving the d x d curvature matrix adds
# about d + d^2/(3n) units per step). Every method takes the best step from a small grid
# (GD: multiples of 1/L, L = largest eigenvalue / 4). For logistic regression the Fisher
# equals the Hessian, so "NG" here is Newton's method.
import math, random

N, CAP, TOL = 100, 2000, 1e-4

def solve(A, b):
    n = len(b); M = [row[:] + [b[i]] for i, row in enumerate(A)]
    for c in range(n):
        p = max(range(c, n), key=lambda r: abs(M[r][c])); M[c], M[p] = M[p], M[c]
        for r in range(c + 1, n):
            f = M[r][c] / M[c][c]
            M[r] = [x - f * y for x, y in zip(M[r], M[c])]
    x = [0.0] * n
    for r in range(n - 1, -1, -1):
        x[r] = (M[r][n] - sum(M[r][k] * x[k] for k in range(r + 1, n))) / M[r][r]
    return x

def rotation(rng, D):                               # random orthogonal (Gram-Schmidt)
    Q = []
    while len(Q) < D:
        v = [rng.gauss(0, 1) for _ in range(D)]
        for q in Q:
            c = sum(a * b for a, b in zip(v, q)); v = [a - c * b for a, b in zip(v, q)]
        s = math.sqrt(sum(a * a for a in v)); Q.append([a / s for a in v])
    return Q

def task(kappa, rotate, seed, D):
    rng = random.Random(seed); ev = [kappa ** (-i / (D - 1)) for i in range(D)]
    I = [[float(i == j) for j in range(D)] for i in range(D)]
    R = rotation(rng, D) if rotate else I
    X = []
    for _ in range(N):
        z = [rng.gauss(0, 1) * math.sqrt(e) for e in ev]
        X.append([sum(R[i][j] * z[j] for j in range(D)) for i in range(D)])
    w = [2 * sum(R[i][j] / math.sqrt(ev[j]) * (0.5 if j else 1) for j in range(D))
         / math.sqrt(D) for i in range(D)]
    y = [1 if rng.random() < 1 / (1 + math.exp(-sum(a * b for a, b in zip(w, x))))
         else 0 for x in X]
    return X, y, max(ev)

def stats(X, y, w, curv=None):                    # loss, gradient, Fisher or EF
    D = len(w); L, g = 0.0, [0.0] * D; F = [[0.0] * D for _ in range(D)] if curv else None
    for x, t in zip(X, y):
        z = sum(a * b for a, b in zip(w, x))
        p = 1 / (1 + math.exp(-z)) if z >= 0 else math.exp(z) / (1 + math.exp(z))
        L += math.log1p(math.exp(-abs(z))) + max(z, 0) - t * z
        gi = [(p - t) * a for a in x]; g = [a + b for a, b in zip(g, gi)]
        if curv:
            h, u = ([p * (1 - p) * a for a in x], x) if curv == "F" else (gi, gi)
            for i in range(D):
                Fi, hi = F[i], h[i]
                for j in range(D):
                    Fi[j] += hi * u[j]
    s = 1 / N
    return L * s, [a * s for a in g], [[a * s for a in r] for r in F] if F else None

def optimise(X, y, method, lr, Lstar):
    D = len(X[0]); w = [0.0] * D; m = [0.0] * D; v = [0.0] * D
    for k in range(1, CAP + 1):
        L, g, F = stats(X, y, w, {"NG": "F", "EF": "E"}.get(method))
        if L <= Lstar + TOL:
            return k - 1
        if method in ("NG", "EF"):
            for i in range(D):
                F[i][i] += 1e-8
            step = solve(F, g)
        elif method == "Adam":
            m = [0.9 * a + 0.1 * b for a, b in zip(m, g)]
            v = [0.999 * a + 0.001 * b * b for a, b in zip(v, g)]
            step = [(a / (1 - 0.9 ** k)) / (math.sqrt(b / (1 - 0.999 ** k)) + 1e-8)
                    for a, b in zip(m, v)]
        else:
            step = g
        w = [a - lr * b for a, b in zip(w, step)]
        if any(abs(a) > 1e6 for a in w):
            return None
    return None

def best(X, y, method, grid, Lstar):
    res = [r for r in (optimise(X, y, method, lr, Lstar) for lr in grid) if r is not None]
    return min(res) if res else None

print(f"steps to L* + {TOL:g} (cost units in brackets); '-' = not reached in {CAP:,}")
print(" d   kappa  rotated    GD            Adam          NG (=Newton)   empirical F")
for D, kappa, rot in ((3, 1, 0), (3, 1, 1), (3, 100, 0), (3, 100, 1), (3, 10_000, 0),
                      (3, 10_000, 1), (12, 1, 1), (12, 100, 1)):
        c2 = 1 + D + D * D / (3 * N); COST = {"GD": 1, "Adam": 1, "NG": c2, "EF": c2}
        X, y, lmax = task(kappa, rot, seed=98 + kappa + D, D=D)
        w = [0.0] * D
        for _ in range(40):                                  # Newton to get L*
            L, g, F = stats(X, y, w, "F"); w = [a - b for a, b in zip(w, solve(F, g))]
        Lstar = stats(X, y, w)[0]
        r = {"GD": best(X, y, "GD", (1 / lmax, 4 / lmax, 16 / lmax), Lstar),
             "Adam": best(X, y, "Adam", (0.01, 0.03, 0.1, 0.3, 1.0), Lstar),
             "NG": optimise(X, y, "NG", 1.0, Lstar),
             "EF": best(X, y, "EF", (0.1, 0.3, 1.0), Lstar)}
        cell = lambda k: (f"{r[k]:5d} [{r[k] * COST[k]:6.0f}]" if r[k] is not None
                          else f"{'-':>5s} {'':8s}")
        print(f"{D:2d} {kappa:7,d}   {'yes' if rot else 'no ':3s}   " +
              "  ".join(cell(k) for k in ("GD", "Adam", "NG", "EF")))
# steps to L* + 0.0001 (cost units in brackets); '-' = not reached in 2,000
#  d   kappa  rotated    GD            Adam          NG (=Newton)   empirical F
#  3       1   no        7 [     7]     45 [    45]      3 [    12]      3 [    12]
#  3       1   yes       6 [     6]     37 [    37]      3 [    12]      4 [    16]
#  3     100   no      603 [   603]     58 [    58]      3 [    12]      4 [    16]
#  3     100   yes     574 [   574]     83 [    83]      3 [    12]      3 [    12]
#  3  10,000   no        -             109 [   109]      3 [    12]      3 [    12]
#  3  10,000   yes       -             404 [   404]      3 [    12]      3 [    12]
# 12       1   yes       9 [     9]     42 [    42]      3 [    40]     13 [   175]
# 12     100   yes     156 [   156]     54 [    54]      2 [    27]      4 [    54]

In steps, the natural gradient is smallest in every row (2–3 steps), regardless of conditioning and rotation; this is Newton’s quadratic convergence. Gradient descent’s step count grows sharply with the condition number: about 600 steps at κ=100\kappa = 100, and the target is not reached within 2,000 at κ=10,000\kappa = 10{,}000 — consistent with the classical dependence of gradient descent’s convergence rate on the condition number (Nocedal and Wright 2006). Adam lies in between; its diagonal preconditioning works better when the features lie along the axes (109 steps at κ=10,000\kappa = 10{,}000) and worse after rotation (404 steps), because a diagonal matrix cannot represent rotated curvature.

In cost, the conclusion differs. With good conditioning (κ=1\kappa = 1), gradient descent needs only 6–9 units, fewer than the natural gradient’s 12 (d=3d = 3) and 40 (d=12d = 12); at d=12d = 12, κ=1\kappa = 1, Adam (42) and the natural gradient (40) are about equal. Only on ill-conditioned problems does the natural gradient clearly win on cost (27 units at d=12d = 12, κ=100\kappa = 100, against 54 for Adam and 156 for gradient descent). The cost per step grows with d2d^2 (building) and d3d^3 (solving); for networks with millions of parameters the exact natural gradient cannot be computed at all, which is why the two approximations below are needed. At d=3d = 3 the empirical Fisher performs much like the Fisher (3–4 steps); but at d=12d = 12, κ=1\kappa = 1 it needs 13 steps (175 units) against the Fisher’s 3 (40 units). The next section explains why.

Left: paths of four methods from the origin on a two-dimensional logistic regression with condition number 100 and rotated features (grey lines are loss contours, the star is the optimum); gradient descent and Adam creep along the narrow valley, the natural gradient arrives in a few steps; the empirical Fisher’s first step is the same as the natural gradient’s (at the origin every example has p = 0.5, so the empirical Fisher equals the Fisher), and its second step overshoots the optimum and comes back. Right: loss minus its optimum against iteration (the horizontal axis is linear for the first 10 steps and logarithmic thereafter).

The empirical Fisher is not the Fisher

The “empirical Fisher” widely used in practice replaces the expectation over the model’s predictive distribution in the Fisher matrix Ey∼pθ[∇ℓ∇ℓ⊤]E_{y\sim p_\theta}[\nabla\ell\nabla\ell^\top] by an average over the observed labels: 1n∑i∇ℓi∇ℓi⊤\tfrac1n\sum_i \nabla\ell_i\nabla\ell_i^\top. It needs only the per-example gradients already computed, so it is cheap.

Evidence

The conclusions of Kunstner, Hennig and Balles (2019). They point out that the empirical Fisher does not in general carry second-order (curvature) information, that the conditions under which it agrees with the Fisher or the Hessian (a correctly specified model, a large sample, proximity to the optimum) are unlikely to hold in practice, and that preconditioning with it causes serious problems even in simple linear regression; they also criticise arguments linking the empirical Fisher to heuristics such as Adam (Kunstner et al. 2019).

Calculation

# The empirical Fisher (EF, the mean of per-example g g') is not the Fisher. Linear
# regression y = x'theta + e, n = 200, d = 2, feature variances 1 and 0.01, fitted by the
# Gaussian likelihood with sigma = 1. Then the Fisher F = X'X/n is also the Hessian,
# while EF = sum r_i^2 x_i x_i'/n depends on the residuals r_i. (1) Near the optimum
# EF ~ s^2 F, where s is the TRUE noise sd: right only if the model's sigma is right.
# (2) Far from it EF is dominated by the gradient direction and the step stalls.
# (3) Steps to converge: Fisher (one Newton step), EF with the best fixed step, GD.
import math, random

def data(noise, seed, n=200):
    rng = random.Random(seed); X, y = [], []
    for _ in range(n):
        x = (rng.gauss(0, 1), rng.gauss(0, 0.1)); X.append(x)
        y.append(2 * x[0] - 3 * x[1] + noise * rng.gauss(0, 1))
    return X, y

def mats(X, y, t):
    n = len(X); g = [0.0, 0.0]; F = [[0.0] * 2 for _ in range(2)]
    E = [[0.0] * 2 for _ in range(2)]; L = 0.0
    for x, v in zip(X, y):
        r = x[0] * t[0] + x[1] * t[1] - v; L += r * r / 2
        for i in range(2):
            g[i] += r * x[i] / n
            for j in range(2):
                F[i][j] += x[i] * x[j] / n; E[i][j] += r * r * x[i] * x[j] / n
    return L / n, g, F, E

def solve2(A, b, damp=1e-10):
    a, c, d = A[0][0] + damp, A[0][1], A[1][1] + damp; det = a * d - c * c
    return [(d * b[0] - c * b[1]) / det, (a * b[1] - c * b[0]) / det]

def opt(t):                                    # exact least squares
    _, g, F, _ = mats(X, y, [0.0, 0.0]); s = solve2(F, g); return [-s[0], -s[1]]

def angle(u, v):
    c = (u[0] * v[0] + u[1] * v[1]) / math.hypot(*u) / math.hypot(*v)
    return math.degrees(math.acos(max(-1.0, min(1.0, c))))

print("(1) at the optimum: EF / F along each eigen-direction (model assumes sigma = 1)")
for noise in (1.0, 0.1, 3.0):
    X, y = data(noise, seed=2019); ts = opt(None)
    _, g, F, E = mats(X, y, ts)
    print(f"   true noise sd {noise:3.1f}: EF11/F11 = {E[0][0] / F[0][0]:7.4f},"
          f" EF22/F22 = {E[1][1] / F[1][1]:7.4f}  (s^2 = {noise ** 2:.2f})")
X, y = data(1.0, seed=2019); ts = opt(None)
print("(2) away from the optimum (true noise sd 1): direction and length of steps")
print("   distance   angle(EF step, Newton step)   |EF step| / |Newton step|")
for dist in (0.1, 1.0, 10.0, 100.0):
    worst, ratio = 0.0, []
    for k in range(12):
        a = 2 * math.pi * k / 12
        t = [ts[0] + dist * math.cos(a), ts[1] + dist * math.sin(a) / 10]
        _, g, F, E = mats(X, y, t)
        ne, ef = solve2(F, g), solve2(E, g)
        worst = max(worst, angle(ne, ef)); ratio.append(math.hypot(*ef) / math.hypot(*ne))
    print(f"   {dist:8.1f}   {worst:10.1f} deg (worst of 12)      "
          f"{min(ratio):.3g} to {max(ratio):.3g}")
print("(3) iterations to L* + 1e-6 from theta = (20, -30), cap 5,000; Fisher = Newton,")
print("    empirical = EF-preconditioned, GD = gradient descent (best step in brackets)")
for noise in (1.0, 0.1):
    X, y = data(noise, seed=2019); ts = opt(None); Ls = mats(X, y, ts)[0]
    res = {}
    for meth, grid in (("Fisher", (1.0,)), ("empirical", (0.03, 0.1, 0.3, 1.0)),
                       ("GD", (0.5, 1.0, 1.9))):
        best = None
        for lr in grid:
            t = [20.0, -30.0]
            for k in range(5001):
                L, g, F, E = mats(X, y, t)
                if L <= Ls + 1e-6 or not math.isfinite(L) or L > 1e12:
                    break
                s = {"Fisher": lambda: solve2(F, g), "empirical": lambda: solve2(E, g),
                     "GD": lambda: g}[meth]()
                t = [t[0] - lr * s[0], t[1] - lr * s[1]]
            if L <= Ls + 1e-6 and (best is None or k < best[0]):
                best = (k, lr)
        res[meth] = best
    print(f"   true noise sd {noise:3.1f}: " + "; ".join(
        f"{m} {b[0]} (step {b[1]:g})" if b else f"{m} -" for m, b in res.items()))
# (1) at the optimum: EF / F along each eigen-direction (model assumes sigma = 1)
#    true noise sd 1.0: EF11/F11 =  0.9798, EF22/F22 =  1.0849  (s^2 = 1.00)
#    true noise sd 0.1: EF11/F11 =  0.0098, EF22/F22 =  0.0108  (s^2 = 0.01)
#    true noise sd 3.0: EF11/F11 =  8.8186, EF22/F22 =  9.7643  (s^2 = 9.00)
# (2) away from the optimum (true noise sd 1): direction and length of steps
#    distance   angle(EF step, Newton step)   |EF step| / |Newton step|
#         0.1         32.3 deg (worst of 12)      0.922 to 1.23
#         1.0         35.9 deg (worst of 12)      0.248 to 0.923
#        10.0         22.5 deg (worst of 12)      0.00314 to 0.912
#       100.0         17.7 deg (worst of 12)      3.16e-05 to 0.281
# (3) iterations to L* + 1e-6 from theta = (20, -30), cap 5,000; Fisher = Newton,
#     empirical = EF-preconditioned, GD = gradient descent (best step in brackets)
#    true noise sd 1.0: Fisher 1 (step 1); empirical 544 (step 1); GD 417 (step 1.9)
#    true noise sd 0.1: Fisher 1 (step 1); empirical 2500 (step 0.3); GD 418 (step 1.9)

The program makes three points on linear regression. First, at the optimum the empirical Fisher is approximately the true noise variance times the Fisher: with the model assuming σ=1\sigma = 1 and a true noise standard deviation of 1, the ratios of the diagonal elements are 0.98 and 1.08; with true noise 0.1 the ratio is about 0.01, and with 3 about 9. If the model’s noise scale is wrong, the empirical Fisher scales the step up by a factor of about a hundred (true noise 0.1) or down by a factor of about nine (true noise 3). Second, away from the optimum the residuals come mostly from parameter error rather than noise, and the empirical Fisher is dominated by the gradient direction: at distance 100 its step is only 3×10−53\times10^{-5} to 0.28 times as long as the Newton step, with a direction error of up to 18 degrees, so far from the optimum it nearly stalls. Third, from (20,−30)(20, -30) the Fisher (Newton’s method) arrives in one step; the empirical Fisher needs 544 steps with the noise level right and 2,500 with noise 0.1 — both slower than plain gradient descent (417 and 418 steps).

K-FAC: a computable approximation

In 2015 Martens and Grosse proposed K-FAC: approximate the Fisher matrix of a neural network as block-diagonal by layer (they also give a block-tridiagonal version that keeps the blocks between adjacent layers), and each block as the Kronecker product of two small matrices — the second moment E[aa⊤]E[aa^\top] of the layer’s input activations and the second moment E[gg⊤]E[gg^\top] of the back-propagated quantities at the layer’s output (Martens and Grosse 2015). The inverse of a Kronecker product is the Kronecker product of the inverses, so each layer needs only the inverses of two small matrices. The approximation has two sources: ignoring the blocks between layers, and assuming that aa and gg are independent enough for the expectation to factorise.

Calculation

# K-FAC in miniature. A 3-4-1 tanh network with biases (21 parameters) for binary labels
# from a teacher network; n = 100 inputs, one input feature scaled by 0.1. (1) How well
# do the block-diagonal Fisher and the Kronecker-factored blocks E[aa'] (x) E[w dd']
# approximate the exact Fisher? (2) Steps to a target training loss fixed in advance
# (0.20; the loss at the start is 0.83) for GD, Adam, exact natural gradient and K-FAC
# (both damped by 1e-3), best step from a small grid, cap 600 steps.
import math, random

H, I, N, CAP, TARGET = 4, 3, 100, 600, 0.20
rng = random.Random(2015)
X = [[rng.gauss(0, 1), rng.gauss(0, 1), 0.1 * rng.gauss(0, 1)] for _ in range(N)]
T = [rng.gauss(0, 1.5) for _ in range(H * (I + 1) + H + 1)]

def forward(th, x):
    a1 = x + [1.0]; h = []
    for j in range(H):
        h.append(math.tanh(math.fsum(th[j * (I + 1) + k] * a1[k] for k in range(I + 1))))
    a2 = h + [1.0]; o = H * (I + 1)
    z = math.fsum(th[o + j] * a2[j] for j in range(H + 1))
    p = 1 / (1 + math.exp(-z)) if z >= 0 else math.exp(z) / (1 + math.exp(z))
    return a1, h, a2, z, p

Y = [1 if rng.random() < forward(T, x)[4] else 0 for x in X]
P = len(T)

def pieces(th):                                  # loss, gradient, per-example Jacobians
    L, g, J = 0.0, [0.0] * P, []
    for x, y in zip(X, Y):
        a1, h, a2, z, p = forward(th, x); o = H * (I + 1)
        d1 = [th[o + j] * (1 - h[j] ** 2) for j in range(H)]
        jz = [d1[j] * a1[k] for j in range(H) for k in range(I + 1)] + a2
        L += math.log1p(math.exp(-abs(z))) + max(z, 0) - y * z
        g = [gi + (p - y) * v / N for gi, v in zip(g, jz)]
        J.append((jz, p * (1 - p), a1, d1, a2))
    return L / N, g, J

def exact_fisher(J):
    F = [[0.0] * P for _ in range(P)]
    for jz, w, *_ in J:
        for i in range(P):
            wi = w * jz[i] / N; Fi = F[i]
            for k in range(i, P):
                Fi[k] += wi * jz[k]
    for i in range(P):
        for k in range(i):
            F[i][k] = F[k][i]
    return F

def kfac(J):                                     # block diagonal, each block A (x) G
    F = [[0.0] * P for _ in range(P)]; o = H * (I + 1)
    A1 = [[math.fsum(a1[k] * a1[m] for _, _, a1, _, _ in J) / N for m in range(I + 1)]
          for k in range(I + 1)]
    G1 = [[math.fsum(w * d1[j] * d1[l] for _, w, _, d1, _ in J) / N for l in range(H)]
          for j in range(H)]
    A2 = [[math.fsum(a2[k] * a2[m] for *_, a2 in J) / N for m in range(H + 1)]
          for k in range(H + 1)]
    G2 = math.fsum(w for _, w, *_ in J) / N
    for j in range(H):
        for k in range(I + 1):
            for l in range(H):
                for m in range(I + 1):
                    F[j * (I + 1) + k][l * (I + 1) + m] = G1[j][l] * A1[k][m]
    for k in range(H + 1):
        for m in range(H + 1):
            F[o + k][o + m] = G2 * A2[k][m]
    return F

def solve(A, b, damp):
    n = len(b); M = [A[i][:] + [b[i]] for i in range(n)]
    for i in range(n):
        M[i][i] += damp
    for c in range(n):
        p = max(range(c, n), key=lambda r: abs(M[r][c])); M[c], M[p] = M[p], M[c]
        for r in range(c + 1, n):
            f = M[r][c] / M[c][c]
            if f:
                M[r] = [x - f * y for x, y in zip(M[r], M[c])]
    x = [0.0] * n
    for r in range(n - 1, -1, -1):
        x[r] = (M[r][n] - math.fsum(M[r][k] * x[k] for k in range(r + 1, n))) / M[r][r]
    return x

def frob(A, B=None):
    return math.sqrt(math.fsum((a - (B[i][j] if B else 0)) ** 2 for i, r in enumerate(A)
                         for j, a in enumerate(r)))

th0 = [0.5 * rng.gauss(0, 1) for _ in range(P)]
_, _, J = pieces(th0); F = exact_fisher(J); K = kfac(J); o = H * (I + 1)
BD = [[F[i][j] if (i < o) == (j < o) else 0.0 for j in range(P)] for i in range(P)]
print(f"{P} parameters; relative Frobenius error at the initial point:")
print(f"   block-diagonal exact Fisher vs full Fisher: {frob(BD, F) / frob(F):.3f}")
print(f"   K-FAC (Kronecker blocks) vs full Fisher:    {frob(K, F) / frob(F):.3f}")
blk = [[F[i][j] for j in range(o)] for i in range(o)]
kb = [[K[i][j] for j in range(o)] for i in range(o)]
print(f"   layer-1 block: Kronecker vs exact block:    {frob(kb, blk) / frob(blk):.3f}")

def train(method, lr):
    th = th0[:]; m = [0.0] * P; v = [0.0] * P; hist = []
    for k in range(1, CAP + 1):
        L, g, J = pieces(th); hist.append(L)
        if L <= TARGET:
            break
        if method == "GD":
            s = g
        elif method == "Adam":
            m = [0.9 * a + 0.1 * b for a, b in zip(m, g)]
            v = [0.999 * a + 0.001 * b * b for a, b in zip(v, g)]
            s = [(a / (1 - 0.9 ** k)) / (math.sqrt(b / (1 - 0.999 ** k)) + 1e-8)
                 for a, b in zip(m, v)]
        else:
            s = solve(exact_fisher(J) if method == "NG" else kfac(J), g, 1e-3)
        th = [a - lr * b for a, b in zip(th, s)]
        if not all(math.isfinite(a) and abs(a) < 1e4 for a in th):
            break
    return hist

GRID = (("GD", (1.0, 3.0, 10.0)), ("Adam", (0.03, 0.1, 0.3)), ("NG", (0.1, 0.3, 1.0)),
        ("K-FAC", (0.1, 0.3, 1.0)))
runs = {(m, lr): train(m, lr) for m, grid in GRID for lr in grid}
target = TARGET
print(f"(2) steps to training loss {target:.2f}; cost per step in gradient units:"
      " GD and Adam 1,\n   NG 1 + P + P^2/(3n), K-FAC 1 + (factor sizes)/P")
cost = {"GD": 1, "Adam": 1, "NG": 1 + P + P * P / (3 * N),
        "K-FAC": 1 + ((I + 1) ** 2 + H * H + (H + 1) ** 2) / P}
for meth in ("GD", "Adam", "NG", "K-FAC"):
    best = None
    for (m, lr), h in runs.items():
        if m == meth:
            k = next((i for i, L in enumerate(h) if L <= target), None)
            if k is not None and (best is None or k < best[0]):
                best = (k, lr)
    if best:
        print(f"   {meth:6s} {best[0]:4d} steps (step {best[1]:g}); about"
              f" {best[0] * cost[meth]:.0f} gradient-evaluation units")
    else:
        print(f"   {meth:6s} not reached in {CAP} steps (lowest loss"
              f" {min(min(h) for (m, _), h in runs.items() if m == meth):.3f})")
# 21 parameters; relative Frobenius error at the initial point:
#    block-diagonal exact Fisher vs full Fisher: 0.654
#    K-FAC (Kronecker blocks) vs full Fisher:    0.670
#    layer-1 block: Kronecker vs exact block:    0.285
# (2) steps to training loss 0.20; cost per step in gradient units: GD and Adam 1,
#    NG 1 + P + P^2/(3n), K-FAC 1 + (factor sizes)/P
#    GD      532 steps (step 3); about 532 gradient-evaluation units
#    Adam    124 steps (step 0.3); about 124 gradient-evaluation units
#    NG       32 steps (step 0.3); about 751 gradient-evaluation units
#    K-FAC  not reached in 600 steps (lowest loss 0.205)

On a 3-4-1 network with only 21 parameters, the program first measures the quality of the approximation: keeping only the within-layer blocks (block-diagonalisation) already gives a relative Frobenius error of 0.654; replacing the blocks by Kronecker products gives a total error of 0.670; for the first layer alone, the Kronecker product differs from the exact block by 0.285. In this network the between-layer blocks are not small.

The training comparison is also reported as it came out. In steps to a training loss of 0.20 (from 0.83 at the start), the exact natural gradient (damping 10−310^{-3}) is fastest with 32 steps; Adam takes 124, gradient descent 532, and K-FAC does not reach the target within 600 steps (lowest 0.205). In cost, the exact natural gradient comes to about 751 units, more than Adam’s 124. With step size 1 the exact natural gradient diverges, showing that it needs damping or a trust region. This is a very small example and says nothing about K-FAC on large networks — where its design aim is precisely to obtain useful curvature information at a cost far below that of the exact Fisher — but it shows that neither “the natural gradient is faster” nor “K-FAC equals the natural gradient” holds without conditions.

Published benchmark comparisons

Evidence

No optimiser dominates on every task. Schmidt, Schneider and Hennig in 2021 compared more than a dozen optimisers on a range of deep-learning tasks and concluded that no method clearly dominates across all tasks, with the tuning budget and the task strongly affecting the ranking (Schmidt et al. 2021). Zhang and co-authors in 2019 used a noisy quadratic model and experiments to show that preconditioned methods such as Adam and K-FAC bring their benefits mainly in large-batch training, with limited advantage at small batch sizes (Zhang et al. 2019). Wilson and co-authors in 2017 reported that adaptive methods find solutions that generalise worse on some tasks (Wilson et al. 2017). The AlgoPerf benchmark of Dahl and co-authors (2023) uses “time to reach a target on fixed hardware” as its main measure and prescribes tuning protocols (Dahl et al. 2023); the protocol of Chapter 8 follows this approach.

Hypothesis · not established · The return on curvature grows with conditioning

The author’s hypothesis (not established): at a fixed computational budget, K-FAC’s wall-clock advantage over Adam increases monotonically with a task’s effective condition number (estimated from the spectrum of the Fisher matrix early in training), and on tasks with condition number below some threshold K-FAC is no faster than Adam. What would show it wrong: in a secondary analysis of the pre-registered benchmark of Chapter 8, after stratifying by a pre-defined condition number, the rank correlation between the log time ratio and the condition number has a confidence interval that includes zero or is positive (i.e. K-FAC’s relative advantage does not grow with conditioning).

Summary

The natural gradient G−1∇LG^{-1}\nabla L is the steepest-descent direction under the Fisher metric. Its invariance holds exactly for the continuous-time flow and only to first order for discrete steps: in the program the gap between charts is 2.5×10−72.5\times10^{-7} at step size 0.004 and 2.1×1062.1\times10^6 at step size 1. The framework’s “proof” should read: when the Fisher equals the Hessian, the natural gradient is Newton’s method. On ill-conditioned logistic regression it takes the fewest steps but costs more than gradient descent when conditioning is good; on a small network the exact natural gradient takes the fewest steps at about six times Adam’s cost, and K-FAC misses the target. The empirical Fisher is not the Fisher: its scale changes a hundredfold with the true noise, and it stalls far from the optimum. Published benchmarks show no optimiser dominating on every task.

References

Amari, Shun-ichi. 1998. “Natural Gradient Works Efficiently in Learning.” Neural Computation 10 (2): 251–76. https://doi.org/10.1162/089976698300017746.
Dahl, George E., Frank Schneider, Zachary Nado, Naman Agarwal, et al. 2023. Benchmarking Neural Network Training Algorithms. arXiv:2306.07179.
Kakade, Sham M. 2001. “A Natural Policy Gradient.” Advances in Neural Information Processing Systems 14.
Kingma, Diederik P., and Jimmy Ba. 2015. “Adam: A Method for Stochastic Optimization.” 3rd International Conference on Learning Representations (ICLR).
Kunstner, Frederik, Philipp Hennig, and Lukas Balles. 2019. “Limitations of the Empirical Fisher Approximation for Natural Gradient Descent.” Advances in Neural Information Processing Systems 32: 4156–67.
Martens, James. 2020. “New Insights and Perspectives on the Natural Gradient Method.” Journal of Machine Learning Research 21 (146): 1–76.
Martens, James, and Roger Grosse. 2015. “Optimizing Neural Networks with Kronecker-Factored Approximate Curvature.” Proceedings of the 32nd International Conference on Machine Learning, Proceedings of machine learning research, vol. 37: 2408–17.
Nocedal, Jorge, and Stephen J. Wright. 2006. Numerical Optimization. 2nd ed. Springer.
Ollivier, Yann, Ludovic Arnold, Anne Auger, and Nikolaus Hansen. 2017. “Information-Geometric Optimization Algorithms: A Unifying Picture via Invariance Principles.” Journal of Machine Learning Research 18 (18): 1–65.
Pascanu, Razvan, and Yoshua Bengio. 2014. “Revisiting Natural Gradient for Deep Networks.” 2nd International Conference on Learning Representations (ICLR).
Schmidt, Robin M., Frank Schneider, and Philipp Hennig. 2021. “Descending through a Crowded Valley – Benchmarking Deep Learning Optimizers.” Proceedings of the 38th International Conference on Machine Learning, Proceedings of machine learning research, vol. 139: 9367–76.
Wilson, Ashia C., Rebecca Roelofs, Mitchell Stern, Nathan Srebro, and Benjamin Recht. 2017. “The Marginal Value of Adaptive Gradient Methods in Machine Learning.” Advances in Neural Information Processing Systems 30.
Zhang, Guodong, Lala Li, Zachary Nado, et al. 2019. “Which Algorithmic Choices Matter at Which Batch Sizes? Insights from a Noisy Quadratic Model.” Advances in Neural Information Processing Systems 32.

Fan, Y. (2026). Information Geometry, the Fisher Information Metric and Natural-Gradient Optimisation on Statistical Manifolds: From the Cramér–Rao Bound and Jeffreys's Prior to Singular Learning Theory, Read Beside Classical Chinese Thought on Change and Coordinates [信息几何、费希尔信息度量与自然梯度优化的统计流形] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23836268 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).