Optimizing restricted problems with guaranteed accuracy bounds
The Optimizer's Windfall: Bounding Hindsight Gain under Random Restrictions
Data Structures and AlgorithmsDiscrete Mathematics
Summary
This paper looks at what happens when you randomly remove parts of a problem and then try to solve it again. The authors studied how much extra benefit you get by optimizing after seeing the restrictions, and they found mathematical limits on this gain. They used these limits to show how well you can estimate the best solution for certain complex optimization problems just by looking at a small random sample. Their results also help answer questions about preserving properties in random subgraphs and estimating energies in quantum systems.
What this means in practice
- •For algorithm engineers: Estimate dense Max-rCSP optima within tight error bounds using only a randomized subset of variables, minimizing required data for approximations.
- •For quantum computing developers: Estimate ground-state energies of bounded local quantum Hamiltonians efficiently from a small uniform sample of particles, improving resource use for simulations.
Authors
Xiaohui Bei, Wenhao Wu
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.