muthu

5 files changed, 62 insertions, 49 deletions

diff --git a/intro.tex b/intro.tex
index 54b5c11..c2e2c8c 100644
--- a/intro.tex
+++ b/intro.tex
@@ -21,43 +21,35 @@ to participate in the experiment; or, it might be the inherent value of the data
 Our contributions are as follows.
 \begin{itemize}
 \item
-We formulate the problem of experimental design subject to a given budget, in presence of strategic agents who specify their costs. In particular, we focus on linear regression. This is naturally viewed  as a budget feasible mechanism design problem. We show that  the objective function is sophisticated and related to the covariance of the $x_i$'s. In particular we formulate the  {\em Experimental Design Problem} (\EDP) as follows: the experimenter \E\ wishes to find set $S$ of subjects to maximize 
+We formulate the problem of experimental design subject to a given budget, in presence of strategic agents who specify their costs. In particular, we focus on linear regression. This is naturally viewed  as a budget feasible mechanism design problem. The objective function is sophisticated and is  related to the covariance of the $x_i$'s. In particular we formulate the  {\em Experimental Design Problem} (\EDP) as follows: the experimenter \E\ wishes to find set $S$ of subjects to maximize 
 \begin{align}V(S) = \log\det(I_d+\sum_{i\in S}x_i\T{x_i}) \label{obj}\end{align}
 with a  budget constraint $\sum_{i\in S}c_i\leq B$, where $B$ is \E's budget. %, and other {\em strategic constraints} we don't list here.
- The objective function, which is the key, is motivated from the so-called $D$-objective criterion; in particular, it captures the reduction in the entropy of $\beta$ when the latter is learned  through linear regression methods.
-
+The objective function, which is the key,  is obtained by optimizing  the information gain in  $\beta$ when it is learned  through linear regression methods, and is the so-called $D$-objective criterion in the literature. 
+ 
 \item
 The above objective is submodular. 
 There are several recent results in budget feasible 
 mechanisms~\cite{singer-mechanisms,chen,singer-influence,bei2012budget,dobz2011-mechanisms}, and some apply to  the submodular optimization in 
 \EDP.
-There is a randomized, 7.91-approximate mechanism for maximizing a general submodular function that is universally truthful, \emph{i.e.}, it is sampled from a distribution among truthful mechanisms. 
-There are however no known deterministic truthful mechanisms for general submodular functions.
+There is a randomized, 7.91-approximate polynomial time mechanism for maximizing a general submodular function that is universally truthful, \emph{i.e.}, it is sampled from a distribution among truthful mechanisms. Also, there is a $8.34$-approximate exponential time deterministic mechanism. 
+There are however no known deterministic, truthful, polynomial time mechanisms for general submodular functions.
 For specific combinatorial problems such as \textsc{Knapsack} or \textsc{Coverage}, there exist 
-deterministic, truthful constant-approximation algorithms~\cite{singer-mechanisms,chen, singer-influence}, but they don't work for the linear-algebraic  objective function in \EDP.
+deterministic, truthful, polynomial constant-approximation algorithms~\cite{singer-mechanisms,chen, singer-influence}, but they do not work for the linear-algebraic  objective function in \EDP.
 %{\bf S+T: could we verify that the above sentence is correct in its implication?}
 
-We present the first known, polynomial time truthful mechanism for \EDP{} and show that it is a constant factor ($\approx 19$) approximation. The technical crux is an approximation algorithm we develop for a  suitable multi-linear relaxation derived from \EDP.
-In contrast, no such truthful algorithms are possible within a factor 2 approximation. 
+We present the first known, polynomial time truthful mechanism for \EDP{}. Our mechanism is a constant factor ($\approx 19$) approximation for \EDP{}. From a technical perspective, we present a convex relaxation to \EDP\; and show that it is within a constant factor approximation of a multi-linear relaxation for \EDP{}. This allows us to adopt the prior work in budget feasible mechanisms by Chen \emph{et al.}~\cite{chen} and Singer~\cite{singer-influence}.  In contrast to this, no truthful algorithms are possible for \EDP{}  within a factor 2 approximation. {\bf FIX the last sentence}
 
 \item
-Our approach to mechanisms for experimental design is general. We apply it to study
-experimental design beyond regression, 
-... {\bf FILL IN}.
-. Again, the same insight
-of data entropy, we can study several experiment design problems in their strategic setting as budget feasible mechanism design with a suitable objective function that is submodular. This immediately gives
+Our approach to mechanisms for experimental design --- by 
+ optimizing  the information gain in parameters like $\beta$ which are estimated through the data analysis process --- is general.  We give examples of this approach beyond linear regression to logistic regression, learning binary functions  and others and derive budgeted mechanism design problems with submodular optimization where prior work immediately applies and gives constant factor approximations. We leave it open to get deterministic truthful polynomial time mechanisms for these problems, like we did for \EDP.
 \end{itemize}
 
+In what follows, we described related work in Section~\ref{sec:related}. We describe the basics of experimental design and budget feasible mechanisms in Section~\ref{sec:peel} and define \EDP formally. In Section~\ref{sec:main} we present our mechanism for \EDP and prove our main results. In~\ref{sec:ext} we present applications of out general framework. 
 
-From a technical perspective, we extend the provide a convex relaxation to the above problem and show that it is within constant approximation from its so-called multilinear relaxation. This allows us to implement the approach used by Chen \emph{et al.}~\cite{chen} and Singer~\cite{singer-influence} to show deterministic constant approximation algorithms for \textsc{Knapsack} and \textsc{Coverage}, respectively.
-
-
-We leave several problems open. 
+\junk{
 
 \stratis{maximizing other ``optimality criteria'' (E-optimality, G-optimality, etc.) Improved upper lower bound for $R\neq I$. General entropy gain optimization}
 
-\junk{
-
 \begin{itemize}
     \item already existing field of experiment design: survey-like setup, what
     are the best points to include in your experiment? Measure of the
diff --git a/main.tex b/main.tex
index 4fa6e74..482b1c9 100644
--- a/main.tex
+++ b/main.tex
@@ -1,10 +1,16 @@
-
+\label{sec:main}
 %\subsection{Truthful, Constant Approximation Mechanism}
 
-In this section we present a mechanism for \EDP. Previous works on maximizing
-submodular functions \cite{nemhauser, sviridenko-submodular} and designing
-auction mechanisms for submodular value functions \cite{singer-mechanisms,
-chen, singer-influence} rely on a greedy algorithm. In this algorithm, elements
+In this section we present a mechanism for \EDP.
+
+\paragraph{Prior approach on sub modular optimization, without strategy} 
+ Previous works~\cite{nemhauser, sviridenko-submodular,singer-mechanisms,chen, singer-influence}
+%
+%on maximizing submodular functions \cite{nemhauser, sviridenko-submodular} and designing
+%auction mechanisms for submodular value functions \cite{singer-mechanisms,
+%chen, singer-influence} 
+%
+rely on a greedy algorithm. In this algorithm, elements
 are added to the solution set according to the following greedy selection rule.
 Assume that $S\subseteq \mathcal{N}$ is the solution set constructed thus far; then, the next element $i$ to be
 included in $S$ is the one with the highest \emph{marginal-value-per-cost}:
@@ -14,36 +20,46 @@ included in $S$ is the one with the highest \emph{marginal-value-per-cost}:
 This process terminates when no more items can be added to $S$ using \eqref{greedy} under budget $B$. This is the generalization of the \emph{value-per-cost} ratio used in the greedy approximation
 algorithm for \textsc{Knapsack}. However, in contrast to \textsc{Knapsack}, for general submodular
 functions, the marginal value  of an element in \eqref{greedy} depends on the set to which it the element is added.
-
+%
 Unfortunately, even for the full information case, the greedy algorithm gives an
 unbounded approximation ratio. Let  $i^*
-= \argmax_{i\in\mathcal{N}} V(i)$ be the element of maximum value (as a singleton
-set). It has been noted by Khuller \emph{et al.}~\cite{khuller} that for the maximum
+= \argmax_{i\in\mathcal{N}} V(i)$ be the element of maximum value.
+% (as a singleton set).
+%It has been noted by Khuller \emph{et al.}~\cite{khuller} that 
+ For the maximum
 coverage problem, taking the maximum between the greedy solution and $V(i^*$)
-gives a $\frac{2e}{e-1}$ approximation ratio. In the general case, we have the
+gives a $\frac{2e}{e-1}$ approximation ratio ~\cite{khuller} . In the general case, 
+\junk{we have the
 following result from Singer \cite{singer-influence} which follows from
 Chen \emph{et al.}~\cite{chen}: \stratis{Is it Singer or Chen? Also, we need to introduce $V(i)$ somewhere...}
+}
 
-\begin{lemma}[Singer \cite{singer-influence}]\label{lemma:greedy-bound}
-Let $S_G$ be the set computed by the greedy algorithm and define $i^*$:
-\begin{displaymath}
-    i^* = \argmax_{i\in\mathcal{N}} V(i)
-\end{displaymath}
-then the following inequality holds:
+\begin{lemma}~\cite{singer-influence}\label{lemma:greedy-bound}
+Let $S_G$ be the set computed by the greedy algorithm and let 
+%define $i^*$:
+%\begin{displaymath}
+$i^* = \argmax_{i\in\mathcal{N}} V(i).$
+%\end{displaymath}
+We have:
+% the following inequality holds:
 \begin{displaymath}
 OPT \leq \frac{e}{e-1}\big( 3 V(S_G) + 2 V(i^*)\big).
 \end{displaymath}
 \end{lemma}
 
 Hence, taking the maximum between $V(S_G)$ and $V(i^*)$ yields an approximation
-ratio of $\frac{5e}{e-1}$. However, Singer \cite{singer-influence} notes that
+ratio of $\frac{5e}{e-1}$. However, 
 this approach breaks incentive compatibility and therefore cannot be directly
-applied to the strategic case. Indeed, suppose this allocation mechanism is used, and consider a case where
+applied to the strategic case.~\cite{singer-influence}
+\junk{
+Indeed, suppose this allocation mechanism is used, and consider a case where
 the allocates  the greedy set ($V(S_G) \geq V(i^*)$). If an
 agent $i$ from $S_G$ reduces her cost, it could happen that $V(S_G)$
 becomes smaller than $V(i^*)$. In this case the mechanism's allocation becomes
 $i^*$, and $i$ is excluded from the allocated set. This violates the monotonicity of
 the allocation function and hence also truthfulness, by Myerson's Theorem.
+}
+
 
 To address this, Chen \emph{et al.}~\cite{chen} %and Singer~\cite{singer-influence},
  introduce a third quantity: if $V(i^*)$ is larger than this quantity, the
diff --git a/paper.tex b/paper.tex
index 9b4de16..28f34a8 100644
--- a/paper.tex
+++ b/paper.tex
@@ -14,7 +14,7 @@
 
 \section{Preliminaries}
 \input{problem}
-\section{Main result}
+\section{Mechanism for \EDP{}}
 \input{main}
 \section{Extension to Other Problems}
 \input{general}
diff --git a/problem.tex b/problem.tex
index 98ca4ac..47991e3 100644
--- a/problem.tex
+++ b/problem.tex
@@ -1,14 +1,15 @@
+\label{sec:prel}
 \subsection{Experimental Design}
 
-The theory of experimental design \cite{pukelsheim2006optimal,atkinson2007optimum}  studies how an experimenter should select the parameters of a set of experiments she is about to conduct. In general, the optimality of a particular design depends on the purpose of the experiment, \emph{i.e.}, the quantity the experimenter is trying to learn or the hypothesis she is trying to validate. Due to their ubiquity in statistical analysis, a large literature on the subject focuses on learning \emph{linear models}, whereby the experimenter wishes to  fit  a linear map to the data she has collected.
+The theory of experimental design \cite{pukelsheim2006optimal,atkinson2007optimum}  studies how an experimenter \E\  should select the parameters of a set of experiments she is about to conduct. In general, the optimality of a particular design depends on the purpose of the experiment, \emph{i.e.}, the quantity \E\  is trying to learn or the hypothesis she is trying to validate. Due to their ubiquity in statistical analysis, a large literature on the subject focuses on learning \emph{linear models}, where \E\ wishes to  fit  a linear map to the data she has collected.
 
-More precisely, putting cost considerations aside, suppose that an experimenter wishes to conduct $k$ among $n$ possible experiments. Each experiment $i\in\mathcal{N}\defeq \{1,\ldots,n\}$ is associated with a set of parameters (or features) $x_i\in \reals^d$, normalized so that $\|x_i\|_2\leq 1$. Denote by $S\subseteq \mathcal{N}$, where $|S|=k$, the set of experiments selected; upon its execution, experiment $i\in S$ reveals an output variable (the ``measurement'') $y_i$,  related to the experiment features $x_i$ through a linear function, \emph{i.e.},
+More precisely, putting cost considerations aside, suppose that \E\ wishes to conduct $k$ among $n$ possible experiments. Each experiment $i\in\mathcal{N}\defeq \{1,\ldots,n\}$ is associated with a set of parameters (or features) $x_i\in \reals^d$, normalized so that $\|x_i\|_2\leq 1$. Denote by $S\subseteq \mathcal{N}$, where $|S|=k$, the set of experiments selected; upon its execution, experiment $i\in S$ reveals an output variable (the ``measurement'') $y_i$,  related to the experiment features $x_i$ through a linear function, \emph{i.e.},
 \begin{align}
      y_i = \T{\beta} x_i + \varepsilon_i,\quad\forall i\in\mathcal{N},\label{model}
 \end{align}
 where $\beta$ a vector in $\reals^d$, commonly referred to as the \emph{model}, and $\varepsilon_i$ (the \emph{measurement noise}) are independent, normally distributed random  variables with mean 0 and variance $\sigma^2$. 
 
-The purpose of these experiments is to allow the experimenter to estimate the model $\beta$. In particular, under \eqref{model}, the maximum likelihood estimator of $\beta$ is the \emph{least squares} estimator: for $X_S=[x_i]_{i\in S}\in \reals^{|S|\times d}$ the matrix of experiment features and
+The purpose of these experiments is to allow \E\  to estimate the model $\beta$. In particular, under \eqref{model}, the maximum likelihood estimator of $\beta$ is the \emph{least squares} estimator: for $X_S=[x_i]_{i\in S}\in \reals^{|S|\times d}$ the matrix of experiment features and
 $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 \nonumber\\
 & = (\T{X_S}X_S)^{-1}X_S^Ty_S\label{leastsquares}\end{align} 
@@ -107,14 +108,16 @@ c_{-i})$ implies $i\in f(c_i', c_{-i})$, and (b)
 %\end{enumerate}
 \end{lemma}
 \fussy
-Myerson's Theorem is particularly useful when designing a budget feasible truthful
-mechanism, as it allows us to focus on designing a monotone allocation function. Then, the
+Myerson's Theorem
+% is particularly useful when designing a budget feasible truthful mechanism, as it 
+allows us to focus on designing a monotone allocation function. Then, the
 mechanism will be truthful as long as we give each agent her threshold payment---the caveat being that the latter need to sum to a value below $B$.
 
 \subsection{Budget Feasible Experimental Design}
-In this paper, we approach the problem of optimal experimental design from the
+
+We approach the problem of optimal experimental design from the
 perspective of a budget feasible reverse auction, as defined above.
- In particular, we assume the experimenter has a budget
+ In particular, we assume the experimenter \E\ has a budget
 $B\in\reals_+$ and plays the role of the buyer. 
 Each experiment $i\in
 \mathcal{N}$ corresponds to a strategic agent, whose cost $c_i$ is
@@ -129,10 +132,10 @@ etc.). The cost $c_i$ is the amount the subject deems sufficient to
 incentivize her participation in the study. Note that, in this setup, the feature vectors $x_i$ are public information that the experimenter can consult prior the experiment design. Moreover, though a subject may lie about her true cost $c_i$, she cannot lie about $x_i$ (\emph{i.e.}, all features are verifiable upon collection) or $y_i$ (\emph{i.e.}, she cannot falsify her measurement).
 
 %\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 one would consider  the (equivalent) maximization of $V(S) = \det\T{X_S}X_S$. %, for some strictly 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 individual rationallity.
+Ideally, motivated by the $D$-optimality criterion, we would like to design a mechanism that maximizes or approximates \eqref{dcrit} . Since \eqref{dcrit} may take arbitrarily small negative values, to define a meaningful approximation one would consider  the (equivalent) maximization of $V(S) = \det\T{X_S}X_S$. %, for some strictly increasing, on-to function $f:\reals_+\to\reals_+$. 
+However, the following lower bound implies that such an optimization goal cannot be attained under the constraints of  truthfulness, budget feasibility, and individual rationality.
 \begin{lemma}
-For any $M>1$, there is no $M$-approximate, truthful, budget feasible, individionally rational mechanism for a budget feasible reverse auction with value fuction $V(S) = \det{\T{X_S}X_S}$.
+For any $M>1$, there is no $M$-approximate, truthful, budget feasible, individionally rational mechanism for a budget feasible reverse auction with $V(S) =  \det{\T{X_S}X_S}$.
 \end{lemma}
 \begin{proof}
 \input{proof_of_lower_bound1}
@@ -149,7 +152,9 @@ This negative result motivates us to study a problem with a modified objective:
 \end{center} 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 orthonormal 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}. 
 
-Note that maximizing \eqref{modified} is equivalent to maximizing \eqref{dcrit} in the full-information case. In particular, $\det(\T{X_S}X_S)> \det(\T{X_{S'}}X_{S'})$ iff $\det(I_d+\T{X_S}X_S)>\det(I_d+\T{X_{S'}}X_{S'})$. In addition, \eqref{edp}---and the equivalent problem with objective \eqref{dcrit}---are NP-hard; to see this, note that \textsc{Knapsack} reduces to EDP with dimension $d=1$ by mapping the weight of each item $w_i$ to an experiment with $x_i=w_i$. Nevertheless, \eqref{modified} is submodular, monotone 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 \cite{chen,singer-mechanisms}. 
+Note that maximizing \eqref{modified} is equivalent to maximizing \eqref{dcrit} in the full-information case. In particular, $\det(\T{X_S}X_S)> \det(\T{X_{S'}}X_{S'})$ iff $\det(I_d+\T{X_S}X_S)>\det(I_d+\T{X_{S'}}X_{S'})$. In addition, \eqref{edp}---and the equivalent problem with objective \eqref{dcrit}---are NP-hard; to see this, note that \textsc{Knapsack} reduces to EDP with dimension $d=1$ by mapping the weight of each item $w_i$ to an experiment with $x_i=w_i$. Nevertheless, \eqref{modified} is submodular, monotone 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 \cite{chen,singer-mechanisms}. 
 
 %\stratis{A potential problem is that all of the above properties hold also for, \emph{e.g.}, $V(S)=\log(1+\det(\T{X_S}X_S))$\ldots}
 
diff --git a/related.tex b/related.tex
index f61abc4..ec22041 100644
--- a/related.tex
+++ b/related.tex
@@ -1,5 +1,5 @@
 \section{Related work}
-
+\label{sec:related}
 
 Budget feasible mechanism design was originally proposed by Singer \cite{singer-mechanisms}. Singer considers the problem of maximizing an arbitrary submodular function subject to a budget constraint in the \emph{value query} model, \emph{i.e.} assuming an  oracle providing the  value of the submodular objective on any given set. 
  Singer shows that there exists a randomized, 112-approximation mechanism for submodular maximization that is \emph{universally truthful} (\emph{i.e.}, it is a randomized mechanism sampled from a distribution over truthful mechanisms). Chen \emph{et al.}~\cite{chen}  improve this result by providing a 7.91-approximate mechanism, and show a corresponding lower bound of $2$ among universally truthful mechanisms for submodular maximization.