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

arXiv: https://arxiv.org/abs/1907.00316 · HTML: https://mlsanity.com/paper/1907.00316/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jun 2019.

## Built on by (most cited first, 9 of 9)

- [Submodularity In Machine Learning and Artificial Intelligence](https://mlsanity.com/paper/2202.00132/) (2022)
- [Regret and Cumulative Constraint Violation Analysis for Distributed Online Constrained Convex Optimization](https://mlsanity.com/paper/2105.00321/) (2021)
- [Distributed Online Convex Optimization with Adversarial Constraints: Reduced Cumulative Constraint Violation Bounds under Slater's Condition](https://mlsanity.com/paper/2306.00149/) (2023)
- [Submodular + Concave](https://mlsanity.com/paper/2106.04769/) (2021)
- [CATRO: Channel Pruning via Class-Aware Trace Ratio Optimization](https://mlsanity.com/paper/2110.10921/) (2021)
- [Minimax Optimization: The Case of Convex-Submodular](https://mlsanity.com/paper/2111.01262/) (2021)
- [Improved Regret Bounds for Online Submodular Maximization](https://mlsanity.com/paper/2106.07836/) (2021)
- [Projection-Free Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/2305.01333/) (2023)
- [Online SuBmodular + SuPermodular (BP) Maximization with Bandit Feedback](https://mlsanity.com/paper/2207.03091/) (2022)

## Abstract (arXiv)

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 ft(x)t=1T and monotone linear budget functions langle pt,x rangle t=1T arrive over time and assuming a total targeted budget BT, the goal is to choose points xt at each time t∈1,dots,T, without knowing ft and pt on that step, to achieve sub-linear regret bound while the total budget violation sumt=1T langle pt,xt rangle -BT 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-frac1e)-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-frac1e)-regret and the total budget violation.