Online Continuous DR-Submodular Maximization with Long-Term Budget Constraints

Abstract

In this paper, we study a class of online optimization problems with long-term budget constraints where the objective functions are not necessarily concave (nor convex) but they instead satisfy the Diminishing Returns (DR) property. Specifically, a sequence of monotone DR-submodular objective functions $\{f_t(x){\}}_{t=1}^T$ and monotone linear budget functions $\{⟨p_t,x⟩{\}}_{t=1}^T$ arrive over time and assuming a total targeted budget $B_T$, the goal is to choose points $x_t$ at each time $t\in \{1,\dots ,T\}$, without knowing $f_t$ and $p_t$ on that step, to achieve sub-linear regret bound while the total budget violation ${\sum }_{t=1}^T⟨p_t,x_t⟩-B_T$ is sub-linear as well. Prior work has shown that achieving sub-linear regret is impossible if the budget functions are chosen adversarially. Therefore, we modify the notion of regret by comparing the agent against a $(1-\frac{1}{e})$-approximation to the best fixed decision in hindsight which satisfies the budget constraint proportionally over any window of length $W$. We propose the Online Saddle Point Hybrid Gradient (OSPHG) algorithm to solve this class of online problems. For $W=T$, we recover the aforementioned impossibility result. However, when $W=o(T)$, we show that it is possible to obtain sub-linear bounds for both the $(1-\frac{1}{e})$-regret and the total budget violation.

Submitted to NeurIPS 2019

References in corpus (10)

• An Online Convex Optimization Approach to Dynamic Network Resource Allocation
• Trading Regret for Efficiency: Online Convex Optimization with Long Term Constraints
• Online convex optimization for cumulative constraints
• Online Convex Optimization with Time-Varying Constraints
• Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains
• Online Continuous Submodular Maximization
• Online Submodular Maximization under a Matroid Constraint with Application to Learning Assignments
• Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularity
• Optimal DR-Submodular Maximization and Applications to Provable Mean Field Inference
• Competitive Online Algorithms for Resource Allocation over the Positive Semidefinite Cone

Cited by in corpus (1)

• Distributed Online Convex Optimization with Time-Varying Coupled Inequality Constraints