Guaranteed Recovery of One-Hidden-Layer Neural Networks via Cross Entropy

Abstract

We study model recovery for data classification, where the training labels are generated from a one-hidden-layer neural network with sigmoid activations, also known as a single-layer feedforward network, and the goal is to recover the weights of the neural network. We consider two network models, the fully-connected network (FCN) and the non-overlapping convolutional neural network (CNN). We prove that with Gaussian inputs, the empirical risk based on cross entropy exhibits strong convexity and smoothness {\em uniformly} in a local neighborhood of the ground truth, as soon as the sample complexity is sufficiently large. This implies that if initialized in this neighborhood, gradient descent converges linearly to a critical point that is provably close to the ground truth. Furthermore, we show such an initialization can be obtained via the tensor method. This establishes the global convergence guarantee for empirical risk minimization using cross entropy via gradient descent for learning one-hidden-layer neural networks, at the near-optimal sample and computational complexity with respect to the network input dimension without unrealistic assumptions such as requiring a fresh set of samples at each iteration.

References in corpus (12)

• Guaranteed Matrix Completion via Non-convex Factorization
• Global Optimality of Local Search for Low Rank Matrix Recovery
• The loss surface of deep and wide neural networks
• Recovery Guarantees for One-hidden-layer Neural Networks
• Learning ReLUs via Gradient Descent
• Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs
• When is a Convolutional Filter Easy To Learn?
• Learning One-hidden-layer ReLU Networks via Gradient Descent
• Learning One Convolutional Layer with Overlapping Patches
• Learning Non-overlapping Convolutional Neural Networks with Multiple Kernels
• Harnessing Structures in Big Data via Guaranteed Low-Rank Matrix Estimation
• Theoretical properties of the global optimizer of two layer neural network

Cited by in corpus (1)

• Learning ReLU Networks on Linearly Separable Data: Algorithm, Optimality, and Generalization