Pith. sign in

REVIEW 1 major objections 5 minor 1 cited by

Gradient Methods with Online Scaling Part I. Theoretical Foundations

T0 review · 1 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read This paper claims that by learning its matrix stepsize online, a simple gradient method provably converges no slower than gradient descent, asymptotically matches the best fixed preconditioner, and converges superlinearly near the optimum.

desk verdict A genuinely new online-learning preconditioning framework with convincing proofs and real superlinear convergence, but the paper's claim to explain hypergradient descent's empirical success is not backed by its own analysis. read the letter →

arxiv 2505.23081 v2 pith:Z3N5ETRB submitted 2025-05-29 math.OC cs.LGstat.ML

Wenzhi Gao , Ya-Chi Chu , Yinyu Ye , Madeleine Udell This is my paper
classification math.OCcs.LGstat.ML MSC 90C2590C53
keywords onlinescaledgradientmethodsstepsizeadaptationhypergradientdescentsuperlinearconvergenceconvexoptimizationpreconditionedregretboundssmoothstrongly
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

The paper tries to establish that choosing a gradient method's stepsize — including a full matrix stepsize — can be posed as an online learning problem, and that doing so provably accelerates convergence. Its central instance, Lookahead OSGM-R, updates a matrix stepsize by online gradient descent on the observed contraction ratio of suboptimality, and is shown to converge no slower than plain gradient descent while asymptotically matching the best possible fixed preconditioner. The same framework yields a non-asymptotic superlinear rate, $f(x^{K+1}) - f^\star \le [f(x^1) - f^\star](C/K)^K$, placing OSGM beside quasi-Newton methods as only the second family of first-order methods with such a guarantee. The paper also claims that the popular hypergradient descent heuristic is an instantiation of the framework, giving that heuristic a theoretical explanation. A careful reader would care because the analysis is simple, problem-dependent, and suggests a design principle — let the stepsize learn from the landscape — rather than a hand-tuned schedule.

What carries the argument

The load-bearing object is the pair (feedback function, landscape action): OSGM — online scaled gradient methods, a family of first-order methods that adapt a matrix stepsize by online learning — measures each stepsize $P_k$ by a feedback function $\ell_{x^k}(P_k)$ and updates $P_k$ by online gradient descent. The central object within that is the ratio feedback $r_x(P)$, the contraction ratio of suboptimality produced by a preconditioned gradient step, together with the reduction inequality that bounds the $K$-step error by the $K$-th power of the average contraction ratio, an AM-GM product bound that needs no convexity. The argument is carried by a cancellation identity: under the lookahead landscape action $x^{k+1} = x^{k+1/2} - (1/L)\nabla f(x^{k+1/2})$, the descent lemma gives $r_k \le r_{x^k}(P_k) - (1/(4L^2))\|\nabla r_{x^k}(P_k)\|_F^2$, while online gradient descent's regret bound carries a matching positive term $(\eta/2)\|\nabla r_{x^k}(P_k)\|_F^2$; setting $\eta = 1/(2L^2)$ makes the two cancel, leaving only constant regret $L^2\|P_1 - \hat P\|_F^2$. For trajectory adaptivity the machinery is dynamic regret with a path-length cost; for local superlinearity it is the fact that the ratio feedback of the Hessian inverse at the optimum is $O(\|x - x^\star\|^2)$ when the Hessian is $H$-Lipschitz, so the constant-regret bound with benchmark $[\nabla^2 f(x^\star)]^{-1}$ yields $(C/K)^K$.

What would settle it

On a strongly convex quadratic with Hessian $H$ (so the Hessian-Lipschitz constant is zero), known optimum $f^\star = 0$ and $L = \|H\|_2$, run Lookahead OSGM-R (Algorithm 2) with $P_1 = (1/L)I$ and $\eta = 1/(2L^2)$ for $K = 10^4$ iterations. Theorem 6.4 predicts $f(x^{K+1}) \le f(x^1)(C/K)^K$ with $C = L^2\|(1/L)I - H^{-1}\|_F^2$; if the observed error exceeds that bound at any $K$, the theorem's constants or the cancellation at Eqs. (18)--(19) fail. A second check targets the mechanism: with $\eta$ doubled, Eq. (18) predicts the compensation term no longer cancels and the superlinear phase should disappear or be substantially delayed; if it does not, the claimed cancellation is not the operative mechanism.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is that a first-order method can be accelerated by letting the stepsize itself be learned online, and that a single extra gradient step — the 'lookahead' — absorbs the error of that learning. The stepsize $P_k$ is updated by online gradient descent against the ratio feedback $r_x(P) = (f(x - P\nabla f(x)) - f^\star)/(f(x) - f^\star)$, and the iterate is advanced from the proposal $x^{k+1/2} = x^k - P_k\nabla f(x^k)$ by one more gradient step of length $1/L$. Because the extra step shrinks the function value by an amount proportional to the squared gradient of the feedback, choosing the online learning rate $\eta = 1/(2L^2)$ cancels the gradient-norm error term that online gradient descent would otherwise leave in its regret bound; the cumulative progress of the method is then bounded by that of any fixed benchmark stepsize plus a constant, $L^2\|P_1 - \hat P\|_F^2$. Feeding this into the arithmetic-mean--geometric-mean reduction $f(x^{K+1}) - f^\star \le [f(x^1) - f^\star]((1/K)\sum_k r_k)^K$ gives the headline rate $\min\{(1 - 1/\kappa)^K,\ (1 - 1/\kappa^\star + L^2\|(1/L)I - P^\star_r\|_F^2/K)^K\}$, and, with the Hessian inverse at the optimum as benchmark, the local superlinear rate $(C/K)^K$. The same machinery, with hypergradient feedback $h_x(P) = (f(x - P\nabla f(x)) - f(x))/\|\nabla f(x)\|^2$ and a monotone lookahead action, reproduces hypergradient descent as a special case ($\eta = 1/L$), which the paper reads as an explanation of why that heuristic works.

Load-bearing premise

The load-bearing premise is that the optimal value $f^\star$ and the smoothness constant $L$ are known exactly — ratio feedback requires $f^\star$ (Section 3.1), and both the online learning rate $\eta = 1/(2L^2)$ and the $1/L$ lookahead step need $L$ — and that gradients are exact, with the stochastic and practical regime deferred to Part II (Section 8); if any of these is missing, the compensation of the online learner's error term fails and the stated acceleration is not guaranteed.

Editorial extensions

If this is right

  • On smooth strongly convex problems, Lookahead OSGM-R reaches accuracy $\varepsilon$ in at most $\min\{\kappa^\star L^2\|P_1 - P^\star_r\|_F^2 + \kappa^\star \log((f(x^1) - f^\star)/\varepsilon),\ \kappa \log((f(x^1) - f^\star)/\varepsilon)\}$ iterations, so it is never asymptotically slower than gradient descent and eventually matches the best fixed preconditioner.
  • When a preconditioner substantially improves conditioning ($\kappa^\star < \sqrt{\kappa}$), the asymptotic complexity $O(\kappa^\star \log(1/\varepsilon))$ beats the classical accelerated rate $O(\sqrt{\kappa} \log(1/\varepsilon))$; the paper reads this as implicit preconditioning, consistent with the known lower bound.
  • On problems with $H$-Lipschitz Hessian, the method converges locally at the non-asymptotic superlinear rate $(C/K)^K$, matching or surpassing the analyzed rates of quasi-Newton methods.
  • A one-line equivalence in Section 9 shows that hypergradient descent with learning rate $1/L$ is exactly Lookahead OSGM-H, so the framework provides a rigorous global convergence analysis of that popular heuristic.
  • Through dynamic regret, OSGM competes with the best stepsize sequence along the actual trajectory up to a path-length cost, so it can track a locally optimal preconditioner that switches between regions of different curvature.

Reading between the lines

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

  • The compensation mechanism at $\eta = 1/(2L^2)$ suggests a general design rule: pair any online learner in stepsize space with a lookahead safeguard whose descent cancels the learner's error term; the paper proves this only for online gradient descent, but Section 7.4's suggestion of more sophisticated online learning algorithms hints that the constant-regret structure may extend beyond OGD.
  • The superlinear bound needs exact $L$ and exact gradients; a testable extension is whether $(C/K)^K$ survives under backtracking estimation of $L$ (sketched in Section 7.4) or under stochastic gradients — the theory here covers neither, and the paper defers the practical regime to Part II.
  • The equivalence between hypergradient descent at $\eta = 1/L$ and Lookahead OSGM-H implies that practitioners running hypergradient descent with a small fixed $\eta$ are in effect using a damped lookahead; decoupling the lookahead stepsize from the online learning rate, as OSGM does, is a modification the theory suggests could restore the full effect.
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.

Referee Report

1 major / 5 minor

Summary. The paper introduces Online Scaled Gradient Methods (OSGM), a framework that treats preconditioner/stepsize selection as an online convex optimization problem over the matrix stepsize, using either ratio feedback r_x(P) or hypergradient feedback h_x(P) and a landscape action that can accept, filter, or look ahead. The main theoretical results are for Lookahead OSGM-R and Monotone Lookahead OSGM-H: global convergence rates that compete with any fixed benchmark stepsize and, in the strongly convex case, are asymptotically as good as gradient descent with the best preconditioner; potential-function complexity bounds; local adaptivity bounds via dynamic regret; and non-asymptotic superlinear convergence of the form (C/K)^K. The paper also claims that this framework explains the empirical success of hypergradient descent. The appendix contains complete proofs for the stated theorems.

Significance. If the central OSGM-R results are correct, they are a substantial contribution: a gradient-only method with global rate matching the optimal fixed preconditioner asymptotically and with non-asymptotic superlinear convergence, proved through a transparent online-learning cancellation argument. The proofs are unusually complete, and the comparisons are made against arbitrary benchmark stepsizes in for-all bounds rather than against quantities fitted to the algorithm's own trajectory. However, the paper's secondary claim that OSGM explains the empirical behavior of the original hypergradient-descent heuristic is not supported by the analyzed monotone variant, and this weakness affects one of the three headline contributions in the abstract.

major comments (1)
  1. [Section 9 and Section 6.2] The claim that OSGM "explains the empirical success of the popular hypergradient-descent heuristic" (Abstract; also Section 1.1 and Section 9) is not supported by the analyzed variant. The convergence theorems for the hypergradient instantiation, Theorems 6.6, 6.7, and 6.9, are stated for "Monotone Lookahead OSGM-H" (Algorithm 3), whose landscape action enforces f(x^{k+1}) <= min{f(x^{k+1/2} - (1/L) grad f(x^{k+1/2})), f(x^k)}. The reduction used for these results, Theorem 4.2, explicitly requires f(x^{k+1}) <= f(x^k) for every k. Section 9 shows that HDM with eta = 1/L and P = R^{n x n} reduces to the non-monotone lookahead update x^{k+1} = x^{k+1/2} - eta grad f(x^{k+1/2}), and the HDM literature contains no monotone filter. The difference is consequential: for f(x) = 0.5 x^2 on x >= 0 and f(x) = 0.25 x^2 on x < 0 (L = 1, mu = 0.5), HDM with eta = 1/L, P_1 = 20, x_1 = 1 gives P_2 = 10.5 and x_2 = -9.5, so f(x_2) = 22.56 > 0.5 = f(x_1), violating the monotonicity required by Theorem 4.2. The abstract and Section 9 should either restrict the explanatory claim to the monotone lookahead variant or supply a separate convergence analysis for the original non-monotone HDM update.
minor comments (5)
  1. [Theorems 6.5 and 6.10] The statements of Theorems 6.5 and 6.10 write the superlinear bound as f(x^{K+1}) - f(x^1) <= ..., but the quantity f(x^{K+1}) - f(x^1) is not the suboptimality; the proofs establish the bound for f(x^{K+1}) - f^*. The displayed inequality is implied by the proof, but the wording should be corrected to avoid confusion.
  2. [Section 6.1.1 and Section 7.4] The headline rates for OSGM-R in Theorem 6.1 and Theorem 6.4 require the ratio feedback, which uses the optimal value f^*, as well as exact knowledge of L to set eta = 1/(2L^2) and the lookahead step 1/L. The paper mentions this in Section 6.1.1 and Section 7.4, but the abstract and Section 1.1 present the results as unconditional; the assumptions should be stated in the theorem statements themselves.
  3. [Section 7.4] The text suggests replacing OGD with parameter-free online algorithms such as [52], but those algorithms typically require a bounded feasible set, whereas the main theorems use P = R^{n x n} with no boundedness assumption. The paper should reconcile this practical recommendation with the unbounded candidate set used in the theory.
  4. [Section 9] The sentence "HDM and Lookahead OSGM are equivalent if the stepsize of online gradient descent is set to eta = 1/L" is imprecise: the equivalence is with the vanilla (non-monotone) lookahead landscape, not with the Monotone Lookahead OSGM-H of Algorithm 3. This wording is part of the overreach identified in the major comment.
  5. [Section 8] Section 8 contains no experiments and refers to Part II; the paper is honest about this, but readers should not interpret the abstract's "empirical success" phrasing as evidence presented in this manuscript.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the OSGM rates follow from self-contained reductions, standard OGD regret lemmas, and for-all benchmark stepsizes; self-citations are contextual pointers, not load-bearing evidence.

full rationale

The derivation chain is self-contained. The key reductions (Theorems 4.1 and 4.2) are algebraic identities, and the lookahead progress improvement (Lemma 4.1) follows from the standard descent lemma. The online-gradient-descent regret bounds (Lemmas 5.1 and 5.2) are textbook inequalities and are applied to an arbitrary benchmark stepsize P_hat that is not fitted to the data or to the trajectory. The cancellation in Eqs. (18)-(19) is an explicit algebraic choice of eta = 1/(2L^2), not a fitted constant disguised as a prediction. The benchmark stepsizes used to obtain the final rates, including P*_r and the Hessian inverse [∇²f(x*)]^{-1}, appear inside for-all bounds; the bound with P*_r uses the minimax definition and Proposition 3.2, and the superlinear bound uses the Lipschitz-Hessian estimate in Lemma 6.1 together with the already-proved linear convergence of Theorem 6.1. No central claim reduces to an input by construction. The self-citations to the authors' preprints [15] and [9] are contextual (noting that the paper extends those works, pointing to additional feedback functions, and deferring practical details to Part II); they are not used as the proof of any theorem here. The claimed explanation of hypergradient descent's empirical success is a scope/applicability concern because the analyzed Monotone Lookahead OSGM-H enforces a descent filter that standard HDM lacks, but this is an overreach beyond the proven setting rather than a circular derivation. Therefore the circularity score is 0.

Assumptions & free parameters 1 free parameters · 6 assumptions · 2 invented entities

The central claims rest on standard smooth convex optimization assumptions (L-smoothness, strong convexity, and for local superlinearity an H-Lipschitz Hessian), on exact gradient evaluations, and on knowledge of L to set η. No constants are fitted to objective data; the online learning step size is the only hand-set algorithmic quantity. The framework introduces new analytical constructs (feedback functions and landscape actions), but these are defined within the paper and supported by proofs, not empirical entities.

free parameters (1)
  • Online gradient stepsize η = 1/(2L^2) for OSGM-R, 1/L for OSGM-H
    Hand-set from the smoothness constant L so the lookahead progress cancels the online learning error (Eq. 18-19). It is not fitted to objective data, but is an algorithmic hyperparameter whose value is assumed known.
assumptions (6)
  • domain assumption f is L-smooth and µ-strongly convex (used throughout Sections 3-6)
    Used to prove convexity and smoothness of the feedback functions (Proposition 3.1, Lemma 3.1) and to define the globally optimal condition number κ* (Definition 3.1). Standard assumption in convex optimization.
  • domain assumption f has H-Lipschitz Hessian (Lemma 6.1, Theorems 6.4, 6.9)
    Required only for the local superlinear convergence results; it bounds the ratio and hypergradient feedback of the Hessian inverse benchmark.
  • domain assumption Exact gradient evaluations at every iteration
    The descent lemma, feedback gradients, and the cancellation in Eqs. (18)-(19) all require deterministic gradients; stochastic gradients would break the analysis.
  • domain assumption The smoothness constant L is known to the algorithm (or a valid upper bound)
    η = 1/(2L^2) and the lookahead step 1/L depend on L (Algorithms 2-3). The paper suggests backtracking to estimate L in Section 7.4 but does not analyze the resulting rates.
  • standard math Standard online gradient descent regret bounds (Lemmas 5.1 and 5.2)
    Uses convexity of the losses and OGD's Euclidean distance bound; standard in online convex optimization.
  • standard math Descent lemma and AM-GM inequality
    Used in Theorems 4.1 and 4.2 and Lemma 4.1 to reduce cumulative progress to suboptimality.
invented entities (2)
  • Scheduler-Landscape abstraction
    purpose: Formalizes step-size selection as an online learning problem with a cooperating environment that can modify iterates through landscape actions.
    A new analytical construct defined in Section 2. Its properties are proved in Lemma 4.1, but the paper provides no external experimental validation in this Part I.
  • Ratio and hypergradient feedback functions r_x(P) and h_x(P)
    purpose: Measure the local quality of a matrix step size at a point so online gradient descent can update P.
    These are new functions defined in Section 3 with proved convexity and smoothness. They are anchored to the analysis rather than to external data, and no empirical validation is included here.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Gradient Methods with Online Scaling Part I. Theoretical Foundations." pith.science (2026). https://pith.science/paper/Z3N5ETRB

@misc{pith2026250523081,
  author       = {Pith},
  title        = {Pith review of: Gradient Methods with Online Scaling Part I. Theoretical Foundations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Z3N5ETRB}},
  note         = {Machine review of arXiv:2505.23081}
}
read the original abstract

This paper establishes the theoretical foundations of the online scaled gradient methods (OSGM), a framework that utilizes online learning to adapt stepsizes and provably accelerate first-order methods. OSGM quantifies the effectiveness of a stepsize by a feedback function motivated from a convergence measure and uses the feedback to adjust the stepsize through an online learning algorithm. Consequently, instantiations of OSGM achieve convergence rates that are asymptotically no worse than the optimal stepsize. OSGM yields desirable convergence guarantees on smooth convex problems, including 1) trajectory-dependent global convergence on smooth convex objectives; 2) an improved complexity result on smooth strongly convex problems, and 3) local superlinear convergence. Notably, OSGM constitutes a new family of first-order methods with non-asymptotic superlinear convergence, joining the celebrated quasi-Newton methods. Finally, OSGM explains the empirical success of the popular hypergradient-descent heuristic in optimization for machine learning.

Figures

Figures reproduced from arXiv: 2505.23081 by the authors.

Figure 1
Figure 1. Illustration of f(x1, x2). However, no diagonal stepsize can achieve rx(P) = 0 for all x simultaneously. Thus, the minimax optimal step￾size P ⋆ r must incur positive cumulative feedback PK k=1 rxk (P ⋆ r ) > 0, which is strictly worse than the trajectory￾based bound. Even if the trajectory {x k} does not always stay in the same region, the dynamic regret bound in (14) allows us to compare with a benchmark sequence … view at source ↗
Figure 2
Figure 2. Theoretical performance of Lookahead OSGM-R. The linear convergence rate initially matches the 1 − 1 κ rate of vanilla gradient descent and accelerates to (at least) 1 − 1 κ⋆ . Alternatively, we can obtain an explicit complexity bound through the lens of a potential function. Potential reduction. Let Pˆ be a benchmark stepsize such that rx(Pˆ) ≤ 1 − 1 κPˆ < 1 for all x. For example, it suffices to take the optimal s… view at source ↗

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Enhanced PDHG for Linear Programming with Online Preconditioning

    math.OC 2025-06 conditional novelty 6.0 of 10

    Online preconditioning for a GPU LP solver cuts iteration counts by roughly 10-30% on Netlib and MIPLIB benchmarks, with the learning rate tuned per instance.

Reference graph

Works this paper leans on

72 extracted references · 51 canonical work pages · cited by 1 Pith paper

  1. [1]

    Disentangling adaptive gradient methods from learning rates.CoRR, abs/2002.11803, 2020

    Naman Agarwal, Rohan Anil, Elad Hazan, Tomer Koren, and Cyril Zhang. Disentangling adaptive gradient methods from learning rates.CoRR, abs/2002.11803, 2020. (cited on 17)

    arXiv 2002

  2. [2]

    Parameter adaptation in stochastic optimization

    Luís B Almeida, Thibault Langlois, José D Amaral, and Alexander Plakhov. Parameter adaptation in stochastic optimization. InOn-line learning in neural networks, pages 111–134. 1999. (cited on 18)

    work page 1999

  3. [3]

    Acceleration by stepsize hedging: Silver stepsize schedule for smooth convex optimization.Mathematical Programming, pages 1–14, 2024

    Jason M Altschuler and Pablo A Parrilo. Acceleration by stepsize hedging: Silver stepsize schedule for smooth convex optimization.Mathematical Programming, pages 1–14, 2024. (cited on 17)

    work page 2024

  4. [4]

    Acceleration by stepsize hedging: Multi-step descent and the silver stepsize schedule.Journal of the ACM, 72(2):1–38, 2025

    Jason M Altschuler and Pablo A Parrilo. Acceleration by stepsize hedging: Multi-step descent and the silver stepsize schedule.Journal of the ACM, 72(2):1–38, 2025. (cited on 17)

    work page 2025

  5. [5]

    Practical large-scale linear programming using primal-dual hybrid gradient.Advances in Neural Information Processing Systems, 34:20243–20257, 2021

    David Applegate, Mateo Diaz, Oliver Hinder, Haihao Lu, Miles Lubin, Brendan O’Donoghue, and Warren Schudy. Practical large-scale linear programming using primal-dual hybrid gradient.Advances in Neural Information Processing Systems, 34:20243–20257, 2021. (cited on 17)

    work page 2021

  6. [6]

    Two-point step size gradient methods.IMA journal of numerical analysis, 8(1):141–148, 1988

    Jonathan Barzilai and Jonathan M Borwein. Two-point step size gradient methods.IMA journal of numerical analysis, 8(1):141–148, 1988. (cited on 17)

    work page 1988

  7. [7]

    Online learning rate adaptation with hypergradient descent

    Atilim Gunes Baydin, Robert Cornish, David Martinez Rubio, Mark Schmidt, and Frank Wood. Online learning rate adaptation with hypergradient descent. InInternational Conference on Learning Represen- tations, 2018. (cited on 2, 18)

    work page 2018

  8. [8]

    Gradient descent: The ultimate optimizer.Advances in Neural Information Processing Systems, 35:8214–8225, 2022

    Kartik Chandra, Audrey Xie, Jonathan Ragan-Kelley, and Erik Meijer. Gradient descent: The ultimate optimizer.Advances in Neural Information Processing Systems, 35:8214–8225, 2022. (cited on 18) 19

    work page 2022

Show all 72 references
  1. [9]

    Provable and practical online learning rate adaptation with hypergradient descent.arXiv preprint arXiv:2502.11229, 2025

    Ya-Chi Chu, Wenzhi Gao, Yinyu Ye, and Madeleine Udell. Provable and practical online learning rate adaptation with hypergradient descent.arXiv preprint arXiv:2502.11229, 2025. (cited on 1, 3, 4, 17, 18)

    2025 arXiv

  2. [10]

    Non-monotonebehavioroftheheavyballmethod

    MarinaDanilova, AnastasiiaKulakova, andBorisPolyak. Non-monotonebehavioroftheheavyballmethod. InDifference Equations and Discrete Dynamical Systems with Applications: 24th ICDEA, Dresden, Ger- many, May 21–25, 2018 24, pages 213–230. Springer, 2020. (cited on 17)

    2018

  3. [11]

    An enhanced alternating direction method of multipliers-based interior point method for linear and conic optimization.INFORMS Journal on Computing, 2024

    Qi Deng, Qing Feng, Wenzhi Gao, Dongdong Ge, Bo Jiang, Yuntian Jiang, Jingsong Liu, Tianhao Liu, Chenyu Xue, Yinyu Ye, et al. An enhanced alternating direction method of multipliers-based interior point method for linear and conic optimization.INFORMS Journal on Computing, 202...

    2024

  4. [12]

    Uniformly optimal and parameter-free first-order methods for convex and function-constrained optimization.arXiv preprint arXiv:2412.06319, 2024

    Qi Deng, Guanghui Lan, and Zhenwei Lin. Uniformly optimal and parameter-free first-order methods for convex and function-constrained optimization.arXiv preprint arXiv:2412.06319, 2024. (cited on 17)

    2024 arXiv

  5. [13]

    Adaptive subgradient methods for online learning and stochas- tic optimization.Journal of machine learning research, 12(7), 2011

    John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochas- tic optimization.Journal of machine learning research, 12(7), 2011. (cited on 3, 16, 17)

    2011

  6. [14]

    John Wiley & Sons, 2000

    Roger Fletcher.Practical methods of optimization. John Wiley & Sons, 2000. (cited on 2)

    2000

  7. [15]

    Gradient methods with online scaling.arXiv preprint arXiv:2411.01803, 2024

    Wenzhi Gao, Ya-Chi Chu, Yinyu Ye, and Madeleine Udell. Gradient methods with online scaling.arXiv preprint arXiv:2411.01803, 2024. (cited on 1, 4, 6, 13, 18)

    2024 arXiv

  8. [16]

    Scalable approximate optimal diagonal pre- conditioning.arXiv preprint arXiv:2312.15594, 2023

    Wenzhi Gao, Zhaonan Qu, Madeleine Udell, and Yinyu Ye. Scalable approximate optimal diagonal pre- conditioning.arXiv preprint arXiv:2312.15594, 2023. (cited on 6, 17)

    2023 arXiv

  9. [17]

    Clarabel: An interior-point solver for conic programs with quadratic objectives.arXiv preprint arXiv:2405.12762, 2024

    Paul J Goulart and Yuwen Chen. Clarabel: An interior-point solver for conic programs with quadratic objectives.arXiv preprint arXiv:2405.12762, 2024. (cited on 17)

    2024 arXiv

  10. [18]

    Shampoo: Preconditioned stochastic tensor optimization

    Vineet Gupta, Tomer Koren, and Yoram Singer. Shampoo: Preconditioned stochastic tensor optimization. InInternational Conference on Machine Learning, pages 1842–1850. PMLR, 2018. (cited on 17)

    2018

  11. [19]

    Introduction to online convex optimization.Foundations and Trends®in Optimization, 2(3-4):157–325, 2016

    Elad Hazan et al. Introduction to online convex optimization.Foundations and Trends®in Optimization, 2(3-4):157–325, 2016. (cited on 8)

    2016

  12. [20]

    Revisiting the polyak step size.arXiv preprint arXiv:1905.00313, 2019

    Elad Hazan and Sham Kakade. Revisiting the polyak step size.arXiv preprint arXiv:1905.00313, 2019. (cited on 17)

    1905 arXiv

  13. [21]

    Adaptive online gradient descent.Advances in neural information processing systems, 20, 2007

    Elad Hazan, Alexander Rakhlin, and Peter Bartlett. Adaptive online gradient descent.Advances in neural information processing systems, 20, 2007. (cited on 3)

    2007

  14. [22]

    Neural networks for machine learning lecture 6a overview of mini-batch gradient descent.Cited on, 14(8):2, 2012

    Geoffrey Hinton, Nitish Srivastava, and Kevin Swersky. Neural networks for machine learning lecture 6a overview of mini-batch gradient descent.Cited on, 14(8):2, 2012. (cited on 3, 17)

    2012

  15. [23]

    Restarted primal-dual hybrid conjugate gradient method for large-scale quadratic programming.arXiv preprint arXiv:2405.16160, 2024

    Yicheng Huang, Wanyu Zhang, Hongpei Li, Dongdong Ge, Huikang Liu, and Yinyu Ye. Restarted primal-dual hybrid conjugate gradient method for large-scale quadratic programming.arXiv preprint arXiv:2405.16160, 2024. (cited on 17)

    2024 arXiv

  16. [24]

    Increased rates of convergence through learning rate adaptation.Neural networks, 1(4):295–307, 1988

    Robert A Jacobs. Increased rates of convergence through learning rate adaptation.Neural networks, 1(4):295–307, 1988. (cited on 18)

    1988

  17. [25]

    Unconstrained online learning with unbounded losses

    Andrew Jacobsen and Ashok Cutkosky. Unconstrained online learning with unbounded losses. InInterna- tional Conference on Machine Learning, pages 14590–14630. PMLR, 2023. (cited on 16)

    2023

  18. [26]

    Online learning guided curvature approximation: A quasi-newton method with global non-asymptotic superlinear convergence

    Ruichen Jiang, Qiujiang Jin, and Aryan Mokhtari. Online learning guided curvature approximation: A quasi-newton method with global non-asymptotic superlinear convergence. InThe Thirty Sixth Annual Conference on Learning Theory, pages 1962–1992. PMLR, 2023. (cited on 2, 17, 18)

    1962

  19. [27]

    Online learning guided quasi-newton methods with global non- asymptotic convergence.arXiv preprint arXiv:2410.02626, 2024

    Ruichen Jiang and Aryan Mokhtari. Online learning guided quasi-newton methods with global non- asymptotic convergence.arXiv preprint arXiv:2410.02626, 2024. (cited on 2, 18) 20

    2024 arXiv

  20. [28]

    Adaptive hierarchical hyper-gradient descent.International Journal of Machine Learning and Cybernetics, 13(12):3785–3805, 2022

    Renlong Jie, Junbin Gao, Andrey Vasnev, and Minh-Ngoc Tran. Adaptive hierarchical hyper-gradient descent.International Journal of Machine Learning and Cybernetics, 13(12):3785–3805, 2022. (cited on 18)

    2022

  21. [29]

    Non-asymptotic global convergence analysis of bfgs with the armijo-wolfe line search.arXiv preprint arXiv:2404.16731, 2024

    Qiujiang Jin, Ruichen Jiang, and Aryan Mokhtari. Non-asymptotic global convergence analysis of bfgs with the armijo-wolfe line search.arXiv preprint arXiv:2404.16731, 2024. (cited on 17)

    2024 arXiv

  22. [30]

    Non-asymptotic global convergence rates of bfgs with exact line search.arXiv preprint arXiv:2404.01267, 2024

    Qiujiang Jin, Ruichen Jiang, and Aryan Mokhtari. Non-asymptotic global convergence rates of bfgs with exact line search.arXiv preprint arXiv:2404.01267, 2024. (cited on 2, 17)

    2024 arXiv

  23. [31]

    Non-asymptotic superlinear convergence of standard quasi-newton methods.Mathematical Programming, 200(1):425–473, 2023

    Qiujiang Jin and Aryan Mokhtari. Non-asymptotic superlinear convergence of standard quasi-newton methods.Mathematical Programming, 200(1):425–473, 2023. (cited on 2)

    2023

  24. [32]

    Adam: A method for stochastic optimization.arXiv preprint arXiv:1412.6980, 2014

    Diederik P Kingma. Adam: A method for stochastic optimization.arXiv preprint arXiv:1412.6980, 2014. (cited on 3)

    2014 arXiv

  25. [33]

    Searching for optimal per-coordinate step-sizes with multidimensional backtracking.Advances in Neural Information Processing Systems, 36, 2024

    Frederik Kunstner, Victor Sanches Portella, Mark Schmidt, and Nicholas Harvey. Searching for optimal per-coordinate step-sizes with multidimensional backtracking.Advances in Neural Information Processing Systems, 36, 2024. (cited on 2, 6, 18)

    2024

  26. [34]

    Optimal and parameter-free gradient minimization methods for smooth optimization.arXiv preprint arXiv:2310.12139, 2023

    Guanghui Lan, Yuyuan Ouyang, and Zhe Zhang. Optimal and parameter-free gradient minimization methods for smooth optimization.arXiv preprint arXiv:2310.12139, 2023. (cited on 3)

    2023 arXiv

  27. [35]

    A simple uniformly optimal method without line search for convex opti- mization.arXiv preprint arXiv:2310.10082, 2023

    Tianjiao Li and Guanghui Lan. A simple uniformly optimal method without line search for convex opti- mization.arXiv preprint arXiv:2310.10082, 2023. (cited on 3, 17)

    2023 arXiv

  28. [36]

    A second look at exponential and cosine step sizes: Simplicity, adaptivity, and performance

    Xiaoyu Li, Zhenxun Zhuang, and Francesco Orabona. A second look at exponential and cosine step sizes: Simplicity, adaptivity, and performance. InInternational Conference on Machine Learning, pages 6553–

  29. [37]

    An admm-based interior-point method for large-scale linear programming.Optimization Methods and Software, 36(2-3):389–424, 2021

    Tianyi Lin, Shiqian Ma, Yinyu Ye, and Shuzhong Zhang. An admm-based interior-point method for large-scale linear programming.Optimization Methods and Software, 36(2-3):389–424, 2021. (cited on 17)

    2021

  30. [38]

    Pdcs: A primal-dual large-scale conic programming solver with gpu enhancements.arXiv preprint arXiv:2505.00311, 2025

    Zhenwei Lin, Zikai Xiong, Dongdong Ge, and Yinyu Ye. Pdcs: A primal-dual large-scale conic programming solver with gpu enhancements.arXiv preprint arXiv:2505.00311, 2025. (cited on 17)

    2025

  31. [39]

    Haihao Lu and Jinwen Yang. cupdlp. jl: A gpu implementation of restarted primal-dual hybrid gradient for linear programming in julia.arXiv preprint arXiv:2311.12180, 2023. (cited on 17)

    2023 arXiv

  32. [40]

    cupdlp-c: A strengthened implementation of cupdlp for linear programming by c language.arXiv preprint arXiv:2312.14832, 2023

    Haihao Lu, Jinwen Yang, Haodong Hu, Qi Huangfu, Jinsong Liu, Tianhao Liu, Yinyu Ye, Chuwen Zhang, and Dongdong Ge. cupdlp-c: A strengthened implementation of cupdlp for linear programming by c language.arXiv preprint arXiv:2312.14832, 2023. (cited on 17)

    2023 arXiv

  33. [41]

    Tuning-freestep-size adaptation

    AshiqueRupamMahmood, RichardSSutton, ThomasDegris, andPatrickMPilarski. Tuning-freestep-size adaptation. In2012 IEEE international conference on acoustics, speech and signal processing (ICASSP), pages 2121–2124. IEEE, 2012. (cited on 18)

    2012

  34. [42]

    Adaptive gradient descent without descent

    Yura Malitsky and Konstantin Mishchenko. Adaptive gradient descent without descent. InInternational Conference on Machine Learning, pages 6702–6712. PMLR, 2020. (cited on 17)

    2020

  35. [43]

    Adaptive proximal gradient method for convex optimization

    Yura Malitsky and Konstantin Mishchenko. Adaptive proximal gradient method for convex optimization. Advances in Neural Information Processing Systems, 37:100670–100697, 2024. (cited on 17)

    2024

  36. [44]

    Adaptive bound optimization for online convex optimization

    H Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex optimization. arXiv preprint arXiv:1002.4908, 2010. (cited on 3) 21

    2010 arXiv

  37. [45]

    Renato D. C. Monteiro, Jerome W. O’Neal, and Arkadi Nemirovski. A new conjugate gradient algorithm in- corporating adaptive ellipsoid preconditioning. Technical Report Optimization Online e-print 2004-10-973, School of Industrial and Systems Engineering, Georgia Institute of T...

    2004

  38. [46]

    Linear convergence of first order methods for non-strongly convex optimization.Mathematical Programming, 175:69–107, 2019

    Ion Necoara, Yu Nesterov, and Francois Glineur. Linear convergence of first order methods for non-strongly convex optimization.Mathematical Programming, 175:69–107, 2019. (cited on 2)

    2019

  39. [47]

    A method for solving the convex programming problem with convergence rate o (1/k2)

    Yurii Nesterov. A method for solving the convex programming problem with convergence rate o (1/k2). In Dokl akad nauk Sssr, volume 269, page 543, 1983. (cited on 2, 17)

    1983

  40. [48]

    Springer Science & Business Media, 2013

    Yurii Nesterov.Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013. (cited on 2, 19)

    2013

  41. [49]

    Springer, 1999

    Jorge Nocedal and Stephen J Wright.Numerical optimization. Springer, 1999. (cited on 2)

    1999

  42. [50]

    Conic optimization via operator splitting and homogeneous self-dual embedding.Journal of Optimization Theory and Applications, 169:1042–1068,

    Brendan O’donoghue, Eric Chu, Neal Parikh, and Stephen Boyd. Conic optimization via operator splitting and homogeneous self-dual embedding.Journal of Optimization Theory and Applications, 169:1042–1068,

  43. [51]

    A modern introduction to online learning.arXiv preprint arXiv:1912.13213, 2019

    Francesco Orabona. A modern introduction to online learning.arXiv preprint arXiv:1912.13213, 2019. (cited on 2, 3, 8, 17, 18)

    1912 arXiv

  44. [52]

    Coin betting and parameter-free online learning.Advances in Neural Information Processing Systems, 29, 2016

    Francesco Orabona and Dávid Pál. Coin betting and parameter-free online learning.Advances in Neural Information Processing Systems, 29, 2016. (cited on 3, 16)

    2016

  45. [53]

    MADA: Meta-adaptive optimizers through hyper-gradient descent

    Kaan Ozkara, Can Karakus, Parameswaran Raman, Mingyi Hong, Shoham Sabach, Branislav Kveton, and Volkan Cevher. MADA: Meta-adaptive optimizers through hyper-gradient descent. InForty-first International Conference on Machine Learning, 2024. (cited on 18)

    2024

  46. [54]

    Introduction to optimization

    Boris T Polyak. Introduction to optimization. 1987. (cited on 17)

    1987

  47. [55]

    Optimal diagonal precondi- tioning.Operations Research, 2024

    Zhaonan Qu, Wenzhi Gao, Oliver Hinder, Yinyu Ye, and Zhengyuan Zhou. Optimal diagonal precondi- tioning.Operations Research, 2024. (cited on 6, 17)

    2024

  48. [56]

    Lecture notes on online learning draft, 2009

    Alexander Rakhlin, J Abernethy, A Agarwal, P Bartlett, E Hazan, and A Tewari. Lecture notes on online learning draft, 2009. (cited on 18)

    2009

  49. [57]

    On the convergence of adam and beyond.arXiv preprint arXiv:1904.09237, 2019

    Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond.arXiv preprint arXiv:1904.09237, 2019. (cited on 17)

    1904 arXiv

  50. [58]

    Greedy quasi-newton methods with explicit superlinear conver- gence.SIAM Journal on Optimization, 31(1):785–811, 2021

    Anton Rodomanov and Yurii Nesterov. Greedy quasi-newton methods with explicit superlinear conver- gence.SIAM Journal on Optimization, 31(1):785–811, 2021. (cited on 2, 17)

    2021

  51. [59]

    New results on superlinear convergence of classical quasi-newton methods.Journal of optimization theory and applications, 188:744–769, 2021

    Anton Rodomanov and Yurii Nesterov. New results on superlinear convergence of classical quasi-newton methods.Journal of optimization theory and applications, 188:744–769, 2021. (cited on 2, 17)

    2021

  52. [60]

    Ratesofsuperlinearconvergenceforclassicalquasi-newtonmethods

    AntonRodomanovandYuriiNesterov. Ratesofsuperlinearconvergenceforclassicalquasi-newtonmethods. Mathematical Programming, pages 1–32, 2022. (cited on 2, 17)

    2022

  53. [61]

    Convergence analysis of an adaptive method of gradient descent.University of Oxford, Oxford, M

    David Martinez Rubio. Convergence analysis of an adaptive method of gradient descent.University of Oxford, Oxford, M. Sc. thesis, 2017. (cited on 18)

    2017

  54. [62]

    Local gain adaptation in stochastic gradient descent

    Nicol N Schraudolph. Local gain adaptation in stochastic gradient descent. 1999. (cited on 2, 18)

    1999

  55. [63]

    Adapting bias by gradient descent: An incremental version of delta-bar-delta

    Richard S Sutton. Adapting bias by gradient descent: An incremental version of delta-bar-delta. InAAAI, volume 92, pages 171–176. Citeseer, 1992. (cited on 18) 22

    1992

  56. [64]

    No-regret dynamics in the fenchel game: A unified framework for algorithmic convex optimization.Mathematical Programming, 205(1):203–268, 2024

    Jun-Kun Wang, Jacob Abernethy, and Kfir Y Levy. No-regret dynamics in the fenchel game: A unified framework for algorithmic convex optimization.Mathematical Programming, 205(1):203–268, 2024. (cited on 18)

    2024

  57. [65]

    On the convergence of stochastic gradient descent with bandwidth-based step size.Journal of Machine Learning Research, 24(48):1–49, 2023

    Xiaoyu Wang and Ya-xiang Yuan. On the convergence of stochastic gradient descent with bandwidth-based step size.Journal of Machine Learning Research, 24(48):1–49, 2023. (cited on 17)

    2023

  58. [66]

    The role of level-set geometry on the performance of pdhg for conic linear optimization.arXiv preprint arXiv:2406.01942, 2024

    Zikai Xiong and Robert M Freund. The role of level-set geometry on the performance of pdhg for conic linear optimization.arXiv preprint arXiv:2406.01942, 2024. (cited on 17)

    2024 arXiv

  59. [67]

    Adaptive powerball stochastic conjugate gradient for large-scale learning.IEEE Transactions on Big Data, 9(6):1598–1606, 2023

    Zhuang Yang. Adaptive powerball stochastic conjugate gradient for large-scale learning.IEEE Transactions on Big Data, 9(6):1598–1606, 2023. (cited on 18)

    2023

  60. [68]

    Adam-mini: Use fewer learning rates to gain more.arXiv preprint arXiv:2406.16793, 2024

    Yushun Zhang, Congliang Chen, Ziniu Li, Tian Ding, Chenwei Wu, Yinyu Ye, Zhi-Quan Luo, and Ruoyu Sun. Adam-mini: Use fewer learning rates to gain more.arXiv preprint arXiv:2406.16793, 2024. (cited on 17)

    2024 arXiv

  61. [69]

    Algorithm 778: L-bfgs-b: Fortran sub- routines for large-scale bound-constrained optimization.ACM Transactions on mathematical software (TOMS), 23(4):550–560, 1997

    Ciyou Zhu, Richard H Byrd, Peihuang Lu, and Jorge Nocedal. Algorithm 778: L-bfgs-b: Fortran sub- routines for large-scale bound-constrained optimization.ACM Transactions on mathematical software (TOMS), 23(4):550–560, 1997

    1997

  62. [70]

    Adabelief optimizer: Adapting stepsizes by the belief in observed gradients.Advances in neural information processing systems, 33:18795–18806, 2020

    Juntang Zhuang, Tommy Tang, Yifan Ding, Sekhar C Tatikonda, Nicha Dvornek, Xenophon Papademetris, and James Duncan. Adabelief optimizer: Adapting stepsizes by the belief in observed gradients.Advances in neural information processing systems, 33:18795–18806, 2020. (cited on 17)

    2020

  63. [71]

    Surrogate losses for online learning of stepsizes in stochastic non-convex optimization

    Zhenxun Zhuang, Ashok Cutkosky, and Francesco Orabona. Surrogate losses for online learning of stepsizes in stochastic non-convex optimization. InInternational Conference on Machine Learning, pages 7664–7672. PMLR, 2019. (cited on 3) 23 Appendix Table of Contents A Proof of re...

    2019

  64. [6564]

    (cited on 17)

    PMLR, 2021. (cited on 17)

    2021

Pith tools

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