Jun, 2024

随机牛顿近端外推法

PDF
TL;DR我们提出了一种新颖的随机牛顿近端外推方法，改进了过去的方法，并在更少的迭代次数内达到更快的全局线性速率和相同的快速超线性速率。
stochastic second-order methodshessian averaging schemeglobal linear ratestochastic newton proximal extragradient methodhybrid proximal extragradient (hpe) framework
发现论文，激发创造
  • 加速拟牛顿近端外推算法：用于平滑凸优化的更快速率

    本文提出了一种加速的拟牛顿近端外推（A-QPNE）算法来解决无约束光滑凸优化问题，证明了该方法能够实现收敛速度，并且通过蒙特罗 - 斯维特加速框架的变种来构建这个方法，并采用在线学习方法更新 Hessian 矩阵的近似，这个方法在一定范围内是优于 NAG 算法的.

    Jun, 2023

  • 随机近端梯度算法的收敛性

    本文基于凸优化中函数是光滑和非光滑组合的形式，证明了一种适用于大类凸优化问题的随机近端梯度算法收敛性质，其避免了平均化和理论研究中常见但实际中不一定满足的有界性假设，证明了一系列强、弱收敛性结果，并得到了期望意义下的 $O (1/n)$ 的有界性结果。

    Mar, 2014

  • 具有全局复杂度分析的实用不精确近端拟牛顿方法

    提出了一种稀疏优化的通用框架，使用了二阶信息和有限的 BFGS Hessian 逼近，通过坐标下降的方法解决问题，并对其全局收敛率进行了新颖的分析。

    Nov, 2013

  • 探索激进，更新保守：变步长缩放的随机极限梯度法

    本研究通过调整双步长外推梯度算法的探索步骤与更新步骤的时间尺度，解决了使用随机梯度时基本版外推梯度算法的发散问题，并在误差界条件下推导出了尖锐的收敛速率。

    Mar, 2020

  • 优化中的外推法：收敛性与复杂性

    本文研究了解决两个函数之和的最小值问题的外推梯度方法，证明了在 Kurdyka-Lojasiewicz 假设下，该方法得到的序列收敛于问题的临界点并具有有限长度。该分析拓展到两个函数均为凸函数的情况，并证明了其次线性收敛率。此外，我们展示了将小型 prox 复杂度结果应用于此方法的方法。这个方法提供了一个机会来描述一种精确的线搜索方案，用于 proximal 分解方法。我们提供了实现这种方案对于一范数规则化最小二乘问题的细节，并展示了数值结果，这些结果表明将非加速方法与精确线搜索相结合可能是一个有竞争力的选择。

    Sep, 2016

  • 随机变分不等式问题的最优鲁棒平滑外推算法

    本文考虑了随机泛型不等式问题及其解决方案，利用局部随机平滑方案求解，并证明了该解决方案在平均意义下和几乎肯定意义下都能收敛到问题的解，同时也实现了 $1/k$ 的收敛速度。

    Mar, 2014

  • 非光滑、非凸问题的近距离引导随机次梯度方法

    本文介绍了一种基于随机投影次梯度方法的弱凸（即均匀逼近正则）非光滑非凸函数的算法，并通过简单证明证明这种方法与用于光滑非凸问题的随机梯度方法具有相同的收敛速度；这似乎是第一个针对弱凸函数类的随机次（或确定性）梯度法的收敛速度分析。

    Jul, 2017

  • 随机梯度下降与外推在非凸优化中的收敛性

    本文研究利用外推算法解决非凸优化问题的收敛性，并通过分析梯度下降和随机梯度下降算法证明外推可以加速算法的收敛速度。

    Jan, 2019

  • 面向噪声自适应、问题自适应（加速）随机梯度下降

    通过利用指数步长和随机线性搜索等技术，使得随机梯度下降算法适应不同噪声水平和问题相关的常数，可以在强凸函数的条件下，取得与理论最优相近的收敛速度，同时能够有效地处理噪声和数据不凸的情况。

    Oct, 2021

  • 使用 Polyak 动量的非凸随机复合优化

    该论文研究了在采用小型或有界批量大小时，在非凸设置中具有重要意义的随机近端梯度法，证明了该方法在非凸复合优化问题中达到最优的收敛速度，并且严格分析了 Polyak 动量在复合优化设置中的方差缩减效应，同时证明了在近似解决近端步骤的情况下，该方法仍然收敛，并通过数值实验验证了我们的理论结果。

    Mar, 2024