path: root/poster/Finale_poster/poster.tex

\documentclass[final, 10]{beamer}
\usepackage[utf8]{inputenc}
\usepackage[scale=1.6]{beamerposter} % Use the beamerposter package for laying
\usetheme{confposter} % Use the confposter theme supplied with this template

\usepackage{framed, amsmath, amsthm, amssymb}
\usepackage{color, bbm}
\setbeamercolor{block title}{fg=dblue,bg=white} % Colors of the block titles
\setbeamercolor{block body}{fg=black,bg=white} % Colors of the body of blocks
\setbeamercolor{block alerted title}{fg=white,bg=dblue!70} % Colors of the
\setbeamercolor{block alerted body}{fg=black,bg=dblue!10} % Colors of the body

\newlength{\sepwid}
\newlength{\onecolwid}
\newlength{\twocolwid}
\newlength{\threecolwid}
\setlength{\paperwidth}{48in} % A0 width: 46.8in
\setlength{\paperheight}{40in} % A0 height: 33.1in
\setlength{\sepwid}{0.024\paperwidth} % Separation width (white space) between
\setlength{\onecolwid}{0.22\paperwidth} % Width of one column
\setlength{\twocolwid}{0.464\paperwidth} % Width of two columns
\setlength{\threecolwid}{0.708\paperwidth} % Width of three columns
\setlength{\topmargin}{-1in} % Reduce the top margin size
%-----------------------------------------------------------

\usepackage{graphicx}
\usepackage{booktabs}

%----------------------------------------------------------------------------------------
%	TITLE SECTION
%----------------------------------------------------------------------------------------

\title{Inferring Graphs from Cascades} % Poster title

\author{Thibaut Horel, Jean Pouget-Abadie} % Author(s)

\institute{Harvard University} % Institution(s)
%----------------------------------------------------------------------------------------
\begin{document}
\addtobeamertemplate{block end}{}{\vspace*{2ex}} % White space under blocks
\addtobeamertemplate{block alerted end}{}{\vspace*{2ex}} % White space under

\setlength{\belowcaptionskip}{2ex} % White space under figures
\setlength\belowdisplayshortskip{2ex} % White space under equations

\begin{frame}[t]
\begin{columns}[t]
\begin{column}{\sepwid}\end{column}
\begin{column}{\onecolwid} % The first column

%----------------------------------------------------------------------------------------
%	INTODUCTION
%----------------------------------------------------------------------------------------


\vspace{- 12.2 cm}
\begin{center}
{\includegraphics[scale=2.5]{../images/SEASLogo_RGB.png}}
\end{center}

\vspace{5 cm}

\begin{block}{Problem}
  \emph{How to recover an unknown network from the observation of contagion
  cascades?}
  \vspace{.5cm}
  \begin{itemize}
  \item {\bf Observe} $X^t_c$ (infections at time $t$ in cascade $c$)
  \item {\bf Objective}: find $\{\theta_{ij}\}$ (graph weight matrix)
\end{itemize}
\end{block}
\vspace{1cm}

\begin{block}{\bf Contagion Model~\cite{}}
\begin{itemize}
  \item Discrete time
  \item Infections drawn indep.~for each node conditioned on previous step
  \item Generalized Linear Model parametrization:
    \begin{framed}
    $$\mathbb{P}(X^{t+1}_j = 1 | X^t) = f(\Theta_j \cdot X^t)$$
    \end{framed}
\end{itemize}
\end{block}

\begin{block}{MLE}
  \begin{itemize}
    \item Log-likelihood is concave for common contagion models (IC model): SGD
      on $\{\theta_{ij}\}$
  \end{itemize}
  \vspace{1cm}
  \begin{equation*}
    \begin{split}
      \hat{\theta}\in \arg\max_\theta \sum_{t}~& y^t\log f(\theta\cdot x^t)
      \\ & + (1-y^t) \log \big(1 - f(\theta\cdot x^t)\big)
  \end{split}
\end{equation*}
\end{block}

\begin{block}{Bayesian Framework}
\begin{figure}
  \centering
  \includegraphics[scale=3]{graphical.pdf}
\end{figure}
\end{block}


\end{column} % End of the first column

%-----------------------------------------------------------------------------
\begin{column}{\sepwid}\end{column} % Empty spacer column
%-----------------------------------------------------------------------------
\begin{column}{\onecolwid} % The first column


\end{column}
%-----------------------------------------------------------------------------
\begin{column}{\sepwid}\end{column}
%-----------------------------------------------------------------------------

\begin{column}{\onecolwid}

\begin{block}{Sparse Recovery}

\begin{itemize}
  \item Solving for $A x = b$ when $A$ is non-degenerate is possible if
      \begin{itemize}
        \item $A$ is {\bf almost invertible}
        \item $x$ is {\bf sparse}
      \end{itemize}
  \item If $x$ is solution to $\min L(x)$ where
    $L$ is convex, then~\cite{Negahban:2009}~solve for:
    \begin{equation*}
      \min_x L(x) + \lambda \| x\|
    \end{equation*}
\end{itemize}
\end{block}

\begin{theorem}
    {\bf Assumptions}:
    \begin{itemize}
        \item $f$ and $1-f$ are log-concave with log-gradient bounded by
          $\frac{1}{\alpha}$
      \item $\nabla^2 {\cal L}$ verifies the $(S,\gamma)$-{\bf
    RE} condition
    \vspace{1cm}
\end{itemize} {\bf Algorithm}:
    \begin{itemize}
      \item Solve MLE program with $\lambda = 2\sqrt{\frac{\log m}{\alpha n}}$
        \begin{framed}
        \begin{equation*}
          \hat \theta_i \in \arg \max_{\theta} {\cal L}_i(\theta_i | x^1,
          \dots x^n) - \lambda \|\theta_i\|_1
        \end{equation*}
      \end{framed}
    \end{itemize}
    \vspace{1cm}
    {\bf Guarantee}
      With high probability:
    \begin{framed}
    \begin{equation*}
    \|\hat \theta - \theta^*\|_2 \leq \frac{6}{\gamma} \sqrt{\frac{s \log
      m}{\alpha n}}
    \end{equation*}
  \end{framed}
    where $s$ is degree of node, $m$ is number of nodes, $n$ is the number of
    observations
\end{theorem}

\begin{block}{Restricted Eigenvalue Condition}
  {\bf Definition}
  \begin{itemize}
    \item $C(S) \equiv \{ X :\|X_{\bar S}\|_1 \leq 3 \|X\|_1\}$
    \item Matrix $A$ verifies the $(\gamma, S)$-{(\bf RE)} condition if:
      $$\forall X \in C({\cal S}), X^T A X \geq \gamma \|X\|_2^2$$
  \end{itemize}

   \vspace{1cm}
  {\bf Hessian $\mapsto$ Gram Matrix}
  \begin{itemize}
    \item If $f$ and $1-f$ are $c$-strictly log-convex, we can replace the
      condition on the $\nabla^2 {\cal L}$ by the same condition on the Gram
      matrix $X^T X$.
  \end{itemize}
    \vspace{1cm}
  {\bf Hessian $\mapsto$ Expected Hessian}
  \begin{itemize}
    \item If $\mathbb{E}[A]$ verifies the $(S, \gamma)$-{(\bf RE)} condition,
      then $A$ verifies the $(S, \gamma/2)$-{(\bf RE)}
     condition~\cite{vandegeer:2009}
  \end{itemize}

\end{block}

\end{column} % End of the second column

%-----------------------------------------------------------------------------
\begin{column}{\sepwid}\end{column} % Empty spacer column
%-----------------------------------------------------------------------------
\begin{column}{\onecolwid} % The third column
  \begin{block}{Experimental validation}
    \begin{figure}
      \centering
      \includegraphics[scale=1.2]{../images/watts_strogatz.pdf}
    \caption{Watts-Strogatz, $300$ nodes, $4500$ edges, uniform edge weights,
    constant $p_{init}$}
    \end{figure}
  \end{block}


\begin{block}{Conclusion}
  \begin{itemize}
    \item Introduce Generalized Linear Casacade model
    \item Better finite sample guarantees~\cite{Netrapalli:2012, Abrahao:13,
        Daneshmand:2014}
    \item Interpretable conditions on Hessian
    \item Lower bound+approximately sparse case developed in full
      paper~\cite{Pouget:2015}
  \end{itemize}
\end{block}

%-----------------------------------------------------------------------------
%	REFERENCES
%-----------------------------------------------------------------------------

\begin{block}{References}
  {\scriptsize
  \bibliography{../../paper/sparse}
\bibliographystyle{plain}}
\end{block}

%-----------------------------------------------------------------------------

\end{column} % End of the third column

\end{columns} % End of all the columns in the poster

\end{frame} % End of the enclosing frame



\end{document}