NCCR Automation Seminar: Asynchronous optimization through the lens of control theory by Mikael Johansson

With the ubiquitous digitalization of society, decision problems are rapidly expanding in size and scope. Increasingly often, we face problems where data, computations, and decisions need to be distributed on multiple nodes. These nodes may be individual cores in a CPU, different processors in a multi-CPU platform, or servers in a geographically dispersed cluster. Insisting that such multi-node systems operate synchronously limits their scalability, since the performance is then dictated by the slowest node, and the system becomes fragile to node failures. Hence, there is a strong current interest in developing asynchronous algorithms for optimal decision-making. However, the dynamics of asynchronous iterations are much richer than their synchronous counterparts and quantifying the impact of asynchrony on the convergence rate is mathematically challenging. 

In this talk, I will describe some of our recent efforts in analyzing and designing asynchronous optimization algorithms with strong convergence guarantees.
 
I will begin by introducing novel convergence results for asynchronous iterations that appear in the analysis of parallel and distributed optimization algorithms. The results are simple to apply and give explicit estimates for how the degree of asynchrony impacts the convergence rates of the iterates. Our results shorten, streamline and strengthen existing convergence proofs for several asynchronous  optimization methods and allow us to establish convergence guarantees for popular algorithms that were thus far lacking a complete theoretical understanding. 
 
I will then proceed to discuss how one can design delay-adaptive optimization algorithms. In contrast to earlier efforts that used fixed step-sizes based on the worst-case delay, these algorithms measure the actual information delays in the system and adapt the step-sizes on-line to maintain a fast and stable convergence. We will also discuss alternative mechanisms that use fixed step-sizes but drop information that is considered too old.
 
Finally, if time permits, I will discuss classes of problems that admit delay-agnostic algorithms. Such algorithms can be tuned without knowledge of the level of asynchrony that they will experience when they are deployed. Our analysis proves that these algorithms converge for all levels of asynchrony, and quantifies how the convergence times increase as the information delays grow larger.
 
This talk is based on joint work with Hamid Reza Feyzmahdavian, Xuyang Wu, Sindri Magnusson and Changxin Liu. 

website: https://people.kth.se/~mikaelj/