אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

Online Learning deals with playing repeated games against an adversary with the aim of minimising a quantity known as regret, and has attracted much attention in recent years due to its applications in algorithm design and machine learning. The computational bottleneck in the application of online learning algorithms is the computation of a projection of a point onto a convex set, which for many problems of interest, such as those that arise in combinatorial optimization and matrix optimization, is prohibitive. An alternative approach is to design algorithms for online learning that trade expensive projection steps in favour of linear optimization steps over the feasible domain, which for many problems are much more efficient and simple to implement.

In this talk we will present an algorithm for online learning that uses only linear optimization steps over the feasible domain (one per iteration of the game) and attains optimal regret, resolving an open question by Vempala and Kalai (COLT 2003), and Hazan and Kale (ICML 2012), in case the feasible domain is a polytope.

Our method is based on a novel variant of the conditional gradient method, that reduces the task of minimizing a smooth convex function over a domain to that of minimizing a linear objective. Whereas previous variants of this method give rise to approximation algorithms, we give such algorithm that converges exponentially faster.

The talk is based on a joint work with Elad Hazan (FOCS '13).