AI-SARAH: Adaptive and Implicit Stochastic Recursive Gradient Methods
Authors: Zheng Shi
Abdurakhmon Sadiev
Nicolas Loizou
Peter Richtárik
Martin Takáč
Venue: Accepted by TMLR ()

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.

Published in Transactions on Machine Learning Research (02/2023)
AI-SARAH: Adaptive and Implicit Stochastic Recursive Gra- dient Methods
Zheng Shi
Shi. Zhing. FFLS@ggmal..o com
IBM United States of America
Abdurakhmon Sadiev
King Abdullah University of Science and Technology (KAUST)
Thuwal
Saudi Arabia
Nicolas Loizou
aloizou@jjve edu
Johns Hopkins University
Baltimore
United States of America
Peter Richtárík
peter.richtaribskkauss....e
King Abdullah Universily of Science and Technology (KAUST)
Thuaaal Soudi Arabia
Martin Takáč
Takac, MT @ggaalllll..mmmmmmmmmmmmmmmmm.m. com
Mohamed bin Zayed University of Artificial Intelligence (MBZUAI) Masdar Cily, Abu Dhabi
United Arab Emirates (UAE)
Reviewed OpenReview: https: // openreview. net/ ftrfo id= NoXJFsJ6Zu
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. AT- SARAH implicitly computes step-size and efficiently estimates local Lipschitz smoothness of stochastic functions. It is fully adaptive, tunc-free, straightforward to implement, and compulationally efficient. We provide technical insight and intuitive illustrations on ils 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.
1 Introduction
We consider the unconstrained finite-sum optimization problem
min P(w)
def
f((w)
(1)
This problem is prevalent in 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, [ often considered the loss function of Empirical Risk Minimization (ERM) problems. For instance, given classification regression problem, fi be defined

---

Published in Transactions on Machine Learning Research (02/2023)
logistic regression least square by (Ia; U4) where x; is feature representation and yr is a label. Throughout the paper, we assume that cach function fi. i E [ra] def optimal solution w* of
[1. is smooth and convex, and there cxists an
1.1 Main Contributions
We propose A Adopiie and Implicit StochAstic Recursive GrAdient AlgoritHm (AI-SARAH), practical variant of stochastic recursive gradient methods (Nguyen et al., 2017 to solve [ This practical algorithm explores and adapts to local geometry. It is adaptive at full scale yet requires zero effort of tuning hyper- parameters. The extensive numerical experiments demonstrate that our tune-free and fully adaptive algorithm is capable of delivering a consistently compelitive performance on various datasets, when comparing with SARAH, SARAH+ and other state-of-the-art first-order methods, all equipped with fine-tuned hyper- parameters (which selected from = 5, 000 runs for each problem). This work provides foundation studying adaplivity (of stochastic recursive gradient methods) and demonstrates that a truly adaptive stochastic recursive algorithm can be developed in practice.
1.2 Related Work
Stochastic gradient descent (SGD) Robbiin & Monro
Shalev-Shwarta et al. 2007 Nemirovski et al. 2009 Gower et al. 2019 is the workhorse for training supervised machine
1951 Nemirovski & Yudin 1983
learning problems that have the generic form 4
In its generic form, SGD defines the new iterate by subtracting a multiple of a stochastic gradient g(w,) from the current iterate wy. That is,
W++1 wt -agggggu (ug(
In most algorithms, g(w) is an unbiased estimator of the gradient (i.e., stochastic gradient), [[g(w)] P(Ww), Ve E Rd. However, in several algorithms (including the ones from this paper), g(w) could be a biased estimator, and convergence guarantees can still be well obtained.
Adaptive step-size selection. The main parameter guarantee the convergence of SGD is the step-size. In recent years, several ways of selecting the step-size have been proposed. For example, analysis of
SGD with constant step-size (ag a.) or decreasing step-size has been proposed in Moulines & Bach 2011
Ghadimi & Lan (2013); Needell et al. (2016); Nguyen et al. (0118) Bottou el al. (2018); Gower el al. 2011 2021 under different assumptions on the properties of (1).
More recently, adaptive / parameter-free methods (Duchi et al. 2011
Kingma & Ba 2015 Bengio 2015
& Orabonal 2018 Vaswani et al. 2019 Liu al.] 2019a Ward et al. 2019: Loizou et al. 2021 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 parameters that might be unknown in practical scenarios, like the smoothness the strongly convex parameter.
we explain how the update rule of the proposed AI-SARAH (Algorithm 2 involves solving a specific sub-problem for selecting the optimal step-size in the current iteration. This idea is novel, but it is closely related to the recent work of Loizou et al. (2021) on the Stochastic Polyak Step-size (SPS) for SGD, where the optimal choice, to some extent, of step-size is selected in each iteration of SGD. Loizou et al. (2021) provided several convergence guarantees of SGD with SPS, including linear convergence to neighborhood for solving strongly convex problems and sublinear rate of convergence to neighborhood for convex and non-convex problems. It also shown that SPS is particularly effective in step-size selections under the interpolation setting, which enables SGD to converge to the true solution at fast rate matching the deterministic case. The results of Loizou el al. (202)) were later exlended to different seltings. Gower et al. 2021)) provided analysis SGD with SPS for structured non-convex problems while D'Orazio et al. (2021 proved convergence of stochastic mirror descent under the mirror stochastic Polyak stepsize (mSPS). More recently, Orvicto al. proposed Decreasing SPS (DecSPS) a step-size selection for SGD, novel modification of SPS, which guarantees convergence (sublinear) to the exact. minimizer without priori
In Section 4.1
2

---

Published in Transactions on Machine Learning Research (02/2023)
knowledge of the problem's parameters. information.
Li et al. (023) recently extended the SPS to include curvature
Random vector g(w) and variance reduced methods. One of the most remarkable algorithmic breakthroughs in recent years was the development. of variance-reduced stochastic gradient algorithms for solving finite-sum optimization problems. These algorithms, by reducing the variance the stochastic gradients, are able to guarantee convergence to the exact solution of the optimization problem with faster convergence than classical SGD. Over the past decade, many efficient variance-reduced methods have been proposed. Some popular examples of variance reduced algorithms are SAG (Schmidt ct al.) 2017). SAGA (Deaazio et al. 2014), SVRG [Johnson & Zhang 2013 and SARAH Ngguyen et al. 2017). For more examples of variance reduced methods, see Defazio (2016); Konečný et al. (2016): Gower et al. (0200); Khaled et al.
(2020): Horváth et al. (2020); Cutkosky & Orabona 22000) Dubois- Taine et al. (202)); Sadiev et al. (2022). ).
A Among the variance reduced methods, SARAH is of our interest in this work. Like the popular SVRG, SA RAH algorithm composed of two nested loops. In each outer loop k 2 1, the gradient estimate vo- = (1) is set to be the full gradient. Subsequently, in the inner loop, at 2 1, biased estimator vt is used and defined recursively as
U1 VV((w) V f2-1,
(2)
where 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 We au, is constant (or diminishing with predetermined rules) and that depends the characteristics of 11. An exception to this rule is variance reduced method with Barzilai-Borwein step-size, named BB-SVRG
and BB-SARAH proposed in Tan et al. (2016) and Li & Giannakis (2019) respectively. These methods allow to use Barzilai-Borwein (BB) step-size rule to update the step-size once in every epoch; for more examples, see Li et al. 2020 ; Yang et al. (2021). There are also methods proposing approach of using local Lipschitz smoothness to derive an adaptive step-size :Liu et al., 2019b) with additional tunable paramcters or leveraging BB step-size with averaging schemes to automatically determine the inner loop size (Li et al.) 2020). However, these methods do not fully take advantage of the local geometry, and truly adaptive algorithm: adjusting step-size at every (inner) iteration and climinating need of tuning any 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.
2
Motivation
With our primary focus on the design of a stochastic recursive algorithm with adaptive step-size, we discuss our motivation in this section.
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 starting point wo Rd. and choices of step-size could be heavily influenced by the curvature provided P²P(w)). What if step-size has to be small due to a "sharp" curvature initiallyy, which becomes 'faal' aflerwards?
To see this is indeed the case for many machine learning problems, let us consider logistic regression for a binary classification problem, i.c., fi(w)= = log(1 + exp(- w)) + A [| where x; E Rd is a feature vector, i (-1, [1] is ground truth, and the ERM problem is in the form of (T] It is easy to derive the local curvature of P(w), defined by its Hessian in the form
exp( 9:20 w)
V2P(w)= =
x + AL.
(3)
exp( yio! w)
(w)
3

---

Published in Transactions on Machine Learning Research (02/2023)
40
AASARUI
SARAR stpprio 2:22
10
10
can
30
SABAH: stppece
10
10
seere dey can 41
20
dry
10
10
bound
26.00
otep-sioe (mooingg avo)
10
15
20
25
30
10
10
20
25
30
0
10
15
20
25
30
Effective Pass
Effective
Effective Pass
(a)
(c)
9.20
11-4
22-4
0.15
11-11
32-
2.05
11-0
33-1
13"4
1.0 29 39
63
69 121 257 22.0 62.522233333
Effective Pass
18:11
0.7
2.5
30
7.5
10.0
12.5
15.0
37.5
100
3.0
10.3 12.5 15.3 17.5
20.0
(d)
(e)
(f)
Figure 1: AI-SARAH vs. SARAH: (a) evolution of the optimality gap P(w) - and (b) the squared
norm of stochastic recursive gradient ||,:||;; AI-SARAH:: (c) evolution of the step-size, upper-bound, local Lipschitz smoothness and (d) distríbution of s; of stochastic functions; (e) and (f) show the comparison of AI-SARAH with a constant step-size selection for non-variance reduced ADAM [Kngmma & Ba (2015), RMSProp Hinton et al. (012); Bengio| (205)), and Adagrad Duchi et al. (2011). Note that larger step-size achieves quicker progress at the beginning but then stagnates. On the other hand, a smaller step-size slows down convergence, but the algorithms can achieve the solution of a better quality.
Note: in (a), P is a lower bound of P(w"); in (c), the white spaces suggest full gradient computations at outer iterations; in (d), bars represent medians of s; 's.
Given that (1+4)2 S 0.25 for any a 2 0, one immediately obtain the global bound Hessian, L.c. Ve E R.d
we have P2P(w) 3 H i= कæे + AL. Consequently, the parameter of global Lipschitz smoothness is L= 1 Amax E 2. ) It is well known that, with a constant step-size less than (or equal to) 1. a convergence is guaranteed by many algorithus.
However, suppose the algorithm starts at a random wo (or at e Rd),, this bound can be very tight. With more progress being made on approaching an optimal solution (or reducing the training error), it is likely that, for many training samples, - 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 a larger step-size can be used. That being said, such a dynamic step-size cannot be well defined in the beginning, and a fully adaptive approach needs to be developed.
For illustration, we present the inspiring results of an experiment on real-sim dataset Chang & Lin 2011
with @-regularized logistic regression. Figures (() and [bb] compare the performance of classical SA SARAH
with AI-SARAH in terms of the evolution of the optimality gap and the squared norm of recursive gradient. As is clear from the figure, AI-SARAH displays a significantly faster convergence per effective pass]
Now, let us discuss why this could happen. The distribution of 8; as shown in Figured T(d) indicates that: initially, all sy's are concentrated at 0.25; the median continues to reduce within a few effective passes on the training samples; eventually, it stabilizes somewhere below 0.05. Correspondingly, as presented in Figure [[c] AI-SARAH starts with a conservative step-size dominated by the global Lipschitz smoothness, i.e., 1/Amaz (V2P(wn)) (red dots); however, within 5 effective passes, the moving average (magenta dash) and
The effective pass defined complete pass on the training dataset. Each data sample is selected once per effective pass average.
4

---

Published in Transactions on Machine Learning Research (02/2023)
upper-bound (blue line) of the step-size start surpassing the red dots, and eventually stablize above the conservative step-size.
For classical SARAH, we configure the algorithm with different values of the fixed step-size, i.e, {2- ,..., 2*), and notice that 2 leads to a divergence. On the other hand, AI-SARAH starts with a small step-size, yet achieves a faster convergence per effective pass with an eventual (moving average)
step-size larger than 25. Figures I(e) and [f) show the comparison of AI-SARAH with a fixed step-size
ADAM Kingma& & Ba (2015) RMSProp Hinton et al. 2012): Bengio (2015). and Adagrad Duchi et al. (0011)
The reducce algorithms mentioned above
achieve faster initial convergence with a larger step-size. However, they achieve worse solutions in the given time budget. On the other hand, choosing a
smaller step-size can lead to a better solution, but algorithms converge slower. In practice, one tunes the step-size and the step-size decay to achieve an acceptable performance.
3 Theoretical Analysis
In this section, we present the theoretical investigation on leveraging local Lipschitz smoothness to dynamically determine the step-size. We are trying to answer the main question: can show convergence of using such adaptive step-size and what are the benefits.
We present the thcoretical framework in Algorithm and refer to it as TheoreticalAT-SAARA. For the theoretical algorithm, we analyze two options for sampling functions: Option I. sampling fi uniformly at random, and Option II. importance sampling, where function fi is sampled with probability proportional to local L,. For brevily, we show the main results in the section and defer the full technical details Appendix
Algorithm Theorelica--A-SARRRR
Parameter: Inner loop size m
Initialize: úhg
3: for h = 1,2,... do
4: wo 1
5: Up = P(Ww))
6: for i E [n] do
Compute L the neighborhood of wo by 4
end for
[axxe]]]] LJ, 1 Σ DQ, Option
Option I and set noo 1/1.0
Compute 7,0
10:
for f = 1.... m7 do
11:
Wt Wt-1 1
Option
12:
Sample 4 randomly from [n] with probability p:
Option II
Vis (wx) Vii (w (V... (w,) - (w,,(w
Option T
13:
= 0
Option
np.
14:
for E [m] do
15:
Compute Li in the neighborhood of w, by 44
16:
end for
Compute L' maxie[m] L; 1 D
Option I
17:
1 L.
Option 11
18:
7i min
I Lt Le
11-1 T1-1
19:
end for
20: Set. Wa where is chosen with probability = mh/ E Yy from {0, 1, 1,...
21: end for

---

Published in Transactions on Machine Learning Research (02/2023)
For t 2 0, E [n], We assume fú is Li-smooth the line segment A {w E Rd w - -,,,, of [0, iz
Then, for Lines and 15, we have
L = max V f((; 774))l2. where 1j [0, 1gl.
(4)
The problem 4 essentially computes the largest eigenvalue of Hessian matrices on the defined line segment. Note that, computes Lद implicitly as it appears on both sides of the equation.
Having presented Algorithm 1 we can now show our main technical result in the following theorem.
Theorem 3.1. Suppose P is u-strongly convex, and each fa is conver and Lm-smooth on the line segment A (w E Rd w = Wi- 1p4 n E [0, Z/1-- For 1, let us define
no 177t + - no
(5)
where H. Ei Th, and select m and nj such that o'n 1,, Algorithm converges as follows
k = E P((x))1
IIot, o' [VP(()))1
Remark 3.2. The convergence result of classical SARAH Nguyen et al. (017 algorithm for strongly convex case has similar form of as (5) but with HSARAH a<(m + 1), where < f constant step-size. In this case, T. is the global smoothness parameter of each fi, i E [n]. Now, of smoothness only a line segment, we trivially have that
defines T2 to be the parameter
TT L
max f( (eolll S max wERd
f(w)ll S.
nE(0
Thus, H. = = E.= Z
2 - T 2 +1 = HSARAH. Then, clear that, Algorithm
can achieve a faster convergence than classical SARAH.
By Theorem 3.1 and Remark 3.2 we show that, in theory, by leveraging local Lipschitz smoothness, Algorithm) is guaranteod to converge and can even achicve a faster convergence than classical SARAH if local geometry permits.
With that being said, we note that Algorithm Daahhammrruuuuue requires the computations of the largest eigenvalues Hessian matrices the line segment for cach fi at every outer and inner itcrations. In general, such computations would be too expensive, and thus would keep one from solving Problem ① efficiently in practice.
In the next section, we will present our main contribution of the paper, the practical algorithm, AI-SARAH. It does not only eliminate the expensive computations in Algorithm L but also climinate efforts tuning hyper-parameters.
4 AI-SARAH
We present the practical algorithm, AI-SARAH, in Algorithm 2 At every iteration, instead of incurring expensive costs on computing the parameters of local Lipshitz smoothness for all fi in Algorithm I Algorithm estimates the local smoothness by approximately solving the sub-problem for only one Si, i.e., min (a)), with a minimal extra cost in addition to computing stochastic gradient, i.e., V.. Also, by approximately solving the sub-problem, Algorithm implicitly computes the step-sizo, i.c., 0t-1 at t 2 1. Please note that, on Line 9, b > 0 is the mini-batch size. Let us remark that AI-SARAH samples function f, uniformly, and here for simplicity, we do not focus on proposing a practical version with an importance sampling.
In Algorithm 2 we adopts an adaptive upper-bound with exponential smoothing. To be specific, the upper-bound is updated with exponential smoothing on harmonic mean of the approximate solutions to the sub-problems, which also keeps track of the estimates of local Lipschitz smoothness.

---

Published in Transactions on Machine Learning Research (02/2023)
In the following sections, will present the details the design of AI-SARAH.
We note that this algorithm is fully adaptive and requires no efforts of 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 3 = 0.999. There exists one syper-parameter in Algorithm 2 y which defines the early stopping criterion on Line 8, and the default setting section that, the performance of this algorithm is not sensitive to the choices of 7: and this true regardless of the problems (i.e., regularized/ pelllariieddooo-rgggllae non-regularized logistic regression and different datascts.)
32" We will show later in this
A Algorithm AI-SARAH
Parameter: 7 (default })), 3 0.999
Initialize: dh
Set: Qmar
4: for k = 1, 2, do
5: Wp wk-1
6: vD P(wo)
7: t=
while ||v/|l 2 2|1 do
Select random mini-batch S. from [n] uniformly with |Se| ãt-1 arg mig ((())
10:
11:
if k and t = then
12:
6. a.-
13:
else
14:
38 + (1 (1-3)) 8)_
15:
end
if
16:
Omer
6.-
17:
0t-1 min
( min(āt-1s
Aman
18:
Wt = W1-1 at 11-1
19:
Vt = +++1
fss, (wa)
Vss, (w)-1) + 1t-1
20:
21:
end while
Set g++1 of
22:
23:
Set wh = Wt.
24:
end for
4.1
Estimate Local Lipschitz Smoothness
In the previous section, we showed that Algorithm 1 computes the parameters of local Lipschitz smoothness, and it can be very expensive and thus prohibited in practice. To avoid the expensive cost, one can estimate the local Lipschitz smoothness instead computing an exact parameter. Then, the question how to estimate the parameter of local Lipschitz smoothness in practice.
Can we use lino-scarch? The standard approach to estimate local Lipschitz smoothness is to use backtracking line-search. Recall SARAH''s update rule, i.e., w; Wt-1 0 where er-1 is stochastic recursive gradient. The standard procedure to apply line-search on function fi, (, - -21-1). However, the main issue is that - 1 is not necessarily a descent direction.
AI-SARAH sub-problem. Define the sub-problen (as shown on Line 10 of Algorithm 2 as
min {c(a) = min V (wi-1 av1-1) (w,-11 + 21211 asu
(6)
a>u
For the sake simplicity, we fú, instead of fsr-

---

Published in Transactions on Machine Learning Research (02/2023)
where t 2 1 denotes inner iteration and in indexes a random sample selected at t. We argue that, by (approximately) solving G we can have good estimate of the parameters of the local Tipschitz smoothness.
To illustrate this setting, we denote L the parameter of local Lipschitz smoothness prescribed by Sú, at "1-1- Let us focus on a simple quadratic function ft. (w) = 2 (,,, w )s,) Let á be the optimal step-size along direction 1: 1. i.e. ā arg min, Jú, (w,-1 - 004-1). Then, the closed form solution of can be easily derived as ă = z 14-1 My whose value can be positive, negative, bounded or unbounded.
On the other hand, one compute the step-size implicitly by solving 6 and obtain af-1, i.c., af arg min, S((a). Then, we have 09-1 ",.
which is exactly 1 E..
To put simply, as quadratic function has a constant Hessian, solving 6 gives exactly T. For general (strongly) convex functions, if v2 (w:-1), does not change too much locally, we can still have a good estimate of 1/L, in direction of 8--1 by solving (6) approximately. To see that, let us assume that approximate the difference of gradients follows
Vi, (wr-1 av--1) - Vi, (w,-1) -v fr. (wa-1)vt-1-
Then
V2 Sr, (w6-1)
arg min || (u( + 2-111
(8)
V fú, (w V2 fie (w)-1)ur-1
The reciprocal of the last expression could be seen as the curvalure of fú, (wr-1) in direction 0--1-
Based on a good estimate of LS we can then obtain the estimate of the local Lipschitz smoothness of P(w:-1). And, that is L' = n. -m= L = Σ a;-; Clearly, if a step-size in the algorithm is selected as 1/L', then a harmonic mean of the sequence of the step-size's, s, computed for various component functions could serve as good adaptive apper-bound on the step-size computed in the algorithm. More details of intuition for the adaptive upper-bound can be found in Appendix B.2
4.2 Compute Step-size and Upper-bound
On Line 10 of Algorithm g
the sub-problem is a one-dimensional minimization problem, which can be approximately solvod by Newton method. Specifically Algorithm we compute one-step Newton at = 0, and that is
( [E(
à
Note that, for convex function in general, (9) gives an approximate solution; for functions in particular forms such quadratic ones, ( gives exact solution.
In order to give an insight why one-step Newton at = 0 could make sense, let us first evaluate the key quantities in 99. We have
(0)) = - oft1 fi, (wc-1)00-1
<0())= V fi, (w+-1) (1--1))1-111111 U1-1,, "f_ 2 (w.-1) (u (wa-1)0t11
where V' (w,-1) - 1/ is the 3rd derivative of fú, multiplied by Ut-1- If assume that the Hessian is not changing much, then this quantity can be ignored and ( becomes equal to (
The procedure prescribed in 9 can be implemented very efficiently, and it does not require any extra (stochastic) gradient computations if compared with classical SARAH. H. 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 B.2 for implementation details.
As shown on Lines 11-16, 22 of Algorithm 2 amaz is updated at every inner iteration. Specifically, the algorithm starts without. an upper bound (i.e., Omaz co Line 3); as â being computed every
8

---

Published in Transactions on Machine Learning Research (02/2023)
ijcnn1
rcv1
real-sim
news20
covtype
10.
10:
10"4
1044
1073
-4-
1754
10
10-4-
-
1/22
171.
178
10
10:17
20-44
20
15
20
20
23
33
5
32
23
22
Figure 2: Evolution of [| for 104 32
2) the regularized case.
Table 1: Summary of Datascts from Chang & Lin 2011
Datasct
# features
n (# Train)
# Test
% Sparsity
tjennl
22
49,990
91,701
40.91
revl
47,236
20,242
677,390
99.85
real-sim?
20,958
54,231
18,078
99.76
news202
1,355,191
14,997
4,999
99.97
coutype"
54
435,759
145,253
77.88
dataset has default training/tesee testing samples. dataset randomly split by 75%-training & 25%-testingg
12 1, we employs the exponential smoothing on the harmonic mean of {ār-1) to update the upper-bound. For 2 and 2 1, we define amar
gt where
k= =
5
Or- + (1 (1-8)as (1-
35
otherwise
and < B < 1. We default 8 0.999 Algorithm 2 At the end of the kth outer loop, denoted t == T, we let
gh+1 8h; see Appendix B.2 for details on the design of the adaptive upper-bound.
4.3 Choice of y
We perform sensitivity analysis different choices of 7. Figures 2 shows the evolution of the squared norm of full gradient, i.., [|VP(w)]]? for f-regularized logistic regression on binary classification problems; see non-regularized case and extended results in Appendix B is clear that the performance of y's, where, y E {1/8, 1/16, 1/32, 1/64), consistent with only marginal improvement by using a smaller value. We default 1/32 Algorithm
5 Numerical Experiment
In this section, we present the empirical study on the performance of AI-SARAH (see Algorithm 2p. For brevily, present subset of experiments in the main paper, and defer the full experimental results and implementation detail: in Appendix
The problems we consider in the experiment are P-regularized logistic regression for binary classification problems; see Appendix B for non-regularized case. Given a training sample (I;, ys) indexed by [n], the component function fr is in the form fiww) log(1 + exp(- w)) ||/l|, where À for the P-regularized case and X = 0 for the non-regularized case. The datasets chosen for the experiments are ijenn1, rev1, real-sim, weus20 and covlype. Table T shows the basic statistics of the datasets. More details
and additional datasets can be found in Appendix B
3 Seee code httg::///gtthan..cceohhhaaaeeers

---

Published in Transactions on Machine Learning Research (02/2023)
AI-SARAH
SARAH
SARAH
SVRG
Adam
SGD
Jjcnn1
rcv1
real-sim
news20
covtype
16
10
10
18-1
10
10:14
10-10
20
Effective Pass
Effective Pass
Effective Pass
Effective Pass
Effective Pass
10-1
22
10111
20
10
10-4
33-1
10-4
20-14
10-
12+1
10:19
10-11
13.0
45.2 102.0
11.0
240.0
937.2
(sec)
(soc)
Wall Clock (sec)
Wall (sec)
Clock (soc)
Figure Running minimum per effective pass (top row) and wall clock time (bottom row) of [VP(w) between other algorithms with all papee-paraaeters configurations and AI-SARAH for the regularized case.
AI-SARAH
SARAH
SARAH+
SVRG
Adam
- SGD w/m
Ijcnn]
rev1
real-sim
news20
covtype
10th
160
10.
10-2
10.
33-1
15
10
33-1
16-4
10-1
10
10-4
20-11
10
10 Effective Pass
20
10
20
Effective Pass
Effective Pass
Effective Pass
Effective Pass
30.5
10:1-
20
[[P])]]]2
10:1--
12:1
10'11
12.4
20
30.h
10.1
20
16
12:11
10-10
125
42
52
320
360
150
220
400
6co
800
1200
Wall Clock (sec)
Wall Clock (Soc)
Wall Clock (50C)
Wall Clock (sec)
Wall Clock [sec]
Figure 4: Evolution of /V for the regularized case by effective pass (top row) and wall clock time
(bottom row).
We compare AI-SARAH with SARAH, SARAH+, SVRG JJhnsoon & Zhang 2013). ADAM Kingma & Ba 2015) and SGD with Momentum (Sutskever et al. 2013 Loizou & Richtárik) 2020 2017). While AI- SARAH does not require hyper-parameter tuning, we fine-tune each of the other algorithms, which yields z 5, 000 runs in total for each dataset and case.
To be specific, we perform an exlensive search on hyper-parameters:: (1) ADAM and SGD with Momentum
(SGD w/ w/m) are tuned with different values 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+ tuned with different values of the (constant) step-size and carly stopping parameter. (See Appendix B for detailed tuning plan and the selected hyper-parameters.)
10

---

Published in Transactions on Machine Learning Research (02/2023)
AI-SARAH
SARAH
SARAH+
SVRG
Adam
jjcnn1
rcv1
real-sim
news20
cavtype
0.20
0.26
6.24
0.20
0.58
0.20
6.22
0.34
0.20
20
Effective Pass.
Effective Pass
Effective
Effective
Effective Pass
0.20
0.28
0.40
0.505
0.2
0.28
0.22
0.2
0.22
0.2
100
125
25
150
Wall Clock (sec)
Wall Clock (sec)
Wall Clock (sed)
Wall Clock (sec)
Well Clock (sec)
Figure 5: Evolution of P(w) for the regularized case by effective pass (top row) and wall clock time (bottom
row).
Al-S SARAH
SARAH
SARAH+
SVRG
Adam SGD
ijcnn1
covtype
3.955
6.952
0:335
3.500
0.333
0.50
Accuncy
0925
3.415
0.52
0010
0.72
0.71
3.00
0.342
0.00
0.78
10
10
20
Effective
Pass
Effective
Pass
3.925
3,940
8:000
0.75
1.923
2.835
3.550
0.34
1.500
0.73
2330
3.2
6.11%
2305
5,885
0.71
30
25
180
125
20
40
60
25
20
1.00
53
103
150
220
430
500
800
1000
Wall Clock (sec)
Wall Clock (sec)
Wall Clock (sec)
Wall Clock (sec)
Wall Clock (sec)
Figure 6: Running maximum of testing accuracy for the regularized case by effective pass (top row) and wall clock time (bottom row).
iinnn1
covtype
25
Siog
10-
Onar
Effective
Figure Evolution of AT-SARAH'ss step-size and upper-bound Ommz for the regularized case.
11

---

Published in Transactions on Machine Learning Research (02/2023)
Figure 3 shows the minimum PV=))l achieved at few points of effective passes and wall clock time horizon. It is clear that, RA''s practical speed of convergence is 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 in Pytorch ), it is likely that our algorithm can be accelerated.
By selecting the fine-tuned hyper-parameters of all other algorithms, we compare them with AI-SARAH and show the results in Figures 6 For these experiments, we use 10 distinct random seeds to initialize and generate stochastic mini-batches. And, use the marked dashes to represent the average and filled areas for 97% confidence intervals.
Figure presents the evolution of IVP(w)] Obviously from the figure, AI-SARAH exhibits the strongest performance in terms of converging to a stationary point: by effective pass, the consistently large gaps are displayed between AI-SARAH and the rest; by wall clock time, we notice that AI-SARAH achieves the smallest P(w) I 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 5 shows that, by effective pass, AI-SARAH consistently outperforms SARAH and SARAH+ on all of the datasets with a possible exception on contype datasct. By wall clock time, AI-SARAH yields a competitive performance on all of the datasets, and it delivers a stronger performance on ijenn1 1 and real-sim than SARAH.
For completeness of illustration on the performance, we show the testing accuracy in Figure G Clearly, fine-tuned ADAM dominates the competition. However, AI-SARAH outperforms the other variance reduced methods most of the datasets from both effective pass and wall clock time perspectives, and achieves the similar levels of accuracy ADAM does revl, 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 7 This figure clearly shows that why AI-SARAH can achieve such a strong performance, especially on the convergence to a stationary point. As mentioned in the previous sections, the adaptivity is driven by the local Lipschitz smost As shown Figure 7 AI-SARAH starts with conservative step-size and upper-bound both of which continue increase while the algorithm progrosses towards stationary point. After few effective passes, we observe: the step-size and upper-bound are stablized due to >> 0 (and hence strong convexily). In Appendix B can see that, as a result of the function being unregularized, and thus likely non-strongly convex, the step-size and upper-bound could be continuously increasing.
6 Conclusion
In this paper, we propose AI-SARAH, a practical variant of stochastic recursive gradient methods. The idea of design is simple yet. powerful: by taking advantage of local Lipschitz smoothness, the step-size can 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 casily implemented in practice. Our algorithm is tune-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 reper-parameters.
Acknowledgments
The work of P.R. was partially supported by the KAUST Baseline Research Fund Scheme and by the SDAIA-KAUST Center of Excellence in Data Science and Artificial Intelligence. The work of M.T. was partially supported by the LIBZUA-WISS research grant.
4please see httpter//yyrrracccooooo//tttttba for Pytorch built-in optimizers.
12

---

Published in Transactions on Machine Learning Research (02/2023)
References
Yoshua Bengio. Rmsprop and equilibrated adaptive learning rates for nonconvex optimization. corr abs/1502.04390 04900, 2015.
Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223-311 311, 2018.
Chin-Chung Chang and Chih-Jen Lin. Libsvm: library for support vector machines. ACM transactions intelligent systems and technology (TIST), 2(3):1-27, 2011.
Ashok Cutkosky and Francesco Orabona. Momentum-based variance reduction in non-convex sgd.
arXiv:1905.10018 2020.
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.
Ryan D'Orazio, Nicolas Loizou, Issam Laradji, and loannis Mitliagkas. Stochastic mirror descent: Convergence analysis and adaptive variants via the mirror stochastic polyak stepsize. arXiv:2110.15412, 2021.
Benjamin Dubois- Taine, Sharan Vaswani, Reza Babanezhad, Mark Schmidt, and Simon Lacoste-Julien. Svrg meets adagrad: painless variance reduction. Machine Learning, pp. 1-51, 2022.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(Jul):2121-211 2159, 2011.
Saced Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. STAM Journal on Oplimization, (3(4):2341-23666 2013.
Robert M Gower, Peter Richtárík, and Francis Bach. Stochastic quasi-gradient methods: Variance reduction via. jacobian sketching. Mathematical Programming, pp. 1-58, 2020.
Robert M Gower, Othmane Sebbouh, and Nicolas Loizou. Sgd for structured nonconvex functions: Learning rates, minibatching and interpolation. AISTATS, 2021.
Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. Sgd: General analysis and improved rates. In International Conference on Machine Learning, pp. 5200-5209, 2019.
Geoffrey Hinton, Nitish Srivastava, and Kevin Swersky, Neural networks for machine learning lecture 6a overview of mini-batch gradient descent. Cited on, 14(8):2, 2012.
Samuel Horváth, Lihua Lei, Peter Richtárik, and Michael I. Jordan. Adaptivity stochastic gradient mothods for nonconvex optimization.
(tti::2002.035500 2020.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in 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. arXim:2006. 1177, 2020.
Diederík Kingma and Jimmy Ba. Adam: A method for stochastic oplimization. In ICLR, 2015.
J. Konečný, J. Liu, P. Richtárik, and M. Takáč. Mini-batch semi-stochastic gradient descent in the proximal setting. IEEE Journal of Selected Topics in Signal Processing, 10(2):242 255, 2016.
Bingcong Li and Georgios B Giannakis. Adaptive step sizes in variance reduction via regularization. 110::910.00655 2019.
13

---

Published in Transactions on Machine Learning Research (02/2023)
Bingcong Li, Lingda Wang, and Georgios B. Giannakis. Almost tune-free variance reduction. In Proceedings of the 37th International Conference on Machine Learning, volume 119, pp. 5969-597777 PMLR, 2020.
Shuang Li, William J Swartworth, Martin Takáe, Deanna Needell, and Robert M Gower. SP2: second order stochastic polyak method. TCLR, 2023.
Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. arXiv:1805.0811 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:1908 08265, 2019a.
Yan Liu, Congying Han, and Tiande Huo. A class of stochastic variance reduced methods with an adaptive stepsize. 2019b. URL http::/t://wt httt:::/www.optmml/et www.oopptttitotoooooooo commiizaiiooonninne htt.a//.rrr/BB.LLLL////////////1
Nicolas Loizon and Peter Richtárik. Lincarly convergent stochastic heavy ball method for minimizing generalization error. 17X00 10737, 2017.
Nicolas Loizou and Peter Richtárik. Momentum and stochastic momentum for stochastic gradient, newton, proximal point and subspace descent methods. Computational Optimization and Applications, 77(3): 653-710, 2020.
Nicolas Loizou, Sharan Vaswani, Issam Laradji, and Simon Jacoste-Julien, Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence. AISTATS, 2021.
Eric Moulines and Francis Bach. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. In Advances in Newral 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(():549-55) 573, 2016.
Arkadi Nemirovski and David B. Yudin. Problem complexity and method efficiency in oplimization. Wiley Interscience, 1983.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. STAM Journal on Optimization, 19(4):1574-109) 2009.
Lam Nguyen, Phuong Ha Nguyen, Marten van Dijk, Peter Richtárik, Katya Scheinberg, and Martin Takáč. SGD and hogwild! Convergence without the bounded gradients assumption. Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 3750 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 Conference on Machine Learning (ICML 2000), volume 70, pp. 2613-2621, International Convention Centre, Sydncy, Australia, 2017. PMLR.
Antonio Orvicto, Simon Lacoste-Julien, and Nicolas Loizou. Dynamics of sgd with stochastic polyak stepsizes: Truly adaptive variants and convergence to exact solution. In Advances in Neural Information Processing Systems.
H. Robbins and S. Monro. A stochastic approximation method. The Annals of Mathematical Statistics, pp. 400-407, 1951.
Abdurakhmon Sadiev, Aleksandr Beznosikov, Abdulla Jasem Almansoori, Dmitry Kamzolov, Rachael Tappenden, and Martin Takáč. Stochastic gradient methods with preconditioned updates. arXiv:2206.002 00285, 2022.
M. Schmidt, N. Le Roux, and F. Bach. Minimizing finite sums with the stochastic average gradient. Math. Program., 162((-2):83-11) -12, 2017.
14

---

Published in Transactions on Machine Learning Research (02/2023)
Shai Shalev-Shwartz, Yoram Singer, and Nathan Srebro. Pegasos: primal estimated subgradient solver for SVM. In 24th International Conference. on Machine Learning, pp. 807-8144 2007.
Iya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. Tn International conference machine learning, pp- 1139 1147. PMLRR 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, F. d' Alché-Bue, E. Fox, and R. Garnett (ods.), Advances in Neural Information Processing Systems, volume 32, pp. 3732 3745. Curran Associates, Inc., 2019.
Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence over nonconvex landscapes. 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.oor/11..0000 20220.0...7.
15

---

Published in Transactions on Machine Learning Research (02/2023)
Appendix
The Appendix is organized follows. In Section we present the technical details of thcoretical analysis in Section 3 of the main paper. In Section B results of our numerical experiments.
we present extended details the design, implementation and
A Technical Results and Proofs
We consider finite-sum optimization problem
P(w) def n Σ Ji(w)
min wERd
(10)
Assumption A.1. For
0, each ft is L4-smooth the line segment
A
Rd -= wi me,, An
0, 1 L
and convex. For simplicity, denote
17 = max DA L :E[n]
1 LM = max L.. Σ
(E.
Note that Section 3 of the main paper, we use L universally for both maximum and average value of parameters local Lipschitz smoothness. In this section, as we will present Algorithm D two specific forms: importance sampling version (see Algorithm 3) and uniform sampling version (see Algorithm we use different notation on the average, i... L -. L.
Assumption A.2. Function P is p-strongly convex.
Definition A.3. Fix outer loop A and consider Algorithms 1 and 4 with an inner loop size m, we define a discrete probability distribution at t 2 for all í E [n]. pf Σn D
and probabilitics qe for all
q:
Tt. H
where H. E}= Th
A.1 Theoretical AI-SARAH with Importance Sampling
We present the importance sampling algorithm Algorithm lemmas that extending the lemmas in Nguyen al.
3 Now, let us start by presenting the following 2017 for the SARAH algorithm.
Lemma A.4. Consider Ur defined in Algorithm 3 Then for ang 1 in Algorithm it holds that
E| V - vell = Σ Elloy -
1-11119
E Bl)w))() VP(W;-1)11)
Proof. Let Ey denote the expectation by conditioning the information Wo. wT, ....... ., wy well Up, U1, . 1y-1- Then,
( - -y = [| PP(w;-1)) (wg 13 P(
+ E,llu; - Uz-1
+2(VP(W5-1) - 11-1, VP(w,) (P)-,, - VP(w,-1)}
-2 -2(VP(u)-1)- 1y-1, - B,y -1--1)
-
- 2 -((VP(w,) - E/ - w)-=l)
/V(w)) - = [E/(/\)( - - -
vP(Wy-1)1
+ E, 11
(11)
16

---

Published in Transactions on Machine Learning Research (02/2023)
Algorithm Theoreeiial-Al--AAAAA with Importance Sampling
Parameter: Inner loop size m
Initialize: the
3: for A: = 1, do
4:
1
5: e0 = P(Ww))
6: for E [n] do
T. max nelo, T.)
V - ryca)]
end for
L = D Li and no
1
10:
for 1 = 1...,, m do
11:
Wt = Wt-1 P
Sample 4 from [n] with probability pi 1-1
12:
13:
U = = + np: (w)) (wt(()))))
14:
for i E [n] do
15:
Li max
V filwi m72))l
16:
end for
17:
L' Ei=1 1
18:
Th min It Le n--
19:
end for
20:
Set ūy w, where is chosen with probability di from {0, 1, m]
21:
end for
where the last equality follows from
E,(u, U--1] Ej
(V.i,(w;)) Vf., (wy-1))
Fi j-1
(W)) (1,((1,1)))
np,
P(W,)) - VP(wj-1)-
(12)
By taking expectation of
11
we have
E VP(w) by [[]]][[[[[[]]]] - - |
(0-- VP(W)-))1
+ Eillu, 11
By summing it over I...., and note that VP((v)) - =ollz = 0, we have
E V((w)) - 1x [=] =
Bllog 1
E
1=1
1=1
Lemma A.5.
Pix outer loop 1: and consider Algorithm with Wt S $1/l/ for any E [m]. Under
Assumption A.1
< E[P(w)) - P(w") [[
+
Σ
Th E (( -
17

---

Published in Transactions on Machine Learning Research (02/2023)
Proof. By Assumption A.1 and the update rule wy Wt-1 1 of Algorithm 3
obtain
-'-1
P(we)) - P(w+-1) 1) - - (VP 2--1) +
2 1/ 11/2/111
= P(w)-1)
7|-1
)l( +
P (( 11-111
2
2
-'-1
11811
2 11i-
1|12-111,
where, in the equality above, use the fact that (a, b) 1 (1|aa|2 |b] ||a 3).
By assuming that 7/-1 S ze-1 it holds that (1 -'- 1p-1 0, Vt [m]. Thus,
- 2
VP(W:-1)]
(P(w--1) - P(we)] + 76-1 VP(w--1) 1211
2
M-- (1 (--1)-1) 101-111?
2
By taking expectations
El
M|-1
|VP(
- B[P((w)]]
1/=1
E||
V 1--1
2
2
M-- 1
(1 I,- -,'-1 11)
EE|
11
9- 1 --11
nh- E VP (1-1) 11111
2
Summing over 1,2..... ,m + 1, have
m+1
m+1
m++
Σ B
Σ
E E[P(w,11) P(w))
1/1
E [P 12-1
2
m+1
[[P((u)- P(um+1)] +
T-- E| VP(w,-1) - 1211
m+1
(((wo) - P(w.)] +
1|-
P - vz 112}
2
where the last inequality holds since w" is the global minimizer of P. The last expression can be equivalently written as
m
m
- P(w.)] )]
Σ
Th
E PPww) - -v,l1
which completes the proof.
Lemma A.6. Consider Algorithm with min 1 E1-1
Te nt mn-1 }
Suppose fi is conver for all i [n].
Then, under Assumption A.1 for any 2 1,
Io
E P(w:))
-xl1
Elllvo [[]]
Lo
18

---

Published in Transactions on Machine Learning Research (02/2023)
Proof.
1
E, [|] - By
|1u311
(Vii, (10--1) - 1|
np!
1110-1112 + B3
|1 Vii (w)-1) - (w))()))) 2
(npi-1
2
V Vii w1y -mrg)
17p-1
1
< ||05~111 B
Vfr, (w--1) - Vn, (1cy)))
{mp) -1p
2
153
V (w--1) - (w,))1
11pp
For each outer loop k 2 1, it holds that 11,1 =np," - - Thus,
1 (V
B 129] S ||0 112 + +B,
npp-1
2
1
1/5-1 1 II-1 BB
(Vi (w)-1)
V (wx))
mpp
2
1
110/-1112+ +
11
1
R
(iii (w--1) (w5))
\/j-1 [
np'
|10y_111 11 +
1
2
Ej
|10 U |2]
1 1
< ||0z-1|| +
E3
||05 Uパ 12]
f/j - D
By rearranging, taking expectations again, and assuming that 17/-1 < <2/i/-1 for any from 1 to t + 1
[ 7 D
Ell Uy 12] E
[10,
2 2- M2 15-1
By summing the above inequality over j = I,...,t (t 2 1), we have
?) I i-
Bille, 1 -
E
[11g)-112- ||0/|12]
2 T
Th 1i-1
/=1
To
77- T, 11
E [[110||2]
E [[]ve]]]]]
Zo
71 I 11-
1] 175-1 -
17 1'
E
|115 122)
2 - nz- n T161
2 - n3 T5
Io
E
[1|10 1[]
(13)
19

---

Published in Transactions on Machine Learning Research (02/2023)
Now, by using Lemma A.4 and
13
obtain
To
(ww,) v
v
Σ
E
-0-111
IP [[]]6]1]]
2 To
1=1
Using the above lemmas, we can present one of our main results in the following theorem. Theorem A.7. Suppose that Assumptions A.
A.2 holds. Let us define
Lo
117t
2
no
and select m and such that om < 1. Then, Algorithm
converges follows
k
II dt
||P((
Proof. Since P(wp) implics
[VP(w)) - uoll2 = 0, then by Lemma A.6 we obtain
no L
R V( - v211 -
E B|
H
1/0 L
Combine this with Lemma
A.5
we have that
(w))
E[P(wo) - P(w.][ }]
Σ
?1
E B - 1²
H
H
H
1=0
L
E E( (w0) P(w.)] 2 1
E El[/00133
Since we consider one outer loop, with 2 1, we have un = (Pww)) = P( and 20, = we where t is drawn at random from L..1...., m) with probabilities ge. Therefore, the following holds,
m m
E V
P(w:))1
H
2
No I
< E ((m)-11) - P(w.)]
71
1. T.
+
E|
HiH
2 - 70o0
Let us define Jh = =(11e WH
To then the above expression be written as
+
2 no
E[IVP((0>)11 S (() )..
By expanding the recurrence, we obtain
[[o of ||P((0))11
This completes the proof.
20

---

Published in Transactions on Machine Learning Research (02/2023)
A.2 Aeeoretical-Al-SARAAA with Uniform Sampling
We present the uniform sampling algorithm in Algorithm Now, let us start by presenting the following lemmas.
Algorithm 4 Theorctial-A--SARRF with Uniform Sampling
Parameter: Inner loop size
Initialize: dñp
3: for k = 1, do
4: Wo = 1ik1
5: Up = P(wp)
6: for E [n] do
L max (b) || fiwwo ry6)
8:
end for
9:
L = maxie(m]
L and 1lo 7
1
10:
for 6 t .,... m do
11:
Wt = Wt-1 - 1
12:
Sample 4 uniformly at random from [n]
13:
et ut- Vi, (w,) Vfa(
14:
for i E [n] do
15:
4 m
V filw- spu:)ll
16:
end for
17:
T, max
18:
? = min
-= [t L 1
19:
end for
20: Set ūy w, where is chosen with probability from {0, lQ..,..,m m]
21: end for
Lemma A.8. Consider vs defined in Algorithm Then for any in Algoritho it holds that
E V[ww) - 0z = El 1l - 1
-VP())))
Proof. The proof is the same as that of Lemma A.4 except that we have pl, 5-1 1/2 in 12 for uniform sampling.
Lemma A.9. Fir outer loop lo 2 1 and consider Algorithm 4 with S 1/T1 for any E [m]. Under
Assumption A.1
m m P(w")
T E V )
(w;)
VP:()) vzl13].
Proof. By Assumption A.1 and the update rule u; w M2- 1 of Algorithm we obtain
-1-1 24 +
P(w.) S P((+-11 - 7/- (V
./-11 ||
= =((W--) - 7/-
| 11
17-1
|| //W v--1
2
2
M1-1
T
1h-1 1|
2 2
where, in the equality above, the fact that (a, b) 1 (11a|12
||b||2 ||a b).
21

---

Published in Transactions on Machine Learning Research (02/2023)
By assuming that 7/-1 S LeI,, it holds (1- 1----1n-1) 2,, Vt E [m]. Thus,
1 2
VP(W S [P(w--1) - P(w))] + ?h-
VP(w[-1) 1--1
2
1 (1 - I, I m 11--111
2
By taking expectations
(P(W 1|1 E[ 1) E3
P((x))
- B
P(w: -
2
2
Th-
-1- 1)
11122-11111
2
15 E[P(()
Ne-1
([ 0c-1113).
2
Summing over == 1.2....., m + 1, we have
m+1
B
V > Σ B[P(w+-1) P(w.)]
V 11-1
2
2
m+1
E[
P(wm+1)]
7--1
E|| VP(ww-1) - 12-1
m+1
- - P(w.)] Th-
E [P]I - - 113)
where the last inequality holds since w" is the global minimum of P. The last expression can be equivalently written as
1t 2
< - P(w.)]
Σ
1)t E 2
VP(w;) - =
1=
which completes the proof.
Lemma A.10. Consider Algorithm with n = min {
1 D
m-13.
Suppose ft is convex for all i e [n].
Then, under Assumplion 1 for any 221, 1,
Bl] -1
Elllyp 122].
2 Io
Proof.
Ei [||yy| 12] < E,, [|05- (V (/) [|2]
= ||
2 + F,, [[[ V/ (11-1) V/, (w;))
2
E2,
V (w V,, (w,) wy-1- ww,)
< ||0
2 + Ei,
V St (wy-)) v/,, (w])
E2
V fi, (wy-1) 1) - (1,55)1
M 1
22

---

Published in Transactions on Machine Learning Research (02/2023)
For each outer loop k 2 1, it holds that L D- Thus,
Es, || uy || - || + Big
|| V Vi V.,,, (w,) ||
2
Rig V (wz--1 - Vii, [1
7/ 7 Li-1
1|/
+
Big || (wy- V (1x |19
11j 1,-1
||u5-111" +
1
Big |10 リー 11
S ||u5-1|1
1
Big |10g Uj 11
11 1
By rearranging, taking expectations again, and assuming that 17,-1 < 2//2² for any from 1 to + 1,
Ell - u 1 12] E
Mj ---- (-
1
|10, [|0,]13]
By summing the above incquality over j l,...,t (t 2 1), we have
15-1-5-1
Σ
Billy
---11
S
E
11 ||0s113]
2
1=1
3=1
Io
1/- -
E [[[16|1²]
[[]x]1]]]
noLo
2 1--1---1
Mi Mi-1 1
Ii I
E
||0, ||0,
2
T/ 1
2 - 11 13
==1
no Lo
E [1]
(14)
Io
Now, by using Lemma A.8 and 14
we obtain
E
(w:))
2 -
[lle, - 1
/=1
oo noLo
E [[lva 12]
2
Using the above lemmas, we can present one of our main results in the following theorem. Theorem A.11. Suppose that Assumption
A.
A.g. holds. Let us define
Lo
ot
47 +
2 - moL
and select m and such that th < 1. Then, Algorithm converges as follows
k II 1=1
E (((x))11
<
o [VP(W)))12
23

---

Published in Transactions on Machine Learning Research (02/2023)
Proof. Since to ((wb) implies P(w)) zull2 0, then by Lemma A.10 obtain:
7000
- - -
E B1lloo11
H
2 10
Combine this with Lemma A.9
we have
E
S E[((wo) - P(ww)]] [].,]]++
Σ
E B =rll²]
H
1=0
1/0 L
T2 [P[((oo) (w0) P(w.)] 2 Io
E. [
Since consider outer loop, with k 2 1, have (Www) v((ūk-1) and wR we, where t is drawn at random from {0, 10.1..... m) with probabilities 9.. Therefore, the following holds,
m
m
P(w:)11
H
2
70
- E
P (i - P(w.)l
V
71
2 Lo
Lo
+
B (
H.H.
2 - 7oLo
Let us use of ( + 2-
then the above expression can be written
E E|| -
By expanding the recurrence, we obtain
B[]VP(@w)]?1 2 [Io, o' ||
This completes the proof.
24

---

Published in Transactions on Machine Learning Research (02/2023)
B Extended details on Numerical Experiment
In this section, we present the extended details of the design, implementation and results of the numerical experiments.
B.1 Problem and Data
The machine learning tasks studied in the experiment are binary classification problems. As a common practice in the empirical research of optimization algorithms, the LIBSVM datasets are chosen to define the tasks. Specifically, we selected 10 popular binary class datasets: ijennd, rev1, news20, covtype, real-sim, ala, gisctte, wla, w8a and mushrooms (sec Table 2 for basic statistics of the datascts). Please note that these datasets do not contain personally identifiable information or offensive content.
Table 2: Summary of Datascts from Chang & Lin (2011)
Datasct d (# feature)
(# Train)
Neest (# Test)
% Sparsity
tjennl
22
49,990
91,701
40.91
rcul
47,236
20,242
677,399
99.85
news202
1,355,191
14,997
4,999
99.97
coutype"
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
giselle 5,000
6,000
1,000
0.85
wla 300
2,477
47,272
96.11 11
w8a
300
49,749
14,951
96.12
mushrooms"
112
6,093
2,031
81.25
dataset has default training/ /testing samples. 2 dataset is randomly split by 75%-ttriinng 25%-testing.
B.1.1 Data Pre-Processing
Let (X,, Mi) be training (or testing) sample indexed by i E [n]] (or E [Mttst]), where X; E Rd feature vector and ys is label. We pre-procossed the data such that X; is of unit length in Euclidean norm and y1 (1}.
B.1.2 Model and Loss Function
The selected model, h; Rd + R, is in the lincar form
ha(w,e) = x7 te, We
(15)
where w Rd-1 is weight vector and R is bias term.
For simplicity of notation, from now on, we let 24 def X 112 E Rd be an augmented feature vector, w def (TT ej E Rd be a parameter vector, and ha(w) = x7 w for i i [n].
Given a training sample indexed by E [n]. the loss function is defined as a logistic regression
f.w)) log(1 + exp(-y;h; A ||wl122
(16)
In 16 [ is the &-regularization of a particular choice of >> 0, where we used X 4 in the experiment; for the non-regularized case, X was set to 0. Accordingly, the finite-sum minimization problem aimed to solve is defined
min P(w) def Σ CAw) R "
(17)
1=1
LIRSVM datasets available htttps://ww..... csie. wtt..a...d.......iii/iiiiieeeee. htt.:/ttdd.......//////////t/aaa
25

---

Published in Transactions on Machine Learning Research (02/2023)
Note that 17 is convex function. For the -erguularized case, i.c. A 1/n in 16
17 is p-strongly convex
and / However, without the (-regularization, i.e., À = 0 in 16 17 is -u-strongly convex if and only if there there exists μ > 0 such that P2((w) = pl for w E Ra (provided VP(w) EC).
B.2 Algorithms
This section provides the implementation detail of of the algorithms, practical consideration, and discussions.
B.2.1 Tune-free AI-SARAH
In Section 4 of the main paper, we introduced AI-SARAH (sce Algorithm 2). tune-free and fully adaptive algorithm. The implementation of Algorithm 2 was quite straightforward, and we highlight the implementation of Line 10 with details: for logistic regression, the one-dimensional (constrained optimization) sub-problem min,:00r(0m can be approximately solved by computing the Newton step at (0
a = 0, i.., á = [o This can easily implemented with automatic differentiation in Pytorch and only two additional backward passes w.r.l a is 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 Section 4 we have an adaptive upper-bound, i.c., Omaz: in the algorithm. To be specific, the algorithm starts without an upper-bound, i.e., O'maz = oo on Line 3 of Algorithm 2 Then, Omar updated per (inner) iteration. Recall in Section 4 Omar is computed as a harmonic mean of the sequence, i.e., {āz-1), and an exponential smoothing applied on top of the simple harmonic mean.
Having an upper-bound stabilizes the algorithm from stochastic optimization perspective. For example, when the training error of the randomly selected mini-batch at we is drastically reduced or approaching zero, the one-step Newton solution in (9) could be very large, i.e. â > O, which could be too aggressive to other mini-batch and hence Problem [I] 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 a large step-size when the algorithm tries to make aggressive progress with respect to Problem ( With the adaptive upper-bound being derived by 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 mention that Algorithm 2 does not require computing extra gradient of fs. with respect to if compared with SARAH and SARAH+. At each inner iteration, > 1, Algorithm computes fss, (wa-1 au4-1) with 0 just as SARAH and SARAH+ would compute (w:-)), and the only difference is that a is specified as variable in Pytorch. After the adaptive step-size 0:-1 is determined (Line 17), Algorithm computes fs, Q1-1Ut-1) just as SARAH and SARAH+ would compute ffs (wx).
In Section of the main paper, we discussed the sensitivity of Algorithm 2 on the choice 7. Here, we present the full results (on 10 chosen datasets for both (e-regularized and regulagulrr cases) in Figures 10 and 11 Note that, in this experiment, we chose 7 ( 32 1s: 81 1 1), and for each 7, dataset and case, used 10 distinct random seeds and ran each experiment for 20 effective passes.
B.2.2 Other Algorithms
In our numerical experiment, 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 methods: SARAH, SARAH+, SVRG, ADAM and SGD with Momentum (SGD w/m). These algorithms were implemented Pytorch, where ADAM and SGD w/m are built-in optimizers of Pytorch.
6Scc code at
hwwp:a/wwc.aaaaihhhoooneeeeeeeee wwwwehh/aarrrrrrrrraraaaaaaaaaa _arah
For detailed description the automatic differentiation engine in Pytorch, please attp:://pptorch.or//tttrrrr beggimer//blttz/snttggrad http:raalddtttrraallatt
26

---

Published in Transactions on Machine Learning Research (02/2023)
Jcnn1
rCV1
real-sim
news20
covtype
072
1/32
66-
3.50
3.72
13
182
64-
04
840
032
10.
33.4
1011
Acconne
61-
Effective
Erfectivn
Effective Pass
Eifective Pass
Effective Pars
Figure 8: P-regularized case ijennl, reel, real-sim, news20 and covtype with E ( 32 T6 2+ evolution of P(w) (top row) and [VP(w)]] (middle row) and rumning maximum of testing accuracy (bottom row).
ala
gisette
wla
w8a
mushrooms
0.70
122
184
0.50
0.-
366
0:00
83
33
0/5
0.5
63
10"1
1071
15"
36-2
10-2
10
104
11-
Accurscy
66-
Effective Pass
Enecctive Pass
Eftective Pads
Eftective Pass
Effective Fats
Figure 9: P-regularized case ala, giselle, wla, wSa and mushrooms with E ( 32 16 31 evolution of P(w) (top row) and ||V[())]] (middle row) and running maximum of testing accuracy (bottom row).
27

---

Published in Transactions on Machine Learning Research (02/2023)
Jcnn1
rCV1
real-sim
news20
covtype
0.70
0.75
132
P100
33-
0.75
0700
0.53
157
10-1
16.4
16.4
16-
6.1
37-
66-
06-
0.5
64
Effection
Erfective
Effective Pass
Effective PAss
Effective Pars
Figure 10: Non-regularized case ijennl, reul, real-sim, news20 and covtype with 7 ( 32 T6 2 evolution of P(w) (top row) and [VP(()]] (middle row) and rumning maximum of testing accuracy (bottom row).
ala
gisette
wla
w8a
mushrooms
1/54
0.00
1152
3.
33
02
10'1
31
10-2
10-
10"
10.4
Accurocy
0.3
Efrective Pass
Effective Pass
Eftective Pads
Eftective Pads
Effective Fats
Figure 11: Non-regularized case ala, giselle, wla, w8a and mushroomms with 7 E ( 32 8: 3: evolution of P(w) (top row) and [[V]( (middle row) and running maximum of testing accuracy (bottom row).
28

---

Published in Transactions on Machine Learning Research (02/2023)
Table Tuning Plan Choice of Hyper- pappeeeera.eters..
Method # Configuration
Step-Size
Schedule (%6) Inner Loop Size (# Effective Pass)
Early Stopping (7)
SARAH
160
00.1,022..
11/L
n/a
{0.5, 0.6.
n/a
SARAH+
(..1,0.2,.. .... 13/L
n/a
n/a {0.5, 0.6, ...,..... ....) 2) n/a
1/(2, 4,8, 16, 32]
SVRG
160
00.1,0.,,... ..., 11/L
1/a
n/a
ADAM
300
10 1,0-3,10 10]
{0. 1, 10, 15)
n/a
SGD w/m²
300
[10-3.1 100
(0, 1,,,,,11,, 15)
n/a
n/a
1 Step-size is scheduled decrease by X% every effective pass over the training samples. 2 81 0.9, 0.999.
8 0.9.
Table 4: Running Budget (# Effective Pass).
Dataset
Regularized Non-regularized
ijenn1
20
20
reul
30
40
news20
40
50
costype
20
20
real-sim
20
30
ala
30
40
gisette
30
40
wla
40
50
w8a 30
40
mushrrooms
30
40
peper-parameter tuning. For ADAM and SGD w w/m, we selected 60 different values of the (initial) step-size on the interval [10-3 10] and 5 different schedules to decrease the step-size after every effective pass the training samples; for SARAH and SVRG, selected 10 different values of the (constant) step-size and 16 different values of 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, we chose different values of the inner loop early stopping parameter. Table 3 presents the detailed tuning plan for these algorithms.
Selection créteria:
We defined the best paper-parameters the ones yielding the minimum ending value of the loss function, where the running budget is presented in Table 1 Specifically, the criteria are: (1) filtering out the ones exhibited a "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 oncs achieved the minimum ending value of the loss function.
Hightlights of the hyper-parameter search:
To take into account the randomness 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.
Tables 5 and 0 present the best hyper-parameters selected from the candidates for the regularized and non-rogularized cases.
13 14 and 15 show the performance of different hyper-parameters for all tuned algorithms; it 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
Figures 12
Global Lipschitz smoothness of P(w). Tuning the (constant) step-size of SARAH, SARAH+ and SVRG requires the parameter of (global) Lipschitz smoothness of P(w), denoted the (global) Tipschitz constant T.,
29

---

Published in Transactions on Machine Learning Research (02/2023)
Table 5: Fine-tuned Hyper-parameiie P-reglaaried Case.
Dataset
ADAM
SGD w/m 2%)
SARAH
SARAH+
SVRG
(arg, x%)
(a, m)
(a, 7)
(a, m)
ijenn1
(0.07, 15%)
(0.4, 15%)
(3.153, 1015)
(3.503, 1/32)
(3.503, 1562)
rcul
(0.016, 10%)
(4.857, 10%)
(3.924, 600)
(3.924, 1/32)
(3.924, 632)
news22
(0.028, 15%)
(6.142, 10%)
(3.786, 468)
(3.786, 1/32)
(3.786, 468)
cootype
(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)
w8a
(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: Finc-tuned Hyper-parametors Non-regularized Casc.
Dataset
ADAM
SGD w/m
SARAH
SARAH+
SVRG
(ap, 2%)
(ag.*%)
(a,m)
(a,
(a, m)
ijenn1
(0.1, 15%)
(0.58, 15%)
(3.153, 1015)
(3.503, 1/32)
(3.503, 1562)
revl
(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)
30

---

Published in Transactions on Machine Learning Research (02/2023)
ijcnn1
rcv1
real-sim
news20
covtype
25.0
P(W)
10.0
12
1.0
5.0
0.5
0.0
100
1014
20.4
10-h
1019
10-4
16-9
10
10-1
10tM
10-
16-7
20-0
0.988
0.45
0.529
Accuracy
0.875
2.825
0.00
3,10
0.6
3.05
0.70
SWYG
Ada
GG0 km
5050lte
SHNHH
Adm
SANAH
SWNS
500
Figure 12: Ending loss (top row), ending squared norm of full gradient (middle row), maximum testing accuracy (bottom row) different hyper reo1, real-sim, news20 and contype datasets.
hyper-paranters paramters and algorithms for the ('-reglaaried case on ijennl,
ala
gisette
w1a
W8a
mushrooms
0.6
1.0
0.5
3.0
P(w)
0.4
0.6
0.4
0.2
0.2
3.
1214
10-1
10
[|PO)||]
12-4
30-1
12:4
1214
10'4
12-4
20.
0.84
0.46
8.4000
1.00
6.94
0.925
Accuracy
0.82
0.92
53000
5.92
0.00
3.473
9.974
2.9755
0.8
6.92
0.78
0.82
1.925
c:5700
SANG
ddm
SACAY
Mam
00541
SYTIC
Adm
5DD Am
50001
SAMH+
Adm
900 Am
500
Figure 13: Ending loss (top row), ending squared norm full gradient (middle row), maximum testing accuracy (bottom row) of different syper-paramters and algorithms for the L e-rreularizeed case on ala, gisette, wla, wsa and mushrooms datasets.
31

---

Published in Transactions on Machine Learning Research (02/2023)
ijcnn1
rcv1
real-sim
news20
covtype
1.75
1,50
5.5
1.4
0.8
3.25
6.5
3.4
P(
1.4
0.8
6.
10-1
10-1
14-4
10-2
10
10.
1079
[|P(0]]
10-4
10-1
10
12-4
10
20-11
16-0
20-4
10"
10-4
10:14
10:1
8.955
0,930
Accuracy
3.905
0.00
8,000
3.855
0.80
3.055
6.70
SWYG
Adam
GG0 wm
50500te
500 wm
Adm
SANHH
SGO wm
5G0
Figure 14: Ending loss (top row), ending squared norm of full gradient (middle row), maximum testing accuracy (bottom row) of different paramters and algorithms for the non-regularized case on ijennl, reef, real-sim, news20 and contype datasets.
a1a
gl glse
w1a
W8a
mushrooms
2.0
1.9
2.0
0.3
0.4
P(W)
0.9
3A
0.2
0.2
0.2
0.1
0.2
10-
12-4
12-4
12-1
10
2214
10
11"
10
12-
10"44
1.00
0.86
3,450
0.98
0.90
Accuracy
3.300
0.990
0.94
0.78
5.175
0./
0.66
3.00
0.89
Abm
am
Aam
Alm
Adm
Figure 15: Ending loss (top row), ending squared norm full gradient (middle row), maximum testing
accuracy (bottom row) of different haper-paramters and algorithms the non-regularized case on ala, gisette, wla, w8a and mushrooms datasets.
32

---

Published in Transactions on Machine Learning Research (02/2023)
Table 7: Global Lipschitz Constant L
Dataset
Regularized
Non-regularized
Ejennl
0,285408
0.285388
reul
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
giselle
0.430994
0.430827
wla 0.274215
0.273811
w8a
0.274301
0.274281
mushrooms
0.372816
0.372652
and it can be computed as, given 16 and
1 L Amarl
m: )
+ X,
where Amar (A) denotes the largest eigenvalue of A and is the penalty term of the e-regularization in Table 7 shows the values of L for the regularized and non-regularized cases on the chosen datasets.
16
33

---

Published in Transactions on Machine Learning Research (02/2023)
D2V0ypa
2210
10
10-13
23
32-11
gisettle
WiBk
muuhhrorms
10
10-
321
30.1
43 Percentl
40
302
Pe Percooiie
Porcerile
Perconilo
Percerilc
Figure 16: Average ending P()((]) for e-regularized case AT-SARAH vs. Other Algorithms: AT-SARAH is shown as the horizontal lines; for each of the other algorithoss, the average ending [[V from different configurations of hyper-paranen parameters are indezed from percentile (the worst choice) to 100 percentile (the best choice); see Section B.2.2 for details of the selection criteria.
B.3 Extended Results of Experiment
Section 5 we compared tune-free & fully adaptive AI-SARAH (Algorithm 2 with fine-tuned SARAH, S SVRG, ADAM and SGD w/ w/m. In this section, we present the exlended results of our empirical study on the performance of AI-SARAH. For the experiments, we used NVIDIA V100 GPUs.
Figures 16 and 17 compare the average ending [[w][]]] achieved by AI-SARAH with the other algorithms, configured with all candidate hyper-parameters.
It 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 a better result for the non-regularized case on ala, gisette, wia and mushrooms, AI-SARAH outperforms ADAM for at least 80% (ala), 55% (gisette), 50% (wla), and 50% (mushrooms) of all candidate hyper-parameteer.
Figure shows the results of the non-regularized case for ijennl, revl, real-sim, news20 and coutype datasets. Figures 19 and 20 present the results of the ee-reuulaiized case and non-regularized case respectively on afa, gisette, wla, w8a and mushrooms datasets. For completeness of presentation, we present the evolution of AI-SARAH's step-size and upper-bound on ala, gisette, wla, w8a and mushrooms datascts in Figures 21 and 22 Consistent with the results shown in Section 5 of the main paper, AI-SARAH delivers a competilive performance in practice.
34

---

Published in Transactions on Machine Learning Research (02/2023)
jecmnn
10V1
real sam
THNA20
codtyp
1214
3019
221
22
Percentlcc
Percertlc
Porce 1010
Percontlle
Perconte
gisette
10-1
1017
10
101T
20
00
Figure 17: Average ending [P(w))] for non-regularized case AI-SARAH Other Algorithms.
covlype
0.30
8.30
0.35
6.5
0.6
0.25
025
0.5
Sanane
0.20
6.0
6.2
Dyno
Acart
6.15
6:25
6.5
500 Al
6.00
6:26
638
356
6.05
8.66
815
0:00
0.10
816
Eftective
Effective Pass
Eftectivv Pass
Effective
Effective
ijcnn1
rcv1
real-sim
news20
covtype
13-1
10"1
110P00011
16th
15""
SARRE-
10-
502 w/m
Efrective Pads
Erfective Pads
Effectivv Pass
Efrective Pass
Efrective Past
[jcnn]
rcv1
real-sim
news20
covtype
6.65
Salder
AESARAH
0.10
SARAM-
0.90
0.58
0.39
0.55
15
Pass
Pass
Effective
Effective
Pass
Figure 18: Non-rogularized case: evolution of P(w) (top row), //V(( (middle row), and running maximum of testing accuracy (bottom row).
35

---

Published in Transactions on Machine Learning Research (02/2023)
ala
gisette
w1a
w8a
mushroams
0.2
S-SARA
644
640
643
500
635
0.4
0.11
6:0
632
0.0
0.50
0.00
0.86
10.1-
13a
30
10.1
10'--
10:11
6.44
6.5
0.120
Accorry
660
139
650
0.12
33
13
23
EFRective Pass
Effective Pass
Effective
Effective Pass
Effective Ploss
Figure 19: (-regularized case: evolution P(w) (top row), [|V (middle row), and running maximum of testing accuracy (bottom row).
ala
giselle
wla
w8a
mushroams
0.50
0.00
0.2
3.26
6475
Al- R-SAHAe SARAII
3.5
0.1
3115
0.6
3350
034
5CD
0.2
6375
6350
0.035
6108
3.255
3.1
0.035
3.800
10-1
22.5
32.
10'4
18*
381
38-1
116
2303
3.50
6078
0.5
0.20
2065
Pass
Figure Non-regularized case: evolution of P(w) (top row), [/V(( (middle row), and running maximum of testing accuracy (bottom row).
36

---

Published in Transactions on Machine Learning Research (02/2023)
ala
gisette
w1a
w8a
mushrooms
140
45
132
75
15
10
---
10
10
10
Effactive Pass
Effective Pass
Effective Posss
Effoctive Pass
Effoctive Pass
Figure 21: e-regularized case: evolution of AI-SARAH's step-size and upper-bound Oman
ala
gisette
wla
mushrooms
60-
230
10
1.0
125
10.0
130
--
Grexs
10
40
10
23
30
Effective Pass
Effective Pass
Effective Pass
Effective Pass
Effective Pass
Figure 22: Non-rogularized case: evolution of AI-SARAH's step-size a and upper-bound Omaaz
37


Reviews:
[{"review_id": "x9u5HO28QU", "reviewer": "Reviewer_sJon", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper has an extensive empirical evaluation against popular optimization methods. All error bars and the experimental setup are very explicit. The algorithm's theoretical version presents an improvement over the convergence guarantee for SARAH. \n\nThe authors don't compare their theoretical guarantee to any other algorithm variance reduced or not. Several tune-free variants of SGD have also emerged in recent years. For non-convex problems, SARAH is optimal, and thus it is reasonable to only compare against it for those problems. However, for strongly convex problems, what's the motivation for not comparing to other algorithms? Are there any relevant lower bounds for finite-sum optimization the authors can discuss? \n\nThere are no theoretical guarantees for the practical variant. Based on the approximations the authors suggest in section four, obtaining such a guarantee as a function of perhaps the accuracies for each of these steps seems possible. This might be useful even for a simple problem class like quadratic problems or logistic regression. \n\nOverall, I like the paper, but I believe a better comparison to some existing guarantees and some writing changes, which I suggest below, will improve the submission. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a tune-free variant of the SARAH algorithm for finite-sum optimization. The algorithm chooses a step size based on the local geometry of the problem and can thus adapt to changing flatness and sharpness of the loss landscape. The authors present a theoretical version of the algorithm and give a theoretical analysis that improves SARAH. However, the theoretical version is extremely expensive as it requires computing the Lipschitzness of the local hessian $tnk$ times in a ball determined by the step size (which itself depends on the local step size), where $n$ is the number of components in the finite sum, and $t,k$ are inner and outer iteration numbers. \n\nTo alleviate this, the authors present a lighter version of the algorithm, which only approximately computes this lipschitzness for just one component in each inner and outer iteration. No theoretical guarantees are provided for this lighter version, but it is extensively compared against the other baselines empirically. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. It would help to add explicit updates for different sampling strategies in algorithm one and retain the discussion in the following text. Currently, some lines are too abstract to make out what is happening in the algorithm, as the pseudo-code is not self-contained. These are mentioned in the appendix, but combining them in the main paper would be good. Line 13 is confusing because it only works for uniform sampling (again, algorithms 3 and 4 are more explicit and useful). It might also be helpful to highlight in a different color the implicit computations in the theoretical algorithm, which are very expensive, so that the changes made in the practical algorithm are easily comparable. \n\n2. Although two sampling strategies are proposed for algorithm 1, the authors are not explicit about which strategy is used for the guarantee in theorem 3.1. Based on the appendix, the result is for uniform sampling; this should be explicit. Also, it is unclear why the authors are presenting these strategies in the first place. The improvement with importance sampling: going from max to the average highest eigenvalue, is standard and doesn't seem surprising. The experiments seem to use uniform sampling as well. \n\n3. It is unclear why the gradient norm is relevant for regularized logistic regression, which is a strongly convex problem. AI-SARAH is competitive for minimizing function value but only outperforms the baselines for gradient norm minimization. Can the authors comment on why they include the norm minimization experiments? Similarly, the accuracy experiments are not helpful, as the paper is purely about optimization. Were the authors hoping to make some comments about the implicit regularization of their algorithm?\n\n4. It would be interesting to see some experiments which can underline the geometric adaptivity of AI-SARAH. Specifically, a synthetic experiment where the algorithms with any fixed step size perform poorly. I am curious how other adaptive methods, such as ADAM/ADAGRAD/RMSPROP (admittedly not tune-free), perform against AI-SARAH on such a task. \n", "broader_impact_concerns": "No broad impact concerns. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "j85cgnWyLK", "reviewer": "Reviewer_Eu4H", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The authors proposed a new strategy to adjust step-sizes based on local geometry, especially for the methods not necessarily moving along the descent direction.\n\n2. The efficiency is verified empirically by extensive numerical experiments on various datasets.\n\nWeaknesses:\n\n1. The authors only prove the convergence for the theoretical-AI-SARAH, which is not practical. No theoretical guarantees is provided for the more interesting AI-SARAH.\n\n2. The proof of Theorem 3.1 is almost the same with those in the original SARAH paper (Nguyen et al. 2017).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposed a practical variant of SARAH for strongly convex problems, which adjusts step-sizes based on local geometry with little extra cost compared with the original SARAH. The proposed method is tune-free, and numerical experiments demonstrate the efficiency comparing with other state-of-the-art methods with fine-tuned hyper-parameters.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. I would give a positive suggestion if the authors could provide more theoretical guarantees of (6). For example, it would be appreciated if the authros could prove the convergence of a variant of Algorithm 1, which only replaces lines 7 and 15 by (6).\n\n2. Other comments:\n\n1). The authors claimed that \"At every iteration, instead of incurring expensive costs on computing the parameters of local Lipshitz smoothness for all f i in Algorithm 1, Algorithm 2 estimates the local smoothness by approximately solving the sub-problem for only one $f_i$\". However, I think it is unfair to compare a theoretically correct algorithm to an empirical one. If we ignore the theoritical guarantees, it would be more nature to compute only one $L_i^t$ on lines 7 and 15 in Algorithm 1.\n\n2). I am not convinced that (6) approximates the local geometry. I think it searches the step size $\\alpha$ to minimize $\\|v_t\\|$, and accordingly, to minimize $\\|\\nabla f(w_t)\\|$ finally.\n\n3). it would be appreciated if the authros could provide more experimental resutls on the case of $\\beta=0$, which could remove the other tricks and only verify the efficiency of (6).", "broader_impact_concerns": "This is a theoretical paper and I think there is no ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "kzvKIBOT2A", "reviewer": "Reviewer_PreZ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength：1. The paper is well-motivated. The authors present an example demonstrating that we need to use the local Lipschitz smoothness property rather than the global one.\n\n2. The advantage of the proposed algorithm is obvious. The algorithm is adaptive and needs a few tunings. The presented numerical results show that the algorithm performs relatively well: the algorithm is faster than others with respect to both iterations and time.\n\n3. The algorithm is well discussed, including the convergence, results under different samplings, subproblems, and stepsize. Although the authors do not present the theoretical accelerations, existing convergence results are satisfying because they focus on developing a practical efficient algorithm. Indeed, I believe it is very difficult to prove the theoretical acceleration even with extra assumptions.\n\nWeakness:\n1. Sub-problem (10) in Algorithm 2 is vital for the algorithm. I appreciate that the authors present many details about the sub-problem. The authors mentioned that automatic differentiation could directly solve the sub-problem in Pytorch. To eliminate extra gradient calculations, the authors approximate (6) at one-step Newton after $\\alpha=0$. But how to guarantee that the approximation is acceptable?\n\n2. I appreciate that the authors present many numerics. But the tests are really small. A large-scale test is optimal.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper aims to make SARAH more efficient in practical problems. The authors propose a variant of SARAH, that is tune-free and adaptive. The authors present the convergence of the variant and discuss the theoretical performance under different sampling styles. Experimental results are solid and well discussed. I deem the paper is beyond the acceptance bar.\n\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1.Add a large-scale  test.\n\n2.Add more explantions about the sub-problem approximation.", "broader_impact_concerns": "I do not find any ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers felt the paper was acceptable. Some minor lingering concerns (around motivation, related work, some clarity issues) were addressed in another round of revisions by the authors.
Decision: Accept (poster)