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 \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 \(Θ(\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 \(π/(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).

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Machine Learning (Statistics)

• arXiv preprint · 5 October 2026

  Two-Sample Testing via Path-based Inference

  Eshant English, Wei-Cheng Lai, Yanfeng Yang and 3 others
• arXiv preprint · 6 October 2026

  Is $\sqrt{d}$ Separation Necessary for Gradient EM to Learn Gaussian Mixtures in High Dimensions?

  Yiran Zhang, Mo Zhou, Weihang Xu and 2 others
• arXiv preprint · 5 October 2026

  From Pixels, Without Pre-training: Joint Generative and Self-Supervised Representation Learning in One Model

  Vicente Balmaseda, Ching-Long Lin and Tianbao Yang
• arXiv preprint · 6 October 2026

  Learning a Mixture of GFlowNets

  Tiago da Silva, Amauri H. Souza and Salem Lahlou
• arXiv preprint · 5 October 2026

  Retrieval-Based In-Context Learning: A Domain Adaptation Framework

  Yilun Zhu, Naihao Deng, Yingcong Li and 2 others

All new papers in Machine Learning (Statistics)