随机梯度下降,加权抽样和随机 Kaczmarz 算法
本文提出了一种基于加速梯度下降的新随机逼近算法,该算法在非强凸情况下取得了最佳预测误差率,并在加速遗忘初始条件方面达到了最优效果,同时在算法的平均迭代次数和最终迭代次数上均提供了收敛结果,该算法还在无噪声环境下提供了一个匹配下界,展示了我们算法的最优性。
Mar, 2022
本文基于凸优化中函数是光滑和非光滑组合的形式,证明了一种适用于大类凸优化问题的随机近端梯度算法收敛性质,其避免了平均化和理论研究中常见但实际中不一定满足的有界性假设,证明了一系列强、弱收敛性结果,并得到了期望意义下的 $O (1/n)$ 的有界性结果。
Mar, 2014
本文研究在强凸光滑目标下使用常数步长随机梯度下降的优化问题,通过马洛夫链的视角对其性质进行研究,证明了当梯度噪音分布满足一定条件时,该迭代过程以总变差距离或 Wasserstein-2 距离收敛于一个不变分布,同时证明了该极限分布具有次高斯或次指数分布的浓度性质;最后针对一些具体应用,推导出了高可信度界限。
Jun, 2023
本文提出一族算法通过简单的随机模型样本和优化方法,成功的减少了目标函数。我们展示出,合理的近似质量和模型的正则性下,此类算法将自然的稳定度衡量推向 0,该衰减速度为 O (k^(-1/4)),基于此原理,我们为随机的近端子梯度法,近端次梯度法以及规则化的高斯牛顿法等提供了第一个复杂性保证。
Mar, 2018
我们提出了一种随机梯度框架,用于解决具有(可能)无限数量的线性包含约束条件的随机复合凸优化问题,而这些约束条件需要几乎确定。我们使用平滑和同伦技术处理约束条件,无需矩阵投影,并且通过数值实验表明,我们的算法实现了最先进的实用性能。
Jan, 2019
本文研究加速随机梯度方法在最小二乘回归问题中的应用,通过对加速随机梯度下降作为随机过程的深入分析,证明了引入加速能够使其对统计误差具有鲁棒性,并提出了一种优于随机梯度下降的加速随机梯度方法。
Apr, 2017
本篇论文研究了关于随机逼近问题的现有算法,提出了两种新型随机梯度算法,并在回归和逻辑分类两种经典的监督学习问题上进行了测试,得到了较好的优化效果。
Jun, 2013
我们在插值条件下证明了随机 Nesterov 加速的新的收敛速度。不同于以往的分析,我们的方法可以加速任何在期望中取得足够进展的随机梯度方法。证明使用估计序列框架进行,适用于凸函数和强凸函数,并且可以轻松推广到满足强生长条件的加速 SGD。在这种特殊情况下,我们的分析将强生长常数的依赖性从 ρ 减小到√ρ,相对于以前的工作来说,这一改进相当于最坏情况下条件数的平方根,并解决了对于随机加速的保证可能不如 SGD 的批评。
Apr, 2024
本文提出了一个基于 Riemann 流形的梯度下降法以及一个几何性质框架,并探讨了如何将慢速收敛的结果转化为快速收敛结果。此外,我们将该框架应用于几何上强凸和欧几里得非凸问题,以及流式 $k$-PCA 问题,并展示了如何加速随机幂法的优化率。
Feb, 2018