Sign up to receive the latest Insights posts in your inbox.


Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization

The authors 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, as well as lower bounds for several specific parallel optimization settings. They highlight gaps between lower and upper bounds on the oracle complexity, and cases where the “natural” algorithms are not known to be optimal.