On the Local Minima of the Empirical Risk
This addresses optimization challenges in machine learning, particularly for deep networks, by providing theoretical guarantees to avoid shallow minima, though it is incremental in improving existing methods.
The paper tackles the problem of spurious local minima in empirical risk optimization for nonconvex losses, proposing an SGD-based algorithm that finds approximate local minima of the population risk with an optimal error tolerance of ν ≤ O(ε^{1.5}/d).
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., $\|F-f\|_{\infty} \le ν$). Our objective is to find the $ε$-approximate local minima of the underlying function $F$ while avoiding the shallow local minima---arising because of the tolerance $ν$---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 $ν\le O(ε^{1.5}/d)$. We also provide an almost matching lower bound showing that our algorithm achieves optimal error tolerance $ν$ 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.