diff options
| -rw-r--r-- | slides/BudgetFeasibleExperimentalDesign.tex | 118 |
1 files changed, 82 insertions, 36 deletions
diff --git a/slides/BudgetFeasibleExperimentalDesign.tex b/slides/BudgetFeasibleExperimentalDesign.tex index 98de9c2..cc8a1a6 100644 --- a/slides/BudgetFeasibleExperimentalDesign.tex +++ b/slides/BudgetFeasibleExperimentalDesign.tex @@ -3,7 +3,7 @@ \usepackage[greek,english]{babel} \usepackage[LGR,T1]{fontenc} \usepackage{amsmath,bbm,verbatim} -\usepackage{algpseudocode,algorithm} +\usepackage{algpseudocode,algorithm,bbding} \usepackage{graphicx} \DeclareMathOperator*{\argmax}{arg\,max} \DeclareMathOperator*{\argmin}{arg\,min} @@ -12,7 +12,7 @@ \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} +\institute[Technicolor]{$^*$INRIA-ENS, $^\dagger$Technicolor, $^\ddagger$Rutgers University} \setbeamercovered{transparent} \setbeamertemplate{navigation symbols}{} %\AtBeginSection[] @@ -84,17 +84,17 @@ \item Linear Regression \pause \begin{itemize} - \item We present a \alert{deterministic, poly-time}, truthful, budget feasible, 12.98-appriximate 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} + \item We present a \alert{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} + \vspace*{1cm} \item Generalization to other machine learning tasks. \end{itemize} \end{frame} @@ -133,7 +133,7 @@ \end{center} \onslide<3> \begin{center} - $y_i\in \reals$: private data (\eg, survey answer, medical test outcome, etc.) + $y_i\in \reals$: private data (\eg, survey answer, medical test outcome, movie rating, etc.) \end{center} \onslide<4> %\begin{} @@ -157,7 +157,7 @@ \end{center} \onslide<8-9> \begin{center} - \E\ pays subjects\visible<9>{; $y_i$ is revealed only if $i$ is paid.} + \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}. @@ -173,7 +173,7 @@ Goal: Determine (a) who to pay and (b) how much,\\ so that $\hat{\beta}$ is as a %\end{enumerate} \end{center} \onslide<12-> - \begin{center}Users are \alert{strategic}: the may lie about costs $c_i$\visible<13>{\\ Users \alert{cannot manipulate $x_i$ or $y_i$}.} %\\(tamper-proof experiments) + \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} @@ -227,9 +227,9 @@ Let $S\subset [N]$ be the set of experiments performed, and \item computationally efficient: polynomial time \pause \vspace{0.2cm} - \item constant approximation: $V(OPT) \leq \alpha V(S)$ with: + \item approximation: $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\} + 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} @@ -422,11 +422,11 @@ Subjects \alert{do not lie} about $y_i$ (tamper-proof experiments).} \item \alert{Deterministic, poly-time}, truthful mechanisms for specific submodular functions $V$ : \vspace{0.3cm} \begin{itemize} - \item Knapsack: $2+\sqrt{2}$ [Singer 2010, Chen \emph{et al.}, 2011] + \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 Coverage: 31 [Singer, 2012] + \item \textsc{Coverage}: 31 [Singer, 2012] \vspace{0.3cm} \end{itemize} \end{itemize} @@ -530,7 +530,7 @@ Subjects \alert{do not lie} about $y_i$ (tamper-proof experiments).} \begin{frame}{Our Main Results} \begin{theorem}<2-> - There exists deterministic, budget feasible, individually rational and truthful mechanism for + There exists a deterministic, budget feasible, individually rational and truthful mechanism for EDP which runs in polynomial time. Its approximation ratio is: \begin{displaymath} @@ -577,7 +577,7 @@ Stop when budget $B$ is reached. \begin{block}{Allocation $S$:} \begin{itemize} \item Let $i^* = \arg\max_i V(\{i\})$ - \item Compute $S_G$ greedily over $[N]\setminus i^*$ + \item Compute $S_G$ greedily over $[N]\setminus \{i^*\}$ \item Return $S$: \begin{itemize} \item Selected at random between $i^*$ and $S_G$ @@ -600,10 +600,10 @@ Stop when budget $B$ is reached. \begin{block}{Allocation $S$} \begin{itemize} \item Find $i^* = \arg\max_i V(\{i\})$ - \item Compute $S_G$ greedily + \item Compute $S_G$ greedily over $[N]\setminus \{i^*\}$ \item Return: \begin{itemize} - \item $\{i^*\}$ if $V(\{i^*\}) \geq \alert<3>{V(OPT_{-i^*})}$ + \item $\{i^*\}$ if $V(\{i^*\}) \geq \alert<3>{OPT_{-i^*}}$ \item $S_G$ otherwise \end{itemize} \end{itemize} @@ -616,9 +616,10 @@ Stop when budget $B$ is reached. \item budget-feasible \item 8.34-approximate [Chen \etal\ 2011]. \end{itemize} - \vspace{0.5cm} - \pause - \alert{Problem:} $OPT_{-i^*}$ is NP-hard to compute +} +\uncover<3-> +{ \vspace{0.5cm} + \alert{Problem:} $OPT_{-i^*}$ is NP-hard to compute\ldots } \end{frame} @@ -643,7 +644,7 @@ Key idea:\\ Replace $OPT$ with a \alert{relaxation $L^*$}:\pause \begin{itemize} \item computable in polynomial time \pause - \item close to $V(OPT_{-i^*})$ + \item close to $OPT_{-i^*}$ \pause \item monotone in costs $c$ \end{itemize} @@ -651,13 +652,55 @@ Key idea:\\ Replace $OPT$ with a \alert{relaxation $L^*$}:\pause \pause \begin{column}{0.45\textwidth} \begin{itemize} - \item Knapsack (Chen \etal, 2011) - \item Coverage (Singer, 2012) + \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} @@ -678,20 +721,23 @@ Key idea:\\ Replace $OPT$ with a \alert{relaxation $L^*$}:\pause } \pause \pause +$L(\lambda^*)$ is: \begin{itemize} - \item Poly-time: $L$ is convex and self-concordant + \item Monotone in $c$ +\pause + \item Poly-time: $L$ is convex and self-concordant (Boyd\&Vanderberghe) \pause - \vspace{0.5cm} - \item Close to $V(OPT)$:\pause - \vspace{0.5cm} + % \vspace{0.5cm} + \item Close to $OPT$:\pause + % \vspace{0.5cm} \begin{block}{Technical Lemma} \begin{displaymath} - L^* \leq 2 V(OPT) + V(\{i^*\}) + L(\lambda^*) \leq 2 OPT + V(\{i^*\}) \end{displaymath} \end{block} \end{itemize} \pause - Proved using \emph{pipage rounding} [Ageev and Sviridenko 2004] + 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{comment} @@ -711,8 +757,8 @@ Key idea:\\ Replace $OPT$ with a \alert{relaxation $L^*$}:\pause \pause \begin{column}{0.45\textwidth} \begin{itemize} - \item Knapsack (Chen et al., 2011) - \item Coverage (Singer, 2012) + \item \textsc{Knapsack} (Chen et al., 2011) + \item \textsc{Coverage} (Singer, 2012) \end{itemize} \end{column} \end{columns} |