Online Continuous DR-Submodular Maximization with Long-Term Budget Constraints
share
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∈{1,...,T}, without knowing f_t and p_t on that step, to achieve sub-linear regret bound while the total budget violation ∑_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-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-1/e)-regret and the total budget violation.
READ FULL TEXT