### Abstract

We investigate regularized algorithms combining with projection forleast-squares regression problem over a Hilbert space, covering nonparametricregression over a reproducing kernel Hilbert space. We prove convergenceresults with respect to variants of norms, under a capacity assumption on thehypothesis space and a regularity condition on the target function. As aresult, we obtain optimal rates for regularized algorithms with randomizedsketches, provided that the sketch dimension is proportional to the effectivedimension up to a logarithmic factor. As a byproduct, we obtain similar resultsfor Nystr\"{o}m regularized algorithms. Our results are the first ones withoptimal, distribution-dependent rates that do not have any saturation effectfor sketched/Nystr\"{o}m regularized algorithms, considering both theattainable and non-attainable cases.

### Introduction (beta)

None

### Conclusion (beta)

None