FOSI: Hybrid First and Second Order Optimization
Authors: Hadar Sivan
Moshe Gabel
Assaf Schuster
Venue: ICLR 2024 poster (2024)
Keywords: convex optimization
nonconvex optimization
first order optimization
second order optimization
deep learning
Primary area: optimization
TL;DR: FOSI is a novel meta-algorithm that improves the performance of any first-order optimizer by efficiently incorporating second-order information.

Abstract: Popular machine learning approaches forgo second-order information due to the difficulty of computing curvature in high dimensions.
We present FOSI, a novel meta-algorithm that improves the performance of any base first-order optimizer by efficiently incorporating second-order information during the optimization process.
In each iteration, FOSI implicitly splits the function into two quadratic functions defined on orthogonal subspaces, then uses a second-order method to minimize the first, and the base optimizer to minimize the other.
We formally analyze FOSI's convergence and the conditions under which it improves a base optimizer.
Our empirical evaluation 
demonstrates that FOSI improves the convergence rate and optimization time of first-order methods such as Heavy-Ball and Adam, and outperforms second-order methods (K-FAC and L-BFGS).

Published as a conference paper at ICLR 2024
FOSI: HYBRID FIRST AND SECOND ORDER OPTIMIZATION
Hadar Sivan
Moshe Gabel York University
Assaf Schuster
Technion
Technion
Haifa, Israel
Toronto, Canada
Haifa, Israel
hadarsivan@cs. wwchnien.ccc... ac.il
mgabel@yorku.ca
assaffcs. technion.cce ac.
ABSTRACT
Popular machine learning approaches forgo second-order information due to the difficulty of computing curvature in high dimensions. We present FOSI, a novel meta-algorithm that improves the performance of any base first-order optimizer by efficiently incorporating second-order information during the optimization pro- cess. each iteration, FOSI implicitly splits the function into two quadratic func- tions defined on orthogonal subspaces, then uses second-order method to mini- mize the first, and the base optimizer to minimize the other. We formally analyze FOSI's convergence and the conditions under which improves a base optimizer. Our empirical evaluation demonstrates that FOSI improves the convergence rate and optimization time of first-order methods such as Heavy-Ball and Adam, and outperforms second-order methods (K-FAC and L-BFGS).
INTRODUCTION
Consider the optimization problem ming f(0) for twice differential function f R" - R. First- order optimizers such as gradient descent (GD) use only the gradient information to update (Kingma & Ba 2014 Tieleman et al., 2012 Duchi al. 2011 Polyak 1987 Nesterov 20033) Conversely, second-order optimizers such as Newton's 's method update & using both the gradient and the Hessian information. First-order optimizers are thus more computationally efficient as they only require evaluating and storing the gradient, and since their update step often involves only element- wise operations, but have lower convergence rate compared to second-order optimizers in many settings (Tan & Lim, 2019). Unfortunately, second -ocder optimizers cannot be used for large-scale optimization problems such deep neural networks (DNNs) due the intractability of evaluating the Hessian when the dimension is large.
Despite recent work on hybrid optimizers that leverage second-order information without computing the entire Hessian (Henriques et al. 2019 Martens & Grosse, 2015) Gupta et al. 2018 Goldfarb cct al. 2020; Sivan et al.] 2022), first-order methods remain the preferred choice for two reasons. First, many hybrid methods approximate the Hessian rather than the inverse preconditioner directly, resulting in amplifying approximation error and noise (Li (017). Second, no single optimizer best across all problems: the performance of an optimizer can depend on the specific characteristics of
the problem it is being applied to (Nocedal & Wright 1999; Wilson et al. 2017 Zhou et al. 2020).
Our Contributions. We propose FOSI (for First-Order and Second-order Integration). an alterna- tive approach. Rather than creating a completely new optimizer, FOSI improves the convergence of any base first-order optimizer by incorporating second-order information. FOSI iteratively splits min, f(0) into pairs of quadratic problems on orthogonal subspaces, then uses Newton's method to optimize one and the base optimizer to optimize the other. Unlike prior approaches, FOSI: (a) esti- mates the inverse preconditioner directly, reducing errors due to matrix inversion; (b) only estimates the most extreme eignenvalues and vectors, making it more robust to noise; (c) has low and control- lable overhead; (d) accepts a base first-order optimizer, making it well suited for a large variety of tasks; and (e) works as "turn key" replacement for the base optimizer without requiring additional tuning. We make the following contributions:
A detailed description of the FOSI algorithm and thorough spectral analysis of its preconditioner. We prove FOSI converges under common assumptions, and that it improves the condition number of the problem for large family of base optimizers.

---

Published as a conference paper at ICLR 2024
An empirical evaluation of FOSI on common DNN training tasks with standard datasets, showing improves over popular first-order optimizers in terms of convergence and wall time. The best FOSI optimizer achieves the same loss the best first-order algorithm in 48%-77% of the wall time, depending on the task. We also use quadratic functions to explore different features of FOSI, showing it significantly improves convergence of hase optimizers when optimizing ill-conditioned functions with von-diagonally dominant Hessians,
An open source implementation of FOSI, available http:://jithabb..o////ssaaaa/aa
2 BACKGROUND AND NOTATION
Given 0, the parameter vector at iteration r, second-order methods incorporate both the gradient & ((,)) and the Hessian H, V2 ((,) in the update step, while first-order methods use only the gradient. These algorithms typically employ an update step of the form ft+1 = 8, + d, where d, is descent direction determined by the information (first and/or second order) from current and previous iterations. Usually, d, is of the form -np,, gr. where Pr is a preconditioner matrix, & is linear combination of current and past gradients, and 17 0 learning rate. This results in an effective condition number of the problem given by the condition number of P. H,, which ideally smaller than that of H, (Zupanski) 2002). Note that Newton's 's method P, = H,, resulting in the ideal effective condition number of
Since evaluating H, for large n intractable, most prior work approximate it. This, however, results in amplification of approximation errors and gradient noise due to the need of computing the inverse P.1 (i. 2017;; techniques such as damping (Martens & Grosse 2015) that artificially modify the approximated Hessian further increase the error. As we will later show, FOSI approximates P,! directly, which avoids the error amplification induced by matrix inversion.
The Lanezos algorithm. To obtain information about the curvature of a function f without com- puting its entire Hessian, we use the Lanczos algroithm (1950). This an iterative method that finds the m extreme eigenvalues and cigenvectors of symmetric matrix A E R=*", where m is usually much smaller than n. After running m iterations, its output matrix R.xxm with orthonormal columns and a tridiagonal real symmetric matrix T E R=x which can then be used to extract the approximate eigenvalues and eigenvectors of A.
The Lanczos approximation is more accurate for more extreme cigenvalues, thus to accurately ap- proximate the largest and f smallest eigenvalues, m must be larger than k + l. Crucially, the Lanczos algorithm does not require storing A explicitly. It only requires an operator that receives vector v and computes the matrix-vector product Av. In our case, is the Hessian H, of f(0) at the point 6, We denote by hvp,(v): R" R the operator that returns the Hessian vector product H,v. This operator can be evaluated in linear time (roughly two approximations of f's gradient), using Pearlmutter's s algorithm (1994).
Notations and definitions. We use diag(v) for a diagonal matrix with diagonal v. O.n or 1m for a row vector of zeros or ones of size m, and [A, B] for concatenating two matrices n X mi X m2 into single n (m, m2) matrix. We also define several notations w.r.t a real symmetric matrix A with cigenvalues d > > da and eigenvectors VI.... v Let À be the row vector with entries A du and -n. A, (the & largest and l smallest eigenvalues), and V E Ruck+l the corresponding matrix whose columns are the eigenvectors of the eigenvalues in X. Similarly, X is the row vector [d--1.-., and p- is the corresponding matrix of eigenvectors.
3 FIRST AND SECOND-ORDER INTEGRATION
FOSI is a hybrid method that combines a first-order base optimizer with Newton's method by utiliz- ing each to operate on a distinct subspace of the problem. The Lanczos algorithm, which provides curvature information of function, is at the core of FOSI. We first provide algorithm for ap- proximating extreme eigenvalues and eigenvectors ($..I) I. We next present FOSI ($3.2), analyze its preconditioner ($3.3) discuss of momentum (3.44) and analyze convergence in stochastic settings such as DNN training ($3.5). We then discuss support for closed-form learning rates ($3.6),
reducing spectrum estimation error, and FOST's overhead 3.7
2

---

the true Published as a conference paper at ICLR 2024
3.1 EXTREME SPECTRUM ESTIMATION (ESE)
FOSI uses the Lanczos algorithm to estimate the extreme eigenvalues and vectors of the Hessian Н, Recently, [Urschel (2021) presented probabilistic upper and lower bounds on the relative error of this approximation for arbitrary eigenvalues. While the upper bound is dependent
eigenvalues of H, which is unknown, the lower bound dependent solely on m and n. To maintain such that
the lower bound small, it necessary k + We thus define a heuristic for determining m: m = max + f), In.
OIn n) and must be greater than
We now describe the ESE procedure for obtaining the k largest and l smallest eigenvalues of H, and their eigenvectors using Lanczos. ESE takes as input the function f and its parameter value 0,, and uses them define Hessian-vector product operator hvp, Next, calls the Lanczos algorithm with specified number of iterations, m. and the hvp, operator. Our implementation parallelizes hvp, computations across the batch dimension, since they involve gradient computation, and performs full orthogonalization w.r.t all previous vectors in each iteration to prevent numerical instability (Meurant Strako 2006). Finally, ESE extracts the desired eigenvalues and eigenvectors from Lanezos's outputs. The steps are summarized as Algorithm in the Supplementary Material (Appendix(AA)
3.2 THE FOSI OPTIMIZER
FOSI takes as input the base optimizer, the function be optimized, and initial point, then performs iterative updates until convergence is reached. In each iteration I, FOSI computes the gradient 8 f(6,), potentially updates the spectrum estimation, then uses both to update 0,
FOSI calls the ESE procedure every T 2 iterations to obtain À and V. the largest and smallest e eigenvalues of H, and their eigenvectors, and then computes u 1/| using element-wise absolute values. To avoid approximation errors, we postpone the first invocation of the ESE procedure by W warmup iterations (we discuss this further in $3.7 During these iterations, the updates are equivalent to those of the base optimizer, as and V are initialized as zeros.
Next, FOSI updates 6, using the following procedure:
1. Compute the sum of g projections on V's columns, 81 V(V* g:). and the sum of gi projec- tions on V's columns, 82 = gr 81. Due to the orthogonality of the eigenvectors, and g2 are also orthogonal each other.
Compute the descent direction di -VV((V 81 81)"""), where stands for the Hadamard product. While the chance of encountering an eigenvalue that is exactly or nearly O when using small k and l values very small, it is common add small epsilon to | to avoid division by such values (Kingma & Ba 2014) when computing u. Note that an equivalent computation to di is -aV diag(u)V' 8.. which is an a-scaled Newton's method step that is limited to V subspace. The resulting di is a linear combination of V's columns.
Call the base optimizer to compute a descent direction from g2, denoted by db.
Subtract from d, its projection on V's columns, d2 = db - V(V do). The new vector d2 is orthogonal to Vss columns, hence also to di.
5. Update the parameters: 9.,1 6, + di + d2
Parentheses the above steps are important as they allow for only matrix-vector products, reducing computational complexity. Appendix A.2 provides the full pseudocode for FOSI.
Splitting to Two Subspaces. For clarity, define 0, 0, H V diia(A))V" and H2
V diag(X)VV Then at each iteration FOSI implicitly uses the quadratic approximation f wtt g: " H,w of f and performs a step to minimize f as follows. It first divides the vector space that is the eigenvectors of H, into two orthogonal complement subspaces one is spanned by V's columns and the other by V. It then implicitly splits f into two quadratic functions fi and f2 such 3 Hzw. Note that f f f2, since 8, = 81 + 82 and H, = H, + H2. Finally, FOSI minmmizes fi and f2 independently, while using scaled Newton's step to minimize fi and the base optimizer step minimize f2-
that f is their sum: fi 1 f. + w gi+ o Hiw and f2 = + g2 + :/w''
3

---

Published as a conference paper at ICLR 2024
fi *
f2
Figure 1: FOSI's update steps (arrows) when minimizing a quadratic function f(O). FOSI implicitly separates the space into two orthogonal complement subspaces and then splits the original function into two functions fi and f2 over these subspaces, such that f = fi + f2. FOSI solves m by simultaneously solving min with Newton's method and min fo with the base optimizer. The update step is the sum of d1 and d2, the updates to fi and respectively.
We observe that fi has similar slope and curvature as f in the subspace that is spanned by V and zero slope and curvature in its orthogonal complement V, while f2 has similar slope and curvature as f in V and zero slope and curvature in V. To minimize fi, FOSI changes 0 in the direction di that a linear combination of V's columns, and to minimize f2, it changes look at each step of FOSI two
the direction
d2 that is linear combination of V's columns. Hence. simultaneous and orthogonal optimization steps that do not affect the solution quality of each other, and their sum is step in the minimization of f. Figure iillustrates this idea for the quadratic function f(0) 1 1.256 + 1 1.250 + 1,50/02.
Avoiding Matrix Inversion. We stress that unlike most hybrid methods, FOSI does not require inverting H1. Rather, the inverse preconditioner is obtained directly and exactly using the output of ESE: !1! = V diag(u))VV. This helps avoid error amplification due to matrix inversion (Li 2017).
3.3 PRECONDITIONER ANALYSIS
We next analyze FOSI as preconditioner. For simplicity, the subscript omitted from g, and H, when it is clear from the text that the reference is to specific point in time.
For base optimizers that utilize diagonal matrix as a preconditioner (e.g., Adam), the result is an efficient computation, as p-1g g is equivalent to element- wise multiplication of p-l's diagonal with g- When using FOSI with such base optimizer, the diagonal of the inverse preconditioner, denoted by q, is calculated using g2, instead of Hence, d, -17 diag(4)g2, for some learning rate O. optimizer
Lemma 1. Let f(I) be convex twice differential function and let BpseOpt be a that utilizes a positive definite diagonal preconditioner. Let H be f's Hessian at iteration of FOSI with BaseOpt, and let V diag(A)VV be an eigendecomposition of H such that V [V, V] and X [x. Then:
1. FOSI's s inverse preconditioner is P-1 = v( a diag(u)
O VT. where M is the trailing n-k- nM principal submatrix (lower right corner submatrix) of VT diag(g)V, and diag(q) is the inverse preconditioner produced by BaseOpi from g2-
2. The preconditioner P is symmetric and positive definite.
3. is eigenvalue of the effective Hessian p- and V's columns are in the eigenspace of a.
The proof can be found in Appendix A.3 It includes expressing dj and d2 product of certain matrices with g, substituting these expressions into 0, + di dz, and using linear algebra properties to prove that the resulting preconditioner is symmetric positive definite matrix. Finally, we assign p-1 expression to obtain p- Note that symmetric positive definite preconditioner is necessary for ensuring that the search direction always points towards descent direction (Li) 2017).
As expected, we obtained separation of the space into two subspaces. For the subspace that spanned by V. for which FOSI uses scaled Newton's 's method, the condition number is 1. For the complementary subspace, the condition number is determined by BaseOpt's preconditioner. In the general case, it is hard to determine the impact of diagonal preconditioner on the condition number of the problem, although is known be effective for diagonally dominant Hessian (Qu et al. 2020
4

---

Published as a conference paper at ICLR 2024
Appendix(A.3 includes analysis of the special case in which H is diagonal. We show that even in this case, which is ideal for a diagonal preconditioner, FOSI provides benefit, since it solves fi with Newton's 's method and provides the base optimizer with f2, which is defined on a smaller subspace, hence can be viewed as of smaller dimensionality than f-
Levy & Duchi 2019).
For base optimizers with identity preconditioner such as GD, we can perform complete spectral analysis of FOSI's preconditioner and effective Hessian, even for non- diagonal H. This allows us to obtain the effective condition number and the conditions in which it is smaller than the original one. However, since FOSI uses two optimizers on orthogonal subspaces, a more relevant measure for improvement is whether the effective condition number of each subspace is smaller than the original one. We show that the condition number of the subspace that is spanned by V is I and the condition number of V is Ax+1 /e-r/ Both condition numbers, of fi and f2, are smaller than the condition number of the original H. See Appendices f.4 proofs and analysis.
Identity Preconditioner.
3.4 MOMENTUM
Momentum accelerates convergence of first-order optimizers and is adapted by many popular opti- mizers (Qian 1999; Kingma & Ba 2014). When using momentum, the descent direction is com- puted on & instead of g, where ğ linear combination of the current and past gradients. Momen- tum could also be used by FOSI; however, FOSI and the base optimizer must apply the same linear combination on 81 and 82, which entails g gi + g2, maintain the orthogonality of fi and f2- We can use g, g. 82 in the proof of Lemma instead of g. 81, 82 and obtain similar results.
3.5 CONVERGENCE IN THE STOCHASTIC SETTING
We adopt the stochastic setting proposed by Wang et al. 2017). Consider the stochastic optimization problem min, f(0) for f(0) = [, x)], where F K" x Bd - R. is twice differentiable w.r.t and x Bdd denotes a random variable with distribution P. When stochastic optimization is used for DNN training, f is usually approximated by a series of of functions: at each iteration 1, a batch b, containing m; data samples (2. Jm, is sampled and the function f set as f( - Σ", F(O, xx). Note that labels, if any, can be added to the data vectors conform this model. Adapting FOSI to stochastic DNN training requires a small change to FOST's s algorithm. at the beginning of each iteration, the first action would be to sample a batch b, and set f". We can call the ESE procedure with the current f", or with some predefined f², S r, as discussed in $3.7
We now show convergence of FOSI in the common stochastic setting under common Lipschitz smoothness assumptions on and F, and assuming bounded noise level of the stochastic gradient.
Lemma 2. Let BaseOpt be a first-order optimizer that utilizes positive definite diagonal precon- ditioner and denote by F², oF
Ø. the Hessian of F w.r. O. Assuming:
1. f(0) is L-smooth and lower bounded by a real number. 2. For every iteration E,,(VoF(,,,x)) f(,,)) and Eg, o f(0))l a², where o > 0, x, for 1,2, are independent samples, and for a given the random variable x, is independent of (0.1/=11
There exist a positive constant z s.t. for every 0 and x, I[V² x)ll s z and the diagonal entries of BaseOpt's 's preconditioner are upper bounded by z
Then, for a given E E (0, 1), the number of iterations N needed to obtain ΣN ELV e when applying FOSI with BaseOpt is = (111)B)))) for step size n1 chosen proportional r-, where B (0.5,) 1) is constant.
The proof (in Appendix A.5) works by expressing FOST in the stochastic quasi-Newtor method form used in Theorem 2.8 of Wang et al. (2017). and proving the Theorem's conditions are satisfied.
In the convex, non-stochastic scenario, the convergence rate of the base optimizer becomes the limiting factor, as Newton's method demonstrates quadratic convergence rate on fi. Therefore, FOSI's convergence rate mirrors that of the base optimizer for f. but with improved constants due to the smaller condition number of fz. For instance, the convergence analysis of GD yields f(0)) f(0') < |l0g 0'1² (2ar) for a S L/L. In the convex case, L = d₁ (the maximal eigenvalue of the Hessian). Since FOSI-GD reduces the maximal eigenvalue to A 1; its bound is tighter.
5

---

Published as a conference paper at ICLR 2024
3.6 AUTOMATIC LEARNING RATE SCALING
When the base optimizer has a closed-form expression of its optimal learning rate in the quadratic setting that only dependant the extreme eigenvalues, FOSI can adjust tuned learning rate 7 to better suit the condition number of f.. Fortunately, in most cases of optimizers that utilize a diagonal preconditioner, such as GD, Heavy-Ball, and Nesterov, there are such closed-forms (Lessard al.) 2016). Specifically, when applying FOSI with such base optimizer and given the relevant closed- form expression for the optimal learning rate, the adjusted learning rate iteration would be "2 //0///n"), where n¹ is the optimal learning rate for the quadratic approximation f and 172 is the optimal one for f2. FOSI able to compute this scaling, using the ESE outputs.
The intuition behind this scaling is that the ratio between the optimal learning rates is proportional to the ratio between the condition number of and that of f2. The full details regarding this scaling suggest more conservative scaling that involves clipping over this scaling factor as follows: 7/2 = min(m///7 /nj, c) for c 2 1. For 1, 1/2 17, and for extremely large (oo), the scaling factor is not clipped.
technique are in Appendix A.6 Note that n///n' 2 1. In practice,
3.7
ERROR OVERHEAD
ESE Approximation Error. Using Newton's method in non-quadratic settings conjunction with inexact approximation of Hessian cigenvalues through the ESE procedure increases the risk of divergence. FOSI uses several techniques to address this: scaled Newton's 's method, extra numerical accuracy inside the ESE procedure, full orthogonalization, and warmup. The details are available in Appendix A.7 In practice, our experiments on a variety of DNNs in $4 demonstrate that FOSI is robust and substantially improves convergence.
Runtime. FOSI's runtime differs from that of the base optimizer due to additional computations in each update step and calls to the ESE procedure. For large and complex functions, the latency of the update step of both optimizers, the base optimizer and FOSI, negligible when compared the computation of the gradient in each iteration. Furthermore, since each Lanczos iteration is domi- nated by the Hessian-vector product operation which takes approximately two gradient evaluations, the latency of the ESE procedure can be approximated by 2mT, where is gradient computation latency and m the number of Lanczos iterations (see 13.1). The ESE procedure is called every T iterations, and the parameter 7 should be set such that FOSI's runtime is at most p times the base optimizer runtime, for a user-defined overhead > 1. Thus, given the above approximations and assumptions, we can achieve overhead p by setting: T 2m/(p - 1). This heuristic helps avoid the need to tune T, though FOSI can of course use any 7 > O. See Appendix A.8 for additional details as well as a more accurate expression for for functions where additional computations are not negligible in comparison to gradient computations.
Memory. FOSI stores & eigenvectors of size O(n), and temporarily uses (mm)) memory when performing the ESE procedure. comparison, other second order methods such as K-FAC (Martens) & Grosse 2015) and Shampoo (Gupta et al. 2018) incur O(Eie df + př) memory overhead, where d, is the ipptt dimension of layer i, pi the output dimension, and L the total number of layers.
4 EVALUATION
We first evaluate FOSI's performance on benchmarks tasks including real-world DNNs with stan- dard datasets, for both first- and second-order methods. We then validate theoretical results by evaluating FOSI on a positive definite (PD) quadratic function with different base optimizers; we explore the effect of the dimension n, the eigenspectrum, the learning rate, the base optimizer, and the clipping parameter on FOSI's performance. We implemented FOSI in Python using the JAX framework (Bradbury al. 2018 0.3.25. For experiments, we use an NVIDIA A40 GPU.
4.1 DEEP NEURAL NETWORKS
We evaluated FOSI on five DNNs of various sizes using standard datasets, first focusing first-order methods in common use. We execute FOSI with k and O, since small eigenvalues are usually negative. We 0.01, 3, and W such that warmup is epoch. T' is determined

---

Published as a conference paper at ICLR 2024
Table 1: Wall time in seconds to reach target validation accuracy (AC, TL, LR) or loss (LM, AE). The target (in parentheses) is the best one reached by the base op- timizer. No single base optimizer is best for all tasks.
Adam
HB FOSl-Adam
FOSI-HB
train loss
0.03
valid acc.
0.4
0.02
0.2
0.01
Task
HB
FOSI-HB
Adam
FOSI-Adam
5000
5000
AC
3822
1850
(40.4%)
5042
3911
(28.9%)
wall time (sec.)
wall time (sec.)
LM
269
207
(1.71)
270
219
(1.76)
Training AC (MobileNetVI on AudioSet data). FOSI converges faster than HB and similar to Adam across wall time (left). However, Adam overfits and generalizes poorly as indicated by its low validation accuracy (right).
Figure 2:
AE
354
267
(52.46)
375
313
(51.26)
TL
93
53
(79.1%)
68
33
(79.0%)
LR
16
8
(92.8%
12
18
(92.8%)
using the heuristic suggested in $ $3.7 aiming 10% overhead (p = 1.1), resulting in T 800 for all experiments. The base optimizers compared to FOSI are Heavy-Ball (HB) and Adam: we omit GD (SGD) as it performed worse than HB in most cases. We use the standard learning rate for Adam (0.001), and the best learning rate for HB out of 0. 0.01, 0.001, with default momentum parameters Bi 0.9.82 = 0.999 for Adam and B = 0.9 for HB. The five evaluated tasks are:
1. Audio Classification (AC): Training MobileNetV (approximately 4 million parameters) on the AudioSet dataset (Gemmeke et al. 2017). The dataset contains about 20,000 audio files, each 10 seconds long, with 527 classes and multiple labels per file. We converted the audio files into I-second mel-spectrograms and used them as input images for the DNN. The multi-hot label vector of segment is the same as the original audio file's label.
Language Model (LM): Training an RNN-based character-level language model with over million parameters (Hennigan et al. 2020) the Tiny Shakespeare dataset (Karpathy (015). For LM training batches are randomly sampled; there is no defined epoch and we use W = T.
3. Autoencoder (AE): Training an autoencoder model with roughly 0.5 million parameters on the CIFAR-10 dataset. Implementation is based on [iipee] (2022) with latent dimension size 128. We observed that the HB optimizer in this case is sensitive the learning rate and diverges easily. Therefore we run FOSI with
(prevents learning rate scaling) and W T, which enables extra warmup iterations (number of iteration per epoch is 175).
4. Transfer Learning (TL): Transfer learning from ImageNet to CIFAR-10. We start with pre- trained ResNet-18 18 on ImageNer2012 and replace the last two layers with a fully-connected layer followed by Softmmx layer. We train the added fully-connected layer (5130 params), while the other layers are frozen (11 million parameters).
5. Logistic Regression (LR): Training multi-class logistic regression model to predict the 10 classes of the MNIST dataset. The model is a neural network with one fully connected layer of 784 input size followed by a Softmax layer of 10 outputs, containing 7850 parameters. The input data is the flattened MNIST images. Since logistic regression is a convex function, the model is also convex w.r.t. the parameters of the network.
Table T summarize the experimental results, showing the wall time when reaching a target validation accuracy (for AC, TL, LR tasks) or target validation loss (for LM, AE tasks). The target metric (in parentheses) is the best one reached by the base optimizer. FOSI consistently reaches the target metric faster than the base optimizer (though Adam is faster than FOSI-Adam on LR. FOSI-HB is faster than both). The improvement in FOSI-HB is more significant than in FOSI-Adam, due to FOSI-HB's s ability to adapt the learning rate according to the improved condition number of the effective Hessian.
Figure shows the optimizers' learning curves for the AC task. The training loss curves suggests that FOSI significantly improves the performance of HB, but does not help Adam. However, while Adam's 's training loss reaches zero quickly, it suffers from substantial overfitting and generalizes poorly, indicated by its accuracy. This supports the idea that there is single best optimizer for all problems (Zhou et al.) 2020). FOSI aims to improve the best optimizer for each specific task. In this case, HB is preferred over Adam as it generalizes much better, and FOSI improves over HB.
7

---

Published as a conference paper at ICLR 2024
Adam
TOSI-Adam
---
FOS-HBB GD
F05-G0
10'
1-000, by
0-1000 A
n=100, 200
1500, 2,0
mey
10-1
100
200
0
100
200
0
100
200
0
100
200
Iteration
Iteration
iteration
iteration
Learning curves for minimizing PD quadratic functions (n = 0.56 H0 with varying n and d values. FOSI converges more than two orders of magnitude faster than its counterparts.
Figure 3:
important to note that when the base optimizer overfits, FOST's acceleration of convergence also leads to an earlier overfitting point. This can be observed in the validation accuracy curve: HB begins to overfit near epoch 70 while FOSI begins to overfit at roughly epoch 35. Overall, throughout our experiments, have not observed FOSI to overfit more than the base optimizer; FOSI always reaches the same or superior validation accuracy as the base optimizer.
Summary. FOSI improves convergence of the base optimizer, and is the fastest optimizer for all five tasks. On average, FOSI achieves the same loss as its base optimizer in 78% of the time on the training set and the same accuracy/loss in 75% of the time on the validation set. Thus while the average FOSI iteration takes longer than the base optimizer's ss FOSI requires fewer iterations resulting in overall faster convergence. Additional results can be found in Appendix B.I
4.2 COMPARISON TO SECOND-ORDER METHODS
We compare FOSI to two representative second-order techniques, K-FAC (Martens Grosse 2015) and L-BFGS (Liu & Nocedal 1989); these use a block-diagonal approximation of the Hessian as a preconditioner, subsequently perform inversion. We repeat the five DNN training experiments and compare the results of both algorithms to FOSI-HB. We use the KFAC-JAX (Botev & Martens, 2022] implementation for K-FAC and the JAXOpt library (Blondel al.
202T for L.BBGSS.
We used grid search to tune K-FAC's learning rate and momentum, and included K-FAC's adaptive as one of the options. We utilized adaptive damping and maintained the default and more precise T3 (interval between two computations of the approximate Fisher inverse matrix) value of 5 after testing larger T3 values and observing no variation in runtime. For tuning L-BFGS hyperparameters, we used line-search for the learning rate, and performed search for the optimal L (history size) for each task, starting from L. 10 (similar to we used for FOSI) and up to = 100. The hyperparameters selected based the lowest validation loss obtained for each experiment.
Overall, we observed that both K-FAC and L-BFGS algorithms have slower runtimes and poorer performance compared to FOSI. They occasionally diverge, can overfit, and rarely achieve the same level of validation accuracy as FOSI. See Appendix B. for figures and additional results.
4.3 QUADRATIC FUNCTIONS
controlled exper- iments on PD quadratic functions of the form fu((0) 0.50 He. We use GD, HB, and Adam to minimize fH. well as FOSI with these base optimizers. We use the default momentum parameters B = 0.9, = 0.999 for Adam and B 0.9 for HB. The learning rate for Adam was set to 0.05 after tuning, for GD to the optimal value 2/(4, + An), and for HB we used 2/( Vdz + VA,)² which is half of the optimal value (due to using constant / rather than optimal). FOSI runs with k = 10,
To evaluate FOSI's optimization performance across range of parameters,
0, a = 1, and c = vo (no clipping on the scaling of the GD and HB learning rates, see {366).
Dimensionality and Eigenspectrum. To study the effect of dimensionality and eigenspectrum on FOSI, we created five fu functions for each (100, 1500) by varying di of the Hessian H with d E (5, 10, 20, 50, 200). The other eigenvalues were set to 2; = 1.5-((-2) and the eigenvectors were extracted from symmetric matrix whose entries
randomly sampled from U(0, 1).
Figure 3 shows learning curves of the optimizers on functions with d = 5 and 4 = 200. Similar results were obtained for other functions. FOSI converges at least two orders of magnitude faster
8

---

Published as a conference paper at ICLR 2024
than its counterparts. In this case, dimensionality has little impact the performance of different optimizers. For a specific n value, increasing d₁ causes the base optimizers to converge to less optimal solutions, but has little impact on FOSI. This is expected for GD and HB, whose learning rate limited by the inverse of the largest eigenvalue, hence, larger at implies slower convergence. FOSI reduces the largest eigenvalue, allowing for larger learning rate that is identical for all functions. Interestingly, this is observed for Adam as well.
Ill-conditioning and diagonally dominance. We explore the effect of both the condition number and the diagonally dominance of the function's Hessian on the different optimizers. We use a set of quadratic functions with different condition number and different rotation w.r.t. the coordinate system, which impacts the dominance of the Hessian's 's diagonal. While all optimizers are negatively affected by large condition number, only Adam is affected by the rotation. FOSI improves over the base optimizer in all cases. The full details and analysis of the results are in Appendix B.2.1
Learning rate and momentum. We explored the effect of various learning rates and momentum parameters on the optimizers. We find that FOSI improves over Adam, HB, and GD for all learning rates and momentum (for HB and Adam). The full details of this experiment are in Appendix B.2.2
5
RELATED WORK
Partially second-orden optimizers are a group of optimization methods that incorporate some aspects of second-order information in their optimization process. Optimizers that use diagonal precon- ditioner (Yao et al.] [021 Jahani et al. 2022 Henriques et al. 2019 Liu et al. 2023). and in fact approximate the Hessian diagonal, suffer when the assumption for diagonally dominance Hessian does not hold (see $ L-BFGS (Liu & Nocedal 1989), which uses low-rank approximation of the Hessian, sensitive to the rank parameter and an incorrect selection can lead slow convergence or divergence. Additionally, it requires line search in each iteration, slowing down the optimization process further. Recent approaches. such as K-FAC (Martens & Grosse (015)) Shampoo (Gupta et al., 2018). K-BFGS (Goldfarb et al., 2020), LocoProp (Amid et al. 2022). Eva (Zhang et al., 2023). and Yang et al. (2023) exploit the structure of the network to approximate block diagonal preconditioner matrix, as an alternative to full second-order methods. However, these techniques approximate the preconditioner directly instead of approximating its inverse, potentially resulting in higher approximation errors and noise sensitivity (Li 2017). They also exhibit comparable limita- tions to those of diagonal preconditioners due to neglecting Hessian elements outside the diagonal blocks, such as inter-layer parameter correlations or rotated problems ($4.3). In contrast, by split- ting the problem into two subspaces FOSI obtains a full low-rank representation of the Hessian for the first subspace V. which captures both the rotation and curvature of the sub-problem fi. This contributes to accuracy and stability of the optimization, particularly as it based on extreme eigen- values and vectors that can be approximated more accurately.
Other optimization approaches for stochastic settings involve the use of sub-sampling of f functions and constructing an approximation of the Hessian based on the gradients of these functions at each iteration Ghoosta-Khorasann
& Mahoney 2019 Xu et al. 2016). However, these methods are lim- ited to functions with only a few thousand parameters. Hessian-free optimization methods (Martens) jet al. 2010 Martens& & Sutskever, 2011; Frantar et al., 202I) rely on conjugate gradient to incor- porate second order information, which while more efficient than Lanczos in terms of memory, it still often requires many steps to converge and is more sensitive to noise. Finally, while these works propose single improved optimizer. FOSI is meta-optimizer.
6 DISCUSSION AND FUTURE WORK
FOSI is a hybrid meta-optimizer that combines a first-order base optimizer with Newton's method to improve the optimization process without additional tuning. Evaluation on real and synthetic tasks demonstrates FOSI improves the wall time to convergence when compared to the base optimizer. Future research will focus on methods for automatic tuning of different parameters of FOSI, such as dynamically adjusting parameters k and l according their impact the effective condition number. We also plan to investigate the effect of stale spectrum estimation, which could allow running the ESE procedure on the CPU in parallel to the training process the GPU.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
The authors thank the anonymous reviewers for their valuable feedback. The research leading to these results was supported by the Israel Science Foundation (grant No. No.191/18), the Technion Hi- roshi Fujiwara Cyber Security Research Center, the Israel National Cyber Directorate, and the HPI- Technion Research School.
REFERENCES
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.
Mathieu Blondel, Quentin Berthet, Marco Cuturi, Roy Frostig, Stephan Hoyer, Felipe Llinares- López, Fabian Pedregosa, and lean-Philippe Vert. Efficient and modular implicit differentiation. arXiv preprint 1111:22005.1183, 2021.
Aleksandar Botev and James Martens. KFAC-JAX, 2022. URL.bttp://iittbb.cmom//e
kfac-jax
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne, and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL http:
//github. com wwt google/jax
Jos Dorsselaer, Michiel Hochstenbach, and Henk Van der Vorst. Computing probabilistic bounds for extreme eigenvalues of symmetric matrices with the lanczos method. SIAM Journal on Matrix Analysis and Applications, 22, 01 2001. doi: 10.113750995-798036635
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. J. Mach. Learn. Res., 121mu1):2121-2155, jul 2011. ISSN 1532-4435.
Elias Frantar, Eldar Kurtie, and Dan Alistarh. M-fac: Efficient matrix-free approximations of second-order information. Advances in Neural Information Processing Systems, 34:14873- 14886, 2021.
Jean Gallier et al. The Schur complement and symmetric positive semidefinite (and definite) matri- ces (2019). URL https://www. cis. upenn. eduijean/schur-comp. pdf. 2020.
Jort F. Gemmeke, Daniel P. W. Ellis, Dylan Freedman, Aren Jansen, Wade Lawrence, R. Channing Moore, Manoj Plakal, and Marvin Ritter. Audio set: An ontology and human-labeled dataset for audio events. In Proc. IEEE ICASSP 2017, New Orleans, LA, 2017.
James Gentle. Matrix Algebra: Theory, Computations and Applications in Statistics. Springer, 01 2017. ISBN 778-3-319-648666 doi: 1L10077978-33319-44665
Donald Goldfarb, Yi Ren, and Achraf Bahamou. Practical quasi-newton methods for training deep neural networks. In Proceedings of the 34th International Conference on Neural Infor- mation Processing Systems, NIPS'20 20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546.
Vineet Gupta, Tomer Koren, and Yoram Singer. Shampoo: Preconditioned stochastic tensor op- timization. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1850- PMLR, 10-15 Jul 2018. URL
@uptal8a.html
Tom Hennigan, Trevor Cai, Tamara Norman, and Igor Babuschkin. Haiku: Sonnet for JAX, 2020. URL http://gi thub. wwt. wwwom//deeiid/////e daaku
João F Henriques, Sebastien Ehrhardt, Samuel Albanie, and Andrea Vedaldi. Small steps and giant leaps: Minimal Newton solvers for deep learning. In Proceedings of the IEEEJCVF International 2019.
Conference Computer Vision, pp.
10

---

Published as a conference paper at ICLR 2024
Majid Jahani, Sergey Rusakov, Zheng Shi, Peter Richtárik, Michael W. Mahoney, and Martin Takác. Doubly adaptive scaled algorithm for machine learning using second-ords order information. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25- 29, 2022. OpenReview.net, 2022, URL htw.l//wws./ppppeeeeeeeee//////s
Andrej Karpathy. char-rnn, 2015. URL
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations, 12 2014.
Coreeluss Lanczos. An iteration method for the solution of the eigenvalue problem of linear dif- ferential and integral operators. Journal of research of the National Bureau of Standards, 45: 255-282, 1950.
Laurent Lessard, Benjamin Recht, and Andrew Packard. Analysis and design of optimization algo- rithms via integral quadratic constraints. SIAM Journal on Optimization, 26(1):57-9)) 2016. doi: 10.1 10.1137/15M1009599. URL httpp::ss//do..oo org/ 10. 1137 1137/15M1009997
Daniel Levy and John C Duchi. Necessary and sufficient geometries for gradient methods. Advances in Neural Information Processing Systems, 32, 2019.
Xi-Lin Li. Preconditioned stochastic gradient descent. IEEE transactions on neural networks and learning systems, 29(5):1454-1466, 2017.
Phillip Lippe. UvA Deep Learning Tutorials. http:://waalccnnnebooosssraaaaad en/ aa/llatst// 2022.
Dong C Liu and Jorge Nocedal. On the limited memory BFGS method for large scale optimization. Mathematical programming, 45(1):503-555 1989.
Hong Liu, Zhiyuan Li, David Hall, Percy Liang and Tengyu Ma. Sophia: A scalable stochastic second-order optimizer for language model pre-training. arXiv preprint arXiv:2305. /4342, 2023.
James Martens and Roger Grosse. Optimizing neural networks with Kronecker-factored approxi- mate curvature. In Proceedings of the 32nd International Conference International Conference on Machine Learning Volume 37, ICML' 15, pp. 2408-2417. JMLR.org, 2015.
James Martens and Ilya Sutskever. Learning recurrent neural networks with hessian-free optimiza- tion. In Proceedings of the 28th international conference machine learning (ICML-I1), pp- 1033-1040, 2011.
James Martens, Jimmy Ba, and Matt Johnson. Kronecker-factorred curvature approximations for recurrent neural networks. In International Conference on Learning Representations, 2018.
James Martens et al. Deep learning via hessian-free optimization. In ICML,, volume 27, pp. 735-742, 2010.
Gérard Meurant and Zdenčk Strakoš. The Lanezos and conjugate gradient algorithms finite pre- cision arithmetic. Acta Numerica, 15:471-542, 2006.
Yurii Nesterov. Introductory lectures convex optimization; A hasic course, volume 87. Springer Science & Business Media, 2003.
Jorge Nocedal and Stephen J Wright. Numerical optimization. Springer, 1999.
Antonio Orvieto, Jonas Kohler, Dario Pavllo, Thomas Hofmann, and Aurelien Lucchi. Vanish- ing curvature in randomly initialized deep ReLU networks. In Gustau Camps- Valls. Francisco J. R. Ruiz, and Isabel Valera (eds.). Proceedings of The 25th International Conference on Ar- rificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pp. 7942-7975. PMLR, 28-30 Mar 2022. URL https://proceeddiii mlr press//1511 orvieto22a. html
Barak A. Pearlmutter. Fast exact multiplication by the Hessian. Neural Computation, 611):147-160, (eteec....9946.66 1994. doi: 10.1 162/neco. 1994.6.1.1. 1994.6.1.147.
11

---

Published as a conference paper at ICLR 2024
Boris T Polyak. Introduction to optimization. optimization software. Inc., Publications Division, New York, 1:32, 1987.
Ning Qian. On the momentum term in gradient descent learning algorithms. Neural networks, 12 (1):145-151, 1999.
Zhaonan Qu, Yinyu Yc, and Zhengyuan Zhou. Diagonal preconditioning: Theory and algorithms. arXiv preprint WxXv:20033005545 2020.
Farbod Roosta-Khorasani and Michael W. Mahoney. Sub-sampled newton methods. Math. Pro-
gram. 174(1-2):293-322 326, mar 2019. ISSN 0025-5610. doi: 10.1007/410107-018-14464 URL
https://doi. org/ 1007/10010701008 1346-5)
Hadar Sivan, Moshe Gabel, and Assaf Schuster. AutoMon: Automatic distributed monitoring for
arbitrary multivariate functions. In Proceedings of the 2022 International Conference Man- agement of Data, SIGMOD '22, pp. 310-324, Association for Computing Machinery, 2022. URL httpt:://oi..oorg///// 1145/
ISBN 978 97844903. 3514221. 3517866
doi: 10. (0.1145/3514221..1
Hong Hui Tan and King Hann Lim. Review of second-order optimization techniques in artificial neural networks backpropagation. JOP Conference Series: Materials Science and Engineering, 495:012003, jun 2019. doi: 10. 1088//1557-899x495////
URL https://doi. http:://dooooogg/1//
1008/775-899x/445////0
Tijmen Tieleman, Geoffrey Hinton, et al. Lecture 6.5-rmsprop: Divide the gradient by running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26-31,
2012.
John C. Urschel. Uniform error estimates for the Lanczos method. SIAM Journal on Matrix Analysis and Applications, 4223):1423-1450, 2021. doi: 10.1137/20M1331440, URL https://doi. org/
2gg/10..o 10. 1137/20M13314770
Xiao Wang, Shiqian Ma. Donald Goldfarb, and Wei Liu. Stochastic quasi-newton methods for nonconvex stochastic optimization. SIAM Journal on Optimization, 27(2):927-956, 2017. doi: 10. 10.1137711MM0053141. URL http::tp:://doo org/ 10. 1137/15M1053141
Ashia C Wilson, Rebecca Roelofs, Mitchell Stern, Nati Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. Advances in neural information process- ing systems, 30, 2017.
Peng Xu, Jiyan Yang, Farbod Goosta-Khorasann Christopher Ré, and Michael W. Mahoney. Sub- sampled newton methods with non-uniform sampling. In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS' 16, pp. 3008-3016, Red Hook, NY, USA, 2016. Curran Associates Inc. ISBN 9781510838819.
M. Yang, D. Xu, Q Cui, Z. Wen, and P. Xu. An efficient fisher matrix approximation method for large-scale neural network optimization. IEEE Transactions on Puttern Analysis and Machine In- telligence, 45(05))5391-54033 may 2023. ISSN 1939-3539. doi: N..1109/PPAMI220 222MM.2222232136544
Zhewei Yao, Amir Gholami, Sheng Shen, Mustafa Mustafa, Kurt Keutzer, and Michael Mahoney. Adahessian: An adaptive second order optimizer for machine learning. In proceedings of the AAAI conference artificial intelligence, volume 35, pp. (0665-10673,
Lin Zhang, Shaohuai Shi, and Bo Li. Eva: Practical second-order optimization with kronecker- vectorized approximation. In The Eleventh International Conference on Learning Represen- tations. ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. URL https:
//openreview www.:nee//peee met/pdfffd=_Miiietteee Mic8VV6Voy
Pan Zhou, Jiashi Feng, Chao Ma. Caiming Xiong, Steven Chu Hong Hoi, et al. Towards theoretically understanding why SGD generalizes better than Adam in deep learning. Advances in Neural Information Processing Systems, 33:21285-21296. 2020.
Milija Zupanski. A preconditioning algorithm for large-scale minimization problems. Tellus A, 45: 478 492, 11 2002. doi: 10. 1103///16000--//// 1991.0001111111
12

---

Published as a conference paper at ICLR 2024
APPENDIX
A FIRST AND SECOND-ORDER INTEGRATION
A.1 THE ESE ALGORITHM
This section describes the ESE algorithm for obtaining the k largest and & smallest eigenvalues, as well as their corresponding eigenvectors, of the Hessian H, The full details of the algorithm are in $ $..
ESE first sets the number of Lanezos iterations, m, defines the hvp, operator, and then calls the Lanczos algorithm. After running Lanczos for m iterations, its output is a matrix U R with orthonormal columns and a tridiagonal real symmetric matrix
Ruxx
To extract the approximate eigenvalues and eigenvectors of A, let QA be the eigendecomposition of T. s.t. A is diagonal matrix whose diagonal is the cigenvalues T sorted from largest to smallest and Q's columns their corresponding eigenvectors. The approximate & largest and & smallest eigenvalues of are the first & and last & elements A's diagonal, and their approximate corresponding eigenvectors the first and last columns of the matrix product UQ
Algorithm
T details the ESE procedure.
Algorithm Extreme Spectrum Estimation.
procedure ESE(f, 0,, k, ()
- length of
max|4(k (), l)
hvp, < generate hvp operator from f and 0,
U, T < Lanczos(m, hvp,)
Q, A + cigendecomposstion((()
X < first k and last é entries of A's diagonal
V first k and last & columns of UQ
return X. V
A.2
THE FOSI ALGORITHM
Algorithm provides the pseudocode for FOSI, The details of the algorithm are in $ 3.2
A.3
PRECONDITIONER ANALYSIS
We start by proving Lemma from 3.3 and continue by analysing special case in which the cigenvectors of H are aligned to the axes of the Euclidean space.
apply FOSI on optimizer that uses an inverse diagonal preconditioner s.t. d, = - () then:
Proof. In
di = -a a==vv((VV 81
o = -a VV V 8) Ou = V V g,
d2 = d - V 4,) = (1 vV ) db -n(1 VV diag(g)82
= - () v [VT 3)) - VV diag(g) (I-V"))
By assigning these forms of d, and d2 in the update step 0,, 0, dj dz, we obtain that the update step of the form 0,1 0, - p-1g and the inverse preconditioner is:
p-1 V diag(u) n VV") diag(a) VVT).
Note that
V V diag((u, Ox-x-rl)V²
(2)
13

---

Published as a conference paper at ICLR 2024
Algorithm 2 FOSI Optimizer.
initialization:
1: BaseOptStep: given gradient, return descent direction.
2: T: number of iterations between two ESE runs.
3: W: number of warmup iterations before calling ESE.
4: k, C: parameters for ESE, 1 k + E <
5: a: positive learning rate (scalar).
6: u - 0, O.
procedure UPDATESTEP(A. 8, V.
7: 81 V VVV'V. g).
V V'
82
8: di -aV (
81 ou))
9: d, BaseOptStep(g.)
10: d2 - ds ((V (V'd))
11: - ++ di + d2
12: return 0
procedure OPTIMIZe[S, 6p)
13: /-
14: while 8, not converged do
g:
f(6,)
16:
if >= W and (t- W) mod T = 0 then
17:
X, V - ESE(S.,.k
18:
//|
0.11 UpdateStep(Or, 8t, V.
20:
1-/+)
Similarly, and using the fact that V is an orthonormal matrix (V is an orthogonal basis) and hence VV"
1 VV = VIV" V diag(( Op- Ox- V ((1-diag diag([1e+e Or- VT
V diag(10 l=-V"
(3)
By assigning equation and equation 3 in equation | obtain:
p =aV diag([u, 0,-x-z))V" V diag(10 1==x+ Viag(q) diag([O.-6, In-v-
=V[ diag([u, 0,- + 17 diag((0e.. 1-vV diag(q)V diag([O l---<()) JV².
This completes the proof of claim of the Lemma.
Note that multiplying a diagonal matrix from left another matrix equivalent to scaling each of the later by the corresponding diagonal entry of the former, and similarly multiplying diagonal matrix from from the right has the same effect on columns. Therefore, the matrix
B = diag([O -==++ v diag((O 1.-
(4)
a matrix whose first + rows and first k columns are 0.
Denote by M the sub matrix of B that contains the entries i, i.jsst. s.t. i, > k + +. Sine BaseOpt utilizes positive definite (PD) preconditioner
stated in the Lemma T i.e. diag(q) > hence v V > O, and since M is trailing principal submatrix of V diag(q)V it is PD (Gentle) 2017 p. 349).
also symmetric, since symmetric. The diagonal matrix diag(u) is also symmetric and PD. Since a block diagonal matrix is PD if each diagonal block is PD (Gallier et al. 2020) and symmetric each block is symmetric, the block diagonal matrix
diag(u)
0
diag([u, 0,-2-r) nB
(5)
n.
PD and symmetric.
Since V has full column and row rank, and the block diagonal matrix equation i PD, the inverse preconditioner
p-1 v(
diag(u)
nM vr
14

---

Published as a conference paper at ICLR 2024
PD (Gentle 2017 p. 113). It is also symmetric, equation is symmetric.
Finally, using the fact that the inverse of a PD and symmetric matrix PD and symmetric, we conclude that the preconditioner P is symmetric and PD. This completes the proof of claim 2 of the Lemma.
We assign the above p_1 in p- H to obtain the effective Hessian:
p P- =V diag(u)
0
vt diag(IA, diag((X.XD)* ADD
nM
a diag(u) diag A)
nM diag(A) )rr
=v
=v( a diagg(1++))
M diag(X)
We obtained partial eigendecomposition of the effective Hessian, which indicates that there are at least k + & repetitions the eigenvalues with value a and its corresponding eigenvectors are V's eigenvectors. This completes the proof of claim of the Lemma.
In the special case in which the eigenvectors of H are aligned to the axes of the Euclidean space R" (i.e. diagonal), a permutation matrix (has exactly one entry of in each row and each column and Os elsewhere). Note that diag(q)/ is an eigendecomposition of diag(q). Let P be the permutation of columns, such that P()) = Then V diag(P(q)) also an eigendecomposition of diag(q), i.e:
diag q V diag(P(qg))*
Therefore,
v V = v diag((()))' diag((()))
and M is the n- k trailing principal submatrix of diag(P(q)). In other words, the diagonal of entries of the vector P(g). By Lemma a is an eigenvalue of p
M contains the last n with k repetitions. From the analysis of M we obtain that the remaining - k - l eigenvalues q is good approximation the Hessian diagonal,
of P H are: 1/P( Pf) then these eigenvalues should be all close since each P(g): is an approximation to the inverse of d/---
This is an optimal case, since the two optimization problems defined on the two subspaces have condition number of 1, which enable fast convergence. However, this a very special case and the Hessian in most optimization problems is not diagonal. Moreover, even in this case, which is ideal for a diagonal preconditioner, FOSI provides benefit, since solves fi with Newton's method, which obtains an ideal effective condition number over V, and provides the base optimizer with f2, which is defined smaller subspace V. hence be viewed of smaller dimensionality than f.
A.4 IDENTITY PRECONDITIONER
Here we formalize the claims in
Lemma 3. Under the same assumption as in Lemma 7 with BaseOpt that utilizes a scaled identity inverse preconditioner ni for some learning rate 11 > 0:
1. FOSI's s resulting inverse preconditioner is p-1 = V diag([ou, 171,,111)=+ The preconditioner P is symmetric and PD. is an eigenvalue of the effective Hessian P- H. and V's columns are in the eigenspace of a. In addition, the entries of the vector π are eigenvalues of p-1 H and their corresponding eigenvectors V's columns.
Proof. The proof immediately follows from Lemma by replacing diag(q) with I. By replacing diag(q) with in equation 4 we obtain
B diag(1Oett, 1== IV diag([O (n-)-() diag([O=-6 (n-e-())
15

---

Published as a conference paper at ICLR 2024
Hence, M diag(In---)) Assigning this M in p-1 given by Lemma obtains:
p p=== diag(u)
diag(In---o) v
V
which completes the proof of claim of the Lemma.
p-! is diagonal matrix with positive diagonal entries, and therefore symmetric and PD. Its inverse, P. is also symmetric and PD, which completes the proof of claim 2 of the Lemma.
We assign the above p-1 in p-111 to obtain the effective Hessian:
p = V diag([ou,, - V diag((X, XDv"" = V diag([a "AD)).
We obtained eigendecomposition of the effective Hessian, which implies there are k+ repetitions of the eigenvalues with value a and their corresponding eigenvectors are V's columns, and the entries of y are eigenvalues and their corresponding eigenvectors are V's columns. This completes the proof of claim of the Lemma.
The following Lemma states the conditions in which the effective condition number is smaller than the original condition number when applying FOSI with a base optimizer that utilizes an identity preconditioner.
Lemma 4. Under the same assumption as in Lemma 3 duced by BaseOpt by x and the effective condition number induced by FOSI using BaseOpt by k. Then, R S in the following cases:
denote the effective condition number in-
1. a < qdn-t and Bdass s
A
T
2. ndn-t S &ndi
3. max+1 < a and ahh S To
Proof. The identity preconditioner does not affect the condition number, so we have K = // As stated in claim 2 of Lemma 3 when using FOSI the distinct eigenvalues of the effective Hessian md4+1.... ... Ma--. There are now three distinct ranges for which affect K:
1.
q.---. In this case, the smallest eigenvalue of p-1 is and the largest is nd4++1, which leads n/dei//a; therefore, R
2,
2. ndn-t S a S 11 In this case, the smallest eigenvalue of p-1 is n- and the largest is Md4+1 therefore, R Aet and & S
< dt Sine deal Aunt #h is true then ă
het
3. ndx+1 a. In this case the smallest eigenvalue of p-1 is ndn-t and the largest is a; therefore, ă Neat and S
Iphatt
While provides the conditions in which FOSI improves the condition number, as discussed in $ 3.3) FOSI is able to accelerate the convergence of the optimization process even when it does not improve the condition number.
To show this phenomenon, we use GD and FOSI with GD as base optimizer to optimize the quadratic function f(() = 0.50 HO,0 R 100 We draw random orthonormal basis for f's Hes- sian, H, and set its eigenvalues as follows: A..... d1o are equally spaced in the range [9, 10] and A are equally spaced in the range [0.01, 0. We used the learning rate 17 = 0.001 and run FOSI with k 9, = 0, 1. For this setting we have \; = 10, = 9,0o 0.01 and none of the conditions in Lemma 4 is satisfied. Since 77410 < 1, the only candidate condition this case FOSI's effective condition number is 1/(44400) 100000, which is much larger than the original condition number of the problem, which is d = 1000. However, shown in Figure FOSI converges much faster then GD.
Lemma
is condition (3). however,
16

---

Published as a conference paper at ICLR 2024
15
GD
FOSI-GD
(t
10
5
0
100
200
iteration
Figure 4: Learning curves of GD and FOSI for the minimization of the quadratic function f(0) 0.50' H0, with A E R0000 H's cigenvectors are random orthogonal basis, 0.001, 10, 210 9, = 0.01, and FOSI runs with k = 9, l = 0, = 1. While FOSI's effective condition number is larger than the original one, it converges much faster than the base optimizer.
This example emphasises our claim that the condition numbers to look at are those of and V, which are smaller than the original one, and not the condition number of the entire Hessian.
A.5 CONVERGENCE GUARANTEES IN THE STOCHASTIC SETTING
Our proof of Lemma 2 relies applying Theorem 2.8 from Wang al. 2017) to FOSI. For clarity, we restate their theorem with our notations:
Theorem (Theorem 2.8, Wang et al. (2017). Suppose that the following assumptions hold for (6,)
generated by stochastic quasi-Newton (SQN) method with batch size m, for all t:
(i) f is continuously differentiable, (() lower bounded by a real number flow for any 0 and V f is globally Lipschitz continuous with Lipschitz constant L. (ii) For every iteration r, (V,,,V = Vf(0,) and E,, gF(,, x,) Vf(()]I S o², where o 0, X₁ for 1,2,.. independent samples, and for given the random variable X, is independent of (0:)
(iii) There exist two positive constants, 3, such that z! S P. 3 3l all t.
(iv) For any 2 2, the random variable p.1 depends only on by, by, b.. (the random batch sampling in the previous iterations).
also assume that ii is chosen as ii r with constant E (0.5, 1). Then, for a given E (0, 1),
the namber of iterations N needed to obtain 2 ΣN B[IVS(O) is N 0
We now prove Lemma 2
Proof. First, we need to bring FOSI's inverse preconditioner p-1 to the standard SQN form stated in Wang et al. (2017), and then prove that all the assumption of Theorem 2.8 satisfied.
To bring FOSI's p-1 from Lemma 2 to the standard SQN form, with update step 0,+1 0, - P.P.P. 81.
let 17 -mp- After extracting -)),, p-1 is then given by
p- p'=v
diag(u)
0
V".
M
where M is the trailing - k principal submatrix of VT' diag(g)V.
Theorem 2.8 comprised of four assumptions, where its first two assumption, (i) and iii
are
satisfied by the first two assumptions in Lemma Assumption (iv) requires that for each iteration FOST's inverse preconditioner p-1 depends only on b,, bz..... b, This could be easily satisfied by ensuring that the ESE procedure is called with f for i < and that BaseOptStep is called after the gradient step (switching the 4th and 5th steps the UpdateStep() procedure), while using d, from the last iteration in the update step. This has no impact on our analysis of FOSI in 3.3
To establish assumption (iii) we examine p-1 structure. Given that the Hessian is symmetric PSD, it follows that for every and the norm of the Hessian F²F x) is equivalent to its largest absolute eigenvalue. Therefore, from assumption 3 that [ xx] s z, we have that the largest
absolute eigenvalue is bounded above by Since (0) Σm F(0, x;), then the largest absolute
17

---

Published as a conference paper at ICLR 2024
eigenvalue of 2 f(0)) is also bounded by 2. In addition, it should be noted that the ESE procedure provides eigenvalue estimates that are within bounds the true extreme eigenvalues of the Hessian of f' DDossellerr et al. 2001). Thus, it follows that each entry of [X] is bounded above by which in turn implies that each entry of is bounded below by 1/2. Moreover, the entries of are also bounded above by I/E for < E (E is added to entries of [ that are smaller than e).
Given that BascOpt utilizes PD preconditioner (assumption 3). the entries of q upper bounded by some positive constant 1/c (assuming w.l.o.g that this is the same constant that upper bounds u). Moreover, given that the eigenvalues of BaseOpt's preconditioner are bounded from above by z, the values of q are lower bounded by 1/z. Since the matrix M is trailing principal submatrix of V V, its eigenvalues theorem), which are simply the entries of q.
bounded by the eigenvalues of ya diag(q)V (eigenvalue interlacing
Finally, since V is a rotation matrix, multiplication from the left by V and from the right by V has no impact on the eigenvalues, which implies that 's eigenvalues are the entries of u and the cigenvalues of M. Hence, for every iteration p-''s eigenvalues are lower bounded by _ 1/z and upper bounded by 2= 1/c.
After establishing assumptions et al. (017))
(IV) we complete the proof by applying Theorem 2.8 from Wang
A.6
AUTOMATIC LEARNING RATE SCALING
This section provides details regarding the automatic learning rate scaling technique, presented in $3.6
Let the base optimizer, BaseOpt, be optimizer with closed-form expression of its optimal learn- ing rate in the quadratic setting, be a tuned learning rate for BaseOpt over f. and 17" be the optimal learning rate of BaseOpt over quadratic approximation f of iteration 1. In general, known since first-order optimizers do not evaluate the extreme eigenvalues. Implicitly, is a scaled version of 17". i... 17 s7j" for some unknown positive scaling factor s, usually < 1.
is
FOSI creates a quadratic subproblem, f2, with a lower condition number compared to f and solves it using BaseOpt. Therefore, we propose using 7/2 S77 scaled version of the optimal learning rate of fz with the same scaling factor of instead of simply using 1j. the ESE procedure provides d1, des de, An-r+1, which allows FOSI to automatically adjust 17 to 172, given the relevant closed-form expression for the optimal learning rate. Specifically, 172 mn(n///")) /,) with 1/" obtainable from A₁ and An, and an approximate value for 175 obtainable from d₂ and An f+
A.7 ESE APPROXIMATION ERROR
Using Newton's method in non-quadratic settings within a subspace obtained from the ESE proce- dure increases the likelihood of divergence due inaccuracies in the direction of the steps taken. These inaccuracies stem from the imprecise approximation of Hessian eigenvalues and eigenvectors through the ESE procedure.
To mitigate this, we employ a scaled Newton's method, with a learning rate of 0 < a S 1, for function fi. an alternative to the traditional Newton's method which enforces a 1.
We also avoid issues of numerical accuracy in the ESE procedure by performing full orthogonaliza- tion w.r.t all previous vectors in each Lanczos iteration (Meurant & Strakoš 2006). Moreover, we use float64 for the ESE procedure computations (only); we retain the original precision for training, storing parameters, and other computations.
To mitigate Lanczos divergence caused by a plateau-like initial point OOrvieto et al. 2022 we use warmup iterations before the first ESE call.
Finally, using ESE in a stochastic setting could theoretically result in unsuitable V and À when called with f which misrepresent Techniques to address this include using larger batch size only for the ESE procedure, or averaging the results obtained from different f's. We leave the investigation of such techniques future work.
18

---

Published as a conference paper at ICLR 2024
In practice, our experiments variety of DNNs in $4 using arbitrary f on ESE calls, demon- strate that FOSI is robust and substantially improves convergence.
A.8 RUNTIME ANALYSIS
FOSI's runtime differs from that of the base optimizer due to additional computations in each update step and its calls to the ESE procedure.
Let Ti be the average latency per iteration of the base optimizers, T2 be the average latency per iter- ation of FOSI that does not include a call to the ESE procedure (as if 7 oo), and r3 be the average latency of the ESE procedure, Given that the base optimizer and FOSI are run for T iterations, the latency of the base optimizer is TT, and that of FOSI is T'2 + T3. the ESE procedure is called once every T iterations. The parameter 7 impacts FOSI's runtime relative to the base optimizer. A small 7' may result in faster convergence in terms of iterations, since V and X are more accurate; however, it also implies longer runtime On the other hand, using a large may result divergence due to inaccurate estimates of V and X. Since the improvement in convergence rate, for any given T, not known in advance, the parameter T should be set such that FOSI's runtime it at most p times the base optimizer runtime, for a user define 1. To ensure that, we require pi'Ti = TT2 + T3. which implies"
T T3/ TpT T2).
(6)
The average latency of FOSI's extra computations in an update step (lines 7, 8, and 10 in Algo- rithm [ denoted by T2- TI, includes three matrix-vector products and some vector additions, which have computational complexity of O(n(k + O). For large and complex functions, the latency of these extra computations is negligible when compared to the computation of the gradient (line 18 in Algorithm
2 thus leading to the approximation of a T2. Furthermore, T3 can be approximated by 2MT,, where n = m + E). In is the number of Lanczos iterations, since each Lanc- zos iteration is dominated by the Hessian-
product operation which takes approximately two gradient evaluations (see $ J.1.. By incorporating these approximations into equation (6). we can derive a formula for T which does not require any measurements:
T 2m/(p 1).
Note that this formula is not accurate for small simple functions, where the gradient be computed quickly, and the additional computations are not negligible in comparison. In such cases, TI, T2, and тa can be evaluated by running small number of iterations, and T can be computed using equation (6) based on these evaluations.
B EVALUATION
B.1 DEEP NEURAL NETWORKS
Figure shows the learning curves of FOSI and the base optimizers for different DNN training
tasks: (1) training logistic regression model the MNIST dataset, (2) training autoencoder on the
CIFAR-10 10 dataset, (3) transfer learning task in which we train the last layer of trained ResNet-18 on
the CIFAR-I0 dataset, and (4) training character-level language model with a recurrent network on the Tiny Shakespeare dataset. FOSI improves over the base optimizers in most cases. While FOSI improvement over Adam is less significant than its improvements over Heavy-Ball there are tasks for which Heavy-Ball -Bal performs better than Adam since it generalizes better.
We do note, however, that in some settings, such distributed settings in which network bandwidth is limited, using fewer iterations is preferred, even the cost of additional runtime per iteration. future work we plan to run the ESE procedure on the CPU in the background in the effort of saving this extra runtime altogether.
It should be noted that this calculation does not take into account the extra evaluation steps during the training process, which has identical runtime with and without FOST; hence, POST's actual runtime is closer to that the hase optimizer.
For DNNs gradient computation can be parallelized over the samples in a batch, however, it must be executed serially for each individual sample. In contrast, operations such matrix-vectoon multiplication and vector addition be efficiently parallelized.
19

---

Published as a conference paper at ICLR 2024
Adom
HB
FOSHAdam
FOSHIB
Adam
HB
FOS Addim
FDS-4B
0.30
validesionn loos
waliddelin Sirtii looa
traas loss
train loss
50
100
10
20
100
100
200
200
400
100
200
epoch
epoch
(a) LR
(b) AE
Adom
HB
FOSI Acom
FOSI HB
Adbm
HB
FOS Adom
FOS: HB
0.8
2.5
validation loss
volidaation loss
train 1zz2
0.7
train lass
train loss
2.0
1.5
1
10
50
100
10
5000
10000
200
5000
10000
apoch
(seconds)
(seconds)
iteration
(c) TI.
(d) LM
Figure 5: Learning curves of different optimizers for different DNN training tasks. In cases FOSI obtains faster convergence than the base optimizers across epochs (left) and across wall time (middle). Since FOSI accelerates convergence, it also leads to an earlier overfitting point when the base optimizer has tendency to overfit, as can be observed in the LR validation loss (right).
Table Comparison of wall time (in seconds) for each base optimizer and FOSI at the same train loss, which is the minimal train loss of the base Optimizer. A lower wall time is preferable as it indicates the optimizer reaches the best loss at faster rate.
Task
HB
FOSI-HB
Adam
FOSI-Adam
AC
6845
3599
6042
6825
LM
255
177
255
233
AE
372
322
375
338
TL
103
58
104
71
LR
18
10
19
19
Table 2 shows the time takes for both the base optimizer and FOSI to reach the same train loss, which is the lowest train loss of the base optimizer. On average, FOSI achieves the same loss over the training set in 78% of the wall time compared to the base optimizers.
Figure 6 shows the learning curves of FOSI-HB, K-FAC and L-BFGS. In all cases, FOSI converges faster and to a lower validation loss than K-FAC and L-BFGS. Specifically:
LR: K-FAC converges quickly but overfits dramatically, resulting in much higher validation loss than FOSI. L-BFGS converges much more slowly than the other approaches and to a much higher validation loss.
TL.: Both K-FAC and L-BFGS converge slower than FOSI and result in higher validation loss.
AE: K-FAC converges quickly but is noisy and leads large validation loss (52.1 compared
51.4 for FOSI), while L-BFGS diverges quickly after the first epoch, even with large values of L.
LM: we could not get the K-FAC implementation to work on this RNN model (this is a known
issue with K-FAC and RNN [Mrtens et al. 2018)). L-BFGS converges more slowly, and to much higher loss.
AC: K-FAC converges slower than FOSI and shows substantial overfitting, while L-BFGS does
not converge.
20

---

Published as a conference paper at ICLR 2024
HUU
validetion loss
0.26
0.24
wall time (seconds)
wall time (seconds)
wall time (seconds)
time (seconds)
(a) LR
(b) AE
Fosi-BB
KFFCC
-FOS-HH
LLEGSS
2.5
volidation loxs
train bos
train loos
volidation
2.0
50
750
wall time (seconds)
wall time (seconds)
wall time (seconds)
wall time (seconds)
TL
(d) LM
FOSS-B
MFAC
L48FGS
'11
vallecction lods
lozs
0.02
20000
600C0
wall time (seconds)
wall time (seconds)
(e) AC
Figure 6: Learning curves of FOSI-BH, K-FAC, and L-BFGS for the DNN training tasks AE, TL, LM, and AC. In the TL figure (top-right), L-BFGS (L=40) omitted due to its poor performance, resulting in a significantly larger loss than other optimizers and 8x slower wall time. Similarly, in the AE figure (top-left), L-BFGS (L;=100)
excluded due its divergence in the first epoch. In the LM figure (bottom-left). K-FAC was omitted due to integration issues with RNN Across all tasks, FOSI demonstrated faster convergence lower validation loss compared to K-FAC and L-BFGS.
21

---

Published as a conference paper at ICLR 2024
x
x
0.230
0.500
0.062
75
1,000
0.125
0.015
0.003
50
0.250
0.008
0.001
0.016
1.10
1.15
1.10
1.15
0.002
1.10
1.15
1.10
1:15
0.000
1.10
1.15 1.10
1.15
0.004
b
(a) Adam (right) FOSI-Adam (left) (b) HB (right) FOSI-HB (left)
(c) GD (right) vs. FOSI-GD (left)
Figure 7: Each (b, 2) combination in each sub figure is the value of different for after 200 iterations of the optimizer. FOSI improves the base optimizer for every function. Learning curves for four functions, indicated by black x markers, can be found in Figure X
Adam
FOSIAddm
HB
FOSI-HB GD
FOSi-D
10a
6.1 6,22 vo(0)
10
6112 m0
5.14. mn
50
100
150
200
50
100
150
200
Iteration
Iteration
Figure 8: Learning curves of four specific fog functions. Each x mark in Figure is the final value of the corresponding learning curve here, i.c. the value of f at iteration 200.
B.2 QUADRATIC FUNCTIONS
B.2.1 DIMENSIONALITY AND EIGENSPECTRUM
Here we provide the full details regarding the experiment in $ 4.3 where we explore the effect of both the condition number and the diagonally dominance of the function's Hessian the different optimizers. To do so, we define a set of functions (b) 0.50" Hh.00 for E (1.1,... 1.17) and { E (O.... 100), e 1000 where b and { are parameters that define the Hessian Hag- The parameter determines the cigenvalues of Hozz E (I.... 100 2, = 0.001b The parameter Ç determines the number of rows in Hag that are not dominated by the diagonal element, i.e., the part of Hb. which not diagonally dominant.
To construct Нeg, start from diagonal matrix whose diagonal contains the eigenvalues accord- ing to b. We then replace square block on the diagonal of this matrix with a PD square block of dimensions & X whose eigenvalues are taken from the original block diagonal and its eigenvectors are some random orthogonal basis. The result is a symmetric PD block diagonal Ha with one block of size x and another diagonal block, and the eigenvalues are set by b.
An important observation is, that for a specific b value, bj. and two different & values, &i and Zz, the Hessians Hb and Hhgg share the same eigenvalues and their eigenvectors are differ by a simple rotation. The starting point Og in all the experiments is the same and it is rotated by rotation matrix that is Ha.'s eigenvectors. As result, for all the experiments with the same the starting values (6b) are identical.
Figure 7 shows for at the optimal point after 200 iterations of the optimizers for different b and values. For specific b value, rotations of the coordinate system (changes in {) have no impact on GD and HB, as seen by the vertical lines with the same value for different & values. Their performance deteriorates for larger b values (more ill-conditioned problems). When applying FOSI, two functions with similar & and different are still differ by an
the new maximal eigenvalues order of magnitude, which leads to the differences in FOSI's performance along the b axis. Adam's performance negatively affected for large b and & values. FOSI improves over the base optimizer in all cases.
22

---

Published as a conference paper at ICLR 2024
Adam
Adam
HB
(c=1)
(c=1)
FOSI-B (c-1)
FOSHIB te=inf)
GOSiGD (c=inf)
FBSI-BB (c-int)
10a
11 ool0
10t
10:1
10"2
10-3
10a1
10"2
10"
(a) Fixed B and Bi (0.9)
(b) 8 and Bi tuned per ?7
Figure 9: f1,12,90 after 200 iterations with different learning rates. Each curve is for different optimizer, while each point the curve the final f value after 200 iterations with specific learning rate. Left: using fixed momentum value of 0.9, B for HB and B1 for Adam. Right: the best momentum E [0.7, for each FOSI improves over the base optimizer even when using the optimal hyperparameter set.
Figure 8 shows the learning curves of the optimizers for four specific for functions: f1.22.0-J1112.00. f116.50- f1.1690. The black x marks in each sub figure of Figure 7 are the last value of these learning curves. For both functions with = 1.12 the learning curves of GD and Heavy- Ball (as well as FOSI with these base optimizers) are identical, as they are only differ by a rotation, and similarly for b 1.16. However, for the same Ç, these optimizers convergence is much slower for larges value. FOSI implicitly reduces the maximal cigenvalue both functions, but the new two maximal eigenvalues still differ by an order of magnitude, which leads to the differences in FOST's performance (as opposed to the first experiment on quadratic functions). Adam is negatively impacted when & is increased. In this experiment. For smaller values its performance is not im- pacted by the change and is able to converge to the same value even for functions with larger curvature.
B.2.2 LEARNING RATE AND MOMENTUM
In the last experiment quadratic functions, use each optimizer to optimize the function fi.12.00 multiple times, with different learning rates 17 E (le - 10). FOSI-HB and FOSI-GD were run with both 1 (no scaling) and version we used a fixed momentum parameter 0.9 (B for HB and B1 for Adam). In the second version find the best momentum parameter [0.7, 1) for each 77.
(no clipping). We repeated the experiment twice. In the first
FigureD]shore the results after 200 iterations for every optimizer and learning rate FOSI improves over Adam for all learning rates. For GD and HB, with 1, FOSI expands the range of values for convergence, changes the optimal 17. and leads to superior results after the same number of iterations. With co, FOSI improves over the base optimizer for all 77 values, but the range of r) values for convergence stays similar. Moreover, FOSI's improvement over the base optimizer when using the optimal set of hyperparameters similar to the improvement for fixed momentum parameters. Similar trends were observed when repeating the experiment for other fo. functions.
23


Reviews:
[{"review_id": "NTRQgKRPtq", "reviewer": "Reviewer_UYzc", "summary": "In this paper, the authors presented a novel optimization method called FOSI, which is a hybrid optimizer algorithm that combines the first-order optimizer with Newton's method. They presented some theoretical analysis as well as some empirical results from the numerical experiments.", "questions": "Please check the weakness section.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This submission is well-organized with clear language and structures. The authors gave detailed description and some theoretical analysis for the proposed algorithms. They also conduct a lot of numerical experiments on deep learning problems and these empirical results are pretty good compared with some state-of-art optimization methods. The idea is pretty interesting and enlightens some promising future direction for the optimization community.", "weaknesses": "There are some disadvantages regarding this submission.\n\nThe authors only gave the theoretical results for the stochastic optimization problem. What's the convergence rate for the general convex optimization problem? What is the convergence rate for the strongly convex setting? If the authors could add and present these theoretical analysis. This could significantly improve the quality of this submission.\n\nIt's better to put the detailed algorithm from the appendix to the main part of the paper.\n\nIt's better to put the section 5 related work part in the section 1 introduction part.", "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": "", "extra_scores": {}}, {"review_id": "LMDXbfaNr3", "reviewer": "Reviewer_dEKh", "summary": "In this paper, the authors present a hybrid method which addresses the challenge of incorporating second-order information in machine learning approaches due to the computational difficulty in high dimensions. This method first splits the space into two orthogonal subspace. Then, the author use first-order method to minimize one of the subspace and use second method to minimize the other one. They also analyze the convergence of FOSI and establish certain conditions under which the proposed method improves the base method. Numerical experiments illustrate the effectiveness of the proposed method.", "questions": "In comparison with second-order methods, it is better to compare the proposed with KLBFGS but not LBFGS because the former method is designed specifically for deep learning tasks. It is suggested to add comparison with Shampoo[1] or NGPlus[2], which has good effectiveness in practice. \n\nit is better to tune the hyper-parameters of ADAM in numerical experiments to make the baseline strong enough. \n\nWhy the curve of FOSI-HB decreases in Figure 2? \n\nCan randomized numerical algebra be combined in ESE procedure? This will help reduce the computational cost.\n\n[1] Anil, Rohan, et al. \"Scalable second order optimization for deep learning.\" arXiv preprint arXiv:2002.09018 (2020).\n[2] Yang, Minghan, et al. \"An efficient fisher matrix approximation method for large-scale neural network optimization.\" IEEE Transactions on Pattern Analysis and Machine Intelligence 45.5 (2022): 5391-5403.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The idea that splitting the raw space into two orthogonal spaces is interesting. The authors adopt the Lanczos to give a possible way to construct these spaces.", "weaknesses": "One of my major concern is that the memory consumption and computational complexity are very high especially for large-scale neural networks. This will limit the usage of the proposed method. Besides, it is not clear how to handle the communication cost  and the computation of $V$ in the distributed setting.\n\nThe scale of the network architecture used in the numerical experiments is limited. It will be more convincing if the authors can show the effectiveness of the proposed method in larger applications.", "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": "", "extra_scores": {}}, {"review_id": "FI69WWwdnL", "reviewer": "Reviewer_XiKZ", "summary": "The paper proposes FOSI -  a novel meta-algorithm that improves the performance of any base 1st order optimizer\nby efficiently incorporating 2nd-order information.\n\nIn each iteration, FOSI implicitly splits the function into two quadratic functions\ndefined on orthogonal subspaces, then uses a 2nd-order method to minimize\nthe first, and the base optimizer to minimize the other.\n\nEmpirical results shown on many tasks in real-world domain to show the efficacy of POSI.", "questions": "In the statement (step 2m Lemma 1):\n\"The preconditioner P is symmetric and PD:.\n\nIs it possible to use a different font for the matrix \"P\", which has no conflict of P (positive) in \"PD\" ?\nor vice-versa.\n\nHope the code of the paper, to implement FOSI for any application of Optimization,\nwill be released soon by authors.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Nice analytics with detailed derivations and explanation.\n\nLarge amount of empirical studies shown with experimental results.\nSteps of the algorithm are clearly specified.\n\nEnjoyed reading the paper.", "weaknesses": "A few failure cases may be discussed.\n\nAlthough decomposing the problem into two parts may not specifically be novel,\nFOSI’s inverse preconditioner seems to be quite a good idea.\n\nSimilar work on those lines of decomposing may be mentioned.", "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": "", "extra_scores": {}}, {"review_id": "HKe7igwDrU", "reviewer": "Reviewer_S4Ex", "summary": "his paper provides a novel algorithm to accelerate the first-order optimizers by incorporating second-order information. The proposed method is well-motivated and the experimental results show the efficiency of it.", "questions": "1. There are some optimizers which also use the hybrid directions of first and second-order methods, or partial information of the Hessian. The author may need to compare and discuss them [1 ,2].\n\n2. Can the authors provide some discussion and numerical evaluation on how to choose $k$ and $l$.\n\n\n**Reference**\n\n[1]. Zhang C, Ge D, Jiang B, et al. DRSOM: A Dimension Reduced Second-Order Method and Preliminary Analyses[J]. arXiv preprint arXiv:2208.00208, 2022.\n\n[2]. Liu H, Li Z, Hall D, et al. Sophia: A Scalable Stochastic Second-order Optimizer for Language Model Pre-training[J]. arXiv preprint arXiv:2305.14342, 2023.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The method is novel which incorporate the descent direction of first-order methods (base optimizer) with second-order information. The empirical study is comprehensive and show the efficiency of the proposed methods. This paper is an interesting attempt on accelerating the first-order methods by using second-order information.", "weaknesses": "The method requires to compute the extreme eigenvalues and vectors of Hessian by lanczos algorithm, it will raises much more computational cost per iteration than the first-order methods. Additionally, it is unknown how to choose $k$ and $l$ in the proposed algorithm. Neither the theoretical analysis and empirical study miss the part on evaluating how $k$ and $l$ affect the behavior of the methods. Besides, the parameters are too much, not only $k$, $l$ need to be chosen, Algorithm 2 also requires the parameter for learning rates $\\alpha$, the learning rate for the base optimizer.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)