acceptodds
Under review as a conference paper at ICLR 2027

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 for small , where 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 . 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 . Thus, knowing where to move is not enough: how far to move can carry an update's entire cost.

Primary area:
optimization
Keywords:
natural gradient, computational complexity, sample complexity, Fisher information, information geometry, step-size calibration

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_YQbyOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the cost of choosing a natural-gradient step that satisfies a population KL constraint and achieves a prescribed fraction of the best feasible gain. Its main construction uses four-state distributions with identical initial gradients and Fisher information, but different useful step lengths. The authors prove matching sample-complexity bounds for selecting such a step and additional computational lower bounds under specified information assumptions.

The paper also studies the difficulty of recovering the natural-gradient direction, analyzes damped estimates, and provides a finite-sample certificate for KL feasibility. Simulations and experiments with fixed classifier features illustrate the results.

Critical strengths
  1. The four-state construction keeps the initial gradient and Fisher information fixed while separating the useful step lengths. This isolates a difficulty that remains even when the natural-gradient direction is known exactly.

  2. The paper gives matching lower and upper sample-complexity bounds, with optimal gain bounded away from zero. The result therefore characterizes the estimation cost rather than providing only an impossibility example.

  3. The direction-recovery analysis distinguishes the Fisher condition number from the absolute scale of its eigenvalues. It shows why a bounded condition number alone need not make direction estimation easy.

  4. The paper complements the lower bounds with a finite-sample KL certificate under explicit assumptions. The experiments also help distinguish direction accuracy, constraint satisfaction, and objective improvement.

Critical weaknesses
  1. Motivation and significance. Given an exact natural-gradient direction, is step-size selection a long-standing open question, or does this paper introduce a new complexity question? The paper should provide historical context, discuss exact and practical line-search approaches, and explain why diminishing or unit step sizes are insufficient for its goal. This would clarify what the bounds reveal beyond the established difficulty of rare-event estimation.

  2. Unclear terminology and definitions. The meaning of "finite" in "a useful finite update" is unclear, as is the term "quadratic step." Technical concepts used throughout the paper should either be rigorously defined or supported by appropriate references, rather than left for the reader to infer. Labels such as “calibration” and “declared update family” could also be replaced with more direct language.

  3. Construction and proof intuition. Although individual design choices are explained, the overall construction remains difficult to follow. The paper should clarify how the probabilities and separation thresholds work together, how conservative the restriction pM≤2−30p_M\leq2^{-30} is, and whether separation persists at larger probabilities. A diagram connecting the constructions and main bounds would help.

Questions for authors

\item What prior result or concrete difficulty in natural-gradient step selection motivates this formulation? Does it address a previously identified open question or introduce a new formulation, and which existing result or example provides the closest comparison?

  1. Theorem 3.2 assumes pM≤2−30p_M\leq2^{-30}. To what extent is this range needed for the separation of useful step lengths, and how much does it reflect conservative estimates in the proof? Is there evidence from the existing analysis or a small numerical illustration that the same phenomenon persists at larger rare-event probabilities?

  2. Would it be possible to explain how the various constants in the constructions are chosen based on the conditions they need to satisfy? A worked construction would be more helpful here than further optimization of the numerical constants. A diagram summarizing the connections among the main results would also be helpful.

  3. On p. 4, lines 176--180, does agreement of the local linear objective include the value J(0)=E[h]J(0)=\mathbb{E}[h]? Matching the gradient and Fisher information alone gives matching variances. Is the intended statement instead that matching the first two moments is sufficient to match the local quantities? The explicit construction in Eq. (2) satisfies those moment identities; my question concerns the implication stated before it.

5 comments
AuthorsOpenReview ↗

Answering the questions and weaknesses by parts

Thank you for this review: we appreciate your patience and rigor and acknowledge the critical components to the best of our capability.

We appreciate that you named the four things we consider its substance: the four-state pair keeps the gradient and the Fisher information fixed while separating the useful steps, the bounds match with the best gain bounded away from zero, the direction analysis separates the condition number from the scale of the eigenvalues, and the certificate and experiments keep direction accuracy, constraint satisfaction and gain apart.

The revision keeps all four and changes how they are presented. The replies below take your weaknesses and questions in order, and we would welcome a further round on any of them, in case it is unclear.

Kindly note that we found that you used "\item" for the first question which did not render, so we have renumbered the questions to your intended numbering.

AuthorsOpenReview ↗

Motivation and the closest prior results (Weakness 1 & Question 1)

We believe, the question is new, and the approach is fundamentally novel, to the best of our knowledge.

No prior result bounds the samples a step rule needs to meet a population KL budget. Current methods decide the step by heuristics: ACKTR takes the quadratic step, TRPO backtracks on a sampled batch, PPO adapts a penalty, and each can exceed its budget. Section 2 places the question in oracle complexity (Nemirovski and Yudin, 1983; Agarwal et al., 2012) and reviews the earlier answers, exact line searches, which would need the population KL at every trial step, and stochastic line searches, which assume that each evaluation is accurate enough. The two closest single results are these. For the rate, Dagum et al. (2000) give the cost of estimating a small probability to relative accuracy, and Theorem 4.1 shows that a step rule pays that same cost without estimating any probability.

For step selection, the stochastic line search of Paquette and Scheinberg (2020) assumes accurate evaluations, and that accuracy is exactly what rare inputs make expensive. Unit and diminishing steps are fixed before any sample, so they return the same step for both members of the hard pair and fail in one of them (Section 4.1). This is what the bounds show beyond rare-event estimation: the two models have no useful step in common, so any useful output must tell them apart, whether or not the rule estimates a probability.

AuthorsOpenReview ↗

Terminology (Weakness 2)

We agree, and the terms you listed are gone: since the first version, we revisited the core areas and looked at them from first principles to make sure that we could provide simpler or more established terminologies without making the statements inaccurate.

"Finite update", "calibration" and "declared update family" no longer appear in the main text. Section 3 now defines each object in words before any symbol: the population KL and the reference distribution, the useful step (Definition 3.1), the boundary step, where the population KL reaches the budget, the quadratic step, where the quadratic model of the KL reaches it, and the sampled check. Every main theorem names the appendix that proves it, and the surrounding text gives the mechanism in words with the distilled intuition and follow up as also pointed out by reviewer: Hex1.

Reviewer_KVcqOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies the hardness of step size selection when using natural gradient descent. The authors provide an NP-hardness analysis for this and experimentally test it on real neural networks.

Critical strengths

While other existing works usually concentrate on approximating the natural gradient, the paper gives a fresh viewpoint that even though we know the direction, inferring a good step size can be hard.

Critical weaknesses

A limitation of this paper is that it is limited to one-step analysis. Although one-step analysis can be a reasonable starting point, multi-step analysis is usually significantly harder than one-step analysis, and addressing that can make the contribution stronger.

Questions for authors

It would be helpful if the authors could provide a more detailed explanation of the practical implications or applications (e.g., potential connections to practical deep neural network training).

1 comment
AuthorsOpenReview ↗

Addressing motivation and practical takeaways

Thank you for the review, and for stating the viewpoint of the paper so precisely as we intended.

On one-step analysis. We agree that a single update is the starting point, and we want to be clear about what the revision adds.

Every lower bound is stated for one update: the cost of a step is set by the rarest outcomes the update touches, and a second update does not make the first one cheaper. The certified check, however, now carries a guarantee over a whole run. Each update of a run receives a share of the failure probability, the shares sum to the stated budget, and the guarantee holds for every update as long as each one fixes its candidates and bounds before its fresh draws (Section 5, "Guarantees over a run", with the statement and proof in the appendix). On forty successive updates of two classifier heads, the check met both requirements every time. The sampled check from data did not. Thus, the only remaining future work is a lower bound for a whole run when samples are reused across updates, which we clarify in the limitations as future work.

On practical implications. Section 5.2 now tests the step rules of TRPO and ACKTR on six learned models, from affine heads to a full CIFAR-10 convolutional network, a WikiText-2 transformer, a policy and a regression network. In each one the costliest one percent of inputs carries a tenth to four fifths of the KL, which is the rare-input mechanism the theory predicts, and every fixed-sample rule fails in some model while the certified check does not. The failures cost accuracy: a step that spends twice the budget multiplies the held-out damage of the boundary step by a median factor of about two. Section 6 turns this into takeaways for anyone updating a network under a KL budget, including K-FAC, TRPO, PPO and KL-regularised fine-tuning, and explains how to run the check on a whole network with one forward-mode pass.

We would be glad to expand any of these points in our comments and add them to the revision, if it is accepted.

Reviewer_Hex1OpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

This paper studies the complexity of obtaining a useful natural gradient step, i.e. a step-size for a natural gradient update that is within a 1−ε1 - \varepsilon multiplicative factor of the optimal step within the KL budget constraint. The authors prove that this cannot be done using only the initial gradient and Fisher information, and that the sample complexity of estimating an ε\varepsilon-useful step with probability at least 1−δ1 - \delta is of order log⁡(1/δ)/(pε2)\log(1/\delta) / (p\varepsilon^2) where pp is the scale of a rare-event probability. The authors further prove the NP-hardness of finding the step, or the direction of the gradient, in various settings.

Critical strengths

I think the question studied here, i.e. "what is the complexity of finding an approximately optimal natural gradient step-size", can be an interesting and fundamental question to explore.

Critical weaknesses
  • It was very hard for me to read and follow this paper, and I'm not sure if I understand the contributions correctly. Part of it might be due to a particular AI writing style that is not informative and tends to be overly technical and detailed even when presenting the broad theme of the paper. If that's the case, I encourage the authors to revise their writing and develop a better narrative around the result.

  • I don't think the problem the authors are studying is well-motivated in the paper. I didn't find any discussion on the literature of "complexity of finding useful updates". The authors should explain why this question is important, how and if people have attempted to answer this in the past, and how their approach is different and novel.

  • All the main theorem statements are written in a bit of a convoluted and lengthy manner which makes them hard to parse, and to judge their importance. I don't think this is the optimal way to present the results. The authors should try to distill the most important information from each theorem / proposition and only present those in the main text.

Questions for authors

Please see above for my main concerns.

4 comments
AuthorsOpenReview ↗

A review of presentation & motivation

We thank you for the frank review, and for reading the paper carefully despite its presentation. We agree with your assessment. The submission led with technical detail where it should have led with the motivation and intuition. We have reorganised the paper with your suggestion in mind.

We appreciate that you identified the strength we care most about: the complexity of finding a useful step is a fundamental question, and the revision now builds the exposition around it. The introduction opens with a concrete failure of the quadratic step on a CIFAR-10 classifier, Section 2 places the question in oracle complexity (Nemirovski and Yudin, 1983; Agarwal et al., 2012) and names the closest results, stochastic line searches and rare-event estimation. Section 3 states the complexity problem in words before any symbol, Figure 3 maps how the results depend on one another, and Section 4 is split into the two results you asked us to distil: exact local information does not determine the step (Section 4.1), and computing it from a description is NP-hard (Section 4.2). Each theorem now states one conclusion with its rate and names the appendix that proves it, and the text around it gives the mechanism in words. Section 5 adds the matching upper bound, a certified check whose sample size meets the lower bound, so the answer to the question is exact rather than an impossibility result.

We hope the revision lets you judge the contributions on their content, and we would value any point where the exposition is still unclear.

AuthorsOpenReview ↗

Writing in AI style

We understand that the submission may have read as heavily written by AI. Our usage statement is accurate: we used AI tools to refine prose, and the mathematics, the constructions and the experiments are our own. The impression came from a choice we made, not from the tools. Under the page limit we chose a flat, dense style that stated every result with full rigour and little motivation, because we did not want accuracy to suffer. We now see that this made the paper hard to follow, and the revision rewrites the main text with the exposition first and the rigour kept in the statements and the appendix.

We welcome any further suggestion on style or structure that would present the central result more cohesively, and we will act on it: either by answering or (if accepted) making room for it in the paper by restructuring it. We strive hard to make sure that no reader finds the work "Difficult to follow despite careful reading."

Thank you for your response and for revising the paper. My concerns with the paper were at a fundamental level with the presentation, which require major revisions that cannot be reviewed during the discussion period. Properly assessing the new submission requires a fresh review of the paper and more time commitment than I can afford for the author-reviewer discussion period. Therefore, I have to keep my original score.

Thank you for letting us know, and we completely understand the time constraints during the discussion period.

For clarity every theorem, construction, and proof from the original submission is preserved intact (Theorems 4.1, 4.4, 4.5, 5.1, and Section 4.2), where your initial review noted no substantive soundness concerns (Soundness: 3).

Our revision directly implemented the structural changes you requested—leading with concrete motivation (Figure 1), distilling main-text theorem statements, and moving dense derivations to the appendix—alongside adding a matching constructive upper bound (Algorithm 1, Theorem 5.1) and six-model validation (Section 5).

Comments on the paper

5 comments
AuthorsOpenReview ↗

Rewriting the paper for clarity

Dear Reviewers,

Thank you for your time and thoughtful feedback. We appreciate your recognition of the technical soundness of our contributions and the originality of our approach to a well-studied problem.

Your reviews also highlight the need for substantial revision. In this rebuttal, we clarify the motivation, address the critical weaknesses identified, and respond directly to your questions.The revised manuscript is uploaded, and a summary of changes with their locations follows in a separate global comment.

Beyond the lower bounds, the revision adds a certified check with a matching upper bound (Algorithm 1, Theorem 5.1) and tests it against the step rules of TRPO and ACKTR on six kinds of model.

AuthorsOpenReview ↗

Full paper revision posted!

Dear readers,

We have uploaded a revised manuscript. The question is unchanged: how many samples does a reliable natural gradient step need when the direction is already known, and what does it cost to compute the step from a description of the model instead? The answers are also unchanged. What changed is how the paper states them and the empirical results that support them.

The main text is now written to be read without resorting to the appendix, such that the reorganization now restates all theorems and proofs in the appendix and keep the main paper intuitive while stating the major theorems. The introduction opens with one update whose exact direction still overshoots the budget, and each contribution says which area it draws on: trust-region optimization for the problem, rare-event estimation and the two-point method for the lower bound, counting complexity for the hardness results, and certification on fresh samples for the algorithm. Figure 3 maps every result to the single argument behind it and links to each theorem. Section 2 places the question in oracle complexity and names the closest prior results. Each symbol in the main text now has one meaning, and every symbol in a figure is introduced in the text.

We further add a structured subsection based on the ideas and questions the reviewers have raised including motivation and practical implication of this work. Appendix B.4 proves when Algorithm 1 stops (Lemma B.8), counts its KL evaluations against an exhaustive check, and records the choices behind the candidates, the abstention rule and the comparator. Section 4.1 now states that a unit or diminishing step fixed before any draw fails in the same way as every other rule that sees only the shared information.

Thank you for considering our revision.

Dear Reviewers,

Thank you for your thoughtful reviews. The authors have provided detailed responses to the concerns raised.

I would appreciate it if you could revisit the author responses and clarify whether your main concerns have been adequately addressed, particularly which issues remain critical to your overall assessment.

Given the differences in the initial recommendations, I also encourage you to consider and discuss one another's key arguments to help clarify the remaining disagreements and develop a more consistent understanding of the paper's merits and limitations.

Please feel free to update your ratings if your assessments have changed following the discussion.

Thank you for your continued contributions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.