Name
Title | ||
|---|---|---|
Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization. |
Abstract | ||
|---|---|---|
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 [Bjan et al., 2017a,b, Soma and Yoshida, 2017, Buchbinder et al., 2012, 2015]. 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. |
Year | Venue | Keywords |
|---|---|---|
2018 | ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 31 (NIPS 2018) | optimization problems,machine learning,approximation problem,binary search,communication systems,equilibrium point,approximation algorithm,full spectrum,extensive-form game,identically distributed |
DocType | Volume | Issue |
Conference | 31 | 125 |
ISSN | Citations | PageRank |
1049-5258 | 1 | 0.35 |
References | Authors | |
3 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rad Niazadeh | 1 | 8 | 4.34 |
| Tim Roughgarden | 2 | 4177 | 353.32 |
| Joshua R. Wang | 3 | 69 | 5.83 |