How Inefficient Is Natural Gradient Descent? From Exact Optimality to Θ(√log d) Deviation Analysis

Natural Gradient Descent (NGD) is the theoretical backbone of many optimization methods in machine learning, appearing everywhere from variational inference to policy optimization in reinforcement learning. By using the Fisher Information Matrix (FIM) to apply a metric correction to the parameter space, it is considered a more "geometrically aware" approach than ordinary gradient descent. But a new arXiv paper (arXiv:2610.07228v1) poses a sharp question: just how inefficient is NGD?

The answer is not a simple "fast" or "slow" — it depends on the geometric structure of the probability distribution family. The research presents a complete picture ranging from exact optimality to unbounded growth with dimension.

The Core Problem: Mixture Geodesics vs. Shortest Paths

In information geometry, a "dually flat" distribution family has two natural geometric structures. When we perform idealized NGD using forward Kullback–Leibler divergence as the optimization objective, the optimization trajectory actually travels along mixture geodesics.

The problem is that mixture geodesics are often not the shortest paths in parameter space. The truly "shortest" path is the geodesic distance defined by the Fisher–Rao metric. The gap between the two is the source of NGD's efficiency loss.

The paper quantifies this overhead with a key metric — the inefficiency ratio R — defined as the Fisher length of the mixture geodesic divided by the Fisher–Rao distance. By definition, R is always greater than or equal to 1. The closer R is to 1, the closer NGD's path is to the theoretical optimum; a larger R means NGD is taking more unnecessary detours. The central task of the research is to analyze the supremum behavior of R as the parameter dimension d varies.

A Quick Overview of Information Geometry Fundamentals

Information geometry treats a family of probability distributions as a Riemannian manifold, where the Fisher Information Matrix (FIM) acts as the metric tensor, defining "how far apart two distributions are." Within this framework, a "dually flat" space has two complementary coordinate systems and geodesics: e-geodesics (exponential geodesics) and m-geodesics (mixture geodesics). Exponential geodesics correspond to linear interpolation of natural parameters (e.g., the natural parameter space of exponential families), while mixture geodesics correspond to linear interpolation of expectation parameters (e.g., the mean parameter space). When KL divergence is used as the objective, the iterative trajectory of natural gradient descent naturally travels along mixture geodesics. The Fisher–Rao metric defines the true Riemannian distance on the manifold; its corresponding geodesics are generally neither e-geodesics nor m-geodesics, but rather the shortest paths accounting for overall curvature. The key to understanding NGD's inefficiency lies precisely in the geometric deviation between mixture geodesics and the Fisher–Rao shortest paths.

Three Geometric Regimes: From Perfect to Divergent

The paper's most valuable contribution is classifying distribution families into three distinct regimes through a tensor criterion.

Regime I: Everywhere Optimal (R = 1)

The first class consists of distribution families with a quadratic potential or with dimension one. For these families, R equals exactly 1 for any pair of endpoints — meaning NGD's path is precisely the shortest path, with no additional overhead.

The most typical example is a Gaussian with fixed covariance. In this case, mixture geodesics and Fisher–Rao geodesics coincide completely, making NGD exactly optimal. Experimentally, R for this class of families reaches machine-precision 1, confirming the theoretical conclusion.

The Geometric Meaning of Quadratic Potentials

The potential function is a central object in dually flat information geometry, linking two dual coordinate systems through the Legendre transform. When the potential function is a quadratic form of the parameters, the relationship between dual coordinates is linear, meaning the mixture geodesic (a linear path in expectation parameters) completely coincides with the exponential geodesic under the Fisher metric. A Gaussian with fixed covariance is the canonical example: the mapping between mean parameters and natural parameters is linear, so the two types of geodesics coincide entirely. This property is practically important — many variational inference algorithms use NGD on Gaussian approximation families and can safely assume there is no geometric waste in path selection. In contrast, when the potential function contains higher-order nonlinear terms, the mapping between coordinate systems becomes curved, and mixture geodesics begin to deviate from the shortest path. This is the root cause of inefficiency in Regimes II and III.

Regime II: Dimension-Independent Bounded Overhead

For non-quadratic distribution families that satisfy two conditions — bounded third-order skewness and finite Fisher–Rao diameter — R is bounded by a constant independent of dimension d.

This means that no matter how high-dimensional the parameter space grows, the degree of NGD's inefficiency does not worsen with it. The paper gives a bound of π/(2√2) ≈ 1.11 for the categorical distribution. Experiments show that R approaches but never reaches this bound, indicating it is a fairly tight theoretical upper bound.

Regime III: Divergence at Θ(√log d) with Dimension

The most striking finding is the third regime. For products of scale families — including the covariance parameters of Gaussian distributions, the rate parameters of Gamma distributions, and other common cases — R grows as Θ(√log d), unboundedly with dimension d.

Although the growth rate of √log d is relatively mild (the square root of a logarithm), it fundamentally refutes the intuition that "NGD remains efficient in high dimensions." In experiments, sampled scale-product families undergoing long-distance, high-dimensional moves yielded R values of approximately 1.5 — meaning NGD requires about 50% more steps than an optimizer traveling along Fisher–Rao geodesics.

High-Dimensional Behavior of Products of Scale Families

A scale family is one whose parameter controls only the "spread" of the distribution — typical examples include the variance parameter σ² (Gaussian) and the rate parameter β (Gamma). When a model has d independent scale parameters, the overall distribution family forms a product manifold of d univariate scale families. This structure is extremely common in practice: diagonal covariance matrices in multivariate Gaussians, layer normalization parameters in deep learning, and hyperparameters in Bayesian neural networks all fall into this category.

The key geometric feature of scale families is the asymmetry of their curvature: the Fisher distance in the "scaling up" direction is not symmetric with the "scaling down" direction (because scale parameters are defined on the positive real line), causing mixture geodesics to accumulate systematic deviations in high-dimensional product spaces. The growth of Θ(√log d) is slower than linear, but for modern deep models with d = 10000, √log(10000) ≈ 3, meaning the path overhead of NGD can be on the order of 3× the optimum — a non-negligible cost at scale.

From Geometry to Computational Cost

The paper doesn't stop at pure geometric analysis — it translates R into concrete, measurable computational cost.

Under a "per-step Fisher-chord budget" constraint, R directly corresponds to the ratio of optimization steps required. The conclusion is straightforward: NGD asymptotically requires at least R times as many iterations as an optimizer traveling along Fisher–Rao geodesics.

In other words, the inefficiency ratio is not merely an abstract geometric quantity — it determines how much extra computation NGD must expend to achieve the same accuracy. For distribution families in Regime III, this overhead accumulates slowly but continuously as model dimension grows.

Practical Implications

This work provides a clear geometric framework for understanding NGD's limitations, with several direct takeaways for practitioners:

• When the optimization target involves a quadratic potential family such as a fixed-covariance Gaussian, NGD can be used with confidence — it is theoretically optimal.
• For families like categorical distributions that satisfy bounded-skewness conditions, NGD's overhead is controllable and does not worsen qualitatively as dimension grows.
• When a model contains many scale-type parameters (such as covariance or rate parameters), especially in high-dimensional settings, NGD's path inefficiency will gradually manifest. In such cases, optimization strategies that more closely follow Fisher–Rao geodesics may offer better returns.

Through consistent theoretical proofs and experimental validation across all three regimes, the paper draws a clear boundary around the "geometric optimality" of natural gradient methods. This reminds us: the elegance of NGD does not imply universal optimality — its efficiency depends strongly on the geometric structure of the underlying distribution family.