{"id":"arxiv/2609.33499","url":"https://arxiv.org/abs/2609.33499","tags":["cs.LG","cs.IT","math.OC"],"score":0,"title":"The cost of useful natural gradient updates","domain":"cs.LG","source":"arxiv","authors":["Subhransu S. Bhattacharjee","Dylan Campbell","Rahul Shome"],"reviews":0,"subject":"cs.LG","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-27","reactions":{}}