Learning infinite layer networks without the kernel trick

Roi Livni, Daniel Carmon, Amir Globerson

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Infinite Layer Networks (ILN) have been proposed as an architecture that mimics neural networks while enjoying some of the advantages of kernel methods. ILN are networks that integrate over infinitely many nodes within a single hidden layer. It has been demonstrated by several authors that the problem of learning ILN can be reduced to the kernel trick, implying that whenever a certain integral can be computed analytically they are efficiently learnable. In this work we give an online algorithm for ILN, which avoids the kernel trick assumption. More generally and of independent interest, we show that kernel methods in general can be exploited even when the kernel cannot be efficiently computed but can only be estimated via sampling. We provide a regret analysis for our algorithm, showing that it matches the sample complexity of methods which have access to kernel values. Thus, our method is the first to demonstrate that the kernel trick is not necessary, as such, and random features suffice to obtain comparable performance.

Original languageEnglish (US)
Title of host publication34th International Conference on Machine Learning, ICML 2017
PublisherInternational Machine Learning Society (IMLS)
Pages3460-3469
Number of pages10
ISBN (Electronic)9781510855144
StatePublished - Jan 1 2017
Event34th International Conference on Machine Learning, ICML 2017 - Sydney, Australia
Duration: Aug 6 2017Aug 11 2017

Publication series

Name34th International Conference on Machine Learning, ICML 2017
Volume5

Other

Other34th International Conference on Machine Learning, ICML 2017
CountryAustralia
CitySydney
Period8/6/178/11/17

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Human-Computer Interaction
  • Software

Fingerprint Dive into the research topics of 'Learning infinite layer networks without the kernel trick'. Together they form a unique fingerprint.

  • Cite this

    Livni, R., Carmon, D., & Globerson, A. (2017). Learning infinite layer networks without the kernel trick. In 34th International Conference on Machine Learning, ICML 2017 (pp. 3460-3469). (34th International Conference on Machine Learning, ICML 2017; Vol. 5). International Machine Learning Society (IMLS).