path: root/slides/BudgetFeasibleExperimentalDesignGoogle.tex

\documentclass[10pt]{beamer}
\usepackage[utf8x]{inputenc}
\usepackage[greek,english]{babel}
\usepackage[LGR,T1]{fontenc}
\usepackage{amsmath,bbm,verbatim}
\usepackage{algpseudocode,algorithm,bbding}
\usepackage{graphicx}
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}
\usetheme{technicolor}
\newcommand{\E}{{\tt E}}

\title{Budget Feasible Mechanisms \hspace*{5cm}for Experimental Design}
\subtitle{Thibaut Horel$^*$, Stratis Ioannidis$^\dagger$, and S. Muthukrishnan$^\ddagger$}
\author{$^*$INRIA-ENS, $^\dagger$Technicolor, $^\ddagger$Rutgers University}
\setbeamercovered{transparent}
%\setbeamertemplate{navigation symbols}{}
%\AtBeginSection[]
%{
%\begin{frame}<beamer>
%\frametitle{Outline}
%\tableofcontents[currentsection]
%\end{frame}
%}


\newcommand{\ie}{\emph{i.e.}}
\newcommand{\eg}{\emph{e.g.}}
\newcommand{\etc}{\emph{etc.}}
\newcommand{\etal}{\emph{et al.}}
\newcommand{\reals}{\ensuremath{\mathbb{R}}}

\usefonttheme[onlymath]{serif}
\begin{document}

\maketitle

\section{Introduction}


\begin{frame}{Experimental Design}
   \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}
 %       \includegraphics<8>[scale=0.4]{st31g.pdf}
   \end{center}

 %   \begin{center}
 %       \begin{overprint}
 %       \onslide<1-8>\begin{center}\end{center}
%	\end{overprint}
 %   \end{center}
\end{frame} 

\begin{frame}{Motivation and Challenges}
%    \begin{overprint}
    \begin{itemize}
	\item<1-> Applications
            \begin{itemize}
		\item Medicine/Sociology
		\item Online surveys
		\item A/B testing
		\item Data markets
	    \end{itemize}
\vspace*{1cm}
        \item<2-> Challenges
	     \begin{itemize}
	     	\item Which experiments are \alert{most valuable}?
		\item What if agents are  \alert{strategic}?
             \end{itemize}
    \end{itemize}
%     \end{overprint}
\end{frame}

\begin{frame}{Our Contributions}
    \pause
    \begin{itemize}
        \item Experimental design when users are strategic
	\pause
	     \begin{itemize}
	     	\item Budget Feasible Mechanisms [Singer 2010]
	     \end{itemize}
	\pause
	\vspace*{1cm}
        \item Linear Regression 
	    \pause
	    \begin{itemize}
                \item We present a deterministic, poly-time, truthful, budget feasible, 12.98-approximate mechanism. 
	%	\pause
	%	\vspace*{0.5cm}
	%	\item Previous results:
	%		\begin{itemize}
	%		\item  \alert{Randomized}, poly-time, universally truthful,  7.91-approximate mechanism. [Singer 2010, Chen 2011]
	%		\item Deterministic, \alert{exponential time}, truthful mechanism. [Chen 2011] 
	%		\end{itemize}
	    \end{itemize}
            \pause
	    \vspace*{1cm}
        \item Generalization to other machine learning tasks. 
   \end{itemize}
\end{frame}


\section{Setting}
\begin{frame}{Outline}
\tableofcontents
\end{frame}

\begin{frame}{Outline}
    \tableofcontents[currentsection]
\end{frame}


\begin{frame}{Formulating the 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, etc.)
            \end{center}
            \onslide<4>
             %\begin{}
                \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}
%$$y_i = \beta^Tx_i + \varepsilon_i, i=1,\ldots, N$$ 
            %\end{center}
	    \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 only if $i$ is paid at least $c_i$.}
	    \end{center} 
	    \onslide<10>
	    \begin{center}{\tt E}  estimates ${\beta}$  through \emph{ridge regression}.
	    \end{center}
	    \onslide<11>
	    \begin{center}
%\begin{enumerate}
Goal: Determine (a) who to pay and (b) how much,\\ so that $\hat{\beta}$ is as accurate as possible.
%\begin{align*}
% \text{Determine (a) who to pay:}\quad &S\subseteq [N], \text{ and}\\
% \text{(b)~ how much:}\quad &p_i\in \reals_+,~~i\in S.
%\end{align*}
%\end{enumerate}
	    \end{center}
	    \onslide<12->
	    \begin{center}Users are \alert{strategic}: they may lie about costs $c_i$\visible<13>{\\ Users \alert{cannot manipulate $x_i$ or $y_i$}.} %\\(tamper-proof experiments)
	    \end{center}
	    
        \end{overprint}
    \end{center}

\end{frame}

\begin{frame}{Budget Feasible Mechanism Design [Singer 2010]}
Let $S\subset [N]$ be the set of experiments performed, and
  $c=[c_i]_{i\in [N]}$ be the subject 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 close to }\beta $$}
\visible<4->{
%\item<1->Fix budget $B$ and value function $V:2^{[N]}\to\reals_+$
\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: $p_i(c_i,c_{-i})-\mathbbm{1}_{i\in S(c_i,c_{-i})}\cdot c_i \geq p_i(c_i',c_{-i})-\mathbbm{1}_{i\in S(c_i',c_{-i})}\cdot c_i $
            \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}{Which Experiments Are Informative?}

\alt<1>{What is the appropriate value function $V$?} {Let $S\subset [N]$ be the set of experiments performed.\\\medskip}
%\end{overprint}
\visible<3->{Assume that \E\ has a \emph{prior} on $\beta$:
$$\beta \sim \mathcal{N}(0,\sigma^2 R). $$}
\visible<4->{Maximum a-posteriori estimation:
\begin{align*}
    \hat{\beta} &= \argmax_{\beta\in\reals^d} \mathbf{P}(\beta\mid y_i, i\in S) \\
&=\argmin_{\beta\in\reals^d} \big(\sum_{i\in S} (y_i - {\beta}^Tx_i)^2
    + \only<4-5>{\alert<5->{{\beta}^TR^{-1}\beta}\big)} \only<6>{\lambda\alert{\|\beta\|_2^2}\big)~~~~~} 
%= (R+{X_S}^TX_S)^{-1}X_S^Ty_S 
\end{align*}
}
\visible<5->{\hspace*{3in}\alert{Ridge Regression}\\}
\visible<6>{\hspace*{2.8in}\alert{$R=\lambda I$: homotropic prior}}
\end{frame}

\begin{frame}{Which Experiments Are Informative? (contd.)}
Let $S\subset [N]$ be the set of experiments performed.\\\bigskip

\visible<2->{
Information Gain/D-optimality Criterion:
\begin{align*}
V(S)&=H(\beta)-H(\beta\mid y_i,i\in S)\\
\visible<3->{& = \frac{1}{2}\log\det (R^{-1}+\sum_{i\in S}x_ix_i^T)}
\end{align*}
}
\visible<4->{ \emph{I.e.}: $$\alert{\text{Value of~}S=\text{Reduction of Uncertainty.}} $$}

\end{frame}

\begin{frame}{A Few Properties of the Value Function}
\begin{align*}
V(S)&= \frac{1}{2}\log\det (R^{-1}+\sum_{i\in S}x_ix_i^T)
\end{align*}
\visible<2->{\begin{align*}V(S\cup\{i\})-V(S) &= \log(1+x_i^TA_S^{-1}x_i    ), \quad\text{where }\\A_S &= R^{-1}+\sum_{i\in S}x_ix_i^T\end{align*}}
\visible<3->{
\begin{itemize}
\item<3-> Increase is greatest when $x_i$ \alert{spans a new direction}
\item<4-> Adding an experiment \alert{always helps}
\item<5-> $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}{Full Information Setting}
\onslide<2->{
\begin{block}{\textsc{Experimental Design Problem (EDP)} }
\vspace*{-0.4cm}		
\begin{align*}
			\text{Maximize}\qquad &V(S) = \log \det (\alert<3>{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}
}
\begin{itemize}
\item<3->$R=I$: homotropic prior, $\lambda=1$
\item<4-> EDP is NP-hard 
\item<5-> $V$ is submodular, monotone, non-negative, and $V(\emptyset)=0$
\item<6-> $\frac{1}{1-1/e}$-approximable (Sviridenko 2004, Krause and Guestrin 2005)
\end{itemize}
	    


\end{frame}

%\begin{frame}{Classic Experimental Design}
%\begin{center}
%\includegraphics[scale=0.3]{st10.pdf}
%\end{center}
%\begin{align*}
%\text{Maximize}& & V(S) &= \log \det (R^{-1}+X^T_SX_S) \\
%\text{subj. to}& & |S|&\leq k
%\end{align*}
%\end{frame}
	
\begin{comment}
\begin{frame}{Cardinality vs. Budget Constraint}
\begin{center}
\includegraphics<1>[scale=0.3]{st10a.pdf}
\includegraphics<2>[scale=0.3]{st10b.pdf}
\includegraphics<3>[scale=0.3]{st10c.pdf}
\includegraphics<4>[scale=0.3]{st10d.pdf}
\includegraphics<5->[scale=0.3]{st10f.pdf}
\end{center}

    \begin{center}
        \begin{overprint}
\onslide<1>\begin{align*}
\text{Maximize}& & V(S) &= \log \det (R^{-1}+X^T_SX_S) \\
\text{subj. to}& & |S|&\leq k
\end{align*}
 
           \onslide<6->
\begin{block}{\textsc{Experimental Design Problem (EDP)} }
\vspace*{-0.4cm}		
\begin{align*}
			\text{Maximize}\qquad &V(S) = \log \det (\alert<7>{I}+X^T_SX_S) \\
			\text{subj. to}\qquad &\textstyle\sum_{i\in S}c_i\leq B
		\end{align*}
\end{block}
		\visible<7>{\alert{$R=I$: homotropic prior}}
	    
          \end{overprint}
    \end{center}
\end{frame}

\begin{frame}{Full-Information Setting}	
\begin{block}{\textsc{Experimental Design Problem (EDP)} }
\vspace*{-0.4cm}		
\begin{align*}
			\text{Maximize}\qquad &V(S) = \log \det ({I}+X^T_SX_S) \\
			\text{subj. to}\qquad &\textstyle\sum_{i\in S}c_i\leq B
		\end{align*}
\end{block}
\begin{itemize}
\item<2-> EDP is NP-hard 
\item<3-> $V$ is submodular, monotone, non-negative, and $V(\emptyset)=0$
\item<4-> $\frac{1}{1-1/e}$-approximable (Sviridenko 2004, Krause and Guestrin 2005)
\end{itemize}
\end{frame}

\begin{frame}{Strategic Subjects}
%\begin{center}
%\includegraphics<1->[scale=0.3]{st10c.pdf}
%\end{center}
%\begin{overprint}
\begin{itemize}
\visible<2->{\item
Subjects are \alert{strategic} and may lie about costs $c_i$.}\\\bigskip
\visible<3>{\item
Subjects \alert{do not lie} about $y_i$ (tamper-proof experiments).}
\end{itemize}
\end{frame}

\begin{frame}{Budget Feasible Mechanism Design [Singer 2010]}
\begin{center}
\includegraphics<1>[scale=0.3]{st11a.pdf}
\includegraphics<2>[scale=0.3]{st11b.pdf}
\includegraphics<3>[scale=0.3]{st11c.pdf}
\includegraphics<4>[scale=0.3]{st11d.pdf}
\end{center}
\begin{itemize}
%\item<1->Fix budget $B$ and value function $V:2^{[N]}\to\reals_+$
\item<2->Let $c=[c_i]_{i\in [N]}$ be the subject costs.
\item<3-> A mechanism $\mathcal{M}(c)=(S(c),p(c))$ comprises
\begin{itemize}
\item<3-> an \alert{allocation function} $S:\reals_+^N\to 2^{[N]}$, and
\item<4> a \alert{payment function} $p:\reals_+^N\to \reals_+^N$.
\end{itemize}
\end{itemize}
\end{frame}
%\section{Budget feasible mechanism design}

%\begin{frame}{Budget Feasible Mechanism Design [Singer 2010]}
%\begin{itemize}
%    \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}^+$
%        \vspace{0.3cm}
%        \pause
%    \item $c_i\in\mathbb{R}^+$ price of seller's $i$ good
%        \vspace{0.3cm}
%        \pause
%    \item $B$ budget constraint of the buyer
%\end{itemize}
%
%\vspace{0.5cm}
%\pause
%
%\begin{block}{Goal}
%    \begin{itemize}
%        \item Find $S\subset \mathcal{A}$ \alert{maximizing} $V(S)$
%            \vspace{0.3cm}
%        \item Find \alert{payment} $p_i$ to seller $i\in S$
%    \end{itemize}
%\end{block}
%\end{frame}
\end{comment}

\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}


\begin{comment}
\begin{frame}{Outline}
    \tableofcontents[currentsection]
\end{frame}

\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 vector of features $x_i\in\mathbb{R}^d$
        \item Private data $y_i\in\mathbb{R}$
    \end{itemize}

    \vspace{0.5cm}

    Gaussian linear model:
    \begin{displaymath}
        y_i = \beta^T x_i + \varepsilon_i,\quad\beta\in\mathbb{R}^d,\;
        \varepsilon_i\sim\mathcal{N}(0,\sigma^2)
    \end{displaymath}

    \pause 
    \vspace{0.5cm} 

    Which users to select?\pause{} Experimental design $\Rightarrow$ D-optimal criterion

    \vspace{0.5cm}

    \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 \textsf{\alert{subject to}}\quad |S|\leq k
    \end{displaymath}
    \end{block}
\end{frame}

\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 \textsf{\alert{subject to}}\quad \sum_{i\in S}c_i\leq B
    \end{displaymath}

    \vspace{1cm}

    \begin{itemize}
        \item the non-strategic optimization problem is NP-hard
            \vspace{0.3cm}
            \pause
        \item $V$ is submodular
            \vspace{0.3cm}
            \pause
        \item previous results give a randomized budget feasible mechanism
            \vspace{0.3cm}
            \pause
        \item deterministic mechanism?
    \end{itemize}
\end{frame}

\begin{frame}{Main result}
\end{comment} 

\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}{A Greedy Construction for Submodular $V$}
Construct $S_G$ by adding elements with \emph{highest marginal-value-per-cost}.\\
\bigskip
\visible<2->{If $S_G=S$ so far, add to it: 
\begin{align*}
    i = \argmax_{j\in\mathcal{N}\setminus S}\frac{V(S\cup\{i\}) - V(S)}{c_i}\label{greedy}
\end{align*}
Stop when budget $B$ is reached.
}

\end{frame}

\begin{frame}{Constant-Approximation Algorithm for Submodular $V$}
    \begin{block}{Allocation $S$:}
        \begin{itemize}
        \item Let $i^* = \arg\max_i V(\{i\})$
        \item Compute $S_G$ greedily over $[N]\setminus \{i^*\}$
	\item Return:
		\begin{itemize}
		\item $i^*$ if $V(\{i^*\})>V(S_G)$
		\item $S_G$ o.w.
		\end{itemize}
	\end{itemize}
    \end{block}
\vspace*{2em}
\uncover<2->{
[Singer 2010] This algorithm is:
\begin{itemize}
\item poly-time,
\item $\frac{5e}{e-1}$-approximate.
\end{itemize}
}
\uncover<3->
{ \vspace{0.5cm}
    \alert{Problem:} As a mechanism, it is not monotone\ldots
}
\end{frame}

\begin{frame}{Randomized  Mechanism for Submodular $V$}
    \begin{block}{Allocation $S$:}
        \begin{itemize}
        \item Let $i^* = \arg\max_i V(\{i\})$
        \item Compute $S_G$ greedily over $[N]\setminus \{i^*\}$
	\item Return $S$:
		\begin{itemize}
		\item Selected at random between $i^*$ and $S_G$
		\end{itemize}
	\end{itemize}
    \end{block}
    \vspace{0.5cm}
\uncover<2->{
[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}
}
\uncover<3->
{ \vspace{0.5cm}
    \alert{Problem:} $OPT\leq 7.91 \cdot \alert{\mathbb{E}[V(S)]}$\ldots
}
\end{frame}

\begin{frame}{Deterministic Mechanism for Submodular $V$}
    \begin{block}{Allocation $S$}
        \begin{itemize}
        \item Find $i^* = \arg\max_i V(\{i\})$
        \item Compute $S_G$ greedily over $[N]\setminus \{i^*\}$
        \item Return:
            \begin{itemize}
                \item $\{i^*\}$ if $V(\{i^*\}) \geq \alert<3>{OPT_{-i^*}}$ 
                \item $S_G$ otherwise
            \end{itemize}
        \end{itemize}
    \end{block}
    \vspace{0.5cm}
\uncover<2->{
[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<3->
{ %\vspace{0.1cm}
    \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 $S$}
        \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.2cm}
    \begin{columns}[c]
        \begin{column}{0.53\textwidth}
Key idea:\\ 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}{Finding a 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 &F(\lambda)=\mathbb{E}_{\lambda}[V(S)] = \textstyle\sum_{S\subset [N]}V(S)\prod_{i\in S}\lambda_i\prod_{i\notin S}(1-\lambda_i)\\
			\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
\visible<2->{Replace $V$ with expectation when $i\in[N]$ is included with probability $\lambda_i$. \\}
\visible<3->{\begin{itemize}
\item
For $S\subseteq [N]$, 
$V(S) = F(\lambda)\text{ for }\lambda_i=\mathbbm{1}_{i\in S}\quad\visible<4->{\Rightarrow\quad OPT \leq F(\lambda^*).}$ 
\visible<5->{%\vspace*{-0.6cm}
\item If $V$ is submodular, for any $\lambda\in [0,1]^N$, there exists  $\bar{\lambda}$ \\with \emph{at most one} $\bar{\lambda}_i\notin\{0,1\}$ s.t.
\begin{align*}F(\lambda) \leq F(\bar{\lambda}) &\visible<7->{=(1-\bar{\lambda}_i) V(S)+\bar{\lambda}_i V(S\cup \{i\})}\visible<8->{\leq V(S)+ V(\{i\})}\\
\visible<9->{&\Rightarrow\quad F(\lambda^*)\leq OPT+V(\{i^*\})} \end{align*}}
 \visible<6->{shown through \alert{pipage rounding} [Ageev and Sviridenko 2004]}
\end{itemize}
}
\end{frame}

\begin{frame}{Finding a Relaxation}
\begin{block}{Multilinear Relaxation}
\vspace*{-0.6cm}		
\begin{align*}
			\text{Maximize}\qquad &F(\lambda)=\mathbb{E}_{\lambda}[V(S)] = \textstyle\sum_{S\subset [N]}V(S)\prod_{i\in S}\lambda_i\prod_{i\notin S}(1-\lambda_i)\\
			\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
\visible<2->{ For $\lambda^*$ the optimal solution. Then:}
\medskip
\visible<3->{
\begin{itemize} 
\item<3->$F(\lambda^*)$ is close to $OPT$:
$$OPT \leq F(\lambda^*) \leq OPT +V(\{i^*\})$$ %under a certain condition on $F$ ($\epsilon$-convexity): 
%can be shown through 
%\alert{pipage rounding}  [Ageev and Sviridenko 2004].\\
\item<4->$F(\lambda^*)$ is monotone in $c$.
\end{itemize}}
\medskip
\visible<5->{Good relaxation candidate, if it can be computed in poly-time.}
\visible<6->{\vspace*{-0.3cm}
\begin{center}
\begin{tabular}{lc}
 \textsc{Knapsack} &\Checkmark
\end{tabular}\qquad
\begin{tabular}{lc}
 \textsc{Coverage} &\XSolidBrush\\
 EDP &\XSolidBrush
\end{tabular}
\end{center}
}
\end{frame}


\begin{frame}{Main Technical Contribution: Relaxation for EDP}
\alt<1>{\begin{block}{\textsc{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}
}
{
\begin{block}{Convex Relaxation}
\vspace*{-0.4cm}		
\begin{align*}
			\text{Maximize}\qquad &L(\lambda) = \log \det (I+\sum_{i\in [N]}\lambda_ix_ix_i^T) \\
			\text{subj. to}\qquad &\textstyle\sum_{i\in S}\lambda_ic_i\leq B, \lambda_i\in [0,1]
\end{align*}
\end{block}
}
\pause
\pause
$L(\lambda^*)$ is:
    \begin{itemize}
	\item Monotone in $c$
\pause
        \item Poly-time: $L$ is convex and self-concordant (Boyd\&Vanderberghe)
            \pause
          %  \vspace{0.5cm}
        \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}
%   \pause
%    Proved by showing that $L(\lambda)\leq 2 F(\lambda)$, where $F$ the multilinear relaxation of $V$. %using \emph{pipage rounding} [Ageev and Sviridenko 2004]
\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->{For all $\lambda\in [0,1]^N$, we show that $L(\lambda) \leq 2F(\lambda)$, where $F$ the multi-linear relaxation of $V$.\\
\bigskip}
\uncover<3->{
We show this by establishing first that $\frac{\partial F/\partial \lambda_i}{\partial L/\partial \lambda_i}\geq \frac{1}{2}$, and arguing about the minima of $\frac{F(\lambda)}{L(\lambda)}$ over the simplex.\\
\bigskip
}
\uncover<4>{Finally, we show that $F(\lambda^*)\leq OPT+V(\{i^*\})$ through pipage rounding.}
\end{frame}
\begin{comment}
    \vspace{0.5cm}
    \pause

    \begin{columns}[c]
        \begin{column}{0.53\textwidth}
            \alert{Solution:} Replace $V(OPT_{-i^*})$ with \alert<7>{$L^*$}:
            \pause
            \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 \textsc{Knapsack} (Chen et al., 2011)
                \item \textsc{Coverage} (Singer, 2012)
            \end{itemize}
        \end{column}
    \end{columns}
\end{frame}
\begin{frame}{Sketch of proof (2)}
    \begin{displaymath}
        L^* = \arg\max_{\lambda\in [0,1]^n} \left\{\log\det\left(I_d + \sum_i \lambda_i x_i x_i^T\right)\mid \sum_{i=1}^n\lambda_i c_i\leq B\right\}
    \end{displaymath}
    \vspace{1cm}
    \begin{itemize}
        \item polynomial time?\pause{} convex optimization problem
            \pause
            \vspace{0.5cm}
        \item close to $V(OPT_{-i^*})$?\pause
            \vspace{0.5cm}
            \begin{block}{Technical lemma}
                \begin{displaymath}
                    L^* \leq 2 V(OPT) + V(\{i^*\})
                \end{displaymath}
            \end{block}
    \end{itemize}
\end{frame}
\end{comment}

\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}