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

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

Loay Mualem, Murad Tukan, Moran Feldman

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence
Main Track. Pages 1926-1934. https://doi.org/10.24963/ijcai.2024/213

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.
Keywords:
Constraint Satisfaction and Optimization: CSO: Constraint optimization problems
Machine Learning: ML: Online learning
Search: S: Combinatorial search and optimisation