Typos. There was an error in the proof of lemma 4. Fixing this error changes our

approximation ratio to 12.98 instead of 19.68...

5 files changed, 35 insertions, 36 deletions

diff --git a/abstract.tex b/abstract.tex
index a3766da..f005dbf 100644
--- a/abstract.tex
+++ b/abstract.tex
@@ -1,13 +1,13 @@
 %We initiate the study of mechanisms for \emph{experimental design}. 
 
 In the classical {\em experimental design} setting,
-an  experimenter  \E\ with  a budget $B$ has access to a population of $n$ potential experiment subjects $i\in 1,\ldots,n$,  each associated with a vector of features $x_i\in\reals^d$ as well as a cost $c_i>0$.
-Conducting an experiment with subject $i$  reveals an unknown value $y_i\in \reals$ to \E. \E\ typically assume some 
+an  experimenter  \E\ with  a budget $B$ has access to a population of $n$ potential experiment subjects $i\in \{1,\ldots,n\}$,  each associated with a vector of features $x_i\in\reals^d$ as well as a cost $c_i>0$.
+Conducting an experiment with subject $i$  reveals an unknown value $y_i\in \reals$ to \E. \E\ typically assumes some 
 hypothetical relationship between  $x_i$'s and $y_i$'s, \emph{e.g.},  $y_i \approx  \T{\beta} x_i$, and estimates 
 $\beta$ from experiments. 
 %conducting the experiments and obtaining the measurements $y_i$ allows 
 %\E\ can estimate  $\beta$. 
-\E\ 's  goal is to select which experiments to conduct, subject to her budget constraint.
+\E 's  goal is to select which experiments to conduct, subject to her budget constraint.
 %, to obtain the best estimate possible for $\beta$.
 
 We initiate the study of mechanisms for experimental design. In this setting, 
diff --git a/intro.tex b/intro.tex
index e113dbc..68eb17f 100644
--- a/intro.tex
+++ b/intro.tex
@@ -24,7 +24,7 @@ Our contributions are as follows.
 \item
 We formulate the problem of experimental design subject to a given budget, in the presence of strategic agents who may lie about their costs. In particular, we focus on linear regression. This is naturally viewed  as a budget feasible mechanism design problem, in which 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}
+\begin{align}V(S) = \log\det\Big(I_d+\sum_{i\in S}x_i\T{x_i}\Big) \label{obj}\end{align}
 subject to 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 obtained by optimizing  the information gain in  $\beta$ when it is learned  through linear regression methods, and is related to the so-called $D$-optimality criterion. 
 \item
@@ -38,7 +38,7 @@ For specific combinatorial problems such as \textsc{Knapsack} or \textsc{Coverag
 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{}. Our mechanism is a constant factor ($\approx 19.68$) approximation for \EDP{}. In contrast to this, we show that no truthful, budget-feasible algorithms are possible for \EDP{}  within a factor 2 approximation. From a technical perspective, we present a convex relaxation of \eqref{obj}, and show that it is within a constant factor from the so-called multi-linear relaxation of  \eqref{obj}. This allows us to adopt the approach followed by prior work in budget feasible mechanisms by Chen \emph{et al.}~\cite{chen} and Singer~\cite{singer-influence}.   %{\bf FIX the last sentence}
+We present the first known, polynomial time truthful mechanism for \EDP{}. Our mechanism is a constant factor ($\approx 12.98$) approximation for \EDP{}. In contrast to this, we show that no truthful, budget-feasible algorithms are possible for \EDP{}  within a factor 2 approximation. From a technical perspective, we present a convex relaxation of \eqref{obj}, and show that it is within a constant factor from the so-called multi-linear relaxation of  \eqref{obj}. This allows us to adopt the approach followed by prior work in budget feasible mechanisms by Chen \emph{et al.}~\cite{chen} and Singer~\cite{singer-influence}.   %{\bf FIX the last sentence}
 
 \item
 Our approach to mechanisms for experimental design --- by 
diff --git a/main.tex b/main.tex
index 8937f04..8fb9666 100644
--- a/main.tex
+++ b/main.tex
@@ -92,7 +92,7 @@ $\id_S$ denotes the indicator vector of $S$. The optimization program
     \leq B\right\}\label{relax}
 \end{align}
 Substituting $OPT'_{-i^*}$ for $OPT_{-i^*}$ like before works for specific problems like \textsc{Knapsack}~\cite{chen} and 
-\textsc{Coverage}~\cite{singer-influence}. For other instances of sub modular function, this overall technology
+\textsc{Coverage}~\cite{singer-influence}. For other instances of submodular function, this overall technology
 has to be applied and extended.
 \end{itemize}
 
@@ -257,9 +257,9 @@ We can now state our main result:
     \log\log \varepsilon^{-1})\right)$ and returns a set $S^*$ such that:
     \begin{align*}
         OPT
-        & \leq \frac{14e-3 + \sqrt{160e^2-48e + 9}}{2(e-1)} V(S^*)+
+        & \leq \frac{10e-3 + \sqrt{64e^2-24e + 9}}{2(e-1)} V(S^*)+
         \varepsilon\\
-        & \simeq 19.68V(S^*) + \varepsilon
+        & \simeq 12.98V(S^*) + \varepsilon
     \end{align*}
 \end{theorem}
 
@@ -296,7 +296,7 @@ contribution; the proof of this lemma can be found in Section~\ref{sec:relaxatio
     $O(\text{poly}(n, d))$ and the mechanism only involves a linear
     number of queries to the function $V$. 
     The function $\log\det$ is concave and self-concordant (see
-    \cite{boyd2004convex}), so for any $\varepsilon$, its maximum can be find
+    \cite{boyd2004convex}), so for any $\varepsilon$, its maximum can be found
     to a precision $\varepsilon$ in $O(\log\log\varepsilon^{-1})$  of iterations of Newton's method. Each iteration  can be
     done in time $O(\text{poly}(n, d))$. Thus, line 3 of
     Algorithm~\ref{mechanism} can be computed in time
@@ -315,7 +315,7 @@ following lemma  which establishes that $OPT'$, the optimal value \eqref{relax}
  is not too far from $OPT$.  
 \begin{lemma}\label{lemma:relaxation}
     %\begin{displaymath}
-     $   OPT' \leq 4 OPT
+     $   OPT' \leq 2 OPT
         + 2\max_{i\in\mathcal{N}}V(i)$
     %\end{displaymath}
 \end{lemma}
@@ -331,7 +331,7 @@ Using Lemma~\ref{lemma:relaxation} we can complete the proof of Theorem~\ref{thm
     $\varepsilon$, then the set $S^*$ allocated by the mechanism is such that:
     \begin{align}
         OPT
-         \leq \frac{14e\!-\!3 + \sqrt{160e^2\!-\!48e\!+\!9}}{2(e\!-\!1)} V(S^*)\!+\! \varepsilon \label{approxbound}
+         \leq \frac{10e\!-\!3 + \sqrt{64e^2\!-\!24e\!+\!9}}{2(e\!-\!1)} V(S^*)\!+\! \varepsilon \label{approxbound}
     \end{align}
 %\end{lemma}
     To see this, let $OPT_{-i^*}'$ be the true maximum value of $L$ subject to $\lambda_{i^*}=0$, $\sum_{i\in \mathcal{N}\setminus{i^*}}c_i\leq B$. Assume that on line 3 of algorithm~\ref{mechanism}, a quantity
@@ -355,39 +355,39 @@ Using Lemma~\ref{lemma:relaxation} we can complete the proof of Theorem~\ref{thm
     from Lemmas \ref{lemma:relaxation} and \ref{lemma:greedy-bound}:
     \begin{align*}
         V(i^*) & \stackrel{}\leq \frac{1}{C}OPT_{-i^*}'+ \frac{\varepsilon}{C}\leq \frac{1}{C}
-        \big(4 OPT + 2 V(i^*)\big) + \frac{\varepsilon}{C}\\
-        & \leq \frac{1}{C}\left(\frac{4e}{e-1}\big(3 V(S_G)
+        \big(2 OPT + 2 V(i^*)\big) + \frac{\varepsilon}{C}\\
+        & \leq \frac{1}{C}\left(\frac{2e}{e-1}\big(3 V(S_G)
         + 2 V(i^*)\big)
         + 2 V(i^*)\right) + \frac{\varepsilon}{C}
     \end{align*}
-    Thus, if $C$ is such that $C(e-1) -10e  +2 > 0$,
+    Thus, if $C$ is such that $C(e-1) -6e  +2 > 0$,
     \begin{align*}
-        V(i^*) \leq \frac{12e}{C(e-1)- 10e + 2} V(S_G) 
-        + \frac{(e-1)\varepsilon}{C(e-1)- 10e + 2}
+        V(i^*) \leq \frac{6e}{C(e-1)- 6e + 2} V(S_G) 
+        + \frac{(e-1)\varepsilon}{C(e-1)- 6e + 2}
     \end{align*}
     Finally, using again Lemma~\ref{lemma:greedy-bound}, we get:
     \begin{multline}\label{eq:bound2}
-        OPT(V, \mathcal{N}, B) \leq \frac{3e}{e-1}\left( 1 + \frac{8e}{C
-        (e-1) -10e  +2}\right) V(S_G)\\
-        +\frac{2e\varepsilon}{C(e-1)- 10e + 2}
+        OPT(V, \mathcal{N}, B) \leq \frac{3e}{e-1}\left( 1 + \frac{4e}{C
+        (e-1) -6e  +2}\right) V(S_G)\\
+        +\frac{2e\varepsilon}{C(e-1)- 6e + 2}
     \end{multline}
     To minimize the coefficients of $V_{i^*}$  and $V(S_G)$  in \eqref{eq:bound1} and \eqref{eq:bound2} respectively,
     we wish to chose for $C=C^*$ such that:
     \begin{displaymath}
         C^* = \argmin_C 
-        \max\left(1+C,\frac{3e}{e-1}\left( 1 + \frac{8e}{C (e-1) -10e  +2}
+        \max\left(1+C,\frac{3e}{e-1}\left( 1 + \frac{4e}{C (e-1) -6e  +2}
         \right)\right)
     \end{displaymath}
-    This equation has two solutions. Only one of those is such that:
-      $  C(e-1) -10e  +2 \geq 0$.
+    This equation has two solutions. Only one of those is such that 
+      $C(e-1) -6e  +2 \geq 0$.
     %which is needed in the above derivation. 
 This solution is:
     \begin{align}
-        C^* =  \frac{12e-1 + \sqrt{160e^2-48e + 9}}{2(e-1)} \label{eq:c}
+        C^* =  \frac{8e-1 + \sqrt{64e^2-24e + 9}}{2(e-1)} \label{eq:c}
     \end{align}
     For this solution,
  %   \begin{displaymath}
-  $      \frac{2e\varepsilon}{C^*(e-1)- 10e + 2}\leq \varepsilon. $
+  $      \frac{2e\varepsilon}{C^*(e-1)- 6e + 2}\leq \varepsilon. $
  %   \end{displaymath}
     Placing the expression of $C^*$ in \eqref{eq:bound1} and \eqref{eq:bound2}
     gives the approximation ratio in \eqref{approxbound}, and concludes the proof of Theorem~\ref{thm:main}.\hspace*{\stretch{1}}\qed
@@ -436,7 +436,7 @@ if we define:
     - e_j)\big)
 \end{displaymath}
 where $e_i$ and $e_j$ are two vectors of the standard basis of
-$\reals^{n}$, then $\tilde{F}$ is convex. Hence its maximum over the interval:
+$\reals^{n}$, then $\tilde{F}_\lambda$ is convex. Hence its maximum over the interval:
 \begin{displaymath}
  I_\lambda = \Big[\max(-\lambda_i,\lambda_j-1), \min(1-\lambda_i, \lambda_j)\Big]
 \end{displaymath}
@@ -444,7 +444,7 @@ is attained at one of the boundaries of $I_\lambda$ for which one of the $i$-th
 or the $j$-th component of $\lambda$ becomes integral.
 
 The lemma below proves that we can similarly trade a fractional component for
-an other until one of them becomes integral \emph{while maintaining the
+another until one of them becomes integral \emph{while maintaining the
 feasibility of the point at which $F$ is evaluated}. Here, by feasibility of
 a point $\lambda$, we mean that it satisfies the budget constraint $\sum_{i=1}^n \lambda_i c_i \leq B$.
 \begin{lemma}[Rounding]\label{lemma:rounding}
@@ -697,14 +697,13 @@ Let us consider a feasible point $\lambda^*\in[0,1]^{n}$ such that $L(\lambda^*)
     \end{equation}
     Let $\lambda_i$ denote the fractional component of $\bar{\lambda}$ and $S$
     denote the set whose indicator vector is $\bar{\lambda} - \lambda_i e_i$.
-    Using the fact that $F$ is linear with respect to the $i$-th
-    component and is a relaxation of the value function, we get:
+    By definition of the multi-linear extension $F$:
     \begin{displaymath}
-        F(\bar{\lambda}) = V(S) +\lambda_i V(S\cup\{i\})
+        F(\bar{\lambda}) = (1-\lambda_i)V(S) +\lambda_i V(S\cup\{i\})
     \end{displaymath}
     Using the submodularity of $V$:
     \begin{displaymath}
-        F(\bar{\lambda}) \leq 2 V(S) + V(i)
+        F(\bar{\lambda}) \leq V(S) + V(i)
     \end{displaymath}
     Note that since $\bar{\lambda}$ is feasible, $S$ is also feasible and
     $V(S)\leq OPT$. Hence:
diff --git a/problem.tex b/problem.tex
index f313be0..e820f85 100644
--- a/problem.tex
+++ b/problem.tex
@@ -4,10 +4,10 @@
 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 \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}
+\begin{align}\label{model}
+     \forall i\in\mathcal{N},\quad y_i = \T{\beta} x_i + \varepsilon_i
 \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$. 
+where $\beta$ is 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 \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, 
@@ -50,8 +50,8 @@ 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:
 \begin{equation}\label{eq:non-strategic}
-    OPT = \max_{S\subseteq\mathcal{N}} \left\{V(S) \mid
-    \sum_{i\in S}c_i\leq B\right\}
+    OPT = \max_{S\subseteq\mathcal{N}} \Big\{V(S) \;\Big| \;
+    \sum_{i\in S}c_i\leq B\Big\}
 \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.}
 
diff --git a/related.tex b/related.tex
index 24ba359..16b2309 100644
--- a/related.tex
+++ b/related.tex
@@ -5,7 +5,7 @@ Budget feasible mechanism design was originally proposed by Singer \cite{singer-
  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.
 
 \sloppy
-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$-approximate 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}. 
+In contrast to the above results, no deterministic, 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$-approximate 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}. 
 
 \fussy
 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}.