{"ID":2847350,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.00708","arxiv_id":"2511.00708","title":"Polynomial Mixing Times of Simulated Tempering for Mixture Targets by Conductance Decomposition","abstract":"We study the theoretical complexity of simulated tempering for sampling from mixtures of log-concave components differing only by location shifts. The main result establishes the first polynomial-time guarantee for simulated tempering combined with the Metropolis-adjusted Langevin algorithm (MALA) with respect to the problem dimension $d$, maximum mode displacement $D$, and logarithmic accuracy $\\log ε^{-1}$. The proof builds on a general state decomposition theorem for $s$-conductance, applied to an auxiliary Markov chain constructed on an augmented space. We also obtain an improved complexity estimate for simulated tempering combined with random-walk Metropolis. Our bounds assume an inverse-temperature ladder with smallest value $β_1 = O(D^{-2})$ and spacing $β_{i+1}/β_i = 1 + O( d^{-1/2} )$, both of which are shown to be asymptotically optimal up to logarithmic factors.","short_abstract":"We study the theoretical complexity of simulated tempering for sampling from mixtures of log-concave components differing only by location shifts. The main result establishes the first polynomial-time guarantee for simulated tempering combined with the Metropolis-adjusted Langevin algorithm (MALA) with respect to the p...","url_abs":"https://arxiv.org/abs/2511.00708","url_pdf":"https://arxiv.org/pdf/2511.00708v1","authors":"[\"Quan Zhou\"]","published":"2025-11-01T21:16:35Z","proceeding":"stat.CO","tasks":"[\"stat.CO\",\"math.PR\",\"stat.ML\"]","methods":"[]","has_code":false}