appendix.tex (8072B)
1 \setchapterstyle{lines} 2 \chapter{Algorithms} 3 % \setchapterpreamble[u]{\margintoc} 4 \vspace{-3em} 5 \begin{algorithm}[h!] 6 \caption{Multi-Shift Minimum Residual (msMINRES)}\label{alg:msminres} 7 \Input{$\bm K \succ 0$, $\bm b$, $\bm P \succ 0$, $t_1, \ldots, t_Q$, $J > 0$} 8 \Output{$\bm c_1 = (\bm K + t_1)^{-1} \bm b, \ldots, \bm c_Q = (\bm K + t_Q)^{-1} \bm b$} 9 $\norm{\bm b}_2 \gets \left( \bm b \cdot \bm b \right)^{1/2}$\; 10 $\bm b \gets \bm b / \norm{\bm b}_2$\; 11 $\bm p \gets \bm K \bm b$\; 12 $\bm z_{-1} \gets \bm 0$\;%Like \bm p 13 $\bm z_{0} \gets \bm b$\; 14 $\bm q_{0} \gets \bm P \bm z_{0}$\; 15 $\beta_{0} \gets \left(\bm z_{0} \cdot \bm q_{0} \right)$\; 16 \For{$q \gets 1$ \KwTo $Q$}{ 17 $\bm c^{(q)}_{0} \gets \bm 0$\; 18 $\bm d^{(q)}_{0}, \bm d^{(q)}_{-1} \gets \bm 0$\;%Like \bm b 19 $\cos^{(q)}_0, \cos^{(q)}_{-1} \gets 1$\; 20 $\sin^{(q)}_0, \sin^{(q)}_{-1} \gets 0$\; 21 $\varphi^{(q)}_0 \gets \beta_{0}$\; 22 } 23 \For{$j \gets 1$ \KwTo $J$}{ 24 $\bm p \gets \bm K \bm q_{j-1}$\; % Removed negative because we input the "negative" K matrix 25 % $\bm p \gets - \bm K \bm q_{j-1}$\; 26 $\alpha_{j} \gets \bm p \cdot \bm q_{j-1}$\; 27 $\bm z_j \gets \bm p - \alpha_j \bm z_{j-1} - \beta_{j-1} \bm z_{j-2}$\; 28 $\bm q_j \gets \bm P \bm z_j$\; 29 $\beta_j \gets ({\bm z_j \bm q_j})^{1/2}$\; 30 % $\beta_j \gets \sqrt{\bm z_j \bm q_j}$\; 31 $\bm z_j \gets \bm z_j / \beta_{j}$\; 32 $\bm q_j \gets \bm q_j / \beta_{j}$\; 33 \For{$q \gets 1$ \KwTo $Q$}{ 34 $\varepsilon^{(q)}_{j} \gets \sin^{(q)}_{j-2} \beta_{j-1}$\;%\Comment{Start Givens rotation} 35 $\zeta^{(q)}_{j} \gets \cos^{(q)}_{j-2} \beta_{j-1}$\; 36 $\alpha^{(q)}_{j} \gets \alpha_{j} + t_q$\;%\Comment{Compute shifted alpha} 37 $\eta^{(q)}_j \gets \cos^{(q)}_{j-1} \alpha^{(q)}_{j} - \sin^{(q)}_{j-1} \zeta^{(q)}_{j}$\;%\Comment{Givens rotation from 1 step ago} 38 $\zeta^{(q)}_{j} \gets \cos^{(q)}_{j-1} \zeta^{(q)}_{j} + \sin^{(q)}_{j-1} \alpha^{(q)}_{j}$\; 39 $r^{(q)}_{j} \gets ({\eta^{(q)2}_{j} + \beta^2_{j}})^{1/2}$\;%\Comment{Compute next Givens terms} 40 % $r^{(q)}_{j} \gets \sqrt{\eta^{(q)2}_{j} + \beta^2_{j}}$\;%\Comment{Compute next Givens terms} 41 $\cos^{(q)}_{j} \gets \eta^{(q)}_{j} / r^{(q)}_{j}$\; 42 $\sin^{(q)}_{j} \gets \beta^{(q)}_{j} / r^{(q)}_{j}$\; 43 $\eta^{(q)}_{j} \gets \eta^{(q)}_{j} \cos^{(q)}_{j} + \sin^{(q)}_{j} \beta_{j}$\;%\Comment{Apply current Givens rotation} 44 $\varphi^{(q)}_{j} \gets - \varphi^{(q)}_{j-1} \sin^{(q)}_{j}$; $\varphi^{(q)}_{j-1} \gets \varphi^{(q)}_{j-1} \cos^{(q)}_{j}$\;%\Comment{Apply the latest Givens rotation to the Lanczos-rhs, computing the scale terms for the search vectors} 45 $\bm d^{(q)}_j \gets ( \bm q_{j-1} - \zeta^{(q)}_{j} \bm d^{(q)}_{j-1} - \varepsilon^{(q)}_{j} \bm d^{(q)}_{j-2} ) / \eta^{(q)}_{j}$\;%\Comment{Get the new search vector} 46 $\Delta \bm c^{(q)}_{j} \gets \bm d^{(q)}_{j} \varphi^{(q)}_{j-1}$\; 47 $\bm c^{(q)}_{j} \gets \bm c^{(q)}_{j-1} + \Delta \bm c^{(q)}_{j}$\;%\Comment{Update the solution} 48 } 49 } 50 \For{$q \gets 1$ \KwTo $Q$}{ 51 $\bm c_q \gets \bm c^{(q)}_J \norm{\bm b}_2$\; 52 } 53 \end{algorithm} 54 55 \setchapterstyle{lines} 56 \chapter{Additional Results} 57 58 \begin{table*}[h] 59 \centering 60 \caption[Comparison of Hessian-vector product performance.]{Comparison of the wall-clock time for Hessian-vector, GGN-vector, and manual matrix-vector products, as well as the equivalent inverse-vector products, on a toy problem. Time measured in milliseconds, measured on an A100 GPU across 5 runs that are reported as a mean and standard deviation. Implicit inverse performed via conjugate gradient for HVP and GVP. We highlight in bold the extreme slowdown of computing the manual Hessian-vector product for a 1\,M-dimensional problem. We can see that manual computations fail above small problems, while the implicit GVP and HVP functions and their inverses scale well. We also see that the GVP is slightly faster than the HVP, both both are significantly faster than the manual Hessian-vector product.} 61 \label{tab:hessian-profile} 62 \include{tables/hessian-profile.tex} 63 \end{table*} 64 65 \begin{figure*}[h!] 66 \begin{subfigure}[h]{0.45\textwidth} 67 \centering 68 \includegraphics{hessian_profile_cpu.pdf} 69 \caption[Comparison of Hessian-vector product performance.]{Top: comparison of the performance for manual matrix-vector, Hessian-vector, and GGN-vector products. Bottom: comparison of the performance of inverse-vector products for the same methods. Implicit inverse performed via conjugate gradient for HVP and GVP. We can see that the explicit Hessian-vector product fails for problems with more than 10\,000 dimensions and that the GVP is faster than the HVP.} 70 \end{subfigure} 71 \hspace{0.5cm} 72 \begin{subfigure}[h]{0.45\textwidth} 73 \centering 74 \includegraphics{hessian_profile_ratios_cpu.pdf} 75 \caption[Comparison of speedup from HVP to GVP.]{Comparison of the speedup from computation of the Hessian-vector product (HVP) versus the GGN-vector product (GVP) (top) and inverse HVP versus inverse GVP using the conjugate gradient method (bottom). Speedup is calculated as the ratio of the wall-clock time of the HVP to the GVP. We can see that the two methods have the same time complexity (up to a linear factor).} 76 \end{subfigure} 77 \caption{Performance comparison of different Hessian-vector products on CPU.} 78 \label{fig:hessian-profile-cpu} 79 \end{figure*} 80 81 \begin{figure*} 82 \centering 83 \begin{subfigure}[b]{0.7\textwidth} 84 \centering 85 \includegraphics{ablation/chisq_55k_0.1_1q_100precondpoints_cg.pdf} 86 \caption{\(Q=1\)} 87 \end{subfigure} 88 \begin{subfigure}[b]{0.7\textwidth} 89 \centering 90 \includegraphics{ablation/chisq_55k_0.1_2q_100precondpoints_cg.pdf} 91 \caption{\(Q=2\)} 92 \end{subfigure} 93 94 \begin{subfigure}[b]{0.7\textwidth} 95 \centering 96 \includegraphics{ablation/chisq_55k_0.1_3q_100precondpoints_cg.pdf} 97 \caption{\(Q=3\)} 98 \end{subfigure} 99 \begin{subfigure}[b]{0.7\textwidth} 100 \centering 101 \includegraphics{ablation/chisq_55k_0.1_4q_100precondpoints_cg.pdf} 102 \caption{\(Q=4\)} 103 \end{subfigure} 104 105 \begin{subfigure}[b]{0.7\textwidth} 106 \centering 107 \includegraphics{ablation/chisq_55k_0.1_5q_100precondpoints_cg.pdf} 108 \caption{\(Q=5\)} 109 \end{subfigure} 110 \begin{subfigure}[b]{0.7\textwidth} 111 \centering 112 \includegraphics{ablation/chisq_55k_0.1_10q_100precondpoints_cg.pdf} 113 \caption{\(Q=10\)} 114 \end{subfigure} 115 116 \begin{subfigure}[b]{0.7\textwidth} 117 \centering 118 \includegraphics{ablation/chisq_55k_0.1_20q_100precondpoints_cg.pdf} 119 \caption{\(Q=20\)} 120 \end{subfigure} 121 \caption[Chi-squared samples plots for ablation on MNIST.]{Chi-squared sample plots for visualising normality of 200 posterior samples from the full Laplace approximation on MNIST for a varying number of quadrature points \(Q\). Samples appear correctly distributed for \(Q \geq 5\), incorrectly distributed for \(Q < 4\), and borderline for \(Q = 4\).} 122 \label{fig:ablation-chisq} 123 \end{figure*} 124 125 \begin{figure*} 126 \begin{subfigure}[h]{0.45\textwidth} 127 \centering 128 \includegraphics[scale=0.9]{sin_posterior_predictive_samples.pdf} 129 \vspace{-0.7cm} 130 \caption{\(\alpha=70\)} 131 \end{subfigure} 132 \begin{subfigure}[h]{0.45\textwidth} 133 \centering 134 \includegraphics[scale=0.9]{sin_posterior_predictive_samples_bad.pdf} 135 \vspace{-0.7cm} 136 \caption{\(\alpha=1\)} 137 \end{subfigure} 138 \vspace{-0.3cm} 139 \caption[Laplace predictive posterior samples for a sine curve for varying prior precision.]{Laplace posterior predictive samples for a sine curve for different prior precisions \(\alpha\).} 140 \label{fig:sin-posterior-predictive-samples} 141 \end{figure*}