非强凸函数的线性收敛离点条件梯度法
提出了一种改进的条件梯度方法来解决约束凸优化问题,针对多面体进行了相应的分析及优化,降低了每次迭代时的计算及内存开销,并在实际中通过对图路径、二分图完全匹配、结构预测任务中的边际分布等多样化问题进行测试并呈现出其卓越表现。
May, 2016
提出了一种混合条件梯度方法,可用于在多面体 P 上最小化平滑凸函数,该方法结合了 Frank-Wolfe 算法和基于梯度的步骤,并通过保持迭代点为 P 的极端点的有限数量的稀疏凸组合,避免了向 P 投影的优点,实现了强凸函数的线性收敛。
May, 2018
本研究介绍了一种基于条件梯度算法的优化模型,可用于求解线性优化问题和非线性凸优化问题,并给出了一种基于此算法的在线凸优化算法,具有线性收敛速度和最优的遗憾保证。
Jan, 2013
本文研究了具有仿射约束的通用凸优化模板,提出了一种新的基于平滑和增广 Lagrangian 框架统一处理的条件梯度算法,证明了该方法在目标残差和可行性差距方面具有 O (1 / 根号 k) 的收敛速率,特别适用于各种半定规划应用。
Jan, 2019
本文研究了解决光滑的非强凸约束优化问题的一些一阶方法的收敛率,提供了一些松弛的强凸条件并证明了它们对于多种一阶方法的线性收敛是足够的,最后证明了所提出的松弛强凸条件涵盖了求解线性系统、线性规划和线性约束凸问题的重要应用。
Apr, 2015
研究表明,当在具有 Lipschitz 梯度的强凸函数上应用梯度下降算法时,其收敛速度由函数的条件数决定且算法收敛速度类似于一个带有离开步骤的 Frank-Wolfe 算法。在对无约束情况的良好扩展中,算法的收敛速度由函数的条件数及多面体的某个特定条件数的乘积决定。本研究为这种类型多面体调整提出了新的方法,并且认为之前的相关方法是等价的,并可通过多面体的参数进行统一,从而实现算法的线性收敛。此外,对于凸二次目标,研究表明收敛速度取决于相应缩放多面体的条件数。
Dec, 2015
本研究针对具有凸 - 凹鞍点问题的优化进行了研究,证明了即使 $f$ 不强凸,使用一般的原始 - 对偶梯度方法也可以实现线性收敛,并给出了具有有限和结构的凸 - 凹鞍点问题的原始 - 对偶随机方差减少梯度方法的分析。
Feb, 2018
我们开发了一种梯度下降法的新次优性边界,该边界依赖于优化路径中的目标条件,而不是全局最坏情况下的常数。我们的证明关键在于方向平滑性,这是一种梯度变化的度量,我们用它来开发上界约束。通过求解隐式方程来最小化这些上界约束,我们展示了这些方程对于凸二次函数是容易解决的,并为两种传统步长提供了新的保证。对于一般函数,我们证明了 Polyak 步长和归一化梯度下降法尽管不使用方向平滑性的任何知识,但能够获得快速的路径相关性。逻辑回归上的实验证明,我们的收敛保证比基于 L 平滑性的传统理论更紧致。
Mar, 2024
本文介绍了一种新的非均匀光滑条件下的优化方法,并开发出一种简单但有效的分析技术来限制沿轨迹的梯度,从而获得更强的凸优化和非凸优化问题的结果。我们通过这种新方法证明了(随机)梯度下降和 Nesterov 加速梯度法在这种一般的光滑条件下的收敛率,而不需要梯度剪裁,并允许在随机场景中的有界方差的重尾噪声。
Jun, 2023