Kernel Conjugate Gradient Methods with Random Projections

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ö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.

Updating acknowledgments; Accepted version for Applied and Computational Harmonic Analysis

References in corpus (4)

• Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spaces
• Convergence rates of Kernel Conjugate Gradient for random design regression
• Optimal Convergence for Distributed Learning with Stochastic Gradient Methods and Spectral Algorithms
• Optimal Rates of Sketched-regularized Algorithms for Least-Squares Regression over Hilbert Spaces

Cited by in corpus (1)

• ParK: Sound and Efficient Kernel Ridge Regression by Feature Space Partitions