Why random reshuffling beats stochastic gradient descent
Why random reshuffling beats stochastic gradient descent
复制标题
DOI：
10.1007/s10107-019-01440-w
复制
发表时间：
2019-10-29
影响因子：
2.7
通讯作者：
Parrilo, P. A.
中科院分区：
文献类型：
--
作者：
Gurbuzbalaban, M.;Ozdaglar, A.;Parrilo, P. A.
分析了随机重排(RR)方法的收敛速度，该方法是一种随机一阶增量算法，用于最小化有限个凸分量函数和。RR按周期进行，挑选统一的随机顺序(排列)，并根据该顺序一次处理一个分量函数，即在每个周期，每个分量函数被采样而不从集合中替换。虽然在数值上观察到RR算法优于随机梯度下降算法(SGD)，但其收敛速度的刻画一直是一个悬而未决的问题。本文在和函数是强凸的情况下，给出了RR及其变种的各种收敛速度结果，从而回答了这个问题。我们首先研究二次分量函数，证明了步长αk=Theta(1/k)的RR所产生的迭代的期望距离需要将步长调整到强凸性常数)。我们的主要结果表明，当分量函数是二次或光滑的(海森矩阵上的Lipschitz假设)时，迭代平均的RR和递减步长αk=Theta(1/ks)的SGD。我们的分析借鉴了Polyak-Ruppert平均理论，并依赖于将独立的周期梯度误差解耦为周期上的独立项和由αK2主导的另一项。这允许我们将大数定律应用于周期梯度误差的适当加权版本，其中权重取决于步长。我们还给出了不同项衰减率的高概率收敛速度估计，并允许我们提出一个收敛速度为O(1k2)的修正RR。
We analyze the convergence rate of the random reshuffling (RR) method, which is a randomized first-order incremental algorithm for minimizing a finite sum of convex component functions. RR proceeds in cycles, picking a uniformly random order (permutation) and processing the component functions one at a time according to this order, i.e., at each cycle, each component function is sampled without replacement from the collection. Though RR has been numerically observed to outperform its with-replacement counterpart stochastic gradient descent (SGD), characterization of its convergence rate has been a long standing open question. In this paper, we answer this question by providing various convergence rate results for RR and variants when the sum function is strongly convex. We first focus on quadratic component functions and show that the expected distance of the iterates generated by RR with stepsize alpha k=Theta(1/ks) requiring adjusting the stepsize to the strong convexity constant).Our main result shows that when the component functions are quadratics or smooth (with a Lipschitz assumption on the Hessian matrices), RR with iterate averaging and a diminishing stepsize alpha k=Theta(1/ks) rate of SGD. Our analysis draws on the theory of Polyak-Ruppert averaging and relies on decoupling the dependent cycle gradient error into an independent term over cycles and another term dominated by alpha k2. This allows us to apply law of large numbers to an appropriately weighted version of the cycle gradient errors, where the weights depend on the stepsize. We also provide high probability convergence rate estimates that shows decay rate of different terms and allows us to propose a modification of RR with convergence rate O(1k2).