TCS+ Talk

Wednesday October 19, 2016 10:00 AM

Kernel-based methods for Bandit Convex Optimization.

Speaker: Ronen Eldan, Weizmann Institute
Location: Annenberg 308

Available remotely at Google Hangouts:

I will present the first poly-time and \sqrt{T} \rm{poly}(n)-regret algorithm for bandit convex optimization. Given a convex body \mathcal{K} \subset \mathbb{R}^n, the problem can be described as the following sequential game: at each time step t=1, ..., T, a player selects an action x_t \in \mathcal{K}, and simultaneously an adversary selects a convex loss function \ell_t : \mathcal{K} \rightarrow [0,1]. The player's feedback is its suffered loss, \ell_t(x_t). The player has access to external randomness, and can select her action x_t based on the history (x_s, \ell_s(x_s))_{s<t}. The player's perfomance at the end of the game is measured through the regret R_T = \sum_{t=1}^T \ell_t(x_t) - \min_{x \in \mathcal{K}} \sum_{t=1}^T \ell_t(x) , which compares her cumulative loss to the smallest cumulative loss she could have obtained had she known the sequence of loss functions. Joint w. Sebastien Bubeck and Yin-Tat Lee.
Series TCS+ Talks

Contact: Thomas Vidick vidick@cms.caltech.edu