From d0349ca6b30e11915cd95c00e981e712198fb5da Mon Sep 17 00:00:00 2001 From: Stratis Ioannidis Date: Wed, 31 Oct 2012 11:19:12 -0700 Subject: lower bound --- main.tex | 4 +++- notes.bib | 20 ++++++++++++++++++++ problem.tex | 3 ++- proof_of_lower_bound1.tex | 2 +- 4 files changed, 26 insertions(+), 3 deletions(-) diff --git a/main.tex b/main.tex index e2e7df6..20f500a 100644 --- a/main.tex +++ b/main.tex @@ -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} diff --git a/notes.bib b/notes.bib index 695b37a..f9e4916 100644 --- a/notes.bib +++ b/notes.bib @@ -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)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 -- cgit v1.2.3-70-g09d2