mlsanityData to 7 Oct 2026

Online Continuous Submodular Maximization: From Full-Information to Bandit Feedback

arXiv 1910.12424 ↗First posted 28 Oct 2019cs.LG stat.MLcited by 33

Not on the map. Why?

Abstract (arXiv)

In this paper, we propose three online algorithms for submodular maximisation. The first one, Mono-Frank-Wolfe, reduces the number of per-function gradient evaluations from T1/2 [Chen2018Online] and T3/2 [chen2018projection] to 1, and achieves a (1-1/e)-regret bound of O(T4/5). The second one, Bandit-Frank-Wolfe, is the first bandit algorithm for continuous DR-submodular maximization, which achieves a (1-1/e)-regret bound of O(T8/9). Finally, we extend Bandit-Frank-Wolfe to a bandit algorithm for discrete submodular maximization, Responsive-Frank-Wolfe, which attains a (1-1/e)-regret bound of O(T8/9) in the responsive bandit setting.

Key facts. Cited by 33 papers in the map (data through 7 Oct 2026). First posted on arXiv 28 Oct 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 6; 2023: 10; 2024: 6; 2025: 3; 2026: 5.

33 papers.

Sort:

  1. 2021Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimizationcited by 40
  2. 2022Stochastic Continuous Submodular Maximization: Boosting via Non-oblivious Functioncited by 21
  3. 2022Resolving the Approximability of Offline and Online Non-monotone DR-Submodular Maximization over General Convex Setscited by 14
  4. 2021Submodular + Concavecited by 13
  5. 2023Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Banditscited by 13
  6. 2023A Unified Approach for Maximizing Continuous DR-submodular Functionscited by 10
  7. 2024Improved Regret for Bandit Convex Optimization with Delayed Feedbackcited by 8
  8. 2024From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimizationcited by 8
  9. 2023Improved Projection-free Online Continuous Submodular Maximizationcited by 7
  10. 2023Nearly Minimax Optimal Submodular Maximization with Bandit Feedbackcited by 7
  11. 2025Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimizationcited by 7
  12. 2022Communication-Efficient Decentralized Online Continuous DR-Submodular Maximizationcited by 6
21 more
  1. 2023Online Submodular Maximization via Online Convex Optimizationcited by 6
  2. 2022Online Submodular Coordination with Bounded Tracking Regret: Theory, Algorithm, and Applications to Multi-Robot Coordinationcited by 5
  3. 2023Bandit Submodular Maximization for Multi-Robot Coordination in Unpredictable and Partially Observable Environmentscited by 5
  4. 2024Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimizationcited by 5
  5. 2022Online Learning for Non-monotone Submodular Maximization: From Full Information to Bandit Feedbackcited by 3
  6. 2023Stochastic Submodular Bandits with Delayed Composite Anonymous Bandit Feedbackcited by 2
  7. 2022One Gradient Frank-Wolfe for Decentralized Online Convex and Submodular Optimizationcited by 1
  8. 2024Bridging the Gap Between General and Down-Closed Convex Sets in Submodular Maximizationcited by 1
  9. 2024No-Regret Mnatural-Concave Function Maximization: Stochastic Bandit Algorithms and Hardness of Adversarial Full-Information Settingcited by 1
  10. 2025Online Nonsubmodular Optimization with Delayed Feedback in the Bandit Settingcited by 1
  11. 2026Improved Approximate Regret for Decentralized Online Continuous Submodular Maximization via Reductionscited by 1
  12. 2026Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Expertscited by 1
  13. 2021Scalable Projection-Free Optimizationcited by 0
  14. 2023Tight Bounds for γ-Regret via the Decision-Estimation Coefficientcited by 0
  15. 2023Allocating Divisible Resources on Arms with Unknown and Random Rewardscited by 0
  16. 2023Leveraging Untrustworthy Commands for Multi-Robot Coordination in Unpredictable Environments: A Bandit Submodular Maximization Approachcited by 0
  17. 2024Performance-Aware Self-Configurable Multi-Agent Networks: A Distributed Submodular Approach for Simultaneous Coordination and Network Designcited by 0
  18. 2025Online Two-Stage Submodular Maximizationcited by 0
  19. 2026γ-weakly θ-up-concavity: A Unified Framework for Non-Convex Optimization Beyond DR-Submodular and OSS Functionscited by 0
  20. 2026Distributed Online Bandit Submodular Maximization with Bounded Sampling Violationscited by 0
  21. 2026Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids, and Full-Bandit Learningcited by 0