Kernel Conjugate Gradient Methods with Random Projections

Junhong Lin, Volkan CevherarXiv 2018 · arXiv

Abstract

Kernel methods are a cornerstone of non-parametric machine learning, yet their application to massive datasets is often hindered by $O(n^2)$ space and $O(n^3)$ time complexities. This paper introduces a computationally efficient framework for Kernel Conjugate Gradient Methods (KCGM) that integrates random projections—specifically randomized sketches and Nyström subsampling—with implicit regularization. We demonstrate that these "sketched" versions achieve optimal statistical accuracy while significantly reducing computational overhead. By utilizing a discrepancy-based early stopping rule, the proposed Projected-KCGM avoids the need for explicit penalty terms, matching minimax lower rates for regression tasks.

Introduction

Kernel methods provide a powerful framework for learning complex, non-linear relationships by mapping data into high-dimensional feature spaces. However, the practical utility of these methods is limited by the "curse of the kernel matrix": for a dataset of $n$ points, standard solvers typically require $O(n^2)$ memory to store the kernel matrix and $O(n^3)$ time to compute a solution.

While iterative solvers like the Conjugate Gradient (CG) method offer a path toward scalability, they still face significant hurdles as $n$ reaches the millions. Previous attempts to mitigate these costs often relied on random projections combined with explicit regularization, such as Kernel Ridge Regression (KRR). This research addresses a critical gap: whether random projections can be successfully combined with the implicit regularization of early-stopped CG to achieve both computational efficiency and optimal statistical generalization.

Methodology

Projected-KCGM

The authors propose Projected-KCGM, an algorithm that restricts the search for a solution to a lower-dimensional subspace $S$. By operating within this subspace, the algorithm avoids the full cost of the $n \times n$ kernel matrix. Two primary techniques are employed to construct this subspace:

  1. Randomized Sketches: The data is projected using a general random matrix (e.g., Gaussian or Subgaussian), compressing the information into an $m$-dimensional space.
  2. Nyström Subsampling: A subset of $m$ training points is randomly selected to serve as a basis for the entire dataset, a technique widely favored for its preservation of data structure.

Implicit Regularization via Early Stopping

Unlike traditional Ridge Regression, which uses an explicit penalty parameter ($\lambda$), Projected-KCGM relies on early stopping. The algorithm employs a "discrepancy rule," which terminates iterations once the training error reaches a specific threshold. This approach prevents the model from fitting noise in the data, ensuring that the final solution generalizes well to unseen samples.

Theoretical Contributions

The Effective Dimension Rule

A central finding of this work is the relationship between the sketch dimension $m$ and the "effective dimension" of the problem. The effective dimension is a measure of the task's underlying complexity. The authors prove that as long as $m$ is proportional to this effective dimension, the sketched algorithm achieves the same level of accuracy as a solver using the full, uncompressed dataset.

Closing the Theoretical Gap

The paper provides the first optimal capacity-dependent rates for classical KCGM in "well-conditioned" regimes for the non-attainable case—where the true target function does not reside perfectly within the kernel's hypothesis space. This confirms that early stopping is a mathematically rigorous substitute for explicit ridge penalties when combined with random projections.

Empirical Validation

To validate the theoretical bounds, the authors conducted numerical simulations using a 1D synthetic regression task ($y = |x - 0.5| - 0.5$) with Gaussian noise and a Sobolev kernel. The experiments, scaled up to $n = 1024$, demonstrated the following:

  • Computational Speedup: Space complexity was reduced from $O(n^2)$ to $O(m^2)$, and time complexity improved from $O(n^2 T)$ to $O(m^3 + m^2 T)$, where $m \ll n$.
  • Statistical Optimality: Both Sketched-KCGM and Nyström-KCGM achieved an error decay rate of $n^{-2/3}$. This matches the performance of the gold-standard Kernel Ridge Regression (KRR), proving that the compression does not degrade predictive power.

Conclusion and Future Work

This research demonstrates that Projected-KCGM is a viable, high-performance alternative for large-scale kernel learning. By combining the speed of random projections with the theoretical robustness of early stopping, the authors provide a framework that is both computationally lean and statistically optimal.

However, several avenues for future research remain. The current theoretical stopping rule requires a priori knowledge of constants like noise levels, which are often unknown in practice. Furthermore, while empirical results are promising, extending the theoretical analysis to include cross-validation for the sketched setting and testing the framework on high-dimensional, real-world datasets (e.g., genomics or climate modeling) are essential next steps for the field.

Summary updated

Abstract

We propose and study kernel conjugate gradient methods (KCGM) with random projections for least-squares regression over a separable Hilbert space. Considering two types of random projections generated by randomized sketches and Nystr\"{o}m subsampling, we prove optimal statistical results with respect to variants of norms for the algorithms under a suitable stopping rule. Particularly, our results show that if the projection dimension is proportional to the effective dimension of the problem, KCGM with randomized sketches can generalize optimally, while achieving a computational advantage. As a corollary, we derive optimal rates for classic KCGM in the well-conditioned regimes for the case that the target function may not be in the hypothesis space.
BibTeX
@misc{lin2018kernel,
  author = {Junhong Lin and Volkan Cevher},
  title = {{Kernel Conjugate Gradient Methods with Random Projections}},
  year = {2018},
  eprint = {1811.01760},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1811.01760},
}
Figure