The Optimizer's Windfall: Bounding Hindsight Gain under Random Restrictions

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 ${\zeta }_i$, the gain is at most $O_r(\Vert A{\Vert }_F{M}^{(r-1)/2}{\sigma }_{\max })$, where $\Vert A{\Vert }_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}\Vert A{\Vert }_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({\epsilon }^{-2})$ sampled variables estimates a dense Max-$r$CSP optimum within $\pm \epsilon n^r$, and this sample size is optimal. (ii) The same approach estimates MaxCut and the distance to bipartiteness within $\pm \epsilon n^2$ using $O({\epsilon }^{-4})$ nonadaptive queries and $O({\epsilon }^{-2})$ examined vertices, both optimal. (iii) We answer a question of Yufei Zhao: vertex percolation at rate $p$ preserves the max-cut fraction whenever $pe(G)/v(G)\to \infty$, and this condition is sharp. (iv) For bounded $r$-local quantum Hamiltonians of fixed local dimension, $O({\epsilon }^{-3})$ uniformly sampled particles suffice to estimate the ground-state energy within $\pm \epsilon n^r$, improving the previous $O({\epsilon }^{-6}\log (1/\epsilon ))$ bound.