From 220d23bc64be0254bcbcb9adc4a26ef511d5543c Mon Sep 17 00:00:00 2001
From: jeanpouget-abadie <jean.pougetabadie@gmail.com>
Date: Sat, 31 Jan 2015 19:20:32 -0500
Subject: last jpa saturday changes

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

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

diff --git a/paper/sections/results.tex b/paper/sections/results.tex
index 2831a51..0c2c7e5 100644
--- a/paper/sections/results.tex
+++ b/paper/sections/results.tex
@@ -51,7 +51,7 @@ Then with probability $1-\frac{1}{m}$, ${\cal S}^*_{\eta + \epsilon} \subset \ha
 Suppose $\theta$ is exactly s-sparse. By choosing $\delta = 0$, if $n>\frac{36}{p_{\min}\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 = \eta + \epsilon$, then $|\hat \theta_i - (\eta+\epsilon)| < \epsilon/2 \implies \theta_j > \eta + \epsilon/2$. Therefore, we get all strong parents.
 \end{proof}
 
-Note that in order to allow for \emph{perfect recovery}, we must estimate $p_{\min}$ within $\epsilon$ and set $\eta \defeq p_{\min} - \epsilon$.
+Note that if we want \emph{perfect recovery} of all edges, we must estimate $p_{\min}$ within $\epsilon'$ and set $\eta \defeq p_{\min} - \epsilon'$
 
 \subsection{Relaxing the Sparsity Constraint}
 
@@ -91,10 +91,10 @@ then similarly: ${\cal S}^*_{\eta + \epsilon} \subset \hat {\cal S}_\eta \subset
 We begin our analysis with the following simple lemma:
 \begin{lemma}
 \label{lem:theta_p_upperbound}
-$\|\theta - \theta^* \|_2 \geq \|p - p^*\|_2$
+$\|\theta - \theta' \|_2 \geq \|p - p^*\|_2$ and $\|\theta_{\lfloor s \rfloor}\|_1 \geq \| p_{\lfloor s \rfloor} \|_1$
 \end{lemma}
 \begin{proof}
-Using the inequality $\forall x>0, \; \log x \geq 1 - \frac{1}{x}$, we have $|\log (1 - p) - \log (1-p')| \geq \max(1 - \frac{1-p}{1-p'}, 1 - \frac{1-p'}{1-p}) \geq \max( p-p', p'-p)$. The result follows easily.
+Using the inequality $\forall x>0, \; \log x \geq 1 - \frac{1}{x}$, we have $|\log (1 - p) - \log (1-p')| \geq \max(1 - \frac{1-p}{1-p'}, 1 - \frac{1-p'}{1-p}) \geq \max( p-p', p'-p)$. The second result follows easily from the monotonicity of $\log$ and $\forall x > 0, | \log (1 -x) | \geq x$
 \end{proof}
 
 In other words, finding an upper-bound for the estimation error of the `effective' parameters $\theta_{i,j} \defeq \log(1-p_{i,j})$ provides immediately an upper-bound for the estimation error of the true parameters $(p_{i,j})_{i,j}$.
-- 
cgit v1.2.3-70-g09d2

