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

Loay Mualem, Murad Tukan, Moran Feldman

Abstract

The optimization of Continuous Diminishing Returns (DR)-submodular functions has become a cornerstone of non-convex optimization, particularly in applications involving resource allocation and summarization. While algorithms for down-closed constraints are well-established, maximizing non-monotone functions over general convex sets remains a significant challenge. This paper introduces a novel decomposition-based approach that bridges the performance gap between these two constraint types. By partitioning a general convex body into down-closed and general components, the proposed offline and online algorithms provide a smooth interpolation of performance guarantees, outperforming existing state-of-the-art methods in both theory and practice.

Introduction

Submodular functions mathematically formalize the "law of diminishing returns," where the marginal gain of an element decreases as the set of selected elements grows. In the continuous domain, DR-submodular functions extend this concept to non-convex optimization. These functions are ubiquitous in machine learning, powering tasks such as sensor placement, viral marketing, and data summarization.

A critical distinction in this field is the nature of the constraints. Down-closed constraints represent "up to" scenarios (e.g., spending at most a certain budget), where any subset of a feasible solution is also feasible. These are relatively well-behaved. However, general convex sets often include lower bounds or complex boundaries (e.g., requiring a minimum level of activity), making optimization significantly harder. Previous research attempted to bridge this gap using the minimum $\ell_\infty$ norm of feasible solutions, but recent findings by Mualem and Feldman (2023) demonstrated that this metric fails to provide a smooth transition in performance between easy and hard constraints.

Methodology: The Decomposition Approach

The primary innovation of this work is a structural decomposition of the constraint set. The authors propose that any general convex body $K$ can be represented as the sum of two distinct parts:

  1. $K_D$ (Down-Closed): A component that adheres to the down-closed property, allowing for more efficient optimization.
  2. $K_N$ (General): A component representing the "hard" constraints that do not follow the down-closed rule.

The Hybrid Algorithm

To leverage this decomposition, the researchers developed a Hybrid Algorithm that maintains two separate optimization vectors, $y$ and $z$, in parallel.

  • The vector $y$ is updated using a "Continuous Greedy" strategy, which is specifically optimized for the down-closed component $K_D$.
  • The vector $z$ is updated using a variant of the "Frank-Wolfe" algorithm, tailored for the general component $K_N$.

A significant challenge in maintaining two vectors is ensuring their combination remains feasible within the $[0, 1]^n$ hypercube. Simple vector addition ($y + z$) often violates these boundaries. The authors solve this by employing a coordinate-wise probabilistic sum ($y \oplus z$), defined as $1 - (1-y)(1-z)$. This operation ensures the combined solution stays within valid limits while effectively merging the progress of both optimization paths. Furthermore, a novel potential function allows the algorithm to balance these vectors dynamically without requiring prior knowledge of the optimal solution.

Theoretical Insights

The proposed framework provides the first "smooth interpolation" guarantee. Unlike previous methods where performance might drop sharply when moving from down-closed to general constraints, this algorithm's performance guarantee scales gracefully based on how much of the optimal solution resides within the down-closed portion of the constraint.

Notably, the mathematical framework is robust: if the general component $K_N$ is null, the algorithm recovers the classic $1/e \approx 0.367$ approximation ratio, which has been the gold standard for submodular maximization over down-closed sets for decades.

Empirical Results

The researchers validated their approach across several real-world and synthetic benchmarks:

  • Revenue Maximization: Using the Facebook (1M edges) and Advogato (61k edges) social networks, the authors simulated viral marketing campaigns. Their algorithm consistently outperformed the previous state-of-the-art in both offline and online (streaming) settings, identifying more influential sets of users under complex constraints.
  • Location Summarization: On the Yelp dataset for Charlotte, NC, the algorithm was used to generate concise business summaries. It consistently achieved higher objective values than existing methods throughout the experimental duration.
  • Quadratic Programming (QP): In synthetic tests using Uniform and Exponential distributions, the hybrid approach matched or exceeded the performance of specialized QP algorithms while offering greater flexibility for non-quadratic submodular functions.

Discussion and Future Work

While the decomposition method offers superior performance and theoretical elegance, it introduces additional computational overhead by running two optimization processes in parallel. The authors also note that while they recover the $1/e$ ratio, the absolute state-of-the-art for down-closed sets is slightly higher at $0.401$. Future research will focus on refining the hybrid approach to reach this higher threshold.

Additionally, the authors highlight the potential of this decomposition for Fairness in AI. Many fairness constraints (e.g., ensuring minimum representation for certain groups) can be modeled as non-down-closed constraints. This work provides a mathematical foundation for integrating such requirements into submodular optimization frameworks without sacrificing significant performance.

Conclusion

By shifting the focus from a single numerical parameter to the underlying structure of the constraint set, this work provides a more nuanced and effective way to handle general convex constraints in submodular maximization. The decomposition strategy and the use of probabilistic summation offer a robust path forward for complex, real-world optimization problems.

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 $\ell_\infty$ norm of any feasible solution as a parameter. Unfortunately, a recent hardness result due to Mualem \& Feldman~\cite{mualem2023resolving} 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