Improved Convergence in High Probability of Clipped Gradient Methods with Heavy Tailed Noise
Improved Convergence in High Probability of Clipped Gradient Methods with Heavy Tailed Noise
复制标题
DOI：
--
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Ta Duy Nguyen;Thien Nguyen;Alina Ene;Huy Nguyen
中科院分区：
文献类型：
--
作者：
Ta Duy Nguyen;Thien Nguyen;Alina Ene;Huy Nguyen
在这项工作中，我们研究了当噪声分布具有重尾，即对于某些\(1 < p\leq2\)具有有界的\(p\)阶矩时，截断梯度方法的高概率收敛性。在此设定下的先前工作遵循相同的方法，即使用集中不等式和带有并集界的归纳论证来对所有迭代中的迭代值进行界定。这种方法导致失败概率增加\(T\)倍，其中\(T\)是迭代次数。我们转而提出一种新的分析方法，该方法基于对精心选择的上鞅序列的矩生成函数进行界定。我们改进了具有截断梯度的多种算法在收敛保证中对\(T\)的依赖关系，这些算法包括用于凸目标的随机（加速）镜像下降算法和用于非凸目标的随机梯度下降算法。我们的高概率界达到了最优收敛速率，并与当前已知的最佳期望界相匹配。我们的方法自然地允许算法在时间范围未知时使用随时间变化的步长和截断参数，而使用先前工作中的技术似乎很难甚至不可能做到这一点。此外，我们表明在截断随机镜像下降的情况下，在设置步长和截断参数时不需要几个问题常数，包括到最优解的初始距离。
In this work, we study the convergence in high probability of clipped gradient 1 methods when the noise distribution has heavy tails, i.e., with bounded p th mo-2 ments, for some 1 < p ≤ 2 . Prior works in this setting follow the same recipe of 3 using concentration inequalities and an inductive argument with union bound to 4 bound the iterates across all iterations. This method results in an increase in the 5 failure probability by a factor of T , where T is the number of iterations. We in-6 stead propose a new analysis approach based on bounding the moment generating 7 function of a well chosen supermartingale sequence. We improve the dependency 8 on T in the convergence guarantee for a wide range of algorithms with clipped 9 gradients, including stochastic (accelerated) mirror descent for convex objectives 10 and stochastic gradient descent for nonconvex objectives. Our high probability 11 bounds achieve the optimal convergence rates and match the best currently known 12 in-expectation bounds. Our approach naturally allows the algorithms to use time-13 varying step sizes and clipping parameters when the time horizon is unknown, 14 which appears difficult or even impossible using the techniques from prior works. 15 Furthermore, we show that in the case of clipped stochastic mirror descent, several 16 problem constants, including the initial distance to the optimum, are not required 17 when setting step sizes and clipping parameters. 18