Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration

Song Mei, Theodor Misiakiewicz, Andrea Montanari

Consider the classical supervised learning problem: we are given data $(y_i,{\mathbf{x}}_i)$, $i\le n$, with $y_i$ a response and ${\mathbf{x}}_i\in \mathcal{X}$ a covariate…