Debiasing Mini-Batch Quadratics for Applications in Deep Learning

## Abstract

Abstract Quadratic approximations form a fundamental building block of machine learning
methods. E.g., second-order optimizers try to find the Newton step into the minimum of a
local quadratic proxy to the objective function; and the second-order approximation of
a network’s loss function can be used to quantify the uncertainty of its outputs via
the Laplace approximation.
When computations on the entire training set are intractable—typical for deep
learning—the relevant quantities are computed on mini-batches. This, however,
distorts and biases the shape of the associated stochastic quadratic
approximations in an intricate way with detrimental effects on applications.
In this paper, we (i) show that this bias introduces a systematic error, (ii) provide
a theoretical explanation for it, (iii) explain its relevance for second-order
optimization and uncertainty quantification via the Laplace approximation in deep
learning, and (iv) develop and evaluate debiasing strategies.

## 1 Introduction

Quadratic approximations of the loss landscape are increasingly used by algorithms in
deep learning, from pruning methods (Dong et al., ; Zeng & Urtasun, ) and
influence functions (Koh & Liang, ) to second-order optimizers
(Amari, ; Martens, ; Martens & Grosse, ; Grosse & Martens, ; Botev et al., ; Zhang et al., ; George et al., ; Martens et al., ; Osawa et al., )
and uncertainty quantification via the Laplace approximation
(Ritter et al., ; ; Kristiadi et al., ; Daxberger et al., ; Immer et al., ).
When the computations are intractable on the entire training set—typical for deep
learning—the quantities of interest are computed on mini-batches subsampled from the
training data.
The goal of this work is to highlight that mini-batching systematically biases the
shape of a quadratic approximation.

A systematic bias? Figure 1 illustrates the phenomenon. It
shows five mini-batch quadratics in their top-curvature 2D subspace for the
fully trained All-CNN-C model on CIFAR-100 data. For comparison, the full-batch
quadratic, where all quantities are evaluated on the entire training set, is
projected into the same 2D subspace. Within that subspace, the two quadratics
are quite different: The mini-batch quadratic is much “narrower” (exhibits larger
curvature) than the full-batch version. Given that the full-batch quadratic is the
“right” object to serve as the basis for, e.g., a Newton step or a Laplace
approximation,(^1^11We are not concerned with the approximation error arising from the quadratic approximation of the non-quadratic function $\mathcal{L}_{\text{reg}}(\,\cdot\,;\mathcal{D})\approx q(\,\cdot\,;\mathcal{D})$ (see Equation 2), but only with the consequences of replacing the full-batch quantities by their mini-batch counterparts $q(\,\cdot\,;\mathcal{D})\approx q(\,\cdot\,;\mathcal{B})$.) the mini-batch version is
not a meaningful surrogate: Its Newton step is overly small and a Laplace
approximation yields an overconfident uncertainty estimate.

Figure: Figure 1: A systematic bias? We compute five mini-batch quadratics $q(\,\cdot\,;\mathcal{B}_{m})$ with batch size $|\mathcal{B}_{m}|=512$ for the loss landscape of the fully trained All-CNN-C model on CIFAR-100 data around ${\bm{\theta}}_{0}\leftarrow{\bm{\theta}}_{\star}$ (shown as ). Each mini-batch quadratic defines a 2D subspace spanned by the top two eigenvectors ${\bm{u}}_{1},{\bm{u}}_{2}$ of ${\bm{H}}_{\mathcal{B}_{m}}$, in which we evaluate (i) the quadratic $q({\bm{\theta}}_{\star}+\tau_{1}{\bm{u}}_{1}+\tau_{2}{\bm{u}}_{2};\mathcal{B}_ {m})$ itself (shown in ) and (ii) the full-batch quadratic $q({\bm{\theta}}_{\star}+\tau_{1}{\bm{u}}_{1}+\tau_{2}{\bm{u}}_{2};\mathcal{D})$ (shown in ). In that subspace, the mini-batch quadratic is much “narrower” than the full-batch version which leads to overly small Newton steps and overconfident uncertainty estimates via the Laplace approximation.
Refer to caption: x1.png

Contributions.
To enable stable and efficient stochastic second-order optimizers, as well as reliable
techniques for uncertainty quantification, we analyze this phenomenon and
develop strategies to mitigate it.
More specifically, our contributions are as follows: (i) We study mini-batch quadratics
empirically and show that their geometry is systematically biased; (ii) we provide an
explanation for this phenomenon, explaining the bias as an instance of the classic
regression to the mean (directions of extreme steepness/curvature for one particular
mini-batch are less extreme for other mini-batches), (iii) we explain the relevance of
this bias for second-order optimization and uncertainty quantification via the Laplace
approximation, and (iv) develop and evaluate debiasing strategies.

## 2 Notation & background

The regularized loss.
We consider a general supervised learning problem, where we try to find the optimal parameters
${\bm{\theta}}_{\star}=\operatorname*{arg\,min}_{{\bm{\theta}}\in\mathbb{R}^{P}
}\mathcal{L}_{\text{reg}}({\bm{\theta}},\mathcal{D})$ for the parameterized function $f_{{\bm{\theta}}}:\mathbb{R}^{D}\rightarrow\mathbb{R}^{C}$ by minimizing the regularized loss $\mathcal{L}_{\text{reg}}$ on $N$ training examples ${\mathbb{D}}\coloneqq\{({\bm{x}}_{n},{\bm{y}}_{n})\in\mathbb{R}^{D}\times
\mathbb{R}^{C}\}_{n\in\mathcal{D}}$,

$$ $\displaystyle\mathcal{L}_{\text{reg}}({\bm{\theta}};\mathcal{D})\coloneqq \mathcal{L}({\bm{\theta}};\mathcal{D})+r({\bm{\theta}})\quad\text{with}\quad \mathcal{L}({\bm{\theta}};\mathcal{D})\coloneqq\frac{1}{|\mathcal{D}|}\sum_{n \in\mathcal{D}}\ell(f_{{\bm{\theta}}}({\bm{x}}_{n}),{\bm{y}}_{n}),\quad \mathcal{D}=\{1,\ldots,N\}.$ (1) $$

The empirical risk $\mathcal{L}$ measures the dissimilarity between the model’s
predictions $f_{{\bm{\theta}}}({\bm{x}}_{n})$ and the true outputs ${\bm{y}}_{n}$ via a loss function
$\ell:\mathbb{R}^{C}\times\mathbb{R}^{C}\rightarrow\mathbb{R}$. The regularizer $r:\mathbb{R}^{P}\to\mathbb{R}$, $r({\bm{\theta}})\coloneqq\nicefrac{{\beta}}{{2}}\,\|{\bm{\theta}}\|_{2}^{2}$ with $\beta\in\mathbb{R}_{\geq 0}$, penalizes the “complexity” of the
model.

### 2.1 Local full-batch & mini-batch quadratic approximations

Full-batch quadratic.
A local quadratic approximation of the regularized loss around ${\bm{\theta}}_{0}\in\mathbb{R}^{P}$ is given by the second-order Taylor expansion

$$ $\mathcal{L}_{\text{reg}}({\bm{\theta}};\mathcal{D})\;\approx\;q({\bm{\theta}}; \mathcal{D})\coloneqq\frac{1}{2}({\bm{\theta}}-{\bm{\theta}}_{0})^{\top}{\bm{H }}_{\mathcal{D}}({\bm{\theta}}-{\bm{\theta}}_{0})+({\bm{\theta}}-{\bm{\theta}} _{0})^{\top}{\bm{g}}_{\mathcal{D}}+c_{\mathcal{D}},$ (2) $$

where
$c_{\mathcal{D}}\coloneqq\mathcal{L}_{\text{reg}}({\bm{\theta}}_{0};\mathcal{D})$,
${\bm{g}}_{\mathcal{D}}\coloneqq\nabla\mathcal{L}_{\text{reg}}({\bm{\theta}}_{0
};\mathcal{D})$
and
${\bm{H}}_{\mathcal{D}}\coloneqq\nabla^{2}\mathcal{L}_{\text{reg}}({\bm{\theta}
}_{0};\mathcal{D})=\nabla^{2}\mathcal{L}({\bm{\theta}}_{0};\mathcal{D})+\beta{
\bm{I}}$
is (some approximation of) the Hessian at ${\bm{\theta}}_{0}$ (all derivatives are with respect
to the parameters ${\bm{\theta}}$ unless stated otherwise). As all quantities are evaluated on
the entire training set $\mathcal{D}$, we refer to this as the
full-batch quadratic. It holds that
$\nabla q({\bm{\theta}};\mathcal{D})={\bm{H}}_{\mathcal{D}}({\bm{\theta}}-{\bm{
\theta}}_{0})+{\bm{g}}_{\mathcal{D}}$
and
$\nabla^{2}q({\bm{\theta}};\mathcal{D})\equiv{\bm{H}}_{\mathcal{D}}.$

Mini-batch quadratic.
When the computations are intractable on the entire training set, the quantities in
Equation 2 are typically computed on a mini-batch—a
small randomly drawn subset—of the training data $\mathcal{B}\subset\mathcal{D},|\mathcal{B}|\ll N$, resulting in a stochastic quadratic
approximation $q(\,\cdot\,;\mathcal{B})\approx q(\,\cdot\,;\mathcal{D})$. As $c_{\mathcal{B}}$, ${\bm{g}}_{\mathcal{B}}$ and ${\bm{H}}_{\mathcal{B}}$ are
unbiased estimates of $c_{\mathcal{D}}$, ${\bm{g}}_{\mathcal{D}}$ and ${\bm{H}}_{\mathcal{D}}$,
this substitution may seem innocent, but, as we will see in
Section 3, it affects the geometry of the quadratic
approximation substantially.

Directional slope and curvature. Consider a cut $r$ through the quadratic
$q(\,\cdot\,;\mathcal{B})$ from ${\bm{\theta}}_{\bullet}\in\mathbb{R}^{P}$ along the
normalized direction ${\bm{d}}$, $\|{\bm{d}}\|=1$. It holds that (derivation in
Section A.1)
$r(\tau)\coloneqq q({\bm{\theta}}_{\bullet}+\tau{\bm{d}};\mathcal{B})=\nicefrac
{{1}}{{2}}\tau^{2}{\bm{d}}^{\top}\nabla^{2}q({\bm{\theta}}_{\bullet};\mathcal{
B})\,{\bm{d}}+\tau{\bm{d}}^{\top}\nabla q({\bm{\theta}}_{\bullet};\mathcal{B})
+\text{const}.$
So, as a function of $\tau$, $r:\mathbb{R}\to\mathbb{R}$ is a 1D parabola with derivatives
$r^{\prime}(\tau)=\tau\,{\bm{d}}^{\top}\nabla^{2}q({\bm{\theta}}_{\bullet};
\mathcal{B})\,{\bm{d}}+{\bm{d}}^{\top}\nabla q({\bm{\theta}}_{\bullet};
\mathcal{B})$ and
$r^{\prime\prime}(\tau)\equiv{\bm{d}}^{\top}\nabla^{2}q({\bm{\theta}}_{\bullet}
;\mathcal{B})\,{\bm{d}}.$
We denote the directional slope and curvature of the quadratic
$q(\,\cdot\,,\mathcal{B})$ at ${\bm{\theta}}_{\bullet}$ in direction ${\bm{d}}$ by

$$ $\partial_{{\bm{d}}}\,q({\bm{\theta}}_{\bullet};\mathcal{B})\coloneqq r^{\prime }(0)={\bm{d}}^{\top}\nabla q({\bm{\theta}}_{\bullet};\mathcal{B})\quad\text{ and}\quad\partial^{2}_{{\bm{d}}}\,q({\bm{\theta}}_{\bullet};\mathcal{B}) \coloneqq r^{\prime\prime}(0)={\bm{d}}^{\top}\nabla^{2}q({\bm{\theta}}_{ \bullet};\mathcal{B})\,{\bm{d}}.$ $$

The directional slope and curvature at ${\bm{\theta}}_{\bullet}$ are thus simply the projections
of the quadratic’s gradient
and Hessian
at that location onto the direction.

Eigenvalues as directional curvatures. The directional curvature of
the quadratic $q(\,\cdot\,;\mathcal{B})$ along one of ${\bm{H}}_{\mathcal{B}}$’s
normalized eigenvectors ${\bm{u}}$ coincides with the corresponding eigenvalue $\lambda$ since
$\partial^{2}_{{\bm{u}}}\,q({\bm{\theta}}_{\bullet};\mathcal{B})={\bm{u}}^{\top
}\nabla^{2}q({\bm{\theta}}_{\bullet};\mathcal{B})\,{\bm{u}}={\bm{u}}^{\top}{
\bm{H}}_{\mathcal{B}}\,{\bm{u}}=\lambda\|{\bm{u}}\|^{2}=\lambda.$
Thus, in the context of a quadratic, an
eigenvalue of the Hessian ${\bm{H}}_{\mathcal{B}}$ has a geometric interpretation as the directional curvature
along the respective eigenvector.

GGN & FIM. Next, we discuss second-order optimization methods and the Laplace
approximation (LA) for neural networks. Both techniques rely on local quadratic
approximations of the regularized loss function and require a positive definite
curvature matrix ${\bm{H}}_{\mathcal{B}}$. The empirical risk’s Hessian $\nabla^{2}\mathcal{L}({\bm{\theta}}_{0};\mathcal{B})$ can be indefinite and is therefore typically
replaced by (an approximation of) the positive semi-definite Generalized Gauss-Newton
matrix (GGN) ${\bm{G}}_{\mathcal{B}}$ or Fisher information matrix (FIM) ${\bm{F}}_{\mathcal{B}}$.
In fact, GGN and FIM are often identical (Martens, , Sec. 9.2). The resulting
${\bm{H}}_{\mathcal{B}}$ is positive definite if $\beta>0$, or when a damping term
$\delta{\bm{I}}$, $\delta\in\mathbb{R}_{>0}$ is added (e.g., in trust-region methods).

### 2.2 Second-order methods & conjugate gradients

The Newton step. Due to the simple polynomial form of the quadratic
$q(\,\cdot\,;\mathcal{B})$, its minimum can be derived in closed form and is
given by the Newton step
$\operatorname*{arg\,min}_{{\bm{\theta}}}q({\bm{\theta}};\mathcal{B})={\bm{
\theta}}_{0}-{\bm{H}}_{\mathcal{B}}^{-1}{\bm{g}}_{\mathcal{B}}.$ This serves as the basis for second-order optimizers like L-BFGS (Liu & Nocedal, ; Nocedal, ), the Hessian-free approach
(Martens, ) or K-FAC (Kronecker-factored approximate curvature)
(Martens & Grosse, ; Grosse & Martens, ; Martens et al., ).

Conjugate gradients. We focus on the method of conjugate gradients (CG)
(Hestenes & Stiefel, ), as it is a powerful method specifically designed to minimize
quadratics with positive definite Hessians effectively (details in
Section A.2). It is particularly useful in the context of large-scale
optimization because it only requires access to matrix-vector products with the
curvature matrix
${\bm{v}}\mapsto{\bm{H}}_{\mathcal{B}}\,{\bm{v}}$
that can be computed in a matrix-free manner
(Pearlmutter, ; Schraudolph, ), i.e. without ever materializing the full
matrix in memory—and it has been used successfully for training neural networks
(Martens, ).
Starting at ${\bm{\theta}}_{0}$, CG creates a sequence of iterates $({\bm{\theta}}_{0},\ldots,{\bm{\theta}}_{P})$. In each iteration $p$, two main steps are performed: (i) Given the
current position ${\bm{\theta}}_{p}$ and a normalized search direction ${\bm{d}}_{p}$, the algorithm
finds the minimum of the quadratic along ${\bm{\theta}}_{p}+\tau{\bm{d}}_{p}$, i.e.

$$ ${\bm{\theta}}_{p+1}={\bm{\theta}}_{p}+\tau_{p}{\bm{d}}_{p}\quad\text{with} \quad\tau_{p}\coloneqq\operatorname*{arg\,min}_{\tau\in\mathbb{R}}q({\bm{ \theta}}_{p}+\tau{\bm{d}}_{p};\mathcal{B})=-\frac{\partial_{{\bm{d}}_{p}}q({ \bm{\theta}}_{p};\mathcal{B})}{\partial^{2}_{{\bm{d}}_{p}}q({\bm{\theta}}_{p}; \mathcal{B})}.$ (3) $$

In the second step (ii), CG constructs the next search direction ${\bm{d}}_{p+1}$ such that
it is conjugate to all previous search directions, i.e. ${\bm{d}}_{p+1}^{\top}{\bm{H}}_{\mathcal{B}}\,{\bm{d}}_{i}=0$ for all $i\in\{1,\dots,p\}$.

### 2.3 Laplace approximation for neural networks

Laplace approximation. The Laplace approximation (LA) turns a trained standard
neural network into a Bayesian neural network in a post-hoc manner
(MacKay, ; Ritter et al., ; Kristiadi et al., ; Daxberger et al., )
(details in Section A.3). The idea is to reinterpret the
regularized loss $\mathcal{L}_{\text{reg}}$ as the negative unnormalized log posterior $\log p({\bm{\theta}}\mid{\mathbb{D}})$ of a specific Bayesian model.
This interpretation identifies the optimal parameters
${\bm{\theta}}_{\star}=\operatorname*{arg\,min}_{{\bm{\theta}}}\mathcal{L}_{
\text{reg}}({\bm{\theta}};\mathcal{D})=\operatorname*{arg\,max}_{{\bm{\theta}}
}p({\bm{\theta}}\mid{\mathbb{D}})$
as the mode of the posterior, i.e. as the maximum a posteriori (MAP) estimate. A
second-order approximation of the regularized loss around ${\bm{\theta}}_{0}\leftarrow{\bm{\theta}}_{\star}$
then translates into a Gaussian approximation of the posterior—the so-called Laplace
approximation (MacKay, ), i.e.

$$ $\mathcal{L}_{\text{reg}}({\bm{\theta}};\mathcal{D})\approx q({\bm{\theta}}; \mathcal{D})=\frac{1}{2}({\bm{\theta}}-{\bm{\theta}}_{\star})^{\top}{\bm{H}}_{ \mathcal{D}}({\bm{\theta}}-{\bm{\theta}}_{\star})+\text{const.}\quad\leadsto \quad p({\bm{\theta}}\mid{\mathbb{D}})\approx{\operatorname{\mathcal{N}} \mathopen{}\left({\bm{\theta}};{\bm{\theta}}_{\star},{\bm{\Sigma}}_{\mathcal{D }}\right)},$ (4) $$

with ${\bm{\Sigma}}_{\mathcal{D}}\coloneqq N^{-1}{\bm{H}}_{\mathcal{D}}^{-1}$ (or an
approximation thereof).
We obtain the predictive uncertainty $p({\bm{y}}_{\diamond}\mid{\bm{x}}_{\diamond},{\mathbb{D}})$ for some test input ${\bm{x}}_{\diamond}\in\mathbb{R}^{D}$ by propagating the
parameter uncertainty ${\operatorname{\mathcal{N}}\mathopen{}\left({\bm{\theta}}_{\star},{\bm{\Sigma}
}_{\mathcal{D}}\right)}$ to the model’s outputs
via the linearized network (Immer et al., ; Roy et al., ).

Full-batch vs. mini-batch LA. It is common practice to compute the LA on the
entire training set. Depending on the curvature approximation, this comes at
considerable computational costs. For example, a full-batch LA is prohibitive even for
moderately sized models/datasets when a low-rank approximation of the Hessian is
computed via repeated Hessian-vector products (each of which requires a full pass over
the training data); and it is essentially infeasible for model classes like LLMs, which
are trained on massive datasets. However, what adds most to the costs is that it is
standard to tune the prior precision (Daxberger et al., ). This adds
another outer loop that requires the same procedure to be performed multiple times.
Being able to emulate the behavior of the full-batch quadratic on a mini-batch would
thus be useful. We therefore study the mini-batch setting, i.e. we replace
$q(\,\cdot\,;\mathcal{D})$ by $q(\,\cdot\,;\mathcal{B})$ in
Equation 4. We will see in Section 6.2 that, when
mitigating the associated biases, a mini-batch LA can be a good proxy for the full-batch
LA.

## 3 The shape of a mini-batch quadratic

This section studies the “shape” of a mini-batch quadratic $q(\,\cdot\,;\!\mathcal{B})$ and how it differs from $q(\,\cdot\,;\!\mathcal{D})$.

### 3.1 Empirical study of the directional slopes and curvatures

The high-curvature subspace is relevant for all common use cases. In our
empirical study, we focus on the top-curvature subspace. This subspace is
particularly relevant for several reasons:

- 1.
By the Eckart-Young-Mirsky Theorem, a truncated SVD is Frobenius norm-optimal,
i.e. a low-rank approximation using the top eigenvectors is ideal from a
theoretical perspective. As the spectrum of the Hessian typically decays quickly
(Ghorbani et al., ), the bulk of the curvature information is
contained in the top-curvature subspace.
- 2.
In the context of optimization, it has been observed that the gradient mainly
lives in the high-curvature space (Gur-Ari et al., ; Dangel et al., ).
Thus, it makes sense for a second-order method to operate mainly in that space,
as steps outside of it can not be expected to reduce the objective function
significantly.
- 3.
In the context of the LA, directions of large curvature correspond to directions
in the weight space with low variance, i.e. these directions capture
what we know about the model’s parameters. Consequently,
Daxberger et al. (, p. 19) describe a low-rank approximation of the
Hessian based on its top eigenvectors.

Experimental procedure. We use the same setting as in
Figure 1: The fully trained All-CNN-C model on the CIFAR-100 dataset.
To isolate the effect of data subsampling, we eliminate all other sources of
noise. Thus, we remove the dropout layers from the model. We use the cross-entropy loss,
an $\ell^{2}$-regularizer, and train the model with SGD for $350$ epochs, see
Section B.1 for details.

We then pick a mini-batch $\mathcal{B}_{m}$ of size $512$ and compute the $100$
eigenvectors ${\bm{u}}_{1},\ldots,{\bm{u}}_{100}$ to the $100$ largest
eigenvalues of ${\bm{H}}_{\mathcal{B}_{m}}\leftarrow{\bm{G}}_{\mathcal{B}_{m}}+\beta{\bm{I}}$. That is
the Hessian of the $\ell^{2}$-regularized mini-batch loss, where we replaced $\nabla^{2}\mathcal{L}({\bm{\theta}}_{\star};\mathcal{B}_{m})$ with the GGN approximation. Next, we compute the
directional slopes and curvatures for all mini-batch quadratics
$q(\,\cdot\,;\mathcal{B}_{m^{\prime}})$, $m^{\prime}\in\{1,\dots,M\}$ along
those $100$ eigenvectors. For a fixed eigenvector ${\bm{u}}_{p}$, the average of
those directional slopes/curvatures over all mini-batches coincides with the
directional slope/curvature of the full-batch quadratic,
i.e.

$$ $\frac{1}{M}\sum_{m^{\prime}=1}^{M}\underbracket{\partial_{{\bm{u}}_{p}}q({\bm{ \theta}}_{\star};\mathcal{B}_{m^{\prime}})}_{\text{one~{}}\leavevmode\hbox to 3.96pt{\vbox to3.96pt{\pgfpicture\makeatletter\hbox{\hskip 1.97989pt\lower-1.9 7989pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{ pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt} \pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{ tikz@color}{rgb}{1,1,1}\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{ rgb}{0.8671875,0.51953125,0.3203125}\pgfsys@color@rgb@fill{0.8671875}{0.519531 25}{0.3203125}\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{tikz@color}{rgb}{1,1,1} \definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{ 1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ }\pgfsys@color@gray@fill{1} \pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{ 0.8671875,0.51953125,0.3203125}\pgfsys@color@rgb@fill{0.8671875}{0.51953125}{0 .3203125}\pgfsys@invoke{ }\pgfsys@moveto{1.97989pt}{0.0pt}\pgfsys@curveto{1.97 989pt}{1.09348pt}{1.09348pt}{1.97989pt}{0.0pt}{1.97989pt}\pgfsys@curveto{-1.09 348pt}{1.97989pt}{-1.97989pt}{1.09348pt}{-1.97989pt}{0.0pt}\pgfsys@curveto{-1. 97989pt}{-1.09348pt}{-1.09348pt}{-1.97989pt}{0.0pt}{-1.97989pt}\pgfsys@curveto {1.09348pt}{-1.97989pt}{1.97989pt}{-1.09348pt}{1.97989pt}{0.0pt} \pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fill\pgfsys@invoke{ } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}{{{{}}\pgfsys@beginscope \pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{0.0pt}{0.0pt} \pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{ 1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1} \pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}\text{~{}and many~{}}\leavevmode\hbox to3.96 pt{\vbox to3.96pt{\pgfpicture\makeatletter\hbox{\hskip 1.97989pt\lower-1.97989 pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor }{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt} \pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{ tikz@color}{rgb}{1,1,1}\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{ rgb}{0.296875,0.4453125,0.69140625}\pgfsys@color@rgb@fill{0.296875}{0.4453125} {0.69140625}\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{tikz@color}{rgb}{1,1,1} \definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{ 1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ }\pgfsys@color@gray@fill{1} \pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{ 0.296875,0.4453125,0.69140625}\pgfsys@color@rgb@fill{0.296875}{0.4453125}{0.69 140625}\pgfsys@invoke{ }\pgfsys@moveto{1.97989pt}{0.0pt}\pgfsys@curveto{1.9798 9pt}{1.09348pt}{1.09348pt}{1.97989pt}{0.0pt}{1.97989pt}\pgfsys@curveto{-1.0934 8pt}{1.97989pt}{-1.97989pt}{1.09348pt}{-1.97989pt}{0.0pt}\pgfsys@curveto{-1.97 989pt}{-1.09348pt}{-1.09348pt}{-1.97989pt}{0.0pt}{-1.97989pt}\pgfsys@curveto{1 .09348pt}{-1.97989pt}{1.97989pt}{-1.09348pt}{1.97989pt}{0.0pt} \pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fill\pgfsys@invoke{ } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}{{{{}}\pgfsys@beginscope \pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{0.0pt}{0.0pt} \pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{ 1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1} \pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}=\underbracket{\partial_{{\bm{u}}_{p}}q({\bm {\theta}}_{\star};\mathcal{D})}_{\text{{\color[rgb]{ 0.33203125,0.66015625,0.40625}\definecolor[named]{pgfstrokecolor}{rgb}{ 0.33203125,0.66015625,0.40625}\char 58}}}\quad\text{and}\quad\frac{1}{M}\sum_{ m^{\prime}=1}^{M}\underbracket{\partial^{2}_{{\bm{u}}_{p}}q({\bm{\theta}}_{ \star};\mathcal{B}_{m^{\prime}})}_{\text{one~{}}\leavevmode\hbox to3.96pt{ \vbox to3.96pt{\pgfpicture\makeatletter\hbox{\hskip 1.97989pt\lower-1.97989pt \hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt} \pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{ tikz@color}{rgb}{1,1,1}\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{ rgb}{0.8671875,0.51953125,0.3203125}\pgfsys@color@rgb@fill{0.8671875}{0.519531 25}{0.3203125}\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{tikz@color}{rgb}{1,1,1} \definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{ 1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ }\pgfsys@color@gray@fill{1} \pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{ 0.8671875,0.51953125,0.3203125}\pgfsys@color@rgb@fill{0.8671875}{0.51953125}{0 .3203125}\pgfsys@invoke{ }\pgfsys@moveto{1.97989pt}{0.0pt}\pgfsys@curveto{1.97 989pt}{1.09348pt}{1.09348pt}{1.97989pt}{0.0pt}{1.97989pt}\pgfsys@curveto{-1.09 348pt}{1.97989pt}{-1.97989pt}{1.09348pt}{-1.97989pt}{0.0pt}\pgfsys@curveto{-1. 97989pt}{-1.09348pt}{-1.09348pt}{-1.97989pt}{0.0pt}{-1.97989pt}\pgfsys@curveto {1.09348pt}{-1.97989pt}{1.97989pt}{-1.09348pt}{1.97989pt}{0.0pt} \pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fill\pgfsys@invoke{ } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}{{{{}}\pgfsys@beginscope \pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{0.0pt}{0.0pt} \pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{ 1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1} \pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}\text{~{}and many~{}}\leavevmode\hbox to3.96 pt{\vbox to3.96pt{\pgfpicture\makeatletter\hbox{\hskip 1.97989pt\lower-1.97989 pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor }{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt} \pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{ tikz@color}{rgb}{1,1,1}\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{ rgb}{0.296875,0.4453125,0.69140625}\pgfsys@color@rgb@fill{0.296875}{0.4453125} {0.69140625}\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{tikz@color}{rgb}{1,1,1} \definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{ 1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ }\pgfsys@color@gray@fill{1} \pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{ 0.296875,0.4453125,0.69140625}\pgfsys@color@rgb@fill{0.296875}{0.4453125}{0.69 140625}\pgfsys@invoke{ }\pgfsys@moveto{1.97989pt}{0.0pt}\pgfsys@curveto{1.9798 9pt}{1.09348pt}{1.09348pt}{1.97989pt}{0.0pt}{1.97989pt}\pgfsys@curveto{-1.0934 8pt}{1.97989pt}{-1.97989pt}{1.09348pt}{-1.97989pt}{0.0pt}\pgfsys@curveto{-1.97 989pt}{-1.09348pt}{-1.09348pt}{-1.97989pt}{0.0pt}{-1.97989pt}\pgfsys@curveto{1 .09348pt}{-1.97989pt}{1.97989pt}{-1.09348pt}{1.97989pt}{0.0pt} \pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fill\pgfsys@invoke{ } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}{{{{}}\pgfsys@beginscope \pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{0.0pt}{0.0pt} \pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{ 1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1} \pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}=\underbracket{\partial^{2}_{{\bm{u}}_{p}}q( {\bm{\theta}}_{\star};\mathcal{D})}_{\text{{\color[rgb]{ 0.33203125,0.66015625,0.40625}\definecolor[named]{pgfstrokecolor}{rgb}{ 0.33203125,0.66015625,0.40625}\char 58}}}\!,$ (5) $$

derivation in in Section A.1. The colored markers in
Equation 5 refer to
Figure 2. We repeat this procedure for three mini-batches $\mathcal{B}_{m}$, $m\in\{0,1,2\}$.

Figure: Figure 2: Directional slopes and curvatures are biased. We use the CIFAR-100 dataset with the fully trained All-CNN-C model and draw three mini-batches $\mathcal{B}_{m}$ of size $|\mathcal{B}_{m}|=512$ to compute the top $100$ eigenvectors ${\bm{u}}_{1},\ldots,{\bm{u}}_{100}$. For each mini-batch/column, we show the directional slopes (Top) and curvatures (Bottom) evaluated on (i) $q({\bm{\theta}}_{\star};\mathcal{B}_{m})$ (i.e. on the same mini-batch of data) as , (ii) $q({\bm{\theta}}_{\star};\mathcal{B}_{m^{\prime}})$ for $m^{\prime}\neq m$ (i.e. for all other mini-batches) as and (iii) the full-batch quadratic (the average of the orange and all blue dots, see Equation 5) as ✚. For the top panel, we switch the order and sign of the eigenvectors such that the orange dots are all above zero and in descending order. There is a strong, systematic bias, particularly in the curvature: Computing the eigenvectors and directional curvatures on the same data results in over-estimation by roughly one order of magnitude.
Refer to caption: x2.png

Directional slopes and curvatures are biased. Figure 2 reveals a
systematic bias in the directional slopes and, more pronounced, in the directional
curvatures: When eigenvectors and directional derivatives are computed on the
same mini-batch, curvature is overestimated by roughly one order of magnitude
compared to the curvature of the full-batch quadratic $q(\,\cdot\,;\mathcal{D})$. Within the space that actually carries curvature information—the
top-eigenspace of the quadratic’s Hessian—the curvature magnitude is thus not at all
representative of the true underlying loss landscape. For other mini-batches,
the directional slopes and curvatures are similar to the full-batch quadratic. This is
because the averages in Equation 5 are dominated by
these unbiased samples.

We present additional results for batch size $2048$ (instead of $512$), the Hessian
$\nabla^{2}\mathcal{L}({\bm{\theta}}_{\star};\mathcal{B}_{m})$ (instead of its GGN approximation) and CG search directions (instead of eigenvectors) in Section B.4. The bias
is present in all settings, but less pronounced for larger batch sizes. For the
CG search directions, the bias in directional slope is much more distinct than for the
eigenvectors: The biased slope is always negative, while the full-batch quadratic’s
slope is in fact positive for most CG directions!

### 3.2 Where do the biases come from?

In the following, we provide an explanation for the biases in the directional slopes and
curvatures (i.e. the gap between the orange and a blue dot in Figure 2) from a
theoretical perspective.

#### 3.2.1 Bias in the directional slope

Here, we focus on the CG search directions since the bias in the directional slope is
even more pronounced for those directions than for the eigenvectors. This is not
accidental! The CG directions are constructed from gradients—and gradients are
directions that maximize the steepness for one
particular mini-batch quadratic. For other mini-batch quadratics, the steepness
along those directions (i.e. the directional slope ) is therefore
less extreme. We formalize this intuition in Section A.4.

#### 3.2.2 Bias in the directional curvature

Next, we consider the bias in the directional curvature along the eigenvectors of the
curvature matrix.

Directional curvature along ${\bm{H}}_{\mathcal{B}}$’s eigenvectors.
Let ${\bm{u}}_{1},\ldots,{\bm{u}}_{P}$ and $\tilde{{\bm{u}}}_{1},\ldots,\tilde{{\bm{u}}}_{P}$ denote the eigenvectors of two mini-batch Hessians
${\bm{H}}_{\mathcal{B}}$ and ${\bm{H}}_{\tilde{\mathcal{B}}}$, respectively. Assume that the
corresponding eigenvalues are in descending order, i.e. $\lambda_{1}\geq\ldots\geq\lambda_{P}$ and $\tilde{\lambda}_{1}\geq\ldots\geq\tilde{\lambda}_{P}$. We can write the directional curvatures on $\mathcal{B}$
and $\tilde{\mathcal{B}}$ along an eigenvector ${\bm{u}}_{i}$ as (details in
Section A.5)

$$ $\underbracket{\partial^{2}_{{\bm{u}}_{i}}q({\bm{\theta}}_{\bullet};\tilde{ \mathcal{B}})}_{\leavevmode\hbox to3.96pt{\vbox to3.96pt{\pgfpicture \makeatletter\hbox{\hskip 1.97989pt\lower-1.97989pt\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to 0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{ tikz@color}{rgb}{1,1,1}\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{ rgb}{0.296875,0.4453125,0.69140625}\pgfsys@color@rgb@fill{0.296875}{0.4453125} {0.69140625}\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{tikz@color}{rgb}{1,1,1} \definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{ 1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ }\pgfsys@color@gray@fill{1} \pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{ 0.296875,0.4453125,0.69140625}\pgfsys@color@rgb@fill{0.296875}{0.4453125}{0.69 140625}\pgfsys@invoke{ }\pgfsys@moveto{1.97989pt}{0.0pt}\pgfsys@curveto{1.9798 9pt}{1.09348pt}{1.09348pt}{1.97989pt}{0.0pt}{1.97989pt}\pgfsys@curveto{-1.0934 8pt}{1.97989pt}{-1.97989pt}{1.09348pt}{-1.97989pt}{0.0pt}\pgfsys@curveto{-1.97 989pt}{-1.09348pt}{-1.09348pt}{-1.97989pt}{0.0pt}{-1.97989pt}\pgfsys@curveto{1 .09348pt}{-1.97989pt}{1.97989pt}{-1.09348pt}{1.97989pt}{0.0pt} \pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fill\pgfsys@invoke{ } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}{{{{}}\pgfsys@beginscope \pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{0.0pt}{0.0pt} \pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{ 1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1} \pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}={\bm{u}}_{i}^{\top}{\bm{H}}_{\tilde{ \mathcal{B}}}{\bm{u}}_{i}=\sum_{p=1}^{P}\tilde{\lambda}_{p}\,{\bm{\Omega}}_{i, p},\quad\text{and}\quad\underbracket{\partial^{2}_{{\bm{u}}_{i}}q({\bm{\theta} }_{\bullet};\mathcal{B})}_{\leavevmode\hbox to3.96pt{\vbox to3.96pt{ \pgfpicture\makeatletter\hbox{\hskip 1.97989pt\lower-1.97989pt\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to 0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{ tikz@color}{rgb}{1,1,1}\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{ rgb}{0.8671875,0.51953125,0.3203125}\pgfsys@color@rgb@fill{0.8671875}{0.519531 25}{0.3203125}\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{tikz@color}{rgb}{1,1,1} \definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{ 1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ }\pgfsys@color@gray@fill{1} \pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{ 0.8671875,0.51953125,0.3203125}\pgfsys@color@rgb@fill{0.8671875}{0.51953125}{0 .3203125}\pgfsys@invoke{ }\pgfsys@moveto{1.97989pt}{0.0pt}\pgfsys@curveto{1.97 989pt}{1.09348pt}{1.09348pt}{1.97989pt}{0.0pt}{1.97989pt}\pgfsys@curveto{-1.09 348pt}{1.97989pt}{-1.97989pt}{1.09348pt}{-1.97989pt}{0.0pt}\pgfsys@curveto{-1. 97989pt}{-1.09348pt}{-1.09348pt}{-1.97989pt}{0.0pt}{-1.97989pt}\pgfsys@curveto {1.09348pt}{-1.97989pt}{1.97989pt}{-1.09348pt}{1.97989pt}{0.0pt} \pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fill\pgfsys@invoke{ } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}{{{{}}\pgfsys@beginscope \pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{0.0pt}{0.0pt} \pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{ 1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1} \pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}={\bm{u}}_{i}^{\top}{\bm{H}}_{\mathcal{B}}{ \bm{u}}_{i}=\lambda_{i}.$ (6) $$

The weights $\{{\bm{\Omega}}_{i,p}\coloneqq({\bm{u}}_{i}^{\top}\tilde{{\bm{u}}}_{p})^{2}\}_
{p=1}^{P}$ are non-negative and sum to one, i.e. $\sum_{p=1}^{P}{\bm{\Omega}}_{i,p}=1$. The bias in the directional curvature thus
originates from misalignment of the eigenspaces of the two curvature
matrices—captured by the weights ${\bm{\Omega}}_{i,p}$—and/or a systematic difference
in their spectra.

Curvature bias is not due to differing spectra… Assume that the eigenspaces
are perfectly aligned, i.e. ${\bm{\Omega}}_{i,i}=1$ and ${\bm{\Omega}}_{i,p}=0\;\forall p\neq i$. In this case, we obtain $\partial^{2}_{{\bm{u}}_{i}}q({\bm{\theta}}_{\bullet};\tilde{\mathcal{B}})=
\tilde{\lambda}_{i}$ from Equation 6, so the bias
originates exclusively from the differences in the spectra. Figure 2
shows the eigenvalues (as directional curvatures) for three different CIFAR-100 mini-batches. As they are very similar, this cannot serve as the main explanation for
the curvature bias.

…but due to misaligned eigenspaces. Now, assume that the spectra of
${\bm{H}}_{\mathcal{B}}$ and ${\bm{H}}_{\tilde{\mathcal{B}}}$ are identical, i.e. $\lambda_{p}=\tilde{\lambda}_{p}\,\forall p\in\{1,\ldots,P\}$ which simplifies the
unbiased estimate in Equation 6 to
$\partial^{2}_{{\bm{u}}_{i}}q({\bm{\theta}}_{\bullet};\tilde{\mathcal{B}})=\sum
_{p=1}^{P}\lambda_{p}\,{\bm{\Omega}}_{i,p}$.
Consider the curvature along ${\bm{u}}_{1}$ as an example. If ${\bm{u}}_{1}=\tilde{{\bm{u}}}_{1}$, there is only one non-zero weight ${\bm{\Omega}}_{1,1}=1$ and the two
directional curvatures are identical. However, if there is significant overlap with any
other eigenvectors (i.e. some weight is distributed also on the lower-curvature
directions), the resulting curvature $\partial^{2}_{{\bm{u}}_{1}}q({\bm{\theta}}_{\bullet};\tilde{\mathcal{B}})$ is smaller than $\partial^{2}_{{\bm{u}}_{1}}q({\bm{\theta}}_{\bullet};\mathcal{B})$.
Analogously, for ${\bm{u}}_{P}$, the directional curvature on $\tilde{\mathcal{B}}$ is
larger than on $\mathcal{B}$ if there is significant overlap between
${\bm{u}}_{P}$ and some of ${\bm{H}}_{\tilde{\mathcal{B}}}$’s
higher-curvature eigenvectors.
This can be formalized by the following inequalities (derivation in Section A.5):

$$ $\underbracket{\partial^{2}_{{\bm{u}}_{1}}q({\bm{\theta}}_{\bullet};\tilde{ \mathcal{B}})}_{\leavevmode\hbox to3.96pt{\vbox to3.96pt{\pgfpicture \makeatletter\hbox{\hskip 1.97989pt\lower-1.97989pt\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to 0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{ tikz@color}{rgb}{1,1,1}\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{ rgb}{0.296875,0.4453125,0.69140625}\pgfsys@color@rgb@fill{0.296875}{0.4453125} {0.69140625}\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{tikz@color}{rgb}{1,1,1} \definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{ 1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ }\pgfsys@color@gray@fill{1} \pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{ 0.296875,0.4453125,0.69140625}\pgfsys@color@rgb@fill{0.296875}{0.4453125}{0.69 140625}\pgfsys@invoke{ }\pgfsys@moveto{1.97989pt}{0.0pt}\pgfsys@curveto{1.9798 9pt}{1.09348pt}{1.09348pt}{1.97989pt}{0.0pt}{1.97989pt}\pgfsys@curveto{-1.0934 8pt}{1.97989pt}{-1.97989pt}{1.09348pt}{-1.97989pt}{0.0pt}\pgfsys@curveto{-1.97 989pt}{-1.09348pt}{-1.09348pt}{-1.97989pt}{0.0pt}{-1.97989pt}\pgfsys@curveto{1 .09348pt}{-1.97989pt}{1.97989pt}{-1.09348pt}{1.97989pt}{0.0pt} \pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fill\pgfsys@invoke{ } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}{{{{}}\pgfsys@beginscope \pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{0.0pt}{0.0pt} \pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{ 1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1} \pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}\leq\underbracket{\partial^{2}_{{\bm{u}}_{1} }q({\bm{\theta}}_{\bullet};\mathcal{B})}_{\leavevmode\hbox to3.96pt{\vbox to 3.96pt{\pgfpicture\makeatletter\hbox{\hskip 1.97989pt\lower-1.97989pt\hbox to0 .0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{ 0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill {0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ } \nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{ tikz@color}{rgb}{1,1,1}\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{ rgb}{0.8671875,0.51953125,0.3203125}\pgfsys@color@rgb@fill{0.8671875}{0.519531 25}{0.3203125}\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{tikz@color}{rgb}{1,1,1} \definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{ 1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ }\pgfsys@color@gray@fill{1} \pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{ 0.8671875,0.51953125,0.3203125}\pgfsys@color@rgb@fill{0.8671875}{0.51953125}{0 .3203125}\pgfsys@invoke{ }\pgfsys@moveto{1.97989pt}{0.0pt}\pgfsys@curveto{1.97 989pt}{1.09348pt}{1.09348pt}{1.97989pt}{0.0pt}{1.97989pt}\pgfsys@curveto{-1.09 348pt}{1.97989pt}{-1.97989pt}{1.09348pt}{-1.97989pt}{0.0pt}\pgfsys@curveto{-1. 97989pt}{-1.09348pt}{-1.09348pt}{-1.97989pt}{0.0pt}{-1.97989pt}\pgfsys@curveto {1.09348pt}{-1.97989pt}{1.97989pt}{-1.09348pt}{1.97989pt}{0.0pt} \pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fill\pgfsys@invoke{ } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}{{{{}}\pgfsys@beginscope \pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{0.0pt}{0.0pt} \pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{ 1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1} \pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}\quad\text{and}\quad\underbracket{\partial^{ 2}_{{\bm{u}}_{P}}q({\bm{\theta}}_{\bullet};\tilde{\mathcal{B}})}_{\leavevmode \hbox to3.96pt{\vbox to3.96pt{\pgfpicture\makeatletter\hbox{\hskip 1.97989pt \lower-1.97989pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{ pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt} \pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{ tikz@color}{rgb}{1,1,1}\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{ rgb}{0.296875,0.4453125,0.69140625}\pgfsys@color@rgb@fill{0.296875}{0.4453125} {0.69140625}\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{tikz@color}{rgb}{1,1,1} \definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{ 1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ }\pgfsys@color@gray@fill{1} \pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{ 0.296875,0.4453125,0.69140625}\pgfsys@color@rgb@fill{0.296875}{0.4453125}{0.69 140625}\pgfsys@invoke{ }\pgfsys@moveto{1.97989pt}{0.0pt}\pgfsys@curveto{1.9798 9pt}{1.09348pt}{1.09348pt}{1.97989pt}{0.0pt}{1.97989pt}\pgfsys@curveto{-1.0934 8pt}{1.97989pt}{-1.97989pt}{1.09348pt}{-1.97989pt}{0.0pt}\pgfsys@curveto{-1.97 989pt}{-1.09348pt}{-1.09348pt}{-1.97989pt}{0.0pt}{-1.97989pt}\pgfsys@curveto{1 .09348pt}{-1.97989pt}{1.97989pt}{-1.09348pt}{1.97989pt}{0.0pt} \pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fill\pgfsys@invoke{ } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}{{{{}}\pgfsys@beginscope \pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{0.0pt}{0.0pt} \pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{ 1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1} \pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}\geq\underbracket{\partial^{2}_{{\bm{u}}_{P} }q({\bm{\theta}}_{\bullet};\mathcal{B})}_{\leavevmode\hbox to3.96pt{\vbox to 3.96pt{\pgfpicture\makeatletter\hbox{\hskip 1.97989pt\lower-1.97989pt\hbox to0 .0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{ 0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill {0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ } \nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{ tikz@color}{rgb}{1,1,1}\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{ rgb}{0.8671875,0.51953125,0.3203125}\pgfsys@color@rgb@fill{0.8671875}{0.519531 25}{0.3203125}\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{tikz@color}{rgb}{1,1,1} \definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{ 1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ }\pgfsys@color@gray@fill{1} \pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{ 0.8671875,0.51953125,0.3203125}\pgfsys@color@rgb@fill{0.8671875}{0.51953125}{0 .3203125}\pgfsys@invoke{ }\pgfsys@moveto{1.97989pt}{0.0pt}\pgfsys@curveto{1.97 989pt}{1.09348pt}{1.09348pt}{1.97989pt}{0.0pt}{1.97989pt}\pgfsys@curveto{-1.09 348pt}{1.97989pt}{-1.97989pt}{1.09348pt}{-1.97989pt}{0.0pt}\pgfsys@curveto{-1. 97989pt}{-1.09348pt}{-1.09348pt}{-1.97989pt}{0.0pt}{-1.97989pt}\pgfsys@curveto {1.09348pt}{-1.97989pt}{1.97989pt}{-1.09348pt}{1.97989pt}{0.0pt} \pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fill\pgfsys@invoke{ } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}{{{{}}\pgfsys@beginscope \pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{0.0pt}{0.0pt} \pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{ 1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1} \pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}\!.$ (7) $$

In general, if the eigenspaces are not perfectly aligned such that weight is distributed
on several eigenvectors, this leads to less extreme directional curvatures on
mini-batch $\tilde{\mathcal{B}}$ on both ends of the spectrum.
Figure 4 shows the weights ${\bm{\Omega}}_{i,p}$ as pixels. The overlap between
the eigenspaces is far from perfect, i.e. one eigenvector from $\mathcal{B}$ overlaps with
several eigenvectors from $\tilde{\mathcal{B}}$ to some extent.
This explains the curvature overestimation in the top curvature subspace we observe in
Figure 2 and identifies the misalignment of the eigenspaces as the dominating
factor for the curvature bias.

#### 3.2.3 Summary of the theoretical findings

The CG search directions and the eigenvectors of the curvature matrix are both
designed to be “extreme” in some sense: The CG directions are based on
gradients that maximize steepness of the quadratic $q(\,\cdot\,;\mathcal{B})$,
while the top/bottom eigenvectors subsume directions of largest/smallest curvature.
However, these directions are extreme only for one particular mini-batch $\mathcal{B}$.
Another mini-batch $\tilde{\mathcal{B}}$ has its own extreme directions that typically
differ from those of $\mathcal{B}$. Thus, the extreme directions for
$\mathcal{B}$ are less extreme for $\tilde{\mathcal{B}}$.
Projecting both quadratics onto $\mathcal{B}$’s directions consequently leads to extreme
steepness and curvatures for $\mathcal{B}$, but less extreme values for
$\tilde{\mathcal{B}}$.
This result is an instance of the classic regression to the mean
(Galton, ): Using an algorithm to find the directions of most extreme
steepness/curvature in one particular mini-batch, we must expect the steepness/curvature
to be less extreme on most other batches (and thus also on the entire
dataset). We can expect this phenomenon to occur for other datasets, models, and curvature
proxies as well, since the underlying mechanism is the stochasticity of the geometric
information.

Figure: Figure 3: In practice, eigenspaces are misaligned. We reuse the setting of Figure 2 and compute the top $100$ eigenvectors ${\bm{U}}_{m}\!\in\mathbb{R}^{P\times 100}$ for $\{\mathcal{B}_{m}\}_{m\in\{0,1,2\}}$. The weights ${\bm{\Omega}}_{i,j}$ are shown as a $100\times 100$ greyscale image (color ranges from black for ${\bm{\Omega}}_{i,j}\leq 10^{-8}$ to white for ${\bm{\Omega}}_{i,j}=1$) for $m\in\{0,1\}$, $m^{\prime}\in\{0,1,2\}$. Clearly, the eigenspaces for different mini-batches are not perfectly aligned as eigenvectors from $\mathcal{B}_{m}$ overlap with several eigenvectors from $\mathcal{B}_{m^{\prime}}$.
Refer to caption: x3.png

## 4 Debiasing mini-batch quadratics for applications

We here argue that the biases affect second-order applications, and
develop debiasing strategies.

### 4.1 Implications for second-order optimization and the Laplace approximation

Detrimental updates in second-order optimizers.
In the context of second-order optimization, both the biases in the directional slopes
and curvatures are relevant. From Equation 3, the CG update
magnitude $\tau_{p}$ to reach the minimum of $q({\bm{\theta}}_{p}+\tau{\bm{d}}_{p};\mathcal{B}_{m})$ is given by the negative ratio of the directional slope and curvature at
the current iterate ${\bm{\theta}}_{p}$ in the direction ${\bm{d}}_{p}$—that is the 1D Newton step
along that cut.(^2^22The exact same argument can also be made for the eigenvector directions as the Newton step can be decomposed into 1D Newton steps along the eigenvectors.) As both these quantities are biased, so is $\tau_{p}$ as shown in
Figure 4: While the update magnitudes for $\mathcal{B}_{m}$ are
always positive (a property of CG), minimizing the other—equally
valid—quadratics would require negative update magnitudes for most of the
CG directions. In this sense, naive CG on a single mini-batch of data makes updates in
the wrong direction. This can be attributed to the bias in the directional slope since
the slope determines the sign of $\tau_{p}$. Overestimation of the directional curvature
is “accidentally beneficial” in this case as it leads to smaller steps.

Unreliable uncertainty quantification with the Laplace approximation.
For the LA, only the bias in the directional curvature is relevant. After
Section 2.3, the approximate posterior covariance over the
network’s parameters is given by ${\bm{\Sigma}}_{\mathcal{B}}=N^{-1}{\bm{H}}_{\mathcal{B}}^{-1}$. Via the eigendecomposition ${\bm{H}}_{\mathcal{B}}=\sum_{p=1}^{P}\lambda_{p}{\bm{u}}_{p}{\bm{u}}_{p}^{\top}$, we obtain ${\bm{\Sigma}}_{\mathcal{B}}=N^{-1}\sum_{p=1}^{P}\lambda_{p}^{-1}{\bm{u}}_{p}{
\bm{u}}_{p}^{\top}$. Due
to the biases we describe in Section 3, the directional
curvatures $\lambda_{p}$ are not representative of the true underlying curvature,
resulting in a deformed posterior covariance ${\bm{\Sigma}}_{\mathcal{B}}$.
Specifically, the overestimation of the curvature in the top-curvature subspace
translates into an underestimation of the uncertainty in the posterior
covariance (due to the inversion) with potentially severe consequences in
safety-critical applications.

### 4.2 Debiasing strategies

We now turn to strategies that mitigate the biases in second-order optimization and the
LA. An empirical evaluation of these methods follows in Sections 6.1 and 6.2.

Decoupling directions from magnitudes with a two-batch strategy. The approaches
we propose are simple yet effective. The idea is to commit to the imperfect directions
from one mini-batch (as before) but use an additional mini-batch to estimate
the directional derivatives. With this, we decouple the mechanism that
determines the parameter subspace in which the method operates from the slope and
curvature measurements within the space. Effectively, we use the blue dots from
Figures 2 and 4 instead of the orange dots and thus obtain much more
realistic estimates of the actual loss function’s geometry (within the subspace defined
by the first mini-batch). Next, we describe in more detail how this strategy can be
applied to debias CG and the LA.

#### 4.2.1 Debiased conjugate gradients

Debiased approach. For the debiased CG method, we need to implement two
processes: (i) The first process applies $K\leq P$ CG iterations to
the mini-batch quadratic $q(\,\cdot\,;\mathcal{B})$ and collects the search
directions $({\bm{d}}_{1},\ldots,{\bm{d}}_{K})$. As before, this defines the subspace in
which CG operates. (ii) The second process recomputes the trajectory
$(\tilde{{\bm{\theta}}}_{1},\ldots,\tilde{{\bm{\theta}}}_{K})$ within that subspace using
debiased update magnitudes that are computed on a different mini-batch
$\tilde{\mathcal{B}}$, i.e. we use $\tilde{{\bm{\theta}}}_{0}\coloneqq{\bm{\theta}}_{0}$ and

$$ $\tilde{{\bm{\theta}}}_{p+1}\coloneqq\tilde{{\bm{\theta}}}_{p}+\tilde{\tau}_{p} {\bm{d}}_{p}\quad\text{with}\quad\underbracket{\tilde{\tau}_{p}}_{\leavevmode \hbox to3.96pt{\vbox to3.96pt{\pgfpicture\makeatletter\hbox{\hskip 1.97989pt \lower-1.97989pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{ pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt} \pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{ tikz@color}{rgb}{1,1,1}\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{ rgb}{0.296875,0.4453125,0.69140625}\pgfsys@color@rgb@fill{0.296875}{0.4453125} {0.69140625}\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{tikz@color}{rgb}{1,1,1} \definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{ 1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ }\pgfsys@color@gray@fill{1} \pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{ 0.296875,0.4453125,0.69140625}\pgfsys@color@rgb@fill{0.296875}{0.4453125}{0.69 140625}\pgfsys@invoke{ }\pgfsys@moveto{1.97989pt}{0.0pt}\pgfsys@curveto{1.9798 9pt}{1.09348pt}{1.09348pt}{1.97989pt}{0.0pt}{1.97989pt}\pgfsys@curveto{-1.0934 8pt}{1.97989pt}{-1.97989pt}{1.09348pt}{-1.97989pt}{0.0pt}\pgfsys@curveto{-1.97 989pt}{-1.09348pt}{-1.09348pt}{-1.97989pt}{0.0pt}{-1.97989pt}\pgfsys@curveto{1 .09348pt}{-1.97989pt}{1.97989pt}{-1.09348pt}{1.97989pt}{0.0pt} \pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fill\pgfsys@invoke{ } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}{{{{}}\pgfsys@beginscope \pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{0.0pt}{0.0pt} \pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{ 1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1} \pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}\coloneqq-\frac{\partial_{{\bm{d}}_{p}}q( \tilde{{\bm{\theta}}}_{p};\tilde{\mathcal{B}})}{\partial^{2}_{{\bm{d}}_{p}}q( \tilde{{\bm{\theta}}}_{p};\tilde{\mathcal{B}})}\quad\text{instead of}\quad \underbracket{\tau_{p}}_{\leavevmode\hbox to3.96pt{\vbox to3.96pt{\pgfpicture \makeatletter\hbox{\hskip 1.97989pt\lower-1.97989pt\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to 0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{ tikz@color}{rgb}{1,1,1}\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{ rgb}{0.8671875,0.51953125,0.3203125}\pgfsys@color@rgb@fill{0.8671875}{0.519531 25}{0.3203125}\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{tikz@color}{rgb}{1,1,1} \definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{ 1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ }\pgfsys@color@gray@fill{1} \pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{ 0.8671875,0.51953125,0.3203125}\pgfsys@color@rgb@fill{0.8671875}{0.51953125}{0 .3203125}\pgfsys@invoke{ }\pgfsys@moveto{1.97989pt}{0.0pt}\pgfsys@curveto{1.97 989pt}{1.09348pt}{1.09348pt}{1.97989pt}{0.0pt}{1.97989pt}\pgfsys@curveto{-1.09 348pt}{1.97989pt}{-1.97989pt}{1.09348pt}{-1.97989pt}{0.0pt}\pgfsys@curveto{-1. 97989pt}{-1.09348pt}{-1.09348pt}{-1.97989pt}{0.0pt}{-1.97989pt}\pgfsys@curveto {1.09348pt}{-1.97989pt}{1.97989pt}{-1.09348pt}{1.97989pt}{0.0pt} \pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fill\pgfsys@invoke{ } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}{{{{}}\pgfsys@beginscope \pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{0.0pt}{0.0pt} \pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{ 1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1} \pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}=-\frac{\partial_{{\bm{d}}_{p}}q(\tilde{{\bm {\theta}}}_{p};\mathcal{B})}{\partial^{2}_{{\bm{d}}_{p}}q(\tilde{{\bm{\theta}} }_{p};\mathcal{B})}.$ (8) $$

For $\tilde{\mathcal{B}}=\mathcal{B}$, $(\tilde{{\bm{\theta}}}_{1},\ldots,\tilde{{\bm{\theta}}}_{K})$ is congruent with the original trajectory $({\bm{\theta}}_{1},\ldots,{\bm{\theta}}_{K})$ from the single-batch CG approach. If the two mini-batches
are different, the debiased trajectory will use updates into the directional minima of
$q(\,\cdot\,;\tilde{\mathcal{B}})$ instead of $q(\,\cdot\,;\mathcal{B})$.
Processes (i) and (ii) can either be run side by side in an alternating fashion
(offering more flexibility regarding e.g. the termination criterion at the cost of a
small memory overhead, details in Section A.2) or one after the other.

#### 4.2.2 Debiased Laplace approximation

Laplace approximation with K-FAC. We briefly explore another
popular curvature proxy: Kronecker-Factored Approximate Curvature (K-FAC), which is
commonly used both in optimization (Martens & Grosse, ; Martens et al., ; Eschenhagen et al., ) and uncertainty quantification (Ritter et al., ).
It is a block-diagonal approximation to the FIM
${\bm{F}}_{\mathcal{B}}\approx{\bm{K}}_{\mathcal{B}}\coloneqq\operatorname{
blockdiag}_{l=1,\ldots,L}({\bm{K}}_{\mathcal{B}}^{(l)})$,
where each block
${\bm{K}}_{\mathcal{B}}^{(l)}\coloneqq{\bm{A}}^{(l)}\otimes{\bm{B}}^{(l)}$ is approximated by the Kronecker product of two smaller
matrices ${\bm{A}}^{(l)}$ and ${\bm{B}}^{(l)}$. Sampling from the respective LA with covariance
${\bm{\Sigma}}_{\mathcal{B}}=N^{-1}({\bm{K}}_{\mathcal{B}}+\beta{\bm{I}})^{-1}$ can be
performed efficiently due to the specific structure of the K-FAC approximation. For
details, see Section A.3.2.

Debiased approach. For the debiased LA, we use two K-FAC approximations
${\bm{K}}_{\mathcal{B}}$ and ${\bm{K}}_{\tilde{\mathcal{B}}}$ computed on different mini-batches. Via
the eigendecomposition ${\bm{K}}_{\mathcal{B}}={\bm{U}}{\bm{\Lambda}}{\bm{U}}^{\top}$ with
${\bm{U}}=({\bm{u}}_{1},\ldots,{\bm{u}}_{P})$ and ${\bm{\Lambda}}=\operatorname{diag}(\lambda_{1},\ldots,\lambda_{P})$, we can re-write the covariance matrix as
${\bm{\Sigma}}_{\mathcal{B}}=N^{-1}({\bm{K}}_{\mathcal{B}}+\beta{\bm{I}})^{-1}=
N^{-1}{\bm{U}}({\bm{\Lambda}}+\beta{\bm{I}})^{-1}{\bm{U}}.$
For the debiased approach, we keep the eigenspace defined by ${\bm{K}}_{\mathcal{B}}$ but
recompute the directional curvatures based on ${\bm{K}}_{\tilde{\mathcal{B}}}$, i.e. we use

$$ $\displaystyle\tilde{{\bm{\Sigma}}}_{\mathcal{B}}\!=\!\frac{1}{N}{\bm{U}}\big{( }\operatorname{diag}(\tilde{\lambda}_{1},\dots,\tilde{\lambda}_{P})+\beta{\bm{ I}}\big{)}^{-1}{\bm{U}}^{\top}\;\;\text{with}\;\;\underbracket{\tilde{\lambda} _{p}}_{\leavevmode\hbox to3.96pt{\vbox to3.96pt{\pgfpicture\makeatletter\hbox{ \hskip 1.97989pt\lower-1.97989pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke { }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0} \pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ } \pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ } {{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{ tikz@color}{rgb}{1,1,1}\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{ rgb}{0.296875,0.4453125,0.69140625}\pgfsys@color@rgb@fill{0.296875}{0.4453125} {0.69140625}\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{tikz@color}{rgb}{1,1,1} \definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{ 1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ }\pgfsys@color@gray@fill{1} \pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{ 0.296875,0.4453125,0.69140625}\pgfsys@color@rgb@fill{0.296875}{0.4453125}{0.69 140625}\pgfsys@invoke{ }\pgfsys@moveto{1.97989pt}{0.0pt}\pgfsys@curveto{1.9798 9pt}{1.09348pt}{1.09348pt}{1.97989pt}{0.0pt}{1.97989pt}\pgfsys@curveto{-1.0934 8pt}{1.97989pt}{-1.97989pt}{1.09348pt}{-1.97989pt}{0.0pt}\pgfsys@curveto{-1.97 989pt}{-1.09348pt}{-1.09348pt}{-1.97989pt}{0.0pt}{-1.97989pt}\pgfsys@curveto{1 .09348pt}{-1.97989pt}{1.97989pt}{-1.09348pt}{1.97989pt}{0.0pt} \pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fill\pgfsys@invoke{ } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}{{{{}}\pgfsys@beginscope \pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{0.0pt}{0.0pt} \pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{ 1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1} \pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}\!=\!{\bm{u}}_{p}^{\top}{\bm{K}}_{\tilde{ \mathcal{B}}}{\bm{u}}_{p}\;\;\text{instead of}\;\;\underbracket{\lambda_{p}}_{ \leavevmode\hbox to3.96pt{\vbox to3.96pt{\pgfpicture\makeatletter\hbox{\hskip 1 .97989pt\lower-1.97989pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } \definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0} \pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ } \pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ } {{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{ tikz@color}{rgb}{1,1,1}\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{ rgb}{0.8671875,0.51953125,0.3203125}\pgfsys@color@rgb@fill{0.8671875}{0.519531 25}{0.3203125}\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{tikz@color}{rgb}{1,1,1} \definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{ 1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ }\pgfsys@color@gray@fill{1} \pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{ 0.8671875,0.51953125,0.3203125}\pgfsys@color@rgb@fill{0.8671875}{0.51953125}{0 .3203125}\pgfsys@invoke{ }\pgfsys@moveto{1.97989pt}{0.0pt}\pgfsys@curveto{1.97 989pt}{1.09348pt}{1.09348pt}{1.97989pt}{0.0pt}{1.97989pt}\pgfsys@curveto{-1.09 348pt}{1.97989pt}{-1.97989pt}{1.09348pt}{-1.97989pt}{0.0pt}\pgfsys@curveto{-1. 97989pt}{-1.09348pt}{-1.09348pt}{-1.97989pt}{0.0pt}{-1.97989pt}\pgfsys@curveto {1.09348pt}{-1.97989pt}{1.97989pt}{-1.09348pt}{1.97989pt}{0.0pt} \pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fill\pgfsys@invoke{ } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}{{{{}}\pgfsys@beginscope \pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{0.0pt}{0.0pt} \pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{ 1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1} \pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}\!=\!{\bm{u}}_{p}^{\top}{\bm{K}}_{\mathcal{B }}{\bm{u}}_{p}.$ (9) $$

#### 4.2.3 Computational cost of debiasing

Both debiasing techniques roughly double runtime compared to their single-batch
counterparts: Debiased CG performs one extra matrix-vector product with
${\bm{H}}_{\tilde{\mathcal{B}}}$ per CG iteration to compute the debiased update magnitude
(details in Section A.2). Debiased LA requires an additional K-FAC approximation ${\bm{K}}_{\tilde{\mathcal{B}}}$; all subsequent operations to compute the
debiased K-FAC can be carried out efficiently at Kronecker factor level
(details in Section A.3.3).
In Section 6, we thus use the debiased versions at half the batch size,
for a fair comparison. We will see that, at the resulting similar computational cost, the debiased versions clearly outperform the
single-batch alternatives.

## 5 Related work

We here briefly list other, related forms of bias correction that have been suggested
elsewhere.

A different two-batch approach. Other works have proposed to use different (not
necessarily disjoint) mini-batches for the gradient and the Hessian
(Martens, ; Byrd et al., ).
Benzing (, Sec. I.5) mentions the idea of using independent
mini-batches for the gradient and the Hessian to obtain an, in some sense, unbiased
estimate
$-{\bm{H}}_{\mathcal{B}}^{-1}{\bm{g}}_{\tilde{\mathcal{B}}}$
of the exact Newton step. This does, however, not resolve the biases described in this
paper. Via the eigendecomposition of the Hessian ${\bm{H}}_{\mathcal{B}}=\sum_{p=1}^{P}\lambda_{p}{\bm{u}}_{p}{\bm{u}}_{p}^{\top}$, we obtain
$-{\bm{H}}_{\mathcal{B}}^{-1}{\bm{g}}_{\tilde{\mathcal{B}}}\!=\!-\sum_{p=1}^{P}
\partial_{{\bm{u}}_{p}}q({\bm{\theta}}_{\star};\tilde{\mathcal{B}})(\partial^{
2}_{{\bm{u}}_{p}}q({\bm{\theta}}_{\star};\mathcal{B}))^{-1}\,{\bm{u}}_{p}.$
While the numerator yields an unbiased estimate of the directional slope (similar to a
blue dot in the upper panel of Figure 2), the bias in the denominator
remains since eigenvectors and directional curvatures are based on the same mini-batch
(as for the orange dots in the bottom panel of Figure 2).

Another debiasing approach. EKFAC (Eigenvalue-corrected Kronecker
Factorization) (George et al., ) corrects the eigenvalues of the K-FAC approximation (similar to Equation 9) which, provably, yields a more accurate
approximation of the FIM than K-FAC (in Frobenius norm). This correction, however, is
designed to resolve a different kind of bias that is specific to the K-FAC approximation
and does not address the biases described in this work.

Running averages. Other popular deep learning optimizers aggregate
curvature information over multiple steps via exponential moving averages (see e.g. (Martens & Grosse, )). This emulates larger mini-batch sizes and thus reduces
the curvature biases. However, when curvature evolves rapidly, obsolete curvature
estimates from past steps might slow down training. Aggregating more robust
debiased curvature estimates instead might allow for shorter moving average
windows and accelerate the optimization progress. We leave it to future work to explore
these interactions.

## 6 Experiments

In this section, we evaluate the effectiveness of the debiasing strategies from
Section 4.2. In Appendix B, we provide the
experimental details as well as additional empirical analyses. For instance, we show how
the curvature biases with K-FAC depend on the mini-batch size (see Section B.8),
how the biases evolve over the course of training (see Section B.9),
and that the curvature biases become more pronounced for deeper/wider models (see
Section B.10).

### 6.1 Debiased conjugate gradients

We compare the standard single-batch CG method to the debiased version (see
Section 4.2.1) on the fully trained All-CNN-C model without curvature damping.
For a fair comparison, the single-batch approach uses one mini-batch of size $1024$
while the debiased approach uses two mini-batches of size $512$, such that a similar
amount of data and runtime budget is used. Details in Section B.5.

Figure: Figure 5: Debiased CG is much more stable than the single-batch approach. We compare CG runs without curvature damping ($\delta=0$) with $K=30$ iterations for the fully trained All-CNN-C model on the CIFAR-100 dataset in terms of training/test loss/accuracy at similar computational cost: The single-batch approach (shown as ) uses one mini-batch of size $1024$ while the debiased approach (shown as ) uses two mini-batches of size $512$ each. Both approaches use the GGN curvature proxy and are run $5$ times on different mini-batches. The markers ◆ and ◆ are placed at peak performance. While the single-batch runs diverge quickly, the debiased CG runs are stable.
Refer to caption: x5.png

Results & discussion.
All CG runs in Figure 5 achieve a significant improvement in all four performance
metrics. The most striking difference between the two approaches is their stability: The
single-batch runs quickly reach peak performance and then diverge. In contrast, although
the steps tend to be larger (see Figure 4), the debiased CG runs are much more stable (without using any curvature damping).
This suggests that the reason for the divergence in the single-batch approach is
not the missing damping but the misinformed update magnitudes.
The peak performance is slightly better for the single-batch runs which can be
attributed to its more informative search directions (they were computed using
double the data). The peak performance of the debiased runs could likely be
improved (at the same computational cost) by using a larger batch size for the
directions and a smaller one for the update magnitudes (as the former seem harder to
estimate, see Section 3.2).

### 6.2 Debiased Laplace approximation

Here, we use a fully trained All-CNN-C model on CIFAR-10 data and compare (i) the
vanilla model without LA, (ii) the single-batch K-FAC LA approach, (iii) the debiased
version (see Section 4.2.2), and (iv) the full-batch approach (where we compute
K-FAC on the entire training set) in terms of accuracy, NLL and ECE. Again, we apply the
debiased approach at half the batch size of the single-batch approach for a fair
comparison. We use prior precisions between $10^{-4}$ and $10$.
Section B.6 contains the experimental details and additional results on
the training and OOD data.

Figure: Figure 6: Debiased LA mimics the full-batch LA very well. We compare LAs for the fully trained All-CNN-C model on CIFAR-10 in terms of accuracy, negative log likelihood loss (NLL) and expected calibration error (ECE) on the CIFAR-10 test set. For each mini-batch size (lighter color indicating smaller batch size), we draw $5$ mini-batches and report the mean performance as dot and min/max as vertical line. We also report the performance of the vanilla model without LA (shown as ) and the full-batch approach based on ${\bm{K}}_{\mathcal{D}}$ (shown as ✚). In contrast to the single-batch approach, the debiased version mimics the behavior of the full-batch approach very well over the entire range of prior precisions.
Refer to caption: x6.png

Results & discussion. Figure 6 shows the results. If the prior precision
is low (i.e. the LA relies mainly on the curvature information without the regularizing
diagonal term), the single-batch version acts erratically due to the deformed curvature
model—its performance drops drastically. The single-batch approach is also more
sensitive to the choice of prior precision (in fact, it suggests a much larger prior
precision than the full-batch approach). In contrast, the debiased approach achieves
good performance over a wider range of prior precisions and mimics the full-batch
approach ($N\!=\!$40000$$) very well despite using only a tiny fraction
of the data.

Summary of the experimental results. The use of mini-batch quadratics is a
simple way to keep the costs of second-order optimization and uncertainty quantification
manageable. The resulting biases, however, severely degrade their value, requiring large
mini-batches or algorithmic add-ons. Our experiments suggest that
even simple debiasing strategies can largely mitigate this issue.

## 7 Conclusion

Our main takeaway is a general principle: Quadratic approximations to the
training loss computed on mini-batches of the training data provide a
distorted representation of the true underlying loss landscape. In particular,
along the directions of large curvature, the mini-batch quadratics tend to strongly
overestimate the curvature of the true loss.
Our theoretical analysis shows that these biases can be traced back to the misalignment
of the curvature matrices’ eigenspaces.
These insights are highly relevant for applications: As we demonstrated empirically, the
biases in the directional slope and curvature lead to severely misinformed updates in
stochastic second-order optimizers, and cause unreliable uncertainty estimates with
Laplace approximations.
We also proposed simple two-batch strategies to mitigate these biases. Our experiments
demonstrate their superiority over the single-batch approaches in terms of stability and
quality at similar computational costs.
Our findings reveal a design prerequisite for building better stochastic curvature-based
methods, which should be generally considered, and further developed, for all methods
using such curvature evaluations.

## Supplemental material

Below, we provide additional details on the mathematical derivations, describe the
experimental setup and present additional results.

[sections]
\printcontents[sections]l1

## Appendix A Mathematical details

### A.1 Directional derivatives of a quadratic

We claim in Section 2.1 that a cut $r$ through the
quadratic $q(\,\cdot\,;\mathcal{B})$ from ${\bm{\theta}}_{\bullet}\in\mathbb{R}^{P}$
along the normalized direction ${\bm{d}}$ can be written as

$$ $r(\tau)\coloneqq q({\bm{\theta}}_{\bullet}+\tau{\bm{d}};\mathcal{B})=\frac{1}{ 2}\tau^{2}{\bm{d}}^{\top}\nabla^{2}q({\bm{\theta}}_{\bullet};\mathcal{B})\,{ \bm{d}}+\tau{\bm{d}}^{\top}\nabla q({\bm{\theta}}_{\bullet};\mathcal{B})+\text {const}.$ (10) $$

Proof for Equation 10. Here, we provide the derivation for
Equation 10. Let ${\bm{\theta}}_{\bullet}\in\mathbb{R}^{P}$ be a point in
parameter space and ${\bm{d}}\in\mathbb{R}^{P}$ a normalized direction, i.e. $\|{\bm{d}}\|=1$. We consider the quadratic approximation $q({\bm{\theta}};\mathcal{B})$ around
${\bm{\theta}}_{0}$ and evaluate it along the cut ${\bm{\theta}}_{\bullet}+\tau{\bm{d}}$ for $\tau\in\mathbb{R}$. We assume that the Hessian (or its approximation) ${\bm{H}}_{\mathcal{B}}$ is
symmetric and obtain

$$ $\displaystyle r(\tau)\coloneqq$ $\displaystyle\;q({\bm{\theta}}_{\bullet}+\tau{\bm{d}};\mathcal{B})$ $\displaystyle=$ $\displaystyle\;\frac{1}{2}({\bm{\theta}}_{\bullet}+\tau{\bm{d}}-{\bm{\theta}}_ {0})^{\top}{\bm{H}}_{\mathcal{B}}({\bm{\theta}}_{\bullet}+\tau{\bm{d}}-{\bm{ \theta}}_{0})+({\bm{\theta}}_{\bullet}+\tau{\bm{d}}-{\bm{\theta}}_{0})^{\top}{ \bm{g}}_{\mathcal{B}}+c_{\mathcal{B}}$ $\displaystyle=$ $\displaystyle\;\frac{1}{2}\tau^{2}{\bm{d}}^{\top}{\bm{H}}_{\mathcal{B}}{\bm{d} }+\tau{\bm{d}}^{\top}{\bm{H}}_{\mathcal{B}}({\bm{\theta}}_{\bullet}-{\bm{ \theta}}_{0})+\frac{1}{2}({\bm{\theta}}_{\bullet}-{\bm{\theta}}_{0})^{\top}{ \bm{H}}_{\mathcal{B}}({\bm{\theta}}_{\bullet}-{\bm{\theta}}_{0})$ $\displaystyle+\tau{\bm{d}}^{\top}{\bm{g}}_{\mathcal{B}}+({\bm{\theta}}_{ \bullet}-{\bm{\theta}}_{0})^{\top}{\bm{g}}_{\mathcal{B}}+c_{\mathcal{B}}$ $\displaystyle=$ $\displaystyle\;\frac{1}{2}\tau^{2}{\bm{d}}^{\top}{\bm{H}}_{\mathcal{B}}{\bm{d} }+\tau{\bm{d}}^{\top}({\bm{H}}_{\mathcal{B}}({\bm{\theta}}_{\bullet}-{\bm{ \theta}}_{0})+{\bm{g}}_{\mathcal{B}})+\text{const}.$ $$

Since
$\nabla q({\bm{\theta}}_{\bullet};\mathcal{B})={\bm{H}}_{\mathcal{B}}({\bm{
\theta}}_{\bullet}-{\bm{\theta}}_{0})+{\bm{g}}_{\mathcal{B}}$
and
$\nabla^{2}q({\bm{\theta}}_{\bullet};\mathcal{B})\equiv{\bm{H}}_{\mathcal{B}},$
we arrive at Equation 10. ∎

Proof for Equation 5. Next, we show that
the average directional slope/curvature over all mini-batches in the training set
coincides with the directional slope/curvature of the full-batch quadratic. Let’s assume
that all $M$ mini-batches $\{\mathcal{B}_{m^{\prime}}\}_{m^{\prime}=1}^{M}$ are
disjoint, have the same size $|\mathcal{B}_{1}|$ and that their union is the
training set, i.e.

$$ $|\mathcal{B}_{m^{\prime}}|=|\mathcal{B}_{1}|\;\;\forall m^{\prime}\in\{1, \ldots,M\}\quad\text{and}\quad\bigcup_{m^{\prime}=1}^{M}\mathcal{B}_{m^{\prime }}=\mathcal{D}.$ (11) $$

This implies $M|\mathcal{B}_{1}|=|\mathcal{D}|$. It
holds

$$ $\displaystyle\frac{1}{M}\sum_{m^{\prime}=1}^{M}\underbracket{\partial_{{\bm{u} }_{p}}q({\bm{\theta}}_{\star};\mathcal{B}_{m^{\prime}})}_{\text{one~{}} \leavevmode\hbox to3.96pt{\vbox to3.96pt{\pgfpicture\makeatletter\hbox{\hskip 1 .97989pt\lower-1.97989pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } \definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0} \pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ } \pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ } {{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{ tikz@color}{rgb}{1,1,1}\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{ rgb}{0.8671875,0.51953125,0.3203125}\pgfsys@color@rgb@fill{0.8671875}{0.519531 25}{0.3203125}\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{tikz@color}{rgb}{1,1,1} \definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{ 1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ }\pgfsys@color@gray@fill{1} \pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{ 0.8671875,0.51953125,0.3203125}\pgfsys@color@rgb@fill{0.8671875}{0.51953125}{0 .3203125}\pgfsys@invoke{ }\pgfsys@moveto{1.97989pt}{0.0pt}\pgfsys@curveto{1.97 989pt}{1.09348pt}{1.09348pt}{1.97989pt}{0.0pt}{1.97989pt}\pgfsys@curveto{-1.09 348pt}{1.97989pt}{-1.97989pt}{1.09348pt}{-1.97989pt}{0.0pt}\pgfsys@curveto{-1. 97989pt}{-1.09348pt}{-1.09348pt}{-1.97989pt}{0.0pt}{-1.97989pt}\pgfsys@curveto {1.09348pt}{-1.97989pt}{1.97989pt}{-1.09348pt}{1.97989pt}{0.0pt} \pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fill\pgfsys@invoke{ } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}{{{{}}\pgfsys@beginscope \pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{0.0pt}{0.0pt} \pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{ 1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1} \pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}\text{~{}and many~{}}\leavevmode\hbox to3.96 pt{\vbox to3.96pt{\pgfpicture\makeatletter\hbox{\hskip 1.97989pt\lower-1.97989 pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor }{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt} \pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{ tikz@color}{rgb}{1,1,1}\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{ rgb}{0.296875,0.4453125,0.69140625}\pgfsys@color@rgb@fill{0.296875}{0.4453125} {0.69140625}\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{tikz@color}{rgb}{1,1,1} \definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{ 1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ }\pgfsys@color@gray@fill{1} \pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{ 0.296875,0.4453125,0.69140625}\pgfsys@color@rgb@fill{0.296875}{0.4453125}{0.69 140625}\pgfsys@invoke{ }\pgfsys@moveto{1.97989pt}{0.0pt}\pgfsys@curveto{1.9798 9pt}{1.09348pt}{1.09348pt}{1.97989pt}{0.0pt}{1.97989pt}\pgfsys@curveto{-1.0934 8pt}{1.97989pt}{-1.97989pt}{1.09348pt}{-1.97989pt}{0.0pt}\pgfsys@curveto{-1.97 989pt}{-1.09348pt}{-1.09348pt}{-1.97989pt}{0.0pt}{-1.97989pt}\pgfsys@curveto{1 .09348pt}{-1.97989pt}{1.97989pt}{-1.09348pt}{1.97989pt}{0.0pt} \pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fill\pgfsys@invoke{ } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}{{{{}}\pgfsys@beginscope \pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{0.0pt}{0.0pt} \pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{ 1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1} \pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}$ $\displaystyle=\frac{1}{M}\sum_{m^{\prime}=1}^{M}{\bm{u}}_{p}^{\top}\nabla q({ \bm{\theta}}_{\star};\mathcal{B}_{m^{\prime}})\quad\text{ with $\nabla q({\bm{\theta}}_{\star};\mathcal{B}_{m^{\prime}})={\bm{g}}_{\mathcal{B }_{m^{\prime}}}$ since ${\bm{\theta}}_{0}\leftarrow{\bm{\theta}}_{\star}$ }$ $\displaystyle={\bm{u}}_{p}^{\top}\frac{1}{M}\sum_{m^{\prime}=1}^{M}\nabla \mathcal{L}_{\text{reg}}({\bm{\theta}}_{\star};\mathcal{B}_{m^{\prime}})$ $\displaystyle={\bm{u}}_{p}^{\top}\left(\frac{1}{M}M\,\nabla r({\bm{\theta}}_{ \star})+\frac{1}{M}\sum_{m^{\prime}=1}^{M}\nabla\mathcal{L}({\bm{\theta}}_{ \star};\mathcal{B}_{m^{\prime}})\right)$ $\displaystyle={\bm{u}}_{p}^{\top}\left(\nabla r({\bm{\theta}}_{\star})+\frac{1 }{M}\sum_{m^{\prime}=1}^{M}\frac{1}{|\mathcal{B}_{m^{\prime}}|}\sum_{n\in \mathcal{B}_{m^{\prime}}}\nabla\ell(f_{{\bm{\theta}}_{\star}}({\bm{x}}_{n}),{ \bm{y}}_{n})\right)$ $\displaystyle\overset{\text{(\ref{eq:assumtions_minibatches_trainingdata})}}{= }{\bm{u}}_{p}^{\top}\left(\nabla r({\bm{\theta}}_{\star})+\frac{1}{M|\mathcal{ B}_{1}|}\sum_{m^{\prime}=1}^{M}\sum_{n\in\mathcal{B}_{m^{\prime}}}\nabla\ell(f _{{\bm{\theta}}_{\star}}({\bm{x}}_{n}),{\bm{y}}_{n})\right)$ $\displaystyle={\bm{u}}_{p}^{\top}\nabla\mathcal{L}_{\text{reg}}({\bm{\theta}}_ {\star};\mathcal{D})$ $\displaystyle=\underbracket{\partial_{{\bm{u}}_{p}}q({\bm{\theta}}_{\star}; \mathcal{D})}_{\text{{\color[rgb]{0.33203125,0.66015625,0.40625}\definecolor[ named]{pgfstrokecolor}{rgb}{0.33203125,0.66015625,0.40625}\char 58}}}\!.$ $$

As the mini-batch curvature $\nabla^{2}\mathcal{L}({\bm{\theta}}_{\star};\mathcal{B}_{m^{\prime}})$ is also an
average over the samples in the mini-batch (this applies to both the actual
Hessian and its GGN approximation), the same argument holds for the associated
directional curvatures. For K-FAC, the derivation above does not hold as $(1/2)({\bm{K}}_{\mathcal{B}}+{\bm{K}}_{\tilde{\mathcal{B}}})\neq{\bm{K}}_{
\mathcal{B}\cup\tilde{\mathcal{B}}}$.
∎

### A.2 The method of conjugate gradients ( CG )

Using CG for minimizing a quadratic.
The argmin of a quadratic $q(\,\cdot\,;\mathcal{B})$ is given by ${\bm{\theta}}_{0}-{\bm{H}}_{\mathcal{B}}^{-1}{\bm{g}}_{\mathcal{B}}$ (assuming that ${\bm{H}}_{\mathcal{B}}$ is
symmetric and positive definite), see Section 2.2. We can
use the method of conjugate gradients (see Algorithm 1) for computing the Newton step
(or an approximation thereof) by setting ${\bm{A}}\leftarrow{\bm{H}}_{\mathcal{B}}$ and ${\bm{b}}\leftarrow-{\bm{g}}_{\mathcal{B}}$.

Figure: Algorithm 1 Method of conjugate gradients (CG), based on (Nocedal & Wright, , Alg. 5.2)

Properties of CG & geometric interpretations. In the following, we provide
some important properties and a geometric interpretation of the quantities involved in
the CG method.

- •
Residual ${\bm{r}}_{p}$. Let ${\bm{x}}_{p}\coloneqq{\bm{\theta}}_{p}-{\bm{\theta}}_{0}$. The residual
${\bm{r}}_{p}$ can be written as
${\bm{r}}_{p}={\bm{A}}{\bm{x}}_{p}-b={\bm{H}}_{\mathcal{B}}({\bm{\theta}}_{p}-{
\bm{\theta}}_{0})+{\bm{g}}_{\mathcal{B}}=\nabla q({\bm{\theta}}_{p};\mathcal{B})$, i.e. it coincides with the gradient of the quadratic at ${\bm{\theta}}_{p}$.
- •
Update magnitude $\alpha_{p}$. Consider a cut through the quadratic from
${\bm{\theta}}_{p}$ into the direction ${\bm{s}}_{p}$, i.e. $r(\tau)=q({\bm{\theta}}_{p}+\tau{\bm{s}}_{p};\mathcal{B})$. Minimizing this 1D quadratic requires its first derivative to
vanish. It holds (see Equation 10)
$\displaystyle r^{\prime}(\tau)=0\quad\Leftrightarrow\quad$
$\displaystyle\tau{\bm{s}}_{p}^{\top}\nabla^{2}q({\bm{\theta}}_{p};\mathcal{B})
\,{\bm{s}}_{p}+{\bm{s}}_{p}^{\top}\nabla q({\bm{\theta}}_{p};\mathcal{B})=0$
$\displaystyle\Leftrightarrow\quad$
$\displaystyle\tau=-\frac{{\bm{s}}_{p}^{\top}\nabla q({\bm{\theta}}_{p};
\mathcal{B})}{{\bm{s}}_{p}^{\top}\nabla^{2}q({\bm{\theta}}_{p};\mathcal{B})\,{
\bm{d}}_{p}}=-\frac{{\bm{s}}_{p}^{\top}{\bm{r}}_{p}}{{\bm{s}}_{p}^{\top}{\bm{A
}}\,{\bm{s}}_{p}}=\frac{{\bm{r}}_{p}^{\top}{\bm{r}}_{p}}{{\bm{s}}_{p}^{\top}{
\bm{A}}{\bm{s}}_{p}}=\alpha_{p},$
where the equality $-{\bm{s}}_{p}^{\top}{\bm{r}}_{p}={\bm{r}}_{p}^{\top}{\bm{r}}_{p}$ is due to Equation (5.14a)
and Theorem 5.2 in (Nocedal & Wright, ). So, the update magnitude $\alpha_{p}$
is chosen such that it minimizes the quadratic along the direction ${\bm{s}}_{p}$. Note that
the update magnitude can also be written as a ratio of the negative directional slope
and directional curvature at ${\bm{\theta}}_{p}$, i.e. a 1D directional Newton step. Let ${\bm{d}}_{p}\coloneqq{\bm{s}}_{p}/\|{\bm{s}}_{p}\|$ denote the normalized search direction. It
holds
${\bm{x}}_{p+1}={\bm{x}}_{p}+\alpha_{p}{\bm{s}}_{p}={\bm{x}}_{p}-\frac{{\bm{s}}
_{p}^{\top}{\bm{r}}_{p}}{{\bm{s}}_{p}^{\top}{\bm{A}}\,{\bm{s}}_{p}}{\bm{s}}_{p
}={\bm{x}}_{p}-\frac{{\bm{d}}_{p}^{\top}{\bm{r}}_{p}}{{\bm{d}}_{p}^{\top}{\bm{
A}}\,{\bm{d}}_{p}}{\bm{d}}_{p}={\bm{x}}_{p}\underbracket{-\frac{\partial_{{\bm
{d}}_{p}}q({\bm{\theta}}_{d};\mathcal{B})}{\partial^{2}_{{\bm{d}}_{p}}q({\bm{
\theta}}_{d};\mathcal{B})}}_{\displaystyle\eqqcolon\tau_{p}}{\bm{d}}_{p}$
i.e. $\tau_{p}=\alpha_{p}\|{\bm{s}}_{p}\|$. Via the shift ${\bm{\theta}}_{p}={\bm{\theta}}_{0}+{\bm{x}}_{p}$, we arrive at Equation 3.
- •
Search direction ${\bm{s}}_{p}$. CG constructs the search directions to be
conjugate, i.e. ${\bm{s}}_{p+1}^{\top}{\bm{A}}\,{\bm{s}}_{i}=0$ for all $i\leq p$. Note that this
property also applies to the normalized search directions.

Efficient implementation of the debiased CG approach. For the debiased CG version, we need to re-evaluate the update magnitudes $\tilde{\tau}_{p}$ for a given set
of search directions $\{{\bm{d}}_{1},\ldots{\bm{d}}_{P}\}$ on a second mini-batch
$\tilde{\mathcal{B}}$ (see Equation 8), i.e.

$$ $\tilde{\tau}_{p}=-\frac{\partial_{{\bm{d}}_{p}}q(\tilde{{\bm{\theta}}}_{p}; \tilde{\mathcal{B}})}{\partial^{2}_{{\bm{d}}_{p}}q(\tilde{{\bm{\theta}}}_{p}; \tilde{\mathcal{B}})}=-\frac{{\bm{d}}_{p}^{\top}\nabla q(\tilde{{\bm{\theta}}} _{p};\tilde{\mathcal{B}})}{{\bm{d}}_{p}^{\top}\nabla^{2}q(\tilde{{\bm{\theta}} }_{p};\tilde{\mathcal{B}})\,{\bm{d}}_{p}}=-\frac{{\bm{d}}_{p}^{\top}({\bm{H}}_ {\tilde{\mathcal{B}}}(\tilde{{\bm{\theta}}}_{p}-{\bm{\theta}}_{0})+{\bm{g}}_{ \tilde{\mathcal{B}}})}{{\bm{d}}_{p}^{\top}{\bm{H}}_{\tilde{\mathcal{B}}}\,{\bm {d}}_{p}}$ $$

Implemented naively, this requires two matrix-vector products—one for the
numerator and one for the denominator. However, we can use a recursive formula for the
numerator:

$$ $\displaystyle\nabla q(\tilde{{\bm{\theta}}}_{p};\tilde{\mathcal{B}})$ $\displaystyle={\bm{H}}_{\tilde{\mathcal{B}}}(\tilde{{\bm{\theta}}}_{p}-{\bm{ \theta}}_{0})+{\bm{g}}_{\tilde{\mathcal{B}}}$ $\displaystyle={\bm{H}}_{\tilde{\mathcal{B}}}(\tilde{{\bm{\theta}}}_{p-1}+ \tilde{\tau}_{p-1}{\bm{d}}_{p-1}-{\bm{\theta}}_{0})+{\bm{g}}_{\tilde{\mathcal{ B}}}$ $\displaystyle={\bm{H}}_{\tilde{\mathcal{B}}}(\tilde{{\bm{\theta}}}_{p-1}-{\bm{ \theta}}_{0})+{\bm{g}}_{\tilde{\mathcal{B}}}+\tilde{\tau}_{p-1}{\bm{H}}_{ \tilde{\mathcal{B}}}\,{\bm{d}}_{p-1}$ $\displaystyle=\nabla q(\tilde{{\bm{\theta}}}_{p-1};\tilde{\mathcal{B}})+\tilde {\tau}_{p-1}{\bm{H}}_{\tilde{\mathcal{B}}}\,{\bm{d}}_{p-1}.$ (12) $$

So, if we store the gradient from the previous iteration $\nabla q(\tilde{{\bm{\theta}}}_{p-1};\tilde{\mathcal{B}})$ and the Hessian vector product
with the previous direction ${\bm{H}}_{\tilde{\mathcal{B}}}\,{\bm{d}}_{p-1}$, the current
gradient can be computed without an additional matrix-vector product. At
iteration $p$, we thus (i) compute the gradient $\nabla q(\tilde{{\bm{\theta}}}_{p};\tilde{\mathcal{B}})$ recursively from the cached vectors $\nabla q(\tilde{{\bm{\theta}}}_{p-1};\tilde{\mathcal{B}})$ and ${\bm{H}}_{\tilde{\mathcal{B}}}\,{\bm{d}}_{p-1}$ via Equation 12 (for $p=0$, we have $\nabla q(\tilde{{\bm{\theta}}}_{0};\tilde{\mathcal{B}})={\bm{g}}_{\tilde{
\mathcal{B}}}$), (ii) compute
the Hessian-vector product with the current direction ${\bm{H}}_{\tilde{\mathcal{B}}}\,{\bm{d}}_{p}$, (iii) store both these vectors and (iv) compute the update magnitude
$\tilde{\tau}_{p}$ (both the numerator and the denominator only require a simple dot
product of two pre-computed vectors).

### A.3 Laplace approximation for neural networks

#### A.3.1 Derivation of the Laplace approximation for neural networks

Preliminaries.
The softmax function $\text{softmax}:\mathbb{R}^{C}\to\mathbb{R}^{C}$ is defined as

$$ $\text{softmax}({\bm{z}})\coloneqq\left(\frac{\exp(z_{1})}{\sum_{c^{\prime}=1}^ {C}\exp(z_{c^{\prime}})},\ldots,\frac{\exp(z_{C})}{\sum_{c^{\prime}=1}^{C}\exp (z_{c^{\prime}})}\right).$ $$

It maps an arbitrary vector ${\bm{z}}\in\mathbb{R}^{C}$ to a vector whose entries are
non-negative and sum up to one. So, the output of the softmax function can be
interpreted as a probability distribution over $C$ classes. With this, the
cross-entropy loss for a single datum $({\bm{x}},{\bm{y}})$ is given by

$$ $\ell(f_{{\bm{\theta}}}({\bm{x}}),{\bm{y}})\coloneqq-\sum_{c=1}^{C}{\bm{y}}_{c} \cdot\log(\text{softmax}(f_{{\bm{\theta}}}({\bm{x}}))_{c}).$ (13) $$

Here, we assume that ${\bm{y}}\in\{0,1\}^{C}$ is a one-hot encoded vector
representing the true class label. So, if $c_{\star}\in\{1,\ldots,C\}$ is the
correct class (i.e. ${\bm{y}}_{c_{\star}}=1$), the cross-entropy loss is given by the negative
logarithm of the probability the network assigns to this class
$\ell(f_{{\bm{\theta}}}({\bm{x}}),{\bm{y}})=-\log(\text{softmax}(f_{{\bm{\theta
}}}({\bm{x}}))_{c_{\star}}).$
Finally, let

$$ ${\operatorname{Cat}\mathopen{}\left({\bm{y}};{\bm{p}}\right)}\coloneqq\prod_{c =1}^{C}{\bm{p}}_{c}^{{\bm{y}}_{c}}$ (14) $$

denote the probability mass function of the categorical distribution, where ${\bm{p}}\in\mathbb{R}^{C}$ is a vector of probabilities (i.e. ${\bm{p}}_{c}\geq 0$ and $\sum_{c}{\bm{p}}_{c}=1$), and ${\bm{y}}\in\{0,1\}^{C}$ is a one-hot encoded vector representing a class
label.

Probabilistic interpretation of the regularized loss. Recall from
Equation 1 that the regularized loss function is given by

$$ $\mathcal{L}_{\text{reg}}({\bm{\theta}};\mathcal{D})=\mathcal{L}({\bm{\theta}}; \mathcal{D})+r({\bm{\theta}})\quad\text{with}\quad\mathcal{L}({\bm{\theta}}; \mathcal{D})=\frac{1}{N}\sum_{n\in\mathcal{D}}\ell(f_{{\bm{\theta}}}({\bm{x}}_ {n}),{\bm{y}}_{n}).$ $$

We assume a classification problem that uses the cross-entropy loss (see
Equation 13) and an $\ell^{2}$ regularizer $r({\bm{\theta}})=\nicefrac{{\beta}}{{2}}\,\|{\bm{\theta}}\|_{2}^{2}$ with parameter $\beta\in\mathbb{R}_{>0}$. We
use one-hot encoded labels ${\bm{y}}_{n}\in\{0,1\}^{C}$ (with ${\bm{y}}_{nc}$, we denote
the $c$-th entry of ${\bm{y}}_{n}$) and obtain

$$ $\displaystyle N\cdot\mathcal{L}_{\text{reg}}({\bm{\theta}};\mathcal{D})$ $\displaystyle=\sum_{n\in\mathcal{D}}\ell(f_{{\bm{\theta}}}({\bm{x}}_{n}),{\bm{ y}}_{n})+\frac{N\beta}{2}\|{\bm{\theta}}\|_{2}^{2}$ $\displaystyle{=}-\sum_{n\in\mathcal{D}}\sum_{c=1}^{C}{\bm{y}}_{nc}\cdot\log( \text{softmax}(f_{{\bm{\theta}}}({\bm{x}}_{n}))_{c})+\frac{N\beta}{2}\|{\bm{ \theta}}\|_{2}^{2}$ $\displaystyle{=}-\sum_{n\in\mathcal{D}}\log\big{(}{\operatorname{Cat}\mathopen {}\left({\bm{y}}_{n};\text{softmax}(f_{{\bm{\theta}}}({\bm{x}}_{n}))\right)} \big{)}-\left(-\frac{1}{2}{\bm{\theta}}^{\top}(N\beta\cdot{\bm{I}})\,{\bm{ \theta}}\right)$ $\displaystyle=-\log\Bigg{(}\underbrace{\prod_{n\in\mathcal{D}}{\operatorname{ Cat}\mathopen{}\left({\bm{y}}_{n};\text{softmax}(f_{{\bm{\theta}}}({\bm{x}}_{n }))\right)}}_{\displaystyle\text{likelihood}\;p({\mathbb{D}}\mid{\bm{\theta}}) }\Bigg{)}-\log\Bigg{(}\underbrace{{\operatorname{\mathcal{N}}\mathopen{}\left( \theta;{\bm{0}},\frac{1}{N\beta}{\bm{I}}\right)}}_{\displaystyle\text{prior}\; p({\bm{\theta}})}\Bigg{)}-Z,$ $$

where
$Z\coloneqq\nicefrac{{P}}{{2}}\log(\nicefrac{{2\pi}}{{N\beta}})$
absorbs the normalization constant of the Gaussian prior. The cross entropy loss $\mathcal{L}$
for the training set is thus connected to the negative log categorical likelihood and
the regularizer can be seen as a negative log Gaussian prior over the parameters. Note
that a similar derivation is possible for other loss functions as well, e.g. the MSE loss
(which is equivalent to a negative log Gaussian likelihood).

The derivation above shows that the (rescaled) regularized loss function can be
interpreted as the negative unnormalized log posterior of a Bayesian model

$$ $N\cdot\mathcal{L}_{\text{reg}}({\bm{\theta}};\mathcal{D})\overset{\text{c}}{=} -\log p({\mathbb{D}}\mid{\bm{\theta}})-\log p({\bm{\theta}})\overset{\text{c}} {=}-\log p({\bm{\theta}}\mid{\mathbb{D}})$ (15) $$

with Gaussian prior and categorical likelihood. With $\overset{\text{c}}{=}$, we denote equality up to an
additive constant.

Training as MAP estimation. Equation 15 allows
re-interpreting the training procedure of a neural network as a maximum a posteriori
(MAP) estimation problem since minimizing the regularized loss

$$ $\underbrace{\operatorname*{arg\,min}_{{\bm{\theta}}\in\mathbb{R}^{P}}\mathcal{ L}_{\text{reg}}({\bm{\theta}},\mathcal{D})}_{\displaystyle\phantom{{\bm{\theta }}_{\star}}={\bm{\theta}}_{\star}}=\operatorname*{arg\,min}_{{\bm{\theta}}\in \mathbb{R}^{P}}N\cdot\mathcal{L}_{\text{reg}}({\bm{\theta}},\mathcal{D}) \overset{\text{(\ref{eq:Lossreg_as_log_posterior})}}{=}\operatorname*{arg\,max }_{{\bm{\theta}}\in\mathbb{R}^{P}}\log p({\bm{\theta}}\mid{\mathbb{D}})= \underbrace{\operatorname*{arg\,max}_{{\bm{\theta}}\in\mathbb{R}^{P}}p({\bm{ \theta}}\mid{\mathbb{D}})}_{\displaystyle\phantom{{\bm{\theta}}_{\star}} \eqqcolon{\bm{\theta}}_{\star}}$ $$

is equivalent to maximizing the posterior $p({\bm{\theta}}\mid{\mathbb{D}})$.

Laplace approximation. The idea of the Laplace approximation is to approximate
the posterior distribution $p({\bm{\theta}}\mid{\mathbb{D}})\approx{\operatorname{\mathcal{N}}\mathopen{}
\left({\bm{\theta}};{\bm{\theta}}_{\star},{\bm{\Sigma}}_{\mathcal{D}}\right)}$ with a Gaussian at the mode
${\bm{\theta}}_{\star}$ of the posterior, i.e. after training the network. For this, we approximate
the log posterior by a second-order Taylor expansion around the mode ${\bm{\theta}}_{0}\leftarrow{\bm{\theta}}_{\star}$, i.e.

$$ $\log p({\bm{\theta}}\mid{\mathbb{D}})\overset{\text{c}}{=}-N\cdot\mathcal{L}_{ \text{reg}}({\bm{\theta}};\mathcal{D})\overset{(\ref{eq:fullbatch_quadratic})} {\approx}-N\cdot q({\bm{\theta}};\mathcal{D})\overset{\text{c}}{=}-\frac{1}{2} ({\bm{\theta}}-{\bm{\theta}}_{\star})^{\top}(N\cdot{\bm{H}}_{\mathcal{D}})({ \bm{\theta}}-{\bm{\theta}}_{\star}),$ (16) $$

where we assumed that ${\bm{\theta}}_{\star}$ is a (local) minimum of the regularized loss function
(i.e. ${\bm{g}}_{\mathcal{D}}=\nabla\mathcal{L}_{\text{reg}}({\bm{\theta}}_{\star};
\mathcal{D})=0$) such that the
linear term $({\bm{\theta}}-{\bm{\theta}}_{0})^{\top}{\bm{g}}_{\mathcal{D}}$ in the quadratic approximation
vanishes. The additive constants we did not state explicitly in
Equation 16 turn into some multiplicative factor (denoted by
$Z^{-1}$) when taking the exponential

$$ $p({\bm{\theta}}\mid{\mathbb{D}})\approx\frac{1}{Z}\exp\left(-\frac{1}{2}({\bm{ \theta}}-{\bm{\theta}}_{\star})^{\top}(N\cdot{\bm{H}}_{\mathcal{D}})({\bm{ \theta}}-{\bm{\theta}}_{\star})\right).$ $$

This immediately identifies $Z$ as the normalization constant of the Gaussian and we
obtain the Laplace approximation

$$ $p({\bm{\theta}}\mid{\mathbb{D}})\approx{\operatorname{\mathcal{N}}\mathopen{} \left({\bm{\theta}};{\bm{\theta}}_{\star},{\bm{\Sigma}}_{\mathcal{D}}\right)} \quad\text{with}\quad{\bm{\Sigma}}_{\mathcal{D}}\coloneqq(N\cdot{\bm{H}}_{ \mathcal{D}})^{-1}=\frac{1}{N}{\bm{H}}_{\mathcal{D}}^{-1}.$ (17) $$

Mini-batch version of the Laplace approximation. In order to reduce the
computational cost of the Laplace approximation, we can replace the full-batch quadratic
$q({\bm{\theta}};\mathcal{D})$ in Equation 16 by a
mini-batch quadratic $q({\bm{\theta}};\mathcal{B})$, i.e. we obtain
${\bm{\Sigma}}_{\mathcal{B}}=N^{-1}{\bm{H}}_{\mathcal{B}}^{-1}$.

Predictive uncertainty via the Laplace approximation. Ultimately, we want to
use the Laplace approximation to equip the prediction for an unknown test input
${\bm{x}}_{\diamond}$ with uncertainty. Ideally, we would compute the expectation of the
model likelihood under the approximate posterior, i.e.

$$ $\displaystyle p({\bm{y}}_{\diamond}\mid{\bm{x}}_{\diamond},{\mathbb{D}})$ $\displaystyle=\int p({\bm{y}}_{\diamond}\mid{\bm{x}}_{\diamond},{\bm{\theta}}) \,p({\bm{\theta}}\mid{\mathbb{D}})\,d{\bm{\theta}}$ $\displaystyle{\approx}\int{\operatorname{Cat}\mathopen{}\left({\bm{y}}_{ \diamond};\text{softmax}(f_{{\bm{\theta}}}({\bm{x}}_{\diamond}))\right)}\,{ \operatorname{\mathcal{N}}\mathopen{}\left({\bm{\theta}};{\bm{\theta}}_{\star} ,{\bm{\Sigma}}_{\mathcal{B}}\right)}\,d{\bm{\theta}}.$ $$

One way to approximate this integral is via Monte Carlo sampling, i.e.

$$ $p({\bm{y}}_{\diamond}\mid{\bm{x}}_{\diamond},{\mathbb{D}})\approx\frac{1}{S} \sum_{s=1}^{S}{\operatorname{Cat}\mathopen{}\left({\bm{y}}_{\diamond};\text{ softmax}(f_{{\bm{\theta}}^{(s)}}^{\text{lin}}({\bm{x}}_{\diamond}))\right)} \quad\text{where}\quad{\bm{\theta}}^{(s)}\sim{\operatorname{\mathcal{N}} \mathopen{}\left({\bm{\theta}}_{\star},{\bm{\Sigma}}_{\mathcal{B}}\right)}.$ (18) $$

As suggested by Immer et al. (); Roy et al. (), we use the
linearized network
$f_{{\bm{\theta}}}^{\text{lin}}({\bm{x}})\coloneqq f_{{\bm{\theta}}_{\star}}({
\bm{x}})+\nabla f_{{\bm{\theta}}_{\star}}({\bm{x}})({\bm{\theta}}-{\bm{\theta}
}_{\star})$, where $\nabla f_{{\bm{\theta}}_{\star}}({\bm{x}})\in\mathbb{R}^{C\times P}$ is
the network’s Jacobian at ${\bm{\theta}}_{\star}$.

#### A.3.2 Sampling from the K-FAC Laplace approximation

The Monte Carlo (MC) approach from Equation 18 requires samples from
the Gaussian ${\operatorname{\mathcal{N}}\mathopen{}\left({\bm{\theta}}_{\star},{\bm{\Sigma}
}_{\mathcal{B}}\right)}$ (the following derivations
work exactly the same when the full-batch LA based on the entire training set is used).
However, ${\bm{\Sigma}}_{\mathcal{B}}\in\mathbb{R}^{P\times P}$ is often too large
to be built explicitly in memory and it requires inverting the $P\times P$ Hessian ${\bm{H}}_{\mathcal{B}}$ of the regularized loss function. One approach
for that issue is to use the K-FAC curvature approximation ${\bm{H}}_{\mathcal{B}}=\nabla^{2}\mathcal{L}({\bm{\theta}};\mathcal{B})+\beta{
\bm{I}}\approx{\bm{K}}_{\mathcal{B}}+\beta{\bm{I}}$,
i.e. ${\bm{\Sigma}}_{\mathcal{B}}\approx N^{-1}({\bm{K}}_{\mathcal{B}}+\beta{\bm{I}}
)^{-1}$.
As we will see in the following, the K-FAC approximation enables us to sample
efficiently from the corresponding LA.

Leveraging K-FAC’s block-diagonal structure. K-FAC is a block-diagonal
curvature approximation, i.e. ${\bm{K}}_{\mathcal{B}}=\operatorname{blockdiag}_{l=1,\ldots,L}({\bm{K}}_{
\mathcal{B}}^{(l)})$ and ${\bm{K}}_{\mathcal{B}}+\beta{\bm{I}}$ inherits this structure.
The inverse of a block-diagonal matrix is also block-diagonal with the block inverses on
the diagonal,
i.e.

$$ $\displaystyle{\bm{\Sigma}}_{\mathcal{B}}$ $\displaystyle\approx\frac{1}{N}({\bm{K}}_{\mathcal{B}}+\beta{\bm{I}})^{-1}$ $\displaystyle=\frac{1}{N}\big{(}\operatorname{blockdiag}_{l=1,\ldots,L}({\bm{K }}_{\mathcal{B}}^{(l)}+\beta{\bm{I}})\big{)}^{-1}$ $\displaystyle=\operatorname{blockdiag}_{l=1,\ldots,L}\big{(}\underbracket{ \frac{1}{N}({\bm{K}}_{\mathcal{B}}^{(l)}+\beta{\bm{I}})^{-1}}_{\displaystyle \eqqcolon{\bm{\Sigma}}^{(l)}}\big{)}$ $\displaystyle=\operatorname{blockdiag}_{l=1,\ldots,L}({\bm{\Sigma}}^{(l)}).$ $$

To draw a sample ${\bm{v}}\in\mathbb{R}^{P}$ from
${\operatorname{\mathcal{N}}\mathopen{}\left({\bm{\theta}}_{\star},{\bm{\Sigma}
}_{\mathcal{B}}\right)}$, we can thus simply sample from the block
covariances ${\bm{v}}^{(l)}\sim{\operatorname{\mathcal{N}}\mathopen{}\left({\bm{0}},{\bm{
\Sigma}}^{(l)}\right)}$, stack these samples and
add the mean, i.e. ${\bm{v}}={\bm{\theta}}_{\star}+({\bm{v}}^{(1)},\dots,{\bm{v}}^{(L)})$.

Leveraging the blocks’ Kronecker structure. To sample from
${\operatorname{\mathcal{N}}\mathopen{}\left({\bm{0}},{\bm{\Sigma}}^{(l)}\right)}$, we can exploit the Kronecker structure of the blocks
${\bm{K}}_{\mathcal{B}}^{(l)}={\bm{A}}\otimes{\bm{B}}$ (we omit the layer index $l$ for ${\bm{A}}$ and
${\bm{B}}$ for brevity). First, we compute the eigendecompositions of the Kronecker factors,
i.e. ${\bm{A}}={\bm{U}}_{{\bm{A}}}{\bm{S}}_{{\bm{A}}}{\bm{U}}_{{\bm{A}}}^{\top}$ and ${\bm{B}}={\bm{U}}_{{\bm{B}}}{\bm{S}}_{{\bm{B}}}{\bm{U}}_{{\bm{B}}}^{\top}$. It follows

$$ $\displaystyle{\bm{K}}_{\mathcal{B}}^{(l)}+\beta{\bm{I}}$ $\displaystyle={\bm{A}}\otimes{\bm{B}}+\beta{\bm{I}}$ $\displaystyle={\bm{U}}_{{\bm{A}}}{\bm{S}}_{{\bm{A}}}{\bm{U}}_{{\bm{A}}}^{\top} \otimes{\bm{U}}_{{\bm{B}}}{\bm{S}}_{{\bm{B}}}{\bm{U}}_{{\bm{B}}}^{\top}+\beta{ \bm{I}}$ $\displaystyle=\underbracket{({\bm{U}}_{{\bm{A}}}\otimes{\bm{U}}_{{\bm{B}}})}_{ \displaystyle\eqqcolon{\bm{U}}}\underbracket{({\bm{S}}_{{\bm{A}}}\otimes{\bm{S }}_{{\bm{B}}})}_{\displaystyle\eqqcolon{\bm{S}}}({\bm{U}}_{{\bm{A}}}\otimes{ \bm{U}}_{{\bm{B}}})^{\top}+\beta{\bm{I}}$ $\displaystyle={\bm{U}}{\bm{S}}{\bm{U}}^{\top}+\beta{\bm{I}}$ $\displaystyle={\bm{U}}({\bm{S}}+\beta{\bm{I}}){\bm{U}}^{\top}.$ $$

${\bm{U}}={\bm{U}}_{{\bm{A}}}\otimes{\bm{U}}_{{\bm{B}}}$ forms an orthogonal eigenbasis of the block and the
diagonal matrix ${\bm{S}}+\beta{\bm{I}}={\bm{S}}_{{\bm{A}}}\otimes{\bm{S}}_{{\bm{B}}}+\beta{\bm
{I}}$ contains the
corresponding eigenvalues (see e.g. (George et al., )). It follows

$$ $\displaystyle{\bm{\Sigma}}^{(l)}$ $\displaystyle=\frac{1}{N}({\bm{K}}_{\mathcal{B}}^{(l)}+\beta{\bm{I}})^{-1}$ $\displaystyle=\frac{1}{N}{\bm{U}}({\bm{S}}+\beta{\bm{I}})^{-1}{\bm{U}}^{\top}$ $\displaystyle=\underbracket{\frac{1}{\sqrt{N}}{\bm{U}}({\bm{S}}+\beta{\bm{I}}) ^{-1/2}}_{\displaystyle\eqqcolon{\bm{V}}}\frac{1}{\sqrt{N}}({\bm{S}}+\beta{\bm {I}})^{-1/2}{\bm{U}}^{\top}$ $\displaystyle={\bm{V}}{\bm{V}}^{\top}.$ $$

So, in order to draw a sample ${\bm{v}}^{(l)}\sim{\operatorname{\mathcal{N}}\mathopen{}\left({\bm{0}},{\bm{
\Sigma}}^{(l)}\right)}$, we
first draw from a standard Gaussian ${\bm{w}}\sim{\operatorname{\mathcal{N}}\mathopen{}\left({\bm{0}},{\bm{I}}
\right)}$ and then transform
the sample via ${\bm{v}}^{(l)}={\bm{V}}{\bm{w}}$. The resulting vector ${\bm{v}}^{(l)}$ has mean ${\bm{0}}$
and covariance ${\bm{V}}{\bm{I}}{\bm{V}}^{\top}={\bm{\Sigma}}^{(l)}$. As Gaussians are closed under affine
linear transformations, ${\bm{v}}^{(l)}$ is indeed distributed according to
${\operatorname{\mathcal{N}}\mathopen{}\left({\bm{0}},{\bm{\Sigma}}^{(l)}\right)}$.

The matrix-vector product ${\bm{w}}\mapsto{\bm{V}}{\bm{w}}$ can be computed efficiently without
actually forming ${\bm{V}}$ in memory. The first step is to multiply with $({\bm{S}}+\beta{\bm{I}})^{-1/2}$. Since this is a diagonal matrix, we can simply multiply the vector ${\bm{w}}$
element-wise with the inverse square root of the diagonal entries of ${\bm{S}}+\beta{\bm{I}}$.
The second step is to multiply with ${\bm{U}}={\bm{U}}_{{\bm{A}}}\otimes{\bm{U}}_{{\bm{B}}}$, which can be
implemented efficiently by using the property $({\bm{U}}_{{\bm{A}}}\otimes{\bm{U}}_{{\bm{B}}})\operatorname{vec}({\bm{W}})=
\operatorname{vec}({\bm{U}}_{{\bm{B}}}{\bm{W}}{\bm{U}}_{{\bm{A}}}^{\top})$. Finally, we scale by $N^{-1/2}$.

Summary. Drawing a sample from the K-FAC LA
${\operatorname{\mathcal{N}}\mathopen{}\left({\bm{\theta}}_{\star},N^{-1}({\bm{
K}}_{\mathcal{B}}+\beta{\bm{I}})^{-1}\right)}$ can be
done without ever forming the blocks of the covariance matrix explicitly. Using
properties of the Kronecker product, we can efficiently transform a sample from the
standard Gaussian to a sample ${\bm{v}}^{(l)}\sim{\operatorname{\mathcal{N}}\mathopen{}\left({\bm{0}},{\bm{
\Sigma}}^{(l)}\right)}$.
Stacking the samples from all blocks and adding the mean ${\bm{\theta}}_{\star}$ yields a sample
from the LA due to the block-diagonal structure of the covariance matrix.

#### A.3.3 Debiased K-FAC Laplace approximation

The idea of the debiased K-FAC Laplace approximation is to construct one
Kronecker-factored curvature matrix from two mini-batches $\mathcal{B}$ and
$\tilde{\mathcal{B}}$.

Eigenbasis of a K-FAC block. First, recall that the eigendecomposition of a
block ${\bm{K}}_{\mathcal{B}}^{(l)}$ from a K-FAC matrix can be constructed from the
eigendecompositions of the Kronecker factors (see e.g. (George et al., )). Consider
the $l$-th block from both K-FAC approximations ${\bm{K}}_{\mathcal{B}}^{(l)}\!=\!{\bm{A}}\otimes{\bm{B}}$ and ${\bm{K}}_{\tilde{\mathcal{B}}}^{(l)}\!=\!{\bm{C}}\otimes{\bm{D}}$ (we omit the layer index $l$
for ${\bm{A}}$, ${\bm{B}}$, ${\bm{C}}$, and ${\bm{D}}$ for brevity). Again, let ${\bm{A}}\!=\!{\bm{U}}_{{\bm{A}}}{\bm{S}}_{{\bm{A}}}{\bm{U}}_{{\bm{A}}}^{\top}$ and ${\bm{B}}\!=\!{\bm{U}}_{{\bm{B}}}{\bm{S}}_{{\bm{B}}}{\bm{U}}_{{\bm{B}}}^{\top}$ denote the
eigendecompositions of the Kronecker factors. It holds

$$ $\displaystyle{\bm{K}}_{\mathcal{B}}^{(l)}$ $\displaystyle={\bm{A}}\otimes{\bm{B}}$ $\displaystyle={\bm{U}}_{{\bm{A}}}{\bm{S}}_{{\bm{A}}}{\bm{U}}_{{\bm{A}}}^{\top} \otimes{\bm{U}}_{{\bm{B}}}{\bm{S}}_{{\bm{B}}}{\bm{U}}_{{\bm{B}}}^{\top}$ $\displaystyle=\underbracket{({\bm{U}}_{{\bm{A}}}\otimes{\bm{U}}_{{\bm{B}}})}_{ \displaystyle\eqqcolon{\bm{U}}}\underbracket{({\bm{S}}_{{\bm{A}}}\otimes{\bm{S }}_{{\bm{B}}})}_{\displaystyle\eqqcolon{\bm{S}}}({\bm{U}}_{{\bm{A}}}\otimes{ \bm{U}}_{{\bm{B}}})^{\top}$ $\displaystyle={\bm{U}}{\bm{S}}\,{\bm{U}}^{\top}$ $$

${\bm{U}}={\bm{U}}_{{\bm{A}}}\otimes{\bm{U}}_{{\bm{B}}}$ forms an orthogonal eigenbasis of the block and the
diagonal matrix ${\bm{S}}={\bm{S}}_{{\bm{A}}}\otimes{\bm{S}}_{{\bm{B}}}$ contains the eigenvalues.

Re-evaluation of the directional curvatures. For the debiased approach, we keep
the block’s eigenbasis ${\bm{U}}$, but instead of using the directional curvatures ${\bm{S}}$, we
re-evaluate these measurements on the second mini-batch $\tilde{\mathcal{B}}$. First,
consider the projection of the block ${\bm{K}}_{\tilde{\mathcal{B}}}^{(l)}$ onto the eigenvectors
${\bm{U}}$, i.e.

$$ $\displaystyle{\bm{U}}^{\top}{\bm{K}}_{\tilde{\mathcal{B}}}^{(l)}{\bm{U}}=({\bm {U}}_{{\bm{A}}}\otimes{\bm{U}}_{{\bm{B}}})^{\top}({\bm{C}}\otimes{\bm{D}})({ \bm{U}}_{{\bm{A}}}\otimes{\bm{U}}_{{\bm{B}}})={\bm{U}}_{{\bm{A}}}^{\top}{\bm{C }}\,{\bm{U}}_{{\bm{A}}}\otimes{\bm{U}}_{{\bm{B}}}^{\top}{\bm{D}}\,{\bm{U}}_{{ \bm{B}}}.$ $$

The debiased directional curvatures are on the diagonal of ${\bm{U}}^{\top}{\bm{K}}_{\tilde{\mathcal{B}}}^{(l)}{\bm{U}}$.
For a square matrix ${\bm{X}}\in\mathbb{R}^{n\times n}$, let $\operatorname{Diag}({\bm{X}})$ denote the operator that maps the
matrix onto its diagonal, i.e. $\operatorname{Diag}\,\colon\,\mathbb{R}^{n\times n}\to\mathbb{R}^{n}$ with
$\operatorname{Diag}({\bm{X}})_{i}:=X_{ii}$ for $i\in\{1,\dots,n\}$. It holds:

$$ $\displaystyle\operatorname{Diag}({\bm{U}}^{\top}{\bm{K}}_{\tilde{\mathcal{B}}} ^{(l)}{\bm{U}})$ $\displaystyle=\operatorname{Diag}({\bm{U}}_{{\bm{A}}}^{\top}{\bm{C}}\,{\bm{U}} _{{\bm{A}}}\otimes{\bm{U}}_{{\bm{B}}}^{\top}{\bm{D}}\,{\bm{U}}_{{\bm{B}}})$ $\displaystyle=\underbracket{\operatorname{Diag}({\bm{U}}_{{\bm{A}}}^{\top}{\bm {C}}\,{\bm{U}}_{{\bm{A}}})}_{\displaystyle\eqqcolon\tilde{{\bm{s}}}_{{\bm{A}}} }\otimes\underbracket{\operatorname{Diag}({\bm{U}}_{{\bm{B}}}^{\top}{\bm{D}}\, {\bm{U}}_{{\bm{B}}})}_{\displaystyle\eqqcolon\tilde{{\bm{s}}}_{{\bm{B}}}}$ $\displaystyle=\tilde{{\bm{s}}}_{{\bm{A}}}\otimes\tilde{{\bm{s}}}_{{\bm{B}}}$ $\displaystyle\eqqcolon\tilde{{\bm{s}}}.$ $$

Construction of a debiased block. Now that we have the eigenbasis ${\bm{U}}$ and the
debiased directional curvatures $\tilde{{\bm{s}}}$, we construct the debiased block. Let
$\tilde{{\bm{S}}}_{{\bm{A}}}\coloneqq\operatorname{diag}(\tilde{{\bm{s}}}_{{\bm
{A}}})$, $\tilde{{\bm{S}}}_{{\bm{B}}}\coloneqq\operatorname{diag}(\tilde{{\bm{s}}}_{{\bm
{B}}})$ and

$$ $\tilde{{\bm{S}}}\coloneqq\operatorname{diag}(\tilde{{\bm{s}}})=\operatorname{ diag}(\tilde{{\bm{s}}}_{{\bm{A}}}\otimes\tilde{{\bm{s}}}_{{\bm{B}}})= \operatorname{diag}(\tilde{{\bm{s}}}_{{\bm{A}}})\otimes\operatorname{diag}( \tilde{{\bm{s}}}_{{\bm{B}}})=\tilde{{\bm{S}}}_{{\bm{A}}}\otimes\tilde{{\bm{S}} }_{{\bm{B}}}.$ $$

The debiased block is given by ${\bm{U}}\tilde{{\bm{S}}}{\bm{U}}^{\top}$. It can be written as the
Kronecker product of two matrices $\tilde{{\bm{A}}}$ and $\tilde{{\bm{B}}}$ since

$$ $\displaystyle{\bm{U}}\tilde{{\bm{S}}}{\bm{U}}^{\top}=({\bm{U}}_{{\bm{A}}} \otimes{\bm{U}}_{{\bm{B}}})(\tilde{{\bm{S}}}_{{\bm{A}}}\otimes\tilde{{\bm{S}}} _{{\bm{B}}})({\bm{U}}_{{\bm{A}}}\otimes{\bm{U}}_{{\bm{B}}})^{\top}= \underbracket{({\bm{U}}_{{\bm{A}}}\tilde{{\bm{S}}}_{{\bm{A}}}{\bm{U}}_{{\bm{A} }}^{\top})}_{\displaystyle\eqqcolon\tilde{{\bm{A}}}}\otimes\underbracket{({\bm {U}}_{{\bm{B}}}\tilde{{\bm{S}}}_{{\bm{B}}}{\bm{U}}_{{\bm{B}}}^{\top})}_{ \displaystyle\eqqcolon\tilde{{\bm{B}}}}.$ $$

This is important as it allows for efficient sampling as described in
Section A.3.2.

Computational cost. Since we need the eigendecompositions of the Kronecker
factors ${\bm{A}}={\bm{U}}_{{\bm{A}}}{\bm{S}}_{{\bm{A}}}\,{\bm{U}}_{{\bm{A}}}^{\top}$ and ${\bm{B}}={\bm{U}}_{{\bm{B}}}{\bm{S}}_{{\bm{B}}}\,{\bm{U}}_{{\bm{B}}}^{\top}$ for sampling in any case (see
Section A.3.2), the computational overhead for the
debiased K-FAC approximation $\tilde{{\bm{A}}}\otimes\tilde{{\bm{B}}}$ consists of computing a
K-FAC approximation ${\bm{C}}\otimes{\bm{D}}$ on another mini-batch, re-evaluating the
directional curvatures $\tilde{{\bm{s}}}_{{\bm{A}}}=\operatorname{Diag}({\bm{U}}_{{\bm{A}}}^{\top}{\bm
{C}}\,{\bm{U}}_{{\bm{A}}})$ and
$\tilde{{\bm{s}}}_{{\bm{B}}}=\operatorname{Diag}({\bm{U}}_{{\bm{B}}}^{\top}{\bm
{D}}\,{\bm{U}}_{{\bm{B}}})$ and finally computing
$\tilde{{\bm{A}}}={\bm{U}}_{{\bm{A}}}\operatorname{diag}(\tilde{{\bm{s}}}_{{\bm
{A}}})\,{\bm{U}}_{{\bm{A}}}^{\top}$ and $\tilde{{\bm{B}}}={\bm{U}}_{{\bm{B}}}\operatorname{diag}(\tilde{{\bm{s}}}_{{\bm
{B}}})\,{\bm{U}}_{{\bm{B}}}^{\top}$.

From block-level to full matrix. So far, we have only considered the debiasing
of a single block. However, correcting the blocks’s eigenvalues is sufficient because
they coincide with the eigenvalues of the full matrix (due to the block-diagonal
structure). Let ${\bm{u}}^{(l)}$ denote an eigenvector of the $l$-th block ${\bm{X}}^{(l)}$ of
some block-diagonal matrix ${\bm{X}}=\operatorname{blockdiag}_{l=1,\dots,L}({\bm{X}}^{(l)})$ corresponding
to the eigenvalue $\lambda$. Then, ${\bm{u}}^{\top}\coloneqq({\bm{0}}^{\top},\dots,{{\bm{u}}^{(l)}}^{\top},\dots,{
\bm{0}}^{\top})$ is an eigenvector of ${\bm{X}}$ corresponding to the
same eigenvalue $\lambda$, because

$$ ${\bm{X}}\cdot{\bm{u}}=\operatorname{blockdiag}_{l=1,\ldots,L}({\bm{X}}^{(l)}) \cdot{\bm{u}}=\begin{pmatrix}{\bm{X}}^{(1)}\cdot{\bm{0}}\\ \vdots\\ {\bm{X}}^{(l)}\cdot{\bm{u}}^{(l)}\\ \vdots\\ {\bm{X}}^{(L)}\cdot{\bm{0}}\end{pmatrix}=\begin{pmatrix}{\bm{0}}\\ \vdots\\ \lambda\,{\bm{u}}^{(l)}\\ \vdots\\ {\bm{0}}\end{pmatrix}=\lambda{\bm{u}}.$ $$

The eigenvalues of ${\bm{X}}$ thus coincide with the eigenvalues of its blocks; and ${\bm{X}}$’s
eigenvectors can be constructed from the the eigenvectors of the blocks by filling them
up with zeros.

Connection to Equation 9: The equivalence between
Equation 9 and the approach we describe above may not be obvious. We thus
show here that the directional curvature of the debiased matrix $\hat{{\bm{K}}}$ along an
eigenvector ${\bm{u}}$ of ${\bm{K}}_{\mathcal{B}}$ indeed coincides with the directional curvature
${\bm{u}}^{\top}{\bm{K}}_{\tilde{\mathcal{B}}}\,{\bm{u}}$ on $\tilde{\mathcal{B}}$.

More concretely, let $\hat{{\bm{K}}}=\operatorname{blockdiag}_{l=1,\dots,L}(\hat{{\bm{K}}}^{(l)})$ denote
the debiased K-FAC approximation constructed from ${\bm{K}}_{\mathcal{B}}$ and
${\bm{K}}_{\tilde{\mathcal{B}}}$ as described above. Also, let ${\bm{u}}^{\top}\coloneqq({\bm{0}}^{\top},\dots,{{\bm{u}}^{(l)}}^{\top},\dots,{
\bm{0}}^{\top})$ denote an eigenvector of
${\bm{K}}_{\mathcal{B}}$, where ${\bm{u}}^{(l)}$ is the $i$-th eigenvector of
${\bm{K}}_{\mathcal{B}}^{(l)}$ (i.e. the $i$-th column of ${\bm{U}}$).
It holds

$$ ${\bm{u}}^{\top}\hat{{\bm{K}}}{\bm{u}}={{\bm{u}}^{(l)}}^{\top}\hat{{\bm{K}}}^{( l)}\,{\bm{u}}^{(l)}={{\bm{u}}^{(l)}}^{\top}{\bm{U}}\tilde{{\bm{S}}}\,{\bm{U}}^ {\top}\,{\bm{u}}^{(l)}={\bm{e}}_{i}^{\top}\tilde{{\bm{S}}}\,{\bm{e}}_{i}= \tilde{{\bm{s}}}_{i}={{\bm{u}}^{(l)}}^{\top}{\bm{K}}_{\tilde{\mathcal{B}}}^{(l )}\,{\bm{u}}^{(l)}={\bm{u}}^{\top}{\bm{K}}_{\tilde{\mathcal{B}}}\,{\bm{u}},$ $$

where ${\bm{e}}_{i}$ denotes the $i$-th eigenvector.

### A.4 Bias in the directional slope

Biased directional slopes along negative gradient directions.
Assume that we are given a quadratic $q(\,\cdot\,;\mathcal{B})$ around the
current parameters ${\bm{\theta}}_{0}$. We consider the negative normalized gradient direction
${\bm{d}}=-\nabla q({\bm{\theta}}_{\bullet};\mathcal{B})\cdot\|\nabla q({\bm{
\theta}}_{\bullet};\mathcal{B})\|^{-1}$
at some location ${\bm{\theta}}_{\bullet}$ evaluated on mini-batch $\mathcal{B}$. We have

$$ $\underbracket{\partial_{{\bm{d}}}\,q({\bm{\theta}}_{\bullet};\tilde{\mathcal{B }})}_{\leavevmode\hbox to3.96pt{\vbox to3.96pt{\pgfpicture\makeatletter\hbox{ \hskip 1.97989pt\lower-1.97989pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke { }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0} \pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ } \pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ } {{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{ tikz@color}{rgb}{1,1,1}\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{ rgb}{0.296875,0.4453125,0.69140625}\pgfsys@color@rgb@fill{0.296875}{0.4453125} {0.69140625}\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{tikz@color}{rgb}{1,1,1} \definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{ 1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ }\pgfsys@color@gray@fill{1} \pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{ 0.296875,0.4453125,0.69140625}\pgfsys@color@rgb@fill{0.296875}{0.4453125}{0.69 140625}\pgfsys@invoke{ }\pgfsys@moveto{1.97989pt}{0.0pt}\pgfsys@curveto{1.9798 9pt}{1.09348pt}{1.09348pt}{1.97989pt}{0.0pt}{1.97989pt}\pgfsys@curveto{-1.0934 8pt}{1.97989pt}{-1.97989pt}{1.09348pt}{-1.97989pt}{0.0pt}\pgfsys@curveto{-1.97 989pt}{-1.09348pt}{-1.09348pt}{-1.97989pt}{0.0pt}{-1.97989pt}\pgfsys@curveto{1 .09348pt}{-1.97989pt}{1.97989pt}{-1.09348pt}{1.97989pt}{0.0pt} \pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fill\pgfsys@invoke{ } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}{{{{}}\pgfsys@beginscope \pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{0.0pt}{0.0pt} \pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{ 1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1} \pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}=\underbracket{\partial_{{\bm{d}}}\,q({\bm{ \theta}}_{\bullet};\mathcal{B})}_{\leavevmode\hbox to3.96pt{\vbox to3.96pt{ \pgfpicture\makeatletter\hbox{\hskip 1.97989pt\lower-1.97989pt\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to 0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{ tikz@color}{rgb}{1,1,1}\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{ rgb}{0.8671875,0.51953125,0.3203125}\pgfsys@color@rgb@fill{0.8671875}{0.519531 25}{0.3203125}\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{tikz@color}{rgb}{1,1,1} \definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{ 1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ }\pgfsys@color@gray@fill{1} \pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{ 0.8671875,0.51953125,0.3203125}\pgfsys@color@rgb@fill{0.8671875}{0.51953125}{0 .3203125}\pgfsys@invoke{ }\pgfsys@moveto{1.97989pt}{0.0pt}\pgfsys@curveto{1.97 989pt}{1.09348pt}{1.09348pt}{1.97989pt}{0.0pt}{1.97989pt}\pgfsys@curveto{-1.09 348pt}{1.97989pt}{-1.97989pt}{1.09348pt}{-1.97989pt}{0.0pt}\pgfsys@curveto{-1. 97989pt}{-1.09348pt}{-1.09348pt}{-1.97989pt}{0.0pt}{-1.97989pt}\pgfsys@curveto {1.09348pt}{-1.97989pt}{1.97989pt}{-1.09348pt}{1.97989pt}{0.0pt} \pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fill\pgfsys@invoke{ } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}{{{{}}\pgfsys@beginscope \pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{0.0pt}{0.0pt} \pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{ 1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1} \pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}+\,\|\nabla q({\bm{\theta}}_{\bullet}; \mathcal{B})\|(1-\cos(\alpha))\geq\underbracket{\partial_{{\bm{d}}}\,q({\bm{ \theta}}_{\bullet};\mathcal{B})}_{\leavevmode\hbox to3.96pt{\vbox to3.96pt{ \pgfpicture\makeatletter\hbox{\hskip 1.97989pt\lower-1.97989pt\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to 0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{ tikz@color}{rgb}{1,1,1}\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{ rgb}{0.8671875,0.51953125,0.3203125}\pgfsys@color@rgb@fill{0.8671875}{0.519531 25}{0.3203125}\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{tikz@color}{rgb}{1,1,1} \definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{ 1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ }\pgfsys@color@gray@fill{1} \pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{ 0.8671875,0.51953125,0.3203125}\pgfsys@color@rgb@fill{0.8671875}{0.51953125}{0 .3203125}\pgfsys@invoke{ }\pgfsys@moveto{1.97989pt}{0.0pt}\pgfsys@curveto{1.97 989pt}{1.09348pt}{1.09348pt}{1.97989pt}{0.0pt}{1.97989pt}\pgfsys@curveto{-1.09 348pt}{1.97989pt}{-1.97989pt}{1.09348pt}{-1.97989pt}{0.0pt}\pgfsys@curveto{-1. 97989pt}{-1.09348pt}{-1.09348pt}{-1.97989pt}{0.0pt}{-1.97989pt}\pgfsys@curveto {1.09348pt}{-1.97989pt}{1.97989pt}{-1.09348pt}{1.97989pt}{0.0pt} \pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fill\pgfsys@invoke{ } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}{{{{}}\pgfsys@beginscope \pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{0.0pt}{0.0pt} \pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{ 1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1} \pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}},$ (19) $$

where $\alpha\coloneqq\angle(\nabla q({\bm{\theta}}_{\bullet};\mathcal{B}),\nabla q({
\bm{\theta}}_{\bullet};\tilde{\mathcal{B}}))$ and we assumed $\|\nabla q({\bm{\theta}}_{\bullet};\tilde{\mathcal{B}})\|=\|\nabla q({\bm{
\theta}}_{\bullet};\mathcal{B})\|$ which is true at least in expectation.
Projecting a gradient onto its negative direction—the right-hand side of the
inequality—will always result in a directional slope that is $\leq 0$ since

$$ $\partial_{{\bm{d}}}\,q({\bm{\theta}}_{\bullet};\mathcal{B})={\bm{d}}^{\top} \nabla q({\bm{\theta}}_{\bullet};\mathcal{B})=-\frac{\nabla q({\bm{\theta}}_{ \bullet};\mathcal{B})^{\top}}{\|\nabla q({\bm{\theta}}_{\bullet};\mathcal{B}) \|}\nabla q({\bm{\theta}}_{\bullet};\mathcal{B})=-\|\nabla q({\bm{\theta}}_{ \bullet};\mathcal{B})\|\leq 0$ $$

and $=0$ only if $\nabla q({\bm{\theta}}_{\bullet};\mathcal{B})={\bm{0}}$. Projecting
a different gradient (of equal length) onto that direction—that is the
left-hand side of the inequality—will result in a larger (possibly even positive)
directional slope.

Proof of Equation 19. Equation 19 quantifies the bias
in the directional slope along ${\bm{d}}$ as a function of the alignment of the two
mini-batch gradients. It holds

$$ $\displaystyle\underbracket{\partial_{{\bm{d}}}\,q({\bm{\theta}}_{\bullet}; \mathcal{B})}_{\leavevmode\hbox to3.96pt{\vbox to3.96pt{\pgfpicture \makeatletter\hbox{\hskip 1.97989pt\lower-1.97989pt\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to 0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{ tikz@color}{rgb}{1,1,1}\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{ rgb}{0.8671875,0.51953125,0.3203125}\pgfsys@color@rgb@fill{0.8671875}{0.519531 25}{0.3203125}\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{tikz@color}{rgb}{1,1,1} \definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{ 1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ }\pgfsys@color@gray@fill{1} \pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{ 0.8671875,0.51953125,0.3203125}\pgfsys@color@rgb@fill{0.8671875}{0.51953125}{0 .3203125}\pgfsys@invoke{ }\pgfsys@moveto{1.97989pt}{0.0pt}\pgfsys@curveto{1.97 989pt}{1.09348pt}{1.09348pt}{1.97989pt}{0.0pt}{1.97989pt}\pgfsys@curveto{-1.09 348pt}{1.97989pt}{-1.97989pt}{1.09348pt}{-1.97989pt}{0.0pt}\pgfsys@curveto{-1. 97989pt}{-1.09348pt}{-1.09348pt}{-1.97989pt}{0.0pt}{-1.97989pt}\pgfsys@curveto {1.09348pt}{-1.97989pt}{1.97989pt}{-1.09348pt}{1.97989pt}{0.0pt} \pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fill\pgfsys@invoke{ } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}{{{{}}\pgfsys@beginscope \pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{0.0pt}{0.0pt} \pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{ 1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1} \pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}-\underbracket{\partial_{{\bm{d}}}\,q({\bm{ \theta}}_{\bullet};\tilde{\mathcal{B}})}_{\leavevmode\hbox to3.96pt{\vbox to 3.96pt{\pgfpicture\makeatletter\hbox{\hskip 1.97989pt\lower-1.97989pt\hbox to0 .0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{ 0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill {0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ } \nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{ tikz@color}{rgb}{1,1,1}\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{ rgb}{0.296875,0.4453125,0.69140625}\pgfsys@color@rgb@fill{0.296875}{0.4453125} {0.69140625}\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{tikz@color}{rgb}{1,1,1} \definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{ 1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ }\pgfsys@color@gray@fill{1} \pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{ 0.296875,0.4453125,0.69140625}\pgfsys@color@rgb@fill{0.296875}{0.4453125}{0.69 140625}\pgfsys@invoke{ }\pgfsys@moveto{1.97989pt}{0.0pt}\pgfsys@curveto{1.9798 9pt}{1.09348pt}{1.09348pt}{1.97989pt}{0.0pt}{1.97989pt}\pgfsys@curveto{-1.0934 8pt}{1.97989pt}{-1.97989pt}{1.09348pt}{-1.97989pt}{0.0pt}\pgfsys@curveto{-1.97 989pt}{-1.09348pt}{-1.09348pt}{-1.97989pt}{0.0pt}{-1.97989pt}\pgfsys@curveto{1 .09348pt}{-1.97989pt}{1.97989pt}{-1.09348pt}{1.97989pt}{0.0pt} \pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fill\pgfsys@invoke{ } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}{{{{}}\pgfsys@beginscope \pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{0.0pt}{0.0pt} \pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{ 1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1} \pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}$ $\displaystyle={\bm{d}}^{\top}\nabla q({\bm{\theta}}_{\bullet};\mathcal{B})-{ \bm{d}}^{\top}\nabla q({\bm{\theta}}_{\bullet};\tilde{\mathcal{B}})$ $\displaystyle=\underbracket{\|{\bm{d}}\|}_{=1}\,\|\nabla q({\bm{\theta}}_{ \bullet};\mathcal{B})\|\underbracket{\cos(\pi)}_{=-1}-\underbracket{\|{\bm{d}} \|}_{=1}\,\|\nabla q({\bm{\theta}}_{\bullet};\tilde{\mathcal{B}})\|\cos(\gamma)$ $\displaystyle=\|\nabla q({\bm{\theta}}_{\bullet};\mathcal{B})\|(-1-\cos(\gamma )),$ $$

where $\gamma=\angle({\bm{d}},\nabla q({\bm{\theta}}_{\bullet};\tilde{\mathcal{B}}))$ and we
assumed that $\|\nabla q({\bm{\theta}}_{\bullet};\mathcal{B})\|=\|\nabla q({\bm{\theta}}_{
\bullet};\tilde{\mathcal{B}})\|$ in the last step (which is true, at
least, in expectation). Next, we re-write $\gamma$ as

$$ $\gamma=\angle({\bm{d}},\nabla q({\bm{\theta}}_{\bullet};\tilde{\mathcal{B}}))= \angle(-\nabla q({\bm{\theta}}_{\bullet};\mathcal{B}),\nabla q({\bm{\theta}}_{ \bullet};\tilde{\mathcal{B}}))=\pi-\underbracket{\angle(\nabla q({\bm{\theta}} _{\bullet};\mathcal{B}),\nabla q({\bm{\theta}}_{\bullet};\tilde{\mathcal{B}})) }_{\eqqcolon\alpha}.$ $$

It follows
$-1-\cos(\gamma)=-1-\cos(\pi-\alpha)=\cos(\alpha)-1.$
Substituting this into the expression for the bias, we arrive at

$$ $\underbracket{\partial_{{\bm{d}}}\,q({\bm{\theta}}_{\bullet};\mathcal{B})}_{ \leavevmode\hbox to3.96pt{\vbox to3.96pt{\pgfpicture\makeatletter\hbox{\hskip 1 .97989pt\lower-1.97989pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } \definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0} \pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ } \pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ } {{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{ tikz@color}{rgb}{1,1,1}\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{ rgb}{0.8671875,0.51953125,0.3203125}\pgfsys@color@rgb@fill{0.8671875}{0.519531 25}{0.3203125}\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{tikz@color}{rgb}{1,1,1} \definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{ 1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ }\pgfsys@color@gray@fill{1} \pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{ 0.8671875,0.51953125,0.3203125}\pgfsys@color@rgb@fill{0.8671875}{0.51953125}{0 .3203125}\pgfsys@invoke{ }\pgfsys@moveto{1.97989pt}{0.0pt}\pgfsys@curveto{1.97 989pt}{1.09348pt}{1.09348pt}{1.97989pt}{0.0pt}{1.97989pt}\pgfsys@curveto{-1.09 348pt}{1.97989pt}{-1.97989pt}{1.09348pt}{-1.97989pt}{0.0pt}\pgfsys@curveto{-1. 97989pt}{-1.09348pt}{-1.09348pt}{-1.97989pt}{0.0pt}{-1.97989pt}\pgfsys@curveto {1.09348pt}{-1.97989pt}{1.97989pt}{-1.09348pt}{1.97989pt}{0.0pt} \pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fill\pgfsys@invoke{ } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}{{{{}}\pgfsys@beginscope \pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{0.0pt}{0.0pt} \pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{ 1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1} \pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}-\underbracket{\partial_{{\bm{d}}}\,q({\bm{ \theta}}_{\bullet};\tilde{\mathcal{B}})}_{\leavevmode\hbox to3.96pt{\vbox to 3.96pt{\pgfpicture\makeatletter\hbox{\hskip 1.97989pt\lower-1.97989pt\hbox to0 .0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{ 0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill {0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ } \nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{ tikz@color}{rgb}{1,1,1}\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{ rgb}{0.296875,0.4453125,0.69140625}\pgfsys@color@rgb@fill{0.296875}{0.4453125} {0.69140625}\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{tikz@color}{rgb}{1,1,1} \definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{ 1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ }\pgfsys@color@gray@fill{1} \pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{ 0.296875,0.4453125,0.69140625}\pgfsys@color@rgb@fill{0.296875}{0.4453125}{0.69 140625}\pgfsys@invoke{ }\pgfsys@moveto{1.97989pt}{0.0pt}\pgfsys@curveto{1.9798 9pt}{1.09348pt}{1.09348pt}{1.97989pt}{0.0pt}{1.97989pt}\pgfsys@curveto{-1.0934 8pt}{1.97989pt}{-1.97989pt}{1.09348pt}{-1.97989pt}{0.0pt}\pgfsys@curveto{-1.97 989pt}{-1.09348pt}{-1.09348pt}{-1.97989pt}{0.0pt}{-1.97989pt}\pgfsys@curveto{1 .09348pt}{-1.97989pt}{1.97989pt}{-1.09348pt}{1.97989pt}{0.0pt} \pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fill\pgfsys@invoke{ } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}{{{{}}\pgfsys@beginscope \pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{0.0pt}{0.0pt} \pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{ 1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1} \pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}=\|\nabla q({\bm{\theta}}_{\bullet};\mathcal {B})\|(-1-\cos(\gamma))=\|\nabla q({\bm{\theta}}_{\bullet};\mathcal{B})\|(\cos (\alpha)-1),$ $$

from which Equation 19 follows. ∎

The first CG search direction. Assume that the current parameters are
${\bm{\theta}}_{0}$ and we apply CG to the local quadratic approximation $q(\,\cdot\,;\mathcal{B})$. The very first search direction is the quadratic’s normalized negative
gradient ${\bm{d}}_{0}=-\nabla q({\bm{\theta}}_{0};\mathcal{B})\cdot\|\nabla q({\bm{
\theta}}_{0};\mathcal{B})\|^{-1}$ at ${\bm{\theta}}_{0}$. This is exactly the
situation we describe above, where ${\bm{\theta}}_{\bullet}$ is set to ${\bm{\theta}}_{0}$.
Equation 19 thus explains the bias for the first CG direction.

The subsequent CG search directions. For the subsequent CG search directions
(${\bm{d}}_{p}$ with $p\geq 1$), the situation is more complex: Each direction ${\bm{d}}_{p}$ is a
linear combination of the current normalized negative residual $-{\bm{r}}_{p}$ (note that
${\bm{r}}_{p}$ coincides with the gradient $\nabla q({\bm{\theta}}_{p};\mathcal{B})$, see
Section A.2) and the previous search direction ${\bm{d}}_{p-1}$ (see
Section A.2) and the previous search direction ${\bm{d}}_{p-1}$ (see
Algorithm 1), i.e.

$$ ${\bm{d}}_{p}=\frac{{\bm{s}}_{p}}{\|{\bm{s}}_{p}\|}=\frac{1}{\|{\bm{s}}_{p}\|}( -{\bm{r}}_{p})+\frac{\beta_{p}}{\|{\bm{s}}_{p}\|}{\bm{s}}_{p-1}=\underbracket{ \frac{\|{\bm{r}}_{p}\|}{\|{\bm{s}}_{p}\|}}_{\eqqcolon\eta_{1}\geq 0}\frac{-{ \bm{r}}_{p}}{\|{\bm{r}}_{p}\|}+\underbracket{\frac{\beta_{p}\|{\bm{s}}_{p-1}\| }{\|{\bm{s}}_{p}\|}}_{\eqqcolon\eta_{2}\geq 0}{\bm{d}}_{p-1}=\eta_{1}\frac{-{ \bm{r}}_{p}}{\|{\bm{r}}_{p}\|}+\eta_{2}\,{\bm{d}}_{p-1}.$ $$

The additional correction term ensures conjugacy. The
directional slope along ${\bm{d}}_{p}$ thus also splits into two corresponding terms: The slope
along the negative gradient direction and the slope along the previous search direction.
It holds

$$ $\displaystyle\partial_{{\bm{d}}_{p}}q({\bm{\theta}}_{p};\mathcal{B})$ $\displaystyle={\bm{d}}_{p}^{\top}\nabla q({\bm{\theta}}_{p};\mathcal{B})$ $\displaystyle=\eta_{1}\frac{-{\bm{r}}_{p}}{\|{\bm{r}}_{p}\|}^{\top}\nabla q({ \bm{\theta}}_{p};\mathcal{B})+\eta_{2}\,{\bm{d}}_{p-1}^{\top}\nabla q({\bm{ \theta}}_{p};\mathcal{B})$ $\displaystyle=\eta_{1}\partial_{\nicefrac{{-{\bm{r}}_{p}}}{{\|{\bm{r}}_{p}\|}} }q({\bm{\theta}}_{p};\mathcal{B})+\eta_{2}\,\partial_{{\bm{d}}_{p-1}}q({\bm{ \theta}}_{p};\mathcal{B}).$ $$

The bias in the first term—as explained by Equation 19—also introduces a
bias along the search direction ${\bm{d}}_{p}$.

### A.5 Bias in the directional curvature

Derivation for Equation 6.
Let ${\bm{H}}_{\mathcal{B}}={\bm{U}}{\bm{\Lambda}}{\bm{U}}^{\top}$ and
${\bm{H}}_{\tilde{\mathcal{B}}}=\tilde{{\bm{U}}}\tilde{{\bm{\Lambda}}}\tilde{{
\bm{U}}}^{\top}$
denote the eigendecompositions of the mini-batch Hessians, where ${\bm{U}}=({\bm{u}}_{1},\ldots,{\bm{u}}_{P}),\tilde{{\bm{U}}}=(\tilde{{\bm{u}}}
_{1},\ldots,\tilde{{\bm{u}}}_{P})\in\mathbb{R}^{P\times P}$ contain the
orthonormal eigenvectors and ${\bm{\Lambda}}=\operatorname{diag}(\lambda_{1},\ldots,\lambda_{P})$, $\tilde{{\bm{\Lambda}}}=\operatorname{diag}(\tilde{\lambda}_{1},\ldots,\tilde{
\lambda}_{P})$ the respective eigenvalues in descending order, i.e. $\lambda_{1}\geq\ldots\geq\lambda_{P}$ and $\tilde{\lambda}_{1}\geq\ldots\geq\tilde{\lambda}_{P}$.
The directional curvature along one of ${\bm{H}}_{\mathcal{B}}$’s eigenvectors ${\bm{u}}_{i}$
on mini-batch $\mathcal{B}$ is given by the corresponding eigenvalue since

$$ $\underbracket{\partial^{2}_{{\bm{u}}_{i}}q({\bm{\theta}}_{\bullet};\mathcal{B} )}_{\leavevmode\hbox to3.96pt{\vbox to3.96pt{\pgfpicture\makeatletter\hbox{ \hskip 1.97989pt\lower-1.97989pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke { }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0} \pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ } \pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ } {{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{ tikz@color}{rgb}{1,1,1}\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{ rgb}{0.8671875,0.51953125,0.3203125}\pgfsys@color@rgb@fill{0.8671875}{0.519531 25}{0.3203125}\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{tikz@color}{rgb}{1,1,1} \definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{ 1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ }\pgfsys@color@gray@fill{1} \pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{ 0.8671875,0.51953125,0.3203125}\pgfsys@color@rgb@fill{0.8671875}{0.51953125}{0 .3203125}\pgfsys@invoke{ }\pgfsys@moveto{1.97989pt}{0.0pt}\pgfsys@curveto{1.97 989pt}{1.09348pt}{1.09348pt}{1.97989pt}{0.0pt}{1.97989pt}\pgfsys@curveto{-1.09 348pt}{1.97989pt}{-1.97989pt}{1.09348pt}{-1.97989pt}{0.0pt}\pgfsys@curveto{-1. 97989pt}{-1.09348pt}{-1.09348pt}{-1.97989pt}{0.0pt}{-1.97989pt}\pgfsys@curveto {1.09348pt}{-1.97989pt}{1.97989pt}{-1.09348pt}{1.97989pt}{0.0pt} \pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fill\pgfsys@invoke{ } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}{{{{}}\pgfsys@beginscope \pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{0.0pt}{0.0pt} \pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{ 1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1} \pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}={\bm{u}}_{i}^{\top}{\bm{H}}_{\mathcal{B}}{ \bm{u}}_{i}={\bm{u}}_{i}^{\top}\lambda_{i}{\bm{u}}_{i}=\lambda_{i}\|{\bm{u}}_{ i}\|_{2}^{2}=\lambda_{i}.$ $$

For $\tilde{\mathcal{B}}$, we obtain

$$ $\underbracket{\partial^{2}_{{\bm{u}}_{i}}q({\bm{\theta}}_{\bullet};\tilde{ \mathcal{B}})}_{\leavevmode\hbox to3.96pt{\vbox to3.96pt{\pgfpicture \makeatletter\hbox{\hskip 1.97989pt\lower-1.97989pt\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to 0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{ tikz@color}{rgb}{1,1,1}\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{ rgb}{0.296875,0.4453125,0.69140625}\pgfsys@color@rgb@fill{0.296875}{0.4453125} {0.69140625}\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{tikz@color}{rgb}{1,1,1} \definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{ 1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ }\pgfsys@color@gray@fill{1} \pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{ 0.296875,0.4453125,0.69140625}\pgfsys@color@rgb@fill{0.296875}{0.4453125}{0.69 140625}\pgfsys@invoke{ }\pgfsys@moveto{1.97989pt}{0.0pt}\pgfsys@curveto{1.9798 9pt}{1.09348pt}{1.09348pt}{1.97989pt}{0.0pt}{1.97989pt}\pgfsys@curveto{-1.0934 8pt}{1.97989pt}{-1.97989pt}{1.09348pt}{-1.97989pt}{0.0pt}\pgfsys@curveto{-1.97 989pt}{-1.09348pt}{-1.09348pt}{-1.97989pt}{0.0pt}{-1.97989pt}\pgfsys@curveto{1 .09348pt}{-1.97989pt}{1.97989pt}{-1.09348pt}{1.97989pt}{0.0pt} \pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fill\pgfsys@invoke{ } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}{{{{}}\pgfsys@beginscope \pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{0.0pt}{0.0pt} \pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{ 1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1} \pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}={\bm{u}}_{i}^{\top}{\bm{H}}_{\tilde{ \mathcal{B}}}{\bm{u}}_{i}={\bm{u}}_{i}^{\top}\left(\sum_{p=1}^{P}\tilde{ \lambda}_{p}\tilde{{\bm{u}}}_{p}\tilde{{\bm{u}}}_{p}^{\top}\right){\bm{u}}_{i} =\sum_{p=1}^{P}\tilde{\lambda}_{p}\underbracket{(\tilde{{\bm{u}}}_{p}^{\top}{ \bm{u}}_{i})^{2}}_{\eqqcolon{\bm{\Omega}}_{i,p}}=\sum_{p=1}^{P}\tilde{\lambda} _{p}\,{\bm{\Omega}}_{i,p}.$ $$

Weights sum up to one. The weights ${\bm{\Omega}}_{i,p}$ are non-negative and sum up
to one, i.e. $\sum_{p=1}^{P}{\bm{\Omega}}_{i,p}=1$. This is because

$$ $\sum_{p=1}^{P}{\bm{\Omega}}_{i,p}=\sum_{p=1}^{P}(\tilde{{\bm{u}}}_{p}^{\top}{ \bm{u}}_{i})^{2}=\|\tilde{{\bm{U}}}^{\top}{\bm{u}}_{i}\|_{2}^{2}={\bm{u}}_{i}^ {\top}\underbracket{\tilde{{\bm{U}}}\tilde{{\bm{U}}}^{\top}}_{={\bm{I}}}{\bm{u }}_{i}=\|{\bm{u}}_{i}\|_{2}^{2}=1$ (20) $$

where we used that $\tilde{{\bm{U}}}$ is an orthogonal matrix and that ${\bm{u}}_{i}$ is
normalized.

Proof of Equation 7. Here, we assume the simplified case
where the spectra of ${\bm{H}}_{\mathcal{B}}$ and ${\bm{H}}_{\tilde{\mathcal{B}}}$ are
identical, i.e. $\lambda_{p}=\tilde{\lambda}_{p}\,\forall p\in\{1,\ldots,P\}$.

First, consider ${\bm{u}}_{1}$ and assume that ${\bm{u}}_{1}$ and $\tilde{{\bm{u}}}_{1}$ are
not perfectly aligned, i.e. ${\bm{\Omega}}_{1,1}=({\bm{u}}_{1}^{\top}\tilde{{\bm{u}}}_{1})^{2}<1$. It holds

$$ $\underbracket{\partial^{2}_{{\bm{u}}_{1}}q({\bm{\theta}}_{0},\tilde{\mathcal{B }})}_{\leavevmode\hbox to3.96pt{\vbox to3.96pt{\pgfpicture\makeatletter\hbox{ \hskip 1.97989pt\lower-1.97989pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke { }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0} \pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ } \pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ } {{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{ tikz@color}{rgb}{1,1,1}\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{ rgb}{0.296875,0.4453125,0.69140625}\pgfsys@color@rgb@fill{0.296875}{0.4453125} {0.69140625}\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{tikz@color}{rgb}{1,1,1} \definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{ 1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ }\pgfsys@color@gray@fill{1} \pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{ 0.296875,0.4453125,0.69140625}\pgfsys@color@rgb@fill{0.296875}{0.4453125}{0.69 140625}\pgfsys@invoke{ }\pgfsys@moveto{1.97989pt}{0.0pt}\pgfsys@curveto{1.9798 9pt}{1.09348pt}{1.09348pt}{1.97989pt}{0.0pt}{1.97989pt}\pgfsys@curveto{-1.0934 8pt}{1.97989pt}{-1.97989pt}{1.09348pt}{-1.97989pt}{0.0pt}\pgfsys@curveto{-1.97 989pt}{-1.09348pt}{-1.09348pt}{-1.97989pt}{0.0pt}{-1.97989pt}\pgfsys@curveto{1 .09348pt}{-1.97989pt}{1.97989pt}{-1.09348pt}{1.97989pt}{0.0pt} \pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fill\pgfsys@invoke{ } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}{{{{}}\pgfsys@beginscope \pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{0.0pt}{0.0pt} \pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{ 1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1} \pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}\overset{\text{(\ref{eq:bias_curvature_ eigvecs})}}{=}\sum_{p=1}^{P}\lambda_{p}{\bm{\Omega}}_{1,p}=\lambda_{1}{\bm{ \Omega}}_{1,1}+\sum_{p=2}^{P}\lambda_{p}{\bm{\Omega}}_{1,p}.$ $$

The sum can be bounded from above by putting all remaining weight $1-{\bm{\Omega}}_{1,1}$
(see Equation 20) on the second-largest eigenvalue $\lambda_{2}$, i.e.

$$ $\underbracket{\partial^{2}_{{\bm{u}}_{1}}q({\bm{\theta}}_{0},\tilde{\mathcal{B }})}_{\leavevmode\hbox to3.96pt{\vbox to3.96pt{\pgfpicture\makeatletter\hbox{ \hskip 1.97989pt\lower-1.97989pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke { }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0} \pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ } \pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ } {{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{ tikz@color}{rgb}{1,1,1}\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{ rgb}{0.296875,0.4453125,0.69140625}\pgfsys@color@rgb@fill{0.296875}{0.4453125} {0.69140625}\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{tikz@color}{rgb}{1,1,1} \definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{ 1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ }\pgfsys@color@gray@fill{1} \pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{ 0.296875,0.4453125,0.69140625}\pgfsys@color@rgb@fill{0.296875}{0.4453125}{0.69 140625}\pgfsys@invoke{ }\pgfsys@moveto{1.97989pt}{0.0pt}\pgfsys@curveto{1.9798 9pt}{1.09348pt}{1.09348pt}{1.97989pt}{0.0pt}{1.97989pt}\pgfsys@curveto{-1.0934 8pt}{1.97989pt}{-1.97989pt}{1.09348pt}{-1.97989pt}{0.0pt}\pgfsys@curveto{-1.97 989pt}{-1.09348pt}{-1.09348pt}{-1.97989pt}{0.0pt}{-1.97989pt}\pgfsys@curveto{1 .09348pt}{-1.97989pt}{1.97989pt}{-1.09348pt}{1.97989pt}{0.0pt} \pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fill\pgfsys@invoke{ } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}{{{{}}\pgfsys@beginscope \pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{0.0pt}{0.0pt} \pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{ 1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1} \pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}\leq\lambda_{1}{\bm{\Omega}}_{1,1}+\lambda_{ 2}(1-{\bm{\Omega}}_{1,1})\overset{(*)}{\leq}\lambda_{1}{\bm{\Omega}}_{1,1}+ \lambda_{1}(1-{\bm{\Omega}}_{1,1})=\lambda_{1}=\underbracket{\partial^{2}_{{ \bm{u}}_{1}}q({\bm{\theta}}_{0},\mathcal{B})}_{\leavevmode\hbox to3.96pt{\vbox to 3.96pt{\pgfpicture\makeatletter\hbox{\hskip 1.97989pt\lower-1.97989pt\hbox to0 .0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{ 0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill {0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ } \nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{ tikz@color}{rgb}{1,1,1}\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{ rgb}{0.8671875,0.51953125,0.3203125}\pgfsys@color@rgb@fill{0.8671875}{0.519531 25}{0.3203125}\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{tikz@color}{rgb}{1,1,1} \definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{ 1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ }\pgfsys@color@gray@fill{1} \pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{ 0.8671875,0.51953125,0.3203125}\pgfsys@color@rgb@fill{0.8671875}{0.51953125}{0 .3203125}\pgfsys@invoke{ }\pgfsys@moveto{1.97989pt}{0.0pt}\pgfsys@curveto{1.97 989pt}{1.09348pt}{1.09348pt}{1.97989pt}{0.0pt}{1.97989pt}\pgfsys@curveto{-1.09 348pt}{1.97989pt}{-1.97989pt}{1.09348pt}{-1.97989pt}{0.0pt}\pgfsys@curveto{-1. 97989pt}{-1.09348pt}{-1.09348pt}{-1.97989pt}{0.0pt}{-1.97989pt}\pgfsys@curveto {1.09348pt}{-1.97989pt}{1.97989pt}{-1.09348pt}{1.97989pt}{0.0pt} \pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fill\pgfsys@invoke{ } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}{{{{}}\pgfsys@beginscope \pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{0.0pt}{0.0pt} \pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{ 1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1} \pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}\!.$ $$

The inequality $(*)$ turns into $<$ if the top two eigenvalues are separated, i.e. $\lambda_{1}>\lambda_{2}$.
The proof for ${\bm{u}}_{P}$ is similar. We assume that ${\bm{u}}_{P}$ and
$\tilde{{\bm{u}}}_{P}$ are not perfectly aligned, i.e. ${\bm{\Omega}}_{P,P}=({\bm{u}}_{P}^{\top}\tilde{{\bm{u}}}_{P})^{2}<1$.
It follows

$$ $\underbracket{\partial^{2}_{{\bm{u}}_{P}}q({\bm{\theta}}_{0},\tilde{\mathcal{B }})}_{\leavevmode\hbox to3.96pt{\vbox to3.96pt{\pgfpicture\makeatletter\hbox{ \hskip 1.97989pt\lower-1.97989pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke { }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0} \pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ } \pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ } {{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{ tikz@color}{rgb}{1,1,1}\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{ rgb}{0.296875,0.4453125,0.69140625}\pgfsys@color@rgb@fill{0.296875}{0.4453125} {0.69140625}\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{tikz@color}{rgb}{1,1,1} \definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{ 1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ }\pgfsys@color@gray@fill{1} \pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{ 0.296875,0.4453125,0.69140625}\pgfsys@color@rgb@fill{0.296875}{0.4453125}{0.69 140625}\pgfsys@invoke{ }\pgfsys@moveto{1.97989pt}{0.0pt}\pgfsys@curveto{1.9798 9pt}{1.09348pt}{1.09348pt}{1.97989pt}{0.0pt}{1.97989pt}\pgfsys@curveto{-1.0934 8pt}{1.97989pt}{-1.97989pt}{1.09348pt}{-1.97989pt}{0.0pt}\pgfsys@curveto{-1.97 989pt}{-1.09348pt}{-1.09348pt}{-1.97989pt}{0.0pt}{-1.97989pt}\pgfsys@curveto{1 .09348pt}{-1.97989pt}{1.97989pt}{-1.09348pt}{1.97989pt}{0.0pt} \pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fill\pgfsys@invoke{ } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}{{{{}}\pgfsys@beginscope \pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{0.0pt}{0.0pt} \pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{ 1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1} \pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}\overset{\text{(\ref{eq:bias_curvature_ eigvecs})}}{=}\sum_{p=1}^{P}\lambda_{p}{\bm{\Omega}}_{P,p}=\sum_{p=1}^{P-1} \lambda_{p}{\bm{\Omega}}_{P,p}+\lambda_{P}{\bm{\Omega}}_{P,P}.$ $$

This time, we bound the sum from below by putting all remaining weight $1-{\bm{\Omega}}_{P,P}$ (see Equation 20) on the second-smallest eigenvalue $\lambda_{P-1}$, i.e.

$$ $\underbracket{\partial^{2}_{{\bm{u}}_{P}}q({\bm{\theta}}_{0},\tilde{\mathcal{B }})}_{\leavevmode\hbox to3.96pt{\vbox to3.96pt{\pgfpicture\makeatletter\hbox{ \hskip 1.97989pt\lower-1.97989pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke { }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0} \pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ } \pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ } {{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{ tikz@color}{rgb}{1,1,1}\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{ rgb}{0.296875,0.4453125,0.69140625}\pgfsys@color@rgb@fill{0.296875}{0.4453125} {0.69140625}\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{tikz@color}{rgb}{1,1,1} \definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{ 1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ }\pgfsys@color@gray@fill{1} \pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{ 0.296875,0.4453125,0.69140625}\pgfsys@color@rgb@fill{0.296875}{0.4453125}{0.69 140625}\pgfsys@invoke{ }\pgfsys@moveto{1.97989pt}{0.0pt}\pgfsys@curveto{1.9798 9pt}{1.09348pt}{1.09348pt}{1.97989pt}{0.0pt}{1.97989pt}\pgfsys@curveto{-1.0934 8pt}{1.97989pt}{-1.97989pt}{1.09348pt}{-1.97989pt}{0.0pt}\pgfsys@curveto{-1.97 989pt}{-1.09348pt}{-1.09348pt}{-1.97989pt}{0.0pt}{-1.97989pt}\pgfsys@curveto{1 .09348pt}{-1.97989pt}{1.97989pt}{-1.09348pt}{1.97989pt}{0.0pt} \pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fill\pgfsys@invoke{ } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}{{{{}}\pgfsys@beginscope \pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{0.0pt}{0.0pt} \pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{ 1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1} \pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}\geq\lambda_{P-1}(1-{\bm{\Omega}}_{P,P})+ \lambda_{P}{\bm{\Omega}}_{P,P}\overset{(*)}{\geq}\lambda_{P}(1-{\bm{\Omega}}_{ P,P})+\lambda_{P}{\bm{\Omega}}_{P,P}=\lambda_{P}=\underbracket{\partial^{2}_{{ \bm{u}}_{P}}q({\bm{\theta}}_{0},\mathcal{B})}_{\leavevmode\hbox to3.96pt{\vbox to 3.96pt{\pgfpicture\makeatletter\hbox{\hskip 1.97989pt\lower-1.97989pt\hbox to0 .0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{ 0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill {0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ } \nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{ tikz@color}{rgb}{1,1,1}\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{ rgb}{0.8671875,0.51953125,0.3203125}\pgfsys@color@rgb@fill{0.8671875}{0.519531 25}{0.3203125}\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{tikz@color}{rgb}{1,1,1} \definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{ 1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ }\pgfsys@color@gray@fill{1} \pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{ 0.8671875,0.51953125,0.3203125}\pgfsys@color@rgb@fill{0.8671875}{0.51953125}{0 .3203125}\pgfsys@invoke{ }\pgfsys@moveto{1.97989pt}{0.0pt}\pgfsys@curveto{1.97 989pt}{1.09348pt}{1.09348pt}{1.97989pt}{0.0pt}{1.97989pt}\pgfsys@curveto{-1.09 348pt}{1.97989pt}{-1.97989pt}{1.09348pt}{-1.97989pt}{0.0pt}\pgfsys@curveto{-1. 97989pt}{-1.09348pt}{-1.09348pt}{-1.97989pt}{0.0pt}{-1.97989pt}\pgfsys@curveto {1.09348pt}{-1.97989pt}{1.97989pt}{-1.09348pt}{1.97989pt}{0.0pt} \pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fill\pgfsys@invoke{ } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}{{{{}}\pgfsys@beginscope \pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{0.0pt}{0.0pt} \pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{ pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{ } \pgfsys@color@gray@fill{1}\pgfsys@invoke{ }\hbox{{\definecolor[named]{.}{rgb}{ 1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1} \pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}\!.$ $$

Again, the inequality $(*)$ turns into $>$ if the bottom two eigenvalues are separated,
i.e. $\lambda_{P-1}>\lambda_{P}$. This concludes the proof of
Equation 7. ∎

## Appendix B Experimental details

In the following, we provide information on the experimental setup and give detailed
instructions on how to replicate all empirical results.

### B.1 Test problems and training procedures

Throughout the paper, we use a series of test problems with different models, datasets,
and training procedures which we describe in more detail in the following. We use
DeepOBS (Schneider et al., ) on top of PyTorch (Paszke et al., ) as
our general benchmarking framework as it provides easy access to a variety of datasets and model architectures.

Data. We use the datasets CIFAR-10 (with $C=10$ classes) and
CIFAR-100 (with $C=100$ classes) (Krizhevsky, ). Each
dataset contains $60000$ data points that are split into $40000$ training
samples, $10000$ validation samples and $10000$ test samples. For the
experiments on out-of-distribution (OOD) data, we create the datasets CIFAR-10-C and
CIFAR-100-C, each containing $10000$ images, as described in
(Hendrycks & Dietterich, ). In these datasets, each image is corrupted using one
out of $15$ different corruptions (chosen uniformly at random) at a specific severity
level (a number between $1$ and $5$). We also use the ImageNet dataset (Deng et al., ) which contains images from $C=1000$ different
classes.

Test problems. All of the following test problems use the cross-entropy loss
function.

- (A)
All-CNN-C on CIFAR-100. This test problem
uses the All-CNN-C model architecture (Springenberg et al., ) (where we
removed the dropout layers as explained in Section 3.1) and
CIFAR-100 data. The training hyperparameters are taken from an existing benchmark
(Schmidt et al., ): We train the model with SGD (learning rate $0.171234$)
with batch size $256$ for $350$ epochs. Weight decay $\beta=0.0005$ is used on the
weights but not the biases of the model.
- (B)
All-CNN-C on CIFAR-10. This test problem is
similar to (A) but uses the CIFAR-10 dataset. The model is
trained with SGD (learning rate $0.025$, momentum $0.9$) with batch size $256$ for
$350$ epochs. The learning rate is reduced by a factor of $10$ at epochs $200$, $250$
and $300$, as suggested in (Springenberg et al., ). Weight decay $\beta=0.001$ is used on the weights but not the biases of the model.
- (C)
WideResNet 40-4 on CIFAR-100. This is a test problem
from DeepOBS. For details on the architecture, see (Zagoruyko & Komodakis, ). We
train this model with SGD (learning rate $0.1$, momentum $0.9$) with batch size $128$
for $160$ epochs. The learning rate is reduced by a factor of $5$ after $60$ and $120$
epochs. Weight decay $\beta=0.0005$ is used on the non-bias weights of the model.
- (D)
ConvNet on CIFAR-10. This test problem uses
a simple convolutional neural network with variable depth $d$ and width $w$ (denoted
by “model $d$-$w$” in Figures 7 and 19). The
first block of the model consists of a convolutional layer (kernel size $5$,
padding $2$) with $3$ input and $w$ output channels, a ReLU activation function, and a
max-pooling layer (kernel size $2$). The last block consists of a max-pooling
layer (kernel size $2$), a flatten layer, and a dense linear layer. In between those
blocks, there are $d$ hidden blocks each consisting of a convolutional layer
(kernel size $5$, padding $2$) with $w$ input and $w$ output channels followed by a
ReLU activation function. So, the depth $d$ determines the number of hidden blocks,
whereas $w$ controls the number of parameters in the layers and is thus referred to as
the width.
We use $d\in\{1,4,7\}$ and $w\in\{32,64,128\}$ (resulting in $9$ models) and
train each model for $100$ epochs on the CIFAR-10 dataset using Adam with standard
hyperparameters (learning rate $0.001$, $\beta_{1}=0.9$, $\beta_{2}=0.999$, $\epsilon=10^{-8}$) with batch size $256$. No weight decay is used for this test problem.
- (E)
ResNet-50 on ImageNet. This
test problem uses the ResNet-50 model architecture (He et al., ) and the
ImageNet dataset. We use the [IMAGENET1K_V1](https://download.pytorch.org/models/resnet50-19c8e357.pth)
weights pre-trained on ImageNet-1k using SGD (initial learning rate $0.1$, momentum $0.9$)
with batch size $256$ for $90$ epochs. For the pre-training, the learning rate was set by a multistep scheduler
which multiplied the learning rate by a factor of $0.1$ after
every $30$ epochs. Additionally, a weight decay of $\beta=0.0001$ was used on all weights apart from
biases and the learned batch normalization weights.

During training, we store the model’s parameters at $10$ checkpoints spaced
log-equidistantly between the first and last epoch. The training metrics for all
test problems are shown in Figure 7.

Figure: Figure 7: Training metrics for all test problems. The panels show the training/test loss/accuracy during training for all test problems (A) (All-CNN-C on CIFAR-100), (B) (All-CNN-C on CIFAR-10), (C) (WideResNet 40-4 on CIFAR-100) and (D) (ConvNet on CIFAR-10). Test problem (E) (ResNet-50 on ImageNet) is not shown since a pre-trained model is used here.
Refer to caption: x7.png

### B.2 Matrix-vector products with the curvature matrix

Access to curvature matrices via BackPACK. In order to
compute an
eigendecomposition of the curvature matrix or apply the CG method to a quadratic, we
need access to matrix-vector products with the curvature matrix ${\bm{v}}\mapsto{\bm{H}}_{\mathcal{B}}\cdot{\bm{v}}$. When products with the full-batch curvature matrix are
required, we accumulate the mini-batch quantities over manageable chunks of the
training set.
Our implementation uses BackPACK (Dangel et al., ) that provides access to
products with the Hessian ${\bm{v}}\mapsto\nabla^{2}\mathcal{L}({\bm{\theta}};\mathcal{B})\cdot{\bm{v}}$
and GGN ${\bm{v}}\mapsto{\bm{G}}_{\mathcal{B}}\cdot{\bm{v}}$ of the empirical risk $\mathcal{L}$ as well as
the K-FAC curvature approximation ${\bm{K}}_{\mathcal{B}}$.

Eigenvectors of the curvature matrix. Given access to matrix-vector products
with the curvature matrix, we can construct an instance of a
scipy.sparse.linalg.LinearOperator that can be used in
scipy.sparse.linalg.eigsh.

### B.3 Section 1 ( Introduction ): Figure 1

For the visual abstract in Figure 1, we use the fully trained All-CNN-C model from test problem (A) (see Section B.1).
The experimental procedure below is repeated for $5$ different mini-batches
$\mathcal{B}_{m}$, $m\in\{0,1,2,3,4\}$ of size $|\mathcal{B}_{m}|=512$ (we
omit the index $m$ in the following).

Experimental procedure. We use the GGN curvature proxy ${\bm{H}}_{\mathcal{B}}\leftarrow{\bm{G}}_{\mathcal{B}}+\beta{\bm{I}}$ and compute its top two eigenvectors ${\bm{u}}_{1}$ and
${\bm{u}}_{2}$ (see Section B.2). In order to evaluate the quadratic $q({\bm{\theta}}_{\star};\mathcal{B})$ in the 2D space
spanned by those eigenvectors efficiently, we use the following equation:

$$ $\displaystyle q({\bm{\theta}}_{\star}+\tau_{1}{\bm{u}}_{1}+\tau_{2}{\bm{u}}_{2 };\mathcal{B})$ $\displaystyle=\frac{1}{2}\tau_{1}^{2}[{\bm{u}}_{1}^{\top}{\bm{H}}_{\mathcal{B} }\,{\bm{u}}_{1}]+\tau_{1}\tau_{2}[{\bm{u}}_{1}^{\top}{\bm{H}}_{\mathcal{B}}\,{ \bm{u}}_{2}]+\frac{1}{2}\tau_{2}^{2}[{\bm{u}}_{2}^{\top}{\bm{H}}_{\mathcal{B}} \,{\bm{u}}_{2}]$ $\displaystyle\;\;\;\;+\tau_{1}[{\bm{u}}_{1}^{\top}{\bm{g}}_{\mathcal{B}}]+\tau _{2}[{\bm{u}}_{2}^{\top}{\bm{g}}_{\mathcal{B}}]+[c_{\mathcal{B}}].$ $$

We can compute all the terms on the right-hand side in brackets once, store
them, and then evaluate the quadratic for arbitrary values of $\tau_{1}$ and $\tau_{2}$ at
basically no cost. The derivation for the full-batch quadratic $q({\bm{\theta}}_{\star}+\tau_{1}{\bm{u}}_{1}+\tau_{2}{\bm{u}}_{2};\mathcal{D})$ is analogous.

### B.4 Section 3 ( The shape of a mini-batch quadratic ): Figures 2 , 4 and 4

For the evaluation of the directional derivatives, we use the fully trained All-CNN-C model from test problem (A) (see Section B.1).

Three settings. Throughout this section, we consider three
different settings: (i) Quadratics that use the Hessian of the empirical risk, i.e. ${\bm{H}}_{\mathcal{B}}\leftarrow\nabla^{2}\mathcal{L}({\bm{\theta}}_{\star};
\mathcal{B})+\beta{\bm{I}}$ at batch
size $512$, (ii) quadratics that use the Hessian’s GGN approximation, i.e. ${\bm{H}}_{\mathcal{B}}\leftarrow{\bm{G}}_{\mathcal{B}}+\beta{\bm{I}}$ at batch size $512$ and
(iii) at batch size $2048$. For each setting, the experimental procedure below is
repeated for $3$ mini-batches $\mathcal{B}_{m}$, $m\in\{0,1,2\}$. The prior precision
$\beta$ is set to $0.0005$ (the same $\beta$ was used for training, see
Section B.1) and only acts on the weights of the model but not its
biases.

Experimental procedure (biases). The experimental procedure consists of two
steps: The computations of the directions on mini-batch $\mathcal{B}_{m}$ and the
evaluation of the directional derivatives on all mini-batches (of the same
size) in the training dataset.

- 1.
Directions based on $\mathcal{B}_{m}$. First, we use the quadratic
$q({\bm{\theta}}_{\star};\mathcal{B}_{m})$ with the given curvature proxy and batch size
to compute a set of $100$ directions. This is either the top $100$ eigenvectors of
${\bm{H}}_{\mathcal{B}}$ computed via scipy.sparse.linalg.eigsh (see
Section B.2) or the first $100$ CG search directions
(see Section B.5). In the case of CG, we also store the trajectory of
the iterates ${\bm{\theta}}_{\star}={\bm{\theta}}_{0},{\bm{\theta}}_{1},\ldots,{\bm{\theta}}
_{100}$.
- 2.
Directional derivatives on all mini-batches. Finally, we evaluate the
directional slope and curvature for all directions from step 1 on all
mini-batches $\mathcal{B}_{m^{\prime}}$, $m^{\prime}\in\{0,\dots,M-1\}$ in the
training dataset (where $M$ denotes the number of mini-batches in the
training data).
•
Directional derivatives along eigenvectors. For an eigenvector
${\bm{u}}$ the directional slope and curvature are given by $\partial_{{\bm{u}}}\,q({\bm{\theta}}_{\star};\mathcal{B}_{m^{\prime}})$ and $\partial^{2}_{{\bm{u}}}\,q({\bm{\theta}}_{\star};\mathcal{B}_{m^{\prime}})$, respectively.
•
Directional derivatives along CG search directions. For CG, we
evaluate the directional slope and curvature along each search direction ${\bm{d}}_{p}$ at
the respective iterate ${\bm{\theta}}_{p}$ of the trajectory,
i.e. $\partial_{{\bm{d}}_{p}}\,q({\bm{\theta}}_{p};\mathcal{B}_{m^{\prime}})$ for the slope and
$\partial^{2}_{{\bm{d}}_{p}}\,q({\bm{\theta}}_{p};\mathcal{B}_{m^{\prime}})$ for the curvature. As the
curvature $\nabla^{2}q({\bm{\theta}};\mathcal{B}_{m^{\prime}})\equiv{\bm{H}}_{\mathcal{B}
_{m^{\prime}}}$ is independent of ${\bm{\theta}}$, this small distinction is
irrelevant for the directional curvature. For the directional slope, however, it
does make a difference.

Results (biases). The results for setting (i) are shown in
Figure 8, for setting (ii) in Figures 2 and 9 and
for (iii) in Figure 10.
The biases in the directional slopes and curvatures can be observed across all
scenarios. The biases in the slopes are even
more pronounced along the CG search directions
than along the eigenvectors of the curvature matrix. The opposite holds for the
curvature biases that tend to be larger along the eigenvectors. This is consistent with
our explanations from Section 3.2.
Both the biases in the slope and curvature decrease with increasing mini-batch size. For
setting (i), CG encounters a search direction with negative curvature (indicating that,
as expected, the curvature matrix ${\bm{H}}_{\mathcal{B}}$ is indefinite) and thus
terminates already after $4$ iterations.

Figure: Figure 8: Directional slopes and curvatures are biased. The experimental setting is similar to Figure 2 but uses the Hessian of the empirical risk, i.e. ${\bm{H}}_{\mathcal{B}}\leftarrow\nabla^{2}\mathcal{L}({\bm{\theta}}_{\star}; \mathcal{B})+\beta{\bm{I}}$ at batch size $512$. The upper plot (Top) shows the directional derivatives along the top $100$ eigenvectors of ${\bm{H}}_{\mathcal{B}}$, the lower plot (Bottom) shows the directional derivatives along the first $100$ CG search directions. For the top panel of the upper plot, we switch the order and sign of the eigenvectors such that the orange dots are all above zero and in descending order. There are strong systematic biases in the directional slopes and curvatures. The curvature biases are more pronounced along the eigenvectors, whereas the biases in the slope are larger along the CG directions.
Refer to caption: x11.png

Figure: Figure 9: Directional slopes and curvatures are biased. The experimental setting is the same as in Figure 2: We use the GGN curvature proxy ${\bm{H}}_{\mathcal{B}}\leftarrow{\bm{G}}_{\mathcal{B}}+\beta{\bm{I}}$ at batch size $512$. The upper plot (Top) shows the directional derivatives along the top $100$ eigenvectors of ${\bm{H}}_{\mathcal{B}}$, the lower plot (Bottom) shows the directional derivatives along the first $100$ CG search directions. For the top panel of the upper plot, we switch the order and sign of the eigenvectors such that the orange dots are all above zero and in descending order. There are strong systematic biases in the directional slopes and curvatures. The curvature biases are more pronounced along the eigenvectors, whereas the biases in the slope are larger along the CG directions.
Refer to caption: x13.png

Figure: Figure 10: Directional slopes and curvatures are biased. The experimental setting is similar to Figure 2: We use the GGN curvature proxy ${\bm{H}}_{\mathcal{B}}\leftarrow{\bm{G}}_{\mathcal{B}}+\beta{\bm{I}}$ but batch size $2048$. The upper plot (Top) shows the directional derivatives along the top $100$ eigenvectors of ${\bm{H}}_{\mathcal{B}}$, the lower plot (Bottom) shows the directional derivatives along the first $100$ CG search directions. For the top panel of the upper plot, we switch the order and sign of the eigenvectors such that the orange dots are all above zero and in descending order. There are strong systematic biases in the directional slopes and curvatures. The curvature biases are more pronounced along the eigenvectors, whereas the biases in the slope are larger along the CG directions.
Refer to caption: x15.png

Experimental procedure (overlaps). Next, we compute the overlaps between the
eigenspaces of the curvature matrices on different mini-batches $\mathcal{B}$ and
$\tilde{\mathcal{B}}$. More specifically, we compute ${\bm{\Omega}}_{i,p}=({\bm{u}}_{i}^{\top}\tilde{{\bm{u}}}_{p})^{2}$, where $i,p\in\{1,\dots,100\}$, ${\bm{u}}_{i}$ is an eigenvector
of ${\bm{H}}_{\mathcal{B}}$ and $\tilde{{\bm{u}}}_{p}$ is an eigenvector of
${\bm{H}}_{\tilde{\mathcal{B}}}$. The values ${\bm{\Omega}}_{i,p}$ are bounded between 0 0
(${\bm{u}}_{i}$ and $\tilde{{\bm{u}}}_{p}$ are orthogonal) and $1$ (${\bm{u}}_{i}$ and $\tilde{{\bm{u}}}_{p}$ are identical, up to their sign). We apply a log-transform to
${\bm{\Omega}}_{i,p}$. In Figures 4 and 11, values below $-8$ (i.e. ${\bm{\Omega}}_{i,p}\leq 10^{-8}$) are shown in black, values equal to 0 0 (i.e. ${\bm{\Omega}}_{i,p}=10^{0}=1$) are shown in white.

Results (overlaps). The results are shown in Figure 11.
They show that the eigenspaces of the curvature matrices are not perfectly aligned:
Eigenvectors from $\mathcal{B}_{m}$ typically overlap with several eigenvectors from
$\tilde{\mathcal{B}}$. The eigenspaces are more aligned at the larger batch size $2048$ than
at batch size $512$. This seems reasonable since random vectors in high-dimensional
spaces tend to be orthogonal to each other —less stochasticity (due to a larger batch
size) thus leads to better alignment.

Figure: Figure 11: In practice, eigenspaces are misaligned. The experimental setting is similar to Figure 4. The top plot shows overlaps between three curvature matrices that use the Hessian of the empirical risk, i.e. ${\bm{H}}_{\mathcal{B}}\leftarrow\nabla^{2}\mathcal{L}({\bm{\theta}}_{\star}; \mathcal{B})+\beta{\bm{I}}$ at batch size $512$. The bottom plots use the GGN curvature proxy ${\bm{H}}_{\mathcal{B}}\leftarrow{\bm{G}}_{\mathcal{B}}+\beta{\bm{I}}$ at batch size $512$ (Left) and $2048$ (Right). The weights ${\bm{\Omega}}_{i,j}$ are shown as a $100\times 100$ greyscale image (color ranges from black for ${\bm{\Omega}}_{i,j}\leq 10^{-8}$ to white for ${\bm{\Omega}}_{i,j}=1$) for $m,m^{\prime}\in\{0,1,2\}$. Clearly, the eigenspaces for different mini-batches are not perfectly aligned as eigenvectors from $\mathcal{B}_{m}$ overlap with several eigenvectors from $\mathcal{B}_{m^{\prime}}$. At the larger batch size, the eigenspaces are more aligned.
Refer to caption: x17.png

### B.5 Section 6.1 ( Debiased conjugate gradients ): Figure 5

Here, we describe the experimental details for Figure 5 from Section 6.1. For
the derivation and the mathematical details of the standard single-batch CG method and
the debiased approach, see Section A.2. The experiment uses the fully trained
All-CNN-C model from test problem (A) (see
Section B.1) and the GGN curvature proxy ${\bm{H}}_{\mathcal{B}}\leftarrow{\bm{G}}_{\mathcal{B}}+\beta{\bm{I}}$ with $\beta=0.0005$.

Experimental procedure. The experimental procedure consists of two steps: The
computation of the CG trajectories and the evaluation of the four performance metrics.

- 1.
Computation of the CG trajectories. For the single-batch CG approach,
we use one mini-batch of size $1024$, apply $K=30$ CG iterations and
store the trajectory ${\bm{\theta}}_{\star}={\bm{\theta}}_{0},{\bm{\theta}}_{1},\ldots,{\bm{\theta}}
_{30}$. For
the debiased approach (details in Section A.2), we use two mini-batches of
size $512$ to construct the trajectory. As the debiased approach uses a total of
$60$ GGN-vector products ($30$ for the search directions and $30$ for the update
magnitudes) at half the computational cost (since the cost for the GGN-vector
product scales linearly with the mini-batch size), the total cost of both approaches
are comparable.
For both approaches, the above procedure is repeated for $5$ different
mini-batches/mini-batch pairs, such that $10$ trajectories are computed in total.
We compute two additional trajectories: The standard CG trajectory for the
full-batch quadratic $q(\,\cdot\,;\mathcal{D})$ and the trajectory for a
debiased full-batch approach, where we use half the training data for the directions
and the other half for the update magnitudes.
- 2.
Evaluation of performance metrics. For each of the $12$ trajectories,
we evaluate four performance metrics: (i) the regularized loss $\mathcal{L}_{\text{reg}}$ (see
Equation 1) on the training set $\mathcal{D}$ and (ii) on the test set
$\mathcal{D}_{\text{test}}$ as well as the accuracy (i.e. the relative number of correctly classified
samples) on the (iii) training and (iv) test dataset.

Results. The mini-batch results are shown in Figure 5 and discussed in
Section 6.1.
The results for the two full-batch CG variants are shown in Figure 12.
Surprisingly, the full-batch CG approach diverges after roughly $10$ iterations. If we
consider the training data as a (large) sample from the data distribution, the
full-batch CG approach can be seen as an instance of the mini-batch approach with a
very large mini-batch size. Thus, it might also exhibit the associated biases we
describe in Section 3.2. Another explanation would be the approximation
error in Equation 2: $\mathcal{L}_{\text{reg}}(\,\cdot\,;\mathcal{D})\;\approx\;q(\,\cdot\,;\mathcal
{D})$. If the trajectory moves far away from ${\bm{\theta}}_{\star}$,
it leaves the region where the approximation is valid (whereas the debiased full-batch
version might take smaller steps and thus remains stable). We leave it to future work to
investigate this further.

Figure: Figure 12: Comparison of full-batch CG approaches. We use the setting from Figure 5. The full-batch approach (shown as ) applies standard CG to $q(\,\cdot\,;\mathcal{D})$ while the debiased approach (shown as ) uses one half of the training data for the directions and the other half for the update magnitudes. The markers ◆ and ◆ are placed at peak performance. Surprisingly, the full-batch run diverges. The debiased CG run is stable.
Refer to caption: x20.png

### B.6 Section 6.2 ( Debiased Laplace approximation ): Figure 6

Figure 6 shows a comparison of the vanilla model, the mini-batch K-FAC LA, the
debiased version, and the full-batch LA. Here, we describe the experiment in more detail
and present additional results, in particular on OOD data. For the derivation and the
mathematical details of these approaches, see Section A.3.
The experiment uses the fully trained All-CNN-C model on CIFAR-10 data from test problem
(B) (see Section B.1).

Experimental procedure. The experimental procedure consists of three steps: The
computation of the K-FAC curvature approximations, the evaluation of the corresponding
predictive class probabilities, and the computation of the performance metrics.

- 1.
K-FAC curvature approximations. We consider a log-equidistant grid of
$13$ prior precisions $\beta$ between $10^{-4}$ and $10^{0}$ and add $\beta=10$.
For each of those $14$ values, we compute the K-FAC curvature approximation via
BackPACK (Dangel et al., ) (see Section B.2)
using (i) a single batch of size $64$, $256$, and $1024$, (ii) the two-batch
debiased LA version (details in Section A.3.3) at batch sizes
$32$, $128$, and $512$, and (iii) the full-batch LA. For the latter, we accumulate
mini-batch K-FAC approximations over the entire training set. As an additional
baseline, we consider (iv) the vanilla model (without LA), which is independent of the
prior precision $\beta$. For approaches (i) and (ii), we repeat the experiment for $5$
different mini-batches/mini-batch pairs.
- 2.
Evaluation of predictive class probabilities. The first step in the
evaluation of the performance metrics is the computation of the predictive
uncertainty. For a given test dataset of size $N_{\diamond}$, these can be
represented as a matrix ${\bm{P}}\in\mathbb{R}^{N_{\diamond}\times C}$, where ${\bm{P}}_{n,c}$ is the probability that the $n$-th sample belongs to class $c$, i.e. rows of ${\bm{P}}$
sum to $1$. In all experiments, we draw $S=40$ MC
samples $\{{\bm{\theta}}^{(s)}\}_{s=1}^{S}$ from the weight posterior following the procedure in
Section A.3.2. The predictive class probabilities
are then obtained via Equation 18. In the case of the vanilla model
without LA, the sum in Equation 18 collapses to a single term
corresponding to the MAP model.
The evaluation procedure above can be applied to arbitrary test datasets. We consider
the training data, test data and CIFAR-10-C (i.e. OOD datasets at severity $1$ to
$5$).
- 3.
Performance metrics. We consider the following performance metrics:
•
Accuracy. The predictive classes are obtained from ${\bm{P}}$ by
extracting the class with the highest probability. The accuracy is the relative
number of correctly classified samples.
•
Negative log-likelihood (NLL). For each datum in the test set, we
compute the negative log-probability of the true class. We then average over all
samples in the test dataset. This coincides with the empirical risk from
Equation 1, evaluated on the test dataset.
•
Expected calibration error (ECE). The ECE is a measure of the
calibration of the model’s predictive probabilities. It groups the classification
confidences (i.e. the maximum entry in each of ${\bm{P}}$’s rows) into bins, and within
these bins, compares the average confidence with the actual accuracy. We use
MulticlassCalibrationError from torchmetrics
(Detlefsen et al., ).
•
AUROC. For the OOD datasets, we provide the Area Under the Receiver
Operating Characteristic curve (AUROC). Our goal is to distinguish in-distribution
(ID) and out-of-distribution (OOD) samples using the model’s uncertainty. We use the
entropy of the predictive distribution $p({\bm{y}}_{\diamond}\mid{\bm{x}}_{\diamond},{\mathbb{D}})$ as our uncertainty estimate $u({\bm{x}}_{\diamond})\in\mathbb{R}$ for input
${\bm{x}}_{\diamond}$. The ground-truth binary labels are the ID/OOD indicators of the
test inputs. Several thresholds $\xi$ could be established to turn the scalar
uncertainty estimates into binary predictions by using
$\mathbf{1}_{\{u({\bm{x}}_{\diamond})>\xi\}}$. Instead of choosing a particular
threshold and evaluating its accuracy, the AUROC metric directly evaluates
$u(\,\cdot\,)$ by measuring the area under the plot of the true positive rate (TPR)
against the false positive rate (FPR) for all possible thresholds.

Additional experimental details.

- •
Uncertainty over weights but not biases. As the prior acts only on the
weights of the network but not its biases (see Section B.1), we
only consider the uncertainty over the weights in the LA. This slightly reduces the
size of the covariance matrix as it excludes the bias parameters.
- •
Single vs. double precision. Although the K-FAC factors are positive
semi-definite by construction, their numerical eigenvalues can be negative due to
numerical inaccuracies. To balance precision and computational cost, we use double
precision for all computations until drawing the MC samples and single precision afterwards.

Results. The results are presented in
Figures 6, 13 and 14. For the
single-batch and debiased approach (where we use $5$ mini-batches/mini-batch pairs
each), we report the average performance as a dot and the min/max as a vertical line.
The performance of the vanilla model is shown as a horizontal line as its performance
does not depend on $\beta$, as explained above.

Across all datasets and performance metrics, the debiased LA mimics the behavior of the
full-batch approach much better than the single-batch LA (although both approaches use a
comparable amount of computational resources). In particular, for small prior
precisions, where the covariance matrix relies almost exclusively on the K-FAC curvature
information, the debiased LA maintains a good performance in contrast to the
single-batch approach.

Figure: Figure 13: Debiased LA mimics the full-batch LA very well. The experimental setting is the same as in Figure 6, but we report results on additional datasets (training set and OOD datasets at severity level $1$ and $2$). For the OOD datasets, we report the AUROC metric in addition to the accuracy, NLL and ECE. In contrast to the single-batch approach, the debiased version mimics the behavior of the full-batch approach very well over the entire range of prior precisions and across datasets.
Refer to caption: x21.png

Figure: Figure 14: Debiased LA mimics the full-batch LA very well. The experimental setting is the same as in Figure 6, but we report results on additional datasets (OOD datasets at severity level $3$, $4$, and $5$). We report the AUROC metric in addition to the accuracy, NLL, and ECE. In contrast to the single-batch approach, the debiased version mimics the behavior of the full-batch approach very well over the entire range of prior precisions and across datasets.
Refer to caption: x24.png

Additional results: ResNet-50 on ImageNet. To showcase the
scalability of our debiased LA approach, we repeat the experiment for a ResNet-50 model on the ImageNet dataset (test problem (E) in
Section B.1). The results are shown in
Figure 15. Again, the debiased approach behaves similarly to
the full-batch LA and maintains stability over the entire spectrum of prior precisions.

Figure: Figure 15: Our approach scales to ResNet-50 on ImageNet. The experimental setting is the same as in Figure 6, but we use test problem (E) (see Section B.1) (ResNet-50 on ImageNet). The results are consistent with the findings on CIFAR-100: The debiased approach behaves similarly to the full-batch LA and maintains stability even for small prior precisions.
Refer to caption: x27.png

### B.7 Additional experiment: Biases for a WideResNet 40-4 model
architecture

Experimental setting and results. Here, we extend our analysis from
Section 3.1 (details in Section B.4) to test problem
(C) (see Section B.1): A Wide ResNet model
on CIFAR-100. We use the GGN curvature proxy ${\bm{H}}_{\mathcal{B}}\leftarrow{\bm{G}}_{\mathcal{B}}+\beta{\bm{I}}$ at batch size $256$ and compute the directional slopes and curvatures along
the top $100$ eigenvectors of ${\bm{H}}_{\mathcal{B}}$. The results are shown in
Figure 16. Along the first few top-curvature directions, the curvature
biases are even larger for this test problem than for the All-CNN-C model on CIFAR-100,
but then they decay more quickly.

Figure: Figure 16: Directional slopes and curvatures are biased. The experimental setting is similar to Figure 2, but we use test problem (C) (Wide ResNet on CIFAR-100) with the GGN curvature proxy ${\bm{H}}_{\mathcal{B}}\leftarrow{\bm{G}}_{\mathcal{B}}+\beta{\bm{I}}$ at batch size $256$. For the top panel, we switch the order and sign of the eigenvectors such that the orange dots are all above zero and in descending order. There is a strong, systematic bias, particularly in the curvature: Computing the eigenvectors and directional curvatures on the same data results in over-estimation that is very pronounced along the first few eigenvectors but then decays more quickly than in test problem (A).
Refer to caption: x28.png

### B.8 Additional experiment: K-FAC and the dependence of the biases on mini-batch size

Experimental setting. Here, we extend our analysis of
test problem
(A) (see Section B.1) from
Section 3.1 to K-FAC and investigate the impact of the mini-batch size
on the curvature biases.

Figure: Figure 17: Directional curvatures with K-FAC. We use the CIFAR-100 dataset with the fully trained All-CNN-C model. For each mini-batch size $\in\{8,32,128,512\}$, we draw one mini-batch and compute the top $100$ eigenvectors ${\bm{u}}_{1},\ldots,{\bm{u}}_{100}$ of the K-FAC matrix ${\bm{K}}_{\mathcal{B}_{0}}$. We show the directional curvatures ${\bm{u}}_{p}^{\top}{\bm{K}}_{\mathcal{B}_{m}}{\bm{u}}_{p}$, $p\in\{1,\ldots,100\}$ on the same mini-batch ($m=0$) as , all other mini-batches in the training set ($m\in\{1,2,\ldots\}$) as and their average as ✚. Similar to Figure 2, we observe a systematic bias in the curvature. The bias decreases with increasing mini-batch size.
Refer to caption: extracted/5933955/exp11/kfac.png

Results & discussion.
Figure 17 shows the directional curvatures of the K-FAC approximation for four
different mini-batch sizes. When we compute the eigenvectors and directional curvatures
on the same mini-batch, we observe a systematic curvature bias that decreases with
increasing mini-batch size.
There are two phenomena at play: With increasing mini-batch size, (i) the green crosses
move upwards and (ii) the orange dots move downwards. Our intuition for this is as
follows: With increasing mini-batch size, the eigenvectors become more meaningful such
that, on other data, they also exhibit large curvature—this explains (i). Similarly,
with increasing mini-batch size, it gets harder to find directions of extreme
curvature as these directions have to exhibit large curvature on all data
points within the mini-batch—this explains (ii).

### B.9 Additional experiment: Development of the biases over the course of training

Experimental setting and results. Here, we investigate how the biases in the
slope and curvature develop over the course of training for test problem
(A) (see Section B.1). We use the same
procedure as in Section B.4 but evaluate the biases at $10$ different
checkpoints during training (spread log-equidistantly between the first and last epoch).
At each checkpoint, we draw $5$ mini-batches, compute the top $100$ eigenvectors of the
corresponding GGN-based quadratics, and finally evaluate the relative errors in
the directional slopes and curvatures (where the ground truth is the full-batch
quadratic’s slope/curvature). For each mini-batch, this distribution of $100$ relative
curvature and slope biases is represented as a dot (at the mean relative bias) and a
vertical line ranging from the $25\%$ to the $75\%$ percentile in
Figure 18.
While the biases in the slope remain relatively stable over the course of
training, the
biases in the curvature increase over more than $3$ orders of magnitude up to a relative
error of order $10$ in epoch $349$ (which is consistent with the results in
Figure 2). This suggests that the eigenspaces of different curvature matrices
become more and more misaligned as training progresses steadily increasing the need for
effective debiasing strategies.

Figure: Figure 18: Curvature biases increase over the course of training. We evaluate the relative slope and curvature biases at different checkpoints during training for the All-CNN-C model on CIFAR-100. $5$ mini-batches are drawn per checkpoint. For each mini-batch, the relative biases are represented as a dot (at the mean relative bias) and a vertical line ranging from the $25\%$ to the $75\%$ percentile. While the biases in the slope remain relatively stable over the course of training, the biases in the curvature increase (over more than $3$ orders of magnitude).
Refer to caption: x29.png

### B.10 Additional experiment: The curvature bias increases with P 𝑃 P italic_P

In high-dimensional spaces, it becomes increasingly unlikely that random vectors are
aligned.
While the eigenspaces of the curvature matrices are not completely random, they
are subject to noise. It is thus conceivable that their overlap decreases as the number
of parameters $P$ increases. If this hypothesis is true, the curvature biases
should become more pronounced in large models.

Experimental procedure & results. To test this hypothesis, we use test problem
(D) that implements a simple convolutional neural network with
variable width and depth (for details, see Section B.1). For each
fully trained model, we evaluate the relative error between $\partial^{2}_{{\bm{u}}_{p}}q({\bm{\theta}}_{\star};\mathcal{B})$ and $\partial^{2}_{{\bm{u}}_{p}}q({\bm{\theta}}_{\star};\mathcal{D})$ for the ${\bm{G}}_{\mathcal{B}}$’s top $100$ eigenvectors at batch size $128$.
This procedure is repeated for $5$ different mini-batches for each of the $9$ models,
resulting in a total of $45$ error distributions (see Figure 19). The
results confirm our hypothesis: The relative errors tend to increase with the number of
parameters $P$. In the massively overparameterized regime, the biases might
thus become even more relevant and effective debiasing strategies are needed.

Figure: Figure 19: Increasing curvature biases with $P$. We train $9$ convolutional neural networks with different widths and depths for $100$ epochs on the CIFAR-10 dataset using Adam with standard hyperparameters. For the fully trained model, we evaluate the relative error $|\partial^{2}_{{\bm{u}}_{p}}q({\bm{\theta}}_{\star};\mathcal{B})-\partial^{2}_ {{\bm{u}}_{p}}q({\bm{\theta}}_{\star};\mathcal{D})|\cdot|\partial^{2}_{{\bm{u} }_{p}}q({\bm{\theta}}_{\star};\mathcal{D})|^{-1}$ for ${\bm{G}}_{\mathcal{B}}$’s top $100$ eigenvectors at batch size $|\mathcal{B}|=128$. $5$ different mini-batches are used per model resulting in a total of $45$ error distributions (each consisting of $100$ numbers). These distributions are represented by their median (as a dot ) and the $25\%$ and $75\%$ percentiles (as a line segment ) $P$. The $5$ distributions for each model are slightly spread along the $x$-axis for better visibility. The experiment confirms our hypothesis: The relative errors tend to increase with the number of parameters $P$.
Refer to caption: x30.png

[sections]

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: — How do you anticipate the method to scale or adapt with different architecture and larger dataset, which have different curvature profiles and optimisation challenges?
— Could you clarify the criteria for selecting mini-batches in the two-batch debasing process? Is there any benefit to use overlapping vs. non-overlapping mini-batches, or would a mini-batch with a specific loss profile provide better results? 
— Can you provide more details on runtime/memory costs associated with the two-batch approach? While authors claim it roughly doubles, it would be helpful to understand how this really scales with batch size, and whether costs remain manageable as model size and dataset complexity grow
soundness: 4
strengths: Authors study a well-known but often overlooked issue in mini-batch approx within second-order optimisations and uncertainty quantification for deep learning: the bias in curvature estimates due to mini-batch sampling. While the issue is not new, the approach of a two-batch debasing strategy is an effective and novel (to my knowledge) way to address it and improve the accuracy of the approximates without suffering too much of a computational overhead. This strategy could generalise well across various settings in ML where the full-batch quadratics are intractable. The paper is supported by nice empirical experiments on CG and K-FAC demonstrating the effectiveness of their solution. The authors provide a theoretical intuition for the bias arising from that “regression to the mean” adding an interesting insight.  The experiments are systematically presented and show clear performance difference between single-batch and debasing method . While very technical, authors make an effort to make it as digestible as possible, with the inclusion of figures to visualise the bias and the impact of their debasing strategy.
summary: This paper investigates biases in mini-batch quadratic approximations, for second-order optimization in deep learning. Authors show that when computing quadratic on mini-batches rather than the full dataset, it introduces curvature distortions, leading to overly narrow approximations. The bias, assigned to “regression to the mean”, affects Newton steps in optimizers and Laplace approx for uncertainty quantification. They provide a “two-batch” strategy to decouple direction selection from magnitude estimation, to align mini batch approx more closely with full-batch behaviour with minimal computational overhead. They demonstrate the improve stability of their strategy on CG and K-FAC experiments.
weaknesses: The experimental scope is pretty limited, with only ablations on CNN architecture and CIFAR-10/100 datasets. Testing on a wider variety of architectures, such as transformers or larger datasets, would strengthen a lot the paper’s claims on general applicability. Another limitations lies in the lack of ablations to investigate the sensitivity of the two-batch approach to mini-batch size, as well as the composition of mini-batches used for debasing. Without these, it’s unclear how the two-batch batch method would perform under different resource constraints or mini-batch sampling strategies. Last, the paper discusses the computational trade-offs, but does not provide sufficient detail to me on actual runtime and memory costs for different debasing configuration, leaving with an incomplete understanding of the true method’s scalability.

---

confidence: 3
contribution: 4
initial_rating: 8
presentation: 4
questions: How well do the proposed debiasing strategies scale for large foundation models with millions or billions of parameters?

Can debiased mini-batch quadratics improve uncertainty quantification in foundation models, especially in tasks requiring precise uncertainty, like language modeling or image synthesis?

Can the theoretical insights and debiasing techniques be effectively adapted for transformer-based foundation models?

Could reduced bias in mini-batch quadratics enhance transfer learning by improving local loss landscape approximations during fine-tuning?

How might the debiasing methods apply to multi-modal foundation models, where different data modalities add complexity to curvature estimation?
soundness: 4
strengths: This is an interesting theoretical investigation collaborated with numerical justifications. It teaches me something that I would expect with a nice and convincing narrative. The overall clarity and language of this paper is good. The insights are well-delivered. The theoretical analyses are mostly backed up by numerical experiments.
summary: This paper addresses the systematic bias in mini-batch quadratic approximations used for second-order optimization and uncertainty quantification in deep learning. Mini-batch methods distort the quadratic shape, making uncertainty estimates unreliable. The authors provide a theoretical explanation, discuss the impact on optimization, and propose debiasing strategies to improve accuracy.
weaknesses: I did not identify any obvious weaknesses.

I did not check the proofs.

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: - I recommend to replace $u_1$ and $u_2$ in Figure 1 by leading eigenvectors of full-batch Hessian to better grasp my comment in weaknesses. I expect to see that increasing batch size will lead to a better approximation of the curvature. 
- What is exactly the quantity that you want to estimate and why it is important to estimate? Directional curvature on which random directions?
- What do you exactly mean by bias? To prove an estimate has bias, we need to take average. But, experiments in Figure 1 are not computing an average. How can I conclude from these experiments that the estimate is biased?
soundness: 2
strengths: - A computationally-cheap estimate of 2nd order information is an important topic for optimization 
- Ample experimental observations 
- Designing computational-cheap experiments to study 2nd order derivative of training loss of neural networks
summary: This paper demonstrates a systematic bias in stochastic 2nd order approximation of empirical risk for neural networks. The study start from an observation showing that a particular curvature structure on minibatch Hessian is biased towards underestimation. Then, authors proposes a debiasing method.
weaknesses: I believe the notion of unbiased estimate is not well defined and studied. Define the Hessian associate with full-batch training loss as  $$H(x) = \frac{1}{n} \sum_{i=1}^n \nabla^2 f_i(x)$$. Similarly, we define the unbiased estimate of this matrix as $$H'(x) = \frac{1}{m} \sum_{k=1}^m \nabla^2 f_{i_k}(x)$$ where $i_k$ are uniformly drawn from $\{1,\dots, n\}$. 
For each fixed vector $d$, we have $$E d^\top H' d^\top = d^\top H d$$. Thus, the **directional curvature**, defined in the paper, is unbiased. But, why this paper observe a bias in the estimate? The main issue is that they consider random directions $d$ depending on minibatches. I do not know why we need to choose random $d$s? 

I believe the quantity of interest is not well defined and motivated, here. It is easy to provide an unbiased estimation of  $q$, directional curvature and directional slop. But, the authors want to estimating another quality that they do not exactly defined and it is not clear how its estimation connect with Newton's method or Laplace approximation. 

If you want to estimate the maximum/minimum eigenvalue of the Hessian or even its condition number, the empirical Hessian provides an asymptotically unbiased estimate (see for example https://arxiv.org/pdf/1912.10754).

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: Regarding the motivation in section 3.1 -- just because the gradient lives in the top subspaces does _not_ mean that all the optimization progress occurs in that space.  To the contrary, the evidence suggests that the vast majority of the motion along the top Hessian eigenvectors is oscillatory, and 'cancels out.'  Long-term loss reduction is due to the components of the gradient that lie along the low-curvature Hessian eigenvectors.  For example, see "Does SGD really happen in tiny subspaces?" by Minhak Song, Kwangjun Ahn, Chulhee Yun: https://arxiv.org/abs/2405.16002.  

I don't think this is fatal for the paper, since you are basically only using your improved estimate of the the top Hessian eigenvalues in order to properly compute the conjugate gradient _step size_, which will depend on the top Hessian eigenvalues.  But if you actually tried to optimize only along those eigenvectors, it wouldn't work (as the linked paper shows).
soundness: 3
strengths: The paper offers a simple solution to a problem of interest to multiple areas of deep learning.
summary: Often one would like to obtain a second-order Taylor approximation to a deep learning objective based on a minibatch.  This paper shows that the use of a minibatch results in a strong overestimation of the top Hessian eigenvalues.  The basic problem is that the directions of highest curvature for a minibatch tend to slightly 'overfit' (my words) that minibatch, and do not generalize to other minibatches or to the full-batch objective.  This paper shows that this bias can be corrected with a scheme that uses two separate minibatches - one to compute the top eigenvectors, and another to compute the directional curvature along these eigenvectors.  The paper discusses applications in both optimization (conjugate gradient method for computing a newton step), and uncertainty quantification (laplace's method)
weaknesses: In the application to optimization, the paper does not actually carry out an end-to-end optimization run with a second-order method using the proposed conjugate gradient scheme; instead, the paper just uses the proposed scheme to compute a single newton step.

Meta-review: This paper investigates systematic biases in mini-batch quadratic approximations used for second-order optimization and uncertainty quantification in deep learning. The authors demonstrate that using mini-batches to estimate curvature leads to distortions in the quadratic shape, particularly overestimating top eigenvalues. They provide theoretical explanations for this phenomenon and propose practical debiasing strategies using a two-batch approach. The paper shows how these biases affect applications like conjugate gradient optimization and Laplace approximation for uncertainty quantification, and demonstrates that their debiasing methods can significantly improve performance in these areas.

The paper's strengths lie in its identification of an important issue in deep learning optimization and uncertainty quantification, providing both theoretical insights and empirical evidence for the observed biases. The proposed debiasing strategies are practical and computationally efficient, showing clear improvements in concrete applications. The paper is well-presented with clear explanations and visualizations.

Initially, the experimental scope was somewhat limited, focusing mainly on CNN architectures and CIFAR datasets. However, the authors addressed this concern in their rebuttal by expanding their experiments to include larger models and datasets.

The paper addresses a significant and previously underexplored issue in deep learning, with potential impact across multiple areas including optimization and uncertainty quantification. The proposed debiasing strategies are novel, practical, and show clear improvements over existing methods. The majority of reviewers strongly support acceptance, and the authors have adequately addressed reviewer concerns and expanded their experiments in the rebuttal.

Decision: Accept (Poster)