带受限高斯序列预言的复合对数凹采样
该研究论文讨论了如何使用结构化的 logconcave 样本算法来采样复合密度和 logconcave 有限和,使用近端点方法启发的降维框架来改善问题条件的相关性,并提出了一种获取大量梯度查询乘数的简单算法。
Oct, 2020
本文提出了一种基于 Metropolis-Hastings 框架的新算法,用于采样具有复合非平滑密度的分布,并针对这种新算法证明了在至多 $O (d log (d/ε))$ 次迭代内将混合到距目标密度不超过 Eps 的总变差距离,而该方法的一个关键点在于使用了可用于大类非平滑函数 G 的一种新的近端基于提议分布的方法。
Oct, 2019
本文考虑了具有非光滑目标函数和具有非光滑潜势(负对数密度)的凸优化和对数凹取样问题,并研究了两个特定的设置,其中凸目标 / 潜势函数可以是半光滑的,也可以是复合形式,作为半光滑分量的有限和。为了克服非光滑性带来的挑战,我们的算法在优化和取样上使用了两种强大的近端框架:优化的近端点框架和使用增广分布上的 Gibbs 取样的交替取样框架(ASF)。优化和取样算法的关键组成部分是通过正则化割平面法对近端映射的高效实现。我们在半光滑和复合的两种情况下建立了近端映射的迭代复杂性。此外,我们还提出了一种适应性近端捆绑法用于非光滑优化。该方法是通用的,因为它不需要任何问题参数作为输入。此外,我们开发了一个类似于优化中近端映射的近端取样预测器,并使用一种新颖的技术(改进的高斯积分)建立了其复杂性。最后,我们将这个近端取样预测器和 ASF 结合起来,得到了一个在半光滑和复合设置中具有非渐近复杂性界限的马尔可夫链蒙特卡洛方法用于取样。
Apr, 2024
证明了通过多尺度构造和具有与 Wishart 矩阵类似的查询下界技术,可以在任何常数维度下通过块 Krylov 算法最优地采样具有强对数凹和对数平滑分布的分布,同时连接到高斯分布的具有误差的查询下界。
Apr, 2023
提出了一个支持各种投影选项的通用近端框架,基于凸紧致支撑体上定义的强对数凹分布进行采样,并与多种采样方法无缝集成,主要研究集中在约束采样的 Langevin 型采样算法,提供了 W1 和 W2 误差的非渐进上界,详细比较了这些方法在约束采样中的性能。
May, 2024
本文提出了一种新的随机组合减少方差的梯度算法来解决现有算法在算法设计中忽略凸性结构而导致的样本复杂度和实践问题,实验结果表明了该算法的有效性和效率。
Jun, 2018
本文提出一种使用归一化近端梯度求解多层组合优化问题的方法,其中包含一系列随机平滑映射,在嵌套随机方差约减的帮助下获得近似梯度,其期望样本复杂度为 O(ϵ^-3),在有限求和的情况下为 O(N+√Nϵ^-2),其中 N 是所有组合级别上的函数总数。与以前的方法相比,我们的总样本复杂度在组合级别数量上的依赖性是多项式的,而不是指数的。
Aug, 2019
本文提出了一种近似线性的多元常微分方程算法,用于解决样本采集问题,特别是针对 Hamiltonian Monte Carlo 的多维 logconcave 密度函数,拥有多项式对数深度。
Dec, 2018
本研究提出了应用于凸集内标准高斯分布抽样及高斯度量估计的随机算法,并证明它们在一般性成员查询模型下的可行性,其采样的时间复杂度为每个样本均摊 $O^*(n^2)$,比现有最先进算法快 $n$ 倍。在等周问题、平滑退火、避免变换到各向同性和快速随机行走等方面实现了改进。
Jun, 2013