Natural gradient step size estimation can be computationally hard

The cost of useful natural gradient updates

Machine LearningInformation Theory

Summary

This paper looks at what is needed to make useful steps when updating models using the natural gradient method. The authors show that even when knowing the best direction to move, deciding how far to move can be very hard or costly, both in terms of computation and the number of samples needed. They support this with examples and complexity results, showing that sometimes finding a good step can be as difficult as solving tough problems in computer science. Their results highlight that knowing where to move in model space isn’t enough; how far to move carries the entire challenge.

What this means in practice

  • For machine learning engineers: Understand computational limits and sample costs when implementing natural gradient updates in complex models to better manage update strategies.
  • For optimization algorithm designers: Design update methods aware that efficient step size selection for natural gradients can be computationally intractable in certain model families.

Tested on simulated data.

Authors

Subhransu S. Bhattacharjee, Dylan Campbell, Rahul Shome

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 $\varepsilon$ 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\varepsilon^2))$ for small $\varepsilon$, 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.