diff options
| author | Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)> | 2013-02-11 19:29:32 -0800 |
|---|---|---|
| committer | Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)> | 2013-02-11 19:29:32 -0800 |
| commit | fca9d9fca8141e104b792ce0b27346d83af71b82 (patch) | |
| tree | 8d7969ccd5ce8f58d1ea6b10f21a569c00176853 /abstract.tex | |
| parent | fcb7ef2df7ddd557ae689f79f32498dd2c705c01 (diff) | |
| download | recommendation-fca9d9fca8141e104b792ce0b27346d83af71b82.tar.gz | |
small changes
Diffstat (limited to 'abstract.tex')
| -rw-r--r-- | abstract.tex | 6 |
1 files changed, 3 insertions, 3 deletions
diff --git a/abstract.tex b/abstract.tex index a92ad45..9e00a95 100644 --- a/abstract.tex +++ b/abstract.tex @@ -10,15 +10,15 @@ hypothetical relationship between $x_i$'s and $y_i$'s, \emph{e.g.}, $y_i \appr $\beta$ from experiments. %conducting the experiments and obtaining the measurements $y_i$ allows %\E\ can estimate $\beta$. -As a proxy for various practical constraints, \E{} may select subjects to select for the experiments. +As a proxy for various practical constraints, \E{} may select only a subset of subjects on which to conduct the experiment. %\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 budgeted mechanisms for experimental design. In this setting, \E{} has a budget $B$. Each subject $i$ declares associated cost $c_i >0$ to be part of the experiment, and must be paid at least their cost. Further, the subjects -are \emph{strategic} and may lie about their costs . In particular, we formulate the {\em Strategic Experimental Design Problem} (\SEDP) as finding 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. +are \emph{strategic} and may lie about their costs. In particular, we formulate the {\em Experimental Design Problem} (\SEDP) as finding 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. We present a deterministic, polynomial time, truthful, budget feasible mechanism for \SEDP{}. -By applying previous work on budget feasible mechanisms with submodular objective, one could have derived either an exponential time deterministic mechanism or a randomized polynomial time mechanism. Our mechanism yields a constant factor ($\approx 12.68$) approximation, and we show that no truthful, budget-feasible algorithms are possible within a factor $2$ approximation. We also show how to apply our approach to a wide class of learning problems. +By applying previous work on budget feasible mechanisms with submodular objective, one could have derived either an exponential time deterministic mechanism or a randomized polynomial time mechanism. Our mechanism yields a constant factor ($\approx 12.68$) approximation, and we show that no truthful, budget-feasible algorithms are possible within a factor $2$ approximation. We also show how to genralize our approach to a wide class of learning problems. |