<p>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. </p>

<p>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.</p>

<p>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. </p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2015-03-27T15:26:08.507Z
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!
user6818
CC BY-SA 3.0
2015-03-27T15:30:51.623Z
When you say $\{ p_i =0 \}$ has or doesn't have a feasible solution are you referring to the contraints being compatible or not?
user6818
CC BY-SA 3.0
2015-03-27T19:11:32.530Z
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$.
Joe Bebel
CC BY-SA 3.0
2015-03-27T19:35:21.543Z
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?
user6818
CC BY-SA 3.0
2015-03-27T20:14:09.447Z
Note that the Goemans Williamson algorithm can be seen more directly as an explicit SDP, so not all sources will explain how it can be seen as using a SoS algorithm.
Joe Bebel
CC BY-SA 3.0
2015-03-27T20:15:04.583Z
[link](http://www.boazbarak.org/sos/files/all-notes.pdf) in sections 1.4 and 2.1 seem most relevant.
Joe Bebel
CC BY-SA 3.0
2015-03-28T21:27:11.980Z
On page 26 just below throrem 2.1 he says this "running the degree-2 SOS algorithm on... yields a valid pseudo-distribution" Can you explain as to what algorithm is he referring to? Where is he actually constructing this degree-2 pseudo distribution?
user6818
CC BY-SA 3.0
2015-03-28T21:30:08.790Z
Which part of his argument around section 2.1 corresponds to "running the degree-2 SOS algorithm on..."?
user6818
CC BY-SA 3.0
2015-03-29T00:48:48.917Z
First, assume only boolean (i.e. $\{0,1\}$ or $\{-1,1\}$) solutions, and note pseudo-distributions exactly correspond to pseudo-expectation operators. Since pseudo-expectations are positive semidefinite linear operators, we can find them with semidefinite programming (and thus construct the pseudo-distribution as well)
Joe Bebel
CC BY-SA 3.0
2015-03-29T01:12:04.157Z
But which part of his Theorem 2.1 correspond to "running the degree-2 SOS" algorithm? Whats the point of doing a SOS rewriting of GW if one is still going to have to tun a SDP in the background?
user6818
CC BY-SA 3.0
2015-03-29T03:20:17.427Z
Theorem 2.1 takes the output of the SOS algorithm (a pseudo-distribution) and finds a cut. This is equivalent to viewing GW as a SDP with rounding procedure; it is the same algorithm, just a different way of viewing it.
Joe Bebel
CC BY-SA 3.0
2015-03-29T04:47:03.950Z
True! Thats what I am trying to get at! So the complete algorithm will also need a step to generate that degree/level 2 pseudo-distribution to do anything! How does one generate that? Where is this SOS algorithm that would give me this level-2 pseudo distribution?
user6818
CC BY-SA 3.0
2015-03-29T05:11:31.460Z
The pseudo-expectation operator is a positive semidefinite linear operator satisfying $\tilde{\mathbb{E}}[1]=1$ and $\tilde{\mathbb{E}}[p_i q]=0$, which are linear constraints, and the space of such $\tilde{\mathbb{E}}$ is convex, so semidefinite programming will find us one. Pseudo-expectations/distributions are related in the same way actual ones are.
Joe Bebel
CC BY-SA 3.0
2015-03-29T16:39:28.093Z
So one would still need need to run a SDP to find this pseudo-E ? Then what is the whole advantage of 2.1? If I still need to solve a SDP to find the pseudo-E then where exactly is SOS giving the advantage here?
user6818
CC BY-SA 3.0
2015-03-29T22:37:21.447Z
I think that is a bigger question than can be addressed in a comment, but, consider the advantages of viewing something a divide-and-conquer algorithm or greedy algorithm or dynamic-programming algorithm. It is a framework for possibly solving many problems using similar techniques.
Joe Bebel
CC BY-SA 3.0
2015-03-30T01:03:18.447Z
Okay! So I asked this more specific question here, http://cstheory.stackexchange.com/questions/30960/the-goemans-williamson-algorithm-in-the-sos-framework Do write in there! :)
user6818
CC BY-SA 3.0
2015-03-27T08:57:21.290Z
2015-03-27T21:45:32.263Z
2015-03-27T21:45:32.263Z
Joe Bebel
<p>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}$ </p>

<ul>
<li><p>Is the above right? </p></li>
<li><p>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" ?</p></li>
<li><p>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}$"</p></li>
</ul>

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

<cc.complexity-theory><approximation-hardness><semidefinite-programming><unique-games-conjecture>
What is a "level-r pseudo expectation functional"?
user6818
# What is a "level-r pseudo expectation functional"?

(Asked by: username_0 on 2015-03-27)

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?

**Tags:** cc.complexity-theory, approximation-hardness, semidefinite-programming, unique-games-conjecture

---

## 1 answers

### Answer by username_1 on 2015-03-27. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_0**: 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!  
> **username_0**: When you say $\{ p_i =0 \}$ has or doesn't have a feasible solution are you referring to the contraints being compatible or not?  
> **username_1**: 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$.  
> **username_0**: 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?  
> **username_1**: Note that the Goemans Williamson algorithm can be seen more directly as an explicit SDP, so not all sources will explain how it can be seen as using a SoS algorithm.  
> **username_1**: [link](http://www.boazbarak.org/sos/files/all-notes.pdf) in sections 1.4 and 2.1 seem most relevant.  
> **username_0**: On page 26 just below throrem 2.1 he says this "running the degree-2 SOS algorithm on... yields a valid pseudo-distribution" Can you explain as to what algorithm is he referring to? Where is he actually constructing this degree-2 pseudo distribution?  
> **username_0**: Which part of his argument around section 2.1 corresponds to "running the degree-2 SOS algorithm on..."?  
> **username_1**: First, assume only boolean (i.e. $\{0,1\}$ or $\{-1,1\}$) solutions, and note pseudo-distributions exactly correspond to pseudo-expectation operators. Since pseudo-expectations are positive semidefinite linear operators, we can find them with semidefinite programming (and thus construct the pseudo-distribution as well)  
> **username_0**: But which part of his Theorem 2.1 correspond to "running the degree-2 SOS" algorithm? Whats the point of doing a SOS rewriting of GW if one is still going to have to tun a SDP in the background?  
> **username_1**: Theorem 2.1 takes the output of the SOS algorithm (a pseudo-distribution) and finds a cut. This is equivalent to viewing GW as a SDP with rounding procedure; it is the same algorithm, just a different way of viewing it.  
> **username_0**: True! Thats what I am trying to get at! So the complete algorithm will also need a step to generate that degree/level 2 pseudo-distribution to do anything! How does one generate that? Where is this SOS algorithm that would give me this level-2 pseudo distribution?  
> **username_1**: The pseudo-expectation operator is a positive semidefinite linear operator satisfying $\tilde{\mathbb{E}}[1]=1$ and $\tilde{\mathbb{E}}[p_i q]=0$, which are linear constraints, and the space of such $\tilde{\mathbb{E}}$ is convex, so semidefinite programming will find us one. Pseudo-expectations/distributions are related in the same way actual ones are.  
> **username_0**: So one would still need need to run a SDP to find this pseudo-E ? Then what is the whole advantage of 2.1? If I still need to solve a SDP to find the pseudo-E then where exactly is SOS giving the advantage here?  
> **username_1**: I think that is a bigger question than can be addressed in a comment, but, consider the advantages of viewing something a divide-and-conquer algorithm or greedy algorithm or dynamic-programming algorithm. It is a framework for possibly solving many problems using similar techniques.  
> **username_0**: Okay! So I asked this more specific question here, http://cstheory.stackexchange.com/questions/30960/the-goemans-williamson-algorithm-in-the-sos-framework Do write in there! :)  

---

