arXiv preprint ·
The Optimizer's Windfall: Bounding Hindsight Gain under Random Restrictions
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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 $ζ_i$, the gain is at most $O_r(\|A\|_F M^{(r-1)/2}σ_{\max})$, where $\|A\|_F^2$ is the sum of squared coefficients, $M=\sum_i\mathbb{E}ζ_i^2$, and $σ_{\max}^2=\max_i\mathrm{Var}(ζ_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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Asymptotically Optimal Weighted Edge Colorings via Local Bin Packing
Distributionally Robust Search: The Power of Information and the Limits of Moments
Abelian embeddings make useful promises: approximation of detrivialised equations
Adjacency Labeling Schemes of Size $\log n+O(\log\log^* n)$ for Graphs of Bounded Treewidth
Glauber Dynamics for Sampling Colorings: Rapid Mixing above $(1+1/\mathrm{e})Δ$ via Hidden Hard-Core Models
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.