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

Loay Mualem, Murad Tukan, Moran Feldman, Chunyan Xu, Jian Yang, Lei Luo

Abstract

This paper addresses the challenge of maximizing non-monotone DR-submodular functions over general convex sets. While existing methods achieve strong approximation guarantees for down-closed constraints, they often struggle with more complex, non-down-closed sets. We propose a novel framework that decomposes general constraints into "down-closed" and "general" components, allowing for a smooth interpolation of approximation ratios. Our approach introduces new offline and online algorithms that leverage a coordinate-wise probabilistic sum to maintain feasibility. Empirical evaluations on revenue maximization tasks using real-world social networks demonstrate that our method consistently outperforms current state-of-the-art techniques.

Introduction

DR-submodular functions are continuous generalizations of discrete submodular set functions, playing a critical role in various machine learning applications such as robotics, data summarization, and viral marketing. A significant hurdle in optimizing these functions is the nature of the constraint set $K$. Optimization is relatively straightforward when $K$ is down-closed (i.e., $x \in K$ and $0 \leq y \leq x$ implies $y \in K$), typically yielding an approximation ratio of $1/e \approx 0.367$.

However, many practical scenarios involve constraints that are not down-closed. For instance, a recommendation system might require a minimum number of items to be selected, or a marketing campaign might have a minimum spend requirement. These lower bounds break the down-closed property. Previous methods for these "general" sets often relied on a single parameter $m$ (the minimum $\ell_\infty$ norm of any feasible point), which led to pessimistic performance guarantees that failed to exploit any underlying down-closed structure. This work bridges that gap by providing a unified approach that adapts to the degree of "down-closedness" in the constraint.

Methodology: Constraint Decomposition

The core innovation lies in viewing a constraint set $K$ not as a monolith, but as a combination of parts. We decompose a general convex body $K$ into $K = (K_N + K_D) \cap [0, 1]^n$, where $K_D$ represents the "easy" down-closed component and $K_N$ captures the "hard" non-down-closed aspects.

Hybrid Algorithms

We introduce two primary algorithms to handle this decomposition:

  1. Offline Hybrid (Algorithm 1): This algorithm runs two parallel Frank-Wolfe-style processes. It applies a "Continuous Greedy" variant to the $K_D$ component to exploit its structure and a non-monotone Frank-Wolfe variant to $K_N$.
  2. Online Hybrid (Algorithm 2): Designed for regret minimization where the objective function evolves over time, this version utilizes Regularized-Follow-the-Leader (RFTL) to dynamically balance the "energy" allocation between the two constraint components.

A key technical contribution is the use of the probabilistic sum operator ($\oplus$), defined as $x \oplus y = x + y - xy$. Unlike a standard vector sum, this operator ensures that the combined solution remains within the $[0, 1]^n$ unit hypercube, preventing coordinates from exceeding 1—a common failure point in continuous submodular optimization.

Figure 2: Comparison of the proposed 'natural' and 'modified' algorithm versions against the state-of-the-art baseline.

Experimental Evaluation

We evaluated our algorithms on a revenue maximization task using two large-scale social network datasets:

  • Advogato Network: A trust-based network with approximately 6.5K users and 61K weighted relationships.
  • Facebook Network: A larger dataset with roughly 64K users and 1M unweighted relationships.

In these experiments, the objective was to maximize "word-of-mouth" revenue by allocating marketing budgets to users. The constraints included both minimum and maximum investment levels, creating a non-down-closed feasible region that challenges traditional optimization methods.

Results and Discussion

Our theoretical analysis shows that the proposed algorithms achieve a smooth interpolation of approximation guarantees. Specifically, they recover the $1/e$ ratio for down-closed sets and the $\frac{1}{4}(1-m)$ ratio for general sets, providing a formal mathematical bridge between the two regimes.

Figure 4: Performance of offline algorithms on the Advogato network, showing the cumulative objective value over iterations.

Empirically, the "Hybrid" algorithms significantly outperformed the previous state-of-the-art method by Mualem & Feldman (2023) across all tested scenarios. As shown in Figure 4, our approach achieves higher objective values on the Advogato network. Furthermore, the algorithms demonstrated high efficiency, scaling effectively to the 64K nodes of the Facebook network, proving their practicality for real-world large-scale applications.

Conclusion

By decomposing constraints into manageable components, we provide a more flexible and powerful framework for DR-submodular maximization. Our method not only offers stronger theoretical guarantees but also delivers superior performance in real-world applications like social network marketing. This approach proves that algorithms can be robust to "nearly" down-closed constraints by exploiting their inherent structure. Future work will explore integrating more advanced greedy components and applying this framework to fairness-constrained optimization problems.

Summary updated

BibTeX
@inproceedings{mualem2024bridging,
  author = {Loay Mualem and Murad Tukan and Moran Feldman and Chunyan Xu and Jian Yang and Lei Luo},
  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