From 347489694571148e0cb940a96fe621a7394b5bfa Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Wed, 4 Feb 2015 15:49:24 -0500
Subject: rewriting of 3.1 + some minor changes

---
 paper/sections/appendix.tex | 44 --------------------------------------------
 1 file changed, 44 deletions(-)

(limited to 'paper/sections/appendix.tex')

diff --git a/paper/sections/appendix.tex b/paper/sections/appendix.tex
index 57658b4..2f0162e 100644
--- a/paper/sections/appendix.tex
+++ b/paper/sections/appendix.tex
@@ -7,50 +7,6 @@
 \end{multline*}
 \end{comment}
 
-\subsection{Upper-bound for $\|\nabla \mathcal{L}(\theta^*)\|_\infty$}
-
-The gradient of $\mathcal{L}$ (as a function of $\theta$) is given by:
-\begin{multline*}
-    \nabla \mathcal{L}(\theta) =
-    \frac{1}{|\mathcal{T}|}\sum_{t\in \mathcal{T}}x^t\bigg[
-        x_i^{t+1}\frac{f'}{f}(\inprod{\theta_i}{x^t})\\
-    - (1-x_i^{t+1})\frac{f'}{1-f}(\inprod{\theta_i}{x^t})\bigg]
-\end{multline*}
-
-Let us focus on one coordinate of the gradient, the partial derivative $\partial_j
-\mathcal{L}(\theta)$ with respect to the $j$-th coordinate.  Writing
-$\partial_j\mathcal{L}(\theta)
-= \frac{1}{|\mathcal{T}|}\sum_{t\in\mathcal{T}} Y_t$ and since
-$\E[x_i^{t+1}|x^t]= f(\inprod{\theta_i}{x^t})$, we have that $\E[Y_{t+1}|Y_t]
-= 0$. Hence $Z_t = \sum_{k=1}^t Y_k$ is a martingale.
-
-Let us assume that we can bound $\frac{f'}{f}(\theta_i\cdot x^t)$ and
-$\frac{f'}{1-f}(\theta_i\cdot x^t)$ almost surely and in absolute value by
-$\frac{1}{\eta}$. It is easy to verify that this will be true if for all
-$(i,j)\in E$, $\delta\leq p_{i,j}\leq 1-\delta$ in the Voter model and when
-$p_{i,j}\leq 1-\delta$ in the Independent Cascade model.
-
-Under the assumption of the previous paragraph, we have almost surely
-$|Z_{t+1}-Z_t|\leq \frac{1}{\eta}$ and we can apply Azuma's inequality to the
-martingale $Z_t$:
-\begin{displaymath}
-    \P\big[|Z_{\mathcal{T}}|\geq \lambda\big]\leq
-    2\exp\left(\frac{-\lambda^2\eta}{2n}\right)
-\end{displaymath}
-
-Applying a union bound to have the previous inequality hold for all coordinates
-of $\nabla\mathcal{L}(\theta)$ implies the following bound:
-\begin{align*}
-    \P\big[\|\nabla\mathcal{L}(\theta)\|_{\infty}\geq \lambda \big]
-    &\leq 2m\exp\left(\frac{-\lambda^2n\eta}{2}\right)\\
-    &= 2\exp\left(\frac{-\lambda^2n\eta}{2}+\log m\right)
-\end{align*}
-
-Choosing $\lambda\defeq 2\sqrt{\frac{\log m}{\eta n^{1-\delta}}}$ concludes the
-proof of Lemma~\ref{lem:icc_lambda_upper_bound}.
-
-
-
 
 \subsection{Proposition~\ref{prop:irrepresentability}}
 In the words and notation of Theorem 9.1 in \cite{vandegeer:2009}: 
-- 
cgit v1.2.3-70-g09d2

