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 Vondrák (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 $\tfrac{1}{4}(1 - m)$-approximation offline algorithm due to Du (2022). However, only a sub-exponential time $\tfrac{1}{3\sqrt{3}}(1 - m)$-approximation algorithm is known for the corresponding online problem. In this work, we present a polynomial time online algorithm matching the $\tfrac{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 of Du (which was only theoretically studied previously), and show that they consistently outperform previously suggested algorithms on revenue maximization, location summarization and quadratic programming applications.
Introduction
DR-submodular functions are a critical class of non-convex functions that appear frequently in machine learning applications such as mean-field inference and social network influence. While "monotone" functions (where more is always better) are relatively well-understood, non-monotone functions—where adding more of a resource might eventually decrease the objective value—are significantly more challenging to optimize.
Most existing research assumes constraints are down-closed (meaning if a solution is feasible, any "smaller" solution is also feasible). However, real-world constraints often aren't that simple. For example, a budget might need to be fully spent, or a recommendation system might require an exact number of items. This paper addresses the challenge of maximizing non-monotone functions over general convex sets, where the difficulty is tied to a parameter $m$ (the minimum $\ell_\infty$-norm of any feasible vector).
Methods
The authors tackle the problem from three distinct angles to bridge the gap between offline and online settings:
Offline Algorithm
They present an explicit, practical version of the Non-monotone Frank-Wolfe algorithm. This gradient-based iterative approach selects a direction in each step that maximizes the inner product with the current gradient to navigate the constraint set $\mathcal{K}$.
Online Algorithm
The primary contribution is a polynomial-time online algorithm using a "Meta-Frank-Wolfe" framework. To handle functions arriving sequentially over $T$ time steps, the algorithm runs $L$ separate instances of an Online Linear Optimizer (such as Regularized-Follow-the-Leader) in parallel. Each instance manages one "step" of the Frank-Wolfe process across time, allowing the algorithm to achieve low regret ($O(\sqrt{T})$) while maintaining the optimal approximation ratio.
Inapproximability Proof
Using the "symmetry gap" framework, the authors prove that no algorithm running in sub-exponential time can achieve an approximation ratio better than $\tfrac{1}{4}(1-m) + \epsilon$. This establishes that the proposed algorithms are optimal in a strong sense.
Empirical Results
The algorithms were evaluated on several real-world and synthetic benchmarks:
- Social Networks (Revenue Maximization): Tested on Facebook (64k users) and Advogato (6.5k users) networks.
- Location Summarization: Using the Yelp dataset to select representative business locations in Charlotte, NC.
- Synthetic Quadratic Programming: Testing robustness on down-closed polytopes using randomly generated non-positive matrices.
Key findings include:
- Theoretical Optimality: The new online algorithm achieves a $\tfrac{1}{4}(1-m)$ approximation ratio, matching the best-known offline result and the theoretical ceiling.
- Empirical Superiority: The proposed online algorithm significantly outperformed previous state-of-the-art methods across all time steps in revenue and summarization tasks.
- Efficiency: The offline variant consistently beat previous sub-exponential algorithms in quadratic programming tasks, particularly as dimensionality increased.
Conclusion and Future Work
This work resolves the approximability of non-monotone DR-submodular maximization over general convex sets by identifying $\tfrac{1}{4}(1-m)$ as the fundamental limit. However, some limitations remain. If the constraint set $\mathcal{K}$ only contains vectors with very large coordinates ($m \approx 1$), the guarantee becomes weak. Additionally, the current analysis requires the objective function to be smooth and assumes access to gradients. Future research could explore non-smooth functions or bandit feedback environments where only function values are observed.
Summary updated