From d0e9c3f41bd11a0bcb32fa13ecbcbb9ec9ea0041 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Sun, 22 Sep 2013 15:46:14 -0400
Subject: Fist reduction of the main part

---
 appendix.tex | 67 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 66 insertions(+), 1 deletion(-)

(limited to 'appendix.tex')

diff --git a/appendix.tex b/appendix.tex
index 5cb60f8..73e879d 100644
--- a/appendix.tex
+++ b/appendix.tex
@@ -264,7 +264,72 @@ Together, \eqref{eq:e1} and \eqref{eq:e2} imply the proposition.\qed
 %For any $\varepsilon>0$, the barrier method computes an $\varepsilon$-accurate
 %approximation of $L^*_c$ in time $O(poly(n,d,\log\log\varepsilon^{-1})$.
 %\end{lemma}
-We proceed by showing that the optimal value of \eqref{eq:perturbed-primal} is close to the
+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}
+
+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}. We proceed by showing that the optimal value of \eqref{eq:perturbed-primal} is close to the
 optimal value of \eqref{eq:primal} (Lemma~\ref{lemma:proximity}) while being
 well-behaved with respect to changes of the cost
 (Lemma~\ref{lemma:monotonicity}). These lemmas together imply
-- 
cgit v1.2.3-70-g09d2

