result

2 files changed, 9 insertions, 5 deletions

diff --git a/general.tex b/general.tex
index e7a955f..23145ad 100644
--- a/general.tex
+++ b/general.tex
@@ -1,13 +1,15 @@
-\subsection{Bayesian Experimental Design}
-In this section, we extend our results to Bayesian experimental design \cite{chaloner1995bayesian}. In particular, we show that our choice of objective function \eqref{...} has a natural interpration in this context, further motivating its selection, and Theorem~\ref{...} has a natural generalization to this context.
+\subsection{Bayesian Experimental Design}\label{sec:bed}
+In this section, we extend our results to Bayesian experimental design \cite{chaloner1995bayesian}. We show that objective function \eqref{modified} has a natural interpration in this context, further motivating its selection as our objective.  Moreover, we extend Theorem~\ref{thm:main} to a more general Bayesian setting.
 
-In the Bayesian setting, it is assumed that the experimenter has a prior distribution on $\beta$: in particular, $\beta$ is assumed to be sampled from a multivariate normal distribution with zero mean  and covariance $\sigma^2R\in \reals^{d^2}$ (where $\sigma^2$ is the noise variance). 
+In the Bayesian setting, it is assumed that the experimenter has a prior distribution on $\beta$: in particular, $\beta$ has a multivariate normal prior with zero mean  and covariance $\sigma^2R\in \reals^{d^2}$ (where $\sigma^2$ is the noise variance). 
 The experimenter estimates $\beta$ through \emph{maximum a posteriori estimation}: \emph{i.e.}, finding the parameter which maximizes the posterior distribution of $\beta$ given the observations $y_S$. Under the linearity assumption \eqref{model} and the gaussian prior on $\beta$, maximum a posteriori estimation leads to the following maximization \cite{hastie}: FIX!
 \begin{displaymath}
     \hat{\beta} = \argmin_{\beta\in\reals^d} \sum_i (y_i - \T{\beta}x_i)^2
     + \sum_i \norm{R\beta}_2^2
 \end{displaymath}
 This optimization, commonly known as \emph{ridge regression}, includes an additional penalty term compared to the least squares estimation \eqref{leastsquares}.
+
+
 Let $\entropy(\beta)$ be the entropy of $\beta$ under this distribution, and $\entropy(\beta\mid y_S)$ the  entropy of $\beta$ conditioned on the experiment outcomes $Y_S$, for some $S\subseteq \mathcal{N}$. In this setting, a natural objective to select a set of experiments $S$ that maximizes her \emph{information gain}:
 $$ I(\beta;y_S) = \entropy(\beta)-\entropy(\beta\mid y_S). $$
 
diff --git a/main.tex b/main.tex
index 20f500a..061d5b6 100644
--- a/main.tex
+++ b/main.tex
@@ -1,6 +1,6 @@
 
 \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.
+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  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>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}$.
@@ -9,7 +9,9 @@ For any $M>1$, there is no truthful, budget feasible, individionally rational me
 \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.
+This negative result motivates us to look at the following modified objective:
+\begin{align}V(S) = \log\det(I_d+\T{X_S}X_S), \label{modified}\end{align} where $I_d\in \reals^{d\times d}$ is the identity matrix.
+One possible interpretation of \eqref{modified} is that, prior to the auction, the experimenter has free access to $d$ experiments whose features form an ortho-normal basis in $\reals^d$. However, \eqref{modified} can also be motivated in the context of \emph{Bayesian experimental design} \cite{chaloner1995bayesian}. In short, the objective \eqref{modified} arises naturally when the experimenter retrieves the model $\beta$ through \emph{ridge regression}, rather than the linear regression \eqref{leastsquares} over the observed data; we explore this connection in Section~\ref{sec:bed}. From a practical standpoint, \eqref{modified} is a good approximation of \eqref{dcrit} when the number of experiments is large. Crucially, \eqref{modified} is submodular and satifies $V(\emptyset) = 0$, allowing us to use the extensive machinery for the optimization of submodular functions, as well as recent results in the context of budget feasible auctions. 
 
 \subsection{Truthful, Constant Approximation Mechanism}