Alina Beygelzimer — 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

Contextual Memory Trees

Wen Sun, Alina Beygelzimer, Hal Daumé Iii, John Langford, Paul Mineiro

ICML 2019oral

We design and study a Contextual Memory Tree (CMT), a learning memory controller that inserts new memories into an experience store of unbounded size. It operates online and is designed to efficiently query for memories from that store, supporting logarithmic time insertion and retrieval operations.…

Cited by 14 Source ↗PDF ↗code ↗Scholar ↗

2018

A Reductions Approach to Fair Classification

Alekh Agarwal, Alina Beygelzimer, Miroslav Dudik, John Langford, Hanna Wallach

ICML 2018oral

We present a systematic approach for achieving fairness in a binary classification setting. While we focus on two well-known quantitative definitions of fairness, our approach encompasses many other previously studied definitions as special cases. The key idea is to reduce fair classification to a s…

Cited by 1454 Source ↗PDF ↗code ↗Scholar ↗

2017

Efficient Online Bandit Multiclass Learning with $\tilde{O}(\sqrt{T})$ Regret

Alina Beygelzimer, Francesco Orabona, Chicheng Zhang

ICML 2017poster

We present an efficient second-order algorithm with $\tilde{O}(1/\eta \sqrt{T})$ regret for the bandit online multiclass problem. The regret bound holds simultaneously with respect to a family of loss functions parameterized by $\eta$, ranging from hinge loss ($\eta=0$) to squared hinge loss ($\eta=…

Cited by 0 Source ↗PDF ↗Scholar ↗

2016

Search Improves Label for Active Learning

Alina Beygelzimer, Daniel J. Hsu, John Langford, Chicheng Zhang

NeurIPS 2016poster

We investigate active learning with access to two distinct oracles: LABEL (which is standard) and SEARCH (which is not). The SEARCH oracle models the situation where a human searches a database to seed or counterexample an existing solution. SEARCH is stronger than LABEL while being natural to imple…

Cited by 34 Source ↗PDF ↗Scholar ↗

2015

Online Gradient Boosting

Alina Beygelzimer, Elad Hazan, Satyen Kale, Haipeng Luo

NeurIPS 2015poster

We extend the theory of boosting for regression problems to the online learning setting. Generalizing from the batch setting for boosting, the notion of a weak learning algorithm is modeled as an online learning algorithm with linear loss functions that competes with a base class of regression funct…

Cited by 82 Source ↗PDF ↗code ↗Scholar ↗

2015

Optimal and Adaptive Algorithms for Online Boosting

Alina Beygelzimer, Satyen Kale, Haipeng Luo

ICML 2015poster

We study online boosting, the task of converting any weak online learner into a strong online learner. Based on a novel and natural definition of weak online learnability, we develop two online boosting algorithms. The first algorithm is an online version of boost-by-majority. By proving a matching…

Cited by 98 Source ↗PDF ↗Scholar ↗