Polytope Sampling at the Speed of Isoperimetry
En palabras de los autores
We give faster algorithms for sampling from the uniform distribution over a polytope. Our main result is an algorithm that, when applied to a polytope with constraints in dimensions, uses iterations, each running in time , to return a sample within total variation distance to the uniform distribution. When and , our runtime improves upon all prior works by an factor. Our sampler is based on the recent functional stochastic localization framework of [GST26], and achieves an iteration count nearly matching the Poincar\'e constant of the uniform distribution with respect to the logarithmic barrier.
Resultado principalEl resumen no menciona limitaciones.
Apareció: lunes, 19 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 58 pages