acceptodds
Under review as a conference paper at ICLR 2027

Optimality in Decentralized Optimization under Bandwidth Constraints

Abstract

We consider a realistic decentralized setup with bandwidth-constrained communication and derive optimal time complexities for non-convex stochastic parallel and asynchronous optimization (up to logarithmic factors). We develop the corresponding methods, Grace SGD and Leon SGD, for both homogeneous and heterogeneous settings. Unlike previous work, our optimal bounds are characterized in terms of min-cut/max-flow quantities and rely on tools from Gomory-Hu trees and Steiner Tree Packing problems, providing tighter and more practical complexities.

Primary area:
optimization
Keywords:
nonconvex optimization, decentralized optimization, time complexity, lower bounds, bandwidth constraints

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_q5NmOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2(+1)
Read review
Paper summary

The paper studies smooth nonconvex stochastic optimization on a graph. The goal is to find the minimum time complexity to find an ε\varepsilon-stationary point, given that the gradient computation takes time hih_i for worker ii, and that the edges have bandwidths bijb_{ij}. The model allows simultaneous communications, as well as routing and splitting.

  • For homogeneous objectives, the algorithm Grace SGD selects a subset of fast workers using a Gomory-Hu tree (Algorithm 2), balancing computation capacity and communication bottlenecks; the choice depends on worker speeds and positions in the network. The selected agents can then compute local gradients and aggregate them using the AllReduce algorithm (Algorithm 3), based on Steiner trees.

  • Theorem 3.2 claims a matching lower bound up to a poly-logarithmic factor log⁡14(n+1)\log^{14}(n+1).

  • For heterogeneous objectives, the algorithm Leon SGD samples every local objective and uses bandwidth-efficient AllReduce. The communication term in the obtained upper-bound scales as d/w‾1d/\overline{w}_1 where w‾1\overline{w}_1 is the global minimum cut. A matching lower-bound is also claimed for this algorithm (Theorem G.12).

  • Examples are provided for sparse, torus, etc. In the sparse-graph setting, assuming equal bandwidths and computation times, it is shown that naive minibatch Synchronous SGD is almost optimal.

  • Appendix K reports MNIST logistic-regression experiments on torus and clustered networks.

Critical strengths
  • This paper presents an interesting trade-off between optimization and network capacity. The considered setting is interesting: it is realistic, with arbitrary graphs, routing, bandwidths, etc. The selection of a subset of agents in the homogeneous case shows an interesting trade-off: having more workers reduces the variance, but increases the communication cost. Gomory-Hu trees provide a relevant subset of candidate workers, while Steiner trees provide an efficient communication between these workers. The use of non-participating workers as routers (or relays) is also quite interesting.

  • This paper has a broad scope and informative special cases. It distinguishes homogeneous objectives, where some workers can be discarded, from heterogeneous objectives, where all local objectives are important. In both cases the given upper-bounds depend on some min cut, as could be expected. Section 4 (and later Appendices I and J) provides examples for different graphs, yielding a better understanding of the general formulas.

Critical weaknesses
  • The lower-bound proofs present issues.

    • In lines 2335-2337 (as well as 1542-1544), a subset RTR_T is uniformly sampled from [d][d], with RT,1<⋯<RT,TR_{T, 1} < \dots < R_{T, T}. However, in line 2407 it is said that "RT,1R_{T, 1} is a uniformly random index from [d][d]", from which you get in lines 2399-2406, P(RT,1=k)=1d\mathbb{P}(R_{T, 1} = k) = \frac1d for any k∈[d]k\in[d], when in fact it holds that P(RT,1=1)=(d−1T−1)/(dT)=Td\mathbb{P}(R_{T, 1} = 1) = {d-1 \choose T-1} / {d \choose T} = \frac{T}{d}. Similarly, in the proof of Lemma G.8, it is said that P(1∈B1)≤Kd\mathbb{P}(1\in B_1) \le \frac{K}{d}, when in fact P(1∈B1)=Td\mathbb{P}(1\in B_1) = \frac{T}{d}. Maybe replacing the sorted subset by an ordered sample without replacement would fix this part, but this change (and its consequences) would need to be made explicitly.
    • Another issue appears on the independence of random variables. It is assumed that the indices generated by the sparsifiers are independent of the random permutation (Assumption G.1). Lines 2062–2064 invoke this to assert independence for νk,S,e,j\nu_{k, S, e, j}, which is a sequence selected based on on where and when messages are sent (definition is give in lines 1724-1732). However, protocol 5 allows the algorithm to choose destinations and feasible routing and to wait between sends (lines 1474–1479). It does not explicitly make these choices independent of local function information.
  • The latency extension omits propagation across multiple edges. Appendix L claims that the time required by AllReduce is O(ℓmax⁡+d/p)O(\ell_{\max}+d/p) (lines 2924-2927). On an path of length nn with per-edge latency ℓ>0\ell>0, information from one endpoint needs at least (n−1)ℓ(n-1)\ell to reach the other. Choosing large bandwidth makes the bandwidth term negligible, so a graph-independent single-edge latency overhead cannot hold uniformly.

Questions for authors
  1. Fixing the random subset construction. Is RT,1,…,RT,TR_{T, 1}, \dots, R_{T, T} supposed to be an ordered sample without replacement instead of a sorted subset? Please provide corrected versions of the proofs of Lemma G.8 and Theorem G.12. This could resolve the T/dT/d versus 1/d1/d contradiction.

  2. On Assumption G.1. Assumption G.1 requires the indices generated by the sparsifiers to be independent of the random permutation defining the objective. Could you clarify why this also guarantees the independence used in Lemma G.8 (line 2061) for the sequences νk,S,e,j\nu_{k,S,e,j} communicated across cuts after discovery times? Protocol 5 seems to allow destination and routing decisions to depend on local information.

  3. Latency claim. Section L claims that AllReduce costs O(ℓmax⁡+d/p)O(\ell_{\max} + d/p). However, shouldn't the latency term scale with the depth of the Steiner trees: O(ℓmax⁡depth+d/p)O(\ell_{\max} \text{depth} + d/p), with depth possibly being Θ(n)\Theta(n)?

  4. Experimental results. In Section K.1, the experiments led on MNIST probably use d=7850d=7850 (logistic regression, 10 classes, 784 pixels) and b=0.1b=0.1 coordinate per second. So a single-edge transfer of a full vector would require 78,50078,500s or more than 19,00019,000s for a four-way splitting. Yet Figures 10-13 show convergence within about 10410^4s. Could you please explain this difference? Additionally, the experiments for the torus use n=100n=100, when in the beginning Appendix K you assume n=(2k+1)2n=(2k+1)^2. How does this change the reasoning made at the beginning of Appendix K?

  5. Relation to prior work. Could you clarify how Algorithm 3’s construction and guarantees differ from the methods of Zhao & Krishnamurthy (2023) and ForestColl (Zhao et al., 2024)?

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

This paper considers a fairly general decentralized optimization scenario, where the agents have different oracle computation time and they can communicate asynchronously by band limited channels. Two scenarios of homogeneous and heterogeneous optimization are considered, for which two algorithms are derived. The algorithms are based on a) selecting a set of agents whose statistical gain outweighs their collective communication losses and b) running a sequence of stages where each agent first calculate a stochastic gradient over an increasing minibatch until a global limit is achieved and then communicating the gradients by an optimal flow algorithm until a shared update is achieved for all. Upper bounds on convergence of the algorithms and lower bounds for their corresponding setups are calculated and it is shown that the algorithms are optimal up to a polylog factor. More discussion in simplified scenarios is provided.

Critical strengths

This work addresses the critical problem of decentralized optimization in a general scenario and provides solutions that are provably optimal. Selecting the best agents and optimal communication scheme are based on graph theoretic approaches that make the algorithms feasible in practice, indeed under some mild practical considerations. The paper is technical, however it is relatively easy to read and understand it.

Critical weaknesses

I do not have any major concern about this work. There are particular assumptions for deriving the lower bound, namely zero respecting property of the algorithm and the particular nature of the compression functions in G1, but I think they are quite standard in the literature. Although the presentation is satisfactory, I suggest the authors to proofread, especially the mathematical concepts once more.

Questions for authors
  1. I am a bit surprised that the optimal algorithm discards some agents. More players would naturally lead to a larger oracle transcript and hence faster convergence (perhaps with a different scheme than the standard SGD). Maybe it is related to the finite bandwidth, but I cannot immediately understand it. The same is true for synchronized rounds, why does not a fully asynchronous algorithm (with nor rounds k=0,1,..) improve the speed of convergence?

  2. How restricting the zero respecting assumption and G1 are? For smooth (strongly) convex family, this has provably no effect, but I suspect that the results here cannot be easily established without these assumption. Is this true?

Reviewer_ZgZGOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper is devoted to distributed optimization. It studies a bandwidth-constrained communication framework for distributed optimization. The question of how the effectiveness of decentralized and centralized (i.e. AllReduce) communication protocols compare has been stated in [1] as early as 2017. Typically in decentralized optimization literature, a synchronous communication protocol is used, when the nodes communicate to their neighbours in synchronous rounds. This paper proposes a bandwidth-constrained protocol, where the communication speed is ruled only by the link bandwidths between the nodes and latency is supposed to be zero.

Under a new assumption, the authors propose lower complexity bounds and corresponding optimal optimization methods. GraceSGD is proposed for the homogeneous setting and LeonSGD is for the heterogeneous setting. Intuitively, the performance of a distributed method in a bandwidth model is upper bounded by the minimum cut in the network. This observation is formalized in the paper via the toolkit of Gomory-Hu trees. The proposed algorithms use increasing local batch sizes and the fastest subset of workers over the network (in homogeneous setting).

[1] Lian, Xiangru, et al. "Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent." Advances in neural information processing systems 30 (2017).

Critical strengths

The main strength of the paper is the novel bandwidth communication protocol it describes. This protocol gives a unified view on decentralized (gossip) and centralized (AllReduce) communication types. The work also gives optimal algorithms in terms of bandwidth-constrained communication.

It is also worth mentioning that the paper makes a step towards combining arguments of optimization theory, such as analysis of nonconvex SGD, and elements of graph theory such as Gomory-Hu trees. Connecting existing theory of decentralized optimization to graph-theoretical arguments is an interesting research direction.

Critical weaknesses

I think reference [1] can be added to the paper and maybe other works that aim to compare centralized and decentralized approaches.

[1] Lian, Xiangru, et al. "Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent." Advances in neural information processing systems 30 (2017).

Questions for authors

Why do the authors stick to nonconvex analysis of SGD? Is this the only problem statement where a nice result can be obtained?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.