diff options
Diffstat (limited to 'problem.tex')
| -rw-r--r-- | problem.tex | 26 |
1 files changed, 17 insertions, 9 deletions
diff --git a/problem.tex b/problem.tex index 0ba9db9..a8b89f4 100644 --- a/problem.tex +++ b/problem.tex @@ -14,15 +14,23 @@ $y_S=[y_i]_{i\in S}\in\reals^{|S|}$ the observed measurements, & = (\T{X_S}X_S)^{-1}X_S^Ty_S\label{leastsquares}\end{align} %The estimator $\hat{\beta}$ is unbiased, \emph{i.e.}, $\expt{\hat{\beta}} = \beta$ (where the expectation is over the noise variables $\varepsilon_i$). Furthermore, $\hat{\beta}$ is a multidimensional normal random variable with mean $\beta$ and covariance matrix $(X_S\T{X_S})^{-1}$. -Note that the estimator $\hat{\beta}$ is a linear map of $y_S$; as $y_S$ is a multidimensional normal r.v., so is $\hat{\beta}$ (the randomness coming from the noise terms $\varepsilon_i$). In particular, $\hat{\beta}$ has mean $\beta$ (\emph{i.e.}, it is an \emph{unbianced estimator}) and covariance $(\T{X_S}X_S)^{-1}$. +Note that the estimator $\hat{\beta}$ is a linear map of $y_S$; as $y_S$ is +a multidimensional normal r.v., so is $\hat{\beta}$ (the randomness coming from +the noise terms $\varepsilon_i$). In particular, $\hat{\beta}$ has mean $\beta$ +(\emph{i.e.}, it is an \emph{unbiased estimator}) and covariance +$(\T{X_S}X_S)^{-1}$. Let $V:2^\mathcal{N}\to\reals$ be a value function, quantifying how informative a set of experiments $S$ is in estimating $\beta$. The standard optimal experimental design problem amounts to finding a set $S$ that maximizes $V(S)$ subject to the constraint $|S|\leq k$. -A variety of different value functions are used in experimental design\cite{pukelsheim2006optimal}; almost all make use of the the covariance $(\T{X_S}X_S)^{-1}$ of the estimator $\hat{\beta}$. A value functioned preferred because of its relationship to entropy is the \emph{$D$-optimality criterion}: %which yields the following optimization problem +A variety of different value functions are used in experimental design\cite{pukelsheim2006optimal}; almost all make use of the covariance $(\T{X_S}X_S)^{-1}$ of the estimator $\hat{\beta}$. A value functioned preferred because of its relationship to entropy is the \emph{$D$-optimality criterion}: %which yields the following optimization problem \begin{align} V(S) &= \frac{1}{2}\log\det \T{X_S}X_S \label{dcrit} %\\ \end{align} -As $\hat{\beta}$ is a multidimensional normal random variable, the $D$-optimality criterion is equal (up to a costant) to the negative of the entropy of $\hat{\beta}$. Hence, selecting a set of experiments $S$ that maximizes $V(S)$ is equivalent to finding the set of experiments that minimizes the uncertainty on $\beta$, as captured by the entropy of its estimator. +As $\hat{\beta}$ is a multidimensional normal random variable, the +$D$-optimality criterion is equal (up to a constant) to the negative of the +entropy of $\hat{\beta}$. Hence, selecting a set of experiments $S$ that +maximizes $V(S)$ is equivalent to finding the set of experiments that minimizes +the uncertainty on $\beta$, as captured by the entropy of its estimator. %As discussed in the next section, in this paper, we work with a modified measure of information function, namely %\begin{align} @@ -45,7 +53,7 @@ maximizing the value $V(S)$ subject to the constraint $\sum_{i\in S} c_i\leq B$. We write: \begin{equation}\label{eq:non-strategic} OPT(V,\mathcal{N}, B) = \max_{S\subseteq\mathcal{N}} \left\{V(S) \mid - \sum_{i\in S}\leq B\right\} + \sum_{i\in S}c_i\leq B\right\} \end{equation} the best value we can reach under the budget constraint $B$ when selecting experiments from the set $\mathcal{N}$. @@ -116,11 +124,11 @@ $\inf\{c_i: i\in f(c_i, c_{-i})\}$. \end{enumerate} \end{theorem} -This theorem is particularly useful when designing a truthful mechanism: we -can focus on designing a monotone allocation function. Then the mechanism will -be truthful as long as we give each agent her threshold payment. Finally, it -suffices to prove that the sum of threshold payments does not exceed the budget -to ensure budget feasibility. +This theorem is particularly useful when designing a budget feasible truthful +mechanism: we can focus on designing a monotone allocation function. Then, the +mechanism will be truthful as long as we give each agent her threshold payment. +Finally, it suffices to prove that the sum of threshold payments does not +exceed the budget to ensure budget feasibility. \begin{comment} \subsection{Experimental Design} |