Combining Adversarial Guarantees and Stochastic Fast Rates in Online Learning
We consider online learning algorithms that guarantee worst-case regret rates in adversarial environments (so they can be deployed safely and will perform robustly), yet adapt optimally to favorable stochastic environments (so they will perform well in a variety of settings of practical importance). We quantify the friendliness of stochastic environments by means of the well-known Bernstein (a.k.a. generalized Tsybakov margin) condition. For two recent algorithms (Squint for the Hedge setting and MetaGrad for online convex optimization) we show that the particular form of their data-dependent individual-sequence regret guarantees implies that they adapt automatically to the Bernstein parameters of the stochastic environment. We prove that these algorithms attain fast rates in their respective settings both in expectation and with high probability.
The paper continues a line of research getting more and more popular in online learning (and learning theory in general): how to design algorithms that perform well in the adversarial setting yet are able to utilize additional regularities in the data that make the task at hand easy. It is shown that some existing algorithms in online learning (Squint and MetaGrad) are able to adapt to easy stochastic environments satisfying the Bernstein condition (used in proving fast rates in stochastic loss minimization), while keeping the usual adversarial guarantees.
ADDED AFTER THE RESPONSE:  I am happy with the response and support the acceptance of the paper. Please include the discussions from the rebuttal to the paper.   Two minor things:  - I still think that unifying the notation is possible (in the expert case you have to restrict U to the corners), but I might be missing something here. - Bernstein to Central: Application of the newly cited lemma is ok, but mention the required boundedness conditions (|2\eta x^f| \le 1.79... which requires D,G-dependent assumptions on eta for the OCO case.  ==============================================  In general I find the problem important and interesting and the treatment elegant. The derivation of the results do not seem to require new techniques, although certainly there are some interesting technicalities in the proofs. While the presentation is good, it could be improved: I think that related work should be discussed a bit differently, and the organization of the paper can be improved to put the results more in context and emphasize on the more relevant parts (these can be done easily, suggestions are given below).  First of all, a slightly weakened version of the intended adaptive bounds can be achieved trivially by applying either the AB-prod algorithm of Sani et al (2014) or the algorithm of the much earlier paper of Even-Dar et al (Machine Learning 2008, "Regret to the best vs. regret to the average, this should also be cited) for an adversarial learning algorithm and the an algorithm that can adapt to the Bernstein condition in the stochastic case (e.g., Bartlet and Mendelson, 2006). You should argue how and why your results are better than this (which is not hard). (This argument also applies as a solution to the "linear worst case regret" in l. 169.)  The results essentially apply to Squint and MetaGrad, but these algorithms are not provided. While Squint is at least published, MetaGrad is only available as a preprint (and by no means is so widely known that it should not be included).   The paper continuously derives results for Squint and MetaGrad separately, from time to time introducing some unifying notation. It seems to me that treating the expert case (Hedge setting) as a problem of linear prediction over the simplex would automatically unify the two problems (the original losses will become gradients).  In the statements of the main results (Theorem, 3 Theorem 9), why do you recall MetaGrad and Squint? Wouldn't the main statement be that given data dependent regret bounds fast rates hold for the Bernstein case? By the way, wouldn't your results apply for Adapt-ML-Prod (maybe I am missing something here)?   * Organization: I think that Lemma 7 (and the related notation) adds very little to understanding the proof of the theorem. Especially, the trivial proofs should be relegated to the appendix. This could free some space to provide more important materials (e.g., more discussion, high level proof steps of Theorem 9, or the proof of Theorem 3).   * Technical questions: 1. In the problem definition, make it clear if the environment is oblivious or not. While in general your results apply to non-oblivious environments, conditional expectations (e.g., in Sec 2.3) are not taken according to that.  2. Sec 2.3: Wouldn't it be enough to require that k^* minimizes the expected cumulative loss?  3. Since the Hedge setting is only defined for countably infinite expert sets, it is somewhat bothering to extend it to the undefined uncountable case. Maybe define the problem generally, then restrict it to the countable case when necessary?  4. Appendix B: It would be better to repeat the Bernstein Sandwich lemma (it is very hard to resolve the notation in the reference). Also, I am not sure that the cited lemma is correct: in the last step of its proof, both sides are multiplied by x^2, but why can you take its minimum in the upper bound? (There are too many parentheses in line 424.)  5. Theorem 13: I find the statement of the theorem a bit confusing. In particular, the O(K_T+C_T) notation is a bit fuzzy when nothing is assumed about these sequences. Why not make an assumption that K_T/T and C_T/T go to zero, in which case the bound would have the nice form of T O(((K_T+C_T)/T)^1/(2-kappa)). Also consider removing the intuitive explanations from mathematical statements (maybe this is just my taste). It is very hard to associate any meaning to this part of the theorem.   * Minor comments: - Introduction, par 2: There are several other types of results (combinatorial problems, context tree prediction, tracking, curvature of the loss function, etc) which adapt to some sort of problem complexity. Consider mentioning what sort of complexity you are after. - l. 66: The definition of \pi might not be entirely clear, in particular that the upper index is not power and that the distribution is over the natural numbers (it will be automatically if you define the algorithm). - l. 100: What do you mean by "the Bays act is in the model?" - l. 116: "these stochastic conditions" -> the following stochastic conditions.  - l. 122: only equivalent with appropriate choices of parameters. - l. 130: "Second order methods" seems to be a bit too general here. - l. 175-180 is not entirely clear (without reading the relevant part in the Appendix). Why is this discussion restricted to Squint? - l. 191-193: In fact you loose a log log T factor by relaxing the assumptions - l. 198: consider->considered - l. 218: "we model" should rather be "Assume z_1,...,z_T is a Markov chain" - Section 3.4: I find it a bit overstatement to call the considered linear loss Hinge loss (since the "hinge part" is excluded). In what sense is the maximum of the Hinge loss 1 (consider a large negative < x,u >)? - Lemma 7: Your statement in 1 is really not that X is negative with high probability, only that it is not too large. Also, the notation about the expectations is very confusing here (e.g., E_{f\sim w} only takes expectation over f (with all other randomness in X^f fixed, wile E does not affect f in E X^f. Please make these more precise/clear (define them; applies to other occurrences, e.g., the proof of Theorem 9). - l. 284: give a reference for the dual representation. - Theorem 9: remove "the" before "excess". gamma is not defined to be 2 eta. This is also needed in the proof (l. 434). - l. 312: 2 epsilon should be 2 gamma - The references are really hard to parse in the current format. - l. 435: You have to take the proper conditional expectations to be able to invoke the chain rule. - l. 455: Mention that the omitted kappa-dependent constant is at most 1. - Example 1: What is \mathcal{J}? Please make the notation consistent throughout. (correct "m utandis") - l. 459: Did you use an assumption that \gamma^2 \le 1 (to deal with (the 1+gamma^2) terms)?