Merge branch 'master' of ssh://74.95.195.229:1444/git/data_value

1 files changed, 28 insertions, 0 deletions

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.