Doubly Adaptive Scaled Algorithm for Machine Learning Using Second-Order Information
Authors: Majid Jahani
Sergey Rusakov
Zheng Shi
Peter Richtárik
Michael W. Mahoney
Martin Takac
Venue: ICLR 2022 Poster (2022)
Keywords: Convex Optimization
Non-Convex Optimization
Stochastic Optimization
Second-Order Optimization
Deep Learning

Abstract: We present a novel adaptive optimization algorithm for large-scale machine learning problems. Equipped with a low-cost estimate of local curvature and Lipschitz smoothness, our method dynamically adapts the search direction and step-size. The search direction contains gradient information preconditioned by a well-scaled diagonal preconditioning matrix that captures the local curvature information. Our methodology does not require the tedious task of learning rate tuning, as the learning rate is updated automatically without adding an extra hyper-parameter. We provide convergence guarantees on a comprehensive collection of optimization problems, including convex, strongly convex, and nonconvex problems, in both deterministic and stochastic regimes. We also conduct an extensive empirical evaluation on standard machine learning problems, justifying our algorithm's versatility and demonstrating its strong performance compared to other start-of-the-art first-order and second-order methods.

Published as a conference paper at ICLR 2022
DOUBLY ADAPTIVE SCALED ALGORITHM FOR MACHINE LEARNING USING 2 2nd ORDER INFORMATION
Majid Jahani', Sergey Rusakov', Zheng Shi', Peter Richtárik?, Michael W. Mahoney?, Martin Takáč
'Lehigh University KKAUST University of California, Berkeley, USA MMohaeed bin Zayed University of Artificial Intelligence (MBZUAD)
majidjahani8 1ttpaainii9mmmmmmmmmmmmm com, ser3180lehigh. shi wfl.iihnnn...lll..e..e com, peter. cettr.richtariker k@kausk edu.. sa, nmahoney@stat. berke ley. edu, takac. Malaaaa com
ABSTRACT
We present a novel adaptive optimization algorithm for large-scale machine learning problems. Equipped with a low-cost estimate of local curvature and Lipschitz smoothness, our method dynamically adapts the search direction and step-size. The search direction contains gradient information preconditioned by a well-scaled diagonal preconditioning matrix that captures the local curvature information. Our methodology does not require the tedious task of learning rate tuning, as the learning rate is updated automatically without adding an extra hyperparameter. We provide convergence guarantees on a comprehensive collection of optimization problems, including convex, strongly convex, and nonconvex problems, in both deterministic and stochastic regimes. We also conduct an extensive empirical evaluation standard machine learning problems, justifying algorithm's 's versatility and demonstrating its strong performance compared to other start-of-the- art first-order and second-order methods.
INTRODUCTION
This paper presents an algorithm for solving empirical risk minimization problems of the form: min (w)) == f x",'''""))) fi)=
(I) where w is the model parameter/wwight vector, {(T,, y,) are the training samples, and fa IR + R is the loss function. Usually, the number of training samples, n, and dimension, d, are large, and the loss function F is potentially nonconvex, making difficult solve.
In the past decades, significant effort has been devoted to developing optimization algorithms for machine learning. Due to easy implementation and low per-iteration cost, (stochastic) first-order methods (Robbins & Monro 1951 Duchi et al., 2011; Schmidt et al. 2017: Johnson & Zhang 2013 Nguyen et al. 7 2019] & Bal 2014]]Jana become prevalent approaches for many machine learning applications. However, these methods have several drawbacks: (i) they are highly sensitive to the choices of hyperparameters, especially learning rate; (iz) they suffer from ill illcconiiiooning that often arises in large-scale machine learning; and (Mi) they offer limited opportunities in distributed computing environments since these methods usually spend more time "communication" instead of the true "computation." The main reasons for the aforementioned issues come from the fact that first-order methods only use the gradient information for their updates.
al. 202 la Recht al. 2011) have
the other hand, going beyond first-order methods, Newton-type and quasi-Newton methods (Nocedal & Wright 2006; Dennis & Moré, 1977] Fletcher 1987) are considered to be strong family of optimizers due to their judicious use of the curvature information in order to scale the gradient. By exploiting the curvature information of the objective function, these methods mitigate many of the issues inherent in first-order methods. known that these methods are relatively insensitive to the choices of the hyperparameters, and they handle ill-conditioned problems with fast convergence rate. Clearly, this does not come for free, and these methods can have memory requirements up to ( with computational
the deterministic regime, it is

---

Published as a conference paper at ICLR 2022
complexity up to ((d)) (e.g.. with a naive use of the Newton method). There are, of course.
efficient ways to solve the Newton system with significantly lower costs (e.g., see Nocedal &
Wright (2006). Moreover, quasi-Newton methods require lower memory and computational
complexities than Newton-type methods. Recently, there has been shifted attention towards
stochastic second-order
& Mahoney, 2018 [Byrd et al., [20TT] Martens 2010
Jahani et al., [2000a] Xu et al., 2017] Roosta et al., 2018 Yao et al. 2018) and quasi-New
methods (Curtis] 2016; Berahas
Beraaa et al.
2016; 2016 Mokhtari & Ribeiro 2015 Jahani et al. 2021b Bera-
has et al. 2019 Jahani et al. 20200b in order to approximately capture the local curvature information.
These methods have shown good results for sev-
Samplex
eral machine learning tasks (Xu et al. 2020;
Berahas et al. 2020: Yao et al., 2019). In some cases, however, due to the noise in the Hessian
Rolajive Erour
AdaHessian
Diagrtal Aypuus.
AdaHessian OASIS
OASIS Hutchinsson
line x y
approximation, their performance is still on par with the first-order variants. One avenue for re- ducing the computational and memory require- ments for capturing curvature information is to consider just the diagonal of the Hessian. Since the Hessian diagonal can be represented as vector, it is affordable to store its moving aver- age, which useful for reducing the impact of noise in the stochastic regime. To exemplify this,
230
30%
19%0
Figure 1: Comparison of the diagonal approxima- tion by AdaHessian and OASIS over random symmetric matrix A (100 x 100). left: Relative error (in Euclidean norm) between the true diag- onal of matrix A and the diagonal approximation by AdaHessian, Hutchinson's 's method, and OASIS (the æ-axis shows the number of random vectors sampled from the Rademacher distribution, see Section 2 Moreover, this plot can be considered as the representation of the error of the Hessian diag- onal approximation's 's evolution over the iterations of minimizing weT Au,, since A is fixed and sym- metric.); right: Diagonal approximation scale for AdaHessian and OASIS (y-axis), in comparison to the true diagonal of matrix A (z-axis).
AdaHessian Algorithm ( (Yao et al.. (2200) uses Hutchinson's 's method (Bekas et al.] 2007) to ap- proximate the Hessian diagonal, and it uses second moment of the Hessian diagonal approx- imation for preconditioning the gradient. Ada- Hessian achieves impressive results on a wide range of state-of- tatte-of-thh-ar ahe- tasks. However, its pre- conditioning matrix approximates the Hessian diagonal only very approximately, suggesting that improvements are possible if one can better approximate the Hessian diagonal.
In this paper, we propose the dOubly Adaptive Scaled algorlthm for machine learning using Second- order information (OASIS). OASIS approximates the Hessian diagonal in an efficient way, providing an estimate whose scale much more closely approximates the scale of the true Hessian diagonal (see Figure DT. Due to this improved scaling, the search direction in OASIS contains gradient information, in which the components are well-scaled by the novel preconditioning matrix. Therefore, every gradient component in each dimension is adaptively scaled based on the approximated curvature for that dimension. For this reason, there is need to tune the learning rate, it would be updated auto- matically based on a local approximation of the Lipschitz smoothness parameter (see Figure 2). The well-scaled preconditioning matrix coupled with the adaptive learning rate results in fully adaptive step for updating the parameters. Here, we provide brief summary of our main contributions:
Novel Optimization Algorithm. We propose OASIS as a fully adaptive method that preconditions the gradient information by well-scaled Hessian diagonal approximation. The gradient component in each dimension is adaptively scaled by the corresponding curvature approximation. Adaptive Learning Rate. Our methodology does not require to tune the learning rate, as it is updated automatically via an adaptive rule. The rule approximates the Lipschitz smoothness parameter, and it updates the learning rate accordingly.
Comprehensive Theoretical Analysis. We derive convergence guarantees for OASIS with respect to different settings of learning rates, namely the case with adaptive learning rate for convex and strongly convex cases. We also provide the convergence guarantees with respect to fixed learning rate and line search for both strongly convex and nonconvex settings.
Competitive Numerical Results. We investigate the empirical performance of OASIS on a variety of standard machine learning tasks, including logistic regression, nonlinear least squares prob- lems, and image classification. Our proposed method consistently shows competitive or superior performance in comparison to many first- and second-order state-of-the art methods.
Notation. By considering the positive definite matrix D, we define the weighted Euclidean norm of vector x E Rd with | = x Dr. Its corresponding dual norm is shown as || -l The operator
2

---

Published as a conference paper at ICLR 2022
Adollessian (i- 0.03125) AdoRessiia (k= 0.0625)
Adallessian 0.15)
Adallessian (1r00.5)
Adaliession (Ir-2)
OASIS
Adaltsssian 0.25)
AdaHessian (Ir=1)
AdaHessiia (lem4)
Jogesi regresania 10x cxd
Lrgatin represse A- ced teretons
1020
10-
10-
AdaHessian
4.10
OASIS
furaiin
30
logid))
lteration
logstir)
Figure 2: Adaptive Learning Rate (Logistic Regression on with strong-convexity parameter _ over revl dataset). left and middle: Comparison of optimality gap for AdaHessian Algorithm with multiple learning-rate choices vs. OASIS Algorithm with adaptive learning rate (dashed-blue line); right: Comparison of the best optimality gap and test accuracy for AdaHessian Algorithm w.r.t each learning rate shown on x-axis after 40 iterations vs. the optimality gap and test accuracy for our OASIS Algorithm with adaptive learning rate after 40 iteration (dashed-blue line).
@ is used as component-wis product between two vectors. Given vector we represent the corresponding diagonal matrix of u with diag()).
2 RELATED WORK
In this paper, we analyze algorithms with the generic iterate updates:
Wk++1 = Wg 7}A Dr -'me,
(2)
where Dy is the preconditioning matrix, my is either 9s (the true gradient or the gradient approxi- mation) or the first moment of the gradient with momentum parameter 31 or the bias corrected first moment of the gradient, and 1/& is the learning rate. The simple interpretation is that, in order to update the iterates, the vector my would be rotated and scaled by the inverse of preconditioning matrix Dr. and the transformed information would be considered as the search direction. Due to limited space, here we consider only some of the related studies with a diagonal preconditioner. For more general preconditioning, see (Ncedal & Wright (2006). Clearly, one of the benefits of well-defined diagonal preconditioner is the easy calculation of its inverse.
There are many optimization algorithms that follow the update in (2) A well-known method is stochastic gradient descent (SGD).The The idea behind SGD simple yet effective: the preconditioning matrix is set to be Dr Ias for all A: 2 O. There are variants of SGD with and without momentum. The advantage of using momentum is to smooth the gradient (approximation) over the past iterations, and it can be useful in the noisy settings. In order to converge to the stationary point(s), the learning rate in SGD needs decay. Therefore, there many important hyperparameters that need to be tuned, e.g., learning rate, learning-rate decay, batch size, and momentum. Among all of them, tuning the learning rate is particularly important and cumbersome since the learning rate in SGD is considered to be the same for all dimensions. To address this issue, one idea is to use an adaptive diagonal preconditioning matrix, where its elements are based on the local information of the iterates.
One of the initial methods with non-identity preconditioning matrix Adagrad (Duchi et al. 2011] McMahan & Streeter 2010). In Adagrad, the momentum parameter is set to be zero (m 9k), and the preconditioning matrix is defined as:
D diag( E/e... @ 9x).
(3)
In the preconditioning matrix D in 3). every gradient component is scaled with the accumulated information of all the past squared gradients. It advantageous the sense that every component scaled adaptively. However, a significant drawhack of D₃ in (3) has to do with the progressive increase of its elements, which leads to rapid decrease of the learning rate. To prevent Adagrad's aggressive, monotonically decreasing learning rate, several approaches. including Adadelta Zeileer 2012) and RMSPPrp (Tieleman & Hinton 2012). have been developed. Specifically, in RMSProp. the momentum parameter B1 is zero (or m = gk) and the preconditioning matrix is as follows:
D V B2D 2 + (1 32)diag(s O (x),
where 32 is the momentum parameter used in the preconditioning matrix. As we see from the difference between the preconditioning matrices in (3) and 4 in RMSProp an exponentially decaying average of squared gradients is used, which prevents rapid increase of preconditioning
3

---

Published as a conference paper at ICLR 2022
components in (3)
Another approach for computing the adaptive scaling for each parameter is Adam (Kingma & Ba
2014). Besides storing an exponentially decaying average of past squared gradients like Adadelta and RMSprop, Adam also keeps first moment estimate of gradient, similar SGD with momentum. In Adam, the bias-corrected first and second moment estimates, i.e., m. and Dj in (2), are follows:
ma
1-81 1-07
1 Di,
Dr - V
1-
92 ビー 1 ' diiag(g @ g.).)
(5)
There have been many other first-order methods with adaptive scaling (Loshchilov & Hutter 2017
Chaudhari et al. 2019 Loshchilov & Hutter 2016 (Shazerr & Stern 2018).
The methods described so far have only used the information of the gradient for preconditioning my in (2). The main difference of second-order methods is to employ higher order information for scaling and rotating the my in (2). To be precise, besides the gradient information, the (approximated) curvature information of the objective function is also used. As textbook example, in Newton's method Dj ((wx) and m. Is with 7)x: =
Diagonal Approx. Recently, using methods from randomized numerical línear algebra, the AdaHes- sian method was developed (Ya et al. (020). AdaHessian approximates the diagonal of the Hessian, and it uses the second moment of the diagonal Hessian approximation as the preconditioner Dr in (2) In AdaHessian, Hutchinson's 's method is used to approximate the Hessian diagonal as follows:
D2 ~ diag @ F²²((w))z)))
where 2/: is random vector with Rademacher distribution. Needless to say the oracle V F(wx))=s or Hessian- vector product, can be efficiently calculated; in particular, for AdaHessian, it is computed with two back proppaaapatton rounds without constructing the Hessian explicitly. In nutshell, the first momentum for AdaHessian is the same as (5), and its second order momentum is:
Da
2 DD?
The intuition behind AdaHessian is to have larger step size for the dimensions with shallow loss surfaces and smaller step size for the dimensions with sharp loss surfaces. The results provided by AdaHessin show its strength by using curvature information, in comparison to other adaptive first-order methods, for a range of state-of-the-art problems in computer vision, natural language processing, and recommendation systems (Yao et al., 2020). However, even for AdaHessian, the preconditioning matrix Dr in ( does not approximate the scale of the actual diagonal of the Hessian particularly well (see Figure Ip. One might hope that better-scaled preconditioner would enable better use of curvature information. This is one of the main focuses of this study.
daptive Learning Rate. In all of the methods discussed previously, the learning rate 7/ in ( is still a hyperparameter which needs to be manually tuned, and is a critical and sensitive hy- perparameter. It is also necessary to tune the learning rate in methods that use approximation of curvature information (such as quasi-Newton methods like BFGS/LBFGS, and methods using di- agonal Hessian approximation like AdaHessian). The studies (Loizou et al. 2020 Vaswani et al., 2019; Chandra et al.) 2019 Baydin et al.) 2017 Malitsky & Mishchenko 2020) have tackled the issue regarding tuning learning rate, and have developed methodologies with adaptive learning rate, Mh. for first-order methods. Specifically, the work (Malitsky & Mishchenko, 2020) finds the learning rate by approximating the Lipschitz smoothness parameter in an affordable way without adding a tunable hyperparameter which is used for GD-typ GD-type methods (with identity norm). Extending the latter approach to the Hnighted-Euclideen
norm is not straightforward. In the next section, we describe how we can extend the work (Malitsky& & Mishchenko 2020) for the case with weighted Fuclidean norm. This is another main focus of this study. In fact, while we focus on AdaHessian, any method with a positive-definite preconditioning matrix and bounded eigenvalues can benefit from our approach.
3 OASIS
In this section, we present our proposed methodology. First, we focus on the deterministic regime, and then we describe the stochastic variant of our method.
1 For a general symmetric matrix A, R[2 @ A2] equals the diagonal of A Bekas et al. 2007]. AAtually, it needs to be said: many within the machine leamning community still maintain the incorrect belief that extracting second order information "requires inverting a matrix." " It does not.
4

---

Published as a conference paper at ICLR 2022
3.1 DETERMINISTIC OASIS
Similar to the methods described in the previous section, our OASIS Algorithm generates iterates according to
Motivated by AdaHessian, and by the fact that the loss surface curvature is different across different dimensions, we use the cur- vature information for preconditioning the gradient. We now describe how the pre- conditioning matrix D2 can be adaptively updated at each iteration as well as how update the learning rate 7i automatically for performing the step. To capture the cur- vature information, we also use Hutchin- son's method and update the diagonal ap- proximation as follows:
Algorithm OASTS
Input:wo. 1/0. Do. On +00
1: W1 = -w 170 Do - FVWw)
2: for k= 1,2,, do
3: Form D2 via 8 and Dr. via 9
4: Update Th based on 10)
5: Set Wk+11 wk Dr VVF(F (wx)
Set 02 M/-1
7: end for
(8) Before we proceed, we make a few more comments about the Hessian diagonal Dx in (8. As is clear from (8), decaying exponential average of Hessian diagonal is used, which can be very useful in the noisy settings for smoothing out the Hessian noise over iterations. Moreover, it approximates the scale of the Hessian diagonal with satisfactory precision, unlike AdaHessian Algorithm (see Figure [ More importantly, the modification is simple yet very effective. Similar simple and efficient modification happens in the evolution of adaptive first-order methods (see Section 2 Further, motivated by (Paternain et al. 2019 Jahani et al.) 20215), in order to find a well-defined preconditioning matrix Dr, we truncate the elements of D3 by a positive truncation value a. To be more precise:
D3 = D2 - 82) diag(v)), where U2 == O F2F(w)))
(i+),, max a), Vi [d].
The goal of the truncation described above is have well-defined preconditioning matrix that results a descent search direction; note the parameter a is equivalent to in Adam and AdaHessian). Next, discuss the adaptive strategy for updating the learning rate 7і in (2). By extending the
adaptive rule in (Malitsky & Mishchenko) 22000) and by defining 0₂ == n Vk 2 1, our learning
rate needs to satisfy the inequalities: i) v < (1 + 02-1)mE-1 and ii) Mn S 2 V(
w. -w--1lp
(These inequalities come from the theoretical results.) Thus, the learning rate be adaptively calculated as follows:
7e min /1 0,-17 |/ wo-ill, (()))(((x) - VF(W)-1))1), )}-
(10)
As is clear from (TO), is only required store the previous iterate with its corresponding gradient and the previous learning rate (a scalar) in order to update the learning rate. Moreover, the learning rate in (1)) is controlled by the gradient and curvature information. As we will see later in the theoretical results, ? 2 2T. where L. is the Lipschitz smoothness parameter of the loss function. It is noteworthy to highlight that due to usage of EuclideddE norms the required analysis for the cases with adaptive learning rate is non-trivial (see Section[4). Also, by setting 3n = 1, 1, and Do = Ia. our OASIS algorithm covers the algorithm (Malitsky & Mishchenko 2020).
3.2 STOCHASTIC OASIS
In every iteration of OASIS, presented in the previous section, it is required to evaluate the gradient and Hessian-vector product on the whole training dataset. However, these computations are prohibitive in the large-scale setting, i.e., when n and d are large. To address this issue, present stochastic variant of CASIS (see Appendix [ for details) that only considers a small mini-batch of training data in each iteration.
The Stochastic OAS chooses sets It. Js C. [nt] randomly and independently, and the new iterate Fr,
computed as: Wk+1 Wk T/ Dr 1 V (ww), where VT (wx) - EieT, V.((w)))
and De is the truncated variant of D₁ 32 D2Dr-1 + (1 32) diag(Ex + V² (wx)=x) with 2 Fs. (wx) [Jol Ejen. (wF)
5

---

Published as a conference paper at ICLR 2022
3.3 WARMSTARTING AND COMPLEXITY OF OASIS
Both deterministic and stochastic variants of our methodology share the need to obtain initial estimate of Do. The importance of this is illustrated by the rule (10). which regulates the choice of yk, which is highly dependent DA. In order have better approximation of Do. we propose to sample some predefined number of Hutchinson's 's estimates before the training process.
The main overhead of our methodology is the Hessian-vectoe product used in Hutchinson's 's method for approximating the Hessian diagonal. With the current advanced hardware and packages, this computation is not bottleneck anymore. To be more specific, the Hessian-vectes product can be efficiently calculated by two rounds of back-propagation. We also present how to calculate the Hessian vector product efficiently for various well-known machine learning tasks in Appendix B
4 THEORETICAL ANALYSIS
In this section, we present theoretical results for OASIS. We show convergence guarantees for different settings of learning rates, i.e., (i) adaptive learning rate, (ii) fixed learning rate, and (vii with line search. Before the main theorems are presented, we state the following assumptions and
lemmas that are used throughout this section. For brevity, we present the theoretical results using line search in Appendix [A] Assumption 4.1. (Convex). The function F is convex.
The proofs and other auxiliary lemmas are in Appendix A
Assumption 4.2. (L- smooth).. The gradients of F are L--Lisshhtzz continuous for all w E Rd, ie.. 3L > 0 such that Yu, w' E IRd, (Rd,F((u F(w) S F(w') (VF(('), w w²) + 2 [|w w'l??
Assumption 4.3. The function Assumption 4.4. (J-ssroogly convex). The function F is μ j-Strrogly convex, iee, there exists constant μ > such that Vw, w/ E ERd, F(w) 2 F(w')= + (VF(("), w²) + f
twice continuously differentiable.
w 1|2
Here is a lemma regarding the bounds for Hutchinson's is approximation and the diagonal differences. Lemma 4.5. (Bound on change of Dz). Suppose that Assumption 4.2 holds, then i) ((x))al s r S VdL. where U2 = 2k @ (ww)()) :x ii) 38 s 2( -32)rr such that wk || - Dxlloo I d.
4.1 ADAPTIVE LEARNING RATE
Here, we present theoretical convergence results for the case with adaptive learning rate using (00).
Theorem 4.6. Suppose that Assumptions 4.1 4.2 and 4.3 hold. Let {wk} be the iterates gen- erated by Algorithm OASIS, then we have: F((rk) - F S LC + 2L(1 - B2) Qu where C= 21| -ilwi-w"" w 1B, + +l|e-- -wull (F
k
and Qx = Ek=
(2m00+a 1 will 2a
13 Iw. w² 12).
Remark 4.7. The following remarks are made regarding Theorem 4.6
1. If Bg 1,
and Do Ia. the results in Theorem 4.6 completely match with Malitsky &
Mishchenko 2020
2. By considering an extra assumption as in (Reddi el al. 2019 Duchi al. 2011 regarding -w-- bounded iterates, ie., ||w - w/ B Vk 2 0, one can easily show the convergence of OASTS to the neighborhood of optimal solution(s).
The following lemma provides the bounds for the adaptive learning rate for smooth and strongly- convex loss functions. The next theorem provides the linear convergence rate for the latter setting.
Lemma 4.8. Suppose that Assumptions
4.2
4.3
and hold, then m7 E 222 2.l-
Theorem 4.9. Suppose that Assumptions
4.2
4.3
4.4 hold, and let w" be the unique solution
for 7. Let } be the iterates generated by Algorithm 7 Then, for all k 2 0 and B2 Z a²²
max 41.-12 (a (a +L125 4LI p= } we have: gp S (1 252,3 ) where wh++1
a²
a²
| wt
12
| Wx|| 2
+ 2 Oc)(F(())) F(w*)).
De
D
4.2 FIXED LEARNING RATE
Here, we provide theoretical results for fixed learning rate for deterministic and stochastic regimes.
Remark 4.10. For any l 2 O, we have al 3 D2 2 TT where < a T.

---

Published as a conference paper at ICLR 2022
4.2.1 DETERMINISTIC REGIME
Strongly Convex. The following theorem provides the linear convergence for the smooth and strongly-convex loss functions with fixed learning rate.
Theorem 4.11. Suppose that Assumptions 4.2 4.3 and 4.4 hold, and let F F(w"), where w" is a²
the unique minimizer. Let }wx} be the iterates generated by Algorithm / where < ?h = 1) S LT
and wp is a starting point. Then, for all k 2 0 we have: F(wx)) - F ( - F*)
Nonconvex. The following theorem provides the convergence to the stationary points for the nonconvex setting with fixed learning rate.
Assumption 4.12. The function F.) is bounded below by scalar F. Theorem 4.13. Suppose that Assumptions 4.2 4.3 and 4.12 hold. Let {wx} be the iterates generated by Algorithm, where 0 < 7) = - and wo is a starting point. Then, for all T > we have:
T (VVF(())))))) s 2r(F(w)) T- 0. E
(11)
4.2.2 STOCHASTIC REGIME
Here, we Ez, [-] to denote conditional expectation given wk, and B[] to denote the full expectation over the full history. The following standard assumptions as in (Bollapragada et al. 2019 Berahas
al. 2016) are considered for this section.
Assumption 4.14. There exist a constant such that Ey [l V ( (w) [) م²
Assumption 4.15. There exist a constant o² < 3o such that Ez E || S 0².
Assumption 4.16. (r() is an unbiased estimator of the gradient, i.e., Ez V [w])] VF(w).
Strongly Convex. The following theorem presents the convergence to the neighborhood of the optimal solution for the smooth and strongly-oovvex case in the stochastic setting.
Theorem 4.17. Suppose that Assumptions 4.2
4.3 4.4
4.15 and holdd Let {wk} be the iterates
generated by Algorithm
with Qn- = E (0, rT then, for all k 2 0,
EE F((()) - F*) (1 c)* (F(wo) F*) + L oa*
(12)
where
2np
2r
E 10. Moreover, if T = E (0, B[F(wx) - F*] S (1 (F(wo) - F*) + LL'Lo? a²
a² 2T then
a
(13)
Nonconvex. The next theorem provides the convergence to the stationary point for the nonconvex loss functions in the stochastic regime.
Theorem 4.18. Suppose that Assumptions 4.2
4.3
4.12
4.14 and 4. holdd Let {wx} be the iterates
generated by Algorithm 1 where ?h = 7) S Yr and We is the starting point. Then, for all 2 21 nf + "T T-400 nT=211
E
<
The previous two theorems provide the convergence to the neighborhood of the stationary points. One can easily use either variance reduced gradient approximation or a decaying learning rate strategy to show the convergence the stationary points (in expectation). OASIS's analyses are similar those of mmitedd-mmorry quasi-Newton approaches which depends on Xmaz and Xmin (largest and smallest eigenvalues) of the preconditioning matrix (while in (S)GD Aman= Aman 1). These methods in theory not better than GD-type methods. In practice, however, they have shown their strength.
5 EMPIRICAL RESULTS
In this section, we present empirical results for several machine learning problems to show that our OASIS methodology outperforms state-of-the-ar first- and second-order methods in both determin- istic and stochastic regimes. We considered: (1) deterministic fz-regularized logistic regression (strongly convex); (2) deterministic nonlinear least squares (nonconvex), and we report results on 2 standard machine learning datasets rev1 and i ijenn? and (3) image classification tasks
https//wwww.csccnn..c.uuuu wwwp://wwwiiiiissoooosossaaaeee
7

---

Published as a conference paper at ICLR 2022
0.5
20
0.0
12-4
0.0
20-1
0.0
0.4
440
25'
0.4
A23h
0465
10"
120
353
320
402
300
200
300
400
102
200
330
402
150
230
200
402
Nunborr ENoociie Poosess
NNttberrff Rot.oooroe Passes
Nunbor Bilcciiv Pooses
Mumber bilective
roVE
10"
0.3
10.
0.9
20'
10
3.5
Find
10"
0.4
10-11
0:030
0.5
300
Rumber of Sifecttive Plarrss
Nambbrr effoccive Raaces
Number of Affecctive Pooses
Marbber Elfective
Figure 3: Comparison of optimality gap and Test Accuracy for different algorithms Logistic Re- gression Problems.
Figure 4: Comparison of objective function (F(w)) and Test Accuracy for different algo- rithms on Non-linear Least Square Problems.
MNIST, CIFARIO, and CIFAR100 datasets on standard network structures.In the interest of space, we report only a subset of the results in this section. The rest can be found in Appendix C To be clear, we compared the empirical performance of OASIS with algorithms with diagonal pre- conditioners. In the deterministic regime, we compared the performance of OAS IS with AdGD) (Malitsky& & Mishchenko (020)) and AdaHessian (Yao et al.| 2020). Further, for the stochastic regime, we provide experiments comparing SGD (Robbins & Monro 1951), Adam (Kingma & Ba 2014), AdamW (Loshchilov & Hutter 2017), and AdaHessian. For the logistic regression problems, the regularization parameter was chosen from the set X E { 10g 1 10 j. It is worth highlighting that wC ran each method for each of the following experiments from f' different random initial points. Moreover, we separately tuned the hyperparameters for each algorithm, if needed. See Appendix C for details. The proposed OASTS is robust with respect to different choices of hyperparameters, and it has narrow spectrum of changes (see Appendix C).
Logistic Regression. We considered fz-regularized logistic regression problems, F(w) =
E log(1 + e-waa" w) + 2 |||==]]2. Figure shows the performance of the methods in terms of optimality gap and test accuracy versus number of effective passes (number of gradient and Hessian-vector evaluations), As is clear, the performance of OASIS (with adaptive learning rate and without any hyperparameter tuning) is on par or better than that of the other methods.
Non-linear Least Square. We considered non-linear least squares problems (described in Xu et al. (2020)) F(w)= , E. (y:- 1/(1+ e =! "))². Figure shows that our OASIS Algorithm always outperforms the other methods in terms of training loss Function and test accuracy. Moreover, the behaviour of CAS is robust with respect to the different initial points.
Image Classification. We illustrate the performance of OASIS on standard bench bench-marking neural network training tasks: MNIST SIFAR10 O, and CIFAR1 00. The results for MNI ST and the details of the problems are given in Appendix C We present the results regarding CIFAR10 0 CIARRIIFROO 00. CIFAR1O. We use standard ResNet - 20 and ResNet - 32 (He et al. 2015) architectures for com- paring the performance of CASIS with SGD, Adam, Adam W and AdaHessian Specifically, report 3 variants of OASIS: 5: (i) adaptive learning rate, (ii) fixed learning rate (without first moment) and (fii) fixed learning rate with gradient momentum tagged with "Adaptive LR,"" "Fixed LR," and "Momentum," respectively. For settings with fixed learning rate, no warmstarting is used in order to obtain an initial Do approximation. For the case with adaptive learning case, we used the warmstart- ing strategy to approximate the initial Hessian diagonal. More details regarding the exact parameter values and hyperparameter search can be found in the Appendix C The results on CIFAR10 are shown in the Figure (the left and middle columns) and Table [ As is clear, the simplest variant of OASIS with fixed learning rate achieves significantly better results, as compared to Adam, and a per- formance comparable to SGD, For the variant with an added momentum, we get similar accuracy as AdaHessian, while getting better or the same loss values, highlighting the advantage of using different preconditioning schema. Another important observation is that OASIS- OASIS-Adaptive LR, without too much tuning efforts, has better performance than Adam with sensitive hyperparameters. All in all, the performance of OASIS S variants is on par better than the other ofthe-o--hheart art methods especially
Note that we follow the same Experiment Setup as in (Yao et al. 2020), and the codes for other algorithms and structures are brought from
8

---

Published as a conference paper at ICLR 2022
Pashott0 CEFARLO with Weight Decay
Nos OFARRD With Weigh
8D-
ResPartl on CIFAELOO WES Weight Ducay
70
30
oudd Fi
500
Auarch
10
Pareran
20
40
50
100
120
140
160
20
150
120
140
160
25
50
200 75
100 Spacts
125
150
375
Epects
Spacha
106
Ieem
0ASS L
10
Jesv
10"
110
10-3
10-2
10aa
20
40
1.00
120 140
160
20
40
60
100
120
140
160
50
75
100
125
150
175 200
Figure 5: Performance of SGD, Adam, AdamW, Adehessian and different variants of OASIS on CIFAR10 (left and middle columns) and CIFARI 00 (right column) problems ResNet-20 (left column), ResNet-32 32 (middle column) and ResNet-18 (right column).
SGD. As we see from Figure Figu and middle columns), the lack of momentum produces a slow, noisy training curve in the initial stages of training, while OASIS with momentum works better than the other two variants in the early stages, All three variants of OASIS get satisfactory results in the end of training. More results and discussion regarding CIFARI0 0 dataset are in Appendix C
Table 1: Results of ResNet-200
on CIFAR10 Table 2: Results of ResNet- - -88 on
Setting
ResNet-32 ResNet-20
CIEAR100.
Setting
ResNet-13
SGD
92.02 = 0.22
92.85
0.12
Adam
90,46 + 0.22
91.30 +: 0.15
SGD
76.57 + 0.24
AdamW
91.99 0.17
92.55"1"..255"
Adam
73.40 + 0.31
AdaHessian
92.03 - 0.10
"0.76""00266"
AdamW
72.31 = 0.76
AdaHessian
75.71 + 0.47
OASIS- Adaptive LR
91.20 + 0.20
92.61
0.22
OASIS- Fixed LR
91.96 = 0.21
93.01 0.09
OASIS- Adaptive LR
76.93 + 0.22
OASIS- Momentum
92.01 = 0.19
92.77 + 0.18
OASIS- Fixed LR
76.28 + 0.21
OASIS- Momentum
76.89 + 0.34
CIFAR-100. We use the hyperparameter settings obtained by training on CIFARIC on ResNet- 2 32 to train CIFAR1 00 on ResNet-18 network structure We similarly compare the performance of our method and its variants with SGD, Adam, Adam W and AdaHessian. The results are shown in Figure (right column) and Table In this setting, without any hyperparam- eter tuning, fully adaptive version of our algorithm immediately produces results surpassing other state-of-the-arr methods especially SGD.
6
FINAL REMARKS
This paper presents a fully adaptive optimization algorithm for empirical risk minimization. The search direction uses the gradient information, well-scaled with novel Hessian diagonal approx- imation, which itself can be calculated and stored efficiently. In addition, we do not need to tune the learning rate, which instead is automatically updated based on low-cost approximation of the Lipschitz smoothness parameter. We provide comprehensive theoretical results covering standard optimization settings, including convex, strongly convex and nonconvex; and our empirical results highlight the efficiency of OASIS in large-scale machine learning problems.
Future research avenues include: (1) deriving the theoretical results for stochastic regime with adaptive learning rate; (2) employing variance reduction schemes in order to reduce further the noise in the gradient and Hessian diagonal estimates; and (3) providing a more extensive empirical investigation other demanding machine learning problems such those from natural language processing and recommendation system (such as those from the original AdaHessian paper (Yao) et al. 2.20
9

---

Published as a conference paper at ICLR 2022
Acknowledgements
MT was partially supported by the NSF, under award numbers CCF:1618717/CCF: was supported by the KAUST Baseline Research Funding Scheme. MM would like acknowledge the US NSF and ONR via its BRC on RandNLA for providing partial support this work. Our conclusions do not necessarily reflect the position or the policy of our sponsors, and no official endorsement should be inferred.
PR
ETHICS STATEMENT
This work presents a new algorithm for training machine learning models. We do not foresee any ethical concerns. All datasets used in this work are from the public domain and are commonly used benchmarks in ML papers.
REPRODUCIBILITY STATEMENT
We uploaded all the codes used 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 the public domain, and one can download them from the following website https: //www. csie, ntu edu. tw/ weliin/ibbswat ools/ dat asetss After acceptance, we will include link to the GitHub repository where will host the source codes.
REFERENCES
Atilim Gunes Baydin, Robert Cornish, David Martinez Rubio, Mark Schmidt, and Frank Wood. Online learning rate adaptation with hypergradient descent. arXiv preprint 1703:077... 2017.
C. Bekas, E. Kokiopoulou, and Y. Saad. An estimator for the diagonal of matrix. Applied Numerical Mathematics, (1(1)):1114-229, 2007. ISSN 0168-9274. doi: https://doi.or//II 10.//0..1//1// 1016/ japnum.2007.0m .0003. URL https: www.. sciencedi rect ctmeecccomseee stt//sciinccccc artticii iriie// TTL/5016892740075
Numerical Algorithms, Parallelism and Applications (2).
Albert S Berahas, Jorge Nocedal, and Martin Takáč. A multi-batch 1-bfgs method for machine learning. Advances in Neural Information Processing Systems, pp. 1055-1063, 2016.
Albert S Berahas, Majid Jahani, Peter Richtárik, and Martin Takáč. Quasi-newton methods for deep learning: Forget the past, just sample. arXiv preprint arXiv: (tt1:::99000997,,, 2019.
Albert S. Berahas, Raghu Bollapragada, and Jorge Nocedal. An investigation of Newton-Sketch and subsampled Newton methods. Optimization Methods and Software, 35(4):661-680, 2020.
Raghu Bollapragada, Richard Byrd, and Jorge Nocedal. Exact and inexact subsampled newton methods for optimization. IMA Journal of Numerical Analysis, 39(2):545-577 578, 2019.
Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-311 2018.
Richard Byrd, Gillian M Chin, Will Neveitt, and Jorge Nocedal. On the use of stochastic hessian information in optimization methods for machine learning. SIAM Journal on Optimization, 21)3): 977-995, 2.
Kartik Chandra, Erik Meijer, Samantha Andow, Emilio Arroyo-Fang, Irene Dea, Johann George, Melissa Grueter, Basil Hosmer, Steffi Stumpos, Alanna Tempest, et al. Gradient descent: The ultimate optimizer. arXiv preprint 1rXiv:1909.1337.1 2019.
Pratik Chaudhari, Anna Choromanska, Stefano Soatto, Yann LeCun, Carlo Baldassi, Christian Borgs, Jennifer Chayes, Levent Sagun, and Riccardo Zecchina. Entropy-sgd: Biasing gradient descent into wide valleys. Journal of Statistical Mechanics: Theory and Experiment, 2019(12):124013 2019.
10

---

Published as a conference paper at ICLR 2022
Frank E. Curtis. A self-correcting variable-metric algorithm for stochastic optimization. In Interna- tional Conference on Machine Learning, pp. 352-641,25 2016.
John E Dennis, Jr and Jorge J Moré. Quasi-newton methods, motivation and theory. SIAM review, 19 (1):46-89) 1977.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
Roger Fletcher. Practical Methods of Optimization. John Wiley & Sons, New York, 2 edition, 1987.
Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. Sgd: General analysis and improved rates. International Conference on Machine Learning, pp. 5200-5209. PMLR, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. CoRR, abs/1512.03333 2015. URL http:::/axxi..rrg/g//p// abs wttp:///aa//111..... 03385
Majid Jahani, Xi He, Chenxin Ma, Aryan Mokhtari, Dheevatsa Mudigere, Alejandro Ribeiro, and Martin Takáč. Efficient distributed hessian free algorithm for large-scale empirical risk minimiza- tion via accumulating sample strategy. International Conference on Artificial Intelligence and PMLR, 2020a.
Statistics, pp.
Majid Jahani, Mohammadreza Nazari, Sergey Rusakov, Albert S Berahas, and Martin Takáč. Scaling up quasi-newton algorithms: Communication efficient distributed sr1. International Conference on Machine Learning, Optimization, and Data Science, pp. 41-54. Springer, 2020b.
Majid Jahani, Naga Venkata C Gudapati, Chenxin Ma, Rachael Tappenden, and Martin Takáč. Fast and safe: accelerated gradient methods with optimality certificates and underestimate sequences. Computational Optimization and Applications, 79(2):369-44 400994444422000 2021a.
Majid Jahani, Mohammadreza Nazari, Rachael Tappenden, Albert Berahas, and Martin Takáč. Sonia: A symmetric blockwise truncated optimization algorithm. In International Conference on Artificial Intelligence and Statistics, pp. 487-495. PMLR, 2021b.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in neural information processing systems, pp. 315-323, 2013.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.69880 2014.
Nicolas Loizou, Sharan Vaswani, Issam Laradji, and Simon Lacoste-Julien. Stochastic polyak step- size for sgd: An adaptive learning rate for fast convergence. arXiv preprint 205.:22002..044.. 2020.
llya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. arXiv preprint arXiv:1608.033 03983, 2016.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint
101 2017.
Yura Malitsky and Konstantin Mishchenko. Adaptive gradient descent without descent. In Interna- tional Conference on Machine Learning, pp. 6702-6712. PMLR, 2020.
James Martens. Deep learning via hessian-free optimization. In ICML, volume 27, pp. 735-742, 2010.
Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex opti- mization. Proceedings of the 23rd Annual Conference Learning Theory (COLT), 2010.
Aryan Mokhtari and Alejandro Ribeiro. Global convergence of online limited memory bigs. The Journal of Machine Learning Research, 16(1):315131111, 2015.
Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013.
11

---

Published as a conference paper at ICLR 2022
Yurii Nesterov et al. Lectures convex optimization, volume 137. Springer, 2018.
L. M. Nguyen, Liu, Scheinberg, and M. Takáč. SARAH: novel method for machine learning problems using stochastic recursive gradient. In Advances in neural information processing systems, volume 70, pp. 2613-2621, 2017.
Lam Nguyen, Phuong Ha Nguyen, Marten Dijk, Peter Richtárik, Katya Scheinberg, and Martin Takáč. Sgd and hogwild! convergence without the bounded gradients assumption. International Conference on Machine Learning, pp. 3750-3758 PMLR, 2018.
Lam M Nguyen, Phuong Ha Nguyen, Peter Richtárik, Katya Scheinberg, Martin Takáč, and Marten van Dijk. New convergence aspects of stochastic gradient algorithms. J. Mach. Learn, Res., 20: 206-9,2019,
Jorge Nocedal and Stephen J. Wright. Numerical Optimization. Springer Series Operations Research. Springer, second edition, 2006.
Santiago Paternain, Aryan Mokhtari, and Alejandro Ribeiro. newton-based method for nonconvex optimization with fast evasion of saddle points. SIAM Journal Optimization, 2941):343-368, 2019.
Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild: A lock-free approach to parallelizing stochastic gradient descent. In Advances in neural information processing systems, pp. 693-701, 2011.
Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. arXiv preprint arXiv:1904.092.: 092377, 2019.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pp. 400-407, 1951.
F. Roosta, Y. Liu, P. Xu, and M. W. Mahoney. Newton-MR: Newton's method without smoothness convexity. Technical Report Preprint: #rXiv:1810.00303 2018.
Farbod
and Michael W. Mahoney. Sub-sampled newton methods. Mathematical
Programming, 2018.
Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162(1-2):83-11,, 2017.
Noam Shazeer and Mitchell Stern. Adafactor: Adaptive learning rates with sublinear memory cost. In International Conference on Machine Learning, pp. 4596-4604, PMLR, 2018.
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-mmsprop: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26-31, 2012.
Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of sgd for over- parameterized models and an accelerated perceptron. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1195-1204 PMLR, 2019.
Xu, F. Khort-KKoo,s,ni,, and W. Mahoney. Newton-type methods for non-convex optimization under inexact Hessian information. Technical Report Preprint: utXiv:1708.077. 164, 2017.
Peng Xu, Fred Roosta, and Michael W Mahoney. Second-orde optimization for non-convex machine learning: An empirical study. In Proceedings of the 2020 SIAM International Conference Data Mining, pp. 199-207. SIAM, 2020.
Z. Yao. P. Xu. F. Roosta-Koin Khorasani,,,, and M. W. Mahoney. Inexact non-convex Newton-type methods. Technical Report Preprint: arXiv: 1.X.v:18020000 006822222....... 2018.
Z. Yao, A. Gholami, K. Keutzer, and M. W. Mahoney. PyHessian: Neural networks through the lens of the Hessian. Technical Report Preprint: 151 2019.
12

---

Published as a conference paper at ICLR 2022
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.007/14 2020.
Matthew D Zeiler. Adadelta: an adaptive learning rate method. arXiv preprint arXiv: 2012.
13

---

Published as a conference paper at ICLR 2022
A
THEORETICAL RESULTS AND PROOFS
A.1
ASSUMPTIONS
Assumption 4.1
(Convex). The function F is convex, i.e., Vw, w/ E Rd,
F(w) 2 F(w') + (VF(())) - ww))
(14)
(L-smooth). The gradients of F are L Lipschhitt continuous for all w E Rd i.e. there exists constant L > 0 such that Vw, w' E'E R
Assumption 4.2
F(w)= S F(w') + (VF(w'), w w') + w' wl12.
L
(15)
Assumption
4.3
The function F is twice continuously differentiable.
Assumption
(n (u-sstongly convex). The function F is jt-strongyy convex, ie, there exists
constant μ
such that Vw, w/ E &R.,
F(w)= 2 F(w') + (VF(w), w')
1 - w'1?
(16)
Assumption
4.12
The function F.) bounded below by scalar F.
Assumption
4.14
There exist a constant 7 such that Er Fr FF))) S?²
Assumption
4.16
V Fr(w)) is an unbiased estimator of the gradient, ie., E V Fr())) = VF(w).
where the samples I are drawn independently.
A.2
PROOF OF LEMMA 4.5
Lemma
4.5.
(Bound on change of Dz). Suppose that Assumption 4.2 holds, Le.. Vw: v2f(w) 1 LI,
then
1. (vx);l STS Vdl, where Uk 2k F2F(wx)
2. there 38 < 2(1 [ such that
D Dilloc Sd, Wk.
Proof. By Assumption 4.2
we have that
/ /2F < T. and hence
||vall> s | I ((w)) val,
which finishes the proof case 1
Now, from
derive
DR+1 Db
(B2 1)D₁ + (1 -1- B2) 2 2 F F2F(wx)2k (1)
and hence
| Dalloo (1 B2)] 2 C F())) 0o $ (1 B2)l 2k|1
I (1 - B2) Dalloo + (1u)llm)) I 2(1 BT
A.3 LEMMA REGARDING SMOOTHNESS WITH WEIGHTED NORM
In the following, we present lemma for smoothness with weighted norm. Theorem 2.1.5 in (Nesterov et al. 2018) provides the same analysis for any norm, and the following lemma can be seen as special case of Theorem 2.1.5 (Nesterov et al.) (2018) with respect to the weighted Euclidean norm. In the following, we provide the proof for completeness.
Lemma A.1. (Smoothness with norm D) Suppose that Assumptions 4.1 and 4.2 hold, and D then we have:
FF)) F
Ż| vllD,
(17)
where L Amin (D)
14

---

Published as a conference paper at ICLR 2022
L
Proof. By the equality L
Amin (D) we conclude that LD LI which results in:
i | --yl
F(y) S F(x) + (VF()), x) +
(18)
2
Extending proof of Theorem 2.1.5. Nesterov 2013 we define x(v) = F(w) - (VF(x),, Then, clearly, arg min ((y) and (18) is still valid for (by).
Therefore
D- Volu)).
x(x) S p
L
o(y) + (Vo(v), D-1
L.
D-1
(xx)
Voly)) 2 L
Vol
L
2
D- D- + 1
_
F(x) - (VF(z),F)))) Fly) (VF(2)
27
1
F(x) S F()) + (VF()), x-
(IVb())lb)
2L
1
F(x) S Fly) + (VF()).
(IVF(v) vF(2)113)
2L
Thus
F(x) + (VF()). - x) + 2L
(IFF() - VF & F(U).
(19)
Adding 19) with itself with x swapped with we obtain
L ((IFF()) VF(+))1)) < (VF()) VF(x),y x))
= (VF(() - D(y - x))
s VF(= I||
which implies that
[VF()- VF & L yaاp
(20)
A.4 PROOF OF THEOREM 4.6
Lemma A.2. Let f : RRd + R be convex function, and x² is one of the optimal solutions for !
Then, for the sequence of [wx} generated by Algorithml we have:
|| w² w011 - ww wk+1l2 112. + 21 + (F - F(w"))
I || Wi w" 21 D
+ 2
1o0k wk wk-1l1 11 + 2 (F(Wk-1) -F()))))))("))+
2(1 - 30) m.0k
+
1
-1wa-11
wxll 2 I.² C2n0
+ w)]l w0').) (21)
2
Proof. We extend the proof in Malitsky & Mishchenko 2020). We have
||
w0 112 D2
|| Wk + Wi w" 112
||wk+1 w D, + 1w w" |13 + 2(
Wke Du(wk w²))
| well + I| w" 11
+
w" wk)
||R++ wall + ||w w" 11?
+ +F7x(F(w")) - F(wN))
(22)
||a++ 1 + [wk wn 113
- -2m - F(w")),
15

---

Published as a conference paper at ICLR 2022
where the third equality comes from the CASIS's step and the inequality follows from convexity of F(w). Now, let's 's focus on || - wx B. We have
||w++1 - wx ll.. =2|1 - ww. wxll - |W++1 - wk wxllDa
-2(-ms Drc [F(wk), DK(WK+1 wk)) - -11u++1 wx
=mt V VVF(w))))))))))))))))))<)))))( wh+1 - -wx) - -1|2k+11 -wall
-m2k (VF (ur) V WK+1 wa) 21TR ( V VV((w=1))) wk+1 wk)
||WX+11 wi P.
-2m (V F wk WK+1) + 2n F -Wck+))-
|| Wi D.
Now,
277 (VF(w))
VF(WX-1), ws - wk+1) S 27k [F(wk) FF( |ww - wx+1lle.
10
||w - wi-1 11 De 1l - wk+1lld
1 Ill wk+1 D.
U/ wg we- 11 +
Cauchy-Schwarz where the first inequality comes from Cauchy- Schwwrz and the third one follows Young's inequality. Further,
1
FVW(k--)) uk - wk++1)
(
1 - wx), wh wk+1)
7)
1
10e-1(wk-1 wx), m: Dr. - FVW()))
7)-
1]k
(Wk-1 wwx) De-IDD DDF'-D(WA
7]-
7k
(Wk-1 wxx (F
1)k
17
(wk=1 - w (D -1) VF(w)).
(23)
-
where the first two qualities due the OASIS's update step. The second term in the above equality can be upperbounded as follows:
(wk-1-1 = DD - VF(Wk) < (1 111--a)
32)
2r
||wk-1 - wxll \V
(24)
where multiplier on the left is obtained via the bound on Iloo norm the diagonal matrix Dr D
11DE-11 =1 = max Dr
max ( [D ')1 32) 21
which also represents bound on the operator norm of the same matrix difference. Next we can use the Young's 's inequality and (F(w")
to get
(1 - 32) | wxll - || FF Il < (1 B2) r (1 wpl2 22 L - w=1l)) (25)
Therefore, we have
(VF(wk-1) 1),0, w/ wk+1) <
7
(wk-1 - wKk [WWw)+++
7k-1
T
B2) a
(1luk-1-
w T.?
1.? Pw1 w w11
16

---

Published as a conference paper at ICLR 2022
Also,
1
1
||k+1 w.ll...
2 llwx wk-1ll..
+ +zllux wk+1ll + 2mm wx) V [[(w))+
r
21y 0x -
-11lux11 wxll2 + 1.81100k w² w²(1²) ||00+11 wk Dr
1 =llux wx+1ll 113. + 2m 21F - - F(
$ 2 wu wk-1 11
+
2
r
277a (1 - (2)
-111uk-11 wkll + L2llu0 w²11²) ||0++1 - wxll D.
a
Finally, we have
1 =/luxx wk+1ll + (F(wx))())-)) - F(w+))+
| w=12 De - 2 1/11 uk-
I (2)
2nx (1-3)) (110-1(11111--1 wxll2+ + L²² lux w w1 1--||/x+1 wk 1xlB2z
a
+ | w0 1l.. -2n((F(ux) F(w")),
By simplifying the above inequality, we have:
|| - "=' -='1,
2 ww - wx+1ll + +2mx(1 + (F)(((ww)) - F(w"))
$ |w - w w1, + +221lu 21lls
+ +n -
+
r
02 - (22) a
(1ww-11 - wull? L/11uus 113)
=1|10k w0 Dz-1
+
2
1
| wk- 11-1112.. 22 21 F(w"))+
r
2m - (2) (110k-1- wwll2 2 +11211100. w" 11
1w0k - -w-wwll "1 Br 1
+
l - wx w 11 Br
2
1
$ |lwx - w²1 Da-1
2
+
11/8 - wk 111 11., - (FFO((F(ux1)) F(w*))+
2
21 - -32) l'
(1
wull 2 L2llure w 11²)+
1
2(1 (2)T((1
11=
[llwa 113))
1
|| - w011 D
+
| wh wh- 11 - Oz (F (F(wx-1) F(w"))
2
|W--1 wx + L L'm 1| w0 lluee w0 1|2+
2(1 ;2)T((
a
ww wk-1 113)
Theorem 4.6
Suppose that Assumptions 4.1 4.2 and 4.3 then we have:
hold. Let {wk} be the iterates generated
by Algorithm
F(WE) F < LC 21(11 Bz)1
Qx
k.
where
= |wl
w² 11? + o |11001 - wo woll?, + 2m 01 (F(wo) - F(w*))
Q Σ
( 11:0;
, || wil12 + I.2 1.2
1
1) w w0(l2)
i=1
17

---

Published as a conference paper at ICLR 2022
Proof. By telescoping inequality
21 in Lemma A.2 we have:
|10+11
w"1
- [uk
wk+1 11? 2m (1 (x)(F((x)) FF(w"))
1-1
+ 2
(1x(1 + 0.) - 1k+ 1 - F(w*))
==1
1
$ [1
w" 11
u0 wo wolld, + (F((w)) F(w")) +
2
h 2(1 B2)
1 + 1100-11 wil1 12
1)]1u; w w²)
+
Qx
Moreover, by the rule for adaptive learning rule we know 17:11 ((]++;)) 0:) - -1/+10141 20, vi. Therefore, we have
R-
(1 1 + (F)(())))))))) - F(w)))++
[7:(1 + +1)) - 1 (F(W))
1=1
+ 2(1 - 32)I
By setting 7m(1 + Wx + Σ k (m (1 + 0.) Th+ T4+10+41 (1110+1)m where Sa na(1 + 0x)
S
Σ (1,(1 0.) nh 1++10+1). and by using Jensens's 's inequality, we have:
C
+ 82)1 Qx
F(wx)= F S
28p
Sk
1
2L
By the fact that M/ 2 thus
S k
we have
2L
Sk
LC
2L(1 - 32)1 Qk
F(wx) F
<
+
k
K
A.5 PROOF OF LEMMA 4.8
a r
Lemma 4.8.
Suppose that Assumptions 4.2 4.3 and 4.4 hold, then me
2L 2p
Proof. By (1 and the point that i
conclude that:
Amin (Dx)*
Ww Wk-1llB. 2| V F(W)
Amin (Dx)
Amin(D))
VF(W*-1)l3
D. 2L
2.
2L
1w4 - all
Now, in order to find the upperbound for V[VF
we use the following inequality
which comes from Assumption 4.4
F(WR) 2 (wwk-1) + (VF(w) 1), (wx - wx-1)) + llw - wk- 1111 1112.
(26)
By setting i #
Ama) we conclude that D.D μT which results in:
F(wx) 2 F(Wa-1)+ + (VF 1), (wk w 1)) + 2 w|w - wk 10.2113..
(27)
18

---

Published as a conference paper at ICLR 2022
The above inequality results in: j - wk- 11 - (VF(wx) VF((x=1); (wx - wk wk- 1))
(Dx (VF VF((w=1)), Dx (wx - wk-1))
(F((k)) V w wk-
(28)
Therefore, obtain that
100. Wk-1llb.
Amax (Dx) r
(w)) (F(( DN
2/1
2/1
2/1'
a T
and therefore, by the update rule for 7)., we conclude that 7/k: E
2T,
2/1
A.6 PROOF OF THEOREM 4.9
Lemma A.3. Suppose Assumptions 4.2
4.3 and 4.4 hold and let w" be the unique solution of 7
Then for (wx) generated by Algorithm
we have:
Wk++1 - w²1
+
Wk+1 - wx + (1+ (F(())))) - FF
D2
1| -0'13,-
+ Ilux woik--w-11ppp 113, + +2 - F(w*))
20 ) pm110
- B2) (1-B2)I
1+
|/ux 1k-1
2L 2L20kTT
-(1- 82)1(
+
1m71)
| w" 112
a
Proof. By the update rule in Algorithm I we have:
|| w² 11?
= Wk wkk + Wi w 11?
|| wk 11 D2 + [w - w" 1|? + 2(wk+1 - Wky Du(wx - -w"))
|| wxl1,, + || w" 11? + (VF w" wk)
|| wxll + || w" 11 + 2nx(F(w") - F(ww))
(29)
|| wxll2, + || w" 11 27 - F(w")))
where the inequality follows from convexity of F(w). By strong convexity of F(.) we have:
F(w")= F(wx)+ (VF(Ww), =t - wx) + |u w" 11.
(30)
2
In the lights of the strongly convex inequality we can change (9) as follows
30
|| w=
| - 11 + |lwx - 11 + 27 (F(")) - F(wx) - 2 ||l. - w0(l²
D
|k441 wx1 + +lwux - w w011?, - 2m (Fww)) - F(w")) - mmmlluu w w01
(31)
19

---

Published as a conference paper at ICLR 2022
Now, let's focus ||wx+1 - 2. We have
||
wk m l..
=2 =2||wx++1 - wxx1 |1 -
=2(-ne VF(wk)), (2tw+++11 wk:) - -11Uk+1 w Dx
- F (wk) wk+1 wwx - || wxl1
= 2 (VF - F (wxk=1), Wk+1 -wa) - 21 ( V F (( wk+1 wkk)
1| wk 1
(VF(x) (F(=x=1). wx+1) + 2mp. (VF(W=-)) wk -KW++1))
|| wi lie
(32)
Now,
27/ (VF(wR) VF(Wx-1), wk+1)
2m [F((k)= FF((w= Ilwe Wxt1le.
- 1 - wk- |wx - wk+1ll Dr
1 |lws wk+1 2 D.
$ 2 | wK
wk- 11 l... + 2
(33)
where the first inequality is due to Cauchy- Sehthar- inequality, and the second inequality comes from the choice of learning rate such that m obtain:
1w -
2 VF(wn-))) By plugging (33 into 32)
32
|w++11 -w 11
wx-1112.
+ + =1l wbt11.. + 2 (VF wy - wk+1)
|| wxll? 1l.
(34)
Now, we summarize that
||
w0 D.
[bb+1 wxll + ||10 - -w'1.,, - -27) (F(x)) - F(w")) - 10m1llax w 11
ww wh- 11B.
+ 2
|lux - ww- 11.2 + 27 ( FV ww wk+1)
| wxl13.
+ |lwc w= w²113: -277 (F(w)) - F F(w")) - ummllux 20 11
1
|wun wk- .1...
| wx-
.1B3, -x-
+ 27k ( (VF 1), wh wk+1)+
2
|mm w0ll 112, -27 (F - F(w"))) - umkll w/ - w w01
2 |m wk- 113,, + |lwe w² 113,m = ||00x - Wk+ 11 112
27Hx V F(wk= 1). wk - wk+1) 21//( (F(wk) - -F(w*))+
5] wk wk-1 11..- + 1|wx 10, -w'1'2_-r-- pOTA || w²
(35)
Next, let bound (VF(wk-1) 1), Wi Wk+1)-
By the OASIS's update rule, Wk+1 Wk
T7 D' FVFF(w), we have.
1
V FVF(w- wx - wk+1)
( (Wk- - wx), wk wk+1)
1
(ip-1 Wx), mm Drx - -I
7
(Wk-1 - wTx) DE- -VV((w))
7]--1
7]k
(Wk-1 wxx TVF(ww)+
1)k
1]k.
(Wk-1 - w (D--DDa-1_ 11) VF(wx).
(36)
7):-1
20

---

Published as a conference paper at ICLR 2022
The second term in the above equality can be bounded from above as follows:
(DE-IDu-L VF((k) - (0))
2r
|| -ic-1-wxkll wxll (VF(w)) (37)
where multiplier the left is obtained via the bound on Ileo norm of the diagonal matrix Da-1 D
m max Da), (1- 32) 2r
1| 11100 max
which also represents bound the operator norm of the same matrix difference. Next we can the Young's s inequality and (P(==)) = to get
82) 32)-
21
|w--
wxll
|| F (Ww)) (1 32) (1 - wxll + 1 w 113). (38)
By the inequalities (72)
(36).
(37) and (38), and the definition O2
7
have:
77--1
|
w01 11..
|Wu++ wxll
27 (1 + (z)(F((x)) F(w"))
1 ||w|
||0b w0 "0=1B, 11:b_,
+
wx-1
D._, + 21 (F F(w"))
1 lur Wk-1 D +1 B2)
(2)
21 ||00% wk-1l1 pum I| wx 111
a
2T ATI.2kkm1
| w0 10'1.,.-AA -Be, +(1 (2)
||w w0Il"
umnal ww w' w²11?)
α
w= =='1² "112._.
+
|100 - -w=-1ll Da_, + 22m.0(FF(xx F(w"))
2
20%TTK
(1 B1)]
1
||u5e -w--1l 11? (T7100))
2
(1-112)) [2)r
||uE w=11
αx
Theorem 4.9 Suppose that Assumptions 4.2
4.4 and 4.3
hold and let w be the unique solution Then, for all k > have:
for
Let [wk] be the iterates generated by Algorithm at atp²
a س²ي²
82 max(1-
1222 4LI L
a
x+ < n 4
(39)
where
||
w0 w=1 || - -wll3, + 21p (F)(() F(w")).
21

---

Published as a conference paper at ICLR 2022
Proof. By Lemma A.3 have:
Wk+1 w"l w01
+
2 |10+41 - wx uxll?2 (1+ F(w"))
1
1lwx =='1
+ 2
Fllux= ww-1ll2._ + O2 F(w"))
20x:1he
) -mma0s))
1 (1-)))r
B2)T
||ux wk-1 11?
21. 21.20
(1 (1- B2)T
2
||usk w" 112
a
a r'
Lemma 4.8 gives us 7/s E
we can choose large enough A8 E (0, 1) such that
2T, 2/1
20xT7k
(1 (1- - 82)[
1
S 0,
(1 52]T 2 2270 ) pmltle
S 0.
In other words, we have the following bound for 32:
a²1²²
a² 22 + 19T2)
B2 max 222
(40)
However, we can push it one step further, by requiring a stricter inequality to hold, to get a recursion which can allows us derive linear convergence rate as follows
20xTH
(1 32
1
1
- 2
a
2L OuTlk
1
(1 - 11) 2+
pTl
2 umlk:
which requires a correspondingly stronger bound on $2:
a'n²²
B2 2 max
4L21 + LI (20 + 1912)
+
(41)
Combining this with the condition for 77 and definition for Os. we obtain
(1 (a- 32) (1+ 20kT7 0
1 ||wx w6-111 < uuma0llluuu ws-1l1
a²
-0 112 1/
x
and
(1- B2)r (1-)))r(2+ 2
2220
1 w011² <
1|w
2 umi ||w w w1
S 4 |w w 11?
where x n. Using it to supplement the main statement of the lemma, we get
| w0 1..
|KK+ wall.,
2n (1 + (2)((( F(w"))
a²
< (1
Ilwe w01 113 + 11
w + 2m - F(w")
4T
22

---

Published as a conference paper at ICLR 2022
Mirroring the result in MMaltsky & Mishchenko 2020) get contraction in all terms, since for function value differences we also can show
77
a
=
S 1
1/6 + 0%)
(1 + 02)
A.7
PROOF OF THEOREM 4.11
Theorem 4.11 Suppose that Assumptions
4.2 4.4 and 4.3 hold, and let F F(w") where w* is
a²
the unique minimizer. Let }wk} be the iterates generated by Algorithm I where nk 17 f LI and wo is starting point. Then, for all & N 0 we have:
F(Wk)= F F
qu )tt F(wo) -F
(42)
Proof. By smoothness of F.) we have:
F(wk-1) = F(wx- - - vf(w)))
S F(wk) + VF(ww) (- 'v [[()))) - 1n ( v((u))l
s F(w)) - [F + 2
(=(=))11
2a
n
F(wx))
7 T 2a
[[
(43)
S F(wx)
11 2T [VF(w))ll
(44)
where the first inequality comes from Assumption 4.2 and the second inequality is due to Remark 4.10 and finally, the last inequality is by the choice of n, Since F(.) is strongly convex, we have [ (wx) - F*) < [[V)( 12, and therefore,
nP (F(w)) F*).
F(Wx+1) & F(wx)
r
Also, we have:
F(wx+1) - F* s (1
D (F(wk) - F*).
r
A.8
PROOF OF THBOREM 4.13
Theorem 4.13.
Suppose that Assumptions 4.3 4.12 and 4.2 hold. Let {wx} be the iterates generated
by Algorithm where 0 < MJ = 7
and wp is a starting point. Then, for all > we have: Lr'
1
[V()))) ([(F(ww)) F T T 0.
(45)
T
TT
Proof. By starting from we have:
F( S F(wx)
"
VF (W.w)))) )12.
(46)
2r
By summing both sides of the above inequality from 1: 0 to
T
we have:
T
(F(wx+1) F(wx)) <
V F (1
2T
k=0
k=0
23

---

Published as a conference paper at ICLR 2022
By simplifying the left-hand-side of the above inequality, we have
Σ [((w++1) - FF(x)) F(wr) - F(wa) 2 - F(wo),
k=0
where the inequality due to F. S F(WT) (Assumption
4.12). Using the above, we have
(F( [VF(()))] 2r
F]
(47)
7
A.9 PROOF OF THEOREM 4.17
Lemma A.4 (see Lemma (guuyen al. 2018) or Lemma 2.4 (Gower et al. 2019)). Assume that Vi the function F.()) is convex and L-smooth. Then, Ve E Rd the following hold:
Er Er]l[Vz((w)) (I((F(w)= - =(ww)) )) + 20
(48)
Theorem A.5, Suppose that Assumptions
4.2
4.3
4.4
4.15
and 4.16 hold. Let parameters a >
?) > O, B2 E (0, 1] are chosen such that a the iterates generated by Algorithm 7 then, for all k 2 0,
2T. $2 > 1- 2τ(
qua
> 0. Let {wa} be
w "1 1.. $ - |1ol| (1o0) + (1 2(1- 20
Ell W/
(49)
where c=
11o (T-np) 221-m))(11-111111 B.2T
10,,1).
To
Remark A.6. If we choose B3 = 4T(l" np))
aua
> 0 then
a||lw w= 11/.p1 s (1
4F
Wwo w= 11
+ + nT-naa 1
2 nu Io2m 11.
Proof. In order to bound 1n++11/ Doti by ||rx+ 113, we will use that
0 x Dx+1
D2 + De+1 D2 D₁ + 11D Delloot 3 Dr + +1Dx+1 - Dalloo
Dr + || - D ~ Dr 2 - 1T
D₂ + 2(1 32 D (1 + 2(1-8e)1 Dr.
(50)
Then
30
|| Dost
(1+ 2(1-
| 112 (1 + 2(1 ||rk - Dn
-1 -VVFr, (wx))
(1 + 211 8:I
||r
22n + 2(1 2(1-02)1
(rrk VFr. (wk)
a
+ (1+ 211-8-1 )r² (I FIg (wxx 11%,2)
< (1+ + 2(1 - 131
|| 11,,
2n (1 + 2(1 2(1-8221
(rk, V (wk))
a
+ (1 2(1 B n²
V PT ( (wa) 2
(51)
24

---

Published as a conference paper at ICLR 2022
Now, taking expectation with respect to Ia conditioned on the past, we obtain
E[llr++1| 11 D
(1 + 2(1-
|| /1rall
+ +12 + 2(1-8) (F+ F(wx) - - Ell w01)3)
IT T (4L(F(u>)) - +20²)
+ (1 2(1 11
$ (1+ 20 PT)
2(1-8a)1
||rx
+ +22(1 + -11- (F- F(ww) 2 1mlll
P
Du
21
+ +(1+ 2(1- 2(1-0o)1 Ba
T (AL(F(w:)) F*) + +20²)
(1 + 201 )
(1-211 2T ||ral122
+ 20 B.)l
(11 221) ((F(wx) -P)) + (1+
2(1-3211'
x²
20
a
a
< (1+ 20 -- Br
(1-1(²)
11
||<iI|, + +1+ الااااا )
(52)
a
a
where we used the fact that 2L " have
- -1 0 17 7 2i In order to achieve a convergence need to
a
(1+ 2(1 M/)1
(1 |
1-ck
a
r
We have
(1 + -()
(1-
qua-
(T- m))2((1 B22TT
T
Po
Now, we need to choose Bg such that
7pa
1> 82 > 1
O.
21" nu)
With such a choice we can conclude that
52
E||lr 1
(1 - e)
D -
+ (1 + 2(1-B2)I r 20²
h-1
$ (1 e) 11o0
(1 c)'(1 + 2 12) 8 20
==0
$ (1 - c) 11o0l0
+
(1 c) + 2(1-82)1 n 20
0=0
S (1 - ()-o))(1ro11300
+ (1 + 21) )
20'12 ac
Theorem 4.17
Suppose that Assumptions 4.2 4.3
4.4
4.15 and 4.16 hold. Let {wk} be the iterates
generated by Algorithm with Th = E (0, f7.2). then, for all k 2 0,
([F(wu) F=] s (1 c)* (F(w)) - -F*)+ 1)2 Lo²
(53)
ca2
where
2np T
L² E (0.1). Moreover, ih = E (0, (F(wo) F*) +
2TL then
a²H
[(F(w))) F*] = (1 nue r
Lo²
(54)
Q²1 μ
Proof. First, we will boper- the F( using smoothness of F(w) F(wx+1)= F(wn- 1, - Fr (wx))
L
< F(ww)) + V x' (- - -VV (wx)) )) +
-
-1
Fr, VVr (ww)ll
2
1
< F(ww) - (()(w)))) -VV (wx) +
v F (wx))1
20
25

---

Published as a conference paper at ICLR 2022
where the first inequality is because of Assumptions 4.2 and 4.4 and the second inequality is due to Remark 4.10 By taking the expectation over the sample Ix. we have
11 L
Er, [F(w++1)] I F(wa) BI, (ux)) D FV. (wk)]
EIg
VIIVFI, (wx)]
2a
= =(ww)) (VV)(())) T Dr (VF(u)) + r/24
ETY |I| ||||/|/// FI, (1xx
20
7 |VF((u>)) T²
S F((w))
(4L(F(wx) - - 20
2n
L (AI(F(ux) - F*) 20²²
F(ww)) + 2 (F* (Fwx)(ww))
(55)
20
Subtracting FM from both sides, we obtain
L
(F(wk) - -F)) + T2
Ez, (F(w++1) F*1
1
2
+
4I
r
2a
a²
2np4
2n
(F(wx) - F²)++ + 17 Lo² (56)
r a²
a²
By taking the total expectation over all batches Io, I1, Iz... and all history starting with wp. we have
56
k-1
c)¹ n
Lo
B[F(wa) F*]
(1 - c)a (F(wo) F² +
Σ (1
a
1=0
00
c)² LO2
(1 5)* (F(wo) P²) Σ
a²
(1 c)a (F(wo) F*) + 1 Loz
co2
o²p then 2
and the 53 is obtained. Now, 1) S
2qp 21j² 1,2
1
a²1 1 1,2
11
11
m
c=
2 2n
21
r
a²
r
23 a²
r
21
r
and 54 follows.
A.
PROOF OF THEOREM 4.18
Theorem 4.18
Suppose that Assumptions 4.3
4.12
4.2
4.14 and 4. 1.lodd. Let {wa} be the iterates
112
generated by Algorithm where 0- < mh = S
and is the starting point. Then, for all
LI'
k 120 O,
F(wo) F]
TT
TT?2L a²
E VF (ww)))
I+0x,
n/T
a²
Proof. We have that
F(wx+1) F(wn- - Tr (Wk))
L
< F(ww)) + VF(wx) " (f (- LVPPT (wx) +
-1 -VV (ww))l?
2
1/L 20
< F(ww) - (V)(())) Dr. -1 -VV (wx)
v
F )1
26

---

Published as a conference paper at ICLR 2022
where the first inequality is because of Assumptions 4.2 and 4.4 and the second inequality is due to Remark 4.10 By taking the expectation over the sample Ix. we have
11 L
Er [F(Wx+1)] I F(wR) BL, V FF )" D FI. (wk)]
EIg FI, (wx)
2a
= =(ww)) FVVF(W)) Di - (VF(W)) + r724 ET,
||| FIN (w<x
2a
nL
< F(ww))
[VF(w))] )1
(57)
2a²
20²
7p-22
F(ww))
V (W+)())))
(58)
2r
2a²
where the second inequality is due to Remark 4.10 and Assumption 4.14 and the third inequality is due to the choice of the step length.
By inequality (58) and taking the total expectation over all batches To. I1. I2... and all history starting with wg. we have
1p7221
B[F(wk+11) F(wx)) S E V V
"
2r
2a²
By summing both sides of the above inequality from 1: = 0 to 1
T
T-1
?T22LT
E[F(wx+1) - F(ww)] -
2T
202
k=0
1T
7 E
VF(wx)]1
21
2a
By simplifying the left-hand-side the above inequality, we have
T-1
[((k-1)) - F(wx)) [[F(wr)] F(wo) 2 F - F(wo),
0=
where the inequality is due to $ F(Wr) (Assumption 4.12)
Using the above, have
[F F]
2 2
E
VF(()) 1
17
A.11 PROOFS WITH LINE SEARCH
Given the current iterate wk, the steplength is chosen satisfy the following sufficient decrease condition
F(wE + TPPk) S F(Wx) er VF(w)) D. - FVW())),
where Pk = - -VFF() and E (0, 1). The mechanism works as follows. Given an initial steplength (say 7ソ = 1), the function is evaluated at the trial point wi + agps and condition (59) is checked. If the trial point satisfies (59), then the step is accepted. If the trial point does not satisfy (59). the steplength reduced (e.g., 7)s T/j for т 1)).)) This process repeated until steplength that satisfies (59) is found.
Algorithm 2 Backtracking Armijo Linesearch (Nocedal & Wright 2006)
Input: Wk. Pk
1: Select Yaaia, E (0, and (0,
2: 17" Mmnnial = 0
while F(wrx m)Pp) > F(wx) ci7ss F(ww)) PF pa do
4: Set Sf 1 Tw/
5: Set =
end while
Output: 7) Nr
27

---

Published as a conference paper at ICLR 2022
By following from the study (Berahas et al. 2019). we have the following theorems.
A.11.1 DETERMINITIC REGIME - STRONGLY CONVEX
Theorem A.7. Suppose that Assumptions 4.3 and 4.2 and 4.4
hold. Let {wk) be the iterates
generated by Algorithm !
where Ths the maximum value ( : = 0, ....... satisfying (59)
with 0 < C1 < 1, and is the starting point. Then for all k 2 0,
F(WN)= - F (1
4pa2c ci -
[F(wo) - FMJ.
I2I.
Proof. Starting with (43) we have
F(wE= 776 Dr FV((k))) S F(Wk) - 7l (1
L.
?} 2a²
[VF(w))]l
(60)
From the Armijo backtracking condition F Fww:= me Dr
59 we have
'V WVF(was (wx))
s F(wk) C1 V F (wr)) )T D3 -VFF(FF)
S F(w)) 71 IVF wx)ll
(61)
Looking at (60) and 61 it clear that the Armijo condition is satisfied when
2a c1)
Tee
(62)
PL
Thus, any Th that satisfies 62 is guaranteed to satisfy the Armijo condition (59). using a constant backtracking factor of r < 1, we have that
Since we find
2a (1 eatT
7 2
(63)
PL
Therefore, from 60 and by (62) and 63
we have
M/ L
F(W++1) & F(Wk) 7/k:
r
2a
T1 $ F(wk) r
/ (wx) 112
2a c1 (1 C1)T
< F(wk)
VF(w))]1
(64)
L
By strong convexity, we have (F(F(w) F+) < [| and thus
F(w++1) < F (wx) 4 c1) (F(w) FF).
(65)
Subtracting F from both sides, and applying (65 recursively yields the desired result.
A.11.2 DRTERMINISTIC REGIME- NONCONVEX
Theorem A.S. Suppose that Assumptions 4.3 4.12 and 4.2 hold. Let {wk} } be the iterates generated by Algorithm 7 where is the maximum value in ( = 1, 0,.....) sutisfying 59 with Ci and where wi the starting point. Then,
lim [[F((w)] = 0,
(66)
and, moreover, for any T >> 1,
T-1
[2 - FF x-00 0.
V (ww))))
20 (1 CI)TT
R=
Proof. We start with 64
2a² cj (1 C1)T [F(#))112
(wi+1)
F(wx)
T
Summing both sides of the above inequality from k = 0 T - 1,
T-1 2a²c (1 C1)T
Σ
(F(w)+1) F(ww)) <
V VF(w)))
1
k=d
k=d
28

---

Published as a conference paper at ICLR 2022
The fetthand-side of the above inequality is telescopic and thus,
[((w++1) F(w+)] F(wr) - F(wo) 2 F - F(wo),
k=0
where the inequality due to F. S F(WT) (Assumption 4.12 Using the above, we have
(1 T [= F.
(67)
(1-a
Taking limits we obtain,
lim
[F(w))] <0,,
k=
which implics (66). Dividing (67 by T we conclude
[( F
[VF(w))]
T
20 - -1)TT
A.12 PROOFS WITH DECAYING STEP-SIZE
In this section, we provide the analysis with decaying stepsize for both strongly convex and nonconvex cases the stochastic regime. The proofs for the following theorems follows from the proofs in Theorems 4.17 and 4. 18 and Theorems 4.7 and 4.9 in Bottou et al. (2018).
A.12.1 STOCHASTIC REGIME STRONGLY CONVEX
15 and 4.16 hold., and let F* = F(w*), where w" is the minimizer of F. Let {wk] be the iterates generated by Algorithm where mh is sequence of stepsize such that, for all k 2 0,
Theorem A.9. Suppose that Assumptions 4.2
4.3
4.4
r
a² p
for some >>> Then, for all k 2 0, the expected optimality gap satisfies v [F(((R)) - F*]
T +
and <> such that 7/0 S
(68)
P
21 21
(69)
c+
where
8 Lo²
V == max
(((F(w)) - FT)}
(70)
1)a2
Proof. By taking total expectation from (56). and replacing 17 with 77 we have:
2mp
21 [[F(wL) F*}
Lo
B[F(wk+1) F
(71)
r
a²
a²
By the assumption
I a² 2r12, and the way that me is designed, i.e., in a decaying way, we have
Th < no < 2F7 therefore
2TH
r
2n
a2
21ja
F
2T az
a² L2
21j
(
2T
Thk
r
Thus, we have:
1h Lo
[[F(w++1) < (1-
Mall
B
B(F(wx)
(72)
2
29

---

Published as a conference paper at ICLR 2022
We do the rest of the analysis of (69 with induction. First, for k 0, (69) holds by the definition of (22
v. Next, assuming (69) holds for 1 0, by
we have:
Of
Lo
B[F(wa+1) - p
r
h
K
1:202
k
L²
r
1/ +
12
k²a2
61
Lo
T
U
122
122
1222
nonpositive by definition of
(73)
k: +
A.12.2 STOCHASTIC REGIME NONCONVEX
Theorem A.10. Suppose that Assumptions
4.3 4.12
4.14 and 4.16 hold. Let {we} be the
iterates generated by Algorithm 7 where is steplength sequence satisfying
Σ
and
n <0.
(74)
and wy is the starting point. Then, with Ar
= k=0 me
lim
E.
m V
< 00,
(75)
T-000
and therefore El
Ms
VF(w))113
T 0.
(76)
AT
Proof. The steplength sequence {mk) goes to zero due to the second condition in 74 meaning that
2a
w.l.o.g., we may assume that 7/k 2TL
for all A 0. By starting from and taking total expectation
from 5 we have
[[F(wk+1) -E[[())) S -7p (1
1
n
n L
E
V
FW (1
2a
2a
7h Elll V F (w)) |1
2r
2a
Summing both sides of this inequality for {0... .,. T 13 gives:
E[F(wo)] < F - E[F(w < [[F(w))] -
1 T- k F
7TT
-T-
Th-
2r
2a
(77)
Multiplying by 2r, and rearranging we get
TT2 T- Ek=o
2T( F)
(78)
a²
The second condition in 74 guarantees that the right-hand side of the above inequality converges to a finite limit when T increases, therefore, it implies (75). By the first condition in 77). we conclude that Ar as T co, which results in 76
30

---

Published as a conference paper at ICLR 2022
A.13 CONVERGENCE BOUNDS INTERPRETATION
In this section, provide the interpretation behind the convergence bounds in our theoretical results.
Theorem 4.6 there the term (1 (1-33)[ Qx which essentially highlights that the
parameter 32 controls the size of the neighborhood of optimal solution(s). In other words, 32 is very close to (which is the case for our algorithm), the convergence neighborhood would be very small. Meaning that, with the assumption regarding bounded iterates, our algorithm converges to very small neighborhood of optimal solution as 82 is very close to (while in SGD the step-size controls the size of this neighborhood and accordingly, the step-size needs to go zero in order to converge to the small neighborhood of the optimal solution(s)). Note this convergence guarantee is for smooth and convex case with adaptive learning rate.
Theorem 4.9 provides linear convergence rate for the smooth and strongly convex with adaptive learning rate. The analysis behind this theorem is based on the I. Lyapunov energy that decreases linearly.
Remark 4.10
guarantees that the OASIS preconditioning matrix is positive definite and its eigenvalues are uniformly bounded above and below.
Theorems 4.11 and 4.13 provides linear and sublinear rate to the stationary point(s) for deterministinc strongly convex and nonconvex cases, respectively. The learning rate is fixed in both mentioned cases, and the convergence rates are similar to those of limited-memory quasi-Newton approaches (e.g., L-BFGS).
Theorems and 4.18 provides linear and sublinear rate to the neighborhood of sta- tionary point(s) (in expectation) for deterministinc strongly convex and nonconvex cases respectively. Please note that we provided another convergence guarantee for the stochastic strongly convex case (please
Theorem A..5). Again, the deterministic cases, the provided convergence guarantees completely match with those of the classical quasi-Newton methods (such as L-BFGS); the learning rate is fixed in the latter cases. Please note that these methods (such as OASI: S and classical limited-memon quasi-Newton methods) in theory are not better than GD-type methods. In practice, however, they have shown their strength.
Theorems A.9 and A. 10 provides convergence guarantees for the stochastic setting with decaying learning rate. The mentioned theorems provides the convergence guarantees to the stationary point(s) (in expectation) for the stochastic strongly convex and nonconvex cases.
Theorems A.7 and A.8 provides linear and sublinear convergence rates the stationary point(s) for the deterministic strongly convex and nonconvex cases with utilizing linesearch.
B ADDITIONAL ALGORITHM DETAILS
B.1 RELATED WORK
As was mentioned in Section we follow the generic iterate update:
7)k Dx mm--
#k+1 wi
Table summarizes the methodologies discussed in Section 2
B.2 STOCHASTIC CASIS
Here we describe stochastic variant of OASIS in more detail. As mentioned in Section to estimate gradient and Hessian diagonal, the choices of sets I, Jg C [n]]. are independent and correspond to only fraction of data. This change results in Algorithm
31

---

Published as a conference paper at ICLR 2022
Table 3: Summary of Algorithms Discussed in Section
2
Algorithm
mk
Dx
SGD
Robbins & Monro
1951
Bm +
B1)
Adagrad
Duchi al.
2011
9k
Ei diag o Og))
RMSProp
Tieleman & Hinton
2012
9k
Bo B2 D 2 + (1 - B2) (2)diag( ga)
(1 - B1) E 1==1
P
91
(1- (1) Σ 32 diag(g + @.)
Adam Kingma & Ba 2014)
(1 - B1) i
11 91
(1 32) Σ gk
AdaHessian
Yao et al. 2020
1 8
1 $
CASIS
9k
kb- (1 B2) Uk
4 di @ V2 and 2; Rademacher((.5) Vi 1,
" "([A))i = max |A a}
"*D, B2 (1 B2)
Algorithm 3 Stochastic OASIS
Input: W/: 1Jo. In. Db, 8o +00, $2,
Do - -WFFFFFWWl 2: for == 1. do
1:
3: Calculate D2 = D2 + (1 - B2) diag(E; O 2 (wx)
4: Calculate D) by setting (Dx)i,; max m a}. Vi [d] w we 11
5: Update Mi min / 0g 1- 1, 2 Fz, (w)). v Fzz (ux 1 D
6: Set Wk+1 = wk Dr VFz (wk)
7: Set 02 1
TH-
8: end forr
Additionally, in order to compare the performance of our preconditioner schema independent of the adaptive learning-rate rule, we also consider variants of OASTS with fixed y). We explore two modifications, denoted as "Fixed LR" and "Momentum" in Section 5 "Fixed LR" is obtained from Algorithm33 simply having fixed scalar for all iterations, which results in Algorithm 4 "Momentum" is obtained from "Fixed LR" by considering simple form of first-order momentum with parameter 31. and this results in Algorithm 5 In Section C.5) we show that OASIS is robust with respect to the different choices of learning rate, obtaining narrow spectrum of changes.
Algorithm OASIS- Fixed LR
Input: wo. 1). It. Do. B2, a
DD 'V Fr, (wo)
w1 = wh
2: for 1,2, do
Calculate D₁ D2 32) diag(2; @ F2, (w))=k)
4: Calculate Dr by setting (Dx)., man eield [d]
5: Set Wk+1 nD -VF (wx)
end for
32

---

Published as a conference paper at ICLR 2022
Algorithm OASIS- Momentum
Input: wo, 17. Ix. Do, $1, B2
Set mg Fvr,, (Wo)
2: wi = wh - - -mo
3: for = 1,2.... do
4: Calculate D2 = B2Dx-1+ diag(2 @ Fu, (wx)2x)
5: Calculate D& by setting (D&).. = m Vi e [d]
Calculate my $1 m= + (1 31 Fr, (wx)
Set wk+11 wk D mm
8: end for
In our experiments, we used biased version the algorithm with Za = J2- One of the benefits of this choice is compute the Hessian-vector product efficiently. By reusing the computed gradient, the overhead of computing gradients with respect to different samples is significantly reduced (see Section B.3).
The final remark is related to a strategy to obtain Do. which is required at the start of QASTS Algorithm. One option is do warmstarting, i.e., spend some time before training in order sample some number of Hutchinson's 's estimates. The second option is to use bias corrected rule for Dj similar the one used Adam and AdaHessian
D = D2-1 + (1 32)diag(Z* @ F2F (wx)2x),
D₁
D
1 g
which allows to obtain Do by defining D-1 to be zero diagonal.
B.3 EFFICIENT HESSIAN- COMPUTATION
In the OASIS Algorithm, similar to AdaHessian (Yao et al. 2020 methodology, the calculation of the Hessian-vector product in Hutchinson's 's method is the main overhead. this section, we present how this product can be calculated efficiently. First, lets focus on two popular machine learning problems: (i) logistic regression; and (di) non-linear least squares problems. Then, we show the efficient calculation of this product in deep learning problems.
Logistic Regression. One can note that can show the Ez-regularized logistic regression as:
F(w)= = n [nn log + -Yo=
|wl
(79)
where 1, the vector of ones with size n. is the standard multiplication operator between two matrices, and X is the feature matrix and Y is the label matrix. Further, the Hessian- vector product logistic regression problems can be calculated as follows (for any vector (Rd):
rox
F(F(w)x== x0=
x
X
+ Av.
(80)
(1+e-Vex
The above calculation shows the order of computations in order to compute the Hessian-vector product without constructing the Hessian explicitly.
Non-linews Least Squares. The non-linear least squares problems can be written following:
F(w) = Y x(x"
(81)
2n
33

---

Published as a conference paper at ICLR 2022
The Hessian-vector product for the above problem can be efficiently calculated as:
4 F(w)
(82)
-x² 1 4(x 2 2(1 + w) 30(x (xxxx) oxx x(x")))
Deep Learning. In general, the Hessian vector product can efficiently calculated by:
0 F2w(w) V'F(w)+U==
á
(F V).
(83)
Owdw
Ow
Ow
As is clear from N two rounds of back pack-propagation are needed. In fact, the round regarding the gradient evaluation is already calculated in the corresponding iteration; and thus, one extra round of paok-propagation is needed in order to evaluate the Hessian-vector product. This means that the extra cost for the above calculation is almost equivalent to one gradient evaluation.
34

---

Published as a conference paper at ICLR 2022
Table 5: Deep Neural Networks used in the experiments.
Data
Network
# Train
# Test
# Classes
d
MNIST
Net DNN
60K
10K
21.8K
ResNet20
50K
10K
10
272K
CIFARIO
ResNet32
50K
10K
10
467K
CIFAR100
ResNet18
10K
11.22M
C DETAILS OF EXPERIMENTS
C.I TABLE OF ALGORITHMS
Table summarrzss the algorithms implemented in Section
Algorithm
Description and Reference
SGD
Stechustic gradient method Robbins & Monno
1951
Xilain
Adam meehhad (Kingma & 2111
AdainW
Adam with decoupted weight decay Loshchilov Hutter 2017
AdGD
Adaptive Gradient Descent (Malitsky & Mishihanko 2020
AdaHessian
AdiHessian method (Yo 21211)
OASI8 Adaptive LR
Our proposed method with udaptive leurning rale
OASI8-Fixed LR
Our proposed methed fixed learning
OAS18 18-Mmmmntumm
Our proposed method with momentum
Table 4: Description of implemented algorithms
To display the optimality gap for logistic regression problems, used Trust Region (TR) New- ton Conjugate Gradient (Newton-CG) method (Nocedal & Wright (006) to find a w such that [VF(2)] 10-19 Hereafter, denote F(w) F(w"") the optimality gap, where we refer w" to the solution found by TR Newton-CG.
C.2 PROBLEM DETAILS
Some metrics for the image classification problems are given in Table
The number of parameters for ResNet architectures is particularly important, showcasing that OASIS is able to operate in very high-dimensional problems, contrary to the widespread belief that methods using second-order information fundamentally limited by the dimensionality of the parame- ter space.
C.3 BINARY CLASSIFICATION
In Section of the main paper, we studied the empirical performance of OASIS on binary classifi- cation problems in deterministic setting, and compared it with AdGD and AdaHessian. Here, present the extended details on the experiment.
C.3.1 PROBLEM AND DATA
As common practice for the empirical research of the optimization algorithms, LIBSVM datasets are chosen for exercise. Specifically, we chose 5 popular binary class datasets, ijcnnl, rcvl, news20, coviype and real-sim. Table summarizes the basic statistics of the datasets.
Datasets datasets/
available
at https: http://wwwcccc www.ww..i...ommm ntu wwwp://...e.........uooooom
35

---

Published as a conference paper at ICLR 2022
Table 6: Summary of Datasets.
Dataset
# feature
n (# Train)
# Test
% Sparsity
ijennl'
49,990
91,701
40,91
revl'
47,236
20,242
677,399
99.85
news20
1,355,191
14,997
4,999
99.97
covtype 54
435,759
145,253
77.88
real-sim" 20,958
54,231
18,078
99.76
dataset has default training/testing samples. datasct is randomly split by 75%-trainnn & 25%-testing.
Let (z,, y1) be a training sample indexed by E [n] == {1, .... n). where 2; Rd is a feature vector and y/ (-1,+1) is label. The loss functions defined in the forms
A
fi(w) = log(1 + e mio w)
2 1wl?
(84)
f((w) y/
(85)
1
where (84) is regularized logistic regression of particular choice of À > 0 (and we used À E {0.1/n, n, 10/n) in the experiment), and hence a strongly convex function; and (85) a non-linear least square loss, which is apparently non-convex.
The problem we aimed to solve is then defined the form
F(w) = Σ fi(11) min WER
1
(86)
==1
and we denote w" the global optimizer of 866 for logistic regression.
C.3.2 CONFIGURATION OF ALGORITHM
To better evaluate the performance the algorithms, we configured OASIS, AdGD and AdaHessian with different choices of parameters.
OASIS was configured with different values of 32 and a. where 32 can be any values in (0.95, 0.99, 0.995, 0.999} and can be any value in the set (10-3, 10-5, 10-1) (see Section C.5 where CASIS has a narrow spectrum of changes with respect to different values of a and 32). In addition, we adopted a warmstarting approach evaluate the diagonal of Hessian the starting
point Wo-
AdGD was configured with 12 different values of the initial learning rate, i.c. 170 {10-11 10010 1.0, 1.0].
AdaHessian was configured with different values of the fixed learning rate: for logistic regression, we used 12 values between 0.1 and 5; for non-linear least square, we used 0.01, 0.05, 0.1, 0.5, 1.0 and 2.0.
To take into account the randomness of the performance, we used 10 distinct random seeds to initialize wp for each algorithm, dataset and problem.
C.3.3 EXTENDED EXPERIMENTAL RESULTS
This section presents the extended results on our numerical experiments. For the whole experiments in this paper, we ran each method 10 times starting from different initial points.
For logistic regression, we show the evolution of the optimality gap in Figure and the ending gap in Figure 7 the evolution of the testing accuracy and the maximum achieved ones are shown in Figure and Figure respectively.
For non-linear least square, the evolution of the objective and its ending values are shown in Figure T0 the evolution the testing accuracy along with the maximum achived ones are shown in
Figure
36

---

Published as a conference paper at ICLR 2022
jenn]
news20
real-sim
Gint GICE:
13
12-1
13
30-4
007
10:44
16-1
206
300
10"1
1071
10
16.0
10-4
10'1
39.
222
200
662
122
420
222
43
020
206
100
0.5
200
400
38"
17"
10-1-
16"1
10-4
10.
10-
18-1
38
1077
283
200
200
20.8
220
Figure 6: Evolution of the optimality gaps of OASTS, AdGD and AdaHessian for lz-regularized Logistic regression: À == 0.1 (top row), x= (middle row), and À 10 right: ijennl, revl, news20, covtype and real-sim.
(bottom row). From left to
n
[cnn]
revl
now-20
covtype
real-sim
16:1
20
10-
Ehiit See-
364
16-
36
A200
A02 AMtraaa 0/8
1000
500
0P30
12:1
10.1
12.1
10"
12:1
10*
16
1>
440
Ad5 Saltroder AMB
A/50 Adcteoie IM0
ACD Malhuan CMt
440
Mativaii
10"
12
Figure 7: Ending optimality gaps of OASIS, AdGD and AdaHessian for fz-regularized Logistic regression: X = 0.1 (top row), À (middle row), and À 10 (bottom row). From left right: tjennl, revl. news20, covtype and real-sim
37

---

Published as a conference paper at ICLR 2022
licnn1
news20
075
85-
0.3
560
0.7
0.5
266
306
033
833
1.
280
206
200
489
230
200
300
400
106
200
300
400
039
389
330
300
0.5
130
200
300
0.8
6.5
617
6.7
065
6.00
055
300 206
300
489
330
200
30
430
106
700
300
30
500 330
320
300
320
400
Figure 8: Evolution of the testing accuracy of OASTS, AdGD and AdaHessian for fz-regularized Logistic regression: À (top row), À (middle row), and À (bottom row). From left to right: ijennl, revl, news20, covtype and real-sim.
n
covtype
534
0317
572
63479
0312
0331
144
0390
198
AGD
74P
ASD A011E20 0730
A00 Aurmia 209
875
1.1
0.77
872
Via
2.53
0866
6804
02144
509
05435
2114
Figure 9: Maximum testing accuracy of OASIS, AdGD and AdaHessian for erregularized Logistic regression: X = 0.1 (top row), À 1 (middle row), and X 10 (bottom row). From left to right: tjennl, revl. news20, covtype and real-sim.
38

---

Published as a conference paper at ICLR 2022
news20
1.35
1.2
1.3
2.50
1.25
0.8
1.25
0.9
0.75
100
200
320 432
103
200
100 400
120
203
300
400
100
200
302
403
300
200
320
405
[icnn1
rev1
nEw:20
covtype
real-sim
0.30
0.5
Figure 10: Evolution of the objective F(w) (top row) and the ending F(w) (bottom row) of CASIS, AdGD and AdaHessian for non-linear least square. From left to right: ijennl, revl, news20, covtype and real-sim.
[icrn]
news20
covtype
0.500
0.077
0.5
0.60
2400
0.5
0966
030
0.4
100
200 300
300
232
302 410
105
200
320 400
120
200
100 450
0
100
203
300
400
[|ann]
rov3
news20
covtype
real-sim
0191
5300
3.90
0.08
2.40
6905
3.50
6090
6190
0390
5707
0553
Figure 11: Evolution of the testing accuracy (top row) and the maximum accuracy (bottom row) of OASIS, AdGD and AdaHessian for non-linear least square. From left to right: ijennl, revl, news20, covtype and real-sim.
39

---

Published as a conference paper at ICLR 2022
ResNet20 CIFARIO With Weight Decay
ResNet20 CIFARIO Without Weight Decay
90
80
Test Accuracy
Test Test Accuracy
70
60
60
340
3se
50
AdaHessian
AdaHessian
OASI5 Fixed LR
40
Adam
OASIS Adaptive LR
Adam
DAS15 Adaptive LR
30
AdamiV
SGD
OASIS Momentum
30
SGD
20
40
60
100
120 140
160
20
40
60
80 Epochs
100
120 140 160
Epochs
AdaHessian
AdaHessian
100
Adam
AdamWW
DASIS Adaptive
OASIS
Momentum
10
Adam/W
Aoam
DASIS Adaptive LR OASI5
Momentum
SGD
SGD
F(w)
F(w)
10
10
0
20
40
60
80 Epochs
100
120
140
160
20
40
60
80 Epochs
100
120
140
160
Figure 12: ResNet20 CIFAR10 with and without weight decay. Final accuracy results can be
found in Table
C.4 IMAGE CLASSIFICATION
In the following sections, provide the results on standard bench-marking neural network training tasks: CIFAR10, CIFAR1 1 00, and MNIST.
C.4.1 CIFARIO
In our experiments, compared the performance of the algorithm described in Table 2 settings with and without weight decay. The procedure for choosing parameter values differs slightly for these two cases, so they presented separately. Implementations of ResNet20/32 architectures taken from AdaHessian repository
Analogously (Malitsky Mishchenko 2020). we also modify terms the update formula for Tjk || ww------llll
min 0z 17hh 2 (w)) -
T/k
Specifically, we incorporate parameter y into /1 + - and use more optimistic bound of L2 instead of 1 LL, which results in a slightly modified rule
The min /1 70,
[| [VF b2
In order find the best value for 7, include into hyperparameter tuning procedure, ranging the values in the set {1, 0.1, 0.05, 0.02, 0.01} (see Section C.5 where OASIS has narrow spectrum of changes with respect different values 7)).
Moreover, we used a learning-rate decaying strategy as considered in Yao et al. 2020) to have the same and consistent settings. In the aforementioned setting, 7} would be decreased by a multiplier on some specific epochs common for every algorithms (the epochs 80 and 120).
hhtp://gghhaaccmmmmmmpppaaaaaaaa
40

---

Published as a conference paper at ICLR 2022
ResNet32 on CIFARIO Weight Decay
ResNet32 on CIFAR10 Without Weight Decay
90
Test Accuracy
80
Test Accuracy
80
70
60
60
250
150
50
50
AdaHessian
DASIS Fixed LR
AdaHessian
DASIS Fixed LR
Adam
OASIS Adaptive
Adam
DAS15 Adaptive LR
30
AdamiV
OASIS Momentum
30
AdamW
OAS15 Momentum
SGD
20
60
100
120
160
20
40
80 Epochs
100 120 140 160
Epochs
Acaltsssinn
DASIS Fixed
AdaHlessian
DASIS Fixed LR
100
DASIS Adaptive
10
DASIS Adaptive
AdamNW
DASIS Momentum
AdamNW SGD
DASI5 Momentum
F(w)
F(w)
10-1
10
10-2
10
0
20
40
60
80 Epochs
100
120
140
160
60
80 Epochs
100
120
140
160
Figure 13: ResNet32 on CIFARI0 with and without weight decay. Final accuracy results can be found in Table
Table 7: Results of ResNet20/32 on CIFARIO with and without weight decay. Variant of our method with fixed learning rate beats or is on with others in the weight decay setting; while OASIS with adaptive learning rate produces consistent results showing a close second best performance without any learning rate tuning (for without weight decay setting).
Setting
ResNet20, WD
ResNet20, no WD
ResNet32, WD
ResNet32, no WD
SGD
92.02 + 0.22
89.92 + 0.16
92.85 + 0.12
90.55 + 0.21
Adam
90.46 + 0.22
90.10 0.19
91.30 + 0.15
91.03 + 0.37
AdamW
91.99 + 0.17
90.25 = 0.14
92.58 1 0.25
91.101
AdaHessian
92.03 + 0.10
91.22 0.24
92.77 T 0.26
92.19 0.14
OASIS-Adaptive LR
91.20 + 0.20
91.19 1.19=000 0.24
92.61 + 0.22
91.97 = 0.14
OASIS-Fixed LR
91.96 + 0.21
89.94 0.16
93.01 = 0.09
90.88 = 0.21
OASTS-Momentum
92.01 + 0.19
90.23 + 0.14
92.77 + 0.18
91.11 + 0.25
WD == Weight decay
41

---

Published as a conference paper at ICLR 2022
With weight decay: It is important to mention that due to variance in stochastic setting, the learning rate needs to decay (regardless of the learning rate rule is adaptive or fixed) to get convergence. One can apply adaptive learning rate rule without decaying by using variance-reduced methods (future work). Experimental setup is generally taken to be similar to the one used in (Yao et al. 2020). Parameter values for SGD, Adam, AdamW and AdaHessian are taken from the same source, meaning that learning rate is set to be 100.00010.01/..000 31 and B2 are set to be 0.9 and 0.999, For OASIS, due significantly different form of the preconditioner aggregation, we conducted small scale search for the best value of B2, choosing from the set (0.999, 0.99, 0.98, 0.97, 0.96, 0.95}, which produced values of 0.99/0.95 09.90/9000.99 00.98 for "Fixed LR," "Momentun" and adaptive variants correspondingly for ResNet20 and for "Fixed LR," "Momentum" and adaptive variants correspondingly for ResNet32, while 31 for momentum variant is still set to 0.9. Additionally, in the experiments with fixed learning rate, it is tuned for each architecture, producing values 0.1/0.1 for ResNet20 and 0.1/0.1 for ResNet32 for "Fixed LR" and "Momentum" variants of OASIS correspondiigly. For the adaptive variant, 7 is set to 0.1/1.0 for ResNet20/32. a is set to 0.1 for all OASIS variants. We train all methods for 160 epochs and for all methods. With fixed learning rate employ identical scheduling, reducing step size by a factor of 10 at epochs 80 and 120. For the adaptive variant scheduler analogue is implemented, multiplying step size by p at epochs 80 and 120, where p is set be 0.1/0.3 for ResNet20/32. Weight decay value for all optimizers with fixed learning rate is 0.0005 and decoupling for OASIS is done similarly to Adam W and AdaHessian. For adaptive OASIS weight decay is set to 0.001 without decoupling, Batch size for all optimizers is 256.
and, where they are used,
10.99/0.98 /0.98
Without weight decay: In this setting we tune learning rate for SGD, Adam, AdamW and AdaHessian, obtaining the values 10/1500005 15.50/005/// / /..25 and 2.115/00.11 /0.01 /0.25 for ResNer20/32 accord- ingly. Where relevant, 31, 32 are taken to be 0.9, 0.999. For OASIS we still try to tune 8g, which produces values of 0.999 for ResNet20 and adaptive case of ResNet32 and 0.99 for "Fixed LR," "Momentum" in the case of ResNet32; for the momentum variant 31 = 0.9. Learning rates are 0.025 /0.05 for ResNet20 and 0.025/0.1 for ResNet32 for "Fixed LR" and "Momentum" variants of OASIS correspondingly. For adaptive variant y is set to 0.01/0.01 for ResNet20/32. a is set to 0.1 for adaptive OASIS variant, while hyperoptimization showed, that for "Fixed LR" and "Momentum" a value of 0.01 can be used. We train all methods for 160 epochs and for all methods with fixed learning rate employ identical scheduling, reducing step size by factor of 10 at epochs 80 and 120. For the adaptive variant scheduler analogue is implemented, multiplying step size by p at epochs 80 and 120, where p set to be 0.1/0.1 for ResNet20/32. Batch size for all optimizers is 256.
Finally, all of the results presented are based on 10 runs with different seeds, where parameters are chosen amongst the best runs produced at the preceding tuning phase.
All available results can be seen in Table 7 and Figures 12 and NVIDIA V100 GPU.
13
We ran our experiments on an
C.4.2 CIFAR100
Analogously to CIFARIO, we do experiments in settings with and without weight decay. In both cases we took best learning rates from the corresponding CIFAR10 10 experiment with ResNet20 architecture without any additional tuning, which results in 0.1 for all. 33 is set to 0.99 in the case with weight decay and to 0.999 in the case without it. ResNet18 architecture implementation is taken from a github repository 8 We train all methods for 200 epochs. For all optimizers learning rate is decreased (or effectively decreased in case of fully adaptive DASIS) by a factor of at epochs 60, 120 and 160.
All of the results presented are based off of 10 runs with different seeds. All available results can be seen in Table and Figure 14] We ran our experiments on an NVIDIA V100 GPU.
C.4.3 MNIST
Similar to the previous results, we ran the methods with 10 different random seeds. We considered Net DNN which has 2 convolutional layers and fully connected layers with ReLu non-linearity, mentioned in the T In order to tune the hyperparameters for other algorithms, we considered the
set of learning rates {10'. 10 10 2 10 30. For OASIS, we used the set of {10-1, 10 - and the
42

---

Published as a conference paper at ICLR 2022
ResNet18 on CIFAR100 Without Weight Decay
ResNet18 on CIFARI00 With Weight Decay
80
70
60
Accuracy
60
Test Accuracy
50
40
310
120
206
30
30
AdaHessian
DASIS Fixed LR
20
Adam
DASI Adaptive LR
20
Adaptive
AdamW
Momentum
Adami
OASIS Momentum
10
SGD
SGD
0
25
50
75
100 Epochs
125 150 175
200
25
50
75
100 125 150 175 200 Epochs
AcaHessian
Adam
DASIS Adaptive
Adam
DASIS Adaptive LR
100
AdamW
OASIS Momentum
10
AdamW
Momentum
SGD
SGD
F(w)
10
F(w)
10-1
10-2
10-2
10-3
10
0
25
50
75
100 Epochs
125
150
175
200
25
50
75
100 Epochs
125
150
175
200
Figure 14: ResNet18 8 CIFAR100 with and without weight decay. Final accuracy results can be found in Table
Table Results ResNet18 on CIFAR100. Simply transferring parameter values from similar task with ResNet20 on CIFARIO predictably damages performance of optimizers compared their heavily tuned versions. Notably, in the setting without weight decay performance of SGD and Adam became unstable for different initializations, while adaptive variant of OASIS produces behaviour robust to the choice of the random seed.
Setting
ResNer18, WD
ResNet18, no WD
SGD
76.57 + 0.24
70.50 + 1.51
Adam
73.40 + 0.31
67.40 0.91
AdamW
72.51 0.76
67.96.0..0
AAdHHsssian
75.71
70.16:40.3
OASIS OASas-Adeptive LR
76.93 + 0.22
74.13 + 0.20
OASIS-Fixed LR
76.28 0.21
70.18 + 0.76
OASIS-Momentum
76.89 + 0.34
70.93 + 0.77
WD = Weight decay
43

---

Published as a conference paper at ICLR 2022
Net DNN MNIST With Weight Decay
Net DNN MNIST Without Weight Decay
100
98
95
Test Accuracy
Test Accuracy
96
94
85
92
90
80
88
75
Adam
OASIS Adaptive LR
Adam
OASIS Adaptive LR Momentum
AdamW
Momentum
86
70
SGD
84
SGD
2
4
6
8
10
2
6
8
10
Epochs
Epochs
AdaHesssin
OASIS Fixed
AdaHessian
OASIS
10
Adam
OASIS Adaptive LR
Adam
OASIS - Adaptive LR Momentum
AdamW
Momentum
SGD
SGD
F(w)
F(w)
10-1
10
2
4
8
10
4
6
8
10
Epochs
Epochs
Figure 15: Net DNN on MNIST with and without weight decay. Final accuracy results can be found T
Table 9: Results of Net DNN on MNIST. Gradient momentum usage seems improve results short
trajectories for all methods, including OASIS.
Setting
Net DNN, WD
Net DNN, no WD
SGD
98.37 = 0.45
98.86 + 0.18
Adam
98.92 = 0.14
98.90 = 0.13
Adam W
98.76 + 0.13
98.92 + 0.13
AdaHessian
98.82 = 0.16
98.86 = 0.16
OASIS-Adaptive LR
97.93 + 0.27
97.95 + 0,29
OASIS-Fixed LR
97.24 + 3.97
98.09 + 1.36
OASIS-Momentum
98.78 = 0.22
98.89 = 0.10
WD Weight decay
set for truncation parameter E 10-2). As clear from the results shown in Figure 15 and T OASIS with momentum has the best performance in terms of training (lowest loss function), and and is comparable with the best test accuracy for the cases with and without weight decay, It is worth mentioning that OASIS with adaptive learning rate got satisfactory results with lower number of parameters, which require tuning, which vividly important, especially in comparison to first-order methods that are sensitive to the choice of learning rate. We ran our experiments on Tesla K80 GPU.
C.5 SENSITIVITY ANALYSIS OF OASTS
is worth noting that we designed and analyzed OASIS for the deterministic setting with adaptive learning rate. is safe to state that sensitive tuning is required in the deterministic setting (the learning rate is updated adaptively, and the performance of CASIS is completely robust even if the rest of the hyperparameters not perfectly hand-tuned); Figures 16 and
44

---

Published as a conference paper at ICLR 2022
ijcnn1
10
10-1
0.95-1e-D5
10
0,95-1e-07
0.99-0.001
10 3
10
0,99-1e-05
0.995-0.001
10
10
0.995-1e-05
0.995-1e-07
10-7
F(w)
10
0.999-0.001
F(w)
0.999-1e-0
10-9.
10-5
10-11
10-6
10
10
100
200
300
400
100
200
300
400
Number of Effective Passes
Number of Effective Passes
news20
covtype
10-1
10
10-1
10-3
F(w) Ft
F(w) F²
10 10
10-5
10
10-2
10-7
100
200
300
400
100
200
300
400
Number of Effective Passes
Number of Effective Passes
Figure 16: Sensitivity of OASIS w.r.t. (82, a), Deterministic Logistic regression.
45

---

Published as a conference paper at ICLR 2022
ijcnn1
rcv1
1.200
0,95-0.001
1.2
1.175
0,95-1e-05
0.95-1e-07
1.1
0.99 0.001
1.150
0.99-1e-05
0.99-1e-07
1.0
1.125
0,995-0.001
0,995-1e-05
0.9
F(w)
1.100
0.995-1e-07
0.999-0.001
1.075
0.999-1e-07
1.050
0.7
1.025
0.6
1.000
0.5
100
200
300
400
0
100
200
300
400
Number of Effective Passes
Number of Effective Passes
news20
covtype
1.20
1.2
1.15
1.1
1.10
1.0
1.05
F(w)
0.9
F(w)
0.8
1.00
0.7
0.95
0.6
0.90
0.5
100
200
300
400
100
200
300
400
Number of Effective Passes
Number of Effective Passes
Figure 17: Sensitivity of OASIS w.r.t (32, a). Deterministic Non-linear Least Square.
46

---

Published as a conference paper at ICLR 2022
Sensitivity Analysis (LR) OASIS
Sensitivity Analysis (LR)- SGD
100
100
sgd_1=0.01
5gd 100.055
80
80
sad In0.05
Test Accuracy
Test Accuracy
sgd Io._620
OASIS Jr:0.005
DASIS Jr:001
60
DASI5_1r:0.025
60
Fgd In0.112
sgd 9-0.
0ASi5_/r0000
sgd Ir0.3
40
OASI5 Jn:0.1
40
00._
OASI
sad ln:10
5.:022
OASIS
-9d_ik2.0
20
Ir:04
20
DASIS Jn0.5
0n:25_
0 0
50
100
150
0
50
100
150
Epochs
Epochs
Figure 18: Sensitivity of OASIS vs. SGD w.r.t learning rate 7, CIFAR10 on ResNet20.
We also provide sensitivity analysis for the image classification tasks. These problems in stochastic setting, and we need to tune some of the hyperparameters in OASIS. IS. As is clear from the following figures, OASIS robust with respect to different settings of hyperparameters, and the spectrum of changes is narrow enough; implying that even the hyperparameters aren't properly tuned, we still get acceptable results that are comparable other state-of-the-arr first- and second-order approaches with less tuming efforts. Figure 18 shows that OASIS is robust for different values of learning rate (left figure), while SGD completely sensitive with respect to learning rate choices. One possible reason for this is because OASIS uses well-scaled preconditioning, which scales each gradient component with regard to the local curvature at that dimension, whereas SGD treats all components equally.
adaptive learning rate in the stochastic setting, extra hyperparameter, y, is used OASIS (similar to (Malitsky & Mishchenko, (020)). Figure 19 shows that OASIS is also robust with respect different values of 7 (unlike the study in (Malitsky & Mishchenko 2020)). The aforementioned figures are for CIFAR1 0 dataset on the ResNet20 architecture; the same behaviour observed for the other network architectures.
Furthermore, in order
Finally, we show here that the performance of OASIS is also robust with respect to different values of B2. Figure 20 shows the robustness of OASIS across range of values. This figure for CIFAR100 dataset on the Re Restet1 architecture.
47

---

Published as a conference paper at ICLR 2022
Sensitivity Analysis (y)- OASIS
100
80
Test Accuracy
60
OASIS OASIS_y:0.01
40
OASIS OASIS_y:0.02
OASIS _=51__v00.05
20
OASIS __00011
OASIS y:1.0
0
0
50
100
150
Epochs
Figure 19: Sensitivity of OASTS w.r.t 7, CIFAR1 0 on ResNet22.
CIFAR100-ResNet18
100
80
Test Accuracy
60
40
OASIS_8:0.97
OASIS_B:0.00
20
OASIS_B:0.99
0ASIS_8:0.999
100
200
Epochs
Figure 20: Sensitivity of OASIS w.r.t. 32, CIFAR100 ResNet18.
48


Reviews:
[{"review_id": "xndVLpovCjP", "reviewer": "Reviewer_QUCj", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: \n- The paper considers a fundamental problem in ML, i.e., minimizing a separable function.\n- The algorithm and its convergence are proven for many cases, i.e., deterministic, stochastic, convex, non-convex.\n- Empirical evidence is given that the algorithm outperforms comparable approaches like AdaHessian, etc.\n- No need to tune a learning rate since the step lengths are determined by the curvature of the function. This can be really a huge advantage in the stochastic setting, i.e., in deep learning.\n\nWeakness:\n- The empirical evidence/experiments are rather limited. \n  Deterministic case: Only two experiments are provided (logistic regression, non-linear least-squares) and only two data sets. Furthermore, a comparison to other minimization methods would be very beneficial in this case, and not only to AdaHessian and AdGD. (Yes, it is stated in the paper that comparison to only diagonal preconditioners is made but in general, there are many more methods to solve this case, e.g., quasi-Newton methods or trust region Newton-CG methods which are also used for computing the optimum in the provided code. These methods make use of the same information as the presented method and hence, a comparison to these methods would also be useful for a better global picture.) \n\n  Stochastic case: Again, only a very limited number of experiments is provided here. Having not to tune the learning rate is an enormous plus here and it would be nice to verify the algorithm's robustness on a number of different problems/nets. The experiments suggest that OASIS would be a viable replacement for SGD, Adam, etc. But for such a bold statement, more experiments are needed.", "summary_of_the_paper": "The paper designs and analyses an algorithm for minimizing a separable function. It provides deterministic as well as stochastic versions, which either fully compute the gradient or sample it. The algorithm estimates the diagonal elements of the Hessian via Hessian-vector products. The algorithm makes use of this information for finding a better search direction and the step length, eliminating the need for a line search. It provides convergence guarantees and a number of experiments on classical ML problems as well as on deep nets.", "summary_of_the_review": "I like the paper, the algorithm, and its versatility. Especially that one does not need to tune a learning rate can be very beneficial. I did not fully read the convergence proofs though they seem sound. According to theory and experiments, one should always use this algorithm. It would be nice to justify this claim by a more comprehensive study, e.g., more problems, datasets, and other algorithms in the deterministic case and more nets and data sets in the stochastic setting. Only then one can tell if it is superior to state-of-the-art approaches. If such experiments were provided in the paper I would have given a higher score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "lK1Yj_g1Iph", "reviewer": "Reviewer_doAo", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "------ Pros ------\n\nThe paper has the following strengths.\n\n1) Very well written paper providing a clear motivation for the problem considered.\n\n2) The theoretical results involving the convergence analysis of the method are rigorous, and cover both convex and nonconvex settings.\n\n3) The empirical evaluation is extensive and provides a good indication of how the method performs in practice.\n\n------ Cons ------ \n\nThe paper has the following weaknesses. \n\n1) There is currently not much discussion on the interpretation of the bounds appearing in the convergence analysis. \nFor instance, how do these results compare with those for existing second-order methods (e.g., AdaHessian)? \n\n2) It would have been helpful to have provided some kind of proof sketch of the theoretical results, or atleast an \noverview of the key steps which I believe might be common to more than one theorem. At the moment, no such explanation is \nprovided for any of the theoretical results. \n \n------ Further remarks -------\n\n1) The setup in Fig. 1 is really not clear to me. What is meant by number of samples (x axis of left plot)? Is there an underlying optimization problem considered here such as a quadratic function with matrix A? Some more detailed explanation on the experimental setup considered for the figure will be very helpful.\n\t\n2) In Fig. 2, the parameter $\\lambda$ is not clearly defined, I believe this occurs much later in the experiments section.\n\t\n3) In eq. (6), is the matrix $D_k$ formed by just generating a Rademacher $z$ and forming $D_k = z \\circ \\nabla^2 F(w_k) z$? Because in the AdaHessian paper, they also consider a spatial averaging step for better estimation of the Hessian diagonal. Also, should $z$ be $z_k$ as in eq. (8) later?\n\t\n4)  As mentioned on pg 4 in the discussion on literature for adaptive LR, the present paper draws upon ideas from the literature on first order methods for adaptive LR. So couldn't one do the same analysis for AdaHessian for adaptive LR? \n\t\n5) It wasn't clear to me why AdaHessian (eq. 6 and 7) doesn't approximate the diagonal well, while  OASIS (eq. 8 and 9) does a better job. \nBecause we see a (temporal) average in eq. 7 as well, which means AdaHessian should also smooth out the Hessian noise over  iterations. Is there any conceptual reason behind this?\n\t\n6) In Section 3.2, shouldn't the distribution from which the sets $\\mathcal{I}_k, \\mathcal{J}_k$ are sampled be specified (e.g., uniformly at random)? Or is it the case that the conditions on the distribution are subsumed by assumptions 4.14-4.16?. Also, in assumption 4.16: the sentence ''where the samples $\\mathcal{I}$ are drawn independently'' should be removed since there is a single random variable $\\mathcal{I}$. \n\t\n7) Since $z_k$ is random, one would imagine that this randomness is accounted for in the convergence analysis, which doesn't seem to be the case. For instance the theorems 4.6, 4.9 seem to be worst case bounds. Moreover, the bound in theorem 4.9 depends on $\\hat{D}_k$ which is a random variable. This point needs further clarification.\n\t\n8) In theorem 4.17, its better to write $\\eta_k = \\eta$ for consistency of notation.\n\n9) Both theorems 4.17, 4.18 show convergence to neighborhoods of stationary points, and not to the stationary points themselves. There is a discussion after theorem 4.18 regarding this aspect, but it seems a bit strange why this (e.g. decaying learning rate) is not accounted for in the analysis to begin with?\t", "summary_of_the_paper": "The paper presents a novel adaptive second order method: ''OASIS'', for large scale optimization problems (convex and nonconvex). The search direction is obtained by preconditioning the gradient information with a matrix obtained by approximating the Hessian diagonal matrix (via Hutchinson's method with a momentum term). The learning rate is updated adaptively by approximating the Lipschitz smoothness parameter. On the theoretical front, convergence analysis is provided for the adaptive learning rate case, for the convex and strongly convex setups. Similar analysis is also provided for the fixed learning rate (LR) case, for the strongly convex and nonconvex settings. Finally, extensive empirical results are provided which show that the proposed method achieves comparable, and sometimes better results than other existing methods.", "summary_of_the_review": "The paper is written in a very clean manner, and is easy to follow. Sufficient background is provided in the introduction which gives the reader a good context to understand the problem setting and contributions. The preconditioning step is a modification of an existing method AdaHessian, and the adaptive LR part builds on techniques used for deriving adaptive LR rules for first order methods (Mishchenko and Malitsky 2020). So the novelty aspect is a bit limited in that respect. The theoretical results are outlined rigorously, although it is not clear what is the novelty of the theoretical results compared to those for other second order methods. The empirical evaluation is quite extensive and satisfactory in my view. I am giving it a 6 at the moment since I have other comments (in ''Further remarks'') which I hope can be addressed during the rebuttal phase.\n\n------------- Post rebuttal ---------\n\nAs mentioned in the comments, I am satisfied with the author's response to my concerns and I am happy to increase my score to 8.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "QsmUc3Nq_OR", "reviewer": "Reviewer_524y", "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": "The paper is nicely written and easy-to-follow. The topic on how to effectively leverage the Hessian-vector oracle in large scale machine learning tasks is definitely important and interesting. \n\nFor the main ideas, the authors show in Figure 1 that OASIS approximates the diagonal of Hessian much more accurate than the Hessian momentum in AdaHessian, which is the main point made in the paper (I have the feeling that the Hessian momentum is not solely for approximation? like the first-order momentum vector may not be an accurate approximation for the gradient vector, but is effective for acceleration). Another point is that OASIS incorporates the adaptive stepsize in (Mishchenko & Malitsky, 2020), which allows it to adapt to the local Lipschitz constant (wrt a weighted Euclidean norm) and thus reduces the tuning effort. However, it seems to me that these ideas are a bit straightforward and not particularly novel. From my perspective, AdaHessian is a ''diagonal-Hessian-variant'' of Adam and OASIS is the corresponding variant of RMSProp. It seems that the adaptive learning rate can also be incorporated into AdaHessian by choosing a different weighted norm.\n\nFor the theory part, I appreciate the thorough analysis of OASIS under various settings. However, I was hoping for more insightful discussion on these results, such as how the theorems would suggest a better parameter choice. Currently, they are only convergence guarantees, which could be far from the practical performance. The theorems in Section 4.1 generalize the results in (Mishchenko & Malitsky, 2020) in the deterministic setting while there seems to be no theoretical advantage of such generalization (BTW, is there any bound on the scale of $Q_k$ in Theorem 4.6? It seems that it can be of the order $O(k)$ which kills the convergence).  \n\nFor the empirical results, the authors considered various machine learning tasks and the deviation is also plotted in the figures, which are appreciated. However, the improvement in most of the results seems marginal to me, and thus may not be appealing to practitioners especially since the Hessian-vector oracle is around twice as expensive as the gradient oracle (for neural nets). Moreover, OASIS still requires a learning rate scheduler as shown in the CIFAR results, which makes the statement \"Our methodology does not require the tedious task of learning rate tuning\" not well-supported.\n\nMinor comments:\n- Equation (7) is not centered.\n- Typo in the citation \"Adaptive gradient descent without descent.  In 37th International Conference on Machine Learning (ICLM 2020), 2020\"\n- I think Lemma A.1 is covered by Theorem 2.1.5 in Nesterov's updated book \"Nesterov, Y. (2018). Lectures on convex optimization (Vol. 137). Berlin, Germany: Springer International Publishing\".", "summary_of_the_paper": "This work proposes OASIS, a second-order method which approximates the diagonal of Hessian matrix and uses the information to rescale the gradient vector. The main difference between OASIS and the existing method AdaHessian (Yao et al., 2020) is on the ways they approximate the diagonal of Hessian, that AdaHessian uses a formula similar to Adam and OASIS uses an exponential average. Moreover, OASIS also incorporates the adaptive stepsize in (Mishchenko & Malitsky, 2020). The authors established the convergence guarantees of OASIS under various settings including convex, strongly convex and nonconvex cases, using various learning rate schedulers such as the adaptive learning rate, fixed learning rate and line search. Empirical results on various machine learning tasks are provided to evaluate OASIS.", "summary_of_the_review": "I appreciate the authors' efforts on the comprehensive analysis and empirical evaluations of the proposed OASIS. The paper is also very well written. However, both the theoretical and practical results seem incremental to me. The construction in OASIS also seems a bit straightforward. Moreover, OASIS still requires parameter tuning in some of the experiments, and thus is not \"fully adaptive\". ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a novel approximate second order optimization method for convex and nonconvex optimization problems. The search direction is obtained by preconditioning the gradient information with a diagonal approximation of the Hessian via Hutchinson's method and exponential averaging. The learning rate is updated using an estimate of the smoothness parameter.

The merit of the paper has to be evaluated from the theoretical and empirical point of view.

From the internal discussion, the reviewers agreed that the new algorithm is a mix a known methods, mainly present in AdaHessian, with a small tweak on the exponential average. Moreover, the theoretical guarantees do not seem to capture the empirical performance of the algorithm nor they provide any hint on how to set the algorithm's hyperparameters. For example, in Theorem 4.6 the optimal setting of $\beta_2$ is 1. That said, the most important theoretical contribution seems to lie in the fact that AdaHessian did not have any formal guarantee. Hence, this paper is the first one to show a formal guarantee this type of algorithms.

From the empirical point of view, the empirical evidence is very limited for the today standards in empirical machine learning papers. The reviewers and me do not actually believe that the proposed algorithm dominates the state-of-the-art optimization algorithms used in machine learning. However, in the internal discussion we agreed that the algorithm has still potential and it should be added to the pool of optimization algorithms people can try.

Overall, considering the paper in a holistic way, there seems to be enough novelty and results to be accepted at this conference.

That said, I would urge the authors to take into account reviewers comments (and I also add some personal ones here). In particular, a frank discussion of current theoretical analysis and empirical evaluation is needed.

Some specific comments:
- AdaGrad was proposed by two different groups at COLT 2010, so both papers should be cited. So, please add a citation to: 
McMahan and Streeter. Adaptive bound optimization for online convex optimization. COLT 2010.
- Remark 4.7, second item: Neither Reddi et al.(2019) nor Duchi et al. (2011) *assume* bounded iterates, that must be proved not assumed. Instead, they explicitly project onto a domain that they assumed to be bounded.
- The convergence of the gradient to zero does not imply convergence to a critical point. To prove convergence to a critical point you should prove that the iterates converge, that in general is false even for lower bounded functions. Indeed, consider $f(x)=log(1+exp(-x))$, the iterates would actually diverge while the gradient still go to zero.
Decision: Accept (Poster)