Online submodular minimization for combinatorial structures

Jegelka, S; Bilmes, J; Getoor T. Scheffer, L.

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

このアイテムの新しいバージョンが利用可能です:
https://pure.mpg.de/pubman/item/item_1788139_2

詳細要約

公開

会議論文

Online submodular minimization for combinatorial structures

MPS-Authors

/persons/resource/persons83994

Jegelka, S
Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society;

/persons/resource/persons83814

Bilmes, J
Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society;

External Resource

There are no locators available

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

公開されているフルテキストはありません

付随資料 (公開)

There is no public supplementary material available

引用

Jegelka, S., & Bilmes, J. (2011). Online submodular minimization for combinatorial structures. In 28th International Conference on Machine Learning (ICML 2011) (pp. 345-352). Madison, WI, USA: International Machine Learning Society.

引用: https://hdl.handle.net/11858/00-001M-0000-0013-BB26-5

要旨

Most results for online decision problems with structured concepts, such as trees or cuts, assume linear costs. In many settings, however, nonlinear costs are more realistic. Owing to their non-separability, these lead to much harder optimization problems. Going beyond linearity, we address online approximation algorithms for structured concepts that allow the cost to be submodular, i.e., nonseparable. In particular, we show regret bounds for three Hannan-consistent strategies that capture different settings. Our results also tighten a regret bound for unconstrained online submodular minimization.