基于频域的不精确梯度方法分析
本文提供了用于计算强凸光滑函数的梯度(或 Cauchy 梯度下降)方法和自准共轭函数的 Newton 方法(包括不准确搜索方向的情况)的最坏情况性能分析的新工具,并通过半定规程性能评估分析扩展了最近 2017 年 Optimization Letters 论文中作者对 Cauchy 方法的性能评估结果,然后通过使用这些工具以一种创新的方式对使用不准确搜索方向的短步长内点法的复杂性进行了演示。作为此框架中的示例,我们概述了如何通过 Abernethy 和 Hazan 在 2016 年的 PMLR 论文中的最近内点法的最坏情况复杂性的严格分析。
Sep, 2017
本文探讨了使用近端梯度法优化平滑凸函数和非平滑凸函数的和时,如果在计算平滑项的梯度或非平滑项的邻近算子时存在误差,基本的近端梯度法和加速近端梯度法可以实现与没有错误的情况下相同的收敛率,前提是错误以适当的速度减小。使用这些速度,在一组结构稀疏性问题上,我们的表现与精心选择的固定误差级别相当或更好。
Sep, 2011
提出了非凸问题的近似解决方案;采用了三次正则化和信任域算法的不精确变体,并且可以应用于有限和问题,通过随机子采样法对梯度和 Hessian 进行适当精度逼近,实现了计算效率与最优迭代复杂度的权衡。
Feb, 2018
对于大部分基于凸优化的统计 $M$- 估计器,我们分析了解决这些问题的渐进收敛速度,并在高维框架中工作,我们定义了适当限制的条件,并证明了这些条件适用于各种统计模型,我们的理论保证了项目的概率几何收敛速度不断提高,最高可达到模型的统计精度,这个结果比以往收敛结果更加尖锐,这适用于 $M$- 估计器和各种统计模型,展现了高维估计中统计精度和计算效率的有趣联系。
Apr, 2011
本文研究了最速下降法在具有 Lipschitz 连续梯度的强凸函数中的精确线性搜索,并确定了该方案的最差收敛速度,证明了某些凸二次函数展示的最差行为。我们还给出了一种噪声变体的最差复杂性边界,通过改变搜索方向,该方向与负梯度的值之差最多只有一个预定的相对容差,并借助于半定规划性能估计问题的解决方法进行了计算机辅助证明
Jun, 2016
本文介绍了一种新的非均匀光滑条件下的优化方法,并开发出一种简单但有效的分析技术来限制沿轨迹的梯度,从而获得更强的凸优化和非凸优化问题的结果。我们通过这种新方法证明了(随机)梯度下降和 Nesterov 加速梯度法在这种一般的光滑条件下的收敛率,而不需要梯度剪裁,并允许在随机场景中的有界方差的重尾噪声。
Jun, 2023
研究了 Nesterov 加速梯度方法在随机逼近和有限和设置下的表现,发现使用通常的步长和动量参数,该方法在后者可能发散,进而阐明了这种方法在此情况下可能失败的原因。
Feb, 2020
本文研究了机器学习中基于不光滑正则化的各种优化问题,并提出了三种不精确的近端梯度算法,包括基本版本和 Nesterov 加速版本。理论分析表明,我们的不精确近端梯度算法可以在非凸情况下具有和精确近端梯度算法相同的收敛速度。实验结果证实了新算法在三个代表性非凸学习问题上的优越性。
Dec, 2016
我们开发了一个新的框架来研究光滑和强凸优化算法,特别是针对二次函数,我们能够将优化算法作为线性运算的递归应用程序来检查,这揭示了一种强大的联系,即一类优化算法与多项式的分析理论之间的联系,从而导出了新的下界和上界,同时我们还以多项式相关的最优解的形式表达它,从而对 Nesterov 著名的加速梯度下降方法进行了新的系统推导。
Mar, 2015