Optimal Rates of Sketchedregularized Algorithms for LeastSquares Regression over Hilbert Spaces
[edit]
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:31023111, 2018.
Abstract
We investigate regularized algorithms combining with projection for leastsquares 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 provide optimal, distributiondependent rates for sketched/Nyström regularized algorithms, considering both the attainable and nonattainable cases.
Related Material


