First-ish Order Methods: Hessian-aware Scalings of Gradient Descent

Fred Roosta; Oscar Smee; Stephen J. Wright

REVIEW 3 major objections 6 minor 78 references

First-ish Order Methods: Hessian-aware Scalings of Gradient Descent

T0 review · 3 major / 6 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Hessian-aware gradient scaling gives gradient descent a unit step guarantee.

desk verdict Solid, checkable theory for Hessian-aware gradient scalings, undermined in the empirical section by selection bias and an assumption that likely fails on the paper's own benchmarks — still deserves peer review. read the letter →

arxiv 2502.03701 v3 pith:TTQPPPWG submitted 2025-02-06 math.OC cs.LG

Oscar Smee , Fred Roosta , Stephen J. Wright This is my paper · ORCID

classification math.OCcs.LG MSC 90C5390C2690C30

keywords Hessian-awarescalingscaledgradientdescentunitstepsizeguaranteesecond-orderconditionnonconvexoptimizationsufficient-decreaselinesearchdirectionalHessiansmoothnessinexact

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Gradient descent's main practical headache is choosing a learning rate: too small crawls, too large diverges, and backtracking line search costs extra evaluations and needs a sensible starting guess. This paper argues that a single piece of local curvature information, one Hessian-vector product along the gradient, can remove that headache. Its adaptive scaling picks a step direction of the form $p=-s g$, with $s$ chosen from three curvature regimes, so the direction always satisfies the second-order descent condition $\langle g,p\rangle + \langle p,Hp\rangle \le 0$. Under a directional smoothness assumption on the Hessian, the paper proves that the standard sufficient-decrease line-search condition accepts the unit step $\alpha=1$ once the gradient is small, and near nondegenerate local minima the unit step is accepted every iteration with linear convergence. If right, this gives gradient descent a second-order-like natural step while keeping first-order per-iteration cost, and it extends to inexact Hessians.

What carries the argument

The object that carries the argument is Algorithm 1's three-regime scaling selection: it converts one directional curvature measurement $\langle g,Hg\rangle$ into a scalar $s$ that is small when curvature is strong, capped at $1/\sigma$ in the limited-positive regime, and free in the negative-curvature regime. Proposition 2.2 upper-bounds all these scalings, and Proposition 2.3 turns those bounds into the second-order descent condition. The analytic machinery is the cubic Taylor upper bound $|f(x+p)-f(x)-\langle g,p\rangle - \frac12\langle p,Hp\rangle| \le (L_2/6)\|p\|^3$, which follows from the paper's Hessian directional smoothness assumption, combined with the sufficient-decrease line-search condition; together they produce explicit thresholds on $\|g\|$ under which $\alpha=1$ is guaranteed.

What would settle it

Run the exact line-search test from Theorem 3.3 on $f(x)=\frac12 x^T x + \epsilon\sum_i x_i^3$ with $\epsilon$ chosen so the Hessian is directionally smooth with known $L_2=6\epsilon$, sampling $x$ with $\|g\|$ below the threshold (8); any rejection of $\alpha=1$ contradicts the theorem.

Watch

Extended reading notes

Core claim

The central claim is that a gradient direction scaled by curvature, $p=-s g$, inherits the step-size wisdom of second-order methods without the cost of solving a full second-order system. Algorithm 1 checks the curvature $\langle g,Hg\rangle$ along the gradient: if it is strongly positive it sets $s$ to one of $s_{\mathrm{CG}}=\|g\|^2/\langle g,Hg\rangle$, $s_{\mathrm{MR}}=\langle g,Hg\rangle/\|Hg\|^2$, or $s_{\mathrm{GM}}=\|g\|/\|Hg\|$; if curvature is limited positive it caps $s\le 1/\sigma$; if curvature is negative it uses a scaling in a user-specified range and exploits the negative curvature. Proposition 2.3 shows all three cases keep $\langle g,p\rangle + \langle p,Hp\rangle \le 0$. Theorem 3.3 then shows that under Hessian directional smoothness, the sufficient-decrease condition holds at $\alpha=1$ whenever $\|g\|$ is below the explicit threshold (8), even for nonconvex functions. Theorem 3.7 upgrades this to a local linear rate with unit steps accepted at every iteration near a minimum satisfying the second-order sufficient conditions, and Theorem 3.9 shows the MR scaling gives linear contraction of the gradient norm. The same guarantees survive inexact Hessian estimates under a directional error bound.

Load-bearing premise

The proof's load-bearing premise is that the Hessian changes slowly along the negative-gradient direction at every point and every future step; if that directional smoothness constant does not exist along the optimization trajectory, the unit-step guarantee and the global convergence rate are unproven.

Editorial extensions

If this is right

Near a nondegenerate local minimum, the method runs with the unit step accepted at every iteration, so backtracking is bypassed and the function value converges linearly.
Globally, the method reaches a gradient norm below $\varepsilon_g$ in $O(\varepsilon_g^{-2})$ iterations under smoothness assumptions weaker than global Lipschitz gradient continuity.
Inexact Hessian information, such as a subsampled Hessian, preserves the unit-step guarantee and the global complexity bound provided the error along the gradient direction is bounded.
With the MR scaling, the gradient norm decreases monotonically and linearly, so the method implicitly minimizes the gradient norm as a secondary objective.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Editorial inference: because the curvature check needs only one Hessian-vector product, the scaling is a plausible drop-in for stochastic minibatch optimizers; the paper's proofs are deterministic, so a stochastic variant with subsampled Hessians is a testable extension rather than a stated result.
Editorial inference: the worst-case threshold (8) is much smaller than the region where unit steps are observed in the experiments, so a sharper analysis that averages curvature along the trajectory rather than bounding it globally would likely close that gap.
Editorial inference: the MR scaling's automatic gradient-norm contraction suggests a parameter-free implicit bias toward flat regions; comparing the generalization of MR-scaled runs with explicit gradient-norm penalties on identical architectures would test this directly.
Editorial inference: the paper notes that large scalings near $1/\mu$ remove the condition-number dependence from the local rate; a decreasing-$\sigma$ schedule that keeps the method in the strong-positive-curvature regime might reproduce that benefit more often, but the paper does not analyze such a schedule.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The short version: this is a competent theory paper with a clean unit-step-size guarantee for curvature-scaled gradient descent, and it deserves a serious referee. The experiments, however, are more favorable than the theory supports, and the central assumption is likely false on the paper's own benchmarks.

What's actually new: the scalings s_CG, s_MR, s_GM are old (steepest descent, minimal gradient, BB), but the paper's contribution is the analysis—the second-order descent condition, the local unit-step guarantee under directional Hessian smoothness, and global convergence under smoothness assumptions weaker than global Lipschitz gradient. The proofs are checkable. Proposition 2.3 is simple algebra; Theorem 3.3 follows from a cubic Taylor bound; the global convergence argument is consistent. The scalar invariance result is a nice touch. I also give credit for the inexact-Hessian extension, which is nontrivial.

Soft spots, roughly in order of severity. First, Assumption 3.1 is global: it requires the Hessian to be directionally Lipschitz along every ray x - t g(x), for all t >= 0. The paper says it's 'difficult to verify directly'; I'd go further. For the MLP and ResNet objectives with GeLU and LayerNorm, there is no reason to expect a finite L2. If L2 is infinite, the cubic bound (11) is vacuous, and Theorem 3.3, Theorem 3.7, and Proposition B.1 lose their foundation. The empirical observation that unit steps are accepted is then unexplained by the theory. Second, the gradient threshold (8) depends on sigma^2 for SPC steps; with the recommended small sigma, the provable unit-step region can be tiny. The authors acknowledge this in the limitations, but it undercuts the claim that the theory explains practice. Third, the numerical section reports the best scaling and best resetting scheme in the main body, which is selection bias. On ResNet18, tuned Adam and momentum methods beat the method; the paper says so. The 'competitive with Adam' claim is only true for the cherry-picked cases.

The central theoretical claims hold under the stated assumptions, and there's no circularity: no parameter is fitted to data to produce the theorems. The paper is self-contained and the references are appropriate.

Who should read it: optimization researchers studying adaptive gradient scaling and weakened smoothness. Practitioners will find the method useful but should not over-read the empirical section. A referee should ask for verification or weakening of Assumption 3.1 on the test problems, and an honest reporting of all scalings/reset schemes. I'd send it to peer review.

Referee Report

3 major / 6 minor

Summary. This paper proposes Hessian-aware scalar scalings of the gradient direction, p = -s g, where s is selected in three regimes (SPC, LPC, NC) according to the directional curvature <g,Hg>. The main theoretical results are: Proposition 2.3, which shows that the resulting direction satisfies the second-order descent condition <g,p> + <p,Hp> <= 0; Theorem 3.3, which gives a sufficient condition under Assumption 3.1 for the Armijo condition to hold with unit step size; Proposition 3.6, which establishes an O(epsilon_g^{-2}) global complexity bound under Assumptions 3.1 and 3.4; Theorem 3.7, which shows local linear convergence near a second-order sufficient minimum with a unit step; and Theorem 3.9, which proves linear convergence in the gradient norm for the MR scaling. Numerical experiments on logistic regression, an MLP, and a ResNet18 compare the method against fixed-step, accelerated, and line-search baselines, reporting oracle-call counts and observing frequent acceptance of alpha=1.

Significance. If the stated results hold, the paper makes a useful conceptual contribution: it shows that a one-dimensional curvature-aware scaling of the gradient can inherit some of the unit-step behavior usually associated with second-order methods, at the cost of one Hessian-vector product per iteration. The analysis is self-contained and the algebra in Propositions 2.2, 2.3, and 2.5 is checkable. The authors are careful to phrase the best-case improved rate in Section 3.2 as conditional rather than as a theorem, and the inexact-Hessian extension is a genuine addition. The numerical study uses oracle-call counts, covers convex and nonconvex problems, and the authors report code availability. The main reservation is that the central unit-step and global-convergence theorems rest on a global directional Hessian smoothness assumption that is not verified for the benchmarks and can fail for smooth nonconvex objectives; the empirical behavior is therefore not fully explained by the theory. In addition, the ResNet experiment uses rho=0, outside the assumptions of all convergence results.

major comments (3)

[Section 3.1, Assumption 3.1 and Eq. (11)] Assumption 3.1 is load-bearing for the central claims: it is used to derive the cubic bound (11), which is the only bridge from the second-order descent condition (3) to the unit-step Armijo guarantee in Theorem 3.3, and it is also used in Proposition 3.6 and Theorem 3.7. The assumption is global (all x in R^d and all t >= 0) and is not verified on any of the Section 4 problems. For smooth nonconvex objectives with unbounded higher-order growth, e.g., f(x) = (a^T x)^4, the Hessian along a negative-gradient ray is unbounded and no finite L2 exists, so (11) and the results built on it do not apply. Remark 3.2 only says the assumption is difficult to verify; the paper should either replace it by a local or checkable condition (for example, with an L2 that depends on the current iterate) or provide empirical estimates of the directional Hessian variation for the tested benchmarks. Without this, the frequent acceptance of alpha=1 in Figures 2-4 is not explained by Theorem 3.3.
[Appendix A.1 and Theorem 3.3] The recommended hyperparameter setting is incompatible with the only unit-step theorem. Appendix A.1 recommends sigma small, "or even zero", and for strongly convex problems sigma = 0. But Theorem 3.3 and its proof use the bound s <= 1/sigma and the first term 6 sigma^2(1/2 - rho)/L2 in (8); for sigma = 0 the theorem has no content in the non-negative curvature case, and the proof divides by sigma. If sigma is merely small, 6 sigma^2(1/2 - rho)/L2 is tiny, making the provable unit-step region minuscule. The limitations paragraph acknowledges this, but the claim in the abstract that the method "ensures a local unit step size guarantee" should be qualified by the parameter regime in which (8) is actually satisfied.
[Appendix D.5 (ResNet18 experiment)] For the ResNet18 benchmark, the paper sets rho = 0 in the Armijo condition (7) (Appendix D.5, "Parameter Settings"), while every convergence result in Section 3 and Appendix B assumes rho in (0,1/2). With rho = 0, the descent constants cSPC, cLPC, cNC in Proposition B.1 vanish, so the O(epsilon_g^{-2}) complexity bound and the local linear rate in Theorem 3.7 have no content for this experiment. The main text and figure caption should either report a run with rho > 0 or state explicitly that the ResNet experiment is outside the theoretical framework.

minor comments (6)

[Section 2.2] "a Lg-Lipschitz gradient" should read "an Lg-Lipschitz gradient".
[Section 3.2] "This reflected in the practical performance" should be "This is reflected in the practical performance".
[Appendix B.3] "the factor based on L1 and L2 could are smaller" should be "the factor based on L1 and L2 could be smaller".
[Appendix B.4] The heading "Amijo condition" is a typo for "Armijo condition".
[Appendix D.1] "Following the typical convection" should be "Following the typical convention".
[References] Reference [73] lists the publisher as "PMLP"; this should be "PMLR".

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the Hessian-aware scalings are derived from explicit quadratic-model minimizations and the convergence theorems follow from stated assumptions without fitted inputs.

full rationale

The main derivation chain is self-contained. The scalings s_CG, s_MR, and s_GM are obtained by explicitly minimizing local quadratic models along p = -s g: s_CG = ||g||^2/<g,Hg> solves the Newton quadratic restricted to the gradient direction, s_MR = <g,Hg>/||Hg||^2 solves min ||Hp+g||^2, and s_GM is their geometric mean. Proposition 2.3 verifies the second-order descent condition <g,p>+<p,Hp> <= 0 directly from these definitions, so the key direction property is constructed rather than imported. Theorem 3.3 derives the unit-step Armijo guarantee from Assumption 3.1 through the cubic bound (11); the gradient threshold (8) is obtained algebraically from the scaling upper bounds s <= 1/sigma and s <= s_NC_max, not from any fitted parameter or from the convergence conclusion. Global convergence (Proposition 3.6 and Proposition B.1) follows from per-iteration descent estimates in Lemma B.2 and scaling lower bounds in Lemma B.4 under Assumptions 3.1 and 3.4; it is a conditional complexity bound with explicitly stated constants. Local results (Theorems 3.7 and 3.9) use second-order sufficient conditions and independent contraction arguments. Section 4 is empirical validation and is not used as an input to any theorem. The self-citations ([42], [43], [63], [66]) are used for motivation, for the Newton-MR/Newton-CG connection, and for the contextual remark that moral smoothness implies Assumption 3.4; none of these citations is load-bearing for the paper's proofs, which use Assumption 3.4 as a stated assumption. No uniqueness theorem from the authors is invoked, and no external result is renamed as a new finding. The unverifiability of Assumption 3.1 flagged in Remark 3.2 is a correctness and robustness concern, not a circularity concern.

Assumptions & free parameters 4 free parameters · 6 assumptions · 0 invented entities

The theorems depend on weakened smoothness assumptions (3.1, 3.4, B.9, B.12) rather than on fitting. The method's hyperparameters (sigma, s ranges) are user-chosen and appear in the constants of the convergence bounds. No new entities are introduced.

free parameters (4)

sigma = 0 for convex experiments, 1e-6 for nonconvex
SPC tolerance; chosen by hand. Affects the classification of curvature cases and the upper bound 1/sigma on step scalings. Not fitted to data.
s_LPC_min, s_LPC_max = 1/sigma or 1
Range for limited positive curvature scalings; set to fixed values in experiments. User-chosen.
s_NC_min, s_NC_max = 1
Range for negative curvature scalings; set to 1 in experiments. User-chosen.
rho, theta = rho=1e-4, theta=0.5
Line search parameters used in experiments; standard values, not fitted.

assumptions (6)

domain assumption f is twice continuously differentiable and bounded below
Stated in the introduction; needed for Hessian-vector products and Taylor expansions.
domain assumption Assumption 3.1: Hessian directional smoothness, ||H(x - t g(x)) - H(x)|| <= t L2 ||g(x)|| for all x, t >= 0
Used in Theorem 3.3 and Lemma B.2 to control the cubic remainder in the Taylor expansion; the paper notes it is difficult to verify directly.
domain assumption Assumption 3.4: if <g,Hg> > 0 then ||Hg|| <= L1 ||g||
Used in Lemma B.4 to lower-bound SPC scalings, required for the global convergence proposition.
domain assumption Assumption B.9: existence of mu0, nu0 with |<g,Hg>| >= mu0||g||^2 and cos^2(angle(g,Hg)) >= nu0 along MR iterates
Used only for Theorem 3.9's gradient-norm convergence; the authors show it is implied near a second-order sufficient minimum.
domain assumption Assumption B.12: |<g,(H - tilde H)g>| <= Delta_H ||g||^2 for the inexact Hessian
Used in Appendix B.7 to extend unit step and convergence results to inexact Hessians.
standard math Taylor expansion with integral remainder and cubic upper bound (11)
Standard calculus result used in all proofs.

how reviews work

0 comments

Cite this review

Pith. "Pith review of First-ish Order Methods: Hessian-aware Scalings of Gradient Descent." pith.science (2026). https://pith.science/paper/TTQPPPWG

@misc{pith2026250203701,
  author       = {Pith},
  title        = {Pith review of: First-ish Order Methods: Hessian-aware Scalings of Gradient Descent},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TTQPPPWG}},
  note         = {Machine review of arXiv:2502.03701}
}

read the original abstract

Gradient descent is the primary workhorse for optimizing large-scale problems in machine learning. However, its performance is highly sensitive to the choice of the learning rate. A key limitation of gradient descent is its lack of natural scaling, which often necessitates expensive line searches or heuristic tuning to determine an appropriate step size. In this paper, we address this limitation by incorporating Hessian information to scale the gradient direction. By accounting for the curvature of the function along the gradient, our adaptive, Hessian-aware scaling method ensures a local unit step size guarantee, even in nonconvex settings. Near a local minimum that satisfies the second-order sufficient conditions, our approach achieves linear convergence with a unit step size. We show that our method converges globally under a significantly weaker version of the standard Lipschitz gradient smoothness assumption. Even when Hessian information is inexact, the local unit step size guarantee and global convergence properties remain valid under mild conditions. Finally, we validate our theoretical results empirically on a range of convex and nonconvex machine learning tasks, showcasing the effectiveness of the approach.

Figures

Figures reproduced from arXiv: 2502.03701 by the authors.

**Figure 1.** Logistic regression on the Mushrooms dataset [1]. We compare our scaling approach to standard GD with backtracking line search, using different initialization of the backtracking procedure (α 0 ), and assess performance based on oracle calls (Appendix D.1). The average number of backtracking steps per iteration is reported in brackets. With an arbitrary initialization, x0, the only hyperparameter is the step size,… view at source ↗

**Figure 2.** Multi-class logistic regression on CIFAR10. (a) Objective value. (b) Scaling utilized by the [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

**Figure 3.** MLP on the FashionMNIST. (a) Objective value (b) Scaling utilized by the CGMR method [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗

Figures from the paper (16 more)

**Figure 4.** Figure 4: ResNet18 on Imagenette. (a) Objective value. (b) Scaling utilized by the MRCG method. [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]

**Figure 5.** Figure 5: Multi-class logistic regression on CIFAR10 (Figure 2 with PoNo line search included). (a) [PITH_FULL_IMAGE:figures/full_fig_p036_5.png]

**Figure 6.** Figure 6: Comparison between scaling method performance for multiclass logistic regression on [PITH_FULL_IMAGE:figures/full_fig_p036_6.png]

**Figure 7.** Figure 7: Performance of the CG scaling on the multi-class logistic regression problem on CIFAR10. [PITH_FULL_IMAGE:figures/full_fig_p037_7.png]

**Figure 8.** Figure 8: Performance of the MR scaling on the multi-class logistic regression problem on CIFAR10. [PITH_FULL_IMAGE:figures/full_fig_p037_8.png]

**Figure 9.** Figure 9: Wall-clock time for multi-class logistic regression on the CIFAR10 dataset. [PITH_FULL_IMAGE:figures/full_fig_p037_9.png]

**Figure 10.** Figure 10: MLP on the FashionMNIST (Figure 3 with PoNo line search included). (a) Objective [PITH_FULL_IMAGE:figures/full_fig_p038_10.png]

**Figure 11.** Figure 11: Comparison between scaling methods for MLP on FashionMNIST dataset. [PITH_FULL_IMAGE:figures/full_fig_p038_11.png]

**Figure 12.** Figure 12: Performance of the CG scaling for the MLP on the FashionMNIST dataset. (a) The [PITH_FULL_IMAGE:figures/full_fig_p039_12.png]

**Figure 13.** Figure 13: Performance of the MR scaling for the MLP on the FashionMNIST dataset. (a) The [PITH_FULL_IMAGE:figures/full_fig_p039_13.png]

**Figure 14.** Figure 14: Wall-clock time results for MLP on the FashionMNIST dataset [ [PITH_FULL_IMAGE:figures/full_fig_p039_14.png]

**Figure 15.** Figure 15: ResNet18 on Imagenette (Figure 4 with PoNo line search included.) (a) Objective value. [PITH_FULL_IMAGE:figures/full_fig_p040_15.png]

**Figure 16.** Figure 16: Comparison of scaling method performance on for the ResNet18 model on the Imagenette [PITH_FULL_IMAGE:figures/full_fig_p041_16.png]

**Figure 17.** Figure 17: Performance of the CG scaling for the ResNet18 model on Imagenette dataset. (a) The [PITH_FULL_IMAGE:figures/full_fig_p041_17.png]

**Figure 18.** Figure 18: Performance of the MR scaling for the ResNet18 model on Imagenette dataset. (a) The [PITH_FULL_IMAGE:figures/full_fig_p041_18.png]

**Figure 19.** Figure 19: Wall-clock time results for the ResNet18 model on Imagenette dataset. [PITH_FULL_IMAGE:figures/full_fig_p042_19.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

78 extracted references · 71 canonical work pages

[1]

Mushroom

(1981). Mushroom. UCI Machine Learning Repository. Accessed under CC-BY 4.0 License. DOI: https://doi.org/10.24432/C5959T

doi:10.24432/c5959t 1981
[2]

Ahn, K., Zhang, J., and Sra, S. (2022). Understanding the unstable convergence of gradient descent. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S., editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 247–257. PMLR

work page 2022
[3]

and Parrilo, P

Altschuler, J. and Parrilo, P. (2024). Acceleration by stepsize hedging: Multi-step descent and the silver stepsize schedule. J. ACM

work page 2024
[4]

L., Kiros, J

Ba, J. L., Kiros, J. R., and Hinton, G. E. (2016). Layer normalization

work page 2016
[5]

and Dherin, B

Barrett, D. and Dherin, B. (2021). Implicit gradient regularization. In International Conference on Learning Representations

work page 2021
[6]

and Borwein, J

Barzilai, J. and Borwein, J. M. (1988). Two-point step size gradient methods. IMA Journal of Numerical Analysis, 8(1):141–148

work page 1988
[7]

G., Pearlmutter, B

Baydin, A. G., Pearlmutter, B. A., Radul, A. A., and Siskind, J. M. (2018). Automatic differenti- ation in machine learning: A survey. Journal of Machine Learning Research, 18(153):1–43

work page 2018
[8]

S., Roberts, L., and Roosta, F

Berahas, A. S., Roberts, L., and Roosta, F. (2024). Non-uniform smoothness for gradient descent. Transactions on Machine Learning Research

work page 2024

Show all 78 references

[9]

and Roulet, V

Blondel, M. and Roulet, V . (2024). The elements of differentiable programming

2024
[10]

Boyd, S. P. and Vandenberghe, L. (2004).Convex Optimization. Cambridge University Press, Cambridge, UK ; New York

2004
[11]

Burdakov, O., Dai, Y ., and Huang, N. (2019). Stabilized Barzilai-Borwein method.Journal of Computational Mathematics, pages 916–936

2019
[12]

Cartis, C., Gould, N. I. M., and Toint, P. L. (2022).Evaluation Complexity of Algorithms for Nonconvex Optimization: Theory, Computation, and Perspectives . Society for Industrial and Applied Mathematics, Philadelphia

2022
[13]

Castera, C., Bolte, J., Févotte, C., and Pauwels, E. (2022). Second-Order Step-Size Tuning of SGD for Non-Convex Optimization. Neural Processing Letters, 54(3):1727–1752

2022
[14]

Z., and Talwalkar, A

Cohen, J., Kaur, S., Li, Y ., Kolter, J. Z., and Talwalkar, A. (2021). Gradient descent on neural networks typically occurs at the edge of stability. In International Conference on Learning Representations

2021
[15]

Curtis, F. E. and Robinson, D. P. (2019). Exploiting negative curvature in deterministic and stochastic optimization. Mathematical Programming, 176(1-2):69–94. 10

2019
[16]

Dai, Y .-H., Huang, Y ., and Liu, X.-W. (2019). A family of spectral gradient methods for optimization. Computational Optimization and Applications, 74(1):43–65

2019
[17]

Dai, Y . H. and Yang, X. Q. (2006). A New Gradient Method with an Optimal Stepsize Property. Computational Optimization and Applications, 33(1):73–88

2006
[18]

and Yuan, Y .-X

Dai, Y .-H. and Yuan, Y .-X. (2003). Alternate minimization gradient method.IMA Journal of Numerical Analysis, 23:377–393

2003
[19]

and Gossard, A

de Gournay, F. and Gossard, A. (2022). Adaptive scaling of the learning rate by second order automatic differentiation. arXiv preprint arXiv:2210.14520

2022 arXiv
[20]

and Mishchenko, K

Defazio, A. and Mishchenko, K. (2023). Learning-rate-free learning by D-adaptation. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J., editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of ...

2023
[21]

Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K., and Fei-Fei, L. (2009). Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pages 248–255. Ieee

2009
[22]

Drineas, P., Kannan, R., and Mahoney, M. W. (2006). Fast Monte Carlo algorithms for matrices I: Approximating matrix multiplication. SIAM Journal on Computing, 36(1):132–157

2006
[23]

Fletcher, R. (2005). On the Barzilai-Borwein Method. In Qi, L., Teo, K., and Yang, X., editors, Optimization and Control with Applications, volume 96, pages 235–256. Springer-Verlag, New York

2005
[24]

and Schmidt, M

Fox, C. and Schmidt, M. (2024). Glocal smoothness: Line search can really help! In OPT 2024: Optimization for Machine Learning

2024
[25]

Galli, L., Rauhut, H., and Schmidt, M. (2023). Don’t be so Monotone: Relaxing Stochastic Line Search in Over-Parameterized Models

2023
[26]

Gonzaga, C. C. and Schneider, R. M. (2016). On the steepest descent algorithm for quadratic functions. Computational Optimization and Applications, 63(2):523–542

2016
[27]

Goodfellow, I., Bengio, Y ., and Courville, A. (2016). Deep Learning. MIT press

2016
[28]

Gould, N. I. M., Lucidi, S., Roma, M., and Toint, Ph. L. (2000). Exploiting negative curvature directions in linesearch methods for unconstrained optimization. Optimization Methods and Software, 14(1-2):75–98

2000
[29]

Grimmer, B. (2024). Provably faster gradient descent via long steps. SIAM Journal on Optimization, 34(3):2588–2608

2024
[30]

He, K., Zhang, X., Ren, S., and Sun, J. (2016). Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 770–778

2016
[31]

and Gimpel, K

Hendrycks, D. and Gimpel, K. (2016). Gaussian error linear units (GELUs). arXiv preprint arXiv:1606.08415

2016 arXiv
[32]

and Schmidhuber, J

Hochreiter, S. and Schmidhuber, J. (1997). Flat Minima. Neural Computation, 9(1):1–42

1997
[33]

Howard, J. (2019). Imagenette: A smaller subset of 10 easily classified classes from Imagenet. Accessed under Apache 2.0 License. URL: https://github.com/fastai/imagenette

2019
[34]

and Szegedy, C

Ioffe, S. and Szegedy, C. (2015). Batch normalization: accelerating deep network training by reducing internal covariate shift. In Proceedings of the 32nd International Conference on International Conference on Machine Learning - Volume 37, ICML’15, page 448–456. JMLR.org

2015
[35]

Ivgi, M., Hinder, O., and Carmon, Y . (2023). DoG is SGD’s best friend: A parameter-free dynamic step size schedule. In International Conference on Machine Learning, pages 14465– 14499. PMLR. 11

2023
[36]

Karakida, R., Takase, T., Hayase, T., and Osawa, K. (2023). Understanding gradient regulariza- tion in deep learning: Efficient finite-difference computation and implicit bias. In International Conference on Machine Learning, pages 15809–15827. PMLR

2023
[37]

S., Mudigere, D., Nocedal, J., Smelyanskiy, M., and Tang, P

Keskar, N. S., Mudigere, D., Nocedal, J., Smelyanskiy, M., and Tang, P. T. P. (2016). On large-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv:1609.04836

2016 arXiv
[38]

Khaled, A., Mishchenko, K., and Jin, C. (2023). DoWG unleashed: An efficient universal parameter-free gradient descent method. Advances in Neural Information Processing Systems, 36:6748–6769

2023
[39]

Kingma, D. P. (2014). Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980

2014 arXiv
[40]

Krizhevsky, A. (2009). Learning multiple layers of features from tiny images. Technical report, University of Toronto. Accessed under unknown license

2009
[41]

Lan, G. (2020). First-Order and Stochastic Optimization Methods for Machine Learning . Springer Series in the Data Sciences. Springer International Publishing, Cham

2020
[42]

and Roosta, F

Lim, A. and Roosta, F. (2023). Complexity guarantees for nonconvex Newton-MR under inexact Hessian information. arXiv preprint arXiv:2308.09912

2023 arXiv
[43]

and Roosta, F

Liu, Y . and Roosta, F. (2022). A Newton-MR algorithm with complexity guarantees for nonconvex smooth unconstrained optimization. arXiv preprint arXiv:2208.07095

2022 arXiv
[44]

Loizou, N., Vaswani, S., Laradji, I., and Lacoste-Julien, S. (2021). Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence. In 24th International Conference on Artificial Intelligence and Statistics

2021
[45]

MacDonald, L., Murray, R., and Tappenden, R. (2024). On a family of relaxed gradient descent methods for quadratic minimization. arXiv preprint arXiv:2404.19255

2024 arXiv
[46]

and Mishchenko, K

Malitsky, Y . and Mishchenko, K. (2020). Adaptive gradient descent without descent. In III, H. D. and Singh, A., editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 6702–6712. PMLR

2020
[47]

and Mishchenko, K

Malitsky, Y . and Mishchenko, K. (2024). Adaptive proximal gradient method for convex optimization. In The Thirty-eighth Annual Conference on Neural Information Processing Systems

2024
[48]

and Grosse, R

Martens, J. and Grosse, R. (2015). Optimizing neural networks with Kronecker-factored approximate curvature. In International conference on machine learning , pages 2408–2417. PMLR

2015
[49]

and Defazio, A

Mishchenko, K. and Defazio, A. (2024). Prodigy: an expeditiously adaptive parameter-free learner. In Proceedings of the 41st International Conference on Machine Learning , ICML’24. JMLR.org

2024
[50]

Mishkin, A., Khaled, A., Wang, Y ., Defazio, A., and Gower, R. M. (2024). Directional smoothness and gradient methods: Convergence and adaptivity. arXiv preprint arXiv:2403.04081

2024 arXiv
[51]

Murphy, K. P. (2012). Machine Learning: A Probabilistic Perspective. Adaptive Computation and Machine Learning Series. MIT Press, Cambridge, MA

2012
[52]

Nesterov, Y . (2004). Introductory Lectures on Convex Optimization, volume 87 of Applied Optimization. Springer US, Boston, MA

2004
[53]

and Polyak, B

Nesterov, Y . and Polyak, B. (2006). Cubic regularization of Newton method and its global performance. Mathematical Programming, 108(1):177–205

2006
[54]

and Wright, S

Nocedal, J. and Wright, S. J. (2006). Numerical Optimization. Springer Series in Operation Research and Financial Engineering. Springer, New York, NY , second edition edition. 12

2006
[55]

and Loizou, N

Oikonomou, D. and Loizou, N. (2024). Stochastic Polyak step-sizes and momentum: Conver- gence guarantees and practical performance. arXiv preprint arXiv:2406.04142

2024 arXiv
[56]

Orvieto, A., Lacoste-Julien, S., and Loizou, N. (2022). Dynamics of SGD with stochastic Polyak stepsizes: Truly adaptive variants and convergence to exact solution. Advances in Neural Information Processing Systems, 35:26943–26954

2022
[57]

Paige, C. C. and Saunders, M. A. (1975). Solution of sparse indefinite systems of linear equations. SIAM Journal on Numerical Analysis, 12(4):617–629

1975
[58]

Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang, E., DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S. (2019). PyTorch: A...

2019
[59]

and Berahas, A

Patel, V . and Berahas, A. S. (2024). Gradient descent in the absence of global Lipschitz continuity of the gradients. SIAM Journal on Mathematics of Data Science, 6(3):602–626

2024
[60]

Patel, V ., Zhang, S., and Tian, B. (2022). Global convergence and stability of stochastic gradient descent. Advances in Neural Information Processing Systems, 35:36014–36025

2022
[61]

Pearlmutter, B. A. (1994). Fast Exact Multiplication by the Hessian. Neural Computation, 6(1):147–160

1994
[62]

Polyak, B. T. (1987). Introduction to Optimization. Translations series in mathematics and engineering. Optimization Software, Publications Division, New York

1987
[63]

Roosta, F., Liu, Y ., Xu, P., and Mahoney, M. W. (2022). Newton-MR: Inexact Newton Method with minimum residual sub-problem solver. EURO Journal on Computational Optimization , 10:100035

2022
[64]

and Mahoney, M

Roosta, F. and Mahoney, M. W. (2019). Sub-sampled Newton methods. Mathematical Pro- gramming, 174(1-2):293–326

2019
[65]

M., Blondel, M., and Pedregosa, F

Roulet, V ., Agarwala, A., Grill, J.-B., Swirszcz, G. M., Blondel, M., and Pedregosa, F. (2024). Stepping on the edge: Curvature aware learning rate tuners. In The Thirty-eighth Annual Confer- ence on Neural Information Processing Systems

2024
[66]

and Roosta, F

Smee, O. and Roosta, F. (2024). Inexact Newton-type Methods for Optimisation with Nonnega- tivity Constraints. In Forty-First International Conference on Machine Learning

2024
[67]

L., Dherin, B., Barrett, D., and De, S

Smith, S. L., Dherin, B., Barrett, D., and De, S. (2021). On the origin of implicit regularization in stochastic gradient descent. In International Conference on Learning Representations

2021
[68]

Vaswani, S., Mishkin, A., Laradji, I., Schmidt, M., Gidel, G., and Lacoste-Julien, S. (2021). Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates

2021
[69]

Wright, S. J. and Recht, B. (2022). Optimization for Data Analysis. Cambridge University Press, 1 edition

2022
[70]

and He, K

Wu, Y . and He, K. (2018). Group normalization. InProceedings of the European Conference on Computer Vision (ECCV)

2018
[71]

Xiao, H., Rasul, K., and V ollgraf, R. (2017). Fashion-MNIST: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.07747. Accessed under MIT license

2017 arXiv
[72]

Xu, P., Roosta, F., and Mahoney, M. W. (2020). Second-order optimization for non-convex machine learning: an empirical study. In Proceedings of the 2020 SIAM International Conference on Data Mining (SDM), pages 199–207

2020
[73]

Zhao, Y ., Zhang, H., and Hu, X. (2022). Penalizing Gradient Norm for Efficiently Improving Generalization in Deep Learning. In International Conference on Machine Learning. PMLP. 13 A Additional Material for Section 2 A.1 Discussion of Algorithm 1 Hyperparameters We now consi...

2022
[74]

big data

and q = 1 − √1 − ν0. We have ak < qand ak+1 ≤ a2 k + √ 1 − ν0ak = (ak + √ 1 − ν0)ak = (1 + ak − q)ak. Also, since αk − q <0 by (29), ak(1 + ak − q) = (1 − (ak − q))(1 + (ak − q)) (1 − (ak − q)) ak = (1 − (ak − q)2) 1 − (ak − q) ak ≤ ak 1 + q − ak , where the inequality follows...
[75]

On the third line we apply ∥˜p∥ ≥sNC min ∥g∥ and ∥g∥ > εg, whereas on the fourth line we apply Lemma B.16 and εg < 1

Therefore, when (33) is satisfied, we have f (x + α˜p) − f (x) ≤ −αρ ∥˜p∥ ∥g∥ ≤ −ρ − 3∆H 2L2 + s 9∆2 H 4L2 2 + 6(1 − ρ) ∥˜p∥ L2sNCmax ! ∥g∥ < −ρ − 3∆H 2L2 + s 9∆2 H 4L2 2 + 6(1 − ρ)sNC minεg L2sNCmax ! εg ≤ −ρ   6(1 − ρ)sNC min/(L2sNC max) 3∆H 2L2 + r 9∆2 H 4L2 2 + 6(1−ρ)s...
[76]

large ˜p

∥g∥, which follows from (34), and ∥g∥ > εg in the fourth line, while in the fifth line we apply Lemma B.16. In the final line we define ˜cSPC ≜ ρ min    12σ2(1/2 − ρ)/ ˜L2 1 3∆H + q 9∆2 H + 24σ2(1/2 − ρ)L2/ ˜L2 1 , σ ˜L2 1    . The proof now proceeds similarly to the det...
[77]

large p” case for the exact Hessian, a better dependence on εg is obtained when ˜p is large and ∆H is controlled. In fact, when θ = 0 we have ∆H = 0 and (39) matches the “large p

Additionally, applying (38) to the lower bound on ∥˜p∥ we obtain ∥˜p∥ ≥6σ(1/2 − ρ) − 3∆H L2 ≥ 6σ(1 − θ)(1/2 − ρ) L2 . By combining the line search condition (33), α ≥ α⋆ 2, (32), the SPC curvature test and the lower bound on ∥˜p∥ we have f (x + α˜p) − f (x) ≤ αρ ⟨˜p, g⟩ ≤ −α⋆ ...
[78]

This modification has previously been considered in [ 70]

layers with LayerNorm [4]. This modification has previously been considered in [ 70]. We utilize the “160px” version of the Imagenette dataset [33], which is available from PyTorch [58]. The Imagenette is a 10 class, subset of the full Imagenet dataset [21]. We process the dat...

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.

[1] [1]

Mushroom

(1981). Mushroom. UCI Machine Learning Repository. Accessed under CC-BY 4.0 License. DOI: https://doi.org/10.24432/C5959T

doi:10.24432/c5959t 1981

[2] [2]

Ahn, K., Zhang, J., and Sra, S. (2022). Understanding the unstable convergence of gradient descent. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S., editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 247–257. PMLR

work page 2022

[3] [3]

and Parrilo, P

Altschuler, J. and Parrilo, P. (2024). Acceleration by stepsize hedging: Multi-step descent and the silver stepsize schedule. J. ACM

work page 2024

[4] [4]

L., Kiros, J

Ba, J. L., Kiros, J. R., and Hinton, G. E. (2016). Layer normalization

work page 2016

[5] [5]

and Dherin, B

Barrett, D. and Dherin, B. (2021). Implicit gradient regularization. In International Conference on Learning Representations

work page 2021

[6] [6]

and Borwein, J

Barzilai, J. and Borwein, J. M. (1988). Two-point step size gradient methods. IMA Journal of Numerical Analysis, 8(1):141–148

work page 1988

[7] [7]

G., Pearlmutter, B

Baydin, A. G., Pearlmutter, B. A., Radul, A. A., and Siskind, J. M. (2018). Automatic differenti- ation in machine learning: A survey. Journal of Machine Learning Research, 18(153):1–43

work page 2018

[8] [8]

S., Roberts, L., and Roosta, F

Berahas, A. S., Roberts, L., and Roosta, F. (2024). Non-uniform smoothness for gradient descent. Transactions on Machine Learning Research

work page 2024