diff options
Diffstat (limited to 'approximation.tex')
| -rw-r--r-- | approximation.tex | 12 |
1 files changed, 6 insertions, 6 deletions
diff --git a/approximation.tex b/approximation.tex index 2f73a6b..10cf171 100644 --- a/approximation.tex +++ b/approximation.tex @@ -46,9 +46,9 @@ expectation of $V$ under the distribution $P_\mathcal{N}^\lambda$: 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) -= \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\left[ \log\det\left( I_d + \sum_{i\in S} x_i\T{x_i}\right) \right] += \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\left[ \log\det\left( I_d + \sum_{i\in S} x_i\T{x_i}\right) \right]. \end{equation} -Function $F$ is an extension of $V$ to the domain $[0,1]^n$, as it agrees with $V$ at integer inputs: $F(\id_S) = V(S)$ for all +Function $F$ is an extension of $V$ to the domain $[0,1]^n$, as it equals $V$ on integer inputs: $F(\id_S) = V(S)$ for all $S\subseteq\mathcal{N}$, where $\id_S$ denotes the indicator vector of $S$. %\citeN{pipage} have shown how to use this extension to obtain approximation guarantees for an interesting class of optimization problems through the \emph{pipage rounding} framework, which has been successfully applied in \citeN{chen, singer-influence}. For $V$ the value function given by \eqref{modified} that we study here, the multi-linear extension \eqref{eq:multi-linear} cannot be computed---let alone maximized---in @@ -59,7 +59,7 @@ polynomial time. Hence, we introduce a new extension $L:[0,1]^n\to\reals$: \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{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 \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. +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. %\begin{displaymath} % L(\lambda) = %\end{displaymath} @@ -108,7 +108,7 @@ The proof of this proposition can be found in Appendix~\ref{proofofproprelaxatio %proposition which is also proved in the Appendix. \subsection{Polynomial-Time, Almost-Monotonous Approximation}\label{sec:monotonicity} - The $\log\det$ objective function of \eqref{eq:primal} is known to be concave and \emph{self-concordant} \cite{boyd2004convex}. The maximization of a concave, self-concordant function subject to a set of linear constraints can be performed through the \emph{barrier method} (see, \emph{e.g.}, \cite{boyd2004convex} Section 11.5.5 for general self-concordant optimization as well as \cite{vandenberghe1998determinant} for a detailed treatise of the $\log\det$ case). The performance of the barrier method is summarized in our case by the following lemma: + The $\log\det$ objective function of \eqref{eq:primal} is strictly concave and \emph{self-concordant} \cite{boyd2004convex}. The maximization of a concave, self-concordant function subject to a set of linear constraints can be performed through the \emph{barrier method} (see, \emph{e.g.}, \cite{boyd2004convex} Section 11.5.5 for general self-concordant optimization as well as \cite{vandenberghe1998determinant} for a detailed treatise of the $\log\det$ objective). The performance of the barrier method is summarized in our case by the following lemma: \begin{lemma}[\citeN{boyd2004convex}]\label{lemma:barrier} For any $\varepsilon>0$, the barrier method computes an approximation $\hat{L}^*_c$ that is $\varepsilon$-accurate, \emph{i.e.}, it satisfies $|\hat L^*_c- L^*_c|\leq \varepsilon$, in time $O\left(poly(n,d,\log\log\varepsilon^{-1})\right)$. @@ -123,9 +123,9 @@ Nevertheless, it is possible to use the barrier method to construct an approxima \text{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 input will be at most $f(x)$. +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 lemma 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$-monotone. 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 . $$ +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$-monotone. 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)\\ |