arXiv：cs.LG· Guni Sharon, Alan Kuhnle·· 4 小时前AI 评分33
自然梯度下降有多低效？从精确最优到 Θ(√log d) 散度
How Inefficient Is Natural Gradient Descent? From Exact Optimality to \Theta ( \sqrt{ \log d } ) Divergence
AI 导读
研究量化了自然梯度下降（NGD）在双平坦分布族上沿混合测地线而非最短 Fisher–Rao 路径的额外开销，用低效比 R≥1 表示。按维度 d 给出三种区间：二次势族 R=1 处处精确最优；有界三阶偏度且 Fisher–Rao 直径有限时 R 有与维度无关上界；尺度族乘积（如高斯协方差、Gamma 速率）下 R 以 Θ(√log d) 增长且无界。
正文
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 \(\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).
| Subjects: | Machine Learning (stat.ML); Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.07228 [stat.ML] |
| (or arXiv:2610.07228v1 [stat.ML] for this version) | |
| https://doi.org/10.48550/arXiv.2610.07228 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Alan Kuhnle [view email]
[v1]
Mon, 5 Oct 2026 18:35:20 UTC (684 KB)
来源：arXiv：cs.LG · arxiv.org