diff options
| -rw-r--r-- | paper/paper.tex | 2 | ||||
| -rw-r--r-- | paper/sections/results.tex | 25 |
2 files changed, 22 insertions, 5 deletions
diff --git a/paper/paper.tex b/paper/paper.tex index 6c6f789..fbc6521 100644 --- a/paper/paper.tex +++ b/paper/paper.tex @@ -59,6 +59,8 @@ \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} +\newtheorem{corollary}{Corollary} +\newtheorem{remark}{Remark} \begin{document} diff --git a/paper/sections/results.tex b/paper/sections/results.tex index ede143f..7566cb3 100644 --- a/paper/sections/results.tex +++ b/paper/sections/results.tex @@ -10,20 +10,35 @@ Our approach is different. Rather than trying to perform variable selection by f We cite the following Theorem from \cite{Negahban:2009}: \begin{theorem} -Suppose that the true vector $\theta^*$ has support S and that the {\bf(RE)} assumption holds for the hessian $\nabla^2 f(\theta^*)$, then by solving Eq.~\ref{...} for $\lambda_n \geq 2 \|\nabla f(\theta^*)\|_{\infty}$ we have: - +\label{theorem:neghaban} +Suppose the true vector $\theta^*$ has support S of size s and the {\bf(RE)} assumption holds for the Hessian $\nabla^2 f(\theta^*)$, then by solving Eq.~\ref{...} for $\lambda_n \geq 2 \|\nabla f(\theta^*)\|_{\infty}$ we have: \begin{equation} -\|\hat \theta - \theta^* \|_2 \leq \frac{\sqrt{|S|}\lambda_n}{\gamma_n} +\|\hat \theta - \theta^* \|_2 \leq \frac{\sqrt{s}\lambda_n}{\gamma_n} \end{equation} \end{theorem} \subsection{Independent Cascade Model} -We analyse the previous conditions in the case of the Independent Cascade model. Lemma 1. provides a ${\cal O}(n)$-upper-bound on $\|\nabla f\|$ +We analyse the previous conditions in the case of the Independent Cascade model. Lemma 1. provides a ${\cal O}(\sqrt{n})$-upper-bound w.h.p. on $\|\nabla f(\theta^*)\|$ \begin{lemma} -blabla +\label{lemma:icc_lambda_upper_bound} +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}. + +\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}$ +\begin{equation} +\|\hat \theta - \theta^* \|_2 \leq \frac{2}{\gamma} \sqrt{\frac{s \log p}{p_{\min} n^{1-\delta}}} +\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. + +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. + + \subsection{Linear Threshold Model} |