Recovery Guarantees for One-hidden-layer Neural Networks

Abstract

In this paper, we consider regression problems with one-hidden-layer neural networks (1NNs). We distill some properties of activation functions that lead to $localstrongconvexity$ in the neighborhood of the ground-truth parameters for the 1NN squared-loss objective. Most popular nonlinear activation functions satisfy the distilled properties, including rectified linear units (ReLUs), leaky ReLUs, squared ReLUs and sigmoids. For activation functions that are also smooth, we show $locallinearconvergence$ guarantees of gradient descent under a resampling rule. For homogeneous activations, we show tensor methods are able to initialize the parameters to fall into the local strong convexity region. As a result, tensor initialization followed by gradient descent is guaranteed to recover the ground truth with sample complexity $d\cdot \log (1/\epsilon )\cdot \mathrm{poly}(k,\lambda )$ and computational complexity $n\cdot d\cdot \mathrm{poly}(k,\lambda )$ for smooth homogeneous activations with high probability, where $d$ is the dimension of the input, $k$ ($k\le d$) is the number of hidden nodes, $\lambda$ is a conditioning property of the ground-truth parameter matrix between the input layer and the hidden layer, $\epsilon$ is the targeted precision and $n$ is the number of samples. To the best of our knowledge, this is the first work that provides recovery guarantees for 1NNs with both sample complexity and computational complexity $linear$ in the input dimension and $logarithmic$ in the precision.

arXiv commentICML 2017

References in corpus (9)

• Breaking the Curse of Dimensionality with Convex Neural Networks
• Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks using Tensor Methods
• On the Expressive Power of Deep Neural Networks
• Distribution-Specific Hardness of Learning Neural Networks
• Deep Learning without Poor Local Minima
• Most tensor problems are NP-hard
• Low Rank Approximation with Entrywise ${\ell }_1$-Norm Error
• Deep Online Convex Optimization with Gated Games
• Provable learning of Noisy-or Networks

Cited by in corpus (87)

• A Mean Field View of the Landscape of Two-Layers Neural Networks
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Non-convex Optimization for Machine Learning
• Convergence Analysis of Two-layer Neural Networks with ReLU Activation
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Gradient Descent Finds Global Minima of Deep Neural Networks
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• Towards Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learning
• Learning ReLU Networks on Linearly Separable Data: Algorithm, Optimality, and Generalization
• Learning One-hidden-layer Neural Networks with Landscape Design
• On the Convergence Rate of Training Recurrent Neural Networks
• Gradient Descent Maximizes the Margin of Homogeneous Neural Networks
• Self-Training: A Survey
• What Can ResNet Learn Efficiently, Going Beyond Kernels?
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimization
• Understanding Straight-Through Estimator in Training Activation Quantized Neural Nets
• Depth with Nonlinearity Creates No Bad Local Minima in ResNets
• Denoising and Regularization via Exploiting the Structural Bias of Convolutional Generators
• On the loss landscape of a class of deep neural networks with no bad local valleys
• ReduNet: A White-box Deep Network from the Principle of Maximizing Rate Reduction
• Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
• The Gaussian equivalence of generative models for learning with shallow neural networks
• Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound
• An Improved Analysis of Training Over-parameterized Deep Neural Networks
• Understanding the Loss Surface of Neural Networks for Binary Classification
• SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data
• Mean Field Limit of the Learning Dynamics of Multilayer Neural Networks
• On the Decision Boundary of Deep Neural Networks
• Risk Bounds for High-dimensional Ridge Function Combinations Including Neural Networks
• On the Benefit of Width for Neural Networks: Disappearance of Bad Basins
• A Generalized Neural Tangent Kernel Analysis for Two-layer Neural Networks
• On Learning Over-parameterized Neural Networks: A Functional Approximation Perspective
• Porcupine Neural Networks: (Almost) All Local Optima are Global
• On the Connection Between Learning Two-Layers Neural Networks and Tensor Decomposition
• Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced
• Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problems
• A Provably Correct Algorithm for Deep Learning that Actually Works
• Can SGD Learn Recurrent Neural Networks with Provable Generalization?
• Tensor Methods for Additive Index Models under Discordance and Heterogeneity
• Learning Two Layer Rectified Neural Networks in Polynomial Time
• The Multilinear Structure of ReLU Networks
• How Many Samples are Needed to Estimate a Convolutional or Recurrent Neural Network?
• Learnability and Robustness of Shallow Neural Networks Learned With a Performance-Driven BP and a Variant PSO For Edge Decision-Making
• History-Gradient Aided Batch Size Adaptation for Variance Reduced Algorithms
• Stationary Points of Shallow Neural Networks with Quadratic Activation Function
• End-to-end Learning of a Convolutional Neural Network via Deep Tensor Decomposition
• Learning ReLU Networks via Alternating Minimization
• Symmetry & critical points for a model shallow neural network
• Generalized Leverage Score Sampling for Neural Networks
• Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK
• When does gradient descent with logistic loss interpolate using deep networks with smoothed ReLU activations?
• DANTE: Deep AlterNations for Training nEural networks
• Improved Learning of One-hidden-layer Convolutional Neural Networks with Overlaps
• On the Principle of Least Symmetry Breaking in Shallow ReLU Models
• Theory III: Dynamics and Generalization in Deep Networks
• On generalization bounds for deep networks based on loss surface implicit regularization
• Guaranteed Recovery of One-Hidden-Layer Neural Networks via Cross Entropy
• When does gradient descent with logistic loss find interpolating two-layer networks?
• The Effects of Mild Over-parameterization on the Optimization Landscape of Shallow ReLU Neural Networks
• Orthant Based Proximal Stochastic Gradient Method for ${\ell }_1$-Regularized Optimization
• A Measure Theoretical Approach to the Mean-field Maximum Principle for Training NeurODEs
• Avoiding Spurious Local Minima in Deep Quadratic Networks
• Sub-Optimal Local Minima Exist for Neural Networks with Almost All Non-Linear Activations
• Forward Super-Resolution: How Can GANs Learn Hierarchical Generative Models for Real-World Distributions
• Breaking the gridlock in Mixture-of-Experts: Consistent and Efficient Algorithms
• Single Layer Predictive Normalized Maximum Likelihood for Out-of-Distribution Detection
• How Does the Task Landscape Affect MAML Performance?
• Local SGD Optimizes Overparameterized Neural Networks in Polynomial Time
• Half-Space Proximal Stochastic Gradient Method for Group-Sparsity Regularized Problem
• Two Dimensional Stochastic Configuration Networks for Image Data Analytics
• Towards Searching Efficient and Accurate Neural Network Architectures in Binary Classification Problems
• A Unified Framework for Training Neural Networks
• Recursive Sketches for Modular Deep Learning
• Making Method of Moments Great Again? -- How can GANs learn distributions
• MixCon: Adjusting the Separability of Data Representations for Harder Data Recovery
• A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few Random Spanning Trees
• Autoencoders Learn Generative Linear Models
• Neural Network Training Techniques Regularize Optimization Trajectory: An Empirical Study
• Recovering the Lowest Layer of Deep Networks with High Threshold Activations
• Going Beyond Linear RL: Sample Efficient Neural Function Approximation
• Learning in Gated Neural Networks
• Nonparametric Learning of Two-Layer ReLU Residual Units
• Towards Understanding Learning in Neural Networks with Linear Teachers
• A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum