Online Prediction under Submodular Constraints - Collections | Kyushu University Library

Back to Results List

＜conference paper＞
Online Prediction under Submodular Constraints

Creator	Author PID K006394 Creator Name Suehiro, Daiki 末廣, 大貴スエヒロ, ダイキ Affiliation Affiliation Name Department of Informatics, Kyushu University 九州大学大学院システム情報科学研究院
	Author PID K002791 Creator Name Hatano, Kohei 畑埜, 晃平ハタノ, コウヘイ Affiliation Affiliation Name Department of Informatics, Kyushu University 九州大学大学院システム情報科学研究院
	Author PID K003645 Creator Name Kijima, Shuji 来嶋, 秀治キジマ, シュウジ Affiliation Affiliation Name Department of Informatics, Kyushu University 九州大学大学院システム情報科学研究院
	Author PID K003271 Creator Name Takimoto, Eiji 瀧本, 英二タキモト, エイジ Affiliation Affiliation Name Department of Informatics, Kyushu University 九州大学大学院システム情報科学研究院
	Creator Name Nagano, Kiyohito ナガノ, キヨヒト Affiliation Affiliation Name University of Tokyo 東京大学
Language	English
Publisher	Springer
Date	2012-10
Conference	Name International Conference on Algorithmic Learning Theory Sequence 23 Place Lyon, France Country France
Publication Type	Accepted Manuscript
Access Rights	open access
Related DOI	isVersionOf https://doi.org/10.1007/978-3-319-46379-7_19
Related DOI	Algorithmic learning theory : 23rd International Conference, ALT 2012, Lyon, France, October 29-31, 2012 : proceedings
Relation	Algorithmic learning theory : 23rd International Conference, ALT 2012, Lyon, France, October 29-31, 2012 : proceedings
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.show more

Hide fulltext details.

File	FileType	Size	Views	Description
alt12	pdf	386 KB	748

Details

Record ID	1932327
Related ISBN	978-3-319-46378-0
Subject Terms	Extreme Point
	Convex Combination
	Submodular Function
	Combinatorial Concept
	Procedure Projection
Created Date	2018.06.07
Modified Date	2018.11.28