Stochastic Submodular Maximization: The Case of Coverage Functions
Stochastic optimization of continuous objectives is at the heart of modern machine learning. However, many important problems are of discrete nature and often involve submodular objectives. We seek to unleash the power of stochastic continuous optimization, namely stochastic gradient descent and its variants, to such discrete problems. We first introduce the problem of stochastic submodular optimization, where one needs to optimize a submodular objective which is given as an expectation. Our model captures situations where the discrete objective arises as an empirical risk (e.g., in the case of exemplar-based clustering), or is given as an explicit stochastic model (e.g., in the case of influence maximization in social networks). By exploiting that common extensions act linearly on the class of submodular functions, we employ projected stochastic gradient ascent and its variants in the continuous domain, and perform rounding to obtain discrete solutions. We focus on the rich and widely used family of weighted coverage functions. We show that our approach yields solutions that are guaranteed to match the optimal approximation guarantees, while reducing the computational cost by several orders of magnitude, as we demonstrate empirically.
The paper discusses the development of stochastic optimization for submodular coverage functions. The results and proofs are a mish-mash of existing results and techniques; nevertheless the results are novel and should spark interest for discussions and further research directions. 
The central contribution of the paper is providing with a framework to exploit the SGD machinery. To this effect, coverage functions can be harnessed, because the concave upperbound is obtained easily. While this seems restrictive, the authors present applications with good empirical performance vs classic greedy. 
I have a couple of points:- 
(a)	Is there to use projected SGD over Stochastic Frank-Wolfe [A] ? The latter will get rid of messy projection issues for general matroids, albeit the convergence might be slower. 
(b)	An interesting aspect of the paper is connection between discrete optimization and convex optimization. I would suggest including more related work that discuss these connections [B,C,D,E]. [B] also talks about approx. form of submodularity, [C,D] both follow the notion of “lifting” atomic optimization to continuous domain. 
Minor:
The paper is well-written overall. There are minor typos for which I suggest the authors spend some time cleaning up the paper. E.g. Line 22,24 “trough”, line 373 “mosst”. An equation reference is missing in the appendix.
Numbering of Proof Proposition 2 is messed up. 
The proof of Theorem 2 seems to be missing, I understand it follows from pipage rounding, but it might be a good idea to give a Lemma or something with reference from which approx. guarantee for rounding follows. In general, adding more information about pipage rounding in the appendix for completeness might be a good idea.
The main text is missing a page of references. 
[A] Linear Convergence of Stochastic Frank Wolfe Variants. Donald Goldfarb, Garud Iyengar, Chaoxu Zhou 
[B] Restricted Strong Convexity Implies Weak Submodularity. Ethan R. Elenberg , Rajiv Khanna , Alexandros G. Dimakis , and Sahand Negahban
[C] On Approximation Guarantees for Greedy Low Rank Optimization Rajiv Khanna , Ethan R. Elenberg1 , Alexandros G. Dimakis , and Sahand Negahban
[D] Lifted coordinate descent for learning with trace-norm regularization. Miro Dudik  Zaid Harchaoui , Jérôme Malick 
[E] Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains. Andrew An Bian, Baharan Mirzasoleiman, Joachim M. Buhmann, Andreas Krause