Optimization for Approximate Submodularity
We consider the problem of maximizing a submodular function when given access to its approximate version. Submodular functions are heavily studied in a wide variety of disciplines since they are used to model many real world phenomena and are amenable to optimization. There are many cases however in which the phenomena we observe is only approximately submodular and the optimization guarantees cease to hold. In this paper we describe a technique that yields strong guarantees for maximization of monotone submodular functions from approximate surrogates under cardinality and intersection of matroid constraints. In particular, we show tight guarantees for maximization under a cardinality constraint and 1/(1 + P ) approximation under intersection of P matroids.
The authors consider the problem of approximate submodular maximization, i.e. the maximization of functions that can are defined via a submodular function whose set evaluatons are scaled by iid (static) noise. The goal is to maximize the underlying submodular function under cardinality and matroid constraints. The authors develop algorithms for that purpose and proof certain approximation guarantees for them.  While the problem itself in its basic version has been studied already, this paper presents improved algorithms and analysis as well as extensions of the considered constraints involving substantial different analysis. I didn't check proofs in details, but on a high-level the author's approach appears to be correct. So novelty and technical contribution certainly make the paper qualify for NIPS.  In terms of presentation of the paper, improvements could be made. For instance, I believe that putting parts of appendix E (additive approximation guarantees, correlated approximations, and more connections to related work) would make the paper more compelling than showing partial proofs (I see little value added compared to the high level steps as large parts of the technical contributions are in the appendix anyway).  Furthermore, an empirical evaluation would help the reader get an intuition of the importance of parts of the results and where to focus for future algorithmic developments. In particular, the authors argue that they overcome fundamental limitations of previous algorithms, which I understand from their theory, but it would be interesting to see whether this makes a difference in practice. It should be relatively straightforward to implement such an experiment.  * f_S(z) seems to be undefined.  --  I have read the author response and thank the authors for their comments. I think this is an interesting paper with significant relevance to a group of NIPS attendees.