论文标题
闭合SGD的收敛间隙而无需更换
Closing the convergence gap of SGD without replacement
论文作者
论文摘要
无需替换抽样的随机梯度下降在实践中广泛用于模型训练。但是，绝大多数SGD分析假设数据是用替换对数据进行采样的，当功能最小化时，$ \ Mathcal {O} \ left（\ frac {1} {1} {t} \ right）$ rate可以在SGD运行$ t $ itererations时建立。在不替代的情况下（SGDO）在SGD上起作用的最新突破性（SGDO）建立了一个$ \ MATHCAL {o} \ left（\ frac {n} {t^2} \ right）$收敛率，当功能最小化时，并且是$ n $平滑功能的总和， $ \ mathcal {o} \ left（\ frac {1} {t^2}+\ frac {n^3} {t^3} \ right）$ rate of Quadratics的总和。另一方面，最紧的已知下限假设$ω\左（\ frac {1} {t^2}+\ frac {n^2} {n^2} {t^3} \ right）$ rate，从而打开了在总体情况下打开更好的sgdo convergence速率的可能性。在本文中，我们缩小了这一差距，并证明没有替换的SGD达到了$ \ Mathcal {o} \ left（\ frac {1} {1} {t^2}+\ frac {n^2} {n^2} {t^3} \ right），当功能的总和Quadrions Quadrions Quadrations时$ω\ left（\ frac {n} {t^2} \ right）$用于强烈凸功能，这是光滑函数的总和。
Stochastic gradient descent without replacement sampling is widely used in practice for model training. However, the vast majority of SGD analyses assumes data is sampled with replacement, and when the function minimized is strongly convex, an $\mathcal{O}\left(\frac{1}{T}\right)$ rate can be established when SGD is run for $T$ iterations. A recent line of breakthrough works on SGD without replacement (SGDo) established an $\mathcal{O}\left(\frac{n}{T^2}\right)$ convergence rate when the function minimized is strongly convex and is a sum of $n$ smooth functions, and an $\mathcal{O}\left(\frac{1}{T^2}+\frac{n^3}{T^3}\right)$ rate for sums of quadratics. On the other hand, the tightest known lower bound postulates an $Ω\left(\frac{1}{T^2}+\frac{n^2}{T^3}\right)$ rate, leaving open the possibility of better SGDo convergence rates in the general case. In this paper, we close this gap and show that SGD without replacement achieves a rate of $\mathcal{O}\left(\frac{1}{T^2}+\frac{n^2}{T^3}\right)$ when the sum of the functions is a quadratic, and offer a new lower bound of $Ω\left(\frac{n}{T^2}\right)$ for strongly convex functions that are sums of smooth functions.
