diff options
| -rw-r--r-- | definitions.tex | 2 | ||||
| -rw-r--r-- | general.tex | 5 | ||||
| -rw-r--r-- | main.tex | 14 | ||||
| -rw-r--r-- | paper.tex | 4 | ||||
| -rw-r--r-- | problem.tex | 30 | ||||
| -rw-r--r-- | proof_of_lower_bound1.tex | 2 |
6 files changed, 45 insertions, 12 deletions
diff --git a/definitions.tex b/definitions.tex index 03cba22..8d01a6a 100644 --- a/definitions.tex +++ b/definitions.tex @@ -17,7 +17,7 @@ \DeclareMathOperator{\trace}{tr} \DeclareMathOperator*{\argmax}{arg\,max} \DeclareMathOperator*{\argmin}{arg\,min} -\newcommand{\reals}{\ensuremath{\mathbbm{R}}} +\newcommand{\reals}{\ensuremath{\mathbb{R}}} \newcommand{\prob}{\ensuremath{\mathrm{Pr}}} \newcommand{\stratis}[1]{\textcolor{red}{Stratis: #1}} \newcommand{\thibaut}[1]{\textcolor{blue}{Thibaut: #1}} diff --git a/general.tex b/general.tex index e69de29..c90a439 100644 --- a/general.tex +++ b/general.tex @@ -0,0 +1,5 @@ +\subsection{Bayesian Experimental Design} +TODO: Introduce prior with covariance $\sigma^2 R$. Change in entropy/ mutual information is then ... So our scheme can be seen as Baysian prior with $R=I_d$. Extension of our main theorem. + +\subsection{Beyond Linear Models} +TODO: Independent noise model. Captures models such as logistic regression, classification, etc. Arbitrary prior. Show that change in the entropy is submodular (cite Krause, Guestrin). @@ -1,3 +1,17 @@ + +\subsection{D-Optimality Criterion} +\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}$. +\end{lemma} +\begin{proof} +\input{proof_of_lower_bound1} +\end{proof} + +This motivates us to look at $$V(S) = \log\det(I_d+\T{X_S}X_S).$$ Interesting for many reasons. Experiment with basis points $e_1$,\ldots,$e_d$, already given for free. Connections to Baysian optimal experiment design: we explore this more in Section~\ref{...}. Close to $D$-optimality criterion when number of experiments is large. Important properties $V(\emptyset)=0$, $V$ is submodular, allows us to exploit the arsenal in our disposal to deal with budget feasible mechanism design for submodular functions. + +\subsection{Truthful, Constant Approximation Mechanism} + + In this section we present a mechanism for the problem described in section~\ref{sec:auction}. Previous works on maximizing submodular functions \cite{nemhauser, sviridenko-submodular} and desiging auction mechanisms for @@ -4,7 +4,7 @@ \usepackage{algorithm} \usepackage{algpseudocode,bbm,color,verbatim} \input{definitions} -\title{Budgeted Auctions for Experimental Design} +\title{Budgeted Mechanisms for Experimental Design} \begin{document} \maketitle @@ -12,7 +12,7 @@ \section{Intro} \input{intro} -\section{Problem formulation} +\section{Preliminaries} \input{problem} \section{Main result} \input{main} diff --git a/problem.tex b/problem.tex index 81b7656..90203c6 100644 --- a/problem.tex +++ b/problem.tex @@ -13,20 +13,34 @@ $y_S=[y_i]_{i\in S}\in\reals^{|S|}$ the observed measurements, \begin{align*} \hat{\beta} &=\max_{\beta\in\reals^d}\prob(y_S;\beta) =\argmin_{\beta\in\reals^d } \sum_{i\in S}(\T{\beta}x_i-y_i)^2 \\ & = (\T{X_S}X_S)^{-1}X_S^Ty_S\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 $\hat{y}_S$; as $y_S$ is a multidimensional normal r.v., so is $\hat{\beta}$. In particular, $\hat{\beta}$ has mean $\beta$ (\emph{i.e.}, it is unbianced) 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{unbianced estimator}) and covariance $(\T{X_S}X_S)^{-1}$. -The above covariance matrix is used in experimental design to determine how informative a set of experiments $S$ is. Though many different measures of information exist~(see \cite{pukelsheim2006optimal}), the most commonly used is the following: %so-called \emph{D-optimality criterion}: %which yields the following optimization problem -\begin{align*} -\text{Maximize}\quad V_D(S) &= \frac{1}{2}\log\det \T{X_S}X_S \\ -\text{subj. to}\quad |S|&\leq k -\end{align*} -The objective of the above optimization, called the \emph{D-optimality criterion}, is equal (up to a costant) to the negative of the entropy of $\hat{\beta}$. Selecting a set of experiments $S$ that maximizes $V_D(S)$ is equivalent to finding the set of experiments that minimizes the uncertainty on $\beta$, as captured by the entropy of its estimator. +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 capture this through some property the covariance $(\T{X_S}X_S)^{-1}$ of the estimator $\hat{\beta}$. Due to its relationship to entropy, a most commonly used is the \emph{$D$-optimality criterion}: %which yields the following optimization problem +\begin{align} + V_D(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_D(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} +%V(S) & = \frac{1}{2} \log\det \left(I + \T{X_S}X_S\right) +%\end{align} +%There are several reasons + + +\subsection{Budget Feasible Mechanism Design} +In this paper, we approach the problem of optimal experimental design from the perspective of \emph{a budget feasible reverse auction} \cite{singer-mechanisms}. In particular, we assume that each experiment $i\in \mathcal{N}$ is associated with a cost $c_i$, that the experimenter needs to pay in order to conduct the experiment. The experimenter has a budget $B\in\reals_+$. In the \emph{full information case}, the costs are common knowledge; optimal design in this context amounts to selecting a set $S$ maximizing the value $V(S)$ subject to the constraint $\sum_{i\in S} c_i\leq B$. +As in \cite{singer-mechanisms,chen}, we focus in a \emph{strategic scenario}: experiment $i$ corresponds to a \emph{strategic agent}, whose cost $c_i$ is private. For example, each $i$ may correspond to a human participant; the feature vector $x_i$ may correspond to a normalized vector of her age, weight, gender, income, \emph{etc.}, and the measurement $y_i$ may capture some biometric information (\emph{e.g.}, her red cell blood count, a genetic marker, etc.). The cost $c_i$ is the amount the participant deems sufficient to incentivize her participation in the study. -\subsection{Budgeted Mechanism Design} +A mechanism $\mathcal{M} = (f,p)$ comprises (a) an \emph{allocation function} $f:\reals_+^n \to 2^\mathcal{N}$ and (b) a \emph{payment function} $p:\reals_+^n\to \reals_+^n$. The allocation function determines the set $S\subset \mathcal{N}$ of experiments to be conducted. The payment function returns a vector of payments $[p_i]_{i\in \mathcal{N}}$. As in \cite{singer-mechanisms, chen}, we study mechanisms that are normalized ($i\notin S$ implies $p_i=0$), individually rational ($p_i\geq c_i$) and have no positive transfers $p_i\geq 0$. +TODO: truthful, computationally efficient, budget feasible, approximation to V(S) +TODO: Myerson's Theorem \begin{comment} \subsection{Experimental Design} diff --git a/proof_of_lower_bound1.tex b/proof_of_lower_bound1.tex index ac957a0..7688edc 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, 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>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 |