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:
- Optimal Approximation: A $1/4(1-m)$ approximation ratio, matching the state-of-the-art offline performance.
- Efficiency: Polynomial running time, making it practical for large-scale applications.
- 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