ML Anthology

Efficient Algorithms for Combinatorial Online Prediction

Eiji Takimoto, Kohei Hatano
ALT 2013 pp. 22-32
doi:10.1007/978-3-642-40935-6_3 /alt/2013/takimoto2013alt-efficient/

Abstract

We study online linear optimization problems over concept classes which are defined in some combinatorial ways. Typically, those concept classes contain finite but exponentially many concepts and hence the complexity issue arises. In this paper, we survey some recent results on universal and efficient implementations of low-regret algorithmic frameworks such as Follow the Regularized Leader (FTRL) and Follow the Perturbed Leader (FPL).

PDF ALT Semantic Scholar

Cite

Text

Takimoto and Hatano. "Efficient Algorithms for Combinatorial Online Prediction." International Conference on Algorithmic Learning Theory, 2013. doi:10.1007/978-3-642-40935-6_3

Markdown

[Takimoto and Hatano. "Efficient Algorithms for Combinatorial Online Prediction." International Conference on Algorithmic Learning Theory, 2013.](https://mlanthology.org/alt/2013/takimoto2013alt-efficient/) doi:10.1007/978-3-642-40935-6_3

BibTeX

@inproceedings{takimoto2013alt-efficient,
  title     = {{Efficient Algorithms for Combinatorial Online Prediction}},
  author    = {Takimoto, Eiji and Hatano, Kohei},
  booktitle = {International Conference on Algorithmic Learning Theory},
  year      = {2013},
  pages     = {22-32},
  doi       = {10.1007/978-3-642-40935-6_3},
  url       = {https://mlanthology.org/alt/2013/takimoto2013alt-efficient/}
}