diff options
Diffstat (limited to 'proof.tex')
| -rw-r--r-- | proof.tex | 137 |
1 files changed, 135 insertions, 2 deletions
@@ -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) |