Greedy sign-based box splitting: exact solvable classes, sharp thresholds and order-oracle complexity

Abstract

Greedy box splitting reads gradient signs at the centre and retains one smaller box. Its summable travel budget makes an incorrect exclusion irreversible. We determine when this geometry is safe. Halving is minimax optimal in the sign-vector oracle model on a coordinatewise sign-consistent class that need not be convex. A dimensionless sign defect yields a sharp scalar envelope, attained by one smooth convex potential; a three-dimensional trajectory ends farther from the target than its initial radius. For quadratics, universal convergence with aspect $w$ and contraction beta holds exactly when the weighted absolute row defect is at most $(2 \beta - 1)$. Perron weights minimise this defect. Adaptive half-sizes avoid initial enlargement and, under persistent error, converge to an exact capped fixed-point limit. For binary comparisons, an independent probe fraction $q$ permits universal localisation on common-target monotone sections exactly when $(q \leq 2 \beta - 1)$; coupled probes give the sharp threshold $2/3$. Matching information bounds distinguish comparisons from sign-vector queries. Error bands give finite-time guarantees and sharp residual floors. Extensions and reproducible experiments identify the assumptions and costs of freezing, smoothing, voting, multistart and random-matrix certificates.