From d69b4c803cd32e6b3cfe19965ebaa08e19751af3 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Sat, 6 Jul 2013 16:55:18 +0200
Subject: Fixing issues related to cost nomalization

---
 approximation.tex | 9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)

(limited to 'approximation.tex')

diff --git a/approximation.tex b/approximation.tex
index 1a4b44b..c306a75 100644
--- a/approximation.tex
+++ b/approximation.tex
@@ -183,9 +183,10 @@ Note that $\dom_c=\dom_{c,0}.$ Consider the following perturbation of the concav
 \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 \min\left(\varepsilon B^{-1}(\delta+n^2)^{-1},\frac{1}{nB}\right) $ 
-        \State Use the barrier method to solve \eqref{eq:perturbed-primal} with accuracy $\varepsilon'=\frac{1}{2^{n+1}}\alpha\delta b$; denote the output by $\hat{L}^*_{c,\alpha}$
+	\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}
@@ -195,7 +196,7 @@ Our construction of a $\delta$-decreasing, $\varepsilon$-accurate approximator o
     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{1}{b\varepsilon\delta})\big)$. \note{THIBAUT, IS THERE A BUDGET $B$ IN THE NUMERATOR OF THE LOGLOG TERM?}
+    algorithm is $O\big(poly(n, d, \log\log\frac{B}{b\varepsilon\delta})\big)$.
 \end{proposition}
 We note that the 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.
 
-- 
cgit v1.2.3-70-g09d2