From d0e9c3f41bd11a0bcb32fa13ecbcbb9ec9ea0041 Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Sun, 22 Sep 2013 15:46:14 -0400 Subject: Fist reduction of the main part --- approximation.tex | 90 +++++++------------------------------------------------ 1 file changed, 10 insertions(+), 80 deletions(-) (limited to 'approximation.tex') 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. +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: -%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} - -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}. -- cgit v1.2.3-70-g09d2