Fist reduction of the main part

1 files changed, 10 insertions, 80 deletions

diff --git a/approximation.tex b/approximation.tex
index 3e3f482..cc278e1 100644
--- a/approximation.tex
+++ b/approximation.tex
@@ -55,12 +55,10 @@ Contrary to problems such as \textsc{Knapsack}, the
 multi-linear extension \eqref{eq:multi-linear} cannot be optimized in
 polynomial time for  the value function $V$  we study here, given by \eqref{modified}. Hence, we introduce an extension $L:[0,1]^n\to\reals$ s.t.~
 \begin{equation}\label{eq:our-relaxation}
-    \begin{split}
-        L(\lambda) &\defeq
-\log\det\left(I_d + \sum_{i\in\mathcal{N}} \lambda_i x_i\T{x_i}\right)\\
-&= \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),
+        L(\lambda) \defeq
+\log\det\left(I_d + \sum_{i\in\mathcal{N}} \lambda_i x_i\T{x_i}\right),
+%= \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),
 \quad \lambda\in[0,1]^n.
-\end{split}
 \end{equation}
 Note that $L$ also extends $V$, and follows naturally from the multi-linear extension by swapping the
 expectation and $\log \det$ in \eqref{eq:multi-linear}. Crucially, it is \emph{strictly concave} on $[0,1]^n$, a fact that  we exploit in the next section to maximize $L$ subject to the budget constraint in polynomial time.
@@ -68,7 +66,7 @@ expectation and $\log \det$ in \eqref{eq:multi-linear}. Crucially, it is \emph{s
 %    L(\lambda) = 
 %\end{displaymath}
 
-Our first technical lemma relates the concave extension $L$ to the multi-linear extension $F$:
+Our first technical lemma relates $L$ to the multi-linear extension $F$:
 \begin{lemma}\label{lemma:relaxation-ratio}
 For all $\lambda\in[0,1]^{n},$
      $           \frac{1}{2}
@@ -77,8 +75,8 @@ For all $\lambda\in[0,1]^{n},$
 \end{lemma}
 The proof of this lemma can be found in Appendix~\ref{proofofrelaxation-ratio}. In short,  exploiting the concavity of the $\log\det$ function over the set of positive semi-definite matrices, we first  bound the ratio of all partial derivatives of $F$ and $L$. We then show that the bound on the ratio of the derivatives also implies a bound on the ratio $F/L$.
 
-Armed with this result, we subsequently use  pipage rounding to show that any $\lambda$ that maximizes the multi-linear extension $F$ can be rounded to an ``almost'' integral solution. More specifically, given a set of costs $c\in \reals^n_+$, we say that a $\lambda\in [0,1]^n$ is feasible if it belongs to the set 
-\begin{align}\dom_c =\{\lambda \in [0,1]^n: \sum_{i\in \mathcal{N}} c_i\lambda_i\leq B\}.\label{fdom}\end{align} Then, the following lemma holds:
+Armed with this result, we subsequently use  pipage rounding to show that any $\lambda$ that maximizes the multi-linear extension $F$ can be rounded to an ``almost'' integral solution. More specifically, given a set of costs $c\in \reals^n_+$, we say that a $\lambda\in [0,1]^n$ is feasible if it belongs to the set $\dom_c =\{\lambda \in [0,1]^n: \sum_{i\in \mathcal{N}} c_i\lambda_i\leq B\}$. Then, the following lemma holds:
+
 \begin{lemma}[Rounding]\label{lemma:rounding}
     For any feasible $\lambda\in \dom_c$, there exists a feasible
     $\bar{\lambda}\in \dom_c$ such that (a) $F(\lambda)\leq F(\bar{\lambda})$, and (b) at most one of the 
@@ -87,11 +85,9 @@ Armed with this result, we subsequently use  pipage rounding to show that any $\
 The proof of this lemma is in Appendix \ref{proofoflemmarounding}, and follows the main steps of the pipage rounding method of \citeN{pipage}. % 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}. 
 Together, Lemma~\ref{lemma:relaxation-ratio} and Lemma~\ref{lemma:rounding} imply that $OPT$, the optimal value of \EDP, can be approximated by solving the following convex optimization problem:
 \begin{align}\tag{$P_c$}\label{eq:primal}
-\begin{split}  \text{Maximize:} &\qquad L(\lambda)\\
-\text{subject to:} & \qquad\lambda \in \dom_c
-\end{split}
+\text{Maximize:} \quad L(\lambda)\quad \text{subject to:} \quad\lambda \in \dom_c
 \end{align}
-In particular, for $L_c^*\defeq \max_{\lambda\in \dom_c} L(\lambda)$ the optimal value of \eqref{eq:primal}, the following holds:
+In particular, for $L_c^*\defeq \max_{\lambda\in \dom_c} L(\lambda)$, the following holds:
 \begin{proposition}\label{prop:relaxation}
 $OPT\leq L^*_c \leq 2 OPT + 2\max_{i\in\mathcal{N}}V(i)$.
 \end{proposition}
@@ -127,79 +123,13 @@ Nevertheless, we prove that it is possible to use the barrier method to construc
     for all $i\in \mathcal{N},x\in\reals^n, \mu\geq\delta,$
 %\end{equation}
 where $e_i$ is the $i$-th canonical basis vector of $\reals^n$.
-In other words, $f$ is $\delta$-decreasing if increasing any coordinate by $\delta$ or more at input $x$ ensures that the output will be at most $f(x)$.
-
-Our next technical result establishes that, using the barrier method, it is possible to construct an algorithm that computes $L^*_c$ at arbitrary accuracy in polynomial time \emph{and} is $\delta$-decreasing. We achieve this by restricting the optimization over a subset of $\dom_c$ at which the concave relaxation $L$ is ``sufficiently'' concave. Formally, for $\alpha\geq 0$ let $$\textstyle\dom_{c,\alpha} \defeq \{\lambda \in [\alpha,1]^n: \sum_{i\in \mathcal{N}}c_i\lambda_i \leq B\}\subseteq  \dom_c . $$ 
-Note that $\dom_c=\dom_{c,0}.$ Consider the following perturbation of the concave relaxation \eqref{eq:primal}:
-\begin{align}\tag{$P_{c,\alpha}$}\label{eq:perturbed-primal}
-\begin{split}  \text{Maximize:} &\qquad L(\lambda)\\
-\text{subject to:} & \qquad\lambda \in \dom_{c,\alpha}
-\end{split}
-\end{align}
-
-%Note, that the feasible set in Problem~\eqref{eq:primal} increases (for the
-%inclusion) when the cost decreases. 
-%non-increasing.
-
-%Furthermore, \eqref{eq:primal} being a convex optimization problem, using
-%standard convex optimization algorithms (Lemma~\ref{lemma:barrier} gives
-%a formal statement for our specific problem) we can compute
-%a $\varepsilon$-accurate approximation of its optimal value as defined below.
-
-%\begin{definition}
-%$a$ is an $\varepsilon$-accurate approximation of $b$ iff $|a-b|\leq \varepsilon$.
-%\end{definition}
-
-%Note however that an $\varepsilon$-accurate approximation of a non-increasing
-%function is not in general non-increasing itself. The goal of this section is
-%to approximate $L^*_c$ while preserving monotonicity. The estimator we
-%construct has a weaker form of monotonicity that we call
-%\emph{$\delta$-monotonicity}.
-
-%\begin{definition}
-%Let $f$ be a function from $\reals^n$ to $\reals$, we say that $f$ is
-%\emph{$\delta$-increasing along the $i$-th coordinate} iff:
-%\begin{equation}\label{eq:dd}
-%    \forall x\in\reals^n,\;
-%    \forall \mu\geq\delta,\;
-%    f(x+\mu e_i)\geq f(x)
-%\end{equation}
-%where $e_i$ is the $i$-th canonical basis vector of $\reals^n$. By extension,
-%$f$ is $\delta$-increasing iff it is $\delta$-increasing along all coordinates.
-
-%We define \emph{$\delta$-decreasing} functions by reversing the inequality in
-%\eqref{eq:dd}.
-%\end{definition}
-
-%We consider a perturbation of \eqref{eq:primal} by introducing:
-%\begin{equation}\tag{$P_{c, \alpha}$}\label{eq:perturbed-primal}
-%    L^*_{c,\alpha} \defeq \max_{\lambda\in[\alpha, 1]^{n}}
-%    \left\{L(\lambda) \Big| \sum_{i=1}^{n} \lambda_i c_i
-%    \leq B\right\}
-%\end{equation}
-%Note that we have $L^*_c = L^*_c(0)$.  We will also assume that
-%$\alpha<\frac{1}{nB}$ so that \eqref{eq:perturbed-primal} has at least one
-%feasible point: $(\frac{1}{nB},\ldots,\frac{1}{nB})$. By computing
-%an approximation of $L^*_{c,\alpha}$ as in Algorithm~\ref{alg:monotone}, we
-%obtain a $\delta$-decreasing approximation of $L^*_c$.
-
-\begin{algorithm}[t]
-    \caption{}\label{alg:monotone}
-    \begin{algorithmic}[1]
-	\Require{ $B\in \reals_+$, $c\in[0,B]^n$, $\delta\in (0,1]$, $\epsilon\in (0,1]$ }
-        \State $\alpha \gets \varepsilon (\delta/B+n^2)^{-1}$ 
-        \State Use the barrier method to solve \eqref{eq:perturbed-primal} with
-        accuracy $\varepsilon'=\frac{1}{2^{n+1}B}\alpha\delta b$; denote the output by $\hat{L}^*_{c,\alpha}$
-	\State \textbf{return} $\hat{L}^*_{c,\alpha}$
-    \end{algorithmic}
-\end{algorithm}
+In other words, $f$ is $\delta$-decreasing if increasing any coordinate by $\delta$ or more at input $x$ ensures that the output will be at most $f(x)$. In particular, the following proposition holds:
 
-Our construction of a $\delta$-decreasing, $\varepsilon$-accurate approximator of $L_c^*$ proceeds as follows: first, it computes an appropriately selected lower bound $\alpha$; using this bound, it solves the perturbed problem \eqref{eq:perturbed-primal} using the barrier method, also at an appropriately selected accuracy $\varepsilon'$, obtaining thus a $\varepsilon'$-accurate approximation of $L^*_{c,\alpha}\defeq \max_{\lambda\in \dom_{c,\alpha}} L(\lambda)$ . The corresponding output is returned as an approximation of $L^*_c$. A summary of the algorithm and the specific choices of $\alpha$ and $\varepsilon'$ are given in Algorithm~\ref{alg:monotone}. The following proposition, which is proved in Appendix~\ref{proofofpropmonotonicity}, establishes that this algorithm has both properties we desire:
 \begin{proposition}\label{prop:monotonicity}
     For any $\delta\in(0,1]$ and any $\varepsilon\in(0,1]$,
     Algorithm~\ref{alg:monotone} computes a $\delta$-decreasing,
     $\varepsilon$-accurate approximation of $L^*_c$. The running time of the
     algorithm is $O\big(poly(n, d, \log\log\frac{B}{b\varepsilon\delta})\big)$.
 \end{proposition}
-We note that the execution of the barrier method on the restricted set $\dom_{c,\alpha}$ is necessary. The algorithm's output when executed over the entire domain may not necessarily be $\delta$-decreasing, even when the approximation accuracy is small. This is because costs become saturated when the optimal $\lambda\in \dom_c$ lies at the boundary: increasing them has no effect on the objective. Forcing the optimization to happen ``off'' the boundary ensures that this does not occur, while taking $\alpha$ to be small ensures that this perturbation does not cost much in terms of approximation accuracy.
 
+The description of Algorithm~\ref{alg:monotone} as well as the proof of the proposition can be found in Appendix~\ref{proofofproprelaxation}.