Preprint
Sep 2026
Greedy sign-based box splitting: exact solvable classes, sharp thresholds and order-oracle complexity
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. Anikin, A. Gornov, T. Zarodnyuk et al.
· 0 citations