Submodular Maximization via Gradient Ascent: The Case of Deep Submodular Functions
We study the problem of maximizing deep submodular functions (DSFs) [13,3] subject to a matroid constraint. DSFs are an expressive class of submodular functions that include, as strict subfamilies, the facility location, weighted coverage, and sums of concave composed with modular functions. We use a strategy similar to the continuous greedy approach [6], but we show that the multilinear extension of any DSF has a natural and computationally attainable concave relaxation that we can optimize using gradient ascent. Our results show a guarantee of max 0<δ<1 (1− − δ − e 2 ) plus time for pipage rounding [6] to recover a discrete solution, where k is the rank of the matroid constraint. This bound is often better than the standard 1 − 1/e guarantee of the continuous greedy algorithm, but runs much faster. Our bound also holds even for fully curved (c = 1) functions where the guarantee of 1 − c/e degenerates to 1 − 1/e where c is the curvature of f [37]. We perform computational experiments that support our theoretical results.
The submodular maximization is an important problem with many real-world applications. One powerful way of tackling these problems is to consider their contentious relaxations, then maximize those relaxations, and finally rounding the resulting solutions into discrete answers. In this paper, the authors consider maximizing a special class of submodular functions called  deep submodular functions (DSFs) under a matroid constraint.  The (almost) standard approach to solve a submodular maximization problem in the continuous domain is to consider the multilinear extension of the original set function. The contribution of this paper is to show that the natural concave extension of a DSF function provides an acceptable approximation for the multilinear extension. Because this natural extension is concave, a gradient ascent method will find the maximum value. The idea of bounding multilinear extension by a concave function for coverage functions is already introduced in [1]. In this paper, authors provide a tighter bound for a more general class of functions.  I have read the paper in details and I believe it is technically correct.  Next you can find my detailed comments.  1. This works is along the new progresses on maximizing DR-continuous functions (and in particular multi-linear extension). For  example, Hassani et al. [2] recently have proven that stochastic gradient ascent achieves 1/2 approximation for DR-continuous functions. Furthermore, Mokhtari et al. [3] have developed practical algorithms for stochastic conditional gradient methods which mitigates the need for subsampling while achieves the  (1-1/e)-approximation guarantee. The computational complexity of the algorithm from [3] is much better than that of O(n^7). The references (and comparison) to these closely related papers are missing.   2. The bound in Theorem 3 is a function of k, |V^1|, w_min and w_max. DSFs are a narrow family of submodular functions. The dependence on |V^1|, w_min and w_max might makes the coverage of these DSFs even narrower (for the cases their algorithm provides improvements for the approximation guarantee). For example, it might be the case that |V^1| should be very large in order to cover a broad family of submodular functions. I believe that the authors should have elaborated (more) on the dependence on these parameters. Considering these points and the fact that the result is only for a subclass of submodular functions with a matroid constraint, I find the contribution of this paper somewhat marginal.  3. The big O notation is not used correctly. Note that O(k) could be 0, and the approximation guarantee could be arbitrarily bad. Also, it is not mathematically sound to write \Delta(x) \geq O(k) (line 243).  4. The Experiments section of the paper is weak as it only considers synthetic datasets. I think adding experiments over the real world datasets would improve the quality of this paper.  5. Minor comments:  a) The presentation of paper could be improved. Next you can find several suggestions:  In page 1, "A" is not defined. Figure 2 is discusses before Figure 1. Font of equations (2) and (5) is very small. It is better to write the equation (2) in an iterative formulation. Different notations are used for definitions: \equiv and \triangleq. The fractions in the text are sometimes written by \nicefrac{}{} and sometimes \frac{}{}. Some sentences starts with numbers, e.g., line 80. The punctuation for "i.e.," and "e.g.," is not consistent.  b) line 40: benefit  c) line 75: \epsilon^{-2}  d) line 178: "we are focusing" or "we focus"  e) line: it is better to say "in continuous domain"  f) line 204: the definition of concave closure seems unnecessary  g) line 289: proposed  References: [1] Mohammad Reza Karimi, Mario Lucic, S. Hamed Hassani, Andreas Krause. Stochastic Submodular Maximization: The Case of Coverage Functions. NIPS 2017. [2] S. Hamed Hassani, Mahdi Soltanolkotabi, Amin Karbasi. Gradient Methods for Submodular Maximization. NIPS 2017. [3] Aryan Mokhtari, Hamed Hassani, Amin Karbasi. Conditional Gradient Method for Stochastic Submodular Maximization: Closing the Gap. AISTATS 2018.