diff options
Diffstat (limited to 'slides/latin/slides.tex')
| -rw-r--r-- | slides/latin/slides.tex | 454 |
1 files changed, 454 insertions, 0 deletions
diff --git a/slides/latin/slides.tex b/slides/latin/slides.tex new file mode 100644 index 0000000..d82c3e8 --- /dev/null +++ b/slides/latin/slides.tex @@ -0,0 +1,454 @@ +\documentclass[10pt]{beamer} +\usepackage[utf8x]{inputenc} +\usepackage{amsmath,verbatim} +\usepackage{algorithm,algpseudocode} +\usepackage{graphicx} +\DeclareMathOperator*{\argmax}{arg\,max} +\DeclareMathOperator*{\argmin}{arg\,min} +\usetheme{Boadilla} +\newcommand{\E}{{\tt E}} + +\title[LATIN 2014]{Budget Feasible Mechanism\\for Experimental +Design} +\author[Thibaut Horel]{\textbf{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 + +\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}{Applications} + \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}{Contributions} +\pause + \begin{itemize} + \item Formulating the problem in the Experimental Design framework + \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 deterministic, poly-time, truthful, budget + feasible, 12.9-approximate mechanism. + \pause + \item Lower bound of 2. + \pause + \item Prior results: + \pause + \begin{itemize} + \item deterministic exponential-time mechanism [Singer, 2010; Chen \etal, 2011] + \pause + \item universally truthful (randomized) mechanism [Chen \etal, 2011; Singer, 2012] + \end{itemize} + \end{itemize} + +\pause +\vspace*{1cm} + + Generalization to more general statistical learning tasks. +\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} + \onslide<12> + \begin{center} + Users are \alert{strategic} and may lie about costs $c_i$\\users cannot manipulate $x_i$ or $y_i$. + \end{center} + + \end{overprint} + \end{center} +\end{frame} + +\begin{frame}{Value of data} + +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*} +\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 (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 +\begin{itemize} +\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}{Experimental Design with Strategic Agents} +\begin{block}{Value function} +\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 +Budgeted auction mechanism design problem. \pause + +\vspace*{0.5cm} + +Payments and allocation rule must be: +\begin{itemize} +\item normalized, truthful and individually rational +\pause +\item computable in polynomial time, give a good approximation ratio +\end{itemize} +\end{frame} + + +\begin{frame}{Our Main Results} + \begin{theorem} + 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} + + \pause + \vspace*{0.5cm} + + \begin{theorem} + There is no 2-approximate, budget feasible, individually rational and truthful mechanism for + EDP. \end{theorem} + + \pause + \vspace*{0.5cm} + + \alert{Bonus:} two technical approximation results. +\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<2>{OPT_{-i^*}}$ + \item $S_G$ otherwise + \end{itemize} + \end{itemize} + \end{block} + \vspace{0.5cm} + \pause + \pause + \begin{columns}[c] + \begin{column}{0.53\textwidth} +Replace $OPT_{-i^*}$ 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}{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 +\end{itemize} +\end{frame} + +\begin{frame}{First technical result: integrality gap} + \begin{align*} + \text{Maximize}\qquad &L(\lambda) = \log \det \big(I+\sum_{i\in [N]}\lambda_ix_ix_i^T\big) \\ + \text{subj. to}\qquad &\textstyle\sum_{i\in [N]}\lambda_ic_i\leq B, \lambda_i\in [0,1] + \end{align*} + + \pause + \vspace{0.5cm} + + \begin{block}{Integrality gap} + For $\lambda^*$ the optimal solution: + \begin{displaymath} + OPT\leq L(\lambda^*) \leq 2 OPT + 2V(\{i^*\}) + \end{displaymath} + \end{block} + + \pause + \vspace{0.5cm} + + \alert{Proof:} + \begin{itemize} + \item relate $L$ to the multilinear extension of $V$ + \item use \alert{pipage rounding} [Ageev and Sviridenko, 2004] + \end{itemize} + +\end{frame} + +\begin{frame}{Second technical result: monotone approximation} + \begin{block}{EDP-relaxed} + \begin{align*} + \text{Maximize}\qquad &L(\lambda) = \log \det \big(I+\sum_{i\in [N]}\lambda_ix_ix_i^T\big) \\ + \text{subj. to}\qquad &\textstyle\sum_{i\in [N]}\lambda_ic_i\leq B, \lambda_i\in [\only<1-2>{0}\only<3->{\alert<3>{\alpha}},1] + \end{align*} + \end{block} + + \vspace*{1cm} + \pause + + Convex optimization only gives $\delta$-approximation $\alert{\Rightarrow}$ breaks monotonicity. + + \vspace*{1cm} + \pause + + Shrink feasible set: + \begin{itemize} + \pause + \item $L$ is ``sufficiently'' monotone + \pause + \item a $\delta$-approximation of its optimum is $\varepsilon(\delta,\alpha)$-monotone in the costs + \pause + \item tune $\delta$, $\alpha$ $\Rightarrow$ $\varepsilon$-truthful mechanism + \end{itemize} + + +\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{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} |