From 0a78933792790017aa0fe87a18b60bed071cafe1 Mon Sep 17 00:00:00 2001
From: jeanpouget-abadie <jean.pougetabadie@gmail.com>
Date: Thu, 22 Jan 2015 09:51:02 -0500
Subject: created ICML folder

---
 notes/maximum_likelihood_approach.tex | 32 +++++++++++++++++++-------------
 1 file changed, 19 insertions(+), 13 deletions(-)

(limited to 'notes/maximum_likelihood_approach.tex')

diff --git a/notes/maximum_likelihood_approach.tex b/notes/maximum_likelihood_approach.tex
index c145b0c..4a22158 100644
--- a/notes/maximum_likelihood_approach.tex
+++ b/notes/maximum_likelihood_approach.tex
@@ -110,15 +110,13 @@ We are going to explicitate a constant $\gamma$ such that: $\forall \Delta \in {
 Suppose that $\forall k$, $\mathbb{E}_{S(k)} \left[ \frac{1}{p_i} \right] \geq 1 + \alpha$, then with probability greater than $1 - 2 p e^{-2 \alpha^2 (1-c)^2p_{\min}^2 p_{\text{init}}^2 N}$, $$\forall k, \ Z_k > c \alpha p_{\text{init}} N$$
 \end{lemma}
 
-{\color{red} The following is not exactly correct!} Since the expectation must be taken conditioned on the probability that at least one parent is active such that $p_i$ is not 0! This does change things.
-
 \begin{proof}
-Let $S(k)$ denote the active set conditioned on the fact that node $k$ is active.
+Let $S(k)$ denote the active set conditioned on the fact that node $k$ is active AND that one parent is active. We denote $p_{S(k)}$ the probability that the active set verifies the previous two conditions.
 \begin{align}
 \nonumber
-\mathbb{E}[Z^i_k] & = \mathbb{P}(x^i_k = 1) \mathbb{E}_{S(k)} \left[ \mathbb{E}[b^i | S(k)] \frac{1 - p_i}{p_i^2} \right] \\ \nonumber
-& = p_{\text{init}} \left( \mathbb{E}_{S(k)} \left[ \frac{1}{p_i} \right] - 1 \right) \\ \nonumber
-& \geq \alpha p_{\text{init}} \quad \text{by assumption}
+\mathbb{E}[Z^i_k] & = p_{S(k)} \mathbb{E}_{S(k)} \left[ \mathbb{E}[b^i | S(k)] \frac{1 - p_i}{p_i^2} \right] \\ \nonumber
+& = p_{S(k)} \left( \mathbb{E}_{S(k)} \left[ \frac{1}{p_i} \right] - 1 \right) \\ \nonumber
+& \geq \alpha p_{S(k)} \quad \text{by assumption}
 \end{align}
 
 Note that $|Z^i_k| < \frac{1}{p_{\text{min}}^2}$ {\it a.s.}. By Hoeffding's first inequality, for $0<c <1$,
@@ -126,37 +124,44 @@ Note that $|Z^i_k| < \frac{1}{p_{\text{min}}^2}$ {\it a.s.}. By Hoeffding's firs
 \begin{align}
 \nonumber
 \mathbb{P}\left(Z_k < c \alpha p_{\text{init}} N \right) & < 2 e^{- \frac{2(1-c)^2}{Nb^2} \left( \mathbb{E}_{S(k)} \left[ \frac{1}{p_i} \right] - 1 \right)^2} \\ \nonumber
-& < 2 e^{-2 \alpha^2 (1-c)^2p_{\min}^2 p_{\text{init}}^2 N}
+& < 2 e^{-2 \alpha^2 (1-c)^2p_{\min}^2 p_{S(k)}^2 N}
 \end{align}
 
 We conclude by union bound.
 \end{proof}
 
 \begin{lemma}
-Suppose that $\forall k,j$, $1 + \alpha \leq \mathbb{E}_{S(k, j)} \left[ \frac{1}{p_i} \right] \leq 1 + \beta$, then with probability greater than $1 - pe^{-2 \alpha^2 (1-c)^2p_{\min}^2 p_{\text{init}}^4 N}$, $$\forall k,j, \ Z_{k,j} < c \beta p_{\text{init}}^2 N$$
+Suppose that $\forall k,j$, $1 + \alpha \leq \mathbb{E}_{S(k, j)} \left[ \frac{1}{p_i} \right] \leq 1 + \beta$, then with probability greater than $1 - pe^{-2 \alpha^2 (1-c)^2p_{\min}^2 p_{S(k,j)}^2 N}$, $$\forall k,j, \ Z_{k,j} < c \beta p_{S(k,j))} N$$
 \end{lemma}
 
 \begin{proof}
 We follow the same reasoning as Lemma~\ref{lem:first_term}:
 \begin{align}
 \nonumber
-\mathbb{E}[Z^i_{k,j}] & = p_{\text{init}}^2 \left( \mathbb{E}_{S(k,j)} \left[ \frac{1}{p_i} \right] - 1 \right) \\ \nonumber
-& \leq \beta p_{\text{init}}^2 \quad \text{by assumption}
+\mathbb{E}[Z^i_{k,j}] & = p_{S(k,j)} \left( \mathbb{E}_{S(k,j)} \left[ \frac{1}{p_i} \right] - 1 \right) \\ \nonumber
+& \leq \beta p_{S(k,j)} \quad \text{by assumption}
 \end{align}
 
 By Hoeffding's second inequality, for $0 < c < 1$,
 \begin{align}
 \nonumber
-\mathbb{P}\left(Z_{k,j} > c \beta p_{\text{init}}^2 N \right) & \leq e^{- \frac{2(1-c)^2}{Nb^2} \left( \mathbb{E}_{S(k,j)} \left[ \frac{1}{p_i} \right] - 1 \right)^2} \\ \nonumber
-& \leq e^{-2 \alpha^2 (1-c)^2p_{\min}^2 p_{\text{init}}^4 N} 
+\mathbb{P}\left(Z_{k,j} > c \beta p_{S(k,j)} N \right) & \leq e^{- \frac{2(1-c)^2}{Nb^2} \left( \mathbb{E}_{S(k,j)} \left[ \frac{1}{p_i} \right] - 1 \right)^2} \\ \nonumber
+& \leq e^{-2 \alpha^2 (1-c)^2p_{\min}^2 p_{S(k,j)}^2 N} 
 \end{align}
 We conclude by union bound.
 \end{proof}
 
 \begin{proposition}
-Suppose that $\forall k,j$, $1 + \alpha \leq \mathbb{E}_{S(k, j)} \left[ \frac{1}{p_i} \right] \leq 1 + \beta$, then with probability greater than $1 - XXX$, condition~\ref{eq:RSC_condition} is met with $\gamma_n = \gamma n$ where $\gamma := p_{\text{init}}(\alpha - 16 \sqrt{s} \beta p_{\text{init}})$
+Suppose that $\forall k,j$, $1 + \alpha \leq \mathbb{E}_{S(k, j)} \left[ \frac{1}{p_i} \right] \leq 1 + \beta$, then with probability greater than $1 - XXX$, condition~\ref{eq:RSC_condition} is met with $\gamma_n = \gamma n$ where $\gamma := \alpha p_{S(k)} - 16 \sqrt{s} \beta p_{S(k,j)}$
 \end{proposition}
 
+\begin{proof}
+(Sketch) By the triangle inequality followed by MacLaurin's inequality,
+\begin{align}
+\mid \frac{2}{\binom{n}{2}} \sum_{i<j} \Delta_k \Delta_j \mid & \leq \frac{1}{n^2} \sum_k \mid \Delta_k \mid \nonumber \\
+\mid 2 \sum_{i<j} \Delta_k \Delta_j \mid & \leq \|\Delta\|_1 \leq 4 \sqrt{s} \| \Delta \|_2 \quad \text{ since } \Delta \in {\cal C} \nonumber
+\end{align}
+\end{proof}
 
 \paragraph{Hoeffding's inequality}
 
@@ -197,6 +202,7 @@ For $t \in \mathbb{R}$ and independent variables $Z_i$ such that $|Z_i|<b$ {\it
 % \subsection*{Second term}
 % We are now going to find an upper-bound on the term $\sum_i b^i x^i_k x^i_j \frac{1 - p_i}{p_i^2}$.
 
+
 \section*{Conclusion}
 
 Suppose we show that Condition~\ref{eq:RSC_condition} is met for $\gamma_n = \gamma N$, then we have the following theorems:
-- 
cgit v1.2.3-70-g09d2