# Constant Regret, Generalized Mixability, and Mirror Descent

arXiv: https://arxiv.org/abs/1802.06965 · HTML: https://mlsanity.com/paper/1802.06965/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Feb 2018.

## Built on by (most cited first, 5 of 5)

- [Scoring Rules and Calibration for Imprecise Probabilities](https://mlsanity.com/paper/2410.23001/) (2024)
- [Efficient Competitions and Online Learning with Strategic Forecasters](https://mlsanity.com/paper/2102.08358/) (2021)
- [A Regret-Variance Trade-Off in Online Learning](https://mlsanity.com/paper/2206.02656/) (2022)
- [The Geometry and Calculus of Losses](https://mlsanity.com/paper/2209.00238/) (2022)
- [The Geometry of Mixability](https://mlsanity.com/paper/2302.11905/) (2023)

## Abstract (arXiv)

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 operatornameS. For a given entropy Phi, losses for which a constant regret is possible using the textscGAA are called Phi-mixable. Which losses are Phi-mixable was previously left as an open question. We fully characterize Phi-mixability and answer other open questions posed by citeReid2015. We show that the Shannon entropy operatornameS is fundamental in nature when it comes to mixability; any Phi-mixable loss is necessarily operatornameS-mixable, and the lowest worst-case regret of the textscGAA 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.