Bridging the Gap between General and Down-Closed Convex Sets in Submodular Maximization

Loay Mualem, Murad Tukan, Moran Feldman

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

  1. Hybrid Frank-Wolfe/Continuous Greedy: Our offline algorithm tracks two separate vectors: $y$ for the general part and $z$ for the down-closed part.
  2. 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.
  3. 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.

Figure 4: Performance of offline algorithms on the Advogato network, showing the superiority of our proposed methods over the baseline.

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).

Figure 3: Comparison of objective values achieved by our algorithm versus the baseline across iterations, demonstrating a significant performance gap.

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

Abstract

Optimization of DR-submodular functions has experienced a notable surge in significance in recent times, marking a pivotal development within the domain of non-convex optimization. Motivated by real-world scenarios, some recent works have delved into the maximization of non-monotone DR-submodular functions over general (not necessarily down-closed) convex set constraints. Up to this point, these works have all used the minimum L-infinity norm of any feasible solution as a parameter. Unfortunately, a recent hardness result due to Mualem and Feldman shows that this approach cannot yield a smooth interpolation between down-closed and non-down-closed constraints. In this work, we suggest novel offline and online algorithms that provably provide such an interpolation based on a natural decomposition of the convex body constraint into two distinct convex bodies: a down-closed convex body and a general convex body. We also empirically demonstrate the superiority of our proposed algorithms across three offline and two online applications.
BibTeX
@inproceedings{mualem2024bridging,
  author = {Loay Mualem and Murad Tukan and Moran Feldman},
  title = {{Bridging the Gap between General and Down-Closed Convex Sets in Submodular Maximization}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=htb4vveg5e},
}
Figure