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

Sep, 2017

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

Jan, 2024

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

Jul, 2017

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

May, 2019

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

Nov, 2014

研究马尔可夫噪声和常数步长的随机逼近算法，通过基于无穷小生成器比较的方法，研究算法的偏差以及时间平均偏差，证明其分别为 O (α) 和 αV + O (α^2)，并且 Polyak-Ruppert 平均值收敛概率高于 θ* + αV。此外，结合 Richardson-Romberg 外推方法，构建一个具有 O (α^2) 偏差的迭代方案。

May, 2024

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

Jun, 2023

本文研究了常数步长情况下强凸损失函数的随机梯度算法，在收敛时随机重排比均匀抽样性能更优，通过分析表明了迭代值到达最小值的邻域范围更小，证明了随机重排算法的性能更好，同时解释了随机重排算法实现中观察到的周期性行为。

Mar, 2018

研究了最小二乘线性回归的问题，其中数据点依赖于并从马尔可夫链中采样。在不同的噪声设置下，建立了关于底层马尔可夫链混合时间 $\tau_{mix}$ 的尖锐信息理论极小值下界来解决此问题。我们发现，与独立数据的优化相比，具有马尔可夫数据的优化通常更加困难，一个只在大约 $ ilde {\Theta}(\tau_{mix})$ 个样本中工作的平凡算法 (SGD-DD) 是极小化最优的。此外，我们还研究了实践中出现的结构化数据集，例如高斯自回归动态，它们能否拥有更高效的优化方案。令人惊讶的是，即使在这个特定的自然环境下，具有一定步长的随机梯度下降法与常数并没有比 SGD-DD 算法更好。相反，我们提出了一种基于体验复盘的算法 —— 一种流行的强化学习技术 —— 它可以实现更好的误差率。我们的改进速率是第一个在有趣的马尔可夫链上优于 SGD-DD 的算法之一，也为在实践中支持使用经验回放提供了首个理论分析。

Jun, 2020

该研究提出了一种新颖的自适应步长方法来解决随机梯度下降（SGD）中的问题，通过利用我们识别出的可追踪的量（梯度的 Lipschitz 常数和搜索方向的局部方差的概念），我们的发现为随机优化提供了几乎无需调参的算法，该算法在应用于二次问题时具有可证明的收敛性质，并在经典图像分类任务中展现出真正的问题自适应行为。我们的框架还可以包含预处理器，从而实现对随机二阶优化方法的自适应步长的实现。

Nov, 2023