本文提出一族算法通过简单的随机模型样本和优化方法,成功的减少了目标函数。我们展示出,合理的近似质量和模型的正则性下,此类算法将自然的稳定度衡量推向 0,该衰减速度为 O (k^(-1/4)),基于此原理,我们为随机的近端子梯度法,近端次梯度法以及规则化的高斯牛顿法等提供了第一个复杂性保证。
Mar, 2018
本文介绍了一种基于随机投影次梯度方法的弱凸(即均匀逼近正则)非光滑非凸函数的算法,并通过简单证明证明这种方法与用于光滑非凸问题的随机梯度方法具有相同的收敛速度;这似乎是第一个针对弱凸函数类的随机次(或确定性)梯度法的收敛速度分析。
Jul, 2017
该论文研究了由凸或 Prox-regular 函数组成的函数与光滑向量函数的复合函数最小化问题,提出了一种基于线性逼近和正则化项的子问题算法框架,并探讨了该子问题的局部解的性质、全局收敛性和含有原问题解的活动流形的识别性质。初步的计算结果具有良好的性能。
Dec, 2008
我们提出了一种随机梯度框架,用于解决具有(可能)无限数量的线性包含约束条件的随机复合凸优化问题,而这些约束条件需要几乎确定。我们使用平滑和同伦技术处理约束条件,无需矩阵投影,并且通过数值实验表明,我们的算法实现了最先进的实用性能。
Jan, 2019
本文研究随机算法优化非凸、非光滑的有限和问题。针对此问题,本文提出快速的随机算法,可获得常数迷你批量的收敛性。本文还使用这些算法的变种,证明了比批量近端梯度下降更快的收敛性,并在非凸、非光滑函数的一个子类中证明全局线性收敛率。
May, 2016
该论文提出了基于随机条件梯度方法的优化问题求解算法,用于解决大规模维度下的凸函数、连续子模型等多种问题,并证明了当问题维度高时,该方法较与传统的随机梯度下降法更加稳定,同时计算时间复杂度也得到了有效降低。
Apr, 2018
提出一种新方法解决一类复合随机非凸优化问题,通过组合两种随机估计量形成混合估计量,将之应用于多种变体的随机梯度法中以达到最优的复杂度界限。
Jul, 2019
本文提出了基于模型的方法,解决随机凸优化问题,并介绍了近似近端点(aProx)家族,包括随机次梯度、近端点和束方法。通过适当准确的建模方法,这些方法享有比传统方法更强的收敛性和鲁棒性保证,即使与随机次梯度方法相比,基于模型的方法通常增加很少甚至没有计算开销。
Oct, 2018
通过研究随机最小化和学习问题的模型,我们提出了一种更具鲁棒性的解决方案。通过适当精确的模型,即所谓的 aProx 系列,随机最优化方法可以稳定,可证明收敛且渐近最优。我们将这些结果扩展到弱凸目标,其中包括凸损失与光滑函数的组合,在现代机器学习应用中很常见。通过对收敛时间和算法灵敏度的仔细实验评估,我们强调了鲁棒性和准确的建模的重要性。
Mar, 2019
本文研究了一类增量方法,用于解决微弱凸优化问题,并证明了这三种增量方法可以使自然稳定性测量值小于给定的极值下界,同时,当微弱凸函数满足锐化条件时,经过适当的初始化和几何递减的步长,三种增量方法可以实现局部线性收敛速度,最后在鲁棒矩阵感知问题上进行了数值实验。