Bandit Multiclass Linear Classification: Efficient Algorithms for the Separable Case

January 1, 2019

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 γ. 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(2O˜(Klog2(1/γ)),2O˜(1/γ√logK)). Our algorithm is based on kernel Perceptron, which is inspired by the work of (Klivans and Servedio, 2008) on improperly learning intersection of halfspaces.

Download

Publication Type

Paper

Conference / Journal Name

ICML

Authors

Alina Beygelzimer

David Pal

Balázs Szörényi

Devanathan Thiruvenkatachari

Chen-Yu Wei

Chicheng Zhang

BibTeX


@inproceedings{
    author = {},
    title = {‌Bandit Multiclass Linear Classification: Efficient Algorithms for the Separable Case‌},
    booktitle = {Proceedings of ICML‌},
    year = {‌2019‌}
}