PSD lifting and Unique Games integrality gaps

February 23, 2011

PSD lifting and Unique Games integrality gaps

Filed under: Math, Open question — Tags: Integrality gaps, semi-definite programming, unique games — James Lee @ 9:51 am

By now, it is known that integrality gaps for the standard Unique Games SDP (see the paper of Khot and Vishnoi or Section 5.2 of this post) can be used to obtain integrality gaps for many other optimization problems, and often for very strong SDPs coming from various methods of SDP tightening; see, for instance, the paper of Raghavendra and Steurer.

Problematically, the Khot-Vishnoi gap is rather inefficient: To achieve the optimal gap for Unique Games with alphabet size ${L}$ , one needs an instance of size ${\exp(\Omega(L))}$ . As far as I know, there is no obstacle to achieving a gap instance where the number of variables is only ${\mathrm{poly}(L)}$ .

The Walsh-Hadamard code

The Khot-Vishnoi construction is based on the Hadamard code.
(See Section 5.2 here for a complete description.) If we use ${L^2(\{-1,1\}^k)}$ to denote the Hilbert space of real-valued functions ${f : \{-1,1\}^k \rightarrow \mathbb R}$ , then the Walsh-Hadamard basis of ${L^2(\{-1,1\}^k))}$ is the set of functions of the form

$\displaystyle u_S(x) = \prod_{i \in S} x_i,$

where ${S \subseteq \{1,2,\ldots,k\}}$ .

Of course, for two such sets ${S \neq T}$ , we have the orthogonality relations,

$\displaystyle \langle u_S, u_T \rangle = 0.$

In their construction, the variables are essentially all functions of the form ${f : \{-1,1\}^k \rightarrow \{-1,1\}}$ , of which there are ${2^{2^k}}$ , while there are only ${2^k}$ basis elements ${\{u_S\}_{S \subseteq [k]}}$ which act as the alphabet for the underlying Unique Games instance. This is what leads to the exponential relationship between the number of variables and the label size.

A PSD lifting question

In an effort to improve this dependence, one could start with a much larger set of nearly orthogonal vectors, and then somehow lift them to a higher-dimensional space where they would become orthogonal. In order for the value of the SDP not to blow up, it would be necessary that this map has some kind of Lipschitz property. We are thus led to the following (possibly naïve) question.

Let ${C(d,\varepsilon)}$ be the smallest number such that the following holds. (Here, ${S^{d-1} \subseteq \mathbb R^d}$ denotes the ${(d-1)}$ -dimensional unit sphere and $S(L^2)$ denotes the unit-sphere of $L^2$ .)

There exists a map ${F : S^{d-1} \rightarrow S(L^2)}$ such that ${\|F\|_{\mathrm{Lip}} \leq C(d,\varepsilon)}$ and whenever ${u,v \in \mathbb R^d}$ satisfy ${|\langle u,v\rangle| \leq \varepsilon}$ , we have ${\langle F(u), F(v)\rangle = 0}$ .

(Recall that $\|F\|_{\mathrm{Lip}} = \sup_{x \neq y \in S^{d-1}} \|F(x)-F(y)\|/\|x-y\|$ .)

One can show that

$\displaystyle C(d,\varepsilon) \lesssim \frac{\sqrt{d}}{1-\varepsilon}$

by randomly partitioning ${S^{d-1}}$ so that all vectors satisfying ${|\langle u,v\rangle| \leq \varepsilon}$ end up in different sets of the partition, and then mapping all the points in a set to a different orthogonal vector.

My question is simply: Is a better dependence on ${d}$ possible? Can one rule out that ${C(d,\varepsilon)}$ could be independent of ${d}$ ? Note that any solution which randomly maps points to orthogonal vectors must incur such a blowup (this is essentially rounding the SDP to an integral solution).

About these ads

Comments (3)

3 Comments »

This may be a proof that the Lipschitz constant $C(d,\varepsilon)$ must depend on $d$ .

Call a function $f:[-1,1]\to \mathbb R$ positive definite on $\mathbb S^d$ if for every $n$ and every Gram matrix $A = (a_{i,j})$ of $n$ points on $\mathbb S^d$ , the matrix $(f(a_{i,j}))$ is positive semi-definite.

A map $F_d:\mathbb S^d\to \mathbb S(L^2)$ can be assumed to come from a positive definite function $f :[-1,1]\to \mathbb R$ on $\mathbb S^d$ , in the sense that $\langle F(u),F(v)\rangle = f(\langle u,v \rangle)$ for all $u,v\in\mathbb S^d$ . This should follow by symmetrizing $\mathbb F_d$ by isometries of $\mathbb S^d$ .

Specifically, we redefine $\mathbb F_d(u)$ by the direct integral $\int^\oplus F_d(\rho u) \;d \rho$ , where the integral is over the orthogonal group $O(d+1)$ . I believe this step can be done, though I didn’t check the details carefully.

Next, consider a sequence of maps $f_d: [-1,1]\to \mathbb R$ positive definite on $\mathbb S^d$ . Passing to a subsequence, they converge pointwise to a function $f:[-1,1]\to \mathbb R$ positive definite on the Hilbert sphere $\mathbb S^\infty$ . Any such function $f$ must be analytic in the open interval $(-1,1)$ , thanks to a result of Christensen and Ressel
http://www.ams.org/journals/tran/1978-243-00/S0002-9947-1978-0502895-2/S0002-9947-1978-0502895-2.pdf.

The orthogonality assumption about $F_d$ (and hence $f_d$ ) implies the limit function $f$ vanishes identically on $(-1,1)$ . Hence the sequence of maps $F_d$ cannot share a common Lipschitz constant independent of dimension $d$ .

The drawback of this proof is the lack of an effective lowerbound on the dependence.

Comment by siuon — March 28, 2011 @ 4:48 pm
Hi, this certainly appears to be a correct proof that $C(d,\varepsilon) \to \infty$ as $d \to \infty$ , and the final conclusion about analycity of $f$ follows directly from Schoenberg’s characterization. Very nice.

I suspect that a quantitative bound can be obtained from the characterization for positive definite functions on $\mathbb S^{d-1}$ ; see here.

Comment by James Lee — April 1, 2011 @ 4:34 pm
[...] On Chan solved the PSD Lifting question in the comments of the post. Since then, the invention of the short code gave a much more [...]

Pingback by Open question recap | tcs math - some mathematics of theoretical computer science — February 25, 2013 @ 12:28 pm

RSS feed for comments on this post. TrackBack URI

	Nguyen Van Phuc on No frills proof of higher-orde…
	Nguyen Van Phuc on No frills proof of higher-orde…
	Nguyen Van Phuc_Viet… on No frills proof of higher-orde…
	Nguyen Van Phuc_Viet… on No frills proof of higher-orde…
	http://iwriteadirtyb… on Expanders from the action of…

tcs math – some mathematics of theoretical computer science

February 23, 2011

PSD lifting and Unique Games integrality gaps

Like this:

3 Comments »

Leave a Reply Cancel reply

Recent Comments

Recent Posts

Links

Math & TCS blogs

Top Posts

Archives

Follow “tcs math - some mathematics of theoretical computer science”