December 15th

14:30 , R2014 Digiteo Shannon (660) (see location):

Joon Kwon (IMJ, Université Pierre-et-Marie-Curie)

joint work with Vianney Perchet (INRIA & LPMA, Université Paris-Diderot)

Title : SPARSE REGRET MINIMIZATION

Abstract :

We demonstrate that, in the classical non-stochastic regret minimization problem with d decisions, gains and losses to be respectively maximized or minimized are fundamentally different. Indeed, by considering the additional sparsity assumption (at each stage, at most s decisions incur a nonzero outcome), we derive optimal regret bounds of different orders. Specically, with gains, we obtain an optimal regret guarantee after T stages of order srqt(T log s), so the classical dependency in the dimension is replaced by the sparsity size. With losses, we provide matching upper and lower bounds of order sqrt(T s log(d)/d), which is decreasing in d. Eventually, we also study the bandit setting, and obtain an upper bound of order sqrt(T s log(d/s)) when outcomes are losses. This bound is proven to be optimal up to the logarithmic factor sqrt log(d/s).

Slides: sparse-tao.pdf

Contact: cyril.furtlehner@inria.fr