Non-monotone DR-submodular Maximization: Approximation and Regret Guarantees
This addresses a fundamental optimization problem in machine learning, economics, and communication systems, providing the first approximation guarantees in these settings.
The paper tackles the problem of maximizing non-monotone DR-submodular functions over convex sets in offline and online settings, showing that the Frank-Wolfe algorithm achieves an approximation guarantee dependent on the convex set and the Stochastic Gradient Ascent algorithm achieves a 1/4-approximation ratio with O(1/√T) regret.
Diminishing-returns (DR) submodular optimization is an important field with many real-world applications in machine learning, economics and communication systems. It captures a subclass of non-convex optimization that provides both practical and theoretical guarantees. In this paper, we study the fundamental problem of maximizing non-monotone DR-submodular functions over down-closed and general convex sets in both offline and online settings. First, we show that for offline maximizing non-monotone DR-submodular functions over a general convex set, the Frank-Wolfe algorithm achieves an approximation guarantee which depends on the convex set. Next, we show that the Stochastic Gradient Ascent algorithm achieves a 1/4-approximation ratio with the regret of $O(1/\sqrt{T})$ for the problem of maximizing non-monotone DR-submodular functions over down-closed convex sets. These are the first approximation guarantees in the corresponding settings. Finally we benchmark these algorithms on problems arising in machine learning domain with the real-world datasets.