Gradient Methods for Submodular Maximization
In this paper, we study the problem of maximizing continuous submodular functions that naturally arise in many learning applications such as those involving utility functions in active learning and sensing, matrix approximations and network inference. Despite the apparent lack of convexity in such functions, we prove that stochastic projected gradient methods can provide strong approximation guarantees for maximizing continuous submodular functions with convex constraints. More specifically, we prove that for monotone continuous DR-submodular functions, all fixed points of projected gradient ascent provide a factor 1 2 approximation to the global maxima. We also study stochastic gradient methods and show that after O(1 2 ) iterations these methods reach solutions which achieve in expectation objective values exceeding ( OPT 2 − ). An immediate application of our results is to maximize submodular functions that are defined stochastically, i.e. the submodular function is defined as an expectation over a family of submodular functions with an unknown distribution. We will show how stochastic gradient methods are naturally well-suited for this setting, leading to a factor 1 2 approximation when the function is monotone. In particular, it allows us to approximately maximize discrete, monotone submodular optimization problems via projected gradient ascent on a continuous relaxation, directly connecting the discrete and continuous domains. Finally, experiments on real data demonstrate that our projected gradient methods consistently achieve the best utility compared to other continuous baselines while remaining competitive in terms of computational effort.
This paper study the problem of continuous submodular maximization subject to a convex constraint. The authors show that for monotone weakly DR-submodular functions, all the stationary points of this problem are actually good enough approximations (gamma^2 / (1 + gamma^2), where gamma is the DR factor) of the optimal value. They also show that stochastic projected gradient descent and mirror descent converge to a stationary point in O(1/eps^2) iterations.
The paper is clear and well presented, with few typos. The results presented can handle more general constraints than prior work and can address the stochastic setting, but at the cost of a worst approximation factor (1/2 for DR-submodular functions as opposed to 1 - 1/e).
Some comments/questions:
-It is worth mentioning that stochastic projected gradient descent was also used recently for submodular minimization in "Chakrabarty, D., Lee, Y. T., Sidford, A., & Wong, S. C. W. Subquadratic submodular function minimization. STOC 2017."
- For the deficiency example of FW in A.2, it would be clearer to present the example with a minibatch setting, with m_i,n = 1/(b+1) batch size, the same example should follow through, but it would make it clearer that a slightly larger minibatch size won't fix the problem.
- Would this deficiency example hold also for the algorithm "Measured continuous greedy" in "Feldman, Moran, Joseph Naor, and Roy Schwartz. "A unified continuous greedy algorithm for submodular maximization." FOCS, 2011, whose updates are slightly different from FW?
- You reference the work [20] on p.2, but I did not find this work online?
- Can you add what are other examples of L-smooth continuous submodular functions, other than the multilinear extension?
- For a more convincing numerical comparison, it would be interesting to see the time comparison (CPU time not just iterations) against FW. 
- What is the y-axis in the figures?
Some typos: 
-line 453: f_ij - f_i - f_j (flipped)
-lemma B.1: right term in the inner product should be proj(y) - x.
-lemma B.2: first term after equality should be D_phi(x,y)
- Eq after line 514 and line 515: grad phi(x+) (nabla missing)
- In proof of lemma B.5: general norm instead of ell_2
- Eq after line 527 and 528: x_t and x^* flipped in inner product.