In the classical experimental design setting, an experimenter E has access to a population of n potential experiment subjects i ∈ {1, . . . , n}, each associated with a vector of features x i ∈ R d . Conducting an experiment with subject i reveals an unknown value y i ∈ R to E. E typically assumes some hypothetical relationship between x i 's and y i 's, e.g., y i ≈ β T 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 > 0 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 + i∈S x i x T i ) under the constraint i∈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.
In REF a computationally tractable approximation algorithm was proposed for the D-optimality criterion of the experimental design problem.
Budget Feasible Mechanisms for Experimental Design
LATIN 2014: Theoretical Informatics. Lecture Notes in Computer Science Volume 8392, 2014, pp 719-730
Computer Science