added plots to appendix

1 files changed, 60 insertions, 26 deletions

diff --git a/paper/sections/appendix.tex b/paper/sections/appendix.tex
index 64953a3..4c6aed7 100644
--- a/paper/sections/appendix.tex
+++ b/paper/sections/appendix.tex
@@ -70,7 +70,7 @@ the proof.
     $
     \forall \Delta\in C(S),\;
     \Delta H\Delta \geq \frac{1}{2} \Delta \E[H]\Delta,
-    $ w.p. at least $1-e^{-n^{\delta}\log m}$ and the conclusion of
+    $ w.p.~at least $1-e^{-n^{\delta}\log m}$ and the conclusion of
     Proposition~\ref{prop:fi} follows.
 \end{proof}
 
@@ -99,37 +99,71 @@ has a quantity of information $\Omega(s\log \frac{m}{s})$ about $S$. By the
 Shannon-Hartley theorem, this information is also upper-bounded by $\O(n\log
 C)$. These two bounds together imply the theorem.
 
-\subsection{Other continuous time processes binned to ours: proportional
-hazards model}
 
-\subsection{Irrepresentability vs. Restricted Eigenvalue Condition}
-In the words and notation of Theorem 9.1 in \cite{vandegeer:2009}:
-\begin{lemma}
-\label{lemm:irrepresentability_proof}
-Let $\phi^2_{\text{compatible}}(L,S) \defeq \min \{ \frac{s
-\|f_\beta\|^2_2}{\|\beta_S\|^2_1} \ : \ \beta \in {\cal R}(L, S) \}$, where
-$\|f_\beta\|^2_2 \defeq \{ \beta^T \Sigma \beta \}$ and ${\cal R}(L,S) \defeq
-\{\beta : \|\beta_{S^c}\|_1 \leq L \|\beta_S\|_1 \neq 0\}$. If
-$\nu_{\text{irrepresentable}(S,s)} < 1/L$, then $\phi^2_{\text{compatible}}(L,S)
-\geq (1 - L \nu_{\text{irrepresentable}(S,s)})^2 \lambda_{\min}^2$.
-\end{lemma}
+\subsection{Running Time Analysis}
 
-Since ${\cal R}(3, S) = {\cal C}$, $\|\beta_S\|_1 \geq \|\beta_S\|_2$, and
-$\|\beta_S\|_1 \geq \frac{1}{3} \|\beta_{S^c}\|_1$ it is easy to see that
-$\|\beta_S\|_1 \geq \frac{1}{4} \|\beta\|_2$ and therefore that: $\gamma_n \geq
-\frac{n}{4s}\phi^2_{\text{compatible}}(3,S)$
+\begin{figure}
+  \centering
+  \includegraphics[scale=.4]{figures/n_nodes_running_time.pdf}
+  \caption{Running time analysis for estimating the parents of a \emph{single
+    node} on a Barabasi-Albert graph as a function of the number of nodes in
+    the graph. The parameter $k$ (number of nodes each new node is attached to)
+    is constant equal to $30$.  $p_{\text{init}}$ is chosen equal to $.15$, and
+    the edge weights are chosen uniformly at random in $[.2,.7]$. The
+  penalization parameter $\lambda$ is chosen equal to $.1$.}
+    \label{fig:running_time_n_nodes}
+\end{figure}
 
-Consequently, if $\epsilon > \frac{2}{3}$, then
-$\nu_{\text{irrepresentable}(S,s)} < 1/3$ and the conditions of
-Lemma~\ref{lemm:irrepresentability_proof} hold.
+\begin{figure}
+  \centering
+  \includegraphics[scale=.4]{figures/n_cascades_running_time.pdf}
+  \caption{Running time analysis for estimating the parents of a \emph{single
+    node} on a Barabasi-Albert graph as a function of the number of total
+    observed cascades.  The parameter $k$ (number of nodes each new node is
+    attached to) is constant equal to $30$.  $p_{\text{init}}$ is chosen equal
+  to $.15$, and the edge weights are chosen uniformly at random in $[.2,.7]$.
+The penalization parameter $\lambda$ is chosen equal to $.1$.}
+    \label{fig:running_time_n_cascades}
+\end{figure}
 
+We include here a running time analysis of the different algorithms, as shown
+in Figure~\ref{fig:running_time_n_nodes} and
+Figure~\ref{fig:running_time_n_cascades}. As expected, the simple greedy
+algorithm is the fastest algorithm. Interestingly, the non-penalized convex
+optimization program also converges faster than our suggested penalized
+maximum-likelihood program.
 
+%\subsection{Other continuous time processes binned to ours: proportional
+%hazards model}
 
-\subsection{Lower bound for restricted eigenvalues (expected hessian) for
-different graphs}
+%\subsection{Irrepresentability vs. Restricted Eigenvalue Condition}
+%In the words and notation of Theorem 9.1 in \cite{vandegeer:2009}:
+%\begin{lemma}
+%\label{lemm:irrepresentability_proof}
+%Let $\phi^2_{\text{compatible}}(L,S) \defeq \min \{ \frac{s
+%\|f_\beta\|^2_2}{\|\beta_S\|^2_1} \ : \ \beta \in {\cal R}(L, S) \}$, where
+%$\|f_\beta\|^2_2 \defeq \{ \beta^T \Sigma \beta \}$ and ${\cal R}(L,S) \defeq
+%\{\beta : \|\beta_{S^c}\|_1 \leq L \|\beta_S\|_1 \neq 0\}$. If
+%$\nu_{\text{irrepresentable}(S,s)} < 1/L$, then $\phi^2_{\text{compatible}}(L,S)
+%\geq (1 - L \nu_{\text{irrepresentable}(S,s)})^2 \lambda_{\min}^2$.
+%\end{lemma}
 
-\subsection{Better asymptotic w.r.t expected hessian}
+%Since ${\cal R}(3, S) = {\cal C}$, $\|\beta_S\|_1 \geq \|\beta_S\|_2$, and
+%$\|\beta_S\|_1 \geq \frac{1}{3} \|\beta_{S^c}\|_1$ it is easy to see that
+%$\|\beta_S\|_1 \geq \frac{1}{4} \|\beta\|_2$ and therefore that: $\gamma_n \geq
+%\frac{n}{4s}\phi^2_{\text{compatible}}(3,S)$
 
-\subsection{Confidence intervals?}
+%Consequently, if $\epsilon > \frac{2}{3}$, then
+%$\nu_{\text{irrepresentable}(S,s)} < 1/3$ and the conditions of
+%Lemma~\ref{lemm:irrepresentability_proof} hold.
 
-\subsection{Active learning}
+
+
+%\subsection{Lower bound for restricted eigenvalues (expected hessian) for
+%different graphs}
+
+%\subsection{Better asymptotic w.r.t expected hessian}
+
+%\subsection{Confidence intervals?}
+
+%\subsection{Active learning}