mixing time | BriefGPT - AI 论文速递

关键词mixing time

搜索结果 - 30

用少量单比特测量来验证几乎所有的量子态
证明了可以通过 O (n^2) 单比特测量来认证几乎所有 n 比特目标态，包括具有指数电路复杂性的目标态，并通过建立一种新的与随机行走的混合时间相关的技术，将认证与目标态的混合时间相关联。
PDF3 months ago
Metropolis 调整的镜像 Langevin 算法在有约束空间快速采样
我们提出了一种名为 Metropolis-adjusted Mirror Langevin 算法的新方法，用于从支持为紧凸集的分布中进行近似抽样。该算法在镜像 Langevin 算法（Zhang 等人，2020）的单步离散化所产生的马尔可夫
PDF7 months ago
缓慢混合过程的泛化能力
给出了关于由平稳和 phi 混合过程生成的数据的多个损失类的绑定一致性界限，其中混合时间（获得近似独立所需的时间）仅以加法方式进入样本复杂性。
PDFa year ago
关于光滑性和等周性下 Metropolis-Adjusted Langevin 算法混合的简单证明
本研究研究了在 $\mathbb {R}^d$ 上采样目标密度的 Metropolis-Adjusted Langevin 算法的混合时间，发现它在一定条件下的混合时间为 $O ((L\Upsilon)^{\frac12}/\psi_\mu
PDFa year ago
BART 简化版本混合时间下界
本文提出了 BART 的简化版本，并证明了 BART 的混合时间与数据点数量之间的联系。我们还表明 BART 使用的样本量需要随数据点数量增加而增加。
PDF2 years ago
针对良好条件分布的 Metropolized 采样方法下限
给出了使用两种蒙特卡罗采样方法（MALA 和 HMC）在良好条件的分布下性能的下界，并确定了每种方法的最短混合时间和松弛时间。该文还发现了跃点积分和 Chebyshev 多项式之间的新连接。
PDF3 years ago
未调整的 Hamilton 蒙特卡罗混合时间保证
该论文提出了一种上调和蒙特卡洛算法（uHMC），并提供了关于其马尔科夫链混合时间、总变差距离等指标的上限，证明了可在 log 级别的时间内实现精度为 ε 的近似目标分布，最终证明在两种模型下该算法的成功耦合可以实现这些上限。
PDF3 years ago
Metropolis-Adjusted Langevin 算法的最优维度依赖
该文研究了非渐近情况下，基于新的技术 ─ Metropolis 调整的投影特征，将 MALA 算法的分析简化到 Langevin SDE 分析领域，从而证明了在一定条件下，MALA 算法得到的混合时间为 O (d^(1/2))
PDF4 years ago
受限高斯 Oracle 的结构化对数凸采样
该研究论文讨论了如何使用结构化的 logconcave 样本算法来采样复合密度和 logconcave 有限和，使用近端点方法启发的降维框架来改善问题条件的相关性，并提出了一种获取大量梯度查询乘数的简单算法。
PDF4 years ago
坐标 Hit-and-Run 的混合时间
研究了 $n$ 维凸体上的随机游走的混合时间，得到了一个多项式上界，并得出该问题一直存在的疑问，即坐标 Hit-and-Run 是否具有多项式混合时间。
PDF4 years ago
带有马尔可夫数据的最小二乘回归：基本限制和算法
研究了最小二乘线性回归的问题，其中数据点依赖于并从马尔可夫链中采样。在不同的噪声设置下，建立了关于底层马尔可夫链混合时间 $\tau_{mix}$ 的尖锐信息理论极小值下界来解决此问题。我们发现，与独立数据的优化相比，具有马尔可夫数据的优化
PDF4 years ago
异步 Q 学习的样本复杂度：更精确的分析和降低方差
该研究通过异步 Q-learning 算法，在马尔科夫决策流程中的样本轨迹中学习最优动作价值函数，给出了基于 L∞的样本复杂度分析及等式组，并在此基础上提出一种新的方差缩减技术，进一步提高了算法的效率。
PDF4 years ago
Metropolized Hamiltonian Monte Carlo 的对数平滑梯度集中性与更紧致的运行时
通过基于梯度范式的均值紧密集中证明了 Metropolized Hamiltonian Monte Carlo 算法在从强 logconcave 分布中进行采样方面的状态最前沿，通过介绍不同于先前文献的限制和新的降低技术，我们提出了高精度混
PDF4 years ago
高阶 Langevin 拓扑在 Markov Chain Monte Carlo 算法中的加速
提出使用三阶 Langevin 动力学的马尔科夫链蒙特卡罗算法，用于采样具有对数凹和平滑密度函数的分布，并在广义线性模型下证明其结果仅需满足梯度的 Lipschitz 条件
PDF5 years ago
MM多步梯度法对 Metropolized Hamiltonian Monte Carlo 的快速混合优势
本文研究 Hamiltonian Monte Carlo 算法及其变种 Metropolized HMC 在连续空间中从光滑概率密度函数中提取样本的能力，并提供了关于混合时间的理论证明和分析。
PDF5 years ago
估计遍历马尔可夫链的混合时间
研究了如何从 1 条路径中估计任意遍历有限状态 Markov 链的混合时间，引入了假谱间隙的概念，并构建了全经验置信区间，将精度优化至多项式依赖的最小稳态概率和假谱间隙。
PDF5 years ago
通过马尔可夫链浓度推导强化学习的遗憾界
针对有 $S$ 个状态、$A$ 个行动、混合时间参数 $t_{mix}$ 的均匀遍历马尔可夫决策过程，在简单的乐观算法下，$T$ 步后 $\tilde {O}(\sqrt {t_{mix} SAT})$ 的遗憾度可推导出，这些界限是所有给定
PDF6 years ago
对数凹采样：Metropolis-Hastings 算法速度快
研究了如何从强对数凹密度分布中进行采样，并证明了使用 Metropolis-adjusted Langevin 算法（MALA）混合时间的非渐近上界。结果表明 MALA 与未调整的 Langevin 算法（ULA）相比，使用接受 - 拒绝步
PDF6 years ago
近似计算可逆马尔可夫链的平稳分布
本文研究马尔可夫链的状态下的稳态概率，并提出一种简单的随机近似算法，以突破小稳态概率难以求解的难题，基于这种方法，可以有效地减少复杂度和计算时间。
PDF7 years ago
基于多面体的快速 MCMC 采样算法
该研究提出并分析了两种新的 MCMC 抽样算法，即 Vaidya walk 和 John walk，用于从多面体上生成样本。其中提出的 Vaidya walk 算法的混合时间比过去的 Dikin walk 的混合时间少得多，混合时间上界为
PDF7 years ago