Sketched Lanczos uncertainty score: a low-memory summary of the Fisher information
Authors: Marco Miani
Lorenzo Beretta
Søren Hauberg
Venue: NeurIPS 2024 poster (2024)
Keywords: Sketching
Uncertainty
Lanczos
Laplace
Primary area: probabilistic_methods
TL;DR: We propose a memory-efficient and provably-good approximation of an enstablished uncertainty score

Abstract: Current uncertainty quantification is memory and compute expensive, which hinders practical uptake. To counter, we develop Sketched Lanczos Uncertainty (SLU): an architecture-agnostic uncertainty score that can be applied to pre-trained neural networks with minimal overhead. Importantly, the memory use of SLU only grows logarithmically with the number of model parameters. We combine Lanczos' algorithm with dimensionality reduction techniques to compute a sketch of the leading eigenvectors of a matrix. Applying this novel algorithm to the Fisher information matrix yields a cheap and reliable uncertainty score. Empirically, SLU yields well-calibrated uncertainties, reliably detects out-of-distribution examples, and consistently outperforms existing methods in the low-memory regime.

Sketched Lanczos uncertainty score: a low-memory summary of the Fisher information
Marco Miani"
Lorenzo Beretta"
Technical University of Denmark mmia@dtu.dk
Unaffiliated
Jorenzooberetta@@al..coom
Soren Hauberg
Technical University of Denmark sohau8dtu.de dk
Abstract
Current uncertainty quantification is memory and compute expensive, which hin- ders practical uptake. To counter, we develop SKETCHED LANCZOS UNCER- TAINTY (SLU): architecture-agnostic uncertainty score that be applied pre-trained neural networks with minimal overhead. Importantly, the memory use of SLU only grows logarithmically with the number model parameters. We com- bine Lanczos' algorithm with dimensionality reduction techniques to compute a sketch of the leading eigenvectors of matrix. Applying this novel algorithm to the Fisher information matrix yields a cheap and reliable uncertainty score. Empirically, SLU yields well-calibrated uncertainties, reliably detects tiitof-dditriuttion exam- ples, and consistently outperforms existing methods in the low-memory regime.
Introduction
The best- ressfperforning uncertainty quantification methods share the same problem: scaling. Practically this prevents their use for deep neural networks with high parameter counts. Perhaps, the simplest way of defining such a score is to independently train several models, perform inference, and check how consistent predictions [Lakshminarayanan et al., 2017] notably introduces a multiplicative overhead equal to the ensemble size. Current approaches aim reduce the growth in training time costs by quantifying uncertainty through local information of a single pre-trained model. This approach has shown some success for methods like Laplace's ' approximation [MacKay, 1992, Immer al., 2021, Khan et al., 2019], SWAG [Maddox et al., 2019], SCOD [Sharma et al., 2021] or Local Ensembles [Madras et al., 2019]. They avoid the need to re-train but still have impractical memory needs.
across models. The overhead of the resulting 'Deep Ensemble'
popular approach to characterizing local information is the empirical Fisher information matrix, which essentially coincides with the Generalized Gauss-Newton (GGN) matrix [Kunstner et al., 2019]. Unfortunately, for a parameter model, the GGN a x p matrix, yielding such high memory costs that it cannot be instantiated for anything but the simplest models. The GGN is, thus, mostly explored through approximations, e.g. block-diagonal [Botev et al., 2017], frrtoiiee-factorizzed [Ritter et al., 2018a, Lee al., 2020, Martens and Grosse, 2015] or even diagonal [Ritter al., 2018b, Miani et al., 2022]. An alternative heuristic is to only assign uncertainties to a subset of the model parameters [Daxberger et al., 2021b, Kristiadi al., 2020], e.g. the last layer.
Instead, we approximate the GGN with a low-rank matrix. rank-k approximation of the GGN can be computed using Lanezos algorithm [Madras al., 2019, Daxberger et al., 2021a] or truncated
"Equal contribution
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

singular value decomposition (SVD) [Sharma et al., 2021]. These approaches deliver promising uncertainty scores but are limited by their memory footprint. Indeed all aforementioned techniques require k p memory. Models with high parameter counts are, thus, reduced to only being able to consider very small approximate ranks.
In this work, we design novel algorithm to compute the local ensemble uncertainty estimation score introduced by Madras et al. [2019], reintroduced in Section 2.1. Our algorithm substantially more memory-efficient than the previous one both in theory and practice, thus circumventing the main bottleneck of vanilla Lanezos and randomized SVD (Figure 1). To that end, we employ sketching dimensionality reduction probability error in some matrix- vector operations for lower memory usage. Combining the latter with the Lanczos algorithm (reintroduced in Section 2.2) results in the novel SKETCHED LANCZOS.
reduuctnn techniques, reintroduced in Section 2.3, that trade a small-with-hipe with-high-
This essentially drops the memory consumption from (pp)) to = in exchange for a provably bounded error independently on the number of parameters p (up to log-terms).
Applying this algorithm in the deep neural networks settings allows to scale up the approach from Madras et al. [2019] and obtain a better uncertainty score for a fixed memory budget.
Our contribution is twofold: (1) we prove that orthogonalization approxi- mately commutes with sketching in Section 3, which makes possible to sketch Lanezos vectors the fly and orthogonaliie them post-hoc, with significant memory savings; (2) empirically show that, in the low- memory-budget regime, the disad- vantage of introducing noise through sketching is outweighed by a higher- rank approximation, thus performing better than baselines when the same amount of memory is used.
0.68
Randomized SVD
Vanila Lanczos
0.70
Sketched Lancaos 5=100000
Sketched Lanczos s=10000
0.72
AUROC
0.74
0.76
100
20
25
30
Memory cost in number of NNs
Figure I: Ool) detection performance (<) on ResNet.
2 Background
Let fa Rd + R' denote a neural network with parameter 9 E RP, or equivalently f x + R. Let (x) = Ve (z))e== E RxxP be its Jacobian with respect to the parameters, evaluated at a datapoint x E Rd. Given a training dataset D {(,, y:)ri=i,.... and loss function L(() E EoWeED fyy, f(x 6), the Generalized Gauss-Newton matrix (GGN) is defined as
Go Σ Jo( H((z.)
fo(n,, ((nls((() E Rxxt is the Hessian of the loss with respect the neural network output. We reduce the notational load by stacking the per-datum Jacobians into Jg = [=( : Jo(x))))) E 1R= and similarly for the Hessians, and write the GGN matrix as Go = JJ HJ.. For extended derivations and connections with the Fisher matrix we refer to the excellent review by Kunstner al. [2019]. In the following, we assume access pre-trained model with parameter 0* and omit the dependency of G on 0*
where H(r:)
2
Computationally we emphasize that Jacobian-vector products can be performed efficiently when is a deep NN. Consequently, the GGN-vector product has twice the cost of gradient backpropagation. at least for common choices of like MSE cross-entropy [Khan and Rue, 2021].
2.1 Uncertainty score
We measure the uncertainty at datapoint x as the variance of the prediction fa(x:) with respect to a distribution over parameter 0 defined at training time and independently of zz This general scheme has received significant attention. For example, Deep Ensemble [lakssmmiarryannan et al., 2017] uses sum of delta distribution supported independently trained models, while methods that only train

---

single network 8 generally use a Gaussian (000"", .M with covariance M E RPxp, In the latter case, first-order approximation the prediction variance is given by M-norm of the Jacobian
VAR = VAR0-Ni010-,,0 [f (=)] = TR(Jø- (x) M - [x)
(2)
where (x) = fo(x) + (o- (6" 0) is a linearization of >> fo( around 0".
The GGN matrix (or empirical Fisher; Kunstner et al. [2019]) is notably connected to uncertainty measures and, more specifically, to the choice of the matrix M. Different theoretical reasoning leads to different choices and we focus two of them:
Meig (G + aTTp))
Maseig = ITa:
where 1g is the projection onto the non-zero eigenvectors of G and 0 is constant.
Madras et al. [2019] justify Maseig through small perturbation along zero-curvature directions. Immer al. [2021] justify Meig in the Bayesian setting where is interpreted prior precision. We do not question these score derivations and refer to the original works, but we highlight their similarity. Given orthonormal eigen- decomposition of G = E, Nua;v, we see that
Maig = Σ A + 4iN
Mnocig Σ E
(4)
Thus both covariances are higher in the directions zero-eigenvalues, and the hyperparameter a controls how many eigenvectors are relevant in Meig-
Practical choices. The matrix G too big to even be stored in memory and approximations are required, commonly in way that allows access to either the inverse or the projection. A variety of techniques are introduced like diagonal, block diagonal, and block KFAC which also allow for easy access to the inverse. Another line of work, like SWAG [Maddox et al., 2019], directly tries to find an approximation of the covariance M based on stochastic gradient descent trajectories. Alternatively, low-rank approximations use the eigen- decomposition relative to the top & eigenvalues, which allows direct access to both inverse and projection.
10c
10a
Is low-rank a good idea? The spectrum of the GGN has been empirically shown to decay exponentially [Sagun al.. 2017, Papyan, 2018, Ghorbani al.. 2019] (see Figure 2). We investigate this phenomenon further in Appendix C.I with an ablation over Lanezos hyperpa- rameters. This fast decay implies that the quality of a rank-k approximation of G improves exponentially w.r.t. k if we measure it with operator or Frobenius norm, thus supporting the choice of low-rank approximation. Moreover, in the overparametrized setting p >>> ní, the rank the GGN is by construction at most rtt, which
Eigenvalue
10
20a
10?
MLP on MNIST
10a
LeNet on FMNIST
10a
ResNet on CIFAR-10
10a
10a
10a
10a
10*
Index
Figure 2: GGN eigenvalues exponential decay. Average and standard deviation over 5 seeds. Details are in Appendix C.I. closely linked with functional reparametrizations [Roy et al., 2024].
The low-rank approach has been applied intensively [Madras al., 2019, Daxberger et al., 202 Sharma et al., 2021] with success, although always limited by memory footprint of pk. Madras et al. [2019] argue favor of a not-too-high i also from a numerical perspective, as using the "small" eigenvectors appears sensitive to noise and consequently is not robust.
2.2 The Lanczos algorithm
The Lanczos algorithm is an iterative method for tridiagonalizinng a symmetric matrix G. If stopped at iteration k. Lanczos returns a oothonoml matrix V = [Vi]... ....... Vi] E xx and a tridiagonal matrix T E k such that VT GV = T. The range space of V corresponds to the Krylov subspace KA+ span(v, Gv...., [.) where V1 is randomly chosen vector. Provably, Kr
"To be precise, Madras et [2019] uses Hessian rather than the GGN, although their reasoning for discarding the eigenvalues applies to both matrices. Thus, while the score with Maseig is technically novel, it a natural connection between Laplace approximations and local ensembles. Also note that some work uses the Hessian in the eigenvalues setting [MacKay, 2003] despite this requires ad-hoc care for negative values.

---

approximates the eigenspace spanned by the top-k eigenvectors of G, i.e. those corresponding to the eigenvalues of largest values [Meurant, 2006]. Thus, VTVT approximates the projection of G onto its top-k eigenspace. Notice that projecting G onto its top-k eigenspace yields the best rank-k approximation of G' under any unitarily-invariant norm [Mirsky, 1960]. Once the decomposition G R VTVT is available, we can retrieve an approximation to the top-k eigenpairs of G by diagonalizing T into T = W A which can be done efficiently for tridiagonal matrices [Dhillon, 1997]. It has both practically and theoretically been found that this eigenpairs' approximation is very good. We point the reader to Meurant [2006] and Cullum and Willoughby [2002] for a comprehensive survey on this topic.
The benefits of Lanczos. Lanczos has two features that make it particularly appealing. First, Lanczos does not need explicit access to the input matrix G. but only access to an implementation of G-vector product u + Gu. Second, Lanczos uses a small working space: only 3p floating point numbers, where the input matrix is p x p. Indeed, we can think of Lanezos as releasing its output in streaming and only storing a small state consisting of the last three vectors Vi-1, V; and V
The downsides of Lanczos. Unfortunately, the implementation of Lanczos described above is prone to numerical instability, causing Vi... Vi to be far from orthogonal. A careful analysis of the rounding errors causing this pathology was carried out by Paige [1971, 1976, 1980]. To counteract, a standard technique is to re-orthogonalize Ve+1 against all (Vi at each iteration. This technique has been employed to compute the low-rank approximation of huge sparse matrices [Simon and Zha, 2000], as well as by Madras et al. [2019] to compute an approximation to the top-k eigenvectors. Unfortunately, this version of Lanczos loses one of the two benefits described above, in that must store a larger state consisting of the entire matrix V. Therefore, we dub this version of the algorithm hi-memory Lanczos and the memory- version described above low- mowmmemory Lanezos. See Appendix C for a comprehensive discussion on these two versions.
hoc orthogonalization Lanczos. Alternatively, instead of re-orthogonalizing at every step as in hi-memory Lanczos, we can run low-memory Lanczos, store all the vectors, and orthogonalize all together at the end. Based on the observations of Paige [1980], we expect that orthogonalizing the output of low-memory Lanczos post-hoc should yield an orthonormal basis that approximately spans the top-k eigenspace, similar hi- mi-memory Lanezos. This post-hoc version of Lanczos is however insufficient. It avoids the cost of orthogonalizing at every iteration but still requires storing the vectors, thus losing again the benefit of memory requirement. Or at least does unless we find an efficient way to store the vectors.
2.3 Sketching
Sketching is key technique in randomized numerical linear algebra [Martinsson and Tropp, 2020] to reduce memory requirements. Specifically, sketching embeds high dimensional vectors from Iº into a lower-dimensional space R2, such that the expected norm error of vector dot-products is bounded, and, as a result, also the score in Equation 2. Here we give concise introduction to this technique.
Definition 2.1 (Subspace embedding). Fix > 0. A (1 + E) E2-subspace embedding for the column space of an x k matrix U is a matrix S for which for all E R
SU = (1 + $) ()|lu
(5)
The goal is to design an oblivious subspace embed- ding, that is random matrix S such that, for any matrix U, S is a subspace embedding for U with sufficiently high probability. In our method, we use a Subsampled Randomized Fourier Transform (SRFT) to achieve this goal [Ailon and Chazelle, 2009]. A SRFT is a s X p matrix defined by the product DH where D is diagonal matrix where each diagonal entry is an independent Rademacher random variable, H is the discrete Fourier transform, and P is diagonal matrix where random di- agonal entries are set to one and every other entry is set to zero. Thanks to the Fast Fourier Transform algorithm, SRFT can be evaluated in O(p log p) time, and its memory footprint is only p + 8.
Time
Memory
Dense JL
O(p²))
p²
Sparse JL.
(sp)
p.es
SRFT
Opplogr)
p P
Table 1: Sketch complexities comparison.
Here w is such that the current best matrix- multiplication algorithm runs in time n².
The following theorem shows that, as long as the sketch size s big enough, SRFT an oblivious subspace embedding with high probability.

---

Theorem 2.2 (Essentially, Theorem 7 in Woodruff et al. [2014]). For any p x k matrix U, SRFT (1 + E)-subspace embedding for the column space of U with probability as long as s = [((k + log(k/
We stress that, although several other random projections work subspace embeddings, our choice is not incidental. Indeed other sketches, including the Sparse JL transform [Kane and Nelson, 2014, Nelson and Nguyên, 2013] or the Dense JL transform (Theorem 4. Woodruff et al. [2014]), theoretically have larger memory footprint or a worse trade-off between and k. as clarified in Table 1. From such a comparison, it clear that SRFT is best if our goal is to minimize memory footprint. At the same time, evaluation time is still quasilinear.
3 Method
We now develop the novel SKETCHED LANCZOS algorithm by combining the 'vanilla' Lanezos algorithm (Section 2.2) with sketching (Section 2.3). Pseudo-code is presented in Algorithm 1. Next, we apply this algorithm in the uncertainty quantification setting and compute an approximation of the score in Equation 2 due to Madras et al. [2019]. Our motivation is that given fixed memory budget, the much lower memory footprint induced by sketching allows for a higher-rank approximation of G.
3.1 Sketched Lanczos
We find the best way to explain our algorithm is to first explain a didactic variant of it, where sketching and orthogonalization happen in reverse order.
Running low-memory Lanezos for k iterations on p X p matrix iteratively constructs the columns of a p X k matrix V. Then, post-hoc, we re-orthogonalize the columns of V in matrix U E ga*k Such a matrix is expensive to store due to the value p, but we sample a SRFT sketch matrix S E Rsxp, we can then store a sketched version SU E Raxk, saving memory as long as 8 < p. In other words, this is post-hoc orthogonalization Lanezos with a sketching at the end.
We observe that sketching the columns of U is sufficient to E-preserve the norm of matrix-vector products, with high probability. In particular, the following lemma holds (proof in Appendix A). Lemma 3.1 (Sketching low-rank matrices). Fix O < 5, < 1/2 and sample a random x p SRFT matrix S. Then, for any E IR" and any matrix U E Bexk with ||0|22, ||/||2 = (11) we have
Pr (I(SSU) = T 2|l2 + e) - 5.
(6)
S
as long as = 22ke- -2, log log(k/)))
This algorithm may initially seem appealing since we can compute tight approximation of |0T vill by paying only s le in memory (plus the neglectable cost of storing S). However, as an intermediate step of such an algorithm, we still need to construct the matrix U, paying p x k in memory. Indeed, we defined U as matrix whose columns are an orthonormal basis of the column space of V and we would like to avoid storing V explicitly and rather sketch each column V; on the fly, without ever paying p x memory. This requires swapping the order of orthogonalization and sketching.
This motivates us to prove that if we orthonormalize the columns of SV and apply the same orthonor- malization steps the columns of V. then we obtain an approximately orthonormal basis. Essentially, this means that sketching and orthogonalization approximately commute. As a consequence, we can use a matrix whose columns are an orthonormal basis of the column space of SV proxy for SU while incurring small error. Formally, the following holds (proof in Appendix A).
Lemma 3.2 (Orthogonalizing the sketch). Fix O < E,8 < 1/2 and sample a random 8 X p SRFT (2kk=2 log log(k/ (5)) the following holds with probability 1 - 8.
matrix S. As long
Given any p x full-rank matrix V, decompose V U.R and SV = UsRs so that U E Rpxk Us Raxk and both U and Ug have orthonormal columns. For any unit-norm U E Bd we have
|| (Sv)ll2 = |
01|2 =e.
In Lemma 3.1, we proved that given a matrix U with orthonormal columns we can store SU instead of U to compute + T|Ule while incurring a small error. However, in our case, we do
5

---

not have explicit access to U. Indeed, we abstractly define U as matrix whose columns are an orthonormal basis of the column space of V. but we only compute Uş as a matrix whose columns are an orthonormal basis of the column space of SV, without ever paying p k memory. Lemma 3.2 implies that the resulting error controlled.
Algorithm lists the pseudocode of our new algorithm: SKETCHED LANCZOS.
Algorithm SKETCHED LANCZOS
1: Input: Rank sketch matrix SER*Xp, matrix-vector product function v + Gv for GeRPXP,
2: Initialize E IRP as uniformly random unit-norm vector.
3: for in 1, .,...k. do
4: LANCZOSITERATION(
Gt)
(glossing over the tridiagonal detail)
5: Sketch and store uy - Sv;
6: end for
7: Construct the matrix Vs = [of..... u E Raxk
8: Orthogonalize the columns of V and return Us E R
Preconditioned SKETCHED LANCZOS. We empirically noticed that low-memory Lanczos' stability quite dependent on the conditioning number of the considered matrix. From this observation, we propose slight modification of SKETCHED LANCZOS that trades some memory consumption for numerical stability.
The idea is simple, we first run hi-memory Lanczos for kn iterations, obtaining approximation of the top-ko eigenspectrum Uo Rexko .g E Xka, Then we define a new matrix-vector product
G = (G UoAoU% y
(8)
and run SKETCHED LANCZOS for kn iterations this new, better-conditioned, matrix G. This results in a Us E R= with sketched orthogonal columns. With = k + kn, the simple concatenation [SU]Uss] E (Ro+H)))* Xxs is sketched orthogonal k-dimensional base of the top-k eigenspace of G, analogous non-preconditioned SKETCHED LANCZOS. The extra stability comes at memory cost of ku p. thus preventing ky from being too large.
3.2 Sketched Lanczos Uncertainty score (SL.U)
The uncertainty score in Equation 2 is computed by first approximating the Generalized Gauss- Newton matrix G. The approach of constructing an orthonormal basis U Bpxk of the top-k eigenvectors of G with relative eigenvalues A, leads to the low-rank approximation G z UAUT. This step is done, for example, by Madras al. [2019] through hi- hi-memory Lanezos and by Sharma et al. [2021] ] through truncated randomized SVD. In this step, we employ our novel SKETCHED LANCZOS. Similar to Madras al. [2019], we focus on the score with Moosig and thus we neglect the eigenvalues.
Having access to U, we can compute the score for test datapoint æ E Rd as
[AR[fe(z)] s TR (Ja- (x) (1- (1-UU0 UUT) Jo (z) = Je (z) (x)U
(9)
which clarifies that computing ||aa- (z) is the challenging bit retrieve the score in Equation 2. Note that Jo- (x:) || can be computed exactly with t Jacobian-vector products.
Computing the uncertainty score through sketching. Employing the novel SKETCHED LANCZOS algorithm we can E E-approximate the score in Equation 9, with only minor modifications. Running the algorithm for iterations returns matrix Us Ra which recall is the orthogonalization of SV where V E Roxk are the column vectors iteratively computed by Lanczos.
Having access to Us,
then compute the score for test datapoint R2d
SLU(x) [Jo (1) - |03 (SJ (z) )
(10)
where parentheses indicate the order in which computations should performed: first a sketch of Jg- (xr) is computed, and then it is multiplied by U3. Algorithm summarizes the pipeline.
Approximation quality. Recall that the Jacobian J (1) is X matrix, where is the output size of the neural network. A slight extension of Lemma 3.2 (formalized in Lemma A. implics that the

---

Algorithm 2 SKETCHED LANCZOS Uncertainty score (SLU)
1: Input: Observed data D, trained MAP parameter 0* E R², approximation rank k sketch size 8.
2: Initialize SRFT sketch matrix S
3: Initialize GGN-vector product + Gv = - Jo- (z,) H (24 Jo (x.)e
4: Us f
SKETCHED LANCZOS(K, S, + Ge)
5: At query time, for a test point x return || (x)] |U3 (SJ (1)
score in Equation 9 is guaranteed to be well-approximated by the score in Equation 10 up to factor 1 + with probability 8 as long as the sketch size is big enough s = Okkls log log log(k1/6)) Neglecting the log terms to develop some intuition, we can think of the sketch size to be R kis thus resulting an orthogonal matrix Ug of size Ra kls- x k; which also correspond to the memory requirement. From an alternative view, we can expect the error induced by the sketching to scale as R Vkt/s, naturally implying that a larger & will have a larger error, and larger sketch sizes will have lower error. Importantly, the sketch size s (and consequently the memory consumption and the error bound) depends only logarithmically ratio '/p clearly improves a lot for bigger architectures.
the number of parameters p, while the memory-
Memory footprint. The memory footprint of our algorithm is at most 4p + s(k: + floating point numbers. Indeed, the SRFT sketch matrix uses p + numbers to store S, whereas memmoyrry Lanczos stores at most 3 size-p vectors at time. Finally, Us is 8 x k matrix. At query time, we only need to store S and Us. resulting in a memory footprint of p + s(k: + 1). Therefore, our method is significantly less memory-intensive than the methods of Madras et al. [2019], Sharma et al. [2021], and all other low-rank Laplace baselines, that use (2kk)) memory.
Time footprint. The time requirement is comparable to Vanilla Lanczos. We need k SRFT sketch-vector products and each takes Opplog p) time, while the orthogonalization of SV R through QR decomposition takes Oppk²) time. Both Vanilla and Sketched algorithm performs GGN-vector products and each takes ((m) time, where n is the size of the dataset, and that is expected to dominate the overall O (pk((ogp + k + n))- Query time is also fast: sketching, Jacobian- vector product and Ug-vector product respectively add up to O(tp(logp + 1) + tsk).
Note that the linear scaling with out- put dimension can slow down infer- ence for generative models. We refer to Immer et al. [2023] for the effect of considering subset on dataset size (or on output dimension t).
Memory
Time
Preprocessing Query p+ +1)
4p s(k +1) Olpk(log p + k n))
Ottp(log p 1) + tssk)
Table 2: Recall that through the whole paper is number of parameters, n is dataset size, t output dimensionality, is rank approximation and s is sketch size.
4 Related work
Modern deep neural networks tend to be more overconfident than their predecessors [Guo al., 2017]. This motivated intensive research on uncertainty estimation. Here we survey the most relevant work.
Perhaps, the simplest technique to estimate uncertainty over classification task is to use the softmax probabilities output by the model [Hendrycks and Gimpel, 2016). more sophisticated approach, combine softmax with temperature scaling (also Platt scaling) [Liang et al., 2017, Guo et al., 2017] 7]. The main benefit of these techniques is their simplicity: they do not require any computation besides inference. However, they do not extend to regression and do not make use of higher-order information. Moreover, this type of score relies on the extrapolation capabilities of neural networks since they use predictions made far away from the training data. Thus, their poor performance is not surprising.
To alleviate this issue, an immense family of methods has been deployed, all sharing the same common idea of using the predictions of more than one model, either explicitly or implicitly. A complete review of these methods unrealistic, but the most established includes Variational inference [Graves, 201 1, Hinton and Van Camp, 1993, Liu and Wang, 2016], Deep ensembles [Laassminnrayannan et al., 2017], Monte Carlo dropout [Gal and Ghahramani, 2016, Kingma et al., 2015] and Bayes by Backprop [Blundell et al., 2015].
7

---

More closely related to us, the two uncertainty quantification scores introduced in Equation 2 with covariances Mai and Maseiy (Equation 3) have been already derived from Bayesian (with Laplace's 's approximation) and frequentist (with local perturbations) notions of underspecification, respectively:
Laplace's approximation. By interpreting the loss function as unnormalized Bayesian log- posterior distribution over the model parameters and performing a second-order Taylor expansion, Laplace's 's approximation [MacKay, 1992] results in a Gaussian approximate posterior whose covari- ance matrix is the loss Hessian. The linearized Laplace approximation [Immer et al., 2021, Khan et al., 2019] further linearize fe at a chosen weight 8", i.e. fo(x) = fo (x) + Jø (z)(B 8*). In this setting the posterior is exactly Gaussian and the covariance is exactly Meig.
Local perturbations. A different, frequentist, family of methods studies the change in optimal parameter values induced by change in observed data. A consequence is that the parameter directions corresponding to functional invariance the training set are the best candidates for Ool) detection. This was directly formalized by Madras et al. [2019] which derives the score with covariance Mnocig. which they call local ensemble. A similar objective is approximated by Resampling Under Uncertainty (RUE, Schulam and Saria [2019]) perturbing the training data via influence functions, and by Stochastic Weight Averaging Gaussian (SWAG, Maddox et al. [2019]) by following stochastic gradient descent trajectories.
Sketching in the deep neural networks literature. Sketching techniques not new to the deep learning community. Indeed several works used randomized SVD [Halko et al., 2011], which is a popular algorithm [Tropp and Webber, 2023] that leverages sketch matrices reduce dimensionality and compute an approximate truncated SVD faster and with fewer passes over the original matrix. was used by Antorán al. [2023] to compute preconditioner for conjugate gradient and, similarly, by Mishkin et al. [2018) 88] to extend Variational Online Gauss-Newton (VOGN) training [Khan et al., 2018]. More related to us, Sketching Curvature for OoD Detection (SCOD, Sharma et al. [2021]) uses Randomized SVD to compute exactly the score in Equation 2 with Meig. thus serving as a baseline with an alternative to Lanczos. We compare to it more extensively in Appendix B.
To the best of our knowledge no other work in uncertainty estimation for deep neural networks uses sketching directly to reduce the size of the data structure used for uncertainty estimation. Nonetheless, a recent line of work in numerical linear algebra studies how to apply sketching techniques to Kryloy methods, like Lanczos or Arnoldi [Balabanov and Grigori, 2022, Timsit et al., 2023, Simoncini and Wang, 2024, Güttel and Schweitzer, 2023]. We believe sketching is a promising technique to be applied in uncertainty estimation and, more broadly, in Bayesian deep learning. Indeed, all the techniques based on approximating the GGN could benefit from dimensionality reduction.
5 Experiments
With a focus on memory budget, we benchmark our method against a series of methods, models, and datasets. The code for both training and testing is implemented in JAX [Bradbury et al., 2018) 8] and it publicly available". Details, hyperparameters and more experiments can be found in Appendix D.
To evaluate the uncertainty score we measure the performance of out-of-distribttion (OoD) detection and report the Area Under Receiver Operator Curve (AUROC). We choose models with increasing com- plexity and number of parameters: MLP, LeNet, ResNet, VistioeAte and Swin Transformer architectures, with the number of parameters ranging from 15K to 200M. We train such models on 5 different datasets: MNIST [Lecun et al., 1998], FASHIONMNISS [Xiao et al., 2017], CIFAR- 10 (Krizhevsky et al., 2009], CELEBA [Liu et al., 2015] and IMAGENET [Deng al., 2009]. We test the score performance on series of OoD datasets, including rotations and corruptions [Hendrycks, 2019] of ID datasets, as well as SVHN [Netzer et al., 201 and FOOD101 [Bossard et al., 2014]. For CELEBA and IMAGENET we hold out some classes from training and use them as OoD datasets.
We compare to the most relevant methods in literature: Linearized Laplace Approximation with low-rank structure (LLAA) [Immer et al., 2021] and Local Ensemble (I.F) are the most similar to us. We also consider Laplace with diagonal structure (LLA-D) and Local Ensemble Hessian variant (LE-H) [Madras et al., 2019]. Another approach using randomized SVD instead of Lanczos is Sketching Curva- ture for OoD Detection (SCOD) [Sharma et al., 2021], which also serves as Lanezos baseline. Lastly, we include SWAG [Maddox et al., 2019] and Deep Ensemble (DE) [Lakshminarayanan et al., 2017].
8

---

0.22
0.35
01.00
0.53
AUMOC
0.94
Bandmrbea DVD
Vordl Lenott
Sockihed Lamsos 5-50000e
Skattred
Suskted Lamoll 20000
0,35
Sestrne LATIDD 11200303
0.63
Statihid 5130
0.7
Stokthed 5-100
207
231
10'
105
10
10"
101
Namory cost in numumbr of MNk
Memory cost In nunumber of MNa
Hemory cost number of Mia
Figure 3: Sketch sizes comparison for: LeNet = 40K on FASHIONMNIST MNIST (left), ResNett p 300K on CIFAR-10 vs CIFAR-corrupte with defocus blur (center), and VieualAttentiooNett
p 4M on CELEBA vs FOOD101 (right). The lower the ratio */p, the stronger the memory efficiency.
Effect of different sketch sizes. We expect the error induced by the sketching to scale as E 2 V k/s. thus a larger& k will have larger error, and larger sketch sizes will have lower error, independently on number of parameters up to log-terms. On the other hand, a larger parameter count will have a better memory-savingg-ree ratio 4/p, leading to an advantage for bigger architectures as shown in Figure 3.
model
MLP p 16K
LeNet p = 40K
ResNet 200K
ID data
MNIST ..
FASHIONMNIST
CIFAR 10
OnD data
FASHIONNIIST
KMNIST
Roiation (avg)
MNIST
Rotation (avg)
SVHN
CIFAR-I00 100
Corrupt (avg)
(05)
0.26 0.02
0.42 +
0.59 0.02
0,94 0.01
0.74 0.03
0.76 0.05
0.54 0.02
0.57 0.04
LLA
0.27 + 0.03
0,30 + 0.03
0.49 + 0.01
0.80 0.03
0.70 + 0.03
0.67 = 0.07
0.54 + 0.02
0.57 + 0.05
0,94 0.03
0,98 =
0.73 0.01
0.68 0.07
0.61 + 0.05
0.55 0.10
0.52 0.02
0.52 0.04
LE
0.27 = 0.03
0,30 + 0.03
0.49 + 0.01
0.80 0.03
0.70 + 0.03
0.67 = 0.07
0.54 +: 0.02
0.57 0.05
0.27 1 0.03
0,30 1: 0.03
0.49 1: 0.01
0,80 0.03
0,70 1: 0.03
0.66 0.07
0.54 0.02
0.57 0.05
SCOD
0.27 - 0.03
0,31 0.03
0.51 0.01
0.84 0.02
0.71 0.03
0.68 0.07
0.54 0.02
0.58 0.04
SWAG
0.29 0.05
0.19 1: 0.02
0.41 0.03
0.75 0.02
0,70 0.04
0.48 0.11
0.49
0.01
0.52 0.06
DE
0.94 0.04
0,96 1 0.00
0.71 1 0.02
0.92 0.01
0.79 1 0.02
0.46
0.02
0.51 1: 0.00
0.50 0.01
model
VisualAAtoniionNattppp 1M
SWIN p= 200M
ID data
IMAGENET u.
OoD data
FOOD-101
Huld-out (avg)
Castle
Hlaingo
Lighier
Odemeter
Parachate
Pincupple
Triceratops
Volcano
SEL (us)
0.72
0.37
0.56
0.69
LLA
0.93 1 0.001
0.67 1 0.02
0.49
0.56
0.59
0.41
0.56
0.45
0.67
0.78
LLA-D
0.52
0.54
0,48
0.68
LE
0.93 = 0.001
0.67 0.02
0.51
0.58
0.62
0.41
0.59
0.47
0.67
0.80
0.91 0.002
0.04
0.50
0.57
0.60
0.41
0.57
0.47
0.67
0.80
SCOD
0.94 1: 0.00
0.68 0.022
ma
ma
ma
ma
na
ma
na
na
SWAG
0.69 1: 0.04
0.46 0.04
0.46
0.54
0.55
0.52
0.44
0.36
0.64
0.72
DE
0,88 = 0.02
0.63 0.02
na
na
na
na
na
na
na.
Table 3: AUROC scores of SKETCHED LANCZOS Uncertainty vs baselines with memory budget of 3p. Results for all OoD datasets are illustrated more extensively in Figure 4. Mean values and standard deviations for each table block obtained over 10, 10, 3, independently trained models, respectively.
Summary of the experiments. For most of the ID-OoD dataset pairs we tested, our SKETCHED LANCZOS Uncertainty outperforms the baselines, as shown in Table and more extensively in Figure 4 where fix the memory budget to be 3p. Deep Ensemble performs very well in the small architecture but progressively deteriorates for bigger parameter sizes. SWAG outperforms the other methods some specific choices of CIFAR- 10 corruptions, but we found this method to be extremely dependent on the choice of hyperparameters. SCOD is also a strong baseline in some settings, but highlight that it requires instantiating the full Jacobian with an actual memory requirement of tp. These memory requirements make SCOD inapplicable to ImageNet. In this setting, given the significant training time, also DEEP ENSEMBLE becomes not applicable.
The budget of 3p is an arbitrary choice, but the results are consistent with different values. More experiments, including 10p memory budget setting, a study on the effect of preconditioning, and synthetic-data ablation on the trade-off sketch size vs low rank, are presented in Appendix D.3.
Conclusion
We have introduced SKETCHED LANCZOS, a powerful memory-effiiient technique to compute approximate matrix eigendecompoosttions. We take a first step exploiting this technique showing that sketching the top eigenvectors of the Generalized Gauss-Newton matrix leads to high-quality

---

9.5
0.90
6.7
AUROC
0.6
0.73
SEL
LLA/LE/LEh
9.70
LE
SCOD
LLA-
9.63
SHAG
FMMASTT
Rotetto 180
30
20
135
Rota
Roo
Rob
Roseree
Rutesto
Rotecte
Rotaree
Roseteo
Rotweedd
Roteeed
(a) MLP p
15K trained MNIST
(b) LeNet p 40K trained on FASHIONMNIST
SLU
0.75
LLA/LE/LEN
LLA-d
0.70
SWAG
AUROC
0.65
0.50
0.45
SYHN
CIPA-1000
Brightmes
Defocuus blur
Bastic transf
Frost
Gaussinn blar
Glass Blur
Impuire noise
Jogg compress
Motion blar
Fixelate
Saturate
Snow
Spatter
Zoom blur
(c) ResNet p
300K trained on C1FAR- 10
+ StU L
0.8
SWAG
AUSDE
AUROC
+ SLU LLA
0.6
0.5
0.4
LE-h
1000-101
Baid
Eyeglasses only
Mustache only
Careanara only
Castle only
Pariiggs only
Ligiter only
Menu
Detameter only
Parachutee only
Pineapple only
Ticeratopn only
Iesicano odi
(d) VisualAttention p 4M trained on CELEBA
(c) SWIN p = 200M trained on IMAGENET
Figure 4: AUROC scores of SKETCHED LANCZOS Uncertainty vs baselines with memory budget 3p. SLU outperforms the baselines on several choices of ID (4a, 4b, 4c, 4d, 4e) and OoD (x-axis) datasets pairs. Dashed lines are for improved visualization only; see Table 3 for values and standard deviations. Plots 4a, 4b, 4c, 4d, 4e are averaged respectively over 10, 10, 5, 3, independently trained models.
scalable uncertainty measure. We empirically show the superiority of the SKETCHED LANCZOS Uncertainty score (SLU) among variety of baselines in the low- www-mmmorr-budeeee setting, where the assumption is that the network has so many parameters that we can only store a few copies.
The data structure produced by Sketched Lanczos is sufficiently rich to evaluate the predictive variance, and consequently the uncertainty score. However, from Bayesian point of view, it is worth noting that the method does not allow us sample according to the posterior.
Limitations.
10

---

Acknowledgments and Disclosure of Funding
The work was partly funded by the Novo Nordisk Foundation through the Center for Basic Machine Learning Research in Life Science (NNF200C0062606). It also received funding from the European Research Council (ERC) under the European Union's Horizon program (101 (101125993), and from research grant (42062) from VILLUM FONDEN. The authors acknowledge the Pioneer Centre for AI, DNRF grant PI. The authors also acknowledge Scuola Normale Superiore Pisa.
We thank Marcel Schweitzer for pointing out some highly relevant literature on applying sketching to Krylov methods carried out by the numerical linear algebra community.
References
Nir Ailon and Bernard Chazelle. The fast JohnssnnLLindeestraut transform and approximate nearest neighbors. SIAM Journal on computing, 39(1):30-3322, 2009.
Javier Antorán, Shreyas Padhy, Riccardo Barbano, Eric Nalisnick, David Janz, and José Miguel Hernnndez-Loaate Sampling-bast -based inference for large linear models, with application linearised Laplace. In International Conference on Representation Learning (ICLR), 2023.
Oleg Balabanov and Laura Grigori. Randomized gram-schmidt process with application to gmres. SIAM Journal on Scientific Computing, 44(3): A4450-A1444 2022.
Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra. Weight uncertainty in neural network. In International conference machine learning, pages 1613-1622. PMLR, 2015.
Lukas Bossard, Matthieu Guillaumin, and Luc Van Gool. 1ood-101-mining discriminative compo- nents with random forests. In Computer vision-ECCV 2014: 13th European conference, zurich, Switzerland, September 6-12, 2014, proceedings, part 13, pages 446-461 Springer, 2014.
Alcksandar Botev, Hippolyt Ritter, and David Barber. Practical gauss-newton optimisation for deep learning. In International Conference Machine Learning, pages 557-565. PMLR, 2017.
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+NumPP programs, 2018. URL
sttp:///ithut com/ /omgggoooe/aax
Jane K Cullum and Ralph A Willoughby. Lanczos algorithms for large symmetric eigenvalue computations: Vol. I: Theory. SIAM, 2002.
Erik Daxberger, Agustinus Kristiadi, Alexander Immer, Runa Eschenhagen, Matthias Bauer, and Philipp Hennig. Laplace redux-effortless Bayesian deep learning. Advances in Neural Information Processing Systems, 34:20089 201003, 2021a.
Erik Daxberger, Eric Nalisnick, James U Allingham, Javier Antorán, and José Miguel Hernández- Lobato. Bayesian deep learning via subnetwork inference. In International Conference on Machine Learning, pages 25 2510-25... PMLR, 2021b.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pages 248-255. leee, 2009.
Inderjit Singh Dhillon. A new O(N(2)) algorithm for the symmetric tridiagonal eigenvalueeecigenvettor problem. University of California, Berkeley, 1997.
Amine Elhafsi, Rohan Sinha, Christopher Agia, Edward Schmerling, Issa AD Nesnas, and Marco Pavone. Semantic anomaly detection with large language models. Autonomous Robots, 47(8): 1035-1055, 2023.
Yarin Gal and Zoubin Ghahramani. Dropout Bayesian approximation: Representing model uncertainty in deep learning. In international conference on machine learning, pages 1050-1059.
PMLR, 2016.

---

Behrooz Ghorbani, Shankar Krishman, and Ying Xiao. An investigation into neural net optimization via Hessian eigenvalue density. In International Conference on Machine Learning, pages 2232- 2241. PMLR, 2019.
Alex Graves. Practical variational inference for neural networks. Advances in neural information processing systems, 24, 2011.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In International conference on machine learning, pages 1321-1330. PMLR, 2017.
Stefan Güttel and Marcel Schweitzer. Randomized sketching for krylov approximations of large-scale matrix functions. SIAM Journal on Matrix Analysis and Applications, 44(3): 2023,
N. Halko, P. G. Martinsson, and J. A. Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM Review, (3 2011. doi: 10. 00.1137090771806 URL https: http://doi.oooo http::///o...../.1.11/./ 11370//771000/////0/819
Dan Hendrycks and Kevin Gimpel. baseline for detecting misclassified and out-of-distribution examples in neural networks. arXiv preprint
2016.
Daniel Hendrycks. Cifar- and cifar- 10-p, January 2019. URL httph::tt//oo htt///i..orr1..2055... zenodo. 2535967.
Geoffrey E Hinton and Drew Van Camp. Keeping the neural networks simple by minimizing the description length of the weights. In Proceedings of the sixth annual conference on Computational learning theory, pages 5-13, 1993.
Alexander Immer, Maciej Korzepa, and Matthias Bauer. Improving predictions of Bayesian neural nets via local linearization. In International conference on artificial intelligence and statistics, pages 703-711. 11 PMLR, 2021.
Alexander Immer, Tycho FA Van Der Ouderaa, Mark Van Der Wilk, Gunnar Ratsch, and Bernhard Schölkopf. Stochastic marginal likelihood gradients using neural tangent kernels. International Conference on Machine Learning, pages 14333-14352. PMLR, 2023.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
Daniel M Kane and Jelani Nelson. Sparser Johnson-Lindensstrun transforms. Journal of the ACM (JACM), 61(1):1-23, 2014.
Mohammad Khan, Didrik Nielsen, Voot Tangkaratt, Wu Lin, Yarin Gal, and Akash Srivastava. Fast and scalable Bayesian deep learning by weight-perturbation in Adam. In International conference on machine learming, pages 261 2611-2620. PMLR, 2018.
Mohammad Emtiyaz Khan and Håvard Rue. arXiv:2107.04562, 2021.
The Bayesian learning rule.
arXiv preprint
Mohammad Emtiyaz E Khan, Alexander Immer, Ehsan Abedi, and Maciej Korzepa. Approximate inference turns deep networks into Gaussian processes. Advances in neural information processing systems, 32, 2019.
Durk P Kingma, Tim Salimans, and Max Welling. Variational dropout and the local reparameterizzation trick. Advances in neural information processing systems, 28, 2015.
Agustinus Kristiadi, Matthias Hein, and Philipp Hennig. Being Bayesian, even just a bit, fixes overconfidence in ReLU networks. In International conference machine learning, pages 5436-5446. PMLR, 2020.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Frederik Kunstner, Philipp Hennig, and Lukas Balles. Limitations of the empirical Fisher approx- imation for natural gradient descent. Advances in neural information processing systems, 32, 2019.
12

---

Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. Advances in neural information processing systems, 30, 2017.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-2) 2324,, 1998. doi: (0.1109/5.726991
Jachoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve linear models under gradient descent. Advances in neural information processing systems, 32, 2019.
Jongseok Lee, Matthias Humt, Jianxiang Feng, and Rudolph Triebel. Estimating model uncertainty of neural networks in sparse information form. International Conference on Machine Learning, pages 5702-5713, PMLR, 2020.
Shiyu Liang, Yixuan Li, and Rayadurgam Srikant. Enhancing the reliability of out-of-distribution image detection in neural networks. arXiv preprint vrXiv:1706.026663 2017.
Qiang Liu and Dilin Wang. Stein variational gradient descent: A general purpose Bayesian inference algorithm. Advances neural information processing systems, 29, 2016.
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of International Conference Computer Vision (ICCV), December 2015.
David JC MacKay. A practical Bayesian framework for backpropagation networks. Neural compula- tion, 4(3):448-477) 1992.
David JC MacKay. Information theory, inference and learning algorithms. Cambridge University Press, 2003.
Wesley Maddox, Pavel Izmailov, Timur Garipov, Dmitry P Vetrov, and Andrew Gordon Wilson A simple baseline for Bayesian uncertainty in deep learning. Advances in neural information processing systems, 32, 2019.
David Madras, James Atwood, and Alexander D' Amour. Detecting extrapolation with local ensem- bles. In International Conference on Learning Representations, 2019.
James Martens and Roger Grosse. Optimizing neural networks with Kromecker-factored approximate curvature. In International conference machine learning, pages 2408-24111 PMLR, 2015.
Per-Gunnar Martinsson and Joel Tropp. Randomized numerical linear algebra: foundations & algorithms (2020). arXiv preprint arXiv:2002.01389 2020.
Gérard Meurant. The Lanczos and conjugate gradient algorithms: from theory to finite precision computations. SIAM, 2006.
Marco Miani, Frederik Warburg, Pablo Moreno-Muñoz, Nicki Skafte, and Søren Hauberg. Laplacian autoencoders for learning stochastic representations. Advances in Neural Information Processing Systems, 35:21059 220922 2022.
Leon Mirsky. Symmetric gauge functions and unitarily invariant norms. The quarterly journal of mathematics, 11(1):50-59, 1960.
Aaron Mishkin, Frederik Kunstner, Didrik Nielsen, Mark Schmidt, and Mohammad Emtiyaz Khan. Slang: Fast structured covariance approximations for Bayesian deep learning with natural gradient. Advances in Neural Information Processing Systems, 31, 2018.
Jelani Nelson and Huy I. Nguyên. Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings. In 2013 ieee 54th annual symposium on foundatisons of computer science. pages 117-126. IEEE, 2013.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Baolin Wu, Andrew Y Ng, et al. Reading digits natural images with unsupervised feature learning. In NIPS workshop on deep learning and unsupervised feature learning, volume 2011, page 4. Granada, 2011.
13

---

Chris C Paige. Accuracy and effectiveness of the Lanczos algorithm for the symmetric eigenproblem. Linear algebra and its applications, 34:235-2555 258,, 1980.
Christopher Paige. Error analysis of the lanczos algorithm for tridiagonalizing a symmetric matrix. IMA Journal of Applied Mathematics, 18(3):341-34, 1976.
Christopher Conway Paige. The computation of eigenvalues and eigenvectors of very large sparse matrices. PhD thesis, University of London, 1971.
Vardan Papyan. The full spectrum of deepnet Hessians at scale: Dynamics with sgd training and sample size. arXiv preprint arXiv:1811.07022 2018.
Jiacheng Qiao, Chengzhi Zhong, Peican Zhu, and Keke Tang. Advscod: Bayesian- based out-of- distribution detection via curvature sketching and adversarial sample enrichment. Mathematics, 11 (3):692, 2023.
Hippolyt Ritter, Aleksandar Botev, and David Barber. Online structured Laplace approximations for overcoming catastrophic forgetting. Advances in Neural Information Processing Systems, 31, 2018a.
Hippolyt Ritter, Aleksandar Botev, and David Barber. A scalable Laplace approximation for neural networks. In 6th International Conference on Learning Representations, ICLR 2018-Confernnce Truck Proceedings, volume 6. International Conference on Representation Learning, 2018b.
Hrittik Roy, Marco Miani, Carl Henrik Ek, Philipp Hennig, Marvin Pförtner, Lukas Tatzel, and Søren Hauberg. Reparameterization invariance approximate bayesian inference. arXiv preprint arXiv:2406.033: 03334, 2024.
Levent Sagun, Utku Evei, V Ugur Guney, Yann Dauphin, and Leon Bottou. Empirical analysis of the Hessian of over-parametrized neural networks. arXiv preprint arXiv: 04445, 2017.
Peter Schulam and Suchi Saria. Can you trust this prediction? auditing pointwise reliability after learning. In The 22nd international conference on artificial intelligence and statistics, pages 1022-1031. PMLR, 2019.
Apoorva Sharma, Navid Azizan, and Marco Pavone. Sketching curvature for efficient out-of- distribution detection for deep neural networks. In Uncertainty in Artificial Intelligence, pages 1958-1967. PMLR, 2021.
Horst D Simon and Hongyuan Zha. Low-rank matrix approximation using the Lanczos bidiago- nalization process with applications. SIAM Journal on Scientific Computing. 21(6):2257-22 2000.
Valeria Simoncini and Yihong Wang. Stabilized short-term recurrences via randomized sketching. 2024.
Edouard Timsit, Laura Grigori, and Oleg Balabanov. Randomized orthogonal projection methods for krylov subspace solvers. arXiv preprint arXiv:2302.07466, 2023.
Joel A Tropp and Robert J Webber. Randomized algorithms for low-rank matrix approximation: Design, analysis, and applications. arXiv preprint arXiv:2306. 12418, 2023.
David P Woodruff et al. Sketching as a tool for numerical linear algebra. Foundations and Trends@ in Theoretical Computer Science, 10(1 115,, 2014.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST: a Novel Image Dataset for Bench- marking Machine Learning Algorithms, 2017.
14

---

A Dimensionality Reduction
A.1 Proof of "Sketching low-rank matrices" Lemma
In this section, we prove Lemma 3.1. We restate it below for convenience.
Lemma 3.1 (Sketching low-rank matrices). Fix 0 < s, < 1/2 and sample a random x SRFT matrix S. Then, for any u E IR' and any matrix E R with ||0||2. |22 = ((1) we have Pr ((((SU)((S)))) | TTulll 2112 + E) - 5.
(6)
as long as s = 22ke logp log(k/)))
Proof. In order to prove that (Su)llz ||0 ull2 = with probability 2 1 1 ò we prove the following stronger statement. Denote with [u]; the i-th coordinae u, then for each = 11... we have (SSU)((S))) (Su)]s = [] + e/ V with probability at least 1 - 6/k. Apparently, the former follows from the latter by union bound.
Notice that [(SU) T (Sv)); = (SU") where U is the i-th column of U. Moreover, as long as s = Okke log p log(k/6)) ()), then is a (1 + se//kkk-susppaaa embedding for the 2-dimensional subspace spanned by v and U with probability 1 6/k (Theorem 2.2). Therefore, conditioning on this event:
1
(IISUU* + + -|S(U .)1(8) (SU")((S))
4 1 (1I(U) + + ||(U* - =))1 = (</vVk
= T O(e/Vk)
IU O(E/Vk))
The second equality sign holds because of the subspace embedding property, together with | U/|2, ||U - 0112 = O(1).
A.2 Proof of "Orthogonalizing the sketch" Lemma
In this section, we prove Lemma 3.2. We restate it below for convenience.
Lemma 3.2 (Orthogonalizing the sketch). Fix O < E, < 1/2 and sample random s X SRFT matrix S. As long as S2(ke- log log(k//) ())) the following holds with probability 8.
Given p l full-rank matrix V. decompose V UR and SV UsRs that U RPxk Us E Rack and both U and Ug have orthonormal columns. For any unit-norm u E R2 we have [|U] (Sv)ll2 - - T
Essentially, the proof of Lemma 3.2 was already known, see for example Corollary 2.2 in Balabanov and Grigori [2022]. Nonetheless, we include short proof for completeness' sake.
Proof. Since V full-rank, it is easy verify that SV is also full rank with high probability. Thus, R is non-singular and we can define Ú V VR55 Notice that Us = SU. Now, prove that
| ÜÜ 1 S
(11)
where 1|-112 is the operator norm. By definition of Us. we have I = USUs = ÜST SÜT By subspace embedding property of S, we have that
|| L00 T - 1 = |00 - ÜST SU 12
with probability 1 8. Conditioning this event, the singular values of U lie in [1 8, 1 e].
Moreover, RUn(U)= = RT) Therefore, taking the singular value decomposition (SVD) of U and
U yields Equation 11.
Now we are left to prove that [Tul = |1T] Sull2te. We have U 5 TT and by Lemma 3.1 we have | S Svll2 = T E with probability 8. Thus, || Tu12 = ||U Sull2 & and combined with Equation 11 gives Equation 7, up constant blow-ups in and 8.
D
15

---

A.3 Extension of Lemma 3.2
In this section we extend Lemma 3.2 to the case where instead of having a query vector v E R' we have a query matrix J E R²xt. In our application, J is the Jacobian Jg- (z)).
Lemma A.1 (Orthogonalizing the sketch, for matrix queries). Fix 0 < s, < 1/2 and sample random & p SRFT matrix S. As long as 22 logp- log(Uk/ /6)) the following holds with probability 1 5.
Given any p k. full-rank matrix V. decompose V UR and SV UgRs that U B Us E Raxk and both U and Ug have orthonormal columns. For any J E &pxt we have
||| [ (SJ)) (1 + =>|>>>> - - JIP-
(12)
Proof. Let J the i-th column of J. Suppose that the following intermediate statement holds: for each i, | (S.))lla = J' + | E/ /t with probability 8/t. If the statement above holds, then we have
[ - 1IU J (IUU -IU J(IF) [[ - J[[
o(J]Ir)) Σ (IUS (SJ))l22 - (211)) S
O11 E).
The penultimate inequality holds because of triangle inequality. whereas the last inequality holds with probability 1 - ò by union bound.
To prove the intermediate statement above, it is sufficient to apply Lemma 3.2 with = =e/Vt and 8' = 5/t.
B Extended Related Work
Local ensembles. In Madras et al. [2019], they consider local ensembles, computationally efficient way to detect underdetermination without training an actual ensemble of models. A local ensemble is a distribution over models obtained by perturbing the parameter along zero-curvature directions. Small parameter perturbations along zero-curvature directions cause small perturbation of the model prediction. Given test point, Madras et al. [2019] define the local ensemble score as the first-order term of the predictive variance for small perturbations along zero-curvature directions.
Moreover, in Madras et al. [2019] they prove that the aforementioned score is equivalent to [[[ (z)ll F where 11, projection onto a subspace defined as the orthogonal of the zero- curvature subspace at 0", Jg- (I) is the Jacobian of the test datapoint and ||-||p is the Frobenius norm. Computationally, they approximate their score by setting IIg = - U² where Un is a x matrix which columns are the top-k eigenvectors of the Hessian of the loss L()).
Their method uses Lanezos algorithm to compute the top-k eigenvectors of the Hessian and uses k memory. This is costly, indeed Madras et al. [2019] write
"The main constraint of our method is space rather than time - while estimating the first k eigenvectors enables easy caching for later use, it may be difficult work with these eigenvectors in memory as and model size p increase. [...] we note in some cases that increasing further could have improved performance [...] This suggests that further work on techniques for mitigating this tradeof."
Comparison with SCOD. SCOD, the uncertainty estimation score introduced in Sharma al. [2021], has gained traction lately and it has been used as an uncertainty estimation baseline in applications Qiao et [2023], Elhafsi et [2023]. SCOD can interpreted as a Bayesian method that approximates the posterior with Gaussian having a covariance matrix of the form identity + low-rank. Computing such approximation of the variance boils down to computing a low-rank approximation of the inverse of F + al, where F is the Fisher information matrix and depends
16

---

on the variance of the isotropic Gaussian prior on 0. Ultimately, the SCOD score is defined as I & J- (z) where Ug a k matrix which columns are the top-k eigenvectors of F and A is a k x k diagonal matrix such that A; > +a).
SCOD and Local Ensembles scores are extremely similar. Indeed, the only difference between their scores is that SCOD weighs projection onto different cigenvectors according to A. However, in Sharma et al. [2021] they observe empirically that different values of a yield the same score accuracy, hinting that replacing A with the identity (that essentially gives local ensembles score) should have a modest impact on accuracy. From a computational point of view, both methods compute the top-k eigenvectors of the Hessian / Fisher accessing it solely through matrix-vector product. Local ensembles achieves that using Lanczos algorithm, whereas SCOD uses truncated randomized singular values decomposition (SVD). In both cases the space complexity k Similarly to Madras et al. [2019], also Sharma al. [2021] observed that the most prominent limiting factor for their method was memory usage*:
"The memory footprint of the offline stage of SCOD still linear, i.e., (kk)). As a result, GPU memory constraints can restrict k [...] substantially for large models."
GGN/ / Fisher Hessian. Local Ensembles uses computes the top-k eigenvalue of the Hessian of (( whereas Sharma et al. [2021], Immer et al. [2021] employs the Fisher / GGN. Implementing matrix-vector product for both Hessian and Fisher /GGN is straightforward, thanks to the power of modern software for automatic differentiation. However, we believe that using the GGN / Fisher is more appropriate in this context. Indeed, the latter is guaranteed be positive semi-definite (PSD), whereas the Hessian is not necessarily PSD for non-conver landscapes.
C Lanezos algorithm
Lanczos algorithm is an iterative method for tridiagonalizing an Hermitian matrix G. If stopped at iteration k; Lanczos returns a column-orthogonal matrix V = [V]]...[VV] E Rp*k and a tridiagonal matrix T E * such that VTGV = T. The range space of V corresponds to the Krylov subspace K& = (v, Gv, .., Gu....,GG-Iy), where Vi is randomly chosen vector. Provably Kc approximates the eigenspace spanned by the top-k eigenvectors (those corresponding to eigenvalues of largest modulus) of G. Thus, VTV approximates the projection of G onto its top-k eigenspace. Notice that projecting G' onto its top-k eigenspace yields the best rank-k approximation of G under any unitarily-invariant norm Mirsky [1960]. Moreover, as observed in the previous section the spectrum of the GGN decays rapidly, making low-rank decomposition particularly accurate.
Once the decomposition G VTVT is available, we can retrieve approximation to the top- eigenpairs of G by diagonalizing T into T = WAW which can be done efficiently for tridiagonal matrices Dhillon [1997]. The quality of eigenpairs' approximation has been studied in theory and practice. We point the reader to Meurant [2006), Cullum and Willoughby [2002] for a comprehensive sourvey on this topic.
Lanczos, in a nutshell. Here we give a minimal description of Lanezos algorithm. Lanczos maintains set of vectors V = [Vil... Vx], where V, is initialized at random. At iteration i + 1. Lanczos performs a matrix-vector product Vi+1 + G V,, orthogonalizes V4+1 against V2 and V,- and normalizes it. The tridiagonal entries of T are given by coefficients computed during orthogonalization and normalization. See Chapter of Meurant [2006] for a full description of Lanczos algorithm.
The benefits of Lanczos. Lanezos has two features that make particularly appealing for our uses case. First, Lanezos does not need explicit access to the input matrix G, but only access to an implementation of -> Gu. Second, Lanezos uses a small working space: only 3p floating point numbers, where the input matrix is p p. Indeed, we can think of Lanczos releasing its output in streaming and only storing a tiny state consisting of the last three vectors Vi-1, V, and V++1-
The curse of numerical instability. Unfortunately, the implementation of Lanczos described above ... V₂ to far from orthogonal. careful analysis of prone to numerical instability, causing Vi...
'The original version statest that the memory footprint is (('p), where T' 2 le a parameter of their SVD algorithm.
In this work, are only concerned with real symmetric matrices.
17

---

1.50
0.75
0.25
1012
Figure 5: We study the GGN of a LeNet model with 44.000 parameters trained on MNIST. We run 40 iterations of hi-memory Lanczosand low-memory Lanczos. Let H [H]]... H Aи- L = [ Lij] and Ag be the cigenvectors and cigenvalues computed by the two algorithms respectively. We sort both sets of eigenvectors in decreasing order of corresponding eigenvalues. In position (i,j) we plot (H; Ly). It is apparent that multiple eigenvectors L, correspond to the same eigenvector H;-
the rounding errors causing this pathology was carried out by Paige in his PhD thesis well as series of papers Paige [1971, 1976, 1980].
To counteract this, a standard technique is re-orthogonalize V++1 against all (Vg)ss at each iteration. This technique has been employed to compute the low-rank approximation of huge sparse matrices Simon and Zha [2000], well in Madras al. [2019] to compute approximation to the top-k eigenvectors. Unfortunately, this version of Lanczos loses one the two benefits described above, in that it must store larger state consisting of the whole matrix V. Therefore, dub this version of thew algorithm hi-memory Lanczosand the cheaper version described above low-memory Lanczos.
Paige Paige [1980] proved that the loss of orthogonality in low-memory Lanczosis strictly linked to the convergence of some of the approximate eigenpairs to the corresponding eigenpairs of G. Moreover, the vectors Vi... V/2 are not orthogonal because they are tilted towards such eigenpairs. Accordingly, he observed that among the eigenpairs computed by low-memor Lanczosthere multiple eigenpairs approximating the same eigenpair of G. This can easily be observed while running both low-memory Lanczosand hi-memory Lanezosand computing the dot products of the their retrieved eigenvectors; see Figure 5.
Post-hoc orthogonalization. Based on the observations of Paige Paige [1980], expect that orthogonalizing the output of low-memory Lanczos post-hoc should yield an orthonormal basis that approximately spans the top-k eigenspace. Since in our method we only need to project vectors onto the top-k eigenspace, this suffices to our purpose.
We confirm this expectation empirically. Indeed, using the same setting of Figure 5 we define L as the projection onto the top-10 principal components of L. and define IHи likewise. Then, we measure the operator norm (i.e., the largest singular value) of II ll and verify that it is fairly low, only 0.03. Taking principal components was necessary, because there is no clear one-to-one correspondence between L,s and H,s, in that observed in Figure 5 many L,s can correspond to single Hę. Nonetheless, this proves that low-memory Lanezos capable approximating the top eigenspace.
C.1 Spectral properties of the Hessian /GGN
Spectral property of the GGN and Hessian have been studied both theoretically and empirically. In theory, was observed that in the limit of infinitely-wide NN, the Hessian is constant through training Jacot et al. [2018]. However, this is no longer true if we consider NN with finite depth Lee et al. [2019]. In Sagun et [2017], Papyan [2018]. Ghorbani et [2019], they show empirically that the
This be done efficiently via power method.
18

---

10
10
10000
10a
datapoints, 10000 datapeints, 1000 Iterations
Egenvalue
1000 datapaints iterations datapoints, 1000 datapaints, Iterations
10a
100 datapoints, iterations
datapoints, iterations
10a
datapoints,
.... 10 datapoints, iterations
109
10 datapaints, 100 iterations catapoints,
10
10
10a
10
102
10a
Index
10a
60000 datapoints, 10 iteraions
00000 datapoints, 100
datapoirts, 60000 datapoints, 10000 iteraions
10000 datapoints, 10 terations
10a
datapoints, datapoints, terations 10000 datapornt, 10000 ite feriioons
Egenvallue
1000 delapaints, terations
datapoints, 1000 datapaints, 1000 iterations
10a
1000 datapoints, 10000 iterations
do0-daaapontss
datapoirts, kerations 100 datapoints, 1000 Rerations
10a
100 datapoints, 10000 iterations datapaints,
10 datapoints, 100 nerations 10 datapoints, 1000 tenations datapoints, 10000 terations
10a
datapoirts, iteration
50000 dataports. 100 Iterationn
10
50000 datapoint,, 1000 iterations
dataporns, 10000 iteraions datapoints, 10000 datapoirts, 100 iteraaioon
10a
10000 detapoints, 1800 iteaaions
Elgenval ue
datapoirts, 1000 datapoints, tematios
10a
1000 datapoints, 100 terations
1000 datapoints,
10
datapaints, 10000 iteration
100 dataports, 10 iterations
100 datapoints 100 terations
10a
datapaints, dalapoints, 19000 teeations
10 datapoints, 10 terations
10-1
10 detapoints, 100 merations datapoints,
10 datapoints, 10000 iteraiion
10
10P
10a
10a
10a
10*
Index
Figure 6: Eigenspectrum obtained from hi-memory Lanczos on: ResNet model (p 300K) trained on CIFAR-10 (top), LeNet model (p = 40K) trained on FashionMNIST (middle) and ML. model (p 20K) trained on MNIST (bottom). Standard deviations over 5 Lanczos random seeds.
19

---

spectrum of the GGN / Hessian is composed of two components: a bulk of near-zero eigenvalues, and small fraction of outliers away from the bulk. Moreover, Ghorbani et al. [2019], they observe a large concentration of the gradients along the eigenspace corresponding to the outlier eigenvalues.
In summary, the spectrum of the GGN Hessian of deep NN is expected decay rapidly, having a few outlier eigenvalues, along which most gradients are oriented. Therefore, we would expect low-rank approximation of the GGN to capture most relevant information.
We lest this phenomenon by using hi-memory Lanczosand performing an ablation over both number of iterations and random initialization of the first vector. Figure 6 shows the results over three different model trained on different datasets. The plots cointains means and std bars over 5 random initializations of the first Lanczos vector. It is interesting to observe how, varying the number of iterations, approximately the first 90% values are the same, while the tail quickly drop down to numerical precision. Based on this observation we choose only use the top 90% vectors returned by Lanczos.
D Experimental setting and extended results
Experiments are reproducible and the code is available at https://githe: com/ htwodmmmbileeunnceraattyy
As explained later in greater details, calling the scripts train_ soinn_mmdel... py and score_model.py py with the right parameters is enough to reproduce all the numbers we presented.
__.r sh collects the entire pipeline of setup, training, scoring and plotting and finally reproduce Figure 4 and save them in the folder figures. The first three plots takes approximately 3 days to complete on NVIDIA H100 80GB GPU.
Reproducibility. The script cassh/loo_figuree
The code is implemented in JAX (Bradbury et al., 2018] in order to guarantee max control on the randomness, and, given a trained model and random seed, the scoring code is fully deterministic (and thus fully reproducible). Nonetheless, the dataloader shuffling used at training time depends on PyTorch (bad) randomness management, and consequently it can be machine-dependen
D.1 Training details
All experiments were conducted on models trained on one of the following datasets: MNIST [Lecun et al., 1998], FASHIONMNIST [Xiao et al., 2017]. CIFAR- 10 [Krizhevsky et al., 2009], CELEBA [Liu et al., 2015] and IMAGENET [Deng et al., 2009]. Specifically we train:
on MNIST with a MLP consisting of one hidden layer of size 20 with tanh activation functions, we trained with ADAM for 50 epochs with a batch size 128 and learning rate 10 3, parameter size is p 15910;
on FASHIONMNIST with LeNet consisting of two convolution layers with maxpool followed by fully connected layers with tanh activation functions, we trained with ADAM for 50 epochs with batch size 128 and learning rate 10 30; parameter size is p 44426;
on CIFAR- 10 with a ResNet with (3,3. 3.3) blocks of channel sizes (16, 32, 64) with relu activation functions, we trained with SGD for 200 epochs with batch size 128 and learning rate 0.1, momentum 0.9 and weight decay 10-4; parameter size is p 272378;
on CELEBA with IisualAttentionNeewoor with blocks of depths (3,3, 5, 2) and embedded dimensions of (32, 64, 160, 256) with relu activation functions, we trained with Adam for 50 epochs with a batch size 128 and a learning rate decreasing from 10-3 to 10-5; parameter size is 3858309.
on IMAGENET with a SWIN model with an embed dimension of 192, blocks of depths (2, 2, 18, 2) and number of heads (6, 12, 24, 48), we trained with Adam with weight decay for 60 epochs plus a 10 epoch warmup, with a batch size 128 and a learning rate decreasing from 10-3 to 10-5; parameter size is
196517106.
For training and testing the default splits were used. All images were normalized to be in the [0, 1] range. For the CELEBA dataset we scale the loss by the class frequencies in order to avoid imbalances. The cross entropy loss was used as the reconstruction loss in all models but the VisualAtteemionNeeewok one, which multiclass binary cross entropy was used.
20

---

We train all models with 10 different random seed, (except for ImageNet, that we only trained with one seed) which can be reproduced by running
bash/setup.c sh source (L.tuullen//bnnaactivae echo "Train all models"
for seed in (1..10) do
python train_modell, --dataset MNIST --likelihood classification --model MLP
--seed Saeed --run_namm good --default_ byyeeuaal.yyeeaaaaaa
python train_model py --dataset FMNIST --likelihood classification --model
LeNet --seed $seed -rrunnamee good -- -eeffult _hyperpaaams t
python train_model --dataset CIFAR-10 10 --likelihood classification --model
ResNet: --seed $seed --run_name good --defanlt.hyperpareee
python train_model.pp py --dataset CelebA --1ikelihood binary_min wwt..//aiiclaaaiiiatiiiio
--model VAN_ tiny --seed $seed --run_ name good --default, --default.byperparamm. hyperparams
python train_model.pp --dataset ImageNet --likelihood classification --model
SWIN_large --seed $seed --run_name good --ddefault.byeeparreee
done
The trained model test set accuracies are: 0.902 0.886 0.003, 0.901 0.0002 0.672, respectively for the 5 different settings.
D.2 Scoring details
The standard deviations of the scores presented obtained scoring the indepentently trained models. For all methods we use: 10 seeds for MNIST, 10 seeds for FMNIST, 5 seeds for CIFAR-10 10, seeds for CELEBA and seeds for IMAGENET. The only exception is Deep Ensemble for which we used only independent scores for the budget3 experiment (for a total of 9 models used) and only I score for the budget10 experiments (using all the 10 trained model).
For the fixed memory budget experiments we fix the rank to be equal to the budget (3 or 10) for all baseline, while for method we were able to have higher rank thanks the memory saving induced by sketching, specifically:
for experiments with MNIST in-distribution we used sketch size s 1000 and rank
k = 45 for the budget3 and k = 150 for the budget10;
for experiments with FASHIONMNIST as in-distribution we used sketch size s = 1000 and a rank | 132 for the budget3 and 440 for the budget10;
for experiments with CIFAR-10 10 in in-distribution we used a sketch size 10000 and a rank k = 81 for the budget3 and sketch size = 50000 and rank k 50 for the budget10;
for experiments with CELEBA as in-distribution we used a sketch size s 10000 and rank 100 both for the budget3 and for the budget10.
for experiments with IMAGENET as in-distribution we used sketch size 20000000 and rank le 30.
Baseline-specific details:
SWAG: we set the parameter collecting frequency to be once every epoch; we perform a grid
search on momentum and learning rate hyperparameter: momentum in [0.9, 0.99) resulting in the latter being better, and learning rate in [0.1, 1, 10] times the one used in training resulting in 1 being better. Although we spent decent amount of effort in optimizing these, it is likely that a more fine search may yield slighlty better results;
SCOD: the truncated randomized SVD has a parameter T and we refer to the paper for full explanation. Importantly to us, the default value T 6k and the memory usage at preprocessing is Tp, which is greater than kp. Nonetheless query time the memory requirement pł and we consider only this value order to present the score in the most fair way possible;
21

---

LOCAL ENSEMBLE: the method presented in the original paper actually makes use of the Hessian, rather than the GGN. And we denoted them LE-H and respectively. which is not fully respectful of the original paper but we think this approach helps clarity. Anyway, we extensively test both variant and the resulting tables show that they perform very similarly;
DEEP ENSEMBLE: each ensemble consists of either 3 or 10 models, depending on the experiment, each initialized with different random seed;
DIAGONAL LAPLACE: has fixed memory requirement of 1p.
All the scores relative to the budget3 experiment on CIFAR- 10 reported in Table 3 can be reproduced by running the following bash code
bash/setup. sh
source /virtuallear/bbnnacctiaaaa
dataset="CIFAR-10"
ood_datasets= CIFAR-100 CIFAR-10-C*
model_na model_name="Raee Laail_aam==RReeeee "RaNett"
for seed in (1..5) do
echo "Sketched Lanczos"
python score_mosee @core_model.pp py --ID_ --ID_datasse dataset $dataset --00D_ datasets $ood_datasets
-model Smodel_mant name model_seed $seed --run name good --subsample trainser
10000 --lanczos_ hm_ iter --lanczos 1m iter 81 --lanczos_ seed --sketch
srft --sketch_ssiee 10000
echo "Linearized Laplace"
python score_model.py
$dataset --000_ datasets food_datased --model Smodel_mann name medde_seed $seed --run name good --subsample_traatee trainset
10000 --lanczos_hhe _______m_tterr_ --laaczos Im 0 --laanzos_aeed 1
-usseeegeevall
echo "Local Ensembles"
python score_model, py ddt_ase $dataset -- --DD dat_satss $ood_ datasess
--model Smodel_nann name --mode_sseed $seed --run _ruu_name name good geubsample_trainge
10000 --lanczos, hm_ iter --lanczos 1m 0 --lanczoo_
echo "Local Ensemble Hessian"
python score_model.pp -- -i-ID_ddtasse $dataset - 00D datasets $ood_datasets
10000 --lanczos_ hm_ iter --lanczos seaizos_mm_itte im_iter 0 ---lanzos_seed taabbaampl_ttrinettttt trainset
--model Smodel_nanc Bameele_emmeee--- --mode__seee $seed --run _ame good --subsample_
echo "Diag Laplace"
python score_model.pp ID dataset _ $dataset --O0D datasets food_dataseta
--moeel Smodel_nane name -mode__seed $seed --run_nan name good --score diagonal_ 11a --subsample_traiie trainset 10000
echo "SCOD"
python score_model, py -- -D__dataaee $dataset --0DD_ datasets $ood_datasets rruu_name name good --score scod
--model Smodel_ name -- model_seed $seed --run
--n_eigonvec_hn hm - wwwssspllettaaiiiiiea trainset 10000
echo "SWAG"
python @hore_model_pp py --ID_ -.D__attsee $dataset --00D
--ODD_ datasets $ood_ datasets -model Smodel_nand name --model_seed $seed --run name good --score swag --wwag___ves n_eag vec 3 --svag_momentun 0.99 --swag_collect interval 1000
done
for seed in (1,4,7)
echo "Deep Ensembles"
python score_mode mts__model..ppp -atteett $dataset --00D 10D_datasets $ood_ datasets
--odel Smodel, name - --model_seee $seed --run_ name good --score ensemble -ensmble_size
do
done
Disclaimer. We did not include KFAC approximation as baseline, although main selling point is the memory efficiency. The reason is that it is layer-by-layer approximation (and so it neglects correlation between layers) and its implementation layer-dependent. There exist implementations for both linear layers and convolutions, which makes the method applicable to MLPs and LeNet.
22

---

But, to the best of our knowledge, there is no implementation (or even a formal expression) for skip-conmections and attention layers, consequently making the method inapplicable to ResNet, Visual Transformer, SWIN, or more complex architectures.
We did not include the max logit values [Hendrycks and Gimpel, 2016] as a baseline. The reason is that it is only applicable for classification tasks, so for example would not be applicable for CelebA which is a binary multiclassfication task.
Disclaimer 2.
datasets. In an attempt to evaluate the score performance as fairly as possible, we include big variety of OoD datasets. For models trained on MNIST we used the rotated versions of MNIST, and similarly for FASHIONMNIST. We also include KMNIST as an MNIST-Out-of. Distribution. For models trained on CIFAR- 10 used CIFAR- 100, SVHN and the corrupted versions of CIFAR-10 10, of the 19 corruption types available we only select and present the 14 types for which at least one method achieve an AUROC 0.5. For models trained CELERA three subsets of CELERA corresponding to faces with eyeglasses, mustache or beard. These images were of course excluded from the In- In-Distribution train and test dataset. Similarly for models trained on IMAGENET we used excluded from the In-Distribution train and test dataset 10 classes (Carbonara, Castle, Flamingo, Lighter, Menu, Odometer, Parachute, Pineapple, Triceratops, Volcano) and use them as OoD datasets. We do not include the results for Carbonara and Menu in thr Table since no method was able to achive an AUROC2 0.5.
used the
Note that rotations are meaningful only for MNIST and FASHIONMNIST since other datasets will have artificial black padding at the corners which would make the OoD detection much easier.
D.3 More experiment
Here we present more experimental results. Specifically we perform an ablation on sketch size s in Appendix 1 (on synthetic data) and on preconditioning size in Appendix D.3.2. Then in Appendix D.3.3 we perform again all the experiments in Figure 4, where the budget is fixed to be 3p, but now with a higher budget of 10p. We score the 62 pairs ID-OoD presented in the previous section (each pair correspond x-position in the plots in Figure 9), with the exception of ImageNet because single H100 GPU is not enough for it.
D.3.1 Synthetic data
Here motivate the claim "the disadvantage of introducing noise through sketching is outweighed by a higher-rank approximation" " with a synthetic experiment. For a fixed "parameter size" p = 106 and a given ground-truth rank R = 100 we generate artificial Fisher matrix M. To do so, sample R uniformly random orthonormal vectors ui... RR E TR? and define M = Σ. A, for some X > Doing so allows us to (1) implement x + Mr without instantiating M and (2) have explicit access to the exact projection vector product so we can measure both the sketch-induded error and the lowrank- wawpaaaappppooimmationinddueeee
error, so we can sum them and observe the trade-off.
For various values of & (on x-axis) and s (on y-axis), we run Skeched Lanczos on x H Mr for k iteration with sketch size s, and we obtain the sketched low rank approxima- tion Us. To further clarify, on the x-axis we added the column "inf" which refers to the same experiments done without any sketching (thus essentially measuring Lanezos lowrank- approximation-ern only) which coincides with the limit of s + co. The memory require-
ment of this "inf" setting is Pk, that is the same as the second last column where s P.
We generate set of test Jacobians as random unit vectors conditioned on their projection onto Span(11 ... UR) having norm J. We compute their score both exacltly (as in Equation 9) and sketched (as in Equation 10). In the Figure we show the difference between these two values. As expected, higher rank & leads to lower error, and higher sketch size 8 leads to lower error. Note that the memory requirement is propor- tional to the product ks, and the figure is in log-log scale.
152
0302
5.58
5.322
CO14 0.77 0.306 0.201 0:255 0.057 01055 0.54 0.00
42-
3//30
3294
2313
6335
6,25 0:33 6337 0232 0314 0212 0313 021:
Kank spprosmmeriin
3554
5/14 2.43 6/01 6:37 0.16 64%% 0A3 0A30 0431 0431 04Y
42 35535 5AM
5.7)
CAF4 0.55 DASTH D.56 0.56 0152 0.56 0.55 0.66
355N 5AM
5.56 C.31 O DAIS DATO OAFZ DAY7 0.77 0A75 0474
1505
1/011
6/1 DAYS DANZ GA9S DADL MADE 0.0 0.9.
350
100
2005
TONDS
70050
500N50
10000S
5000005
23 Figure 7: Ablation rank k and sketch size

---

D.3.2 Effect of different preconditioning sizes
0.53
0.72
SeltchelLeccm Steti Lencin precand 23
0.74
AURDS
0.66
0.72
Landta
Veell Lanota
skanched Landus proase Sheiched
Skanched Lanaus precen
0.22
042
Shatched Lanczs
048
505
23t
32"
0.58
20
14 Hemory cost in number of MNs
10
0.58
20"
Nemory cost number Nik
Nemory cost number of Mks
Figure 8: Preconditioning comparison for LeNet 40K FASHIONMNIST FASHIONMNIST- rotated-30 (left), and ResNet p = 300K on CIFAR-10 10 vs SVHN (center) or CIFAR-pixelated (right).
Preconditioning can be thought of as a smooth bridge between high-memory Lanezos and SKETCHED LANCZOS. We the former for few steps and then continue with the latter the preconditioned matrix. Consequently, the preconditioning scores "start" from the vanilla Lanczos curve, and improve quicker memory- memery-wise, shown in Figure 8.
D.3.3 Budget 10
The results with memory bugdet 10p are Table 4, Table and more extensively in Figure 9.
MNIST vs KMNIST
FASHIONMNIST
FASHIONMNIST
Rotation (avg)
MNIST
Rotation (avg)
SLU (us)
0.28 + 0.02
0,46 - 0.04
0.61 = 0.02
0.95 + 0.01
0.75 + 0.03
LLA
0.27 = 0.03
0.34
0.52 0.01
0.88 = 0.03
0.72 0.03
LLA-D
0.94 + 0.03
0.98
0.73 + 0.01
0.68 + 0.06
0.61 + 0.04
0.27 0.03
0.03
0.88 + 0.03
0.72 + 0.03
LE-H
0.27 + 0.03
0.03
0.52 0.01
0.88 + 0.03
0.72 + 0.03
SCOD
0.27 0.02
0.36 0.03
0.54 - 0.01
0.89 + 0.02
0.72 + 0.03
SWAG
0.26 + 0.05
0.18 + 0.03
0.39 - 0.03
0.77 + 0.04
0.72 + 0.04
DE
0.90
1.00
0.79
0.99
0.90
Table 4: AUROC scores of Sketched Lanczos Uncertainty vs baselines with memory budget of 10p.
CIFAR-10
CELEBA
v
SVHN
CIFAR- 100
Corruption (avg)
FOOD-101
Hold-out (avg)
SLU (us)
0.76 + 0.06
0.54 + 0.02
0.57 + 0.04
0.95 + 0.003
0.72 + 0.02
LLA
0.72 = 0.06
0.53 + 0.02
0.02
0,57 + 0.04
0.94 0.001
0.70 = 0.02
LLA-D
0.55 0.10
0.52
0.52 0.04
0.80 0.02
0.52 - 0.03
LE
0.06
0.02
0.900
0.70 0.02
LE-H
0.72 0.07
0.02
0.57
0.93 0.002
0.67 = 0.02
SCOD
0.75 + 0.05
0.58 0.04
0.94 0.002
0.70 = 0.02
SWAG
0.52 + 0.06
+
0.51 + 0.05
0.78 + 0.13
0.55 + 0.09
DE
0.45
0.51
0.50
0.96
0.68
Table AUROC scores of Sketched Lanezos Uncertainty vs baselines with a memory budget of 10p.
24

---

0.95
0.85
0.7
AUROC
0.6
0.75
0.5
SLU
LLA/ /LEhh
0.70
LLV/
0.4
LLAd
LLA-d
SCOD
0.3
SWAG
0.60
SWAG
DE
0.2
PMNIST
KMMNST
MINST-RLS
MNIST-R30
MNI5T:RAS
MNIST-RG
MNIST
MNIST-R90
MNST-AIOS
MUST-A120
MNIST-2335
MINISTA1500
MNI5T-R165
MUSTRR30
MWIST
Retatted 15"
Rotaled
Rotated
Rotated 75*
Rotatedd op
Rotated 105
Rotated
Rotated 135
Racated 150
Rotated 165
Rotated 180
(a) MLPp = 15K train on MNIST
(b) LcNet 40K train on FMNIST
0.80
0.75
0.95
LLA/LE
0.85
SCOD
SWAG
AUROC
0.65
0.80
LE-h
0.60
0.75
SLU
LLA/
0.55
LLA-d
SCOD
SWAG
0.60
0.45
0.55
CIFAR
Brighoness
Deforus blur
Elastic transf Frost
Geussian blur
blur
nolse
josg compress
Modion blur
Pirclate
Saturate
Snow
Spatter
Zoom blar
FOOD-101
Mustache only
only
Eyaglasses only
(d) VAN 4M train on CelebA
(c) ResNet p = 300K train on CIFAR-10
Figure 9: AUROC scores of Sketched Lanczos Uncertainty baselines with memory budget of 10p.
25

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The theoretical claim match the results presented in the Method Section. The experimental results match the numbers presented in the Experiment Section.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The limitations are related to memory requirements and scaling of the error induced by the sketching. Both of them are fully addressed in the Method Section.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-specfiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
26

---

Answer: [Yes]
Justification:
All theoretical statements are given detailed derivation in Appendix A.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We include the code in the submission and made it public at https: //github. com/
which allows to reproduce all results presented. We provide a detailed Appendix D describing the experimental setup, also directly pointing at scripts to train, score and plot the results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
27

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they 5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
Justification: We rely on established benchmark data. All code was included in the submis- sion supplementary material and is now publicly available https://gits com/ TlMioFrizzantinommmbbll htt.:///wwmmmieeeeeereaaaaaeeaaa teaettaattttuuutiiiiiieeee quantification under an open source software license.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ //tpps.cc/pppiii ctce/pubbic/guides... //c////ooSSSeiaaaeeeeeeee casssiinooicyyy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Every detail is specified in Appendix D
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
We provide standard deviations for all presented results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
28

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: These details are presented in Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https httpp://neete /ttpp::////uuipp... cc/ Ceapblic/thhcscuideeee.
Answer: [Yes]
Justification:
The work is predominantly theoretical and does not raise ethical concerns.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: The paper is predominantly theoretical. However, uncertainty quantification is potential remedy for several issues with currently deployed machine learning models, so there a potential for positive societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
29

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
we do not deem this be relevant.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best. faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: only consider well-established benchmark data, which cite appropri- ately.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
30

---

This is If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out the asset's s creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Open source code for reproducing experiments has been released at https:
/ //github. www.hh......iaaaa..ee.e.. http:///iiiiiiiiiiiiioaaaoaaaaaa well documented.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: this paper does not involve crowdsourcing or other forms of research involving human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: this paper does not involve crowdsoureing or other forms of research involving human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
31

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
32


Reviews:
[{"review_id": "XKqa2gRFCu", "reviewer": "Reviewer_Ntg4", "summary": "## Summary\n\n- This paper presents an architecture agnostic technique to compute uncertainty scores for pre-trained neural networks. The space complexity (memory usage) of their proposed technique SLU (Sketched Lanczos Uncertainty) grows logarithmically in the size of model parameters. The experiments reported in the paper use models such as LeNet and ResNet in the range 40K - 300K parameters. This is typically still smaller than pre-trained LLMs which are in millions of parameters or perhaps can be applied to LLMs in LoRA setting.\n- More concretely, this paper designs an algorithm to compute the \"local ensemble uncertainty estimation\" score introduced in Madras et al 2019. https://arxiv.org/pdf/1910.09573\n\t- This earlier paper quantifies \"unreliability\" of a prediction on the test-example as \"underspecification\".\n\t- They state, \"trained model is underspecified at a test input if many different predictions at that input are all equally consistent with the constraints posed by the training data and the learning problem specification (i.e., the model architecture and the loss function)\" \n\t- As a solution they introduce, \"local ensembles\" , a post-hoc method to measure how much a pre-trained model's prediction is underspecified for a particular test input.\n- This paper provides a more memory efficient algorithm to compute this \"local ensemble\".\n- The key observation the authors make in this paper are the following\n\t- Orthogonalization (used in vanilla Lanczos) approximately commutes with sketching (embedding high dim vectors to lower dim to save on memory). Using this key observation they can change the order of sketching the Lanczos vectors and orthogonalization. Doing orthogonalization post-hoc leads to significant memory-savings.\n\t- The other results they demonstrate is that in this low-memory budget regime, the disadvantage of introducing noise through sketching is countered by using a higher-rank approximation, leading to better performance.\n\n- Background:\n\t- **Generalized Gauss Newton Matrix**\n\t\t- The local information can be characterized commonly by using the Fisher Information Matrix which is the same as Generalized Gauss Newton Matrix (GGN) Matrix. This GGN matrix is a pxp matrix where p is the number of parameters of the model. Various approximations have been proposed in the literature such as block-diagonal, diagonal etc.\n\t\t- In this work, the authors approximate the GGN matrix with a low-rank matrix. The rank-k approximation of the GGN matrix can be computed through two algorithms.\n\t\t\t- the Lanczos algorithm or\n\t\t\t- truncated singular value decomposition algorithm.\n\t\t- This is also known as Empirical Fischer matrix (Kutner et al 2019)\n\t- **Uncertainty Score**\n\t\t- The uncertainty at a datapoint x is measured as the variance of the prediction $f(\\theta)$ with respect to distribution over parameter $\\theta$.\n\t\t- For the approaches which only train a single network, various choices of covariance are proposed which are connected to the GGN matrix described above (Kunstner et al 2019)\n\t- Essentially, the authors in this paper show that low-rank approximation of GGN matrix is a good idea because the eigen values decay exponentially.\n\t- **Lanczos Algorithm**\n\t\t- The lanczos algorithm is an algorithm is an iterative method for tridiagonalizing a symmetric matrix G (pxp).\n\t\t- If you stop this algorithm at iteration k, it returns a column orthonormal matrix V (pxk) and a tridiagonal matrix T (kxk) such that $V^T.G.V = T$\n\t\t- $V^T.T.V$ approximates the projection of G onto its top k eigenvectors. Projecting G onto its top k eigenspace yields the best rank k approximation of G under any unitarily invariant norm.\n\t\t- Once the approximation $V^T.T.V$ of $G$ is available, we can retrieve an approximation of top-k eigenpairs of G by diagonalizing T into $T=W\\Lambda W^T$\n\t\t- The benefit of Lanczos algorithm is that it only takes 3p space where p is the number of neural network parameters\n\t\t- However the downside of Lanczos is that its prone to numerical instability and the $V$ may not be orthogonal. Typically standard implementations re-orthogonalize $V$ after every iteration. This loses the memory benefit of Lanczos. \n\t\t- The authors dub this version as hi-memory lanczos.\n\t\t- Instead of re-orthogonalizing at every step, an alternative strategy is to store all vectors and orthogonalize at the end. This approach still requires to store all vectors hence is not memory efficient. To make it more memory efficient, the authors propose to use sketching to store these vectors efficiently.\n\t- **Sketching**\n\t\t- Sketching is a technique to store high dimensional vectors to low dimensions so that expected norm of vector dot products is bounded.\n\t\t- The authors use Subsampled Random Fourier Transform (SRFT) to obtain the subspace embedding.\n- Finally, the authors combine the Lanczos algorithm with Sketching to propose the Sketched Lanczos algorithm.\n- The paper also proposes a slight modification of sketched lanczos which first runs hi-memory lanczos for few iterations followed by sketched lanczos iterations. The idea here is that running the high memory lanczos for few iterations results in a better conditioned matrix G'.\n- Finally the low rank decomposition of G is used to compute the variance of a prediction, which also gives the uncertainty score of a datapoint.", "questions": "### Questions\n\n- Given that memory consumption of the algorithm is $O(k^2.\\epsilon^-2)$. (Line 43) Since this does not depend on the number of parameters. Does this mean this can theoretically be applied to larger models? Also, how does this grow logarithmically in the size of model parameters?\n- What is the reason for dip in the AUROC beyond a certain memory cost in Figure 3 and Figure 4?\n- What is meant by \"number of NNs\" ? Do you mean number of neural network parameters?\n-", "limitations": "The authors have adequately addressed the limitations.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "### Strengths\n\n- The paper provides a good overview of various other ways of computing uncertainty and their associated limitations. Background on previous papers on which this work builds upon is also greatly appreciated.\n- Experimental results show that sketched lanczos is able to achieve AUROC similar to that of Vanilla lanczos with significantly lesser memory\n- The paper is comprehensive, with clear and accessible writing. The experimental results justify the claims made. The literature review provides a solid contextual foundation for the work and the background is thoroughly covered.", "weaknesses": "### Weakness\n\n- As I alluded to earlier, the models used in experiments are primarily vision models ranging from 40K params to 300K params, it's not clear whether this approach would work for NLP pre-trained models typically ranging in millions of parameters.\n- The datasets used are also primarily small scale vision datasets like CIFAR and MNIST.\n- However, I still value in this work and novel insights from authors in optimizing the Lanczos algorithm using Sketching.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- \"As I alluded to earlier, the models used in experiments are primarily vision models ranging from 40K params to 300K params, it's not clear whether this approach would work for NLP pre-trained models typically ranging in millions of parameters.\"\n\nWe made additional experiments, specifically, we used a 4M parameter Visual Transformer trained on the CelebA dataset. We also included an extra (easier) OoD dataset: FOOD101. The results are very good and included in the general response pdf. In the $3p$ budget setting our method clearly outperforms all baselines. In the $10p$ budget Deep Ensemble slightly outperforms in detecting FOOOD101 OoD, but our method still outperform all baselines for the more challenging hold-out-classes OoD datasets.\n\n- \"As I alluded to \n    The datasets used are also primarily small scale vision datasets like CIFAR and MNIST.\"\n\nThe submission also worked on the CelebA dataset which is not a small-scale vision problem. \nWith the updated experiments, we show again favorable performance on CelebA OoD detection with another and more modern architecture (Visual Transformer), in addition to the previously shown favorable performance on ResNet architecture. This experiments suggests that our method works irrespective of the choosen architecture.\n\n- \"Given that memory consumption of the algorithm is $O(k^2 \\epsilon^{-2})$. (Line 43) Since this does not depend on the number of parameters. Does this mean this can theoretically be applied to larger models? Also, how does this grow logarithmically in the size of model parameters?\"\n\n\n The actual space consumption is $O(k\\varepsilon^{-2} \\cdot \\log p \\cdot \\log(k / \\delta))$ as reported in Lemma 3.1 and 3.2. \nIn line 43, we say that the memory consumption of our algorithm scales \\emph{essentially} as $O(k^2\\varepsilon^{-2})$. In the introduction, we chose to ignore factors $\\log p$ and $\\log k/\\delta$ to make our result more understandable. The word \\emph{essentially} suggests that $O(k^2\\epsilon^{-2})$ is not exact but conveys the most relevant dependence. Indeed yes, this means this can theoretically be applied to larger models since the $\\log p$ term is neglectable even for a billion parameters model.\n\n- \"What is the reason for dip in the AUROC beyond a certain memory cost in Figure 3 and Figure 4?\"\n\nIn a nutshell, a sketch of size $O(k^2 \\epsilon^{-2})$ can only handle up to $k$ vectors and guarantee an absolute error $\\epsilon$ on our uncertainty score. If more than $k$ vectors are considered, the sketch becomes more noisy, which makes our uncertainty score more noisy and thus performs worse on OoD task.\n\n- \"What is meant by \"number of NNs\" ? Do you mean number of neural network parameters?\"\n\nIn our figures we measure the memory footprint of our algorithm as the number of trained models (NNs) one could fit in such space, exactly as the size of a Deep Ensemble would. We believe that such a unit of measurement is natural. Indeed, for large models, we expect to dispose of storage comparable with that used for the model itself but not orders of magnitude more than that.", "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": "0VT0tRh3DL", "reviewer": "Reviewer_y4fZ", "summary": "This paper provides a new algorithm for approximating the Fisher information matrix. Approximation of the Fisher information matrix is an important task whenever the amount of parameters is very large, such as the case for neural networks. This paper makes use of Lanczos algorithm to find an approximate spectrum of the Fisher information matrix, and particularly targets the low memory setting where such approximations are desirable. In particular, in this paper the authors show that:\n\n-Orthogonalization approximately commutes with sketching, making it feasible to sketch Lanczos vectors on the fly and orthogonalize them afterward. \n\n-Empirically, they demonstrate that in low-memory-budget scenarios, the disadvantage of introducing noise through sketching is outweighed by achieving a higher-rank approximation.", "questions": "Can the authors provide examples of when the embedding method works/fails. I believe it would be greatly beneficial to the reader if some intuition is shed on when this compression step is a useful computational resource and when it may greatly hinder performance.", "limitations": "The authors have not included a limitations section. I think this must be included in a future version and include the dependence of their methods performance on the sketching algorithm used.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This paper is well written and well motivated. Indeed, approximation of the Fisher information is an important task where the parameter count is very high. This paper introduces the regime where their approximation is necessary and provides assistance to the reader for these practical choices throughout the document. The authors detail when Lanczos algorithm is applicable and when it is limited. This naturally motives their algorithm of finding a spanning set of basis vectors for the Kyrlov subspace generated by Lanczos algorithm, and then performing the orthogonalisation. Clearly storing high-dimensional basis vectors is an issue. The authors use embedding techniques to minimise this storage requirement and provide compelling computational examples.", "weaknesses": "I do not see significant weaknesses with this paper. I think it would be nice if the choice of embedding procedure was better described in the main text. I believe that this might be a problem dependent choice, and whilst the authors have provided a good default choice, it would be good to know when their choice might give poor results, albeit if this seldom occurs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- \"I do not see significant weaknesses with this paper. I think it would be nice if the choice of embedding procedure was better described in the main text. I believe that this might be a problem dependent choice, and whilst the authors have provided a good default choice, it would be good to know when their choice might give poor results, albeit if this seldom occurs.\"\n\nThe embedding is done through multiplication with a sketch matrix. It is true that several choices can be made, an alternative to the \\texttt{srft} (used in all the reported experiments) is the \\texttt{dense} sketch (Theorem 4, [3]\n). You can try this alternative with the code provided in the submission by simply changing the command ``--sketch srft\" to ``--sketch dense\".\n\nThe choice of the sketch comes from the theoretical guarantees they offer. Specifically, we require it to be $(1\\pm \\epsilon)$ oblivious subspace embedding (Definition 2.1) and we require it to be memory efficient. We considered three candidate sketch matrices: SRFT (also named Fast JL transform) [1], Sparse JL transform [2] and Dense JL transform (Theorem 4, [3]). These three sketch matrices give different trade-offs in terms of matrix-vector product evaluation time and memory footprint, which we summarize in the following table.\nHere, $p$ is the original dimension (i.e., the number of parameters), $\\varepsilon$ is the approximation parameter for subspace embedding (as in Definition 2.1) and $s$ is the reduced dimension. Let $\\omega$ be such that the current best matrix-multiplication algorithm runs in time $n^\\omega$. \n\n|           | Time    | Memory |\n| ------- | -------- | ------- |\n| Dense JL | $O(p^\\omega)$  | $p^2$   |\n| Sparse JL | $O(p \\cdot \\varepsilon s)$ | $p \\cdot \\varepsilon s$    |\n| SRFT | $O(p \\log p)$    | $p + s$   |\n\nFrom the table above, it is clear that SRFT is best if our goal is to minimize memory footprint. At the same time, evaluation time is still quasilinear.\n\n[1] Ailon, Nir, and Bernard Chazelle. \"The fast Johnson–Lindenstrauss transform and approximate nearest neighbors.\" SIAM Journal on computing 39.1 (2009): 302-322.\n\n[2] Kane, Daniel M., and Jelani Nelson. \"Sparser johnson-lindenstrauss transforms.\" Journal of the ACM (JACM) 61.1 (2014): 1-23.\n\n[3] Woodruff, David P. \"Sketching as a tool for numerical linear algebra.\" Foundations and Trends® in Theoretical Computer Science 10.1–2 (2014): 1-157.\n\n\n- \"Can the authors provide examples of when the embedding method works/fails. I believe it would be greatly beneficial to the reader if some intuition is shed on when this compression step is a useful computational resource and when it may greatly hinder performance.\"\n\nThe embedding is theoretically guaranteed to work (i.e. to have a small error $\\epsilon$ with high probability) as long as the sketch size $s$ is big enough. This means that, as long as this condition is satisfied, there exist no examples where the embedding fails.\n\nTo be more explicit, for any choosen sketch size $s$, there exists some $\\epsilon$ such that the sketching is guaranteed to not exceed $\\epsilon$-error (with high probability). This of course means that for this technique to be of any use, such $\\epsilon$ needs to be small compared to the ground truth, and consequently $s$ needs to be ``big enough\". If $\\epsilon$ is on the same scale of the ground truth, then you essentially measure noise, and the method fails.\n\nFor example, in the synthetic data experiment (Figure 1 in the general rebuttal pdf) the ground truth is $~0.7$ (i.e. $1/\\sqrt2$). You can see that $s=200$ leads to an error of $0.3$ (so likely practically useless), while $s=5000$ leads to an error of $0.07$ (so likely practically useful).", "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": "9ZIf81dxAb", "reviewer": "Reviewer_nMeL", "summary": "In this paper, the authors present a memory-efficient way of computing the uncertainty score of a model (the variance of the model's prediction w.r.t. distribution over the model's parameters). Specifically, they combined Lanczos method and sketching to obtain a low-rank approximation of the Generalized Gauss-Newton (GGN) matrix, which is critical in computing the score but has a square size of parameters.\n\nThe authors first introduce the Lanczos method since the GGN matrix is more tractable as an operator. However, Lanczos requires re-orthogonalizing the output vectors, leading to extra memory consumption; while the authors' key observation is that the score only depends on the norm of matrix-vector product (Eq.9) which is only slightly influenced by sketching, therefore they can sketch the output on the fly, and conduct orthogonalization and compute the norm in the sketched subspace to save memory. Consequently, the proposed method is called Sketched Lanczos Uncertainty (SLU).\n\nFor validation, the authors tested the performance of SLU on out of distribution (OoD) detection tasks with models including MLP, LeNet, and ResNet. Results showed that SLU outperforms existing metrics, achieving a higher AUROC mainly in the low-memory budget scheme (as shown in Fig.3, 4, and Tab.1).", "questions": "1. Are there other ways of reducing the memory bottleneck in computing uncertainty scores? Since Eq.2 which authors leverage to compute the score is an approximation of the true variance, there may be better alternatives to it. For instance, is there a more computation/memory-efficient form of the covariance matrix $M$ that leads to better scores with less cost?\n2. For Tab.1, why do the authors fix the memory budget as $3p$? Looking forward to justifications for this choice.", "limitations": "1. The authors only considered the $M_\\text{noeig}$ case where singular values are 0/1, need to improve the flexibility of SLU to fit for other $M$s.\n2. The proposed method only works well for the low-memory setting. As the number of NNs increases, Sketched Lanczos deteriorates while vanilla hi-memory Lanczos work better. (Fig.3, 4)", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "Originality: Good. The authors are the first to incorporate sketching with approximate matrix eigendecompositions to reduce the memory footprint.\n\nQuality: Good. The authors provide a comprehensive analysis of their SLU method. For instance, in Fig.2 they illustrated the low-rankness of the GGN matrix and the efficacy of low-rank approximation, also with the core lemma 3.2 they showed the norm can be recovered by the sketched vectors and the sketching matrix.\n\nClarity: Good. The paper is well-organized for the readers to understand why each feature of SLU is proposed.\n\nSignificance: Fair. With SLU the authors compensate the sketching error with a higher-rank approximation and get better OoD detection results than baselines with a low-memory budget. SLU can also be applied to other tasks that require computing the norm of vector products with the U matrix.", "weaknesses": "Concerns of this paper are mainly around the experiment part:\n\n1. For the claim that \"the disadvantage of introducing noise through sketching is outweighed by a higher-rank approximation\" (lines 55~57), the authors should add a simple experiment with synthetic data to verify it.\n\n2. Experiment settings in this paper are too simple; expect to see results with larger-scale models such as Vision Transformers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- \"For the claim that \"the disadvantage of introducing noise through sketching is outweighed by a higher-rank approximation\" (lines 55~57), the authors should add a simple experiment with synthetic data to verify it.\"\n\nWe thank the reviewer for the valuable comment. We run an experiment on synthetic data and the results (Figure 1 in the main rebuttal pdf) confirms our claim. We now proceed to explain the setting.\n\nFor a given number of parameters $p$ and a given ground-truth rank $R$ we generate an artificial Fisher matrix $M$. To do so, we sample $R$ uniformly random orthonormal vectors $v_1 \\dots v_R\\in\\mathbb{R}^p$ and define $M = \\sum_i \\lambda_i v_i v_i^\\top$ for some $\\lambda_i>0$. Doing so allows us to (1) implement $x \\mapsto M x$ without instantiating $M$ and (2) have explicit access to the exact projection vector product so we can measure both the sketch-induded error and the lowrank-approximation-induced error.\n\nFor various values of $r$ and $s$, we run Skeched Lanczos on $x \\mapsto M x$ for $r$ iteration with a sketch size $s$, and we obtain the sketched low rank approximation $U_S$.\n\nWe generate a set of test Jacobians as random unit vectors conditioned on their projection onto $Span(v_1\\dots v_R)$ having norm $\\frac{1}{\\sqrt2}$. We compute their score both exacltly (as in Equation (9)) and sketched (as in Equation (10)). In the Figure we show the difference between these two values.\n\nAs expected, higher rank $r$ leads to lower error, and higher sketch size $s$ leads to lower error. Note that the memory requirement is proportional to the product $rs$, and the figure is in log-log scale.\n\n\nTo further clarify this results, on the x-axis we added the column \"inf\" which refers to the same experiments done without any sketching (thus essentially measuring Lanczos lowrank-approximation-error only) which coincides with the limit of $s\\rightarrow\\infty$. The memory requirement of this \"inf\" setting is $Pr$, that is the same as the second to last column where $s=P$.\n\n- \"Experiment settings in this paper are too simple; expect to see results with larger-scale models such as Vision Transformers.\"\n\nWe have extended the experiments with a 4M parameter Vision Transformer on CelebA dataset. Results are great (much better than the ResNet model included in the submission) and we provide figures and tables in the general rebuttal pdf.\nIn the $3p$ budget setting our method clearly outperforms all baselines. In the $10p$ budget Deep Ensemble slightly outperforms in detecting FOOOD101 OoD, but our method still outperform all baselines for the more challenging hold-out-classes OoD datasets.\n\n- \"Are there other ways of reducing the memory bottleneck in computing uncertainty scores? Since Eq.2 which authors leverage to compute the score is an approximation of the true variance, there may be better alternatives to it. For instance, is there a more computation/memory-efficient form of the covariance matrix $M$ that leads to better scores with less cost?\"\n\nThis is a great question and the whole line of research that we reviewed in our related work section aims at answering exactly this question.\n\nThere are indeed several works that study memory efficient approximation of the matrix $M$, as referred to in the paper, the most notable are diagonal, block diagonal, and Kronecker factorization. Out of these three, we compare with the first one and outperform it, we didn't include the second one because it requires too much memory and, lastly, we didn't include the third one because it is an architecture-dependent approximation and current implementations are very restricted only to some specific types of network (differently from our model, which is architecture agnostic).\n\n- \"For Tab.1, why do the authors fix the memory budget as $3p$? Looking forward to justifications for this choice.\"\n\nThis is an interesting question. Our goal was to show the superiority of SLU in a low-memory regime. Given the number of baselines and ID-OoD dataset pairs, we chose to fix the memory budget in order to display our results more easily.\n\nThen why $3p$ and not $2p$ or $5p$? This was indeed an arbitrary choice. We used both $3p$ and $10p$ (in the Appendix) as we thought this was enough to show the behavior of the method. If the reviewer thinks some different values would be interesting we are happy to run those experiments as well and include them in the paper.\n\nMoreover, we are open to suggestions on experiments without a fixed memory budget and we would be happy to include them.", "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:
We are grateful for the positive and constructive reviews that we reply to individually below. Some of the individual replies refer to figures and tables that are provided in the PDF attached to this message. These figures provide the requested additional experiments, including demonstrating results on vision transformers and synthetic data experiments.

The additional large-scale experiments are presented in Table 1 and Figure 2. Here we use a $4M$ parameter vision trasformer trained on CelebA, this network is able to train much better compared to the previous ResNet and, consequently, it leads to much better OoD performance. Additionally, given the difficulty of the 3 class-out datasets, we included a new (more out-of-distribution) dataset: FOOD101.

The synthetic data experiment is shown in Figure 1 and it supports the claim ``the disadvantage of introducing noise through sketching [going left on the x-axis] is outweighed by a higher-rank approximation [going up on the y-axis]" that we made in line lines 55-57. Note, for example, the two points $(s,r)=(\textnormal{inf},2)$ and $(s,r)=(20000,100)$ have the same memory requirement. At the same time, they have very different errors: 0.495 and 0.061, respectively.


We hope to have alleviated all concerns and are looking forward to further discussion.

Meta-review: This paper proposes a memory-efficient method for producing uncertainty scores. The main idea is to use a rank-k sketch of the empirical Fisher information matrix, which can be obtained using the Lanczos iteration. The Lanczos iteration is memory-efficient, and the orthogonalization step can be done post-hoc, introducing further memory savings. 

The reviews are overall supportive of the paper. Reviewers appreciate the clear motivation, novel method, and the experimental validation of the approach. The concern around the scale of the experiments was largely resolved during the rebuttal phase with additional experiments. Given the positive feedback, I recommend acceptance.
Decision: Accept (poster)