small stuff

6 files changed, 25 insertions, 29 deletions

diff --git a/general.tex b/general.tex
index 550d6b7..6e56577 100644
--- a/general.tex
+++ b/general.tex
@@ -6,7 +6,7 @@ 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$ 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!
+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}: 
 \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
@@ -73,13 +73,11 @@ In this setup, assume that the experimenter has a prior distribution on the hypo
 V(S) = \entropy(\beta) -\entropy(\beta\mid y_S),\quad S\subseteq\mathcal{N} 
 \end{align}
 This is a monotone set function, and it clearly satisfies $V(\emptyset)=0$. Though, in general, mutual information is not a submodular function, this specific setup leads indeed to a submodular formulation.
-
 \begin{lemma}
 The value function given by the information gain \eqref{general} is submodular.
 \end{lemma}
-
 \begin{proof}
-The theorem is proved in a slightly different context in \cite{krause2005near}; we
+The lemma is proved in a slightly different context in \cite{krause2005near}; we
 repeat the proof here for the sake of completeness. Using the chain rule for
 the conditional entropy we get:
 \begin{equation}\label{eq:chain-rule}
@@ -89,8 +87,7 @@ the conditional entropy we get:
 where the second equality comes from the independence of the $y_i$'s
 conditioned on $\beta$. Recall that the joint entropy of a set of random
 variables is a submodular function. Thus, our value function is written in
-\eqref{eq:chain-rule} as the sum of a submodular function and a modular function:
-it is submodular.
+\eqref{eq:chain-rule} as the sum of a submodular function and a modular function. 
 \end{proof}
 
 This lemma that implies that learning an \emph{arbitrary hypothesis, under an
diff --git a/intro.tex b/intro.tex
index d2ba54c..33ce910 100644
--- a/intro.tex
+++ b/intro.tex
@@ -21,23 +21,24 @@ 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 particular we formulate the  {\em Experimental Design Problem} (\edp\ ) 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, 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.
+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
 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.
+\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?}
+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.
+%{\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. 
+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. 
 
 \item
 Our approach to mechanisms for experimental design is general. We apply it to study
diff --git a/main.tex b/main.tex
index f44d1c8..d3ba277 100644
--- a/main.tex
+++ b/main.tex
@@ -31,7 +31,7 @@ Let $S_G$ be the set computed by the greedy algorithm and define $i^*$:
 \end{displaymath}
 then the following inequality holds:
 \begin{displaymath}
-OPT(V,\mathcal{N},B) \leq \frac{e}{e-1}\big( 3 V(S_G) + 2 V(i^*)\big)
+OPT(V,\mathcal{N},B) \leq \frac{e}{e-1}\big( 3 V(S_G) + 2 V(i^*)\big).
 \end{displaymath}
 \end{lemma}
 
diff --git a/problem.tex b/problem.tex
index e3ee84b..2a40185 100644
--- a/problem.tex
+++ b/problem.tex
@@ -6,7 +6,7 @@ More precisely, putting cost considerations aside, suppose that an experimenter
 \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 zero mean and variance $\sigma^2$. 
+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
 $y_S=[y_i]_{i\in S}\in\reals^{|S|}$ the observed measurements, 
@@ -47,12 +47,12 @@ A \emph{budget feasible reverse auction}
 \cite{singer-mechanisms} comprises a set of items $\mathcal{N}=\{1,\ldots,n\}$ as well as a single buyer. Each item has a cost $c_i\in\reals_+$. Moreover, the buyer has a positive value function  $V:2^{\mathcal{N}}\to \reals_+$, as well as a budget $B\in \reals_+$. In the \emph{full information case}, the costs $c_i$ are common
 knowledge; the objective of the buyer in this context is to select a set $S$
 maximizing the value $V(S)$ subject to the constraint $\sum_{i\in S} c_i\leq
-B$.We write:
+B$. We write:
 \begin{equation}\label{eq:non-strategic}
     OPT(V,\mathcal{N}, B) = \max_{S\subseteq\mathcal{N}} \left\{V(S) \mid
     \sum_{i\in S}c_i\leq B\right\}
 \end{equation}
-for the optimal value achievable in the full-information case. \stratis{Should be $OPT(V,c,B)$\ldots better drop the arguments here and introduce them wherever necessary.}
+for the optimal value achievable in the full-information case. %\stratis{Should be $OPT(V,c,B)$\ldots better drop the arguments here and introduce them wherever necessary.}
 
 In the \emph{strategic case}, each items in $\mathcal{N}$ is held by a different strategic agent, whose cost is a-priori private.
 A \emph{mechanism} $\mathcal{M} = (f,p)$ comprises (a) an \emph{allocation function}
@@ -74,9 +74,9 @@ A mechanism is truthful iff  every $i \in \mathcal{N}$ and every two cost vector
  $p_i(c_i,c_{-i}) - s_i(c_i,c_{-i})\cdot c_i \geq p_i(c_i',c_{-i}) - s(c_i',c_{-i})\cdot c_i$.
     \item \emph{Budget Feasibility.} The sum of the payments should not exceed the
     budget constraint:
-    \begin{displaymath}
-        \sum_{i\in\mathcal{N}} p_i \leq B.
-    \end{displaymath}
+    %\begin{displaymath}
+     $   \sum_{i\in\mathcal{N}} p_i \leq B.$
+    %\end{displaymath}
     \item \emph{Approximation ratio.} The value of the allocated set should not
     be too far from the optimum value of the full information case
     \eqref{eq:non-strategic}. Formally, there must exist some $\alpha\geq 1$
@@ -130,18 +130,16 @@ incentivize her participation in the study. Note that, in this setup, the featur
 
 %\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 individional rationallity.
-
+However, the following lower bound implies that such an optimization goal cannot be attained under the costraints of  truthfulness, budget feasibility, and individual rationallity.
 \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}$.
 \end{lemma}
 \begin{proof}
 \input{proof_of_lower_bound1}
 \end{proof}
-
 This negative result motivates us to study a problem with a modified objective:
 \begin{center}
-\textsc{ExperimentalDesign} (EDP)
+\textsc{ExperimentalDesignProblem} (EDP)
 \begin{subequations}
 \begin{align}
 \text{Maximize}\quad V(S) &= \log\det(I_d+\T{X_S}X_S) \label{modified} \\
@@ -151,9 +149,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}
+%\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}
 
 
 \begin{comment}
diff --git a/proof_of_lower_bound1.tex b/proof_of_lower_bound1.tex
index 8a6a2f1..b665a50 100644
--- a/proof_of_lower_bound1.tex
+++ b/proof_of_lower_bound1.tex
@@ -1 +1 @@
-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$, a contradiction. %so the ratio is at least $(1+\delta)/\delta>M$. %\qed
+Given $M>1$, consider $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$, $x_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$, a contradiction. %so the ratio is at least $(1+\delta)/\delta>M$. %\qed
diff --git a/related.tex b/related.tex
index 6f55208..2788478 100644
--- a/related.tex
+++ b/related.tex
@@ -4,7 +4,7 @@
 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.
 
-In contrast to the above results, no truthful, constant approximation mechanism that runs in polynomial time is presently known for submodular maximization.  However, assuming access to an oracle providing the optimum in the full-information setup, Chen \emph{et al.},~provide a truthful, $8.34$-appoximate mechanism; in cases for which the full information problem is NP-hard, as the one we consider here, this mechanism is not poly-time, unless $P=NP$. Moreover, Chen et al.~prove a $1+\sqrt{2}$ lower bound for truthful mechanisms, improving upon an earlier bound of 2 by Singer \cite{singer-mechanisms}. 
+In contrast to the above results, no truthful, constant approximation mechanism that runs in polynomial time is presently known for submodular maximization.  However, assuming access to an oracle providing the optimum in the full-information setup, Chen \emph{et al.},~provide a truthful, $8.34$-appoximate mechanism; in cases for which the full information problem is NP-hard, as the one we consider here, this mechanism is not poly-time, unless P=NP.  Chen \emph{et al.}~also prove a $1+\sqrt{2}$ lower bound for truthful mechanisms, improving upon an earlier bound of 2 by Singer \cite{singer-mechanisms}. 
 
 Improved bounds, as well as deterministic polynomial mechanisms, are known for specific submodular objectives. For symmetric submodular functions, a truthful mechanism with approximation ratio 2 is known, and this ratio is tight \cite{singer-mechanisms}. Singer also provides a 7.32-approximate truthful mechanism for the budget feasible version of \textsc{Matching}, and a corresponding lower bound of 2 \cite{singer-mechanisms}. Improving an earlier result by Singer,  Chen \emph{et al.}~\cite{chen} , give a truthful, $2+\sqrt{2}$-approximate mechanism for \textsc{Knapsack}, and a lower bound of $1+\sqrt{2}$. Finally, a truthful, 31-approximate  mechanism is also known for the budgeted version of \textsc{Coverage} \cite{singer-mechanisms,singer-influence}.