Provable and Practical Online Learning Rate Adaptation with Hypergradient Descent
Authors: Ya-Chi Chu
Wenzhi Gao
Yinyu Ye
Madeleine Udell
Venue: ICML 2025 poster (2025)
Keywords: First-order method
online convex optimization
stepsize scheduling
Primary area: optimization->convex
TL;DR: The first rigorous theoretical study of hypergradient descent

Abstract: This paper investigates the convergence properties of the hypergradient descent method ($\texttt{HDM}$), a 25-year-old heuristic originally proposed for adaptive stepsize selection in stochastic first-order methods. We provide the first rigorous convergence analysis of $\texttt{HDM}$ using the online learning framework and apply this analysis to develop a new state-of-the-art adaptive gradient methods with empirical and theoretical support. Notably, $\texttt{HDM}$ automatically identifies the optimal stepsize for the local optimization landscape and achieves local superlinear convergence. Our analysis explains the instability of $\texttt{HDM}$ reported in the literature and proposes efficient strategies to address it. We also develop two $\texttt{HDM}$ variants with heavy-ball and Nesterov momentum. Experiments on deterministic convex problems show  $\texttt{HDM}$ with heavy-ball momentum ($\texttt{HDM-HB}$) exhibits robust performance and significantly outperforms other adaptive first-order methods. Moreover, $\texttt{HDM-HB}$ often matches the performance of $\texttt{L-BFGS}$, an efficient and practical quasi-Newton method, using less memory and cheaper iterations.

Provable and Practical Online Learning Rate Adaptation with Hypergradient Descent
Ya-Chi Chu 1
Wenzhi Gao
Yinyu Ye 234 Madeleine Udell 24
Abstract
where f: - R is convex and L-smooth with f(**) == min, f(x) > -00. Theoretically, gradient descent
This paper investigates the convergence proper- ties of the hypergradient descent method (HDM), 25 25-year-old heuristic originally proposed for adaptive stepsize selection in stochastic first- order methods (Almeida et al., 1999; Baydin et al., 2018). We provide the first rigorous con- vergence analysis of HDM using the online learn- ing framework of Gao et al. (2024) and apply this analysis develop a new suute-of-the-ar adap- tive gradient methods with empirical and the- oretical support. Notably, HDM automatically identifies the optimal stepsize for the local op- timization landscape and achieves local superlin- ear convergence. Our analysis explains the insta- bility of HDM reported the literature and pro- poses efficient strategies to address it. We also develop two HDM variants with heavy-ball and Nesterov momentum. Experiments istic convex problems show HDM with heavy-ball momentum (HDM-HB) exhibits robust perfor- mance and significantly outperforms other adap- tive first-order methods. Morcover, HDM-HB of- ten matches the performance of L-BFGS, an ef- ficient and practical quasi-Newter method, using less memory and cheaper iterations.
x. k+1 x² O ()x²))
with constant stepsize an = 1/L guaranteed to converge. However, the choice of stepsize ag strongly affects the per- formance of gradient descent in practice (Defazio et al., 2024; Agarwal et al., 2020). Various stepsize selection strategies have been proposed to improve the convergence of gradient descent. Examples include line-search (Armijo, 1966), Polyak stepsize (Polyak, 1987), stepsize schedul- ing (Li et al., 2021; Wang and Yuan, 2023), hypergradient descent (Almeida et al.. 1999; Rubio, 2017: Baydin al., 2018) and the well-known adaptive stepsizes (Orabona and Pál, 2016; Duchi al., 2011; Kingma, 2014; Malitsky and Mishchenko, 2020; 2024).
This paper focuses on the hypergradient descent method (HDM), which was initially proposed by Almeida et al. (1999) as heuristic for stochastic optimization. was later tested by Baydin et al. (2018) on modern machine learning problems and exhibited promising performance. In HDM, the stepsize ax is adjusted by another gradient de- scent update:
determin-
01+1 = 0t
7N da
d
[ aV (1l))))
V/ ( V |((*)|
ag
where the hypergradient stepsize ñi is often set to Íis [[= for 7} 0 to make the update invariant of the scaling of f. Recently, Gao et al. (2024) generalized HDM to update matrix stepsize (preconditioner) Pa. R in preconditioned gradient descent through the iteration gk+l = I
1. Introduction
We consider smooth convex optimization problem
(x
minimize f(x), #ER
Pa+1 Ps 7KK
(2)
"Equal contribution 'Department Mathematics, Stanford University 'ICME, Stanford University "Shanghai Jiao Tong University and Shanghai Institute for Mathematics and Inter- disciplinary Sciences 'Management Science and Engineering, Stanford University. Correspondence to: Ya-Chi Chu <ye- chu97 edus, Wenzhi Gao <gwz@ stanford.edus.
where (2) follows from
- V V PVS(-PV(("
VS -
We call the update (1)-(2 vanilla HDM throughout the pa- per. In practice, matrix stepsize Ps is often set to be diago- nal and the update (2) simplifies to
Proceedings of the 1nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
(/a f(2)
P Ps 7k
[[

---

Provable and Practical Hypergradient Descent
10
10
However, we do not require P to be subset of positive (semi)definite cone and P is often taken to be simple sub- set such as a ball or box.
Functon gap
Vanilla HDM
Vanilla HDM
HDM + Null step
HDM-Best (Ours)
10
10
Divergance
Convergance
Algorithm Hypergradient Descent Method (HDM) input initial point x' P. E P (not necessarily PSD) for k = 1, 1,2.... do x x++1 =
10
98
10%
90
0
200
400
600
200
400
600
Iteration
Ituration
(a) Two-phase behavior
(b) Addressing instability
arg min =E(2* x P. {(x)))
far
Figure 1: The convergence behavior of different HDM vari- ants on a toy quadratic optimization problem. Figure la: two-phase convergence behavior of vanilla HDM. Figure lb; effect of null step and our best variant HDM-Best.
Pa+1 = pp T/ Wh (Ps)
end
Vanilla HDM + null steps (Algorithm 1) was first consid- ered by Gao al. (2024) and guaranteed converge glob- ally. However, their analysis is not sufficient to explain the practical behavior of HDM and provides no advice for how to design a practically efficient HDM. In this paper, we dive deeper into the convergence behavior of HDM (Al- gorithm 1), establishing sharper global convergence guar- antees and conducting a local convergence analysis. Our findings offer new insights into (vanilla) HDM and serve as foundation to design more efficient and practical variants of HDM. The contributions of this paper include:
where is the entry-wise product and diag(d) is the diag- onal matrix with d E R on the diagonal.
While vanilla HDM has been used heuristically in vari- ous applications (Chandra et al., 2022: Wang et al., 2023; Ozkara et al., 2024; Baydin et al., 2018), it can be unsta- ble if the hypergradient stepsize nn is not carefully tuned (Kunstner et al., 2024; Chandra et al., 2022; Rubio, 2017). Figure la shows f(x*) can spike as high 1000 in the early iterations of vanilla HDM, which would lead users to abandon the algorithm. Surprisingly, our analysis re- veals that this behavior of HDM is not true divergence; in- stead, it can be understood as the warm-up phase of an online learning procedure, and is followed by fast conver- gence (Figure la). Moreover, we show in both theory and practice that the explosion of f(**) can be circumvented by taking a null step, which skips the update whenever the new iterate fails to decrease the objective value, i.e., f(a* - PVV 2 f(**). The null steps flatten the ob- jective value curve in the warm-up phase of HDM but cannot shorten the warm-up (Figure lb).
We provide the first rigorous convergence analysis for HDM, including both global and local convergence guar- antees (Section 3) that show HDM can adapt to the lo- cal optimization landscape. Our analysis provides sev- eral new insights into how HDM adapts to optimization landscapes (Section 3.1), why vanilla HDM unstable in practice (Section 3.2), and the connection between HDM and quasi-Newton methods (Section 3.3).
We develop and analyze two improved variants of HDM: HDM + heavy-ball momentum (HDM-HB in Section 4. 1), which has the same convergence rate as HDM but is faster than HDM in practice; and HDM + Nesterov momentum (HDM-AGD in Section 4.2), which is faster in theory and intermediate between HDM and HDM-HB in practice.
Our analysis exploits the online learning framework by Gao et al. (2024), in which the authors observe that the P-
update (2) in vanilla HDM can be viewed as online gradient descent with respect to the online surrogate loss
We develop a practically efficient variant HDM-Best (Figure lb), which updates ,² by preconditioned gra- dient descent with heavy-ball momentum and jointly up- dates Ps and momentum parameter by AdaGrad. Our HDM-Best outperforms most adaptive first-order meth- ods and performs on par with L-BFGS (with memory size 5 or 10) using less memory (memory size 1) (Sec- tion 5).
h (P) == f(x- PV /(1)))/
(3)
(f))
The function h (P),, called hypergradient feedback in this paper, is function of preconditioner P and is well-defined for all non -oatsoationary x. To see that (2) aligns with the online gradient descent update, notice Wh.((P)) =
++ f(((=)T so the update (2) sets [
Pa+1= - The (Pt).
1.1. Related Literature
To ensure boundedness of Pe. P-update in Gao et al. (2024) and in this paper is projected onto a bounded closed convex candidate set? P:
Adaptive First-order Methods. Notable adaptive first- order methods include AdaGrad (Duchi et al., 2011; McMahan and Streeter, 2010), Adam (Kingma, 2014; Zhang et al., 2024), parameter-free stepsizes (Orabona and
Pk+1 M (Pt- 1h Vhat (Pt)]
2

---

Provable and Practical Hypergradient Descent
Pál, 2016; Defazio al., 2024), and online learning guided stepsizes (Zhuang et al., 2019). Most of these techniques originate in the online learning community, and they typi- cally achieve both strong empirical convergence and online learning regret guarantees.
the hypergradient feedback (3) simplifies to
h₂(a) == ((=-aV((m) [(m]
if = S:
h (d) := ((=-dVV(())-
if i
Hypergradient Descent. Hypergradient descent dates back to Almeida et al. (1999), which was first proposed as heuristic to accelerate stochastic gradient descent. Simi- lar concepts were also explored in Sutton (1992); Schrau- dolph (1999); Jacobs (1988); Mahmood et al. (2012), while those works employed slightly different algorithmic up- dates. Later, Baydin et al. (2018) rediscovered the HDM and named it "hypergradient descent"; Baydin et al. (2018) also extended HDM to other first-order methods with exten- sive experimental validation of its practical efficacy. Re- cent studies (Jie et al., 2022; Chandra et al., 2022; Ozkara et al., 2024) further empirically enhanced HDM for broader applicability, reporting promising numerical results.
2. Background: HDM and Online Learning
This section establishes the connection between HDM and online learning through the framework in Gao al. (2024). We refer to the following assumptions in the paper.
A1: f(z) is L-smooth and convex.
A2: f(z) is p-strongly convex with μ >>>> 0.
A3: Closed convex set P satisfies 0 E P, L and diam(P) == minnqer P Q11 DD <000
2.1. Descent Lemma and Hypergradient Feedback
Despite these empirical successes, a rigorous theoretical understanding of HDM has emerged only recently. Rubio (2017) showed that HDM converges on convex quadratic functions and established several analytic properties. Sub- sequently, Kunstner al. (2024) demonstrated that when using a diagonal preconditioner, hypergradient can be em- ployed to generate cutting planes in the preconditioner space, achieving an O(yik" log(1/z)) complexity on smooth strongly convex functions. Here, x* is the condi- tion number associated with the optimal diagonal precon- ditioner. The idea to update the preconditioner using the ellipsoid method also appeared in Monteiro et al. (2004) for solving linear systems, albeit with a very different mo- tivation. More recently, Gao et al. (2024) showed that HDM can be viewed as online gradient descent applied to some surrogate loss function and that HDM has strong trajectory- based convergence guarantees.
Hypergradient feedback (3) is motivated by descent lemma:
f(x - fff()) - f(x) < - [((x))
The descent lemma states that, under the constant step- size P& = J,1, the function value progress of gradi- ent step is at least proportional to [[V with ratio - 1/LL).. When an (effective) preconditioner Ps is used, the effective smoothness constant decreases, and thus the ratio h2 (P) = [x--PV PV((=))-((a is expected to become smaller than - -1/(2L), yielding faster convergence. Hence, the ratio h. (P) is suitable feedback to measure the qual- ity of a preconditioner. HDM uses this feedback to learn a good preconditioner with online gradient descent. The hy- pergradient feedback h2 (P) has the following properties.
[())
Lemma 2.1 (Extension of Proposition 6.1 in Gao et al. (2024)). For any & X'.
1.2. Notations
Under A1, hx(P) is convex and L-smooth and he h S 2T. Moreover, if A2 holds and P C S. then h (a) j-stroogly convex.
We denote Euclidean norm by || and Euclidean in- ner product by (. The upper and lower case letters A, a respectively denote matrices and scalars. Denote the V Eis ofy- Define F++ ma. We use [I]]:] to denote the orthogonal pro- jection onto a closed convex set C and use dist(x, C) := || - [[c[=]] to denote the distance between a point x and a closed convex set C. Denote the optimal set of f by X [x fxx = f(=*)); and the ausleeee set of ʃ by C. = f2: (2: f(z) S a). The condition number of an L- smooth and ju-strongly convex function is и. := L/p. For consistency of notation, stepsize P in this paper always refers to matrix applied in the gradient update. Define the set of scalar stepsizes S == {P = al : a E IR} and diag- onal stepsizes D == {P- = diag(d) : E IR" }. for which
Under A1 and A3, h hz,(P) is (LD + 1)-Lischhitz More- over, if A2 holds and S. D, then h2 (z(d) is (T+LD] exponential concave (Hazan et al., 2007).
Frobenius norm by ||A||e
2.2. Online Learning Guarantees
Using convexity and Lipschitz continuity of hg analy- sis in online learning (Orabona, 2019; Hazan et al., 2016) guarantees sublinear regret for online gradient descent.
Lemma 2.2 (Sublinear regret (Gao et al., 2024)). Under AI and A3, online gradient descent
Pk41 = (Pr - ME Whgt (Pt)
(4)
3

---

Provable and Practical Hypergradient Descent
with stepsize okk erates {Pk} such that
D 2(LD+1yRR or Ihe
2(LD+IJVE gen-
vergence. Given the objective 7 (x())))), HDM applies on- line gradient descent generate sequence of precondi- tioners }Prs that guarantee the following lower bound:
Ek=n 112 (Pt) - min PEP Ek=1 l1g0 (P)
Tke 7k({Px)) 2 max
PEP K Σ k-1 -lag (P) + o(1),
(7)
PK -D( (5)
which follows from the sublinear regret pk = (K) in Lemma 2.2 and Lemma 2.3, implying PK = o(1)
If strong convexity A2 is further assumed and Pk- E S,
a different choice of hypergradient stepsize Th in (4) im- proves the regret to log K.
3. The Convergence Behavior of HDM
Lemma 2.3 (Logarithmic regret). Instate A1 A3 and suppose p - S. Then online gradient descent (4) with Th = 1/((k)) generates {Pk} such that Σ h (Pk)
This section presents our main convergence results on HDM and consequent insights. All the analyses are based on the online learning framework established in Section 2.
minpep Ekm h (P) (LD+1)² log K.
3.1. HDM Adapts to the Local Landscape
Given apponential-concavii of h2 in Lemma 2.1, it is pos- sible to apply online learning algorithms such as the online Newton method (Hazan et al., 2007). Remark 1.
Our first convergence result follows by combining Lemma 2.4 and Lemma 2.2:
Theorem 3.1 (Static adaptivity). Instate (((**) in (6). Un- der A1 and (A1 A2) respectively, Algorithm with D Th 2(LD+1)VR ?] 2(LD+1)VR satisfies
The diameter D of candidate stepsize set P is measured in Frobenius norm (A3) and can incur dimen- sion dependence in the regret bound when Pa are diago- nal or full matrices. This introduces a trade-off between online regret and the best possible cumulative feedback minpep Ek=1 ha** (P): full matrices may achieve smaller feedback but have larger dimension factor in the regret bound. Diagonal stepsize often strikes good balance in practice.
Klik T p(x))}; p(ak+1) S mint A²
(A1)
(lak+t)) & (p(x))(( 2ulix - 4 ) (AI + A2)
I+)
where A is the same as defined in Lemma 2.4, PK is de- fined in (5), and 1Kk == min PEP K >x=1 h2 (P). In particular, the relations hold for all K 2 when 7) =
1
2.3. Hypergradient Reduction and HDM
2(LD+1JVK
One major contribution of Gao et al. (2024) is reduction that relates the minimization of cumulative hypergradient feedback D ha (Px) to the function value gap:
Theorem 3.1 has two implications: 1) Since *
K K Ek= hat (+,1) 2 2I, (by descent lemma) and &g o(1), both upper bounds in Theorem 3.1 converge to 0 when K goes to infinity, guaranteeing global convergence of HDM. 2) More importantly, 7 reflects the possibly im- proved convergence rate of HDM through the adaptive P- update, which depends on the local optimization landscape. To see this, when K is large and 2K K negligible, the con- vergence of HDM is competitive with preconditioned gradi- ent descent (1) with any static preconditioner. In particular, the optimal Pk == arg min pEp K ΣK= hy+ achieves A2 Note that 7 (or Pk) depends only on the
p(**) = f(xx) f(x)).
(6)
We provide a sharper version of this reduction. Lemma 2.4 (Sharper version of Lemma 6.1 in Gao et al. (2024)). Denote the negative average feedback feedbac by
(k(((p))==>> - (Pk).
Under A1, the iterates generated by Algorithm/ I satisfy
the rate K past trajectory [=*) and thus if the algorithm visits a local region with a smaller smoothness constant than the global constant I., one can expect 1 >> 2L HDM adapts to the local optimization landscape and leads to faster convergence than standard gradient descent.
p((k+1) S min| Khwwllat ((x')).
A²
1 In summary,
where A maxxeL minl ||0 x*Il. Further,
under A1 and A2,
x
S (1-)))1122pp))) ((PAH)))
We borrow standard dynamic regret argument in online convex optimization literature (Hazan et al., 2016) to pro- vide an even stronger notion of adaptivity of HDM:
According to Lemma 2.4, the negative average feedback 7k ((Px)) determines the rate for sublinear/linaa conver- gence of Algorithm 1: larger 7x ([ (P&)) implies faster con-
Theorem 3.2 (Dynamic adaptivity). Instate (6). Under A1 and (A1 + A2) respectively, Algorithm with stepsize Tj. =

---

Provable and Practical Hypergradient Descent
satisfies
RLD+IIVR
p((kkt)) & min
A² k
:f(x1)};
(A1)
10
p(ak(t)) S (((=")(1
2
I+)*
(A1+A2)
Vanilla HDM
Null step
Null step AdaGrad
where A is the same as defined in Lemma 2.4, pk is defined in (5),
10
100
200
300
400
Figure 2: Addressing instability of HDM
5k- = min (PEE)
(
&
K k== high (P%)
2(LD+ (PL
(8)
time to learn good preconditioner, and the regret accu- mulated during this warm-up phase causes HDM to behave as if it is diverging until the progress Σ 1, (P&) out- paces the regret pk- Since pk grows sublinearly with the iteration count K, HDM will eventually converge. However, the objective value will usually explode and possibly be terminated by the user before convergence begins. Conse- quently, the two-phase convergence behavior (Figure 1a) is rarely observed.
VK
and
Pk+1 PAlle-
Theorem 3.1 and Theorem 3.2 differ in the constants 7i and k the minimum in (8) searches over different opti- mal preconditioners for different hgt. Theorem 3.2 shows that, even if the sequence {a*} traverses different regions of the landscape, HDM automatically chooses P& to adapt to the local region, at the price of an additional regret term PL(())). Note that the upper bounds Theorem 3.2 holds for any benchmark path {Pk} C P. In particular, HDM is guaranteed to asymptotically achieve the perfor- mance of the optimal path that maximizes the algorithm progress. Adaptivity of HDM undergirds its good empirical performance.
Addressing Instability. While our analysis guarantees HDM will converge eventually, an algorithm that diverges up to 1000 before converging is not practical. We propose two simple but effective fixes based on our analysis:
Null step. The xrupdate is skipped if new iterate in- creases objective value (see the first line of Algorithm I), The null step ensures a monotonic decrease as HDM learns good preconditioner, although requires an ad- ditional function value oracle call at each iteration. Even on iterations when x² is not updated, the preconditioner Pe is updated using online gradient descent, so the algo- rithm is still making progress. In Figure 2, the null steps flatten the objective value curve in the divergence phase.
Behavior of HDM and Static/Dynamic Adaptivity. We observe that the behavior of HDM can be divided into two stages: (1) when the iterates x² are far from the optimum x², the change in landscape is more drastic and we expect dynamic adaptivity to capture the convergence behavior; (2) when x* is near the optimum x², f(x locally behaves like quadratic and P& remains more stable, and thus static adaptivity describes the convergence behavior.
Advanced Learning Algorithms. Better online learn- ing algorithms with lower regret shorten the divergence phase. Figure shows significant speedup when the online gradient descent in Algorithm is replaced by AdaGrad. In our experiments, AdaGrad often im- proves the robustness of HDM since it does not require pre-specifying algorithm parameters that depend on the total iteration count K and provides convergence guar- antees for the earlier iterates {a**) JaSK (Appendix B.6).
3.2. Online Regret and Instability
Though adaptive P-update underpins the strong perfor- mance of HDM, vanilla HDM is observed unstable in practice. This section identifies the source of instabilty in vanilla HDM (Figure 1) based on our analysis. We also propose two simple yet effective strategies to address the instability.
Divergence Behavior due to Regret. Recall from The- orem 3.1 that the optimality gap at ++ is bounded by
3.3. Local Superlinear Convergence
A² -+ This rate can be better than that of gradient descent when K is large and 1kk > 21 but the anal- ysis provides no guarantee on earlier iterates (**) J In particular, the convergence rate makes sense only if Tk > Pg That is, the progress Σk= h++ (Px) accu- mulated by the online gradient descent outweighs its re- gret PK- In other words, online gradient descent takes
Figure 1 shows HDM converges faster than the (linearly con- vergent) first-order methods. In fact, HDM exhibits local su- perlinear convergence strongly convex objectives (The- orem 3.3 below). This subsection assume a strongly convex objective (A2) and Lipschitz Hessian (A4):
K
A4: f(x) has H H-Lipschitz Hessian.
5

---

Provable and Practical Hypergradient Descent
Strongly Convex Quadratics. We develop intuition by considering strongly convex quadratic. For f(x) 4 (x, Ar) - x)) we have x² =I -er--IV [ f(x). In other words. P = IV f(=))] is a universal mini- mizer of (P) that drives any non-optimal point x & X to the optimum x² in one step. When [V>((="]] E P. Theorem 3.1 guarantees the performance of HDM is com- Therefore, we expect the descent curve to decrease more and more sharply, giving superlin- ear convergence (Figure la).
HDM Learns the Hessian at the Optimum. In fact, {Pt} in HDM will converge to [V [==)(==) under assumption similar to one studied in the quasi-Newton literature (Conn et al., 1991; Nocedal and Wright, 1999). Lemma 3.1 quan- tifies the effect of learning the preconditioner through the distance || - -V [==)((
Lemma 3.1. Under the same assumptions as Theorem 3.3, Algorithm generates } such that
petitive to [V²](="]
PR++ [V' PPx [V [| -
Local Superlinear Convergence. For general functions satisfying A4, fx) behaves like a quadratic near x":
ا || (P& (V2
[V((=*] ||
Vi(a*)
+ (2n - Lnd") Hir 1| x x01
(10)
f(x) ~ f(x²)x + (x - x", f(x"))(z -a)xx=x))) x²)).
Therefore, local superlinear convergence is expected for HDM near x², Theorem 3.3 formalizes this intuition.
Relation (10) consists of three terms: the distance || [ f(=))] ; a decrement in the distance; and an er- ror term that converges to zero as x² + x². The decrement is determined by the magnitude of [| [V*( V/(=") || which measures the difference between the operators Pj and [V²](=")] in the (unit) gradient direction v/(=*) To ensure fast convergence, it suffices for Ps ((x)(** and [V²](x')
Theorem 3.3 (Local superlinear convergence). Instate <p(xh) in (6). Suppose [V² [(xx()()==> E P and assume A1 to A4. Then Algorithm with t7-- 2(LD+1)VE has local
D
superlinear convergence:
p(a S sp((') 122 EK || x²11²= + 2Lox K (9) Ap2k
)x
to re-
Vi(a*) } spans the
main sufficiently close. If the set tire space over the iterations, Ps. and [V f==))=]] should align in all directions, leading to convergence of (Pk)-
where PK is the regret bound defined in (5).
Theorem 3.3 justifies our observation of superlinear con- vergence in Figure la: for strongly convex quadrat- ics, the Hessian Lipschitz constant is zero (H 0) and (9) guarantees the superlinear convergence at rate O((*K) O(( )(()))))) For general strongly convex objectives, global linear convergence (Theorem 3.1) im- plies limg K ΣK ||** =x112 = 0 when T)k- (1/VV)). So eventually the first term in (9) vanishes, giving superlinear convergence. This superlinear conver- gence behavior demonstrates that HDM can perform sig- nificantly better than standard adaptive first-order methods and line search. HDM represents a new family of first-order methods that achieves superlinear convergence on strongly convex objectives, following the celebrated quasi-Newton (QN) family (Nocedal and Wright, 1999; Fletcher, 2000). Table summarizes the superlinear convergence rates of HDM and other QN methods.
Theorem 3.4 (Convergence of the preconditioner). Instate the same assumptions as in Lemma 3.1 and let T = r E (0, 214r in online gradient descent (4). Suppose the gradient directions V((a") } are uniformly indepen- [VV(=
dent 1 Then lima- |P& [V² = O.
The convergence of stepsize in HDM was observed exper- imentally by Baydin et al. (2018) for a scalar stepsize. (P S S). Our result theoretically justifies this observation.
HDM and Quasi-Newton Methods. Our results identify a similarity between HDM and quasi-Newton methods. Both learn the inverse Hessian operator g + [V²[(=*)] as the algorithm progresses, but through different properties of the operator. The quasi-Newton methods use the se- cant equation x - y = (V((() - vf(v)) for x. y close to x² and enforce this equation, replacing the inverse Hessian by Ps. to guide learning (Jiang et al., 2023). In contrast, HDM learns an optimal preconditioner for the function. Since the function is locally quadratic, this optimal preconditioner is the inverse Hessian. HDM uses the hypergradient feedback h2 (P) to directly measure
Table 1: Recent Superlinear convergence rates
Algorithm
Rate
Greedy QN (Rodomanov and Nesterov, 2021)
O(e k
Broyden family (Rodomanov and Nesterov, 2022)
( Woo
Online- guided QN (Jiang et al., 2023)
O 1 bog X)
BFGS with line-search (Jin al., 2024a:b)
O log K)
'The formal definition of uniformly independent sequence is given in Appendix C.5, which is adapted from quasi-Newton literature (Conn et al., 1991; Nocedal and Wright, 1999)
HDM (This paper)
Ole 1 100oK
6

---

Provable and Practical Hypergradient Descent
the quality of the preconditioner and can search for an opti- mal preconditioner in given closed convex set P, whereas quasi-Newton methods use the secant equation as indi- rect proxy. Both approaches require safeguard to pre- vent divergence in the warm-up phase, which is achieved by line-search in quasi-Newton and null step in HDM.
10"0
1000
Function value gap
Heavy-ball
AGD
HDM-HB-Diag
HDM-AGD-Diag
HDM-HB-Full
HDM-AGD-Full
10"
10"
10 30
10
200
400
600
200
400
600
Iteration
Iteration
4. HDM with Momentum
(a) HDM-EB
(b) LIDM-AGD
In this section, develop two variants of HDM, with heavy-ball momentum (Polyak, 1964) and with Nesterov momentum (Nesterov, 1983).
Figure 3: The convergence behavior of HDM-HB and HDM-AGD on toy quadratic problem. Figure 3a: HDM-HB Figure 3b: HDM with Nesterov momentum.
4.1. Heavy-ball Momentum
where 7k minep, K E (P,
Heavy-ball method is practical acceleration technique: x x² (=*) + Bx - -x=-)). (11)
depends on the iteration trajectory {a Jeski PK
O(VK) is the regret with respect to feedback (12); V == p(x') min 4 -
}: A is defined in Lemma 2.4.
The momentum parameter B5 typically chosen as scalar By / with Bx > O. HDM can learn a matrix momentum B& E B S RTx" with convergence guarantees (Theorem 4.1) when B satisfies this assumption:
4.2. Nesterov Momentum
HDM can also improve accelerated gradient descent AGD (a.k.. Nesterov momentum): for a given sequence {As}.
A5: Closed convex set B satisfies / E B, dBam(B) S D.
y =² + (1 Al (z x²)
HDM can jointly learn the pair (Px, Bx) using the modified feedback function
k+1 n² - - ((()
(13)
ha (P, =- [V
(P.B) x),x
(12)
k+1 2h Auti An
L ()()
HDM can learn preconditioner Ps that replaces 1 to ac- celerate the gradient step (13) in AGD, We call the resulting algorithm HDM-AGD AGD. It achieves ((1/K² pk/ / con- vergence rate and empirical speedup (Figure 3b). Fur- ther discussion of HDM-AGD appears in Appendix D.2.
where vi is the potential function for heavy-ball momentum defined by (ar, = (xx + #| x -- 1
(Danilova et al., 2020); x B), = x - + B(x x)) updates x; and w > 0 and 7 > 0 are constants. Algorithm 2 presents the resulting method, HDM- HDM which uses HDM, heavy-ball momentum, and a null step to ensure decrease of the potential function vb. Figure 3a compares non-adaptive heavy-ball (P& = al, B = BI) against HDM-HB with full-matrix/diagonnl preconditioner and scalar momentum.
Theorem 4.2 (Informal). Instate )0(**) in (6). Under A1, A3, HDM-AGD with proper initialization gives ((x,K+t) S Xxs 0 R + (&). where Xx 2L depends on rk.
5. Experiments
Algorithm HDM with heavy-ball momentum (HDM- HB)
input initial point zd x. Tpp Th 0, PI. Bi for k == 2,... do
This section conducts numerical experiments to validate the empirical performance of hypergradient descent. We compare HDM-Best (see Section 5.1 below) with differ- ent adaptive optimization algorithms.
k+12/ = rx_ P&V f(**) + (x* - xb-1)
Pa+1 = [P - n, V Wpliht (Pk, Bb))
Bx+1 = [B - no V Whhatat - (Px, B&)]
(1++11 x²k)=
arg min
1b( .x))
5.1. Efficient and Practical Variant: HDM-Best
(x(t)) ak- (att
end
This section highlights the major components of our most competitive variant HDM-Best. The algorithm and more detailed explanation are available in Appendix A. The im- plementation is available at https: httpttitt.uh..ggg/// com/ udel www.rrrwppperrre
output x K+1
Theorem 4.1 (Convergence of HDM-HB), Instate sp(a*t ) in (6). Under A1, A3 and A5, Algorithm with Tho Up = O(1/VK) or (k)) satisfies
Diagonal Preconditioner and Heavy-ball Momentum. HDM-Rest updates x by (11) with diagonal preconditioner
p(( <
p(2))
KV 4 1+++1
7

---

Provable and Practical Hypergradient Descent
P SSC and scalar momentum B {BI B RJ. This choice balances practical efficiency and implementa- tion complexity. Boundedness of P does not greatly impact the performance, while the bound on B can significantly change algorithm behavior. Two empirically robust ranges for B are [0, 0.9995] and [-0.9995, 0.9995].
Testing Configurations.
1) Maximum oracle access. We allow maximum of 1000 gradient oracles for each algorithm.
2) Initial point. All the algorithms are initialized from the same starting point generated from normal distribution
NO, I,) and normalized to have unit length.
AdaGrad for Online Learning. HDM-Best uses AdaGrad to shorten the warm-up phase for learning of (Px, 3x) (see Section 3.2). AdaGrad usually yields faster convergence HDM than online gradient descent the cost of additional memory of size n.
3) Stopping criterion. Algorithms stop if V f S 10-4.
Table 2: Number of solved problems for each algorithm.
Algorithm/Problen
SVM (33 f)
Lagistic Regression (33 f)
5.2. Dataset and Testing Problems
5
2
GD-HB HB
9
7
We test. HDM-Bess on deterministic convex problems. We adopt two convex optimization tasks in machine learning: support vector machine (Lee and Mangasarian, 2001) and logistic regression (Hastie, 2009). The testing datasets are obtained from LIBSVM (Chang and Lin, 2011) 1).
AGD-CVX
8
3
AGD-BCVX
7
6
Adam
26
11
AdaGrad
8
L-BFGS-M1
13
11
L-BFGS-M3
20
14
L-BFGS-MS
26
16
5.3. Experiment Setup
L-BFGS-M10
18
BFGS
32
26
Algorithm Benchmark. We benchmark the following algorithms. More details appear in the appendix Table 3.
HDM-Rest
32
21
GD. Vanilla gradient descent.
For each algorithm, we record the number of successfully solved instances fll/ I 10-4 within 1000 gradient oracles). Table 2 summarizes the detailed statistics. The number of instances solved by HDM-Best is comparable to that of BL--FGSSMMM
GD GD-HB. Gradient descent with heavy-ball momentum.
AGD-CVX. The smooth convex version of accelerated gradient descent (Nesterov momentum).
AGD-SCVX. The smooth strongly convex version of ac- celerated gradient descent.
Support Vector Machine. Figure shows the function value gap and gradient norm plots on sample test instances support vector machine problems. The optimal value for each instance is obtained by rumning BFGS until || Vflle S 10-1 We see that the practical variant of HDM-Best achieves a significant speedup over other adaptive first- order methods. In particular, HDM-Best often matches L-BFGS- M5 and L-BFGS-MMCC while its memory usage is closer L-BFGS-MA Notably, Adam also achieves competitive performance in several instances.
Adam. Adaptive momentum estimation.
AdaGrad. Adaptive (sub)gradient method.
BFGS. BFGS from scipy.
L L-BFGS-MA Mk. BSBGS with memory size k in scipy.
Practical variant BDDM-Best uses as memory 7 vectors of size n, comparable to memory for L-BFGS-M1..
Algorithm Configuration.
See Appendix A for details.
Logistic Regression. In logistic regression (Figure 5), HDM-Best still compares well with L-BFGS -MG and is significantly faster than other adaptive first-order methods.
For HDM-Best, we search for the optimal 7p within 10,, 10/ IL, 100/L] L. and 176 E (1,3,5, 5, 10, 100). are
Stepsize in GD, GD-HB, HB, AGD-CV, and all set to 1/L.
Overall, HDM-Best demonstrates superior performance on deterministic convex problems and comparable with the mature L-BFGS family. We believe that further devel- opment of HDM will fully unleash its potential for broad range of optimization tasks.
The momentum parameter in GD-HB is chosen within the set 0.51, 0.9, 0.99).
The Adam stepsize is chosen within the set (1/L,10 1,,00-2111 1,10,,111111111 1,, B1 = 0.9,3, = 0.999.
The AdaGrad stepsize is chosen within the set (1/L,10-3, 10 10.21022100 1001,,,,000
6. Conclusion
This paper addresses the long-standing challenge of estab- lishing convergence of the hypergradient descent heuristic.
BFGS, L-BFGS Mk use default parameters in scipy.
8

---

Provable and Practical Hypergradient Descent
svmguide3
12
Functon valuee gap
12a
10
10"
10
16"
97
10
50
10
252
1enn
10"h
25
200
10.0
200
1003
RD
1r00
lleration
lloration
Iteration
leeratoon
1aa
a8p
wBA
11'
sumguide3
Cradert
13'
10"
12'
93"
13
907
100 Iteration
200
13"
6.0
907
Iee Ileration
Iteration
Iteratoon
GD
AGD-CV -VX
Adam
BFGS
L-BGG-MM
L-BFGS-M10
GD-HB
AGD-SCVX
AdaGrad
L-BFGS-M1
L-BFGS-M5
HDM-Best
Figure 4: Experiments on support vector-machine problem. First row: function value gap. Second row: gradient norm
aa
wea
ionosphere scale
icnnt
Functinn volua gop
19t
16
16¹
16
19
10
16"
10"
10
10"
lleration
Deration
llenaioon
lleration
vida
lonosphere scale
iicnn1
127
17"
Grntett Norm
10"
93"
200
400
300
800
1000
10"
330
403
500
200
1000
200
530
1000
13
207
430
120
1000
Figure 5: Experiments on logistic regression problems. First row: function value gap. Second row: gradient norm
We provide the first rigorous theoretical foundation for hy- pergradient descent and introduce novel online learning perspective that extends to other first-order methods with adaptive hyperparameter updates. Our theoretical advances support effective and scalable enhancements that allow the (first-order) HDM to achieve superlinear convergence with guarantees that resemble quasi-Newton methods. Build- ing on these results, we propose HDM-Best, an efficient variant of HDM that performs competitively with the widely used L-BEGS method on convex problems. This empiri- cal success positions HDM as compelling alternative for modern machine learning. Extending the theory of HDM to stochastic and nonconvex optimization is crucial next step to understanding its potential to speed up the training of large-scale models.
Acknowledgments
MU, YC, and WG gratefully acknowledge support from the National Science Foundation (NSF) Award IIS- 2233762, the Office of Naval Research (ONR) Awards N000142212825, N000142412306, and N000142312203,
the Alfred Sloan Foundation, and from IBM Research as founding member of Stanford Institute for Human- centered Artificial Intelligence (HAI).
Impact Statement
This paper addresses the convergence behavior of the hy- pergradient descent heuristic. There are many potential so- cietal consequences our work, none of which we feel must be specifically highlighted here.

---

Provable and Practical Hypergradient Descent
References
Wenzhi Gao, Ya-Chi Chu, Yinyu Ye, and Madeleine Udell. Gradient methods with online scaling. arXiv preprint arXiv:2411.01805 2024.
Naman Agarwal, Rohan Anil, Elad Hazan, Tomer Ko- ren, and Cyril Zhang. Disentangling adaptive gra- dient methods from learning rates. arXiv preprint arXiv:2002. / 1803, 2020.
Trevor Hastie. The elements of statistical learning: data mining, inference, and prediction, 2009.
Luís Almeida, Thibault Langlois, José Amaral, and Alexander Plakhov. Parameter adaptation in stochastic optimization. In On-line learning in neural networks, pages 111-134. 1999.
Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Ma- chine Learning, 69(2):169-192, 2007.
Elad Hazan et al. Introduction to online convex optimiza- tion. Foundations and Trends@ in Optimization, 2(3-4): 157-325, 2016.
Larry Armijo.
Minimization of functions having lipschitz continuous first partial derivatives. Pacific Journal of mathematics, 16(1):1-3, 1966.
Robert A Jacobs. Increased rates of convergence through learning rate adaptation. Neural networks, 1(4):295- 307, 1988.
Atilim Gunes Baydin, Robert Cornish, David Martinez Ru- bio, Mark Schmidt, and Frank Wood. Online learn- ing rate adaptation with hypergradient descent. In In- ternational Conference on Learning Representations, 2018. URL hattss:/opeeneeviss..ttttt/ id=BkrsAZWAb.
Ruichen Jiang, Qiujiang Jin, and Aryan Mokhtari. On- line learning guided curvature approximation: quasi- newton method with global non-asymptotic superlinear convergence. In The Thirty Sixth Annual Conference Learning Theory, pages 1962-1992. PMLR, 2023.
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.
Renlong Jie, Junbin Gao, Andrey Vasnev, and Minh-Ngoc Tran. Adaptive hierarchical hyper-gradient descent. In- ternational Journal of Machine Learning and Cybernet- ics, 13(12)3375- -3055, 2022.
Chih-Chung Chang and Chih-Jen Lin. Libsvm: library for support vector machines. ACM transactions on intel- ligent systems and technology (TIST), 2(3):1-27, 2011.
Qiujiang Jin, Ruichen Jiang, and Aryan Mokhtari. Non- asymptotic global convergence rates of bfgs with exact line search. arXiv preprint arXiv:2404.01267. 2024a.
Andrew R Conn, Nicholas IM Gould, and Ph L Toint. Convergence of quasi-newton matrices generated by the symmetric rank one update. Mathematical program- ming, 50(1):177-195, 1991.
Qiujiang Jin, Ruichen Jiang, and Aryan Mokhtari. Non-asymptotic global convergence analysis of bfgs with the arlie line search. arXiv preprint arXiv:2404.1773 2024b.
Marina Danilova, Anastasiia Kulakova, and Boris Polyak. Non-monotone behavior of the heavy ball method. In Difference Equations and Discrete Dynamical Systems with Applications: 24th ICDEA, Dresden, Germany, May 21 21-25, 2018 24, pages 213-230. Springer, 2020.
Diederik P Kingma. Adam: method for stochastic opti- mization. arXiv preprint arXiv:1412.6980 2014.
Frederik Kunstner, Victor Sanches Portella, Mark Schmidt, and Nicholas Harvey. Searching for optimal per- coordinate step-sizes with multidimensional backtrack- ing. Advances in Neural Information Processing Sys- tems, 36, 2024.
Alexandre d' Aspremont, Damien Scieur, Adrien Taylor, et al. Acceleration methods. Foundations and Trends@ in Optimization, 5(1-2):1-24) 2021.
Aaron Defazio, Harsh Mchta, Konstantin Mishchenko, Ahmed Khaled, Ashok Cutkosky, et al. The road less scheduled. arXiv preprint arXiv:240S. 15682, 2024.
Yuh-Jye Lee and Olvi L Mangasarian. Ssvm: A smooth support vector machine for classification. Computa- tional optimization and Applications, 20:5-22 2001.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive sub- gradient methods for online learning and stochastic opti- mization. Journal of machine learning research, 12(7), 2011.
Xiaoyu Li, Zhenxun Zhuang, and Francesco Orabona. A second look at exponential and cosine step sizes: Sim- plicity, adaptivity, and performance. In International Conference on Machine Learning. pages 6553-6564. PMLR, 2021.
Roger Fletcher. Practical methods of optimization. John Wiley& & Sons, 2000.
10

---

Provable and Practical Hypergradient Descent
Ashique Rupam Mahmood, Richard S Sutton, Thomas Degris, and Patrick M Pilarski. Tuning-free step-size adaptation. In 2012 IEEE international conference acoustics, speech and signal processing (ICASSP), pages 2121-2124. IEEE, 2012.
Vincent Roulet and Alexandre d' Aspremont. Sharpness, restart and acceleration. Advances in Neural Information Processing Systems, 30, 2017.
David Martinez Rubio. Convergence analysis of an adap- tive method of gradient descent. University of Oxford, Oxford, M. Sc. thesis, 2017.
Yura Malitsky and Konstantin Mishchenko. Adaptive gra- dient descent without descent. In International Confer- ence on Machine Learning, pages 6702-6712. PMLR, 2020.
Nicol N Schraudolph. Local gain adaptation stochastic gradient descent. 1999.
Yura Malitsky and Konstantin Mishchenko. Adaptive prox- imal gradient method for convex optimization. Advances in Neural Information Processing Systems, 37: 100600 100697, 2024.
Richard S Sutton. Adapting bias by gradient descent: An incremental version of delta-bar-delta, In AAAI, vol- ume 92, pages 171-176. Citeseer, 1992.
Pauli Virtanen, Ralf Gommers, Travis E Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, et al. Scipy 1.0: fundamental algorithms for scientific computing python. Nature methods, 17(3): 261-272, 2020.
H Brendan McMahan and Matthew Streeter. Adap- tive bound optimization for online convex optimization. arXiv preprint arXiv:000..499 1002.4908, 2010.
Renato DC Monteiro, Jerome W O'Nea, and Arkadi Ne- mirovski. A new conjugate gradient algorithm incorpo- rating adaptive ellipsoid preconditioning. Report, School of ISyE, Georgia Tech, USA, 2004.
Xiaoyu Wang and Ya-xiang Yuan. On the convergence of stochastic gradient descent with bandwidth-basee step size. Journal of Machine Learning Research, 24(48); 1 1-49, 2023.
Yurii Nesterov. A method for solving the convex program- ming problem with convergence rate (1/k2). In Dokl akad nauk Sssr, volume 269, page 543, 1983.
Ziyao Wang, Jianyu Wang, and Ang Li. Fedhyper: A universal and robust learning rate scheduler for feder- ated learning with hypergradient descent. arXiv preprint arXiv:2310.03/50 2023.
Jorge Nocedal and Stephen J Wright. Numerical optimiza- tion. Springer, 1999.
Francesco Orabona. A modern introduction to online learn- ing. arXiv preprint
Yushun Zhang, Congliang Chen, Ziniu Li, Tian Ding, Chenwei Wu, Yinyu Ye, Zhi-Quan Luo, and Ruoyu Sun. Adam-minn Use fewer learning rates to gain more. arXiv preprint arXiv:2406. 16793, 2024.
2019.
Francesco Orabona and Dávid Pál. Coin betting and parameter-free online learning. Advances in Neural In- formation Processing Systems, 29, 2016.
Zhenxun Zhuang, Ashok Cutkosky, and Francesco Orabona. Surrogate losses for online learning of step- sizes in stochastic non-convex optimization. Inter- national Conference on Machine Learning, pages 7664- 7672. PMLR, 2019.
Kaan Ozkara, Can Karakus, Parameswaran Raman, Mingyi Hong, Shoham Sabach, Branislav Kveton, and Volkan Cevher. MADA: Meta-adaptive optimizers through hyper-gradient descent. In Forty-first International Con- ference on Machine Leurning, 2024. URL https: / sopenreview.net//e..ee htt.:/eettooommmmidttttttoo wiw.mmmeedtttttttata.....
Boris T Polyak. Some methods of speeding up the conver- gence of iteration methods. Ussr computational mathe- matics and mathematical physics, 4(5):1-17, 1964.
Boris T Polyak. Introduction to optimization. 1987.
Anton Rodomanov and Yurii Nesterov. Greedy quasi- newton methods with explicit superlinear convergence.
SIAM Journal on Optimization, 31(1):785-81) 8115 2021.
Anton Rodomanov and Yurii Nesterov. Rates of superlinear convergence for classical quasi-newton methods. Math- ematical Programming, pages 1-32, 2022.

---

Provable and Practical Hypergradient Descent
Appendix
Table of Contents
HDM Practice
B Proof of Results in Section
14
Auxiliary Results
B.2 Proof of Lemma 2.1
15
Proof Lemma 2.2
B.4 Proof of Lemma 2.3
16
Proof Lemma 2.4
B.6 Intermediate Iterate Convergence with Adaptive Online Algorithms
16
Proof Results in Section
C.I Proof of Theorem 3.1
16
Proof Theorem
C33 Proof of Theorem 3.3
17
Proof Lemma 3.1
C.S Proof of Theorem 3.4
19
D Proof of Results in Section
21
D.I HDM + Hcavy-ball ball Momentum (HDM-HB)
21
D.2 HDM + Nesterov Momentum (HDM-AGD)
24
E Additional Experiments
28
E.1 Details of the Algorithms
28
E.2 Ablation Study of 773--Best..
28
E,3 Additional Experiments on Support Vector Machine Problems
.o..............................
28
E,4 Additional Experiments on Logistic Regression Problems
28
E.5 Experiments against Additional Benchmark Algorithms
33
Structure of the Appendix. The appendix is organized as follows. In Appendix A, introduce practical variant of hypergradient descent and explain its implementation details. Appendix E provides additional experiment details on the tested problems. Appendix B to Appendix D provide proofs of the main results in the paper.
12

---

Provable and Practical Hypergradient Descent
A. HDM in Practice
This section introduces HDM Best, our recommended practical hypergradient descent method. This variant adapted from HDM-HB, with simplificatiion reduce the implementation complexity. The algorithm is given in Algorithm 3.
Algorithm 3 HDM-Best
input starting point x² = x², P $ D, [0, 0.9995], initial diagonal preconditioner Pi E s4 nD
initial scalar momentum parameter B1 = 0.95, AdaGrad stepsize 7pp, 7 > 0, AdaCrad diagonal matrix U1 = 0,
AdaGrad momentum scalar 11 = 0, r > 0
for k 1, 2,... do
x411/2 L² PR (AVS((")) + 3x(x* xb-1) (Pss 3k) = IV F(a
V pplihhaa x
Flement-wile product
Vah x- (Pxs 8k) = (V ([x++1/3) ) -
- Inner product
Uk+1 = Ux + V Wh aa (Pk: 3x) aph
# Diagonal matrix
Uk+1 = 0% + V slaz -- (Pr, 3k) Bahez x (Pks B&) Scalar matrix
Pa+1 DD Ps Tpp U phiyt (Pk, 3x)] # Diagonal matrix
0k+1 ([..0.99995 15x T/UU 1/2 V s ah (Pk, Bc)]
x k+1 arg min oE x
f(x).
end
output o: K+1
We make several remarks about Algorithm
Choice of online learning algorithm. Unless ((x) is quadratic, adaptive online learning algorithms such as AdaGra often significantly outperform online gradient descent with constant stepsize. Note that AdaGrad introduces additional memory of size store the diagonal online learning preconditioner U.
Sensitivity of parameters. The two stepsize parameters in AdaGrad are the most important algorithm parameters: 7pp Th- According the experiments, ', should be proportional to L/L, the smoothness constant, while aggressive choice of 7 {1, 10, 100} often yields fast convergence. A local estimator of the smoothness constant L can significantly enhance algorithm performance.
Heavy-ball feedback and null step. In practice, it is observed that dropping the //r (P, x/|² in the numerator of heavy-ball feedback (12) often does not affect algorithm performance. Therefore, in Algorithm 3 the hypergradient z||² is ignored. On the other hand, the 1 || (P, smoothes the update of 6g and can strongly affect convergence. The parameter 7 should be taken to be proportional to L according to the discussions Appendix D.I. The null step taken with respect to the function value f((x:) instead of the baaly-ball potential function.
with respect to 5 ||x (P.
x||² term in the denominator
Memory usage. The memory usage of HDM-Best, measured terms of number of vectors of length n is 7m: 1) three vectors store primal iterates x ,x, x 2) Two vectors store past and buffer gradients V fz()) Vf(xt). 3) A vector stores the diagonal preconditioner Pt. 4) A vector stores the AdaGrad stepsize matrix U.
Computational cost. The major additional computation cost arises from computing hypergradient Vh, which involves one element-wise product and one inner product for vectors of size n. In addition, HDM-Best needs maintain diagonal matrix for AdaGrad. The overall additional computational cost is several (n)) operations.
13

---

Provable and Practical Hypergradient Descent
B. Proof of Results in Section 2
B.1. Auxiliary Results
Lemma B.1 (Sublinear static regret), Given a family of convex and 7/-Lipschitz losses {hu}. online gradient descent
Pk+1 [p Thk (Pt() with stepsize Uis 27VK or U)
D
generates { such that
2/v
Ekzi (Px) - -k
for any P E P.
The result follows from standard dynamic regret analysis from online convex optimization literature, and adapt the proof for our analysis. For any P E P, we deduce
|P PI = μ Ps The Vh Pk)) - PIE
< | Pk P a (
(14)
S P P1l 27 (V> /h (Pk), Px - P) + (Px))11
< P - PIE 2 (/x (P&) - h2 + ni?
(15)
where (14) uses non-expansiveness of orthogonal projection; (15) applies convexity and y-Lipschitz continuity of hy. Re-arranging, we get
hy (Ps) h2 S 2T
||| - Pl
PP++1 111:11111111 ?
Suppose π7 is non-increasing, and we have
hp)) S E
PA - P1
| - PI| + 2/Z Σ 7
2714
2np
$ 2m Pl - P1 + +
k-1
1
+ -/2 Σx= Tl
k==
9h11
s 1 12 + Σズ=
1
D2
2/2 Σ 7
2m
7/+1
27
$ D² + Ek=
M 2
<
2yDVK
since Ek=1 1 2V... This completes the proof. VE
Lemma B.2 (Sublinear dynamic regret (Hazan et al., 2016)). Given a family of convex and --Lisshitzz losses {ha}, online gradient descent Pa+1 = IIp PP - 1) hhv((P)) with constant stepsize 1 2//K generates stepsizes {Px} such that
D
MK (ppp)) hu (Px)
7DD VK + "
PL(PPt))
(16)
where (Pa), Ps are arbitrarily chosen competitor stepsizes and PL((Pt)) = Ek-1 1P Petille is the path length of the competitors.
Proof. Starting from (15), we let P P% and re-arrange to get
hpkpk) - h4 (Px) - 2n I1 Px11 - | - -Px112] + 3n?
= 11 P| + 2(Ph, Pk+1 Px)]+ 21²
Telescoping, we get
Σ hr (Px) hy (Px)
1P + 322K + EK (Pr. Pe+ PP))
2n
IP
+ 2,2K + 1 EK- (Pk41, Px- -Prt1) + (Pk, -
(17)
2n
3D2 2 D IP' - -Patille
(18)
3D2
+ +
where (17) is by re-arrangement: (PE, - Ps) = EE K- (Px41, Ps - -Pa-)) + (PK, Pk+1) - (PI,P)) (19)
k=
applies dP) D and Cauchy-Schwarz 12 Pr. Pk+1) | || - 1| Dj -P [.. Plugging
in D 2 completes the proof.
14

---

Provable and Practical Hypergradient Descent
Lemma B.3 (Logarithmic static regret (Orabona, 2019)). Given a family of pustrrongly convex and 7-Lipschitz losses (lig). online gradient descent Pk+1 p Ps T/k Vhg (Ps)) with stepsize vi generatsss sequence of scaling matrices {P&} such that Ei=1 (P())) - hi P) S 2 log K.
generates
Proof. Using strong convexity, we have h4 (P) 2 (Pp) + (Ph) Pk) + - and
|| p 1 Pk P1 27 (h,()P)): Ps: P) -
< Ps P1 27 h2g PPa) - (P) + Th wmm Pxll
1 x Pr - -11 - Z,d (Px - h2( + R
(19)
where (19) plugs in 77k = 1/(kk). Re- de-arranging the terms,
1a (Ps) - ha (P) S [[ - 1)llPs - P11 k|| PI
x²
2kp
and telescoping gives Ek= ha (Px) ha (P) S E
=² kk 2kµ
S z/Z (log K + 1), which completes the proof.
B.2. Proof of Lemma 2.1
Consider the first property. Convexity and smoothness follow directly from (Gao et al., 2024). To verify strong convexity, note that for (a)) -()) f(z))
d V = [ (()(
V
V
) 2 1
da
[
[V
since f(f(x) č pl and x & x This completes the proof of the first property.
Next, we consider the second property. Lipschitz continuity also follows from (Gao et al., 2024). To verify exp-concavity, recall that twice-differenniaale function is B-exp-concave if (²)(x) > VVh(z)Vh(x) for some 33 2 0. By definition of D,
(P) ((()) f(=)PP) PV)()) M
diag V f (ax) ((t) PV/(a))
and (P), (Vig((/(()))))) f(z 1x--VV (in) Using PP = μl, deduce that
[
(P) h. (P) (P)
(( fa- PV (())ddin((V(())
PV (())) (a (P-P)))) T (((())
|+
[
= diag( V/(x)
f(x PVf(x)) - [V(e-P fir--PV PV f(x))
diag V((w)
|[][(
[V
[V/[(=)]
[[((]]
= diag(
[|][=]]|
f(())
M/
Vf PV
diag(
|V
Vf(a)
(20)
where (20) uses p-strong convexity of f(r). Now, it suffices to verify that
V((=-PV(())
((x-PV/(())"
(21)
[
for all x & X². Write \/(--PV((E) V
V ((w)) -V))) and let 2= vffl -V)()) we
[[[(a)
have, by L-smoothness, that | LIIVV(())) < [x)] and
V(==~V/()) -((=~~((a))
||
( + I )
((()
+ (18/12)) Vf(a)) V
vS(2)] [v((2||
=
/(=))((()) + [V + M + ||
[V((r)
2|| + (+ (1+ | (1 + LD)3
1+
MM
Hence, for 8 5 1
(I+DD)= the relation (21) holds. We conclude that hp) = (d is (I+LD)) exponentaal concave.
15

---

Provable and Practical Hypergradient Descent
B.3. Proof of Lemma 2.2
We use Lipschitzness from Lemma 2.1 and Lemma B.I by taking 7 1+ LD and `д (LD+1)VK or (LD+1)Vk Here, we use slightly loose bound to unify the constants in static and dynamic regret bounds.
D
B.4. Proof of Lemma 2.3
We use Lipschitzness and strong convexity from Lemma 2.1 and invoke Lemma B.3 by taking LD.
B.5. Proof of Lemma 2.4
The proof resembles (Gao et al., 2024) and uses tighter analysis. Consider the optimality measure f(oK+1)- f(xx), and deduce that
f(*K+1)- - f(x²))
-(*
1
kk=1 [(x (actti-s(a)) [(a)) 1(0))
1( - 11x4+11
[/( - ) [(x) パ()))
k=l max - (P. (1)00
パ(
Next, using (x) f(x)) [+)] 11 -
max (axx--A_(122,0/11///1)1
max hh (P..0-11(P2))00001/(011111
max(-A, (P.).))
max -h -h (P%)..)
-(==))))~(((>)000((((())) 2
((x=))
(xck
4
Finally, we deduce that
f(x f(x') s
A²
> maxt - A
A²
A²
max (Px) 3( ((E))
min
Kmax K Ex - h (P (P)).0) f(x)) f(x') 1(x*)}
and this completes the proof.
B.6. Intermediate Iterate Convergence with Adaptive Online Algorithms
Two disadvantages of constant stepsize online gradient descent is 1) the dependence on the total number of iterations K;; and 2) no regret guarantee for the intermediate iterates. One simple fix is let Me = (11/Vk) and online gradient descent achieves the same sublinear regret guarantee (up constant multiplicative factor) for any i (Orabona, 2019). Similar arguments hold for adaptive gradient methods (Duchi et al., 2011: I; McMahan and Streeter, 2010).
C. Proof of Results in Section 3
C.1. Proof of Theorem 3.1
Plugging (5) from Lemma 2.2 into Lemma 2.4 completes the proof.
C.2. Proof of Theorem 3.2
Invoking Lipschitzness from Lemma 2.1 and (16) from Lemma B.2 with y= 1+
(LD+IJVK gives
D
ΣK (Pt) hap (Px) S PK +
LD+1
K
K-1
|| Pr: Pr-ille.
2
16

---

Provable and Practical Hypergradient Descent
Plugging the relation into Lemma 2.4 completes the proof.
C.3. Proof of Theorem 3.3
For Theorem 3.3 and Lemma 3.1 only, we will define the following modified feedback function by replacing f(* in the numerator by f(x*):
hz = faa fa- ((a)) [|) 2 0.
For fixed z, hg (P) only differs from the original hypergradient feedback by constant; it has the same properties as the original feedback function, and the algorithm is exactly the same since only the gradient of hy is considered in the algorithm update. Using the definition of (P), we deduce that
1(a*t))f((") [(x1)-((*')
I (att")-((e")
)((t))(()))
$ + E (ultt)-f(aa
= x Ek= min{ (P ,))
(22)
((0))
< x E min miin (Pb),
(23)
k=
S (min 22 E h (Px). 1))*
where (22) plugs in the definition of hn; (23) uses T-smoothness and that hn is nonnegative. Using Lemma 2.2, we get ΣK ha (Ps) >x ha (P) + Pk for any P P. Next, consider the quantity he [[V2f(="'] and deduce that
{((('((=))))) f(x IV f(z" ((a))-
V
|| 2 f(" v(x)
1-
(24)
(()
f(n" [(
(25)
2/
| x---"
where (24) uses T-smoothness (xx) - f(x*) )= I | - x= and (25) uses //[<>]] 2 12110 - 112 Then,
r - (V - x x- [V'
[V''""""'~'(''''''"">>>>"">>>'") -0)-==()-)) Vf(x')
since Vʃ(x*) = 0. Plugging in Vf(x)) V5(x*) = fo v ((1-
- [)) x' *dl,, we deduce that
(==) - v)((*)))| = = --) - fo' v2f(2² + t(x - x² () x )ttll
=+]]] = -I1 -v====""'V"((++++//>>>>)>>> ((x==+((===)]((< -
xd)dl|
-
< So 1H| x x² 1|2dt 41 x+1
(26)
where (26) uses H-Lipschitz continuity of fx) and, consequently,
|| [==IV\((=)) x'
= || - - (V vf(x
<
H || - x 3/o
(27)
since v²f(x*) 2 pl due to strong convexity. Plugging the relation back, we get
H²
h (V2 <
4p 1
1-
H² 8
||
x 11
(28)
2/
1 x
Since [V2f(**)] P by assumption,
Ekn S {
+ px Px
Na
H2
Σx
k= |100 - x12 1/2 + pk:
-x-1
and we get
((ckt))- - f(x*) < ( [(x)) min
2 k
K
||,
xz 112 2
13)
which completes the proof.
17

---

Provable and Practical Hypergradient Descent
C.4. Proof of Lemma 3.1
For brevity let p = [V= We have, according to the update of online gradient descent, that,
[P - P* = - |||||| [Px v/ (Px)) - 1
$ || - 77 Thh (Px) - P*1 1/:
||& p- (V. (Pt): Pk- - PT) + Vhgt (Px)
$ P|& - 2T1 2//h, (Px) - h1 (P*) [] + 1h, (Px) - inf [P)]
(29)
PERuxO
= ||& - P- -m (Px) - h (P*) + 22 P1 (Px) - han (P*) + 22 (P*)
(30)
|| - 1T -2n(1 1) 1 (Px) h (P)) + 2Ln hig (P*),
(31)
where (29) uses L-smoothness and inf PEREXN h (P) for all æ E x (30) a simple re-arrangement.
Next we lower bound hrt (Px) - hzg (P*). Using strong convexity,
[- P&VS(a*)) - 1(** - (*V)(=)))
f(z -
f(a² f'*')(z*))
2 $110 - x² - (VV(==))++(((>*)))
(32)
where (32) uses f(x) - f(xx)= )2 2 -110-2011 The first term can be bounded follows:
11* x²- - PR V ( 212
11 p=V - x²' + (()))
= 1|a (*V - -2 12 2(x - f'V)((a)))))) - -I",(P"-PAVV((ff) + -
- 110* - px*) -x"1|²
where we use the inequality 2(a, b) 2 -01aa|2 8- 1b12 with B = Plugging the relation back into (32) and dividing
both sides by || V (x* )|2
has (P%) - hes (P*) = f(x' - ((x")+((2) - -aaa-"'''('"""""
2 G1IPP - Ph) [V 111
Vf(²')
113
11
f(=)) (fae)))(a-p----i
2
-11(P" - PA) |V
V
112
//2
110a
(Pm)
(33)
2 "II(P= - PW) V/('')
1 H² -|
[+ high (P*)
(34)
8y
2 [P( - Ph)
V
11-
H²x 1|a
x=" h (P'),
(35)
|V
where (33) uses the definition of h (34) applies the relation || f()) - =z1| <
H ||-=1=x"
x=11 1|2 from (27); (35) again
uses the fact || fxx)]] 2 μ²11æ= 2=12 Putting the relations back into (31) and assuming 17 S 2L'
|| || p= 11
< |Pp 1 13--
M(n Lnn 2
(Pp PT)
[V] 112
V((a")
+ H (n
|100
x² 12 + 2n1 - LTd) ) (P*) ) + hha (P*)
4/1²
= |P pa
u(n Lnn 2
(P -P*) V/(c")
112 )
+ HP
1100 xx 112 27th (P*)
< | PP pr]
12
p(u Tny2) 2
(Pa - (P*) V(aa
112 + 122(n- Iay 1100 x= 112 + 2n H2 1| - x=11|
(36)
44
= | P:
P
12
p ا 2
([ - -P* V/(x
1|2 + (2n Tnp
2) 1²
|100* - x=" 1p2
where (36) uses the relation (28) and this completes the proof.
18

---

Provable and Practical Hypergradient Descent
C.5. Proof of Theorem 3.4
The proof of Theorem 3.4 relies on the following auxiliary results.
Lemma C.1. Under A1 to A4, hz inf QER=x" hQ( S 2p (LD+1)?.
Proof. Note that (P) = f(a PV f(x))- f(x)
2 f(a)) for all P E P, we deduce that |[][))]
|V](2)]
(P))
inf
(2) ((--PV/(x)) (()))/(a))))
((a))f(())
(37)
QER"x"
[VS())
PV)(=))- f(x')
1
IV (V
(38)
2p
(39)
2p
[/-*
S
(40)
zp
where (37) applics hp(P) 2 1(=))((() (w)); ||||| s D.
(38) uses f(x) - f(x*) - [f
[f(a)]?? (39) uses L-smoothness and (40) uses
24
Then we show that HDM converges even when 17 is constant that does not depend on K. Lemma C.2. Under A1 to A4, Algorithm I with Me (0, 21( satisfies
limg-soo 100 x²1l O. limg-+0 K Eaaillat - x=112 cc.
Proof. Using the online gradient descent update, we have
|P
p < |Ps 7V (Px) - P1
|P P1] (Vh,,
P) , (Px)1
< P Pll 2n( (Px) - h2 (P) + 2T, (Px)
inf hygh (P))
(41)
PERuXn
PPs P11 2nh (Pk) + 2 (P) 2h (Pk)
inf hat (P)],
PERaXa
where (41) follows from convexity (P) 2 (Ph) + (Vhg P Pa) and L-smoothness of (P). Next, we invoke the upperbound on ha* (Px) inRQERex" h2t (Q) from Lemma C.I:
2 (Px)
inf PERaX"
hy (P) <
2L (LD + 1)²1² = x(LD + 1)3
2n
and deduce that
2nh (Pt) < 2m/,4 (P) P/ - PI] |P P1] + 2 (Pk)) inf h (P))
PeRexa
< 2mhg (P) + Ps - 2 PA+1 P1] + 7 (L + 1)².
Next, we divide both sides of the inequality by 21 and
ha (Pa) S h2 (P) + |P 21
| 2
De(D++1)2
2n
Telescoping the relation and using diam ( < D, we get
ΣK hat (Px) S 5 K k=
Pigh (P)
D²
+
mx(LD+1)²
2n
2
19

---

Provable and Practical Hypergradient Descent
Taking P II/L)/ and taking average, ER=1 lizt (P) S 1
K
and
K Ek=i hig (Px) S - 2T.
1.
+
D² + 2n
ne(LD+1)²
2 =
+ AT.
1
2n +
D
1n(LD+1)2
2 4T
With 17 S ITLD+1JER we have Do(LD+1)
17 S and
R Ek= he (Px) +
D
Using the reduction Lemma 2.4, we get, for any k 2 1 (since v, does not depend on the iteration number),
((*ht)) - [(x') S (1(xt) - f(x - 2/1 max( + D'LLLD+1) 00)**
k and there exists some Kg such that for all k 2 Kg. that (f(**) - f(xx)[(1 1 1a= - 1 since
2D* .0} =
lim 1 - 2p max 1T
- =1
This proves the first relation lim 1| - -x11 = since || 1=11=112 I 21((x)) - fl f(x)) directly from
and the second relation follows
11
x011²= = k=
Kg
1| x² 11 + > k= Ko+1 1 - x²12
(42)
Σ
Kg
||a5 x² 1|2 + kk=Kotl ko+1 - - [xx))(1 = < co.
(43)
k=
Now we are ready to prove Theorem 3.4, and we start by stating the precise definition of uniformly independent sequence.
Definition C.1 (Uniformly linearly indepdendent sequence (Conn et al., 1991)). A sequence of unit-norm vectors J. of E R", |Ig = 1 is uniformly linearly independent if there exists a constant с > 0, Ko 2 0 and m 2 n such that for each k z Ko, one can choose n distinct indices
h S ki < ... < kn S k + m
with mmin ((g
2
We prove by contradiction. For brevity we denote g ==
[ax and e := 1P% Recall that p== = [V2
V fark)
First, using Lemma C.2. for any E >> there exists some index K₁ such that for all l 2 K1 we have 1| 1 E and k= |ao x² 1|2 is bounded. Then we show that lim Vight (Pr)llr 0 using (31): after re-arrangement, for
that
00
any K > 1.
ΣK h hex)
S
2n
K Ex=
Pight (P*) + n1) P1 11
S 2y(1 nL)
2y
12g
K
| - x² x01 + 2n(1-n1) PI 11
(44)
8p
1=
< 2 nLj
2n
H2K 8y
k 30
1
1| - x=1 112 + .n P|
1I1
where (44) applies (28). Since Ex= 1|
x=' 12 is bounded and h.. (P) is nonnegative, we must have lima hag (Pt)
0. Further notice that ||Vh, (Px) < 2 (Pr). it implies lim Σk= |/ (Px) < 00, giving
limg-soe |/ (P&) r = and lim Pk- P also exists. Now suppose by contradiction that ||P p= 0.
Then there exists some K₂ > 0 such that for all & 2 K2, P pll S s. For k 2 max(Ko, K1, K2) + 1, we invoke
Lemma 3.1 with v E (0, ] to get
|| Pk+1 - 1 < Pk P*1
1 01
(P, - p*) AzE
|P P 1/ an
(Pr P P - p*)g" * 1|2 + 022
< P P' 12
2 (P - P0)) +2 (Pp - P| + a22
< PP - P*
2 (P - P')g"' 12 3a15² +02
(45)
|| P" 2
E (r( T (P TT) (P-P*) -P)) + -aae² 2 + a22,
(46)
20

---

Provable and Practical Hypergradient Descent
) > O, a2 = (2n - =n² 3 and (45) uses the fact that |P& - p*llr S
where a1
2
Telescoping (46) for the next m + iterations, we deduce that
Ch+m+1 || +1
1
Pk P. | on مド= (
Pt)) + (3are² + a2e) +)
マ ir - m  h (g ,P (P-PP) -T) (P- P*)) + (3a1e² ame) 10mm++1 +)
and using the independent sequence assumption, we can pick .i....,
......, knn such that
Tmin (lg .....
gg nrr c
and m I k (g = 1 ( 2 eT1. Hence
tr tr( g k (g )
T (P- PP) ( - P*1 = =c262
and +1+m++ ek و وº (3a 2 (m 1). Since is arbitrary, we can repeat the same argument till ex+m++1 < 0,
2 which leads to contradiction unless 0 0. This completes the proof.
D. Proof of Results in Section 4
D.1. HDM + Heavy-ball Momentum (HDM-HB)
Algorithm uses the following heavy-ball feedbackk to guide the online learning for (Pk, By):
h (P,B)
(( .²) (a)-v(aa.
[s(x)) + 1|+ - 11==>> [1?]
[+(()]]+++ 1----11-
[V -
where w >> T O, 0,
(v)()) + Bix - xT), and (< x) f(x) + + x 11 To show that online
learning can be applied hz,z (P, with regret guarantees, we need verify the convexity and Lipschitz continuity of hz,z- B) with respect to the norm defined by
IIP,, B)I =IP==
(47)
Lemma D.I. Under A1, A3, and A5, the heavy-ball feedback function hz (P,B) jointly convex in (P, B) and Lipschitz with respect to the norm defined in (47), where c == v2(1+ 22 2(1 +
Proof. Denote x (P,B) = x PV f(x) + B(x - x x)). Recall that the feedback function is
h (P, [/ [[= (P,0)) 1 (P.0)
Since x*t (P, affine in (P, and f is convex, the term f(x t (P.3)) + +% 1 (P.9) x112 jointly convex function of (P, B). The other terms in the feedback function hz (P, B) are constants, so h (P, B) also jointly convex in (P, B).
To prove the Lipschitz continuity of hr.-- B), it suffices to show that the gradients of hr (P, B) are bounded. The gradients h (P, B) with respect to P and are
V phig.a (P, B)
[- (P
[V((
1---11
V Bh (P, B) fl (P.B) w PV
)
Using the fact ||ab T
||
||a|| [lb]] the gradients have norms
V phi (P, B]] |V (P. - (P
[(()]
(48)
BBh (P, B]
(49)
21

---

Provable and Practical Hypergradient Descent
Using A1, have the Lipschitz continuity of V (x) and thus
- -7
- <|
$
x x-
(1 + LD + [D) (w --
(50)
Now, we bound the norms in (48)-(49) by the case analysis.
Case 1. - - x11 1 || f (x)] || then together with (50), we have
pax(I|Vph,.r FF, Bhz,2 [Pb)) [L+LD+
(+)))
max 2r H1 V vx())]
S max ( 22 1)((1 1.D w vED(W+L)
max max 2T 1) v2T
Case 2. If 2111 - x 11 [ then
max{|]Vph,,-- (P, (P. (P, < [[=]D+w/)]|//]]]]|+++)
max /..1]l=>
maxt / 7/2, 1 v2(1+LD+wD) 2D(w+L)
v7
- max v 2r 1) D(L +) + 2
Combining the two cases, we have
(P,))ell (P, B)IB) S max (, 1) D(L [ +1 v2T-1)
I (1 + }) + 2(1 + D + w)]
Then the gradient of ha.a- (P, under the norm defined in (47) is bounded by the constant c =: v2 + ?) + +(1 + D) +w)) w)].
The next lemma bounds the potential the last iterate x K+1 from Algorithm 2 in terms of the sum of feedback functions high a (Pk, BB).
Lemma D.2. The sequence {x*} generated from Algorithm 2 satisfies
(wtt)/((a) [(* f(x') k11 1K112 I+ maxt hag - (.),0V
(51)
where V = mmin ((x')-/(x")
Twi } and A maxxel min || - x*1|
Proof. The null step guarantees
Me -00"" x " ah upp min - (Pr, O).
22

---

Provable and Practical Hypergradient Descent
Using the initial condition x² _ have
(1* +1 xx - f(x²)
Σ
k
1
k=1 (( --=))( (art wot ()-((())) (xx),0)) f(x))
K
2/ ..k- 1/ .2k)
k=1
10 , - 1x 11 wat 1) [-](a"]]
(b f())t,)))-(a)> f(ar)
(52)
Σ
K
max(- ck. 1 ( B.).0)
V f(a++* || lank
k=1
|(aa+ x --) (sr) 10
f(z)))
V5
|1²
+ 20 -x
112
[ 8 + 1|
Then, by monotonicity,
[0
.x f (x
[(an
Ma ,2
Now we do case analysis to bound
[(((")11 1ar 11-12
(1r
102"",0 (1x0)) [(a0)) 51 2* 11 ((
Case 1. If 11100 -
- 14-1112 < f(²²) - -xxx), then
|V 311=* =11=- 12
[パ(())))<=)) 2 -.
+ - |-
where A == ma min | - -x:11-
Case 2. If 11 - 11 2 f(x²) ) - f(xx) then - 1111 2 (lf(1²) - f(xx²) and
11 + -z+ 112
- 2n 1 -मt 2 2s パ-
[(a))+ 3 1a =t 1(
since / || 2 1 < cl x - f(x²)
xx(1,20) f(x*) f(x²) - f(x²).
In both cases, we have VV E11
Mlak xt 1)- 1( > mint TA7 au )(') = )(a
where the constant V is
defined in the lemma. Finally, plugging in the definition of w, (52) gives
f(IK+1) (((")))f(())>)) + *+ - 1x 11 < T+E max{ -aax--hakk hak 1 Bc).
(arl)s(a""
The next lemma shows that there exist hindsight P, B such that Na (P, S - < 0 for some 6.
Lemma D.3. Let w = 3L and T = 16L2. Then for any x, x of X*, we have hz,z 1, 11 S sT. In particular, if
d I E Pe 1 E B, and 1k n X Ø, then
min T (P.B))XXB K
Ek hk h 8L
Proof. When P = af and B- = BT for some 3 > 0, the classical analysis for the heavy-ball momentum (Danilova et al., 2020) gives
f(xt) + الاجا 1la 1112 f(x) 1 12 : 1.
Let a 47, and 3 2, we have
f(xx) + 3L - - x < f(x) + -11 - x 1- 1 7z [V
2
-((x + //4
[V L||z x 112
=f(x) + 2 (1V
x [12]
23

---

Provable and Practical Hypergradient Descent
and re-arranging the terms, we get
f( 1- 2 -
22 1| -- 1121 S
[V((]] 4812112-2
and this completes the proof.
D.1.1. PROOF OF THEOREM 4.1
By Lemma D.I, the heavy-ball feedback is convex and Lipschitz, and thus the same proof of Lemma 2.2 guarantees that online gradient descent
(Pk+1, Bx+1) = IIxxx((Px. B&) V/ - (Px. Bx)
(with = 7/6 = =1) gives the regret bound
E -2gh (P,, BR)
7k
for some sublinear regret PK = OVVK) and the constant > as defined in Lemma D.3. Using the inequality
K E max - - (Px, Bx), 0} 2 max { Ex= - - (Pr, Bx), 03 2 max - 2k
K 0),
the desired result follows directly from (51) in Lemma D.2.
D.2. HDM + Nesterov Momentum (HDM-AGD)
D.2.1. HDM WITH NESTEROV MOMENTUM
In smooth convex optimization, accelerated gradient descent (AGD) achieves the convergence rate O ( (Nesterov, 1983):
yº x + Aeta
As
(2 - x
x x+1 = 1¹th - ((r")
(53)
N+1 2 + A 1
As f(y*),
where {Aa} pre-specified sequence. To apply HDM, we can replace the gradient descent step (53) by hypergradient descent: xx+11 n² P& (z²*) and Px+1 [Pp - ( That is. we only accelerate the gradient descent step in AGD. Algorithm 4 provides realization of the HDM-AGD based monotone variant of AGD (d' Arpremott al., 2021). The convergence of HDM-AGD is established in Theorem D.I, the proof of which is deferred to Appendix D.2.3.
Algorithm 4 HDM with Nesterov momentum
input starting point a1 ,,,,, 0, 0 1 LD), Ao for k 1, 2,... do A = (At+1 A2) g² * + (1
do+1 (z - x*)
k+1
xElv" 1. f(g ),v* ).ok f(x)
arg min
Pk+1 1Tp 1/ hy (Px)]
Uk max maxx m
-h ((2))1 20
2+1 ++1 * + (Av Aul -A Avl
v4
end
output k K+1
Theorem D.I. Assume A1 and A3. Suppose AGD starts from (x'z²) and runs for K iterations to output t. Then Algo-
rithm 4 starting from (x' 22) = (ž, 2²) and E [ LD) satisfies
f(x k(1 f(x) ) - 20 (8
4) [B=kk 2L11"'
KJ + O ))
where wk - minrer 2 EK hy (P) depends on the iteration trajectory {a* JKSK.
24

---

Provable and Practical Hypergradient Descent
The parameter 0 serves smooth interpolation between HDM and HDM-AGD: when 0 1/2, Theorem D.1 recovers the convergence rate of vanilla AGD; when 0 1/2 and w -> I.D, expect HDM-AGD yield faster convergence. As suggested by Figure 3b, HDM-AGD achieves faster convergence than AGD.
Remark 2. To mitigate the effect of regret, Algorithm needs a warm start from vanilla AGD. However, experiments suggest that is unnecessary in practice, and we leave an improved analysis to future work.
Remark 3. For strongly convex problems, we can combine Theorem D.1 with a standard restart argument (d' Aspremont et al., 2021; Roulet and d' Aspremont, 2017) and achieve a similar trajectory- based linear convergence rate.
D.2.2. AUXILIARY RESULTS
Lemma D.4. Suppose a nonnegative sequence {As} satisfies Ak+1 = (Ak+1 - As)² and Ao = O, then ARt1 - As I k+1 for all k 2
Proof. We prove by induction. The induction hypothesis is AR+1 - Aa S 1+
Base case. For k 1, A2 A
v 1 < 2 and the relation holds.
Inductive step. Suppose Ak+1 A S k. Using Agt2 A (1+ (1+ v /4Ax+1 + 1), we deduce that
Ak+2 - AR+1 = 11 + v+A++1+1 +1)
=1(1+ v4(At+1 Ax)² 2
f/(1 2(Ax+1 -Ax) +)
(54)
< 1 + Ak+1 Ak
$ k + 2,
(55)
where (54) uses va+b < Vā vb and (55) uses the induction hypothesis Ast1 Ag < k + 1. By the principle of mathematical induction, this completes the proof.
Lemma D.5 ((d' Aspremont et al., 2021)). Under the same conditions as Lemma D.4, A 2 4 for all k 2 1.
D.2.3. PROOF OF THEBREM D.I
Using the definition (P) f(v- PV f()) and the x-update in Algorithm 4:
[V
k+1
arg min
f(x),
we have the following two inequalities:
(aa+1) - 1(x²) S minn H
(56)
f(a s )(xtt).
(57)
In other words, with dy = max{ mmin (h,) (Pt)),1/(2L)) 26 }. we have
f(0)) 24
| 2 f(a+tl)
(58)
and using 1-1 zh (AR41-As) V (()"), by algebraic rearrangement
1x
1/ || k+1 - 12
(59)
2
Ex || xx + (AR11 Ac) V )(
2
24
= vs 1| x² 1|2 (Ak+1 Ac)(V[(y*)) -x*) + (Ak+1 A
(60)
25

---

S - - + PK K Provable and Practical Hypergradient Descent
Next, we apply convexity and have
f(x*) 2 + ( yr) 1(x*) /(0 (1) y²)
(61)
(62)
Taking a weighted summation between (58), (61) and (62), we deduce that
0 2 (AR+1
x² - 5²) - [(x)) An(O(o)) (VI())) - -0 - [(aa1]
+ - 200 IV )1
= -AA+1 Ac) 5²) (Ak+I - Ak)
). x² -1² - Axs(2²) + Au-1s
+
Act1
(63)
20
= =Atilf(o - --x''(((44//1111 - -f(x')
+AAHI - Av) -/²) +xx(V ),
Au+1
| [())))
(64)
20k
= - -
- - f(("))
(V(("" x= (v) -x²) +
Ac+1
[
200
= =Autil((a - - f(("))
-(As+1 (v) (*) +
A
|
(65)
20k
where (63) to (64) simply re-arrange the terms and (65) uses the identity 5² ===x x* + (1
txpl (2 - =xt)):
As
A (VI(() - w/> + As (V) - xx)) = -(Ax+1 - ([) - xz)).
Putting the relations together, we arrive at
A (1=**)+ - f(x*)] S Aclf(z")- - f(x')( + (Ak+1- Aa) 2 -x") 20k
As+1
|| (1((2)112
and adding (60) gives
Antilf(a f(x')((]]) )] + 11 xx'1
s Anl((**)) - ffxx']++ 112 - x12 +
Aut1 1011-(o [Ax A² [f((()]
20k
= Anlf(x²) - f(x")] -
- x=1
(66)
where (66) uses the relation As+1 (A - Ax)² O.
We are now ready to analyze the acceleration effect of online hypergradient. Recall that we can guarantee
(67)
where 1 == pen E hygt (P) is expected to be larger than 1/(2L) to improve performance. Recall that 7 =
wi w 20 0 and note that w/ depends on the iteration trajectory. Moreover, we have, by convexity of f(x),
L
(C-P > ((0)) [V)())
(VD [
2 -D
and 7/ S D implies wi & LDD Define I= = f1: hygh (Px) S - ] for E LD). Then, according to (67),
u px Ex K
K hy (Pk) 1 My (Px) Exer , (Ph) 2 E hyt (Pt) 8 K-1z
Using hy (Ph) 2 - D. we get
-RITTS S * Eter (P6)
Wi +
K- 7
PK
K
K
26

---

Provable and Practical Hypergradient Descent
Re-arranging the terms,
(- K
+ KI
|
S
0-wis
+
2x
L
R
Using D > L. we get
w
PK
(0 1K
(wk-00e
I
LD-OPK.
8 B-LD
LD-8
+
K
KL
We have, if & E I, that using the fact that (66) holds for un maaimmamiitaaaaaa (
L 1.
28
20-
- [(xx)) I1 - x0111 { - [(xx)) + + $ 11 - x01
(68)
On the other hand, if k & I, Us S L and
AR+1 Af f(x")] + 4 11
- x01 S Aulf(a/) - f(x*)( + y/ 11 1²2
(69)
and f(x S f(x²) implies
A A - f(x")] S 1 - f(("))
S A - f(xx)( + ([f((*)) - f(x")),
(70)
where (70) uses the condition that Ac+1 A S k from Lemma D.4.
Taking a weighted summation of (69) and (70), combining (68),
Actil((ahtt)- - f(xx(( + to2 =1= - 1*11
S An(f(=²)) - f(x*)[ + #11 =111 + (1- 2 ((f(())) f(x')) -1fk E I}
2 An[f(a")) - [(x)]]+++++]) + 1 - +1 -
- -1x)) E Z}.
Telescoping the relation from 1 to K,
Ak- Ax-1(J(zKt3)- - [(x*)] S 10 |==1 - 1=11= + EkE7(1 1 (+((t²+ [(x*))
20
Using Ak+1 2 K² from Lemma D.5 and that
[ = - [ < K (uk + LD-6
Lex
f(rk+1) - f(x*) < 18 11
L
1| - 112 + 1 (1- ExEI klf( - f(x')]
Akl1
< I ||
-xx =12 + A² - 1/) Ekez ((s(x')((*))) - -[(x))
L || x= [1 (1))(()))) -(x=)) [7]
0k
<
L || 122 + 4(1 ) -
]](1 ID- + LD- R
-
L 28
Suppose we run accelerated gradient descent from z' for K iterations and obtain x²
Plugging in f(x1) - f(x*) S 21
||' - x= 2 we get, using z1 = 2", that
R²
[1* - f(x)) < क || x= 112 + フK² || - x= 138(200 - 1)
I
J
- -
a 2|' - x'' 11 + # -
(12 1|
2|' 1
- 1)
1 + (8 ()
R² + +(())
This completes the proof.
27

---

Provable and Practical Hypergradient Descent
Table 3: Algorithm benchmark
Algorithm
Explanation
GD
Vanilla gradient descent
GD-HB (Polyak, 1964)
Gradient descent with heavy-ball momentum
AGD CBV (d' Aspremont al., 2021)
Smooth convex version of accelerated gradient
AGD-SCVX (d' Aspremont al., 2021)
Strongly convex version of accelerated gradient Adaptive momentum estimation
Adam. (Kingma, 2014)
AdaGrad (Duchi et al., 2011)
Adaptive (sub)gradien method
BFGS (Nocedal and Wright, 1999)
BFGS from scipy
L-BFGS-MAR (Nocedal and Wright, 1999)
L-BFGS with memory k from scipy (Virtanen et al., 2020)
HDM-Be Best
Practical hypergradient descent method
E. Additional Experiments
E.1. Details the Algorithms
Table 3 details the algorithms used in our experiments.
E.2. A Ablation Study HDM-Best
This section evaluates the effect of different components IDM-Best, including null-step and AdaGrad. In particular, we consider the following versions of IDM-Best
HDM Raw.
HDM-Best without null step and online gradient descent with constant stepsize is used.
HDM+Null step.
HDM-Best with null step and online gradient descent with constant stepsize is used.
HDM+Null step+AdaCrad.
HDM-Best with all the components.
a28
a38
w2a
w3a
1/7
17
10
16
HOM hall AdarCred
112
101
10-
12"
10
-DM whill
KCM will Adsoin
18"
HCM
HCA Hall Adsomn
77"
HCM
HOM
10
200
10
10
Figure 6: Ablation on different components of HDM-Best
As Figure 6 shows, both the null step and AdaGrad bring significant speedup and justify our theoretical results.
F.3. Additional Experiments on Support Vector Machine Problems
See Figure 7 and Figure
E.4. Additional Experiments on Logistic Regression Problems
See Figure 9 and Figure 10.
28

---

Provable and Practical Hypergradient Descent
a1a
a2a
a3a
34a
13-
12
10"
16
167
12
10
18.
16"
Funcion
10
10"
200
a1a
a2a
a3a
34a
Gradlent Norm
12
10'
12"
12"
10"
13
12"
200
:00
300
803
1000
12"
200
<in
660
1000
12"
600
100
1006
Fin
100
1000
lleratio
lleration
lleration
lerr ation
a5a
a6a
13
10
107
12'
12
16
10²
12"
16"
12
10.99
lteration
Iteration
Iteration
Iteratoon
12
12
16"
10"
10"
16
10"
12"
12
lleration
lleration
Ileration
lleration
a9a
sustralian scale
fourdlass scale
ijenn1
133
13*
12*
16
16'
12"
10
15"
16"
12"
12"
16"
10
10
12
12
a9a
sustralian scale
fourclass: scale
ijenn1
10
16'
12"
12"
13
12"
12
'6"
200
400
800
1000
13
200
400
600
600
1000
12"
200
400
600
600
1000
16"
300
400
6.00
600
1000
lleration
Iteration
Iteration
Iteratin
GD
AGD-CVX AGD-SCVX
Adam AdaGrad
BFGS
L-BFGS-M3
L-BFGS-M10
GD-HB
L-BFGS-M1
L-BFGS-M5
HDM-Best
Figure 7: More experiments on support vector-maching problem
29

---

Provable and Practical Hypergradient Descent
w1a
w2a
w3a
vda
137
13
16'
137
16"
16"
165
16"
16"
12"
10"
16"
16"
10"
19
200
400
1600
12
750
510
610
1760
12
270
93)
600
1000
10"75
250
033
600
lleration
lleration
Iteration
Itertionn
w1a
W33
w4a
10
12"
12"
lleration
Ileration
lteration
lleration
12
12
12
10¹
12
155
16²
16"
16"
12"
16"
16"
Iteration
Iteration
Iteration
Ileraion
wSa
w6a
W78
w8a
12
16'
16
13
12"
12"
1-"
12"
10"
12
12"
GD GD-HB
AGD-CVX AGD-SCVX
Adam
BFGS
L-BFGS-M3
L-BFGS-M10
AdaGrad
L-BFGS-M1
L-BFGS-M5
HDM-Best
Figure 8: More experiments on support vector-machin problem
30

---

Provable and Practical Hypergradient Descent
a1a
a2a
83a
94a
gap
12
16
12
18
10"
10"
16.
16"
12"
10
10"
200
200
250
a1a
a2a
a3a
34a
Gradient Norm
12"
12
16"
10
12"
13
13
12
13
12"
250
100
300
831
9000
12"
200
683
1008
12"
2000
600
1006
10"
200
400
100
900
llertion
lleratio
leretton
Her etiiiioo
120
127
13
10
13.
12"
10
13
1000
1060
lteration
Iteration
Iteration
Ieeraion
12
12
10'
72"
12"
12"
12"
12"
12"
lleration
lleration
Iteration
lleration
a9a
australian scale
fourdlass scale
ijenn1
33*
12
10'
32
19a
10
12a
16"
12"
10"
16"
16
16"
10"
T6"
10
13
12
15
a9e
australian scale scale
fourclass, scale
ijenn1
12
10'
12"
13"
10"
12"
'8"
200
400
:dc
800
1060
200
400
600
600
1000
10."
200
400
600
600
1000
16."
300
400
600
000
1000
lleration
Iteration
Iteration
Iteratin
GD
AGD-CVX AGD-SCVX
Adam
BFGS
L-BFGS-M3
L-BFGS-M10
GD-HB
AdaGrad
L-BFGS-M1
L-BGGSM5
HDM-Best
Figure 9: More experiments logistic regression problem
31

---

Provable and Practical Hypergradient Descent
w1a
w2a
W3a
wdaa
137
10
167
18
167
16"
16
12"
16
10"
16"
15
16"
10"
12"
16"
167
10
250
400
300
1000
12
750
510
610
1760
12
210
93)
600
1000
10.7
250
03)
600
lleration
lteration
Iteration
Ieertion
w1a
.33
12"
16'
10
18-
lleration
lleration
lleration
lleration
12"
10
137
12
127
12
16
16
16"
10
16
12"
16"
16"
10"
10
Iteration
Iteration
Iteration
Ilraaion
wSa
w6a
w7a
w8a
12'
10'
18*
12
12"
18*
12*
18"
10
12"
12"
GD GD-HB
AGD-CVX AGD-SCVX
Adam
BFGS
L-BFGS-M3
L-BFGS-M10
AdaGrad
L-BFGS-M1
L-BFGS-M5
HDM-Best
Figure 10: More experiments on logistic regression problem
32

---

Provable and Practical Hypergradient Descent
E.5. Experiments against Additional Benchmark Algorithms
This section compares HDM- Best with the following additional benchmark algorithms:
GD-LS. Gradient descent with Armijo line-search.
AGD-CVX-LS. Accelerated gradient descent with Armijo line-search applied to the descent step.
ADPGD. Adaptive gradient descent without descent in Malitsky and Mishchenko (2020).
ADPGDACC. ADPGD with acceleration in Malitsky and Mishchenko (2020).
Algorithm Configuration.
Line-search condition is taken be standard Armijo rule:
f(==aV((>) s f(x) a<]]V
where 10-4 and a is obtained using backtracking. Whenever the test passes without backtracking, the initial
backtracking stepsize og updated by og f- 1.20g
The Åy parameter in ADPGD is chosen within the range (0.1/L,1/L, 10/L, 10/4,,1000 100/L).
ADPGDACC uses the default heuristic parameters provided by Malitsky and Mishchenko (2020).
Results. Table 4 shows the number of problems solved by each additional benchmark algorithms. The numbers in parentheses indicate the total number of test problems. We observe that although line-search improves the convergence behavior of the baseline algorithms, the algorithms with single stepsize seem less competitive with algorithms with a diagonal preconditioner when a moderate cedderate-to-hiihee oo-hiih-accurccyy solution is needed. Our requirement [V](())l> S 10-4 (which corresponds to function value gap of 10-7 10-9) often too high for typical first-order methods.
Table Number of solved problems for additional benchmark algorithms.
Algorithm/Probeem
SVM (33)
Logistic Regression (33)
GD LS
AGD CVX LS
ADPGD
9
ADPGDACC
11
11
HDM-Best
33


Reviews:
[{"review_id": "LelGrYjoRu", "reviewer": "Reviewer_fbAc", "summary": "The paper analyzes the local and global convergence behavior of the hypergradient descent method using online learning. Underlying the analysis is interpreting hypergradient descent as doing online gradient descent on “hypergradient feedback,” a proxy loss function that measures the quality of a preconditioner. Concretely, they provide a sharpened version of a prior result due to Gao et al. (2024) which ties the difference in function value of the method’s solution versus the optimal one to the average hypergradient feedback acumulated.\n\nIn addition, the authors propose improved variants of hypergradient descent which have much more appealing empirical behavior, and conduct extensive experiments to characterize the empirical convergence behavior of the proposed methods, compared to a comprehensive set of baselines/alternative optimization methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback on our paper!\n\n**Experimental Designs Or Analyses**\n\n1. Unclear how generalizable the trends are to broader tasks\n\n   Thank you for the comment. Our paper is primarily theoretical, so the experiments are intended to test the theory; hence, we compare HDM-Best with current popular first-order adaptive methods and quasi-Newton methods. To address your curiosity about whether HDM generalizes to other tasks, note that in the past 25 years, HDM (and its variants) have been widely used (despite a lack of theoretical guarantees) and have empirically shown excellent performance in a range of tasks [1-10]. \n\n   We believe that our methodological tweaks motivated by our theoretical analysis (such as the null step) are likely to benefit these other applications as well. We also expect that our theoretical framework could also be adapted to some of these other setups (stochastic, nonsmooth, nonconvex, ...), but to do so is beyond the scope of this paper.\n\n**Relation To Broader Scientific Literature**\n\n1. More discussion on the empirical behavior of these optimizers and choice\n\n   Thanks for the comment. First, we would like to note that although we frame HDM as a standard-alone algorithm to analyze its performance, it is a plugin-type acceleration technique that is compatible with most existing optimizers. For example, HDM has demonstrated superior performance when integrated with Adam [3]. Using our analysis framework, one can develop HDM variants such as HDM-Adam.\n\n   Pertaining to HDM-Best (HDM + HB) alone, we find that for deterministic optimization problems, if $f(x)$ looks globally quadratic, then QN works well. If it does not look quadratic near the starting point, we expect HDM to be a better choice. Since smooth strongly convex functions locally look quadratic near the optimum, we might expect that the best method would switch from HDM to QN as it nears convergence.\n\n2. More discussions on the related literature \n\n   Thank you for pointing out this missing reference! We will add a more comprehensive discussion in the revision.\n\n**Other Strengths And Weaknesses**\n\n1. Dynamic regret and path-length analysis\n\n   This is a very good question. Indeed, the path-length analysis is very detailed -- not just problem-dependent but actually trajectory-dependent! -- and it is hard to fully quantify its benefits in the standard oracle access model with only first-order information.\n\n   Here is one way to understand the benefit: our path-length dependent upper bound holds for **any** path $\\\\{\\hat{P}_k\\\\}$, and in particular, it holds for the path $\\\\{\\hat{P}_k\\\\}$ that *maximizes the algorithm progress*. In other words, the algorithm achieves the performance guaranteed by the optimal path. Let's call this the \"long path\" regime.\n\n   As another example of the strength of our analysis, the bound is always at least as good as the static adaptivity result guaranteed by Theorem 3.1, since we can take $\\hat{P}_k\\equiv \\hat{P}$ (e.g., $1/L\\cdot I$). Let's call this the \"short path\" regime.\n\n   In practice, we observe that HDM's behavior can be divided into two stages: \n\n   1. When the algorithm iterates $x^k$ are far from $x^\\star$, the change in landscape is more drastic and we expect the long path regime to capture the convergence behavior. \n\n   2. When $x^k$ is near convergence,  $f(x)$ locally behaves like a quadratic, $P_k$ remains more stable and the short path regime describes the behavior.\n\n   Overall, we believe that having a trajectory dependent guarantee with a non-trivial worse-case guarantee is a powerful best-of-both-worlds result.\n\n**Other Comments Or Suggestions**\n\n1. Citation issues and typos\n\n   Thank you for pointing out the issues, we have fixed these issues.\n\n2. Lemma 2.3\n\n   Thank you for pointing this out. Using Lemma B.2, the constant here is $\\frac{1}{2}(LD+1)^2$ and we will add it in the revised version.\n\n**Questions**\n\nPlease see \"Other Strengths And Weaknesses\".\n\nWe again appreciate the constructive feedback of the reviewer and thank you for the time spent on our paper.\n\n----\n**References**\n\n[1] Schraudolph, N.N, 1999. Local gain adaptation in stochastic gradient descent.\n\n[2] Almeida, L.B. et al, 1999. Parameter adaptation in stochastic optimization.\n\n[3] Baydin, A.G. et al, 2017. Online learning rate adaptation with hypergradient descent.\n\n[4] Itakura, K. et al, 2020. Adapting the learning rate of the learning rate in hypergradient descent.\n\n[5] Chandra, K. et al, 2022. Gradient descent: The ultimate optimizer.\n\n[6] Jie, R. et al, 2022. Adaptive hierarchical hyper-gradient descent.\n\n[7] Amid, E. et al, 2022. Step-size adaptation using exponentiated gradient updates.\n\n[8] Wang, Z. et al, 2023. Fedhyper: A universal and robust learning rate scheduler for federated learning with HDM.\n\n[9] Yang, Z. & Li, X, 2024. Powered stochastic optimization with HDM for large-scale learning systems.\n\n[10] Ozkara. et al, 2024. MADA: Meta-adaptive optimizers through HDM", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I did not have time to carefully review the proofs (as they all are in the supplementary material).", "experimental_designs_or_analyses": "The experimental section is well designed (e.g. including a comprehensive list of baselines, as well as detailed loss curve plots), albeit only encompassing two classical tasks and, in that sense, unclear how generalizable the trends are to broader tasks.", "relation_to_broader_scientific_literature": "The paper is well related to the online learning and optimization literatures, by employing online learning tools and applying them to study the convergence behavior of an optimization method that has nice intuition behind it and potential for empirical appeal as an option to other popular optimizers currently used (AdaGrad, Adam, BFGS, etc.). Possibly more discussion could be included on observed empirical behavior of these optimizers, as well as systems-related reasons for choosing one versus the other. (One somewhat relevant example of could be Disentangling adaptive gradient methods from learning rates by Agarwal et al. 2020.)", "essential_references_not_discussed": "I think more references should be added in the very beginning following the remark that the choice of stepsize affects the performance. One example could be the paper mentioned above, Disentangling adaptive gradient methods from learning rates by Agarwal et al. 2020.", "other_strengths_and_weaknesses": "I appreciate the intuition given on exactly what the method is doing and how that plays into the analysis and the interpretation of the loss blow-up during the “warm-up” phase. \n\nOne area of improvement in my opinion is that I believe more discussion and nuance are needed for the analysis of the local behavior. Currently the authors simply say that the preconditioner is chosen “to adapt to the local region, at the price of an additional regret term” that corresponds to the path length. The reason I believe more nuance is needed is that a priori it is not clear how big one should expect this path length to be, and that would determine the quality of the adaptation. So, without further analysis of why or when we’d expect this to be small (which a priori I don’t fully see why it would necessarily be), it is not clear that the analysis fully satisfactorily characterizes the local behavior.", "other_comments_or_suggestions": "Throughout, citations with parentheses are used incorrectly. For example in line 19 in the abstract rather than “the framework of (Gao et al., 2024)” it should be “the framework of Gao et al. (2024).” This can be adapted by a change of the citing command (e.g. from \\cite to \\citep or something of the sort). Further examples include line 30 right hand column,  line 76 right hand side (change to “due to Gao et al., (2024)), line 106 right hand side, and line 115 left hand side.\n\nI think in line 48, right hand column, you mean to say “UNexperienced users”?\n\nIn Lemma 2.3 you use the big O notation, but nowhere else I think — for consistency maybe put in the constants here too?", "questions_for_authors": "Could you comment more on the local convergence guarantee and when/why we can expect the path length contribution to be innocuous?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5mDAsKA9Wa", "reviewer": "Reviewer_DNfY", "summary": "This paper presents the first rigorous convergence analysis of the hypergradient descent method (HDM), a technique for adaptive stepsize selection in optimization that has been used heuristically for 25 years. The authors develop a theoretical framework based on online learning to analyze HDM's convergence properties and create improved variants with momentum. Their analysis shows that HDM exhibits several desirable properties: it automatically adapts to the local optimization landscape, achieves local superlinear convergence for strongly convex problems, and learns the inverse Hessian at the optimum. The authors identify reasons for HDM's previously reported instability and propose solutions including null steps and improved online learning algorithms. They develop two momentum-based variants: HDM with heavy-ball momentum (HDM-HB) and HDM with Nesterov momentum (HDM-AGD). Their best practical variant, HDM-Best, combines diagonal preconditioners, heavy-ball momentum, and AdaGrad updates. Experiments on deterministic convex problems show that HDM-Best outperforms other adaptive first-order methods and often matches L-BFGS with less memory usage.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback on our paper.\n\n**Questions**\n\n1. Extension to the stochastic setting\n\n   This is a very good question. One major bottleneck in extending HDM to the stochastic case is that the hypergradient feedback can be corrupted by noise, especially the gradient norm denominator of the feedback, which can only be estimated using random samples. However, in some easier settings, such as over-parametrized and finite-sum problems, we still expect HDM to work.\n\n2. Memory usage of HDM-Best and more clarification\n\n   Thanks for raising this point. As we mentioned in the Experiment setup (Line 333) and in Appendix A, for an optimization problem with variable dimension $n$, HDM-Best uses $\\mathcal{O}(7 n)$ memory while L-BFGS with memory size $m$ uses $\\mathcal{O}((5 + 2m) n)$ memory. Hence for large-scale problems, HDM has comparable memory usage compared to L-BFGS with memory size 1, and in practice, HDM-Best often has competitive performance with L-BFGS-5 or L-BFGS-10. Therefore, we expect HDM to be useful in memory-intensive nonlinear optimization tasks.\n\n3. Stability-enhancing techniques other than null step\n\n   Our current theoretical analysis requires a null step to work, but in practice, we observe that after a good preconditioner is learned, the null step is rarely triggered. It is generally safe to turn it off after monotonicity is observed for many iterations. Trust-region methods might be useful to extend HDM to nonconvex optimization, but the trust region methods are generally not worthwhile for large-scale convex optimization, as the trust region subproblem is too expensive to solve the subproblem.\n\n4. Hybrid approach of HDM and quasi-Newton\n\n   This is an interesting idea. Yes, theoretically, when the iterate $x^k$ is far from optimality and Hessian does not behave stably, it's more favorable to use HDM since it still has guarantees with respect to a high-quality preconditioner. When $x^k$ is near $x^\\star$, using secant equations more efficiently captures the local curvature around the optimal solution, and quasi-Newton methods can be more suitable locally. As with incorporating the secant equation into HDM update, we feel it's an interesting future direction worth exploring.\n\n5. Difference between performance on SVM and logistic regression\n\n   The smoothed SVM problems we use take the simple form $\\\\|[A x- b]_+\\\\|^2$ and is friendly to first-order methods. For the logistic regression problem, we observe that typically $x^\\star$ can have a very large norm, and the Hessian around the optimal solution does not have strong curvature. Therefore, we find first-order methods slow down on these problems.\n\nThank you for the time spent in the review process.", "claims_and_evidence": "The claims in the paper are generally well-supported by theoretical analysis and experimental evidence:\n\n1. Convergence properties of HDM: The authors provide clear theoretical results analyzing both global convergence (Theorems 1 and 2) and local superlinear convergence (Theorem 3). The analysis explains how HDM adapts to the local landscape and why it can achieve superlinear convergence for strongly convex problems.\n2. Understanding HDM's instability: The paper convincingly explains why vanilla HDM can appear unstable in early iterations and proposes effective solutions through null steps and improved online learning algorithms. Figure 1 provides visual evidence of this instability and how their solutions address it.\n3. HDM learns the inverse Hessian: Theorem 5 and Lemma 3 provide solid theoretical support for the claim that HDM converges to the inverse Hessian at the optimum, connecting it to quasi-Newton methods.\n4. Momentum-based variants: The authors develop and analyze HDM-HB (Algorithm 2) and HDM-AGD (Algorithm 3), providing convergence guarantees for both in Theorems 4 and 6.\n5. Practical performance: The experimental results in Section 6 support the claim that HDM-Best outperforms other adaptive first-order methods and competes with L-BFGS. Table 1 shows HDM-Best solves 32/33 SVM problems and 21/33 logistic regression problems, similar to L-BFGS-M10 and BFGS.\n\nThe evidence is convincing for convex optimization problems. The authors are appropriately cautious about generalizing their results beyond this context.", "methods_and_evaluation_criteria": "The methods and evaluation criteria are appropriate and well-designed for the problem:\n\n1. The theoretical analysis uses online learning tools to provide sharp convergence bounds for HDM and its variants. This approach is novel for analyzing HDM and yields insights about its behavior.\n2. The experimental evaluation uses standard benchmark datasets from LIBSVM for two common convex optimization problems: support vector machines and logistic regression.\n3. The comparison algorithms represent a comprehensive set of optimization methods, including standard gradient descent, momentum methods, adaptive methods (Adam, AdaGrad), and quasi-Newton methods (BFGS, L-BFGS).\n4. The evaluation metrics (number of solved problems, function value gap, gradient norm) are standard and appropriate for assessing optimization algorithm performance.\n5. The experimental setup is clearly described with appropriate details about algorithm configuration, stopping criteria, and maximum oracle access. This enables reproducibility and fair comparison.\n\nThe only potential limitation is that the evaluation focuses solely on deterministic convex problems, whereas the original motivation for HDM included stochastic optimization. However, the authors make this focus clear, and the insights gained should still be valuable for broader applications.", "theoretical_claims": "The theoretical claims in the paper appear correct and are supported by detailed proofs:\n\n1. Static adaptivity (Theorem 1): This result builds on the online learning framework and shows how HDM's convergence rate depends on the trajectory-dependent term γ_K^* reflecting the local landscape.\n2. Dynamic adaptivity (Theorem 2): This extends the analysis to show HDM can adapt to different regions of the landscape, using dynamic regret concepts from online learning.\n3. Local superlinear convergence (Theorem 3): This result establishes the superlinear convergence of HDM near the optimum for strongly convex problems with Lipschitz Hessian, explaining the fast convergence observed in practice.\n4. Convergence of the preconditioner (Theorem 5): This result shows HDM learns the inverse Hessian at the optimum under appropriate conditions.\n5. Convergence guarantees for HDM-HB (Theorem 4) and HDM-AGD (Theorem 6): These extend the analysis to the momentum-based variants.\n\nThe proofs use techniques from online learning theory, convex optimization, and analysis of first-order methods. The assumptions are standard in the optimization literature (smoothness, convexity, Lipschitz Hessian) and appropriately specified throughout the paper.", "experimental_designs_or_analyses": "The experimental design is sound and the analyses are valid:\n\n1. The experiments use a diverse set of 33 benchmark datasets from LIBSVM for both SVM and logistic regression problems, providing a robust test of algorithm performance.\n2. The algorithm comparison is comprehensive, including multiple variants of gradient descent, momentum methods, adaptive methods, and quasi-Newton methods.\n3. The hyperparameter selection process is clearly described, with reasonable ranges for each algorithm.\n4. The evaluation metrics (function value gap and gradient norm) are plotted against the number of gradient evaluations, providing a fair comparison of computational efficiency.\n5. Table 1 provides a summary of algorithm performance across all test problems, while Figures 3 and 4 show detailed convergence plots for representative examples.\n\nThe experimental results align with the theoretical findings, showing that HDM-Best achieves faster convergence than other adaptive first-order methods and often matches L-BFGS. The authors' claim that HDM-Best uses less memory than comparable L-BFGS variants is supported by their description of the algorithm.", "relation_to_broader_scientific_literature": "The paper effectively situates its contributions within the broader scientific literature:\n\n1. It connects to the extensive literature on adaptive first-order methods, including AdaGrad, Adam, and parameter-free stepsizes, providing a theoretical foundation for a different approach to adaptation.\n2. It builds on the history of hypergradient descent, tracing its origins to Almeida (1999) and its rediscovery by Gunes (2018), while advancing beyond previous analyses by Rubio (2017), Kunstner (2024), and Gao (2024).\n3. It establishes connections between HDM and quasi-Newton methods, showing both theoretical similarities (learning the inverse Hessian) and practical differences (how they measure and update the preconditioner).\n4. It applies ideas from online learning theory to analyze offline optimization algorithms, following recent work that has demonstrated the power of this approach.\n\nThe authors appropriately credit prior work and clearly delineate their novel contributions, particularly the rigorous convergence analysis and the development of momentum-based variants.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "No", "other_comments_or_suggestions": "No", "questions_for_authors": "1. Your analysis focuses on deterministic convex optimization, but HDM was originally proposed for stochastic optimization. Do you expect your theoretical results to extend to the stochastic setting, and what modifications would be necessary? Would the instability issues be more or less severe with stochastic gradients?\n2. You mention that HDM-Best uses approximately the same memory as L-BFGS-M1 but often matches the performance of L-BFGS-M5 or L-BFGS-M10. Could you elaborate on the memory requirements of HDM-Best compared to L-BFGS variants more precisely, and clarify the trade-offs?\n3. The null step approach requires an additional function evaluation at each iteration. Have you explored alternative stability-enhancing approaches that avoid this extra cost? For instance, would trust-region approaches be applicable here?\n4. Your theoretical analysis reveals connections between HDM and quasi-Newton methods. Have you explored hybrid approaches that combine insights from both methods? For example, could one incorporate secant conditions into the preconditioner updates of HDM?\n5. The experimental results show that HDM-Best performs better on SVM problems (32/33 solved) than on logistic regression problems (21/33 solved). Do you have insights into why this performance difference exists? Are there particular problem characteristics that make HDM more effective?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vg8HLAuA84", "reviewer": "Reviewer_htFv", "summary": "In this paper, the authors study the hypergradient descent method for smooth convex optimization, where the preconditioner is updated using online gradient descent. Building on the online learning framework of (Gao et al., 2024), they prove sublinear and linear convergence rates in the convex and strongly-convex settings, respectively. Under additional assumptions, they further prove local superlinear convergence and show that the preconditioner converges to the Hessian at the optimum. The authors also analyze two momentum variants, where both the preconditioner and the momentum parameter are updated via online gradient descent. Finally, they develop a practical variant and demonstrate that it performs comparably to L-BFGS while requiring less memory.\n\n## Update after rebuttal\nDuring the rebuttal, the authors conducted additional experiments to include suggested baselines, such as GD/AGD with line search and the adaptive gradient method of [MM 2020]. The proposed method continues to outperform these baselines, which further validates its empirical efficiency.  \n\nHowever, I remain on the fence regarding acceptance. On the theoretical side, the superlinear convergence guarantees apply only to the full-matrix version of the algorithm, which differs from the diagonal version used in the experiments. This discrepancy makes me somewhat cautious about the strength of the theoretical claims and their alignment with the empirical results. On the experimental side, the case would be more compelling if the authors included additional large-scale experiments in stochastic, non-convex settings.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and insightful comments. Below are our responses to your two major concerns and other comments. If we have addressed your concerns, we kindly request a re-evaluation of the score, and please let us know if you have further questions.\n\n**Major concerns (\"Questions\")**\n\n1. Numerical comparison\n\n   We added the suggested experiments to https://anonymous.4open.science/r/hypergrad-00CB, including line-search GD/AGD and [YK2020]. On the benchmark data, line-search improves the performance of GD/AGD, but neither suffices to achieve $10^{-4}$ gradient norm tolerance. Please see `add_exp.pdf` for more details.\n\n2. htFv worries our theory is not particularly strong and shows no clear advantage over GD with line search\n\n   We politely disagree that there is no clear advantage w.r.t. line search GD. \n\n   Consider an ill-conditioned diagonal quadratic objective. Even with exact line-search, GD can converge arbitrarily slowly on this problem [1]. HDM does not! Rather, its diagonal version converges superlinearly. In the revision, we will use this example to demonstrate the advantage of HDM over GD with line-search, and more generally, the strength of our theory, which provides\n\n   - the first rigorous guarantee for HDM with matching empirical performance. \n   - a proof HDM achieves superlinear convergence with only first-order information. The first family of first-order algorithms with superlinear convergence, discovered in 1959, is quasi-Newton, which uses secant equations to approximate second-order curvature. Our paper discovers the second such family!\n   - novel proof techniques that show acceleration either 1) when a convex Lyapunov function is available (like HB) or 2) when the descent lemma is used in the analysis (like AGD). \n   - momentum extensions that perform better than any baseline algorithm (fixing the same memory budget).\n\n   Our work lays a foundation for future research, and we believe these contributions together are strong enough for a conference submission.\n\n**Claims And Evidence**\n\n1. Path-length argument and adaptivity to the local landscape\n\n   Thanks for your insightful comment! In a word, the path-length argument unifies HDM's behavior when far from/near the optimum without complicating the analysis. This is a novel best-of-both-worlds guarantee for an optimization algorithm.\n\n   Due to space limit, we kindly refer the reviewer to our response to Reviewer fbAc Other Strengths And Weaknesses at https://openreview.net/forum?id=NkVCB1Cpgl&noteId=2xn5Z6a9Xd. \n\n2. Require $\\nabla f(x^\\star)^{-1}\\in\\mathcal{P}$\n\n   You are correct that our superlinear convergence result requires this assumption; we'll clarify it in the revision. \n   However, all other non-second-order methods achieving superlinear convergence (the quasi-Newton (QN) family) also store an n x n preconditioner.\n   Moreover, HDM can achieve linear convergence competitive with the best possible preconditioner even if $\\nabla f(x^\\star)^{-1}\\not\\in\\mathcal{P}$, while QN has no such guarantee.\n\n**Experimental Designs/Analyses**\n\nPlease see our response to Major concerns.\n\n**Essential References Not Discussed**\n\nThanks for these refs! We have added them to the revision.\n\n**Other Strengths And Weaknesses**\n\n1. Similarity to [Gao2024]\n\n   Our paper builds on [Gao2024], and we restate Thm 3.1 for completeness, although it's a slightly refined version. Our dynamic regret perspective (Thm 3.2) offers new insights beyond [Gao2024], bounding regret w.r.t the best preconditioner **sequence** (see Claims And Evidence). The analysis is simple, but it *captures what HDM is doing* without complicated analysis and provides new insights. We believe this type of result is valuable.\n\n2. Weakness of HDM-HB/HDM-AGD\n\n   Since HDM works by preconditioning, it improves the *problem-dependent constant* instead of the *convergence rate*. Hence, HDM-HB/HDM-AGD inherits the same rate of HB/AGD but gives improved constants:\n\n   - HDM-HB's constant is determined by hindsight w.r.t $h_x(P,\\beta)$, which can be much smaller than $h_x(P)$.\n\n   - HDM-AGD does not improve and requires a warmstart. \n\n     It's true; but HDM-AGD can improve the constant hidden by the big-O! e.g., run AGD for $K$ iterations. If $\\sum_{k=1}^K h_{x^k}(P)/K\\ll-1/(2L)$ (as always holds in our experiments), then K iters of HDM-AGD (with the AGD warmstart) can outperform $K$ more iters of AGD.\n\n**Other Comments**\n\n1. Dimension dependence\n\n   We'll discuss it in the revision.\n\n2. Could a small loss bound argument provide constant regret guarantee and so faster convergence?\n\n   Alas no: this argument requires a global lower bound on $h_x$ which is not known for general convex problems, though possibly a refinement of the argument might work.\n\n3. Notation\n\n   Thanks! We have fixed these issues.\n\nWe again thank you for your time in the review process! Please let us know if you have further questions.\n\n**Reference**\n\n[1] Saad, Y. (03). Iterative methods for sparse linear systems.", "claims_and_evidence": "Overall, most of the claims in the paper are well supported by theorems and their proofs. That said, I have some reservations regarding certain statements: \n- In Section 3.1, the authors claim that HDM can adapt to the local optimization landscape since the choice of $P\\_K^\\*$ in Theorem 3.1 or $\\\\{\\hat{P}\\_k\\\\}$ in Theorem 3.2 only depends on the past trajectory $\\\\{x^k\\\\}_{k \\leq K}$. However, this argument appears somewhat imprecise. From my understanding, there is no guarantee that the iterates of HDM will remain confined to a local region. Given that the initial point is typically far from the optimal solution, the iterates may traverse a large region of space before converging. As such, the convergence bound likely still depends on the global properties of the objective function rather than solely on its local behavior. \n- In Section 3.3, the authors establish that HDM achieves local superlinear convergence and learns the Hessian at the optimum. However, these results rely on the crucial assumption that $[\\nabla^2 f(x^*)]^{-1} \\in \\mathcal{P}$, which is unlikely to hold when $\\mathcal{P}$ is the set of diagonal matrices, as considered in the numerical experiments. This mismatch between the theoretical assumptions and practical implementation should be better clarified.", "methods_and_evaluation_criteria": "Yes, the hypergradient descent method is a common heuristic for hyperparameter selection, and LIBSVM is also a common benchmark dataset for deterministic convex problems.", "theoretical_claims": "Yes, I checked most of the proofs in the appendix and they appear correct, except for some typos (specified in \"Other Comments Or Suggestions\").", "experimental_designs_or_analyses": "I have some concerns regarding the choice of baselines in the numerical experiments. \n- It appears that the authors use a grid search to find the optimal $\\eta_p$ for HDM-Best but employ a fixed step size for GD, GD-HB, AGD-CVX, and SGD-SCVX. This seems unfair, as all the algorithms should receive the same level of tuning. To ensure a fair comparison, the authors should also conduct a grid search for the step size of the other methods. \n- Additionally, I think it is important to consider GD, GD-HB, AGD-CVX, and SGD-SCVX with the classical backtracking line search. Notably, the use of a null step in HDM-Best resembles a line search procedure, where the step size is reduced until the function value decreases sufficiently. Since both rely on function evaluations to adjust the step size, these line-search-based methods should also be included as baselines.   \n- Another relevant baseline is the adaptive gradient method proposed by Malitsky and Mishchenko (2020; 2024). As further detailed in \"Essential References Not Discussed\", their algorithm is also designed to adaptively select the step size for gradient descent in deterministic convex optimization problems. Including this method in the comparison would strengthen the evaluation. \n---\n\nMalitsky, Y., & Mishchenko, K (2020). Adaptive Gradient Descent without Descent. ICML 2020. \n\nMalitsky, Y., & Mishchenko, K (2024). Adaptive proximal gradient method for convex optimization. NeurIPS 2024.", "relation_to_broader_scientific_literature": "This paper analyzes the convergence properties of hypergradient descent and its extensions, a strategy for adaptively selecting the step size.\n\n- The most relevant prior work is Gao et al. (2024), which also employs an online learning framework with hypergradient feedback to analyze hypergradient descent methods. The main additional contributions of this paper are the local superlinear convergence analysis and the introduction of two momentum-based variants. \n\n- Other adaptive step-size selection strategies include line-search-based methods, AdaGrad, and the adaptive gradient method proposed by Malitsky and Mishchenko (2020; 2024). These approaches provide alternative ways to adjust step sizes dynamically based on problem-dependent quantities.\n\n- In terms of methodology, this paper selects the step size by formulating an online learning problem and applying online gradient descent. In this sense, their framework is similar to that of Zhuang et al. (2019), where the authors address stochastic non-convex optimization and adapt the step size by running an online learning algorithm on a surrogate loss. Additionally, the propose framework is related to Jiang et al. (2023), which proposes learning a Hessian approximation matrix in an online manner rather than a preconditioner.\n\n----\n\nMalitsky, Y., & Mishchenko, K (2020). Adaptive Gradient Descent without Descent. ICML 2020. \n\nMalitsky, Y., & Mishchenko, K (2024). Adaptive proximal gradient method for convex optimization. NeurIPS 2024.\n\nZhuang, Z., Cutkosky, A., & Orabona, F. (2019). Surrogate losses for online learning of stepsizes in stochastic non-convex optimization. ICML 2019.\n\nJiang, R., Jin, Q., & Mokhtari, A. (2023). Online learning guided curvature approximation: A quasi-Newton method with global non-asymptotic superlinear convergence. COLT 2023.", "essential_references_not_discussed": "I suggest that the authors to include a more detailed discussion and comparison with the adaptive gradient method by Malitsky and Mishchenko (2020; 2024), which introduces a step-size selection strategy based on observed gradient differences. Moreover, it is worth mentioning the works of Zhuang et al. (2019) and Jiang et al. (2023), both of which employ an online learning framework to adaptively update hyperparameters in optimization algorithms, such as the step size and Hessian approximation matrix.\n\nThat said, I would like to note that these references do not diminish the contributions of this work.", "other_strengths_and_weaknesses": "Another concern is that the theoretical results are not particularly strong. \n- Theorem 3.1 appears to be nearly identical to Theorem 6.1 in Gao et al. (2024). The only difference is that the bound in (A1) also takes the minimum with $\\phi(x^1)$, which follows directly from the definition of null steps. While Theorem 3.2 is new, its proof largely follows the same strategy as Theorem 3.1, relying on a standard application of the dynamic regret argument.\n- As mentioned earlier, while the authors establish local superlinear convergence, this result hinges on the assumption that $[\\nabla^2 f(x^*)]^{-1} \\in \\mathcal{P}$. Thus, it may not be applicable when $\\mathcal{P}$ is the set of diagonal matrices, which are the main focus of the paper. \n- For HDM with heavy-ball momentum, Theorem 4.1 does not demonstrate an improved convergence rate compared to vanilla HDM in Theorem 3.1. Moreover, for HDM with Nesterov momentum, while Theorem 4.2 seemingly establishes a faster rate of $O(1/K^2)$, this result actually requires the initial suboptimality gap to be already in the order of $O(1/K^2)$, as discussed in Theorem D.1. This limitation diminishes its significance.", "other_comments_or_suggestions": "- Most of the convergence results in this paper depend on the diameter of the set $\\mathcal{P}$ defined in **A3**. However, note that this quantity can scale with the problem dimension $d$. Thus, it would be better to make this dimensional dependence more explicit. \n- In Theorem 3.1, the authors follow the standard analysis of online gradient descent, which achieves a regret bound of $\\rho_K= D(LD+1)\\sqrt{K}$ in the given setting. However, since $h_x(P)$ is known to be $L$-smooth from Lemma 2.1, it may be possible to leverage a small-loss bound to establish a constant regret independent of the time horizon. Would this alternative approach lead to a better convergence bound?\n\nMinor suggestions: \n- Some of the notations are not clearly defined, leading to potential confusion. For instance, $h_x(\\alpha)$ and $h_x(d)$ in Lemma 2.1 are not properly introduced. Moreover, $\\rho_K$ is used throughout the paper, but it is only defined in (5), where it is not particularly prominent (I initially overlooked it on my first read).", "questions_for_authors": "To summarize, my concerns are two-fold: \n- The numerical comparison omits important baseline methods and does not properly tune their step sizes. As a result, it remains unclear whether the proposed method truly outperforms existing approaches.\n- The theoretical results are not particularly strong. In particular, they do not demonstrate a clear advantage over standard methods such as gradient descent with line search.\n\nI am willing to raise my score if these two issues are properly addressed.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hRvaPXI6lf", "reviewer": "Reviewer_mYzg", "summary": "The authors addressed the challenge of establishing convergence of the hypergradient descent heuristic in this submission. They provided the first rigorous theoretical foundation for hypergradient descent and introduce a novel online learning perspective that extends to other first-order methods with adaptive hyperparameter updates. They also proposed HDM-Best, an efficient variant of HDM that performs competitively with the widely used L-BFGS method on convex problems. They also conduct numerical experiments and the empirical results are consistent with the theoretical analysis.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback on our paper and for acknowledging the contribution of our results!\n\n**Essential References Not Discussed**\n\nThank you for pointing out these references. We will thoroughly discuss the superlinear convergence results in the revised version. Here, we give a brief comparison with the existing results in terms of the superlinear convergence rate, where for HDM we plug in $\\rho_K = \\mathcal{O}(\\sqrt{K})$ and get $\\mathcal{O}((\\frac{1}{\\sqrt{K}})^K)$ convergence.\n\n| Paper |       Superlinear convergence rate       |\n| :---: | :--------------------------------------: |\n|  [1]  |    $\\mathcal{O}(e^{-\\frac{1}{2}K^2})$    |\n|  [2]  | $\\mathcal{O}(e^{-\\frac{1}{2} K \\log K})$ |\n|  [3]  | $\\mathcal{O}(e^{-\\frac{1}{2}K \\log K})$  |\n|  [4]  | $\\mathcal{O}(e^{-\\frac{1}{2}K \\log K})$  |\n|  [5]  |       $\\mathcal{O}(e^{-K \\log K})$       |\n|  [6]  |       $\\mathcal{O}(e^{-K \\log K})$       |\n|  HDM  | $\\mathcal{O}(e^{-\\frac{1}{2} K \\log K})$ |\n\nConvergence rate in terms of $K$ is discussed since these references uses different notation for the problem-dependent constants and convergence metric, but in the revised version of the paper we will choose a unified notation and compare them, with problem-dependent constants.\n\nWe again appreciate the constructive feedback of the reviewer and thank you for the time spent on our paper!\n\n**References**\n\n[1] Rodomanov, A., & Nesterov, Y. (2021). Greedy quasi-Newton methods with explicit superlinear convergence. *SIAM Journal on Optimization, 31*(1), 785–811. \n\n[2] Rodomanov, A., & Nesterov, Y. (2021). Rates of superlinear convergence for classical quasi-Newton methods. *Mathematical Programming*.\n\n[3] Rodomanov, A., & Nesterov, Y. (2021). New results on superlinear convergence of classical quasi-Newton methods. *Journal of Optimization Theory and Applications, 188*, 744–769.\n\n[4] Jin, Q., & Mokhtari, A. (2021). Non-asymptotic superlinear convergence of standard quasi-Newton methods. arXiv preprint arXiv:2003.13607.\n\n[5] Jin, Q., Jiang, R., & Mokhtari, A. (2025). Non-asymptotic global convergence analysis of BFGS with the Armijo-Wolfe line search. arXiv preprint arXiv:2404.16731.\n\n[6] Jin, Q., Jiang, R., & Mokhtari, A. (2024). Non-asymptotic global convergence rates of BFGS with exact line search. arXiv preprint arXiv:2404.01267.", "claims_and_evidence": "The claims in this submission are supported by both theoretical proof and numerical experiments.", "methods_and_evaluation_criteria": "The methods from theoretical analysis and benchmark datasets from empirical results make sense for the convergence analysis of the Hypergradient Descent method.", "theoretical_claims": "The proof of the theatrical claims shown in the appendix is correct after checking", "experimental_designs_or_analyses": "The empirical results shown in the numerical experiments are valid after checking.", "relation_to_broader_scientific_literature": "All the related works discussed in the section 1.1 are closely related to the contributions of this submission.", "essential_references_not_discussed": "The following are the newest results about the superliner convergence rates of the quasi-Newton methods and I suggest that the authors should refer these works and compare the superliner convergence rates of the Hypergradient Descent in Theorem 3.3 with all these rates:\n\nhttps://arxiv.org/abs/2002.00657\n\nhttps://arxiv.org/abs/2003.09174\n\nhttps://arxiv.org/abs/2004.14866\n\nhttps://arxiv.org/abs/2003.13607\n\nhttps://arxiv.org/abs/2404.16731\n\nhttps://arxiv.org/abs/2404.01267", "other_strengths_and_weaknesses": "This paper is a high-quality optimization theory submission where the authors proved the first rigorous convergence analysis for\nHDM, including both global and local convergence guarantees. They developed and analyze two improved variants of HDM:\nHDM + heavy-ball momentum and HDM + Nesterov momentum. They provided all the mathematical proof and the emprical results from the numerical experiments are consistent with the theoretical results. This submission deserves a publication for ICML.", "other_comments_or_suggestions": "Please compare the superliner convergence rates of the Hypergradient Descent in Theorem 3.3 with the latest non-asymptotic superlinear convergence rates of the quasi-Newton methods listed in the essential references not discussed section.", "questions_for_authors": "No other questions", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents a rigorous theoretical analysis of the hypergradient descent method (HDM) for optimization, including both global and local convergence guarantees. The work provides comprehensive theoretical foundation for HDM, which has been used heuristically for 25 years, and introduces novel momentum-based variants with improved practical performance.

The paper's primary strengths include its theoretical analysis, which establishes explicit non-asymptotic bounds for both global and local convergence. The authors develop an online learning perspective that yields insights into HDM's behavior and extends to other first-order methods with adaptive hyperparameter updates. The practical variant HDM-Best demonstrates competitive performance with L-BFGS while using less memory, supported by empirical evaluation.

During the review process, some concerns were raised about theoretical aspects and experimental validation. In response, the authors:

- Added experiments comparing against line-search GD/AGD and other adaptive methods.
- Clarified the theoretical contributions, particularly emphasizing HDM as only the second known family of first-order methods achieving superlinear convergence.
- Provided explanations of the path-length analysis and its unification of HDM's behavior both far from and near the optimum.
- Added comparisons with recent results on superlinear convergence rates of quasi-Newton methods.

While one reviewer remained concerned about the alignment between theoretical results (which assume full-matrix preconditioners) and practical implementation (using diagonal preconditioners), the overall consensus is that the paper makes valuable contributions to both theory and practice of optimization methods.

The paper would benefit from:

1. More explicit discussion of dimensional dependencies in the theoretical bounds
2. Clearer exposition of the tradeoffs between diagonal and full-matrix variants
3. Additional discussion of the practical implications of theoretical assumptions
Decision: Accept (poster)