\documentclass{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{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} %\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} \begin{frame} \maketitle \end{frame} \section{Introduction} \begin{frame}{Motivation: A Data Market} \begin{center} \includegraphics<1>[scale=0.4]{st31a.pdf} \includegraphics<2>[scale=0.4]{st31b.pdf} \includegraphics<3>[scale=0.4]{st31c.pdf} \includegraphics<4>[scale=0.4]{st31d.pdf} \includegraphics<5>[scale=0.4]{st31dd.pdf} \includegraphics<6>[scale=0.4]{st31e.pdf} \includegraphics<7>[scale=0.4]{st31f.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}{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 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} \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. \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] (cont'd)} 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>{\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=I$: homotropic prior, $\lambda=1$}} \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.}} $$} \vspace*{-0.7cm} } \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 \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 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}{A Randomized Mechanism for Submodular $V$ [Singer 2010]} \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} } \end{frame} \begin{frame}{A Deterministic Mechanism for Submodular $V$ [Singer 2010]} \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.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 $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.5cm} \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.4cm} \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*} \end{block} } \medskip \visible<2->{Replace $V$ with expectation when $i\in[N]$ is included with probability $\lambda_i$. }\visible<3->{Let $\lambda^*$ be optimal solution. Then:} \bigskip \visible<3->{ \begin{itemize} \item<3->$F(\lambda^*)$ is monotone in $c$. \item<4->$F(\lambda^*)$ is close to $OPT$ under a certain condition on $F$ ($\epsilon$-convexity). Can be shown through \alert{pipage rounding} [Ageev and Sviridenko 2004].\\ \end{itemize}} \bigskip \visible<5->{Good relaxation candidate, if it can be computed in poly-time.} \visible<6->{ \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} 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} 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} 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}