- 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 -stationary point, given that the gradient computation takes time for worker , and that the edges have bandwidths . 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 .
-
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 where 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 is uniformly sampled from , with . However, in line 2407 it is said that " is a uniformly random index from ", from which you get in lines 2399-2406, for any , when in fact it holds that . Similarly, in the proof of Lemma G.8, it is said that , when in fact . 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 , 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 (lines 2924-2927). On an path of length with per-edge latency , information from one endpoint needs at least 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
-
Fixing the random subset construction. Is 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 versus contradiction.
-
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 communicated across cuts after discovery times? Protocol 5 seems to allow destination and routing decisions to depend on local information.
-
Latency claim. Section L claims that AllReduce costs . However, shouldn't the latency term scale with the depth of the Steiner trees: , with depth possibly being ?
-
Experimental results. In Section K.1, the experiments led on MNIST probably use (logistic regression, 10 classes, 784 pixels) and coordinate per second. So a single-edge transfer of a full vector would require s or more than s for a four-way splitting. Yet Figures 10-13 show convergence within about s. Could you please explain this difference? Additionally, the experiments for the torus use , when in the beginning Appendix K you assume . How does this change the reasoning made at the beginning of Appendix K?
-
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)?