added more comments from reviewers

1 files changed, 63 insertions, 28 deletions

diff --git a/paper/sections/results.tex b/paper/sections/results.tex
index b156897..54fc587 100644
--- a/paper/sections/results.tex
+++ b/paper/sections/results.tex
@@ -92,6 +92,7 @@ $n$, which is different from the number of cascades. For example, in the case
 of the voter model with horizon time $T$ and for $N$ cascades, we can expect
 a number of measurements proportional to $N\times T$.
 
+{\color{red} Move this to the model section}
 Before moving to the proof of Theorem~\ref{thm:main}, note that interpreting it
 in the case of the Independent Cascade Model requires one more step. Indeed, to
 cast it as a generalized linear cascade model, we had to perform the
@@ -114,8 +115,7 @@ which gives a bound on the convergence rate of regularized estimators. We state
 their theorem in the context of $\ell_1$ regularization in
 Lemma~\ref{lem:negahban}.
 
-\begin{lemma}
-    \label{lem:negahban}
+\begin{lemma} \label{lem:negahban}
 Let ${\cal C}(S) \defeq \{ \Delta \in \mathbb{R}^m\,|\,\|\Delta_S\|_1 \leq
 3 \|\Delta_{S^c}\|_1 \}$. Suppose that:
 \begin{multline}
@@ -142,6 +142,8 @@ implied by the (RE)-condition.. The upper bound
 on the $\ell_{\infty}$ norm of $\nabla\mathcal{L}(\theta^*)$ is given by
 Lemma~\ref{lem:ub}.
 
+{\color{red} explain usefulness/interpretation and contribution}
+{\color{red} Sketch proof, full proof in appendix}
 \begin{lemma}
 \label{lem:ub}
 Assume {\bf(LF)} holds for some $\alpha>0$. For any $\delta\in(0,1)$:
@@ -245,32 +247,35 @@ In other words, the closer $\theta^*$ is to being sparse, the smaller the
 price, and we recover the results of Section~\ref{sec:main_theorem} in the
 limit of exact sparsity. These results are formalized in the following theorem,
 which is also a consequence of Theorem 1 in \cite{Negahban:2009}.
+{\color{red} Include full proof in appendix}
 
 \begin{theorem}
 \label{thm:approx_sparse}
-Suppose the {\bf(RE)} assumption holds for the Hessian $\nabla^2
-f(\theta^*)$ and $\tau_{\mathcal{L}}(\theta^*) = \frac{\kappa_2\log m}{n}\|\theta^*\|_1$
-on the following set:
+Suppose the {\bf(RE)} assumption holds for the Hessian $\nabla^2 f(\theta^*)$
+and $\tau_{\mathcal{L}}(\theta^*) = \frac{\kappa_2\log m}{n}\|\theta^*\|_1$ on
+the following set:
 \begin{align}
 \nonumber
 {\cal C}' \defeq & \{X \in \mathbb{R}^p : \|X_{S^c}\|_1 \leq 3 \|X_S\|_1
 + 4 \|\theta^* - \theta^*_{\lfloor s \rfloor}\|_1 \} \\ \nonumber
 & \cap \{ \|X\|_1 \leq 1 \}
 \end{align}
-If the number of measurements $n\geq \frac{64\kappa_2}{\gamma}s\log m$, then
-by solving \eqref{eq:pre-mle} for $\lambda \defeq 2\sqrt{\frac{\log m}{\alpha n^{1 - \delta}}}$ we have:
+If the number of measurements $n\geq \frac{64\kappa_2}{\gamma}s\log m$, then by
+solving \eqref{eq:pre-mle} for $\lambda \defeq 2\sqrt{\frac{\log m}{\alpha n^{1
+- \delta}}}$ we have:
 \begin{align*}
-    \|\hat \theta - \theta^* \|_2 \leq
-    \frac{3}{\gamma} \sqrt{\frac{s\log m}{\alpha n^{1-\delta}}}
-    + 4 \sqrt[4]{\frac{s\log m}{\gamma^4\alpha n^{1-\delta}}} \|\theta^* - \theta^*_{\lfloor s \rfloor}\|_1
+    \|\hat \theta - \theta^* \|_2 \leq \frac{3}{\gamma} \sqrt{\frac{s\log
+    m}{\alpha n^{1-\delta}}} + 4 \sqrt[4]{\frac{s\log m}{\gamma^4\alpha
+    n^{1-\delta}}} \|\theta^* - \theta^*_{\lfloor s \rfloor}\|_1
 \end{align*}
 \end{theorem}
 
-As before, edge recovery is a consequence of upper-bounding $\|\theta^* - \hat \theta\|_2$
+As before, edge recovery is a consequence of upper-bounding $\|\theta^* - \hat
+\theta\|_2$
 
 \begin{corollary}
-    Under the same assumptions as Theorem~\ref{thm:approx_sparse}, if the number of
-    measurements verifies: \begin{equation}
+    Under the same assumptions as Theorem~\ref{thm:approx_sparse}, if the number
+    of measurements verifies: \begin{equation}
         n > \frac{9}{\alpha\gamma^2\epsilon^2}\left(1+
         \frac{16}{\epsilon^2}\| \theta^* - \theta^*_{\lfloor
     s\rfloor}\|_1\right)s\log m
@@ -279,8 +284,6 @@ then similarly: ${\cal S}^*_{\eta + \epsilon} \subset \hat {\cal S}_\eta
 \subset {\cal S}^*$ w.p. at least $1-\frac{1}{m}$.
 \end{corollary}
 
-
-
 \subsection{Restricted Eigenvalue Condition}
 \label{sec:re}
 
@@ -312,6 +315,10 @@ a re-weighted Gram matrix of the observations. In other words, the restricted
 eigenvalue condition sates that the observed set of active nodes are not
 too collinear with each other.
 
+{\color{red} if the function is strictly log-convex, then equivalent -> explain
+what the gram matrix is (explanation)}
+
+{\color{red} move to model section, small example}
 In the specific case of ``logistic cascades'' (when $f$ is the logistic
 function), the Hessian simplifies to $\nabla^2\mathcal{L}(\theta^*)
 = \frac{1}{|\mathcal{T}|}XX^T$ where $X$ is the observation matrix $[x^1 \ldots
@@ -351,13 +358,14 @@ again non restrictive in the (IC) model and (V) model.
 
 \begin{proposition}
     \label{prop:fi}
-    Suppose $\E[\nabla^2\mathcal{L}(\theta^*)]$ verifies the $(S,\gamma)$-{\bf (RE)}
-    condition and assume {\bf (LF)} and {\bf (LF2)}. For $\delta> 0$, if $n^{1-\delta}\geq
-\frac{M+2}{21\gamma\alpha}s^2\log m
-    $, then $\nabla^2\mathcal{L}(\theta^*)$ verifies the $(S,\frac{\gamma}{2})$-(RE)
+    Suppose $\E[\nabla^2\mathcal{L}(\theta^*)]$ verifies the $(S,\gamma)$-{\bf
+    (RE)} condition and assume {\bf (LF)} and {\bf (LF2)}. For $\delta> 0$, if
+    $n^{1-\delta}\geq \frac{M+2}{21\gamma\alpha}s^2\log m $, then
+    $\nabla^2\mathcal{L}(\theta^*)$ verifies the $(S,\frac{\gamma}{2})$-(RE)
     condition, w.p $\geq 1-e^{-n^\delta\log m}$.
 \end{proposition}
 
+{\color{red} sketch proof, full (AND BETTER) proof in appendix}
 \begin{proof}Writing $H\defeq \nabla^2\mathcal{L}(\theta^*)$, if
     $ \forall\Delta\in C(S),\;
         \|\E[H] - H]\|_\infty\leq \lambda $
@@ -366,8 +374,8 @@ again non restrictive in the (IC) model and (V) model.
     \begin{equation}
         \label{eq:foo}
     \forall \Delta\in C(S),\;
-    \Delta H\Delta \geq 
-    \Delta \E[H]\Delta(1-32s\lambda/\gamma) 
+    \Delta H\Delta \geq
+    \Delta \E[H]\Delta(1-32s\lambda/\gamma)
     \end{equation}
     Indeed, $
     |\Delta(H-E[H])\Delta| \leq 2\lambda \|\Delta\|_1^2\leq
@@ -407,11 +415,16 @@ likelihood function also known as the {\it (S,s)-irrepresentability} condition.
 
 \begin{comment}
 \begin{definition}
-Following similar notation, let $Q^* \defeq \nabla^2 f(\theta^*)$. Let $S$ and $S^c$ be the set of indices of all the parents and non-parents respectively and $Q_{S,S}$, $Q_{S^c,S}$, $Q_{S, S^c}$, and $Q_{S^c, S^c}$ the induced sub-matrices. Consider the following constant:
+Following similar notation, let $Q^* \defeq \nabla^2 f(\theta^*)$. Let $S$ and
+$S^c$ be the set of indices of all the parents and non-parents respectively and
+$Q_{S,S}$, $Q_{S^c,S}$, $Q_{S, S^c}$, and $Q_{S^c, S^c}$ the induced
+sub-matrices. Consider the following constant:
 \begin{equation}
-\nu_{\text{irrepresentable}}(S) \defeq \max_{\tau \in \mathbb{R}^p \ :\ \| \tau \|_{\infty} \leq 1} \|Q_{S^c, S} Q_{S, S}^{-1} \tau\|_{\infty}
+\nu_{\text{irrepresentable}}(S) \defeq \max_{\tau \in \mathbb{R}^p \ :\ \| \tau
+\|_{\infty} \leq 1} \|Q_{S^c, S} Q_{S, S}^{-1} \tau\|_{\infty}
 \end{equation}
-The (S,s)-irrepresentability holds if $\nu_{\text{irrepresentable}}(S) < 1 - \epsilon$ for $\epsilon > 0$
+The (S,s)-irrepresentability holds if $\nu_{\text{irrepresentable}}(S) < 1 -
+\epsilon$ for $\epsilon > 0$
 \end{definition}
 \end{comment}
 
@@ -423,7 +436,11 @@ the {\bf(RE)} condition for $\ell_2$-recovery.
 \begin{comment}
 \begin{proposition}
 \label{prop:irrepresentability}
-If the irrepresentability condition holds with $\epsilon > \frac{2}{3}$, then the restricted eigenvalue condition holds with constant  $\gamma_n \geq \frac{ (1 - 3(1 -\epsilon))^2 \lambda_{\min}^2}{4s}n$, where $\lambda_{\min} > 0$ is the smallest eigenvalue of $Q^*_{S,S}$, on which the results of \cite{Daneshmand:2014} also depend.
+If the irrepresentability condition holds with $\epsilon > \frac{2}{3}$, then
+the restricted eigenvalue condition holds with constant  $\gamma_n \geq \frac{
+(1 - 3(1 -\epsilon))^2 \lambda_{\min}^2}{4s}n$, where $\lambda_{\min} > 0$ is
+the smallest eigenvalue of $Q^*_{S,S}$, on which the results of
+\cite{Daneshmand:2014} also depend.
 \end{proposition}
 \end{comment}
 
@@ -434,18 +451,36 @@ a correlation between variables. Consider the following simplified example from
 \cite{vandegeer:2011}:
 \begin{equation}
 \nonumber
-\left( 
+\left(
 \begin{array}{cccc}
 I_s & \rho J \\
 \rho J & I_s \\
 \end{array}
 \right)
 \end{equation}
-where $I_s$ is the $s \times s$ identity matrix, $J$ is the all-ones matrix and $\rho \in \mathbb{R}^+$. It is easy to see that $\nu_{\text{irrepresentable}}(S) = \rho s$ and $\lambda_{\min}(Q) \geq 1 - \rho$, such that for any $\rho > \frac{1}{s}$ and $\rho < 1$, the restricted eigenvalue holds trivially but the (S,s)-irrepresentability does not hold.
+where $I_s$ is the $s \times s$ identity matrix, $J$ is the all-ones matrix and
+$\rho \in \mathbb{R}^+$. It is easy to see that $\nu_{\text{irrepresentable}}(S)
+= \rho s$ and $\lambda_{\min}(Q) \geq 1 - \rho$, such that for any $\rho >
+\frac{1}{s}$ and $\rho < 1$, the restricted eigenvalue holds trivially but the
+(S,s)-irrepresentability does not hold.
 
 
 \begin{lemma}
-Let ${\cal C}({\cal M}, \bar {\cal M}^\perp, \theta^*) \defeq \{ \Delta \in \mathbb{R}^p | {\cal R}(\Delta_{\bar {\cal M}^\perp} \leq 3 {\cal R}(\Delta_{\bar {\cal M}} + 4 {\cal R}(\theta^*_{{\cal M}^\perp}) \}$, where $\cal R$ is a \emph{decomposable} regularizer with respect to $({\cal M}, \bar {\cal M}^\perp)$, and $({\cal M}, \bar {\cal M})$ are two subspaces such that  ${\cal M} \subseteq \bar {\cal M}$. Suppose that $\exists \kappa_{\cal L} > 0, \; \exists \tau_{\cal L}, \; \forall \Delta \in {\cal C}, \; {\cal L}(\theta^* + \Delta) - {\cal L}(\theta^*) - \langle \Delta {\cal L}(\theta^*), \Delta \rangle \geq \kappa_{\cal L} \|\Delta\|^2 - \tau_{\cal L}^2(\theta^*)$. Let $\Psi({\cal M}) \defeq \sup_{u \in {\cal M} \backslash \{0\}} \frac{{\cal R}(u)}{\|u\|}$. Finally suppose that $\lambda \geq 2 {\cal R}(\nabla {\cal L}(\theta^*))$, where ${\cal R}^*$ is the conjugate of ${\cal R}$. Then: $$\|\hat \theta_\lambda - \theta^* \|^2 \leq 9 \frac{\lambda^2}{\kappa_{\cal L}}\Psi^2(\bar {\cal M}) + \frac{\lambda}{\kappa_{\cal L}}\{2 \tau^2_{\cal L}(\theta^*) + 4 {\cal R}(\theta^*_{{\cal M}^\perp}\}$$
+Let ${\cal C}({\cal M}, \bar {\cal M}^\perp, \theta^*) \defeq \{ \Delta \in
+\mathbb{R}^p | {\cal R}(\Delta_{\bar {\cal M}^\perp} \leq 3 {\cal
+R}(\Delta_{\bar {\cal M}} + 4 {\cal R}(\theta^*_{{\cal M}^\perp}) \}$, where
+$\cal R$ is a \emph{decomposable} regularizer with respect to $({\cal M}, \bar
+{\cal M}^\perp)$, and $({\cal M}, \bar {\cal M})$ are two subspaces such that
+${\cal M} \subseteq \bar {\cal M}$. Suppose that $\exists \kappa_{\cal L} > 0,
+\; \exists \tau_{\cal L}, \; \forall \Delta \in {\cal C}, \; {\cal L}(\theta^* +
+\Delta) - {\cal L}(\theta^*) - \langle \Delta {\cal L}(\theta^*), \Delta \rangle
+\geq \kappa_{\cal L} \|\Delta\|^2 - \tau_{\cal L}^2(\theta^*)$. Let $\Psi({\cal
+M}) \defeq \sup_{u \in {\cal M} \backslash \{0\}} \frac{{\cal R}(u)}{\|u\|}$.
+Finally suppose that $\lambda \geq 2 {\cal R}(\nabla {\cal L}(\theta^*))$, where
+${\cal R}^*$ is the conjugate of ${\cal R}$. Then: $$\|\hat \theta_\lambda -
+\theta^* \|^2 \leq 9 \frac{\lambda^2}{\kappa_{\cal L}}\Psi^2(\bar {\cal M}) +
+\frac{\lambda}{\kappa_{\cal L}}\{2 \tau^2_{\cal L}(\theta^*) + 4 {\cal
+R}(\theta^*_{{\cal M}^\perp}\}$$
 \end{lemma}
 
 \subsection{The Independent Cascade Model}