Jul, 2015

一种平滑的原始对偶优化框架用于非光滑复合凸最小化

PDF
TL;DR本文介绍了一种新的一阶原始 - 对偶优化框架，利用平滑、加速和同伦等三个经典思想，实现了具有许多广泛应用的凸优化，达到了最佳的收敛效果，针对只包含非平滑函数的情况。同时提供了重新启动策略，大大提高了实际性能，并展示了与增广拉格朗日方法的关系以及如何利用严格收敛率保证来利用强凸目标。最后提供了两个实例验证，表明新的方法可以优于 Chambolle-Pock 和交替方向乘法算法等现有的算法。
primal-dual optimizationconvex optimizationconvergence guaranteessmoothingacceleration
发现论文，激发创造
  • 非光滑凸优化平滑原始 - 对偶坐标下降算法

    提出一种新的随机坐标下降方法，应用广泛，采用四种新颖的思想，包括平滑、加速、同伦、坐标下降和非均匀采样，具有迭代收敛保证，数值实验表明其优于现有算法。

    Nov, 2017

  • 最大结构非凸优化的原始 - 对偶平滑框架

    本文提出了一种基于原始 - 对偶平滑框架的方法，用于寻找一类非光滑非凸优化问题的近似稳态点，并通过两种方法，即先对偶后原始和先原始后对偶平滑方法分析了框架的原始和对偶梯度复杂度。通过一个新开发的非 Hilbertian 不精确加速近端梯度算法来解决一类（强）凸 - 凹鞍点问题，进一步改进了已有方法的最佳 oracle 复杂度，并讨论了其变体和扩展。

    Mar, 2020

  • 受限凸最小化问题的原始 - 对偶算法框架

    本文提出了一种原始 - 对偶算法框架，以获得近似解决方案来解决典型的约束凸优化问题，并严格描述了常见结构假设如何影响数值效率。通过选择双重平滑策略和中心点，我们的框架将分解算法、增广 Lagrange 以及交替方向乘子方法作为其特殊情况，并为所有迭代的原始目标残差和原始可行性间隙提供最优收敛速率。

    Jun, 2014

  • 一种通用的原始 - 对偶凸优化框架

    提出一种新的原始对偶算法框架，以解决约束的凸优化问题，具有优秀的收敛速度和更高效的计算方式。

    Feb, 2015

  • 用主 - 对偶次梯度法最小化一致凸函数

    讨论非欧几里得确定性和随机算法，解决强凸和一致凸的优化问题，提供算法性能的准确性界限，设计针对强或一致凸性参数的自适应方法：在总迭代次数 $N$ 固定的情况下，它们的准确度与最优算法的准确度相同，直到 $N$ 的对数因子。

    Jan, 2014

  • 一种条件梯度框架用于复合凸最小化及半定规划应用

    我们提出了一个基于条件梯度法的复合凸优化模板，该方法结合了平滑和同伦技术，在 CGM 框架下实现了最优的 O（1 /sqrt（k））收敛速度，并证明了在线性子问题具有加法或乘法误差时，同样的速率保持不变。此外，与相关工作相比，我们能够描述非平滑项为指示函数时的收敛性质。

    Apr, 2018

  • 基于拉格朗日法的非平滑非凸优化方法的开发

    本文中我们考虑在闭凸子集上最小化一个非光滑非凸的目标函数 $f (x)$，同时满足附加的非光滑非凸约束 $c (x) = 0$。我们开发了一个统一的框架来发展基于 Lagrangian 的方法，在每次迭代中通过某些子梯度方法对原始变量进行单步更新。这些子梯度方法被 “嵌入” 到我们的框架中，以黑盒更新原始变量的方式加以合并。我们证明了在温和条件下，我们提出的框架继承了这些嵌入子梯度方法的全局收敛性保证。此外，我们证明了我们的框架可以扩展到解决具有期望约束的约束优化问题。基于我们提出的框架，我们展示了一系列现有的随机子梯度方法，包括 proximal SGD、proximal momentum SGD 和 proximal ADAM，可以嵌入到基于 Lagrangian 的方法中。对深度学习任务的初步数值实验表明，我们提出的框架可以为非凸非光滑约束优化问题提供高效的 Lagrangian-based 方法变体，并具有收敛性保证。

    Apr, 2024

  • 具有线性收敛率的分散近端梯度算法

    本文研究了一类非光滑的分散式多智能体最优化问题，该代理旨在最小化局部强凸光滑组成部分和一个共同的非光滑项。我们提出了一个通用的原始对偶算法框架，统一了许多现有的最先进的算法。我们在非光滑项存在的情况下，证明了所提出的方法向确切解的线性收敛。此外，对于更一般的具有代理特定非光滑术语的问题类，我们展示了使用光滑和非光滑部分的梯度和临界映射的算法类别的线性收敛在最坏的情况下无法实现。我们进一步提供了一个数字反例，展示了某些最先进的算法如何在强凸目标和不同的局部非光滑项的情况下无法线性收敛。

    Sep, 2019

  • 超越凸性和 Lipschitz 梯度连续性的一阶方法及其在二次逆问题中的应用

    利用可适应性光滑函数的概念和 Bregman 基础的近端梯度方法，在解决具有复杂目标函数的非凸、非光滑最小化问题时，实现全局收敛。

    Jun, 2017

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

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

    Sep, 2023