平滑强凸函数的随机逼近:超越 $O (1/T)$ 收敛速度
本篇论文研究了关于随机逼近问题的现有算法,提出了两种新型随机梯度算法,并在回归和逻辑分类两种经典的监督学习问题上进行了测试,得到了较好的优化效果。
Jun, 2013
本文考虑优化一个平滑凸函数,该函数是一组可微函数的平均数,在每个梯度的范数受到平均梯度范数的线性约束的假设下,证明了基本的随机梯度方法具有 O (1/k) 的收敛速度,并且在强凸条件下具有线性收敛速度。
Aug, 2013
该研究论文主要讨论了随机逼近算法在嘈杂测量、凸凹优化、强化学习以及马尔可夫逼近方面的应用,并且扩展了该算法以包含具有非零条件均值和 / 或无界条件方差的错误,从而证明了算法在这些情况下的收敛性,并计算了 “优化步长序列” 以最大化估计的收敛速率。
Dec, 2023
本研究考虑在没有标准 Lipschitz 连续性假设的随机弱凸优化问题中,基于新的自适应正则化(步长)策略,我们展示了一类广泛的随机算法包括随机次梯度法在具有恒定错误率的情况下保持 O (1/√K) 的收敛速率。我们的分析基于弱假设:Lipschitz 参数可以由 ||x|| 的一般增长函数界定,或通过独立随机样本进行局部估计。
Jan, 2024
本文提出一族算法通过简单的随机模型样本和优化方法,成功的减少了目标函数。我们展示出,合理的近似质量和模型的正则性下,此类算法将自然的稳定度衡量推向 0,该衰减速度为 O (k^(-1/4)),基于此原理,我们为随机的近端子梯度法,近端次梯度法以及规则化的高斯牛顿法等提供了第一个复杂性保证。
Mar, 2018
本文基于凸优化中函数是光滑和非光滑组合的形式,证明了一种适用于大类凸优化问题的随机近端梯度算法收敛性质,其避免了平均化和理论研究中常见但实际中不一定满足的有界性假设,证明了一系列强、弱收敛性结果,并得到了期望意义下的 $O (1/n)$ 的有界性结果。
Mar, 2014
本文研究了随机梯度下降在随机情形下的最优性。结果表明,对于光滑问题,算法可以达到最优的 O (1/T) 收敛速率,但对于非光滑问题,平均收敛速率可能真的是 Ω(log (T)/T),而这不仅仅是分析的产物。反过来,我们展示了一种简单的平均步骤修改方法,足以恢复到 O (1/T) 收敛速率,而无需对算法做出任何其他改变。此外,我们还给出了支持我们发现的实验结果,并指出了开放性问题。
Sep, 2011
本文提出了一种基于广义 Moreau 信封的平滑 Lyapunov 函数方法,使用不同的步长展示了其在含噪声的固定点方程求解中的有限样本误差界,并将其应用于强化学习中的 V-trace 算法和 Q-learning,获得了现有最先进的结果,且收敛边界仅在状态空间大小上具有对数依赖。
Feb, 2020
本文研究了利用随机一阶预测器在凸集上最小化凸函数的问题,证明了函数在最小值点 $x_{f, S}^*$ 附近增长的速率是最优学习率的决定因素,并得到了关于学习率和复杂度的结论结果。
Jul, 2012