corrolary 2

1 files changed, 11 insertions, 3 deletions

diff --git a/paper/sections/results.tex b/paper/sections/results.tex
index 7566cb3..96d79b9 100644
--- a/paper/sections/results.tex
+++ b/paper/sections/results.tex
@@ -25,7 +25,7 @@ We analyse the previous conditions in the case of the Independent Cascade model.
 For any $\delta > 0$, with probability $1-e^{-n^\delta \log m}$, $\|\nabla f(\theta^*)\|_{\infty} \leq 2 \sqrt{\frac{n^{\delta + 1} \log m}{p_{\min}}}$
 \end{lemma}
 
-The following corollary follows immediately from Theorem~\ref{theorem:neghaban} and Lemma~\ref{lemma:icc_lambda_upper_bound}.
+The following corollaries follows immediately from Theorem~\ref{theorem:neghaban} and Lemma~\ref{lemma:icc_lambda_upper_bound}.
 
 \begin{corollary}
 Assume that ${\bf (RE)}$ holds with $\gamma_n = n \gamma$ for $\gamma > 0$. Then for $\lambda_n := 2 \sqrt{\frac{n^{\delta + 1} \log m}{p_{\min}}}$ and with probability $1-e^{n^\delta \log p}$
@@ -34,9 +34,17 @@ Assume that ${\bf (RE)}$ holds with $\gamma_n = n \gamma$ for $\gamma > 0$. Then
 \end{equation}
 \end{corollary}
 
-Note that here $n$ is the number of measurements and not the number of cascades. This is an important improvement over prior work since we expect several measurements per cascade. We claim that graph recovery is better understood as $n$, the cumulative number of steps in each cascade, rather than $N$, the number of individual cascades.
+\begin{corollary}
+Suppose that after solving Eq.~\ref{eq:mle}, we construct the set $\hat {\cal S}_\eta := \{ i \in [1..p] : \hat \theta_i > \eta\}$ for $\eta > 0$. Suppose the number of measurements verifies:
+\begin{equation}
+n > \frac{4}{\gamma^2 p_{\min}} s \log p
+\end{equation}
+Then $\hat {\cal S}_\eta = {\cal S}^*_{2\eta}$, where ${\cal S}^*_{2\eta} = \{ i \in [1..p] :\theta^*_i > 2 \eta \} $. In other words, we incur no false positives (false parents) and recover all `strong' parents, such that $\theta^*_j > 2 \eta$.
+\end{corollary}
+
+Note that here $n$ is the number of measurements and not the number of cascades. This is an important improvement over prior work since we expect several measurements per cascade. We claim that graph recovery is better understood as a function of $n$, the cumulative number of steps in each cascade, rather than as a function $N$, the number of individual cascades.
 
-Unfortunately, proving the {\bf (RE)} assumption for correlated measurements is highly non-trivial. We can show a very crude ${\cal O}(N)$-lower bound for  for $\gamma_n$ by exploiting only the first set of measurements, where only the source nodes are active. Note that even though we waste a lot of information, we obtain similar asymptotic behavior than previous work.
+Unfortunately, proving the {\bf (RE)} assumption for correlated measurements is highly non-trivial. We can show a very crude ${\cal O}(N)$-lower bound for $\gamma_n$ by exploiting only the first set of measurements, where only the source nodes are active. Note that even though we waste a lot of information, we obtain similar asymptotic behavior than previous work.
 
 
 \subsection{Linear Threshold Model}