Learning faster from easy data

Worst-case sample complexity bounds generally scale quadratically with the excess error. However, when the target error is small, the dependence on the excess error is more similar to a linear dependence rather than quadratic. In this talk I will discuss when and how such optimistic rates are possible, in particular in the non-parametric scale-sensitive case, and when they are not possible, argue that the "optimistic" regime better captures the relevant regime to learning, and show examples of how an analysis based on such optimistic rates is necessary in order to understand various learning phenomena.

In this talk, we study the problem of active learning for cost-sensitive multiclass classification. We propose selective sampling algorithms, which process the data in a streaming fashion, querying only a subset of the labels. For these algorithms, we analyze the regret and label complexity when the labels are generated according to a generalized linear model. We establish that the gains of active learning over passive learning can range from none to exponentially large, based on a natural notion of margin. We also present a safety guarantee to guard against model mismatch. Numerical simulations show that our algorithms indeed obtain a low regret with a small number of queries.

The traditional worst-case analysis for online learning problems is often too pessimistic for real world applications. We would like to design adaptive online learning algorithms that enjoy much better (faster rates) regret bounds against "nicer" data sequences while still preserving the worst-case bounds against the worst case data sequences. While in previous works such algorithms have been designed for specific problems, in this talk I shall describe a generic methodology for designing adaptive algorithms for general online learning problems. Specifically I shall introduce the idea of adaptive relaxation and the concept of localization in online learning. Using these concepts I shall provide a general recipe for designing adaptive online learning algorithms for problems. Through examples I shall illustrate the utility of the introduced concepts on several problems. These examples include new adaptive online learning algorithms against iid adversaries and algorithms that can adapt to data geometry.

In sequential prediction with expert advice, the intuitive Follow-the-Leader (FTL) algorithm predicts like the expert that has performed best in the past. Although this algorithm performs very well on stochastic data or in other `easy' cases where there are few leader changes, it is known to fail dramatically when the data are adversarial. On the other hand, other algorithms (like exponential weights with conservative parameter tuning) perform well on adversarial data, but learn much slower than FTL when we are indeed lucky enough to encounter the 'easy' data for which FTL performs well. This observation raises the question of whether it is possible to get the best of both worlds: is there a single algorithm that is robust to adversarial data, but exploits `easy' data to learn faster when possible?

I will discuss how previous methods that satisfy so-called second-order bounds get us part of the way: they work both for adversarial and for stochastic data, but do not exploit other `easy' data for which FTL works well. Then I will present a new method, called FlipFlop, which satisfies the same second-order bounds as previous methods, but in addition is provably as good as FTL on any data.

This is joint work with Steven de Rooij, Peter Grünwald and Wouter Koolen. The paper "Follow the Leader If You Can, Hedge If You Must" is available from www.timvanerven.nl/publications.

Since the seminal work of Lai and Robbins (1985) we know bandit strategies with normalized regret of order (i) 1/sqrt(T) for any stochastic bandit, and (ii) log(T) / T for 'benign' distributions. In Bubeck and Slivkins (2012) we designed a new strategy which extends property (i) to adversarial bandits while still having the fast rate given in (ii). I will present this algorithm and I will also discuss the possibility of even faster rates of order 1/T when extra information is available.