First Provably Optimal Asynchronous SGD for Homogeneous and Heterogeneous Data
This thesis introduces a novel framework for asynchronous first-order stochastic optimization centered on heterogeneous worker speeds that remain fast, stable, and even provably optimal.
Overview
Artificial intelligence continues to scale through large neural networks trained on massive datasets using thousands of GPUs or TPUs. Yet most such training still relies on synchronous methods, where faster workers wait for slower ones, creating inefficiency in real systems with unavoidable computational heterogeneity. Removing synchronization seems natural, but asynchrony introduces staleness—updates computed with outdated models—which makes analysis difficult. As a result, the time complexity of asynchronous methods remains poorly understood.
In my PhD defense, I will present a framework developed in my dissertation for asynchronous first-order stochastic optimization centered on heterogeneous worker speeds. Within it, we show that asynchronous SGD can be provably optimal in time complexity when designed carefully. We introduce Ringmaster ASGD for homogeneous data, Ringleader ASGD for heterogeneous data, and ATA, which adapts to workers’ compute-time distributions to improve resource efficiency. Together, they demonstrate that asynchronous optimization can achieve optimal time complexity in theory while outperforming synchronous methods in practice.
Presenters
Brief Biography
Artavazd Maranjyan is a Ph.D. Candidate in Computer Science at King Abdullah University of Science and Technology (KAUST), advised by Prof. Peter Richtárik.
His work has been published in leading machine learning conferences such as ICML, ICLR, and UAI. He has received the CEMSE Dean’s List Award for academic and research excellence, and the Dean’s List Award upon joining KAUST.
Before starting his Ph.D., Artavazd earned his M.S. and B.S. degrees from Yerevan State University, where he co-authored several papers in harmonic analysis under the guidance of Prof. Martin Grigoryan.
