muthu

1 files changed, 18 insertions, 7 deletions

diff --git a/intro.tex b/intro.tex
index f7b047a..d2ba54c 100644
--- a/intro.tex
+++ b/intro.tex
@@ -21,20 +21,33 @@ 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 with a sophisticated objective function that is related to the covariance of the $x_i$'s. In particolar the \textsc{ExperimentalDesignProblem} is as follows: the experimenter \E\ wishes 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 with a sophisticated objective function that 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 maximize 
 \begin{align}V(S) = \log\det(I_d+\sum_{i\in S}x_i\T{x_i}) \label{obj}\end{align}
-subject to the budget constraint $\sum_{i\in S}c_i\leq B$, where $B$ is \E's budget. 
-The objective function 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 ridge regression.
+subject to the 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 regression methods.
 
 \item
-There are several recent results in budget feasible mechanisms \cite{singer-mechanisms,chen,singer-influence,bei2012budget,dobz2011-mechanisms}. The above objective is submodular, and 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). Though no deterministic, truthful constant approximation mechanism  for general submodular functions exists, constant-approximation algorithms for specific problems are known \cite{singer-mechanisms,chen, singer-influence}. In this work, we extend the set of problems for which such approximations are known by presenting the first known polynomial time algorithm for EDP with approximation ratio 18 \ldots, as well as a lower bound of $2$. 
+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.
+For specific combinatorial problems such as knapsack or coverage, there exist 
+constant-approximation algorithms~\cite{singer-mechanisms,chen, singer-influence}, but they don't 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 that will be factor 2 approximation. 
 
 \item
-We extend this study of the experimental design in general, beyond the basic regression problem. Again, the same insight
+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
 \end{itemize}
 
+
 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.
 
 
@@ -61,6 +74,4 @@ We leave several problems open.
 
 }
 
-
-
 \input{related}