commit 23354c15980eedc464e16acf03be0b8b736c7e0e
parent af49311130d1e13c108c05e9f76989879cfb9db5
Author: Silas Brack <s174433@student.dtu.dk>
Date: Mon, 2 Jan 2023 21:37:29 +0100
Fixed section headers.
Diffstat:
4 files changed, 18 insertions(+), 17 deletions(-)
diff --git a/chapters/experiments.tex b/chapters/experiments.tex
@@ -2,7 +2,7 @@
\chapter{Experiments}
\labch{experiments}
-\section{The Advantage of Working With Hessian-Vector Products}
+\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.
How significant of an effect does this have, though?
@@ -82,7 +82,7 @@ What metrics can we use?
-\section{Sampling for the Sine Function}
+\section[Sampling for the Sine Function]{Sampling for the Sine Function}[The Sine Function]
Note that the choice of \(\alpha\) is a non-trivial one
@@ -100,6 +100,6 @@ Note that the choice of \(\alpha\) is a non-trivial one
\label{fig:chisq-sin}
\end{figure}
-\section{Sampling for MNIST}
+\section[Sampling for MNIST]{Sampling for MNIST}[MNIST]
diff --git a/chapters/sampling.tex b/chapters/sampling.tex
@@ -21,7 +21,7 @@ In \cref{eq:sample-reparam}, the square root of a matrix yields another matrix w
However, since a Gaussian distribution is invariant to 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)\).}, in this special case, we simply need to obtain a matrix which returns the original matrix \emph{up to a rotation}.
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}
+\section[Contour Integral Quadrature]{Contour Integral Quadrature}[Contour Integral Quad]
\textcite{pleiss2020fast} propose one such algorithm.
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.
@@ -252,7 +252,8 @@ In CIQ, we will, in each iteration, perform one matrix-vector product \(H v\) an
As such, if the preconditioner-vector product is similarly or more expensive to compute compared to the matrix-vector product, then preconditoineing 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.
-\subsection{Adam-esque fully linear GGN}\label{ssec:adam-preconditioner}
+\subsection[Adam-esque fully linear GGN]{Adam-esque fully linear GGN}[Fully Linear GGN]
+\label{ssec:adam-preconditioner}
If we calculate the GGN approximation of the Hessian by linearizing over the whole model and loss (as described in \cref{ssec:practical-ggn}), we get
\begin{align}
P ={} & \nabla \nabla\T + \alpha \identity
@@ -338,18 +339,18 @@ Often,it is necessary to multiply a vector of zeros with a value of one at the i
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}.
-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 keep in mind.
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.
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}
+\subsection[Randomly Pivoted Cholesky]{Randomly Pivoted Cholesky}[Random Pivoted Cholesky]
Unfortunately, similarly to the pivoted Cholesky preconditioner, the randomly pivoted Cholesky preconditioner requires the diagonal of the GGN matrix in order for the decomposition to be close to the GGN. (MENTION THIS IN THE PIVOTED CHOLESKY SECTION)
-\subsection{Other Laplace approximations}
+\subsection[Other Laplace approximations]{Other Laplace approximations}[Other approximations]
% Last-Layer Laplace
@@ -361,7 +362,7 @@ Unfortunately, similarly to the pivoted Cholesky preconditioner, the randomly pi
However, due to the speed, effectiveness, and theoretical properties of other preconditioners proposed in this section, these methods were not attempted.
-\subsection{A Recap on Preconditioning}
+\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\) term\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.} preconditioner to account for the summing over a Hessian of a limited batch size
diff --git a/chapters/theory.tex b/chapters/theory.tex
@@ -2,7 +2,7 @@
\chapter{Theory}
\labch{theory}
-\section{Optimisation in Deep Learning}
+\section[Optimisation in Deep Learning]{Optimisation in Deep Learning}[Optimisation]
Suppose a neural network is a real-valued function \(f: \reals^n \times \reals^d \rightarrow \reals^o\) parameterised in \(\bm\theta\) which maps an input \(\bm x\) to an output \(f(\bm x; \bm\theta) \equiv f_{\bm\theta}(\bm x)\).
Our goal is to find the optimal parameters \(\bm\theta^*\) which best model the observed data.
@@ -26,7 +26,7 @@ Similarly, for the negative log-posterior loss, we have
\\ ={}& \underbrace{-\sum_i^N \log p(x_i \given \bm \theta)}_{\text{Negative log-likelihood}} - \underbrace{\log p(\bm\theta)}_{\text{Regularisation}}
\end{align}
-\subsection{Stochastic Gradient Descent}
+\subsection[Stochastic Gradient Descent]{Stochastic Gradient Descent}[Gradient Descent]
Stochastic gradient descent (SGD) is a first-order optimisation algorithm which iteratively updates the parameters \(\bm\theta\) in the direction of the negative gradient of the loss function \(\mathcal{L}(\bm\theta)\).
The update rule is given by
@@ -69,7 +69,7 @@ In this framing, if considering, e.g., the negative log-posterior loss from \cre
\\ ={}& \sum_i^N \nabla^2_{\bm\theta} \log p(x_i \given \bm \theta) + \nabla^2_{\bm\theta} \log p(\bm \theta).
\end{align}
-\section{The Generalised Gauss-Newton Approximation}
+\section[The Generalised Gauss-Newton Approximation]{The Generalised Gauss-Newton Approximation}[The GGN Approximation]
From the equation of the Hessian we can apply the chain rule twice and the product rule once to obtain a simpler expression
%
@@ -241,7 +241,7 @@ Instead, it is often approximated by the diagonal of the Hessian.
For a recent, detailed discussion of the natural gradient, see \cite{martens2020new}.
\cite{wu2019logan}
-\section{Inverting a low-rank matrix}
+\section[Inverting a low-rank matrix]{Inverting a low-rank matrix}[Woodbury-Morrison]
\label{sec:woodbury}
% Theorem 1.1 ([18, Thm. 1.35]). Let U, V ∈ Cn×k with k ≤ n and assume that V ∗U is nonsingular. Let f be defined on the spectrum of A = αIn + U V ∗, and if k = n let f be defined at α. Then (1.2) f (A) = f (α)In + U (V ∗U )−1(f (αIk + V ∗U ) − f (α)Ik )V ∗.
@@ -298,7 +298,7 @@ However, the power iteration method only uses the last vector \(\bm b_J\), there
To make use of the entire Krylov subspace \(\mathcal{K}_j(\bm K, \bm b_0)\), the Lanczos algorithm combines the power iteration method with the Gram–Schmidt process, along with the assumption that \(\bm K\) is Hermitian, to produce an orthonormal basis from the Krylov subspace.
This method then converts an eigendecomposition problem for \(\bm K\) into an eigendecomposition problem for a tridiagonal matrix of rank \(J\) whose maximum and minimum eigenvalues will be close to those of \(\bm K\).
-\subsection{The Conjugate Gradient Method}
+\subsection[The Conjugate Gradient Method]{The Conjugate Gradient Method}[The Conjugate Gradient]
Further adjustments to the Lanczos algorithm yield the conjugate gradient method, a Krylov subspace method used to compute the inverse of a matrix by solving a system of equations as
\begin{align*}
@@ -352,7 +352,7 @@ The algorithm itself can be seen in \cref{alg:cg}.
% }
% \end{algorithm}
-\subsection{The Minimum Residual Method}
+\subsection[The Minimum Residual Method]{The Minimum Residual Method}[The Minimum Residual]
\label{ssec:msminres}
Another method which is derived from the Lanczos algorithm is the minimum residual method (MINRES).
diff --git a/chapters/training.tex b/chapters/training.tex
@@ -12,9 +12,9 @@ where \(p(x)\) is known as the evidence\sidenote{It's also known as the \emph{ma
\textcite{fong2020marginal} argue that maximising the marginal (and consequently the log-marginal) is equivalent to performing k-fold cross validation for all values \(k = 1, \ldots, \infty\) and choosing the model with the highest average posterior probability (across each of \(k\) folds and across all values of \(k\)).
-\section{The Determinant Lower Bound}
+\section[The Determinant Lower Bound]{The Determinant Lower Bound}[The Lower Bound]
-\subsection{Hutchinson's Trace Estimator}
+\subsection[Hutchinson's Trace Estimator]{Hutchinson's Trace Estimator}[The Trace Estimator]
