Poster
Submodular Maximization via Gradient Ascent: The Case of Deep Submodular Functions
Wenruo Bai · William Stafford Noble · Jeffrey A Bilmes
Room 210 #36
Keywords: [ Combinatorial Optimization ] [ Convex Optimization ] [ Submodular Optimization ]
[
Abstract
]
Abstract:
We study the problem of maximizing deep submodular functions (DSFs) 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, 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 with a running time of plus time for pipage rounding
to recover a discrete solution, where is the rank of the matroid constraint. This bound is often better than the standard guarantee of the continuous greedy algorithm, but runs much faster. Our bound also holds even for fully curved () functions where the guarantee of degenerates to where is the curvature of . We perform computational experiments that support our theoretical results.
Live content is unavailable. Log in and register to view live content