Don't be so Monotone: Relaxing Stochastic Line Search in Over-Parameterized Models
Authors: Leonardo Galli
Holger Rauhut
Mark Schmidt
Venue: NeurIPS 2023 poster (2023)
Keywords: line search
nonmonotone
stochastic gradient descent
over-parametrized models
Polyak step size
optimization
TL;DR: Nonmonotone stochastic line search methods outperform SGD, Adam and their monotone counterpart for training over-parameterized models.

Abstract: Recent works have shown that line search methods can speed up Stochastic Gradient Descent (SGD) and Adam in modern over-parameterized settings. However, existing line searches may take steps that are smaller than necessary since they require a monotone decrease of the (mini-)batch objective function. We explore nonmonotone line search methods to relax this condition and possibly accept larger step sizes. Despite the lack of a monotonic decrease, we prove the same fast rates of convergence as in the monotone case. Our experiments show that nonmonotone methods improve the speed of convergence and generalization properties of SGD/Adam even beyond the previous monotone line searches. We propose a POlyak NOnmonotone Stochastic (PoNoS) method, obtained by combining a nonmonotone line search with a Polyak initial step size. Furthermore, we develop a new resetting technique that in the majority of the iterations reduces the amount of backtracks to zero while still maintaining a large initial step size. To the best of our knowledge, a first runtime comparison shows that the epoch-wise advantage of line-search-based methods gets reflected in the overall computational time.

Don't be so Monotone: Relaxing Stochastic Line Search Over-Parameterized Models
Leonardo Galli, Holger Rauhut RWTH Aachen University
Mark Schmidt
University of British Columbia Canada CIFAR AI Chair (Amii) schmidtmecs. .ubteccs.ub.c.. ubc.ca
Aachen
fgalli,
Abstract
Recent works have shown that line search methods speed up Stochastic Gradi- ent Descent (SGD) and Adam modern wee-pparameterized settings. However, existing line searches may take steps that smaller than necessary since they require a monotone decrease of the (mini-)batch objective function. We explore nonmonotone line search methods relax this condition and possibly accept larger step sizes. Despite the lack of a monotonic decrease, we prove the same fast rates of convergence in the monotone case. Our experiments show that nonmono- tone methods improve the speed of convergence and generalization properties SGD/Adam even beyond the previous monotone line searches. We propose a POlyak NOnmonotone Stochastic (PoNoS) method, obtained by combining a nonmonotone line search with Polyak initial step size. Furthermore, we develop a new resetting technique that in the majority of the iterations reduces the amount of backtracks to zero while still maintaining large initial step size. To the best of our knowledge, a first runtime comparison shows that the epoch-wise advantage of line-search-basee methods gets reflected in the overall computational time.
Introduction
Stochastic Gradient Descent (SGD) [Robbins and Monro [951] the workhorse for the whole Deep Learning (DL. activity today. Even though its simplicity and low memory requirements seem crucial for dealing with these huge models, the success of SGD strongly connected the choice of the learning rate. In the field of deterministic optimization [Nocedal and Wright (006). this problem is addressed [Armijo| 1966) by employing a line search technique to select the step size. Following this approach, recent branch of research has started to re-introduce the use of line search techniques for training DL models [Mahsereci and Hennig 2017 Paquette and Scheinberg 2018 Bollapragada et al. 2018 [Trunng and Nguyen 2018 Vaswani et al. 2019]. These methods have been shown to speed up SGD Vaswani et al. 2019] and Adam [Duchi et al., [201]] Vaswani et al. 2020 in the weertearameerrize regime. However, the existing stochastic line searches may take step sizes that smaller than necessary since they require a monotone decrease in the (mini-)batch objective function. In particular, the highly non-linear non-convex landscapes of DL training losses suggest that it may be too restrictive to impose such condition [Grippo et al. 1986). In addition, the stochastic nature of directly the one we are minimizing [Ferris and Lucidi 1994) (mini- vs full-batch function). Furthermore, the recent research on the edge of stability phenomenon [Cheen et al. 2021 Nacson et al.) 2022 shows that the best performance for training DL models with Gradient Descent (GD) is obtained when large step sizes yield nonmonotone decrease of the loss function. In this paper, we propose the use of nonmonotone line search methods [Gripoo et al., 1986 Zhang and Hager 2004 to possibly accept increases in the objective function and thus larger step sizes.
SGD discourages imposing a monotone requirement on a function that
In parallel with line search techniques, many other methods [aydin et al. 2017 Luo et al. 2019
Mutschler and Zell 2020 Truong and Nguyen 2021 have been recently developed to automatically
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

select the step size. In Asi and Duchi 2019]. Berrada et al. [2020] Loizou et al. [202T] Gower et al.
[222]] 2022]. Li et al. 2 the Polyak step size from Polyak 1969 has been adapted SGD and successfully employed to train DL models. However, in this setting, the Polyak step size may become very large and it may lead to divergence or, more favorable cases, induce the (mini-batch) function to decrease nonmonotonically. Starting from [Berrada et al. (2020). the Polyak step size has been upper-bounded to avoid divergence and "smoothed" to prevent large fluctuations [Loizou et al. 2021]. However, this "smoothing" technique is a heuristic and, as we will clarify below, may reduce the Polyak step more than necessary. In this paper, we instead combine the Polyak initial step from Loizou et al. [2021] with nonmonotone line search. In fact, nonmonotone methods are well suited for accepting as often as possible a promising (nonmontone) step size, while still controlling its growth. In the deterministic setting, the same optimization recipe has been used in the seminal papers |aydan] [197]] (for the Barzilai and Borwein 1988) (BB) step size) and Grippo et al. 1986 (for the unitary step in the case of Newton).
In the over- pre-terrameterized regime, the number of free parameters dominates the number of training samples. This provides modern DL models with the ability of exactly fitting the training data. In practice, over-parameterizzd models are able to reduce to zero the full-batch loss and consequently also all the individual losses. This is mathematically captured by the interpolation assumption, which allows SGD with non-diminishing step sizes to achieve GD-like convergence rates [Vaswani et al., 2019]. We develop the first rates of convergence for stochastic nonmonotone line search methods under interpolation. In the non-convex case, we prove a linear rate of convergence under the (PL) condition. In fact in Liu et al. 22222. it has been shown that wide neural networks satisfy a local version of the PI. condition, making this assumption more realistic for DL models than the Strong Growth Condition (SGC) (Schmidt and Le Roux 2013
When considering line search methods for training DL models one has to take into account that they require one additional forward step for each backtrack (internal iteration) and each mini-batch iteration requires an unknown amount (usually within 5) of backtracks. A single forward step may require up to one-third the runtime of SGD (see Section E.6 of the supplementary materials), thus, too many of them may become a computational burden. Le Roux et al. (2012) proposed a "resetting" technique that is able to (almost) always reduce the number of backtracking steps zero by shrinking the initial step size [Vaswani et al., 2019]. In this paper, we will show that this technique may safeguard (as
have a negative impact on the speed of convergence, even when only employed in the "smoothing" technique [Loizou et al., (021]). As a third contribution, we develop a new resetting technique for the Polyak step size that reduces (almost) always the number of backtracks to zero, while still maintaining a large initial step size. To conclude, we will compare the runtime of different algorithms to show that line search methods equipped with our new technique outperform non-line-search-base algorithms.
2 Related Works
The first nonmonotone technique was proposed by Grippo et al. [1986] to globalize the Newton method without enforcing monotonic decrease of the objective function. After that, nonmonotone techniques have been employed to speed up various optimization methods by relaxing this monotone requirement. A few notable examples are the spectral gradient in Raadan] [1997), the spectral projected gradient in Birgin al. (000), sequential quadratic programming methods in Zhou and Tits 1993], and the Beaa--Ribere-Polyeee conjugate gradient in Zhou 2013).
In the pre-deep-l era (Plagianakos al. 2002). shallow neural networks have been trained by combining the nonmonotone method [Grippo et al.] 1986) with GD. In the context of speech recognition [Keskar and Saon 2015), one fully-connected neural network has been trained with a combination of a single-pass full-batch nonmonotone line search [Grippo et al. [9866 and SGD, The Fast Inertial Relaxation Engine (FIRE) algorithm is combined with the nonmonotone method (Zhang and Hager 2004] in Wang et al. [2019] 2021 for solving sparse optimization methods and training logistic regression models, while manually adapted learning rate is employed to train DL models. In Krejić and Krklec Jerinkič [2015] 2019). Bellavia et al. [202T], the nonmonotone line search by Li and Fukushima [1999 is used together with SGD to solve classical optimization problems. In concurrent work [Hafshejani et al. 2023]. the nonmonotone line search by Grippo et al. (9866 has been adapted to SGD for training small-scale kernel models. This line search maintains a nonmonotone window W (usually 10) of weights in memory and it computes the current mini-batch

---

function value on all of them at every iteration. The method proposed in Hafshejani et al. [2023] is computationally very expensive and impractical to train modern deep learning models due to the need to store previous weights. In this paper, we instead propose the first stochastic adaptation of the nonmonotone line search method by /Zhang and Hager (2004). Thanks to this line search, no computational overhead is introduced in computing the nonmonotone term which is in fact linear combination of the previously computed mini-batch function values, To the best of our knowledge, we propose the first stochastic nonmonotone line search method to train modern convolutional neural networks and transformers (Vaswani et al. 2017].
Our paper is the first to combine a line search technique with the Stochastic Polyak Step size (SPS) [Loizou et al.] 202T]. In fact, the existing line search methods [Vaswani al. 2019 Paquette and Scheimberg 2018 Mahsereci and Hennig, [017]] do not address the problem of the selection of a suitable initial step size. In Vaswani et al. [2019), , the authors focus on reducing the amount of backtracks and propose a "resetting" technique 3 that ends up also selecting the initial step size. In this paper, we consider these two problems separately and tackle them with two different solutions: Polyak initial step size and new resetting technique (5) to reduce the amount of backtracks. Regarding the latter, a similar scheme was presented in Grapiglia and Sachs [2021], however we modify it to be combined with an independent initial step size (e.g., Polyak). This modification allows the original initial step size not to be altered by the resetting technique.
In this paper, we extend Vaswani et al. [2019] by modifying the monotone line search proposed there with nonmonotone line search. Our theoretical results extend the theorems presented in
Vaswani et al. [019] to the case of stochastic nonmonotone line search methods. Previous results
in a similar context were given by Krejie and Krklee Jerinkič [2055] 2019). Bellavia al.) [202T) that assumed 1) the difference between the nonmonotone and monotone terms to be geometrically converging to O and 2) the batch-size to be geometrically increasing. In this paper, we replace both hypotheses with a weaker assumption (i.e., interpolation) [Meng et al.) 2020) and we actually prove that the nonmonotone and monotone terms converge to the same value. In Hafshejani et al. [2023),
related convergence theorems are proved under the interpolation assumption for the use of a different
nonmonotone line search (i.e., Grippo et al. [1986] instead of Zhang and Hager (2004). ). However in Hafshejami et al. [2023]. , no explanation given how to use asymptotic result (Lemma 4) for achieving their non-asyma asymttymptotic convergence rates (Theorem I and 2). Addressing this problem represents one of the main challenges of adapting the existing nonmonotone theory [Gripppo et al..
1986 Dai 2002 Zhang and Hager 2004) to the stochastic case.
In Vaswani et al. [2019), the rates provided in the non-convex case are developed under an SGC, while we here assume the more realistic PL condition [Liu et al. 2022]. In fact in Liu et al. [2022) not only wide networks are proven to satisfy PL but also networks with skip connections (e.g.. ResNet
[He et al. 2016], DenseNet [Huang et al. 2017).. For this result, we extend Theorem 3.6 of Loizou et al. 2021 for stochastic nonmonotone line search methods by exploiting
proof technique. In
Loizou et al. 2021], various rates are developed for SGD with a Polyak step size and it is possible to prove that they hold also for PoNoS. In fact, the step size yielded by PoNoS is by construction less or equal than Polyak's. 's. However, the rates presented in this paper are more general since they are developed for nonmonotone line search methods and do not assume the use of any specific initial step size (e.g., they hold in combination with a BB step size).
3 Methods
Training machine learning models (e.g., neural networks) entails solving the finite sum problem minwer" [(w)- = 37 Ei= [(ww), where w is the parameter vector and S/ corresponds to a single instance of the MM points in the training set. We assume that f is lower-bounded by some value f", that f is L-smooth and that it either satisfies the PL condition, convexity or strong-convexity. Vanilla SGD can be described by the step Wk+1 = wi 1 Vf, (W+), where in {L...., MM is one instance randomly sampled at iteration k. Vf, (wa) is the gradient computed only w.r.t. the 4t instance and r) > 0 the step size. The mini- batch version of this method modifies is to be a randomly selected subset of instances, i.e., is C {1..... ......M, M), with Vf, (wx) being the averaged gradient on this subset and |ix|| = i the mini-batch size. Through the whole paper we assume that each stochastic function Sú, and gradient Vi, (w) evaluations are unbiased, i.e., E.,, (w) = f(w) and TE,, [Vi, (wr) = (Ww), Vw E RR Note that E. represents the conditional expectation w.r.t. Wk. i.c., Eg [-] = [[w] In other words, E. is the expectation computed w.r.t. Mk. that is the
3

---

random variable associated with the selection of the sample (or subset) at iteration & (see Bottou et al. 2018 for more details).
We interpret the pver-parameterized setting in which we operate to imply the interpolation property, ie., let w" aargmin f(r),, then w² argmin fe(w) LA S S M. This property is crucial
wER"
wER"
for the convergence results of SGD-based methods because it can be combined either with the Lipschitz smoothness of Ssg or with line search condition to achieve the bound By, || (ws, (wx))l S (f(wx) f(w")) with a > O (see Lemma 4 of the supplementary materials for the proof). This bound on the variance of the gradient results in a r.h.s. which is independent of ig and, in the convex and strongly convex cases, it can be used to replace the SGC (see Fan al. [023) for more details).
As previously stated, our algorithm does not employ constant learning rate n,. but the step size me is instead determined at each iteration & by a line search method. Given an initial step size M),,0 and E (0, 1), the Stochastic Line Search (SLS) condition (Vaswani et al. 2019] select the smallest 4 E N such that 7) -1k,00 satisfies the following condition
Six (wx 1/K Vla (wxk) S Si, (1OR) cmj || V (wx)]l
where c E (0, 1) and || is the Euclidean norm. Each internal step of the line search is called backtrack since the procedure starts with the largest value 7λ.0 and reduces (cuts) it until the condition is fulfilled. Note that (T) requires a monotone decrease of Ji,- In this paper, we follow Zhang and Hager 2004] and propose to replace fi, with nonmonotone term Ck.
fix (wx= The Vf (wx)) C2 cTall Vf (wx)
fix (wx) Ex EQuCk-1 + fix (wk) Q++1
C =maxxx { Ck:
Qk+1 = =QQu= +
where & [0, 1]. Co Qu 0 and C-1 fio (Wo). The value C₁ is linear combination of the previously computed function values Sio (100),..... Ji, (wx) and it ranges between the strongly nonmonotone term 1 - Si, (wy) (with
1) and the monotone value fi, (wx) (with & = 0). The maximum in C2 is needed to ensure the use of value that is always greater or equal than the monotone term fi, (wa). The activation of fi, (wx. instead of Cs happens only in the initial iterations and it is rare in deterministic problems, but becomes more common in the stochastic case. The computation of C₁ does not introduce overhead since the linear combination is accumulated in Cj.
Given y > 1, the initial step size employed in Vaswani et al. 2019 is the following
T/k:0 min (7k- b/M b/M
max).
In this paper, we propose to use the following modified version of SPS [Loizou et al. 2021
Tlk.0 = min (ñx,,, v) mxx with 7k. = Sig (ws) Sū
and cp E (0, 1).
cpll Vf, (wx))l?
In Loizou et al.
2021 is not directly employed, but equipped with the same resetting technique 3 to control the growth of Āi..o. i.e. 1,0 min [i.., 7 A/M m)mx..
Given 4--1 the amount of backtracks iteration k: 1, our newly introduced resetting technique stores this value for using it in the following iteration. In particular, to relieve the line search at iteration from the burden of cutting the new step size 4a-1 times, the new initial step size is pre-scaled by 8/t-1, In fact, l-11 is a good estimate for la (see Section E.3 of the supplementary materials). However, to allow the original 7/..0 to be eventually used non-scaled, reduce 4--1 by one. We thus redefine Y/k as
7 0 81x
with 4 == max(Te-1 4-11 1,0).
(5)
In Section 5
many backtracks and reduce them to zero in the majority of the iterations. At the same time, the original 77. is not modified and the resulting step size ті is always scaled version of π,,о- Moreover, the presence of the -1 in (5) keeps pushing 8'x towards zero, so that the initial step size is not cut more than necessary. Note that (5) can be combined with any initial step size and it is not limited to the case of
experiments show that thanks (5) we

---

4 Rates of Convergence
We present the first rates of convergence for nonmonotone stochastic line search methods under inter- polation (see Section B of the supplementary materials for the proofs). The three main theorems are given under drong-convexity, convexity and the PL condition. Our results do not prove convergence only for PoNoS, but more generally for methods employing
(2) and any bounded initial step size, i.e.
7J..0 E [17thin m7] with 17
Tptin 0.
(6)
Many step size rules in the literature fulfill the above requirement (Berrada al. 2020 Loizou et al.,
2021 Liang et al. [019] since when applied to non-convex DL models the step size needs to be upper
bounded to achieve convergence [Bottou et al. 2018 Berrada et al. 2020].
In Theorem 1 below, we show a linear rate of convergence the case of a strongly convex function f. with each Ji, being convex. We are able to recover the same speed of convergence of Theorem 1 in Vaswani et al. 2019]. despite the presence of the nonmonotone term C₂ instead of fig (wn)). The challenges of the new theorem originate from studying the speed of convergence of Cg to f(w")
and from combining the two interconnected sequences } and {Cx]. It turns out that g small
enough (i.e., such that b < (1 v))),, u)), then the presence of the nonmonotone term does not alter the speed of convergence of {wx} to w", not even in terms of constants.
Theorem 1. Let Cj and nı be defined in (2). with Tk,o defined in (6) We assume interpolation, fin convex, f p-strrongyy convex and fiz Li, Lipschitz smooth. Assuming
and (20-1)
we have
E [|l - w0 w11 + a(Cx - f(ww))) S d (1lwg - w²1 + (f(w)) - ff((=f(w) f(w"))),
where d max {(1 - m) m), b) (0, b b= (1+ gTT
E0, a =- mi (2 d) > 0 with
sc
n min 25(1-o) spmmnn.
Comparing the above result with the corresponding deterministic rate (Theorem 3.1 from Zhang
and Hager (2004)), we notice that the constants of the two rates are different. In particular, the proof technique employed in Theorem 3.1 from Zhang and Hager (2044] cannot be reused in Theorem I since few bounds not valid in the stochastic case (e.g., [[+++))] I || (fx))
or Ck+1 I C - V/ (wx) ). The only common aspect in these proofs the distinction between
the two different cases defining C (i.e., being C2 or Si, (wx) )). Moreover, in both theorems & needs to be small enough to allow the final constant to be less than 1.
In Theorem 2 we show ( rate of convergence in the case of a convex function f. Interestingly, in both Theorems I and (and also in the corresponding monotone versions from Vaswani et al. 2019 ) e is required to be larger than 2. The same lower bound is also required for achieving Q-super- convergence for the Newton method in the deterministic case, but it is often considered too large in practice and the default value (also in the case of first-order methods) is 0.1 or smaller (Nocedal and Wright 2006). In this paper, we numerically tried both values and found out that e 0.1 is too small since it may indeed lead to divergence (see Section E. of the supplementary materials).
Theorem 2. Let Ck and mn be defined in (2). with me.0 defined in 6 We assume interpolation, convex and fúy Lig -Lipschitz smooth. Given constant ai such that O an < (2 2 and assuming e > 2 and & < as we have
di ( (1 Ilu0 w w²1 2- + an (J(wo) [(ww(w ((w)))
E [((( - [(ww)] <
k 1ymin
where wh = Ei Wjj di := ((-a1) 0, by (1+ g E (0. 1), 17 17thn min! 28(1-o) s7min..
Limas
In Theorem 3 below we prove linear convergence rate in the case of satisfying PL condition.
We say that a function f RD + R satisfies the PL condition there exists μ O such that, (w))). The proof of this theorem extends Theorem 3.6 of 2 2n(f(w)= 2
Vwu E R"
Loizou et al. 2021 to the use of stochastic nonmonotone line search. Again here, the presence of a nonmonotone term does not modify the constants controlling the speed of convergence (a2 below can be chosen arbitrarily small) as long as & is small enough. The conditions on e and on ma are the same as those of Theorem 3.6 of Loizou et al. 2222 (see the proof).
5

---

Theorem 3. Let Cj and be defined in ② with n7 defined in 6 We assume interpolation, the
PL condition on f and that fix are L Lipschitz smooth. Given 0 < 02 = 4ue(1-c)- -mme + 21pnss
48c
and assuming 25(1-c) < f7piin pyp < Iimes (pc( 4/
260(1-0)
Lonxz
< c and 5 < agethmms
agc
we have
Limax
E [[f(WR+1) f(w") a211 (221""0(C f(w")())) S di (1 a27 (f(um) (( [(w))
where d2: 10 min {2, by) E (0, 1), V==1)- Amas Auo(l-o) a2) E (0, (0, 1), by:= (1+
EE (0. Limax age
26c(1-c)
Theorem 3 is particularly meaningful for modern neural networks because of the recent work of Liu et al. 2022]. More precisely, their Theorem 8 and Theorem 13 prove that, respectively given a wide-enough fully-connected or convolutiona/ssiipcoomeeee
neural network, the corresponding function satisfies local version of the PL condition. As consequence, nonmonotone line search methods achieve linear convergence for training of non-convex neural networks if the assumptions of both Theorem 3 above and Theorem 8 from Liu et al. [022] hold and if the initial point wo is close enough to w".
Experiments
In this section, we benchmark PoNoS against otate-of-the-art methods for training different over- parametrized models. We focus on various deep learning architectures for multi-class image classifi- cation problems, while in Section 5.3 we consider transformers for language modelling and kernel models for binary classification. In the absence of better estimate, we assume fi, (w*) = 0 for all the experiments. Indeed the final loss is many problems very close O.
Concerning datasets and architectures for the image classification task, we follow the setup by Luo
et al. [019]] later employed also in Vaswani et al. [2019]. Loizou et al. [02T]] In particular, focus on the datasets MNIST, FashionMNIST. CIFARIO, CIFARTO0 and SVHN addressed with the architectures MLP [Luo al.
2019]. EfficientNet-bl [Tan and Le 2019). ResNet-34 [He et al. 2016). DenseNet-122 121 [uuagg et al. 2017] and WideResNet [Zagoruyko and Komodakis 2016]. Because of space limitation, will not show all the experiments here, but report the first three datasets combined respectively with the first three architectures. We refer to the supplementary materials for the complete benchmark (see Figures I-XII) and the implementation details (Section C). In Section C of the supplementary materials, we also discuss the sensitivity of the results to the selection of typer-paramettrs.
In Figure M we compare SGD Robbins and Monro 1951]. Adam [Kingma and Ba 2015]. SLS Vaswani al. ] SPS [oizzou et al.] 2001 and PoNoS. We present train loss (log scale), test accuracy and average step size within the epoch (log scale). Note that the learning rate of SGD and Adam has been chosen through grid-search the one achieving the best performance each we can make the following observations:
problem. Based on Figure |
PoNoS achieves the best performances both in terms of train loss and test accuracy. In particular, it often terminates by reaching loss of 10-6 and it always achieves the highest test accuracy.
SLS does not always achieve the same best accuracy as PoNoS. In terms of training loss, SLS is particularly slow on mnist mlp and fashion effbi, while competitive on the others. On these two problems, both SLS and SPS employ a step size that is remarkably smaller than that of PoNoS. On the same problems, SPS behaves similarly as SLS because the original Polyak step size is larger than the "smoothing/resetting" value (3), i.e., Vik.0 > 11 b/M P/M and thus the step size controlled by (3). On the other hand, the proposed nonmonotone line search selects larger step size, achieving faster convergence and better generalization [Nacson et al. 2022].
SLS encounters some cancellation eπrors (c.g., around epoch 120 in cifar10 resnet34) that lead the step size to be reduced drastically, sometimes reaching values below 10-7. These events are caused by the fact that fi, (wx) and fú, (wk+1) became numerically identical. Thanks to the nonmonotone term C₁ replacing fig (w&). PoNoS avoids cancellations errors by design.
SGD, Adam and SPS never achieve the best test accuracy the best training loss. In accordance with the results in Vaswani et al. 2019]. the line-search- based algorithms outperform the others.
Because of space limitation, we defer the comparison between PoNoS and its monotone counterpart to the supplementary materials (Section E.2). There we show that PoNoS outperforms the other line search techniques, including tractable stochastic adaptation of the method by Grippo al. 1986).

---

400th
Figure 1:
Comparison between the proposed method (PoNoS) and the-state-of-the-ee Each column focus a dataset. First row: train loss. Second row: test accuracy. Third row: step size.
5.1 A New Resetting Technique
In this subsection, we compare different initial step sizes and resetting techniques. fix the line search be (2). but similar comments can be made on ① (see the Section D.2 of the supplementary materials). In Figure 2 we compare PoNoS and PoNoS resetO (without 55) with zhang reset2 (initial
step size and:
IIV 1Il? adapted to SGD from Nocedal and Wright 2006
zhang reset3: 76.0 17k-1 V/g (wa
zhang_reset4: 1,,0 = 2(S4 (wx fig_ adapted to SGD from Nocedal and Wright 2006
|V (wa-1)l
zhang_every2: same as Sesiost but new step is computed only every iterations.
In Figure we report train loss (log scale), the total amount of backtracks epoch and the average we can make the following observations:
step size within the epoch (log scale). From Figure 2
PoNoS and PoNoS resetO achieve very similar performances. In fact, the two algorithms yield step sizes that almost always overlapping. An important difference between PoNoS resetO and PoNoS can be noticed in the amount of backtracks that the two algorithms require. The plots show a sum of M elements, with this value. This means that PoNoS employs median backtrack per iteration for the first 5-25 epochs, while PoNoS_ resett needs more backtracks in this stage (around 1,00030000 per-epoch, see Section D.2 of the supplementary materials). After this initial phase, both PoNoS_reseto and PoNoS reduce the amount of backtracks until reaches (almost) constant value of O.
391 469 depending the problem and PoNoS's line hits exactly
zhang_every2 does not achieve the same good performance as PoNoS or PoNoS resett.. The common belief that step sizes can be used in many subsequent iterations does not find confirmation here. In fact, chang_every: shows that we cannot skip the application of a line search if we want to maintain the same good performances.
All the other initial step sizes achieve poor performances on both train loss and test accuracy. In many cases, the algorithms yield step sizes (also before the line search) that are too small w.r.t.
5.2 Time Comparison
In this subsection, we show runtime comparisons corresponding to Figure In the first row of Figure 3 we plot the train loss as in the first row of Figure However, the æ-axis of Figure measures cumulative epoch time of the average of different runs of the same algorithm with different seeds. In the second row of Figure 3, report the runtime per-epoch (with shaded error bars) on
7

---

40c
fratim dideeeeeoo
20ang sain
1710g /eace
Figure 2: Comparison between different initial step sizes and resetting techniques. Each column focus a dataset. First row: train loss. Second row: # backtracks. Third row: step size.
it is clear that PoNoS is not only faster than the other methods in terms of epochs but also terms of total computational time. In particular, PoNoS is faster than SGD, despite the fact the second achieves the lowest per-epoch time. Again from the second row of Figure 3 we can observe that PoNoS's per-epoch time makes transition from the phase of a median of backtrack (first 5-25 epochs) to the phase of a median of O backtracks where its time is actually overlapping with that of SLS (always a median case, PoNoS requires less than twice the time of SGD, and in the second, this time is lower than 1.5 that SGD, Given these measures, PoNoS becomes faster than SGD/Adam in terms of per-epoch time
the y-axis and epochs on the x z-axis. From Figures I and 3]
backtracks). the first
grid-search (or any other best-pen pest-perfornin learning rate.
optimization) is employed to select the
To conclude, let us recall that any algorithm based on a stochastic line search always requires one additional forward pass if compared with SGD. fact, both fú, (wx) and fi, (W++1) are computed at each & and each backtrack requires one additional forward pass. On the other hand, if we consider that one backward pass costs roughly two forward passes and that SGD needs one forward and one backward pass, any additional forward pass costs roughly one-third of SGD. These rough calculations have been verified in Section E.6 of the supplementary materials, where we profiled the single iteration of PoNoS. Following these calculations and referring to the two phases of Figure 3 one iteration of PoNoS only costs 3 that of SGD in the first phase and 4 in the second. 3
5.3 Experiments for Convex Losses and for Transformers
As a last benchmark, we take into account a set of convex problems from Vaswani et al. (001 Loizou et al. 202T and the transformers (Vaswani et al. 2017 trained from scratch in Kunstner et al. 2023). In Figure we show one convex problem (first column) and two transformers (last two column). We leave the fine-tuning of transformers future works. Our experiments take into account binary classification problems addressed with RBF kernel model without regularization. We show the results achieved on the dataset mushrooms, while leaving those on ijenn, revl and w8a to Section D.4 of the supplementary materials. Given the high amount of iterations, the smoothed version of the train loss will be reported. The test accuracy is also only reported Section D.4 since (almost) all the methods achieve the best test accuracy in all the problems within the first few iterations. From the left subplot of Figure 4 (see supplementary materials). In Figure PoNoS achieves very low train loss (10-1) within the first 200 iterations. Only SI.S able to catch up, but this takes 6 times the iterations of PoNoS. this problem, SLS is the only method reaching the value (10-6) The methods SLS and SPS behave
we can observe that PoNoS obtains very good performances also in this setting
8

---

Ci nuttima
"uthin uffcetteett
400
Figure 3: Time comparison (s) between the proposed method (PoNoS) and the-stateoof-thh-arr, Each column focus on dataset. First row: train loss vs runtime. Second row: epoch runtime.
very similarly on all the datasets (see the supplementary materials) since in both cases controls the step size. As clearly shown by the comparison with PoNoS, this choice is suboptimal and the Polyak step size is faster. Because of (3), both SLS and SPS encounter slow convergence issues in many of problems of this setting. As in Figure 1 SGD and Adam always slower than PoNoS.
We consider training transformers on language modeling datasets. In particular, we train Transformer Encoder [Vaswani et al., 2017] on PTB [Marcus et al. [1993] and a Transformer-Xi [Dai et al. 2019) on Wikitext2 [Merity et al. 2017]. most popular method for training transformers is Adam and not SGD Pan and Li 2022 Kunstner ct al., 2023]. For this reason, we use a preconditioned version of PoNoS, SLS, and SPS (respectively PoNoS prec, SLS prec, and SPS prec, Section D.5 of the supplementary materials for details). In fact, Adam can be considered a preconditioned version of SGD with momentum (Vaswani et al.) 2020]. As in Kunstner et al. 2023), we focus on the training procedure and defer the generalization properties to the supplementary materials. From Figure we can observe that the best algorithms in this setting are preconditioned baased and not SGD-based, in accordance with the literature. Moreover, PoNoS prec achieves similar performances as Adam's. 's. In particular from the central subplot of Figure 4 observe that PoNoS PoNoS_prec is the only algorithm as fast as Adam, while all the others have difficulties achieving loss below 1. Taking the right subplot of Figure +
contrast to the case of convolutional neural networks, the
into account, we can notice that PoNoS perecssppeeeeee slower than Adam on this problem. On the other hand, there not one order of difference between the two final losses (i.c., ~ 1.5 points). Morcover, we should keep in mind that Adam's ''s learning rate has been fine-tuned separately for each problem, while PoNoS _pecc has been used off-the-shelf,
prec
Figure 4: Train loss comparison between the new method (PoNoS) and the sfate-of-the-art on convex kernel models (first column) and transformers (last two columns).
6 Conclusion
In this work, we showed that modern DL models can be efficiently trained by nonmonotone line search methods. More precisely, nonmonotone techniques have been shown to outperform the monotone line searches existing in the literature. A stochastic Polyak step size with resetting has been employed as the initial step size for the nonmonotone line search, showing that the combined method is faster than the version without line search. Morcover, presented the first runtime comparison

---

between line-search- search-baeed methods and SGD/Adam. The results show that the new line search is new resetting technique developed to
overall computationally faster than the state-of-the reduce the amount of backtracks to almost zero on average, while still maintaining large initial step size. To conclude, the similar behavior of S1_S_prec and Adam on the rightmost subplot Figure suggests that other initial step sizes might also be suited for training transformers. We leave such exploration (e.g., a stochastic BB like in Tan et al. [2016]. Liang et al. (2019) to future works.
We proved three convergence rate results for stochastic nonmonotone line search methods under convexity, the PL condition. Our theory matches
interpolation and under either ltrong-convente its monotone counterpart despite the use of a nonmonotone term. In the future, we plan to explore the conditions of the theorems in Liu et al. [022] and to study a bridge between their local PL results and our global PL assumption. To conclude it is worth mentioning that nonmonotone line search methods might be connected to the edge of stability phenomenon described in Cohen et al. (202T), because of the very similar behavior they induce in the decrease of (deterministic) objective functions. However, a rigorous study remains for future investigations.
Acknowledgments
The work was conducted within the KI-Starter project "Robustness and Generalization in Train- ing Deep Neural Networks" funded by the Ministry of Culture and Science Nordrhein-Westie Germany and partially supported by the Canada CIFAR AI Chair Program.
References
Larry Armijo. Minimization of funetions having lipschitz continuous first partial derivatives. Pacific Journal of Mathematics, 16(1):1-3, 1966. Cited on
Hilal Asi and John C Duchi. The importance of better models in stochastic optimization. Proceedings of the National Academy of Sciences, 16644)) 2019. Cited on
Jonathan Barzilai and Jonathan M Borwein. Two-point step size gradient methods. IMA Journal of Numerical Analysis, 8(1):14 1988. Cited 2
Atilim Gunes Baydin, Robert Cornish, David Martinez Rubio, Mark Schmidt, and Frank Wood. Online learning rate adaptation with hypergradient descent. In International Conference on Learning Representations, 2017. Cited on [
Stefania Bellavia, Natasa Krejic, Benedetta Morini, and Simone Rebegoldi. A stochastic first- order trust-region method with inexact restoration for finite-sum minimization. arXiv preprint arXiv:2107.03322 2021. Cited on 2
Leonard Berrada, Andrew Zisserman, and M Pawan Kumar. Training neural networks for and by interpolation. In International Conference Machine Learning, pages 799-809. PMLR, 2020.
Cited on 5
E. G. Birgin, J. M. Martínez, and M. Raydan. Nonmonotone spectral projected gradient methods on convex sets. SIAM Journal on Optimization, 10(4):1196-2211, 2000. Cited 2
R. Bollapragada, D. Mudigere, J. Nocedal, H.-.M. Shi, and P.T.P. Tang. A progressive batching I.- BFGS method for machine learning. In International Conference on Machine Learning, volume pages 1013, 2018. Cited on
Léon Bottou, Frank Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223-31,, 2018. Cited on 5
Jeremy Cohen, Simran Kaur, Yuanzhi Li, Zico Kolter, and Ameet Talwalkar. Gradient descent on neural networks typically occurs at the edge of stability, In International Conference on Learning Representations, 2021. Cited on 10
Yu-Hong Dai. On the nonmonotone line search. Journal of Optimization Theory and Applications, 112(2):315333) 33303, 2002, Cited on
10

---

Zihang Dai, Zhilin Yang, Yiming Yang. Jaime G Carbonell, Quoe Le, and Ruslan Salakhutdinov. Transformer-xl: Attentive language models beyond fixed-length context. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 2978 27788-988,02 2019. Cited on 9
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(7). 2011. Cited on [
Chen Fan, Christos Thrampoulidis, and Mark Schmidt. Fast convergence random reshuffling under weeepaaraetterizatonn and the polyak- \| ojasiewicz condition. arXiv preprint arXiv:2304.004533
2023. Cited on
MC Ferris and S Lucidi. Nonmonotone stabilization methods for nonlinear equations. Journal of Optimization Theory and Applications, 81(1):53-71, 1994. Cited on !
Robert M Gower, Aaron Defazio, and Michael Rabbat. Stochastic Polyak stepsize with a moving target. arXiv preprint arXiv:2106. 1851, 2021, Cited on
Robert M Gower, Mathieu Blondel, Nidham Gazagnadou, and Fabian Pedregosa. Cutting some slack for SGD with adaptive polyak stepsizes. arXiv preprint arXiv:2202. 12328, 2022. Cited on A
Geovani Grapiglia and Ekkehard W Sachs, A generalized worst-case complexity analysis for non-monotone line searches. Numerical Algorithms, 87:779-796, 2021. Cited on
Luigi Grippo, Francesco Lampariello, and Stefano Lucidi, A nonmonotone line search technique for Newton's 's method. SIAM Journal on Numerical Analysis, 23(4):707-716, 1986. Cited on
Sajad Fathi Hafshejani, Daya Gaur, Shahadat Hossain, and Robert Benkoczi. Fast armijo line search for stochastic gradient descent. Research Square preprint https::/tb..rr/10.21203/3/. 2285238/v1, 2023. Cited on
Kaiming Hc. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016. Cited on 3
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4700-4708, 2017. Cited on 3 6
Nitish Shirish Keskar and George Saon. A nonmonotone learning rate strategy for sgd training of deep neural networks. In 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 4974 4978. IEEE, 2015. Cited on [
D.P. Kingma and J.I. Ba. Adam: A method for stochastic optimization. In International Conference Learning Representations, 2015. Cited on 6
Nataša Krejić and Nataša Krklec Jerinkić. Nonmonotone line search methods with variable sample size. Numerical Algorithmss, 68(4):711-73) 2015. Cited on
Nataša Krejić and Nataša Krklec Jerinkić. Spectral projected gradient method for stochastic opti- mization. Journal of Global Optimization, 73(1):59-81, 2019. Cited on
Frederik Kunstner, Jacques Chen, Jonathan Wilder Lavington, and Mark Schmidt. Noise is not the main factor behind the gap between sgd and adam on transformers, but sign descent might be. In The Eleventh International Conference on Learning Representations, 2023. Cited on g
Nicolas Le Roux, Mark Schmidt, and Francis Bach. stochastic gradient method with an exponential convergence rate for finite training sets. Advances in neural information processing systems, 25, 2012. Cited 2
Donghui Li and Masao Fukushima. A globally and superlinearly convergent Causs-Newtoon BFGS method for symmetric nonlinear equations. SIAM Journal on Numerical Analysis, 37(1): 152-172, 1999. Cited on 2

---

Shuang Li, William J Swartworth, Martin Takáč, Deanna Needell, and Robert M Gower. SP2: A second order stochastic Polyak method. arXiv preprint arXiv:2207.08171, 2022. Cited on 2
Jinxiu Liang, Yong Xu, Chenglong Bao, Yuhui Quan, and Hui Ji. learning rate for deep learning. Puttern Recognition Letters, 128:197-203 2019, Cited on 5
adaptive
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in weerparamettrizee non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 59: 85-116, 2022. Cited on
10
Nicolas Loizou, Sharan Vaswani, Issam Hadj Laradji, and Simon Lacoste-Julien. Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence. In International Conference on Artificial Intelligence and Statistics, pages 1306-1314. PMLR, 2021. Cited on 2 33
L. Luo, Y. Xiong, Y. Liu, and X. Sun. Adaptive gradient methods with dynamic bound of learning rate. In International Conference on Learning Representations, 2019. Cited on
Maren Mahsereci and Philipp Hennig. Probabilistic line searches for stochastic optimization. The Journal of Machine Learning Research, 18(1):4262-4322, 2017. Cited on
Mitchell Marcus, Beatrice Santorini, and Mary Ann Mareinkiewicz. Building large annotated corpus of english: The Penn Treebank. Computational Linguistics 19.2, pages 313-330, 1993. Cited on 9
Si Yi Meng, Sharan Vaswani, Issam Hadj Laradji, Mark Schmidt, and Simon Lacoste-Julien. Fast and furious convergence: Stochastic second order methods under interpolation. In International Conference Artificial Intelligence and Statistics, pages 1375-1386. PMLR, 2020. Cited on
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. In International Conference Learning Representations, 2017. Cited on
Maximus Mutschler and Andreas Zell. Parabolic approximation line search for DNNs. Advances in Neural Information Processing Systems, 33:5405-5416, 2020. Cited on
Mor Shpigel Nacson, Kavya Ravichandran, Nathan Srebro, and Daniel Soudry. Implicit bias of the step size in linear diagonal neural networks. In International Conference on Machine Learning, pages
PMLR, 2022. Cited on 6
Jorge Nocedal and Stephen Wright. Numerical optimization. Springer Science & Business Media, 2006. Cited on 7
Yan Pan and Yuanzhi Li. Toward understanding why Adam converges faster than SGD for transform- ers. In Optimization for Machine Learning (NeurIPS Workshop), 2022. Cited on
Courtney Paquette and Katya Scheinberg. A stochastic line search method with convergence rate analysis. arXiv preprint arXiv:1807.0799) 2018. Cited on
Vassilis P Plagianakos, George Magoulas, and Michael N Vrahatis. Deterministic nonmonotone strategies for effective training of multilayer perceptrons. IEEE Transactions on Neural Networks, 138 2002. Cited on 2
Boris Teodorovich Polyak. Minimization of unsmooth functionals. USSR Computational Mathematics and Mathematical Physics, 144:14-29, 1969. Cited on 2
M. Raydan. The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem. SIAM Journal on Optimization, 7(1):26-33, 1997. Cited o
Herbert Robbins and Sutton Monro. stochastic approximation method. The Annals of Mahematical Statistics, pages 400-407, 1951. Cited on
Mark Schmidt and Nicolas Le Roux, Fast convergence of stochastic gradient descent under a strong growth condition. arXiv preprint arXiv:1 6370 2013. Cited on 2
12

---

Conghui Tan, Shiqian Ma, Yu-Hong Dai. and Yuqiu Qian. Barzilai-Borwein step size for stochastic gradient descent. In Advances in Neural Information Processing Systems, pages 685-693, 2016. Cited on 10
Mingxing Tan and Quoe Le. Efficientnet: Rethinking model scaling for convolutional neural networks. In International conference on machine learning, pages 6105-61 6155-1144 PMLR, 2019. Cited on
Tuyen Trung Truong and Hang-Tuan Nguyen. Backtracking gradient descent method and some applications in large scale optimisation. Part 2: Algorithms and experiments. Applied Mathematies & Optimization, 84(3):2557-2586 2021. Cited on [
Tuyen Trung Truong and Tuan Hang Nguyen. Backtracking gradient descent method for general C functions, with applications deep learning. arXiv preprint vrXiv:1808.051000 2018. Cited
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017. Cited on
Sharan Vaswani, Aaron Mishkin, Issam Laradji, Mark Schmidt, Gauthier Gidel, and Simon Lacoste- Julien. Painless stochastic gradient: Interpolation, line-search, and convergence rates. In Advances in Neural Information Processing Systems, pages 3732-3745, 2019. Cited on | 2 3 6 g
Sharan Vaswani, Issam Laradji, Frederik Kunstner, Si Yi Meng, Mark Schmidt, and Simon Lacoste- Julien. Adaptive gradient methods converge faster with over-paramettriiztion (but you should do line-search). arXiv preprint arXiv:2006.06833 2020. Cited on
Yifei Wang. Zeyu Jia, and Zaiwen Wen. The search direction correction makes first-order methods faster. arXiv preprint FrXiv:9905.0650/ 2019. Cited on P
Yifei Wang, Zeyu Jia, and Zaiwen Wen. Search direction correction with normalized gradient makes first-order methods faster. SIAM Journal on Scientific Computing, 43(5) 2021. Cited on
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In British Machine Vision Conference 2016. British Machine Vision Association, 2016. Cited 6
Hongchao Zhang and William W Hager. A nonmonotone line search technique and its application unconstrained optimization. SIAM Journal on Optimization, 14(4):1043-1056, 2004. Cited on
5
Jian L Zhou and AL Tits. Nonmonotone line search for minimax problems. Journal of Optimization Theory and Applications, 76(3):455-476, 1993. Cited on 2
Weijun Zhou A short note the global convergence of the unmodified PRP method. Optimization Letters, 766): 1372, 2013. Cited on
13


Reviews:
[{"review_id": "2OBbcKmITE", "reviewer": "Reviewer_TC8b", "summary": "The paper presents a proposed Polyak nonmonotone stochastic (PoNoS) method which combines a nonmonotone line search with a Polyak initial step size. It builds on the work of Vaswani et al. [2019] by modifying the monotone line search to incorporate a nonmonotone approach. ", "questions": "1.\tLines 12-23 are about a reduction of the number of backtracks to zero. Can you specify which parts of the experiments to support the argument.\n2.\tDid you have comparison with he based model of Vaswani et al. [2019]?\n3.\tCan you explain further or provide intuition about the observation in lines 317-319?\n4.\tIn figure 4, data for SLS-prec, SPS-pre and PoNoS-pres seems to be missing. Do you have any reason for not to put the data?", "limitations": "The authors do address some of the limitations of their work.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Originality:\nThe introduction of nonmonotone line search applied to Deep Learning is noteworthy.\nClarity:\nThe paper is generally well-written. However, the authors should emphasize their specific methodological innovation and contribution to the conclusion section to highlight the significance.\n\nQuality: The overall quality is good. The paper demonstrates the outperformance of the proposed methods over other methods in regard to runtime.\n\nSignificance:\nThe experiments show the advantages of the methods in terms of convergence speed and runtime when applied to Deep Learning. ", "weaknesses": "The authors admitted the adverse impact on convergence speed of the proposed method. This matter should be further investigated to have a more comprehensive intuition of the robustness of the method.\n\nAdditionally, the authors should conduct a further comparison with the state-of-the-art line search approaches and the based model of Vaswani et al. [2019]\n?a Figurethis", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the comments and the time spent reading the paper.\n\nStrengths:\n  We will follow the reviewer's suggestion and highlight our contributions in Section 6.\n\nWeaknesses:\n\n  · We are not sure we understood the comment of the reviewer regarding the adverse effect on the convergence speed. We assume the reference is to our sentence \"Our theory matches its monotone counterpart despite the use of a nonmonotone term\" (line 367). What we meant there is that despite the convergence proof being more complicated, our method still achieves the same rate as its monotone counterpart. The additional complexity comes from the fact that nonmonotone methods only ensure the decrease of the (mini-batch) function value every $W$ iterations, instead of every iteration. In practice, this is a great advantage since it provides the line search with more freedom of choice. Despite the more complex analysis, nonmonotone rates have always been shown to be consistent with those of their monotone counterparts [Grippo et al. 1986, Raydan 1997, Dai 2002, Zhang and Hager 2004] and the same can be said for PoNoS. For a discussion on provable advantages of one method over another, see the general repose to all reviewers.\n\n  · The comparison with Vaswani et al. [2019] was reported in Figures 1, 3 and 4 of the main paper and in the corresponding Figures I, III and IV of the supplementary materials. The method is there denoted SLS. Additional experiments on other stochastic line search methods are reported in Figure VIII of the supplementary.\n\nQuestions:\n\n  1. This argument is supported in Figure 2 and in the corresponding Figure II of the supplementary. Moreover, a zoom-in on the amount of backtracks is reported in Figure IX and Section E.3 of the supplementary.\n\n  2. See the reply above regarding the comparison with Vaswani et al. [2019].\n\n  3. We would like to thank the reviewer for this question, there is a mistake in the sentence, instead of \"In fact, we can notice that the additional per-epoch runtime of PoNoS in the first 5-25 epochs is less than one half that of the later stage of the training.\" it should have been \"In fact, ... is less than the double that of the later...\". Also, what we meant is that the time of the last forward step (e.g., which in the case of \"cifar10 | resnet34\" is 4s/#batches-per-epoch) is less than the second forward step (6s/#batches-per-epoch). This observation supports the thesis that the first forward step is more expensive than the others, because of the loading of the data in the GPU memory. We will clarify this sentence and add a more rigorous timing comparison.\n\n  4. We understand the reviewer's confusion here, in Figure 4 we reported a convex experiment (first column) and two experiments on transformers (last two columns). SLS_prec, SPS_prec and PoNoS_prec were not tested on convex problems. We will clarify this point.\n\nReferences not in the main paper:\n\n  [Dai, 2002] Dai, Yu-Hong. \"On the nonmonotone line search.\" Journal of Optimization Theory and Applications 112 (2002): 315-330."}, {"review_id": "FwZCK7dYI2", "reviewer": "Reviewer_WR5e", "summary": "This paper proposes a new line search method for determining the step size in SGD within the interpolation regime. In contrast to the previous approach called SLS, which relies on the monotonically decreasing Amijo condition, the proposed method adopts the non-monotone Zhang & Hager line search. The authors establish the convergence guarantees for the proposed Stochastic Zhang & Hager line search when an upper bound is placed on the initial step size, considering strongly convex, convex, and PL problems. Additionally, they introduce several enhancements to improve empirical performance: (1) utilizing the Stochastic Polyak Step (SPS) to set the initial step size of the line search and (2) introducing a new resetting technique to reduce the number of backtracking steps.\n\n\n\n\n\n\n", "questions": "- While reading the main text, I was initially skeptical about Theorem 1 and 2 due to their requirement of Lipschitz continuity for function $f$. It has been shown that the bounded gradient assumption contradicts the strong convexity [1]. Upon reviewing the proof in the appendix, it seems that the Lipschitz continuity of $f$ may not be necessary for Theorem 1 and 2. Additionally, in Theorem 3, it is unclear why the smoothness of $f$ needs to be separately assumed given that $f_i$ is $L_i$-smooth. It would be helpful if the authors could provide clarification.\n- Furthermore, the notation \"LC\" used in Theorem 2 and 3 lacks a definition in the main text. The corresponding definition can be found in Appendix B. \n- In theory, how can you ensure that backtracking (Lines 10 - 12) halts in finite steps?\n\n[1] Nguyen, Lam, et al. \"SGD and Hogwild! convergence without the bounded gradients assumption.\" International Conference on Machine Learning. ICML, 2018.", "limitations": "N/A", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Numerical experiments are extensive and the performance of PoNoS looks quite promising. It is great to see a provably convergent optimization algorithm (with other heuristics) working well in large-scale experiments while incurring only a minor computation overhead.\n- The proof techniques look new and interesting. ", "weaknesses": "- There are certain expressions within theorems that may lead to confusion. I have elaborated on these concerns in the \"Questions\" section of my review.\n- The Polyak step and the resetting technique are only heuristics. It would be valuable to provide further analysis regarding how these heuristics influence the convergence properties of the algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the accurate comments and the time spent reading the paper. \n\nWeaknesses:\n\n  Additional studies on the Polyak step alone show its connections to the \"better model\" of Asi and Duchi [2019] in Gower et al. [2021] and to the \"passive aggressive\" optimization framework [Gower et al. 2022]. However, we agree with the reviewer, it would be valuable to study what theoretical influence has the Polyak step when employed as an initial step for line search methods. Regarding the new resetting technique, we obtained some preliminary results linking $l_k$ and $l_{k-1}$, but they were not conclusive and they were left out of the paper. We will consider both these directions in future works. \n  \nQuestions:\n\n  · We would like to thank the reviewer for the very constructive feedback, we didn't realize that the assumption on the Lipschitz continuity of $f$ may not be necessary. We will study this extension in future works. Moreover, it is true that the smoothness of $f$ is not needed, once we assume that of the $f_i$. The reason for this redundancy was just that of defining $L$ ($L$ would be upper-bounded by the average of the $L_i$).\n\n  · We notice this issue and replaced the notation \"LC\" directly with \"Lipschitz smoothness\".\n  \n  · The fact that backtracking halts in finite steps is a consequence of Lemma 1 from the supplementary. This lemma shows that the step size yielded by the backtracking algorithm has a lower bound. This, together with the fact that the initial step size has an upper bound, shows that the amount of backtracks is limited. "}, {"review_id": "9nMzzXCfJm", "reviewer": "Reviewer_hZgC", "summary": "This submission proposed a new linear search method to ensure convergence without the monotone decrease condition of the (mini-)batch objective function. The method is quite suitable for the modem DNN training, which prefers the larger training learning rate.", "questions": "- The experimental results are not entirely convincing. With the development of neural network training technology in recent years, the Adam optimizer can achieve better training losses than SGD in most cases. It is strange that SGD beat Adam constantly, especially on the transformer model for the NLP task.", "limitations": "See weakness.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "- The explanation of motivation is very clear.\n- The related work has been extensively discussed.", "weaknesses": "- Discussing the difference between the proposed and the previous methods is inadequate, especially since the existing methods inspire some steps.\n- The theoretical benefits of the proposed method are not shown/discussed in the convergence rate results. The proposed method seems to share a similar rate with the previous results. However, since PoNoS prefers a larger learning rate, its rate at least can demonstrate the advantage of a constant level.\n- There is no numerical comparison in the main part, and just having the curve figures cannot fully display the results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the comments and the time spent reading the paper.\n\nWeaknesses:\n\n  · We don't understand the reviewer's comment, in what sense is our discussion on the difference between the proposed and the previous methods inadequate? \n\n  · While it is true that nonmonotone methods take larger steps, they do not ensure that the function value will decrease at each iteration (but only every $W$ iterations). Even if practically this is a real advantage (i.e., it grants line searches more freedom of choice), this property it is not captured by the theory. In fact, none of the existing nonmonotone rates is faster than their monotone counterpart [Grippo et al. 1986, Raydan 1997, Dai 2002, Zhang and Hager 2004] not even in terms of constants. But nevertheless non-monotonicity has shown to improve practical performance in a variety of settings. For a discussion on the provable advantages of one method over another, see the general repose to all reviewers. \n\n  · We don't understand the reviewer's comment, what does the reviewer mean with numerical comparisons?\n\nQuestions:\n\n  · Our results agree with the reviewer's comment: Adam is always faster than SGD for training transformers (see the last two columns of Figure 4 of the main paper and Figure V of the supplementary) and comparable with SGD for training convolutional neural networks (e.g., Figure I of the supplementary). This observation is consistent with other works [Kunstner et al., 2023]\n  \nReferences not in the main paper:\n\n  [Dai, 2002] Dai, Yu-Hong. \"On the nonmonotone line search.\" Journal of Optimization Theory and Applications 112 (2002): 315-330."}, {"review_id": "AB7pa5gSfe", "reviewer": "Reviewer_CWjK", "summary": "This paper presents a non-monotone line search method for optimizing over-parameterized models. The method is equipped with some theoretical support for strongly convex, convex and the PL condition. Furthermore, experimentally, the method is shown to have favorable performance when optimizing various deep learning models of practical interest.\n\n==> post rebuttal: increased score from 4 to 5.", "questions": "- In the theorem, particularly for the PL case, the degree of (non-) monotonicity that can be tolerated seems to be rather small (the permitted \\zeta appears to be super small)? Can the authors clarify this?\n\n- The theorem for the strongly convex case doesn't appear to be particularly applicable in the over-parameterized case unless a regularized objective is being solved for, which doesn't reflect on how the behavior manifests on the loss function we truly care for.\n\n- Can the authors clarify why the proposed stepsizes tend to increase as a function of iterations? Is this related to using normalization layers (e.g. batch norm/layer norm) within the architectures? How do these stepsizes look like for convex case in the experiments conducted in the paper?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Obtaining convergence results with non-monotone line search strategies appears to be a novel contribution - though, I don't know if some variant of this result has appeared in existing literature dealing with non-monotone line search.", "weaknesses": "- The proposed approach seems incremental compared to existing approaches.\n- The theory doesn't adequately capture why the proposed method outperforms existing approaches. The bounds suggest identical convergence rates as ones that use monotone line search methods. This suggests all these bounds are fairly worst case (loose upper bounds) that do not help quantify why these methods work well in practice in the first place.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the comments and the time spent reading the paper.\n\nWeaknesses:\n\n  · We understand the reviewer's position on this matter, however we would like to stress a few factors that make our contribution non-incremental. PoNoS is the first stochastic nonmonotone line search method able to train neural networks efficiently while simultaneously achieving state-of-the-art generalization performance. To the best of our knowledge, the following contributions were not existing in the literature before:\\\n    &nbsp;&nbsp;1.1 the stochastic Zhang and Hager [2004] line search (2);\\\n    &nbsp;&nbsp;1.2 the memory-based resetting technique (5);\\\n    &nbsp;&nbsp;1.3 the combination of a Polyak initial step size and a Zhang and Hager [2004] line search (not even in the deterministic setting);\\\n    &nbsp;&nbsp;1.4 Theorems 1-3 and the proof technique employed to show them.\\\n    Of the above elements, 1.2 and 1.4 are non-incremental contributions of our work. In fact, (5) is very different from (3) and the idea of summing the monotone and nonmonotone sequences is original and it is a non-trivial contribution of our study.\n    Regarding 1.1 and 1.3, we agree with the reviewer on the fact that they seem more easily reachable from the existing methods. On the other hand, the process of designing them included creative and non-conventional elements that in the end were replaced by adaptations of more consolidated techniques. We believe that this is actually a stregth of our method and not a weakness. In fact, simple changes with big practical impact are often very appreciated contributions in the long term.\n\n  · Even though we do not improve on the worst-case theoretical rate, we match the worst-case theoretical rate while significantly improving practical performance. Please also see the reply to all reviewers.\n\n\nQuestions:\n\n  · The reviewer is right, the $\\xi$ permitted by Theorem 3 is very small. This bound is a consequence of the fact the nonmonotone term needs to be \"squeezed\" between the monotone sequence and the linear bound. In fact, also in the deterministic case, monotone and nonmonotone sequences need to be geometrically converging to the same value. We conjecture that this bound does not need to be this tight, but we leave this exploration to future works.\n\n  · We are not sure we understood the reviewer's comment correctly, which are the loss functions we truly care for? In deep learning, it is true that neural networks do not employ any regularization, on the other hand, one might be interested in applying our method to more classical machine learning models (e.g., linear Support Vector Machines (SVM)) on a dataset with many more features than instances. In this case, the over-parametrization property would be satisfied and also the strong convexity (SVM models are regularized models).\n\n  · The step size increases because the squared norm of the gradient decreases as we get closer to a stationary point (see fourth column of Figure I of the supplementary). This is the consequence of the Polyak step size, whose denominator is the squared norm of the gradient. The same happens in the case of the convex experiments (see the third column of Figure IV of the supplementary)."}, {"review_id": "bEEJy0Hkmr", "reviewer": "Reviewer_qQnN", "summary": "This paper proposes a non-monotonic line search method for choosing step sizes in stochastic optimization. Convergence rates are proved for strongly convex, convex, and PL functions, and the rates match those of previous work. Experimental results show that (1) for MLPs and CNNs, the proposed algorithm outperforms SGD, Adam, and previous line search methods, and (2) for kernel models and transformers, the proposed algorithm outperforms SGD and previous line search methods, and is competitive with Adam.", "questions": "1. Why is interpolation important to achieve the theoretical results? The introduction discusses interpolation in detail, but Section 4 only mentions interpolation as a condition for the theorems, and does not discuss why interpolation is necessary. Do previous line search methods also require interpolation to recover the same convergence rates?\n2. How were the hyperparameters chosen? In particular, were all algorithms fairly tuned?\n2. Why does PoNoS outperform other line search methods empirically when the theoretical guarantees of PoNoS do not improve over baselines?\n3. How much do the two individual components of PoNoS (non-monotonicity and choice of initial step size) affect the performance? In particular, how would PoNoS perform if we used non-monotonicity with a classical initial step size?\n\nAs a miscellaneous suggestion, please use lower resolution images for Figures 1-3, or if you're using a vector format please remove some data points. The provided PDF is unusually large and viewing the figures in Chrome's PDF viewer is quite slow.", "limitations": "The authors include some discussion of limitations and future work in the conclusion, though it would be nice to see some more discussion of the weaknesses of the proposed method instead of just directions for future work. Discussion of potential negative societal impact is, in my opinion, not necessary for this paper.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "1. The question is significant. Given the observations of the \"edge of stability\" and non-monotonic decreases in loss when training deep networks, it seems natural that incorporating non-monotonicity into line search methods may yield significant performance improvements.\n2. The presentation is clear and easy to follow.\n3. The theoretical results (Theorems 1, 2, 3) can recover convergence rates from previous work.\n4. The experimental evaluation is very broad, covering many datasets and neural network architectures.", "weaknesses": "1. The proposed algorithm appears to be a direct combination of existing techniques (non-monotonic line search with Polyak initial step size). While this isn't necessarily a problem in itself, as a result the technical novelty of the paper is not very high.\n2. The theoretical results recover the previous convergence rate, but they do not exhibit any improvement over baselines. Recovering the previous convergence rates is natural and the proofs don't appear to contain any new techniques. Therefore, the theoretical contribution is not significant.\n3. The main text contains no information about the tuning procedure for baselines or for the proposed algorithm, and the appendix contains very little information about hyperparameters. It's uncertain whether the experimental comparison is fair, and since the theoretical results do not exhibit improvement over baselines, the experimental performance is the only substantial contribution. Some previous baselines require additional hyperparameters (e.g. SPS with $\\gamma$), but there is no assurance that this parameter was properly tuned. It is also difficult to see whether PoNoS was tuned more extensively than baselines, which would of course not be a fair comparison.\n4. Evaluation for RBF kernel models and transformers does not compare by wall-clock time, and does not include results for test loss. Since PoNoS is competitive with Adam when measured by epochs, it is natural to assume that PoNoS lags behind Adam in terms of wall-clock time, which begs the question whether existing line search methods are useful for training Transformers. Line 344 says that only the training procedure is considered (following previous work), but this is not completely satisfying to me. If we compared test performance for MLPs, and CNNs, why not also for RBFs and Transformers?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the comments and the time spent reading the paper. As a general answer, it appears that many of his/her statements are influenced by the reviewer's belief regarding our theory not containing any novelty. In the reply to Weakness 2. below, we clarify that our proof does contain a new technique, which is a central contribution of our work and that seems already to have a candidate for being reused. \n\nWeaknesses:\n\n 1. Below, we provide an example of a valuable technical novelty of our work. Please also see the reply to Reviewer CWjK. \n\n 2. We understand the concern of the reviewer, however the derived theorems are not a straightforward consequence of Theorems 1-2 of Vaswani et al. [2019]. In particular, the proof structure is similar to theirs, on the other hand, the idea of summing the monotone and nonmonotone sequences is original and it is a non-trivial contribution of our study. This proof technique allows us to show for the first time in the stochastic setting that\\\n (*) the difference between the nonmonotone and the monotone terms is geometrically converging to 0.\\\n A few evidences of the non-triviality of our achievement are:\n  - all the existing convergence rates for stochastic nonmonotone methods assume (*), instead of proving it (since [Krejić and Krklec 2015]);\n  - in the preprint by Hafshejani et al. [2023], the converge proof seems incomplete because the authors did not show (*) but only an asymptotic version of it;\n  - one of the main contributions of Grippo et al. [1986] is the inductive proof showing (*) for the deterministic setting.\n\n 3. PoNoS's hyperparameters were not fine-tuned, they were either set to very standard values or fixed by theory (see reply to Reviewer 9zy1 for a detailed discussion). The reviewer refers to $\\gamma$ of SPS. If the reference is to the maximum step size of Loizou et al., [2021], the robustness analysis for SPS, SLS and PoNoS can be found in Section E.4 of the supplementary. If the reference is to $\\gamma$ in (3) (which is only affecting SLS and SPS), our experiments were not conclusive towards changing it, so we decided to keep the default value chosen by Loizou et al., [2021]. Notice that we performed a per-problem fine-tuning of hyperparameters only for the learning rates of SGD and Adam.  \n \n 4. Concerning transformers, as the reviewer pointed out, PoNoS is competitive with Adam in terms of epochs, but slower than it in terms of wall-clock time. On the other hand, Adam's learning rate has been fine-tuned, while PoNoS has been used off-the-shelf. In fact, as soon as a hyperparameter selection is performed to select its learning rate, Adam is overall slower also in terms of cumulative-training time. It is true, however, that the improvement of PoNoS over Adam for training transformers is not as noticeable as that over SGD for CNN. In Section D.5 of the supplementary, we discuss the limitation of the Polyak step in this set of experiments. As in the case of SGD, it seems that transformers need to be treated differently also for (Po)NoS, especially in terms of its initial step size.\n    Regarding the wall-clock time of training RBF kernel models, these values are in the order of fractions of seconds, so we decided to not report them. The accuracy of RBF kernel models on the binary classification tasks can be found in Figure IV of the supplementary.\n\nQuestions:\n\n 1. We would like to thank the reviewer for the question, we will clarify this point. The interpolation assumption is the property that allows stochastic methods to achieve linear rates [Ma et al. 2018] without needing to grow the batch size. Together with L-smoothness, this assumption allows the weak growth condition to be replaced by an alternative bound on the variance of the mini-batch gradients. A large chunk of the methods designed after Ma et al. [2018] assume interpolation because it is a realistic property of neural networks and because it allows us to avoid designing a hand-crafted sequence of step sizes. This includes the previous monotone line search [Vaswani et al., 2019] and the stochastic Polyak step size method [Loizou et al., 2021].\n 2. See above.\n 3. Our theory is consistent with the literature. In fact, none of the existing nonmonotone rates is faster than their monotone counterpart [Grippo et al. 1986, Raydan 1997, Dai 2002, Zhang and Hager 2004] not even in terms of constants. But nevertheless non-monotonicity has shown to improve practical performance in a variety of settings. Please also see the reply to all reviewers.\n 4. This question is replied half in Section D.2 and half in Section E.2 of the supplementary. In Section D.2, we fix the use of the proposed nonmonotone stochastic line search and study different initial step sizes. In particular, the Polyak step is by far the best initial step among those explored. In Section E.2, we fix the use of the Polyak intial step and analyze different line search methods. The results show that the adapted stochastic Zhang and Hager [2004] line search achieves the best performance, especially because of the dominance in terms of test accuracy and the heavy computational costs of single_batch_grippo.\n\nMiscellaneous:\n Thanks for the suggestion, we will lower the resolution of all images.\n\nLimitations:\n The limitations of PoNoS were partially discussed in the answer to the reviewer's comment on transformers, but a complete frame is given in the reply to Reviewer 9zy1.\n\n\nReferences not in the main paper:\n\n [Ma et al., 2018] Siyuan Ma, Raef Bassily, and Mikhail Belkin. \"The power of interpolation: Understanding the effectiveness of SGD in modern over-parametrized learning\". In International Conference on Machine Learning, pages 3325–3334. PMLR, 2018.\n \n [Dai, 2002] Dai, Yu-Hong. \"On the nonmonotone line search.\" Journal of Optimization Theory and Applications 112 (2002): 315-330.\n "}, {"review_id": "dNfL4nNvPe", "reviewer": "Reviewer_9zy1", "summary": "This paper proposes the use of nonmonotone line search methods to speed up the optimization process of modern deep learning models, specifically Stochastic Gradient Descent (SGD) and Adam, in over-parameterized settings. The proposed method relaxes the condition of a monotonic decrease in the objective function and allows for larger step sizes. The authors introduce a new resetting technique that reduces the number of backtracks to zero while still maintaining a large initial step size. The proposed POlyak NOnmonotone Stochastic (PoNoS) method combines a nonmonotone line search with a Polyak initial step size. The paper proves the same rates of convergence as in the monotone case. The experiments show that nonmonotone methods outperform the rate of convergence and also generalization properties of SGD/Adam.", "questions": "Same as stated in the **Weakness** part.", "limitations": "The limitations of the proposed method are stated not sufficiently. Only future perspectives are stated. For example, considering the local PL assumption. The claims that the proposed method outperforms many other the-state-of-the-art methods from several perspectives are quite strong. Are there any drawbacks, or points to be improved, of the proposed method?", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- **Originality:** The use of nonmonotone line search methods to relax the condition of a monotonic decrease in the objective function is a stochastic generalization of [Zhang and Hager 2004] which was proposed initially for deterministic optimization. The initial step size is chosen on the basis of previous work [Vaswani et al 2019]. The paper also introduces originally a new resetting technique that reduces the amount of backtracks to zero while still maintaining a large initial step size. Overall, the paper's originality is a significant strength. \n\n- **Quality:** The paper provides rigorous proof that the proposed nonmonotone line search method has the same rate of convergence as in the monotone case despite the lack of a monotonic decrease. The experiments show that nonmonotone method has a larger speed of convergence and better generalization properties of SGD and Adam. Computational time comparison experiments also show the outperformance of the proposed method. The theory is solid and the experimental results are strong.\n\n- **Clarity:** The paper is well-written and easy to understand, with clear explanations of technical terms and concepts. Qualitative explanations of the theorems are provided to help the readers understand the main messages. The authors provide detailed descriptions of the proposed method and the experiments conducted to evaluate its performance. Comparisons with other methods are presented clearly.\n\n- **Significance:** The proposed method shows the outperformance of existing state-of-the-art algorithms in both computational time and generalization properties. ", "weaknesses": "- The proposed method includes many parameters to be chosen artificially, such as $\\eta_{\\rm max}$, $c$, $c_p$, $\\delta$, and $\\xi$. Although the ranges of them are provided in the theorems, influences on the performance of the proposed method due to different choices of these parameters are not clear. Are the specific values used in a real experiment not so important? If so, to what extent?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the accurate comments and the time spent reading the paper. \n\nWeaknesses:\n\n  The performance of PoNoS is actually not sensitive to hyperparameters. In fact, the same values work across experiments and there was no need to fine-tune them. Most of PoNoS's hyperparameters were set to very standard values, while others were either inherited by recent papers or fixed by the theory:\n   - $\\delta = 0.5$, classical cut of the step [Nocedal and Wright, 2006]. SLS employs an unusual value of 0.9 and this choice is connected to the use of their resetting technique (3). We checked the results of SLS with $\\delta=0.5$ and they indeed turned out to not be as good as with $\\delta=0.9$.\n   - $\\xi = 1$, fully nonmonotone version of Zhang and Hager [2004].\n   - $\\eta^{\\text{max}} = 10$, very classical value [Vaswani et al., 2019, Loizou et al., 2021]. We conducted an ablation study in Section E.4, which shows that larger values of $\\eta^{\\text{max}}$ do not have a remarkable impact on the results. These results show that PoNoS is more robust than SLS and SPS to these changes.\n   - $c = 0.5$, suggested by the theory. Both our theory and that of Vaswani et al. [2019] suggest employing 0.5 for $c$, rather than the classical 0.1 or lower [Nocedal and Wright, 2006]. The numerical results in Section E.1 of the supplementary support this choice. In particular, they show in Figure VII that $c=0.1$ might bring PoNoS and its monotone counterpart to diverge.\n   - $c_p = 0.1$, half of the inherited value [Loizou et al., 2021]. In Loizou et al. [2021], the value 0.2 was suggested for SPS, however in our case, the initial step size is not the final step since the backtracking procedure might reduce this value to its half (or less). For this reason, we decided to employ a step that is initially double that of SPS. The results show that PoNoS|0.1 is consistently better than PoNoS|0.2 (see Section E.5 of the supplementary). Thus, we also checked whether SPS|0.1 would be consistently better than the original SPS, but this is not the case.\n   \n   \nLimitations:\n\n  - In the case of transformers, PoNoS's advantage over Adam is not consistent with the one obtained for convolutional neural networks. The reason for this seems to be the reduced dynamics of the loss and of the norm of the gradient in the case of transformers. These two values directly determine the Polyak step, which consequently remains very flat along the training (see section D.5 of the supplementary). This observation suggests that (Po)NoS might need to be paired with a new initial step size and/or a different preconditioner for training transformers. \n  \n  - Given the local PL result by Liu et al. [2022], our Theorem 3 can only be considered to hold locally and only for neural networks with some specific properties that are still not completely realistic. In fact, Theorem 8 by Liu et al. [2022] holds only for very wide networks with a squared loss function and whose tangent kernel at initialization is strictly positive deﬁnite. To the best of our knowledge, other works on neural networks use the same assumptions since they are still the closest available to applications.\n  \n  - The $\\xi$ permitted by our theorems is very small. On the other hand, the value employed in practice is large ($\\xi = 1$). We conjecture that the bound on $\\xi$ might be relaxed, even if the final shape of this bound might depend on the solution to the above-mentioned issue on Theorem 3."}]

Author rebuttal:
We would like to thank all six reviewers for their feedback and the time spent reading the paper. Below we comment several reviewers' concerns regarding the lack of a theoretical result showing PoNoS's advantages over the existing methods.

We understand the reviewers' opinion, however we would like to clarify our point of view on this matter. For DL researchers and especially for the possible users of PoNoS, it is of great interest to know that it is numerically faster than state-of-the-art methods while still being backed up by the same convergence rates. This theoretical achievement is not trivial and it is more than what can be obtained for instance by Adam [Reddi et al., 2018]. Despite the lack of a theoretical justification showing why Adam is faster than SGD [Kunstner et al., 2023], Adam has a huge practical impact and it replaced SGD for training transformers. In fact, if we would always require a theoretical justification of the superiority of a method, Adam would probably not be published, while it is becoming one of the most cited works of all time. Another example that is very appropriate for our case, is the spectral projected gradient by Birgin et al. [2000]. In this paper, the authors introduced nonmonotonicity and clever step sizes in a different setting and they showed that the new method works much better in practice without showing a faster convergence rate. This paper was published in a top optimization journal and has more than one thousand citations. 

References not in the main paper:

[Reddi et al., 2018] Reddi, S. J., Kale, S. & Kumar, S. On the convergence of Adam and beyond. 6th International Conference Learning Representation (ICLR), pp. 1–23 (2018).

Meta-review: This paper proposes a new line search method for determining the step size in SGD within the interpolation regime. In contrast to SLS, which relies on the monotonically decreasing Amijo condition, the proposed method adopts a non-monotone line-search (following Zhang and Hager, 2004). The paper continues a line of work that focused on adaptive stepsize/line search methods for finite sum problems under interpolation. The paper highlights cases when the prior methos might be slow, and shows that the proposed method can address this in the mentioned cases.

The paper is well-written, and carefully discussing the placement of the contribution in light of prior work. 

The opinion of the reviewers on this paper were divided, some were not convicted by the numerical evacuation (mostly conduced on small scale) and the many hyperparameters that might make the method difficult to tune on new classes of problems.

One reviewer was championing the paper, by arguing that this paper could impact further research on DL methods with 'non-traditional' stepsizes (e.g. larger what is dictated by conservative worst-case guarantees). Eventually, this lead to recommendation of the committee to propose acceptance (with none of the reviewers opposing this decision).

Please consider adding the clarifications and discussion points from below (especially also the clarifications on the hyperparameters) to the final version of the paper.
Decision: Accept (poster)