2018/02/27 by Ya-Ping Hsieh, Hsieh, Ya-Ping, Kavis, Ali +2 · 8 citations
Computer Science · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Generative Adversarial Networks and Image Synthesis #Machine Learning (cs.LG) #Markov Chains and Monte Carlo Methods #Optimization and Control (math.OC) #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1802.10174
openalex publication_date 2018/02/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of sampling from constrained distributions, which has posed significant challenges to both non-asymptotic analysis and algorithmic design. We propose a unified framework, which is inspired by the classical mirror descent, to derive novel first-order sampling schemes. We prove that, for a general target distribution with strongly convex potential, our framework implies the existence of a first-order algorithm achieving O(ε-2d) convergence, suggesting that the state-of-the-art O(ε-6d5) can be vastly improved. With the important Latent Dirichlet Allocation (LDA) application in mind, we specialize our algorithm to sample from Dirichlet posteriors, and derive the first non-asymptotic O(ε-2d2) rate for first-order sampling. We further extend our framework to the mini-batch setting and prove convergence rates when only stochastic gradients are available. Finally, we report promising experimental results for LDA on real datasets.