A Novel Fast Exact Subproblem Solver for Stochastic Quasi-Newton Cubic Regularized Optimization
Authors: Jarad Forristal
Joshua Griffin
Wenwen Zhou
Seyedalireza Yektamaram
Venue: Submitted to ICLR 2023 (2023)
Keywords: optimization
quasi-newton

Abstract: In this work we describe an Adaptive Regularization using Cubics (ARC) method for large-scale nonconvex unconstrained optimization using Limited memory Quasi-Newton (LQN) matrices. ARC methods are a relatively new family of second-order optimization strategies that utilize a cubic-regularization (CR) term in place of trust-regions or line-searches. Solving the CR subproblem exactly requires Newton's method, yet using properties of the internal structure of LQN matrices, we are able to find exact solutions to the CR subproblem in a matrix-free manner, providing very large speedups. Additionally, we expand upon previous ARC work and explicitly incorporate first-order updates into our algorithm. We provide empirical results for different LQN matrices and find our proposed method compares to or exceeds all tested optimizers with minimal tuning.

Under review as a conference paper at ICLR 2023
A NOVEL FAST EXACT SUBPROBLEM SOLVER FOR STOCHASTIC QUASI-NEWTON CUBIC REGULARIZED OPTIMIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
In this work we describe an Adaptive Regularization using Cubics (ARC) method for large-scale nonconvex unconstrained optimization using Limited memory Quasi- Newton (LQN) matrices. ARC methods are relatively new family of second-order optimization strategies that utilize a cubie-regularization (CR) term in place of trust- regions or line-searcie searches. Solving the CR subproblem exactly requires Newton's 's method, yet using properties of the internal structure of LQN matrices, we are able to find exact solutions to the CR subproblem in matrix-free manner, providing very large speedups. Additionally, we expand upon previous ARC work and explicitly incorporate first-order updates into algorithm. We provide empirical results for different LQN matrices and find our proposed method compares to or exceeds all tested optimizers with minimal tuning.
INTRODUCTION
Scalable second-order methods for training deep learning problems have shown great potential, yet ones that build on Hessian- veetor products may be prohibitively expensive to use. In this paper, we focus on algorithms that require information similar to Stochastic Gradient Descent (SGD) Ruder (2016), namely, stochastic gradients calculated on mini-batches of data. Quasi-Newton (QN) methods are natural higher-level alternative to first-order methods, in that they seek to model curvature information dynamically from past steps based on available gradient information. Thus, they can work out of the box in the same settings as SGD with little model-specific coding required.
However, this comes with possible instability of the step size. Controlling the step size can be done using line-searches along given direction or using trust-regions find the best for given step size. A relatively recent alternative to the mentioned approaches is known as cubic regularization Nesterov and Polyak (2006); [Crrtis et al. (201I); Tripuranení al. (2018), which shows very promising results. In detail, we study the minimization problem of
minimize mx(s) del f(xx) + S gl + 2 *ER"
S B&S 3 Th [1sls
(1)
for a given where adaptive regularization parameter, and (xxx is the objective function to minimize evaluated zg- Equation T is also known as the CR subproblem. Cubic regularization shows promise because it can be shown that 2 f is Lipschitz continuous with constant L, then far +s) S (s) whenever a 2 T. and B5&8 2 f(r()) Nesterov and Polyak (200)). Thus if the Hessian approximation B& behaves like V f(x( along the search direction 8; the model function m*(s) becomes an upper bound on the objective f(r + s). In such cases line-search would not be needed reduction in mx(s) translates directly into reduction in f( + s), removing the risk that the computational work performed minimizing ms(s) is wasted.
(xxx), B₁ is Hessian approximation, σg an iteratively chosen
We propose an efficient exact solver to Equation I using Newton's method which is tractable in surge-scale optimization problems under near-identical conditions to those in which SGD itself commonly applied. As Newton's 's method corresponds to much of the computation overhead when solving Equation [ dense approach such that described in Cartis et al. (2011) would be

---

Under review as a conference paper at ICLR 2023
prohibitive. However, by exploiting properties of LQN methods described in Erway and Marcia (2015) Burdakov et al. (2017) (and further applied in other papers CCenn et al. (2014)) pei Lee et al. Lee et (2022) ), we can instead perform Newton's 's method in reduced subspace such that the cost per Newton iteration is reduced from O to ((m), where n is the problem dimension and m is the history size, commonly chosen to be an integer between 5 and 20. The full-space solution to Equation [ can then be recovered for cost identical to that of classic LQN methods.
To the best of our knowledge, all previous attempts use LQN methods in the context of the ARC framework have necessarily had to change the definition of my (s) in order to find an approximate solution Andrei (202T); Liu al. (202T); Ranganath et al. (2022). Remarkably, we present a mechanism for minimizing ( using similar computational efforts to single matrix inversion of a shifted LQN matrix, which itself is lower bound of the complexity of traditional LQQN approaches.
Further, we show that by applying Newton's method in the reduced subspace, we can achieve speed improvements of more than 100x over a naive (L.QN inversion-based implementation. In the numerical results section we further show that this modification permits the application of LQN matrices with exact cubic regularization as a practical optimizer for large DNNs.
RELATED WORK
Second-order methods in machine learning are steadily growing more common Berahas al. (202) )
Brust et al. (2017) ; Chen et al. (2020); Goldfarb el al. (2020); Ma 20 Ramamurthy and Dutty
(2016); Yao et al. (021). Limited-memen
SRI (LSRI) updates are studied in the context of ARC
methodology using a "memory-less' variant in Andrei (202T). As we will describe in Section 3
many QN methods iteratively update BB matrices with pairs (8k: Vk) such that B&Sg = ykk. where yk
denotes the difference of the corresponding gradients of the objective functions. In |nnArrri (2021), 1), yk
a difference of the gradients of (s).). [Liu et al. (2021] approximately minimize mg(s) (8) by solving
shifted systems of form (By + or 0||sk-1 [[]ss = -9. where the norm of the previous step is used as
an estimate for the norm of [|sx|] || to define the optimal shift. As described in Theorem
I in Section 3
-g. Since the norm of [] s || may vary greatly between iterations, this solution is a noisy approximation. They further simplify the sub-problem using only the diagonals of Bg + a||sk-11 /|/ when generating sk-
the optimal solution necessarily satisfies condition of the form (Bx + a ||sxx|[T)s
Ranganath et al. (2022) solve a modified version of the problem using a shape-changing norm as the cubic overestimation that provides an analytical solution to Equation [ They transform mx(ss using similar strategies to those advocated in this paper. However, this norm definition is dependent on the matrix B& and thus makes the definition of the target Lipschitz constant, L, dependent as well. A nontrivial distinction in our approaches is that theirs requires QR factorization of matrices of size m. This may be prohibitive for deep learning problems, which may have billions of parameters. Bergou et al. (2017) explores a similar idea of making the norm dependant on the QN matrix. In Park eet al. (2020). the ARC framework with stochastic gradients is used with a Hessian-based approach first advocated by Martens et al. 2010)) In this case, 22 fax) is approximated within Krylov-based subspace using Hessian- vector products with batched estimates of fz)( They then minimize (s) with this miml--dimeniional subspace.
An alternative to ARC methods is the use of trust-regions or line-searches. Though fundamentally different approaches, we often borrow technology from the trust-region subproblem solver space to adapt to the ARC context. For example. |Brust et al. (2017) outlines mechanisms for efficiently computing (Bg+ + AT) y and implicit eigendecomposition of B₁ + \/ when solving the trust-region
subproblem of minimizing (s) f(x)) + s gk + 1 B&s while subject to ||||| < 8. Burdakov
et al. (011)) significantly reduces the complexity and memory cost of such algebraic operations
while solving the same problem. We thus adopt select operations developed therein when applicable, to adapt the method of Cartis et al.] (20TT) to the L.QN context. Unlike the approach advocated in Burdakov et al. (2017), we avoid inversions of potentially ill-oonitiioned systems to improve the stability of the approach while simultancously reducing computation overhead costs.
Note that we further extend Cartis et al. 12011) to the stochastic optimization setting. Thus we also
share relation to past stochastic QN approaches. Erway et al. (2020) use the tools described in Brust
et al.) (201)) to create stochastic trust-region solver using LSRI updates. [Schraudolph et al. (2007)
generalizes BFGS and LBFGS to the online convex optimization setting. [Mokhtari and Ribeiro 2014)
studies BFGS applied to the stochastic convex case and develops a regularization scheme to prevent
2

---

Under review as a conference paper at ICLR 2023
the BFGS matrix from becoming singular. Sohl-Dickstein al. (2014) explores domain-specifie modifications to SGD and BFGS for sum-of-functions minimization, where the objective function is composed of the sum of multiple differential subfunctions. Byrd et al. (2016) considers not using simple gradient differencing for the BFGS update, but instead more carefully building (sk, yk) pairs using Hessian-vectte vector products: Berahas et al. (202T) also explores similar idea of carefully choosing 3ü. and yk- WWan et al. (2016) tries to prevent ill-conditioning of B3 for BFGS updates, similar to
Mokhtari and Ribeiro 2014), but explicitl for the nonconvex case. Keskar and Berahas (2016)
present an optimizer designed specifically for RNNs that builds on Byrd et al. (2016).
Our Contributions.
1. A fast (mm) approach for exactly solving the cubic regularization problem for any limited memory quasi-Newton approximation that lends itself to efficient eigendecomposition such as LBFGS and L,R
2. A hybrid first and second-order stochastic Quasi-Newton ARC framework that is competitive with current SOTA optimizers.
3. Convergence theory that proves convergence the nonconvex case, and
4. Strong empirical results of this optimizer applied to real-life nonconvex problems.
3 ALGORITHM
In this section we describe the proposed algorithm. We will first provide a brief introduction to LQN matrices, then describe how exactly and efficiently solve Equation [ when B& is defined by an LQN matrix. We will demonstrate that the computational complexity of ARCLQN (detailed in Algorithm(3) similar to that of classical LQN solvers. Later in this section we describe how to solve the nonlinear optimization problem (Algorithm 2 using this subproblem solver. Until Section 3.2 for simplicity, we will motivate the problem by largely considering full-batch gradient descent. However, the techniques being developed in this paper will largely be applied in the stochastic setting.
Popular Quasi-Newton updates such as BFGS, DFP, and SR1 are based on iteratively updating an initial matrix Bo > with rank one two corrections with pairs (sk, such that the property B&S%- = M/ is maintained each update (Nocedal and Wright 2006). For example, the popular SR1 update formula is given by the recursive relation:
(Vk- (L BBSK)²
Ba+1 Bg
o (yk BLSK)
where yk del
gk 9k-1 and Sy del 2b - 0k-1- To verify that the update is well-defined,
s (yk- Bes+)l > [[ss - BASHll
(3)
is checked with a small number e. If condition is not satisfied, Bx+1 < Bs. This helps ensure that B& remains bounded. While for much of this paper will focus on the SRI update, we stress that the exact subproblem solver proposed in this section will hold for all QN variants described in Erway and Marcia (2015). We discuss many of such variants later in Section 3.2
Note that if Bş is explicitly formed, the computational and memory costs are at least O(n?); such, for large-scale problems, limited-memory variants are popular. For such cases, only the most recent m & pairs of (8,y) are stored in n X m matrices S₃ and Yx. where S. def ($k-m+1..... Sx) and Y2 def -W--m+1......l.. 93)). In the limited memory case, B& is never explicitly formed, and operations using Bg are performed using only 7, S, and Y using O(m)) operations. How this done specifically for the cubic-regularized case will become clearer later in this section. Before proceeding, we will next briefly describe the approach used by Cartis et al. (201I) for the case where B& is dense. Later we describe how to adapt their dense approach to the limited-memory case.
3.1 SOLVING THE CUBIC REGULARIZED SUB- PROBLEM
In this section we focus on efficiently finding a global solution to the cubic regularized subproblem given in Equation]] [ restated here for convenience:
3

---

Under review as a conference paper at ICLR 2023
1 minimize (s(ss) del (xx) + 5 + 22" B&S + J0 |s|3 SEIt"
1
We start by describing a Newton-based approach proven to be convergent in Cartis et al. 201 Though their approach targets dense matrices By where Cholesky factorizations are viable, subsequently show in this section how to efficiently extend this approach to large-scale limited memory QN matrices. The Newton-based solver for Equation Tis based on the following theorem:
Theorem 1 (Cartts et al. 2011)). Let (x(A) del
Bx AI, X denote the smallest eigenvalue of BR, and its corresponding eigenvector. A step 88 is a global minimizer of mx(8) if there exists x 2 max (0, -X1) such that:
Ba(A")o
99k X
(4)
|
(5)
OF
implying B& (x() is positive semidefinite. Further, only if By is indefinite, un gu O, and [B
X11 gu S -1/ then X" = -A-
For simplicity we define s(A) - -B (B++ where the pseudo-inverse is used for the case where A -A1. We can then see that for the case where X -A1, st. is given by the solution to the following equation:
d1 (A) del
A O.
(6)
||s()]]
Note the authors of Cartis et al. (2011) show that when Bg indefinite and u/ g 0, the solution sp
given by st = x( + (19)) where ar is a solution to the equation -X1 ( + arn
That is, whenever Equation multiple of the direction of greatest negative curvature to the min-two norm solution to Equation 4 so
6 fails have a solution (the "hard-case") s% is obtained by adding
that Equation is satisfied. The authors of (Cartis al. (201I) thus apply Newton's 's method to @1 (A)
resulting in Algorithm 1 This corresponds to Algorithm (6.1) of Cartis et al. (201T)
Algorithm I Newton's method to find s* and solve d1 (A) 0
if B indefinite, u/ g = 0 then
< (>>\)l Solve a1 olls(-A1) + oun for
then
8" t s( A1) + 0m1
else
8" + s
end if
else
Let ma -1)) while Φ1 (A) # 0 do Solve for s:
(B + AT)s -9-
=
Lw =
(8)
Compute the Newton correction
A(1|s|1 - 2
A
||$|| } (110/1 (1]
Let A - A+ V
end while s* - -a)
end
4

---

Under review as a conference paper at ICLR 2023
At first glance, Algorithm may not look feasible, Equation & requires the Cholesky matrix L, which is only cheaply obtained for small dense systems. Looking closer, we note that to execute A one need not form and w. as only their corresponding norms are needed to compute AAN. Relevantly, it has been demonstrated that matrices in the Quasi-Newton family have compact matrix representations of the form
may
B = - WM
(10)
further detailed in Byrd et al. 2016). For example, for LSRI V Y 7S and M M- (E S) where E is a symmetric approximation of the matrix S whose lower triangular elements equal those of S (Erway and Marcia 2015). They further show that for matrices of this class, (mm) calculation may be used to implicitly form the spectral decomposition B = UAUT, where U is never formed but stored implicitly and A satisfies
71 A 1-01 1 )
(11)
where Å Be*k is the diagonal matrix defined in Erway and Marcia (2015) to be diag (A1,
...y Am)
Thus we know that B will have a cluster of eigenvalues equal to of size n k. We can exploit this property to further reduce the computational complexity of Algorithm |
Note again that AA in
Equation 9 can be computed as long as ||s] and ||w|| are known. Using the eigendeconposition of BR, we get
|| - -
Note here that À denotes the parameter optimized in Algorithm aad not the diagonal values of A. then define U block-wise we can define the components タ1 and Ò2 as follows:
U = U g
91
U = (U1
U2) - U. g
(12)
92
Thus we can compute ||||| and |w||| in (()) operations assuming 9 stored, giving
11
m
92(1)²
|| 1
+
(13)
(A + 7)2
(): + A)²
11
i2))
(14)
(A + 73
()1 X)3
Using this, the computation cost of Newton's method is reduced to an arguably inconsequential amount, assuming that || and ÿ2 required by Equations 13 and c4 be efficiently computed. We dub this optimization the "norm-trick". We additionally note that Y and S both change by only one column each iteration of Algorithm 3 (defined later). Thus with negligible overhead we can cheaply update the matrix y & E R each iteration by retaining previously computed values that are not dependent on the new (8, y) pair. Making the following two assumptions, we can then show that Al Algorithm] D can be solved with negligible overhead compared to classical LQQ approaches.
Assumption 1. The matrix = v" V is stored and updated incrementally. That is, if & has one column replaced, then only one row and column Tf
T is updated.
Assumption 2. The vector it = TT is computed once each iteration of Algorithm 3 and stored.
We note that classic LQN methods each iteration must update By and then solve system of the form = - -(B; + X7)-1g for some X > 0. This creates an ((m)) computational lower bound that we aim to likewise achieve when generating an optimal step for Equation [ In contrast to the approach described in Ranganath et al. (2022) that uses QR factorization of V, we use analogous approach to that described in Burdakov et al. 2017) for trust-region methods to perform the majority of the required calculations matrices of size m on both storage and computational overhead. Note that unlike Burdakov et al. (2017) we do not explicitly compute M
in place of m. This saves significantly
have found this matrix can periodically become ill-conditioned.
Using the techniques detailed here (but proven in Section of the appendix), we can form a very efficient solver for Equation T (using modified version of Algorithm T]. Using the norm-trick,
5

---

Under review as a conference paper at ICLR 2023
avoid explicitly forming and w, reducing complexity of Newton iterate from O(mn) to (m)).
Using Equationns] 13 and 14 and Assumptions 1 2 we can thus solve X = =I||s"|| from Algorithm | in O Omm²) additional operations once T' and are formed. Finally, once A is recovered, we can form 8" in (m,), single inversion of a shifted system, the same complexity of classical LQN approaches. Full derivation and proof available in Section|Djof the appendix.
3.2 SOLVING THE NONLINEAR OPTIMIZATION PROBLEM
In this section we focus on solving the problem
min f(x) E(a ZER"
(15)
where fi(z) defined as the loss for the i-th datapoint, using the subproblem solver defined in
Section 3.1 We follow the ARC framework as described in Cartis et al. (201I), stated here as
Algorithm 2 A benefit of the algorithm defined in Algorithm is that first-order convergence is
proven if 2& remains bounded and f(x) C² (R"). Thus the condition that B₁ f²f(z) is greatly
relaxed from its predecessors such as Nesterov and Polyak (2006).
Algorithm 2 Adaptive Regularization using Cubics (ARC). Blue text in Equation 18 indicates our modification to default to an SGD-like step on failure.
Given Fo, do > 0, 72, 71, T2 > 7h > 0, a > O, for k = 0, 1,...... until convergence,
1. Compute update o such that:
m& (s S (s
(16)
where the Cauchy point $f = - and of. arg min mz(-ugk). w
2. Compute ratio between the estimated reduction and actual reduction
Pk + f(xx)= - f(Ix + sh) f(xx) mA (8%
(17)
3. Update
I + sh -agk
px 2 m otherwise
Øk+1
(18)
4. Set
(0, onl [ok ro (Y 720k)
if ps > 1/2 if 122 2 Pk 2 otherwise
Tb41 in
(19)
In Algorithm we first solve the CR subproblem (Equations 16 Algorithm to find step,
st. We then determine if the step is accepted by examining if the ratio between the decrease in the
objective (fxx) f [g st)) and the predicted decrease in objective (f(xx) - mx((s) )) is large enough (Equations 17
(st)
Then, depending on Pk, 7) and 7/,, we adjust our regularization parameter Tg: the 'better' the step is, the more we decrease 0k+1, and the worse it is, the more we increase (Equation 19 The amount of increase and decrease is governed by two byperparameters, Y1 and 72-
We note one important modification to the ARC framework: we find that p 7/1 we take an SGD step instead of just setting 3y + -1-1 (Equation I8). While, empirically, rejected steps are not common, we find that reverting to SGD in case of failure can save time in cases where Bg is ill-conditioned. One may note that we have no guarantees that f(xx) - f(1 agg)) > O, which may seem to contradict the ARC pattern detailed in Cartis et al. (00IT) which only accepts steps which improve loss. However, Chen al. (2018) proves that in trust-region framework, if you accept all steps. Pk need only be positive half of the time for almost sure convergence (Paquette and Scheinberg (2020) proves similar result for first-order methods). It has also been shown that noisy SGD steps improve performance of final solution quality (Zhang et al. 2017] Zou et al. (02T). Implementation details regarding Algorithm 2 can be found in Section B of the appendix and Algorithm

---

Under review as a conference paper at ICLR 2023
Joining the optimizations presented in Section 3.1 with the modifications in Section 3.2
can form the full ARCLQN algorithm, explicitly described in Algorithm 31 It is worth noting that while much of the above discussion assumes our Hessian approximation Bg is an LQN matrix with compact representation, this is not required. Indeed, any Hessian approximation which lends itself to a fast eigendecomposition and inversion may be applied this modified ARC framework, with the caveat that Algorithm| I may be slower if the norm-trick cannot be used. We explore this potential extension more Section
where we use the positive-definite Hessian approximation proposed Ma (2020). We also provide theoretical analysis of the proposed framework in Section of the appendix, where we prove that under moderate assumptions ARCLQN converges in the nonconvex case.
Algorithm 3 ARCLQN, our proposed algorithm for solving Algorithm 2 under memory constraints.
Require: Given z0 initial parameter vector
Require: 0 < 1/1 < 7/2 hyperparameters to measure the level of success of a step
Require: D. q dataset and minibatch-size, respectively.
Require: do starting regularization parameter
Require: é, tolerance parameters
Require: f(xx,)) b) objective function with inputs parameters & and minibatch
Require: a1 0g learning rates
1: Initialize Bg = I.
2: for k 2. do
3: Let by be minibatch sampled randomly from DD of size
4: 9x f (=k( bj.)
5: Calculate x of B
6:
Let + max(-A1, +
7:
Compute sT. (using Algorithm
8:
Calculate p (as in Equation 17
9:
if p yn then
10:
FK < -I-1 +
11:
y < [ bw) 9k
12:
Update By using BR- 818 y if update and resulting B3 are well-defined
if p 2 72 then
14:
T% + max 0k-1
end
16:
else
17:
0k x 2. 0
18:
2& Ik-1 029h
19:
y Vof(Ik, bb) 9k
20:
Update By using BB- -229k if update and resulting B& well-defined
21: end
22:
end for
4 NUMERICAL RESULTS
4.1 COMPARISON TO SRI
We start by benchmarking the optimized CR subproblem solver alone, without integration into the larger ARCLQN optimizer[] These results are summarized in Table [ All timing information is reported as the average across 10 runs. We see that the dense SRI solver fails to scale to more than 10,000 variables. We also that the traditional LSRI solver becomes computationally prohibitive for higher dimensions. For example, when n 10a, the -ositive-definite test case takes 274 seconds converge for the inversion-base solver, whereas following steps outlined in Section 3.1 it is reduced to 2.33 seconds, a speedup of over 100x. Considering that the CR subproblem represents the bulk of the computation of any given optimization step, this performance improvement greatly increases the scalability of the algorithm. In the next section, we use the enhancements highlighted here to provide preliminary results using Algorithm
experiments in this section were run on two Intel Xcon Gold 61550 processors.
7

---

Under review as a conference paper at ICLR 2023
Table I: Timing information for solving the CR subproblem, Equation | A hyphen indicates that the test did not terminate within 300 seconds. SRI corresponds a dense SR1 implementation. LSRI corresponds to ARCLON without the norm trick. For limited memory experiments, m = was used. Cases are detailed in section All other columns correspond to the problem dimension, and entrics correspond to time (in seconds) required to find the global minimizer s" using CPU.
Time (in seconds) to solve CR subproblem of given dimension
Method
Case
le2
1e3
le4
lc5
le6
1e7
1e8
SRI
Hard
3.71e-3
2. 2.79--1
1.03e2
LSRI
Hard
4.47e-4
8,05e-4
3. 3.16e-3
5.72e-3
4.05e-2
8.75e- 6.44e-1
7.41e0
ARCLON
Hard
4.31c-4
7.34e-4
1.68e-3
4.47e-3
2.66c-2
5.64e0
SRI
Indefinite
1.93e-3
8,53e-2
1.17e1
LSRI
Indefinite
1.49e-3
3.54e-3
1.90e-2
4.40e-2
7.78e-1
8.55e0
8.14e1
ARCLQN
Indefinitc
8.02c-4
1.69e-3
1.99c-3
2.79c-3
1.90c-2
2.59c-1
2.39c0
SRI
Positive Definite
1.39e-3
9.65e-1
9.23el
LSRI
Positive Definite
7.85c-3
1.64e-2
9.09e-2
1.48c-1
2.12c0
3.06e1
2.74c2
ARCLQN
Positive Definite
3.64c-3
6.03e-3
6,45c-3
7.90e-3
2.68c-2
2.70c-1
2.33e0
4.2
AUTOENCODING
We also experiment with using ARCLON as an optimizer for an autoencoder, as detailed in Good dataset and compare against number of recent optimizers Kingma and Ba 2013); Ruder (2016); Ma (2020); Yao et al. (002)) Hyperparameters are detailed in Section C the appendix. For this experiment, as our Hessian approximation, we use an LSRI matrix Ramamurthy and Duffy (2016). Results are summarized in Figure D and Table 2 All numbers reported are averaged across 10 runs. is worth noting that while LBFGS converges more rapidly (by number of steps), it is over twice as slow as our approach (by wall clock time) and suffers from numerical stability issues: of the 10 runs performed, 2 failed due to NaN loss.
fellow et al. (2016) We use CIFAR-10 Krizhevsky (2009)
Test Loss
SGD
Table 2: The amount of time taken to achieve best recorded test loss, relative to SGD, Timing infor- mation included parts of training. but excluded calculation test set loss.
Adillessian
150
Apollo
loos
L.FRISS
ARCLON
Test
102
Optimizer SGD Adam
Cost (xSGD)
1.00
50-
1.00
AdaHessian
1.01
Apollo
1.00
Epochs
LBFGS
5.45
ARCLQN 1.95
Figure 1: Test set loss of the trained CIFAR-10 autoen- coder, evaluated at the end of each epoch.
4.3 IMAGE CLASSIFICATION
We additionally perform experiments on image classification using the ImageNet dataset Deng et al. 20099 Motivated by Chrabaszez et al. (017) and lack of computational resourees, we resize ImageNet et to 32x32. Following Ma (2020). we use modified version of ResNet- 18 (dubbed ResNet- 110) adapted for smaller image sizes. Additionally, we use the best hyperparameters from TromMMi] (220)) namely, the learning rate, epsilon, and momentum for all optimizers. Here we use the desitive-detintt diagonal Hessian approximation presented by Ma (2020) as our Bg- Unlike the other optimizers which received extensive hyperparameter searches, ARCLQN achieves strong results using the same
single NVIDIA V100 GPU over 2 days. 3 All experiments in this section were run on a single NVIDIA A 100 GPU over 3 days.
All experiments in this section
8

---

Under review as a conference paper at ICLR 2023
hyperparameters in the CIFAR-10 experiments. This is of significance: proposed method outperforms or compares to all optimizers considered without expensive hyperparameter tuning or hacking. It is worth noting that Apollo, the optimizer proposed by Ma (202)), requires long warmup period for good performance. Our approach has no such requirement. We theorize this result is due combination of defaulting SGD failure and the ARC framework preventing any steps that would otherwise degrade performance. Finally, in Table 3 with both the highest Top-1 accuracy and the lowest computational cost.
we can see that ARCLQN is associated
Training
Test Accuracy
SGD
Trmining Average Loss
RAdam
Tedl Top-1 Accurcc
AdaBcliel
Apollo
ARCLON
SGD
Adam
RAdam
Apollo
0-
ARCLON
Epochs
Epochs
Figure 2: Average training loss for each epoch.
Figure 3: Test set accuracy for each epoch.
Table 3: Table summarizing performance of different optimizers. The corresponds the amount of time taken achieve best recorded test accuracy, relative SGD, Timing information included all parts of training, but excluded calculation test set accuracy.
Optimizer
Best Top-1 Accuracy
Best Top-5 Accuracy
Cost (xSGD)
SGD
35.89
60.09
1.0
Adam
36.12
59.85
0.86
RAdam
34.89
62.06
0.90
AdaBelief
34.61
61.38
0.96
Apollo
36.38
61.74
0.76
ARCLON
36.59
61.76
0.69
CONCLUSION AND DISCUSSION
Conclusion. We have introduced a new family optimizers, referred ARCLQN, which utilize novel fast lcrge-scale solver for the CR subproblem. We demonstrate very large speedups over a baseline implementation, and we find that ARCLQN is competitive with modern first-order and second-order optimizers on real-world nonconvex problems with minimal tuning. To the best of our knowledge, ARCLQN the first extension of the ARC framework to limited memory case without major modification of the core framework. We additionally expand upon ARC, explicitly incorporating first-order updates into our methodology. Finally, we provide convergence analysis of the modified framework which proves convergence even for the nonconvex case.
Limitations. While we have introduced an optimization framework that is applicable to any Hessian approximation that has a fast cigendecomposition, we do not consider Hessian approximations for which this information is not readily available. Additionally, if our Hessian approximation' s eigenvalues differ greatly between steps, this can lead to oscillation in the calculated ||sı|] ||- Future work may also include wider variety of evaluated Hessian approximations, as there are many which were not tested here.
Reproducibility Statement In this paper provide all details to recreate our implementation, in- cluding algorithms matching how the optimizer is written in code. These are located in Section 3 We also provide all implementation details and hyperparameters in Section and Section respectivel..

---

Under review as a conference paper at ICLR 2023
REFERENCES
Neculai Andrei. Accelerated modified memory-less SRI method with cubic regularization for unconstrained optimization, 2021. /tLAttpss//cmm...........
pdf
A. S. Berahas, M. Jahani, Richtárik, and M. Takáč. Quasi-newton methods for machine learn- ing: forget the past, just sample. Optimization Methods and Software, 0(0): 1-37, 2021. doi: 10. 001100000055678.2221..177777
URL httph::: /
2021
1977806
El Houcine Bergou, Youssef Diouane, and Serge Gratton. On the use of the energy norm in trust-region and adaptive cubic regularization subproblems. Computational Optimization and Applications, 68 (3):533-554, 2017. URL http::ttp////t /ttp://............000/0//-----/
9929-2999222222
Johannes Brust, Jennifer B. Erway, and Roummel F. Marcia. On solving L-SRI trust-region subproblems. Compulational Optimization and Applications, 66:245-266, 2017.
Oleg Burdakov, Lujin Gong, Spartak Zikrin, and Ya-xiang Yuan. On efficiently combining limited- memory and trust-region techniques. Mathematical Programming Computation, 911:1011-33, 2017.
R. H. Byrd, S. L. Hansen, Jorge Nocedal, and Y. Singer. A stochastic quasi-newton method for large-scale optimization. SIAM Journal on Optimization, 26(2); 1008-101,, 2016. doi: 10.1137/ 140954362. Utthttpss:/ wwwpiioorg/1... 1tt.:///....1111000111
Coralia Cartis, Nicholas I. M. Gould, and Philippe Toint. Adaptive cubic regularisation methods for unconstrained optimization, part i: motivation, convergence and numerical results. Mathematical programming, 127(2):245-295, April 2011. ISSN 0025-5610. doi: 10. 10000077/11107--00-00-6--5
Huiming Chen, Ho-Chun Wu, Shing-Choo Chan, and Wong-Hing Lam. A stochastic quasi-newton method for large-scale nonconvex optimization with applications. IEEE Transactions on Neural Networks and Learning Systems, 31(11):47764499 2020. doi: 10. 11111119N1.1101991.2.
R. Chen, M. Menickelly, and K. Scheinberg. Stochastic optimization using trust-region method and random models. Mathematical Programming, 1690))447-447. 2018. ISSN 1436-4646. doi: 10. 1007/s10107-017-1114 1141-8. URL htLLhtts:://// /oi. 0ttp:///000100001101000001111111
Weizhu Chen, Zhenghao Wang, and Jingren Zhou. Large-scale I-bfgs using mapreduce. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, ed- itors, Advances in Neural Information Processing Systems, volume 27. Curran Asso- ciates, Inc., 2014. URL e 449588005255500111444300........
Patryk Chrabaszez, Ilya Loshchilov, and Frank Hutter. A downsampled variant of imagenet as an alternative to the cifar datasets, 2017. URL httpt:://////. http/axxivvv.
http:::/acciv..og////e wwtpw/wwwwww./////...o./.. 1777//000//777111
Jia Deng, Wei Dong, Richard Socher, I.iJiia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hier- archical image database. 2009 IEEE Conference on Computer Vision and Pattern Recognition, doi: 10. WWW.CC/R.20095200000
pages 245.255, 2009.
Jennifer B Erway and Roummel F Marcia. On efficiently computing the eigenvalues of limited- memory quasi-newton matrices. SIAM Journal on Matrix Analysis and Applications, 36(3): 2015.
Jennifer B Erway. Joshua Griffin, Roummel Marcia, and Riadh Omheni. Trust-region algo- rithms for training responses: machine learning methods using indefinite hessian approximations. Optimization Methods and Software, 38(3):460-487, 2020.
Donald Goldfarb, Yi Ren, and Achraf Bahamou. Practical quasi-newton methods for training deep neural networks. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 2386-2396. Curran As- sociates, Inc., 2020. URL httpt:ttt///cc / ngs neuri ps wts.cc//peeee httccc//ppppe 22000//12222011/11 1e/ 1 192 4e 4df 44 wwwffffasscf3333 44c.e4444ff444444443443333333333 Pwwpaaaawaaa..oeeeea..eo...
10

---

Under review as a conference paper at ICLR 2023
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.
Nitish Shirish Keskar and Albert S. Berahas. adaqn: An adaptive quasi-newton algorithm for training rnns. In Paolo Frasconi, Niels Landwehr, Giuseppe Manco, and Jilles Vreeken, editors, Machine Learning and Knowledge Discovery in Databases, pages 1-16, Cham, 2016. Springer International Publishing. ISBN 978-3-319-461288
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL http:://are hwtp:/ivwrrgbbb///iiee 6980
Günter Klambauer, Thomas Unterthiner, Andreas Mayr, and Sepp Hochreiter. Self-normalizing neural networks. CoRR, abs/1706.02515, 2017. (Rth:tt:///axxiii httpaaawwwww....a//aaaaaaaaaaaae 02515
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
Ching-pei Lee, Po-Wei Wang, and Chih-Jen Lin. Limited-memory common-directions method for large-scale optimization: convergence, parallelization, and distributed optimization, Mathematical Programming Computation, Mar 2022. ISSN 1867-2957. doi: 10. 10077/112532-022-0021444
URL /tttp:://doi.oo//1000/ 1007 1010:///011..1100/25522222222220 00219-2
Y Liu, M Zhang, Z Zhong, and X. Zeng. AdaCN: An Adaptive Cubic Newton Method for Nonconvex Stochastic Optimization. Comput Intell Neurosci, 2021 :5790688 2021.
Ilya Loshchilov and Frank Hutter. SGDR: stochastic gradient descent with warm restarts. In 5th
International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26. 2017, Conference Track Proceedings. OpenReview.net, 2017. URL httpss:://ppeeeeiiiiiie
set/forrumid-SSk39550
Xuezhe Ma. Apollo: An adaptive parameter-wise diagonai quasi-newton method for nonconvex stochastic optimization, 2020.
James Martens al. Deep learning via hessian-free optimization. In ICML, volume 27, pages 735-742, 2010.
Aryan Mokhtari and Alejandro Ribeiro. Res: Regularized stochastic bigs algorithm. IEEE Transac- tions on Signal Processing, 62(23))6089-6100 2014. doi: 10.1 20.1109//SP221122337777
Yurii Nesterov and Boris T Polyak. Cubie regularization of newton method and global performance. Mathematical Programming. 177(2): 2006.
Jorge Nocedal and Stephen J Wright. Quasi-newton methods. Numerical optimization, pages 135-163, 2006.
Courtney Paquette and Katya Scheinberg. A stochastic line search method with expected complexity analysis. SIAM Journal on Optimization, 30(1): (139))3393366 -76,, 2020. doi: 10.1137/18M1216223 URL
Sconho Park, Seung Hyun Jung, and Panos M. Pardalos. Combining stochastic adaptive cubic regular- ization with negative curvature for nonconvex optimization. 184(3), 2020. ISSN 0022-3239, doi: 10.
1007/s10957-011-016222 /tt.///ae///ooo....//0//0.000000
Ching pei Lee, Po-Wei Wang. Weizhu Chen, and Chih-Jen Lin. Limited-memory Common-directions Method for Distributed Optimization and its Application on Empirical Risk Minimization, pages
732-740. doi: 10.113771.978111119944499
httlhttts//:puulee sian. siam.org/doii.....o.oo wwt./oi/abbbo
Vivek Ramamurthy and Nigel Duffy. L-SR1 A novel second order optimization method for deep learning. 2016.
Aditya Ranganath, Mukesh Singhal, and Roummel Marcia. L-SRI adaptive regularization by cubics for deep learning. 2022. URL htt.tps://opeereiiiiiii wttp:rrrwwweeeeeeeorruuuumm
net./ wttp://orommmmmm wtw.ooorommmoiooddodd-od-

---

Under review as a conference paper at ICLR 2023
Sebastian Ruder. An overview of gradient descent optimization algorithms. CoRR, hess/1609.4474. 2016. URL [KLL/ttp://axxiv.oo wttp://apaaaa..ooo.oooo C4747
Nicol N. Schraudolph, Jin Yu, and Simon Günter. A stochastic quasi-newton method for online convex optimization. Marina Meila and Xiaotong Shen, editors, Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, volume 2 of Proceedings of Machine Learning Research, pages 436 443, San Juan, Puerto Rico, 21-24 Mar 2007. PMLR.
URL httpss//pprocccciggss. mlr prwss / htm
Jascha Sohl-Dickstein, Ben Poole, and Surya Ganguli. Fast large-scale optimization by unifying stochastic gradient and quasi-newton methods. In ICML, 2014.
Nilesh Tripuraneni, Mitchell Stern, Chi Jin, Jeffrey Regier, and Michael Jordan. Stochastic cubic regularization for fast nonconvex optimization. Advances in neural information processing systems, 31, 2018.
Xiao Wang, Shiqian Ma, Donald Goldfarb, and Wei Liu. Stochastic quasi-newton methods for nonconvex stochastic optimization. SIAM Journal on Optimization, 27, 07 2016. doi: 10.1137/ 15M1053141.
Zhewei Yao, Amir Gholami, Sheng Shen, Kurt Keutzer, and Michael W Mahoney, Adahessian: An adaptive second order optimizer for machine learning. AAAI (Accepted), 2021.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In 5th International Conference Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL htt.ttts./oopeeeiiicieeeeee wwtp:/rrmttttemee.ee./ Sy8gdB9xxy
W. Zhou, Akrotirianakis, S. Yektamaram, and Griffin. matrix-free line-search algorithm for nonconvex optimization. Optimization Methods and Software, pages 1-24, 2017.
Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, Dean Foster, and Sham M. Kakade. The benefits of implicit regularization from SGD in least squares problems. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances Neural Information Processing Systems, 2021. URL httpps: / ew, net. fo rum? 14x0ro__-dop
12

---

Under review as a conference paper at ICLR 2023
A ETHICAL CONSIDERATIONS
With the ever-increasing utilization and adoption of more powerful models, it is more and more important for authors to consider the ethical aspects of their work. Our work presented here is very general in nature, as it is possible to use ARQLQN as an optimizer for any function where gradient information is easily available.
major positive impact from this paper and subsequent research may be substantial reductions in power consumption, as is seen preliminarily in the significantly reduced runtime in 3 Additionally, as a general-purpose optimizer, this work may help progress societally beneficial research (such in medicine). However, it also holds the ability to be misused (e.g., being used to train unethical models that discriminate hased of protected personal attributes). This potential for misuse is inherent to all general-purpol optimization research. Avoidance of this may be impractical, and is beyond the scope this work.
In our numerical results section (Section 4, we two image based datasets: CIFAR-10 and ImageNet. Improper or careless use datasets that contain sensitive information should be avoided where possible. We believe both CIFAR-10 10 and the version of ImageNet used pose very little risk, as both of the datasets are at 32x32 resolution, hiding most sensitive information. The research done in this paper abides by the licenses provided by the authors of the datasets.
B IMPLEMENTATION DETAILS
Second-order methods times be unstable. To achieve good performance and stable training, it is important to use heuristics to prevent or alleviate this instability. For the sake of complete transparency, share all used heuristics and modifications not explicitly detailed elsewhere. It is worth explicitly noting that none of the parameters below have been tuned for performance, and instead have been chosen either arbitrarily, or via test-runs on toy problems. There may be significant room for improvement with tuning of these parameters, and we leave that to future work.
B. GENERAL DETAILS
An important detail is that we do not check if Φ1 (A) = 0 when using Newton's 's method in Algorithm Instead, we repeat the while loop until |||| set // 1c-5. For comparison to SR1, we set < v. For CIFAR-10 and ImageNet experiments, we 1c-7. We empirically find that for larger scale problems, // can be set higher, as Φ1 (A) does not change much at the final iterations of Algorithm] For CIFAR- experiments, and Ba (0015). Finally, we also bound a above, as rarely & < ?)) can occur multiple times in a row, which can lead many very small steps being taken with little effect on performance.
do not take actual SGD step, but instead use Adam step Kingma
B.2 LSRI SPECIFIC
If we repeatedly take very similar or very small steps, we can run into issues with Sy being singular or Bg being ill conditioned. We use two heuristics to detect and fix this. First, before updating Bx on lines 12 and 20 of Algorithm we set y max and from becoming ill-conditioned if ||||| very small. Additionally, we also reset B& if the minimum eigenvalue of S S& is less than When we 'reset" BE. we drop the first and last column of S& and Yu instead of setting B₁ +- I; this helps us prevent resetting from destroying too much curvature information. We set 1e-7.
max{] This prevents B
C HYPERPARAMETERS
This section will detail optimizer settings not otherwise explicitly mentioned in the paper. For all experiments, default dataset splits are used.
C.1 CIFAR-10.
The hyperparameters used to generate Figure can be found in Table 4 For CIFAR-1O experiments, a2 = 0.005 for ARCLQN was set arbitrarily. For ARCLQN, we use 7h = 0.05, 772 = 0.6; these
13

---

Under review as a conference paper at ICLR 2023
hyperparameters were not tuned, but instead set be similar to Cartis et al. (2011) For all optimizers with momentum, values were left at their defaults and not tuned. Since the Apollo paper emphasizes that warmup is extremely important for their method, we use linear warmup over 500 steps Ma (2020). We performed a hyperparameter search over learning rates in a E {_001, .0. all optimizers. For applicable optimizers, also searched for the optimal For each optimizer, we chose the hyperparameter settings that lead to the lowest test loss after 10 epochs. For limited memory methods, fixed the history size at neural network Goodfellow et al. (2016) with convolutional layers, then 3 transposed convolutional layers. For all layers, padding and stride are to 1 and 2 respectively. Between all layers (except the middle one), SeLU Klambauer et al. 2017) activations are used; the final layer uses sigmoid activation. Layers have 3, 12, 24, 48, 24, and input channels respectively; minibatch size is fixed as 128. We use binary cross-entropy as our loss function.
for
{1e-4, 1e-8, 16-16).
We a convolutional
Table 4: Hyperparameter settings for the optimizers used in the CIFAR-10 autoencoding experiments. A dash indicates that the optimizer does not have given hyperparameter.
Optimizer
Q
B
SGD
0.01
0.9
Adam
0.001
(0.9, 0.999)
1e-8
Apollo
0.01
0.9
1e-8
AdaHessian
0.1
(0.9, 0.999)
le-4
LBFGS
ARCLQN
(.75, 0.005)
(0.9, 0.999)
le-4
C.2 IMAGENET
The hyperparameters used to generate Figure and Table 3 can be found in Table 5 For AR- CLQN, we use the same hyperparameters as in Table We use the cosine learning rate annealing scheduler Loshchilov and Hutter (2017), in line with Ma (2020), from which take many of our hyperparameters.
Table Hyperparameter settings the optimizers used ImageNet classification experiments. dash indicates that the optimizer does not have a given hyperparameter.
Optimizer
SGD
0.1
0.9
Adam
0.001
(0.9, 0.999)
1e-8
RAdam
0.001
(0.9, 0.999)
1e-8
AdaBelief
0.001
(0.9, 0.999)
le-4
Apollo
.01
0.9
le-4
ARLQN
(.75.0.005) 0.005)
le-4
D PROOF OF SUBPROBLEM SOLVER COMPLEXITY
This section contains the full proof of many of the claims located in Section D We will restate the assumptions made there, then progress with the proofs.
Assumption 1.
The matrix column replaced, then only one row and column of T is updated.
v v is stored and updated incrementally. That if has one
Assumption 2. The vector ū = v is computed once each iteration of Algorithm 3 and stored.
Unlike trust-region methods, the cubic-regularization search steps can sometimes quickly grow when negative curvature is found. To stabilize the approach we assume a safeguard is used (as in line-search methods Zhou al. (2017) that uniformly bounds the second-order correction matrix from singularity.
Assumption 3. The final search direction has form
-ー
14

---

Under review as a conference paper at ICLR 2023
where Aạ max(T, Au + x*) for small positive constant T where A is given by Equation and X*
denotes the optimal found by Algorithm !1]
The following theorem shows that given T and defined in Assumptions I and that the optimal X* can be cheaply obtained by Algorithm using ((m²) operations.
Theorem 2. Suppose that B del II + VM- as defined Equation 10 and that (V, A) solves the generalized eigenvalue problem Me = XTv. Then U2 as defined in 12 is given by U2 V.. Further the corresponding eigenvalues Å from Equation 11 are given by A (7l + A- We can
then recover Ú22 V ú, and [1 g" 9/ 92.
Proof. Rather than inverting M simply solve the generalized eigenvalue problem [V,A] (M, v V) where
MV V'VV V MV A V VV 1, where A is the diagonal matrix of generalized eigenvalues for the system Me >x Tu. Then we
have U2= = VV implying
BU2 7U2 + VM TT VM- (VVVA -1 = -U2 W. MVA- U2(7 + A-
Thus we can can set Å from equation V 7 V a and | = g"
as Å (+/+A-)) Further we can recover و2 U
a o||s*|| from Algorithm | in O(m²) additional operations once T and ū are formed. We now show how to efficiently recover the optimal s* from Equation using (mn) operations.
Using the previous theorems and Equations
13 and 14 we can thus obtain x
Theorem 3. Using the same assumptions and definitions in Theorem given any X max(0,- ->1), the solution (B X1) is given by X+7 Vrr where can be
formed with O(m)) computations.
Proof. Note we can further save on computation by storing V g for later calculations when we recover the final search direction. Note that the very end we must form the search direction by solving the system (B- + X = with the optimal value of X. This implies
8 -U + AUT
= A+7 UNT U2(A -
X+7 (U.Uf g (U2U2 U. 9)) - (Ā + AT) -
9 U2((((A + -1- X+7 NUTT
=
A A+75 --
A+7 -
where E' = -
Theorem Let (A1, denote the eigenpair corresponding to the most negative eigenvalue of the matrix B. Then, i < (diag(A)), )), in can be formed as u1 = -/||f|] where ř = (I U2U yr for any vector in R such that ||Al| O. Otherwise un Trg where Ug is column of V that corresponds to the smallest eigenvalue of Å.
Proof. Note that (1- - U2U?") is the projection matrix onto the subspace defined by the span(U;) implying Uzf = 0, then Bf = UUU 7(1 U2UF) = yf, since ? has already been projected.
Thus 8 is an eigenvector of ry If y is not the smallest eigenvalue of B, then by design un can be obtained from U2e1 assuming the eigenvalues of Ả are sorted smallest to largest.
n
15

---

Under review as a conference paper at ICLR 2023
E CONVERGENCE ANALYSIS
Several useful assumptions are given to establish the global convergence of Algorithm 3 Let below denote minibatch.
Assumption 4. The function f(x) is bounded below by scalar L
Assumption 5. fx) is Lipschitz continuous for all æ. That is, | fx)) - vf(v)) - -1||== yll-
Assumption 6. (x) is Lipschitz continuous for all x. That is. [[(()) - H()Il - L2 - yll-
Assumption 7. For any iteration k, we have that Ezg(Z b]] (zx).
Assumption For any iteration for all TR- That is, [1g b)ll S Log
have that the gradient for that minibatch g b) is bounded
Assumption For any iteration we have that the hessian for that minibatch H (av, b) is bounded for all rk. That is, || b)ll S LH-
From the results below, Algorithm 3 will iteratively reduce f(z) with probability one when oy goes O. Thus, it is expected that Assumptions and can be satisfied.
In Algorithm 3 ai and a2 are used as the learning rates. To simplify the notation, og is used in this section as either of them for a given iteration k. The following assumption is then given.
Assumption 10. The sequence of learning rates og in Algorithm 3 is chosen such that:
1. Σ 1= a; +00
2. Σ k= a +o0
The first theorem below ensures [ wiill will solve problem and it can be found in Cartis ct al. (011T)
Theorem 5. (Cartis al. (2017)) Algorithm converges to the global solution of problem whenever the initial X satisfies max -}1) < x <||s|| where x denotes the smallest eigenvalue of Bt.
Note that an initial À for the preceding theorem is easily found by choosing À suitably close to its lower bound.
The following lemma can be found in Berahas et al. 2201
Lemma 6. (Berahas et al. (2021)) Suppose that æı is generated by Algorithm Jndd assumption holds, and also Bg is the Hessian approximations updated by Equation] when the new curvature pair satisfies Equation!
3 Then there exists a constant > 0 such that | S..
Using Lemma 6 the following important theorem can be derived.
Theorem Suppose that zı generated by Algorithm Bariidmmmannddda assumption holds and also By is the Hessian approximations generated by Equation 2 when the new curvature pair satisfies Equation 3
then there exists a constant C2 > O such that Bs + oh sx ||||| < 02
Proof. We will first show that œ ll s is always bounded for all k.
Let Bg UT AU, and where A is diagonal matrix and UTU = I,
Then, we have:
B + = UT(A +
Therefore,
(Bx + +x + + UZ (A !)
[) + oR ls
Because of Lemma there exists Ahin and Ahar such that
x7 [BB o s [] axllsa|(T) $ (oxl|sx] + 2 (20)
(ox [ | + ) $
xT
16

---

Under review as a conference paper at ICLR 2023
for all nonzero Note that Amnin and X bounded by c1-
Set x = Sk+1 in Equation 20 and because of 8k+1 is solution of Problem we have:
I
(o + )
96. 9k-
[ok|s \max)
(21)
2 R+1 Sk+1
There are two scenarios now.
1. gh. 9k
is bounded. Because of Equation 21 we can easily conclude that o (1l is
96415k+7 8k+1
bounded. Thus, the lemma follows.
96
is unbounded. That is, there exists M₁. such that gh 9k
2.
2 Mr.
$41 5k+1
$k+ sk+1
9 9
Because Assumption 8 g Ik bounded. We have that of.8
0 as
is
$ Sk++
unbounded. Using Taylor expansion, we note that from Equation 17
Pk f(xx) f( + Sk)
f(xx) (x()
f(xx) mm((sk) (11ss [(xx) (sk)s)
(22)
But || M&l[sall we have:
f(xx) (sk) = - sk of B
2 - M $k 12 - ei 8k 12
(23)
when ||s|| is small. Therefore, when sy is very small, combining Equation 22 and have:
23 we
0(1|s11))
1pk 11
f(xN) mm (sk)
(11+|3))
Mx|1sx|1 + c1 |
Because M₃g + 0o, we can now conclude that Pk > as | + 0. This means that dk is unbounded, we have that ||sa|] - and aj. is
is bounded. Therefore when 9h Ok
$ SR+1
bounded. Therefore 0 || is bounded.
We can then conclude that | + < ||]|| bounded.
We now focus on the proof of the convergence of Algorithm Lemma 8. Suppose that I& is generated by Algorithm Then, there exists C4 such that:
3 and assumptions
3
6 8 and hold.
a 2
El((x++1)
E[[(xx)]
Ok E
c4
(24)
C3
Proof. Because of Assumption 3 we have that there exists a c3 > 0 such that
T (Br + ox @s|lsw|[[)s 2 cal|s||2
(25)
holds for all the and iterations kt
Now suppose Ws+1 = 2y + arg8 From the Taylor theorem, there exist 0g such that:
+ at
f(*+11) = f(xx) + on (V(())
2 s (( )sk-
(26)
Now there two scenarios.
17

---

Under review as a conference paper at ICLR 2023
1. p 2 7/2 So 8p is the solution of the cubic regularized subproblem. Thus, Equation 26 becomes
f(xx+1) f(xx) argh (Bx + AR||s 1V) a T s (0x)ss (27)
Let (fxx)= - 9k + Ex. By Assumption we have (T 0.
So from Equation 27 now we have:
f(xx+1) f(zx) at V (B₁ + A
a15k (BB + >e||sa|| (V) + of
2 84 H(Ak)) (28)
Note that because of Equation 25 and Assumption 8 we have:
ca||sx|1 s of (Ba + Asl)ss
| Lg sx
(29)
Thus, is bounded.
Because of Equation
28 we further have:
f(*x+1) S f(xx)
V (xxx) [1
C3
a 2
O V (fxx) (Be + | 1
+
H (l 8k:
Because of Assumptions
and the above equation becomes:
((1*+1)$$f f(x)) 0 [f(x)))
a V) (Br \n|[sx|[T) + of (L2llskll Ln)11s111. La>)llll (30)
2
We now take the expected value both sides of the above inequality, Because of F((x((t))) =
0, we have:
Elf < f(xx)
akk
vf(xx)))
at + =
(L2 Lg
(31)
C3
2
c3
C3
2. p < Mi, that is, the SGD direction is used as sg. Similarly, have:
2 L3
E[f(r++))ar)) fzx) az vf(xx))
(32)
Thus, combining with Equations and 32 have that there exists c4 such that:
(((((x+1)(z)) f (ax))
ak
[V](2x)]]
ax c4.
(33)
C3
Thus Lemma holds.
Theorem 9. Suppose that æy is generated by Algorithm 3 and assumptions hold. Then, we have:
f
and
lim f[
0.
(34)
Proof. Because of Lemma
we have:
N
N Σ
N Σ
E[f(1x+))
Σ Elf(zx)]
ElIVf((
+
C4.
c3
2
A=
18

---

Under review as a conference paper at ICLR 2023
That is,
N
N
((x())))
Σ ([[
+
ag
2
k=
k=1
Thus,
N
N
f(x1) f(xN+1)
+
#
C4.
(35)
C3
2
Krm
km
Note:
F [(x)))
or E Vf(x))]
(36)
EE as)) k=1
So, from Equation 35 and 36
we have:
1= Oa
[(())]
Ell V (xxx)
C3
cs
N
a
$ f(x1) - f(xN+1) +
c1.
2
k=1
That
F 2
E
f(xr)
(f(x1) - f(xN+1)) +
k=
o C3C4
(37)
Em 04
5
0j 2
Because of Assumption
and 10
have:
lim ( O. k
(38)
Thus, the theorem follows.
19


Reviews:
[{"review_id": "yCI0Paovc9", "reviewer": "Reviewer_4R9H", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors provide to their knowledge the first matrix-free Newton's method in reduced subspace to obtain exact solution of cubic-regularization (CR), which is much faster than the previous CR solvers. Then, the previous ARC algorithm is expanded to ARCLQN algorithm using LQN matrices, to incorporate SGD and the proposed exact cubic-regularization solver. ARCLQN is proved to converge to stationary point and empirically demonstrated more efficient than existing CR-based algorithms.", "summary_of_the_review": "Based on \"Strength And Weaknesses\" above, I currently recommend borderline reject for this paper. If the authors can solve the above listed problems, especially my two major concerns (item 1 of clarity and quality), I would like to raise my rating. ", "strength_and_weaknesses": "Pros: The ideas of matrix-free exact CR solver and incorporating SGD when the update of $B_k~$fails look novel. Lit review looks very comprehensive. Experimental results look good. \n\nCons: There is lack of clarity, non-asymptotic convergence rate results and objective functions for experiments, as listed in \"Clarity, Quality, Novelty And Reproducibility\". ", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "de9InRa5cM", "reviewer": "Reviewer_ZmCM", "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": "", "summary_of_the_paper": "This paper proposes a novel fast exact subproblem solver for stochastic Quasi-Newton cubic regularized optimization.\nThe solver can much reduce the computation cost and is easy to implement.\nI believe this method has potential applications in non-convex optimization.", "summary_of_the_review": "The solver proposed in this paper can much reduce the computation cost and is easy to implement.\nI believe this method has potential applications in non-convex optimization.", "strength_and_weaknesses": "The solver proposed in this paper can much reduce the computation cost and is easy to implement.\nI believe this method has potential applications in non-convex optimization.", "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": "ULt0h1MRQXi", "reviewer": "Reviewer_VDMs", "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 work studies using L-BFGS method to solve the cubic subproblem in the second-order optimization. The authors provide theoretical analysis to suggest their method converges. Experiment results show their algorithm is empirically better than existing approaches. ", "summary_of_the_review": "This paper studies how to efficiently solve the cubic sub-problem given the limited-memory limit. However, the contribution of this work is somehow limited, and its presentation also needs to be further improved. Thus I recommend a reject to this paper. ", "strength_and_weaknesses": "Pros:\n\n- The algorithm design is clear.\n\nCons:\n\n- This work may lack importance. Although making an efficient cubic-subproblem solver is a very important task in second-order optimization research, the main contribution of this work seems only to be providing an efficient implementation of solving a Newton method by adapting the low-rank structure, which does not contribute a lot of new knowledge to the optimization community. \n\n- The presentation of this paper is very confusing. For instance, \n\n-- Page 5, the authors keep mentioning matrices $S$ and $Y$. What are their definitions? \n\n-- Page 5, the matrix $\\Phi$ is defined in (10), which serves as one component from the decomposition of $B$. However, later in Assumption 1, the authors mention 'replace columns in $\\Phi$), which confuses me since $\\Phi$ should be some fixed matrix. \n\n- I suggest the authors compare their L-BFGS algorithms with some Krylov subspace-based algorithms for solving the cubic subproblems, such as [1]. It is interesting to see how their computational complexity differs from each other, given the fact that the approximate Krylov subspace-based algorithms actually perform very well in practice.\n\n[1] Kohler, Jonas Moritz, and Aurelien Lucchi. \"Sub-sampled cubic regularization for non-convex optimization.\" International Conference on Machine Learning. PMLR, 2017.\n\n- The experiments need more demonstration. For instance, \n\n-- In Table 3, I do not understand why SGD achieves the highest cost, compared with other algorithms. Are they supposed to run the same 25 epochs? If so, it is strange because SGD should enjoy the lowest cost since any other algorithms need additional computation besides the computation of gradients.\n\n\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": {}}]

Author rebuttal:

Decision: Reject