From b0d1e82017eb270398a5747ff2b46969e720b52a Mon Sep 17 00:00:00 2001 From: Stratis Ioannidis Date: Mon, 5 Nov 2012 13:13:54 -0800 Subject: intro abstract muthu --- abstract.tex | 21 +++++++++++++++++---- 1 file changed, 17 insertions(+), 4 deletions(-) (limited to 'abstract.tex') diff --git a/abstract.tex b/abstract.tex index 2da5561..a3766da 100644 --- a/abstract.tex +++ b/abstract.tex @@ -1,8 +1,21 @@ -We initiate the study of mechanisms for \emph{experimental design}. In this setting, -an experimenter with a budget $B$ 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$ as well as a cost $c_i>0$. -Conducting an experiment with subject $i$ reveals an unknown value $y_i\in \reals$ to the experimenter. Assuming a linear relationship between $x_i$'s and $y_i$'s, \emph{i.e.}, $y_i \approx \T{\beta} x_i$, conducting the experiments and obtaining the measurements $y_i$ allows the experimenter to estimate $\beta$. The experimenter's goal is to select which experiments to conduct, subject to her budget constraint, to obtain the best estimate possible. +%We initiate the study of mechanisms for \emph{experimental design}. -We study this problem when subjects are \emph{strategic} and may lie about their costs. In particular, we formulate the {\em Experimental Design Problem} (\EDP) as finding a set $S$ of subjects that maximize $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 $\beta$ when it is learned through linear regression methods, and is related to the so-called $D$-optimality criterion. We present the first known deterministic, polynomial time truthful mechanism for \EDP{}, yielding a constant factor ($\approx 19.68$) approximation, and show that no truthful algorithms are possible within a factor 2 approximation. Moreover, we show that a wider class of learning problems admits a polynomial time universally truthful (\emph{i.e.}, randomized) mechanism, also within a constant factor approximation. +In the classical {\em experimental design} setting, +an experimenter \E\ with a budget $B$ 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$ as well as a cost $c_i>0$. +Conducting an experiment with subject $i$ reveals an unknown value $y_i\in \reals$ to \E. \E\ typically assume 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. +%conducting the experiments and obtaining the measurements $y_i$ allows +%\E\ can estimate $\beta$. +\E\ 's goal is to select which experiments to conduct, subject to her budget constraint. +%, to obtain the best estimate possible for $\beta$. + +We initiate the study of mechanisms for experimental design. In this setting, +subjects are \emph{strategic} and may lie about their costs. In particular, we formulate the {\em Experimental Design Problem} (\EDP) as finding a set $S$ of subjects that maximize $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 $\beta$ when it is learned through linear regression methods, and is related to the so-called $D$-optimality criterion. We present the first known +deterministic, polynomial time, truthful, budget feasible mechanism for \EDP{}. +Our mechanism yields a constant factor ($\approx 19.68$) approximation, and we show that no truthful, budget-feasible algorithms are possible within a factor 2 approximation. +Our approach here generally applies to a wider class of learning problems and +obtains polynomial time universally truthful (\emph{i.e.}, randomized) budget feasible mechanism, also within a constant factor approximation. -- cgit v1.2.3-70-g09d2