How Inefficient Is Natural Gradient Descent? From Exact Optimality to Θ( \sqrt{ \log d } ) Divergence
Abstract
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 Θ(√(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).
Related
- Revisiting Natural Gradient Descent for PINNs Using Adaptive Collocation Strategies
- Gauss-Newton drifting extends natural gradient descent
- Broximal Gradient Descent: A Projection-Free Sister of Projected Gradient Descent
- Optimality of Threshold Policies for Heat Storage Optimization and a Policy Gradient Algorithm
- Minimax optimality for sequential gradient-free minimization of smooth functions and their derivatives
BibTeX
@misc{sharon2026inefficient,
title = {{How Inefficient Is Natural Gradient Descent? From Exact Optimality to Θ( \sqrt \log d ) Divergence}},
author = {Guni Sharon and Alan Kuhnle},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.07228},
eprint = {2610.07228},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.07228},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - How Inefficient Is Natural Gradient Descent? From Exact Optimality to Θ( \sqrt{ \log d } ) Divergence
AU - Guni Sharon
AU - Alan Kuhnle
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.07228
UR - https://arxiv.org/abs/2610.07228
AB - 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 Θ(√(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).
ER -