Jun, 2020

IDEAL：非精确分散加速增广拉格朗日算法

PDF
TL;DR提出了一个在分散优化设置下设计原始方法的框架，该框架适用于局部函数光滑且强凸。通过近似解决由加速增广拉格朗日方法引起的一系列子问题，从而提供了一种演导出几个著名的分散算法的系统方法。当与加速梯度下降相结合时，我们的框架会产生一种新的原始算法，其收敛速度是最优的，并且与最近确定的下限相匹配。我们提供实验结果，证明了拟议算法在高度病态问题上的有效性。
发现论文，激发创造
  • 非凸优化及非线性约束问题的不精确增广 Lagrangian 框架

    本研究提出了一种实用的不精确增广拉格朗日方法（iALM）用于具有非凸问题和非线性约束，这种方法可以在计算复杂度上符合理论结果。

    Jun, 2019

  • 分布式优化加速：基于原始对偶视角的局部步骤

    在分布式机器学习中，有效地进行具有不同数据分布的多个代理的训练面临着重大挑战。本研究解决了分布式优化问题中的集中式和分散式设置，并提出了一种基于原始对偶方法的新方法，即（加速）梯度上升的多随机梯度下降（GA-MSGD），它自然地融合了本地更新，实现了线性收敛，并且几乎达到了最优的通信复杂性。

    Jul, 2024

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

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

    Jun, 2014

  • 基于原始对偶框架的去中心化随机优化

    本文提出了一种基于原始 - 对偶框架的分布式优化算法，无需使用难以构建的双重随机混合矩阵，通过维护对偶变量来跟踪相邻节点之间的差异，使用这种方法构建的分布式算法比采用梯度跟踪的算法具有更好的性能。

    Dec, 2020

  • 精确增广拉格朗日与随机迭代草图的受限最优化

    本篇研究开发了一种自适应的非精确牛顿法，通过使用随机迭代草图求解器不精确地求解拉格朗日牛顿系统，并在精确增广拉格朗日优势函数上执行线搜索以选择适当的步长，以控制随机求解器的精度和惩罚参数，以确保不精确的牛顿方向是精确增广拉格朗日的下降方向，从而全局近乎确定地收敛，并表明在本地可采用单位步长，因此该方法表现出局部线性收敛。

    May, 2023

  • 用于解决线性约束光滑非凸组合优化问题的不精确近端加速增广 Lagrangian 方法的迭代复杂度

    本文提出和建立了一种非精确的近端加速增广 Lagrange (IPAAL) 方法，用于解决线性约束平滑非凸复合优化问题的迭代复杂度，并证明了 IPAAL 方法在大多数 ACG 迭代中产生一个近似稳定解决方案。

    Jun, 2020

  • 一种加速线性化交替方向乘子法

    提出一种新颖的框架 AADMM，用于加速线性化交替方向乘子法 (ADMM)，对于一类具有线性约束的凸复合优化问题，AADMM 的收敛速度比线性化 ADMM 更快，而且当相应的鞍点问题有解时，AADMM 能够处理无边界的可行域，并提出了一种回溯算法来提高实际性能。

    Jan, 2014

  • 并行分裂快速近端线性交替方向乘子方法

    提出快速近端改进增广拉格朗日方法 Fast PALM 和快速近端交替方向乘子方法 Fast PL-ADMM-PS 用于解决凸规划问题，成果表明与传统方法相比，算法具有更好的收敛速度和迭代复杂度.

    Nov, 2015

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

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

    Sep, 2019

  • 线性约束非凸优化的乘子近端交替方向法

    本文提出了一种新的 proximal ADMM 算法，使用平滑后的原始迭代的序列并在每次迭代时向增广拉格朗日函数中引入一个二次近似项。该算法的迭代收敛到这个问题的一个站点，特别是当目标函数是二次函数时，证明算法的线性收敛性。

    Dec, 2018