Differentiable Greedy Algorithm for Monotone Submodular Maximization: Guarantees, Gradient Estimators, and Applications
Differentiable Greedy Algorithm for Monotone Submodular Maximization: Guarantees, Gradient Estimators, and Applications
复制标题
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Shinsaku Sakaue
中科院分区：
文献类型：
--
作者：
Shinsaku Sakaue
例如，随着灵敏度分析和端到端学习的发展，对可定制优化算法的需求不断增加。本文提出了一种求解单调子模函数极大化问题的理论保证的可微分贪婪算法。我们通过随机化对贪婪算法进行了平滑，并证明了在基数和κ -可扩展系统约束的情况下，该算法几乎可以在期望范围内恢复原始的近似保证.然后，我们提出了如何有效地计算梯度估计的任何预期的输出依赖量。我们证明了我们的方法的实用性，通过实例化它的各种应用程序。
Motivated by, e.g., sensitivity analysis and end-to-end learning, the demand for differen-tiable optimization algorithms has been increasing. This paper presents a theoretically guaranteed differentiable greedy algorithm for monotone submodular function maximization. We smooth the greedy algorithm via randomization, and prove that it almost recovers original approximation guarantees in expectation for the cases of cardinality and κ -extendible system constraints. We then present how to efficiently compute gradient estimators of any expected output-dependent quantities. We demonstrate the usefulness of our method by instantiating it for various applications.