diff options
Diffstat (limited to 'paper')
| -rw-r--r-- | paper/sections/model.tex | 6 | ||||
| -rw-r--r-- | paper/sections/results.tex | 22 |
2 files changed, 15 insertions, 13 deletions
diff --git a/paper/sections/model.tex b/paper/sections/model.tex index d3403ef..bbfd96c 100644 --- a/paper/sections/model.tex +++ b/paper/sections/model.tex @@ -78,7 +78,8 @@ Defining $\Theta_{i,j} \defeq \log(1-p_{i,j})$, this can be rewritten as: = 1 - e^{\inprod{\theta_j}{X^t}} \end{equation} -Therefore, the independent cascade model is a Generalized Linear Cascade model with canonical link function $f : z \mapsto 1 - e^z$ +Therefore, the independent cascade model is a Generalized Linear Cascade model +with canonical link function $f : z \mapsto 1 - e^z$. \subsubsection{The Linear Voter Model} @@ -93,7 +94,8 @@ step $t$, then we have: \tag{V} \end{equation} -Therefore, the independent cascade model is a Generalized Linear Cascade model with canonical link function $f: z \mapsto z$ +Therefore, the independent cascade model is a Generalized Linear Cascade model +with canonical link function $f: z \mapsto z$. % \subsection{The Linear Threshold Model} diff --git a/paper/sections/results.tex b/paper/sections/results.tex index 128a79f..6fba6b2 100644 --- a/paper/sections/results.tex +++ b/paper/sections/results.tex @@ -63,7 +63,7 @@ Assume the Hessian $\nabla^2\mathcal{L}(\theta^*)$ satisfies the $(S,\gamma)$-{\bf(RE)} for some $\gamma > 0$ and that {\bf (LF)} holds for some $\alpha > 0$. For any $\delta\in(0,1)$, let $\hat{\theta}$ be the solution of \eqref{eq:pre-mle} with $\lambda \defeq 2\sqrt{\frac{\log m}{\alpha n^{1 -- \delta}}}$ then: +- \delta}}}$, then: \begin{equation} \label{eq:sparse} \|\hat \theta - \theta^* \|_2 @@ -176,30 +176,30 @@ Under the same assumptions of Theorem~\ref{thm:main}, let $\hat {\cal S}_\eta $\epsilon>0$ and $\epsilon < \eta$, let ${\cal S}^*_{\eta + \epsilon} \defeq \{ i \in \{1,\ldots,m\} :\theta_i > \eta +\epsilon \}$ be the set of all true `strong' parents. Suppose the number of measurements verifies: -$ n > \frac{9}{\alpha}\frac{\gamma^2}{\epsilon^2} s \log m $. +$ n > \frac{9s\log m}{\alpha\gamma^2\epsilon^2}$. Then with probability $1-\frac{1}{m}$, ${\cal S}^*_{\eta + \epsilon} \subseteq \hat {\cal S}_\eta \subseteq {\cal S}^*$. In other words we recover all `strong' parents and no `false' parents. \end{corollary} \begin{proof} -By choosing $\delta = 0$, if $n>\frac{9}{\alpha}\frac{\gamma^2}{\epsilon^2} s \log m$, -then $\|\hat \theta-\theta\|_2 < \epsilon < \eta$ with probability -$1-\frac{1}{m}$. If $\theta_i = 0$ and $\hat \theta > \eta$, then $\|\hat -\theta - \theta\|_2 \geq |\hat \theta_i-\theta_j| > \eta$, which is -a contradiction. Therefore we get no false positives. If $\theta_i \leq \eta -+ \epsilon$, then $|\hat{\theta}_i- \theta_i| < \epsilon \implies -\theta_j > \eta$. Therefore, we get all strong parents. +By choosing $\delta = 0$, if $ n > \frac{9s\log +m}{\alpha\gamma^2\epsilon^2}$, then $\|\hat \theta-\theta\|_2 < \epsilon < \eta$ +with probability $1-\frac{1}{m}$. If $\theta_i = 0$ and $\hat \theta > \eta$, +then $\|\hat \theta - \theta\|_2 \geq |\hat \theta_i-\theta_j| > \eta$, which +is a contradiction. Therefore we get no false positives. If $\theta_i \leq \eta ++ \epsilon$, then $|\hat{\theta}_i- \theta_i| < \epsilon \implies \theta_j +> \eta$. Therefore, we get all strong parents. \end{proof} Assuming we know a lower bound $\alpha$ on $\Theta_{i,j}$, Corollary~\ref{cor:variable_selection} can be applied to the Graph Inference problem in the following manner: pick $\epsilon = \frac{\eta}{2}$ and $\eta = \frac{\alpha}{3}$, then $S_{\eta+\epsilon}^* = S$ provided that -$n=\Omega\left(\frac{\gamma^2}{\alpha^3}s\log m\right)$. That is, the support +$n=\Omega\left(\frac{s\log m}{\alpha^3\gamma^2}\right)$. That is, the support of $\theta^*$ can be found by thresholding $\hat{\theta}$ to the level $\eta$. -\subsection{Relaxing the Sparsity Constraint} +\subsection{Approximate sparsity} \label{sec:relaxing_sparsity} In practice, exact sparsity is rarely verified. For social networks in particular, it is more realistic to assume that each node has few strong `parents' and many `weak' parents. Rather than obtaining an impossibility result in this situation, we show that we pay a small price for relaxing the sparsity constraint. If we let $\theta^*_{\lfloor s \rfloor}$ be the best s-sparse approximation to $\theta^*$ defined as |