AI-SARAH: Adaptive and Implicit Stochastic Recursive Gradient Methods
Authors: Zheng Shi
Nicolas Loizou
Peter Richtárik
Martin Takac
Venue: ICLR 2022 Submitted (2022)
Keywords: practical variant of SARAH
adaptive step-size
tune-free algorithm
implicit approach
convex optimization in machine learning

Abstract: We present AI-SARAH, a practical variant of SARAH. As a variant of SARAH, this algorithm employs the stochastic recursive gradient yet adjusts step-size based on local geometry. AI-SARAH implicitly computes step-size and efficiently estimates local Lipschitz smoothness of stochastic functions. It is fully adaptive, tune-free, straightforward to implement, and computationally efficient. We provide technical insight and intuitive illustrations on its design and convergence. We conduct extensive empirical analysis and demonstrate its strong performance compared with its classical counterparts and other state-of-the-art first-order methods in solving convex machine learning problems.

Under review as a conference paper at ICLR 2022
AI-SARAH: ADAPTIVE AND IMPLICIT STOCHASTIC RECURSIVE GRADIENT METHODS
Anonymous authors Paper under double-blind review
ABSTRACT
We present AI-SARAH, practical variant of SARAH. As variant of SARAH, this algorithm employs the stochastic recursive gradient yet adjusts step-size based on local geometry. AI-SARAH implicitly computes step-size and efficiently estimates local Lipschitz smoothness of stochastic functions. It is fully adaptive, tune-free, straightforward to implement, and computationally efficient. We provide technical insight and intuitive illustrations extensive empirical analysis and demonstrate strong performance compared with its classical counterparts and other ofate-of-the-ar first-order methods in solving convex machine learning problems.
its design and convergence. We conduct
INTRODUCTION
We consider the unconstrained finite-sum optimization problem
min [P(w) def 1. [(()] T2
This problem prevalent machine learning tasks where w corresponds to the model parameters, f((w) represents the loss on the training point i, and the goal is to minimize the average loss P(w) across the training points. In machine learning applications. ( is often considered the loss function of Empirical Risk Minimization (ERM) problems. For instance, given a classification or regression problem, ft can be defined as logistic regression or least square by (I:; y/) where x; feature representation and y; is label. Throughout the paper, we assume that each function fi,
i E [n)
def [1....,n) n), is smooth and convex, and there exists an optimal solution w" of
1.1
MAIN CONTRIBUTIONS
We propose AI-SARAIL, a practical variant of stochastic recursive gradient methods (Nguyen et al. 2017) to solve ( This practical algorithm explores and adapts to local geometry. is adaptive at full scale yet requires zero effort of tuning hyper-parameter
The extensive numerical experiments demonstrate that our tune-free and fully adaptive algorithm is capable of delivering a consistently competitive performance on various datasets, when comparing with SARAH, SARAH+ and other state-of-the-arr first-order method, all equipped with fine-tuned hyper-parameters (which are selected from & 5, 000 runs for each problem). This work provides a foundation on studying adaptivity (of stochastic recursive gradient methods) and demonstrates that truly adaptive stochastic recursive algorithm can be developed in practice.
1.2 RELATED WORK
Stochastic gradient descent (SGD) (Robbins & Monro 1951
Nemirovski & Yudin 1983 Shalev
Shwartz et al. 2007: Nemirovski et al.) 2009 Gower et al. supervised machine learning problems that have the generic form (I)
2019) is the workhorse for training
In its generic form, SGD defines the new iterate by subtracting multiple of stochastic gradient g(w.) from the current iterate wt. That is,
Wi+1 wi (wg(w))
In most algorithms, g(w) is an unbiased estimator of the gradient (i.e., a stochastic gradient), B[g(w) = V P(w), Ver E Rd. However, in several algorithms (including the ones from this paper),

---

Under review as a conference paper at ICLR 2022
g(w) could be biased estimator, and convergence guarantees can still be well obtained. Adaptive step-size selection. The main parameter to guarantee the convergence of SGD is the step-size. In recent years, several ways of selecting the step-size have been proposed. For example,
an analysis of SGD with constant step-Size (a, a) or decreasing step-Size has been proposed
in Moulines & Bach (2011); Ghadimi & Lan (2013); Needell et al. (2016); Nguyen et al. (2018);
Bottou al. (2018): Gower et (2019: 2020b under different assumptions on the properties of
problem
More recently, adaptive parameter-free methods (Duchi et al. 2011 Kingma & Ba 2015 Bengio
2013
Li & Orabonal 20188; Vaswani et al., 2019; Liu et al.] 2019a] Ward et al. 2019; Loizou et al.
2020 that adapt the step-size as the algorithms progress have become popular and are particularly
beneficial when training deep neural networks. Normally, in these algorithms, the step-size does not depend on parameters that might be unknown in practical scenarios, like the smoothness parameter or the strongly convex parameter.
Random vector g(w)) and variance reduced methods. One of the most remarkable algorithmic breakthroughs in recent years was the development variance-reduced stochastic gradient algorithms for solving finite-sum optimization problems. These algorithms, by reducing the variance of the stochastic gradients, are able to guarantee convergence to the exact solution of the optimization problem with faster convergence than classical SGD. In the past decade, many efficient variance- reduced methods have been proposed. Some popular examples of variance reduced algorithms are SAG (Schmidt et al. 2017). SAGA (Defazio et al. 2014), SVRG (Johnson & Zhang, 2013) and SARAH (Nguyen et al. 2017) 7 For more examples of variance reduced methods, see Defazio (2016); Konečny ct al. (2016); Gower al. (2020a); Khaled et al. (2020); Horväth et al.] (2020).
Among the variance reduced methods, SARAH is of our interest in this work. Like the popular SVRG, SARAH algorithm is composed of two nested loops. In each outer loop & > 1, the gradient estimate
8 = ((w)-)) is set to be the full gradient. Subsequently, in the inner loop, at t 2 1, a biased estimator n4 is used and defined recursively
Ut = (.,,), - (w: + Ut-1,
where i E [n] is a random sample selected at t.
A common characteristic of the popular variance reduced methods is that the step-size a in their update rule W++1 = W/p - am,; is constant (or diminishing with predetermined rules) and that depends on the characteristics of problem (I. An exception to this rule are the variance reduced methods with Barzilai-Bal Borweei step size, named BB-SVRG and BB-SARAH proposed in Tan et al. (2016) and Li & Giannakis (2019) respectively. These methods allow to Barzilai-Borwein size rule to update the step-size once in every epoch; for more examples, see Li et al. (2020); Yang al. (202T). There are also methods proposing approach of using local Lipschitz smoothness to derive an adaptive step-size (Liu et al. 2019b) with additional tunable parameters or leveraging BB step-size with averaging schemes to automatically determine the inner loop size (Li al. 2220)). However, these methods do not fully take advantage of the local geometry. and a truly adaptive algorithm: adjusting step-size at every (inner) iteration and eliminating need of tuning any hyper-parameters, is yet to be developed in the stochastic variance reduced framework. This is exactly the main contribution of this work, as we mentioned in previous section.
Borwein (BB) step
MOTIVATION
With our primary focus on the design of stochastic recursive algorithm with adaptive step-size, we discuss our motivation in this chapter.
A standard approach of tuning the step-size involves the painstaking grid search on a wide range of candidates. While more sophisticated methods can design a tuning plan, they often struggle for efficiency and/or require considerable amount of computing resources.
More importantly, tuning step-size requires knowledge that is not readily available at a starting point Wo E Rd, and choices of step-size could be heavily influenced by the curvature provided P2P(u)). What if a step-size has to be small due to "sharp" curvature initially, which becomes "flat" afterwards?
To this is indeed the case for many machine learning problems, let consider logistic regression for a binary classification problem, i.c., f.(w)= = log(1 + exp( (app- w)) + 3/ wl2, where x; E Rd a feature vector, y/ E -11+11 is ground truth, and the ERM problem is in the form of (1 It is
2

---

Under review as a conference paper at ICLR 2022
28:5
(a)
(b)
(d)
Figure I: AI-SARAH vs. SARAH: (a) evolution of the optimality gap P(w) and (b) the squared
norm of stochastic recursive gradient ||v AT AI-SARAH: (c) evolution of the step- size, upper-bound, local Lipschitz smoothness and (d) distribution of s; of stochastic functions. Note: in (a), is a
lower bound P(w"); ); in (c), the white spaces suggest full gradient computations outer iterations; in (d), bars represent medians of st's.
easy to derive the local curvature of P(w), defined by its Hessian in the form
V2 = E
[[+expl- w] Daa + AT.
exp( u
(1(W)
Given that (T+a) S 0.25 for any a 2 0, one can immediately obtain the global bound on Hessian, Le. Ve Rd we have P(w(w) 1 - 2 + AI. Consequently, the parameter of global Lipschitz smoothness is 1 Amax Ei= x.aef) + A. well known that, with constant step-size less than (or equal to) +. a convergence guaranteed by many algorithms.
However, suppose the algorithm starts at a random wo (or at 0 E Rd), this bound can be very tight. With more progress being made approaching optimal solution (or reducing the training error), is likely that, for many training samples, -y,2, w/ < O. An immediate implication is that sy (w)) defined in (3) becomes smaller and hence the local curvature will be smaller as well. It suggests that, although large initial step-size could lead to divergence, with more progress made by the algorithm, the parameter of local Lipschitz smoothness tends to be smaller and larger step-size can be used. That being said, such a dynamic step-size cannot be well defined in the beginning, and fully adaptive approach needs to developed.
For illustration, we present the inspiring results of an experiment on real-sim datase with f2 re-gullaaizee logistic regression. Figures [(a) and [(b) compare the performance of classical SARAH with AI-SARAH in terms of the evolution of the optimality gap and the squared norm of recursive gradient. As clear from the figure, AI-SARAH displays significantly faster convergence per effective 2
Now, us discuss why this could happen. The distribution of s; as shown in Figured [(d] indicates that: initially, all s, 's are concentrated at 0.25; the median continues to reduce within few effective passes on the training samples; eventually, stabilizes somewhere below 0.05. Correspondingly, as presented in Figure [cc] AI-SARAH starts with a conservative step-size dominated by the global Lipschitz smoothness, i.c., 1/ 1/Amax 2 P7PP(uu (ww)) (red dots); however, within effective passes, the moving average (magenta dash) and upper-boume (blue line) of the step-size start surpassing the red dots, and eventually stablize above the conservative step-size.
For classical SARAH, configure the algorithm with different values of the fixed step-size, i.e., (2-2,2-1 ...,,"...... 2²), and notice that 2 leads to a divergence. On the other hand, AI-SARAH starts with small step-size, yet achieves faster convergence per effective pass with an eventual (moving average) step-size larger than 25.
'The datasct is available datasets/
hhttps://ww.....
"The effective pass is defined complete pass on the training dataset. Each data sample is selected once per effective pass average.
3

---

Under review as a conference paper at ICLR 2022
3 ALGORITHM
We present AI-SARAH in Algorithm|| This algorithm implicitly computes a;-1 at any 2 1 through approximately solving the sub-problem, i.c., minaso {a()), and estimating the local Lipschitz smoothness of a stochastic function; the upper-bound of step-size makes the algorithm stable, and it is updated with exponential smoothing harmonic mean (of approximate solutions to the sub- problems), which also keep tracks of the local Lipschitz smoothness of a finite sum function, i.e., P(w).
This algorithm is fully adaptive and requires no efforts tuning, and can be implemented easily. Notice that 3 is treated as smoothing factor in updating the upper-bound of the step-size, and the default setting is 3 0.999. There exists one hyper-parameter
Algorithm [ 7 which defines the early stopping criterion on Line 8, and the default setting is 7 32- We will show later in this chapter that, the performance of this algorithm is not sensitive to the choices of y, and this true regardless of the problems (i.e., datasets.)
logistic regression and different
Algorithm AI-SARAH
1: Parameter: < < 1 (default 5/2) 8 0.999
2: Initialize: t6g
3: Set: amaz = 00
4: for k = 1, 2,.,.... do
5: we W6k-
6: to V ((wn)
7: t= 1
8: while ||0 11 7//00|1 do
9:
Select random mini-batch S. from [ri] uniformly with |S.] = â 1 2 arg min (()
11:
if k = 0 and f = then
12:
8% ã.-1
13:
else
8% B8 + (1 3) ac-1
15:
end if
16:
amaz
8/
17:
a1-1 = minf (ā=- Omazz
18:
Wi Wr-1 a' - 14-1
19:
V fs. (we) fs, (w;-1) + 22-1
t t+
21:
end while
22:
Set tik w/.
23:
end for
3.1 ESTIMATE LOCAL LIPSCHITZ SMOOTHNESS
In the previous chapter, we showed that AI-SARAH adapts to local Lipschitz smoothness and yields faster convergence than classical SARAH. Then, the question is how estimate the parameter of local Lipschitz smoothness in practice.
line-search? The standard approach to estimate local Lipschitz smoothness to use backtracking line-search. Recall SARAH's update rule, i.e., W; = W4-1 - where vt-1 is a stochastic recursive gradient. The standard procedure to apply line-search on function ft. (w--1- - 00. However, the main issue is that - is not necessarily a descent direction.
Can
AI-SARAH sub-problem. Define the sub-problem (as shown on line 10 of Algorithm as
min (a) min V fá, (we-1 -v V fi, (wr-1) + 11 a>0
(4)
a>0
where t 2 1 denotes an inner iteration and i; indexes random sample selected at f. We argue that, by (approximately) solving (4), we can have good estimate of the parameters of the local Lipschitz
For sake of simplicity, we fa, instead of fs.-
4

---

Under review as a conference paper at ICLR 2022
smoothness.
To illustrate this setting, we denote Lद the parameter of local Lipschitz smoothness prescribed by fú, at Wt-1- Let us focus on simple quadratic function fú, (w) = { y1,)² Let á be the optimal step-size along direction - i.e. á = arg min, fi, (1 - av;-1). Then, the closed
form solution of ā can be easily derived as ā 14-1 Uie whose value can be positive, negative, bounded or unbounded.
#1 06-1 ve-1
On the other hand, one can compute the step-size implicitly by solving and obtain af- i.c., af_ arg mina (()).. Then, we have
which is exactly and recall Lj is the parameter of local Lipschitz smoothness of Ja. Σ
Simply put, quadratic function has constant Hessian, solving 4 gives exactly z For general (strongly) convex functions, if v ( (wr-1)) does not change too much locally, we can still have a good estimate of T. by solving (4) approximately.
Based on a good estimate of Li, we can then obtain the estimate of the local Lipschitz smoothness of P(w--1). And, that is
L, = Li -
Clearly, if step-size the algorithm is selected as 1/L,, then a harmonic mean of the sequence of the step-size's computed for various component functions could serve as good adaptive upper-bound on the step-size computed in the algorithm. More details of intuition for the adaptive upper-bound can be found in Appendix A.2
3.2 COMPUTE STEP-SIZE SIZE AND UPPER-BOUNE BOUND
Line 10 of Algorithm [ the sub-problem is one-dimensional minimization problem, which can be approximately solved by Newton method. Specifically in Algorithm [ we compute one-step Newton at & 0, and that is
(0)
G
(5)
(0)
Note that, for convex function in general,
5 gives an approximate solution; for functions in particular
forms such as quadratic ones, (5) gives an exact solution.
The procedure prescribed in (5) can be implemented very efficiently, and does not require any extra (stochastic) gradient computations if compared with classical SARAH. The only extra cost per iteration is to perform two backward passes, i.e., one pass for (0) and the other for & (0); see Appendix A.2 for implementation details.
As shown on Lines 11-16 of Algorithm I. Omaa is updated at every inner iteration. Specifically, the algorithm starts without upper bound (i.e., Qmaa every t Z 1, we employs the exponential smoothing on the harmonic mean of {ār-1} to update the upper-bound. For k > 0 and 2 we define Omar
on Line 3); ãz- being computed at
ZE where
=
ôe-1"
Bot
(1 3 otherwise
and 0 3 < 1. We default / = 0.999 in Algorithm see Appendix A.2 for details on the design of adaptive upper-bound.
3.3 CHOICE OF
We perform sensitivity analysis different choices of 7. Figures shows the evolution of
the squared norm of full gradient, i.e., [W)) | for logistic regression on binary classification problems; extended results in Appendix A It is clear that the performance of y'ss where, y E {1/8, 1/16, 1 /32 , 1 1/64], is consistent with only marginal improvement by using a smaller value.
We default 7 = 1/32 in Algorithm 1
5

---

Under review as a conference paper at ICLR 2022
jjrm1
FCV1
reaksim
news20
covtype
127
13-4
10.
334
10"
13
1210
10
0077
1977
10
36"5
21
1.2.5
36"5
1.5
12
26
Effectiv
Effectivel
Effective Pank
Effeciooe
Effectiee
Figure 2: Evolution of / for {
32 16 1 regularized (top row) and non-
1
1 1
regularized (bottom row) logistic regression on jennl, revl, real-sim, news20 and covtype.
3.4 CONVERGENCE ANALYSIS
In this section, we provide a convergence analysis of AI-SARAH (Algorithm [ with i) modified line 10 to āc-1 z arg a Er(a), and ii) replacing the while loop with for loop I E [m]]. where mmin and max are step-size bounds picked each outer iteration and m be hyper-parameter.
For brevity, let just hint that for many problems (e.g., the mentioned in Chapter (2). as the solution W is approaching w" the local curvature of P(w) is getting flatter and hence a could be chosen fraction of reciprocal of smoothness parameter of f((w)'s over
WE (w E Rd || w|l S m a ( |/vall:
which can be much larger than the fraction of reciprocal of global smoothness parameter. Let us just remark that for k-th outer loop, all iterates wa will stay inside of W% and hence a is well defined. The parameter 0 < a S a be chosen arbitrary (e.g., a amax/2 or a = a We defer the technical details and proof's in Appendix B and C Let us just state the main convergence theorem here.
Theorem 3.1. Suppose that the functions fi(w) are convex and smooth with parameter I We and P is p-strongly convex. Let us define
m_aax over
o
Oray
pec (m++1)
min
2-00
F. F.maa.
and select and o such that t
< 1, vk 2 1. Then, modified Algorithm converges follows:
E V 12 (IT= ( ||VP(Wa))1
Remark: SARAH algorithm is special of the modified Algorithm when Vk: ai a 0 S 2T
4 NUMERICAL EXPERIMENT
In this chapter, we present the empirical study on the performance of AI-SARAH. For brevity, we present subset of experiments in the main paper, and defer the full experimental results and imple- mentation detail47] in Appendix A
The problems consider in the experiment are f"-regularized logistic regression for binary classifi- cation problems; see Appendix A for non-regularized case. Given a training sample (xi, y:) indexed
by E [n]. the component function fi is in the form fa(w) = log(1 + exp( -yaf w)) + 2 w|
*Code will he made available upon publication.

---

Under review as a conference paper at ICLR 2022
Table 1: Summary of Datasets from Chang & Lin (001))
Dataset
# features
(# Train)
# Test
% Sparsity
ijennl'
22
49,990
91,701
40.91
rcvl'
47,236
20,242
677,399
99.85
real-sim?
20,958
54,231
18,078
99.76
news20"
1,355,191
14,997
4,999
99.97
covtype"
54
435,759
145,253
77.88
dataset has default training/testing sanples.
2 dataset is randomly split by 75%-training & 25%--testing.
where A = for the (2 (e-reulaarized case and À = for the non-regularized case.
The datasets chosen for the experiments are ijemnl, revl, real-sim, news20 and covtype. Table Table shows the basic statistics of the datasets. More details and additional datasets can be found in Appendix [A]
We compare AI-SARAH with SARAH, SARAH+. SVRG (Johnson & Zhang 2013). (013).ADO ADAM (Kingma & Ba 2013) and SGD with Momentum (Sutskever et 2013) Loizou & Richtárik [020 2017).
While RAH does not require
tuning, we fine-tune each of the other al- gorithms, which yields x 5, 000 runs in total for each dataset and case.
(1) ADAM and SGD with Momentum (SGD) w/m) are tuned with different values of the (initial) step-size and schedules to reduce the step-size; (2) SARAH and SVRG are tuned with different values of the (constant) step-size and inner loop size; (3) SARAH+ is tuned with different values of the (constant) step-size and early stopping parameter. (See Appendix A for detailed tuning plan and the selected tlyee-paraaeters, Figure 3 shows the average and total wall clock running time of AI-SARAH and the other algorithms. While any individual run of AI-SARAH could be 2-5x more time consuming than the other algorithms, its running time is negligible if comparing the total wall clock time. The reason is that AI-SARAH does not not require any tuning effort, but we have 2 5, 000 runs to fine-tune the other algorithms. Figure 4sshws the minimum P( 2 achieved at a few points of effective passes and wall clock time horizon. It clear that, AI-SARAH's practical speed of convergence faster than the other algorithms in most cases. Here, we argue that, if given an optimal implementation of AI-SARAH (just as that of ADAM and other built-in optimizer Pytorct D. it is likely that our algorithm can be accelerated. By selecting the fine-tuned prrrr--arameters of all other algorithms, we compare them with A/- For these experiments, we use 10 distinct random seeds
To be specific, we perform an extensive search on
SARAH and show the results in Figures 5 7 to initialize w and generate stochastic mini-batches. And, we use the marked dashes to represent the average and filled areas for 97% confidence intervals.
Figure presents the evolution of P(w)) Obviously from the figure, AI-SARAH exhibits the strongest performance in terms of converging to a stationary point: by effective pass, the consis- tently large gaps are displayed between AI-SARAH and the rest; by wall clock time, we notice that AI-SARAH achieves the smallest P at the same time point. This validates our design, that is to leverage local Lipschitz smoothness and achieve a faster convergence than SARAH and SARAH+.
In terms of minimizing the finite-sum functions, Figure showos that, by effective pass, AI-SARAH consistently outperforms SARAH and SARAH+ on all of the datasets with possible exception on covtype dataset. By wall clock time, AI-SARAH yields a competitive performance on all of the datasets, and delivers a stronger performance on ijenn/ and real-sim than SARAH.
For completeness of illustration on the performance, we show the testing accuracy in Figure 7 Clearly, fine-tuned ADAM dominates the competition. However, AI-SARAH outperforms the other variance reduced methods on most of the datasets from both effective pass and wall clock time perspectives, and achieves the similar levels of accuracy as ADAM does on rcvl, real-sim and covtype datasets.
Having illustrated the strong performance of AI-SARAH, we continue the presentation by showing the trajectories of the adaptive step-size and upper-bound in Figure g
This figure clearly shows that why AI-SARAH the convergence to a stationary point. As mentioned in previous chapters, the adaptivity is driven by the local Lipschitz smoothness. As shown in Figure AI-SARAHI starts with conservative step-size and upper-bound, both of which continue to increase while the algorithm progresses towards a stationary point. After a few effective passes, we observe; the step-size and upper-bound are stablized
achieve such strong performance, especially on
Please see htchhttpss///ttttoc.orrgg//////
stabl e/ cooppiim... html for Pytorch huilt-in optimizers.
7

---

Under review as a conference paper at ICLR 2022
AI-ARAH
SARAH
SARAH+
SVAG
Adam
SGD w/m
[cnn1
real-sim
news20
639
100
289
141
Tolel Caek (oed)
Agonthm
AlgorArum
Algonifm
Algerizu
Algorthm
Figure 3: Average (top row) and total (bottom row) running time of Al-SARAII and other algorithms for the regularized case.
AI-SARAH
SARAH
SARAH+
SVRG
Adam
SGD w/m
ijcnn1
real-sim
news20
Effective Paus
Effediive Pass
Effective Pass
Effective Pass
Effective Pass
10
35.0
133.0
3C.8
15.0
240 $35.0
Wall Clock (sec)
Wall Clock (sec)
Wall Clock (Sa))
Wall Clock (sad)
Wall Clock (sec)
Figure 4: Running minimum per effective pass (top row) and wall clock time (bottom row) of P(w))l between other algorithms with all haper--ppammee parameters configurations and AI-SARAH for the regularized case. Note: the horizontal dashes in blue represent the minimum PPw))] achieved by AI-SARAH at certain effective pass or time point.
AI-AHRAH
SARAH
- SARAH+
SVRG
- Adam
SGD wim
ijonn1
real-sim
news20
covtype
20-1
201
20
10-1
10
5g
15
Pacss
Pans
Paox
Effective Pass
3014
20.2
1077
33
10:1-
[0Pool]
20
12
10th
10"
20
12
10
12
1/6
125
206
3000
Clock (sec)
Vill (vwe)
(we))
(sec)
Figure 5: Evolution of P|w)( for the regularized case by effective pass (top row) and wall clock time (bottom row).
8

---

Under review as a conference paper at ICLR 2022
NI-SARHH
SARAH
-A-
SARAH+
+ SVRG
-
Adam
5GD whn
Jinn1
rcvI
real.sim
news20
covtype
4.20
6.2
9.24
9.8
0.2
9.2
3.25
0.18
6500
Effective Pass
Effecitre Pass
Efectiva Pass
Bllectvve Pass
Effective Pass
6.2
0315
624
C15
035
E23
10
66
32
120
230 600 an
Dock (sac)
Will Clock (sec]
Wall Cock (snc)
(sec]
Cloce (sac)
Figure 6: Evolution of P(w) for the regularized case by effective pass (top row) and wall clock time (bottom row).
AI-ARRAH
SARAH
SARAH+
SVAG
Adam
SGD w/m
jennn
coxtype
0.85
0915
0.0
EM
082
0.9
Effective Pa55
Effective Pass
Effectiv Pass
Effective Pass
Effectiv
8.05
0.7
0.35
8213
0.5%
0.1
0.3
0.2
293
0.72
126
45
182
125
200 40
6/0
19t0
Clock (pec)
(26c)
Wel Cookk Soc1
Wall Clock Sccc
(ock
Figure 7: Running maximum of testing accuracy for the regularized case by effective pass (top row) and wall clock time (bottom row).
[|cnn]
real-sim
Prw
20
Effective Pays
Effective Paiss
Effective Pays
Effective
Effective Pass
Figure 8: Evolution of AI-SARAIL's step-size a and upper-bound Omar for the regularized case.
due to À (and hence strong convexity). In Appendix A we can see that, as result of the function being unregularized, the step-size and upper-bound could be continuously increasing due to the fact that the function is likely non-strongly convex.
5 CONCLUSION
In this paper, propose AI-SARAH,, practical variant of stochastic recursive gradient methods. The idea of design simple yet powerful: by taking advantage of local Lipschitz smoothness, the step-size be dynamically determined. With intuitive illustration and implementation details, we show how AI-SARAH can efficiently estimate local Lipschitz smoothness and how it can be easily implemented in practice. Our algorithm is fune-free and adaptive at full scale. With extensive numerical experiment, we demonstrate that, without (tuning) any hyper-parameters, it delivers competitive performance compared with SARAH(+), ADAM and other first-order methods, all equipped with fine-tuned parametrrss...s...

---

Under review as a conference paper at ICLR 2022
ETHICS STATEMENT
This work presents a new algorithm for training machine learning models. We do not foresee any ethical concerns. All datasets used in this work are from the public domain and are commonly used benchmarks in ML papers.
REPRODUCIBILITY STATEMENT
We uploaded all the codes used to make all the experiments presented in this paper. We have used random seeds ensure that one can start optimizing the ML models from the same initial starting point was used in the experiments. We have used only datasets that are in the public domain. and one can download them from the following website https: //www//wwwwwo csie ntu. edu. tw/ hcjlin/11 bsvmt oo I s dataset.s/ After acceptance, we will include link to the GitHub repository where we will host the source codes.
10

---

Under review as a conference paper at ICLR 2022
REFERENCES
Yoshua Bengio. Rmsprop and equilibrated adaptive learning rates for nonconvex optimization. corr 05s/1502.04390,, 2015.
Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223- -1121, 2018.
Chih-Chung Chang and Chih-Jen Lin. Libsvm: a library for support vector machines. ACM transactions intelligent systems and technology (TIST),
A. Defazio. A simple practical accelerated method for finite sums. In NewrIPS, 2016.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. In Advances in Neural Information Processing Systems, volume 27, pp. 1646-1654. Curran Associates, Inc., 2014.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(uul):221-21111 2011.
Saced Ghadimi and Guanghui Lan. Stochastic first-and zeroth methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2366 2013.
Robert M Gower, Peter Richtárik, and Francis Bach. Stochastic quasi-gradient methods: Variance
reduction via jacobian sketching. Mathematical Programming, pp. 1-58, 2020a.
Robert M Gower, Othmane Sebbouh, and Nicolas Loizou. Sgd for structured nonconvex functions: Learning rates, minibatching and interpolation. arXiv preprint arXiv:2006. 103/1, 2020b.
Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. Sgd: General analysis and improved rates. In International Conference Machine Learning, pp. 5200-5209, 2019.
Samuel Horváth, Lihua Lei, Peter Richtárik, and Michael I. Jordan. Adaptivity of stochastic gradient methods for nonconvex optimization. arXiv preprint arXiv:2002.05359, 2020.
Rie Johnson and Tong Zhang. Accelcrating stochastic gradient descent using predictive variance reduction. Advances Neural Information Processing Systems, volume 26, pp. 315-323, Curran Associates, Inc., 2013.
Ahmed Khaled, Othmane Sebbouh, Nicolas Loizou, Robert M. Gower, and Peter Richtárik. Unified analysis of stochastic gradient methods for composite convex and smooth optimization. arXiv preprint wwXiv:2006.1557. 2020.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
J. Konečny, J. Liu, P. Richtárik, and M. Takáč, Mini-batch semi-stochastic gradient descent in the proximal setting. IEEE Journal of Selected Topics Signal Processing, 10(2):242 255-25,, 2016.
Bingcong Li and Georgios B Giannakis. Adaptive step sizes in variance reduction via regularization. arXiv preprint arXiv:1910.06332. 2019.
Bingcong Li, Lingda Wang, and Georgios B. Giannakis. Almost tune-free variance reduction. In Proceedings the 37th International Conference Machine Learning, volume 119, pp. 5969-5978 PMLR, 2020.
Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. arXiv preprint 1rXiv:1805.08/ 14, 2018.
Liyuan Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han. On the variance of the adaptive learning rate and beyond. arXiv preprint 190..03235 2019a.
Yan Liu, Congying Han, and Tiande Huo. A class of stochastic variance reduced methods with an adaptive stepsize. 2019b. URL hollattp/// www. opt wwwiatiiiiiii...i on mininn.... FILE// 201 9/04 33704/7170..dff

---

Under review as a conference paper at ICLR 2022
Nicolas Loizou and Peter Richtárik. Linearly convergent stochastic heavy ball method for minimizing generalization error. arXiv preprint arXiv:1710.10733 2017.
Nicolas Loizou and Peter Richtárik. Momentum and stochastic momentum for stochastic gradi- ent, newton, proximal point and subspace descent methods. Computational Optimization and Applications, 77(3):633-710, 2020.
Nicolas Loizou, Sharan Vaswani, Issam Laradji, and Simon Lacoste-Julien. Stochastic polyak step- size for sgd: An adaptive learning rate for fast convergence. arXiv preprint 10554 2020.
Eric Moulines and Francis R Bach. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. Advances in Neural Information Processing Systems, pp. 451-459, 2011
D. Needell, N. Srebro, and R. Ward, Stochastic gradient descent, weighted sampling, and the randomized kaczmarz algorithm. Mathematical Programming, Series A, 155(1):549-577, 2016.
Arkadi Nemirovski and David B. Yudin. Problem complexity and method efficiency in optimization. Wiley Interscience, 1983.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4):1574- 1609, 2009.
Yurii Nesterov. Introductory lectures convex optimization: A basic course, volume 87. Springer Science & Business Media, 2003.
Lam Nguyen, Phuong Ha Nguyen, Marten van Dijk, Peter Richtárik, Katya Scheinberg, and Martin Takác. SGD and hogwild! Convergence without the bounded gradients assumption. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 3750-3758. PMLR, 2018.
Lam M. Nguyen, Jie Liu, Katya Scheinberg. and Martin Takáč. Sarah: A novel method for machine learning problems using stochastic recursive gradient. In Proceedings of the 34th International Con- ference on Machine Learning (ICML 2000), volume 70, pp. 2613-2621, International Convention Centre, Sydney, Australia, 2017. PMLR.
H. Robbins and S. Monro. A stochastic approximation method. The Annals of Mathematical Statistics, pp. 400-407, 1951.
M. Schmidt, N. Le Roux, and F. Bach. Minimizing finite sums with the stochastic average gradient. Math. Program.. 162(1-2):33-1 2017.
Shai Shalev-Shward Shwartz, Yoram Singer, and Nathan Srebro. Pegasos: primal estimated subgradient solver for SVM. In 24th International Conference on Machine Learning, pp. 807-814, 2007.
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. In International conference on machine learning, pp. 1139-1147. PMLR, 2013.
Conghui Tan, Shiqian Ma, Yu-Hong Dai, and Yuqiu Qian. Barzilai-borwein step size for stochastic gradient descent. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pp. 685-693, 2016.
Sharan Vaswani, Aaron Mishkin. Issam Laradji, Mark Schmidt, Gauthier Gidel, and Simon Lacoste- Julien. Painless stochastic gradient: Interpolation, line-search, and convergence rates. In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché- -uue E. Fox, and R. Garnett (eds.), Advances Neural Information Processing Systems, volume 32, pp.
Curran Associates, Inc., 2019.
Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence nonconvex landscapes. In International Conference on Machine Learning, pp. 6677-6686, 2019.
Zhuang Yang, Zengping Chen, and Cheng Wang. Accelerating mini-batch sarah by step size rules. Information Sciences, 2021. ISSN 0020-0255. doi: https///doi.org11.000///// 2020. 12.075.
12

---

Under review as a conference paper at ICLR 2022
APPENDIX
The Appendix is organized as follows. In Chapter implementation and results of our numerical experiments. In Chapter B we present the theoretical analysis of AI-SARAH. In Chapter [ we provide the basic definitions, some existing technical preliminaries that are used in our results, and the proofs of the main lemmas and theorems from Chapter
present extended details the design,
A EXTENDED DETAILS ON NUMERICAL EXPERIMENT
In this chapter, present the extended details of the design, implementation and results of the numerical experiments.
A.1 PROBLEM AND DATA
The machine learning tasks studied in the experiment are binary classification problems. As common practice in the empirical research of optimization algorithmss, the LIBSVM datasets are chosen to define the tasks. Specifically, we selected 10 popular binary class datasets: ijennl, rev1, news20, covtype, real-sim, ala, gisette, wla, w8a and mushrooms (see Table 2 for basic statistics of the datasets).
Table Summary Datasets.
Dataset
1 (# feature)
(# Train)
Nest Test)
% Sparsity
ijennl'
22
49,990
91,701
40.91
revl
47,236
20,242
677.399
99.85
news20
1,355,191
14,997
4,999
99.97
covtype"
54
435,759
145,253
77.88
real-sim"
20,958
54,231
18,078
99.76
ala
123
1,605
30,956
88.73
gisette
5,000
6,000
1,000
0.85
wla'
300
2,477
47,272
96.
w8a'
300
49,749
14,951
96. 12
mushrooms"
112
6,093
2,031
81.25
dataset has default training/testing samples. dataset randomly split by 75%--triinng 25%--estingg
A.1.1 DATA PRE-PROCESSIIG
Let (X;, yi) be training (or testing) sample indexed by i [m]] (or E (Meest), where X; Rd-1 a feature vector and yi a label. We pre-processed the data such that X; is of a unit length in Euclidean norm and y E {-1,+1).
A.1.2 MODEL AND LOss FUNCTION
The selected model, h; Rd + R, is in the linear form
he(w,e) XT + Wi E [n].
where w E Rd-1 is weight vector and E R is bias term.
For simplicity of notation, from now on, we let [x 11TH E Rd be an augmented feature vector, def
w wTT =|T E Rd be parameter vector, and h2 (w) = x w for i E [n].
1.IBVV datasets are available at httpss://///t. wwtp://wwwwwo/ www.wccie....... csie. ntv w.ttu.edu.com www.ww/wwww.... ttt bavntooll col httpps//www.ciiii.
/atasets/
13

---

Under review as a conference paper at ICLR 2022
Given training sample indexed by E [nx], the loss function is defined as logistic regression
[ww)) log(1 (1 exp(-y;hh(ww) X |00l
In (8 |||| is the l reregularization of partieular choice of À > O, where used À == 1 in the experiment: for the non-regularized case, À was set to O. Accordingly, the finite-sum minimization problem we aimed solve is defined
min wER
{ P(w)
del
1 NV
Σ
Note that 9 is a convex function. For the e-regularized case, i.c. == 1/n in 88, is ju-strongyy convex and μ n' and only there there exists μ > such that P(w(() ž pl for w E Rd (provided V E C).
2. However, without the X, i..., = in 8). is ju-strongly convex
A.2 ALGORITIMS
This section provides the implementation details" of the algorithms, practical consideration, and discussions.
A.2.1 TUNE-FREE AI-SARAH
In Chapter 3 of the main paper, we introduced AI-SARAH, a tune-free and fully adaptive algo- rithm. The implementation of Algorithm 1 was quite straightforward, and we highlight the implementation of Line 10 with details: for logistic regression, the one-dimensional (constrained optimization) sub-problem min. (a(a) can be approximately solved by computing the Newton (0)
step at a = 0, i.e., 0 = [0]] This can be easily implemented with automatic differentiation in
Pytoret 8 and only two additional backward passes w.r. a needed. For function in some particular form, such as linear least square loss function, an exact solution in closed form can be easily derived.
As mentioned in Chapter 3, we have an adaptive upper-bound, i.e., Omaz in the algorithm. To be specific, the algorithm starts without upper-bound, i.e., Omaa x on Line of Algorithm [ Then, Qmes is updated per (inner) iteration. Recall in Chapter 3 Orma computed as harmonic mean of the sequence, i.e., {āt-1}, and an exponential smoothing is applied on top of the simple harmonic mean.
Having upper-bound stabilizes the algorithm from stochastic optimization perspective. For example, when the training eиror of the randomly selected mini-batch at w; is drastically reduced approaching zero, the one-step Newton solution in (5) could be very large, i.e. 6z-1 > 0, which could be too aggressive to other mini-batch and hence Problem (T) prescribed by the batch. On the other hand, making the upper-bound adaptive allows the algorithm to adapt to the local geometry and avoid restrictions on using large step-size when the algorithm tries to make aggressive progress with respect to Problem (T). With the adaptive upper-bound bound being derived by an exponential smoothing of the harmonic mean, the step-size is determined by emphasizing the current estimate of local geometry while taking into account the history of the estimates. The exponential smoothing further stabilizes the algorithm by balancing the trade-off of being locally focused (with respect to fs,) and globally focused (with respect to P).
It is worthwhile to mention that Algorithm [ does not require computing extra gradient of fs, with respect to w if compared with SARAH and SARAHI+ At each inner iteration, / > 1, Algorithm computees V.s, (W;-1 -r 1)) with 0 just as SARAH and SARAH/ would compute fss. (w,-1). .)..2..))..... and the only difference is that a is specified as a variable in Pytorch. After the adaptive step-size 0t-1 is determined (Line 17), Algorithm I computes fss, (w,-1 at-12(-1) 1) just as
SARAH and SARAH+ would compute V (wx).
In Chapter of the main paper, we discussed the sensitivity of Algorithm on the choice of y- Here, we present the full results (on 10 chosen datasets for both -regullarized and non-regularized
7 "oode will he made available upon publication.
'For detailed description of the automatic diffcrentiation engine in Pytorch, please see httphh:///ttt///// html]
al htwpa//wwa........eeeee/////////
14

---

Under review as a conference paper at ICLR 2022
real-sim
covtyge
1/44
030
040
Prio
27
348
340
EflectrePa Posa
Elecieed Nos
Stoccea Taxa
Effectiv Piss
Ehaciiv Nas
Figure 9: 1 erreullarized case ijennl, rcvl, real-sim, news20 and covtype with E 1
( 32: 7: ) evolution of P(w) (top row) and [V (middle row) and running maxi- mum of testing accuracy (bottom row).
0.5
3.0
044
0.87
1844
12 14
Taxo
Electio
Bluctivd
Figure 10: P-regularized case of ala. gisette, wla, w8a and mushrooms with 7 I 1 1]: evolution of P(w) (top row) and /V (middle row) and running maxi- 664: 32: 16: 4: 2
mum of testing accuracy (bottom row).
cases) in Figures 10 11 and 12 Note that, in this experiment, we chose 64 32 16 4: 2 and for each y, dataset and case, we used distinct random seeds and ran each experiment for 20 effective passes.
11
A.2.2 OTHER ALGORITHMS
In our numerical experiment, we compared the performance of TUNE-FREE AI-SARAH (Algorithm with that of 5 FINE-TUNED state-of-the-art (stochastic variance reduced or adaptive) first-order
15

---

Under review as a conference paper at ICLR 2022
160
PWO)
0.20
3044
0.55
0.0
Eftectin
Eftectiee
SPlrrtue PACE
Eftectve
Effectu PAVt
Figure 11: Non-regularized case ijennl, revl, real-sim, news20 and covtype with y E ( 32: To: & 2. 2: evolution of P(w) (top row) and [VP(w)]l (middle row) and running maxi- mum of testing accuracy (bottom row).
WSB
0.6
1/4
105
04
040
201
1131
04
Sttectin Fact
Pare
Figure 12: Non-regularized case ala, gisette, wla, w8a and mushrooms with y 1.
(T 32: 16 4:2:: evolution of Pww) (top row) and /V (middle row) and running maxi-
mum of testing accuracy (bottom row).
16

---

Under review as a conference paper at ICLR 2022
Table 3: Tuning Plan Choice of Hyper-paramettes..
Method Configuration
Step-Size
Schedule (%))
Inner Loop Size Effective Pass)
Early Stopping (t)
SARAH
160
(0.1. 0.2.....
1
(0.5, 0.......
SARAH+
50
00.1. 0.2.
17/
D/a
W/a [0.5, 0.6,
1/ 4, 8, 16, 32)
SVRG
160
[0.1, 0.2, 13/h
D/
n/a
ADAM
300
10 10
10. L,
10, 15)
n/a
n/a
SGD w/m'
300
10 10)
{0, 1,5, 10, 15)
n/a
m/a
Step-size scheduled decrease by X% every effective pass over the training samples.
31 = 0.9, 82 0.999.
3 = 0.9.
Table 4: Running Budget (# Effective Pass).
Dataset
Regularized Non-regularized
ijonnl
20
20
rcvl
30
40
news20
40
50
covtype
20
20
real-sim
20
30
ala
30
40
gisette
30
40
wla
40
50
w&a
30
40
mushrooms
30
40
methods: SARAH, SARAH+, SVRG, ADAM and SGD with Momentum (SGD w/m). These algorithms were implemented in Pytorch, where ADAM and SGD w/m are built-in optimizers of Pytorch.
Hyper-parameter tuning. For ADAM and SGD w/m, we selected 60 different values of the (initial) step-size on the interval [10-3 10] and different schedules decrease the step-size after every effective pass on the training samples; for SARAH and SVRG, we selected 10 different values of the (constant) siep and 16 different values the inner loop size; for SARAH+, the values of step-size were selected in the same way as that of SARAH and SVRG. In addition, chose 5 different values of the inner loop early stopping parameter. Table presents the detailed tuning plan for these algorithms.
Selection criteria:
We defined the best hyper-pane paremeearsesers the ones yielding the minimum ending value of the loss function, where the rumning budget is presented Table Specifically, the criteria are: (1) filtering out the ones exhibited "spike" of the loss function, i.e., the initial value of the loss function is surpassed at any point within the budget; (2) selecting the ones achieved the minimum ending value of the loss function.
Hightlights of the hyper-parameter search:
To take into account the randomness in the performance of these algorithms provided different hyper-parameters, we ran each configuration with distinct random seeds. The total number of runs for each dataset and case is 4, 850.
T and 6 present the best hyper-parameters selected from the candidates for the regularized and non-regularized cases.
14] 15 and [6 show the performance of different hyper-parametent for all tuned algorithms: is clearly that, the performance is highly dependent on the choices of hyper- parameter for SARAH, SARAH++ and SVRG. And, the performance of ADAM and SGD w/m are very SENSITIVE to the choices of hyper-parameter.
Figures 13
Global Lipsehitz smoothness of P(w). Tuning the (constant) step-size SARAH. SARAH+ and SVRG requires the parameter of (global) Lipschitz smoothness of P(w), denoted the (global) Lipschitz
17

---

Under review as a conference paper at ICLR 2022
Table 5: Fine-tuned Hyper-parameters - -regularized Case.
Dataset
ADAM
SGD w/m
SARAM
SARAII+
SVRG
(og, x%)
(okg, x%)
(a,, m)
(a, 7)
(a,m) ml
ijonnl
(0.07, 15%)
(0.4, 15%)
(3.153, 1015)
(3.503, 1/32)
(3,503, 1562)
rcvl
(0.016, 10%)
(4.857, 10%)
(3.924, 600)
(3,924, 1/32)
(3.924, 632)
news20
(0.028, 15%)
(6.142, 10%)
(3.786, 468)
(3.786, 1/32)
(3.786, 468)
covtype
(0.07, 15%)
(0.4, 15%)
(2.447, 13616)
(2.447, 1/32)
(2.447, 13616)
real-sim
(0.16, 15%)
(7.428, 15%)
(3.165, 762)
(3.957, 1/32)
(3.957, 1694)
ala
(0.7, 15%)
(4.214, 15%)
(2.758, 50)
(2.758, 1/32)
(2.758, 50)
gisette
(0.028, 15%)
(8.714, 10%)
(2.320, 186)
(2.320, 1/16)
(2.320, 186)
wla
(0.1, 10%)
(3.571, 10%)
(3.646, 60)
(3.646, 1/32)
(3.646, 76)
wdu
(0.034, 15%)
(2.285, 15%)
(2.187, 543)
(3.645, 1/32)
(3.645, 1554)
mushrooms
(0.220, 15%)
(3,571, 0%)
(2.682, 190)
(2.682, 1/32)
(2.682, 190)
Table 6: Fine-tuned Slyper-parametery. Non- Non-regularized Case.
Dataset
ADAM
SGD w/m
SARAH
SARAII+
SVRG
(0ig x%)
(og, x%)
(a, m)
(a, ())
(a, m)
ijennl
(0.1, 15%)
(0.58, 15%)
(3.153, 1015)
(3.503, 1/32)
(3.503, 1562)
rcvl
(5.5, 10%)
(10.0, 0%)
(3.925, 632)
(3.925, 1/32)
(3.925, 632)
news20
(1.642, 10%)
(10.0, 0%)
(3.787, 468)
(3.787, 1/32)
(3.787, 468)
covtype
(0.16, 15%)
(2.2857, 15%)
(2.447, 13616)
(2.447, 1/32)
(2.447, 13616)
real-sim
(2.928, 15%)
(10.0, 0%)
(3.957, 1609)
(3.957, 1/16)
(3,957, 1694)
ala
(1.642, 15%)
(6.785, 1%)
(2.763, 50)
(2.763, 1/32)
(2.763, 50)
gisette
(2.285, 1%)
(10.0, 0%)
(2.321, 186)
(2.321, 1/32)
(2.321, 186)
wla
(8.714, 10%)
(10.0, 0%)
(3.652, 76)
(3.652, 1/32)
(3.652, 76)
w8a
(0.16, 10%)
(10.0, 5%)
(2.552, 543)
(3.645, 1/32)
(3.645, 1554)
mushrooms
(10.0, 0%)
(10.0, 0%)
(2.683, 190)
(2.683, 1/32)
(2.683, 190)
[cnn]
rov3
real-sim
news20
cavtype
Plat
24
12"1
16-1
234
10-1
26-4
19.
2E-
E530
0.90
0.90
0.50
2530
0.75
158
0.20
$20
SHOAI
SAMDA
9M0
DMG
Figure 13: Ending loss (top row), ending squared norm of full gradient (middle row), maximum testing accuracy (bottom row) of different hyper- paramters and algorithms for the eegreullrrieed case ijennl, rcv real-sim, news20 and covtype datasets.
18

---

Under review as a conference paper at ICLR 2022
gisette
w1a
mushroems
1.0
04
36-4
8.57
Accursa
8553
08725
05710
8492
CANYYe
Adm
SX90
560M
XM0
500
Figure 14: Ending loss (top row), ending squared norm full gradient (middle row), maximum
testing accuracy (bottom row) of different crper-paramtert and algorithms for the e-reulaarized case on ala, gisette, wla, w8a and mushrooms datasets.
[cnn]
neW520
1.75
1.29
Plw)
0.7%
30
16-1
23-
10
8.14
0.20
5000
500 am
CANUI
CAMP
200G
Figure 15: Ending loss (top row), ending squared norm full gradient (middle row), maximum
testing accuracy (bottom row) of different hyper-pann paramters and algorithms for the non-regularized case on ijennl, rcv real-sim, news20 and covtype datasets.
19

---

Under review as a conference paper at ICLR 2022
mushroorre
12
PtM
18-1
12-11
18-1
10
39.1
8:182
8.99
0.985
8822
6.96
3390
0.94
3375
6/9
3839
0.00
6379
cate
009214
50001
Adbr
SUAG
Abee
523
$20
530
550
Figure 16: Ending loss (top row), ending squared norm full gradient (middle row), maximum
testing accuracy (bottom row) of different case on ala, gisette, wla, w8a and mushrooms datasets.
and algorithms for the non-regularized
Table 7: Global Lipschitz Constant L
Dataset
Regularized
Non-regularized
ijennl
0.285408
0.285388
revl
0.254812
0,254763
news20
0.264119
0.264052
covtype
0.408527
0.408525
real-sim
0.252693
0,252675
ala
0.362456
0.361833
gisetle
0.430994
0.430827
wla
0.274215
0.273811
w&a 0.274301
0.274281
mushrooms
0.372816
0.372652
constant and it can be computed as, given 8 and (
L Amar
x +
where Xmaz (A) denotes the largest eigenvalue of A and À is the penalty term of the -eregularization in (8). Table 7 shows the values of L for the regularized and non-regularized cases on the chosen datasets.
20

---

Under review as a conference paper at ICLR 2022
SENO.20
Codlye
32"
13
6/x
<Bs
12
Perzanda
Perarita
Percertl
Percentl
Parert
Figure 17: Average ending P(w)]] for e-regularized case AI-SARAH vs. Other Algorithms: AI-SARAH shown as the horizontal lines: for each of the other algorithms, the average ending P(w)ll from different configurations of pypper-arramterr are indexed from 0 percentile (the worst choice) to 100 percentile (the best choice); see Section A.2.2 for details of the selection criteria.
Percatde
Parorii
Parerdo
Pararii
Pererd
ala
w13
6Bs
12
PrrCeedA
Peroreda
Prrcerate
Figure 18: Average ending P(w)l1 for non-regularized case AI-SARAH vs. Other Algorithms.
A.3 EXTENDED RESULTS OF EXPERIMENT
In Chapter 4 we compared tune-free & fully adaptive AI-SARAH (Algorithm I with fine-tuned SARAH, SARAH++ SVRG, ADAM and SGD w/m. In this section, we present the extended results of empirical study on the performance of AI-SARAH.
Figures 17 and 18 compare the average ending //> achieved by AI-SARAH with the other algorithms, contigured with all candidate hyper- parameters.
is clear that,
without tuning, AI-SARAH achieves the best convergence (to a stationary point) in practice on most of the datasets for both cases;
while fine-tuned ADAM achieves better result for the non-regularized case on ala, gisette, wla and mushrooms, AI-SARAH outperforms ADAM for at least 80% (ala), 55% (gisette), 50% (wla), and 50% (mushrooms)) of all candidate sereee-pramettrs.
Figure 19 shows the results of the non-regularized case for ijennl, rev1, real-sim, news20 and covtype datasets. Figures 20 and 21 present the results of the reguulrard case and non-regularized case respectively on ala, gisette, wla, w&a and mushrooms datasets. For completeness of presentation, we present the evolution of AI-SARAII's step-size and boper-bound on ala, gisette, wla, w&a and mushrooms datasets in Figures 22 and 23 Consistent with the results shown in Chapter 4 of the main paper, AI-SARAH delivers competitive performance in practice.
21

---

Under review as a conference paper at ICLR 2022
covtype
2.7
SNAKTs
tets
222
030
209
Offective
Pass
Choccivv Faxs
Effective Pans
Pam
[jnnn1
rovl
real-sim
news20
coviype
SAPAA
15"
2
Ijann1
realksim
costype
0.58
6:45
6940-
A4 NOOO
0412
2-60
8:22
Dioccton Pars
Offecivee 7ass
Difective Pass
Cfacche 7ass
Dtrective Pass
Figure 19: Non-regularized case: evolution of P(w) (top row), PWw)]]] (middle row), and running maximum of testing accuracy (bottom row).
gisette
w8a
mushrromm
0.20
246
SIAHH
3.14
238
812
031-
5.1
10.1
16.
127
3.19
5.00
230
5.0
Figure 20: e-regularized case: evolution of P(w) (top row), || VP(w)]1 (middle row), and running
maximum of testing accuracy (bottom row).
22

---

Under review as a conference paper at ICLR 2022
gisttte
mushrooms
6471
GLSANAN
SCD
0603
0.35
680
11"
0.98
30
0.9
25
Figure 21: Non-regularized case: evolution of P(w) (toprow), /|WP(1)] (middle row), and running
maximum of testing accuracy (bottom row).
mushroams
140
20
22
30
46
Effective
Eflective Pass
Effective Park
Effective
Effective Pass
Figure 22: e-regularized case: evolution of AI-SARAH''s step-size a and upper-bound Omann
ala
gisette
wla
wBa
mushrooms
209
235
102
330
Figure 23: Non-regularized case: evolution of AI-SARAHT' step-size a and upper-bound Omaz.
23

---

Under review as a conference paper at ICLR 2022
B THEORETICAL ANALYSIS
In this chapter, we provide a convergence analysis of AI-SARAH (Algorithm I with a i) modified line 10 to 0;-1 = arg ae " ((()), and ii) replacing the while loop with for loop t E [m], where amin and amax are step-size bounds picked in each outer iteration and m be hyper-parameter.
B.1 AI-SARAH AND SARAH
Like SVRG and SARAH, AI-SARAH's loop structure of this algorithm is divided into the outer loop, where a full gradient is computed, and the inner loop, where only stochastic gradient is computed. However, unlike SVRG and SARAH, the step-size is computed implicitly. In particular, at each iteration t E [m] of the inner loop, the step-size is chosen by approximately solving a simple one- dimensional constrained optimization problem. Define the (modified) sub-problem (optimization problem) at t as
min ac (n min 1 max
Ec(a),
(10)
an 1) Vss, (we-1) 1) 1- o and a are lower- where (a == ||0]|1 I[V (w (w+-1
bound and upper-bound of the step-size respectively. These bounds do allow large fluctuations of the (adaptive) step-size. We denote at-1 the approximate solution of (10). Now, let us present some remarks regarding AI-SARAH.
Remark B.1. As will explain with more details in the following subsections, the values of a and a cannot be arbitrarily large. To guarantee convergence, will need to assume that a.k Omax S T.mas, where L maxte[n] Li: Here, Li is the local smoothness parameter of fi defined on working-ser for each outer loop (see Definition B.6
Remark B.2. SARAH Nguyen et al. (2017) can be seen as special case of AI-SARAH, where a minn o for all outer loops (k 1). In other words, constant step-size is chosen for the algorithm. However, a o then the selection of the step-size in AI-SARAH allows faster convergence of [|w]]] than SARAH in each inner loop.
Remark B.3. Art 2 1, let us select mini-batch of size n, i.e., |Sp] equivalent to deterministic gradient descent with very particular way of selecting the step-size, i.e. by solving the following problem
n. In this case, AI-SARAH
min Ee(ar,
where (: = /VV (w,-1- aV ((w,-) II?. In other words, the step-size is selected to minimize the squared norm of the full gradient with respect to wt.
B.2 DEFINITIONS / ASSUMPTIONS
First, we present the main definitions and assumptions that are used our convergence analysis.
Definition B.4. Function f Rd is I-smooth if: f(x) S f(v) + (VS()), x - y) + 1
v112, Yx, E Rd,
and it is Le-smooth if:
Le || ul1 Val,, EC.
f(x) f(y) (VI())
2
Definition B.5. Function f Rd > R is p-strongly convex if: f(x) 2 f(y) + (Vf()), -y) $ - 2| Vx, y E Rd If 0 then function f is (non-strongly) convex function.
Having presented the two main definitions for the class of problems that we are interested in, let us now present the working-set W, which contains all iterates produced in the k-th outer loop of (the modified) Algorithm
Definition B.6 (Working-So Wa). For any outer loop k 2 1 in (the modified) Algorithm 7 starting define
Wh-1
Wk = (w E Rd
|| w|l
a m |]]-
(11)
24

---

ready to provide the main Under review as a conference paper at ICLR 2022
Note that the working-set W3 can be seen as a ball of all vectors w's, which are not further away from wk-1 than m mmax |oo|- Here, recall that m is the total number of iterations of an inner loop, a is an upper bound of the step-size 04-1, Vt [m], and ||% is simply the norm of the full gradient evaluated at the starting point i in the outer loop. By combining Definition [B.4 with the working-set Wa. assumption used in our analysis.
Assumption 1. Functions fo ii [n]] of problem working-set Wk. we simply write Li-smoothh.
1 are Lww, -smooth. Since only focus the
Let us denote L; the smoothness parameter of function fi, i E [nx], in the domain Rd. Then, it is easy to see that Li I Lis E [m]. In addition, under Assumption it holds that function P is Ts-ohooth in the working-set Wa. where Li = : E;= L4.
As we will explain with more details in the next section for our theoretical results, we will assume that max
LiuaR where L m Li
B.3 CONVERGENCE GUARANTEES
Now, we can derive the convergence rate of AI-SARAH. Here, we highlight that, all of our theoretical results can applied to SARAH. We also note that, some quantities involved in our results, such as LE and m are dependent upon the working set W; (defined for each outer loop k 2 1). Similar to Nguyen et al. (2017), we start by presenting two important lemmas, serving as the foundation of our theory.
The first lemma provides an upper bound on the quantity T P(w;)) Note that it does not require any convexity assumption.
Lemma B.7.
Fix outer loop k 2 and consider Algorithm
7 with amax S 1/Lg. Under
Assumption
Σ E P
E[P(wo) P(w")] )]
a E [[ P(w.) well wel1
The second lemma provides an informative bound on the quantity P(w:) vel 3). Note that it requires convexity of component functions fi, i [n]. Lemma B.8. Fix outer loop k 2 1 and consider Algorithm with o < 2/ Lmaxx Suppose Si is convex for all E [n]. Then, under Assumption 7 for any
[[[))((w:) vell <
Omma L.g.
Equipped with the above lemmas, we can then present our main theorem and show the linear convergence of (the modified) Algorithm I for solving strongly convex smooth problems.
Theorem B.9. Suppose that Assumption holds and P is strongly convex with convex component
functions fa. i E [n]. Let us define
t and select m and o max such that oy
Omea min
per (m++1)
2-a
1, Ak 2 1. Then, Algorithm converges as follows: [[IVP(@E)) < (IT I [IVP(
As a corollary of our main theorem, it is easy to see that we can also obtain the convergence of SARAH Nguyen et al. (2017). Recall, from Remark B.2 that SARAH can seen as special case of AI-SARAH if, for all outer loops, a a mmxx = In this case, we can have
aL
μa(m+1) + 2-aLnixx
If we further assume that all functions f.. E [n]. are L-smooth and do not take advantage of the local smoothness (in other words, do not use the working-set W&), then Lmax L for & 2 1. Then, with these restrictions, have
Om
[mm-)
T- <
As result, Theorem B.9 guarantees the following linear convergence: E V ( 1P <
(a, > (()))( which is exactly the convergence of classical SARAH provided in Nguyen et al.
(017)
25

---

Under review as a conference paper at ICLR 2022
C TECHNICAL PRELIMINARIES & PROOFS OF MAIN RESULTS
Let us start by presenting some important technical lemmas that will be later used for our main proofs.
C.1
TECHNICAL. PRELIMINARIES
Lemma C.I. Nesterov 2003 Suppose that function f is convex and L-Smooth in C C R Then for any w, w/ CC:
(w 1 Vf(w)- -
(Vf(w) -
(12)
Lemma C.2. Let Assumption 7 hold for all functions Jc of problem 7 That is, let assume that def
function Sq is L -mooth Vi E [n]. Then, function P(w) E Sc(w) is T-g-smothh, where
LL - L.
Proof. For each function fs. we have by definition of Li -local smoothness,
Li || y11 Vx, Wk. 2
[xx)) < fi(w) + (Vfi(v), -
Summing through all i's and dividing by n, we get
La |1 ull Vx, We.
P(x) S P(v) + (VP(y), x y) +
The next Lemma was first proposed in Nguyen et al. (017)). We add here with its proof for completeness and will use it later for our main theoretical result.
Lemma C.3. Nguyen et al. (2077) Consider vt defined in (2) Then for any t 2 in Algorithm 7 holds that:
BP(w) - [=]
Bl|ly 1 Bl)))((ws) VP(W)-1))l] (13)
Proof. Let By denote the expectation by conditioning on the information Wp, W1, Wy as well as
vo U1, ....... 11 Then,
E (10g)) - -
(v3 (0)--))))1
= -B - VP(W;- ++ K, 1
-)-V (VP(w,) (V)))))(()((((( -)P(W)P())
(OMP(()-1)-0j-11 E, 1/-11
-2(VP(w,) V E,(u, [1, 0--1]
E,(1IPP(W))1) - E, E VP(W)-))11]+ +,, 1--1
where the last equality follows from
E - uy-1] V. (wy)
-
By taking expectation in the above expression, using the tower property, and summing over j
1 1,..., 1, we obtain
E vP(w:) - rel1
Elloy - - 2z 11
EIll B((w))((s) - vP(w;-1))1
1=1
26

---

Under review as a conference paper at ICLR 2022
C.2 PROOFS OF LEMMAS AND THEOREMS
For simplicity of notation, we use |S| 1 in the following proofs, and a generalization to [S] > 1 is straightforward.
C.2.1 PROOF OF LEMMA B.7
By Assumption Lemma and the update rule wi = W 01-11/1111111 of Algorithm
we obtain:
L 0 2
P(w+) v P(w;-1) 04 1 ( 02-1) +
111-1---111
LE
P(w--1) a1-1 (VPP(w-))]] + at-1 /V(
(1 - U2-1
0t-1
ai-1
||0--11?
2
2
2
2
where, in the equality above, we use the fact that (a, b) = 2 [1|a|12 + 16/12 ||a
b1
By rearranging and using the lower and upper bounds of the step-size 04-1 in the outer loop (a S a S mmxx), we get:
min
| P( I [P(W)-1)- P(ws)] + max
VP(w;-1) 1/-1112- at (1- - Lxai-1) || 1/26211
2
2
2
By assuming that a I 1. T
holds that 04-1 S Ta and (1 T+ 2 0, 44 E [m]. Thus,
min
\P(
[P(w--1) P(w,)] max
/P((w-11) 1/-1
M (1 Lgamard ||/0_1 11?
2
2
By taking expectations and multiplying both sides with
a min
2 -EP(
a a
T Blllut- E V 1/-111
E [/WVVP((W:))))
1/ 1131
min
a
E[P((r 1 P()
Omin
a min
where the last inequality holds as o max I Txx
Summing over = 1,2,.... .... + 1, we have
2 m+1
m+1
B(P(w+-1) P(w:)] O
s
E (IV
amin
2 E(P(wo) P(wm+1)l O
m+11
E [[][P((( - 21-111
mmiu
o
min
2 E(P(wo) P(w+)] + amin
k max
m=+11
mii
t=1
where the last inequality holds since w" is the global minimizer of P. The last expression can be equivalently written as:
E[P((w) - P(w.)) + a
EE [()))(
<
max
(((;)((w;) -v.l/
t=0
min
min t=0
which completes the proof.
C.2.2 PROOF OF LEMMA B.8
E, [|]
< E, U - (V (w.-1) Vi,, (w,)) |2]
|| 2 + E,
V Vi, (wj-1) V/, (w
=
2
E,
(w, V,. (w,), 20--1 (0y)) -w,) m1n)
aj-1
2
||m 12 + E,
[ ( fir (w, E,
V (w - V.f. (w,,))
01 L
27

---

Under review as a conference paper at ICLR 2022
For each outer loop k; it holds that ay-1 a and L S L Thus, E E
2
|1 + E
fi, (wj-1) - fu, (w,))l 0
B [IV (wy-1)
Vfe,
Omax k
Lmax
2
|03-11| +
B V (wy-1)
Vls, (w;))1
are max k maxx
10--111 1|
B [lle 2ーー 11
ah max
Li
max
By rearranging, taking expectations again, and assuming that c "max < 2/ 2/Lm L
amax Li
B[lluş 1 <
B11 [12]] B [13] -
2 - Linx-L Liuax
By summing the above inequality over j L....,t (t 1), we have:
Blllu - 1- S
a
max Li max
[1luz-1 112 |105 [|]]
a Lik Lmax
mmxx Lik max
[E] 00 |1²] [-]
(14)
omaxx maxx
Now, by using Lemma C33
we obtain:
E P( 1z [2]
Σ E [[|u] - 11
J=1
14
a amax Lyax
E [B||co pol E[[lo]] [1]
2
at amaxLip Lmxx
a max T.max
E Blllva un []
(15)
2 aut a L
C.2.3 PROOF OF THEOREM B.9
Proof. Since uo = V P(w)) implies |/ P(wo)) - v0ol2 = 0, then by Lemma B.8
we obtain:
m
ma mox T. max
Σ
Blll) 1z [1]]
E |ollvol |.
(16)
2 ort max Lmax
Combine this with Lemma
B.7 we have that:
m
m
((w)))
E[P(uo)) - P(w.)] mmax a
E[| V P(w.)
a
ma A
mnx L
max
E[P(wo) - P[w+)] +
E Billvo (117)
2 - a amax L max
Omin
Since we are considering one outer iteration, with 1, we have uh (P T Wi, where t is drawn uniformly at random from {0, 1..................... m). Therefore, the following holds,
and
1
E V 11
E
t=
2
a a
max at _ L k I. max
E[P(wr-1)
E
P(w.)]
E P (wx-
min (m
+
1)
a
1
t amaxx
I. mmax
+
max
[E V P(
pac (m + 1)
a
2 a mmax
28

---

Under review as a conference paper at ICLR 2022
Let us use k min (m+1)
+ M muin
2- man Laaa then the above expression can be written as:
at Laua
V
E
o (
By expanding the recurrence, we obtain:
k II [VP(2)))11
E (
o'
This completes the proof.
29


Reviews:
[{"review_id": "rHIj1LNzE_c", "reviewer": "Reviewer_Y92t", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n1: This paper proposes a practical variant of SARAH with faster convergence by exploring the local geometry of the stochastic functions.\n\n2: Extensive experiments are conducted to verify the effectiveness and efficiency of the proposed algorithm.\n\n3: This paper is well-organized and well written with clear language and structures. The background knowledge is presented and the related papers are cited. \n\n\nWeaknesses:\n\n1: The contribution of SARAH over SVRG is mainly on convex functions rather than strongly convex functions. However, this paper only analyzes the case of the strongly convex function for AI-SARAH. As a variant of SARAH, I believe theoretical results on the general convex function are required.\n\n2: In convex optimization, the convergence results are usually evaluated with regard to the function value rather than the squared norm of the gradient. However, the proposed AI-SARAH is usually slower than the compared methods with regard to the function value. \n\n3: To tune the hyperparameter of SARAH and SVRG, in my personal experience, we do not really need 5000 runs to find a good hyperparameter. The authors may need to explain more on that.  \n", "summary_of_the_paper": "This paper studies the stochastic recursive gradient method for finite-sum problems. The proposed approach AI-SARAH is a practical variant of SARAH by exploring the local geometry of the stochastic functions. Specifically, in each iteration of the inner loop, AI-SARAH estimates the parameter of local Lipschitz smoothness by solving a sub-problem so that can use a larger step size for faster convergence when approaching the optimum. ", "summary_of_the_review": "Although the authors make some contributions in this paper, the weaknesses above are very critical to evaluating the contributions of the proposed method. I would like to vote for 'reject' if they are not addressed well.\n\nAfter the discussion, some of the concerns are solved. I will increase the score to 5.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "dFuFx6TiRtE", "reviewer": "Reviewer_G45K", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros: \n\n(1) The combination of adaptive tuning-free stepsize + SARAH is novel. Its motivation is very clear. \n\n(2) The experiments show that AI-SARAH outperforms some main-stream stochastic optimizers.  \n\nConcerns:\n\n(1) My major concern is that both the theorem and the experiments only involve convex optimization, while nonconvex optimization is more popular in machine learning, and SARAH achieves near-optimal sample complexity for nonconvex optimization. For convex optimization, SVRG and SAGA [2] have better sample complexity than SARAH. Hence, I suggest adding both theorem and experiments for nonconvex optimization.\n\n(2) Also, for convex optimization, usually we obtain convergence rate of function value gap $f(w_t)-f(w^*)$ or point distance $\\|w_t-w^*\\|$, while the authors only obtain convergence rate of gradient norm which is weaker and usually obtained for nonconvex optimization. \n\n(3) I suggest adding theoretical results of sample complexity (The number of computing function value and derivatives) and compare with that of SARAH for nonconvex optimization, since most works on SGD and variance reduction techniques (including SARAH) have sample complexity results. For the convex optimization, the complexity result can be directly obtained from Theorem 1.\n\n**I reject this paper mainly due to the above three concerns. Once they are solved, I will change to accept.**\n\n(4) The algorithm is claimed as \"First-order\", while $\\xi'(0)$ and $\\xi''(0)$ require the second and the third order derivatives of $P$ respectively. Hence, the sample complexity result also needs to involve the number of evaluations of the second and the third order derivatives.\n\n(5) There is an unclear point in Algorithm 1. If $k>0$ and $t=1$, then the line 14 is implemented using the undefined $\\delta_0^k$. What is the value of $\\delta_0^k$?\n\nMinor comments: \n\n(1) It is better to add y-axis labels to Figures 1c, 1d and 8. For example, The y-axis label of Figure 8 may be \"stepsize\".\n\n(2) In line 10 of Algorithm 1, you could add \"using $\\xi_t$ defined in (4)\", and in (4), I think you could still use $f_{S_t}$ since that looks the same simple as $f_{i_t}$ and guides us to correctly use Algorithm 1. Then, when explaining (4) by the example of quadratic function, you could let $S_t=\\{i_t\\}$ for simplicity.\n\n(3) For nonconvex optimization, you might use STORM algorithm [1] instead of SARAH, since both of them achieve the near-optimal sample complexity for nonconvex finite-sum optimization, but STORM does not require full gradient. \n\n(4) At the beginning of page 5, use \"Let\" (capitalized) in \"let us focus on a simple quadratic function\". \n\n(5) You might compare with SAGA [2], another important variance reduction technique as well in your experiment. \n\n(6) The authors may add intuition of the line 17 of Algorithm, i.e., the reason for using $\\alpha_{\\max}$.\n\n(7) In the final paragraph of Section 1.2, all the variance reduced work I read use $w_{t+1}=w_t-\\alpha_t v_t$, with either constant stepsize $\\alpha_t=\\alpha$ or predetermined diminishing stepsize. Also \"allow use\" could be \"allow to use\". \n\nReferences:\n\n[1] Cutkosky, Ashok, and Francesco Orabona. Momentum-based variance reduction in non-convex sgd. ArXiv:1905.10018 (2019).\n\n[2] Defazio, Aaron, Francis Bach, and Simon Lacoste-Julien. SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. Advances in neural information processing systems. 2014.", "summary_of_the_paper": "This paper proposes a novel algorithm by using adaptive tuning-free stepsize in SARAH, obtains its convergence rate in convex optimization, and demonstrates its empirical superiority by logistic regression experiments. ", "summary_of_the_review": "I reject this paper mainly due to the above concerns 1-3. Once they are solved, I will change to accept.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "OEjbPwCl0E0", "reviewer": "Reviewer_4uKg", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors presented a parameter-free and hence tunning-free variant of the SARAH variance reduction method. An extensive empirical study of the algorithm has been done and the result shows some advantages of the proposed method compared to other state-of-the-art methods that may need parameter tuning. This is the strength of the result. \n\nHowever, the weakness of the paper is that, though the authors do show some theoretical results, there is a big gap between the theory and the implemented algorithm. \n\n", "summary_of_the_paper": "In this paper, the authors proposed a SARAH-type variance reduced gradient method that adaptively and automatically selects the stepsize. \nIn each step, the authors propose to do an approximate line-search of the currently sampled function $f_{i_t}$ (or $f_{S_t}$) to estimate the local Lipschitz constant of the sampled function. To estimate the Lipschitz constant of the true objective function (the summation), the authors propose to do an exponential moving average of the estimated local Lipschitz constants. \n\nExtensive experiments are done in solving convex problems, and the comparison with other state-of-the-art first-order methods is also carefully presented. The authors also presented some theoretical guarantees of the algorithm with certain modifications.\n ", "summary_of_the_review": "The reviewer does appreciate the efforts in the empirical study. However, the reviewer has a few comments about the gap between theory and practice. \n\n1. The strength of the proposed algorithm is \"tuning-free\" and \"parameter-free\". However, to theoretically guarantee the convergence, the author actually requires knowing the local Lipschitz constant in the set $\\mathcal{W}_k$, see Eq(6). \n\n2. The authors argue that as the iterations approach the optimal solution, the curvature may tend to be flatter. Therefore, the global Lipschitz constant may be much larger than the local Lipschitz constant, resulting in a more conservative stepsize, i.e., the stepsize $1/L_{global}$ may be much smaller than the stepsize $1/L_{local}$. However, since $\\alpha_{max}^k$ is already $1/2L_{local}$, doing a line search only results in smaller stepsizes. This contradicts the philosophy of using larger stepsize when possible. Therefore, the theory does not explain the strength of the algorithm. Moreover, if $1/L_{local}$ is known, why not directly apply SARAH with this local parameter? \n\n3. There is a small flaw in the logic of the proof. First, the authors define the set \\mathcal{W}_k:= {w:||w- \\tilde w_{k-1}|| \\leq m\\alpha_{max}^k||v_0||}. The authors argued that $\\mathcal{W}_k$ is the set where all the iterations of the $k$-th epoch should lie within. This only happens when all the later gradient estimators $||v_t||\\leq ||v_0||$ almost surely, otherwise the proof wouldn't work. However, the authors are not able to show this because all the descent results are in the sense of expectation instead of almost surely. \n\n4. With $\\alpha_{max}^k = 1/2L_{local}$, the analysis is more or less the same as the original SARAH algorithm, with little modification. Therefore, the current analysis is not very interesting to the reviewer. However, a much more interesting thing is how well the proposed procedure approximates the local gradient, this has never been addressed in the existing works. However, with the current assumptions on $\\alpha_{max}^k$, this challenge is left undone.\n\n-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\nAfter the rebutal, the authors have cleared my question in comment #3. The issue stated in this comment can be cleared with a few more explanation. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Ln9CAMHffyW", "reviewer": "Reviewer_CpvK", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- I cannot see it explained how to pick $\\alpha_{max}^k$, In Lemmas B.7 and B.8 they depend on some Lipschitz constant depending on the set in eq. (11) how to estimate these?\n- The authors talk about using Newton method to solve the sub-problem, but how does this affects the analysis explicitly?\n- What about adaptivity to strong convexity? While it is easy to know the strong convexity for the regularizers, it can be quite difficult to estimate the strong convexity of the loss function (\"data-term\"). The authors say the algorithm is \"fully adaptive\". Probably,it should be explained that this \"full adaptivity\" is not to the strong convexity.\n\n\nFor the experiments, I understand the authors point: even though each iteration of AI-SARAH can be expensive because of the local Lipschitz constant estimation, it doesn't require tuning and the other methods require tuning. The authors state that they do \"fine-tuning\" for all the other methods, which takes a lot of time and therefore the overall cost of AI-SARAH is reasonable. My question is: what happens when the authors do a \"rough tuning\"? Is the improvement of the other methods is significant between the \"rough tuning\" and \"fine tuning\"? Maybe \"fine tuning\" isn't necessary for these methods to be competitive and the overall time for these algorithms can be reduced this way. It would be nice to see a tradeoff of these algorithms in terms of the accuracy/total time/budget of tuning.\n\n\n- Why is sparsity of the datasets mentioned? Does the algorithm use this information in any way?\n\nOverall, I am concerned that the writing is not too transparent to show this fact about the difference of analyzed and implemented algorithms. I find the discussions before Section 3.4 too long and repetitive whereas Section 3.4 is too quick and unclear for the readers why all these modifications are being done for analysis.\n\n\nWhile I do appreciate the value of extensive practical comparisons, for such a well-studied class of problems (smooth and strongly convex), I expect a smaller gap between the theory and practice within the paper. Therefore, I think the authors should either implement the algorithm they analyze or analyze an algorithm closer to the one they implement. Moreover, if the paper wants to make a claim more on the practical side, then I am curious what happens with \"a rough and systematic tuning\" for other algorithms.\n", "summary_of_the_paper": "This paper proposes a new variance reduced algorithm for solving smooth and strongly convex optimization. The authors build on SARAH and propose AI-SARAH which aims to estimate the local Lipschitz smoothness parameters on the fly. The authors provide theoretical analysis for a modified version of AI-SARAH and provide extensive practical experiments for AI-SARAH.\n", "summary_of_the_review": "I really appreciate the promise of the paper and the direction pursued by the authors. However, I have some concerns regarding the theory-practice mismatch within the paper. Unfortunately, until Section 3.4, the writing is as if the authors will analyze AI-SARAH which is implemented in practice, however Section 3.4 introduces many modifications on the algorithm. On this front, it is not explained if the analyzed algorithm does really work well in practice or how much theory can be shown for the implemented algorithm. \n\nI am willing to increase my score if the authors reply to my questions in a satisfactory way.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a variant of SARAH, which employs the stochastic recursive gradient and adjustable step-size based on local geometry. The main concerns about this paper include (1) the empirical comparison with other algorithms might not be fair (which is arguable); and (2)  the theorem proved in the paper is for a simplified algorithm rather than the algorithm used in the experiments. Even after author response and reviewer discussion, this paper does not gather sufficient support from the reviewers. Thus I recommend rejection.
Decision: Reject