A Fast Randomized Incremental Gradient Method for Decentralized Nonconvex Optimization

DOI10.1109/TAC.2021.3122586MaRDI QIDQ6077094zbMATH OpenOpenAlexFDO

Authors Ran Xin, Usman A. Khan, Soummya Kar

Publication date 24 September 2023

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

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

zbMATH Keywords

variance reductionincremental gradient methodsdecentralized nonconvex optimization

Mathematics Subject Classification ID

Systems theory; control (93-XX)

Abstract: We study decentralized non-convex finite-sum minimization problems described over a network of nodes, where each node possesses a local batch of data samples. In this context, we analyze a single-timescale randomized incremental gradient method, called GT-SAGA. GT-SAGA is computationally efficient as it evaluates one component gradient per node per iteration and achieves provably fast and robust performance by leveraging node-level variance reduction and network-level gradient tracking. For general smooth non-convex problems, we show the almost sure and mean-squared convergence of GT-SAGA to a first-order stationary point and further describe regimes of practical significance where it outperforms the existing approaches and achieves a network topology-independent iteration complexity respectively. When the global function satisfies the Polyak-Lojaciewisz condition, we show that GT-SAGA exhibits linear convergence to an optimal solution in expectation and describe regimes of practical interest where the performance is network topology-independent and improves upon the existing methods. Numerical experiments are included to highlight the main convergence aspects of GT-SAGA in non-convex settings.

Cited in

(7)

• DESTRESS: Computation-Optimal and Communication-Efficient Decentralized Nonconvex Finite-Sum Optimization
• ET-PDA: an event-triggered parameter distributed accelerated algorithm for economic dispatch problems
• Decentralized Accelerated Gradient Methods With Increasing Penalty Parameters
• On Nonconvex Decentralized Gradient Descent
• Gradient-free federated learning methods with l₁ and l₂-randomization for non-smooth convex stochastic optimization problems
• Convergence results of a nested decentralized gradient method for non-strongly convex problems
• Decentralized learning over a network with Nyström approximation using SGD

This page was built for publication: A Fast Randomized Incremental Gradient Method for Decentralized Nonconvex Optimization

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