diff options
| -rw-r--r-- | main.tex | 4 | ||||
| -rw-r--r-- | notes.bib | 20 | ||||
| -rw-r--r-- | problem.tex | 3 | ||||
| -rw-r--r-- | proof_of_lower_bound1.tex | 2 |
4 files changed, 26 insertions, 3 deletions
@@ -1,7 +1,9 @@ \subsection{D-Optimality Criterion} +Ideally, motivated by the $D$-optimality criterion, we would like to design a mechanism that maximizes \eqref{dcrit} within a good approximation ratio. As \eqref{dcrit} may take arbitrarily small negative values, to define a meaningful approximation we consider with the (equivalent) maximization of $V(S) = f(\det\T{X_S}X_S )$, for some increasing, on-to function $f:\reals_+\to\reals_+$. However, the following lower bound implies that such an optimization goal cannot be attained under the costraints of truthfulness, budget feasibility, and individional rationallity. + \begin{lemma} -For any $M>0$, there is no truthful, budget feasible, individionally rational mechanism for optimal mechanism design with value fuction $V(S) = \det{\T{X_S}X_S}$. +For any $M>1$, there is no truthful, budget feasible, individionally rational mechanism for optimal mechanism design with value fuction $V(S) = \det{\T{X_S}X_S}$. \end{lemma} \begin{proof} \input{proof_of_lower_bound1} @@ -1,3 +1,23 @@ +@book{boyd2004convex, + title={Convex optimization}, + author={Boyd, S. and Vandenberghe, L.}, + year={2004}, + publisher={Cambridge University Press} +} + + +@article{vandenberghe1998determinant, + title={Determinant maximization with linear matrix inequality constraints}, + author={Vandenberghe, L. and Boyd, S. and Wu, S.P.}, + journal={SIAM journal on matrix analysis and applications}, + volume={19}, + number={2}, + pages={499--533}, + year={1998}, + publisher={SIAM} +} + + @book{pukelsheim2006optimal, title={Optimal design of experiments}, author={Pukelsheim, F.}, diff --git a/problem.tex b/problem.tex index 5fd8906..423e6fa 100644 --- a/problem.tex +++ b/problem.tex @@ -17,12 +17,13 @@ Note that the estimator $\hat{\beta}$ is a linear map of $y_S$; as $y_S$ is a mu 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$. -There is a variety of different value functions used in experimental design~\cite{pukelsheim2006optimal}; almost all are related to the covariance $(\T{X_S}X_S)^{-1}$ of the estimator $\hat{\beta}$. Due to its relationship to entropy, the \emph{$D$-optimality criterion} is commonly used: %which yields the following optimization problem +A variety of different value functions are used in experimental design~\cite{pukelsheim2006optimal}; almost all are related to the covariance $(\T{X_S}X_S)^{-1}$ of the estimator $\hat{\beta}$. A commonly used choice is the so-called \emph{$D$-optimality criterion} \cite{pukelsheim2006optimal,chaloner1995bayesian}: %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, maximizing \eqref{dcrit} amounts to finding the set of experiments that minimizes the uncertainty on $\beta$, as captured by the entropy of its estimator. +Value function \eqref{dcrit} has several appealing properties. To begin with, it is a submodular set function (see Lemma~\ref{...} and Thm.~\ref{...}). In addition, the maximization of convex relaxations of this function is a well-studied problem \cite{boyd}. Note that \eqref{dcrit} is undefined when $\mathrm{rank}(\T{X_S}X_S)<d$; in this case, we take $V(S)=-\infty$ (so that $V$ takes values in the extended reals). %As discussed in the next section, in this paper, we work with a modified measure of information function, namely %\begin{align} %V(S) & = \frac{1}{2} \log\det \left(I + \T{X_S}X_S\right) diff --git a/proof_of_lower_bound1.tex b/proof_of_lower_bound1.tex index 7688edc..abef6f7 100644 --- a/proof_of_lower_bound1.tex +++ b/proof_of_lower_bound1.tex @@ -1 +1 @@ -Given an $M>0$, consider a scenario with $n=4$ experiments of dimension $d=2$. For $e_1,e_2$ the standard basis vectors in $\reals^2$, let $x_1 = e_1$, $x_2 = e_1$, and $x_3=\delta e_1$, $x_4=\delta e_2$, where $0<\delta<1/(M-1) $. Moreover, assume that $c_1=c_2=0.5+\epsilon$, while $c_3=c_4=\epsilon$, for some small $\epsilon>0$. Suppose, for the sake of contradiction, that there exists a mechanism with approximation ratio less than $M$. Then, it must include in the solution $S$ at least one of $x_1$ or $x_2$: if not, then $V(S)\leq \det \left(x_3\T{x_3}+x_4\T{x_4}\right)=\delta^2$, while $OPT = (1+\delta)\delta$, so their ratio is greater than $M$, a contradiction. W.l.o.g., suppose thus that the solution contains $x_1$. By the monotonicity property, if user $1$ reduces her cost to $B/2-3\epsilon$, she will still be in the solution. By threshold payment, she must receive in this case a payment that is at least $B/2+\epsilon$ (as increasing her cost to this value still keeps her in the solution). By individual rationality and budget feasibility, user $x_2$ cannot be included in the solution, so $V(S)$ is at most $(1+\delta)\delta$. However, the optimal solution includes all experiments, and yields $OPT=(1+\delta)^2$, so the ratio is at least $(1+\delta)/\delta>M$. \qed +Given an $M>1$, consider a scenario with $n=4$ experiments of dimension $d=2$. For $e_1,e_2$ the standard basis vectors in $\reals^2$, let $x_1 = e_1$, $x_2 = e_1$, and $x_3=\delta e_1$, $x_4=\delta e_2$, where $0<\delta<1/(M-1) $. Moreover, assume that $c_1=c_2=0.5+\epsilon$, while $c_3=c_4=\epsilon$, for some small $\epsilon>0$. Suppose, for the sake of contradiction, that there exists a mechanism with approximation ratio $M$. Then, it must include in the solution $S$ at least one of $x_1$ or $x_2$: if not, then $V(S)\leq \delta^2$, while $OPT = (1+\delta)\delta$, a contradiction. Suppose thus that the solution contains $x_1$. By the monotonicity property, if the cost of experiment $x_1$ reduces to $B/2-3\epsilon$, 1 will still be in the solution. By threshold payments, experiment $x_1$ receives in this case a payment that is at least $B/2+\epsilon$. By individual rationality and budget feasibility, $x_2$ cannot be included in the solution, so $V(S)$ is at most $(1+\delta)\delta$. However, the optimal solution includes all experiments, and yields $OPT=(1+\delta)^2$, so the ratio is at least $(1+\delta)/\delta>M$. %\qed |