Provable Bounds for Learning Some Deep Representations

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^{\gamma }$ for some $\gamma <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.

The first 18 pages serve as an extended abstract and a 36 pages long technical appendix follows

References in corpus (3)

• A Spectral Algorithm for Latent Dirichlet Allocation
• New Algorithms for Learning Incoherent and Overcomplete Dictionaries
• Learning mixtures of spherical Gaussians: moment methods and spectral decompositions

Cited by in corpus (70)

• Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding
• Going Deeper in Facial Expression Recognition using Deep Neural Networks
• A Mean Field View of the Landscape of Two-Layers Neural Networks
• Land Use Classification in Remote Sensing Images by Convolutional Neural Networks
• XNOR-Net: ImageNet Classification Using Binary Convolutional Neural Networks
• Convergence Analysis of Two-layer Neural Networks with ReLU Activation
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Provable approximation properties for deep neural networks
• Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity
• Deep Neural Networks with Random Gaussian Weights: A Universal Classification Strategy?
• Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks using Tensor Methods
• Learning One-hidden-layer Neural Networks with Landscape Design
• On the Convergence Rate of Training Recurrent Neural Networks
• AdaNet: Adaptive Structural Learning of Artificial Neural Networks
• DeepSZ: A Novel Framework to Compress Deep Neural Networks by Using Error-Bounded Lossy Compression
• Efficient Black-box Assessment of Autonomous Vehicle Safety
• Flexible Multi-layer Sparse Approximations of Matrices and Applications
• Why are deep nets reversible: A simple theory, with implications for training
• Scalable End-to-End Autonomous Vehicle Testing via Rare-event Simulation
• More Algorithms for Provable Dictionary Learning
• Convolutional Neural Networks Analyzed via Convolutional Sparse Coding
• Mean Field Limit of the Learning Dynamics of Multilayer Neural Networks
• Score Function Features for Discriminative Learning: Matrix and Tensor Framework
• Greedy Layerwise Learning Can Scale to ImageNet
• On the Connection Between Learning Two-Layers Neural Networks and Tensor Decomposition
• Sparse Matrix Factorization
• A Brain-inspired Algorithm for Training Highly Sparse Neural Networks
• Learning Halfspaces and Neural Networks with Random Initialization
• Provable Algorithms for Inference in Topic Models
• A Probabilistic Framework for Deep Learning
• On the energy landscape of deep networks
• Variational Inference to Measure Model Uncertainty in Deep Neural Networks
• Towards Interpretable R-CNN by Unfolding Latent Structures
• Learning Two Layer Rectified Neural Networks in Polynomial Time
• Deep Learning for Image Denoising: A Survey
• Learnability and Robustness of Shallow Neural Networks Learned With a Performance-Driven BP and a Variant PSO For Edge Decision-Making
• Learning Versatile Convolution Filters for Efficient Visual Recognition
• Weight Sharing is Crucial to Succesful Optimization
• Interpreting Deep Learning: The Machine Learning Rorschach Test?
• Deep Learning and Hierarchal Generative Models
• Learning computationally efficient dictionaries and their implementation as fast transforms
• Deep Stochastic Configuration Networks with Universal Approximation Property
• Fast Neural Architecture Construction using EnvelopeNets
• Hardness of Learning Neural Networks with Natural Weights
• Sparsifying Neural Network Connections for Face Recognition
• AOGNets: Compositional Grammatical Architectures for Deep Learning
• Prediction with a Short Memory
• Saec: Similarity-Aware Embedding Compression in Recommendation Systems
• Disentanglement for Discriminative Visual Recognition
• On the average-case complexity of learning output distributions of quantum circuits
• On the Regret Minimization of Nonconvex Online Gradient Ascent for Online PCA
• Walking the Tightrope: An Investigation of the Convolutional Autoencoder Bottleneck
• RePr: Improved Training of Convolutional Filters
• Improving training of deep neural networks via Singular Value Bounding
• Randomness in Deconvolutional Networks for Visual Representation
• Nonasymptotic Guarantees for Spiked Matrix Recovery with Generative Priors
• From Local Pseudorandom Generators to Hardness of Learning
• Learning Combinations of Sigmoids Through Gradient Estimation
• Spectral Sparse Representation for Clustering: Evolved from PCA, K-means, Laplacian Eigenmap, and Ratio Cut
• Learning Boolean Circuits with Neural Networks
• Full-Stack Filters to Build Minimum Viable CNNs
• Recursive Sketches for Modular Deep Learning
• Autoencoders Learn Generative Linear Models
• Minimally Supervised Feature Selection for Classification (Master's Thesis, University Politehnica of Bucharest)
• Unsupervisedly Learned Representations: Should the Quest be Over?
• Recurrent Residual Module for Fast Inference in Videos
• Span Recovery for Deep Neural Networks with Applications to Input Obfuscation
• Recovering the Lowest Layer of Deep Networks with High Threshold Activations
• Distributed Training of Deep Neural Networks with Theoretical Analysis: Under SSP Setting
• Nonparametric Learning of Two-Layer ReLU Residual Units