- 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 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 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
-
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.
-
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
-
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?
-
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?
-
Given that arXiv:2610.00545 achieves a stronger 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
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 method permits queries on the ambient cube, whereas our algorithm restricts every gradient query to . To our knowledge, among online algorithms that use one gradient query per round, ours is the only one above with every query in .
For example, the direct method plays the action , and gives its coefficient for general down-closed sets. Take and . The direct method's action is feasible, but its first upper-chain query segment , , lies entirely outside . This segment is sampled with positive probability. Thus action feasibility alone does not establish query feasibility.
The direct sampler therefore does not implement the 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 , 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 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 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 .
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.
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/e whose queries all lie in K. The guarantees of 2609.02145, Sections 3–4 use function-value queries at points of [0,1]d that may lie outside the feasible set K. Our algorithm queries one full gradient at zt∈[0,xt]⊆K after committing to its action, so every query, as well as every played action, is feasible. In addition, our coefficient, α∗>0.4013, is slightly larger than their 0.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:
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.