Jun, 2020

带有马尔可夫数据的最小二乘回归：基本限制和算法

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

    本文研究了基于 Markov 链采样的随机约束随机优化问题，将 drift-plus-penalty 方法推广至这一设置，提出了两种变体，分别适用于已知和未知混合时间的情况，同时适用于约束函数序列遵循 Markov 链的一般设置，通过在分类中引入公平约束的数值实验证明了我们所提方法的有效性。

    Dec, 2023

  • 马尔科夫链理论方法描述随机梯度下降（针对最小二乘法）的极小极大优化特性

    本文针对最小二乘法，提供了一个简化的证明，证明了随机梯度下降法（SGD）的（迭代平均）统计极小值最优性，并通过分析 SGD 作为随机过程、对该过程的稳态协方差矩阵进行尖锐刻画等方式进行了证明。有限速率的最优性刻画捕获了常数因子，并解决了模型错误规格化的问题。

    Oct, 2017

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

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

    Jul, 2017

  • 应对马尔科夫数据随机优化中的混合时间

    本研究提出了一种新颖的多层蒙特卡罗渐进优化方法，针对含有 Markov 链随机数据的优化问题，能够在不知道 Markov 链混合时间的情况下获得最佳渐进收敛速率，并适用于非凸优化求解及在时间差分 (TD) 学习中获取更好的混合时间依赖性。

    Feb, 2022

  • 利用随机梯度下降进行近似贝叶斯推断

    本文从随机过程的角度出发，论证了常数学习率随机梯度下降算法（constant SGD）可用作一种近似贝叶斯推断算法，其可优化模型中的超级参数，同时分析了 Langevin Dynamics 和 Stochastic Gradient Fisher Scoring 的近似误差以及 Polyak 平均算法的最优性。在此基础上，提出了一种可扩展的近似马尔科夫链蒙特卡罗（MCMC）算法，即平均随机梯度采样算法（Averaged Stochastic Gradient Sampler）。

    Apr, 2017

  • 马尔可夫链梯度下降

    本文研究随机梯度下降的变体 —— 马尔科夫链梯度下降算法，并针对非凸问题和不可逆有限状态马尔科夫链等情形，提出可行的非等时收敛证明，并通过实验验证其有效性。

    Sep, 2018

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

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

    May, 2019

  • 非强凸最小二乘问题的加速随机梯度下降

    本文提出了一种基于加速梯度下降的新随机逼近算法，该算法在非强凸情况下取得了最佳预测误差率，并在加速遗忘初始条件方面达到了最优效果，同时在算法的平均迭代次数和最终迭代次数上均提供了收敛结果，该算法还在无噪声环境下提供了一个匹配下界，展示了我们算法的最优性。

    Mar, 2022

  • 大步长非参数随机逼近

    本文研究了基于再生核 Hilbert 空间（RKHS）框架下的随机设计最小二乘回归问题，其中采用平均非正则化最小均方算法得到了最优收敛速率。

    Aug, 2014

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

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

    Feb, 2019