Efficiently sampling points from an integer lattice.

Question

Let $\mathcal{L}$ = {x$\in$ $N^n$ : ||x||$_1$ $\leq$ m} denote the set of integer points in the positive orthant of the $\ell_1$ ball of radius $m$, where $m < n$. For each $x \in \mathcal{L}$, let w : $\mathcal{L}$ $\rightarrow$ $\mathcal{R}^+$ denote an efficiently computable weighting function. Let $\mathcal{D}$ define a probability distribution over $\mathcal{L}$ that selects each element from $\mathcal{L}$ with probability proportional to its weight: $$\Pr_\mathcal{D}[x] = \frac{w(x)}{\sum_{y\in\mathcal{L}}w(y)}$$

I would like to (approximately) sample from this distribution efficiently, where efficiently means in time polynomial in n, the dimension of the space. The algorithm may query the weight function $w$ a polynomial number of times. In general, this is hard, but I know two additional facts about the weighting function that I suspect make the problem tractable.

1) The weight function is convex: in particular, for any C, the set of points with weight at least C lies inside some convex polytope.

2) The weight function is Lipschitz: for any $x,y \in \mathcal{L} : ||x-y||_1 \leq 1$, $|w(x) - w(y)| \leq$ poly(n).

Is there a known method that would allow efficient sampling from this distribution?

Answer 1

Is your weight convex or concave? Your property 1) is self-contradictory.

In the concave case, you can just take a uniform, polynomial size sample from your simplex and select your point from this selection based on the actual weights.

In the convex case, the same algorithm works if the average of $w$ is comparable to the maximum (both can be obtained in polynomial time by taking a uniform sample and by local descent respectively). If that is not the case, then you can test the same property for the projection of $w$ onto one of the facets of $\mathcal L$. If this projection has the required property, you sample from that facet according to the projected weight and then sample from the fiber over the selected point according to $w$ if the property still does not hold, you take an $n-2$ dimensional face etc. When you get down to vertices, you already know that $w$ is concentrated around the vertices of $\mathcal L$ and can find neighbourhoods of them containing almost all of the weight and having the property of the average of $w$ being comparable to the maximum of $w$ within these neighbourhoods (choose the entire $L$ and repeatedly shrink it by a factor of $1-\frac{1}{poly}$ and test the condition). From those neighbourhoods, choose one according to their total weight, and within the chosen one, take a polynomial size uniform sample and sample according to $w$ from within it.