Decentralized Non-Convex Optimization and Learning over Heterogeneous Networks

We study decentralized optimization and learning problems, where a network of n nodes, such as machines, edge devices, and robot swarms, cooperatively minimizes a finite sum of cost functions by means of local information processing and communication with neighboring nodes. Decentralized optimization has emerged as a promising framework for large-scale machine learning and signal processing problems. It is fundamentally important in scenarios where data samples are geographically distributed and/or centralized data processing is infeasible due to computation and communication overhead or data privacy concerns. Although decentralized optimization has been extensively researched under convexity over the past decade, the field still lacks a sound understanding of how to achieve optimal complexities when the underlying problems of interest become non-convex. In this thesis, we construct provably efficient decentralized stochastic firstorder gradient methods for several important classes of non-convex problems with online or offline data, with the help of gradient tracking and variance reduction techniques. In particular, we prove that the proposed algorithms, in regimes of practical significance, achieve network topology-independent computation complexities that match the centralized lower bounds for the corresponding problem classes. This network topology-independence property further leads to the linear speedup of decentralized stochastic optimization algorithms under arbitrary network topologies, in that, the total number of gradient computations at each node is reduced by a factor of 1/n compared to the centralized optimal algorithms that perform all gradient computations at a single node. We also discuss several techniques to balance the computationcommunication trade-offs in the proposed algorithms. Our algorithmic frameworks and their companion analyses are constructed and developed in a systematic manner and may be generalized to other problems of interest. Extensive numerical experiments with both real and synthetic datasets are included to demonstrate our main theoretical results.