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.

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.

This paper proposes an oracle model for parallel algorithms for stochastic convex programming. There are two main oracle models that are studied: In the first one, the algorithm has access to an stochastic unbiased estimator of the gradient for a given feasible point, and in the second one one can query an stochastic proximal oracle (that is, the proximal operator for a random instance f(.,z), All oracle access are obtained from i.i.d. Interestingly, the paper introduces sample access architectures that can reflect parallelism, delayed updates or intermittent communication, and it turns out the obtained lower bounds are optimal for most of these cases. However, in some situations the matching upper bound comes from an unnatural algorithms, so it is left as open problem whether the natural algorithms used in practice are optimal as well.

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. Papers published at the Neural Information Processing Systems Conference.