diff options
Diffstat (limited to 'slides/11-25-2014/slides.tex')
| -rwxr-xr-x | slides/11-25-2014/slides.tex | 890 |
1 files changed, 890 insertions, 0 deletions
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} |