This paper considers the problems of maximizing a continuous nonmonotone submodular function over the hypercube, both with and without coordinatewise concavity. This family of optimization problems has several applications in machine learning, economics, and communication systems. The main result is
the first 1/2approximation algorithm for continuous submodular function maximization; this approximation factor of 1/2 is the best possible for algorithms that only query the objective function at polynomially many points. For the special case of DRsubmodular maximization, i.e. when the submodular functions are also coordinatewise concave along all coordinates, we provide a different 1 2approximation algorithm that runs in quasilinear time.
more »
« less
Fast FirstOrder Methods for Monotone Strongly DRSubmodular Maximization
Continuous DRsubmodular functions are a class of functions that satisfy the Diminishing Returns (DR) property, which implies that they are concave along nonnegative directions. Existing works have studied monotone continuous DRsubmodular maximization subject to a convex constraint and have proposed efficient algorithms with approximation guarantees. However, in many applications, e. g., computing the stability number of a graph and meanfield inference for probabilistic logsubmodular models, the DRsubmodular function has the additional property of being strongly concave along nonnegative directions that could be utilized for obtaining faster convergence rates. In this paper, we first introduce and characterize the class of strongly DRsubmodular functions and show how such a property implies strong concavity along nonnegative directions. Then, we study Lsmooth monotone strongly DRsubmodular functions that have bounded curvature, and we show how to exploit such additional structure to obtain algorithms with improved approximation guarantees and faster convergence rates for the maximization problem. In particular, we propose the SDRFW algorithm that matches the provably optimal approximation ratio after only iterations, where c ∈ [0,1] and μ ≥ 0 are the curvature and the strong DRsubmodularity parameter. Furthermore, we study the Projected Gradient Ascent (PGA) method for this problem and provide a refined analysis of the algorithm with an improved approximation ratio (compared to ½ in prior works) and a linear convergence rate. Given that both algorithms require knowledge of the smoothness parameter L, we provide a novel characterization of L for DRsubmodular functions showing that in many cases, computing L could be formulated as a convex optimization problem, i. e., a geometric program, that could be solved efficiently. Experimental results illustrate and validate the efficiency and effectiveness of our algorithms.
more »
« less
 Award ID(s):
 2023166
 NSFPAR ID:
 10443284
 Editor(s):
 Berry, Jonathan; Shmoys, David; Cowen, Lenore; Naumann, Uwe
 Date Published:
 Journal Name:
 Proceedings of SIAM Conference on Applied and Computational Discrete Algorithms
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


We consider the problem of maximizing the multilinear extension of a submodular function subject a single matroid constraint or multiple packing constraints with a small number of adaptive rounds of evaluation queries. We obtain the first algorithms with low adaptivity for submodular maximization with a matroid constraint. Our algorithms achieve a $11/e\epsilon$ approximation for monotone functions and a $1/e\epsilon$ approximation for nonmonotone functions, which nearly matches the best guarantees known in the fully adaptive setting. The number of rounds of adaptivity is $O(\log^2{n}/\epsilon^3)$, which is an exponential speedup over the existing algorithms. We obtain the first parallel algorithm for nonmonotone submodular maximization subject to packing constraints. Our algorithm achieves a $1/e\epsilon$ approximation using $O(\log(n/\epsilon) \log(1/\epsilon) \log(n+m)/ \epsilon^2)$ parallel rounds, which is again an exponential speedup in parallel time over the existing algorithms. For monotone functions, we obtain a $11/e\epsilon$ approximation in $O(\log(n/\epsilon)\log(m)/\epsilon^2)$ parallel rounds. The number of parallel rounds of our algorithm matches that of the state of the art algorithm for solving packing LPs with a linear objective (Mahoney et al., 2016). Our results apply more generally to the problem of maximizing a diminishing returns submodular (DRsubmodular) function.more » « less

Kraus, Andreas (Ed.)In this paper we study the fundamental problems of maximizing a continuous nonmonotone submodular function over the hypercube, both 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; this approximation factor of 1 2 is the best possible for algorithms that only query the objective function at polynomially many points. For the special case of DRsubmodular maximization, i.e. when the submodular function is also coordinatewise concave along all coordinates, we provide a different 1 2 approximation algorithm that runs in quasilinear time. Both these results improve upon prior work (Bian et al., 2017a,b; Soma and Yoshida, 2017). Our first algorithm uses novel ideas such as reducing the guaranteed approximation problem to analyzing a zerosum game for each coordinate, and incorporates the geometry of this zerosum game to fix the value at this coordinate. Our second algorithm exploits coordinatewise 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.more » « less

null (Ed.)We introduce the problem of optimal congestion control in cache networks, whereby both rate allocations and content placements are optimized jointly. We formulate this as a maximization problem with nonconvex constraints, and propose solving this problem via (a) a Lagrangian barrier algorithm and (b) a convex relaxation. We prove different optimality guarantees for each of these two algorithms; our proofs exploit the fact that the nonconvex constraints of our problem involve DRsubmodular functions.more » « less

We study the problem of differentially private constrained maximization of decomposable submodular functions. A submodular function is decomposable if it takes the form of a sum of submodular functions. The special case of maximizing a monotone, decomposable submodular function under cardinality constraints is known as the Combinatorial Public Projects (CPP) problem (Papadimitriou, Schapira, and Singer 2008). Previous work by Gupta et al. (2010) gave a differentially private algorithm for the CPP problem. We extend this work by designing differentially private algorithms for both monotone and nonmonotone decomposable submodular maximization under general matroid constraints, with competitive utility guarantees. We complement our theoretical bounds with experiments demonstrating improved empirical performance.more » « less