Graph oracle models, lower bounds, and gaps for parallel stochastic optimization
Date
2018-12-01
DOI
Authors
Woodworth, Blake
Wang, Jialei
Smith, Adam
McMahan, Brendan
Srebro, Nati
Version
Published version
OA Version
Citation
Blake Woodworth, Jialei Wang, Adam Smith, Brendan McMahan, Nati Srebro. 2018. "Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization." Advances in Neural Information Processing Systems 31 (NIPS 2018), pp. 8505-8515.
Abstract
We suggest a general oracle-based framework that captures different parallel stochastic optimization settings described by a dependency graph, and derive generic lower bounds in terms of this graph. We then use the framework and derive lower bounds for several specific parallel optimization settings, including delayed updates and parallel processing with intermittent communication. We highlight gaps between lower and upper bounds on the oracle complexity, and cases where the "natural" algorithms are not known to be optimal.