# Convergence rates of Kernel Conjugate Gradient for random design regression

arXiv: https://arxiv.org/abs/1607.02387 · HTML: https://mlsanity.com/paper/1607.02387/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jul 2016.

## Built on by (most cited first, 8 of 8)

- [Random Smoothing Regularization in Kernel Gradient Descent Learning](https://mlsanity.com/paper/2305.03531/) (2023)
- [From inexact optimization to learning via gradient concentration](https://mlsanity.com/paper/2106.05397/) (2021)
- [Towards Data-Algorithm Dependent Generalization: a Case Study on Overparameterized Linear Regression](https://mlsanity.com/paper/2202.06054/) (2022)
- [Adaptive Parameter Selection for Kernel Ridge Regression](https://mlsanity.com/paper/2312.05885/) (2023)
- [Adaptive Distributed Kernel Ridge Regression: A Feasible Distributed Learning Scheme for Data Silos](https://mlsanity.com/paper/2309.04236/) (2023)
- [Comparing regularisation paths of (conjugate) gradient estimators in ridge regression](https://mlsanity.com/paper/2503.05542/) (2025)
- [Beyond Cross-Validation: Adaptive Parameter Selection for Kernel-Based Gradient Descents](https://mlsanity.com/paper/2603.03401/) (2026)
- [Kernel-Based Distributed Q-Learning: A Scalable Reinforcement Learning Approach for Dynamic Treatment Regimes](https://mlsanity.com/paper/2302.10434/) (2023)

## Abstract (arXiv)

We prove statistical rates of convergence for kernel-based least squares regression from i.i.d. data using a conjugate gradient algorithm, where regularization against overfitting is obtained by early stopping. This method is related to Kernel Partial Least Squares, a regression method that combines supervised dimensionality reduction with least squares projection. Following the setting introduced in earlier related literature, we study so-called "fast convergence rates" depending on the regularity of the target regression function (measured by a source condition in terms of the kernel integral operator) and on the effective dimensionality of the data mapped into the kernel space. We obtain upper bounds, essentially matching known minimax lower bounds, for the L2 (prediction) norm as well as for the stronger Hilbert norm, if the true regression function belongs to the reproducing kernel Hilbert space. If the latter assumption is not fulfilled, we obtain similar convergence rates for appropriate norms, provided additional unlabeled data are available.