diff options
| -rw-r--r-- | paper/sections/appendix.tex | 25 |
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 |