# Improved Projection-free Online Continuous Submodular Maximization

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 29 references that are in the map.
- First posted on arXiv 29 May 2023.

## Builds on (most cited first, 13 of 13)

- [Variance-Reduced and Projection-Free Stochastic Optimization](https://mlsanity.com/paper/1602.02101/) (2016)
- [Faster Projection-free Online Learning](https://mlsanity.com/paper/2001.11568/) (2020)
- [Online Continuous Submodular Maximization](https://mlsanity.com/paper/1802.06052/) (2018)
- [Gradient Methods for Submodular Maximization](https://mlsanity.com/paper/1708.03949/) (2017)
- [Online Continuous Submodular Maximization: From Full-Information to Bandit Feedback](https://mlsanity.com/paper/1910.12424/) (2019)
- [Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains](https://mlsanity.com/paper/1606.05615/) (2016)
- [Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularity](https://mlsanity.com/paper/1802.08183/) (2018)
- [New Projection-free Algorithms for Online Convex Optimization with Adaptive Regret Guarantees](https://mlsanity.com/paper/2202.04721/) (2022)
- [Stochastic Continuous Submodular Maximization: Boosting via Non-oblivious Function](https://mlsanity.com/paper/2201.00703/) (2022)
- [Decentralized Submodular Maximization: Bridging Discrete and Continuous Settings](https://mlsanity.com/paper/1802.03825/) (2018)
- [Continuous Submodular Function Maximization](https://mlsanity.com/paper/2006.13474/) (2020)
- [Non-monotone DR-Submodular Function Maximization](https://mlsanity.com/paper/1612.00960/) (2016)
- [Communication-Efficient Decentralized Online Continuous DR-Submodular Maximization](https://mlsanity.com/paper/2208.08681/) (2022)

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

- [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)
- [Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization](https://mlsanity.com/paper/2501.18183/) (2025)
- [Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization](https://mlsanity.com/paper/2403.10063/) (2024)
- [Online Nonsubmodular Optimization with Delayed Feedback in the Bandit Setting](https://mlsanity.com/paper/2508.00523/) (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)
- [Dec-BFTRL: Squre-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximization](https://mlsanity.com/paper/2608.30271/) (2026)

## Abstract (arXiv)

We investigate the problem of online learning with monotone and continuous DR-submodular reward functions, which has received great attention recently. To efficiently handle this problem, especially in the case with complicated decision sets, previous studies have proposed an efficient projection-free algorithm called Mono-Frank-Wolfe (Mono-FW) using O(T) gradient evaluations and linear optimization steps in total. However, it only attains a (1-1/e)-regret bound of O(T4/5). In this paper, we propose an improved projection-free algorithm, namely POBGA, which reduces the regret bound to O(T3/4) while keeping the same computational complexity as Mono-FW. Instead of modifying Mono-FW, our key idea is to make a novel combination of a projection-based algorithm called online boosting gradient ascent, an infeasible projection technique, and a blocking technique. Furthermore, we consider the decentralized setting and develop a variant of POBGA, which not only reduces the current best regret bound of efficient projection-free algorithms for this setting from O(T4/5) to O(T3/4), but also reduces the total communication complexity from O(T) to O(√T).