From ea0af4abc93a0ceb099c3e5bb520f6057e9ae215 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Mon, 18 May 2015 19:11:35 +0200
Subject: Put all assumptions together

---
 paper/sections/results.tex | 45 ++++++---------------------------------------
 1 file changed, 6 insertions(+), 39 deletions(-)

(limited to 'paper/sections/results.tex')

diff --git a/paper/sections/results.tex b/paper/sections/results.tex
index 7fca661..1db8288 100644
--- a/paper/sections/results.tex
+++ b/paper/sections/results.tex
@@ -47,28 +47,6 @@ log-likelihood function $\mathcal{L}$: it essentially captures the fact that
 the binary vectors of the set of active nodes (\emph{i.e} the measurement) are
 not \emph{too} collinear.
 
-{\color{red} Rewrite the minimal assumptions necessary}
-We will also need the following assumption on the inverse link function $f$ of
-the generalized linear cascade model:
-%\begin{equation}
-    %\tag{LF}
-    %\max\left(\left|\frac{f'}{f}(\inprod{\theta^*}{x})\right|,
-    %\left|\frac{f'}{1-f}(\inprod{\theta^*}{x})\right|\right)\leq
-    %\frac{1}{\alpha}
-%\end{equation}
-\begin{equation}
-  \tag{LF}
-  \max \left( \| (\log f)' \|_{\infty}, \|(\log (1-f))' \|_{\infty} \right)
-  \leq \frac{1}{\alpha}
-\end{equation}
-for some $\alpha\in(0, 1)$ and for all $x\in\reals^m$ such that
-$f(\inprod{\theta^*}{x})\notin\{0,1\}$.
-
-In the voter model, $\frac{f'}{f}(z) = \frac{1}{z}$ and $\frac{f'}{f}(1-z) =
-\frac{1}{1-z}$. Hence (LF) will hold as soon as $\alpha\leq \Theta_{i,j}\leq
-1-\alpha$ for all $(i,j)\in E$ which is always satisfied for some $\alpha$ for
-non-isolated nodes.  In the Independent Cascade Model, $\frac{f'}{f}(z) =
-\frac{1}{1-e^{-z}}$ and $\frac{f'}{1-f}(z) = -1$ and (LF) is not restrictive.
 
 \begin{comment}
 Remember that in this case we have $\Theta_{i,j} = \log(1-p_{i,j})$. These
@@ -231,7 +209,7 @@ As before, edge recovery is a consequence of upper-bounding $\|\theta^* - \hat
         \frac{16}{\epsilon^2}\| \theta^* - \theta^*_{\lfloor
     s\rfloor}\|_1\right)s\log m
 \end{equation}
-then similarly: ${\cal S}^*_{\eta + \epsilon} \subset \hat {\cal S}_\eta
+then: ${\cal S}^*_{\eta + \epsilon} \subset \hat {\cal S}_\eta
 \subset {\cal S}^*$ w.p. at least $1-\frac{1}{m}$.
 \end{corollary}
 
@@ -267,8 +245,8 @@ then
 \end{displaymath}
 and the $(S, \gamma)$-({\bf RE}) condition on the Hessian in
 Theorem~\ref{thm:main} and Theorem~\ref{thm:approx_sparse} reduces to a
-condition on the \emph{gram matrix} of the observations $X^T X =
-\frac{1}{|\mathcal{T}|}\sum_{t\in\mathcal{T}}x^t(x^t)^T$ with $\gamma \leftarrow
+condition on the \emph{Gram matrix} of the observations $X^T X =
+\frac{1}{|\mathcal{T}|}\sum_{t\in\mathcal{T}}x^t(x^t)^T$ for $\gamma' \defeq
 \gamma\cdot c$.
 
 \paragraph{(RE) with high probability}
@@ -287,7 +265,7 @@ probability.
 
 If $f$ and $1-f$ are strictly log-convex, then the previous observations yields
 the following natural interpretation of the {\bf(RE)}-condition: the expected
-\emph{gram matrix} $A \equiv \mathbb{E}[X^T X]$ is a matrix whose entry
+\emph{Gram matrix} $A \equiv \mathbb{E}[X^T X]$ is a matrix whose entry
 $a_{i,j}$ is the average fraction of times node $i$ and node $j$ are infected
 at the same time during several runs of the cascade process. Note that the
 diagonal terms $a_{i,i}$ are simply the average fraction of times the
@@ -295,24 +273,13 @@ corresponding node $i$ is infected.
 
 Therefore, under an assumption which only involves the probabilistic model and
 not the actual observations, Proposition~\ref{prop:fi} allows us to draw the
-same conclusion as in Theorem~\ref{thm:main}. We will need the following
-additional assumptions on the inverse link function $f$:
-\begin{equation}
-    \tag{LF2}
-    \|f'\|_{\infty} \leq M
-    \text{ and }
-    \max\left(\left|\frac{f''}{1-f}\right|,
-    \left|\frac{f''}{f}\right|\right)
-    \leq\frac{1}{\alpha}
-\end{equation}
-whenever $f(\inprod{\theta^*}{x})\notin\{0,1\}$. These conditions are once
-again non restrictive in the (IC) model and (V) model.
+same conclusion as in Theorem~\ref{thm:main}.
 
 \begin{proposition}
     \label{prop:fi}
     Suppose $\E[\nabla^2\mathcal{L}(\theta^*)]$ verifies the $(S,\gamma)$-{\bf
     (RE)} condition and assume {\bf (LF)} and {\bf (LF2)}. For $\delta> 0$, if
-    $n^{1-\delta}\geq \frac{M+2}{21\gamma\alpha}s^2\log m $, then
+    $n^{1-\delta}\geq \frac{1}{28\gamma\alpha}s^2\log m $, then
     $\nabla^2\mathcal{L}(\theta^*)$ verifies the $(S,\frac{\gamma}{2})$-(RE)
     condition, w.p $\geq 1-e^{-n^\delta\log m}$.
 \end{proposition}
-- 
cgit v1.2.3-70-g09d2

