63 files changed, 890 insertions, 0 deletions

diff --git a/slides/11-25-2014/1.pdf b/slides/11-25-2014/1.pdf
new file mode 100755
index 0000000..cfdab56
--- /dev/null
+++ b/slides/11-25-2014/1.pdf
diff --git a/slides/11-25-2014/2.pdf b/slides/11-25-2014/2.pdf
new file mode 100755
index 0000000..db2ced6
--- /dev/null
+++ b/slides/11-25-2014/2.pdf
diff --git a/slides/11-25-2014/3.pdf b/slides/11-25-2014/3.pdf
new file mode 100755
index 0000000..2ef00a1
--- /dev/null
+++ b/slides/11-25-2014/3.pdf
diff --git a/slides/11-25-2014/4.pdf b/slides/11-25-2014/4.pdf
new file mode 100755
index 0000000..388ed9b
--- /dev/null
+++ b/slides/11-25-2014/4.pdf
diff --git a/slides/11-25-2014/5.pdf b/slides/11-25-2014/5.pdf
new file mode 100755
index 0000000..567fb49
--- /dev/null
+++ b/slides/11-25-2014/5.pdf
diff --git a/slides/11-25-2014/6.pdf b/slides/11-25-2014/6.pdf
new file mode 100755
index 0000000..5080b60
--- /dev/null
+++ b/slides/11-25-2014/6.pdf
diff --git a/slides/11-25-2014/7.pdf b/slides/11-25-2014/7.pdf
new file mode 100755
index 0000000..2861a5b
--- /dev/null
+++ b/slides/11-25-2014/7.pdf
diff --git a/slides/11-25-2014/8.pdf b/slides/11-25-2014/8.pdf
new file mode 100755
index 0000000..b502d99
--- /dev/null
+++ b/slides/11-25-2014/8.pdf
diff --git a/slides/11-25-2014/slides.tex b/slides/11-25-2014/slides.tex
new file mode 100755
index 0000000..5273ae9
--- /dev/null
+++ b/slides/11-25-2014/slides.tex
@@ -0,0 +1,890 @@
+\documentclass[10pt]{beamer}
+\usepackage[utf8x]{inputenc}
+\usepackage{amsmath,bbm,verbatim}
+\usepackage{algpseudocode,algorithm,bbding}
+\usepackage{graphicx}
+\DeclareMathOperator*{\argmax}{arg\,max}
+\DeclareMathOperator*{\argmin}{arg\,min}
+\usetheme{Boadilla}
+\newcommand{\E}{{\tt E}}
+
+\title[Harvard EconCS Seminar]{Budget Feasible Mechanism\\for Experimental
+Design}
+\author[Thibaut Horel]{Thibaut Horel, Stratis Ioannidis, and S. Muthukrishnan}
+
+%\setbeamercovered{transparent}
+\setbeamertemplate{navigation symbols}{}
+
+\newcommand{\ie}{\emph{i.e.}}
+\newcommand{\eg}{\emph{e.g.}}
+\newcommand{\etc}{\emph{etc.}}
+\newcommand{\etal}{\emph{et al.}}
+\newcommand{\reals}{\ensuremath{\mathbb{R}}}
+
+\begin{document}
+
+\maketitle
+
+\section{Motivation}
+
+\begin{frame}{Motivation}
+   \begin{center}
+        \includegraphics<1>[scale=0.4]{stg-8.pdf}
+        \includegraphics<2>[scale=0.4]{stg-7.pdf}
+        \includegraphics<3>[scale=0.4]{stg-6.pdf}
+        \includegraphics<4>[scale=0.4]{stg-5.pdf}
+        \includegraphics<5>[scale=0.4]{stg-4.pdf}
+        \includegraphics<6>[scale=0.4]{stg-3.pdf}
+        \includegraphics<7>[scale=0.4]{stg-2.pdf}
+        \includegraphics<8>[scale=0.4]{stg-1.pdf}
+   \end{center}
+
+\end{frame} 
+
+\begin{frame}{Application and Challenges}
+    \begin{itemize}
+	\item<1-> Applications
+            \begin{itemize}
+		\item Medicine/Sociology
+		\item Online surveys
+		\item Data markets
+	    \end{itemize}
+\vspace*{1cm}
+        \item<2-> Challenges
+	     \begin{itemize}
+	     	\item Which users are \alert{the most valuable}?
+            \item What if users are \alert{strategic}?
+        \end{itemize}
+    \end{itemize}
+\end{frame}
+
+\begin{frame}{Answers}
+    \begin{itemize}
+        \item Which users are \alert{the most valuable}?
+            \pause
+            \begin{itemize}
+                \item Experimental Design
+            \end{itemize}
+            \pause
+        \item Experimental design with \alert{strategic agents}?\pause
+            \begin{itemize}
+                \item Budget Feasible Mechanisms [Singer, 2010]
+            \end{itemize}
+    \end{itemize}
+	\pause
+	\vspace*{1cm}
+
+    For Linear Regression:
+	    \begin{itemize}
+            \item We present a deterministic, poly-time, truthful, budget
+                feasible, 12.9-aproximate mechanism. 
+            \item Lower bound of 2.
+	    \end{itemize}
+\end{frame}
+
+\section{Experimental design}
+
+\begin{frame}{Outline}
+\tableofcontents
+\end{frame}
+
+\begin{frame}{Outline}
+    \tableofcontents[currentsection]
+\end{frame}
+
+\begin{frame}{Problem}
+   \begin{center}
+        \includegraphics<1>[scale=0.4]{st2.pdf}
+        \includegraphics<2>[scale=0.4]{st3.pdf}
+        \includegraphics<3>[scale=0.4]{st4.pdf}
+        \includegraphics<4>[scale=0.4]{st5.pdf}
+        \includegraphics<5>[scale=0.4]{st6.pdf}
+        \includegraphics<6>[scale=0.4]{st6a.pdf}
+        \includegraphics<7>[scale=0.4]{st6b.pdf}
+        \includegraphics<8>[scale=0.4]{st6c.pdf}
+        \includegraphics<9>[scale=0.4]{st6d.pdf}
+        \includegraphics<10->[scale=0.4]{st6e.pdf}
+    \end{center}
+	\vspace*{-2em}
+    \begin{center}
+        \begin{overprint}
+        \onslide<1>\begin{center}$N$ ``experiment subjects'', $[N]\equiv
+        \{1,\ldots,N\}$ \end{center}
+            \onslide<2>
+            \begin{center}
+                $x_i\in \reals^d$: public features (\eg, age, gender, height, \etc)
+            \end{center}
+            \onslide<3>
+            \begin{center}
+                $y_i\in \reals$: private data (\eg, survey answer, medical test outcome, movie rating\ldots)
+            \end{center}
+            \onslide<4>
+                \textbf{Gaussian Linear Model.}  There exists $\beta\in \reals^d$ s.t.\vspace*{-1em}
+    \begin{displaymath}
+        y_i = \beta^T x_i + \varepsilon_i,\quad
+        \varepsilon_i\sim\mathcal{N}(0,\sigma^2), \quad i\in [N]
+    \end{displaymath}
+	    \onslide<5>
+	    \begin{center}
+		Experimenter {\tt E} wishes to learn $\beta$. 
+	    \end{center}
+       \onslide<6>
+       \begin{center}
+	Each subject $i\in [N]$ has a cost $c_i\in \reals_+$
+	\end{center}
+            \onslide<7>
+             \begin{center}
+                \E\ has a budget $B$.
+            \end{center}
+	    \onslide<8-9>
+	    \begin{center}
+		\E\ pays subjects\visible<9>{; $y_i$ is revealed upon payment.}
+	    \end{center} 
+	    \onslide<10>
+	    \begin{center}
+            {\tt E}  estimates ${\beta}$  through \emph{ridge regression}.
+	    \end{center}
+	    \onslide<11>
+	    \begin{center}
+            Goal: Determine who to pay how much so that $\hat{\beta}$ is as
+            accurate as possible.
+        \end{center}
+        \end{overprint}
+    \end{center}
+\end{frame}
+
+\begin{frame}{Which Users Are Informative?}
+
+Let $S\subseteq [N]$ be the set of selected users.
+
+\pause
+
+\E\ has a \emph{prior} on $\beta$:
+$$\beta \sim \mathcal{N}(0,\sigma^2 R^{-1}). $$
+
+\pause
+
+MAP estimation after observing private values:
+\begin{align*}
+    \hat{\beta} = \argmax_{\beta\in\reals^d} \mathbf{P}(\beta\mid y_i, i\in S)
+    \pause
+=\argmin_{\beta\in\reals^d} \big(\sum_{i\in S} (y_i - {\beta}^Tx_i)^2
+    + \beta^TR\beta\big)
+\end{align*}
+
+\pause
+
+Variance:
+\begin{displaymath}
+    \mathrm{Var}\, \hat{\beta} = \Big(R+\sum_{i\in S}x_ix_i^T\Big)^{-1} 
+\end{displaymath}
+
+\pause
+
+Minimizing variance: which scalarization?\pause{} \alert{D}eterminant (\alert{D}-optimal design)
+\begin{displaymath}
+    \det\Big(R+\sum_{i\in S}x_i x_i^T\Big)^{-1}
+\end{displaymath}
+\end{frame}
+
+\begin{frame}{Which Users Are Informative? (contd.)}
+Let $S\subset [N]$ be the set of selected users.
+
+\E\ has a \emph{prior} on $\beta$:
+$$\beta \sim \mathcal{N}(0,\sigma^2 R^{-1}). $$
+
+\pause
+Information Gain: reduction of uncertainty on $\beta$
+\begin{align*}
+    I(\beta;S)&=H(\beta)-H(\beta\mid y_i,i\in S)\\
+    \pause
+    & = \frac{1}{2}\log\det \Big(R+\sum_{i\in S}x_ix_i^T\Big)-\frac{1}{2}\log\det R
+\end{align*}
+
+\pause
+\begin{alertblock}{}
+    \begin{center}
+Maximizing information = Minimizing variance
+\end{center}
+\end{alertblock}
+\end{frame}
+
+\begin{frame}{Value function}
+\begin{align*}
+V(S)=\log\det\Big(R+\sum_{i\in S}x_ix_i^T\Big)
+\end{align*}
+\pause
+
+Marginal contribution of a user:
+\begin{align*}
+    &V(S\cup\{i\})-V(S) = \log(1+x_i^TA_S^{-1}x_i),\\
+    &\text{where } A_S = R + \sum_{i\in S}x_ix_i^T
+\end{align*}
+\pause
+\begin{itemize}
+\item Increase is greatest when $x_i$ \alert{spans a new direction}
+    \pause
+\item Adding an experiment \alert{always helps}
+    \pause
+\item $V$ is \alert{submodular}:
+$$V(S\cup\{i\})-V(S) \geq  V(S'\cup\{i\})-V(S'),\quad \text{ for }S\subseteq S'. $$
+\end{itemize}
+\end{frame}
+
+
+\begin{frame}{Experimental Design}
+\begin{block}{\textsc{Experimental Design Problem (EDP)} }
+\vspace*{-0.4cm}		
+\begin{align*}
+			\text{Maximize}\qquad &V(S) = \log \det (\alert<2>{I}+\sum_{i\in S}x_ix_i^T) \\
+			\text{subj. to}\qquad &\textstyle\sum_{i\in S}c_i\leq B
+\end{align*}
+\end{block}
+\pause
+\begin{itemize}
+\item $R=I$: homotropic prior
+    \pause
+\item EDP is NP-hard 
+    \pause
+\item $V$ is submodular, monotone, non-negative, and $V(\emptyset)=0$
+    \pause
+\item $\frac{e}{e-1}$-approximable (Sviridenko 2004, Krause and Guestrin 2005)
+\end{itemize}
+\end{frame}
+
+\begin{frame}{Constant-approximation algorithm}
+    \begin{block}{Budgeted Submodular Maximization}
+        \begin{itemize}
+        \item Let $i^* = \arg\max_i V(\{i\})$
+        \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}
+                    \end{align*}
+                \item stop when the budget is exhausted
+            \end{itemize}
+        \item Return:
+		\begin{itemize}
+		\item $i^*$ if $V(\{i^*\})>V(S_G)$
+		\item $S_G$ otherwise
+		\end{itemize}
+	\end{itemize}
+    \end{block}
+\vspace*{2em}
+\pause
+
+This algorithm is:
+\begin{itemize}
+\item poly-time,
+    \pause
+\item $\frac{5e}{e-1}$-approximate.
+\end{itemize}
+\end{frame}
+
+\begin{frame}{Summary}
+\begin{block}{\textsc{Experimental Design Problem (EDP)} }
+\vspace*{-0.4cm}		
+\begin{align*}
+			\text{Maximize}\qquad &V(S) = \log \det (I+\sum_{i\in S}x_ix_i^T) \\
+			\text{subj. to}\qquad &\textstyle\sum_{i\in S}c_i\leq B
+\end{align*}
+\end{block}
+\vspace{1cm}
+\pause
+Simple $\frac{2e}{e-1}$-approximate algorithm.
+\end{frame}
+\section{Experimental design with strategic users}
+
+\begin{frame}{Outline}
+    \tableofcontents[currentsection]
+\end{frame}
+
+\begin{frame}{Strategic users}
+\begin{center}
+\includegraphics<1->[scale=0.3]{st10c.pdf}
+\end{center}
+\begin{itemize}
+\visible<2-3>{\item
+Subjects are \alert{strategic} and may lie about costs $c_i$.}
+\visible<3>{\item
+Subjects \alert{do not lie} about $y_i$ (tamper-proof experiments).}
+\visible<4-5>{\item Goal: estimate $\beta$ accurately.}
+\visible<5>{\item Adapt selection algorithm and payments.}
+\end{itemize}
+\end{frame}
+
+\begin{frame}{Budget Feasible Mechanism Design [Singer 2010]}
+Let $S\subset [N]$ be the selected users, and
+  $c=[c_i]_{i\in [N]}$ be the reported costs.  \\\bigskip
+\visible<2->{Let $V(S)\in\reals_+$ denote the \alert{value} of the experiments.}
+\visible<3->{$$\text{High }V(S) \Leftrightarrow \text{ estimate }\hat{\beta}(S) \text{ is good}$$}
+\visible<4->{
+\begin{block}{Reverse Auction Mechanism}
+ A mechanism $\mathcal{M}(c)=(S(c),p(c))$ comprises
+\begin{itemize}
+\item an \alert{allocation function} $S:\reals_+^N\to 2^{[N]}$, and
+\item a \alert{payment function} $p:\reals_+^N\to \reals_+^N$.
+\end{itemize}
+\end{block}
+}
+\end{frame}
+
+
+\begin{frame}{Budget Feasible Mechanism Design [Singer 2010] }
+    We seek mechanisms $\mathcal{M}=(S,p)$  that are: 
+    \pause
+    \vspace{0.3cm}
+    \begin{itemize}
+	\item Normalized: $p_i=0$ if $i\notin S$.
+            \vspace{0.2cm}
+            \pause
+        \item Individually Rational: $p_i\geq c_i,\;i\in S$
+            \vspace{0.2cm}
+            \pause
+        \item Truthful
+            \vspace{0.2cm}
+            \pause
+        \item budget feasible: $\sum_{i\in S} p_i \leq B$
+            \vspace{0.2cm}
+    \end{itemize}
+
+    \pause
+    \vspace{0.3cm}
+
+    In addition, $\mathcal{M}$ must be:
+    \vspace{0.3cm}
+    \pause
+    \begin{itemize}
+        \item computationally efficient: polynomial time
+            \pause
+            \vspace{0.2cm}
+        \item approximation: $OPT \leq \alpha V(S)$  with:
+            \begin{displaymath}
+                OPT = \max_{S\subset \mathcal{A}} \left\{V(S)\mid \sum_{i\in S}c_i\leq B\right\}
+            \end{displaymath}
+    \end{itemize}
+\end{frame}
+
+\begin{frame}{Strategic Subjects}
+    When $V$ is submodular:
+ %   \vspace{1cm}
+    \pause
+    \begin{itemize}
+        \item \alert{Randomized}, poly-time, universally truthful  mechanism,
+            approximation ratio: $7.91$ [Singer 2010, Chen \emph{et al.}, 2011]
+        \vspace{0.5cm}
+        \pause
+        \item Deterministic, \alert{exponential time}, truthful  mechanism,
+            approximation ratio: $8.34$ [Singer 2010, Chen \emph{et al.}, 2011]
+        \vspace{0.5cm}
+        \pause
+        \item \alert{Deterministic, poly-time}, truthful mechanisms for specific submodular functions $V$ :
+            \vspace{0.3cm}
+            \begin{itemize}
+                \item \textsc{Knapsack}: $2+\sqrt{2}$ [Singer 2010, Chen \emph{et al.}, 2011]
+                    \vspace{0.3cm}
+                \item \textsc{Matching}: 7.37 [Singer, 2010]
+                    \vspace{0.3cm}
+                \item \textsc{Coverage}: 31 [Singer, 2012]
+                    \vspace{0.3cm}
+            \end{itemize}
+    \end{itemize}
+\end{frame}
+
+\section{Main Results}
+
+\begin{frame}{Outline}
+    \tableofcontents[currentsection]
+\end{frame}
+
+
+\begin{frame}{Our Main Results}
+   \begin{theorem}<2->
+        There exists a deterministic,  budget feasible, individually rational and truthful mechanism for
+        EDP which runs in polynomial time. Its
+        approximation ratio is:
+        \begin{displaymath}
+        \frac{10e-3 + \sqrt{64e^2-24e + 9}}{2(e-1)}
+        \simeq 12.98
+        \end{displaymath}
+    \end{theorem}
+   \begin{theorem}<3->
+        There is no 2-approximate, budget feasible, individually rational and truthful mechanism for
+        EDP.     \end{theorem}
+
+\end{frame}
+
+\begin{frame}{Myerson's Theorem}
+\begin{theorem}[Myerson 1981]
+ A normalized mechanism $\mathcal{M} = (S,p)$ for a single parameter auction is
+truthful iff:
+\begin{enumerate}
+\item<2-> 
+ $S$ is \alert{monotone}, \emph{i.e.},%\\ for any agent $i$ and $c_i' \leq c_i$, for any fixed costs $c_{-i}$ of agents in $[N]\setminus\{i\}$,
+ $$\text{for all}~c_i' \leq c_i,\quad i\in S(c_i,
+c_{-i})\text{ implies }i\in S(c_i', c_{-i}),$$ and 
+\item<3->
+ subjects are paid \alert{threshold payments}, \emph{i.e.}, $$\text{for all }i\in S(c), \qquad p_i(c)=\inf\{c_i': i\in S(c_i', c_{-i})\}.$$
+\end{enumerate}
+\end{theorem}
+\uncover<4->{Focus on  \alert{monotone} mechanisms.}
+\end{frame}
+
+\begin{frame}{Can we use submodular maximization?}
+    \begin{block}{Allocation rule candidate}
+        \begin{itemize}
+        \item Compute $i^* = \arg\max_i V(\{i\})$
+        \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^*\})>V(S_G)$
+		\item $S_G$ otherwise
+		\end{itemize}
+	\end{itemize}
+    \end{block}
+
+\vspace*{2em}
+\pause
+
+Two problems:
+\begin{itemize}
+\item $\max$ breaks monotonicity
+    \pause
+\item threshold payments exceed budget
+\end{itemize}
+\end{frame}
+
+\begin{frame}{Randomized  Mechanism for Submodular $V$}
+    \begin{block}{Allocation rule}
+        \begin{itemize}
+        \item Compute $i^* = \arg\max_i V(\{i\})$
+        \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 \alt<1>{stop when the budget is exhausted}{\alert<2>{stop when $c_k\leq\frac{B}{2}\frac{V(S_G\cup\{i\}) - V(S_G)}{V(S_G\cup\{i\})}$}}
+            \end{itemize}
+        \item Return:
+            \begin{itemize}
+                    \alt<1-2>{
+		\item $i^*$ if $V(\{i^*\})>V(S_G)$
+    \item $S_G$ otherwise}{
+        \item
+\alert<3>{Select at random between $i^*$ and $S_G$}}
+\end{itemize}
+    \end{itemize}
+\end{block}
+\vspace{0.5cm}
+\begin{overprint}
+\onslide<4>
+[Singer 2010] Along with threshold payments, this mechanism is:
+\begin{itemize}
+\item poly-time,
+\item universally truthful, 
+\item budget-feasible
+\item 7.91-approximate [Chen \etal\ 2011].
+\end{itemize}
+\onslide<5->
+ \vspace{0.5cm}
+    \alert{Problem:} $OPT\leq 7.91 \cdot \alert{\mathbb{E}[V(S)]}$\ldots
+\end{overprint}
+\end{frame}
+
+\begin{frame}{Deterministic Mechanism for Submodular $V$}
+    \alert{Idea:} Use a proxy to compute the maximum
+    \begin{block}{Allocation rule}
+        \begin{itemize}
+        \item Compute $i^* = \arg\max_i V(\{i\})$
+        \item Compute $S_G$ greedily
+        \item Return:
+            \begin{itemize}
+                \item $i^*$ if $V(\{i^*\}) \geq \alt<1>{V(S_G)}{\alert<2>{OPT_{-i^*}}}$ 
+                \item $S_G$ otherwise
+            \end{itemize}
+        \end{itemize}
+    \end{block}
+    \vspace{0.5cm}
+\uncover<3->{
+[Singer 2010] Along with threshold payments, this mechanism is:
+\begin{itemize}
+\item truthful, 
+\item budget-feasible
+\item 8.34-approximate [Chen \etal\ 2011].
+\end{itemize}
+}   
+\uncover<4->
+{ \vspace{0.5cm}
+    \alert{Problem:} $OPT_{-i^*}$ is NP-hard to compute\ldots
+}
+\end{frame}
+
+
+\begin{frame}{Blueprint for Deterministic, Poly-time Algorithm}
+Azar and Gamzu 2008, Singer 2010, Chen \etal\ 2011:
+    \begin{block}{Allocation rule}
+        \begin{itemize}
+        \item Find $i^* = \arg\max_i V(\{i\})$
+        \item Compute $S_G$ greedily
+        \item Return:
+            \begin{itemize}
+                \item $\{i^*\}$ if $V(\{i^*\}) \geq \alert{L^*}$ 
+                \item $S_G$ otherwise
+            \end{itemize}
+        \end{itemize}
+    \end{block}
+    \vspace{0.5cm}
+    \begin{columns}[c]
+        \begin{column}{0.53\textwidth}
+Replace $OPT$ with a \alert{relaxation $L^*$}:\pause
+            \begin{itemize}
+		   \item computable in polynomial time
+                    \pause
+                \item close to $OPT_{-i^*}$
+		    \pause
+		\item monotone in costs $c$
+            \end{itemize}
+ 	\end{column}
+	\pause
+        \begin{column}{0.45\textwidth}
+   	\begin{itemize}
+                \item \textsc{Knapsack} (Chen \etal, 2011)
+                \item \textsc{Coverage} (Singer, 2012)
+            \end{itemize}
+	\end{column}
+       \end{columns}
+\end{frame}
+
+
+\begin{frame}{Which relaxation?}
+\alt<1>{\begin{block}{Submodular Maximization}
+\vspace*{-0.4cm}		
+\begin{align*}
+			\text{Maximize}\qquad &V(S) \\
+			\text{subj. to}\qquad &\textstyle\sum_{i\in S}c_i\leq B
+\end{align*}
+\end{block}
+}
+{
+\begin{block}{Multilinear Relaxation}
+\vspace*{-0.6cm}		
+\begin{align*}
+    \text{Maximize}\qquad &\alert<2>{F(\lambda)=\mathbb{E}_{S\sim\lambda}[V(S)]}\\
+			\text{subj. to}\qquad &\textstyle\sum_{i\in [N]}\lambda_i c_i\leq B,\\& \lambda_i\in[0,1], i\in [N]
+\end{align*}
+\vspace*{-0.6cm}		
+\end{block}
+}
+\medskip
+\pause
+For $\lambda^*$ the optimal solution:
+
+\begin{itemize}
+    \item
+        $V(S) = F(\lambda)\text{ for }\lambda_i=\mathbbm{1}_{i\in S}\quad\visible<3->{\Rightarrow\quad OPT \leq F(\lambda^*).}$ 
+        \pause
+    \item $F(\lambda^*)$ is monotone in $c$
+        \pause
+    \item Pipage rounding [Ageev and Sviridenko]:
+        \begin{displaymath}F(\lambda^*) \leq OPT + V(i^*)\end{displaymath}
+\end{itemize}
+\vspace{1cm}
+\pause
+Good relaxation candidate…\pause{} if it can be computed in poly-time.
+\end{frame}
+
+\begin{frame}{A relaxation for \textsc{EDP}}
+\alt<1>{
+    \begin{block}{\textsc{EDP} }
+        \vspace*{-0.4cm}		
+        \begin{align*}
+            \text{Maximize}\qquad &V(S) = \log \det\big(I+\sum_{i\in S}x_ix_i^T\big) \\
+            \text{subj. to}\qquad &\textstyle\sum_{i\in S}c_i\leq B
+        \end{align*}
+    \end{block}
+}
+{
+    \begin{block}{Convex Relaxation}
+        \vspace*{-0.4cm}		
+        \begin{align*}
+            \text{Maximize}\qquad &\alert<2>{L(\lambda)} = \log \det \big(I+\sum_{i\in [N]}\alert<2>{\lambda_i}x_ix_i^T\big) \\
+            \text{subj. to}\qquad &\textstyle\sum_{i\in [N]}\alert<2>{\lambda_i}c_i\leq B, \lambda_i\in [0,1]
+        \end{align*}
+    \end{block}
+}
+\pause
+\vspace{0.5cm}
+$L(\lambda^*)$ is:
+\begin{itemize}
+    \item Monotone in $c$
+        \pause
+    \item Poly-time: $L$ is concave
+        \pause
+    \item Close to $OPT$:\pause
+        \vspace{0.5cm}
+        \begin{block}{Technical Lemma}
+            \begin{displaymath}
+                OPT\leq  L(\lambda^*) \leq 2 OPT + 2V(\{i^*\})
+            \end{displaymath}
+        \end{block}
+\end{itemize}
+\end{frame}
+
+\begin{frame}{Proof Steps}
+           \begin{block}{Technical Lemma}
+                \begin{displaymath}
+                 OPT\leq   L(\lambda^*) \leq 2 OPT + 2V(\{i^*\})
+                \end{displaymath}
+            \end{block}
+            \uncover<2->{Relate $L$ to the multi-linear extension $F$:
+            \begin{itemize}
+                \item $F(\lambda)=\mathbb{E}_{S\sim\lambda}\Big[\log\det\big(I+\sum_{i\in S}x_ix_i^T\big)\Big]$
+                \item $L(\lambda)=\log\det\Big(I+\mathbb{E}_{S\sim\lambda}\big[\sum_{i\in S}x_ix_i^T\big]\Big)$
+            \end{itemize}
+\bigskip}
+\uncover<3->{
+    Bounding the derivatives of $\log\det$ $\Rightarrow$ $L(\lambda)\leq 2 F(\lambda)$
+}
+\bigskip
+
+\uncover<4>{Finally, $F(\lambda^*)\leq OPT+V(\{i^*\})$ (pipage rounding).}
+\end{frame}
+
+\begin{frame}{Summary}
+    \begin{block}{Allocation rule}
+        \begin{itemize}
+        \item Compute $i^* = \arg\max_i V(\{i\})$
+        \item Compute $S_G$ greedily
+        \item Compute $L(\lambda^*) = \max_{\lambda}\Big\{\log \det \big(I+\sum_{i\in [N]}\lambda_ix_ix_i^T\big),\; \sum_{i\in[N]}\lambda_ic_i\leq B\Big\}$
+        \item Return:
+            \begin{itemize}
+                \item $i^*$ if $V(\{i^*\}) \geq L(\lambda^*)$ 
+                \item $S_G$ otherwise
+            \end{itemize}
+        \end{itemize}
+    \end{block}
+    \vspace{0.5cm}
+    \pause
+    Along with threshold payments:
+    \begin{itemize}
+        \item individually rational, truthful, budget-feasible
+            \pause
+        \item poly-time
+            \pause
+        \item 12.98-approximate
+    \end{itemize}
+\end{frame}
+
+\begin{frame}{}
+    \begin{center}
+    \Huge{\alert{Are we done?}}
+    \end{center}
+\end{frame}
+
+\begin{frame}{Tiny glitch}
+    \begin{block}{Allocation rule}
+        \begin{itemize}
+            \item Compute $i^* = \arg\max_i V(\{i\})$
+            \item Compute $S_G$ greedily
+            \item Compute $\alert<2>{L(\lambda^*) = \max_{\lambda}\Big\{\log \det \big(I+\sum_{i\in [N]}\lambda_ix_ix_i^T\big),\; \sum_{i\in[N]}\lambda_ic_i\leq B\Big\}}$
+            \item Return:
+                \begin{itemize}
+                    \item $i^*$ if $V(\{i^*\}) \geq L(\lambda^*)$ 
+                    \item $S_G$ otherwise
+                \end{itemize}
+        \end{itemize}
+    \end{block}
+    \pause
+    \vspace{0.5cm}
+    \begin{itemize}
+        \item $L(\lambda^*)$ is monotone in $c$
+            \pause
+        \item but not an approximation of $L(\lambda^*)$
+    \end{itemize}
+\end{frame}
+
+\begin{frame}{$\varepsilon$-truthfulness}
+    Assume that:
+    \begin{displaymath}
+        c_i'\leq c_i-\varepsilon \Rightarrow L(\lambda^*_{c'})\geq L(\lambda^*_c)+\delta
+    \end{displaymath}
+
+    \pause
+    \vspace{1cm}
+    Then, if $\tilde{L}(\lambda^*_c)$ is a $\delta$-approximate of $L(\lambda^*_c)$
+    \begin{displaymath}
+        c_i'\leq c_i-\varepsilon \Rightarrow \tilde{L}(\lambda^*_{c'})\geq \tilde{L}(\lambda^*_c)
+    \end{displaymath}
+
+    \vspace{1cm}
+    \pause
+    Implies $\varepsilon$-truthfulness:
+    \begin{center}
+        \alert{users have not incentive to lie by more $\varepsilon$}
+    \end{center}
+\end{frame}
+
+\begin{frame}{Sensitivity analysis}
+    \begin{block}{Goal ($\varepsilon$, $\delta$)-monotonicity}
+        \begin{displaymath}
+            c_i'\leq c_i-\varepsilon \Rightarrow L(\lambda^*_{c'})\geq L(\lambda^*_c)+\delta
+        \end{displaymath}
+    \end{block}
+    \pause
+    \vspace{0.5cm}
+
+    Bad news:
+    \begin{displaymath}
+        \frac{\partial L(\lambda^*_c)}{\partial c_i} \propto \lambda_i^*\only<3->{\alert{\geq \alpha}}
+    \end{displaymath}
+
+    \pause
+    \vspace{0.5cm}
+    Solution: regularize the problem
+    \begin{displaymath}
+        L(\lambda^*) = \max_{\lambda}\Big\{\log \det \big(I+\sum_{i\in [N]}\lambda_ix_ix_i^T\big),\; \sum_{i\in[N]}\lambda_ic_i\leq B,\; \alert{\lambda_i\geq \alpha}\Big\}
+    \end{displaymath}
+
+    \pause
+    \vspace{0.5cm}
+    Then carefully tune all the parameters…
+\end{frame}
+
+
+\section{Generalization}
+
+\begin{frame}{Outline}
+    \tableofcontents[currentsection]
+\end{frame}
+
+\begin{frame}{Towards More General ML Tasks}
+   \begin{center}
+        \includegraphics<1>[scale=0.4]{st2.pdf}
+        \includegraphics<2>[scale=0.4]{st3.pdf}
+        \includegraphics<3>[scale=0.4]{st4.pdf}
+        \includegraphics<4-5>[scale=0.4]{st25.pdf}
+        \includegraphics<6->[scale=0.4]{st26.pdf}
+    \end{center}
+
+    \begin{overprint}
+        \onslide<1>
+		\begin{center}$N$ experiment subjects\end{center}
+       	\onslide<2>
+            \begin{center}
+                $x_i\in \Omega$: public features
+            \end{center}
+        \onslide<3>
+            \begin{center}
+                $y_i\in \reals$: private data 
+            \end{center}
+        \onslide<4-5>
+             \begin{center}
+                \textbf{Hypothesis.}  There exists $h:\Omega\to \reals$ s.t.
+ %   \begin{displaymath}
+        $y_i =  h(x_i) + \varepsilon_i,$ %\quad
+	where $\varepsilon_i$ are independent.
+	\visible<5>{Examples: Logistic Regression, LDA, SVMs, \etc}
+  % \end{displaymath}
+		\end{center}
+%$$y_i = \beta^Tx_i + \varepsilon_i, i=1,\ldots, N$$ 
+            %\end{center}
+	    \onslide<6>
+	    \begin{center}
+		Experimenter {\tt E} wishes to learn $h$, and has a prior distribution over $$\mathcal{H}=\{\text{mappings from }\Omega\text{ to }\reals\}.$$ 
+	    \end{center}
+    \onslide<7->\begin{center}
+\vspace*{-0.5cm}
+%    \begin{block}
+%{Value function: Information gain}
+        \begin{displaymath}
+            V(S) = H(h) - H(h\mid y_i,i\in S),\quad S\subseteq[N]
+        \end{displaymath}
+ %   \end{block}
+	\visible<8>{$V$ is submodular! [Krause and Guestrin 2009]}
+    \end{center}
+	\end{overprint}
+
+\end{frame}
+
+\begin{comment}
+    \begin{itemize}
+        \item Generative model: $y_i = f(x_i) + \varepsilon_i,\;i\in\mathcal{A}$
+        \pause
+        \item prior knowledge of the experimenter: $f$ is a \alert{random variable}
+        \pause
+        \item \alert{uncertainty} of the experimenter: entropy $H(f)$
+        \pause
+        \item after observing $\{y_i,\; i\in S\}$, uncertainty: $H(f\mid S)$
+    \end{itemize}
+
+    \pause
+    \vspace{0.5cm}
+
+    \begin{block}{Value function: Information gain}
+        \begin{displaymath}
+            V(S) = H(f) - H(f\mid S),\quad S\subset\mathcal{A}
+        \end{displaymath}
+    \end{block}
+
+    \pause
+    \vspace{0.5cm}
+
+    $V$ is \alert{submodular} $\Rightarrow$ randomized budget feasible mechanism
+\end{frame}
+
+\end{comment}
+
+\begin{frame}{Conclusion}
+    \begin{itemize}
+        \item Experimental design + Budget Feasible Mechanisms
+        \vspace{1cm}
+        \pause
+        \item Deterministic mechanism for other ML Tasks? General submodular functions?
+            \vspace{1cm}
+            \pause
+        \item  Approximation ratio $\simeq \alert{13}$. Lower bound: \alert{$2$}
+    \end{itemize}
+\end{frame}
+\begin{frame}{}
+\vspace{\stretch{1}}
+\begin{center}
+{\Huge Thank you!}
+\end{center}
+\vspace{\stretch{1}}
+\end{frame}
+
+\begin{frame}{Non-Homotropic Prior}
+Recall that:
+\begin{align*}
+V(S)&=H(\beta)-H(\beta\mid y_i,i\in S)\\
+& = \frac{1}{2}\log\det (R^{-1}+\sum_{i\in S}x_ix_i^T)
+\end{align*}
+What if $R\neq I$?
+\begin{theorem}
+ There exists a truthful, poly-time, and budget feasible mechanism for the objective
+ function $V$ above. Furthermore, 
+ the algorithm computes a set $S^*$ such that:
+ \begin{displaymath}
+    OPT \leq 
+    \frac{5e-1}{e-1}\frac{2}{\mu\log(1+1/\mu)}V(S^*) + 5.1 
+\end{displaymath}
+where $\mu$ is the largest eigenvalue of $R$.
+\end{theorem}
+\end{frame}
+
+\end{document}
diff --git a/slides/11-25-2014/st1.pdf b/slides/11-25-2014/st1.pdf
new file mode 100755
index 0000000..27e8111
--- /dev/null
+++ b/slides/11-25-2014/st1.pdf
diff --git a/slides/11-25-2014/st10.pdf b/slides/11-25-2014/st10.pdf
new file mode 100755
index 0000000..5d435cd
--- /dev/null
+++ b/slides/11-25-2014/st10.pdf
diff --git a/slides/11-25-2014/st10a.pdf b/slides/11-25-2014/st10a.pdf
new file mode 100755
index 0000000..5d435cd
--- /dev/null
+++ b/slides/11-25-2014/st10a.pdf
diff --git a/slides/11-25-2014/st10b.pdf b/slides/11-25-2014/st10b.pdf
new file mode 100755
index 0000000..1499076
--- /dev/null
+++ b/slides/11-25-2014/st10b.pdf
diff --git a/slides/11-25-2014/st10c.pdf b/slides/11-25-2014/st10c.pdf
new file mode 100755
index 0000000..7a6473a
--- /dev/null
+++ b/slides/11-25-2014/st10c.pdf
diff --git a/slides/11-25-2014/st10d.pdf b/slides/11-25-2014/st10d.pdf
new file mode 100755
index 0000000..890ab3c
--- /dev/null
+++ b/slides/11-25-2014/st10d.pdf
diff --git a/slides/11-25-2014/st10e.pdf b/slides/11-25-2014/st10e.pdf
new file mode 100755
index 0000000..890ab3c
--- /dev/null
+++ b/slides/11-25-2014/st10e.pdf
diff --git a/slides/11-25-2014/st10f.pdf b/slides/11-25-2014/st10f.pdf
new file mode 100755
index 0000000..2e181b3
--- /dev/null
+++ b/slides/11-25-2014/st10f.pdf
diff --git a/slides/11-25-2014/st11a.pdf b/slides/11-25-2014/st11a.pdf
new file mode 100755
index 0000000..04dd73b
--- /dev/null
+++ b/slides/11-25-2014/st11a.pdf
diff --git a/slides/11-25-2014/st11b.pdf b/slides/11-25-2014/st11b.pdf
new file mode 100755
index 0000000..0b5a7e3
--- /dev/null
+++ b/slides/11-25-2014/st11b.pdf
diff --git a/slides/11-25-2014/st11c.pdf b/slides/11-25-2014/st11c.pdf
new file mode 100755
index 0000000..2096fc2
--- /dev/null
+++ b/slides/11-25-2014/st11c.pdf
diff --git a/slides/11-25-2014/st11d.pdf b/slides/11-25-2014/st11d.pdf
new file mode 100755
index 0000000..eafc148
--- /dev/null
+++ b/slides/11-25-2014/st11d.pdf
diff --git a/slides/11-25-2014/st1a.pdf b/slides/11-25-2014/st1a.pdf
new file mode 100755
index 0000000..1ded757
--- /dev/null
+++ b/slides/11-25-2014/st1a.pdf
diff --git a/slides/11-25-2014/st1b.pdf b/slides/11-25-2014/st1b.pdf
new file mode 100755
index 0000000..a447246
--- /dev/null
+++ b/slides/11-25-2014/st1b.pdf
diff --git a/slides/11-25-2014/st1c.pdf b/slides/11-25-2014/st1c.pdf
new file mode 100755
index 0000000..cfdc1a8
--- /dev/null
+++ b/slides/11-25-2014/st1c.pdf
diff --git a/slides/11-25-2014/st1d.pdf b/slides/11-25-2014/st1d.pdf
new file mode 100755
index 0000000..24734ef
--- /dev/null
+++ b/slides/11-25-2014/st1d.pdf
diff --git a/slides/11-25-2014/st1dd.pdf b/slides/11-25-2014/st1dd.pdf
new file mode 100755
index 0000000..b2e596f
--- /dev/null
+++ b/slides/11-25-2014/st1dd.pdf
diff --git a/slides/11-25-2014/st1e.pdf b/slides/11-25-2014/st1e.pdf
new file mode 100755
index 0000000..4e32eff
--- /dev/null
+++ b/slides/11-25-2014/st1e.pdf
diff --git a/slides/11-25-2014/st1f.pdf b/slides/11-25-2014/st1f.pdf
new file mode 100755
index 0000000..4112c05
--- /dev/null
+++ b/slides/11-25-2014/st1f.pdf
diff --git a/slides/11-25-2014/st1g.pdf b/slides/11-25-2014/st1g.pdf
new file mode 100755
index 0000000..13a7cf8
--- /dev/null
+++ b/slides/11-25-2014/st1g.pdf
diff --git a/slides/11-25-2014/st1h.pdf b/slides/11-25-2014/st1h.pdf
new file mode 100755
index 0000000..13a7cf8
--- /dev/null
+++ b/slides/11-25-2014/st1h.pdf
diff --git a/slides/11-25-2014/st2.pdf b/slides/11-25-2014/st2.pdf
new file mode 100755
index 0000000..b0dff4e
--- /dev/null
+++ b/slides/11-25-2014/st2.pdf
diff --git a/slides/11-25-2014/st25.pdf b/slides/11-25-2014/st25.pdf
new file mode 100755
index 0000000..c898155
--- /dev/null
+++ b/slides/11-25-2014/st25.pdf
diff --git a/slides/11-25-2014/st26.pdf b/slides/11-25-2014/st26.pdf
new file mode 100755
index 0000000..b5c9f2d
--- /dev/null
+++ b/slides/11-25-2014/st26.pdf
diff --git a/slides/11-25-2014/st3.pdf b/slides/11-25-2014/st3.pdf
new file mode 100755
index 0000000..f018bd7
--- /dev/null
+++ b/slides/11-25-2014/st3.pdf
diff --git a/slides/11-25-2014/st31a.pdf b/slides/11-25-2014/st31a.pdf
new file mode 100755
index 0000000..81a6200
--- /dev/null
+++ b/slides/11-25-2014/st31a.pdf
diff --git a/slides/11-25-2014/st31b.pdf b/slides/11-25-2014/st31b.pdf
new file mode 100755
index 0000000..9230122
--- /dev/null
+++ b/slides/11-25-2014/st31b.pdf
diff --git a/slides/11-25-2014/st31c.pdf b/slides/11-25-2014/st31c.pdf
new file mode 100755
index 0000000..84d8798
--- /dev/null
+++ b/slides/11-25-2014/st31c.pdf
diff --git a/slides/11-25-2014/st31d.pdf b/slides/11-25-2014/st31d.pdf
new file mode 100755
index 0000000..5c941cc
--- /dev/null
+++ b/slides/11-25-2014/st31d.pdf
diff --git a/slides/11-25-2014/st31dd.pdf b/slides/11-25-2014/st31dd.pdf
new file mode 100755
index 0000000..cca1133
--- /dev/null
+++ b/slides/11-25-2014/st31dd.pdf
diff --git a/slides/11-25-2014/st31e.pdf b/slides/11-25-2014/st31e.pdf
new file mode 100755
index 0000000..983e7fe
--- /dev/null
+++ b/slides/11-25-2014/st31e.pdf
diff --git a/slides/11-25-2014/st31f.pdf b/slides/11-25-2014/st31f.pdf
new file mode 100755
index 0000000..f8716f4
--- /dev/null
+++ b/slides/11-25-2014/st31f.pdf
diff --git a/slides/11-25-2014/st31g.pdf b/slides/11-25-2014/st31g.pdf
new file mode 100755
index 0000000..fa1083d
--- /dev/null
+++ b/slides/11-25-2014/st31g.pdf
diff --git a/slides/11-25-2014/st4.pdf b/slides/11-25-2014/st4.pdf
new file mode 100755
index 0000000..da4b05b
--- /dev/null
+++ b/slides/11-25-2014/st4.pdf
diff --git a/slides/11-25-2014/st5.pdf b/slides/11-25-2014/st5.pdf
new file mode 100755
index 0000000..9b0ec26
--- /dev/null
+++ b/slides/11-25-2014/st5.pdf
diff --git a/slides/11-25-2014/st6.pdf b/slides/11-25-2014/st6.pdf
new file mode 100755
index 0000000..a6ed679
--- /dev/null
+++ b/slides/11-25-2014/st6.pdf
diff --git a/slides/11-25-2014/st6a.pdf b/slides/11-25-2014/st6a.pdf
new file mode 100755
index 0000000..c3caafb
--- /dev/null
+++ b/slides/11-25-2014/st6a.pdf
diff --git a/slides/11-25-2014/st6b.pdf b/slides/11-25-2014/st6b.pdf
new file mode 100755
index 0000000..d4cc19c
--- /dev/null
+++ b/slides/11-25-2014/st6b.pdf
diff --git a/slides/11-25-2014/st6c.pdf b/slides/11-25-2014/st6c.pdf
new file mode 100755
index 0000000..6cdcc1c
--- /dev/null
+++ b/slides/11-25-2014/st6c.pdf
diff --git a/slides/11-25-2014/st6d.pdf b/slides/11-25-2014/st6d.pdf
new file mode 100755
index 0000000..b16466f
--- /dev/null
+++ b/slides/11-25-2014/st6d.pdf
diff --git a/slides/11-25-2014/st6e.pdf b/slides/11-25-2014/st6e.pdf
new file mode 100755
index 0000000..a532f43
--- /dev/null
+++ b/slides/11-25-2014/st6e.pdf
diff --git a/slides/11-25-2014/st6f.pdf b/slides/11-25-2014/st6f.pdf
new file mode 100755
index 0000000..45b9414
--- /dev/null
+++ b/slides/11-25-2014/st6f.pdf
diff --git a/slides/11-25-2014/st7.pdf b/slides/11-25-2014/st7.pdf
new file mode 100755
index 0000000..ba0d63c
--- /dev/null
+++ b/slides/11-25-2014/st7.pdf
diff --git a/slides/11-25-2014/st8.pdf b/slides/11-25-2014/st8.pdf
new file mode 100755
index 0000000..8f59326
--- /dev/null
+++ b/slides/11-25-2014/st8.pdf
diff --git a/slides/11-25-2014/st9.pdf b/slides/11-25-2014/st9.pdf
new file mode 100755
index 0000000..8f4d0e1
--- /dev/null
+++ b/slides/11-25-2014/st9.pdf
diff --git a/slides/11-25-2014/stg-1.pdf b/slides/11-25-2014/stg-1.pdf
new file mode 100755
index 0000000..38d5ab0
--- /dev/null
+++ b/slides/11-25-2014/stg-1.pdf
diff --git a/slides/11-25-2014/stg-2.pdf b/slides/11-25-2014/stg-2.pdf
new file mode 100755
index 0000000..b4850f9
--- /dev/null
+++ b/slides/11-25-2014/stg-2.pdf
diff --git a/slides/11-25-2014/stg-3.pdf b/slides/11-25-2014/stg-3.pdf
new file mode 100755
index 0000000..268b0aa
--- /dev/null
+++ b/slides/11-25-2014/stg-3.pdf
diff --git a/slides/11-25-2014/stg-4.pdf b/slides/11-25-2014/stg-4.pdf
new file mode 100755
index 0000000..70cab06
--- /dev/null
+++ b/slides/11-25-2014/stg-4.pdf
diff --git a/slides/11-25-2014/stg-5.pdf b/slides/11-25-2014/stg-5.pdf
new file mode 100755
index 0000000..9b1d5d5
--- /dev/null
+++ b/slides/11-25-2014/stg-5.pdf
diff --git a/slides/11-25-2014/stg-6.pdf b/slides/11-25-2014/stg-6.pdf
new file mode 100755
index 0000000..636bcca
--- /dev/null
+++ b/slides/11-25-2014/stg-6.pdf
diff --git a/slides/11-25-2014/stg-7.pdf b/slides/11-25-2014/stg-7.pdf
new file mode 100755
index 0000000..a964ac3
--- /dev/null
+++ b/slides/11-25-2014/stg-7.pdf
diff --git a/slides/11-25-2014/stg-8.pdf b/slides/11-25-2014/stg-8.pdf
new file mode 100755
index 0000000..b781a27
--- /dev/null
+++ b/slides/11-25-2014/stg-8.pdf
diff --git a/slides/11-25-2014/stg-9.pdf b/slides/11-25-2014/stg-9.pdf
new file mode 100755
index 0000000..e69de29
--- /dev/null
+++ b/slides/11-25-2014/stg-9.pdf