The cost of useful natural gradient updates
Abstract
What information is needed to turn a natural-gradient direction into a useful finite update? Under a population Kullback-Leibler (KL) budget, we call a step useful if it is feasible and loses at most a fraction ε of the best feasible gain along the direction. We construct a four-state exponential family whose laws share their initial gradient, scalar Fisher information and natural gradient, yet two laws have disjoint useful-step sets. With these quantities supplied exactly and the law otherwise known only through draws, the family's worst-case sample complexity is Θ(log(1/δ)/(pε2)) for small ε, where p scales rare-state probabilities and δ is the failure probability. The budget is fixed and the optimal gain stays bounded away from zero, so the step length, not the direction, carries this cost. For succinctly described event-tilt models, returning a useful step is NP-hard even with the exact natural gradient and efficient exact sampling. Recovering the unit natural gradient to constant error is also NP-hard even in a two-parameter logistic family with Fisher condition number at most 3. We also give matching sample bounds for event tilts, sample bounds for damped Fisher solves and a population-KL certificate for affine classifiers. In frozen-feature classifier heads, stopping at a sampled KL boundary succeeds in about half of the trials, and a 10% KL margin raises joint success above 93% at a KL budget of 0.01. Thus, knowing where to move is not enough: how far to move can carry an update's entire cost.
Related
- Communication-Efficient Differentially Private Gradient Tracking for Distributed Optimization via Local Updates
- The first ℓ2-Betti number, cost and rank gradient of few-relator random groups
- Revisiting Natural Gradient Descent for PINNs Using Adaptive Collocation Strategies
- Entire p-harmonic functions with an isolated critical point and failure of C1-regularity of the natural gradient
- Gauss-Newton drifting extends natural gradient descent
BibTeX
@misc{bhattacharjee2026cost,
title = {{The cost of useful natural gradient updates}},
author = {Subhransu S. Bhattacharjee and Dylan Campbell and Rahul Shome},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.33499},
eprint = {2609.33499},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.33499},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The cost of useful natural gradient updates
AU - Subhransu S. Bhattacharjee
AU - Dylan Campbell
AU - Rahul Shome
PY - 2026
DA - 2026/09/27
PB - arXiv
DO - 10.48550/arxiv.2609.33499
UR - https://arxiv.org/abs/2609.33499
AB - What information is needed to turn a natural-gradient direction into a useful finite update? Under a population Kullback-Leibler (KL) budget, we call a step useful if it is feasible and loses at most a fraction ε of the best feasible gain along the direction. We construct a four-state exponential family whose laws share their initial gradient, scalar Fisher information and natural gradient, yet two laws have disjoint useful-step sets. With these quantities supplied exactly and the law otherwise known only through draws, the family's worst-case sample complexity is Θ(log(1/δ)/(pε^2)) for small ε, where p scales rare-state probabilities and δ is the failure probability. The budget is fixed and the optimal gain stays bounded away from zero, so the step length, not the direction, carries this cost. For succinctly described event-tilt models, returning a useful step is NP-hard even with the exact natural gradient and efficient exact sampling. Recovering the unit natural gradient to constant error is also NP-hard even in a two-parameter logistic family with Fisher condition number at most 3. We also give matching sample bounds for event tilts, sample bounds for damped Fisher solves and a population-KL certificate for affine classifiers. In frozen-feature classifier heads, stopping at a sampled KL boundary succeeds in about half of the trials, and a 10% KL margin raises joint success above 93% at a KL budget of 0.01. Thus, knowing where to move is not enough: how far to move can carry an update's entire cost.
ER -