Amostragem log-concava de alta precisão mais rápida via inícios quentes algorítmicos

É um problema fundamental entender a complexidade da amostragem de alta precisão a partir de uma densidade π fortemente log-concava em ℝ d. De fato, na prática, amostradores de alta precisão, como o algoritmo de Langevin ajustado de Metropolis (MALA), permanecem o padrão de fato; e em teoria, através da redução do amostrador proximal, entende-se que tais amostradores são fundamentais para amostragem mesmo além da log-convexidade (em particular, para amostragem sob suposições isoperimétricas). Este artigo melhora a dependência dimenssional desse problema de amostragem para \ (O (d^{1/2}) \). O melhor resultado anterior para MALA era \ (O (d) \). Isso fecha a longa linha de trabalho sobre a complexidade de MALA e, além disso, leva a garantias de ponta para amostragem de alta precisão sob forte log-convexidade e além (graças à redução mencionada). Nosso ponto de partida é que a complexidade de MALA melhora para \ (O (d^{1/2}) \), mas apenas sob um início quente (uma inicialização com divergência de Rényi constante em relação a π). Algoritmos anteriores para encontrar um início quente levavam O (d) tempo e, portanto, dominavam o esforço computacional de amostragem. Nossa principal contribuição técnica resolve essa lacuna ao estabelecer as primeiras taxas de mistura de Rényi \ (O (d^{1/2}) \) para a difusão de Langevin sub-amortecida discretizada. Para isso, desenvolvemos novas técnicas inspiradas em privacidade diferencial baseadas em divergências de Rényi com deslocamentos de Orlicz–Wasserstein, que nos permitem contornar desafios de longa data para provar a rápida convergência de equações diferenciais hipocóercivas.