PACM Colloquium: Kernel-based methods for Bandit Convex Optimization

I will present the first poly-time and $\sqrt{T} \rm{poly}(n)$-regret algorithm for bandit convex optimization. 

Consider the problem of optimizing a unknown convex function using an approximate function value oracle. In the stochastic approximation literature one usually assumes that the noise is zero-mean, identical and independent between queries. The bandit framework goes much beyond this independence assumption by saying that for each query there is a different function (potentially chosen adversarially given all the past choices) and the objective is to optimize the average function. 

The problem at hand is thus formulated as follows: 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.

We will present the first algorithm which achieves optimal dependence of $T$ and a polynomial dependence on the dimension. This new algorithm is based on three ideas: (i) kernel methods, (ii) a generalization of Bernoulli convolutions (this a self-similar process that has been studied since the 1930's, most notably by Erdos), and (iii) a new annealing schedule for exponential weights (with increasing learning rate).

Joint w. Sebastien Bubeck and Yin-Tat Lee.