Abstract
Optimization of DR-submodular functions has become increasingly significant in non-convex optimization. While recent work has addressed maximizing non-monotone DR-submodular functions over general convex set constraints, existing approaches rely on the minimum $\ell_\infty$ norm ($m$) of feasible solutions, which fails to provide a smooth interpolation between down-closed and general constraints. We propose novel offline and online algorithms that achieve this interpolation by decomposing the convex body constraint into a down-closed part and a general part. Empirical results across multiple applications demonstrate the superiority of our approach.
Introduction
Submodular maximization is a fundamental pillar of discrete optimization, often viewed as the discrete counterpart to convex optimization. In continuous domains, DR-submodular functions are vital for applications like data summarization and robotics. However, a theoretical and practical rift exists between "easy" down-closed constraints (where any solution smaller than a feasible one is also feasible) and "hard" general convex sets.
Previous attempts to bridge this gap used a single parameter $m$, but recent hardness results show this does not allow for a smooth performance transition. This work introduces a decomposition strategy to provide a theoretical and empirical bridge.
Methodology
The core of our approach is representing a general constraint set $K$ as the intersection of a general convex body $K_N$ and a down-closed convex body $K_D$.
Algorithmic Innovations
- Hybrid Frank-Wolfe/Continuous Greedy: Our offline algorithm tracks two separate vectors: $y$ for the general part and $z$ for the down-closed part.
- Probabilistic Sum ($\oplus$): To maintain feasibility within the $[0, 1]^n$ domain, we use $(x \oplus y)_i = 1 - (1-x_i)(1-y_i)$. This allows simultaneous "investment" in both constraint parts without prematurely hitting boundaries.
- Online Regret Minimization: We extend this to online settings using a Regularized-Follow-the-Leader (RFTL) approach for the linear optimization steps.
Empirical Evaluation
We evaluated our algorithms on a Revenue Maximization task using real-world social networks: the Advogato network (6.5K nodes) and the Facebook network (64K nodes). The task involves seeding users to maximize word-of-mouth effects under both minimum and maximum investment constraints.
Key Results and Insights
Our theoretical analysis shows that the approximation ratio smoothly transitions from $\frac{1}{4}(1-m)$ for general sets to $e^{-1} \approx 0.367$ for down-closed sets. Empirically, our algorithms consistently outperform the state-of-the-art baseline established by Mualem & Feldman (2023).
The use of the coordinate-wise probabilistic sum $\oplus$ is crucial. Unlike traditional addition, it prevents coordinates from growing too quickly, keeping the solution competitive throughout the optimization process. Furthermore, the algorithms are polynomial-time, making them practical for the large-scale social networks tested.
Conclusion
By decomposing complex constraints, we provide a robust framework for DR-submodular maximization that adapts to the "difficulty" of the constraint set. Future work includes closing the gap to the theoretical 0.401 ratio and exploring bandit settings in the online case where the function is not fully revealed.
Summary updated