Resolving the Approximability of Offline and Online Non-monotone DR-Submodular Maximization over General Convex Sets

Loay Mualem, Moran Feldman

Abstract

Maximizing DR-submodular continuous functions is a critical task in machine learning, operations research, and economics, particularly for modeling phenomena with diminishing returns. Historically, research focused on down-closed convex set constraints due to known inapproximability results for general sets. However, recent work introduced a parameter $m$—the minimum $\ell_\infty$-norm of any feasible vector—to bypass these limits. While offline algorithms achieved a $1/4(1-m)$ approximation ratio, online counterparts remained computationally inefficient or theoretically inferior. This paper resolves this gap by introducing a polynomial-time online algorithm that matches the $1/4(1-m)$ ratio. Furthermore, we provide an inapproximability proof demonstrating that this ratio is optimal for both offline and online settings, and we validate our findings through extensive empirical testing on revenue maximization and data summarization tasks.

Introduction

In the landscape of continuous optimization, DR-submodular functions represent a versatile class of objectives characterized by the "diminishing returns" property. These functions are prevalent in applications ranging from social network marketing and revenue maximization to location summarization.

Traditionally, the optimization of these functions was restricted to "down-closed" constraints—sets where if a solution is feasible, any smaller solution is also feasible. This restriction was largely driven by a 2013 result by Vondrak, which suggested that constant approximation ratios were unattainable for general convex sets. This paper addresses the challenge of non-monotone DR-submodular maximization over general (non-down-closed) convex sets, effectively settling the question of its approximability in both offline and online contexts.

The Role of the $m$ Parameter

The breakthrough in handling general convex sets lies in the parameter $m \in [0, 1)$, defined as the minimum $\ell_\infty$-norm of any vector within the feasible set $\mathcal{K}$. This parameter quantifies how far a constraint set deviates from being down-closed. When $m=0$, the set is potentially down-closed; as $m$ increases, the constraints become more restrictive (e.g., requiring a minimum selection of resources).

Previous work by Du (2022) established a $1/4(1-m)$ approximation for the offline setting. However, the online version—where the objective function changes at every time step $t$—lacked an efficient solution, with existing algorithms requiring sub-exponential time to achieve comparable guarantees.

Algorithmic Framework: Meta-Frank-Wolfe

This work introduces a new polynomial-time online algorithm: the Non-monotone Meta-Frank-Wolfe. This framework nests multiple instances of an online linear optimizer (such as Regularized-Follow-the-Leader) as black boxes. By carefully managing the gradients of the evolving objective functions, the algorithm achieves:

  1. Optimal Approximation: A $1/4(1-m)$ approximation ratio, matching the state-of-the-art offline performance.
  2. Efficiency: Polynomial running time, making it practical for large-scale applications.
  3. Low Regret: A regret bound of $O(\sqrt{T})$, ensuring that the algorithm's performance converges quickly to the best possible fixed strategy over time.

Additionally, the authors provide a refined, practical version of the offline Frank-Wolfe algorithm, simplifying previous analyses and improving empirical execution.

Proving Theoretical Optimality

A core contribution of this research is the proof of inapproximability. Using the "symmetry gap" framework, the authors demonstrate that the $1/4(1-m)$ ratio is not merely a limitation of current algorithms but a fundamental theoretical ceiling. They show that no algorithm—even one with sub-exponential time complexity—can achieve a better approximation ratio unless it possesses specific, non-standard information about the objective function. This result effectively "resolves" the approximability of this problem class.

Empirical Evaluation

The proposed algorithms were tested against several benchmarks across diverse datasets:

  • Revenue Maximization: Using the Facebook (64K nodes) and Advogato (6.5K nodes) social networks, the authors demonstrated that their algorithm consistently yields higher revenue than previous methods by Tháng and Srivastav (2021).
  • Location Summarization: Utilizing the Yelp Dataset, the algorithm selected representative business locations in Charlotte, NC, under complex distance constraints, outperforming existing sub-exponential alternatives.
  • Quadratic Programming: On synthetic datasets (Uniform and Exponential distributions), the refined offline algorithm showed superior scalability and objective values as the problem dimension $n$ increased.

Conclusion

By aligning the theoretical guarantees of online and offline DR-submodular maximization and proving their optimality, this work provides a definitive answer to a major open question in the field. While the approximation ratio remains dependent on the constraint parameter $m$, the introduction of efficient, polynomial-time algorithms with $O(\sqrt{T})$ regret marks a significant advancement for real-world non-monotone optimization problems.

Summary updated

Abstract

In recent years, maximization of DR-submodular continuous functions became an important research field, with many real-worlds applications in the domains of machine learning, communication systems, operation research and economics. Most of the works in this field study maximization subject to down-closed convex set constraints due to an inapproximability result by Vondrak (2013). However, Durr et al. (2021) showed that one can bypass this inapproximability by proving approximation ratios that are functions of m, the minimum $\ell-\infty$ norm of any feasible vector. Given this observation, it is possible to get results for maximizing a DR-submodular function subject to general convex set constraints, which has led to multiple works on this problem. The most recent of which is a polynomial time 1/4(1 - m)-approximation offline algorithm due to Du (2022). However, only a sub-exponential time $(1 - m)/(3^{1.5})$-approximation algorithm is known for the corresponding online problem. In this work, we present a polynomial time online algorithm matching the 1/4(1 - m)-approximation of the state-of-the-art offline algorithm. We also present an inapproximability result showing that our online algorithm and Du’s (2022) offline algorithm are both optimal in a strong sense. Finally, we study the empirical performance of our algorithm and the algorithm Du (2022) (which was only theoretically studied previously), and show that they consistently outperform previously suggested algorithms on revenue maximization, location summarization and quadratic programming applications.
BibTeX
@inproceedings{mualem2023resolving,
  author = {Loay Mualem and Moran Feldman},
  title = {{Resolving the Approximability of Offline and Online Non-monotone DR-Submodular Maximization over General Convex Sets}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
  url = {https://openreview.net/forum?id=J9zEQrImxx},
}
Figure