Bandit multiclass linear classification: Efficient algorithms for the separable case

Alina Beygelzimer, Dávid Pál, Balázs Szörényi, Devanathan Thiruvenkatachari, Chen Yu Wei, Chicheng Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

We study the problem of efficient online multi-class linear classification with bandit feedback, where all examples belong to one of K classes and lie in the (¿-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 7. In this work, we take a first step towards this problem. We consider two notions of linear separability, strong and weak. 1. Under the strong linear separability condition, we design an efficient algorithm that achieves a near-optimal mistake bound of o(K/γ2). 2. Under the more challenging weak linear separability condition, we design an efficient algorithm with a mistake bound of min(2õ(K log 2(1/γ)),2õ(√1/γ log K)).1 Our algorithm is based on kernel Perceptron and is inspired by the work of Klivans & Serve-dio (2008) on improperly learning intersection of halfspaces.

Original languageEnglish (US)
Title of host publication36th International Conference on Machine Learning, ICML 2019
PublisherInternational Machine Learning Society (IMLS)
Pages975-1011
Number of pages37
ISBN (Electronic)9781510886988
StatePublished - 2019
Externally publishedYes
Event36th International Conference on Machine Learning, ICML 2019 - Long Beach, United States
Duration: Jun 9 2019Jun 15 2019

Publication series

Name36th International Conference on Machine Learning, ICML 2019
Volume2019-June

Conference

Conference36th International Conference on Machine Learning, ICML 2019
Country/TerritoryUnited States
CityLong Beach
Period6/9/196/15/19

ASJC Scopus subject areas

  • Education
  • Computer Science Applications
  • Human-Computer Interaction

Fingerprint

Dive into the research topics of 'Bandit multiclass linear classification: Efficient algorithms for the separable case'. Together they form a unique fingerprint.

Cite this