acceptodds
Under review as a conference paper at ICLR 2027

Online Non-Monotone DR-Submodular Maximization Beyond

Abstract

We give a -approximate algorithm for adversarial online maximization of nonnegative, non-monotone DR-submodular functions over compact convex down-closed sets. To our knowledge, this is the first polynomial-oracle online guarantee strictly above for this problem class. Each action is committed before current-function feedback. The algorithm maintains one feasible state, uses one feasible gradient query and one Euclidean projection per round, and achieves expected approximate regret for diameter and gradient bound . The main result is a first-order inequality that holds simultaneously for every comparator. A strengthened delayed-trajectory comparison and an endpoint-retaining coordinate-chain comparison have complementary nonlinear residuals. A common-state substitution aligns their linear terms, and a fixed mixture of two feasible actions cancels the nonlinear terms exactly. This replaces objective-dependent offline auxiliary optimization with one online linear update. Continuous differentiability suffices; no positive anchor or interior-point condition is required. We prove extensions to non-anticipating adaptive adversaries and stochastic gradients. For every absolute tolerance , the offline specialization attains expected coefficient up to additive error using feasible gradient queries and projections.

Primary area:
optimization
Keywords:
Non-monotone DR-submodular Maximization, Online Optimization, Down-closed

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_x1ebOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies adversarial online non-monotone DR-submodular maximization over compact convex down-closed sets. The authors establish a comparator-uniform first-order inequality by combining a strengthened delayed-trajectory comparison with an endpoint-retaining coordinate-chain inequality. Based on this result, they propose an algorithm achieving an approximation coefficient above 0.4013 with O(T)O(\sqrt{T}) expected approximate regret, using one feasible gradient query and one projection per round.

The paper addresses an interesting theoretical problem and presents a nontrivial structural construction with favorable oracle complexity. However, its novelty and significance relative to closely related work are not sufficiently established, and the central technical challenges and contributions are not clearly explained.

Critical strengths

The paper establishes a 0.4013 approximation coefficient with O(T)O(\sqrt{T}) expected approximate regret. The algorithm requires only one feasible gradient query and one projection per round, without assuming Lipschitz-continuous gradients or an interior point of the feasible set. The analysis also covers stochastic gradients and non-anticipating adaptive adversaries.

Critical weaknesses
  1. The proposed approach relies heavily on existing delayed-trajectory, coordinate-chain, and online optimization techniques. Although their combination is technically nontrivial, the manuscript does not sufficiently explain which mathematical ingredients are genuinely new or why the more elaborate comparison and cancellation mechanism is necessary. The presentation emphasizes technical constructions without clearly identifying the specific limitations of existing methods that they overcome.

  2. The manuscript is closely related to two recent preprints, arXiv:2609.02145 and arXiv:2610.00545. The former already establishes an online approximation coefficient above (1/e) using a weighted online-learning approach, although under a different feedback model and regret–query tradeoff. More importantly, Lemma 3.1 of arXiv:2610.00545, specialized to (c=1), gives the same endpoint-retaining coordinate-chain inequality as Lemma 3.2 of the present manuscript. Moreover, arXiv:2610.00545 obtains a stronger (4/9) online approximation coefficient without the delayed-trajectory cancellation construction.genuinely new. A clearer comparison with the underlying offline techniques would help establish the actual technical contribution.

Questions for authors
  1. How does the proposed method differ from arXiv:2609.02145, and what are its precise advantages in terms of approximation ratio, regret, and oracle complexity?

  2. Which ingredients of Propositions 3.1 and 3.3 are genuinely new relative to existing offline techniques, and why are these modifications necessary for Theorem 3.4?

  3. Given that arXiv:2610.00545 achieves a stronger 4/94/9 approximation through a direct first-order comparison, is the delayed-trajectory and cancellation mechanism essential for restricting gradient queries to the feasible set?

6 comments
AuthorsOpenReview ↗

Response to Reviewer x1eb's Q1 and Q2

Thank you for recognizing the structural construction, feasible-query complexity, and extensions. Below we address Q1–Q3, followed by a summary of the revision.

Both preprints raised in the review appeared very close to the submission deadline: 2609.02145 on September 2, and 2610.00545 on September 30, after the deadline. ICLR's reviewer guidance does not require comparison with work that appeared within two months of the submission deadline, and states that the lack of such comparisons cannot be a basis for rejection. We provide the comparisons below because you asked for them, while noting that the guidelines do not require them.

Q1. Comparison with arXiv:2609.02145

The main distinction is where the oracle can be queried. Among online algorithms that use one gradient query per round, ours is, to our knowledge, the only one above 1/e1/e whose queries all lie in KK. The guarantees of 2609.02145, Sections 3–4 use function-value queries at points of [0,1]d[0,1]^d that may lie outside the feasible set KK. Our algorithm queries one full gradient at zt∈[0,xt]⊆Kz_t\in[0,x_t]\subseteq K after committing to its action, so every query, as well as every played action, is feasible. In addition, our coefficient, α∗>0.4013\alpha_*>0.4013, is slightly larger than their 0.4010.401.

Structurally, the preprint controls the nonlinear residuals cumulatively through a weighted auxiliary online learner. Our comparison cancels them pointwise at a common state, leaving one field that a single online linear learner can control. Q2 explains the ingredients enabling this cancellation.

Q2. New ingredients in Propositions 3.1 and 3.3 and their role in Theorem 3.4

The contribution is the complete comparator-uniform feasible-query comparison in Theorem 3.4. Its additional structural ingredients are:

  • Proposition 3.1: retaining the mixed trajectory contribution. Building on the attributed exponential expansion, we retain a mixed early/late second-order term and bound it below by three quarters of the union value. This lowers the union coefficient by Δs=3s(1−s)2/(8e)\Delta_s=3s(1-s)^2/(8e). At s=199/500s=199/500, the resulting slack satisfies ℓ−ζs>0.004823\ell-\zeta_s>0.004823; omitting this contribution gives ℓ−(ζs+Δs)<−0.015\ell-(\zeta_s+\Delta_s)<-0.015. Thus the unstrengthened estimate does not justify the coefficient-matching choice at the submitted parameters. We have added this parameter-specific comparison in blue immediately after the proof of Proposition 3.1 in Section 3.1.
  • Proposition 3.3: common-state localization to a feasible box. We apply the chain inequality to Jx(a)=f(x⊙(1−a))J_x(a)=f(x\odot(1-a)), with a=1−xa=1-x and b=1−ob=1-o. Every original gradient location then belongs to [0,x]⊆K[0,x]\subseteq K, while the linear residual is aligned with o−xo-x. This localized comparison controls f(x⊙o)+f(x)f(x\odot o)+f(x), leaving the original comparator value f(o)f(o) unresolved.
  • Theorem 3.4: matching and cancelling both residuals. The trajectory comparison supplies f(o)f(o). Choosing ℓ=μs/3\ell=\mu_s/3 equalizes its two nonlinear residual coefficients, and a fixed mixture of the prescribed feasible actions cancels both residual values. Retaining the box endpoint Jx(0)=f(x)J_x(0)=f(x) is necessary for this particular cancellation. The result holds at every feasible state and simultaneously for every comparator, with one comparator-independent field estimable from a single feasible gradient query.

An offline guarantee at an objective-dependent auxiliary solution does not supply this inequality at a state selected from past online feedback. The common-state construction and coefficient matching provide that missing comparison.

AuthorsOpenReview ↗

Response to Reviewer x1eb's Q3 and summary of related revisions

Q3. Relationship to the direct 4/9 comparison and the feasible-query restriction

As noted above, 2610.00545 appeared after the submission deadline.

In addition, the preprint does not restrict its queries to the feasible region: the direct 4/94/9 method permits queries on the ambient cube, whereas our algorithm restricts every gradient query to KK. To our knowledge, among online algorithms that use one gradient query per round, ours is the only one above 1/e1/e with every query in KK.

For example, the direct method plays the action x/(c+x)x/(c+x), and c=1c=1 gives its coefficient 4/94/9 for general down-closed sets. Take K={z∈[0,1]2:z1+z2≤1}K=\{z\in[0,1]^2:z_1+z_2\le1\} and x=(1/2,1/2)x=(1/2,1/2). The direct method's action (1/3,1/3)(1/3,1/3) is feasible, but its first upper-chain query segment (1−2v/3,1)(1-2v/3,1), v∈[0,1]v\in[0,1], lies entirely outside KK. This segment is sampled with positive probability. Thus action feasibility alone does not establish query feasibility.

The direct sampler therefore does not implement the 4/94/9 comparison under the restricted oracle. Our localization and cancellation resolve this obstruction through the steps in Q2. The quantitative gradient bound is needed only on KK, although nonnegativity and DR-submodularity remain assumptions on the ambient cube. This establishes the role of the delayed trajectory within our construction; we do not prove that every feasible-query algorithm must use it or that 4/94/9 is impossible with feasible queries.

Revision

We have made presentation revisions, key ones marked in blue. The abstract now states that, among online algorithms using one gradient query per round, ours is the first to exceed 1/e1/e with every query in the feasible set. This remains true when the recent preprints are included. A new paragraph in Section 1 ("Why feasible queries matter") explains why feasible queries are needed. The “Relation to prior techniques” paragraph in Section 1 now explicitly distinguishes the standard online reduction from our structural contribution: aligning the trajectory and feasible-box comparisons at a common state and matching their nonlinear residual coefficients, with all gradient locations in [0,x]⊆K[0,x]\subseteq K.

Dear Reviewer,

As the discussion period is nearing its end, we would appreciate hearing if you have any remaining questions or concerns regarding our response. We would be happy to provide further clarification.

Thank you for your time and consideration.

Reviewer_NjXhOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies adversarial online maximization of nonnegative, non-monotone DR-submodular functions over down-closed convex sets. The authors propose a 0.40130.4013-approximation algorithm with O(DBdT)O(DB\sqrt{dT}) expected approximate regret.

Critical strengths

The paper provides detailed theoretical analyses and proofs of the proposed algorithm and its approximation guarantees.

Critical weaknesses
  • Limited theoretical and algorithmic novelty. The underlying first-order comparison framework has already been established in prior work. In particular, the proposed approach follows the upper-linearizability framework introduced by Pedramfar and Aggarwal (2024) and subsequently applied to online non-monotone DR-submodular maximization by Lu et al. (2026). The main contribution of this paper appears to be a refinement and combination of existing offline approximation techniques within an established theoretical framework, rather than a fundamentally new algorithmic approach. The authors should more clearly distinguish their technical contributions from these prior results.

    • References:

      • Pedramfar, M., and Aggarwal, V. (2024). From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-Stationary DR-Submodular Optimization. NeurIPS, 37, 37626–37664.

      • Lu, Y., Jadav, H., Pedramfar, M., et al. (2026). Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization over Down-Closed Convex Sets. arXiv preprint arXiv:2602.20578.

  • Lack of numerical experiments. The manuscript is entirely theoretical and provides no numerical experiments to evaluate the proposed algorithm. Although theoretical guarantees are valuable, empirical evaluations are also important for assessing the practical relevance of the proposed method, particularly for the ICLR audience. Numerical comparisons with existing algorithms would help demonstrate whether the improved approximation coefficient translates into better practical performance.

Questions for authors
  • Please clarify the main theoretical and algorithmic novelty of this work compared with the existing upper-linearizability framework and related offline approximation techniques.

  • Please provide numerical comparisons with existing algorithms to demonstrate the practical benefits of improving the approximation coefficient from 1/e1/e to 0.40130.4013, particularly considering the additional dimension-dependent factor in the regret bound.

8 comments
AuthorsOpenReview ↗

Response to Reviewer NjXh's Q1 (W1)

Thank you for recognizing the detailed theoretical analysis and for asking us to clarify both the contribution and its practical implications.

Q1. Theoretical and algorithmic novelty relative to upper-linearizability and offline techniques

(a) Comparison with the upper-linearizability framework.

What is already established. Pedramfar and Aggarwal (2024), Theorem 1 establish a paradigm that transfers a structural upper-linearizable comparison, together with an oracle for its field, to an online regret guarantee. The transfer preserves the approximation coefficient supplied by that comparison. Lu et al. (2026), Theorem 1 and Lemma 2 show that this paradigm applies to non-monotone DR-submodular functions over down-closed sets when the structural comparison, the field estimator GG and the action map hh are designed suitably. They provide the relevant 1/e1/e comparison for down-closed sets, using the action 1−e−x1-e^{-x} and a single gradient query at 1−e−vx∈[0,x]⊆K1-e^{-vx}\in[0,x]\subseteq K. Thus the reduction and a feasible single-query implementation exist at coefficient 1/e1/e. The open question was whether a larger coefficient is possible while keeping every query feasible.

What our result adds. Applying the reduction to the comparison of Lu et al. gives coefficient 1/e1/e online, below the offline coefficient 0.4010.401 Buchbinder and Feldman (2024). Our Theorem 3.4 supplies a different action distribution and field satisfying

\qquad \alpha_*>0.4013,$$ at every prescribed $x\in K$, simultaneously for all $o\in K$, with every gradient location in $[0,x]\subseteq K$. The reduction is the same; the new parts are the structural comparison, the coupled design of the field $G$ and action map $h$, and the one-query estimator $\hat G$. To our knowledge, among online algorithms that use one gradient query per round, this is the first to exceed $1/e$ with every query in $K$. **(b) Comparison with the offline techniques.** **What is already established.** [Buchbinder and Feldman (2024)](https://arxiv.org/html/2311.01129) combine a guided trajectory with box maximization in Algorithm 1. Their Lemmas 4.1–4.2 provide the exponential expansion, and their box guarantee in Corollary 2.6 already retains both $f(x\odot o)$ and $f(x)$. Neither combining trajectory and box arguments nor retaining endpoint values alone is our novelty. However, their final guarantee relies on approximate local optimization and objective-dependent auxiliary solutions for the current function. **What changes in our comparison.** There are two specific differences: - **From an objective-dependent box solution to a first-order inequality at a prescribed state.** The offline box routine returns a point selected using the current objective. Proposition 3.3 instead uses the explicit action $P(x)=x/(2-x)$ and proves $$f(x\odot o)+f(x)-\tfrac94 f(P(x))\le\langle k(f,x),o-x\rangle.$$ The complement substitution $J_x(a)=f(x\odot(1-a))$, $a=1-x$, $b=1-o$ aligns the residual with the trajectory's direction $o-x$ and maps every gradient query into $[0,x]$. It requires no assumption that $x$ approximately optimizes the current objective: the linear residual is retained for the online learner to control cumulatively. - **From the existing trajectory coefficient to one permitting the prescribed cancellation.** With accuracy terms suppressed, the union coefficient in their Theorem 3.1 is $$\zeta_s^{\mathrm{BF}}=\frac{(2-s)e^s+s-(s^2+5)/2}{e}.$$ Our constant-direction comparison retains and lower-bounds a mixed early/late term from their expansion, giving $\zeta_s=\zeta_s^{\mathrm{BF}}-3s(1-s)^2/(8e)$, together with an explicit first-order residual. At $s=199/500$, this permits the matching choice $\ell=\mu_s/3$: $\ell-\zeta_s>0.004823$, whereas using the unstrengthened coefficient gives $\ell-\zeta_s^{\mathrm{BF}}<-0.015$. We have added this parameter-specific comparison in blue immediately after the proof of Proposition 3.1 in Section 3.1 in the revision draft. These differences make the two comparisons compatible at the same prescribed state: matching the coefficients cancels both nonlinear residuals pointwise through a fixed action mixture, leaving one comparator-independent linear field. This is the comparison needed to obtain the improved online guarantee from the existing framework, without first optimizing the current objective.
AuthorsOpenReview ↗

Response to Reviewer NjXh's Q2 (W2)

Q2. Numerical comparisons and the additional dimension dependence

We appreciate the question about the significance of the improved approximation ratio. Exact maximization of non-monotone DR-submodular functions is NP-hard in general, even under box constraints; see Bian et al. (2019), Section 3. This motivates polynomial-time algorithms that guarantee a fraction of the optimum, quantified by an approximation ratio.

In our online setting, define the best fixed comparator’s expected reward as

OPTT=E[max⁡o∈K∑t=1Tft(o)].\mathrm{OPT}_T=\mathbb E \left[\max_{o\in K}\sum_{t=1}^T f_t(o)\right].

An α\alpha-approximate no-regret guarantee takes the form

\qquad \mathcal R(T)=o(T).$$ Here $\alpha$ specifies the guaranteed fraction of the comparator reward, and $\mathcal R(T)$ is the additive learning cost. Our result improves $\alpha$ from $1/e\approx0.3679$ to $0.4013$, an approximately 9.1% relative increase in this guaranteed fraction. Both methods use one feasible gradient query and one projection per round. The coefficient is a worst-case guarantee: it holds for every admissible adversarial sequence, with no distributional or stationarity assumption on the objectives. On a particular sequence, the actual reward of either algorithm can be much higher than the guaranteed fraction. Experiments on a chosen family of instances therefore cannot confirm or refute an improvement in the worst-case coefficient, so the paper focuses on the proved guarantee: a larger coefficient under the same feasible one-query budget, established by the structural comparison and the regret analysis. We acknowledge the additional $\sqrt d$ dependence in the additive regret term, $O(DB\sqrt{dT})$ versus the baseline’s $O(DB\sqrt T)$, and explicitly disclose this tradeoff in the revised introduction after equation (1), with both bounds recorded in Table 1.

Dear Reviewer,

As the discussion period is nearing its end, we would appreciate hearing if you have any remaining questions or concerns regarding our response. We would be happy to provide further clarification.

Thank you for your time and consideration.

Reviewer_ftVEOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper provides an algorithm for online DR-submodular optimization with 0.401 approximation and low regret.

Critical strengths

The fact that the proposed method achieves the best approximation so far is the strength.

Critical weaknesses

No weaknesses. This is an interesting result.

Questions for authors

No questions.

1 comment

Thank you for the positive assessment and for recognizing that the approximation coefficient is the main strength of the paper. This is the first online approximation improvement beyond 1/e1/e in this regime.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General comments and summary of revision

We thank all reviewers for their time and comments. We have uploaded a revised PDF in which all changes are marked in blue. The algorithm, Theorem 3.4, and the 0.40130.4013 approximation and regret bounds are unchanged. The revisions are:

  1. Main contribution stated explicitly (abstract; Section 1, new paragraph "Why feasible queries matter"; Conclusion). Among online algorithms using one gradient query per round, ours is, to our knowledge, the first to exceed 1/e1/e with every query in the feasible set KK. ICLR's reviewer guidance does not require comparison with contemporaneous work that appeared within two months of the submission deadline. Among earlier work, to our knowledge, the best online coefficient for this problem was 1/e1/e in any query model, so the qualification above is needed only to account for the recent preprints discussed in our response to Reviewer x1eb. The new paragraph in Section 1 explains why feasible queries matter: when a gradient is obtained by running the system at an allocation, an infeasible allocation cannot be run, and our gradient bound BB is needed only on KK.
  2. Relation to prior techniques (Section 1). The paragraph now separates the standard online reduction (Pedramfar and Aggarwal, 2024; Lu et al., 2026) from our structural contribution: aligning the trajectory and feasible-box comparisons at a common state and matching their nonlinear residual coefficients, with every gradient location in [0,x]⊆K[0,x]\subseteq K. (Reviewers NjXh and x1eb)
  3. Why the strengthened trajectory bound is needed (Section 3.1, after Proposition 3.1). At s=199/500s=199/500, the retained mixed term gives ℓ−ζs>0.004823\ell-\zeta_s>0.004823 for ℓ=μs/3\ell=\mu_s/3, whereas the unstrengthened bound gives a value below −0.015-0.015, so the coefficient-matching choice would not be justified without it. (Reviewers NjXh and x1eb)
  4. Regret constant (Section 1, after equation (1); Table 1). We state that the improvement is in the leading coefficient and that our bound O(DBdT)O(DB\sqrt{dT}) has an additional d\sqrt d factor relative to the O(DBT)O(DB\sqrt T) bound of the 1/e1/e baseline. (Reviewer NjXh)
  5. Presentation and organization. To improve presentation, we have reorganized the paper. The abstract and introduction are rewritten in plain language, and the proofs are written out step by step with equation references. The verification of the constants α∗>0.4013\alpha_*>0.4013 and ℓ>ζs\ell>\zeta_s is now in Section 3.3, and the estimator guarantee is stated as Lemma 4.1. Each appendix is titled by the result it proves. Repeated material is removed. We have not changed any statement or bound.

The paper is theoretical: its contribution is a worst-case approximation guarantee, which experiments on chosen instances cannot confirm or refute (see our response to Reviewer NjXh, Q2). Detailed comparisons with the two recent preprints raised by Reviewer x1eb are given in our response to that reviewer.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.