We consider the sum-of-squares hierarchy of approximations for the problem of minimizing a polynomial $f$ over the boolean hypercube $\mathbb{ B}^{ n}=\{ 0,1\}^n$. This hierarchy provides for each integer $r \in \mathbb{ N}$ a lower bound $f_{ (r)}$ on the minimum $f_{ \min}$ of $f$, given by the largest scalar $\lambda$ for which the polynomial $f - \lambda$ is a sum-of-squares on $\mathbb{ B}^{ n}$ with degree at most $2r$. We analyze the quality of these bounds by estimating the worst-case error $f_{ \min} - f_{ (r)}$ in terms of the least roots of the Krawtchouk polynomials. As a consequence, for fixed $t \in [0, 1/2]$, we can show that this worst-case error in the regime $r \approx t \cdot n$ is of the order $1/2 - \sqrt{ t(1-t)}$ as $n$ tends to $\infty$. Our proof combines classical Fourier analysis on $\mathbb{ B}^{ n}$ with the polynomial kernel technique and existing results on the extremal roots of Krawtchouk polynomials. This link to roots of orthogonal polynomials relies on a connection between the hierarchy of lower bounds $f_{ (r)}$ and another hierarchy of upper bounds $f^{ (r)}$, for which we are also able to establish the same error analysis. Our analysis extends to the minimization of a polynomial over the $q$-ary cube $(\mathbb{ Z}/q\mathbb{ Z})^{ n}$.
Categories: math.OC