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

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.