diff options
Diffstat (limited to 'approximation.tex')
| -rw-r--r-- | approximation.tex | 9 |
1 files changed, 5 insertions, 4 deletions
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. |