# Continuous Submodular Maximization: Beyond DR-Submodularity

arXiv: https://arxiv.org/abs/2006.11726 · HTML: https://mlsanity.com/paper/2006.11726/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jun 2020.

## Built on by (most cited first, 1 of 1)

- [Nearly Minimax Optimal Submodular Maximization with Bandit Feedback](https://mlsanity.com/paper/2310.18465/) (2023)

## Abstract (arXiv)

In this paper, we propose the first continuous optimization algorithms that achieve a constant factor approximation guarantee for the problem of monotone continuous submodular maximization subject to a linear constraint. We first prove that a simple variant of the vanilla coordinate ascent, called Coordinate-Ascent+, achieves a (frace-12e-1-varepsilon)-approximation guarantee while performing O(n/varepsilon) iterations, where the computational complexity of each iteration is roughly O(n/√varepsilon+nlog n) (here, n denotes the dimension of the optimization problem). We then propose Coordinate-Ascent++, that achieves the tight (1-1/e-varepsilon)-approximation guarantee while performing the same number of iterations, but at a higher computational complexity of roughly O(n3/varepsilon2.5 + n3 log n / varepsilon2) per iteration. However, the computation of each round of Coordinate-Ascent++ can be easily parallelized so that the computational cost per machine scales as O(n/√varepsilon+nlog n).