MMOct, 2017

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

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

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

    Jul, 2017

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

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

    Jun, 2020

  • 最小二乘回归的随机梯度下降并行化：小批量、平均和模型错误

    该研究探讨了在随机梯度下降中广泛使用的平均方案的好处。特别是，通过对最小二乘回归的随机逼近问题进行非渐进超额风险分析，提供了这些方案的性能保证，并提出了高度可并行化的随机梯度下降方法。同时，该研究认为，为了保证最小极大风险，针对混浊噪声的步长必须是噪声属性的一个函数。

    Oct, 2016

  • 使用随机梯度下降法找到稳定点的复杂度

    研究了随机梯度下降（SGD）算法在最小化光滑、可能非凸函数梯度范数方面的迭代复杂度，结果表明，Ghadimi 和 Lan 的上限不能得到改进，除非做出额外的假设，即使对于凸二次函数，也是如此；此外还表明，对于非凸函数，SGD 最小化梯度的可行性需要根据所选择的最优性标准而定。

    Oct, 2019

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

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

    Apr, 2017

  • 极小化极大优化的 SDEs

    利用随机微分方程分析和比较最小化最大化优化器的 SDE 模型，揭示超参数、隐式正则化和隐含的曲率诱导噪声之间的相互作用，并以简化的设定推导出收敛条件和闭式解，进一步揭示不同优化器行为的见解。

    Feb, 2024

  • 使用顺序半定规划分析带偏差的随机梯度下降

    本文研究了计算误差对有偏随机梯度下降算法的收敛速率的影响，并使用随机二次约束和线性矩阵不等式来推导有偏随机梯度下降算法的收敛界限。此外，通过该线性矩阵不等式条件开发了一种序列最小化方法，用于分析步长选择，收敛速度，优化精度和梯度不准确性之间的复杂权衡，并提供了该线性矩阵不等式的可行点，并得到了在各个损失函数假设下有偏随机梯度下降算法收敛特性的理论公式。

    Nov, 2017

  • 马尔可夫链梯度下降

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

    Sep, 2018

  • 深度学习理论 IIb：SGD 的优化特性

    本文结合实验和理论，对深度卷积网络的随机梯度下降进行了优化，并提出了一种新的猜想，即 SGD 会在概率上集中于大体积的 “平坦” 极小值，选择刚好也是全局最小值的 “平坦” 极小值。

    Jan, 2018

  • 随机梯度下降法在极小极大问题中的稳定性和泛化性

    通过算法稳定性的视角，对凸凹和非凸非凹情形下的随机梯度方法在极小极大问题中的泛化能力进行了全面的分析，建立了稳定性与泛化能力之间的定量联系。在凸凹情形下，稳定性分析表明了随机梯度下降算法对于平滑和非平滑的极小极大问题皆可达到最优的泛化界。我们还确定了泛函弱凸弱凹和梯度占主导地位的问题的泛化界。

    May, 2021