path: root/slides/BudgetFeasibleExperimentalDesign.tex

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

\title[EconCS Seminar]{Budget Feasible Mechanisms for Experimental Design}
\author[Horel, Ioannidis, Muthu]{Thibaut Horel$^*$, \alert{Stratis Ioannidis}$^\dagger$, and S. Muthukrishnan$^\ddagger$}
\institute[]{$^*$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{\reals}{\ensuremath{\mathbb{R}}}

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

\begin{frame}
\maketitle
\end{frame}

\section{Introduction}


\begin{frame}{Motivation:A Data Market}
   \begin{center}
        \includegraphics<1>[scale=0.4]{st1a.pdf}
        \includegraphics<2>[scale=0.4]{st1b.pdf}
        \includegraphics<3>[scale=0.4]{st1c.pdf}
        \includegraphics<4>[scale=0.4]{st1d.pdf}
        \includegraphics<5>[scale=0.4]{st1dd.pdf}
        \includegraphics<6>[scale=0.4]{st1e.pdf}
        \includegraphics<7>[scale=0.4]{st1f.pdf}
        \includegraphics<8>[scale=0.4]{st1g.pdf}
   \end{center}

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

\begin{frame}{Challenges}
%    \begin{overprint}
    \begin{itemize}
	\item<1-> Value of data?
            \visible<3-4>{\begin{itemize}
		\item Experimental Design
	    \end{itemize}}
\vspace*{1cm}
        \item<2-> Strategic users?
	     \visible<4>{\begin{itemize}
	     \item Budget Feasible Auctions [Singer 2010]
             \end{itemize}}
    \end{itemize}
%     \end{overprint}
\end{frame}

\begin{frame}{Contributions}
    \pause
    \begin{itemize}
        \item Experimental design when users are strategic
	\pause
	\vspace*{1cm}
        \item Linear Regression 
	    \pause
	    \begin{itemize}
                \item \emph{Deterministic}, truthful, budget feasible, 12.98-appriximate mechanism. 
		\pause
		\item Singer 2010, Chen 2011:\\ \emph{Randomized}, universaly truthful, budget feasible, 7.91-approximate mechanism.
	    \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}{Experimental Design}
   \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]{st7.pdf}
        \includegraphics<7>[scale=0.4]{st8.pdf}
        \includegraphics<8>[scale=0.4]{st9.pdf}
    \end{center}

    \begin{center}
        \begin{overprint}
        \onslide<1>\begin{center}$N$ users (``experiment subjects'') \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, etc.)
            \end{center}
            \onslide<4>
             %\begin{}
                \textbf{Gaussian Linear Model.}  There exists $\beta\in \reals^d$ s.t.
    \begin{displaymath}
        y_i = \beta^T x_i + \varepsilon_i,\quad
        \varepsilon_i\sim\mathcal{N}(0,\sigma^2), \quad i=1,\ldots,N
    \end{displaymath}
%$$y_i = \beta^Tx_i + \varepsilon_i, i=1,\ldots, N$$ 
            %\end{center}
	    \onslide<5-7>
	    \begin{center}
		Experimenter {\tt E} wishes to learn $\beta$ and can perform  at most $k$ experiments. 
	    \end{center}
	    \onslide<8>
	    \begin{center}{\tt E} computes estimate $\hat{\beta}$ of $\beta$ through ridge regression.
	    \end{center}
        \end{overprint}
    \end{center}

\end{frame}

\begin{frame}{Linear (Ridge) Regression}
%There exists $\beta\in \reals^d$ s.t.
%    \begin{displaymath}
%        y_i = \beta^T x_i + \varepsilon_i,\quad
%        \varepsilon_i\sim\mathcal{N}(0,\sigma^2), \quad i=1,\ldots,N
%    \end{displaymath}
\visible<1->{Let $S\subset [N]\equiv \{1,\ldots,N\}$ be the set of experiments performed.\\\medskip}
\visible<2->{Assume that \E\ has a \emph{prior} on $\beta$:
$$\beta \sim \mathcal{N}(0,\sigma^2 R). $$}
\visible<3->{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<3-4>{\alert<4->{{\beta}^TR^{-1}\beta}\big)} \only<5>{\alert{\|\beta\|_2^2}\big)~~~~~} 
%= (R+{X_S}^TX_S)^{-1}X_S^Ty_S 
\end{align*}
}
\visible<4->{\hspace*{3in}\alert{Ridge Regression}\\}
\visible<5>{\hspace*{3in}$R=I$: homotropic prior}
\end{frame}

\begin{frame}{Value Function}
Select $S\subset [N]$, s.t. $|S|\leq k$. 
\\\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}+X_S^TX_S)}
\end{align*}
\visible<3->{where $$X_S=[x_i^T]_{i\in S}\in \reals^{|S|\times d}$$}
}
\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{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<2>\begin{center}
	Each subject $i\in [N]$ has a cost $c_i\in \reals_+$
	\end{center}
            \onslide<3>
             \begin{center}
                \E\ has a budget $B$.
            \end{center}
	    \onslide<4-5>
	    \begin{center}
		\E\ can pay subjects\visible<5>{; $y_i$ is revealed only if $i$ is paid.}
	    \end{center} 
           \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}

\begin{frame}{Objectives}
    Mechanism $\mathcal{M}=(S,p)$  must be: 
    \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}

    Mechanism must be:
    \vspace{0.3cm}
    \pause
    \begin{itemize}
        \item computationally efficient: polynomial time
            \pause
            \vspace{0.2cm}
        \item constant approximation: $V(OPT) \leq \alpha V(S)$  with:
            \begin{displaymath}
                OPT = \arg\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}{Known Results}
    When $V$ is submodular:
    \vspace{1cm}
    \pause
    \begin{itemize}
        \item \alert{randomized}, universally truthful, budget feasible mechanism,
            approximation ratio: $7.91$ [Singer 2010, Chen \emph{et al.}, 2011]
        \vspace{1cm}
        \pause
        \item \alert{deterministic} mechanisms for specific submodular $V$ functions:
            \vspace{0.3cm}
            \begin{itemize}
                \item Knapsack: $2+\sqrt{2}$ [Singer 2010, Chen \emph{et al.}, 2011]
                    \vspace{0.3cm}
                \item Matching: 7.37 [Singer, 2010]
                    \vspace{0.3cm}
                \item 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 Result}


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


\begin{frame}{Our Main Result}
   \begin{theorem}
        There exists 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)}+\varepsilon
        \simeq 12.98 +\varepsilon
        \end{displaymath}
    \end{theorem}
\end{frame}

\begin{frame}{Sketch of proof}
    \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
        \item Return:
            \begin{itemize}
                \item $\{i^*\}$ if $V(\{i^*\}) \geq \only<1-2>{V(OPT_{-i^*})}\only<3>{\alert{V(OPT_{-i^*})}}\only<4->{\alert{L^*}}$
                \item $S_G$ otherwise
            \end{itemize}
        \end{itemize}
    \end{block}

    \vspace{0.5cm}
    \pause

    Valid mechanism, approximation ratio: 8.34

    \vspace{0.5cm}
    \pause

    \alert{Problem:} $OPT_{-i^*}$ is NP-hard to compute

    \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 Knapsack (Chen et al., 2011)
                \item 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}

\section{Generalization}

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

\begin{frame}{Generalization}
    \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}


\begin{frame}{Conclusion}
    \begin{itemize}
        \item Experimental design + Auction theory = powerful framework
        \vspace{1cm}
        \pause
        \item deterministic mechanism for the general case? other learning tasks?
            \vspace{1cm}
            \pause
        \item  approximation ratio $\simeq \alert{13}$. Lower bound: \alert{$2$}
    \end{itemize}
\end{frame}
\end{document}