Bridging the Gap Between Homogeneous and Heterogeneous Asynchronous Optimization Is Surprisingly Difficult
Lower bounds show heterogeneous asynchronous optimization cannot match homogeneous rates under standard similarity assumptions; strong interpolation plus local PL condition closes the gap.
The paper examines whether pessimistic optimal time complexities for asynchronous distributed optimization with heterogeneous workers (different data distributions) can be overcome. It proves improvement is provably impossible under widely used first- and second-order similarity assumptions for any randomized algorithm, and that the weak interpolation assumption alone is also insufficient. Combining strong interpolation with the local Polyak-Lojasiewicz condition yields a new time complexity bound matching the best-known homogeneous dependence on worker computation times without requiring identical data distributions.