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

Area of Science:

• Optimization Theory
• Machine Learning
• Discrete Mathematics

Background:

• Deep Submodular Functions (DSFs) are a significant class of functions with applications in facility location, weighted coverage, and more.
• Maximizing DSFs under matroid constraints is a computationally challenging problem.
• Existing methods like the continuous greedy algorithm offer theoretical guarantees but can be slow.

Purpose of the Study:

• To develop a computationally efficient algorithm for maximizing deep submodular functions (DSFs) subject to a matroid constraint.
• To achieve a better approximation guarantee than existing methods while improving running time.
• To validate the theoretical findings through computational experiments.

Main Methods:

• The study adapts the continuous greedy approach by optimizing a computationally attainable concave relaxation of the multilinear extension of DSFs.
• Gradient ascent is employed to optimize the concave relaxation.
• Pipage rounding is used to recover a discrete solution from the continuous optimization result.

Main Results:

• A novel algorithm is proposed that achieves an approximation guarantee of (1 - 1/e) with a running time of O(n^2/ε).
• This bound is often superior to the standard continuous greedy algorithm's guarantee and offers significantly faster computation.
• The method is effective even for fully curved functions (c=1), where traditional guarantees may degrade.

Conclusions:

• The proposed gradient ascent-based method provides an efficient and effective way to maximize deep submodular functions under matroid constraints.
• The algorithm offers a favorable trade-off between approximation quality and computational cost.
• Empirical results confirm the theoretical advantages of the new approach.