High Probability Convergence of Stochastic Gradient Methods
High Probability Convergence of Stochastic Gradient Methods
复制标题
DOI：
10.48550/arxiv.2302.14843
复制
发表时间：
2023-02
期刊：
影响因子：
--
通讯作者：
Zijian Liu;Ta Duy Nguyen;Thien Hai Nguyen;Alina Ene;Huy L. Nguyen
中科院分区：
文献类型：
--
作者：
Zijian Liu;Ta Duy Nguyen;Thien Hai Nguyen;Alina Ene;Huy L. Nguyen
在这项工作中，我们描述了一种通用方法，可以显示出具有高可能性凸和非凸优化的高概率和次高斯噪声的概率。在以前的凸优化工作中，收敛性仅在预期中，或者结合取决于域的直径。取而代之的是，根据与最佳解决方案的初始距离，我们显示出高概率收敛性。算法使用的步骤大小类似于标准设置，并且与Lipschitz函数，光滑函数及其线性组合具有通用。该方法可以应用于非凸情况。我们演示了一个$ o（（1+ \ sigma^{2} \ log（1/\ delta））/t+\ sigma/\ sqrt {t}）$ cleangence $ temergence $ temerations $ t $ t $已知并且已知$ o（（（1+ \ sigma^{2} \ log（t/\ delta））/\ sqrt {t}）$当$ T $不知道SGD时，融合率是$ 1- \ delta $是所需的成功概率。这些界限改善了文献中的现有界限。此外，我们证明我们的技术可用于获得Adagrad-Norm的高概率（Ward等，2019），从而消除了以前的作品中有界梯度的假设。此外，我们的Adagrad-Norm技术扩展到标准的每坐标adagrad算法（Duchi等，2011），提供了第一个适应Adagrad的噪声高概率收敛性。
In this work, we describe a generic approach to show convergence with high probability for both stochastic convex and non-convex optimization with sub-Gaussian noise. In previous works for convex optimization, either the convergence is only in expectation or the bound depends on the diameter of the domain. Instead, we show high probability convergence with bounds depending on the initial distance to the optimal solution. The algorithms use step sizes analogous to the standard settings and are universal to Lipschitz functions, smooth functions, and their linear combinations. This method can be applied to the non-convex case. We demonstrate an $O((1+\sigma^{2}\log(1/\delta))/T+\sigma/\sqrt{T})$ convergence rate when the number of iterations $T$ is known and an $O((1+\sigma^{2}\log(T/\delta))/\sqrt{T})$ convergence rate when $T$ is unknown for SGD, where $1-\delta$ is the desired success probability. These bounds improve over existing bounds in the literature. Additionally, we demonstrate that our techniques can be used to obtain high probability bound for AdaGrad-Norm (Ward et al., 2019) that removes the bounded gradients assumption from previous works. Furthermore, our technique for AdaGrad-Norm extends to the standard per-coordinate AdaGrad algorithm (Duchi et al., 2011), providing the first noise-adapted high probability convergence for AdaGrad.