非强凸平稳随机逼近,收敛速率 O (1/n)
考虑由二次函数的期望值和任意凸函数组合成的复合目标函数的最小化问题,我们研究了随机双均值算法在恒定步长下的特性,证明其无需强凸假设即可获得 O (1/n) 的收敛速度,从而将欧几里得几何中关于最小二乘回归的较早结果扩展到了 (a) 所有凸正则化器以及约束条件,以及(b)由 Bregman 距离表示的所有几何形状。通过一种新的证明技巧来实现这一点,该技巧将随机和确定性递归联系起来。
Feb, 2017
本文提出一族算法通过简单的随机模型样本和优化方法,成功的减少了目标函数。我们展示出,合理的近似质量和模型的正则性下,此类算法将自然的稳定度衡量推向 0,该衰减速度为 O (k^(-1/4)),基于此原理,我们为随机的近端子梯度法,近端次梯度法以及规则化的高斯牛顿法等提供了第一个复杂性保证。
Mar, 2018
本文基于凸优化中函数是光滑和非光滑组合的形式,证明了一种适用于大类凸优化问题的随机近端梯度算法收敛性质,其避免了平均化和理论研究中常见但实际中不一定满足的有界性假设,证明了一系列强、弱收敛性结果,并得到了期望意义下的 $O (1/n)$ 的有界性结果。
Mar, 2014
本研究旨在探讨优化非光滑非凸正则化器下的平滑非凸损失函数的随机梯度方法。我们提出了两种简单的随机梯度算法,对于有限总和和一般随机优化问题,相较于现有技术水平,其具有更优的收敛复杂度。同时,我们在经验风险最小化中比较了两种算法的实际表现。
Jan, 2019
本文提出了一种基于加速梯度下降的新随机逼近算法,该算法在非强凸情况下取得了最佳预测误差率,并在加速遗忘初始条件方面达到了最优效果,同时在算法的平均迭代次数和最终迭代次数上均提供了收敛结果,该算法还在无噪声环境下提供了一个匹配下界,展示了我们算法的最优性。
Mar, 2022
本研究考虑在没有标准 Lipschitz 连续性假设的随机弱凸优化问题中,基于新的自适应正则化(步长)策略,我们展示了一类广泛的随机算法包括随机次梯度法在具有恒定错误率的情况下保持 O (1/√K) 的收敛速率。我们的分析基于弱假设:Lipschitz 参数可以由 ||x|| 的一般增长函数界定,或通过独立随机样本进行局部估计。
Jan, 2024
本文研究随机算法优化非凸、非光滑的有限和问题。针对此问题,本文提出快速的随机算法,可获得常数迷你批量的收敛性。本文还使用这些算法的变种,证明了比批量近端梯度下降更快的收敛性,并在非凸、非光滑函数的一个子类中证明全局线性收敛率。
May, 2016
提出一种基于平均加速正则梯度下降的算法,通过细化初值和 Hessian 矩阵的假设,最优地优化回归问题,并证明其在偏差与方差之间具有最优性、大数据时初始化影响可达到 O(1/n2)以及对于维度 d 的依赖程度为 O(d/n)。
Feb, 2016