A fast randomized incremental gradient method for decentralized non-convex optimization

Understand

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.