Reviews: Stochastic Submodular Maximization: The Case of Coverage Functions

The papers deals with the problem of submodular maximization; specifically, it proposes a stochastic optimization algorithm for maximizing a specific family of submodular functions, i.e. weighted coverage, under matroid constraints. The algorithm operates on the multilinear extension of the weighted coverage function. This way, the authors are sacrificing accuracy by optimizing a concave function which is a bounded approximation of the target function. However, they gain theoretically supported bounds on the convergence rate and the running time, which they also showcase in the experiments. In general, the paper is well written, and the set of ideas that it uses are well put together. The experimental section, although brief, drives the point that the authors want to make.