一种具有近似评估和复杂度保证的非凸最小化随机算法
在在线学习中,优化随机零阶反馈下的凸函数一直是一个主要而具有挑战性的问题。本文考虑了仅能对目标函数进行噪声评估的情况下,对二阶平滑和强凸函数进行优化的问题;通过提出匹配的上下界,第一次对最小化最大简单后悔的速率进行了紧密的刻画。我们提出了一种算法,结合了启动阶段和镜像下降阶段。我们的主要技术创新包括对高阶平滑性条件下球形采样梯度估计器的尖锐刻画,从而使算法能够在偏差 - 方差权衡方面达到最优平衡,以及一种用于启动阶段的新的迭代方法,它能够保持无界 Hessian 的性能。
Jun, 2024
本文研究了基于 Hessian 矩阵近似的非凸优化中信任域和立方正则化方法的变体。通过对不精确 Hessian 矩阵的渐进解和相应子问题的近似解,提供了迭代复杂度,以实现达到二阶最优条件的近似解,并且在现有文献中条件松弛。
Aug, 2017
本文提出了一种基于加速的近端点方法和最小值近端步求解器的算法,其梯度复杂度为 O(kappa_x kappa_y^0.5),匹配了已有的最优下界,可用于解决强凸强凹、凸凹、非凸强凹和非凸凹函数的问题。
Feb, 2020
通过使用随机 TR 和 ARC 方法,我们可以在同时提供 Hessian 矩阵、梯度和函数值的不精确计算的基础上,减少每次迭代的传播开销,从而获得与之前研究中的准确计算同级别的迭代复杂度以实现近似二阶最优性,并通过有限和最小化问题中的随机采样技术满足不精确性的温和条件。数值实验支持这些发现,并表明我们的算法在进行相同或相似次数的迭代时,每次迭代所需的计算开销较当前的二阶方法更少。
Oct, 2023
使用基于牛顿方法和线性共轭梯度算法的迭代算法来最小化平滑非凸目标函数,在 Hessian 矩阵的负曲率方向上显式检测和利用,可以证明该算法与 1980 年代开发的 Newton-conjugate 梯度程序非常接近,但包括了增强功能,以证明收敛到满足近似一阶和二阶最优条件的点的最坏情况复杂度结果,这些复杂度结果与文献中已知的二阶方法的最佳结果相匹配。
Mar, 2018
通过重新定义问题为最小化问题,应用特定变体的近端点算法和使用最佳算法计算不准确的近端算子,我们将最小极小化优化问题的梯度计算复杂度降至 O (sqrt (kappax*kappay)*log (1/epsilon))
May, 2022
针对非凸优化中最小最大优化问题,本研究提出了利用高效的 Hessian - 向量乘积的新型修正动量算法,建立了收敛条件并证明了所提算法的迭代复杂度为 O (ε^{-3})。通过在实际数据集上进行鲁棒的逻辑回归的应用验证了该方法的有效性。
Jun, 2024
提出了非凸问题的近似解决方案;采用了三次正则化和信任域算法的不精确变体,并且可以应用于有限和问题,通过随机子采样法对梯度和 Hessian 进行适当精度逼近,实现了计算效率与最优迭代复杂度的权衡。
Feb, 2018
本篇论文研究了关于随机逼近问题的现有算法,提出了两种新型随机梯度算法,并在回归和逻辑分类两种经典的监督学习问题上进行了测试,得到了较好的优化效果。
Jun, 2013
通过使用只需要计算梯度的加速梯度方法,该论文提出了一种快速求解具有 Lipschitz 连续的一阶和二阶导数的非凸优化问题的算法,该方法相较于梯度下降算法在复杂度和精度上都表现更优。
Nov, 2016