Nov, 2017

Neon2: 通过一阶预言找到本地最小值

PDF
TL;DR本文提出了一种针对非凸优化的简化方法，通过该方法可将寻找稳态的算法转变为寻找局部极小值的算法，并将海森矩阵向量积计算替换为仅使用梯度计算，此方法在随机和确定性设置下均可应用且不会影响算法的性能表现。将此方法应用于现有算法，可以将 Natasha2 转变为一阶方法而不影响性能，亦可以将 SGD，GD，SCSG 和 SVRG 转换为寻找近似局部极小值的算法，表现优于已知的一些最佳结果。
non-convex optimizationlocal-minimum findinggradient computationsstochastic and deterministic settingsalgorithm performance
发现论文，激发创造
  • 通过随机嵌套方差缩减寻找局部最小值

    提出两个算法，其中一个利用随机嵌套方差降低算法能快速找到局部最小值， 算法在有限和一般随机非凸优化中的效果都优于现有算法，并进一步探索了目标函数的三阶光滑度加速优化的情况。

    Jun, 2018

  • Natasha 2：比 SGD 更快的非凸优化

    本文设计了一种随机算法，使用 O (ε^{-3.25}) 次反向传播来训练任何平滑神经网络到 ε- 近似局部极小值，并能够在不需要凸梯度下降的情况下，以速率 O (ε^{-3.25}) 找到任何平滑非凸函数的 ε- 近似局部极小值。

    Aug, 2017

  • 比梯度下降法更快地找到局部极小值

    本文介绍了一种非凸二阶优化算法，其时间复杂度与样本维度和训练样本数量呈线性关系，在训练神经网络和其他非凸目标的机器学习问题上具有广泛应用，并可以保证返回近似局部最小值。

    Nov, 2016

  • 减小方差以实现更快的非凸优化

    本篇论文研究了非凸优化中高效到达稳定点的基本问题，并利用方差缩减技巧和适用于非凸优化的全新方差缩减分析提出一种首个非凸优化的一阶小批量随机算法，并在非凸损失函数和神经网络训练中表现出了有效性。

    Mar, 2016

  • 非凸随机优化下的下限界

    采用随机一阶方法找到梯度范数不超过 ε 的 ε- 稳定点的复杂度下界，使用具有有界方差的无偏随机梯度预言机访问光滑但可能非凸函数的一种模型，证明任何算法在最坏情况下需要至少 ε^-4 个查询才能找到 ε- 稳定点。对于噪声梯度估计满足均方光滑性质的更严格模型，我们证明了 ε^ -3 个查询的下界，建立了最近提出的方差缩减技术的最优性。

    Dec, 2019

  • 一种具有近似评估和复杂度保证的非凸最小化随机算法

    非凸函数的最小化，利用近似正负曲率方向步长，相对不精确度度量梯度和 Hessian 矩阵，松弛一阶和二阶精度的耦合，通过马丁格尔分析和浓度不等式得到收敛性分析，并将算法应用于经验风险最小化问题。

    Oct, 2023

  • 使用迭代一阶方法解决一类非凸极小极大博弈

    利用多阶梯度下降上升算法解决机器学习中非凸场景下最小最大鞍点问题，给出了基于 Polyak-Lojasiewicz 条件的算法和 Concave 最大玩家目标函数的算法，并在 Fashion-MNIST 数据集上进行公平分类实验。

    Feb, 2019

  • 分散式随机非凸优化问题的混合方差缩减方法

    本文研究了分散式随机优化的网络问题，提出了一种新的单循环分散式混合降低方差随机梯度下降算法 GT-HSGD，并度量了其优化性能。

    Feb, 2021

  • 基于修正偏置动量的加速随机极小 - 极大优化

    针对非凸优化中最小最大优化问题，本研究提出了利用高效的 Hessian - 向量乘积的新型修正动量算法，建立了收敛条件并证明了所提算法的迭代复杂度为 O (ε^{-3})。通过在实际数据集上进行鲁棒的逻辑回归的应用验证了该方法的有效性。

    Jun, 2024

  • 一种用于一阶优化的通用催化剂

    本研究引入了一种通用方案，利用对加速邻域点算法的新分析，加快一阶优化方法。通过近似解决一系列精心选择的辅助问题来最小化凸目标，从而实现更快的收敛速度，为包括梯度下降、块坐标下降、SAG、SAGA、SDCA、SVRG、Finito/MISO 及其邻域点变体在内的大类算法提供加速和明确的非强凸目标支持，加速在实践中证明对病态问题尤其有用。

    Jun, 2015