diff options
| -rw-r--r-- | abstract_wine.tex | 56 |
1 files changed, 56 insertions, 0 deletions
diff --git a/abstract_wine.tex b/abstract_wine.tex new file mode 100644 index 0000000..a3b7460 --- /dev/null +++ b/abstract_wine.tex @@ -0,0 +1,56 @@ +\documentclass{llncs} +\usepackage[numbers]{natbib} +\usepackage[utf8x]{inputenc} +\usepackage{amsmath,amsfonts} +\usepackage{algorithm, algpseudocode} +\usepackage{bbm,color,verbatim} +\input{definitions} +\usepackage[pagebackref=true,breaklinks=true,colorlinks=true]{hyperref} +\title{Budget Feasible Mechanisms\\ for Experimental Design} +\author{ + Thibaut Horel\inst{1} + \and + Stratis Ioannidis\inst{2} + \and + S. Muthukrishnan\inst{3} +} +\institute{École Normale Supérieure, \email{thibaut.horel@normalesup.org} + \and + Technicolor, \email{stratis.ioannidis@technicolor.com} + \and + Rutgers University, \email{muthu@cs.rutgers.edu} +} +\begin{document} +\maketitle +\vspace{2em} + +In the classical {\em experimental design} setting, an experimenter \E\ has +access to a population of $n$ potential experiment subjects $i\in +\{1,\ldots,n\}$, each associated with a vector of features $x_i\in\reals^d$. +Conducting an experiment with subject $i$ reveals an unknown value $y_i\in +\reals$ to \E. \E\ typically assumes some hypothetical relationship between +$x_i$'s and $y_i$'s, \emph{e.g.}, $y_i \approx \T{\beta} x_i$, and estimates +$\beta$ from experiments, \emph{e.g.}, through linear regression. As a proxy +for various practical constraints, \E{} may select only a subset of subjects on +which to conduct the experiment. + +We initiate the study of budgeted mechanisms for experimental design. In this +setting, \E{} has a budget $B$. Each subject $i$ declares an associated cost +$c_i >0$ to be part of the experiment, and must be paid at least her cost. In +particular, the {\em Experimental Design Problem} (\SEDP) is to find a set +$S$ of subjects for the experiment that maximizes $V(S) += \log\det(I_d+\sum_{i\in S}x_i\T{x_i})$ under the constraint $\sum_{i\in +S}c_i\leq B$; our objective function corresponds to the information gain in +parameter $\beta$ that is learned through linear regression methods, and is +related to the so-called $D$-optimality criterion. Further, the subjects are +\emph{strategic} and may lie about their costs. Thus, we need to design +a mechanism for \SEDP{} with suitable properties. We present a deterministic, +polynomial time, budget feasible mechanism scheme, that is approximately +truthful and yields a 12.98 factor approximation to \EDP. +% By applying previous work on budget feasible mechanisms with +% a submodular objective, one could {\em only} have derived either an exponential +% time deterministic mechanism or a randomized polynomial time mechanism. +We also establish that no truthful, budget-feasible mechanism is possible +within a factor $2$ approximation, and show how to generalize our approach to +a wide class of learning problems, beyond linear regression. +\end{document} |