Submodular Maximization via Gradient Ascent: The Case of Deep Submodular Functions.

ABSTRACT: We study the problem of maximizing deep submodular functions (DSFs) [13, 3] subject to a matroid constraint. DSFs are an expressive class of submodular functions that include, as strict subfamilies, the facility location, weighted coverage, and sums of concave composed with modular functions. We use a strategy similar to the continuous greedy approach [6], but we show that the multilinear extension of any DSF has a natural and computationally attainable concave relaxation that we can optimize using gradient ascent. Our results show a guarantee of max 0 < δ < 1 ( 1 - ϵ - δ - e - δ 2 Ω ( k ) ) with a running time of O(n ² /ϵ ² ) plus time for pipage rounding [6] to recover a discrete solution, where k is the rank of the mat

SUBMITTER: Bai W 

PROVIDER: S-EPMC6351064 | biostudies-literature | 2018 Dec

REPOSITORIES: biostudies-literature