The Landscape of Empirical Risk for Non-convex Losses

Abstract

Most high-dimensional estimation and prediction methods propose to minimize a cost function (empirical risk) that is written as a sum of losses associated to each data point. In this paper we focus on the case of non-convex losses, which is practically important but still poorly understood. Classical empirical process theory implies uniform convergence of the empirical risk to the population risk. While uniform convergence implies consistency of the resulting M-estimator, it does not ensure that the latter can be computed efficiently. In order to capture the complexity of computing M-estimators, we propose to study the landscape of the empirical risk, namely its stationary points and their properties. We establish uniform convergence of the gradient and Hessian of the empirical risk to their population counterparts, as soon as the number of samples becomes larger than the number of unknown parameters (modulo logarithmic factors). Consequently, good properties of the population risk can be carried to the empirical risk, and we can establish one-to-one correspondence of their stationary points. We demonstrate that in several problems such as non-convex binary classification, robust regression, and Gaussian mixture model, this result implies a complete characterization of the landscape of the empirical risk, and of the convergence properties of descent algorithms. We extend our analysis to the very high-dimensional setting in which the number of parameters exceeds the number of samples, and provide a characterization of the empirical risk landscape under a nearly information-theoretically minimal condition. Namely, if the number of samples exceeds the sparsity of the unknown parameters vector (modulo logarithmic factors), then a suitable uniform convergence result takes place. We apply this result to non-convex binary classification and robust regression in very high-dimension.

arXiv commentThis version presents a general framework, and applies it to several statistical learning problems

References in corpus (9)

• The Loss Surfaces of Multilayer Networks
• High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity
• Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima
• Matrix Completion from a Few Entries
• A statistical model for tensor PCA
• High-dimensional estimation with geometric constraints
• Global analysis of Expectation Maximization for mixtures of two Gaussians
• Sparse Nonlinear Regression: Parameter Estimation and Asymptotic Inference
• Minimum Distance Estimation for Robust High-Dimensional Regression

Cited by in corpus (34)

• A Mean Field View of the Landscape of Two-Layers Neural Networks
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Empirical Analysis of the Hessian of Over-Parametrized Neural Networks
• Distributed Statistical Machine Learning in Adversarial Settings: Byzantine Gradient Descent
• Learning One-hidden-layer Neural Networks with Landscape Design
• An Analytical Formula of Population Gradient for two-layered ReLU network and its Applications in Convergence and Critical Point Analysis
• Universal Statistics of Fisher Information in Deep Neural Networks: Mean Field Approach
• Nonconvex penalties with analytical solutions for one-bit compressive sensing
• Porcupine Neural Networks: (Almost) All Local Optima are Global
• Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networks
• The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differences
• Statistical Inference for the Population Landscape via Moment Adjusted Stochastic Gradients
• The Landscape of Deep Learning Algorithms
• Statistical Convergence of the EM Algorithm on Gaussian Mixture Models
• Decentralized Submodular Maximization: Bridging Discrete and Continuous Settings
• Learning a Single Neuron with Gradient Methods
• The Multilinear Structure of ReLU Networks
• Conditional Gradient Method for Stochastic Submodular Maximization: Closing the Gap
• Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds
• Weight Sharing is Crucial to Succesful Optimization
• The Landscape of Non-convex Empirical Risk with Degenerate Population Risk
• Deterministic Inequalities for Smooth M-estimators
• Learning time-scales in two-layers neural networks
• Statistical Inference with Local Optima
• Understanding Global Loss Landscape of One-hidden-layer ReLU Networks, Part 1: Theory
• Graph estimation for Gaussian data zero-inflated by double truncation
• Multichannel Sparse Blind Deconvolution on the Sphere
• A Newton-Based Method for Nonconvex Optimization with Fast Evasion of Saddle Points
• When random initializations help: a study of variational inference for community detection
• A Unified Framework for Training Neural Networks
• Convergence Analysis of the Dynamics of a Special Kind of Two-Layered Neural Networks with ${\ell }_1$ and ${\ell }_2$ Regularization
• Fast Global Convergence via Landscape of Empirical Loss
• Spurious Local Minima Are Common for Deep Neural Networks with Piecewise Linear Activations