Metraipolis › archive › dc_be4d7fe9dceb
Greedy sign-based box splitting: exact solvable classes, sharp thresholds and order-oracle complexity — arXiv:2609.37444
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.37444
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T18:02:10.176Z
- SHA-256 of the archived text
bf86d9a54df6a4ae5e65f9db5a150c81b935246f1ed790f1e3ec5b352a1adb4b- Stable URL of this page
https://metraipolis.com/documento/dc_be4d7fe9dceb
How to cite
Greedy sign-based box splitting: exact solvable classes, sharp thresholds and order-oracle complexity — arXiv:2609.37444 — arXiv (en), https://arxiv.org/abs/2609.37444 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_be4d7fe9dceb (Metraipolis archive dc_be4d7fe9dceb, sha256 bf86d9a54df6a4ae5e65f9db5a150c81b935246f1ed790f1e3ec5b352a1adb4b)
BibTeX
@misc{dcbe4d7fe9dceb,
title = {Greedy sign-based box splitting: exact solvable classes, sharp thresholds and order-oracle complexity — arXiv:2609.37444},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.37444},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_be4d7fe9dceb; sha256 bf86d9a54df6a4ae5e65f9db5a150c81b935246f1ed790f1e3ec5b352a1adb4b},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.37444. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-30 in math.OC). Categorie arXiv: Optimization and Control (math.OC). Pagina del lavoro: https://arxiv.org/abs/2609.37444 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-07T17:35:03.562Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-30?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).