关于平滑非凸有限和优化的下界
本文提出了优化 n 个 L-smooth、强凸函数总和的下界,并将其与先前的方法进行比较。在随机数据情况下,我们将这些复杂度结果与用于直接优化总和的最优一阶方法进行对比。研究发现需要谨慎进行准确比较,并确定新方法在机器学习场景中的帮助计算能力。
Oct, 2014
本文研究非凸强凹(NC-SC)平滑极小值问题的近似稳定点的复杂度,在一般和平均平滑有限和设置中建立了非平凡的较低复杂度下界。我们提出了一种通用的加速方案,使用现有的基于梯度的方法来解决一系列的精心制作的强凸 - 强凹子问题,进而缩小了复杂度差距,尤其是在一般情况下,我们提出的算法的复杂度几乎与下界相当。
Mar, 2021
采用随机一阶方法找到梯度范数不超过 ε 的 ε- 稳定点的复杂度下界,使用具有有界方差的无偏随机梯度预言机访问光滑但可能非凸函数的一种模型,证明任何算法在最坏情况下需要至少 ε^-4 个查询才能找到 ε- 稳定点。对于噪声梯度估计满足均方光滑性质的更严格模型,我们证明了 ε^ -3 个查询的下界,建立了最近提出的方差缩减技术的最优性。
Dec, 2019
该论文提出了改进的 SARAH 算法并证明其最劣情况复杂性与通常常数因子内与阈值相关,用于求解随机一阶优化算法的无限和光滑非凸目标函数,同时提出 SARAH++ 算法,并在各种数据集上进行数值实验以验证其实用性。
Jan, 2019
本文针对一个类别的复合非凸非光滑优化问题,通过使用两个不同的一阶预言机,在最优性公差 ϵ>0 的情况下建立 FOMs 的下界复杂性界,并提出一个非精确近端梯度法来解决该问题。所提出的 IPG 方法的预言机复杂度与我们建立的下界匹配。
Jul, 2023
我们通过使用第一阶 oracle 及条件数,提供了寻找 min-max 优化问题中目标函数在最小化变量上是非凸及在最大化变量上是强凸时的稳定点的复杂度的下界,这既适用于确定性 oracle 也适用于随机 oracle,并提供了各自的下界,并与其他文献的上界进行了比较。
Apr, 2021
本篇论文研究了非凸优化中高效到达稳定点的基本问题,并利用方差缩减技巧和适用于非凸优化的全新方差缩减分析提出一种首个非凸优化的一阶小批量随机算法,并在非凸损失函数和神经网络训练中表现出了有效性。
Mar, 2016