Fast Rates for Bandit Optimization with Upper-Confidence Frank-Wolfe
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.
This is a very interesting paper at the intersection of bandit problems and stochastic optimization. The authors consider the setup where at each time step a decision maker takes an action and gets as a feedback a gradient estimate at the chosen point. The gradient estimate is noisy  but the assumption is that we have control over how noisy the gradient estimate is.  The challenge for the decision maker is to make a sequence of moves such that the average of all iterates has low error  compared to the optima. So the goal is similar to the goal in stochastic optimization, but unlike stochastic optimization (but like bandit problems) one gets to see limited information about the loss function.
For the above problem setting the authors introduce an algorithm that combines elements of UCB along with Frank-Wolfe updates. The FW style updates means that we do not play the arm corresponding to the highest UCB, but instead play an arm that is a convex combination of the UCB arm and a probability distribution that comes from historical updates. The authors establish stochastic optimization style bounds for a variety of function classes.  The paper is failry well written and makes novel contributions to both stochastic opt and bandit literature. I have a few comments
1. It is not clear to me why the authors consider only Frank-Wolfe algorithm. Is there a deep motivation here or can the arguments made in this paper be translated to even work with other optimization algorithms such as stochastic gradient descent etc...?
2. In lines 214-219, it is not clear to me why one needs to invoke KKT condition. It was not clear to me what the relevance and importance of this paragraph is. Can the authors shine some light here?
3. Definition of strong convexity in line 230 is incorrect.
4. It would perhaps be useful to moved the lines 246-249 to the start of the paper. In this way it will be more clear why and how the problem considered here is different from standard stochastic optimization algorithms.
5. In line 257 what is \sigma_max?