3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
16
  • $\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 '15 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 '15 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 '15 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 '15 at 19:35
  • 1
    $\begingroup$ link in sections 1.4 and 2.1 seem most relevant. $\endgroup$
    – Joe Bebel
    Mar 27 '15 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.