mlsanityData to 14 Oct 2026

Online Submodular Maximization via Online Convex Optimization

arXiv 2309.04339 ↗First posted 8 Sep 2023cs.LG cs.AI math.OCcited by 6

Not on the map. Why?

Abstract (arXiv)

We study monotone submodular maximization under general matroid constraints in the online setting. We prove that online optimization of a large class of submodular functions, namely, weighted threshold potential functions, reduces to online convex optimization (OCO). This is precisely because functions in this class admit a concave relaxation; as a result, OCO policies, coupled with an appropriate rounding scheme, can be used to achieve sublinear regret in the combinatorial setting. We show that our reduction extends to many different versions of the online learning problem, including the dynamic regret, bandit, and optimistic-learning settings.

Key facts. Cited by 6 papers in the map (data through 14 Oct 2026). Builds on 21 of its 88 references that are in the map. First posted on arXiv 8 Sep 2023.

Builds on

21 of 88 references.

References · 21

  1. 2019Introduction to Online Convex Optimizationcited by 803
  2. 2013Optimization, Learning, and Games with Predictable Sequencescited by 188
  3. 2013Non-stationary Stochastic Optimizationcited by 175
  4. 2017Cooperative Game Theory Approaches for Network Partitioningcited by 135
  5. 2018Adaptive Online Learning in Dynamic Environmentscited by 133
  6. 2015Online Optimization : Competing with Dynamic Comparatorscited by 99
  7. 2020Dynamic Regret of Convex and Smooth Functionscited by 90
  8. 2021Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimizationcited by 40
  9. 2018Online Continuous Submodular Maximizationcited by 35
  10. 2019Online Continuous Submodular Maximization: From Full-Information to Bandit Feedbackcited by 33
  11. 2016Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domainscited by 31
  12. 2015Submodular Functions: from Discrete to Continous Domainscited by 25
9 more
  1. 2022Stochastic Continuous Submodular Maximization: Boosting via Non-oblivious Functioncited by 21
  2. 2018Guess Free Maximization of Submodular and Linear Sumscited by 13
  3. 2023Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Banditscited by 13
  4. 2017Stochastic Submodular Maximization: The Case of Coverage Functionscited by 11
  5. 2016Adaptive Caching Networks with Optimality Guaranteescited by 8
  6. 2019Understand Dynamic Regret with Switching Cost for Online Decision Makingcited by 7
  7. 2016Solving Combinatorial Games using Products, Projections and Lexicographically Optimal Basescited by 3
  8. 2021Ascent Similarity Caching with Approximate Indexescited by 2
  9. 2016Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidderscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 3; 2026: 2.

6 papers.

  1. 2025Semantic Caching for Low-Cost LLM Serving: From Offline Learning to Online Adaptationcited by 13
  2. 2025On the Dynamic Regret of Following the Regularized Leader: Optimism with History Pruningcited by 5
  3. 2024Optimistic Online Non-stochastic Control via FTRLcited by 3
  4. 2025Online Two-Stage Submodular Maximizationcited by 0
  5. 2026Provably Optimal Learning Algorithms for Assistance Gamescited by 0
  6. 2026Bandit Submodular Maximization under Matroid Constraints: Learning Compressed Exchange Policycited by 0