NeurIPS 2022 | 馬里蘭、北大等機構提出量子算法用于采樣對數凹分布和估計歸一化常數
加入技術交流群
本文是 NeurIPS 2022 入選論文《Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants》的解讀。該方法對數凹采樣（log-concave sampling）在機器學習、物理、統計等領域有著諸多應用。
對數凹采樣（log-concave sampling）在機器學習、物理、統計等領域有著諸多應用。本文基于朗之萬擴散（Langevin diffusion）設計了新的量子算法，用于采樣對數凹分布和估計歸一化常數，相比最好的經典算法對于精度（ε），維度（d），條件數（κ）等參數達到了多項式級加速。
論文地址：https://arxiv.org/abs/2210.06539
本文作者包括：Andrew M. Childs（馬里蘭大學），李彤陽（北京大學），劉錦鵬（加州大學伯克利分校西蒙斯研究所），王春昊（賓州州立大學）和張睿哲（德州大學奧斯汀分校）。
問題介紹
從給定的分布函數采樣是一個基礎的計算問題。例如，在統計中，樣本可以確定置信區(qū)間或探索后驗分布。在機器學習中，樣本用于回歸和訓練監(jiān)督學習模型。在優(yōu)化中，來自精心挑選的樣本分布可以產生接近局部甚至全局最優(yōu)的點。本文考慮的問題是對數凹采樣（log-concave sampling），這個問題涵蓋了許多實際應用例子，例如多元高斯分布和指數分布。與之相關的一個問題是估計對數凹分布的歸一化常（normalizing constant），這個問題也有許多應用，例如配分函數（partition function）的估計[2]。更多相關工作見參考文獻[3, 4, 5, 6]。
問題模型
- 對數凹采樣：輸出一個隨機變量滿足分布 ，使得 ；
- 歸一化常數估計：輸出一個隨機變量 ，使得以至少 的概率滿足 。
主要貢獻
- ，這里 是 Wasserstein 2-范數，對于量子訪問 oracle 的查詢復雜度為 ；或
- ，這里 是全變差距離（total-variation distance），對于量子梯度 oracle 的查詢復雜度為 ；若初始分布滿足熱啟動條件，則復雜度為 。
定理 2（歸一化常數估計）存在量子算法輸出一個隨機變量 ，使得以至少 的概率滿足 ，
- 對于量子訪問 oracle 的查詢復雜度為 ；或
- 對于量子梯度 oracle 的查詢復雜度為 ；若有一個熱的初始概率分布（warm start），則復雜度為 。
另外，這個任務的量子查詢復雜度的下界是 。
我們在表1和表2總結了我們的結果和先前經典算法復雜度的對比。
技術改進
1. 量子模擬退火（quantum simulated annealing）。我們用于估計歸一化常數的量子算法結合了量子模擬退火框架和量子平均值估計算法。對于每種類型，根據朗之萬動力學（隨機游走），我們構建了相應的量子游走。重要的是，隨機游走的譜間隙在相應的量子游走的相位間隙中被“放大”為原先的平方。這讓在給定足夠好的初始狀態(tài)的情形，我們使用類似 Grover 算法的過程來產生穩(wěn)定分布狀態(tài)。在退火框架中，這個初始狀態(tài)就是前一個馬爾可夫鏈的穩(wěn)定分布狀態(tài)。
2. 有效譜間隙（effective spectral gap）。我們展示了如何利用熱啟動的初始分布來實現量子加速用于采樣。即使譜間隙很小，熱啟動也會導致更快的混合。在量子算法中，我們將“有效譜間隙”的概念推廣到我們更一般的采樣問題。我們表明使用有界熱啟動參數，量子算法可以在混合時間上實現平方加速。通過將采樣問題視為只有一個馬爾可夫鏈的模擬退火過程，通過分析有效譜間隙，我們證明了量子算法實現了平方加速。
3. 量子梯度估計（quantum gradient estimation）。我們將 Jordan 的量子梯度算法應用于我們的量子算法，并給出嚴格的證明來限制由于梯度估計誤差引起的采樣誤差。
參考文獻
[1] Andrew M. Childs, Tongyang Li, Jin-Peng Liu, Chunhao Wang, and Ruizhe Zhang, "Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants," to appear in NeurIPS 2022.
[2] Rong Ge, Holden Lee, and Jianfeng Lu, "Estimating normalizing constants for log-concave distributions: Algorithms and lower bounds," STOC 2020.
[3] Xiang Cheng, Niladri S. Chatterji, Peter L. Bartlett, and Michael I. Jordan, "Underdamped langevin mcmc: A non-asymptotic analysis," COLT 2018.
[4] Yin Tat Lee, Ruoqi Shen, and Kevin Tian, "Logsmooth gradient concentration and tighter runtimes for metropolized Hamiltonian Monte Carlo," COLT 2020.
[5] Ruoqi Shen and Yin Tat Lee, "The randomized midpoint method for log-concave sampling," NeurIPS 2019.
[6] Keru Wu, Scott Schmidler, and Yuansi Chen, "Minimax mixing time of the Metropolis-adjusted Langevin algorithm for log-concave sampling," 2021, arXiv:2109.13055.
*博客內容為網友個人發(fā)布，僅代表博主個人觀點，如有侵權請聯系工作人員刪除。
