Abstract

Generalization performance of classifiers in deep learning has recently become a subject of intense study. Deep models, which are typically heavily over-parametrized, tend to fit the training dat exactly. Despite this “overfitting”, they perform well on test data, a phenomenon not yet fully understood. The first point of our paper is that strong performance of overfitted classifiers is not a unique feature of deep learning. Using six realworld and two synthetic datasets, we establish experimentally that kernel machines trained to have zero classification error or near zero regression e ror (interpolation) perform very well on test data. We proceed to give a lower bound on the norm of zero loss solutions for smooth kernels, showing that they increase nearly exponentially with data size. None of the existing bounds produce nontrivial results for interpolating solutions. We als show experimentally that (non-smooth) Laplacian kernels easily fit random labels, a finding that pa allels results recently reported for ReLU neural networks. In contrast, fitting noisy data requires many more epochs for smooth Gaussian kernels. Similar performance of overfitted Laplacian and Gaussian classifiers on test, suggests that general ization is tied to the properties of the kernel fun tion rather than the optimization process. Some key phenomena of deep learning are manifested similarly in kernel methods in the modern “overfitted” regime. The combination of the experimental and theoretical results presented in this paper indicates a need for new theoretical ideas for understanding properties of classical kernel methods. We argue that progress on understanding