TCS+ Talk

Wednesday, October 19, 2016

10:00am to 11:00am

Annenberg 308

Kernel-based methods for Bandit Convex Optimization.

Ronen Eldan, Weizmann Institute ,

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.

more details» copy to my calendar

For more information, please contact Thomas Vidick by email at [email protected].

Event Series

TCS+ Talks

Event Sponsors

Computing and Mathematical Sciences (CMS) More Events from this Sponsor