On the Local Minima of the Empirical Risk

Abstract

Population risk is always of primary interest in machine learning; however, learning algorithms only have access to the empirical risk. Even for applications with nonconvex nonsmooth losses (such as modern deep networks), the population risk is generally significantly more well-behaved from an optimization point of view than the empirical risk. In particular, sampling can create many spurious local minima. We consider a general framework which aims to optimize a smooth nonconvex function $F$ (population risk) given only access to an approximation $f$ (empirical risk) that is pointwise close to $F$ (i.e., $\Vert F-f{\Vert }_{\infty }\le \nu$). Our objective is to find the $\epsilon$-approximate local minima of the underlying function $F$ while avoiding the shallow local minima---arising because of the tolerance $\nu$---which exist only in $f$. We propose a simple algorithm based on stochastic gradient descent (SGD) on a smoothed version of $f$ that is guaranteed to achieve our goal as long as $\nu \le O({\epsilon }^{1.5}/d)$. We also provide an almost matching lower bound showing that our algorithm achieves optimal error tolerance $\nu$ among all algorithms making a polynomial number of queries of $f$. As a concrete example, we show that our results can be directly used to give sample complexities for learning a ReLU unit.

To appear in NIPS 2018

Cited by in corpus (9)

• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Asymmetric Valleys: Beyond Sharp and Flat Local Minima
• Solving Empirical Risk Minimization in the Current Matrix Multiplication Time
• Sharp Analysis for Nonconvex SGD Escaping from Saddle Points
• Quasi-potential as an implicit regularizer for the loss function in the stochastic gradient descent
• Efficiently avoiding saddle points with zero order methods: No gradients required
• Statistical Analysis of Stationary Solutions of Coupled Nonconvex Nonsmooth Empirical Risk Minimization
• Stochasticity of Deterministic Gradient Descent: Large Learning Rate for Multiscale Objective Function
• Characterization of Excess Risk for Locally Strongly Convex Population Risk