Provable Bounds for Learning Some Deep Representations

Sanjeev Arora, Aditya Bhaskara, Rong Ge, Tengyu Ma

Type: Preprint

Publication Date: 2013-01-01

Citations: 236

DOI: https://doi.org/10.48550/arxiv.1310.6343

View Publication

Locations

arXiv (Cornell University) - View - PDF
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	Provable Bounds for Learning Some Deep Representations	2013	Sanjeev Arora Aditya Bhaskara Rong Ge Tengyu Ma
+	Provable approximation properties for deep neural networks	2016	Uri Shaham Alexander Cloninger Ronald R. Coifman
+	Computational Complexity of Learning Neural Networks: Smoothness and Degeneracy	2023	Amit Daniely Nathan Srebro Gal Vardi
+	A Provably Correct Algorithm for Deep Learning that Actually Works	2018	Eran Malach Shai Shalev‐Shwartz
+	Provable Methods for Training Neural Networks with Sparse Connectivity	2014	Hanie Sedghi Anima Anandkumar
+	Provable Methods for Training Neural Networks with Sparse Connectivity	2014	Hanie Sedghi Anima Anandkumar
+	Recovering the Lowest Layer of Deep Networks with High Threshold Activations	2019	Surbhi Goel Rina Panigrahy‎
+ PDF Chat	Generalization in Deep Learning	2022	Kenji Kawaguchi Yoshua Bengio Leslie Pack Kaelbling
+	Generalization in Deep Learning	2017	Kenji Kawaguchi Leslie Pack Kaelbling Yoshua Bengio
+	On the Learnability of Deep Random Networks	2019	Abhimanyu Das Sreenivas Gollapudi Ravi Kumar Rina Panigrahy‎
+	On the Learnability of Deep Random Networks	2019	Abhimanyu Das Sreenivas Gollapudi Ravi Kumar Rina Panigrahy‎
+ PDF Chat	A gentle introduction to deep learning for graphs	2020	Davide Bacciu Federico Errica Alessio Micheli Marco Podda
+	Width Provably Matters in Optimization for Deep Linear Neural Networks	2019	Simon S. Du Wei Hu
+ PDF Chat	Graph neural network outputs are almost surely asymptotically constant	2024	Sam Adam-Day Michael Benedikt İsmail İlkan Ceylan Ben Finkelshtein
+	Most Neural Networks Are Almost Learnable	2023	Amit Daniely Nathan Srebro Gal Vardi
+ PDF Chat	Robust and Provable Guarantees for Sparse Random Embeddings	2022	Maciej Skórski Alessandro Temperoni Martin Theobald
+ PDF Chat	Learning on Transformers is Provable Low-Rank and Sparse: A One-layer Analysis	2024	Hongkang Li Meng Wang Shuai Zhang Sijia Liu Pin‐Yu Chen
+ PDF Chat	Deep Graph Neural Networks with Shallow Subgraph Samplers	2020	Hanqing Zeng Muhan Zhang Yinglong Xia Ajitesh Srivastava Andrey Malevich Rajgopal Kannan Viktor K. Prasanna Long Jin Ren Chen
+	Deep Graph Neural Networks with Shallow Subgraph Samplers	2020	Hanqing Zeng Muhan Zhang Yinglong Xia Ajitesh Srivastava Rajgopal Kannan Viktor K. Prasanna Long Jin Andrey Malevich Chen Ren
+	Random Features Strengthen Graph Neural Networks	2021	Ryoma Sato Makoto Yamada Hisashi Kashima

Works That Cite This (114)

Action	Title	Year	Authors
+	Mad Max: Affine Spline Insights Into Deep Learning	2020	Randall Balestriero Richard G. Baraniuk
+ PDF Chat	Parameter identifiability of a deep feedforward ReLU neural network	2023	Joachim Bona-Pellissier François Bachoc François Malgouyres
+	Land Use Classification in Remote Sensing Images by Convolutional Neural Networks	2015	Marco Castelluccio Giovanni Poggi Carlo Sansone Luisa Verdoliva
+	Learning Boolean Circuits with Neural Networks	2019	Eran Malach Shai Shalev‐Shwartz
+	Prediction with a Short Memory	2016	Vatsal Sharan Sham M. Kakade Percy Liang Gregory Valiant
+	Efficient Black-box Assessment of Autonomous Vehicle Safety	2019	Justin Norden Matthew O’Kelly Aman Sinha
+ PDF Chat	Flexible Multilayer Sparse Approximations of Matrices and Applications	2016	Luc Le Magoarou Rémi Gribonval
+	Distribution-specific hardness of learning neural networks	2018	Ohad Shamir
+	Hardness of Learning Neural Networks with Natural Weights	2020	Amit Daniely Gal Vardi
+	On the Computational Efficiency of Training Neural Networks	2014	Roi Livni Shai Shalev‐Shwartz Ohad Shamir

Works Cited by This (12)

Action	Title	Year	Authors
+ PDF Chat	Combining geometry and combinatorics: A unified approach to sparse signal recovery	2008	Radu Berinde Anna C. Gilbert Piotr Indyk Howard Karloff Michael Strauss
+	A spectral algorithm for learning Hidden Markov Models	2012	Daniel Hsu Sham M. Kakade Tong Zhang
+ PDF Chat	Learning mixtures of spherical gaussians	2013	Daniel Hsu Sham M. Kakade
+ PDF Chat	Settling the Polynomial Learnability of Mixtures of Gaussians	2010	Ankur Moitra Gregory Valiant
+	New Algorithms for Learning Incoherent and Overcomplete Dictionaries	2013	Sanjeev Arora Rong Ge Ankur Moitra
+ PDF Chat	Learning Topic Models -- Going beyond SVD	2012	Sanjeev Arora Rong Ge Ankur Moitra
+ PDF Chat	Representation Learning: A Review and New Perspectives	2013	Yoshua Bengio Aaron Courville P. M. Durai Raj Vincent
+ PDF Chat	The Noise-Sensitivity Phase Transition in Compressed Sensing	2011	David L. Donoho Arian Maleki Andrea Montanari
+ PDF Chat	A Spectral Algorithm for Latent Dirichlet Allocation	2014	Anima Anandkumar Dean P. Foster Daniel Hsu Sham M. Kakade Yi-Kai Liu
+	A Provably Efficient Algorithm for Training Deep Networks	2013	Roi Livni Shai Shalev‐Shwartz Ohad Shamir