Representing Model Uncertainty of Neural Networks in Sparse Information Form
Authors: Jongseok Lee
Rudolph Triebel
Venue:  (2020)
Keywords: Model Uncertainty
Neural Networks
Sparse representation

Abstract: This paper addresses the problem of representing a system's belief using multi-variate normal distributions (MND) where the underlying model is based on a deep neural network (DNN). The major challenge with DNNs is the computational complexity that is needed to obtain model uncertainty using MNDs. To achieve a scalable method, we propose a novel approach that expresses the parameter posterior in sparse information form. Our inference algorithm is based on a novel Laplace Approximation scheme, which involves a diagonal correction of the Kronecker-factored eigenbasis. As this makes the inversion of the information matrix intractable - an operation that is required for full Bayesian analysis, we devise a low-rank   approximation of this eigenbasis and a memory-efficient sampling scheme. We provide both a theoretical analysis and an empirical evaluation on various benchmark data sets, showing the superiority of our approach over existing methods.

Under review as a conference paper at ICLR 2020
REPRESENTING MODEL UNCERTAINTY OF NEURAL NETWORKS IN SPARSE INFORMATION FORM
Anonymous authors Paper under double-blind review
ABSTRACT
This paper presents a sparse representation of model uncertainty for deep neural networks (DNNs) that relies on an inverse formulation of Multivariate Normal Distribution (MND): be estimated in this form using scalable Laplace Approximation scheme, which involves a diagonal correction of the Kronecker-factoree eigenbasis. As this makes the inversion of the information matrix intractable an operation that is required for full Bayesian analysis, we further devise novel low-rank approximation of this eigenhasis that exploits spectral sparsity of DNNs. Methods to realize this sparsification are provided that develops into a memory- tractable sampling computations. Both of our theoretical analysis and empirical evaluations over various benchmarks show the superiority of our approach over existing methods.
information form. We show that the model uncertainty can
INTRODUCTION
Whenever machine learning methods are used for safety-critical applications such medical image analysis or autonomous driving, it is crucial to provide a precise estimation of the failure probability of the learned predictor. Therefore, most of the current learning approaches return distributions rather than single, most-likely predictions. For example, DNNs trained for classification usually use the softmax function to provide a distribution over predicted class labels. Unfortunately, this method tends to severely underestimate the true failure probability, leading to overconfident predictions (Guo al. 2017). The main reason for this is that neural networks are typically trained with a principle of maximum likelihood, neglecting their epistemic model uncertainty with the point estimates.
widely known work by Gal (0016) shows that this can be mitigated by using dropout at test time. This so-called Monte-Carlo dropout (MC-dropout) has the advantage that it is relatively easy to use and therefore very popular in practice. However, MC-dropout also has significant drawbacks. First, requires a specific stochastic regularization during training. This limits its architectures, because current networks are often trained with other regularization techniques such as batch normalization. Moreover, it uses Bernoulli distribution to represent the complex model uncertainty, which in return, leads to an underestimation of the predictive uncertainty.
already well trained
Several strong alternatives exist without these drawbacks. Variational inference (Khan al. 2018 Kingma et al.) 2015) Graves 201T) and expectation propagation (Herandez- Lotratdez-Lobato Lobato & Adams 2015) are such examples. Yet, these methods use a diagonal covariance matrix which limits their applicability as the model parameters are often highly correlated. Building upon these, Sun et al. (2017): Louizos Welling (016); Zhang et al. (2018); Ritter et al. (2018a) show that the correlations between the parameters can also be computed efficienlly by decomposing the covariance matrix of MND into Kronecker products of smaller matrices. However, not all matrices can be Kronecker decomposed and thus, these simplifications usually induce crude approximations (Bae et al. 2018)) 8). As the dimensionality of statistical manifolds are prohibitively too large in DNNs, more expressive, efficient but still easy to use ways of representing such high dimensional distributions are required.
To tackle this challenge, we propose to represent the model uncertainty in sparse information form of MND. As a first step, we devise a new Laplace Approximation (LA) for DNNs, in which we improve the of-te-of-the-art Kronecker factored approximations of the Hessian (George et al. 20088) by correcting the diagonal variance in parameter space. We show that these be computed effccintll, and that the information matrix of the resulting parameter posterior is more accurate in terms of the Frobenius norm. In this way the model uncertainty is approximated in information form of the MND.

---

Under review as a conference paper at ICLR 2020
(a) Problea Ilatei
FC
(b) Spectrun
(o) Main Idea
1. Information Matrix
CNN
Baaten
moter, nour 0.0
Hatten
Laplace
nuro
3136
IDAK at 0.035
Tx7x61
1024
((N
aggnvaalsss [-]
O(N3) >> O(L
Diagonal Correction
samples 03
N3 x
most beat 0.0
6 -10-
//0 12 ~ (a),
Ng 3211222111 1264
-igerssatues
Sampling Wi-ie Fash
Spansificttion
Main idea. (a) Covariance matrix Σ for DNNs is intractable infer, store and sample (an example taken from our MNIST experiments). (b) Our main insight is that the spectrum (eigenvalues) of information matrix (inverse of covariance) tend be sparse. (c) Exploiting this insight Laplace Approximation scheme is devised which applies a spectral sparsification (LRA) while keeping the diagonals exact. With this formulation, the complexity becomes tractable for sampling while producing more accurate estimates. Here, the diagonal elements (nodes in graphical interpretation) corresponds information content in parameter whereas the corrections (links) are the off oif-diagos.ls.
Figure 1:
As this results in intractable inverse operation for sampling, we further propose novel low-rank representation of the resulting Kronecker factorization, which paves the way to applications on large network structures trained realistically sized data sets. To realize such sparsification, propose novel algorithm that enables a low-rank approximation of the Kronecker factored eigenvalue decom- position, and we demonstrate that our approach effective in providing more accurate uncertainty estimates and calibration on considered benchmark data sets. A detailed theoretical analysis is also provided for further insights.
associated sampling computations. Our experiments demonstrate
We summarize our main contributions below.
novel Laplace Approximation scheme with a diagonal correction the eigenvalue re- scaled approximations of the Hessian, as a practical inference tool (section 2.2
A novel low-rank representation of Kronecker factored eigendecomposition that preserves Kronecker structure (section 2.3 This results in a sparse information form of MND.
A novel algorithm to enable low rank approximation (LRA) for the given representation of
MND (algorithm) T and derivation of a memory-wise tractable sampler (section B.2).
Both theoretical (section C) and experimental results (section 4 showing the applicability of our approach. In our experiments, we showcase the state-of oott--of-theant performance within the class of Bayesian Neural Networks that are scalable and training-free.
To knowledge explore sparse information form to represent the model uncertainty of DNNs for the first time. Figure depicts our main idea which we provide more rigorous formulation next.
2 METHODOLOGY
2.1 BACKGROUND AND NOTATION
We model neural network a parameterized function RM R where R are the weights and N₂ N1 + +... + N,. This function fo is fact a concatenation of layers, where each layer E (l..../) computes
Waa- and a d(h-1). Here, & is a nonlinear function, ai are activations, hy linear pre-activations, and W; are weight matrices. The bias terms are absorbed into vec(W))7 where vec is the
W: by appending to each a. Thus, 0 = [ve vec(W,)² operator that stacks the columns of a matrix to a vector. Let gi = Sh, the gradient of h; w.r.t 0.
Using LA the posterior is approximated with Gaussian. The mean is then given by the MAP estimate OMAP and the covariance by the Hessian of the log-likelihood (H + r!)-1 assuming a Gaussian prior with precision Using loss functions such as MSE cross entropy and piece-wise linear activation 4;
2

---

Under review as a conference paper at ICLR 2020
(e.g RELU), good approximation of the Hessian is the Fisher information matrix (IM) I E 8060
for the backpropagated gradients 60 I and is typically scaled by the number of data points N (Martens & Grosse 2013). IM is of size N, No resulting in too large matrix for moderately sized DNNs.
To make the computation tractable, a number of approximations are applied. First, it is assumed that the weights across layers uncorrelated, which corresponds to block-diagonal form of I with blocks J, I...... Jt- Then, each realisation of block I; is represented as a Kronecker product 50 d--1d @ gig This has an advantage that the inverse can be computed efficiently using (A G) A-1 G Then, matrices A:- and Gi are assumed be statistically independent:
Jkti = =B - gig = B [aa-aa=1] 3 B gig
A,11 @ Gi.
We refer to Martens & Grosse 2015) for details on KFAC. Here, A E R and G E R where the number of weights N; = nim: Applying equation to LA (Ritter al. [018a), the parameter posterior per layer can be represented with a matrix normal distribution MN (defined in section A).
p(0 x, ~ ((Vee(W..MA)) (ifae) MMN(W..APP
Typically IM is scaled by the number of data points N and incorporates the Gaussian prior r. The herein presented parameter posterior omits the addition of prior precision and scaling term for simplicity. Further note that, in practice, N and are treated hyperparameters (Ritter et al. 2018a).
NI, + r/ (VNA,- + vFl) @ VNG + VFi).
KFAC scales to big data sets such as ImageNet (Krizhevsky et al. 2012) with large DNNs (Ba al. and does not require changes in the training procedure when applied to LA.
2017
2.2
LAPLACE APPROXIMATION WITH DIAGONAL CORRECTION
Following George et al. (2018), we first employ an eigenvalue correction the Kronecker factored eigenbasis for LA. For simplicity, we drop layer indices and explanation herein applies layer-wise.
Let I= Vinue/ vT be the true eigendecomposition of IM per layer. From this it follows Arme 50); for elements of layer wise matrices E (1,2. .N).
E V.Th 5656" Vuue] and Ame.. E [V [V
U and further follows Line & (U, @ UG) A 8 &S& (U, @ Ug)" from the properties of the Kronecker product. Now, this approximation can be improved by replacing (S, @ Sc) with the eigenvalues A
Defining the cigendecomposition of and G in equation 1 as
U
where Vine is set to (UA @ UG) resulting in A B [[U( & Up) (e)]) We denote it EFB:
(4) This technique has many desirable properties. Notably, it holds I|I Labllr S I Ixtaell wrt. the Frobenius norm as the computation is more accurate by correcting the diagonal the eigenbasis.
Lab = (U, & U,)A(U, @ U and I (U, @ U & U.)
However, there is an approximation in EFB since (UA @ UG) is still an approximation of the true eigenbasis Vune- Intuitively, EFB only performs a correction the diagonal elements in the eigenbasis, but when mapping back to the parameter space this correction is again harmed by the inexact estimate of the eigenvectors. Of course, an exact estimation of the eigenvectors is infeasible, but it is important to note that the diagonals of the exact IM I = E [0? can be computed efficiently using back- propagation. This and the fact that the off diagonal elements of the IM are weaker with larger data sets or when using weight normalization (Neyshabur al. (2016); Desjardins et al. (2013); [Saliaan & Kingma (2016)), motivates the idea to correct the approximation further as follows:
Ias (UA & Un)A(U @ Un) + D where D,, B 688
Σ (ViJ A
(5)
Thee expectation herein is defined wrt. the paramerterized density po(y))) assuming i.i.d. samples
3

---

Under review as a conference paper at ICLR 2020
(Va Un)A(U, @ Uu)" ze (VAL. @ Ue, MMnlUA.. @ U
NxN
T
n m X
LXL
nxa m x
X.X.
E (L. m) 9 (1,
mia- +7 mf +)+{
E (1,-. my ( E (1,-. m)
E (1, .. m)
= mla - 1) +
E (1, 1. m)
indiciugs
m)
g {1, .. .a)
= mif - 1)
c (1. (1)
Figure 2: Sparse Information Matrix. We perform a low rank approximation on Kronecker factored cigendecomposition that preserves Kronecker structure in eigenvectors for two reasons: (a) reducing directly (UA & Ua)az is memory-wise infeasible, and (b) sampling scheme then only involves matrix multiplications of smaller matrices UAm.. and UG Notations on indicing rules also depicted.
In equation 5. have represented (U,eUa)\(Ux@Uee) as Σ Li=(v A where V (U,@
Rmmnomr is a Kronecker product with row elements V1, (see definition below). It follows from the properties of the Kronecker product that m(a 1) + y. The derivation is shown in section Note that in this given form, the Kronecker products are never directly evaluated but the diagonal matrix D can be computed recursively, making it computationally feasible.
Definition 1: For UA E Ruxe and UG E R_xx, the Kronecker product of V UA @ UG E R.mxom is given by Vi, L,, with the indices i mía - 1) + y and j mB Ç. Here, the indices of the matrices UA and UG are E (1,... n), B (1,... .),, y E [1...., m) and Ç (1,... ,)).
Now, the parameter posterior distribution is represented in an information form or inverse formulation N-1 of MND as shown in equation 6 which is parameterized by an information vector W [- veeo (MAP) and matrix Ter from equation
MAP
Section A provides the formulation.
p0 | x.y) N((veC( Idd)
- (WMP MAP (UA Uo)A(U, Un) D
(6)
Unfortunately, in the current form, involves matrix inversion with size N by N when sampling. For some layers in modern architectures, this is not be feasible. This problem is tackled next.
2.3 REPRESENTING MODEL UNCERTAINTY IN SPARSE INFORMATION
Sampling from the posterior is crucial. For example, an important use-case of the parameter posterior estimating the predict uncertainty for test data (x', yy) ) by a full Bayesian analysis with K,n samples (equation 7
The herein approximation step is so-called Monte-carlo integration (Gal 2016).
x(''xx'x,,)) f 0pt"xx" = Kme
Σ y'xx00)) for 0 -- 1=1
(MPPs
MAP Iser)
(7)
However, directly sampling from equation 6 is non-trivial as explained in an example below.
Example 1: Consider the architecture from figure 7 where the covariance matrix Σ3 RRNNN for N3 = 321 1264. With equation 6 the sampling requires O(N)) complexity (the cost of inver- sion and finding a symmetrical factor) and obviously, this operation is computationally infeasible. Consequently, we next describe sparse formulation of equation 6 that ensures tructability.
To tackle this challenge, we propose the low rank form in equation as a first step. Here, ^nd. E [RLxL UAi E m and UG,- RR*x denote low rank form of corresponding eigenvalues and vectors (depicted in figure 2) Naturally, it follows that = ag. N = mn and furthermore, the persevered rank L corresponds to preserving top K and additional J eigenvalues (resulting in L 2 K, L ag = K J).
Laet Las (Un,, & UG AU, @ UG y +D
(8)
Note that the term is added after I.R.A where D computed similar equation
4

---

Under review as a conference paper at ICLR 2020
2. Compute m/)())) and { mLf -011-1)
4. Compute 2 m +)++5 for all @ and
K
Find top eigenvalues
3. UA UA..
UA and Uc +> Uo..
Uo.
A1
Figure 3: Illustration of algorithm 1 A low rank approximation Kronecker factored eigende- composition that preserves Kronecker structure in eigenvectors constitutes steps I to 5.
Note the difference to preserving top L eigenvalues and corresponding eigenvectors (Bishop 2006 for LRA. our case, this results in intractable (U^ @ UGhız which defies the purpose. Therefore, as seen in equation 88 the Kronecker structure in eigenvectors as (UA,, @ UG...) is preserved. Consequently, due to the Kronecker product operation, preserving top K eigenvalues results
K eigenvaluus.
Example 2: Let matrix E decomposed as UUGAASU R with UL.6 =
[
U2
u6
R and A16 diag(Ai, A,,,..... .A6) with top 3 eigenvalues result in E13 UraArUU E R266 (see notation to above). Instead, consider now the matrix ExsOn = (UAla 2UG ( DUm))" E RR6x Again, say we want to preserve top 3 the eigenvalues A13 and corresponding eigenvectors (UA.. @ 33G.,,3, However, as (U (UG..) @ MG: uΛ, @ ue. preserving the eigenvectors with the Kronecker structure results in having to store UA12 =
E R6x6 in descending order. In this toy example, the LRA
UA, @ MG..
=[wA, Ws and = =|ma, uGa] Consequently, additional eigenvalue Na has to be saved in order to fulfill the definition of Kronecker product Ezrom1 = (UA1z @ UG (i=(UA & UGT.)" R6x6, In summary, preserving top K eigenvalues results in other J eigenvalues, which ensures the memory-wist tractability when performing LRA on large matrices.
Then, how do we compute low rank approximation that preserves Kronecker structures in eigenvec- tors? For this computation we propose algorithm [ as an algorithmic contribution (also illustrated in figure 3). Let us start with definition on indexing rules of Kronecker factored diagonal matrices.
Definition For diagonal matrices S E R and S E mmm the Kronecker product of SA @ SG monzou is given by A; SapSyz, where the indices i = m(ß - 1) + { with /3 (1, m) and { E (1.....
Then, given and m. B = inr( [ + and given B, m, and i, 5 = i- m(B - 1). Here, int(.) is an operator that maps inpul to lower number integer.
Notations in algorithm arre also depicted in figure 2 Now we explain with toy example below.
Example 3: For explaining algorithm the toy example can be revisited. Firstly, as we preserve top 3 eigenvalues, i E 2,,2,3) 2 which are indices of eigenvalues Ava (line 1). Then, using line 2, B E (1, 2) and E (1, can be computed using defimition This relation holds as is computed from S @ S.. and thus, UA and UG are their corresponding eigenvectors respectively. In line 3, we keep UAm and UG.. using & and Ç. Again, in order to fulfill the Kronecker product operation, line 4 find the eigenvalues jE (1,2,3,4), 4), and then preserve A1a- As explained, this has resulted in saving top 3 and additional I eigenvalues. Algorithm provides the generalization of this and even if eigendecomposition does not come with a descending order, the same logic trivially applies.
The incorporation of prior regularization terms also follows without any additional approximation.
Ni + =/= (UA) UG.,) (UN, @ UG..)" (ND + r/)
Sampling: A key benefit of the proposed LRA that now, sampling from the given covariance (equation o with the low rank form in equation 8 equation with an incorporation of priors) only involves the inversion Kronecker factored matrices or diagonal matrices during full Bayesian analysis. To this end, derive the analytical form of the sampler section B.2 which makes the sampling computations feasible. This enables to bound the intractable complexity of O(N²) to O(1.) for I. << N.
L x matrix (in offine settings) and matrix multiplications of smaller
5

---

Under review as a conference paper at ICLR 2020
Algorithm 1: Sparsification
Algorithm 2: Inference of IM
Input: Matrices UA. UG. A and Rank K.
Input: Pre-trained Neural Network and train data.
Output: Matrices: UAie: Un Aua-
Output: Matrices: UAix" Usia Aug and
Algorithm:
Algorithm:
1. Find indices of top K eigenvalues on A. This results in indices E [1....AA .K).
for the given data points do KFAC
for i to do
Compute A; and G; (equation
2. For each elements of i, find corresponding indices of each Kronecker factors of original matrix S Sg by using definition 2: B = inn( [.) + and < = i- mmß 1188-10 1). This results in indices of /8 and Ç for U, and UG
end
end
Compute UA. UG with eigenvalue decomposition. for the given data points do EFB for to do
corresponding to SA @ S Λ1xx = A, Using obtained indices / and C, compute eigenvectors AL = UA and UG., Uoz. These are the preserved cigenvectors in equation 8
Compute 1666 Compute Ag with UA and Ug.
end
4. Find indices of top K and additional eigenvalues using j = m(B 1) for all B and Ç.
end for all the layers do DEF (without involving data)
5. Preserve eigenvalues Aut = Ay where j / j. Aui represents the preserved top K and additional J cigenvalues in equation 8
Compute UAiy Ug Aut (algorithm 1). Compute D (equation
end
Overview: An overview is depicted in figure I where we first show that IM of DNNs tend to be sparse in its spectrum (similar to the findings of Sagun et al. (018)). With this insight we propose to represent the parameter posterior in sparse information form which visualized with its graphical interpretations. From IM of EFB, we apply our LRA that weakens the strengths of weak nodes (diagonals of IM) and links (off-diagonals) be added to keep the information of each nodes exact. A key benefit is that the sampling computations can be achieved in a memory-wing feasible way. Algorithm Sattmmmssooo shows the overall procedures. Further note that, IM is estimated after training, is also computed in a different way to George et al. (2018) so that our EFB does not require batch assumption for taking expectations, and the scheme is cheaper since eigenvalue decomposition of A;-1 and G; are computed only once. Computing diagonal correction term also does not involve data.
preserving fashion. Then, diagonal correction can
method can be applied to existing architectures. EFB
p(0 x. ~ - MMPP: (UA,, @ UG,,, MIL.UAA @ UG J + D)
(10)
As result our approach yields sparse information form of MND where the IM has low rank eigendecomposition plus diagonal structure that preserves Kronecker structure in eigenvectors (shown above; prior and scaling terms are omitted keep the notation uncluttered; WiV an information vector associated to the proposed IM). Since this formulation of model uncertainty has not bee studied before, we provide theoretical results in section for further insights and justifications.
RELATED WORKS
Sparse Information Filters: A similar idea of sparsifying the information matrix while keeping the diagonals accurate can be found in sparse information filters. Here, Bayesian tracking is realized in information form of MND instead of canonical counterparts (Kalman Filters). As this leads to inefficiency in marginalization, sparsity is introduced while keeping the diagonals accurate (Thrun al. 2004). main difference, however, that DNNs typically have higher dimensions and a sparse structure in the spectrum (eigenvalues) in contrast to spaces of parameters in SL.AM problems. Thus, we propose to explore Kronecker factorization and induce spectral sparsity or L.A respectively.
Approximation of the Hessian: The Hessian of DNNs is prohibitively too large as its size is quadratic to the parameter space. For this problem an efficient approximation is a layer-wise Kronecker factorization (Martens & Grosse 2015 Botev et al., (017) which have demonstrated notable scalability (Ba et al.] 2017). a recent extension of (George et al. 2018) the eigenvalues of the Kronecker factored matrices re- re-scaled so that the diagonal variance in its eigenbasis is exact. The work demonstrates a provable method of achieving higher accuracy. Yet, as this is harmed by inaccurate estimates of eigenvectors, further correct the diagonals in the parameter space.

---

Under review as a conference paper at ICLR 2020
150
150
150
350
50
50
50
50
-30
120
130
-330
-300
220
220
-230
220
Diag Laplace
KFAC Laplace
FB Laplace
Ours (DEF)
150
150
150
150-
100-
130-
50
50
-30
-10
-120
-120
-190
-250
-4
-230
-230
-200
-4
BBB
EFB Laplace
DEF with L=1
HMC (ground truth)
Figure 4: Uncertainty toy regression. The black dots and the black lines are data points (x, y)- The red and blue lines show predictions of the deterministic Neural Network and the mean output respectively. Upto three standard deviations shown with blue shades.
Laplace Approximation: Instead of methods rooted in variational inference (Hinton & van Camp 1993) and sampling (Neal, 1996), we build upon LA (MacKay 1992) as a practical inference framework. Recently, diagonal (Becker & Lecun 1989) and Kronecker- factoredd approximations (Botev et al. (017)) to the Hessian have been applied to LA by Ritter et al. (2018a). The authors have further proposed
LA in continual learning (Ritter al. (018b), and demonstrate competitive results by significantly outperforming its benchmarks (Kirkpatrick et al. 2017,Zenke Zenke et al. (017). expressive posterior distribution than matrix normal distribution. In the context of variational inference, SLANG (Mishkin et al. 2018) share similar spirit to ours in using low-rank plus diagonal form of covariance where the authors show the benefits of low-rank approximation in detail. Yet, SLANG is different to ours as they do not explore Kronecker structures and requires changes the training procedure.
Building upon Ritter al. (2018a) for approximate inference, propose
Dimensionality Reduction: A vast literature is available for dimensionality reduction beyond principal component analysis (Wold al.) 1987) and singular value decomposition (Golub & Reinsch 1971 Van Der Maaten al.) (009). To our knowledge though, dimensionality reduction in Kronecker factored eigendecomposition that maintains Kronecker structure of cigenvectors has not been studied before. Thus, propose algorithm I and further provide its theoretical properties in section C
4 EXPERIMENTAL RESULTS
An empirical study is presented with toy regression and classification tasks across MNIST (Lecun eet al. 1998), notMNIST (Bulatov] 2011). CIFARIO (Krizhevsky) 2009) and SHVN (Netzer et al. designed to demonstrate the quality of predictive uncertainty, effects of varying LRA, the quality of approximate Hessian, and gains in reduction of computational complexity due LRA. All experiments are implemented using Tensorflow (Abadi et 2016).
2011 data-sets. The experiments
4.1 Toy REGRESSION AND EFFECTS OF Low RANK APPROXIMATION
Predictive Uncertainty: Firstly, evaluation toy regression data-set is presented. This experi- ment has an advantage that we can not only evaluate the quality of predictive uncertainty, but also directly compare various approximations to the Hessian. For this single-layered fully connected
7

---

Under review as a conference paper at ICLR 2020
(TAC
04:
FF6
CPTNF
County
dimension [%]
dimension [%]
dimension [%]
eigenvalues [-]
(a) Diagonal error
(b) Off-O off-diagonal error
(c) Overall error
(d) Eigenvalues
Figure 5: Effects of Low Rank Approximation in Frobenius norm of error. This measure is normalized from O to 1. Lower the better. Laplace based methods such as EFB, Diag, KFAC and DEF are compared in terms of diagonal, off-diagonal and overall resulting approximation error to exact block diagonal hessian. Eigenvalue histogram is also plotted.
network with seven units in the first layer is considered. We have used 100 uniformly distributed points x U(-4,4) and samples
N(x², 32). Visualization of predictive uncertainty is shown in figure HMC (Neal 1996). BBB (Blundell et al., 2013), diagonal and KFAC Laplace |Rttter et al. (0018a) have been included as a comparison whereas EFB Laplace, exact block diagonal Hessian (FB) and DEF with a full rank and one rank are presented for an ablation study. Both Diag and KFAC Laplace are tuned similar to Ritter et al. (0188) by regularizing them. DEF variants and FB Laplace for this experiment did not require prper-paramter tuning. Implementation details are in section E
All the methods show higher uncertainty in the regimes far away from training data where BBB showing the most difference to HMC. Furthermore, Diag, KFAC and EFB Laplace predicts rather high uncertainty even within the regions that are covered by the training data. DEF variants slightly underestimate the uncertainty but produces the most comparable fit to the FB Laplace and HMC (our ground truths). We believe this is the direct effect of modelling the Hessian more accurately 3l Moreover, since the only difference between EFB and DEF Laplace is a diagonal correction term, this empirical results suggest that keeping diagonals of IM exact results in accurate predictive uncertainty.
Effects of Low Rank Approximation: Next, we quantitatively study the effects of LRA by directly evaluating on the approximations of IM. This is because uncertainty estimation, despite being a crucial entity, are confounded from the problem itself and may reveal the algorithmic insights to its full potential. For this, we revisit the toy regression problem and provide a direct evaluation IM with measure on normalized Frobenius norm of error ertyp in the first layer of the network.
The results are shown in figure 5 Here, the reduced dimension is not proportional to the ranks (e.g. many zero or close eigenvalues). Figure 5 (a) depicts that DEF results in accurate estimates on I regardless of the chosen dimensions while EFB has the more approximation error, which we helieve due inaccurate estimates of eigenvectors. KFAC on the other hand, produces the most errors on diagonal elements, which indicate that its assumption of Kronecker factorization induces crude approximation in this experiment. Regarding the off off-diagonal errors EFB also outperforms KFAC and Diag estimates. Furthermore, error profile of off-diagonal error Iūj also explains the principles of the LRA that as we decrease the ranks, the error increases but a preserving manner. These results can also be explained by Lemma I and 4 of section C which reflects the design principles of the method.
4.2 CLASSIFICATION AND REDUCTION IN COMPLEXITY
Predictive Uncertainty: Next, we evaluate predictive uncertainty on classification tasks in which the proposed low-rank representation is strictly necessary. Furthermore, our goal is not to achieve the highest accuracy but evaluate predictive uncertainty. To this end, we choose classification tasks with known and unknown classes, e.g. network is not only trained and evaluated on MNIST but also tested using notMNIST. Note that under such tests, any probabilistic methods should report their evaluations on both known and unknown classes with the same hyperparameter settings. This is because a Bayesian Neural Network to be always highly uncertain, which may seem to work well on
comment this statement, and the effects of data-set size to number of parameters in section P
8

---

Under review as a conference paper at ICLR 2020
out-of-distribution samples but are always overestimating uncertainty, even for the correctly classified samples within the distribution similar to the train data. For evaluating predictive uncertainty on known classes, Expectation Calibration Error (ECE) has been used. As we found it more intuitive, normalized entropy is reported for evaluating predictive uncertainty on unknown classes.
Table I: Results of classification experiments. Accuracy and ECE are evaluated on in-domain distribution (MNIST and CIFARIO) whereas entropy is evaluated aut-of-distribution (notMNIST and SHVN). Lower the better for ECE. Higher the better for entropy and accuracy.
MNIST
NN
Diag
KFAC
MC MC-dropout
Ensemble
EFB
DEF
Accuracy
0.993
0.9935
0,9929
0,9922
0.9937
0,9929
0.9927
ECE
0.395
0.0075
0,0635
0.012
0,0069
Entropy
0.0
0.555 + 0.196
0.599 + 0.199
0.562 + 0.19
0.596 0.133
0.618 + 0.185
0.635 0.19
CIFAR
NN
Diag
KFAC
MC-dropout
Easemble
EFB
DEF
Accuracy
0.8606
0.8659
0,8572
N/A
0.8651
0.8638
0.86446
ECE
0,0819
0.0358
0.0351
N/A
0,0809
0.0343
0,0084
Entropy
0,245 0.215
0,4129 0.197
0.408 0.197
N/A
0.370 0.192
0.417 0.166
0.4338 0.18
10000
aees in-dist
10005
in-dist
MNIST
Dim N-1
Dim [-]
Percent (%)
2000
$008
out-dist
2002
out-dist
CNN-7
800
450
56.25
CNN-2
51200
5185
10.12
Conut [-]
8000
5000
FC-1
3211264
5625
0.18
FC-2
10240
46.63
CIFAR
Dim NI-1
Dim L [-]
Pereent [%)
CVN-7
4800
4800
CNN-2
102400
2112
2.06
FC-I
884736
3980
0.45
FC-2
73728
5499
7.45
Entropy
-1
Entropy H
FC-3
1920
1920
100
Figure 6: Normalized Entropy histogram (left: DEF Laplace and right: deterministic) on MNIST vs notMNIST experiments. Our method clearly and wrongly clas- sified samples (out-dist) to the correctly classified samples from in-domain distribution (in-dist).
Table 2: Reduction in complexity. Reduced di- mensions from N to the chosen rank I. per layer are reported for both MNIST and CIFAR experi- ments. CNN stand for convolution while FC is for fully connected layers. The complexity of sam- pling computations O(N²) are reduced to O(L").
separates the out-of-distribie
On W.IISTTooMNNISTT experiments, we compare MC-dropout (Gal
2016). ensemble (Lakshmi
narayanan et al., 2017) of size 15, Diag and KFAC Laplace (Ritter et al. 201 8a). These methods are state-of-the-an baselines that have a merit of requiring no changes the training procedure. The later is crucial for fair comparison as we can use the same experiment settings (Mukhoti et al. 2018). Regarding the architectures, LeNet with RELU and L2 coefficient of 1c-8 has been the choice. In particular, this typically makes neural network overconfident, and we can see the effects of model uncertainty. This architecture validates our claim as it has the parameters of size 03 E IR 1g3137x100 1024 in the 3rd layer. Obviously, its covariance is intractable it is quadratic in size (see figure Dp. The results can be found in table [ Firstly all the methods improved significantly over the deterministic one (denoted NN). Furthermore, DEF Laplace achieved here the lowest ECE, the same time, predicted with the highest mean entropy on out-of-distribut method separates between wrong and correct predictions which stems from the domain change.
samples. Figure shows this result where our
Further tests were performed on CIFAR 10 (known) and SVHN (unknown) to see the generalization under batch normalization and data augmentation. For this, we trained a 5 layer architecture with CNN and 3 FC layers. The results are also reported in table [ Similar to MNIST experiments. our method resulted in better calibration performance and -iitt-diitributiion detection overall. Note that for Diag, KFAC and EFB Laplace, grid searches hyperparameters were rather non-trivial here. Increasing r/ had the tendency to reduce ECE on CIFARÍC 10, but return resulted in underestimating the uncertainty SVHN and vice versa. DEF Laplace instead, required smallest regularization hyperparameters to strike a good balance between these two objectives. We omitted dropout as using it stochastic regularization instead of batch normalization would result in different network and thus, comparison would be not meaningful. More implementation details are provided section
Reduction in Complexity: The proposed LRA has been imposed as means to tackle the challenges of computational intractability of MND. To empirically access the reduction in complexity, we depict the parameter and low rank dimensions N and I. respectively in table 2 As demonstrated, our LRA

---

Under review as a conference paper at ICLR 2020
based sampling computations reduce the computational complexity significantly. Furthermore, this explains the necessity of LRA- - certain layers (e.g. FC-1 of both MNIST and CIFAR experiments) computationally intractable to store, infer and sample. As result, we demonstrate an alternative representation for DNNS without resorting to fully factorized and matrix normal distribution.
Discussion and Limitations: Importantly, we demonstrate that when projected to different success criteria, no inference methods largely win uniformly. Yet these experiments also show empirical evidence that our method works in principle and compares well to the state-of-the-art. Representing layer-wise MND in a sparse information form, and demonstrating a low rank inverse/sampling com- putations, we show an alternative approach of designing scalable and practical inference framework. Finally, these results also indicate that keeping the diagonals of IM accurate while sparsifying the off-diagonals can lead to outstanding performance terms of predictive uncertainty and generalizes well to various data, models and even measures. For future works, we share the view that comparing different approximations to the true posterior is quite challenging for DNNs. Consequently, better metrics and benchmarks that show the benefits of model uncertainty can be important direction.
On the other hand, we also address key limitation our work which stems from two hypothesis: (a) when represented in information form, the spectrum of IM should be sparse, and (b) keeping the diagonals exact while sparsifying the off-diagonals should result in a better estimates of model uncertainty (equivalently keeping the information content of node exact while sparsifying the weak links between the nodes from a graphical interpretation of information matrix). While empirical evidence from prior works (Sagun et al., 2018 Thrun et al. 2004 Bailey & Durrant-Whyre 2006) along with our experiments validate these to some extent, there exists no theoretic guarantces to our knowledge. Consequently, theoretical studies that connect information geometry (Amari 2016) of DNNs and Bayesian Neural Networks can be an exciting venue of future research. Nevertheless, similar to sparse Gaussian Processes (Snelson & Ghahramani] (006), we believe our work can be stepping stone for sparse Bayesian Neural Networks that goes beyond approximate inference alone.
5 CONCLUSION
We address an effective approach of representing model uncertainty in deep neural networks using Multivariate Normal Distribution, which has been thought computationally intractable so far. This is achieved by designing its novel sparse information form. With one of the most expressive representation of model uncertainty in current Bayesian deep learning literature, uncertainty can be estimated more accurately than existing methods. For future works, we plan to demonstrate a real world application of this approach, pushing beyond the validity of concepts.
show that
REFERENCES
Martin Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, Manjunath Kudlur, Josh Levenberg. Rajat Monga, Sherry Moore, Derek G. Murray, Benoit Steiner, Paul Tucker, Vijay Vasudevan, Pete Warden, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. Tensorflow: A system for large-scale machine learning. In 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16). pp. 265-283, 2016.
Shun-ichi Amari Information Geometry and Its Applications. Springer Incorporated, 1st edition, 2016. ISBN 4431559779, 9784431559771.
Springr Publishing Company,
Sivaram Ambikasaran and Michael O' Neil. Fast symmetric factorization of hierarchical matrices with applications. CoRR, abs/140S 0223,,222.22222 2014.
Jimmy Ba, Roger B. Grosse, and James Martens. Distributed second-order optimization using cronecker-factored approximations. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
Juhan Bae, Guodong Zhang, and Roger Grosse. Eigenvalue corrected noisy natural gradient. CoRR, abs/181 122565, 2018
Tim Bailey and Hugh Durrant- Durrant-Whyte. Whyte. Simultancous localization and mapping (slam): Part ii. JEEE robotics & automation magazine, 13(3):108-117, 2006.
10

---

Under review as a conference paper at ICLR 2020
S. Becker and Yann Lecun. Improving the convergence of back-propagation learning with second- order methods. In D. Touretzky, G. Hinton, and T. Sejnowski (eds.), Proceedings of the 1988 Connectionist Models Summer School, San Mateo, pp. 29-37. Morgan Kaufmann, 1989.
Christopher M. Bishop. Pattern Recognition and Machine Learning (Information Science and Statistics). Springer-Verlag, Berlin, Heidelberg, 2006. ISBN 0387310738.
Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra. Weight uncertainty in neural networks. In Proceedings of the 32Nd International Conference on Machine Learning Volume 37, ICML' 15, pp. 1613-1622. JMLR.org, 2015.
Alcksandar Botev, Hippolyt Ritter, and David Barber. Practical Gauss-Newton optimisation for deep learning. Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 557-565, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR.
Yaroslav Bulatov. Notmnist dataset. Google (Books/OCR), Tech. Rep.[Online]] Available: http://yrrolavvb. blogspot. it/011 222011009nttmmiit-daaaaass html, 2, 2011.
Sheng- theng--Wiite Chen, Chun-Nan Chou, and Edward Y. Chang. Bda-pch: Block-diagonal approximation of positive-curvature hessian for training neural networks. CoRR, abs/1802.00. 1001108022.0.2.. 2018.
Guillaume Desjardins, Karen Simonyan, Razvan Pascanu, and koray kavukcuoglu. Natural Neural Networks. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett (eds.), Advances in Neural Information Processing Systems 28, pp. 2071-2079. Curran Associates, Inc., 2015.
Yarin Gal. Uncertainty in Deep Learning. PhD thesis, University of Cambridge, 2016.
Thomas George, César Laurent, Xavier Bouthillier, Nicolas Ballas, and Pascal Vincent. Fast approximate natural gradient descent in a kronecker factored eigenbasis. Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, 3-8 December 2018, Montréal, Canada., pp. 9573-95533 2018.
Gene H Golub and Christian Reinsch. Singular value decomposition and least squares solutions. In Linear Algebra, pp. 134-151. Springer, 1971.
Alex Graves. Practical variational inference for neural networks. In J. Shawe-Taylor, R. S. Zemel, P. L. Bartlett, Pereira, and K. Q. Weinberger (eds.), Advances in Neurul Information Processing Systems 24, pp. 2356..35.. Curran Associates, 2011.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 1321-1330, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR.
A.K. Gupta and D.K. Nagar. Matrix Variate Distributions. Monographs and Surveys in Pure and Applied Mathematics. Taylor & Francis, 1999. ISBN 978 158488869.
Jose Miguel Herandez-Lobato and Ryan P. Adams. Probabilistic backpropagation for scalable learning of bayesian neural networks. In Proceedings of the 32Nd International Conference on International Conference on Machine Learning Volume 37, ICML' 15, pp. 1861-1869, JMLR.org
2015.
Nicholas J. Higham. Computing nearest symmetric positive semidefinite matrix. Linear Algebra and its Applications, 103:103-118. 1988. ISSN 0024-3795. doi: 10. 00.10066002243755888)))0000
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, COLT 193, pp. 5-13, New York, NY, USA, 1993. ACM. ISBN 0-89791-611-5.
Mohammad Emtiyaz Khan, Didrik Nielsen, Voot Tangkaratt, Wu Lin, Yarin Gal, and Akash Srivastava. Fast and scalable bayesian deep learning by weight-perturbation in adam. In Proceedings of the 35th International Conference on Machine Learning. ICML 2018, Stockholmsmüssann Stockholm, Sweden, July 10-15, 2018, pp.
2018
11

---

Under review as a conference paper at ICLR 2020
Durk P Kingma, Tim Salimans, and Max Welling. Variational Dropout and the Local Reparame- terization Trick. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett (eds.), Advances in Neural Information Processing Systems 28, pp. 2015.
Curran Associates, Inc.,
James Kirkpatrick, Razvan Pascanu, Neil C. Rabinowitz, Joel Veness, Guillaume Desjardins, An- drei A. Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska-Barwinss. Demis Hassabis, Claudia Clopath, Dharshan Kumaran, and Raia Hadsell. Overcoming catastrophic forgetting in neural networks. Proceedings of the National Academy of Sciences of the United States of America, 114 13:3521-3526, 2017.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, Canadian Institute for Advanced Research, 2009.
Alex Krizhevsky, Πly Sutskever, and Geoffrey E. Hinton. Imagenet classification with deep con- volutional neural networks. In Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems 2012. Proceedings of meeting held December 3-6, 2012, Lake Tahoe, Nevada, United States., pp. 1106-1114, 2012.
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pp. 6402-6413, 2017.
Yann Lecun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. In Proceedings of the IEEE, pp.
1998.
Christos Louizos and Max Welling. Structured and efficient variational deep learning with matrix gaussian posteriors. In Maria Florina Balcan and Kilian Q Weinberger (eds.). Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 1708-1716, New York, New York, USA, 20-22 Jun 2016. PMLR.
Christos Louizos and Max Welling. Multiplicative normalizing flows for variational Bayesian neural networks. In Doina Precup and Yee Whye Teh (eds.). Proceedings of the 34th International Conference Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 2218-2227 International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR.
David C. MacKay. A practical bayesian framework for backpropagation networks. Neural Computation, 4(3):448 472, 1992.
James Martens and Roger B. Grosse. Optimizing neural networks with kronecker-factored approxi- mate curvature. In Proceedings of the 32nd International Conference on Machine Learning. ICML 2015, Lille, France, 6-11 July 2015, pp. 2408 2417, 2015.
Aaron Mishkin, Frederik Kunstner, Didrik Nielsen, Mark W. Schmidt, and Mohammad Emtiyaz Khan. SLANG: fast structured covariance approximations for bayesian deep learning with natural gradient. In Advances in Neural Information Processing Systems 31: Anmual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montreal, Canada pp. 6248 6258, 2018
Jishnu Mukhoti, Pontus Stenetorp, and Yarin Gal. On the importance of strong baselines in bayesian deep learning. CoRR, abs//811.09933 2018
Radford M. Neal. Bayesian Learning for Neural Networks. Springer-Verlag Berlin, Heidelberg, 1996. ISBN 0387947248.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y. Ng. Reading digits in natural images with unsupervised feature learning. In NIPS Workshop on Deep Learning and Unsupervised Feature Learning 201 2011.
Behnam Neyshabur, Yuhuai Wu, Ruslan Salakhutdinov, and Nati Srebro.
opti- mization of recurrent neural networks with relu activations. In Advances in Neural Information Processing Systems 29: Anmual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pp. 3477-3485, 2016.
12

---

Under review as a conference paper at ICLR 2020
Du Phan, Neeraj Pradhan, and Martin Jankowiak. Composable effects for flexible and accelerated probabilistic programming in numpyro. In NeurIPS Workshop on Program Transformations 2019 (to appear), 2019.
Hippolyt Ritter, Aleksandar Botev, and David Barber. scalable laplace approximation for neural networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC. Canada, April 30 May 3, 2018, Conference Track Proceedings, 2018a.
Hippolyt Ritter, Aleksandar Botev, and David Barber, Online structured laplace approximations for overcoming catastrophic forgetting. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, 3-8 December 2018b.
2018, Montréal, Canada., pp.
Levent Sagun, Utku Evci, V. Ugur Güney, Yann Dauphin, and Léon Bottou. Empirical analysis of the hessian of werr-paaametrized neural networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Workshop Track Proceedings, 2018
Tim Salimans and Durk P Kingma. Weight Normalization: A Simple Reparameterization to Acceler- ate Training of Deep Neural Networks. In D. Lee, M. Sugiyama, V. Luxburg, Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems 29, pp. 901-909, Curran Associates, Inc., 2016.
Edward Snelson and Zoubin Ghahramani. Sparse gaussian processes using pseudo-inputs. In Weiss, B. Schölkopf, and J. C. Platt (eds.), Advances in Neural Information Processing Systems 18, pp. 1257-1264. MIT Press, 2006.
Shengyang Sun, Changyou Chen, and Lawrence Carin. Learning Structured Weight Uncertainty in Bayesian Neural Networks. In Aarti Singh and Jerry Zhu (eds.), Proceedings of the 20th International Conference Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pp. 1283-1292, Fort Lauderdale, FL, USA, 20-22 Apr 2017. PMLR.
Sebastian Thrun, Yufeng Liu, Daphne Koller, Andrew Ng. Zoubin Ghahramani, and Hugh Durrant- Whyte. Simultaneous localization and mapping with sparse extended information filters. The international journal of robotics research, 23(7 (3(7-8):693-777 076699967667799 2004.
Laurens Van Der Maaten, Eric Postma, and Jaap Van den Herik. Dimensionality reduction: comparative. Journal of Machine Learning Research, 10(66-71):13, 2009.
Svante Wold, Kim Eshensen, and Paul Geladi, Principal component analysis. Chemometrics and intelligent laboratory systems, 2(1-3):37-52, 1987.
Friedemann Zenke, Ben Poole, and Surya Ganguli. Continual learning through synaptic intelligence. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 3987-3995, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR.
Guodong Zhang, Shengyang Sun, David K. Duvenaud, and Roger B. Grosse. Noisy natural gradient as variational inference. In Proceedings of the 35th International Conference on Machine Learning. ICMI. 2018, Stockholmsmäissan, Stockholm, Sweden, July 10-15, 15,15, 2018, pp. 5847-5856, 2018.
13

---

Under review as a conference paper at ICLR 2020
A NOTATIONS ON DISTRIBUTIONS
A.1 MATRIX NORMAL DISTRIBUTION
The matrix normal distribution a probability density function for the random variable X e R in matrix form. It can be parameterized with mean WMAP E R scales U^ E R and Ug E Rmxn It essentially multivariate Gaussian distribution with mean vec(WMAP) and covariance U @
exp cxp(-jorlug U ( U ( WMAP)) (2x) [
P(X[WMAP. UA Un)
(11)
In section
B we denote this distribution with MN parameterized by WMAP, U^ and UG so that MAPP U. Ua)= MWP UΛ. Ug). Here, tr stands for trace operation and we omitted layer indicing for better clarity. Refer to Gupta & Nagar (199)) for more details.
A.2 INFORMATION FORM or MULIIVARIATE NORMAL DISTRIBUTION
Information form of Multivariate Normal Distribution (MND) is a dual representation for the well known canonical form. Lets denote I vec(X) E R. μ = vec(W R"" and Σ = I-1 -1 T munnon as random variable, mean and covariance respectively for N mn.
p(ll,,)) E) & exp { (-2 P (
(12)
Then, equation 12 defines the canonical form. Now we denote its Information form in equation 13
1 - W
p(äl,, F) exp 2
MAP-
(13)
Here, E nd represent the random variable as well. W information vector (denoted in the main text with superscript) and matrix respectively. We denote the information form N-1 which is completely described by an information vector and matrix. Information matrix is also widely known as precision matrix. [Thrun et al. (2004) in Simultancous Localization and Mapping (SLAM) literature provides a good overview and explanations.
MAP = =E ' R and I -=E- E R.onomi are
B DERIVATIONS
B.1 DERIVATION 1: DIAGONAL CORRECTION WITHOUU EVALUATING THE KRONECKER PRODUCTS
Directly evaluating UA @ UG may not be computationally feasible for modern DNNs. Therefore, derive the analytical form of the diagonal elements for (UA @ Uc)A(U, @ Ua) without having to fully evaluate it. Let UA E Rox* and UG " be the square matrices. A Ru is diagonal matrix by construction.
= UA @ UG E mmmxmn is Kronecker product with elements V., with i == m(ar 1) y and j= m(B 1) + (from definition of Kronecker product). Then, the diagonal entries of (U, @ Uc)A(U, @ U can be computed as follows:
[UU @ UG)A(UA @ U
Σ
VL.
A
(14)
Derivation: As first step of the derivation, express (A @ B)A(A @ B)J in the following form:
(UA @ Ua) & Uo) = (U, @ UaA @ Ua)
= [[CU, @ U U
(15)
= UUT
14

---

Under review as a conference paper at ICLR 2020
Then, diag(UU"); = [ شبر mi by definition. Now, we let (U, Uc) VA with A being again diagonal matrix. Therefore, Mij Vi. / due to the multiplication with diagonal matrix from right hand side. Substituting back these results in (U* 8 Uc)A(U, @ Un)"
2 (vi,, vA,)² which completes the derivation. Formulating equation for the non-square matrices (which results after low rank approximation) such as UA R and UGig IRxx and paralleling this operation are rather trivial and hence, they are omitted.
B.2 DERIVATION 2: ANALYTICAL DERIVATION OF A SAMPLER
For a full Bayesian analysis which is approximated by Monte Carlo integration, sampling is crucial operation (see equation 7 for computing predictive uncertainty. We start by stating the problem.
Problem statement: Consider drawing samples vec(W") R"m from sparse information form:
vec(W") - MAP. (UA.. 8
@ UGrg)* ) D)
(16)
Typically, drawing such samples vec W from canonical form MND requires finding a symmet- rical factor of the covariance matrix (e.g. Chloesky decomposition) which is cubic in cost O(N)). Even worse, when represented in an information form as in equation T6 it requires first an inversion of information matrix and then the computation of symmetrical factor which overall constitutes two operations cost O(N²). Clearly, if N lies in a high dimension such as million, even storing is obvious feasible, let alone the sampling computations. Therefore, tion that (a) keeps the Kronecker structure while sampling so that first, the storage is memory-wiss feasible, and then (b) the operations that require cubic cost such as inversion, must be performed in the dimensions of low rank L instead of full parameter dimensions N. We provide the solution below.
need sampling computa-
Analytica solution: Let us define X Rmm and X' ROXK as the samples from standard Multivariate Normal Distribution in equation 17 where we denote the followings: Omm E !!"",
Lmn B mixomu
Onxm R IRo0 and Im R mxx
Note that these sampling operations are cheap.
x N(0 Imm) or X MN(00mon Ins Im).
(17)
Furthermore, we denote w' = vec(W") E R!" OMAP = vec(WMAP) E RR" as sample from equation
16 and its mean as vector respectively. We also note that Zμ R.xt and D Rimaxom are the low ranked form of the re-scaled eigen-values and the diagonal correction term previously defined. U maxa and UG., Rx* are the eigenvectors of low ranked eigen-basis so that m 2 a, n 2 g can be computed analytically as
and 1= ag. Then, the samples 1f
W = OMAP + FEX where,
F D- ( 1nm Cim-DD's (UAA, UG., UU.,MMin,CC M +VVV U
(18)
Firstly, the symmetrical factor Fe E mux in equation 18 is a function of matrices that are feasible store as they involve diagonal matrices or small matrices Kronecker structure. Furthermore,
V, D @ UG UG
(19)
C C= A.T (B, I1)A,1 with A, and B,
being the Cholesky decomposed matrices of V V, E RLxL and VTV + It R such that:
A.A. VTV, V, and B.B. = v. V, +
(20)
We show how the Kronecker structure of F he exploited compute F* in the derivation only.
15

---

Under review as a conference paper at ICLR 2020
Consequently, the matrices in equation 18 defined C E R!x,, (c-1+++V I e R In this way, the two operations namely Cholesky decomposition and inversion that are cubic in cost O(N9) are reduced to the low rank dimension L with complexity O(L").
+ VTV) R and
Firstly, note that sampling from standard multivariate Gaussian for X or X' is computationally cheap (see equation 17p. Given a symmetrical factor for the covariance = F*Fe" (e.g. by Cholesky decomposition), samples can be drawn via 6MAP F* depicted in equation 18 Our derivation involves finding such symmetrical factor for the given form of covariance matrix while exploring the Kronecker structure for the sampling computations to bound the complexity as O(L").
Derivation:
Let us first reformulate the covariance (inverse of information matrix) as follows.
Σ (UAL MIn(UA, @ UGr + D)"
pd D (UA, @ Un n A (U U D Imom D D
(21)
D (U U M 10 1D tU @ UGrg) An Ium )
D
= = VVT Inm |' D..
Here, we define: V, = (UA., @ UG Now, a symmetrical factor for Σ FcF can be found by exploiting the above structure. We let w be a symmetrical factor for VV + 4m so that F' D W is the symmetrical factor of Σ. Following the work of Ambikasaran O'Neil 2014) the symmetrical factor We can be found using equations below.
W Iam + V,CV? C A= - 1B)AA
(22)
Note that and B are Cholesky decomposed matrices of VTv R and VTV 1 RIxL respectively, As first result, this operation is bounded by complexity O(L") instead of the full parameter dimension N. Now the symmetrical factor for Σ can be expressed as follows.
W- F D !- = 2 + V,CV?)-1
(23)
D Inm v.(C + Vt V.
Woodbury's ' Identity used here, Now, it follows simply by substitution:
W/ = -MMAP + x' where,
Fe D- -1 V,CC-L + VVV
(24)
D (Im
UG Mi V @ Uo D
This completes the derivation of equation 18 As result, the inversion operation is bounded by complexity O(L'). Furthermore, the derivation constitutes smaller matrices UAi. and UG., diagonal matrices D and Im which can be stored as vectors. In short the complexity has significantly reduced.
Now we further derive computations that exploits rules Kronecker products. Consider:
x 1-m=-D((1m---- @ UG MA D (C- + V. - A @ V
(25)
Then, follows by defining inverted matrix If (C-1 + V/ V.V RLxL with cost O(12)):
16

---

Under review as a conference paper at ICLR 2020
F'X'= = -mm @ Uo, Lo (u @ Uo, D J
(26)
We further reduce this by evaluating D= and defining x, - R and pe AlglsA RexL, We that this multiplication operation is memory-wise feasible.
F-X' = xx==x xD-((''(UA,, @ (UAA. @ )
(27)
Now, we map X to matrix normal distribution by an unvec(-) operation so that X = unvec(X;)
E IR or equivalently x )) Using a widely known relation for Kronecker product that is AU & U, vec(X") = vec(U AA,)), it follows:
),
Fx = X - (D~ @ Ua, ) x XUUA))))
(28)
Note that matrix multiplication performed with small matrices. Repeating a similar procedure as above obtain the equation below for X3- pe vec((UA,) @ VV..) xp).
F'X' = Xx (D vec[(UAL, @ UG xxp]
(29)
= X
This completes the derivation. Lastly, we provide remark below to summarize the main points.
Remark: We herein presented derivation is to sample from equation 16 low-rank and information formulation of MND. This analytical solution ensures (a) O(N3) >> O(L.) )) for Cholesky decomposi- tion, (b) O(N3) >> O(1.)) for a matrix inversion, (c) storage of small matrices UG., UA a diagonal matrix D and identity matrices and finally (d) matrix multiplications that only involve these matrices.
This is a direct benefit of our proposed LRA that preserves Kronecker structure in eigenvectors.
C THEORETICAL ANALYSIS
Some of the interesting theoretical properties are as follows with proofs provided in section D
C.1 DIAGONAL. CORRECTION LEADS TO MORE ACCURATE ESTIMATION OF INFORMATION MATRIX
A theoretical result of adding diagonal correction term is captured below. This relates to the work presented in section 2.2 where a diagonal correction term is added to EFB estimates of IM.
Lemma 1: Let I NxN be the real Fisher information matrix, and let Laef E NNN and Lep NNN be the DEF and EFB estimates of respectively. It is guaranteed have | I - Taoll
Corollary 1: Let Inue E NNN and Laef NNN be KFAC and our estimates of real Fisher information matrix NxN respectively. Then, it is guaranteed to have ||z Isfuell; >|I Iaells.
Remark: For interested readers, find the proof ||T --rraallss 2 || - F in George et al. 2018).
- vice versa. Yet, our proposed approximation yield better estimates than KFAC the information form of MND.
Note that | Iafellly z || Fe may not mean that | p -
C.2 THEORETICAL PROPERTIES OF LOW-RANK INFORMATION MATRIX
To knowledge, the proposed sparse IM have not been studied before. Therefore, we theoretically motivate its design and validity for better insights. The analysis can be found below.
Firstly, study the effects of preserving Kronecker structure in eigenvectors. We define:
17

---

Under review as a conference paper at ICLR 2020
1:K (U^ UO) UG)
(30)
as a low rank EFB estimates of true Fisher that preserves top K eigenvalues. Similarly, 1 can be defined which preserves top L. eigenvalues. contract, our proposal to preserve Kronecker structure in eigenvectors F.z denoted as shown below. Now, we provide our analysis with Lemma
f... = (U & UG, (U & U.....
(31)
Lemma 2: Let I E NNN be the real Fisher information matrix, and let L E RRAN, pop and f E NNN be the low rank estimates of I of EFB obtained by preserving top K, L. and top K plus additional J resulting in L eigenvalues. Here, we define K < L. Then, the approximation error of Ii is bounded as follows: | I 2 > -- 2 prop 1
I:1. E RNXN
This bound provides insight that if preserving top I. eigenvaluus result in prohibitively too large covariance matrix, our LRA provides an alternative to preserving top K eigenvalues given that K < L. In practise, note that fiz is a memory-wise feasible option as we formulate Lu AUA @ UGr,)Ani((A,... @ U which preserves the Kronecker structure in eigenvectors. This can be a case where evaluating (UA,, @ UG..) or (UA,, @ UG ):x not feasible to store.
Remark:
Lemma 3: The low rank matrix E = (UUA, @ UG, (i:L(AA @ UGr.g
I + +D) NNN is a non- degenerate covariance matrix if the diagonal correction matrix D and LRA (UAI. @ Uan, MiL(UAI. @ U S are both symmetric and positive definite. This condition is satisfied (U',,, UUG. DA @
UG 0/ < { for all e (1.2. d) and with ALL $ O.
Remark: This Lemma comments on validity of resulting parameter posterior and proves that sparsifying the matrix can lead to valid non-degenerate covariance if two conditions are met. As non-degenerate covariance can have uniquely defined inverse, it important to check these two conditions. We note that searching the rank can be automated with off-line computations that does not involve any data. Thus, it does not introduce significant overhead. In case does not turn out to be, there are still several techniques that can deal with it. We recommend eigen-value clipping (Chen) ctt al. 2018) or finding nearest positive semi-definite matrices (Higham 1988), Lastly, D does not get numerically unstable when we add prior precision term and scaling factor (ND +
Lemma 4:
Let I RNN be the real Fisher information matrix, and let Ldef e BNNN Lop E RNNN and Isfoe RNN be the low rank DEF, EFB and KFAC estimates of it respec- tively. Then, it is guaranteed to have || diag(T)- diag( Top 2 || diag(I)- diag(TacD)l diag(I)- - diag(Igue)lls 2 diag(())- diag(fag)ll = O. Furthermore, if the eigenvalues of
O
and| || Lad contains all non-zero eigenvalues of Leef. it follows: || Lolls 2 - -adlle
Lemma 4 shows the optimally in capturing the diagonal variance while indicating that our approach also becomes effective in estimating off-diagonal entries IM contains many close to zero eigenvalues. Validity of this assumption has been studied by Sagun et al. (2018) where it is shown that the Hessian of overparameterized DNNs tend to have many close-to- closeto--zero zero cigenvalues. Intuitively, from graphical interpretation of IM, diagonal entries indicate information present in each nodes and off-diagonal entries are links of these nodes (depicted in figure []. Our sparsification scheme reduces the strength of the weak links (their numerical values) while keeping the diagonal variance exact. This is a result of the diagonal correction after LRA which exploits spectrum sparsity of IM.
Remark:
D PROOFS
D.1 DIAGONAL CORRECTION LEADS TO ACCURATE ESTIMATION INFORMATION MATRIX
Proposition 1: Let I E N be the real Fisher information matrix, and let Laef E NxN and Ldet E RAXON be our estimates of it with rank d and k such that k < d. Their diagonal entries equal that is Ig Idef Las, for all i = 1, 2, .... N.
18

---

Under review as a conference paper at ICLR 2020
proof:
The proof trivially follows from the definitions of I E R Iaet E R and Leet R As the exact Fisher is an expectation on outer products back- paok-propegtted gradients, its diagonal entries equal I = B [66] for all i 1.2....,
In the case of full ranked Loes substituting = D 60 2x=1 (Va VAd with 2 (v= (Von VAR>² (U, @ UG)A(U, Ue), results in equation 32 for all i == 1, ...,, N.
Idef. (U, & UG)A(U, @ UO) + D
(32)
(U, UG)A(U, Uc) = [088 Similarly, substitute D., E 66 Σ (fo. v with Σxel (Ra vAI.))²
AUA @ U UOY E 66.
(UADN Apx X
Un which results in equation 33 for all = 1, 2, .....N N.
def. = (UAIN & MiLWAAA & UGiu I Dú
-UAIN @ UG (1 @ Unuw) 688 (UAIN @ Vna An UG (33) = =B(80?]
Therefore, we have I = Laef, faet for all 1,2,.....N
Lemma 1: Let I E NNN be the real Fisher information matrix, and let Laef E BNN and Lab E R NNN be the DEF and EFB estimates of respectively. It is guaranteed huve Looll ||r Iadls
proof: Let e2 ||A- BII define a squared Frobenius norm of error between the two matrices RNN and NXN, Now, e² can be formulated as,
of = 1AA - BlI;
= EA (A - BY + ΣΣ (A jAi
B)
(34)
The first term of equation belongs to errors of diagonal entries in B wrt whilst the second term due to the dif-dial entries. Now, it follows that,
|| Lublle II Tueille
ey 2 Ede/
Σ1 Lab) + Ei E j= 1 L Σ,[I Lact); + Li E1n((I Loct)
Σ - Ian)) Σi E jes( Iant)
Σi Ees (I Ieee)
Σ Ion) Σi E E1= Lant) Σi Ej+(1I Lani)
Note that Σ, = using proposition 1. Furthermore, Σ, E1+ - Lderti since by definition, Lebb and Jset have the same off-diagonal terms.
EIe -Labt)
Corollary 1: Let Iafac NNN and Laef NxN be KFAC and estimates of real Fisher Information matrix I NxN respectively. Then, it guaranteed to have | Ixfaelle- 2 Idolle
Find the proof | | -efalll | 2 I|I Iebbll in George et al. 2018).
D.2 THEORETICAL PROPERTIES OF LOW-RANK INFORMATION MATRIX
Lemma 2: Let NKN be the real Fisher information matrix, and let fop
NNN, jup NNN
and I E NxN be the low rank estimates of I of EFB obtained by preserving top K, L and top plus additional J resulting eigenvalues. Here, we define K Then, the approximation error of
Fr is bounded follows: || Pupll || Fizllpe
grop] I
19

---

Under review as a conference paper at ICLR 2020
proof: From the definition, (UA UG)A(U, @ UG) VAV* is PSD as Au B 60) O for all elements i and VV I with as an identity matrix (orthogonality). Naturally, low rank approximations (U^ @ Uoh.vAA. (U ) UG,,)* (U, @ (e))AAAu(U @ Uo)iz are again PSD by the fact that low rank approximation does not introduce negative eigenvalues.
@ Uc) (U^ @ U A (U^ @ U&) and
Now, well known fact from dimensional reduction literature is that low rank approximation preserving the top eigenvalues result in best approximation emors in terms of Frobenius norm for the given rank. Informally stating Wely's ideas on eigenvalue perturbation:
Let B E R with rank smaller or equal to (one can also use complex space C instead of R) and let A B with A R=xx" Then, follows that,
[| = -AA oo -A +........o. + B)² = - (35)
where o'..... .y are the singular values of with μ min(n, m). The convention here is that (A) is the ith largest singular value and (A,(A) = 0 for > rank(A). Using this insight, and the fact that in the given settings, squared singular values are variances new space lead to:
- Po-ll 2 || Irellr 2 I| P.
Lemma 3: The low rank matrix Σ = ((UA... @ UGi (ALL(UA @ UGr.)
) + +D] degenerate covariance matrix if the diagonal correction matrix D and LRA (U @ UG Aiz(UA 8 UG.,)² Y are both symmetric and positive definite. This condition is satisfied AU', @Ua, (UA(UAL 8
E NNN is a non-
Uo..) " E [of) for all 11.2.....N) and with A1. & O.
proof: Let us first rewrite iast AU @ UG.,)AA (U @ V + D in the following form.
(UAi, @ UG (U, @ UG,,)" + = (UAIo @ UG A (UA.. @ UGn +D
=(UUAL Uo Au (UA... @ Uo Ai 1' + (36)
= -UTT +D
Now, if D and (UA,, @ Van.)NaaAAA @ )² is both symmetric and positive definite, it follows that for an arbitrary vector x E Rd, -UUTT > 0 as eigen-values R; > 0 by construction. Furthermore, IT Dx also holds by the definition of positive definiteness. Therefore, we have x (UUT D)x xT JUUT* x x" Dx > O which leads to the proof that l is positive definite if D and (UA, @ UG, (Uz,UA,, @ Ua,)) ) is both symmetric and positive definite. As this results non-degenerate IM, the canonical covariance Σ is non-degenerate as well.
Trivially following the definition of D E 808 - (UA Ug)A(U, U.), D3 0 for all i when
(U @ UG., Au, 8 UGig y < E [80 Again, by the definition of A; = B [V 80) Ar containing no zero eigenvalues result in the positive definite matrix (UA,, @ @UG,))A1:1(U, Aro @ D.
Lemma 4:
Let I NNN be the real Fisher information matrix. and let Lde E BNN, Lop E NNN and Isuue NNN be the low rank DEF, EFB and KFAC estimates of it respec- tively. Then, it is guaranteed have [[dia((]) diag(T.f))ll >I]diag(T) - diag(f
and O. Furthermore, if the eigenvalues of L
|| diag(I)- - diag(I diag(Iya))l 2 diag([) - diag( contains all non-zero eigenvalues of Iag it follows: ||r- Lollle 2 || i
proof: The first part follows from proposition I which states that for all the elements i, In fast || diag(I)) diag(L.s>)l 2 diag(I) diag(fa=))|ı
o and || diag(I) diag(I 2 || diag(I) - diag(Sar))| = O. This results by the design of the method, in which, we correct the diagonal entries in parameter space after the LRA.
20

---

Under review as a conference paper at ICLR 2020
For the second part of the proof, lets recap that Lemma 2 (Wely's idea eigenvalue perturbation) that removing zero eigenvalues does not affect the approximation error in terms of Frobenius norm. This then implies that off-diagonal elements of faer and Leb are equivalent. Then,:
|| Llll 2 || feellF
e 2 22 &def
Σ - Iunt + L j; jos
Iebb) 2 Σ, a + Σi E jes((I ldet
Σ I Ei jzs jzs [ Ieb 1, 2 Ei E=: {
Σ Ian) Σi Σ jus(1 (I- Tab 2 Σi [T - Ianh)
Again, - -
= according to proposition 1 for all the elements i.
E IMPLEMENTATION DETAILS AND FURTHER RESULTS
KFAC library from Tensorflow was used to implement the Fisher estimator (Martens & Grosse 2015) for our methods and the works of Ritter et al. (2018a). Note that empirical Fisher usually is not good estimates as it is typically biased (Martens & Grosse 2015) and therefore, did not use it. KFAC library offers several estimation modes for both fully connected and convolutional layers. We have used the gradients mode for KFAC Fisher estimation (which is also crucial for our pipelines) whereas the exact mode was used for diagonal approximations. We did not use the exponential averaging for all our experiments as well as the inversion scheme in the library. However, when using it in practice, it might be useful especially if there are too many layers that one cannot access convergence of the Fisher estimation. We have used NVIDIA Tesla for grid searching the parameters of Diag and KFAC Laplace, and 1080Ti for all other experiments.
E.1 Toy REGRESSION DATASET
Apart from the architecture choices discussed in section 4 the training details are follows. A gradient descent optimizer from tensorflow has been used with a learning rate of 0.001 with zero prior precision or L2 regularization coefficient (T 0.2 for KFAC, both FB and DEF have been used). Mcan squared error (MSE) has been used as its loss function. Interestingly, the exact block-wise Hessian and their approximations for the given experimental setup contained zero values on its diagonals. This can be interpreted as zero variance in information matrix, meaning no information, resulting in information matrix being degenerate for the likelihood term. In such cases, the covariance may not be uniquely defined (Thrun et al. 2004). Therefore, we treated these variances deterministic, making the information matrix non-degenerate (motivated from Lemma 3). Similar findings are interestingly reported by MacKay (1992).
0.45 for Diag, N 1 and T 0 for
More importantly, we present a detailed analysis to avoid misunderstanding about our toy dataset experiments. As starting remark, main advantage of this toy regression problem is that it simplifies the understandings of on-going process, in lieu of sophisticated networks with a large number of parameters. Typically, as of Herandez-Looaa & Adams| (015)). Ritter al. (0188), Gal (2016), or even originating back to Gaussian processes literature, this example has been used to check the predictive uncertainty by qualitatively evaluating on whether the method predicts high uncertainty in the regimes of no training data. However, drawback exists: no quantitative analysis has been reported to our knowledge other than qualitatively comparing to community wide accepted ground truth such as Hamiltonian Monte Carlo Sampling (Neal 1996), and LA using KFAC and Diag seem to be sensitive to hyperparameters in this dataset which makes the comparison difficult.
This is illustrated in figure 7 where we additional introduce Random which is just user-set r/ for covariance estimation in order to demonstrate this. Qualitatively analyzing from the first look, all the methods look very similar in delivering high uncertainty estimates in the regimes of no training data. Here, we note that the same hyperparameter settings have been used for Diag, KFAC and FB Laplace whereas the user-set 7 7 has been found for Random. This agrees to the discussions of Ritter et al.) (2018)) as KFAC resulted in less T when compared to Diag Laplace.
https://gi http:///gghhuu.ccm///eeerrr/ro//
21

---

Under review as a conference paper at ICLR 2020
150
155
150
100
105
-50
-50
-55
-50
-10
-150
-10
-35
-20
-20
(a) KFAC Laplace
(b) Diag Laplace
(c) Random
(d) FB Laplace
Figure 7: Toy regression uncertainty. User-set Laplace means user-set r/ for covariance estimation. This shows that if one tries to tune the "regularizing parameters, all these approximations to the true Hessian behaves similarly within this experiment. Now trained with 20 data points.
130
150
120
120
-100
-130
-150
-150
(a) OKF Laplace
(b) OKF Laplace (tuned)
(c) OKF inverse
(d) KFAC inverse
Figure 8: Toy regression uncertainty and covariance visualization (only the first layer is shown here). OKF Laplace means using the left hand side of equation without further approximation (only possible with this small model and data-set).
However, we also observed that without the approximation step of equation (denoted OKF), using the same hyper parameter as above resulted in visible over-prediction of uncertainty and inaccurate estimates on the prediction. This is shown in figure [ Again, tuning the parameter to higher precision similar behavior to figure can be reproduced. This can be analyzed by visualizing the covariance of KFAC and OKF, As can seen, in this experiment settings, figure shows that equation damps the magnitude of estimated covariance matrix.
possible explanation is that if the approximate Hessian is degenerate, then small T/ places a big mass areas of low posterior probabilities for some network parameters with information (zero variance and correlations in the approximate Hessian). This can be seen in figure g part (a) where the approximate Hessian contains parameters with exactly zero diagonal elements and zeros in its off- off-diagonal elements. If one tries to add small r = 0.001 here, then the covariance of these parameters get close its inverse -- 1000 as shown in figure & part (c). This would in return result in over prediction of uncertainty and inaccurate predictions which explains figure 8 part (a).
Another interesting experiments are studying the effects of dataset size number of parameters. For this, we have increased the dataset size to 100 in oppose to 20. Again, we now compare the approximate Hessian by visualizing them. Notably, using 100 data points resulted in more number of zero diagonal entries and corresponding rows and columns. This is due to over parameterization of the model which results in under determined Hessian.
These insights hint for the followings. Accurately estimating the Hessian while forcing its estimates non-degeneracy via not considering zero eigenvalues for this data and model can lead less sensitivity to its hyperparameters points to number of parameters change the approximate Hessian (similarly found for estimates of Fisher) changes its structure, and can lead to under-determined approximation (therefore, changing hyperparameters affects the
in particular. Secondly, further increasing decreasing the ratio of data
its loss landscape). Finally, if the Hessian is resulting predictive uncertainty (or covariance) if its magnitude significantly differs (and in case of
22

---

Under review as a conference paper at ICLR 2020
KFAC). However, more detailed experimental analysis is outside the scope of the paper, be an interesting future work to further analyze the relation between the hyperparameters, their probabilistic interpretation and resulting loss landscape of neural network.
E.2 BENCHMARK IMPLEMENTATIONS
We have used Numpyro (Phan et al. 2019) for the implementations of HMC. We have used 50000 MC samples generate the results in order ensure the convergence. For the implementation of Bayes By Backprop we have used an open-source implementation byyes-by-ber by-bbckprooppp for which a similar experiment settings are implemented where the Gaussian noise is sampled in a batch initially, and symmetric sampling technique is deployed. We note that the number of data samples and network architectures are different. Furthermore, we have used 10000 iterations to ensure convergence of the network.
thub. com/ ThirstySScolar
E.3 CLASSIFICATION TASKS
Most of the implementations for MNIST and CIFAR10 experiments were taken from Tensorflow tutorials including the network architectures and training pipelines if otherwise stated in the main text. This in line of argument that our method can be directly applied to existing, and well trained neural networks. For MNIST experiments, the architecture choices are the followings. Firstly, no down-scaling has been performed to its inputs. The architecture constitutes 2 convolutional layers followed by 2 fully connected layer (each convolutional layer is followed by pooling layer of size? by 2, and a stride 2). For flattening from the second convolutional layer to the first fully connected layer, a pooling operation of 49 by 64 has been naturally used. RELU activation have been used for all the layers except the last layer which computes the softmax output. Dropout has been applied to the fully connected layer with dropout rate of 0.6 after grid search (explained in section E.3.1) I. Regarding the loss functions, cross entropy loss has been used with ADAM as its optimizer and learning rate of 0.001. An important information is the size of each layers. The first layer constitutes 32 filters with 5 by 5 kernel, followed by the second layer with 64 filters and 5 by 5 kernel. The first fully connected layer then constitutes 1024 units and the last one ends with 10 units. We note that, this validates method memory efficiency the third layer has large number of parameters, and its covariance, being quadratic in its size, cannot be stored in our utilized GPUs.
Regarding the architecture selection of CI- FAR10 experiments, down-scaling of the in- puts has be done. The chosen architecture is composed of 2 convolutional layers followed by fully connected layers. Pooling layers of size 3 by 3 with strides have been applied to outputs of the convolutional layers. Obviously, the third convolutional layer is pooled to match the input size of the following fully connected layers. Batch normalization has been applied to each outputs of convolutional layer before pooling, with bias 1, a of 0.001/9.0 and / of 0.75 (notations are different
88:8
(a) the Hessian [100]. (b) the Hessian [20]
Figure 9: Visualization of the approximate Hes- sian with different data points.
the main text, and this follows that of tensorflow library). A weight decay factor of 0.004 has been used, and trained again with cross entropy loss, now with stochastic gradient descent. Learning rate of 0.001 has been used. Again, the most relevant settings are: the first layer constitutes 5 by 5 kernel with 64 filters. This is then again followed by the same (but as input to CIFAR 10 is RGB, the second layer naturally has more number of parameters). Units of 384, 192, and 10 have been used for the fully connected layers in an ascending order. Lastly, random cropping, flipping, brightness changes and contract have been applied as the data augmentation scheme. Similar to MNIST experiments, the necessity of LRA is capture in CIFAR10 10 as well.
23

---

Under review as a conference paper at ICLR 2020
Unlike Ritter et al. 80188) did not artificially augment the data for MNIST experiments because the usual training pipeline did not require it, For our low rank approximation, we always have used the maximum rank could fit, after removing all the zero eigenvalues and checking the conditions from Lemma 3. Lastly we have used 1000 Monte-Carlo samples for MNIST, and 100 samples for CIFAR10 and toy regression experiments.
E.3.1 BENCHMARK IMPLEMENTATIONS
Implementation of deep ensemble [akksminarayaaaaa et al. 2017) was kept rather simple by not using the adversarial training, but we combined 15 networks that were trained with different initialization. used for all. Note that CIFAR 10 experiments with
The same architecture and training procedure similar convolutional architectures were not present in the works of Lakshminarayanann et al.) (017) the best of knowledge. On MNIST, Louizos & Welling (2017) found similar results ours that deep ensemble performed similar to the MC-dropout (Gal 2016). For dropout, we have tried grid search of dropout probabilities of 0.5 and 0.8, and have reported the best results. For the methods based on Laplace approximation, we have performed grid search on hyperparameters N of (1, 50000, 100000) and 100 values of were tried using known class validation set. Note that for every method, and different data-sets, each method required different values of T/ to give reasonable accuracy. The starting point of the grid-search were determined based on the mean values of their predictions were obtained similar accuracy to the deterministic counter parts. The figure below are the examples on MNIST where minimum ece points were selected and reported.
2.244
0.2029
3.00
8.630
5.590
0.4925
0.10
2 3.191
3,0
00920
2.000
0.44
2949
09910
0.
9.02
2.887
103 150
200 damping
250 300
3.00
50
100
153
230 239
0.000
20
40 50
100
0.00
20
90
50
100
dampingi
dampingt
damping
Figure 10: Grid search results. For Diag (left two figures) and KFAC Laplace (right two) an extensive grid search has been conducted to ensure fair comparison. Here, we report the results with pseudo observation term of 50000 on MNIST. This ensures that a main difference to DEF Laplace is the expression for model uncertainty as the inference and network architectures kept the same.
24


Reviews:
[{"review_id": "rJxnUJb6cH", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The submitted paper presents a method of approximating the posterior distribution over the DNN parameters based on a Laplace Approximation scheme. It extends on the previous work by adding a diagonal correction term to the Kronecker-factored eigenbasis and also suggests a low-rank representation of Kronecker-factored eigendecomposition. Empirical evaluations were done to show that the proposed method has a more accurate uncertainty estimation compared to the previous work.\n\nOverall, the paper is well-organized and easy to follow, although mathematical notations are not consistent throughout the paper. It is well-referenced, and the derivations look mostly correct (explained in minor comments). The main idea of the paper is convincing and well-motivated. To my knowledge, the proposed method of adding a correction term has not been introduced before. However, it is more of an incremental contribution to the existing works. In that sense, I am slightly concerned that its novelty is limited.\n\nThe experiments are not comprehensive. For the toy regression problem, a comparison to Hamiltonian Monte Carlo would be more informative. Moreover, it would be helpful to report the comparison with factorized variational methods (e.g. Graves, 2011) and experiment on modern architectures. I would be also interested to see what the additional time complexity by adding a diagonal correction term is and how more efficient it gets by low-rank approximation in experimental details.\n \nMinor comments:\n*Page 4: It would have been easier to understand if there had been a notational distinction between exact eigenbasis and K-FAC eigenbasis in defining V. Also, “In equation equation 10” -> “In equation 10”.\n*Page 7: In Lemma 2, the order in describing the low-rank estimate does not appear to be correct. Also, in Lemma 4, shouldn’t there be a hat on I_{efb} and I_{kfac}?\n*Page 9: The colour scheme in Figure 3 looks visually harder to read.\n*Page 14: In equation 15 and 16, there should be a bracket for (2 \\pi), and in Appendix B, some variables (e.g. p, k, R) are left unexplained.\n*Page 14, 15: In equation 23 and proposition 1, \\mathcal is missing, and vec operator is missing in equation 22.\n*Page 3: In equation 2 and 4, is it A_{i-1} or A_i?\n*Page 16: In equation 27, the dimension of X \\in \\mathcal{R}^{m \\times m} seems incorrect. Also, in the last line, doesn’t X \\odot D have different dimensions (similarly in equation 22)? ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "r1xd1v3u9H", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Laplace approximation has been an important tool for obtaining uncertainty estimation for deterministic models. To efficiently approximate the Hessian matrix for neural networks, Ritter et. al (2018) proposes to use K-FAC . Motivated by the relatively inaccurate approximations of K-FAC, this paper proposes to improve KFAC approximations by combining eigen-basis corrections (EK-FAC, George et al, 2018) and diagonal corrections. The paper shows that the proposed method has smaller Frobenius approximate errors compared to K-FAC and EK-FAC. To further reduce the computational costs, the paper proposes a low-rank approximation by keeping only the L largest eigenvalues. Empirically, the paper demonstrates improved calibration and out-of-distribution entropies compared to previous approaches. \n\n# Diagonal Corrections. \nWith the diagonal correction approximating the Fisher better, the paper shows the computation can still be conducted in the scale of W, which is similar to K-FAC. However, the method requires the diagonal correction matrix D is always positive, which might not be true. Moreover, because the computation requires D^{-1}, clipping D to a small constant will bring up stability issues. I wonder how this problem is tackled in this paper. \n\n# Writing \nThe paper's notations are messy, which requires a lot of intellectual guesses to understand the conveyed idea. \n1) Notations are not introduced, such as $\\delta \\theta$, $W_{map}^{IV}$, the MN distribution in the appendix.\n2) Notations are typoed. Eq(3) $N(0, A^{-1} \\otimes G^{-1}) = MN(0, G^{-1}, A^{-1})$; The bottom paragraph in Page 4; eq(8).\n3) Notations are abused. In particular for $V$ and $\\Lambda$ when introducing EK-FAC. The paper uses $V$ for both true eigenbasis and the EK-FAC eigenbasis. In addition, the EK-FAC part should be moved to the background section.\n4) The paragraph below Corollary 1 says the author can prove the proposed method also has closer approximations in terms of the Fisher inverse. But no proofs are given.\n5) Caption of Figure4.\n\n# Laplace Approximation \nFor eq(4, 8, 12), The Hessian in Laplace approximations should be divided by $N$. Although the paper also mentions the scaling below those equations. But technically eq(4, 8, 12) are wrong and I don't know whether the experiments really did the scaling or not. \n\n# Low-rank Approximation\n1) It is not clear why the low-rank approximation is necessary. The computational costs are inevitable to compute the eigen-system of A and G. Why do we need the low-rank approximation after that ? K-FAC is not a computationally expensive method either. \n2) I cannot understand the proofs of Lemma 2. In fact, I don't know what $ I_{1:L}^{top}, I_{1:K}^{top}$ means. More explicit formulas should be given for clarity. \n3) Lemma 4 states $I_ii = (\\hat{I}_{def})_ii$. Although the diagonal correction makes $I_ii = (I_{def})_ii$, the low-rank approximation makes them unequal again. Or I guess you use a different D in eq(13) from the D in eq(10) ? \n\n# Experiments \nThe paper needs more experiments to validate the proposed method. Firstly, for the MNIST experiments, it is better to use the same architecture as in Ritter et al (2018) for direct comparisons. Beyond that, the adversarial attack experiment and the mis-classification uncertainty experiment in Ritter et al (2018) seem to be good choices as well. \n\n# Overall\nThe paper proposes a diagonal corrected EK-FAC, achieving better approximation of the Fisher matrix. Interestingly, the paper shows that this corrections doesn't add too much computations.  However, the proposed low-rank approximation doesn't seem necessary. And the paper's notations and presentations are too messy to be an accepted paper.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "r1gQ31udtS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The contribution of the paper is marginal, as the principle of imposing Gaussians on the network to perform Bayes is not new. The Laplace-based approximation is half-baked and certainly much better techniques for Bayes exist in the recent literature; furthermore, it's selection is not substantiated enough, and, of course, it represents no novelty. The experimental results are not convincing, as both the considered scenarios are limited and the comparisons are too poor (no consideration of state of the art alternatives). The provided corollaries are not actually helpful and should be put in the appendix. ", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "S1xjOAscqr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThe paper studies the Laplace approximation for Bayesian inference of a neural network. Specifically, it proposes a diagonal correction and a further low-rank approximation to the Kronecker-factored eigenbasis for more accurate approximation of the Fisher information matrix and better scalablility, respectively. The proposed diagonal correction is shown to have a smaller residual error in F-norm. Experiments are given to show that the proposed Laplace approximation makes more accurate uncertainty estimations. \n\nThe paper makes a certain contribution to existing Laplace approximations for the task in terms of accuracy and scalability. However, it is incremental and the novelty is a bit low, compared to many recent closely related works, for example,\n\nOptimizing Neural Networks with Kronecker-factored Approximate Curvature. 2015\nPractical Gauss-Newton Optimisation for Deep Learning. 2017\nFast Approximate Natural Gradient Descent in a Kronecker-factored Eigenbasis. 2018\nA scalable Laplace approximation for neural networks. 2018\nEigenvalue Corrected Noisy Natural Gradient. 2018\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a variant of recently developed Kronecker-factored approximations to BNN posteriors. It corrects the diagonal entries of the approximate Hessian, and in order to make this scalable, approximates the Kronecker factors as low-rank.

The approach seems reasonable, and is a natural thing to try. The novelty is fairly limited, however, and the calculations are mostly routine. In terms of the experiments: it seems like it improved the Frobenius norm of the error, though it's not clear to me that this would be a good measure of practical effectiveness. On the toy regression experiment, it's hard for me to tell the difference from the other variational methods. It looks like it helped a bit in the quantitative comparisons, though the improvement over K-FAC doesn't seem significant enough to justify acceptance purely based on the results.

Reviewers felt like there was a potentially useful idea here and didn't spot any serious red flags, but didn't feel like the novelty or the experimental results were enough to justify acceptance. I tend to agree with this assessment.

Decision: Reject