From 2755cb771c956590c627b19692a4d62dcdeb4e19 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Fri, 8 Feb 2013 10:37:43 -0800
Subject: Last version of the slides

---
 slides/slides.tex | 110 +++++++++++++++++++++++++++++++-----------------------
 1 file changed, 64 insertions(+), 46 deletions(-)

(limited to 'slides/slides.tex')

diff --git a/slides/slides.tex b/slides/slides.tex
index 1bccd02..2c4b3fa 100644
--- a/slides/slides.tex
+++ b/slides/slides.tex
@@ -30,36 +30,14 @@
 
 \begin{frame}{Motivation}
     \begin{center}
-        \includegraphics<1-4>[scale=0.5]{1.pdf}
-        \includegraphics<5>[scale=0.5]{2.pdf}
-        \includegraphics<6>[scale=0.5]{3.pdf}
-        \includegraphics<7>[scale=0.5]{4.pdf}
-    \end{center}
-
-    \begin{center}
-        \begin{overprint}
-        \onslide<1>\begin{center}$N$ users\end{center}
-            \onslide<2>
-            \begin{center}
-                $x_i\in\mathbb{R}^d$: public features (e.g. age, sex, height, etc.)
-            \end{center}
-            \onslide<3>
-            \begin{center}
-                $y_i\in\mathbb{R}$: private date (e.g. disease, etc.)
-            \end{center}
-            \onslide<4>
-            \begin{center}
-                Linear model: $y_i = \beta^Tx_i + \varepsilon_i$
-            \end{center}
-            \begin{displaymath}
-                \beta^* = \arg\min_\beta \sum_i |y_i-\beta^Tx_i|^2
-            \end{displaymath}
-        \end{overprint}
+        \includegraphics<1>[scale=0.5]{1.pdf}
+        \includegraphics<2>[scale=0.5]{2.pdf}
+        \includegraphics<3>[scale=0.5]{3.pdf}
+        \includegraphics<4>[scale=0.5]{4.pdf}
     \end{center}
 \end{frame}
-
-
 \begin{frame}{Challenges}
+    \pause
     \begin{itemize}
         \item Value of data?
             \vspace{1cm}
@@ -72,6 +50,7 @@
 \end{frame}
 
 \begin{frame}{Contributions}
+    \pause
     \begin{itemize}
         \item case of the linear regression
             \vspace{1cm}
@@ -95,7 +74,7 @@
 
 \begin{frame}{Reverse auction}
 \begin{itemize}
-    \item set of $N$ sellers $\mathcal{A} = \{1,\ldots,N\}$ and a buyer
+    \item set of $N$ sellers: $\mathcal{A} = \{1,\ldots,N\}$; a buyer
         \vspace{0.3cm}
         \pause
     \item $V$ value function of the buyer, $V:2^\mathcal{A}\rightarrow \mathbb{R}^+$
@@ -114,7 +93,7 @@
     \begin{itemize}
         \item Find $S\subset \mathcal{A}$ \alert{maximizing} $V(S)$
             \vspace{0.3cm}
-        \item Find \alert{payment} $p_i$ to seller $i$
+        \item Find \alert{payment} $p_i$ to seller $i\in S$
     \end{itemize}
 \end{block}
 \end{frame}
@@ -179,14 +158,42 @@
     \tableofcontents[currentsection]
 \end{frame}
 
-\begin{frame}{Linear regression}
-    Each user $i\in\mathcal{A}$ has:
+\begin{frame}{Linear Regression}
+    \begin{center}
+        \includegraphics<1-4>[scale=0.5]{5.pdf}
+        \includegraphics<5>[scale=0.5]{6.pdf}
+        \includegraphics<6>[scale=0.5]{7.pdf}
+        \includegraphics<7>[scale=0.5]{8.pdf}
+    \end{center}
+
+    \begin{center}
+        \begin{overprint}
+        \onslide<1>\begin{center}$N$ users\end{center}
+            \onslide<2>
+            \begin{center}
+                $x_i$: public features (e.g. age, gender, height, etc.)
+            \end{center}
+            \onslide<3>
+            \begin{center}
+                $y_i$: private data (e.g. disease, etc.)
+            \end{center}
+            \onslide<4>
+            \begin{center}
+                Gaussian Linear model: $y_i = \beta^Tx_i + \varepsilon_i$
+            \end{center}
+            \begin{displaymath}
+                \beta^* = \arg\min_\beta \sum_i |y_i-\beta^Tx_i|^2
+            \end{displaymath}
+        \end{overprint}
+    \end{center}
+\end{frame}
+
+\begin{frame}{Experimental design}
     \begin{itemize}
-        \item Public feature vector $x_i\in\mathbb{R}^d$
+        \item Public vector of features $x_i\in\mathbb{R}^d$
         \item Private data $y_i\in\mathbb{R}$
     \end{itemize}
 
-    \pause
     \vspace{0.5cm}
 
     Gaussian linear model:
@@ -204,14 +211,14 @@
 
     \begin{block}{Experimental Design}
     \begin{displaymath}
-        \textsf{\alert{maximize}}\quad V(S) = \log\det\left(I_d + \sum_{i\in S} x_i x_i^T\right),\quad S\subset\mathcal{A}
+        \textsf{\alert{maximize}}\quad V(S) = \log\det\left(I_d + \sum_{i\in S} x_i x_i^T\right)\quad \textsf{\alert{subject to}}\quad |S|\leq k
     \end{displaymath}
     \end{block}
 \end{frame}
 
-\begin{frame}{Experimental design}
+\begin{frame}{Budgeted Experimental design}
     \begin{displaymath}
-        \textsf{\alert{maximize}}\quad V(S) = \log\det\left(I_d + \sum_{i\in S} x_i x_i^T\right),\quad S\subset\mathcal{A}
+        \textsf{\alert{maximize}}\quad V(S) = \log\det\left(I_d + \sum_{i\in S} x_i x_i^T\right)\quad \textsf{\alert{subject to}}\quad \sum_{i\in S}c_i\leq B
     \end{displaymath}
 
     \vspace{1cm}
@@ -233,7 +240,7 @@
 \begin{frame}{Main result}
     \begin{theorem}
         There exists a budget feasible, individually rational and truthful mechanism for
-        experimental design which runs in polynomial time. Its
+        budgeted experimental design which runs in polynomial time. Its
         approximation ratio is:
         \begin{displaymath}
         \frac{10e-3 + \sqrt{64e^2-24e + 9}}{2(e-1)}
@@ -243,7 +250,7 @@
 \end{frame}
 
 \begin{frame}{Sketch of proof}
-    \begin{block}{Mechanism (Chen et. al, 2011)}
+    \begin{block}{Mechanism (Chen et. al, 2011) for submodular $V$}
         \begin{itemize}
         \item Find $i^* = \arg\max_i V(\{i\})$
         \item Compute $S_G$ greedily
@@ -268,13 +275,24 @@
     \vspace{0.5cm}
     \pause
 
-    \alert{Solution:} Replace $V(OPT_{-i^*})$ with $L^*$:
-    \pause
-    \begin{itemize}
-        \item computable in polynomial time
+    \begin{columns}[c]
+        \begin{column}{0.53\textwidth}
+            \alert{Solution:} Replace $V(OPT_{-i^*})$ with \alert<7>{$L^*$}:
             \pause
-        \item close to $V(OPT_{-i^*})$
-    \end{itemize}
+            \begin{itemize}
+                \item computable in polynomial time
+                    \pause
+                \item close to $V(OPT_{-i^*})$
+            \end{itemize}
+        \end{column}
+        \pause
+        \begin{column}{0.45\textwidth}
+            \begin{itemize}
+                \item Knapsack (Chen et al., 2011)
+                \item Coverage (Singer, 2012)
+            \end{itemize}
+        \end{column}
+    \end{columns}
 \end{frame}
 
 \begin{frame}{Sketch of proof (2)}
@@ -316,9 +334,9 @@
     \pause
     \vspace{0.5cm}
 
-    \begin{block}{Value function: entropy reduction}
+    \begin{block}{Value function: Information gain}
         \begin{displaymath}
-            V(S) = H(f) - H(f\mid Y_S),\quad S\subset\mathcal{A}
+            V(S) = H(f) - H(f\mid S),\quad S\subset\mathcal{A}
         \end{displaymath}
     \end{block}
 
-- 
cgit v1.2.3-70-g09d2

