Variance-Reduced Stochastic Learning by Networked Agents Under Random Reshuffling

DOI10.1109/TSP.2018.2872003MaRDI QIDQ4628193zbMATH OpenOpenAlexWikidataFDO

Authors Kun Yuan, Bicheng Ying, Jiageng Liu, Ali H. Sayed

Publication date 6 March 2019

Published in IEEE Transactions on Signal Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.01384

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05) Nonparametric inference (62G99) Decentralized systems (93A14)

Abstract: A new amortized variance-reduced gradient (AVRG) algorithm was developed in cite{ying2017convergence}, which has constant storage requirement in comparison to SAGA and balanced gradient computations in comparison to SVRG. One key advantage of the AVRG strategy is its amenability to decentralized implementations. In this work, we show how AVRG can be extended to the network case where multiple learning agents are assumed to be connected by a graph topology. In this scenario, each agent observes data that is spatially distributed and all agents are only allowed to communicate with direct neighbors. Moreover, the amount of data observed by the individual agents may differ drastically. For such situations, the balanced gradient computation property of AVRG becomes a real advantage in reducing idle time caused by unbalanced local data storage requirements, which is characteristic of other reduced-variance gradient algorithms. The resulting diffusion-AVRG algorithm is shown to have linear convergence to the exact solution, and is much more memory efficient than other alternative algorithms. In addition, we propose a mini-batch strategy to balance the communication and computation efficiency for diffusion-AVRG. When a proper batch size is employed, it is observed in simulations that diffusion-AVRG is more computationally efficient than exact diffusion or EXTRA while maintaining almost the same communication efficiency.

Cited in

(5)

• Experiential and Stochastic Learning Algorithms Based on the Probability of a Fuzzy Event and Modified Fuzzy Metric Distance in Intelligent Robotic Part Micro-Assembly
• scientific article; zbMATH DE number 7307473 (Why is no real title available?)
• Distributed policy gradient with variance reduction in multi-agent reinforcement learning
• Fast decentralized nonconvex finite-sum optimization with recursive variance reduction
• Linear convergence of cyclic SAGA

This page was built for publication: Variance-Reduced Stochastic Learning by Networked Agents Under Random Reshuffling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4628193)