Directional Smoothness and Gradient Methods: Convergence and Adaptivity
Authors: Aaron Mishkin
Ahmed Khaled
Yuanhao Wang
Aaron Defazio
Robert M. Gower
Venue: NeurIPS 2024 poster (2024)
Keywords: directional smoothness
gradient descent
exponential search
polyak stepsize
normalized gradient descent
Primary area: optimization
TL;DR: We derive new convergence rates for gradient descent which depend only on local properties of the objective using directional smoothness.

Abstract: We develop new sub-optimality bounds for gradient descent (GD) that depend on the conditioning of the objective along the path of optimization, rather than on global, worst-case constants.  Key to our proofs is directional smoothness, a measure of gradient variation that we use to develop upper-bounds on the objective.  Minimizing these upper-bounds requires solving implicit equations to obtain a sequence of strongly adapted step-sizes; we show that these equations are straightforward to solve for convex quadratics and lead to new guarantees for two classical step-sizes.  For general functions, we prove that the Polyak step-size and normalized GD obtain fast, path-dependent rates despite using no knowledge of the directional smoothness.  Experiments on logistic regression show our convergence guarantees are tighter than the classical theory based on $L$-smoothness.

Directional Smoothness and Gradient Methods: Convergence and Adaptivity
Aaron Mishkin"
Ahmed Khaled Princeton University
Stanford University
amishkin@cs.. stanf ord. edu
ahmed khaleedpriinctonn.oo edu
Yuanhao Wang Princcton University yuanhaoa@princetonn edu
Aaron Defazio FAIR, Meta AI adef azio@meta. com
Robert M. Gower
CCM. Flatiron Institute
gowerrobert@gmail.. com
Abstract
We develop new sub-optimality bounds for gradient descent (GD) that depend on the conditioning of the objective along the path of optimization rather than global, worst-case constants. Key to our proofs is directional smoothness, measure gradient variation that we these upper-bounds requires solving implicit equations to obtain a sequence straightforward to
develop upper-bounds the objective. Minimizing
strongly adapted step-sizes; we show that these equations solve for convex quadratics and lead to new guarantees for two classical step-sizes. For general functions, prove that the Polyak step-size sieesize and normalized GD obtain fast, path-dependent rates despite using no knowledge the directional smoothness. Experiments on logistic regression show convergence guarantees are tighter than the classical theory based on I-smoothness.
Introduction
Gradient methods for differentiable functions are typically analyzed under the assumption that is L-smooth, meaning f is L-Lipschitz continuous. This condition implies f is upper-bounded by quadratic and guarantees that gradient descent (GD) with step-size 2/ decreases the optimality gap at each iteration (Bertsekas, 1997). However, experience shows that GD can still decrease the objective when f is not L-smooth, particularly for deep neural networks (Bengio, 2012) Z. Li et al., 2020. Cohen et al. al., 202T). Even for functions verifying smoothness, convergence rates are often pessimistic and fail to predict optimization speed in practice (Paquette et al., (003)).
One alternative global smoothness local Lipschitz continuity of the gradient ("local smoothness"). Local smoothness assumes different Lipschitz constants hold for different neighbourhoods which avoids global assumptions and improves rates. However, such analyses typically rely on boundedness of the iterates and then use local smoothness to obtain L-smoothness over a compact set (Malitsky and Mishchenko, 2020). Boundedness is guaranteed in several ways: Junyu Zhang and Hong (2020) break optimization into stages, Patel and Berahas (2022) use stopping-times, and Lu and S. Mei (2023) employ a tine-search, Unfortunately. these approaches modify the underlying optimization algorithm, require local smoothness oracles (Park et al., 2021) rely on highly complex arguments.
In contrast, we prove simple rates for GD without global smoothness by deriving bounds of the form,
M T3.
f(x+11) $ f(xx) +
2k) +
| I& 112
(1)
2
"Equal contribution.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

ionosphere
mammographic
Optimality Gap
102-
10-2
10-6
10"
10-10 10
10-2
50
100
150
200
10
20
30
40
Iterations
Iterations
1/M .F))
Polyak Bound (L-Smooth) Bound ()M(( Bound (Polyak)
Figure 1: Comparison of actual (solid lines) and theoretical (dashed lines) convergence rates for GD with (i) step-sizes strongly adapted to the directional smoothness (77- = 1/ 2x)) and (ii) the Polyak step-size. Both problems are logistic regressions on UCI repository datasets (Asuncion and Newman, 2007). Our bounds using directional smoothness are tighter than those based global L- smoothness f and adapt to the optimization path. For example, on mammographic our theoretical rate for the Polyak step-size concentrates rapidly exactly when the optimizer shows fast convergence.
where the directional smoothness function M (I 2x) depends only on properties of f along the chord between Iy and T&+1- Our sub-optimality bounds provide path-dependent perspective GD) and are tighter than conventional analyses when the step-size sequence is adapted to the directional smoothness, meaning 7i < (/ .Kk) . See Figure I for two real-data examples highlighting our improvement over classical rates. We summarize all our contributions as follows.
Directional Smoothness. We introduce three constructive directional smoothness functions M (x, y). The first, point-wise smoothness, depends only on the end-points y, and is easily computed, while the second, path-wiss smoothness, yields a tighter bound, but depends on the chord C = {az + (1 a)y: : [0, 1]]. The last function, which we call the optimal point- wise smoothness. is both casy-to-evaluate and provides the tightest possible quadratic upper bound.
Sub-optimality bounds. We leverage directional smoothness functions to prove sub-optimality bounds for GD on convex functions. Our bounds are localized to the GD trajectory, hold for any step-size sequence, and are tighter than the classic analysis using Z-smoothness. They are also more general since we do not need to assume that f is globally L-smooth to show progress; all we require a sequence of step-sizes adapted to the directional smoothness function. Furthermore, our approach extends naturally to acceleration, allowing us to prove optimal rates for (strongly) (rrongly)-convex, -convex functions.
Adaptive Step-Sizes in the Quadratic Case. In the general setting, computing step-sizes which adapted to the directional smoothness requires solving a challenging non-linear root-finding problem. For quadratic problems, show that the ideal step-size that satisfies V) 1/M (Ix+1 .x is the Rayleigh quotient and is connected to the hedging algorithm (Altschuler and Parrilo, 2023).
Exponential Search. Moving beyond quadratics, prove that the equation 7) = 1/M(TA- (I&+1.2))
admits solution under mild conditions, meaning ideal step-sizes can be computed using Newton's method. Since computing these step-sizes is typically impractical, we adapt exponential search (Carmon and Hinder, 2022) to obtain similar path-dependent complexities up to a log-log penalty.
Polyak and Normalized GD. More importantly, we show that the Polyak step-size (Polyak, 1987) and normalized GD achieve fast, wath-dependent rates without knowledge of the directional smoothness. Our analysis reveals that the Polyak step-size adapts to any directional smoothness to obtain the tightest possible convergence rate. This property not shared by constant step-size GD and may explain the superiority of the Polyak step-size in many practical settings.
1.1 Additional Related Work
Directional smoothness is a relaxation of non-uniform smoothness (J. Mei et al., 2021), which restricts the smoothness function M to depend only on 2, the origin point. J. Mei et al. (2021) leverage non-uniform smoothness and a non-uniform Lojasiewiez inequality to break lower-bounds for first-order optimization. Similarly, Berahas et al. (2023) show that weak local smoothness oracle can break lower bounds for gradient methods. A major advantage of our work over such oracle-based approaches is that we construct explicit directional smoothness functions that are easy to evaluate.

---

Similar to non- con-uniform smoothness, Grimmer (2019) and Orabona (2023) consider Hölder-typp growth conditions with constants that depend on neighbourhood of z. Since directional smoothness is stronger than and implies these Hölder error bounds, our M functions can be leveraged to make their results fully explicit (the Hölder bounds are non-constructive) Finally, while they also analyze normalized GD, our rates are anytime and do not use online-to- tiiine-to-batte ho-batch reductions like Orabona (2023).
Directional smoothness is also related to (Lo, L1) >smoothnesss (Jingzhao Zhang et al., 2020; B. Zhang et al., 2020), which can be interpreted as a directional smoothness function with exponential depen- dence on the distance between and y. The extension of (Lu, Lmmssoothsssss to (r. 1) -ssmoohhnsss by H. Li et al. (2023) shows how to bound sequences of such directional smoothness functions, even for accelerated methods. These approaches are complementary to ours and showcase a setting where directional smoothness leads to concrete convergence rates.
Our work is most closely connected to that by Malitsky and Mishchenko (2020), who use smoothed version of M y) to set the step-size. Vladarean et al. (2021) apply a similar smoothed step-size scheme primal-dual hybrid gradient methods, while Zhao and Huang (2024) relate directional smoothness to Barzilai-Borwein updates (Barzilai and Borwein, 1988) and Vainsencher et al. (2015) use local smoothness over neighbourhoods of the global minimizer to set the step-size for SVRG.
Finally, we note that adaptivity to directional smoothness is different from adaptivity to the sequence of observed gradients obtained by methods such Adagrad (Duchi et al., 2010]] Streeter and McMahan, 2010). Adagrad and its variants are most useful when the gradients are bounded, such as in Lipschitz optimization, although they can also be used obtain rates for smooth functions (Levy, 2017).
We do not address adaptivity to gradients in this work.
Directional Smoothness
We say that a convex function I' is L-smooth if for all x.y E Rd.
(wv) < f(x) (VI(z),y - 2) +
Minimizing this quadratic upper bound in y gives the classical GD update with step-size mh = L/L. However, this viewpoint leads to rates which depend on the global, worst-case growth of f. This is both counter-intuitive and undesirable because the iterates of GD, Zk+11 2₁ - 7 fxx)). depend only on local properties of f. Ideally, the analysis should also depend only on the local conditioning along the path {x1, (2,,,2,,... Towards this end, we generalize the smoothness upper-bound as follows.
Definition 2.1. We call M: : Rddd + R directional smoothness function for f if for all x, e Rd.
M(x, v) Bly
f(v) <
2
If a function is L-smooth, then M(x, y) = T. is trivial choice of directional smoothness function. In the rest of this section, we construct different M functions that provide tighter bounds on f while still being possible to evaluate. The first is the point-wise directional smoothness,
D( = 2 2 - ()(2)
11y 2
Point-wise smoothness is a directional estimate of L and satisfies D(x, < 2L. Indeed, L can be cquivalently defined as the supremum of D(x, n)/2 over the domain of ʃ (Beck, 2017 . If ʃ is convex and differentiable, then D(z, y) is a directional smoothness function according to Definition 2.1 Lemma 2.2. If f is corvex and differentiable, then the point-wise directional smoothness satisfies,
f(y) S f(x) (Vf(2),))))))))))))(())))))) 2) + D(x,y) v) lly x:12.
See Appendix A (we defer all proofs the relevant appendices). In the worst-case, the wise directional smoothness D is weaker than the standard bouer M M v) = L by a factor of two. This is not an artifact of the analysis and is generally unavoidable, as the next proposition shows. Proposition 2.3. There exists a convex, differentiable I and x, E Rd such that ift < 2, then
y f(y) > f(x)+ + (Vf(o), - x) [[] - vs(y)) ly - x x122.
(6)
2 y x1|2
3

---

Actual Progress
L- L-Smooth
Mr fe-Smooth
Lk+1
f(x)
Figure 2: Illustration of GD with 7k 1/L. Even though this step-size exactly minimizes the upper-bound from I-smoothness, M& directional smoothness better predicts the progress of the gradient step because Mj. < L. Our rates improve on T-smoothness because of this tighter bound.
While the point-wise smoothness is easy compute, this additional factor of can make Equa- tion ( looser than L-smoothness - on isotropic quadratics, for example. As an alternative, we define the path-wise directional smoothness,
A(z, v)
sup
(7)
tE|o.1]
and show verifies the quadratic upper-bound and satisfies Definition 2.1 Lemma 2.4. For any differentiable function J, the path-wise smoothness satisfies
even without convexity.
f(v) +V)()(((())))))))))))))))))))))) x) A(z, v) 11v x:12-
(8)
Path smoothness is tighter than point-wise smoothness since A(x, y) S (zx, v), but hard to compute because it depends on the chord between a and y. That is, it depends on the properties of f on the line (Ir + (1 - f)y & E [0. }]} rather than solely on the points x and y like the point-wise smoothness.
Point-wise and path-wise smoothness are constructive, but they may not yield the tightest bounds in all situations. The tightest directional smoothness function, which we call the optimal point-wise smoothness, is the smallest number for which the quadratic upper bound holds,
fly) f(x) (Vf(z). vv).=).var x>)
H H y)
lly x 1|
By definition, H is the tightest possible directional smoothness function; it lower bounds any constant C' that satisfies the quadratic bound 2 Thus, Hxx,)) v) < Mx.,, y) for any smoothness function M.
The directional smoothness functions introduced in this section represent different trade-offs between computability and tightness. The optimal wise smoothness H y) requires access to both the function and gradient values, whereas the point-wise only access to the gradients and convexity. In contrast, the path-wise direction smoothness A(x, v) satisfies Lemma 2.4 with or without convexity, but may be hard to evaluate.
D(r, () requires
Path-Dependent Sub-Optimality Bounds
Using directional smoothness, we obtain descent lemma which depends only on local geometry,
f(xx+1) (f(x)) -(1p 1) (
(10)
2
See Lemma A.1 If Th < 2/M (K41 1,, then GD is guaranteed to decrease the function value and we call 77 adapted to M (1 Fx+1). However, computing adapted step-sizes not always straight- forward. For instance, finding 7 1/M #141 (7))) requires solving non-linear equation.
The rest of this section leverages directional smoothness to derive new guarantees for GD with arbi- trary step-sizes. We emphasize that these results are sub-optimality bounds, rather than convergence rates; a sequence of adapted step-sizes required convert our propositions into convergence theory. As a trade-off, our bounds reflect the locality of GD, rather than treating it global method.

---

We start with the case when f has lower curvature. Instead of using strong convexity or the PL- condition (Karimi al., 2016). we propose the directional strong convexity constant,
(V((at(y==))-V(aaa
p(z, y) inf
(11)
te[0,1]
-
If f is convex, then p(z, y) 2 and verifies the standard fower-bound from strong convexity,
(v) ((x) + (VS(x), 2) p1z, v)
lly -
(12)
2
Moreover, we have pl y) 2 μ when f is p-strongly convex. We prove two bounds for convex functions using directional strong convexity. For brevity, we denote M; == M (I;, Ti+1), 1. Pi == (1 x²), ) 6 = f(x,) f(x*), and A; = I x11 where I" is a minimizer of f. Proposition 3.1. If f is convex and differentiable, then GD with step-size sequence {nk} satisfies,
5% <
II (1 +m
60 + +
II (1 1b
16 2
(13)
LEg
VEB
where n G {i: f < 2//Mi), and B = [K]]G.
The analysis splits iterations into good steps G, where m7s is adapted to the directional smoothness, and bad steps B, where the step-size is too large and GD may increase the optimality gap. When is L-smooth and justtrongly convex, using the step-size sequence 7e = =1/1. gives
) )
f(xx+1) - f(x") <
II
(1-
1
Mi (2
(f(x))- - ff(=))
(14)
L
13) gives at least as tight rate as standard assumptions by localizing to the convergence path using any directional smoothness M. When M; < L, the gap in constants yields a strictly improved rate (see Figure We also prove a more elegant bound. Proposition 3.2. If f is convex and differentiable, then GD with step-size sequence {nk} satisfies,
where μ4 (2 M./L) μ. Thus, Equation
A
II ===
pmmdl
Ao
Σ
157yl P5+17
(Mm ni
Vf(x))
(15)
M4417
1+ +++11
Unlike Proposition 3.1 this analysis shows linear progress each iteration and does not divide into good steps and bad steps. In exchange. the second term in Equation (15) reflects how much convergence is degraded when yJs is not adapted to the directional smoothness function M. We conclude this section with bound for when there is no lower curvature, meaning μ4; =0 0.
Proposition 3.3. Let Ix = EE m/ =
/
Th- If f is convex and differentiable, then GD satisfies,
120 - 13 Σ
(n - /)
f(zx)- - f(x)) I
(16)
2 3Σ T
2 2 T
Eq. (16) is faster than standard analyses whenever M, < L; it will be a key tool in the next sections.
3.1 Path- Path-Dependent Acceleration
Now we show that directional smoothness can also be used to derive path-dependent sub-optimality bounds for accelerated algorithms that is, methods obtaining optimal rates for smooth, convex optimization. In particular, we study Nesterov's accelerated gradient descent (AGD) (Nesterov, (983)) and prove that directional smoothness leads to tighter rates given adapted step-sizes. Throughout this section we assume that f is u-strongly convex with μ 0 when f is merely convex.
Although our analysis uses estimating sequences (Nesterov et al., 2018), we state AGD in the following "momentum" formulation, where y) the momentum and og the momentum parameter,
1k+1 = y/ 7h (2()
a2 =(1 -kk++))0 )ak 7k+1 + 174+1044+144
7)
(17)
ax -ox)
Uk+1 = Tk+1 +
( Ix))
2
+ ax+1
5

---

If Th I
then Equation (10) combined with 1 Max xx+11/2 2 1/2 implies,
[(x+1)) S f(y=) - The V l1
(18)
Our analysis leverages the fact that this descent condition for 2x+1 is the only connection between the smoothness of and the convergence rate of AGD. Since Equation (18) depends only on the step-size V|,, we replace I. within the analysis of AGD with sequence of adapted step-sizes. The following theorem controls the effect of these step-sizes to obtain path-dependent bounds.
Theorem 3.4. Suppose f differentiable, j-strongly convex and AGD is run with adapted step-sizes Wh S 1/Ma. 1f > O and Org = /molt, then AGD obtains the following accelerated rale:
f(#++1) - f(x))())+)))))))))))
11 II /imm) [f(zo) f(x²)= + " |1:00 x= ==113 i=0
(19)
Let Mmin minkelM lhe 1f 2 0 and on E V/rio c), where e is the maximum value of ora for which
aa-100ou sattisfees "tu M/mii + μ4, then AGD obtains the following rate: Y/ m0(1-a0)
[(xx+1) [(x)) Thmin (1) + 1)2 [s(n)) - [(x') ++ + 70 1 x 2=1
4
(20)
If m/ = 1/M > 1/L, then these rates are strictly faster than those obtained under L-smoothness and Theorem 3.4 shows that AGD provably benefits from taking the largest possible steps given the local geometry of f. However, obtaining accelerated rates when μ = 0 requires prior knowledge of the minimum step-size; while this is straightforward for L-smooth functions, it is clear how to extend such result to non-strongly convex acceleration with locally Lipschitz gradients. For example, while H. Li et al. (2023) show that the (r, -)ssmoothssss (a valid directional smoothness function) is bounded over the iterate trajectory, their rate does not adapt to the optimization path.
4 Adaptive Learning Rates
Converting our sub-optimality bounds into convergence rates requires adapted step-sizes satisfying Th < 2/M (zt, Given an adapted step-size, the directional descent lemma (Equation (10) implies GD decreases I and we can obtain fast rates if the step-sizes are bounded below. However, Jk+1 is itself a function of 17k, meaning adapted step-sizes are not straightforward to compute.
For L-smooth f, the different directional smoothness functions M introduced in Section 2 satisfy M (22,, I S 2L. This implies Tek- < + is trivially adapted. As such step-sizes don't 't capture local properties of f, we introduce the notion of strongly adapted step-sizes, which satisfy
1/M (1))) 2x)-
(21)
Equation 10 implies GD with a strongly adapted step-size makes guaranteed progress as,
[(xx+1) f(xx) (2M
[ (V
|
(22)
This progress is greater than that guaranteed by T-ssooothness when ( (x*1, < L. and holds when f is not T-smooth. However, it is not clear a priori if (i) strongly adapted step-sizes exist or if (ii) any iterative method achieves the progress in Eq. (2T). Surprisingly, we provide a positive answer both questions. Strongly adapted 77& are computable and we also prove GD with the Polyak step-size adapts to any choice of directional smoothness, including the optimal point-wise smoothness. Before presenting this strong result, we consider the illustrative case of quadratic minimization.
4.1 Adaptivity in Quadratics
Now we show that step-sizes adapted to both the pisnt-wise smoothness M and the wash-wise smoothness A exist when f is quadratic. Let fx) Bx/2 c where B is positive semi- definite. Assuming {ma} is strongly adapted to the directional smoothness, Equation (16) implies
|00 - r 11
1000 x
|1:0 x² 2-112 E
M M( 2441)
f(zx) f(x')
(23)
2
2
Di=o h
2(k
k
M(

---

Optimality Gap
Point-Wise Smoothness
Adapted Step-Sizer Sizes
10a
10
10a
10a
10
10a 10
10a
10
10a
10
10
Iteration
Iteration
lteration
1/Dx
1/Ax
2/L
Figure 3: Performance of GD with different step-size rules for a synthetic quadratic problem. We run GD for 20,000 steps on 20 random quadratic problems with L 1000 and Hessian skew. Left- to-right, the first plot shows the optimality gap f(xx) - f(**) ), the second shows the point-wise directional smoothness ( and the third shows step-sizes used by the different methods.
where we used M;MM; = 1 as well as Jensen's 's inequality. This guarantee depends solely on the average directional smoothness along the optimization trajectory {ar, :1.... When f is quadratic, we can exactly compute these smoothness constants. In particular, the point-wise directional smoothness is,
((4, = 2|| (2
Notably, (a, (441) has no dependence on -,-1 and the corresponding strongly adapted step-size given by 77, [ BV ((:))ll) see Lemma C.I Remarkably, this expression recovers the step-size proposed by Dai and Yang (2006), who show it approximates the Cauchy step-size and converges to the "edge-of-stabilit"
(J. Cohen et al., 2021 at 2/L as k + co. Combining this simple expression with Equation (23) gives a fast, non-asymptotic convergence rate for GD and new theoretical justification for their work.
We can also compute the path-wis wise directional smoothness in closed form. As Lemma C.2 shows.
A x+41) = fz())) BV(())) Vff(),
(( (x;)] is the well-known Cauchy step-size. Path-wise directional smoothness thus provides another interpretation (and convergence guarantee) for the Cauchy step-size, which is traditionally derived by minimizing f(x - 1/ fz)) in 17.
and
4.2 Adaptivity for Convex Functions
In the last subsection, proved that strongly adapted step-sizes for the point-wise and path-wise directional smoothness functions have closed-form expressions when f is quadratic. Moreover, these step-sizes recover two classical schemes from the optimization literature, giving them new justification and fast convergence rates. Now we consider the existence of strongly adapted step-sizes for general convex functions. Our first result gives simple conditions for Equation (2I) to have at least one solution when M is the point-wise directional smoothness.
Proposition 4.1. If is convex and continuously differentiable, then either (i) f is minimized along the ray (())
V I (x) or (ii) there exists 1 satisfying v 1/D( (VV((x)
The next proposition uses a similar argument with slightly stronger conditions to show existence of strongly adapted step-sizes for the path-wiz wise smoothness.
Proposition 4.2. If is convex and twice continuously differentiable, then either (i) is minimized along the ray z(n) I v/ fx) or (ii) there exists > O satisfying 1 = 1/A(z, x v/ fx)).
Propositions 4.1 and 4.2 not assume the global smoothness; although neither proof is constructive, it is possible to compute strongly adapted step-sizes for the point-wise directional smoothness using root-finding methods. We show in Section 5 that if f is twice differentiable, then strongly adapted step-sizes can be found via Newton's 's method using only Hessian- vestoor products, 4 (z))))
4.2.1 Exponential Search
Now we show that the exponential search algorithm developed by Carmon and Hinder (2022) can be used to find step-sizes that adapt average to the directional smoothness. Consider fixed
7

---

optimization horizon k and denote by (1(n) the sequence of iterates obtained by running GD from 2o using a fixed step-size 17. Define the criterion function,
E (n))
(n)
(24)
E.= (n) 2+41 (
and suppose that we have a step-size 7i that satisfies (n))22 2 S 1 S (n). Using these bounds in Proposition 3.3 yields the following convergence rate,
f(T)) - f. - T MI Elzo VVS())
10 x²
(25)
While n does not adapt to each directional smoothness M 11+1) along the path, adapts to a weighted average of the directional smoothness constants, where the weights are the observed squared gradient norms. This is always smaller than the maximum directional smoothness along the trajectory and can be much smaller than the global smoothness. Furthermore, we have reduced our problem to finding 7) E [d)(n)/2 (n)).. which is similar to the problem Carmon and Hinder (2022) solve with exponential search. We adopt their approach Algorithm I and give convergence guarantee.
Theorem 4.3. Assume f is convex and L-smooth. Then Algorithm / with 7/o > 0 requires at most 2K (log log log(2no/ L) V 1) iterations of GD and in the last run it outputs a step-size 1) and point
KK = K Ei (x( such that exactly one of the following holds:
f(xx) 1100
12
Case 1: n no and
2KTo
and f(zx)- f f < 100 xx
M V f
Case 2: # no
2K
where M, def M (I/ and x are the iterates generated by GD with step-size n7' E [n, 27).
Theorem 4.3 requires J to be T-smooth, but has only log log dependence on the global smoothness constant. Moreover, the rate scales with the weighted average of smoothness constants along very close trajectory {z1, ......). In the next section, we give convergence bounds that depend on the unweighted average of the directional smoothness constants along the actual optimization trajectory.
4.2.2 Polyak's Step-Size Rule
Our theory so-far suggests using strongly adapted step-sizes, but neither root- root-finding nor exponential search are practical methods for large-scale optimization. Thus, we now consider other step-size selection rules which may leverage directional smoothness. In particular, the Polyak step-size sets,
mi = 7 (f())) - /IV
(26)
for some y > O. which is optimal for smooth and non-smooth optimization (Hazan and Kakade, 2019) given knowledge of (w=).. Surprisingly, we show that GD with the Polyak step-size also achieves the same guarantee strongly adapted step- without knowledge of the directional smoothness.
Theorem 4.4. Suppose that f is convex and differentiable and let M be any directional smoothness function for f. Let Do = |1000 - x:" 1²1 Then GD with the Polyak step-size and y E (1,2) satisfies
c(1)Ao
f(īx) - f(x')(
(27)
2 2 M 1:41)-1
where -(2)==1())))(-- and I2 E M( -l,;]/ (EA M(
Theorem measures sub-optimality at average iterate obtained using the directional smoothness. However, it also holds for the best iterate, á = arg min (æ;), meaning no knowledge of the directional smoothness required to obtain the guarantee. We prove an alternative guarantee for the
Polyak step-size in Theorem D.2 where the progress depends on the sum of step-sizes rather than on the average directional smoothness. This shows that the step-size in Equation (26) can itself be viewed as measure of local smoothness, albeit without formal justification.
8

---

Compared with the standard guarantee for the Polyak step-size under L-smoothness, f(=x)) f 2L (Hazan and Kakade, 2019). our analysis in Theorem 4.4 with the choice 7 = 1.5 yields
3
3 Σ M(x 2:+1)
f(3x) - f(x") - E (( ((+1)
k
k
where the second bound follows from Jensen's inequality and shows that the convergence depends on the average directional smoothness along the trajectory, rather than L. If f is L-smooth, then M (Ja, F & L. immediately recovers the classic rate for Polyak's 's method up to a 3/2 constant factor. If f is not I--mmoth, but (arg, Fk++1 ) is bounded, then Equation (27p generalizes the ((1/k) rate proved concurrently by Takezawa et al. (2024), but for any choice of directional smoothness (of which (Lo, -mmoootthsssss (Jingzhao Zhang al., 2020) is but one).
Comparison with strongly adapted step-sizes. As we saw for quadratics, strongly adapted step-sizes for any directional smoothness function allow to obtain the following convergence rate,
20
2011
f(zx) - f(()) 2 1=
M (2i,
This is matches the guarantec given by Equation (27) up to constant factors. As result, we give positive answer to the question posed earlier in this section: GD with the Polyak step-size achieves the same convergence for any smoothness function M as GD with step-sizes strongly adapted M.
Application to the optimal directional smoothness. Theorem 4.4 holds for every directional smoothness function M. Therefore we can specialize Equation 27 with the optimal point-wise directional smoothness (as defined Equation (4) and 7 = 1.5 to get the guarantee,
3 ro x 12
[f(a,) f(x)) Σi=0 H (z,,, KE(K-1
min
(28)
This rate requires computing the iterate with the minimum function value, but that is casy to track during optimization. Unlike previous results, Equation (28) requires no access to the optimal point-wise smoothness, yet obtains a dependence on the tightest constant possible.
4.3 Normalized Gradient Descent
Now we change directions slightly and study normalized GD, whose convergence also depends on the directional smoothness. Normalized GD uses step-sizes which are divided by the gradient magnitude,
26
ff(()))l
The
vf(x)).
(29)
Our next theorem shows that normalized GD obtains a guarantee which depends solely on the average of the point-wise directional smoothness D2 == D( r1-1) despite no explicit knowledge of D2-
Theorem 4.5. Suppose that I is convex and differentiable. Lei D be the point-wise directional smoothness defined by Equation 44h and Ao == |100 - x "1.. Then normalized GD with a sequence of non-increasing step-sizes T) satisfies
- ((xx) Ao + Ek- oi
(((a)
f(x') m
Do +
ΣE= k-1
M( (30)
212
To
2k
k
arg arg minne]] (xx). ). If maxxe[k-11 M xi-1) bounded for all k (i.e. f is L- smooth), then for Ti = 1/vi we have f(ix) - f(x*) E O(1kk) and for m = 1/Vi we get the anytime result f(xx) f(x') E ((log())/k)
where Sx
Theorem 4.5 gives a rate for normalized GD which is valid for any convex f without any dependence on global smoothness. However, does not adapt to any smoothness function like the Polyak step-size.
5 Experiments
We evaluate the practical improvement of our convergence rates over those using T-smoothness on two logistic regression problems taken from the UCI repository (Asuncion and Newman, 2007).

---

ionosphere
horse colic
ozone
10
Optimality Gap
10-1
10
10
10-9
10
16-1
10-2
10-44
100
200
100
100
Iterations
Iterations
Iterations
GD (1/L)
GD (1/Da)
Polyak
Norm. GD
AdGD
Figure 4: Comparison of GD with 7)s = 1/L, step-sizes strongly adapted to the point-wise smoothness
(m 1/D(z xk+1)), and the Polyak step-size against normalized GD (Norm. GD) and the AdGD method on three logistic regression problems. AdGD uses smoothed version of the point-wise directional smoothness from the previous iteration set 77.- We find that GD methods with adaptive step-sizes consistently outperform GD with = 1/L and even obtain a linear rate on horse-con coolicllle ic.
Figure 1 compares GD with strongly adapted step-sizes 17 = 1 1/Mx, where Mj is the point-wise smoothness, against GD with the Polyak step-size. We also plot the exact convergence rates for each method, Equation (16) and Equation (27), respectively, and compare against the classical guarantee for both methods. Our convergence rates an order of magnitude tighter the ionosphere dataset and display remarkable ability to adapt to the path of optimization on mamnographic.
Figure 3 compares the performance of GD with strongly adapted step-sizes and with the fixed step- size 7h L/L for a synthetic quadratic with Hessian skew (R. Pan et al., 2022). Results are averaged over twenty random problems. We find that strongly adapted step-sizes lead to significantly faster convergence. Since Ag, D₁ < L, the adapted step-sizes are larger than 2/L. L, especially at the start of training; they eventually converge 2/ L, indicating these methods operate the adge-of-stabillig (J. Cohen et al., 202T] J. M. Cohen et al., 2002). This is consistent with Ahn et al. (2022) and Pan and Y. Li (002)). who show local smoothness is correlated with edge-of-stability behavior.
We conclude with comparison of empirical convergence rates on three additional logistic regression problems from the UCI repository. We compare GD with 77 1/ L. GD with step-sizes strongly adapted to the point-wise smoothness (7 = Ds),,, GD with the Polyak step-size (Polyak), and normalized GD (Norm. GD) against the AdGD method (Malitsky and Mishchenko, 2020). The Polyak step-size performs best on every dataset but ozone, where GD with 7/s = 1/Ds solves the problem to high accuracy in just few iterations. Thus, although Polyak step-size sizesizes have the optimal dependence on directional smoothness, computing strongly adapted step-sizes can still be advantageous.
Conclusion
We present new sub-optimality bounds for GD under novel measures of local gradient variation which we call directional smoothness functions. Our results hold for any step-sizes, improve over standard analyses when 7) is adapted to the choice of directional smoothness, and depend only on properties of f local to the optimization path. For convex quadratics, we show that computing step-sizes strongly adapted to directional smoothness functions straightforward and recovers two well-known step-size schemes, including the Cauchy step-size. In the general case, we prove that an algorithm based on exponential search gives a weighted- version the path-dependent convergence rate with no need for adapted step-sizes. We also show that GD with the Polyak step-size and normalized GD both obtain fast rates with no dependence on the global smoothness parameter. Crucially, the Polyak step-size adapts to any choice of directional smoothness, including the tightest possible parameter.
10

---

Acknowledgements
Aaron Mishkin was supported by NSF Grant 1GE-1656518, by NSERC Grant PGSD3-547242-2022
and by an internship at the Center for Computational Mathematics, Flatiron Institute. We thank Si Yi Meng for insightful discussions during the preparation of this work and Fabian Schaipp for use of the step- hop-backjee code. We also thank the anonymous reviewers for comments leading to improvements in Proposition 3.2 and the addition of Theorem D.2
References
Ahn, Kwangjun, Jingzhao Zhang, and Suvrit Sra (2022). "Understanding the unstable convergence of gradient descent". In: International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA. Vol. 162. Proceedings of Machine Learning Research, pp. 247-257. Altschuler, Jason M. and Pablo A. Parrilo (2023). "Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedule". In: CoRR abs/2309.07877 007899
Asuncion, Arthur and David Newman (2007). UCI machine learning repository.
Barzilai, Jonathan and Jonathan M Borwein (1988). "Two-point step size gradient methods". In: IMA
journal of numerical analysis 8.1, pp. 141-148.
Beck, Amir (2017). First-order methods in optimization. MOS-SIAM series on optimization. Philadel- phia Philadelphia: Society for Industrial and Applied Mathematics Mathematical Optimization
Society. ISBN: 778-161-197-449-99-
Bengio, Yoshua (2012). "Practical Recommendations for Gradient- Training of Deep Archi- tectures". In: Neural Networks: Tricks the Trade SSecond Edition. Vol. 7700. Lecture Notes in Computer Science, pp. 437-478.
Berahas, Albert S., Lindon Roberts, and Fred Roosta (2023). "Non-Uniform Smoothness for Gradient Descent". In: arXiv preprint arXiv:231 I. 1.08615 abs/231 1.08615.
Bertsekas, Dimitri P (1997). "Nonlinear programming". In: Journal of the Operational Research
Society 48.3, pp. 334-334.
Bubeck, Sébastien et al. (2015). "Convex optimization: Algorithms and complexity". In: Foundations and Trends@ Machine Learning 8.3-4, pp. 231-357.
Carmon, Yair and Oliver Hinder (2022). "Making SGD Parameter-Fred In: Conference on Learn- ing Theory, 2-5 July 2022. London, UK. Vol. 178. Proceedings of Machine Learning Research, pp. 2360-2389.
Cohen, Jeremy et al. (2021). "Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability". In: 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021.
Cohen, Jeremy M. et al. (2022). "Adaptive Gradient Methods At the Edge of Stability". In: arXiv preprint ar arXiv:2207. 14484 abs/2207.11444.
Dai, Y. H. and X. Q. Yang (2006). "A New Gradient Method with Optimal Stepsize Property", In: Computational Optimization and Applicutions 33.1, pp. 73-88.
Duchi, John C., Elad Hazan, and Yoram Singer (2010). "Adaptive Subgradient Methods for Online
Learning and Stochastic Optimization". In: COLT 2010 The 23rd Conference on Learning Theory, Haifa, Israel, June 27-29, 2010, pp. 257-269.
Gernández-Delgado. Manuel et al. (2014). "Do we need hundreds of classifiers to solve real world classification problems?" In: The journal of machine learning research 15.1, pp. 3133-3181. Grimmer, Benjamin (2019). "Convergence Rates for Deterministic and Stochastic Subgradient Methods without Lipschitz Continuity". In: SIAM J. Optim. 29.2, pp. 1365.
Hazan, Elad and Sham Kakade (2019). "Revisiting the Polyak step size". In: arXiv preprint
urXiv:/905.003/ 03
He, Kaiming et al. (2015). "Delving deep into rectifiers: Surpassing human-level performance on imagenet classification". In: Proceedings of the IEEE international conference on computer vision,
pp. 1026-1034.
Hogan, William W (1973). "Point-to-set maps in mathematical programming". In: SIAM review 15.3,
pp. 591-603.
Karimi, Hamed, Julie Nutini, and Mark Schmidt (2016). "Linear convergence of gradient and condition". In: Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2016, Riva del Garda, Italy September 19-23, 2016, Proceedings, Part I 16. Springer, pp. 795-811.
proximal -raddeent methods under the
11

---

Levy, Kfr Y. (2017). "Online to Offline Conversions, Universality and Adaptive Minibatch Sizes". In: Advances Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 1613-1622.
Li, Haochuan et al. (2023). "Convex and Non-convex Optimization Under Generalized Smoothness". In: Advances in Neural Information Processing Systems 36: Annual Conference on Neural In- formation Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10- 16. 2023.
Li, Zhiyuan, Kaifeng Lyu, and Sanjeev Arora (2020). "Reconciling Modern Deep Learning with Traditional Optimization Analyses: The Intrinsic Learning Rate". In: Advances in Neural Informa- tion Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual.
Liu, Dong C and Jorge Nocedal (1989). "On the limited memory BFGS method for large scale optimization". In: Mathematical programming 45.1-3, pp. 503-528.
Lu, Zhaosong and Sanyou Mei (2023). "Accelerated first-order methods for convex optimization with locally Lipschitz continuous gradient". In: SIAM Journal on Optimization 33.3, pp. 2275-2310. Malitsky. Yura and Konstantin Mishchenko (2020). "Adaptive Gradient Descent without Descent". In: Proceedings of the 37th International Conference on Machine Leurning, ICML 2020, 13-18
July 2020, Virtual Event. Vol. 1 119. Proceedings of Machine Learning Research, pp. 6702-6712.
Mei, Jincheng et al. (2021). "Leveraging Non- Non-uniformity in First-order Non-convex Optimization".
In: Proceedings of the 38th International Conference on Machine Learning. ICML 2021, 18-24 July 2021, Virtual Event. Vol. 139. Proceedings of Machine Learning Research, pp. 7555-7564. Mishkin, Aaron, Mert Pilanci, and Mark Schmidt (2024). "Faster Convergence of Stochastic Acceler- ated Gradient Descent under Interpolation". In: arXiv preprint arXiv:2404. 023378.
Nesterov, Yurii (1983). "A method for solving the convex programming problem with convergence rate (1/k2)", In: Dokl akad nauk Sssr. Vol. 269, p. 543. Nesterov, Yurii et al. (2018). Lectures convex optimization. Vol. 137. Springer. Orabona, Francesco (2023). "Normalized Gradients for All". In: arXiv preprint arXiv:2308.0500
Abs/2300.056221
Pan, Rui, Haishan Ye, and Tong Zhang (2022). "Eigencurve: Optimal Learning Rate Schedule for SGD Quadratic Objectives with Skewed Hessian Spectrums" In: ICLR.
Pan, Yan and Yuanzhi Li (2023). "Toward understanding why adam converges faster than sgd for transformers". In: arXiv preprint arXivv2306.000 206.00004.
Paquette, Courtney et al. (2023). "Halting time is predictable for large models: A universality property and average-case analysis". In: Foundations of Computational Mathematics 23.2, pp. 597-673. Park, Jea-Hyun, Abner Salgado, and Steven M Wise (2021). "Preconditioned accelerated gradient descent methods for locally Lipschitz smooth objectives with applications to the solution of nonlinear PDEs". In: Journal of Scientific Computing 89.1, p. 17.
Paszke, Adam al. (2019). "Pytorch: An imperative style, nigh-performance deep learning library". In: Advances in neural information processing systems 32.
Patel, Vivak and Albert S. Berahas (2022). "Gradient descent in the absence of global Lipschitz conti- nuity of the gradients: Convergence, divergence and limitations of its continuous approximation". In: arXiv preprint 1r.iv:2210.02411
Polyak, Boris T (1987). "Introduction to optimization".. In.
Streeter, Matthew and H. Brendan McMahan (2010). "Less Regret Via Online Conditioning". In: arXiv preprint ar arXiv: 2002. 4862.
Takezawa, Yuki et al. (2024). "Polyak Meets Parameter-free Clipped Gradient Descent". In: CoRR
abs/2405. 15010. DOI: 10. 48550/ ARXIV. 2405 15010 arXiv: 2405 15010
URL: https
//doi.org// 10. 48550/ arxiv 2405 15010
Vainsencher, Daniel, Han Liu, and Tong Zhang (2015). "Local Smoothness in Variance Reduced Optimization". ", In: Advances in Neural Information Processing Systems 28: Annual Conference on
Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pp. 2179-21877
Virtanen, Pauli et al. (2020). "SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python". " In: Nature Methods 17, pp. 261-272.
Vladarean, Maria-Luiza, Yura Malitsky, and Volkan Cevher (2021). "A first-order primal-dual method with adaptivity to local smoothness". In: Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pp. 6111-
12

---

Zhang, Bohang et al. (2020). "Improved Analysis of Clipping Algorithms for Non-convex Optimiza- tion". In: Advances Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual.
Zhang, Jingzhao al. (2020). "Why Gradient Clipping Accelerates Training: Theoretical Justifica- tion for Adaptivity".. In: 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020.
Zhang, Junyu and Mingyi Hong (2020). "First-order algorithms without Lipschitz gradient: A sequential local optimization approach". In: arXiv preprint arXiv:2010.03194
Zhao, Weijing and He Huang (2024). "A "Adaptive stepsize estimation based accelerated gradient descent algorithm for fully complex- valued neural networks". In: Expert Systems with Applications
236. p. 121166.
13

---

A Proofs for Section 2
Lemma 2.2. If is convex and differentiable, then the point-wise directional smoothness satisfies,
D 9)
f(y) - f(x)+ (Vf())) 2)
1 - x=12-
(5)
2
Proof. By the convexity of f we have
f(x) (V))) f(9).
Rearranging and then using Cauchy-Schward we get
f(x) f(y) + (Vf - V)
= f(y) + (Vf(v), x - y) + (Vf(x) Vf(y), x y)
f(y) + (Vf()), V) + [V(x) f |||= vll
f(w) + (Vf()), -- v) + D(x, y)
| yl?
Lemma 2.4. For any funttitn f. the path-wise smoothness
satisfies
f(y) f(=)+(++++))))) (Vf(z).y x) A(x, 1ly x 21/2.
(8)
Proof. Starting from the fundamental theorem of calculus,
f(g) f(x) (v)(x). x)
(Vf(x t(y x)) Vf(x). 2) dt
J. A(x, y)t x y1
A(x, v)
by x1...
which completes the proof.
Proposition 2.3. There exists a convex, differentiable and x, E Rd such that ift < 2, then
f(y) > f(x) (Vf(=), 2) f - vf(ii
2 x1|2 ly 2112.
(6)
Proof. Let H denote the optimal pointwise directional smoothness associated with some convex and differentiable function f Rdd - R (as defined in Equation ). and D, denote the pointwise directional smoothness associated with f (as defined in Equation
For any 1, the statement of (6)
equivalent to saying H, II (xx)Vf(()) for all x, y RRd and convex, differentiable f. Observe
||æ-~||
that Lemma 2.2 already shows that for all convex and differentiable functions f .Rd - R
HG(r, v) S Dy(x, [V (
yl
for all æ, y E IRd, In order to show that this tight, we suppose by the way of contradiction that there exists some 2 2 such that for all convex and differentiable functions f : Rd -
( v) <t. t. [V/(x) V [
(31)
| wll
for all x, y R. We shall show that no such exists by showing for each such there exists function fr such that Equation 31 does not hold.
Consider fz(x) = V + for c I 1. The function f is differentiable. Moreover
é²
f((x)
x
(e2 + x2) 2 0.
Vx² + 2
14

---

Therefore f is convex. Let g(x) |z]. Fix 2 = 1 and - 0, we have
(g(x)) g(v) sign(y) (z (z- -)) - [f( fv) f((v) (z - y) + ((x) - f((x)
+ +16(v) fe(v)) + +(f sign(y)) (x - v)
=ff((x) f((v) f(()) (x y) + 1=
+ +/0 ve + 10 (0-0) (1-0)
<f((()) - f(()) (()) (x v) 2c.
Now observe that
10 g(z) - g(v) - sign(y) (x - y) = 1 - - 0- 0) =1
Therefore
[f((z) felv) f'(v) (x y) 1 - 2c.
(32)
By definition we have 2/100 - y11² 1 therefore
2.
Hy(x, [f(x)) fe(u) - [(y) (x y)1 4c.
(33)
b - ylI
But by our starting assumption we have that there exists some such that Hy(r, v) t ("v(( for all differentiable and convex functions Applying this Se we get M
S
H (1,0) - (1( f((0)1
1
SL
(34)
|1|
V1+ v1 + 62
Combining Equations
33 and 34 we have
2 2 4E S (1, St
Rearranging we get
2 2-t t S 4e
Choosing c 2-t > we get contradiction. It follows that the minimal such that H v) S
[f (w) for all convex and differentiable is t 2.
Lemma A.1. One step of gradient descent with step-size Te > 0 makes progress as
f(*++1) S f(xx) - (1- Mh (Ik, xx-1)
[+xx)
2
Proof. Starting from Equation
we have
f(xx+1) S f(xx) + V (1x) IA-1 - xx) +
|x xx
2
M Tx+11
f(xx) Th f
V
=((x)) 1p 1 (1
(IR (I2, #x+1)
[V
2
B Proofs for Section 3
Lemma B.1. f f is convex, then for any Ir, y E Rd.
M(x, v)
f(v) 2 + If ff is p strongly convex, then ulz, 3) 2 μ.
11 1
(35)
15

---

Proof. The fundamental theorem of calculus implies
( Lo (VI(x + (1y +(y- Vi(x)), y- dl
2 J pla, w()xx)||==-0 ylladt
(x,,)) x11.
Note that have implicitly used convexity to verify the inequality in the second line in the case where (zz, y) = O. Now assume that is f strongly convex. As a standard consequence of strong-convexity. we obtain:
(V (x + My x)) V5(x), x)
( + fly x)) ()(x), x
Mly x) x)
1 - v11
1 121 311
2 Myy - x) - -x x1
1211 x
Proposition 3.1. If f is convex and differentiable, then GD with step-size sequence {nk] satisfies,
8% - II (1 maXape) (1+mp1p)))
80
E
II
(1+ m
nA [Vf(2;))
(13)
LiEg
iEB
Li>ijE
where - 2. {i: 22/Mi,, and B [K]|9.
Proof. First note that X; < i E G and A 0 for i E B. We start from Equation
10
(IK, rk-1) -1
f(x++1) S f(xx)) + 1l
f<x))]
mr-A V [V
= =s(xx) + lkeg
+ 1EE
V
fxxx
)
2
S f(x)) + lueg [mAdER (f(#x) f(x + ANEB
| [x=(
2
where we used that directional strong convexity gives
[ 2 24 (f(xx) - f(a"))
Subtracting fxx) from both sides and then recursively applying the inequality gives the result.
Proposition 3.2. f is convex and differentiable, then GD with step-size sequence {nk} satisfies,
147
k
(Mm n??
A <
Ao
Vf(x))
(15)
+ Ms+1
+
15+17
1 Mi+17
1>1
Proof. Let Au = || - x²12 and observe
A 10 Ik+1 + Bb+1 - x= 112 = A + | - F4+1
(xx F4411 - x²)
Using this expansion As+1 - DE. we obtain
++1 As = -1 Ik+ill 11 2 (ox - Fk+1, Fk+1 x²)
=-12 fxx)) - 2m (Vf(x)) Ik+l - =x²)
-- f [zx) 2mH (V fxxz)) Fball - FR) -27 (V [V.((w)) 26. -x").
16

---

Now we control the inner-products with directional strong convexity and directional smoothness.
- V fz++)) 27J (Vf(xx), Fx+1 - 24) + 27/ [f(x²) - f(xx)=
- 1/6
2 A
< 27R [((Zz) f(xx+1) MIR; Ib+1 2m
[
+ 27 [((=") f(x))-f(x1) M/ AR
= The (k+)))) 1) f
) )12 + 2nk [f(==)((==))))))(())) - f(xx+1)) - MA Ak
S Ví
where the last inequality follows from M strong convexity between #K+1 and x". Re-arranging this expression allows us to deduce a rate with error terms depending on the local smoothness,
= (1 + 1k+177)) 77)
A++1 S (1 mx77)e) A n (MR, Fk+1 1) (1=
< [1 - pa D a
The (M (IL, Th+ )m V 2
11 1
2 (M (I+,)
A++1 S
Ds +
V f
1 + p4++177
1 + Pk+17h
A
[1 Hanel
Do
+ Mi+177/
0=
|1- Hamil
nf (M x441) - 1)
V f (x;)
1 14++7h
1 11-177
==0
j=++1
Proposition 3.3. LetTx= = =
17/5--1/ // Th. If f is convex and differentiable, then GD satisfies,
|r00 x 11
E 1)
((Tk) - f(x*)
(16)
2 Σ Σi=0 11
2 2
Proof. Let A ||+0 xx x01 and observe
A | Ik+1 + Fk++1 x= 112 AK+1 + 1 Fx+1 112 + (xx IK41, - -x*)-
Using this expansion in Ak+1 As. obtain
A k-1 Do - | 5k+1 112 2 (ax Fk++1 Fk+1 x²))
k fx 27 f Tk41 - x²)
mhl (=x)) 27y, (xx Tx41 ann - 2m (FF())) .y - -x)).
Now we use convexity and directional smoothness control the two inner-products as follows:
A A S n V fxx))) 27p (f(x)) [(x²)) 2n (I)))), mx)
< k V (xx))11 2mp (f(#x) - f(x*)) + 2m (f(x) f(xx+1))
M (1
(Mx (I xx+1) - f 27/ (f(x)1) - f(x"))
Re-arranging this equation and summing over iterations implies the following sub-optimality bound:
k T (f(a:)1) - f(x*)) = Ao Σt_ 1 (th M MM,, 1.-1 -))l
E Tk
1 2
Convexity of ff and Jensen's 's inequality now imply the final result,
= f(Tx) - f(x*) s Do + Et (1, (1, ->)l -(fx)-
"! 17
17

---

B.1 Path-Dependent Acceleration: Proofs
This section proves Theorem 3.4 using estimating sequences. Throughout this section, we assume 2 0 is the global strong convexity parameter, where μ 0 covers the non-strongly convex case. We start from the estimating sequences version of Equation (77. which given as follows:
a = 174 - axe + 77
7 (1 - aak)) + anp
Vk =
7l tzfu
Tou + 7+11
(36)
2h+1 = yk nh V (3x)
Uk+1 7h+1
[[1 ak) + axpyE a fyx)]]
The algorithm is initialized with zo vo and some Too 0. Note that go Ho to since ye is convex combination of ø5 and Vg. First we prove that this scheme is equivalent to the one given in Equation (17.
Lemma B.2. Equation (36) and Equation 17 lead equivalent updates for the ye, I and ar
sequences. Moreover, given initialization "Yu 0, the corresponding initialization for ogg is,
?00 ( (M--70) 70) + V(ro 14)2 + 4770/T0)
ag 2
(37)
Proof. The proof follows Nesterov et (2018 Theorem 2.2.3). Expanding the definition of Uk+11 we obtain
1
ax)
Uk+1
[1766 + akp)yK - 7k+10p] + Cx:/iikk
ax V (1x))
Yk+1
O
1
(1
aik 1ik
y/ + uyj
(1-ak) 2n
a
V (y(k))
1
ak
7
V f(k)
(yk xxk)
ax
ak
1
(xx+1
rk)
0
Plugging this back into the expression for Vk++1
1
Uk+1
(6411111 + 74420++1]
76+1 a2+1/1
1
a1+17++1(2k + Ork
(#x+1 - Iz)) + 74220++1
No+1 + a-+1H
0k+17k + 04 ak+ 1k+1))441 + +ata411 0K+1 an(74+1 + (1+111)
a1+174+1 (1 ax)
ax(7k41 + (1+11)
#k41 + 04+174+1 an)
(Ik++ -xx)
06(7641 + ak+1I))
ax+17k+11 (1 ocp) 0g (7k+1 + 2 k411 /m - -(1 a241)7441
#b+11 +
(Ix+1 - Ib)
ax ax))
2b+1
(It+1 2k).
(a++1 + at)
Note that this update is consistent with Equation Since 7 = og/ne, m.. we can write,
a 7//+1 (1 0k+ 7 11410044114
Mk+1 (1 1 + 164108+1/1
17
18

---

which is also consistent with Equation 17 Finally, the initialization for ao is determined by in Equation (36) as,
nol 00) 7000/1
The quadratic formula now implies.
7o
(u 1u--0) 70) + -(100 =12 + 470/110
ag
2
This completes the proof.
As mentioned, our proof uses the concept of estimating sequences. Definition B.3. Two sequences Ag. @% are estimating sequences for f if X 2 for all k N,
lim A = 0, and,
(x(x) s (1 -xx)f(a) + Axdo(z),
(38)
for all x E Rdd.
We use the same estimating sequences as developed by Nesterov et al. 2018 Let Ao = 1, do(x)
=
(ao) + 7o | vol 2. and define the updates,
A = (1 - (
(x) = (1 (x) an (S(UR) + (VI())), x - yx) + +1 yy 1212))
(39)
where μ 2 is the strong convexity parameter, with μr 0 when f merely convex. It is straight- forward to differentiate 0x++1 that U++1 of Equation (36) is the minimizer. Indeed, Nesterov et al. (2018, Lemma 2.2.3) shows that this choice for the estimating sequences obeys the following canonical form:
(2) min (2+ +
7 | uk+1 11..
(40)
where Yk+1 and Uk+1 are given by Equation (36) and the minimum value is,
0x
min (1+1 = axk) min (x) + oz (()=)
(
2
(41)
as (1 axk
[1 un (V)())), un - yk?)
7k+1
Before we can prove our main theorem, we must show that these choices for 2 and Φ yield valid estimating sequence. The following proofs build on (Nesterov et al., (2018) and (Mishkin et al., (024))
Lemma B.4. Assume ag E (0, for all k E N. If > 0 and To = then
k-1
A
II ==
TKH).
(42)
If p 2 0 and To (1, p + 3/mmin), then,
4
A Mmmn (70 p)(k 1)2*
(43)
Proof. Assume "to p 0. Then 7 = / for all and,
a (1 au a A1
As consequence,
k-1 A
II
==0
claimed.
19

---

Now assume [L, + p). Modifying the proof by Nesterov et al. (2018 Lemma 2.2.4), we
compute follows:
Y (1 an) (aok 1) (1 (1-a))(1 14)
Recursing on this equality implies
7k+1
(70 11)
II aR) = 1x+1 (1).
i=0
ag or or 2 0. then using Ak+1 Otherwise, recall 7 = Th to obtain,
ax) implies Ak+1 0 and the result trivially holds.
Ak+1
Onk (T++1 11h )/2
d
(Tofe + ma - 11)))122 1/2
1
+ m1(0 - (1)
Ak+1
A
X k+1
1/2
Ak+1
Tmmin/s + Vmin (Yu - 11) )
1/2
1/2 X
AR+1
k+1
Finally, this implies
2
1
1/2 A-+1
1/2
1/2
1/2
1/2
1/2
X//
1/2
k++1
Ak+1
AK+1
1/2
Mmin/
Maii Aamin(%o (7/ - p4)
1+1
1/2
Act1
Moreover, this bound holds uniformly for all & N. We have now exactly reached Eq. 2.2.11 11 of Nesterov et al. (2018 Lemma 2.2.4) with L replaced by 1/mmin- Applying that Lemma with this modification, we obtain
4
1/min (70 1k( 1)22
which completes the proof.
Lemma B.5. If f is strongly convex with parameter 0 and mh S f/r all k E N, then d and dx are estimating sequences.
Proof. Using the quadratic formula, we find
ag 1- + (11 (/k-))
72 2 + 47///1
2/1k
Thus,
(μ- 7k) (1=-7))² 2 44x / 11 1/2 > 0.
is sufficient for ag > 0. This holds if 2 72. Otherwise, we require,
(μ - )x) 48p/nk > (μ - 72)
which holds if and only if me. > 0. On the other hand, we also need ag < 1, which is satisfied when,
1 7k S 1
4+ 4m (71 11) + (p mx)2 < nh (1 7x 4m
as claimed.
Recall Ån 1 and A4+1 (1 a )rg- Since ag (0. 1), A 2 0 holds by induction. It remains to show that A tends to zero, which holds by Lemma B.4 since we have shown 0g E (0, for all k.
Now we establish the last piece,
2 (x) 5 (1 (x) (x))(())
But this follows immediately by Nesterov et al. (2018 Lemma 2.2.2).
20

---

Now we can prove the last major lemma before our convergence result.
Lemma B.6. Suppose f is strongly convex with parameter μ 2 0 and Te a sequence of adapted step-sizes, meaning 77 ( Fx+1). Then for every & E N.
min = f(xx)-
Proof. We use an inductive proof again. The inductive assumption is
min (x) 2 f(xx),
It is easy to see this holds at k = 0 since,
<o(2) - [(00) + 70 || vo volla
2
implies min- 0b(=)) = [(x)). Using Equation (41) we obtain
ok
min (x) (1 a4 min Φ& (2) + fx
| [yx)]1
2*x+1
ax ak)T
11
vxl1 + (VI 2x), yx.)
7k+1
a7
2 (xxxa))(zx) aaf(y))
[V
27x+1
(M
1l + (Vf(zk), up uki)
7k+1
where the inequality holds by the inductive assumption. Using convexity of f and recalling from the definition of the update (Equation 36))
of
7k
76+1
min 0x+1 2 (1 - -ax) (f(vk) + (Vf())), 2A yke) + (Uk) - Th
2
ax am
L (Hllon uxll + (V (zw)), uz>)
2
7h+1
= =((k)) + (1 an) (Vf())), - -yk)
V {1
2
au. (1 -ox
( Ilve -x (VI(u)), yk)
7k+1
2
Using the fact that the step-sizes are adapted and invoking the directional descent lemma (i.e. Equation (8) now implies
min (x)) 2 f(x+1)) + +1 (11 aw) (VI(U)), - yk)
(5
12 (Vf(v)) Us vnl) Uni))
Ne+1
The remainder of the proof is largely unchanged from the analysis in Nesterov al. (2018). The (yk uk), which we use to obtain
definition of gives It
2x2k
min (x) 2 f(xx41) + (1 (1-aw)
a' 7k
fyyx), 2k Uk)
7
au (1
|1//= - Ukl ? (Vf(zx), us - yki) )
76+1 2
= f(zx41) + par (1 - ax) 1lyx - ux
2
> ((x+1))
since nou (1-ax17k 2
2 0. We conclude the desired result by induction.
21

---

The main accelerated result now follows almost immediately.
Theorem 3.4. Suppose f differentiable, j-strongly convex and AGD is run with adapted step-sizes Th & 1/Mx. F > 0 and cxg /hup, then AGD obtains the following accelerated rate:
f(*x+1) -
II vumi) (f(00)-((=") i=0
f(==)=f()))=-))))))))> -11000 x=
(19)
Let Mmin min Mi- 1f 0 and ox E (v/uno c). where is the maximum value of on for which
1000 satisfies To 3/ Mmain + pb then AGD obtains the following rale: 70 mo(1-ap)
(0x+1)-((x')- Mmin - (k: + 1)2 [f(m)) f(x)) + 70 11000
x² x112
(20)
2
Proof. We analyze the equivalent formulation given in Equation (36 See Lemma B.2 for formal proof that these two schemes produce the same Tk, yks and 0g iterates. Note that our proof follows Nesterov et al. (2018) and Mishkin et al. (2024) closely; while their results are very similar, not aware of pre-existing works which adapt them to our specific setting.
First, observe that M ( Tx41) 2 μ for all k E N. Since the step-sizes Te are assumed to satisfy ? I 1/M Tk41). we also have that 176 S 1/2 for every k.
Thus, Lemma B.4 and Lemma B.5 apply. Using the definition an estimating sequence and Lemma B.6 we obtain,
f(xx) E min (x(2)
S min (1 {x) + Ando(2)
$ (1 {x) + \xΦo(=").
Re-arranging this equation and expanding the definition @u (Equation (39 ) deduce the following:
f(xx) f(Ø*) s A (0o(x*) - f(x"))
Au (f(on)-((2")
- )2=) - 70
||ao x x²13)
2
We see that the of convergence of AGD is entirely controlled by the convergence of the sequence
dk. If μ >> and To = then Lemma B.4 implies
k-1
f(xx) - f(x²))))))))))r)))) < II (1
(m)) [((0)) f(x*)+++++++) || x= x=1
1=0
By Lemma [.2, this initialization is equivalent choosing ap nofL which the setting claimed in the theorem.
Alternatively, if p and yu (H,, 14 + 3/ 3/Mmin)> then,
f f(x') S Mmnn (70 - 22 (aa) - f(x'( )+
20 1200 x x11
where the equality,
a 170000/4
[1 o0)
holds by Lemma B.2 Since dg < for %o 1/p. Yo an increasing function of 70- Thus, an upper-bound og be deduced from that on 7o using the quadratic formula:
3mjo
7uu
9
37mmin + 11
1/2
C
+
2mmii
2
(Amin))
n1o
3rju
37min + F4
1/2
+ ((mmn)) )²
27min
9r1o
22

---

C Proofs for Section 4.1
Lemma C.I. Let B be positive semi-definite matrix and suppose that
f(z) Bx cJ x.
1
Let 11+1= x; -V(r)( Then for any q >>>> 0, the pointwise directional smoothness between the gradient descent iterates Fiz Fi41 given
[z))22)
2 D(x(,
[VS(2))
Proof. We have by straightforward algebra,
1 D(r,,
-V
| 1ill2
||a [Bx; cl ll2
| 32ll2
B [ xzl 12
|0+41 3; 12
B |- (z:)) l12
nv f2:)ll
BV f 2
Lemma C.2. Let B be a positive semi-definite matrix and suppose that
f(x) 2" Bx cTT..
Let 2:41 =I - Then for any 17 0, the path-wise directional smoothness between the gradient descent iterates Iı, Fi41 is given by by
(xxx,) BV fzz) Vs(.) Vs(x;)
2(11,
Proof. Let As(x, y)
(V((+t(v==)))-- [(+) We have
11r-v112
V 1(y x)) V Vf(x), x)
Ax(x,))
t|| 21
((B(x + t(y xz)) c
[Br - c], x)
11 - v11 2
B(y x). y x))
t| y12
(y x) B x.)
|| y 1'2
The path-wis directional smoothness A is therefore A(x, v) sup A, y)
[E[0.1]
(y x) BBy x)
sup rE(o.1]
||0 y
(y x) BByy x))
||x 1 12
23

---

Plugging in y = [z) - -- -n c) in the above gives
A(z,z- = (-n [-7 [Br c)) B(-n) [xx
1/ c]1 2
(Bx c) BBBx c)
|Bx - c12
[Ex -c) -C)TB(B B(Br c)
| - clf
vf()) BV f(x)
Vf(x) TV((x)
D Proofs for Section 4.2
Proposition 4.1. J is convex and continuously differentiable, then either (i) S is minimized along the ray x((]) V/V [((x) or (ii) there exists 1j >> satisfying n = 1/D (())..
Proof. Let {1 fz v)f(2)) = [x))) For every E I, it holds that - (V)=) - (V
However, since f is convex, the directional derivative
(V 1/ (()))) vf(z))
monotone non-decreasing in r/'. We deduce that I must be an interval of form [0, 7j. If is bounded, then f is linear along - (x) and is minimized by taking + co. Therefore, we may assume is finite.
Let > 77. Then we have the following:
2|1x - V/[(()) - 2/12
T f)x)) =
- Vf(x)
2z)l2
vf(x)
Vf(x),
from which we deduce
-
sufficient for the implicit equation to hold. Squaring both sides and multiplying by 1/2, we obtain the following alternative root-finding problem:
1 (V[(=~V\((>]E (V (V/(x -[ //)()))))<<(()))))))))))))))))>) - 0. ((n) : 2 -
(44)
Because f is C h continuous function and it suffices show that there exists interval in which h crosses 0. From the display above, we see
h = - [V)( < 0.
Continuity now implies Br/ > 77 such that /1(r') < O. Now, suppose h(1) < 0 for all 1 2 T/. Working backwards, we see that this can only occur when
2 x [)) =||2 [v - f()) - vf(x)]l2 D(x(n), - = vVf())
n for all 17 2 r/. The directional descent lemma (Equation
10 now implics
-(- - f(x) (1 12 x -
[Vʃ(z) < f(x) (1))))
2
Taking limits on both sides as 1 implies f(r v/ (x:)) is minimized along the ray x(1)
x -- V/))x. Thus, we deduce that either there exists 1/" 1/' such that h(rr") > 0 exists, or f minimized along the gradient direction claimed.
24

---

Proposition 4.2. f is convex and twice continuously differentiable, then either (i) f is minimized along the ray z(n) fz) or (ii) there exists 1i satisfying 1j 1/A(z, x f
Proof. Let
- (]((==\V(())) Vf(x)) = -
Since is convex, the directional derivative
(Vf(z - (V(=)) Vf(x))
monotone non-decreasing in v/. We deduce that must be interval of form [0, ni). If is not bounded, then convexity implies
lim f(æ vz)) 4-000
lim f(z) -V 7
=00
meaning f is minimized along -V (x)). Therefore, we may assume Tj is finite.
We have
I [z)x A(r, x [))) V/(x)
V
- 1
inf
[. (V(()) (x Vf(z))
Thus, for 1) >> 77. the equation we must solve reduces to
tn V
((n) == : inf
vf(r LvV)(())) V(()) 0.
rE[o.] Vf(()
Since is C2, h is continuous (see, e.g. Hogan 1973 Theorem 7)) and it suffices to show that there exists an interval over which h crosses 0.
Using Taylor's theorem, we can re-write this expression as
[>)
((n) = -7- inf rE (Vf(z), v o(n)
where for some a(br) E [0, (n). Examining the denominator, we find that,
Vf(z)) = 0,
which, since f is convex, implies
vx(x) V [VV = =0, for every a E [0, T/. By continuity of the Hessian, for every e > 0, there exists d such that n' E [7, + d] guarantees,
Substituting this into our expression for h.
[ Wffaa)////-aar))/ii)))) 1E(0.]]
h(7') = n/ inf
8 [ff())1
<0,
for e, sufficiently small. Thus, there exists T/ > 77 for which h(rr) < 0.
Now let us show that (((r") > 0 for some 7/". For convenience, define
{=))l1
inf g(n)
0.10
( (n))) v((z))
25

---

Algorithm Gradient Descent with Exponential Search
1: Procedure ExponentialSearch(i;, 7jo)
2: for = 1,2,3.... do
3: Tout t -RoooFindingBiiccttonn (I.2 24 170, no))
4: if "oot <0 then
5: Return Moutt
6: end if
7: end for
8: End Procedure
9: Procedure RoolFindingBiscctionne; No: Thi)
10: Define Φ(π) steps.
(n) where (T)) is given in 24
One access to ø requires T descent
11: if (T))) - 0 then
12: Return 7hi
13: end if
14: if <(ma) > O then
15: Return
16: end if
while Thi 27n do
18: Mmmdd v Thi
if ((7mid) then
20:
Thi Mmidd
else
22:
The 7mid
end if
Invariant: ((ma) > O, and ((n)) S O.
end while
25:
Return Tho
26: End Procedure
which is continuous and monotone non-increasing function. Take v and let
lim g(n) = c, 11000
where the limit exists, but may be co. Indeed, it must hold that c < oc since,
lim g(n) g(n') oc. m-00
O, then taking r/" large enough that g()"") S suffices. Alternatively, if 2 0, then there exists îj such that g(n) & c+ for every 2 Choosing 17" max {ū, c) + yields
h(n")) = - -0((""") > c
This completes the proof.
Theorem 4.3. Assume is convex and L-smooth. Then Algorithm with vo requires at most 2K (log log (2go2 L) V 1) iterations of GD and in the last run it outputs a step-size and point
FK * Eko (T( such that exactly one of the following holds:
f(*x)-f(a) - f(x=)= 20
x=
Case 1: n no and
2Kno
120
x=
x=13
Σ 1=
M
V
Case 2: # no
and f(*x) - f³ <
2K
oizo
where M, def
M M d(41) and x; the iterates generated by GD with step-size n/ In, 2n).
26

---

Proof of Theorem 4.3 This analysis follows (Carmon and Hinder, 2022). First, instantiate Equa-
tion T6) from Proposition 3.3 with f r for all obtain
Ei [V(()))
f(t)) - f 200
x² 1²
n
(45)
2Tp
2k
Now, observe that if we get a "Lucky strike" and ((ma)) = <(10)) S 0, then specializing Equation (45 for 17 = n7 we get
f(xx) - f(x") -
11:00
x=11
+
?70
( (1
k Σ
2no
2k
==0
=
||:00
xx 112
1/0
Di
M
2:41) (i+))\ ((10)
(xt
2nok
2k
|1:00
x= 112
277o
This covers the first case of Theorem
With the first case out of the way, we may assume that <(hai) > O. This implies that Thi J, since
if 17 S I we have ((n)= I O. Now observe that when Moo = 2 T7o S t. we have that ((n) S O, therefore it takes at most k = [log log T to find such an Mho- From here on, we suppose that ((hi) > 0 and (Tno) < Now observe that the algorithm's 's main loop always maintains the invariant @Mpii
0 and o(ni)) I and every iteration of the loop halves log thi therefore %io
make most [log log no loop iterations. The output step-size The satisfies Iuu S Tho S Thh and (()a) I 0. Specializing Equation (45) for r = 1/o and using that (11)) I 0 we get
1100 - x 2112
Mo Σi_ M (z. (mo), T (mo V. o(mo)
f(Tx) - f(x)) <
2ynok
2k
|::00 x x=112
(46)
2
By the loop invariant o( >> O we have
Ek | (xx
(Tha
+ Mhi
E
(Tu)) (2, ( (m+1(
By the loop termination condition we have noo 2 thi combining this with the last equation we get
Thi 1
Σ E
(max)
mo
2
ER IV (z, (( (naa)
Plugging this into Equation (46) we obtain
f(Tx) - f(x)) 1:0 111
ΣK (S( (Lm
Σ [V)((
remains notice that Tha E [mo 2mpo]-
Theorem 4.4. Suppose that ff is convex and differentiable and let M be any directional smoothness
function for f. Let Do - x= 1* Then GD with the Polyak step-size and y E (1,2) satisfies
co7)
f(xx) - f(x") S
(27)
k-1 2 M M(
2
where = = () and Tx EhzO M( -m;
(I M(nn
For the proof of this theorem, we will need the following proposition:
27

---

Proposition D.I. Let x E RR. Define 7r 7 |V][) for some 7 E (1, and let I x
[(a)-((=))
The fx.).. Then,
f(x) - f(x)= 2 2 2-1 2
Vf(2)]l2
72 (x,
Proof. Observe
f(x) - f(0))= = f(0) f(8) + f(0) - f(x²)
2 f(x) - (()).
(47)
By smoothness we have
f(0) S f(x) + (Vf(2,, x) + M(r, 3:)
|| x²
2
fxx) nhe [ (x, 3))
[
2
Plugging back into Equation 47 we get
-(x) f(x") 2 Tr Vz)) (x,
Let us now use the definition of 1/2 7 [
1(m)-f(a>>
to get
f(x) - f(x)) (((xx) f(x")) Ma, x)
2 (f(z) - f(x")).
Assuming that f(x) # f(x*) then we get by cancellation
127 (xr,
2
Using the definition of n/ again
M(x f(x) f(z²)
1 1- -2
2
Rearranging we get
f(x) f(x)) 2 7 7-1 2
[V]())]
72 M(x,E)
If f(x) = f(x*) then [V)(2)] = 0, both sides are identically zero and the statement holds
trivially.
Now we can prove our theorem on the convergence of GD with Polyak step-sizes:
Proof of Theorem
4.4 We start by considering the distance to the optimum and expanding the square
|
x0 1/
[ x=112 + (Nx+1 Tk. - x²) + | - 2x 1 - x²)
Ia x²112 2m (V)(z))
+ v
(48)
Let 5₁ = f(xx)= - f(x'), ). By convexity we have f(x*) 2 f(xx) + (v)())), x- 2x). Therefore can upper bound Equation (48) as
|
x=11 112 = || 1
x
11
2m + nal Vf(xx) 12
= | - x 1| 21 + 1k
[V
= =1|-
- -11--~2
112 (2 7)
(49)
28

---

where in the second line we used the definition of me. By Proposition D.1
we have
ŌR 2 7-1
2
[V[(z))
(50)
M 1++1)
Using this in Equation (49) gives
| - x= 1 -
100.
x²
2 (2 -) 7-1
2
Vf(xx))
72
M (xk, Tk+1l
||0
x² 11 - (2 7) -
7/2 M (IRRs Ik+1)
2
(IV
5z
[Vf(2=)1
1| x² 2(2 7) 1)
Sk-
(M (x+1)
Rearranging we get
2(2 - 7) - 1)
6x < 1,: x²12 -1[2+11 - x=11
(IM, 26+11
Summing up and telescoping we get
k 1 2(2 () - 1)
8$ S | x²1
(M,,
x(+1) (I;,
Let Fg =
M (Ii, (1+1) xy then by the convexity of f and Jensen's
E. (41))
inequality we have
f(xx) - ff(x)) 5
M ((I,
Σ M (1 I++1)
$ 7
11:00 - x=1
2(2 7)(7 1) Ei- M (1
Theorem D.2. f is convex and differentiable, then GD with the Polyak step-size and y < 2 satisfies,
1
f( - f(x") <
(2 - 7) Σ 1|z0 x x²1
(51)
where Ta Eio ///s// (Ei=o m:)
Proof. The proof begins in the same manner as that for Theorem 4.4
||0441
21
I x=1 112 + (.x+1 Tg I2k x²) + || 2
| x 112 2nk (Vf(xx), 2x - x²) + 1 f (x+)
I
x² $12
2n 1/ V [
|
x²1 $122 2n 1/2 ? <<<
|V |V
| x $12 - (2 - -7
Re-arranging, summing from = to & 1, and dividing by Σir10 ni
k-1
Σ
M (f(xz) - f(ww)) <
[1L x² 112 - | - x=
(2 - 7) Ei 11
f
11200 x= 112.
(2 - 7) Σk 11
which completes the proof.
29

---

Lemma D.3. Normalized GD with step-sizes пソ satisfies
[ (Vf(zx), (f((x-1)) S M -nal
Tkk
m
(52)
Proof. By convexity we have
[*x+1) S [(rk) (18411 Ih, V[(x++1))
=s(r))
[V/f(x)]l (Vf(xx). Vf(xx1)
(53)
Now note that
Tik
(Vf())), Vf(x>)1))
7h
ff(x)) Vf(xx)) Vf((x+1))
(54)
Vf(2x)]l2
[vf(z>)
Th V f (2x)]l2
m \ - V (2*++)) mh (f(x))]
S
(55)
where we used Cauchy-Schwart
Recalling the definition of directional smoothness
[Vf(xx) v+(+++))]
(ar Tk+1)
def
xx+1|
Equation
55 gives
(Vf())) Vf(++-))) s s M(H, - Mall V
[Vf(z))l
Theorem 4.5. Suppose that f is convex and disferentiable. Let D be the point-wise directional smoothness defined by Equation 44 and Dg == 1100 - x= 112. Then normalized GD with a sequence of non-increasing step-sizes The satisfies
f(ax)-f(x*) - f(=)) Ao EE k-1 ni
(S(a))
[axt)
Ao
2i= T
M(31, (30)
2k2
np
2k
k
where ibp = arg min; 11] fx,). If max (2,, bounded for all k (i.e. f is L- smooth), then for 1/vi we have f(tx)) f(x*) O(1/k) and for t 1/vi we the
anytime result f(xx) ((*))= E (llog(k)/k).
Proof. Here we will first establish that for any non-increasing sequence of step-sizes Mk 0 we have that
+ min [(x)) fxx)) A
k-1 n vh
[(xo)
f(x*)
M Mari
(56)
EE(k-11
k
knng
knpp
k
1=0
M(21 is bounded, which it is the case The specialized results follow by assuming that -i=0 of L-Liipsciizz gradients. In particular the min 1] f(x;) - f(x*) E O(1/T) result follows by plugging in n7 1/VK and using that
R-1
k-
Σ 1=0
- k
=1
1=0
f(ro)
f(x")
= f(xo) - f(x²)-
kng
kmp
using that f(x;)) - f(x*) E Ollog())/)))) ()) by plugging in r = 1/vi+1 +++1. and
Alternatively we get minje[k-1)
A-1
k-1
Σ Tp
Σ
< log(k)
i+1
1=0
i=0
fx0)
f(x*)
f(20)
f(x").
kmg
km
k:
30

---

With this in mind, let us prove Equation (56).
By convexity,
f(IR+1) S f(xx) [Vʃ(,>)] V((z)) vf((x+1)
7h
f(()) 7k [++)))]2 M ( Ix+1).
(Using 52
Re-arranging, dividing through by nī. and then summing over 0,... , gives
ff(x))ll
((10)
k-2
f(x")
h-1
+
+I
f(as)
M 1++1)
7p
1/-1
Th-1
iml
k=0
f fx0)
f(0*)
M M(r (i+1),
(57)
n
mk-
where we used that 7/;-1 S which is convex for a positive. gives
S 0. Using Jensen's inequality over the map a ++ 1/a,
1
22
2
(58)
E
(V
[izo)
f(x')
+
Σk- M (11e
Meanwhile, recall our notation A; = ||= x² 21. Expanding the squares and using that (x) is convex, we have that
A41 A
[Vf(z))] vf(x;) (z, - x²) + n/
A 2m/ [(x;) [(x") m
[
As before, use 6; (x,) f(x'). Re-arranging, summing both sides of the above i = 0,...,k 1 and using telescopic cancellation gives
Ao + -i 11
7
2
0=0
Using the above along with (58 gives,
8 [Vf(2))
NE k-
min 8; <
Σ Li=D
1-1
M
IV [V,
1=0
1 Ao Σ == T
-- 2
Σ 1=0
K-1
Ao
+ Σ i=0 "/
f(())
f(z")
k-
M (2t, 1++1)
<
2
k
kmng
km
k
1=0
E Experimental Details
In this section we provide additional details necessary to reproduce our experiments. We run our logistic regression experiments using Py Torch (Paszke et al., 2019). For the UCI datasets, we use the pre-processed version of the data provided by Fernández-Delgadoo al. (2014), although we do not use their evaluation procedure as it is known have test-set leakage. Instead, we randomly perform an 80-20 train-test split and use the test set for validation. Unless otherwise stated, all methods are initialized using the Kaiming initialization (He et al., 2015). which is standard in Porch..
31

---

In order to compute the strongly adapted step-sizes, we run the SciPy (Virtanen et al., 2020) imple- mentation of Newton method on Equation (44). general, we find this procedure is surprisingly robust, although it can be slow.
Figure 1 We pick two datasets from the UCI repository showease different behaviors of the upper-bounds. We compute tight-upper bound on L as follows. Recall that for logistic regression problems the Hessian is given by
v f(x) A DDiag
A,
a y- Ax) + oly Ax)
where is the data matrix and ((2) T=exp(=) the sigmoid function. A short calculation shows that the diagonal matrix
Diag a Ar) + 2 + ( Ar)
3
which is tight when 0. As result, L Amax (AT A)/4 We compute this manually. We also compute the optimal value for the logistic regression problem using the SciPy implementation of BFGS (Liu and Nocedal, 1989). We use this value for f(=") to compute the Polyak step-size and when plotting sub-optimality. It turns out that the upper-bound bound based on L-smoothness for both GD with the Polyak step-size (Hazan and Kakade, 2019) and standard GD (Bubeck et al., 2013) is
2L| x
f(xx) - f(x)) <
k
Figure We run these experiments using vanilla NumPy. As mentioned in the text, we generate quadratic optimization problem
1 Ar bT
min
2
where the eigenvalues of A were generated to follow power law distribution with parameter a 3. We scaled the eigenvalues to ensure L 1000. The dimension of the problem we create 300. We repeat the experiment for 20 random trials and plot the mean and standard deviations.
Figure We pick three different datasets from the UCI repository to showease the possible con- vergence behavior of the optimization methods. We compute and f(w") as described above for Figure 1 For normalized GD, we use the step-size schedule πi = mo/Vk as suggested by our theory. To pick NJ., we run a grid search on the grid generated by np logspace (-8, 1, 20). We implement AdGD from scratch and use starting step-size of no = 10-3, -3, We use the same procedure to compute the strongly adapted step-sizes as described above.
Computational Details
The experiments in Figure 3 were run a MacBook Pro (16 inch, 2019) with 2.6 GHz 6- 6-Core Intel i7 CPU and 16GB of memory. All other experiments were run on a Slurm cluster with several different node configurations. Our experiments A100 GPUs (80GB or 40GB memory) or Nvidia H100-80GB GPUs with Icelake CPUs, or (ii) Nvidia V100-32GB or V100-16GB GPUs with Skylake CPUs. All jobs allocated a single GPU and 24GB of RAM.
the cluster were with nodes using (i) Nvidia
32

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All claims in the abstract and introduction are justified with rigorous proofs and supported by experiments.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The limitations of our theoretical results, including necessary assumptions, are addressed in the text.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model sell-specification asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texx system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess..
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknow ledgww in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
33

---

Answer: [Yes]
Justification: Our theoretical results are accompanied by their necessary assumptions and rigorous proofs provided in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: All experimental procedures and hyper-paramette parameter settings are provided in Appendix E
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
cases, in which
5. Open access to data and code
34

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [No]
Justification: We will release the code reproduce experiments upon acceptance of the paper. All non-synthetic data used in this paper is open source and freely accessible online.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://niis.cc.
aublic//uuddes/Coeeeubbiis wtw.eeeesuumiisioooooooooooo for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ wttpcccccppppcuucccceec.cc /ooeee///oodmmmii ississiinnn asiionoolccy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The details necessary interpret our experimental results are provided in while additional details necessary to reproduce the experiments are given in
Section 5]
Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
Our experiments consider only deterministic optimization methods.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
35

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are of range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information the computer resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: We detail the compute resources used in our paper in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https::/neurips... http:ppps..ppppppcceeeeeeec httpp///lle..tthcccsssleeee..e..
Answer: [Yes]
Justification: All authors are familiar with the code of ethics and conform to its principles. Moreover, our research is primarily theoretical and is of minor ethical concern.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our research is primarily theoretical and has no societal impact beyond the impact of general advances in the fields of machine learning and optimization.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
36

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
No new data or models are released as part this paper.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All libraries, models, and data sources are appropriately referenced.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
37

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, latasets,papersstt pwp.pppppssiiaco
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: No new assets are introduced.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/codeemmodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
We did not use any crowdsourcing for this work
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: IRB approval was not required for this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
38

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
39


Reviews:
[{"review_id": "96bp9eGHn4", "reviewer": "Reviewer_ETZ9", "summary": "This paper develops refined sub-optimality bounds for gradient descent in the convex setting. The authors consider directional smoothness, a local and path dependent smoothness condition, instead of assuming globally bounded smoothness constants in classical analyses. They discussed several interesting examples of directional smoothness functions, and derived sub-optimality bounds with them. For convex quadratic problems, they show that the stepsizes that minimize the upper bounds can be easily computed, which leads to new guarantees for two classical stepsizes. For general convex functions, they show that ideal stepsizes exist and can be computed using Newton's method or by exponential search. They also show that Polyak stepsize and normalized GD can achieve fast and path-dependent rates without knowing the directional smoothness.", "questions": "1. Have the authors considered non-convex settings? In fact, since the authors mentioned neural networks in the first paragraph of the introduction, I wonder if this directional smoothness can be used to explain certain phenomenons in deep neural network training, like edge of stability or benefits of adaptivity.\n\nSome potential typos:\na. Equation (3): missing \"+\"\nb. Line 194: it should be the inverse of Hessian?\nc. Theorem 4.3. Case 1: missing \")\"", "limitations": "The authors have adequately addressed limitations.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The sub-optimality bounds in terms of directional smoothness and the stepsizes and convergence results following the upper bounds look novel. The perspective is quite interesting.\n2. The proofs look correct and the results look reasonable. The authors have thoroughly studied relevant aspects and details of their theory.\n3. The authors did a good job connecting their results with existing methods and theories, which is quite insightful.\n3. The writing and presentation are also very good. I enjoyed reading the paper.", "weaknesses": "1. The final convergence rates are path-dependent. Although they are more refined and should be better than classical rates, it is not clear how large the gap is. I wonder if there are any interesting applications for which their rates can be more explicit and show clear improvement over classical ones.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**1. I wonder if there are any interesting applications for which their rates\ncan be more explicit and show clear improvement over classical ones.** \n\nYes, and we provide such an example in Section 4.1 for quadratics. In this\nexample, instead of the convergence rate relying on the largest eigenvalue of\nthe constant Hessian matrix, our results show that the convergence rate relies\ninstead on Rayleigh coefficient with respect to the local gradient. This\nRayleigh coefficient is smaller than the largest eigenvalue, unless the local\ngradient happens to be exactly the eigenvector associated to the largest\neigenvalue. \n\n**2. Have the authors considered non-convex settings?**\n\nPlease see the general response.\n\n**3. Connections to edge of stability and adaptivity.**\n\nThere are close connections betweens directional smoothness, edge of stability,\nand the performance of adaptive gradient methods. Kwangjun et al. [1]\npropose an alternative definition of directional smoothness (which is closely\nrelated to our path-wise smoothness) and use this quantity to study the\nbehavior of SGD in stable and unstable regimes. Similarly, Yan et al. [2] consider a directional sharpness measure. They provide\nexperiments showing that directional sharpness is lower for adaptive methods\nlike Adam than for gradient descent. We will add these references to the paper.", "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": "d1Hls0H3ke", "reviewer": "Reviewer_vUdK", "summary": "The paper proposes a new type of non-uniform smoothness, which the authors label _directional smoothness_. Directional smoothness replaces $L$ in the typical $L$-smoothness inequality by a function $M(x,y)$, which describes the smoothness along the line between $x$ and $y$. The authors proof multiple basic properties of this notion as well as sub-optimality bounds for GD with general stepsizes in the deterministic convex setting. Additionally, they provide sub-optimality bounds for three specific stepsizes in the same setting.", "questions": "# Questions\n1. In the proof of Proposition 3.2, why does the last inequality (above line 438) hold? More specifically, in the case $\\eta_k > \\mu_k^{-1}$, the recursive argument cannot be applied as the sign is flipped. How do the authors deal with this case?\n2. Theorem 4.3 is very unclear to me. What is one “iteration” of GD? In order to reach a point $\\hat{x}_T$ with $f(\\hat{x}_T) - f(x^*) \\leq \\varepsilon$, do you require $\\widetilde{O}(\\varepsilon^{-1})$ or $\\widetilde{O}(\\varepsilon^{-2})$ gradient evaluations? Maybe these unclear points could be addressed by including the full algorithm, producing the final output $\\hat{x}_T$, in Algorithm 1.\n3. The authors first derive suboptimality bounds for general stepsizes, before proving results for specific stepsizes. However, the proofs for Theorems 4.4 and 4.5 are not based on the general results, rather they are standalone proofs. Why did the authors not plug in these stepsizes into the general results? This would be a great opportunity to showcase the application of Propositions 3.1 – 3.3.\n4. Given directional smoothness generalises other non-uniform smoothness notions, did the authors examine whether their sub-optimality bounds reconstruct / improve previous results for notions of smoothness that can be modelled by directional smoothness? For example, can results from $(L_0, L_1)$-smoothness [1] be reconstructed? The corresponding $M(x,y)$ is specified in [2, Lemma A.3] / [3, Lemma 8]. \n5. Is there hope for any lower bound results that show strongly adapted stepsizes are indeed the best (non-accelerated) stepsize one can choose in your generalized setting? Given such result, the Polyak-stepsize results would get even stronger.\n6. Are there any difficulties extending the notion of directional smoothness to the typical nonconvex setting and results, i.e. $|| \\nabla F(x) - \\nabla F(y) || \\leq M(x,y) || x-y||$ and the corresponding GD guarantees?\n\n[1]: Li et al., Convex and Non-convex Optimization Under Generalized Smoothness, NeurIPS 2023\n\n[2]: Zhang et al., Improved Analysis of Clipping Algorithms for Non-convex Optimization, NeurIPS 2020\n\n[3]: Hübler et al., Parameter-Agnostic Optimization under Relaxed Smoothness, AISTATS 2024\n\n# Remarks\n- There are multiple potential inconsistencies throughout the work. None of them have an impact on the soundness of the work, but it would be great if the authors could address them. \n\na) Most results use $k$, some use $T$ while others use $t$ as the last iteration index. \n\nb) The averaged iterate is sometimes denoted using hats while other times using widebars. \n\nc) There are inconsistencies whether differentiability assumptions are explicitly stated or not. In sections 2 and 4 they are consistently mentioned, section 3 and its proofs in the appendix do not mention it even-though it is required.\n\nd) Usage of $f(x^*)$ vs. $f^*$.\n\ne) Appendix C denotes the Euclidian norm by $|| \\cdot ||$, while all other sections use $|| \\cdot ||_2$.\n\nf) All results in the appendix besides the three Theorems are numbered relative to the appendix, the theorems relative to the main section.\n- Lemma A.4 might better fit in Appendix B. \n- Proposition 3.2 could potentially be improved by using $2 \\eta_k [f(x^*) – f(x_{k+1})] \\leq -\\eta_k \\mu_k \\Delta_{k+1}$ instead of removing the former term in the last inequality after line 435. This divides each term in the product by $(1+\\eta_k\\mu_k)$. \n- In it’s current version, Equation (41) does not provide additional information. The authors could either remove it or modify Equation (40) to include this step.\n- As mentioned in Line 562, the convergence results in Theorem 4.5 require some smoothness assumption such as $L$-smoothness. This assumption is missing in the statement of Theorem 4.5.\n\nBelow some potential typos.\n- Proposition 3.1: $\\delta_k$ -> $\\delta_{k+1}$\n- Proposition 3.2: $\\Delta_k$ -> $\\Delta_{k+1}$\n- Theorem 3.4, Case 1: Missing parenthesis\n- Equation (23): $\\bar x$ -> $\\bar x_t$\n- Last inequality in equation after Line 232: $M(x_{k+1},x_{k})^{-1}$ -> $M(x_{k+1},x_{k})$\n- Equation after Line 393: $f(x)$ -> $f(y) - f(x)$\n- Second inequality in equation after Line 435: $|| \\nabla f(x) ||$ -> $|| \\nabla f(x) ||^2$\n- Equation after Line 468: $\\Rightarrow$ -> $\\Leftarrow$ (or $\\Leftrightarrow$)\n- Equations after line 475: $M$ -> $D$\n- Algorithm 1, Line 1: $L_0$ -> $\\eta_0$\n- Algorithm 1, Line 3: Wrong parentheses\n- Line 527: follow -> following", "limitations": "The introduction could more clearly mention that the paper (besides Lemma 2.4) exclusively focuses on the deterministic convex setting.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The proposed smoothness notion – directional smoothness – is generalising many previous notions of smoothness while still allowing for a meaningful analysis of algorithms.\n- Convergence analysis with directional smoothness can potentially give some intuition which algorithms automatically adapt to (potentially beneficial) local smoothness properties.\n- The authors provide a wide range of properties for directional smoothness and different ways to compute upper bounds on the directional smoothness.\n- The sub-optimality gap for Polyak’s step-size, showing it automatically adapts to the local smoothness in a meaningful way, could potentially explain empirical success of the step-size schedule in practise.", "weaknesses": "- Many of the results until Section 4.2 are direct consequences of the (directional) descent inequality. In particular, it was to be expected that the global smoothness inequality can be replaced with a localized version, and that results along the lines of Proposition 3.1 – 3.3 should hold. That being said, these results can be seen as preliminary results for the propositions / theorems in the later portion of the paper, which provide new insights.\n- ~~There might be some questions regarding the soundness of Proposition 3.2, see Question 1. However, this result is not used in the consequent results and does hence not have any further implications.~~\n- Given this submission introduces a new way to analyse algorithms, seeing its application in different settings and for different algorithms would be highly beneficial to showcase the benefit of the proposed approach. All results in the work are however limited to the deterministic convex setting, and only Gradient Descent with different stepsizes is considered. Showcasing the approach for the stochastic setting or for different algorithms (such as Nesterov AGD) could give a more wholistic picture of the approach.\n\n---\n\n**Edit after Author Rebuttal**\n\nThe authors did fix the proof of Proposition 3.2.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. **Many of the results until Section 4.2 are direct consequences of the\n(directional) descent inequality.**\n\nThe reviewer has listed this as one of the weakness of our paper, but we would\nargue that this is a strength. It is this clear link between the definition of\ndirectional smoothness, the descent property, and the convergence rates that\nmakes directional smoothness such an interesting definition. We were very\nsurprised to see that such a natural definition had not been explored before.\n\n2. **Stochastic setting or different algorithms (such as Nesterov AGD) could give\na more wholistic picture of the approach.**\n\nWe agree that having the stochastic setting would strengthen the paper. But\nsince directional smoothness is a new concept, we decided on carefully\nanalysing the deterministic setting first, and leaving the stochastic setting\nfor future work. \n\nAs for analysing more algorithms, again we agree more would always strengthen\nthe paper. Yet, we already analyse four different settings of GD with a\nconstant step size, exponential line search, normalized gradient and Polyak\nstep-size.  These four settings already justify the utility of our new\ndefinition and also leave no additional room within a 9 page paper.\n\n3. **In the proof of Proposition 3.2, why does the last inequality (above line 438) hold?**\n\nIt looks like this is a minor bug. However, it's immediately corrected by\nupper-bounding as \n$$(1 - \\mu_k \\eta_k) \\Delta_k \\leq |1 - \\mu_k \\eta_k| \\Delta_k,$$\nsince $\\Delta_k \\geq 0$. \nThis doesn't affect the meaning of the proof since we need $\\eta_k \\leq 1 /\n\\mu_k$ for any hope of progress. \nMany thanks for pointing it out. \n\n4. **Theorem 4.3 is very unclear to me.**\n\nOne iteration in this setting means one single gradient access. So to get\n$f(\\hat{x}_T) - f(x^*) \\leq \\varepsilon$, we require\n$\\widetilde{O}(\\varepsilon^{-1})$ gradient accesses. The output of the\nalgorithm $\\hat{x}$ would come from running gradient descent one final time\nafter line 5 in Algorithm 1-- we will clarify this and write the algorithm in\nfull for the next version of the paper.\nThank you for drawing it to our attention.\n\n5. **Why did the authors not plug in these step-sizes into the general results?**\n\nThis is an excellent question. We would have preferred to proceed in this\nmanner, but the Polyak step-size and the normalized GD step-size are not\nnecessarily adapted to the directional smoothness. In other words, they are\nnot descent methods. Instead, Polyak and normalized GD make progress by\ndecreasing the distances $\\Delta_k = \\\\|x_{k} = x^*\\\\|_2^2$. As a result, we\nrequire dedicated proofs which leverage the specific structure of each\nalgorithm.\n\n\n6. **Can we reconstruct/improve results for other notions of smoothness using\ndirectional smoothness?**\n\nThank you for raising this question relating to $(L_0,L_1)$--smoothness and\npoint outing [2, Lemma A.3] and [3, Lemma 8]. Looking to Lemma A.3, though at\nface value it does fit our definition of directional smoothness with,\n$$M(x_{k+1},x_k) : = (AL_0+B L_1 \\\\|\\nabla f(x_k)\\\\|)/2,$$\nwe see an issue that prevents us from applying our theory. \nThe issue is related to the constants $A$, $L1$ and $B$ which\nactually depend on all iterations of the algorithm. \nThis is because the result of Lemma A.3 holds under the assumption that \n$$\\\\|x_k -x_{k+1}\\\\| \\leq c/L_1,$$ \nfor all iterations $k$, and for fixed constants $c$ and $L_1$. \nIn other words, we have that,\n$$\\max_k \\\\|x_k -x_{k+1}\\\\| \\leq c/L_1,$$\nand $c/L_1$ depends on the entire trajectory of the\nunderlying algorithm. \nFurthermore, the constants $A$ and $B$ depend on this\nconstant $c$ since,\n$$A = 1 + e^c -\\frac{e^c-1}{c},$$\nand,\n$$B =\\frac{e^c-1}{c}.$$\nConsequently the quantity $(A L_0 + B L_1 \\\\|\\nabla f(x_k)\\\\|)/2$ depends on\nall iterations, and thus doesn't fit our definition of directional smoothness.\nWe will continue to consider possible connections, and write a comment about\nthis in our updated draft. \n\n\n**7. Is there hope for any lower bound results that show strongly adapted\nstepsizes are indeed the best?**\n\nThis is an interesting and subtle problem since showing meaningful\nlower-bounds requires a minimum of variation in the curvature of $f$.\nFor example, if $f(x) = 0.5 \\\\|x - x^*\\\\|_2^2$, then the Polyak step-size is \njust $\\eta_k = 1/2$ and there is no difference between Polyak and vanilla GD. \nThis indicates that we may need to exclude \"simple\" problems like isotropic\nquadratics from the function class in order to prove that strongly adapted \nstep-sizes lead to strictly improved rates.\nSince this is highly non-trivial, we leave it to future work.\n\n\n**8. Are there any difficulties extending the notion of directional smoothness to\nthe typical nonconvex setting?**\n\nPlease see the general response.\n\n**9. Typographical issues and inconsistencies**:\n\nThanks for pointing these out. We will correct them for the camera ready\ndeadline.", "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": "MdYsXrQPAn", "reviewer": "Reviewer_Z7fB", "summary": "The work propose different directional smoothness function and use them to establish sub-optimality bounds that are adaptive to the optimization trajectory. This approach can be explicitly used in quadratics or with an exponential search technique for convex objectives to use adaptive stepsizes that enjoy better guarantees compared to constant stepsize GD tuned according to the global smoothness. Furthermore, the paper shows that Polyak and normalized GD obtain convergence guarantees that depend on the directional smoothness without modifying the algorithms.\nThe theoretical claims are empirically evaluated using two logistic regression problems.", "questions": "5. Can the framework be of use for stochastic optimization?\n\n6. Can the authors elaborate on the technical novelty of the results? In particular, it is arguably known that the standard analysis technique of GD exploits smoothness only between consecutive points. What is the main difficulty when we replace global smoothness with an adaptive variant?\n\nOverall, the paper presents an appealing framework for adaptive bounds which encompasses a long list of stepsize strategies, while the novelty and deterministic setting are somewhat in question.", "limitations": "See weaknesses.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The technique naturally yields results for several existing methods.\n2. Tighter, adaptive guarantees are appealing due to the observed success beyond the theoretical convergence bounds.", "weaknesses": "3. The paper discusses only deterministic optimization, while modern large-scale optimization is largely stochastic. It begs the question, which is not discussed in the paper, whether such approaches are even valid for stochastic optimization (e.g. [1]).\n\n4. The novelty of the approach is unclear for some of the observed results. Consider especially Theorem 4.4 with the Polyak stepsizes, which achieve the best empirical performance in the experiments. It is straightforward to translate the decrease mentioned in [2] (page 2, end of left column), $\\lVert x_{t+1} - x^* \\rVert^2 - \\lVert x_{t} - x^* \\rVert^2 \\leq - \\frac{(f(x_t)-f(x^*))^2}{\\lVert \\nabla f(x_t) \\rVert^2}$ to a bound of the weighted $\\overline{x}$ of $f(\\overline{x_t})-f(x^*) \\leq \\frac{\\lVert x_0 - x^*\\rVert^2}{\\sum_{k=0}^{t} \\eta_t}$. Theorem 4.4 can be considered as replacing $\\eta_t$ with a possibly worse $M(x_{t+1},x_t)$. In this case, the simple adaptive result is only framed for convenience in the directional smoothness framework.\n\n[1] N. Loizou, S. Vaswani, I. H. Laradji, and S. Lacoste-Julien. Stochastic Polyak step-size for SGD: An adaptive learning rate for fast convergence. In International Conference on Artificial Intelligence and Statistics, pages 1306–1314, 2021.\n\n[2] Hazan, E. and Kakade, S., 2019. Revisiting the Polyak step size. arXiv preprint arXiv:1905.00313.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nThank you for your time and review. We were pleased to see that you thought\nour \"tighter, adaptive guarantees are appealing due to the observed success\nbeyond the theoretical convergence bounds\" and that \"the technique naturally\nyields results for several existing methods.\" \n\nWe understand you currently do not appreciate Theorem 4.4, but our paper has\nmany other results (a total of 11 Lemmas, propositions and Theorems). Does the\nreviewer appreciate or have questions regarding any other specific part of our\npaper? \n\n1. **The paper discusses only deterministic optimization. Can the framework be\n   used for stochastic optimization?**\n\nWe agree that developing stochastic results is desirable and we are confident\nthat our framework is useful for stochastic optimization. For instance,\ndirectional smoothness has already been used (e.g. in [2]) to explore empirical\nproperties of stochastic algorithms.  However, we must leave exploring this in\ndetail to future work.\n\nSince directional smoothness is a new concept, we need the space in this paper\nto carefully characterize classes of functions which have a meaningful\ndirectional smoothness function, and to show how this is a useful concept for\nthe optimization. This is consistent with the literature, where optimization\nconcepts are often studied in the deterministic setting before being extended\nto stochastic optimization. For example, you have linked papers [4, 5] on the\nPolyak step-sizes; [5] only consider the deterministic setting and it took\nseveral years after its publication for [4] to study the stochastic setting. \n\n2. **The novelty of the approach is unclear for some of the observed results.**\n\nThe novelty of our approach is proposing a new directional smoothness\nassumption, showing that this assumption holds for differentiable functions,\nand then showing how directional smoothness function can be used to precisely\ncharacterize the convergence of first order methods.\n\n3. **Theorem 4.4 ... the simple adaptive result is only framed for convenience\n   in the directional smoothness framework.** \n\nTheorem 4.4 says that for *any* directional smoothness function $M$, the\nsub-optimality bound $\\frac{D^2}{\\sum_{k=0}^{t-1} M(x_{k+1}, x_k)^{-1}}$ holds, where $D=\\|x_0-x_{\\ast}\\|$.\nThe point of this theorem is to show that Polyak's method has a certain\nuniversality: whatever directional smoothness function $M$ exists, Polyak's\nalgorithm adapts to it. The proof the reviewer gives does not show\nthis, and while useful for establishing a convergence bound, doesn't indicate a\nuniversality property. Indeed, many algorithms achieve rates that look like\n$\\frac{D^2}{\\sum_{k=0}^{t-1} \\eta_{k}}$, e.g. GD with any\nstep-size sequence $\\eta_{k} \\leq \\frac{1}{L}$ achieves this rate. \nWhat sets our theorem apart is that it shows the Polyak\nstep-sizes possess an adaptivity that GD with a non-adaptive\nstep-size sequence does not.\n\nHowever, we will also add a remark showing how to conclude the proof by keeping\nthe Polyak step-size (i.e. without replacing it by directional smoothness).\nThis observation gives us new insights into the Polyak step-size, showing that\nthe Polyak step-size itself is a type of directional smoothness, and can be\nused to form a smoothness upper-bound such as Eq (1).\n\n4. **It is arguably known that the standard analysis technique of GD exploits\n   smoothness only between consecutive points.**\n\nThis is exactly what our work shows explicitly. Though intuitively GD is a\nlocal method, and should depend on local notations of smoothness,\nwe found that there is no satisfying prior definition and theory that captures\nthis local behaviour. Unless the reviewer has a reference in mind that they\ncould share? \n\nWe also note that tight proofs for the convergence of GD for non-strongly\nconvex functions (e.g. [3; Theorem 3.3]) actually do rely on smoothness\neverywhere rather than just between iterates.  This is because they use an\ninequality sometimes called co-coercivity, [3; Lemma 3.5] which requires global\nsmoothness. Moreover, the existence of an extensive literature on local\nLipschitz continuity shows that relaxing global smoothness assumptions is not\nstraightforward in general. \n\n5. **What is the main difficulty when we replace global smoothness with an adaptive variant?**\n\nFirstly, discovering the correct definitions of local/adaptive variants of\nsmoothness is not straightforward. \nSecondly, verifying conditions under which these variants yield directional\nsmoothness bounds and proving bounds like Prop. 3.1, which allow for steps\nto increase the optimality gap, both require developing non-standard proof\ntechniques.\nThe fact that these results seem obvious in hindsight is a testament to the\nfact that we \"got it right\" compared to the many other relaxations of\nsmoothness which have been proposed.\n\nThe main technical difficulty is that the directional smoothness depends on the\nstep-size. The standard analysis of GD starts with smoothness as\n$$f(x_{k+1}) \\leq f(x_k) + \\langle \\nabla f(x_k), x_{k+1} - x_k \\rangle + \\frac{L}{2} \\\\| x_{k+1} - x_k \\\\|^2 = f(x_k) - \\eta_{k} (1 - \\frac{\\eta_k L}{2}) \\\\| \\nabla f(x_k) \\\\| ^2,$$ \nfrom which we obtain convergence\nof the gradient norm when $\\eta_k < \\frac{2}{L}$. \nWhen we replace $L$ by a directional smoothness $M$ instead, we get the requirement \n$\\eta_{k} < \\frac{2}{M(x_{k+1}, x_k)}$. \nBoth sides of the equation depend on $\\eta_{k}$, as $x_{k+1}$ depends on $\\eta_k$. \nThis implicit equation is not\nstraightforward to solve and it's not obvious that a solution even exists. \nWe prove that strongly adapted step-sizes do exist, derive new\ndirect methods for computing such step-sizes (root-finding, exponential\nsearch), _and_ establish novel connections to normalized GD and the Polyak\nstep-size. Again, we believe the fact that these results are clean and\neasy-to-follow in hindsight is a strength of our work, not a weakness.", "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:
**1. Extensions to the non-convex setting.**

Deriving meaningful results for non-convex functions is challenging.
For example, we can immediately use the directional descent lemma to obtain,

$$\\begin{aligned} \\eta_k (1 - \\frac{\\eta_k M_k}{2}) \\| \\nabla f(x_k) \\|^2_2 & \\leq f(x_k) - f(x_{k+1}) \\\\ \\implies \\frac{1}{K} \\sum_{k=0}^{K-1} \\eta_k(1 - \\frac{\\eta_k M_k}{2})\\|\\nabla f(x_k)\\|_2^2 &\\leq \\frac{1}{K}(f(x_0) - f(x_K))\\end{aligned}$$

This inequality shows that the main challenge is computing (strongly) adapted
step-sizes such that $\eta_k \leq 1 / M_k$. 
While the majority of our paper is concerned exactly with this problem,
our approaches rely on convexity;
the only result we can obtain for the non-convex setting is to use path-wise
smoothness and apply Prop. 4.2 along with a root-finding method. 
Such an approach is not practical because we cannot easily calculate the
path-wise smoothness. 

In contrast, in the convex setting we can easily calculate the point-wise
directional smoothness (as given by Lemma 2.2). Unfortunately, the analog of
Lemma 2.2 is false in the non-convex setting. Consider the function $f(x) =
\frac{x^2}{2} + 2e^{-(x-\frac{1}{2})^2/2}$. This function is non-convex due to
the Gaussian bump centered at $x=\frac{1}{2}$ with amplitude 2. For $x = 1.14$
and $y=-1.05$, we have,
$$f(x) \approxeq 2.2794 > 1.8352 \approxeq f(y) + \langle \nabla f(y), x-y \rangle + 2 \\|\nabla f(x) - \nabla f(y)\\| \\|x-y\\|.$$ 
If the reviewers request, we can include this counterexample in the paper to
highlight the added difficulties in the non-convex setting.

We intend to develop theory for the non-convex setting, but, because non-convex
functions require new adapted step-size schemes, we believe that this is beyond
the scope of our paper. 


## References

[1] Ahn, Kwangjun, Jingzhao Zhang, and Suvrit Sra. "Understanding the unstable
convergence of gradient descent." International Conference on Machine Learning.
PMLR, 2022.

[2] Pan, Yan, and Yuanzhi Li. "Toward Understanding Why Adam Converges Faster
Than SGD for Transformers." OPT 2022: Optimization for Machine Learning
(NeurIPS 2022 Workshop).

[3] Bubeck, Sébastien. "Convex optimization: Algorithms and complexity." Foundations and Trends® in Machine Learning 8.3-4 (2015): 231-357.

[4] N. Loizou, S. Vaswani, I. H. Laradji, and S. Lacoste-Julien. Stochastic Polyak step-size for SGD: An adaptive learning rate for fast convergence. In International Conference on Artificial Intelligence and Statistics, pages 1306–1314, 2021.

[5] Hazan, E. And Kakade, S., 2019. Revisiting the Polyak step size. ArXiv preprint arXiv:1905.00313.

Meta-review: By leveraging directional smoothness—a local, path-dependent condition—rather than global smoothness as in classical analyses, this paper presents new sub-optimality bounds for gradient descent (GD). While computing a step-size adapted to the directional smoothness involves solving a challenging implicit equation, the paper shows that for convex quadratic functions, this equation admits a closed-form solution. For general convex functions, the paper demonstrates that the Polyak step-size and normalized GD achieve fast, path-dependent rates without requiring knowledge of directional smoothness. Experimental results are provided to validate the theoretical convergence guarantees.

Overall, the reviewers find the contributions of the paper to be interesting and valuable. However, several suggestions/questions/concerns have been raised during the review process, which the authors are strongly encouraged to incorporate into their final revision.
Decision: Accept (poster)