Nesterov Finds GRAAL: Optimal and Adaptive Gradient Method for Convex Optimization
Authors: Ekaterina Borodich
Dmitry Kovalev
Venue: ICLR 2026 Poster (2026)
Keywords: convex optimization
adaptive optimization
gradient methods
accelerated methods
Primary area: optimization

Abstract: In this paper, we focus on the problem of minimizing a continuously differentiable convex objective function, $\min_x f(x)$. Recently, Malitsky (2020); Alacaoglu et al. (2023) developed an adaptive first-order method, GRAAL. This algorithm computes stepsizes by estimating the local curvature of the objective function without any line search procedures or hyperparameter tuning, and attains the standard iteration complexity $\mathcal{O}(L\Vert x_0-x^* \Vert^2/\epsilon)$ of fixed-stepsize gradient descent for $L$-smooth functions. However, a natural question arises: is it possible to accelerate the convergence of GRAAL to match the optimal complexity $\mathcal{O}(\sqrt{L\Vert x_0-x^*\Vert^2/\epsilon})$ of the accelerated gradient descent of Nesterov (1983)? Although some attempts have been made by Li and Lan (2025); Suh and Ma (2025), the ability of existing accelerated algorithms to adapt to the local curvature of the objective function is highly limited. We resolve this issue and develop GRAAL with Nesterov acceleration, which can adapt its stepsize to the local curvature at a geometric, or linear, rate just like non-accelerated GRAAL. We demonstrate the adaptive capabilities of our algorithm by proving that it achieves near-optimal iteration complexities for $L$-smooth functions, as well as under a more general $(L_0,L_1)$-smoothness assumption (Zhang et al., 2019).

Published as a conference paper at ICLR 2026
NESTEROV FINDS GRAAL: OPTIMAL AND ADAPTIVE GRADIENT METHOD FOR CONVEX OPTIMIZATION
Ekaterina Borodich
Dmitry Kovalev Yandex Research
Higher School of Economics; Yandex Research borodi ch. ed@phystech. edu
dakovalev1 com
ABSTRACT
In this paper, we focus on the problem of minimizing a continuously differen- tiable convex objective function, min, f(z). Recently MMlitsky (2020); Ala- caoglu et al. (2023) developed an adaptive first-order method, GRAAL This algorithm computes stepsizes by estimating the local curvature of the objective function without any line search procedures or hyperparameter tuning, and attains the standard iteration complexity (L - x=12 1 /c) of fixed-stepsize gradient descent for L-smooth functions. However, a natural question arises: is it pos- sible to accelerate convergence of GRAAL match the optimal complexity
OLVLl - x ll of the accelerated gradient descent of Nesterov )983)? Al- though some attempts have been made by Li & Lan (2025); Suh & Ma (2025). ), the ability of existing accelerated algorithms to adapt to the local curvature of the objective function is highly limited. We resolve this issue and develop GRAAL with Nesterov acceleration, which can adapt its stepsize to the local curvature at geometric, or linear, rate just like non-accelerated GRAAL. We demonstrate the adaptive capabilities of our algorithm by proving that it achieves near-optimal iteration complexities for L-smooth functions, well as under more general (Lo. -mmooohtssssss assumption (Zhang et al. (019).
INTRODUCTION
First-order, or gradient, optmizatiion methods are highly popular in many practical applications due their simplicity and scalability. However, the key limitation of these methods is that they require the choice of the stepsize parameter. In this paper, we focus on developing efficient gradient methods that can adjust the stepsize at each iteration an adaptive manner. Formally speaking, we consider the following optimization problem:
min f(x). xER4
(1)
where Rd is finite-dimensional Fuclidean space, and f(x): Rdd differentiable objective function. We assume that problem has a solution x" E IRd
IR is convex continuously
1.1 GRADIENT METHODS
The simplest and most fundamental example of first-order methods is gradient descent (GD). This algorithm performs iterations to find an approximate solution to problem according to the fol- lowing update rule:
Fa++ 24 - 1) {*x))
(2)
where 7) > is the stepsize. Despite its simplicity, GD and its variants are widely used in practice, especially for solving large-scale problems that often appear, for instance, in machine learning. It is well-known (Polyak) 1963 Nesterov al. 2018 Droni & Teboulle 2014) that in the case where the objective function [(x is L-soooth, i.e., the gradient Vf(x) is I. Lipschitz, GD with the stepsize ? = 1/T, achieves the following iteration complexity:
K ( x²1/2
-(ax)-((r)) - f(x") Se.
(3)

---

Published as a conference paper at ICLR 2026
In addition, in his seminal work, Nesterov (1983) proposed modification of GD that implements acceleration via momentum. This accelerated gradient descent (AGD) achieves substantially im- proved iteration complexity:
K (| x= (²/e)
f(zk) f(x))
It was shown that AGD is an optimal algorithm. That is, the complexity in eq. (4) cannot be improved by any first-order optimization method due to the lower complexity bounds of Nesterov al. 2018
1.2 ADAPTIVE METHODS
One of the main issues with the standard GD and AGD is that they require tuning the stepsize n)- In particular, they require knowledge of the gradient Lipschitz constant L to achieve the iteration complexities in eqs. (3) and (4) typical approach to addressing this issue
use time-varying stepsize 77 in eq. which computed at each iteration according to a certain adaptive rule.
Line search. The simplest way to compute the stepsize ?/ is to use line search (or backtracking), an iterative procedure that finds 7/ satisfying certain objective function value decrement condition. was originally proposed by Goldstein (1962); |Armijo (166)), and its modern variant for GD and AGD was analyzed by Nesterov (2013). Unfortunately, line search makes the iterations of gradient methods more expensive as it requires the computation of the gradient V fz) and/or function value f()) multiple times without making any "progress". Henee, it is rarely used in practice.
AdaGrad-type methods. An alternative approach is to use the following stepsizes T7s in eq.
?/k = (E [x:))]) 1/2
where v) > O is a positive parameter. The resulting algorithm is called AdaGrad and was originally developed by Duchi et al.] (2011); McMahan Streeter (2010). is well known that AdaGrad has the complexity of GD in eq. (3) for L-smooth functions (Levy et al. 2018). Moreover, this algorithm is universal: it can also achieve the corresponding complexities of GD for non-smooth but Lipschitz functions, or in the case where only stochastic estimates of the gradients are available, all
with a single choice of the parameter 1) x || - x= (Levy et al. 2018 Li Orabona Orabona 2023). In addition, accelerated variants of AdaGrad are available (Levy et al. 2018
2019
Cutkosky 2019 Kavis et al. 2019, Rodomanov et al., 22044) Kreisler et al.) 2024; Kovalev 2025).
as well as Parameter-free variants (Cutkosky & Orabona 2018 Orabona & Pál Defazio &
Mishchenko 2023 Mishchenko & Defazio 2023 Lvgi et al.) [023]] Khaled et [l.3) Kreisler
2004), which do not require tuning the parameter 1/. Unfortunately, AdaGrad-type methods have a significant drawback: the stepsize V)s in eq. (5) is non-increasing. Hence, it cannot truly adapt to the local curvature of the objective function, which may limit its performance in many applications (Defazio et al. (2022).
Local curvature estimation. In this paper, we focus on different approach to computing the stepsize 7 by estimating the local curvature, i.e., the local gradient Lipschitz constant. To the best of our knowledge, the first such algorithm that has strong convergence guarantees, GRAAL, was proposed by Malitsky (2020). It is a modification of GD, which uses the following stepsize rule at each iteration:
Mx+1 = min (1
(6)
where A4+1 > O is a certain difte-diffeeence estimate of the local inverse gradient Lipschitz constant at the current iteration, and 7, v > are positive constants. [Alacaoglu et al. (2023) showed that GRAAL can achieve the iteration complexity in eq. (3) for L-smooth functions. Moreover, Malitsky
Mishchenko (2020) established the same result for AdGD, the vanilla GD with a stepsize rule similar to eq. (6)
Mk+1 min Ti
1+ Th me-1"
DAR+1}
Overall, GRAAL and AdGD demonstrate attractive results, both theoretically and experimentally. on a range of practical optimization problems (Alacaoglu et al. 2023) Malitsky & Mishchenko, 2020
2

---

Published as a conference paper at ICLR 2026
1.3 MAIN CONTRIBUTION: GRAAL WITH NESTEROV ACCELERATION
Motivated by the attractive theoretical and practical results for GRAAL and AdGD, we pose the following natural research question:
Q1. Is it possible to develop an algorithm that incorporates Nesterov acceleration and can truly adapt to the local curvature of the objective function, as GRAAL and AdGD do?
Unfortunately, to the best of our knowledge, there is no positive and comprehensive answer to this question. MMlittsky& & Mishchenko (2020) proposed an accelerated version of AdGD, which showed strong experimental results. However, it is only a heuristic and does not have any theoretical con- vergence guarantees whatsoever. In addition, Li Lan (2025) developed AC-FGM and Suh & Ma (2023) developed AdaNAG, which can be seen as attempts to incorporate Nesterov acceleration into GRAAL/AdGD with theoretical guarantees. However, the abilities of AC-FGM and AdaNAG to adapt to the local curvature of the objective function are highly limited, as we will discuss later.
In this paper, we provide a positive answer to Question | and make the following contributions:
(i) In Section 2 we develop Accelerated GRAAL (Algorithm 1 for solving problem which incorporates Nesterov acceleration and utilizes generalized version of the step- size update rules in eqs. (6) and We also provide theoretical convergence analysis of
this algorithm.
(ii) In Section we show that Algorithm I Jachivess the optimal iteration complexity in eq. (4) for L-smooth functions up to additive logarithmic factors, without the requirement of hy- perparameter tuning or any additional line search procedures.
(iii) In Section 4
demonstrate the adaptive capabilities of Algorithm T by showing that it achieves the iteration complexity in eq. (4) under the more general (Tn, T. -smoothnesss of the objective function, up constant additive factors that do not depend on the precision
The important feature of Algorithm i that it can adapt the stepsize TH to the local curvature at geometric, or linear, rate, just like the standard non-accelerated GRAAL. In contrast, AC-FGM and AdaNAG allow only sublinear growth of the stepsize, so their adaptive abilities are insufficient. In particular, Algorithm [] the first adaptive algorithm that can achieve near-optimal iteration complexity for (To, TA -smooth functions, while there are no such results for AC-FGM or AdaNAG, to the best of our knowledge. More details are available in Sections 3.2 and 4.2
1.4 RELATED WORK
More adaptive stepsizes: Barzilai- -Brleinn and Polyak. The idea of computing stepsizes using estimates of the local gradient Lipsehitz constant was previously used by Barzilai & Borwein (988). who proposed the following stepsize rule:
[V/[ vf(ee))
Rg. V/ ((((()
(8)
Unfortunately, GD with this rule provably works only in the case where the objective function fx)
is quadratic (Raydan 1993 Dai & Liao| 2002). and may not work otherwise (Burdakov et al. 2019
Polyak 1969) suggested using GD with the following stepsize rule:
M = f( (())))))(0>)
Similar to AdaGrad, GD with this rule was shown to be universal (Hazan & Kakade 2019). How- ever, it requires a tight estimate of the optimal objective function value f(z*). which is rarely avail- able in practice.
Optimization for (Ig. Ln )smmoth functions. The (Lo, L1) -mmoothhnssss assumption was pro- posed by Zhang et al.] (2019) as a generalization and a more realistic alternative to the standard L-smoothness. The convergence of gradient methods under this assumption has been extensively studied in the literature (Zhang al. 2020 Chen et al. 2023). Gorbunov al. (2024) showed that AdGD can achieve the iteration complexity of non-accoes -on-accelerated GD in eq. (3) up to additive con- stant factors without the requirement of hyperparameter tuning line search. Additionally, several
accelerated algorithms with theoretical guarantees are available (Li et al.] 2023 Gorbunov et al.
2024 Vankov al. 2024). However, all these algorithms are non-adaptive, and only Vankov et al.
3

---

Published as a conference paper at ICLR 2026
2024 managed to achieve the optimal iteration complexity in eq. up to additive constant factors, with the requirement of a substantially more complex small-dimensional relaxation oracle (Nesterov et al. 202I). It is also worth mentioning the concurrent work of Tyurin (025), who managed to achieve the complexity in eq. (4) up to additive constant factors. However, their algorithm requires the tuning of several parameters and is, therefore, also -anativii Additionally, the initial version
of our paper appeared online prior to the work (2025)) with only the results from Section 4 missing, which we were finalizing that time.
2
ADAPTIVE GRADIENT METHOD WITH NESTEROV ACCELERATION
2.1 ALGORITHM DEVELOPMENT
In this section, we develop Accelerated GRAAL for solving problem ( Below, we briefly describe the key ideas used in the development of the algorithm. After assembling these ideas, we obtain the resulting Algorithm
Local curvature estimator. As discussed in Section 1.2 the stepsize rule in eq. (6 used in GRAAL
requires an estimate of the inverse local gradient Lipschitz constant A. When the objective function
is convex, given two points 2, E RR, can consider the following two options for computing X:
Option I: X |V
ال=ج||
2Dy(s.s) Option II: X V[
(10)
GRAAL was originally developed for solving monotone variational inequalities (VI). Hence, it uses Option I, which works for this more general problem class, with the gradient ff()) replaced by the monotone operator. However, it turns out that Option II can better exploit the properties of the objective function f(xx). Hence, we use Option II and, for convenience, define A 2) as follows:
V + f())) fz(2) = fz()
2(x;2)
[VF()
(11)
+0c
is worth noting that Li & Lan (2025); Suh & Ma (0255) also used Option II in AC-FGM and AdaNAG, respectively.
Nesterov acceleration. To incorporate Nesterov acceleration in Algorithm 1 we use its recent interpretation by Kovalev & Borodich 2024). The idea is that at the iteration i of gradient method, we replace the objective function f(x) with the function fa (z): Id + R. defined as follows:
(x) = azz f(azz + (1-ax) TT)) where ar E (0,
I ER.
(12)
In the case where GD is used, that is. Ik+1 I 7h V (xx). we can choose ag 2/(k + 2) and Tx+1 = 0g.T&+1 + (1 TT which gives the STM algorithm (Gasnikov & Nesterov 2016), a variant of AGD, However, we use the definition in eq. (12 as substantially simplifies the development of Algorithm [
GRAAL extrapolation. We use the extrapolation step of GRAAL in combination with the inter- pretation of Nesterov acceleration above. It can be summarized as follows:
To++ F4 - 7/a ($te,,
.2+1 = #2+1 + 0( - -xx);
(13)
where 0 > 0 is the extrapolation parameter. GRAAL uses extrapolation for two reasons. First, the vanilla gradient method does not work for VI as diverges even on simple bilinear min-max prob- lems (Daskalakis et al. 2017]. Hence, the extragradient method (Korpelevich) 1976; Mishchenko et al. 2020) or methods with extrapolation (Daskalakis et al., 2017] Malitsky & Tam [2020] Ko- valev al. (022) are typically used. Second, and more importantly, to the best of our knowledge, the particular type of extrapolation used by GRAAL plays a key role in its adaptive capabilities. In particular, it is an open question whether our results can be obtained with a different baseline algorithm.
Problem:
choosing onk- Although it may seem that the tools described above are already enough to obtain Algorithm D one issue remains. The interpretation Kovalev & Borodich (2024) combined with the GRAAL step in eq. (13) suggests that one should choose Tx+1 ag.. However, this would require that the parameters as satisfy the following inequality
0rk) )
mp/Ox I 11-1//0- Th-
(14)
Mooe details eq. (14 are available in the works of Kovalev & Borodich 2024 Kovalev
2025
4

---

Published as a conference paper at ICLR 2026
Algorithm 1 Accelerated GRAAL
1: input: 2n E _R_ > 0, K E (1, ...
2: parameters: Y, > 0 satisfying eq. 19
3: 30p = Hp = H- = =1-11 = 1/0.
2o
TD = 20
4: for k 0, o.......A. do
(1+7)m
5: at++ +1++(++)
6:
Ik+1
1/K (ā(k))
gradient step
7:
Tk+1 Bx00 + Jx
additional coupling step
8:
āk+1 Ih+1 + 0(xx+1 Ik)
GRAAL extrapolation
9:
F = 0x+1&x+1 + 0K++1 Jk++1
b Nesterov acceleration/SIN
10:
Ak+1 min A [T++1 }x,,, ( 1x+1))
D local curvature estimator
11:
7h+1 min + 77
WHe WHy de+1
Jr Ha+1 = Hs + mh+1
adaptive stepsize
12:
3k+1
76-1
H++1
13:
output: -K- E R
The best option is choose a such that eq. (44 becomes an equality. However, this is impossible: computing 7) requires an estimate of the local curvature, which requires the computation of the gradient (.xx and its use in eq. (11), which in turn requires knowing ag in advance. Alterna- tively, one could follow the approach of Li & Lan (2025) and Suh & Ma (025) used in AC-FGM and AdaNAG, respectively, and simply predefine ag x 2/(k + 2), just like in AGD. However, this requires additional restrictions the stepsize 77 and vastly limits the adaptation capabilities of AC-FGM, as we will discuss in Section 3.2
Solution: additional coupling step. The key idea to resolve the issue above is to avoid the inequal- ity in eq. [44 by defining Tk+1 differently, using an additional coupling step:
Th+1 B5 (1 3T)
i* - au + )Tx
(15)
where Be E (0, 1]. Consequently, instead of requiring the inequality 14 we choose the param- eters Br to satisfy the following relation
ne/ ()xx0))))) = 7
(k-1) + 7/k -... Ha. where H4 Ei=olh-
(16)
Hence, we choose 3g m) na/ Hx) and avoid additional restrictions on the stepsize ?)-- The only
remaining question is how to ensure 3R S 1. The answer is that we choose ay. H4-1+(1+7)
(1+7))%
Indeed, in Lemmal 1 we prove that BB. (0, 1] by utilizing the inequality T/s (1+7)mm which is implied by our stepsize rule in eq. [17. Moreover, our choice of a is implementable as it does require knowledge of 17K. and, contrast to AC-FGM and AdaNAG, is not based on any predefined sequence, but rather uses the adaptive stepsizes 7 and their sum H
adaptive because
Adaptive stepsize. We use the following adaptive stepsize 7 in our algorithm:
M = min (1 7)
(17)
11-1
where dc+1 = min(A(T 2x) A (T xx+1)} } is the local curvature estimator. This rule is
primarily implied by the convergence analysis in the proof of Theorem iin Appendix A.3 It can
also be seen as a generalization of the stepsize rules in eqs. (6) and 7 for GRAAL and AdGD, respectively.
2.2 CONVERGENCE ANALYSIS
We start the convergence analysis with the following two lemmas. In Lemma show that 3e E (0, 1] as discussed the previous Section 2.1 In Lemma 2 we use the additional coupling step from line 7 and the convexity of the objective function f(x) to obtain some useful inequalities.
Lemma
A Me. H > O, E (0, 1), and 3g E (0, for all k K}.
More details eq.
16 available in the proof of Theorem 1 in Appendix
A.3
5

---

Published as a conference paper at ICLR 2026
Lemma 2 a.. The following inequalities hold for all lo E fI...., K-1KK11 1}: f(Tx) - f(xx)= S Bx (f(Tx)) - f(x++))), Dy(TRi - (;
(18)
Now, we obtain the main convergence result in Theorem Note that Algorithm | requires the universal constant parameters % > 0 to satisfy eq. (19). However, it is easy to verify that such parameters exist. Using Theorem D we also obtain the upper bound on the functional suboptimality
and distance the solution of problem ① in Corollary [
Theorem
Let parameters 7, > O satisfy the following relations:
4v0(1 + 7)² 7, 1 1 27
2n.02 [I+9]7
0 + [I+0)²
0a
(19)
[1+8]
Then, the following inequality holds for all x E Rd and E (1,.... ........ K -1]:
(x) S (x(x)
20 2 Mh
V fi+))l 4[1b)) D (Tx: Tx),
(20)
where (x(x)) is defined as follows:
vx(x)) = 1 I| - =r|2+ + H (((x)) +
OTpe 7/--
(T(Tk-11 TR 1) +) 10
x2 Tk-1 (21)
As
Corollary 4 The The following inequality holds for all x R& and K - 1:
|| ==1² + (f- fx)) s f1100 - x|2 + (1+00) 1o (xo))l
(22)
is important to highlight that the results in Theorem [ and Corollary are general and do not require any additional assumptions on the objective function other than convexity and continuous differentiability. Consequently, they do not imply any non-asymptotic convergence results for Al- gorithm ! However, in Sections 3 and 4 we will establish particular iteration complexities in the cases where the objective function is L-smooth and (Lo, L1) Ls)-shothh, respectively.
3
CONVERGENCE ANALYSIS FOR L-SMOOTH FUNCTIONS
3.1 MAIN RESULT
In this section, we establish the iteration complexity of Algorithm in the case where the objective function f(x) is L-moooth for O. That is, the gradient f( is L-Lipschitz:
Vf(x) - ff()))l < L|a - =|| for all x, Ed.
(23)
We start with the following two lemmas. Lemma 3 provides lower bound the eurvature esti- mates Ag. This lemma is standard, and its proof is given, for instance, by Nesterov et al. (2018) Theorem 2.1.5). Lemma 4 bounds the growth of the cumulative sum H4 of the stepsizes T/k-
Lemma 3. A 2 L/L all E KL. Lemma H S HA S (2+ H all ls fo....,K].
Now, we ready establish the lower bound the cumulative sum H& of the stepsizes 7e in the following Theorem 2] Using this bound, we establish the iteration complexity of Algorithm for L-smooth functions in Corollary 2
Theorem
D. Let constants C, m E R. be defined as follows:
c min
Jv 3(247) 16 V
max (
2, 19,11
1J
(24)
29
Then, the following inequality holds for all l E (O....,'y K):
/Hn Z VL (k m).
(25)
Let L < 1. Then, to reach the precision f(Tx) - f(x*) S e, the following number of iterations of Algorithm iis sufficient:
Corollary 2.
x² 12 K= k=0(1+ 1/ I
(26)
Note that the complexity result in Corollary reeuurres the initial stepsize Nu to satisfy the inequality 77 1/L. However, simply choose 7/u be very small, say 10 suggested by Malitsky
& Mishchenko/ (2020) for AdGD. This will only result in a small logarithmic additive factor in the iteration complexity implied by Corollary 2

---

Published as a conference paper at ICLR 2026
3.2
COMPARISON WITH AC-FGM AND ADANAG
AC-FGM. Li& Lan 2025 Corollary 1) use the following adaptive stepsize rule for AC-FGM:
7 min Jetil x Tiks gk
(27)
This rule implies that the stepsize growth restricted by the inequality 7/411 S (1 + 1/k)mj- As
mentioned in Section 2.1] this restriction substantially limits the ability of AC-FGM to adapt to the curvature of the objective function. In particular, the result oi & Lan 2025 Corollary 1) implies the following iteration complexity, provided no - L.
K= = o (L, L/) L x=1 1=1///c = f(Tx) - Sxx
(28)
This matches the optimal complexity in eq. (4) if we choose 7o 0.4/L. However, if we choose
the initial stepsize to be too small, i.e., ?/o < 0.4/L, the complexity result in eq. (28) will be worse
than the optimal one by factor of 1/ In other words, the stepsize rule in eq. (27) cannot adapt to a "bad" choice of the initial stepsize no due to stepsize growth restrictions. Li & Lan (2025) even had to use line search at the first iteration of AC-FGM to find a "good" initial stepsize f/o and achieve the optimal complexity in eq.
AdaNAG. Suh & Ma (2025) uses stepsize rule in AdaNAG, which is not substantially different difference is that they do not use line search the first iteration, but rather estimate ?/u using Option in eq. TTP. which implies the following iteration complexity:
from eq. (27). Consequently, they encounter issues similar to AC-FGM. The
K = O ( m1 no v LL - x 1l/cc
= f(zk)- Sc.
(29)
This result may be significantly worse than the optimal one in eq. 4 if the initial stepsize estimate is too large, i.e., no L. >> 1. Moreover, similar AC-FGM, the growth of the stepsize in AdaNAG is also substantially restricted, which can limit its performance, for instance, under the more realistic (Lo, (.o..,))ssmooe -isssmetssssss assumption.
Algorithm|| [ vs AC-FGM and AdaNAG. In contrast to AC-FGM and AdaNAG, our stepsize rule in eq. (17) allows the geometric growth of the stepsize 76+11 S (1 + 7))k- Hence, Algorithm can adapt even to very small choice of the initial stepsize 7ju at the cost of small logarithmic additive factor in the iteration complexity, as indicated by Corollary
addition, as we will discuss in Section 4 the geometric growth of the stepsize is crucial for adaptation under the (Too, I,)- smoothness assumption, where the local gradient Lipschitz constant may change an exponential rate. It is also worth mentioning that(Li & Lan [2025] Corollary 2) and /Sh & Ma (2025) Theorem 6) tried to resolve the issues with the stepsize growth restrictions in AC-FGM and AdaNAG by using different stepsize rules. However, they could not properly justify the efficiency of these new stepsize rules and provably achieve geometric growth of the stepsize.
4 CONVERGENCE ANALYSIS FOR (Lo, L))-SMOTTH FUNCTIONS
In this section, we establish the iteration complexity of Algorithm in I the case where the objective function [xx) is (To, -mmoohh for Lo, J,1 > O. That is, the objective function f(x) is twice continuously differentiable and the following inequality holds:
(V2((x) S Lo f()] for all x Rd.
(30)
This assumption was proposed by Zhang al. (2019) and primarily motivated by experiments suggesting that the norm of the Hessian correlates with the gradient norm of the objective functions in deep neural networks. Note that the requirement for twice continuous differentiability may be re- laxed by using the following equivalent condition for continuously differentiable objective functions Vankov et al., 2024 Lemma 2.5):
[ - vf(=)] & (To + L (x))) 2, (exp(Tall
- =|I) - 1).
(31)
is also important to highlight that (Lo, L smoothhnsss implies L-smoothness with = Lo. The reverse is obviously not true: (Lo, L2) smoothness is much more general and allows the exponen- tial growth of the objective function and local gradient Lipschitz constant (Gorbunov et al. 2024
Lemma 2.1: Vankov al., 2024 Lemma 2.5).
7

---

Published as a conference paper at ICLR 2026
4.1 MAIN RESULT
We start the convergence analysis of Algorithm with Lemma 5 which refines the previously ob- tained results in Theorem [ and Corollary | Furthermore, in Lemmas and 7 we establish lower bounds on the estimate X of the local inverse gradient Lipschitz constant.
Lemma 4 The following inequalities hold for all K 2 1:
| -1 - = |Ix-1- -0-1-==111 =''l DD
Σ
+
< <D², (32)
where D 2 0 is defined as follows:
D2 = max 70: 2(1 + 7), (1 (1+20)² (1120 - x²11 70) Vf
(33)
Lemma 6 A 2 Amin for all k E {L...., K}. where Amia 0 is defined follows:
Amin to exp( -3L
(34)
Lemma
The following inequality holds for all k E (1.....K):
4
(35)
max
(Tx: #x), (3
Next, we define the sets of indices (k),, (k)), Ts(k), (kk)) follows:
(k) = 1 I i S :: :7; = 2
and X; 2
2
9i-2
(2(k) = [1 s k wHi-ad and X; < gLe
2
8-
(36)
Ta(k) = { 1 iisis i k 0--2
2d: and (1(i) E (ikk) or i ((i) m)).
Ta(k) = {1< Aisiss k: :
and ((i) E T2)() U {0} and -(())= S m
where is positive integer, and the integer function ((k) is defined as follows:
I(k) = max i (1k) U (T(( U (0)}-
(37)
It is not hard to verify that these sets of indices are pairwise disjoint and that T(k))
(1.....k) k). Moreover, the sizes of the sets Ta (A)) and (k) are bounded as shown in the following
Lemma
Lemma
The following inequalities hold for all k E {I,.... K}: [T((K) m mT)((k)),
[T2( S 1 (in LTD
81(1+a)²
(38)
Now, we establish the key lower bound on the cumulative sum H₃ of the stepsizes 7 in the following Theorem 3
Using this bound, establish the iteration complexity of Algorithm for (Lo, I )-
smooth functions in Corollary 3
Theorem D Let 0 and 0 be defined as follows:
c= mim
V20 9(2+7) 21 (11 Jr
Vey
|mxx 1, 1, 19040 ]
46"
lm my PLadmin }} (39)
Then, the following inequality holds for all l (O.....,), KK).
VH vi (k: - (T2(k:) - [a((k)] 1).
(40)
Corollary
Let To Lo exp(Li 11:0 - x1)) < 1. Then, D = O(11=5 - x=
and to reach the f(x') S the following number of iterations of Algorithm is sufficient:
precision f(TK)
K = 0 (1 LoD2 +2TD + (1+ L3D²) In
(41)
To
Similar to Corollary 2 for the L-smooth case, Corollary 3 requires the initial stepsize too to satisfy the inequality Lo exp(Li [|000 - xx I)) 1. We can ensure this inequality without any line search or hyperparameter tuning, simply by choosing a very small initial stepsize 7p. Choosing the initial stepsize du too small will only result in additive constant factor (1+ L2 In Lop b which
does not depend the precision and has logarithmic dependence 1/o-
8

---

Published as a conference paper at ICLR 2026
Table I: Comparison of the iteration complexities for solving problem TD under the convexity and (Lo. L >smoothnesss; universal constants are omitted: D = =1|20 - 2"Il: the initial functional gap is
bounded f(xo) - f(=*) S (LoD exp(LiD)) where necessary; optimality considered up to
additive constants.
Reference
Iteration Complexity
Optimal
Adaptive
Li et al. (2033)
LnD
(1+ L,D?) exp ())(O())),D)
Gorbunov et al.
2024
Lg D2
x /V ex
X
x
Vankov et al. (0244
De
+ (L,
Tyurin 2025
De
+ +LID2)
x
Corollary 3
De
+ (L,D)²
4.2 COMPARISON WITH EXISTING RESULTS
Accelerated methods for (Lo. -mmothh functions. As mentioned in Section 1.4 there sev- eral existing accelerated algorithms with theoretical guarantees for minimizing convex (Lo, L1)- smooth functions. To compare these results with Algorithm T we
particular choice of the initial stepsize Yoo = Lo exp( L1 20 x=" x=" in Corollary 3 The comparison is summarized in
Table T The algorithms of Li et al. (2023); Gorbunov et al. (2024) are neither adaptive nor optimal. they match the complex- ity in eq. (4) up to additive constants, just like Algorithm [ The result of Vankov et al. (2024) has a slightly better additive constant (L/D) However, neither of the algorithms of Vankov et al. 2024);; Tyurin (2025) is adaptive: the algorithm of Vankov et al. (2024) requires solving
The algorithms of Vankov et al. (2024); Tyurin] (2025) are near-optimal
dimensional auxiliary optimization subproblem at each iteration, and the algorithm of/Tyurin (2025) requires tuning several parameters. In contrast, Algorithm [ does require any hyperparameter tuning or line search to achieve near-optimal complexity, as discussed in the previous Section 4.1
AdGD for (To, Ta 3mm-shohhh functions. Gorbunov al. (024)) established the iteration complexity (L,DD²/ + (L, for the AdGD algorithm under the (Lu, Ls)-smoothness assumption 3 This result unsurprisingly worse than ours in Corollary 3 due to the lack of acceleration. In addition, Gorbunov et al. (2024) did not prove that the constant D is bounded D O[I ==))) In Tact, D also contains the initial objective function gap / [((o)) - f(xx), and hence, it may have an
exponential dependency on the initial distance ||aro - ||-
As previously discussed in Section 3.2 we allow the geometric growth of the adaptive stepsize in Algorithm [ which crucial for obtaining the near-optimal complexity result in Corollary 3 Indeed, the estimates of the local curvature A& can scale exponentially in the worst case according to Lemma 6 but can grow up to (11LL)) when the algorithm reaches certain region near the solution x=" Hence, the growth of the stepsize at a geometric rate or faster is contrast, [ & Lan (2025): ; Suh necessary to avoid exponential factors in the iteration complexity.
AC-FGM and AdaNAG.
& Ma (205)) do not provide any convergence guarantees for (Lo, Ln -ssmoothness for AC-FGM and AdaNAG. In addition, as previously discussed, the rate of stepsize growth in AC-FGM and AdaNAG is far below geometric. Hence, conjecture that it is not possible to reach near-optimal complexity with these algorithms.
ACKNOWLEDGEMENTS
This work was supported by the The Ministry Economic Development of the Russian Federation in accordance with the subsidy agreement (agreement identifier 0000000311925PP400000 grant No 20225-0100....
Note that Gorbunov
2024 incorrectly reported their result Ó(T,D /e (

---

Published as a conference paper at ICLR 2026
REFERENCES
Ahmet Alacaoglu, Axel Böhm, and Yura Malitsky. Beyond the golden ratio for variational inequality algorithms. Journal of machine learning research, 24(172):1-33, 2023.
Larry Armijo. Minimization of functions having lipschitz continuous first partial derivatives. Pacific Journal of mathematics, 16(1):1-3, 1966.
Jonathan Barzilai and Jonathan M Borwein. Two-point step size gradient methods. IMA journal of numerical analysis, 8(1): (1):1141-14, 1988.
Oleg Burdakov, Yuhong Dai, and Na Huang. Stabilized barzilai-borwein method. Journal of Com- putational Mathematics, pp. 916-936, 2019.
Ziyi Chen, Yi Zhou, Yingbin Liang, and Zhaosong Lu. Generalized smoohh nonconvex optimiza- tion is as efficient as smooth nonconvex optimization. In International Conference Machine Learning, pp. 5396-5427. PMLR, 2023.
Ashok Cutkosky. Anytime online-to-batee optimism and acceleration. International conference on machine learning, pp. 1446-1454 PMLR, 2019.
Ashok Cutkosky and Francesco Orabona. Black- box reductions for parameter-free online learning in banach spaces. In Conference On Learning Theory, pp. 1493-1529, PMLR, 2018.
Yu-Hong Dai and Li-Zhi Liao. R-linear convergence of the barzilai and borwein gradient method. IMA Journal of numerical analysis, 22(1):1-10, 2002.
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. arXiv preprint arXiv:1711.00144 2017.
Aaron Defazio and Konstantin Mishchenko. Learning-rate free learning by d-adaptation. In Inter- national Conference on Machine Learning, pp. 7449-7479. PMLR, 2023.
Aaron Defazio, Baoyu Zhou, and Lin Xiao. Grad-gradagrade a non-monotone adaptive stochastic gradient method. arXiv preprint 220i::::2200066000 2022.
Yoel Drori and Marc Teboulle. Performance of first-order methods for smooth convex minimization: a novel approach. Mathematical Programming, 145(1):451-48) 2014.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
Alexander Gasnikov and Yurii Nesterov. Universal fast gradient method for stochastic composit optimization problems. arXiv preprint 1604::160..05275. 2016.
Allen A Goldstein. Cauchy's method of minimization. Numerische Mathematik, 4(1):146-150 1962.
Eduard Gorbunov, Nazarii Tupitsa, Sayantan Choudhury, Alen Aliev, Peter Richtárik, Samuel Horváth, and Martin Takáč. Methods for convex (L0, -moohh optimization: Clipping, ac- celeration, and adaptivity. arXiv preprint arXiv:2409.14998 2024.
Elad Hazan and Sham Kakade. Revisiting the polyak step size. arXiv preprint arXiv:1905.00311 2019.
Maor Ivgi, Oliver Hinder, and Yair Carmon. Dog is sgd's best friend: A parameter-free dynamic step size schedule. In International Conference on Machine Learning, pp. 14465-14499. PMLR, 2023.
Ali Kavis, Kfir Y Levy, Francis Bach, and Volkan Cevher. Unixgrad: A universal, adaptive algorithm with optimal guarantees for constrained optimization. Advances in neural information processing systems, 32, 2019.
Ahmed Khaled, Konstantin Mishchenko, and Chi Jin. Dowg unleashed: An efficient universal parameter-fi free gradient descent method. Advances in Neural Information Processing Systems, 36:6748-6769, 2023.
10

---

Published as a conference paper at ICLR 2026
Galina M Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
Dmitry Kovalev. Sgd with adaptive preconditioning: Unified analysis and momentum acceleration. arXiv preprint 2rXiv:2506.238800 2025.
Dmitry Kovalev and Ekaterina Borodich. On linear convergence in smooth convex-concave bilinearly-couples saddle-point optimization: Lower bounds and optimal algorithms. arXiv preprint arXiv:2411.14601 2024.
Dmitry Kovalev, Alexander Gasnikov, and Peter Richtárik. Accelerated primal-dual gradient method for smooth and convex-concave saddle-poing point problems with bilinear coupling. Advances in Neural Information Processing Systems, 35:21725-2111 21737, 2022.
Itai Kreisler, Maor Ivgi, Oliver Hinder, and Yair Carmon. Accelerated parameter-free stochastic optimization. In The Thirty Seventh Annual Conference on Learning Theory, pp. 3257-3324. PMLR, 2024.
Kfrr Y Levy, Alp Yurtsever, and Volkan Cevher. Online adaptive methods, universality and acceler- ation. Advances in neural information processing systems, 31, 2018.
Haochuan Li, Jian Qian, Yi Tian, Alexander Rakhlin, and Ali Jadbabaic. Convex and non-convex optimization under generalized smoothness. Advances in Neural Information Processing Systems, 36:40238-4022 2023.
Tianjiao Li and Guanghui Lan. A simple uniformly optimal method without line search for convex optimization: T. li, lan. Mathematical Programming, pp. 1-38, 2025.
Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. The 22nd international conference on artificial intelligence and statistics, pp. 983- 992. PMLR, 2019.
Yura Malitsky, Golden ratio algorithms for variational inequalities. Mathematical Programming, 184(1):383 410, 2020.
Yura Malitsky and Konstantin Mishchenko. Adaptive gradient descent without descent. In Interna- tional Conference on Machine Learning, pp. 6702-6712. PMLR, 2020.
Yura Malitsky and Matthew K Tam. A forward-backward splitting method for monotone inclusions without cocoercivity. SIAM Journal on Optimization, 4012):1451-147,, 2020.
Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex opti- mization. arXiv preprint 1002:: 2010.
Konstantin Mishchenko and Aaron Defazio. Prodigy: An expeditiously adaptive parameter-free learner. arXiv preprint arXiv:2306.06101, 2023.
Konstantin Mishchenko, Dmitry Kovalev, Egor Shulgin, Peter Richtárik, and Yura Malitsky. Revis- iting stochastic extragradient. International Conference on Artificial Intelligence and Statistics, pp. 4573 PMLR, 2020.
Yu Nesterov. Gradient methods for minimizing composite functions. Mathematical programming. 140(1):125-161, 2013.
Yurii Nesterov. A method for unconstrained convex minimization problem with the rate of conver- gence (11/k²) Dokl. Akad. Nauk. SSSR, 269(3):543, 1983.
Yurii Nesterov, Alexander Gasnikov, Sergey Guminov, and Pavel Dvurechensky. Primal-dual ac- celerated gradient methods with small-dimensional relaxation oracle. Optimization Methods and Software, 36(4):773-810 2021.
Yurii Nesterov et al. Lectures convex optimization, volume 137. Springer, 2018.
Francesco Orabona. Normalized gradients for all. arXiv preprint 200 2023.
11

---

Published as a conference paper at ICLR 2026
Francesco Orabona and Dávid Pál. Parameter-free free stochastic optimization of variationally coherent functions. arXiv preprint arXiv:2102.00236. 2021.
Boris Teodorovich Polyak. Gradient methods for minimizing functionals. Zhurnal Vychislitel noi Matematiki Matematicheskoi Fiziki, 3(4):643-653, 1963.
Boris Teodorovich Polyak. Minimization of unsmooth functionals. USSR Computational Mathe- matics and Mathematical Physics, 93)):14-99, 1969.
Marcos Raydan. On the barzilai and borwein choice of steplength for the gradient method. IMA Journal of Numerical Analysis, 13(3)321-326, 1993.
Anton Rodomanov, Xiaowen Jiang, and Sebastian U Stich. Universality of adagrad stepsizes for stochastic optimization: Inexact oracle, acceleration and variance reduction. Advances in Neural Information Processing Systems, 37:26770-26813, 2024.
Jaewook J Suh and Shigian Ma. An adaptive and parameter-free nesterov's accelerated gradient method for convex optimization. arXiv preprint arXiv:2505. 1670, 2025.
Alexander Tyurin. Near-optimal convergence of accelerated gradient methods under generalized and (1_0, smoothhssssssss arXiv preprint arXiv:2508.0668: 2025.
Daniil Vankov, Anton Rodomanov, Angelia Nedich, Lalitha Sankar, and Sebastian U Stich. Opti- mizing (L_0,_1)-smn -mmooot functions by gradient methods. arXiv preprint arXiv:2410. 2024.
Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang. Improved analysis of clipping algorithms for non-convex optimization. Advances Neural Information Processing Systems, 33:15511-15522 2020.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. arXiv preprint 1rXiv:1905.1188/ 2019.
12

---

Published as a conference paper at ICLR 2026
Appendix
A PROOFS FOR SECTION 2
A.1 PROOF OF LEMMA
First, we can show that A > for all k E [I,...,K]. Otherwise, if Ax 0, there exist
2, E Re such that A(z, z) 0 due to the definition of A line 10 Hence, Dy(#; z) = according to eq. [II. From the convexity of the function f(x). it follows that (y(x; 2) 2 0. Hence, minimizes the function ( and by the first-order optimality conditions, Va VyDr(r; Vf(x) vf(=) = 0. This implies A (x;z) +oo according to eq. (1)), which contradicts the
possibiliity of λ 0.
Next, using the fact that A > and lines and is easy to show that Me, H > 0 for all k (-l,..., Kj. Hence, the inclusions or (0, and 3x E (0, +00) are obvious due their
definitions on lines 5 and 12 Finally, we can upper-bound BR+1 as follows:
8x+1
Th++1
Hy + (1 7)
(1 7)TH
HA + (1 (1+ 1,
Ogg
H4+1
Hg 11+1
(1 + 7mm
H& + (1+7))m
(1+ >)m)
where (a) uses line 12 db) uses lines 5 and 11 (ch uses the inequality mh+1 S (1 + 7) implied by
line 11 and the monotonicity of the function t/(1 + t).
L
A.2 PROOF OF LEMMA 2
We can upper-bound / (*++1) as follows:
[ 1
[Barã + (1 (1- B.)
(Tx. + (1 (xx)
whereda) uses line 7, b uses Lemma and the convexity of fxx) After rearranging, we obtain the first desired inequality. Furthermore, can upper-bound D (TR, Jx-1) as follows:
Dy 1 + (1 3k- J xk-1)
Bk-1) Dy (Tx- xx-1) + f Dy (ik-1;
where uses line 7 bb and (cp use uses Lemma and the convexity of Dy(1)8-1); which is implied by the convexity of f(r]. This proves the second desired inequality.
A.3 PROOF OF THEOREM 1
For all {I...., K - 1}. we obtain the following:
|| - x| = 2 2| - z0|2 1
2 | - 12 + (
Ik. Fk+1 - x))
= b|| - z1|2 - 1110411 - 22 2 + (Øk+11
Ik. xc++1 - -1++1)
+ (xx+1 Fs, + - .4 + 2t - x))
|| - 2||2 - (5 + 0) || 1| + (0++1 - Tk. Bb+1 fb + 8t x))
2 || x/| (1 0) || 21
Th V (3t)) 8441 .x2)
(ā x .x)
1|1 z0|2 - | xxl| 1| 1/6 V f St 5rxe
Th (V - zz) (1-axing (V (īx) T - 5x.
2/ | ==12 ( 0)
|| = Th (V $1 ..x)
13

---

Published as a conference paper at ICLR 2026
+ nx(f(x) f(xx)) (L-ae)mt (f(Ix) -f f(x) - (Ix: kx,))
ay
= - - 21|² - (5 + +0) - xx|1² - 77 V (āx), Tx+1 - 2xk
-m((((T)) - f(x)) 244 (f(Tx) - [(xx) (س (3
- -1llz - x|I2 - (1 + 0) |1++| - xx - (V ix+1 - 3xx
(=((()))) - f(x)) + 2. (f(xx) f((x+1)) (L-a+) (I( ttkc)
ok
0 -11=a= -0--1111 2112 - ( + 00) 12 xxll 112 - (V [+x),, - xx) (x(((T))) - f(x)) + Hx( - -((x++1) - (2-ax)14 Dy (T #x)
1 =1 - (1 0) |, - xx/12 Tn (V (Tx(), u2+11 ftne
H (f - -=x)) H (J (f (xx)) (1-az)0k Dj (T( Tx)),
cxp
where (ap uses line 8
bb)
uses line 6 + uses line 9 (d) uses the convexity of function f(x); (c)
uses Lemma 2. uses
line 12
uses line 11 Furthermore, we get the following:
1 |
x1|
2
S 2 1| æ=|2 - (2 + 0|| - 1 + Hx-1(f(T1)) - f(x)) - H H& - f(x))
(1-0x) )nk. (y(Tx; 7/ (V5( - V 2241 - it)) - mh (V]((Tx))) $0 - hn)
2 1| x=|2 - (b + 0) || 122 + 1 (f(T)) f(x)) (Fx+(( - f(x))
(1-mx) me Dy( +x) 7/ (V)( - V 1), 1xx11 - tn))
7h-1 (ITk 1k-1, - .22
b 1110 - x1|2 - (1 - 0) || - rull2 + H 1 (f(Tx) - f(x)) - ()(()
(1-ar)m )m (y(Tx:
Thk (Vf((t)) V
1).2111 - (xx)
a6
+ n (0x - Ik. fx+1 - 2x)
One-1
111 x1| (1 + 0) || - 12 + H 1 (f(xz) - -(()) (A(((T
(1-ox) )m (T{xx: Nx (Vf(#t) (fxx 8x41 .TA)
a6
+ 20me-1 1 (1 23 2 - | - 1x -1 - 11)
c
111 - x1| 2- (1 + 0) || - 1x 11 + 1 (f(x)) ) - -xx)) (Fx((())+)) [wx))
(1-cx) )nk DT{ āx) 7h (V)( - V ff (1; 2,,1 xtk)
a&
+ 20m
((1 + 1) - 2x1l 8² 1|a - x6 2 112 - 11 - 1x)
1 1|[ - x1|2 + 20
(1+0)²
m
0+202
|| - 2x
- || xk-1
91k
M--
(1+0)=)
Mi || | 3
12 + mk
V ʃ (Txx - V |+ - dz
20me-1
(1-a) mo
(y( kx)) + H (Ix) - fx))
f(x)),
where @a) uses line o and (c) use line g
uses the Mauchy-Schwarze inequality. Next, we get
1 | z:|
$ 11 x012 + (1+0)²
8-202 (1+0y)) || - Ixll -na-1 || - 111
Oye
28
カk-1
(1-aw)me
D D Rxk) + H (f(x)) - ((x)) H&( - f (xz)
mk -0
|| 22 122 + mell V f(tx) - V (f - -bxll
1| - =x|12 + H 1 (f(x)) - f(x))
Hn( - f(x))
(1+0)²
242 (1+0y²)
|0 - xx
Amk -
| - -h-1
28
14

---

Published as a conference paper at ICLR 2026
[k+1 2x,1" 2- (1-ax)me D DT( #xk)
20 1
+ 7kl V (āx) - -V Vf(Tx))l11 - 2x61 + mh I (Txx) - V((++-))ll(@+1 - -fxl
2112g - xx12² + Hx-1 - -((x)) - -Hx(f(Tx-1) - f(x))
(2+-))*
1h 0+202
| - xx 11
Bri 2nk-1
lokk - IA 1112
20
Mx-1
(148y²
|xx+1 $6 12
(1-aw)mk Dy Txx)
20
an
+ 77
D (T(TKi [b)1| - &xll + 7 V de Dy(TRiāk-111 1x $x1l
N
2 2/
=e|2 Hx-
Hx-1(S(TxR) (f(T)) - [(x)) HH(((TR+1)) - f(x))
(1+0)²
9-202 (1+07²
[TR+1] - =x21?
Oyp
| - IK-
20
mik
2nd
| 12
(1-aw)mk Dj (I xxx)
201
1
an
+ 17
2 DT(Ta: 01 - +xll + 7k V d
Txel
2 1|10 - xx1² + H==I(f(TTk) - f(x)) - -Hx(f(Tx-1) - f(x))
(2+0)²
0+202
| xxx1 211-1
By
| I x1
Mk-1
(148y²)
me
|| [ - 8% 11
(1-ayl1k (Ts: xx) + (1 Mi D, (T 3x))
20
201
| 1x
+ 0m 1 Dy(TN.
(Tn k- xx- + 20m ||
&x 11?
(1-ae)Ae
Au
&11 - xe||2 + H (f(T)) - f(x)) HHa[ - -f(x))
(1-04) 1' Dy (Txx:
dax
+ 20
(1+0)²
M--1
9h 0+203
(1+082
| - 1x 2
Byh |atk - 5k- 112
|:2+11 1x
(1-04)06
Dy (Txiit))== + OmN (D((x-1i;08-))
(1-ax)M Di
4am
du
1 11 - x=|²² + HHH (f(Iz) - f(x)) Hx(((IZ+11 - -x(x)) I(I+7) Dy (T(x 2x)
The
2
+ 20
(1+0)²
n1 0420² (1+07=
|08+1 - xx
2 1a - -Ik-1ll
|
2x
(1-a,)ve Dy Tx) + Onwmu-1 Dy
(1-02
1az
where uses the triangle inequality; (b) uses line 10 and eq. I cc) uses Lemma
2
uses
Young's inequality; (e) uses lines
5 and Furthermore, we obtain the following:
|| - 2
< 1111== 2112 + Hy-1(f(TH) f(x)) - Hx(((Tx+1) - f(xx)
Tee
Dy(Txi
((+t))
(1+0)²
0+20²
|| 1x
Bnn
|| - TK- 112
24
[1+6}2
Zm
| - 2/
(1-01)dE11
Onk 19k DT(Tzi xx) +
Bm Av
Dy (T
Au+1
111 - xx|12 + 11s-1(((2)) f(x)) - H&(f(TT4)
f(x))
पा+b) Dy(Txiãz)
(1+0)²
Aik
94220
|| - 12
Ank
|| - Ix 112
28
[1+07=]
In
||
- 1x 11
0n
D Dy(Tx; Tx) +
09 D (ī
[1-ax)AA
T0O[1+7)
AK+1
||
xr| + H (TTT) f(x)) - Hf - f()) Mाोデ D5
(1+0)²
Aik
94200
|| - xx - Ang
-ne- || - -I--1l 112
28
[1+07²]
+ (A
|1a
- 12 - (1+^) 07 DT( 8xk) +
m DT 1;
3
1
2,
(Ixi 2x)) < } | 2112 + Hf -f(z)) - Hz(f(xx41) -f(x)) - Dz(
15

---

Published as a conference paper at ICLR 2026
(1+0)
me
84202
|| - xxxl?
Onk
1 I-- 11
20 77-1
[1+0}3)
2rju-
| 2/112 - 17
(Txx +
(D((ER-ii
(1-ax]Ak
Autz
Av
b1l - x112 +
- f(x)) - H& (Tx+1) - f(x))
( Dy (T(Txiã
01
(F(
1;
00
A
Ak+1
(1+0)²
0+202
||0x+11 - xx - Ong || - Izk 112
24
7
[1+6}=
201c
2(1+6) Rx
| - xx 11? + 20 20
(1-aeldn 1| - x12-111
(1 (1-ay]b 1x
< 1 211 00| ? + H (f - f(x)) - (Tx++) - f(x)) ((1+>) Dy(Tx::1)
mm
D (I
0m 19 Dy(Tx::Kk) Txk)
dE
A6+1
(1+0)²
0+20"
|| =2ell + 26 26 || - 1122 (1-ma)de
20
11k
(1 (1-ax)dr )2x
(1+0)2)
1 x=1 + H H (x=) - H&& ( - f(()) [(1+>] Dy (x2;
1 (3x
Pnk Dy(Tx Txx)
de
Aut1
(1+0)²
|| xk-1 1| b111x z=12 + Hf f(x)) - HH -(x))) - [(1T7) D DT(xxi 2x))
(1+7)= + (1-au)Ax
10amnk
@+20² [1+0}=]
||: - -1 1 +
20
20
(1-auld,
O
Dy (f( 01k+19 Dj (Txx:: 3.,)
dE
Ak+1
(1+0)²
xR 12-1 21110 2=|2 + -Hs-(((TTk) f(x)) - H& f(x)) (((t)) (T(:
((1 (1+7) + +440(1 + 7)2 - 0+202
(1-002 ) 11 2 + +2202 (1 + +
20
O1
01
(T(Tx::31 3x,)
dE
Ak+1
(1+0)² 29
(1+
0
0²
|| - I& 1|a + 229 1|112 122
(1+0)
(1+0)²)
|z0 x||2 + HH - (f - f(z)) - HI (x - f(x)) - भपोन)ा Dy (T Txk
5x (y( 1) 01
Ax+1 Dy (J): (x)) - -01 xxx 112 + 306 |F Ik ||
1;
|
x=| + H - (J - fxx) - H (T - -xx)
Dy 1 x-1
0 (Tx it)) - =1 | 1 + 20 |
x-- 2
Ax
Akil
2
ff(x)))
| ワ(+ン
Dj (Fzz + )m
where and (c use lines and I (6). i and g use eq. 19): 3 uses line and the inequality
|a +
< 2| + 2 2|bb| d uses the inequality Th S (1 +-) 7) implied by line 11 desc.
remains to use the definition V (x) in eq. 21
A.4 PROOF OF COROLLARY
We can upper-bound b|10 - x:|22 + H HK-I(((TK) - f(x)) as follows:
z:|2 + Hx-I(f(Tx) - -x)))
(x) _ 1 (x)
1110 - x1 + Ho(s(a1) - f(x)) +
8ma A
Dy (2o: + 38 ||:1
xol12
|| x1|² 2 + (o( f(x)) 31100 10 1
16

---

Published as a conference paper at ICLR 2026
x1| +
(1+20)0
(2())) 11 1/ (V/(z)), to - x) + no(((())) - f(x))
2
||:00
x=|² + (1+78) mn
[xo)]] 1/0 Dy vn)
2
|1000
x=| + (n
(mm)]?
2
where a and use eq.
21
b uses Theorem
uses lines
and 7 (c)
use lines
and 6
uses the convexity of f(r).
17

---

Published as a conference paper at ICLR 2026
B PROOFS FOR SECTION 3
B.1 PROOF OF LEMMA
For k 0 have H₁ 1 The inequality Hę 2 Hx-1 is obvious for 2 1 due line II Furthermore, we can upper-bound H3 for l 2 as follows:
H H
Th
H + (1 7) HR-1
where a).
(b) and
(cp use line
11
B.2 PROOF OF THEOREM
We prove the statement of Theorem by induction over K. The base case, K m, is obvious.
Now, we assume that eq. (25) holds for all k E {0,.... K}. where K 2 m, and prove eq. (25) for k K We consider the following cases:
Case 1. (1+ (1+))=mk-1 2 vH -HK-1
Case 2. (1+ 7) < DHK-
Case 2a. УバK = mo (1++1) 7)
Case 2b. УΙK < m1 + +
Case 1. Here we have 7K+1
yHl--rde11 and obtain the following inequality:
1K-1
HK+1
(HK-1 2K-2) + v HK-2
(HRILt HK HK
(AK+1 Hx-2) + HK--
2/
(1K + +1--1) + H HK-
2V1x+11
|KKIIK-- Hgll
+ HK-
/vfKK-1 v HK-
LHK++
Vv (2+7)V + VHK-
Ve
+ c
(K - - -m)
(2+7)VE
VI
VI (K + +1 1
where (a) the inequality HK-2 I HK+1 for K 2 2 2; (b) uses line 11 uses Young's
inequality; uses the assumption 7] PHx A (Case 1) and Lemma (e) uses Lemma
uses the induction hypothesis in eq. 25 (g)
uses the inequality 3e VL
<
(2+>)VL implied by
eq. 24 This proves Case
Case 2a. In this case, it is easy to verify that mo + 7* for all h: E -....., K + 1}. Hence, we can lower-bound Hx+1 as follows:
HK+
K+ (1 + 7) Do
(1+7))<22
(1
K+2
3m(1+>) (1 7) kk+ 2 1
1m(l+
(( -1)
7
(l(l+)) 7
TM (1 3(KK m + 2)) -1) 2
( (K m 2)²
(42)
(K + 2 m)² > ÉK( + 1 m)²
18

---

Published as a conference paper at ICLR 2026
where (a) uses line 11 and the relation 7 = moo(1 + 7)*h above; (b) uses the inequality K 2 and 4e²
Bernoulli's 's inequality; (c) uses the inequality (1 + 7)
ma implied by eq. 24 This proves
Case 2a.
Case 2b. In this case, there exists I E [I..... K} such that yn < (1 + 7)1-11 We choose the largest such index E {L,.... K.. This implics the following relations:
M M-
- and Tis = (1 (1+>)='m for all & E fl....,K K +1.
(43)
Hence, we can upper-bound HK+1 as follows:
Hk+1
P
Hi-1 + Ei= I
m (1 7)² = H1-1 + 11 ((1 + 7) x-12+2 1)
(44)
+ (1+7))-13 Hi-1 S [1t1]/-1+3 k-1+3 H1-1
where (a uses the above relation; (b)
uses the inequalities mn $ (1 + 7) and mn-1 S Hi-1 implied by line I1 Furthermore, can lower-bound ry as follows:
2H 2H
xH 1ilh-1t H: s)
(45)
Hi Hi
where aap uses the relation above; (b) uses lines
3 and
where we define H_2 = Ho: c
uses
Lemma Next, we obtain the following inequality:
(VHKmH - (H-)))
(VHon-VHH.))(E ---Vie VHI-3)
(HHHHI- - -H--I )
Hx+1 -H--1
Hi HI-HI-3
V VBi+VHL-
H841-HL- HH-1 Hi-Hi-
24/Hi 2VH
(((1+)))-4t2-) H4-Hi-3
27 2H/H
2/Hl
((+-)( (12-1)
47L4/HR44HH, Hi
=H (1+y)* (1+))~(12_) 112_1
(1+77) M
((++))x-1+2
vHl ((1 + (11/)/2+1 1)
HI
4L (1+70)))) ((1 + 7) (K (K- 1),
(46)
where (ap uses the inequalities Hi-3 < H1-1 and H: < HK uses the inequalities Hx+1 >
Hi-1 and Hi 2 Hi-3; (c) and (e) use eq. (44); @ use eq. 45
uses Lemma Next, we take
the square root of both sides and obtain the following:
/ HKKI1 H
(1 (1 (K))(2222221111 -
(1)+))((-++)))))) 2/1(++=122+))81
vV
(1+ (0///43/// (1 (1+7))
F(
(1(K + }
2/1(4+7)
(L(K () + 1
(K-1+4)
(47)
(2
19

---

Published as a conference paper at ICLR 2026
where (ap uses the inequality va Va + vb for a, b 2 0: (b) uses Berouuli's inequality; @ch
uses the inequality 2 1; d uses eq. 24 Finally, we obtain the following:
HKK+12 + + (1+ VL KK + +1-m),
where (a) uses the induction hypothesis in eq. the definition H-2 = Hg- This proves Case 2b.
25 for k = -, which also holds for / due to
20

---

Published as a conference paper at ICLR 2026
C
PROOFS FOR SECTION
C.I PROOF OF LEMMA
S
Step We can bouer-
Σ K (v) nu (y(T,;))) as follows: Di=1
Σ
V 74 11
(Z,;,))
2 70. 4(1 + 7) Σ 1 + マाイッ Dj (x(;at)))
< max
78: 4(1 + 7) ( - v++1(x*))
2
max
70, 4(1 + +7) 11(1x'))
2
m18X
2(1 + 7) (1|20 x²11 112 (1 70) [f(()))))) 39
1
max
where @a) uses Theorem I ( uses the fact that 4 (x)) > 0.
which is implied by eq. 21 is
obtained similarly to the proof of Corollary [ in Appendix A.4
Step 2. Next, we prove the following inequality for all k E (O...., K by induction:
[ x
Th
x²'l [|} S (1 + 20) l=
max Jaa 2"||-
(48)
The base case k = 0 is obvious due to line
For k 2 1 we can upper-bound || - x=|| as follows:
1 x=1
x= (1 BN 1 - x=1l
(1 + 20)
max k= K
="I1,
where a uses line 7 the triangle inequality, and Lemma D bb) uses the induction hypothesis in eq. (48) for 1. Next, we can upper-bound
| - x²1l as follows:
[b
x"1
au |ل x²1 + ax) || x='l
0x1
x=
(1 ax (2)+0)
max 1 x²'l
k=
(1 + 0)] x= + a4 10--1 x= + axx((1 20)
max | x=]
k= K"
< (1 + 20)
max | - k= K
where a uses line 9 and the triangle inequality; bb) uses the inequality obtained above; uses
line g and the triangle inequality. This proves eq. (48) Next, using eq. 448 and Corollary we
obtain the following inequality for & {O..... K}:
max { x 112, [ x 11?} < (1 20) (1 x²1 + (1+ )n)
Combining this with the inequality obtained in Step concludes the proof.
C.2 PROOF OF LEMMA
We can lower-bound A follows:
A
min(A(Es, A(T,, [x)}
2D
(z2.2))
min
[V)(2)) V/
2(Lo L, (((xa) 11 max Vf(Tx) Vf( Vf(
(Lo +
maxt
-
T
21

---

Published as a conference paper at ICLR 2026
2
(Lo + [xxVV
x=1
max x* o
x
x0113))
2
(To + / exp(2[,)))
2
Lo exp (1 T - x² ()) exp exp((2,1))
Lo (xxp(,D)(L exp(21,D)
Lg exp(3L,D)
where
a
uses line T0: bb uses eq.
uses Corollary 2.8 of Vankov et al. (022); d and if
use eq.
and
use
Lemma
C.3 PROOF OF LEMMA 7
We can lower-bound D (a 2) for all I, 2 Rd follows:
[Vf(z) - Vf(2))1
(y( 2(Lo + L, Vf(x))]
L. L2 Vf(z)]I
- -
2(Lo + L, + + VL
where (a) uses Corollary 2.8 of Vankov et al. (2024):
: (b) uses the triangle inequality. Hence, we
obtain the following inequality, which is quadratic Vf(() V()))l
[V)()) vf(=) 3I, (2 =) [x)
v/(=)] 2(T, + (z,
Solving this inequality with respect to fz)) f=((=]] gives the following
34, (y (3L, (2), + 8(Lo + L
- <
2
3L, (y( 2(L + / ( Dy
EM
Li [z, 2) + (L0 ( (V{=)
where (a) uses the inequality Va - b < v bb: (b uses Young's inequality. Combining this with the inequalities above gives the following:
(x. 2)
(D.(s.))
V)(())-
2(Lo L / + +3,, Vf(x)) Vf(2))
4
6(Lo T1 [=)] + (x(,22)
max 2L, V [=))] 77 (r,
where a uses eq.
(1] (b) and (c) use the inequalities obtained above. Using this, we can lower-
bound d as follows:
x min(A(Z,, A #+)}
4
9
#111
4
2nax 2L,
where (a) uses line 10 (b) uses the inequality obtained above; (c) uses Lemma 2
22

---

Published as a conference paper at ICLR 2026
C.4 PROOF OF LEMMA
Using the definition of (k) in eq. (36). one can verify that the following inclusion holds:
ka) C {1 S S k: max j E U (()))((0)) S m),
(49)
which implies the first desired inequality. Next, using Lemma and the definition of 72(k) in eq. (36). one veryfy that the following inequality holds for all i (k)::
4
x
(50)
1 (,, (2,-1,
9 max 21, V
Hence, we obtain the following:
2D2
2
2 +
( V 7 11
[1+7]²
ΣiETz(H)
xP (1+7)²
| +
Vă: (1+))
where uses Lemma bi uses line
cc) uses the fact that γ
uses the definition
(k)
Ta(k) {1}: uses the definition of T2(k) in eq. (36) and the fact that H;-2 2 1/-2- Furthermore, using eq. (50p. we can show that the following inequality holds for all T2 T2(
max ( X V/( X (T:; A Dy (ar- 2 8127
(51)
Hence, we obtain the following:
2D2 2 EiET(()
min min(u.y (1+7)²
min 81(1+7)21
(T%(1))),
817
where (a) uses the fact that > 0. remains to use the inequality [T2(k)) s 1 + (T)(
C.5 PROOF OF THEOREM 3
We prove the statement Theorem by induction over K. The base case, K 1, is obvious. Now, assume that eq. (40) holds for all {O...., K), where K 2 1, and prove the inequality in eq. (40) for = T. We consider the following cases:
Case 1. K + 1 Ta(K + + or K +1 Ta(K 1).
Case 2. K + 1 E Ti(K + +).
Case 3. K + 1 E Ta(K + +
Case 3a. [(K + +1) =0.
Case 3b. 1(K 11) E Ti(K + +1)
Case 3c, I(K +1) E TrKK +1).
Case 1. In this case, we can fower-bound / Hk+1 as follows:
HKK+ HK
23

---

Published as a conference paper at ICLR 2026
c VLo
(K - - -
Lp (K 1K + +
[T< 1)] 1),
where a uses Lemma
(b) uses the induction hypothesis in eq. 40); c uses the assumpttion
K + E T2(K
1) 1) and the definition of T2(K 1) and Ta ( + 1) in eq. (36.. This
proves Case 1.
Case 2. In this case, we can bound /H as follows:
HK+1 = VHKILtVBL (Hk-1 - HK-2) + V-VVHK- Hx-
2/HRI1 (HK+1 HK-2) + VHK-2
(NK+1 + 7]-1) + v HH-
0K41RK-1 HK-
Hg+1
PART1 + VHK-2
Hx+1
2ully 11 + VKK-2
9LgHN+1
V2V + HHK-
3(2+2)VLo
36 VLa
+ VHK-2
+ _ (K 2 T2(K 2) 1T 2) 1)
VLa
vLg
c
(K + 1 T2(K 2)| - 1 - -2) -1)
VLo
(K + T2(K + 1) - (T + +-)1-1), 1);
VLo
where (a) and f use Lemma 4 uses line
Young's inequality: and (e) the assumption + (K(K + T) and the definition of Ti(K in eq. (36 dg uses the definition
of e in eq.
(3);
h uses the induction hypothesis in eq. (40 uses the definition of T2(k) and
Ta(k) in eq. (36 This proves Case 2.
=) no- Moreover, since K E Ts(K + m due to eqs. (36) and 37 Besides, since Ti (K + 1) = T2(K + Ø, from eq. (36) we conclude that Ta(K + 1) m 1,..., K 1)
Case 3a. Since I(K + 1) 0, we have [K(K + = T2(K 1) Ø. Hence, from eqs. (36)
and (37 and line 11 we have 7K = (1+
and [K + 1) &' T + 1), we have K +1+1
and TKK 1) m,.. Hence, we can lower-bound / /lk+I follows:
v HHx+
107(1+)) 1
(K m m 2)
Le (K m + 2)
(K + - (K(K + 1)1 Ta(K + 1)1)² Lo
2
La [ + 1 (K(K + 1)1 [4 + -
where (a) is obtained similarly to eq. (42 in the proof of Theorem 2 in Appendix B.2 (b) uses the
definition of m in eq. (39h; (c) uses the fact that TiKK 1) = (1, (1...., "....,m] m) and Tz = Ø as shown above. This proves Case 3a.
Case 3b. Using eqs. (36 and 37 and line 11 we can express 4 as follows:
nK+1 (1+ (K+1) M(K+1)
-Hux=n)-dAxeen RKK41)-2
(52)
24

---

Published as a conference paper at ICLR 2026
Moreover, similar to eq. (44) in the proof of Theorem 2 in Appendix B.2 can upper-bound HK+1 as follows:
Hk+1 S +1)+ ( *
[K+1)-1-
(53)
In addition, similar to eq. (46) in the proof of Theorem 2 in Appendix B.2 and using the definition
of (k) in eq. (36), we can obtain the following inequality:
(VHK+1 HuK+I)-3)
( (1++))(--((1)//2211
(54)
(5Le/>(L++)2++))
where H-2 Ho. and similar to eq. 47) in the proof of Theorem 2 in Appendix B.2 the following inequality:
we can obtain
HKK+ -I---VHiAA HUK++)-32 21
(K 1(K + 1) 4).
(55)
Finally, after rearranging, we can lower-bound
HK+1 as follows:
Hk+1
Huk+1)-3+ (3((((++)))))2)))) (K - I((K + +11 +
Jey
Hi(K+1)-3+ vi (K - 1(K + 1) 4
Via (I(K 11 - - 3 - (T( + 3)1 - (Ta(1(K +1) 3)1 - 1).
(K-I(K +1 + 4)
vio
1K+1-17a(4 K +1) - 3) - 177(1(K +1) - -3] -
Via
(K + (T2 + 1)1 -Ta(K + 1)1 1),
where eq. (55); (b) the definition of in eq. eq. 440
39
uses the induction hypothesis in This proves Case 3b.
d
uses the definition of (k) and (k) in eq.
36
Case 3c. Similar to eq. (46) in the proof of Theorem Appendix B.2 and using Lemma 6 can obtain the following inequality:
(VHK+1 (HRKHN)-)) 2
MAmin
(1++))K-K((tD))222
4 (1(++)))+73
(1+m)))+
(K-K))
(11((++)(2+)))
(1+7)=73
18la//(1++)(2tm))
(1 (K
184 18L0 (1L0)/(+++)222)))
where H-2 = Ho, and (a) uses the definition of m in eq. (39 (b) uses the fact that K K-IKK ([K+1) +1)
m, which is implied by the assumptions K + E Ta [ 1) and I(K + Te(K + 1). and
eq. 36). After taking the square root from both sides of the inequality, we obtain the following:
V HH*+ / HHIK+1)-
ve
(1+ (K(K)))))
(K+=)(K-1KK+))0//88 -1)
(((()))))
(K- - (1+
3 112411+
Jey
(K I(K + 1) 4):
213/49(17))12-777)
where (a) uses the inequality Va 2 Va +b - vb; bb uses Bernoulli's inequality. The rest of the proof is identical to the proof of Case 3b.
25

---

Published as a conference paper at ICLR 2026
C.6 PROOF OF COROLLARY 3
We can upper-bound D as follows:
max
700 2(1 + 71, =0)2 -1 + (1+ ff(x)))
max
70: 20 +1, +202]
(1200 - ==11++++ + v(1 70)m (
max
700 2(1 + 7)) 20)²
(1 (1+ (1 + 7
11 ( ||a0 x=1l
max
70: 21 +7),(1 (1 20)²
(1 (1 + 70) exp(I1 - x =)))]] - x²1l
max 7/0 2( + 7), (1+ + 20) (2 + 10) --'1 x"1l
O x=1) II),
where (a) uses eq. (33: (b) uses the incquality va+b vā+ vb; e uses eq.
31 (d) uses the
inequality cxp(t) < exp(tt), which is implied by the convexity of the function f + cxp(t);
uses the assumption Lo exp(-L1l)) - x²))). It remains to combine Corollary Lemma
and Theorem 3
26


Reviews:
[{"review_id": "igJwJTXJzy", "reviewer": "Reviewer_aKbR", "summary": "This paper studies a GRAAL-based adaptive variant of Nesterov’s accelerated gradient method for smooth convex minimization. Unlike other recent adaptive methods, this approach allows the step size to grow linearly, which is particularly useful when the algorithm is initialized with a very small step size. This feature becomes even more important under the more general $(L_0,L_1)$-smoothness condition, where the local curvature may change at an exponential rate.", "questions": "- (10): The definition of $D_f$ is missing.\n- L181: It seems that Option II can better exploit the properties of the objective function, but I recommend providing a more precise statement.\n- L207: Could the authors clarify how the extrapolation enables adaptive capabilities?\n- L226: The definition of $\\Lambda$ is missing.\n- L322: Wouldn't a small $\\eta_0$ slow down the empirical performance?\n- L461-462: The initial step size is required to satisfy $\\eta_0 \\le \\frac{1}{L_0\\exp(L_1||x_0-x^*||)}$, and the authors suggest choosing a very small value, which effectively makes the method free from hyperparameter tuning. The authors also note that a concurrent work by Tyurin (2025) provides a similar result but requires additional hyperparameter tuning. However, if one apply the same principle (choosing an extremely small or large constant), couldn't Tyurin's method also be regarded as tuning-free? This is what I inferred after reading Section 4 of Tyurin (2025). I would appreciate clarification on this point.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- As clearly summarized in Table 1, this paper proposes the first adaptive accelerated method that achieves the optimal rate under convexity and $(L_0,L_1)$-smoothness.\n\n- Even under the standard smoothness assumption, the proposed adaptive accelerated method allows the step size to grow linearly, unlike existing methods, which is particularly beneficial when the initial step size is small.", "weaknesses": "- Although this is primarily a theoretical paper, including a simple toy experiment would make the contribution more informative. (This is not a requirement for acceptance, but a suggestion to strengthen the paper.)\n\n- I would appreciate it if Section 4.1 provided a higher-level sketch of the main idea.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "DpP2TIe3G6", "reviewer": "Reviewer_BGKs", "summary": "This paper develops an accelerated variant of the GRAAL algorithm that achieves near-optimal iteration complexity for convex optimization while maintaining adaptive stepsize capabilities. The main contribution is Algorithm 1 (Accelerated GRAAL), which incorporates Nesterov acceleration while adapting stepsizes to local curvature at a geometric rate. The authors conduct convergence analysis of the proposed algorithm for $L$-smooth and $(L_0, L_1)$-smooth functions. The key technical innovation is an \"additional coupling step\" that allows adaptive choice of acceleration parameters $\\alpha_k$ without requiring predefined sequences or restricting stepsize growth.", "questions": "1. How does the algorithm perform empirically compared to AC-FGM, AdaNAG, and non-accelerated GRAAL? \n\n2. Could you provide explicit $(\\theta,\\gamma,\\nu)$ values that satisfy the required inequalities, and a recommended default $\\eta_0$?\n\n3. Because the method introduces several iterates ($x_k, \\bar{x}_k, \\hat{x}_k, \\tilde{x}_k$) and requires multiple gradients for curvature estimation, the peak memory can exceed that of standard AGD. Have you considered memory-efficient implementation of the proposed algorithm?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The additional coupling step is a novel technique that elegantly enabling acceleration and adaptive step-size growth in one framework.\n\n2. The analysis is layered and rigorous: a general potential-descent framework for convex $C^1$ objectives, followed by rate results for $L$-smooth and $(L_0,L_1)$-smooth settings. The bounds are near-optimal and adapt to unknown curvature, with only logarithmic dependence on the initial stepsize guess in the $L$-smooth case.\n\n3. The paper clearly states its target question, the design obstacles, and how each algorithmic components (extrapolation, coupling, curvature estimation) addresses them.", "weaknesses": "1.  Lack of empirical validation. The paper presents no experiments. Small-scale benchmarks (logistic regression, least-squares, GLMs, robust convex losses) would verify geometric step-size growth in practice, overhead of computing $\\Lambda$, and wall-clock speedups versus other algorithms.\n\n2. The theory requires universal constants $(\\theta, \\gamma, \\nu)>0$ satisfying equation (19), but the paper does not provide guidance on how to choose these parameters in practice. This is a significant practical limitation. The paper should provide at least one explicit set of valid parameters and discuss how parameter choices affect the hidden constants in the O(·) notation.\n\n3. Results cover smooth convex minimization only; there is no composite/prox extension, constraint handling, or analysis with stochastic/inexact oracles.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "WZbnMm8hmx", "reviewer": "Reviewer_A1cJ", "summary": "The paper allows exponential growth of the stepsize for adaptive accelerated gradient method. The results show true adaptivity of the method under the generalized smoothness.", "questions": "-", "limitations": "", "rating": 10, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper solves the issue with explicit (no backtracking) adaptive accelerated methods  -- they cannot increase the stepsize fast.\n\nDetailed comparison with related works.", "weaknesses": "Despite experiments would be quite predictable it would be interesting to see a comparison with adproxgd and optimizers with backtracking beyond the standard smoothness. Not a real weakness, for the sake of comprehensiveness, the theoretical contribution is solid enough.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "EnR4vDYj29", "reviewer": "Reviewer_E3U6", "summary": "This paper proposes an accelerated adaptive method that can estimate the local Lipschitz constant of the gradients adaptively. It is based on a series of recent papers that use the difference of gradients or other empirical quantities to estimate the Lipschitzness of gradients. This work isn't the first to introduce an accelerated adaptive method like that, but it is the first one where the stepsize estimate can change by a constant non-decreasing factor. The authors prove convergence guarantees for $L$-smooth as well as $(L_0, L_1)$-smooth problems, claiming complexity improvements. The paper features strong theoretical results, but it doesn't present any numerical validation of the proposed method's performance.", "questions": "1. The authors wrote that $\\theta$, $\\gamma$, and $\\nu$ should satisfy equation (19), but it's not obvious from looking at the equation what possible values we can select from. Could you please provide at least explicit example in the paper?\n2. The complexities in Table 1 for Algorithm 1 and for the method of Tyurin (2025) are different in the power of $L_1 \\mathcal{D}$. Is the optimal complexity known for this term? Is the result of Vankv et al. (2024) optimal? Do the authors believe their complexity is worse because it's a limiation of the analysis or of the method itself?\n3. When discussing AdGD for $(L\\_0, L\\_1)$ functions, the authors wrote \"In fact, $\\mathcal{D}$ also contains the initial objective function gap $f(x\\_0) − f(x^\\*)$, and hence, it may have an exponential dependency on the initial distance $\\Vert x\\_0 − x^\\*\\Vert$.\" However, it seems that the proof of Corollary 3 actually also shows an exponential dependency on $\\Vert x_0 − x^*\\Vert$, which is then removed by assuming $\\eta\\_0 L\\_0 \\le \\exp(-L\\_1 \\Vert x\\_0 - x^\\* \\Vert)$. Isn't it an unfair comparison?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The work is undeniably strong theoretically. The authors propose a method that is more adaptive than other accelerated methods, which is an important consideration for its practical performance. It is also clear that deriving the method and its convergence guarantees was no easy task. The algorithmic design can be insightful for future developments of other adaptive methods.\n\nI also think the proposed method can be quite useful for deterministic convex optimization on its own. While convex optimization is a less popular area of applications these days, I still find it a valuable contribution since such problems arise in a lot of applications.", "weaknesses": "1. The method unfortunately requires the ability to compute functional values, unlike the prior work on GRAAL and AdGD.\n\n2. In terms of complexity, there is no realy improvement upon the work of Li & Lan (2025). As the authors mention, the approach of Li & Lan (2025) is to use a line-search at the first iteration, which introduces only an additive term in the complexity, while guaranteeing that $\\eta_0 L \\ge 1$, so it doesn't affect the complexity in a multiplicative way. I don't see any limitation of this approach since both works require the use of functional values anyway. That being said, the proposed new method still may benefit a lot from updating the stepsize more adaptively in practice.\n\n3. It's a bit unfortunate there is no numerical insights in this paper.\n\n4. I found the discussion in Section 4.1 to be extremely hard to follow, especially Lemma 7. The four sets of indices are introduced without being properly explained, not to mention the third and the fourth sets use $l(k)$, whose meaning is even less obvious. It's completely unclear why these sets are introduced and what we should expect them to be. Moreover, it would be useful to remind the reader of the definition of $m$ around Lemma 8 as it's not used anywhere prior to that except for Theorem 2. It's also very confusing that the authors redefine $m$ in Theorem 3. To summarize, this section is extremely technical and would benefit from a rewrite that makes it more intuitive.\n\n5. The way the proofs are structured in the appendix makes reading them a tedious and a strongly challenging endeavour. I wish the authors chopped it into pieces with intuitive steps, rather than just giving the bounds all as a single huge inequality. I just couldn't make myself go through all the steps to check them even though I wanted to understand the proof.\n\n## Minor typos\n\"$f(x) \\colon \\mathbb{R}^d \\to \\mathbb{R}$\" should be \"$f \\colon \\mathbb{R}^d \\to \\mathbb{R}$\"  \n\"Hence, it is rarely used in practice.\" I don't think this statement is true, many convex problems are still solved with line-search based methods  \n\"It is well known that AdaGrad has the complexity of GD in eq. (3) for L-smooth functions (Levy et al., 2018)\". I think it needs a clarification here that the results of Levy are only for bounded domains. It is also worth mentioning that the update in (5) misses the $G^2$ constant inside the square root, which is important for non-smooth convergence results.  \nI think when introducing (6) and (7) it would be educational for the reader if the authors provided values of $\\gamma$ and $\\nu$ that have theoretical guarantees.  \n\"Suh & Ma (2025) uses a stepsize\" -> \"Suh & Ma (2025) use a stepsize\"  \nSome small issues in the citations: \"Jonathan M Borwein\" -> \"Jonathan M. Borwein\", \"in banach spaces\" -> \"in Banach spaces\", \"barzilai and borwein gradient\" -> \"Barzilai and Borwein gradient\", etc.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Poster)