Proof of lemma 3 (bound on the relaxations of the value function)

1 files changed, 135 insertions, 2 deletions

diff --git a/proof.tex b/proof.tex
index cbfa759..a26c191 100644
--- a/proof.tex
+++ b/proof.tex
@@ -104,6 +104,7 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
             & = \log\det \mathbb{E}_{S\sim P_\mathcal{N}(S,\lambda)}\big[X(S)\big]\\
             & = \log\det\left(\sum_{S\subset N}
                 P_\mathcal{N}(S,\lambda)X(S)\right)\\
+                & = \log\det \tilde{X}(\lambda)\\
             & = \log\det\left(I_d
                 + \frac{\kappa}{\sigma^2}\sum_{i\in\mathcal{N}}
                     \lambda_ix_ix_i^*\right)
@@ -181,13 +182,145 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
 \end{proof}
 
 \begin{lemma}
-    There exists $C>0$ such that:
+    The following inequality holds:
     \begin{displaymath}
-        \forall\lambda\in[0,1]^n,\; C\,L_\mathcal{N}(\lambda)\leq
+        \forall\lambda\in[0,1]^n,\; 
+        \frac{\log\big(1+\frac{\kappa}{\sigma^2}\big)}{2\frac{\kappa}{\sigma^2}}
+        \,L_\mathcal{N}(\lambda)\leq
         F_\mathcal{N}(\lambda)\leq L_{\mathcal{N}}(\lambda)
     \end{displaymath}
 \end{lemma}
 
+\begin{proof}
+
+    We will prove that:
+    \begin{displaymath}
+        \frac{\log\big(1+\frac{\kappa}{\sigma^2}\big)}{2\frac{\kappa}{\sigma^2}}
+    \end{displaymath}
+    is a lower bound of the ratio $\partial_i F_\mathcal{N}(\lambda)/\partial_i
+    L_\mathcal{N}(\lambda)$.
+
+    This will be enough to conclude, by observing that:
+    \begin{displaymath}
+        \frac{F_\mathcal{N}(\lambda)}{L_\mathcal{N}(\lambda)}
+        \sim_{\lambda\rightarrow 0}
+        \frac{\sum_{i\in S}\partial_i F_\mathcal{N}(0)}{\sum_{i\in S}\partial_i L_\mathcal{N}(0)}
+    \end{displaymath}
+    and that an interior critical point of the ratio
+    $F_\mathcal{N}(\lambda)/L_\mathcal{N}(\lambda)$ is defined by:
+    \begin{displaymath}
+        \frac{F_\mathcal{N}(\lambda)}{L_\mathcal{N}(\lambda)}
+        = \frac{\partial_i F_\mathcal{N}(\lambda)}{\partial_i
+        L_\mathcal{N}(\lambda)}
+    \end{displaymath}
+
+    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}(S,\lambda)$:
+    \begin{displaymath}
+        \partial_i P_\mathcal{N}(S,\lambda) = \left\{
+            \begin{aligned}
+                & P_{\mathcal{N}\setminus\{i\}}(S\setminus\{i\},\lambda)\;\textrm{if}\; i\in S \\
+                & - P_{\mathcal{N}\setminus\{i\}}(S,\lambda)\;\textrm{if}\;
+                i\in \mathcal{N}\setminus S \\
+            \end{aligned}\right.
+    \end{displaymath}
+
+    Hence:
+    \begin{multline*}
+        \partial_i F_\mathcal{N} =
+        \sum_{\substack{S\subset\mathcal{N}\\ i\in S}}
+        P_{\mathcal{N}\setminus\{i\}}(S\setminus\{i\},\lambda)V(S)\\
+        - \sum_{\substack{S\subset\mathcal{N}\\ i\in \mathcal{N}\setminus S}}
+        P_{\mathcal{N}\setminus\{i\}}(S,\lambda)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\subset\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
+        P_{\mathcal{N}\setminus\{i\}}(S,\lambda)V(S\cup\{i\})\\
+        - \sum_{\substack{S\subset\mathcal{N}\\ i\in \mathcal{N}\setminus S}}
+        P_{\mathcal{N}\setminus\{i\}}(S,\lambda)V(S)\\
+    \end{multline*}
+
+    Finally, by using the expression for the marginal contribution of $i$ to
+    $S$:
+    \begin{displaymath}
+        \partial_i F_\mathcal{N}(\lambda) = 
+        \sum_{\substack{S\subset\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
+        P_{\mathcal{N}\setminus\{i\}}(S,\lambda)
+        \log\Big(1 + \frac{\kappa}{\sigma^2}x_i^*X(S)^{-1}x_i\Big)
+    \end{displaymath}
+
+    The computation of the derivative of $L_\mathcal{N}$ uses standard matrix
+    calculus and gives:
+    \begin{displaymath}
+        \partial_i L_\mathcal{N}(\lambda)
+        = \frac{\kappa}{\sigma^2}x_i^* \tilde{X}(\lambda)^{-1}x_i
+    \end{displaymath}
+    
+    Using the following inequalities:
+    \begin{gather*}
+        P_{\mathcal{N}\setminus\{i\}}(S,\lambda) \geq
+        P_\mathcal{N}(S,\lambda)\\
+        X(S)^{-1} \geq X(S\cup\{i\})^{-1}\\
+        P_\mathcal{N}(S\cup\{i\},\lambda)\geq P_\mathcal{N}(S,\lambda)
+    \end{gather*}
+    we get:
+    \begin{align*}
+        \partial_i F_\mathcal{N}(\lambda) 
+        & \geq \sum_{\substack{S\subset\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
+        P_\mathcal{N}(S,\lambda)
+        \log\Big(1 + \frac{\kappa}{\sigma^2}x_i^*X(S)^{-1}x_i\Big)\\
+        & \geq \frac{1}{2}
+        \sum_{\substack{S\subset\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
+        P_\mathcal{N}(S,\lambda)
+        \log\Big(1 + \frac{\kappa}{\sigma^2}x_i^*X(S)^{-1}x_i\Big)\\
+        &\hspace{-3.5em}+\frac{1}{2}
+        \sum_{\substack{S\subset\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
+        P_\mathcal{N}(S\cup\{i\},\lambda)
+        \log\Big(1 + \frac{\kappa}{\sigma^2}x_i^*X(S\cup\{i\})^{-1}x_i\Big)\\
+        &\geq \frac{1}{2}
+        \sum_{S\subset\mathcal{N}}
+        P_\mathcal{N}(S,\lambda)
+        \log\Big(1 + \frac{\kappa}{\sigma^2}x_i^*X(S)^{-1}x_i\Big)\\
+    \end{align*}
+
+    Using that $X(S)\geq I_d$ we get that:
+    \begin{displaymath}
+        \frac{\kappa}{\sigma^2}x_i^*X(S)^{-1}x_i \leq \frac{\kappa}{\sigma^2}
+    \end{displaymath}
+    
+    Moreover:
+    \begin{displaymath}
+        \forall x\leq\frac{\kappa}{\sigma^2},\; \log(1+x)\geq
+    \frac{\log\big(1+\frac{\kappa}{\sigma^2}\big)}{\frac{\kappa}{\sigma^2}} x
+    \end{displaymath}
+
+    Hence:
+    \begin{displaymath}
+        \partial_i F_\mathcal{N}(\lambda) \geq
+        \frac{\log\big(1+\frac{\kappa}{\sigma^2}\big)}{2\frac{\kappa}{\sigma^2}}
+        x_i^*\bigg(\sum_{S\subset\mathcal{N}}P_\mathcal{N}(S,\lambda)X(S)^{-1}\bigg)x_i
+    \end{displaymath}
+    
+    Finally, using that the inverse is a matrix convex function over symmetric
+    positive definite matrices:
+    \begin{align*}
+        \partial_i F_\mathcal{N}(\lambda) &\geq
+        \frac{\log\big(1+\frac{\kappa}{\sigma^2}\big)}{2\frac{\kappa}{\sigma^2}}
+        x_i^*\bigg(\sum_{S\subset\mathcal{N}}P_\mathcal{N}(S,\lambda)X(S)\bigg)^{-1}x_i\\
+        & \geq \frac{\log\big(1+\frac{\kappa}{\sigma^2}\big)}{2\frac{\kappa}{\sigma^2}}
+        \partial_i L_\mathcal{N}(\lambda)
+    \end{align*}
+
+\end{proof}
+
 \begin{lemma}
     \begin{displaymath}
         OPT(L_\mathcal{N}, B) \leq \frac{1}{C}OPT(V,\mathcal{N},B)