Bandit Convex Optimization: Towards Tight Bounds
Bandit Convex Optimization (BCO) is a fundamental framework for decision making under uncertainty, which generalizes many problems from the realm of online and statistical learning. While the special case of linear cost functions is well understood, a gap on the attainable regret for BCO with nonlinear losses remains an important open question. In this paper we take a step towards understanding the best attainable regret bounds for BCO: we give an efficient and near-optimal regret algorithm for BCO with strongly-convex and smooth loss functions. In contrast to previous works on BCO that use time invariant exploration schemes, our method employs an exploration scheme that shrinks with time.
In this paper, the authors have proposed a new algorithm for Bandit Convex Optimization (BCO) with strongly-convex and smooth loss functions, which uses an exploration scheme that shrinks with time. The authors have also proved that the proposed algorithm achieves an \tilde{O}(\sqrt{T}) regret (see Theorem 10), which matches the existing best lower bound if we ignore the logarithm factors. The technical analysis of this paper looks correct.The result of this paper is significant in the sense that the authors have not only provided a tighter regret bound for BCO with strongly-convex and smooth loss functions (from \tilde{O}(T^{2/3}) to \tilde{O}(T^{1/2})), but more importantly, this improved regret bound matches the lower bound in (Shamir 2013). Thus, in general, I vote for acceptance of this paper. However, I vote for marginal acceptance instead of strong acceptance since I think the paper is not well-written, specifically,1) There are many lemmas in the paper, but when reading the paper (without looking at the appendix), it is not clear which ones are existing results and which ones are proved by the authors. This makes it a little bit hard to evaluate the technical significance of the paper.2) The authors spend too much space to review the existing results, and the main result of this paper starts at the end of page 6.3) Some symbols in the paper are not well defined, for example, \delta in Eqn(4) is not defined. Some results are not very clear, for instance, the result of Lemma 9 should hold for any \omega, but the authors do not explicitly state that.4) The authors should rewrite Algorithm 2: there should be no loop in Algorithm 2, and \Nabla h_t (x_t)'s should be inputs to the algorithm.