May, 2024

计算具有马尔可夫噪声的恒定步长随机逼近的偏差

PDF
TL;DR研究马尔可夫噪声和常数步长的随机逼近算法，通过基于无穷小生成器比较的方法，研究算法的偏差以及时间平均偏差，证明其分别为 O (α) 和 αV + O (α^2)，并且 Polyak-Ruppert 平均值收敛概率高于 θ* + αV。此外，结合 Richardson-Romberg 外推方法，构建一个具有 O (α^2) 偏差的迭代方案。
stochastic approximation algorithmsmarkovian noiseconstant step-sizebiaspolyak-ruppert average
发现论文，激发创造
  • 常值步长最小均方：偏差 - 方差权衡与最优抽样分布

    本文考虑了最小二乘回归问题，提出了平均恒定步长随机梯度下降（也称最小均方误差）的性能的详细渐近分析。在强凸情况下，我们提供了一个高度渐近展开式。我们的分析提供了对随机逼近算法的新见解。

    Nov, 2014

  • 非线性随机逼近的有限样本分析及其在强化学习中的应用

    研究了一种在 Markovian 噪声下的非线性随机逼近算法，证明了其具有不同学习速率的有限样本收敛界限，并证明了其适用于 Q-learning 算法。

    May, 2019

  • 线性随机逼近和 TD 学习的有限时间误差界

    考虑由 Markovian 噪声驱动的线性随机逼近算法的动态特性，通过考虑适当选择的 Lyapunov 函数的漂移，获得常数步长算法的有限时间误差的二次矩的有限时间界限。我们还对逼近误差 2 范数的平方的矩进行了全面的处理。

    Feb, 2019

  • 常步长随机梯度下降与马尔可夫链的桥梁

    本文应用马尔科夫链理论，通过随机梯度下降（SGD）算法来计算目标函数，并提供了一种新的 Richardson-Romberg 外推方法来优化 SGD 算法，通过渐进展开分析，总结出其与初始条件、噪声和步长的相关性。

    Jul, 2017

  • 线性随机逼近：常数步长与迭代平均

    本文考虑使用常数步长和 Polyak-Ruppert 平均的 $d$ 维线性随机逼近算法 (Linear Stochastic Approximation Algorithms) 及其应用于机器学习和强化学习，针对策略评估问题，采用时序差分 (Temporal Difference) 类算法作为 LSAs，提供了均方误差 (MSE) 的界限，并探讨了适用一类数据分布的常数步长选取条件以及启发式步长调整算法。

    Sep, 2017

  • Markovian LSA 和统计推论中的恒定步幅的有效性

    本研究通过线性随机逼近（LSA）算法与马尔可夫数据研究了使用恒定步长进行统计推断的有效性。通过建立中心极限定理（CLT），我们提出了一种使用平均 LSA 迭代构建置信区间（CIs）的推断过程。我们的方法利用恒定步长 LSA 的快速混合特性进行更好的协方差估计，并采用 Richardson-Romberg（RR）外推方法来减少恒定步长和马尔可夫数据引起的偏差。我们在 RR 外推中开发了用于指导步长选择的理论结果，并确定了几个重要设置，在没有外推的情况下，偏差可以证明消失。我们进行了大量的数值实验，并与传统推断方法进行比较。我们的结果表明，使用恒定步长在超参数调整、快速收敛和一致性更好的置信区间覆盖方面具有优势，尤其是在数据有限的情况下。

    Dec, 2023

  • 常步尺度 Q - 学习：分布收敛、偏差和推广

    通过将常步长 Q 学习与时间齐次马尔可夫链连接，在 Wasserstein 距离中展示了迭代的分布收敛性，建立了其指数收敛速度；我们还为 Q 学习迭代建立了中心极限定理，证明了平均迭代的渐近正态性；此外，我们提供了对步长渐近偏差的显式扩展，具体而言，偏差与步长成比例，我们为线性系数提供了一个明确的表达式；这个对偏差的精确刻画允许应用 Richardson-Romberg 外推技术来构造一个新估计，该估计可证明比最优的 Q 函数更接近；数值结果证实了我们在 RR 外推方法改进方面的理论发现。

    Jan, 2024

  • 随机逼近的收敛速度：有偏差噪声与无界方差，及其应用

    该研究论文主要讨论了随机逼近算法在嘈杂测量、凸凹优化、强化学习以及马尔可夫逼近方面的应用，并且扩展了该算法以包含具有非零条件均值和 / 或无界条件方差的错误，从而证明了算法在这些情况下的收敛性，并计算了 “优化步长序列” 以最大化估计的收敛速率。

    Dec, 2023

  • 应用 ODE 方法的随机逼近和强化学习在马尔可夫噪音中

    扩展 Borkar-Meyn 定理以适用于具有线性函数逼近和资格痕迹的离策略强化学习算法，分析随机逼近算法的稳定性和马尔可夫噪声条件下的边界性。

    Jan, 2024

  • 通过马尔可夫链实现常数步长 SGD 的收敛和集中特性

    本文研究在强凸光滑目标下使用常数步长随机梯度下降的优化问题，通过马洛夫链的视角对其性质进行研究，证明了当梯度噪音分布满足一定条件时，该迭代过程以总变差距离或 Wasserstein-2 距离收敛于一个不变分布，同时证明了该极限分布具有次高斯或次指数分布的浓度性质；最后针对一些具体应用，推导出了高可信度界限。

    Jun, 2023