First pass on appendix

1 files changed, 17 insertions, 8 deletions

diff --git a/paper/sections/appendix.tex b/paper/sections/appendix.tex
index 8e82e0c..5cd364f 100644
--- a/paper/sections/appendix.tex
+++ b/paper/sections/appendix.tex
@@ -1,6 +1,13 @@
-\subsection{Proof for different lemmas}
+In this appendix, we provide the missing proofs of Section~\ref{sec:results}
+and Section~\ref{sec:lowerbound}. We also show additional experiments on the
+running time of our recovery algorithm which could not fit in the main part of
+the paper.
 
-\subsubsection{Bounded gradient}
+\subsection{Proofs of Section~\ref{sec:results}}
+
+\paragraph{Bounded gradient} The proof of Lemma~\ref{lem:ub} giving an upper
+bound on the $\ell_{\infty}$ norm of the gradient of the likelihood function is
+given below.
 
 \begin{proof}
 The gradient of $\mathcal{L}$ is given by:
@@ -36,7 +43,9 @@ the proof.
 \end{proof}
 
 %\subsubsection{Approximate sparsity proof}
-\subsubsection{RE with high probability}
+\paragraph{(RE) with high probability} We now prove Proposition~\ref{prop:fi}.
+The proof mostly relies on showing that the Hessian of likelihood function
+$\mathcal{L}$ is sufficiently well concentrated around its expectation.
 
 \begin{proof}Writing $H\defeq \nabla^2\mathcal{L}(\theta^*)$, if
     $ \forall\Delta\in C(S),\;
@@ -56,17 +65,17 @@ the proof.
     Writing
     $\partial^2_{i,j}\mathcal{L}(\theta^*)=\frac{1}{|\mathcal{T}|}\sum_{t\in
     T}Y_t$ and using $(LF)$ and $(LF2)$ we have $\big|Y_t - \E[Y_t]\big|\leq
-    \frac{4(M+2)}{\alpha}$.
+    \frac{3}{\alpha}$.
     Applying Azuma's inequality as in the proof of Lemma~\ref{lem:ub}, this
     implies:
     \begin{displaymath}
         \P\big[\|\E[H]-H\|_{\infty}\geq\lambda\big] \leq
-        2\exp\left(-\frac{n\alpha\lambda^2}{4(M+2)} + 2\log m\right)
+        2\exp\left(-\frac{n\alpha\lambda^2}{3} + 2\log m\right)
     \end{displaymath}
-    Thus, if we take $\lambda=\sqrt{\frac{12(M+2)\log m}{\alpha
+    Thus, if we take $\lambda=\sqrt{\frac{9log m}{\alpha
     n^{1-\delta}}}$, $\|E[H]-H\|_{\infty}\leq\lambda$ w.p at least
     $1-e^{-n^{\delta}\log m}$. When $n^{1-\delta}\geq
-    \frac{M+2}{21\gamma\alpha}s^2\log m$, \eqref{eq:foo} implies
+    \frac{1}{28\gamma\alpha}s^2\log m$, \eqref{eq:foo} implies
     $
     \forall \Delta\in C(S),\;
     \Delta H\Delta \geq \frac{1}{2} \Delta \E[H]\Delta,
@@ -74,7 +83,7 @@ the proof.
     Proposition~\ref{prop:fi} follows.
 \end{proof}
 
-\subsection{Lower Bound}
+\subsection{Proof of Theorem~\ref{thm:lb}}
 
 Let us consider an algorithm $\mathcal{A}$ which verifies the recovery
 guarantee of Theorem~\ref{thm:lb}: there exists a probability distribution over