commit bbc978d01641de3832bee005101f3a782b1fa05c
parent 0dbb6997353fe36829abd0bfeb3e12c9781cb443
Author: Silas Brack <s174433@student.dtu.dk>
Date: Tue, 3 Jan 2023 22:56:35 +0100
More writing.
Diffstat:
11 files changed, 231 insertions(+), 520 deletions(-)
diff --git a/chapters/experiments.tex b/chapters/experiments.tex
@@ -4,7 +4,7 @@
\section[The Advantage of Working With Hessian-Vector Products]{The Advantage of Working With Hessian-Vector Products}[Hessian-Vector Products]
-In this project we propose performing the Laplace approximation by only storing the computational graph for the implicit Hessian-vector product, thereby avoiding the explicit computation and storage of the quadratically-scaling Hessian matrix.
+In this project, we propose performing the Laplace approximation by only storing the computational graph for the implicit Hessian-vector product, thereby avoiding the explicit computation and storage of the quadratically-scaling Hessian matrix.
How significant of an effect does this have, though?
To test this, we perform Hessian-vector products \(\bm K \bm v\) and inverse Hessian-vector products \(\bm K^{-1} \bm v\), where \(\bm K \in \reals^{N \times N}\), and compare their performance.
To compare performance with regard to memory usage, we perform these products for an increasing problem dimensionality \(N \in \{10^1, 10^2, \ldots, 10^9\}\).
@@ -17,7 +17,7 @@ Instead, we simply measure the value of \(N\) at which the program fails from an
This experiment will then answer two questions:
\begin{enumerate}
- \item How much larger problems can we tackle if we don't need to instantiate the whole Hessian?
+ \item How much larger problems can we solve if we don't need to instantiate the whole Hessian?
\item How much faster is it to compute the GVP versus, say, the HVP or the explicit Hessian-vector product?
\end{enumerate}
@@ -65,7 +65,7 @@ This can be calculated as the ratio between the wall-clock time of the HVP to th
Thus, larger values suggest greater performance gains for the GVP, while values closer to one suggest there is no performance gain.
These results can be seen in \cref{fig:hessian-profile-ratios}.
-Notice that the number of parameters on the \(x\)-axis are exponentially increasing.
+The number of parameters on the \(x\)-axis are exponentially increasing.
This is in line with the theory, as noted in \cref{ssec:practical-ggn} (SHOULD IT BE MOVED HERE?)
\section{Sampling Ablation}
diff --git a/chapters/higham.tex b/chapters/higham.tex
@@ -30,14 +30,14 @@ Let us analyse the shapes of the different terms in \cref{eq:higham-samples} as
\begin{align*}
\Sigma^{1/2} \epsilon = \underbrace{\alpha^{-1/2} \epsilon}_{n} + \underbrace{J\T}_{n \times kN} \underbrace{\left(J J\T\right)^{-1}}_{kN \times kN} \left( \underbrace{\left(J J\T + \alpha \identity\right)^{-1/2}}_{kN \times kN} \underbrace{J \epsilon}_{kN} - \underbrace{\alpha^{-1/2} J \epsilon}_{kN} \right).
\end{align*}
-Now, which matrix multiplications involve summing over two \(kN\)-shaped dimensions?\footnote{Notice that both \(J J\T\) and \(J \epsilon\) sum over \(n\).}
+Now, which matrix multiplications involve summing over two \(kN\)-shaped dimensions?\footnote{Both \(J J\T\) and \(J \epsilon\) sum over \(n\).}
Why is this relevant?
-Notice that these summations are the only thing which prevents us from simply summing over the whole term!
+These summations are the only thing which prevents us from simply summing over the whole term!
These multiplications are bolded in the following equation:
\begin{align*}
\Sigma^{1/2} \epsilon = \alpha^{-1/2} \epsilon + J\T \bullet \left(J J\T\right)^{-1} \bullet \left(\left(J J\T + \alpha \identity\right)^{-1/2} \bullet J \epsilon - \alpha^{-1/2} J \epsilon \right)
\end{align*}
-Notice that in each of these terms we sum over the output size \(k\) naturally by performing the matrix multiplication, and that we would like to sum over \(N\) as well.
+In each of these terms, we sum over the output size \(k\) naturally by performing the matrix multiplication, and that we would like to sum over \(N\) as well.
Let us look at the individual terms which get summed over their \(kN\)-sized dimension.
We separate these terms into \(A\) and \(B\):
\begin{align*}
diff --git a/chapters/introduction.tex b/chapters/introduction.tex
@@ -43,7 +43,7 @@ The ideas presented in this article essentially constitute a compilation of advi
This should be discussed in a bit more detail in a thesis, since there
are certain objectives discussed in the project plan.
In an article, a quick sentence which summarises the rest of the
-introduction and states succinctly exactly which problem will be tackled
+introduction and states succinctly exactly which problem will be approached
and which approach will be made should suffice.
In this project, we strive to develop an effortless Bayesian method.
diff --git a/chapters/literature.tex b/chapters/literature.tex
@@ -177,14 +177,14 @@ minimum eigenvalue determined by the perturbation \(\alpha\) which guarantees po
% \bm{\theta} ={} & \bm{\mu} + \bm{\sigma} \circ \bm{\varepsilon}\label{eq:meanfield}
% \end{align}
% where \(\bm{\varepsilon} \sim \normal(\bm 0, \identity)\).
-% For this type of variational approximation, the entropy term is given by \(\entropy{q(\theta)} = - \sum_i \log \sigma_i\) and the cross-entropy of the prior relative to the variational approximation is calculated via Monte Carlo simulation by taking the prior log probability with respect to mean-field posterior samples as
+% For this type of variational approximation, the entropy term is given by \(\entropy{q(\theta)} = - \sum_i \log \sigma_i\) and the cross-entropy of the prior compared to the variational approximation is calculated via Monte Carlo simulation by taking the prior log probability with respect to mean-field posterior samples as
% \begin{align}
% \crossentropy{q(\bm\theta)}{p(\bm\theta)} ={} & - \int q(\bm\theta) \log(p(\bm\theta))\,d\bm\theta \nonumber \\
% \approx{} & \frac{1}{S} \sum^S_{s=1} \log p(\bm{\theta}^{(s)})
% \end{align}
% where \(\bm{\theta}^{(s)} \sim \normal(\bm{\mu}, \bm{\sigma})\).
-% The use of the mean-field approximation for BNNs has been found to be unreliable~\sidecite{wu2018deterministic} and, for increasingly wide neural networks, converges towards the prior~\sidecite{coker2021wide}.
+% The use of the mean-field approximation for BNNs has been found to be unreliable~\sidecite{wu2018deterministic} and, for increasingly wide neural networks, converges toward the prior~\sidecite{coker2021wide}.
% However, for \emph{deep} BNNs, the mean-field assumption may be reasonable~\sidecite{farquhar2020liberty}.
% \subsection{Full-Rank Variational Approximation}
@@ -196,7 +196,7 @@ minimum eigenvalue determined by the perturbation \(\alpha\) which guarantees po
% For \(D\) model parameters, while a mean-field approximation has scale parameters \(\bm \sigma^D\), the full-rank approximation has scale parameters \(\bm \Sigma_{\mathrm{FR}}^{D \times D}\).
% The variational parameters scale quadratically with the number of model parameters, which constitutes a significant limitation of this type of approximation.
% Specifically, since NNs are typically overparameterised, possessing from thousands to millions to billions of parameters, the quadratic number of variational parameters makes this type of VI infeasible for BNNs.
-% As such, full-rank VI is not applied in any of the experiments in this paper.
+% As such, full-rank VI is not applied in any of our experiments.
% \subsection{Low-Rank Variational Approximation}
diff --git a/chapters/mixture.tex b/chapters/mixture.tex
@@ -27,5 +27,5 @@ This method depends on the conditioning number of the outer product \(J H J\T\),
However, this method poses some major issues when it comes to computing the evidence of the model.
\begin{align}
p(\bm x) ={} & \int_{\bm \theta} p(\bm x \given \bm \theta) p(\bm \theta)\,d \bm \theta
- \\ ={}& \prod^N_n \exp F_n (\bm \theta_\textsc{map}) \int_{\bm \theta} \exp\left\{ -\frac{1}{2} (\bm\theta - \bm\theta_\textsc{map} )\T \Lambda_n (\bm\theta - \bm\theta_\textsc{map} )\,d\bm\theta \right\}
+ \\ ={}& \prod^N_n \exp F_n (\bm \theta_\textsc{map}) \int_{\bm \theta} \exp\left\{ -\frac{1}{2} (\bm\theta - \bm\theta_\textsc{map} )\T \Lambda_n (\bm\theta - \bm\theta_\textsc{map} )\,d\bm\theta \right\} \nonumber
\end{align}
diff --git a/chapters/preface.tex b/chapters/preface.tex
@@ -7,6 +7,8 @@
I suppose that, because of this, there is some kind of expectation of anticipation, of the sensation that a culmination/apogee of a.
I, not always being the biggest adherent to the idea of symbol-for-the-sake-of-symbol, wasn't sure what to expect of this experience
+ I also took the meagre chance I saw to sneak in an en dash into the report
+
The work in this thesis is the product of a five-month-long research project conducted in the Section for Cognitive Systems of DTU Compute, during which I helped develop some ideas in the paper ``Large-Scale Laplace''(cite).
}
diff --git a/chapters/sampling.tex b/chapters/sampling.tex
@@ -4,7 +4,7 @@
\section{Introduction}
-In many methods, such as the Laplace approximation (\cref{sec:laplace}), we need to sample from a multivariate normal distribution parameterised by a mean vector \(\bm \mu\) and a covariance matrix \(\bm \Sigma\).
+In many methods, such as the Laplace approximation (\cref{sec:laplace}), we sample from a multivariate normal distribution parameterised by a mean vector \(\bm \mu\) and a covariance matrix \(\bm \Sigma\).
To sample from a Gaussian distribution, you can apply the \emph{reparametrisation trick} to compute a vector of samples as
\begin{align}\label{eq:sample-reparam}
\bm \varepsilon ={} & \bm \mu + \bm \Sigma^{1/2} \bm \varepsilon_0,
@@ -16,16 +16,16 @@ Because of this, the covariance matrix is given by the inverse of this Hessian,
\begin{align}\label{eq:sample-laplace}
\bm \varepsilon = \bm \mu + \bm \Lambda^{-1/2} \bm \varepsilon_0,
\end{align}
-where \(\Lambda = \nabla^2_{\bm\theta} \log p(\bm \theta \given \bm x)\).
+where \(\bm \Lambda = \nabla^2_{\bm\theta} \log p(\bm \theta \given \bm x)\).
In \cref{eq:sample-reparam}, the square root of a matrix yields another matrix which, when multiplied by itself, is equal to the original matrix.
-However, since a Gaussian distribution is invariant to rotation, in this special case, we simply need to obtain a matrix which returns the original matrix \emph{up to a rotation}.\sidenote{That is, if we have a vector of standard normal samples \(\bm \varepsilon \sim \normal(\bm 0, \identity)\), then, for an orthogonal matrix \(\bm A\) (a rotation matrix), \(\bm A\T \bm \varepsilon \sim \normal(\bm 0, \identity)\). We then have that we can sample \emph{non}-standard normal samples as \(\bm \Lambda^{-1/2} \bm A\T \bm \varepsilon \sim \normal(\bm 0, \identity)\).}
+However, since a Gaussian distribution is invariant to rotation, in this special case, we just need to obtain a matrix which returns the original matrix \emph{up to a rotation}.\sidenote{That is, if we have a vector of standard normal samples \(\bm \varepsilon \sim \normal(\bm 0, \identity)\), then, for an orthogonal matrix \(\bm R\) (i.e., a rotation matrix), \(\bm R\T \bm \varepsilon \sim \normal(\bm 0, \identity)\). We then have that we can sample \emph{non}-standard normal samples as \(\bm \Lambda^{-1/2} \bm R\T \bm \varepsilon \sim \normal(\bm 0, \identity)\).}
We thus need to find a method which computes the inverse square root of a high-dimensional matrix up to a rotation.
\section[Contour Integral Quadrature]{Contour Integral Quadrature}[Contour Integral Quad]
-\sidetextcite{pleiss2020fast} propose one such algorithm.
+\sidetextcite{pleiss2020fast} propose one such method.
Contour integral quadrature (CIQ) attempts to solve the problem of computing the inverse-square root of a matrix, up to a rotation, by approximating the expression \(f(\bm K) \bm \varepsilon_0 = \bm K^{-1/2} \bm \varepsilon_0\) where \(\bm K\) is a positive semi-definite matrix using Cauchy's integral formula.
-To do this, it exploits the Lanczos algorithm, Gaussian quadrature, and the msMINRES algorithm, methods which only require the computation of matrix-vector products \(\bm K \bm v\).
+To approximate this integral, it exploits the Lanczos algorithm, Gaussian quadrature, and the msMINRES algorithm, methods which only require the computation of matrix-vector products \(\bm K \bm v\).
There are then essentially three steps to CIQ, namely:
\begin{enumerate}
\item Perform the Lanczos algorithm to compute a lower bound on the maximum eigenvalue and an upper bound on the minimum eigenvalue of \(\bm K\).
@@ -35,25 +35,25 @@ There are then essentially three steps to CIQ, namely:
\begin{algorithm}
\caption{Contour Integral Quad (CIQ)}\label{alg:ciq}
- \Input{$\bm K \succ 0$, $\bm b$, $\bm P \succ 0$, $J > 0$, $Q > 0$}
- \Output{$\bm s = \bm K^{-1/2} b$}
- $\_, \bm\alpha, \bm\beta \gets \mathrm{CG}(\bm K, \bm b, \bm P, J)$\;
- $M_{\mathrm{Lanczos}} \gets \mathrm{TriDiag}(\bm\alpha, \bm\beta)$\;
- $\lambda_M \gets \lambda(M_{\mathrm{Lanczos}})$\;
- $\lambda_{\min} \gets \min{\lambda_M}$\;
- $\lambda_{\max} \gets \max{\lambda_M}$\;
- $w_1, \ldots, w_Q, t_1, \ldots, t_Q \gets \mathrm{Quadrature}(\lambda_{\min}, \lambda_{\max}, Q)$\;
- $\bm c_1, \ldots, \bm c_Q \gets \mathrm{msMINRES}(-\bm K, \bm b, t_q, \bm P, J)$ \Comment*[r]{$\left( t_q \identity - \bm K \right)^{-1} \bm b$.}
- % $s_q \gets \left( t_q \identity + H \right)^{-1} b$ \Comment*[r]{Computed via msMINRES(K, t, J).}
- $\bm s \gets \sum^Q_{q=1} w_q \bm c_q$\;
- % $\mathrm{samples} \gets \sum^Q_{q=1} w_q \left( t_q \identity + H \right)^{-1} b$
+ \Input{\(\bm K \succ 0\), \(\bm b\), \(\bm P \succ 0\), \(J > 0\), \(Q > 0\)}
+ \Output{\(\bm s = \bm K^{-1/2} b\)}
+ \(\_, \bm\alpha, \bm\beta \gets \mathrm{CG}(\bm K, \bm b, \bm P, J)\)\;
+ \(M_{\mathrm{Lanczos}} \gets \mathrm{TriDiag}(\bm\alpha, \bm\beta)\)\;
+ \(\lambda_M \gets \lambda(M_{\mathrm{Lanczos}})\)\;
+ \(\lambda_{\min} \gets \min{\lambda_M}\)\;
+ \(\lambda_{\max} \gets \max{\lambda_M}\)\;
+ \(w_1, \ldots, w_Q, t_1, \ldots, t_Q \gets \mathrm{Quadrature}(\lambda_{\min}, \lambda_{\max}, Q)\)\;
+ \(\bm c_1, \ldots, \bm c_Q \gets \mathrm{msMINRES}(\bm K, \bm b, t_q, \bm P, J)\) \Comment*[r]{\(\left( t_q \identity + \bm K \right)^{-1} \bm b\).}
+ % \(s_q \gets \left( t_q \identity + H \right)^{-1} b\) \Comment*[r]{Computed via msMINRES(K, t, J).}
+ \(\bm s \gets \sum^Q_{q=1} w_q \bm c_q\)\;
+ % \(\mathrm{samples} \gets \sum^Q_{q=1} w_q \left( t_q \identity + H \right)^{-1} b\)
\end{algorithm}
-This procedure (see \cref{alg:ciq}) computes the approximate inverse square root product \(\bm K\) by \(\bm \varepsilon_0\) up to a rotation, i.e.,
+Since this procedure (see \cref{alg:ciq}) computes the approximate inverse square root product \(\bm K\) by \(\bm \varepsilon_0\) up to a rotation, i.e.,
\begin{align}\label{eq:ciq-asdf}
- \bm K^{-1/2} \bm \varepsilon_0.
+ \bm K^{-1/2} \bm \varepsilon_0,
\end{align}
-From here, it is then trivial to also compute the product of a matrix square root by multiplying \(\bm K\) onto this vector, as per
+it is then also trivial to compute the square root product by multiplying \(\bm K\) onto this vector, as per
\begin{align}
\bm K^{1/2} \bm \varepsilon_0 = \bm K \cdot \underbrace{\bm K^{-1/2} \bm \varepsilon_0}_{\text{\cref{eq:ciq-asdf}}}.
\end{align}
@@ -74,12 +74,13 @@ From here, it is then trivial to also compute the product of a matrix square roo
% CAUCHY INTEGRAL FORMULA
% ------------------------------------------
-The first step therefore invokes Cauchy's integral formula.
-Cauchy's integral formula is a central theorem in complex analysis which states that, for a holomorphic function \(f\), for a closed circular contour \(\Gamma\) in the complex plane (see \cref{fig:cauchy-integral-formula}) which encloses the eigenvalues of \(\bm K\), \(f(\bm K)\) can be approximated as\marginnote{Note that the square root function is holomorphic for all positive definite real matrices.}
+The first step invokes Cauchy's integral formula.
+Cauchy's integral formula is a central theorem in complex analysis which states that, for a holomorphic function \(f\), there exists a closed circular contour \(\Gamma\) in the complex plane (see \cref{fig:cauchy-integral-formula}) which encloses the eigenvalues of \(\bm K\) such that \(f(\bm K)\) can be approximated as\marginnote{The inverse square root function is holomorphic for all positive definite real matrices.}
\begin{align}\label{eq:cauchy-integral-formula}
f(\bm K) ={} & \frac{1}{2 \pi i} \oint_\Gamma f(\tau) \left(\tau \identity - \bm K\right)^{-1}\,d\tau.
\end{align}
Since, in our case, the eigenvalues of \(\bm K\) will all be real-valued, a circle centred on the real axis which encloses the minimum and maximum eigenvalues of \(\bm K\) will suffice.\marginnote{If a real-valued matrix is symmetric, its eigenvalues are real. In our case, \(\bm K\) will be the precision matrix obtained from the Laplace approximation.}
+To estimate these values, we can use the Lanczos algorithm (\cref{ssec:lanczos}) to compute a lower bound on the maximum eigenvalue and an upper bound on the minimum eigenvalue of \(\bm K\).
% ------------------------------------------
% QUADRATURE
@@ -97,20 +98,12 @@ Since, in our case, the eigenvalues of \(\bm K\) will all be real-valued, a circ
\label{fig:ciq}
\end{marginfigure}
-We can then apply this to the function \(f(\bm K) = \bm K^{-1/2}\), apply a change of variable, and then approximate the integral using the quadrature rule with \(Q\) quadrature points (see \cref{fig:ciq}), as per
-\begin{align}\label{eq:ciq}
- \bm K^{-1/2} ={} & \frac{1}{2 \pi i} \oint_\Gamma \tau^{-1/2} \left(\tau \identity - \bm K\right)^{-1}\,d\tau \nonumber
- \\ ={}& \frac{1}{\pi i} \oint_{\Gamma_\sigma} \left( \sigma^2 \identity - \bm K \right)^{-1}\,d\sigma \nonumber
- \\ \approx{}& \frac{1}{\pi i} \sum_{q=1}^Q \Tilde{w}_q \left( \sigma^2_q \identity - \bm K \right)^{-1} \nonumber
- \\ \bm K^{-1/2} \bm v \approx{}& \frac{1}{\pi i} \sum_{q=1}^Q \Tilde{w}_q \underbrace{\left( \sigma^2_q \identity - \bm K \right)^{-1} \bm v}_{Q\text{ system solves}},
+We can then apply this to the function \(f(\bm K) = \bm K^{-1/2}\), apply a change of variable, and then approximate this contour integral using the quadrature rule with \(Q\) quadrature points (see \cref{fig:ciq}), as per
+\begin{align}
+ \bm K^{-1/2} ={} & \frac{1}{2 \pi i} \oint_\Gamma \tau^{-1/2} \left(\tau \identity - \bm K\right)^{-1}\,d\tau \label{eq:ciq-integral-tau}
+ \\ \approx{}& \frac{1}{2 \pi i} \sum_{q=1}^Q \Tilde{w}_q \tau_q^{-1/2} \left( \tau_q \identity - \bm K \right)^{-1} \label{eq:ciq-quadrature-tau}
\end{align}
-where \(\sigma\) is obtained from \(\tau\) as a change of variable and \(\Tilde{w}_1, \ldots, \Tilde{w}_Q\) are the \(Q\) quadrature weights.
-We can then solve the \(Q\) systems of equations \(\left( \sigma^2_1 \identity - \bm K \right) \bm c_1 = \bm v, \ldots, \left( \sigma^2_Q \identity - \bm K \right) \bm c_Q = \bm v\) to obtain the solutions \(\bm c_q = \left(\sigma^2_q \identity - \bm K \right)^{-1} \bm v\).
-Note that, since the integrand is symmetric with respect to the real axis, only the imaginary component of \(\Gamma_\sigma\) is required.\sidenote{This is due to the fact that the circle with its centre on the \(x\)-axis is symmetric with respect to said \(x\)-axis.}
-Since \(\sigma\) is then imaginary (its real part is zero), \(\tau := \sigma^2\) is real such that \(\tau = - \Im(\sigma)^2\).
-As such, since \(\Im(\sigma)^2\) must be positive, \(\tau\) must then be real-valued and negative.\marginnote{For simplicity, since \(w_q\) happens to also be real-valued and negative, from now on we will define the variables \(w_q = -\Tilde{w}_q\) and \(t_q = -\sigma^2_q\).}
-In practice, we incorporate the \(1 / (\pi i) \) term into the quadrature weights and, with the quadrature points \(t_1, \ldots, t_Q\), compute \(\bm K^{-1/2} \bm v \approx \sum^Q_{q=1} w_q \bm c_q\).
-
+where \(\tau_1, \ldots, \tau_Q\) are the sampled quadrature points and \(\Tilde{w}_1, \ldots, \Tilde{w}_Q\) are the quadrature weights.
Since we will be sampling a fixed number of quadrature points from the circle, to improve the closeness of the approximation of the integral, it would be beneficial to choose a closed circle which intersects the real axis \emph{at} the minimum and maximum eigenvalues, since this will avoid sampling quadrature points which lie outside the spectrum of \(\bm K\).
% ------------------------------------------
@@ -119,75 +112,74 @@ Since we will be sampling a fixed number of quadrature points from the circle, t
We could sample these quadrature points from the circle uniformly, which corresponds to the regular trapezoid quadrature rule.
However, the convergence for this quadrature is linear with regard to the condition number of \(\bm K\)~\sidecite{pleiss2020fast,hale2008computing}.
-Since the precision matrix computed from the Laplace approximation as the GGN matrix can often have a very low rank and poor conditioning, uniform sampling would then require a very large number of quadrature points \(Q\) and would therefore be inadequate.
+Since the precision matrix (which will be computed from the Laplace approximation as the GGN matrix) can often have a very low rank and poor conditioning, uniform sampling would then require a very large number of quadrature points \(Q\) and would therefore be inadequate.
Since our GGN precision matrix \(\bm \Lambda = \sum^N_{i=1} \bm J_i\T \bm H_i \bm J_i\) can be low-rank, we would instead prefer to oversample quadrature points which lie close to the minimum eigenvalue.
-This is accomplished by applying a change of variable from \(\tau\) to \(\sigma = \tau^{1/2}\) before sampling \(\sigma\).
-This change of variables yields a set of quadrature weights \(w_1, \ldots, w_Q\) given by
+This is accomplished by applying a change of variable from \(\tau\) to \(\sigma = \tau^{1/2}\) and sampling the quadrature points from \(\sigma\).
+To then account for this change of variable, we reformulate \cref{eq:ciq-integral-tau,eq:ciq-quadrature-tau} as
+\begin{align}
+ \bm K^{-1/2} ={} & \frac{1}{2 \pi i} \oint_\Gamma \tau^{-1/2} \left(\tau \identity - \bm K\right)^{-1}\,d\tau \nonumber
+ \\ ={}& \frac{1}{\pi i} \oint_{\Gamma_\sigma} \left( \sigma^2 \identity - \bm K \right)^{-1}\,d\sigma \label{eq:ciq-integral-sigma}
+ \\ \approx{}& \frac{1}{\pi i} \sum_{q=1}^Q \Tilde{w}_q \left( \sigma^2_q \identity - \bm K \right)^{-1}. \label{eq:ciq-quadrature-sigma}
+\end{align}
+We can now adapt the equation to allow for computation using only matrix-vector products.
+From here, the inverse square root vector product is given by
+\begin{align}\label{eq:ciq-sigma-product}
+ \bm K^{-1/2} \bm v \approx{} & \frac{1}{\pi i} \sum_{q=1}^Q \Tilde{w}_q \underbrace{\left( \sigma^2_q \identity - \bm K \right)^{-1} \bm v}_{Q\text{ system solves}}.
+\end{align}
+We can then solve the \(Q\) systems of equations to obtain the solutions \(\bm c_q = \left(\tau_q \identity - \bm K \right)^{-1} \bm v\) for \(q \in 1, \ldots, Q\).
+
+Since the integrand is symmetric with respect to the real axis, only the imaginary component of \(\Gamma_\sigma\) is required.\sidenote{This is because the circle with its centre on the \(x\)-axis is symmetric with respect to said \(x\)-axis.}
+Since \(\sigma\) is then imaginary (its real part is zero), \(\tau := \sigma^2\) is real such that \(\tau = - \Im(\sigma)^2\).
+As such, since \(\Im(\sigma)^2\) must be positive, \(\tau\) must then be real-valued and negative.
+In practice, we incorporate the \(1 / (\pi i)\) term into the quadrature weights and, since \(\Tilde{w}_q\) also happens to be real-valued and negative, we can redefine the quadrature weights \(w_q = -\Tilde{w}_q\) and the quadrature points \(t_q = -\sigma^2_q\) for simplicity.\marginnote{With this redefinition, both \(w_q > 0\) and \(t_q > 0\). This then means that \(\left(t_q \identity + \bm K\right)\) is positive definite.}
+This yields the quadrature rule result \(\bm K^{-1/2} \bm v \approx \sum^Q_{q=1} w_q \bm c_q\), where \(\bm c_q = \left(t_q \identity + \bm K\right)^{-1}\).
+
+This change of variables from \(\tau\) to \(\sigma\) yields a set of quadrature weights \(w_1, \ldots, w_Q\) given by
\begin{align}\label{eq:quadrature-weights}
- w_q = - \frac{2 \sqrt{\lambda_\mathrm{min}}}{\pi Q} \mathcal{K}^\prime (k) \cn(i u_q \mathcal{K}^\prime (k) \given k) \dn (i u_q \mathcal{K}^\prime (k) \given k),
+ w_q = \frac{2 \sqrt{\lambda_\mathrm{min}}}{\pi Q} \mathcal{K}^\prime (k) \cn(i u_q \mathcal{K}^\prime (k) \given k) \dn (i u_q \mathcal{K}^\prime (k) \given k)
\end{align}
-and a set of quadrature points (shifts) by
+and a set of quadrature points (shifts) given by
\begin{align}\label{eq:quadrature-shifts}
\sigma^2_q = \lambda_{\mathrm{min}} \cdot \sn(i u_q \mathcal{K}^\prime (k) \given k)^2,
\end{align}
-where \(\sn\), \(\cn\), and \(\dn\) are the Jacobi elliptic functions and \(\mathcal{K}^\prime(k) = \mathcal{K}(k^\prime) = \mathcal{K}(\sqrt{1 - k^2})\) (see \cref{sec:jacobi-elliptic}).
+where \(\sn\), \(\cn\), and \(\dn\) are the Jacobi elliptic functions and the complete elliptic integral is \(\mathcal{K}^\prime(k) = \mathcal{K}(k^\prime) = \mathcal{K}(\sqrt{1 - k^2})\) (see \cref{sec:jacobi-elliptic}).
To compute these values, we also use the elliptic modulus \(k = \kappa(\bm K)^{-1/2}\) (where \(\kappa(\bm K)\) denotes the condition number of \(\bm K\)), and \(u_q = (q - 1/2) / Q\).
We can thereby now compute the quadrature weights and shifts, as seen in \cref{alg:quad}.
\begin{marginfigure}
\begin{algorithm}[H]
\caption{Quadrature}\label{alg:quad}
- \Input{$\lambda_{\min}$, $\lambda_{\max}$, $Q > 0$}
- \Output{$w_q, t_q \given q \in 1, \ldots, Q$}
- $k^2 \gets \lambda_{\min} / \lambda_{\max}$\;
- ${k^{\prime}}^2 \gets \sqrt{1 - k^2}$\;
- $K^\prime \gets \mathcal{K}({k^{\prime}}^2)$\;
- \For{$q \gets 1$ \KwTo $Q$}{
- $u_q \gets (q - 1/2) / Q$\;
- $\overline{\sn}_q \gets \sn(u_q K^\prime \given {k^{\prime}}^2)$\;
- $\overline{\cn}_q \gets \cn(u_q K^\prime \given {k^{\prime}}^2)$\;
- $\overline{\dn}_q \gets \dn(u_q K^\prime \given {k^{\prime}}^2)$\;
- $\sn_q \gets i ( \overline{\sn}_q / \overline{\cn}_q )$\;
- $\dn_q \gets ( \overline{\dn}_q / \overline{\cn}_q )$\;
- $\cn_q \gets ( 1 / \overline{\cn}_q )$\;
- $w_q \gets \lambda_{\min}^{1/2} K^\prime \cn_q \dn_q$\;
- $w_q \gets -2 w_q / \left(\pi Q\right) $\;
- $t_q \gets \lambda_{\min} \sn_q^2$\;
+ \Input{\(\lambda_{\min}\), \(\lambda_{\max}\), \(Q > 0\)}
+ \Output{\(w_q, t_q \given q \in 1, \ldots, Q\)}
+ \(k^2 \gets \lambda_{\min} / \lambda_{\max}\)\;
+ \({k^{\prime}}^2 \gets \sqrt{1 - k^2}\)\;
+ \(K^\prime \gets \mathcal{K}({k^{\prime}}^2)\)\;
+ \For{\(q \gets 1\) \KwTo \(Q\)}{
+ \(u_q \gets (q - 1/2) / Q\)\;
+ \(\overline{\sn}_q \gets \sn(u_q K^\prime \given {k^{\prime}}^2)\)\;
+ \(\overline{\cn}_q \gets \cn(u_q K^\prime \given {k^{\prime}}^2)\)\;
+ \(\overline{\dn}_q \gets \dn(u_q K^\prime \given {k^{\prime}}^2)\)\;
+ \(\sn_q \gets i ( \overline{\sn}_q / \overline{\cn}_q )\)\;
+ \(\dn_q \gets ( \overline{\dn}_q / \overline{\cn}_q )\)\;
+ \(\cn_q \gets ( 1 / \overline{\cn}_q )\)\;
+ \(w_q \gets \lambda_{\min}^{1/2} K^\prime \cn_q \dn_q\)\;
+ \(w_q \gets 2 w_q / \left(\pi Q\right) \)\;
+ \(t_q \gets -\lambda_{\min} \sn_q^2\)\;
}
\end{algorithm}
\end{marginfigure}
-% \begin{algorithm}
-% \caption{Quadrature}\label{alg:quad}
-% \Input{$\lambda_{\min}$, $\lambda_{\max}$, $Q > 0$}
-% \Output{$w_1, \ldots, w_Q, t_1, \ldots, t_Q$}
-% $k^2 \gets \lambda_{\min} / \lambda_{\max}$\;
-% ${k^{\prime}}^2 \gets \sqrt{1 - k^2}$\;
-% $K^\prime \gets \mathcal{K}({k^{\prime}}^2)$ \Comment*[r]{Computed using ellipk}
-% \For{$q \gets 1$ \KwTo $Q$}{
-% $u_q \gets (q - 1/2) / Q$\;
-% $\overline{\sn}_q \gets \sn(u_q K^\prime \given {k^{\prime}}^2)$ \Comment*[r]{Computed using ellipj}
-% $\overline{\cn}_q \gets \cn(u_q K^\prime \given {k^{\prime}}^2)$ \Comment*[r]{Computed using ellipj}
-% $\overline{\dn}_q \gets \dn(u_q K^\prime \given {k^{\prime}}^2)$ \Comment*[r]{Computed using ellipj}
-% $\sn_q \gets i ( \overline{\sn}_q / \overline{\cn}_q )$\;
-% $\dn_q \gets ( \overline{\dn}_q / \overline{\cn}_q )$\;
-% $\cn_q \gets ( 1 / \overline{\cn}_q )$\;
-% $w_q \gets \left(-2 \lambda_{\min}^{1/2}\right) / \left(\pi Q\right) K^\prime \cn_q \dn_q$\;
-% $t_q \gets \lambda_{\min} \sn_q^2$\;
-% }
-% \end{algorithm}
-
-The last step involves solving the \(Q\) linear systems defined in \cref{eq:ciq} to determine the solves \(\bm c_q\).
-As mentioned above, this is done by using msMINRES (\cref{ssec:msminres,alg:msminres}) as \texttt{msMINRES(-K, b, t\_q, P, J)}.\sidenote{Note that we negate \(\bm K\), since msMINRES computes \(\left(t_q \identity + \bm K \right)^{-1} \bm v\), while we want to compute \(\left(t_q \identity - \bm K \right)^{-1} \bm v\). Since we can only access the matrix-vector product, we simply use \(- \bm K \bm v\) whenever the matrix-vector product is called.}
-
-This last step is then sensitive to preconditioning
-
-Mention computational bottleneck being performing the msMINRES for the shifted systems.
+The last step involves solving the \(Q\) linear systems defined in \cref{eq:ciq-sigma-product} to determine \(\bm c_q\).
+As mentioned above, this is done by using msMINRES (\cref{ssec:msminres,alg:msminres}).
+Since the Lanczos algorithm only requires the matrix-vector product \(\bm K \bm v\) with a random vector \(\bm v\), we can use the same random vector for all \(Q\) linear systems.
+As such, the computational bottleneck of the contour integral quadrature is performing the msMINRES for the shifted systems.
+Additionally, since msMINRES is an iterative Krylov method, it is also sensitive to the conditioning of the linear systems, i.e., the conditioning of \(\bm K\).
+To mitigate the effect of ill conditioning, we can use a preconditioner \(\bm P\) such that \(\bm P^{-1} \bm K\) is well-conditioned.
\section{Preconditioning}
-One drawback of contour integral quadrature if that the accuracy its of approximation of \(\bm \Lambda^{-1/2} \bm \varepsilon_0\) suffers when the precision matrix \(\bm \Lambda\) is poorly conditioned.\sidenote{Recall that a matrix is considered poorly conditioned when the ratio of its largest eigenvalue to its lowest eigenvalue, its \emph{conditioning number} (\(\kappa := \lambda_{\mathrm{max}} / \lambda_{\mathrm{min}}\)), is very large.}
+One drawback of contour integral quadrature if that the accuracy its of approximation of \(\bm \Lambda^{-1/2} \bm \varepsilon_0\) suffers when the precision matrix \(\bm \Lambda\) is poorly conditioned.\sidenote{A matrix is considered poorly conditioned when the ratio of its largest eigenvalue to its lowest eigenvalue, its \emph{conditioning number} (\(\kappa := \lambda_{\mathrm{max}} / \lambda_{\mathrm{min}}\)), is very large.}
In the case of the Laplace approximation, as per \cref{eq:ggn-laplace}, we have that the precision matrix is given by
\begin{align}\label{eq:ggn-laplace}
@@ -200,7 +192,7 @@ Let us define \(\lambda_1, \ldots, \lambda_o\) as the eigenvalues of a matrix so
We can then
Assume that the non-zero spectrum of \(J_i\T H J_i\) is relatively flat, i.e., \(\lambda_1 \not\gg \lambda_o\).
-In a hand-wavy way, we have that the ``more similar'' the eigenvectors (and assuming that the eigenvectors have the same ordering between the two matrices)
+In a hand-wavy way, we have that the ``more similar'' the eigenvectors (and assuming that the eigenvectors have the same ordering between the two matrices) are, the more the largest eigenvalue will be to the sum of the eigenvalues.
For preconditioning, we need to find a preconditioner matrix \(P\) and its inverse \(P^{-1}\) such that
\begin{align}
@@ -215,9 +207,13 @@ The eigenvalues of our GGN approximation are given by
\end{align}
where \(\{s_1, \ldots, s_p\}, p \leq N \cdot k\) are the non-zero eigenvalues of the rank-\(p\) matrix \(\sum^N_i J_i\T H J_i\).
-Notice that if a preconditioner approximates all eigenvalues and eigenvectors of a
-Something something spectrum, shape of spectrum, how steep is it?
-The more values you add, the steeper the spectrum becomes (even the non-zero one)
+If a preconditioner approximates all eigenvalues and eigenvectors of a matrix, then the preconditioner and the matrix are equal and the preconditioner is exact.
+However, we often do not have a preconditioner which is exact, but rather an approximation of the matrix.
+In this case, a balance must be struck between the accuracy of the preconditioner and the computational cost of computing the preconditioner (as well as its feasibility).
+Furthermore, the inverse of the preconditioner is required for preconditioning, which is often not available.
+To approximate the inverse of the preconditioner, we can use the conjugate gradient method, though this method is then sensitive to the conditioning of the preconditioner.
+Spectrum, shape of spectrum, how steep is it?
+The more values you add, the steeper the spectrum becomes (even the non-zero one).
\begin{enumerate}
\item Scaling
@@ -228,27 +224,27 @@ The more values you add, the steeper the spectrum becomes (even the non-zero one
\item Speed
\end{enumerate}
-Typically, when preconditioning, you need a matrix which is similar to the
+Typically, when preconditioning, you need a matrix which is similar to the matrix you are preconditioning.
In this way, the preconditioner acts as an ``initial best guess'' of the value to be computed.
As such, for CIQ, it would be expected that the preconditioner should approximate the value of \(H^{-1/2}\).
-In reality, we only need an approximation of \(H^{-1}\) wait is this really true? we still need \(H^{1/2} b\), we just calculate this value itself using CIQ?
+In reality, we only need an approximation of \(H^{-1}\).
+WAIT IS THIS TRUE? WE STILL NEED \(H^{1/2} b\), WE JUST CALCULATE THIS VALUE USING CIQ.
As such, the conditioning number of our preconditioner also becomes an issue, since we have two conflicting objectives: to have a preconditioner which is as similar to \(H\) as possible and to have a preconditioner which we can invert easily.
-The first point lends itself towards the use of preconditioners with a similar conditioning number as \(H\).
-However, in order to invert an arbitrary positive semi-definite matrix, we will often resort to using the conjugate gradient method which is sentitive to the conditioning number of the preconditioner.
-Thus, there is an intrinsic balance to be struck between a preconditioner which is very similar to \(H\) (but whose conditioning number is an issue in itself) and a preconditioner which is less similar to \(H\) (and will therefore not improve the conditioning of the problem).
+The first point lends itself toward the use of preconditioners with a similar conditioning number as \(H\).
+However, to invert an arbitrary positive semi-definite matrix, we will often resort to using the conjugate gradient method which is sentitive to the conditioning number of the preconditioner.
+Thus, there is an intrinsic balance to be struck between a preconditioner which is very similar to \(H\) (but whose conditioning number is itself an issue) and a preconditioner which is less similar to \(H\) (and will therefore not improve the conditioning of the problem).
Let us consider the toy example of a preconditioner which we can guarantee to have the same eigenvectors as \(H\) and for which we can control the eigenvalues.
One example of such a preconditioner would be???
-Depending on the rank of the preconditioner, we can then eliminate a number of the largest / lowest eigenvalues of \(H\) equal to the rank of the preconditioner.
+Depending on the rank of the preconditioner, we can then eliminate as many of the largest / lowest eigenvalues of \(H\) as the rank of the preconditioner.
If we have a rank-one preconditioner whose only eigenvector is the largest eigenvector of \(H\), the second-largest eigenvalue becomes the largest.
In the best-case scenario, you can then eliminate
If \(H\) has a very flat spectrum, then the problem cannot be ill conditioned and thus preconditioning is immaterial.
-If \(H\) has a very
% This analogy can be extended in a hand-wavy way to an imperfect preconditioner which doesn't exactly approximate the eigenvalue
Finally, performance of computing
-In CIQ, we will, in each iteration, perform one matrix-vector product \(H v\) and one preconditioner-vector product \textbf{check this}, as seen in \cref{alg:ciq}.\sidenote{Because of this, to avoid the preconditioner becoming a performance bottleneck, the speed of the preconditioner-vector products should ideally be significantly greater than that of the matrix-vector products.}
+In CIQ, we will, in each iteration, perform one matrix-vector product \(H v\) and one preconditioner-vector product \textbf{check this}, as seen in \cref{alg:ciq}.\sidenote{Because of this, to avoid the preconditioner becoming a performance bottleneck, the speed of the preconditioner-vector products should be significantly greater than that of the matrix-vector products.}
As such, if the preconditioner-vector product is similarly or more expensive to compute compared to the matrix-vector product, then preconditioning will ....
However, an effective preconditioner will significantly improve the convergence speed of CIQ, and this effect can often outweigh the cost of computing the preconditioner.
@@ -262,7 +258,7 @@ If we calculate the GGN approximation of the Hessian by linearizing over the who
\end{align}
DO I NEED TO PROVE THIS?
The problem with using this approximation is that the rank of \(P\) is 1.
-This means that, best-case scenario, we can reduce the highest eigenvalue of the Hessian.
+Best-case scenario, we can reduce the highest eigenvalue of the Hessian.
This occurs when the gradient corresponds to the direction of the highest precision (empirically, it seems that \emph{this is not the case}).
This would then leave the second-highest eigenvalue unaffected.
If the rank of our precision matrix is greater than one, then this value seems likely to be similarly large to originally the largest eigenvalue.
@@ -270,7 +266,7 @@ Therefore, the conditioning number of our problem will not be significantly redu
As such, this preconditioner is not worth pursuing.
\subsection{Sub-sampling the data}
-We could simply choose to calculate the Hessian over fewer points and invert it using the conjugate gradient method to find our preconditioner.
+We could just choose to calculate the Hessian over fewer points and invert it using the conjugate gradient method to find our preconditioner.
This would have the advantage of
\begin{align}
\lambda\left( J\T J + \alpha I \right) ={} & \{ \underbrace{s_1, s_2, \ldots, s_k}_{k}, \underbrace{\alpha, \ldots, \alpha}_{n - k} \}
@@ -279,8 +275,8 @@ This would have the advantage of
% \Span_\lambda\left( J\T J + \alpha \identity \right)
\end{align}
-If the eigenvectors of \(J_i\T J_i\) are all (approximately) the same, then the \(\textstyle{\sum^N_i} J_i\T J_i\) term has \(k\) non-zero eigenvalues (the same as \(J\T J\)).
-If these eigenvectors are all different (orthogonal?), then the aforementioned term will have \(B \cdot k\) non-zero eigenvalues.
+If the eigenvectors of \(J_i\T J_i\) are all (approximately) the same, then the per-observation Jacobian term \(\textstyle{\sum^N_i} J_i\T J_i\) has \(k\) non-zero eigenvalues (the same as \(J\T J\)).
+If these eigenvectors are all different (orthogonal?), then this per-observation Jacobian term will have \(B \cdot k\) non-zero eigenvalues.
Alternatively, we can also instead estimate the eigenvectors and eigenvalues of \(\textstyle{N / B \sum^B_i} J_i\T J_i\).
This would \emph{hopefully} have an eigenbasis that is closer to that of \(\textstyle{\sum^N_i} J_i\T J_i\) without needing to calculate the precision matrix over the whole dataset (we may need to guarantee all classes are represented in \(x_i, i \sim \mathcal{B}\)).
@@ -291,12 +287,12 @@ Now, dealing with poor conditioning only in the inversion of our preconditioner
\[\textstyle{\sum^N_i} s_1 v_i / \alpha \leq \kappa \leq N s_1 / \alpha\]
TALK ABOUT PRECONDITIONER WITH ALL OBSERVATIONS BUT DIFFERENT ALPHA
-NOTE THAT THIS POSES ANOTHER ISSUE: THE FACT THAT THE PRECONDITIONER BECOMES WAY MORE EXPENSIVE ON ALL OBSERVATIONS
+THIS POSES ANOTHER ISSUE: THE PRECONDITIONER BECOMES WAY MORE EXPENSIVE ON ALL OBSERVATIONS
As mentioned before, each msMINRES iteration performs one matrix-vector product and one preconditioner-vector product.
However, even though the preconditioner is constructed in nearly the same way as the GGN matrix, the preconditioner is significantly cheaper to compute.
-For the subsampled GGN preconditioner, the preconditioner-vector product will then cost \(B / N \cdot t_{\mathrm{GGN}}\), where \(t_{\mathrm{GGN}}\) is the computational cost of performing the GGN-vector product.\sidenote{Note that this analysis assumes that the computation of the GGN-vector product scales linearly in the number of observations used in the GGN matrix.}
-Since \(N \gg B\), then the cost of computing the preconditioner will be negligible relative to that of the GGN-vector product.
+For the subsampled GGN preconditioner, the preconditioner-vector product will then cost \(B / N \cdot t_{\mathrm{GGN}}\), where \(t_{\mathrm{GGN}}\) is the computational cost of performing the GGN-vector product.\sidenote{This analysis assumes that the computation of the GGN-vector product scales linearly in the number of observations used in the GGN matrix.}
+Since \(N \gg B\), then the cost of computing the preconditioner will be negligible compared to that of the GGN-vector product.
\subsection{Pivoted Cholesky}
@@ -313,37 +309,45 @@ We can then use this approximation as a preconditioner by computing its inverse
\\ P^{-1} ={}& \alpha^{-1} \identity - \alpha^{-2} L\T \left( \identity + \alpha^{-1} L L\T \right)^{-1} L
\end{align}
we then obtain the preconditioner-vector and inverse-preconditioner-vector products as in Equation~\ref{eq:pivoted-cholesky-preconditioner}.
-Notice that the ``scariest'' computation in the inverse preconditioner is inverting a \(k \times k \) matrix, where \(k\) is the rank of our pivoted Cholesky factorisation (which we choose).
+The ``scariest'' computation in the inverse preconditioner is inverting a \(k \times k \) matrix, where \(k\) is the rank of our pivoted Cholesky factorisation (which we choose).
\begin{align}\label{eq:pivoted-cholesky-preconditioner}
P v ={} & L\T ( L v ) + \alpha v
\\ P^{-1} v ={}& \alpha^{-1} v - \alpha^{-2} L\T ( \underbrace{\identity + \alpha^{-1} L L\T}_{k \times k} )^{-1} ( L v )
\end{align}
-We can precompute \(L\T ( \identity + \alpha^{-1} L L\T )^{-1} \in \reals^{n \times k}\), meaning that we only need to perform two matrix multiplications for both the preconditioner- and inverse preconditioner-vector products.
-This would then require storing \(L \in \reals^{k \times n}\) and the aforementioned \(\reals^{n \times k}\) matrix.\sidenote{Note that we can also precompute \(( \identity + \alpha^{-1} L L\T )^{-1} \in \reals^{k \times k}\), which means we would only need to store \(L \in \reals^{k \times n}\) and the aforementioned \(k \times k\) matrix, in which case we would just need to perform one more matrix multiplication (multiplying \(L\T\) with this \(k \times k\) matrix) in every preconditioner call.}
+We can precompute the factorisation-inverse product \(L\T ( \identity + \alpha^{-1} L L\T )^{-1} \in \reals^{n \times k}\), meaning that we only need to perform two matrix multiplications for both the preconditioner- and inverse preconditioner-vector products.
+This would then require storing the factorisation \(L \in \reals^{k \times n}\) and the factorisation-inverse product \(\reals^{n \times k}\) matrix.\sidenote{We can also precompute the inverse \(( \identity + \alpha^{-1} L L\T )^{-1} \in \reals^{k \times k}\), which means we would only need to store the factorisation \(L \in \reals^{k \times n}\) and this inverse \(k \times k\) matrix, in which case we would just need to perform one more matrix multiplication (multiplying \(L\T\) with this \(k \times k\) matrix) in every preconditioner call.}
ADD SOMEWHERE:
-As we sum over multiple low-rank matrices, we will likely find that the minimum non-zero eigenvalue gets progressively smaller relative to the largest.
+As we sum over multiple low-rank matrices, we will likely find that the minimum non-zero eigenvalue gets progressively smaller compared to the largest.
When we have a single rank \(o\) GGN matrix, we have
-This means that the preconditioning of \(J J\T\) (which should be low-rank) will progressively become both \emph{less} low-rank and its condition number will progressively become higher.
+The preconditioning of \(J J\T\) (which should be low-rank) will progressively become both \emph{less} low-rank and its condition number will progressively become higher. MERGE WITH:
-In terms of eigenvalues and eigenvectors,
+Regarding the eigenvalues and eigenvectors, we consider a best-case scenario.
Assume that the pivoted Cholesky factorisation finds the \(k\) largest eigenvectors.
-If the fall-off in the eigenspectrum of this factorisation is steep enough, then the largest eigenvector \(s_1\) will be significantly larger than the smallest eigenvector \(s_k\), especially if the value of \(B\) is large enough that the
+If the eigenspectrum of this factorisation is steep enough, then the largest eigenvalue \(s_1\) will be significantly larger than the smallest eigenvalue \(s_1\) (i.e., there will be a steep drop-off from the largest to the smallest non-zero eigenvalue).
+Since the eigenvectors of each per-observation Hessian will not be the same, when we sum over them, the eigenvalues of the sum will not be the same as the eigenvalues of the individual Hessians.
+However, some of the eigenvectors may be close to each other, and so those eigenvalues will be approximately summed in the summed Hessian's spectrum.
+However, the rank of the total Hessian will increase by the number of observations and so the number of non-zero eigenvalues consequently increase as well.
+These eigenvalues will be smaller than the summed eigenvalues (because the eigenvectors may not be contained in the same subspace), but they will be larger than the smallest eigenvalue of the per-observation Hessian.
+This will then lead to a steeper eigenspectrum and a larger condition number of the total Hessian.
+Thus, when the batch size \(B\) is large, the condition number will increase and the preconditioner will become less effective.
+How much the condition number increases with the batch size depends on the eigenspectrum of the per-observation Hessians (i.e., how close the eigenvectors are to each other).
+REWRITE THIS, IT'S KINDA HARD TO EXPLAIN.
Unfortunately, if we want to use the pivoted Cholesky decomposition to approximate \(\sum^B_i J_i\T J_i\), we are largely trying to approximate the higher eigenvectors of the sum.
In order for this to be the case, we will want to oversample vectors from this matrix which correspond to the largest eigenvalues.
A common approach to sampling the largest eigenvalues is to sample vectors with probability proportional to the diagonal value~\sidecite{harbrecht2012low}.
-However, it is not, in general, possible to efficiently determine the diagonal of a matrix via matrix-vector products.
+However, it is not possible to generally and efficiently determine the diagonal of a matrix via matrix-vector products.
Often, it is necessary to multiply a vector of zeros with a value of one at the index at which to find the diagonal.
-Alternatively, it is possible to approximate the diagonal of the GGN matrix as the element-wise product of the gradient with itself, similarly to the preconditioner described in \cref{ssec:adam-preconditioner} and the GGN approximation computed in \cref{eq:fully-linear-ggn}.
+Alternatively, we can approximate the diagonal of the GGN matrix as the element-wise product of the gradient with itself, similarly to the preconditioner described in \cref{ssec:adam-preconditioner} and the GGN approximation computed in \cref{eq:fully-linear-ggn}.
-In conclusion, to find the optimal parameters for the pivoted Cholesky preconditioner (the number of observations \(B\) and the rank of the pivoted Cholesky factorisation \(k\)), there are some rules of thumb to keep in mind.
+In conclusion, to find the optimal parameters for the pivoted Cholesky preconditioner (the number of observations \(B\) and the rank of the pivoted Cholesky factorisation \(k\)), there are some rules of thumb to consider.
Notably, the quality of the preconditioner depends largely on the ease of inverting the \(\identity + \alpha^{-1} L L\T\) matrix, which depends on its conditioning number.
In practice, increasing the number
-I've found that it's most important to keep \(k\) low, such that the \(k \times k\) outer product of the pivoted Cholesky factorisation matrix \(L\) approximates few enough of the largest eigenvectors that the eigenvalue of the largest is similar to that of the smallest (meaning this outer product is well-conditioned).
-Overall, this means that you need a large enough \(k\) to approximate enough large eigenvectors and a small enough \(k\) to make sure the conditioning number of the outer product is low.
+I've found that it's most effective to keep \(k\) low, such that the \(k \times k\) outer product of the pivoted Cholesky factorisation matrix \(L\) approximates few enough of the largest eigenvectors that the eigenvalue of the largest is close to that of the smallest (meaning this outer product is well-conditioned).
+You thus need a large enough \(k\) to approximate enough large eigenvectors and a small enough \(k\) to ensure the conditioning number of the outer product is low.
Furthermore, you want enough observations \(B\) to be included in the preconditioner such that it's possible to accurately approximate the eigenvectors of the problem (why not include all of them, always?).
\subsection[Randomly Pivoted Cholesky]{Randomly Pivoted Cholesky}[Random Pivoted Cholesky]
@@ -364,7 +368,7 @@ However, due to the speed, effectiveness, and theoretical properties of other pr
\subsection[A Recap on Preconditioning]{A Recap on Preconditioning}[A Recap]
-In general, it is worth noting the flaw with scaling the term in the \(\sum J\T H J\) preconditioner to account for the summing over a Hessian of a limited batch size.\sidenote{Or, more precisely, the term which is equivalent to the \(J\T H J\) term in the Hessian and is consequently used to approximate the largest eigenvalue.}
+It is worth noting the issues that arise from scaling the term in the \(\sum J\T H J\) preconditioner to account for the summing over a Hessian of a limited batch size.\sidenote{Or, more precisely, the term which is equivalent to the \(J\T H J\) term in the Hessian and is consequently used to approximate the largest eigenvalue.}
\begin{enumerate}
\item Never scale your preconditioner up
@@ -384,7 +388,7 @@ Samples \(\varepsilon\) which are normally distributed but do not have a mean of
\end{align}
This has the advantage of only requiring computation of the precision matrix \(\Sigma^{-1}\).
-For the Laplace approximation, this can easily be computed as \(\Sigma^{-1} = - \nabla^2_\theta \log p(\theta \given x)\).
+For the Laplace approximation, this can easily be computed as $\Sigma^{-1} = - \nabla^2_\theta \log p(\theta \given x)$.
Since \(- \nabla^2_\theta \log p(\theta \given x)\) can be computed exactly, this calculation can be performed to evaluate the whether a set of samples \(\varepsilon\) are drawn from a distribution \(\normal(\mu, \Sigma)\) while only accessing the precision matrix in the evaluation.
As such, this method can be used to evaluate whether the approximate normal samples obtained from CIQ are correctly distributed.
diff --git a/chapters/theory.tex b/chapters/theory.tex
@@ -90,7 +90,7 @@ This approximation is given by
\\ \text{Notice that } \nabla^2_{\bm \theta} f_{\bm \theta_0}(\bm x) = 0 \nonumber
\end{align}
%
-% Notice that, in this approximation, we have \(\nabla^2_{\bm \theta} f_{\bm \theta_0}(\bm x) = 0\).
+% In this approximation, we have \(\nabla^2_{\bm \theta} f_{\bm \theta_0}(\bm x) = 0\).
In this way, we are linearising our neural network function.
By combining \cref{eq:ggn-whole-hessian} and \cref{eq:nn-taylor} we then obtain the Gauss-Newton Hessian approximation,
%
@@ -140,7 +140,7 @@ The diagonal of this matrix is given by the element-wise square of the gradient
Note that the choice of application of the generalised Gauss-Newton approximation is not based on having a reduced computational cost --- both the Hessian and the GGN approximation require the same number of forward and backward passes.
However, the GGN approximation is better behaved than the exact Hessian, thereby making it more suitable for practical applications.
-This is because the GGN approximation is designed to be positive semi-definite, whereas the exact Hessian can be vulnerable to negative curvature.
+This is because the GGN approximation is designed to be positive semi-definite, while the exact Hessian can be vulnerable to negative curvature.
This feature can limit its use for optimisation algorithms that require a positive definite Hessian, such as conjugate gradient descent, or the Laplace approximation, which employs the inverse of the Hessian as the covariance matrix of a Gaussian distribution, thereby assuming a positive semi-definite covariance matrix.
The Levenberg-Marquardt heuristic~\sidecite{pascanu2013revisiting}
@@ -238,7 +238,7 @@ Instead, it is often approximated by the diagonal of the Hessian.
\sidecite{martens2015optimizing}
\sidecite{botev2017practical}
-For a recent, detailed discussion of the natural gradient, see~\sidetextcite{martens2020new}.
+For a recent, detailed discussion of the natural gradient, see \sidetextcite{martens2020new}.
\sidecite{wu2019logan}
\section[Inverting a low-rank matrix]{Inverting a low-rank matrix}[Woodbury-Morrison]
@@ -286,6 +286,7 @@ One major advantage Krylov subspace methods have is that they only require compu
As such, if allocation of memory to store a matrix is infeasible, but the computational graph for this matrix can be determined, then methods such as the conjugate gradient method or the minimum residual method can be used to approximate the inverse of this matrix~\sidecite{giordano2018covariances, nocedal1999numerical}.
\subsection{The Lanczos Algorithm}
+\label{ssec:lanczos}
One application known as the Lanczos algorithm adapts the power iteration method, which computes the greatest eigenvector of a square matrix \(\bm K\).
The power iteration method involves iteratively computing the normalised product of \(\bm K\) with a random vector, i.e.,
diff --git a/journals.bib b/journals.bib
@@ -0,0 +1,4 @@
+@String{colt="Conference on Learning Theory"}
+@String{icml="International Conference on Machine Learning"}
+@String{jmlr="Journal of Machine Learning Research"}
+@String{nips="Advances in Neural Information Processing Systems"}
diff --git a/main.bib b/main.bib
@@ -1,116 +1,29 @@
-@article{amari1998natural,
- title = {Natural gradient works efficiently in learning},
- author = {Amari, Shun-Ichi},
- journal = {Neural computation},
- volume = {10},
- number = {2},
- pages = {251--276},
- year = {1998},
- publisher = {MIT Press}
-}
-
@inproceedings{bach2013sharp,
- title = {Sharp analysis of low-rank kernel matrix approximations},
- author = {Bach, Francis},
- booktitle = {Conference on learning theory},
- pages = {185--209},
- year = {2013},
- organization = {PMLR}
-}
-
-@article{bae2018eigenvalue,
- title = {Eigenvalue corrected noisy natural gradient},
- author = {Bae, Juhan and Zhang, Guodong and Grosse, Roger},
- journal = {arXiv preprint arXiv:1811.12565},
- year = {2018}
-}
-
-@book{bernardo2009bayesian,
- title = {Bayesian theory},
- author = {Bernardo, Jos{\'e} M and Smith, Adrian FM},
- volume = {405},
- year = {2009},
- publisher = {John Wiley \& Sons}
-}
-
-@article{bingham2018pyro,
- author = {Bingham, Eli and Chen, Jonathan P. and Jankowiak, Martin and Obermeyer, Fritz and
- Pradhan, Neeraj and Karaletsos, Theofanis and Singh, Rohit and Szerlip, Paul and
- Horsfall, Paul and Goodman, Noah D.},
- title = {{Pyro: Deep Universal Probabilistic Programming}},
- journal = {Journal of Machine Learning Research},
- year = {2018}
+ title = {Sharp analysis of low-rank kernel matrix approximations},
+ author = {Bach, Francis},
+ booktitle = colt,
+ year = {2013}
}
@book{bishop1995neural,
title = {Neural networks for pattern recognition},
author = {Bishop, Christopher},
year = {1995},
- publisher = {Oxford university press}
-}
-
-@book{bishop2006pattern_evidence,
- title = {Pattern recognition and machine learning},
- author = {Bishop, Christopher M and Nasrabadi, Nasser M},
- volume = {4},
- number = {4},
- year = {2006},
- publisher = {Springer},
- pages = {165-172}
+ publisher = {Oxford University Press}
}
@inproceedings{botev2017practical,
- title = {Practical gauss-newton optimisation for deep learning},
- author = {Botev, Aleksandar and Ritter, Hippolyt and Barber, David},
- booktitle = {International Conference on Machine Learning},
- pages = {557--565},
- year = {2017},
- organization = {PMLR}
-}
-
-@article{chang2021bayesian,
- title = {Bayesian Neural Networks: Essentials},
- author = {Chang, Daniel T},
- journal = {arXiv preprint arXiv:2106.13594},
- year = {2021}
-}
-
-@article{cohn1996active,
- title = {Active learning with statistical models},
- author = {Cohn, David A and Ghahramani, Zoubin and Jordan, Michael I},
- journal = {Journal of artificial intelligence research},
- volume = {4},
- pages = {129--145},
- year = {1996}
-}
-
-@article{coker2021wide,
- title = {Wide Mean-Field Variational Bayesian Neural Networks Ignore the Data},
- journal = {International Conference on Machine Learning},
- year = {2021},
- author = {Coker, Beau and Pan, Weiwei and Doshi-Velez, Finale}
-}
-
-@article{daxberger2021laplace,
- title = {Laplace Redux-Effortless Bayesian Deep Learning},
- author = {Daxberger, Erik and Kristiadi, Agustinus and Immer, Alexander and Eschenhagen, Runa and Bauer, Matthias and Hennig, Philipp},
- journal = {Advances in Neural Information Processing Systems},
- year = {2021}
-}
-
-@article{farquhar2020liberty,
- title = {Liberty or depth: Deep bayesian neural nets do not need complex weight posterior approximations},
- author = {Farquhar, Sebastian and Smith, Lewis and Gal, Yarin},
- journal = {Advances in Neural Information Processing Systems},
- year = {2020}
+ title = {Practical gauss-newton optimisation for deep learning},
+ author = {Botev, Aleksandar and Ritter, Hippolyt and Barber, David},
+ booktitle = icml,
+ year = {2017}
}
-@inproceedings{farquhar2020radial,
- title = {Radial bayesian neural networks: Beyond discrete support in large-scale bayesian deep learning},
- author = {Farquhar, Sebastian and Osborne, Michael A and Gal, Yarin},
- booktitle = {International Conference on Artificial Intelligence and Statistics},
- year = {2020},
- organization = {PMLR}
+@inproceedings{daxberger2021laplace,
+ title = {Laplace Redux-Effortless Bayesian Deep Learning},
+ author = {Daxberger, Erik and Kristiadi, Agustinus and Immer, Alexander and Eschenhagen, Runa and Bauer, Matthias and Hennig, Philipp},
+ booktitle = nips,
+ year = {2021}
}
@article{fong2020marginal,
@@ -124,50 +37,17 @@
publisher = {Oxford University Press}
}
-@article{foong2020expressiveness,
- title = {On the expressiveness of approximate inference in bayesian neural networks},
- author = {Foong, Andrew and Burt, David and Li, Yingzhen and Turner, Richard},
- journal = {Advances in Neural Information Processing Systems},
- volume = {33},
- pages = {15897--15908},
- year = {2020}
-}
-
-@article{fortuin2021priors,
- title = {Priors in bayesian deep learning: A review},
- author = {Fortuin, Vincent},
- journal = {arXiv preprint arXiv:2105.06868},
- year = {2021}
-}
-
-@inproceedings{gal2016dropout,
- title = {Dropout as a bayesian approximation: Representing model uncertainty in deep learning},
- author = {Gal, Yarin and Ghahramani, Zoubin},
- booktitle = {International Conference on Machine Learning},
- year = {2016},
- organization = {PMLR}
-}
-
-@inproceedings{gal2017deep,
- title = {Deep bayesian active learning with image data},
- author = {Gal, Yarin and Islam, Riashat and Ghahramani, Zoubin},
- booktitle = {International Conference on Machine Learning},
- year = {2017},
- organization = {PMLR}
-}
-
-@article{gardner2018gpytorch,
- title = {GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration},
- author = {Gardner, Jacob and Pleiss, Geoff and Weinberger, Kilian Q and Bindel, David and Wilson, Andrew G},
- journal = {Advances in neural information processing systems},
- volume = {31},
- year = {2018}
+@inproceedings{gardner2018gpytorch,
+ title = {GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration},
+ author = {Gardner, Jacob and Pleiss, Geoff and Weinberger, Kilian Q and Bindel, David and Wilson, Andrew G},
+ booktitle = nips,
+ year = {2018}
}
@article{giordano2018covariances,
title = {Covariances, robustness and variational bayes},
author = {Giordano, Ryan and Broderick, Tamara and Jordan, Michael I},
- journal = {Journal of machine learning research},
+ journal = jmlr,
volume = {19},
number = {51},
year = {2018}
@@ -195,21 +75,6 @@
publisher = {Elsevier}
}
-@inproceedings{huang2017densely,
- title = {Densely connected convolutional networks},
- author = {Huang, Gao and Liu, Zhuang and Van Der Maaten, Laurens and Weinberger, Kilian Q},
- booktitle = {Proceedings of the IEEE conference on computer vision and pattern recognition},
- year = {2017}
-}
-
-@inproceedings{izmailov2021bayesian,
- title = {What are Bayesian neural network posteriors really like?},
- author = {Izmailov, Pavel and Vikram, Sharad and Hoffman, Matthew D and Wilson, Andrew Gordon Gordon},
- booktitle = {International Conference on Machine Learning},
- year = {2021},
- organization = {PMLR}
-}
-
@software{jax2018github,
author = {James Bradbury and Roy Frostig and Peter Hawkins and Matthew James Johnson and Chris Leary and Dougal Maclaurin and George Necula and Adam Paszke and Jake Vander{P}las and Skye Wanderman-{M}ilne and Qiao Zhang},
title = {{JAX}: composable transformations of {P}ython+{N}um{P}y programs},
@@ -218,13 +83,6 @@
year = {2018}
}
-@article{khan2017variational,
- title = {Variational adaptive-Newton method for explorative learning},
- author = {Khan, Mohammad Emtiyaz and Lin, Wu and Tangkaratt, Voot and Liu, Zuozhu and Nielsen, Didrik},
- journal = {arXiv preprint arXiv:1711.05560},
- year = {2017}
-}
-
@article{kingma2014adam,
title = {Adam: A method for stochastic optimization},
author = {Kingma, Diederik P and Ba, Jimmy},
@@ -232,35 +90,11 @@
year = {2014}
}
-@article{kingma2015variational,
- title = {Variational dropout and the local reparameterization trick},
- author = {Kingma, Durk P and Salimans, Tim and Welling, Max},
- journal = {Advances in Neural Information Processing Systems},
- year = {2015}
-}
-
-% -------------------------------------------------------------------------
-
-@article{krizhevsky2009learning,
- title = {Learning multiple layers of features from tiny images},
- author = {Krizhevsky, Alex and Hinton, Geoffrey and others},
- year = {2009},
- publisher = {Citeseer}
-}
-
-@article{kunstner2019limitations,
- title = {Limitations of the empirical Fisher approximation for natural gradient descent},
- author = {Kunstner, Frederik and Hennig, Philipp and Balles, Lukas},
- journal = {Advances in neural information processing systems},
- volume = {32},
- year = {2019}
-}
-
-@article{lakshminarayanan2017simple,
- title = {Simple and scalable predictive uncertainty estimation using deep ensembles},
- author = {Lakshminarayanan, Balaji and Pritzel, Alexander and Blundell, Charles},
- journal = {Advances in neural information processing systems},
- year = {2017}
+@inproceedings{kunstner2019limitations,
+ title = {Limitations of the empirical Fisher approximation for natural gradient descent},
+ author = {Kunstner, Frederik and Hennig, Philipp and Balles, Lukas},
+ booktitle = nips,
+ year = {2019}
}
@article{laplace1774memoire,
@@ -268,87 +102,39 @@
author = {Laplace, Pierre-Simon},
journal = {M\'em. De Math. Et Phys. Pr\'esent\'es à l’Acad. Roy. Des Sci},
volume = {6},
- pages = {621–656},
+ pages = {621--656},
year = {1774}
}
-@article{lecun1998gradient,
- title = {Gradient-based learning applied to document recognition},
- author = {LeCun, Yann and Bottou, L{\'e}on and Bengio, Yoshua and Haffner, Patrick},
- journal = {Proceedings of the IEEE},
- year = {1998}
-}
-
-@article{mackay1992evidence,
- title = {The evidence framework applied to classification networks},
- author = {MacKay, David JC},
- journal = {Neural computation},
- year = {1992},
- publisher = {MIT Press}
-}
-
@book{mackay2003information,
title = {Information theory, inference and learning algorithms},
author = {MacKay, David},
year = {2003},
- publisher = {Cambridge university press}
-}
-
-@article{maddox2019simple,
- title = {A simple baseline for bayesian uncertainty in deep learning},
- author = {Maddox, Wesley J and Izmailov, Pavel and Garipov, Timur and Vetrov, Dmitry P and Wilson, Andrew Gordon},
- journal = {Advances in Neural Information Processing Systems},
- volume = {32},
- year = {2019}
-}
-
-@inproceedings{martens2010deep,
- title = {Deep learning via hessian-free optimization.},
- author = {Martens, James and others},
- booktitle = {ICML},
- volume = {27},
- pages = {735--742},
- year = {2010}
+ publisher = {Cambridge University Press}
}
@inproceedings{martens2015optimizing,
- title = {Optimizing neural networks with kronecker-factored approximate curvature},
- author = {Martens, James and Grosse, Roger},
- booktitle = {International conference on machine learning},
- pages = {2408--2417},
- year = {2015},
- organization = {PMLR}
+ title = {Optimizing neural networks with kronecker-factored approximate curvature},
+ author = {Martens, James and Grosse, Roger},
+ booktitle = icml,
+ year = {2015}
}
@article{martens2020new,
- title = {New insights and perspectives on the natural gradient method},
- author = {Martens, James},
- journal = {The Journal of Machine Learning Research},
- volume = {21},
- number = {1},
- pages = {5776--5851},
- year = {2020},
- publisher = {JMLRORG}
-}
-
-@article{miani2022laplacian,
- title = {Laplacian Autoencoders for Learning Stochastic Representations},
- author = {Miani, Marco and Warburg, Frederik and Moreno-Mu{\~n}oz, Pablo and Detlefsen, Nicke Skafte and Hauberg, S{\o}ren},
- journal = {arXiv preprint arXiv:2206.15078},
- year = {2022}
-}
-
-@article{netzer2011reading,
- title = {Reading digits in natural images with unsupervised feature learning},
- author = {Netzer, Yuval and Wang, Tao and Coates, Adam and Bissacco, Alessandro and Wu, Bo and Ng, Andrew Y},
- year = {2011}
+ title = {New insights and perspectives on the natural gradient method},
+ author = {Martens, James},
+ journal = jmlr,
+ volume = {21},
+ number = {1},
+ pages = {5776--5851},
+ year = {2020}
}
-@article{nguyen2017variational,
- title = {Variational continual learning},
- author = {Nguyen, Cuong V and Li, Yingzhen and Bui, Thang D and Turner, Richard E},
- journal = {arXiv preprint arXiv:1710.10628},
- year = {2017}
+@inproceedings{miani2022laplacian,
+ title = {Laplacian Autoencoders for Learning Stochastic Representations},
+ author = {Miani, Marco and Warburg, Frederik and Moreno-Mu{\~n}oz, Pablo and Detlefsen, Nicke Skafte and Hauberg, S{\o}ren},
+ booktitle = nips,
+ year = {2022}
}
@book{nocedal1999numerical,
@@ -358,14 +144,6 @@
publisher = {Springer}
}
-@article{osawa2019practical,
- title = {Practical deep learning with Bayesian principles},
- author = {Osawa, Kazuki and Swaroop, Siddharth and Khan, Mohammad Emtiyaz E and Jain, Anirudh and Eschenhagen, Runa and Turner, Richard E and Yokota, Rio},
- journal = {Advances in neural information processing systems},
- volume = {32},
- year = {2019}
-}
-
@article{pascanu2013revisiting,
title = {Revisiting natural gradient for deep networks},
author = {Pascanu, Razvan and Bengio, Yoshua},
@@ -373,43 +151,11 @@
year = {2013}
}
-@incollection{paszke2019pytorch,
- title = {PyTorch: An Imperative Style, High-Performance Deep Learning Library},
- author = {Paszke, Adam and Gross, Sam and Massa, Francisco and Lerer, Adam and Bradbury, James and Chanan, Gregory and Killeen, Trevor and Lin, Zeming and Gimelshein, Natalia and Antiga, Luca and Desmaison, Alban and Kopf, Andreas and Yang, Edward and DeVito, Zachary and Raison, Martin and Tejani, Alykhan and Chilamkurthy, Sasank and Steiner, Benoit and Fang, Lu and Bai, Junjie and Chintala, Soumith},
- booktitle = {Advances in Neural Information Processing Systems}
-}
-
-@article{pleiss2020fast,
- title = {Fast matrix square roots with applications to Gaussian processes and Bayesian optimization},
- author = {Pleiss, Geoff and Jankowiak, Martin and Eriksson, David and Damle, Anil and Gardner, Jacob},
- journal = {Advances in Neural Information Processing Systems},
- volume = {33},
- pages = {22268--22281},
- year = {2020}
-}
-
-@article{rajpurkar2017mura,
- title = {Mura: Large dataset for abnormality detection in musculoskeletal radiographs},
- author = {Rajpurkar, Pranav and Irvin, Jeremy and Bagul, Aarti and Ding, Daisy and Duan, Tony and Mehta, Hershel and Yang, Brandon and Zhu, Kaylie and Laird, Dillon and Ball, Robyn L and others},
- journal = {arXiv preprint arXiv:1712.06957},
- year = {2017}
-}
-
-@article{ritter2021tyxe,
- title = {Ty{X}e: Pyro-based {B}ayesian neural nets for {P}ytorch},
- author = {Ritter, Hippolyt and Karaletsos, Theofanis},
- journal = {arXiv preprint arXiv:2110.00276},
- year = {2021}
-}
-
-@article{rue2017bayesian,
- title = {Bayesian computing with INLA: a review},
- author = {Rue, H{\aa}vard and Riebler, Andrea and S{\o}rbye, Sigrunn H and Illian, Janine B and Simpson, Daniel P and Lindgren, Finn K},
- journal = {Annual Review of Statistics and Its Application},
- volume = {4},
- pages = {395--421},
- year = {2017},
- publisher = {Annual Reviews}
+@inproceedings{pleiss2020fast,
+ title = {Fast matrix square roots with applications to Gaussian processes and Bayesian optimization},
+ author = {Pleiss, Geoff and Jankowiak, Martin and Eriksson, David and Damle, Anil and Gardner, Jacob},
+ booktitle = nips,
+ year = {2020}
}
@article{sabne2020xla,
@@ -418,37 +164,11 @@
year = {2020}
}
-@article{shannon1948mathematical,
- title = {A mathematical theory of communication},
- author = {Shannon, Claude Elwood},
- journal = {The Bell system technical journal},
- volume = {27},
- number = {3},
- year = {1948},
- publisher = {Nokia Bell Labs}
-}
-
@inproceedings{sutskever2013importance,
- title = {On the importance of initialization and momentum in deep learning},
- author = {Sutskever, Ilya and Martens, James and Dahl, George and Hinton, Geoffrey},
- booktitle = {International conference on machine learning},
- pages = {1139--1147},
- year = {2013},
- organization = {PMLR}
-}
-
-@article{wilson2020bayesian,
- title = {Bayesian deep learning and a probabilistic perspective of generalization},
- author = {Wilson, Andrew G and Izmailov, Pavel},
- journal = {Advances in neural information processing systems},
- year = {2020}
-}
-
-@article{wu2018deterministic,
- title = {Deterministic variational inference for robust bayesian neural networks},
- author = {Wu, Anqi and Nowozin, Sebastian and Meeds, Edward and Turner, Richard E and Hern{\'a}ndez-Lobato, Jos{\'e} Miguel and Gaunt, Alexander L},
- journal = {arXiv preprint arXiv:1810.03958},
- year = {2018}
+ title = {On the importance of initialization and momentum in deep learning},
+ author = {Sutskever, Ilya and Martens, James and Dahl, George and Hinton, Geoffrey},
+ booktitle = icml,
+ year = {2013}
}
@article{wu2019logan,
@@ -457,23 +177,3 @@
journal = {arXiv preprint arXiv:1912.00953},
year = {2019}
}
-
-@article{yip1986note,
- title = {A note on the stability of solving a rank-p modification of a linear system by the Sherman--Morrison--Woodbury formula},
- author = {Yip, Elizabeth L},
- journal = {SIAM Journal on Scientific and Statistical Computing},
- volume = {7},
- number = {2},
- pages = {507--513},
- year = {1986},
- publisher = {SIAM}
-}
-
-@inproceedings{zhang2018noisy,
- title = {Noisy natural gradient as variational inference},
- author = {Zhang, Guodong and Sun, Shengyang and Duvenaud, David and Grosse, Roger},
- booktitle = {International Conference on Machine Learning},
- pages = {5852--5861},
- year = {2018},
- organization = {PMLR}
-}
diff --git a/main.tex b/main.tex
@@ -42,6 +42,7 @@
% Load the bibliography package
\usepackage{kaobiblio}
+\addbibresource{journals.bib}
\addbibresource{main.bib} % Bibliography file
% Load mathematical packages for theorems and related environments
@@ -70,15 +71,14 @@
\tikzstyle{mydashed}=[dash pattern=on 2pt off 2pt]
\newcommand{\tick}[2]{\draw[thick] (#1) ++ (#2:0.1) --++ (#2-180:0.2)} %0.03*\xmax
-
\input{macros.tex}
\graphicspath{{figures/}{./}} % Paths in which to look for images
\makeindex[columns=3, title=Alphabetical Index, intoc] % Make LaTeX produce the files required to compile the index
-\makeglossaries % Make LaTeX produce the files required to compile the glossary
-\input{glossary.tex} % Include the glossary definitions
+% \makeglossaries % Make LaTeX produce the files required to compile the glossary
+% \input{glossary.tex} % Include the glossary definitions
\makenomenclature % Make LaTeX produce the files required to compile the nomenclature
@@ -173,16 +173,16 @@
}
\makeatother
-%----------------------------------------------------------------------------------------
-% DEDICATION
-%----------------------------------------------------------------------------------------
+% %----------------------------------------------------------------------------------------
+% % DEDICATION
+% %----------------------------------------------------------------------------------------
-\dedication{
- % \blackout
- % {It’s an incredibly exciting thing, this one, meaningless life of yours.}\\
- {You don't have to have a dream.}\\
- \flushright -- Tim Minchin
-}
+% \dedication{
+% % \blackout
+% % {It’s an incredibly exciting thing, this one, meaningless life of yours.}\\
+% {You don't have to have a dream.}\\
+% \flushright -- Tim Minchin
+% }
%----------------------------------------------------------------------------------------
% OUTPUT TITLE PAGE AND PREVIOUS
@@ -192,18 +192,18 @@
\maketitle
-%----------------------------------------------------------------------------------------
-% PREFACE
-%----------------------------------------------------------------------------------------
+% %----------------------------------------------------------------------------------------
+% % PREFACE
+% %----------------------------------------------------------------------------------------
-\input{chapters/preface.tex}
-\index{preface}
+% \input{chapters/preface.tex}
+% \index{preface}
-\input{chapters/acknowledgments.tex}
-\index{acknowledgments}
+% \input{chapters/acknowledgments.tex}
+% \index{acknowledgments}
-\input{chapters/abstract.tex}
-\index{abstract}
+% \input{chapters/abstract.tex}
+% \index{abstract}
%----------------------------------------------------------------------------------------
% TABLE OF CONTENTS & LIST OF FIGURES/TABLES
@@ -277,29 +277,29 @@
\defbibnote{bibnote}{Here are the references in citation order.\par\bigskip} % Prepend this text to the bibliography
\printbibliography[heading=bibintoc, title=Bibliography, prenote=bibnote] % Add the bibliography heading to the ToC, set the title of the bibliography and output the bibliography note
-%----------------------------------------------------------------------------------------
-% NOMENCLATURE
-%----------------------------------------------------------------------------------------
+% %----------------------------------------------------------------------------------------
+% % NOMENCLATURE
+% %----------------------------------------------------------------------------------------
-% The nomenclature needs to be compiled on the command line with 'makeindex main.nlo -s nomencl.ist -o main.nls' from the template directory
+% % The nomenclature needs to be compiled on the command line with 'makeindex main.nlo -s nomencl.ist -o main.nls' from the template directory
-\nomenclature{$c$}{Speed of light in a vacuum inertial frame}
-\nomenclature{$h$}{Planck constant}
+% \nomenclature{$c$}{Speed of light in a vacuum inertial frame}
+% \nomenclature{$h$}{Planck constant}
-\renewcommand{\nomname}{Notation} % Rename the default 'Nomenclature'
-\renewcommand{\nompreamble}{The next list describes several symbols that will be later used within the body of the document.} % Prepend this text to the nomenclature
+% \renewcommand{\nomname}{Notation} % Rename the default 'Nomenclature'
+% \renewcommand{\nompreamble}{The next list describes several symbols that will be later used within the body of the document.} % Prepend this text to the nomenclature
-\printnomenclature % Output the nomenclature
+% \printnomenclature % Output the nomenclature
-%----------------------------------------------------------------------------------------
-% GLOSSARY
-%----------------------------------------------------------------------------------------
+% %----------------------------------------------------------------------------------------
+% % GLOSSARY
+% %----------------------------------------------------------------------------------------
-% The glossary needs to be compiled on the command line with 'makeglossaries main' from the template directory
+% % The glossary needs to be compiled on the command line with 'makeglossaries main' from the template directory
-\glsaddall % Comment if you want to mention glossary entries in the text
-\setglossarystyle{listgroup} % Set the style of the glossary (see https://en.wikibooks.org/wiki/LaTeX/Glossary for a reference)
-\printglossary[title=Special Terms, toctitle=List of Terms] % Output the glossary, 'title' is the chapter heading for the glossary, toctitle is the table of contents heading
+% \glsaddall % Comment if you want to mention glossary entries in the text
+% \setglossarystyle{listgroup} % Set the style of the glossary (see https://en.wikibooks.org/wiki/LaTeX/Glossary for a reference)
+% \printglossary[title=Special Terms, toctitle=List of Terms] % Output the glossary, 'title' is the chapter heading for the glossary, toctitle is the table of contents heading
%----------------------------------------------------------------------------------------
