Why is the first step in the Lovasz-Vempala convex volume algorithm correct?

I've been reading about convex volume estimation, and have found the paper "Simulated Annealing in Convex Bodies and an $O^{*}(n^4)$ Volume Algorithm" by Lovasz and Vempala, which can be read here.

The algorithm provided relies the standard multi-phase monte-carlo technique of producing a series of values, the first of which is easy to compute, the remainder estimatable by random variables, and then combining each of these variables in some way to produce an estimate of the volume. This particular technique involves extruding an $n$-dimensional shape into an $n+1$-dimensional pencil, and estimating the volume of that pencil. The pencil is defined as the intersection of a cylinder over the convex body and a cone. Let $K$ be the convex body, and

$$C = \{{\bf x} \in \mathbb{R}^{n+1} | x_0 > 0, \; \sum^n_{i=1}x_i^2 \leqslant x_0^2\}$$ The pencil, $K'$, is defined: $$K' = ([0,2D] \times K) \cap C$$

By assumption, $K$ contains the unit ball, so the set of points in $K'$ with $x_0<1$ is exactly the $n+1$-dimensional hypercone with height $1$ and whose base is the $n$-ball of radius $1$. This cone is referred to as $C_B$. We also denote by $\pi_n$ the volume of the unit n-ball. The estimates of the volume of the pencil are provided using the following function:

$$Z(a) = \int_{K'} e^{-ax_0} d{\bf x}$$

For a sufficiently small value of $a$, $Z(a)$ can be shown to be a good estimate for the volume of $K'$. For $a \geqslant 2n$, it is claimed that $Z(a)$ is close to the above integral taken over the entire cone $C$. We know that $K' \subseteq C$ from its definition, hence

$$Z(a) = \int_{K'} e^{-ax_0} d{\bf x} \leqslant \int_{C} e^{-ax_0} d{\bf x} = \int_0^\infty e^{-at}t^n \pi_n dt = n! \pi_n a^{-(n+1)}$$

We know also that $C_B \subseteq K'$, hence

$$Z(a) \geqslant \int_{C_B} e^{-ax_0} d{\bf x} = \int_0^1 e^{-at}t^n \pi_n dt$$

At this point, I can no longer follow the paper's reasoning. It is stated that

$$\int_0^1 e^{-at}t^n \pi_n dt > (1-\varepsilon) \int_0^\infty e^{-at}t^n \pi_n dt$$

No bounds are specified on $\varepsilon$. Indeed, our estimation algorithm should be able to take an arbitrarily small value of $\varepsilon$. The integrand, hovever, is non-negative across its domain of integration, so it must be the case that

$$\int_0^1 e^{-at}t^n \pi_n dt \leqslant \int_0^\infty e^{-at}t^n \pi_n dt$$

Surely, then, the inequality in $\varepsilon$ would only hold for a sufficiently large value of $\varepsilon$, rather than for an arbitrarily small one. Further, stating that $a\geqslant 2n$ gives no information about a relationship between $\varepsilon$ and $a$. How is it even possible to reach the conclusion from the premise in this case? Further still, an independent talk on the algorithm found here suggests instead that the inequality only holds for $a>6n$, rather than $a>2n$. The paper states that this is true by standard computation, so I do feel that I must be missing something here, but I cannot tell what.

I've emailed both of the authors at the email addresses I can find for them, and haven't received any response from them, so hopefully someone from here can help.

1 Answer

It is also unclear to me what $\epsilon$ means in that line of the paper. The approximation error for $Z(a_0)$ is never mentioned again; my interpretation is that the authors are saying the error is so small it can be ignored.

The bound I get is: $$\tag{*} Z(a_0)=Z(2n) \geq (1-(2/e)^n \mathrm{poly}(n)) \int_0^\infty e^{-2nt} t^n \pi_n dt.$$

So the approximation should be ok for $n > 100 \log \epsilon^{-1}$ and large $n$. I don't know if it is necessary to use a different analysis or algorithm to get Theorem 1.1 as stated for the regime where $\epsilon$ is exponentially small compared to $n$.

To show (*), I claim the stronger statement that $\int_1^\infty e^{-at}t^n dt \leq e^{-a}/n$ for all $a\geq 2n$ - this can be shown by induction on $n$. Using Stirling's approximation on $\int_0^\infty e^{-2nt}t^n dt=n!(2n)^{-(n+1)}$, $$\frac{\int_1^\infty e^{-2nt}t^n dt} {\int_0^\infty e^{-2nt}t^n dt} \leq \frac{e^{-2n}(2n)^n}{n^n e^{-n}} \mathrm{poly}(n) = (2/e)^n \mathrm{poly}(n).$$

• Thanks for the answer, this is very useful. $\varepsilon$ is the relative error of the estimate. The ultimate goal is to find a $v$ such that $$(1-\varepsilon)v \leqslant \mbox{vol}(K) \leqslant (1+\varepsilon)v$$ At no point are bounds specified on $\varepsilon$, but taking into account what you've written it does seem to be implicit that $\varepsilon$ is not too small, which is a little disappointing, but that does at least confirm to me that the bound is sufficient for most purposes. I'm not sure where the counter-claim that $a_0 > 6n$ came from. That was just plain confusing. – ymbirtt Sep 8 '13 at 10:57