Muestreo eficiente de puntos de una red entera.

Question

Sea $\mathcal{L}$ = {x $\in$ $N^n$ : ||x|| $_1$ $\leq$ m} denotan el conjunto de puntos enteros en el ortante positivo de la $\ell_1$ bola de radio $m$ donde $m < n$ . Para cada $x \in \mathcal{L}$ , sea w : $\mathcal{L}$ $\rightarrow$ $\mathcal{R}^+$ denota una función de ponderación eficientemente computable. Sea $\mathcal{D}$ definen una distribución de probabilidad sobre $\mathcal{L}$ que selecciona cada elemento de $\mathcal{L}$ con probabilidad proporcional a su peso: $$\Pr_\mathcal{D}[x] = \frac{w(x)}{\sum_{y\in\mathcal{L}}w(y)}$$

Me gustaría muestrear (aproximadamente) de esta distribución de manera eficiente, donde eficiente significa en tiempo polinomial en n, la dimensión del espacio. El algoritmo puede consultar la función de peso $w$ un número polinomial de veces. En general, esto es difícil, pero sé dos hechos adicionales acerca de la función de ponderación que sospecho hacer el problema manejable.

1) La función de peso es convexa: en particular, para cualquier C, el conjunto de puntos con peso al menos C se encuentra dentro de algún politopo convexo.

2) La función de peso es Lipschitz: para cualquier $x,y \in \mathcal{L} : ||x-y||_1 \leq 1$ , $|w(x) - w(y)| \leq$ poli(n).

¿Existe algún método conocido que permita un muestreo eficaz de esta distribución?

Answer 1

¿Su peso es convexo o cóncavo? Tu propiedad 1) es autocontradictoria.

En el caso cóncavo, puede simplemente tomar una muestra uniforme de tamaño polinómico de su simplex y seleccionar su punto a partir de esta selección basándose en los pesos reales.

En el caso convexo, el mismo algoritmo funciona si la media de $w$ es comparable al máximo (ambos pueden obtenerse en tiempo polinómico tomando una muestra uniforme y por descenso local, respectivamente). Si no es así, se puede comprobar la misma propiedad para la proyección de $w$ en una de las facetas de $\mathcal L$ . Si esta proyección tiene la propiedad requerida, se muestrea de esa faceta según el peso proyectado y luego se muestrea de la fibra sobre el punto seleccionado según $w$ si la propiedad aún no se mantiene, se toma una $n-2$ cara dimensional, etc. Cuando se llega a los vértices, ya se sabe que $w$ se concentra alrededor de los vértices de $\mathcal L$ y puede encontrar vecindades de ellas que contengan casi todo el peso y tengan la propiedad de la media de $w$ siendo comparable al máximo de $w$ dentro de estos barrios (elija todo el $L$ y reducirlo repetidamente en un factor de $1-\frac{1}{poly}$ y probar la condición). De esos barrios, elija uno en función de su peso total y, dentro del elegido, tome una muestra uniforme de tamaño polinómico y muestre según $w$ desde su interior.