Online Prediction under Submodular Constraints

• Suehiro, Daiki

  Department of Informatics, Kyushu University

• Hatano, Kohei

  Department of Informatics, Kyushu University

• Kijima, Shuji

  Department of Informatics, Kyushu University

• Takimoto, Eiji

  Department of Informatics, Kyushu University

• Nagano, Kiyohito

  University of Tokyo

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.

Journal

• 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報

  電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 112 (83), 15-22, 2012-10

  Springer

Keywords

• Extreme Point
• Convex Combination
• Submodular Function
• Combinatorial Concept
• Procedure Projection

Details

• CRID: 1050861482658528128
• NII Article ID: 110009588469
• NII Book ID: AA1123312X
• ISSN: 09135685
• HANDLE: 2324/1932327
• NDL BIB ID: 023810524
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I023810524
• Text Lang: en
• Article Type: conference paper
• Data Source:
  • IRDB
  • NDL
  • CiNii Articles