Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization
Abstract
We suggest a general oracle-based framework that captures parallel stochastic optimization in different parallelization 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 to study 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.
Cite
Text
Woodworth et al. "Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization." Neural Information Processing Systems, 2018.Markdown
[Woodworth et al. "Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization." Neural Information Processing Systems, 2018.](https://mlanthology.org/neurips/2018/woodworth2018neurips-graph/)BibTeX
@inproceedings{woodworth2018neurips-graph,
title = {{Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization}},
author = {Woodworth, Blake E and Wang, Jialei and Smith, Adam and McMahan, Brendan and Srebro, Nati},
booktitle = {Neural Information Processing Systems},
year = {2018},
pages = {8496-8506},
url = {https://mlanthology.org/neurips/2018/woodworth2018neurips-graph/}
}