Oct, 2020

利用黎曼随机算法解决半定规划问题

PDF
TL;DR基于 Langevin 扩散，提出一种新算法，在球面乘积流形上进行非凸优化和采样，并与 Burer-Monteiro 方法一起，应用于求解具有对角限制的半定规划问题。该算法在有限次迭代中生成 Gibbs 分布，并在 Kullback–Leibler 散度中保证渐进精度，其迭代次数呈多项式级别增长。与结果相结合，我们提供了全局最优性性保证，即使是存在鞍点和局部最小值的问题，算法仍能近似于全局最优解。
langevin diffusionnon-convex optimizationkullback--leibler divergenceburer--monteiro approachsemidefinite program
发现论文，激发创造
  • 通过凸优化分析 Langevin Monte Carlo

    该论文提出了新的调整 Langevin 算法的洞见，并表明该方法可以被公式化为定义在阶为 2 的 Wasserstein 空间上的目标函数的一阶优化算法。

    Feb, 2018

  • 非光滑对数凹情况下的 Langevin Monte Carlo 算法

    研究 Langevin Monte Carlo 算法在凸函数情况下的收敛性，其中潜在函数在定义域上是全局 Lipschitz 并且通常是任意凸集合上有限数量仿射函数的最大值，与大多数现有工作不同的是潜在函数没有被假设为梯度 Lipschitz。

    Jan, 2021

  • 基于 Langevin 动力学的非凸优化算法的全局收敛性

    本文提出了强化的 Langevin dynamics 算法和分析框架，理论证明了全局收敛性，能在各自的梯度复杂度内接近极小值。

    Jul, 2017

  • 弱条件下的驯服 Langevin 采样

    通过采样不满足对数凹条件且仅具有弱耗散性的分布来解决深度学习中常见的不满足标准 Lipschitz 光滑性要求的问题，该采样问题要求考虑目标分布满足对数索伯勒夫或某种柯西不等式以及局部 Lipschitz 光滑性假设，通过引入一种与目标分布的增长和衰减特性相关的驯服方案，提供了关于 Kullback-Leibler（KL）散度、总变分和 Wasserstein 距离与目标分布的显式非渐进保证的采样器。

    May, 2024

  • 基于先验扩散的 Langevin 算法在非对数凹采样问题中的改进分析

    在这篇论文中，我们研究了应用于满足对数 Sobolev 不等式（LSI）的目标分布的先验扩散技术，证明了改进的 Langevin 算法在不同步长计划下能够获得与维度无关的 KL 散度收敛，并通过构建插值的 SDE 和准确描述过阻尼 Langevin 动力学离散更新的方法提供了理论分析的证明。我们的研究结果展示了先验扩散对更广泛类别的目标分布的优势，并为开发更快的采样算法提供了新的见解。

    Mar, 2024

  • 近端 Langevin 算法：等周条件下的快速收敛

    该论文研究 Proximal Langevin Algorithm 在满足 log-Sobolev inequality 的条件下从概率分布中采样的收敛性，证明了该算法在 Kullback-Leibler divergence 下具有更优异的收敛速度，在 Renyi divergence 下也具有收敛性。

    Nov, 2019

  • 基于未调整 Langevin 算法的高维贝叶斯推断

    文章研究了如何使用基于 Langevin 随机微分方程的采样方法，对高维概率分布进行采样， 并通过 Wasserstein 距离和总变差距离获得收敛到平稳状态的非渐进界限。同时，对于测量和有界函数报告了平均均方误差和指数偏差不等式的界限，并提供了二分类回归的贝叶斯推断例证。

    May, 2016

  • Langevin Monte Carlo 与不准确梯度的用户友好保证

    本文研究了从已知平滑和强对数凹概率密度函数中采样的方法， 分析了基于过渡态随机游走的近似采样方法，并提出了几种保证误差的方法， 包括第一阶 Langevin Monte Carlo 算法的误差上界、误差上界和梯度评估不准确的情况， 以及二阶 Langevin Monte Carlo 算法利用 log 密度的海森矩阵的保证。

    Sep, 2017

  • 强对数凹分布的朗之万蒙特卡罗方法：随机中点重访

    本文针对具有强烈对数凹密度的平滑目标分布的采样问题进行探究，借助随机中点离散化方法，建立可计算的 Wasserstein-2 误差的上界，并基于中点离散化的 Langevin 扩散过程进行分析以明确其基本原理和提供有价值的见解，进而建立起更改进的上界以改进 Euler 离散化的 Langevin 扩散过程。

    Jun, 2023

  • Langevin MCMC 在 KL 散度下的收敛性

    研究 Langevin 扩散在采样、KL - 散度、强凸性、收敛速率等方面的应用，证明在目标密度是 L 光滑且 m 强凸的情况下，该扩散可以在几步内收敛于目标分布，同时揭示了在强凸性假设缺失时的收敛速率。

    May, 2017