With the emergence of large-scale data, there is a massive surge in machine learning (ML) applications. In many of these applications, uncertainty calibration and interpretability of ML predictions are crucial. Gaussian processes (GPs) allow for the learning of non-parametric models with uncertainty and interpretability of prediction. However, a well-known limitation of GPs is their running time. Inference and learning for GPs require performing linear algebraic operations (LAOs) (e.g., matrix inversion and computing log determinants) on an n x n kernel matrix, where n is the number of training data points. Naive methods for the exact computation of these LAOs require $\Theta(n^3)$ time, severely prohibiting their application to large-scale problems.
This thesis focuses on developing fast algorithms for accelerating LAOs mentioned above, which are essential for inference and learning for GPs. Initially, we investigate the structured kernel interpolation (SKI) framework, employing a dense grid and iterative algorithms to expedite LAOs. The iterative algorithms can perform LAOs utilizing a sequence of kernel matrix-vector multiplications (MVMs). First, we present a novel and fast iterative algorithm for the SKI framework for GP problems. After a single $\O(n)$ time computation, we show that the LAOs can be entirely independent of n, yielding speedups in GP inference for several datasets in low dimensions. Unfortunately, SKI scales poorly in the dimension of the input points since the dense grid size grows exponentially with the input dimension. Since sparse grids enable accurate interpolation with slower growth in the number of points relative to dimension, we introduce a novel MVM algorithm for the sparse grid kernel matrix, thereby facilitating the use of sparse grids with SKI.
Finally, we investigate the application of GPs in bandit algorithms,
specifically aimed at identifying the optimal top-k ranking of items chosen from a list of available items. Contrary to previous studies, we introduce a contextual bandit algorithm that employs GPs with Kendall kernels, eliminating the need for restrictive assumptions commonly associated with reward or bandit feedback to deal with the combinatorial number of arms. Moreover, we present a fast algorithm for performing LAOs with the kernel matrix on top-k rankings by leveraging a sparse feature representation of the Kendall kernel.
Advisor: Daniel Sheldon