Improper Deep Kernels
Venue
Proceedings of The 19th International Conference on Artificial Intelligence and Statististics. (2016)
Publication Year
2016
Authors
Uri Heinemann, Roi Livni, Elad Eban, Gal Elidan, Amir Globerson
BibTeX
Abstract
Neural networks have recently re-emerged as a powerful hypothesis class, yielding
impressive classification accuracy in multiple domains. However, their training is
a non-convex optimization problem which poses theoretical and practical challenges.
Here we address this difficulty by turning to ``improper'' learning of neural nets.
In other words, we learn a classifier that is not a neural net but is competitive
with the best neural net model given a sufficient number of training examples. Our
approach relies on a novel kernel construction scheme in which the kernel is a
result of integration over the set of all possible instantiation of neural models.
It turns out that the corresponding integral can be evaluated in closed-form via a
simple recursion. Thus we translate the non-convex, hard learning problem of a
neural net to a SVM with an appropriate kernel. We also provide sample complexity
results which depend on the stability of the optimal neural net.
