Adaptive Online Learning
We propose a general framework for studying adaptive regret bounds in the online learning setting, subsuming model selection and data-dependent bounds. Given a data-or model-dependent bound we ask, "Does there exist some algorithm achieving this bound?" We show that modifications to recently introduced sequential complexity measures can be used to answer this question by providing sufficient conditions under which adaptive rates can be achieved. In particular each adaptive rate induces a set of so-called offset complexity measures, and obtaining small upper bounds on these quantities is sufficient to demonstrate achievability. A cornerstone of our analysis technique is the use of one-sided tail inequalities to bound suprema of offset random processes. Our framework recovers and improves a wide variety of adaptive bounds including quantile bounds, second order data-dependent bounds, and small loss bounds. In addition we derive a new type of adaptive bound for online linear optimization based on the spectral norm, as well as a new online PAC-Bayes theorem.
Summary:This paper investigates luckiness guarantees for online learning that may depend on the data and on the comparator. Deciding achievability of a proposed adaptive bound is cast as a minimax problem. This problem is subsequently relaxed using sequential Rademacher complexity. Probability tail bounds are used to give tractable expressions for achievable bounds in general and in a variety of examples. Originality and Significance:This is a novel extension of the game-theoretic approach to obtain adaptive bounds. Whereas most algorithms are designed bottom-up, this approach starts at the core of the problem and. Tractability then becomes a trade-off with sharpness of bounds. This method is very powerful, and will undoubtedly result in new algorithms for existing and new adaptivity targets. Clarity and Quality:The paper is nicely done. I was a little disappointed that the methods, after plugging in the proposed tail bounds, unfortunately cannot match the state of the art in the worked-out examples. I also feel that the discussion of the results is a little one-sided as it does not point this out enough.  The bound of Example 4.4 should be compared to Theorem 1 and Corollary 1 from the NIPS'14 paper "Exploiting Easy Data in Online Optimization" by Sani, Neu and Lazaric. Their bound seems strictly better, as it gives constant regret compared to the singled-out strategy, independent of the time horizon and the number of other strategies. I am also a little wary of the current bound's dependence on $L$. Intuitively the whole bound should simply scale with $L$, for this is what should happen if we rescale the loss function. (if not, the results can be improved by pre- and post-scaling appropriately). The bound of Example 4.5 should be compared to Theorem 4 (which trivially extends from subsets to mixtures) from the COLT'15 paper "Second-order Quantile Methods for Experts and Combinatorial Games" by Koolen and Van Erven. Doing so, the advantage that the current paper sees over [13] (which is obtained by magnifying lower-order terms) disappears. What remains is that the current paper has a worse linear term (loss of comparator f instead of variance of regret with respect to f) at the cost of a worse multiplicative overhead (ln n at time horizon n instead of ln ln n). It is surprising that the proposed method, which in principle should be much tighter as it is minimax-optimal, ignores all computational issues and fixed-horizon, loses out on all fronts to a computationally efficient anytime method. It would be interesting to see a dissection of where the advantage is lost.  Minor: line 161: move the left-hand-side of this definition from line 160 into the equation. lines 272, 372: You need a singleton $\cal X$. If it is empty everything collapses. line 297: Why use O-tilde if you spell out the log factor? line 304: It looks that empty $\cal F(1)$ presents problems. For what is the Rademacher complexity of the empty set? If it is $0$ we have a division by $0$. If it is $-\infty$ the bound 304 is unachievable. line 311: Why is infinite set of radii an issue for exponential weights? line 336: omit "is" Example 4.4. I was unsure what $N$ means here. Is $N = |\cal F|$? line 418: Perhaps omit this, it sounds a little embarrassing. You did find the appendix for other material. page 9: please unify the reference style (full names vs initials) and check for capitals in titles: Hilbert, Banach, ...         *** UPDATE *** I would like to respond to this sentence from the author response:The bound of Koolen et al is N-independent, but is in terms of the prior (that is, MDL-style).The suggested difference is purely cosmetic and not intrinsic. A trivial modification of the analysis results in a KL (i.e. PAC-Bayes) bound. Koolen and Van Erven seem to do this for their Theorem 8 but not their Theorem 4. Yet, there is no difficulty whatsoever.