approximatively sparse

1 files changed, 17 insertions, 5 deletions

diff --git a/paper/sections/results.tex b/paper/sections/results.tex
index ebe90bd..c26c499 100644
--- a/paper/sections/results.tex
+++ b/paper/sections/results.tex
@@ -1,10 +1,18 @@
+In this section, we exploit standard techniques in sparse recovery, and leveraging the simple nature of Generalized Linear models to address the standard problem of edge detection as well as the (new?) problem of coefficient estimation. We discuss both standard diffusion processes, and extend our analysis beyond sparse graphs to approximately sparse graphs.
+
+\paragraph{Recovering Edges vs. Recovering Coefficients} 
 There have been a series of papers arguing that the Lasso is an inappropriate variable selection method (see H.Zou and T.Hastie, Sarah van de Geer ...). In fact, the irrepresentability condition, though essentially necessary for variable selection, rarely holds in practical situations where correlation between variable occurs. We defer an extended analysis of this situation to Section~\ref{sec:assumptions}.
 
-Our approach is different. Rather than trying to perform variable selection by finding $\{j: \theta_j \neq 0\}$, we seek to obtain oracle inequalities by upper-bounding $\|\hat \theta - \theta^* \|_2$. It is easy to see that by thresholding $\hat \theta$, one recovers all `strong' parents without false positives, as shown in corollary~\ref{cor:variable_selection}. Interestingly, obtaining oracle inequalities depends on a the following restricted eigenvalue condition\footnote{which is less restrictive? Irrepresentability implies compatibility? But do we have comptability and do they have irrepresentability?} for a symetric matrix $\Sigma$ and set ${\cal C} := \{X \in \mathbb{R}^p : \|X_{S^c}\|_1 \leq 3 \|X_S\|_1 \}$
+Our approach is different. Rather than trying to perform variable selection by finding $\{j: \theta_j \neq 0\}$, we seek to upper-bound $\|\hat \theta - \theta^* \|_2$. We first apply standard techniques to obtain ${\cal O}(\sqrt{\frac{s \log m}{n}})$ in the case of sparse vectors, which is tight to a certain extent as we will show in Section ???. 
+
+It is easy to see that `parent selection' is a direct consequence of the previous result: by thresholding $\hat \theta$, one recovers all `strong' parents without false positives, as shown in corollary~\ref{cor:variable_selection}. 
+
+\paragraph{Main Theorem}
+Interestingly, obtaining oracle inequalities depends on the following restricted eigenvalue condition\footnote{which is less restrictive? Irrepresentability implies compatibility? But do we have comptability and do they have irrepresentability?} for a symetric matrix $\Sigma$ and set ${\cal C} := \{X \in \mathbb{R}^p : \|X_{S^c}\|_1 \leq 3 \|X_S\|_1 \} \cap \{ \|X\|_1 \leq 1 \}$
 
 \begin{equation}
 \nonumber
-\forall X \in {\cal C}, \| \Sigma X \|_2^2 \geq \gamma_n \|X\|_2^2 \qquad \ \quad \text{\bf (RE)}
+\forall X \in {\cal C}, \| \Sigma X \|_2^2 \geq \gamma_n \|X\|_2^2 \qquad \text{\bf (RE)}
 \end{equation}
 
 We cite the following Theorem from \cite{Negahban:2009}
@@ -13,12 +21,16 @@ We cite the following Theorem from \cite{Negahban:2009}
 \label{thm:neghaban}
 Suppose the true vector $\theta^*$ has support S of size s and the {\bf(RE)} assumption holds for the Hessian $\nabla^2 f(\theta^*)$, then by solving Eq.~\ref{eq:mle} for $\lambda_n \geq 2 \|\nabla f(\theta^*)\|_{\infty}$ we have:
 \begin{equation}
-\|\hat \theta - \theta^* \|_2 \leq \frac{\sqrt{s}\lambda_n}{\gamma_n}
+\|\hat \theta - \theta^* \|_2 \leq 3 \frac{\sqrt{s}\lambda_n}{\gamma_n}
 \end{equation}
 \end{theorem}
 
-\subsection{Independent Cascade Model}
+\paragraph{Relaxing the Sparsity Constraint}
 
+We can relax the sparsity constraint and express the upper-bound as a function of the best sparse approximation to $\theta^*$. This result is particularly relevant in cases where $\theta^*$ has few `strong' parents, and many `weak' parents, which is frequent in social networks. The results of section~\ref{subsec:icc} and section~\ref{subsec:ltm} that follow can be easily extended to the approximately-sparse case.
+
+\subsection{Independent Cascade Model}
+\label{subsec:icc}
 We analyse the previous conditions in the case of the Independent Cascade model. Lemma 1. provides a ${\cal O}(\sqrt{n})$-upper-bound w.h.p. on $\|\nabla f(\theta^*)\|$
 \begin{lemma}
 \label{lem:icc_lambda_upper_bound}
@@ -50,4 +62,4 @@ Note that $n$ is the number of measurements and not the number of cascades. This
 
 
 \subsection{Linear Threshold Model}
-
+\label{subsec:ltm}