- Rating
- 1
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
This paper studies submodular minimization with dueling feedback. This is a setting where in each interaction with the environment the learner only sees whether or not one action is better than another in the sense that, given the learner sees a random draw from , where is the sigmoid function, is a known parameter, and F is an unknown function we try to minimize. The goal as stated in the section labelled setting is to output a possibly randomized after T iterations such that is as small as possible. The paper contains several results pertaining to this objective and seemingly some results that aid in obtaining this objective. The paper also contains experiments.
Critical strengths
I have trouble articulating strengths, as the paper is unreadable to me.
Critical weaknesses
I had trouble reading this paper. This made understanding the results somewhat impossible for me. I will provide some examples in hopes that the authors may improve the writing such that the paper becomes more readable. As it stands right now I can not recommend accepting the paper.
The first improvement lies in the first paragraph, the second sentence. The sentence describes a developer selecting retrieved facts and a tool that calls for an answer. However, it is completely unclear what facts are being retrieved or what questions need answered. Then the fourth sentence suddenly describes a scenario in which lower values are preferable. However, it is unclear what these lower values represent. This unclarity continues throughout the introduction and the rest of the paper. New concepts are continuously used without introduction. I strongly recommend the authors to carefully read the paper and see where new concepts are used without introduction, and then write the paper in such a way that every new concept that is needed is carefully introduced.
There is a mismatch in how the introduction describes the setting, how the section labelled “setting” describes the setting, and how the setting seems to be used in “the price of a direction”. In the introduction, the second paragraph reads as if in each interaction with the environment we will learn the sign of . In the “setting” it reads as if we see a random draw from . In “the price of a direction” the sentence “the value of is accessible” reads as if we directly get to observe the value . These three versions of the setting are seemingly not compatible, and it is highly confusing to read the paper as a consequence.
Section 4 is disconnected from the previous section. In section 3 the goal is stated as making as small as possible. Yet in section 4 it seems that the goal is to estimate gradients of the Lovasz extension. There needs to be a paragraph relating the two goals to each other. Likewise, section 4.2 starts off with “to test whether this dependence is unavoidable”, but the last paragraph of 4.1 does not mention any dependence whatsoever. This happens throughout the paper: sections are completely disconnected from each other and that makes the paper unreadable.
The notation changes throughout the paper. The notation introduced in the “setting” for the goal of the paper is replaced by in section 5 and in section 6 there appears to be another way to denote a version of in theorem 10. There are several other seemingly random switches in notation throughout the paper.
Questions for authors
I do not have questions for the authors.
2 comments
Follow-up for Reviewer 5Smm
Dear Reviewer 5Smm,
Thank you again for your careful review. Your comments on the three passages that appeared to describe different feedback models helped us clarify what each query returns and how repeated comparisons yield an estimate of the difference.
We posted our response on November 13 and wanted to check in before the discussion closes. We would appreciate hearing whether these explanations address your concerns. If anything is still unclear, we would be happy to clarify it while the discussion is open.
Thank you for your time.
Best regards, The Authors
One feedback model, one objective, and the steps connecting them
W1. What do the opening examples and quantities mean?
“Retrieved facts and tool calls” are the objects being selected; “lower is better” means a lower objective value for the selected set. The original opening places a recommendation bundle beside selecting facts and tools to answer a question, then introduces noisy comparisons of candidate sets (original p. 1, lines 31–37). Both illustrate selecting a set through comparisons. The facts and question depend on the application; Section 3 formally defines F and its submodularity conditions.
We retain these examples and clarify that the facts come from retrieved documents and the selection answers a user's question. The opening now defines F(S) as the selected subset's loss and specifies noisy binary feedback. We preserve the route from the Lovász extension to subgradient optimization; Section 3 explains threshold rounding back to a set.
The original Section 3 defines the extension, and Section 4.1 defines tie blocks and the canonical subgradient before reconstruction. The revised Introduction adds their intuition: equal coordinates form a tie block, internal greedy orders give valid subgradients, and averaging gives the canonical direction. This connects each concept to set optimization before its formal result.
W2. Is the feedback a sign, a random comparison, or a numerical difference?
All three passages describe one random binary comparison model: the observed feedback, its probability law, and estimation from that feedback.
Introduction: the observed comparison is noisy. The original text states that a comparison gives neither a numerical gap nor a reliable ordering (original p. 1, lines 39–42). The learner therefore does not observe the true sign of F(A_t)−F(B_t).
Setting: σ(b(F(A_t)−F(B_t))) is the probability of Y_t=+1. The observation is only +1 or −1, not that probability or the numerical difference. This specifies the probability law of the Introduction's noisy comparison.
“h_j(U) is accessible”: the difference is estimated from those comparisons. Section 4.1 chooses A=H_j∪U and B=H_j, making the unknown gap h_j(U). Repeated binary responses construct Z_U with E[Z_U|U]=h_j(U), used in the subgradient estimate. The original construction and cost appear on p. 5, lines 239–249, and in Appendix A.3, Lemma 14. We replace “accessible” with “an unbiased estimate of the unknown difference obtained from repeated binary comparisons”; every response is charged to the budget.
W3. How does subgradient reconstruction serve set minimization?
It supplies the optimization direction. The original Section 3 already states min_x f(x)=min_S F(S), with threshold-rounded expected loss f(x) (original p. 3, lines 153–161). Section 4 studies the comparisons needed for an accurate direction; Section 5 uses it to optimize f and rounds back to a set, controlling the same set-loss excess. We add this connection at the start of Section 4.
In Section 4.2, “this dependence” means dependence on dimension and tie structure. Original Section 4.1 already contrasts quadratic cost when coordinates differ with linear cost when all tie (original p. 5, lines 257–260). Section 4.2 asks whether arbitrary adaptive set comparisons improve that dependence. Its lower bound matches the structural dependence for regular, locally unbiased canonical reconstruction. The revision spells out this referent to connect the upper bound, lower bound and algorithm.
W4. How are the objective notation and budget unified?
Sections 3, 5 and 6 concern the same expected set-loss excess: task definition, algorithmic upper bound, and minimax lower bound. The original Ŝ in Section 5 is the budget-T output Ŝ_T from the Setting. The minimax quantity takes the worst function and best budget-constrained algorithm for that same loss.
We consistently use Ŝ_T and expand the minimax definition to identify the function class and algorithm budget. T counts binary comparisons, as already specified in original Section 3 and Theorem 8; one update may use several comparisons. The revised Setting makes this distinction explicit.