Numerical precision in sum-of-squares method?

Question

I have been reading a bit about the sum-of-squares method (SOS) from the survey of Barak & Steurer and the lecture notes of Barak. In both cases they sweep issues of numerical accuracy under the rug.

From my (admittedly limited) understanding of the method, the following should be true:

Given any system of polynomial equalities $E$ over real-valued variables $x \in \mathbb{R}^n$, where all parameters are $O(1)$ ($n$, $|E|$, and degree of each constraint), the degree-"$2n$" ($=O(1)$) SOS method finds a satisfying assignment of the variables or proves none exists in $O(1)$ time.

My first question is whether the above claim is true (is there a naive argument that doesn't use SOS to solve this?). The second question is where numerical accuracy fits in. If I want to get an assignment that satisfies all constraints to within additive $\varepsilon$ accuracy, how does the runtime depend on $1/\varepsilon$? In particular, is it polynomial?

The motivation for this is to, say, apply a divide-and-conquer approach on a large system until the base case is an $O(1)$-size system.

EDIT: From Barak-Steurer, it appears that the "degree $l$ sum-of-squares algorithm" on p.9 (and the paragraphs leading up to it) all define problems for solutions over $\mathbb{R}$, and in fact the definition of a pseudo-distribution in section 2.2 is over $\mathbb{R}$. Now I am seeing from Lemma 2.2, however, that one is not guaranteed a solution/refutation at degree $2n$ without binary variables.

So I can refine my question a little bit. If your variables are not binary, the worry is that the sequence of outputs $\varphi^{(l)}$ is not finite (maybe not even monotonic increasing?). So the question is: is $\varphi^{(l)}$ still increasing? And if so, how far you have to go to get additive accuracy $\varepsilon$?

Though this likely does not change anything, I happen to know my system is satisfiable (there is no refutation of any degree), so I am really just concerned about how large $l$ needs to be. Finally, I am interested in a theoretical solution, not a numerical solver.

Answer 1

Here is Boaz Barak's comment on the issue:

We do sweep numerical accuracy under the rug -- the more "traditional" SOS literature of Parrilo, Lasserre etc.. deals with these issues (e.g., see Monique Laurent's surveys and the references therein). It is known that that the hierarchy is monotone (it's not hard to see that a degree $l$ psuedo-distribution is in particular a degree $l-1$ one), and that it will converge in finite degree for any fixed set of equations (this is the Positivstellensatz). The exact degree could vary. Generally, if all the coefficients of the polynomials are bounded and you are trying to distinguish between the case that there is a solution and the case that in any assignment one of the equations is off by $\epsilon$, then one could discretize this to a $\delta$-net for $\delta$ related to the number of variables, degree of equations, and $\epsilon$, and then (assuming the net is sufficiently "nice" and "cube like") the degree required should be roughly log the size of the net.

Answer 2

I think my answer is probably insufficient, but it remains for completeness' sake (although see Boaz's comments below for probably a better answer)

When we limit ourselves to boolean variables, the claim can be seen when $(x_i^2-1) \in E$ for all $i \in[n]$ with the observation that degree $2n$ pseudo-distributions are actual distributions, that is, suppose you have a pseudo-distribution $\mu(x)$ over solutions $x$ of your polynomial equalities $E$ satisfying:

$\sum_{ x \in \{-1,1\}^n} \mu(x)$ and $\sum_{x\in\{-1,1\}^n} \mu(x) p^2(x)\ge0$ for all polynomials $p$ with degree at most $n$

But degree $n$ polynomials include the indicator polynomial (for example, $x_1 = 1, x_2=-1, x_3=1$ has $2^{-3}(1+x_1)(1-x_2)(1+x_3)$ which is all-zero elsewhere and 1 on that assignment). So $\mu(x) \ge 0$ for all $x\in\{-1,1\}^n$, so we conclude $\mu$ is an actual distribution over the solutions of $E$. Degree $\ell$ pseudo-distributions can be found by using semidefinite programming to find an associated degree $\ell$ pseudo-expectation operator in $n^{O(\ell)}$ time, so we can find the actual distribution $\mu$ in time $n^{O(n)}$ by using that pseudo-expectation (now an actual expectation) to find all the moments of $\mu$.

So, if $|E| = O(1)$, then you can find a distribution of solutions to $E$ in $O(1)$ time. Of course, brute force search guarantees the same.

However, if the solutions are not necessarily boolean, then degree-$2n$ pseudo-expectations are not sufficient to find a distribution over solutions. As can be seen above, the proof that degree $2n$ pseudo-distributions are actual distributions depends on the fact that degree $n$ polynomials are sufficient to 'pick out' individual assignments, which is not true more generally. Another way of viewing it is that boolean-variable polynomials are considered $\mod(x_i^2)$, so the degree of every monomial is at most $n$.

For example, one could consider replacing every binary variable with a 4-ary variable, say by including $(x_i^2-1)(x_i^2-4) \in E$. Then you would have to have a degree $4n$ pseudo-expectation in order to guarantee recovery of a distribution over solutions.

Now, for theoretical guarantees, it seems like approximating a root of a system of polynomals is also known as Smale's 17th problem, and apparently there is a randomized (Las Vegas) polynomial time algorithm that solves this - see http://arxiv.org/pdf/1211.1528v1.pdf. Note that this seems to be in the Blum-Shub-Smale model, so real operations are the primitive. I am not sure if this gives the guarantee that you need.