diff options
Diffstat (limited to 'slides/slides.tex')
| -rw-r--r-- | slides/slides.tex | 110 |
1 files changed, 64 insertions, 46 deletions
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} |