The cost of useful natural gradient updates

Subhransu S. Bhattacharjee; Dylan Campbell; Rahul Shome

cs.LGSep 27, 2026

The cost of useful natural gradient updates

Authors: Subhransu S. Bhattacharjee, Dylan Campbell, Rahul Shome

Organizations: School of Computing, The Australian National University

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.

Figures & tables

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

(a) Four-state calibration			(b) Binary calibration
$mp_{\mathrm{M}}\varepsilon^{2}$	Plug-in (%)	Conservative (%)	$p$	Confidence (%)
$2^{4}$	48.97	52.78	$10^{-6}$	95.80
$2^{12}$	48.05	93.90	$10^{-5}$	96.39
$2^{20}$	50.29	100.00	$10^{-4}$	96.29
			$2^{-11}$	97.07

Appendix

Table A1: Joint success over 2,048 paired count simulations per setting. (a) Four-state law,

\omega=1.25

p_{\mathrm{M}}=2^{-30}

\varepsilon=1/8

. (b) Event-tilt confidence rule, 95% event-mass confidence set,

\varepsilon=1/32

mp\varepsilon^{2}=16

$mp_{\mathrm{M}}\varepsilon^{2}$	Upper success	Plug-in success	Upper max. rate	Plug-in max. rate
$2^{-2}$	24.02–73.19	24.02–73.19	40.09	40.09
$2^{0}$	40.87–89.31	40.87–89.50	19.97	19.97
$2^{2}$	47.61–99.17	46.78–99.32	3.81	4.25
$2^{4}$	50.78–100.00	48.93–100.00	0.00	0.05
$2^{6}$	53.12–100.00	49.95–100.00	0.00	0.00
$2^{8}$	55.71–100.00	48.10–100.00	0.00	0.00

Appendix

Table A2: All normalized budgets in the four-state study. Each success range spans the 12 settings of

(p_{\mathrm{M}},\omega,\varepsilon)

: two scale values, three law coefficients and two gain targets. Upper denotes the conservative rule. The last two columns give the largest rates of true KL exceeding

1.1\eta

across these settings. Entries are observed percentages over 2,048 repetitions per setting.

$p_{\mathrm{M}}$	$mp_{\mathrm{M}}\varepsilon^{2}$	P	P+R	P+O	P+O+R	P excess	P+O+R excess
$2^{-30}$	$2^{0}$	44.14	44.14	44.14	44.14	4.603	4.457
$2^{-30}$	$2^{4}$	48.97	51.56	50.39	52.78	1.071	0.935
$2^{-30}$	$2^{8}$	49.76	59.47	55.37	64.36	0.263	0.152
$2^{-30}$	$2^{12}$	48.05	83.01	70.61	93.90	0.068	0.010
$2^{-30}$	$2^{16}$	50.93	100.00	99.02	100.00	0.016	0.000
$2^{-30}$	$2^{20}$	50.29	100.00	100.00	100.00	0.004	0.000

Appendix

Table A3: Paired offset/rounding ablation at

\omega=1.25

\varepsilon=1/8

, reusing the 2,048 counts per row. P is plug-in, O adds the upward offset, and R rounds the step downward. The four central columns give joint-success percentages. The last two give the mean of

\max\{{\mathcal{K}}/\eta-1,0\}

over all trials, as a percentage of the KL budget.

$m/D_{\mathrm{L}}$	Euclidean pass	Fisher cosine	Finite gain	$S_{90}$
0.25	4.0	30.21	31.08	5.1
1	18.3	77.31	78.30	41.1
4	15.6	97.80	98.10	96.2
16	31.9	99.46	99.54	100.0
64	62.8	99.88	99.89	100.0
256	91.6	99.97	99.97	100.0

Appendix

Table A4: Post hoc Fisher alignment for the pseudoinverse direction at

K=1

D_{\mathrm{L}}=65536

and

\bar{\eta}=0.05

, reusing the 2,048 trials per row. All entries after the sample budget are percentages. Euclidean pass uses the

1/32

tolerance. Fisher cosine and finite gain are means over trials.

S_{90}

is the fraction attaining 90% of global optimal finite gain under reference-KL calibration. Zero directions remain in every denominator.

$m/D_{\mathrm{L}}$	Direction	Calibration	Feas.	Gain	$S_{90}$ [95% CI]
16	Population	Reference	100.0	100.0	100.0 [99.8, 100.0]
16	Population	Confidence	99.9	78.0	1.1 [0.7, 1.6]
16	Pseudoinverse	Reference	100.0	99.5	100.0 [99.8, 100.0]
16	Pseudoinverse	Confidence	99.9	76.9	0.5 [0.3, 1.0]
64	Population	Reference	100.0	100.0	100.0 [99.8, 100.0]
64	Population	Confidence	100.0	88.0	23.6 [21.8, 25.5]

Appendix

Table A5: Direction and calibration controls at

K=1

D_{\mathrm{L}}=65{,}536

and

\eta=0.05/D_{\mathrm{L}}

. The population method uses the exact direction, while the pseudoinverse method estimates it from the counts. Reference calibration uses the true law. Confidence calibration uses the simultaneous confidence set for cell masses from those same counts. All metrics are percentages over 2,048 paired repetitions per row. Feas. is true KL feasibility. Gain is mean improvement divided by the global constrained query optimum, with infeasible gains set to zero.

S_{90}

requires both feasibility and at least 90% of that optimum. Brackets are pointwise 95% Wilson intervals for

S_{90}

$K$	$D_{\mathrm{L}}$	$m/D_{\mathrm{L}}$	$A_{\rm dir}$	Feas.	Gain	$S_{90}$ [95% CI]
1	4,096	16	33.7	100.0	77.0	0.8 [0.5, 1.3]
1	4,096	64	61.2	100.0	87.5	19.2 [17.6, 21.0]
1	4,096	256	91.8	100.0	93.5	98.5 [97.9, 98.9]
1	65,536	16	33.2	99.9	76.9	0.5 [0.3, 1.0]
1	65,536	64	60.8	100.0	87.6	20.8 [19.1, 22.7]
1	65,536	256	91.6	100.0	93.5	98.7 [98.1, 99.1]

Appendix

Table A6: Pseudoinverse directions with confidence calibration at

\eta=0.05/D_{\mathrm{L}}

, over 2,048 repetitions per row.

A_{\rm dir}

is the percentage with direction error at most

1/32

. Feasibility is evaluated under the true law. Normalized feasible gain and joint success

S_{90}

use the global query optimum as in Table A5 . Brackets are pointwise 95% Wilson intervals for

S_{90}

(a) Matched expected count per block: $m/({n_{\mathrm{blk}}}D_{\mathrm{L}})=16$
	$K=1$		$K=2$
$d$	Successes	Gain (%)	Successes	Gain (%)
2	361	$99.53\pm 0.04$	410	$99.75\pm 0.02$
8	0	$98.15\pm 0.08$	1	$98.96\pm 0.04$
32	0	$97.71\pm 0.05$	0	$98.68\pm 0.03$
128	0	$97.62\pm 0.03$	0	$98.64\pm 0.01$

Appendix

Table A7: (a) Separate-block pseudoinverse at

m/({n_{\mathrm{blk}}}D_{\mathrm{L}})=16

. Direction successes are out of 1,024 and gains are percentages of the global optimum with 95% normal half-widths. (b) Gain at fixed total

m=16D_{\mathrm{L}},K=1

. All methods use reference-KL calibration.

	CIFAR-10 / ResNet-18	SST-2 / DistilBERT
Reference inputs	50,000 training inputs	67,349 training inputs
Query split (accuracy)	Test (95.34%)	Validation (91.055%)
Selected errors	32 of 466	32 of 78
Feature dimension / free head parameters	513 / 4,617	769 / 769

Appendix

Table A8: Fixed models. Features include an intercept, and the last class’s logits are fixed at zero to remove redundant head parameters.

Contrast (budget)	CIFAR-10	SST-2
Reference minus empirical calibration ( $0.01$ )	$-1.59$ [ $-5.09,1.75$ ]	$-0.112$ [ $-1.214,0.845$ ]
Reference direction minus estimated direction ( $0.01$ )	2.32 [ $-0.36,5.13$ ]	0.13 [ $-5.69,4.90$ ]
Estimated direction minus gradient direction ( $0.01$ )	156.97 [71.08,249.32]	1717.06 [1401.41,2021.48]
Reference direction minus estimated direction ( $0.001$ )	4.76 [1.10,8.64]	76.58 [52.35,101.32]

Appendix

Table A9: Paired raw-gain contrasts at

m=1024,\lambda=0.001

, in

10^{-3}

nats, with 95% query-bootstrap intervals. Direction contrasts use reference calibration.

Dataset	Full budget $\eta$	Margin $0.9\eta$	Margin gain (%)
	Joint success (%) [95% CI]
CIFAR-10	48.59 $[44.69,52.50]$	99.53 $[98.91,100.00]$	99.63
SST-2	50.94 $[47.34,54.69]$	93.75 $[91.09,96.25]$	99.79

Appendix

Table A10: Results for empirical calibration in Figure 2 at

m=16{,}384

and

\eta=0.01

. Joint success requires KL feasibility and at least 75% of the full-budget ray-optimal gain. Brackets give pointwise 95% query-bootstrap intervals. Margin gain averages each intervention’s raw gain as a percentage of the full-budget ray optimum. This mean includes infeasible updates.

Explore similar work

How Inefficient Is Natural Gradient Descent? From Exact Optimality to Θ( \sqrt{ \log d } ) Divergence
Oct 5, 2026Guni Sharon, Alan KuhnleFisher Information Matrix
Department of Computer Science and Engineering, Texas A&M University, College Station, TX 77843, USA.
Fisher-Rao Gradient Flows of Linear Programs and State-Action Natural Policy Gradients
Mar 28, 2024Johannes Müller, Semih Çaycı, Guido MontúfarPolicy Gradient Fisher Information Matrix
Department of Mathematics, RWTH Aachen University, Aachen, 52062, Germany · Departments of Mathematics and Statistics & Data Science, University of California, Los Angeles, 90095, USA · Max Planck Institute for Mathematics in the Sciences, Leipzig, 04103, Germany
Natural gradient descent with momentum
Apr 16, 2026Anthony Nouy, Agustín SomacalGradient Descent Gradient
Centrale Nantes, Nantes Universit´e, Laboratoire de Math´ematiques Jean Leray UMR CNRS 6629

Oct 5, 2026, stat.MLJ/K move · Enter open · S save

How Inefficient Is Natural Gradient Descent? From Exact Optimality to Θ( \sqrt{ \log d } ) Divergence

Guni Sharon, Alan Kuhnle

Department of Computer Science and Engineering, Texas A&M University, College Station, TX 77843, USA.

Fisher Information Matrix

Open paper AskPDF arXiv

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).

Abstract

Explore similar work

How Inefficient Is Natural Gradient Descent? From Exact Optimality to Θ( \sqrt{ \log d } ) Divergence

Fisher-Rao Gradient Flows of Linear Programs and State-Action Natural Policy Gradients

Natural gradient descent with momentum