NeurIPS 2022 | 馬里蘭、北大等機(jī)構(gòu)提出量子算法用于采樣對數(shù)凹分布和估計(jì)歸一化常數(shù)
加入技術(shù)交流群
本文是 NeurIPS 2022 入選論文《Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants》的解讀。該方法對數(shù)凹采樣（log-concave sampling）在機(jī)器學(xué)習(xí)、物理、統(tǒng)計(jì)等領(lǐng)域有著諸多應(yīng)用。
對數(shù)凹采樣（log-concave sampling）在機(jī)器學(xué)習(xí)、物理、統(tǒng)計(jì)等領(lǐng)域有著諸多應(yīng)用。本文基于朗之萬擴(kuò)散（Langevin diffusion）設(shè)計(jì)了新的量子算法，用于采樣對數(shù)凹分布和估計(jì)歸一化常數(shù)，相比最好的經(jīng)典算法對于精度（ε），維度（d），條件數(shù)（κ）等參數(shù)達(dá)到了多項(xiàng)式級加速。
論文地址：https://arxiv.org/abs/2210.06539
本文作者包括：Andrew M. Childs（馬里蘭大學(xué)），李彤陽（北京大學(xué)），劉錦鵬（加州大學(xué)伯克利分校西蒙斯研究所），王春昊（賓州州立大學(xué)）和張睿哲（德州大學(xué)奧斯汀分校）。
問題介紹
從給定的分布函數(shù)采樣是一個基礎(chǔ)的計(jì)算問題。例如，在統(tǒng)計(jì)中，樣本可以確定置信區(qū)間或探索后驗(yàn)分布。在機(jī)器學(xué)習(xí)中，樣本用于回歸和訓(xùn)練監(jiān)督學(xué)習(xí)模型。在優(yōu)化中，來自精心挑選的樣本分布可以產(chǎn)生接近局部甚至全局最優(yōu)的點(diǎn)。本文考慮的問題是對數(shù)凹采樣（log-concave sampling），這個問題涵蓋了許多實(shí)際應(yīng)用例子，例如多元高斯分布和指數(shù)分布。與之相關(guān)的一個問題是估計(jì)對數(shù)凹分布的歸一化常（normalizing constant），這個問題也有許多應(yīng)用，例如配分函數(shù)（partition function）的估計(jì)[2]。更多相關(guān)工作見參考文獻(xiàn)[3, 4, 5, 6]。
問題模型
- 對數(shù)凹采樣：輸出一個隨機(jī)變量滿足分布 ，使得 ；
- 歸一化常數(shù)估計(jì)：輸出一個隨機(jī)變量 ，使得以至少 的概率滿足 。
主要貢獻(xiàn)
- ，這里 是 Wasserstein 2-范數(shù)，對于量子訪問 oracle 的查詢復(fù)雜度為 ；或
- ，這里 是全變差距離（total-variation distance），對于量子梯度 oracle 的查詢復(fù)雜度為 ；若初始分布滿足熱啟動條件，則復(fù)雜度為 。
定理 2（歸一化常數(shù)估計(jì)）存在量子算法輸出一個隨機(jī)變量 ，使得以至少 的概率滿足 ，
- 對于量子訪問 oracle 的查詢復(fù)雜度為 ；或
- 對于量子梯度 oracle 的查詢復(fù)雜度為 ；若有一個熱的初始概率分布（warm start），則復(fù)雜度為 。
另外，這個任務(wù)的量子查詢復(fù)雜度的下界是 。
我們在表1和表2總結(jié)了我們的結(jié)果和先前經(jīng)典算法復(fù)雜度的對比。
技術(shù)改進(jìn)
1. 量子模擬退火（quantum simulated annealing）。我們用于估計(jì)歸一化常數(shù)的量子算法結(jié)合了量子模擬退火框架和量子平均值估計(jì)算法。對于每種類型，根據(jù)朗之萬動力學(xué)（隨機(jī)游走），我們構(gòu)建了相應(yīng)的量子游走。重要的是，隨機(jī)游走的譜間隙在相應(yīng)的量子游走的相位間隙中被“放大”為原先的平方。這讓在給定足夠好的初始狀態(tài)的情形，我們使用類似 Grover 算法的過程來產(chǎn)生穩(wěn)定分布狀態(tài)。在退火框架中，這個初始狀態(tài)就是前一個馬爾可夫鏈的穩(wěn)定分布狀態(tài)。
2. 有效譜間隙（effective spectral gap）。我們展示了如何利用熱啟動的初始分布來實(shí)現(xiàn)量子加速用于采樣。即使譜間隙很小，熱啟動也會導(dǎo)致更快的混合。在量子算法中，我們將“有效譜間隙”的概念推廣到我們更一般的采樣問題。我們表明使用有界熱啟動參數(shù)，量子算法可以在混合時(shí)間上實(shí)現(xiàn)平方加速。通過將采樣問題視為只有一個馬爾可夫鏈的模擬退火過程，通過分析有效譜間隙，我們證明了量子算法實(shí)現(xiàn)了平方加速。
3. 量子梯度估計(jì)（quantum gradient estimation）。我們將 Jordan 的量子梯度算法應(yīng)用于我們的量子算法，并給出嚴(yán)格的證明來限制由于梯度估計(jì)誤差引起的采樣誤差。
參考文獻(xiàn)
[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.
*博客內(nèi)容為網(wǎng)友個人發(fā)布，僅代表博主個人觀點(diǎn)，如有侵權(quán)請聯(lián)系工作人員刪除。
