Optimistic Bandit Convex Optimization
We introduce the general and powerful scheme of predicting information re-use in optimization algorithms. This allows us to devise a computationally efficient algorithm for bandit convex optimization with new state-of-the-art guarantees for both Lipschitz loss functions and loss functions with Lipschitz gradients. This is the first algorithm admitting both a polynomial time complexity and a regret that is polynomial in the dimension of the action space that improves upon the original regret bound for Lipschitz loss functions, achieving a regret of e O T 11/16 d 3/8 . Our algorithm further improves upon the best existing polynomial-in-dimension bound (both computationally and in terms of regret) for loss functions with Lipschitz gradients, achieving a regret of e O T 8/13 d 5/3 .
The present paper provides a new algorithm---optimistic BCO---for bandit convex optimization. It leads to improved regret bounds among computationally efficient algorithms, for both Lipschitz loss functions and loss functions with Lipschitz gradients.
The presentation is globally clear, the paper seems technically solid, but a careful proofreading is necessary before publication. For instance there are too many notational inconsistencies throughout the paper.  As far as originality is concerned, the improvement in the regret bounds is new, but they may seem incremental, especially because there are known to be suboptimal (putting algorithmic issues aside). Indeed Bubeck and Eldan (2015) proved through a non-constructive approach that the optimal rate in T is sqrt(T) up to log factors. The authors also mention the recent manuscript by Hazan and Li (2016) who claim to get the optimal sqrt(T) regret (up to log factors) but whose algorithm has an exponential dependency w.r.t. the dimension of the decision set, both in terms of its regret bound and its computational complexity. On the contrary, the algorithm provided here has a polynomial dependency w.r.t. the ambient dimension.  I cannot figure out whether the prediction of information re- use is just a technical trick or if it can be used to get optimal bounds. Could the authors provide some insight about that? Besides, why just predict \bar{g}_{t+1} and not \bar{g}_{t+2},...,\bar{g}_{t+k}?   Some specific comments: - Is it an oblivious adversary? (cf. definition of regret line 54) - Line 126: please specify \widehat{g}_{t-i} when t-i \leq 0. - Previous work : please also mention existing lower bounds - Figure 1: k is also a parameter? - \eta in the definition of x_{t+1} is not at the right place? See also line 183 and 330. - In theorem 1 and 2, must k be an integer? - In lemma 5, x is not defined, x^star= min ... - Line 218 missing square bracket - Line 317, please say somewhere that \widehat{f}_t(x) \geq f_t(x), - Line 330 I do not understand the conditional expectation, what is F_t? - Page 14: inversion between y_t and z_t and T and t - End of lemma 7 where do you check that \lambda(x_t,F_t)\leq 1/2? - Line 347 Since ... it is an x_t - Line 352 what is E_{t-i}? - Same line, I do not understand the upper bound of the third term by L. - Line 357 in Lemma 2 there is a factor C in the upper bound of the local norm of \widehat{g}_s.