Abstract
Continuous DR-submodular maximization is a critical framework for non-convex optimization problems such as MAP inference in Determinantal Point Processes and mean-field inference. While monotone cases are well-understood, non-monotone functions over general convex constraints present significant challenges. This paper introduces two novel algorithms: a Two-Phase Frank-Wolfe approach and a specialized Non-monotone Frank-Wolfe variant, providing the first constant-factor approximation guarantees of 1/4 and 1/e, respectively. Empirical evaluations on synthetic and real-world summarization tasks demonstrate that these algorithms consistently outperform standard baselines and often exceed their theoretical performance bounds.
Introduction
Optimization typically relies on convexity to ensure local optima are global. However, many practical applications involve non-convex objectives. DR-submodularity, a continuous generalization of submodularity characterized by diminishing returns, offers a structured approach to a subset of these non-convex problems. While algorithms for monotone DR-submodular functions exist, the non-monotone case—where the objective may decrease as variables increase—remains difficult under general constraints. This work bridges this gap by leveraging the specific geometric properties of DR-submodular functions.
Methods
The authors propose two primary algorithmic strategies to address the non-monotone setting:
- Two-Phase Frank-Wolfe (Algorithm 1): This method utilizes a non-convex solver as a subroutine. It identifies an approximately stationary point within the original constraint set, then optimizes again within a "shrunken" subset of the constraints. By returning the better of the two results, it achieves a 1/4 approximation guarantee.
- Non-monotone Frank-Wolfe Variant (Algorithm 2): This integrated approach employs a "shrunken Linear Minimization Oracle (LMO)" at each iteration. This restriction prevents the solution from overshooting the optimal region in non-monotone landscapes, yielding a 1/e (~0.36) approximation guarantee with sublinear convergence.
A key theoretical contribution is the "Local-Global Relation," which proves that for DR-submodular functions, any approximately stationary point is mathematically bounded relative to the global optimum.
Experimental Validation
The algorithms were tested on three types of problem instances:
- Synthetic DR-submodular Quadratic Programming: Tested with both uniform and exponential distributions to evaluate robustness.
- Softmax Extensions of DPPs: Synthetic instances simulating MAP inference tasks.
- Matched Summarization: A real-world task using 2012 US Republican debate data to select document pairs that are similar yet collectively diverse.
Results and Discussion
The theoretical bounds (1/4 and 1/e) represent the first such guarantees for this problem class. Empirically, the Two-Phase Frank-Wolfe method demonstrated exceptional performance, frequently outperforming the 1/e variant and standard projected gradient ascent.
As shown in the figure above, the Two-Phase method (magenta) consistently achieves higher approximation ratios across varying dimensionalities compared to the standard Frank-Wolfe variant and projected gradient methods. This robustness is further evidenced across different data distributions, such as exponential settings, where the performance gap between the proposed methods and baselines remains significant.
On the Republican debate dataset, the Two-Phase algorithm consistently achieved the highest function values, demonstrating its practical utility for complex data summarization tasks where non-monotonicity is a core feature.
Conclusion
This work establishes a solid theoretical and practical foundation for non-monotone DR-submodular maximization. While current theory relies on down-closed convex constraints, the empirical success of these algorithms suggests broader applicability. Future research will focus on extending these guarantees to more general convex sets and exploring the efficiency of the Two-Phase method's subroutines in more complex conic lattices.
Summary updated