When Do Nonlinear Preferences Slow Submodular Minimization?

We study minimization of $[0,1]$-valued submodular functions on $n$ elements from noisy comparisons between sets that differ by at most one element, which we call 1-local queries. For every fixed sigmoid strength $b>0$, we establish the minimax rate ${\Theta }_b(\min \{1,n^{3/2}/\sqrt{T}\})$. Our algorithm uses sequential unbiased log-odds estimates and at most $T$ comparisons; the previous upper bound was $O_b(n^{7/5}{T}^{-2/5})$. More generally, let $\psi$ be the inverse of the odd part of a known transfer function $\rho$. Under regularity and shape conditions on $\psi$, we prove the minimax rate ${\Theta }_{\rho }(\min \{1,n{\psi }_{\mathrm{cl}}(\sqrt{n/T})\})$ jointly in $n$ and $T$, where ${\psi }_{\mathrm{cl}}$ extends $\psi$ 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 $T^{-1/2}$ 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 $\Theta (T^{-1/6})$ on two elements because 1-local queries encounter flatness away from ties. For arbitrary transfer functions and fixed $n\ge 2$, the inverse’s modulus of continuity characterizes the rate.