Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization
Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization
复制标题
DOI：
--
复制
发表时间：
2018-05
期刊：
影响因子：
--
通讯作者：
Blake E. Woodworth;Jialei Wang;H. B. McMahan;N. Srebro
中科院分区：
文献类型：
--
作者：
Blake E. Woodworth;Jialei Wang;H. B. McMahan;N. Srebro
我们提出了一个基于Oracle的通用框架，该框架捕获由依赖图描述的不同并行化环境下的并行随机优化，并根据依赖图推导出通用的下界。然后，我们使用该框架并推导出下界来研究几种特定的并行优化设置，包括延迟更新和间歇通信的并行处理。我们强调了Oracle复杂性的下界和上界之间的差距，以及已知“自然”算法不是最优的情况。
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.