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

  • 2018-03-12 16:57:48
  • Junhong Lin, Volkan Cevher
  • 1


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)



Conclusion (beta)