Non-monotone Submodular Maximization in Exponentially Fewer Iterations

In machine learning, many fundamental quantities we care to optimize such as entropy, graph cuts, diversity, coverage, diffusion, and clustering are submodular functions.