- 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
-
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.
-
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.
-
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.
-
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
-
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.
-
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.
-
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 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?
-
Theorem 3.2 assumes . 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?
-
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.
-
On p. 4, lines 176--180, does agreement of the local linear objective include the value ? 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
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.
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.
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.