- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This work studies submodular function minimization using noisy pairwise comparisons between sets that differ by at most one element. The authors employ sequential unbiased log-odds estimation to establish the optimal minimax rate of for sigmoid preferences, improving the previously known upper bound. The paper further extends the analysis to more general nonlinear transfer functions.
Critical strengths
A meaningful theoretical problem with detailed mathematical analysis.
Critical weaknesses
-
Limited algorithmic novelty relative to existing estimation methods. The optimization framework relies on standard stochastic subgradient methods, while sequential unbiased log-odds estimation and randomized estimation of nonlinear functions of expectations have direct precedents in the literature. Although the theoretical improvements are meaningful, the main algorithmic contribution appears to be a refinement and integration of existing estimation techniques within an established estimation-to-optimization framework. The extent of the methodological novelty is therefore unclear.
-
Insufficient numerical experiments. The experiments are limited to two small synthetic settings and do not convincingly demonstrate improvements over existing methods. In particular, the empirical advantages of the proposed estimators and their scalability to larger problems remain unclear. Although the paper is primarily theoretical, more comprehensive experiments would strengthen its relevance to the broader ICLR audience.
Questions for authors
-
Could the authors clarify the key technical differences between the proposed estimators and existing methods? In particular, which components constitute fundamentally new methodological contributions, rather than refinements or applications of established estimation-to-optimization techniques?
-
Could the authors provide additional experiments across different problem sizes, comparison budgets, and transfer functions to evaluate the scalability and practical advantages of the proposed methods?
Response to Reviewer CK6q
We thank Reviewer CK6q for asking us to make the technical contribution and empirical evidence clearer. We revised the Introduction and Section 4 to explain the role of the uniform bounds, and Section 6 now leads with the larger held-out comparisons and actual-solver learning curves. We address these two points below.
Q1. Which parts of the analysis contribute beyond the existing estimation tools?
A1.
We prove uniform moment bounds for the antithetic estimator and use them to obtain sharp optimization rates under a hard comparison budget. Our analysis builds on the log-odds identities, antithetic construction, and Lovász-SGD framework developed in prior work.
Under Assumption 3, these estimates and matching lower bounds give the sharp joint characterization Rn,T(1)(ρ)=Θρ(min{1,nψcl(n/T)}).
At a singular inverse, the required bounds must remain uniform over the unknown marginal. Bounds based only on inverse magnitude can lose logarithmic factors at nearly linear scales. Lemma 14 bounds the existing antithetic correction through D(t)=2ϕ(t)−ϕ(2t); its normalized dyadic terms telescope, and Lemmas 15 and 16 yield the uniform bias-cost-second-moment tradeoff. For ϕ(t)=tlog(e/t), Section 4 explicitly derives allocation-product upper bounds O(L4) from inverse size and O(L2) from curvature, showing how the extra logarithm disappears from the risk bound.
For sigmoid preferences, the SFM analysis uses the whole-chain bound ∥g∥1≤2 to control random cost and second moment. Propositions 10 and 11 enforce a hard comparison budget.
The other results explain how this rate depends on the link. Within Assumption 3, Theorem 5 equates uniformly finite-cost, finite-second-moment unbiased estimation with the T−1/2 optimization rate; finite-resolution biased estimates still attain the optimal rate in the singular cases. Section 5 exhibits an analytic link with positive derivative at zero but rate T−1/6 because of off-tie flatness. Theorem 6 characterizes arbitrary known links at fixed dimension using a global inverse modulus; the new Proposition 21 adds a polynomial dimension-dependent upper bound. Sharp joint dependence for arbitrary links remains open.
Q2. What do the experiments show on larger problems and across budgets?
A2.
Section 6 and Appendix J.4 now evaluate cut, coverage, and facility-location objectives at n=20,50,100, strengths b=1,2,4, and budgets T/n=4000,16000,64000. There are 90 held-out objectives, twenty oracle repetitions per objective, and separate training objectives for tuning. All strengths and budgets are reported. Tuned Firth has lower mean excess in 24 of 27 largest-budget settings; harmonic has lower mean excess in three.
Learning as the budget increases. To examine the learning behavior of the implemented solvers, Figure 2 and Appendix N.1 use the same objective bank at every budget and constant no-observation baselines. Harmonic's sigmoid-family slopes at n=2,4,8 are -0.545, -0.509, and -0.496; Firth also exhibits approximately T−1/2 behavior. The generic off-tie local solver has slope -0.165. These finite-family diagnostics show actual-solver learning over the tested budget range. Firth's published T−2/5 guarantee is an upper bound; the tested families exhibit faster decay.
What affects finite-budget performance? A separate nine-objective ablation (Appendix J.5) reduces the median excess ratio to published Firth from 2.13 for restarts to 1.06 for a whole-chain single run. With the antithetic corrections held fixed, curvature-based allocation improves the measured cost-second-moment proxy by 1.62x (Appendix N.2). Power-link experiments for q=1,1.5,2,3 show substantial overhead: the finite-level optimizer's normalized loss remains above 0.1 even at 100 times the majority-reference budget in the tested fixed-gap setting (Appendix J.6). Appendix N.4 reports actual-optimizer learning for q=2,3 on a fixed bank as finite-budget diagnostics; the observed curves show substantial finite-budget effects.