acceptodds
Under review as a conference paper at ICLR 2027

When Do Nonlinear Preferences Slow Submodular Minimization?

Abstract

We study minimization of -valued submodular functions on elements from noisy comparisons between sets that differ by at most one element, which we call 1-local queries. For every fixed sigmoid strength , we establish the minimax rate . Our algorithm uses sequential unbiased log-odds estimates and at most comparisons; the previous upper bound was . More generally, let be the inverse of the odd part of a known transfer function . Under regularity and shape conditions on , we prove the minimax rate jointly in and , where extends by the constant one above its domain. A curvature bound for antithetic multilevel estimation gives the upper bound for power, logarithmic, and infinite-order flatness. Within this class, the rate is equivalent to the existence of unbiased marginal estimators with uniformly bounded expected cost and second moment. Beyond this class, an analytic transfer function with positive derivative at zero can have minimax rate on two elements because 1-local queries encounter flatness away from ties. For arbitrary transfer functions and fixed , the inverse’s modulus of continuity characterizes the rate.

Primary area:
optimization
Keywords:
submodular minimization, dueling optimization, preference learning, minimax rates, sequential estimation, multilevel Monte Carlo

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_CK6qOpenReview ↗
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 Θb(min⁡1,n3/2/T)\Theta_b(\min{1,n^{3/2}/\sqrt{T}}) 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?

1 comment
AuthorsOpenReview ↗

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)}).R^{(1)}_{n,T}(\rho)=\Theta_\rho\left(\min\lbrace1,n\psi_{\mathrm{cl}}(\sqrt{n/T})\rbrace\right).

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)D(t)=2\phi(t)-\phi(2t); its normalized dyadic terms telescope, and Lemmas 15 and 16 yield the uniform bias-cost-second-moment tradeoff. For ϕ(t)=tlog⁡(e/t)\phi(t)=t\log(e/t), Section 4 explicitly derives allocation-product upper bounds O(L4)O(L^4) from inverse size and O(L2)O(L^2) 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\lVert g\rVert_1\le2 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/2T^{-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/6T^{-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,100n=20,50,100, strengths b=1,2,4b=1,2,4, and budgets T/n=4000,16000,64000T/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,8n=2,4,8 are -0.545, -0.509, and -0.496; Firth also exhibits approximately T−1/2T^{-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/5T^{-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,3q=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,3q=2,3 on a fixed bank as finite-budget diagnostics; the observed curves show substantial finite-budget effects.

Reviewer_R8FBOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the minimization of [0,1]-valued submodular functions over a ground set of n elements using noisy comparisons between sets that differ by at most one element, referred to as 1-local queries. The proposed algorithm employs sequential unbiased log-odds estimators and uses at most T comparisons. The authors establish lower and matching upper bounds for the sigmoid transfer function.

Critical strengths
  1. This paper investigates a fundamental submodular optimization problem under a noisy 1-local query model, which is an interesting and theoretically meaningful setting.
  2. The authors close an existing gap in the theoretical analysis by establishing matching upper and lower bounds.
  3. The paper is technically sound. In particular, the algorithmic design, especially the harmonic estimator, is interesting, and the theoretical analysis appears rigorous and solid.
Critical weaknesses

My primary concern is the practical relevance and applicability of the proposed framework.

First, the paper does not provide a concrete real-world application that simultaneously motivates submodular minimization and the restriction to noisy 1-local queries. While both submodular optimization and noisy comparisons are well-studied, it is unclear in which practical scenarios these specific assumptions naturally arise together. Providing such an example would significantly strengthen the motivation and practical relevance of the work.

Second, the experimental evaluation is overly simplified, even for a theory-oriented paper. For example, one experiment considers a cardinality-based function defined over a ground set of only three elements. Such a small-scale synthetic example provides limited evidence of the practical effectiveness or scalability of the proposed algorithm.

Third, and perhaps more importantly, I am concerned about the assumption that the transfer function is known. This assumption raises a fundamental question about the practical applicability of the proposed model. In particular, how can the transfer function be estimated or calibrated without access to the underlying submodular function values? If estimating the transfer function requires access to the original submodular function, then the motivation for relying exclusively on noisy 1-local comparisons becomes less compelling. On the other hand, if the authors assume that the transfer function can be independently estimated or is known a priori, they should explicitly justify this assumption and explain the practical scenarios in which it holds.

Questions for authors

Please refer to my comments in the weakness section.

1 comment
AuthorsOpenReview ↗

Response to Reviewer R8FB

We thank Reviewer R8FB for asking how the assumptions fit an application and how the link can be calibrated. We revised Section 2 to make the modeling inputs explicit and explain a bundle-selection example. Below, we address the link assumption first, followed by the application and evaluation.

1. What link information does the method require?

The method assumes a specified response-law shape. For sigmoid preferences with n≥2n\ge2, a known interval 0<bmin⁡≤b≤bmax⁡<∞0<b_{\min}\le b\le b_{\max}<\infty suffices to retain the hard-budget T−1/2T^{-1/2} rate, with interval-dependent constants (Appendix M). The optimization uses only local preference comparisons.

Specifically, divide the harmonic statistic by bmax⁡b_{\max} and use that endpoint for all cost bounds and step sizes. The mean direction is (b/bmax⁡)g(b/b_{\max})g, a positive scaling that preserves the minimizers.

Our synthetic experiments evaluate optimization under these assumptions; establishing their fit to human judgments requires separate empirical evidence. Any auxiliary data used to justify these inputs would be additional to the stated optimization-query budget. Section 2 now states these modeling inputs explicitly.

Appendix N.3 tests the interval-only schedule on 18 new structured objectives with known interval [1,4][1,4]. Only the simulator uses the true bb; normalization, cost bounds, and schedule use 4. At the exploratory larger budget T/n=64000T/n=64000, harmonic excess is 1.245 and 1.269 times the exact-scale result for true b=1,2b=1,2. Smaller-budget outcomes and Firth comparisons are also reported, quantifying the finite-budget cost of this uncertainty.

Proposition 22 isolates the role of shape information. It gives two analytic, strictly increasing links with positive derivatives everywhere and two submodular objectives with identical local-comparison laws but opposite unique minimizers. The resulting identifiability obstruction concerns unrestricted shape uncertainty; individual parametric families require their own identifiability analysis.

2. Where do submodular minimization and 1-local queries arise together?

One setting is incremental bundle selection with complementary interactions, specializing the recommendation example in Sho and Ito (2026, Section 3). Let net utility be U(x)=∑iaixi+∑i<jbijxixjU(x)=\sum_ i a_ ix_ i+\sum_{i<j}b_{ij}x_ ix_ j, where bij≥0b_{ij}\ge0. The coefficients aia_ i include costs and may be negative, so the optimum balances individual net utilities with complementary gains. Maximizing UU is equivalent to minimizing submodular −U-U, after a positive affine normalization.

An interface that compares the current bundle with a version obtained by adding or removing one item makes every query 1-local. Together, complementary utility and the single-item interface give a conditional application model for incremental bundle selection.

3. Evaluation on larger problems.

Section 6 now leads with cut, coverage, and facility-location objectives at n=20,50,100n=20,50,100, strengths b=1,2,4b=1,2,4, and budgets T/n=4000,16000,64000T/n=4000,16000,64000: 90 held-out objectives with twenty oracle repetitions each. Tuning uses separate training objectives; confidence intervals resample objective means.

Tuned Firth has lower mean excess in 24 of 27 largest-budget settings. Figure 2 separately evaluates actual-solver learning on fixed objective families. The original small examples remain as mechanism diagnostics in Appendix J, with their role distinguished from the broader performance evaluation.

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

This paper studies submodular function minimization under noisy pairwise comparisons restricted to sets differing by at most one element. The authors first construct an unbiased marginal estimator for sigmoid preferences and establish a minimax rate of Θb(n3/2/T)\Theta_b(n^{3/2}/\sqrt{T}) in the nontrivial regime, improving the previous upper bound of Ob(n7/5T−2/5)O_b(n^{7/5}T^{-2/5}). They further investigate more general transfer functions using randomized multilevel estimation and characterize the minimax rates under regularity and shape assumptions on the inverse transfer function. The paper also establishes a connection between unbiased marginal estimation and the T−1/2T^{-1/2} rate and studies how flatness away from zero can affect optimization complexity under 1-local queries.

Critical strengths

First, the paper addresses a well-defined theoretical question and closes the existing gap between the upper and lower bounds for sigmoid preferences under 1-local queries. Second, the minimax characterization for a class of transfer functions and the analysis of flatness away from zero provide potentially useful insights into how comparison feedback affects optimization complexity.

Critical weaknesses
  1. The sigmoid result relies on existing unbiased log-odds estimation techniques combined with standard Lovász-extension-based stochastic optimization. The new technical contributions beyond these established tools are not sufficiently distinguished.

  2. The general analysis builds on established multilevel estimation techniques. The authors do not clearly explain what new technical difficulties their curvature analysis overcomes. Moreover, the joint minimax characterization requires restrictive assumptions, while the arbitrary-transfer result applies only to fixed dimensions.

  3. The experiments mainly illustrate estimation bias and transfer-function flatness without directly evaluating the claimed minimax rates. The proposed method also does not consistently outperform the existing Sho–Ito method.

Questions for authors
  1. What are the essential technical differences from existing unbiased estimation methods?

  2. What new difficulties does the proposed curvature analysis resolve beyond existing multilevel estimation theory?

  3. How restrictive are the assumptions underlying the joint minimax characterization?

1 comment
AuthorsOpenReview ↗

Response to Reviewer zbz5

We thank Reviewer zbz5 for the questions about the existing estimators and the role of curvature. These led us to revise the Introduction and Section 4 to explain the uniform bounds needed for the sharp rate. We address Q1-Q3 below, followed by the experimental concerns.

Q1. What distinguishes the analysis from existing unbiased estimation?

A1.

For sigmoid preferences, our SFM analysis uses the whole-chain bound ∥g∥1≤2\lVert g\rVert_1\le2 to control random cost and second moment in a single capped run (Proposition 10). Proposition 11 handles more general costs using only their first moment, even when the random cost and output are dependent.

The log-odds identities, antithetic construction, and Lovász-SGD framework are established ingredients. We credit Mendo and El Bakkali et al. for sigmoid estimation; the October revision by Chayti et al. also gives a harmonic run-length estimator.

Q2. What difficulty does the curvature analysis resolve?

A2.

The difficulty is to control the existing antithetic correction uniformly over unknown marginals, including singular inverse links, tightly enough to recover the joint minimax rate. Theorem 1 of Blanchet, Glynn, and Pei (2019) assumes differentiability and positive Hölder regularity of the derivative near the mean. Our curvature argument covers singular inverse behavior at the tie.

Lemma 14 controls the correction by D(t)=2ϕ(t)−ϕ(2t)D(t)=2\phi(t)-\phi(2t). Its normalized dyadic terms telescope, and Lemma 15 converts them into uniform moment bounds. Section 4 makes the gain concrete: for ϕ(t)=tlog⁡(e/t)\phi(t)=t\log(e/t), D(t)=2tlog⁡2D(t)=2t\log2. The inverse-size analysis gives an O(L4)O(L^4) allocation-product upper bound, whereas the curvature analysis gives O(L2)O(L^2), removing an extra logarithmic factor from the resulting risk bound.

Finite-resolution estimates then attain the matching rate in Theorem 4 even where Theorem 5 rules out unbiased marginal estimation with uniformly finite expected cost and second moment. Within Assumption 3, Theorem 5 identifies unbiased feasibility with ψ(u)=O(u)\psi(u)=O(u) and the T−1/2T^{-1/2} optimization rate.

Q3. How restrictive are the assumptions for the joint rate?

A3.

Assumption 3 provides sufficient conditions for sharp joint dependence on nn and TT. It includes regular inverses and the paper's power, logarithmic, and infinite-flatness examples. The singular branch requires a nonnegative, nonincreasing, convex derivative near zero and Dini regularity away from zero. The off-tie example isolates the importance of behavior away from ties: an analytic link with positive derivative at zero has rate T−1/6T^{-1/6} because of off-tie flatness.

For arbitrary known links, Theorem 6 uses the global inverse modulus and is sharp at fixed nn. The new Proposition 21 additionally gives Rn,T(1)(ρ)≤Cmin⁡{1,nlog⁡(e+T/n)Ωρ(n/T)}.R^{(1)}_{n,T}(\rho)\le C\min\lbrace1,n\log(e+T/n)\Omega_\rho(\sqrt{n/T})\rbrace. For a modulus bounded by HsαHs^\alpha, 0<α<10<\alpha<1, the logarithm is removable. This yields polynomial dimension dependence; sharp joint dependence for arbitrary links remains open.

Experimental concerns: learning rates and comparison with Firth.

We evaluate actual solvers on the same objective bank at every budget, alongside constant no-observation baselines (Figure 2 and Appendix N.1). Actual harmonic runs at n=2,4,8n=2,4,8 have finite-range slopes -0.545, -0.509, and -0.496; Firth also shows approximately T−1/2T^{-1/2} behavior. The generic off-tie local solver has slope -0.165, with bootstrap interval [-0.169,-0.162]. These curves measure each solver's learning behavior over the specified finite objective bank and budget range. With the antithetic corrections held fixed, curvature-based allocation improves the measured cost-second-moment proxy by 1.62x (Appendix N.2).

Section 6 also compares 90 held-out structured objectives at n=20,50,100n=20,50,100, three strengths, and three budgets. Tuned Firth has lower mean excess in 24 of 27 largest-budget settings. The power-link experiments also show substantial finite-budget overhead (Appendix J.6).

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response

We thank the reviewers for their careful reading and helpful questions about the technical contribution, modeling assumptions, and evaluation. We summarize the revisions addressing these points below and respond to each review separately.

Technical contribution (zbz5, CK6q). We revised the Introduction and Section 4 to explain why the sharp rate requires bounds that hold uniformly over unknown marginals, including singular inverses. A concrete example shows how the curvature bound removes a logarithmic loss and enters the sharp optimization rate.

Model scope (R8FB, zbz5). Section 2 states the application and known-link assumptions explicitly. Appendix M shows that a known positive bounded interval for sigmoid strength suffices without objective-value observations, while distinguishing this relaxation from the obstruction for arbitrary unknown link shapes. Appendix L adds a polynomial dimension-dependent upper bound beyond the joint theorem's shape assumptions.

Empirical evidence (all reviewers). Section 6 leads with larger held-out benchmarks and actual-solver learning curves on fixed objective families. We report the settings where tuned Firth performs better, alongside the rate and mechanism diagnostics; Appendices J and N give the full protocols and results.

Added or revised text is red relative to the original submission; red side bars identify new or revised figures, which retain their plotting colors.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.