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 (13)

• Convergence Analysis of Two-layer Neural Networks with ReLU Activation
• Provable Bounds for Learning Some Deep Representations
• How to Escape Saddle Points Efficiently
• Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity
• Matrix Completion has No Spurious Local Minimum
• No bad local minima: Data independent training error guarantees for multilayer neural networks
• Gradient Descent Learns Linear Dynamical Systems
• Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks using Tensor Methods
• Recovery Guarantees for One-hidden-layer Neural Networks
• When Are Nonconvex Problems Not Scary?
• On the low-rank approach for semidefinite programs arising in synchronization and community detection
• An Analytical Formula of Population Gradient for two-layered ReLU network and its Applications in Convergence and Critical Point Analysis
• The Landscape of Empirical Risk for Non-convex Losses

Cited by in corpus (60)

• A Mean Field View of the Landscape of Two-Layers Neural Networks
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• Towards Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learning
• Optimization for deep learning: theory and algorithms
• What Can ResNet Learn Efficiently, Going Beyond Kernels?
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Depth with Nonlinearity Creates No Bad Local Minima in ResNets
• Spurious Valleys in Two-layer Neural Network Optimization Landscapes
• Elimination of All Bad Local Minima in Deep Learning
• Subgradient Descent Learns Orthogonal Dictionaries
• Asymmetric Valleys: Beyond Sharp and Flat Local Minima
• Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration
• From Symmetry to Geometry: Tractable Nonconvex Problems
• Greedy Layerwise Learning Can Scale to ImageNet
• On the Connection Between Learning Two-Layers Neural Networks and Tensor Decomposition
• Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced
• Constrained Learning with Non-Convex Losses
• Rate Distortion For Model Compression: From Theory To Practice
• 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
• SGD Learns One-Layer Networks in WGANs
• Can SGD Learn Recurrent Neural Networks with Provable Generalization?
• Limitations of Lazy Training of Two-layers Neural Networks
• Learning Two Layer Rectified Neural Networks in Polynomial Time
• Revisiting Landscape Analysis in Deep Neural Networks: Eliminating Decreasing Paths to Infinity
• Deep Neural Networks with Multi-Branch Architectures Are Less Non-Convex
• Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization
• Learnability and Robustness of Shallow Neural Networks Learned With a Performance-Driven BP and a Variant PSO For Edge Decision-Making
• Stationary Points of Shallow Neural Networks with Quadratic Activation Function
• Learning ReLU Networks via Alternating Minimization
• End-to-end Learning of a Convolutional Neural Network via Deep Tensor Decomposition
• Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization
• Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK
• GradSign: Model Performance Inference with Theoretical Insights
• The Landscape of Non-convex Empirical Risk with Degenerate Population Risk
• Improved Learning of One-hidden-layer Convolutional Neural Networks with Overlaps
• A Deep Conditioning Treatment of Neural Networks
• Learning Polynomials of Few Relevant Dimensions
• Towards an Understanding of Residual Networks Using Neural Tangent Hierarchy (NTH)
• Nonlinear Inductive Matrix Completion based on One-layer Neural Networks
• Forward Super-Resolution: How Can GANs Learn Hierarchical Generative Models for Real-World Distributions
• The Rate of Convergence of Variation-Constrained Deep Neural Networks
• Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networks
• Understanding Global Loss Landscape of One-hidden-layer ReLU Networks, Part 1: Theory
• The Landscape of Matrix Factorization Revisited
• Breaking the gridlock in Mixture-of-Experts: Consistent and Efficient Algorithms
• A Super-Resolution Framework for Tensor Decomposition
• PCA by Optimisation of Symmetric Functions has no Spurious Local Optima
• Student Specialization in Deep ReLU Networks With Finite Width and Input Dimension
• Probably Approximately Correct Constrained Learning
• Autoencoders Learn Generative Linear Models
• Robust Generalization of Quadratic Neural Networks via Function Identification
• Understanding Deflation Process in Over-parametrized Tensor Decomposition
• Recovering the Lowest Layer of Deep Networks with High Threshold Activations
• Nonparametric Learning of Two-Layer ReLU Residual Units
• Learning Graph Neural Networks with Approximate Gradient Descent
• Spurious Local Minima Are Common for Deep Neural Networks with Piecewise Linear Activations
• Parameter Critic: a Model Free Variance Reduction Method Through Imperishable Samples
• SSRGD: Simple Stochastic Recursive Gradient Descent for Escaping Saddle Points