diff options
Diffstat (limited to 'paper/sections/intro.tex')
| -rw-r--r-- | paper/sections/intro.tex | 5 |
1 files changed, 5 insertions, 0 deletions
diff --git a/paper/sections/intro.tex b/paper/sections/intro.tex index c89c641..cc29ed7 100644 --- a/paper/sections/intro.tex +++ b/paper/sections/intro.tex @@ -73,21 +73,26 @@ However, the best known upper bound to this day is $\O(s^2\log m)$~\cite{Netrapalli:2012, Daneshmand:2014} The contributions of this paper are the following: +\vspace{-1em} \begin{itemize} \item we formulate the Graph Inference problem in the context of discrete-time influence cascades as a sparse recovery problem for a specific type of Generalized Linear Model. This formulation notably encompasses the well-studied Independent Cascade Model and Voter Model. + \vspace{-0.5em} \item we give an algorithm which recovers the graph's edges using $\O(s\log m)$ cascades. Furthermore, we show that our algorithm is also able to efficiently recover the edge weights (the parameters of the influence model) up to an additive error term, + \vspace{-0.5em} \item we show that our algorithm is robust in cases where the signal to recover is approximately $s$-sparse by proving guarantees in the \emph{stable recovery} setting. + \vspace{-0.5em} \item we provide an almost tight lower bound of $\Omega(s\log \frac{m}{s})$ observations required for sparse recovery. \end{itemize} +\vspace{-0.5em} The organization of the paper is as follows: we conclude the introduction by a survey of the related work. In Section~\ref{sec:model} we present our model of |