Learning One-hidden-layer Neural Networks with Landscape Design

2017/11/01 by Rong Ge, Jason D. Lee, Ge, Rong +3 · 21 citations
Computer Science · #Stochastic Gradient Optimization Techniques #Machine Learning and Algorithms #Machine Learning and ELM

paper · pdf · doi:10.48550/arxiv.1711.00501

Abstract

We consider the problem of learning a one-hidden-layer neural network: we assume the input x∈ ℝ^d is from Gaussian distribution and the label y = a^\top σ(Bx) + ξ, where a is a nonnegative vector in ℝ^m with m≤ d, B∈ ℝ^{m× d} is a full-rank weight matrix, and ξ is a noise vector. We first give an analytic formula for the population risk of the standard squared loss and demonstrate that it implicitly attempts to decompose a sequence of low-rank tensors simultaneously. Inspired by the formula, we design a non-convex objective function G(⋅) whose landscape is guaranteed to have the following properties: 1. All local minima of G are also global minima. 2. All global minima of G correspond to the ground truth parameters. 3. The value and gradient of G can be estimated using samples. With these properties, stochastic gradient descent on G provably converges to the global minimum and learn the ground-truth parameters. We also prove finite sample complexity result and validate the results by simulations.

Cited by

• Provably Extracting the Features from a General Superposition
• Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization
• Learning Polynomials of Few Relevant Dimensions
• Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
• Towards Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learning
• Subgradient Descent Learns Orthogonal Dictionaries
• What Can ResNet Learn Efficiently, Going Beyond Kernels?
• Nonparametric Learning of Two-Layer ReLU Residual Units
• Improved Learning of One-hidden-layer Convolutional Neural Networks with Overlaps
• Deep Neural Networks with Multi-Branch Architectures Are Less Non-Convex
• On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulator
• The Landscape of Matrix Factorization Revisited
• Algorithmic Regularization in Learning Deep Homogeneous Models: Layers\n are Automatically Balanced
• Greedy Layerwise Learning Can Scale to ImageNet
• Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration
• Stationary Points of Shallow Neural Networks with Quadratic Activation\n Function
• Low-Rank Tensor Decompositions for the Theory of Neural Networks
• Elimination of All Bad Local Minima in Deep Learning
• Understanding Deflation Process in Over-parametrized Tensor Decomposition
• Spurious Local Minima Are Common for Deep Neural Networks with Piecewise Linear Activations
• Forward Super-Resolution: How Can GANs Learn Hierarchical Generative Models for Real-World Distributions

Related

• Learning One-hidden-layer Neural Networks under General Input Distributions
• Learning and generalization of one-hidden-layer neural networks, going beyond standard Gaussian data
• Guaranteed Recovery of One-Hidden-Layer Neural Networks via Cross Entropy
• Agnostic Learning of a Single Neuron with Gradient Descent
• Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minima