Title: Online submodular minimization for combinatorial structures

Authors: S. Jegelka and J. A. Bilmes

Abstract

Most results for online decision problems with structured concepts, such as trees or cuts, as- sume linear costs. In many settings, how- ever, nonlinear costs are more realistic. Ow- ing to their non-separability, these lead to much harder optimization problems. Going beyond linearity, we address online approx- imation 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.

Full Text: [PDF]

Accessibility at Yale   Inference, Information, and Decision Group at Yale