Research map / Bandits and online learning / Online convex optimization and games
Gradient Methods for Online DR-Submodular Maximization with Stochastic Long-Term Constraints
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.
Proposes primal-dual stochastic gradient ascent algorithms (OLSGA) for online stochastic monotone DR-submodular maximization under stochastic long-term linear budget constraints, with semi-bandit and first-order full-information variants achieving 1/2- and (1-1/e)-regret of O(sqrt T) and O(T^3/4) constraint violation.
Problem
Online monotone DR-submodular maximization where rewards and linear stochastic budget costs arrive i.i.d. each round, with long-term budget constraints satisfied only on average and limited gradient feedback (semi-bandit or full-information).
Approach
A regularized Lagrangian primal-dual gradient ascent using one stochastic gradient query per round, with an empirical cost estimate, handles general convex sets not containing the origin; the non-oblivious function (Zhang et al.) lifts the full-information variant to (1-1/e) approximation.
Key results
- Semi-bandit primal-dual algorithm (OLSGA) achieves 1/2-regret O(sqrt T) with O(T^3/4) constraint violation w.h.p., using one gradient query per round.
- First-order full-information variant achieves (1-1/e)-regret O(sqrt T) with O(T^3/4) constraint violation w.h.p.
- Prior works required sqrt(T) gradient queries per round; the proposed methods require 1.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use semi-bandit feedback with OLSGA instead of prior full-information methods | Online DR-submodular maximization with stochastic long-term constraints · Stochastic long-term constraints | gradient evaluations per round: √T -> 1 | Helped |
| Use first-order full-information OLSGA | Online DR-submodular maximization with stochastic long-term constraints · Stochastic long-term constraints | approximation ratio: 1/2 -> 1 − 1/e | Helped |
| Use first-order full-information OLSGA instead of prior full-information methods | Online DR-submodular maximization with stochastic long-term constraints · Stochastic long-term constraints | gradient evaluations per round: √T -> 1 | Helped |
Limitations
- Constraint violation bound is O(T^3/4) rather than O(sqrt T) as achieved by some prior works in expectation.
- Assumes linear stochastic constraints and i.i.d. sampled functions with DR-submodularity only in expectation.
- Results are purely theoretical with no experiments reported.
Experimental setup
Metrics: alpha-regret total constraint violation
Baselines: Raut et al. (2021) Sadeghi et al. (2023) Feng et al. Chen et al. Frank-Wolfe with stochastic gradients Zhang et al. 2019 (O(T^4/5) one-query)
Builds on: Online gradient ascent for DR-submodular (Chen et al. 2018) Non-oblivious function (Zhang et al. 2022) Raut et al. stochastic long-term constraints Online convex optimization with long-term constraints (Yu et al.)
Closest papers by meaning
- Online DR-Submodular Maximization: Minimizing Regret and Constraint Violation (AAAI 2021 · similarity 0.95)
- Online Submodular Maximization via Online Convex Optimization (AAAI 2024 · similarity 0.92)
- Online Two-Stage Submodular Maximization (NeurIPS 2025 · similarity 0.91)
- 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.90)
- Online and Streaming Algorithms for Constrained k-Submodular Maximization (AAAI 2025 · 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.