Distributed Random Reshuffling Methods With Improved Convergence

This article proposes two distributed random reshuffling (RR) methods, namely gradient tracking with RR (GT-RR) and exact diffusion with RR (ED-RR), to solve the distributed optimization problem over a connected network, where a set of agents aim to minimize the average of their local cost functions. Both algorithms invoke RR update for each agent, inherit favorable characteristics of RR for minimizing smooth nonconvex objective functions, and improve the performance of previous distributed RR methods both theoretically and empirically. Specifically, both GT-RR and ED-RR achieve the convergence rate of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal {O}(1/[(1-\lambda)^{1/3}m^{1/3}T^{2/3}])$</tex-math></inline-formula> in driving the (minimum) expected squared norm of the gradient to zero, where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$T$</tex-math></inline-formula> denotes the number of epochs, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$m$</tex-math></inline-formula> is the sample size for each agent, and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$(1-\lambda)$</tex-math></inline-formula> represents the spectral gap of the mixing matrix. When the objective functions further satisfy the Polyak–Łojasiewicz condition, we show GT-RR and ED-RR both achieve <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal {O}(1/[(1-\lambda)mT^{2}])$</tex-math></inline-formula> convergence rate in terms of the averaged expected differences between the agents' function values and the global minimum value. Notably, both results are comparable to the convergence rates of centralized RR methods (up to constant factors depending on the network topology) and outperform those of previous distributed RR algorithms.