寻找局部极小值点的双时间尺度外推法
本文研究了解决两个函数之和的最小值问题的外推梯度方法,证明了在 Kurdyka-Lojasiewicz 假设下,该方法得到的序列收敛于问题的临界点并具有有限长度。该分析拓展到两个函数均为凸函数的情况,并证明了其次线性收敛率。此外,我们展示了将小型 prox 复杂度结果应用于此方法的方法。这个方法提供了一个机会来描述一种精确的线搜索方案,用于 proximal 分解方法。我们提供了实现这种方案对于一范数规则化最小二乘问题的细节,并展示了数值结果,这些结果表明将非加速方法与精确线搜索相结合可能是一个有竞争力的选择。
Sep, 2016
提出了一种新的 MinMax 优化算法家族,它利用早期迭代所观察到的梯度数据的几何信息,以在后期执行更具信息性的额外梯度步骤,从而自适应地检测问题是否光滑。
Oct, 2020
我们提出了自适应的、无需线搜索的二阶方法,以最优收敛速度解决凸凹最大最小问题,通过自适应步长,我们的算法采用简单的更新规则,每次迭代仅需解一个线性系统,消除了线搜索和回溯机制的需求,具体而言,我们基于乐观法则并将其与二阶信息合理地结合,与常见的自适应方案不同的是,我们递归地将步长定义为梯度范数和乐观更新中的预测误差的函数,我们首先分析了一种方案,其中步长需要知道 Hessian 的 Lipschitz 常数,在额外假设梯度连续 Lipschitz 的情况下,我们通过局部跟踪 Hessian 的 Lipschitz 常数并确保迭代保持有界,进一步设计了一个无需参数的版本,我们还通过将其与现有的二阶算法进行比较来评估我们算法的实际性能。
Jun, 2024
本研究通过调整双步长外推梯度算法的探索步骤与更新步骤的时间尺度,解决了使用随机梯度时基本版外推梯度算法的发散问题,并在误差界条件下推导出了尖锐的收敛速率。
Mar, 2020
本文提出了一种基于加速的近端点方法和最小值近端步求解器的算法,其梯度复杂度为 O(kappa_x kappa_y^0.5),匹配了已有的最优下界,可用于解决强凸强凹、凸凹、非凸强凹和非凸凹函数的问题。
Feb, 2020
提出了一种用于解决两时间尺度优化问题的新方法,通过利用平均化步骤改善算子的估计,消除了主要变量之间的直接耦合,从而大大加快了收敛速度,并在强凸性、凸性、Polyak-Lojasiewicz 条件和一般非凸性等各种情况下改进了传统两时间尺度随机逼近算法的复杂性,该算法在强化学习中表现出色,超越或与现有的最先进方法相匹配,并通过强化学习中的数值模拟验证了理论结果。
May, 2024
本文提出了一种针对非凸优化的简化方法,通过该方法可将寻找稳态的算法转变为寻找局部极小值的算法,并将海森矩阵向量积计算替换为仅使用梯度计算,此方法在随机和确定性设置下均可应用且不会影响算法的性能表现。将此方法应用于现有算法,可以将 Natasha2 转变为一阶方法而不影响性能,亦可以将 SGD,GD,SCSG 和 SVRG 转换为寻找近似局部极小值的算法,表现优于已知的一些最佳结果。
Nov, 2017