Stochastic Gradient Methods with Preconditioned Updates
Authors: Abdurakhmon Sadiev
Aleksandr Beznosikov
Dmitry Kamzolov
Rachael Tappenden
Martin Takáč
Venue: Submitted to ICLR 2023 (2023)
Keywords: optimization
non-convex optimization
stochastic optimization
scaled methods
variance reduction

Abstract: This work considers non-convex finite sum minimization. There are a number of algorithms for such problems, but existing methods often work poorly when the problem is badly scaled and/or ill-conditioned, and a primary goal of this work is to introduce methods that alleviate this issue. Thus, here we include a preconditioner that is based upon Hutchinson's approach to approximating the diagonal of the Hessian, and couple it with several gradient based methods to give new `scaled' algorithms: Scaled  SARAH and Scaled L-SVRG. Theoretical complexity guarantees under smoothness assumptions are presented, and we prove linear convergence when both smoothness and the PL-condition is assumed. Because our adaptively scaled methods use approximate partial second order curvature information, they are better able to mitigate the impact of badly scaled problems, and this improved practical performance is demonstrated in the numerical experiments that are also presented in this work.

Under review as a conference paper at ICLR 2023
STOCHASTIC GRADIENT METHODS WITH PRECONDI- TIONED UPDATES
Anonymous authors Paper under double-blind review
ABSTRACT
This work considers non-convex finite sum minimization. There are a number of algorithms for such problems, but existing methods often work poorly when the problem is badly scaled and/or ill ill-conditioned, and primary goal of this work is to introduce methods that alleviate this issue. Thus, here we include a preconditioner that is based upon Hutchinson's 's approach to approximating the diagonal of the Hessian, and couple it with several gradient based methods to give new 'scaled' algorithms: Scaled SARAH and Scaled L L-SVRG. Theoretical complexity guarantees under smoothness assumptions are presented, and we prove linear con- vergence when both smoothness and the PL-condition is assumed. Because adaptively scaled methods use approximate partial second order curvature informa- tion, they are better able mitigate the impact of badly scaled problems, and this improved practical performance is demonstrated in the numerical experiments that are also presented in this work.
INTRODUCTION
This work considers the following, possibly nonconvex, finite-sum optimization problem: minwer (P(w) = ((())-
where w E Rd is the model/weight parameter and the loss functions f: IR - Rv [n] (1...n) are smooth and twice differentiable. Throughout this work assumed that has an optimal solution, with corresponding optimal value, denoted by w", and P = P(w"), respectively. Problems of the form ) cover plethora of applications, including empirical risk minimization, deep learning, and supervised learning tasks such as regularized least squares or logistic regression (Shalev) Shwartz & David 2014). This minimization problem can be difficult to solve, particularly when the number of training samples or problem dimension d, is large, or if the problem is nonconvex. Stochastic Gradient Descent (SGD) is one of the most widely known methods for problem ① and its origins date back to the 1950s with the work of Robbins Monro (I95T). The explosion of interest in machine learning has led to an immediate need for reliable and efficient algorithms for solving [ Motivated by, and aiming to improve upon, vanilla SGD, many novel methods have already been developed for convex and/or strongly convex instances of (T), including SAG/SAGA (Le Roux et al.) 2012 Defazio et al. 2014), SDCA (Shalev-Shwand & Zhang 2013), SVRG (Johnson & Zhang 2013 Xiao & Zhang 2014), S2GD (Konečný & Richtárik 2017) and SARAH (Nguyen al. 2017). to name just few. In general, these methods are simple, have low per iteration computational costs, and are often able to find s-optimal solution to ( quickly, when & 0 is too small. However, they often have several hyper-parameters that can be difficult to tune, they can struggle when applied ill-conditioned problems. and many iterations may be required to find a high accuracy solution. Non- Non-convex instances of the optimization problem (I) (for example, arising from deep neural networks (DNNS) have been diverting the attention of researchers of late, and new algorithms are being developed to fill this gap (Ghadimi & Lan 2013 Ghadimi et al.) 2016 Lei et al. 2017 2021b). Of particular relevance to this work is the PAGE algorithm presented in Li et al. (02 The algorithm is conceptually simple, involving only one loop, and small number of parameters, and can be applied to non-convex problems ( The main update involves either a minibatch SGD direction, or the previous gradient with small adjustment (similar to that in SARAH (Nguyen et al.) 2017)). The Loopless SVRG (L-SVRG) method (Hofmann et al., 2015 Qian et al., (2021), l). is also of particular interest here. It is a simpler 'loopless' variant of SVRG, which, unlike for PAGE, involves
Li et al.

---

Under review as a conference paper at ICLR 2023
an unbiased estimator of the gradient, and it can be applied to non-convex instances of problem I For problems that are poorly scaled and/or ill-conditioned, second order methods that incorporate curvature information, such as Newton or quasi-Newton methods (Dennis Jr. & Moré 1977 Fletcher 1987, Nocedal& & Wright 2006), can often outperform first order methods. Unfortunately, they can also be prohibitively expensive, in terms of both computational and storage costs. There are several works that have tried to reduce the potentially high cost of second order methods by using only approximate, or partial curvature information. Some of these stochastic second order, and quasi-Newton (Jahani et al. 202 2020) methods have shown good practical performance for some machine learning problems, although, possibly due to the noise in the Hessian approximation, sometimes they perform similarly to first order variants.
An alternative approach to enhancing search directions is to use a preconditioner. There are several methods for problems of the form ( which use what we call a 'first order preconditioner' preconditioner built using gradient information - including Adagrad (Duchi et al.] (2011), RMSProp (Tieleman et al., 2012), and Adam (Kingma & Bal Ba (211)). Adagrad (Duchi et al. (201]) incorporates diagonal preconditioner that is built using accumulated gradient information from the previous iterates. The preconditioner allows every component of the current gradient to be scaled adaptively, but it has the disadvantage that the elements of the preconditioner tend to grow rapidly as iterations progress, leading to quickly decaying learning rate. A method that maintains the ability to adaptively scale elements of the gradient, but overcomes the drawback of rapidly decreasing learning rate, is RMSProp. It does this by including a momentum parameter, B3 in the update for the diagonal preconditioner. In particular, at each iteration the updated diagonal preconditioner is taken to be convex combination (using a momentum parameter (2) of the (square) of the previous preconditioner and the Hadamard product of the current gradient with itself. So, gradient information from all the previous iterates is included in the preconditioner, but there is a preference for more recent information. Adam (Kingma & Ba 2013) combines the positive features of Adagr ad and RMSProp, but it also uses first moment estimate of the gradient, providing kind of additional momentum. Adam preforms well in practice, and is among the most popular algorithms for DNN.
Recently, second order preconditioners that use approximate and/or partial curvature information have been developed and studied. The approach in Ada Hessi an Yao et al., 2020) was use diagonal preconditioner that was motivated by Hutchinson's 's approximation to the diagonal of the
Hessian (Bekas et al., (2077), , but that also stayed close to some of the approximations used in existing methods such as Adam (Kingma & Ba 2015) and Adagrad (Duchi et al. 2011). Because of this, the approximation often differed markedly from the true diagonal of the Hessian, and therefore it did not always capture good enough curvature information to be helpful. The work OASIS (Jahani et al. 2021b). proposed a preconditioner that was closely based upon Hutchinson's 's approach, and provided more accurate estimation of the diagonal of the Hessian, and correspondingly led to improved numerical behaviour in practice. The preconditioner presented in Jahani al. (202Tb) is adopted here.
1.1 NOTATION AND ASSUMPTIONS
Given a Positive Definite (PD) matrix D E Rdxd, the weighted Euclidean norm is defined to be || = xx" Dr. where x E IRd. The symbol o denotes the Hadamard product, and diag(r) denotes the d 1x diagonal matrix whose diagonal entries are the components of the vector x E Rdd
Recall that problem TT is assumed to have an optimal (probably not a unique) solution w", with corresponding optimal value p P(w"). ). As is standard for stochastic algorithms, the convergence guarantees presented in this work will develop a bound on the number of iterations T', required to push the expected squared norm of the gradient below some error tolerance E > 0, i.e., to find ur
satisfying
[I V dor S S
A point पे satisfying (2) is referred to as an e-optmmll solution. Importantly, ur is some iterate generated in the first T iterations of each algorithm, but it not necessarily the Tth iterate.
Throughout this work we assume that each f. Rd + R and P Rd + R are twice differentiable and also I-smooth. This is formalized in the following assumption.
Assumption 1.1 (L-smoothness)) For all i E [n]] fs and P are assumed to be twice differentiable and L-smooth, i... Vi E [n], Vw, w' E dom(ff) we have ff.) - ff('l))l < Lllw w'1l. and ww,, w/ dom(P) we have [VP(w) P((w") < T.ll w/ll
2

---

Under review as a conference paper at ICLR 2023
For some of the results in this work, it will also be assumed that the function P satisfies the PL- condition. Note that the PL-condition does not imply convexity (see Footnote in Li et al. (201aa))
Assumption 1.2 wowasaasiiieiecccoodiioooooo if there exists >> O, such that [1) (p((P()) - P*), Vw E R
A function P R + R. satisfies the PL-condition
1.2 CONTRIBUTIONS
Table I: Comparison of scaled methods for non-convex problems.
Notation: ε denotes solution accuracy ( The "Tuning of B²"
The main contributions of this work are stated below, and are summarized in Tables [ and 2
column shows whether it is easy ('+"), or difficult ('-") to tune 82. Our preconditioner (5) works with any 32. Adam only supports
certain large 3 = 1 Défooseez et al. 2020: Reddi et al. 2019).
Scaled SARAH. We present new algorithm called Scaled
Method
Reference
Convergence
Tuning of 32
Duchi
SARAH, which is combina-
Adagrad
7cu et al
2018
8"
tion of the SARAH (Nguyen
Delossez et al.
2120
al. 2017) and PAGE (Li el al.
RMSProp
Tickemnn
2012
no theory
2021a) algorithms, coupled with
Adam
Kingma & Ba
2015
the diagonal preconditioner from Jahani et al. (202Tb). The inclu- sion of the preconditioner results in adaptive scaling of every ele- ment of the search direction (neg- ative gradient), which leads to improved practical performance, particularly on ill-conditioned and poorly scaled problems. The algorithm is simple (a single loop) and is easy to tune (Sec- tion
Défosses et al
2020
AdaHessian
Yao
2000
no theory
OASIS
Jahani et al
2021b
6
Scaled SARAH
This work
E
Scaled L-SVRG
This work
2
Table 2: A summary of the main results of this work. Complexities for Scal led SARAH and Scal ed L-SVRG are given for non- convex problems (first row), and under the PI. assumption (second row). Notation: L = smoothness constant, μ = PL constant, E solution accuracy (2) Ao P(w")- P* data size, and I', are upper and lower bounds of the Hessian approximation.
Scaled SARAH
Scaled L-SVRG
Scaled L-SVRG. The Scaled L-SVRG algorithm is also presented, which is PL
NC
2/2 LA
[max
n, Vn
log da
max
n,
2/3 Z log 20p
similar LVSV but with the addition of the diagonal preconditioner (Jahani et al. 202 Again, the preconditioner allows all elements of the gradient to be scaled adaptively, the algorithm uses a single loop structure, and for this algorithm unbiased estimate of the gradient is used. The inclusion of adaptive local curvature information via the preconditioner leads to improvments in practical performance (Appendix AA).
Convergence guarantees. Theoretical guarantees show that both Scaled SARAH and Scaled L- LVSVRG converge and we present an explicit bound for the number of iterations required by each algorithm to obtain an iterate that is e-optimal. Convergence is guaranteed for both Scaled SARAH and Scal L-SVRG under a smoothness assumption on the functions ʃi. If both smoothness and the PL-condition hold, then improved iteration complexity results for Sca ed SARAH and Scaled L-SVRG are obtained, which show that expected function value gap converges to zero at linear rate (see Theorems and (A.2) Our scaled methods achieve the best known rates of all methods with preconditioning for non-convex deterministic and stochastic problems, and Scaled SARAH and Scaled L-SVRG are the first preconditioned methods that achieve linear rate of convergence under the PL assumption. See detailed comparison in Section 4
Numerical experiments. Extensive numerical experiments were performed (Sections 5 and B
under various parameter settings to investigate the practical behaviour of our new scaled algorithms. The inclusion of preconditioning in Scall le SARAH and Scal 1 edd L-SVRG led to improvements in performance compared with no preconditioning in several of the experiments, and Scaled SARAH and Scaled L- SVRG were competitive with, and often outperformed, Adam.
Paper outline. This paper is organised as follows. In Section 2 we describe the diagonal precondi- tioner that will be used in this work. In Section we describe a new Scaled SARAH algorithm and present theoretical convergence guarantees. In Section 4 we give discussions of our results for the Scaled SARAH method, and also compare it with other methods. In Appendix AA] we introduce the Scall led L.-VVR algorithm, which adapts the L-SVRG algorithm to include a preconditioner.
3

---

Under review as a conference paper at ICLR 2023
We present numerical experiments demonstrating the practical performance of our proposed methods in Section[5] All proofs (Sections F.). additional numerical experiments (Section B and further details and discussion can be found in the appendix.
2 DIAGONAL PRECONDITIONER
In this section we describe the diagonal preconditioner that is used in this work. The paper of Bekas jtt al. (2007) described Hutchinson's approximation to the diagonal of the Hessian, and this provided motivation for the diagonal preconditioner proposed in Jahani et al. (2021b), which is adopted here. In partieular, given an initial approximation Do. (to be described soon), and Hessian approximation momentum parameter E (0, 1) (equivalent to the second moment hyperparameter, .2 in Adam (Kingma & Ba 2015). ) for all 2 1,
D, 3D,-1 (1 3)diag (ze @ V P..
where is random vector with Rademacher distribution To is an index set randomly sampled from [n]. and
V Pr. (w))
V (u.))
(4)
Jel
JEJ.
Finally, for >> 0 (where the parameter 0 is equivalent to the parameter in Adam (Kingma & Ba 2013) and Adaffessian (Yo et al. 2020)), the diagonal preconditioner is:
(D.) 2,
max [Del,,)-
(5)
The expression 55) ensures that the preconditioner D, is always PD, so it is well-defined and results in descent direction. The absolute values are necessary because the objective function is potentially nonconvex, so the batch Hessian approximation could be indefinite. In fact, even if the Hessian is PD, D; in (3) may still contain negative elements due to the sampling strategy used.
The preconditioner (5) is good estimate of the diagonal of the (batch) Hessian because Hutchinson's updating formula (3) is used (see also Figures 12 13.. Hence, it captures accurate curvature informa- tion, which is helpful for poorly scaled and ill-conditioned problems. Because the preconditioner is diagonal it is easy and inexpensive to apply it's inverse, and the associated storage costs are low.
The preconditioner (3) depends on the parameter f: if B then the preconditioner is fixed for all iterations, whereas if 3 = then the preconditioner is simply a kind of sketched batch Hessian. Taking 0 < 3 < 1 gives a convex combination of the previous approximation and the current approximation. thereby ensuring that the entire history is included in the preconditioner, but is damped by 8, and the most recent information is also present. See Section G for a detailed discussion of the choice of B.
The main computational cost of the approximation in (3) is the (batch) Hessian- product V2 P2P,,w (w, 2z. Fortunately, this can be efficiently calculated using two rounds of back propagation. Moreover, the preconditioner is matrix-free free, simply needing an oracle to return the Hessian vector product, but it does not need explicit access to the batch Hessian itself; see Appendix in Dahani et al. (2021b). Therefore, the costs (both computational and storage) for this preconditioner are not burdensome.
As previously mentioned, the approximation (3) requires an initial estimate Do of the diagonal of the Hessian, and this is critical to the success of the preconditioner. In particular, must take
Do = m 1=1
Σ diag (z, O V2P (wo)z;).
(6)
where Jy denotes sampled batches and the vectors 2j are generated from a Radermacher distribution. This ensures that D, does indeed approximate the diagonal of the Hessian; see Section 3.3 in Jahani al. (202Ib).
The following remark confirms that the diagonal preconditioner is both PD and bounded.
Lemma 2.1 (See Remark 4.10 in Jahani et al. (2021b)). For any 2 1, we have aT & D, x IT, where 0 < a T vdl.
i... the components of the 2, are +1 with equal prohahility.
4

---

Under review as a conference paper at ICLR 2023
Note that Remark 4.10 is proved incorrectly in Jahani al. (2021b).
Scaled SARAH
Here propose new algorithm, Scaled SARAH, for finite sum optimization 11] Our algorithm is similar to the SARAH algorithm (Nguyen et al. 2017) and the PAGE algorithm (Li ct al. 2021a), but a key difference is that Scaled SARAH includes the option of a preconditioner, D, for all > 0. with preconditioned approximate gradient step. Scaled SARAH is presented now Algorithm
Algorithm Scaled SARAH
1: Input: initial point wo, learning rate 7) preconditioner Do, probability p
2: to = ((ww))
3: for 0, 1, 2.
4: Wt+1 wt ./D,'uy U/
5: Generate independently batches 4+11 for u and Te for Dr-1
V P(W+++))
with probability p
6: Ut+1
+ Sitt (we+1) V Vieta (we);
with probability 1 p
7: Update the preconditioner Dz+1
8: end for
9: Output: wr chosen uniformly from {wx)
In each iteration of Algorithm T update is computed in Step 4 The point is adjusted by taking a step in the direction D of fixed step size The vector approximates the gradient, and the preconditioner scales that direction. A key difference between Scaled SARAH and PAGE/SARAH the inclusion of the preconditioner Dr in this step.
Steplo defines the next gradient estimator 14+1, for which there are two options. With probability the full gradient used. Alternately, with probability p. the new gradient estimate is the previous gradient approximation 8t, with an adjustment term that involves the difference between the gradient of fi evaluated at Wr+1 and at wy The search direction computed in Scaled SARAH contains gradient information, while the preconditioner described in Section 2 contains approximate second order information. When this preconditioner applied to the gradient estimate, each dimension is scaled adaptively depending with low curvature (shallow loss surfaces), while damping directions with high curvature (sharper loss surfaces). The aim is for D, - Ug to point in a better, adjusted direction, compared with vt. Sea eed SARAH is a single loop algorithm so it is conceptually simple. If p then the algorithm always picks the first option in Step 6 so that Sca Scaled SARAH reduces to a preconditioned GD method. On the other hand, if p 0, then only the second option in Step 6 used.
the corresponding curvature. Intuitively, this amplifies dimensions
Notice that Scaled SARAH is combination of both the PAGE and SARAH algorithms, coupled with preconditioner. SARAH (Nguyen et al. 2017) is a double loop algorithm, where the inner loop defined in the same way as update in Step 6 PAGE (Li al. (021aa) is based upon SARAH, but PAGE uses single loop structure, and allows for minibatches to be used in the gradient approximation e++1 (rather than the single component as in 6 Scaled SARAH shares the same single loop structure as PAGE, but also shares the same single component update for the gradient estimator as SARAH (no minibatches). However, different from both PAGE and SARAH, Scaled SARAH uses a preconditioner in Step
In the remainder of this work focus a particular instance of Scal Ecaled SARAH, which uses and uses the diagonal preconditioner presented Section These choices
fixed probability have been made because central goal of this work to understand the impact that well chosen preconditioner has on poorly scaled problems. Convergence guarantees and the results of numerical experiments, will be presented using this set up.
Theoretical results for Scaled SARAH are presented now, In particular, we present complexity bounds on the number of iterations required by Scaled SARAH to obtain e-optimal solution for the non-convex problem ( (recall Section I.I and (2). The first result holds under Assumption I.I
Note that, while PAGE allows minihatches for either option in the update Step 6 most of the theoretical results presented in et (202Ta) require the full gradient he computed as the first option Step
5

---

Under review as a conference paper at ICLR 2023
while the second theorem holds under both smoothness and PL assumptions. First, define the following step-size bound:
1
Theorem 3.1. Suppose that Assumption holds, let > O, let p denote the probability, and let the
step-size satisfy S 7 7 Then, the number of iterations performed by Scaled SARAH, starting from an initial point wo TRd with Do of the non-convex finite-sum problem can be bounded by
P(wa) - PP, required to obtain an S-upproximate solution
r DOL
(IVPD) P
P
T=
0
1
E2
Theorem 3.2. Suppose that Assumptions 1.1 and 1.2 hold, let 0, and let the step-size satisfy
" (7. Then the number of iterations performed by Scaled SARAH sufficient for finding E-approximate solution of non-convex finite-sune sum problem ①
can be bounded by
T T=o max
LT (
P
log 2 Do
1
p p
Note that this last theorem shows that Scaled SARAH exhibits linear of convergence under both the smoothness assumption and the PL-condition.
We know that Algorithm 1 calls the full gradient the heginning (Step and then pn p) stochastic gradients for each iteration on expectation (6 Thus, the number of stochastic gradient computations (i.e., gradient complexity)
Tpm + (1 p)] and the following corollaries of
Theorems 3.1 and 3.2 are valid.
n+1' and let the step-size satisfy 7 S r (7). Then, the stochastic gradient complexity performed by Scaled SARAH, starting from an initial point wu E IR with Ao P(wa) - P", required to obtain an E-approximate solution of the non-convex finite-sum problem can be bounded by O (n I - A
Corollary 3.3. Suppose that Assumption 1.1 holds, let 0,
Corollary 3.4. Suppose that Assumptions T.I and 1.2 hold, let > 0, and the step-size satisfy
77. Then the stochastic gradient complexity performed by Scaled SARAH sufficient for finding an E-approximate solution of non-convex fui problem ( can be bounded by
7 S oj
O LT #
log An
In Appendix A we give our second method Scaled L-SVRG, it has worse convergence results than scaled SARAH, but is be investigated in experiments, but is not be mentioned in the next section with discussions and comparison with competitors results.
4 DISCUSSION
In this section, we discuss the obtained result for Scaled SARAH, including how it relates to the same results for other scaled methods as well for methods without preconditioning. For convenience, we give Table 3 summarising all the results.
Despite in Section we consider scaling based on the Hutchinson's 's approximation, but with our analysis one can obtain similar estimates for Scaled SARAH with Adam preconditioning, In particular, we can prove an analogue of Lemma 2.1 (see Appendix (D) by additionally assuming boundedness of the stochastic gradient for all w: (V)( < M (a similar assumption is made in Défossez et al. (2020)). We present these results in Table for comparison with the current best results for Adam.
In the deterministic case our results are significantly superior to those from Défossez al. (2020), in particular, in terms of the accuracy of the solution time the guarantees from Défossez et al. (2020) are O(s-*), Compared to OASIS in the deterministic case we have the same results in terms of s, but our bounds are much better in terms of d, L, also an interesting detail that our estimates for Scaled SARAH with Adam preconditioner are independent of and with Hutchinson's 's preconditioner depend on vd, which is important for high-dimen high-dimensional problems.
estimates give O(= dependence, the same

---

Under review as a conference paper at ICLR 2023
In the stochastic case, convergence guarantees are also the best among other scaled methods primarily in terms of e. This is mainly due to the fact that we use the stochastic finite sum setting typical for machine learning.
Unfortunately, our estimates are inferior to bounds of the unscaled methods: SARAH (the base method for our method) and SGD (the best known method for minimization problems). As one can see in Table $] all results for methods with preconditioning have the same problem. This is the level of theory development in this field the moment. It seems that our results are able in some sense to reduce this gap between scaled and unscaled methods by decreasing the additional multiplier.
Table 3: Comparison of deterministic and stochastic methods for non-convex problems in the general case and under folyak-t.ojsiewiit condition. In the stochastic case, the table is divided into two parts: the bounded and finite-sum setups. Notation: x² = variance of stochastic gradients, M=uniform bound of (stochastic) gradients, the rest of the notation is the same as the one introduced earlier the paper.
Method and reforeace
Non-coores
Polpal-Lajasveiicc
567 (Socs R.2 and C.2 fromdl i Richtink
3000
(+ log })
8ABAH (Sec. 5.2 fron
Phom Phom
all 20200 Sec. La
2021a
o (A los t)
Deterninidii
Adagrad (Th, I from Difrrezz et al.
30203
daga
Adan (Sec. 4.3 froma Défossez all 2020
GASIS (Ihss 4.17 and 4.18 from Jahani all
2021be
Edu
acdl o loz
Scaled BARAE with Batchisson's is preconditionre (oun)
lox
Scaled SARAS with Adam precenditiener (our))
los
Method reforence
convex
Lojseeee
550 (Secs, B.2 and C22 frmmli Li & Richtink 2000
( Lou
+
Lgu
o(* log Ag7
Addggred (Th, from Défooure
0 [xy2 600 +d o 12"
Stochaiic
Boamdel
Adan (Sec. 4.3 from Deforsex et
20200
0 4x2. Lgp + o Edp))
OAS15 (Tts, 4.17 and 4.18 fronnhhuni es
2021b1
0
530 + of
e a22 Jox
Finite-um
SARAH (Sec. 3.2 from Pham et 2000 Sec. from Lt
2021a3
0 (n + v A0m)
o v #) lox
Scaled SARAH with Hunhimon'ss peccoditooes (ouss
vnn
o i xae v/n # lox
Scaled SABAM with Adam precondtioner (ours)
vi
[1 # J 4 log
for strongly convex problems.
To sum up, our results exceed the estimates already given in the literature for scaled methods. If we take into account that algorithms with preconditioning are strongly attractive from the point of view of real-world learning problems, turns out that we prove the best results for the practical class of methods at present. Meanwhile, our estimates are still worse than those for unscaled methods, in Appendix G we give some reasoning why these estimates are unimproved. Then we present Section 5 with experiments in which it becomes clear that real problems are not necessarily "the worst", on the contrary, it is on practical problems that our method from Sections and shows itself most strongly.
5 NUMERICAL EXPERIMENTS
The purpose of these numerical experiments is to study the practical performance of our new Scaled SARAH and Scaled L-SVRG algorithms, and hence, to understand the advantages of using the proposed diagonal preconditioner on SARAH and L-SVRG. These results will also be compared with SGD, both with and without the preconditioner described in Section 2 as well as the state-of-the-a (first order) preconditioned optimizer Adam.
We test these algorithms on problem ( with two loss functions: (1) logistic regression loss function, which is convex, and (2) non-linear least squares loss function, which is nonconvex. The loss functions are described in details below. For further details and experimental results that support the findings of this section, please see Appendix B Note that all the experiments were initialized at the point wi 0, and each experiment was for 10 different random seeds.
7

---

Under review as a conference paper at ICLR 2023
Deal performences on logiolic loss
0.3
1.2
02-
376
EP
EPlectas
EPfictino
rLVE
12-
11-4
10-4
10m0
10
320
24
300
revi
-ilm
10a
30
1007
20
40
60
326
0
23
20
60
330
23
40
60
300
Effcctio Proses
Figure 1: Best performances of the optimizers, including Adam, on the (unscaled) LibSVM datasets
using the logistic loss. The Scaled variants are shown dashed lines sharing the same color.
5.1 LOss FUNCTIONS
Let P(w) be the empirical risk on dataset {(xi, B:) where I; E Id and yi E {-1,, +1}. Then, the logistic regression loss is
Pagistic(w) - log(1 + we
(8)
whereas for E {0, 1} the non-linear least squares loss (NLLSQ) is
Pallsg( (w) 1
n Ei= (y - 1/ + + "")²²
(9)
We consider two different loss functions to test our algorithms on both convex and nonconvex settings.
5.2 BINARY CLASSIFICATION ON LIBSVM DATASETS
We train the optimizers on three binary classification LibSVM datasets namely wBa, rev1, and real-sim. We also consider feature-scaled versions of these datasets, where the scaling is done as follows: we choose a minimum exponent kyri and a maximum exponent kmazz and scale the features by values ranging from 10amin to 10tmme in equal steps in the exponent according to the number of features and in random order. The setting (kmin kmax) = (0, 0) corresponds to the original, unscaled version of the datasets. We consider combinations of kmin 0, -3 and kmaz 0, 3. This scaling is done to check the robustness and overall effectiveness of the diagonal preconditioner in comparison with Adam. Figure [ shows the results of the first experiment, and presents three types of line plots for each of the datasets of interest where the loss function is the logistic regression loss (8). Figure shows the same for the NLLSQ loss (9). The first row corresponds the loss, the second is the squared norm of the gradient, and the third is the error. Tuning was performed in order to select the best hyperparameters (that minimize either the loss, gradient norm squared, or the error). The hyperparameter search grid is reported in Appendix, Table and a thorough discussion below. We fixed the batch size to be 128, order to narrow the fine-tuned variables down to n, 3, and Figure T shows the performances when minimizing the error the unscaled datasets, (kmin, kmax) = (0, 0). Experiments on scaled datasets can be found in Appendix B.2
Consider the first column in Figure T which uses the w8a dataset. While preconditioned SGD performs better than SGD, for SARAH and L-SVRG this is not the case. Notice that Adam performs well initially, but then further effective data passes lead to small improvement (for all three metrics).
hhtps//www.csic..m ntw. http://wwww....o.oo....////////a ggin//iisymmooossdaasssss
8

---

Under review as a conference paper at ICLR 2023
Dest performences on rileq lows
neal-am
0.20
0.15
6.00-
0.05
Cffcctive
Cffectoo
CPfuctivs
1EVI
real-sm
22
10
10-1
32-1
10-1
10-1
10:1
12- 10
180
20
43
146
wiB
rovi
real-sm
10
22-1
10
1011
32-1
16
46
80
110
23
40
60
160
20
43
340
Figure 2: Best performances on the unscaled LibSVM datasets using the NLLSQ loss.
While SARAH and L-SVRG perform the best on this dataset, after approximately 35 passes for Sca led L L-SVRG and 60 passes for Scaled SARAH, performance is better than Adam. For the remaining three datasets, preconditioning helps in all cases, with Scaled L-SVRG and Scaled SARAH, performing the best.
In order to understand the main factors that affect the preconditioner, we ran comparative studies, including studying the parameters 3, and a, as well as studying the initialization of preconditioner Do, including a warm-up up period, and studying how the number of samples, 2, impacts performance. First, recalling O there did not appear be any significant improvement from averaging across more samples of = per minibatch, neither in the initialization nor in the update step. We also observed that initializing Do with a batch size of 100 was sufficiently good for non-sparse problems, and consistently resulted in relative error of within 0.1 from the true diagonal. However, increasing the number of warm-up samples, proportionally to the number of features, led to observable improvements in convergence for sparse datasets.
We also investigated the role that 3 3 played in algorithm performance. We found that larger values lead to slightly slower but more stable convergence. The best / highly depends the dataset, but the value 0.999 appeared to be a good starting point in general. To ensure a fair comparison, we also optimized Adam's 's momentum parameter (92 over the same range.
Aside from the batch size and learning rate, we found that, for ill-conditioned problems, the choice of a (recall (5) and Remark 2.1) played an important role in determining the quality of the solution, convergence speed, and stability (which is not obvious from Figure D For example, if the features were scaled with kyin = -3 and kimax 0, the best is often around 10-7 (very small), whereas if we scaled with kmin = 0 and kmaz = 3, the best a becomes 10-1 (relatively large). Therefore, finding the best a might require some additional fine-tuning, depending on the choice of rj and B8. However, we noticed that once we had tuned the learning rate for one scaled version of the dataset, the same learning rate transferred well all the other scaled versions. In general, the optimal learning rate in our Scaled ed algorithms is very robust to feature scaling, given that is chosen well, whereas Adam's learning rate depends more heavily upon how ill-conditioned the problem is, so it requires fine-tuning across a potentially much wider range. In our case, tuning and |3 is straightforward, so we obtained state- the- art performance with minimal parameter tuning.
The choice B suggest that this choice virtually removes the dependence on a, and is competitive with fine-tuned / across a large number of values. This makes fine-tuning much easier, even for strong feature scaling.
1/(t 1) was investigated in Appendices B.5 and G.3 Preliminary results

---

Under review as a conference paper at ICLR 2023
REFERENCES
C. Bekas, E. Kokiopoulou, and Y. Saad. An estimator for the diagonal of a matrix. Applied Numerical Mathematics, (7(11))1214-122 1229, 2007. Numerical Algorithms, Parallelism and Applications (2).
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. In Proceedings of the 27th International Conference on Neural Information and Processing Systems, vol. 1, pp. 1646-1654, 2014.
Alexandre Défosse7, Léon Bottou, Francis Bach, and Nicolas Usunier. A simple convergence proof of adam and adagrad. arXiv preprint S.Xiv:2003.023955 2020.
John E. Dennis Jr. and Jorge J. Moré. Quasi-newton methods, motivation and theory. SIAM Review, 19(1):46-89 -9, 1977.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(7):212121159, 2011.
Roger Fletcher. Practical Methods of Optimization. John Wiley & Sons, New York, 2 edition, 1987.
Saeed Ghadimi and Guanghui Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic programming, SIAM Journal on Optimization, 23(4):23411 -3-6888 2013.
Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization. Mathematical Programming, 155:267-305, 2016.
Thomas Hofmann, Aurelien Lucchi, Simon Lacoste-Julien, and Brian McWilliams. Variance reduced stochastic gradient descent with neighbors. In Proceedings of the 28th International Conference on Neural Information and Processing Systems, pp. 2305-2313, 2015.
Majid Jahani, Mohammadreza Nazari, Sergey Rusakov, Albert Berahas, and Martin Takáč. Scaling up quasi-Newton algorithms: Communication efficient distributed SR1. In International Conference Machine Learning, Optimization and Data Science, pp. 41-54, 2020. PMLR.
Majid Jahani, Mohammadreza Nazari, Rachael Tappenden, Albert Berahas, and Martin Takáč. SONIA: symmetric blockwise truncated optimization algorithm. In International Conference Artificial Intelligence and Statistics, pp. 487-495, 2021a. PMLR.
Majid Jahani, Sergey Rusakov, Zheng Shi, Peter Richtárik, Michael Mahoney, and Martin Takáč. Doubly adaptive scaled algorithm for machine learning using second-order information. arXiv preprint wwXhv:2109.05198/// 2021b.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Proceedings of the 26th International Conference Neural Information and Processing Systems, vol. 1, pp. 315-323, 2013.
D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, pp. 2305-2313, 2015.
Jakub Konečný and Peter Richtárik. Semi-stochastic gradient descent methods. Frontiers in Applied Mathematics and Statistics, 3, 2017.
Nicolas Le Roux Le Roux, Mark Schmidt, and Francis Bach. A stochastic gradient method with an exponential convergence rate for finite training sets. In Proceedings of the 25th International Conference on Neural Information and Processing Systems, vol. 2, pp. 2663-2671, 2012.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEF, 86(1 1):2278-2324, 1998. doi: 10.1 1997579777...
L. Lei, C. Ju, J. Chen, and M.I. Jordan. Non-convex finite-sum optimization via SCSG methods. In Proceedings of the 31st International Conference on Neural Information and Processing Systems, pp. 2017.
10

---

Under review as a conference paper at ICLR 2023
Zhize Li and Peter Richtárik. A unified analysis of stochastic gradient methods for nonconvex federated optimization. arXiv preprint arXiv:2006.07013, 2020.
Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtarik. PAGE: A simple and optimal proba- bilistic gradient estimator for nonconvex optimization. In Proceedings of the 38th International Conference on Machine Learning, PMLR 139, pp. 6286-6295, 2021a.
Zhize Li, Slavomír Hanzely, and Peter Richtárik. ZeroSARAH: Efficient nonconvex finite-sum optimization with zero full gradient computation. arXiv preprint arXiv:2103.01447, 2021b.
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. PMLR 70, pp. 2613-2621, 2017.
Jorge Nocedal and Stephen J. Wright. Numerical Optimization. Springer Series in Operations Research, 2 edition, 2006.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 8024-8035. Curran Associates, Inc., 2019. URL http:///ppppppeeeeoroo.....///ce www.innnuippp....
9015 pytorch an imperative style - pdf
-eep deep learning Library.
Nhan H Pham, Lam M Nguyen, Dzung T Phan, and Quoc Tran-Dinh. Proxsarah: An efficient algorithmic framework for stochastic composite nonconvex optimization. Mach. Learn. Res., 21 1110))1-48, 2020.
Xun Qian, Zheng Qu, and Peter Richtárik. L-SVRG and L-katyusha with arbitrary sampling. Journal of Machine Learning Research, 22:1 22:1-49, 2021.
Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. arXiv preprint 1TXXi::99440022377 2019.
Herbert Robbins and Sutton Monro. stochastic approximation method. The Annals of Mathematical Statistics, 22(3):400-40) 407, 1951.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Shai Shalev-Shwartz and Tong Zhang. Stochastic dual coordinate ascent methods for regularized loss minimization. Journal of Machine Learning Research, 14(1):567-599, 2013.
Tijmen Tieleman, Geoffrey Hinton, al. Lecture 6.5-rmsprop: Divide the gradient by running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26-31, 2012.
Lin Xiao and Tong Zhang. A proximal stochastic gradient method with progressive variance reduction. SIAM Journal on Optimization, 24(4):2057-2075, 2014.
Zhewei Yao, Amir Gholami, Sheng Shen, Kurt Keutzer, and Michael W Mahoney. ADAHESSIAN: An adaptive second order optimizer for machine learning. arXiv preprint arXiv:2006.001 007 19, 2020.
Fangyu Zou, Li Shen, Zequn Jie, Ju Sun, and Wei Liu. Weighted adagrad with unified momentum. arXiv preprint arXiv: 1808 03408, 2018
11

---

Under review as a conference paper at ICLR 2023
A Scaled L-SVRG
SVRG (Johnson & Zhang, 2013: Xiao & Zhang, 2014) is a variance reduced stochastic gradient method that is very popular for finite sum optimization problems. However, the algorithm has double is required for good practical performance. Recently, Hofmann et al. (2015) proposed a Loopless SVRG (L-SVRG) variant, that has simpler, single loop structure. which can be applied to problem (T) in the convex and smooth case. This was extended in Qian et al. (202T) to cover the composite case with an arbitrary sampling scheme. With its single loop structure, and consequently fewer hyperparameters to tune, coupled with the fact that, unlike for PAGE (recall Section D L-SVRG uses an unbiased estimate of the gradient, L-SVRG is versatile and competitive algorithm for problems the form
loop structure, and careful tuning of
However, as for the other previously mentioned gradient based methods, SVSVRG can perform poorly when the problem is badly scaled and/or ill-conditioned. This provides the motivation for the Scaled L-SVRG method that we propose in this work. Our Scaled L-SVRG algorithm combines the positive features of L SVRG, with preconditioner, give method that loopless, has few hyperparameters to tune, uses an unbiased estimate of the gradient, and adaptively scales the search direction depending upon the local curvature. The Scaled L-SVRG method is presented now as Algorithm 2
Algorithm 2 Sca led SVRG
1: Input: initial point wo, learning rate 7) preconditioner Do. probability p
2: 20 = Wi., v0- = ((ww)
3: for t =
... do
4: Wi++1 Wt nD,,'vy
2t. with probability p (Wt, with probability P
5: Ze+1
6: Generate independently batches ic+1 for u441 and Ti for D
7: Ut+1 = fu.., (W++1)= - V (2++1) + VP(4+11)
8: Update the preconditioner Di+1
9: end for
10: Output: wy chosen uniformly from (woFFo
Sca led L-SVRG can be described, in words, as follows. The algorithm is initialized with an initial point Wo. a learning rate v), an initial preconditioner Do. and probability At each iteration & > 0 of Scaled L- SVRG (Algorithm 2 search direction 6; generated. This is made up of the full gradient plus small adjustment. Next, the new point W1+11 is taken to be a step from we in the scaled direction D of size y). The new point 2++1 is either the (unchanged) previous point 2, with probability p. or the scaled approximate gradient step Wz+1 with probability 1 1- p. Finally, the preconditioner is updated and the next iterate begins. The output, denoted by uT is chosen uniformly from the points wt, for t = O,..., T, generated by Scaled L-SVRG (Algorithm) 2p.
Note that key difference between L-SVRG (Hofmann et al. 2015 Qian et al. 2021 and our new Scaled L-SVRG is the inclusion of the preconditioner in Step 4 recall that a competitive preconditioner is described in Section 2
The following theorem presents a complexity bound on the number of iterations required by Scaled L-SVRG to obtain c-optimal solution for the non-convex problem (I.
Theorem A.1. Suppose that Assumption 1.1 holds, let = > O, let denote the probability and let
the step-size satisfy 1) < min TT>
//o 2/3
144973 +t Given an initial point wo E Rdd, lel Do
/24L'
P(w.) P Then the number of iterations performed by Scaled L-SVRG, starting from wi- required to obtain an E e-approximate solution of non-convex finite-sum problem ① can be bounded by
T LA
T= O
a tis
While the previous theorem held under a smoothness assumption, here we prove a complexity result for Sca led SARAH under both smoothness and PL. assumptions.
12

---

Under review as a conference paper at ICLR 2023
Theorem A.2. Suppose that Assumptions
1.1 and
1.2 hold, let E let p denote the probability
and let the step-size satisfy S min
pr
( I
2/3 t
Then the number of iterations
performed by Scaled L-SVRG sufficient for finding an E-approximate solution of non-convex finite-sum problem (1 can be bounded by
A
T=
max
(p (p'appaa
log
&
give corollaries on the stochastic gradient of complexities.
Corollary A.3. Suppose that Assumption
holds, let > 0, p - I-I and the step-
size satisfy S min AL' V2AL" 1442/3 L Given an initial point wo E Rd, let Do = P(wo)
y/a pais
Pt. Then the stochastic gradient complexity performed by Scaled L-SVRG, starting from wo. required to obtain an e-approximate solution of non-convex finite-sum problem ① can be bounded by (n F LAa g2 n2/s).
Corollary A.4. Suppose that Assumptions
1.1 and 1.2 hold, let > 0, let n+1 and let the
step-size satisfy S min performed by Scaled L-SVRG sufficient for finding E-approximate solution of non-convex finite-sum problem ① can be bounded by O (frz L n/
pf la
(B)
I. (.)
Then the stochastic gradient complexity
6
4
A/s
log An
B ADDITIONAL NUMERICAL EXPERIMENTS
Here we provide additional details related to our experimental set-up, as well as presenting the results of additional numerical experiments.
B.1 BEST PERFOR MANCE GIVEN A FIXED PARAMETER
Table 4 states the hyperparameters that used in numerical experiments.
Table 4: Hyperparameter search grid.
Settings
Optimizer
SARAH, L- SVRG, SGD, Adam
Scaled
True, Fal (except for Adam)
Dataset
a9a, w8a, rev1, real-sim (0,0), (0,3), (-3, 0). (-3,3)
(kminz kmaw)
Loss function
logistic, NLLSO 0,....9
Random Seed
Parameters
Batch Size
128, 512
2-20 2- ,.,,, 21
10-1, 10-3 10-7
0.95, 0.99. 0.995, 0.999, avg
We ran extensive experiments order to find the best performing set of parameters for each optimizer on each dataset. For our parameter search, we fixed one parameter (e.g.. 10-1), and then found the best choice for the remaining parameters, given that fixed value. This allowed us to understand how robust the algorithm's 's optimal performance is, with respect each parameter. In other words, 'how does changing one parameter degrade the quality of the solution or the overall performance of the algorithm?". We also report the best overall performances.
13

---

Under review as a conference paper at ICLR 2023
Here, consider fixing of three parameters: 7/, 3, and a, and then plot the trajectory of the gradient norm squared [w:)( for the setting that minimizes the eπror with respect to the other parameters. The values 'a none' and :B none' indicate non preconditioned trajectories, and the value / = avg indicate the choice 3t = 1 (t + 1) (or more precisely, as described in Appendix
B.5
See Figures
5| 6
B.2 CORRUPTING SCALE OF FEATURES
We consider the settings where the features of the data are corrupted with a given logarith- mic scale. We show the best overall performances 4 scaled datasets with (kmin kmar) ((-3,0) 0). (0, 3), 3.33-- This allowed us to understand the impact of no preconditioning versus preconditioning on poorly scaled problems. The results shown Figures 7 and
B.3 CONVEX VS. NON-CONVEX LOSS
We test our algorithms on the non-linear least squares loss, which is a non-convex loss function. We show the best performance the unscaled datasets, well as datasets scaled with (kmino kmax)
(-3.3). See Figures 10 and
B.4 RELATIVE ERROR OF Do
For the preconditioner described in Section 2 the initial preconditioner Do must be chosen appropri- ately. Note that, if diag Ho) is the true Hessian diagonal for some initial point wo. then the relative error of the approximation Do diag(Ho) is
Do diag Ho)l
diag Ho)l
For our numerical experiments we used this relative error to determine whether the initial precon- ditioner Do was sufficiently accurate. In particular, we noticed that, if a minibatch of size 100 was used, then the resulting Do almost always reached a relative error of below 0.1, for dense datasets. improve convergence and quality of the solution, but
For sparse datasets, more warm-up samples in either case, a minibatch of size 100 was sufficient to establish convergence. Thus, we initialized
Do with size 100 minibatch in most of our experiments. See Figures 12 13 and 14
B.5 CHOOSING Be
We show plots where we finetune a and on a wider range of parameters. Similarly to Section B.1 optimize the other parameters by fixing the parameter of interest at the chosen value, and report the optimal performance metric. We only consider Sca led SARAH this experiment. We show plots where we minimize either the error the gradient norm under the logistic loss or NLLSQ loss. We also show the optimal performance when choosing 3 =
7-to where to is the number of warm-up samples. We run experiments for 10 random seeds and show the confidence intervals for each hyperparameter setting. We see that the suggested choice for 3, consistently competitive with
the best / and is robust to feature scaling as well. See Figures 15 16 and 17
B.6 DEEP NEURAL NETS ON MNIST
In order to demonstrate that our algorithms are indeed practical and competitive with the state-of- the-art, we test them on deep neural nets. The setting of our experiment is widely accessible and well-known; train the LeNet-5 model on MNIST dataset with the cross entropy loss Lecun al.) (1998). For this experiment, we believe that it suffices to test Scaled L-SVRG vs. Adam. For SVS,,G we use 0.999. The programming framework we run this experiment on PyTorch Paszke et al. (2019). The hyperparameter search grid is slightly reduced for this experiment. To be specific, learning rates bigger than 2 and lower than 2-14 are omitted, and we only consider / in {avg, 0.99, 0.999). The result is shown in Figure 18 and 19 We observe that the performance of Scaled L-SVRG is indeed competitive with Adam in this simple deep learning problem. We omit trajectories that diverge in this plot, which is why the value 10 is not seen in Figure 19 In the future, we plan on running more sophisticated deep learning experiments, and explore ways to adapt algorithms these settings in particular.
14

---

Under review as a conference paper at ICLR 2023
Best performances on lagistic loss
wBa
rcv1
real-sim
0.7
SAATE 2 3-
Suitte 1.B smn
en at-i2t
0.6
0.6
Piai
0.4
Pimi
pin)
0.3
0.2
0.2
0.2
0.1
20
40
20
100
60
80
100
40
60
80
100
Effective Passes
Effective Passes
Effective Passes
w8a
rcv1
real-sim
10-4
E.0 yor ande awaxsn
30
10
10-4
10
10-4
Effectivn Passes
Effective Passess
Effective Passes
WS3
rcv1
real-sim
s00ti-aa on
sodte
10-1
Enerr
Entrr
Enter
10-3
10-1
10-3
Figure 3: Performance of the best parameters minimizing the error using the logistic loss.
15

---

Under review as a conference paper at ICLR 2023
Best [jorteoll? y given logisdi los0
SC3[VEN)
12
23
107
11"1
10'
Eteckee Tesses
Chiccvv Taiins
Pleckrefessm
11.
20
18-1
Pattes
L-SIN(roo2))
15.m
12:7
4.-4
10-
23.
38
10
Adam//(aa)
10
15-1
20-
20"
18-4
207
10.
100
28
20
Figure 4: Trajectory of P\:())) of the best parameters minimizing the emror given 1) and logistic loss.
16

---

Under review as a conference paper at ICLR 2023
Best [jorteoll glven logisiicles
SCI[VEN)
SCl[real-
10
13
23
Effectie Tasses
Chicciv Tasies
Pleckretesom
10"*
15"
10m
30
Pattes
L-SIRG
(r
L-StRG
16-
4344
23
207
18:1
38
16
23
20
Adam//Oaa)
Adrad -5563
23-
121
10a
2p
11"
10
15-
100
28
20
Figure 5: Trajectory of [P(w))] of the best parameters minimizing the errors given B and logistic loss.
17

---

Under review as a conference paper at ICLR 2023
Dest [|sPrall given on leglete lone
144
10"1
16-
2344
107
10.4
Efficter Froms
oPhertve Partes
Plickee
11-1
10-
23.
32.0
16
16-
20
Cheecive Parres
L-211G/wda)
L-319G(ror3)
L-2VNG rank-sni
10"0
12-1
10-
33*
10-1
12'
10
Figure 6: Trajectory of P( of the best parameters minimizing the error given a and logistic loss.
Best performances on logistic less
w8a
royl
real-sim
0.7
10D ped Feede di goond
100ge1 Tee E2 go-m
0.6
0.6
0.6-
0.5
Aferrse:f A. +305)
Anamicega A 1300
Markecz2 d 1950
0.4
0.3
0.2
0.2
0.2
0.1
0.0
100
100
100
Effective PaNses
Effective Pasiess
Effective Passes
wBa
rov1
real-sim
10-3
B00Ieua 2e -0t Aug
10
10:1
10. 9.
Afurity A-1E (355
Aearie A- Aroo
20-7
10->
10-
10
10:43
100
Effective Passes
Effective Rasses
Effective Passes
wBa
rov1
real-sim
Adurty- -961
10-1
Adamic 2nd 2 An0o
10
(9 Asaric pi Anw
bror
10-4
10-3
10-1
Effective
Effective
Effective Passes
Figure 7: Performance of the best parameters minimizing the error given (kimin kimaz) = (-3,0).
18

---

Under review as a conference paper at ICLR 2023
Best performances an lngistic loss
wBa
rcv1
real-sim
Si0t 2 and ang
1.0
500ly and Lon,, piiss
prop
0.8
0.4-
0.6
0.3
0.2
0.2
20
40
60
80
100
20
40
60
80
100
20
40
60
80
100
Eff activi Rasses
Effoctive Posses
Effoctire PaEoos
wBa
rcv1
reaksim
107
10
Sifeew foond
S0liped and aword
10
10.
99
10
20
10-1
10.5
10-1
10-
20
60
100
20
40
8D
80
100
100
Eill sccivve Passus
Effective Passes
silectir Pasces
wBa
revl
reak-si
socty Ses aeg
10:1
10:2
Enor
Erer
Emor
10-1
10-1
10:-
10-1
20
60
200
20
40
60
80
100
100
Effective Passas
Effective Passes
Effectire Passes
Figure 8: Performance of the best parameters minimizing the error given (kimin kmazx) = =0,,3)
Best performances on logistic loss
wBa
revl
real-sim
5000
500tpw 10 gommi
strgge ges po poon
60
50-
40-
3000
Rima
2000
20-
1000
10-
20
40
60
80
100
20
40
60
80
100
20
40
60
80
100
Effective Passes
Effective Passes
Effective Preses
wBa
revl
real-sim
10a
Silko pame
GDDced and Do deoml
amoue onte Ch eounc
30'
107
10
10-1
16-1
10-4
1
10
10
10-1
20
60
60
8G
100
20
40
60
80
100
40
160
cctivvv Pass
Effective Passes
erfcctie Pasoes
wBa
rev]
real-sim
Enor
Ertrr
Emir
10-1
10:1
10-2
20
60
100
60 Effective Passes
100
Etfective Passes
Effoctive Poe025
Figure 9: Performance of the best parameters minimizing the error given (kmmin kmax) = (33.3).
19

---

Under review as a conference paper at ICLR 2023
Best performances on niisa loss
w8a
rcvl
realsim
0.25
Antised i Late on de
Sifeew Saete 12, 12.sed. ong
0.20
0.15
0.15
0.15
0.30
6.10
0.05
0.05
0.05
0.00
0
20
40
60
80
100
20
40
60
50
100
20
40
60
60
100
Eflective Passas es
Effective Passes
Effective Passes
w&a
rcvl
real-sim
10. 0
Solle yod 18-00 2-104
10
Sclte 2e1 1a-3 Lane
10.
10:4
1017
10
10.
10
20
40
60
20
100
20
40
60
90
100
20
40
60
60
100
Effection Pricees
Effective Passes
Effective Paeses
wBa
rev1
real-sim
Soilpne pn 30 pi 9900
503 p0 p-a
Slitew be- and 1996
10-1
10
Broe
10-1
10-1
20
40
60
1.00
40
1.00
Eflective Plecess
Effective Passes
Eflectivn Passes
Figure 10: Performance of the best parameters minimizing the error using the NLLSQ loss.
Best performances loss
real-sim
0.25
0.25
0.25
M 201,
MiMeogee oen, pacas
0.20
eugh
0.20
0.20
0.15
0.15
0.10
0.10
0.10
0.05
0.00
20
40
60
90
100
20
40
60
80
100
20
40
60
80
100
Efficc Pocses
Effective Passes
Effcctive Passes
wBa
rcv1
real-sim
1.0
100
Saketiin onl wol
por
10a
SMRAr1L aworel, po0d00
10-4
10-3
30
10-4
10
10-1
10-1
10-4
10a4
0
20
40
60
90
100
0
20
40
60
80
100
20
40
60
30
100
Lifeetive Pancess
Eltective Passes
Lift litecctve Paoces
wBa
rcvl
realsii
10
Entr
Erre
10-1
10-²
20
40
60
100
20
40
60
100
100
20
40
50
20
100
Effective P Fasssss
Effective Passes
Effecttve Pusces
Figure 11: Performance of the best parameters minimizing the error on NLLSQ loss given (kmin, kmma)) = 3)..
20

---

Under review as a conference paper at ICLR 2023
135
3.71
337
ado, 120
Jie 05 12
PCrL SS 130
reat Loo E54228
13
30"
200
137
377
121
327
Figure 12: The diagonal values of the true hessian Ho vs. the estimate Do. The tree a levels in our hyperparameter search grid are shown in dashed pink horizonatal lines. Increasing the number of warmup samples is beneficial, with slightly diminishing benefits as the batch size decreases. This can be seen from the larger number of light pink points around the diagonal for batch size 1024 on real 1 Frallssin i.s...
rivi kiv
20"
13"
roat E2-128
140
139
1.7
13"
301
12
1444 www.0/00 204 351
Figure 13: The diagonal values of the true hessian Ho the estimate Do given (kman, kmax) -,33).
21

---

Under review as a conference paper at ICLR 2023
12.0
200
450
202
150 150
Figure 14: The relative error of the diagonal with respect to the diagonal of the true Hessian plotted against the number warmup samples. The value corrupt indicates the feature scaling. For sparse datasets, it is more difficult to decrease the relative error below 0.1.
(redi-3..31
10
10:11
30:1
10.1
10:14
Figure 15: Optimal error achieved with the logistic loss given the value of the parameter. The optimal error for the "aavrrgging" B3 shown as a dashed red line. The arguments after the dataset name are the scaling factors.
121*
18
18
22:54
22.1
42.
20.5
Figure 16: Optimal gradient norm achieved with the logistic loss given the value of the parameter. The optimal gradient norm for the "averrgging" 3, is shown dashed red line. The arguments after the dataset name are the scaling factors.
Credi-33-3
11-0--
11
1271
2'1
1371
1371
1011
20
12:11
22:1
12:1
12"
20
1251
12:1
13:1
Figure 17: Optimal error achieved with the NLLSQ loss given the value of the parameter. The optimal error for the "averagging" B, shown as dashed red line. The arguments after the dataset name are the scaling factors.
22

---

Under review as a conference paper at ICLR 2023
performances on
100
2.0
10'
1.5
P060
Enorr
1.0
10-1
0.5
15
Passes
Effective
Figure 18: Best performance of Scaled L-SVRG and Adam on MNIST.
Best Error given
L SVRG mnitt))
Adam(mn it)
109
102
B 800030025
Ereer
Error
10
10-2
10-2
10
15
20
25
10
15
20
25
Eftective Passes
Eftective Passes
Figure 19: Best error given on MNIST.
23

---

Under review as a conference paper at ICLR 2023
C
LEMMA 2.1
In this section we prove Lemma 2.1
Proof: To begin, note that by constructing matrices D, according to (3) (6). Dr is a diagonal matrix with positive elements on the diagonal, where every elements is at least a. Hence, al Dr-
To prove that D < rI, let us show that all elements of D do not exceed I. Based on it suffices show that ||diag (zt @ P2 (wx) al S r for all
||diag (2r @ V (u 11 - (zt 3
P.. (w))))) 1l
2
Σ (v Ps. (wo))ssl
max
Σ (V Ps. (we))es
< max
< max
(2 P.r. (w:)));
j=l
d d
(w:))
S dI V2 Ps. (1e (1,)) - dT.2.
In the last step we use L-smoothness of Ji (Assumption ||diag (ze @ V2P (w))aa 1l =
1.1
Finally,
we have
D LEMMA 2.1
FOR ADAM
In this section we prove Lemma 2.1 but for Adam preconditioning. The rules for calculating the D-matrix for Adam method are as follows:
Dj B,D?_, + (1 3.)
D
diag (W)(w)) @ (
Joo
jeJo
where
8r B gt-1
with (E(0;1)
H3.
diag ([)(w)) @ V[((w)))
go+1
Tt
jEZ.
and
(D.) 4s
max(a, Dele,d
Lemma D.1. For any 2 1, we have al D, & TI, where a a M.
Proof: To begin, note that by constructing matrices D, according to these rules, D, is diagonal matrix with positive elements on the diagonal, where every elements is at least a. Hence, aT x D.
24

---

Under review as a conference paper at ICLR 2023
Moreover, using the diagonal structure of H one note that
1
10
diag (()(m) @ (wr))
ITt
jEN.
||diag( (f C (f
[Tl
JEN
(W) o V.f(w))lls
jE
1
[w)(
[V, M
JEJ.
Finally, we have |13 a0. S M2, And then, al क D. MT TT.
E Scaled SARAH
In this section we present the proof' for the main theoretical complexity results for the Scaled SARAH from Section 3
Lemma E.1 (Descent Lemma). Suppose that function P satisfies Assumption 1.1 and Algorithm 1
generate a sequence Jee- Then we have for any 2 0 and 1)
P(W++1) S P(w.)
1 IVP(w.) 12112
L
|1 will..
" 3/ (V
2a
2n
2a
Proof: Using L-smoothness of the function P and 1 $ Dr
L |2+11 - well
wr+1 - wt) 1(w++1) SP(w.) + (VP(w:), We41
I
<P(w.) + (VP(w:), W++1 w.) +
|| we 11 1.2-
2a
With an update of Scaled
SARAH: W++1 = wy -11D, -
Ur we get
P(W++1) SP(w)) + (V:(w)) -n + "
(ir we+1), wx+1 we)
L
+ ||+++1 - we wel1..
2a
=P(wx) + - Ut. PP(w)) - vve) D-
- -n(VP(w:) - VP(W))) (2
1) || we 12.
17
2a
=P(w:) n/ PPw.) - 1/ P(w.) v. VP(w:))
-0 17 2a
L
|10e41 wall?
25

---

Under review as a conference paper at ICLR 2023
Let us define Wt+1 w, (PP())) Using this notation and update w1+11 w)
n Dr 1 then we have
P(w++1) SP(w)) + 1) /V[[)))))) - vel vel.b, (wi+1 W141, we - x1+1) D.
{ 13
L.
||0++1 - well?.
2a
L
-P(w)) + 17) (V Del vel...
1 wy 11
2a
1
||1--1 wz+1 11 + +Ilwr=
We++ 11
-1lux+1 -wall wr/l (.)))
21
L
-P(w)) + n/ [/w)) mel mel
| wirl2
2a
(T/VVP(w:) vell - + 21
+
|| We well? (l?
Lemma E.2. Suppose that the function P satisfies satisfies Assumptions generate a sequence {we]t2o- Then we have for any 2 0 and 1)
1.1 1.2
and Algorithm
P(w++1) - P < (1- 72 (P(w)) p*)+
" PV:(w) wall
1
L
||
Wz 1l
2a
2m
2a
(10)
Proof: According Lemma E.1 we have
P(wx+1) S P(w))=
V P(wx) vzl12
1
L
|
will..
P
11
20
21y
2a
Then with D-1 & t1 and PL-condition, we have
") /V(ww) - -1,11 (p-11
I.
P(w++1) P <P(w)) P +
|10011
we
2a
2n
2a
n
|VP(w;)]
21
L
<((w)) p + P(we) - v2l12
|10e+1
well.
2a
2n
2a
(P(w,) - -P)).
r
Lemma E.3. Suppose that Assumption T.I holds. Then we have
E [100411 VP(w [[]] < p)E [lle - [P(w))11 (1 (1-p)L2 E ||w 10041-1,113.
Proof: Lemma from (Li al.
2021a)
gives
E [1lee41 P(w S (1 F) [llce - VP(ww))] + +1 - p) 1 [[]we++ -wel
Using I x D., get
(1 (1-p)T? p)T
||041 VP(W s p)E [|ee
vP(w))1
[1wee1-wellf well
Theorem E.4 (Theorem Suppose that Assumption I.I holds, let 0, let p denote the probability, and let the step-size satisfy
7
5
L
1
1-p
26

---

Under review as a conference paper at ICLR 2023
Then, the number of iterations performed by Scaled SARAH, starting, initial point wy R with Ae = P((w)) - P", required to obtain an E E-approximate solution of the non-convex finite-sum
problem can be bounded by
T T=
DnL 8²
1 P
)
1
a
p
Proof: Using Lemmas|
E.
we have
P(wr+1) p
"
V PV((+++)) v2+1ll 112
2ap
<B
P(w,)
p + |V - vell²)
2a
1
I.
||wct1 - well3.]
||utt1-wellf
"E | w: )1 |1 p-1
27
2a
2
1
(1
- p)B |||e PP(w)))
(1 L)
E [|l1ee+1 - wxll3)
2npp
a
P(we)
-p*
+ 77 (
P =]
20p
1
L (1 L²
E [1]200+1 w/ll" 1²]
17
21
2a
2a p
Choosing 1) 1
a
and defining Ve+1 = P(we+1) - P +
V [P(w++1) - 004111 we
[11+ v
20p
have
"E [VP(w))
E V
Summing up, we obtain
7 Σ
b < E [o [r).
Using that ur is chosen uniformly from all wy from 0 to T
1, we have
E [
E [
E
|
T
With Au Vu P(wo) P we get
2
B )r
E
IE
TE
<
n/T
Then
Aol')
(Lاا) l'
1 1
T = 0
= -0
1 1
n
V
Theorem E.5 (Theorem sizp-size satisfy
3.2 Suppose that Assumptions 1.1 and 1.2
hold, let e >> 0, and let the
a
1 5 L 11+
Then the number of iterations performed by Scaled SARAH sufficient for finding an e-approximate solution of non-convex finite-sum problem [ can be bounded by
T =
max
LT 1+
p
log
Ao
a
27

---

Under review as a conference paper at ICLR 2023
Proof:
Using Lemmas E.2 E.3 we have for some B >> 0
E P(w)+1)) - p + B
V P (w++1) - 11-1
7/
E [P(w))) - PT] + 21 E [|V)((w) - vz11
T
2a
1
L
E || wi [.
211
20x
[1uee [P(w))]1 + (1 11-pp p22
+ B
(1
p)
E || we wallB.]]
a
s 511 np
E
(P(w))
- P*] +
17
+ +B(1 p)) E [I//P(w)) =eel?
2a
L (1-P)L2)
|1ut11 - well wel12.]
21
20x
α
We need to choose 17. B such that
71
1
L
(1 L2
+ p) - 1
B;
B N 0.
2a
T
211
2x
If we take B = "
and 17 S min {
pl
a
}. we get
pa
2p² 21
1+v 1=
(P(w)-1) - p + B B( U2 12+11111 S (1 (1- T
T/
E [P(ws) - P* + BlIVP(w;) veel
and then obtain
E P(wr) - P + B Ur 11 S (11
?/
Du.
r
Finally,
r
Au
- LT p a
1 1-p) P
} log A
T
log
= |max
1+
1111
F Scaled L-SVRG
Here we provide proofs for our theoretical results for Scaled L L-SVRG
Lemma F.1. Suppose that Algorithm 2 generate sequences (werr2 and fzh22- Then we have for any 2 any 1) and B 0
E, [1ww++ 1 < n12
E, [Ival1B;
[ +11-p)(1++BB) [llu - z 11 +=1]]+(11p))
| P(w )BB,
aB
Proof: Using definition 21+1 and update of Scaled L-SVRG: wi+1 wi - -n,;" 1 U2. we have
E [B [llwe+1 2++1 []]]] =pF [|
wx] + (1 Ep) E [[l - []]
prf²
E leell??.-
+ (1 p) [|1044] - 21
a
Here we additionally use DT-1 & 1T. Next, we estimate E [|| - 2 11:]
E [1lwe11 - 2 =E ||we - nD, U/2 11
E [l ze 2| + 222 E |10x b--1
1 -2r/EE [D, ve, we - z1) -20)
28

---

Under review as a conference paper at ICLR 2023
Using unbiasedness of vt, get for some B
+ 17²
E ||
-2112
=E ||a0 - =ell
E
|1
b.
2nB (Dp'v((wr)...... wi - 20)
n
E
[11e0e
=ella]
+
E
|lvel
a
[PPw,)))))) || - BE |||u - 2=112)
"
IE
aB
((1 + 1, [[w
24 ||] +
"
RR
[VP(W:))l
" [1:11
aB
a
Combining inequality and equation, finish proof.
Lemma F.2. Suppose that function P satisfies Assumption (we)e2n Then we have for any 2 0 and 1)
L.1 and Algorithm
generate sequence
61.2
E
S 3E [IVP(W))
E [[ - [2
(11)
Proof: Using definition of Us, we have
E
|| l, -
V Sa (wx)) (l((z)) + VP(=)) B. 1
<3E
V (w))(w))))))))))))))) 133,1
3E / - P(())) 13-1
+ 3E
fi, (wx)
(+,,l B
6T.2 E [|we ==
<3E
[VP((=))) [
Here we use Assumption
and DJ+ x TT
Theorem F3 (Theorem 3.1 Suppose that Assumption probability and let the step-size satisfy
T.1
holds, let > 0, p denote the
{a ypa 22/3 1
n S min
4L V2AL" 1442/3 L T
Given initial point wo E Rdd let Do P(wa) P Then the number of iterations performed by Scaled L- L-SVRG, starting from wo, required to obtain an e-approximate solution of non-conver finite-sum problem ( can be bounded by
LAO f/s
T=
Proof: Using L-smoothness of the function P and I $ D', we have
I
E [[[(w4+)] SE ((w,)]
E (E w[+1 - w()l +
E
|100+11
well
2
L
E P((w))) E (V P (w))) Mr+1 -
E
||
2a
Taking into account an update of Scaled L-SVRG, we obtain
E [[P(we+)) P*] <E P(w.) - P*] E (VP() -n 02))
|1 11,,1
+
2xx
Ln²
=E(((w)) - - (VP(W:)), D.'
+
E
|10 11,,1
2a
29

---

Under review as a conference paper at ICLR 2023
Let us define P141 P(W1+1) - P* + Allwe+1 2+11l for some A >> 0. Using Lemmas F.1
F.2
we have
Ln²
E
[
SE [P()) - PT] m IVP 11,, +
E
|1va
[1; 1
+ Al [[|we+1
=+1
2a
L
A
E (P(w. - P*] - 1ytR
|V (we) > b. + 17²
+
E
[Iwell8
2a
+ +(1 - (1 + B) E [||ux [2
+ A(1 p)
"
R
aB
SE (P(w,) - p- 1 A(1 p)
E
V (v 6-
aB
A(1 - ()(1 + B 1116 2x [|]]
+ 122 ( L + )) 2E [IVP(w>))] D.
2L
E [[w, 21 =1111]
22
a
<T (P(ws) - P*] - (1 A(1 A(1-p) p)
2A |
[IVP((=))
a "
aB
a
T
1,2
+ +A (1 (1-p)(1 + Bn) + +1p
+2
E 1100 - 2e|2]-
(12)
A
a²
We need to choose A, 17. B in such way:
A(1
p)
2A
L
2
(1
(1-p)
p) (B) +1²
L
+2
a² I 1.
I
aB
4'
A
Thus, taking
312²1 L3
P
1
(P)
1/2
(p)
2/3
a
A
pa²
B
3m)
17
min
4'' 6
6 $6
L'
we have
E [[ < E
[
"E
Summing up and using that ur is chosen uniformly from all we from 0 to T - 1, we get
4Aol'
6
36
4L
E P((.))1 S \
S Tn
S
max 1,
p 1//s
T a
Then
T LAo
T= o
Theorem F.4 (Theorem A. Suppose that Assumptions probability and let the step-size satisfy
1.1 and 1.2
hold, let e O, let p denote the
pl la 6i 4L
(2)
1/2 1/2
P 2/3 a
S min
I
LJ
Then the number of iterations performed by Scaled L- L-SVRG sufficient for finding an
approximate solution of non-convex finite-sum problem ( can be bounded by
1
L.
T=O O max
P a pppppp))
Proof: Starting from
12 we get
E [0.+1] (Pwx) - P*] -1 --] ( A(l p)
2A
L
E [[IVP(W>)]B.)))
=1)
aB
+A ( (1- + nB) 2
L
1
2
E
[[|
[w ze 1=
A
2
30

---

Under review as a conference paper at ICLR 2023
We use Di's & I and Assumption 1.2 and then get
E 1++1 SE (P(w: - PM] !! (1
A(1 p)
2A
L
E [1
a
aB
a
L
L
+ A (1 - p1 nB3 1/²
2
E2
[|
zell²1
A
a
< (P(wt) - PT] m1
A(1
2A
1
11
=
E [P(w,) PM]
r
aB
L
1
+ A (1 (1 + B) + 1/2
E
[|luet
==11²]-
A
2
We need to choose
A, B in such way:
A(1 - p)
2A
L
L
1m
-1
(1 - p1 + 18) +1
+2
S
a8
A
a
41
Thus, taking
A 317² L3
pl
1 aa
1/2
2/3
B
17 S
min
pa²
31/
6
4
6
we have
P1+1 S
1 1-min
min
p
ap
P
1/2
opp
(P)
2/3
aj
24'
rL
6
4
6
4
Then
1 T
ITTA
T = 0 max
(p' a'ap' 3''pp//p1
G THE ROLE OF 3 IN THE PRECONDITIONER
The purpose of this section is to better understand the role that 3 plays with regards to the convergence theory and practical performance of algorithms. Recall that / is the momentum parameter for the preconditioner (3), and it controls the weighting/trade-off between the past curvature history and the current minibatch Hessian.
Note that the analysis presented in Appendices E and F does not impose any additional assumptions on B, which demonstrates kind universality of method and convergence theory. Note that, Adam (Défossez et al. 2020) and OASIS S do not have such universality. In particular, for Adam, the parameter B2 (corresponding to ,3 in this work) is critical: for Adam to converge at the rate 1 1/VT in the non-convex setting, one must choose B2 = 1/VT, while for small 82 the method diverges (Reddi et al. 2019). The dependence of CASIS on 3 is only presented in the adaptive case, but this dependence negatively impact, or destroy, convergence. This section aims to better understand the choice B.
Consider the following quadratic function:
f(r v)
L
+
y1
2
1
y
2
The corresponding Hessian for this function is
Lta
L-
2
L- 14
L++
and
L-H 1 Lt# 2
+
2?
0
diag (ze 2 v2fz)
2
Lott
L-
2
22
2
2
31

---

Under review as a conference paper at ICLR 2023
where 2, is from Radermacher distribution. One note that with probability 1/2 our approximation
diag g (z V2 is
0
1 0
or
(13)
L
0 14
G.1 THE WORST CASE
Intuitively, with a good understanding of 3, should be possible to get better practical performance of the method. For example, convergence analysis depends upon the factor I'/a (recall Remark(2.1] and good choice of can shrink this factor. However, here we present the worst case, and show that for the function described above, unfortunately, improvement is not possible. Choose μt, that for Dr have possible matrices with probability z:
a 0
or
L
The matrices above scaled identity matrices, that applying the preconditioner is equivalent simply dividing the gradient by constant. This scaling can dramatically change size of gradient especially in the early iterations, when O. particular, when we work with the second matrix we change gradient by 1/a. Then it is really worth taking a step T. impact of scaling, T, original stepsize for GD type methods. Additionally, if randomly work with the first matrix with L, this additional L. goes to the convergence of the method as r.
G.2 HOW TO CHOOSE THE CONSTANT 3
D, is a linear combination of identically distributed independent matrices natural consider reducing the variance of Dr. Note that
13 In such situation,
D: = B'diag (zo o 2
Σ
(z+ o v=
and notice that, by (3) every diag (2+ 2 fz+) Dj can be computed as
has the same distribution. Then the variance of
Var[D,]
g2t +
Σ
82c-27
3)2 c.
where C' is some constant (that does not depend B). Now, minimizing this expression w.r.t [0:1]:
min $E|0:1]
g2t
2r -32
Using the optimality conditions has:
82t-1 (2t 1 + 213 + 2) 1.
If we have limit of iterations T and if we minimize the variance of the final preconditioner, we can take
1
1.
27 -27-111 273+2
2//TT T-000
G.3
IT IS BETTER CONSIDER VARYING 35
As in the previous section, here also want reduce the variance of Dr. But now, let consider the case when B is allowed to vary:
Dj = 3, D. + (1 8.)diag (+ V2
32

---

Under review as a conference paper at ICLR 2023
To understand how to choose 3t, note that at each iteration, because diag (2) @ f21) get one of the two matrices given in (13). To reduce the variance the matrix D, one can choose D, as
1 D.-1 1+1
D. diag (z, f2,)
diag (z f2)).
Thus,
8 =
t+1 1
Using the identity and independence the di ag (z+ ④ f2+) distributions, one can note that such Bt gives better variance then the constant from the previous subsection.
H DRAFT OF EXPERIMENTS
ALBERT training
ALBERT training (zoomed)
Adam
Adam
10
Scaled SARAH
Scaled SARAH
Loss
2.5
2.4
2.3
2.2
2:30
Billions tokens
Billions
Figure 20: ALBERT training.
33


Reviews:
[{"review_id": "IdPvdn4HlO", "reviewer": "Reviewer_8yK7", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper provides a generic pre-conditioning method for non-convex finite-sum minimization, which is an important task in machine learning. It combines this technique with two mainstream algorithms for finite-sum minimization, namely SARAH and L-SVRG. They provide both theoretical analysis for these algorithms, showing it achieves 1/eps^2 convergence rate under smoothness condition and log(1/eps) convergence rate under PL condition. They also corroborate the favorable performance of this pre-conditioning technique in practice by comparing it with Adam, another algorithm that incorporates second order information adaptively.", "summary_of_the_review": "I like the main idea of the paper a lot. And I think the experiment performance looks quite interesting too.\n\nI just feel theoretical analysis could probably be improved, or if not the main contributions and comparison with prior art shall be made clearer in the paper. Otherwise the theory part of the paper really doesn't feel like making much point in the current form.", "strength_and_weaknesses": "Strength:\n1) I think the paper is well-presented. The authors explain the motivation and idea pretty clearly, thus making it easy to follow. The author also did a thorough literature review.\n\n2) I think the problem they study is interesting and of important: i.e. study the effect of preconditioning, or incorporating little second-order information for finite-sum minimization-type methods. This is an important topic.\n\n3)The empirical performance show favorable improvement over other SOTA optimizer like Adam, which demonstrates potential impact of this preconditioning idea to other mainstream first-order optimizers in training neural networks.\n\nWeakness:\n1) The main confusion I have is I don't think the theoretical results in this paper corroborate the main argument of the paper, i.e. pre-conditioning technique is useful in practice. In particular, the theoretical analysis with preconditioning all just suffer from an additional L/alpha in their runtimes (compared with standard SARAH and SVRG), which is basically the condition number in worst case of the approximate diagonal matrix you construct, right? This is not a very interesting theoretical result in my mind. In particular, it doesn't explain why you choose such an estimator for diagonal rescaling at all. I believe for any arbitrary diagonal preconditioning bounded by condition number L/alpha, you can prove the same result. Please correct me if I am wrong.\n\n2) Following the above point, I feel the claim in the introduction about showing an eps^{-2} theoretical result, which improve over eps^{-4} is a bit misleading. Really you probably want to compare with un-preconditioned SARAH and other methods. The eps^{-4} result is for general case not finite sum minimization, and they also don't scale additionally with the number of function n, right? (please correct me if I am mistaken)\n\n2) In its current way written, it is hard to compare this paper's theoretical result with some prior art. In particular in these settings a natural metric is the gradient complexity so adding a remark for Theorem 3.1, 3.2 etc. on that would be helpful. Also, it seems Theorem 3.1 right now doesn't require an additive n in the final bound? Is that possible, or in other words would this violate some lower bound?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "GdouHgXNFtE", "reviewer": "Reviewer_ayos", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a preconditioned update to stochastic gradient methods， based upon Hutchinson’s approach to approximating the diagonal of the Hessian. ", "summary_of_the_review": "The paper proposes a preconditioned update to stochastic gradient methods, but the theoretical results still need to be strengthened. ", "strength_and_weaknesses": "Strength: introducing a new method to improve the convergence of the stochastic method \n\nWeaknesses: (1) The theoretical complexity is only for the smooth objective function. \n\n                       (2) The function under the PL condition is equivalent to the strongly convex function, but the linear convergence   from Nesterov's method is classical.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "ABg93W0PwQ", "reviewer": "Reviewer_QfWd", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper enhances two previous algorithms for non-convex finite sum minimization, SARAH and L-SVRG, by adding a diagonal preconditioner from Jahani et al. The authors prove that the preconditioned methods, which they call Scaled SARAH and Scaled L-SVRG, both converge. The convergence bounds are better than those of previous algorithms. \nThe authors then show the results of their methods on several LibSVM datasets.", "summary_of_the_review": "I would like to see the weaknesses in the paper corrected before it is ready for publication. As of now, it makes strong claims, but they are not backed up by enough discussion of their significance, or by experimental results.", "strength_and_weaknesses": "The paper combines two well known algorithms with a previous preconditioner. The key theoretical result (which I did not check in detail) is that the preconditioned algorithms have a better convergence bound than previous algorithms such as AdaGrad, Adam etc.\n\nPoints to improve:\n1. Please compare the convergence bounds of the Scaled algorithms with the unscaled versions. Also for Adagrad and Adam, please do point out the specific theorems in the papers where the epsilon^{-4} bounds are shown.\n2. Some discussion of the importance of these bounds should be included. While the given algorithms are theoretically much more efficient than AdaGrad/Adam, the difference is not visible in the experimental results.\n3. The experiments are on very small datasets. The big advantage of Adagrad and Adam is that they run on very large datasets, it would be definitely desirable to see the performance of Scaled SARAH and Scaled L-SVRG on some moderate sized datasets.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject