Is a degree-$d$ pseudo distribution always a relaxation? The optimization problem we are generally concerned with looks like the following,
\begin{eqnarray*}
&amp;\inf \{ p(x) \vert x \in K\} \\
&amp;K = \{ x \in \mathbb{R}^n \vert q_i(x) \geq 0, i = 1,..,m \} 
\end{eqnarray*}

where $p(x)$ is some polynomial objective function and $q_i(x)$ are polynomial constraints. 

One can look at this corresponding question, 

\begin{eqnarray*} 
&amp;\inf_D \{ \tilde{\mathbb{E}_D} [p] \} \\
&amp;s.t \\
&amp;D : \{ 0,1\} ^n \rightarrow \mathbb{R} \\
&amp;\sum_{x \in \{0,1\}^n} D(x) = 1 \\
&amp; \forall u \in SOS_d \\ 
&amp;\tilde{\mathbb{E}}_D [u] \geq 0 \\
&amp;\tilde{\mathbb{E}}_D[q_i] \geq 0 
\end{eqnarray*} 

Here we use the ``pseudo-expectation" notation" whereby we have for any function $f$, $\tilde{\mathbb{E}}_D[f] = \sum_{x \in \{ 0,1\}^n } D(x)f(x)$ And $SOS_d$ is the cone of all real polynomials in $n-$variables which can be written as a sum of squares of polynomials of degree at most $\frac{d}{2}$


Is it clear that for all $d$ the later is a relaxation of the former? 

If we restrict the polynomials to be valued on the hypercube $\{0,1\}^n$ then I can think of an argument which shows that the latter is a relaxation of the former by going through an intermediate Lassere relaxation. But if the polynomials are valued on the whole of $\mathbb{R}^n$ (as written above) then my above argument works only if $n^d &lt; 2^n$. 
Is there a proof that if one keeps increasing the $d$ then at $d=n$ the later will exactly hit the infimum being searched for in the first?
To see that this is a relaxation, all you have to check is that each feasible solution to the first problem gives rise to a feasible solution to the second problem. All you have to do is, given $x \in K$, take an actual distribution $D$ concentrated on $x$. (This only works if in the definition of $K$ you replace $\mathbb{R}^n$ with $\{0,1\}^n$; your formulation doesn't make too much sense.)

When $d = n$, the conditions guarantee that $D$ is an actual distribution. If the objective function $p$ is concave then the optimal distributions are singletons, and so both programs have the same value. Otherwise it could be that for some distribution $D$ supported on $K$ it holds that $\mathbb{E}_{X\sim D}[p(X)] &lt; \min_x p(x)$.