David Pal — accepted AI-conference papers

2019

Bandit Multiclass Linear Classification: Efficient Algorithms for the Separable Case

Alina Beygelzimer, David Pal, Balazs Szorenyi, Devanathan Thiruvenkatachari, Chen-Yu Wei, Chicheng Zhang

ICML 2019oral

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 whe…

Cited by 18 Source ↗PDF ↗Scholar ↗

2019

The information-theoretic value of unlabeled data in semi-supervised learning

Alexander Golovnev, David Pal, Balazs Szorenyi

ICML 2019oral

We quantify the separation between the numbers of labeled examples required to learn in two settings: Settings with and without the knowledge of the distribution of the unlabeled data. More specifically, we prove a separation by $\Theta(\log n)$ multiplicative factor for the class of projections ove…

Cited by 13 Source ↗PDF ↗Scholar ↗

2016

Coin Betting and Parameter-Free Online Learning

Francesco Orabona, David Pal

NeurIPS 2016poster

In the recent years, a number of parameter-free algorithms have been developed for online linear optimization over Hilbert spaces and for learning with expert advice. These algorithms achieve optimal regret bounds that depend on the unknown competitors, without having to tune the learning rates wit…

Cited by 202 Source ↗PDF ↗Scholar ↗

2016

Hardness of Online Sleeping Combinatorial Optimization Problems

Satyen Kale, Chansoo Lee, David Pal

NeurIPS 2016poster

We show that several online combinatorial optimization problems that admit efficient no-regret algorithms become computationally hard in the sleeping setting where a subset of actions becomes unavailable in each round. Specifically, we show that the sleeping versions of these problems are at least a…

Cited by 23 Source ↗PDF ↗Scholar ↗