This NIPS 2017 paper by Bian et al. represents a significant step forward in non-convex optimization. It provides the first theoretical framework and practical algorithms for maximizing a specific class of non-convex functions—non-monotone continuous DR-submodular functions—under general constraints.
TL;DR
The authors bridge the gap between discrete submodular optimization and continuous non-convex programming by providing the first algorithms with provable approximation guarantees (1/4 and 1/e) for maximizing non-monotone DR-submodular functions. They demonstrate that despite being non-convex, these functions possess a "local-global" structure that allows stationary points to stay relatively close to the global optimum.
What Problem Does This Paper Address?
In the world of optimization, "submodularity" is often called the discrete analogue of convexity. While submodular set functions are well-studied, their continuous counterparts are more complex. Specifically, the authors focus on DR-submodular functions (those exhibiting Diminishing Returns).
The challenge is that while minimizing these functions is relatively easy (similar to convex minimization), maximizing them is generally NP-hard. Previous research had solved this for "monotone" functions (functions that only go up as inputs increase) or for very simple "box" constraints. However, many real-world problems—like MAP inference in Determinantal Point Processes (DPPs) or mean-field inference in machine learning—are non-monotone and involve complex, down-closed convex constraints (like polytopes). This paper fills that theoretical gap.
Methods
The authors propose two primary algorithmic contributions based on the Frank-Wolfe (Conditional Gradient) framework:
- Two-Phase Frank-Wolfe: This algorithm first finds an approximately stationary point in the original constraint set, then finds another in a "shrunken" set, and returns the better of the two. It achieves a 1/4 approximation guarantee. Its main advantage is flexibility; it can use any existing non-convex solver as a subroutine.
- Non-monotone Frank-Wolfe Variant: This is a single-pass algorithm that uses a "shrunken Linear Minimization Oracle (LMO)." By restricting the search direction at each step based on the current position, it prevents the algorithm from growing the solution too aggressively—a common failure mode in non-monotone maximization. This variant achieves a superior theoretical 1/e (~0.36) approximation guarantee.
Additionally, the authors introduce the concept of Strong DR-submodularity (analogous to strong concavity) to provide tighter bounds on how far a stationary point can be from the global maximum.
Datasets
The authors validated their theoretical findings using both synthetic and real-world data:
- Synthetic Quadratic Programming: Randomly generated DR-submodular quadratic objectives with uniform and exponential distributions.
- Softmax Extensions: Synthetic instances of Determinantal Point Processes (DPPs), which are used to model diversity.
- Matched Summarization: A real-world task using the 2012 US Republican Debates dataset. The goal was to select pairs of similar documents from different candidates to create a diverse yet representative summary of the debates.
Key Insights and Ideas
- The Local-Global Relation: The most profound insight is Proposition 1, which proves a mathematical link between stationary points (where the gradient is zero) and the global optimum. In general non-convex optimization, a stationary point could be a terrible local maximum; here, the DR-submodular structure ensures it retains a constant fraction of the optimal value.
- Shrinking is Essential: In non-monotone settings, "more" isn't always "better." Both algorithms succeed by effectively "shrinking" the feasible region as they progress, ensuring the search doesn't overshoot the peak of the function.
- Beyond Boxes: By extending the theory to "conic lattices," the authors show that these techniques can be applied to a much wider range of problems, including logistic regression with non-convex regularizers.
Key Results
- Theoretical Convergence: The 1/e variant is shown to have a sublinear convergence rate, making it computationally efficient for large-scale problems.
- Practical Performance: In experiments, the Two-Phase algorithm often outperformed the 1/e variant and standard baselines like Projected Gradient Ascent, despite having a lower theoretical worst-case bound.
- Robustness: On the 2012 debate data, the proposed methods consistently achieved higher objective values than traditional non-convex solvers, proving that leveraging the DR-submodular structure provides a tangible edge in real-world applications.
Limitations and Future Work
- The Gap Between Theory and Practice: There is a curious discrepancy where the algorithm with the worse theoretical guarantee (1/4) often performs better in practice than the one with the 1/e guarantee. The authors suggest that further research is needed to identify specific problem properties that favor one over the other.
- Constraint Types: While "down-closed convex constraints" cover many cases (like matroids), they do not cover all possible constraint types. Extending these guarantees to non-down-closed sets remains an open challenge.
- Stochastic Settings: The current algorithms assume full access to the gradient. Developing stochastic versions for truly massive datasets where only noisy gradient estimates are available is a logical next step.
Summary updated