ML Anthology

Online Prediction Under Submodular Constraints

Daiki Suehiro, Kohei Hatano, Shuji Kijima, Eiji Takimoto, Kiyohito Nagano
ALT 2012 pp. 260-274
doi:10.1007/978-3-642-34106-9_22 /alt/2012/suehiro2012alt-online/

Abstract

We consider an online prediction problem of combinatorial concepts where each combinatorial concept is represented as a vertex of a polyhedron described by a submodular function (base polyhedron). In general, there are exponentially many vertices in the base polyhedron. We propose polynomial time algorithms with regret bounds. In particular, for cardinality-based submodular functions, we give O ( n ^2)-time algorithms.

PDF ALT Semantic Scholar

Cite

Text

Suehiro et al. "Online Prediction Under Submodular Constraints." International Conference on Algorithmic Learning Theory, 2012. doi:10.1007/978-3-642-34106-9_22

Markdown

[Suehiro et al. "Online Prediction Under Submodular Constraints." International Conference on Algorithmic Learning Theory, 2012.](https://mlanthology.org/alt/2012/suehiro2012alt-online/) doi:10.1007/978-3-642-34106-9_22

BibTeX

@inproceedings{suehiro2012alt-online,
  title     = {{Online Prediction Under Submodular Constraints}},
  author    = {Suehiro, Daiki and Hatano, Kohei and Kijima, Shuji and Takimoto, Eiji and Nagano, Kiyohito},
  booktitle = {International Conference on Algorithmic Learning Theory},
  year      = {2012},
  pages     = {260-274},
  doi       = {10.1007/978-3-642-34106-9_22},
  url       = {https://mlanthology.org/alt/2012/suehiro2012alt-online/}
}