diff options
| -rw-r--r-- | approximation.tex | 4 | ||||
| -rw-r--r-- | conclusion.tex | 6 | ||||
| -rw-r--r-- | intro.tex | 2 | ||||
| -rw-r--r-- | main.tex | 2 | ||||
| -rw-r--r-- | problem.tex | 14 | ||||
| -rw-r--r-- | related.tex | 10 |
6 files changed, 19 insertions, 19 deletions
diff --git a/approximation.tex b/approximation.tex index 5e5ee11..4978279 100644 --- a/approximation.tex +++ b/approximation.tex @@ -1,7 +1,7 @@ Previous approaches towards designing truthful, budget feasible mechanisms for \textsc{Knapsack}~\cite{chen} and \textsc{Coverage}~\cite{singer-influence} build upon polynomial-time algorithms that compute an approximation of $OPT$, the optimal value in the full information case. Crucially, to be used in designing a truthful mechanism, such algorithms need also to be \emph{monotone}, in the sense that decreasing any cost $c_i$ leads to an increase in the estimation of $OPT$; %In the cases of \textsc{Knapsack} and~\textsc{Coverage}, as well as in the case of \EDP{}, the monotonicity property precludes using traditional approximation algorithms. -In the fist part of this section, we address this issue by designing a convex relaxation of \EDP{}, and showing that its solution can be used to approximate $OPT$. The objective of this relaxation is concave and self-concordant \cite{boyd2004convex} and, as such, there exists an algorithm that solves this relaxed problem with arbitrary accuracy in polynomial time. Unfortunately, the output of this algorithm may not necessarily be monotone. Nevertheless, in the second part of this section, we show that a solver of the relaxed problem can be used to construct a solver that is ``almost'' monotone. In Section~\ref{sec:main}, we show that this algorithm can be used to design a $\delta$-truthful mechanism for \EDP. +In the first part of this section, we address this issue by designing a convex relaxation of \EDP{}, and showing that its solution can be used to approximate $OPT$. The objective of this relaxation is concave and self-concordant \cite{boyd2004convex} and, as such, there exists an algorithm that solves this relaxed problem with arbitrary accuracy in polynomial time. Unfortunately, the output of this algorithm may not necessarily be monotone. Nevertheless, in the second part of this section, we show that a solver of the relaxed problem can be used to construct a solver that is ``almost'' monotone. In Section~\ref{sec:main}, we show that this algorithm can be used to design a $\delta$-truthful mechanism for \EDP. %As noted above, \EDP{} is NP-hard. Designing a mechanism for this problem, as @@ -92,7 +92,7 @@ In particular, for $L_c^*\defeq \max_{\lambda\in \dom_c} L(\lambda)$ the optimal \begin{proposition}\label{prop:relaxation} $OPT\leq L^*_c \leq 2 OPT + 2\max_{i\in\mathcal{N}}V(i)$. \end{proposition} -The proof of this proposition can be found in Appendix~\ref{proofofproprelaxation}. As we discuss in the next section, $L^*_c$ can be computed a polynomial time algorithm at arbitrary accuracy. However, the outcome of this computation may not necessarily be monotone; we address this by converting this poly-time estimator of $L^*_c$ to one that is ``almost'' monotone.%The optimization program \eqref{eq:non-strategic} extends naturally to such +The proof of this proposition can be found in Appendix~\ref{proofofproprelaxation}. As we discuss in the next section, $L^*_c$ can be computed by a poly-time algorithm at arbitrary accuracy. However, the outcome of this computation may not necessarily be monotone; we address this by converting this poly-time estimator of $L^*_c$ to one that is ``almost'' monotone.%The optimization program \eqref{eq:non-strategic} extends naturally to such %a relaxation. We define: %\begin{equation}\tag{$P_c$}\label{eq:primal} % L^*_c \defeq \max_{\lambda\in[0, 1]^{n}} diff --git a/conclusion.tex b/conclusion.tex index 5d32a1e..6a3917e 100644 --- a/conclusion.tex +++ b/conclusion.tex @@ -1,12 +1,12 @@ -We have proposed a convex relaxation for \EDP, and showed that it can be used to design a $\delta$-truthful, constant approximation mechanism that runs in polynomial time. Our objective function, commonly known as the Bayes $D$-optimality criterion, is motivated from linear regression, and in particular captures the information gain when experiments are used to learn a linear model. %in \reals^d. +We have proposed a convex relaxation for \EDP, and showed that it can be used to design a $\delta$-truthful, constant approximation mechanism that runs in polynomial time. Our objective function, commonly known as the Bayes $D$-optimality criterion, is motivated by linear regression, and in particular captures the information gain when experiments are used to learn a linear model. %in \reals^d. A natural question to ask is to what extent the results we present here generalize to other machine learning tasks beyond linear regression. We outline a path in pursuing such generalizations in Appendix~\ref{sec:ext}. In particular, although the information gain is not generally a submodular function, we show that for a wide class of models, in which experiments -outcomes are perturbed by independent noise, the information does indeed -exhibit submodularity. Several important learning tasks fall under this +outcomes are perturbed by independent noise, the information gain indeed +exhibits submodularity. Several important learning tasks fall under this category, including generalized linear regression, logistic regression, \emph{etc.} In light of this, it would be interesting to investigate whether our convex relaxation approach generalizes to other learning tasks in this @@ -8,7 +8,7 @@ Typically, \E\ has a hypothesis on the relationship between $x_i$'s and $y_i$'s. $$y_i = \T{\beta} x_i+\varepsilon_i,$$ for all $i\in \{1,\ldots,n\},$ where $\varepsilon_i$ are zero-mean, i.i.d.~random variables. Conducting the experiments and obtaining the measurements $y_i$ lets \E\ estimate $\beta$, \emph{e.g.}, through linear regression. %, \emph{i.e.}, the model underlying the data, and the experimenter's goal is to obtain such an estimate as accurately as possible. %The goal of experimental design amounts to determining which subjects to experiment upon to produce the best possible such estimate. The above experimental design scenario has many applications. Regression over personal data collected through surveys or experimentation is the cornerstone of marketing research, as well as research in a variety of experimental sciences such as medicine and sociology. Crucially, statistical analysis of user data is also a widely spread practice among Internet companies, which routinely use machine learning techniques over vast records of user data to perform inference and classification tasks integral to their daily operations. -Beyond linear regression, there is a rich literature about estimation procedures, as well as for means of quantifying the quality of the produced estimate~\cite{pukelsheim2006optimal}. There is also an extensive theory on how to select subjects +Beyond linear regression, there is a rich literature about estimation procedures, as well as about means of quantifying the quality of the produced estimate~\cite{pukelsheim2006optimal}. There is also an extensive theory on how to select subjects if \E\ can conduct only a limited number of experiments, so the estimation process returns a $\beta$ that approximates the true parameter of the underlying population \cite{ginebra2007measure,le1996comparison,chaloner1995bayesian,boyd2004convex}. @@ -5,7 +5,7 @@ In this section we use the $\delta$-decreasing, $\epsilon$-accurate algorithm so %In the strategic case, Algorithm~\eqref{eq:max-algorithm} breaks incentive compatibility. Indeed, \citeN{singer-influence} notes that this allocation function is not monotone, which implies by Myerson's theorem (Theorem~\ref{thm:myerson}) that the resulting mechanism is not truthful. -Recall from Section~\ref{sec:fullinfo} that $i^*\defeq \arg\max_{i\in \mathcal{N}} V(\{i\})$ is the element of maximum value, and $S_G$ is a set constructed greedily, by selecting elements of maximum marginal value per cost. The general framework used by \citeN{chen} and by \citeN{singer-influence} for the \textsc{Knapsack} and \textsc{Coverage} value functions contructs an allocation as follows. First, a polynomial-time, monotone approximation of $OPT$ is computed over all elements excluding $i^*$. The outcome of this approximation is compared to $V(\{i^*\})$: if it exceeds $V(\{i^*\})$, then the mechanism constructs an allocation $S_G$ greedily; otherwise, the only item allocated is the singleton $\{i^*\}$. Provided that the approximation used is within a constant from $OPT$, the above allocation can be shown to also yield a constant approximation to $OPT$. Furthermore, this allocation combined with \emph{threshold payments} (see Lemma~\ref{thm:myerson-variant} below), the mechanism can be shown to be truthful using Myerson's Theorem~\cite{myerson}. +Recall from Section~\ref{sec:fullinfo} that $i^*\defeq \arg\max_{i\in \mathcal{N}} V(\{i\})$ is the element of maximum value, and $S_G$ is a set constructed greedily, by selecting elements of maximum marginal value per cost. The general framework used by \citeN{chen} and by \citeN{singer-influence} for the \textsc{Knapsack} and \textsc{Coverage} value functions contructs an allocation as follows. First, a polynomial-time, monotone approximation of $OPT$ is computed over all elements excluding $i^*$. The outcome of this approximation is compared to $V(\{i^*\})$: if it exceeds $V(\{i^*\})$, then the mechanism constructs an allocation $S_G$ greedily; otherwise, the only item allocated is the singleton $\{i^*\}$. Provided that the approximation used is within a constant from $OPT$, the above allocation can be shown to also yield a constant approximation to $OPT$. Furthermore, using Myerson's Theorem~\cite{myerson}, it can be shown that this allocation combined with \emph{threshold payments} (see Lemma~\ref{thm:myerson-variant} below) constitute a truthful mechanism. The approximation algorithms used in \cite{chen,singer-influence} are LP relaxations, and thus their outputs are monotone and can be computed exactly in polynomial time. We show that the convex relaxation \eqref{eq:primal}, which can be solved by an $\epsilon$-accurate, $\delta$-decreasing algorithm, can be used to construct a $\delta$-truthful, constant approximation mechanism, by being incorporated in the same framework. diff --git a/problem.tex b/problem.tex index 1ac1a38..15f0c11 100644 --- a/problem.tex +++ b/problem.tex @@ -91,10 +91,10 @@ The cost $c_i$ can capture, \emph{e.g.}, the amount the subject $i$ deems suffic \begin{subequations} \begin{align} \text{Maximize}\quad V(S) &= \log\det(I_d+\T{X_S}X_S) \label{modified} \\ -\text{subject to}\quad \sum_{i\in S} c_i&\leq B +\text{subject to}\quad \sum_{i\in S} c_i&\leq B\label{lincon} \end{align}\label{edp} \end{subequations} -\emph{W.l.o.g.}, we assume that $c_i\in [0,B]$ for all $i\in \mathcal{N}$, as no $i$ with $c_i>B$ can be in $S$. We denote by +\emph{W.l.o.g.}, we assume that $c_i\in [0,B]$ for all $i\in \mathcal{N}$, as no $i$ with $c_i>B$ can be in an $S$ satisfying \eqref{lincon}. Denote by \begin{equation}\label{eq:non-strategic} OPT = \max_{S\subseteq\mathcal{N}} \Big\{V(S) \;\Big| \; \sum_{i\in S}c_i\leq B\Big\} @@ -106,11 +106,11 @@ $w_i$, to an experiment with $x_i^2=w_i$.% Moreover, \eqref{modified} is submodu The value function \eqref{modified} has the following properties, which are proved in Appendix~\ref{app:properties}. First, it is non-negative, \emph{i.e.}, $V(S)\geq 0$ for all $S\subseteq\mathcal{N}$. Second, it is -also monotone, \emph{i.e.}, $V(S)\leq V(T)$ for all $S\subset T$, with -$V(\emptyset)=0$. Finally, it is a submodular, \emph{i.e.}, -$V(S)+V(T)\geq V(S\cup T)+V(S\cap T)$ for all $S,T\subseteq \mathcal{N}$. +also monotone, \emph{i.e.}, $V(S)\leq V(T)$ for all $S\subseteq T$, with +$V(\emptyset)=0$. Finally, it is submodular, \emph{i.e.}, +$V(S\cup \{i\})-V(S)\geq V(T\cup \{i\})-V(T)$ for all $S\subseteq T\subseteq \mathcal{N}$ and $i\in \mathcal{N}$. %Finally, we define the strategic version of \EDP{} (denoted by \SEDP) by adding the additional constraints of truthfulness, individual rationality, and normal payments, as described in the previous section. -The above three properties imply that a greedy algorithm yields a constant approximation ratio to \EDP. +The above imply that a greedy algorithm yields a constant approximation ratio to \EDP. In particular, consider the greedy algorithm in which, for %In the full-information case, submodular maximization under a budget constraint %\eqref{eq:non-strategic} relies on a greedy heuristic in which elements are @@ -145,7 +145,7 @@ We seek mechanisms that are \emph{normalized} (unallocated experiments receive z We relax the notion of truthfulness to \emph{$\delta$-truthfulness}, requiring that reporting one's true cost is an \emph{almost-dominant} strategy: no subject increases their utility by reporting a cost that differs more than $\delta>0$ from their true cost. Under this definition, a mechanism is truthful if $\delta=0$. In addition, we would like the allocation $S(c)$ to be of maximal value; however, $\delta$-truthfulness, as well as the hardness of \EDP{}, preclude achieving this goal. Hence, we seek mechanisms with that are \emph{$(\alpha,\beta)$-approximate}, \emph{i.e.}, there exist $\alpha\geq 1$ and $\beta>0$ s.t.~$OPT \leq \alpha V(S(c))+\beta$, and are \emph{computationally efficient}, in that $S$ and $p$ can be computed in polynomial time. -We note that the greedy algorithm \eqref{eq:max-algorithm} breaks +We note that the constant approximation algorithm \eqref{eq:max-algorithm} breaks truthfulness. Though this is not true for all submodular functions (see, \emph{e.g.}, \cite{singer-mechanisms}), it is true for the objective of \EDP{}: we show this in Appendix~\ref{sec:non-monotonicity}. This motivates our study of more complex mechanisms. \begin{comment} diff --git a/related.tex b/related.tex index b25b91b..4b7e740 100644 --- a/related.tex +++ b/related.tex @@ -24,8 +24,8 @@ The deterministic mechanisms for \textsc{Knapsack} \cite{chen} and which we also employ in our mechanism for \EDP. We describe this framework in detail in Section~\ref{sec:main}. Both of these mechanisms rely on approximating the optimal solution to the underlying combinatorial problem by a well-known linear program (LP) relaxation~\cite{pipage}, which can be solved exactly in polynomial time. No -such relaxation exists for \EDP, whose logarithmic objective is unlikely to be -approximable through an LP. We develop instead a convex relaxation to \EDP; +such relaxation exists for \EDP, which unlikely to be +approximable through an LP due to its logarithmic objective. We develop instead a convex relaxation to \EDP; though, contrary to the above LP relaxations, this cannot be solved exactly, we establish that it can be incorporated in the framework of \cite{chen,singer-influence} to yield a $\delta$-truthful mechanism for \EDP. @@ -50,13 +50,13 @@ constructed. \citeN{archer-approximate} propose a randomized rounding of the LP which is \emph{truthful-in-expectation}. %and in high probability. \citeN{lavi-truthful} construct randomized truthful-in-expectation mechanisms for several combinatorial auctions, improving the approximation -ratio in \cite{archer-approximate}, by treating the fractional solution of an LP as a probability distribution over integral solutions. +ratio in \cite{archer-approximate}, by treating the fractional solution of an LP as a probability distribution from which they sample integral solutions. Beyond LP relaxations, \citeN{dughmi2011convex} propose truthful-in-expectation mechanisms for combinatorial auctions in which -the bidders' utilities are matroid rank sum functions (applied earlier to the \textsc{CombinatorialPublicProjects} problem \cite{dughmi-truthful}). As in our case, their framework relies -on solving a convex optimization problem which can only be solved approximately. The authors ensure that a solver is applied to a +the bidders' utilities are matroid rank sum functions (applied earlier to the \textsc{CombinatorialPublicProjects} problem \cite{dughmi-truthful}). Their framework relies +on solving a convex optimization problem which can only be solved approximately. As in \cite{lavi-truthful}, they also treat the fractional solution as a distribution over which they sample integral solutions. The authors ensure that a solver is applied to a ``well-conditioned'' problem, which resembles the technical challenge we face in Section~\ref{sec:monotonicity}. However, we seek a deterministic mechanism and $\delta$-truthfulness, not truthfulness-in-expectation. In addition, our objective is not a matroid rank sum function. As such, both the methodology for dealing with problems that are not ``well-conditioned'' as well as the approximation guarantees of the convex relaxation in \cite{dughmi2011convex} do not readily extend to \EDP. |