Optimal Rates of Sketched-regularized Algorithms for Least-Squares Regression over Hilbert Spaces
This work provides foundational theoretical guarantees for sketched and Nyström regularized algorithms in nonparametric regression, addressing a key bottleneck in scalable machine learning for researchers and practitioners.
The paper tackles the problem of least-squares regression over Hilbert spaces by analyzing regularized algorithms combined with projection, such as randomized sketches and Nyström methods, and proves optimal convergence rates without saturation effects, achieving rates that depend on the sketch dimension being proportional to the effective dimension up to a logarithmic factor.
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öm regularized algorithms. Our results are the first ones with optimal, distribution-dependent rates that do not have any saturation effect for sketched/Nyström regularized algorithms, considering both the attainable and non-attainable cases.