A Polynomial Number of Random Points does not Determine the Volume of a Convex Body
Ronen Eldan
We show that there is no algorithm which, provided a polynomial number of random points uniformly distributed over a convex body in R^n, can approximate the volume of the body up to a constant factor with high probability.
Specifically, you can't estimate the volume of a convex body merely by sampling. You need to generate new points that are "near" the old ones, and use a membership oracle as well.
Neat...
Can you give an example of a convex body for which an efficient random point oracle exists but not efficient membership oracle? Do such objects ever come up naturally?
ReplyDeleteI'm not sure I can answer that. I think the point of the result was that you can't just sample from the convex body if you want an efficient estimator: it's not that it's cheaper but limited.
ReplyDeleteOn the other hand, I can imagine a membership oracle being hard if the object is described by its vertices only. Computing the convex hull is expensive.
On the other hand, I can imagine a membership oracle being hard if the object is described by its vertices only. Computing the convex hull is expensive.
ReplyDeleteComplexity of computing the convex hull is not really relevant here since you can check membership in this case by solving an LP.
Of course you could say that the vertex coordinates are given by real numbers and so solving an LP is not an option. I don't know if you meant it that way. In this case one could still "almost" sample points from this polytope by using a slight perturbation. (the new polytope has almost the same volume and almost the same interior available for sampling but the membership answers for some points differ for the two polytopes.)
that's what I did mean: you're given the vertices, rather than the inequalities defining the halfspaces.
ReplyDelete@Suresh:
ReplyDeleteMy confusion was whether or not you meant that the vertices have real or rational coordinates.
For rational coordinates checking whether $x \in conv(V)$ or not just amounts to checking that the LP $x=V^T*\Lambda, \Lambda >= 0, \Sigma \lambda_i = 1$ is feasible or not.
If the entries of V are real then we don't know how to check the feasibility efficiently but for rational V it does not matter that you don't know the halfspaces (and you don't need to compute them). It is just a matter of checking feasibility of a rational LP.
I'm having trouble comparing this to the usual concentration results, which show that all the mass is near the surface.
ReplyDeleteOf course, this is all in asymptotic dimensions. In d=2 or d=3, this is easy, right?
Benoit:
ReplyDeleteI think that one of the keys is that you can't distinguish between a uniform dist over a convex shape and a spherical dist using only poly many points.
What you mention about concentration of mass may have something to do with that.