Kernel Conjugate Gradient Methods with Random Projections
This work addresses computational efficiency in kernel methods for machine learning, presenting an incremental improvement with specific theoretical guarantees.
The authors tackled the problem of kernel conjugate gradient methods for least-squares regression by incorporating random projections via randomized sketches and Nyström subsampling, proving optimal statistical results with generalization and computational advantages when projection dimension matches the effective dimension.
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ö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.