Sanjeev Arora,
Aditya Bhaskara,
Rong Ge,
Tengyu Ma
;
Proceedings of the 31st International Conference on Machine Learning, PMLR 32(1):584-592, 2014.
Abstract
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 neural net 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.
@InProceedings{pmlr-v32-arora14,
title = {Provable Bounds for Learning Some Deep Representations},
author = {Sanjeev Arora and Aditya Bhaskara and Rong Ge and Tengyu Ma},
booktitle = {Proceedings of the 31st International Conference on Machine Learning},
pages = {584--592},
year = {2014},
editor = {Eric P. Xing and Tony Jebara},
volume = {32},
number = {1},
series = {Proceedings of Machine Learning Research},
address = {Bejing, China},
month = {22--24 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v32/arora14.pdf},
url = {http://proceedings.mlr.press/v32/arora14.html},
abstract = {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 neural net 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.}
}
%0 Conference Paper
%T Provable Bounds for Learning Some Deep Representations
%A Sanjeev Arora
%A Aditya Bhaskara
%A Rong Ge
%A Tengyu Ma
%B Proceedings of the 31st International Conference on Machine Learning
%C Proceedings of Machine Learning Research
%D 2014
%E Eric P. Xing
%E Tony Jebara
%F pmlr-v32-arora14
%I PMLR
%J Proceedings of Machine Learning Research
%P 584--592
%U http://proceedings.mlr.press
%V 32
%N 1
%W PMLR
%X 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 neural net 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.
TY - CPAPER
TI - Provable Bounds for Learning Some Deep Representations
AU - Sanjeev Arora
AU - Aditya Bhaskara
AU - Rong Ge
AU - Tengyu Ma
BT - Proceedings of the 31st International Conference on Machine Learning
PY - 2014/01/27
DA - 2014/01/27
ED - Eric P. Xing
ED - Tony Jebara
ID - pmlr-v32-arora14
PB - PMLR
SP - 584
DP - PMLR
EP - 592
L1 - http://proceedings.mlr.press/v32/arora14.pdf
UR - http://proceedings.mlr.press/v32/arora14.html
AB - 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 neural net 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.
ER -
Arora, S., Bhaskara, A., Ge, R. & Ma, T.. (2014). Provable Bounds for Learning Some Deep Representations. Proceedings of the 31st International Conference on Machine Learning, in PMLR 32(1):584-592
This site last compiled Mon, 16 Jul 2018 21:44:33 +0000