Running time analysis

1 files changed, 19 insertions, 12 deletions

diff --git a/paper/sections/appendix.tex b/paper/sections/appendix.tex
index 5cd364f..5a6a2c7 100644
--- a/paper/sections/appendix.tex
+++ b/paper/sections/appendix.tex
@@ -108,7 +108,6 @@ 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{Running Time Analysis}
 
 \begin{figure}
@@ -117,7 +116,7 @@ C)$. These two bounds together imply the theorem.
   \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
+    was set 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}
@@ -128,19 +127,27 @@ C)$. These two bounds together imply the theorem.
   \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$.}
+    observed cascades. The parameters defining the graph were set as in
+Figure~\ref{fig:running_time_n_nodes}.}
     \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.
+We include here a running time analysis of our algorithm. In
+Figure~\ref{fig:running_time_n_nodes}, we compared our algorithm to the
+benchmarks for increasing values of the number of nodes. In
+Figure~\ref{fig:running_time_n_cascades}, we compared our algorithm to the
+benchmarks for a fixed graph but for increasing number of observed cascades.
+
+In both Figures, unsurprisingly, the simple greedy algorithm is the fastest.
+Even though both the MLE algorithm and the algorithm we introduced are based on
+convex optimization, the MLE algorithm is faster. This is due to the overhead
+caused by the $\ell_1$-regularisation in~\eqref{eq:pre-mle}.
+
+The dependency as the number of cascades increases is linear, as expected. The
+slope is largest for our algorithm, which is against caused by the overhead
+induced by the $\ell_1$-regularization.
+
+
 
 %\subsection{Other continuous time processes binned to ours: proportional
 %hazards model}