Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reduction
Authors: Xiaowen Jiang
Sebastian U Stich
Venue: NeurIPS 2023 poster (2023)
Keywords: Convex Optimization
SGD
Adaptive Methods
Variance Reduction
Polyak Stepsize
Line-Search
TL;DR: We propose AdaSPS and AdaSLS, adaptive gradient methods, which yield fast and robust convergence. We further accelerate both algorithms with novel variance-reduction.

Abstract: The recently proposed stochastic Polyak stepsize (SPS) and stochastic line-search (SLS) for SGD have shown remarkable effectiveness when training over-parameterized models. However, two issues remain unsolved in this line of work. 

First, in non-interpolation settings, both algorithms only guarantee convergence to a neighborhood of a solution which may result in a worse output than the initial guess. While artificially decreasing the adaptive stepsize has been proposed to address this issue (Orvieto et al.), this approach results in slower convergence rates under interpolation. Second, intuitive line-search methods equipped with variance-reduction (VR) fail to converge (Dubois-Taine et al.). So far, no VR methods successfully accelerate these two stepsizes with a convergence guarantee.

In this work, we make two contributions:
Firstly, we propose two new robust variants of SPS and SLS, called AdaSPS and AdaSLS, which achieve optimal asymptotic rates in both strongly-convex or convex and interpolation or non-interpolation settings, except for the case when we have both strong convexity and non-interpolation. AdaSLS requires no knowledge of problem-dependent parameters, and AdaSPS requires only a lower bound of the optimal function value as input. Secondly, we propose a novel VR method that can use Polyak stepsizes or line-search to achieve acceleration. When it is equipped with AdaSPS or AdaSLS, the resulting algorithms obtain the optimal rate
for optimizing convex smooth functions. Finally, numerical experiments on synthetic and real datasets validate our theory and demonstrate the effectiveness and robustness of our algorithms.

Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reduction
Xiaowen Jiang
Sebastian U. Stich CISPA* stich@cispa.de de
CISPA
xiaowen. xiaowen. jia.ggnipaangg
Abstract
The recently proposed stochastic Polyak stepsize (SPS) and stochastic line- search (SLS) for SGD have shown remarkable effectiveness when training over- parameterized models. However, two issues remain unsolved this line of work. First, in non-interpolation settings, both algorithms only guarantee convergence to neightorhood of solution which may result in worse output than the initial guess. While artificially decreasing the adaptive stepsize has been proposed to address this issue (Orvieto al. (44)), this approach results in slower convergence rates under interpolation. Second, intuitive line-search methods equipped with (VR) fail converge (Dubois- Taine et [4] ). So far, no VR methods successfully accelerate these two stepsizes with a convergence guarantee. In this work. make two contributions: Firstly, propose two new robust variants of SPS and SLS, called AdaSPS and AdaSLS, which achieve optimal asymptotic rates in both strongly-convex interpolation settings, except for the case when we have both strong convexity and non-interpolation. AdaSLS requires no knowledge of problem-dependen parameters, and AdaSPS requires only a lower bound of the optimal function value input. Secondly, propose novel VR method that can use Polyak stepsizes line-search to achieve acceleration. When it is equipped with AdaSPS or AdaSLSS the resulting algorithms obtain the optimal rate optimizing convex smooth functions. Finally, numerical experiments on synthetic and real datasets validate our theory and demonstrate the effectiveness and robustness our algorithms.
convex and interpolation
non-
Introduction
Stochastic Gradient Descent (SGD) 46 and its variants 7 are among the most preferred algorithms for training modern machine learning models. These methods only compute stochastic gradients in each iteration, which is often more efficient than computing full batch gradient. However, the performance SGD highly sensitive to the choice of the stepsize. Common strategies use a fixed stepsize schedule, such keeping it constant or decreasing it over time. Unfortunately, the theoretically optimal schedules are disparate across different function classes [8), and usually depend problem parameters that are often unavailable, such as the Lipschitz constant of the gradient. As result, a heavy tuning of the stepsize parameter is required, which is typically expensive practice.
Instead of fixing the stepsize schedule, adaptive SGD methods adjust the stepsize on the fly [5 26 These algorithms often require less hyper-parameter tuning and still enjoy competitive performance in practice. Stochastic Polyak Stepsize (SPS) 34 6 45 is one of such recent advances. It has received rapid growing interest due to two factors: (i) the only required parameter the individual optimal function value which is often available in many machine learning applications and (ii) its adaptivity
*CISPA Helmholtz Center for Information Security, Saarbrücken, Germany
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

utilizes the local curvature and smoothness information allowing the algorithm to accelerate and converge quickly when training parrmarrmetrized models. Stochastic Line-Search (SLS) [52] is another adaptive stepsize that offers exceptional performance when the interpolation condition holds. In contrast to SPS, the knowledge of the optimal function value not required for SL.S, at the cost of additional function value evaluations per iteration.
An ideal adaptive stepsize should not only require fewer convergence, in the sense that they can automatically adapt to the optimization setting (interpolation vs. non- -nn-ieerpoolaion.. This will bring great convenience to the users in practice as they no longer need to choose which method to use (or runinning both of them at double the cost). Indeed, in many real-world scenarios, it can be challenging to ascertain whether a model is effectively interpolating the data or not [T]]. For instance, the feature dimension of the rev1 dataset [IO] is twice larger than the number of data points. A logistic regression model with as many parameters as the feature dimension may tend to overfit the data points. But the features are actually sparse and the model not interpolated. Another example is federated learning [23] where millions of clients jointly train a machine learning model on their mobile devices, which usually cannot support huge-scale models. Due to the fact that each client's data is stored locally, it becomes impractical to check the interpolation condition.
but should also enjoy robust
While SPS and SLS are promising adaptive methods, they are not robust since both methods cannot converge to the solution when interpolation does not hold. Orvieto et al. [44] address this issue for SPS by applying an artificially decreasing rule and the resulting algorithm DecSPS is able to converge as quickly as SGD with the optimal stepsize schedule. However, the convergence rates of DecSPS in interpolation regimes are much slower than SPS. For SLS,, no solution has been proposed.
If the user is certain that the underlying problem is non-interpolated, then applying variance- reduction (VR) techniques can further accelerate the convergence [22] 40 I3
27
49 33). While
gradient descent with Polayak stepsize and line-search perform well in the deterministic settings, there exists method that successfully adapt these stepsizes in VR methods. Mairal 36 and Schmidt et al. [49] proposed to use stochastic line-search with VR. However, no theoretical guarantee is shown. Indeed, this a challenging open question as Dubois- Taine et al. [14] provides a counter-example where classical line-search methods fail in the VR setting. As such, it remains unclear whether we can accelerate SGD with stepsizes from Polyak and line-search family in non-interpolated settings.
1.1 Main contributions
In this work, we provide solutions to the aforementioned two challenges and contribute new theoretical insights on Polyak stepsize and line- search methods. We summarize our main contributions as follows:
In Section we propose the first robust adaptive methods that simultancously achieve the best- known asymptotic rates in both strongly- or convex and interpolation or non non- interpolation settings except for the case when we have strongly-convexitt and non-interpolation. The first method called AdaSPS, variant of SPS, requires only a lower hound of the optimal function value as input (similar to DecSPS) while AdaSLS, the second method based on SL.S, is parameter-free In the non-interpolated setting, we prove for both algorithms an (11/²2) convergence rate for convex functions which matches the classical DecSPS and AdaGrad [15] results, whereas SPS and SLS cannot converge in this case. In the interpolated regime, we establish fast (log(1/s)) and ((1/e) rates under strong convexity and convexity conditions respectively, without knowledge of any problem-depenndet parameters. In contrast, DecSPS converges at the slower ((1/s²) rate and for AdaGrad, the Lipschitz constant is needed to set its stepsize [56).
In Section 4 we design a new variance-reduction method that is applicaple to both Polyak stepsizes line-search methods. We prove that reach an e-accuracy, the total number of gradient evaluations required in expectation is On + 1/e) ) for convex functions which matches the rate of Ad [14). With our newly proposed decreasing probability strategy, the artificially designed multi-stage inner-outer-loop structure is not needed, which makes our methods easier to analyze.
Our novel VR FR-frraework is based on proxy function sequences and can recover the standard VR methods 22 as special case. We believe that this technique can be of independent interest the optimization community and may motivate more personalized VR techniques in the future.
2

---

Interpolation
Non-interpolation
Stepsize
strongl--covvex
convex
required input
strongly-convex
conve
required input ft
SPS/SPS
O(log( ())
(Q2
Fr
<2 9(
22 0(17,a)
SLS 52
Ologg ())
O(H)
None
8 M(r).))
2 ((rj.)
None 4
DecSPS 44
((2))
((2)
6.
((2)
o(2)
AdaSPS (this work)
Ogoog())
((+)
((+)
((+)
C.
AdaSLS (this work)
(1))
O(2)
Nome
((3)
o(3)
None
"The assumption of bounded iterates is also required except for SPS and SLS.
Table I: Summary of convergence behaviors of the considered adaptive stepsizes for smooth functions. For SPS/SPSmxx and SLS in non-interpolation settings, S?()) indicates the size of the neighborhood that they can converge to, the other cases, the O(+) complexity provides the total number of gradient evaluations required for each algorithm to reach an (e)) suboptimality. For convex functions, the suboptimality is defined as E[f(xr) - f"] and for strongly convex functions, the suboptimality is defined as [[|[xT xx x*|]"].
strongly convess Interpolatien
strongl conves ex Interpelation
interpolation
convext enterpparrllattooo
105
10'
161
16a
10f
10'
0054-
20
106 F"
100
10-5
207
10-1
10
107
101
1000
2000
2000
4000
2500
5000
7500 10000
10000
20000
mminn-tttchh gradennt evaluations
mini-batch grad ant evaluations
mini-botch gradient ecsiuations
mminbbathh gradient evalustions
DecSPS
SLS
AdoSPS
AdaSLS
Figure 1: Illustration of the robust convergence of AdaSPS and AdaSLS on synthetic data with quadratic loss. SPS and SLS have superior performance on the two interpolated problems but cannot converge when the interpolation condition does not hold. DecSPS suffers from slow convergence on both interpolated problems. (Repeated times. The solid lines and the shaded area represent the mean and the standard deviation.)
1.2 Related work
Line-search procedures has been successfully applied to accelerate large-scale machine learning training. Following [52], Galli et al. [16) propose to relax the condition of monotone decrease of objective function for training over-parameterized models. Kunstner et al. (30) extends backtracking line-search to multidimensional variant which provides better diagonal preconditioners. In recent years, adaptive stepsizes from the AdaGrad family have become widespread and are particularly successful when training deep neural networks. Plenty of contributions have been made analyze variants of AdaGrad for different classes of functions [15] 51
43 55 56], among which Vaswani al. 53 first propose to use line-search to set the stepsize for AdaGrad to enhance its practical performance. More recently, variance reduction has successfully been applied to AdaGrad stepsize and faster convergence rates have been established for convex and non-convex functions [4 25).
originally designed as subgradient method for solving non-smooth convex problems. Hazan and Kakade (20) show that PS indeed gives simultaneously the optimal convergence result for a more general class of convex functions. Nedić and Bertsekas [38) propose several variants of PS as incremental subgradient methods and they also discuss the method of dynamic estimation of the optimal function value when it is not known. Recently, more effort has been put into extending deterministic PS the stochastic setting 47 6 (2). However, theoretical guarantees of the algorithms still remain elusive until the emergence of SPS/SPS [34]. Subsequently, further improvements and new variants such as DecSPS 44 and SPS with moving target [17] have been introduced. A more recent line of work interprets stochastic Polyak stepsize as subsampled Newton Raphson method and interesting algorithms have been designed based on the first-order local expansion
Another promising direction is the Polyak stepsize (PS) 45
[17 [8] well as the second-orde expansion (3T]. Wang et (54) propose to set the stepsize for SGD with momentum using Polyak stepsize. Abdukhakimov al. employ more general preconditioning techniques to SPS.
3

---

There has been recent line of work attempting to develop methods that can adapt to both the interpolation setting and the general growth condition beyond strong convexity. Using the iterative halving technique from [5) Cheng and Duchi [II] propose AdaStar-G which gives the desired property if the Lipschitz constant and the diameter of the parameter domain are known. How to remove these requirements is an interesting open question for the future research.
2 Problem setup and background
2.1 Notations
In this work, we consider solving the finite-sum sum smooth convex optimization problem:
f(x) - Σ fi(x)
min XER
(1)
This type of problem appears frequently in the modern machine learning applications [9] where each
[x(x) represents the loss of a model the i-th data point parametrized by the parameter x. Stochastic
Gradient Descent (SGD) [46] is one of the most popular methods for solving the problem ① At each iteration, SGD takes the form:
X++1 = x, T/p fr, (x;),
(2)
where ny is the stepsize parameter, is S [n] is a random set of size B sampled independently each iteration and f,, (x) B Eiet, fx() is the minibatch gradient.
Throughout the paper, we assume that there exists a non-empty set of optimal points X C IRd and we use f* to denote the optimal value of f at point x* E X*. We use ft₃ denote the infimum of minibatch function fú, (Ir), i.e. Ji, infxeR" B Eies, f((x). We assume that all the individual functions [fi(x) are I-ssmothh Finally, we denote the optimal objective difference, first introduced in (34), by 7BBB f E,, [ The definitions for the interpolation condition can be defined
and studied in various ways 48
9 4 11. Here, we adopt the notion from [34. The problem (I)
said to be interpolated if of
O, which implies that 8).8 0 for all B S n since o7,B B is
non-inereasing w.r.t B. Note interpolation implies that the global minimizer of is also a minimizer of each individual function fi.
2.2 SGD with stochastic polyak stepsize
(x,
Loizou et al. propose set the stepsize 1/: 7/e 21 (x:)) which is well known as the Stochastic Polyak stepsize (SPS). In addition to SPS, they also propose a bounded variant SPSmax (f
fú,
which has the form 17 min (2 fi, [x.]]== }6} where 7 > 0. Both algorithms require the input of the exact fü, which is often unavailable when the batch size B > 1 or when the interpolation condition does not hold. Orvieto et al. 44] removes the requirement for fü and propose set f) as:
N रे min { fu, (x,)
fx, vin-11 fort 2 1 (DecSPS), where yo > 0 is a constant and é is an input lower bound such that E ft. In contrast the exact optimal function value, a lower bound f is often available in practice, in particular for machine learning problems when the individual loss functions are non-negative. We henceforth denote the estimation error by:
erry, J.B B- = E. [f:
For convex smooth functions, SPS achieves a fast convergence up to a neighborhood of size Moz) n) where = min I 7.) Note that the size
and its variant. SPS converges up to li0 //////// 7///aa) of the neighborhood cannot be further reduced by choosing an appropriate 76- In contrast, DecSPS converges at the rate of (1 (1/VT)) which matches the standard result for SGD with decreasing stepsize. However, the strictly decreasing ((1/vt) stepsize schedule hurts its performance in interpolated settings. For example, DecSPS has a much slower O(1/VT) convergence rate compared with the fast O(exp(-Tp//n
rate of SPS when optimizing strongly-convex objectives. Therefore, both algorithms do not have the robust convergence property (achieving fast convergence guarantees in both interpolated and non-interpolated regimes) and we aim fill this gap. See Figure for a detailed illustration of the non-robustness of SPS and DecSPS.

---

3
Adaptive SGD with polyak stepsize and line-search
In this section, we introduce and analyze two adaptive algorithms to solve problem (T).
3.1 Proposed methods
AdaSPS. Our first stepsize is defined as the following:
(x+) t cp (x)]l
Th min
17--1
with 771 = +00, (AdaSPS)
VEi (x,) Ex,
where e is an input parameter that must satisfy E S fit and cp > 0 is an input constant to adjust the magnitude of the stepsize (we discuss suggested choices in Section
AdaSPS can be seen as an extension of DecSPS. However, unlike the strict ((L/vt) decreasing rule applied in DecSPS, AdaSPS accumulates the function value difference during the optimization process which enables it to dynamically adapt to the underlying unknown interpolation settings.
AdaSLS. We provide another stepsize that be applied even when lower bound estimation is unavailable. The method is based on line-search and thus is completely parameter-free but requires additional function value evaluations in each iteration:
7
7/ min
T/- 1
with 77-1 +00
(AdaSLS)
CtV E. % (x,)]l2
where cj > is an input constant, and the scale nt is obtained via stardard Armijo backtracking line-search (see Algorithm 4 for further implementation details in the Appendix D such that the following conditions are satisfied:
(x, %a2 (x.,)))) S fx.( PVvllVVV.... (x,)11 and Vt S Ymaxx 0 <<p<1,
(4)
for line-search parameters Ymax and By setting the decreasing factor 3 Σ defined in Algorithm
4
can show that 7 2 min( 1 7/max). We give formal proof in Lemma 16 Appendix A.2
Discussion. Our adaptation mechanism in AdaSPS/AdaSI.S is reminiscent of AdaGrra type methods, in particular to AdaGrad-Noos Norm, the scalar version of AdaGrad, that aggregates the gradient norm in the denominator and takes the form f)+
Og
where Cg > 0 and bf 2
VJ, (x,))1++bg
The primary distinction between AdaSPS and AdaSLS compared to AdaGrad-Norna is the inclusion of an additional component that captures the curvature information at each step, and not using squared gradient norms in AdaSPS. contrast to the strict decreasing behavior of AdaGrad-Norm. AdaSPS and AdaSLS can automatically mimic a constant stepsize when navigating flatter region.
Vaswani al. [53] suggest using line-search to set the stepsize for AdaGrad-Nowe which takes the where %/ S 7t-1 is required for solving non- non-interpolated convex
form 7/s Eا= (x,)],
24
problems. While this stepsize is similar to AdaSLS, the scaling of the denominator gives suboptimal convergence rate as we demonstrate in the following section.
3.2 Convergence rates
In this section, we present the convergence results for AdaSPS and AdaSLS. We list the helpful lemmas Appendix The proofs can be found Appendix B
General convex. We denote X' to be convex compact set with diameter D such that there exists solution x" X' and supx,yex |xx y1|2 D2 We let 11x denote the Euclidean projection onto X. For general convex stochastic optimization, it seems inevitable that adaptive methods require the bounded iterates assumption or an additional projection step prove convergence due to the lack parameters [12 15). Here, we employ the latter solution by
of knowledge of running projected stochastic gradient descent (PSGD):
X 1xx(x; The f., (x:)).
(5)
5

---

Theorem 1 (General convex), Assume that f is convex, each f. is L-smooth and X is comvex compact feasible set with diameter D. PSGD with AdaSPS or AdaSLS converges as:
Tpy
of J.B + +
- T
(AdaSPS): B[f(Rr) - fr1 v
+
VT
(6)
(AdaSIS): ((]()r) |-| -
+
T
VT
where XT = 1 T - X Tp = (20 + 2/ and πं = max
L (I-plye' Tmax J JDD2+ +
avv
As a consequence of Theorem if err = o = 0, then PSGD with AdasPS or AdaSLS
converges as (()). Suppose Ymax is sufficiently large, then picking &p = VILD and oj = VLD
vi-g
gives a 0 ((P))) rate under the interpolation condition, which is slightly worse than -||xa-X'11 obtained by SPS and SLS but is better than O LD
7
obtained by DecSPS. If otherwise o7.B > 0,
VT
then AdaSPS, AdaSLS, and DecSPS converge as ((1/VT) which matches the rate of Vanilla SGID with decreasing stepsize. Finally, AdaGrad-Nomn Norm gives similar rate in both cases while AdaGrad-
53 shows suboptimal rate of O 1 12',3/20) ). It is worth noting that SPS, DecSPS and SLS require an additional assumption on individual convexity.
Norm with line-search
T
VT
Theorem 2 (Individual convex+innerrolation)) Assume that I is convex, each Ji is convex and
L-smooth, and that ent = =o fB = 0, by setting Cp = -ing(xo)-Fr, and at =
/V/ool/V fio (x))
with constants crcale 2 and eqcate z 1, then for any T 2 1, SGD (no projection) with AdaSPS or
AdaSLS converges as:
11x0 - x*1 x1121 fro (xo) - -
I. T.|1x0
-x112
(AdaSPS) E[f(xr) [AL( 2
Eig
(7)
T
and
(cgrale)2
[xo- - x²1
L
|x0
1=1
(AdaSLS) B[J(xr) - -8]]
Eig
1 Lm Tmax)
col
V fio (xn)]
T
(8)
where XT- = ET X
The result implics that the bounded iterates assumption is not needed if we have both individual convexity and interpolation by picking Cp and e to satisfy certain conditions that do not depend on unknown parameters. To our knowledge, no such result exists for stepsizes from the AdaGrad family, It is worth noting that the min operator defined in AdaSPS or AdaSLS is not necessary in the proof.
Remark 3. We note that for non- con-interpolated problems, AdaSPS only requires the knowledge of tú while the exact ft, is needed under the interpolation condition. We argue that in many standard machine learning problems, simply picking zero will suffice. For instance, ft, = 0 for over-parameterized logistic regression and after adding a regularizer, f = O.
Strongly convex. We now present two algorithmic behaviors of AdaSPS and AdaSI.S for strongly convex functions. In particular, We show that 1) the projection step can be removed as shown in DecSPS, and 2) if the interpolation condition holds, the min operator is not needed and the asymptotic linear convergence rate is preserved. The full statement of Lemma 3 can be found in Appendix B.2
Lemma 4 (Bounded iterates). Let each fr be u-strongly convex and Lmoohhh. For any t = O...., T the iterates of SGD with AdaSPS or AdaSLS satisfy: I|x, -x112 < D for a constant D specified in the appendix in Equation (B.16).
Corollary 5 (Individual strongly convex). Assume each fa is p-strongly convex and I--mooth, Theorem 7 holds with PSGD and D replaced by SGD and Dunax defined in 4
Although it has not been formally demonstrated that AadGrad/AdaGrad-aia tion on bounded iterates for strongly convex functions, we believe that with a similar proof technique, this property still holds for AdaGrra//AdaGrrd-Nooo
can relax the assump-

---

We next show that AdaSPS and AdaSLS achieve linear convergence under the interpolation condition. Theorem 6 (Strongly convex + individual convex + interpolation). Consider SGD with AdaSPS (AdaSPS) or AdaSLS ) stepsize. Suppose that each f. is convex and L-smooth, f p
strongly convex and that J.B = err O. If let cp (10 and C = PV Pho20lVVho (x00)l
with constants egaae 2 1 and equule 1, then AdaSPS or AdaSLS converges
-1|x++1-x* - xx11]] Eio (1
(fig (xx) -
(AdaSPS)
1x0 1x11, (9)
(2egcale L X20 x x1)2
and
E| x1 x11 s Bio (1 u22 ( (--,, 7max / / Vio (xo))l2) T
(AdaSLS)
|
[x0 |xx0-x111
(crolee) Xn x1
(10)
The proof of Theorem 6 is presented in Appendix B.3 the other stepsizes. Under the same settings, DecSPS has slower O(1/ VT) rate due to the usage of @(1/v3 decay stepsize. While AdaGrad-None accumulator grows large, to avoid an (11/E) slow down, the parameters of AdaGrad-Norm have to satisfy Cg bu/Z L, which requires the knowledge of Lipschitz constant [56]. Instead, the conditions on Cp and at for AdaSPS and AdaSLS only depend on the function value and gradient norm at Xo which be computed at the first iteration. SPS, SLS, and Vannilia-SGI with constant stepsize achieve faster linear convergence rate of order O (exp((=# (T)) It is worth noting that Vannila-SGD further remove the individual convexity assumption.
We now compare the above results with
does have linear acceleration phase when the
Discussion. In non-interpolation regimes, AdaSPS and AdaSLS only ensure a slower O(1vVT) convergence rate compared with O(1/T) rate achieved by vanilla SGD with ( decay stepsize when optimizing strongly-conver functions 77]. To our knowledge, no parameter-fre freee adaptive stepsize exists that achieves such a fast rate under the same assumptions. Therefore, developing an adaptive algorithm that can adapt to both convex and strongly-convex functions would be significant further contribution.
4 AdaSPS and AdaSLS with variance-reduction
Combining variance-reduction (VR) with adaptive Polyak-stepsize and line-search to achieve acceler- ation natural idea that has been explored in the last decade 44 36 However, it remains an open challenge as no theoretical guarantee has been proven yet. Indeed, Dubois-Taine et al. [4] provide a counter-example for intuitive line-search methods. In Appendix we provide counter-exand caampe- of the classical SPS and its variants. The reason behind the failure is the biased curvature information provided by fú. that prevents global convergence. In this section, we introduce a novel framework to address this issue. Since there exists many variance-reduee stochastic gradient estimators, we focus on the classical SVRG estimator this section, and our framework also applies to other estimators such as SARAH 40
4.1 Algorithm design: achieving variance-reduction without interpolation
is known that adaptive methods such as SPS or SL. converge linearly on problems where the interpolation condition holds, i.e. f(x) with ,.8 =0. 0.
For problems that do not satisfy the interpolation condition, our approach is to transition the problem to an equivalent one that satisfies the interpolation condition. One such transformation is to shift each individual function by the gradient of fx) at x*, i.e. Fx(x = fx(x) V'V''''V'''''' (x()).. In this case f(x) can be written f(x) Σr (x) due to the fact that Σ Di=1 fi(*)) 0. Note that which implies that each F2(x) shares the same minimizer and
(x(x*) = (x(x - fi(x))
thus the interpolation condition is satisfied (o 0). However, V (x*) is usually not available at hand. This motivates to design the following algorithm.
7

---

Algorithm (Loopless) AdaSVRPS and AdaSVRLS
Require: Xy E RR HP > 0, cp > or Ci > 0
I: set We Xo, 771 +00
2: for ( = to 7
do
3: uniformly sample C [n]]
4: set F,, (x) = (x) + T (V((w.) (w.)) + - x111 -x: cp Fi (F
5: T min
M1-1 (AdaSVRPS)
6: T = min
NV II, (x.) M7-1) (AdaSVRLS TJ V F., (xx)
7: X(+1
Hxx (x:
8: W1+1 = (w,
with probability 1 - P++1
Xt with probability P++1
9: return XT = T ΣE
4.2 Algorithms and convergence
Inspired by the observation, we attempt to reduce the variance of the functions o7.B by constructing a sequence of random functions {Fi, (x)) such that o² Σ. (x),8 + 0 as x, - x*. However, directly applying SPS or SLS to { Fi, (x)} still requires the knowledge of the Lipschitz constant to guarantee convergence. This problem can be solved by using our proposed AdaSPS and AdaSLS. The whole procedure of the final algorithm summarized in Algorithm [|
At each iteration of Algorithm D we construct a proxy function by adding two quantities to the minibatch function fü. (x), where #r ||x xel? a proximal term that helps improve the inherent stochasticity due to the partial information obtained from fú, (x). The additional inner product quantity is used to draw closer the minimizers of fú, (x) and fxx). Following (27 33]. the full gradient is computed with coin flip probability. Note that Algorithm T still works with v) replaced with SVRG and AdaSVRG stepsize since FF; (x,) = fi, (x,) VT,, (w,) + V.((w.). and thus
this framework can be seen generalization of the standard VR methods. A similar idea can also be found in the works on federated learning with variance-reduction
[32]
37 50)
Theorem 7. Assume each fo is convex and L smooth and X' is a convex compact feassbbee set with 1 with 0 < < 1. Algorithm 7 converges as:
diameter D. Let Pt aF+T
1 + (1-a)RF
1)
(AdaSVRPS)
Exf(xT) - fr
+
(11)
T
(AdaSVRIS) ([
1
(1-O)uF
2L
max
L +
1
D2
1
(12)
T
[1 p)vp'
immx vp
Ct cvp
where XT EL- X2.
Suppose Tmax is sufficiently large, then picking 10 = OLL), ct ((LD)) ) and = 0
VLD
yields an ( LD² T rate which matches the O -11x rate of full-batch gradient descent except for a larger term 2 due to the lack of knowledge the Lipschitz constant.
T
Corollary 8. Under the setting of Theorem 7 given an arbitrary accuracy e, the total number of gradient evaluations required to have [x(((T) f < in expectation is O(log(1/s)m 1/e).
The proved efficiency of stochastic gradient calls matches the optimal rates of SARAH 40VSVR and AdaSVRG [144 but removes the artificially designed inner and outer loop size. However, note that Algorithm I requires an additional assumption on individual convexity. Unfortunately, we believe this
Awhere y is obtained via the Armijo backtracking line-search (Algorithm 4 which satisfies: Fi, (x: 7t V.V (xx)) & (x.) prx PPllVV [V., (x:)l1 and T Tmaxx.

---

strunggh-ceervss winpeeersssiiillaaaaaaaa innerpolaatinn
convarinntopsaalion
30
10a
10
10a
301
167
101
10
107
100
10-1
107
10
10
10
10
1000
2000
2003
4000
0
5000
10000
10000
20000
* mini-batch gradient aealvalions
miri-batich gradiant ovallstions
mini-batchh biii-bbthh gradient evaluations
* -ibiibbtchh gradient avals ation
AdaEVRLS
AdaSVRPS
AdGLLS
AdaSPS
Figure 2: Illustration of the accelcrated convergence of AdaS and AdaSVRLS on quadratic loss without interpolation. Both algorithms require less gradient evaluations than AdaSPS and AdaSLS for optimizing -nterrprrpol problems. However, they are less efficient for solving interpolated problems. (Repeated times. The solid lines and the shaded area represent the and the standard deviation.)
assumption is necessary for the VR methods to work for the algorithms in the Polyak and line-search family since SPS/SLS has to assume the same condition for the proof in the interpolation settings.
Discussion. The classical SVRG with Armijo linc-search (presented as Algorithm 6 in (14) employs the same gradient estimator as SVRG but chooses its stepsize based on the returning value of line-search on the individual function ft. Similarly, SVRG with classical Polyak stepsize uses the individual curvature information of f: to set the stepsize for the global variance-reduced gradient. Due the misleading curvature information provided by the biased function fs, both methods have convergence issues. In constrast, Algorithm | reduces the bias by adding correction term x" (w,) fi, (w.)) with global information to fi and then applying line-search or Polyak- stepsize on the veriance-reduced functions Fi,. This difference essentially guarantees the convergence.
Numerical evaluation
In this section, we illustrate the main properties of our proposed methods in numerical experiments. A detailed description of the experimental setup can be found in Appendix We report the theoretically justified hyperparameter scale or cicale as defined in Theorem 6 rather than Cp or a in the following.
Synthetic data. We illustrate the robustness property on class of synthetic problems. We consider the minimization of quadratic of the form: f(x) Σ" fx(x) where fx(x) = 2 (x, (x
by), b; E Rd and A; E dxd is a diagonal matrix. We use n = 50, d = 1000. We can control the convexity of the problem by choosing different matrices A,, and control interpolation by either setting all (b;} to be identical or different. We generate a strongly convex instance where the eigenvalues of [x)(x) are between 1 and 10, and general convex instance by setting some of the eigenvalues to small values close to zero (while ensuring that each 2 fx)((x) is positive semi-definite). The exact procedure generate these problems described in Appendix F
For all methods, we use a batch size B 1. We compare AdaSPS and AdaSLS against DecSPS 44), SPS 34 and SLS [52] illustrate the robustness property. More comparisons
be found in We fix sccaee = cscale = 1 for AdaSPS/AdaLLS and use the optimal parameters for DecSPS and SPS. In Figure]] I we observe that SPS does not converge in the -on-interpolated settings and DecSPS suffers from slow O(1/VT) convergence on the interpolated problems. AdaSPS and AdaSIS show the desired convergence rates across all cases which matches the theory. When the problems are non-interpolated, AdASVRPS and AdaSVRLS illustrate faster convergence, which can be seen in Figure 2
Appendix F. 1
Binary classification on LIBSVM datasets. We experiment with binary classification on four diverse datasets from [0). We consider the standard regularized logistic loss: f(x) = _ >n= log(1 +
exp(-3 - a. x)) + 1 |||||2 where (a, y:) E IR++1 are features and labels. We defer the study of variance-reduction methods to Appendix F.2 for clarity of presentation. We benchmark against popular
optimization algorithms including Adam (26). SPS (34), DecSPS [44], SLS [52] and AdaGrad-
Norm 15 We fix geale qiaale 1 for AdaSPS/AdaLS and pick the best learning rate from
We observe that Adam, SPS and SI.S have remarkable performances on duke with 48 and d 7129, which satisfies interpolation. AdaSPS
{10*) )= 4.... for SGD, Adam and AdaGrad-Noon

---

duke
rcvl
Ijeun
10"
10"4
10-4
Grodknt Norm
Gradben Norm
10-1
Grodknt Norm
Gradient Norm
10:11
10.2
Low
10-4
500
1000
1500
5000 10000 15000
10000
20000
30000
10000 20000 30000
mini-butch gradient avalusiions
miri-batch gradient esalaation
mini-batch gracient evalustions
mirkibbtch gradient evalatevvalnn evalaations
DecSPS
SPS
5G0
SLS
Adom
AcoSLS
ASaSPS
AdsNoom
Figure 3: with batch size B = 1 for duke, / = 64 for revl, B 64 for ijenn and B 128 for w8a. AdaSPS and AdaSLS have competitive performance on revl, ijenn, and w8a while SPS, SLS, and Adam converge on duke. (Repeated times. The solid lines and the shaded area represent the mean and the standard deviation.)
Comparison of AdaSPS/AdaSLS against six other popular optimizers on four LIBSVM datasets.
CIRAR100-ReNNatt
0.825
20
0.70
10-1
Accuan Accuury
0.65
UGS
0.875
2014
0.60
Taain
10-
Maallytoey of
0.825
10-
0:55
10
0.30
103
150
200
100
130
200
30
100
230
200
Epoch
Eboch
Epodh
Esoch
Adam
(DL)
DocSPS
Figure 4: Comparison of the considered optimizers on multi-class classification tasks with CIFAR10 and CIFAR 100 datasets using ResNet34 with softmax loss.
and AdaSLS consistently perform reasonably well on the other three larger datasets. It worth noting that the spperrparameters equale and eitale are fixed for all the datasets, which is desired in practice.
Deep learning task. We provide heuristic extension of AdaSPS to over-parameterized non-convex optimization tasks to illustrate its potential. We benchmark the convergence and generalization performance of AdaSPS (DL) for the multi-class classification tasks on CIFAR10 10 [28] and CI- FARI00 [29] datasets using ResNet-34 (21). More experimental details can be found in Appendix G
We demonstrate the effectiveness of AdaSPS (DL) in Figure
Discussion. AdaSPS and AdaSLS consistently demonstrate robust convergence across all tasks and achieve performance par with, if not better than, the best-tuned algorithms. Consequently, it is reliable and convenient for practical use.
Conclusion and future work
We proposed variants of SPS and SLS algorithms and demonstrated their robust and fast convergence in both interpolated and non-interpolated settings. We further accelerate both algorithms for convex optimization with a novel variance reduction technique. Interesting future directions may include: accelerating AdaSPS and AdaSLS with momentum, developing effective robust adaptive methods for training deep neural networks, designing an adaptive algorithm that gives a faster rate OL1/T) under strong convexity, extensions to distributed and decentralized settings.
Acknowledgments
appreciate the fruitfuu discussion with Anton Rodomanov.
10

---

References
[1] Farshed Abdukkakimovv Chulu Xiang, Dmitry Kamzolov, and Martin Takáč. Stochastic gradient descent with preconditioned polyak step-size. arXiv preprint arXiv:3310.00093, 2023.
[2] Durmus Alp Emre Acar, Yue Zhao, Ramon Matas Navarro, Matthew Mattina, Paul N Whatmough, and Venkatesh Saligrama. Federated learning based on dynamic regularization. arXiv preprint arXiv:2111.04266, 2021.
[3] Larry Armijo. Minimization of functions having lipschitz continuous first partial derivatives. Pacific Journal of Mathematics, 16(1):1-3, 1966.
[4] Hilal and John Duchi. Stochastic (approximate) proximal point methods: Convergence, optimality, and adaptivity. SIAM Journal on Optimization, 29(3):2257-2290, 2019.
[5] Hilal Asi, Daniel Lévy, and John C Duchi. Adapting to function difficulty and growth conditions in private optimization. Advances in Neural Information Processing Systems, 34:19069 1999099999811, 2021.
[6] Leonard Berrada, Andrew Zisserman, and M. Pawan Kumar. Training neural networks for and by interpolation. In Proceedings of the 37th International Conference on Muchine Learning, ICML'20.
JMLR.org, 2020.
[7] Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223-111, 2018. doi: 10. 10.1137/16M1000173.. URL htttps://doi.org//t
16M1080173
[8] Sébastien Bubeck. Convex optimization: Algorithmss and complexity. Found. Trends Much. Learn., 8(3-4): 231-357, nov 2015. ISSN 1935-8237. doi: 10. 10/15//02000000000 /tL.https://doioor//// 2200000050
[9] Karan Chadha, Gary Cheng, and John Duchi. Accelerated, optimal and parallel: Some results model- based stochastic optimization. In International Conference Machine Learning, pages 1811-2827. PMLR, 2022.
[10] Chih-Chung Chang and Chih-Jen Lin. Libsvm: A library for support vector machines. ACM Trans. Intell. Syst. Technol. 2(3), may 2011. ISSN 2157-6904. doi: 10. 19.114/966118891961111 URL https //doi.org/// 10/ 1145/ 00114/19961 19w1189.911. 1961199
[11] Gary Cheng and John Duchi. adastar: A method for adapting interpolation. In OPT 2022: Optimization for Machine Learning (NeurIPS 2022 Workshop), 2022. htt.latppr//ppeeeeeeeeeaaa//rrrr
dMbczvuk6JJj
[12] Ashok Cutkosky and Kwabena Boahen. Online convex optimization with unconstrained domains and losses. In Proceedings of the 30th International Conference on Neural Information Processing Systems. NIPS' 16, page 748-756, Red Hook, NY, USA, 2016. Curran Associates Inc. ISBN 978 0111535811811
[13] Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. In Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, vol- ume 27. Curran Associates, Inc., 2014. URL httt:::://pooeeee wewtiiinnnnnuuuruie ips pesorripsccppppprrr files/ vaper/2014/fii/
Paper. .dff
[14] Benjamin Dubois-Taing Sharan Vaswani, Reza Babanezhad, Mark Schmidt, and Simon Lacoste- Julien. SVRG meets adagrad: painless variance reduction. Mach. Learn., 111((2)4439 44009 2022. doi: 10. (0077//10994-22--62226 062655xx. URL
06265-x
[15] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. J. Mach. Learn. Res., (2(mll):222122155) jul 2011. ISSN 1532-4435.
[16] Leonardo Galli, Holger Rauhut, and Mark Schmidt. Don't be monotone: Relaxing stochastic line search in over-parameterized models, 2023.
[17] Robert M. Gower, Aaron Defazio, and Michael Rabbat. Stochastic polyak stepsize with a moving target. CoRR, abs/2106. 11851, 2021. URL htttp:://axxxv.rrge... abs/ 1105.11851
[18] Robert M Gower, Mathieu Blondel, Nidham Gazagnadou, and Fabian Pedregosa. Cutting some slack for sgd with adaptive polyak stepsizes. arXiv preprint arXiv:2202.12326 2022.

---

[19] Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The elements of statistical learning: data mining. inference and prediction. Springer. edition, 2009. URL http:h/t://ett http:://wwwssaaasataaforroo adu/-tibs.
ElemStatLearn/
[20] Elad Hazan and Sham Kakade, Revisiting the polyak step size, 2019, URL httLhttts///axxi.orrg//
00310
[21] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 770-778, 2016. doi: 10. 211.0//VV....06..99
[22] Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive vari- ance reduction. In C.J. Burges. L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Wein- berger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Asso- ciates, Inc., 2013. URL
http:///roceedinggneerrrrs.....p httpp//ps..c.aapp...eeee//p//ppp ftllss/ppper2013///t/a. accaa229bcceeeddceee255eeeeeee Paper pdf
[23]
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D' D'Oliveira, Hubert Eichner, Salim EI Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He. Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi. Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konecný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Hang Qi, Daniel Ramage, Ramesh Raskar, Mariana Raykova, Dawn Song. Weikang Song, Sehastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramer, Praneeth Vepakomma, Jianyu Wang, Li Xiong. Zheng Xu, Qiang Yang. Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. Found. Trends Mach. Learn.. 14 (1-2):1-210, jun 2021. ISSN 1935-8237. doi: 10.1561/2200000883 URL https:: org/ 10. 1661/ 2200000083
[24] Sai Praneeth Karimireddy, Satyen Kale, Mchryar Mohri, Sashank Reddi, Scbastian Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for federated Icarning. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 5132-5143. PMLR, 13-18 2020. URL
[25] Ali Kavis, Stratis Skoulakis. Kimon Antonakopoulos. Leello Tadesse Dadi, and Volkan Cevher. Adaptive stochastic variance reduction for non-convex finite-sum minimization. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 23524-23538 Curran Asso- sailes/paper/222/1
ciates, Inc., 2022. URL https: httpp//reeeiinnnneeirrr... FFE655cdee3311444336666666666333
[26] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL httptt/t///axi// org/ /bs// 1412.6988
[27] Dmitry Kovalev, Samuel Horváth, and Peter Richtárik. Don't jump through hoops and remove those loops:
Svrg and katyusha are better without the outer loop. In Aryeh Kontorovich and Gergely Neu, editors, Proceedings of the 31 International Conference Algorithmic Learning Theory, volume 117 of Proceedings of Machine Learning Research, pages 451-467. PMLR, 08 Feb-11 Feb 2020. URL httpss//pproceedingss mlr /rs../eree////1///aa///////
[28] Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar- 10 (canadian institute for advanced research).
http::::/ww....trroot./o wwwp//////////arr..a.aaaa html
[29] Alex Krizhovsky, Vinod Nair, and Geoffrey Hinton. C0f (canadian institute for advanced research). URL http::://www.cc.oorooo wetpeeedi//dd//ee//eee
kriiz cim
[30] Frederik Kunstner, Victor S. Portella, Mark Schmidt, and Nick Harvey. Searching for optimal per-coordinate step-sizes with multidimensional backtracking, 2023.
[31] Shuang Li, William J Swartworth, Martin Takáč, Deanna Needell, and Robert M Gower. Sp2: A second order stochastic polyak method. arXiv preprint 2rXiv:2207.08177 2022.
12

---

[32] Tian Li. Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. In Inderjit S. Dhillon, Dimitris S. Papailiopoulos, and Vivienne Sze, editors, Proceedings of Machine Learning and Systems 2020, MLSys 2020, Austin, TX, USA, March 2-4, 2020. misys.org. 2020. URL htttttt://proceedanggg http://ceeeinngsmmssl.........ee oxg/ http//oo///////// pdf
[33] Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtarik. Page: A simple and optimal probabilistic gradient estimator for nonconvex optimization. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 6286 6295, PMLR, 18-24 Jul 2021. URL wtt.ttts:://////tttttttt html
wtt.:iiiinn.mm....ssss/eeeeeeeee prw.s//sssss/. wwwps//vss/pp/pp /
m.r.
[34] Nicolas Loizou, Sharan Vaswani, Issam Hadj Laradji. and Simon Lacoste- Stochastic polyak step- size for SGD: an adaptive learning rate for fast convergence. In Arindam Banerjee and Kenji Fukumizu, editors, The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event, volume 130 of Proceedings of Machine Learning Research, pages 1306-1314, PMLR, 2021. URL http:tt//pprocoeeingg.aa htt..rrrees///11oooooool wt..ooatnnnaaaamlll
[35] Ily Loshchilov and Frank Hutter. SGDR: Stochastic gradient descent with warm restarts. In Interna- tional Conference on Learning Representations, 2017. URL bettpee//openreviee.eet/ttte
Skq89Scxx
[36] Julien Mairal. Optimization with first-order surrogate functions. In International Conference on Machine Learning, pages 783-791. PMLR, 2013.
[37] Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtárík. Proxskip: Yes! local gradient steps provably lead communication acceleration! finally! In International Conference on Machine Learning, pages 15750-15766 PMLR, 2022.
[38] Angelia Nedić and Dimitri Bertsekas. Convergence Rate of Incremental Subgrudient Algorithms, pages 223- 264. Springer US, Boston, MA. 2001. ISBN 15BN9978-1445776699444 doi: 10.1007/978--4455-66677 |11 URL http://do..rrr//000000////1//--1
[39] Yurii Nesterov. Introductory Lectures Convex Optimization: A Basic Course. Springer Publishing Company, Incorporated, edition, 2014. ISBN 1461346916.
[40] Lam M. Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáë. SARAH: A novel method for ma- chine learning problems using stochastic recursive gradient. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference Machine Learning, volume 70 of Pro- ceedings of Machine Learning Research. pages 2613-2621. PMLR, 06-11 Aug 2017. URL litpss //proceedings mlr wttp://www.........eeeeee wwwess/v///guuee /tap/////////uuuy/.///aaaa
[41] Jorge Nocedal and Stephen Wright. Numerical Optimization. Springer, New York, NY, USA, 2e edition, 2006.
[42] Adam M Oberman and Mariana Prazeres. Stochastic gradient descent with polyak's learning rate. arXiv preprint 1903::900.0060 2019.
[43] Francesco Orabona and Dávid Pál. Scale-free algorithms for online linear optimization. In Kamalika Chaudhuri, CLAUDIO GENTILE, and Sandra Zilles, editors, Algorithmic Learning Theory, pages 287-301, Cham, 2015. Springer International Publishing. ISBN 11883-311-244866
[44] Antonio Orvieto, Simon Lacoste-Julien, and Nicolas Loizou. Dynamics of sgd with stochas- tic polyak stepsizes: Truly adaptive variants and convergence
exact solution. In S. Koyejo, Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 26943-26954. Curran Asso- ciates, Inc., 2022. URL http::////ccceeeeeeeeeeee wwwpurripscccppppeee.eepppeppe PaweeaaaaaaaaPPPa-aaaaaaaeee Pwweerraneeeeeeeeeeppppama httpp/ppeer.ele//aappeeeeeeeeeee
[45] B. T. Polyak. Introduction to optimization. Translations series in mathematics and engineering. Optimiza- tion Software, Publications Division, New York, 1987. ISBN 091 1575146; 15751499
[46] Herbert Robbins and Sutton Monro. A Stochastic Approximation Method. The Annals of Mathematical Statistics, 22(3):400~ 407, 1951. doi: 10. N0.22144aoms/11177295566 URL aoms/ .oms/1177729586
10.11///
[47] Michal Rolinek and Georg Martius. L4: Practical loss-based stepsize adaptation for deep learning. In Advances in Neural Information Processing Systems 31 (NeurIPS 2018), pages 6434 6444. Curran Associates, Inc., 2018. URL attpp://papers www.errssiisscccc.coo. www.:iiioaaaptttiionnno for www.oeppeerrnnn.... wwtps/ccpppppeecccpee 14- practicalaaaa-... loss-baeddd
13

---

[48] Mark Schmidt and Nicolas Le Roux, Fast convergence of stochastic gradient descent under strong growth condition. arXiv preprint arXiv: S00iv:v300.66700000 2013.
[49] Mark Schmidt, Nicolas Le Roux, and Francis Bach, Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162:83-112, 2017
[50] Ohad Shamir, Nati Srebro, and Tong Zhang. Communication--ficienn distributed optimization using an approximate newton-type method. In International conference on machine learning, pages 1000-1008. PMLR, 2014.
[51] Matthew Streeter and H. Brendan McMahan. Less regret via online conditioning. CoRR, abs/1002.4866 2010. URL
[52] Sharan Vaswani, Aaron Mishkin, Issam H. Laradji, Mark Schmidt, Gauthier Gidel, and Simon Lacoste- Julien. Painless stochastic gradient: Interpolation, line-search, and convergence rates. Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer. Florence d' A'Accéé-uuc, Emily B. Fox, and Roman Garnett, editors. Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC. Camada, pages 3727-3740, 2019. URL httppp//ppocellg...eeeeeaapppppp
[53] Sharan Vaswani, Issam Laradji, Frederik Kunstner, Si Meng, Mark Schmidt, Simon Lacoste-Julien Adaptive gradient methods converge faster with over-parameterization (but you should do a line-search). arXiv preprint (xXiv:200600683) 2020.
[54] Xiaoyu Wang, Mikacl Johansson, and Tong Zhang. Generalized polyak step size for first order optimization with momentum. arXiv preprint arXiv:2305. 12939, 2023.
[55] Rachel Ward, Xiaoxia Wu, and Leon Bottou. AdaGrad stepsizes: Sharp convergence over nonconvex landscapes. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th Interna- tional Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 6677-6686. PMLR, 09-15 Jun 2019. URL http:///////oo mwr. wttppp/e/e/s///s////// html
[56] Yuege Xie, Xiaoxia Wu, and Rachel Ward. Linear convergence of adaptive stochastic gradient descent. In Silvia Chiappa and Roherto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 1475-1485 PMLR, 26-28 Aug 2020. URL htstt:p:/pooocednnssl..prreseees xt00
14

---

Appendix
A Technical Preliminaries
A.1 Basic Definitions
We use the following definitions throughout the paper.
Definition 1 (convexity). differentiahle function f R + is convex if x, E R
f(y) 2 f(x) (VI(x). -x)
(A.1)
Definition 2 (strong convexity), A differentiable function f R² + R is p-strongly corvex if E R fly) 2 f(x) - (Vf(x), x) Definition 3 (Z-smooth), Let function f TR. + be differentiable. f is smooth if there exists I. >> 0 such that V xx R
2 #|Ix- -1x- yl1
(A.2)
[Vx()) vf(())l - L||x y
(A.3)
A.2 Useful Lemmas
We frequently use the following helpful lemmas for the proof.
Lemma (Nesterov
39 Lemma 1.2.3). Definition 3 implies that there exists a quadratic upper bound on f:
fly) f(x) (V)()), - x) L x11 Vx.y E
(A.4)
Lemma 10 (Nesterov
39 Theorem 2.1.5). If convex functionn f satisfies A.4
then it holds that:
f(y 2 fx) + (V/(x). x)1+ 2L
|V/6)
[xx)]| Vx.y E RR.
(A.5)
Lemma 11 (Ward et al.
55 For any non-negative sequence da ...y Or, the following holds:
a:
ax
<
Σ
at
(A.6)
2ii
do 2 1, then the following holds:
T a.) +1.
log
(A.7)
1= dx
t=
Proof. To show equation A.6), we proceed with the proof by induction. For I = 0, (A.6) holds trivially since
Vou S v < 2 Assume equation A.6 holds for T 1. For RHS, we have:
T-1
or
aT
ae
1=0
E
Er ai
t=0
2 as
2
ar +
(A.8)
VET az
<
at
15

---

where the last inequality is due to the fact that 2 - +
S 2 for x 2 2 0. For LHS, we have:
Σ a0
ar
Liz
V VIi=
Di=
T
Σ t=0
at
aT
+
4T
(A.9)
T
where the last incquality due to the fact that v2 1 y +
V for any x 2 y 2
v
We next show equation
A.7 by induction. For t 0, equation A.7
trivially holds since log(ao) + 1.
Assume (A.7 holds for we have:
T
T-1
log
Qr ai)
1 1+
t=
2i=
di
E 04
(A.10)
log
ac) +1.
1=
where the last inequality is due to the fact that log( - 7) + S log(z) for any x 2 2 0 since ez
14
Lemma 12 TDubois-Taine et al. 14 Lemma 5)). xf S a(x + for 2 and b then it holds that:
S a Vab.
(A.11)
The following Lemma is an extension of Lemma 5 in 44 Lemma 13. Let 2441 (1 an)) + m/b and where 0, b >> 0 and 0,1441 $ mp 1L 0.
holds that:
21 S max 20, nobb, VE 2220 0.
(A.12)
Proof. Since is non-increasing, - arp I 0 is non decreasing. For any > 0 such that 1 am & 0, we have ze+1 S. beb < Job. If 1 ozk < 0 for all f 0, then the proof is done. Otherwise, let us assume there exists first index such that anj 0 and we have 2j S max(20, nob] 2o. We proceed with the proof starting with the index j by induction. For = j. the lemma trivially holds. Let us assume S max _ 3o for & >> j. If 2 Zu. then by induction, we have:
2++1 S 51 - an)) + vpb b
(A.13)
a
instead _ < 20. then by induction, we have:
F++1 S (1 arp 2 + mhb 20 - (aão - b)) S 20
(A.14)
Combining the ahove cases concludes the proof.
following lemma is commonly used in the works on Polyak stepsize (34 20
Lemma 14. Suppose a function is L-smooth and p-strongly convex, then the following holds:
f(x) -f" f"
(A.15)
2L |V((2)) 2p
The following lemma provides upper and lower bounds for the stepsize of AdaSPS.
Lemma 15. Suppose each f. is L-smooth, then the stepsize of AdaSPS AdaSPS)
satisfies:
1
Sv. (xx) E7
2m <
(A.16)
20,h v E R2 (xx) - e2 c (x))
Ei (x,( (x.))
-
16

---

Prouf. The upper bound follows from the definition of the stepsize (AdaSPS)
To prove the lower bound, we Si, (x.))11,
note that the stepsize (AdaSPS) composed two parts where the first component epl VS,, (x.]l12 2 2c,
for
all 0 I S due to A.15), and the second component always decreasing. Finally, recall that 1/-1 +00 and thus the proof is completed.
following lemma provides upper and lower bounds for the stepsize of AdaSL.S. We refer Appendix D for details of the line-search procedure.
Lemma 16. Suppose each L-smooth, then the stepsice of AdaSLS AdaSLS
satisfies:
P Tmax
1
min
S
(A.17)
oVEi_ 74 fi, (x,))l
a E' Va I,,
Proof. The upper bound is due to the definition the stepsize the smoothness definition, the following holds for all yx:
AdaSLS
We next prove the lower bound. From
A4
L (
[x 74 V (x.))
Sr (xx)
(A.18)
For any 0 7/- S 21-pl we have:
(x V., (xx) S px (..))
(A.19)
which satisfies the line-search condition From the procedure of Backtracking line-search (Alg. 4. if Tmax I 7 then "I Tmmax accepted. Otherwise, since we require the decreasing factor / to be no smaller than in Algorithm 4 we must have " 2 2(1-1), Therefore, 7/t is always lower bounded by minf "", Ymmx }. The second component of AdaSLS always decreasing, recall that 7-1 +00. The proof is thus completed.
B Proofs of main results
B.1 Proof of Theorem 1
Proof. We follow common proof routine for the general convex optimization rule of PSGD we have:
Using the update
|x++ x12 | (x,)()))) [xx
Xx Vx., 11
(B.1)
- x1 2m (V.. (x.,, x") + + (x,
Dividing by 2n, and rearranging gives:
(V J (xx).x. x")
|x
1²
|
1²
Ttt
f. (x:1)
27
217c
2
(B.2)
|x: - x"
|x
|
11
[Xx41 - 11
V (xx))1².
21/r
21/++1
21/++1
21p
2
Summing from t= t T 1, get:
(V (x:) XI-
Xx
x²1
|x+1 122
||x011 x"11
||x+1|
- 1²1
+
| (xx))
27:
27/+1
27c+1
217c
LmD
[xx
x" x"11
|XT x"
||xT
x"
1xr
x" 111
1
D +
Σ
11t
v
fa
(x:)1l²
2no
2n7r
20pr
2tpr-1
2m1+1
277
2
Xxn x"1 11
xxT
x"1
XXT
x11
+
D
T-1
Σ
IV (x,))1
2170
277r
20pr
2m
2
1=0
17

---

|
x=1
D
T-1
Σ 1=0
f
(B.3)
2rjo
-1
2
where in the second inequality, we use the decreasing property of the stepsize which guarantees 2xp
we use fact that ||x; - x"11² v
D because of projection step (5). For clarity, we next separate
the proof for AdaSPS and AdaSLS.
AdaSPS: We upper bound the last two terms by using Lemma 15 and we obtain:
Mtt fi,
fú, E
T
fc, (Xa) - -
(B.4)
1=0
2cp
Ei_o fú, (x+) - P
D
A
Cy
LD
T-1
Σ [r,(x,) Cr
(B.5)
2tfr-1
Using
D2
and plugging B.4] and B.S back to
B.3 gives:
2na
2vr-1
Σ (V), x - x*) S 12
fú, (x,) fi
(B.6)
Taking the expectation on both sides, we have:
xx -xx) (2c
)
1
T-1
Σ fú (x.) - ci,]
(B.7)
T-1
(2c LD²
)
Σ
fr, (xx) + (xx))x()) -f%
Cp
==0
Using the convexity assumption and applying Jensen's inequality the square function, we get:
T-1
Σ E[f(x:) - 1'l s (2cpLD2 "
Σ Eif(x.) - f*] oo errj.
(B.8)
Cp
where erri.0 = I,, fi Let = 22, + + Taking the square gives:
T-1
Σ Elf(xi) fT1)² 7d
Σ [-0
- f11 + terj,)))
(B.9)
1-0
We next apply Lemma
12 with Ei- Ex,( )- f(x')((x))))))))))))))) a= and T(o?. ter)
[[((x)) l و 72 + + of + emr VT
(B.10)
We conclude by dividing both sides by T' and using Jensen's inequality:
7 7 + err? ?
(1f(xr)-11) - E. [[(x))) S4)
(B.11)
T
T VT
where K7 = -TT x..
AdaSLS: The proof almost same as AdaSPS, omit procedures with the same proof reasons for simplicity. We first use Lemma To obtain:
Σ W
(x:
V (x:)
Yo
V (x.)),
(B.12)
201
E
Toll V (x.)1l2
2
2s=0 Vol
V., (x.) D2
max
D
Tama
Σ Yall (x)))l (x
(B.13)
27T
2 min
1- Tinxx
18

---

Inequality B.3 can then be further bounded by:
(x),) -xxxx s (max I.
Ymaxx JaDe 2
7-1
Σ
7al
V (x.)
p'
(B.14)
T-1
$ max
L
JaiD p +
1
Σ (x,) ft.
p)vP
Timax
cv/p)
where we used line-search condition 4 and the fact that fú, (x: - (x,,,xx()x S.
Let r = max (1-P) Tmua v aD + ava
I We arrive at:
-
T0
(B.15)
VT
where Xy = + Xt.
B.2 Full statement and proof for Lemma 4
Lemma 17 (Bounded iterates). Let each fo be p--ttrongly convex and I-smoooh. For any E N, the iterates of SGD with AdaSPS or AdaSLS satisfy:
||x - x x²11 S Dmax == max { ||x00 - x" 20 + (20 + b)yo
(B.16)
where mmax max;, (si (x") - figh b 1/(40) Sio
( [1o(x))) - (%0) for AdaSPS and a
maxi, (Ji(x'') b== 1/ (Ac2 V IV //)o\ for AdaSLS.
Proof. By strong convexity of fi,, the iterates generated by SGD satisfy: x" x"11
[
[x 11 2Tp. (V (x:), Xx x²) ví [V
||x= x 11a (m, (1,,, (xt) - fx((x)))) + 2
|x - + (B.17)
(1 )=/1)|x; - x" 2m. (x+) fi. (xx + TZ (x,))
We next separate the proof's for clarity.
AdaSPS: Plugging in the upper bound of n) in Lemma 13 we obtain:
Xo+1
(x,) -hi
(1 Tx)+)xx - x" x1 (x.) (xx(x)) +
cov 111 fir (x((x))
fú, (xx) Ei.
mx))lx x²1 27 (T; -(,)) (Tn(Ji, (ii)) + +
Cp El fr. (x:)) - E7
(x.) - -
< (1 - -mm)lli x²1 + 2m. - 2n. (fu (oxxe)-C - -(a) +m
co COVE Σl fú, (xx)) - -7,
(B.18)
where o := maxi, {fr (x*) }.
We now split the proof into cases. Firstly, if cp
Dizo fú, (xi) Ei 1.2 then it follows that:
fú, (x.) C, 2cp
and
Σ Sr (xx) - - 2 Sro (xo) C% ==0
(B.19)
Plugging in the above bounds, we have:
| - x" x11 < (1 mx]][xx - x21 + m. (20 +
1
(B.20)
1r2 fig (xx) 1%
19

---

We conclude by applying Lemma 13 with
||x, xx=xx = μr. 6 (20 +
Secondly,
de 4 / (20) 20
if instead coy V Ei=o Jin (xx.
2. then we have:
(x,( - Eig S 0
2Tp (i.)
(B.21)
cv Σ. Si, (xx) Ei
and consequently we can apply Lemma with 2, = ||x: x 11, = μr, b 20 -
AdaSLS: Similarly, by plugging the upper bound 7/. in Lemma I6 we obtain:
Xx+1 - x"I
74 VV (x,) )11
nelllxx x21 (7,(f(, fx,(x)) + n
a1 Ei=o 7oll Vi, (x=)]12
fr. (x.1 fi.
<(1 - -[n))xl - x11 (xx((xx((''))))))) fi:) - (n,(((x -(t) +
aPV
Ei YollIV fú, (x,))l²
J (xi)
si+
S(1 - - x21 2nx 2n (xx(
+mp
apV E 7/ Vi, (xx)1l²
20
(B.22)
where mmax max, (f,(xx)) - fir]. We can then compare cppy E1 7/41 V (x.)11² with 1 and apply
Lemma correspoondd
B.3
Proof's for Theorem 2 and 6
Proef. For clarity, we separate the proofs for AdaSPS and AdaSLS.
AdaSPS: Plugging in the upper bound of in Lemma L5 we have:
Sx,( - l
[|x+1 - 2x l|x: x 11= 2m (
x + n
(B.23)
Σ fi,(Xe) -
cpy
Since v fro (Xo) - f 2 1. B223) can be reduced to:
|x1411 x"1 1 ||x: x"11
2Tp. (V S4, (x.), x xx) (T] -P').
(B.24)
By convexity of fic, we get:
||x11
X x x111 1/: fi (x,))
(B.25)
Note that (X., Xx
x") 2 0 and n is non- con-increasing, we thus get:
[x++1
1| -
x")
(B.26)
We first show that 1 is always lower bounded. From equation H.25 and using convexity of f., we get:
Vy (xx f²) < ||xe x 11 Xx+1 x
(B.27)
Summing from = to = 1, we get:
Σ (x., - -8¹) S 1|x0 - x=1
(B.28)
Using the lower bound of vı. get:
T-1 (x,xx)
Sú (xx) s*
AWT
2
((.. -f")
(B.29)
I. T.
2cp T t=
Di Jú (x,) - f
1=
This reveals that:
Mr-
2
2 (2c,L||Xo - x=1)
(B.30)
20pL v DT= Sú, (Xx) -
20

---

Plugging in the lower bound of y--11 B.26). we obtain:
||x+11 x"11" <
(2cp Xu x2 (x
(B.31)
Plugging in Cp 5 (x0) we get
fig (xo) - 1 (2cg x xx 1|) (X),,
x=1 S 1|xe x²1
(B.32)
case 1: f convex.
For any 2 1. we take expectation conditional on do both sides and get:
fio (xx) f
E X xn1 S B|| X
[1o -x111
(2egaal L||x0 x* 11) (L. 1x0==x")ll [6)6
(B.33)
A.1
fio (xo)
[[[[x x 111
(2cgale L|| xo x 1112 E(f(x)) f=)
Summing up from t = to t = TI' and dividing by T' we obtain:
1
No x" 11 L E X x
[xf(x:) - [ = (
(B.34)
(xo) - f
Note that [x[[
x"1 P|oo| ||x1 || > 11x0
x11 duc to (B.31
We thus get:
1 T
(AI(e |x0 x11
L
10x00= x
Σ -
(B.35)
T
fx0( - f
T
Taking expectation w.r.t is on both sides, we arrive at:
T HΣ -(f(()) و X1 x"1
Xo x=112
with 42 Faol
(B.36)
T
Fio (xo) f
case is strongly-convex
For any 2 1, we take expectation conditional on to both sides of B.32 and get:
fro (Xo) f"
E [
x [ < E1| x.
-x 1x0 ([(V xxx)
(2egrah L Xo x Sio (xo) 1 (2 I.| No
B[ |x, x 11%
1))a B(f(xx) f" - lixe x"1 111%)o]
(B.37)
Note that f(x.) 1r
$ |x4
x1 due to strong convexity, we obtain:
E [xe1 x"1| 1100 I (1 (2cgalo L|| Nu
(Srp (xo) f*)
E Ellix:
x" [7)
(B.38)
x 11)2
For any T 2 1, unrolling gives:
El| E|][x++1 x"1 x111 1 (1 (xx) f-
E[l[x] x" [1
(Zegaale L 11x0 x* x=1
(B.39)
< (2o L||x0 - x1) ||xu -xx-xx" x1
(fro (xo) 1
T.
The claim of Thhorem@ffolloww by taking expectation w.r.t to both sides.
AdaSLS: We only highlight the difference from AdaSPS. Plugging in the upper bound of m from Lemma 16 and using the line-search condition, we get:
7/s fe, (xx)
X
X2
2Th (.. (x:). X m
a/ E.= / /i, (x.))l2
(B.40)
fl (xx) - f
< ||x:
x2112
2m ( (xi), xx') m
app Dt 7all 1/.l/ (x.))l
21

---

Since apV E == 7-
fe, (xx) 1| 2 we obtain same equation as (B266). find lower bound of 1pr-1.
we rearrange (B25 as:
T) (Js. (xx) (r) - X x
||
x²11²,
(B.41)
the left-hand-side of which can be lower bounded by:
pr V VLe (xx)]1
(x()(( f) 2 (.
min mmax
(B.42)
aV
E 7/ v..lV/.. (x,,(x))]
Summing over 0 to gives:
min
Pmax
P
V.lVV (x+)
A. min 1 P
Tmax
Y: V. (x
S [|x00=x
1x12-x"112-
t=
E 7/1 V (x.)
(B.43)
This implics that:
min Vmax }
6:43
pmin 1-p Tmaxx L
(B.44)
Xg x 112
2== 74
V.A, (x.)
After plugging the above into B.26 the remaining proof follows from the same routine shown for AdaSPS.
Proofs for Loopless Variance-Reduction
B.4 Statement and Proof of Lemma 18
The following Lemma provides us with the guarantee that W., x", E,, (x., F..] + 0. which implies diminishing variance. Lemma 18. Assume each fi is convex and L-smooth, for any t 2 0, the iterates generated by Algorithm satisfy:
E., (Fi, Fill S f(x)) f + 1
13,, [[.V (x,(
(B.45)
2ur
Proof. By definition of (x),, we have:
Fs, (x1) - F;, (xi) Fi, (x") (xx) FA
(B.46)
fx.) (x") + (x:-x') x") (VS(w) -V..)))).((...)
Mef ||x: x'11 Fx((x) F%.
By pr-strong convexity of Fi, (x). obtain:
(x))') Ft
[V
2μ1F
(B.47)
[x'xx') - Vfi) + V)(ws) + ur xx)
2uF
Plugging
B.47 into (.46), taking expectation w.r. the randomness é, on both sides gives:
E,, [T,, (xx) FG.]
fx(x)) f(x') PF
||x: x" x
+1i, [x')((')
V.J, + (/p('- -x:)l
2
2FF
=s(x)) - 1(x*) - 148
||x: - xx111 x11 +
ME
| x12
1
E. [IV (x') (ws( [[(w)))
2
2
2FF
1 E.,((V f.. (x*) V.J, + Vf(w)). -xx))
pF
1
=f(x)) - f(x') +
E. (x") (..(ww)) V
2/14
s sx(x)) f(x') + 244
E., V (x') -al/x''-VVVVll (wo)l
(B.48)
L
22

---

B.5 Proof of Theorem 7
Proof. Recall the proof technique that gives equation 6B6 and (.14 in Theorem routine, we arrive at:
Following the same
Σ (x.),, x - -x) ST Rd (xx) - Ft
(B.49)
where T = (2cp(T. + (r) + ) for AdaSVRPS and 7 max
L+nE [1 (エ-P)マカ "max j ja + 4vp for
AdaSVRLS. The difference is due to the fact that (x) is (L + 14 -mmoohh. Taking the expectation, using the fact that F., (x.)) f.. + vf(w.)- f., (w:)] (xx) and applying Lemma with:
18 end up
T
B.48
[xx(
B[((x)) [4]
(B.50)
2p1
Taking the square gives:
EE(((x) -
S=² Σ [xx( -'+ 2/
Vi. -v (xxx()))) (B.51)
Define the Lyapunov function: Zi-1 2(1-a) Pei 12f
| lez4a (we41) V/.ti1 (x*) It follows that:
1
E [[++1]
| firs (W++1) - V Vivti [x*)
2(1 a) P+tIUF
7²
fit4 (x.) - Vheaa (x" x²* + 1 pe+1 7²
BBI f., (W.) V (x')1l
2(1 a)μ
2(1 - a) Pe+1/FF
A3
72
p(+1) E[Z.]
B[II(Jic41 (xx) fiit1 (x*) (VSic.i (x"), -x11]]
2(1
a)uF
pc+1
L
22 (E) -P) (1 - 1--P+1))t E[ZZ)
(B.52)
(1
a)u
p141
Adding E B.] 1[14+1] to both sides of B.51 and substituting the above upper bound, we get:
Σ [(((x)) - 51)
+
E
Z.+1l (11
L
B[f(xx) (xxx)))f f1
(1 (1-a)pr
(B.53)
T-1 (1 a)p +
p(41)Rg E[Zz]
P++1
t=0
Rearranging and dropping [[[z]] 2 0 gives:
Σ Bl((x)) B1((x))- r1)
< (1 + (1 a)pF
L
[xf( f²1
T-1
(1 a)pp +
(1 P(t1)p:
1) B[zi]
P++1
(1 - p1)po E[Zu]
+ ((1 a)po +
P1
(B.54)
By choice of pt, have:
a)pe (1 pLp I)p
P++1
Pt+1
Pt.
apt
at +
+ a
(at +
a
2(at + 1)
0. (B.55)
Therefore, it holds that:
Σ
E((()) ri) $ (1+
L
Elf(xi) - fr] E|Zo)
(B.56)
(1 - a)ur
Further, by L-smoothness and convexity of f. we have
1
L
E E
B (x) (xx(("))1
(f(xo) -f))
(B.57)
2(1 a) POlF
(1 a)fF
23

---

Hence. we obtain:
E(((())- - -11) (1+ (1 a)
2L
[x((xi) (xi) - 8
(B.58)
follows that:
T-1 Σ Elf(x)) fl ] (1+
2T.
(1 a-ur )7
(B.59)
Dividing both sides by and applying Jensen's incquality concludes the proof.
B.6 Proof of Corollary
Proof. Algorithmm
I calls the stochastic gradient oracle in expectation ( p.n) times at iteration t. Therefore, the total number gradient evaluations upper bounded by O pen + T). By our choice of pt, holds that E Pt 1 Ei= = s a
5+2 a (log(T) + 1-1) 1 log(T). Due the sublinear convergence rate of Algorithm we conclude that the total number of stochastic gradient calls is O(log(1/E)) + 1/e).
C Pseudo-codes for AdaSPS and AdaSLS
this section, we provide formal pseudo codes for AdaSPS AdaSPS and AdaSLS (AdaSI.S)
To implement AdaSPS, lower bound optimal function value each minibatch function is required. machine learning problems where the individual loss functions are non-negative, we can use zero as an input. Apart from that, we need to provide constant Cp to adjust the magnitude of the stepsize. Theoretically suggested Op for robust convergence satisfics op
cpv fig (xo) Ci 2 1/4 Therefore, common choice is to set
Cp
Viio (NO) C
Algorithm 2 AdaSPS
Require: Xy R., T N+ co
1: set 17-11111100 to0
2: set 10-10
3: for / to - do
4: uniformly sample C [n]
5: provide a lower bound f - fi
fu (xx))
6: set = min
Cpll (x.)
EE: (x.) 110
7:
X,+1 = x (x,
ne V Tú (x,))
return Xy = + Σt X2
To implement AdaSLS AAdSLSS)
line-search sub-solver and an input constant Ç; > 0 are required. Similar according to the theory.
to (AdaSPS), we can set ej e [x)]]
Algorithm 3 AdaSLS
Require: Xn R2d, T E N+ 00
1: set 1/ 400
2: set 5 = 10-10
3: for / = to - do
4: uniformly sample i, C [n]
5: obtain 2/ via backtracking line-search (4
6: set = min
Ei_ 7a 7.lV (xx. 1/-
7
(x.)11++="
7: Xx+1 = (1x(x;
T/t fú, (xx))
return X7 = + Σ X:
24

---

D Line-search procedure
In this section, we introduce the classical Armijo line-search method [ 41). Given function (x), the Armijo linc-search returns stepsize "/e that satisfies the following condition:
(x > f4, (x:) S f. (xi) - px (x)))l
(D.1)
where p (0, 1) is an input hyper- hhper--pramen parameter. If fi. (x) is a smooth function, then backtracking line-search is practical implementation way to ensure that D.I is satisfied.
Algorithm 4 Backtracking senerh
Require: B E 1/ 1),1,, p (0, 7max > 0 (We fix 8 0.8 and
0.5 for AdaSLS)
1: y = Vmax
2: while fi, (Xt -0-- (x.(()))) fa, P (x,) || do
3:
=== 88
return ?tt 7
To implement Algorithm one needs to provide the decreasing factor 9. the maximum stepsize "Ymax. and the condition parameter Starting from "Ymax. Algorithm 4 decreases the stepsize iteratively by constant factor B until the condition [.I] is satisfied. Note that checking the condition requires additional minibatch function value evaluations. Fortunately, note that the output y camnot he smaller than --2 (Lemma 16), and thus
13 . In practice, Vaswani al. [52 suggests dynamic initialization Tmaa to reduce the algorithm's running time, that is, setting 7iaa,, -t-11 00/n where common choice for 0 is 2. This strategy initializes "/max by slightly larger number than the last output and thus is usually all our experiments, we use the same "ymax at each iteration for AdaSL, to show its theoretical properties.
the number of function value evaluations required is at most O [maxx(oog (1max/(11p)) /10x////////000000/
efficient than keeping Timax constant always using Timax: 7h-1-
Goldstein search is another search method that checks and an additional curvature condition We do not study this method in this work and we refer to [52) for more details.
E
Counter examples of SPS and its variants for SVRG
We provide two simple counterexamples where SVRG with the SPS stepsize and intuitive variants fail to converge. For simplicity, consider the update rule X++1 =
fx)) i.c. we = x, for all 2 0. Consider the function f(x) = f2(x) where [x = ai (x - 1)² and f2(x) = a2 (x + 1)2 with Ø1, ag >> 0.
2
Example 19. Individual curvature is not representative. Consider the standard stochastic Polyak stepsize: and a2 1. Note that + Bog + +oo as a2 - O, which leads to divergence. The reason behind this that individual curvature does not match the global carvature.
fx(x)-111 where is randomly chosen from (1,2). We now let a1 (x))
Yh
V fx) a1 + 02 (1,2) while Ea[ys] -
Example 20. Mismatching quantity. Consider a variant of stochastic Polyak stepsize:
+1 [V)))) VJ((w) ((W)) where is randomly chosen from (1,2}. Let a = a2 = 1. We note
1((x))-11
* O and thus no stationary point exists. Similar reasoning can exclude number of other variants such as: = f((x))) folwe)t/tww)-- - [(w:) Indeed, the numerator is not the proper properffunction value difference of a valid function with the gradient defined in the denominator.
E. [xxx)]
Zxz
[(())))))) Jalwe)+ +
F Experimental details and additional experiment results
this section, we provide detailed setup of experiments presented in the main paper.
practice, can use lower bound of F;; for running AdaSVRPS since convergence still guaranteed thanks to the property of AdaSPS. By default, use f; minx(x" (V (V fw..) V., (w.)) + eg ||x x.ll²) for all the experiments, where Et, a lower bound for fi.
F1 Synthetic experiment
We consider the minimization of quadratic of the form: f(x) = 1 Σ fe(x) where fi(x) = [
b.)TA.(x (x b.). b. E gd and A, E dgd is a diagonal matrix. We use n = 50. d = 1000. We control the interpolation by either setting all {6:) to be identical different. Each component of {b: is generated according
25

---

to (0, 10"). We control the complexity of the problems by choosing different matrices A, For the strongly-
U11
and
convex case, we first generate matrix A =
clip(
1,) where each d.y (0, 152)
an1
and
and the clipping operator clips the elements to the interval between and 10. Then we compute:
1
E
ANd-1)
A
10m Ei Al
A
AN
1..
10m
(dd1)
2i A
where O denotes the Hadamard product. We set the diagonal elements of cach A, using the corresponding row stored in the matrix A. Note that f(x) > A, has the minimum and the largest eigenvalues being 1 and 10. For the general convex case, we use the same matrix Ax to generate sparse matrix AM such that
AM Av O M where M a mask matrix with M, ~ B(1,p) and (1 We then compute the matrix A and set each A; in the same way.
1) M, 2 1, Vj E [1.d]
2-30
2
10n Ei And
O Aar
20
19
EP
A
Through the construction, the smallest eigenvalues (x) are clustered around zero, and the largest eigenvalue is 10. Additionally, each f²fi(x) is positive semi-definite.
We set the batch size to be and thus we have ft; = 0 with interpolation and E, = 0 without interpolation.
For AdaSPS/AdaSVRPS compare against DecSPS 44 SPS 34 and SVRG [2 and tune the stepsize for SVRG by picking the best one
fix cp 1, and for AdASVRPS further μtF 10 and pt 0.I0+I We
from {10') ).-........
In addition to these optimizers, we further evaluate the performance of SLS 52 AdaSLS, SGD, SPS 34 and AdaSVRLS. We fix qtale = 1, Ymax 10. 8 = 0.8 and p 1/2 for both algorithms and for AdaSVRLS, we further use f4r 10 and pt 6.1r4T. For SGD, we use the best learning rate schedules in different scenarios. Specifically, for both interpolation problems, keep the stepsize constant and for non-interpolation problems, we apply @(1/vt) and @11/t) decay schedules for convex and strongly-covve problems respectively. We further pick the best stepsize from {10') h.--....... For SPSmax. we use % 10 -3 and we only showease its performance in non-intert inteerrpollated settings. We report the results in Figure F. We observe that AdaSLS is comparable if no faster than the best-tuned vanilla SGD, SPSmax is reduced to the vanilla SGD with constant
stepsize. AdaSVRLS provides similar performance to AdaS VRPS but due to the cost of additional function evaluations, it is less competitive than AdASVRPS.
strangls -aaals--oome--tttteeeeee.. fiom
strungts coar ct Interpelation
comret-ine interpaladon
20
10"
10a
10'
101
62
10-2
30-1
207
000
30
10P
10-9
1003
2000
5
2000
4000
0
2500
5000
7500
10000
0
10000
20000
miti botch gradient eveluacions
mini batch grodient evaluations
min botch grad ont evoluations
miri botch g ondie evaluations
10"
10-4
10-2
10-1
Sto 522
10-1
Shap doe
S:0 dic
30-4
10-3
10-
Shap
10-1
1000
2000
2000
4000
2500
5000
7500
10000
0
10000
20000
mini botch gradient wuslint 1016
minbhttch gradien: untiios
min bbatch gredd wnt avwkuations
mini bwich www.uatOO
A445VPPS
AdASVRLS
SUSG
Ada
575
Ada775
S5C
DecSP5
Figure F.1: Comparison of the considered optimizers on synthetic data set with quadratic loss. The left block of the label illustrates the ceriance-reduced methods and the right represents SGD with different stepsizes. (Repeated times. The solid lines and the shaded area represent the mean and standard deviation.)
26

---

hyper-parameters used for synthetic experiments
optimizers
st-convextip
St-convex+non-ip
convex+ip
convex+non-ip
AdaSPS
Gp 1
AdaSLS
1. 3, = 0.8, 0.5, Timax 10
SPS
c= 0.5
SPSmax
c 0.5, 78 = 1003
SLS
0.1, 3 - 0.9, Timxx 10
DecSP$
00 = 1, 10
SGD
constant, 100-2
O11/1), 1) ==
constant, 7= 10-2 0(1V0), 10-1 Mr 10. pt 0.I+I
AdaSVRPS
Geale
AdaSVRLS
Gcale = 1, 0.8, = 0.5, mmax 0.1, pr 10 पा
SVRG
10
Table F.I: Hlper-parameeers of the considered optimizers used in synthetic experiments. st-convex stands for strongly-convex and ip stands for interpolation.
F.2 Binary classification
Following binary classification experiments presented the main paper. we provide additional experiments for VR algorithms. The chosen hyper-pprameetee for each algorithm can be found in Table F33 In particular, we fix ef = 1. Tmax
10a 3 0.8 and p = 1/2 for AdaSLS and AdaSVRLS. We report the best pp E {10 10"}. J- In Figure F.2 observe that AdaSVRLS/Ada VRPS provides similar performance to the other two suriance-reduction methods. The details of the four considered datasets are summarized Table
We next investigate impact of the probability schedule on the convergence behaviours. We pick w8a as the dataset and run AdaSVRPS (Alg. [ with and without probability decay, Specficially, we set p: B /n and = D.J++T to separate the cases. We control the level of the interpolation by using = 32 and B = 128 since ff128 S. 5.32- From Figure F3 we observe that decreasing probability schedule is more efficient when the
problem is more non-interpolated. This because for interpolated problems, the frequent computation of the full gradients the beginning provides no additional convergence benefits.
duke
rcvl
ijenn
w8a
n
44
20242
49990
49749
d
7129
47236
22
300
B
1
64
64
128
Table F.2: Number of datapoints, dimension of features, used batch size of four datasets from LIBSVM 10
duke
wSa
10'
369
Grafeetturm Narms
2.3%
Godeett
Gradent Noarmh
20-
20-
10-4
10-1
10:
5.00
1000
1500
5203
10000 15000
10000
20000
20000
10000
20000
30000
missbbttc grackent evalustiona
mamibatcc grad ent evaluations
mi7e batch grad evatustion
<717 batch grad evalunt ons
102-
3.7
100
102
1.0
Stop s44
Stu 2022
Soap 2802
Sigg
10-1
300
3.0
10:-
100
10'
10-
10a
10-1
500
1000
1500
5000
10000
15000
10000
20000
30000
10000
20000
30000
miniibatch gradiett avaluutioon
manihbatch gred ent svatuetions
mine batch gradd ant mvstustton.
mine--blth grad evstint on
ASSSVRLS
Ad3515
Figure F2: Comparison of the considered optimizers four LIBSVM datasets with regularized logistic loss. The left block the label illustrates the variance- reduuced methods the right represents SGD with different stepsizes. (Repeated 3 times. The solid lines and the shaded area represent the mean and standard deviation.)
27

---

wBa (B-32)
w8a (B-128)
10a
10a
10:4
10-2
Gradent Nomm
10-2
10-2
1
10-3
10
10-4
10
10-1
10-4
100000
200000 300000
20000 50000
mini-batch gradient evalustions
mini-batch gradient evalustions
AdeSVRPS with decreasing P
AdaSVRPS constant
Figure F3: Comparison of different probability schedules for AdaSVRPS the w8a datasct with regularized logistic loss. Decreasing probability more efficient when optimizing highly non-interpolated convex problems (Repeated times. The solid lines and shaded area represent the mean and standard deviation.)
optimizers
hyper-parumeteer used binary classification tusks
dake
Tcvl
ijenn
w8a
for
AdaSPS
AdaSLS
caak TImxx
ctth
Tiax 10
Tmax 10a
Tmax
102
0.8. p
SPS
c= 0.5
$1.5
Tmmax
Thaa 10
Tmax 10
Timax 10
8 0.9. 0.1
DeeSPS
% 200
2s 100
26 8(1/33). 100
SGD
constant,
10 6 I: 10
(11/v5), 100
(11vv 1 100
AdaNorm
Go 10
Go 10
Gp 10
by = 10
Adam
=== 10
===10-2
10
= 0.9, 8: 0.999
AdsSVRPS
pr
100
p. Sale
P: X
AdaSVRLS
100
jiy 10
11 10
1. 10
0.5,
SVRG
10
= 100
= 10
1) 10
AdoSVRG
We use heuristic method provied in Section 5 from [4.
Table F.3: Hyper-parameters of the considered optimizers used in binary classification.
G Deep learning task
In this section, provide heuristic extension of AdaSPS to over-parameterized non-convex optimization tasks. When training modern deep learning models, Loshchilov and Hutter (35 observe that eyclic hehaviour of the stepsize, i.c., increasing at the heginning and then decreasing up to a constant, can help with training and good generalization performance. Since AdaSPS a non-increasing stepsize, it excludes such a cyclic behaviour. To address this issue, we provide non-convex version of AdaSPS which incorporates restart mechanism that allows increase of the stepsize according the local curvature. The full algorithm is summarized in Algorithm 5 practice, we can set u B Algorithm 5 updates the stepsize and cp the beginning of each epoch and uses AdaSPS AddaSSS for the rest of the epoch.
Following
52 we benchmark the convergence and generalization performance of AdaSPS (DL) for the multi-class classification tasks on CIFAR (28 and CIFAR 100 29] datasets using ResNet-34 21. We
compare against SPS [34] Adam [66. AdaGrad [5]] DecSPS 44 and SGD with momentum. We use the
smoothing technique and pick c 0.02 for SPS suggested in [4] We the official implementations
of Adam, AdaGrad, and SGD with momentum from https///ptorr..oogg////ssssslblt
We choose
Ir 10 10-3 B = 0.9 and 32 0.999 for Adam. We choose Ir = 0.01 for AdaOrad. We choose Ir 0.01 and g = 0.9 for SGD with momentum. Finally, we pick ox = 0.02 for Algorithm 5 In Figure G.1 AdaSPS (DL)
shows competitive performance both datasets. We leave the study of its theoretical properties to future work.
28

---

0.95
101
10-1
Tex: Agp00ry
10--
size
0.85
10
10"4
10-3
0.775
Epach
CIPARI000ReNNe04
0..75
10f
0.63
Tran lass
Step
0.55
10
0.50
100
150
200
1000 Epoch
150
200
100 Epocc
150
200
Epoch
AdsSPS
500
AdaCrad
DecSPS
Adam
Figure G.I: Comparison of the considered optimizers multi-class classification tasks with CIFARIO and CIFAR 100 datasets using ResNet34 with softmax loss. AdaSPS (DL. Flnd SPS provide remarkable performance on both datasets.
optimizers
hyper-parameters used for multi-classfficaion tasks
AdaSPS (DS)
Actle 0.2
SPS
0.2 smoothing technique
DecSPS
74 1000
SGD-M
Ir 0.01, 3= == 0.9
AdaGrad
Ir = 0.01
Adam
10 81 0.9, 82 0.999
Table G.I: Slyper-parameee of the considered optimizers used in multi-classification tasks.
Algorithm AdaSPS (DL)
Require: Rd, T E N+, Scale
0, update frequency N+
1: set 17-1 +00
2: set 10-10
3: for = 0 T do
4:
uniformly sample C [n]
5: provide a lower bound f; S fü
6: if t mod is then
7:
set Cp
v Vii (x,
Ja (x:)-6
8:
set 1/- epll V.l (x:))12
E. (x.)-1,
9: else
-x
10:
set 1)- = min
(x, to 11-1
Xx+1 Xt ni (x,)
return Xx
29


Reviews:
[{"review_id": "DZepXXY3Ym", "reviewer": "Reviewer_NwRJ", "summary": "This paper proposes two new variants of SPS and SLS, called AdaSPS and AdaSLS, which provide convergence in non-interpolation settings for convex and strongly convex functions when training over-parameterized models. AdaSLS requires no knowledge of problem-dependent parameters, and AdaSPS requires a lower bound of the optimal function value as input. In addition, the paper studies a new variance reduction technique for AdaSPS and AdaSLS and proves the gradient complexity for convex functions, which improves upon the rates of AdaSPS and AdaSLS without variance reduction in the non-interpolation settings. This matches the fast rates of AdaSVRG and SARAH without the inner-outer-loop structure, which is easier to implement and analyze. The authors provides numerical experiments on synthetic and binary classification on LIBSVM datasets.", "questions": "Since the algorithm requires more parameter than classical methods, could you explain how they are chosen in the experiments/ suggested in practical settings? e.g. $\\mu_F$, $c_p$, $c_l$, $\\gamma_t$ , $p_t$? \n\nHow the lower bound information of 0 may affect the performance of the algorithm (theoretically and empirically), since the theory uses the correct lower optimal values. \n\n---\nI thank the authors for your rebuttal. My recommendation remains the same. ", "limitations": "NA", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The two algorithms AdaSPS and AdaSLS are interesting. The authors provide the convergence analysis for them, especially in non-interpolation setting the algorithms attained the classical convergence rate for convex functions. The variance reduction technique has the same complexity in expectation for convex functions as the rate of AdaSVRG and SARAH. ", "weaknesses": "The theoretical rate has comparison with SARAH but it is not included in the experiment. The variance technique and the one loop structure is not entirely new since it already appeared in the PAGE algorithm. The authors may consider discussing that as well. A natural question is why practitioners should use the new variance reduction algorithms while it is more complicated than the well established methods in convex settings. Thus more extensive experiments would help to demonstrate the effectiveness of the algorithms. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the remarks and suggestions on our paper. You can find our replies below:\n\n> Comparison with SARAH and PAGE\n\nWe thank the reviewer for mentioning PAGE. We will include the discussion on PAGE in the potential camera-ready version. We would like to highlight that **there is no direct connection of our methods to SARAH and PAGE.** We classify SVRG, SARAH, and PAGE into the first group, as they propose different gradient estimators for variance reduction. To guarantee convergence, the knowledge of $L$ is required to set their constant stepsizes. Conversely, AdaSVRG/AdaSVRPS/AdaSVRLS belongs to a different group where they fix the gradient estimator first (for instance, they all use SVRG) and the focus is to set the stepsize adaptively without the need to know problem-dependent parameters to guarantee convergence. **Therefore, the works in these two groups are orthogonal.** \n\n> Technical novelty\n\nWe do not claim that the one loop structure and probabilistic update of the full gradient is new since it has already been discussed in Dmitry [19] and PAGE as you mentioned. However, our proposed VR framework based on the moving sequence of random functions is new as it allows some difficult adaptive stepsizes such as Polyak and line-search type algorithms to accelerate. With the common VR technique, these stepsizes fail to converge. Another novelty is that with our decreasing probability strategy, the inner-outer-loop structure used in AdaSVRG can be removed and this strategy is the key to providing the optimal convergence rate in the convex setting. In the other works on loopless VR technique, the probability is set to be a constant. \n\n> SARAH experiment\n\nWe thank the comment on SARAH and we have included it in the attached pdf under the same experimental setting as in Section 5. But as we mentioned earlier, AdaSVRPS/AdaSVRLS/AdaSVRG/SVRG all use the same gradient estimator but with different stepsizes. Consequently, we think it is fair to compare them in the experiments. Comparison of different gradient estimators is a bit orthogonal to the focus of this work.\n\n> How to set hyper-parameters for AdaSVRPS/AdaSVRLS in practice\n\nFor both AdaSVRPS and AdaSVRLS, the key parameters are $\\mu_F$ and $c_p^{\\text{scale}}/c_l^{\\text{scale}}$. \n\nNote that the inverse of the curvature of the random function $F_{i_t}$ is upper bounded by $\\mathcal{O}(\\frac{1}{\\mu_F})$ ($F_{i_t}$ is at least $\\mu_F$-st covex). Therefore, the smaller the $\\mu_F$, the larger the maximum value of the stepsize could reach. In practice, we can set it to be $10^{-4}$ for a potential aggressive stepsize in the case where $d>n$. Otherwise, we can set it to be $1$ for a conservative stepsize. \n\n$c_p^{\\text{scale}}/c_l^{\\text{scale}}$ controls the scale of the Polyak stepsize/line-search stepsize. In other words, the adaptive stepsize is upper bounded by the standard  Polyak stepsize/line-search stepsize multiplied by the inverse of $c_p^{\\text{scale}}/c_l^{\\text{scale}}$. A reasonable choice would simply be $c_p^{\\text{scale}}/c_l^{\\text{scale}}\\in[0.5,1,2]$. The smaller the number, the more aggressive the stepsize. \n\nFor the parameters inside the line-search method, we always  fix $\\gamma_{\\max}=10^3$ or $\\frac{1}{\\mu_F}$, $\\beta=0.8$ and $\\rho=1/2$. \n\nThe last parameter $p_t=\\frac{1}{at+1}$ is very flexible. The smaller $a$, the more frequent of computation of the full gradient. A standard choice would be $a=0.1$. However, depending on the computational power, one can freely choose this number. In constrast, the inner-outer-loop structure of AdaSVRG does not allow arbitrary full gradient update frequency. Indeed, AdaSVRG fails to converge with inner-loop size being one and fixing $g_t = \\nabla f(x_t)$.\n\nAll the experimental details can be found in Appendix F. \n\n> Impact of  the lower bound of zero for AdaSVRPS in practice\n\nYes, for AdaSVRPS, we use the exact $F_{i_t}^\\star$ in theory. If we replace it with $\\ell_{i_t}^\\star$ (a lower bound of $F_{i_t}$), then an additional slow down term $\\mathcal{O}(\\frac{\\sigma}{\\sqrt{T}})$ will occur in theory. The proof can follow the routine for AdaSPS. However, in practice, it suffices to use $\\ell_{i_t}^\\star+\\min_x\\{x^T(\\nabla f(w_t)-\\nabla f_{i_t}(w_t))+\\frac{\\mu_F}{2}||x-x_t||^2\\}$ where $\\ell_{i_t}^\\star$ is a lower bound for $f_{i_t}^\\star$ which is zero normally. Note that we use this lower bound for all our experiments and AdaSVRPS always shows competitive performance compared with a well tuned SVRG. Therefore, we believe using a lower bound has no impact in practice and sometimes can even make the algorithm behave more aggressively (since the stepsize is larger than needed).\n\n> Practical consideration\n\nThe previous well-established VR methods including SVRG/SARAH/PAGE requires the knowledge of Lipschitz constant to guarantee convergence. AdaSVRG needs to predefine the target accuracy $\\epsilon$ to design the number of stages and the inner-outer-loop size. Also, the arbitrary full gradient update frequency is not supported. While AdaSVRPS/AdaSVRLS requires more hyper-parameters, one can simply set $\\mu_F=1$ and $c_p^{\\text{scale}}/c_l^{\\text{scale}}=1$, and the algorithms can reliably converge at a correct rate of $\\mathcal{O}(1/T)$. The user also has the freedom to adjust these parameters to gain more aggressive practical performance. \nFor the two adaptive stepsizes, AdaSPS/AdaSLS brings much convenience to the user experience since they do\nnot need extra tuning of the stepsize (simply setting $c_p^{\\text{scale}}/c_l^{\\text{scale}}=1$ is enough for robust convergence). \n\nWe believe that our newly proposed stepsizes and the novel VR framework are important contributions to the community as this may motivate more personalized VR techniques in the future. If you agree that we managed to address all issues, please consider raising your mark. If you believe this is not the case, please let us know so that we have a chance to respond. We really appreciate that."}, {"review_id": "PlfrVs1pt7", "reviewer": "Reviewer_a9xP", "summary": "This paper introduces Adagrad-norm type update into stochastic line search (SLS) and stochastic Polyak step size (SPS) (namely AdaSLS and AdaSPS) that guarantee convergence in non-interpolating convex scenario with a $\\mathcal{O}(\\frac{1}{\\epsilon^2})$ rate. Then it shows that AdaSLS and AdaSPS  converge linearly when interpolation holds under strong convexity. Finally, it combines variance reduction with AdaSLS/AdaSPS to improve the convergence to $\\mathcal{O}(n+\\frac{1}{\\epsilon})$ for convex losses.", "questions": "I vote for rejection due to the following reasons:\n\n1. No improvements in rates over previous works in either interpolation or non-interpolation scenario.\n\n2. Weak empirical results. The gain in the proposed method is insignificant.\n\n3. The analysis requires some strong assumptions and additional requirements to obtain the same rate as previous works.\n\n[1] Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution\n\n[2] Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates\n\n[3] Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Overall, the paper is well-written. The comparisons with existing literature results are thorough. \n\n2. The introduction of loopless variance reduction, together with AdaGrad and SPS/SLS into a single framework is novel.", "weaknesses": "1. There is no improvement in the convergence rates. DecSPS was introduced to make SPS converge in non-interpolating settings by forcing the step size to be monotonic-decreasing. The proposed AdaSPS essentially replaces the sequence $c_k$ in DecSPS [1] with Adagrad-Norm, and the step size is also monotonically decreasing, resulting in the same rate as DecSPS. In the interpolating settings, SLS  [2] and SPS [3] already converge without the step size being monotonic decreasing. I don’t see the improvements in AdaSPS/AdaSLS over previous methods under interpolation or non-interpolation. \n\n2. In the strongly-convex interpolating case, AdaSPS/AdaSLS converges linearly with some requirements given in Corollary 6. SPS and SLS have the same convergence rate without those additional requirements. In fact, the constants $c_p$ and $c_l$ associated with AdaSPS and AdaSLS respectively depend on the sample at first iteration. I don’t see how this is always satisfied. Does it mean that $c_p$  and $c_l$ need to change every time when running the algorithm? In addition to this, AdaSPS/AdaSLS assumes that each function is strongly convex, this is a very strong assumption that does not appear in the analysis of SPS and SLS. Does it mean only optimizing one function is sufficient as they all share the same unique global optimum under interpolation? \n\n3. The experiments are not promising. Figure 1 just shows that AdaSPS performs worse than SPS under interpolation, and performs worse than or similarly to DecSPS under non-interpolation. If there already exists some better alternatives in either setting, what is the benefit of using AdaSPS?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the remarks and criticisms. Before responding to each point, we kindly want to highlight our first contribution to address your main concern. \n\n**We focus on the settings where the underlying interpolation condition is unknown to the users.** Having a **robust** (that can adapt to the interpolation condition) and theoretically-grounded algorithm is important in many cases such as in the federated learning setting as mentioned in the introduction part. **Furthermore, it is not easy to determine whether or not a model is effectively interpolating the given dataset.** Consider the rcv1 dataset where the dimension of features are twice larger than the number of data points. A logistic regression model is considered overparameterized. But the features are actually sparse and it is not interpolated.  Therefore employing SPS/SLS cannot guarantee convergence. **Developing a robust and reliable algorithm will be of great convenience for the users in practice.**\n\nAs summarized in Table 1, our newly proposed AdaSPS/AdaSLS are the **first** adaptive stepsizes to have such strong **robust** theoretical guarantees in all cases without knowledge of the Lipschitz constant.\n\nWe now provide answers to each point.\n\n>W1. There is no improvement in the convergence rates.\n\nWe kindly disagree. The previous adaptive methods are the best on a certain range class of problems, while our method achieves the best known rates in all these scenarios. From Table 1, AdaSPS/AdaSLS achieve both fast convergence rates in the interpolation settings like SPS/SLS and in non-interpolated settings like DecSPS. **These asymptotic rates are already optimal and cannot be further improved.** (except for strong convexity without interpolation). The denominator defined in AdaSPS/AdaSLS is essentially the key to having such an adaptivity to the underlying interpolation condition. Note that DecSPS artificially incorporates $\\mathcal{O}(1/\\sqrt{t})$ decreasing rule which results in slow convergence with interpolation while the denominator designed for AdaSPS/AdaSLS actually can be upper bounded by a constant if interpolation holds and will go to infinity if not. \n\n> W2. Assumptions\n\nWe thank the reviewer for the comments. In the attached pdf, we replaced the individual strong-convexity assumption in Theorem 5 with the classical individual convexity. The original linear rate complexity is preserved. \n\nWe kindly disagree with the comment “The analysis requires some strong assumptions and additional requirements to obtain the same rate as previous works.” **In all the cases, our assumptions are at least the same or even weaker than any of the previous adaptive methods!** . \n1. Convex + interpolation: SPS/SLS/DecSPS assumes individual convexity while ours and AdaGrad-Norm only assume $f$ is convex (See Theorem 1 with noise = 0). \n2. Convex + interpolation + individual convexity: we can further remove the bounded iterates assumption while AdaGrad-Norm cannot. \n3. Convex + non-interpolation: DecSPS assumes individual convexity while ours and AdaGrad-Norm only assume $f$ is convex. \n4. st-convex + non-interpolation + individual st-convexity: ours and DecSPS remove the bounded iterates assumption while AdaGrad-Norm cannot.\n5. st-convex + interpolation: SPS/SLS and ours all assume individual convexity. While AdaGrad-Norm cannot show linear convergence without knowledge of $L$. DecSPS only has $\\mathcal{O}(1/\\epsilon^2)$. \n\nThis shows again the **strong robustness and the weakest assumptions required** for our stepsizes.\n\n> W3. How to set $c_p$/$c_l$\n\nAs illustrated in the numerical evaluation section, we used the theoretically justified hyperparamter $c_p^{\\text{scale}}$ which essentially only depends on the first iterate. For instance, let us fix $c_p^{\\text{scale}}=1$. Then $c_p=\\frac{1}{2\\sqrt{f_{i_0}(x_0)-\\ell_{i_0}^\\star}}$ and it will not change during the iterations. This quantity provides the right scaling correction to the stepsize and brings much convenience to the user experience since they do not need extra tuning. \n\n> W4. The experiments are not promising?\n\nWe kindly disagree: Our synthetic experiments are designed to illustrate the **robustness** of our proposed algorithms. Let us compare these algorithms closely. \n\nWe first agree that AdaSPS is not as competitive as SPS with interpolation since AdaSPS is a non-increasing stepsize. However, AdaSPS shows the desired linear and sublinear convergence for st-convex and convex problems while DecSPS converges much more slowly. In the non-interpolation regimes, SPS **cannot** converge and has a big neighborhood error. **AdaSPS outperforms DecSPS in all the experiments** (See Figure 1 and 2) **only except** the second plot in Figure 1 which we can apparently choose a larger $c_p$ to improve its performance. (Note we fix the same $c_p^{\\text{scale}}=1$ across these experiments to show the robustness).  As such, AdaSPS can be seen as a direct replacement for DecSPS (both in theory and in practice).  \n\nIf we are certain that the underlying problem is interpolated and we know the exact optimal function value, then we definitely recommend using SPS. Otherwise, AdaSPS/AdaSLS is always reliable and offers a better choice. \n\nWe would like to highlight another importance of introducing AdaSPS/AdaSLS. SPS/SLS/DecSPS all fail to be incorporated into the VR framework because they are not robust. Our work gives a very promising direction that even these difficult stepsizes can also be combined with VR techniques as long as we can 'make them robust'. This may motivate more personalized VR techniques in the future. \n\nWe believe that our newly proposed stepsizes and the novel VR framework are good contributions to the community for many potential extensions. If you agree that we managed to address all issues, please consider raising your mark. If you believe this is not the case, please let us know so that we have a chance to respond. We really appreciate that."}, {"review_id": "P6LA0JdxKk", "reviewer": "Reviewer_7mHQ", "summary": "The paper aims to propose robust methods that achieves optimal rates in both\nstrongly-convex or convex and interpolation or non-interpolation settings.\nSpecifically, they propose AdaSPS, a modification of $SPS_{max}$ with\nan AdaGrad-like denominator (replacing the gradient norms with function values) in\nthe stepsize, and AdaSLS, a combination of AdaGrad-Norm and line search\nmethods.\n\n- For convex functions,\nAdaSPS and AdaSLS achieve a $O(1/\\epsilon^2)$ convergence rate assuming individual\nsmoothness and bounded domain.\nWhen interpolation is assumed, both methods get rid of the bounded domain\nassumption (but additionally require individual convexity and AdaSPS requires\nthe exact minimal function values) and achieve a $O(1/\\epsilon)$ convergence\nrate.\n- For strongly-convex functions, individual strong-convexity and smoothness\nare required. AdaSPS and AdaSLS achieve a $O(1/\\epsilon^2)$ rate without interpolation.\nWith interpolation, they achieve linear convergence rates.\n- Furthermore, the author combine the proposed methods with variance reduction techniques,\nand improves the rate for strongly-convex and convex settings to $O(1/\\epsilon)$\nwithout interpolation.\n\nThe proposed methods are also evaluated by numerical experiments.", "questions": "  I would appreciate it if the author could address the concerns listed\n  as weaknesses 1-3. \n\nAdditionally, I wonder if we could change the added function value\n  gaps (under the square root) in the denominator of AdaSPS stepsize to the\n  squared norm of gradients (like AdaGrad) and obtain a similar result. Is the use\n  of function value gap necessary?\n", "limitations": "  I think the main limitation is the sub-optimality in the non-interpolation\n  strongly-convex setting, which is also a known hard problem for adaptive methods.\n  This is metioned in the Conclusion and future work section of the paper.\n", "rating": 4, "confidence": 3, "soundness": 1, "presentation": 4, "contribution": 2, "strengths": "1. The paper has clear logic and is well-written, making it easy to follow.\n2. In all considered settings (convex/strongly-convex and interpolation/non-interpolation),\nthe proposed AdaSPS and AdaSLS match the rate of well-tuned SGD in all settings\nexcept for the case when we have strongly-convexity and non-interpolation.\nImportantly, AdaSLS achieves this without requiring knowledge of any problem-dependent parameters.\n3. The intuition behind the proposed variance reduction framework is interesting,\nand could potentially motivate new algorithms.", "weaknesses": "  1. The related work on interpolation is somehow insufficient. One very\n  relevant work [1] is missing. Importantly, [1] also proposed combining AdaGrad\n  with line search, similar to AdaSLS, and provided theoretical guarantees in convex setting.\n  The difference is that AdaSLS uses a minimum operator for all past stepsizes.\n  Usually, non-diminishing stepsizes work better in practice, so it would also\n  make sense to compare them in the experiments.\n  2. I cannot find any theorems or proofs that show the results of AdaSVRPS/AdaSVRLS \n  in strongly-convex and convex settings with interpolation,\n  as listed in Table 1. This is the reason why I give\n  a 1 in the soundness assessment.\n  3. Without variance reduction, the paper claims that their algorithms match the convergence rate of SGD in\n  many settings, however, the assumptions are different. Individual smoothness\n  and individual (strongly-)convexity are additionally assumed in many theorems in this work,\n  making it hard to compare them to classical results of SGD (also AdaGrad-Norm).\n  I wonder if there are lower bounds for the individual (strongly-)convexity\n  settings. With variance reduction, Theorem 8 also requires individual convexity,\n  while the compared AdaSVRG does not.\n\n  Minor issues:\n\n  4. Table 1 could contain results of AdaSVRG and SARAH for a more comprehensive comparison\n  of adaptive variance reduction methods. For the interpolation strongly-convex setting\n  where we have linear convergence, the dependence on $\\kappa$, the condition number,\n  is also important.\n  5. In Theorem 5, $T_p$ and $T_l$ are not defined. According to the results in\n  the appendix, they depends on $\\epsilon$ (of order $1/\\log(1+\\epsilon)$, or nearly $1/\\epsilon$,\n  if $c_p$ is chosen poorly).\n  6. Usually the scalar version of AdaGrad is referred as AdaGrad-Norm. Calling\n  it AdaNorm is not common, especially when there are other algorithms called AdaNorm.\n\n\n  **References:** \n\n  [1] Vaswani, Sharan, et al. \"Adaptive gradient methods converge faster with over-parameterization (but you should do a line-search).\" arXiv preprint arXiv:2006.06835 (2020).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive remarks. We provide answers below. (For space limit, We omit the big O notation and write V-SGD for Vanilla SGD, AGN for AdaGrad-Norm, IC for individual convexity, ISC for individual st-convexity and PCV for potential camera-ready version).\n\n> W1. Paper on AdaGrad+line-search\n\nWe apologize for missing this paper and will include it in our PCV. Since we study adaptive stepsize for SGD, let us discuss the scalar version of this algorithm. \n\nFor AGN with constant stepsize, the best $\\eta$ should be of order $\\Theta(D)$ which gives the optimal rate of $LD^2/T+\\sqrt{L}D\\sigma/\\sqrt{T}$. Note this method multiplies it by a scalar of order $1/L$ which results in a suboptimal rate $D^4L^3/T+D^2L^{3/2}\\sigma/\\sqrt{T}$ (See Theorem 2 in this paper and $\\eta_{\\max}$ is usually larger than $\\frac{1}{L}$). In contrast, our carefully designed AdaSLS multiplies the inverse of the curvature $\\gamma_t$ by the refined scaling term $1/c_l\\sqrt{\\sum_{s=0}^t\\gamma_s||\\nabla f_{i_s}(x_s)||^2}$ instead of $1/\\sqrt{\\sum_{s=0}^t||\\nabla f_{i_s}(x_s)||^2}$ (this paper) which allows to obtain the optimal convergence rate.\n\nIn the case of interpolation + IC, they can remove the constraint on $\\eta_{t+1}\\le\\eta_t$ to improve practical performance. For AdaSLS, we can also remove the $\\min$-operator, and the fast rate is still preserved (our proof does not require $\\min$-operator in this case).  However. since we focus on the setting where the underlying interpolation condition is unknown, it is only fair to compare these methods with conservative constraints. This paper requires $\\eta_t\\le\\eta_0$, and thus the algorithm is no better than a well-tuned AGN in practice. Since we have compared our stepsizes with the best-tuned AGN, we argue that it is not necessary to add this method to the experiments.\n\n> W2. VR, typos\n\nWe thank the reviewer for finding these typos. For the VR methods, in all the four cases listed in Table 1, we will refill them with $\\tilde{\\mathcal{O}}(n+\\frac{1}{\\epsilon})$. Theorem 8 covers the convex and interpolation setting as well as the two st-convex settings.  \n\nFor the st-convex problems, it is a known hard problem to prove adaptive VR methods converge linearly. Since we do not claim any contribution of our new VR methods to the st convex setting and the word robustness is referred to the adaptive stepsizes, we really appreciate it if you consider raising your soundness score. \n\n> W3. Assumptions\n\nWe thank for your careful discussion. We first agree V-SGD only requires smoothness of $f$. But individual smoothness assumption is also standard and can be satisfied in practice. Under this assumption, for all the cases, **the assumptions required for AdaSP/LS are at least the same or even weaker than any of the previous adaptive methods**.\n1. $f$ is convex + interp. V-SGD with constant stepsize/AdaSP/LS/AGN converges as  $1/T$. SPS/SLS/DecSPS requires IC and DecSPS converges slowly. \n2. $f$ is convex + non-interp. V-SGD with decreasing stepsize/AdaSP/LS/AGN converges as $\\sigma/\\sqrt{T}$. SPS/SLS cannot converge. DecSPS needs IC.\n3. $f$ is convex + IC + interp. AdaSP/LS can remove bounded iterates assumption while no such result exists for AGN. \n4. $f$ is st-convex + ITC + non-interp: AdaSP/LS/DecSPS can remove bounded iterates assumption while no such result exists for AGN.  \n5. $f$ is st-convex + interp: (In the attached pdf, we replaced ISC with the classical IC, and the original linear rate is preserved.) **In this case, the current adaptive methods require one more assumption than V-SGD**. V-SGD converges as $\\exp(-\\mu T/L)$. With additional IC, SPS/SLS converges as $\\exp(-\\mu T/L)$. AdaSP/LS also converges linearly, the constant of which depends on the first iterate and is usually worse than SPS/SLS (see attached). AdaGrad-Norm cannot converge linearly without knowing $L$.\n\nVR method + $f$ is convex: AdaSVRP/LS requires IC while SARAH/AdaSVRG do not. We will clearly state this requirement  in our PCV. However, since SPS/SLS exactly needs individual convexity in the interpolation setting. we think this assumption cannot be removed and we believe this is a weakness of these methods compared with AdaGrad. But in practice, the IC assumption is often satisfied.\n\n> Q1. Can we replace added function value gaps with the squared norm of gradients\n\nThere are a few reasons why we cannot. 1) scaling issue. Suppose the exact Polyak stepsize is used. This quantity is of scale $1/L$. If we multiply it by AGN, then the scaling gives a suboptimal rate. 2) For convex problems, the error term $f_{i_t}(x_t)-f_{i_t}^\\star$ cannot be upper bounded by $||\\nabla f_{i_t}(x_t)||^2$ which might lead to divergence. 3) If we relax it to $\\frac{f_{i_t}(x_t)-\\ell_{i_t}^\\star}{||\\nabla f_{i_t}(x_t)||^2}$. Then the error caused by $\\ell_{i_t}^\\star$ cannot be compensated by the growing squared norm of the gradients at a correct rate. But it can be controlled by the accumulated $f_{i_t}-\\ell_{i_t}^\\star$ used in AdaSPS. \n\n> M1. A refined version of Table 1\n\nWe thank for the suggestions. We will add the results and its relaxed assumption for AdaSVRG. For SARAH, since it uses a different gradient estimator and its stepsize is constant, we think it is a bit unfair to add it to Table 1 for adaptive stepsizes. For ISC problem, we agree that the constant is important and we will add it for clarity.\n\n> M2. $T_p$ and $T_l$\n\nWe agree that if $c_p$/$c_l$ is chosen poorly, the convergence can be sublinear. Therefore, we recommend the theoretically suggested $c_p$/$c_l$ indicated in the Theorem to avoid the potential slowdown. These values only depend on the first iterate. In other words, they are parameter-free. \n\n> M3. A correct name: AdaGrad-Norm\n\nWe will do that, thanks.\n\nWe thank you again for the great reviews. If you agree we addressed the main concerns, please consider raising your mark. If you believe not, please let us know. We really appreciate that.\n \n\n\n"}, {"review_id": "kxLebvOalN", "reviewer": "Reviewer_Dgvs", "summary": "This paper presents two step-sizes, AdaSPS and AdaSLS, and theoretical analyses of PSGD with AdaSPS/AdaSLS. It also presents numerical results to support the analyses. The contribution of the paper is to provide AdaSPS and AdaSLS step-sizes. ", "questions": "- AdaSLS and Lemma 17 (AdaSPS_main+appendix.pdf): Using the Armijo condition (4) in AdaSLS is interesting. Here, I check Lemma 17 (AdaSPS_main+appendix.pdf). However, I doubt that there exists a lower bound $(1-\\rho)/L$ of the step-size $\\gamma_t$ satisfying (4). In  fact, we can provide counter-examples such that the step-size $\\gamma_t$ satisfying (4) does not have any lower bounds. Consider $f(x) = x^2$ and apply it to the Armijo condition (4). Then, we can set a sufficiently small $\\gamma_t$.\n- Armijo condition (4): Related to the above comment, Figure 5 in [32] indicates that there is a possibility such that $\\gamma_t$ satisfying (4) converges to 0. Hence, we have counter-examples of Lemma 17 such that there does not exist a lower bound of the step-size $\\gamma_t$ satisfying (4).\n- AdaSPS: AdaSPS uses $\\ell_{i_t}^\\star$. It would be unrealistic in deep learning. Can the authors provide some practical examples of $\\ell_{i_t}^\\star$ and $\\eta_t$ defined by AdaSPS in deep learning?\n- Assumptions: Can the authors provide some examples of satisfying the interpolation condition? \n- Convex optimization: Since optimization problems in deep learning are nonconvex, considering only convex optimization is limited in machine learning society. Can the authors rebut this? \n- Can the authors provide numerical results for training DNNs on the benchmark datasets (CIFAR-100 and ImageNet)? Using only LIVSBM datasets is insufficient to show usefulness of the proposed algorithms. ", "limitations": "There is no potential negative societal impact.", "rating": 2, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "The strength of the paper is to provide two step-sizes, AdaSPS and AdaSLS, and to apply them to PSGD. In practice, the modifications, AdaSVRPS and AdaSVRLS, accelerate the existing methods.  ", "weaknesses": "- This paper considers only convex optimization, although optimization problems in deep learning are nonconvex.\n- There seem to be some doubts in Lemmas and Theorems. I would like to have solutions for the doubts (Please see Questions).  \n- Numerical results are insufficient since it does not consider optimization problems in deep neural networks. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the remarks and criticisms. We are a bit puzzled by your score. We provide clear answers to your questions below. \n\nAlthough we do not claim any contribution to the deep learning scenarios, we do provide DL experiments with our practical version of AdaSPS. Please see Appendix G for more details. In Figure G.1, we give results of multi-class classification tasks with CIFAR10 and CIFAR100 using ResNet34 with softmax loss. We compared our stepsize against the popular algorithms including Adam, SGD-M, AdaGrad, and SPS, **among which our proposed AdaSPS gives the best performance**.\n\nWe next provide answers to your questions.\n\n> Q1. line-search: lower bound\n\nWe kindly disagree. The lower bound should be $\\min(\\frac{1-\\rho}{L},\\gamma_{\\max})$. We guess you missed the $\\min$ operator. (See also Lemma 1 in your mentioned paper). We also provide concrete proof in Lemma 17 in the appendix.\n\nWe next answer your second question on why the stepsize in Figure 5 may diminish. \n\n1. The implementation of SLS shown in Figure 5 uses dynamic initialization of $\\gamma_{\\max}$ to reduce the algorithm's running time, that is, setting $\\gamma_{\\max t}=\\gamma_{t-1}\\theta^{1/n}$ where a common choice for $\\theta$ is 2 and $\\gamma_{t-1}$ is the previous stepsize which reflects the curvature. Therefore $\\gamma_{\\max}$ is not fixed anymore.\n\n2. Note that in ResNet 32, more than 80 percent of the parameters (denoted by $x$) are scale invariant, that is $f(x)=f(cx)$ for any $c>0$. This implies that $||\\nabla^2 f(x)||=\\frac{1}{||x^2||}||\\nabla f^2(\\frac{x}{||x||})||$ which is unbounded from above and thus $f(x)$ is **not** smooth. See more discussions in [1]. \n\nCombining 1) and 2), we can clearly see that the iterates generated by SLS may converge to some minimizer with locally increasing curvature and therefore the stepsize diminishes (which is the inverse of the curvature). \n\nTo sum up, for non-smooth functions, the lower bound might not exist. However, in our work, we consider smooth functions.\n\n> Q2. $\\ell_{i_t}^\\star$ in deep learning\n\nWe kindly disagree with the comment *AdaSPS uses $\\ell_{i_t}^\\star$ It would be unrealistic in deep learning.*\nFirst of all, $\\ell_{i_t}^\\star$ is much more readily available than $f_{i_t}^\\star$ and this is already an improvement over SPS. Second of all,  in most deep learning tasks, the loss functions are always lower bounded by zero, i.e. $\\ell_{i_t}^\\star=0$. The examples include but are not limited to:\n1. Regression: Mean Square Error, Mean Absolute Error, Huber loss and  log-cosh loss,\n2. Classification: Cross-entropy loss, Hinge loss, etc. \n\nThese losses are commonly used in machine learning and deep learning tasks.\n\n> Q3. Examples satisfying the interpolation condition\n\nIf the machine learning model  is highly expressive and can fit the training dataset completely, then normally the interpolation condition holds. For convex problems, a classical example would be binary classification using RBF kernels without regularization and with logistic loss. For non-convex problems, training an overparameterized neural network is a classical example.\n\n> Q4. Since deep learning is non-convex, Why do we still study convex problems?\n\nWe thank the author to raise this question.\nFirst, the development of the 'appropriate' optimization theory for deep learning models remains an elusive challenge. These complicated models are often non-convex, non-smooth, and non-differentiable at their minimizes (e.g. relu activation and normalization). Traditional analysis  investigates convergence towards stationary points with zero gradient norms. However, for deep learning, this conventional framework might not be useful. Therefore, the exploration of optimization theory for deep learning models remains an open question.\nSecond, solving open questions in stochastic convex optimization boosts theoretical understanding and scientific development.\nMachine learning is not only about deep learning. Many machine learning problems are indeed convex such as SVM, logistic regression, and linear regression. Even for these simple models, there still exist tricky problems that we cannot solve yet. Providing solutions or insights into these problems will help us understand more complicated models and this is essentially how science should proceed. \n\n> Q5. Numerical results for training DNNs\n\nAs mentioned earlier, we provide solid evidence in Appendix G that our proposed stepsize works well on deep learning tasks. Therefore, we think it is a promising stepsize that needs further study in the future.\n\n> Remark\n\nIt is important and crucial to fundamentally understand the behavior of adaptive algorithms in st-convex and convex functions before we advance it to a more complicated case. We would like to highlight the contributions in our work. First, we propose two adaptive stepsizes which have both strong theoretical guarantees and practical performance, under the weakest assumptions, which improves upon some of the drawbacks of the previous methods. Essentially, the user can reliably apply our methods to the problems, without the need to know problem-dependent parameters and the underlying interpolation conditions that are often difficult to assess. This serves as a good step towards a totally automatic adaptive stepsize. Besides, they also show strong performance in deep learning experiments. Secondly, Polyak and line-search type methods all fail to be combined with the classical VR framework. However, we break this limitation and manage to accelerate these two complicated stepsizes. We believe our newly proposed framework may encourage more personalized VR techniques in the future. \n\nIf you agree that we managed to address all issues, please consider raising your mark. If you believe this is not the case, please let us know so that we have a chance to respond. We really appreciate that.\n\n[1] Robust Training of Neural Networks Using Scale Invariant Architectures, ICML 2022"}]

Author rebuttal:
Thanks to all reviewers for examining our manuscript and help with improving our paper. We appreciate the constructive comments from the reviewers, and we address all raised issues via individual comments.

We like to highlight that:
- **We propose the first adaptive methods that simultaneously achieve optimal asymptotic rates in both strongly-convex or convex and interpolation or non-interpolation settings. This is a significant contribution, as it is not easy to determine whether or not the interpolation condition holds for a given problem (without solving it).**

    We work on smooth and convex optimization. We focus on the practical scenario where the underlying interpolation condition of the considered problem is unknown to the users. We propose two new robust stepsizes based on Polyak stepsize and line-search. These are the first adaptive methods that simultaneously achieve optimal asymptotic rates in both strongly-convex or convex and interpolation or non-interpolation settings (except for the case when we have strongly-convexity and non-interpolation), without requiring knowledge of the Lipschitz constant. Furthermore, AdaSPS only needs a lower bound of the optimal function value and AdaSLS is completely parameter-free. Under the  standard individual smoothness condition, the assumptions required are the weakest compared with all the previous adaptive methods. We provide theoretically suggested hyper-parameters for these stepsizes, which makes it even more convenient and reliable for the users to apply in practice. Moreover, their competitive performance in deep learning experiments show strong potential for non-convex optimization as well. 

- **We propose the first variance-reduced methods with Polyak stepsizes or line-search. This is a significant contribution, as trivial combinations of existing variance-reduction techniques with Polyak stepsizes or line-search does not work (see the lower bound proven in [8] for line search, and appendix E for SPS).**

   Polyak and line-search type methods cannot converge with the classical variance-reduction framework. In this work, we successfully break this long-time barrier and manage to accelerate these two complicated stepsizes. We managed to do that by first proposing a novel variance-reduction framework based on the random proxy function sequence and then applying our robust stepsizes to the new proxy function. We prove the optimal rate of our new algorithms for convex problems. We also introduce the new decreasing probability strategy which allows to remove the classical inner-outer-loop structure and make the proof much easier. Numerical experiments show their strong performance in practice. 

Reviewer NwRJ found our two algorithms AdaSPS and AdaSLS are interesting. Reviewer a9xP thinks our variance-reduction framework combined with adaptive stepsizes is novel. Reviewer 7mHQ correctly recognizes that our new robust stepsizes have the strong theoretical guarantees and supports AdaSLS as' Importantly, AdaSLS achieves all this without requiring knowledge of any problem-dependent parameters.' Reviewer 7mHQ further agrees that 'the intuition behind the proposed variance reduction framework is interesting, and could potentially motivate new algorithms.' Reviewer Dgvs thinks using these stepsizes and combining them with acceleration can be useful in practice. 

Based on the questions of the reviewers, we have made the following major updates.
1) We replaced the individual strong-convexity assumption in Theorem 5 with the classical individual convexity and prove the same linear convergence rate. 
2) We added the comparison of SARAH in experiments.
3) We fixed the typos of the last two lines within the interpolation columns in the Table 1. 

To summarize, in this work, we propose two new adaptive stepsizes that enjoy robust convergent guarantees, which serves as a good step towards a totally automatic adaptive algorithm. Our novel VR framework is general and may motivate more personalized variance-reduction techniques in the future. We believe both of them are important contributions to the community. 

We anticipate an interactive discussion with you, and we will be most happy to answer any remaining questions.

Meta-review: Although the reviewers are on average negative, I feel that achieving fast interpolation and non-interpolation rates is an important contribution and I feel that the authors did a reasonable job responding to the criticisms brought up in the reviews. As most of the reviewers did not engage with these rebuttals, I am leaning towards saying that the criticisms were addressed and the paper should be accepted.

Please make sure that the following changes are made (in addition to other comments brought up in the review):
- Fix the table and downplay the claims about the variance-reduced versions. (I would even be fine if you removed the variance-reduced versions from the paper, I feel like they make it more confusing and given the weaker result they downplay interestingness of AdaSLS and AdaSPS.)
- Report numerical results in the main paper where you choose one fixed set of hyper-parameters across datasets. I considered for a long time whether to reject the paper just on this point - truly adaptive methods should not need hyper-parameter tuning for each dataset.
- I feel like a numerical comparison involving SLS and AdaSLS should appear in the main paper, this seems like a weird omission. It probably also makes sense to include the similar "painless SVRG" method.
Decision: Accept (poster)