The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication

This work provides a theoretical understanding of the fundamental limits and optimal algorithms for distributed stochastic convex optimization under intermittent communication, which is important for researchers and practitioners designing efficient distributed optimization systems.

This paper resolves the min-max complexity of distributed stochastic convex optimization in the intermittent communication setting, where M machines compute K stochastic gradient estimates per round over R rounds. They present a novel lower bound with a matching upper bound that establishes an optimal algorithm.