marginal contrib

1 files changed, 28 insertions, 29 deletions

diff --git a/main.tex b/main.tex
index 560a86a..d14e668 100644
--- a/main.tex
+++ b/main.tex
@@ -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