Online submodular minimization for combinatorial structures

Jegelka, S; Bilmes, J.

アイテム詳細

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

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

会議論文

Online submodular minimization for combinatorial structures

MPS-Authors

/persons/resource/persons83994

Jegelka, S
Dept. Empirical Inference, Max Planck Institute for Intelligent Systems, Max Planck Society;

/persons/resource/persons75286

Bilmes, J.
Dept. Empirical Inference, Max Planck Institute for Intelligent Systems, 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).

引用: https://hdl.handle.net/11858/00-001M-0000-0010-75BD-D

要旨

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.