Online Submodular Minimization for Combinatorial Structures
Online Submodular Minimization for Combinatorial Structures
复制标题
组合结构的在线子模最小化
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
J. Bilmes
中科院分区：
文献类型：
--
作者：
S. Jegelka;J. Bilmes
结构化概念（例如树木或砍伐）的在线决策问题的大多数结果都假定线性成本。但是，在许多情况下，非线性成本更现实。由于它们的不可分割性，这些导致了更困难的优化问题。超越线性性，我们解决了在线近似算法的结构化概念，这些概念允许成本subsodular，即不可分割。特别是，我们为捕获不同设置的三种汉南一致策略显示了遗憾的界限。我们的结果还收紧了对不受限制的在线superodular最小化的遗憾。
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.