Year: 2021

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.

heading: 1 INTRODUCTION
text: We consider the unconstrained finite-sum optimization problem
minw∈Rd [P (w) def = 1n ∑n i=1fi(w)]. (1)
This problem is prevalent in machine learning tasks where w corresponds to the model parameters, fi(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, (1) is often considered the loss function of Empirical Risk Minimization (ERM) problems. For instance, given a classification or regression problem, fi can be defined as logistic regression or least square by (xi, yi) where xi is a feature representation and yi is a label. Throughout the paper, we assume that each function fi, i ∈ [n] def= {1, ..., n}, is smooth and convex, and there exists an optimal solution w∗ of (1).

heading: 1.1 MAIN CONTRIBUTIONS
text: We propose AI-SARAH, a practical variant of stochastic recursive gradient methods (Nguyen et al., 2017) to solve (1). 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 competitive performance on various datasets, when comparing with SARAH, SARAH+ and other state-of-the-art 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 a truly adaptive stochastic recursive algorithm can be developed in practice.

heading: 1.2 RELATED WORK
text: Stochastic gradient descent (SGD) (Robbins & Monro, 1951; Nemirovski & Yudin, 1983; ShalevShwartz et al., 2007; Nemirovski et al., 2009; Gower et al., 2019) is the workhorse for training supervised machine learning problems that have the generic form (1). In its generic form, SGD defines the new iterate by subtracting a multiple of a stochastic gradient g(wt) from the current iterate wt. That is,
wt+1 = wt − αtg(wt). In most algorithms, g(w) is an unbiased estimator of the gradient (i.e., a stochastic gradient), E[g(w)] = ∇P (w),∀w ∈ 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 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 (αt = α) or decreasing step-size has been proposed in Moulines & Bach (2011); Ghadimi & Lan (2013); Needell et al. (2016); Nguyen et al. (2018); Bottou et al. (2018); Gower et al. (2019; 2020b) under different assumptions on the properties of problem (1). More recently, adaptive / parameter-free methods (Duchi et al., 2011; Kingma & Ba, 2015; Bengio, 2015; Li & Orabona, 2018; 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(wt) 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 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 variancereduced 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). For more examples of variance reduced methods, see Defazio (2016); Konečný et al. (2016); Gower et 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 k ≥ 1, the gradient estimate v0 = ∇P (wk−1) is set to be the full gradient. Subsequently, in the inner loop, at t ≥ 1, a biased estimator vt is used and defined recursively as
vt = ∇fi(wt)−∇fi(wt−1) + vt−1, (2) where i ∈ [n] is a random sample selected at t. A common characteristic of the popular variance reduced methods is that the step-size α in their update rule wt+1 = wt − αvt is constant (or diminishing with predetermined rules) and that depends on the characteristics of problem (1). An exception to this rule are the variance reduced methods 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 parameters 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 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.

heading: 2 MOTIVATION
text: With our primary focus on the design of a 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 a considerable amount of computing resources. More importantly, tuning step-size requires knowledge that is not readily available at a starting point w0 ∈ Rd, and choices of step-size could be heavily influenced by the curvature provided ∇2P (w0). What if a step-size has to be small due to a "sharp" curvature initially, which becomes "flat" afterwards? To see this is indeed the case for many machine learning problems, let us consider logistic regression for a binary classification problem, i.e., fi(w) = log(1 + exp(−yixTi w)) + λ2 ‖w‖
2, where xi ∈ Rd is a feature vector, yi ∈ {−1,+1} is a ground truth, and the ERM problem is in the form of (1). It is
easy to derive the local curvature of P (w), defined by its Hessian in the form
∇2P (w) = 1n ∑n i=1
exp(−yixTi w) [1+exp(−yixTi w)]2︸ ︷︷ ︸
si(w)
xix T i + λI. (3)
Given that a(1+a)2 ≤ 0.25 for any a ≥ 0, one can immediately obtain the global bound on Hessian, i.e. ∀w ∈ Rd we have ∇2P (w) 14 1 n ∑n i=1 xix T i + λI . Consequently, the parameter of global Lipschitz smoothness is L = 14λmax( 1 n ∑n i=1 xix T i ) + λ. It is well known that, with a constant step-size less than (or equal to) 1L , a convergence is guaranteed by many algorithms.
However, suppose the algorithm starts at a random w0 (or at 0 ∈ 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, −yixTi wt 0. An immediate implication is that si(wt) defined in (3) becomes smaller and hence the local curvature will be smaller as well. It suggests that, although a 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 dataset1 with `2-regularized logistic regression. Figures 1(a) and 1(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 is clear from the figure, AI-SARAH displays a significantly faster convergence per effective pass2.
Now, let us discuss why this could happen. The distribution of si as shown in Figured 1(d) indicates that: initially, all si’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 1(c), AI-SARAH starts with a conservative step-size dominated by the global Lipschitz smoothness, i.e., 1/λmax(∇2P (w0)) (red dots); however, within 5 effective passes, the moving average (magenta dash) and 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, 2−1, ..., 24}, and notice that 25 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.
1The dataset is available at https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/ datasets/
2The effective pass is defined as a complete pass on the training dataset. Each data sample is selected once per effective pass on average.

heading: 3 ALGORITHM
text: We present AI-SARAH in Algorithm 1. This algorithm implicitly computes αt−1 at any t ≥ 1 through approximately solving the sub-problem, i.e., minα>0 ξt(α), 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 on harmonic mean (of approximate solutions to the subproblems), 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 of tuning, and can be implemented easily. Notice that β is treated as a smoothing factor in updating the upper-bound of the step-size, and the default setting is β = 0.999. There exists one hyper-parameter in Algorithm 1, γ, which defines the early stopping criterion on Line 8, and the default setting is γ = 132 . We will show later in this chapter that, the performance of this algorithm is not sensitive to the choices of γ, and this is true regardless of the problems (i.e., regularized/non-regularized logistic regression and different datasets.)
Algorithm 1 AI-SARAH 1: Parameter: 0 < γ < 1 (default 132 ), β = 0.999 2: Initialize: w̃0 3: Set: αmax =∞ 4: for k = 1, 2, ... do 5: w0 = w̃k−1 6: v0 = ∇P (w0) 7: t = 1 8: while ‖vt‖2 ≥ γ‖v0‖2 do 9: Select random mini-batch St from [n] uniformly with |St| = b 10: α̃t−1 ≈ arg minα>0 ξt(α) 11: if k = 0 and t = 1 then 12: δkt = 1 α̃t−1 13: else 14: δkt = βδ k t−1 + (1− β) 1α̃t−1 15: end if 16: αmax =
1 δkt
17: αt−1 = min{α̃t−1, αmax} 18: wt = wt−1 − αt−1vt−1 19: vt = ∇fSt(wt)−∇fSt(wt−1) + vt−1 20: t = t+ 1 21: end while 22: Set w̃k = wt. 23: end for

heading: 3.1 ESTIMATE LOCAL LIPSCHITZ SMOOTHNESS
text: In the previous chapter, we showed that AI-SARAH adapts to local Lipschitz smoothness and yields a faster convergence than classical SARAH. Then, the question is how to estimate the parameter of local Lipschitz smoothness in practice. Can we use line-search? The standard approach to estimate local Lipschitz smoothness is to use backtracking line-search. Recall SARAH’s update rule, i.e., wt = wt−1 − αt−1vt−1, where vt−1 is a stochastic recursive gradient. The standard procedure is to apply line-search on function fit(wt−1 − αvt−1). However, the main issue is that −vt−1 is not necessarily a descent direction. AI-SARAH sub-problem. Define the sub-problem (as shown on line 10 of Algorithm 13) as
min α>0 ξt(α) = min α>0 ‖∇fit(wt−1 − αvt−1)−∇fit(wt−1) + vt−1‖2, (4)
where t ≥ 1 denotes an inner iteration and it indexes a random sample selected at t. We argue that, by (approximately) solving (4), we can have good estimate of the parameters of the local Lipschitz
3For sake of simplicity, we use fit instead of fSt .
smoothness. To illustrate this setting, we denote Lit the parameter of local Lipschitz smoothness prescribed by fit at wt−1. Let us focus on a simple quadratic function fit(w) = 1 2 (x T it w − yit)2. Let α̃ be the optimal step-size along direction −vt−1, i.e. α̃ = arg minα fit(wt−1 − αvt−1). Then, the closed form solution of α̃ can be easily derived as α̃ =
xTitwt−1−yit xTit vt−1 , whose value can be positive, negative,
bounded or unbounded.
On the other hand, one can compute the step-size implicitly by solving (4) and obtain αit−1, i.e., αit−1 = arg minα ξt(α). Then, we have
αit−1 = 1
xTit xit ,
which is exactly 1 Lit and recall Lit is the parameter of local Lipschitz smoothness of fit . Simply put, as quadratic function has a constant Hessian, solving (4) gives exactly 1 Lit
. For general (strongly) convex functions, if ∇2fit(wt−1), does not change too much locally, we can still have a good estimate of Lit by solving (4) approximately. Based on a good estimate of Lit, we can then obtain the estimate of the local Lipschitz smoothness of P (wt−1). And, that is
L̄t = 1 n ∑n i=1L i t = 1 n ∑n i=1 1 αit−1 .
Clearly, if a step-size in the algorithm is selected as 1/L̄t, then a harmonic mean of the sequence of the step-size’s, computed for various component functions could serve as a 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.

heading: 3.2 COMPUTE STEP-SIZE AND UPPER-BOUND
text: On Line 10 of Algorithm 1, the sub-problem is a one-dimensional minimization problem, which can be approximately solved by Newton method. Specifically in Algorithm 1, we compute one-step Newton at α = 0, and that is
α̃t−1 = − ξ′t(0)
|ξ′′t (0)| . (5)
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 it 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 ξ′t(0) and the other for ξ ′′ t (0); see Appendix A.2 for implementation details. As shown on Lines 11-16 of Algorithm 1, αmax is updated at every inner iteration. Specifically, the algorithm starts without an upper bound (i.e., αmax = ∞ on Line 3); as α̃t−1 being computed at every t ≥ 1, we employs the exponential smoothing on the harmonic mean of {α̃t−1} to update the upper-bound. For k ≥ 0 and t ≥ 1, we define αmax = 1δkt , where
δkt =
{ 1
α̃t−1 , k = 0, t = 1 βδkt−1 + (1− β) 1α̃t−1 , otherwise
and 0 < β < 1. We default β = 0.999 in Algorithm 1; see Appendix A.2 for details on the design of the adaptive upper-bound.
3.3 CHOICE OF γ
We perform a sensitivity analysis on different choices of γ. Figures 2 shows the evolution of the squared norm of full gradient, i.e., ‖∇P (w)‖2, for logistic regression on binary classification problems; see extended results in Appendix A. It is clear that the performance of γ’s, where, γ ∈ {1/8, 1/16, 1/32, 1/64}, is consistent with only marginal improvement by using a smaller value. We default γ = 1/32 in Algorithm 1.

heading: 3.4 CONVERGENCE ANALYSIS
text: In this section, we provide a convergence analysis of AI-SARAH (Algorithm 1) with a i) modified line 10 to α̃t−1 ≈ arg minα∈[αkmin,αkmax] ξt(α), and ii) replacing the while loop with a for loop t ∈ [m], where αkmin and αkmax are step-size bounds picked in each outer iteration and m be a hyper-parameter. For brevity, let us just hint that for many problems (e.g., the one mentioned in Chapter 2), as the solution wt is approaching w∗ the local curvature of P (w) is getting flatter and hence αkmax could be chosen as a fraction of reciprocal of a smoothness parameter of fi(w)’s over set
Wk := {w ∈ Rd | ‖w̃k−1 − w‖ ≤ m · αkmax‖v0‖}, (6)
which can be much larger than the fraction of reciprocal of a global smoothness parameter. Let us just remark that for k-th outer loop, all iterates wt will stay inside ofWk and hence αkmax is well defined. The parameter 0 < αkmin ≤ αkmax can be chosen arbitrary (e.g., αkmin = αkmax/2 or even αkmin = α k max). We defer the technical details and proofs 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 Lmaxk over Wk and P is µ-strongly convex. Let us define
σkm = 1
µαkmin(m+1) + αkmax αkmin · α k maxL max k 2−αkmaxLmaxk ,
and select m and αkmax such that σ k m < 1, ∀k ≥ 1. Then, modified Algorithm 1 converges as follows: E[‖∇P (w̃k)‖2] ≤ (∏k `=1σ ` m ) ‖∇P (w̃0)‖2.
Remark: SARAH algorithm is a special case of the modified Algorithm 1 when ∀k: αkmin = αkmax = α ≤ 12L .

heading: 4 NUMERICAL EXPERIMENT
text: In this chapter, we present the empirical study on the performance of AI-SARAH. For brevity, we present a subset of experiments in the main paper, and defer the full experimental results and implementation details4 in Appendix A. The problems we consider in the experiment are `2-regularized logistic regression for binary classification problems; see Appendix A for non-regularized case. Given a training sample (xi, yi) indexed by i ∈ [n], the component function fi is in the form fi(w) = log(1 + exp(−yixTi w)) + λ2 ‖w‖ 2,
4Code will be made available upon publication.
where λ = 1n for the ` 2-regularized case and λ = 0 for the non-regularized case. The datasets chosen for the experiments are ijcnn1, rcv1, real-sim, news20 and covtype. Table 1 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), 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 ≈ 5,000 runs in total for each dataset and case. To be specific, we perform an extensive search on hyper-parameters: (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 hyper-parameters.) 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 require any tuning effort, but we have≈ 5, 000 runs to fine-tune the other algorithms. Figure 4 shows the minimum ‖∇P (w)‖2 achieved at a few points of effective passes and wall clock time horizon. It is clear that, AI-SARAH’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 Pytorch5 ), it is likely that our algorithm can be accelerated. By selecting the fine-tuned hyper-parameters of all other algorithms, we compare them with AISARAH and show the results in Figures 5-7. For these experiments, we use 10 distinct random seeds 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 5 presents the evolution of ‖∇P (w)‖2. 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)‖2 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 6 shows that, by effective pass, AI-SARAH consistently outperforms SARAH and SARAH+ on all of the datasets with a possible exception on covtype dataset. By wall clock time, AI-SARAH yields a competitive performance on all of the datasets, and it delivers a stronger performance on ijcnn1 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 rcv1, 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 8. 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 previous chapters, the adaptivity is driven by the local Lipschitz smoothness. As shown in Figure 8, AI-SARAH 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
5Please see https://pytorch.org/docs/stable/optim.html for Pytorch built-in optimizers.
due to λ (and hence strong convexity). In Appendix A, we can see that, as a 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.

heading: 5 CONCLUSION
text: 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 easily 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 a competitive performance compared with SARAH(+), ADAM and other first-order methods, all equipped with fine-tuned hyper-parameters.

heading: ETHICS STATEMENT
text: 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.

heading: REPRODUCIBILITY STATEMENT
text: We uploaded all the codes used to make all the experiments presented in this paper. We have used random seeds to ensure that one can start optimizing the ML models from the same initial starting point as 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.csie.ntu.edu.tw/ ~cjlin/libsvmtools/datasets/. After acceptance, we will include a link to the GitHub repository where we will host the source codes.

heading: APPENDIX
text: The Appendix is organized as follows. In Chapter A, we present extended details on the design, implementation and results of our numerical experiments. In Chapter B, we present the theoretical analysis of AI-SARAH. In Chapter C, 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 B.

heading: A EXTENDED DETAILS ON NUMERICAL EXPERIMENT
text: In this chapter, we present the extended details of the design, implementation and results of the numerical experiments.

heading: A.1 PROBLEM AND DATA
text: 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 datasets6 are chosen to define the tasks. Specifically, we selected 10 popular binary class datasets: ijcnn1, rcv1, news20, covtype, real-sim, a1a, gisette, w1a, w8a and mushrooms (see Table 2 for basic statistics of the datasets).

heading: A.1.1 DATA PRE-PROCESSING
text: Let (χi, yi) be a training (or testing) sample indexed by i ∈ [n] (or i ∈ [ntest]), where χi ∈ Rd−1 is a feature vector and yi is a label. We pre-processed the data such that χi is of a unit length in Euclidean norm and yi ∈ {−1,+1}.

heading: A.1.2 MODEL AND LOSS FUNCTION
text: The selected model, hi : Rd 7→ R, is in the linear form
hi(ω, ε) = χ T i ω + ε, ∀i ∈ [n], (7)
where ω ∈ Rd−1 is a weight vector and ε ∈ R is a bias term.
For simplicity of notation, from now on, we let xi def = [χTi 1]
T ∈ Rd be an augmented feature vector, w
def = [ωT ε]T ∈ Rd be a parameter vector, and hi(w) = xTi w for i ∈ [n].
6LIBSVM datasets are available at https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/ datasets/.
Given a training sample indexed by i ∈ [n], the loss function is defined as a logistic regression
fi(w) = log(1 + exp(−yihi(w)) + λ
2 ‖w‖2. (8)
In (8), λ2 ‖w‖ 2 is the `2-regularization of a particular choice of λ > 0, where we used λ = 1n in the experiment; for the non-regularized case, λ was set to 0. Accordingly, the finite-sum minimization problem we aimed to solve is defined as
min w∈Rd
{ P (w) def = 1
n n∑ i=1 fi(w) } . (9)
Note that (9) is a convex function. For the `2-regularized case, i.e., λ = 1/n in (8), (9) is µ-strongly convex and µ = 1n . However, without the λ, i.e., λ = 0 in (8), (9) is µ-strongly convex if and only if there there exists µ > 0 such that∇2P (w) µI for w ∈ Rd (provided ∇P (w) ∈ C).

heading: A.2 ALGORITHMS
text: This section provides the implementation details7 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 algorithm. 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α>0 ξt(α) can be approximately solved by computing the Newton step at α = 0, i.e., α̃t−1 = − ξ
′ t(0) |ξ′′t (0)|
. This can be easily implemented with automatic differentiation in Pytorch8, and only two additional backward passes w.r.t α is needed. For function in some particular form, such as a 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., αmax, in the algorithm. To be specific, the algorithm starts without an upper-bound, i.e., αmax = ∞ on Line 3 of Algorithm 1. Then, αmax is updated per (inner) iteration. Recall in Chapter 3, αmax is computed as a harmonic mean of the sequence, i.e., {α̃t−1}, and an exponential smoothing is 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 wt is drastically reduced or approaching zero, the one-step Newton solution in (5) could be very large, i.e. α̃t−1 0, which could be too aggressive to other mini-batch and hence Problem (1) 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 (1). With the adaptive upper-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 fSt ) and globally focused (with respect to P ).
It is worthwhile to mention that Algorithm 1 does not require computing extra gradient of fSt with respect to w if compared with SARAH and SARAH+. At each inner iteration, t ≥ 1, Algorithm 1 computes∇fSt(wt−1−αvt−1) with α = 0 just as SARAH and SARAH+ would compute ∇fSt(wt−1), and the only difference is that α is specified as a variable in Pytorch. After the adaptive step-size αt−1 is determined (Line 17), Algorithm 1 computes ∇fSt(wt−1 − αt−1vt−1) just as SARAH and SARAH+ would compute∇fSt(wt). In Chapter 3 of the main paper, we discussed the sensitivity of Algorithm 1 on the choice of γ. Here, we present the full results (on 10 chosen datasets for both `2-regularized and non-regularized
7Code will be made available upon publication. 8For detailed description of the automatic differentiation engine in Pytorch, please see https://pytorch.
org/tutorials/beginner/blitz/autograd_tutorial.html.
cases) in Figures 9, 10, 11, and 12. Note that, in this experiment, we chose γ ∈ { 164 , 1 32 , 1 16 , 1 8 , 1 4 , 1 2}, and for each γ, dataset and case, we used 10 distinct random seeds and ran each experiment for 20 effective passes.

heading: A.2.2 OTHER ALGORITHMS
text: In our numerical experiment, we compared the performance of TUNE-FREE AI-SARAH (Algorithm 1) 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 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 5 different schedules to decrease the step-size after every effective pass on the training samples; for SARAH and SVRG, we 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 5 different values of the inner loop early stopping parameter. Table 3 presents the detailed tuning plan for these algorithms.

heading: Selection criteria:
text: We defined the best hyper-parameters as the ones yielding the minimum ending value of the loss function, where the running budget is presented in Table 4. 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 ones achieved the minimum ending value of the loss function.

heading: Hightlights of the hyper-parameter search:
text: • To take into account the randomness in the performance of these algorithms provided different hyper-parameters, we ran each configuration with 5 distinct random seeds. The total number of runs for each dataset and case is 4, 850. • Tables 5 and 6 present the best hyper-parameters selected from the candidates for the regularized and non-regularized cases. • Figures 13, 14, 15 and 16 show the performance of different hyper-parameters for all tuned algorithms; it is clearly that, the performance is highly dependent on the choices of hyperparameter for SARAH, SARAH+, and SVRG. And, the performance of ADAM and SGD w/m are very SENSITIVE to the choices of hyper-parameter.
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) Lipschitz
constant L, and it can be computed as, given (8) and (9),
L = 1
4 λmax(
1
n n∑ i=1 xix T i ) + λ,
where λmax(A) denotes the largest eigenvalue of A and λ is the penalty term of the `2-regularization in (8). Table 7 shows the values of L for the regularized and non-regularized cases on the chosen datasets.

heading: A.3 EXTENDED RESULTS OF EXPERIMENT
text: In Chapter 4, we compared tune-free & fully adaptive AI-SARAH (Algorithm 1) with fine-tuned SARAH, SARAH+, SVRG, ADAM and SGD w/m. In this section, we present the extended results of our empirical study on the performance of AI-SARAH.
Figures 17 and 18 compare the average ending ‖∇P (w)‖2 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 a1a, gisette, w1a and mushrooms, AI-SARAH outperforms ADAM for at least 80% (a1a), 55% (gisette), 50% (w1a), and 50% (mushrooms) of all candidate hyper-parameters.
Figure 19 shows the results of the non-regularized case for ijcnn1, rcv1, real-sim, news20 and covtype datasets. Figures 20 and 21 present the results of the `2-regularized case and non-regularized case respectively on a1a, gisette, w1a, w8a and mushrooms datasets. For completeness of presentation, we present the evolution of AI-SARAH’s step-size and upper-bound on a1a, gisette, w1a, w8a and mushrooms datasets in Figures 22 and 23. Consistent with the results shown in Chapter 4 of the main paper, AI-SARAH delivers a competitive performance in practice.

heading: B THEORETICAL ANALYSIS
text: In this chapter, we provide a convergence analysis of AI-SARAH (Algorithm 1) with a i) modified line 10 to α̃t−1 ≈ arg minα∈[αkmin,αkmax] ξt(α), and ii) replacing the while loop with a for loop t ∈ [m], where αkmin and αkmax are step-size bounds picked in each outer iteration and m be a 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 ∈ [m] of the inner loop, the step-size is chosen by approximately solving a simple onedimensional constrained optimization problem. Define the (modified) sub-problem (optimization problem) at t ≥ 1 as
min α∈[αkmin,αkmax] ξt(α), (10)
where ξt(α) := ‖vt‖2 = ‖∇fSt(wt−1−αvt−1)−∇fSt(wt−1) + vt−1‖2, αkmin and αkmax are lowerbound and upper-bound of the step-size respectively. These bounds do not allow large fluctuations of the (adaptive) step-size. We denote αt−1 the approximate solution of (10). Now, let us present some remarks regarding AI-SARAH. Remark B.1. As we will explain with more details in the following subsections, the values of αkmin and αkmax cannot be arbitrarily large. To guarantee convergence, we will need to assume that αkmax ≤ 2Lmaxk , where L max k = maxi∈[n] L i k. Here, L i k is the local smoothness parameter of fi defined on a working-set for each outer loop (see Definition B.6). Remark B.2. SARAH Nguyen et al. (2017) can be seen as a special case of AI-SARAH, where αkmin = α k max = α for all outer loops (k ≥ 1). In other words, a constant step-size is chosen for the algorithm. However, if αkmin < α k max, then the selection of the step-size in AI-SARAH allows a faster convergence of ‖vt‖2 than SARAH in each inner loop. Remark B.3. At t ≥ 1, let us select a mini-batch of size n, i.e., |St| = n. In this case, AI-SARAH is equivalent to deterministic gradient descent with a very particular way of selecting the step-size, i.e. by solving the following problem
min α∈[αkmin,αkmax] ξt(α),
where ξt(α) = ‖∇P (wt−1 − α∇P (wt−1)) ‖2. In other words, the step-size is selected to minimize the squared norm of the full gradient with respect to wt.

heading: B.2 DEFINITIONS / ASSUMPTIONS
text: First, we present the main definitions and assumptions that are used in our convergence analysis. Definition B.4. Function f : Rd → R is L-smooth if: f(x) ≤ f(y) + 〈∇f(y), x − y〉 + L2 ‖x − y‖2,∀x, y ∈ Rd, and it is LC-smooth if:
f(x) ≤ f(y) + 〈∇f(y), x− y〉+ LC 2 ‖x− y‖2,∀x, y ∈ C.
Definition B.5. Function f : Rd → R is µ-strongly convex if: f(x) ≥ f(y) + 〈∇f(y), x − y〉 + µ 2 ‖x− y‖ 2,∀x, y ∈ Rd. If µ = 0 then function f is a (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-setWk which contains all iterates produced in the k-th outer loop of (the modified) Algorithm 1. Definition B.6 (Working-SetWk). For any outer loop k ≥ 1 in (the modified) Algorithm 1, starting at w̃k−1 we define
Wk := {w ∈ Rd | ‖w̃k−1 − w‖ ≤ m · αkmax‖v0‖}. (11)
Note that the working-setWk can be seen as a ball of all vectors w’s, which are not further away from w̃k−1 than m · αkmax‖v0‖. Here, recall that m is the total number of iterations of an inner loop, αkmax is an upper bound of the step-size αt−1, ∀t ∈ [m], and ‖v0‖ is simply the norm of the full gradient evaluated at the starting point w̃k−1 in the outer loop. By combining Definition B.4 with the working-set Wk, we are now ready to provide the main assumption used in our analysis. Assumption 1. Functions fi, i ∈ [n], of problem (1) are LiWk -smooth. Since we only focus on the working-setWk, we simply write Lik-smooth.
Let us denote Li the smoothness parameter of function fi, i ∈ [n], in the domain Rd. Then, it is easy to see that Lik ≤ Li, ∀i ∈ [n]. In addition, under Assumption 1, it holds that function P is L̄k-smooth in the working-setWk, where L̄k = 1n ∑n i=1 L i k. As we will explain with more details in the next section for our theoretical results, we will assume that αkmax ≤ 2Lmaxk , where L max k = maxi∈[n] L i k.

heading: B.3 CONVERGENCE GUARANTEES
text: Now, we can derive the convergence rate of AI-SARAH. Here, we highlight that, all of our theoretical results can be applied to SARAH. We also note that, some quantities involved in our results, such as Lk and Lmaxk , are dependent upon the working setWk (defined for each outer loop k ≥ 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 ∑m t=0 E[‖∇P (wt)‖2]. Note that it does not require any convexity assumption. Lemma B.7. Fix a outer loop k ≥ 1 and consider Algorithm 1 with αkmax ≤ 1/L̄k. Under Assumption 1, ∑m t=0 E[‖∇P (wt)‖2] ≤
2 αkmin
E[P (w0)−P (w∗)] + α k max
αkmin
∑m t=0 E[‖∇P (wt)− vt‖2].
The second lemma provides an informative bound on the quantity E[‖∇P (wt)− vt‖2]. Note that it requires convexity of component functions fi, i ∈ [n]. Lemma B.8. Fix a outer loop k ≥ 1 and consider Algorithm 1 with αkmax < 2/Lmaxk . Suppose fi is convex for all i ∈ [n]. Then, under Assumption 1, for any t ≥ 1 :
E[‖∇P (wt)− vt‖2] ≤ ( αkmaxL max k
2−αkmaxLmaxk
) E[‖v0‖2].
Equipped with the above lemmas, we can then present our main theorem and show the linear convergence of (the modified) Algorithm 1 for solving strongly convex smooth problems. Theorem B.9. Suppose that Assumption 1 holds and P is strongly convex with convex component functions fi, i ∈ [n]. Let us define
σkm = 1
µαkmin(m+1) + αkmax αkmin · α k maxL max k 2−αkmaxLmaxk ,
and select m and αkmax such that σ k m < 1, ∀k ≥ 1. Then, Algorithm 1 converges as follows: E[‖∇P (w̃k)‖2] ≤ (∏k `=1σ ` m ) ‖∇P (w̃0)‖2.
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 be seen as a special case of AI-SARAH if, for all outer loops, αkmin = α k max = α. In this case, we can have
σkm = 1 µα(m+1) + αLmaxk
2−αLmaxk .
If we further assume that all functions fi, i ∈ [n], are L-smooth and do not take advantage of the local smoothness (in other words, do not use the working-setWk), then Lmaxk = L for all k ≥ 1. Then, with these restrictions, we have
σm = σ k m = 1 µα(m+1) + αL 2−αL < 1.
As a result, Theorem B.9 guarantees the following linear convergence: E[‖∇P (w̃k)‖2] ≤ (σm)
k‖∇P (w̃0)‖2, which is exactly the convergence of classical SARAH provided in Nguyen et al. (2017).

heading: C TECHNICAL PRELIMINARIES & PROOFS OF MAIN RESULTS
text: Let us start by presenting some important technical lemmas that will be later used for our main proofs.

heading: C.1 TECHNICAL PRELIMINARIES
text: Lemma C.1. Nesterov (2003) Suppose that function f is convex and L-Smooth in C ⊆ Rn. Then for any w, w′ ∈ C:
〈∇f(w)−∇f(w′), (w − w′)〉 ≥ 1 L ‖∇f(w)−∇f(w′)‖2. (12)
Lemma C.2. Let Assumption 1 hold for all functions fi of problem (1). That is, let us assume that function fi is Lik-smooth ∀i ∈ [n]. Then, function P (w) def = 1n ∑n i=1 fi(w) is L̄k-smooth, where L̄k = 1 n ∑n i=1 L i k.
Proof. For each function fi, we have by definition of Lik-local smoothness,
fi(x) ≤ fi(y) + 〈∇fi(y), x− y〉+ Lik 2 ‖x− y‖2,∀x, y ∈ Wk.
Summing through all i′s and dividing by n, we get
P (x) ≤ P (y) + 〈∇P (y), x− y〉+ L̄k 2 ‖x− y‖2,∀x, y ∈ Wk.
The next Lemma was first proposed in Nguyen et al. (2017). We add it here with its proof for completeness and will use it later for our main theoretical result.
Lemma C.3. Nguyen et al. (2017) Consider vt defined in (2). Then for any t ≥ 1 in Algorithm 1, it holds that:
E[‖∇P (wt)− vt‖2] = t∑
j=1
E[‖vj − vj−1‖2]− t∑
j=1
E[‖∇P (wj)−∇P (wj−1)‖2]. (13)
Proof. Let Ej denote the expectation by conditioning on the information w0, w1, . . . , wj as well as v0, v1, . . . , vj−1. Then,
Ej [‖∇P (wj)− vj‖2] = Ej [ ‖ (∇P (wj−1)− vj−1) + (∇P (wj)−∇P (wj−1))− (vj − vj−1)‖2 ] = Ej [‖∇P (wj−1)− vj−1‖2] + Ej [‖∇P (wj)−∇P (wj−1)‖2] + Ej [‖vj − vj−1‖2]
+ 2 (∇P (wj−1)− vj−1)T (∇P (wj)−∇P (wj−1))
− 2 (∇P (wj−1)− vj−1)T Ej [vj − vj−1]
− 2 (∇P (wj)−∇P (wj−1))T Ej [vj − vj−1] = Ej [‖∇P (wj−1)− vj−1‖2]− Ej [‖∇P (wj)−∇P (wj−1)‖2] + Ej [‖vj − vj−1‖2],
where the last equality follows from
Ej [vj − vj−1] = Ej [∇fij (wj)−∇fij (wj−1)] = ∇P (wj)−∇P (wj−1).
By taking expectation in the above expression, using the tower property, and summing over j = 1, ..., t, we obtain
E[‖∇P (wt)− vt‖2] = t∑
j=1
E[‖vj − vj−1‖2]− t∑
j=1
E[‖∇P (wj)−∇P (wj−1)‖2].

heading: C.2 PROOFS OF LEMMAS AND THEOREMS
text: For simplicity of notation, we use |S| = 1 in the following proofs, and a generalization to |S| > 1 is straightforward.

heading: C.2.1 PROOF OF LEMMA B.7
text: By Assumption 1, Lemma C.2 and the update rule wt = wt−1−αt−1vt−1 of Algorithm 1, we obtain:
P (wt) ≤ P (wt−1)− αt−1〈∇P (wt−1), vt−1〉+ L̄k 2 α2t−1‖vt−1‖2
= P (wt−1)− αt−1
2 ‖∇P (wt−1)‖2 + αt−1 2 ‖∇P (wt−1)− vt−1‖2 −
( αt−1
2 − L̄k 2 α2t−1
) ‖vt−1‖2,
where, in the equality above, we use the fact that 〈a, b〉 = 12 (‖a‖ 2 + ‖b‖2 − ‖a− b‖2).
By rearranging and using the lower and upper bounds of the step-size αt−1 in the outer loop k (αkmin ≤ αt−1 ≤ αkmax), we get: αkmin
2 ‖∇P (wt−1)‖2 ≤ [P (wt−1)− P (wt)] + αkmax 2 ‖∇P (wt−1)− vt−1‖2 − αt−1 2
( 1− L̄kαt−1 ) ‖vt−1‖2.
By assuming that αkmax ≤ 1L̄k , it holds that αt−1 ≤ 1 L̄k
and ( 1− L̄kαt−1 ) ≥ 0, ∀t ∈ [m]. Thus,
αkmin 2 ‖∇P (wt−1)‖2 ≤ [P (wt−1)− P (wt)] + αkmax 2 ‖∇P (wt−1)− vt−1‖2 − αkmin 2
( 1− L̄kαkmax ) ‖vt−1‖2.
By taking expectations and multiplying both sides with 2 αkmin :
E[‖∇P (wt−1)‖2] ≤ 2
αkmin [E[P (wt−1)]− E[P (wt)]] + αkmax αkmin
E[‖∇P (wt−1)− vt−1‖2]− ( 1− L̄kαkmax ) E[‖vt−1‖2]
≤ 2 αkmin [E[P (wt−1)]− E[P (wt)]] + αkmax αkmin E[‖∇P (wt−1)− vt−1‖2],
where the last inequality holds as αkmax ≤ 1L̄k . Summing over t = 1, 2, . . . ,m+ 1, we have m+1∑ t=1 E[‖∇P (wt−1)‖2] ≤ 2 αkmin m+1∑ t=1 E[P (wt−1)− P (wt)] + αkmax αkmin m+1∑ t=1 E[‖∇P (wt−1)− vt−1‖2]
= 2
αkmin E[P (w0)− P (wm+1)] + αkmax αkmin m+1∑ t=1 E[‖∇P (wt−1)− vt−1‖2
≤ 2 αkmin E[P (w0)− P (w∗)] + αkmax αkmin m+1∑ t=1 E[‖∇P (wt−1)− vt−1‖2],
where the last inequality holds since w∗ is the global minimizer of P.
The last expression can be equivalently written as: m∑ t=0 E[‖∇P (wt)‖2] ≤ 2 αkmin E[P (w0)− P (w∗)] + αkmax αkmin m∑ t=0 E[‖∇P (wt)− vt‖2], which completes the proof.

heading: C.2.2 PROOF OF LEMMA B.8
text: Ej [ ‖vj‖2 ] ≤ Ej [ ‖vj−1 − ( ∇fij (wj−1)−∇fij (wj) ) ‖2 ]
= ‖vj−1‖2 + Ej [ ‖∇fij (wj−1)−∇fij (wj)‖2 ] −Ej [ 2
αj−1
〈 ∇fit(wj−1)−∇fij (wj), wj−1 − wj 〉] (12)
≤ ‖vj−1‖2 + Ej [ ‖∇fij (wj−1)−∇fij (wj)‖2 ] − Ej
[ 2
αj−1L ij k
‖∇fij (wj−1)−∇fij (wj)‖2 ] .
For each outer loop k, it holds that αj−1 ≤ αkmax and Lik ≤ Lmaxk . Thus,
Ej [‖vj‖2] ≤ ‖vj−1‖2 + Ej [ ‖∇fij (wj−1)−∇fij (wj)‖2 ] − 2 αkmaxL max k Ej [ ‖∇fij (wj−1)−∇fij (wj)‖2 ] = ‖vj−1‖2 + ( 1− 2
αkmaxL max k
) Ej [ ‖∇fij (wj−1)−∇fij (wj)‖2 ] = ‖vj−1‖2 + ( 1− 2
αkmaxL max k
) Ej [ ‖vj − vj−1‖2 ] .
By rearranging, taking expectations again, and assuming that αkmax < 2/L max k : E[‖vj − vj−1‖2] ≤ ( αkmaxL max k
2− αkmaxLmaxk
)[ E[‖vj−1‖2]− E[‖vj‖2] ] .
By summing the above inequality over j = 1, . . . , t (t ≥ 1), we have: t∑
j=1
E[‖vj − vj−1‖2] ≤ ( αkmaxL max k
2− αkmaxLmaxk ) t∑ j=1 [ ‖vj−1‖2 − ‖vj‖2 ] ≤ ( αkmaxL max k
2− αkmaxLmaxk
)[ E[‖v0‖2]− E[‖vt‖2] ] . (14)
Now, by using Lemma C.3, we obtain:
E[‖∇P (wt)− vt‖2] (13) ≤ t∑
j=1
E [ ‖vj − vj−1‖2 ] (14)
≤ ( αkmaxL max k
2− αkmaxLmaxk
)[ E[‖v0‖2]− E[‖vt‖2] ] ≤ ( αkmaxL max k
2− αkmaxLmaxk
) E[‖v0‖2]. (15)

heading: C.2.3 PROOF OF THEOREM B.9
text: Proof. Since v0 = ∇P (w0) implies ‖∇P (w0)− v0‖2 = 0, then by Lemma B.8, we obtain: m∑ t=0 E[‖∇P (wt)− vt‖2] ≤ ( mαkmaxL max k 2− αkmaxLmaxk ) E[‖v0‖2]. (16)
Combine this with Lemma B.7, we have that: m∑ t=0 E[‖∇P (wt)‖2] ≤ 2 αkmin E[P (w0)− P (w∗)] + αkmax αkmin m∑ t=0 E[‖∇P (wt)− vt‖2]
(16)
≤ 2 αkmin E[P (w0)− P (w∗)] + αkmax αkmin
( mαkmaxL max k
2− αkmaxLmaxk
) E[‖v0‖2].(17)
Since we are considering one outer iteration, with k ≥ 1, we have v0 = ∇P (w0) = ∇P (w̃k−1) and w̃k = wt, where t is drawn uniformly at random from {0, 1, . . . ,m}. Therefore, the following holds,
E[‖∇P (w̃k)‖2] = 1
m+ 1 m∑ t=0 E[‖∇P (wt)‖2]
(17)
≤ 2 αkmin(m+ 1) E[P (w̃k−1)− P (w∗)] + αkmax αkmin
( αkmaxL max k
2− αkmaxLmaxk
) E[‖∇P (w̃k−1)‖2]
≤ (
1 µαkmin(m+ 1) + αkmax αkmin
( αkmaxL max k
2− αkmaxLmaxk
)) E[‖∇P (w̃k−1)‖2].
Let us use σkm = 1
µαkmin(m+1) + αkmax αkmin · α k maxL max k 2−αkmaxLmaxk , then the above expression can be written as:
E[‖∇P (w̃k)‖2] ≤ σkmE[‖∇P (w̃k−1)‖2].
By expanding the recurrence, we obtain:
E[‖∇P (w̃k)‖2] ≤ ( k∏ `=1 σ`m ) ‖∇P (w̃0)‖2.
This completes the proof.

Review summaries:
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. 

In this paper, the authors proposed a SARAH-type variance reduced gradient method that adaptively and automatically selects the stepsize.  In 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.   Extensive 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.  

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.