Apr, 2024

优化和采样的近端预言机

PDF
TL;DR本文考虑了具有非光滑目标函数和具有非光滑潜势（负对数密度）的凸优化和对数凹取样问题，并研究了两个特定的设置，其中凸目标 / 潜势函数可以是半光滑的，也可以是复合形式，作为半光滑分量的有限和。为了克服非光滑性带来的挑战，我们的算法在优化和取样上使用了两种强大的近端框架：优化的近端点框架和使用增广分布上的 Gibbs 取样的交替取样框架（ASF）。优化和取样算法的关键组成部分是通过正则化割平面法对近端映射的高效实现。我们在半光滑和复合的两种情况下建立了近端映射的迭代复杂性。此外，我们还提出了一种适应性近端捆绑法用于非光滑优化。该方法是通用的，因为它不需要任何问题参数作为输入。此外，我们开发了一个类似于优化中近端映射的近端取样预测器，并使用一种新颖的技术（改进的高斯积分）建立了其复杂性。最后，我们将这个近端取样预测器和 ASF 结合起来，得到了一个在半光滑和复合设置中具有非渐近复杂性界限的马尔可夫链蒙特卡洛方法用于取样。
convex optimizationnon-smooth objective functionlog-concave samplingproximal frameworksmarkov chain monte carlo
发现论文，激发创造
  • 带受限高斯序列预言的复合对数凹采样

    本文提出了一种算法来从具有复合密度的分布中采样，这些密度由具有良好条件数的 $f$ 和凸（但可能不光滑）函数 $g$ 构成，这组密度通过受限高斯 oracle 的抽象来推广限制为凸集的约束。该算法是概念上简单的，实验表明其可显著优于 hit-and-run 算法用于采样（非对角线）高斯分布的正定方向区域限制。

    Jun, 2020

  • 受限高斯 Oracle 的结构化对数凸采样

    该研究论文讨论了如何使用结构化的 logconcave 样本算法来采样复合密度和 logconcave 有限和，使用近端点方法启发的降维框架来改善问题条件的相关性，并提出了一种获取大量梯度查询乘数的简单算法。

    Oct, 2020

  • 紧支持上的对数凹采样：一个通用的近端框架

    提出了一个支持各种投影选项的通用近端框架，基于凸紧致支撑体上定义的强对数凹分布进行采样，并与多种采样方法无缝集成，主要研究集中在约束采样的 Langevin 型采样算法，提供了 W1 和 W2 误差的非渐进上界，详细比较了这些方法在约束采样中的性能。

    May, 2024

  • 自适应平滑算法用于凸复合优化

    我们引入自协调平滑的概念，用于最小化两个凸函数的和：第一个是光滑的函数，第二个可以是不光滑的函数。我们的方法自然地从称为部分平滑的平滑近似技术中得出。我们的方法的重点在于所得问题结构的自然特性，它为我们提供了一个变量度量选择方法和一条特别适合于近端牛顿类型算法的步长选择规则。另外，我们有效地处理不光滑函数推动的特定结构，例如 L1 正则化和组套索惩罚。我们证明了两种算法的局部二次收敛速度：Prox-N-SCORE，即近端牛顿算法和 Prox-GGN-SCORE，即近端广义高斯牛顿（GGN）算法。Prox-GGN-SCORE 算法突出了一种较为重要的近似过程，有助于显著降低与逆 Hessian 相关的大部分计算开销。此近似过程对于超参数机器学习模型和小批量设置非常有用。对合成数据集和真实数据集的数值实验证明了我们方法的效率和优越性。

    Sep, 2023

  • 一种用于非光滑复合势函数的高效取样算法

    本文提出了一种基于 Metropolis-Hastings 框架的新算法，用于采样具有复合非平滑密度的分布，并针对这种新算法证明了在至多 $O (d log (d/ε))$ 次迭代内将混合到距目标密度不超过 Eps 的总变差距离，而该方法的一个关键点在于使用了可用于大类非平滑函数 G 的一种新的近端基于提议分布的方法。

    Oct, 2019

  • 基于随机模型的弱凸函数最小化

    本文提出一族算法通过简单的随机模型样本和优化方法，成功的减少了目标函数。我们展示出，合理的近似质量和模型的正则性下，此类算法将自然的稳定度衡量推向 0，该衰减速度为 O (k^(-1/4))，基于此原理，我们为随机的近端子梯度法，近端次梯度法以及规则化的高斯牛顿法等提供了第一个复杂性保证。

    Mar, 2018

  • 优化复合目标的紧密复杂度界

    通过使用分量函数的梯度和 prox oracles 提供了最小化 m 个凸函数平均值的复杂性的严格上下界；我们表明决定性和随机优化之间存在显着差距。对于光滑函数，我们表明在确定性和随机设置中，加速梯度下降 (AGD) 和 SVRG 的加速变体分别是最优的，并且梯度 Orcale 足以获得最佳速率。对于非光滑函数，通过接入 prox oracles 可降低复杂度，因此，我们提出基于平滑的最优方法，以改进仅使用梯度访问的方法。

    May, 2016

  • 对数拉普拉斯变换的算法特征及非欧几里得近端采样器

    本文介绍了一种针对非欧几里得几何体的高效采样算法，该算法通过 log-Laplace 变换提供正则化性质，这种采样器匹配现有的欧几里得采样器，并在凸优化等领域表现出色。

    Feb, 2023

  • 用于最小化复合函数的近端牛顿型方法

    该研究广义化了牛顿型方法以处理光滑函数的最小化，特别是一个包含简单近端映射的凸函数和一个非光滑函数的总和，在此基础上提出了近端牛顿型方法。研究表明，该方法即使在计算搜索方向不精确时，也能继承用于最小化光滑函数的牛顿型方法的理想收敛性质。该方法是许多针对生物信息学、信号处理和统计学习等问题量身定制的流行方法的特例，并且分析结果为其中一些方法提供了新的收敛结果。

    Jun, 2012

  • 一种随机复合非凸优化的混合随机优化框架

    提出一种新方法解决一类复合随机非凸优化问题，通过组合两种随机估计量形成混合估计量，将之应用于多种变体的随机梯度法中以达到最优的复杂度界限。

    Jul, 2019