{
  "id": "1803.09357",
  "version": "v2",
  "published": "2018-03-25T22:18:04.000Z",
  "updated": "2018-10-17T22:55:49.000Z",
  "title": "On the Local Minima of the Empirical Risk",
  "authors": [
    "Chi Jin",
    "Lydia T. Liu",
    "Rong Ge",
    "Michael I. Jordan"
  ],
  "comment": "To appear in NIPS 2018",
  "categories": [
    "cs.LG",
    "math.OC",
    "stat.ML"
  ],
  "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., $\\|F-f\\|_{\\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.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2018-10-17T22:55:49.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "empirical risk",
      "population risk",
      "algorithm achieves optimal error tolerance",
      "nonconvex nonsmooth losses",
      "smooth nonconvex function"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}