Online DR-Submodular Maximization with Stochastic Cumulative Constraints

Abstract

In this paper, we consider online continuous DR-submodular maximization with linear stochastic long-term constraints. Compared to the prior work on online submodular maximization, our setting introduces the extra complication of stochastic linear constraint functions that are i.i.d. generated at each round. To be precise, at step $t\in \{1,\dots ,T\}$, a DR-submodular utility function $f_t(\cdot )$ and a constraint vector $p_t$, i.i.d. generated from an unknown distribution with mean $p$, are revealed after committing to an action $x_t$ and we aim to maximize the overall utility while the expected cumulative resource consumption ${\sum }_{t=1}^T⟨p,x_t⟩$ is below a fixed budget $B_T$. Stochastic long-term constraints arise naturally in applications where there is a limited budget or resource available and resource consumption at each step is governed by stochastically time-varying environments. We propose the Online Lagrangian Frank-Wolfe (OLFW) algorithm to solve this class of online problems. We analyze the performance of the OLFW algorithm and we obtain sub-linear regret bounds as well as sub-linear cumulative constraint violation bounds, both in expectation and with high probability.

To appear in proceedings of AAAI 2021

References in corpus (8)

• Online Learning: A Modern Introduction Using Convex Optimization
• Online convex optimization for cumulative constraints
• Online Convex Optimization with Time-Varying Constraints
• A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm
• Online Continuous Submodular Maximization
• The Online Saddle Point Problem and Online Convex Optimization with Knapsacks
• Efficient Constrained Regret Minimization
• Online optimization and regret guarantees for non-additive long-term constraints

Cited by in corpus (1)

• Submodular + Concave