diff options
| -rw-r--r-- | main.tex | 57 |
1 files changed, 28 insertions, 29 deletions
@@ -340,7 +340,7 @@ This solution is: %\end{displaymath} %However, for the purpose of proving theorem~\ref{thm:main}, we need to bound %$L_\mathcal{N}$ from above (up to a multiplicative factor) by $V$. -Toprove Lemma~\ref{lemma:relaxation}, we use the +To prove Lemma~\ref{lemma:relaxation}, we use the \emph{pipage rounding} method of Ageev and Sviridenko~\cite{pipage}, where $L_\mathcal{N}$ is first bounded from above by the multi-linear relaxation $F_\mathcal{N}$, which is itself subsequently bounded by $V$. While the latter part is general and can be applied @@ -434,27 +434,29 @@ For all $\lambda\in[0,1]^{n},$ \end{lemma} \begin{proof} We will prove that $\frac{1}{2}$ is a lower bound of the ratio $\partial_i - F_\mathcal{N}(\lambda)/\partial_i L_\mathcal{N}(\lambda)$. Where - $\partial_i\, \cdot$ denotes the derivative of a function with respect to the - $i$-th variable. This will be enough to conclude, by observing that at - $\lambda = 0$, one can write: - \begin{displaymath} - \frac{F_\mathcal{N}(\lambda)}{L_\mathcal{N}(\lambda)} - \sim_{\lambda\rightarrow 0} - \frac{\sum_{i\in \mathcal{N}}\lambda_i\partial_i F_\mathcal{N}(0)} - {\sum_{i\in\mathcal{N}}\lambda_i\partial_i L_\mathcal{N}(0)} - \geq \frac{1}{2} - \end{displaymath} - If the minimum is attained at a point interior to the hypercube, then it is - a critical point of the ratio - $F_\mathcal{N}(\lambda)/L_\mathcal{N}(\lambda)$. Such a critical point is + F_\mathcal{N}(\lambda)/\partial_i L_\mathcal{N}(\lambda)$, where + $\partial_i\, \cdot$ denotes the partial derivative of a function with respect to the + $i$-th variable. This will be enough to conclude, by observing the following cases. + First, if the minimum of the ratio + $F_\mathcal{N}(\lambda)/L_\mathcal{N}(\lambda)$ is attained at a point interior to the hypercube, then it is + a critical point; such a critical point is characterized by: \begin{equation}\label{eq:lhopital} \frac{F_\mathcal{N}(\lambda)}{L_\mathcal{N}(\lambda)} = \frac{\partial_i F_\mathcal{N}(\lambda)}{\partial_i L_\mathcal{N}(\lambda)} \geq \frac{1}{2} \end{equation} - Finally, if the minimum is attained on a face of the hypercube (a face is + Second, if the minimum is attained as + $\lambda$ converges to zero in, \emph{e.g.}, the $l_2$ norm, by the Taylor approximation, one can write: + \begin{displaymath} + \frac{F_\mathcal{N}(\lambda)}{L_\mathcal{N}(\lambda)} + \sim_{\lambda\rightarrow 0} + \frac{\sum_{i\in \mathcal{N}}\lambda_i\partial_i F_\mathcal{N}(0)} + {\sum_{i\in\mathcal{N}}\lambda_i\partial_i L_\mathcal{N}(0)} + \geq \frac{1}{2}, + \end{displaymath} + \emph{i.e.}, the ratio $\frac{F_\mathcal{N}(\lambda)}{L_\mathcal{N}(\lambda)}$ is necessarily bounded from below by 1/2 for small enough $\lambda$. + Finally, if the minimum is attained on a face of the hypercube $[0,1]^n$ (a face is defined as a subset of the hypercube where one of the variable is fixed to 0 or 1), without loss of generality, we can assume that the minimum is attained on the face where the $n$-th variable has been fixed @@ -469,7 +471,6 @@ For all $\lambda\in[0,1]^{n},$ Let us start by computing the derivatives of $F_\mathcal{N}$ and $L_\mathcal{N}$ with respect to the $i$-th component. - For $F$, it suffices to look at the derivative of $P_\mathcal{N}^\lambda(S)$: \begin{displaymath} @@ -484,44 +485,43 @@ For all $\lambda\in[0,1]^{n},$ \begin{multline*} \partial_i F_\mathcal{N} = \sum_{\substack{S\subseteq\mathcal{N}\\ i\in S}} - P_{\mathcal{N}\setminus\{i\}}^\lambda(S\setminus\{i\})V(S)\\ + P_{\mathcal{N}\setminus\{i\}}^\lambda(S\setminus\{i\})V(S) - \sum_{\substack{S\subseteq\mathcal{N}\\ i\in \mathcal{N}\setminus S}} P_{\mathcal{N}\setminus\{i\}}^\lambda(S)V(S) \end{multline*} - Now, using that every $S$ such that $i\in S$ can be uniquely written as $S'\cup\{i\}$, we can write: \begin{multline*} \partial_i F_\mathcal{N} = \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}} - P_{\mathcal{N}\setminus\{i\}}^\lambda(S)V(S\cup\{i\})\\ + P_{\mathcal{N}\setminus\{i\}}^\lambda(S)V(S\cup\{i\}) - \sum_{\substack{S\subseteq\mathcal{N}\\ i\in \mathcal{N}\setminus S}} P_{\mathcal{N}\setminus\{i\}}^\lambda(S)V(S) \end{multline*} - Finally, by using the expression for the marginal contribution of $i$ to - $S$: + Finally, the marginal contribution of $i$ to + $S$ is + $ \Delta_i V(S)\defeq V(S\cup\{i\}) - V(S) = \frac{1}{2}\log\left(1 + \mu \T{x_i} A(S)^{-1}x_i\right)$. +Using this, \begin{displaymath} \partial_i F_\mathcal{N}(\lambda) = \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}} P_{\mathcal{N}\setminus\{i\}}^\lambda(S) \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big) \end{displaymath} - - The computation of the derivative of $L_\mathcal{N}$ uses standard matrix + where $A(S) =I_d+ \T{X_S}X_S$. The computation of the derivative of $L_\mathcal{N}$ uses standard matrix calculus and gives: \begin{displaymath} \partial_i L_\mathcal{N}(\lambda) = \T{x_i}\tilde{A}(\lambda)^{-1}x_i \end{displaymath} - - Using the following inequalities: + where $\tilde{A}(\lambda) = I_d+\sum_{i\in \mathcal{N}}\lambda_ix_i\T{x_i}$. Using the following inequalities (where $A\geq B$ implies $A-B$ is positive semi-definite): \begin{gather*} \forall S\subseteq\mathcal{N}\setminus\{i\},\quad P_{\mathcal{N}\setminus\{i\}}^\lambda(S)\geq P_{\mathcal{N}\setminus\{i\}}^\lambda(S\cup\{i\})\\ \forall S\subseteq\mathcal{N},\quad P_{\mathcal{N}\setminus\{i\}}^\lambda(S) \geq P_\mathcal{N}^\lambda(S)\\ - \forall S\subseteq\mathcal{N},\quad A(S)^{-1} \geq A(S\cup\{i\})^{-1}\\ + \forall S\subseteq\mathcal{N},\quad A(S)^{-1} \geq A(S\cup\{i\})^{-1} \end{gather*} we get: \begin{align*} @@ -540,9 +540,8 @@ For all $\lambda\in[0,1]^{n},$ &\geq \frac{1}{2} \sum_{S\subseteq\mathcal{N}} P_\mathcal{N}^\lambda(S) - \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big)\\ + \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big) \end{align*} - Using that $A(S)\geq I_d$ we get that: \begin{displaymath} \T{x_i}A(S)^{-1}x_i \leq \norm{x_i}_2^2 = 1 |