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

Omid Sadeghi, Maryam Fazel
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:4410-4419, 2020.

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. In this online setting, a sequence of monotone DR-submodular objective functions and linear budget functions arrive over time and assuming a limited total budget, the goal is to take actions at each time, before observing the utility and budget function arriving at that round, to achieve sub-linear regret bound while the total budget violation is sub-linear as well. Prior work has shown that achieving sub-linear regret and total budget violation simultaneously is impossible if the utility and budget functions are chosen adversarially. Therefore, we modify the notion of regret by comparing the agent against 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, if $W$ is sub-linear in $T$, we show that it is possible to obtain sub-linear bounds for both the regret and the total budget violation.

Cite this Paper

BibTeX
@InProceedings{pmlr-v108-sadeghi20a, title = {Online Continuous DR-Submodular Maximization with Long-Term Budget Constraints}, author = {Sadeghi, Omid and Fazel, Maryam}, booktitle = {Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics}, pages = {4410--4419}, year = {2020}, editor = {Chiappa, Silvia and Calandra, Roberto}, volume = {108}, series = {Proceedings of Machine Learning Research}, month = {26--28 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v108/sadeghi20a/sadeghi20a.pdf}, url = {https://proceedings.mlr.press/v108/sadeghi20a.html}, 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. In this online setting, a sequence of monotone DR-submodular objective functions and linear budget functions arrive over time and assuming a limited total budget, the goal is to take actions at each time, before observing the utility and budget function arriving at that round, to achieve sub-linear regret bound while the total budget violation is sub-linear as well. Prior work has shown that achieving sub-linear regret and total budget violation simultaneously is impossible if the utility and budget functions are chosen adversarially. Therefore, we modify the notion of regret by comparing the agent against 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, if $W$ is sub-linear in $T$, we show that it is possible to obtain sub-linear bounds for both the regret and the total budget violation.} }
Endnote
%0 Conference Paper %T Online Continuous DR-Submodular Maximization with Long-Term Budget Constraints %A Omid Sadeghi %A Maryam Fazel %B Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2020 %E Silvia Chiappa %E Roberto Calandra %F pmlr-v108-sadeghi20a %I PMLR %P 4410--4419 %U https://proceedings.mlr.press/v108/sadeghi20a.html %V 108 %X 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. In this online setting, a sequence of monotone DR-submodular objective functions and linear budget functions arrive over time and assuming a limited total budget, the goal is to take actions at each time, before observing the utility and budget function arriving at that round, to achieve sub-linear regret bound while the total budget violation is sub-linear as well. Prior work has shown that achieving sub-linear regret and total budget violation simultaneously is impossible if the utility and budget functions are chosen adversarially. Therefore, we modify the notion of regret by comparing the agent against 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, if $W$ is sub-linear in $T$, we show that it is possible to obtain sub-linear bounds for both the regret and the total budget violation.
APA
Sadeghi, O. & Fazel, M.. (2020). Online Continuous DR-Submodular Maximization with Long-Term Budget Constraints. Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 108:4410-4419 Available from https://proceedings.mlr.press/v108/sadeghi20a.html.

Related Material