1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
\begin{comment}
\begin{multline*}
\nabla^2 \mathcal{L}(\theta) =
\frac{1}{|\mathcal{T}|}\sum_{t\in \mathcal{T}}x^t(x^t)^T\bigg[
x_i^{t+1}\frac{f''f - f'^2}{f^2}(\inprod{\theta_i}{x^t})\\
- (1-x_i^{t+1})\frac{f''(1-f) + f'^2}{(1-f)^2}(\inprod{\theta_i}{x^t})\bigg]
\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}:
\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.
|
