Comparison-Only Cutting Planes for Star-Shaped Objectives, with Contour Refinement as the Test Case

Suppose an expert can only say which of two candidate outlines of a polyp better matches the lesion, and cannot give a score. Can an algorithm still reliably find the best outline? Existing theory for optimizing from comparisons covers convex and quasi-convex objectives. Quasi-convex means every set of points "at least this good" is convex. The theory for star-convex objectives instead requires numerical function values. A star-convex objective is one that only has to behave well along straight lines through the optimum.

We argue that the class actually relevant to comparison feedback lies in the gap between these two literatures. We call it star-shaped objectives: functions that strictly increase as you move away from the optimum along any ray, with no other requirement. This class has two useful properties. First, it does not change if every value is passed through the same increasing function, so comparisons see all of it. Second, it is exactly the structure that standard mask-quality judgments have over radial contour parameterizations.

The algorithmic observation is short. For such functions, the gradient direction at a point can be useless for descent, but it always defines a valid cutting plane, a half-space that is guaranteed to contain the optimum. Gradient directions are precisely what comparisons can estimate. We propose to turn this into a comparison-only cutting-plane method, analyze what accuracy it can guarantee, and test it on interactive refinement of star-convex contours on medical segmentation benchmarks against preferential Bayesian optimization and simpler comparison-driven searches.

Core Claim

Let $f$ be differentiable with minimizer $x^*$. Suppose $t \mapsto f(x^* + t(z - x^*))$ is nondecreasing for $t \ge 0$ and every $z$; this is the "star-shaped" condition. Differentiating at $t=1$ gives $\langle \nabla f(z), z - x^* \rangle \ge 0$. Equivalently,

$$x^* \in H_z = \{\, y : \langle \nabla f(z),\, y - z \rangle \le 0 \,\}.$$

So a half-space through any queried point $z$, with normal equal to the gradient direction, never discards the optimum. Three facts make this matter.

The inequality is unchanged if $f$ is replaced by $\phi \circ f$ for any increasing $\phi$, and the half-space depends only on the unit gradient direction. Comparison-based gradient-direction estimators supply exactly that direction: Comparisons Are All You Need for Optimizing Smooth Functions recovers it from aggregated pairwise bits, and Gradient Testing and Estimation by Comparisons tests alignment with a given direction in constant queries.

The inequality also resolves an apparent conflict in the file. Optimizing Star-Convex Functions shows that gradients of star-convex functions can point nearly orthogonal to the optimum, so descending along them fails. On Quasi-Convex Smooth Optimization Problems by a Comparison Oracle relies on descending along the comparison-estimated direction, which requires strict quasi-convexity. Both statements are compatible with ours, because a direction can be bad for descent yet still yield a valid cut. Lee, Sidford and Vempala needed scalar values for two reasons: to smooth discontinuous functions with a blurred logarithm, and to verify cuts. In the differentiable regime we target, the cut needs no verification, so comparisons should suffice.

Finally, star-shaped objectives arise naturally in segmentation. Represent an outline by its radius $r(\theta)$ around a fixed center, for example with truncated Fourier coefficients as in Extremal Contours. Let $r^*$ be the true radial function. Move from $r^*$ toward any other contour along $r^* + \alpha\Delta$. At each angle the area error $|r^2 - r^{*2}|/2$ then grows with $\alpha$ wherever $r$ stays positive. The Jaccard loss along this path has the form $\alpha D/(c + \alpha E)$, where $D$ is the area of disagreement, $c$ the area of the true region, and $E$ the extra union area. Its derivative is $Dc/(c+\alpha E)^2 > 0$, so it increases as well. Dice behaves the same way, and so does mean radial boundary distance. Linear reparameterizations such as Fourier or radial B-spline coefficients map rays to rays, so the property survives.

The Jaccard loss is a ratio of convex quantities, though, so its sublevel sets need not be convex. Contour preference landscapes are therefore star-shaped but plausibly not quasi-convex. That places them outside the guarantees of comparison-based normalized descent, and outside the value-based star-convex methods.

Two caveats are part of the claim. Star-shapedness is exact only when the true outline is representable and the center lies in the object's visible kernel. With truncated bases and imperfect centers it holds only approximately, and measuring how approximately is the first experiment.

Research Program

The theoretical part builds a cutting-plane method in which each cut is a comparison-estimated gradient direction at an approximate center of the current region known to contain the optimum. For progress we use a center-of-gravity style method rather than the ellipsoid method. Center-of-gravity methods need on the order of $n\log(1/\text{volume})$ cuts instead of $n^2$, and comparisons are expensive. Here $n$ is the parameter dimension, typically 11 to 33 for contours.

The open question is what accuracy this guarantees. Values carry no meaning for a comparison-only method, so accuracy must be invariant to increasing transforms. We measure it by the quantile of the returned point, the fraction of the domain that is at least as good. We will characterize when a shrinking region containing $x^*$ forces a low-quantile point. This presumably needs a regularity condition ruling out needle-like sublevel sets. We conjecture that a bounded ratio between the inner and outer radii of the sublevel sets is enough, and that monotone transforms of star-convex functions satisfy it. We also want lower bounds showing that pure ray-monotonicity without such a condition is not enough.

We will handle noisy comparisons by replacing exact cuts with slack cuts. The slack would be sized from the angular error of the direction estimate under a Bradley–Terry noise model. This addresses the deterministic-oracle limitation that Gasnikov et al. leave open.

The applied part freezes a pretrained segmenter's prediction, its center, and a Fourier radial fit. An oracle then answers "which contour is better" for pairs. The method interleaves cuts with a final comparison-based line search near the region's center.

Baselines

The naive reference point is doing nothing: report the IoU or Dice of the initial contour from the frozen model. On the file's benchmarks this is concrete. Convex Combination Star Shape Prior reports SAM with its star-prior module at Dice 86.91% on Kvasir-SEG and 80.82% on Refuge, against 84.82% and 77.73% for plain SAM. We start from SAM and from SAM+CCS where reproducible. Any comparison budget that does not move Dice meaningfully above these starting points is a failure.

The strongest existing competitor is preferential Bayesian optimization over the same Fourier coefficients. One variant uses dueling Thompson sampling from Preferential Bayesian Optimization. The other uses PF-TS with a dueling kernel from A Finite Time Analysis of Thompson Sampling for Bayesian Optimization with Preferential Feedback. This is the strongest competitor because it is designed for small comparison budgets and, in González et al., found a near-optimal Six-Hump Camel solution in about 200 duels where the Sparring bandit needed thousands. That is a 2D problem, and there is no reported result found on Lacuna for preferential BO on contour or segmentation parameter spaces. It receives the same initial contour, the same parameterization, the same oracle and noise, and the same comparison budget. Kernel hyperparameters are tuned on a held-out split with the same tuning budget as our method's slack and step parameters. Beating it means higher final Dice at matched budgets of 50, 200 and 1000 comparisons, averaged over images with paired tests.

The comparison-based normalized descent of Gasnikov et al. is the second strong competitor. It is the existing comparison method most closely related to ours: it uses the same direction estimates, but descends along them instead of cutting. No reported result was found on Lacuna, since that paper is purely theoretical. We will implement it with the same direction estimator.

The ablation isolating our key ingredient keeps everything identical except the cut normal, which is replaced by a random direction through the center. This tests whether the gradient-direction cut, rather than just the shrinking-region bookkeeping, produces the gains.

A per-angle binary search on the radii is a baseline in its own right, discussed below.

Why not just…?

Why not just ask for scalar scores and use zeroth-order optimization? Jamieson et al. in Query Complexity of Derivative-Free Optimization show that under noise, comparisons reach the same optimal $O(1/\sqrt{T})$ rate as noisy values. The cutting plane also needs only directions. Lazzaro et al. note, however, that values carry more information per query when cost ratios are near one. So we include a scalar-feedback version, finite differences on noisy simulated IoU, as an upper reference. We report the cost ratio at which comparisons win.

Why not just do binary search on each radius separately? With a per-angle radius parameterization, each listed loss is monotone in each radius's distance to the truth when the others are held fixed. Coordinate-wise comparison search then needs only about $n\log(1/\varepsilon)$ comparisons. This is a real threat. We expect it to break in two cases: under Fourier or spline bases, where moving one coefficient moves every radius, and under realistic noise, where a single-ray change is too small to perceive. Perceptibility is modeled in the oracle by a Bradley–Terry temperature tied to the area difference. We run it in both parameterizations. If it matches us in the Fourier basis, we will restrict our claims to theory and to non-separable parameterizations.

Why not just use clicks, as in extreme-point interactive segmentation? Clicks give more information per interaction when the expert can localize errors. Deep Extreme Cut, however, fails on concave structures. Comparisons also apply where localization is the hard part, such as diffuse optic-cup margins. We do not claim comparisons beat clicks for routine annotation. The segmentation task is a testbed for star-shaped ordinal optimization, so we do not run a click baseline.

Why not just use preferential BO, given the dimension is small? In 11 to 33 dimensions it may well win at the smallest budgets. The pairwise kernel works on doubled dimension and has no knowledge of ray structure. Budget-resolved curves will show where, if anywhere, the cutting method overtakes it.

Proposed Experiments

The decisive first check is about the landscape. On Kvasir-SEG, Refuge, the ISIC 2018 lesion task, and BBBC038v1 nuclei, we fit truncated Fourier contours with K from 5 to 16 around the predicted center. We then sample random rays and segments in coefficient space and measure two rates. One is how often Jaccard, Dice and boundary-distance losses violate ray-monotonicity around the best representable contour. The other is how often they violate quasi-convexity, measured as the midpoint of two points being worse than both.

If quasi-convexity violations are rare, comparison-based normalized descent already covers the practical case, and the applied contribution shrinks to the noise-robust variant; we will report that outcome as it stands. If ray-monotonicity violations are frequent, star-shapedness does not hold approximately in these contour spaces and the proposed method loses its justification; we will measure this through the fraction of objects whose center falls outside the kernel.

The main experiment simulates annotators. Each judges contour pairs by one of IoU, Dice, Hausdorff distance, or a random increasing mixture of them, with Bradley–Terry noise at three temperatures. Changing the judgment metric changes the increasing transform but not the order structure along rays, which is the point. We report final Dice and IoU against the number of comparisons. As an external anchor for ISIC 2018, Dermoscopic Image Analysis for ISIC Challenge 2018 reports a validation Jaccard of 0.780 for a fully supervised model. For BBBC038v1 no numeric IoU is reported on Lacuna. SplineDist reports only parity with StarDist.

A synthetic suite supports the theory. It uses increasing transforms of star-convex functions built to have non-convex sublevel sets, in dimensions 5 to 50. On it we measure the quantile reached against comparisons, and check how cost scales with $n$ against the $nD^2/\varepsilon^2$ rate proved for the quasi-convex method.

A small pilot with two clinicians on Refuge optic-cup outlines, at about 100 comparisons per image, checks the one assumption the simulations cannot: that real judgments are approximately consistent with some increasing transform of a ray-monotone loss. We measure this as the rate of intransitive triples, and as agreement with the simulated annotators.