Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization
In this paper we study the fundamental problems of maximizing abcontinuous non-monotone submodular function over a hypercube, with and without coordinatewise concavity. This family of optimization problems has several applications in machine learning, economics, and communication systems. Our main result is the first 1 2 -approximation algorithm for continuous submodular function maximization; the approximation factor of 1 2 is the best possible for algorithms that use only polynomially many queries. For the special case of DR-submodular maximization, i.e., when the submodular functions is also coordinate-wise concave along all coordinates, we provide a faster 1 2 -approximation algorithm that runs in almost linear time. Both of these results improve upon prior work [Bian et al., 2017a,b,  Soma and Yoshida, 2017, Buchbinder et al., 2012. Our first algorithm is a single-pass algorithm that uses novel ideas such as reducing the guaranteed approximation problem to analyzing a zero-sum game for each coordinate, and incorporates the geometry of this zero-sum game to fix the value at this coordinate. Our second algorithm is a faster single-pass algorithm that exploits coordinate-wise concavity to identify a monotone equilibrium condition sufficient for getting the required approximation guarantee, and hunts for the equilibrium point using binary search. We further run experiments to verify the performance of our proposed algorithms in related machine learning applications.
This paper concerns a different well-studied setting, where L is a hypercube (i.e., [0,1] n ), with componentwise maximum and minimum serving as the join and meet, respectively. 3 We consider the fundamental problem of (approximately) maximizing a continuous and nonnegative submodular function over the hypercube. 4 The function F is given as a "black box" and can only be accessed by querying its value at a point. We are interested in algorithms that use at most a polynomial (in n) number of queries. We do not assume that F is monotone (otherwise the problem is trivial).
We next briefly mention four applications of maximizing a non-monotone submodular function over a hypercube that are germane to machine learning and other related application domains.
The paper is about maximizing non-monotone continuous submodular functions on the hypercube [0,1]^n. The main result of the paper is an algorithm that provides a tight (1/2-eps)-optimal solution using O(n^2/eps) complexity. The algorithm is built on the double-greedy algorithm proposed by Buchbinder et al for maximizing non-monotone submodular set functions, however, it turns out that a number of novel ideas have to be added to extend the algorithm to continuous submodular functions (e.g. the coordinate-wise zero-sum game strategy to decide the value of the final solution at each coordinate). A 1/2-optimal algorithm was already known for DR-submodular functions and a 1/3-opt efficient algorithm was known for continuous submodular functions, both based on the double-greedy method, however, I find the case of general continuous submodular functions much more difficult than maximizing non-monotone DR-submodular functions. All in all, after a careful read, I find the results of the paper quite novel and I recommend acceptance.  I don't have any major comments and only have a few suggestions. First of all, the dependency to the dimension n, i.e.  n^2, can perhaps be improved by a more intelligent (and adaptive over rounds using submodularity and lazy updates) discretization method. Second, it's worth to mention how many function computations your algorithm needs (i.e. is it O(n/eps) or O(n^2/eps)--I suspect that the latter is the case ).