{
  "id": "2106.15662",
  "version": "v1",
  "published": "2021-06-29T18:14:01.000Z",
  "updated": "2021-06-29T18:14:01.000Z",
  "title": "Exponential Weights Algorithms for Selective Learning",
  "authors": [
    "Mingda Qiao",
    "Gregory Valiant"
  ],
  "comment": "To appear in COLT 2021",
  "categories": [
    "cs.LG",
    "cs.DS",
    "stat.ML"
  ],
  "abstract": "We study the selective learning problem introduced by Qiao and Valiant (2019), in which the learner observes $n$ labeled data points one at a time. At a time of its choosing, the learner selects a window length $w$ and a model $\\hat\\ell$ from the model class $\\mathcal{L}$, and then labels the next $w$ data points using $\\hat\\ell$. The excess risk incurred by the learner is defined as the difference between the average loss of $\\hat\\ell$ over those $w$ data points and the smallest possible average loss among all models in $\\mathcal{L}$ over those $w$ data points. We give an improved algorithm, termed the hybrid exponential weights algorithm, that achieves an expected excess risk of $O((\\log\\log|\\mathcal{L}| + \\log\\log n)/\\log n)$. This result gives a doubly exponential improvement in the dependence on $|\\mathcal{L}|$ over the best known bound of $O(\\sqrt{|\\mathcal{L}|/\\log n})$. We complement the positive result with an almost matching lower bound, which suggests the worst-case optimality of the algorithm. We also study a more restrictive family of learning algorithms that are bounded-recall in the sense that when a prediction window of length $w$ is chosen, the learner's decision only depends on the most recent $w$ data points. We analyze an exponential weights variant of the ERM algorithm in Qiao and Valiant (2019). This new algorithm achieves an expected excess risk of $O(\\sqrt{\\log |\\mathcal{L}|/\\log n})$, which is shown to be nearly optimal among all bounded-recall learners. Our analysis builds on a generalized version of the selective mean prediction problem in Drucker (2013); Qiao and Valiant (2019), which may be of independent interest.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-06-29T18:14:01.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "data points",
      "selective learning",
      "expected excess risk",
      "average loss",
      "hybrid exponential weights algorithm"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}