本研究提出了应用于凸集内标准高斯分布抽样及高斯度量估计的随机算法,并证明它们在一般性成员查询模型下的可行性,其采样的时间复杂度为每个样本均摊 $O^*(n^2)$,比现有最先进算法快 $n$ 倍。在等周问题、平滑退火、避免变换到各向同性和快速随机行走等方面实现了改进。
Jun, 2013
本研究提出一种基于 Chebyshev cooling 并利用量子随机游走技术的量子算法,用于估算多维凸包的体积,比已知的经典算法要更快,同时还证明了量子算法所需的查询次数。
Aug, 2019
我们通过使用鞍点常数和等熵恒量来证明了,具有远离均匀分布的概率分布的 Cheeger 常数在对数凹度量类中的限制为 $ n^{1/4}$,并使用该限制改进了 Poincaré 常数、Lipschitz 浓度常数和球行进算法的性能估计。
Dec, 2016
该研究论文讨论了如何使用结构化的 logconcave 样本算法来采样复合密度和 logconcave 有限和,使用近端点方法启发的降维框架来改善问题条件的相关性,并提出了一种获取大量梯度查询乘数的简单算法。
Oct, 2020
Riemannian Hamiltonian Monte Carlo 在流形上的收敛性以及在流形上采样问题和计算体积问题中的应用。
Oct, 2017
提供了一种高效的样本多项式时间估计器,用于高维球形高斯混合模型中,从而显着降低了时间和样本复杂度,并且还提出了针对一维混合模型的简单估计器及一种更快的算法,用于从一组分布中选择密度估计。
Feb, 2014
本研究探讨高维几何对象的求并集体积问题。本文给出了一个快速的 FPRAS 算法,可以有效地逼近 Klee's measure problem 和 hypervolume indicator,并能够逼近由弱成员资格证明给出的凸体的并集体积。同时,作者还探讨了高维几何对象的交集计算问题,并证明了其 #P 难度。
Sep, 2008
证明了通过多尺度构造和具有与 Wishart 矩阵类似的查询下界技术,可以在任何常数维度下通过块 Krylov 算法最优地采样具有强对数凹和对数平滑分布的分布,同时连接到高斯分布的具有误差的查询下界。
Apr, 2023
本文提出了一种算法来从具有复合密度的分布中采样,这些密度由具有良好条件数的 $f$ 和凸(但可能不光滑)函数 $g$ 构成,这组密度通过受限高斯 oracle 的抽象来推广限制为凸集的约束。该算法是概念上简单的,实验表明其可显著优于 hit-and-run 算法用于采样(非对角线)高斯分布的正定方向区域限制。
Jun, 2020
在 d 维空间中,从标准正态分布中选择 n 个独立的随机点,得到凸包 K_n,称为高斯随机多面体。我们证明,K_n 的体积和面数满足中心极限定理,解决了该领域一个著名的猜想。
Oct, 2006