From e80124c06ad4b9af98f64e110551aab584c12010 Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Sat, 2 Mar 2013 22:25:34 -0800
Subject: UCB talk

---
 slides/BudgetFeasibleExperimentalDesign.tex | 587 ++++++++++++++++++++++++++++
 1 file changed, 587 insertions(+)
 create mode 100644 slides/BudgetFeasibleExperimentalDesign.tex

(limited to 'slides/BudgetFeasibleExperimentalDesign.tex')

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}
+
+
-- 
cgit v1.2.3-70-g09d2

