Title: Fast Rates for Bandit Optimization with Upper-Confidence Frank-Wolfe,
Abstract: We consider the problem of bandit optimization, inspired by stochastic
optimization and online learning problems with bandit feedback. In this
problem, the objective is to minimize a global loss function of all the
actions, not necessarily a cumulative loss. This framework allows us to study a
very general class of problems, with applications in statistics, machine
learning, and other fields. To solve this problem, we analyze the
Upper-Confidence Frank-Wolfe algorithm, inspired by techniques for bandits and
convex optimization. We give theoretical guarantees for the performance of this
algorithm over various classes of functions, and discuss the optimality of
these results.