Presented at AAAI 2021, this research addresses a significant gap in the field of continuous optimization: the lack of provable guarantees for online algorithms dealing with non-monotone, diminishing-returns (DR)-submodular functions. By introducing novel algorithmic frameworks, the authors provide the first constant-factor approximation guarantees for these complex problems, bridging the divide between theoretical offline optimization and dynamic, real-world applications.
The Challenge of Non-Monotony and Online Constraints
In many machine learning and economic scenarios, we encounter the principle of diminishing returns. Mathematically, this is captured by DR-submodular functions. While monotone DR-submodular functions (where more input always yields more output) are well-studied, many practical applications are non-monotone. For instance, in social network marketing, increasing an advertising budget to target more users initially increases influence, but excessive targeting can lead to "saturation" or negative consumer sentiment, causing the total reward to decrease.
Furthermore, real-world decision-making is often online. An agent must make sequential decisions (e.g., daily budget allocations) before the specific reward function for that period is revealed by an adversary. The objective is to maximize the cumulative reward over time or, conversely, to minimize regret—the difference between the algorithm's performance and the best fixed decision that could have been made in hindsight.
Theoretical Landscape and Contributions
Prior to this work, no online algorithms existed that could guarantee a constant approximation ratio for non-monotone DR-submodular functions over general convex sets. The authors successfully filled several gaps in the existing literature, as summarized in the table below.
Key Theoretical Results:
- Down-Closed Sets: For constraints where any subset of a feasible solution is also feasible (down-closed), the algorithm achieves a $1/e$ approximation ratio with a regret of $O(T^{3/4})$. This $1/e$ ratio is particularly significant as it matches the best-known theoretical limit for the offline version of the problem.
- General Convex Sets: For more complex constraints that are not down-closed, the authors achieved an approximation ratio of approximately $1/(3\sqrt{3})$ (roughly 0.19) with $O(T/\ln T)$ regret.
Algorithmic Innovation: Lifting and Meta-Frank-Wolfe
The authors' approach relies on two primary technical innovations designed to bypass the inherent non-convexity of the problem:
- Online Vee Learning & Lifting: The core "aha moment" of the paper is the realization that non-convexity in a low-dimensional space can be treated as linearity in a much higher-dimensional space. The authors map the search space onto a high-dimensional lattice (a process called "lifting"). In this lifted space, the complex reward function becomes linear, allowing the use of standard online linear optimization oracles. The solution is then rounded back to the original space.
- Meta-Frank-Wolfe: To handle the broader maximization task, the authors adapted the Meta-Frank-Wolfe framework. This involves running multiple internal instances of their Vee learning algorithm to estimate gradients and iteratively update the solution at each time step without requiring expensive projections onto the constraint set.
Empirical Performance on Social Networks
To validate their theoretical findings, the authors conducted experiments using a Facebook social network dataset containing 20,000 users and 1 million relationships. The task was online revenue maximization, where the algorithm allocated budgets to influence users while edge weights (influence strength) were revealed by an adversary at each step.
As shown in the figures above, the online algorithm significantly outperformed its theoretical lower bounds in practice. In the Facebook experiments, the algorithm achieved an online-to-offline ratio of over 0.44, which is notably better than the $1/e \approx 0.36$ theoretical guarantee for down-closed sets.
Conclusion and Future Directions
This work establishes a new baseline for online non-monotone optimization. While the $O(T^{3/4})$ regret is sub-linear, it remains slower than the $O(\sqrt{T})$ rate common in online convex optimization. Future research may focus on closing this gap or optimizing the computational overhead of the "lifting" technique for even larger-scale industrial applications. Nonetheless, the ability to provide provable guarantees for non-monotone functions marks a major step forward for robust online machine learning.
Summary updated