Minimum complexity interpolation in random features models

Michael Celentano, Theodor Misiakiewicz, Andrea Montanari

Despite their many appealing properties, kernel methods are heavily affected by the curse of dimensionality. For instance, in the case of inner product kernels in ${\mathbb{R}}^d$, t…