Adaptive backtracking line search
Authors: Joao V. Cavalcanti
Laurent Lessard
Ashia C. Wilson
Venue: ICLR 2025 Poster (2025)
Keywords: Optimization
backtracking line search
Armijo condition
descent lemma
adaptive optimization methods
Primary area: optimization
TL;DR: We propose a way to make backtracking line search subroutines adaptive by adjusting step sizes using a variable factor that depends on the criterion enforced by the line search.

Abstract: Backtracking line search is foundational in numerical optimization. 
The basic idea is to adjust the step size of an algorithm by a {\em constant} factor until some chosen criterion (e.g. Armijo, Descent Lemma) is satisfied. 
We propose a novel way to adjust step sizes, replacing the constant factor used in regular backtracking with one that takes into account the degree to which the chosen criterion is violated, with no additional computational burden. This light-weight adjustment leads to significantly faster optimization, which we confirm by performing a variety of experiments on over fifteen real world datasets.
For convex problems, we prove adaptive backtracking requires no more adjustments to produce a feasible step size than regular backtracking does.
For nonconvex smooth problems, we prove adaptive backtracking enjoys the same guarantees of regular backtracking. %same lower bounds that step sizes produced by regular backtracking do.
Furthermore, we prove adaptive backtracking preserves the convergence rates of gradient descent and its accelerated variant.

Published as a conference paper at ICLR 2025
ADAPTIVE BACKTRACKING LINE SEARCH
Joao V. Cavalcanti', Laurent Lessard & Ashia C. Wilson' MIT, Northeastern University
[caval, ashia) @mit.edu, 1. d.lessard@norchaasttr..ee
ABSTRACT
Backtracking line search is foundational in numerical optimization. The basic idea is to adjust the step-size of an algorithm by a constant factor until some chosen criterion (e.g. Armijo, Descent Lemma) satisfied. We propose novel way to adjust step-sizes replacing the constant factor used in regular backtracking with one that takes into account the degree to which the chosen criterion is violated, with no additional computational burden. This light-weight adjustment leads to significantly faster optimization, which we confirm by performing a variety experiments over fifteen real world datasets. For convex problems, adaptive backtracking requires no more adjustments to produce a feasible step-size than regular back backtracking does. For nonconvex smooth problems, we prove adaptive backtracking enjoys the same guarantees of regular backtracking. Furthermore, we prove adaptive backtracking preserves the convergence rates of gradient descent and its accelerated variant.
prove
INTRODUCTION
We consider learning settings that can be posed the unconstrained optimization problem
arg arg min F(z).
(1)
xER
Typically, algorithms solve (1) iteratively, refining the current iterate dy by taking a step ogd4;
Tk + and+.
Here, a is the size of the step taken in the direction dg. Examples of iteration algorithms include gradient descent (GD), Newton's method, quasi-Newton methods (Moré Sorensen, 1982; Nocedal & Wright, 2006), Nesterov's 's accelerated gradient method (AGD) (Nesterov, 1983), adaptive gradient methods (Ruder, 2016) and their stochastic and coordinate-updatt variants (Boyd et al., 2011). To find an appropriate step-size, iterative algorithms typically call line search (LS) subroutine, which adopts some criterion and adjusts a tentative step-size until this criterion is satisfied. For many popular criteria, if the direction dę selected by the base algorithm is somewhat aligned with the gradient of F, then feasible step-size can be produced a finite number of updates by successively reducing an satisfied. The standard practice for this process, known
initial tentative step-size until the criteria as backtracking, is to multiply the tentative step-size by predefined constant factor to update it. We propose a simple alternative standard practice:
to adjust the step-size by an online variable factor that depends on the line search criterion violation.
While in principle this idea can be applied to many criteria, this paper focuses on illustrating it in the context of two line search criteria: the Armijo condition (Armijo, 1966), arguably the most popular example of such criteria, and the descent lemma (Bertsekas, 2016, proposition A.24) in the context of composite objectives (Beck & Teboulle, 2009). After motivating our choices of online adaptive prove factors, we show that they enjoy the best theoretical guarantees one can hope for. Moreover, that adaptive backtracking preserves the convergence rates of GD and AGD. To conclude, we present numerical experiments several real-world problems confirming that using online adaptive factors in line search subroutines can produce higher- qualityy step-sizes and significantly reduce the total number of function evaluations standard backtracking subroutines require.

---

Published as a conference paper at ICLR 2025
Contributions. Our contributions be summarized as follows.
Section 2, we propose a template for adaptive backtracking procedures with broad applicability.
In Section 2.4, we apply the template to enforce the Armijo condition and, in Section 3, present experiments on real-world problems showcasing that the adaptive subroutine outperforms regular backtracking and improves the performance of standard baseline optimization algorithms.
In Section 2.5, we apply the template on proximal- -aaed algorithms to satisfy the descent lemma and present more real-world problems in Section illustrating that the adaptive subroutine improves the performance of FISTA.
For both subroutines, in Section we prove that for convex problems, adaptive backtracking takes more function evaluations to terminate than regular backtracking in any single iteration. We also give global theoretical guarantees for adaptive backtracking in nonconvex smooth problems, which match those of regular backtracking. Furthermore, the convergence rates of gradient descent and its accelerated variant. In particular, the proof of accelerated convergence based on a novel technical argument, to the best of our knowledge.
show that adaptive backtracking preserves
ADAPTIVE BACKTRACKING
2.1
LINE SEARCH: CRITERIA AND SEARCH PROCEDURES
Every line search subroutine can be decomposed into the criteria that it enforces and the procedure to return feasible step-size. We now briefly discuss each component and provide examples.
Criteria. The most popular of line search criteria is the Armijo condition (Armijo, 1966), which requires that the objective function sufficiently decrease along consecutive iterates. Other popular sets of criteria are the weak and strong Wolfe conditions (Wolfe, 1969), which comprise the Armijo condition and an additional curvature condition that prevents excessively small step-sizes and induces step-sizes for which the objective function decreases even more. In contrast, nonmonotone criteria (Grippo al., 1986; Zhang Hager, 2004) only require that some aggregate metric of the objective function values (c.g., an exponential moving average) decrease along consecutive iterates.
Search procedures. The second component of line search subroutine is the procedure that finds step-size satisfying the target criteria. For example, Wolfe line search is often implemented by bracketing procedures based on polynomial interpolation (Nocedal & Wright, 2006, pp. 60-61). In contrast, several criteria consisting in single condition such Armijo and nonmonotone, are provably satisfied by sufficiently small step-sizes. For them, the standard procedure to compute step- sizes fixes an initial tentative step-size and then consecutively multiplies it by constant p (0, 1) until the criteria are satisfied. This procedure is generally known as backtracking line search (BLS).
2.2 ADAPTIVE BACKTRACKING
BLS often enforces inequality that is affine in the step-size. In this case, BLS can be reformulated as computing v(0x), ), which is less than when the line search criterion evaluated at the tentative step- size og is violated, and then scaling 0g by factor until v(ag) is greater than 1. BLS (Algorithm employs a fixed factor E (0, 1). We propose a simple modification of this procedure:
to replace p with an adaptive factor p(v(ax)) chosen as a nontrivial function of the violation v(ax).
Algorithm Backtracking Line Search
Algorithm Adaptive Backtracking Line Search
Input: op > 0, v: -4- IR, p E (0, 1)
Input: to > 0, v: R4- R. p: RR (0, 1)
Output: ag
Output: ayk
1: < Org
I: 0g +
2: while v(ax) < do
while v((x)) do
3:
t- p- Or
3: ag <- p(v(ax))
4: end while
4: end while
2

---

Published as a conference paper at ICLR 2025
2.3 RELATED WORK
Backtracking is simple and effective alternative to exact line search subroutines (Nocedal & Wright, 2006, Ch. 3), which helps explain why it remains a popular procedure to enforce various line search criteria (Beck & Teboulle, 2009; Nesterov, 2013; Vaswani et al., 2019b; Galli et al., 2023; Aujol al., 2024). Notwithstanding, there no standard practice to select the adjustment factor p. but rather some rough guidelines suggesting that the parameter p "is often chosen to be between 0.1 (which corresponds to a very crude search) and 0.8 (which corresponds to a less crude search)" (Boyd & Vandenberghe, 2004, 466) and that it "is usually chosen from 1/2 to 1/10, depending on the confidence we have on the quality of the initial step-size" (Bertsekas, 2016, p. 36). Indeed, we find that varies somewhat arbitrarily depending enforced by backtracking. For example, p 0.8 is used in (Aujol et al., 2024) to enforce the descent lemma, while P 0.5 is used in (Vaswani et al., 2019b) to enforce the Armijo conditions. With that in mind, in our experimental validation, we compare our proposed adaptive subroutine with regular backtracking for several values of p. Our goal is to exhibit compelling evidence for simple alternative to a classic method that remains popular, rather than champion a particular line search subroutine. Accordingly, we do not compare against subroutines that do not enforce similar line search criteria, such as (Fridovich-Ken) Keil & Recht, 2020; Orseau & Hutter, 2023), nor subroutines that do not release code (de Oliveira & Takahashi, 2021). Likewise, we leave recent twists on backtracking, such as (Truong & Nguyen, 2021; Calatroni & Chambolle, 2019; Rebegoldi & Calatroni, 2022), for future work, since these methods could in principle also benefit from adaptive adjustments (see Section 5.)
empirical performance and the conditions
2.4
CASE STUDY: ARMIJO CONDITION
The most popular criterion used in line search is the Armijo condition (Armijo, 1966), which is specified by hyperparameter c E (0, 1) and requires sufficient decrease the objective function:
Fxxx andd)) F((xa) S au (VF())) de)-
For the Armijo condition, the direction dę is usually assumed to be a descent direction:
Assumption (descent direction). The direction dę satisfies (V Fxxx), de) < O.
We define the violation of (3) as
F(x + aadd)) - F(xx)
v(ax)=
(4a)
C. c- (V
du)
Under Assumption 1, (3) can be written as v(ax) 2 1. To account for the information conveyed by (3) when violated, we choose the corresponding adaptive geometric factor p(v(ax))
1-c p(v(au)) max (c. (c.
(4b)
where 0 is small factor that prevents occasional numerical errors in v(ax) from spreading to p(v(ax)). Although (4b) is parameterized by e and p. for each method we fix their values on all experiments, effectively making Algorithm 2 parameter free. We our adaptive BLS procedure to find suitable step-sizes for three standard base methods: gradient descent (GD), Nesterov's accelerated gradient descent (AGD) (Nesterov, 1983) and Adagrad (Duchi et al., 2011). The standard implementations that we use for these algorithms are given in Appendix C. Incorporating line search into GD and Adagrad is straightforward, but the case of AGD merits further comment.
Backtracking and AGD. Unlike GD, AGD is not necessarily a monotone method in the sense that Fœx + axd)) < F(xx) need not hold. But AGD is a multistep method, one being GD step, for which line search can help to compute a step-size or, cquivalently, to estimate the Lipschitz constant L.. If the estimate of T. satisfies (3) with e = 1/2 and is increasingly multiplied by lower bounded positive geometric factor, then AGD with line search enjoys essentially the same theoretical guarantees of AGD tuned with constant parameters. We also consider AGD with memoryless line search with fixed predetermined initial step-sizes. Then, unless some variant such as Scheinberg et al. (2014) is used, the theoretical guarantees are not necessarily preserved when AGD combined with memoryles, line search. For some values of p, however, we find empirically that not only does the resulting method converge, but it does so much faster than the monotone line search variant, which in turn typically converges faster than AGD tuned with pre-computed estimate L. (see Appendix D.1.)
3

---

Published as a conference paper at ICLR 2025
2.5 CASE STUDY: DESCENT LEMMA
A standard assumption in the analysis and design of several optimization algorithms is that gradients are siscchitz-mmotth, which implies (Nesterov, 2018, Thm. 2.1.5.) that there is some such that
f(v) S f()) + (Vf(z). x) l ==1?
Vx, y-
(5)
Inequality (5) is commonly known as the descent lemma (Bertsekas, 2016). In particular, it is commonly assumed (5) holds for algorithms that solve problems with composite objective functions F= f+Ø, where f is Lipschitz-smooti convex and vú is continuous, possibly nonsmooth, convex. A prototypical example of such algorithm is FISTA (Beck & Teboulle, 2009), which is extension of Nesterov's AGD to composite problems (for details see Appendix C.) FISTA assumes that produces points уı and Pox (yx) satisfying (5) applied to I with x ys and y = Pos (yte), where pa denotes the proximal operator (Parikh & Boyd, 2014) parameterized by a > and defined by
Po Pa(v)= = arg min (xxx) +
|| -v -w- ((-av/Gw)) 20
(6)
In practice, a 1/L seldom known for given f. and FISTA estimates it with some on by checking
F(Pac (vk)) - (1kk + (Vx( Pa. (yx) yk)
1
IlPa (Uk) - yx + (Paa (Uk)).
(7)
200
Since (7) holds for any a < I/L, an estimate ag can precomputed from analytical upper bounds on L for particular cases of f. but these bounds tend to be overly conservative and can lead to poor performance. better alternative, adopted by FISTA and many methods (Nesterov, 2013; Scheinberg et al., 2014) 4), is to backtrack: reduce O% by some constant factor < 1 until (7) holds.
We define the violation of Eq. (7)
v((x)= = 201 Paa (8k) - wxll? (f((pa - f((k) - (V (yk) -kk))
(8a)
and the corresponding adaptive factor as:
p(v(ar)) == po(aa).
(8b)
In experiments below, we use (8h) find suitable step-sizes for FISTA, with fixed p < value.
3 EMPIRICAL PERFORMANCE
We present four experiments illustrating different ways and scenarios in which our adaptive backtrack- ing line search (ABLS)) subroutine (Algorithm 2) can outperform regular backtracking (Algorithm 1).
3.1 CONVEX OBJECTIVE: LOGISTIC REGRESSION + ARMIJO
First, we consider the logistic regression objective with Le regularization, defined by
1 n Σ (Ur log(o(aTT))) + vz) v:) log(1 - aaa x))) + ? |x|13
F(x)
(9)
where (2) = 1/(1 + exp(-2)) is the sigmoid function, 7 0 and (A, b;) E Rd {0, 1} ob- servations from a given dataset. For each dataset, T-= Amaxe (AT A) (4n) provides an upper bound on the true Lipschitz parameter of the first term in (9), with which fix 7 I./(10n) and the step-size of gradient descent to 1/(L + 77). In all experiments, the initial point x0 is the origin as is standard.
Result Summary. A succinet summary of our results contained in Table and Appendix D is that
across datasets and step-size initializations considered, adaptive backtracking is more robust than regular backtracking and often leads to significant improvements with respect base methods.
4

---

Published as a conference paper at ICLR 2025
Backtracking Line Search (BLSS
Adaptive BLS (ABLS)
P = 0.2
P = 0.3 #VF
P
Method
Dataset
#1
#VS
ET [s]
#
ET [s]
#1
#V5
ET [s]
gain
GD
ADULT
148597.2
32582.0
1319.0
74258.5
18749.0
694.7
37296.0
13583.8
370.0
46.7%
G_SCALE
58488.5
18252.2
3050,4
65429.2
17111.5
3059.7
25917.2
11700.5
1607.0
47.3%
MNIST
148469.8
41726.2
10986.4
207786.8
46475.5
13474.8
52616.5
22385.8
4841.9
55.9%
MUSHROOMS
14170.5
6507.2
31.7
14800.8
6628.5
33.9
7611.0
3693.8
17.3
45.5%
PHISHING
33388.2
8059.8
63.0
7938.5
62.4
16543.2
PROTEIN
28011.0
13260.5
4481.6
35733.2
14868.8 88
5282.0
27656.0
13207.2
4137.4
7,7%
6721.5
3139.0
6156.8
2972.8
6192.2
3024.8
7.9
(5.4%))
0.5
0.6
Method
Dataset
#1
#VS
ET [6]
#1
#VI
ET [s]
#1
#V
ET [6]
gain
AGD
ADULT
17288.8
2014.2
116.6
49331.2
3806.2
247.0
7999.0
2275.0
49.2
52.5%
G_SCALE
3580.2
592.5
114.9
18530.8
1964.0
512.9
2204.5
728.5
84.1
26.8%
MNIST
8934.2
1524.5
452.3
14365,8
1846.5
643.7
4943.2
1666.2
283.0
37.4%
MUSHROOMS
1100.5
372.2
1.7
1146.8
367.8
850.0
376.2
1.4
15.5%
PHISHING
6763.2
944.2
9.1
8344.2
944.8
8.6
3699.0
1058.0
4.0
53.6%
PROTEIN
2865.0
1232.2
396.3
3397.5
1272.5
346.5
2743.2
1257.0
291.6
15.8%
WEB-1
651.8
208.5
0.6
699.8
202.2
0.5
519.2
217.8
0.4
3,3%
0.2
0.3
0.3
Method
Dalaset
#-
#V
[s]
#1
#VF
#1
#V
gain
Adagrad
ADULT
124102.0
20001.0
699.5
145159.8
19789.8
746.5
27179.0
8000.5
178.8
74.4%
G_BCALE
274023.2
7396.5
361852.0
9740.9
84201.0
17176.2
MNIST
86240.5
13843.8
3921.2
990221.8
14760.8
4377.22
12366.2
3521.8
679.5
82.7 %
MUSHROOMS
7794.8
1967.8
7239.5
1693.0
3751.5
1446.0
PHISHING
74737.5
15833.5
68.9
117564.0
20001.0
96.4
18053.0
6375.0
19.4
71.8%
6103.0
809.2
420.6
4040.2
429.0
257.9
1845.8
446.5
164.4
36.2%
WEB-1
4384.2
1027.0
2,9
3857.8
745.2
2.5
1726.5
568.8
1.3
50.1 %
Table 1: Logistic regression. # and f denote the number of function and gradient evaluations and ET refers elapsed time in seconds. The gain is given by 1- (ET of ABLS) (ET) of BLS) with the best ET for BLS across p in each experiment, which is bolded. We ran each BLS experiment with grid of four p's and present the best two in the table. The gain for GD on WEB- is colored orange because although ABLS terminated before the hest performing BLS variant, it required more function and gradient evaluations. This anomaly can be attributed to the relatively small ET for this problem.
Datasets and methods. We take observations from seven datasets, whose details can be found in Appendix D. We consider GD, AGD, and Adagrad, described in Appendix C, with BLS for p {0.2, 0.3, 0.5, 0.6} and our ABLS with pre-set p.
Initialization. We set the starting point xo as the origin and fix e = 0.01 in (4b) on all experiments. We also fix p. but change it according to the base method. For more details, see Appendix D.
Evaluation. We run all methods for long enough to produce solutions with designated precision, then average various metrics over different initial step-sizes. For more details, see Appendix D. All experiments were run on a supercomputer cluster containing Intel Xeon Platinum 8260 and Intel Xeon Gold 6248 CPUs Reuther et al. (2018).
Remarks. Table shows that ABLS significantly outperform BLS. For GD and Adagrad, ABLS variants outperforms BLS for almost every combination of p and og by saving function evaluations and returning better step-sizes, which speed up convergence. Fig. 1 illustrates this point by showing how the suboptimality gap evolves with time for the baseline GD, its ABLS variant and BLS variants for two choices of initial step-size. In particular, increasing the initial step-size helps BLS in some datasets but not in others. Fig. shows a similar trend for the case of AGD. In general, ABLS is more robust to the choice of initial step-size and that is the main reason why the ABLS variant of AGD outperforms its BLS counterparts. Appendix D.2, Figs. 14 and 15 show the corresponding step-sizes. Initially, ABLS returns smaller GD step-sizes than BLS, but this trend quickly reverses. plausible explanation is that BLS returns the largest step-sizes that satisfy (3), within a factor of p. If the step-sizes are excessively large initially, they can lead to worse optimization paths (e.g.. more zig- sgg-zagging.. For AGD, the step-sizes follow a similar trend initially, but then the adaptive step- size seems to converge while the regular step-sizes not always do. This can be indicative of another shortcoming of regular backtracking, namely that it can only return step-sizes that are powers of times the initial step-size, in contrast with adaptive backtracking.
5

---

Published as a conference paper at ICLR 2025
base inc (GD)
(0.3, 1e2)
reg (0.3, 1c4)
ad (0.3, 1c4)
10"
gisette
10-
104
protein
10--
10-3
10->
10
10
10
0
1000
2000 time [s]
3000
4000
0
5000 10000 15000 time [s]
0
2000 4000 time [s]
6000
Figure I: Baseline: GD with constant au = 1/L; reg (p, 8) and ad (p,3): GD with, respectively, regular and adaptive memoryless BLS parameterized by p and og B/L. L.
baseline (AGD)
reg (0.6, lel)
reg (0.6, 1e2)
ad [0.9. 1e2)
10a
gisette_5com scale
10"
MNIST
protein
10-5
10-5
10
10
50 time [s]
time [5]
time [s]
Baseline: AGD with constant as 1/L; reg (p, 3) and (p. B): AGD with, respectively, regular and adaptive memoryless BLS parameterized by and og = B/L.
Figure 2:
3.2 CONVEX OBJECTIVE: LINEAR INVERSE PROBLEMS + DESCENT LEMMA
The goal of linear inverse problem is to recover the sparse signal x from a noisy measurement model y = Az where A Rexd and y R" are known, and is unknown noise. The problem of estimating x is typically posed as Lasso objective (Santosa & Symes, 1986; Tibshirani, 1996)
1 |A -1 y12 + A||=||1.
F(x)
Datasets. We take observations from eight datasets, see Appendix E for details.
Methods. We consider FISTA (Beck & Teboulle, 2009) (Algorithm 6) and BLS variants. For BLS, p = (1/2, 1/5} and & = 1/1.1 .9 for ABLS, mirroring the choice for AGD above. All BLS methods start with the same initial Lipschitz constant estimate increase it accordingly.
Initialization. For each dataset, we empirically find values of ap 1/T. T-g around which backtracking becomes active, and then increase them successively (values reported on Appendix E.)
Results Summary. The ABLS variant FISTA outperforms its BLS counterparts across all datasets tested. Moreover, the best value of for BLS changes from one dataset the other. Since the Lipschitz constant estimate is monotone, function evaluations vary little across methods and have small impact on performance. Nevertheless, ABLS requires fewer function evaluations for all datasets.
3.3 NONCONVEX OBJECTIVE: ROSENBROCK ARMIJ
We consider the classical nonconvex problem given by the Rosenbrock objective function F(u, u) 100(u - 02 + (1 2 We use the origin as the initial point and 0.1 as the initial step-size. Fig. shows the optimization paths for BLS and ABLS memoryless variants of GD and AGD after 1000

---

Published as a conference paper at ICLR 2025
Backtracking Line Search (BLS)
Adaptive BLS (ABLS)
0.5
0.3
0.9
Method
Dataset
A#f
#V,
A#
#V
A#f
#VF
gain
FISTA
DIGITS
15.5
28282.25
34730.75
4.75
16756
40.8%
IRAS
10.75
726.25
7
816.5
710
2.2%
OLIVETTI
10
242709.5
6,25
246827.75
2
2129330.55
12.3%
LFW
26.25
49093.75
49014.55
45070.75
8.0%
SPEAR3
13.25
328328.75
506308.5
255417..5
22.2%
SPEARIO
44.75
18691
29.75
19992.75
8
15128
19.1% %
SPARCO3
27.75
251
WINE
48
529333.25
27.75
564293.75
8.5
472527
10.7%
Table 2: Linear inverse problem. #VS and A# denote the number of gradient and excess function evaluations (total function evaluations minus times total iterations). The gain given by ( of ABLS)/(# of BLS) with the best ET for BLS across in each dataset (bolded.) We run each BLS experiment with three p's and present the best in the table. ABLS reached the desired precision in all testpoints while the asterisk on LFW* indicates BLS did not in at least one testpoint.
iterations, using p 0.3 and p 0.9, respectively. We see that the ABLS variants achieve better losses, requiring far fewer function evaluations and less time to do so.
Method
#1
loss
ET [s]
GD+BLS
4992
7,30c-03
1.04c-1
GD+ABLS
2754
7.21c-12
9.98e-2
AGD+BLS
42263
9.25e-11
5.59e-1
AGD+ABLS
2991
4.01e-13
6.40e-2
(a) GD
(b) AGD
(c)
Figure 3: Performance of GD and AGD regular (red) and adaptive (blue) BLS variants on Rosenbrock. "loss" refers to the final loss after 1000 iterations.
3.4 NONCONVEX OBJECTIVE: MATRIX FACTORIZATION + ARMIJO
Lastly, we consider the nonconvex problem of matrix factorization, defined by the objective F(U, V) = L ll. where A Rm E RR V TRa and < min mui We take A from the MovieLens 100K dataset (Harper & Konstan, 2015) and consider three rank values r E {10, 20, 30) (see Appendix F for further details and full plots.)
For this experiment replicate the initialization and evaluation methodologies of Section 3.1, except we disconsider Adagrad, and pick different values for initial step-sizes, {0.05, 0.5, 5, 50). and p. Namely, let {0.2, 0.3, 0.5, 0.6} for the BLS variants, but fix p 0.3 and p 0.9 for the ABLS GD and AGD variants, respectively. Table 3 summarizes the results for ABLS and the top two BL.S variants. Once again, the best value of p for BLS is inconsistent: o = 0.3 for ranks 10 and 20 but = 0.2 for rank 30. ABLS requires significantly fewer gradient and function evaluations than the top BLS variant does, which leads considerable gains in time to achieve the desired precision.
MOTIVATION AND THEORETICAL RESULTS
In this section, motivate choices of adaptive factors and characterize them theoretically.
The particular choices of adaptive factors were made with two goals in mind: generate more aggressive backtracking factors to save function evaluations and guarantee reasonably large step-sizes to achieve fast convergence. To meet our first goal, p(v(as) E (0, p) must hold. Indeed, if (3) is violated, then v((x) because de is assumed descent direction, where is defined by (4a). So, if in addition

---

Published as a conference paper at ICLR 2025
Backtracking Line Search
Adaptive BLS (ABLS)
0.2
0.3
Method
Rank
#
#Vf
ET [S]
#
#VF
ET [8]
#
#VS
ET [s]
gain
GD
10
39960.0
$683.5
1034.5
33531.8
4897.8
999.5
52075.8
16318
64.8
93.5%
127480.2
18734.5
1153.2
111322.0
16109.2
1010,9
377111.8
5133.0
170.9
83.1%
231170.5
35639.8
2035.5
394472.2
50001.0
4195.1
681952.0
14802.8
669.2
67.1%
0.3
= 0.5
0.9
AGD
362029.7
21909.3
2377.0
44873.0
6198.3
379.4
22707.7
6663.7
172.0
54.7%
479432.0
35672.0
2987.9
491753.3
33523.3
3588.6
80720.3
24588.7
738.0
75.3%
30
357885.7
39234.3
2187.8
478084.3
42985.3
5157.0
95040.0
27454.0
855.1
60.9%
Table 3:
Backtracking for matrix factorization. #f and #Vf denote the number of function and gradient evaluations and ET refers elapsed time seconds. The gain is given by 1 (ET of ABLS)/(ET of BLS) with the best ET for BLS across in each experiment, which is bolded.
E (0, p) in (4b), then ((v(a))) < p. To meet the second goal, the returned step-size must be non- trivially lower bounded. To this end, in Section 4.2 we show that the objective function is Lipschitz- smooth, then ABLS returns a step-size on par with the greatest step-size that is guaranteed to satisfy (3). For now, we note that if (3) violated, then c v((a)) ) > O, since a (0, 1) by assumption. Thus, p(v(ou)) is bounded away from zero. Moreover, that same bound applies to BLS. Similar conclusions can be reached the BLS criterion is (7) and f and e are chosen as (8b) and (8a).
4.1 THE SCOPE OF THEORETICAL GUARANTEES FOR A BACKTRACKING SUBROUTINE
Before characterizing adaptive backtracking theoretically, we state a theoretical bound on how well a general line search procedure can do relative to regular backtracking. Then, we state three further facts that substantiate why comparing line search procures is hard. These statements are consequences of simple examples described in Appendix B.
The fundamental obstacle we face theoretically comparing adaptive backtracking, or any other line search procedure, with regular backtracking is described by Example 1, which shows that
no line search procedure can be provably better than regular backtracking to enforce any set of line search criteria that includes the Armijo condition or the descent lemma, for any class of functions that includes quadratics.
We compare line search procedures on the basis of the number of adjustments to return feasible step-size and the length of the returned step-size. To establish this fact, in Appendix B.1 we construct a simple scalar quadratics example in which regular backtracking returns the greatest feasible step- size after one adjustment and furthermore this step-size leads the minimum. Also in Appendix B.1, we present a similar example for the descent lemma
In general, comparing line search procedures is challenging because different procedures return different step-sizes, which lead to different optimization paths. For example, procedure that reduces step-sizes more in each adjustment need not require fewer adjustments (function evaluations) overall than procedure that reduces step sizes less because each procedure leads to different sequence of iterates. In fact, comparison is challenging even for a single backtracking call because:
1. the step-size returned by backtracking is not monotone p, even for convex problems.
2. For nonconvex problems, given step-sizes a' and with a' ar, a being feasible does not imply a' is also feasible.
3. For nonconvex problems, decreasing p may increase the number of criteria evaluations required to compute feasible step-size.
Example establishes the first fact and Example establishes the second and third facts.
With the above in mind, in the following we provide the best set of performance guarantees that one hope for. Namely, show that adaptive backtracking requires more function evaluations
8

---

Published as a conference paper at ICLR 2025
than regular backtracking to return feasible step-size, and that the step-size lower bounds for the two procedures are the same, which leads to the same global convergence rate results.
4.2 THEORETICAL RESULTS
In this subsection, we present theoretical results regarding regular and adaptive backtracking. Several additional convergence results and full proofs can be found in Appendix B.
Convex problems. We show that only the first fact above holds for convex problems, which expands the extent to which two backtracking subroutines can be compared.
Proposition 1. Let F be convex differentiable. Given a point Tig, a direction dg and a step-size ag > 0 satisfying (3) for some c, then Ik, dy and 04.. also satisfy for any di (0,
The following proposition refers to "compatible inputs." By this mean:
Definition 1 (Compatibility). The inputs to Algorithms and 2 are said to be compatible if oa, C, coincide and the input ý to Algorithm 2 is parameterized by the same p that Algorithm takes as input.
Proposition 2. Let F be convex differentiable. Fixing all other inputs, the number of function evaluations that Algorithm and Algorithm 2 take to return a feasible step-size is nondecreasing in the input p. Moreover, given compatible inputs with descent direction and c < p. Algorithm 2 takes no more function evaluations to return feasible step-size than Algorithm I does.
Nonconvex problems. For convex problems, we were able to compare the number of times regular and adaptive backtracking must evaluate their criteria in order to return single feasible step-size. But what really matters is the total number of criteria evaluations up to a given iteration. We bound this number for general nonconvex problems, hinging on the following properties.'
Definition 2 (Smoothness). A function F is said to be Lipschitz-smoott (5) holds for some L >> 0.
Definition 3 (Gradient related). The directions da are said to be gradient related if there are Ci > 0
and 02 > O such that (V F(r), -4) 2 ea F (xx))) l2 and ||dg|| S e2) e (x(x)) Ib. for all k 2 0.
Assumption 2. We assume F is Lipschitz-smonn smooth and d2 are gradient related.
Gradient relatedness ensures that dg is not "too large" "too small" with respect to (Zz))) and that the angle between du and V F((x)) is not "too close" to being perpendicular (Bertsekas, 2016, p. 41). Together with e₁ and 02, the Lipschitz constant T. and Armijo constant define step-size threshold ā = 2c1 (1 c/LLc below which (3) holds. This quamtity is central in the following result.
Informal Theorem (Armijo). Let F be Lipschitz- smooth and dy gradient related. Given compatible imputs, if p and û are chosen as (4), then Algorithms I and 2 share the same bounds on the total number of backtracking criteria evaluations up to any iteration. If og is received as the initial step-size input at iteration + 1 for all k 2 then they evaluate (3) at most [log, (a/p(a/o))) + 1+ times up to iteration k. If. on the other hand, Ogg is received as the initial step-size input at every iteration, then they evaluate (3) at most k(llog, (ā/ox)] + 1) times up to iteration k. Moreover, Algorithms and 2 always return a step-size ag such that a 2 min,aa., pā).
Informal Theorem (Descent lemma). Let f be Lipschitz-smooth convex and let sb be continuous convex. Also, suppose v and ğ are chosen as (8a) and (8b). If E (0, 1/L.), then (7) holds for all yk- If Algorithmms I and 2 receive Org as the initial step-size input iteration k+1,, then they evaluate (7) at most [ogg (1/LL))] +1 1+ k times up to iteration k. If, on the other hand, Algorithms I and 2 receive oo as the initial step-size imput in every iteration, then they evaluate (7) at most kc b([[og, (1/Lo)) +1) times up to iteration k. Moreover, they return a feasible step-size Org such that Og 2 min {co, L.).
5 FUTURE WORK: FURTHER APPLICATIONS, EXTENSIONS AND LIMITATIONS
Adaptive backtracking is a general idea that can be broadly applied in a variety of settings. Our goal in this paper was rigorously validate it in classical machine learning and optimization problems. This section outlines several promising directions for future work and speculate about potential limitations.
Instead of the usual condition that FF()) Fly)ll S -.] hold for all v, y. adopt the equivalent (Nesterov, 2018, Thm. 1.5. condition (5) the definition of Tipshhiiz-smoottnnss for the sake of convenience.

---

Published as a conference paper at ICLR 2025
5.1 FURTHER APPLICATIONS AND EXTENSIONS
Stochastic line search. machine learning, models such as aver-parameterized neural networks are sufficiently expressive to interpolate immense datasets (Zhang et al., 2016; Ma et al., 2018). Inter- polation provides theoretical foundation for the stochastic line search (SLS) proposed by Vaswani et al. (2019b), which enforces the Armijo condition on the training mini-batches. In the same vein, Galli et al. (2023) replaced the Armijo condition in SLS with a nonmonotone criterion and used Polyak's step-size to devise initial step-size heuristic, obtaining the Polyak Nonmonotone Stochas- tic (PoNoS) method. Below, we reproduce experiment from (Galli et al., 2023) to demonstrate the potential of applying ABLS in combination with stochastic line search in the interpolating regime. Fig. 4 shows that combining ABLS with PoNoS leads to good test accuracy in fewer epochs (details in Appendix A.) We defer fully developing this application future work.
0.99
10a
accuracy
10
0.98-
SLS
PoNoS
train
Adam SPS
ABLS
10-5
0.96
38
56
75
56
75
epoch
epoch
Figure 4: MLP trained on MNIST with different algorithms.
Additional line search criteria. Adaptive backtracking may be useful to enforce other conditions that are affine in the step-size. A prominent candidate are the Goldstein conditions (Goldstein & Price, 1967), which comprise two inequalities that are affine in the step-size. Nonmonotone line search criteria (Grippo et al., 1986; Zhang & Hager, 2004) also offer several candidates.
Additional algorithms and increasing step-sizes. In this paper, experimented with increasing step-sizes through memoryless line search, where the initial step-size is fixed for every iteration, but other schemes are possible. For example, adaptive adjustments can also be used to increase step- sizes. In addition, adaptive backtracking can replace regular backtracking in line search methods that increase the current step-size and then use as the initial step-size, such as the two-way method (Truong & Nguyen, 2021) and FISTA variants (Scheinberg et al., 2014; Calatroni & Chambolle, 2019; Rebegoldi & Calatroni, 2022). Also, it would be interesting to see how adaptive backtracking works together with schemes that handle problems where the strong convexity constant is unknown, namely restarting schemes Becker al. (2011); O' O'Donoghue & Candès (2015); Aujol al. (2024). Finally, we note that the violation of a condition can also be used indirectly to adjust step-sizes, for example to pick the degree to which fixed p is exponentiated, saving backtracking cycles.
5.2 LIMITATIONS
The weak and strong Wolfe conditions (Wolfe, 1969) are not affine in the step-size and are not satisfied by arbitrarily small step-sizes. Hence, Wolfe conditions are not enforced by backtracking (e.g., Nocedal & Wright (2006, pp. 60-61)) and it is unclear how to find analogous adaptive schemes. In turn, quasi-Newtor methods. which often must enforce Wolfe conditions to guarantee global convergence, may not be suitable candidates for adaptive line search subroutines. In reality, the role of line search for these methods is to guarantee they converge globally rather than finding the "right" step-size, since they work with unit step-size locally. Hence, only few adjustments may be necessary. The same applics to Newton's method and the Barzilai-Borwein method (Barzilai & Borwein, 1988).
It is also unclear if adaptive adjustments can be useful for more general stochastic line search methods that do not rely on the interpolation property (Cartis & Scheinberg, 2017; Paquette & Scheinberg, 2020). Instead, they resample function and gradient mini-batches in every loop, whether sufficient descent condition is violated or not. But the information conveyed by the violation for one sample need not be relevant to satisfy the same condition with different sample, which poses potential limitation.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
L. Armijo. Minimization of functions having lipschitz continuous first partial derivatives, Pac. J. Math., 16(1):1-3, 1966.
J.-F. Aujol, L. Calatroni, C. Dossal, H. Labarrière, and A. Rondepierre. Parameter-free fista by adaptive restart and backtracking, SIAM Journal on Optimization, 34(4):3259-3285 2024.
Barzilai and J. Borwein. Two-point step size gradient methods. IMA J. Numer. 8(1):141-113 1988.
A. Beck and M. Teboulle. fast iterative shrinkage-thressoolding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences, 2(1): 2009.
B. Becker and Kohavi R. Adult. UCI Machine Learning Repository, 1996.
S. R. Becker, E. J. Candès, and M. C. Grant. Templates for convex cone problems with applications sparse signal recovery. Mathematical Programming Compulation, 3(2): 2011.
D. Bertsekas. Nonlinear Programming. Athena Scientific, 3rd edition, 2016.
S. Boyd and L. Vandenberghe. Convex optimization. Cambridge university press, 2004.
S. Boyd, N. Parikh, H. Chu, B. Peleato, and J. Eckstein. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine learning, 3(1):1-122, 2011.
I. Calatroni and A. Chambolle. Backtracking strategies for accelerated descent methods with smooth composite objectives. SIAM Journal on Optimization, 29(3):1772-177) 2019.
C. Cartis and K. Scheinberg. Global convergence rate analysis of unconstrained optimization methods based probabilistic models. Math. Program., 169:337-375, 2017. 2017.
R. Caruana, T. Joachims, and Backstrom. Kdd-cup 2004: Results and analysis. SIGKDD Explorations Newsletter, 6(2):95-108, 2004.
C.-C. Chang and C.-J. Lin. LIBSVM: a library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2(27):1-27, 2011.
I. F. D. de Oliveira and R. H. C. Takahashi. Efficient solvers for armijo's 's backtracking problem, 2021.
Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12:2121-2159, 2011.
Fridovich-Keil and Recht. Approximately exact line search, 2020.
L. Galli, H. Rauhut, and M. Schmidt. Dont be so monotone: Relaxing stochastic line search in over- parameterized models. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 34752-34764, Curran Associates, Inc., 2023.
A. Goldstein and J. Price. An effective algorithm for minimization. Numer: Math., 10:184-189, 1967.
L. Grippo, F. Lampariello, and S. Lucidi. A nonmonotone line search technique for newton's 's method. SIAM journal on Numerical Analysis, 23(4):707-716, 1986.
M.F. Harper and J.A. Konstan. The movielens datasets: History and context. ACM Transactions on Interactive Intelligent Systems (TiS), 5(4), 2015.
D.P. Kingma and J.L. Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICML). 2015.
Y. LeCun, C. Cortes, and C.J.C. Burges. The MNIST database of handwritten digits. Proceedings of the IEEF, 86(1 11:2278-2233 2324, 1998.

---

Published as a conference paper at ICLR 2025
N. Loizou, S. Vaswani, I. H. Laradji, and S. Lacoste-Julien. Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence, International Conference on Artificial Intelligence and Statistics, pp. 1306-1311 2021.
D.A. Lorenz, M.E. Pfetsch, A.M. Tillmann, and C. Kruschel. SPEAR: Sparse exact and approximate recovery. https: wwwopt mat hemat ikk tu www.ddaaasaaaaaao de spear/. 2014.
Ma, R. Bassily, and M. Belkin. The power of interpolation: Understanding the effectiveness of sgd in modern over wer-parametrrzed learning. In International Conference Machine Learning (ICML), 2018.
J. Moré and D. C. Sorensen. Newton's method. Technical report, Argonne National Lab., IL (USA), 1982.
Y. Nesterov. A method for unconstrained convex minimization problem with the rate of convergence o(1/k2). Doklady AN SSSR, 269:543-547, 1983.
Y. Nesterov. Gradient methods for minimizing composite functions. Math. Program. Ser. B, 140: 125-161, 2013.
Y. Nesterov. Lectures on convex optimization, volume 137. Springer, 2018.
Nocedal and Wright. Numerical Optimization. Springer Science & Business Media, 2006.
L. Orseau and M. Hutter. Line search for convex minimization, 2023.
B. O' Donoghue and E. J. Candès. Adaptive restart for accelerated gradient schemes. Foundations of computational mathematics, 153))775--332, 2015.
C. Paquette and K. Scheinberg. A stochastic line search method with expected complexity analysis. SIAM Journal on Optimization, 30(1):349-376, 2020.
N. Parikh and S. Boyd. Proximal algorithms. Foundations and Trends in Optimization, 1(3):127-339, 2014.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in python. JMLR, pp. 2825-2830, 2011.
Platt. Fast training of support vector machines using sequential minimal optimization. In Advances in Kernel Methods- Support Vector Learning. MIT Press, January 1998.
Rebegoldi and I.. Calatroni. Scaled, inexact, and adaptive generalized fista for strongly convex optimization. SIAM Journal on Optimization, 32(3):2428-22 2459, 2022.
A. Reuther, Kepner, C. Byun, S. Samsi, W. Arcand, D. Bestor, B. Bergeron, V. Gadepally, M. Houle, M. Hubbell, M. Jones, A. Klein, I.. Milechin, J. Mullen, A. Prout, A. Rosa, C. Yee, and P. Michaleas. Interactive supercomputing on 40,000 cores for machine learning and data analysis. In 2018 IEEE High Performance extreme Computing Conference (HPEC), pp. 1-6, 2018.
Ruder. overview of gradient descent optimization algorithms. arXiv: /1166.097777,1. 2016.
F. Santosa and W.W. Symes. Linear inversion of on Scientific and Statistical Computing, 1(4):1077- 1986.
reflection seismograms. SIAM Journal
K. Scheinberg, D. Goldfarb, and X. Bai. Fast first-order methods for composite convex optimization with backtracking. Foundations of Computational Mathematics, 14:389-417, 2014.
R. Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society, 58(1):66-228,, 1996.
T. Truong and H. Nguyen. Backtracking gradient descent method for general cl functions, with applications to deep learning. Appl. Math. Optm., 84:2557-2586, 2021.
12

---

Published as a conference paper at ICLR 2025
E. van den Berg, G. Friedlander, M.Pand Hennenfent, F. Herrmann, R. Saab, and Ô. Yilmaz. Sparco: a testing framework for sparse reconstruction. Technical Report Tech. Report TR-2007-20, University of British Columbia, Vancouver, Dept. Computer Science, 2007.
S. Vaswani, A. Mishkin, I. Laradji, M. Schmidt, G. Gidel, and S. Lacoste-Julien Painless stochastic gradient: Interpolation, line-search, and convergence rates. In NeurIPS, 2019a.
S. Vaswani, A. Mishkin, I. Laradji, M. Schmidt, G. Gidel, and S. Lacoste-Julien. Painless stochastic gradient: Interpolation, line-search, and convergence rates. Advances neural information processing systems, 32, 2019b.
P. Wolfe. Convergence conditions for ascent methods. SIAM Review, 11(2):226-235 1969.
C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning requires rethinking generalization. arXiv, 2016.
H. Zhang and W. W. Hager. A nonmonotone line search technique and its application to unconstrained optimization. SIAM journal on Optimization, 14(4):1043 1003:00431006 2004.
13

---

Published as a conference paper at ICLR 2025
A STOCHASTIC LINE SEARCH EXAMPLE
The results presented in Fig. 4 correspond to experiment from (Galli et al., 2023) without any modifications, and are run using the base code from the same paper, which be found at:
In this experiment, a multilayer perceptron (MLP) with a single layer, width 1000 and 535818 18 parameters is trained the MNIST dataset (LeCun al., 1998) until the training loss becomes less than 10 This is the same stopping criterion adopted in (Galli et al., 2023). To train the MLP, the following methods are used:
1. Adam: adaptive moment estimation method (Kingma & Ba, 2015).
2. SLS: stochastic line search (Vaswani et al., 2019a).
3. SPS: stochastic Polyak step-size method (Loizou et al., 2021).
4. PoNoS: Polyak nonmonotone stochastic method (Galli et al., 2023).
5. ABLS: an adaptive backtracking variant of PoNoS, detailed below.
As Fig. 4 shows, only PoNoS and ABLS terminate within 75 epochs. PoNoS does so after 56 epochs and 583 seconds, while ABLS finishes in 41 epochs and 464 seconds.
For all the above methods, we preserve the parameters recommended in (Galli al., 2023) unaltered from the source code. The ABLS method combines our adaptive backtracking procedure with a simplified version of PoNoS. Namely, PoNoS generates initial step-sizes with
N = 70.00* +ha,
(10)
where E (0, 1) and 4 is the amount of backtracks in iteration i - 1, which are accounted for in
4 max(Ta-1 + 4-11 1.0}.
That is, previous backtracks used to discount initial step-size given by
10.0 min(āk., 17 max }.
which in turn is based on the Polyak initial step-size
Jú (wx) S
N =
(11)
Cp (
where c, E (0, is hyperparameter, ig denotes the mini-batch sampled in iteration k, wy denotes the MLP parameters in iteration and fü, refers to the minimum of the mini-batche training loss:
fv
Σ fz.
iR
JEiL
Instead, simply (11) the initial step-size, with Cp = 1/2, the same value proposed in (Galli et al., 2023). Then, we apply ABLS to enforce
fi (wk- - 7i Si, (wk)) s C cm 11,
C C (0,
(12)
where Cn denotes an exponential moving average of losses given by
Ö SQuCk-1 + Si, (wx)
C max fú, (w+)),
QK+I =Q +1
Q++1
with & 1). The inequality (12) is stochastic variant enforced by PoNoS of the deterministic criterion proposed by Zhang & Hager (2004). This inequality can be seen as a generalization of the Armijo condition with the current loss replaced with average. As such, it preserves the structure of (3), which allows us to seamlessly apply (4b), with = 0.9 and c = 0.5.
14

---

Published as a conference paper at ICLR 2025
B EXAMPLES, THEOREMS AND PROOFS
In this section, we present the examples mentioned in Section 4, prove the results stated therein and provide further convergence results.
B.1 EXAMPLES
The first example establishes the fundamental obstacle that
no line search procedure can be provably better than regular backtracking to enforce any set of line search criteria that includes the Armijo condition or the descent lemma, for any class of functions that includes quadratics.
The second and third examples establish three more facts:
1. The step-size returned by backtracking is not monotone in p. even convex problems.
2. For nonconvex problems, given step-sizes af and a with a' < a, a being feasible does not imply a' is too.
3. For nonconvex problems, decreasing p may increase the number of criteria evaluations required to compute feasible step-size.
Example (Fundamental obstacle). Let F be defined by F(x:) 2²/22. If 3 * and dy descent direction, then by definition (V F FZz),, dz) (zz),ds) some C1 > O. Hence, given some e E (0, 1), (3) holds if and only if
dr 0 and must be that d₃ CI for
] 2 F(Ix+1) - F(Ix) + con ( (FF))
2"h carci
Therefore, (3) holds if and only if
C, (2(1 - c1ax) ).. = 200, -1 (1- )1 2 0,
or, equivalently, ag 2 - c), since x O. Now, suppose that ogg 4(1 c)/c; 0 and = 1/2. Then, after testing (3) exactly once, backtrucking returns the step-size On 2(1 - c)/er. the greatest value that is guaranteed to satisfy (3). Thus, in this example, backtracking optimal in the sense that it tests (3) only once to return the greatest feasible feasibee step-size possible. Therefore, no other line search procedure can be provably better than backtracking enforce any set of line search criteria that includes the Armijo condition for any class of functions that includes quadratics.
For the sake of concreteness, Fig. illustrates the particular case where = =1/2. Ig -1
du = - = 1, au = 2 and p = 1/2. The initial step-size Qu = 2. is too large and leads to that lies outside of the shaded region of iterates allowable by the A Armijo condition. After one adjustment, however, the step-size is reduced to poza = 1/2,, leading to the tentative iterate No + paxgdg = 0, which lies the boundary of the region of allowable iterates by the Armijo condition. That is, regular backtracking returns the greatest feasible step-size after one adjustment. Furthermore, this step-size leads to the minimum, therefore solving the problem after one iteration and one adjustment.
tentative iterate xo + oxgdo
Next, we show an analogous result for the descent lemma. Keeping F(z) = 12.22. for any x + y. (5) holds with estimate Li of the Lipschitz constant if and only if
2 F(v) F(y) + (V)()), y)
Lx
v11² La - (1² 2ry) +
La 2
2
22
which is equivalent to L 1. Hence, if Lo (0,1) and p Ly. then backtracking returns the optimal estimate Lo/p after testing (5) exactly once (requiring two function evaluations), no matter what x + y are. Hence, this example, backtracking is optimal in the sense that tests (5) only once to return the tightest Lipschitz constant estimate possible. Therefore, no other line search procedure can be provably better than backtracking to enforce any set of line search criteria that includes the descent lemma for any class of functions that includes quadratics.
As a side note, we look into what adaptive backtracking would do, For this problem, (8a) becomes
2c0p [|por (y)a) 1/112
v(ox) F(par (vk)) f(0x)
(z)( Pas (yre) yk) Lx-
15

---

Published as a conference paper at ICLR 2025
-1
Figure 5: Regular backtracking returns the greatest feasible step size after adjustment.
Therefore, after one function evaluation, adaptive backtracking returns po(as)aa = p. which matches the theoretical lower bound of backtracking and corresponds to the Lipschitz constant estimate 1/p.
Example 2 (Fact 1). Let F be defined by F(x)= = x² and fix 24 = = dg (Ix) = -2xx 2.
Then, the Armijo condition with c 1/4 satisfied if and only if
(-1+ S ak-
To find the critical step-size values which this inequality is satisfied, we simply solve a second-order equation, which gives the positive value of o% = 0.75 with corresponding Uerate Iı: + +o 0.5. Thus, if the initial tentative step-size is or = which produces the tentative iterate 1, then the Armijo condition is not satisfied and the step-size must be adjusted. If 0.75, then the adjusted step-size 0.75 produces the tentative iterate 0.5 and the Armijo condition is satisfied, therefore the step-size requires no further adjustments. On the other hand, p 0.8, then the adjusted step- size 0.8 produces the tentative iterate 0.6 and the Armijo condition is not satisfied. Adjusting the step-size once more produces a step-size of 0.64 og and an corresponding ilerate Ih + ougda- -1 + 0.64 2 = 0.28, satisfying the Armijo condition. Therefore, increasing = 0.75 to p = 0.8 decreases the step-size that backtracking returns.
Example 3 (Facts 2 and 3). Let F be defined by F(x) COs ax, where 55 fix 7/4 and
dy =F= = sin + a = 1+ a.
Given the above choices, the Armijo condition parameterized by c
1 is satisfied if and only if
2x
cos π + (1 + a))x)) a ( + +(1+a)ay S cos ②
am
(1 + a)² Olkc
2
2
2
or, equivalently, if and only
a + (1 + a)ax) S a(1 a)ax - -(1 +1 a)² O
cos
2
2T
If the initial tentative step-size is picked as
7n 2(1+a)'
then (1 + a)az =
Tt
so that
2
-12
π
+7 ạ -12 1.16 ~ 7/10
5t +
COS
20
That is, the Armijo condition is not satisfied, therefore the step-size must be adjusted. If 5, then 5x the step-size is adjusted to 2(1-a)' so that (1 a)a 2
5x and the Armijo condition is satisfied, since
cos 2/ + (1 (1)))aa)
=cos(3r) = 1 s -0.83 =
1 5T +
-
2
20m
-1.00
0.00
0.28 0.50
1.00
Figure 6: Reducing p can lead greater step-sizes.
16

---

Published as a conference paper at ICLR 2025
1/2 3.59
2m
3/t
4n
Figure 7: Reducing p can lead to step-size adjustments.
On the other hand, if 9.
then (1 a)ax 3r and the Armijo condition is not satisfied, since
π + (1 +a) = 1 0.5 = 3/10 10 - 5T +
cos
2
20T
Adjusting the step-size once more by p p= produces the step-size 14(1+a) and, in turn, the iterate I + Cydx
2
+
9x
7
x 3.59, which is feasible since
8T
9
5
+1
COS
= 1.13 0.21 ~
9
7
70
140T
In this example, the step-size 2[++a] is not feasible although is smaller than 2(+aj' which is feasible. More generally, this establishes that feusibility is not monotone in the step-size for nonconvex functions. Moreover, by reducing p & to p I. backtracking must adjust the initial step-size one additional time. Therefore, reducing p might increase the number of criteria evaluations to return feasible step-size.
B.2 CONVEX PROBLEMS
In this subsection, we present and proof the results for convex problems stated in Section 4. Proposition 3. Let F be convex differentiable. Given a point direction dy and step-size og > satisfying (3) for some e, then Tys de and 04 also satisfy (3) for any o'g (0,
Proof. Let / (0,1). Then, expressing 2x + + +
we obtain
F(Ix + +(.d)) = F(3(xx + agdy) + 3)xx) < (F + ands) + F)
s 3 (FF con (VF(x)) + (3))(x))
cak. (FF())), du) F(xx),
where the first and second follow from F being convex and FR, d₂ and satisfying (3), respectivell.
Proposition Let be convex differentiable. Fixing all other imputs, the number of backtracking criteria evaluations that Algorithm takes to return a feasible step-size is nondecreasing in the inpul
Proof. Consider the inputs ag, e and Algorithm fixed. Then, < P1 < and let Ni and N2 denote the number of adjustments Algorithm takes to compute feasible step-size when it receives respectively and P2 as inputs. If p NNaay am is feasible step-size and N > N; for some i E (1,2), then so is ooo, in view of the fact that p.N² < <P; and of Proposition 3. Moreover, Algorithm must test if the step-size P; feasible before testing the step-size p1 Ni and therefore
cannot return Pi NY. agg Inductively, we conclude that N₂ and N₂ are the least nonnegative integers
such that P are feasible. Now, since / feasible, if N1 > N2. then so is No < p2 the assumption that P1 P2 and of Proposition 3. That is, N₁ is not the least nonnegative integer such that pi is feasible, contradiction. Moreover, each adjustment requires evaluating the objective function once, so the total number function evaluations Algorithm takes to return feasible step-size is N; + 2. Therefore, if Algorithm receives Pi input, then it takes more function cvaluations to return a feasible step-size than if receives as input.
N2 in view of
17

---

Published as a conference paper at ICLR 2025
Definition 4. The inputs Algorithms 1 and 2 said to be compatible if cku, c, coincide and the imput P to Algorithm is parameterized by the same p that Algoritim I takes as input.
Proposition 5. Let F be convex differentiable. Given compatible inputs with a descent direction dy. and e < Algorithm 2 takes no more function evaluations to return feusible step-size than Algorithm does.
Proof. Suppose Algorithms and 2 receive compatible inputs. (3) is violated for some tentative step-size Og,, then v(ax) < 1 which together with c E (-0, imply - c- v((s) > 1 c > 0. In turn, p(v((cx)) < p because p. by assumption. The result follows by repeating the arguments used to prove Proposition 4 above.
B.3 NONCONVEX PROBLEMS
B.3.1 ARMIJO CONDITION
Proposition (Armijo feasibility for C2 functions). Let F be twice continuously differentiable. Given base point The descent direction dx, an initial step-size og and constant e (0, for the Armijo condition (3), there is some ā ā(Tk, des c) S Og such that Ty + ogd2 satisfies (3) all Or (0, a).
Proof. Assuming F' twice continuously differentiable, then by Taylor's theorem (Nocedal & Wright, 2006, p. 14), there exists some t = t(Tk, de, ax)) E (0, 1) such that
F(Ix + agds)) F(x+) + a (VF d4) 2 F2F(2z tagd))de).
(13)
Moreover, the eigenvalues of V are continuous and the line segment {ax + ands as E [0, aol compact, therefore there is some À > 0 such that for all ag (0, an) and t E (0,1)
V F(z + tagd4)de I A||d&|1
(14)
So, let ā = a(*,, dz, = 2(1 - ()F - dg)/((|ldd l??) > O, which positive since dg is a
descent direction, by assumption. Combining (13) with (14), it follows that if ag (0, ā), then (3) holds.
For the sake of convenience, we now restate some definition from Section Definition (Smoothness). A function F is said be Lipschitz-smooth (5) holds for some T, >
Definition 6 (Gradient related). The directions de said to be gradient related if there C1 0
and 02 > 0 such that (*+), dd)) 2 e1 F[ and ||dx|l S 02l FF(xx)) Il. for all 2 0.
function F, we are particularly interested in applying the Descent Lemma (5) with æ = Ix and y = Ia + ardg, which gives
Given Lipschitz-smoole
F(as + agds)) S F(xx) + an (VF(x)) da) + a 1d2.
(15)
Proposition (Armijo feasibility for Lipschitz-smone smoohh functions). Let F be Lipschitz-smonn smooth. Given base point a descent direction de, an initial step-size on and constant E (0, for the Armijo condition (3), there is some â a(IK, de, e) S og such that (3) holds for all os E (0, a). If, in addition, dy are gradient related, then (3) holds for all ag E (0,
2(1-)011 independent of 24 and de- Leg
Proof. To guarantee (3) holds, we impose that the right-hand side of (15) less than the right-hand side of (3):
F(xx) + a (VF(s)), dx) + a a 1| F(xx) + (oF(VF()))
In turn, simplifying the above inequality, follows that
2(1 (V(F((x)) -da)
0k
L [|
(16)
18

---

Published as a conference paper at ICLR 2025
then (3) holds, where note that (16) is positive, since dę is assumed a descent direction.
Now, suppose that (VF(*+), -d+) 2 ai [ and deel I e2 e2l (zx))]l for some C1 > and 02 > O. Then, for all ag such that ay S 2(1 c) we have that
ag - 2(1 c) ci (Fxb)]
2(1 (VF(())
L ([
L||da|1
That is, (16) holds. Therefore, (3) also holds.
and assume U, are given by (4). Also, suppose da are gradient related. If Algorithms and receive Org, as the initial step-size input at iteration k: + for all 0, then they evaluate (3) at most [log, [ā)p((//o]]] + 1+ k times up to iteration k, where = 2(1 - c)e1/ Lez. If, on the other hand, Algorithms and receive on as the initial step-size inpul at every iteration, then they evaluate (3) most k( (a/ + +1) times up to iteration k.
Proposition 8. Let F be Lipschitz-smooth,
Proof. Suppose that Algorithm 2 evaluaaes (3) and it does not hold for a given tentative step-size ork- Then.
F(z axd4) F(x))) > ca. (VF(x))
Dividing both sides above by co2 (V (3 follows that 1 - >>>> 1 cu(ax) > 0 and (1 c) (1 - c v(an)) < 1. Plugging this inequality into (4b), we obtain
gives v(ax) < In turn, since (0, 1),
p(ax) max(e, p(1 c)
v(ax)) <.
since by assumption p. Therefore, (3) does hold for a given tentative step-size, then Algorithms and multiply it by a factor of at most to adjust it.
Moreover, by Proposition 7, (3) is satisfied for og (0, a), independently of æ and de-
Hence, if Algorithms and 2 use oup the initial step-size for the first iteration and og at iteration k+1 for l: 2 0, then most [log, (ā/ ((G//o)) +1 adjustments are necessary until step-size that is uniformly feasible is found. Each adjustment entails evaluating (3) once. In addition, (3) must be evaluated once times up to iteration k.
every iteration. Therefore, (3) is evaluated at most [log,(0, (ā/an)] +
Now, suppose Algorithms and 2 use (āo (a/oo)) + adjustments are necessary in every iteration until feasible step-size is found. As before, each adjustment entails evaluating (3) once, in addition to the first evaluation. Therefore, (3) evaluated most k[Llog, (alloog((//))) (a/ao)] + times up to iteration k.
the initial step-size in every iteration. Then, at most
Proposition 9 (step-size lower bounds). Let F be Lipschitz-smoothh Also, suppose dy gradient related. Given appropriate inputs, Algorithm 2 with the choices specified by (4) and Algorithm 1 return a step-size on such that
2(1 (1-c)cc >
0 2 min Co. p
}
Le
Proof. Since dy is descent direction, dividing both sides of (15) by (VF()))), -dp)
yields
-co(ox) = F(xx + ands) F(xx)
a L 1|
2(VF dz)
Hence, if ő is chosen as (4b) and (3) does not hold, then step-sizes og returned by Algorithm 2 satisfy
1 1-c a 2 2(1 (VF de) 2(1 (11-com c)c1
Helax))ax 2 P cc(aa)
2 Le3
> 0.
L|
Moreover, by Proposition 7, the greatest siep-size for which (3) is guaranteed to hold is 2(1 e)cı/Lež, an 2 2(1 c)c/ Loz, then Algorithm returns step-size at least within factor of 2(1 c.a.
19

---

Published as a conference paper at ICLR 2025
B.3.2 DESCENT LEMMA
First, note the proximal operator Pas given by (6) is well-defined. Indeed, given continuous convex function g, a point 3/k and some og > 0, the map x + g(x) + (1/20x)) || - (y og V ((()) is continuous strongly convex and therefore admits unique minimum.
Proposition 10 (Lipschitz step-size feasibility). Let f be Sopschitz-smootti convex and let be continuous convex. Also, suppose and P are chosen as (8a) and (8b). If aq (0, L/),, then (7) holds for all yt. If Algorithss and 2 receive Or as the initial step-size input in iteration k + 1, then they evaluate (7) at most [ogg((/Io. (1/Loo)] + 1 1++7 times up to iteration If. on the other hand, Algorithms/ 1 and 2 receive oo the initial step-size input in every iteration, then they evaluate (7) at most k([log,( (1/ Lao)] + 1) times up to iteration ki
Proof. Given any yk. if on E (0, 10,1/ then applying (5) with x = Paax (8k) and y = yks we get J(Paz (vn)) S [(x) + (V ((xx),() (Ux) - yk) + (T//2) (Uk) 1x11
S (vk) + (V (vx),, Pa,, (Uk) yk) + (1 (1/22x))l222 (MI:) y/ 112
Adding (Paz (uk)) to both sides, we recover (7). Thus, if og E (0, a), then (7) holds for all y/--
Given initial step-size ag and the points yk and Pau (yxx), Algorithm 1 checks if (7) holds. If it does hold, then Algorithm returns ag. otherwise Algorithm adjusts ark by p. recomputes Pau (1k). checks if (7) and repeats. Since (7) is guaranteed hold for os E (0, 1/L,), given initial step- size Ogg, Algorithm computes a feasible step-size after adjusting 0 at most [log, [T/Lo))] + times. Each time Algorithm adjusts ag,, Algorithm 1 evaluates (7). In addition, Algorithm I evaluates Eq. (7) once every time it is called to check if the initial step-size is feasible. Hence, if Algorithm I receives ag as the initial step-size input at iteration k 1, then it evaluates Eq. (7) most [log, (1/Lao)] + 1 + & times up to iteration k. On the other hand, if Algorithm receives the same ag as initial step-size input at every iteration, then it might have to adjust a up to (1/Lo() + in every iteration, therefore Algorithm 1 evaluates (7) at most ((Llog, (1/Lo)) + 1) times up to iteration k.
Now, consider Algorithm 2, with e and أ chosen as (8a) and (8b). Given an initial step-size og and the points yı and Pa.. (y+).. Algorithm checks (7) holds. Suppose (7) does not hold. Then, moving
the terms f f(Po. )) and ( Pas (yk) - yu) to the left-hane side and cancelling (Pa (1k))
on both sides, we obtain
(Pa. (wx)) f(v)) fV)()) Pas (1)) yk) (1/2ax) Pl (vk) yk 1x.12
(17)
Since || || 2 O. the lent-hand side must be positive. So. dividing both sides by the left-hand side and using (8a), follows that v(xx) < 1. Hence, Algorithm adjusts og to p(are) )oy < porg. That is, the factor by which Algorithm 2 adjusts og is smaller than the factor by which Algorithm 1 adjusts Og- Therefore, Algorithm evaluates Eq. (7) at most as many times as (1) does.
L
Proposition 11. Let f be Lipschitz-smooth convex and let g be continuous convex. Also, suppose and و are chosen as (8a) and (8b). If Algorithms 1 and 2 receive an initial step-size oig > 0, then they return a feasible step-size ag such that ag 2 min {ap. p/ L}.
Proof. By Proposition 10, every step-size og (0, 1/L) is feasible. Hence, if oup is not feasible, then since Algorithm adjusts step-sizes by p. it must return a feasible step-size within a factor of 1/L.
Now, consider Algorithm 2, with and á chosen as (8a) and (8b). Algorithm 2 only adjusts og when (7) does not hold, so suppose that is the case. Applying (5) with y = yk and 2g = Pau, (yx) yields
(pa. (1x)) [(xx) - (VI())) Par (yR) yn) S (L/2)]lpon (wx) yu 1l
Dividing both sides by (L/ (Uk)) f(mx) - (V (V]( Po. (yL) - yx))), which is positive by (17), we obtain
Pas (M1) - 3111
E F(P.g (wx) - fxx) (v)())) Pau (yk) yk)
pu(ax)as.
where the identity follows from (8a). Hence, Algorithm 2 adjusts on to p(v(ax))) 2 2p/T. n
20

---

Published as a conference paper at ICLR 2025
B.4 CONVERGENCE RESULTS
B.4.1 A GENERAL CONVERGENCE RESULT FOR ADAPTIVE BACKTRACKING
Under mild conditions, we now show that limg-++oo V (f+))) ||2 = 0 for iterates rı in the form (2) with gradient related dg and step-size sizes generated by adaptive backtracking. We emphasize that the following results make no further assumptions on how the descent directions are generated and that (Nocedal & Wright, 2006, p. 40):
For line search methods of the general form (2), the limit limg [+((=))) is the strongest global convergence result that can obtained: We cannot guarantee that the method converges to a minimizer, but only that it is attracted by stationary points. Only by making additional requirements on the search direction dy-by introducing negative curvature information from the Hessian V f(xx), for example- -an strengthen these results include convergence to local minimum
Proposition 12. Let f be bounded below and Lipschitz-smooth on an open set containing the level set {0 : f(x)= S f [zo)], }. where zo is the initial point of iterates (2) where dy are gradient related and og generated by adaptive backtracking (Algorithm 2) with some oo 0 and using and given by (4). Then, lim V [xx))
Proof. Under the above assumptions, we have that ou 2 min pa), where 2-1-2111)))) / by Proposition 9. Moreover, we have that (V (Vx)) ,, dz) - < (x+))l because d₃ are gradient related. Hence, since adaptive backtracking enforces the Armijo condition, (3), it follows that
f(zx+1) f(z) s f(xx)) < -mminfoo, p2 cl.,(Lc))V
Telescoping the above difference, we get
[(x++1) ((x) E E((oe)) - ((x:)) < -emin (o, vo, --minn
2(1 c)c1
Le3
1=1
Rearranging the above inequality and using the assumption that f is lower bounded, we obtain
2(1 - c)c [Vf(=)) < f(xo) - f(x++1) < +00.
emin av.
Le3
That is, [[ are square- Therefore, it follows that
lim [[ 0. Je- +:00
B.4.2 CONVERGENCE RESULTS FOR GRADIENT DESCENT
We show that the standard convergence results for gradient descent are preserved if step-sizes are generated by adaptive backtracking. We address smooth and then smooth strongly convex objectives.
Proposition 13. Let f be convex, Lipschitz-smooth and suppose f(())) 0 for some x". the step- sizes og of gradient descent (Algorithm 3) are chosen by adaptive backtracking (Algorithm 2) using ğ and v given by (4) with E [1/2, 1) and cro > 0, then ag 2 min(au, p where a = 2(1 - c) and
f(xx) - f(x*) - 10 x0 112
2 min (nin pot)
Proof. Under the above assumptions, all iterates of gradient descent satisfy the Armijo condition, (3). Moreover, since f is convex, we have that
f(x)) S f(x") + (Vf( - -x*).
Hence, combining the above inequality with (3), follows that
f(xx+1) S f(xx) cou [Z)())))) f(x')( + (Vf(zx), -x)) cox (z
21

---

Published as a conference paper at ICLR 2025
In tum, since 2 1/2, rearranging the above inequality and completing square, get
f(zx+1) - f(=")=f(-=----0)) - (2ax (V f((z)), x²)
2am
(20r ([[())) - x²) - - [ + I|ok - x x²1
200k
(1|rs= - - Vx (xra)) - ==11 2 - ||=t - x x²1
20rk
(1|0r= x= x=2 |,++1 x= 11²).
20%
Now, since gradient descent sets da (xxx) then de are gradient related with e C2 = 1. Moreover, since f is Lipschitz-smooth, then 2 min(ao, pa), where ā = 2(1 c)/ L. by Proposition 9, Plugging this lower bound into the above inequality, follows that
[(x+1) - f(x)) 2 minn po)) (1 - x" x²11² - || x²11²).
Telescoping the above, we get
Σ (f(x4)) f(x"))
Σ
(12x - 20112- || - x²11?)
2 min (0, pEt
t=1
100 x 112
| 1 - 21
2 min (KO, pc)
FD x='1
2 min pa.
Since fx(=²) and f is convex, we have that f f(x*) 2 0. Moreover, f(xk) are decreasing because the Armijo condition holds in every iteration. Therefore
| - x=12
f(*x+1) f(x*) < 2 min (oo, pa)
Next, we show that adaptive backtracking also preserves the convergence rate of gradient descent on strongly convex objectives, which define below.
Definition 7 (Strong convexity). A continuously differentiable function f is said to be strongly convex if there exists some m such that for every x. and y
f(u) 2 f(x)(()
m 2222
x212.
(18)
Proposition 14. Let be Lipschitz- and strongly convex. If the step-sizes on of gradient descent (Algorithm 3) are chosen by adaptive backtracking (Algorithm 2) using and given by (4) with c E [1/2, 1) and og E (0, 1/m), then
To + m
f(xx) - f(x")( I (1- imminfoo, pa))
120
x x²1
2
In particular, c- 1/2 and on > p\ L. then
L + m <1
f(xx) - f(x') < (1-
1
x 1²
2
where q mmmm-mmmm--- L/Lii is the reciprocal of the condition number of f.
Proof. Let and m denote the Lipschitz-smoothness and strong convexity constants f. The assumption that f is strongly convex implies the existence of unique global minimizer x" for f. We then use x² to define a Lyapunov function V. given by
V(xx)= = f(xx) - f(x
m
I
x1
2
22

---

Published as a conference paper at ICLR 2025
which is positive for rı # x². To prove the result, show that
0. where L
L
6% Qk
Qk
and
m
And note that the assumption that og S oo 1/m implies Ls m. thus dR well-defined. By assumption, the iterates gradient descent satisfy (3) with E [1/2, 1), hence
0 V f (x+) 11 [(x++1) - f(xx) - -oox [V/=))]
Moreover, by strong convexity, we have that
f(xx) - f(=²) & (Vf(z)). xx)
m
2 x²1
2
Next, expanding quadratic terms, it follows that
(1 + 6x)1 x²11² || x=1l 112 =(1 + [ - 20 (V)(t)) -xx))
x²))
8u I x =²1
Now, from the definition of oR. we obtain
Qx
Qx - =1
Qx 8k.
(1 62)( ma²)
and
(1 + 8g maa
Qx
Qx
Qi Qx
Then, we put everything together to get
(1 + (1+8)VV(XXNI)) - Va((x)) S (1 (w++ 6x) mark)
V
[x(x))1
2
- (6% (1 + & )
(V (((x)
=x"
Ok [Vf(=x)]
S 2
Applying the above inequality inductively, it follows that
A V(Ix-1) & Vxxo)
1 ++ &
Moreover, applying (5) with y mo and x x², and noticing that ff(x*) we obtain
L + m
V(ra) f(xo) f(x")
2 I00 x11
2 1w0
x x01
Furthermore, under the above assumptions, we have that age 2 min mainooo,ni where 2(1 - c)/L. which implies that
Qk
1 5g
Q2 Q
mar
I m min can pa]
Finally, we put everything together and obtain
L m
f(xx) f(x)) S (( S
11:00 x=
2
+ 5
L + m
<(1 m min min )ax)
||:00 11
2
B.4.3 A CONVERGENCE RESULT FOR ACCELERATED GRADIENT DESCENT
To establish that adaptive backtracking preserves the convergence rate of accelerated gradient descent, we employ a Lyapunov argument based on the function V defined by
(2 ma) = f(w) f(x
m
= x
(19)
2
23

---

Published as a conference paper at ICLR 2025
where the point 2; (TTk: ykb) is defined
= 2h V Qi= yk.),
(20)
and the estimated condition number Q2 and estimated Lipschitz constant are given by
- Lo/m. < 0, La/m, 12 0,
(L=
Qi -
and
L
(21)
Note that the index t of 24 follows that of V. but is independent of the indices of 2y and ye. which allows us to split the Lyapunov analysis in two auxiliary lemmas. First, we show that for a fixed index k + I, the Lyapunov function V decreases along consecutive AGD iterates Second, we bound by how much V can increase with respect to V& for the same AGD iterate.
accelerated rate.
Lemma 1. Let f be Lipschitz-smoott and strongly convex. If the Lipschitz constant estimates I- of accelerated gradient descent (Algorithm 4) are generated by adaptive backtracking (Algorithm 2) using P and v given by (4) with c E [1/2, 1) and Lo > m, then for k 2 0
(1 + V (Bx Fx+1) V (Uk. IR)) S 0,
where
= = 1/(V=1 11..
Proof. We start by splitting (1 b))1)((((41)))
into three further differences:
(1 + 5k+1) (f f(x*)) - (f(Nk) f(x*)
=(1 + 5x+1) - f(xx)) + (f+1(((zx)) - f(x")) + (f(xx) - f(uw))
Since e E [1/2,1) 1), then adaptive backtracking generates La such that
1 [Vf((z))1
(1 + 8x+ ((f(ee1))) - f((x)) S - (1 +1+ 5x
(22)
2Lk
Moreover, applying (18) with x = Iu and y = x² and using that f is convex, we get
(f+1(f(z)) f(z*)) < 8x+1 f xx x²) 5x+1 f(xx)- - f(yk) S (Vf(xx), xx ybh)
m
|| x=11,
(23)
2
(24)
Next, we express the difference #x+1 - x²
Zk+1 - x²" =x++1 + Vxx - 4k-11) - x²'
=yk+1 3x(x++1 us) + VL yk) x
= (1 3x + VQ.)) + +1+(++ (Ou)( yb) + - x
LA
VQLVf(zx) + (VQx - 1) yk) + Ib xx"
L
where we used the identities
1 + (1 + = Q
and
3x + V - VQr- -1.
In the same vein, when expanding the 2-norm term || - 112 below, we use the following identities after colons to simplify the coefficients of terms before colons:
|V (x=)))
(Qx/L2)(m/2) 1/2Lkr
( f (xx). 2% vk)
m(1 + 0x+1)) QullV -1) 1,
( f(x)), x²)
m(1 + 6x41) Q Sk.
||ا| - yxll 2
(1 (1+6+1)(V0)) - 1)2 VQelvQ
(xk Uk. F. x²)
(1 (1+))1)((v0 Qr -1) VQk.
24

---

Published as a conference paper at ICLR 2025
As result, the 2-norm difference in (1 (ot+))V++((VM+11111 - (Vki becomes
(1 + 6k+1)
m
|++1 - x x=1
m 1ink x² + QK( - -ya)22
2
2
1 + 6k+1
[V (Vf(zz).
ykb) 6% (z((z)), 2b x²))
2L
m
(Qe(vQ= 1)1l=x y=11² + m (2 12VVktt Qx(xx - yk, I - x² + (1 + 5k 5x+1)llax - -x=113)
2
2
m
2/222/2 (Qullæx - yx112 + 2/ Qi (3x Vb - x²) + || - 2²1
2
1 + ok+1 [2xx)] - (Vf(zx),
uk) - 6R (V fxxx) Ih - x²)
2L
QxI1= yk 2 + 6% 2 1| 2²112
(25)
2
Finally, combining (22) to (25) and then canceling several terms, we obtain
(1 + 1++++)144+4 (3he 2x41) - VR++ (yk, I&) S
m V QuIl=> 2
yx 11 S 0.
Lemma 2.
Let be Lipschitz-smoott strongly convex. Given initial points 3o = Yo, the estimates La of the Lipschitz constant in accelerated gradient descent (Algorithm 4) are generated monotoni- cally by adaptive backtracking (Algorithm with La serving as the initial estimate for LB+1) using P and v given by (4) with [1/2,1) and Lo then for k 2 0
O Q 1
V (Miss xnn S Ve(ya, zx).
Proof. We argue by induction. If ao and yo match, then 21 (yo, Fo) za + Qu(a vo) za zo + Q-1 vo) 2o(yo.20)
Moreover, Q-1 = Qu. by definition. Therefore, we have that
V1 =o) = f(wo) - f(x*)(()+))) )+ + m
2 2| (J):)o)) Ho) - =22
28 (f(w)) -((x)) + 120(y0, vo) x= x1)
Q²
Q
Vo(31. 2o).
Q²
which establishes the base case. To prove the inductive step. divide the analysis in two cases, each representing a possible sign of (xx yk 2z - I²)) For each case, we bound
|| - x= + V Quia vall - -1=x x x11
22((Qx 1Qk x², ab wn) (Qx- Qk-1))l 11.
(26)
In turn, bounds on (26) translate into bounds on Vk+1 (yk,, In) Vi(un, I.I,, since
VK+1 x - Vi xK) = m72 (1|= - + +Qu( - yx))l - 11 x0 111
(27)
2
Then, to prove the inductive step, we express bounds on (27) in terms of Va+1 and VE.
First, suppose (Ix yk. - x²) 2 O. Also assuming L Lk-1, then / / Qx S 1, so that
Qk
Q Qx Q
VQr- VQ-IS
VQ
vQr
VQn
VQn
25

---

Published as a conference paper at ICLR 2025
Hence, applying the above inequality to (26) and then adding nonnegative | x01 term to it, we get
110k x' + VQu(TI -v=)ll - 1| x='
Qk Qk-1 (ark - -x - -yb) + (Qk 11-1))1=0x 3x
Qx - QK-
<
10 x²1
VQk
Qk
Qk Qk-1 | 1 I + VRl yx)l1
(28)
Qk
Plugging (28) back into (27) yields
Qx Qx-1 m
V (x) Vx(uk, -
1 -x" +x*+ +x - ub))l
Qk 2
Qx Qk Vk+1
Vy+i
(29)
Qk
where the last inequality follows from the definition of Va, as f(vk) - f(x") 2 0 implies
Vi+1
N
m
2 | - x²' + VQu(xx - -vk)l
(30)
Thus, rearranging terms in (29) and then multiplying both sides by Q 1 we obtain
Qk Ve(yn,
Q2 Ve(u,,
Ve+ S
Qx-1
2
where the second inequality holds because Q4/Qx-121
Now, suppose (I 1/. Th x²) < 0. As in the previous case, we start by bounding the gap (26). But given the negative sign of (I yks 2x x²) term, we bound the || I yysl² l2 term instead. To this end, we first invoke the assumption that (Ix yke IR x²) < 0 to establish that
1lyk= xx 2=
| x²
(rk y1x) 1
[2 x²112 112--22 2(xx x² , 34h |
yk 11?
It'k 112
(31)
To the above inequality on (26), first we rewrite more conveniently as
| x² + VQkTz - ykl 1 - 1²12
Qk VQ
(Ix -x", S Vu(xr vw)) + VQllVQu VQ+-1)l
yxll 1
VQk
VQ-il Do-i(VQa Q+ -VQu 3x VQk - -Qk=1
| =1'1
VQk
VQr Qu-
|008 x² VQx(mx w1)1 + 1k- (Qk-1) 3k 11
VQk
/ /Qk-1
| - 2
(32)
VQk
Next, we use the following elementary inequality, which is consequence of |l/c bell > 0:
||a b1l2 ||a|| - 2(a, b) |bb1 < (1 + 1/c3 + + !18B2
26

---

Published as a conference paper at ICLR 2025
Namely, we apply the above inequality with 24 x², b = 2 x= and c² /Qk-1/VQs to
bound the || ykll term (32) and obtain
Qk-i(V Qx v QQ- [0 - yx11
VQR-IIVVQ (Q-
yk + (2x - -x')////////0 V
VQk VQK-1
1 - x² --- (Ix - =x²)11
VQk-1
VQk- VQL-1
(1+
VQk
11 -x"1| + vQu- 1-Q
1 1 VQ-1
|| - x²1
VQk-
VQR-1
vQk-
Qx Qk-1
|| x² x²112 vQk- -VQu-1 vQ VQk-
| - x=1
(33)
Qk-1
vQk
VQ--
Plugging (33) back into (32) and then using (31), we get
I - x + VQV QQ(x - yx)ll - || - x121
VQk- VQu-1
1108 1-6--x4+ x² Vxk - yx)112 1 Qk Qk-QU-1
Qk-1 -1 1
x=1
vQk
Qk-1
VQk- - VQk-1 ( (vO6 + (
-Qu-i -1) 11102 x²1
VQk
VQK-1
UQ+- VQk-1 1 -x" + VQR(Ix - -bh)1 + Qk Qk-1
1 - x²1
VQk
Qx-1
vQk- VQk-1 11 - 12.
(34)
VQk-1
In turn, plugging (34) back into (27) and then using the assumptions that m 2 m and m S m yields
Va+ (1k, Ix)
Vi 2x)
VQn- VQ-i
m Qx
Qu-1
<
1008
x² + VQL 3x)l1++
||2 - x= 2 Qx-1
2
vQk
m v QK-
VQK-
+
11 =2²1|
2
VQ
<
VQk QQ-1
1 VQk 2
m
x² + (Qa(xxx-aa)) +
Qx - -Qk-1
m
|2 - x=1
Qk-1
2
VQk /Q
+
m
2 191k x²11?.
(35)
VQu-1
Now, in (30), the fact that f(y)) f(x*) 2 0 implics
Va m4) (1xx f(x") ) + マタ || x x1 > 1| xx
(36)
In the same vein, applying (18) with = x² and y = yı: to the definition of Vs. we obtain
V& (yk, .x) f(x) f(x'x(xx))) ) + m
2 1 x 11
m 1ly 1²
(37)
Plugging in (30), (36) and (37) back into (35), and then moving all Vest (yx, x&) terms to the left- hand side and all V4 (M,, xx) to the right-hand side, we obtain
Q (yk xx) S ( Qu-i
Qk + VQr VQK- Va (yr, Ix)
(38)
VQL
VQk-1
Multiplying both sides of (38) by VQkl /0/lQQ.e /Qk-1, and then using the fact that VQr 2 VQ- yields
vQ Qx
+ VQk /Q--1
O2
V2-1 24) - VQ-1
Valuk (())) 5 Q Velun, zb),
Qh-1
VQk-1
27

---

Published as a conference paper at ICLR 2025
where the last inequality above holds because Qx 2 Qk-1 implies the following equivalences hold:
Qk
VQk- - VQQ=1
Qk 2/2
I
=
Qk-1
VQx1
3/2
k--1
Qk-IlVQx - 5Q -
Therefore, both when (ara , Fk - ya) 2 0 and when (IrA - ,",0x
2k - -u) < 0, the inequality
VK 2xk) S
Ve(Uk. 2x)
holds generically for all yk, proving the lemma.
Proposition 15. Let f be Lipschitz- smoohh strongly convex. Given initial points Io = yo- if the estimates Lak of the Lipschitz constant in accelerated gradient descent (Algorithm 4) generated monotonically by adaptive backtracking (Algorithm 2 with La serving as the initial estimate for Lk+1) using P and v given by (4) with с [1/2, 1) and Lo m, then for k 2 0
vQ= 2(1 - c)p
Q²
L + m
f(y++1) - f(x')
10 x=1
VQ
4(1 cl-pp)pp
2
Proof. Combining Lemmas 1 and 2, we have that for every A: 0
Qi
76411 S 1 1 5g Va+a S 1 8g 0
Vx(u,,
Moreover, from Proposition 9 and the assumption that La it follows that
LA S max L/((11 - c)))] S mmx L/ c)p)}
and, in turn, we obtain
1 VQk-I
vQ& < VQ - 22(1 c)p
L
where
Q
(39)
1 8
VQ
Furthermore, assuming = no. we have that
L
Vo .D) fy0) f(x")+ + 1|:00 x²1 <
2 11:00 - x² 11
Arguing inductively, all but O and Q² = Q cancel and, since Lo > m, we get f(1++1) f(x))= - V (bk+1, I1++1)
4 1
VQ /2 ccp
Volyo. Do)
VQ
43
VQ 2(1 c)p
Q2
L +
x=1
VQ
4(1
c)2
pp
2
28

---

Published as a conference paper at ICLR 2025
C METHODS
In this subsection, we briefly state standard inplementations of the base methods that we use in the paper. For the sake of simplicity, we only state single iteration of the corresponding method.
Algorithms 3 and 4 summarize gradient descent and Nesterov's 's accelerated gradient descent in the formulation with constant momentum coefficient (Nesterov, 2018, 2.2.22). Algorithm: summarizes Adagrad (Duchi et al., 2011).
To state the last base method that consider in this paper, we must introduce an auxiliary operator. Given a convex Lipschitz-smode smooth function f with Lipschitz constant L and a continuous convex function, the proximal operator pz is defined by
L
prly)) arg min g(x)
(40)
With this definition, state Algorithm 6, which summarizes FISTA (Beck & Teboulle, 2009).
Algorithm Gradient Descent.
Input: Th. f(rx), > 0
Output: Ik+1
I: Tk+1 Ik O& fzz))
Algorithm Nesterov's accelerated gradient descent (Nesterov, 2018, 2.2.22).
Input: Fk. yke vf(xx)), La m
Output: Ik+1, yk++1
1: Mk+1 Ik V
2: Bx < VLutym
-mm
Øk41 (1 34yyk+1
Ba8k
Algorithm Adagrad (Duchi et al., 2011). Superscript means the i-th entry of the vector.
Input: JK, V f(()), Mk. Z200 > 0
Output: Fk+1, Sk+1
I: $ = yk: 2h + ())(
2h+1 r V fz())
Algorithm FISTA (Beck Teboulle, 2009).
Input: Tk. Fk-1, yki tx, ff(xx) Output: Fk+1, 1k++1, 1x+1
1: Th+11 < (y()
tk41 & /1411
Mk++1
Ik + 1--1
fell
(xh xk-1)
29

---

Published as a conference paper at ICLR 2025
D LOGISTIC REGRESSION EXPERIMENTS
In this section, we provide further details of the logistic regression experiments and present full plots of all runs.
Table 4: Details of datasets and method precisions used in the logistic regression problem.
dataset
datapoints
dimensions
AGD
GD
GD (monotone)
Adagrad
a9a
32561
123
10-9
10-6
10-b
10-6
gisette_ scale
6000
5000
10-9
10-9
10-5
10-9
MNIST
60000
784
10-9
10-6
10-3
10-9
mushrooms
8124
112
10-9
10-9
10-5
10-9
phishing
1 11055
68
10-9
10-9
10-6
10-6
protein
102025
75
10-9
10-9
10-5
10-9
web-1
2477
300
10-9
10-9
10
10-9
Dataset details. We take observation from seven datasets: A9A, GISETTE AASETTE_SCALE (G SCALE), MUSHROOMS, PHISHING and WEB-1 I from LIBSVM (Chang & Lin, 2011), PROTEIN from KDD Cup 2004 (Caruana et al., 2004) and MNIST (LeCun et al., 1998) The dataset A A is a preprocessed version of the ADULT dataset (Becker & R, 1996), while WEB-1 1 is subsample of the WEB dataset (Platt, 1998).
Initialization details. For Lipschitz-smoote problems, a step-size of 1/L is guaranteed to satisfy the Armijo condition (with e = /2) L. > L. Accordingly, consider four choices of initial step-sizes, == [10*, 102, 10s, 1/2)/ which capture the transition from initial step-sizes that do not require adjustments to satisfy the Armijo condition step-sizes that do. In practice, is unknown and the transition would occur as one attempted an arbitrary initial step-size and adjusted it correspondingly until the line search was activated. Hence, using L anchor the choice of initial step-sizes is merely an educated guess of the transition values that would be found in practice. We adopt the standard choice 10-4 (Nocedal Wright, 2006, p. 62) in (3) for BLS used with GD and Adagrad but, motivated by both theory and practice, we choose c 1/2 in the case of AGD, Also, we use the regularization parameter y as the strong convexity parameter input for AGD.
Evaluation details. We run all base method and their variants for long enough to produce solutions with designated precision; Then, we account for the number of gradient and function evaluations and clapsed time each variant takes to produce that solution. Finally, for each BLS variant we average those numbers over the four initial step-sizes that we considered. All methods compute exactly one gradient per iteration. To account for elapsed time, we record wall clock time after every iteration. Although somewhat imprecise, elapsed time reflects the relative computational cost of gradient and function evaluations and, especially in larger problems, is reasonable metric to compare performance.
Additional comments. We make the following additional remarks and observations:
We considered two ways to initialize the step-size for line search at each iteration: (1) using the step-size from the previous iteration and (2) using the same fixed step-size at every iteration. We refer to the corresponding line search subroutines as monotone and memoryless. The monotone variants robust to every choice of p while some values of p may turn the memoryless variants of AGD unstable or unacceptably slow. When the memoryless variants work, however, they generally work much better than the corresponding monotone variants and the baseline methods.
Monotone backtracking is not as appealing as memoryless backtracking because although both vari- ants take fewer iterations than the baseline method does to reach a given precision, the savings in iter- ations generated by the monotone variants are not enough to outweigh the additional computational cost of function evaluations that the same variants accrue. Therefore, we only report results for the memoryless variant in the main text and defer results for the monotone variant to Appendix D.
The initial step-sizes greatly impact performance. For some starting step-sizes, vanilla backtrack- ing is better suited for finding the optimal solution than our adaptive method. However, we find that there tends to be more variance in the performance of vanilla backtracking.
When is a good estimate of the true Lipschitz constant, the computational cost of function eval- uations may outweigh the savings in gradient evaluation and even memoryless backtracking might
30

---

Published as a conference paper at ICLR 2025
not improve the baseline method. This is the case for the COVTYPE dataset from LIBSVM (Chang Lin, 201 I), as shown by Fig. 19b, in Appendix D.2.
The corresponding stable values of for the adaptive counterpart of AGD lie in the upper interval (0.7, 1) and usually greater values of p make the adaptive variant more stable but also more com- putationally expensive. AGD with regular memoryless backtracking fails to consistently converge for values of outside the interval (0.3, 0.5). In fact, on COVTYPE, for at least one of the initial step-sizes, AGD with regular memoryless backtracking line search fails to converge. On the other hand, as shown in Fig. 19b in Appendix D. the adaptive variant converges for p = 0.9 and even for p 0.7, the more unstable end of feasible p values.
31

---

Published as a conference paper at ICLR 2025
D.1
MONOTONE BACKTRACKING LINE SEARCH
10
GD
p=03 0.5
P
0.9
0.96
AD
10
3
10-6
50000
50000
50000
50000
le1
1e2
1e3
le4
(a) ADULT.
100
GD
0.5
p=077
0.9
0.90
AD
10-3
10-6
50000
50000
50000
50000
1e1
1e2
1e3
1e4
(b) GISETTE SCALE.
10
0.3G
10
10-4
50000
50000
50000
50000
le1
le2
1e3
le4
(c) MNIST.
10
GD
p-0 0.5
0-07
p-
p- 0.96
10-2
10-6
10000
10000
10000
10800
1e1
1e2
1e3
1e4
(d) MUSHROOMS.
Figure 8: Logistic regression on four different datasets and four initial step-sizes Org
(10t. 102, 10 10*) T. suboptimality gap for GD, GD with standard backtracking line search using E (0.5, 0.7, 0.9, 0.95) and GD with adaptive memoryless backtracking line search using p 0.9. The light gray horizontal dashed line shows the precision used to compute performance for each dataset.
32

---

Published as a conference paper at ICLR 2025
10
GD
p-0.5 0.5
p0077
p 0.9
pm 0.96
AD
10-3
10-7
20000
20000
20000
20000
le1
1e2
1e3
1e4
(a) PHISHING.
10
GD
p=0.5
p-077
0.9
0.96
AD
4
10 2
f(
10-6
20000
20000
20000
20000
1e1
1e2
1e3
1e4
(b) PROTEIN.
10
GD
0.5
0.9
0.96
10-4
10
10000
10000
10000
10000
1e1
1e2
1e3
1e4
(c) WEB-1. 1.
Figure 9: Logistic regression on four different datasets and four initial step-sizes Og
(10* 10a 10a. LL: suboptimality gap for GD, GD with standard backtracking line search using E (0.5, 0.7, 0.9, 0.95) and GD with adaptive memoryless backtracking line search using p == 0.9. The light gray horizontal dashed line shows the precision used compute performance for each dataset.
33

---

Published as a conference paper at ICLR 2025
10
AGD
p 0.
00
p 0000
p-0.6
4D
10-5
10
5082
5082
5082
5082
1e1
1e2
1e3
1e4
(a) ADULT.
100
AGD
0.5
p=0.7
p-00
p- 0.36
AD
fx
10
f(
10-10
2574
2574
2574
2574
1e1
1e2
1e3
1e4
(b) GISETTE SCALE.
109
AGD
p=0g
p=0%
AD
10
10-10 10
1e1
1e2
1e3
1e4
(c) MNIST.
101
AGD
10-4
f(ztt)
10-10
lel
1e2
1e3
1e4
MUSHROOMS.
Figure 10: Logistic regression on four different datasets and four initial step-sizes (10', 102, 103 / suboptimality gap for AGD, AGD with standard backtracking line search using E {0.5, 0.7, 0.9, 0.95] and AGD with adaptive memoryless backtracking line search using p 0 The light gray horizontal dashed line shows the precision used to compute performance for each dataset.
34

---

Published as a conference paper at ICLR 2025
100
AGD
p 0.
p 0000
AD
10
10
3232
3232
3232
3232
le1
1e2
1e3
1e4
(a) PHISHING.
10
ACD
0.5
p=0.7
p- 3.9
p- 0.90
AD
10-4
f
10-10
11840
11840
11840
11840
1e1
1e2
1e3
1e4
(b) PROTEIN.
100
AGD
p=0d
p=0
AD
10
10-10 10
1e1
1e2
1e3
1e4
(c) WEB-L 1.
Figure 11: Logistic regression on four different datasets and four initial step-sizes ap (10*, 102, 10 104}/L: suboptimality gap for AGD, AGD with standard backtracking line search using E {0.5, 0.7, 0.9, 0.95] and AGD with adaptive memoryless backtracking line search using p = 0.9. The light gray horizontal dashed line shows the precision used to compute performance for each dataset.
35

---

Published as a conference paper at ICLR 2025
10-1
Adagral
p-0. 0.5
p 0.9
pm 0.66
AD
10
10-7
50000
50000
50000
50000
lel
1e2
1e3
1e4
(a) ADULT.
10a
Adagred
p-05
0.7
0.35
.DD
10-3
f(
10-10
50000
50000
50000
50000
le1
1e2
1e3
1e4
(b) GISETTE SCALE.
101
Adsgrad
p=0
p=
AD
10
10-10
50000
1e1
1e2
1e3
1e4
(c) MNIST.
10-1 -1
Absarol
0.95
10-10
le1
1e2
1e3
1e4
MUSHROOMS.
Figure 12: Logistic regression on four different datasets and four initial step-sizes (10', 102, 10 10 L: suboptimality gap for Adagrad, Adagrad with standard backtracking line search using p (0.5. 0.7, 0.9, 0.95) and Adagrad with adaptive memoryless backtracking line search using p = 0.9. The light gray horizontal dashed line shows the precision used to compute performance for each dataset.
36

---

Published as a conference paper at ICLR 2025
10-1
Adagral
pm0. 0.5
p-0.7
p 0.9
pm 0.95
AD
10-4
10-7
20000 0
20000 0
20000
20000
le1
1e2
1e3
1e4
(a) PHISHING.
10a
Adagrad
p-00
p-077
2.95
AD
10-3
f(zz)
10-10
5000
5000
5000
5000
le1
1e2
1e3
1e4
(b) PROTEIN.
100
Adagrad
0.5
0.9
p=0
AD
10
10-10 10
3000
3000
1e1
1e2
1e3
1e4
(c) WEB- 1.
Figure 13: Logistic regression on four different datasets and four initial step-sizes Cp (10*, 102, 10 10 )/ L: suboptimality gap for Adagrad, Adagrad with standard backtracking line search using p E (0.5, 0.7, 0.9, 0.95] and Adagrad with adaptive memoryless backtracking line search using p 0.9. The light gray horizontal dashed line shows the precision used to compute performance for each dataset.
37

---

Published as a conference paper at ICLR 2025
D.2
MEMORYLESS BACKTRACKING LINE SEARCH
(0.3, 1e2]
(0.3, 1e4)
ad [0.3, 1o4)
14.
gisette Scale
MNIST
protein
10
10t2
10
10
10
10
10
10
10a
10"4
10
10"1
500
1000
1000
2000 [s)
3000
1000
2000
3000
time [s]
time
Figure 14: step-sizes for experiments shown Fig. 1. Baseline: GD with constant as = L/L; reg (p,8) and ad (p. B): GD with, respectively, regular and adaptive memoryless BLS parameterized by and Cr. = 3/ L. The thick black dashed line denotes I/L, where Amax A) 44n
(0.6, le1)
10.6, 1e2)
ad Ie2)
1/.
MNIST
10-4
10-3
10-1
time 1000
time
Figure 15: step-sizes for experiments shown in Fig. 2. Baseline: AGD with constant as = 1/L; reg (p, () and ad (): AGD with, respectively, regular and adaptive memoryless BLS parameterized by and ag = B/ L. The thick black dashed line denotes 1/ L,, where = Amax (A A)/4n.
100
p-
10-3
10-7
1e1
1e2
1e3
1e4
(a) ADULT.
Figure 16: Logistic regression on four different datasets and four initial step-sizes (10t. 102, 10 104)/T. T. suboptimality gap for GD, GD with standard memoryless backtracking line search using p E {0.2, 0.3, 0.5, 0.6} and GD with adaptive memoryless backtracking line search us- ing p = 0.3. The light gray horizontal dashed line shows the precision used to compute performance for each dataset.
38

---

Published as a conference paper at ICLR 2025
100
GD
0.2
05
p 0.5
p 0.5
AD
10-5 -5
10
50000
50000
50000
50000
1e1
1e2
1e3
1e4
(a) GISETTE_ LISETTE_SCALE,
10
0.2
0.3
05
0.5
AD
10-3
f(
10-7
50000
50000
50000
50000
le1
1e2
1e3
1e4
(b) MNIST.
101
GD
0.2
05
AD
10
10-10
1e1
1e2
1e3
1e4
(c) MUSHROOMS.
Figure 17: Logistic regression on four different datasets and four initial step-sizes Cp (10*, 102, 10 104)/L L:: suboptimality gap for GD, GD with standard memoryless backtracking line search using & E {0.2, 0.3, 0.5, 0.6) and GD with adaptive memoryless backtracking line search us- ing p 0.3. The light gray horizontal dashed line shows the precision used compute performance for each dataset.
39

---

Published as a conference paper at ICLR 2025
100
GD
0.2
0.5
P-06 0.5
AD
10 -5
10
20000
20000
20000
20000
1e1
1e2
1e3
1e4
(a) PHISHING.
10
GD
0-0.2
0.5
05
p=05
AD
10-4
f
10-10
20000
20000
20000
20000
1e1
1e2
1e3
1e4
(b) PROTEIN.
100
GD
0.2
05
AD
10
10-10
1e1
1e2
1e3
1e4
(c) WEB- 1.
Figure 18: Logistic regression on four different datasets and four initial step-sizes Cp (10* 10a 10 104)/L L: suboptimality gap for GD, GD with standard memoryless backtracking line search using & E {0.2, 0.3, 0.5, 0.6) and GD with adaptive memoryless backtracking line search us- ing p 0.3. The light gray horizontal dashed line shows the precision used compute performance for each dataset.
40

---

Published as a conference paper at ICLR 2025
10
AGD
pm02
0.5
0.5
AD
10 55
10
6000
6000
6000
6000
1e1
1e2
1e3
1e4
(a) ADULT.
102
AGD
0-0
A-
0.5
0=5.
AD
4
10
f(
10-9
30000
30000
30000
30000
1e1
1e2
1e3
1e4
(b) COVTYPE.
100
p=
0.3
0.5
10
10
4632
1e1
1e2
1e3
1e4
(c) GISETTE_ _SCALE.
10a
fx
10-5
f(zz)
10-10
lel
1e2
1e3
1e4
(d) MNIST.
Figure 19: Logistic regression on four different datasets and four initial step-sizes (10', 102, 10 104) suboptimality gap for AGD, AGD with standard memoryless backtrack- ing line search using P {0.2, 0.6) and AGD with adaptive memoryless backtracking line search using p = 0.9. The light gray horizontal dashed line shows the precision used to compute performance for all methods, 10-9.
41

---

Published as a conference paper at ICLR 2025
10a
AGD
pm02
p 0.5
0.5
p 06
AD
10 -4
10
3000
3000
3000
3000
1e1
1e2
1e3
1e4
(a) MUSHROOMS.
100
AGD
p-02
0.3
AD
f
10 10-5
f(
10-10
3079
3079
3079
3079
1e1
1e2
1e3
1e4
(b) PHISHING.
101
AGD
p=0
03
p=06
AD
10
10-10
1e1
1e2
1e3
1e4
(c) PROTEIN.
100
10-5
f(zz)
10-10
lel
1e2
1e3
1e4
WEB-1.
Figure 20: Logistic regression on four different datasets and four initial step-sizes (10', 102, 10 10t) suboptimality gap for AGD, AGD with standard memoryless backtrack- ing line search using P {0.2, 0.6) and AGD with adaptive memoryless backtracking line search using p = 0.9. The light gray horizontal dashed line shows the precision used to compute performance for all methods, 10-9.
42

---

Published as a conference paper at ICLR 2025
10-1
Adagral
p- 0.2
pam 0.5
pm 05
AD
10
10-7
20000
20000
20000
20000
le1
1e2
1e3
1e4
(a) ADULT.
10a
Adarra
p-0.2
0.5
p- 3.5
p=0.5 0.5
.DD
10
f
10-10
50000
50000
50000
50000
1e1
1e2
1e3
1e4
(b) GISETTE SCALE.
101
Adagral
0.2
p=05 0.
ADD
10
10-10
20000
1e1
1e2
1e3
1e4
(c) MNIST.
10-1 11
Adgrrd
10-10
1el
1e2
1e3
1e4
MUSHROOMS.
Figure 21: Logistic regression on four different datasets and four initial step-sizes (10', 102, 10 10*)/L: suboptimality gap for Adagrad, Adagrad with standard memoryless back- tracking line search using (0.2, 0.3, 0.5, 0.6} and Adagrad with adaptive memoryless backtrack- ing line search using P = 0.3. The light gray horizontal dashed line shows the precision used to compute performance for each dataset.
43

---

Published as a conference paper at ICLR 2025
10-1
Adagral
p- 0.2
pmm 0.5
pm 05
pm 00
AD
10
10-7
20000
20000
20000
20000
le1
1e2
1e3
1e4
(a) PHISHING.
10a
Md
p-0.2
P-
0-03
p- 0.5
AD
10-3
f(zz)
10-10
5000
5000
5000
5000
1e1
1e2
1e3
1e4
(b) PROTEIN.
100
Adugral
p=
0.5
0.5
AD
10
10-10 10
1e1
1e2
1e3
1e4
(c) WEB-L 1.
Figure 22: Logistic regression on four different datasets and four initial step-sizes Cp = {10* 102, 10 10*}/L: suboptimality gap for Adagrad, Adagrad with standard memoryless back- tracking line search using E {0.2, 0.3, 0.5, 0.6} and Adagrad with adaptive memoryless backtrack- ing line search using p = 0.3. The light gray horizontal dashed line shows the precision used to compute performance for each dataset.
44

---

Published as a conference paper at ICLR 2025
E LINEAR INVERSE PROBLEMS
Dataset details. We consider A observations from eight datasets: IRIS, DIGITS, WINE, OLIVETTI_FACH and LFW _FW_PAIRS from scikit-learn (Pedregosa al., 2011), SPEAR3 and SPEARI0 (Lorenz et al., 2014) and SPARCO (van den Berg et al., 2007). For multi-class datasets, the first two considered. The number of datapoints and dimensions of each dataset can be found on Table 5,
Table 5: Details of FISTA experiments.
dataset
datapoints
dimensions
Lo
digits
360
10-1
1, 1, 10 10a
iris
100
4
10-2
10-1,1,10",10 102
Ifw_pain
2200
5828
10-3.10-2.10-1,
10-3,
siveeti_facce
20
4096
10-2
1010",10",10$
Spear3
512
1024
10-1
10-3,10-2.10-1
Spear 10
512
1024
10
10-3,10-2.10-1;
Sparco3
1024
2048
10
10-3,10-2,,0-1
wine
130
13
10-2
1,100,10,,00
301
p-05
p-02
102
10-3
10-4
10-11
2
5
10
(a) SYNTHETIC.
P-05
6
0-02
40
207
10-2
30-4
10
10-1
10
22500050007500000000
125000500075000000000
12500030007500000000
(b) OLIVETTI OLIVETTI_FACES FACES.
Figure 23
45

---

Published as a conference paper at ICLR 2025
104
10-2
1250
2300 5750 3000
1250
20:00
3750 3000
1250
2002
3750
5000
1250
2000
3750 5000
10
(a) IRIS.
30
107
107
10-
123000500005200000000
12500050007500500000
325000
1250005000875/05000
10
(b) WINE.
p=0s
a-02
101
10-1
30 -.-
10-9
10-11
3riossndop
10
(c) DIGITS.
Figure 24
46

---

Published as a conference paper at ICLR 2025
F MATRIX FACTORIZATION EXPERIMENTS
We sample from the file "u.data", part of the Movielens 100K dataset (grouplens, wwrouuulen.rrro.. datasets moviilenss//////mmmmmme 100kk)). Moreover, we choose the precision representing reduction 10-12 in the suboptimality gap, which corresponds to a lower bound of 10 as the initial objective values typically hover around 10?.
107
101
10-5
10000
10000
20000
10000
5e-02
5e-01
5e0
(a) Rank 10.
107
GD
0.2
0.3
0.5
0.6
ADLS
f.
10a
f(
10
30000 0
30000 0
30000
J0000
5e-02
5e-01
5e0
5e1
(b) Rank 20.
107
GD
0.2
0.3
0.5
0.6
ADLS
I.
10a
10-5
50000
5e-02
5e-01
5e0
5e1
(c) Rank 30.
Figure 25: Matrix factorization and three values of rank: suboptimality gap for gradient descent, gradient descent with standard backtracking line search using p {0.2, 0.3, 0.5, 0.6} and gradient descent with adaptive backtracking line search using & = 0.3. The light gray horizontal dashed line shows the precision used compute performance for all methods, 10-5
47


Reviews:
[{"review_id": "W4eVnzYaUS", "reviewer": "Reviewer_RAP1", "summary": "This paper studies the backtracking line search commonly used for step size selection in optimization algorithms. The main focus is to propose an adaptive approach for setting the decay parameter when searching for the step size. The authors consider several examples (e.g., Armijo, descent lemma) to illustrate the concept, which is straightforward and presented in Algorithm 2. They also conduct extensive numerical simulations to demonstrate the effectiveness of the adaptive approach.", "questions": "See above.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "Backtracking line search is a fundamental task in general optimization algorithms. The numerical simulations show promising potential for the adaptive method.", "weaknesses": "As my work primarily focuses on the theoretical aspects of optimization, my comments and concerns mainly relate to the theoretical analysis of the proposed adaptive approach. Broadly speaking, the theorems presented in Section 4 provide limited insight into the advantages of the new approach compared to the conventional backtracking line search in Algorithm 1. I will elaborate on this and discuss other concerns below.\n\n* My main technical concern is with the lower bound of the adaptive factor, which will affect the overall complexity of the algorithm, not just the number of function evaluations in a single iteration step. As mentioned by the authors in Line 395, the search procedure should ensure a sufficiently large step size to achieve fast convergence. Following this, the authors argue that their construction guarantees that the adaptive factor is bounded away from zero. However, this is not sufficient to ensure convergence of the (outer-loop) algorithm iteration sequence, as the step size can be arbitrarily small compared to the step size selected by \"regular\" line search (for example, in the descent lemma setting, the regular search will produce a step size lower bounded multiplicatively by the factor $\\rho$). Indeed, using some standard theorems for smooth optimization, the adaptive factor appears in the final complexity guarantee and may not be easily controlled. Therefore, an important task here is to investigate the overall evaluation complexity when the proposed adaptive line search is used.\n\n* As for the theorems presented in Section 4, specifically Propositions 1, 2, and the two informal theorems, it seems that these results do not demonstrate the advantage of using an adaptive approach compared to the regular search method. These results essentially state that, under certain assumptions, the adaptive approach is not worse than the regular method in terms of the number of function evaluations in a single step. Also, as mentioned above, it is unclear how this affects the total number of iterations in the outer loop.\n\n* The first question that likely arises after seeing Algorithm 2 is how to design the adaptive factor $\\hat{\\rho}$. The authors demonstrate some possible constructions in Section 2, but these are mostly reformulations of known methods. Thus, is there a principled way to construct this adaptive factor, even for specific settings?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mBWKaYsbuk", "reviewer": "Reviewer_Qk4F", "summary": "This paper proposes an \"adaptive\" version of backtracking line search (BLS) for descent steps in optimization. Namely, while in classical BLS the candidate step-size shrinks by a fixed factor of $\\rho$, this paper proposes an adaptive choice of $\\rho$ at each iteration which depends on how much the line-search condition is violated. The paper demonstrates in a series of experiments that this adaptive version of BLS seems to be more robust to starting point and usually leads to significant savings in compute-time if compared to classical BLS with a fixed rate. Moreover, they show theoretical results demonstrating that, in convex and/or Lipschitz smooth problems, Adaptive BLS is *effectively* no worse than BLS and the worst-case step-size guarantee are similar.", "questions": "- Do you think it would be interesting to compare adaptive BLS with LS with polynomial interpolation (mainly quadratic or cubic)? It seems to me it would be a more interesting comparison than simply comparing with fixed-parameter BLS, but the authors could disagree with me. Also, I believe there is likely other methods or heuristics used in the literature that should be at least acknowledge an briefly discussed in the paper;\n\n- Are there other relevant research work on BLS that the authors are aware? The two papers I referenced I found on a brief web search, thus I only found somewhat recent work that hasn't been necessarily published yet (although one of them appeared in 2019 as a workshop paper), and I am quite certain that the authors are more better acquainted with the literature in the area than myself;", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Usually papers on backtracking line-search tend to focus on effects of non-monotonic searches or on changing the condition of the line-search. This paper proposes a seemingly simple modification to the choice of the backtracking factor that preserves most of the theoretical guarantees. This seems like one of those simple observations that is of interest to the optimization community in general. In fact, I think the contribution is good exactly because of the simplicity: there seems to be a easy modification to BLS that most likely improves it;\n- The presentation is relatively clear and easy to understand;\n- The variety of experiments gives confidence about the empirical performance of the method if compared to BLS with a fixed parameter;", "weaknesses": "I believe the main area of improvement of this paper is its discussion previous work, which is even more important in a paper about such a classical topic.  I will detail two aspects of the paper that I believe could be improved.\n\n- **Discussion of related research work**: Backtracking line-search is a classical topic with a vast amount of work on it (even if most of it is not necessarily on the backtracking factor). Yet, besides references to classical books and the original works on BLS, there is almost no discussion of previous work. Although I am not familiar with the most recent work on line-search, while reviewing this paper I found at least two papers [1,2] that should at least have been cited, and probably this line of research discussed in more depth. \n\n- **Lack of comparison with line-search variants**: The paper focuses on backtracking line-search with a fixed backtracking parameter $\\rho$ as the main method they are comparing against. However, there are classical variants of this idea that are more often used in practice, and the main one that comes to mind is polynomial interpolation, and there are likely other heuristics the authors could have at least discussed.  Moreover, a quote from the classical textbook [3, Sec. 3.1] mentions that BLS with a varying backtracking parameter is more often used in practice:\n\n> In practice, the contraction factor $\\rho$ is often allowed to vary at each iteration of the line search. For example, it can be chosen by safeguarded interpolation, as we describe later. We need ensure only that at each iteration we have $\\rho\\in [\\rho_{\\mathrm{lo}},\\rho_{\\mathrm{hi}}]$, for some fixed constants $0 < \\rho_{\\mathrm{lo}} < \\rho_{\\mathrm{hi}} < 1$.\n\n---\n**Summary of review**: I believe the contribution of this paper is simple (in a good way) and relevant to the optimization community. However, the lack of discussion of recent related work and the sole focus on comparing against BLS with a fixed backtracking parameter does not seem to properly situate the contribution in the literature and to paint a fair picture of its impact in line-search methods in general, which is why I'm currently inclined to recommend a rejection of the paper. \n\nI hope to discuss with the authors about what related work they believe is relevant to be discussed and which other methods would be valid comparison points. Finally, I just want to make it clear that I do not believe that the adaptive BLS that this paper proposes needs to outperform all other variants of BLS to be a good contribution, or that the authors need to perform experiments against all other variants. However, there definitely should be a more in-depth discussion of related work and comparison with BLS vairants and heuristics.\n\n\n--- \n\n\n** References **\n\n[1] de Oliveira, Ivo Fagundes David, and Ricardo Hiroshi Caldeira Takahashi. \"Efficient solvers for Armijo's backtracking problem.\" arXiv preprint arXiv:2110.14072 (2021).\n\n[2] Fridovich-Keil, Sara, and Benjamin Recht. \"Approximately exact line search.\" arXiv:2011.04721 (2020). (This one seems to be a full version of a workshop paper: https://opt-ml.org/papers/2019/paper_17.pdf)\n\n[3] Nocedal, Jorge, and Stephen J. Wright. \"Numerical optimization\", Second Edition (1999)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CyQP9JfkSY", "reviewer": "Reviewer_QtPJ", "summary": "This paper describes a backtracking strategy suitable to both convex/non-convex and smooth/non-smooth optimisation which relies on the definition of a violation factor adjusting the decrease of the step-size along the iteration. Such factor quantifies the amount at which standard backtracking conditions (e.g., Armijo) are *not* satisfied and is thus cleverly used to choose an optimal decreasing factor. In comparison to, e.g., standard Armijo condition, this avoids unnecessary overdecrease of the step (in case of small factors) and high computational costs (in case of big ones, which makes the decrease slower).\nThe paper is a pleasure to read: the motivation is clearly given, some examples are used to motivate the strategy used and, before providing the main theoretical results, some triggering empirical evidence is provided. The main sets of experiments reported in the body of the paper are convincing and show improvements with standard backtracking line search w.r.t. to a suitable gain measure related mostly to computational evaluation. Experiments are performed in both convex and non-convex settings as well as in a convex non-smooth scenario where comparisons with FISTA are made.\nThe presentation of the theoretical results is complete and the appendices are very well written and substantiated. \nI congratulate with the authors for such a nice piece of work which, in my opinion, opens the path to many questions and future research directions additionally to the ones highlighted in the final section of this work.", "questions": "- I think that some further referencing should be added. In these works (DOI1: 10.1137/17M1149390, DOI2: 10.1137/21M1391699) adaptive backtracking strategies that could be generally employed for smooth/non-smooth and convex/strongly-convex optimisation schemes are considered. The main idea there is the possibility of the step-size to increase locally as long as the desired backtrcking conditions (there defined in terms of a Bregman distance of the smooth component) are used. Despite the adaptivity of the approach you propose, your backtracking strategy is still monotone (at least in the, indeed, monotone case). Is this really needed? Couldn't you allow also the local increase of the step-size, check if the condition is violated and, if not, allow it and, if yes, perform your strategy with suitable adjustments? I think that a comparison with these approaches should be added and such extension possibly considered.\nThe use of non-monotone approaches as the one mentioned above is interesting, for instance, where you have, for some reason, a very bad estimation of \\alpha_0  (e.g., very small) which as far as I undertsand, not even with your approach you would be able to inrease along iterations.\n- Another approach that is worth mentioning is the one studied here (Malitsky, Mishchenko Adaptive Gradient Descent without Descent\n PMLR 119:6702-6712, 2020) which is computationally very effective and relies on different backtracking rules adaptive to local geometry.\n- Your theoretical results aim at quantifying, essentially, the amount of backtracking iterations in comparison with the standard approaches, but can you indeed guarantee that usual convergence rates are obtained whenever the strategy is employed as an 'inner loop' of any underlying algorithm?\n- In some sections I found a bit of overlooking on the regularity properties of the problems considered and/or of the schemes employed. This in particular when you considered strongly convex optimistation schemes. In the non-smooth examples you considered AGD schemes adapted to strong convexity (e.g., relying on the knowledge/estimation of strong-convexity parameters) as in the case of Algorithm 4 (where I whink that m is indeed the strong convexity parameter although never mentioned) or not (FISTA). For strongly convex algorithms linear convergence is normally achieved, contrarily to convex ones where only O(1/k^2) speed is obtained. Some more precision on the reasons why you consider one or the other and on how potentially your idea adapts to situations where the strongly convex parameter is unknown (and estimated via restarting strategies, see, e.g., DOI3: 10.1137/23M158961X) should be added. This is interesting, for instance, when one wants to control oscillations due to inertia in accelerated schemes. Interestingly, you don't seem to have that many oscillations. Do you have any guess on why this happens? It is surely related to the adaptation to the local geometry of the function.\n- It's a bit surprising that for standard BLS, in the results in Figure 1 and t2, with the same \\rho, the convergence curve obtained with a higher value of \\beta (higher initial step-size), pink curves, lies *above* and not below the one with smaller step size. Is this due to the 'bad' adjustment of the step-size in the standard backtracking inner routine?\nI think it would be very interesting comparing the evolution of the step-size estimation along the iterations, in comparison with the (over)estimation of 2/L (convex) or 1/L (non-convex) used as a fixed reference.\n\n\n\n\nMinor points:\n- I would change notation in (5) on page 3, lines 151 and subsequent since, as you said, (5) has to hold for F (capital) while it looks it has to hold only for the smooth part. \n- Page 4, line (191) is somehow bizarre (the regularisation parameter can be anyhing), is there any reason why you relate this to \\bar{L}?\n- What is the stopping criterion for achieveing \"designated precision\" used in the experiments in section 3?\n- What is the interest of using accelerated schemes in the non-convex objective example? It's not clear that they improve at all the speed of convergence right?\n- In Figure 3 and the corresponding table you use the value of the non-convex loss functions as a measure of how good one approach is w.r.t. others. This may suggest that convergence to different local minimisers is achieved, althoutgh from the examples it seems that the trajectory is pointing towards the same local minimiser. So why is the loss smaller? Did you stop iterations after a max number of iterations and notice that in one case you got a lower value (closer to the one of the minimiser you are converging to)?\n- The two 1d illustrations in Figure 4 are enlightening but not clear at all without looking at the appendix. I would provide some more details in the main body of the paper\n- In the Informal Theorem on page 9 (line 477) what is the function \"g\"?\n- I would be careful with the use of the word \"restarting\" as in the standard optimisation community this is a strategy more concerned with the estimation  of the strongly convex parameter (see for instance DOI4: 10.1007/s10208-013-9150-3) than the step-size. Also, the use of the restarting strategy you propose sounds unnecessarily expensive. Why keep starting with the initial step-size especially when this is too big when one can use the last estimated one? You say that they seem to work much better but I imagine they require more inner checks?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper is very nicely written, the intuitition behind the proposed adaptive strategy is well described and the numerical tests are convincing. I liked the choice of the authors of presenting first the numerical results raather than the theoretical ones, since the reader is really triggered to keep reading and understanding more. The exhaustive list of experiments reported in the appendix is very convincing and shows that the proposed strategy performs indeed very well, as supported by the thoeretical results which I have checked and, up to some minor typos, appear correct to me.", "weaknesses": "The only \"weaknesses\" I could highlight relate to some (minor) lack of referencing to existing work and/or to some refinement that could be made to guarantee that the proposed strategy maintains (as it seems) the convergence speed of stnadard algorithm also in more 'regular' scenario (e.g., strong convexity). Some minor imprecisions can be easily fixed as I will suggest below. \nUpon the modifications suggested (at all, or even partially), I think I would be happy to change my note to 10 as I think that this is a very good piece of work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "E2FxtEFBty", "reviewer": "Reviewer_vFwJ", "summary": "The paper proposes an enhancement to backtracking line search by introducing an adaptive adjustment to step size rather than the traditional multiplicative retraction. The basic idea is to not just backtrack when the acceptance criterion is not met but rather to use the violation information to adjust the backtracking factor. The empirical results demonstrate significant improvements in several cases and the authors also provide some theoretical justification for the performance.", "questions": "no questions - see above", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The empirical results are strong which in my books is also the main merit of the paper. The theory while nice/ok is not particularly spectacular or unexpected but does provide a nice complement to the observed performance in practice. \n\nStill I like the paper quite a bit and set my initial score to accept based on the computational benefits of the proposed approach.\n\n(while not strictly required to be read the appendix provides some additional computational results which are nice)", "weaknesses": "The paper feels a little thin on the contribution mostly consisting of strong empirical results. the underlying idea of a dynamic adjustment is nice but not particularly surprising. I personally very much like the paper, however I could understand if other reviewers find its theoretical contributions too little.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)