In the context of the SOS hierarchy papers, it seems that a "level-r psuedo expectation functional" is the same as an operator taking expectations of functions just that this one has the restriction that expectation of a square of a function is guaranteed to be zero only when the function is a polynomial of degree $\leq \frac{r}{2}$

  • Is the above right?

  • So the polynomials on which one would take the "level-r pseudo expectation functional" are what are to be called "level-r fictitious random variable" ?

  • Conventionally in optimization questions one would say something like "maximize $P_0$ given that $P_i^2=0$ for $i =1,2,..,m$" but the ``r-round SOS SDP relaxation" of this same question would be to choose a "level-r pseudo expectation functional" say $\tilde{E}$ and say "maximize $\tilde{E}[P_0]$ given that $\tilde{E}[P_i^2]=0$ for $i =1,2,..,m$ for $deg(P_i) \leq \frac{r}{2}$"

Is the above right? And if so then how is a specific $\tilde{E}$ chosen to do the relaxation?


1 Answer 1


The degree $r$ pseudo-expectation operator operates on polynomials of at most degree $r$. Since the pseudo-expectation operator is positive semidefinite, we're guaranteed that the square of a polynomial (or sum of squares of polynomials) always has nonnegative pseudo-expectation.

Also, if we have a system of polynomial equations $\{p_i = 0\}$ of degree at most $r/2$, then we can construct the pseudo-expectation operator to be such that the pseudo-expectation $\tilde{\mathbb{E}}[p_i q] = 0$ for all polynomials $q$ of sufficiently small degree.

The intuition should be that if $\{p_i=0\}$ has a feasible solution, then $\mathbb{E}[ p_i(x) ] = 0$ where $x$ is a random feasible solution to $\{p_i = 0\}$ and $\mathbb{E}$ is the "actual" expectation operator.

But of course, it is not possible for us to directly sample this distribution. Instead we play a sort of game where we assume that we can evaluate various expectations of polynomials $\mathbb{E}[p]$ (that is, moments) of this distribution over feasible solutions, and 'combine' them together to get a feasible solution.

But of course, we don't really have those moments, either, because again it's too hard to sample the distribution. So we instead use the SoS algorithm to find a pseudo-distribution and pseudo-expectation operator that we can evaluate to get pseudo-moments $\tilde{\mathbb{E}}[p]$, and feed the pseudo-moments to the same 'combiner' algorithm as if they were actual moments, and sometimes we get an answer out that's actually not half bad.

Edit: It is better to consider the sum of squares SDP as optimizing a particular pseudo-expectation; for example, in Goemans-Williamson, we maximize $\tilde{\mathbb{E}}[ \langle x, Lx \rangle]$ where $L$ is the Laplacian and this corresponds to maximizing the value of our cut.

  • $\begingroup$ Can you refer to a typical example where such an SOS algorithm has been shown? (Are you saying that finding an $\tilde E$ is also a part of the question? I thought one fixes a $\tilde E$ beforehand and then does the optimization or proves its infeasible) I would like to see a bare-bones example of doing such a thing! $\endgroup$
    – user6818
    Mar 27, 2015 at 15:26
  • $\begingroup$ When you say $\{ p_i =0 \}$ has or doesn't have a feasible solution are you referring to the contraints being compatible or not? $\endgroup$
    – user6818
    Mar 27, 2015 at 15:30
  • $\begingroup$ The Goemans Williamson algorithm for max cut seems to be the prototypical example (Boaz Barak has an excellent set of notes on SoS). Yes, finding such $\tilde{\mathbb{E}}$ is the principal goal of the SoS algorithm. Note that the actual expectation operator $\mathbb{E}[p(x)]$ on a polynomial of $x$, a random solution to $\{p_i=0\}$, also depends greatly on the actual instance you're dealing with (because the set of solutions may vary) A feasible solution to $\{p_i = 0\}$ is an assignment of real values to variables such that every polynomial $p_i$ evaluates to $0$. $\endgroup$
    – Joe Bebel
    Mar 27, 2015 at 19:11
  • $\begingroup$ Thanks! I have been seeing those Boaz-Barak notes. (1) Can you point what in that notes looks like "solving a SOS (hierarchy?)" ? (2) How is the GW Max-Cut SDP an example of "r-round SOS SDP relaxation"? (3) In most analysis that I see in those lecture notes or elsewhere I don't see anyone trying to find this "$\tilde E$". It seems to be something that is implicitly floating in the background. Can you point out something specific in BB's notes? $\endgroup$
    – user6818
    Mar 27, 2015 at 19:35
  • 1
    $\begingroup$ link in sections 1.4 and 2.1 seem most relevant. $\endgroup$
    – Joe Bebel
    Mar 27, 2015 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.