自适应一阶优化方法的收敛性:近端梯度和交替最小化算法
通过对于凸最小化问题的自适应方法的最新进展的利用,本文提供了一种无需线搜索的近端梯度下降框架,用于全局化收敛于流行的步长选择,如 Barzilai-Borwein 和一维 Anderson 加速。该框架可以处理梯度可微函数只具有局部 Holder 连续性的问题。我们的分析不仅包含但也改进了现有结果,并以数值证据来证明快速步长选择和自适应方法之间的协同作用。
Apr, 2024
本文探讨了凸优化中的两个基本一阶算法,梯度下降法(GD)和近端梯度法(ProxGD)。我们着重于通过利用光滑函数的局部曲率信息,使这些算法完全自适应。我们提出了基于观察到的梯度差异的 GD 和 ProxGD 的自适应版本,因此没有额外的计算成本。此外,我们证明了方法的收敛性,仅需假设梯度在局部利普希茨连续。此外,所提出的版本允许使用比 [MM20] 最初建议的更大的步长。
Aug, 2023
通过分析,我们展示了对于凸问题,自适应的近端梯度方法不受传统的 Lipschitzian 假设的限制。我们的分析揭示了一类无需线搜索的方法仍然在纯粹的局部 Hölder 梯度连续性下收敛,特别是连续可微分的半代数函数。为了解决局部 Lipschitz 连续性的缺失,流行的方法围绕着 ε- 预测器和 / 或线搜索程序。相反,我们利用 Hölder 不等式,而不需要任何近似,同时保持自适应方案的无需线搜索的特性。此外,我们在先验地不了解局部 Hölder 常数和 Hölder 连续性的阶的情况下,证明了完全序列的收敛性。在数值实验中,我们将其与基准方法在涵盖局部和全局 Hölder 设置的各种机器学习任务中进行比较。
Feb, 2024
本文提出了 AdaACSA、AdaAGD + 等新的自适应一阶优化算法,以加速受限制的凸优化问题中的收敛速度,同时针对平滑和不平滑函数,实现几乎最优的收敛速率;同时,通过自动调整每个坐标学习率,这些算法不需要固定事先知道目标函数的参数化,是针对限制优化的真正加速 Adagrad 方法之一。此外,本文提出了适用于无限制优化和单调算子的自适应方法,并附有具体的算法实现。
Jul, 2020
本文提出了一个新的优化方法 PPG,它可以解决很多可以表示为许多可微分和许多不可微分的凸函数总和的最小化问题,并放宽了不可微分函数之间的限制,同时还引入了称为 S-PPG 的随机变异方法。这些方法具有处理大量不可微分,不可分离函数的能力,并且可以以快速的速度进行收敛。
Aug, 2017
本文旨在从理论和实证角度分析适应性梯度算法在解决非凸非凹极小极大问题中的性能,并提出了一种名为乐观阿达格勒的自适应变体算法,证明了非凸非凹极小极大优化的自适应复杂性,并在生成对抗网络培训中显示出优越性能。
Dec, 2019
研究零阶算法求解非凸最小最大问题在确定性和随机设置下的紧密线性约束,为确定性和随机设置下求解非凸凹最小最大问题提出两种单环算法,即零阶原始 -- 对偶交替投影梯度(ZO-PDAPG)算法和零阶正则化动量原始 -- 对偶投影梯度算法(ZO-RMPDPG),其迭代复杂度被证明为 Ο(ε^(-2))(非凸凹最小最大问题)和 Ο(ε^(-4))(非凸凹最小最大问题),在确定性设置下,持有 ε- 稳定点,并且在随机设置下,迭代复杂度分别为 Ο̃(ε^(-3)) 和 Ο̃(ε^(-6.5))。据我们所知,它们是第一个能够解决确定性和随机设置下的非凸凹最小最大问题的零阶算法,并具有迭代复杂度保证。
Jan, 2024
本文研究了一类非光滑的分散式多智能体最优化问题,该代理旨在最小化局部强凸光滑组成部分和一个共同的非光滑项。我们提出了一个通用的原始对偶算法框架,统一了许多现有的最先进的算法。我们在非光滑项存在的情况下,证明了所提出的方法向确切解的线性收敛。此外,对于更一般的具有代理特定非光滑术语的问题类,我们展示了使用光滑和非光滑部分的梯度和临界映射的算法类别的线性收敛在最坏的情况下无法实现。我们进一步提供了一个数字反例,展示了某些最先进的算法如何在强凸目标和不同的局部非光滑项的情况下无法线性收敛。
Sep, 2019
本文考虑了一种基于近似算子的新型 Primal-Dual 算法及其收敛性,证明了比以前更弱的步长条件下可以收敛,证明了该步长条件是重要的,也将其应用到了分布式 PG-EXTRA 算法并导出了最弱的收敛条件。
Nov, 2017
本文介绍一种新的分布式优化问题的近端 - 梯度算法,用于处理包含平滑和非平滑项的组合目标,我们提出的新算法与以前的算法相比具有一些优势,例如不需要协调步长和可得到线性收敛。
Apr, 2017