A. Gornov

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...