PaperlayerView exact revision on arXiv

Source-linked AI summary

How Inefficient Is Natural Gradient Descent? From Exact Optimality to \Theta ( \sqrt{ \log d } ) Divergence

Guni Sharon, Alan Kuhnle

arXiv:2610.07228v1stat.MLcs.LG

TL;DR

The paper asks how much longer idealized NGD’s mixture-geodesic path can be than the shortest Fisher–Rao path. It measures that overhead, classifies families using a tensor criterion, and reports exact, bounded, and dimensionally unbounded regimes; under a per-step Fisher-chord budget, the ratio gives a one-sided step-count lower bound.

  • Problem

    The paper asks whether idealized NGD’s mixture-geodesic trajectory is efficient relative to the shortest Fisher–Rao path.

    Source: §1 · p. 1

  • Method

    The paper measures mixture-geodesic length divided by Fisher–Rao distance and uses an Amari–Chentsov tensor criterion to distinguish efficiency regimes.

    Source: §1 · p. 2

  • Results

    The tensor criterion identifies exact efficiency for one-dimensional or quadratic-potential families, while bounded skewness with finite Fisher–Rao diameter yields a dimension-independent bound and scale-product families are dimensionally unbounded.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Under a per-step Fisher-chord budget, idealized NGD requires asymptotically at least R times as many steps as a Fisher–Rao geodesic oracle.

    Source: §1 · p. 2

    The step-count interpretation is one-sided under a formal Fisher-chord budget, and a version under a fixed KL cap remains an open direction.

    Source: §5 · p. 12

Abstract

from arXiv · show

Natural gradient descent (NGD) underlies common methods in ML. For dually flat families, idealized NGD on the forward Kullback--Leibler objective follows the mixture geodesic which is often longer than the shortest Fisher--Rao path. We quantify this overhead by the inefficiency ratio \(R \ge 1\), the Fisher length of the mixture geodesic divided by the Fisher--Rao distance, and bound its supremum over endpoint pairs as a function of the parameter dimension \(d\). A tensor criterion identifies the regime (I) families, with \(R=1\) everywhere: exactly those with quadratic potential or dimension one, such as fixed-covariance Gaussians. For non-quadratic families, we prove two further regimes: (II) bounded third-order skewness plus finite Fisher--Rao diameter yields a dimension-independent bound; and (III) for products of scale families---including Gaussian covariances and Gamma rates---\(R\) grows as \(\Theta(\sqrt{\log d})\), unbounded in \(d\). Under a per-step Fisher-chord budget, \(R\) translates to a practical computational cost: NGD requires asymptotically at least \(R\) times as many steps as an optimizer following the Fisher--Rao geodesic. Experiments confirm all three regimes: \(R=1\) to machine precision for quadratic-potential families (I), the categorical bound \(\pi/(2\sqrt{2})\) is approached but not attained (II), and sampled scale-product \(R\) grows with \(d\), reaching \(R \approx 1.5\) for long, high-dimensional moves (III).

1 Introduction

The introduction asks whether idealized natural gradient descent (NGD) is itself an efficient path through Fisher geometry, not only whether it is a useful optimizer. It measures the path-length overhead and uses a tensor criterion to organize families into distinct efficiency regimes, with a step-count interpretation under a Fisher-chord budget.

1 Introduction

  • Idealized NGD follows the mixture geodesic, which need not be the shortest path in Fisher geometry.The introduction notes that practical NGD has other documented difficulties, but frames trajectory efficiency as a separate question.Source: §1 · p. 1
  • The inefficiency ratio R compares the mixture-geodesic length with the Fisher–Rao distance; R = 1 means length-optimal, while R > 1 means a suboptimal path.The worst-case ratio is taken over endpoint pairs to study how inefficiency behaves with family dimension.Source: §1 · p. 2
  • The Amari–Chentsov tensor gives a pointwise criterion for when an m-geodesic is length-optimal.The criterion requires the tensor contracted twice against the path velocity to be proportional to that velocity along the path.Source: §1 · p. 2
  • Regime I has R* = 1 for one-dimensional or quadratic-potential families, while Regime II has dimension-independent bounded inefficiency under bounded third-order skewness and finite Fisher–Rao diameter.The introduction gives fixed-covariance families as an example of Regime I.Source: §1 · p. 2
  • For products of scale families, including Gaussian covariances and Gamma rates, Regime III has dimensionally unbounded inefficiency.Experiments report increasing sampled R with dimension, reaching about 1.5 for long, high-dimensional covariance and Gamma moves, consistent with a Θ(√log d) rate.Source: §1 · p. 2
  • Under a per-step Fisher-chord budget, idealized NGD requires asymptotically at least R times as many steps as a Fisher–Rao geodesic oracle.The introduction gives R ≈ 1.5 as corresponding to at least 50% more gradient steps.Source: §1 · p. 2

2 Setup and Scope

The paper studies Fisher geometry for dually flat families, where natural-gradient updates follow mixture geodesics that need not be shortest paths. It measures this path overhead with the Fisher inefficiency ratio.

2 Setup and Scope

  • Every family studied is an exponential family, with a strictly convex log-partition potential relating natural and expectation coordinates and defining the Fisher metric.The expectation parameter is the gradient of the potential, and the Fisher information is its Hessian.Source: §2.1 · p. 3

2.1 Exponential families and dually flat geometry

  • In dually flat geometry, mixture and exponential geodesics are affine segments in expectation and natural coordinates, respectively, but neither is generally Fisher-shortest.The Amari–Chentsov tensor measures the gap between the dual connections and is the negative third derivative of the potential.Source: §2.1 · p. 3

2.2 The Fisher inefficiency ratio

  • The Fisher inefficiency ratio is the mixture-geodesic length divided by Fisher–Rao distance, so it is at least 1 and equals 1 exactly for a minimizing mixture geodesic.The framework assumes a connected, globally dually flat manifold with fixed dual connections.Source: §2.2 · pp. 3–4

3 Fisher-Inefficiency Regimes

The paper classifies worst-case Fisher inefficiency into exact efficiency, dimension-free boundedness, and dimensionally unbounded scale-product regimes. A tensor criterion characterizes optimal paths, while a per-step Fisher-chord budget translates path overhead into a step-count lower bound.

3 Fisher-Inefficiency Regimes

  • The tensor criterion identifies three regimes: exact efficiency, uniformly bounded inefficiency, and inefficiency unbounded with dimension.The boundedness condition requires finite normalized skewness and finite Fisher–Rao diameter; scale products show that the diameter condition cannot simply be dropped.Source: §3 · p. 4

3.1 The pointwise optimality criterion

  • An m-geodesic is a Levi–Civita pregeodesic exactly when its Amari–Chentsov tensor contraction is proportional to its velocity; with global length minimality, this implies R = 1.R = 1 also implies the pointwise condition.Source: §3.1 · pp. 4–5

3.2 Regime I: Fisher efficient (R∗= 1)

  • R* = 1 exactly for one-dimensional families or, under a convex expectation-coordinate image, families with quadratic potential.In dimension at least two, a non-quadratic potential yields R > 1 somewhere under that convex-domain hypothesis.Source: §3.2 · p. 5

3.3 Regime II: Uniformly bounded inefficiency (R∗

  • Finite normalized skewness and finite Fisher–Rao diameter yield a dimension-independent bound on R*; for a convex expectation image and non-quadratic potential, R* > 1.This criterion is sufficient, not necessary.Source: §3.3 · p. 6
  • For categorical families with k ≥ 3 outcomes, R* = π/(2√2) ≈ 1.1107, independent of k and approached but not attained; for k = 2, R* = 1.The sharp limiting value comes from moves confined to two coordinates as their conserved mass vanishes and their swept angle approaches π/2.Source: §3.3 · pp. 6–7

3.4 Regime III: Dimensionally unbounded inefficiency (supd R∗

  • Products of n identical scale families have R* = Θ(√log n), so their worst-case inefficiency is unbounded as dimension grows.Coordinates spanning many distinct log-scales drive the growth: their path-length contributions add while their squared distance contributions combine quadratically.Source: §3.4 · p. 7

3.5 Operational meaning of R: a step-count corollary

  • Under a per-step Fisher-chord budget, NGD requires asymptotically at least R(p, q) times as many steps as a Fisher–Rao geodesic oracle.The bound covers exact forward-KL trust-region or proximal steps and specified consistent budgeted schemes; replacing the chord cap with a fixed KL cap remains open, and fixed-rate NGD is outside its scope.Source: §3.5 · p. 8

4 Empirical R Study

The sampled results distinguish an exactly efficient Gaussian-location regime, a dimension-free categorical cap, and scale-product inefficiency that rises with dimension. For scale products, the largest sampled ratios occur on longer moves, while dispersion alone does not determine inefficiency.

4.1 Experimental setup

  • The experiments draw 2,000 endpoint pairs per family at each d ∈ {2, 4, 8, 16}, recording Fisher–Rao length, R, and dispersion entropy.Pairs are sampled to span ranges of both length and spectral shape, so no single regime dominates the batch.Source: §4.1 · p. 9
  • Figure 1 plots R against Fisher–Rao length, facets by family and dimension, and colors points by dispersion entropy H.H uses different underlying vectors for SPD and Gamma, so compare it within each family rather than across those panels.Source: Figure 1 · p. 10, §4.1 · p. 10

4.2 Results

  • Gaussian location returns R = 1 to machine precision, with |R −1| < 10^-12 for every sampled pair and dimension.Source: §4.2 · p. 10
  • Categorical sampled maxima remain below the dimension-independent cap and approach it closely, ranging from 1.110 at d = 2 to 1.086 at d = 16.The cap is rarely approached under random sampling; its extremal configuration changes only two coordinates, becoming less common as outcome count grows.Source: §4.2 · pp. 10–11
  • Scale-product inefficiency rises with dimension: sampled maxima reach R ≈1.51 for SPD and 1.48 for Gamma at d = 16.For very short moves R stays near 1; the upper envelope lifts at larger Fisher–Rao lengths, and the growth is consistent with Θ(√log d).Source: §4.2 · p. 11
  • At d = 2, larger sampled ratios co-occur with longer moves and two comparable-magnitude coordinates, but the samples do not establish high dispersion as necessary.At d ≥4, dispersion entropy alone shows no single-axis relationship with R.Source: §4.2 · p. 11

5 Summary

The paper organizes Fisher inefficiency into three regimes, from exact optimality to dimensionally unbounded growth. The regimes are governed by the Amari–Chentsov tensor, skewness and diameter conditions, and scale-product behavior.

5 Summary

  • The three regimes are exact efficiency, dimension-independent bounded inefficiency, and scale-product inefficiency of Θ(√log d).The bounded regime follows from bounded third-order skewness together with finite Fisher–Rao diameter; scale products are unbounded in dimension.Source: §5 · p. 12
  • A pointwise condition for optimality is proportionality between the Amari–Chentsov tensor contracted twice with the mixture-geodesic velocity and that velocity.Requiring the condition in all directions characterizes Fisher-efficient families as those with quadratic potential, alongside the separate one-dimensional case.Source: §5 · p. 12
  • The paper identifies scale stratification in infinite-diameter scale families as the mechanism associated with unbounded inefficiency, rather than curvature alone.Both the Hadamard covariance manifold and the flat Gamma-rate product diverge.Source: §5 · p. 12
  • Under a per-step Fisher-chord budget, R gives a one-sided lower bound on NGD’s step count relative to a Fisher–Rao geodesic oracle.The comparison is limited to that formal budget and comparator; the paper leaves open a converse about diameter and a version under a fixed KL cap.Source: §5 · p. 12

B.1 Pointwise pregeodesy criterion

The appendix connects optimality of a mixture geodesic to a pointwise tensor condition and then characterizes when all endpoint pairs are Fisher-efficient. The characterization separates the one-dimensional case from higher-dimensional families.

B.1 Pointwise pregeodesy criterion

  • A mixture geodesic is a Levi–Civita pregeodesic exactly when T(˙γ, ˙γ, Z) = µ g(˙γ, Z) for every vector field Z along it.R(p, q) = 1 implies this condition; conversely, it implies R(p, q) = 1 when the geodesic image is globally length-minimizing, such as in a Hadamard manifold or a strongly convex normal neighborhood.Source: §B.1 · pp. 15–16
  • The pointwise condition arises because the mixture geodesic’s Levi–Civita acceleration is proportional to its velocity precisely when the contracted tensor has the stated form.Source: §B.1 · p. 16

B.2 The tensor lemma

  • The appendix’s tensor lemma is used to rule out nonzero fully symmetric tensors under the all-directions proportionality condition in dimensions at least two.Source: §B.2 · p. 16

B.3 Dimension one

  • In dimension one, the mixture geodesic traverses the expectation-coordinate interval monotonically and is length-minimizing, so R ≡1 even when T is nonzero.Source: §B.3 · p. 17

B.4 Fisher-efficient characterization

  • For convex expectation-coordinate images, R∗ = 1 exactly in dimension one or, in dimensions at least two, when the potential is quadratic.In higher dimensions, a non-quadratic potential forces R > 1 somewhere.Source: §B.4 · pp. 17–18

C Class II: the skewness–diameter criterion

  • The Class II proof avoids comparison geometry by tracking distortion of a fixed expectation-coordinate ruler along curves; finite diameter then supplies global control.The appendix notes that bounding the mixture geodesic’s own speed instead yields a self-referential Riccati-type bound that can blow up in finite time.Source: C Class II: the skewness–diameter… · p. 18, §C.2 · p. 19

C.1 Polarization

  • A dimension-independent tensor-norm bound follows by applying Banach’s theorem to the symmetric trilinear form and its diagonal cubic form.The resulting constant is 1 and does not depend on manifold dimension.Source: §C.1 · p. 18

C.3 The bounded-inefficiency theorem

Finite normalized skewness and finite Fisher–Rao diameter give a dimension-free upper bound on inefficiency. The categorical family has a separate sharp, uniform bound that is strictly below its supremum for every distinct pair.

C.3 The bounded-inefficiency theorem

  • If normalized skewness κT and Fisher–Rao diameter D are finite, then R∗ ≤ e^(κT D/2), with no dependence on dimension.For a convex expectation-coordinate image and non-quadratic potential, the same theorem states R∗ > 1.Source: §C.3 · pp. 19–20
  • The skewness–diameter bound does not cover the full simplex because normalized skewness diverges at its boundary, although the categorical inefficiency remains bounded.The categorical constant therefore requires the independent argument in Section D.Source: §C.3 · p. 20, D The categorical constant π/(2 · p. 20

D The categorical constant π/(2

  • The categorical proof establishes the exact constant using an arcsine-weight argument, Cauchy–Schwarz, and sin x ≤ x, rather than the skewness–diameter theorem.Source: D The categorical constant π/(2 · p. 20

D.2 The chord bound and the sharp constant

  • In the categorical chord-bound proof, equality in the coordinate condition occurs only when each coordinate is frozen, a pure entry, or a pure exit.Source: §D.2 · p. 22
  • For every categorical pair of distinct distributions, R(p, q) < π/(2√2), and the supremum is not attained.The exact supremum for k ≥ 3 outcomes is π/(2√2); for k = 2 it is 1.Source: D The categorical constant π/(2 · p. 20, §D.2 · p. 23

D.3 The matching lower bound and the exact value

For categorical families with k ≥ 3, the supremal inefficiency is the same constant, approached but not attained; a two-outcome construction supplies the lower bound. For scale-product factors, a change to log-ratio coordinates reduces the problem to a scalar functional independent of the metric scale κ.

D.3 The matching lower bound and the exact value

  • For k ≥ 3, R* = 1.1107, independent of k and approached but not attained; for k = 2, R* = 1.The lower bound uses a two-outcome family embedded in every simplex with k ≥ 3; the limiting case is approached as m → 0 and ψ → π/2.Source: §D.3 · pp. 23–24
  • The two-outcome construction freezes all other coordinates, and its limiting ratio supplies the categorical lower bound for every k ≥ 3.The two inequality steps are tight in complementary regimes, establishing that the constant is exact.Source: §D.3 · pp. 23–24

E.1 Reduction to a scalar functional

  • For scale-product factors with metric g_ηiηi = κ/η_i², log-ratio coordinates give Fisher–Rao distance √κ||w|| and a reduced functional R(w) independent of κ.The reduction uses y_i = √κ log η_i and w_i = log(ηq_i/ηp_i).Source: §E.1 · p. 24

E.2 Per-channel and elementary bounds

The section bounds the scale-product ratio using per-channel estimates and elementary inequalities. Its upper- and lower-bound arguments together establish the √log n growth rate.

E.2 Per-channel and elementary bounds

  • For every nonzero w, the reduced scale-product ratio satisfies 1 ≤ R(w) ≤ √n.The upper bound follows by bounding the integrated coordinatewise speeds with their ℓ1 norm and then using ||w||₁ ≤ √n||w||₂.Source: §E.2 · p. 25
  • The upper-bound argument gives O(√log n), although its leading constant is not sharp.It splits coordinates into small and large channels; the large-channel estimate uses a weighted Hardy bound.Source: §E.3 · pp. 26–27
  • The padded construction gives a lower bound Ω(√log n), so the upper-bound scaling is matched.It uses m = Θ(log n) blocks at exponentially separated scales; zero coordinates can pad the construction without changing the lower bound.Source: §E.3 · p. 28

E.5 The rate theorem

For products of identical one-dimensional scale families, the supremal ratio grows as Θ(√log n), including on the Gaussian covariance manifold. The operational-cost analysis proves a one-sided step-count result, while the matching upper bound for inexact schemes remains open.

E.5 The rate theorem

  • For products of n identical scale families, R*(M_n) = Θ(√log n), and the same rate holds for Gaussian covariances on SPD(n).The scalar reduction and matching upper and lower bounds also imply that the supremal inefficiency is unbounded as n grows.Source: §E.5 · p. 28
  • Curvature sign does not distinguish the bounded and unbounded examples: negatively curved SPD(n) and flat Gamma products both have infinite diameter and the √log n rate, while the finite-diameter simplex is bounded.The sufficient criterion keys on finite versus infinite Fisher–Rao diameter.Source: §E.5 · p. 28

F Operational cost: a one-sided step-count bound

  • The operational-cost analysis proves only a one-sided step-count bound; a matching upper bound on traversed length for inexact schemes remains open.The proof establishes the direction used by the proposition, not a two-sided result.Source: F Operational cost: a one-sided… · p. 29

F.1 The exact trust-region step stays on the m-geodesic

With the current iterate on the left of the forward-KL trust-region constraint, an exact step stays on the mixture-geodesic segment to the target. For consistent approximate schemes, the analysis bounds deviation from that geodesic and gives a one-sided step-count guarantee.

F.1 The exact trust-region step stays on the m-geodesic

  • An exact forward-KL trust-region step with the current iterate on the left places the next expectation parameter on the segment toward the target.The proximal step has the same segment property, so exact iterates advance monotonically along the mixture geodesic.Source: §F.1 · p. 29
  • The exact scheme’s chord-budgeted steps yield a one-sided lower bound on traversed length relative to the number of steps.The per-edge arc-length bound is summed over the steps.Source: §F.1 · p. 30

F.2 Shadowing for consistent approximate schemes

  • For a β-consistent budgeted scheme, every iterate stays within C1ε of the mixture geodesic and a terminating run satisfies N ≥ (L/ε)(1 − C3ε).The constants depend on the local slab and scheme parameters listed in the result.Source: §F.2 · p. 30
  • The analysis does not prove a matching upper bound on traversed length for inexact schemes, so its result remains one-sided.Such a bound is stated as unproved and is not used in the proposition.Source: §F.2 · p. 31

F.3 The step-count proposition

Under a small per-step Fisher-chord budget, the proposition gives a one-sided lower bound: idealized NGD uses asymptotically at least R times the steps needed to inscribe a minimizing Fisher–Rao geodesic. The comparison is against an oracle path, and the result does not apply to fixed-rate NGD.

F.3 The step-count proposition

  • NNGD/Ngeo(ε) ≥ R(p, q)(1 − O(ε)) as ε shrinks, under the proposition’s stated budgeted-scheme conditions.The comparison uses the minimum number of Fisher-chord-capped steps inscribing a minimizing geodesic.Source: §F.3 · pp. 31–32
  • The lower bound follows because budgeted NGD tracks the mixture geodesic’s Fisher length, while the geodesic comparator’s step count tracks Fisher–Rao distance.The proof controls discretization errors in both path lengths as ε becomes small.Source: §F.3 · pp. 31–32
  • The step-count interpretation requires a Fisher-chord budget; fixed-rate NGD violates it, and the comparison is against an often-intractable geodesic oracle.The paper does not claim a practical competitor is R times faster.Source: §F.3 · p. 32
  • The supplement flags the matching upper bound on traversed length for inexact schemes as open.This is the remaining unproved result noted in the appendix.Source: §F.3 · p. 32

G Related Work

The paper distinguishes its contribution from prior work on dual-geodesic flows and path dilation: it studies the Fisher dilation of the mixture geodesic and derives family-specific constants and rates. The accompanying glossary supplies geometric vocabulary for the proof supplement and identifies manifold points with probability distributions in a statistical model.

G Related Work

  • The contribution is exact constants and dimension-dependent worst-case rates for the Fisher dilation of mixture geodesics, with a restricted natural-gradient interpretation.The paper treats the mixture geodesic as the distinguished curve rather than introducing path dilation or dual-geodesic flow.Source: G Related Work · pp. 32, 34
  • Prior work establishes canonical-divergence flows along dual affine geodesics; the forward-KL natural-gradient mixture-affine trajectory is therefore prior geometry, not this paper’s discovery.The paper instead measures the mixture path’s Fisher length relative to the shortest Fisher path.Source: G Related Work · pp. 32–33

H Geometry Glossary

  • The glossary is a compact reference for differential geometry, aimed at readers familiar with linear algebra and multivariable calculus.It treats points of the manifold as probability distributions in a statistical model.Source: H Geometry Glossary · p. 34, §H.1 · p. 34

H.1 Manifolds and tangent objects.

  • A manifold point is locally represented by coordinates, while tangent spaces encode infinitesimal directions of movement from that point.The glossary describes charts as local coordinate maps and tangent vectors as directions of movement.Source: §H.1 · p. 34

H.2 Metrics and lengths.

This glossary section establishes the geometric vocabulary used to describe Fisher lengths, dual affine paths, and the paper’s inefficiency quantities. It connects local metric and connection definitions to global distances and the paper’s assumptions and bounds.

H.2 Metrics and lengths.

  • The Fisher metric is the Riemannian inner product used throughout the paper and, for an exponential family, is the Hessian of its log-partition function.It assigns a local Fisher norm to tangent vectors, which supplies infinitesimal length.Source: §H.2 · pp. 34–35

H.3 Connections and covariant differentiation.

  • Connections define how vector fields are differentiated across tangent spaces; the Levi-Civita connection is torsion-free and metric-compatible, and its geodesics locally minimize Fisher length.The mixture and exponential connections are flat in their respective expectation and natural coordinates.Source: §H.3 · p. 35

H.4 Dually flat statistical manifolds.

  • Dually flat statistical manifolds have dual flat connections, with natural and expectation coordinates making exponential and mixture geodesics straight affine segments, respectively.For exponential families, the expectation parameter is the expected sufficient statistic and is dual to the natural parameter.Source: §H.4 · pp. 35–36

H.5 Geodesics and pregeodesics.

  • A Fisher–Rao distance is the infimum of Fisher lengths over curves between endpoints, whereas geodesics and pregeodesics distinguish affine speed from path alone.The m-geodesic is straight in expectation coordinates; the Levi-Civita geodesic is locally shortest for the Fisher metric.Source: §H.5 · p. 36

H.6 Tensors.

  • The Amari–Chentsov tensor is a fully symmetric trilinear object that measures the gap between the exponential and mixture connections.The glossary describes a (0, 3)-tensor as taking three tangent vectors and returning a scalar, linearly in each argument.Source: §H.6 · p. 37

H.7 Paper-specific quantities.

  • R(p, q) is mixture-geodesic Fisher length divided by Fisher–Rao distance, while R*(M) is the manifold’s worst-case inefficiency.The paper also uses normalized tensor skewness and Fisher–Rao diameter; a β-consistent budgeted scheme has second-order local error from the ideal mixture-geodesic flow.Source: §H.7 · p. 37

H.8 Global geometry and inequalities.

  • A Hadamard manifold is complete, simply connected, and non-positively curved, with a unique globally minimizing geodesic between any two points.A strongly convex normal neighborhood provides a local region with a unique minimizing geodesic between any pair of points.Source: §H.8 · p. 37

Related papers

Loading 2610.07228v1…