论文标题
关于贪婪算法的不合理有效性：贪婪适应清晰度
On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness
论文作者
论文摘要
在过去的几十年中，已经广泛研究了子模型的最大化，这主要是因为其在现实世界中的许多应用。众所周知，标准贪婪算法在基础限制下最大化单调下调函数时，可以保证最坏情况下的近似值为1-1/e。但是，经验研究表明，其实践的性能在实践中要好得多。这提出了一个自然的问题，即解释了这种贪婪算法的改善性能。在这项工作中，我们将表函数的清晰度定义为这种现象的候选解释。清晰度标准的灵感来自凸优化中强凸度的概念。我们表明，随着子管函数的清晰度的增加，贪婪的算法的性能效果更好。这种改进与凸优化的尖锐函数的一阶方法的更快收敛速率紧密相关。最后，我们进行了一项计算研究，以凭经验支持我们的理论结果，并表明清晰度比文献中其他理由更好地解释了贪婪的表现。
Submodular maximization has been widely studied over the past decades, mostly because of its numerous applications in real-world problems. It is well known that the standard greedy algorithm guarantees a worst-case approximation factor of 1-1/e when maximizing a monotone submodular function under a cardinality constraint. However, empirical studies show that its performance is substantially better in practice. This raises a natural question of explaining this improved performance of the greedy algorithm. In this work, we define sharpness for submodular functions as a candidate explanation for this phenomenon. The sharpness criterion is inspired by the concept of strong convexity in convex optimization. We show that the greedy algorithm provably performs better as the sharpness of the submodular function increases. This improvement ties in closely with the faster convergence rates of first order methods for sharp functions in convex optimization. Finally, we perform a computational study to empirically support our theoretical results and show that sharpness explains the greedy performance better than other justifications in the literature.
