Research map / Bandits and online learning / Online convex optimization and games
Online Submodular Maximization via Online Convex Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that online maximization of weighted threshold potential submodular functions over matroids reduces to online convex optimization via concave relaxations and negatively correlated (swap/pipage) rounding, extending to dynamic, optimistic and bandit settings.
Problem
Online maximization of monotone submodular reward functions under general matroid constraints, with no-regret guarantees (alpha-regret), including dynamic, optimistic, and bandit variants.
Approach
Weighted threshold potential functions admit concave relaxations of the same functional form that upper-bound them on integral points and lower-bound them in expectation under negatively correlated rounding (swap or pipage rounding over matroids); any OCO policy run on these relaxations, combined with rounding (RAOCO), yields sublinear (1-1/e)-regret.
Key results
- RAOCO-OMA achieves normalized reward of about 0.965 on ZKC uniform matroid at t=T/3 versus 0.839 for TabularGreedy and 0.833 for FSF*.
- The reduction gives O(sqrt(T)) alpha-regret with alpha=1-1/e for matroid-constrained WTP functions, and O(sqrt(P_T T)) dynamic alpha-regret under OMA.
- RAOCO is reported to be 2.15-250 times faster than TabularGreedy and FSF*.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use RAOCO-OMA instead of FSF* | Online submodular maximization · ZKC, uniform, t=99 | normalized average cumulative reward: 0.933 -> 0.982 | Helped |
| Use RAOCO-OMA instead of TabularGreedy | Online submodular maximization · Epinions, partition, t=149 | normalized average cumulative reward: 0.818 -> 0.927 | Helped |
| Use RAOCO-OMA instead of TabularGreedy | Online submodular maximization · MovieLens, partition, t=293 | normalized average cumulative reward: 0.964 -> 0.948 | Hurt |
| Use RAOCO-OMA instead of TabularGreedy | Online submodular maximization · MovieLens, uniform, t=293 | normalized average cumulative reward: 0.769 -> 0.866 | Helped |
| Use RAOCO-OMA instead of RAOCO-OGA | RAOCO · ZKC, uniform, t=99 | normalized average cumulative reward: 0.945 -> 0.982 | Helped |
| Use RAOCO-OMA instead of RAOCO-OGA | RAOCO · MovieLens, uniform, t=196 | normalized average cumulative reward: 0.786 -> 0.781 | Hurt |
| Use RAOCO-OGA instead of TabularGreedy | Online submodular maximization · SynthTF, uniform, t=99 | normalized average cumulative reward: 0.902 -> 0.995 | Helped |
| Use RAOCO instead of TabularGreedy | Online submodular maximization · MovieLens | normalized average cumulative reward | Mixed |
| Use RAOCO-OMA instead of RAOCO-OGA | RAOCO · Experiments across datasets and constraints | normalized average cumulative reward | Mixed |
| Use RAOCO instead of TabularGreedy and FSF* | Online submodular maximization · Experiments across datasets | running time: 2.15-250 times faster | Helped |
| Provide predictions to optimistic policies | RAOCO optimistic setting · Non-stationary scenario | average cumulative reward | Helped |
| Use RAOCO-OGA, RAOCO-OMA, or FSF* rather than other policies | Dynamic online submodular maximization · Non-stationary scenario | robustness | Helped |
Surprising findings
- On MovieLens, TabularGreedy outperforms RAOCO, and the Random policy also performs well, suggesting the static offline optimum is poor for that reward sequence.
Limitations
- Framework does not directly apply to general submodular functions; requires concave relaxations.
- Bandit reduction restricted to partition matroids and to general submodular functions with a perturbation approach.
- FSF* applies only to uniform matroids, limiting comparisons.
Experimental setup
Datasets: ZKC Epinions MovieLens SynthTF SynthWC
Benchmarks: ZKC Epinions MovieLens SynthTF
Metrics: average cumulative reward normalized by fractional optimum alpha-regret running time
Baselines: FSF* TabularGreedy Random
Builds on: online mirror ascent follow the regularized leader swap rounding fixed share forecaster tabular greedy
Closest papers by meaning
- Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization over Down-Closed Convex Sets (ICML 2026 · similarity 0.94)
- Improved Algorithms for Online Submodular Maximization via First-order Regret Bounds (NeurIPS 2020 · similarity 0.94)
- Online Two-Stage Submodular Maximization (NeurIPS 2025 · similarity 0.93)
- Gradient Methods for Online DR-Submodular Maximization with Stochastic Long-Term Constraints (NeurIPS 2024 · similarity 0.92)
- From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization (NeurIPS 2024 · similarity 0.91)
- Nearly Minimax Optimal Submodular Maximization with Bandit Feedback (NeurIPS 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.