# Provable Bounds for Learning Some Deep Representations

arXiv: https://arxiv.org/abs/1310.6343 · HTML: https://mlsanity.com/paper/1310.6343/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Oct 2013.

## Built on by (most cited first, 14 of 14)

- [MIRACLE: Causally-Aware Imputation via Learning Missing Data Mechanisms](https://mlsanity.com/paper/2111.03187/) (2021)
- [From Local Pseudorandom Generators to Hardness of Learning](https://mlsanity.com/paper/2101.08303/) (2021)
- [Parameter identifiability of a deep feedforward ReLU neural network](https://mlsanity.com/paper/2112.12982/) (2021)
- [Local Identifiability of Deep ReLU Neural Networks: the Theory](https://mlsanity.com/paper/2206.07424/) (2022)
- [On the average-case complexity of learning output distributions of quantum circuits](https://mlsanity.com/paper/2305.05765/) (2023)
- [Why Do Local Methods Solve Nonconvex Problems?](https://mlsanity.com/paper/2103.13462/) (2021)
- [Privacy Vulnerability of Split Computing to Data-Free Model Inversion Attacks](https://mlsanity.com/paper/2107.06304/) (2021)
- [XnODR and XnIDR: Two Accurate and Fast Fully Connected Layers For Convolutional Neural Networks](https://mlsanity.com/paper/2111.10854/) (2021)
- [Learning Versatile Convolution Filters for Efficient Visual Recognition](https://mlsanity.com/paper/2109.09310/) (2021)
- [Is Stochastic Gradient Descent Near Optimal?](https://mlsanity.com/paper/2209.08627/) (2022)
- [Design and Implementation of A Soccer Ball Detection System with Multiple Cameras](https://mlsanity.com/paper/2302.00123/) (2023)
- [A Study on Broadcast Networks for Music Genre Classification](https://mlsanity.com/paper/2208.12086/) (2022)
- [Learning Spatially-Adaptive Squeeze-Excitation Networks for Image Synthesis and Image Recognition](https://mlsanity.com/paper/2112.14804/) (2021)
- [Surgical Foundation Model Leveraging Compression and Entropy Maximization for Image-Guided Surgical Assistance](https://mlsanity.com/paper/2506.01980/) (2025)

## Abstract (arXiv)

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 em 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 networks with random edge weights.