论文标题
批处理贪婪的最大化功能：实验设计的保证和应用
Batch greedy maximization of non-submodular functions: Guarantees and applications to experimental design
论文作者
论文摘要
我们提出和分析批处理贪婪的启发式方法，以限制非屈服非调节设置功能的最大化。我们考虑标准的贪婪范式，以及其分布的贪婪和随机贪婪的变体。我们的理论保证的特征在于表育体和超模比的结合。我们争论这些参数如何基于增量增益来定义紧密的模块化边界，并使用次要最大化（MM）原理对经典贪婪算法进行新颖的重新解释。基于该类比，我们提出了一类利用任何合理模块化结合的新方法。在线性贝叶斯逆问题的最佳实验设计的背景下，当基础目标基于相互信息时，我们绑定了亚二次性和超模化比率。我们还为在这种情况下开发了新型的模块化边界，并描述与多面体组合剂的某些连接。我们讨论使用这些模块化界限的算法如何与已建立的统计概念（例如杠杆得分）以及诸如数量抽样之类的最新努力相关联。我们证明了关于综合问题和现实气候监测示例的理论发现。
We propose and analyze batch greedy heuristics for cardinality constrained maximization of non-submodular non-decreasing set functions. We consider the standard greedy paradigm, along with its distributed greedy and stochastic greedy variants. Our theoretical guarantees are characterized by the combination of submodularity and supermodularity ratios. We argue how these parameters define tight modular bounds based on incremental gains, and provide a novel reinterpretation of the classical greedy algorithm using the minorize-maximize (MM) principle. Based on that analogy, we propose a new class of methods exploiting any plausible modular bound. In the context of optimal experimental design for linear Bayesian inverse problems, we bound the submodularity and supermodularity ratios when the underlying objective is based on mutual information. We also develop novel modular bounds for the mutual information in this setting, and describe certain connections to polyhedral combinatorics. We discuss how algorithms using these modular bounds relate to established statistical notions such as leverage scores and to more recent efforts such as volume sampling. We demonstrate our theoretical findings on synthetic problems and on a real-world climate monitoring example.
