Generalised Mixability, Constant Regret, and Bayesian Updating
Mixability of a loss is known to characterise when constant regret bounds are achievable in games of prediction with expert advice through the use of Vovk's aggregating algorithm. We provide a new interpretation of mixability via convex analysis that highlights the role of the Kullback-Leibler divergence in its definition. This naturally generalises to what we call $\Phi$-mixability where the Bregman divergence $D_\Phi$ replaces the KL divergence. We prove that losses that are $\Phi$-mixable also enjoy constant regret bounds via a generalised aggregating algorithm that is similar to mirror descent.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
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 i…
Open-Ended Question AnsweringGeneralized Mixability via Entropic Duality
Mixability is a property of a loss which characterizes when fast convergence is possible in the game of prediction with expert advice. We show that a key property of mixability generalizes, and the exp and log operations…
Mixability in Statistical Learning
Statistical learning and sequential prediction are two different but related formalisms to study the quality of predictions. Mapping out their relations and transferring ideas is an active area of investigation. We provi…
Bayesian InferencePredictionAn Information-Theoretic Approach to Minimax Regret in Partial Monitoring
We prove a new minimax theorem connecting the worst-case Bayesian regret and minimax regret under partial monitoring with no assumptions on the space of signals or decisions of the adversary. We then generalise the infor…
Exploiting the Surrogate Gap in Online Multiclass Classification
We present Gaptron, a randomized first-order algorithm for online multiclass classification. In the full information setting we show expected mistake bounds with respect to the logistic loss, hinge loss, and the smooth h…
ClassificationGeneral Classification