pith. sign in

arxiv: 1907.00316 · v1 · pith:C55RTVVSnew · submitted 2019-06-30 · 🧮 math.OC · cs.LG· stat.ML

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

Omid Sadeghi , Maryam Fazel This is my paper

Pith reviewed 2026-05-25 13:02 UTC · model grok-4.3

classification 🧮 math.OC cs.LGstat.ML
keywords online optimizationDR-submodular maximizationlong-term budget constraintsregret boundssaddle point methodscontinuous submodular functionsonline algorithms
0
0 comments X

The pith

A modified regret definition comparing to a (1-1/e) windowed benchmark enables sublinear (1-1/e)-regret and sublinear budget violation for online DR-submodular maximization when W=o(T).

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that online continuous maximization of monotone DR-submodular functions subject to long-term linear budget constraints can achieve both sublinear (1-1/e)-regret and sublinear total budget violation. This is done by comparing performance to a (1-1/e)-approximate best fixed decision in hindsight that satisfies the budget constraint proportionally over every window of length W. The OSPHG algorithm is proposed to attain these bounds whenever W is little-o of the total time horizon T. Prior results showed impossibility under standard regret with adversarial budgets, so the modification enables positive results for sublinear W.

Core claim

The OSPHG algorithm achieves sub-linear bounds on both the (1-1/e)-regret and the total budget violation for sequences of monotone DR-submodular objectives and monotone linear budgets, when the benchmark window length W satisfies W = o(T). For W = T the impossibility of sublinear regret is recovered.

What carries the argument

The Online Saddle Point Hybrid Gradient (OSPHG) algorithm, which performs hybrid gradient updates to maximize the DR-submodular objective while enforcing the cumulative linear budget constraint.

If this is right

  • Both (1-1/e)-regret and budget violation remain sublinear in T whenever W=o(T).
  • The standard (1-1/e) approximation guarantee from offline submodular maximization is preserved in the online setting.
  • Decisions at each step can be made without knowledge of the current or future objective and budget functions.
  • When W=T the construction recovers the known impossibility of sublinear regret under adversarial budgets.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The window parameter W provides a tunable tradeoff between constraint strictness and achievable regret rate.
  • Similar windowed benchmark relaxations could be applied to other online problems with cumulative resource constraints.
  • The approach suggests that short-term proportional satisfaction of budgets suffices for long-horizon sublinear performance.

Load-bearing premise

The budget functions are monotone linear and the comparison benchmark is restricted to decisions that satisfy the budget constraint proportionally over any window of length W.

What would settle it

An explicit sequence of DR-submodular functions and linear budgets with W=o(T) on which OSPHG produces linear (1-1/e)-regret or linear total budget violation would falsify the sublinear bounds.

Figures

Figures reproduced from arXiv: 1907.00316 by Maryam Fazel, Omid Sadeghi.

Figure 1
Figure 1. Figure 1: (a) Budget violation running average Pt τ=1 gτ (xτ ) t of OSPHG algorithm for W = √ T (b) Utility performance running average Pt τ=1 fτ (xτ ) t of OSPHG algorithm for W = √ T vs. utility of the benchmark (c) Utility of the benchmark for different window lengths 1 ≤ W ≤ T Plugging in µ = R β √ W T = O( √ 1 W T ) and K = O( q T W )in the above inequality and multiplying both sides by 2δµT + 4 µ , the dominat… view at source ↗
read the original 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 $\{\langle p_t,x \rangle \}_{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 \langle p_t,x_t \rangle -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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper studies online maximization of a sequence of monotone DR-submodular objective functions subject to monotone linear budget constraints with total budget B_T. It defines a modified benchmark consisting of a (1-1/e)-approximation to the best fixed decision that satisfies the budget constraint proportionally over every window of length W, and proposes the OSPHG algorithm. The central claim is that OSPHG achieves sub-linear (1-1/e)-regret and sub-linear total budget violation when W=o(T); the known impossibility result is recovered when W=T.

Significance. If the stated bounds hold, the work is significant because it provides the first sub-linear guarantees for continuous DR-submodular maximization under long-term linear constraints by relaxing the benchmark to a window-proportional feasibility condition. This directly addresses the impossibility for fully adversarial budgets while remaining consistent with the standard (1-1/e) approximation for DR-submodular functions. The approach is relevant to online resource allocation problems where strict per-step adversarial constraints are overly restrictive.

major comments (2)
  1. [Abstract / regret definition] Abstract and regret definition section: the claim that sub-linear (1-1/e)-regret is obtained relies on the precise definition of the benchmark (a (1-1/e)-approximation to the best fixed decision satisfying proportional budget satisfaction over windows of length W); without an explicit equation for this benchmark and the resulting regret expression, it is impossible to verify that the OSPHG analysis yields a sub-linear quantity rather than a constant-factor loss.
  2. [OSPHG analysis] Analysis of OSPHG (presumably §4 or §5): the manuscript states sub-linear bounds for both regret and budget violation when W=o(T) but provides no proof sketch, assumption list, or dependence on W/T in the abstract or high-level description; the central claim cannot be assessed without the explicit regret and violation bounds (e.g., O(·) expressions) and the error analysis that shows they remain sub-linear.
minor comments (2)
  1. The abstract refers to 'the section on regret definition' but the main text should ensure all notation (including the window-proportional constraint) is defined before the algorithm is presented.
  2. It would strengthen the paper to include a short table or paragraph contrasting the new benchmark with the standard offline (1-1/e) guarantee and with the fully adversarial case (W=T).

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and constructive comments on our work. We address each major comment below and will incorporate clarifications into the revised manuscript.

read point-by-point responses

  1. Referee: [Abstract / regret definition] Abstract and regret definition section: the claim that sub-linear (1-1/e)-regret is obtained relies on the precise definition of the benchmark (a (1-1/e)-approximation to the best fixed decision satisfying proportional budget satisfaction over windows of length W); without an explicit equation for this benchmark and the resulting regret expression, it is impossible to verify that the OSPHG analysis yields a sub-linear quantity rather than a constant-factor loss.

    Authors: We agree that the abstract and regret definition section would be strengthened by including the explicit mathematical definition of the benchmark and the resulting regret expression. The benchmark is defined in the manuscript as the (1-1/e)-approximation to the best fixed decision satisfying the proportional budget constraint over every window of length W, and the regret is the difference from the algorithm's cumulative reward to this benchmark value. We will add the explicit equations to the abstract and the relevant section in the revision. revision: yes

  2. Referee: [OSPHG analysis] Analysis of OSPHG (presumably §4 or §5): the manuscript states sub-linear bounds for both regret and budget violation when W=o(T) but provides no proof sketch, assumption list, or dependence on W/T in the abstract or high-level description; the central claim cannot be assessed without the explicit regret and violation bounds (e.g., O(·) expressions) and the error analysis that shows they remain sub-linear.

    Authors: The manuscript provides the explicit sub-linear bounds on both (1-1/e)-regret and budget violation (with dependence on W/T) in the analysis section, along with the supporting error analysis that establishes sub-linearity when W=o(T). We agree that a brief proof sketch, list of key assumptions, and the O(·) expressions would improve the abstract and high-level description. We will add these elements in the revision. revision: yes

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper explicitly modifies the regret benchmark to a (1-1/e)-approximation of the best fixed decision satisfying linear budgets proportionally over windows of length W, precisely to sidestep the known impossibility for W=T (adversarial case). The OSPHG algorithm and sub-linear bounds for W=o(T) are derived via standard saddle-point and gradient methods applied to this redefined problem under the stated monotone DR-submodular and linear budget assumptions. No equation or claim reduces by construction to a fitted parameter, self-definition, or load-bearing self-citation; the central results are independent analyses of the modified benchmark and are self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no explicit free parameters, axioms, or invented entities are stated.

pith-pipeline@v0.9.0 · 5824 in / 1030 out tokens · 36914 ms · 2026-05-25T13:02:25.009554+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages · 6 internal anchors

  1. [1]

    Trading regret for efficiency: online convex optimization with long term constraints

    Mehrdad Mahdavi, Rong Jin, and Tianbao Yang. Trading regret for efficiency: online convex optimization with long term constraints. Journal of Machine Learning Research, 13(Sep):2503– 2528, 2012

    work page 2012

  2. [2]

    Adaptive algorithms for online convex optimization with long-term constraints

    Rodolphe Jenatton, Jim Huang, and Cedric Archambeau. Adaptive algorithms for online convex optimization with long-term constraints. In Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 402–411, New York, New York, USA, 2...

    work page 2016

  3. [3]

    Online convex optimization for cumulative constraints

    Jianjun Yuan and Andrew Lamperski. Online convex optimization for cumulative constraints. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 6137–6146. Curran Associates, Inc., 2018

    work page 2018

  4. [4]

    Online learning with sample path constraints

    Shie Mannor, John N Tsitsiklis, and Jia Yuan Yu. Online learning with sample path constraints. Journal of Machine Learning Research, 10(Mar):569–590, 2009

    work page 2009

  5. [5]

    Online Convex Optimization with Time-Varying Constraints

    Michael J Neely and Hao Yu. Online convex optimization with time-varying constraints. arXiv preprint arXiv:1702.04783, 2017

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  6. [6]

    Safety-aware algorithms for adversarial contextual bandit

    Wen Sun, Debadeepta Dey, and Ashish Kapoor. Safety-aware algorithms for adversarial contextual bandit. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 3280–3288. JMLR. org, 2017

    work page 2017

  7. [7]

    Cautious regret minimization: Online optimization with long-term budget constraints

    Nikolaos Liakopoulos, Apostolos Destounis, Georgios Paschos, Thrasyvoulos Spyropoulos, and Panayotis Mertikopoulos. Cautious regret minimization: Online optimization with long-term budget constraints. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of M...

    work page 2019

  8. [8]

    An online convex optimization approach to proactive network resource allocation

    Tianyi Chen, Qing Ling, and Georgios B Giannakis. An online convex optimization approach to proactive network resource allocation. IEEE Transactions on Signal Processing, 65(24):6350– 6364, 2017

    work page 2017

  9. [9]

    Online convex optimization with time-varying constraints and bandit feedback

    Xuanyu Cao and KJ Ray Liu. Online convex optimization with time-varying constraints and bandit feedback. IEEE Transactions on Automatic Control, 2018

    work page 2018

  10. [10]

    Online Continuous Submodular Maximization

    Lin Chen, Hamed Hassani, and Amin Karbasi. Online continuous submodular maximization. arXiv preprint arXiv:1802.06052, 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  11. [11]

    Online Submodular Maximization under a Matroid Constraint with Application to Learning Assignments

    Daniel Golovin, Andreas Krause, and Matthew Streeter. Online submodular maximization under a matroid constraint with application to learning assignments. arXiv preprint arXiv:1407.1082, 2014

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  12. [12]

    Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularity

    Lin Chen, Christopher Harshaw, Hamed Hassani, and Amin Karbasi. Projection-free on- line optimization with stochastic gradient: From convexity to submodularity. arXiv preprint arXiv:1802.08183, 2018. 14

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  13. [13]

    Submodular function maximization., 2014

    Andreas Krause and Daniel Golovin. Submodular function maximization., 2014

    work page 2014

  14. [14]

    Optimal approximation for the submodular welfare problem in the value oracle model

    Jan V ondrák. Optimal approximation for the submodular welfare problem in the value oracle model. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 67–74. ACM, 2008

    work page 2008

  15. [15]

    Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains

    Andrew An Bian, Baharan Mirzasoleiman, Joachim M Buhmann, and Andreas Krause. Guar- anteed non-convex optimization: Submodular maximization over continuous domains. arXiv preprint arXiv:1606.05615, 2016

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  16. [16]

    Designing smoothing functions for improved worst-case competitive ratio in online optimization

    Reza Eghbali and Maryam Fazel. Designing smoothing functions for improved worst-case competitive ratio in online optimization. In D. D. Lee, M. Sugiyama, U. V . Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems 29, pages 3287–

    work page

  17. [17]

    Curran Associates, Inc., 2016

    work page 2016

  18. [18]

    Competitive online algorithms for resource allocation over the positive semidefinite cone

    Reza Eghbali, James Saunderson, and Maryam Fazel. Competitive online algorithms for resource allocation over the positive semidefinite cone. Mathematical Programming, pages 1–26, 2018

    work page 2018

  19. [19]

    Maximizing a submodular set function subject to a matroid constraint

    Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan V ondrák. Maximizing a submodular set function subject to a matroid constraint. In International Conference on Integer Programming and Combinatorial Optimization, pages 182–196. Springer, 2007

    work page 2007

  20. [20]

    Monotone closure of relaxed constraints in sub- modular optimization: Connections between minimization and maximization

    Rishabh Iyer, Stefanie Jegelka, and Jeff Bilmes. Monotone closure of relaxed constraints in sub- modular optimization: Connections between minimization and maximization. In Proceedings of the Thirtieth Conference on Uncertainty in Artificial Intelligence, UAI’14, pages 360–369, Arlington, Virginia, United States, 2914. AUAI Press

    work page

  21. [21]

    Optimal DR-Submodular Maximization and Applications to Provable Mean Field Inference

    An Bian, Joachim M Buhmann, and Andreas Krause. Optimal dr-submodular maximization and applications to provable mean field inference.arXiv preprint arXiv:1805.07482, 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  22. [22]

    Continuous dr-submodular maximization: Structure and algorithms

    An Bian, Kfir Levy, Andreas Krause, and Joachim M Buhmann. Continuous dr-submodular maximization: Structure and algorithms. In Advances in Neural Information Processing Systems, pages 486–496, 2017

    work page 2017

  23. [23]

    Numerical optimization

    Jorge Nocedal and Stephen Wright. Numerical optimization. Springer Science & Business Media, 2006

    work page 2006

  24. [24]

    Introduction to online convex optimization

    Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends R⃝ in Optimization, 2(3-4):157–325, 2016. 15

    work page 2016