From 50900bfc44961b87379cd2d3464b677d9f5be1ac Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Sat, 21 Sep 2013 18:16:12 -0400 Subject: Converting to LATIN format --- abstract.txt | 28 ++++++++++++++++++++++++++++ 1 file changed, 28 insertions(+) create mode 100644 abstract.txt (limited to 'abstract.txt') diff --git a/abstract.txt b/abstract.txt new file mode 100644 index 0000000..9078926 --- /dev/null +++ b/abstract.txt @@ -0,0 +1,28 @@ +In the classical experimental design setting, an experimenter E has access to +a population of n potential experiment subjects each associated +with a vector of features x_i. Conducting an experiment with subject i +reveals an unknown value y_i E. E typically assumes some hypothetical +relationship between x_i and y_i, e.g., y_i = β*x_i, and estimates β from +experiments, 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 to be part of the experiment, and must be paid at least her cost. In +particular, the Experimental Design Problem (EDP) 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 x_i^T ) +under the constraint \sum_{i\in S} c_i ≤ B; our objective function corresponds to the information +gain in parameter β that is learned through linear regression methods, and +is related to the so-called D-optimality criterion. Further, the subjects are +strategic and may lie about their costs. Thus, we need to design a mechanism +for EDP with suitable properties. + +We present a deterministic, polynomial time, budget feasible mechanism +scheme, that is approximately truthful and yields a constant (= 12.98) factor +approximation to EDP. By applying previous work on budget feasible mechanisms +with a submodular objective, one could 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. -- cgit v1.2.3-70-g09d2