Metraipolis › archive › dc_fec219b207db
The Optimizer's Windfall: Bounding Hindsight Gain under Random Restrictions — arXiv:2611.03468
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.03468
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T11:38:33.647Z
- SHA-256 of the archived text
558fdc5b1af7a22c7c6569bc6af2319a7af6813606e638601aec5b637f68736e- Stable URL of this page
https://metraipolis.com/documento/dc_fec219b207db
How to cite
The Optimizer's Windfall: Bounding Hindsight Gain under Random Restrictions — arXiv:2611.03468 — arXiv (en), https://arxiv.org/abs/2611.03468 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fec219b207db (Metraipolis archive dc_fec219b207db, sha256 558fdc5b1af7a22c7c6569bc6af2319a7af6813606e638601aec5b637f68736e)
BibTeX
@misc{dcfec219b207db,
title = {The Optimizer's Windfall: Bounding Hindsight Gain under Random Restrictions — arXiv:2611.03468},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.03468},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fec219b207db; sha256 558fdc5b1af7a22c7c6569bc6af2319a7af6813606e638601aec5b637f68736e},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.03468. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Suppose an optimization problem is randomly restricted, independently on each variable, and re-optimized after the restriction is revealed. For multilinear objectives, every fixed solution is unbiased after rescaling, but re-optimizing introduces an upward bias. We bound this excess, the hindsight gain, over products of arbitrary compact local domains in Euclidean unit balls. For interactions $A=(A_e)_e$ among $r$ distinct variables and independent random weights $\zeta_i$, the gain is at most $O_r(\|A\|_F M^{(r-1)/2}\sigma_{\max})$, where $\|A\|_F^2$ is the sum of squared coefficients, $M=\sum_i\mathbb{E}\zeta_i^2$, and $\sigma_{\max}^2=\max_i\mathrm{Var}(\zeta_i)$; only second moments are needed. Under uniform retention with probability $p$, we sharpen this to $O_r(p^{r-1/2}\sqrt{1-p}\,n^{(r-1)/2}\|A\|_F)$, which is tight for every fixed $r$ and $p\in(0,1)$. Our proof combines a comparison principle along a single support direction with tensor projection, vector contraction, and repeated thinning. Applications: (i) For fixed arity and alphabet size, solving the subproblem induced by $O(\varepsilon^{-2})$ sampled variables estimates a dense Max-$r$CSP optimum within $\pm\varepsilon n^r$, and this sample size is optimal. (ii) The same approach estimates MaxCut and the distance to bipartiteness within $\pm\varepsilon n^2$ using $O(\varepsilon^{-4})$ nonadaptive queries and $O(\varepsilon^{-2})$ examined vertices, both optimal. (iii) We answer a question of Yufei Zhao: vertex percolation at rate $p$ preserves the max-cut fraction whenever $p\,e(G)/v(G)\to\infty$, and this condition is sharp. (iv) For bounded $r$-local quantum Hamiltonians of fixed local dimension, $O(\varepsilon^{-3})$ uniformly sampled particles suffice to estimate the ground-state energy within $\pm\varepsilon n^r$, improving the previous $O(\varepsilon^{-6}\log(1/\varepsilon))$ bound.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Discrete Mathematics (cs.DM); Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2611.03468 — 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-11-03T11:05:22.366Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).