ML Anthology

Mixability and the Existence of Weak Complexities

Yuri Kalnishkan, Michael V. Vyugin
COLT 2002 pp. 105-120
doi:10.1007/3-540-45435-7_8 /colt/2002/kalnishkan2002colt-mixability/

Abstract

This paper investigates the behaviour of the constant c ( β ) from the Aggregating Algorithm. Some conditions for mixability are derived and it is shown that for many non-mixable games c ( β ) still converges to 1. The condition c ( β ) → 1 is shown to imply the existence of weak predictive complexity and it is proved that many games specify complexity up to √ n .

PDF COLT Semantic Scholar

Cite

Text

Kalnishkan and Vyugin. "Mixability and the Existence of Weak Complexities." Annual Conference on Computational Learning Theory, 2002. doi:10.1007/3-540-45435-7_8

Markdown

[Kalnishkan and Vyugin. "Mixability and the Existence of Weak Complexities." Annual Conference on Computational Learning Theory, 2002.](https://mlanthology.org/colt/2002/kalnishkan2002colt-mixability/) doi:10.1007/3-540-45435-7_8

BibTeX

@inproceedings{kalnishkan2002colt-mixability,
  title     = {{Mixability and the Existence of Weak Complexities}},
  author    = {Kalnishkan, Yuri and Vyugin, Michael V.},
  booktitle = {Annual Conference on Computational Learning Theory},
  year      = {2002},
  pages     = {105-120},
  doi       = {10.1007/3-540-45435-7_8},
  url       = {https://mlanthology.org/colt/2002/kalnishkan2002colt-mixability/}
}