Accelerated training of Gaussian processes using banded square exponential covariances

Technical Summary: Accelerated Training of Gaussian Processes Using Banded Square Exponential Covariances

Problem Statement
Standard Gaussian Process (GP) regression faces a computational bottleneck due to the $O(n^3)$ complexity required to invert the covariance matrix $K_{f,f} + \sigma_n^2 I$ during training and inference. While sparse GP methods (e.g., Variational Free Energy (VFE) and Fully Independent Training Conditional (FITC)) reduce this complexity to $O(nm^2)$ by introducing $m \ll n$ inducing variables, they often require a large number of inducing points to model long time-series accurately. This requirement can negate the computational gains, particularly when the latent function exhibits complex structures that global inducing points fail to capture efficiently.

Methodology: Banded Training Covariance (BTC)
The authors propose a novel approach termed Banded Training Covariance (BTC), which exploits the inherent approximate sparsity of the Square Exponential (SE) kernel. In 1D settings with SE kernels, pairwise covariances decay exponentially to zero as the distance between points increases.

1. Banded Approximation: Instead of using inducing variables, BTC replaces the full covariance matrix $K_{f,f}$ with a $k$-banded approximation $L_k(K_{f,f})$. The operator $L_k$ sets all entries $A_{ij}$ to zero where $|i-j| > k$, effectively assuming that observations are uncorrelated beyond a specific bandwidth $k$.
2. Computational Efficiency: By enforcing this banded structure, the inverse and log-determinant required for the negative log-likelihood (NLL) can be computed via LU or Cholesky decomposition at a reduced cost of $O(nk^2)$, avoiding the introduction of variational parameters.
3. Theoretical Guarantees: The paper provides a rigorous theoretical framework to determine the optimal bandwidth $k$ that ensures:
   • Positive Definiteness: The approximated matrix $L_k(K_{f,f}) + \sigma_n^2 I$ remains symmetric and positive definite, a prerequisite for valid probabilistic modeling and numerical stability.
   • Valid Predictive Distribution: The resulting posterior predictive covariance remains positive definite.
   • Independence from Sample Size: Crucially, the derived bound for $k$ depends on kernel hyperparameters (signal variance $\sigma^2$, length-scale $\ell$) and noise variance $\sigma_n^2$, but not on the number of observations $n$. This allows the method to scale to long time-series without increasing the bandwidth proportionally.

Key Contributions

• Novel Sparse Formulation: The introduction of BTC, a method that achieves sparse GP efficiency without inducing variables, relying instead on the structural sparsity of the SE kernel.
• Theoretical Bounds: The derivation of Lemma 3.1 and Theorem 3.2, which provide explicit conditions and a formula (Corollary 3.3) for selecting the bandwidth $k$ to guarantee positive definiteness for SE kernels with noise.
• Empirical Validation: Comprehensive experiments demonstrating that BTC matches the accuracy of full GPs while significantly outperforming standard sparse methods (VFE and FITC) in terms of runtime and predictive performance on real-world datasets.

Experimental Results
The authors evaluated BTC on two real-world datasets: the monthly sunspots dataset (3,315 points) and the Helsinki neonatal EEG dataset (4,000 points).

• Performance vs. Runtime: In terms of Normalized Mean Squared Error (NMSE) and Negative Log Predictive Density (NLPD), BTC achieved results nearly identical to exact full GPs.
• Comparison with Benchmarks: BTC consistently outperformed both VFE and FITC across all tested configurations of inducing points ($m$) and bandwidths ($k$).
• Robustness to $k$: The method demonstrated robust performance across a range of valid bandwidths. The theoretical choice of $k$ (derived from Corollary 3.3) was shown to be sufficient to maintain positive definiteness and high accuracy, confirming that increasing $k$ beyond this theoretical bound yields negligible accuracy gains at the cost of higher computational complexity.
• Validation of Theory: Experiments on synthetic data confirmed that the theoretically derived $k$ values successfully preserved positive definiteness during training, even when hyperparameters varied.

Significance and Claims
The paper claims that BTC offers a principled, parameter-free alternative to inducing-point methods for 1D GP regression with SE kernels. By leveraging the exponential decay of the kernel, BTC achieves the computational efficiency of sparse methods ($O(nk^2)$) while maintaining the accuracy of full GPs. The authors emphasize that their approach eliminates the need to optimize variational parameters (inducing points) and provides a theoretically grounded rule for selecting the bandwidth that scales independently of the dataset size.

The authors note that the current method is restricted to the SE kernel and assumes a fixed bandwidth during optimization. They identify extending the approach to higher dimensions and other kernels as key future work to broaden its practical applicability.