Nov, 2023

在轻松平滑条件下的参数无关优化

HTML
PDF
TL;DR通过理论和实验证明，Normalized Stochastic Gradient Descent with Momentum算法在没有先验知识的情况下可以实现（接近）最优复杂度，但复杂度中引入了一个依赖于(L_1)的指数项，这是不可避免的。同时，在确定性设置下，可以通过使用Gradient Descent with a Backtracking Line Search来抵消指数因子。这是首个在广义平滑条件下提出的无需参数设置的收敛结果。
发现论文，激发创造
  • 自适应步长随机梯度下降算法的收敛性

    通过研究广义AdaGrad步长在凸和非凸设置中，本文证明了这些步长实现梯度渐近收敛于零的充分条件，从而填补了这些方法理论上的空白。此外，本文表明这些步长允许自动适应随机梯度噪声级别在凸和非凸情况下，实现O（1/T）到O（1/根号T）的插值（带有对数项）。

    May, 2018

  • 带动量的随机梯度方法收敛于非光滑非凸优化问题

    本文介绍了一种随机子梯度方法，该方法结合了动量项，能够在一类广泛意义下的非光滑、非凸和受约束的优化问题中建立一个特殊的李亚普诺夫函数，实现快速收敛。

    Feb, 2020

  • 一枚硬币的两面：未调节的 SGD 的局限性和自适应方法的威力

    本文探讨了随机梯度下降法与多项式衰减步长之间的关系，并证明无调谐的随机梯度下降法具有渐进最优的收敛速率，但需要面临指数级的平滑度常数；而规范化SGD、AMSGrad和AdaGrad方法可以在不知道平滑度参数和随机梯度边界条件的情况下消除梯度爆炸问题。

    May, 2023

  • 梯度下降的非均匀平滑性

    该研究介绍了一种局部一阶平滑性oracle（LFSO），可以用于调整梯度下降方法的步长，从而改善全局和局部收敛性。通过应用LFSO于修正的一阶方法，可以在非强凸问题中实现全局线性收敛速度，从而提高了一般（加速）一阶方法的收敛率下界。

    Nov, 2023

  • 加速梯度算法与自适应子空间搜索用于快速实例优化

    设计和分析基于梯度的算法，适用于机器学习中的优化问题，包括线性回归等，并改进了现有的复杂度下界。

    Dec, 2023

  • 隐式逐步优化中动量在平滑目标函数中的作用

    随机梯度下降(SGD)与动量在收敛性和泛化能力方面具有快速收敛和优秀的表现，但缺乏理论解释。本文证明了SGD与动量使目标函数平滑化，平滑程度由学习率、批量大小、动量因子、随机梯度的方差和梯度范数的上界决定。这一理论发现揭示了动量为何改善泛化性能，并对包括动量因子在内的超参数的作用提供了新的见解。我们还提出了一种利用SGD与动量平滑性质的隐性渐变优化算法，并提供了支持我们断言的实验结果。

    Feb, 2024

  • 方向平滑性和梯度方法：收敛性和适应性

    我们开发了一种梯度下降法的新次优性边界，该边界依赖于优化路径中的目标条件，而不是全局最坏情况下的常数。我们的证明关键在于方向平滑性，这是一种梯度变化的度量，我们用它来开发上界约束。通过求解隐式方程来最小化这些上界约束，我们展示了这些方程对于凸二次函数是容易解决的，并为两种传统步长提供了新的保证。对于一般函数，我们证明了Polyak步长和归一化梯度下降法尽管不使用方向平滑性的任何知识，但能够获得快速的路径相关性。逻辑回归上的实验证明，我们的收敛保证比基于L平滑性的传统理论更紧致。

    Mar, 2024

  • 一种非凸优化的随机拟牛顿方法

    本文提出了一种快速的随机拟牛顿方法，针对平滑性不均匀的情况，通过梯度剪切和方差减小，实现了最优的O(ε^(-3))样本复杂度，并通过简单的超参数调节实现了收敛加速，数值实验证明了该算法优于现有方法。

    Mar, 2024

  • Polyak 遇上无参数 Clipped 梯度下降

    本研究探讨了参数自由方法在修剪的梯度下降中的应用，提出了非精确Polyak步长方法，其收敛速度与拥有良好调整的超参数的修剪梯度下降方法在L平滑和（L0，L1）平滑假设下，收敛到最优解的速度渐近独立。在合成函数和LSTM、Nano-GPT和T5的实验中验证了我们的收敛结果和方法的有效性。

    May, 2024

  • 凸$(L_0,L_1)$-光滑优化的方法：剪辑、加速与自适应

    本研究解决了机器学习中优化问题的非光滑性问题，针对 convex $(L_0,L_1)$-光滑函数提出了新的收敛保证。研究通过改进梯度下降法的收敛速度，提出了一种新的加速方法，并扩展了结果到随机情况下，为自适应梯度下降法提供了新的收敛速率。

    Sep, 2024