Ties Worth Keeping in Dueling Submodular Minimization

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.