从误差界到凸函数的一阶下降方法复杂度
本文针对结构化凸优化问题,建立一个新的错误边界框架,并对常见的错误边界结果进行统一和透明的证明,此外,将其应用于核范数正则化损失最小化问题,并在严格补充型条件下建立了新的错误边界。
Dec, 2015
本文研究 KL 指数,为分析一阶方法的收敛速度提供了重要指标,针对新函数我们计算其 KL 指数,并发现对于许多优化模型的目标函数,KL 指数都是 $\frac {1}{2}$。此研究结果可用于许多实际优化模型的一阶方法的明确收敛速度。
Feb, 2016
使用全局误差界分析的方法,研究了一种线性约束非凸最小化问题的迭代复杂度,证明了一类适当设计的原始 - 对偶一阶方法可以在 O (1/∊²) 次迭代内生成线性约束非凸最小化问题的 ε- 稳定解,其复杂度为已知最佳。
Jun, 2020
利用可适应性光滑函数的概念和 Bregman 基础的近端梯度方法,在解决具有复杂目标函数的非凸、非光滑最小化问题时,实现全局收敛。
Jun, 2017
本研究重点关注函数满足较小限制的割线不等式和较大上限误差的函数类,可以在各采样梯度上分别满足一组简单条件,在所有一阶算法中,通过梯度下降法可以完全优化此类函数,从而导致收敛速率的下限。
Mar, 2022
本文介绍了一种利用步长乘以线性误差边界的方法来实现凸函数最小化的近端梯度算法;通过证明将误差边界与一种自然二次生长条件的等价性,直观地解释了观察到的线性收敛现象;我们的方法将推广到用于最小化由光滑映射组成的非光滑函数的近端方法,同时观察到算法中的短步长暗示了接近稳定状态,建议作为可靠的终止准则。
Feb, 2016
我们开发了一个新的框架来研究光滑和强凸优化算法,特别是针对二次函数,我们能够将优化算法作为线性运算的递归应用程序来检查,这揭示了一种强大的联系,即一类优化算法与多项式的分析理论之间的联系,从而导出了新的下界和上界,同时我们还以多项式相关的最优解的形式表达它,从而对 Nesterov 著名的加速梯度下降方法进行了新的系统推导。
Mar, 2015
本文针对一个类别的复合非凸非光滑优化问题,通过使用两个不同的一阶预言机,在最优性公差 ϵ>0 的情况下建立 FOMs 的下界复杂性界,并提出一个非精确近端梯度法来解决该问题。所提出的 IPG 方法的预言机复杂度与我们建立的下界匹配。
Jul, 2023
本文提出一族算法通过简单的随机模型样本和优化方法,成功的减少了目标函数。我们展示出,合理的近似质量和模型的正则性下,此类算法将自然的稳定度衡量推向 0,该衰减速度为 O (k^(-1/4)),基于此原理,我们为随机的近端子梯度法,近端次梯度法以及规则化的高斯牛顿法等提供了第一个复杂性保证。
Mar, 2018