acceptodds
Under review as a conference paper at ICLR 2027

On Distributed Separation Oracles and the Communication Cost of Optimization

Abstract

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 constraint sets at a time. In this model we show that one can solve linear programming with queries, for constant where represents the bit precision to which the underlying constraints are specified. This improves on the na\"ive approach of making queries per round to simulate separation oracle queries to , 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 communication in the coordinator model with servers, and communication in the blackboard model.

Primary area:
optimization
Keywords:
distributed algorithms, linear programming, convex optimization

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_YHp3OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces a new model in distributed optimization, to which they call distributed separation oracle (DSO) model. In this model, an algorithm is allowed to perform s separation oracle queries in one single query. One thing they show in this model is naturally that one can solve LP of constant dimension with only O(s+Llogs)O(s + L log s) queries, for bit precision LL. They also study solving LPs with multiple servers, giving algorithms with O(sd3L+poly(dlogn)L(s))O(sd^3L+poly(dlogn)L \sqrt(s)) communication in the coordinator model with ss servers and also a communication of O(sd)+Llogn+log2n+(s)log(sd)poly(d)O(sd) +L log n +log^2 n +\sqrt(s) log(sd) poly(d) in the blackboard model.

Critical strengths
  • The paper seems sound

  • The problem is fundamental

  • The writing is usually clear

Critical weaknesses
  • The main weakness in my opinion is the model. It seems tailored to the result, meaning that I am not sure why can one assume that in any case. It is relatively strong and arbitrary assumption in my opinion that one could have access to such oracle. I would at least expect better motivation.

  • Not enough motivation. Please provide much better motivation for why another model is necessary in this area.

  • The experiments mainly demonstrate the theoretical phenomena and do not provide evidence for any practical use cases.

Questions for authors
  • Could you please give better motivation for the model? why should one study it? i.e., in what realistic setting does it occur that one has access to such an oracle?

  • Could you solve classic combinatorial optimization problems in this model with faster guarantees? maximum matching, knapsack, etc?

1 comment

The main weakness in my opinion is the model. It seems tailored to the result, meaning that I am not sure why can one assume that in any case. It is relatively strong and arbitrary assumption in my opinion that one could have access to such oracle. I would at least expect better motivation.

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.

Not enough motivation. Please provide much better motivation for why another model is necessary in this area.

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.

The experiments mainly demonstrate the theoretical phenomena and do not provide evidence for any practical use cases.

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.

Could you please give better motivation for the model? why should one study it? i.e., in what realistic setting does it occur that one has access to such an oracle?

We added a network-capacity planning example. A small vector xx represents shared investments with linear cost; server ii holds a large network with capacities that depend affinely on xx. A max-flow computation either verifies its demand or returns a violated minimum-cut inequality in xx. Thus the required separation oracle is a standard local algorithm, even when sending the entire network is expensive.

Could you solve classic combinatorial optimization problems in this model with faster guarantees? maximum matching, knapsack, etc?

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.

Reviewer_NsKjOpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proves that linear programming can be solved with O(s+Llog⁡s)O(s+L \log s) queries for constant dd and fixed bit precision LL in the distributed separation oracle model. Further, they extend to distribution setting with many servers. In blackboard and coordinator models of communication, they improved the communication complexity from the previous best algorithms.

Critical strengths

This paper proves that any distributed convex program over s servers can be exactly solved by resolving only O(d)O(d) subproblems which only involve a subset of servers. Using this intuition, this paper can improve the query complexity to O(s+Llog⁡s)O(s+L \log s), which ha sonly a log⁡s\log s gap between the lower bound Ω(s+L)\Omega(s+L).

Critical weaknesses
  1. DSO requires computation of convex and affine hulls as well as exact solutions to mulitple local optimization problems. However, this paper neglects the computation complexity to solve this local problems.
  2. The bound O(s+Llogs)O(s+L log s) requires d is fixed, and the bound depends strongly on the dimension dd. It is hard to extend the results to general continuous and high-dimensional settings.
  3. The experiments only use the synthetic data and limited feature dimension d=3d=3. The experiment setting is a little simple, and I am not sure whether the results can be extended to a more practical setting.
Questions for authors

n/a

1 comment

DSO requires computation of convex and affine hulls as well as exact solutions to mulitple local optimization problems. However, this paper neglects the computation complexity to solve this local problems.

We added an appendix note separating oracle-query complexity from local computation. The original hull-enumeration construction proves the query bound but can take exponential time in LL. We also described how exact oracle LP methods of Dadush, Végh and Zambelli yield polynomial arithmetic work in the bounded-precision setting, excluding the computation performed inside each server’s oracle.

The bound O(s+Llog⁡s)O(s+L\log s) requires d is fixed, and the bound depends strongly on the dimension dd. It is hard to extend the results to general continuous and high-dimensional settings.

Agreed: the near-optimal bound is for fixed dd. We now write it as Od(s+Llog⁡(s+1))O_d(s+L\log(s+1)) and emphasize the intended regime of a small shared decision vector and potentially large local instances. We do not claim practical efficiency for arbitrary high-dimensional problems.

The experiments only use the synthetic data and limited feature dimension d=3d=3. The experiment setting is a little simple, and I am not sure whether the results can be extended to a more practical setting.

The d=3d=3 experiment was intended to isolate coordination behavior in the small-dimensional regime, rather than establish broad practical performance. We clarified this scope and added a concrete network-planning application to motivate the setting. We have not presented that application as a new experiment. Additionally, we would like to emphasize that the primary contribution of our paper is the introduction of the model and the main theoretical guarantees. Our experiments serve as a simple proof-of-concept complementing our theoretical results and have not been heavily optimized.

Reviewer_2xdbOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies distributed linear optimization: the goal is to minimize a linear functional ⟨c,x⟩\langle c, x \rangle over the intersection ⋂i=1sCi\bigcap_{i=1}^{s} C_i of ss convex constraint sets, each held by a different server. The authors introduce the Distributed Separation Oracle (DSO) model, in which the algorithm interacts with the servers only through separation oracle queries. A query specifies a point xx and a server ii, and the server either certifies x∈Cix \in C_i or returns a hyperplane separating xx from CiC_i. The goal is to beat the naive cutting plane approach, which queries all ss servers in every iteration.

In the bit limited DSO setting, the constraints, the objective, and the returned hyperplanes have LL bit coefficients, and the feasible region is nonempty and contained in a public box. There, the authors give a randomized algorithm that returns an exact minimizer using O(sd)+Ls⋅poly(d)O(sd) + L\sqrt{s} \cdot \mathrm{poly}(d) expected queries in dimension dd (Theorem 1.1), and O(s+Llog⁡s)O(s + L\log s) expected queries for constant dd (Theorem 1.2). They complement this with an Ω(s+L)\Omega(s + L) lower bound that holds even for finding a feasible point, so the constant dimension bound is optimal up to a logarithmic factor. Without bit precision limits, they show that for constant dd, a feasible point can be found with probability at least 3/43/4 using O(s/α+sαlog⁡slog⁡(1/ε))O(s/\alpha + s^{\alpha}\log s \log(1/\varepsilon)) queries for any α>0\alpha > 0, provided the feasible region has volume at least ε\varepsilon (Theorem 1.3).

The paper also studies distributed linear programming with explicit constraints in the coordinator and blackboard models of communication, where server ii holds nin_i half spaces and n=∑inin = \sum_i n_i. The authors obtain total communication O(sd3L)+poly(dlog⁡n)⋅LsO(sd^3L) + \mathrm{poly}(d\log n) \cdot L\sqrt{s} in the coordinator model (Theorem 1.4) and O(sd)+(Llog⁡n+log⁡2n+s)log⁡(sd)⋅poly(d)O(sd) + (L\log n + \log^2 n + \sqrt{s})\log(sd) \cdot \mathrm{poly}(d) in the blackboard model (Theorem 1.5). They present these as improvements over Vempala et al. (2020), since the leading term linear in ss no longer carries a log⁡n\log n factor. The protocols extend to an additional global convex constraint, which covers semidefinite programming (Theorem 1.6), and yield communication bounds for (1+ε)(1 + \varepsilon) approximate ℓp\ell_p regression with p>2p > 2 (Theorem 1.7).

Critical strengths

S1. The paper obtains results across a broad range of settings, covering both query complexity and communication complexity:

  • the general DSO model without bit precision limits (Theorem 1.3);
  • the bit limited DSO model (Theorems 1.1 and 1.2, together with an Ω(s+L)\Omega(s + L) lower bound);
  • the coordinator and blackboard communication models (Theorems 1.4 and 1.5);
  • extensions to a global convex constraint that covers SDP (Theorem 1.6) and to ℓp\ell_p regression (Theorem 1.7).

S2. The paper includes a dedicated technical overview (Section 1.2). It isolates the four main technical mechanisms (active set sampling, Diophantine discretization for exact optimization, randomized exploration, and nested multiplicative weights) and contrasts each with prior approaches. This makes a long and technical paper much easier to navigate.

S3. The small simulation study in Section 5 is consistent with the theory. On distributed Chebyshev regression, the proposed method needs roughly 1 to 3 global synchronization rounds, versus roughly 8 to 16 for the baseline of Vempala et al. (2020). Its round count stays nearly flat as nin_i grows, and it shows much lower variance across trials.

Critical weaknesses

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 dd, where that facet count is polynomial. The empirical study does not instantiate the DSO model either. Each server holds 2ni2n_i 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)\tilde{O}(sd^3L + d^4L) in the coordinator model and O~(sd+d4L)\tilde{O}(sd + d^4L) in the blackboard model, where O~\tilde{O} suppresses polylog(sndL)\mathrm{polylog}(sndL) factors. The claimed improvement consists of removing log⁡n\log n factors, so it lies entirely within what that notation hides. Yet Table 1 expands those factors only partially (O(sd3Llog⁡n)O(sd^3L\log n) in one row, O~(sdlog⁡n)\tilde{O}(sd\log n) in the other). Both columns should list explicit factors. The text should also note that for constant dd, Vempala et al. (2020) already report Θ~(sL)\tilde{\Theta}(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 dd 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

Questions for authors

Q1. Can the authors give a concrete application in which (i) each server can answer separation queries for its local set but cannot cheaply transmit it, and (ii) the global objective is linear? In particular, how would the structured SVM and adversarial training examples from Section 1 be cast in the DSO model?

Q2. For each entry of Table 1, is the bound deterministic, in expectation, or with high probability? Do Theorems 1.4 and 1.5 require the public box assumption, and does the comparison with Vempala et al. (2020) remain valid without it?

Q3. How does the DSO model differ from the setting of Bürger et al.? Can the active set framework be extended to their asynchronous peer to peer setting?

3 comments

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 dd, where that facet count is polynomial. The empirical study does not instantiate the DSO model either. Each server holds 2ni2n_i 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.

We added a concrete network-capacity planning example to the introduction, with details in Appendix A. Each server holds a potentially large network, but can answer separation queries through a local max-flow computation that returns a violated cut when needed. The shared objective is linear, and the dimension counts shared investments rather than network edges. We also clarified that the experiments test our active-server framework on explicit LPs, not the full oracle-only implementation, and narrowed the learning examples accordingly.

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.

We made the terminology consistent: “linear optimization over convex intersections” refers to the general problem, while “distributed linear programming” refers to finite systems of linear inequalities. This was a wording issue and does not affect the results.

W3. The algorithms are hard to follow from the main text. The main text contains no pseudocode.

We added concise pseudocode for the active-server algorithm to the main text; the detailed procedures remain in the appendix.

W4. The comparison with prior work in Table 1 is not made on equal terms.

We revised Table 1 to distinguish the prior protocols, their assumptions, and the nature of their guarantees. We address the specific points below.

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.

The revised table now identifies our and Vempala et al.’s Clarkson bounds as expected communication bounds with exact output, and lists their deterministic center-of-gravity result separately. Our protocols terminate almost surely and return an exact solution.

Notation. Vempala et al. (2020) state their bounds as O~(sd3L+d4L)\tilde{O}(sd^3L+d^4L) in the coordinator model and O~(sd+d4L)\tilde{O}(sd+d^4L) in the blackboard model, where O~\tilde{O} suppresses polylog(sndL)\text{polylog}(sndL) factors. The claimed improvement consists of removing log⁡n\log n factors, so it lies entirely within what that notation hides. Yet Table 1 expands those factors only partially (O(sd3Llog⁡n)O(sd^3L\log n) in one row, O~(sdlog⁡n)\tilde{O}(sd\log n) in the other). Both columns should list explicit factors. The text should also note that for constant dd, Vempala et al. (2020) already report Θ~(sL)\tilde{\Theta}(sL) in the coordinator model, so improvements there are at most polylogarithmic.

We expanded the relevant logarithmic factors for fixed dd and included Vempala et al.’s deterministic center-of-gravity bound (Theorem 11.3), which is independent of nn and gives Od(sL)O_d(sL). We now describe our coordinator improvement specifically relative to their Clarkson implementation, rather than as an improvement over all prior protocols. The blackboard bound provides a different tradeoff, with leading term Od(s)O_d(s).

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.

The public-box assumption was already in the setup and proofs; we now state it directly in Theorems 1.4 and 1.5. We also added a short appendix discussion of the standard bounded-witness, feasibility, and unboundedness reductions for explicit rational LPs, including the precision cost. Table 1 now makes clear that its direct comparison is for the common boxed setting.

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 dd 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.

Thank you for pointing out this work. We added the papers of Bürger et al. and Notarstefano and Bullo, and removed the claim that the distributed oracle model is new. Our contribution is the quantitative analysis of local oracle queries and communication, rather than the oracle interface or small-basis principle itself.

Relatedly, Ghadiri et al. (STOC 2024) improve communication bounds for approximately solving LP in the coordinator and blackboard models, and should be discussed.

We added Ghadiri et al. to the related-work discussion and distinguished their high-accuracy results and assumptions from our exact bounds. We also clarified that their stated LP theorem is in the coordinator model.

Q1. Can the authors give a concrete application in which (i) each server can answer separation queries for its local set but cannot cheaply transmit it, and (ii) the global objective is linear? In particular, how would the structured SVM and adversarial training examples from Section 1 be cast in the DSO model?

We added a concrete example based on continuous network-capacity planning. A shared vector x∈[0,1]dx\in[0,1]^d represents investments with linear cost c⊤xc^\top x. Server ii holds a network GiG_i with capacities ui,e(x)=bi,e+ai,e⊤x≥0u_{i,e}(x)=b_{i,e}+a_{i,e}^\top x\ge0 and demand DiD_i. The global problem is

\quad\text{subject to}\quad \operatorname{MaxFlow}(G_i,u_i(x))\ge D_i\quad\forall i.$$ A local max-flow computation either certifies feasibility or returns a minimum cut whose capacity is below $D_i$. The corresponding cut inequality separates $x$ and has only $d+1$ coefficients. The server need not transmit its network or enumerate its cuts. Structured SVM can be given a linear objective using epigraph variables, but the lifted dimension and quadratic regularizer mean it is not a direct instance of our strongest fixed-dimensional result. We therefore removed these broad learning examples from the main motivation rather than presenting them as direct applications. > Q2. For each entry of Table 1, is the bound deterministic, in expectation, or with high probability? Do Theorems 1.4 and 1.5 require the public box assumption, and does the comparison with Vempala et al. (2020) remain valid without it? Our bounds and the Clarkson bounds in Table 1 are in expectation, with exact output; Vempala et al.’s center-of-gravity bound is deterministic. The public-box assumption now appears explicitly in Theorems 1.4 and 1.5. We also added the rational-LP reductions and their precision costs, so the table does not imply that the stated bounds apply unchanged to unrestricted LPs. > Q3. How does the DSO model differ from the setting of Bürger et al.? Can the active set framework be extended to their asynchronous peer to peer setting? The oracle interface is essentially the same. Bürger et al. study convergence in asynchronous peer-to-peer networks, while we analyze query and communication costs in the coordinator and blackboard models. We clarified this distinction in the related-work discussion. Extending our quantitative bounds to fully asynchronous operation remains open.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.