Warm-Starting Iterative Gaussian Processes for Faster Sequential Inference

Technical Summary: Warm-Starting Iterative Gaussian Processes for Faster Sequential Inference

Problem Statement
Gaussian Processes (GPs) are powerful non-parametric models for regression, classification, and Bayesian optimization, yet their scalability is limited by the $O(n^3)$ cost of inverting the covariance matrix to compute the posterior. While iterative solvers (e.g., Conjugate Gradients, Stochastic Gradient Descent, Alternating Projections) offer a way to avoid cubic costs by approximating the solution, they typically require many iterations to converge. In sequential settings—such as active learning, online prediction, and Bayesian optimization—where data arrives incrementally and the posterior must be updated frequently, the standard "cold-start" approach (initializing all weights to zero and discarding previous computation) becomes a bottleneck. This inefficiency limits the efficacy of iterative GPs in dynamic environments.

Methodology
The paper proposes three "warm-start" strategies to initialize iterative linear solvers when updating a GP posterior with new data points. Instead of solving the extended linear system from scratch, these methods leverage the solution ($u_1$) of the previous, smaller linear system to initialize the weights ($v$) of the new, larger system.

The problem is framed as solving an extended linear system $Hv = b$, where the matrix $H$ and vector $b$ are partitioned to include existing data (block 1) and new data (block 2). The three proposed initialization methods are:

1. Naïve Warm-Start: The weights corresponding to the original data ($v_1$) are initialized to the previous solution ($u_1$), while the weights for the new data ($v_2$) are initialized to zero.
   $$v \leftarrow \begin{bmatrix} u_1 \\ 0 \end{bmatrix}$$
2. Residual Line Search: This method improves upon the naïve approach by performing a line search to determine the optimal scalar $\alpha$ for the new weights ($v_2$) in the direction of the residual. This minimizes the quadratic objective given the fixed $v_1 = u_1$.
   $$v_2 = \alpha^* r, \quad \text{where } r = b_2 - H_{12}^\top u_1 \text{ and } \alpha^* = \frac{r^\top r}{r^\top H_{22} r}$$
3. Marginal System Solve: The most complex method, which solves a smaller marginal linear system ($H_{22}v_2 = r$) to find the optimal $v_2$ that minimizes the objective given $v_1 = u_1$.
   $$v_2 = H_{22}^{-1} r$$

Theoretical Analysis
The authors provide theoretical support using the Reproducing Kernel Hilbert Space (RKHS) distance, defined as $d^2 = (v - v^*)^\top H (v - v^*)$, where $v^*$ is the exact solution. They demonstrate that:

• The naïve warm-start strictly reduces the initial RKHS distance compared to a cold-start ($d^2_{cold} - d^2_{naïve} \geq 0$).
• Both the residual line search and marginal system solve further reduce this distance ($d^2_{naïve} > d^2_{line-search} > d^2_{marginal-solve}$).
• Reducing the RKHS distance is equivalent to reducing the initial residual of the linear system, which directly correlates with fewer iterations required for convergence.

Key Contributions and Results
The paper introduces these three initialization strategies and validates them through theoretical analysis and empirical experiments on regression benchmarks and Bayesian optimization tasks.

• Regression Experiments: Using datasets from the UCI repository (e.g., 3droad, protein, buzz), the authors compared the number of iterations required for convergence against a cold-start baseline.

  • Speed-ups: When solving to a specific tolerance, warm-starting achieved speed-ups of up to 1.4× for Conjugate Gradients (CG), 1.5× for Stochastic Gradient Descent (SGD), and 4.0× for Alternating Projections (AP).
  • Extreme Cases: For AP, speed-ups reached up to 19× on certain datasets, particularly when the ratio of new data to existing data is small.
  • Accuracy: Under fixed compute budgets (limited iterations), warm-starting produced more accurate posterior estimates, reducing the final residual norm.

• Bayesian Optimization (Parallel Thompson Sampling): In a parallel Thompson sampling experiment with a fixed compute budget, the methods were evaluated on their ability to maximize an objective function.

  • Performance Gains: The warm-start methods improved the final maximum value found on the objective function by up to 13% for CG, 46% for SGD, and 10% for AP compared to cold-starting.
  • Accumulated Progress: The results indicated that solver progress accumulates over multiple sequential solves when warm-starting, rather than resetting, leading to more accurate posterior samples and better optimization performance.

Significance
The paper establishes warm-starting as a simple, effective, and broadly applicable tool for scaling Gaussian processes in sequential settings. By exploiting solutions from smaller linear systems, these methods substantially speed up convergence without requiring sparse approximations that sacrifice accuracy. The authors claim that this approach directly addresses the scalability bottleneck in sequential decision-making tasks, allowing for more frequent and accurate posterior updates within the same computational constraints. The methods are presented as practical enhancements that can be integrated with existing iterative solvers (CG, SGD, AP) to improve the efficiency of GP-based applications.