# Online Non-Monotone DR-submodular Maximization

arXiv: https://arxiv.org/abs/1909.11426 · HTML: https://mlsanity.com/paper/1909.11426/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Sep 2019.

## Built on by (most cited first, 10 of 10)

- [Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization](https://mlsanity.com/paper/2102.11050/) (2021)
- [Resolving the Approximability of Offline and Online Non-monotone DR-Submodular Maximization over General Convex Sets](https://mlsanity.com/paper/2210.05965/) (2022)
- [Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Bandits](https://mlsanity.com/paper/2305.12402/) (2023)
- [A Unified Approach for Maximizing Continuous DR-submodular Functions](https://mlsanity.com/paper/2305.16671/) (2023)
- [Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization](https://mlsanity.com/paper/2403.10063/) (2024)
- [Online Learning for Non-monotone Submodular Maximization: From Full Information to Bandit Feedback](https://mlsanity.com/paper/2208.07632/) (2022)
- [Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization over Down-Closed Convex Sets](https://mlsanity.com/paper/2602.20578/) (2026)
- [Online Nonsubmodular Minimization with Delayed Costs: From Full Information to Bandit Feedback](https://mlsanity.com/paper/2205.07217/) (2022)
- [Bridging the Gap Between General and Down-Closed Convex Sets in Submodular Maximization](https://mlsanity.com/paper/2401.09251/) (2024)
- [Improved Approximate Regret for Decentralized Online Continuous Submodular Maximization via Reductions](https://mlsanity.com/paper/2602.09502/) (2026)

## Abstract (arXiv)

In this paper, we study fundamental problems of maximizing DR-submodular continuous functions that have real-world applications in the domain of machine learning, economics, operations research and communication systems. It captures a subclass of non-convex optimization that provides both theoretical and practical guarantees. Here, we focus on minimizing regret for online arriving non-monotone DR-submodular functions over different types of convex sets: hypercube, down-closed and general convex sets. First, we present an online algorithm that achieves a 1/e-approximation ratio with the regret of O(T2/3) for maximizing DR-submodular functions over any down-closed convex set. Note that, the approximation ratio of 1/e matches the best-known guarantee for the offline version of the problem. Moreover, when the convex set is the hypercube, we propose a tight 1/2-approximation algorithm with regret bound of O(√T). Next, we give an online algorithm that achieves an approximation guarantee (depending on the search space) for the problem of maximizing non-monotone continuous DR-submodular functions over a general convex set (not necessarily down-closed). To best of our knowledge, no prior algorithm with approximation guarantee was known for non-monotone DR-submodular maximization in the online setting. Finally we run experiments to verify the performance of our algorithms on problems arising in machine learning domain with the real-world datasets.