Bandit Smooth Convex Optimization: Improving the Bias-Variance Tradeoff
Bandit convex optimization is one of the fundamental problems in the field of online learning. The best algorithm for the general bandit convex optimization problem guarantees a regret of e O(T 5/6
As I have stated in review summary, the significance of the paper, as least in my opinion, cannot be questioned. It is a simple question of whether the proofs are correct. I will highlight a couple of points which I believe are mistakes. Other than that, I have a few minor questions regarding presentation of the paper (which are not important in terms of accept/reject decision, but if the paper gets in, will be important in terms of clarity).Line 322-323- The authors state that by definitions of \gar{g}_t and the \alpha variables, it is true that \sum_{s=1}^t \alpha_{s,t} \hat{g}_s= \sum_{s=1}^t \bar{g}_s. In fact, this is an important claim because then the dual averaging step reduces to an operation with gradient estimates \bar{g}_1,...\bar{g}_T.I simply cannot see how this is true. I feel this is basic algebra. First of all, even for the equality to hold, we must have \eta \sum_{s=1}^t \bar{g}_s (I can understand missing \eta is a typo). However, even with that, I dont think the equality holds. From definition, it can be seen that \eta \sum_{s=1}^t \bar{g}_s=\sum_{s=1}^t \eta \frac{t-s+1}{K+1} \hat{g}_s. Thus, for each \hat{g}_s, the coefficient associated with it is :\eta \frac{t-s+1}{K+1}. However, for all s, the coefficient is not equal to \alpha_{s,t}. By definition, \alpha_{s,t}=\eta \frac{t-s+1}{K+1} only for s \> t-k. So, how is the equality holding when s\le t-k?Lemma 11: (8c)\le 0. When i looked at the proof of this statement, I once again felt there was a mistake. It is stated in the proof that sum of the \bar{f}_t(x^*) terms is equal to sum of the \hat{f}_t(x^*) terms. I dont see how that is true. This can be simply tested by taking T=2 and K=1 (allowed by condition of Thm. 9) By definitions, for T=2 and K=1, \sum_{t=1}^T \bar{f}_t(x^*)= \hat{f}_1(x^*) + (1/2) \hat{f}_2(x^*), which is obviously not equal to \hat{f}_1(x^*) + \hat{f}_2(x^*).I did not even look through the rest of the proofs. I find the two mistakes very surprising since they seem to be basic algebra. It is of course possible that the authors made some typos which have completely changed some important definitions. Otherwise, I will be happy to be corrected.In terms of presentations, I have a few small questions: 1. In abstract, in line 026, it should be that the regret guarantee is for smooth convex functions, not all convex functions. For the general Lipschitz BCO problem, the lower bound might still be \Omega (T^{2/3}) (or even higher, since the best known result is Flaxman's O(T^{3/4}). 2. I am not sure what Thm.5 means (or rather, the definition of K_{y,\epsilon}. In the definition of K_{y,\epsilon}, there is an \alpha term present and no epsilon term. Is \alpha= \epsilon? It seems to be a typo. 3. Thm 9. In the regret bound, the term \epsilon appears. Nowhere in the algorithm or in the statement of Thm.9 do we have \epsilon. I understand that \epsilon probably appears while using an upper bound on the self-concordant R(), but this is quite poor in terms of presentation. Please modify the statement of Thm 9 to explicitly mention \epsilon. Or dont mention \epsilon at all and use T (like in Saha and Tewari).4. In Saha and Tewari's paper, the authors dont analyze regret directly in terms of x^*. They instead consider a term \bar{x}, which is 1/\sqrt(T) away from boundary of K. This allows R(\bar{x}) \le 2 \new log(T). How do you use x^* directly?5. Please provide definition of Minkowski functional in supplement to make the paper self-containing. Specifically, I would like to know what is the Minkowski's func. associated with a Dikin's ellipsoid. Like specifically what does the functional look like for Dikin's ellipsoid?Update: It appears that the proofs are correct. I accept the paper.