Provable bounds for learning some deep representations

Sanjeev Arora, Aditya Bhaskara, Rong Ge, Tengyu Ma

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

54 Scopus citations

Abstract

2014 We give algorithms with provable guarantees that learn a class of deep nets in the generative model view popularized by Hinton and others. Our generative model is an n node multilayer network that has degree at most nγ for some γ < 1 and each edge has a random edge weight in [-1,1]. Our algorithm learns almost all networks in this class with polynomial running time. The sample complexity is quadratic or cubic depending upon the details of the model. The algorithm uses layerwise learning. It is based upon a novel idea of observing correlations among features and using these to infer the underlying edge structure via a global graph recovery procedure. The analysis of the algorithm reveals interesting structure of neural nets with random edge weights.

Original languageEnglish (US)
Title of host publication31st International Conference on Machine Learning, ICML 2014
PublisherInternational Machine Learning Society (IMLS)
Pages883-891
Number of pages9
ISBN (Electronic)9781634393973
StatePublished - Jan 1 2014
Event31st International Conference on Machine Learning, ICML 2014 - Beijing, China
Duration: Jun 21 2014Jun 26 2014

Publication series

Name31st International Conference on Machine Learning, ICML 2014
Volume1

Other

Other31st International Conference on Machine Learning, ICML 2014
CountryChina
CityBeijing
Period6/21/146/26/14

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Computer Networks and Communications
  • Software

Fingerprint Dive into the research topics of 'Provable bounds for learning some deep representations'. Together they form a unique fingerprint.

  • Cite this

    Arora, S., Bhaskara, A., Ge, R., & Ma, T. (2014). Provable bounds for learning some deep representations. In 31st International Conference on Machine Learning, ICML 2014 (pp. 883-891). (31st International Conference on Machine Learning, ICML 2014; Vol. 1). International Machine Learning Society (IMLS).