ViViT: Curvature access through the generalized Gauss-Newton's low-rank structure
Authors: Felix Dangel
Lukas Tatzel
Philipp Hennig
Venue: ICLR 2022 Submitted (2022)
Keywords: generalized Gauss-Newton
curvature
second-order methods
Hessian spectrum in deep learning
automatic differentiation

Abstract: Curvature in form of the Hessian or its generalized Gauss-Newton (GGN) approximation is valuable for algorithms that rely on a local model for the loss to train, compress, or explain deep networks. Existing methods based on implicit multiplication via automatic differentiation or Kronecker-factored block diagonal approximations do not consider noise in the mini-batch. We present ViViT, a curvature model that leverages the GGN's low-rank structure without further approximations. It allows for efficient computation of eigenvalues, eigenvectors, as well as per-sample first- and second-order directional derivatives. The representation is computed in parallel with gradients in one backward pass and offers a fine-grained cost-accuracy trade-off, which allows it to scale. As examples for ViViT's usefulness, we investigate the directional first- and second-order derivatives during training, and how noise information can be used to improve the stability of second-order methods.

Under review as a conference paper at ICLR 2022
VIVIT: CURVATURE ACCESS THROUGH THE GENERAL- IZED GAUSS-NEWTONY LOW-RANK STRUCTURE
Anonymous authors Paper under double-bling review
ABSTRACT
Curvature in form of the Hessian or its generalized Gauss-Newton (GGN) ap- proximation is valuable for algorithms that rely on a local model for the loss to train, compress, explain deep networks. Existing methods based on implicit multiplication via automatic differentiation or Kromecker-factored block diago- nal approximations do not consider noise in the mini-batch. We present VIVIT, a curvature model that leverages the GGN's low-rank structure without further approximations. allows for efficient computation of eigenvalues, eigenvectors, as well as per-sample first- and second-order directional derivatives. The repre- sentation is computed in parallel with gradients in one backward pass and offers fine-grad fine-grained cost-accuracy trade-off, which allows it to scale. As examples for VIVIT's usefulness, we investigate the directional first- and second-order deriva- tives during training, and how noise information can be used to improve the stability of second-orde -oder methods.
INTRODUCTION & MOTIVATION
The large number of trainable parameters in deep neural networks imposes computational constraints on the information that can be made available to optimization algorithms. Standard machine learning libraries (Abadi et al., 2015; Paszke al., 2019) mainly provide access to first-order information in the form of average mini-batch gradients. This is a limitation that complicates the development of novel methods that may outperform the state-of- of-the-art They must use the same objects to remain easy to implement and use, and to rely the highly optimized code of those libraries. There is evidence that this has led to stagnation in the performance of first-order optimizers (Schmidt et al., 2021). Here, we thus study how to provide efficient access to richer information, namely higher-order derivatives and full statistics of the mini-batee batch loss.
Recent advances in automatic differentiation (Bradbury et al., 2020; Dangel et al., 2020) have made such information more readily accessible through vectorization of algebraic structure in the differentiated loss. We leverage and extend this functionality to efficiently access curvature in form of the Hessian's 's generalized Gauss-Newton (GGN) approximation. It offers practical advantages over the Hessian and is established for training (Martens, 2010; Martens & Grosse, 2015), compressing (Singh & Alistarh, 2020), or adding uncertainty to (Ritter et al., 2018b;a; Kristiadi et al., 2020) neural nets. It is also linked theoretically to the natural gradient method (Amari, 2000) via the Fisher information matrix (Martens, 2020, Section 9.2), and has been used to investigate the generalization of neural networks (Jastrzebski al., 2020; Thomas et al., 2020).
Traditional ways to access curvature fall into two categories. Firstly, repeated automatic differen- tiation allows for matrix-free exact multiplication with the Hessian (Pearlmutter, 1994) and GGN (Schraudolph, 2002). Iterative linear and eigensolvers can leverage such functionality to compute Newton steps (Martens, 2010; Zhang et al., 2017: Gargiani et al., 2020) and spectral properties (Sagun et al., 2017; 2018; Adams et al., 2018; Ghorbani et al., 2019; Papyan, 2019b; Yao et al., 2019; Granziol et al., 2021) 1) on arbitrary architectures thanks to the generality of automatic differentiation. However, repeated matrix-vector products represent critical factor for performance.
Secondly, Kronecker-factin factored approximate curvature (K-FAC) (Martens & Grosse, 2015; Grosse & Martens, 2016; Botev et al., 2017; Martens et al., 2018) constructs explicit light-weight representation of the GGN based on its algebraic Kronecker structure. The computations are streamlined via gradient backpropagation and the resulting matrices are cheap store and invert.

---

Under review as a conference paper at ICLR 2022
This allows K-FAC to scale: It has been used successfully with very large mini-batches (Osawa et al., 2019). One reason for this efficiency is that K-FAC only approximates the GGN's 's block diagonal, neglecting interactions across layers. Such terms could be useful, however, for other applications, like uncertainty quantification with Laplace approximations (Ritter et al., 201 8b;a; Kristiadi et al., 2020) that currently rely on K-FAC. Moreover, due its specific design for optimization, the Kronecker representation does not become more accurate with more data. It remains a simplification, exact only under assumptions unlikely to be met in practice (Martens & Grosse, 2015). This might be downside for applications that depend on a precise curvature proxy.
Here, we propose VIVIT (inspired by VVT in Equation (3)), a vivid curvature model that leverages the GGN's 's low-rank structure. Like K-FAC, its representation is computed in parallel with gradients. But it allows a cost-accuracy trade-off, ranging from the exact GGN to an approximation that has the cost of single gradient computation. Our contributions are as follows:
We highlight the GGN's low-rank structure, and with it structural limit for the inherent curvature information contained in a mati.
This low-rank structure allows for efficient computation of various GGN properties: The exact eigenvalue spectrum, including eigenvectors, and per-sample directional derivatives. They enable VIVIT to model curvature noise in a mini-batch, in contrast to existing methods.
Approximations allow VIVIT to flexibly trade off computational cost and accuracy. We empirically demonstrate scalability on deep neural networks and provide a fully-featured efficient implementation in PYTORCH (Paszke al., 2019) on top of the BACKPACK (Dangel et al., 2020) package.
Using VIVIT, illustrate that noise in deep learning poses challenge for the stability of second- order methods and give a simple example how its quantities can he used to address this problem.
2 NOTATION & METHOD
Consider a model f e X + Y and dataset {(x,, yy.) E X Y) For simplicity we use N for both the mini-batch and training set size. The network, parameterized by 0 E O maps sample F, to a prediction Dn- Predictions are scored by a convex loss function é : Y x Y - IR
(e.g. cross-entropy or square loss), which compares to the ground truth yn. The training objective L : + R is the empirical risk
(1) We use e, (0) = {[ 2,), yn) and (0) = f(0, ..)) ) for per-sample losses and predictions. For gradients, write (0) -ol., (0) and g VoL(O), suppressing 0 if unambiguous. We also set θ = I D and Y R with D, C the model parameter and prediction space dimensions, respectively. For classification, C the number of classes.
((0) N Ew (.)()
Hessian & GGN: Two-fold chain rule application to the split { o f decomposes the Hessian of Equation (1) into two parts ((C( G(0) R(0)= E R. DxD the positive semi-definite GGN
G = (JoSn) (V Cn) (Jof))
E. Gn,
(2)
and a residual R = 1/N EC (Vginle) V ln Here, we use the Jacobian Jab that
contains partial derivatives of with respect to a, Jab]e ij = @lb):/Ola];- As the residual may alter the Hessian's definiteness - an undesirable property for many applications we focus on the GGN,
Low-rank structure: By basic inequalities, Equation (2) has rank(G) S NC.2 To make this explicit, we factorize the positive semi-definite Hessian V En = C 8ac where 8nc E RC and denote its backpropagated version by Une = [J sne E D. Absorbing sums into matrix multiplications, we arrive at the GGN's outer product representation that lies at the heart VIVIT,
G G= EN UneV m VVT with V
U1
V12
UNC) E DNNC (3)
VN
'Code available at https: pettps//giit //tpthub..bttt//////. com/ 3k4 We assume the overparameterized deep learning setting (NC < D) and suppress the trivial rank bound D.
2

---

Under review as a conference paper at ICLR 2022
V allows for exact computations with the explicit GGN matrix, at linear rather than quadratic memory cost D. We first formulate the extraction of relevant GGN properties from this factorization, before addressing how further approximate V to reduce memory and computation costs.
2.1 COMPUTING THE FULL GGN EIGENSPECTRUM
Each GGN eigenvalue À R satisfies the characteristic polynomial det(G - > = 0 with identity matrix In E RDxD Leveraging the VIVIT factorization of Equation (3) and the matrix determinant lemma, the D-dimensional eigenproblem reduces to that of the much smaller Gram matrix G = V NCXNCC which contains pairwise scalar products of Une (see Appendix A.
det(G - A =0
(-A)D-NC det - XINc) =0
(4)
With least D NC trivial solutions that represent vanishing eigenvalues, the GGN curvature is flat along most directions in parameter space. Nontrivial solutions that give rise to curved directions fully-contained in the Gram matrix, and hence much cheaper compute. For example, the left panel of Figure la visualizes the full, exact GGN's s empirical spectral density on a mini-batch for deep convolutional neural net on CIFAR- 10. reproduces the characteristics that have been reported by numerous works, e.g. Sagun et al. (2018): An extensive amount of vanishing or small eigenvalues and small number of larger outliers.
Despite these various Hessian spectral studies which rely on iterative eigensolvers and implicit matrix multiplication (Sagun al., 2017; 2018; Adams et al., 2018; Ghorbani et al., 2019; Papyan, 2019b; Yao et al., 2019; Granziol al., 2021), spectrum from its Gram matrix. In contrast to those techniques, this matrix can be computed in parallel with gradients in single backward pass, which results in less sequential overhead. In fact, our approach allows for plots like Figure to be efficiently live- -ww-mmoitoeed during training, which may be interesting for practitioners that seek to better understand their model (Schneider al., 2021).
not aware of works that extract the exact GGN
Eigenvalues themselves can help identify reasonable hyperparameters, like learning rates. But we also reconstruct the associated eigenvectors in parameter space. These are directions along which curvature information contained in the mini-batch. Let S. {(>,, ēx) A 0, Gē, = ) denote the nontrivial Gram spectrum with orthonormal eigenvectors é ég ōjж (5 represents the Kronecker delta and K rank(G)) Then, the transformed set of vectors e& 1/vx. Vog orthonormal eigenvectors of G associated to eigenvalues A (see Appendix A.2),
A (Ax. @x) S, Gē λ
GVê, VēR
(5)
The eigenspectrum provides access to the GGN's pseudo-invers based on V and S.., required by e.g. second-order methods (see Section 4.2). As show next, quadratic models defined through the GGN naturally decompose along the eigenvectors from + {Ax, ex) A * 0, Ge, = \
2.2 COMPUTING DIRECTIONAL. DERIVATIVES
Various algorithms update their solution by constructing local quadratic approximation of the loss landscape. For instance, optimization methods adapt their parameters by stepping to the local proxy's 's minimum. Such quadratic models are based on a second-order Taylor expansion and hence require some form of curvature. Let (0) denote quadratic model for the loss around position 0, E θ that uses curvature represented by the GGN,
(0) const + (0 0.) ((.))) 1 )0 0.) T.) T(())) 0.)
At its base point 0,, the shape of along an arbitrary normalized direction e E (i.e. ||e| = 1) is determined by the local gradient and curvature. Specifically, the projection of Equation (6) onto gives rise to the first-and second-ores -oddrr directional derivatives
Ye Vog (,)) = T g(,)) E ER,
(7a)
A- = G
(7b)
As G's characteristic directions are its eigenvectors, they form natural basis for the quadratic model. Denoting " = =Ye, and 0S = Ae, the directional gradients and curvatures along eigenvector eg. we from Equation (7b) that the directional curvature indeed coincides with the GGN's 's eigenvalue.
3

---

Under review as a conference paper at ICLR 2022
In addition to the mean gradient and curvature along eigenvector es. can expand the samples from Equation (1) to obtain the per-sample contributions to each derivative. Let Yok and Ank denote these first- and second-order derivatives contributions of sample 2n in direction k. i...
Iik e 0 VV
gn
(8a)
AE V
V V
|| Vē
An = Ex Gn
(8b)
A
A
where V, E DxC is the VIVIT factor of G, corresponding to scaled sub-matrix of V with fixed sample index. Note that directional derivatives can be evaluated efficiently with the Gram matrix eigenvectors without explicit access to the associated directions in parameter space. In Equation (7) gradient and curvature G are sums over In. and Gn, respectively. This structure also carries over to the directional derivatives, i.e. 1/N En Tnnk and A 1/N >a
Ank-
Access to per-sample directional gradients 7nk and curvatures Ank along G's natural directions is a distinct feature of VIVIT. Not only do these quantities provide geometric information about the local loss landscape but also about its directional stochasticity over the mini-batch, Incorporating such knowledge about the noise into algorithms that rely on quadratic models provides a promising way increase their performance and stability. Section 4.2 we show how to use this information to make second-orde optimization methods more robust against noise.
2.3 COMPUTATIONAL COMPLEXITY
So far, we have formulated the computation of GGN eigenvalues (Equation (4)) including eigen- vectors (Equation (5)) and per-sample directional derivatives (Fquation (8)). Now, we analyze their computational complexity more detail to identify critical performance factors. Those limitations effectively be addressed with approximations that allow the costs to be decreased in fine-grained fashion. We evaluate their effectiveness on deep neural networks to demonstrate that VIVIT scales.
Relation to gradient computation: Machine learning libraries are optimized to backpropagate sig- nals 1/NV fn e and accumulate the result into the mini-batch gradient g 1/N Σ [Jo V Ln Each column Une of V also involves applying the Jacobian, but to a different vector Sne from the loss Hessian's 's symmetric factorization. For popular loss functions, like square and cross-entropy loss, this factorization is analytically known and available at negligible overhead. Hence, computing V basically costs C gradient computations as it involves NC backpropagations. while the gradient requires N. However, the practical overhead is expected to be smaller: Computations can re-use information from the Jacobians and enjoy significant additional speedup on parallel processors like GPUs. Because our implementation relies on BACKPACK vectorized Jacobians, we expect similar run time performance as its second-order extensions which have the same backpropagation.
Stage-wise discarding V (GGN eigenvalues & directional derivatives): The columns of V correspond to backpropagated vectors. During backpropagation, sub-matrices of V. associated to parameters in the current layer, become available once at a time. As many of the above GGN properties can computed by contraction and accumulation these stage-wise VIVIT factors, they can be discarded immediately. This allows for memory savings without any approximations.
One example is the Gram matrix G formed by pairwise scalar products of N in ((NC)²)) operations. The spectral decomposition S. has additional cost of ((NC))). Simi- larly, the terms for the directional derivatives in Equation (8) be built up stage-wise: First-order derivatives {Trkk) [ require the vectors { (V" In. IR NCW J== that cost O(NCDD operations. Second-order derivatives are basically for free, (V. V RCNNO
In=1 is available from G.
GGN eigenvectors: Raising one Gram matrix eigenvector ēN to the GGN eigenvector es through application of V (Equation (5)) costs O(NCD) operations. However, repeated application of V can be avoided for raising weighted sums of the form Σ. (st/Va)), with arbitrary weights C E RR. The summation can be performed in the Gram space negligible overhead, and only single vector Ee o needs to be transformed. For instance, this allows for efficient aggregation of Newton steps along directions in the Gram space before transforming them to parameter space (see Section 4.2).
4

---

Under review as a conference paper at ICLR 2022
(a)
exact,
exact, frac
MC, full
(b)
Nai (eigenvalues)
GGN
full
frac
10-4
exact
390
991
Density
MC
2792
4839
10-5
Noit (block Newton)
GGN
Batch
full
frac
exact
349
795
10-3 1
10
10
10
10'
10
10
10
MC
1659
2112
Eigenvalues
Eigenvalues
Eigenvalues
Figure 1: Reducing costs with curvature sub-sampling, MC-sampling, and parameter groups. (a) GGN eigenvalue distribution of the 3C3D architecture on CIFAR-10 (D = 895,210, C 10) for settings with different costs on a mini-batch of size N 128 (Schneider al., 2019). From left to right: Exact GGN on the full batch, exact GGN on a batch fraction (1/8, as in Zhang et al. (2017)), MC approximation
the GGN on the full batch. (b) Maximum batch size Nexi on a GeForce RTX 2080 Ti (I1 GB) for a standard gradient computation and the GGN spectrum and (c) computing exact Newton steps with layer-wise parameter groups. More architectures and details in Appendix B.1.
2.4 APPROXIMATIONS & IMPLEMENTATION
Although the GGN's representation by V has linear memory cost in D, it requires memory equivalent to NC model copies. Of course, this infeasible for many networks and data sets, e.g. IMAGENET (C 1000). So far, our formulation was concerned with exact computations. We now present approximations that allow N and C the above cost analysis to be replaced by smaller numbers, enabling VIVIT trade-off accuracy and performance.
Curvature sub-samlin & MC approximation: To reduce the scaling in C, we can approximate the factorization V2, (0) = E Snc by a smaller set of vectors. One principled approach to draw MC samples {5am] such that Em (5m
V (n(()) as in Dangel et al. (2020). This reduces the scaling of backpropagated vectors from C' to the number of MC samples (1 in the following). Another commonly used independent approximation to reduce the scaling in N is to compute curvature only on subset of mini-batch samples (Byrd et al., 2011; Zhang et al., 2017).
Parameter groups (block (block-diagonal approximation): Some applications. e.g. computing Newton steps. require V to be kept in memory for performing the transformation into the parameter space. Still, we can reduce costs by using the GGN's diagonal blocks {G(0) of each layer, rather than the full matrix G. Such blocks are available during backpropagation and can thus be used and discarded step by step. addition to the previously described approximations for reducing the costs in N and C, this technique tackles scaling in D.
To assess the quality the above approximations, Figure la shows the exact GGN eigenvalue spectrum (left) in comparison to its approximation through curvature sub-sampling (center) and MC (right). Even though the amount of backpropagated vectors is reduced by factor of 8 and 10, respectively. the approximated spectra capture essential features. We also tabularize the critical batch sizes Nem at which their computations experience out-of-memory errors in Figure 1b. On standard GPU, they exceed the traditional batch size used for training, even for the exact scheme. Approximations further increase the applicable batch size.*
Conerete example & implementation details:
'The critical batch sizes in Figure 1b and differ strongly for similar reductions of 8 and in the number of backpropagated vectors. This is because most neural networks have final layers with many parameters. During initial stages of backpropagation, expanding V for these weights critically affects peak memory, and thus Nmm- This can he improved by leveraging structure in the Jacobian (see Appendix C.
5

---

Under review as a conference paper at ICLR 2022
As concrete example for block-diagona approximations, we group weights and biases layerwise and compute the exact Newton step implied by the GGN's block-diagonal approximation (similar to Zhang et al. (2017)). Figure 1c shows the critical batch size and supports our approach's is scalability.
BACKPACK's 's functionality allows us to efficiently compute individual gradients and V in a single backward pass, using either an exact or MC-factorization of the loss Hessian. To reduce memory consumption, we extend its implementation with a protocol to support mini-batch sub-sampling and parameter groups. By hooks into the package's extensions, we can discard buffers as soon as possible during backpropagation, effectively implementing all discussed approximations and optimizations.
3 RELATED WORK
GGN spectrum & low-rank structure: Other works point out the GGN's low-rank structure.
Botev et al. (2017) present the rank bound and propose an alternative to K-FAC based on backpropa- gating a decomposition of the loss Hessian. Papyan (2019a) presents the factorization in Equation (3) and studies the eigenvalue spectrum's 's hierarchy for cross-entropy loss. In this setting, the GGN further decomposes into summands, some of which are then analyzed through similar Gram matrices. These can be obtained contractions of G. but approach goes beyond them it does not neglect terms. We are not aware of works that obtain the exact spectrum and leverage a highly-efficient fully-parallel implementation. This may be because, until recently (Bradbury et al., 2020; Dangel et al., 2020), vectorized Jacobians required to perform those operations efficiently were not available.
Efficient operations with low-rank matrices in deep learning: Chen et al. (2021) use Equa- tion (3) for element-wise evaluation of the GGN in fully-connected feed-forward neural networks. They also present a variant based on MC sampling. This clement-wise evaluation is then used to construct hierarchical matrix approximations of the GGN. VIVIT instead leverages the global low-rank structure that also enjoys efficient dignnddccomposition and linear solves.
Another prominent low-rank matrix in deep learning is the un-centered gradient covariance (some- times called empirical Fisher). Singh & Alistarh (2020) describe implicit multiplication with its inverse* and apply it for neural network compression, assuming the empirical Fisher as Hessian proxy. However, this assumption has limitations, specifically for optimization (Kunstner et al., 2019). In principle though, the low-rank structure also permits the application of our methods from Section 2.
EXPERIMENTS
Different phases are encountered in the course of neural network training (Frankle et al., 2020). We view those regimes in light of our newly accessible quantities and identify challenges for second-orde optimizers. Then, on a simple example, we use those quantities to stabilize such methods.
4.1 NOISE DURING TRAINING
The interaction between gradient, curvature, and their stochasticity is crucial for the behavior of optimization methods (Thomas et al., 2020). Here, we aim to identify characteristic features of gradient noise, curvature noise, and their interaction to gain insights into the conditions under which deep learning optimizers are operating. Training different architectures from the DEEPOBS problem set using the baselines from Dangel et al. (2020), we evaluate the GGN's nontrivial eigenvectors and per-sample directional derivatives on fixed held-out mini-batch with VIVIT. Figure 2 shows results for the 3C3D architecture trained on CIFAR evaluation that includes more problems, training with ADAM, and description of procedural details, is given in Appendix B.2. We make the following observations.
using SGD and cross-entropy loss. A broader
Directional gradient-curvatur correlations: Figure 2a shows pairs of GGN eigenvalues d and the associated directional gradient magnitude ITxl at different training stages. Like for a quadratic function, gradients and curvatures are positively correlated.
For completeness, we describe implicit multiplication with the inverse GGN in Appendix C.2. We show [Ya because the directional gradient varies in sign, depending on the eigenvector's 's orientiation.

---

Under review as a conference paper at ICLR 2022
(a)
Loss: 2.326 (K 1152)
Loss: 1.209 (K' 1121)
Loss: 0.330 (K (85)
10
[Tc
10
10-6
(b)
10
Det /|/l
10
10-6
10
SNR((A)
10
(d) 10
SNR(
10
10-5
10
10 10
10a 10
10
10"
10a
10
10
10"
10a
A
A
A
Figure 2: Gradient, curvature and noise during training. Columns show the 3C3D architecture initialization (left), an early (epoch 5, center), and ad advanced (epoch 68, right) stage of training on CIFAR-I0 with SGD (hyperparameters from Schneider et (2019); Dangel et (2020), details in Appendix B.2). For each direction k, characterized by its curvature λ we monitor (a) the directional gradient magnitude; (b) gradient-eigenveeto alignment; (c.d) SNRs of curvatures and gradients.
High gradient overlap with top eigenspace & shrinking of non-trivial eigenspace: Similar to Gur-Ari et al. (2018), we observe high alignment between the mini-bac batch gradient and the GGN's top eigenspace. Specifically, we compute the normalized gradient overlap *1/1lal1² with direction Due to their additivity, gradient overlaps from multiple directions can be grouped by summation. The histograms in Figure 2b show such overlaps: Each bin summarizes directions of similar curvature. The accumulated normalized overlap of the gradient with these directions is shown the height of the histogram bar. The gradient aligns mostly with high-curvature directions. In particular, its overlap with flat directions, Σk_ throughout training even though the GGN's active sub-space dimension decreases.
k=1 22 r//1aal?,, is smaller than the axis limits. We observe this alignment
Curvature signal vanishes during training gradient signal is consistently small: To quantify the noise in both the directional gradients and curvatures, we compute their signal-to-now ratios (SNR). It given by the squared empirical mean divided by the empirical variance of the mini-batch samples (An J-y and (Tok J. for each non-trivial direction k.
Figures 2c,d show the evolution of both ratios. At early stages, the curvature signal along some of the high-curvature directions and parts of the bulk dominates over the noise (SNR(A&) > 1), i.c. curvatures per- per-sample GGN s are similar. As training proceeds, the signal decreases until all directions are dominated by noise (SNR())) < 1). In comparison, the directional gradients do not exhibit such a pattern. They are always strongly corrupted by noise (SNR(*) < 1), irrespective of the curvature, even though their mean 7/ correlates with ' (Figure 2a).
On the one hand, the high overlap between gradient and the top GGN eigenspace encourages gradient pre-conditioning with the GGN pseudo-inverse for second-order optimization, negligible gradient

---

Under review as a conference paper at ICLR 2022
information will be projected out. On the other hand, however, noise in both the gradients and curvatures, which can vary among directions and during training over several orders of magnitude, represents challenge for such methods. A naive Newton step based on the mean gradient and curvature along each direction may be unstable due to large noise, eliminating all previously made progress. We now turn those methods and investigate how improve their stability by equipping them with a noise-aware adaptation strategy to act individually along directions.
4.2 USE-CASE: IMPROVING DAMPING IN SECOND-ORDER METHODS
Spectral decomposition of Newton's ' method into one-dimensional problems: Second-order optimizers are based on a local quadratic approximation g (cf. Equation (6)) of the objective function. common approach to make such methods work in practice to regularize the curvature matrix with damping term å.D. 0 < 8 E I. The resulting quadratic is minimized by the update AO - - + ÓID) -pgg)--g. g. In the GGN eigenvector basis from S+ and the trivial spectrum So = {()x. ex) d 0, Ge 0} - we observe different updates in the respective sub-spaces,
99) In the non-trivial eigenspace, A takes damped Newton-type steps, while flat directions are updated with SGD at a learning rate 8-1, Motivated by Section 4.1 and Gur-Ari et al. (201 8), we omit the SGD update along flat directions in the following due to their negligible overlap with the gradient.
A = - (G +
7h Apt ek - Ek=K+1 7h ek
Global damping versus directional damping: Due to of the quadratic model are corrupted by sub-sampling noise. Hence, the mini-batee averages The = 1/N >xm I 7nk and A 1/N Σx Ank in Equation (9) may deviate considerably from the true values on the noise-free training loss. This noise can lead overly large steps and thus cause the optimization procedure to become unstable. Damping helps to increase stability as it decreases the step size. However, its relative effect on the step length in direction e₁ depends sensitively on the scale of the curvature λς- Also, even at comparable curvature scale, stronger damping may be required in the presence of high uncertainty over 7 and Ag. thus expected that treating all directions identically yields diminishing returns along certain directions while it is required to keep uncertain ones stable. This suggests directional damping, i.e. update of the form A - -E
the gradient and curvature
Xe+dE
2kk
Ck.
Noise-aware directional damping via bootstrap: We the quadratic mini-batch model's loss reduction R(xx) ) to assess the step Sk Ao
74
E IR in direction Ex.
R8x) <(0) q(0 + sHet) sk N 7hk) 1 ENENI Arks)
(10)
From observations on a mini-batch, our goal to minimize the training loss. Hence, we want to choose a damping such that its corresponding update not only reduces y, but consistently decreases the loss over all other on additional samples for this purpose. Instead, we use resampling technique based the non- parametric bootstrap (Efron, 1979) to simulate samples for R(0x) on other batches, only using information contained in Yak; Ank (details in Appendíx B). For a given damping 9g, this provides an indicator of what reduction in training loss to expect with the respective update. Taking the 5% percentile of the generrtaeeeeertee samples, we obtain a confident lower bound to R(6x). We then choose the òn that maximizes this lower bound from candidates on a discrete grid.
models as well. Ideally, one would compute directional derivatives
Evaluation on noisy quadratic: We consider a quadratic loss function C()) T G with G. 12 for i E (1,..., D= = 20} and initialize O at 100 1p. At each step, the optimizer observes unit vectors as directions {_ and noisy directional derivatives {"/n N == (>nk N.N.K -== Specifically, we design the noise to provide unbiased samples with constant variance (see Appendix B for details). We compare our directional damping based on Equation (10) with constant damping and SGD. The results reported in Figure 3 were obtained from multiple runs with different random seeds.
With constant damping, there is a trade-off between large steps that may cause instabilities (small damping) and slower progress due to smaller steps (large damping). Both extremes are observed in our experiment. For ò = 10 10-4, there are unstable runs, as indicated by the loss mean and the maximum final distance to the minimum. For large constant damping, the behavior becomes more
8

---

Under review as a conference paper at ICLR 2022
( m())))) min
||0 mmin after 20 steps
Relative damping 6x/42
10
10
10a
10
10a
100
10a
10
10-1
10
10
10
5
10
15
20
500
6x. (wrr
= 10"
d 10
100
5 10a
=z 102
5
10
15
20
5 10
step
step
=
8. (ouns
10
10
10a
Figure 3: Comparison of optimizers on noisy quadratic. Statistics for different optimizers during (left) and at the end (center) of training over 100 runs. For the loss values, we present mean (dashed line), median (solid line) and a confidence interval (shaded area) between the lower and upper quartile. Boxplot whiskers range from the distribution's 's minimum to the maximum and boxes indicate lower and upper quartile, enclosing the median. Horizontal black lines indicate the initial loss/distance. Right: Relative dampings of our adaptive method. Darker shades indicate larger curvatures.
stable and increasingly resembles SGD. Compared to constant damping, the directional noise-aware damping 6% provides the smallest median final distance to the minimum with relatively low variance.
The right panel Figure shows the directional damping dş in relation to the underlying true curvature k² for single run. We make two observations: Firstly, the relative damping increases over time to compensate for the vanishing gradient signal as the optimization approaches the minimum. Secondly, since constant noise is applied, the SNR in low curvature directions (yellow) is smaller than in high-curvature directions (red). This is also reflected in the directional damping, which tends assign larger dampings the noisier (yellow) directions. The directional bootstrap damping works as expected and yields stable runs with consistently good final performance.
We provided evidence that VIVIT's quantities may be required for the improvement of second-order methods. As the main contribution of this paper is in delivering these quantities, we deliberately designed simplistic experiments
full derivation and empirical evaluation would amount separate paper of its own right (and would be incommensurate with the space limitations).
5 CONCLUSION
We have presented VIVIT, curvature model based on the low-rank structure of the Hessian's generalized Gauss-Newton approximation. This structure allows for efficient extraction of curvature properties, such the full eigenvalue spectrum and directional gradients and curvatures along the associated eigenvectors. In contrast to alternatives, VIVIT offers statistics of these directional derivatives across the mini-batch, and thus rich noise model.
We demonstrated the utility of these new quantities by studying noise characteristics of representative deep learning tasks. We find that they pose challenges to the stability of second-order methods, and showed, in a simplistic toy model, how VIVIT can provide quantities to improve their stability.
VIVIT's representation is efficiently computed in parallel with gradients during single backward pass. As it mainly relies on vectorized Jacobians, is even general enough to be integrated into existing machine learning libraries in the future. For the moment, we provide an efficient open-source implementation in PYTORCH by extending the existing BACKPACK library.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Martin Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg Corrado, Andy Davis, Jeffrey Dean, Matthicu Devin, Sanjay Ghemawat, lan Goodfellow, Andrew Harp, Geoftrey Irving, Michael Isard, Yangqing Jia, Rafal Jazefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dan Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large-scale machine learning on heterogeneous systems, 2015.
Ryan P. Adams, Jeffrey Pennington, Matthew Johnson, Jamic Smith, Yaniv Ovadia, Brian Patton, James Saunderson. Estimating the spectral density of large implicit matrices, 2018.
Shun-ichi Amari. Natural gradient works efficiently learning. Neural Computation, 2000.
Alcksandar Botev, Hippolyt Ritter, and David Barber. Practical Gauss-Newton optimisation for deep learning. In Proceedings of the 34th International Conference on Machine Learning, 2017.
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, and Skye Wanderman Milne. JAX: composable transformations of Python + NumPy programs. 2020.
Richard H. Byrd, Gillian M. Chin, Will Neveitt, and Jorge Nocedal. On the use of stochastic Hessian information in optimization methods for machine learning, SIAM Journal on Optimization, 2011.
Chao Chen, Severin Reiz, Chenhan D. Yu, Hans-Joachim Bungartz, and George Biros. Fast approximation of the Gauss Newton Hessian matrix for the multilayer perceptron. SIAM Jourmal Matrix Analysis and Applications, 2021.
Felix Dangel, Frederik Kunstner, and Philipp Hennig. BackPACK: Packing into backprop. International Conference on Learning Representations, 2020.
Bradley Efron. Rootstrap methods: Another look the jackknife. The Annals of Statistics, 1979.
Jonathan Frankle, David J. Schwab, and Ari S. Morcos. The early phase of neural network training. In Intermational Conference on Learning Representations, 2020.
Matilde Gargiani, Andrea Zanelli, Moritz Dichl, and Frank Hutter. On the promise of the stochastic generalized Neuss-Neetoo method for training DNNs, 2020.
Behrooz Ghorbani, Shankar Krishnan, and Ying Xiao. An investigation into neural net optimization via Hessian cigenvalue density, 2019.
Diego Granziol, Xingchen Wan, and Timur Garipov. Deep curvature suite, 2021.
Roger Grosse and James Martens. Kronecker-factored approximate Fisher matrix convolution layers, 2016.
Guy Gur-Ari, Daniel A. Roberts, and Ethan Dyer. Gradient descent happens a tiny subspace, 2018.
Stanislaw Jastrzebski, Devansh Arpit, Oliver Astrand, Giancarlo Kerg. Huan Wang. Caiming Xiong, Richard Socher, Kyunghyun Cho, and Krzysztof Geras, Catastrophic Fisher explosion: Early phase Fisher matrix impacts generalization, 2020.
Agustinus Kristiadi, Matthias Hein, and Philipp Hennig. Being Bayesian, even just a bit, fixes overconfidence in ReLU networks. In International Conference on Machine Learning, 2020.
Frederik Kunstner, Philipp Hennig, and Lukas Balles. Limitations of the empirical Fisher approximation for natural gradient descent. In Advances in Neural Information Processing Systems, 2019.
James Martens. Deep learning via Hessian-free optimization. In Proceedings of the 27th International Conference on Machine Learning, 2010.
James Martens, New insights and perspectives the natural gradient method, 2020.
James Martens and Roger Grosse. Optimizing neural networks with Kronecker-factores factored approximate curvature. In Proceedings of the 32nd International Conference on Machine Learning, 2015.
James Martens, Jimmy Ba, and Matt Johnson. Kronecker-factoret curvature approximations for recurrent neural networks. In International Conference Learning Representations, 2018.
10

---

Under review as a conference paper at ICLR 2022
Kazuki Osawa, Yohei Tsuji, Yuichiro Ueno, Akira Naruse, Rio Yokota, and Satoshi Matsuoka. Large-scale distributed second-order optimization using frotoeker-factrred approximate curvature for deep convolutional neural networks. In 2019 JEEE/CVF Conference on Computer Vision and Pattern Recognition, 2019.
Vardan Papyan. Measurements of three-level hierarchical structure the outliers in the spectrum of deepnet Hessians. In Proceedings of the 36th International Conference on Machine Learning, 2019a.
Vardan Papyan. The full spectrum of deepnet Hessians at scale: Dynamics with SGD training and sample size, 2019b.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An imperative style, perfoperformnnc deep learning library. In Advances in Neural Information Processing Systems 32. 2019.
Barak A. Pearlmutter. Fast exact multiplication by the Hessian. Neural Computation, 1994.
Hippolyt Ritter, Aleksandar Botev, and David Barber. Online structured Laplace approximations for overcoming catastrophic forgetting, In Advances in Neural Information Processing Systems, 201 8a.
Hippolyt Ritter, Aleksandar Botev, and David Barber. A scalable Laplace approximation for neural networks. In International Conference on Learning Representations, 201 8b.
Levent Sagun, Leon Bottou, and Yann LeCun. Eigenvalues of the Hessian in deep learning: Singularity and beyond, 2017.
Levent Sagun, Utku Evci, V. Ugur Guney, Yann Dauphin, and Lcon Bottou. Empirical analysis of the Hessian of over-parametrized neural networks, 2018.
Robin M. Schmidt, Frank Schneider, and Philipp Hennig. Descending through crowded valley benchmarking deep learning optimizers, 2021.
F. Schneider, L. Balles, and P. Hennig. DeepOBS: A deep learning optimizer benchmark suite. In 7th International Conference on Learning Representations, 2019.
Frank Schneider, Felix Dangel, and Philipp Hennig. Cockpit: A practical debugging tool for training deep neural networks, 2021.
Nicol N Schraudolph. Fast curvature matrix-vector products for second-order gradient descent. Neural computation, 2002.
Sidak Pal Singh and Dan Alistarh. WoodFisher: Efficient second-order approximation for neural network compression. In Advances in Neural Information Processing Systems, 2020.
Valentin Thomas, Fabian Pedregosa, Bart van Merriënboer, fierre-Antoing Manzagol, Yoshua Bengio, and Nico- las Le Roux. On the interplay between noise and curvature and its effect optimization and generalization. Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, 2020.
Zhewei Yao, Amir Gholami, Kurt Keutzer, and Michael Mahoney. PyHessian: Neural networks through the lens of Hessian, 2019.
Huishuai Zhang, Caiming Xiong, James Bradbury, and Richard Socher. Block-diagonal Hessian-free optimization for training neural networks, 2017.


Reviews:
[{"review_id": "yTT5aSXXyxu", "reviewer": "Reviewer_1dgm", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is clearly written and easy to follow.\n\n**Main idea: low-rank structure of the GGN**: The main idea of taking advantage of the low-rank structure of the GGN is clearly motivated as well as the linear algebra manipulations (though somewhat basic) used to get the spectrum of the GGN. I would however not deem it as new as it is e.g. discussed in [1,2], but arguably it is interesting to emphasize how to use this low-rank structure in deep learning algorithms.\n\n**Implementation** It is difficult to judge given that no code is provided (or linked) but it would certainly be very useful to have a good implementation for such quantities. I would be interested in seeing timings (or at least orders of magnitudes) for your experiments on this reasonably large model of section 4.1. I am not sure however that ICLR is the most appropriate conference for implementation papers.\n\n**Per-sample variance analysis** (section 4.1) is new as far as I can tell. It provides very interesting insights about the SNR of the gradients and curvature projected onto the eigenvectors of the GGN. I would have appreciated some more insights with more standard networks (e.g. ResNets)\n\n**Proposed adaptive damping scheme** The information about mini-batch variance is nicely exploited in the proposed adaptive damping scheme for second-order methods. As you rightfully notice, fully analyzing and benchmarking such an algorithm on an actual neural network would require a separate paper, which I would be looking forward to reading. A difficult problem that I can foresee is that even by estimating the GGN on a minibatch, the partial left singular vectors of $\\mathbf V$ are of dimension $D$ which can already be quite large.\n\n[1] https://arxiv.org/abs/1905.11675\n\n[2] https://arxiv.org/abs/1806.02958", "summary_of_the_paper": "This paper describes a way of leveraging the low-rank structure of the generalized Gauss-Newton (GGN) matrix, and a library that extends BackPACK's features in order to efficiently compute:\n - the spectrum (eigenvalues, eigenvectors) of the GGN\n - per sample directional derivatives and curvature of the GGN\n\nThey then demonstrate the library on a 900K parameters x 10 classes deep network on CIFAR-10.\nThey also propose a damping scheme for second-order that only have access to noisy estimates of the curvature.", "summary_of_the_review": "If it were a purely theory paper, I am not sure that the idea of leveraging the low-rank structure of the GGN makes for a novel enough contribution by itself to be published at ICLR.\n\nIt if were a pure implementation paper, I think ICLR would not be the most appropriate venue.\n\nHence my low rating, for a paper that is otherwise very pleasant to read.\n\nI think that the proposed adaptive damping scheme can however make for a nice follow-up.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "TDgykBndRNu", "reviewer": "Reviewer_9mCz", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. The paper proposes a method tailored to work efficiently on state-of-the-art auto differentiation tools and GPU hardware. Such tools are essential in better understanding various deep learning phenomena, improving optimization algorithms and in aiding practitioners with hyperparameter choices.\n2. The observations on the alignment of gradients with top eigendirections correlates well with recent results on deep neural network loss landscapes, and I find the discussion on the evolution of directional gradient and curvature SNR interesting. This direction can be very promising in designing practical second-order optimizers that scale to contemporary models and datasets.\n3. The directional damping scheme is an interesting idea, especially the adjustment of damping based on the stochastic uncertainty in a given eigendirection.\n\nWeaknesses:\n1. Scalability to practical settings: It is not clear whether the proposed method scales for contemporary architectures and large-scale datasets. Since the low-rank structure of the GGN has been investigated before by others (as the authors also pointed out), the main contribution of this paper is the compute/memory efficiency and scalability of the proposed tool. However, the experiments are performed on CIFAR-10 with a small, 6-layer neural network and it is not clear how it would scale to architectures such as ResNet and datasets such as ImageNet. In case the method does not work well in these scenarios, the applicability of the tool is limited.\n2. Overhead: In-depth study on the compute and memory overhead of the method would be valuable. For example statements such as 'However, the practical overhead is expected to be smaller' should be backed by concrete experiments. Even though the memory requirements for different accuracy settings are shown, it would be useful to see how it translates to wall-clock time overhead.\n3. Accuracy of the approximation: It is clear that an approximation of V is necessary to make the tool feasible in practical settings. However, the paper doesn't investigate the accuracy of the approximate spectra obtained from the method. Authors claim that the main contribution of the paper is delivering directional derivatives and GGN curvatures, but the accuracy of those quantities is not verified in any way in the paper. Providing some guarantees on the accuracy would be crucial, especially since the method is proposed as an analysis tool. For instance, taking a look at Figure 1 shows that the exact GGN and MC approximate spectra show similar characteristics, but how large is the difference in the top eigenspaces? Small errors in top eigendirections can greatly impact downstream applications where the quantities are used. An in-depth quantitative analysis of the cost savings-accuracy trade-off would be essential.\nFurthermore, I am concerned about the accuracy of the method when applied to datasets with larger number of classes. For instance, the CIFAR-100 results in Figure S.5 show that the MC approximate spectrum looks very different from the exact spectrum, even qualitatively. This can be a serious issue when scaling the method to datasets such as ImageNet.\n4. Damping: The directional damping method is interesting and is a neat application for the proposed tool, but 1) if it is meant only as a proof-of-concept, the discussion takes up a very significant portion of the paper (almost 2 pages) that could be used for supporting the main claims of the paper or 2) if it is meant as a main contribution and a practical method, then much more in-depth studies are needed to establish whether it improves damping in second-order methods.\n\nMinor: What does K denote exactly (first appearing in 4.1)? Is K=NC?", "summary_of_the_paper": "This paper highlights how the low-rank structure of the generalized Gauss-Newton (GGN) approximation of the Hessian can be used as a computationally efficient tool to study the loss landscape of deep neural networks. In particular, authors discuss methods to compute the full spectrum of the GGN and thus providing access to per-sample directional gradients and curvature approximation. Through the lens of the GGN spectrum, authors make observations on the geometry of the loss landscape and its evolution during training, and propose an adaptive damping technique for second-order optimizers that utilizes the GGN curvature information.", "summary_of_the_review": "The paper relies heavily on different forms of approximations to make the technique feasible, however  discussion on the accuracy of the approximated quantities is lacking, therefore it is difficult to judge how useful the obtained quantities are. Moreover, the scalability of the method to contemporary, practical architectures and datasets is not well-supported, thus the significance of the results is limited. Therefore, I recommend rejection of the paper in its current form. However, I believe that the paper has merit and some interesting contributions, and I am open to increasing my score if the authors address my concerns.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "OfQg0Ef2DWf", "reviewer": "Reviewer_VGMZ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\nBy leveraging the GGN’s low-rank structure, one can efficiently computate the eigenvalues, eigenvectors,  per-sample first- and second-order directional derivatives, and features. \n\nWeakness:\n1) The technical novelty of using low-rankness of GGN's seems a bit limited. It is suggested to highlight the difference as well as technical difficulty with existing works in exploiting the low-rank structure for fast computation of quantities like eigenvalues. \n2) Give more clear theoretical explanations of why the residual in Eq. (2)  is simply ignored. \n3) The theoretical analysis of why noise information improves the stability of second-order methods seems insufficient. ", "summary_of_the_paper": "This paper leverages the GGN’s low-rank structure, which allows for efficient computation of eigenvalues, eigenvectors,  per-sample first- and second-order directional derivatives, and parallel feature computation. The empirical performance is encouraging. ", "summary_of_the_review": "This paper proposes to use the GGN’s low-rank structure for fast and sound model learning. The empirical performance in promising. However, the technical novelty of using low-rankness of GGN's seems limited and the technical significance seems not sufficiently strong. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "JlmOIGjMY3", "reviewer": "Reviewer_GBwe", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1.\tIt is novel that the proposed curvature model VIVIT extracts full spectrum from the exact GGN matrix (on each mini-batch) and provides per-sample directional derivatives and curvatures, which may be of interest to future work on their own.\n2.\tThe proposed usage of VIVIT in second-order methods, i.e., the directional damping, is novel and deals with the difficulty of step size selection. \n3.\tOverall, the paper is well organized and clearly written. Thorough discussions on computational complexity and implementation details make this work practical.\n\nWeaknesses:\n1.\tWhy is the GGN matrix a good approximation of the true Hessian matrix? Does the GGN matrix well capture the top eigenvalues of the true Hessian? What is left in the residual matrix $R$? It would be better to have a discussion of the quality of such GGN approximation or demonstrate it in some experiment.\n2.\tIt would be better to compare the obtained eigenvalue spectrum (and eigen-vectors) with some of the existing curvature approximation methods in the experiment. Though these methods may not provide per-sample curvature estimation, it is still necessary to compare with them to show the quality and efficiency of VIVIT.\n3.\tIn Figure 3, it would be better to demonstrate how well the proposed directional damping balances convergence speed and stability. Currently in the left plot its performance seems to be not as good as the simple choice $\\delta=1$.\n4.\tIt would be better to distinguish between the mini-bath size and the training set size and formally state that VIVIT is for the underdetermined cases with $D > NC$.\n", "summary_of_the_paper": "This work proposes a curvature model VIVIT based on generalized Gauss-Newton (GGN) approximation for the training of neural networks with a convex loss function. The low-rank structure of VIVIT allows for efficient eigen-value decomposition, which also gives per-sample directional derivatives and curvatures. To further improve the efficiency, sampling within the mini-batch and among the coordinates of the prediction can be applied to trade off computational cost with accuracy. As an application example, VIVIT is used to provide noise-aware directional damping which improves the stability of second-order methods.", "summary_of_the_review": "The proposed curvature approximation method is novel and practical and appears to have the potential of being useful to future work. Though there are a few things to be improved, in general I find this work well written, and my current recommendation is marginally above the acceptance threshold.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "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": {}}]

Author rebuttal:

Meta-review: A method for efficient exact computation of the generalized Gauss-Newton matrix is given. Using this method the authors provide several empirical observations of first and second order statistics of neural networks during training. Additionally the authors use to tool to propose a new damping technique that some reviewers found particularly interesting. Reviewers noted that the low rank decomposition the authors provide is not new, and has been used in prior work, although the trick may not be widely known within the deep learning community. As such novelty is not a strength of the work, and reviewers suggested the authors could strengthen the work with a convincing demonstration that the method can be made to work at scale, as well as providing more detailed run time and memory comparisons with other approaches to calculating the GGN matrix. Although the authors agreed with reviewer suggestions, the paper was not updated during the rebuttal period. As such I recommend the authors resubmit with the proposed revisions.
Decision: Reject