Adaptive backtracking line search

We are glad that the reviewer liked the paper and we are grateful for the notes.

We agree that one of the main merits of the paper is that the proposed adaptive backtracking routines seem to work well in practice, but we find the impression that ``the paper feels a little thin on the contribution mostly consisting of strong empirical results'' unjustified. In our view, there are two more important contributions. One is that the proposed subroutines are simple, which makes them easy to incorporate by different methods, as illustrated by the four different methods that could benefit from adaptive backtracking in the experiments. Given the prevalence of backtracking in optimization methods, presenting a simple way to potentially improve it can have a broad impact. Moreover, we believe that the paper also has an important conceptual contribution, which is to take into account the information conveyed by line search criteria more explicitly when choosing step sizes, which could lead to several new line search methods.

Furthermore, it is important to mention if the statement that ``the theory while nice/ok is not particularly spectacular or unexpected but does provide a nice complement to the observed performance in practice'' is true for our paper, then it would also be for many relevant line search methods. As argued at the beginning of section 4, the guarantees that we provide for adaptive backtracking are essentially the best one can hope for without making further assumptions on the objective function and without specifying the base method that calls adaptive backtracking. We included in Appendix B.4.1 (first paragraph) a quote from (J. Nocedal and S. J. Wright, Numerical optimization, 2006) that corroborates this opinion. Also, we reiterate that if the paper can be reproached for perceived lack of theory, then perhaps so could the highly influential original paper that proposed the Armijo condition, which is less than three pages long. Notwithstanding, in response to the reviewer's comments we have now added several convergence results in Appendix B.4. Most of them follow by substituting the corresponding line search condition and step size lower bounds in standard proofs, with the exception of the convergence result for AGD which is proven with a novel technique, to the best of our knowledge.

We really appreciate the reviewer's supportive review, extensive comments and suggestions. We hope to have addressed every point raised, but we are happy to take into account any further suggestions that the reviewer might have.

• "I think that some further referencing should be added": We thank the reviewer for pointing out to us these interesting references, which we now discuss in the "Additional algorithms and increasing step sizes'' part of Section 5.1. These approaches slightly increase the final step size of one iteration and then use it as the initial backtracking step size in the following one, similar to what the two-way method by Truong does. "The 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 understand, not even with your approach you would be able to increase along iterations.'' In the memoryless adaptive backtracking variant, the initial step size is constant, therefore the step sizes are generally nonmonotone. Moreover, as we mention in the paper, in principle adaptive adjustments can also be used to increase step sizes, but hybrid approaches are possible as well, where only the backtracking portion of the line search is adaptive, for example. We leave the investigation of further variants of adaptive line search to future work.

• "Another approach that is worth mentioning is the one studied here (Malitsky, Mishchenko Adaptive Gradient Descent without Descent" We are aware of that interesting paper, but their adaptive method does not actually enforce the same criterion that our adaptive backtracking subroutine does (the Armijo condition in this case), which is why had not mentioned it before.

• "can you indeed guarantee that usual convergence rates are obtained whenever the strategy is employed as an 'inner loop' of any underlying algorithm?" Yes, adaptive backtracking preserves convergence rates. We have added several such results to the appendix. Most of them follow from standard proofs by plugging in the step size lower bounds and noticing that (when $c \geq 1/2$) the Armijo condition implies the descent lemma, which is the main requirement on the step size for those arguments. The exception is the proof of accelerated convergence for AGD with adaptive backtracking, which to the best of our knowledge is novel.

• "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 [...] should be added" We chose methods that we felt were representative of different broad algorithmic families and that would show that adaptive backtracking performs well in various settings and is flexible enough to be seamlessly incorporated by many further methods. Indeed, the reference mentioned by the reviewer (now cited in the ``additional algorithms'' paragraph of section 5.1) is an example where it seems that adaptive backtracking could easily replace regular backtracking, since the enforced condition seems to be affine in the step size. "Interestingly, you don't seem to have that many oscillations. Do you have any guess on why this happens?'' In addition to its flexibility, adaptive backtracking seemingly picks more appropriate step sizes that end up reducing oscillations, which makes us optimistic that it could work well for methods that adopt nonmonotone step sizes and also simultaneously estimate other parameters.

• "I think it would be very interesting comparing the evolution of the step-size estimation along the iterations" Plotting step sizes was a good suggestion and we have now included Figures 12 and 13 in Appendix D.2 on page X that show the corresponding step sizes for Figures 1 and 2. In the new figures, we can see that initially adaptive backtracking returns smaller step sizes than regular backtracking, which seems to have lasting impacts afterwards. Regular backtracking returns the largest feasible step size within a factor of rho, which seemingly is not always good as the step sizes can be excessively large and lead to worse optimization paths (e.g., more zig-zagging). For AGD, adaptive backtracking step sizes converge, but regular backtracking step sizes do not necessarily. Regular backtracking can only return step sizes that are powers of rho multiplied by the initial step size, therefore when the steady state step size is somewhat in between two grid points, the returned step size can keep oscillating instead of settling down, which can perhaps degrade performance.

We would like to thank the reviewer for taking the time to evaluate our paper and for contributing with relevant references.

• "Discussion of related research work":The page limit constraint forced us to make some compromises and we ended up shortening the introduction, perhaps excessively. Also, most references are spread over the paper, where we felt was most pertinent, rather than at the beginning. For example, on page 2 we mentioned Armijo, Wolfe and nonmonotone conditions, as well as polynomial interpolation, where we cited Nocedal and Wright. But the majority of references can be found in the last section, where we thoroughly discuss several connections with recent line search methods. That being said, we are glad that the reviewer brought this issue to our attention and we will add a more thorough discussion of recent line search references, including the first two references.

• "Lack of comparison with line-search variants": Our focus in this paper is on backtracking subroutines that enforce a specific condition (Armijo's or the descent lemma.) The second paper mentioned by the reviewer does not enforce any specific condition, but is a rather ``general purpose'' subroutine that aims at finding an approximation of the step size returned by exact line search. Since the line search condition plays a fundamental role on the behavior of an optimization method, we did not consider appropriate to compare adaptive backtracking with their line search subroutine. On the other hand, the first reference does enforce the Armijo condition, but apparently did not release any code. Moreover, they also only compared their subroutine with regular backtracking. In particular, they do not consider a polynomial interpolation subroutine. This is also the case in the two papers mentioned by reviewer QtPJ, which also mostly compare the benefits of their subroutines with respect to standard backtracking subroutines enforcing the descent lemma. In fact, these two papers improve on the performance of the base method (FISTA), which originally implemented regular backtracking to enforce the descent lemma, without ever mentioning polynomial interpolation. Furthermore, we have not found any standard packages for polynomial interpolation to enforce the Armijo condition, because it is often not done. With this in mind, we believe that our decision of not including a comparison with polynomial interpolation is justified. Indeed, our goal was to showcase the potential benefits of adaptive backtracking relative to regular backtracking in terms of performance improvement, irrespective of the choice of $\rho$. This is in particular because standard backtracking is still the de facto standard given its simplicity and ease of implementation. Our method similarly simple and easy to implement.

Questions

• We do believe it would be an interesting comparison, but given the reasons mentioned in the first bullet above, we instead decided to dedicate our available computational effort to thoroughly sweeping over several values of $\rho$ for regular backtracking.
• Yes, there are quite a lot of exciting recent developments in line search that provide several lines of work for future research, as we discuss in section 5.

We thank the reviewer for considering our response. To fully address the final outstanding concern regarding proper mention to related work, we have now added section 2.3 to the main paper, in which we summarize the above discussions. We hope that this addition further improves the presentation of the paper and allows the reviewer to adjust their score accordingly. If the reviewer has any additional feedback to help us improve the paper's soundness, presentation and contribution scores, we would appreciate the opportunity to address them.

We would like to thank the reviewer for reading our paper and for the comments, which we address below.

• "as the step size can be arbitrarily small compared to the step size selected by `regular' line search": It seems there was a misunderstanding here. For both the Armijo condition and the descent lemma, the step size itself enjoys nontrivial positive lower bounds, presented in the last sentences of the informal theorems. Namely, for the Armijo condition with $L$-smooth objective and gradient related descent directions with constants $c_{1}$ and $c_{2}$, the step-size returned by our adaptive procedure satisfies

which matches the lower bound for the step-size returned via regular backtracking (please consult proofs for more details.) Likewise, the step size lower bound for the step-size returned by the descent lemma is

With these lower bounds we are able to establish worst-case convergence results for specific base methods that call adaptive backtracking, which can be found in appendix B.4 of the updated manuscript. Some simplified instances of these results are:

Gradient descent If $f$ is $L$-smooth, $\alpha_{0}>1/L$ and $c= 10^{-4}$ for GD (where $c_1 = c_2 = 1$)

Accelerated gradient descent If $f$ is $L$-smooth and $m$-strongly convex, $\alpha_{0} < 1/m$ and $c=1/2$, then

where $Q=L/m$ denotes the condition number of the problem. Complete statements and proofs of these and more results are now included in Appendix B.4. Most of them are straightforward extensions of standard proofs, except for the AGD result, which we prove with a technique that is novel, to the best of our knowledge.

• "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." Iterates are bounded for most choices of descent direction (e.g., GD), therefore to prove that adaptive backtracking requires no more function evaluations than regular backtracking, it suffices that the gradient be continuous, not even that a global smoothness constant $L$ exists. Furthermore, to derive explicit lower bounds on the returned step size, the smoothness assumption is necessary for both adaptive and non-adaptive backtracking and is standard in most convergence proofs of gradient-based methods (e.g., theorem 3.2 of [1]).

• "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?" We argue that requiring that $\hat{\rho}(v(\alpha_{k})) \in (0,\rho)$ while matching the lower bound of standard backtracking is a principled way of constructing the adaptive factor. Notwithstanding, whenever the line search criteria are affine in the step size, as in the Armijo condition and in the descent lemma, one can isolate the step size on one side of the inequality, take the other side as a candidate for the adaptive step size and then extract $\rho$ and $v$ from that expression accordingly. Finally, we would like to stress that none of the constructions that we present is a reformulation of a known method. In fact, the base methods (GD, AGD, etc.) are known, but not the line search procedure that is used to generate feasible step sizes.

In summary, our theoretical results match those for backtracking line search (in addition to showing our factor is more aggressive at finding feasible step sizes) and we perform extensive experiments to showcase its advantage. Our procedure can be applied to many baseline algorithms and we demonstrated its advantage on several. We also rigorously show why we couldn't hope for much more from a theoretical characterization of a backtracking scheme unless we narrow the set of problem instances we consider and specify the base method that is calling backtracking. Notwithstanding, in response to the reviewer's comments we have now added several convergence results to the appendix. Most of them follow by substituting the corresponding line search condition and step size lower bounds in standard proofs, with the exception of the convergence result for AGD which is proven with a novel technique, to the best of our knowledge.

Finally, we hope that the reviewer would agree that if the paper can be reproached for perceived lack of theory, then perhaps so could the original highly influential paper that proposed the Armijo condition, which is less than three pages long with a similar amount of theory.