Poster for NYCE 2013

5 files changed, 378 insertions, 0 deletions

diff --git a/poster_nyce_2013/beamerthemeconfposter.sty b/poster_nyce_2013/beamerthemeconfposter.sty
new file mode 100755
index 0000000..74d573a
--- /dev/null
+++ b/poster_nyce_2013/beamerthemeconfposter.sty
@@ -0,0 +1,184 @@
+\ProvidesPackage{beamerthemeconfposter}
+\RequirePackage{tikz}		% for drawing the nice rounded boxes
+\usetikzlibrary{arrows,backgrounds}
+\newcommand{\makeruleinbox}{{\usebeamercolor[bg]{block alerted title}\centering\hspace*{-0.7cm}\rule{\inboxrule}{0.5cm}}}
+\usepackage{ragged2e}
+
+% Spacing before and inside list environments to add white space before lists and between items inside lists
+\makeatletter
+\def\@listi{\leftmargin\leftmarginii
+\topsep 1ex % Spacing before lists
+\parsep 0\p@ \@plus\p@
+\itemsep 6pt} % Spacing between items
+\makeatother
+
+\usecaptiontemplate{\small\structure{\insertcaptionname~\insertcaptionnumber: }\insertcaption} % A fix for figure numbering
+
+\definecolor{lgreen} {RGB}{180,210,100}
+\definecolor{dblue}  {RGB}{41,40,64}
+\definecolor{ddblue} {RGB}{11,36,69}
+\definecolor{lred}   {RGB}{220,0,0}
+\definecolor{nred}   {RGB}{224,0,0}
+\definecolor{norange}{RGB}{230,120,20}
+\definecolor{nyellow}{RGB}{255,221,0}
+\definecolor{ngreen} {RGB}{98,158,31}
+\definecolor{dgreen} {RGB}{78,138,21}
+\definecolor{nblue}  {RGB}{28,130,185}
+\definecolor{jblue}  {RGB}{20,50,100}
+
+% set the basic colors
+\setbeamercolor{palette primary}   {fg=black,bg=white}
+\setbeamercolor{palette secondary} {fg=black,bg=white}
+\setbeamercolor{palette tertiary}  {bg=jblue,fg=white}
+\setbeamercolor{palette quaternary}{fg=black,bg=white}
+\setbeamercolor{structure}{fg=jblue}
+\setbeamercolor{titlelike}         {bg=jblue,fg=white}
+\setbeamercolor{frametitle}        {bg=jblue!10,fg=jblue}
+\setbeamercolor{cboxb}{fg=black,bg=dblue}
+\setbeamercolor{cboxr}{fg=black,bg=red}
+
+% set colors for itemize/enumerate
+\setbeamercolor{item}{fg=dblue}
+\setbeamercolor{item projected}{fg=white,bg=ngreen}
+
+% set colors for blocks
+\setbeamercolor{block title}{fg=dblue,bg=white}
+\setbeamercolor{headline}{fg=white,bg=dblue}
+\setbeamercolor{block body}{fg=black,bg=white}
+
+% set colors for alerted blocks (blocks with frame)
+\setbeamercolor{block alerted title}{fg=white,bg=jblue}
+\setbeamercolor{block alerted body}{fg=black,bg=jblue!10}
+
+% set the fonts
+\setbeamerfont{section in head/foot}{series=\bfseries}
+\setbeamerfont{block title}{series=\bfseries}
+\setbeamerfont{block alerted title}{series=\bfseries}
+\setbeamerfont{frametitle}{series=\bfseries}
+\setbeamerfont{frametitle}{size=\Large}
+\setbeamerfont{block body}{size=\normalsize}
+
+% set some beamer theme options
+\setbeamertemplate{title page}[default][colsep=-4bp,rounded=true]
+\setbeamertemplate{sections/subsections in toc}[square]
+\setbeamertemplate{blocks}[width=0.0]
+\beamertemplatenavigationsymbolsempty
+
+% set bibliography style
+\setbeamertemplate{bibliography item}[text]
+\setbeamercolor{bibliography item}{fg=black,bg=white}
+\setbeamercolor{bibliography entry author}{fg=black,bg=white}
+\setbeamercolor{bibliography item}{fg=black,bg=white}
+
+% define some length variables that are used by the template
+\newlength{\inboxwd}
+\newlength{\iinboxwd}
+\newlength{\inboxrule}
+\makeatletter
+\makeatother
+
+%==============================================================================
+% build the poster title
+%==============================================================================
+\setbeamertemplate{headline}{
+ \begin{beamercolorbox}{headline}
+ \begin{columns}[T]
+     \begin{column}[T]{0.947\linewidth}
+         \begin{center}
+       \usebeamercolor{title in headline}{\LARGE{\textbf{\inserttitle}}}
+
+   \vspace{0.2cm}
+
+       \usebeamercolor{author in headline}{\large{\insertauthor}}
+   \end{center}
+   \vspace{0.2cm}
+   \end{column}
+     \begin{column}[T]{0.053\linewidth}
+         \vspace{0.5cm}
+         \includegraphics{qr2.png}
+         \hspace{1cm}
+
+     \end{column}
+  \end{columns}
+ \end{beamercolorbox}
+}
+
+\setbeamertemplate{footline}{
+ \begin{beamercolorbox}[colsep=0.08cm]{cboxb}\end{beamercolorbox}
+  
+     \begin{columns}
+         \begin{column}{0.70\linewidth}
+       \begin{center}
+           \usebeamercolor{institute in headline}{\color{fg}\normalsize{\insertinstitute}}
+       \end{center}
+       \vspace{0.1cm}
+   \end{column}
+   \begin{column}{0.30\linewidth}
+       \small{Contact: \texttt{thibaut.horel@gmail.com}}
+    \end{column}
+  \end{columns}
+}
+
+% Block definition
+\setbeamertemplate{block begin}
+{
+  \par\vskip\medskipamount
+  \begin{beamercolorbox}[colsep*=0ex,dp={2ex},center]{block title}
+    \vskip-0.25cm
+    \usebeamerfont{block title}\large\insertblocktitle
+    \begin{flushleft}
+    \vskip-1cm
+    \begin{tikzpicture}[remember picture,overlay]
+      \shade [inner color=gray,outer color=white]
+      (0,0) rectangle (\textwidth,0.3cm);
+    \end{tikzpicture}
+    \end{flushleft}
+  \end{beamercolorbox}
+  {\parskip0pt\par}
+  \ifbeamercolorempty[bg]{block title}
+  {}
+  {\ifbeamercolorempty[bg]{block body}{}{\nointerlineskip\vskip-0.5pt}}
+  \usebeamerfont{block body}
+  \vskip-0.5cm
+  \begin{beamercolorbox}[colsep*=0ex,vmode]{block body}
+  \justifying
+}
+
+\setbeamertemplate{block end}
+{
+  \end{beamercolorbox}
+  \vskip\smallskipamount
+}
+
+% Alert block definition (with frame)
+\setbeamertemplate{block alerted begin}
+{
+  \par\vskip\medskipamount
+  \begin{beamercolorbox}[sep=0ex,rounded=true,center,dp={2ex}]{block alerted title}
+    \vskip0.01cm
+    \usebeamerfont{block title}\large\insertblocktitle
+  \end{beamercolorbox}
+  {\parskip0pt\par}
+  \usebeamerfont{block body}
+  \vskip-0.8cm
+  \begin{beamercolorbox}[sep=0.5cm, rounded=true,center]{block alerted title}
+  \setlength{\inboxwd}{\linewidth}
+  \addtolength{\inboxwd}{-1cm}
+  \begin{beamercolorbox}[rounded=true,wd={\inboxwd},center]{block alerted body}
+  \setlength{\iinboxwd}{\inboxwd}
+  \setlength{\inboxrule}{\inboxwd}
+  \addtolength{\iinboxwd}{-0.5cm}
+  \addtolength{\inboxrule}{0.5cm}
+  \begin{center}
+  \begin{minipage}{\iinboxwd}
+  \justifying
+}
+
+\setbeamertemplate{block alerted end}
+{
+  \end{minipage}
+  \end{center}
+  \end{beamercolorbox}
+  \end{beamercolorbox}
+  \vskip\smallskipamount
+}
diff --git a/poster_nyce_2013/main.tex b/poster_nyce_2013/main.tex
new file mode 100644
index 0000000..688290e
--- /dev/null
+++ b/poster_nyce_2013/main.tex
@@ -0,0 +1,194 @@
+\documentclass[portrait]{beamer}
+\usepackage[utf8]{inputenc}
+\usepackage[orientation=portrait,size=custom,width=55,height=71,scale=1]{beamerposter}
+\usetheme{confposter}
+\usepackage{times}
+\newlength{\sepwid}
+\newlength{\onecolwid}
+\newlength{\twocolwid}
+\newlength{\threecolwid}
+\setlength{\paperwidth}{22in}
+\setlength{\paperheight}{28in}
+\setlength{\sepwid}{0.01\paperwidth}
+\setlength{\onecolwid}{0.47\paperwidth}
+\setlength{\twocolwid}{0.96\paperwidth}
+\setlength{\fboxrule}{2pt}
+\setlength{\fboxsep}{10pt}
+
+\usepackage{graphicx}
+\usepackage{amsmath}
+
+\title{Budget Feasible Mechanisms for Experimental Design}
+\author{Thibaut Horel$^*$ \and Stratis Ioannidis$^\dag$ \and Muthu Muthukrishnan$^\ddag$}
+\institute{$^*$École Normale Supérieure, $^\dag$Technicolor, $^\ddag$Rutgers University}
+
+\begin{document}
+
+
+\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}{\sepwid}\end{column}
+
+\begin{column}{\onecolwid}
+
+\begin{block}{Setting}
+    \begin{center}
+    \includegraphics[scale=1]{st.pdf}
+\end{center}
+$N$ users, each of them has:
+\begin{itemize}
+    \item \textbf{public} features $x_i$ (\emph{e.g.} age, gender, height, etc.)
+    \item \textbf{private} data $y_i$ (\emph{e.g.} survey answer, medical test outcome)
+    \item cost $c_i$ to reveal their data
+\end{itemize}
+
+Experimenter \textsf{E}:
+\begin{itemize}
+    \item pays users to reveal their private data
+    \item has a budget constraint $B$
+\end{itemize}
+\end{block}
+
+\begin{block}{Ridge Regression}
+    \begin{enumerate}
+        \item Experimenter $E$ assumes a linear model:
+\begin{displaymath}
+    y_i = \beta^{T}x_i + \varepsilon_i,\quad\varepsilon_i\sim\mathcal{N}(0,\sigma^2)
+\end{displaymath}
+and a normal prior: $\beta\sim\mathcal{N}(0,\sigma^2I_d)$.
+\item Experimenter $E$ selects a set $S$ of users within his budget constraint,
+and learns $\beta$ through ridge regression:
+\begin{displaymath}
+    \hat{\beta} = \sigma^{-2}\arg\,\min_\beta\Big[ \sum_{i\in S}(y_i-\beta^Tx_i)^2 + \|\beta\|^2\Big]
+\end{displaymath}
+\end{enumerate}
+\end{block}
+
+\begin{block}{Value of Data}
+    \textbf{Goal} minimize the variance-covariance matrix of the
+    estimator:
+    \begin{displaymath}
+        \mathrm{Var}\, \hat{\beta} = \Big(I_d+\sum_{i\in S}x_ix_i^T\Big)^{-1} 
+    \end{displaymath}
+    Minimizing the volume ($\det$) of the variance is equivalent to maximizing the information gain (entropy reduction) on $\beta$:
+    \begin{displaymath}
+        V(S) = \log\det\Big(I_d+\sum_{i\in S} x_ix_i^T\Big)
+    \end{displaymath}
+\end{block}
+
+\begin{block}{Experimental Design}
+The experimenter selects set of user $S$ solution to:
+\begin{displaymath}
+    \begin{split}
+    &\text{Maximize } V(S) = \log\det\Big(I_d+\sum_{i\in S} x_ix_i^T\Big)\\
+        &\text{Subject to } \sum_{i\in S} c_i\leq B
+\end{split}
+\end{displaymath}
+\begin{itemize}
+    \item specific case of budgeted submodular maximization
+    \item there exists a poly-time $\frac{e}{e-1}$-approximate algorithm
+\end{itemize}
+
+
+\end{block}
+\end{column}
+
+\begin{column}{\sepwid}\end{column}
+\vrule{}
+\begin{column}{\sepwid}\end{column}
+
+    \begin{column}{\onecolwid}
+        \begin{block}{Experimental Design with Strategic Users}
+            \begin{itemize}
+                \item users might lie about the reported costs $c_i$
+                \item payments and selection rule must be adapted accordingly
+            \end{itemize}
+            Specific case of \textbf{budget feasible mechanism design}; the payments and selection rule must satisfy:
+            \begin{itemize}
+                \item individual rationality and truthfulness
+                \item budget feasibility
+            \end{itemize}
+            Can we still obtain a constant approximation ratio in polynomial time?
+        \end{block}
+
+        \begin{block}{Mechanism blueprint for Experimental Design}
+            \fbox{\parbox{0.95\textwidth}{
+            \begin{itemize}
+                \item Compute $i^* = \arg\max_i V(\{i\})$
+                \item Compute $L^*$ (see below)
+                \item Compute $S_G$ greedily:
+                    \begin{itemize}
+                        \item repeatedly add element with \emph{highest
+                            marginal-value-per-cost}:
+                            \begin{align*}
+                                i = \argmax_{j\in[N]\setminus
+                                S}\frac{V(S\cup\{i\}) - V(S)}{c_i}\label{greedy}
+                            \end{align*}
+                        \item stop when the budget is exhausted
+                    \end{itemize}
+                \item Return:
+                    \begin{itemize}
+                        \item $i^*$ if $V(\{i^*\})>L^*$
+                        \item $S_G$ otherwise
+                    \end{itemize}
+            \end{itemize}
+    }}
+
+    \vspace{0.3cm}
+
+            $L^*$ must be:
+            \begin{itemize}
+                \item close to $OPT:=\max_{S\subseteq [N]\setminus \{i^*\}} \{V(S);
+                    \sum_{i\in S}c_i\leq B\}$
+                \item monotone in $c$; computable in poly-time
+            \end{itemize}
+        \end{block}
+        
+        \begin{block}{Convex Relaxation for Experimental Design}
+            We introduce the following concave function:
+            \begin{displaymath}
+                L(\lambda) = \sum_{1\leq i\leq N}\log\det\Big(I_d
+                + \sum_{1\leq i\leq N} \lambda_i x_ix_i^T\Big).
+            \end{displaymath}
+            Then using $L^* = \max_\lambda \big\{L(\lambda); \sum_{1\leq i\leq N} c_i\leq B,\; \lambda_{i^*} = 0\big\}$:
+
+            \vspace{0.3cm}
+
+            \fbox{\parbox{0.95\textwidth}{
+            \textbf{Theorem:} \emph{The above mechanism is truthful, individually rational, budget-feasible, runs in polynomial time and its approximation \mbox{ratio} is $\simeq 12.984$.}}}
+
+            \vspace{0.5cm}
+
+            Technical challenges:
+            \begin{itemize}
+                \item $L^*$ is close to $OPT$ (shown via pipage rounding)
+                \item $L^*$ can be approximated monotonously in $c$
+            \end{itemize}
+        \end{block}
+        \begin{block}{Generalization}
+            \begin{itemize}
+                \item Generative model of the form: 
+    \begin{displaymath}
+        y_i = f(x_i) + \varepsilon_i
+    \end{displaymath}
+\item Prior knowledge: $f$ is a random variable, the entropy $H(f)$ captures the
+    experimenter's uncertainty.
+\item Value function: information gain (entropy reduction) induced by the observed data of the users in $S$:
+    \begin{displaymath}
+        V(S) = H(f) - H(f\,|\,S)
+    \end{displaymath}
+    \end{itemize}
+    $V$ is again submodular and the previous framework applies.
+        \end{block}
+    \end{column}
+\begin{column}{\sepwid}\end{column}
+\begin{column}{\sepwid}\end{column}
+\end{columns}
+
+\end{frame}
+
+\end{document}
diff --git a/poster_nyce_2013/qr.png b/poster_nyce_2013/qr.png
new file mode 100644
index 0000000..81d963c
--- /dev/null
+++ b/poster_nyce_2013/qr.png
diff --git a/poster_nyce_2013/qr2.png b/poster_nyce_2013/qr2.png
new file mode 100644
index 0000000..7521b2d
--- /dev/null
+++ b/poster_nyce_2013/qr2.png
diff --git a/poster_nyce_2013/st.pdf b/poster_nyce_2013/st.pdf
new file mode 100644
index 0000000..f9507b6
--- /dev/null
+++ b/poster_nyce_2013/st.pdf