Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization
This work addresses foundational gaps in parallel stochastic optimization theory, which is incremental but important for researchers in optimization and distributed computing.
The paper introduces an oracle-based framework to model parallel stochastic optimization via dependency graphs and derives generic lower bounds, applying them to settings like delayed updates and intermittent communication to reveal gaps between lower and upper bounds on oracle complexity.
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.