Online Submodular Minimization for Combinatorial Structures

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. 1.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 24 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.