diff options
Diffstat (limited to 'intro.tex')
| -rw-r--r-- | intro.tex | 8 |
1 files changed, 4 insertions, 4 deletions
@@ -3,7 +3,7 @@ In the classic setting of experimental design \cite{pukelsheim2006optimal,atkins Each subject $i\in \{1,\ldots,n\}$ is associated with a set of parameters (or features) $x_i\in \reals^d$, known to the experimenter. \E\ wishes to perform an experiment that measures a certain inherent property of the subjects: the outcome for a subject $i$ is denoted $y_i$, which is unknown to \E\ before the experiment is performed. -Typically, \E\ has a hypothesis of the relationship between $x_i$'s and $y_i$'s, such as, say linear, \emph{i.e.}, $y_i \approx \T{\beta} x_i$; conducting the experiments and obtaining the measurements $y_i$ lets \E\ derive an estimate $\beta$. %The goal of experimental design amounts to determining which subjects to experiment upon to produce the best possible such estimate. +Typically, \E\ has a hypothesis of the relationship between $x_i$'s and $y_i$'s, such as, say linear, \emph{i.e.}, $y_i \approx \T{\beta} x_i$; conducting the experiments and obtaining the measurements $y_i$ lets \E\ estimate $\beta$. %The goal of experimental design amounts to determining which subjects to experiment upon to produce the best possible such estimate. The above experimental design scenario has many applications, from medical testing to marketing research and others. There is a rich literature about estimation procedures, as well as for means for quantifying the quality of the produced estimate \cite{pukelsheim2006optimal}. There is also an extensive theory on how to select subjects @@ -21,10 +21,10 @@ to participate in the experiment; or, it might be the inherent value of the data Our contributions are as follows. \begin{itemize} \item -We formulate the problem of experimental design subject to a given budget, in presence of strategic agents who specify their costs. In particular, we focus on linear regression. This is naturally viewed as a budget feasible mechanism design problem. The objective function is sophisticated and is related to the covariance of the $x_i$'s. In particular we formulate the {\em Experimental Design Problem} (\EDP) as follows: the experimenter \E\ wishes to find set $S$ of subjects to maximize +We formulate the problem of experimental design subject to a given budget, in presence of strategic agents who specify their costs. In particular, we focus on linear regression. This is naturally viewed as a budget feasible mechanism design problem. The objective function is sophisticated and is related to the covariance of the $x_i$'s. In particular, we formulate the {\em Experimental Design Problem} (\EDP) as follows: the experimenter \E\ wishes to find set $S$ of subjects to maximize \begin{align}V(S) = \log\det(I_d+\sum_{i\in S}x_i\T{x_i}) \label{obj}\end{align} with a budget constraint $\sum_{i\in S}c_i\leq B$, where $B$ is \E's budget. %, and other {\em strategic constraints} we don't list here. -The objective function, which is the key, is obtained by optimizing the information gain in $\beta$ when it is learned through linear regression methods, and is the so-called $D$-optimality criterion in the literature. +The objective function, which is the key, is obtained by optimizing the information gain in $\beta$ when it is learned through linear regression methods, and is related to the so-called $D$-optimality criterion. \item The above objective is submodular. There are several recent results in budget feasible @@ -36,7 +36,7 @@ For specific combinatorial problems such as \textsc{Knapsack} or \textsc{Coverag deterministic, truthful, polynomial constant-approximation algorithms~\cite{singer-mechanisms,chen, singer-influence}, but they do not work for the linear-algebraic objective function in \EDP. %{\bf S+T: could we verify that the above sentence is correct in its implication?} -We present the first known, polynomial time truthful mechanism for \EDP{}. Our mechanism is a constant factor ($\approx 19$) approximation for \EDP{}. From a technical perspective, we present a convex relaxation to \EDP\; and show that it is within a constant factor approximation of a multi-linear relaxation for \EDP{}. This allows us to adopt the prior work in budget feasible mechanisms by Chen \emph{et al.}~\cite{chen} and Singer~\cite{singer-influence}. In contrast to this, no truthful algorithms are possible for \EDP{} within a factor 2 approximation. {\bf FIX the last sentence} +We present the first known, polynomial time truthful mechanism for \EDP{}. Our mechanism is a constant factor ($\approx 19.68$) approximation for \EDP{}. From a technical perspective, we present a convex relaxation to \EDP\; and show that it is within a constant factor approximation of a multi-linear relaxation for \EDP{}. This allows us to adopt the prior work in budget feasible mechanisms by Chen \emph{et al.}~\cite{chen} and Singer~\cite{singer-influence}. In contrast to this, no truthful algorithms are possible for \EDP{} within a factor 2 approximation. {\bf FIX the last sentence} \item Our approach to mechanisms for experimental design --- by |