Distributed Random Reshuffling Over Networks
| Autor: | Kun Huang, Xiao Li, Andre Milzarek, Shi Pu, Junwen Qiu |
|---|---|
| Rok vydání: | 2023 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Machine Learning Computer Science - Distributed Parallel and Cluster Computing Optimization and Control (math.OC) Signal Processing FOS: Mathematics Computer Science - Multiagent Systems Distributed Parallel and Cluster Computing (cs.DC) Electrical and Electronic Engineering Mathematics - Optimization and Control Machine Learning (cs.LG) Multiagent Systems (cs.MA) |
| Zdroj: | IEEE Transactions on Signal Processing. 71:1143-1158 |
| ISSN: | 1941-0476 1053-587X |
| Popis: | In this paper, we consider distributed optimization problems where $n$ agents, each possessing a local cost function, collaboratively minimize the average of the local cost functions over a connected network. To solve the problem, we propose a distributed random reshuffling (D-RR) algorithm that invokes the random reshuffling (RR) update in each agent. We show that D-RR inherits favorable characteristics of RR for both smooth strongly convex and smooth nonconvex objective functions. In particular, for smooth strongly convex objective functions, D-RR achieves $\mathcal{O}(1/T^2)$ rate of convergence (where $T$ counts epoch number) in terms of the squared distance between the iterate and the global minimizer. When the objective function is assumed to be smooth nonconvex, we show that D-RR drives the squared norm of gradient to $0$ at a rate of $\mathcal{O}(1/T^{2/3})$. These convergence results match those of centralized RR (up to constant factors) and outperform the distributed stochastic gradient descent (DSGD) algorithm if we run a relatively large number of epochs. Finally, we conduct a set of numerical experiments to illustrate the efficiency of the proposed D-RR method on both strongly convex and nonconvex distributed optimization problems. 20 pages, 13 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|