Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution
Authors: Antonio Orvieto
Simon Lacoste-Julien
Nicolas Loizou
Venue: NeurIPS 2022 Accept (2022)
Keywords: Optimization
Convex Optimization
SGD
Gradient Descent
Adaptive Methods
Polyak Stepsize

Abstract: Recently Loizou et al. (2021), proposed and analyzed stochastic gradient descent (SGD) with stochastic Polyak stepsize (SPS). The proposed SPS comes with strong convergence guarantees and competitive performance; however, it has two main drawbacks when it is used in non-over-parameterized regimes: (i) It requires a priori knowledge of the optimal mini-batch losses, which are not available when the interpolation condition is not satisfied (e.g., regularized objectives), and (ii) it guarantees convergence only to a neighborhood of the solution. In this work, we study the dynamics and the convergence properties of SGD equipped with new variants of the stochastic Polyak stepsize and provide solutions to both drawbacks of the original SPS. We first show that a simple modification of the original SPS that uses lower bounds instead of the optimal function values can directly solve issue (i). On the other hand, solving issue (ii) turns out to be more challenging and leads us to valuable insights into the method's behavior. We show that if interpolation is not satisfied, the correlation between SPS and stochastic gradients introduces a bias, which effectively distorts the expectation of the gradient signal near minimizers, leading to non-convergence - even if the stepsize is scaled down during training. To fix this issue, we propose DecSPS, a novel modification of SPS, which guarantees convergence to the exact minimizer - without a priori knowledge of the problem parameters. For strongly-convex optimization problems, DecSPS is the first stochastic adaptive optimization method that converges to the exact solution without restrictive assumptions like bounded iterates/gradients.

Dynamies of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution
Antonio Orvieto"
Simon Lacoste-Julien Mila and DIRO, Université de Montréal
Nicolas Loizou AMS and MINDS, Johns Hopkins University
Department of Computer Science, ETH Zürich
Abstract
Recently Loizou et al. [22], proposed and analyzed stochastic gradient descent (SGD) with stochastic Polyak stepsize (SPS). The proposed SPS comes with strong convergence guarantees and competitive performance; however, it has two main drawbacks when it is used in nal-over--prammeterie priori knowledge of the optimal mini-batch losses, which are not available when the interpolation condition is not satisfied (e.g.. regularized objectives), and (ii) it guarantees convergence only to neighborhood of the solution. In this work, we study the dynamics and the convergence properties of SGD equipped with new variants of the stochastic Polyak stepsize and provide solutions both drawbacks the original SPS. We first show that simple modification the original SPS that uses lower bounds instead of the optimal function values can directly solve issue (i). On the other hand, solving issue (ii) turss out be more challenging and leads us to valuable insights into the method's behavior. We show that if interpolation is not satisfied, the correlation between SPS and stochastic gradients introduces a bias, which effectively distorts the expectation of the gradient signal near minimizers, leading to non-convergence even the stepsize is scaled down during training. To fix this issue, we propose DecSPS, a novel modification of SPS, which guarantees convergence the exact minimizer without priori knowledge of the problem parameters. For strongly-conve optimization problems, DecSPS is the first stochastic adaptive optimization method that converges the exact solution without restrictive assumptions like bounded iterates/gradients.
regimes: (i) It requires
1 Introduction
We consider the stochastic optimization problem:
min f(x) = 1 71 ze E
f(x)
where each f, is convex and lower bounded. We denote by X' the non-empty set of optimal points xx of equation (1). We f == min f(x). and fr == inf f((x).
36th Conference on Neural Information Processing Systems (NcurIPS 2022).
"Corresponding author: antonio. orvieto@inf ethz. ch. Part this work was done while interning at Mila, Université de Montréal under the supervision of Nicolas Loizou and Simon Lacoste-Julien. *Canada CIFAR Al Chair

---

In this setting, the algorithm of choice is often Stochastic Gradient Descent (SGD), i.c. x g+1 = xº V V (I*), where 7A > 0 is the stepsize at iteration k, Ss S [n]] random subset of datapoints (minibatch) with cardinality B sampled independently at each iteration k, and Vss, (z) = B Eies, (z((z) is the minibatch gradient.
careful choice of T is crucial for most applications [4, 14]. constant over training, with its value inversely proportional to the Lipschitz constant of the gradient. While this choice yields fast convergence to the neighborhood of minimizer, two main problems arise: (a) the optimal y depends on (often unknown) problem parameters - hence often requires heavy tuning: and (b) it cannot be guaranteed that X is reached in the limit [13, 16, 15]. A simple fix for the last problem is to allow polynomially decreasing stepsizes (second option) [23]: this choice for "I often leads to convergence to X", but hurts the overall algorithm speed. The third option, which became very popular with the rise of deep learning, to implement an adaptive stepsize. These methods do not commit to fixed schedule, but instead use the optimization statistics (e.g. gradient history, cost history) to tune the value of 7 at each iteration. These stepsizes known to work very well in deep learning [35], and include Adam [19], Adagrad [11], and RMSprop [29].
The simplest option is to pick 7/K he
Ideally, a theoretically grounded adaptive method should yield fast convergence to X without knowledge of problem dependent parameters, such as the gradient Lipshitz constant or the strong convexity constant. As result, an ideal adaptive method should require very little tuning by the user, while matching the performance of a fine-tuned "ik- However, while in practice this is the case for common adaptive methods such as Adam and AdaGrad, the associated convergence rates often rely on strong assumptions - e.g. that the iterates live on bounded domain, or that gradients are uniformly bounded in norm [11, 32, 31]. While the above assumptions are valid in the constrained setting, they are problematic for problems defined in the whole Rd.
promising new direction in the adaptive stepsizes literature based on the idea of Polyak stepsizes, introduced by [25] in the context of deterministic convex optimization. Recently [22] successfully adapted Polyak stepsizes the stochastic setting, and provided convergence rates matching fine- tuned SGD while the algorithm does not require knowledge of the unknown quantities such the gradient Lipschitz constant. The results especially shines in the overparameterized strongly convex setting, where linear convergence to x= is shown. This result is especially important since, under the same assumption, no such rate exists for AdaGrad (see e.g. [31] for the latest results) or other adaptive stepsizes. Moreover, the method was shown to work surprisingly well on deep learning problems, without requiring heavy tuning [22].
Even if the stochastic Polyak stepsize (SPS) [22] comes with strong convergence guarantees, it has two main drawbacks when it is used in non-over- aevrrpparameterized regimes: (i) It requires a priori knowledge of the optimal mini-batch losses, which are not often available for big batch sizes or regularized objectives (see discussion in $1.1) and (ii) it guarantees convergence only to a neighborhood of the solution. In this work, we study the dynamics and the convergence properties of SGD equipped with new variants of SPS for solving general convex optimization problems. Our new proposed variants provide solutions to both drawbacks of the original SPS.
1.1 Background and Technical Preliminaries
The stepsize proposed by [22] is
fs. (x*1) f3, 76 }
7A min
(SPS
clV (xx) 22
where 7b. c >> 0 are problem-inndependen constants, fs. : [Sal
1 EiEs, fi, f3. = inf fs, (z).
Dependency on fš.- Crucially the algorithm requires knowledge of fš, for every realization of the mini-batch Sg. In the non-regularized overparametrized setting (e.g. neural networks), fs, is often zero for every subset S [34]. However, this is not the only setting where f3 is computable: e.g., in the regularized logistic loss with batch size 1, it is possible to recover cheap closed form

---

expression for each f; [22]. Unfortunately, if the batch-size is bigger than 1 or the loss becomes more demanding (e.g. cross-entropy), then no such closed-form computation is possible.
Rates and comparison with AdaGrad. In the convex overparametrized setting (more precisely, under the interpolation condition, i.e. xx" E x inf fs(x) = fs(x") for all S, see also $2), SPSmax enjoys a convergence speed of (1/k)) without requiring knowledge of the gradient Lipschitz constant or other problem parameters. Recently, [31] showed that the same rate can be achieved for AdaGrad in the same setting. However, there is an important difference: the rate of [31] is technically OddD² /k), where d is the problem dimension and D is global bound on the squared distance to the minimizer, which is assumed to be finite. Not only does SPS not have this dimension dependency, which dates back to crucial arguments in the AdaGrad literature [11, 21], but also does not require bounded iterates. While this assumption is satisfied in the constrained setting, it has no reason to hold in the unconstrained scenario. Unfortunately, this a common problem of all AdaGrad variants: with the exception of [33] (which works in a slightly different scenario), no rate can be provided in the stochastic setting without the bounded iterates/gradients [12] assumption even after assuming strong convexity. However, in the non-interpolated setting, AdaGrad enjoys convergence guarantee of O(1/Vk) (with the bounded iterates assumption). A similar rate does not yet exist for SPS, and our work aims filling this gap.
1.2 Main Contributions
As already mentioned, in the non-interpolated setting SPS has the following issues: Issue (1): For B (minibatch setting), SPSmax requires the exact knowledge of f3. This is not practical.
Issue (2): SPSmax guarantees convergence to neighborhood of the solution. is not clear how to modify it to yield convergence to the exact minimizer.
Having the above two issues in mind, the main contributions of our work (see also Table for a summary of the main complexity results obtained in this paper) are summarized as follows:
In $3, we provide a direct solution for Issue (1). We explain how only lower bound on få (trivial if all fis are non-negnn negaatieee required for convergence a neighborhood of the solution. While this neighborhood is bigger that the one for SPS modified version provides practical baseline for the solution to the second issue.
We explain why Issue (2) is highly non- non-trivial and requires in-depth study of the bias induced by the interaction between gradients and Polyak stepsizes. Namely, we show that simply multiplying the stepsize of SPS by 1/V which would work for vanilla SGD [23] yields a bias in the solution found by SPS ($4), regardless of the estimation of f's-
In $5, we provide solution to the problem (Issue (2)) by introducing additional structure - as well as the fix to Issue (1) - into the stepsize. We call the new algorithm Decreasing SPS (DecSPS), and provide a convergence guarantee under the bounded domain assumption - matching the standard AdaGrad results.
$5.2 we go one step further and show that, if strong convexity is assumed, iterates are bounded with probability and hence we can remove the bounded iterates assumption. To the best of our knowledge, DecSPS, the first stochastic adaptive optimization method that converges to the exact solution without assuming strong assumptions like bounded iterates/gradients
In $5.3 we provide extensions of our approach to the smooth setting.
In $6, corroborate our theoretical results with experimental testing.
2 Background on Stochastic Polyak Stepsize
In this section, we provide a concise overview of the results in [22], and highlight the main assump- tions and open questions.
To start, we remind the reader that problem (1) is said to be interpolated if there exists a problem solution x" e X such that infzer f((x) fi(x") for all [n]. The degree of interpolation
3

---

Stepsize
Citation
Assumptions
No Knowledge of f
Exact Convergence
Theorem
SPS
[22]
convex, smooth
X
X
Thm.
SPS
This paper
conves, smooth
/
X
Thm. 2, Cor.
DecSPS
This paper
convex, smooth, bounded iterates
V
/
Cor, 2. ((l/v))
This paper
strongly-oonvex, smooth
Thm. 4. ((1/vK)
DecSPS-NS
This paper
conves, bounded lirrates/grads
Coz. 3. (L/vVK)
Table I: Summary of the considered stepsizes and the corresponding theoretical results in the non-interpolated setting. The studied quantity in all Theorems, with respect which all rates are expressed is E [[ f=x''(
where zº Φे E x² In addition, for all converging methods, consider the stepsize scaling factor Ok O(v formally defined in the corresoonding sections. For the methods without exact convergence, show $4 that any different scaling factor cannot make the algorithm convergent.
at batch size can be quantified by the following quantity, introduced by [22] and studied also in [31, 9]: fix a batch size B, and let S S [nx] with |S| B.
o = Es(fs(>") - f3] =f]= Es(ss]
(2)
It is easy to realize that as soon problem (1) is interpolated, then o 0 for each B S n. In addition, note that og is non-increasing as function of B.
We now comment on the main result from [22].
Theorem 1 (Main result of [22]). Let each Ji be L,-smooth convex functions. SPS mini-batch size B. and I, converges as: [f(x*))- - f(x")) S a |10-="11
Then SGD with
2n
where a = minn 2clamse 7b] and x.KK = 2 EK- x² If in addition f u-strongly corvex, then,
for any c 2 1/2, SGD with SPS converges as: 1BI - x01 112 S (1 - (1-)a)² 1|="" x 1 + 2nuae where again a= m zoti (6b and Temax max T. V2 is the maximum smoothness constant.
In the overparametrized setting, the result guarantees convergence to the exact minimizer, without knowledge of the gradient Lipschitz constant (as vanilla SGD would instead require) and without assuming bounded iterates (in contrast to [31]).
As soon as (1) regularizer is applied to the loss (e.g. L2 penalty), or (2) the number of datapoints gets comparable to the dimension, then the problem is not interpolated and SPS only converges to neighborhood and it gets impractical to compute fā - this is the setting we sfudy in this paper.
Remark (What if V fsy = 0?). In the rare case that // /s, [ss"(>)))'"" = 0, there is no need to evaluate the stepsize. In this scenario, the update direction Vss, (a*) = 0 and thus the iterate is not updated irrespective of the choice of step-size. this happens, the user should simply sample a different minibatch. We note that in our experiments (see $6), such event never occurred.
Related work Polyak stepsize: The classical Polyak stepsize [25] has been successfully used in the analysis of deterministic subgradient methods in different settings [5, 7, 18]. First attempts on providing an efficient variant of the stepsize that works well in the stochastic setting were made in [3, 24]. However, as explained in [22]. none of these approaches provide natural stochastic extension with strong theoretical convergence guarantees, and thus Loizou et al. [22] proposed the stochastic Polyak stepsize SPSmax as a better alternative." 3 Despite its recent appearance, SPSmax has already been used and analyzed as a stepsize for SGD for solving structured non-convex problems [15], in combination with other adaptive methods [31], with a moving target [17] and in the update rule of stochastic mirror descent [9]. These extensions are orthogonal to approach, and
A variant of SGD with SPS was also proposed by Asi and Duchi [2] special case of model-based method called the power-truncated model. Asi and Duchi [2] also proposed a decreasing step-size variant of SPS which is closely related but different than the DecSPS that we propose in $5, Among some differences. they assume interpolation for their convergence results whereas we do not in $5, We describe the differences between our work and Asi and Duchi [2] in more detail in Appendix A.

---

Interpolation and 8 >
Interpolation and 8 >
Interpolation and f 0
107
Stl C. op
5p 1/ -
578ben 1/ -
107
-a- SPrlen C' -
107
S1 =09 +
10²
51 -.
Sta 6.
SP -0
+
51% -0
10"
10
10t
3 10
10.
10-3
10-1
10"1
10"1
barations 24
5
10 15 20 25
30 35
10 20 25
30 35
Figure 1: We consider a 100 dim problem with 100 datapoints where each f. ft with fi" for E [n]] and H. random SPD matrix generated using the standard Gaussian matrix H, A, /3d).. If 2; # 2; for é * j. then the problem does not satisfy interpolation
x
Hj x?) +
A, E RRdxd (left plot). Instead, if all = equal, then the problem is interpolated (central plot). The plot shows the behaviour of SPS (7h, = 2) for different choices the approximated suboptimality E, plot (mean and std deviation over 10 runs) the function suboptimality level f(x) - f(a") )) for different values of f Note that, if instead f = 0 for all i then all the shown algorithms coincide (right plot) and converge to the solution.
speculate that our proposed variants can also be used in the above settings. We leave such extensions for future work.
Removing fš from SPS
As motivated in the last sections, computing f3 in the non-interpolated setting is not practical. In this section, we explore the effect of using a lower bound E's S fs instead in the SPS definition.
[s, (x**) fs.. cll fls (x*) 1112: }
min
(SPS
max
Such lower bound is easy get for many problems of interest: indeed, for standard regularized regression and classification tasks, the loss is non-negative hence one can pick E's for any S C [mi].
The obvious question is: what the effect of estimating Ess on the convergence rates in Thm. 1? We found that the proof of [22] is easy to adapt to this case, by using the following fundamental fs, (x))1
fa, (x*) --E
bound (see also Lemma 3): 2al.s.
dIV [+
The following results can be seen easy extension of the main result of [22], under newly defined suboptimality measure:
0 = Es. (s, - f(x))= Es, (...).
(3)
Theorem 2. Under SPS maxe the same exact rates in Thm. I hold (under the corresponding assump- tions), after replacing oB with o²
And we also have easy practical corollary.
Corollary 1. In the context of Thm. 2, assume all J&8 are non-negative and estimate f's = 0 for all S C [n]. Then the same exact rates in Thm. 1 hold for SPSt maax after replacing o² with f f(x*)
A numerical illustration of this result can be found in Fig. 1. In essence, both theory and experiments confirm that, if interpolation is not satisfied, then we have a linear rate until a convergence ball, where the size is optimal under exact knowledge of fš. Instead, under interpolation, all the fis are nog-tegeeive and f 0, then SPSmay=SPS max Finally, in the less common case in practice where f > but we still have interpolation, then SPS converges to the exact solution while SPS max does not. To conclude SPS! iPS does not (of course) work better than SPS but it is practical variant which we can convergence the true z" in the non-interpolated setting.
baseline in $5 for an adaptive stochastic Polyak stepsize with
5

---

4 Bias in the SPS dynamics.
In this section, we study convergence of the standard SPS in the non-interpolated regime, under an additional (decreasing) multiplicative factor, in the most ideal setting: batch size 1, and we have
Jr, (a*)- knowledge of each f?- That is, consider * min ex Vi, (x*) )6) with ct 00, e.g. o =V(F) or c = Okk). We note that, in the SGD case, simply picking egg. 7 =0/ /o/v/k/i + would guarantee convergence of f(z²) to f(z"), in expectation and with high probability [20. 23]. Therefore, it is natural to expect a similar behavior for SPS, if 1/a, safisfies the usual Robbins-Morro conditions [27]: Ex=o 1/ca co, Ei
co.
We show that this is not the case: quite interestingly, f(**) converges to a biased solution due to the correlation between V fi, and Tik we show this formally, in the case of non- non-interpolation (otherwise both SGD and SPS do not require decreasing learning rate).
Counterexample. Consider the following finite-sum setting: f(z) = fz(()) + ff((()) with f1) = / (a - f2(x) = 3 (x + 1)2. To make the problem interesting, we choose di = and 02 1: this introduces asymmetry in the average landscape with respect to the origin. During optimization, we sample (1 and f2 independently and seek convergence to the unique minimizer x= 01-02 1/3. The first thing notice is that x= is not stationary point for the dynamics 4:4-02
under SPS. Indeed note that since f = 0 for i 1,2 we have (assuming Tb large enough): N% fi, (x) = g-1 if is = 1, and 7 f., (z) ++1 if is = 2.
Crucially, note that this update is curvature centtturr-ideeeedeen. The expected update is E., hYs fi, (z) =
1 x. Hence, the iterates can only converge to z because this is the only fixed x-1 + 1ep 2cg
dct
point for the update rule. The proof naturally extends the multidimensional setting, an illustration
can be found in Fig. 2.
No interpolation
Interpolation
In the same picture, we show how our modified variant of the vanilla stepsize - we call this new algorithm DecSPS, see $5 - instead converges to the correct solution.
inttaalzttions
intialioniius
SP'
DeeSPS
Remark 2. SGD with (non-adaptive) stepsize Y' instead keeps the curvature, and therefore is able to correctly estimate the average E,, [7x Vi,, (x)] =
Jtk (a1 + 02) x 2
-1-0z] 41 tag - precisely because
Yk is independent from Vfu. From this
feln)
see that SGD can only converge to the correct stationary point x= 01-42
f(x)
a1+42 because again
Figure 2: Dynamics of SPS with decreasing multiplicative constant (SGD style) compared with DecSPS. We compared both in the interpolated set- ting (right) and in the non-interpolated setting (left). In the lad- setting, simple multiplicative factor introduces bias in the final solution, dis- cussed in this section. We consider two dimensional fi = {xr ) H.(x= 2;). for i = 1,2 and plot the contour lines of the corresponding landscapes, as well as the average landscape (ff + fa)/2 we soek to minimize. Solution is denoted with gold star.
this is the only fixed point for the update rule.
In the appendix, we go one step further and pro- vide an analysis of the bias of SPS in the one- dimensional quadratic case (Prop. 4). Yet, we expect the precise characterization of the bias phe- nomenon in the non-quadratic setting to be partic- ularly challenging. We provide additional insights in $D.2. Instead, the next section, we show how to effectively modify 76 to yield convergence aeeeeetssssssio assumptions.
xx without further
5 DecSPS: Convergence to the exact solution
We propose the following modification of the vanilla SPS proposed in [22], designed to yield convergence to the exact minimizer while keeping the main adaptiveness properties*. We call it Decreasing SPS (DecSPS), since it combines a steady stepsize decrease with the adaptiveness of SPS.
Similar choices are possible. We found that this leads to the biggest stepsize magnitude, allowing for faster convergence in practice.

---

1
min (5*) Es.
Tkk =
[V (x*))|2 Ck- 1 17-1 ))
(DecSPS)
Ck
for l E N, where en o 0 for every lo E N. We set C-1 cn and 7-1 74 0 (stepsize bound,
similar to (22]), to get 7 == 1 min 1s, (=,(=")-
[
Co7
Lemma 1. Let each Si be Li smooth and let (cx)le be any non-decreasing positie sequence of real numbers. Under DecSPS, we have min
Coll
S 7
I Cu7b and "/k-1 S "
2ey
Remark 3. As stated in the last lemma, under the assumption of c non-decreasing, Y is trivially non-increasing since "ik S Ck-17R-1/G--
The proof can be found in the appendix, and is based on a simple induction argument.
5.1 Convergence under bounded iterates
The following result provides a proof of convergence of SGD for the % sequence defined above.
Theorem Consider SGD with DecSPS and let (ck) be any non-decreasing sequence such that Ck 1, Vik E N. Assume that each fü is convex and Li smooth. We have:
2C 2ek-ILD2
K
( -
(4)
K
Ck
k=0
where 22 maxx<((-1] 11 2²1/2 i: max max; (Li); 20071 and ..K 1/ =k= x..
K-
If 63 = 0, then c = for all E N leads to a rate ) well known from [22]. If o3 > 0, as for the standard SGD analysis under decreasing stepsizes, the choice = O(vk) k) leads to an optimal asymptotic trade-off between the deterministic and the stochastic terms, hence to the asymptotic rate ((L/Vk) since E VK+I S 2VK. Moreover, picking co = minimizes the speed of convergence for the deterministic factor. Under the assumption that o < LD² (c.g. reasonable distance initialization
and Lmax > 1//%), this factor is dominant compared to the factor involving 0z3. For this setting, the rate simplifies as follows.
Corollary 2. Under the setting of Thm. for Ca = /k + (c-1 co) we have
(((="))((x"))) 2i.D² 20
(5)
VK
Remark (Beyond bounded iterates). The result above crucially relies on the bounded iterates assumption: 1)2 < oc. To the best of our knowledge, if no further regularity is assumed, modern convergence results for adaptive methods (e.g. variants of AdaGrad) in convex stochastic program- ming require² this assumption, or else require gradients to be globally bounded. To mention few: [11, 26, 32, 8, 31]. A simple algorithmic fix to this problem is adding cheap projection step onto a large bounded domain [21]. We can of course include this projection step in DecSPS, and the theorem above will hold with no further modification. Yet we found this to be not necessary: the strong guarantees of SPS in the strongly convex setting [22] let us go one step beyond: in $5.2 we show that, if each f. is strongly convex (e.g. regularizer is added), then one can bound the iterates globally with probability one, without knowledge of the gradient Lipschitz constant. To the best of knowledge, no such result exist for AdaGrad except [30], for the deterministic case.
Remark 5 (Dependency on the problem dimension). In standard results for AdaGrad, a dependency on the problem dimension often appears (c.g. Thm. in [31]). This dependency follows from a bound on the AdaGrad preconditioner that can be found e.g. in Thm. in [21]. In the SPS case no such dependency appears - specifically because the stepsize lower bounded by 1/22x)
Perhaps the only exception is the result of [33]. where the authors work on different setting: i.e. they introduce the RUIG inequality.
7

---

5.2
Removing the bounded iterates assumption
We prove that under DecSPS the iterates live in a set of diameter Dmxx almost surely. This can be done by assuming strong convexity of each ft-
The result uses this alternative definition of neighborhood: 8 B,,ax == maxsgin,,St Ez).
Note that trivially Bax < under the assumption that all ft are lower bounded and oc. Proposition 1. Let each Si be pi-strongly convex and Le-smooth. The ilerates of SGD with DecSPS with ck .k++ (and c-1 co) are such that ||
x=12 -x-12 < D almost surely
vk N. where D max max 1|000 x=1
with Pmnin min ( and 200"10 B.max
min
Teemas Mumin 7aa
Lmax = maxie[n] Li-
The proof relies on the variations of constants formula and an induction argument - it is provided in the appendix. We are now ready to state the main theorem for the unconstrained setting, which follows from Prop. and Thm. 3.
Js. (x")132 TV (-+))) -k-
Theorem 4. Consider SGD with the DecSPS stepsize "ik := vk+1 min
for k 2 1 and to defined as the beginning this section. Let each fü be pe-strongly convex and Ly-smooth:
2T.D2 max + 200
(6)
VK
Remark 6 (Strong Convexity). The careful reader might notice that, while assumed strong convexity, our rate is slower than the optimal O11/K). This is due to the adaptive nature of DecSPS. It is indeed notoriously hard to achieve a convergence rate of O K) for adaptive methods in the strongly convex regime. While further investigations will shed light on this interesting problem, we note that the resull we provide somewhat unique in the literature: we are not aware any adaptive method that enjoys a similar convergence rate without either (a) assuming bounded iterates/gradients or (b) assuming knowledge of the gradient Lipschitz constant the strong convexity constant.
Remark 7 (Comparison with Vanilla SGD). On a convex problem, the non-asymptotic performance of SGD with decreasing stepsize * = n// V strongly depends on the choice of 1). The optimizer might diverge if 1y is too big for the problem hand. Indeed, most bounds for SGD, under no access to gradient Lipschitz. constant, display a dependency on the size of the domain and rely on projections after each step. If one applies the method in the unconstrained setting, such convergence rates technically do not hold, and tuning is sometimes necessary retrieve stability and good performance. Instead, for DecSPS, simply by adding small regularizer, the method is guaranteed converge the non-asymptotic rate we derived even in the unconstrained setting.
5.3 Extension to the non-smooth setting
For any S C [n). denote in this section by (s(r) the subgradient of fs evaluated at x. We discuss the extension of DecSPS to the non- setting.
straightforward application of DecSPS leads to a stepsize " which no longer lower bounded (see Indeed, the gradient Lipschitz constant in
Lemma by the positive quantity min 2e.4maxx a the non-smooth case is formally Lmax = 0o. Hence, ?/ prescribed by DecSPS can get arbitrarily small for finite kt One easy solution to the problem is to enforce a lower bound, and adopt a new proof technique. Specifically we propose the following:
Cara
(x**
l'ss , ,Ct-17 18a-1n-1
mhk =
min
max
Co78,
19s, (x
(DecSPS-NS)
"Take for instance the deterministic setting one- diddemsinionnl setting f(z) = |x]. As r - 0. the stepsize prescribed by DecSPS converges zero. This is not the case e.g. in the quadratic setting.
8

---

where # O for every & 2 0, Ve 2 is small positive number and all the other quantities are defined as in DecSPS. In particular, as for DecSPS, we set c_1 co and 7-1 "h. Intuitively, 7 is (see proof in $F, appendix), but has subgradient- dependent adaptive value. In addition, this stepsize is enforced to be monotonically decreasing.
selected to live in the interval [cote/ce, c07b/Ck) /c/l
Theorem 5. For any non-decreasing positive sequence (c+)R=o consider SGD with DecSPS-NS. Assume that each fo is convex and lower bounded. We have
Elf(**) f(xx)] Cx-1D²
K-1 Σ Como km0
+
K
Ck
where D² = max || - x² 2? and G² := max 99s, (x*)
One can then easily derive an O(1/Vk) convergence rate. This is presented in SF (appendix).
Numerical Evaluation
We evaluate the performance of DecSPS with c = co l + on binary classification tasks, with regularized logistic loss f(z) = 1 Ei= log(1 + exp(y: a, x)) + 3|211² where a; E I2 is the feature vector for the i-th datapoint and y/ E 1] is the corresponding binary target.
We study performance three datasets: (1) a Synthetic Dataset, (2) The AIA dataset [6] and (3) the Breast Cancer dataset [10]. We choose different regularization levels and batch sizes bigger than 1. Details are reported in $G, and the code is available at https: /gi thub. www.aoroo/a/a/e.e wawoiittoeeeeieeee DecSPS. At the batch sizes and regularizer levels we choose, the problems do not satisfy interpolation. Indeed, running full batch gradient descent yields f > 0. While running SPS on these problems (1) does not guarantee convergence to f* and (2) requires full knowledge of the set of optimal function values {ff) is n. in DecSPS we can simply pick the lower bound
f'' I fā for every S. Supported by Theorems 3 & & 5, expect SGD with DecSPS to converge the minimum f"
Stability DecSPS. DecSPS has two hyperparameters: the upper bound Tb on the first stepsize and the scaling constant co- While Thm. 5 guarantees convergence for any positive value of these hyperparameters, the result of Thm. 3 suggests that using co 1 yields the best performance under the assumption that B < LD² (e.g. reasonable distance of initialization from the solution, and Lmax 1//w). In Fig, 3, we show the synthetic dataset that (1) in this setting and (2) the performance of SGD with DecSPS is almost independent of %. Similar findings are reported and commented in Figure 7 (Appendix) for the other datasets. Hence, for all
1 is indeed the best choice
further experiments, we choose the hyperparameters 76 = 10, co 1.
Comparison with vanilla SGD with decreas- ing stepsize. We compare the performance of DecSPS against the classical decreasing SGD stepsize / + 1, which guarantees conver- gence to the exact solution the same asymp- totic rate DecSPS. We show that, while the asymptotics are the same, DecSPS with hyper- parameters cn = 1, %/ 10 performs compet- itively to fine-tuned 17 where crucially the optimal value of 7 depends on the problem. This behavior is shown on all the considered datasets, and reported in Figures 4 (Breast and Syn- thetic reported in the appendix for space constraints). If lower regularization (1e 4, le 6) is considered, then DecSPS can still match the performance of tuned SGD but further tuning is needed (see Figure 14. Specifically, since the non-regularized problems do not have strong curvature, we found that DecSPS works best with a much higher 76 parameter and co 0.05.
Decass
SeeffS bec5ss.
De3'5 de = js
+ 1.26. /
3.26, (8
3.38.n 300
3.00.
31*
19:00
X00
1000)
4000
2000 12.22 10:03 B20
Figure 3: DecSPS (Cp- Co Co + sensitivity to hyperparameters on the Synthetic Dataset, with À = 0. Repeated 10 times and plotted is mean and std.
DecSPS yields truly adaptive stepsize. We inspect the value of 7h returned by DecSPS, shown in Figures 4 & 8 (in the appendix). Compared to the vanilla SGD stepsize n/ / + I, crucial difference appears: 7h decreases faster than ((1/Vk). This showcases that, while the factor /k +

---

can be found in the formula of DecSPS", the algorithm structure provides additional adaptation to curvature. Indeed, in (regularized) logistic regression, the local gradient Lipschitz constant increases as we approach the solution. Since the optimal stepsize for steadily-decreasing SGD is 1/(Lvk where L is the global Lipschitz constant [13], it is pretty clear that v) should be decreased over training for optimal converge (as T. effectively increases). This is precisely what DecSPS is doing.
Comparison with AdaGrad stepsizes. Last, we compare DecSPS with another adaptive coordinate- independent stepsize with strong theoretical guarantees: the norm version of AdaGrad (a.k.a. AdaGrad- -loGrad-Norm, AdaNorm), which guarantees the exact solution at the same asymptotic rate as DecSPS [32]. AdaGrad-noma at each iteration updates the scalar b Dig + V/ (mx))) and then selects the next step as F&+1 Ik
" V (xx)). Hence, it has tuning parameters bn and 77. In Fig. 4 we show that, the Breast Cancer dataset, after fixing 60 0.1 recommended in [32] (see their Figure 3), tuning 7) cannot quite match the performance of DecSPS. This behavior is also observed on the other two datasets we consider (see Fig. 9 in the Appendix). Last, in Fig. 10& 11 in the Appendix, we show that further tuning of by likely does not yield a substantial improvement.
Regularized A1A SGD Vs DeeSPS
Regularized Breast Cancer AdaGrad-Norm VS DeeSPS
Acatorn Aet -+ becifi dy Lo00g
bechts Lo0.
121
10000
75004
127
SAAESONACE THOSE ERTM SChM
155
147
12
Figure 4: Left: performance of DecSPS, on the AIA Dataset (A 0.01). Right: performance of DecSPS on the Breast Cancer Dataset (A = le 1). Further experiments can be found in $G (appendix).
Comparison with Adam and AMSgrad without momentum. In Figures 5& 12& we compare DecSPS with Adam [19] and AMSgrad [26] on the AIA and Breast Cancer datasets. Results show that DecSPS with the usual hyperparameters is comparable to the fine-tuned version of both these algorithms which however do not enjoy convergence guarantees in the unbounded domain setting.
Regularized A1A DecSPS Vs Adam
Regularized Breast Cancer DecSPS Vs AMSgrad
A Asam, 9-630 g-0a00: sasm, pet p-02313 sams p4t.20 p000000
drapat beids Iice caapat sesa W85get f-655 mid 2008 nears we
2000
11000h004 MC
9o
Parasaan.0 01
Figure 5: Left: Performance Adam (with fixed stepsize and no momentum) and Right: AMSgrad (with sqrt decreasing stepsize and no momentum) compared to DecSPS on AIA and Breast Cancer dataset, respectively. Plots comparing the performance of Adam with DecSPS on the Breast Cancer Dataset can he found in Figure 13, and plots comparing AMSgrad with DecSPS on the A1A Dataset can he found in Figure 12. Plotted is also the average stepsize (each parameter evolves with different stepsize).
7 Conclusions and Future Work
We provided practical variant of SPS [22], which converges to the true problem solution without the interpolation assumption in convex stochastic problems matching the rate of AdaGrad. If in addition, strong convexity is assumed, then we show how, in contrast to current results for AdaGrad, the bounded iterates assumption can be dropped. The main open direction is proof of a faster rate O1/KK) under strong convexity. Other possible extensions of our work include using the proposed new variants of SPS with accelerated methods, studying further the effect of mini-batching and non-uniform sampling of DecSPS, and extensions to the distributed and decentralized settings.
We pick cs covk= + I, suggested by Cor. 2 &
10

---

Acknowledgements
This work was partially supported by the Canada CIFAR Al Chair Program. Simon Lacoste-Julien is a CIFAR Associate Fellow in the Learning in Machines & Brains program.
References
[1] H. Asi and C. Duchi. The importance of better models in stochastic optimization. Proceedings of the National Academy Sciences, 116446):2292--22930, 2019.
[2] H. Asi and J. C. Duchi. Stochastic (approximate) proximal point methods: Convergence, optimality, and adaptivity. SIAM Journal on Oplimization, 29(3):2257-2290, 2019.
[3] L.. Berrada, A. Zisserman, and M. Kumar. Training neural networks for and by interpolation.
In International Conference Machine Learning, 2020.
[4] I.. Bottou, F. E. Curtis, and Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):23--31, 2018.
[5] S. Boyd, L. Xiao, and A. Mutapeic. Subgradient methods. Lecture Notes of EE392o, Stanford University, Autumn Quarter, 2004:2004-2005. 2003.
[6] C.-C. Chang. LIBSVM: library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2011.
[7] D. Davis, D. Drusvyatskiy, K. J. MacPhee, and C. Paquette. Subgradient methods for sharp weakly convex functions. Journal of Optimization Theory and Applications. 179(3):962-982, 2018.
[8] A. Défossez, Bottou, Bach, and N. Usunier. A simple convergence proof of Adam and Adagrad. arXiv preprint urXiv:2003.02395, 2020.
[9] R. D'Orazio, N. Loizou, I. Laradji, and I. Mitliagkas. Stochastic mirror descent: Conver- gence analysis and adaptive variants via the mirror stochastic Polyak stepsize. arXiv preprint arXiv:2110.15412, 2021.
[10] D. Dua and C. Graff. UCI machine learning repository, 2017. URL http://///rrrr uci edu/ml.
[11] Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(7), 2011.
[12] A. Ene and H. L. Nguyen. Adaptive and universal algorithms for variational inequalities with optimal convergence. arXiv preprint arXiv:2010.07799 2020.
[13] S. Ghadimi and Lan. Stochastic first-and zeroth-ordes methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4), 2013.
[14] I. Goodfellow, Y. Bengio, and A. Courville. Deep Learning. MIT press, 2016.
[15] R. Gower, O. Sebbouh, and N. Loizou. SGD for structured nonconvex functions: Learning rates, minibatching and interpolation. In International Conference Artificial Intelligence and Statistics, 2021.
[16] R. M. Gower, N. Loizou, X. Qian, A. Sailanbayev, E. Shulgin, and Richtárik. SGD: General analysis and improved rates. International Conference on Machine Learning, 2019.
[17] R. M. Gower, A. Defazio, and M. Rabbat. Stochastic Polyak stepsize with moving target. arXiv preprint

---

[18] E. Hazan and S. Kakade. Revisiting the Polyak step size. arXiv preprint arXiv: 1905.00313, 2019.
[19] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. 14 2014.
[20] H. Kushner and G. G. Yin. Stochastic Approximation and Recursive Algorithms and Applica- tions, volume 35. Springer Science & Business Media, 2003.
[21] K. Y. Levy, A. Yurtsever, and V. Cevher. Online adaptive methods, universality and acceleration. Advances in Neural Information Processing Systems, 31, 2018.
[22] N. Loizou, S. Vaswani, I. H. Laradji, and S. Lacoste-Julien. Stochastic Polyak step-size for SGD: An adaptive learning rate for fast convergence. In International Conference Artificial Intelligence and Statistics, 2021.
[23] A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approxmaatinn approach to stochastic programming. SIAM Journal on Optimization, 19(4):1774-109, 2009.
[24] A. M. Oberman and M. Prazeres. Stochastic gradient descent with Polyak's 's learning rate. arXiv preprint arXiv: 1903,08888, 2019.
[25] B. Polyak. Introduction to Optimization. Inc., Publications Division, New York, 1987.
[26] J. Reddi, S. Kale, and Kumar. On the convergence of Adam and beyond. International Conference on Learning Representations, 2018.
[27] H. Robbins and S. Monro. A stochastic approximation method. The Annals of Mathematical Statistics, 1951.
[28] M. Rolinek and G. Martius. L4: Practical loss-based stepsize adaptation for deep learning. Advances in neural information processing systems, 31, 2018.
[29] T. Tieleman and G. Hinton. Lecture 6.5 RMSprop, Coursera: Neural networks for machine learning. University of Toronto, Technical Report, 2012.
[30] C. Traoré and E. Pauwels. Sequential convergence of AdaGrad algorithm for smooth convex optimization. Operations Research Letters, 49(4):452-455 2021.
[31] S. Vaswani, I. Laradji, F. Kunstner, S. Meng, M. Schmidt, and Lacoste-Julien. Adaptive gradient methods converge faster with paraeeerrieattiiinnn (but you should do line-search). arXiv preprint arXiv:2006.06833 2020.
[32] R. Ward, X. Wu, and L.. Bottou. Adagrad stepsizes: Sharp convergence over nonconvex landscapes. International Conference on Machine Learning. 2019.
[33] Y. Xie, X. Wu, and R. Ward. Linear convergence of adaptive stochastic gradient descent. In International Conference on Artificial Intelligence and Statistics, 2020.
[34] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021.
[35] Zhang, S. Karimireddy, Veit, Kim, Reddi, S. Kumar, and S. Sra. Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems, 33, 2020.
12


Reviews:
[{"review_id": "eimEDeL9G0U", "reviewer": "Reviewer_CpM5", "summary": "This paper presents a novel variant of Stochastic Polyak Stepsizes (SPS) providing adaptation when the usual interpolation assumption does not hold, as soon as a lower bound of the loss is known.\n\nThe authors explain first that traditional SPS methods \n- (1) require the knowledge of the optimal loss on any batch which is often not the case and \n- (2) only converge theoretically to a neighborhood of the solution \n\nAuthors provide a practical fix which is to replace the optimal loss on any batch by a lower bound of the loss (often 0 as many losses are non-negative) and call this algorithm SPS_max^l as it is a variant of SPS_max proposed in [Loizou et al, 2021]. Moreover, to enforce convergence to the solution, they make the upper bound of the adaptive step size decrease at each iteration in O(1/sqrt(k)) and provide convergence guarantees in O(1/sqrt(K)) of this new algorithm call DecSPS:\n- for convex and smooth losses with a lower bound and bounded iterates\n- for strongly convex and smooth losses with a lower bound (thus removing the bounded iterate assumption)\nFinally, they extend their method to the non-smooth setting by enforcing a lower bound on their SPS version leading to DecSPS-NS and prove also O(1/sqrt(K)) convergence for\n- convex non-smooth losses with a lower bound, bounded iterates and bounded subgradients  \n\nFinally, authors run experiments on regularized logistic regression on 3 datasets\n- one small synthetic\n- two small real datasets A1A and Breast Cancer\n for which interpolation is not met. They compare the performance of DecSPS with AdaGrad-Norm and SGD with decreasing \n\nThey also give elements indicating that their method is not too sensible to \\gamma_b : the upper bound of DecSPS and that the decrease of the step size thus computed is faster than O(1/sqrt(k)) which shows real curvature adaptation.\n\n~~~~\nScore updated to 8 to support the paper after the answer of the authors to the question \"What would be the downsides of using DecSPS or SPS instead of SGD?\" (by reviewer 98CJ).", "questions": "The paper is very clear, reasoning is easy to follow and going though the proofs was a pleasure.\n\nLet me start with typos and nitpicking:\n- A1) Only cited equations should be numbered. Useful cited equations are flooded in all the numbered equations (makes it harder to navigate in the proofs)\n- A2) line 68 : \"Dependency on f_{S_k}^*\" star is missing\n- A3) lines 102-105 : precise \"in section 4\"\n- A4) line 167 & 172 : strange too read \"$f_i$s\"\n- A5) line 171 : \"linear rate\" right ?\n- A6) line 229: gamma is decreasing not increasing (this typo appears several times eg in E.1)\n- A7) line 232: \"appendix E.1\" to simplify the reading\n- A8) line 240: Strange way of calling both terms in (4) : both are deterministic. Better to say \"distance-to-the-solution term\"  and a \"noise\" term\n- A9) line 243 : strange \"distance initialization-solution\" -> instead initialization-solution distance ?\n- A10) line 254 : \"regularizer is added\" and then interpolation is thus lost, right ? \n- A11) line 273 : better to stick with notations with c_k and c_{k-1}. There is no point changing this only here\n- A12) Footnote 3 page 7 : miscitation. [31] should be cited here. No RUIG inequality in [30]\n- A13) In Lemma E.1, I do not think $a \\leq 1$ is required. If it were, then it would imply that one would need to set $\\gamma_b$ such that $\\mu_{\\min} \\gamma_b \\leq 1$ in (114)\n- A14) Eq 107 Minus sign missing and I would put a $\\leq$ at the RHS \n- A15) Same typo : step sizes are decreasing not increasing\n- A16) line 762 : \\alpha_k are non-negative\n- A17) eq (126) I think a constant 2 is lost on the left-hand side. It would give a sharper result, nothing important asymptotically\n- A18) line 783 : J*E*nsen not Jansen\n  \n\nMore major questions :\n- B1) I am not sure to be aware of all results in adaptive and SPS methods so I wonder what are the known classical results in the domain. A small table like in A.1 would have helped summarizing assumptions and known results for methods cited in the second paragraph of 1.1. I hope the other reviewers will have a clear opinion whether this convergence result without bounded iterates nor gradients nor using the smoothness constant nor the strong convexity value is novel or not. If not, it would worth citing relevant works.\n- B2) line 325 : Could you precise why you say that \\gamma_b = 10 is \"theoretically inspired\" ? I find it a bit incorrect.\n- B3) line 334-335 : Could you provide a reference or a quick explanation why the local gradient Lipshchitz constant increases near the solution ?\n- B4) As pointed out in weaknesses, the regularization parameters used are way too large. The problems become very simple too solve and as we are talking about optimization methods for Machine Learning than we should keep in mind that our goal is to have good generalization of our model and I doubt that this is the case here. I would like to see the results for \\lambda = 1e-4 and 1e-6.\n- B5) Lack of consistency in the setting of hyperparameters depending on the methods: DecSPS parameters are set on the real datasets A1A and Breast whereas the b_0 for Adagrad-norm is set on the synthtetic data set... Why ?\n", "limitations": "We would definitely need to see how pratical this new methods are in practice on large models or at least on difficult logistic regression problems (easy to find real-sim or rcv1.binary dataset on LIBSVM Data: Classification (Binary Class) website)\n\nI already mentioned this in weaknesses but the DecSPS method comes with 2 or 3 hyper-parameters to tune which I think is not in fact taking us away from \"adaptivity\".\n\nNot really a limitation but potential extension: as the authors point out in their conclusion:\n- they still unable to prove O (1/K) convergence for strongly convex objective", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n- Problem and interest of the paper well posed\n- Good review of existing methods (in the appendix for more details) in the interpolation case\n- Solid theoretical guarantees (I went though all the proofs and everything looks correct)\n- The paper is particularly well written, good intuition is given in the proofs which are easy to follow and makes the intentions clear to the reader\n\n\nWeaknesses:\n- The experimental section is very light. I know it's a common (and sometimes easy criticism) but I was a bit disappointed by the experiments which are focusing on regularized logistic regression on 3 small datasets. See experiments on CIFAR-10 or CIFAR-100 of [1], [2] and [3]\n- the regularization in the experiments is way too large in my opinion. Makes the problems solved way too simple... \n- A paper proposing a new SPS methods without comparing it *numerically* to previous variants (SPS_max [1], Ali-G [2], SPSL1 from [1] and maybe other) is a bit problematic. I would have expected experiments on a \"gradient\" of experiments from non interpolated to interpolated like done in the motivational plot (but on a larger problem) by playing on the regularization.\n- It looks like the price to pay for \"adaptivity\" is to tune 2 parameters (c_0 and \\gamma_b) or 3 (additional \\gamma_l) in the non-smooth case. The authors try to show numerically that numerical results are not too sensitive to these values but as in previous points, Imo experiments are not exhaustive enough to conclude.\n\n[1] Loizou et al, Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence (2021)\n[2] Berrada et al, Training Neural Networks for and by Interpolation (2020)\n[3] Gower et al, Cutting Some Slack for SGD with Adaptive Polyak Stepsizes (2022)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "cSeYpQxImaF", "reviewer": "Reviewer_bV6Q", "summary": "\nThis paper proposes DecSPS, which aims at improving the convergence of SPS in two aspects: (1) removing the optimal minibatch loss in the step sizes by replacing it with a lower bound, and (2) proving that DecSPS converges to the exact minimizer in the strongly convex setting by showing that the iterates are bounded in the strongly convex setting. ", "questions": "\nPlease see above.", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nStrengths:\n\n1. The overall writing is clear and easily understandable, and the proof is also well-organized.\n2. The contributions of this work are also clearly stated.\n\nMajor concerns:\n\n1. Overall, the theoretical contributions are not very significant. The proof of the almost sure boundedness of iterates (Proposition 5.4) is novel, which helps establish that DecSPS can reach the exact minimizer under strong convexity. On the other hand, removing the optimal minibatch loss in the step sizes by replacing it with a lower bound is nice in practice, but does not need a complicated adjustment in the proof. \n\nMore results can be added to this work if possible. For example, does DecSPS have similar properties as in Theorem 3.1 and 3.8 of [22] for strongly convex and nonconvex settings?\n\n2. In the numerical results, comparisons with other adaptive methods such as Adam and RMSProp should also be added. \n3. Also, more numerical results on benchmarks of deep learning can be added, e.g. ResNet56 on Cifar10, which nearly satisfies the interpolation condition. Does DecSPS have an advantage over other adaptive methods?\n\nMinor concerns:\n\n1. It would be better if Table 1 can be put in the main text, as it provides a succinct summary of the main results.\n2. The role of parameter $\\gamma_b$ in SPS and DecSPS should be explained. This parameter follows from [22], but it should still be introduced and discussed here.\n3. The fonts of legends and x, y axis should be larger in the figures.\n4. In line 227, the $k$ in the formula should be $0$\n5. In line 282, and or should be and/or\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "MchbsCNI4q6", "reviewer": "Reviewer_Z1Lm", "summary": "This work further investigates the use of stochastic Polyak stepsizes (SPS) first proposed in Loizou et al. (2021). The prior work had several limitations, essentially requiring that the global optimum is 0 (known) and that all minibatch samples are also minimized by the global minimizer. This work lifts this restriction and extends the analyses to the case where only a lower bound of the global optimum is known and when interpolation does not happen. The use of Polyak-type stepsizes in stochastic optimization is a relatively new direction, so many basic foundational questions about the setup need to be addressed. The discussion of section 4 provides insight into the bias in the SPS dynamics via a simple counter-example, and this nicely and clearly illustrates the difference between the SPS dynamics and that of the usual SGD dynamics. The newly proposed DecSPS is tested with some brief convex experiments, but no experiments on deep learning are done.", "questions": "In what way are the rates for DecSPS stronger compared to the prior rates on SGD?", "limitations": ".", "rating": 4, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This work has some nice contributions, as it addresses some of the clear limitations of the prior SPS by Loizou et al. (2021). The line of research on SPS is new and, in my view, quite promising, so this work provides some clear value to the field\n\nOverall, however, I feel that this work is a necessary, natural, but an incremental follow-up to Loizou et al. (2021). The analysis is not highly distinct or novel compared to the prior work. While there are certainly some new and interesting insights, the resultant rate is not really strong; under the interpolation assumptions, Loizou et al. (2021) established nice fast rates, but by lifting such assumptions, it seems that the rates are no longer surprising or impressive compared to the SGD rates. I found the results interesting, and I think this paper will serve as a good step forward in the SPS line of work, but I am not sure if these results are strong enough to be published in NeurIPS.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "G6rgLLFS8id", "reviewer": "Reviewer_98CJ", "summary": "This paper presents a method called DecSPS, which is based on a modification of stochastic Polyak stepsize (SPS). The proposed DecSPS method provides an exact convergence to the optimum value and is not dependent on prior knowledge of problem parameters. As a result, DecSPS achieves an exact solution without any restrictive assumptions such as bounded gradients and is the first stochastic adaptive optimization method. ", "questions": "- How about the time complexity? Does it take more time than the existing algorithm?\n- Should we directly start using SPS, or present the algorithm DecSPS instead of other methods like SGD with diminishing step sizes?\n\n", "limitations": "The limitations are briefly discussed within the paper, both in Introduction and conclusion. There is no negative societal impact of work. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## STRENGTHS\n\n- The modification performed on top SPS is minor and can be easily implemented. \n- The paper is well written, structure is easy to follow.\n\n## WEAKNESSES\n- In figure 2, the example consists of 2 variables. It might be a good starting point but it is essential to have a model which can be adapted to larger scale experiments. Now we can run the experiments in a cloud system,..\n- Minor typo :\n... is bigger that the one for SPS_{\\max}...\n... is bigger **than** the one for SPS_{\\max}...\n- In Figure 3. sensitivity analysis could be performed for more seeds, 3 might be too less, it would be nice to see an error bar.\n- The overall contribution is not too effective.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept