蒙特卡罗和线性随机逼近的显式均方误差界
考虑由 Markovian 噪声驱动的线性随机逼近算法的动态特性,通过考虑适当选择的 Lyapunov 函数的漂移,获得常数步长算法的有限时间误差的二次矩的有限时间界限。我们还对逼近误差 2 范数的平方的矩进行了全面的处理。
Feb, 2019
本文提供了一个线性双时间尺度随机逼近方法的有限时间分析,结果表明在马尔可夫噪声和鞅噪声下没有收敛速率的区别,只有马尔可夫链的混合时间会影响常数,并提出了一个匹配的下界。
Feb, 2020
研究了最小二乘线性回归的问题,其中数据点依赖于并从马尔可夫链中采样。在不同的噪声设置下,建立了关于底层马尔可夫链混合时间 $\tau_{mix}$ 的尖锐信息理论极小值下界来解决此问题。我们发现,与独立数据的优化相比,具有马尔可夫数据的优化通常更加困难,一个只在大约 $ ilde {\Theta}(\tau_{mix})$ 个样本中工作的平凡算法 (SGD-DD) 是极小化最优的。此外,我们还研究了实践中出现的结构化数据集,例如高斯自回归动态,它们能否拥有更高效的优化方案。令人惊讶的是,即使在这个特定的自然环境下,具有一定步长的随机梯度下降法与常数并没有比 SGD-DD 算法更好。相反,我们提出了一种基于体验复盘的算法 —— 一种流行的强化学习技术 —— 它可以实现更好的误差率。我们的改进速率是第一个在有趣的马尔可夫链上优于 SGD-DD 的算法之一,也为在实践中支持使用经验回放提供了首个理论分析。
Jun, 2020
该研究论文主要讨论了随机逼近算法在嘈杂测量、凸凹优化、强化学习以及马尔可夫逼近方面的应用,并且扩展了该算法以包含具有非零条件均值和 / 或无界条件方差的错误,从而证明了算法在这些情况下的收敛性,并计算了 “优化步长序列” 以最大化估计的收敛速率。
Dec, 2023
研究了一种在 Markovian 噪声下的非线性随机逼近算法,证明了其具有不同学习速率的有限样本收敛界限,并证明了其适用于 Q-learning 算法。
May, 2019
本文研究了马尔科夫链蒙特卡罗方法的误差边界问题,针对不同类型的马尔科夫链给出了相应的上下界,同时提供了选择转化期的配方,并将误差边界应用于积分和概率计算。
Aug, 2011
本文证明了当损失函数为亚高斯函数时,基于互信息计算的以经验风险最小化为主要准则的监督机器学习算法对训练数据过拟合的泛化误差上界,此外还探究了噪声受限的迭代算法的泛化误差上界。
Jan, 2018
本文提出了一种称为精确估计算法的蒙特卡罗方法,该算法为实值函数的平衡期望提供无偏估计,并为正哈里斯经常性马尔可夫链以及平均收缩的链提供易于实现的算法。此外,本文认为在马尔可夫链环境中进行精确估计相对于精确模拟方法提供了显着的理论松弛。
Sep, 2014
本文介绍了一种新的随机快速蒙特卡洛采样算法,在强假设下,对于具有平方可积混合偏导数的积分被证明其可获得适当的精度;文中提出的算法数值示例 RMSE 呈 $N^{-5/2}$ 和 $N^{-7/2}$ 的收敛,符合理论上界。
Jul, 2010
用马尔可夫噪声对线性二时间尺度随机逼近算法进行了收敛性分析,得到了该算法各种步长选择下的收敛行为,应用结果到 TDC 算法得到了比之前工作更好的收敛性样本复杂度,该结果还适用于确定各种强化学习算法的收敛行为,如带有 Polyak 平均的 TD 学习,GTD 和 GTD2。
Dec, 2023