Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
Authors: Sharan Vaswani
Reza Babanezhad Harikandeh
Venue: ICML 2025 poster (2025)
Keywords: Armijo line-search
(Stochastic) Gradient descent
Convergence rates
Logistic regression
Policy optimization
Generalized linear models
Interpolation
Primary area: optimization
TL;DR: Using Armijo line-search can lead to exponential improvements in the gradient descent convergence rate for problems such as logistic regression and policy optimization in reinforcement learning.

Abstract: Armijo line-search (Armijo-LS) is a standard method to set the step-size for gradient descent (GD). For smooth functions, Armijo-LS alleviates the need to know the global smoothness constant $L$ and adapts to the ``local'' smoothness, enabling GD to converge faster. Existing theoretical analyses show that GD with Armijo-LS ($\texttt{GD-LS}$) can result in constant factor improvements over GD with a $1/L$ step-size (denoted as $\texttt{GD(1/L)}$). We strengthen these results and show that if the objective function satisfies a certain non-uniform smoothness condition, $\texttt{GD-LS}$ can result in a faster convergence rate than $\texttt{GD(1/L)}$. In particular, we prove that for convex objectives corresponding to logistic regression and multi-class classification, $\texttt{GD-LS}$ can converge to the optimum at a linear rate, and hence improves over the sublinear convergence of $\texttt{GD(1/L)}$. Furthermore, for non-convex objectives satisfying gradient domination (e.g., those corresponding to the softmax policy gradient in RL or generalized linear models with a logistic link function), $\texttt{GD-LS}$ can match the fast convergence of algorithms tailored for these specific settings. Finally, we analyze the convergence of stochastic GD with a stochastic line-search on convex losses under the interpolation assumption.

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
Sharan Vaswani'
Reza Babanezhad 2
Abstract
Given an initial step-size, the simplest form of Armijo-LS "searches" for the largest step-size that guarantees a suf- ficient decrease in the function value. When minimizing L-smooth functions using GD, Armijo-LS alleviates the need to know L, the global smoothness constant and en- ables setting the GD step-size in an adaptive manner. For both L-smooth convex and non-convex functions, GD with Armijo-LS (henceforth GD-LS) has been shown to match the favorable theoretical guarantees of GD with a constant step-sizze (henceforth GD (1/L) ). However, empirically, GD typically results in faster convergence and is conse- quently, the default choice in practice.
Armijo line-search (Armijo-LS) is a standard method to set the step-size for gradient descent (GD). For smooth functions, Armijo-I. allevi- ates the need know the global smoothness con- stant L and adapts to the "local" smoothness, enabling GD to converge faster. Existing theo- retical analyses show that GD with Armijo-LS (GD-LS) can result in constant factor improve- ments over GD with a 1/L. step-size (denoted as GD (1/L)). ). We strengthen these results and show that if the objective function satisfies a certain non- uniform smoothness condition, GD-LS result in faster convergence rate than GD (1/L). In particular, we prove that for convex objectives cor- responding to logistic regression and multi-class classification, GD-LS can converge to the opti- mum at a linear rate, and hence improves over the sublinear convergence of GD (1/L). Further- more, for non-convex objectives satisfying gradi- ent domination (e.g. those corresponding the softmax policy gradient in RL or generalized lin- car models with a logistic link function), GD-LS can match the fast convergence of algorithms tai- lored for these specific settings. Finally, we an- alyze the convergence of stochastic GD with a stochastic line-search on convex losses under the interpolation assumption.
One often-cited reason to explain the faster convergence of GD-LS is that it adapts to the "local" smoothness constant L(0) near the point 6, and results in an effective step-size of 1/L(0). In some regions, L()) might be much smaller than the global smoothness L, thus allowing GD-LS to use much bigger step-sizes and consequently lead faster conver- gence. Existing works that define notions of local smooth- ness (Scheinberg et al., 2014; Lu & Mei, 2023; Mishkin et al., 2024; Fox & Schmidt, and references there in) can be used to formalize this intuition and show that GD-LS can result in constant factor improvements over GD (1/L), while having the same rate of convergence. In contrast, we consider a special class of objective functions and show that GD-LS (with large initial step-size) can result in provably faster rate of convergence compared to GD (1/L), In particular, we make the following contributions.
Contribution 1. In Sec. 2, we introduce a class of func- tions that satisfy an (Lo, L1) non-uniform smoothness con- dition. In particular, we consider functions where the local smoothness constant around point is given by ((0) Lu + L2 f(O) where Lg and L1 non-negative constants (and T., = O corresponds to the standard uniform smoothness). We show that the proposed condition is satis- fied by common objectives; for example, both the logistic and exponential losses used for linear classification satisfy the condition with La = 0 and I, o O. Furthermore, we prove that this condition is also satisfied by non-convex functions corresponding generalized linear models with logistic link function, and the softmax policy gradient objective in reinforcement learning.
1. Introduction
Gradient descent (GD) (Cauchy et al.. 1847) and its stochas- tic variants are the preferred optimization methods in ma- chine learning. The practical effectiveness of gradient meth- ods heavily relies on the choice of the step-size ("learning rate") parameter. Backtracking Armijo line-search (Armijo, 1 1966; Nocedal & Wright, 2006) (referred as Armijo-LS) is a standard method to set the step-size for gradient descent.
Simon Fraser University "Samsung AI, Montreal. Correspon- dence Sharan Vaswani <vaswani. sharan @ .omm,,com>, Reza Babanezhad <babanezhad @ gomi..com>.
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
This condition is similar to that proposed in Zhang et al.

---

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
(2019) to explain the success of normalization and gradient clipping when training neural networks. The difference is that we consider problems where the smoothness is pro- portional to f(0) rather than [+)]l (Zhang et al., 2019; 2020; Chen et al., 2023). Furthermore, in Sec. 2, we show that non-negative, wiice-differentiable fiunctions satisfying the non-uniform smoothness condition in Zhang et al. (2019) satisfy the proposed condition.
mality. Specifically, in Sec. 5.1, we analyze the convergence of GD-LS for the softmax policy gradient objective in re- inforcement learning (Mei et al., 2020). In this setting, the linear convergence rate attained by GD-LS is provably bet- ter than the 221/+) convergence of GD (1/I.) and matches the rate of natural policy gradient (Kakade & Langford, 2002). In Sec. 5.2, we analyze the convergence of GD-LS for functions satisfying the PL condition (Polyak, 1987; Karimi et al., 2016) and instantiate the result for generalized linear models with the logistic link function. Our result demonstrates that GD-LS can converge faster than both constant step-size and normalized GD (Hazan et al., 2015).
Contribution 2. In Sec. 3, we analyze the convergence of GD-LS on functions satisfying the proposed conditions. We first prove that the step-size selected by GD-LS around 0 is lower- bounded by 1/f( and hence, GD-LS provably adapts to the local smoothness. We use this to prove Thm. I, a meta-theorem that quantifies the convergence rate of GD-LS for both convex and non-convex objectives.
Contribution 5. Finally, in Sec. 6, we investigate whether the advantages of line-search carry over to the stochastic set- ting. Specifically, we consider a finite-sum objective f0) = n Σ f0),, and study the convergence of stochastic gra- dient descent (SGD) in conjunction with a stochastic line- search proposed in Vaswani et al. (2019b). We restrict our attention to the interpolation setting (Vaswani et al., 2019a; Ma et al., 2018; Schmidt & Roux, 2013) which implies that each fa is minimized at l == arg min ((). The interpola- tion assumption of practical interest (Zhang et al., 2017; Belkin et al., 2019), for example, it is satisfied for logistic regression with linearly separable data.
1
Contribution 3. In Sec. 4, we instantiate Thm. 1 for non- uniform smooth, convex losses that include logistic regres- sion and multi-class classification with the cross-entropy loss as examples. Specifically, in Cor. 1, we show that GD- (with a sufficiently large initial step-size) converges at an O ((5%)) In (1/c) rate where f == inf f(). Hence, when ʃ* is O(e), GD-LS converges at an O (In (4/+) rate, compared to the sublinear 0(/4) convergence of GD (1/L). We further instantiate this result for logistic regression on linearly separable data, and prove the linear convergence of GD-I.S (Cor. 2), thus matching the rate for normalized GD (Axiotis & Sviridenko, 2023). In App. C, we show that GD with the Polyak step-size (Polyak, 1987) can inherit this fast convergence for logistic regression.
Interpolation enables the fast convergence of SGD, allow- ing it to match the GD convergence rate, but with an O(1) iteration cost. Under interpolation, SGD with a stochastic line-search (referred to as SGD-SLS) and its variants em- pirically outperform constant step-size SGD, and have been used to train deep neural networks (Vaswani et al., 2019b; Galli et al., 2024). We further investigate the convergence of SGD-SLS for logistic regression with linearly separable data, and prove that it can leverage non-uniform smoothness to achieve faster rates.
In comparison to our results, most work exploiting non- uniform smoothness (Zhang et al., 2019; 2020; Koloskova et al., 2023; Chen et al., 2023; Li et al., 2023) requires the knowledge of the corresponding problem-dependent constants. Notable exceptions include Hübler et al. (2024) and (Vankov et al., 2024: Takezawa et al., 2024; Gorbunov et al., 2024) that consider GD-LS and the Polyak step-size respectively, and aim to minimize the class of con-uniform smooth functions in (Zhang et al., 2019). In particular, the work in Hübler et al. (2024) considers general non-convex functions and does not demonstrate the algorithm's 's adaptiv- ity to the smoothness, nor does it result in a faster rate than GD (1 (1/I.). Moreover, their resulting algorithm requires the knowledge of the non-uniform smoothness constant, making it impractical. On the other hand, (Vankov et al., 2024; Takezawa et al., 2024; Gorbunov et al., 2024) con- sider minimizing convex, non-uniform smooth functions using GD with the Polyak step-size. In Sec. 4, we show that GD-LS (without any modification) can achieve a similar convergence guarantee as these works.
2. Problem Formulation
We aim to solve the unconstrained minimization problem: mingER f().. We detine 0* E arg inf f0) as an optimal solution and f := inf f f(f as the minimum function value. Throughout, we consider / to be twice-differentiable and satisfying the following assumptions:
Assumption 1. f is non-negative i.e. for all 0. f() 2 O.
Assumption 2. f is L1) non-uniform smooth i.e. for constants Lo. L 2 0.
(a) For all xr y such that || - yll S h, where q 2 1 is
constant, if A == 1 1 e
1- and B :- 1-
9
f(y) S f(x) - (Vf(z), - x)
(A + B f(x)
Contribution 4. In Sec. 5, we instantiate Thm. for non- convex functions satisfying non-uniform smoothness and gradient domination conditions that guarantee global opti-
20 (1)
2
(b) For all A, [| S Lo + I. 1())
2

---

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
The above condition is similar to the non-uniform smooth- ness conditions proposed in the literature (Zhang et al., 2019; 2020; Chen et al., 2023). Subsequently, we will see that this alternate definition of non-uniform smoothness is more general and enables a simpler analysis for GD-IS.
Proposition 2. Consider a points where x, R are the features and yi [0, 1] are the corresponding labels. If (T(0) = o ((zi, 0)) -eepp-((a,00) the GLM objective,
1 2n
f(0)
(T: y1)
(4)
L = 0, Assn. 2 recovers the standard uniform smooth- ness condition as a special case. Consequently, common smooth objectives such as linear regression or logistic regression satisfy the above condition. For example, if X E Rdx= is the feature matrix, and y E R" is the vec- tor of measurements, then the linear regression objective, f(0) = 2n |X f - ull2 is (2 1mmxxxX' [XTX],0 0) non-uniform smooth where [ is the maximum eigenvalue of the positive semi-definit matrix A.
max || 1. 1 9 maxieja] [1 and Assn. 3 with v = 9 max; || w = max; ||ar|]|
satisfies Assn. 2 with Lo 16
Finally, in App. A. we show that the objective for softmax policy gradient (Mei et al., 2020) also satisfies the required assumptions for multi-armed bandits and tabular Markov decision processes, and we study these objectives in See. 5.
In order to show the benefit of GD with Armijo line-search, we will focus on functions where L1 # O, and the smooth- ness depends on the function value. We will require these functions to satisfy an additional assumption that relates the gradient norm to the function value. As we will see, such an assumption is true for losses with an exponential tail, even when using 2 layer neural network (Taheri & Thrampoulidss, 2023; Wu al., 2024).
Connection to non-uniform smoothness in Zhang et al. (2019): Assn. 2 and 3 related to the non-uniform smooth- ness condition proposed in Zhang et al. (2019) and analyzed in Zhang et al. (2020); Li et al. (2023); Chen et al. (2023); Vankov et al. (2024); Gorbunov et al. (2024). In particular, we prove the following result in App. A.
Proposition 3. For non-negative, wiice-differentiabl function J. if is (Les Lg) non-uniform smooth according to Zhang et al. (2019) iee.
Assumption 3. For all 0, there exist constants w, 2 s.s.
| f(0)ll v f(0) ww.
(2)
To motivate the above assumptions, we prove that common convex objectives for supervised learning such as linear logistic regression and linear multi-class classification sat- isfy Assn. 2 with Lp 0 and non-zero L1. Moreover, we show that these functions also satisfy Assn. 3 with = O. Below, we state the result for logistic regression, and defer the other results and all proofs to App. A.
|| S L. + Ly IIV
then, it is satisfies Assn. 2 with Lo = Lu + Lg V2T and Li Lg (8Lg + v2Lo) and Assn. 3 with 8Lg + V2T. and w = V2T.c.
Hence, the (Le, Ly) non-uniform smoothness in Zhang et al. (2019) implies Assn. 2 and 3. Consequently, our subsequent results also apply to non-negative, wiiee-differentiable, (L, non-uniform smooth functions.
Proposition 1. Consider n points where 2; E Rdd are the features and yi E {-1,1} are the corresponding labels. Logistic regression with the objective
1 Σ In(1 +
In order to further motivate Assn. and 3, consider the logistic regression example in Prop. 1. For logistic regres- sion, the loss corresponding to a single point satisfies the notion of (Iee I.g) non-uniform smoothness with L. 0 and by = ||0;||| (Gorbunov et al., 2024, Example 1.6). How- ever, the finite-sum over points (O) in Eq. (3)) does not necessarily satisfy this assumption with L. = 0 (see Prop. 8 for a simple example with n = 2). Consequently, unlike the result in Prop. 1, using the (Le, Lg)) condition in con- junction with Prop. 3 does not directly imply that Lo = O. In Sec. 4, we will see that, for logistic regression, having Lo = 0 is the key to achieving fast convergence for GD-LS. This further justifies our alternate definition of non-uniform smoothness.
f(0)= = n
(3)
1| satisfies Assn. 2 with Lo = O. L1 maxxee and Assn. 3 with max; ||aa|l. w 0.
Note that the logistic regression objective is also uniform smooth, meaning that it simultaneously satisfies Assn, 2 with Ly = 4n Amax [X"x X] and L = O, where X E Raxd the corresponding feature matrix. On the other hand, binary classification with the exponential loss is not uniform smooth on an unbounded domain, but satisfies Assn. 2 with ||x; l (see Prop. 6 in App. A).
Lo- = 0, Li 8 max
Next, we show that the non-convex objective corresponding to the generalized linear model (GLM) with a logistic link function also satisfies Assn. 1 to 3. In particular, we prove the following proposition in App. A.
Now that we have motivated Assn. to 3, in the next section, we consider minimizing such non- uniform smooth functions using gradient descent with Armijo lene-search.
3

---

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
3. GD with Armijo Line-search
in practice. In contrast to these works that show constant factor improvements for GD-LS, study non-uniform smooth functions satisfying Assn. 2 and 3, and aim to show that GD-LS can result in a faster rate of convergence.
The update for gradient descent (GD) with Armijo line- search (Armijo, 1966) (henceforth referred to as GD-LS) at iteration E [T'] is given as: 0t+1 = 0g - ne f(0)), where t is the step-size returned by the backtracking Armijo line- search (referred to Armijo-LS). In particular, starting from an initial maximum step-size 7max. Armijo-LS uses backtracking to select the (approximately) largest step-size that satisfies the Armijo condition,
We first show that, when minimizing non-uniform smooth functions satisfying Assn. and 3, GD-LS can result in prov- ably larger step-sizes that enable faster convergence. For the subsequent theoretical analysis, we only consider "exact backtracking" i.e. we assume that the backtracking proce- dure returns the largest step-size that satisfies the Armijo condition, meaning that / x 1. Similar to the standard analysis (Nocedal & Wright, 2006), it is straightforward to relax this assumption. We prove the following lemma that hower-bounds the step-size returned by GD-IS.
S(O,- - V/. ((OO)) s ((0)) - on [V
(5)
where E (0, 1) is a tunable parameter. The complete pseudo-code is described in Alg. 1. The parameter 3 con- trols the backtracking and is typically set to 0.9, while the parameter с is typically set to a small value such as 10-1 (Nocedal & Wright, 2006).
Lemma 1. If f satisfies Assn. 1 to 3, at iteration t. CD-LS 1
returns a step-size Te min {
7mmaxx AotA [(0.) j. where
X = 3 Lothow and X1 := 3 (x(+1)) (1-c)
(1-c)
Algorithm GD with Armijo Linrchearch (GD-IS)
1: Input: Do. 7mmax c E (0, 1), 3 E (0,
Note that when L1 = O. the lower-bound on T7t is similar to that for uniformly smooth functions. However, when Lo 0 and w = 0 (e.g. for logistic regression in Prop. 1), the lower-bound on т) is proportional to (0.( meaning that as f(0) decreases, the step-size returned by Armijo-LS increases. This enables the faster convergence of GD-LS.
2: for t = =O...., T.....T--.... 1 do
3: vi + -maax
4: while f(0,- - ij. V (0.)) > f(0.) - o (VS00)
do
5:
fj + rjc 8
6: end while
We now present a meta-theorem (proved in App. B) that characterizes this fast convergence for both convex and non- convex functions. It requires an additional condition which lower-bounds the gradient norm in terms of the function sub- bubb-opiimllity. In Sec. 4, we use convexity to satisfy this condition, whereas in Sec. 5, we use gradient domination to satisfy it. We also require that the step-size is not con- strained by the initial choice, but rather by the properties of the function. This can be achieved by using large 7max which is greater than Ao+Ai f(0.) for all or by using borward-tracking line-search to (approximately) return the largest step-size satisfying the Armijo condition (Fridovich- Keil & Recht, 2019). For conciseness, we express this requirement as 7max co. We note that it is straightfor- ward to relax it and get an explicit dependence on Mmax albeit at the cost of clarity in our theoretical results.
7:
1) 1/e
8:
0.+1 = 0g - 7/ ((.)))
9: end for
When using GD-LS for minimizing L uniformly- smooth functions (corresponding to Lo * O and L = 0 in Assn. 2), 1) is constrained to lie in the min { [mmax: 2(1-o) 2006). Note that this bound holds for all L uniformly- smooth functions, does not require convexity, and guar- antees that the backtracking line-search will terminate at a non-zero step-size. The parameter e controls the "aggres- siveness" of the algorithm; small e values encourage larger step-size. Hence, Armijo-LS can be seen as method to ob- tain step-size proportional to 1/L, without the knowledge of the global smoothness constant.
L. j 7max range (Nocedal & Wright,
Theorem 1. For fixed > 0, if satisfies Assn. 1 to 3. and if for a constant R > 0, || (0,)) 2 [((0)) for all iterations E [T", then, GD-LS LS with Tmax = 3o requires
These bounds on the step-size can be used to derive the convergence rate for GD-LS. For example, for uniformly L-smooth and convex functions, the standard analysis shows that GD-LS converges to an optimum at an (1/TT) rate (Nocedal & Wright, 2006). It thus matches the rate of GD with constant step-size equal to 1/L (henceforth referred to as GD (1/L)). ). However, as alluded to in Sec. I, Armijo-LS enables GD to adapt to the "local" smoothness ((,)) (the smoothness around iterate f,), and results in faster convergence both in theory (Scheinberg et al., 2014; Lu & Mei, 2023; Mishkin et al., 2024; Fox & Schmidt), and
R
max(2RXI,1) 1} (++ In (100)-f)
if 2 X1 - (Case (1))
T2
2h + m2, +1+ In (100)-1')
otherwise
(Case (2))
iterations to ensure that f(Or) - f S.
4

---

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
Proof Sketch. Using the condition [V) 2 with the Armijo condition in Eq. (5) and the lower-bound on tie from Lemma 1, we get that
- R
w
GD-LS with 7mmax
00, requires T 2
max (2 100 - 0 13 [ +1 In (( iteru-
tions to ensure that f(OT) f SE
[S(0.) -4
5(0++)) 1(0.)- - DAu + X1 f(0)) R
(6)
ECSM Locitic
Figure 1. .Comparing GD-LS with 1/2 and 7/max 10" and CD (1/L) for unreg- ularized logistic regression on the i ijenn dataset (Chang & Lin, 2011). f" is small and GD-1.$ converges faster.
We now split the proof into two cases: Case (1) when f(O)) 2
At Ay for all t E [T]. In this case, A1 f(;) 2 Ag- Using this relation with Eq. (6) and following the argu- ments in Axiotis & Sviridenko (2023, Theorem 5.2) allows us to complete the proof of Case (1). For Case (2), we follow the proof of the first case for iterations & [T] for which f(t)) 2 Ao and obtain a similar rate. This corre- sponds to Phase I. wiit faster convergence. For all iterations
Referring to the explanation following Thm. 1, we conclude tht GD-LS can result in faster convergence than GD (1 (L) when f is small (see Fig. for an experimental validation).
I E T. (O,) S du and hence Ao 2 A (f.). Using this relation with Eq. (6) and following the standard proof for uniformly smooth functions completes the proof for Phase 2. which results in slower convergence. Putting the results for both phases together completes the proof of Case (2). D
Xi
In order to compare the result in Cor. with existing works, consider the special case of logistic regression. In this case, GD GD-LS matches the rate for a variant of normalized gradient descent (NGD) in Axiotis & Sviridenko (2023, Theorem 5.2). However, unlike GD-LS, NGD requires the knowl- edge of L, making it relatively difficult to be implemented in practice. Furthermore, we note NGD is a specialized algorithm that is helpful to attain faster rates for certain problems (Mei et al., 2021; Hazan et al., 2015; Wilson et al., 2019), whereas GD-LS is universally used and can automat- ically exploit the problem structure. Moreover, Cor. is more general and also holds for the exponential loss.
In order to interpret the above theorem, let us first consider the setting corresponding to a = 0. Here, case (2) is ac- tive, and the algorithm requires ((1/c) iterations to achieve the desired sub-optimality, matching the standard result for uniformly smooth functions. Now consider the setting when Ao= = O. Here, case (1) is active, and GS- requires (t)) iterations. The iteration complexity thus depends on f*, and in cases where f is small, GD-LS can result in improved rate. As concrete example, con- sider the case when = O(f*). In this setting, CD-LS will result in a faster O (R In (2)) convergence. Note that GD (1/L) does not benefit from such adaptivity, and will always result in a sublinear rate. For non-zero Au and '1, the resulting rate depends on the value of f If f is larger than the threshold X/ GD-LS can result in the potentially fast rate corresponding to case (1), whereas if f* is smaller than the threshold, the algorithm has a two-phase behaviour: fast convergence until the loss becomes smaller than the threshold, followed by slow convergence to the minimizer.
( ( In
While GD (1/L) results in an 2(1/c) rate for gen- eral smooth, convex functions (Nesterov et al., 2018), analyses of GD on logistic regression often ex- ploit strong-convexity and prove faster rates (Karimi et al., 2016). In particular, if the iterates lie in a bounded set, the objective is μuf) strongly-convex where m(0)= = X min; (0) (1 - TT() where m, = I I+exp(-w. ()). Notice that as (0) tends to either zero or one i.e. the predictions become deterministic, m(0) tends to O. Freund et al. (2018, Theorem 3.3) characterize the re- sulting rate for GD (1/L) and prove that the suboptimality scales as O (cxp(-T exp (-1/e)) where È is the degree of non-separability and tends to zero the data becomes more separable. Hence, the rate becomes exponentially worse as & decreases. However, as the data becomes separable, GD-LS converges at a faster linear rate (see Fig. 2), meaning that strong-convexity cannot explain this behaviour.
In the next section, we instantiate the above theorem to prove the fast convergence of GD-LS for convex losses.
4. LS for Convex Losses
In this section, we characterize the convergence rate of GD-LS on convex losses satisfying Assn. 1 to 3. Recall that binary classification using logistic regression and multi- class classification using the cross-entropy loss both sat- isfy Assn. to with Lo- = and w = 0. Consequently, we only instantiate Thm. for this setting and prove the following corollary in App. C.
Consequently, we consider the special case where the data is linearly separable and f 0, and better characterize the fast convergence of GD-LSS Unfortunately, we cannot directly use Cor. I since ||0|| + oo f()) + O. making the resulting bound vacuous (Orabona, 2024). Consequently, we use a different technique, and first prove the following theorem in App. C.
Corollary 1. For a fixed e > O, assuming f()) is convex and satisfies Assn. to 3 with Lo = and
5

---

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
Theorem 2. For an initialization Og. t E (0, (00)) and comparator s.t. [()) I c, if f(0) is convex, safis- fies Assn. I to 3 with Lo = 0, = 0, then, GD-LS with [(0 1 c
step-size (Polyak, 1987) (which does not necessarily re- sult in monotonic descent in the function values) can also achieve the linear convergence rate in Thm. 2.
Thnax = =0,, c > 2. requires T 2 < 1000 2
(2c-1)
Convergence under (Le. Lg) non-uniform smoothness: Using the reduction in Prop. 3 allows characterizing the con- vergence of GD-LS on wiice-differeniiabee, non-negative, (Le, non-uniform smooth (Zhang et al., 2019) and con- vex functions. In particular, by using Prop. 3 in conjunction with Thm. 1 allows us bound the sub-optimality for the last-iterate of GD-LS (see Cor. 5 in App. C. for the formal statement) without requiring the knowledge of Le or Lg. In particular, assuming Lg 2 1, L 2 1, we prove that n CD-LS requires Ö ( ( + L, (13+2))
iterations to ensure that f(Or)= - f(u) S.
Compared to Cor. 1, the above result only holds for re- stricted range of and a comparator s.t. f(u) S c. Note that since f is non-negative and GD-LS ensures monotonic descent, its sub-optimalityy is upper-bounded by f(0n). The result only requires the non-uniform smoothness assump- tions and thus holds for the exponential loss, logistic regres- sion and multi-class classification.
iterations. In contrast, in this same setting, Vankov et al. (2024); Gor- bunov et al. (2024) show that GD with the Polyak step-size requires O ( (max { [rr, Lig R2) iterations for the best-iterate to achieve an sub-optimality (Gorbunov et al., 2024, Thm. 4.1). Comparing the two results, we note that, in general, the upper-bound in (Gorbunov et al., 2024) is tighter in terms of c. However, when e = ((**) the two bounds are equiv- alent in their e dependence. Moreover, while the results in Gorbunov et al. (2024); Vankov al. (2024) hold for the hest-iterate of GD with the Polyak step-size (that requires the knowledge of f*), Cor. 5 holds for the last-iterate and does not require knowing s"
We now use the above result and prove the following corol- lary for logistic regression on separable data (similar results hold for the exponential loss and multi-class classification).
Corollary 2. For logistic regression on linearly separable data with margin 7, if. for all i, || S 1, for an initial- ization Oo E E ((0)), GD GD-LS with Tmax
requires T 2 O 189 In (+)1") ensure that f(Or) 22.
iterations to
Hence, linearly separable data, GD-LS can achieve linear rate of convergence for logistic regression (see Fig. 2 for an experimental validation). In this setting, Wu et al. (2024, Theorem 3) show that GD (1/L) (or more generally, GD with any constant step-size that guarantees monotonic descent) cannot have a convergence rate faster than ((//e). Hence, GD-IS can result in an exponential improvement over the rate for GD (1/L). Furthermore, the rate in Cor. 2 is better than the (1///c) rate for GD with large (beyond L/L) constant step-sizes (Wu et al., 2024). Finally, we note that, in this setting, no algorithm that guarantees monotonic descent in the function values can achieve rate faster than the linear rate (Zhang et al., 2025, Theorem 2.2), Hence, in this sense, LS is optimal for logistic regression.
Next, we analyze GD-LS on non-convex losses.
5. GD-LS for Non-convex Losses
In this section, we consider non-convex losses that satisfy two alternative gradient domination conditions which enable convergence to the global optimum. In Sec. 5.1, we analyze the convergence of GD-LS for objectives corresponding to the softmax policy gradient in reinforcement learning. In Sec. 5.2, we consider objectives satisfying the Polyak- Lojasiewicz (PL) condition (Karimi et al., 2016; Polyak, 1987). and study the generalized linear model with a logistic link function as an example.
Assumption 4. f satisfies a non-uniform gradient domina- tion condition if there exists a constant Ç 2 and p(0) > 0 s.t. for all 6, | 2 (f()- ff]
Gradient domination or Lojasiewicz conditions are satis- fied for matrix factorization (Ward & Kolda, 2023), policy gradient in reinforcement learning (Mei et al., 2020) and generalized linear models (Mei et al., 2021). These con- ditions have been exploited to prove global convergence guarantees for first-order methods (Karimi et al., 2016; Mei et al., 2021).
Figure 2. Comparing GD-LS with c = 1/2, Mmax 10a and GD (1/L.) for unregularized logistic regression on synthetic separable dataset with 7 = 0.1, 10$ and 200. (Left) Sub-optimality plot: GD-L. converges lincarly, while GD (1 I.) has a sublinear convergence. (Right) Step-size plot: The GD-LS step-size increases non- monotonically.
5.1. Gradient domination with Ç = 1
We use softmax policy optimization for multi-armet bandits (MAB) as a concrete example that satisfies Assn. 1 to
Interestingly, in App. C. we prove that GD with the Polyak
6

---

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
and Assn. 4 with < 1. In particular, we consider an MAB problem in the exact setting with deterministic, known rewards. This setting is often used testbed to evaluate policy gradient methods (Xiao, 2022; Mei et al., 2020; Lu et al., 2024). We prove the following proposition in App. A. Proposition 4. Given an MAB problem with K arms and known deterministic rewards r E [0, 1]K, consider the class of softmax policies Te E AK parameterized by 0 E R&K exp(O(a)) The loss corresponding to the s.t. Ta(a)= En expl0(a')))
only attain an 92 (t) convergence rate for both bandits and MDPs (Mei et al., 2020, Theorem 9, 10). The convergence rate of GD-LS matches that of algorithms designed for this specific problem, including GD with a specific line-search that requires the knowledge of f (Lu et al., 2024), GD with specific increasing step-sizes (Liu et al., 2024), normalized GD (Mei et al., 2021), natural policy gradient (Kakade & Langford, 2002; Xiao, 2022) and mirror descent with log- sum-exp mirror map (Asad et al., 2024). From practical perspective, Lu et al. (2024, Figure 1) empirically demon- strate the linear convergence of GD-LS on tabular Markov decision processes, and hence, Cor. 6 substantiates their results theoretically.
bandit problem is given by: f(0) = r(a")) - (me, r), where a' := arg [k]] r(a) is the optimal arm. f(0) is non- negative, satisfies Assn. 2 with T-p = 0 and 1,_ = 72, Assn. 3 with V= = 24 and w = and Assn. 4 with < = 1 and
u00) - =000= (a").
Two-layer neural networks: We note that Assn. to and Assn. 4 with Ç are also satisfied when using the (i) exponential loss to train (ii) two-layer neural networks with a smoothed leaky-Rel.U non-linearity and (iii) assum- ing that the training data is linearly separable (Taheri & Thrampoulidis, 2023, Lemmas 3,5). In this setting, Theo- rem in Taheri & Thrampoulidis (2023) shows that normal- ized GD can result in linear convergence for the resulting non-convex objective. Since this problem also satisfies the required assumptions for Cor. 3, GD-LS also converges lin- early and unlike normalized GD, it does not require knowing problem-dependens constants.
Softmax policy gradient methods (Williams, 1992) optimize the above non-convex objective using gradient descent, and have been analyzed recently (Mei et al., 2020; Agarwal et al., 2021). We aim to use GS to optimize the objec- tive defined in Prop. 4 for which the GD update is given by: 0.+1- = 0e- - `). ( = 0, + m/e (e(TT, r). and the corresponding Arnijo condition given as (To..1: r) 2
(Te,r) r) + cm: Ve 1-2
In Prop. 7 in App. A, we show that, under additional as- sumptions, the softmax policy gradient objective for tabular Markov decision processes (MDPs) also satisfies the Assn. to with Lo- = 0 = 0 and < = 1. In this case, the exact setting corresponds to knowing the rewards and the tran- sition probabilitiies, and is the same setting under which classic RL algorithms such as value iteration or policy itera- tion are analyzed (Puterman, 2014).
Hence, these results demonstrate the universality of GD
5.2. Gradient domination with 2
We use the generalized linear model (GLM) with logistic link function as an example of an objective that satisfies the PL condition (which corresponds to Assn. 4 with Ç = 2).
We now characterize the convergence rate of GD-LS. Corollary 3. For an > assuming f0) satisfies Assn. to 3 with Lg = 0, w- 0 and Assn. 4 with Ç = 1, if p := minee()) (0))), then, GD-LS with Tmmax = oG, requires T2 max {1, 2A1 } (E+1) In (1(0))=") iterations to ensure [(OT) 6.
Lemma 2 (Lemma 9 in (Mei et al., 2021)). If (-) is the sigmoid function and (0) == a((x,,) assuming that for all i E [n]. ||=|| S 1, y/ = (00))) such that 110*| S D < oo and v(0) := minse[a] (=( (1 (1- (0)), then the GLM objective in Eq. (4) satisfies Assn. 4 with Ç 2 and u(0) 64 [u))] [min(v(0), (1²)
Similar to logistic regression, the PL constant μ depends e()). However, unlike logistic regression where ya {0, 1) and ||0*]] || can be infinite for separable data, for GLMs,
In order to better understand the implications of Cor. 3, we instantiate the above result for MAB and prove the following corollary in App. D.I.
Yi E (0, 1), |001] || is bounded and consequently, fu(²) > O. Hence, as long as ||0&|| < oo for all iterates & E [T]. #()) is bounded away from zero. However, we note that this does not preclude the case where the iterates initially diverge away from the solution, resulting in large ||0,]| and small (but non-zero) ((0)..
Corollary 4. For an MAB problem with K arms, rewards bounded in [0, 1), GD-LS with uniform initialization i.e Va, Tep (a) = 1/K, = T. Tmax = 0o requires T = 0 (K21 In (1/)) iterations to guarantee (mo,,r) r) 2 r(a")-c
Hence, for MAB, LD-LS converges at a linear rate. Under additional assumptions, by combining Prop. 7 and Cor. 3, we can prove a similar linear rate for tabular MDPs in the exact setting (see Cor. in App. D.1 for the formal result).
Recall that in Prop. 2, we have seen that the GLM objective satisfies Assn. I to 3 with non-zero Lo, L1, v, W. Further- more, since the targets y: = T(()") are assumed to be realizable in Lemma 2, f = O. Given these considerations, we prove the following theorem in App. D and characterize
The above result is in contrast to GD (1/L) which can
7

---

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
the convergence of GD-LS for such an objective.
stochastic variant of the Armijo line-search (referred to as SGD-SLS) proposed in Vaswani et al. (2019b).
x1 if f satisfies Assn. to 3 and Assn. with < = 2. f = and if u ;= min p(0))= > O, then, GD-LS with Thmax = 0C, requires T2 2 (06) + d In ] iterations to ensure thut f(0r)
Theorem 3. For fixed E (0, Ao
We focus on the convex, finite-sum setting, and consider minimizing f(0) = 1 Σx= f((0) where each fa is convex and satisfies Assn. to 3. Logistic regression and multi- class classification using the cross-entropy loss are examples of such an objective. For ease of exposition, we assume that each ft is (Lo, L1) non-uniform smooth, and note that it is straightforward to analyze the case where the fi 's have different smoothness constants.
The above result shows that GD-LS converges linearly, where the convergence rate depends on the ratio Xo/X1. On the other hand, for an L uniformly-smooth func- tion satisfying the PL condition, GD (1/L) requires O (+ In [(0o) iterations (Karimi al., 2016). Ignor- ing the constant first term which is independent of and assuming Åo x L, we can see that the result in Thm. 3 is better than the standard rate when Ao/A, is smaller than f(o)). It is important to note that since GD-LS can automatically (without any change in the algorithm) ex- ploit the uniform smoothness and obtain the standard re- sult well, the number of iterations required for GD-LS O do In
At iteration t E [T], SGD randomly samples function ft from the n functions in the finite-sum, computes its gradient and updates the parameters. Specifically,
0.+1 = 6 - 7h f(())),
where ((((O)) is the gradient of the loss function chosen at iteration t. Each stochastic gradient V ((t) is unbiased, implying that E2, [V = (()).. In order to estimate The SGD SLS uses the stochastic analog of the Armijo con- dition in Eq. (5). In particular, starting from Mmma SLS uses backtracking procedure and returns the largest step-size l) that satisfies: 1/c S 1mmax and,
X1c) } meaning that GD-LS converges at least as fast as GD (1 /L). Since the GLM objective is also uniformly smooth (Mei et al., 2021, Lemma 10), in Fig. 3, we empirically compare to GD (1/L). and verify the faster convergence of GS-LS.
is min {o { In
[(Om) )).
Ao
fc(O, T/e v.)) S (..) cm (0)))
(8)
Sydbede G.M
Note that the above stochastic Armijo condition only in- volves the sampled function and its gradient.
Figure Comparing
GD-LS
with = 1/2. 1mmax 10a
and GD (1/I) for GLM on
In order to analyze the convergence of SLS, we de- fine f. == min f.(0) as the minimum of function in the finite-sum and x²(0*) := E, (0')) - ff' as the measure of the stochasticity at the optimum (Loizou et al., 2021). In particular, if x² 0, then each ʃ; is minimized at 0* implying that (0*) = O. This special case is referred to as the interpolation setting (Vaswani et al., 2019 Ma et al., 2018; Schmidt & Roux, 2013) and is useful in practical ma- chine learning; for example, it is approximately satisfied by over wver-parameterized neural networks (Zhang et al., 2017) or non por-maramttric regression (Liang & Rakhlin, 2018: Belkin et al., 2019). Furthermore, logistic regression on linearly separable data is an example of smooth convex loss that satisfies the interpolation condition and is the main motiva- tion for the subsequent analysis.
synthetic dataset with a = 10
d= d2000, ||0]|=
Comparing Thm. 3 to the existing results for the GLM objec- tive, we note that Hazan et al. (2015, Lemma 3.1) show that the objective is locally quasi-convex, and use this property to derive a slower ( convergence rate for normalized GD with a decreasing step-size (Hazan et al., 2015, Theo- rem 4.1). On the other hand, Mei et al. (2021) propose a novel variant of normalized GD and prove that it converges linearly, with a better constant dependence compared to GD. However, their method requires the knowledge of μ. making it difficult to implement. On the other hand, GD-LS does not require the knowledge of any problem-dependent constants, and achieves similar or better theoretical results compared to these specialized methods
When minimizing uniformly smmooth convex functions in the interpolation setting, Vaswani et al. (2019a) proved that SGD-SLS converges to the optimum at an O(1/e) rate, matching GD and is faster than the standard O(1/e²) rate for SGD (Bottou et al., 2018). Motivated by this and the results in Sec. 4, we analyze SGD-SLS for logistic regres- sion which satisfies Assn. to 3. We first note the results in Vaswani et al. (2019a) (and subsequent papers analyzing the interpolation setting) do not directly apply to logistic regression. In particular, these results have a dependence
In the next section, we show the benefits of using line- search in the stochastic setting.
6. SGD with Stochastic Line-search
In this section, we analyze the convergence of stochastic gradient descent (SGD) (Robbins& & Monro, 1951) with a
8

---

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
on ||0|| which is infinite in the logistic regression exam- ple (Orabona, 2024). Consequently, we first prove that SGD- SGD-SLS can exploit the uniform smoothness in logistic regression and prove a O(1/e) rate in App. E.
for variance reduced methods such as SARAH (Nguyen et al., 2017) on general uniformly-smooth convex losses.
Given the above intuition, a natural question is whether SGD-SLS can attain faster rates if the algorithm can ensure that it samples points that have a relatively large function values. We formalize this in the following theorem proved in App. E.
Theorem 4. For logistic regression on linearly separable data with margin " if. for all i, ||=||| S 1, for a fixed re- [In (+)))) iterations to ensure that
e E (0, 1), SGD-SLS with 1/max = ? and
quires T = E7
Theorem 6. For logistic regression on linearly separable data with margin 7, if. for all i, | S 1, for a fixed
5e ( f f(0)) - 2
E =(0, min {3,0"} where C' == G18 SGD SLL
Next, we exploit the non-uniform smoothness of logis- tic regression and analyze the convergence of SGD- SLS. Note that since SLS involves an Armijo line-search for one (randomly chosen) function in each iteration, we can follow the same argument in Lemma and show that the siep-size in each iteration is lower-bounded i.e. T) 2 min Mmaxx oo +Xi [e( J. Given this result, we prove the following theorem in App. E.
with T/max = 1 and c = 3/2 and guaranteeing that for all t [T]. Pr [f((0)) 2 5] requires T O (++ [In (2)]²)
3x 2 iterations to ensure that [[]((T)] -
Hence, if the algorithm can ensure that the sampled function ft at iteration has loss greater than e/2, then, SGD-S1. can indeed achieve a faster ((In(1/c)) convergence rate which is independent of n. Skipping updates when the sam- pled point has small loss, or using projection step to ensure that no loss becomes smaller than c/2 are two poten- tial ways to ensure that Pr [f(( 2 & = 1. Implementing such approaches in a computationally efficient manner and analyzing the resulting algorithm is challenging, and we leave this interesting direction to future work. Finally, we note that by combining the proof techniques in App. C.I and App. E, the above convergence guarantees also hold for the stochastic Polyak step-size (Loizou et al., 2021).
Theorem 5. For logistic regression on linearly separable data with margin %, if. for all i, || S 1. for a fixed (0, (0. where C" = (1), SGD-SGDDD SSLS with 7mmax = _
e EE
and c = Th requires T = 0 (* In (*)) iterations to ensure that [m f(0,)] < 2
Se
Note that the above On (In(n/e))²) convergence rate is slower than that of GD-LS. However, since SGD-SLS has an (() cost per iteration (as compared to the ((n) cost for GD-LS), both algorithms have the same gradient complex- ity. In order to intuitively understand why it is difficult to prove faster (independent of n) rate for SGD-SLS, first note that the stochastic setting does not allow using arbi- trarily large values of 7maax Second, note that individual losses f; in the finite sum can become much smaller than f- Specifically, consider iteration of SGD-SLS and consider a point such that f1( < 8 <<< é where é is the desired sub- optimality. If this point is sampled at iteration f, the corre- sponding size of the update is [l0+2 - 0e]l = 5 7max = 6/c which can be small. On the other hand, for i such that f(())) 2 5, the size of the update is O1)) Hence, if at iteration f, there are
7. Conclusion
We analyzed GD-LS for a class of functions satisfying non- uniform smoothness. For a range of practical convex and non-convex functions, we proved that Armijo-LS can enable GD adapt the objective's properties and result in faster convergence. In particular, we showed that, for specific problems in machine learning, CD-LS can (i) either match or provably improve upon the sublinear rate of GD (1 LL), (ii) do so without relying on the knowledge of problem- dependent constants and (iii) match the fast convergence of algorithms tailored for these problems. Our results thus show the universal effectiveness of GD-LS.
"small" losses and the algorithm samples a point uniformly at random, it has an O(1) up- date with probability 1 1/n. Hence, in expectation, the rate depends on n in the worst-case.
We believe that analyzing GD-LS for a broader class of non-convex functions, and characterizing the advantage of using Armijo-L.S for other algorithms (such as Nesterov ac- celerated gradient) are important future directions. We also plan to investigate whether other adaptive step-size schemes such as AdaGrad (Duchi et al., 2011) or Adam (Kingma & Ba, 2014) can also provably adapt the non-uniform smoothness and result in faster convergence rates.
However, note that the same SGD-SLS algorithm can achieve the rates in Thm. and and hence, the algorithm has an O (min (n. 1/+} (In(n/c))²) convergence rate. We conjecture that by formalizing the above intuition, we can prove a matching lower-bound and leave this to future work. Note that the resulting gradient complexity for SGD-SLS is smaller than that of GD-LS. Interestingly, this is also smaller than the O (nn + 1/d) In(1/e)) gradient complexity
9

---

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
Impact Statement
Duchi, J., Hazan, E., and Singer, Y. Adaptive subgradient
methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011. (cited on 9)
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Fox, C. and Schmidt, M. Glocal smoothness: Line search can really help! OPT 2024: Optimization for Machine Learning. (cited 1, 4)
Acknowledgments
We thank Damien Scieur, Mark Schmidt, Curtis Fox, Michael Lu and Siyi Meng for helpful discussions and feedback, and Anh Dang for help with the initial experi- ments. This research was partially supported by the Natu- ral Sciences and Engineering Research Council of Canada (NSERC) Discovery Grant RGPIN-2022-04816
Freund, R. M., Grigas, P., and Mazumder, R. Condition number analysis of logistic regression, and its implica- tions for standard first-order solution methods. arXiv preprint 1rXiv:1810.08727, 2018. (cited on 5)
Fridovich-Keil S. and Recht, B. Choosing the step size: intuitive line search algorithms with efficient convergence. In 11th annual workshop optimization for machine learning, Vancouver, BC, Canada, pp. 1-21, 2019. (cited on 4)
References
Agarwal, A., Kakade, S. M., Lee, J. D., and Mahajan, G. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1-766 2021. (cited on 7)
Galli, L., Rauhut, H., and Schmidt, M. Don't so monotone: relaxing stochastic line search in over- parameterized models. Advances in Neural Information Processing Systems, 36, 2024. (cited on 2)
Armijo, L. Minimization of functions having Lipschitz. continuous first partial derivatives. Pacific Journal of mathematics, 1966. (cited on 4)
Gorbunov, E., Tupitsa, N., Choudhury, S., Aliev, A.. Richtárik, P., Horváth, S., and Takáč, M. Methods for convex (1_0, [1) -mmooth optimization: Clipping, acceler- ation, and adaptivity. arXiv preprint arXiv:2409.1498) 2024. (cited on 2, 3, 6)
Asad, R., Babanezhad, R., Laradji, I., Roux, N. L., and Vaswani, S. Fast convergence of softmax policy mirror ascent. arXiv preprint arXiv:2411.12042 2024. (cited on 7)
Hazan, E., Levy, K., and Shalev-Shwartz, S. Beyond convex- ity: Stochastic quasi-convex optimization. Advances in neural information processing systems, 28, 2015. (cited on 2, 5, 8)
Axiotis, K. and Sviridenko, M. Gradient descent converges linearly for logistic regression on separable data. In In- ternational Conference on Machine Learning, pp. 1302- 1319. PMLR, 2023. (cited on 2, 5, 21)
Hübler, F., Yang, J., Li, X., and He, N. Parameter-agnostic optimization under relaxed smoothness. In International Conference on Artificial Intelligence and Statistics, pp. 4861-4869. PMLR, 2024. (cited on 2)
Belkin, M., Rakhlin, A., and Tsybakov, A. B. Does data in- terpolation contradict statistical optimality? In AISAATS, 2019. (cited on 2, 8)
Bottou, L.., Curtis, F. E., and Nocedal, J. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223-311 311, 2018. (cited on 8)
Kakade, S. and Langford, Approximately optimal ap- proximate reinforcement learning. In Proceedings of the Nineteenth International Conference on Machine Learn- ing. pp. 267-274, 2002. (cited on 2,
Cauchy, A. et al. Méthode générale pour la résolution des systemes d' é'quttion simultanées. Comp. Rend. Sci. Paris, 25(1847)5336-55 538, 1847. (cited on 1)
Karimi, H., Nutini, J., and Schmidt, M. Linear conver- gence of gradient and proximal-gradient methods under the polyak- -ojasiewicz condition. In Machine Learn- ing and Knowledge Discovery in Databases: European Conference, ECML PKDD 2016, Riva del Garda, Italy, September 19-23, 2016, Proceedings, Part I 16. pp. 795- 811. Springer, 2016. (cited on 2, 5, 8)
Chang, C.-C. and Lin, C.-J. Libsvm: library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3):1-27, 2011. 1. (cited on 5)
Chen, Z., Zhou, Y., Liang, Y., and Lu, Z. Generalized- smooth nonconvex optimization is as efficient as smooth nonconvex optimization. In International Conference on Machine Learning, pp. 5396-5427. PMLR, 2023, (cited on 2, 3)
Kingma, D. P. and Ba, J. Adam: A method for stochastic op- timization. arXiv preprint arXiv:1412.6900 2014. (cited on 9)
10

---

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
Koloskova, A., Hendrikx, H., and Stich, S. U. Revisiting gradient clipping: Stochastic bias and tight convergence guarantees. In International Conference Machine Learning, Pp. 17343-17363 PMLR, 2023. (cited on 2)
Nesterov, Y. et al. Lectures on convex optimization, volume 137. Springer, 2018. (cited on 5)
Nguyen, M., Liu, J., Scheinberg, K., and Takáč, M. Sarah: A novel method for machine learning problems using stochastic recursive gradient. In International conference on machine learning, pp. 2613-2621. PMLR, 2017. (cited on 9)
Li, H., Qian, J., Tian, Y., Rakhlin, A., and Jadbabaie, A. Convex and non-convex optimization under generalized smoothness. Advances in Neural Information Processing Systems, 012440288440277 2023. (cited on 2, 3. 13)
Nocedal, and Wright, S. Numerical optimization. Springer Science & Business Media, 2006. (cited 1, 4, 18)
Liang, T. and Rakhlin, A. Just interpolate: Kernel" ridgeless" regression can generalize. arXiv preprint arXiv:1888.0033 00387, 2018. (cited on 8)
Orabona.
URL https:// à /2//m//eerrreee.com//2//////////
F., 2024.
parameterfree.com
Liu, J., Li, W., and Wei, K. Elementary analysis of pol- icy gradient methods. arXiv preprint arXiv:240.00337, 2024. (cited on
(cited on 5,
9)
Polyak, B. T. Introduction to optimization. 1987. (cited on 2, 6, 25)
Loizou, N., Vaswani, S., Laradji, I. H., and Lacoste-Julien, S. Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence. In International Conference on Artificial Intelligence and Statistics, pp. 1306-1314. PMLR, 2021. (cited on 8, 9)
Puterman, M. L. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014. (cited on
Robbins, H. and Monro, S. A stochastic approximation method. The annals of mathematical statistics, pp. 400- 407, 1951. (cited on 8)
Lu, M., Aghaei, M., Raj, A., and Vaswani, S. Towards prin- cipled, practical policy gradient for bandits and tabular mdps. arXiv preprint 2xXiv22455.33136 2024. (cited on 7)
Scheinberg, K., Goldfarb, D., and Bai, X. Fast first-order methods for composite convex optimization with back- tracking. Found. Comput. Math., 14(3):389-417, 2014. (cited on 1, 4)
Lu, and Mei, S. Accelerated first-order methods for convex optimization with locally lipschitz continuous gradient. SIAM J. Optim., 33)))2275--33100 2023. (cited on 1, 4)
Schmidt, M. and Roux, N. L.. Fast convergence of stochastic gradient descent under a strong growth condition. arXiv preprint arXiv: 6370, 2013. (cited on 2, 8)
Ma, S., Bassily, R., and Belkin, M. The power of interpola- tion: Understanding the effectiveness of SGD in modern over pverpparametrized learning. In Proceedings of the 35th International Conference on Machine Learning, ICML, 2018. (cited on 2, 8)
Taheri, H. and Thrampoulidis, C. Fast convergence in learn- ing two-layer neural networks with separable data. In Proceedings of the AAAI Conference on Artificial Intel- ligence, volume 37, pp. 9944 9952, 2023. (cited on 3, 7)
Mei, J., Xiao, C., Szepesvari, C., and Schuurmans, D. On the global convergence rates of softmax policy gradient methods. In International conference on machine learn- ing, pp. 6820-6829. PMLR, 2020. (cited 2. 17, 29)
Takezawa, Y., Bao, H., Sato, R., Niwa, K., and Yamada, M. Polyak meets parameter-free clipped gradient descent. arXiv e-prints, pp. arXiv-2405, 2024. (cited on 2)
Mei, J., Gao, Y., Dai, B., Szepesvari, C., and Schuurmans, D. Leveraging non-uniformity in first-order non-convex optimization. In International Conference on Machine Learning, pp. 7555-7564 PMLR, 2021. (cited on 5, 6, 8, 17)
Vankov, D., Rodomanov, A., Nedich, A., Sankar, L.,, and
Stich, S. U. Optimizing (I 0, ())-mooh functions by gradient methods. arXiv preprint arXiv:2410.10800. 2024. (cited on 3,
Vaswani, S., Bach, F., and Schmidt, M. Fast and faster convergence of sgd for over- par-parrmeterizee models and an accelerated perceptron. In The 22nd international conference on artificial intelligence and statistics, pp. 1195-1204, PMLR, 2019a. (cited on 8)
Mishkin, A., Khaled, A., Wang, Y., Defazio, A., and Gower, R. M. Directional smoothness and gradient methods: Con- vergence and adaptivity. CoRR, 0bs/2403.040011. 2024. (cited on 1, 4)

---

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
Vaswani, S., Mishkin, A., Laradji, I., Schmidt, M., Gidel, G., and Lacoste-Julien, S. Painless stochastic gradient: In- terpolation, line-search, and convergence rates. Advances in neural information processing systems, -7772---745, 2019b. (cited on 2, 8)
Ward, R. and Kolda, T. Convergence of alternating gradient descent for matrix factorization. Advances in Neural Information Processing Systems, (cited on 6)
2023.
Williams, J. Simple statistical gradient-following algo- rithms for connectionist reinforcement learning. Machine learning, 8(3-4):229-255 256, 1992. (cited on 7)
Wilson, A. C.,, Mackey, L., and Wibisono, A. Accelerating rescaled gradient descent: Fast optimization of smooth functions. Advances in Neural Information Processing Systems, 32, 2019. (cited on 5)
Wu, J., Bartlett, P. L.. Telgarsky, M., and Yu, Large step- size gradient descent for logistic loss: non-monotyniccty of the loss improves optimization efficiency. arXiv preprint arXiv:2402. 15926, 2024. (cited on 3, 6)
Xiao, L. On the convergence rates of policy gradient meth- ods. Journal of Machine Learning Research, 23(282): 1-36, 2022. (cited on 7)
Zhang, B., Jin, J., Fang, C., and Wang, L. Improved anal- ysis of clipping algorithms for non-convex optimization. Advances in Neural Information Processing Systems, 33: 15511-15521, 2020. (cited on 3, 14)
Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, O. Understanding deep learning requires rethinking general- ization. In ICLR, 2017. (cited on 2,
Zhang, J., He, T., Sra, S., and Jadbabaie, A. Why gradient clipping accelerates training: A theoretical justification for adaptivity. arXiv preprint arXiv: / 1905. 1881, 2019. (cited on 1, 2, 13, 17)
Zhang, R., Wu, J., Lin, L., and Bartlett, P. L. Minimax optimal convergence of gradient descent in logistic re- gression via large and adaptive stepsizes. arXiv preprint arXiv:2504.0 04105, 2025, (cited on 6)
12

---

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
Supplementary Material
Organization of the Appendix
A Proofs for Sec. 2
B Proofs for Sec. 3
C Proofs for Sec. 4
D Proofs for Sec. 5
E Proofs for Sec. 6
A. Proofs for Sec. 2
Assumption 5. If f is twice differentiable and (Le, Lg) non -ot--noon--oonon uniform smooth as defined in Zhang et al. (2019). then, for constants Tee Tog > 0,
|[ s L. + Lo (VVI(
Proposition 3. For a non-negative, twice-differentiable function J. if f is (Tes Tug) non-uniform smooth according to Zhang et al. (2019) i.e.
|| f(0)]) & La + Lg [V)())
then, is satisfies Assn. 2 with Lo L. + Lg 2L and L1 Lg (8Lg 2LL.) and Assn. 3 with =Lg + 2L, and w = 22
Proof. Using Li al. (2023, Lemma 3.5), we know that (Les Lg) non-uniform smoothness also implies that,
[V)(()) < 2 + 2hy ||V (f(0) f*) 2 + 2 [[V]())]] f(0)
(Since f is non-negative)
= |V)(())| < 4L, f(0) + /2Lc (0)
(By completing the square w.r. [[V)())))
Consider cases depending whether f(0) is larger than 1.
Case 1: If (0) < 1 V 1. The above inequality can be simplified as: ||V](0) < 4L, f(0) + v2L..
Case 2: f(0) >1 f < f(0). The above inequality can simplified as: |[V[(0)] < 44, f(0) + V2L. f(0).
Combining both cases, we have that,
[V(()) < (SL, + 22lx) 1(0) + 2L
(10)
Hence, Assn. 3 is satisfied with 8Lg + 22Tee and V2T.. Using this result in the definition of non-uniform smoothness in Assn. 5,
[ s Le + b.g [(ST.g + 2T ʃ(0) + / 2L = The + L, 22 + Lo (SL.g + 2 S(0)
(11)
Hence, Assn. (b) is satisfied with T.p Toe + Tog 2TT, and In Tr (8T.g + v2T.e).
13

---

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
Using Zhang al. (2020, Lemma A.3), if satisfies Assn. then, for all 2, such that || y1 S Siy where 0 is constant,
f()) - (V -x) ALe + Lg [f(())]
|ly -y-xllk x
2
where = 1+ e-1 and B = et-1 Combining the above inequality with Eq. (10),
4
ALe + B Ng (8T. + v2T.o) f(x + v21cel
f(0) f(x) + (Vf(z), -x) 2)
11 - xr2
2
A + B Lg v2 A
+ B Lg (8Lg + v2Lc) f(x)
= f(x) + (Vf(2), 2)
11 10-00 ==12
2
A ALLo + b1g 2L.) + B Ln (8Lg + v2Lo) f(x)
$ [ (V))),, - +)+
11y or 1
(Since B S A)
Hence, Assn. 2 (a) is satisfied with Lo Lo+ + lig 22T and In = bg (8l.g + V2T.).
In order to prove that commonly used functions in machine learning satisfy the assumptions Sec. 2, we will require the following lemma.
Lemma For a finite-sum objective, f(0) - ( if. for all i, So is non-negative and satisfies Assn. 5 with constants Le and Lgg then, satiifies Assn. 3 with constants Lo Le + Li /2L L1 Lug (8Lg + /2Lc). v= 8Lg + 22Le and w = /2Lc.
Proof. If fi is non-negative for all i, then, f is non non-negative, thus satisfying Assn. We will first prove that fr is non-negative and satisfies Assn. 2 and 3, then f also satisfies these assumptions with the same constants.
If fa satisfies Assn. (a), then,
(() S f(x)) (VA(s),y 2)) ALu + B BL, fi(a)
||y xr112
2
Summing the LHS and RHS for = and dividing by n completes the proof that f satisfies Assn. (a). If fi satisfies Assn. (b), then,
V f()) =
1 Σ (1)
S Σ V f(00 s Lo
L n Σ f(()) = Lu + (()
Hence, f satisfies Assn. 2 with the same constants Lo and L, ʃ; satisfies Assn. 3, then,
L n
Σ IVAOI S
Hence, satisfies Assn. 3 with the same constants v and From Prop. 3, if fo satisfies Assn. 5 with constants Le, Ly. then, Ji and consequently ʃ satisfies Assn. and 3 with constants Lo = Lo + Lg V2l., Li Lg (8Lg + v /2 8L, + 22L, and 22Le
14

---

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
A.1. Examples satisfying Assn. 1 to 3
We will use the above lemma prove that linear logistic regression, exponential loss with linear model, linear multi-class classification using the cross-entrops loss, generalized linear models with logistic link function and the softmax policy gradient objective for multi- bandits and tabular MDPs satisfy Assn. 1 to 3.
Proposition 1. Consider points where Ti E R2 are the features and yi E {-1,1) are the corresponding labels. Logistic regression with the objective
1 ((0)
In(1 + Σ
(3)
==1
satisfies Assn. 2 with La- 0, L1- = m([)) | and Assn. 3 with 8 maxx ||0/|| = O.
Proof. Clearly, f(( 2 0 for all 0. Calculating the gradient and hessian for fi(0) == In(1 + exp( ( yo (1 ()), exp(- Yi (zi, f]
exp(ppppp y/ (Ia 0)) f(((0) 1 + exp(- --1 (z,, 0)) 1/i Tz
1 Vi(((0) + exp( - ()), 1 exp( - y1 (zi 07) vi 24 x!
Bounding the Hessian,
exp( y/ (1,, f))
exp(- Vi (Ii; 0))
(i(( = 1 exp( y1 (I f))
v. va
(For all x, 1 and y? = 1)
1+ exp( y1 (z,, 8))
= V 110)| exp(- y/ ( 0))
exp( Vi (5;; 0)) 11-:112=1 -|aail [|)|l(0)]|
Hence, for all i, f. satisfies Assn. 5 with Le satisfies Assn. with Lu = 0 and L1 = 8 max, | |2 and Assn. 3 with v = 8 max; | and w = 0.
and Lg max; ||=:||-- Using Lemma 3, we conclude that f(0)
Proposition 2. Consider n points where Ia E Rd are the features and E [0, 1] are the corresponding labels. If (0) = o(xx,0)) = 1+exp(- (1),0)) the GLM objective,
f(0) = 2n
(0) - -1))²
(4)
satisfies Assn. 2 with Lo = 16 max |<: L1 = 9 max ||0:||2 and Assn. 3 with 9 max; ||>i|| w max; ||=:||.
Proof. Clearly, f0) 2 0 and hence f(0) 2 0 for all 0. f(0 is a finite-sum objective. Calculating the gradient and hessian for (0) = 2 (0) y:)²
exp(- (2,, 8))
ff(00) = (T)( - v.) 1 -+eepp-((2 (2,, 0)) 1 1 exp( - (a.,, 0)) Fz
fa000) = [1 (0) (0) [1 (0) (0) yi x. _ + [T: [1 [1)};(0)} x4 x.
= f(0)|| = || 1 (0) (0) (1-
- vil |r + b. (0) [1- (0)) | (0)] [T(
||>||| (Triangle Inequality)
=1VV/.001
1
+ 1 < ||ح|| [()]
+ 1|
16
Hence, for all i, f(()) satisfies Assn. 5 with L. 1 max || and Lg maxic ||x]]]
Using Lemma 3, we conclude that f(0) satisfies Assn. 2 with Lo
8+y2 16v2 maxiej 1|2:112 and L1
16/2+1 maxiglo] || and Assn. with 16v2+1 max, || and Is max, ||v||] v8
v8
15

---

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
Proposition 5. Consider n points where 24 Rd are the features and yı {0, 13 are the corresponding one-hot label vectors for C classes. Multi-class classification with the cross-entropy objective is given as:
f(0)
1 n2 m=1
Σ
(=T) where Vm E [n], x E Ac s.t. Vi E [C]. (1) = Ei exp( (Tim 0k))
exp ( 0())
where 0g E Rd for i [C] and 0 = [01, 82 .......,8.................. 0c]. 0c]. Multi-class logistic regression satisfies Assn. 2 with Lo 0 and ||>|| and Assn. 3 with 16 max; ||>:||| and O.
L1 32 maxme[n]
Proof. Let us consider a single input-output pair (z, and calculate the gradient for single function in the finite-sum. Define E(f) = (L)))[m)) where y is C-dimensional one-hot vector, I E Id and To E Ac s.t. TT(i)
exp((ar,;))
Σ exp((a,6x))
Clearly, {(0) 2 0. Calculating its gradient and Hessian,
aE(0)
[To (3) yt) x.
08;
The Hessian can be written as a Kronecker product of a C x C matrix which corresponds to the Jacobian of the softmax function, and a x d rank-one matrix formed using the features. Specifically,
V2((0) = H. xz where, H == diag(To) -o x
T
CXC Axd
|() S | ||
Since H. is square symmetric PSD matrix, ||]| Amax [H). By the Gershgorin circle theorem, Amax [H] S
max; Ee |H Calculating the row sums, we conclude that || ||| S Amax [H] S 2 max; To(i) (1 To(i)). Hence,
\ || 2 || max (1) (1 TT())) s 2 ||=||| max; ( (1 (i) |V((0)]
Eim (Te(i)) - yal
Let = arg max (1) (1 - no (1)). Using that Ei=1 TT (i) Val Z (molj") - wو- and ||0:12 S ||
Te (j (1 - TT (j')) [V(())]
< 2 ||0||
Ta - y
(Since Vy- E {0, 13 and To(j*) E [0, 1D) Hence, for single (ar, v) pair, we can conclude that, {(0) satisfies Assn. 5 with Lg 2 || Hence, Si satisfies Assn. 5 with L. 0 and Lg 2 max ||<:||||-
= ||
< 2 |=||| [[))ll
Using Lemma 3, we can conclude that f0) satisfies Assn. 2 with Lo and L1 32 maxie[n] | | and Assn. 3 with 16 max; ||:||| and 0.
Proposition 6. Consider points where 2; E Rdd are the features and yi {0, 1) are the corresponding labels. Binary classification with exponential loss with the objective
1 n
f(0) == 71
Σ
exp(-y:
ys (x,
satisfies Assn. 2 with La- and L1 max in] ||=:112 and Assn. 3 with max; || and w
Proof. Clearly, f((0) 2 and hence f()) > 0 for all 0. Calculating the gradient and hessian for f((0) == exp( (y, (2(,0))) 0)).
Vf(( exp( 34 (x. 8) )y; D; v fa(0) = exp(- - (x,, 0)) vi xs .o. exp((-9llxa 01) xe x.
( = 1)
V (()) < ||>ح|| V (0)
Hence, for all i, f: satisfies Assn. 5 with L. 0 and Lg max; ||aa|]- Using Lemma 3, conclude that f(0)
satisfies Assn. with Lo and In = 8 max; | l and Assn. 3 with v max; || and w
16

---

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
Proposition 4. Given an MAB problem with K arms and known deterministic rewards [0, 1|k, consider the class of exp(0(a))
softmax policies Tg E A parameterized by 8 E IR K s.t. To(a) = E.. exp(O(a)))) The loss corresponding to the bandit problem is given by: f(0) r(a") (TT, r), where a² arg [ r(a) is the optimal arm. f(8) is non-negative, satisfies Assn. 2 with Lo- 0 and L1 72, Assn. 3 with v = 24 and w = 0 and Assn. 4 with Ç and μ(0) Te(a").
Proof. From Mei et al. (2021, Lemma 2), we know that
(2 (To, 3 (To, r)|l 3 [
Hence, the loss for the bandit problem satisfies Assn. with Le = 0 and Ly = 3. Using Lemma 3 with n = 1, we can conclude the the loss for the bandit problem satisfies Assn. 2 with Lu = 0 and L1 = 72 and Assn. 3 with v = 24 and w 0. From Mei et al. (2020, Lemma 3), we know that,
|V( = [[Vo(Ta, 2 TO no(a") (r(a") - (T,, r)] = No =o(aa)))))))))))))")))) ((0)
Hence, the loss for the bandit problem satisfies Assn. with μ(0) TT(a")
Proposition 7. Consider an infinite- horizon discounted Markov decision process (MDP) defined by (S,A, p. r),, where S and A represent the states and actions, P : S A As the transition probability function, S + [0. 1] the reward function, p E As is the initial state distribution, and ? [0,1) represents the discount factor. Vf == ('t, ax)) so = s] where 8t p(-1st-1,, at-1), and a, (.(ss) for t 2 1 is the expected discounted cumulative reward for policy π starting at state s. we define (p) =
Consider a policy To parameterized by E RISIX|A| s.t. To(s,.) E Ax for all E S and no(s, a) x exp(O(s, a)). The loss corresponding to the tabular MDP problem is given by:
f(0) V* (p) V=
4. 1-min, مb. ((-))) 1 S, Assn. with VS and w = and Assn. 4 with μ(0) = min, mata' (x)[a) where a" is the action that a min.es p(s)
where nt is the optimal policy. ((0) satisfies Assn. 2 with Lo and L1 3
1-7
== 3 1-(min, ab. (1 (11-))
I-7
deterministic optimal policy x" selects in state s.
Proof. Assuming that the starting state distribution has full support, i.e. p(s) > from Mei et al. (2021, Lemma 6), we know that,
4. mingg p(e)
1 - -(1 (1--))
|(000)] < 3
Vs. (|V1())()0
1 1-7
3 4. 1(min, ptoy (1-91) 1-y
Hence, the loss for the tabular MDP problem satisfies Assn. 5 with Le 0 and L,
V5.
Using Lemma with n = 1, we can conclude the the loss for the tabular MDP problem satisfies Assn. 2 with Lo = 0 and min, o.. (1 (1-7)) S and Assn. 3 with 3 4. (min, pb. (1-1)) Vs and w = 0. From Mei et al. 1-7
L1 8 3
1-y
(2020, Lemma 8), we know that
min, (s)ls) (())
|V](
VS mingesp(o)
Hence, the loss for the tabular MDP problem satisfies Assn. 4 with m(0)
min, ma(a (a]]a)
vs min.es p(e)
Proposition 8. Consider the logistic regression objective in Eq. (3) with n = 2 and d Consider the two points to be such that y1 21 = 2 and y/2 I2 = -2. For this problem, the non con-unfformness assumption in Zhang et al. (2019): 22 (0)] & To + La [() cannot hold for Lo = O and any Tn +
17

---

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
Proof. Using the proof of Prop. I to calculate the gradient and hessian, we get that (0) and V f2 (0) 0 which implies Vf(0) 0. Similarly, for Hessian, get V (1() and 4 (0()) 1 which implies 42 Since
V f(0) 0 and V f(0) of O, the assumption cannot hold with Lo of 0 and any L1 + O.
B. Proofs for Sec. 3
Lemma If f satisfies Assn. 1 to 3, at iteration I, GD-LS returns a step-size tpe 2 min { (Maxxs tothi 1(02) (,(+1)
}. where
Ap 3 Lo+Liw and A1 33 (1-c)
(I-o)
Proof. Case 1: L1 0, Assn. equivalent to the standard Lg-uniform smoothness condition, this case, we
can follow the standard analysis of GD-LS (Nocedal & Wright, 2006) and conclude that 7/: 2 min (mmax Lo
2(1-o)
(1-c) }. min Tmnxx: 3oo S.
In this special case, λg = T-c and X 0, meaning that 7/ 2 min { (mmaxx Ao+ F(0.)
This concludes the proof.
Case 2: If Ta # 0 and since s(0) is non-negative, define the log-loss as follows.
g == In(Lo L1 f(0))
Using Assn. 2, (²)(0) > [Lo + L, [(0)) La. Using this result, we bound the Hessian of g(0).
L1 V f(0)
Vg(()=
Le + L1 f(0)
L1 2 1(0)
LI (2)
V²)(0) Lo + f(0)
(Since the second term is PSD)
(Lo L, f()))²
Lo + L1 f(0)
V2 (0) < la
Hence, g(0) is L1 -lobballly smooth. Using this result, we know that for all u, u,
s(u) s ((v) + (Vg(o), - - u) + L
1/u u112
2
Using this result for 0,+1 and 0..
Ta
s(f++1) S ((,)) + (Vg(0.), 0:41 -1)) +
|1 0ell2
2
L1 m 2
= = Tu (0.) vg(O:))
| |
2
(Using the update that 0.41 = -, 17 v(()))
= =(())) - Tu (F(()). L vS(,,)
L m
+
(V (Since Vg(() Lo+Li ((8)
(.V1(0)
Lo L1 f(0))
2
f(.)))
+ L n
g(0, 7. (.()))) S ((+)) - T/ Lo + L1 ((0,)
\V
(12)
2
Next, we will compare the above inequality with what we obtain from the Armijo line-search.
f(0. n f(.)) < f(0)) en [V
Lo + L, f(0 ((.)) - Lo + L, f(0)) - cn: L, II
Note that Lo L1 f(0.) en L1 | [(.) > 0. Since f. Lo, Li 2 0, en
4 /
> 0. Taking log on both
T - ((,)
18

---

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
sides,
In (Lo + 11 1 (V(()))) & In Lo + L1 f(0:) cm L1 IV
(Since In is monotonically increasing)
= 906 vf((.)) In
Lo + L1 f((:) tu TT V f()))))
(By definition of g)
(1-0)) cm Lo 11 f(0.)
L1 11 (
=hn
(Lo - (1f(00))
(13)
11 [V
= =((r) + In 1 11-ch
-1- Lo + L, s(0:)
(By definition of g)
S (((() + (1 (100 Lo + L1 f(0t)
Li || ((0.)
-1
(For all > O, In(x) S x - 1)
11 |
g(0++1) S g00)) etlt Lo + L1 ((,)) :h)(())
(14)
Hence, assuming exact back-tracking, if nee is a step-size that satisfies Eq. (5), then Eq. (14) will also be satisfied. If the Armijo condition is satisfied for an s.t. (1te) S hm()). then,
L1 I (0.) (g( ni Lo + L1 f(0,)
L1 [V.)0))
L1 n
g(0,) - CT)
[V
Lo L1 f(0))
2
2 c)
11t Lo L, ((,))
If the Armijo condition is satisfied for an ne s.t. hn(T)) I hz())) it implies that ne S
2(1-c) 1o+
However, we show that the resulting step-size cannot be too small. In particular, we will prove that the Armijo condition is satisfied for
-(1-c) 6(Lo + Lww) + 1T, ())))
To show this, we use Assn. 2. In order use this inequality, we have to ensure that ||0:41 0:11 Thh IV s + Since based on Assn. 3, [f()il I v f(,) + w, it suffices ensure that q 2 ni L1 (1/ f(0)) + w).
Using Assn. 2, we get that:
f(0++1) S f(0,) - The [V.)()))) + ALo + BL, f(0.)
1): 2 |V
The Armijo condition is definitely satisfied if:
f(0.) m [VV)())))1 (1 - Lo +
[--1 9
Li f(0.)
m
|V < S(.)) en 1V
Hence, the Armijo condition is satisfies for all m s.t.
211 c)
1 1
1 1 e9 - اس-ع - 9
Lo +
c9_1 9
Li f(0.)
Since,
2 (1
2(1-6
5
1 e9 19-1 Lo
1--1
L1 f(t)) + [0-1]
L1 (vf(0.) +w)
11
eh-1
Lo +
5--1
L f(.))
9
19

---

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
the Armijo condition will be satisfied for the smaller step-size.
Moreover, for
2(1 c)
Tj:'= :
1 1 [1+.9- 69 - _ Lo + 19-1
L1 f(0))
(1==))
Li (uf(0:) + w)
we need to ensure that 2 mp' Li(e f(0z) + w). Hence, we want to find q s.t.
2(1 - c) (1 f(()) + +w)
92
(vf(0,) + w) (1 _ Lo 1-=1 L1 f(0() (
Since (1+ el ) Lo + (11ا
L1 f(0,) > 0, it suffices to choose g s.t.
2(1 c) (v/ f(0)) + +w)
2(1 c)
q
c--1 L (v f (0.) + w) 2
Finally, since 1 x S exp(x) for all r, it suffices to choose g s.t.
q 2 c)
Hence, 9 = 2 satisfies the required conditions. Therefore, for g we have,
2(1 c)
e2 Lo + [--) 2 Li f(0,) + (= Li (uf(0r) + +w)
Therefore for any 7/ S np' we have 922 Mh (ve( + w). Since x² S 6 and 1 + e² - S 6 we can set
2(1
2(1 c)
Th 6 Lo 6 L, f(0,) + Li (v](0)) 6 (Lo + Lww) + 6 L 1)
Based on above argument, can conclude that the nh the step-size returned by the Armijo line-search is lower-bounded as
2(1 c)
1) 2 6 L!w) + 6 (
Moreover if
2(1 -
7max (Lo L(w) 6 L1 (v f(0)'
then Mmax satisfies both Armijo condition and ha (Tmaa) S h2 (Nmaa)) in which case, the line-search would terminate immediately and return Mjnax- Therefore
2(1 -1-c)
Th min (7maxx 6Lo + L(w) + 6 L1 +1)s(0))
Theorem 1. For fixed 0, if satisfies Assn. I to and for constant R 0. /V [f(0.)--PP
for all
iterations & E [T], then, GD-L5 with Tjmax = requires
max 12 (1= In -(00)-8"
if 2 x1
(Case (1))
T
2 + (2,,, 13 (f- +1)
1(00)-5"
otherwise (Case (2))
iterations to ensure that f(r) - f" S
20

---

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
Proof. Using the Armijo line-search condition in Eq. (5), and combining it with the lower-bound in Lemma
1
f(0++1) - f(0.) Xo A f(0,) IV)())))
(15)
We now follow a proof similar to that of Axiotis & Sviridenko (2023, Theorem 5.2) and derive a linear rate of convergence. From the theorem assumption, know that V f(v)(()) - Combining these relations,
1
(f(0,) - f
[(0++1) S f(0.) Ay X 5(0))
R
Let us define t = max(l s.t do S A2 Hence, for all S ((,)) 2
da X1
Consider two cases:
Since (f(0,)) is monotonically decreasing due the Armijo line-search and converging to 24. Hence, there exists a r' s.t. r' S such that f(0,-) f s E and f(0,--1) f 2 i.c. r' is the iteration index when the desired sub-optimality criterion is satisfied for the first time. This implies that for all < T d == f(O,) l e.
Case (1): If fr 2 An
(18_)) Hence, 1" = 11 fo. Since f > 0 and 0, a > 1. Hence for all f T',
((O,) f >
86 = f(0()
S f(0.)
> 0.
Using the condition of Case (1), we get
1 [f(e,) f2
8
1
2λ1 R
f(0.)
6, [f(O)) ST8
(where ā max(1,a))
f(0.)
6, [f())) -f"
de
f(0+)
fr
6, ā 1 [(0.)
Combining the above relations, for all / <'
1- 1
8441
5z
:=p
Since (0, 1) and (1 (1- 2) E (0,1), p= =ā (1- 1) 1). Recursing from 0 / = =-'-1
S, S exp exp(-pp (-pT') d0
In order to ensure that f(0,,) - f < e, we require,
do
(=+1) In
d0 ( max [ (=+1) In [((0)) -
+' In
p
mi
Case (2): If f <
Ag
e. We will divide the subsequent analysis into two phases.
X
21

---

Armijo Line-scarch Can Make (Stochastic) Gradient Descent Provably Faster
Phase (I): For all 1 S.t. do + +11 ((,)) s 2\, ((0,) holds, by a similar analysis above, we can conclude that, 8 f exp (-))) 50 = 5(0+) 5 - exp (-pr) [f(6)) f*)
Since 8, f(0+) f
Aa f Hence.
1 - In [(00)-
exp (-pT) (s(On) - m2 = TS
p
Phase (2): For all t > T, Ao 2 \1 ((0,) which implies Ao + λ1 f(0)) - 2Ag. In this case,
1
f(01+1) f - [f(e))
[f(e)) f = 5ut1 S 6c
2λo R 67
2A0
Following the standard approach, we divide both sides by det 6r and rearranging we get
1
1
5
(since 6,_
2 1)
2Ao
R
2Ao
R
6c+1
8--1
1
1
5,41
Summing the above for t = r to = T 1, we get
T' -
7
2Ag R
8T
0
81 2
T-r
2Ag 11
br
We need find T' such that dp S which means
2An R
27o R
2dg R
1
T-1 Sc = T-T2
T
+ p
ln(oo/))
2Ag R
E
E
Putting everything together,
2An R
[ (-+1) In [(00) -5"
T T>
+ max (2 RM
C. Proofs for Sec. 4
Corollary 1. For a fixed e > O, assuming [() is convex and satisfies Assn. to 3 with Lo = 0 and w = 0, GD LS with
Mmax = oc, requires T max(2A1 ||0, - 1 11 (f (5++)) +1) In ((8))-1") iterations to ensure that f(Or) f S.c. c.
Proof. Using the convexity of s.
f(0.) 5 (V - (VS(0)1 110 -
|V/(0)1 [f(0)) - -r
|0, 0
Next, we show that |10+1 8" < |0 11 for all t, and hence ||0: 0* S 110. - -8
|10c+1
111 ||@: 8" no (f() 1|0: 012 ( O2 - 8*) m [
< |0: 0- 1 (0l) - f'1 + n. [V
(By convexity of f)
< ||6:
8- 112 (0l) - -f"1 2 (f())) f(0++1)
(Using the Armijo line-search with }
= -10 1-1 < |10, 0- 112 2m (f(0))) - 1 + 2 me (f.))) [
10 0" 0012
(By the definition of 0" and using that for all t, f" f(0T) < f(0.)
22

---

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
Combining the above inequalities,
[ [f(+,) f-
(16)
100 0- 1
Using Thm. with R = 100 10'1 and setting Lo 0 completes the proof.
Theorem 2. For an initialization 0g (0, f(0)) and comparator s.t. f(u) S if f(0) is convex, satisfies Assn. I to 3
with Lo- = 0, = 0, then, GD-LS with Mmna oc. > 1, requires T 2 ed 100-ul1 [(Or) (u) e.
1 + [(w] iterations to ensure that (20-1)
Proof. For an arbitrary comparator a s.t. f(u) & f(Or),
110+1 u1 - 110 u112- 2n (VS(0)), 02 u) ne IIV s 11, -ul2 n (S(0.) [(w]] + n [IV
(Convexity)
$ |10 - (f(ee) f(u)] The [f(0.) f(0++1))
c
(Using the Armijo line-search with c > }
M |10: 2
2m (f(()) f(u)] + tht [f(Ot) f(u)
(Since f(u) S f(t))
2 - 1
= |10 2
ni
- (
(17)
2 - 1
1
= |10+1 - u12 > |10g 2
[f(e)) - f(u)]
(Using Lemma I)
do (0.)
2 1
1 ((a)) f(u)
= 100 ull 2
A
f(0,)
(using do O since Lo, 0 and by defining C' := (2 (1/Ai)
By recursing from = to T 1,
10, ul12 - 10, - C T-1
[(0.) ((u)
Σ
f(0,)
Assume T is the first iteration s.t. f(Or) - fwu) S 6. Hence, and f(0,) (w)) > a. Consequently, [(0.)-f(u) > Combining the above relations,
f(0r) f(u) S a + π:u. Hence, for all < (T.)())-
[(0.)
2 < 110 ull2 - CT (1 -1_ 1
|
Since satisfies Assn. to and f(u) S e, then, using Lemma 4 with M f(0)) and B s²-1 where y such that ||0r u|l S R. Since || - w|l s 110g ull. we can set = L1 110 u/|. Hence,
|0 py--wlj ul12
f(0r)- f(u) - 2 + 2 f(0o) LL f(0o)]
2
==
= ff(0r)-f(()) f(u)= < ç _ + 1r
2 2
u12 <
2
+
L
2
110 - 21/ -T
CT
[1_2]
=
2
E
+
L
2
|10 - u11 -CT
f(u) +e (18)
é
Hence, in order to ensure that f(Or) - fuu < e, it is sufficient to guarantee that ||0r u11 < i. In order to guarantee this, it is sufficient to set T as follows.
10
1
f(u)
T
L
1 +
(Using the definition of a)
C
23

---

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
Using the definition of C, conclude that it is sufficient 7 as:
cλ1 |6u
u112
1 + [(u)
T 2
(2c 1)
Corollary 2. For logistic regression on linearty separable data with margin for all i, | S for an initialization 8o an e E ((0)), GD-LS with 7mnax = 3o requires [(Or) 2e.
2 (1-c) 17 In (+)]²) iterations to ensure that
Proof. Define u' to be the max- max-margin solution i.e. ||u*|| and y be the corresponding margin, i.e.
= min yelrs, u²)
(19)
For scalar B > O,
[(Bu)
n Σ
n 1
In(1 exp(- Bu)))) exp(-u(o,, exp(-87)
1
(20)
For normalized data, s.t. || < I, the logistic regression loss is convex, is uniform smooth with L Amaa
< 1.
4n
We set In (+) implies that f(3u)) S c. For the defined in the theorem statement, consider two cases: Case f(Or)) < f(3u") S e. This gives the desired result immediately.
Case (II): ((r) f(Bu)). this case, we can use the result in Eq. (18) in Thm. with the comparator u B3" where
[()) S Hence, GD with Armijo line-search with c, 1maax 30 and 0g O ensures that when T the first iteration
s.t. f(0r) f(u) S f(0r) S 2c, then, for C = 2c-1 L 1/² f(0o) B L1 f(6u) where B e--1 and
od
q = L, |10 ull.
1(0T) S f(Bu)) )+
L CT
g
(
( (+((()))
e
2
L
2
CT
[(0)) S e +
(Since f(Bu") S e and == In (t))
72
2
Hence, order to ensure that f(Or) s 2e, is sufficient to set as:
T>
In
C22
cλ1
2
In
(2c 1)
3cL1 (v 1)
In -
2
(using the value of A1)
(2c - 1)(1 <)>²
216c
In
(2)
(using Prop. for the value of and L1)
(2c (oc-1]( - ?
Combining the two cases, we conclude that f(OT) S 2e. Corollary 5. Assume f is convex and satisfies Assn. 5, then GD-LS with Mmas 00 requires
f" 8 In T= ( R((Le + L. + I.. L.gtt) + (R(L (Lo)² + Lo(Lg + V VLo)))
E
iterations to ensure that f(Or) - f S*S5. S.
24

---

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
Proof. Since is convex, we can follow similar argument in the proof of Cor. establish that [V >
(1(0)) where R ||8u 1- This allows to apply the result from Thm. 1, obtain bound on T. Since the bound in Case 2 is bigger than Case 1, we consider the bound in Case 2.
2Ao R
(f=1) In f(00)= -
T
max (2RA1,1 13
e
Ao R
RA1
= O
+
E
From Thm. 1, we have An - (Lo + L)w) and Aι = --e and w with their respective expressions in terms of Le and Lg yielding
(L. (L1 (v + 1)). By using Prop. 3, we can substitute Lo, L v,
T =- R(L. + Ly VVL L Loge)
(R(L vLo) + Lo(Lo + v V.a))
f f e 6
In
C.1. Proofs for the Polyak Step-size
For an arbitrary comparator u, we generalize the Polyak step-size (Polyak, 1987) at iteration E [7] as:
f(0,) - f(u) 7) c [V
(21)
[16,)- recovers the standard where, e (0, 1) is hyper-parameter parameter. Note that when u = 0 = arg min f(0), nt = f(.)1 Polyak step-size Polyak (1987).
We analyze the convergence of GD with the step-size in Eq. (21) under Assn. 3 with 0 i.. will assume that f is L uniform smooth and that for all 0, /|V [(0) I f0). From Prop. 1, 5 and 6, we know that this property is true from binary classification with the logistic loss, well as for multi-class classification with the cross- cross-entropy loss.
Theorem 7. For initialization Og. (0, I (0o)) and comparator S.I. ((u) S c, (() is convex, satisfies Assn. I to 3
with Lo 0, O, GD with the Polyak size-size in Eq. (21) and c 2. requires
cv² 110p u1/2 T
1 f())
(2c-1) 1)
e
iterations to ensure that f(Or) - f(u) Se.
Proof. Following proof similar to that for Thm. 2, for arbitrary comparator f(u) s f((1))
|| u1 = |00 ull 2n (V.())), 0. u) +m [[V) s 110 -ul - -2 [f(0.) - f(u)] + +m (V)
(Convexity)
< 110, - u12 - 2 [f(0)) f(u)] + m1 [f(O)) - f(u)]
(Using the Polyak step-size in Eq. (21) with > to simplify the third term)
2 )) [f(0.) - f(u)]
110
(Using the Polyak step-size in Eq. (21))
c cllvf(0)))1
2 2)
(s(0)) - f(w))
S 110g wll
(Using Assn. 3)
ev [f())))²
= -10 - uII2 < 10: 1112 C [f(O)) ( f(0+)
f(u) 2
(Using Lemma 1 and defining
(2c-
cvu
25

---

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
By recursing from = to T 1,
[(0.) [(0.)- 2 f(8))
| u12 - 1100 u112 C
Assume T is the first iteration s.t. f(0r) ((u) e. Hence, f(0r) < a 1+ f(J) f(u)
Hence, for all <(0,)))) [(u) >e
and 1(0 a. Consequently, [(0))_((u) f(a]
Combining the above relations,
f(0.)
100 u112 2 1100 -ul2 CT 1- C2
Proceeding in the same manner as the proof of Thm. 2, where B e²-ع and q = L1 110 =ul. we obtain that,
10 |0 -r-u2 ul12
((0T)- < E + [1P ((0o) + BL [(0o)]
2
L
(1-2)
L
((0r)- f()) s 2 + 1 u1/2 S
+
2
110 - u112 - CT
-CT
= - 2
+
110 - w - -TT
[(u) + (22)
Hence, in order to ensure that f(Or) f(u) S e, sufficient to guarantee that ||0r u112 S f. this, it is sufficient to set T as follows.
In order guarantee
2 cv² |10g u1/ (2c - 1)
1 1 f(u)
Theorem 8. For logistic regression linearly separable data with margin "/, for all ||æ;1l 1, for initialization
0o 0, fixed e (0, (0o)), GD with the Polyak step-size T)t min <[[[[[e))] Te for some >> 2 requires
f(8.)
8²
64 c4c²
64c 1
T
In
C
(c 1) 2
to ensure that [(O)) 5 e..
Proof. The logistic loss on linearly separable data is convex, satisfies Assn. 1 to with Lo 0, w = 0, v By Assn. 3, [0)] s f(8) and we can bound the Polyak step-size as:
and f 0.
Ne min 1
1
(23)
cv² f(0.) 2e 2e
Using the GD update: 0c+1 0c --n, '7 (f(),, consider comparator u s.t. f(u) S max[cv=.2] and f(u) S f(0.) for all
26

---

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
1 [T] Assuming that 7 is the first iteration such that f(Or) f(u) S e, we have that,
||0+1 - u112 2 = 00 - u112 2m (Vf(0.), - u) + n [V)())
||: u1( 2m (ft) f(u)] n²² IV
(Convexity)
|00 212 2 (ft)) f(u)] 1he [f(0:]
(Using the Polyak step-size with 2)
c
2 1
100 w 2
Th f(0.) + 2 f(u)
2 1
min 1
f(0.)
100
2
21. f(u)
(Using Eq. (23))
ceu2'
2e
|00 2
2 1
1
2T f(u)
(Since f(0,) 2 e for all T)
max {cv22 2]
100 1
2
1
1
f(u)
(Since THt S from Eq. (23))
max {cv2, 2}
e
||0
2
2
1
1
(Since f(u) S max(cv2.2)
max {cv2, 2}
max (cv2,2)
e
1
1
10: 212
max {cv2, 2]
=C
Summing up from 0 to 1,
10 - u112 S 110g u1/2 CT |ull2 CTu
(Since 0g = 0)
Since f is uniformly smooth, using Lemma with M f(fo), we get
10 u112
S(Or) f(u)
6 + 1u2 f(0)) + 11 2
T
[Iml CT)
2
To ensure that f(Or) f(u)= S c, it is sufficient to set
| 2
2
(24)
C
In order to bound [lu]]. we define u² to be the max-margin solution i.e. ||u*|| = and y to be the corresponding margin, i.e.
:= min ye (2,, u²)
(25)
Consider = 3 u², for scalar == 1 In max max (ev² 2)
f(u) = Σ In(1 exp(- Bu, Bu))))
1
Σ
exp(-Mi(xs,)) u²)) < exp(-87) max (cu? 2]
(26)
This satisfies the requirement on (u). For logistic regression, we and since e 2, therefore max(cv² 22 2] cv2 Using this to bound T, get that,
g2
c²
22
cV2
2
T
In
C
(c
1)?2
Finally, we conclude that after T
8a
2 3
In
iterations we have f(Or) - -f(u) s e and since f(u) S e
C
T0- 7
then f(Or) <
27

---

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
C.2. Helper Lemmas
Lemma 4. Fore e (0, and a comparator u s.t. f(u) S if satisfies Assn. 1 to with Lo and O, then, for all s.t. ||0 u|l L.
1(0) - s(w) S c + BL, M) 10 u
2
where B == e-11 Furthermore, if f is also L uniform smooth, then, for all 6,
110 ul12
c 2 [u [T] 5(0) f(u) 2
2
Proof. Since f satisfies Assn. with Lo O, using Eq. (1), we have that for all s.t. 110 ull s 1 and B == =i11
B L1 (u)
110) f(u) (VS(u), u)
110 u112
2
[Vf(u)12
1²M 10 - 212
B L1 f(u)
10
ul12
(Using Young's inequality)
2M D2
2
[f()]2
110
uu
2
[v2 M + B B1 f(w)]
(Since f satisfies Assn. with = 0)
2M
2
²²
|10
ull2
$ 2 M
+ 122 BB
(Since f(u) S c)
2
10 u112
f(0)- f(u)
+
[22 M BL, M]
(Since 2² 2M S 1 for S M)
2
f is L-uniform smooth, can use the standard descent lemma to get, that for all 0,
L
f(0) f(u)= s (Vf(u), u) 2 110 ull
Using this inequality and following the same proof gives the result.
28

---

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
D. Proofs for Sec. 5
D.I. Proofs Sec. 5.1
Corollary 3. For an > O, assuming f(0) satisfies Assn. 1 to with Lo 0, w = and Assn. 4 with < 1, if
Jr == min (())), then, GD-LS with Thaa = 0o, requires T 2 max 1, 2x1 ensure ((0r) <.
( +1 In (10))=1))
iterations to
n=²
Proof. Using Assn. 4, we know that,
|V) 2 [v(0)) - n² (f(0) fr²
Using Thm. with R = and Lo = 0 completes the proof.
Corollary 4. For an MAB problem with arms, rewards bounded [0, 1]. GD-LS with uniform initialization i.e. Va. To, (a) 1/K, 2 1mmxx requires T O (K² In (2/2) iterations to guarantee (TTrr r(aa)(a))))))))))))) -6
Proof. From Prop. 4, we know that the MAB problem satisfies both Assn. 2 and Assn. 3 with the parameters Lo = 0, L1 = 72, / = 24, and w = It also satisfies Assn. with <= Since GD-LS guarantees monotonic decrease of the objective, Mei et al. (2020, Lemma and Proposition 2), implies that for the uniform initialization where xo Ta(a) for all a, ne, (a*) 2 K result of Cor. 3, and get:
V 1 2 0. Therefore, we have μ min, no, (a*) R. With these parameters, can instantiate the
(5" (=+1)
f(00) -
T max (1.20885² 52 K2] -0000k2 1n )
(.1(+11) and c 2 (since A1 = 3 1-c
7 7
(since f = 0 and /(00) - l 1)
Corollary 6. For the tabular MDP problem defined Prop. GS-LS, with c 1 and Tmaa = 00 requires
2.
4 (iin, p(s) (1 (1-7))
)
23 T
3 +
1
1-7
(1 - 7)e (1-7)e
iterations to guarantee f(0r) ==* (p) V (p) S where μ infietr u((:) and u(0) /s minses pis) a" (s) is the action corresponding to the optimal policy n²" in state s, yy is the discount factor, p is the initial state distribution, and the size of state space.
min, uo(a (s))s)
Proof. As proved in Prop. 7, the function f() satisfies Assn. 2 with Lo and L1 = 4-mnn, of (1-)))
72
S.
Assn. with // = 8 3 min, 2do) (1 (1-1)) and = 0 and Assn. 4 with Since GD-LS guarantees monotonic decrease in the objective, Mei et al. (2020, Lemma 9), implies that y > With these parameters and noting that f"
I-y
29

---

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
can instantiate the result of Cor. and get:
48
4
min, [(s]
(1 - 7)
4 min, n(s)
(1 (1-
((06)
2 max
1,
3
3
VS +1
1 Y
1 1-7
e
(since \1
3 I-c and
2)
4 min, p(a)
1 - (1 - -1)
4
min, p(s)
1 (1 -i)
48
1
T
3 +
8 8
3 +
VS +1
In
1
7-7
1-7
7)
(since V*(p) S - for all policies m)
3
273
4.
mins p(a) - (1 - 7))
1
T2
3+
in
1 1-7
(1 - 7)E
D.2. Proofs for Sec. 5.2
Theorem 3. For a fixed e E (0, X if satisfies Assn. to 3 and Assn. 4 with Ç 2,
f 2,
0 and if == min μ((,) >
0, then, CD-LS with Mmax oc, requires T 2 (x1((0) + Ao In
iterations to ensure that f(Or) S x1c
Aa
Proof. Using the Armijo line-search condition in Eq. (5), and combining it with the lower-bound Lemma 1,
1
f(0++1) S f(0.) No + X1 ((0.) IV
(27)
Phase 1: Let us define r := maxft s.t do s A f(fi)) Hence, for all t S T, f(0)) 2 Ao x. and hence,
1
1(0,+1) S f(0.) 2 ((0.) [V)(0))
From Assn. 4 with Ç = 2, we know that [[V 2/2 m(0) (S(0) [*] and that f 0. Combining these relations, we have that for all t < T,
f(0c11) 2A R (0,)
f(0.) = f(0))
4
(Since μ = minke(T) ((0e))
2
Recursing from / = 0 =T
[(0,) < f(00) a
Since f(0+) 2 Aa we get that,
Xr
1
Au 2h1 F(Ob)
Ao
r TS - a f(0o)
A1
A1
Phase 2: For 2 T, f(0.) <
Ae Combining this with Eq. (27) and using that [V 2 / f(O.),
X1
f(0++1) S f(0.) f(,))) f(0.) 1
An
2 2
Recursing from f to = T and using that 1 - exp( -Iz),
(- p (T (T- -T)
f(0r) S exp
f(0-)
2 A
30

---

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
Hence, in order for [(0r) S e, require
Ao T In
f(0+)
1
Since 5(0+) - a sufficient T as:
Au In T 2 +
f(0b) T
6
:=(rr)
Hence, it is sufficient to set T' as:
s.t 7 TS 2
Ao ((0b)
T max h(r)
Xn
Calculating the first and second derivatives of l(()),
270 a
2Ad a² (T) =- p (f((0) Ta)²
- (S((0) aa)
Hence, ((F) is maximized when at = 201 (f(Hb) 2n] Calculating h(T*), we conclude that it is sufficient set T
2 )i5(00) - -o0 (In
Ao
Aze)
1
31

---

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
E. Proofs for Sec. 6
Lemma 5. For a finite sum f(0) - Ei=r min fi(0) = 0 for all and an arbitrary comparator u, then iteration of
SGD-SLS satisfies the following bound:
10t+ - 2112 - 100,
ul12
(2 (2- )) n +
2
Proof. Using the SGD update:
0c+1 = (O.). for comparator u,
|0 - u112 = |10e ull2 - 2 (V.f((0)), 6 u) + n || f((e))l
s ||0: u1l2 2 (ft( [((4]+++ n (
(Convexity)
$ |10g u112 2n (fc(0() f((w]] Th [f. f((++)))
(Using the stochastic Armijo line-search with c }
I |10: u112 2m (f(( - f(()]+ + Tt [f((O.) - ft''
(where ft" == min f:)))
c
= |10, 2 2m (v(( - Λ² - 2m Se(w)] + Tte [v((Ot) - f2
(Add/subtract ft")
2 1
= |10: u -
m (f.) - f('++ 2m [f((u) - fc"
1
|0 u & |10g
u1l2
2
ni [f(((0)]] + (m]
(Since ft" = 0)
Theorem 4, For logistic regression on linearly separable data with margin ",, if. for all i, |xx|| S 1, for a fixed E (0, 1).
SGD-SU SLS with Tmax = and e = requires T = + [In (+)1²) iterations to ensure that Eiinfeerry f(0:)] S
5x 2
Proof. For the and T defined in the theorem statement, define the event G [inf, c}. Using the law of total expectation,
E
inf s(0.)
E
inf S(.)G [E(T]]
Pr[G] + E inf [(0)) Pr[g]
(28)
[T(T]
[E(T)
S E
inf [cE[T]
f(0.)lG))
(By definition of G)
Hence, we need to bound E [infeerry [(0,)] conditioned on the event G = {infeetr f(0,) 2 c).
Conditioned on G:: For normalized data, s.t. ||>م||| < the logistic regression loss convex, uniform smooth with
L= Amax_ X) < Using the standard guarantee for Armijo line-search, we know that Muna 2 min { Mmmaxx 2 ( ]
4n
Since f() 0, combining this with Lemma 5,
2 [c(O,) + 2m (m
||0+11 u 110:
ull22
2
min Mmax
L
110,
w|
min
7max:
[e(O.)
(Since L and setting }
2
1
2f((u)
|00
w|
f((0.)
(Setting 7max and since <
3
Taking expectation over the randomness in iteration conditioned on the past iterates,
f(O)) 2f)
u112
||0:
u112
(Since u is independent of the randomness at iteration
e
32

---

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
Consider 3u" where inequality, get,
In (1) implies that f(u) S 12- Since e S 1, f(u) S Using this relation with the above
f(O:)
E. 11 u u1/. s 10 u1/
3
6
From the conditioning on G we know that f(0() 2 c. Hence,
E 111 - u - 102 21/2
6 3 + =
10,
u
u
Taking expectation w.r.t the randomness from iterations t = to T 1.
B1 u/2: - 18110 u1 6
T
B[ w//2 < 100
u1
(Summing from / - 0 to T 1)
6
$ 3 T
(Since 0g 0 and ||/|| (3)
6
Since satisfies Assn. 1 to 3, f is uniform smooth and f(u) c, then, using Lemma 4 with M g.
|0r
ul1
L
[lf(Or) f(u)] S 2 1
- CT
2 +
2
:=
3E
L
+ B[J(0T)
8
CT
(Since f(u)
In order to ensure that ([S(OT)) < 3r it is sufficient to set T as:
g T 2
12 ) 2
In
C c2?
Since the above calculations were conditioned on Go, we can conclude that after T Blinfrgm [[T < 2. Hence, from Eq. (29)
Eg2 [In (12) iterations,
I 5c
inf (0t) (E/2
2
Theorem For logistic regression on linearly separable data with margin 7, if. for all i, ||>e|| S 1, for a fixed E (0,
where C" = =1(1), SGD-SLS with T/nax = and = requires = n
In
[ [²)
iterations to ensure that
Elinfre f(0.)) < 5e
Proof. For the and defined in the theorem statement, define the event G (inf (inffe(m([( < c). Using the law of total expectation,
E
inf [(0.))
= E
inf [E|T]]
/(0.)
Pr[G] +
inf [(0.))G")
Pr[ga]
(29)
[E(T]
(E|T
Se + E
inf (e[T]
f(O)))
(By definition of G)
Hence, we need to bound E [infretr] f(0.)) conditioned on the event G (infre(r) f(0.) 2 c).
33

---

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
Conditioned on G Note that from Lemma 1, we know that 2 min mmax [z(0,] combining this with Lemma 5, we get that.
C' where C² := X Since fc(0) 2 0,
110+1 - u1 v 10: - u 2 -) min (Tmax fe(O.), C*} + 2fmax
min 1Tmaax f((()), + 2m [ee
= 10, u
(Setting c c= -33
In order to simplify (*), consider two cases that depend whether not fo())
min f1 (0:), C"} I(.(((+)) 2 e)
min Mmaxx f((8)), I(f((0,) <
min Tm (c() C²) [()((O,)) 2 min (/maxx, C") I(.f((0,) 2)
2
Combining the above incqualities, we get that,
min f, C²} I(f((O.) 2 2c + mmax (u)
||0++1 - u112 = 10: ull2
2
Taking expectation over the randomness in iteration t, conditioned on the past iterates,
min {Tmaxe C*} Pr(f((0.) c] [J
[1 -=l2) < 110, ul2
2
(Since 7/max and u both independent of the randomness at iteration
From the conditioning on G we know that f(0)) 2 e. Since f is the average of the fę losses, we know that there exists at least one j s.t. (6.) 2 c. Hence, conditioned on the past iterates, (r.f. 2 e N 3. Combining this lower bound with the above inequality, we get that,
min {Mmax C*}
E, [11 u1[21 s ||0: u1l
2n + 2mmax [f
min {1, Cr) 2 f((
||0, u|1
(Setting Mmax 2)
2n
Define u² to be the max-margin solution i.e. ||~*|| || = 1 and y to be the corresponding margin, i.e.
7 = min ye(rs; u²)
(30)
For a scalar B > 0,
1 n n
1 a n
f(Bu')
Σ In + (xp(-M((,, Bu")) S
Σ
exp(- (x,,, u²)) s exp(-87)
(31)
Consider u Bu" where 8 = In 2 implics that f(u) < with the above inequality, we get,
2. Since e < and n 2 1, f(u) s e. Using this relation
min (1, C')
2e
E - u|/2] S 110. u1
2n.
n
For < < min (n 1,
Ee[1 - u1/2] < 10. -ul² min {1, C*}
4n
34

---

3r 3 Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
Taking expectation w.r.t. the randomness from iterations to T 1,
min {1, 4n min {1, T
E [111 - u1/2] - 11 ul]2
u1/2 - 100 ull2
(Summing from 0 T 1)
4n
min {1, C,
s B²
T
(Since 0g 0 and ||]|| ()
4n
==C
Since satisfies Assn. 1 to 3, f is uniform smooth and f(u) e, then, using Lemma 4 with M $.
BlS(0r) - s(w)] S
c
+
2 +
|T
u11
2 +
L B2 - CT
2
2
==b
3x
L
= B[)(rr]
+ 2
[ CT
(Since f(u) S c)
In order to ensure that [[f(0r)] <
3e is sufficient to set I as:
T C
32 n
In
11
]
min 13
Since the above calculations were conditioned on G", we can conclude that after / s 3/ Hence, from Eq. (29)
4n min m (''
[In (=)] iterations,
E
f0t) 6E/2
inf
s 5c 2
Corollary 7. For logistic regression on linearly separable data with margin 7/, for all i, ||aa||| S for a fixed E
0,
where C² = X1 648 SCD-SLS with Mmax = 1 and requires
1. 1
= min ( 1 In
n,
72
c2
iterations to ensure that Elinfrem f(0:)] < bc
Proof. Combining Thm. 4 and Thm. completes the proof.
Theorem 6. For logistic regression linearly separable data with margin 7/, if. for all i, ||I,|| 1, for fixed
(o. mint t,0 where C' : X1 648*
1 1 SCD-SLS with Muax = ! and and guaranteeing that for all t E [T].
Pr (f.(O.) 2 requires T = 0 [In (1)1²) iterations to ensure that B[f(Or)) <
Proof. Note that from Lemma 1, we know that 7) 2 min Thaux: f((01) c² where C² == Ai Since fc(0) 2 0, combining this with Lemma 5, get that,
10 - ul12 < 10, u1l2 2 2 min (Imaxf((0.) C'} 2mmax [f((u]]
min {mmax fe(O.), C*}
=1 u|
21max [f((w)]
(Setting
2
35

---

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
Since the algorithm guarantees that f((0)) for all I, fc(Ot) 2 3.2 Hence,
s 00 u1 min 7/maxx CC') + 21maax (u))
1 O 2f((u)
10: u1l2 min
(Setting Tmax = )
Define u² be the max-margin solution i.e. ||x*| 1 and y to be the corresponding margin, i.e.
= min ye(rs; u²)
(32)
For a scalar > O,
f(Bu))
Σ In(1 exp(- Bu" 3)"))) - n i= n ==1
1
1
Σ (xp(- u²)) exp(-8r)
(33)
Consider u = -u= where + implies that f(u) S 2. Since e S 1, f(u) S e. Using this relation with the above inequality, we get,
1
10:
ul
min
C"
+ 2e
2
1
1
u 2
min
(2' C"
(Since S min { C'})
Taking expectation w.r.t. the randomness from iterations t = T
min { C"}
E1
u112]
min 12, T
B||l0r
u < 110
u
(Summing from / = t T 1)
min 21 C*
$ 8
(Since 8g = 0 and |||| = 3)
Since ff satisfies Assn. 1 to 3, f is uniform smooth and f(u) s e, then, using Lemma 4 with M 4
[[f(Or) - f(w)] s 2/2
+
2 2 +1
|0
u112
s e
+ [32 - CT)
2
2 2
1=l.
L
= + =[S(0T]
+
3 CT
(Since f(u) 5))
In order to ensure that ([
3r 2 <
it is sufficient to set T as:
8² 4
1 2
T> 2 C
In
min(C', }
7
E
36


Reviews:
[{"review_id": "c8JSQg31Ys", "reviewer": "Reviewer_jUfU", "summary": "This paper investigates the effectiveness of the Armijo line-search (Armijo-LS) method for step-size selection in gradient descent (GD) algorithms. The authors introduce a class of functions that satisfy a non-uniform smoothness condition and show that GD with Armijo-LS (GD-LS) can adapt to local smoothness, leading to faster convergence compared to standard GD with a fixed step-size of $1/L$ (GD(1/L)). The analysis is further extended to the stochastic setting.\n\n## update after rebuttal \n\nThanks the authors for answering my questions. I decide to keep my score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their helpful feedback and address their concerns below. \n\n> *(1) Independence of Assumptions*\n\nAssumptions 3 and 5 do indeed imply Assumption 2(b). The reason we did not use Assumption 5 as our main assumption is because Assumption 5 cannot be satisfied for logistic regression, multi-class classification with $L_c = 0$. We explained this in Lines 137-142, and note that having $L_c = 0$ is essential to derive a linear convergence rate for logistic regression in Corollary 2. To see this from a technical perspective, consider $f$ to be a finite sum $f(\\theta) = \\frac{1}{n}\\sum_i f_i(\\theta)$ (for example, the logistic regression loss in Proposition 1). If $f_i$ satisfies Assumption 5 with constants $L_c, L_g$, it does necessarily imply that $f$ also satisfies Assumption 5 with the same constants (see Proposition 7 for a counter-example). \n\nIn contrast, using Assumption 2 as our main assumption enables us to prove that the losses corresponding to logistic regression, multi-class classification satisfy this assumption with $L_0 = 0$, and this enables us to prove the linear convergence rate in Corollary 2. Again, from a technical perspective, we can do this because if $f_i$ satisfies Assumption 2 with constants $L_0$ and $L_1$, then $f$ also satisfies this assumption with the same constants (please refer to the proof of Lemma 5). \n\nIn summary, we only use Assumption 5 for $f_i$ (and not $f$) corresponding to common finite-sum losses as a way (using Lemma 5) to show that $f$ satisfies Assumption 2. For example, see the proof of Proposition 1, where we instantiate this logic for logistic regression. \n\n> *(2) Positivity Assumption (Assumption 1)* \n\nFrom an algorithmic perspective, Assumption 1 is quite benign. As the reviewer suggests, it is possible to shift $f$ by subtracting $f^*$ and ensure that the resulting function $h(\\theta) := f(\\theta) - f^\\ast$ is always non-negative. Since $f^\\ast$ is a constant, $\\nabla h(\\theta) = \\nabla f(\\theta)$, meaning that we do not require the knowledge of $f^\\ast$ to implement GD. Moreover, the Armijo condition on $h(\\theta)$ has $f^\\ast$ on both sides, implying that implementing $\\texttt{GD-LS}$ on the non-negative function $h(\\theta)$ does not require the knowledge of $f^*$. We use this property in Section 5.1 (see Proposition 3 and the corresponding discussion). Finally, we note that most common losses in machine learning (cross-entropy, exponential, and squared) are non-negative. \n\n> *(3) Missing Reference*\n\nThank you for directing us to this paper. The assumption in their paper is more restrictive than ours, as they assume strong convexity, whereas we only rely on gradient domination. This enables us to consider non-convex losses such as generalized linear models. Additionally, they focus on exact line search, while we consider Armijo line search. We will cite this paper in the final version.\n\n> *(4) Experimental Validation*\n\nIn the deterministic setting (with access to full gradients), $\\texttt{GD-LS}$ is a standard algorithm for (non)-convex minimization and is widely used in practice. In the stochastic setting, Vaswani et al. (2019b); Galli et al. (2024) have empirically evaluated the performance of $\\texttt{SGD-SLS}$ and its non-monotone variant for convex losses corresponding to linear and logistic regression and non-convex losses with deep neural networks. These supervised learning experiments have demonstrated the efficacy of $\\texttt{SGD-SLS}$. As we explain in Section 6, under the interpolation assumption, Vaswani et al. (2019a) can only prove an O(1/ϵ) rate for SGD-SLS on smooth convex losses such as logistic regression. However, empirically, the convergence seems to be faster than O(1/ϵ) (for example, see the linear convergence on the mushrooms dataset in Vaswani et al. (2019b, Figure 3). Our paper (specifically Corollary 5) can explain this fast convergence. \n\nFor the softmax policy optimization problem in RL, we note that Lu et al. (2024, Figure 1) have shown the linear convergence of $\\texttt{GD-LS}$ on tabular Markov decision processes. However, they could only prove an O(1/ϵ) convergence rate for the resulting algorithm (Lu et al., 2024, Theorem 1). In order to attain a linear convergence rate in theory, they propose a non-standard line-search scheme that requires the knowledge of the optimal value function. On the other hand, Corollary 4 in our paper proves a linear convergence rate for $\\texttt{GD-LS}$ (the standard line-search) on bandit problems, and the same proof extends to the MDP setting (using Proposition 6 in our paper). \n\nWe will include these comparisons and explanations in the final version of the paper.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes.", "experimental_designs_or_analyses": "Almost no experiment.", "relation_to_broader_scientific_literature": "See below.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Weaknesses:\n\n* Independence of Assumptions: Assumption 2(b) is a direct consequence of the generalized smoothness condition used in prior literature. The proof primarily relies on Assumptions 2(c), 3, and 5, with Assumption 2(c) being implied by the other two. Since assumptions should ideally be independent, I suggest presenting only Assumptions 3 and 5 to clarify their distinct roles in the proof. Alternatively, would it be possible to provide an example satisfying Assumption 2(c) and 3 without Assumption 5?\n\n* Positivity Assumption (Assumption 1): The paper assumes that $f$ is positive over the entire space. While it is possible to shift \n$f$ by subtracting $f^*=\\min f$, in most cases, $f^*$ is unknown. Would it be possible to remove Assumption 1 and instead consider \n$|f|$ in the relevant conditions?\n\n* Missing Reference: The paper should reference [1], which provides gives tight rates for GD(LO) that are faster than for GD(1/L) in strongly convex setting. This aligns with Assumption 4 when $\\xi=2$. \n\n[1] De Klerk E, Glineur F, Taylor AB. On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions. Optimization Letters, 2017, 11:1185-99.\n\n* Experimental Validation: More experiments should be conducted to further validate the efficiency of the proposed line-search algorithm, particularly in multi-armed bandit (MAB) problems and stochastic settings.\n\nStrengths:\n\n* The newly proposed conditions are well-discussed and provide valuable insights.\n* The paper reveals an interesting result: GD-LS provably adapts to local smoothness, leading to improved convergence rates.\n* The paper is well-written and easy to follow.", "other_comments_or_suggestions": "See above.", "questions_for_authors": "See above.", "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": {"ethical_review_concerns": "N/A"}}, {"review_id": "iVrNbRgQlG", "reviewer": "Reviewer_sPj3", "summary": "This paper studies gradient descent using Armijo line search to choose the stepsize. They prove convergence rates for the algorithm under a non-uniform smoothness condition, and specialize these results to logistic regression, softmax policy gradient for multi-armed bandit problems, and GLMs with the logistic link function. They also have convergence guarantees for a stochastic version of the algorithm for finite-sum structured separable logistic regression.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their helpful feedback and address their concerns below. **For all unaddressed comments, we agree with the reviewer's suggestion and will make the corresponding change.** \n\n> *(1) Lower-bounds for $\\texttt{GD(1/L)}$*\n\nFor logistic regression, Theorem 3 in Wu et al, 2024 shows that $\\texttt{GD(1/L)}$ (or more generally, GD with any constant step-size that guarantees monotonic descent) cannot have a convergence rate faster than $\\Omega(1/\\epsilon)$. Hence, both $\\texttt{GD-LS}$ and $\\texttt{SGD-SLS}$ on logistic regression are provably faster than their constant step-size analogs. \n\nFor the softmax policy gradient in Section 5.1, Theorems 9, 10 in Mei et al, 2020 show that GD with any constant step-size cannot achieve a rate faster than $\\Omega(1/\\epsilon)$ on both bandit and MDP problems. We mention this after Corollary 4 in the paper. For the GLM problem in Section 5.2, we are not aware of a lower bound for $\\texttt{GD(1/L)}$ or normalized GD. We will include these comparisons.\n\n> *(2) Softmax PG - Setup* \n\nWe note that the linear convergence result in Corollary 3 also applies to the general MDP problem. See Proposition 6 for the problem setting. $\\texttt{GD-LS}$ in Section 5.1 is equivalent to softmax policy gradient in the \"deterministic'' or \"exact'' setting. This setting is commonly used as a testbed for analyzing policy gradient algorithms [Mei et al 2020; Section 4, Lu et al 2024]. For general MDPs, the deterministic setting corresponds to knowing the rewards and transition probabilities, and is the same setting under which classic RL algorithms such as value iteration or policy iteration are analyzed. This was our motivation to consider the problem setup in Section 5.1. \n\n> *(3) Softmax PG - Handling stochasticity*\n\nFor the general MDP problem, in cases where the rewards/transition probabilities are unknown, the policy gradient is estimated by interacting with the environment. Standard policy gradient results (e.g [Theorem 29, Agarwal et al, 2020] can then prove convergence up to an error incurred because of the estimation. \n\nFor the specific case of stochastic multi-armed bandits with unknown rewards, recent work [Mei et al, 2023] has proven stronger global convergence results. In particular, Mei et al, 2023 use importance sampling to construct the stochastic softmax policy gradient and use it with constant step-size SGD. The resulting algorithm can be proven to converge to the optimal arm. From Proposition 3, we know that the objective function satisfies Assumptions 2, 3, and 4. It also satisfies the interpolation condition [Theorem 4.2 in Mei et al, 2023], required for the $\\texttt{SGD-SLS}$ analysis in Section 6. Hence, we believe that a variant of $\\texttt{SGD-SLS}$ could be a good algorithm for the stochastic multi-armed bandit problem. However, since the softmax policy objective is non-convex, we cannot directly use the results in Section 6 and leave this interesting direction to future work. \n\n> *(4) ....not clear if gains from GD-LS would extend to more typical problems..*.\n\nWe have tried to argue that losses that satisfy our non-uniform smoothness assumptions are in fact, not as rare. To illustrate this, we have given numerous examples ranging from classification in supervised learning to policy gradient in reinforcement learning. In general, applications where we use losses with an exponential tail (e.g. exponential, logistic loss) or those that use a softmax function to parameterize probabilities can benefit from using a line-search. Another example that we did not study in detail is noise contrastive estimation [Lu et al 2021], where GD is slow because of the flatness of the landscape, and $\\texttt{GD-LS}$ can potentially improve the convergence. \n\nWe agree that large gains from $\\texttt{GD-LS}$ are not always possible (e.g. for quadratics) and if the function is only uniformly smooth, $\\texttt{GD-LS}$ will converge at the same rate as $\\texttt{GD(1/L)}$. However, even in this case, $\\texttt{GD-LS}$ enables setting the step-size without estimating or conservatively bounding the smoothness constant and thus has a practical benefit.\n\n> (5) *Comparison to Polyak step-size*\n\nThe proof of Theorem 1 (and non-convex results) relies on the monotonic decrease in the function values guaranteed by $\\texttt{GD-LS}$. GD with the Polyak step-size is not a monotonic descent method, and it is unclear how to extend the proofs.\n\n> (6) *Experimental Evaluation* \n\nSee Point (4) in our response to Rev. jUfU\n\n> *(7) Comparison to recent work on adaptive step-sizes*\n\nSee Point (1) in our response to Rev. 8uuj\n\n> (8) Cor. 2 vs Cor. 6: \n\nCor. 2 is for $\\texttt{GD-LS}$, Cor. 6 is for GD with the Polyak step-size.\n\n> (9) Proposition 3: Def. of reward gap\n\nIt is the difference between the rewards of the best (optimal) and second-best arm [see Lemma 17 in Mei et al, 2020]. \n\n> (10) Assumption 2 (a) and (b)\n\nThese are separate (but related) conditions that need to both be satisfied.", "claims_and_evidence": "For the most part, the claims made in this paper are clear and backed up by convincing evidence. There are three main places where this is not the case:\n\n1) At various times in the paper, the authors claim that GD-LS is better than GD-(1/L) by comparing the upper bounds they prove for GD-LS against upper bounds for GD-(1/L) derived in other papers. This is not a sound way of making the comparison---how do we know that those guarantees for GD-(1/L) are tight? Without lower bounds for GD-(1/L), it is possible that GD-(1/L) is just as good (or even better) than GD-LS in some or all of the cases considered in this paper. I agree with the authors that this seems unlikely given that GD-(1/L) needs to use a fixed stepsize, but to know this definitively, we'd need an actual proof.\n\n2) Proposition 3 seems to require that the reward vector (and therefore the optimal action) are known---otherwise, it would not be possible to implement GD-LS to sole the problem. The authors later argue that GD-LS is superior to some alternatives because they require knowledge of r(a^*). Even though this is true, GD-LS requires knowledge of the reward vector (and therefore the optimal action), so there isn't much difference. I understand what they are trying to get at---their algorithm is less \"specialized\" to the problem---but I think the advantage would be more clear if this distinction was made a little bit more clearly. I believe they are trying to gesture towards GD-LS being a good method for more interesting cases when we don't just know the reward vector / optimal arm, but I think the problem setup in this section could use a little more explanation. In general, you wouldn't know the reward vector, so you'd probably need to do some kind of online/stochastic optimization here---is there reason to think GD-LS would be good for that? Does the line search work well enough when you only have online/stochastic gradients and can only estimate the function value? Section 6 and the last sentence of page 6 suggests that they think the answer is yes, but it's not completely clear to me precisely what they are showing vs just claiming for the specific problem here.\n\n3) A lot of the claims in this paper are based on logistic regression or similar objectives where, for most gradient methods, convergence is initially fast and then slows down as the loss / gradients / hessian become very small. This is a rare example in optimization where very large stepsizes are possible / desirable, and it is not necessarily that clear that these gains from GD-LS would extend to more typical problems where the maximum possible stepsize is not so large.", "methods_and_evaluation_criteria": "Experimental evidence is provided for GD-LS versus other alternatives, but I think the stochastic setting is much more interesting for typical ML applications, and there are no experiments covering this. Experiments for SGD-SLS on logistic regression is one thing, but given  that the upshot of Lemma 3 is not very clear outside of the application to Corollary 5, it would probably be interesting to see how well SGD-SLS works on other (non-logistic regression) supervised learning problems, both convex and non-convex. \n\nAt the bottom of pg 5, the authors point out that GD with the Polyak stepsize can achieve the same thing as Theorem 2. This raises the question of whether the Polyak stepsize can also match the guarantee, e.g., in Corollary 1. On the one hand, to implement the Polyak stepsize you need to know $f^*$, which is not necessarily available. On the other hand, you only need to evaluate the function value once (versus multiple times for the backtracking line search). I feel making this comparison more thoroughly is important context for this work.", "theoretical_claims": "I read the proofs and they appear basically sound as far as I can tell.\n\nThe only issues I see are: \n\n- I believe Corollary 2 and 6 are supposed to be the same thing? But, Corollary 6 in the appendix appears to be slightly different than Corollary 2 in the main text.\n\n- Proposition 3: Shouldn't the reward gap be defined as \\min_a rather than \\max_a?\n\n- Assumption 4: As stated, this appears to just a complicated way of saying that $f$ has no stationary points that are not global minima (for arbitrary \\zeta, just take $\\mu(\\theta) = \\|\\nabla f(\\theta)\\|^\\zeta / [f(\\theta) - f^*]$, which is strictly positive for such $f$). I think it would be better to say that \"$f$ satisfies the $(\\zeta,\\mu)$-gradient domination condition if...\" because the $\\mu$ function plays an important quantitative role (beyond just the fact that it exists).\n\n- Pg 4: I'm being a little pedantic here, but this sentence \"As a concrete example, consider the case when $f^* = \\delta \\epsilon$ where $\\delta \\geq 1$ is a constant independent of $\\epsilon$\" does not make very much sense. Of course $\\delta$ depends on $\\epsilon$, it is exactly $\\delta = f^* / \\epsilon$! Calling it a \"constant\" let's you ignore it in the big-O convergence rate $O(R \\ln 1/\\epsilon)$, but I would say this is cheating a little bit. To make a similar statement, I would phrase it differently, something like: if you are only trying to reach accuracy $\\epsilon = \\Theta(f^*)$, then GD-LS will result in $O(R \\ln 1/\\epsilon)$ convergence. This isn't a big deal and I apologize for the pedantry, but I am not a fan of using a sleight of hand to hide things in big-O notation.", "experimental_designs_or_analyses": "There is not a ton of detail given for the experiments in the paper (this is probably fine given their simplicity), so it is hard to say.", "relation_to_broader_scientific_literature": "This paper is trying to show that GD-LS compares favorably to alternatives (especially GD-(1/L)). I am honestly not very familiar with prior analysis of Armijo line search beyond the most basic cases, so this work appears novel to the best of my knowledge. \n\nGiven the emphasis of this paper, I think it would be useful to spend some additional time putting this work into the context of related work.  E.g. see my comments above about the Polyak stepsize rule. Also, this paper puts an emphasis on the fact that GD-LS is adaptive to the problem parameters like the smoothness constant, so it would probably be useful to make some comparison to recent work on adaptive stepsizes for GD (e.g. [Carmon and Hinder 2022] and many more).", "essential_references_not_discussed": "See above.", "other_strengths_and_weaknesses": "Nothing else to add.", "other_comments_or_suggestions": "Small comments:\n\nAssumption 2: Are parts (a) and (b) equivalent statements, or are these separate conditions that need to both be satisfied? It is not obvious whether or not (a) <=> (b).\n\nTheorem 1: probably have $\\| \\nabla f(\\theta) \\|_2^2 \\geq [f(\\theta) - f^*]^2 / R$ be \"Assumption 4\" rather than sneaking it into the theorem statement? Then for e.g. Corollary 1 I would just note that convexity -> assumption 4.\n\nTheorem 1: it might be better to write this as $\\max\\{ 2 R \\lambda_1, 1 \\}\\left( \\frac{f^* + \\frac{\\lambda_0}{\\lambda_1}}{\\epsilon} + 1 \\right) \\ln\\left( \\frac{f(\\theta_0) - f^*}{\\epsilon} \\right)$ in all cases. In case 1, the bound is a little looser, but the lambda_0 / lambda_1 term is less than f^*, so by at most a factor of 2. And in case two, similarly, this is only looser by a log factor. On the other hand, it is easier to read and understand if there is only one case. Relatedly, in the last full paragraph on page 4, you describe the guarantee as exhibiting two phases, but unless you are considering the ln(1/eps) term to be \"large\", I don't see what is so different in the first/second phase---it is 1/eps or ln(1/eps)/eps convergence in all cases. The proof of Theorem 1 involves breaking things up into two phases, but that is more about the analysis than the actual convergence guarantee, at least as it is written.", "questions_for_authors": "See other comments.", "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": {"ethical_review_concerns": "No concerns."}}, {"review_id": "gkLZdnw4UM", "reviewer": "Reviewer_8bAV", "summary": "The paper analyzes functions where the local smoothness constant is given by \\\\( L(\\\\theta) = L_0 + L_1 f(\\\\theta) \\\\), which is satisfied by common objectives like logistic regression or regression problems with generalized linear models. The authors prove that Gradient Descent with Armijo Line-Search (GD-LS) converges faster on these functions by showing that the step size selected is lower-bounded by \\\\( 1/L(\\\\theta) \\\\). They extend their analysis to non-convex functions such as generalized linear models (GLMs) with a logistic link function and demonstrate empirically that GD-LS outperforms standard GD with a fixed step size. The paper also discusses the benefits of using a line-search in the stochastic setting by analyzing SGD with a stochastic variant of the Armijo line-search (SGD-SLS). By introducing assumptions on non-uniform smoothness and relating gradient norms to function values, the authors provide a framework that facilitates the analysis of GD with Armijo line-search for functions with exponential-type losses.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their helpful feedback and address their concerns below. \n\n> *(1) The targeted optimization problem in this paper is limited in terms of application perspective. The authors primarily focus on logistic regression and generalized linear models. Although the authors showed that object for softmax policy gradient also satisfies the assumptions in appendix, the application sides of this paper to real-world use cases are not significant enough for a venue like ICML.*\n\nIt is not required for papers in ICML to have \"application sides...to real-world use cases''. In fact, the call for papers lists \"Theory of Machine Learning (statistical learning theory, bandits, game theory, decision theory, etc.)'' explicitly as a topic of interest. \n\nHaving said that, we believe that our paper does have practical implications. In particular, our paper analyzes when $\\texttt{GD-LS}$ (a standard optimization method widely used in practice) can be *provably* faster than $\\texttt{GD(1/L)}$. Besides achieving adaptivity to the smoothness in a principled manner and hence requiring minimal hyper-parameter tuning (an important consideration from a practical standpoint), $\\texttt{GD-LS}$ can result in faster convergence on numerous convex (e.g. logistic regression) and non-convex problems (e.g. generalized linear models, 2 layer neural networks, softmax policy gradient) important in machine learning. We have argued that $\\texttt{GD-LS}$ can thus replace more specialized algorithms tailored for these specific problem settings. *Having a single algorithm that can work well across different applications is important from a practical standpoint.*\n\nFurthermore, as evidenced by the experimental results in [Vaswani et al, 2019], $\\texttt{SGD-SLS}$ (analyzed in Section 6 of our paper) results in good empirical performance on convex problems that satisfy our assumptions. Under the interpolation assumption, Vaswani et al, 2019 can only prove an $O(1/\\epsilon)$ rate for $\\texttt{SGD-SLS}$ on smooth convex losses such as logistic regression. However, the empirically, the convergence seems to be faster than $O(1/\\epsilon)$ (for example, see the linear convergence on the $\\texttt{mushrooms}$ dataset in Figure 3 of [Vaswani et al, 2019]. Our paper (specifically Corollary 5) can explain this fast convergence. *We believe that it is important to understand the behaviour of optimization algorithms, and that these insights can often lead to developing better methods in practice.*\n\nFinally, it is important to note that this same method - $\\texttt{SGD-SLS}$ and its non-monotone variants [Galli et al, 2024] result in strong empirical performance on non-convex losses with deep neural networks [Vaswani et al, 2019, Galli et al 2024] where our assumptions are not necessarily satisfied. *This demonstrates that developing methods that are theoretically principled in simple settings can result in empirical gains for real-world use cases.*\n\n> *(2) One potential improvement for this is that the author may list one or two informal version of their main theorem and provide a clear and succinct description of their contributions.*\n\nThank you for the good suggestion. We will consider making this change in the final version of the paper.\n\n> *(3) Moving the explanation on taking $\\eta_{\\max} = \\infty$ before Theorem 1 will minimize the confusion.*\n\nWe will make the change.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I browse the proof of Theorem 1 and it looks correct to me.", "experimental_designs_or_analyses": "The experiment designs look good.", "relation_to_broader_scientific_literature": "The main difference of this paper and other paper analyzing Armijo line search is that this paper consider a specific setting by Assumption 2. It can be viewed as a relaxed version of  symmetric (L0, L1) smoothness discussed in [1]. As this setting is novel, the theoretical contribution of this paper is new.\n\n[1] Gorbunov, Eduard, et al. \"Methods for convex $(l_0, l_1) $-smooth optimization: Clipping, acceleration, and adaptivity.\" arXiv preprint arXiv:2409.14989 (2024).", "essential_references_not_discussed": "Not applicable.", "other_strengths_and_weaknesses": "Overall this paper provides a solid theoretical contribution for the study of Armijo line search for proposed (L0-L1) non-uniformly smooth optimization problems.\n\nNevertheless, the writing of the paper can be improved. For instance, the authors list 6 contributions in the introduction section, but each of them look like the organization of each of section. To be specific, the contribution 1 (i.e., the content of Section 2) is simply the problem formulation. In other words, the main contribution of this work is not easy to find. One potential improvement for this is that the author may list one or two informal version of their main theorem and provide a clear and succinct description of their contributions.\n\nThe targeted optimization problem in this paper is limited in terms of application perspective. The authors primarily focus on logistic regression and generalized linear models. Although the authors showed that object for softmax policy gradient also satisfies the assumptions in appendix, the application sides of this paper to real-world use cases are not significant enough for a venue like ICML.", "other_comments_or_suggestions": "The description of taking $\\eta_\\max=\\infty$ in GD-LS is very unclear. At line 3 in Algorithm 1, the author initializes $\\tilde \\eta_t$ by $\\eta_\\max$. By taking $\\eta_\\max=\\infty$, every step $\\tilde \\eta_t$ in Algorithm 1 will simply be $\\infty$. From line 193-194 at the right column and from the proof, it seems that this assumption on $\\eta_\\max$ is somehow equivalent to taking a sufficiently large $\\eta_\\max$. Moving the explanation on taking $\\eta_\\max=\\infty$ before Theorem 1 will minimize the confusion.", "questions_for_authors": "No.", "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": "6vrt8UDbac", "reviewer": "Reviewer_8uuj", "summary": "Establishes rates for Armijo line search in several settings.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their helpful feedback and address their concerns below. \n\n> *(1) My major concern with this paper is that it doesn't have a related work section, and seems to only cite very old papers concerning line searches, as well as a nearly 20 year old text book...Please include this in your rebuttal and add it to the final camera ready.*\n\nEven though we do not have an explicit related work section, we believe that we have cited the most relevant work. This includes recent work on Armijo line-search (Vaswani et al., 2019a; Galli et al., 2024; Hubler et al., 2024), Polyak step-sizes (Loizou et al., 2021) and variants of normalized gradient descent (Mei et al., 2021; Axiotis & Sviridenko, 2023; Taheri & Thrampoulidis, 2023). Moreover, we have added the most relevant and recent references for each example – logistic regression (Axiotis & Sviridenko, 2023; Freund et al., 2018; Wu et al., 2024), generalized linear models (Mei et al., 2020; Hazan et al., 2015), softmax policy gradient (Mei et al., 2020; Asad et al., 2024; Lu et al., 2024), two layer neural networks (Taheri & Thrampoulidis, 2023). In the final version of the paper, we will add the following extended comparison and the corresponding references.\n\n**Comparison to GD with adaptive step-sizes on uniform smooth functions**: There has been substantial work on designing adaptive step-sizes for GD. However, most of this literature (for example (Orabona & Pal, 2016; Malitsky & Mishchenko, 2019; Carmon & Hinder, 2022; Khaled et al., 2023)) considers either the uniform-smooth, convex or non-smooth but Lipschitz, convex settings. In the uniform-smooth, convex case, the focus of these papers is to design more efficient ways to adapt to the smoothness constant, and the resulting methods achieve the same rate as GD with constant step-size. In contrast, we consider Armijo line-search which is the classic way to set the step-size for GD on smooth functions. The focus of our work is to identify when $\\texttt{GD-LS}$ can be *provably* faster than $\\texttt{GD(1/L)}$. To that end, we have identified a class of non-uniform smooth functions and shown that numerous examples in machine learning satisfy these properties. We believe that we are the first to identify such a broad range of examples and demonstrate the provable improvement of $\\texttt{GD-LS}$ over $\\texttt{GD(1/L)}$. \n\n**Comparison to GD on non-uniform smooth functions:** There has been recent work on analyzing GD (with/without clipping) on functions satisfying (L0, L1) non-uniform smoothness (Zhang et al., 2019; 2020; Koloskova et al., 2023). This work requires the knowledge of L0 and L1. In contrast, as explained in Contribution 1 and in lines 133-142 (after Proposition 1) of our paper, the proposed non-uniform smoothness condition is different and the $\\texttt{GD-LS}$ algorithm does not require the knowledge of L0, L1 or other problem-dependent constants. \n\n**Comparison to $\\texttt{GD-LS}$ on non-uniform smooth functions**: The most relevant paper to our setup is (Hubler et al., 2024) and we have compared to this in Lines 58-64. In particular, this paper analyzes the convergence of $\\texttt{GD-LS}$ on functions satisfying a different notion of (L0, L1) non-uniform smoothness. However, their algorithm requires the knowledge of L1 and the resulting rate is the same as that of $\\texttt{GD(1/L)}$\n\nWe hope that this addresses the reviewer’s concerns and helps them better contextualize our contributions. If the reviewer is aware of a key reference we have missed, we would be happy to include and compare to it.\n\n> *(2) I object to the use of stochastic to refer to analysis under interpolation condition... The title of the paper is misleading and would suggest to readers that there is some novelty in the paper that addresses the full stochastic setting.*\n\nAs is evidenced by the numerous papers analyzing SGD under interpolation, we first note that the interpolation setting is an important special case. Moreover, this setting can serve as a building block towards analyzing the full stochastic setting. For example, the stochastic line-search (Vaswani et al., 2019b) and stochastic Polyak step-sizes (Loizou et al., 2021) were originally designed for the interpolation setting, and have been adapted to the full stochastic case by combining these techniques with appropriately decreasing step-sizes (Orvieto et al., 2022; Vaswani et al., 2022; Jiang & Stich, 2023). Moreover, the proof for $\\texttt{SGD-SLS}$ in Section 6 is more involved compared to the standard SGD proofs. Given this, we think it is important to highlight that our paper also considers the stochastic setting, and hence we added \"stochastic” to the title. Note that we clarify that we are only considering the interpolation setting in the abstract\n\nWe do understand the reviewer's point, and will change the title to *Armijo Line-search **Can** Make (Stochastic) Gradient Descent Go Fast* to suggest that the speedup is for some special settings.", "claims_and_evidence": "There are some interesting results in this paper, and I like the expansion of our understanding of the (L0, L1)-smoothness condition and it's generalizations.\n\nI object to the use of stochastic to refer to analysis under interpolation condition. These are profoundly different settings and they should not be confused. The title of the paper is misleading and would suggest to readers that there is some novelty in the paper that addresses the full stochastic setting.\n\nMy major concern with this paper is that it doesn't have a related work section, and seems to only cite very old papers concerning line searches, as well as a nearly 20 year old text book. Research papers on line searches are normally published in the optimization literature not so much the machine learning literature, and I am not familiar with the state of the art here, but it's an enormous and heavily studied research area and there are surely related work that should be cited in the last 50 years since the Armijo line search was introduced.\n\nI would like to ask the authors to write a 1 page related work section that includes some recent state-of-the art research (at least some citations from the last few years), as well as older works. Please include this in your rebuttal and add it to the final camera ready.\n\nEDIT: The additional literature review is reasonable. Please also include the missing references mentioned by other reviewers also. I have updated my score.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "Established results seem solid.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "See Above.", "essential_references_not_discussed": "See above.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "Typo line 146 “satisfiesAssumptions”", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper analyzes Armijo line descent under a new generalization of (L_0,L_1)-smoothness that bounds the spectra of the Hessian by a constant plus a multiple of the function value. The paper also assumes in addition that the gradient norm is bounded by a constant plus a multiple of the function value. The assumptions are properly justified by presenting three problems where they (non-trivially) hold: logistic regression, a particular non-convex GLM, and softmax policy gradient  for multi-armed bandits and tabular Markov decision processes. This is sufficient to justify the assumptions. The paper has a few meta-theorems, which are specialized in the setting of logistic regression for separable data (both SGD and GD),  and softmax policy optimization for multi-armed bandits. I think the contributions and clarity are enough to warrant publication. But I would like to see the authors add additional references to other methods (in particular polyak based stepsizes) and address some minor issues I've compiled below. 

1- **Descent property, Polyak stepsize and additional comparison.**  Regarding your answer to Reviewer sPj3 on if Theorem 1 and Corollary 1 could be applied to the Polyak stepsize, note that GD with a Polyak stepsize *is monotonically decreasing*, even in the stochastic setting, so long as the loss is convex, see for instance Theorem 2.3 in [Garrigos2022]. In this regard, in both your full batch (when assuming $f(x^*) =0$) and stochastic setting you are competing directly with the Polyak stepsize.  Furthemore, the resulting stepsize of Armijo line search and the polyak stepsize are both local estimates of smoothness. Moreover, several closely related (though not the same) types of smoothness conditions have now been used to study the Polyak step size, see [Yuki2024, Vankov2025]. These are very recent works (online since October 2024), but I think it would enrich the reader's perspective if you point out some of these connections.

2- **The growth condition you assume in Theorem 1** sometimes goes by the name of the weak gradient domination condition see (Agarwal et al., 2021;Mei et al., 2020, Yuan et al 2022). It might be worth naming it, and pointing where exactly to find proofs of convergence under this condition. 

3- **Corollary 1** you show that this weak gradient domination holds **along the trajectory** so long as the method is monotonic and the function is convex. But here you need to adjust the assumption of Theorem 1 to assume weak domination over the trajectory, instead of globally as is written now.

4- Clarify if $f(x^*) =0$ is assumed for Theorem 2, I wasn't sure when reading. Though it is clear in Corollary 2 you assume f(x^*)=0.

5- Lemma 3, calling $\chi^2$ the noise of the stochastic gradients is confusing. Calling the "function noise" is much more accurate, as done in  Definition 4.13 in [Garrigos2023, Section 4.3.2]

6- I see a small (inconsequential) mistake in two of the proofs: "For normalized data, s.t. $\vert x\rvert =1$ the logistic regression loss is convex, is uniform smooth with $L = \lambda_{\max}(X^\top X) =1$ satisfies Assumption 2 with $L1=1$." This should be instead   $L \leq \lambda_{\max}(X^\top X) =n$ or   $L \leq (1/n) \lambda_{\max}(X^\top X) \leq 1$. 

7- I partly agree with Reviewer  8uuj, the title is a little bit misleading, in that, when I read the title, I was hoping for a rate of convergence of Armijo linear for the truly stochastic setting. By assuming interpolation, you are still in the stochastic setting, but it's the setting where SGD achieves the same rates as full batch gradient descent, so its *almost* like analysing the full batch case (but not really). A clearer title that would better fit the contributions would be

`` Armijo Line-search Makes Gradient Descent Go Fast: Rates for Full batch and Stochastic Interpolation''

But this is just a suggestion, the title you have now is ok.


[Yuki2024] Yuki Takezawa and Han Bao and Ryoma Sato and Kenta Niwa and Makoto Yamada, Parameter-free Clipped Gradient Descent Meets Polyak, Neurips 2024

[Vankov2025] Daniil Vankov and Anton Rodomanov and Angelia Nedich and Lalitha Sankar and Sebastian U Stich,  Optimizing \$(L\_0, L\_1)\$-Smooth Functions by Gradient Methods, 
ICLR, 2025

[Yuan et all 2022] ] Yuan, R., Gower, R. M., & Lazaric, A. (2022). A general sample complexity analysis of vanilla policy gradient. Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151, 3332–3380

[Agarwal et al., 2021] Agarwal, A., Kakade, S. M., Lee, J. D., & Mahajan, G. (2021). On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift. Journal of Machine Learning Research, 22(98), 1-76

[Mei et al., 2020] J Mei, C Xiao, C Szepesvari, D Schuurmans. On the global convergence rates of softmax policy gradient methods
 - ICML 2020

[Garrigos2022] Guillaume Garrigos, Robert M. Gower, Fabian Schaipp, Function Value Learning: Adaptive Learning Rates Based on the Polyak Stepsize and Function Splitting in ERM, 2022

[Garrigos2023] Handbook of Convergence Theorems for (Stochastic) Gradient Methods
Guillaume Garrigos, Robert M. Gower, 2023
Decision: Accept (poster)