From e41204334108b4ad40246f3d81435a40ff484837 Mon Sep 17 00:00:00 2001 From: jeanpouget-abadie Date: Mon, 18 May 2015 19:19:35 +0200 Subject: added plots to appendix --- paper/sections/appendix.tex | 102 +++++++++++++++++++++++++++++--------------- 1 file changed, 68 insertions(+), 34 deletions(-) (limited to 'paper') 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} - -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)$ - -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{Lower bound for restricted eigenvalues (expected hessian) for -different graphs} - -\subsection{Better asymptotic w.r.t expected hessian} - -\subsection{Confidence intervals?} - -\subsection{Active learning} +\subsection{Running Time Analysis} + +\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} + +\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{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} + +%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)$ + +%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{Lower bound for restricted eigenvalues (expected hessian) for +%different graphs} + +%\subsection{Better asymptotic w.r.t expected hessian} + +%\subsection{Confidence intervals?} + +%\subsection{Active learning} -- cgit v1.2.3-70-g09d2