fixing typos reportYaron

1 files changed, 16 insertions, 16 deletions

diff --git a/notes/reportYaron.tex b/notes/reportYaron.tex
index 3f31ecd..f3189cb 100644
--- a/notes/reportYaron.tex
+++ b/notes/reportYaron.tex
@@ -22,18 +22,18 @@ Given a set of observed cascades, the graph reconstruction problem consists of f
 There have been several works tackling the graph reconstruction problem in variants of the independent cascade. We briefly summarize their results and approaches below.
 
 \begin{itemize}
-\item Manuel Gomez-Rodriguez, Jure Leskovec, and Andreas Klause were amongst the first to tackle the problem of graph reconstruction from cascade observation \cite{gomez}. Their first method \textsc{NetInf}, and a series of other similar methods published subsequently, solves a heuristic which approximates a NP-hard maximum-likelihood formulation. Unfortunately \textsc{NetInf} has no known theoretical guarantees. One difficulty with comparing ourselves to their heuristic is that they assume a continuous time independent cascade model, which is close but un-adaptable to our framework. Namely, as we will see in Section~\ref{sec:icc}, nodes in our model cannot influence nodes beyond the time step at which they are active.
-\item Their paper was later followed by a publication from Praneeth Netrapalli and Sujay Sanghavi \cite{netrapalli}, which provided two algorithms with several theoretical guarantees. 
+\item Manuel Gomez-Rodriguez, Jure Leskovec, and Andreas Klause were amongst the first to tackle the problem of graph reconstruction from cascade observations \cite{gomez}. Their first method \textsc{NetInf}, and a series of other similar methods published subsequently, solves a heuristic which approximates a NP-hard maximum-likelihood formulation. Unfortunately \textsc{NetInf} has no known theoretical guarantees. One difficulty with comparing ourselves to their heuristic is that they assume a continuous time model, which is close but un-adaptable to our framework. Namely, as we will see in Section~\ref{sec:icc}, nodes in our model cannot influence nodes beyond the time step at which they are active.
+\item Their paper was later followed by a publication from Praneeth Netrapalli and Sujay Sanghavi \cite{netrapalli}, which provides two algorithms with interesting theoretical guarantees. 
   \begin{itemize}
-  \item The first algorithm they discuss is a convex and parallelizable optimization problem. However, the theoretical guarantee is close to perfect reconstruction of `strong' edges after ${\cal O}(d^2 \log n)$ with high probability. There are several problems to this result however.
+  \item The first algorithm they discuss is a convex and parallelizable optimization problem. The algorithm is guaranteed to achieve perfect reconstruction of `strong' edges after ${\cal O}(\Delta^2 \log n)$ with high probability, where $\Delta$ is the maximum degree in the graph. There are several things to note about this result:
   \begin{itemize}
-    \item Researchers believe the true threshold of cascades necessary is closer to ${\cal O}(d \log n)$
-    \item The constant in the big ${\cal O}$ is highly polynomial in the different constants, of the order of billions even for very generous initializations of these parameters
-    \item The authors make a restrictive assumption on the probabilities of each edge, which they call `correlation decay': $\forall i, \sum_{j \in {\cal N}(i)} p_{j,i} < 1 -\alpha$, where $0 < \alpha < 1$
+    \item Researchers believe the true threshold of cascades necessary to achieve perfect reconstruction is closer to ${\cal O}(\Delta \log n)$.
+    \item The big ${\cal O}$ is highly polynomial in the different constants of the model. The constant is of the order of billions even for very generous initializations of these parameters
+    \item The authors make a restrictive assumption, called `correlation decay', on the probabilities of each edge: $\forall i, \sum_{j \in {\cal N}(i)} p_{j,i} < 1 -\alpha$, where $0 < \alpha < 1$. 
   \end{itemize}
-  \item The second algorithm, to which we will compare ourselves in Section~\ref{sec:exp}, is \textsc{Greedy}. It achieves perfect reconstruction after ${\cal O}(d \log n)$ observed cascades with high probability. However, this guarantee has been proven only in the case of tree-graphs. The authors mention that it does fairly well in pratice on other types of graphs.
+  \item The second algorithm suggested in \cite{netrapalli}, to which we will compare ourselves in Section~\ref{sec:exp}, is \textsc{Greedy}. It achieves perfect reconstruction after ${\cal O}(d \log n)$ observed cascades with high probability. However, this guarantee has been proven only in the case of tree-graphs. The authors mention that it does fairly well in pratice on other types of graphs.
   \end{itemize}
-\item Finally, a recent paper by Bruno Abrahao, Flavio Chierichetti, Robert Kleinberg, Alessandro Panconesi gives several algorithms and a different approach to showing their theoretical guarantees. Their strongest result is for bounded-degree graphs, where they show that they can obtain perfect reconstruction after observing ${\cal O}(\Delta^9 \log^2 \Delta \log n)$ algorithm. This is weaker than the first algorithm suggested by \cite{netrapalli}, but does not make the `correlation decay' assumption., where $\Delta$ is the max degree in graph ${\cal G}$.
+\item Finally, a recent paper by Bruno Abrahao, Flavio Chierichetti, Robert Kleinberg, Alessandro Panconesi gives several algorithms and a different approach to obtaining theoretical guarantees. Their strongest result is for bounded-degree graphs, where they show that they can obtain perfect reconstruction after observing ${\cal O}(\Delta^9 \log^2 \Delta \log n)$ algorithm. This is weaker than the first algorithm suggested by \cite{netrapalli}, but does not make the `correlation decay' assumption. 
 \end{itemize}
 
 What we aim for with the following framework is to achieve theoretical guarantees promising close-to-perfect reconstruction with observing ${\cal O}(\Delta \log n)$ cascades with high probability without relying on unreasonable assumptions like `correlation decay'. We also want our method to be easily implementable in practice and compare favorably to the above algorithms.
@@ -192,14 +192,14 @@ Note that this is not exactly a sparse recovery model due to the non-linear expo
 
 To recover the neighbors of $v_5$, we get the following matrix $M$ for the example in Figure 2:
 \begin{align*}
-&v_1 \hspace{0.2 cm}  v_2 \hspace{0.2 cm} v_3 \hspace{0.2 cm} v_4 \\
-\vspace{1 cm}
+\centering
+&\hspace{0.35cm} v_1 \hspace{0.2 cm}  v_2 \hspace{0.2 cm} v_3 \hspace{0.2 cm} v_4 \\
 M  = &  \left( \begin{array}{cccc}
 1 & 0 & 0 & 0 \\
 0 & 1 & 1 & 0 \\
-\end{array} \right)   \begin{array}{l} \hspace{ 1cm} 
+\end{array} \right)   \begin{array}{l} 
 \text{time step 0} \\
- \hspace{ 1cm}  \text{time step 1} \\
+  \text{time step 1} \\
  \end{array}
 \end{align*}
 
@@ -209,9 +209,9 @@ and the vector $b_5$:
 b_5  = &  \left( \begin{array}{c}
 0 \\
 1 \\
-\end{array} \right)  \begin{array}{l} \hspace{ 1cm} 
+\end{array} \right)  \begin{array}{l}
 \text{time step 1} \\
- \hspace{ 1cm}  \text{time step 2} \\
+ \text{time step 2} \\
  \end{array}
 \end{align*}
 
@@ -224,7 +224,7 @@ The literature on sparse recovery has expanded rapidly since a series of papers
 
 \subsection{Exploration}
 \paragraph{Disclosure}
-After an unsatisfactory attempt at adapting \cite{candestao}, we cite the main results of \cite{candestao} and give arguments as to why we believe, with more work, these assumptions can be made reasonable in the case our model. Due to the limited time frame of this project, we were unable to find a complete and rigorous argumentation as to why these assumptions hold. The following paragraphs should be understood as motivation for this line of research rather than concrete guarantees.
+After an unsatisfactory attempt at adapting \cite{candestao}, we cite the main results of \cite{candes} and give arguments as to why we believe, with more work, these assumptions can be made reasonable in the case our model. Due to the limited time frame of this project, we were unable to find a complete and rigorous argumentation as to why these assumptions hold. The following paragraphs should be understood as motivation for this line of research rather than concrete guarantees.
 
 \paragraph{Framework}
 Suppose that each row $m$ of $M$ is taken from a distribution ${\cal F}$, such that $\mathbb{E}(m m^T) = I_n$. Suppose further that $\|m\|_{\infty} \leq \mu$ and that $\|M^T \epsilon\|_{\infty} < 2.5 \sqrt{\log n}$. For every node $i$, consider the following optimization program:
@@ -241,7 +241,7 @@ If the number of rows $l$ of our matrix $M$ verifies $l \geq C \mu s \log n$ (wh
 \label{eq:first_guarantee}
 \| \hat x - x^* \|_2 \leq C (1 + \log^{3/2}n)\left[\frac{\|x^* - \tilde x\|_1}{\sqrt{s}} + \sigma \sqrt{\frac{s\log n}{l}}\right]
 \end{equation}
-where $\sigma$ is a constant dependent on the variance of $\epsilon$, and $\tilde x$ is the best s-sparse approximation to the ground truth $x^*$. In other words if node $i$ is of degree at most $s$, then $\|x^* - \tilde x\|_1 = 0$ since $x^*$ is $s-sparse$.\footnote{The result in the paper supposes that $x_i^*$ is $s$-sparse, i.e. that node $i$ has at most $s$ neighbors.}
+where $\sigma$ is a constant dependent on the variance of $\epsilon$, and $\tilde x$ is the best s-sparse approximation to the ground truth $x^*$. In other words if node $i$ is of degree at most $s$, then $\|x^* - \tilde x\|_1 = 0$ since $x^*$ is $s-sparse$.\footnote{The result in the poster implicitly supposes that $x_i^*$ is $s$-sparse, i.e. that node $i$ has at most $s$ neighbors. The term $\|x^* - \tilde x\|_1=0$ and does not appear in the statement of the theorem.}
 \end{theorem}
 
 \paragraph{Discussion}