# Improved Approximate Regret for Decentralized Online Continuous Submodular Maximization via Reductions

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 37 references that are in the map.
- First posted on arXiv 10 Feb 2026.

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

- [Faster Projection-free Online Learning](https://mlsanity.com/paper/2001.11568/) (2020)
- [Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization](https://mlsanity.com/paper/2102.11050/) (2021)
- [Online Continuous Submodular Maximization](https://mlsanity.com/paper/1802.06052/) (2018)
- [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)
- [Stochastic Continuous Submodular Maximization: Boosting via Non-oblivious Function](https://mlsanity.com/paper/2201.00703/) (2022)
- [Multi-consensus Decentralized Accelerated Gradient Descent](https://mlsanity.com/paper/2005.00797/) (2020)
- [Resolving the Approximability of Offline and Online Non-monotone DR-Submodular Maximization over General Convex Sets](https://mlsanity.com/paper/2210.05965/) (2022)
- [Projection-free Distributed Online Learning with Sublinear Communication Complexity](https://mlsanity.com/paper/2103.11102/) (2021)
- [Online Non-Monotone DR-submodular Maximization](https://mlsanity.com/paper/1909.11426/) (2019)
- [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)
- [Optimal and Efficient Algorithms for Decentralized Online Convex Optimization](https://mlsanity.com/paper/2402.09173/) (2024)
- [Improved Projection-free Online Continuous Submodular Maximization](https://mlsanity.com/paper/2305.18442/) (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)
- [Boosting Gradient Ascent for Continuous DR-submodular Maximization](https://mlsanity.com/paper/2401.08330/) (2024)
- [Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization](https://mlsanity.com/paper/2403.10063/) (2024)
- [Projection-free Online Learning with Arbitrary Delays](https://mlsanity.com/paper/2204.04964/) (2022)

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

- [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)

To expand the applicability of decentralized online learning, previous studies have proposed several algorithms for decentralized online continuous submodular maximization (D-OCSM) -- a non-convex/non-concave setting with continuous DR-submodular reward functions. However, there exist large gaps between their approximate regret bounds and the regret bounds achieved in the convex setting. Moreover, if focusing on projection-free algorithms, which can efficiently handle complex decision sets, they cannot even recover the approximate regret bounds achieved in the centralized setting. In this paper, we first demonstrate that for D-OCSM over general convex decision sets, these two issues can be addressed simultaneously. Furthermore, for D-OCSM over downward-closed decision sets, we show that the second issue can be addressed while significantly alleviating the first issue. Our key techniques are two reductions from D-OCSM to decentralized online convex optimization (D-OCO), which can exploit D-OCO algorithms to improve the approximate regret of D-OCSM in these two cases, respectively.