Dear All,
We are happy to
invite you to our next SPIP talk on Friday,
6th November from 16:00-17:00. Our speaker is Dirk
van der Hoeven and he will talk about ‘Exploiting
the Surrogate Gap in Online Multiclass Classification’.
Dirk
is a PhD student at Leiden University with Tim van Erven
and he will join Nicolò Cesa-Bianchis group
as a postdoc in December.
Zoom Details:
Topic: SPIP - Dirk
van der Hoeven
Abstract:
We
present Gaptron, a randomized first-order algorithm for
online multiclass classification. In the full information
setting we show expected mistake bounds with respect to the
logistic loss, hinge loss, and the smooth hinge loss with
constant regret, where the expectation is with respect to
the learner's randomness. In the bandit classification
setting we show that Gaptron is the first linear time
algorithm with O(K sqrt(T)) expected regret, where K is the
number of classes. Additionally, the expected mistake bound
of Gaptron does not depend on the dimension of the feature
vector, contrary to previous algorithms with O(K sqrt(T) )
regret in the bandit classification setting. We present a
new proof technique that exploits the gap between the
zero-one loss and surrogate losses rather than exploiting
properties such as exp-concavity or mixability, which are
traditionally used to prove logarithmic or constant regret
bounds.
The
Organizer-team