Timezone: »

Optimal Rates of Sketched-regularized Algorithms for Least-Squares Regression over Hilbert Spaces
Junhong Lin · Volkan Cevher

Wed Jul 11 09:15 AM -- 12:00 PM (PDT) @ Hall B #119

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\"{o}m regularized algorithms. Our results provide optimal, distribution-dependent rates for sketched/Nystr\"{o}m regularized algorithms, considering both the attainable and non-attainable cases.

Author Information

Junhong Lin (EPFL)
Volkan Cevher (EPFL)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors