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