W1. Practical motivation for the DSO model. I am not convinced that there is a realistic setting in which each machine can only expose a separation oracle for its local constraint set, while the machines jointly optimize a linear objective. The examples in Section 1 do not fit this template: structured SVM training has a quadratic regularized objective, and adversarial training is typically nonconvex. The facet counting example argues that explicit constraints are too large to transmit. However, all main results target small or constant d, where that facet count is polynomial. The empirical study does not instantiate the DSO model either. Each server holds 2ni explicit inequalities, and the oracle returns only a binary feasibility indicator (a membership oracle rather than a separation oracle). The inner problems are also solved by HiGHS on the explicit constraints. Prior work on essentially the same model gives concrete instantiations (see W5), and the paper would benefit from adopting similar ones.
W2. Inconsistent naming and an overclaim on the problem class. The paper uses different names for the problem it solves. The introduction and Section 1.1 speak of convex programs. The abstract, Theorems 1.4 and 1.5, and Appendix A.1 instead call the problem distributed linear programming, even though Appendix A.1 defines it over arbitrary closed convex sets. Prior work calls linear optimization over an intersection of convex sets distributed convex optimization (e.g., Bürger et al.; Vempala et al., 2020, Theorem 1.12), so either name can be defended, but the paper should define one term and use it consistently.
W3. The algorithms are hard to follow from the main text. The main text contains no pseudocode.
W4. The comparison with prior work in Table 1 is not made on equal terms.
- Nature of the guarantees. The linear programming algorithms in this paper are randomized: they return an exact solution on termination, with communication bounded in expectation. Please state, for every entry on both sides of the table, whether the bound is deterministic, in expectation, or with high probability.
- Notation. Vempala et al. (2020) state their bounds as O~(sd3L+d4L) in the coordinator model and O~(sd+d4L) in the blackboard model, where O~ suppresses polylog(sndL) factors. The claimed improvement consists of removing logn factors, so it lies entirely within what that notation hides. Yet Table 1 expands those factors only partially (O(sd3Llogn) in one row, O~(sdlogn) in the other). Both columns should list explicit factors. The text should also note that for constant d, Vempala et al. (2020) already report Θ~(sL) in the coordinator model, so improvements there are at most polylogarithmic.
- Problem setting. It is unclear that both papers solve the same problem. The exact bounds here assume that the feasible region, or an optimizer, lies in a public box (Section 1.1, Theorem G.3, Lemma J.5), and this is not stated in Theorems 1.4 and 1.5. The formulation of Vempala et al. (2020) contains no such promise and also covers feasibility testing.
W5. Missing related work on the same model. Bürger, Notarstefano and Allgöwer study essentially the same setting. Each processor holds a closed convex set that cannot be encoded with finite data, the set is accessed only through a local cutting plane (separation) oracle, and the goal is to optimize a linear objective over the intersection. Their cutting plane consensus algorithm also exploits the fact that the optimum is determined by a basis of at most d constraints, building on constraints consensus (Notarstefano and Bullo, 2011). The submission neither cites nor compares against this work, which contradicts the claim in Appendix A.2 that the DSO model is the first distributed version of the separation oracle model.
Relatedly, Ghadiri et al. (STOC 2024) improve communication bounds for approximately solving LP in the coordinator and blackboard models, and should be discussed.
Bürger, M., Notarstefano, G., & Allgöwer, F. (2014). A polyhedral approximation framework for convex and robust distributed optimization. IEEE Transactions on Automatic Control, 59(2), 384–395. https://doi.org/10.1109/TAC.2013.2281883
Ghadiri, M., Lee, Y. T., Padmanabhan, S., Swartworth, W., Woodruff, D. P., & Ye, G. (2024). Improving the bit complexity of communication for distributed convex optimization. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (pp. 1130–1140). Association for Computing Machinery. https://doi.org/10.1145/3618260.3649787
We strengthened the motivation with a concrete network-capacity example. Each server can run max-flow on its own network and return a violated minimum-cut inequality, rather than transmitting the network. We also cited earlier cutting-plane consensus work using the same type of oracle interface.
We clarified why this access model is useful: a server’s feasible set may be defined by a large network or other local optimization problem, rather than a short list of inequalities. The model asks how many local feasibility/separation queries are needed to optimize a small set of shared decisions. Our results quantify that coordination cost.
We clarified that the existing synthetic experiments illustrate the coordination behavior predicted by the analysis; they are not an end-to-end application benchmark. We added the network-capacity example as a concrete motivation, without claiming to have evaluated it experimentally.
We added a network-capacity planning example. A small vector x represents shared investments with linear cost; server i holds a large network with capacities that depend affinely on x. A max-flow computation either verifies its demand or returns a violated minimum-cut inequality in x. Thus the required separation oracle is a standard local algorithm, even when sending the entire network is expensive.
Not directly for general matching or integer knapsack. Standard matching formulations have dimension growing with graph size, while an exact separation oracle for the integer knapsack hull would itself be computationally difficult. Our network-planning example gives a more direct combinatorial application: local max-flow algorithms implement the separation queries, and our bounds control how often servers must be queried, not the cost of each max-flow computation.