On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness
Sebastian Pokutta, Mohit Singh, Alfredo Torrico
Abstract
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. 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.
BibTeX
@InProceedings{pmlr-v119-pokutta20a,
title = {On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness},
author = {Pokutta, Sebastian and Singh, Mohit and Torrico, Alfredo},
booktitle = {Proceedings of the 37th International Conference on Machine Learning},
pages = {7772--7782},
year = {2020},
editor = {III, Hal Daumé and Singh, Aarti},
volume = {119},
series = {Proceedings of Machine Learning Research},
month = {13--18 Jul},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v119/pokutta20a/pokutta20a.pdf},
url = {https://proceedings.mlr.press/v119/pokutta20a.html},
abstract = {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. 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.}
}