Abstract
The runtime for Kernel Partial Least Squares (KPLS) to compute the fit is quadratic in the number of examples. However, the necessity of obtaining sensitivity measures as degrees of freedom for model selection or confidence intervals for more detailed analysis requires cubic runtime, and thus constitutes a computational bottleneck in real-world data analysis. We propose a novel algorithm for KPLS which not only computes (a) the fit, but also (b) its approximate degrees of freedom and (c) error bars in quadratic runtime. The algorithm exploits a close connection between Kernel PLS and the Lanczos algorithm for approximating the eigenvalues of symmetric matrices, and uses this approximation to compute the trace of powers of the kernel matrix in quadratic runtime.
Introduction
Kernel Partial Least Squares (KPLS) is a powerful technique for supervised dimensionality reduction and non-linear regression. Its primary advantage is efficiency: the model fit can be computed using iterative matrix-vector multiplications, resulting in a complexity of $O(n^2)$ relative to the number of samples $n$.
However, in practical applications, a point estimate is rarely sufficient. Engineers and researchers require model selection (e.g., tuning kernel parameters or the number of components) and uncertainty quantification. These tasks rely on calculating the Degrees of Freedom (DoF) and prediction error bars. Traditionally, these sensitivity measures require computing the trace of powers of the kernel matrix or complex derivatives, operations that scale cubically ($O(n^3)$). This computational bottleneck makes thorough statistical analysis prohibitive for large datasets. This paper introduces a method to perform these calculations in $O(n^2)$ time, matching the speed of the initial model fit.
Methodology: Leveraging the Lanczos Connection
The core innovation lies in identifying a deep mathematical link between KPLS and the Lanczos algorithm, a standard numerical method for approximating the eigenvalues of large symmetric matrices.
Ritz Values for Efficient DoF Calculation
The authors demonstrate that the KPLS process implicitly generates a small $m \times m$ tridiagonal matrix $D$, where $m$ is the number of latent components. The eigenvalues of $D$, known as Ritz values, serve as highly accurate approximations for the eigenvalues of the full $n \times n$ kernel matrix. By utilizing these Ritz values, the "trace of powers" of the kernel matrix—the primary $O(n^3)$ bottleneck—can be approximated in negligible time. Crucially, since $D$ is a byproduct of the standard KPLS fitting iterations, this approximation is obtained essentially "for free."
Quadratic-Time Confidence Intervals
To compute confidence intervals, one must determine the derivative of the KPLS solution with respect to the target variables. The authors derived a novel formulation for this derivative that avoids expensive matrix-matrix multiplications. Instead, it utilizes a sequence of matrix-vector products, ensuring the entire process remains within $O(n^2)$ complexity.
Experimental Evaluation
The proposed algorithm was evaluated on two primary benchmarks:
- Synthetic "Sinc" Function: A 1D regression task used to validate the accuracy of the approximate DoF and model selection criteria across various kernel widths.
- "kin" Dataset: An 8-dimensional robotic arm dataset (8,192 samples) from the Delve repository, used to benchmark runtime performance as a function of sample size.
Key Results and Discussion
The experiments yielded two major findings: massive computational speedups and high approximation fidelity.
Performance and Fidelity
In runtime benchmarks on the "kin" dataset, the exact $O(n^3)$ calculation exhibited the expected steep exponential growth. In contrast, the $O(n^2)$ approximation scaled much more gracefully. For instance, at $n=1,000$, the approximation was nearly 10 times faster than the exact method, a gap that widens significantly as $n$ grows.
Despite the speedup, the approximation remains highly accurate. As shown in the figure below, the approximate DoF and the resulting generalized Minimum Description Length (gMDL) criteria closely track the exact values across different kernel widths, provided a sufficient number of components ($M$) are used for the approximation.
Insights on Spectral Decay
The effectiveness of the Lanczos approximation is tied to the spectral decay of the kernel matrix. For kernels with rapidly decaying eigenvalues, such as the RBF (Gaussian) kernel, the Ritz values converge quickly, allowing for high-precision DoF estimates with very few components. This confirms that "statistical thoroughness" does not need to be more computationally expensive than the initial model fit.
Conclusion and Future Work
This work successfully removes the cubic-time bottleneck for KPLS model selection and sensitivity analysis. By reframing these problems within the context of Krylov subspace methods, the authors provide a framework for $O(n^2)$ KPLS that includes both point estimates and reliable uncertainty measures.
Limitations: The approximation's accuracy is sensitive to the kernel's spectral properties; kernels with "flat" spectra (e.g., very small RBF widths) may require more components. Additionally, while time complexity is reduced, $O(n^2)$ memory is still required to store the kernel matrix. Future research could explore extending these techniques to Kernel PLS for classification (KPLS-DA).
Summary updated