本研究考虑具有强凸(但不一定平滑)目标函数的随机凸优化问题,我们提出一种仅使用梯度更新的算法,具有最优的收敛速度。
Jun, 2010
本文提出一族算法通过简单的随机模型样本和优化方法,成功的减少了目标函数。我们展示出,合理的近似质量和模型的正则性下,此类算法将自然的稳定度衡量推向 0,该衰减速度为 O (k^(-1/4)),基于此原理,我们为随机的近端子梯度法,近端次梯度法以及规则化的高斯牛顿法等提供了第一个复杂性保证。
Mar, 2018
我们提出了一个基于条件梯度法的复合凸优化模板,该方法结合了平滑和同伦技术,在 CGM 框架下实现了最优的 O(1 /sqrt(k))收敛速度,并证明了在线性子问题具有加法或乘法误差时,同样的速率保持不变。此外,与相关工作相比,我们能够描述非平滑项为指示函数时的收敛性质。
Apr, 2018
本文基于凸优化中函数是光滑和非光滑组合的形式,证明了一种适用于大类凸优化问题的随机近端梯度算法收敛性质,其避免了平均化和理论研究中常见但实际中不一定满足的有界性假设,证明了一系列强、弱收敛性结果,并得到了期望意义下的 $O (1/n)$ 的有界性结果。
Mar, 2014
本研究考虑了具有随机性的凸函数和光滑函数组成并且是弱凸的函数式的最小化问题,开发了一系列随机算法,并通过实验验证了实际效果。
Mar, 2017
该研究提出了一种基于随机梯度下降法的内点算法,用于最小化一个连续可微的目标函数,该函数可能不是凸函数,同时受到边界约束。该算法唯一之处在于通过计算随机梯度估计来计算搜索方向,以及通过正面和消失的邻域参数序列来定义可行区域内部邻域,从而迫使迭代点保持在该邻域内。数值实验结果表明,在确定性和随机设置下,该算法的性能可以超过投影 -(随机)梯度法。
Apr, 2023
本研究介绍了一种基于条件梯度算法的优化模型,可用于求解线性优化问题和非线性凸优化问题,并给出了一种基于此算法的在线凸优化算法,具有线性收敛速度和最优的遗憾保证。
Jan, 2013
我们开发了一个新的框架来研究光滑和强凸优化算法,特别是针对二次函数,我们能够将优化算法作为线性运算的递归应用程序来检查,这揭示了一种强大的联系,即一类优化算法与多项式的分析理论之间的联系,从而导出了新的下界和上界,同时我们还以多项式相关的最优解的形式表达它,从而对 Nesterov 著名的加速梯度下降方法进行了新的系统推导。
Mar, 2015
该论文研究了随机受限多层优化的无投影算法。介绍了新的无投影方差缩减算法并分析了它们在不同条件下的复杂性,包括梯度映射和 Frank-Wolfe 间隙准则,并通过分阶段适应进一步获得了凸函数和强凸函数的复杂性,数值实验证明了该方法的有效性。
Jun, 2024
本研究提出了一种新的不需要投影的算法框架来解决在线凸优化问题,该算法框架具有较好的性能表现并可处理多种约束情况。
May, 2023