# Online Continuous Submodular Maximization

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

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Feb 2018.

## Built on by (most cited first, 30 of 35)

- [Stochastic Continuous Submodular Maximization: Boosting via Non-oblivious Function](https://mlsanity.com/paper/2201.00703/) (2022)
- [Resolving the Approximability of Offline and Online Non-monotone DR-Submodular Maximization over General Convex Sets](https://mlsanity.com/paper/2210.05965/) (2022)
- [Submodular + Concave](https://mlsanity.com/paper/2106.04769/) (2021)
- [Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Bandits](https://mlsanity.com/paper/2305.12402/) (2023)
- [Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Acceleration](https://mlsanity.com/paper/2305.08367/) (2023)
- [A Unified Approach for Maximizing Continuous DR-submodular Functions](https://mlsanity.com/paper/2305.16671/) (2023)
- [From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization](https://mlsanity.com/paper/2405.00065/) (2024)
- [Fast First-Order Methods for Monotone Strongly DR-Submodular Maximization](https://mlsanity.com/paper/2111.07990/) (2021)
- [Improved Projection-free Online Continuous Submodular Maximization](https://mlsanity.com/paper/2305.18442/) (2023)
- [Nearly Minimax Optimal Submodular Maximization with Bandit Feedback](https://mlsanity.com/paper/2310.18465/) (2023)
- [Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization](https://mlsanity.com/paper/2501.18183/) (2025)
- [Communication-Efficient Decentralized Online Continuous DR-Submodular Maximization](https://mlsanity.com/paper/2208.08681/) (2022)
- [Bandit Submodular Maximization for Multi-Robot Coordination in Unpredictable and Partially Observable Environments](https://mlsanity.com/paper/2305.12795/) (2023)
- [Online Submodular Maximization via Online Convex Optimization](https://mlsanity.com/paper/2309.04339/) (2023)
- [Boosting Gradient Ascent for Continuous DR-submodular Maximization](https://mlsanity.com/paper/2401.08330/) (2024)
- [Online Submodular Coordination with Bounded Tracking Regret: Theory, Algorithm, and Applications to Multi-Robot Coordination](https://mlsanity.com/paper/2209.12429/) (2022)
- [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)
- [Improved Regret Bounds for Online Submodular Maximization](https://mlsanity.com/paper/2106.07836/) (2021)
- [Ascent Similarity Caching with Approximate Indexes](https://mlsanity.com/paper/2107.00957/) (2021)
- [Projection-Free Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/2305.01333/) (2023)
- [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)
- [Online Learning for Approximately-Convex Functions with Long-term Adversarial Constraints](https://mlsanity.com/paper/2508.16992/) (2025)
- [Improved Approximate Regret for Decentralized Online Continuous Submodular Maximization via Reductions](https://mlsanity.com/paper/2602.09502/) (2026)
- [γ-weakly θ-up-concavity: A Unified Framework for Non-Convex Optimization Beyond DR-Submodular and OSS Functions](https://mlsanity.com/paper/2602.13506/) (2026)
- [Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Experts](https://mlsanity.com/paper/2606.14929/) (2026)
- [Scalable Projection-Free Optimization](https://mlsanity.com/paper/2105.03527/) (2021)
- [Online Decentralized Frank-Wolfe: From theoretical bound to applications in smart-building](https://mlsanity.com/paper/2208.00522/) (2022)

## Abstract (arXiv)

In this paper, we consider an online optimization process, where the objective functions are not convex (nor concave) but instead belong to a broad class of continuous submodular functions. We first propose a variant of the Frank-Wolfe algorithm that has access to the full gradient of the objective functions. We show that it achieves a regret bound of O(√T) (where T is the horizon of the online optimization problem) against a (1-1/e)-approximation to the best feasible solution in hindsight. However, in many scenarios, only an unbiased estimate of the gradients are available. For such settings, we then propose an online stochastic gradient ascent algorithm that also achieves a regret bound of O(√T) regret, albeit against a weaker 1/2-approximation to the best feasible solution in hindsight. We also generalize our results to γ-weakly submodular functions and prove the same sublinear regret bounds. Finally, we demonstrate the efficiency of our algorithms on a few problem instances, including non-convex/non-concave quadratic programs, multilinear extensions of submodular set functions, and D-optimal design.