CS 294 Lecture 14: ARV Analysis, Part 3

In which we complete the analysis of the ARV rounding algorithm

We are finally going to complete the analysis of the Arora-Rao-Vazirani rounding algorithm, which rounds a Semidefinite Programming solution of a relaxation of sparsest cut into an actual cut, with an approximation ratio {O(\sqrt {\log |V|})}.

In previous lectures, we reduced the analysis of the algorithm to the following claim.

Lemma 1 Let {d(\cdot, \cdot)} be a semi-metric over a set {C} such that {d(u,v) \leq 1} for all {u,v \in C}, let {\{ {\bf x}_v \}_{v \in C}} be a collection of vectors in {{\mathbb R}^m}, such that {d(i,j) := ||{\bf x}_u - {\bf x}_v ||^2} is a semimetric, let {{\bf g}} be a random Gaussian vector in {{\mathbb R}^m}, define {Y_v := \langle {\bf g}, {\bf x}_v \rangle}, and suppose that, for every {{\bf g}}, we can define a set of disjoint pairs {M_{\bf g}} such that, with probability 1 over {{\bf g}},

\displaystyle  \forall \{ u,v \} \in M_{\bf g}. \ | Y_u - Y_v | \geq \sigma \ \wedge \ d(u,v) \leq \ell

and

\displaystyle  \forall u\in C. \ \mathop{\mathbb P} [ \exists v. \{ u,v\} \in M_{\bf g} ] \geq \epsilon

Then

\displaystyle  \ell \geq \Omega_{\epsilon, \sigma} \left( \frac 1 {\sqrt{\log |C|}} \right)

1. An Inductive Proof that Gives a Weaker Result

In this section we will prove a weaker lower bound on {\ell}, of the order of {\frac 1 {(\log |C|)^{\frac 23}}}. We will then show how to modify the proof to obtain the tight result.

We begin will the following definitions. We define the ball or radius {r} centered at {u} as

\displaystyle  B(u,r) := \{ v \in C. \ d(u,v) \leq r \}

We say that a point {u\in C} has the {(p,r,\delta)}-Large-Projection-Property, or that it is {(p,r,\delta)}-LPP if

\displaystyle  \mathop{\mathbb P} \left [ \max_{v \in B(u,r)} Y_v - Y_u \geq p \right] \geq \delta

Lemma 2 Under the assumptions of Lemma 1, there is a constant {c_4 >0} (that depends only on {\epsilon} and {\sigma}) such that for all {t \leq c_4 \cdot \frac 1 {\sqrt \ell}}, at least {\left( \frac \epsilon 8 \right)^{t} \cdot |C|} elements of {C} have the {\left( t \frac \sigma 2 , t \ell, 1- \frac \epsilon 4 \right)} Large Projection Property.

Proof: We will prove the Lemma by induction on {t}. We call {C_t} the set of elements of {C} that are {\left( t \frac \sigma 2 , t \ell, 1- \frac \epsilon 4 \right)}-LPP

Let {M'_{\bf g}} be the set of ordered pairs {(u,v)} such that {\{ u,v\} \in M_{\bf g}} and {Y_v > Y_u}, and hence {Y_v - Y_u \geq \sigma}. Because {{\bf g}} and {-{\bf g}} have the same distribution, we have that, for every {u\in C}, there is probability {\geq \epsilon /2} that there is a {v\in C} such that {(v,u) \in M'_{\bf g}} (a fact that we will use in the inductive step).

For the base case {t=0} there is nothing to prove.

For the inductive case, define the function {F: C_t \rightarrow C} (which will be a random variable dependent on {{\bf g}}) such that {F(v)} is the lexicographically smallest {w \in B(v, t \ell) } such that {Y_w- Y_v \geq \sigma} if such a {w} exists, and {F(v) = \bot} otherwise. The definition of {C_t} is that {\mathop{\mathbb P} [ F(v) \neq \bot] \geq 1-\epsilon/4} for every {v\in C_t}, and the inductive assumption is that {|C_t| \geq |C| \cdot (\epsilon/8)^{t}} .

By a union bound, for every {v\in C_t}, there is probability at least {\epsilon/4} that there is an {u\in C} such that {(u,v) \in M'_{\bf g}} and {F(v)= w \neq \bot}. In this case, we will define {F'(u) = w}, otherwise {F'(u) = \bot}.

Note that the above definition is consistent, because {M'_{\bf g}} is a set of disjoint pairs, so for every {u} there is at most one {v} that could be used to define {F'(u)}. We also note that, if {F'(u) = w \neq \bot}, then

\displaystyle  Y_w - Y_u \geq t \cdot \frac \sigma 2 + \sigma \ ,

\displaystyle  d(u,w) \leq (t+1) \cdot \ell

and

\displaystyle  \sum_{u \in C} \mathop{\mathbb P} [ F'(u) \neq \bot] = \sum_{v \in C_t} [ F(v) \neq \bot \wedge \exists u. (u,v) \in M'_{\bf g}] \geq |C_t| \cdot \frac {\epsilon}4

Now we can use another averaging argument to say that there have to be at least {|C_t|\cdot \frac{\epsilon}8} elements {u} of {C} such that

\displaystyle  \mathop{\mathbb P} [ F'(u) \neq \bot] \geq \frac {\epsilon}8 \cdot \frac {|C_t|}{|C|} \geq \left( \frac \epsilon 8 \right) ^{t+1}

Let us call {C_{t+1}} the set of such element. As required, {|C_{t+1}| \geq |C| \cdot (\epsilon/8)^{t+1}}.

By applying concentration of measure, the fact that, for every {u\in C_{t+1}} we have

\displaystyle  \mathop{\mathbb P} \left[ \max_{w \in B(u, (t+1) \cdot \ell)} Y_w - Y_u \geq (t+1) \frac \sigma 2 + \frac \sigma 2 \right ] \geq \left( \frac {\epsilon} 8 \right)^{t+1}

implies that, for every {u\in C_{t+1}}

\displaystyle  \mathop{\mathbb P} \left[\max_{w \in B(u, (t+1) \cdot \ell)} Y_w - Y_u \geq (t+1) \frac \sigma 2 + \frac \sigma 2 - c_3 \sqrt{ \log \frac {4\cdot 8^{t+1}}{\epsilon^{t+2}}} \sqrt{(t+1) \cdot \ell} \right ] \geq 1 -\frac {\epsilon} 4

and the inductive step is proved, provided

\displaystyle  \frac \sigma 2 \geq c_3 \sqrt{ (t+2) \cdot \log \frac 8\epsilon } \sqrt{(t+1) \cdot \ell}

which is true when

\displaystyle  t+2 \leq \frac{\sigma}{2c_3 \sqrt {\log 8/\epsilon} } \cdot \frac 1 {\sqrt \ell}

which proves the lemma if we choose {c_4} appropriately. \Box

Applying the previous lemma with {t = c_4 /\sqrt {\ell}}, we have that, with probability {\Omega(1)}, there is a pair {u,v} in {C} such that

\displaystyle  Y_v- Y_u \geq \Omega( 1/\sqrt{\ell} )

and

\displaystyle  d(u,v) \leq O( \sqrt \ell)

but we also know that, with {1-o(1)} probability, for all pairs {u,v} in {C},

\displaystyle  | Y_v - Y_u|^2 \leq O(\log |C|) \cdot d(i,j)

and so

\displaystyle  \frac 1 \ell \leq O(\log |C|) \sqrt{\ell}

implying

\displaystyle  \ell \geq \Omega \left( \frac 1 {(\log |C|)^{2/3} } \right)

2. The Tight Bound

In the result proved in the previous section, we need {\frac \sigma 2 }, which is a constant, to be bigger than the loss incurred in the application of concentration of measure, which is of the order of {t \sqrt \ell}. A factor of {\sqrt {t \ell}} simply comes from the distances between the points that we are considering; an additional factor of {\sqrt t} comes from the fact that we need to push up the probability from a bound that is exponentially small in {t}.

The reason for such a poor probability bound is the averaging argument: each element of {C_t} has probability {\Omega(1)} of being the “middle point” of the construction, so that the sum over the elements {u} of {C} of the probability that {u} has {F'(u) \neq \bot} adds up to {\Omega (|C_t|)}; such overall probability, however, could be spread out over all of {C}, with each element of {C} getting a very low probability of the order of {|C_t|/|C|}, which is exponentially small in {t}.

Not all elements of {C}, however, can be a {u} for which {F'(u) \neq \bot}; this is only possible for elements {u} that are within distance {\ell} from {C_t}. If the set {\Gamma_{\ell} (C_t) := \{ u : \exists v \in C_t : d(u,v) \leq \ell \}} has cardinality of the same order of {C_t}, then we only lose a constant factor in the probability, and we do not pay the extra {\sqrt t} term in the application of concentration of measure. But what do we do if {\Gamma_{\ell} (C_t)} is much bigger than {C_t}? In that case we may replace {C_t} and {\Gamma_\ell (C_t)} and have similar properties.

Lemma 3 Under the assumptions of Lemma 1, if {S\subseteq C} is a set of points such that for every {v \in S}

\displaystyle  \mathop{\mathbb P} \left[ \max_{w \in B(v, d)} Y_w - Y_v \geq p \right ] \geq \epsilon

then, for every distance {D}, every {k>0}, and every {u \in \Gamma_D(S)}

\displaystyle  \mathop{\mathbb P} \left[ \max _{w \in B(u, d+D)} Y_w - Y_u \geq p - \sqrt D \cdot k \right ] \geq \epsilon - e^{-k^2/2}

That is, if all the elements of {S} are {(p,d,\epsilon)}-LPP, then all the elements of {\Gamma_D(S)} are {(p - k \sqrt{D}, d+D, \epsilon - e^{-k^2/2})}-LPP.

Proof: If {u\in \Gamma_D(S)}, then there is {v\in S} such that {d(u,v) \leq D}, and, with probability {1-e^{-k^2/2}} we have {Y_u - Y_v \leq \sqrt D \cdot k}. The claim follows from a union bound. \Box

Lemma 4 Under the assumptions of Lemma 1, there is a constant {c_5 >0} (that depends only on {\epsilon} and {\sigma}) such that for all {t \leq c_5 \cdot \frac 1 {\ell}}, there is a set {C_t \subseteq C} such that {|C_t | \geq |C| \cdot(\epsilon/8) ^{t}}, every element of {C_t} is {\left( t \cdot \frac \sigma 4, \left(2t+\log_{\frac 8 \epsilon} \frac {|C_t|}{|C|} \right) \cdot \ell , 1 - \frac \epsilon 4 \right)}-LPP, and

\displaystyle  | \Gamma_\ell (C_t) | \leq \frac 8 \epsilon |C_t|

Proof: The base case {t=0} is proved by setting {C_0 = C}.

For the inductive step, we define {F(\cdot)} and {F'(\cdot)} as in the proof of Lemma 2. We have that if {F'(u) = w \neq \bot}, then

\displaystyle  Y_w - Y_u \geq t \cdot \frac \sigma 4 + \sigma \ ,

\displaystyle  d(u,w) \leq \left(2t+\log_{\frac 8 \epsilon} \frac {|C_t|}{|C|} \right)\cdot \ell + \ell \ ,

and

\displaystyle  \sum_{u \in C} \mathop{\mathbb P} [ F'(u) \neq \bot] = \sum_{v \in C_t} [ F(v) \neq \bot \wedge \exists u. (u,v) \in M'_{\bf g}] \geq |C_t| \cdot \frac {\epsilon}4

Now we can use another averaging argument to say that there have to be at least {|C_t|\cdot \frac{\epsilon}8} elements {u} of {C} such that

\displaystyle  \mathop{\mathbb P} [ F'(u) \neq \bot] \geq \frac {\epsilon}8 \cdot \frac {|C_t|}{|\Gamma_\ell(C_t)|} \geq \left( \frac {\epsilon^2} {64} \right)

Let us call {C^{(0)}_{t+1}} the set of such elements.

Define {C^{(1)}_{t+1} := \Gamma_\ell (C^{(0)}_{t+1})}, {C^{(2)}_{t+1} := \Gamma_\ell (C^{(1)}_{t+1})}, and so on, and let {k} be the first time such that {| C^{(k+1)}_{t+1} | \leq \frac 8 \epsilon |C^{(k)}_{t+1}|}. We will define {C_{t+1} := C^{(k)}_{t+1}}. Note that

\displaystyle  |C_{t+1} | \geq \left( \frac 8 \epsilon \right)^k \cdot |C^{(0)} _{t+1} | \geq \left( \frac 8 \epsilon \right)^{k-1} \cdot |C_t| \geq \left( \frac 8 \epsilon \right)^{k-1 - t} |C|

which implies that {k \leq t+1}. We have {|C_{t+1}| \geq |C^{(0)}_{t+1}| \geq \frac \epsilon 8 |C_t|} so we satisfy the inductive claim about the size of {C_t}. Regarding the other properties, we note that {C_{t+1} \subseteq \Gamma_{k\ell} (C^{(0)}_{t+1})}, and that every element of {C^{(0)}_{t+1}} is

\displaystyle  \left( t \frac \sigma 4 + \sigma, \left(2t+ 1 +\log_{\frac 8 \epsilon} \frac {|C_t|}{|C|} \right)\cdot \ell , \frac {\epsilon^2}{64} \right) - {\rm LPP}

so we also have that every element of {C_{t+1}} is

\displaystyle  \left( t \frac \sigma 4 + \frac \sigma 2, \left(2t+ 1 + k +\log_{\frac 8 \epsilon} \frac {|C_t|}{|C|} \right) \cdot \ell , \frac {\epsilon^2}{128} \right)-{\rm LPP}

provided

\displaystyle  \frac \sigma 2 \geq \sqrt { 2 \log \frac{128}{\epsilon^2}} \cdot k \ell

which we can satisfy with an appropriate choice of {c_4}, recalling that {k \leq t+1}.

Then we apply concentration of measure to deduce that every element of {C_{t+1}} is

\displaystyle  \left( t \frac \sigma 4 +\frac \sigma 4, \left(2t+ 1 + k +\log_{\frac 8 \epsilon} \frac {|C_t|}{|C|} \right) \cdot \ell , 1 - \frac \epsilon 4 \right)-{\rm LPP}

provided that

\displaystyle  \frac \sigma 4 \geq c_3 \sqrt { \log \frac{512}{\epsilon^3}} \cdot \left(2t+ 1 + k +\log_{\frac 8 \epsilon} \frac {|C_t|}{|C|} \right) \cdot \ell

which we can again satisfy with an appropriate choice of {c_4}, because {k \leq t+1} and {\log_{\frac 8 \epsilon} \frac {|C_t|}{|C|} } is smaller than or equal to zero.

Finally,

\displaystyle  2t+ 1 + k + \log_{\frac 8 \epsilon} \frac {|C_t|}{|C|} \leq 2t +2 + \log_{\frac 8 \epsilon} \frac {|C_{t+1}|}{|C|}

because, as we established above,

\displaystyle  |C_{t+1}| \geq \left( \frac 8{\epsilon} \right)^{k-1} |C_t|

\Box

By applying Lemma 4 with {t = \Omega(1/\ell)}, we find that there is {\Omega(1)} probability that there are {u,v} in {C} such that

\displaystyle  Y_j - Y_i \geq \Omega(1/\ell)

\displaystyle  d(i,j) \leq 1

\displaystyle  |Y_i - Y_j|^2 \leq O(\log n) \cdot d(i,j)

which, together, imply

\displaystyle  \ell \geq \Omega \left( \frac 1 {\sqrt{ \log n}} \right)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s