How Inefficient Is Natural Gradient Descent? From Exact Optimality to Theta ( √ log d ) Divergence

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 ≥ 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(√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 (π/(2√2)) is approached but not attained (II), and sampled scale-product (R) grows with (d), reaching (R ≈ 1.5) for long, high-dimensional moves (III).