Moving our two main results to a section preceding the introduction of our mechanism

1 files changed, 4 insertions, 323 deletions

diff --git a/proofs.tex b/proofs.tex
index 0c06d67..6169bb5 100644
--- a/proofs.tex
+++ b/proofs.tex
@@ -31,18 +31,9 @@ The complexity of the mechanism is given by the following lemma.
     }
 \end{proof}
 
-Finally, we prove the approximation ratio of the mechanism. We use the
-following lemma  which establishes that $OPT'$, the optimal value \eqref{relax}
-of the fractional relaxation $L$ under the budget constraints is not too far
-from $OPT$.  
-\begin{lemma}[Approximation]\label{lemma:relaxation}
-     $   OPT' \leq 2 OPT
-        + 2\max_{i\in\mathcal{N}}V(i)$.
-\end{lemma}
-The proof of Lemma~\ref{lemma:relaxation} is our main technical contribution,
-and can be found in Section \ref{sec:relaxation}.
+Finally, we prove the approximation ratio of the mechanism.
 
-We also use the following lemma from \cite{chen} which bounds $OPT$ in terms of
+We use the following lemma from \cite{chen} which bounds $OPT$ in terms of
 the value of $S_G$, as computed in Algorithm \ref{mechanism}, and $i^*$, the
 element of maximum value.
 
@@ -54,7 +45,7 @@ OPT \leq \frac{e}{e-1}\big( 3 V(S_G) + 2 V(i^*)\big).
 \end{displaymath}
 \end{lemma}
 
-Using Lemmas~\ref{lemma:relaxation} and~\ref{lemma:greedy-bound} we can complete the proof of
+Using Proposition~\ref{prop:relaxation} and~\ref{lemma:greedy-bound} we can complete the proof of
 Theorem~\ref{thm:main} by showing that, for any $\varepsilon > 0$, if
 $OPT_{-i}'$, the optimal value of $L$ when $i^*$ is excluded from
 $\mathcal{N}$, has been computed to a precision $\varepsilon$, then the set
@@ -83,7 +74,7 @@ hence,
 \end{equation}
 
 If the condition  does not hold, by observing that $OPT'_{-i^*}\leq OPT'$ and
-applying Lemma~\ref{lemma:relaxation}, we get
+applying Proposition~\ref{prop:relaxation}, we get
 \begin{displaymath}
     V(i^*)  \stackrel{}\leq \frac{1}{C}OPT_{-i^*}' + \frac{\varepsilon}{C}
     \leq \frac{1}{C} \big(2 OPT + 2 V(i^*)\big) + \frac{\varepsilon}{C}.
@@ -120,316 +111,6 @@ 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
 
-\subsection{Proof of Lemma~\ref{lemma:relaxation}}\label{sec:relaxation}
-
-We need to prove that for our relaxation $L$ given by
-\eqref{eq:our-relaxation}, $OPT'$ is close to $OPT$ as stated in
-Lemma~\ref{lemma:relaxation}. Our analysis follows the \emph{pipage rounding}
-framework of \citeN{pipage}.
-
-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{displaymath}
-    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{displaymath}
-
-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 proof proceeds as follows:
-\begin{itemize}
-\item First, we prove 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(\tilde{\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}), or
-$\varepsilon$-convexity by \citeN{pipage}. This is stated and proven in
-Lemma~\ref{lemma:rounding} and allows us to bound $F$ in terms of $OPT$.
-\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, if we define:
-\begin{displaymath}
-    \tilde{F}_\lambda(\varepsilon) \defeq F\big(\lambda + \varepsilon(e_i
-    - e_j)\big)
-\end{displaymath}
-where $e_i$ and $e_j$ are two vectors of the standard basis of
-$\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}
-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}
-
-\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
-    fractional %, that is, lies in $(0,1)$ and:
-     and $F_{\mathcal{N}}(\lambda)\leq F_{\mathcal{N}}(\bar{\lambda})$.
-\end{lemma}
-\begin{proof}
-    We give a rounding procedure which, given a feasible $\lambda$ with at least
-    two fractional components, returns some feasible $\lambda'$ with one less fractional
-    component such that $F(\lambda) \leq F(\lambda')$.
-
-    Applying this procedure recursively yields the lemma's result.
-    Let us consider such a feasible $\lambda$. Let $i$ and $j$ be two
-    fractional components of $\lambda$ and let us define the following
-    function:
-    \begin{displaymath}
-        F_\lambda(\varepsilon) = F(\lambda_\varepsilon)
-        \quad\textrm{where} \quad
-        \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{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],\;
-            \lambda_\varepsilon\;\;\textrm{is feasible}
-    \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]
-    \end{align*}
-    Thus, $F_\lambda$ is a degree 2 polynomial whose dominant coefficient is:
-    \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{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}
-
-
-\begin{lemma}\label{lemma:relaxation-ratio}
- %   The following inequality holds:
-For all $\lambda\in[0,1]^{n},$
-    %\begin{displaymath}
-     $           \frac{1}{2}
-        \,L(\lambda)\leq
-        F(\lambda)\leq L(\lambda)$.
-    %\end{displaymath}
-\end{lemma}
-\begin{proof}
-    The bound $F_{\mathcal{N}}(\lambda)\leq L_{\mathcal{N}(\lambda)}$ follows by the concavity of the $\log\det$ function.
-    To show the lower bound, 
-    we first prove that $\frac{1}{2}$ is a lower bound of the ratio $\partial_i
-    F(\lambda)/\partial_i L(\lambda)$, where
-    $\partial_i\, \cdot$ denotes the partial derivative with respect to the
-    $i$-th variable.  
-
-   Let us start by computing the derivatives of $F$ and
-    $L$ with respect to the $i$-th component.
-    Observe that
-    \begin{displaymath}
-        \partial_i P_\mathcal{N}^\lambda(S) = \left\{
-            \begin{aligned}
-                & P_{\mathcal{N}\setminus\{i\}}^\lambda(S\setminus\{i\})\;\textrm{if}\;
-                i\in S, \\
-                & - P_{\mathcal{N}\setminus\{i\}}^\lambda(S)\;\textrm{if}\;
-                i\in \mathcal{N}\setminus S. \\
-            \end{aligned}\right.
-    \end{displaymath}
-    Hence,
-    \begin{displaymath}
-        \partial_i F(\lambda) =
-        \sum_{\substack{S\subseteq\mathcal{N}\\ i\in S}}
-        P_{\mathcal{N}\setminus\{i\}}^\lambda(S\setminus\{i\})V(S)
-        - \sum_{\substack{S\subseteq\mathcal{N}\\ i\in \mathcal{N}\setminus S}}
-        P_{\mathcal{N}\setminus\{i\}}^\lambda(S)V(S).
-    \end{displaymath}
-    Now, using that every $S$ such that $i\in S$ can be uniquely written as
-    $S'\cup\{i\}$, we can write:
-    \begin{displaymath}
-        \partial_i F(\lambda) =
-        \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
-        P_{\mathcal{N}\setminus\{i\}}^\lambda(S)\big(V(S\cup\{i\})
-        - V(S)\big).
-    \end{displaymath}
-    The marginal contribution of $i$ to
-    $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)\\
-    &  = \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)
-\end{align*}
-where $A(S) \defeq I_d+ \T{X_S}X_S$, and the last equality follows from the
-Sylvester's determinant identity~\cite{sylvester}.
-%  $  V(S\cup\{i\}) - V(S) = \frac{1}{2}\log\left(1 +  \T{x_i} A(S)^{-1}x_i\right)$.
-Using this,
-    \begin{displaymath}
-        \partial_i F(\lambda) = \frac{1}{2}
-        \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
-        P_{\mathcal{N}\setminus\{i\}}^\lambda(S)
-        \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big)
-    \end{displaymath}
-     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{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{displaymath}
-    Hence,
-    \begin{displaymath}
-       \log\det\tilde{A}(\lambda + h\cdot e_i)= \log\det\tilde{A}(\lambda)
-        + h\T{x_i}\tilde{A}(\lambda)^{-1}x_i + o(h),
-    \end{displaymath}
-    which implies
-    \begin{displaymath}
-        \partial_i L(\lambda)
-        =\frac{1}{2} \T{x_i}\tilde{A}(\lambda)^{-1}x_i.
-    \end{displaymath}
-
-For two symmetric matrices $A$ and $B$, we write $A\succ B$ ($A\succeq B$) if
-$A-B$ is positive definite (positive semi-definite).  This order allows us to
-define the notion of a \emph{decreasing} as well as  \emph{convex} matrix
-function, similarly to their real counterparts. With this definition, matrix
-inversion is decreasing and convex over symmetric positive definite
-matrices (see Example 3.48 p. 110 in \cite{boyd2004convex}).
-In particular,
-\begin{gather*}
-        \forall S\subseteq\mathcal{N},\quad A(S)^{-1} \succeq A(S\cup\{i\})^{-1}
-\end{gather*}
-as $A(S)\preceq A(S\cup\{i\})$. Observe that
- %   \begin{gather*}
- %       \forall 
-$P_{\mathcal{N}\setminus\{i\}}^\lambda(S)\geq P_{\mathcal{N}\setminus\{i\}}^\lambda(S\cup\{i\})$ for all $S\subseteq\mathcal{N}\setminus\{i\}$, and
-       % ,\\
-        $P_{\mathcal{N}\setminus\{i\}}^\lambda(S) \geq P_\mathcal{N}^\lambda(S),$ for all $S\subseteq\mathcal{N}$.
- %\end{gather*}
-    Hence,
-    \begin{align*}
-        \partial_i F(\lambda) 
-      %  & = \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}} P_\mathcal{N}^\lambda(S) \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big)\\
-        & \geq \frac{1}{4}
-        \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
-        P_{\mathcal{N}\setminus\{i\}}^\lambda(S)
-        \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big)\\
-        &\hspace{-3.5em}+\frac{1}{4}
-        \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
-        P_{\mathcal{N}\setminus\{i\}}^\lambda(S\cup\{i\})
-        \log\Big(1 + \T{x_i}A(S\cup\{i\})^{-1}x_i\Big)\\
-        &\geq \frac{1}{4}
-        \sum_{S\subseteq\mathcal{N}}
-        P_\mathcal{N}^\lambda(S)
-        \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big).
-    \end{align*}
-    Using that $A(S)\succeq I_d$ we get that $\T{x_i}A(S)^{-1}x_i \leq
-    \norm{x_i}_2^2 \leq 1$. Moreover, $\log(1+x)\geq x$ for all $x\leq 1$.
-    Hence,
-    \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)^{-1}\bigg)x_i.
-    \end{displaymath}
-    Finally, using that the inverse is a matrix convex function over symmetric
-    positive definite matrices:
-    \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}
-     \partial_i L(\lambda).
-    \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
-    $F(\lambda)/L(\lambda)$ is attained at a point interior to the hypercube, then it is
-    a critical point, \emph{i.e.}, $\partial_i \big(F(\lambda)/L(\lambda)\big)=0$ for all $i\in \mathcal{N}$; hence, at such a critical point:
-    \begin{equation}\label{eq:lhopital}
-        \frac{F(\lambda)}{L(\lambda)}
-        = \frac{\partial_i F(\lambda)}{\partial_i
-        L(\lambda)} \geq \frac{1}{2}.
-    \end{equation}
-    Second, if the minimum is attained as 
-    $\lambda$ converges to zero in, \emph{e.g.}, the $l_2$ norm, by the Taylor approximation, one can write:
-    \begin{displaymath}
-        \frac{F(\lambda)}{L(\lambda)}
-        \sim_{\lambda\rightarrow 0}
-        \frac{\sum_{i\in \mathcal{N}}\lambda_i\partial_i F(0)}
-        {\sum_{i\in\mathcal{N}}\lambda_i\partial_i L(0)}
-        \geq \frac{1}{2},
-    \end{displaymath}
-    \emph{i.e.}, the ratio $\frac{F(\lambda)}{L(\lambda)}$ is necessarily bounded from below by 1/2 for small enough $\lambda$. 
-       Finally, if the minimum is attained on a face of the hypercube $[0,1]^n$ (a face is
-    defined as a subset of the hypercube where one of the variable is fixed to
-    0 or 1), without loss of generality, we can assume that the minimum is
-    attained on the face where the $n$-th variable has been fixed
-    to 0 or 1. Then, either the minimum is attained at a point interior to the
-    face or on a boundary of the face. In the first sub-case, relation
-    \eqref{eq:lhopital} still characterizes the minimum for $i< n$.
-    In the second sub-case, by repeating the argument again by induction, we see
-    that all is left to do is to show that the bound holds for the vertices of
-    the cube (the faces of dimension 1).  The vertices are exactly the binary
-    points, for which we know that both relaxations are equal to the value
-    function $V$. Hence, the ratio is equal to 1 on the vertices.
-\end{proof}
-
-To conclude the proof of Lemma~\ref{lemma:relaxation}, let us consider
-a feasible point $\lambda^*\in[0,1]^{n}$ such that $L(\lambda^*) = OPT'$. By
-applying Lemma~\ref{lemma:relaxation-ratio} and Lemma~\ref{lemma:rounding} we
-get a feasible point $\bar{\lambda}$ with at most one fractional component such
-that
-\begin{equation}\label{eq:e1}
-    L(\lambda^*) \leq 2 F(\bar{\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$.
-    By definition of the multi-linear extension $F$:
-    \begin{displaymath}
-        F(\bar{\lambda}) = (1-\lambda_i)V(S) +\lambda_i V(S\cup\{i\}).
-    \end{displaymath}
-    By submodularity of $V$, $V(S\cup\{i\})\leq V(S) + V(\{i\})$. Hence,
-    \begin{displaymath}
-        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,
-    \begin{equation}\label{eq:e2}
-        F(\bar{\lambda}) \leq  OPT + \max_{i\in\mathcal{N}} V(i).
-    \end{equation}
-    Together, \eqref{eq:e1} and \eqref{eq:e2} imply the lemma. \hspace*{\stretch{1}}\qed
 
 \subsection{Proof of Theorem \ref{thm:lowerbound}}