# Optimal Rates of Sketched-regularized Algorithms for Least-Squares Regression over Hilbert Spaces

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Mar 2018.

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

- [Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learning](https://mlsanity.com/paper/2202.04005/) (2022)
- [Mutual Information Learned Regressor: an Information-theoretic Viewpoint of Training Regression Systems](https://mlsanity.com/paper/2211.12685/) (2022)
- [Dirac-Frenkel dynamics with inertia for nonlinearly parametrized solutions of evolution problems](https://mlsanity.com/paper/2606.24769/) (2026)

## Abstract (arXiv)

We investigate regularized algorithms combining with projection for least-squares regression problem over a Hilbert space, covering nonparametric regression over a reproducing kernel Hilbert space. We prove convergence results with respect to variants of norms, under a capacity assumption on the hypothesis space and a regularity condition on the target function. As a result, we obtain optimal rates for regularized algorithms with randomized sketches, provided that the sketch dimension is proportional to the effective dimension up to a logarithmic factor. As a byproduct, we obtain similar results for Nystr"om regularized algorithms. Our results are the first ones with optimal, distribution-dependent rates that do not have any saturation effect for sketched/Nystr"om regularized algorithms, considering both the attainable and non-attainable cases.