From a42eaba2bf8403982fe4861ea4eaf36245a3f54c Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Sun, 10 Feb 2013 17:55:39 -0800 Subject: Finishing my pass over section 4 --- main.tex | 191 +++++++++++++++++++++++++-------------------------------------- 1 file changed, 75 insertions(+), 116 deletions(-) (limited to 'main.tex') diff --git a/main.tex b/main.tex index 64d4604..903d1ed 100644 --- a/main.tex +++ b/main.tex @@ -99,10 +99,10 @@ multilinear extension through the \emph{pipage rounding} framework of \citeN{pip Following Chen \citeN{chen} and \citeN{singer-influence}, we in turn introduce a relaxation $L$ specifically tailored to the value function of \EDP: -\begin{displaymath} +\begin{equation}\label{eq:our-relaxation} \forall\,\lambda\in[0,1]^n,\quad L(\lambda) \defeq \log\det\left(I_d + \sum_{i\in\mathcal{N}} \lambda_i x_i\T{x_i}\right), -\end{displaymath} +\end{equation} and then use $L^* = OPT'_{-i^*}$ with $R=L$ in our mechanism. The function $L$ is well-known to be concave and even self-concordant (see \emph{e.g.}, \cite{boyd2004convex}). In this case, the analysis of Newton's method for @@ -183,57 +183,13 @@ There is no $2$-approximate, truthful, budget feasible, individually rational me Suppose, for contradiction, that such a mechanism exists. Consider two experiments with dimension $d=2$, such that $x_1 = e_1=[1 ,0]$, $x_2=e_2=[0,1]$ and $c_1=c_2=B/2+\epsilon$. Then, one of the two experiments, say, $x_1$, must be in the set selected by the mechanism, otherwise the ratio is unbounded, a contradiction. If $x_1$ lowers its value to $B/2-\epsilon$, by monotonicity it remains in the solution; by threshold payment, it is paid at least $B/2+\epsilon$. So $x_2$ is not included in the solution by budget feasibility and individual rationality: hence, the selected set attains a value $\log2$, while the optimal value is $2\log 2$. \end{proof} -\begin{comment} -$P_\mathcal{N}^\lambda(S)$ is the probability of choosing the set $S$ if -we select each element $i$ in $\mathcal{N}$ independently with probability -$\lambda_i$: %or to reject it with probability $1-\lambda_i$: -\begin{displaymath} - P_\mathcal{N}^\lambda(S) = \prod_{i\in S} \lambda_i - \prod_{i\in\mathcal{N}\setminus S}( 1 - \lambda_i) -\end{displaymath} -Consider the general \emph{multi-linear} -extension: -\begin{equation}\label{eq:multilinear} - F(\lambda) - = \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\left[V(S)\right] - = \sum_{S\subseteq\mathcal{N}} P_\mathcal{N}^\lambda(S) V(S) -\end{equation} -\junk{ - -$P_\mathcal{N}^\lambda(S)$ is the probability of choosing the set $S$ if -we select each element $i$ in $\mathcal{N}$ independently with probability -$\lambda_i$: %or to reject it with probability $1-\lambda_i$: -\begin{displaymath} - P_\mathcal{N}^\lambda(S) = \prod_{i\in S} \lambda_i - \prod_{i\in\mathcal{N}\setminus S}( 1 - \lambda_i) -\end{displaymath} - -For \EDP\ the multi-linear extension -%of \eqref{modified} -can be written: -\begin{displaymath} - F(\lambda) = \mathbb{E}_{S\sim - P_\mathcal{N}^\lambda}\Big[\log\det \big(I_d + \sum_{i\in S} x_i\T{x_i}\big) \Big]. -\end{displaymath} -%As in the case of \textsc{Coverage}, -\eqref{relax} is not a convex optimization problem, and is not easy to solve directly. %As in ~\cite{singer-influence}, -We consider an additional relaxation $L$ that -follows naturally by swapping the expectation and the $\log\det$ -in the above formula: -\begin{align}\label{eq:concave} - L(\lambda) & \defeq \log\det\Big(\mathbb{E}_{S\sim - P_\mathcal{N}^\lambda}\big[I_d + \sum_{i\in S} x_i\T{x_i}\big]\Big)\notag \\ - &= \log\det\left(I_d + \sum_{i\in\mathcal{N}} - \lambda_i x_i\T{x_i}\right) -\end{align} -\end{comment} \subsection{Proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm} %\stratis{individual rationality???} %The proof of the properties of the mechanism is broken down into lemmas. We now present the proof of Theorem~\ref{thm:main}. Truthfulness and individual -rationality follows from monotonicity and threshold payments. Monotonicity and +rationality follow from monotonicity and threshold payments. Monotonicity and budget feasibility follow the same steps as the analysis of \citeN{chen}; for the sake of completeness, we restate their proof in the Appendix. @@ -345,41 +301,57 @@ This solution is: %\end{proof} \subsection{Proof of Lemma~\ref{lemma:relaxation}}\label{sec:relaxation} -%Recall that, since $L$ is a fractional relaxation of $V$, -%\begin{displaymath} -% OPT \leq OPT(L, B). -%\end{displaymath} -%However, for the purpose of proving theorem~\ref{thm:main}, we need to bound -%$L$ from above (up to a multiplicative factor) by $V$. -\junk{ -To prove Lemma~\ref{lemma:relaxation}, we use the -\emph{pipage rounding} method of Ageev and Sviridenko~\cite{pipage}, where -$L$ is first bounded from above by the multi-linear relaxation $F$, which is itself -subsequently bounded by $V$. While the latter part is general and can be applied -to the multi-linear extension of any submodular function, the former part is -specific to our choice for the function $L$. %and is our main technical contribution (lemma~\ref{lemma:relaxation-ratio}). - -The proof has two aspects. The easier part is that $F$ is bounded by $V$. -This is called \emph{cross-convexity} in the literature (see, \emph{e.g.}, -\cite{dughmi}), or $\varepsilon$-convexity by Ageev and Sviridenko~\cite{pipage}. -} - -We prove that our multi-linear function $F$ has a property - which allows to trade one fractional component of the solution for another until -one of them becomes integral, without losing any value. -This property is referred to in the literature as \emph{cross-convexity} (see, \emph{e.g.}, -\cite{dughmi}), or $\varepsilon$-convexity by Ageev and -Sviridenko~\cite{pipage}. -\junk{ +We need to prove that for our relaxation $L$ \eqref{eq:our-relaxation}, $OPT'$ +is close to $OPT$ as stated in Lemma~\ref{lemma:relaxation}. As discussed at +the beginning of Section~\ref{sec:main}, following the same approach as +\citeN{singer-influence}, we make use of the \emph{pipage +rounding} framework of \citeN{pipage}. -a variant of the $\varepsilon$-convexity of the multi-linear -extension \eqref{eq:multilinear} introduced by Ageev and Sviridenko -\cite{pipage} which allows to trade one fractional component of the solution for another until -one of them becomes integral, without loosing any value. This property is also +This framework uses the \emph{multi-linear} extension $F$ of the submodular +function $V$. Let $P_\mathcal{N}^\lambda(S)$ be the probability of choosing the set $S$ if we select each element $i$ in $\mathcal{N}$ independently with probability $\lambda_i$: +\begin{displaymath} + P_\mathcal{N}^\lambda(S) \defeq \prod_{i\in S} \lambda_i + \prod_{i\in\mathcal{N}\setminus S}( 1 - \lambda_i). +\end{displaymath} +Then, the \emph{multi-linear} extension $F$ is defined by: +\begin{equation}\label{eq:multilinear} + F(\lambda) + \defeq \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\big[V(S)\big] + = \sum_{S\subseteq\mathcal{N}} P_\mathcal{N}^\lambda(S) V(S) +\end{equation} + +For \EDP{} the multi-linear extension can be written: +\begin{equation}\label{eq:multi-linear-logdet} + F(\lambda) = \mathbb{E}_{S\sim + P_\mathcal{N}^\lambda}\bigg[\log\det \big(I_d + \sum_{i\in S} x_i\T{x_i}\big) \Big]. +\end{equation} +Note that the relaxation $L$ that we introduced in \eqref{eq:our-relaxation}, +follows naturally from the \emph{multi-linear} relaxation by swapping the +expectation and the $\log\det$ in \eqref{eq:multi-linear-logdet}: +\begin{displaymath} + L(\lambda) = \log\det\left(\mathbb{E}_{S\sim + P_\mathcal{N}^\lambda}\bigg[I_d + \sum_{i\in S} x_i\T{x_i} \bigg]\right). +\end{displaymath} + +The pipage rounding framework then proceeds as follows: +\begin{itemize} +\item First, we prove (Lemma \ref{lemma:rounding}) that $F$ admits the +following rounding property: let $\lambda$ be a feasible element of $[0,1]^n$, +it is possible to trade one fractional component of $\lambda$ for another until +one of them becomes integral, obtaining a new element $\tilde{\lambda}$ which +is both feasible and for which $F(\lambda)\geq F(\lambda)$. 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$. This rounding property is referred to in the literature as \emph{cross-convexity} (see, \emph{e.g.}, -\cite{dughmi}). -} +\cite{dughmi}), or $\varepsilon$-convexity by \citeN{pipage}. +\item Next, we prove the central result of bounding $L$ appropriately in terms +of the multi-linear relaxation $F$ (Lemma \ref{lemma:relaxation-ratio}). +\item Finally, we conclude the proof of Lemma~\ref{lemma:relaxation} by +combining Lemma~\ref{lemma:rounding} and Lemma~\ref{lemma:relaxation-ratio}. +\end{itemize} + +\begin{comment} Formally, %this property states that if we define: \begin{displaymath} @@ -393,11 +365,8 @@ $\reals^{n}$, then $\tilde{F}_\lambda$ is convex. Hence its maximum over the int \end{displaymath} 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. +\end{comment} -The lemma below proves that we can similarly trade a fractional component for -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} For any feasible $\lambda\in[0,1]^{n}$, there exists a feasible $\bar{\lambda}\in[0,1]^{n}$ such that at most one of its components is @@ -424,43 +393,33 @@ a point $\lambda$, we mean that it satisfies the budget constraint $\sum_{i=1}^n \lambda_\varepsilon = \lambda + \varepsilon\left(e_i-\frac{c_i}{c_j}e_j\right) \end{displaymath} It is easy to see that if $\lambda$ is feasible, then: - \begin{multline}\label{eq:convex-interval} + \begin{equation}\label{eq:convex-interval} \forall\varepsilon\in\Big[\max\Big(-\lambda_i,(\lambda_j-1)\frac{c_j}{c_i}\Big), \min\Big(1-\lambda_i, \lambda_j - \frac{c_j}{c_i}\Big)\Big],\;\\ + \frac{c_j}{c_i}\Big)\Big],\; \lambda_\varepsilon\;\;\textrm{is feasible} - \end{multline} + \end{equation} Furthermore, the function $F_\lambda$ is convex; indeed: \begin{align*} F_\lambda(\varepsilon) & = \mathbb{E}_{S'\sim P_{\mathcal{N}\setminus\{i,j\}}^\lambda(S')}\Big[ (\lambda_i+\varepsilon)\Big(\lambda_j-\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{i,j\})\\ - & + (\lambda_i+\varepsilon)\Big(1-\lambda_j+\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{i\})\\ - & + (1-\lambda_i-\varepsilon)\Big(\lambda_j-\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{j\})\\ - & + (1-\lambda_i-\varepsilon)\Big(1-\lambda_j+\varepsilon\frac{c_i}{c_j}\Big)V(S')\Big] + & + (\lambda_i+\varepsilon)\Big(1-\lambda_j+\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{i\}) + + (1-\lambda_i-\varepsilon)\Big(\lambda_j-\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{j\})\\ + & + (1-\lambda_i-\varepsilon)\Big(1-\lambda_j+\varepsilon\frac{c_i}{c_j}\Big)V(S')\Big] \end{align*} Thus, $F_\lambda$ is a degree 2 polynomial whose dominant coefficient is: - \begin{multline*} + \begin{displaymath} \frac{c_i}{c_j}\mathbb{E}_{S'\sim P_{\mathcal{N}\setminus\{i,j\}}^\lambda(S')}\Big[ V(S'\cup\{i\})+V(S'\cup\{i\})\\ -V(S'\cup\{i,j\})-V(S')\Big] - \end{multline*} + \end{displaymath} which is positive by submodularity of $V$. Hence, the maximum of $F_\lambda$ over the interval given in \eqref{eq:convex-interval} is attained at one of its limit, at which either the $i$-th or $j$-th component of $\lambda_\varepsilon$ becomes integral. \end{proof} -Next, we prove the central result of bounding $L$ appropriately in terms of $F$. - -\junk{ -To prove Lemma~\ref{lemma:relaxation}, we use the -\emph{pipage rounding} method of Ageev and Sviridenko~\cite{pipage}, where -$L$ is first bounded from above by the multi-linear relaxation $F$, which is itself -subsequently bounded by $V$. While the latter part is general and can be applied -to the multi-linear extension of any submodular function, the former part is -specific to our choice for the function $L$. %and is our main techn -} \begin{lemma}\label{lemma:relaxation-ratio} % The following inequality holds: @@ -510,11 +469,11 @@ For all $\lambda\in[0,1]^{n},$ $S$ can be written as \begin{align*} V(S\cup \{i\}) - V(S)& = \frac{1}{2}\log\det(I_d - + \T{X_S}X_S + x_i\T{x_i})\\ - & - \frac{1}{2}\log\det(I_d + \T{X_S}X_S)\\ + + \T{X_S}X_S + x_i\T{x_i}) + - \frac{1}{2}\log\det(I_d + \T{X_S}X_S)\\ & = \frac{1}{2}\log\det(I_d + x_i\T{x_i}(I_d + -\T{X_S}X_S)^{-1})\\ -& = \frac{1}{2}\log(1 + \T{x_i}A(S)^{-1}x_i) +\T{X_S}X_S)^{-1}) + = \frac{1}{2}\log(1 + \T{x_i}A(S)^{-1}x_i) \end{align*} where $A(S) =I_d+ \T{X_S}X_S$. % $ V(S\cup\{i\}) - V(S) = \frac{1}{2}\log\left(1 + \T{x_i} A(S)^{-1}x_i\right)$. @@ -528,12 +487,12 @@ Using this, The computation of the derivative of $L$ uses standard matrix calculus. Writing $\tilde{A}(\lambda) = I_d+\sum_{i\in \mathcal{N}}\lambda_ix_i\T{x_i}$: - \begin{align*} - \det \tilde{A}(\lambda + h\cdot e_i) & = \det\big(\tilde{A}(\lambda) - + hx_i\T{x_i}\big)\\ - & =\det \tilde{A}(\lambda)\big(1+ + \begin{displaymath} + \det \tilde{A}(\lambda + h\cdot e_i) = \det\big(\tilde{A}(\lambda) + + hx_i\T{x_i}\big) + =\det \tilde{A}(\lambda)\big(1+ h\T{x_i}\tilde{A}(\lambda)^{-1}x_i\big) - \end{align*} + \end{displaymath} Hence: \begin{displaymath} \log\det\tilde{A}(\lambda + h\cdot e_i)= \log\det\tilde{A}(\lambda) @@ -595,14 +554,14 @@ In particular, \end{displaymath} Finally, using that the inverse is a matrix convex function over symmetric positive definite matrices: - \begin{align*} - \partial_i F(\lambda) &\geq + \begin{displaymath} + \partial_i F(\lambda) \geq \frac{1}{4} - \T{x_i}\bigg(\sum_{S\subseteq\mathcal{N}}P_\mathcal{N}^\lambda(S)A(S)\bigg)^{-1}x_i\\ - & = \frac{1}{4}\T{x_i}\tilde{A}(\lambda)^{-1}x_i\\ - & = \frac{1}{2} + \T{x_i}\bigg(\sum_{S\subseteq\mathcal{N}}P_\mathcal{N}^\lambda(S)A(S)\bigg)^{-1}x_i + = \frac{1}{4}\T{x_i}\tilde{A}(\lambda)^{-1}x_i + = \frac{1}{2} \partial_i L(\lambda) - \end{align*} + \end{displaymath} Having bound the ratio between the partial derivatives, we now bound the ratio $F(\lambda)/L(\lambda)$ from below. Consider the following cases. First, if the minimum of the ratio -- cgit v1.2.3-70-g09d2