NeurIPS2022量子算法用于采样对数凹分布和估计归一化

　　导读
　　本文是NeurIPS2022入选论文QuantumAlgorithmsforSamplingLogConcaveDistributionsandEstimatingNormalizingConstants〔1〕的解读。该方法对数凹采样（logconcavesampling）在机器学习、物理、统计等领域有着诸多应用。本文基于朗之万扩散（Langevindiffusion）设计了新的量子算法，用于采样对数凹分布和估计归一化常数，相比最好的经典算法对于精度（），维度（d），条件数（）等参数达到了多项式级加速。本文作者包括：AndrewM。Childs（马里兰大学），李彤阳（北京大学），刘锦鹏（加州大学伯克利分校西蒙斯研究所），王春昊（宾州州立大学）和张睿哲（德州大学奥斯汀分校）。
　　论文地址：https：arxiv。orgabs2210。06539
　　01hr问题介绍
　　从给定的分布函数采样是一个基础的计算问题。例如，在统计中，样本可以确定置信区间或探索后验分布。在机器学习中，样本用于回归和训练监督学习模型。在优化中，来自精心挑选的样本分布可以产生接近局部甚至全局最优的点。本文考虑的问题是对数凹采样（logconcavesampling），这个问题涵盖了许多实际应用例子，例如多元高斯分布和指数分布。与之相关的一个问题是估计对数凹分布的归一化常（normalizingconstant），这个问题也有许多应用，例如配分函数（partitionfunction）的估计〔2〕。更多相关工作见参考文献〔3，4，5，6〕。
　　02hr问题模型
　　给定一个凸函数R，且f是Lsmooth和convex的。我们定义条件数。我们希望从分布函数进行采样，这里是正则化常数。给定（0，1），对数凹采样：输出一个随机变量满足分布，使得；归一化常数估计：输出一个随机变量，使得以至少23的概率满足。
　　03hr主要贡献
　　我们设计了新的量子算法，对于采样对数凹分布和估计正则化常数两个问题，对比经典算法在复杂度上实现了多项式级加速。
　　定理1（对数凸采样）给定一个对数凹分布，存在量子算法输出一个随机变量满足分布，使得：，这里是Wasserstein2范数，对于量子访问oracle的查询复杂度为；或，这里是全变差距离（totalvariationdistance），对于量子梯度oracle的查询复杂度为；若初始分布满足热启动条件，则复杂度为。
　　定理2（归一化常数估计）存在量子算法输出一个随机变量，使得以至少23的概率满足，对于量子访问oracle的查询复杂度为；或对于量子梯度oracle的查询复杂度为；若有一个热的初始概率分布（warmstart），则复杂度为。
　　另外，这个任务的量子查询复杂度的下界是。
　　我们在表1和表2总结了我们的结果和先前经典算法复杂度的对比。
　　04hr技术改进
　　我们开发了一种系统的方法来研究量子游走混合（quantumwalkmixing）的复杂度，并揭示了对于任何可逆的经典马尔可夫链，只要初始分布满足热启动条件，我们就可以获得混合时间（mixingtime）的平方加速。特别地，我们将量子行走和量子退火（quantumannealing）应用于朗之万动力学并实现多项式量子加速。下面简单介绍我们的技术贡献。
　　1。量子模拟退火（quantumsimulatedannealing）。我们用于估计归一化常数的量子算法结合了量子模拟退火框架和量子平均值估计算法。对于每种类型，根据朗之万动力学（随机游走），我们构建了相应的量子游走。重要的是，随机游走的谱间隙在相应的量子游走的相位间隙中被放大为原先的平方。这让在给定足够好的初始状态的情形，我们使用类似Grover算法的过程来产生稳定分布状态。在退火框架中，这个初始状态就是前一个马尔可夫链的稳定分布状态。
　　2。有效谱间隙（effectivespectralgap）。我们展示了如何利用热启动的初始分布来实现量子加速用于采样。即使谱间隙很小，热启动也会导致更快的混合。在量子算法中，我们将有效谱间隙的概念推广到我们更一般的采样问题。我们表明使用有界热启动参数，量子算法可以在混合时间上实现平方加速。通过将采样问题视为只有一个马尔可夫链的模拟退火过程，通过分析有效谱间隙，我们证明了量子算法实现了平方加速。
　　3。量子梯度估计（quantumgradientestimation）。我们将Jordan的量子梯度算法应用于我们的量子算法，并给出严格的证明来限制由于梯度估计误差引起的采样误差。
　　参考文献
　　〔1〕AndrewM。Childs，TongyangLi，JinPengLiu，ChunhaoWang，andRuizheZhang，QuantumAlgorithmsforSamplingLogConcaveDistributionsandEstimatingNormalizingConstants，toappearinNeurIPS2022。
　　〔2〕RongGe，HoldenLee，andJianfengLu，Estimatingnormalizingconstantsforlogconcavedistributions：Algorithmsandlowerbounds，STOC2020。
　　〔3〕XiangCheng，NiladriS。Chatterji，PeterL。Bartlett，andMichaelI。Jordan，Underdampedlangevinmcmc：Anonasymptoticanalysis，COLT2018。
　　〔4〕YinTatLee，RuoqiShen，andKevinTian，LogsmoothgradientconcentrationandtighterruntimesformetropolizedHamiltonianMonteCarlo，COLT2020。
　　〔5〕RuoqiShenandYinTatLee，Therandomizedmidpointmethodforlogconcavesampling，NeurIPS2019。
　　〔6〕KeruWu，ScottSchmidler，andYuansiChen，MinimaxmixingtimeoftheMetropolisadjustedLangevinalgorithmforlogconcavesampling，2021，arXiv：2109。13055。
　　图文刘锦鹏、李彤阳
　　PKUQUARKLab