acceptodds
Under review as a conference paper at ICLR 2027

Ties Worth Keeping in Dueling Submodular Minimization

Abstract

Many learning systems must choose a set but observe only which of two candidates is preferred. For submodular objectives, existing analyses combine the cost of reconstructing a Lovasz subgradient with optimization. Under sigmoid feedback, we characterize the worst-case tradeoff between expected comparison count and mean squared error for reconstructing a canonical subgradient. This cost depends on which coordinates of the iterate are equal, with quadratic dimension dependence when all coordinates differ and linear dependence when all coincide. A Shapley identity yields an unbiased estimator. For regular, locally unbiased estimators, an electrical network argument gives a matching structural lower bound that covers arbitrary adaptive comparisons. Rounding the iterate creates ties at controlled bias, yielding a family of algorithms that improves the optimization bound over both the unquantized method and prior work at intermediate budgets. Experiments support the predicted dependence on tie structure and the optimization benefits of quantization. Across two objective families, one fitted constant describes the measured product of query cost and mean squared error within 7%; controlled optimization experiments reduce median error by up to a factor of 19 relative to the unquantized method.

Primary area:
learning theory
Keywords:
submodular minimization, pairwise comparison feedback, query complexity, stochastic optimization, Shapley estimation

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_5SmmOpenReview ↗
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 At,Bt∈[n]A_t, B_t \in [n] the learner sees a random draw from σ(b(F(At)−F(Bt)))\sigma(b(F(A_t) - F(B_t))), where σ\sigma is the sigmoid function, b>0b>0 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 ST^∈[n]\hat{S_T} \in [n] after T iterations such that E[F(ST)−min⁡S∈[n]F(S)]E[F(S_T) - \min_{S \in [n]}F(S)] 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 F(At)−F(Bt)F(A_t) - F(B_t). In the “setting” it reads as if we see a random draw from σ(b(F(At)−F(Bt)))\sigma(b(F(A_t) - F(B_t))). In “the price of a direction” the sentence “the value of hj(U)=F(Hj∪U)−F(Hj)h_j(U) = F(H_j \cup U) - F(H_j) is accessible” reads as if we directly get to observe the value F(At)−F(Bt)F(A_t) - F(B_t). 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 E[F(ST)−min⁡S∈[n]F(S)]E[F(S_T) - \min_{S \in [n]}F(S)] 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 E[F(S^)−min⁡SF]E[F(\hat{S}) - \min_{S} F] in section 5 and in section 6 there appears to be another way to denote a version of E[F(S^)−min⁡SF]E[F(\hat{S}) - \min_{S} F] 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
AuthorsOpenReview ↗

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.

  1. 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).

  2. 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.

  3. “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.

AuthorsOpenReview ↗

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

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

This paper studies submodular minimization under noisy pairwise comparison feedback. It constructs an unbiased estimator of a canonical Lovász subgradient using blockwise Shapley values and derives matching upper and lower bounds on the comparison cost and reconstruction error under specified estimator assumptions. The paper further proposes quantizing the optimization iterates to create tied coordinates, reducing subgradient estimation cost while introducing controlled approximation bias. It establishes a budget-dependent convergence guarantee and evaluates the method on synthetic objectives and image graph-cut problems.

Critical strengths
  1. The paper constructs an unbiased blockwise Shapley subgradient estimator using sampled wide-pair comparisons. The matching upper and lower bounds characterize how the reconstruction cost depends on the tie-block structure, reducing the dimension dependence from quadratic to linear when all coordinates are tied.
  2. The paper introduces quantization of the query iterates to create tied coordinates and reduce the cost of estimating subgradients. The analysis explicitly balances estimation error against quantization bias and derives an improved dimension-budget tradeoff compared with the unquantized approach.
Critical weaknesses
  1. The main optimization experiments do not directly validate the algorithm and quantization tradeoff analyzed in Theorem 8. The theorem considers a fixed-round algorithm with a hard query-budget cap and a prescribed step size, whereas the main experiments use an uncapped implementation and include empirically calibrated step sizes. The largest reported improvement also uses a fixed quantization level L = 1, for which the theorem's bias term R/L equals the maximum possible excess R, making the bound trivial for this configuration. The current experiments demonstrate the effectiveness of coarse quantization on the tested instances, but do not directly verify the predicted budget-dependent choice of quantization level.

  2. The experimental comparison with the Sho–Ito baseline is not sufficiently complete under comparable tuning conditions. The main step-size sensitivity experiments vary the proposed method's step size while retaining the baseline's original schedule. Appendix D.7 introduces common step multipliers but reports only selected configurations of one Flower objective. Moreover, the reported 19-fold improvement is measured against the paper's own unquantized variant rather than Sho–Ito. Although Table 4 shows improvements on several image instances, the comparison does not fully establish how consistently the advantage holds across tasks, budgets, feedback strengths, and comparable tuning settings.

Questions for authors
  1. Could the authors provide optimization results using the exact algorithm analyzed in Theorem 8, including its prescribed step size and hard budget cap? It would also be useful to report the mean excess error across different budgets and quantization levels, especially when the quantization level is selected according to the theoretical tradeoff. How does this compare with the fixed L = 1 configuration used in the main experiments?

  2. Could the authors provide complete paired comparisons with Sho–Ito under comparable step-size tuning and realized query budgets? Appendix D.7 applies common step multipliers but displays only selected Flower configurations. Results across the complete set of tasks, budgets, and feedback strengths, together with uncertainty estimates, would help establish whether the improvements are consistent across settings.

3 comments
AuthorsOpenReview ↗

The strict algorithm, the quantization choice, and paired comparisons

W1/Q1(a). Was the complete algorithm analyzed in Theorem 8 run?

Yes. The original optimization experiments compared theoretical and empirically calibrated step sizes, with the fixed-round implementation and Theorem 8's hard-budget version distinguished in Appendix D. Following your suggestion, we additionally ran the complete theorem algorithm with prescribed steps, fixed rounds, a hard budget guard and fallback on overflow. Mean excess losses are:

Family / budgetL=1L=2L=4L=8Unquantized
Decomposable / 1,000.5407.1992.1992.1999.2131
Decomposable / 16,000.3011.1992.1992.2064.2199
Decomposable / 64,000.2046.1992.1992.1978.2172
Graph cut / 1,000.5214.0333.0333.0358.0712
Graph cut / 16,000.5368.0333.0333.0485.0889
Graph cut / 64,000.4568.0333.0333.0342.0677

Here n=8, b=R=1, with two oracle seeds per fixed objective. Every run respects the cap, and an independent implementation reproduces the results (Appendix E).

Quantized updates still have lower final error under the prescribed steps. L=2,4,8 each outperform unquantized updates in all six family/budget settings. At budget 64,000 on the decomposable objective, L=8 gives .1978, unquantized .2172, and L=1 .2046.

The source of the lower error differs by level. L=2,4 preserve their quantized initial point: .1992 and .0333 are the two objectives' center losses. L=8 permits changes; at budget 64,000 on the decomposable objective, its mean loss falls from .1992 to .1978. This separates the comparison with unquantized updates from progress beyond initialization.

Q1(b). Which L does theory choose, compared with fixed L=1?

Following your suggestion, we computed the level minimizing the explicit theorem bound at each budget. It selects L=1 at all three, matching the main experiments' fixed level; the bound clipped at R is 1. This selects the smallest conservative bound, whereas the table compares actual excess loss.

For useful bound-based selection, constants matter. At n=16,32,64, the first budgets where a finite level beats both R and the unquantized bound are approximately 6.82×10^8, 2.73×10^9 and 1.09×10^10, each selecting L=4; at n=8 no finite level meets both conditions. These are sufficient-bound thresholds, not measured optimization thresholds. The revision separates exact-algorithm tests from tuned experiments and identifies the L=1 bias R/L=R.

W2/Q2. Can you provide matched tuning, uncertainty and comparisons across settings?

Yes. Building on original D.7's common-step-multiplier study, we computed paired differences and uncertainty for all 207 archived configurations: nine tasks, all archived budgets and feedback strengths. Pairs share the objective, oracle seed and realized response count, with multipliers .5,1,2 on each method's base schedule. Incomplete terminal updates are excluded. Five method pairs give 1,035 comparison rows.

Gains vary by task and configuration. L=2 has lower mean excess than our unquantized variant in 188/207 configurations and than Sho–Ito in 57/207; L=1 beats Sho–Ito in 6/207. For L=2 versus Sho–Ito, paired 95% bootstrap intervals favor L=2 in 43, Sho–Ito in 136, and include zero in 28. They measure within-configuration oracle-seed uncertainty without cross-configuration multiplicity correction.

Appendix E summarizes all configurations by task and method pair, retaining both directions of comparison. The full row-level differences and intervals are saved in a separate CSV. The PDF thus provides a compact summary covering every configuration.

We also identify the comparator beside the headline result: the 19-fold median improvement is over our unquantized variant at n=64 and about 10^9 comparisons. The jointly tuned Sho–Ito study addresses performance relative to that separate baseline.

Thank you for the detailed response and the additional experiments. The new experiments address several of my original concerns, particularly by evaluating the complete algorithm from Theorem 8 and providing paired comparisons across 207 configurations. The experiments using the exact algorithm from Theorem 8 are limited to n=8 with only two oracle seeds per objective. Moreover, L=2 and L=4 return exactly the initial-point losses in all six settings. Their advantage over the unquantized method therefore does not demonstrate actual optimization progress. Although L=8 shows some improvement beyond initialization, the improvement is small. The theoretical selection of L=1 also relies on a bound clipped at R=1, which does not provide a nontrivial validation of the predicted budget-dependent quantization tradeoff.

I appreciate the additional evidence and the clarification of the comparison underlying the reported 19-fold improvement. The theoretical characterization of sensing complexity and the use of ties to reduce reconstruction cost remain valuable contributions. Although the new experiments reveal limitations in the practical optimization results, they do not change my assessment of the paper's theoretical contribution. I will therefore maintain my original rating of 3

AuthorsOpenReview ↗

Thank you for the follow-up

Thank you for the careful follow-up and for recognizing the sensing-complexity characterization and the role of ties in reducing reconstruction cost. We appreciate your consideration of the additional experiments and clarifications.

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

This paper builds on the work of Sho and Ito to study submodular function minimization under sigmoid comparison feedback. Its central idea is to separate the query cost of subgradient reconstruction from the subsequent optimization process. The authors combine a Shapley identity with an exactly unbiased estimator of value differences to construct an unbiased estimator of a canonical subgradient, and characterize how its reconstruction cost depends on the coordinate tie structure. They then quantize the iterates to deliberately create ties, balancing direction-estimation cost against quantization bias. This yields improved optimization error bounds, supported by experiments on synthetic objectives and image graph-cut problems.

Critical strengths
  1. The sum of coefficient norms in the Shapley representation determines both the sampling distribution used in the upper bound and the lower bound derived from the graph-Laplacian information structure. This connection is one of the paper’s most appealing technical contributions. The lower bound accommodates arbitrary adaptive set comparisons, although it is restricted to regular, locally unbiased estimation of the canonical subgradient. The improved expected optimization error bounds under sigmoid feedback also represent substantive progress over prior work.
  2. Quantizing the iterates to create ties and thereby reduce direction-estimation cost is a natural idea. The authors use an (\ell_1) bound on subgradients to control quantization error without introducing an additional dimension factor. The coupling analysis connecting the exactly unbiased scalar estimator to the hard query-budget cap is also reasonably complete.
Critical weaknesses
  1. Starting from Section 4, the exposition becomes dense, with substantial notation and numerous technical definitions. Some key derivations would benefit from more intuition. Before presenting the formal results, the authors could more clearly explain the estimation target, the sampling construction, and the main proof ideas. A simple worked example illustrating how the tie-block structure affects reconstruction cost would also improve accessibility.
  2. The main sweep fixes one objective instance for each objective-family–dimension pair and primarily considers small dimensions. The independent validation in Appendix D.7 strengthens the empirical evidence, but it evaluates second-moment predictions rather than exactly the same query-cost–MSE product reported in Figure 3a. The authors should clarify which conclusions each experiment supports. Comparisons of the query costs required by different reconstruction methods to reach the same MSE would also strengthen the evaluation.
Questions for authors

On practically motivated objectives, do unquantized optimization trajectories naturally form a small number of large tie blocks, or do most coordinates remain distinct? To what extent does the low-cost block structure arise naturally, and to what extent does it depend on deliberate quantization? Appendix D.7 reports the realized block counts for one Flower configuration. Could the authors provide corresponding statistics across more objectives and query budgets to establish how broadly this structure and its benefits occur?

4 comments
AuthorsOpenReview ↗

Natural ties, reconstruction cost, and a worked example

Q1. Are large tie blocks natural, or created by quantization?

Few large tie blocks are mainly maintained by deliberate quantization. Following your suggestion, we extended original D.7's Flower example to five practical tasks across all archived query budgets, feedback strengths and step settings.

Without quantization, more coordinates become distinct as budgets increase. From 10^5 to 10^7 responses, singleton-coordinate fractions rise from 47.6% to 90.9% on Flower and 33.1% to 82.4% on CiteSeer; the three department graphs reach 84.8–89.9%. L=2 maintains about 2.86–2.92 blocks across these tasks and budgets, with 96.40–99.76% of coordinates in blocks of at least ten. Quantization thus preserves a few large blocks as natural ties disappear.

Quantization improves over unquantized updates on all five tasks. Matching task, query budget, feedback strength and step multiplier, L=2 has lower mean excess loss in 98/108 configurations across the four graphs and 27/27 on Flower, averaging 16 seeds per configuration. The gain covers most graph configurations as well as Flower.

Progress from initialization uses a different baseline. Compared with the zero-query center, all 27 Flower configurations improve, whereas each graph task has 0/27 improvements. The graph gains above therefore compare quantized with unquantized updates; the initialization comparison separately measures net progress from the starting point (Appendix E).

W2(a). What does independent validation establish?

Original D.7 reported second moments, while Figure 3a reports expected query cost × MSE. Following your suggestion, we recomputed the latter from the existing validation records. For each target, we subtract the exact canonical vector's squared norm from the predicted and analytic design second moments, then multiply by expected response cost. On 180 targets at n=8,10 with instance seeds disjoint from calibration, maximum relative discrepancies are .68%, 3.24%, 9.21% at bR=.25,1,3; 174/180 are within 7%. Figure 3a uses the original eight reused n=8–20 objectives; this check tests transfer to independently drawn targets.

W2(b). How many queries do the methods need to reach the same MSE?

Following your requested equal-MSE comparison, we added common-target query-cost measurements on two n=8 objectives with four partitions each. The adjacent estimator randomizes tie-compatible orders, so both estimate the same canonical vector and charge every binary response. Wide pairs have lower cost × MSE for the two all-tied targets; adjacent reconstruction is lower on the other six.

At MSE=1, the adjacent method first reaches the threshold at tested expected costs of about 7,615 responses on seven targets and 30,460 on graph-cut/all-tied. Wide pairs remain above it at their tested maximum of about 3,808. These are first attained grid points, with different tested cost ranges. Smoothed-logit comparisons include squared bias: at MSE=.01, r=16 needs 32,768 responses on all eight targets, r=64 needs 32,768–131,072, and r=4 does not reach it. Appendix E reports all targets and costs separately from end-to-end optimization.

W1. What is estimated, how is it sampled, and why do ties help?

The target averages greedy subgradients over tie-compatible orders; each block contributes its Shapley vector. We sample blocks and subsets by coefficient-vector norms, estimate the subset's value difference from earlier blocks through noisy comparisons, and divide by sampling probabilities. One wide comparison informs several coordinates while retaining unbiasedness.

For n=4, the structural factor D=(Σ C_m)² is 64 for four singletons, 32 for two pairs, and (2+4/√3)²≈18.57 for one block. The sufficient comparison count for MSE ε is c⌈VD/ε⌉, with c,V set by the scalar estimator, so more ties reduce the bound.

The lower bound uses the same coefficient vectors. Adaptive comparisons form an information graph between set values; recovering the target coefficients incurs the same structural dependence, up to constants. Revised Section 4 presents this example and intuition before the lower bound for regular, locally unbiased canonical reconstruction.

AuthorsOpenReview ↗

Follow-up for Reviewer tpxi

Dear Reviewer tpxi,

Thank you again for your careful review. Your questions about whether large tie blocks arise naturally and how much benefit deliberate quantization provides helped us focus our experimental comparisons.

We posted our response on November 13 and wanted to check in before the discussion closes. We would appreciate hearing whether the additional statistics and comparisons 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

Thank you for the follow-up. The added results clarify how quantization creates and maintains tie blocks. My main reservation remains the practical relevance of the problem setting, especially since the graph experiments show no improvement over initialization. I’ll keep my current rating.

AuthorsOpenReview ↗

Practical Motivation and the Graph Optimization Results

Thank you for recognizing the clarification of how quantization creates and maintains tie blocks. Our practical motivation is to improve subset selection with a limited budget of noisy comparisons, when feedback only tells us which of two candidate subsets is better. On Flower, the quantized method achieved a lower final mean loss than initialization in all 27 tested configurations, demonstrating net optimization progress under this feedback model.

The graph objectives also penalize differences between connected nodes. This cost is zero at the center initialization. Our replay diagnostics showed that noisy updates separated connected nodes, and the resulting increase in edge-cut costs dominated the loss increase. Thus, while large tie blocks reduce reconstruction cost, translating that saving into optimization progress also depends on how the updates interact with the graph structure. In the final version, we will explain this specific cause and the relationship between reconstruction efficiency and optimization progress more clearly.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.