{
  "id": "1002.2044",
  "version": "v1",
  "published": "2010-02-10T09:08:56.000Z",
  "updated": "2010-02-10T09:08:56.000Z",
  "title": "On the Stability of Empirical Risk Minimization in the Presence of Multiple Risk Minimizers",
  "authors": [
    "Benjamin I. P. Rubinstein",
    "Aleksandr Simma"
  ],
  "comment": "4 pages",
  "categories": [
    "cs.LG"
  ],
  "abstract": "Recently Kutin and Niyogi investigated several notions of algorithmic stability--a property of a learning map conceptually similar to continuity--showing that training-stability is sufficient for consistency of Empirical Risk Minimization while distribution-free CV-stability is necessary and sufficient for having finite VC-dimension. This paper concerns a phase transition in the training stability of ERM, conjectured by the same authors. Kutin and Niyogi proved that ERM on finite hypothesis spaces containing a unique risk minimizer has training stability that scales exponentially with sample size, and conjectured that the existence of multiple risk minimizers prevents even super-quadratic convergence. We prove this result for the strictly weaker notion of CV-stability, positively resolving the conjecture.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2010-02-10T09:08:56.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "empirical risk minimization",
      "multiple risk minimizers prevents",
      "conjecture",
      "algorithmic stability-a property",
      "unique risk minimizer"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 4,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1002.2044R"
    }
  }
}