On Distributed Separation Oracles and the Communication Cost of Optimization

We introduce a new model for studying distributed optimization, that we call the distributed separation oracle model. Here one is allowed to make separation oracle queries to one of $s$ constraint sets ${\mathcal{C}}_i$ at a time. In this model we show that one can solve linear programming with $O(s+L\log s)$ queries, for constant $d,$ where $L$ represents the bit precision to which the underlying constraints are specified. This improves on the na\"ive approach of making $s$ queries per round to simulate separation oracle queries to $\bigcap {\mathcal{C}}_i$, and suggests that further non-trivial algorithms may be possible in this model. We also show that a similar improvement is possible in constant dimensions, even for adversarial separation oracles, with no bit-precision limits on the query results. We also study the problem of solving linear programs in a distributed setting with many servers. In the blackboard and coordinator models of communication, we develop algorithms for linear programming, and related convex optimization problems that improve over the previous best of [Vempala, Woodruff, Wang '20]. Specifically, we give an algorithm using $O(s{d}^{3}L+\text{poly}(d\log n)\cdot L\sqrt{s}$ communication in the coordinator model with $s$ servers, and $O(sd)+(L\log n+{\log }^{2}n+\sqrt{s})\log (sd)\cdot \text{poly}(d)$ communication in the blackboard model.