# Title: Robust Guarantees of Stochastic Greedy Algorithms

# Authors: Avinatan Hassidim, Yaron Singer

# Abstract

In this paper we analyze the robustness of stochastic variants of the greedy algorithm for submodular maximization. Our main result shows that for maximizing a monotone submod- ular function under a cardinality constraint, itera- tively selecting an element whose marginal con- tribution is approximately maximal in expecta- tion is a sufficient condition to obtain the opti- mal approximation guarantee with exponentially high probability, assuming the cardinality is suf- ficiently large. One consequence of our result is that the linear-time STOCHASTIC-GREEDY algo- rithm recently proposed in (Mirzasoleiman et al., 2015) achieves the optimal running time while maintaining an optimal approximation guaran- tee. We also show that high probability guaran- tees cannot be obtained for stochastic greedy al- gorithms under matroid constraints, and prove an approximation guarantee which holds in expec- tation. In contrast to the guarantees of the greedy algorithm, we show that the approximation ratio of stochastic local search is arbitrarily bad, with high probability, as well as in expectation.