diff options
Diffstat (limited to 'slides/BudgetFeasibleExperimentalDesign.tex')
| -rw-r--r-- | slides/BudgetFeasibleExperimentalDesign.tex | 587 |
1 files changed, 587 insertions, 0 deletions
diff --git a/slides/BudgetFeasibleExperimentalDesign.tex b/slides/BudgetFeasibleExperimentalDesign.tex new file mode 100644 index 0000000..04e2f8e --- /dev/null +++ b/slides/BudgetFeasibleExperimentalDesign.tex @@ -0,0 +1,587 @@ +\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} + + |