Apollo: An Adaptive Parameter-wised Diagonal Quasi-Newton Method for Nonconvex Stochastic Optimization
Authors: Xuezhe Ma
Venue: ICLR 2022 Submitted (2022)
Keywords: Optimization for Neural Networks
Optimization for Representation Learning
Stochastic Optimization
Nonconvex
Quasi-Newton
Optimization for Deep Learning

Abstract: In this paper, we introduce Apollo, a quasi-Newton method for nonconvex stochastic optimization, which dynamically incorporates the curvature of the loss function by approximating the Hessian via a diagonal matrix. Importantly, the update and storage of the diagonal approximation of Hessian is as efficient as adaptive first-order optimization methods with linear complexity for both time and memory. To handle nonconvexity, we replace the Hessian with its rectified absolute value, which is guaranteed to be positive-definite. Experiments on three tasks of vision and language show that Apollo achieves significant improvements over other stochastic optimization methods, including SGD and variants of Adam, in term of both convergence speed and generalization performance.

Under review as a conference paper at ICLR 2022
APOLLO: AN ADAPTIVE PARAMETER-WISE DIAG- ONAL QUASI-NEWTON METHOD FOR NONCONVEX STOCHASTIC OPTIMIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, we introduce APOLLO, a quasi-Newton method for nonconvex stochastic optimization, which dynamically incorporates the curvature of the loss function by approximating the Hessian via diagonal matrix. Importantly, the up- date and storage the diagonal approximation of Hessian is as efficient as adaptive first-order optimization methods with linear complexity for both time and memory. To handle nonconvexity, we replace the Hessian with its rectified absolute value, which is guaranteed to be positive-definite Experiments on three tasks of vision and language show that APOLLO achieves significant improvements over other stochastic optimization methods, including SGD and variants of Adam, in terms of both convergence speed and generalization performance. The implementation of the algorithm is available anonymous link.
INTRODUCTION
Nonconvex stochastic optimization of core practical importance many fields of machine learning, in particular for training deep neural networks (DNNs). First-order gradient-based optimization algorithms, conceptually attractive due to their linear efficiency on both the time and memory complexity, have led tremendous progress and impressive successes. A number of advanced first-order algorithms have emerged over the years to pursue fast and stable convergence, among which stochastic gradient descent (SGD) (Robbins & Monro 1951;
al.) 1998), equipped with momentum (Rumelhart et al. 1985 Qian 1999 Bottou & Bousquet, 2008). has stood out for its simplicity and effectiveness across a wide range of applications (Hinton & Salakhutdinov 2006, Hinton et al. 2012 Graves, 2013). However, one disadvantage of SGD is that the gradients in different directions are scaled uniformly, resulting in limited convergence speed and sensitive choice of learning rate, and thus has spawned lot of recent interests in accelerating SGD from the algorithmic and practical perspectives.
Recently, many adaptive first-order optimization methods have been proposed to achieve rapid training progress with sementtwwise sealed learning rates, and we can only mention a few here due to space limits. In their pioneering work, Duchi et al. (2011) proposed AdaGrad, which scales the gradient by the square root of the accumulative square gradients from the first iteration. While AdaGrad works well for sparse settings, its performance significantly degrades for dense settings, primarily due to the monotonic increase of the accumulation. Subsequently several methods have been proposed with the intuition limit the accumulation in particular exponentially reduce the weight of earlier iterations. Notable works incorporating this method are RMSProp (Tieleman & Hinton| 2012). AdaDelta (Zeiler 2012). and Adam (Kingma & Ba 2015), among which Adam has become the default optimization algorithm across many deep learning applications because its fast convergence speed and relatively consistent selections of hyper-parameters (Ruder, 2016 Zhang et al. (2020). However, it has been observed that these adaptive optimization methods may converge to bad/suspicious local optima, resulting in worse generalization ability than their non-adaptive counterparts (Wilson et al. 2017), or fail converge due unstable and extreme learning rates (Luo et al.) 2019).
small window of past iterations, and
Buasi-Newton methods have been widely used in solving convex optimization problems, due to their efficient computation and fast convergence rate (Broyden] 1967, Dennis & Moré 1977). However, the stochastic, high-dimensional and nonconvex nature of many machine learning tasks, such as

---

Under review as a conference paper at ICLR 2022
training deep neural networks, has rendered many classical quasi-Newton methods ineffective and/or inefficient (Keskar& & Berahas [016 Wang et al., 2017: Yao et al., 2020). Indeed, in many natural language processing (NLP) and computer vision (CV) tasks (He et al. 2016 Ma & Hovy 2016 Luo et al. 2019), SGD (with momentum) is chosen as the optimizer, benefiting from its stable and efficient training and outstanding generalization.
In this work, we develop APOLLO, quasi-Newton method for nonconvex stochastic optimization to simultaneously tackle the aforementioned challenges of stochastic variance, nonconvexity and inefficiency. Algorithmically, APOLLO dynamically incorporates the curvature of the objective function with diagonally approximated Hessian. It only requires first-order gradients and updates the approximation of the Hessian diagonally so that it satisfies parameter-wise version of the weak secant condition (Wolfe 1959). To handle nonconvexity, we replace the Hessian with its rectified absolute value, the computation of which is also efficient under our diagonal approximation, yielding an efficient optimization algorithm with linear complexity for both time and memory ($3) Experimentally, through three tasks on CV and NLP with popular deep neural networks, including ResNets (He et al.) 2016), LSTMs (Hochreiter & Schmidhuber 1997) and Transformers (Vaswani al. 2017), we demonstrate that APOLLO significantly outperforms SGD and variants of Adam, in terms of both convergence speed and generalization performance ($4)
2 BACKGROUNDS
In this section, we set up the notations on nonconvex stochastic optimization, briefly review the (quasi-) Newton methods, and discuss the problems of applying quasi-Newton methods to nonconvex stochastic optimization that we attempt to study in the rest of the paper.
2.1 NONCONVEX STOCHASTIC OPTIMIZATION
In this paper, we consider the following nonconvex stochastic optimization problem:
min S(0) = E[]
BER
where : Rd x RD + R. is a continuously differentiable (and possible nonconvex) function, 0 E Rd denotes the parameter be optimized, R" denotes a random variable with distribution function P. and E[-] denotes the expectation w.r.t r. Intuitively, I incorporates noises in f. leading to a stochastic objective function. special case of (T) that arises frequently in machine learning the empirical risk minimization problem:
1 N Σ 4(0)
min 1(0) R
where 4 Rd > R is the loss function corresponding to the i-th data, and N is the number of data samples that is assumed to be extremely large. Objective functions may also have other sources of noise than data subsampling, such as dropout (Srivastava et al. 2014) in deep neural networks.
this work, we consider a setting of decoupled parameters: 0 (00), / i,..., L}. Intuitively, under this setting the parameter 0 is decoupled into sequence of parameters serving different functionalities. For example, in neural network training the parameters of neural network can be naturally decoupled into the parameters of different layers or modules.
Decoupled Parameters.
2.2 NEWTON AND QUASI-NEWTON METHODS
Newton's 's method usually employs the following updates to solve 1I]
θt+1 = 0, - H.' gt
(3)
where St = (0.) the gradient at O2 and H,, V2 f(.) is the Hessian matrix. The convergence rate of Newton's 's method is quadratic under standard assumptions (Nocedal & Wright 2006). How- ever, major challenges with this method are i) the expensive computation of the inverse Hessian at every iteration and the corresponding quadratic memory complexity; and ii) the limitation to convex functions (nonconvexity results in negative curvature of H, and misleads the update directions).
A standard alternative to Newton's method is class of quasi-Newton methods, which have been
widely used in solving convex deterministic optimization problem:
0 0, 1/p B, 9t
2

---

Under review as a conference paper at ICLR 2022
where ni is the stepsize (a.k.a learning rate), B, is approximation to the Hessian matrix (2.)
at l2. which is updated based on the well-known secant equation:
B = argmin |B B,ll
B
(5)
s.t. B V (secant equation)
where Sr = 01+1-06 and = 9t+1 9t. B++1 is, in the sense of some matrix norm, the closest to Br
among all symmetric matrices that satisfy the secant equation. Each choice of the matrix norm results in different update formula, such as DFP (Davidon 1991 Fletcher 1987) and BFGS (Broyden 1970, Fletcher, 1970; Goldfarb 1970; Shanno 1970). The popularity of this method due the fact that only the gradient of the objective function is required at each iteration. Since no second derivatives (Hessian) are required, quasi- Newton methods are sometimes more efficient than Newton's 's method, especially when the computation of Hessian is expensive. To further reduce memory cost, one seminal work is the limited memory BFGS (L-BFGS) (Liu & Nocedal 1989; Byrd et al. 1995) that achieves desirable linear computational and memory complexity by approximating the Hessian as a series of sum of first order information from previous iterations.
2.3 PROBLEMS OF QUASI-NEWTON METHOSS
Despite their impressive successes convex deterministic optimization, quasi-Newton methods suffer from their own problems in more challenging scenarios. In this section, we mainly discuss three problems preventing quasi-Newton methods from being applied the scenario of large- scale nonconvex stochastic optimization. Due to these problems, no quasi-Newton methods (to our best knowledge) designed for nonconvex optimization consistently outperform adaptive first- order algorithms w.r.t convergence speed and generalization performance. The main goal of this work is to algorithmically design and experimentally demonstrate novel quasi-Newton method, in hope of improving the convergence speed and generalization performance of nonconvex stochastic optimization eventually.
Stochastic Variance. One challenge of quasi-Newton methods nonconvex stochastic optimiza- tion ① is the variance introduced by the stochastic nature of the problem. At each iteration, only the stochastic gradient Sr is available, which is an unbiased estimation of the gradient (0+) and may lead to an erroneous approximation of Hessian (Byrd et al. 2011).
Nonconvexity.
Another key challenge in designing such quasi- Newston methods lies the difficulty of B, in (5). due to the nonconvexity of the objective function.
of preserving the What is worse is that performing line search is infeasible in the stochastic setting, due to the presence of noise in the stochastic gradients |Wann et al.) 2017).
Computational and Memory Efficiency. Even though quasi-Newton methods are more efficient than Newton's 's method, the time and memory complexities are still relatively large compared with adaptive first-order methods. For instance, L-BFGS requires to store first-order information from m previous iterations with commonly m 5, which is still too expensive for deep neural networks con- taining millions of parameters. Moreover, adapting guasi-Newtor methods to nonconvex stochastic optimization probably introduces additional computation, further slowing down these methods.
3 ADAPTIVE PARAMETER- WISE DIAGONAL QUASI-NEWTON
With the end goal of designing an efficient quasi-Newton method to solve the problem in ( in mind, we first propose to approximate the Hessian with a diagonal matrix, whose elements are determined by the variational approach subject to the pire weak secant equation 3$3.
Then, we explain our stepsize bias correction technique to reduce the stochastic variance in $3.2 To handle nonconvexity, we directly use the rectified absolute value of the diagonally approximated Hessian as the preconditioning of the gradient ($3.)). The initialization technique of APOLLO allows to eliminate one hyper-parameter ($3.4). At last, we provide theoretical analysis of APOLLO's ''s convergence in both convex optimization and nonconvex stochastic optimization ($3.5). The pseudo-code is shown in Algorithm
3.1 QUASI-NEWTON METHODS WITH DIAGONAL HESSIAN APPROXIMATION
As discussed in Bordes et al. (2099) designing an efficient stochastic quasi-Newtor algorithm involves careful trade-off between the sparsity of the approximation matrix B, and the quality of
3

---

Under review as a conference paper at ICLR 2022
its approximation of the Hessian H,, and diagonal approximation is a reasonable choice (Becker ct al. 1988 Zhu et al. 1999). If B is chosen to be a diagonal matrix satisfying (5), one can obtain a formula similar to the SGD-QN algorithm (Bordes et al. 2009).
An alternative of the secant equation in the updating formula (5) as first introduced by Nazareth (1993), is the weak secant equation (Dennis & Wolkowiez, 1993):
B++1 = argmin | Bell
B
S.L. si Bi+1s = of yt (weak secant equation)
The motivation of using the weak secant condition in diagonal quasi-Newton method is straight- forward: the standard mean-value theorem might not necessarily hold for vector-valued functions expressed the secant equation, BB+15 5c = yt ~ V (0,)s, Thus, we do not know whether there
exists a vector 9 E Rd such that y/+ = V f(0)s Dennis & Moré 1977). On the other hand, the Taylor theorem ensures that there exists such 0 that st = st V f(0)s, leading to the reasonable assumption of the weak secant condition (6).
Based on the variational technique Zhu et al.
1999).
the solution of (6) with Frobenius norm is:
$ yv
sf. Byst Diag(s?)
A a B141 B,
|
where of is the element-wis square vector of 8t, Diag(s?) is the diagonal matrix with diagonal elements from vector s/. and - I|a is the 4-norm of a vector.
Parameter- Wise Weak Secant Condition. However, in optimization problems with high- dimensional parameter space, such as training deep neural networks with millions of parameters, the weak secant condition might be too flexible to produce good Hessian approximation. In the setting of decoupled parameters ($ (...1). we propose a parameter-wise version of the weak secant equation to achieve a trade-off between the secant and weak secant conditions: for each parameter g()) e 6, we update B corresponding to g(t) by solving (6) individually. Remarkably, the secant condition restricts B with equation of d-dimensional vector, while the weak secant condition relaxes it with 1-dimensional scalar. The parameter-wise weak secant condition expresses the restriction as a I-dimension vector (1 < < d), resulting in reasonable trade-off. The updating formula is the same as 7 for each parameter-wise B.
3.2 STEPSIZE BIAS CORRECTION
To mitigate the stochastic variance problem in stochastic quasi-Newton methods, APOLLO utilizes stepsize bias correction on the stochastic gradients at each step t. We know that the optimal step- size ni equals w.r.t the quadratic approximation underlying Newton's method, if the Hessian approximation B, and the stochastic gradient 9t are close to the exact Hessian H; and gradient (ft)). respectively. Inspired by this, we correct the stepsize bias in the stochastic gradient gr by replacing it with corrected gradient of = 1):9t. Together with the corresponding corrected v/ = 5'41 gt = (ellit we correct the updating term of B, in (7) by replacing ye with v/: di 21. + df B,d, Diag(d?)
of V/
of BYst Diag(>;)
N'
||dell2
where d, -s/n B,,'. 9t is the corrected update direction. Note that after applying the step bias correction, the update formula of B, in (8) is independent with the stepsize ne eliminating the stepsize bias. Technically, the stepsize bias correction is designed to reduce the stochastic variance, rather than entirely discarding the stepsize. The APOLLO algorithm (Algorithm still incorporates the stepsize at every iteration to enforce convergence.
Based on previous studies, incorporating exponential moving averages (EMVs) for the stochastic gradients significantly reduces the variance (Kingma & Ba 2015). We follow these works and apply EMV to gt. together with the initialization bias correction:
3(1 8t)
1 1-
m
1 1 g++1 m. + 8-8 9t+1
where 0 < 8 < 1 is the decay rate of EMV and ye in do not apply moving average methods to the approximated Hessian, though the diagonal matrix is easier to be explicitly formed to average than full matrices. Investigating the moving average of the diagonal B, might be interesting direction of future work.
{8 is written as m4+1 my Note that we
4

---

Under review as a conference paper at ICLR 2022
Algorithm 1: APOLLO, our proposed algorithm for nonconvex stochastic optimization. All operations on vectors are element-wise. Good default settings are 0.9 and c 1e
Initial: mo. do, Bn < 0, 0,
// Initialian mo, do, Be to zero
while t {O...., ......,7 T do
for 0 E (0' ..... 0%) do
gc+1 + V (.,
// calculate gradient at step t
m++1 + T 1 My + 1-8
0(1-3')
T-
// Update blas-corrected moving
average
a +- of (m (mm-1-m))+d md Bid.
1/ calculate coefficient of B update // Update diagonal Hessian // Handle nonconvexity
(1de)late)
Bi+1 B₁
Diag (df)
Dit1 + rectify( BBt+1, 0.01)
det t Dit1 m++1
// Calculate update di on // Update parameters
l.+1 f- O1 - 11+1d++1
end
end
3.3 RECTIFED ABSOLUTE VALUE OF HESSIAN FOR NONCONVEXITY
To guarantee convergence, quasi-Newton methods require the approximated Hessian matrix B, to be positive definite at each step. The common strategy in previous studies is solve the updating formula in (5) by restricting the candidate matrix B to be symmetric positive definite. It is known that the BFGS update preserves the positive-definiteness of Br+1 as long as the curvature condition of We > O holds, which can be guaranteed for strongly convex problem. For nonconvex problem, the curvature condition can be satisfied by performing a line search, which is, however, expensive or infcasible in stochastic setting, because the exact function values and gradient information unavailable. WWng et al. (2017) proposed the stochastic damped L-BFGS (SdLBFGS) method that implicitly generates positive definite matrix without line search. However, it usually requires large history size (m 2 100) to guarantee convergence, which is infeasible for large-scale optimization.
To handle nonconvexity,
adopt a different strategy that does not require the solution of B, in (5) to be positive definite. Intuitively, we search for B, that is a good approximation of the real Hessian, which is not necessarily positive definite in nonconvex problem. When we B, as preconditioning
calculate the update direction, we use its absolute value: |B,] = BB, B., where is is the positive definite square root of a matrix. The motivation of absolute value is straight-forwand for dimensions with large absolute values of curvature, the objective function could be very sharp and we would prefer to take relatively smaller steps than those flatter dimensions. Since APOLLO formulate B, as diagonal matrix, the cost of computing [B] is marginal.
Rectified Absolute Value of B, For nonconvex objective functions, there exist inflection points whose curvatures are zero. To prevent the steps from becoming arbitrarily large, we rectify the absolute value of B, with a convexity hyper-parameter a:
(atiifyyB,,,) Dj rectify [Bt, o) = max( ())))
(10)
where the rectify o) function is similar to the rectified linear unit (ReLU) (Nair Hinton 2010 with threshold a. The update direction in
then d, D, ','mm m.
AdaHessian Yao et al. 2020) used an idea similar to the absolute values of B, to handle nonconvexity. where the root mean square averaging is applied to compute the Hessian diagonal. Different from APOLLO, AdaHessian requires second-orde information to compute the Hessian matvec oracle and approximate the Hessian diagonal using Hutchinson's 's method, which significantly more costly.
3.4 INTTIALIZATION
The rectified D, in TO) introduces more hyper-parameter a, limiting the application of APOLLO in practice. In this section, we show that the zero initialization approach in APOLLO, which initializes the moving average of gradient mo. the parameter update direction do and the diagonal approximation of Hessian Bo as (vector of) zeros, leads to coupled stepsize n and convexity a, allowing us to eliminate one
of r or a.
5

---

Under review as a conference paper at ICLR 2022
Coupled Stepsize and Convexity With the zero initialization of mu, do and Bo, the following theorem illustrates the relation between 7, and a (details in Appendix
Theorem 1. Given zero initialization of mo, do, and Bo and fixed parameter intialization Bg- Suppose that we have sets of hyper-parameters 1); and n/ o' with the same ratio: 2 = 3. Then the convergence trajectories of these two sets of hyper-paramette are exactly the same:
0: f:. Vt {I....,T):
(11)
where Ot and 02 are the parameters of (n, o) and (n', o') at iteration t, respectively.
From Theorem T we observe that and a are coupled with each other and in practice we only need tune one of them, leaving the other fixed. Therefore, in our experiments ($4) we fix o 0.01 and tune on different problems
Learning Rate Warmup for APOLLO As discussed in Kingma Ba 2015). zero initialization leads to estimations biased towards zero in the initial iterations. For the moving average m,, this bias can corrected by dividing the bias-correction term ( For d, and B,, however, we cannot derive such bias correction terms. Fortunately, simple linear warmup heuristic of at the beginning iterations achieves remarkably stable training.
3.5 CONVERGENCE ANALYSIS
Similar to previous work (Reddi et al. 2018 Chen et al. initialization bias correction step, i.e. we use my 3,m + Be)gr, 0 < Be < 1, VI E (T).
2019 Zhuang al. 2020).
omit the
We first analyze the convergence of APOLLO in convex optimization using the online learning framework (Zinkevich] 2003) for sequence of convex cost functions fi (0), f2(0).....fr((())
Theorem 2. (Convergence in convex optimization) Let {0:} ) be the sequence from APOLLO. Suppose
"h 2 0 < 3: S B S 11 S SG ||Dt-1ll s ||Da|la ||0, - 1el I D, Vt, t' E [T]. For 0
n
generated with the APOLLO algorithm, we have the following bound on the regret:
VTD*| Drlli + 1-3 (2VT
G/2
D2
T
B
Rr S 2n(1 -
1)+ 2(1
(12)
B)
1
The following result falls as an immediate corollary of the above result.
Corollary 2.1. Suppose Bg =0X--1,0
< in Theorem 2 have
/
G
D2
Rr S
1 (2VT 1)+ 27y11 X2)2
(13)
21y(1 3)
Theorem implies the regret of APOLLO upper bounded by O(VT). The conditions for Corol- lary 2.1 as Reddi et al. (2018), can be relaxed to 3, = B/tt and still ensures a regret of O(VT).
For nonconvex case, we analyze the convergence rate of APOLLO with the similar derivations of that Chen al. (2019), since APOLLO belongs the family of generalized Adam-type methods:
Theorem 3. (Convergence in nonconvex stochastic optimization) Under the assumptions:
f lower bounded and differentiable; f V ||2 L| 8'112. || < L, Vt, 0, H'.
Both the true and stochastic gradient are bounded, i.e. [V la < H, llgelle < H, Vt.
Unbiased and independent noise in gts iee. 9t = ((.)) + G. [[[G] = 0, and C Gj. Vi #
Assume Tt-
"/ 3e < B < 1 in non-increasing.
D.-1.1 < Puj VI E [T],j E [d]. then:
7-
E V (())) T
min
(L T) + C2dn + Czdn² + Ca) VT
L
(14)
where C₁ C2. C3 are constants independent of d and T, C4 is a constant independent of T, the expectation is taken w.r.t all the randomness corresponding {ge}. Theorem immples the conver- gence rate for APOLLO in the non-convex case is (log (1logT//el T//T), which is similar to Adam-type optimizer (Reddi et al.) 2018 Chen et al. 2019). In addition, unlike Theorem 3.1 in Chen et al. (2019), Theorem does not specify the bound of each update ||mmee/ Dell2. This is because that, with conditions 1/: [mmm, D < HH G.
|9 l < Hl and D, > 1, it is straight-forward to derive the bound of
We changed from 0.01 make n in suitable range. See Appendix E.4 for details.

---

Under review as a conference paper at ICLR 2022
SGD
Adam
RAdam accuracy (milestone)
AdeBelief
Adallessian
Apollc
Training loss (milestone)
Training loss (milestonne)
Test (milestone)
95
90
25
0.4
2.0
0.3
0.2
1.5
75
1.0
0.0g
700
0.5g
400
Epochs
Epochs
Epochs
Epochs
Training loss (cosine)
Test (cosine)
Training (cosine)
Test accuracy (casine)
0.5
7.5
0.4
85
2.0
0.3
0.2
1.5
75
1.0
48
0.0
200 70g
250
0.5g
400
Epochs
CIFAR-10
Epochs
Epochs
ImageNet
Epochs
Figure I: Training loss and test accuracy of ResNet- 10 on CIFAR-10 and ResNeXt-50 on ImageNet, with two schedule strategies of learning rate decay.
EXPERIMENTS
To evaluate APOLLO, we conduct experiments on four benchmark datasets across three tasks of CV and NLP that are commonly used to evaluate optimization algorithms: CIFAR-10 (Krizhevsky &
Hinton| 2009) and ImageNet (Deng et al.] 2009) for image classification; One Billion Words (Chelha
ct stal.] (2133) for language modeling; and WMT 2014 English- for neural machine translation.
The five baseline methods we compare with are SGD with momentum (Bottou & Bousquet 2008).
Adam Kingma& Ba 2015), Rectified Adam (RAdam) (Liu et al., 2020), AdaBeliet (Zhuang et al.. 2020), and AdaHessian (ao et al., 2020). Following Loshchilov & Hutter (2019), we decouple weight decays in Adam, RAdam, AdaBelief and AdaHessian in all the experiments] For each experiment, we report the average over runs. More detailed descriptions, results and analysis of the conducted experiments are provided in Appendix
4.1 IMAGE CLASSIFICATION
We begin our experiments with an evaluation of the convergence and generalization performance on image classification. We use ResNet- 1q" CIFAR-10 and standard ResNeXt-50 (Xie et al.) 2017) for ImageNet, respectively. The results on CIFAR-10 10 and ImageNet are presented in Figure and Table [ together with the five base- lines. For each optimizer, we use two schedul- mile-
Table 1: Test Acc. on CIFAR-10 10 and ImageNet.
CIFAR-10
ImageNet
Method
milestone
cosine
milestone
cosine
SGD
93.94
94.53
77.57
78.26
Adam
93.74
94.24
76.86
77.54
RAdam
93.88
94.38
76,91
77.68
AdaBelief
94.03
94.51
77.55
78.22
ing strategies of learning rate decay: stone that decays the learning rate at the end of some predefined epochs; and ii) cosine anneal- ing schedule proposed in Loshchilov & Hutter (2017). All the optimization methods are comprehensively tuned, especially for the learning rate and the rate of weight decay. It is because that the strength of weight decay regularization is co-related with the learning rate, even though the decoupled weight decay technique (Loshchilov & Hutter 2019) has been applied. The tuning information and the model details are provided in the Appendix F.
AdaHessian
93.97
94.48
77,61
78.02
APOLLO
94.21
94.64
77.85
78.45
From Figure | and Table I we see that APOLLO outperforms the four first-order methods (SGD, Adam, RAdam and AdaBelief) on both the convergence speed and classification accuracy, demon- strating its effectiveness on training the ResNet architectures based on convolutional neural networks (CNNs) (LeCun et al. 1989). Comparing with AdaHessian, APOLLO obtains better test accuracy with similar convergence speed. Note that AdaHessian requires second-order information and is significantly more costly (detailed comparison of time and memory costs in Appendix F3 Thus, omit AdaHessian from the following experiments in the rest of this paper.
For AdaBelief, we also tried standard 1-g regularization. But the accuracies are consistently worse than the models with decoupled weight decay.
ResNeet I 10 is modified (small) version of ResNet-18 18 adapt the image size 32 32 in CIFAR-10.
7

---

Under review as a conference paper at ICLR 2022
0.5
S60
0.6
Adam
0.6
RAdam
0.6
Apallo
0.5
0.5
0.5
0.5
Training
0.2
0.2
0.2
0.2
0.1
0.1
0.00
100
160
0.0
120
0.0
40
100
160
0.0
120 140
20
40
00
80
160
120
180
360
70g
20
60
65
80
100
120
360
160
20
40
65
80
160
120
340
160
70g
20
60
02
80
100
120
340
100
Figure 2: SGD, Adam, RAdam and APOLLO with different learning rates CIFAR-10.
SGD
Adam Training
RAdam
AdaBelief
Apollo
120
Method
PPL.
130
43
100
15
SGD
32.65
Adam
36.68
39
RAdam
36.20
36
00
AdaBelief
32.83
50k
100%
150: Updetes
200K
254
250
6M
10
12
APOLLO
31.94
Updates
Epochs
Figure 3: Language modeling (LSTMs) on One Billion Words.
Table 2: Test PPL.
Robustness to Learning Rate Change. Besides performance improvements, we also investigate the robustness of different optimization methods to the change of learning rate. For each optimizer, we use the learning rate in the previous experiment (Table 1 as the base, i.e. 0.1 for SGD, 0.001 for Adam and RAdam, and 0.01 for APOLLO. Then, we explore different learning rates that are times of the base learning rate, with a E {0.2, 1.0, 2.0, 10.0). As mentioned above, we observed that the strength of weight decay regularization is co-related with the learning rate, even for Adam and RAdam with decoupled weight decay (Loshchilov & Hutter 2019). To eliminate the impact of weight decay, adjust the weight decay rates according to the factor Experimental results with ResNet- 10 on CIFAR-10 are summarized in Figure 2 After correcting the impact of weight decay, all the optimization methods, except SGD with 10.0, achieve consistent model performance, while APOLLO slightly improves the robustness of model training over the three baseline methods.
4.2 LANGUAGE MODELING
To evaluate APOLLO Recurrent Neural Networks (RNNs) that applied in wide range of NLP tasks (Graves 2013), we conduct experiments on the One Billion Words dataset (Chelba et al. 2013)) using layer LSTM network for language modeling (details in Appendix E.2
Figure 3 and Table illustrate the perplexity (PPL) of training and test for APOLLO and four baseline methods, including SGD, Adam, RAdam and AdaBelief. As shown in Figure 3 although APOLLO is slower than Adam-type methods in the first few updates, its convergence is much faster after that. On generalization performance, A PPOLOO achieves significant improvements (more than 4.0 PPL points on test data) over Adam and RAdam. In addition, APOLLO also outperforms AdaBelief, which obtains the lowest PPL among the three Adam-type optimization methods" This demonstrates the effectiveness of APOLLO on training LSTM-based neural architectures.
Training Stability. From the middle plot of Figure 3 we see that the training losses of Adam and RAdam may suddenly increase. This occurred in all the runs of experiments using Adam and RAdam, and we selected these successfully converged the loss went back to normal after some updates, and discarded those that failed to converge - the model crashed due to loss numerical overflow. The suffered from this issue, demonstrating its stability.
models optimized with APOLLO
is obtained using = le -22 With other values, e.g. 1e or 1e" the PPI. points of AdaBelief are even higher than Adam and RAdam. See Appendix F.2 for the details of papar-parameter tuning.
WWe found that AdaBelief is very sensitive to the value of The result in Table 2
8

---

Under review as a conference paper at ICLR 2022
4.3 NEURAL MACHINE TRANSLATION
Table 3: Test BLEU.
To evaluate APOLLO on Attention-based Transformer architec- ture (Vaswani et al,, 2017), we train the Transformer-base model on the WMT2011 English-German (EN-DE) dataset (around 4.5M sentence pairs). We use the same data preprocessing steps as in Ma
Method
BLEU
SGD
26.59=0007
et al. 2019) (details in Appendix E.3 We compare APOLLO with the same four baseline methods in the experiments of language modeling. For each experiment, we report the mean and standard variance over 5 runs. From Table 3, the first interesting observation is that SGD performs much worse than Adam-type methods (which is opposite to its behaviour for ResNet- and MSTM- neural architectures). Similar observations about SGI) were reported in (Yao et al.] 2020 Zhang et al., (020). Despite this, APOLLO obtains improvements over all the baseline methods for NMT with transformers.
Adam
27.84.10.12
RAdam
28.15:10.115
AdaBelief
28.14=0.11
APOLLO
28.34:10.10
5 RELATED WORK
Stochastic Quasi-Newton Methods. In the literature of (nonconvex) stochastic quasi-Newton methods, several algorithms have been developed recently for large-scale machine learning problems: oLBFGS (Schraudolph et al.
& Ribeiro 2015). RES (Mokhtari & Ribeiro 2014).
SFO (Sohi-Dickstein et 2014)) SQN (Byrd al. 2016). SILBFGS (Wang et al.][2017] ) and AdaQN (Keskar & Berahas 2016), among which only SILBFGS and AdaQN are designed to solve nonconvex optimization problems. The SdLBFGS algorithm carefully controls the quality of modified BFGS updates preserve the positive-definitenn
of B, in (5) without line search. AdaQN shares a similar idea but is specifically designed for RNNs by refining the initial L-BFGS scaling, step acceptance control and choice of curvature information matrix, and adopting the SQN framework (Byrd et al.) 2016). Different from these two methods, APOLLO does not require B, in (5) to be positive definite, but replacing it with its rectified absolute value to handle nonconvexity. Moreover, both SdLBFGS and AdaQN use the updating formula similar to L-BFGS and require even larger history size (commonly 100) to guarantee convergence, preventing them from being applied to large-scale optimization. For comprehensive comparison of SdLBFGS with Apollo, we conducted experiments with small toy CNN models (details in Appendix G
Adaptive First-Order Methods. From the diagonal approximation of Hessian, APOLLO is also related to those diagonally-scaled first-order algorithms, such as AdaGrad (Duchi et al. 201
RMSProp (Tieleman& & Hinton| 2012). AdaDelta (Zeiler 2012), and Adam (Kingma & Ba 2015
Subsequently, a number of techniques have emerged to theoretically justify and algorithmicaly improve Adam, including AMSGrad (Reddi al. 2018), AdaBound (Luo al. 2019). RAdam (Liu et al. 2020) and AdaBelief (Zhuang et al. 2020). The main difference is that the diagonal precon- ditioning APOLLO is directly derived from the quasi-Newton updating formula (6). In terms of memory efficiency. [Anil et al. (2019) and Chen et al. (2020) further reduces the memory cost of adaptive methods, Agarwal et al. (019) proposed effccient full-matrix adaptive regularization.
Stochastic Second-Order Hessian-Free Free Methods. Stochastic Second- Hessian-Free meth- ods (20rt) Martens & Sutskever] [001 implicitly solve quadratic models using matrix-vector products. [Duphhn al. a (2014) argued the existence of saddle points and proposed method to rapidly escape them. K-FAC (Martens & Grosse 2015) computes a second-order step by constructing an invertible approximation of the Fisher information matrix in an online fashion. Shampoo (Gupta iet al. 2018) approximates the Fisher information matrix using low-rank decomposition. Recently, Yao et al. (2020) proposed AdaHessian, which approximates the Hessian diagonal using Hutchinson's method. These second-order methods differ from APOLLO mainly in the request of second-orde information of the objective function at each iteration.
CONCLUSION AND EXTENSIONS
We have introduced APOLLO, a simple and computationally efficient quasi-Newir algorithm for nonconvex stochastic optimization. This method is aimed towards large-scale optimization problems in the sense of large datasets and/or high-dimensional parameter spaces such as machine learning with deep neural networks. Experimental results three CV and NLP tasks demonstrate the effectiveness of APOLLO, in terms of both convergence speed and generalization performance. In Appendix [ we briefly outline few extensions to APOLIOO that we want to explore in future work.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Naman Agarwal, Brian Bullins, Xinyi Chen, Elad Hazan, Karan Singh, Cyril Zhang, and Yi Zhang. Efficient full-matrix adaptive regularization. In International Conference on Machine Learning. pp. 102-110, 2019.
Rohan Anil, Vineet Gupta, Tomer Koren, and Yoram Singer. Memory efficient adaptive optimization. In Advances in Neural Information Processing Systems, pp. 9749-9758, 2019.
Sue Becker, Yann Le Cun, et al. Improving the convergence of back- propagation learning with second order methods. In Proceedings of the 1988 connectionist models summer school, pp. 29-37, 1988.
Antoine Bordes, Léon Bottou, and Patrick Gallinari. SGD-QN: Careful quasi-newton stochastic gradient descent. The Journal of Machine Learning Research, 10:1737-1754, 2009.
Léon Bottou and Olivier Bousquet. The tradeoffs of large scale learning. Advances neural information processing systems, pp. 161-168, 2008.
Charles G Broyden. Quasi- methods and their application to function minimisation. Mathe- matics of Computation, 2 (199))3668-1 -881, 1967.
Charles George Broyden. The convergence of a class of double-rank minimization algorithms. IMA Journal of Applied Mathematics, 6(1):76 90, 1970.
Richard H Byrd, Peihuang Lu, Jorge Nocedal, and Ciyou Zhu. limited memory algorithm for 1995.
bound constrained optimization. SIAM Journal scientific computing,
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, 2011.
Richard Byrd, Samantha I. Hansen, Jorge Nocedal, and Yoram Singer. A stochastic quasi-newton method for large-scale optimization. SIAM Journal on Optimization, 26(2):1008-10) 2016.
Ciprian Chelba, Tomas Mikolov, Mike Schuster, Qi Ge, Thorsten Brants, Phillipp Koehn, and Tony Robinson. One billion word benchmark for measuring progress in statistical language modeling. arXiv preprint arXiv:1312.3000 2013.
X Chen, M Hong, $ Liu, and R Sun. On the convergence of a class of adam-type algorithms for non-convex optimization. In 7th International Conference on Learning Representations, ICLR 2019, 2019.
Xinyi Chen, Naman Agarwal, Elad Hazan, Cyril Zhang, and Yi Zhang. Extreme tensoring for low-memory preconditioning. In International Conference on Learning Representations, 2020.
Yann N Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio. Identifying and attacking the saddle point problem in nigh-dimensiooal non-convex optimization. In Advances in neural information processing systems, pp. 2933-201 22412994,112 2014.
William C Davidon. Variable metric method for minimization. SIAM Journal on Optimization, 1(1):
1-17, 1991.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp.
leee, 2009.
John E Dennis, Jr and Jorge J Moré. Quasi-newton methods, motivation and theory. SIAM review, 19 (1):46-99, 1977.
John E Dennis, Jr and Henry Wolkowicz. Sizing and least-change secant methods. SIAM Journal on Numerical Analysis, 329 1993.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
10

---

Under review as a conference paper at ICLR 2022
Roger Fletcher. A new approach variable metric algorithms. The computer journal, 13(3), 1970.
Roger Fletcher. Practical methods of optimization. John Wiley & Sons, 1987.
D Goldfarb. A family of variable metric updates derived by variational means. Mathematics of Computation, 24(109):23-26, 1970.
Alex Graves. Generating sequences with recurrent neural networks. arXiv preprint: 1308. 0850, 2013.
Vineet Gupta, Tomer Koren, and Yoram Singer. Shampoo: Preconditioned stochastic tensor optimiza- tion. arXiv preprint arXiv:1802.090 1802.0958, 2018
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Geoffrey Hinton, Li Deng, Dong Yu, George E Dahl, Abdel-rahman Mohamed, Navdeep Jaitly, Andrew Senior, Vincent Vanhoucke, Patrick Nguyen, Tara N Sainath, et al. Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups. IEEE Signal processing magazine, (96):22797 2012.
Geoffrey E Hinton and Ruslan R Salakhutdinov. Reducing the dimensionality of data with neural networks. science, 31345786):504-577, 2006.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
Nitish Shirish Keskar and Albert S Berahas. AdaQN: An adaptive quasi-newton algorithm for training mns. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 1-16. Springer, 2016.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference Learning Representations, 2015.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
Yann LeCun, Bernhard Boser, John S Denker, Donnie Henderson, Richard E Howard, Wayne Hubbard, and Lawrence D Jackel. Backpropagation applied handwritten zip code recognition. Neural computation, 1(4):541 -511, 1989.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-2344 1998.
Yingkai Li and Huidong Liu. Implementation of stochastic quasi-newton's method in pytorch. arXiv preprint arXiv:1805.023: 02338, 2018
Dong C Liu and Jorge Nocedal. On the limited memory bfgs method for large scale optimization. Mathematical programming, 4501-3):503-528 1989.
Liyuan Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han. On the variance of the adaptive learning rate and beyond. In International Conference on Learning Representations, 2020.
Ilya Loshchilov and Frank Hutter. SGDR: Stochastic gradient descent with warm restarts. In International Conference Learning Representations, 2017.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Confer- ence on Learning Representations, 2019.
Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate. In International Conference Learning Representations, 2019.
11

---

Under review as a conference paper at ICLR 2022
Xuezhe Ma and Eduard Hovy. End-to-end sequence labeling via bi-directional LSTM- CRNNS-RRF In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1064-1074, Berlin, Germany, August 2016.
Xuezhe Ma, Chunting Zhou, Xian Li, Graham Neubig, and Eduard Hovy. Flowseq: Non- autoregressive conditional sequence generation with generative flow. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing, pp. 4282-4292, Hong Kong, November 2019.
James Martens. Deep learning via hessian-free optimization. In Proceedings of the 27th International Conference on International Conference on Machine Learning, pp- 735-742, 2010.
James Martens and Roger Grosse. Optimizing neural networks with kronecker-factoree approximate curvature. In International conference on machine learning, pp. 2408-24422 2408-224,,47 2015.
James Martens and Nya Sutskever. Learning recurrent neural networks with hessian-free optimization. In Proceedings of the 28th international conference on machine learning (ICML-11), pp. 1033- 1040. Citeseer, 2011.
Aryan Mokhtari and Alejandro Ribeiro. Res: Regularized stochastic bigs algorithm. IEEE Transac- fions Signal Processing, 62(23))6089-6100 2014.
Aryan Mokhtari and Alejandro Ribeiro. Global convergence online limited memory bfgs. The Journal of Machine Learning Research, 16(1)33151-3181 2015.
Vinod Nair and Geoffrey E Hinton. Rectified linear units improve restricted boltzmann machines. In ICML, 2010.
JL Nazareth. If quasi-newton then why not quasi-cauchy. SIAG/Opt Views-and-news, 6: 1:11-14, 1995.
Jorge Nocedal and Stephen Wright. Numerical optimization. Springer Science & Business Media, 2006.
Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng. David Grangier, and Michael Auli. FairSeq: A fast, extensible toolkit for sequence modeling. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics (Demonstraaionss), pp. 18-53,22 2019.
Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In International conference on machine learning, pp. 1310-1318, 2013.
Ning Qian, On the momentum term in gradient descent learning algorithms. Neural networks, 12(1): 145-151, 1999.
Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference Learning Representations, 2018.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pp. 400 400-407, 407, 1951.
Sebastian Ruder. An overview of gradient descent optimization algorithms. arXiv:1609.04747 04747, 2016.
arXiv preprint
David E Rumelhart, Geoffrey E Hinton, and Ronald J Williams. Learning internal representations by error propagation. Technical report, California Univ San Diego La Jolla Cognitive Science, 1985.
Nicol N Schraudolph, Jin Yu, and Simon Günter. A stochastic quasi-newton newton method for online convex optimization. In Artificial intelligence and statistics, pp. 436 443, 2007.
David F Shanno. Conditioning of newsin methods for function minimization. Mathematics of computation, 24(1 24(111):647-666 1970.
12

---

Under review as a conference paper at ICLR 2022
Jascha Sohl-Dickstein, Ben Poole, and Surya Ganguli. Fast large-scale optimization by unifying stochastic gradient and quasi-newton methods. In International Conference on Machine Learning, pp. 604-612, 2014.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research, 15():1199--1958 2014.
Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna. Rethinking the inception architecture for computer vision. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 2818-22888 2818-2826, 2016.
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2), 2012.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 1998-6008, 2017.
Xiao Wang, Shiqian Ma, Donald Goldfarb, and Wei Liu. Stochastic quasi-newton methods for nonconvex stochastic optimization. SIAM Journal Optinization, 27(2):927-956, 2017.
Ashia C Wilson, Rebecca Roelofs, Mitchell Stem,, Nati Srebro, and Benjamin Recht. The marginal
value of adaptive gradient methods in machine learning. In Advances in neural information processing systems, pp. 4148 1148-4158, 2017.
Philip Wolfe. The secant method for simultaneous nonlinear equations. Communications of the ACM, 2(12):12-13, 1959.
Saining Xie, Ross Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He. Aggregated residual transformations for deep neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1492-1500. 2017.
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.00719, 2020. 2020.
Wei Yuan and Kai-Xin Gao. EAdam optimizer: How epsilon impact adam. arXiv preprint
arXiv:2011.02//5 0.0-20///.2211 2020.
Matthew D Zeiler. Adadelta: an adaptive learning rate method. arXiv preprint:121225700 1212.5701, 2012.
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiy Kumar, and Suvrit Sra. Why adaptive methods good for attention models? Advances in Neural Information Processing Systems, 33, 2020.
Mingfa Zhu, John Lawrence Nazareth, and Henry Wolkowicz. The quasi-cauchy relation and diagonal updating. SIAM Journal on Optimization, 9(4):1922-1204, 1999.
Juntang Zhuang, Tommy Tang, Yifan Ding, Sekhar C Tatikonda, Nicha Dvornek, Xenophon Pa- pademetris, and James Duncan. Adabelief optimizer: Adapting stepsizes by the belief in observed gradients. Advances in Neural Information Processing Systems, 33, 2020.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference machine learning (ieml-03), pp. 928-936. 2003.
13


Reviews:
[{"review_id": "c23w1USJntL", "reviewer": "Reviewer_p4ji", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "*Strengths*: Overall, the paper is well-written and well-motivated,\nthe background material is sufficient, and the computational experiments\nare comprehensive and significant. I also appreciate the efforts the\nauthors made to keep the presentation simple and concise.\n\n*Weaknesses*: I have a few technical issues with the presentation\nof the results:\n1. Theorem 2 and Corollary 2.1 are not \"convergence\" results, but\nrather regret bounds. For completeness, the authors should present\na true convergence result, like in Theorem 3, in which a relevant\nresidual, e.g. $\\min_{t\\in[T]} E [\\|\\nabla f(\\theta_t)\\|] $\nor $\\min_{t\\in[T]}E[f(\\theta_{t})-f_{*}]$, is proven to go to zero\nas $T\\to\\infty$. It should also be expected that the produced convergence rate\nbe similar to other quasi-Newton convergence rates for the convex setting.\n\n2. The convergence rate established in Theorem 3 in the nonconvex case\nis on the same order of complexity as other Adam-based methods (in\nfact, the proof of this result is based on prior analyses of Adam-type\nmethods). This result is not encouraging from a theoretical point\nof view as there are other works in the literature (see, for example,\n[1]) that make use of second-order information (through first-order\napproximations) that have better convergence rates than purely first-order\nmethods. The authors should comment on why their method cannot achieve\nsuch a level of acceleration, e.g., due to rectification or the use\nof a weakened secant equation, and/or the advantage of their method\nover other **accelerated** methods like in [1].\n\nAside from the above points, I only have a few minor issues with some\nof the other material in the paper:\n\n1. [p. 6] Give the precise definition of the regret $R_{T}$ (it is only defined in the Appendix).\n2. *Minor typos*:\n- [p. 5] All instances of \"problem\" should be plural in the\nfirst paragraph of Subsection 3.3. \n- [p. 6] Remove the period in equation (11).\n- [p. 6] ... Similar to previous **works** ...\n\n[1] Carmon, Y., Duchi, J. C., Hinder, O., & Sidford, A. (2018).\nAccelerated methods for nonconvex optimization. *SIAM Journal on\nOptimization, 28*(2), 1751-1772.", "summary_of_the_paper": "This paper presents a first-order quasi-Newton method, named APOLLO,\nfor solving stochastic nonconvex finite sum problems with a large\nnumber of data points. Each iteration of the method consists of computing\na sparse and positive definite (diagonal) approximation of the objective\nfunction's Hessian, followed a quasi-Newton step. A regret bound is\nestablished for the convex setting and a complexity bound is established\nfor the nonconvex setting, based on prior results on Adam-type optimizers.\nFinally, a comprehensive set of numerical experiments on three common\ntasks in vision and language is presented to show the superiority\nof the proposed method.\n", "summary_of_the_review": "This paper is overall well-written and contains a comprehensive and\nsignificant set of numerical experiments. A few gaps in the presentation\nof the theoretical contributions, however, prevent it from receiving\na stronger score.", "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": "YV4BRaRhqFt", "reviewer": "Reviewer_XwAE", "summary": "", "questions": "", "limitations": "", "rating": 3, "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:\nThere is certain novelty in the proposed method, and the issues of nonconvexity, computational efficiency, and stochastic variance that are addressed in this work are significant.\n\nWeaknesses:\n1.\tIn Theorem 2 and Corollary 2.1, there is an assumption on $\\|\\|D_{t-1}\\|\\|\\_1$ and $\\|\\|D_t\\|\\|\\_1$, but $D\\_t$ is a variable in the iterative update. Similarly, Theorem 3 has the assumption $\\frac{D_{t-1},j}{\\eta_{t-1}} \\leq \\frac{D_{t,j}}{\\eta_t}$. How strong are these assumptions? Can they be satisfied during the iterations?\n2.\tOne of the key points in this work is that the parameter-wise update of $B_t$ trades off between secant condition and weak secant condition. Intuitively, one would expect that the number of decoupled parameters $L$ has influence on the performance both theoretically and numerically. However, $L$ does not appear in the convergence analysis or the experiments.\n3.\tIn the experiments, it is claimed that the proposed method outperforms the compared first-order methods on convergence speed. However, it is only true in terms of epochs, but not true in terms of runtime. It is quite common that a quasi-second-order method converges faster in terms of iterations, but the real question is how efficient it is in runtime.\n4.\tIt is suggested that the notation for the Lipchitz constant in Theorem 3 should be changed, since L already denotes the number of decoupled parameters.\n", "summary_of_the_paper": "This work proposes a quasi-Newton method APOLLO for nonconvex stochastic optimization. Based on a parameter-wise weak secant condition, a diagonal approximation of the Hessian is constructed, and rectified absolute value is adopted on the approximation. A step-size bias correction technique is used to mitigate stochastic gradient variance. Theoretical convergence analysis is provided under a convex online setting and a nonconvex stochastic setting. Experiments on CV and NLP tasks demonstrate the effectiveness and stability of the proposed method.", "summary_of_the_review": "Though there is certain novelty in this work, the theoretical contributions seem to be flawed, and the numerical results are not convincing, as explained in the main review. Thus, my current recommendation for this work is rejection.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "CVb7AUcPFER", "reviewer": "Reviewer_LyjG", "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 presents a diagonal approximation to the Hessian. The presentation is very clear, and the algorithm is simple and easy to implement. The experiments show improvements on several datasets.\n\nDiagonal approximation of quasi-Newton methods has been studied before, as the authors point out. The main contribution of the paper is to combine it with several other ideas, such as rectification (also done by AdaHessian), momentum via moving averages, learning rate warmup and step size bias correction. \n\nThe sentence in the introduction \"these adaptive optimization methods may converge to bad/suspicious local optima\" is rather strange, given the widespread use of these methods in industrial and academic settings. Seems unfair to castigate methods that have been used in so many applications on the basis of one isolated study. Adaptive methods are the methods of choice for NLP and CV tasks for several years, notwithstanding the claim made in the first para of page 2 (those papers are from several years ago).\n\nThe claim that Apollo \"significantly outperforms SGD and variants of Adam, in terms of both convergence speed and generalization performance\" is not supported by the results. The image classification results use non-standard architectures, and the improvement in accuracy is small. The appendix shows that Apollo is 20-50% slower than SGD and Adam --- it is hard to tell from the graphs, but it is quite likely that in the same time, SGD and Adam could have produced the same accuracy. Please include a test accuracy vs time plot in the appendix.\n\nFurthermore, given that the current method is estimating the Hessian, it should be compared with the second order methods such as  Shampoo (Anil et al), as these methods are able to outperform SGD and Adam on large problems.", "summary_of_the_paper": "The paper presents a diagonal quasi-Newton method, by approximating the Hessian with a diagonal matrix. The paper proves a regret bound for the method in the convex case, and shows that in the non-convex setting the expected norm of the gradients goes to 0. The paper then provides experimental results on two image datasets, a small translation task and a small language modeling task.\n\n", "summary_of_the_review": "The paper presents an optimizer by combining several ideas from previous papers, and shows small improvements on some datasets.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "AP80iJWHLDE", "reviewer": "Reviewer_qbeR", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Strengths:\nThe authors provided theoretical guarantee of the proposed algorithm, Apollo, and showed good empirical performance of it.\n\nWeaknesses: \n- The algorithm imposed the restriction that parameters have to be updated component-wise; while this is applicable to neural-network type problems (i.e., each layer may be updated separately during training), I don't see how this can be easily applied to other ML problems.\n- I'm not able to judge the technical correctness of the statements in Theorems 1,2,3 from the main paper; One question I have is about the parameter-wise update of the gradient/Hessian; this results in a different type of algorithm than SGD-variants; While I'm not a hundred percent sure, I believe this is also not the case for Adam/Ada-grad type algorithms. How does this not affect the convergence guarantee? Does this type of parameter-wise update fit the framework of generalized-Adam?", "summary_of_the_paper": "The paper developed a new quasi-Newton algorithm for stochastic non-convex optimization. In contrast to existing works, it uses a (rectified/capped) diagonal matrix to approximate the Hessian, and incorporated techniques to reduce the stochastic variance. It shows first-order convergence guarantee of the algorithm and provided empirical evaluation on 2 CV and 2 NLP datasets.", "summary_of_the_review": "The paper could be a good contribution to the literature (as well as for practice), however I have several concerns currently holding me back, which I hope the authors can address in the rebuttal (they are all related to the parameter-wise update regime enforced by the algorithm; please see my comments in the main review section)", "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: This paper proposes a diagonal approximation to the Hessian in a quasi-Newton method for non convex stochastic optimization problems. They combine several good existing ideas and show empirically that the method performs well on several learning tasks, but reviewers found that the comparisons were limited in that as an (approximate) second order method, it would be more fair to compare to other second-order methods rather than largely focusing on SGD and some variants of ADAM. Overall, reviewers found the novelty limited and had some concerns about the strength of assumptions, parameter-wise updates, and some more minor comments on gaps in the presentation. The author response did not fully convince the borderline/negative reviewers, though the paper includes good ideas that would potentially be well received in a future revision.
Decision: Reject