Constant Regret, Generalized Mixability, and Mirror Descent
We consider the setting of prediction with expert advice; a learner makes predictions by aggregating those of a group of experts. Under this setting, and for the right choice of loss function and "mixing" algorithm, it is possible for the learner to achieve a constant regret regardless of the number of prediction rounds. For example, a constant regret can be achieved for mixable losses using the aggregating algorithm. The Generalized Aggregating Algorithm (GAA) is a name for a family of algorithms parameterized by convex functions on simplices (entropies), which reduce to the aggregating algorithm when using the Shannon entropy S. For a given entropy Φ, losses for which a constant regret is possible using the GAA are called Φ-mixable. Which losses are Φ-mixable was previously left as an open question. We fully characterize Φ-mixability and answer other open questions posed by [6]. We show that the Shannon entropy S is fundamental in nature when it comes to mixability; any Φ-mixable loss is necessarily S-mixable, and the lowest worst-case regret of the GAA is achieved using the Shannon entropy. Finally, by leveraging the connection between the mirror descent algorithm and the update step of the GAA, we suggest a new adaptive generalized aggregating algorithm and analyze its performance in terms of the regret bound.
This paper studies a generalization of the notion of mixability, called \Phi-mixability, and developed an adaptive generalized aggregating algorithm (AGAA) for it.   To me, the interesting part of this paper is that it reveals the fundamental nature of the Shannon entropy in defining mixability: For a loss to be \Phi-mixable, it is necessary that it is mixable w.r.t. the Shannon entropy. Indeed, (9) gives an if and only if characterization of \Phi-mixability using mixability w.r.t. the Shannon entropy. Theorem 17 shows that exploiting the general \Phi-mixability does not help reduce the regret, though this result is only specific to the so-called generalized AA.   The AGAA is not very exciting to me. This paper provides a scenario where the AGAA can even achieve a negative regret, but the scenario does not seem very general. A more satisfactory argument, in my opinion, should be similar to the results for, say, the optimistic mirror descent; there is a clear characterization for the data to be "easy", and it is clear that smaller regret can be achieved with easy data. Moreover, as mentioned in the paper, the AGAA can also yield worse performance.  The main weakness of this paper, in my view, is that the main message is not very clear. The abstract emphasized both the novel characterization of \Phi-mixability and the AGAA. The characterization of \Phi-mixability, however, seems to suggest that generalizing the notion of mixability (at least in the direction of this paper) is not really helpful. The argument for the superiority of the AGAA is not strong enough, as I said in the preceding paragraph.   I did not have the time to check the very long proofs.   Other comments:   1. The presentation can be improved. This paper uses many terminologies and symbols without defining them first. For example, "Vovk's exponential mixing" in the first paragraph can be confusing to non-experts of online learning, and this confusion can be easily avoided by rewriting the sentence. The loss \ell is not defined before the appearance of R_\ell. The definition of H in (5) is missing.   2. The if and only if condition (9) looks similar to the condition proposed in the following two papers.      a. "A descent lemma beyond Lipschitz gradient continuity: First-order methods revisited and applications" by Bauschke et al.      b. "Relatively smooth convex optimization by first-order methods, and applications" by Lu et al.  There is perhaps be some relationship.   3. ln 96, p. 3: The claim that "we make no topological assumption on A" is unnecessarily too strong.   4. ln 247, p. 6: The similarity with Vovk's work on the fundamental nature of the logarithmic loss is mentioned. However, this similarity is clear to me, as Vovk's result is about the choice of the loss function, instead of the definition of mixability. Please elaborate.