Recent Advances in Distributed Non-Convex Optimization and Learning

Abstract: We consider a class of distributed non-convex optimization problems, in which a number of agents are connected by a communication network, and they collectively optimize a sum of (possibly non-convex and non-smooth) local objective functions. This type of problem has gained some recent popularities, especially in the application of distributed training of deep neural networks.

We first address the following general question: What is the fastest convergence rate that any properly defined distributed algorithms can achieve, and how to achieve those rates. In particular, we consider a class of unconstrained nonconvex problems and allow the agents to access local first-order gradient information. We develop a lower bound analysis that identifies difficult problem instances for any first-order method. Further, we develop a rate-optimal method whose rate matches our derived lower bound (up to a polylog factor).  The algorithm combines ideas from distributed consensus, nonlinear optimization, as well as classical signal processing techniques. Second, we present some recent extensions of the above work, including how to achieve optimal sample complexity, and how to deal with composite local functions efficiently. Finally, we provide some applications in distributed training of the neural networks, as well as in distributed control of wind farms, and discuss a number of open questions in the area.

Bio: Haoran Sun received his PhD degree in Electrical Engineering from the University of Minnesota, Minneapolis, MN, USA, in 2021. His research interests are primarily in the fields of distributed optimization, machine learning, and their applications in signal processing and wireless communications. His work has been awarded the Best Student Paper Award at the 52nd Asilomar Conference on Signals, Systems, and Computers, and the Best Readings in Machine Learning in Communications by the IEEE Communications Society (ComSoc).