Learning One-hidden-layer Neural Networks with Landscape Design

Abstract

We consider the problem of learning a one-hidden-layer neural network: we assume the input $x\in {\mathbb{R}}^d$ is from Gaussian distribution and the label $y=a^{\top }\sigma (Bx)+\xi$, where $a$ is a nonnegative vector in ${\mathbb{R}}^m$ with $m\le d$, $B\in {\mathbb{R}}^{m\times d}$ is a full-rank weight matrix, and $\xi$ 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(\cdot )$ 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.

References in corpus (3)

• How to Escape Saddle Points Efficiently
• Recovery Guarantees for One-hidden-layer Neural Networks
• The Landscape of Empirical Risk for Non-convex Losses

Cited by in corpus (13)

• Optimization for deep learning: theory and algorithms
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Asymmetric Valleys: Beyond Sharp and Flat Local Minima
• On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulator
• Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks
• Can SGD Learn Recurrent Neural Networks with Provable Generalization?
• Limitations of Lazy Training of Two-layers Neural Networks
• Revisiting Landscape Analysis in Deep Neural Networks: Eliminating Decreasing Paths to Infinity
• Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization
• Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK
• Learning Polynomials of Few Relevant Dimensions
• SSRGD: Simple Stochastic Recursive Gradient Descent for Escaping Saddle Points
• Parameter Critic: a Model Free Variance Reduction Method Through Imperishable Samples