From 1d7ffddca772e540efba876748a2b6e1d3bbd9f4 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Wed, 4 Feb 2015 20:07:43 -0500
Subject: Fix constants in support recovery

---
 paper/sections/results.tex | 22 +++++++++++-----------
 1 file changed, 11 insertions(+), 11 deletions(-)

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

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 
-- 
cgit v1.2.3-70-g09d2

