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 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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.37444
curl -X POST /api/v1/records/arxiv/2609.37444/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.37444/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'