A Computationally Efficient Sparsified Online Newton Method
Authors: Fnu Devvrit
Sai Surya Duvvuri
Rohan Anil
Vineet Gupta
Cho-Jui Hsieh
Inderjit S Dhillon
Venue: Submitted to ICLR 2023 (2023)
Keywords: Optimization
Second order methods

Abstract: Second-order methods have huge potential in improving the convergence of deep neural network (DNN) training, but are prohibitive due to their large memory and compute requirements. Furthermore, computing the matrix inverse or the Newton direction, which is needed in second-order methods, requires high precision computation for stable training as the preconditioner could have a large condition number. This paper provides a first attempt at developing computationally efficient sparse preconditioners for DNN training which can also tolerate low precision computation. Our new Sparsified Online Newton (SONew) algorithm emerges from the novel use of the so-called LogDet matrix divergence measure; we combine it with sparsity constraints to minimize the regret in the online convex optimization framework. Our mathematical analysis allows us to reduce the condition number of our sparse preconditioning matrix, thus improving the stability of training with low precision. We conduct experiments on a feed-forward neural-network autoencoder benchmark, where we compare training loss of optimizers when run for a fixed number of epochs. In the float32 experiments, our methods outperform the best-performing first-order optimizers and perform comparably to Shampoo, a state-of-the-art second-order optimizer. However, our method is even more effective in low-precision, where SONew finishes training considerably faster while performing comparably with Shampoo on training loss.

Under review as a conference paper at ICLR 2023
A COMPUTATIONALLY EFFICIENT SPARSIFIED ONLINE NEWTON METHOD
Anonymous authors Paper under double-blind review
ABSTRACT
Second-order methods have enormous potential in improving the convergence of deep neural network (DNN) training, but prohibitive due to their large mem- ory and compute requirements. Furthermore, computing the matrix inverse or the Newton direction, which is needed in second-order methods, requires high pre- cision computation for stable training as the preconditioner could have large condition number. This paper provides first attempt at developing computa- tionally efficient sparse preconditioners for DNN training which can also tolerate low precision computation. Our new Sparsified Online Newton (SONew) algo- rithm emerges from the novel use of the LogDet matrix divergence measure; we combine it with sparsity constraints to minimize regret in the online convex opti- mization framework. Our mathematical analysis allows us to reduce the condition number of our sparse preconditioning matrix, thus improving the stability of train- ing with low precision. We conduct experiments autoencoder benchmark, where we compare training loss of optimizers when run for fixed number of epochs. In the float32 experiments. our methods outperform the best-perfoo pess--erforming first-order optimizers and perform comparably to Shampoo. a state-of-the-as second-order optimizer. However, our method is even more ef- fective in low precision, where SONew finishes training considerably faster while performing comparably with Shampoo on training loss.
ferd-forward neural-network
INTRODUCTION
Stochastic first order methods which use the negative gradient direction to update parameters have become the standard for training deep neural networks (DNNs). Gradient-based preconditioning involves finding update direction, by multiplying the gradient with preconditioner matrix care- fully chosen from gradients observed in previous iterations, to improve convergence. (Full-matri) malll-mttrix Adagrad (Duchi et al., 201 1h), online Newton method (Hazan al., 2007) and natural gradient descent (Amari) 1998) use full-matrix preconditioner, but computing and storing the full matrix is infeasible when there are millions of parameters. Thus, diagonal versions such diagonal Adagrad, Adam (Kingma & Ba 2014), and RMSpprpp (Hinton et al. 2012) are now widely used to train DNNs due to their scalability.
Several higher-order methods have previously been applied to deep learning (Gupta let al. 2020 Goldfarb et al. 2020: Martens & Grosse 2015). All these methods use Kronecker prod- ucts that reduce computational and storage costs to make them feasible for training neural networks. However, these methods rely on matrix inverses or pth-roots that require high precision arithmetic as the matrices they deal with can have large condition numbers (Anil et al. 2020 2022). Meanwhile, deep learning hardware accelerators have evolved towards using lower precision (bfloat16, float int8) (Henry et al., 2019 Jouppi et al., 2017) to reduce overall computational and memory costs and improve training performance. This calls for further research in developing efficient optimiza- tion techniques that work with low precision. Indeed there is recent work along these directions, from careful quantization of Adam (Dettmers al. (021) to 8-bits to optimizer agnostic local loss optimization (Amid et al. 2022) that leverage first-order methods to match higher-orde methods.
2018 Anil
In this paper, we present a first attempt towards computationally efficient sparse preconditioners for DNN training. Regret analysis when using a preconditioner reveals that the error is bounded by two summations (see (3) below); the first summation depends on the change in the precondi- tioning matrix, while the second depends the generalized gradient norm. We take the approach

---

Under review as a conference paper at ICLR 2023
of minimizing the second term while regularizing two successive preconditioners to be close in the LogDet matrix divergence measure (Kulis et al., 2009). This technique gives us an Online Newton method (Hazan et al. 2007). To make it computationally efficient, we further sparsify the precondi- tioner by finding sparse approximation that is close in LogDet divergence. Thus we are consistent in using the same measure (LogDDet divergence) in both the regularization and sparsification steps. This gives us our Sparsified Online Newton (SONew) method, which only requires (n)) time and memory complexity per iteration. We achieve this by imposing structured sparsity, such tridiag- onal and banded sparsity patterns, in the preconditioner. This is unlike most existing online Newton methods that require least (n²) space and time complexity. By making each step linear time, the SONew method can be applied to train modern DNNs. Further, for some sparsity structures, our method is easily parallelized thus making negligible the overhead computing the preconditioner. We also show that introducing sparsity allows us to reduce the condition number of the problem; as a consequence our preconditioner allows us to train DNNs even in low precision arithmetic.
We establish regret bound guarantees of our algorithm in the online convex optimization frame- work. This involves using various properties about LogDet divergence and connections to other Bregman matrix divergences (Bregman 1967), such as the von Neumann matrix divergence (Kulis) et al. 2009). We conduct experiments on MLP Autoencoder, where we obtain better training loss compared to first order methods. We also conduct experiments on large-scale benchmarks in Appendix (A.5] and observe comparable or improved performance than Adam (Kingma & Ba (014). Our MLP experiments in limited precision arithmetic (bfloat16) showed comparable performance with second-order methods, while being considerably faster.
2
BACKGROUND
The inner product between matrices is defined () Ir where Tr(.) denotes the matrix trace. The Frobenius norm of matrix A is || AT)(ATA), while its spectral norm is ||Al|2 = max, | / ||ا|||- We use J E |R== to denote an identity matrix. We use Sn, S to denote the set of symmetric, and positive definite matrices respectively. The generalized norm of vector 2 E R with respect to matrix A E S is defined as | = VxT Ax. We use det (A) to denote the determinant of matrix A, and diag(A) to denote diagonal matrix with diag( (A);s = An-- Let Eg denote set of edges in graph G. and (ii denote neighbours of vertex i in graph G. The sparsity graph/pattern of matrix A Rnx is graph with edges Eg = {(i,j) : Ai F 0} corresponding to the non-zero entries in A. We extensively use (9)++ to denote the set of positive definite
We use G and & to denote a graph and its sub-graph with vertex set [n] {l...., n..
matrices with sparsity structure given by graph G. Given an index set I { (11,2,,... 12,,2,,.. bn Air to denote the corresponding principal sub-matrix of A.
2.1 LOGDET MATRIX DIVERGENCE
Let Φ + + RR be a strictly convex, differentiable function. Then the Bregman matrix divergence between X, Y E S is defined as (Bregman 1967: Kulis et 2009):
(x,))) = ((X) o(Y) (xV
Since ó is convex, D U) 2 0 for all X,Y 0. A well known example is when ((X) ||X
the corresponding Bregman divergence (X, Y) ||X
- -YIī is the squared Frobenius norm. In this paper, we extensively use the divergence when the convex function is ((X)= = log det (X); the corresponding divergence measure Dea (X, Y) is called the LogDet matrix divergence:
Y) log det (XY-1) Tr(XY-1) n.
(1)
The LogDet divergence is scale invariant invertible matrices A, i.c. Da,
Dea Xx Y). The following revealing form of LogDet divergence in terms of eigendecompooitions of X = VAVT and Y UOUT (Kulis et 2009)
(xa = ΣΣ (uf u, 2 log (x,,)) -1).
(2)
These two properties are later used in Section to highlight the significance of LogDet divergence in our algorithm.
2

---

Under review as a conference paper at ICLR 2023
3
SONEW: SPARSIFIED ONLINE NEWTON METHOD
We now present our proposed SONew algorithm.
3.1 REGRET MINIMIZATION VIA LOGDET DIVERGENCE
We set up our problem under the online convex optimization framework (OCO) (Shalev-Shwartz al. 2012, Hazan al. al., 2016), where at each round the learner makes prediction we an online fashion and receives convex loss fi f(;)) and gradient Jr = f((w)) as feedback. The goal of the learner is to reduce regret Rr by predicting wy so that low aggregate loss Σ fi(w)) is achieved compared to the best possible, w² = arg min Et f((w). Formally, the regret is given by
T RT(wi, WT) = Ei(w)) - - Ee(w")..
1=1
To upper bound this regret, proceed as in Hazan et al. (2016) by analyzing the error in the iterates for the update w4+1 we 19h where X, E Ruxx Then || w
Ixx
I|w, '2 w" xxx ||l, w x g7 X19t 2n(ww, w* 9.- The convexity of (T
ft implies that f((we) f((w)) S (we "TT gi leading to f((w)) f((w)) s ||w, w x
||++11 - w' 18x n nr=9; Xig. Summing over all E [T] and rearranging reveals the following upper bound on overall regret:
RT 2n |ml w" "I, + 2n Σ w w
(X)'XX," - -x w²) -=)+
9 Xigi (3)
t=1
Since w" is unknown, finding X₂ which minimizes 33) is infeasible. So to minimize regret, we attempt to minimize the last term in (3) while regularizing X, to be "close" to X, The nearness measure we choose is the LogDet matrix divergence, thus leading to the following objective
X, arg miyming ot Xgi, such that Dea (X, X11) S ct: XES,
where Dea is as in II. Why do we use the LogDet divergence? From 2 due to the term A Dea(X,X,-11 priortizes matching the smaller eigenvalues of X with those of X, i.c., matching the larger eigenvalues of X,-, and X As consequence, LogDet divergence regularizes X by matching up its large eigenvalues with those of X,-1. For e.g., if smallest and largest eigenvalue of X,-1 O₂ and f1. then for eigenvalue of X, when À > on.. f1 the penalty from ? for On is higher than for 0,, (2/0, - log(A/O,,) - 1) > (A/0; - logí ()1() 1). This intuition leads to formulate 44) as objective. We recall that there precedence of using the LogDet divergence in the optimization literature; indeed the celebrated BFGS algorithm (Broyden) 1967, Fletcher 1970 Goldfarb 1970 Shanno 1970) can be shown to be the unique solution obtained when the LogDet divergence between successive preconditioners, subject to a secant constraint, is minimized (as shown in the beautiful 4- 4-page paper by Fletcher (199T)).
The optimization problem in 44h convex in X since the LogDet divergence convex in its first argument. The Lagrange Z(X.>) = 9f X + (X, - ca) = Tr(X ) + A log det (XX;1) + Tr(XX,=)) - n)). Setting VL(X, = 0, and using the fact that V log det (X) = X we get the following update rule:
x-²= + 9:9t />..
(5)
Note that setting 0 (equivalently A; x0) Vt E [n|] in (4) results in change to the pre- conditioner in any round. this case, with Xo = In we get online gradient descent (Zinkevich) 2003). On the other hand, setting de gives the update rule of the online Newton method Hazan et al. 2007). Our update rule differs from (full-matrix) Adagrad (Duchi et al. 2011b) which has X
9:96.
Maintaining and updating X, in (5) is possible by using Sherman-Morrin Morrison formula but requires (n²) storage and time complexity. This becomes impractical when n is in the order millions which is typically the case in DNNs.
3

---

Under review as a conference paper at ICLR 2023
Algorithm 1 Sparsified (SONew) Algorithm
Online
Newton
Algorithm 2 SPARSIFIED INVERSE(H, 9) in n)) flops
Inputs: ) == coefficient the update (
Inputs:H E (9)) is as (O).
g = sparsity graph (banded/ridiagonaa),
G == the banded graph of band size <
= damping parameter,
Outputs: lower triangular banded L E R
T total number of iterations/mini-batthess,,
and diagonal matrix E R
7) == step size/learning rate.
function SPARSIFIED INVERSE(H.
Output: wr-1
2:
=== 0, D ==
1: Ho = ela. w1 =
3:
Ly = 1, Vj E [n]
2: for E [1..... T) do
4:
for E fl) do
parallelizable
3:
compute = (w.
5:
Let Hzg and Hrg be defined as in Section {i 1,....J + [n].
4:
H, H1-1 Po Polgig /2a) E (g) with
where I
Pg as in (8)
b (m) time & memory
5:
Get L, SPARSIFIED INVERSE (Hr, 9).
6:
Solve for L1,5 in the linear system HI L1,5 HHss D DO(b") time.
where X, = LDL" solves 1II.
6:
Compute update N, = LDL" gt.
7:
D3 = 1/( + H1,5)
7: We++1 = We M/
end for
8:
end for
9: return I,,
9:
return WT+11
10: end function
3.2 SPARSIFYING THE PRECONDITIONER
To reduce the memory required to maintain and update X, using (5) we consider the follow- ing general problem: find sparse X > O with |X]lu I an, (a,XX(X,
1, such that the objective 969 /xe) is minimized. Due to the Lg-norm constraint, this is non-convex problem, which makes it difficult to solve exactly. Since L norm serves convex relaxation for the Lg norm, we could use instead, resulting in the following optimization problem also known as graphical lasso estimator (Friedman et al. 2008):
min Dea (X, (X + 9696 (A +X|IXII1 XEST
The sparsity introduced by I,2 norm penalty will reduce the memory usage. However, the time taken to solve the above problem, even with the current best methods (Bollhöter et al.) 2019 Hsieh et al.)
2013 Fattahi & Sojoudi 2019 Zhang et al. 2018)) can still be too large (as these methods take several minutes for matrix of size million). making it impractical to embed in DNN training since preconditioning may need to be done after processing every mini-batch
In this paper, we take different direction where we use fixed sparsity pattern constraints, specified by a fixed undirected graph G. To sparsify the solution in (5), we formulate the subproblem
X arg arg Dea (X; (X + 9:96 - (0)+
where Sn (g)++ denotes the set of positive definite matrices with the fixed sparsity pattern given by graph G. Note that even for sparsification we use the LogDet measure; thus both the steps and (6) use the same measure.
Algorithm presents one proposed SONew method, which solves 66) using ((n) time and memory for banded matrices with band size b, in particular a tridiagonal matrix, corresponding chain graph, is a banded matrix with bandsize 1.
Maintaining H, E (g) in line 4 Solving the subproblem in (6 naively is impractical since X is a dense matrix. However, the structure of the LogDet divergence comes to the rescue; ( can be expanded as follows:
X arg min - log det (X) + Tr(X + 96966 /Ae)).
X (C)+
Let us define the projection onto S, Pg Rax + Bu as:
{ Ma
{
if (1. E Eg. otherwise
Po(M)
{0-
(8)
4

---

Under review as a conference paper at ICLR 2023
Note that the Tr(.) term in 7 involves only the non-zero elements of X S,( Hence, 7 can be written as
X, arg min log det (X) + TTXP) + 9 /xe)),
(G)+
Computing matrix can be avoided by analyzing optimality condition (9) Let g(X) be objective function in then the optimality condition of (9) is Pg(Vg(X)) =U. Expanding g gives
1) = Po + 9:9 (x)) = Po(X + Polg.ot /Ae),
H, = H1-1 + Po(gegt /
(10)
Thus we only need maintain H, E (9), which is H, Po This matrix updated as H, = H, + (9 /A,), which can be done in ([Eg)) memory and time, while computing the matrix X, would have cost On?²). In SONew, this key observation is used to maintain H; in 4ine
Computing X₂ in line 5 Now that H, is known at every round we can replace Po + 9:9 (Xe) with H, as:
X₂ arg min log det (X) Tr(XH)).
(11)
(9)
For arbitrary graph G, solving this subproblem might be difficult. Theorems and show embar- rassingly parallelizable explicit solutions to the subproblem TT for tridiagonal and banded sparsity patterns. Proofs of Theorems 1 and
2 are given in Appendix A.
Theorem (Explicit solution of I for tridiagonal matrix/chain graph). Let the sparsity structure
be chain with edges Eg [G.j + 1) j E [n - 1]}, and E Sn(9), then the solution
of (11) is given by & LDL", where the unil lower triangular matrix L and diagonal matrix D have the following non-zero entries:
Hjti H5+1541*
H3r1j
Toj 1, Litay
Djj
Hjj
issn
D H
(12)
H5t15+1
The time and memory complexity required to compute 12 is On)). Note that the computation of
12 can be easily parallelized. This explicit solution can be generalized to banded sparsity structures
with band size b.
Theorem (Explicit solution of (11) for banded matrices). Let the sparsity pattern be
banded matrix of band size b, iee. for every vertex j, let I; {j + 1.....j + b), then edges
Eg = U²= {i} x I2) n {(i.j) i n. S n). Then X; = LDL is the solution of (11 with nonzero entries of L and D defined as follows:
= =1 L1, = -Hi,), HIg5 D (H₃ HI, HT, H1,5), 15isn.
(13)
Finding the above solution requires solving linear systems of size b (which is small) shown in Algorithm [] and takes O((n - b 1)5²) flops. Since & the number of flops is O(n).
3.3 ANALYSIS OF SONEW
The following theorem establishes regret guarantees of SONew online convex optimization frame- work mentioned in Section
Theorem 3. When G = tridiagona/chain graph, then Algorithm 7 incurs the following regret under convex losses ft
3/4
1 11+8 3
1/2
91.
n
Rr < 0 01/2.73/4
i-
Σ
log
1
log (1 -3.)
6
5

---

Under review as a conference paper at ICLR 2023
(8) where Fi:r ((9) .. denotes gradient history it variable/parumeter G (1
C== max, 1 ) 3, -
91:7--1777
denotes dot- poo--rrduct between
Vco+ll999 D (ct (6t1)
gradient histories of connected parameters in the chain graph, 3 max
SONew is scale-invariant to diagonal transformation of gradients; if the gradients sent feedback to the OCO learner are St = Agr. then the iterates for the transformed problem will be o = A A = A 11 It-1 It-1 n(A A X -! A9 this is due to scale-invariance property of LogDet divergence Section 2.1 i.e. the transformed preconditioner is X, = A -- 11-1 Furthermore, the regret bound derived in Theorem transformed and original problem is approximately same. Our regret bound is data-dependent, since if 3 is nearer to 1, then the regret is smaller due to the log(1 ( term. This effect is more amplified when log(1 + 1191:T | l2/c) is relatively low compared to log(1 1 88). The proof for Theorem 3 is given in Appendix A.2 We also derive regret bound with ((VET1/2) dependency T in Appendix A.3 where the condition number
xi r(diagg(Hy) H,)) S n.
NUMERICAL STABILITY OF SONEW
The matrix H (G) given as imput Algorithm 2 should have positive definite submatrices Hردرر J, = U (j). E [n]. where I is as in Theorem 2 hence, it should have positive schur complements (H₃ HF, 1,1, H155). But, if the matrices HJJJ,, and H1,1, are illconditioned, then the computed value for (H + +H Lı,,) = (H, H Hi,s). in line of Algorithm 2 can be zero or negative due to catastrophic cancellation, since finding Lı, --H 1,1, H1ys in floating point arithmetic can result in rounding errors. To understand this issue further, we conduct perturbation analysis in Theorem 4 which establishes componentwise condition number (Higham 2002) of the optimization problem in (IT) with a tridiagonal sparsity structure G.
Theorem (Condition number of tridiagonal LogDet subproblem 11,. Let H St+ be such that H. = 1 for i E [n]. Let AH be a symmetric perturbation such that AH = 0 0 i E [n], and
H + AH E St Let (I) be the input to 11 where G is chain graph, then
Kigo
.d
max sE(n-1]
2/(1 101--831 -10)) Ree
ld
(14)
where, B, Hig 1 componentwise condition number of 11 for perturbation AH.
So, the tridiagonal LogDet problem with inputs H as mentioned in Theorem 4 has high con- dition number when 1 - B Hs;
are low and as a result the precondi- tioner X, in SONew (Algorithm [ has high componentwise relative errors. In SONew ( the H, = Po 9=92 /x)) generated line 4 could be such that the matrix E not be positive definite and the schur complements H4, / can be zero, giving an infinite condition number xddd by Theorem The following lemma describes such cases in detail for more general banded sparsity structure case.
need
Lemma 1 (Degenerate inputs to banded LogDet subproblem). Let H = Po(GG")), where G E ReXT and let g be ith row of G, which is gradients of parameter for T rounds, then Hij (000911)
Firr 91.)
Case 1: For tridiagonal sparsity structure G: if gift (141). then His Wis41/HJ41JH =0. 0.
g
Case 2: For b > in 13:: If rank(H,,,,) = rank(Hi,1,) b. then (H₃j H1,5) = 0 and Djj = co. If rank H,, < then the inverse Hi,,, doesn't 't exist and Djj is not well-defined.
If GGT = E 9:9: is a singular matrix, then solution to the LogDet problem might not be well- defined as shown in Lemma I For instance, Case I can occur when preconditioning the input layer
'The full version of Theorem along with proof is given in Appendix A.4

---

Under review as a conference paper at ICLR 2023
of an image-based DNN with flattened image inputs, where jth and (j + 1)thh pixel can be highly correlated throughout the dataset. Case can occur in the first b iterations in Algorithm when the rank of submatrices rank 1,,,) degenerate inputs H, given that Ha > O. It finds a subgraph & of G for which (13 well-defined.
b and of We develop Algorithm 3 which is robust to
This is done by removing edges which causes inverse H to be singular or H H1 to be low. Our ablation study in Table 4 demonstrates noticeable improvement in performance Algorithm 3 is used.
Theorem 5 (Numerically stable algorithm). Algorithm 3 finds a subgraph & of G, such that
plicit solution for 9 in (3) is well-defined. Furthermore, when G is tridiagonal/chain graph, the component-wise condition number upperbound in (14) is reduced upon using Algorithm 3
a aG where Red Rea are defined as in Theorem 4 for graphs & and G respectively.
Ed < ti
The proofs for Lemma 1 and Theorem are given in Appendix A.4
Algorithm 3 Numerically stable banded I LegDet solution
1: Input: G- tridiagonal or banded graph, H symmetric matrix x=*x" with sparsity structure G and Hi > O, 7- tolerance parameter for low schur complements.
2: Output: Finds subgraph 9 of 9 without any degenerate cases from Lemma 1 and finds preconditioner X corresponding to the subgraph
3: Let E. = ((t.j) : (i.j) E E be edges from vertex to its neighbours in graph G.
4: Let V,+ [j :1 <. (1, E Fig} and V, {j 1 j. (1,5) Fig), denote positive and negative
neighbourhood of vertex
5: Let K = {i: Hs Hi,, HI, is not defined or 7 E [m]}
6: Consider a new subgraph with edges Eg = Eg \ (Uiex E. U UV,+ x V,))
7: return = SPARSIFIED INVERSE (Hr, 9), where Hr = (HHH
5 RELATED WORK
Online Newton method a second order method in online convex optimization framework with properties such as scale invariance (Luo al. 2016) and logarithmic regrets in exp-concave and strongly convex functions (Hazan et al. 2007 2016). However, it has a time complexity of O(n²). making it infeasible for large n. A diagonal version of this method SC-Adagrad (Mukkamala & Hein 2017) was proposed to make the online Newton method scalable for deep-learning. SC- Adagrad equivalent to setting the sparsity pattern in equation TT as null graph, furthermore, setting G as complete graph will result in online Newton method. However, introduction of LogDet divergence measure in SONew allows us to set different sparsity graphs as & such as banded graph with band-size b, for which our preconditioning process is more computationally efficient with time complexity of (bb²(n (n - b + 1)) compared to online-newton method (n²). As discussed in Theorem 3 SONew also utilizes correlation among gradients of parameters improve convergence, in contrast to diagonal preconditioners such as SC-Adagaad.
Shampoo Gupta et al., 2018 Anil et al. 2020) uses Kronecker factored preconditioners to reduce the memory and time complexity from O( to Odl + d)) and O + dB)) respectively, where n = did2 denotes number of parameters for a linear layer of dimensions di x d2. The time com- plexity of matrix inversion takes a heavy toll in Shampoo' compute time even with the Kronecker product assumption on the preconditioner, whereas, our method has a time complexity of O ((bdddd)) d2) quadratic dimensions of the linear layer (note that b = 1 for tridiagonal structure). Furthermore, precision lost in matrix inversion can be large due to high condition number matrices occurring in training (Anil et al. 2022. 2020).
LogDet problem in equation
closely related to the Maximum Determinant Matrix Comple-
tion (MDMC) (Andersen et al. 2013] Vandenberghe et al. 2015). The MDMC problem is the dual of LogDet problem (I]), and has explicit solutions for chordal graphs (Andersen et al. 2013). Thus the explicit solutions in (L3) are the same as the ones proved in Andersen et al. (2013). 3). Also, we noticed that the tridiagonal explicit solution has been used previously in KFAC (Martens Grosse) 2013) in the context of gaussian graphical model interpretation of gradients. In this paper we also analyze conditioning and degenerate cases of these explicit solutions (which can occur frequently in
This is proved in Appendix A.4
7

---

Under review as a conference paper at ICLR 2023
DNN training) and develop algorithms to avoid such cases. In addition, have regret guarantees connecting these explicit solutions to regret in online convex optimization problem setup. There is prior work (Luo et al., 2016 2019) in reducing the complexity On²²) flops of Online Newton Step (ONS) to (n) flops using sketching. These ONS variants maintain a low rank approximation of H2 (as in Algorithm I and updating it with new gradient dt. at every iteration requires conduct- ing SVD (Luo et al. 9019/oorhoooooaiiiationn (Luo et al. 2016) of tall and thin matrix in Rexr, where r denotes the rank of approximation of Ilg. Our proposed method (Algorithm [ has a more parallelizable update H₁ == Hi-1 + Po(g9g!) making it more suitable for DNN training.
EXPERIMENTAL RESULTS
In this section we describe our experiments on Autoencoder benchmark (Schmidhuber 2015) using MNIST dataset (Deng] 2012). Our results on larger benchmarks are given in Appendix AA.5| We compare SONew against commonly used first order methods including SGD (Kiefer & Wolfowitz, D SGD with Momentum (Qian 1999), Nesterov (Nesterov) 1983). Adagrad (Duchi et al,, 20) Adam (Kingma& & Ba 2014). and Risprop (Tieleman & Hinton 2012). We also compare with Shampoo (Gupta et al. 2018), state of the art second-order optimizer used in practice. Com- puting preconditioner every step in shampoo could be infeasible, instead computed every steps referred to as Shampoo(t) in the experiments.
For SONew, we use exponentially moving average (EMA) for both first order and second order statistics. EMA is commonly used in adaptive optimizers for deep-learning training Kingma Ba 2014 Qian (1999). Let $1. 32 E [0, 1] be the coefficients for EMA and Jt E R be the gradient at 8thh itterttio/mmii-aaaiii batch Let Mr E IR"" be the first order gradient statistic, and H, E S,, (9) be the second order gradient statistic as in (TO.. Then, the following modification to update rules are made to in the SONew implementation.
Hi = 3114-11 + (1 - 31)9 = (1
Furthermore, (4 is used in W++11 = Xette replacing the gradient gt. similar to Kingma & Ba (2114). As discussed in Section 3.2 we need to store the values of H, only corresponding to the sparsity pattern, hence SONew uses (n) space. The updates above get computed in parallel in (1) time. Moreover, we use Algorithm 3 to make SONew numerically stable. We also use graft- ing (Agarwal et al.] 2022), a technique used to transfer step size between optimization algorithms. Specifically, given an update ei of Optimizer-I and d2 of Optimizer-2, grafting allows to use the direction suggested by Optimizer-2 with step size suggested by Optimizer-1. The final update is given by ||>]|| U2. Grafting has been shown take advantage of tuned optimizer step size and improve performance. In our case, we use Adam grafting using Adam optimizer step size ||uh ll with SONew direction "2/I1=all-
||>1]]
We use three sparsity patterns for SONew a) diagonal sparsity, resulting in diagonal precondi- tioner similar to adaptive first order methods like Adam and Adagrad; b) tridiagonal sparsity, corre- sponding a chain graph; and e) banded sparsity, represented by "band-k" in tables and figures for band size of k.
All the baselines and SONew are trained for 100 epochs and use the train set of MNIST dataset containing 60k points. We use a standard sized (2.72M parameters) Autoencoder with layer sizes: [1000, 500, 250, 30, 250, 500, 1000] and tanh non-linearity. Batch size is fixed at 1000 and we use leamning rate schedule with a linear warmup of 5 epochs followed by linear decay towards Over 2k hyperparameters are searched over for each experiment using a Bayesian optimization package. The search space for each optimizer is mentioned in Appendix A..5 A.5
From the float32 experiments in Table | we observe that among first order methods, diag- SOaee performs the best while taking same amount of time. Increasing the number of edges in the sparsity graph to tridiag or banded with band size enhances the performance further. Tridiag-SONew performs 4x faster than Shampoo at marginal cost to the loss even when Shampoo updates preconditioner once every 20 steps. When dealing with large scale models like Resnet50 (He et al., 2015a), Shampoo requires updating preconditioner much more often (Aill et al. 2019), whereas our method is also promising in such scenarios. We leave comparison of SONew with Shampoo on such large benchmarks conduct bfloat16 experiments. We notice in Table thht SONeww performs the best in first order methods, just like in float32. Moreover SONew undergoes the least degradation in performance
future work. To show efficacy of SONew at lower precision,
8

---

Under review as a conference paper at ICLR 2023
Table 1: float32 experiments on Autoencoder benchmark. "tridiag" repersents tridiag- SONew, "band- 4" represents Munded-SONew with band size 4. We observe that diag- diaew performs the best among all first order methods while taking similar time. tridiag and band-4 perform significantly better than first order methads while requiring similar linear space and being marginally slower. Shampoo performs best but takes (dd") time for computing preconditioner of linear layer of size d whereas methods take ((d²) find the precondioner.
Optimizer
Methods
Methods
SGD
Nesterov
Adagrad
Momentum
RMSProp
Adam
diug-SONew
Shumpow(22)
triding
hund-4
loss
59.087
53.330
51.723
51.357
Time(s)
62
102
62
67
62
62
63
371 87
251
Table 2: bfloat16 experiments on Autoencoder benchmark. diag SONee performs the best among all first order methods, while degrading only marginally (0.26 absolute difference) compared to float32 performance. tridiag-SONew and handed-SONer holds similar observations as well. Shampoo performs the best but has considerable drop (0.70) in performance compared float32 due to using matrix inverse, and is slower due to its cubic time complexity for computing preconditioners. Shampoo implementation uses 16-bit quantization to make it work in 16-bit setting, leading to further slowdown. Hence the running time in b6loat is even higher
than in float32.
Optimizer
Order Methods
Second Methods
SGD
Nesterov
Adagrad
Momentum
RMSProp
Adam
diag-SONew New Shampoo(20)
triding
hand-4
Train CE loss
80,454
72.975
68.854
70.053
53.743
54.328
53.29
51,401
51,937
51.84
Train time(s)
502
70
Nomentum
Nesterov
AdaGrad
train loss
train less
60
RMSProp
Momentum
Nasterov
60
d'aq_sonew
shampoo(20)
AdeGred
Adam
tridieg
RMSProp
band-4
54
53
2hampoo(20)
54
52
tridieg
53
51
cand-4
52
51
50
60
80
100
epachs
epachs
(a) float32
(b) bfloat16
Figure I: (a) Comparison of SONew (tridiag, band-4) 4) with first-order optimizers and Shampoo (sccond-orden Left (a) uses float32 training and right (b) uses bíloat16 training. We observe that tridiag and banded SONew have better convergence compared shampoo in lower precision early stages, and performs better than all first order methods in float32 and bfloat16.
compared to all other optimizers. We also provide an ablation study on effect of using Algorithm training loss in the appendix.
CONCLUSIONS AND FUTURE WORK
In this paper have introduced a computationally efficient sparse preconditioner. Our algorithm arises from a novel regret bound analysis using LogDet Divergence, and furthermore we make numerically stable. Experimental results the Autoencoder benchmark confirm the effectiveness of SONew in both float32 as well as 6 precision. In the future, one can explore different sparsity graphs for which efficient solutions exist for the LogDet subproblem
REFERENCES
Naman Agarwal, Rohan Anil, Elad Hazan, Tomer Koren, and Cyril Zhang. Learning rate grafting: Transferability of optimizer tuning. 2022.

---

Under review as a conference paper at ICLR 2023
Shun-Ichi Amari. Natural gradient works efficiently in learning. Neural computation, 10(2):251- 276, 1998.
Ehsan Amid, Rohan Anil, and Manfred Warmuth. Locoprop: Enhancing backprop via local loss optimization. In International Conference on Artificial Intelligence and Statistics, pp. 9626-9642. PMLR, 2022.
Martin S Andersen, Joachim Dahl, and Lieven Vandenberghe. Logarithmic barriers for sparse matrix cones. Oplimization Methods and Software, 28(3):396-422 2013.
Rohan Anil, Vineet Gupta, Tomer Koren, and Yoram Singer. Memory-eeficient adaptive optimiza- tion, 2019. URL
11150
Rohan Anil, Vineet Gupta, Tomer Koren, Kevin Regan, and Yoram Singer. Scalable second order optimization for deep learning. arXiv preprint 2rXiv:2002.09018. 2020.
Rohan Anil, Sandra Gadanho, Da Huang, Nijith Jacob, Zhuoshu Li, Dong Lin, Todd Phillips, Cristina Pop, Kevin Regan, Gil I Shamir, et al. On the factory floor: MI engineerrg for industrial- scale ads recommendation models. arXiv preprint arXiv:2209.053 2022.
Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Sanchez-Gonzaler Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Caglar Gulcehre, Francis Song. Andrew Ballard, Justin Gilmer, George Dahl, Ashish Vaswani, Kelsey Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matt Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascanu. Relational inductive biases, deep learning, and graph networks, 2018. URL URL/tttss: wwwp//aaivvvvv/// www.w/viwwrr/ooooooo abs 1806. 01261
Matthias Bollhöfer, Aryan Eftekhari, Simon Scheidegger, and Olaf Schenk. Large-scale sparse inverse covariance matrix estimation. SIAM Journal on Scientific Computing, 41(1):A380~441,, 2019.
Lev M Bregman. The relaxation method of finding the common point of convex sets and its applica- tion to the solution problems in convex programming. USSR computational mathematics and mathematical physics, 7(3):200-217, 1967.
Charles G Broyden. Quasi-Newton Newton methods and their application function minimisation. Mathe- matics of Computation, 2 (199)))668-31, 1967.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hier- archical image database. In 2009 IEEE Conference Computer Vision and Pattern Recognition, pp. 248-255, 2009, doi: 10.
Li Deng. The MNIST database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 19(6):141-142, 2012.
Tim Dettmers, Mike Lewis, Sam Shleifer, and Luke Zettlemoyer. 8-bit optimizers via bisek-wise quantization. arXiv preprint 2x.::22:100002660 2021.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszko- reit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale, 2020. URL https:://// /ttp///aivvv////////////..//..al http:/twwwiaaaaaaaa.aaaoo wwg//rg//aab....o.. http://bbb/2...... 11929
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, (161):2121-2159 2011a. URL
http:// http://mmmmooororappp/m
www.///ppppp.a.... v1 2./ duchiichhii1 htmml
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 201 1b.
Salar Fattahi and Somayeh Sojoudi. Graphical lasso and thresholding: Equivalence and closed-form solutions. Journal of machine learning research, 2019.
10

---

Under review as a conference paper at ICLR 2023
Roger Fletcher. A new approach to variable metric algorithms. The computer journal, 13(3):317- 322, 1970.
Roger Fletcher. A new variational result for quasi-Newton formulae. SIAM Journal on Optinization, 1(1):18-21 21, 1991.
Jerome Friedman, Trevor Hastie, and Robert Tibshirani. Sparse inverse covariance estimation with the graphical lasso. Biostatistics, 9(3):332-44 1414224111,,2 2008.
Jonathan Godwin Thomas Keck*, Peter Battaglia, Victor Bapst, Thomas Kipf, Yujia Li, Kimberly Stachenfeld, Petar Veličković, and Alvaro Sanzhez- Jraph: A library for graph neural networks in jax., 2020. URL http:////ggihabb...cc//eemmmo/dd jraph
Donald Goldfarb. A family of variable-metric methods derived by variational means, Mathematics of computation, 24 24(109):23-266 1970.
Donald Goldfarb, Yi Ren, and Achraf Bahamou. Practical quasi-Newton methods for training deep neural networks. Advances in Neural Information Processing Systems, 2322866-2396, 2020.
Vineet Gupta, Tomer Koren, and Yoram Singer. Shampoo: Preconditioned stochastic tensor opti-
mization. In International Conference on Machine Learning, pp. 1842-1850. PMLR, 2018
Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Muchine Learning, 69(2):169-192, 2007.
Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Opti- mization, 217-45) 2016.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learningfor image recog- nition. ComputerScience, 2015a.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition, 2015b. URL htt.aaae/aaavvv.rraaa/////LLL/// 03385
Greg Henry, Ping Tak Peter Tang, and Alexander Heinecke. Leveraging the 6float16 artificial intel- ligence datatype for nigher-precisiie computations. In 2019 IEEE 26th Symposium Computer Arithmetic (ARITH), pp. 69-76. IEEE, 2019.
Nicholas Higham. Accuracy and stability of numerical algorithms. SIAM, 2002.
Geoffrey Hinton, Nitish Srivastava, and Kevin Swersky. Neural networks for machine learning lecture 6a overview of mini-batch gradient descent. Cited on, 14(8):2, 2012.
Cho-Jui Hsieh, Mátyás Sustik, Inderjit S Dhillon, Pradeep K Ravikumar, and Russell Poldrack. BIG & QUIC: Sparse inverse covariance estimation for million variables. Advances in neural information processing systems, 26, 2013.
Weihua Hu, Mauthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs, 2020. URL
wrg/ abs 2005. 00687
Norman P Jouppi, Cliff Young. Nishant Patil, David Patterson, Gaurav Agrawal, Raminder Bajwa, Sarah Bates, Suresh Bhatia, Nan Boden, Al Borchers, et al. In-datacenter performance analysis of tensor processing unit. In Proceedings of the 44th annual international symposium on computer architecture, pp. 1-12, 2017.
J. Kiefer and J. Wolfowitz. Stochastic Estimation of the Maximum of a Regression Function. The 466, 1952, doi: 117229999// URL https: /ww. http://///oo..r//...oo 1214 aoms 1177729392
Annals of Mathematical Statistics, 23(3):462
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint
arXiv: 14/2,690, 2014.
Brian Kulis, Mátyás A Sustik, and Inderjit Dhillon. Low-rank kernel learning with Bregman matrix divergences. Journal of Machine Learning Research, 10(2), 2009.

---

Under review as a conference paper at ICLR 2023
G Lindblad. Completely positive maps and entropy inequalities. 1975.
Haipeng Luo, Alekh Agarwal, Nicolo Cesa-Bianchi and John Langford. Efficient second order online learning by sketching, Advances Neural Information Processing Systems, 29, 2016.
Luo Luo, Cheng Chen, Zhihua Zhang, Wu-Jun Li, and Tong Zhang. Robust frequent directions with application in online learning. The Journal of Machine Learning Research, 20(1):197-11337, 2019.
James Martens and Roger Grosse. Optimizing neural networks with Kronecker-factored approxi- mate curvature. In International conference machine learning, pp. 2408-2417. PMLR, 2015.
Mahesh Chandra Mukkamala and Matthias Hein. Variants of rmsprop and adagrad with logarithmic regret bounds. International conference on machine learning, pp. 2545-2553, PMLR, 2017.
Yurii Nesterov, method for unconstrained convex minimization problem with the rate of conver- gence o( (1 1983. 19883.
Ning Qian. On the momentum term in gradient descent learning algorithms. Neural Net- works, 12(1):145-151, 1999. ISSN 0893-6080. doi: hutp://0iioon////000006511s00000 wwt.://wwc.deieeeee......m..ee.e
00116-6. URL htttps://wwer sc encedi rectt httpt///ccceeee//arrailll/////// 50893608098001166
Jürgen Schmidhuber. Deep learning neural networks: An overview. Neural Networks, 61:85-
117. 2015. doi: h0006///nutee22214.00999 URL http:s///oo..orr//00000000..
Shai Shalev-Shwartz et al. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2):107-194, 2012.
David F Shanno. Conditioning of quasi-Newton methods for function minimization. Mathematics of computation, 24(111):647-656, 1970.
Tieleman and G. Hinton. Lecture 6.5-rpppoop: Divide the gradient by a running average of its recent magnitude. coursera: Neural networks for machine learning. 2012.
Lieven Vandenberghe, Martin S Andersen, et al. Chordal graphs and semidefinite optimization. Foun- dations and Trends Optimization, 144)2241 0401,14333110 2015.
Richard Zhang, Salar Fattahi, and Somayeh Sojoudi. Large-scale sparse inverse covariance estimation via thresholding and max-det matrix completion. In International Conference on Machine Learning, pp. 516557665777 5775. PMLR, 2018
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pp. 928-9998,...21199 2003.
A APPENDIX
A. PROPERTIES OF LOGDET SUBPROBLEM
Proof of Theorem
The optimality condition of
|I is
P
Let Z - --1- then P2( !l
ZL = L L- - ZLe, L
Let J, = I, J.j. then select Jj indices of vectors on both sides of the second equality.
7,jj
Zz1;
1
1/d
(15)
ZJ,J,
L1,
0
12

---

Under review as a conference paper at ICLR 2023
Note that L-T is upper triangular matrix with ones in the diagonal hence J/Mh block of L- will be 01,0,0,... ....... Also, since Pz
H
7
Zzzz
H3j H1g
H5t5 HJ
Zı,
ZJ
Substituting this in the linear equation
15
Hij
HaT,
1 [1
1/d55
Hi,5
HJ
H3
H3
dij
1
0
Hig
H1
dis L1,
=1 Hzgdi d3s H م1,3
Hj + d,y H1, L1, =0
The lemma follows from solving the above equations. Note that here we used that lower triangular halves of matrices L and H have the same sparsity patterns, which follows from the fact that banded graph is chordal and has a perfect elimination order [1,2....,
Proof of Theorem The proof follows trivially from Theorem when is set to
A.2 REGRET BOUND ANALYSIS
Proof of Theorem 3
To upperbound the regret we prove the following lemma about regret decompsition
Lemma 2 ( (Hazan et al. (2016) the OCO problem setup, a prediction we R is made at
round and updated as u++1 = X using preconditioner matrix X₁ E S
RT S
(1120 - w "1x - -| w xu'llx"))
(16)
21
T-1
[1++1 - (x(x - -x,1) - -w²)
(17)
217
t=1
T
Σ
!|
9t
T
X.9r
(18)
2
t=1
Proof.
|w041
w01l w=(1",,1 || nx w0 1|x,_
= ||w w" x,x- + 172 X.gt 20(ww: w² gt
21((w: - w0 " St = ||w - w" 1|x || w= w²'lx,-1 +on++
n2= gt X.9r
Using the convexity of St, fe(w:) - fe(w²) & (we - gt, where 9t = Ae(w)) and summing over E [T]
T
(Iw: w w0112,, -1-:1111111111 - - .) 2 o6 X.9r
RT <
(19)
2n
1=1
The first summation can be decomposed as follows
T
[10 - w² wI1 - || - =n 11x,)))) = (Iw1 -20 -101-=0011-- 10= -1|WT+1 =w= 10=1(a-1)
(we+1 w²) (2044 -w")
13

---

Under review as a conference paper at ICLR 2023
Substituting the above identity in the Equation (9) proves the lemma.
Let Rt < T + T2 + T3, where
. T1 2nj
1 ([lw1 - w0
"Ixx, xx, |1 - w x1x,')
T2 2n Ei= (w++11 w²) (X (w2t1 w²)
T3 Σt= 2 of Xigi
The following lemmas will be used to bound T,, T2. Ts.
Lemma 3. g = chain/rridiagonal graph and X arg mill XES, Dea (X, then the
inverse X-1 takes the following expression
Hij H. M. 1 Bas 15-15-1
11-1111
(X (8-
(20)
Proof.
x-1x0)= E
Where (() is the 9th column X. Let y denote the right hand side of Equation (0).
(F8) = Xx Vo + ش セー + x Yist1
Hز + Xy-1y + Xzs+1 H
=1
The third equality is by using the following alternative form of Equation
12
if -
(8 ).
(#: 1
14.441
if i+
(21)
(1+ EjEnniio()) H., H
if =
Hu
where K. Similarly, the offdiagonals of P& can be evaluated to zero as follows. (Fx),, YiyK,i Y &94t18,+11
Y + Yy, Hー-1j-1 Y1s
H5jt Xy+1j
HJ-15
H3g
Lemma 4. Let E R", B maxt maxie (H(H))z+1) // (HH))((H))))) < 1,
En 5 (G where Dir = (((n)) ((g)).... ... (oT) and G! = 1 then
1 8
y" x'x, S (Ct (1v1
3
Proof. Let X diag - 1/2
X, diag (H,) 11/2
2
yf x, ツ - diag( 1/2
(22)
Using the identity of spectral radius p(X) < | ooo and since X positive definite,
|x |x:1 5
|| | ||.0
Xx-1
< max Σ (XG 'aol
< 11+ 2(3 + B² + ....)
1+ 8
< 1- B
14

---

Under review as a conference paper at ICLR 2023
Using (H,)a | ||
The second inequality is using Lemma 3 the lemma.
in Equation 22 will give
Lemma 5 (Upperbound of Ti). Ti x
(C+eD)) 2n
1+8 I-3
where D2 = max 77] I|wl - w" l1 where
(8) C max, (v: ((G
Proof.
Since X7 is positive definite
| w= x
Ti 1
27
( X (2)
2n
Using Lemma 4 proves the lemma.
Upperbounding T2 Let Vr Wt w", Pt = oi X yt. and Q, = of vf Let P = [P2,'.. .. " and Q =
1Q Qrl be the two array representations. Then,
T-1 Σ
21/12
Met1 (Xi+) - x;²)) Mt+1
i=1
Σ 1=2
vi (X, - -x--)) 31
Σ 1=2
Vi T X,- U1 vē x
Σ P. Q
| QI1
(23)
In order upper bound this, derive here generalized version of Pinsker's inequality for our setting.
Lemma 6. Let A [A,, Ar] and B [B1, Br) be two T-length arrays. Let Bi, A > V E [1, T + 1). Then,
I - BI <
[2A B.) DKL(B,A)
where the generalized KL-Divergence (KI(B,A) = = (Bilog (1 B; + A1).
Proof. This proof is a mock up of Pinsker's inequality for probability spaces. First step involves using the following identity, for 2 -1
1 1
(1 ()log( +
12
2 1
Let
B. 4,
1. Then, -1 & 4. Therefore,
15

---

Under review as a conference paper at ICLR 2023
B;
(KI(B,A)
Σ
B, log
B; + A
A
1=1
Bi
Bi
B;
A
log
+1
A
A
A
Σ A ((t, + log(tt + +1) - t.)
A.l.
2 Σ
2 (1+
1=1
T Σ, 1m1
A
Σ jj= 4))
(BL(B,A)
2 (1 4/2
Σ Ax11+
ΣTh A,ltal)
(Using Cauchy-Schwand
2 Ei Ax(1 + 4)
ET |A, - Bil)
2
EL= (2Ax= + Bk)
A| -B11
Σラ (2Ar + B,)
Using the above to bound Equation
23
with B P'and& A = Q, get
T Σ
2T/T, = ||P 111 -
(2Q, + P.)
DKI(P,Q)
2
T
(2Qr + P.)
(KI(Pr
3
2=
T
Σ 1=2
(2Q, + P.)
DKi(u! X
vr, oi
T
Σ (2Qr + P.)
Σ DKI( 1 Ne. T (1))
T
Σ (2Q, + P.) 1
Σ Iellll DoN x
(24)
Here, U. Artr. X, = A,A,A, 8, A, DEN is von-Neuman Divergence, and last inequality is from Lindblad (9755). We upper bound Equation (44) using the following lemma.
Lemma 7. Let A, B be two PD matrices. Then,
DaN A, B) & (A) Dea (B, A)
16

---

Under review as a conference paper at ICLR 2023
Proof. Let A = VAVT and B UOUT
DuN(A, B) = Σ
(u? ug)
> log
A, +02
0
11
Σ (u, uy)d
log
1 +
0g
X
(- (-log
[0j
0j
S max A
Σ
(u3 Ug)
log
- 1 +
X
1.
Amar (A) Deaa(BB..
Combining the above result, we get
1
T2
P
Q112
27
1
Σ (2Qr+ + P.)
Σ 11 11 Dea (xa 8,1)
27)
3
1
Σ (2Qr + P.)
Σ
1
|
(x
3
27
The second inequality due to scale invariance of LogDet divergence. If we set A, diag(H,) 1/22 then using Lemma
T
1 Th
<
2
Σ (2Qr + P.)
Σ
(Ct+eelb (1o01)
1 (1 B (1-3)
Dea(X
21
3
T
1
2
Σ (2Q, + PP)
(CT + +DD)
1 3 T-
Σ Dea Dea(X
21j
3
< (CT +DD3)
1 21j
1 8 (1-3
2
T Σ Dra(X
(25)
3
where, D2 = max: Il ll. the second and third inequality is using Lemma 4 (e, X, ') term in the above equation, we develop the following lemma.
Now to bound the
Lemma 8. Tr(X,H,)
Vt E (2....,T) T in Algorithm 7 with any g
Proof. ))(X, = H, is an optimality condition of Leg subproblem Equation Tr(X,H,) = Tr(x) = Tr((X,x,1) n
The second equality is because X, follows the sparsity graph G.
Lemma 9.
Σ Dra Dra(X x s log( det (X,.1)
det (X-1)
(6)
91.T
log
1
log (1 -B8))
6
17

---

Under review as a conference paper at ICLR 2023
(0) 11
where B, =
(ct pl
(3)
Met
Proof. LogDet divergence is defined as follows
det (X,-1)
(ixxxixxx"" = -loo
+ Tr(X
1-1
det (X,
The second two terms on right hand side can be simplified analyzed as follows.
Tr(X;=1 -
-
-
of Xigt
<0
(26)
Thus
T
T
det (Xi1)
Dea 1x
1
- loo
det (X;
f=2
det (Xx*)
I log
det (XT-1)
Since LogDet divergence is positive
det (Xr-1)
Dea(X X;-)
-lo
+ Tr(Xx - det (Xr-)
det (X,²)
log The second inequality uses Equation (26). Now, using Equation position format,
2 0
(27)
det ( x-1
13
which is in cholesky decom-
log(det (X²*))
log ((HT) (Hr)) log((Hr)an)
log(1 (8)
Σ log((Hn)
Using the above, we can expand the log deteriminatn difference.
det (X,r))
det (X7=²)
log del (X-1)
< log
del (X-2)
(3)
2
9i.r
n-
log
1
+
log (1 (8?)
(28)
t=1
det (x-1 det(Xx
Let Xo = arg migi (xa(X, (X, 1), the above inequality is since log
using Equation
27
Lemma 10 (Upperbound of T2).
1 (CT+ eD3)
1 B
2
91.T
n-1
Ta < 2m
T
Σ log
1
log (1 -87)
1-B
3
e
18

---

Under review as a conference paper at ICLR 2023
Proof.
The proof directly follows from Equation 25 and Lemma 9
Lemma 11 (Upperbound of T3). Let Xu arg (inx Dea Hn') Hp¹)
T
T3
Σ
9t Xege
T
2
t=1
det (X7
7
log
2
det (Xo-)
(6) 1|2
91:1
log
1+
2
Σ i=1
log (1 (3
2
((11n) gd
91 2)²
where B = (ct||919) (c+
(1) 12
Proof.
F X.g: = Tr(X.ge97)
-Tr(X,(X,-- -x-1)
Tr(X,x,11)
det (X₂=1)
log
det Xx
The second equality is using Lemma and that X, 's sparsity graph is tridiagonal. The first inequality using the property Dea X, 2 of LogDet divergence. Thus summing up and using Equation (28
will give the lemma.
Putting together Tı, T2 and T3 from Lemma
Lemma 10 and Lemma |I
Ti (C (C++D))
1+ B
21
- 3*
1 B
2
n
91.7
n
T2 < (CT + +eD))
log 1
+
log (1 - (3)
(29)
21
3
3
(i)
91sT
T3 <
log
1
Σ log (1 - (3)
(30)
i=1
01/273/1,
(1+2) 1/2 1/2
If we set 17
177. then
(c)
Du log
+ +I 1og(1-07)
Ry Ti + + +2
3/4
(
( 1 1
91.
0
C T3/1
Σ [=1
log 1+
2
+
log (1 -
(82
1 1- 3
19

---

Under review as a conference paper at ICLR 2023
A.3 /3T REGRET UPPER BOUND
In this section we derive a regret upper bound with O(T1/2) growth, in contrast to the O(T8/4) obtained in A.2 In which can reduced (T)), by upper bounding each entry of X, X individually. The following lemma helps in constructing telescoping argument to bound [X; )isl
29 72 Σi=((u; w -x,"
w²) is of the order ((T8/2),
Lemma 12. Let H, H E 5 such that H = H + 99", where g E R,, then
Hy V
Hi
9:9
Hig
Hallis - = Ois (NnnH
+
HuHH
H
v H
v HHuHi
Proof.
Hij
Hij
v HiiHjj
(His
Hij)
/ Hz
(Hillij
(Hill
v HHHHi
-1))
HHalljs
gilh
v |inltis
+ Hij
Vilnllss
Lemma 13. Let H.H E St+. such that H H 9g", where 9 E R". Also, Y arg xig, (xa(X, XX, H) and arg (0)+ Dea(X, H), where & is chain graph, then
- Y Ditt S -
G2B 2)
where i k I n, Gxc = llglloo and maxi, Hsyh/ HHH,, I 3 < Let m(diag(H)) = condition number of the diagonal part of H, then = max(x(diag(( (H)diaagg(HH,)))) x(diag(HH) (H)).
Proof. Using Lemma 3 will give the following:
108 (8-1-y-))aa ))48
Huti... ... Al 1itk
High ... Hitk- litk
H441441 ... HirRitk
H441441 H H5-kitk
||V MaNNot ... NitR- Hitkitk
/ HaNa4i- ... N 144k / Hitkith
Hullineee Nuti Ni4R-144 - No. M44R-14K(
H
20

---

Under review as a conference paper at ICLR 2023
where Nij Hts/HHHHH.Ha HHaHjj Expanding Na+1 Nu+1 + 0st+1 (from Lemma 12 subsequently
Nu42 = Nut2 + 0u+2 and so on will give
Hi HiHiiiiik
NotI... N44K-144 Na+1 ... NARE-I
Hu HiHiii
0s44 N141142.. ... No+R-144 + No+1 Nitieta.... Neta-1it- N41142... N44x-1448 litky
H
H Hetkit
= =10441 Ne41442...
Y14n-1148 144h + Na Ne Ne4 +... + Na+1 Na+k-1 12t.000000 l6th
+ NNa11... Nutk (1-1)
His HiHH+ H A
Ha Hstkek
0 00+6+1+1)) gh-1 1 V HaHlaRet
H Hitht
(V-1 (V-1---1)) )ath S v AitatR (0 1 gh-1
V His Hytkith
where maxi, (No,ll max,, |isl S 8. Expanding 04404441111111 from Lemma 11+1+4+11l V He Hitkith will give:
12 in the term
044444411 V Malllettt
9441944141
HH Han Honneall
(V
H Hi MoHHAAssNNNAHH
9it1044141
+
V WH
H HHlHHtHthNNHtHH (1- H HH441111
(1-V
H H441416-441
Since Histit H4 184141 S Heungllaansann
Hosu-hHouttee < max (1- Hig H44441444
Hith+ 1- H4444144441
H444+
H4444144441
max
H4- (i44444tt)
Using the above, H,,/ Hjs S and 19,1 Go. Vi,j
[n]. gives
v Ho 1 GZ + 3G
I G2 n5 + 3)
Thus the following part of (g-1-y-)) x-1
can be upperbounded:
iitk
H HutHit
1
Also, gh-1
H Ho
S 1 . so
Hy 1
(P-1-r-1)
$ (
#+*
21

---

Under review as a conference paper at ICLR 2023
Lemma 14 (O(T) upper bound of T2). Given that k(diag H
w w0112 S D2,
max,, (1 (H)))HH)) s < 1, Vt E [T] in Algorithm
then T2 in 29 can be bounded
as follows:
T
T2 1
2n(1 B)² (G D2)2k
Proof. Note that T2 =
Σ (Wh+1 - "x'T(Xx+1 - (w - w") -
2n
- D2 (X
x, x11 Using ||lll - p(A) $ ||All for symmetric matrices A, we get
|| - X; x2'122 $ |x - -X;' 1100
= max (X X, )el)
G 8)2
0
The third inequality is using Lemma
13
Expanding T2 with this bound gives the result.
Theorem 1/2) regret upper bound). Setting
T 21/2D2GoOVR
Ei log 1 116.2/10 + -1 log (1 - (82)
(1 (1-8),
1)
gives the following regret
2
Pr 50 0
1
1/2 D2G
Σ log
1+
9i.T
2
n-1
log (1 (8)
1 (1-
where condition number re r(diag( H.)) S K. l/wce 112 < D2, maxi, ((H,)s)/ (He)) I 1, E [T] and gt, H, are as defined in Algorithm 7
Proof. The result follows from using (30) and Lemma 14
A.4 NUMERICAL STABILITY
Theorem 7 (Full version of Theorem 4.. Let H. St++ such that Hą 1, for i E [n|] and symmetric perturbation AH such that AH; 0, for i [n] and H AH > O. Let X arg min,xss, Dia (X, H-1) and X A arg wigminxes.ccm Dea (X, (H + AH) here G == chain/tridaggona sparsity graph and Sn(g) denotes positive definite matrices which follows the sparsity pattern G.
A8
Rid = max lim sup [i- c-000
AH < (cH.ll (k. E Eg
Xij
max 1/(1 -111-33 (P)
<E(n-1]
where, Kea = condition number of the LogDet subproblem, N2(.) = condition number of a matrix in l2 norm, B, = Hutt/ /iaei//HH.e HH
Proof. Consider the offdiagonals for which (X + A -Hu+1/(1 H2+1) f(Ha41) where f(x) -x/(1 x²). Let y (अ), f(x Ar) and Ar/ar then
22

---

Under review as a conference paper at ICLR 2023
using Taylor series
(0 y)
(x)
Ar
+ 0((Ar)))
y
f(x)
(i 1--y y)
x (x)
lim
c-0
ey
f(x)
Using the above inequality, with x Hu and
y = X
AX A
1 1 H2
lim
(31)
eX eXa++1
2
$
1 H
Let g(z)
22/(11 2²), let y1 g(w1), 1/2 g (2222 91
g
Az), 12 = g(22 + Ar). Using
Taylor series
(Ù1 v1)
x1 (11)
An1
+0((Az))3)
8/1
f(11)
21
(02 1/2)
(x2)
Ar2
+ +0((Az2))
122
f(x2)
22
Ay Ay2
2
lim c0
max
c11 + y1 + y2)
1 x9
22
Putting 21 == H8+1. 1, x2 = H and analyzing 1/1 == H? H 1)
11 - H (1 and 1/2 = H1
will result the following
AX,
2
lim -0
I max
(32)
X
1- 1 - H2
Since Xx = 1+
H
1 (1
1)
+ H3 //1111111 H Putting together Equation (32 and
Equation 31 the theorem is proved.
Proof of Lemmal
(4+1) then Hjjt1 H3 For b 1, 91.r
(
H5+1541 0 ? thus H3
1 HHz+1j+1 = For b > 1, since HI,1,, using Gutiman rank additivity formula, (ank(H,) H3jt H)415+1) rank([I,,,,)) (rnk((H1,1,)
0, thus fijj H1 = 0. Furthermore, if ()) < b. then all b
b 6+ principal submatrices of H have rank b, thus Vj. HJ,J, have a rank b, thus D,j for all j are undefined.
Proof of Theurem 5
Let I, = (l.)) Eg} and 1
Let K {i: Ha - H H7, H4s is undefined or 0, E [n]] denote vertices which are getting removed by the algorithm, then for the new graph G. D L/Ha, Vi e K since Hμ > 0.
Let K {i: H4s Hy, 1. 7. H 0, [n]] Let for some K, if
= arg min (i : j < i E n 11).
denotes the nearest connected vertex higher than for which Du is undefined zero, then according to the definition Eg in Algorithm 3 IJ [j+1,, 1.......Z 1} C I,. since Dj is well-defined, HI,1, is invertible, which makes it positive definite matrix (since H is PSD). Since H3j - Hi,, H1, > 0, using Guttman rank additivity formula HJ,J, 0, where J, U, Since H H submatrix of HJ, J it is positive definite and hence its schur complement H;j - H. 1 Hr,5 > 0. Thus for all j [ni], the corresponding Djj² 's are well-defined in the new graph g.
Note that Kid max x-1) 1/(1 101--33 (87) < max 1/(1- 37)
n. for tridiagonal graph, where 3, Ha the case where H;; = This is because the arg max 1/(1 -3?) K.
23

---

Under review as a conference paper at ICLR 2023
Table 3: float32 experiments on Autoencoder benchmark using different band sizes. Band size O corresponds to diag-SOO Sowew and 1 corresponds to tridiag-SONews We see the training loss getting better as we increase band size
Band size
0 (diag-SONew) 1 (tridiag-SONee
4
10
Train CE loss
53.025
51.723
51.357
51.226
Table 4: bíloat16 experiments on Autoencoder benchmark with and without Algorithm observe gains in training loss when using Algorithm
We
Optimizer
Train CE loss without Algorithm 3
Train CE loss with Algorithm 3
tridiag-SNNew
53.150
51.936
band-4-SONew
51.950
51.84
Table 5: Large Scale Benchmarks. We compare tds vs Adam on the following large scale bench- mark. We compare train CE loss, and validation performance measured as precision for OGBG benchmark and error rate for Resnet50 and Vision Transformer benchmark.
Benchmark
A model parameters
truining points
Train Loss (Adam)
Truin LestSSONew)
Valid, perf. (Adam)
Valid, pent. (SONew)
ReanetSD-Imnree
304
1.2
0.0081
0.8857
22.61%
22.58%
Viscon Tuisiommee Anagenet
176M
1.2M
0.4589
0.45516
22.85%
23.301
OGBG molpeha
29.AM
437,929
0.0143
0.0157
0,2520
A.5 ADDITIONAL EXPERIMENTS, ABLATIONS, AND DETAILS
Effeet of band size in banded-SONew Increasing band size in Banded-SONens captures more corre- lation between parameters, hence should expectedly lead to better preconditioners. We confirm this through experiments on the Autoencoder benchmark where we take band size = 0 SOlle-, (tridiag-SOn) -Siiia,--ONew,.... 4, and 10.
Effect of mini-batch size To find the effect of mini-batch size, in Table We empirically compare SONew with state of the art first-order methods such as Adam and RMSProp, and second order method Shampoo. We see that SONew performance doesn't 't deteriorate much when using smaller or larger batch size. First order methods on the other hand suffer significantly. We also notice that Shampoo doesn't 't perform better than SONew in these regimes.
observe that using Algorithm improves training loss. We present in Table results where we observed significant performance improvements.
Effect of Numerical Stability Algorithm 3 On tridiag-SONer and banded--SSONen
Large Scale Benchmark Comparison To test efficacy of SONew in Deep Learning, test method against Adam on large scale benchmarks Resnet50 He et al. (2015)) on Imagenet Deng al. (2009) training, Vision Transformer Dosovitskiy Dosooviiime et al. (2020) Imagenet training, and Graph- Network Battaglia et al. (2018); Godwin et al. (2020) on OGBG-molpcba dataset Hu et al. (2020). The numbers are given in Table We see that SONew performs comparable or outperiorms Adam in all the benchmark in both train loss and validation performance. Moreover, we plot the training and validation curve in Figure We observe that SONew has an early advantage over Adam.
Hyperparaeter search space We provide the hyperparamter search space for experiments presented in Section(6 We search over 2k hyperparameters for each experiment using Bayesian Optimization
package. The search ranges are: first order momentum term 81 [le 1, 0.999). second order momentum term A2 E [1 1, 0.999), learning rate E [le 7, le - 1 E [1e 10, le 1]. We give the optimal hyperparameter value for each experiment in Table 6 For large scale benchmark (Table 5). we search 31, 33 E [0.1, 0.999), Ir E [le 5, le 11, [e 8, le 4/. weight decay E [le 5. 1.0]. learning rate warmup E [2%. 5%, 10%] 10%]ttotalltraal www.ittaanaant ttriinsstess...... We use cosine learning rate schedule. For resnet50 imagenet, we also search label smoothing over [0.0. 0.2). Batch size was kept = 1024, 1024, and 512 for Resnet50, Vision Transformer, and OGBG respectively. We sweep over 100 hyperparameters in the search space for both SONew and Adam.
24

---

Under review as a conference paper at ICLR 2023
(a) Imagenet-Resnete train CE loss
(b) Imagenet- Resenntt-eeset50 valid. rate
adam
a0am
tratn CE loss
0.5
validation
0.10
0.08
20
40
80
100
120
140
stops (711)
epochs
(c) OGBG train CE loss
(d) OGBG valid, average precision
adam
validation average precisior.
train CE Jass
0.0160
tris
0.0140
0
10
20
30
10
50
60
20
steps (*1
shops (*1k)
(e) Imagenet- Vision Transformer train CE loss
Imagenet- Visioon Transformer validation error rate
Ids adam
train GR loss
10a
validation
0.203
0.227
20
10
80
100
120
149
20
40
80 sleps (*1a)
60
100
120
140
steps (*1k)
Figure 2: SONew Adam large scale benchmark Train Cross Entropy (CE) Loss (left column) and validation performance (right column). We see that SONew has an early advantage over Adam all the experiments.
25

---

Under review as a conference paper at ICLR 2023
Table 6: Optimal hyperparamers for Autoencoder Benchmark
(a) float32 experiments optimal hyperparamters
bfloatl6 experiments optimal hyperparamters
Bascline
81
8
Baseline
f1
SGD
0.99
0.91
8.37c-9
1.17c-2
SGD
0.96
0.98
2.80e-2
1.35e-2
Nesterov
0.914
0.90
3,88e-10
5.74e-3
Nestervv
0.914
0.945
8.48e-9
6.19e-3
Adagrad
0.95
0.90
9.96e-7
1.82c-2
Adagrad
0.95
2.44c-5
2.53e-2
Momentum
0.9
0.99
lc-5
6.89e-3
Momentum
7.77e-3
RMSProp
0.9
0.9
le-10
4.61e-4
RMSProp
0.9
2.53c-10
4.83e-4
Adam
0.9
0.94
1.65e-6
3.75e-3
Adam
0.9
0.94
3.03e-10
3.45e-3
Diag-5ONew
0.88
0.95
4.63e-6
1.18e-3
DiaewSONew
0.9
0.95
4.07e-6
8.50e=3
Shampoo
0.9
0.95
9.6c-9
3.70e-3
Shampoo
0.85
0.806
6.58e-4
5.03e-3
tridiag
0,9
0.96
1.3e-6
8.60e-3
ztridiag
0.83
0.954
1.78c-6
7.83e-3
band-4
0.88
0.95
1.5e-3
5,53e-3
band-4
0.9
0.96
1.52e-6
4.53e:3
Table 7: Comparison on Autoencoder with different batch-sizes
Baseline Batch size
100
1000
5000
10000
RMSProp
55.61
53.33
58.69
64.91
Adam
55.67
54.39
58.93
65.37
Shampoo(20)
53.91
50.70
53.52
54.90
tds
53.84
51.72
54.24
55.87
bds-4
53.52
51.35
53.03
54.89
26


Reviews:
[{"review_id": "fN6bsIZ_XP", "reviewer": "Reviewer_9vTP", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposed SONew (Sparsified Online Newton), which is an efficient variant of online Newton step (ONS) by using $b$-banded sparsity graph. The time complexity of this method is $O(b^3 n)$, and the regret bound is $O(T^{3/4})$. The authors provide some simple experiments to verify the performance of the proposed method.", "summary_of_the_review": "By considering the $O(T^{3/4})$ regret bound of the proposed method and the existing efficient variants of ONS, I tend to reject this paper.", "strength_and_weaknesses": "#Strength\n1) The authors proposed a new efficient variant of online Newton step (ONS) by using $b$-banded sparsity graph.\n2) The proposed algorithm improves the time complexity of ONS from $O(n^2)$ to $O(b^3 n)$.\n\n#Weaknesses\n1) The authors only established a regret bound of $O(T^{3/4})$ for their method, which is far worse than the $O(\\sqrt{T})$ regret bound of many existing first-order methods such as online gradient descent. Note that these first-order methods are more efficient than the proposed algorithm for $b>1$.\n2) The experiments presented in this paper is too simple, which is not sufficient to verify the advantage of the proposed method. The authors at least consider some other datasets such as CIFAR10 and CIFAR100. Moreover, the authors should also consider other deep neural networks such as convolutional neural networks (CNNs).\n3) In the experiments, some tricks including momentum and grafting are added to the proposed method, which may affect the evaluation of the proposed method.\n4) There actually exist efficient variants of ONS [1][2], which enjoy the time complexity of $O(\\tau n)$ for very small $\\tau$. However, the authors do not discuss and compare the proposed method with them.\n\n[1] Haipeng Luo et al. Efficient Second Order Online Learning via Sketching. In NeurIPS 2016.\n\n[2] Luo Luo et al. Robust Frequent Directions with Application in Online Learning. In JMLR 2019.\n", "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": "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": "VKFlILNe-7", "reviewer": "Reviewer_kEgN", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes sparsifed online Newton method.\n", "summary_of_the_review": "This paper proposes sparsifed online Newton method.", "strength_and_weaknesses": "Pros: It is easy to follow and the intuition of the algorithm is easy to understand.\n\nCons: Page 4, between Eq. 8 and Eq. 9, the optimality condition of Eq. 7 is not the gradient equal to zero because Eq. 7 is a constrained optimization problem. Thus, the derivation of Eq. 9 may be problematic.\n\nThis paper only considers the third term of Eq.3. This may be not enough because $X_t ^{-1}-X_{t-1}^{-1} $ which makes the regret large.\n", "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": "-0vPYhNpgk", "reviewer": "Reviewer_pCLb", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work proposes SONew, an online convex optimizer derived by combining the regret minimization based on the LogDet divergence measure and structured sparsity in the preconditioning matrix. The preconditioning matrix of the SONew is a shape of either diagonal, tri-diagonal, or banded and is calculated in linear flops and numerically stable ways, making it compatible with large deep neural networks. On the MNIST autoencoder training task, SONew achieved better convergence than the existing first-order adaptive gradient method. Furthermore, SONew shows better numerical stability than other methods, including the Shampoo optimizer, when training with bfloat16.\n", "summary_of_the_review": "This work proposes a compute- and memory-efficient online convex optimizer for deep neural networks based on solid mathematical insight. However, it is not clear from the given experimental results and theoretical justification alone that the proposed method is helpful in “Learning Representation.” I think more empirical results and discussion of non-convex optimization/generalization would improve the quality of this research, but it is currently the under the bar of acceptance.", "strength_and_weaknesses": "Strengths\n- This paper is clearly written.\n- This paper highlights an interesting connection between the regret minimization in OCO and LogDet divergence of the preconditioning matrix, giving a novel insight into the online gradient descent and online Newton method.\n- By taking advantage of structural sparsity in the preconditioning matrix, the proposed SONew method gives a way to solve the LogDet divergence subproblem fast enough (enough to be applied every step during training). It seems practical even with a large DNN model. \n- Also, thanks to the flexibility of the sparse structure in SONew, the form of the preconditioning matrix (diag, tri-diag, banded) can be determined according to the computational budget, and a straightforward trade-off between convergence speed and computation time is observed in the auto-encoder training experiments in MNIST.\n\nAlthough SONew is based on solid mathematical intuition and the experimental results show good convergence and numerical stability, the empirical results are not strong enough to support SONew’s effectiveness as a ‘deep learning optimizer’, as described below.\n\nWeaknesses\n- Comparisons at different mini-batch sizes have not been made.\n    - In mini-batch training, g_t in Equation 5 corresponds to the mini-batch gradient, and X_t^{-1} is known as the (mini-batch) empirical Fisher. It has been pointed out that the mini-batch empirical Fisher loses valuable second-order information for optimization as the mini-batch size increases (Equation 4 in https://www.cs.toronto.edu/~rgrosse/courses/csc2541_2022/readings/L05_normalization.pdf).\n    - Therefore, comparisons with different (larger or smaller) mini-batch sizes are desirable, as differences in mini-batch size are expected to affect the convergence of SONew (and the optimization methods being compared). In particular, since large batches are desirable for large-scale training that takes advantage of data parallelism and distributed accelerators (e.g., https://arxiv.org/abs/1802.09941), how well SONew maintains convergence in large-batch training is useful information for practical (esp. large-scale) uses.\n- Comparison of numerical stability needs improvement.\n    - The numerical stability of the eigenvalue decomposition required by Shampoo depends largely on the condition number of the matrix, which can be significantly improved by the damping value to be added to the diagonal of the matrix. For example, in the experimental code of Anil et al. (2020) (https://arxiv.org/abs/2002.09018), the default value of damping is set to 1e-4 (https://github.com/jettify/pytorch-optimizer/blob/master/torch_optimizer/shampoo.py#L50) to improve the numerical stability. Similarly, large damping values are often used in K-FAC in practice (e.g., 1e-3 in https://github.com/gpauloski/kfac-pytorch/blob/main/kfac/preconditioner.py#L57). Therefore, it is desirable to use Shampoo with a large damping value as a baseline result in the bfloat16 setting.\n    - K-FAC can also be implemented using Cholesky decomposition. In addition, there are second-order optimization methods that can take advantage of the low-rank nature of matrices and avoid explicit inverse matrix and eigenvalue decomposition calculations (e.g., SKFAC https://openaccess.thecvf.com/content/CVPR2021/papers/Tang_SKFAC_Training_Neural_Networks_With_Faster_Kronecker-Factored_Approximate_Curvature_CVPR_2021_paper.pdf, SENG https://link.springer.com/article/10.1007/s10915-022-01911-x). Since these methods can be expected to have more robust numerical stability in low-precision training, using only Shampoo (which is less numerically stable) as a baseline for low-precision second-order optimization seems inappropriate for evaluating the relative numerical stability of SONew. \n- It is unclear whether SONew is effective as a ‘deep learning optimizer’.\n    - From the derivation, SONew is an online 'convex' optimizer. However, since the loss function in deep learning is nonconvex, it is unclear how effective regret minimization achieved by SONew is in minimizing loss. Since the MNIST autoencoder training is a very simple task by today's deep learning standards, training results in a larger, more realistic setting (e.g., training CNNs on ImageNet classification, Transformers on language tasks with cross-entropy loss) would be desirable.\n    - Although only training loss is shown in the experiment, I believe that the evaluation of generalization performance is necessary to measure the performance of SONew as a deep learning optimizer. For example, not only the training convergence speed of the optimizer but also its compatibility with regularization, such as weight decay, is an essential subject of discussion (e.g., Adam vs. AdamW https://arxiv.org/abs/1711.05101).\n\nQuestions\n- Why is there no result for “band-4” with bfloat16 in Figure1 and Table2?\n- What are the damping values (espsilon) used for SONew, Shampoo, and other adaptive gradient methods?\n", "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": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject