{
  "id": "1902.02244",
  "version": "v1",
  "published": "2019-02-06T15:47:38.000Z",
  "updated": "2019-02-06T15:47:38.000Z",
  "title": "Bandit Multiclass Linear Classification: Efficient Algorithms for the Separable Case",
  "authors": [
    "Alina Beygelzimer",
    "Dávid Pál",
    "Balázs Szörényi",
    "Devanathan Thiruvenkatachari",
    "Chen-Yu Wei",
    "Chicheng Zhang"
  ],
  "comment": "41 pages, 8 figures",
  "categories": [
    "cs.LG",
    "stat.ML"
  ],
  "abstract": "We study the problem of efficient online multiclass linear classification with bandit feedback, where all examples belong to one of $K$ classes and lie in the $d$-dimensional Euclidean space. Previous works have left open the challenge of designing efficient algorithms with finite mistake bounds when the data is linearly separable by a margin $\\gamma$. In this work, we take a first step towards this problem. We consider two notions of linear separability, \\emph{strong} and \\emph{weak}. 1. Under the strong linear separability condition, we design an efficient algorithm that achieves a near-optimal mistake bound of $O\\left( K/\\gamma^2 \\right)$. 2. Under the more challenging weak linear separability condition, we design an efficient algorithm with a mistake bound of $\\min (2^{\\widetilde{O}(K \\log^2 (1/\\gamma))}, 2^{\\widetilde{O}(\\sqrt{1/\\gamma} \\log K)})$. Our algorithm is based on kernel Perceptron, which is inspired by the work of \\citet{Klivans-Servedio-2008} on improperly learning intersection of halfspaces.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-02-06T15:47:38.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "bandit multiclass linear classification",
      "efficient algorithm",
      "weak linear separability condition",
      "separable case",
      "mistake bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 41,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}