- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper develops a communication algorithm in a ring-shaped network for approximate gradient estimation that requires less communication but more local work. This algorithm may produce arbitrarily accurate gradients in exact arithmetic, but this worsens the conditioning of the encoder and decoder. Experiments are performed in both low and high bandwidth settings.
Critical strengths
- The main idea is creative, I am not aware of a similar communication routine (I am not very familiar with the literature though).
- Math looks solid and intuitive in most places.
- The authors make a good job in positioning this work: approximate vs exact gradient estimation, is needed to get less communication, encoding and decoding is needed thus local work may increase, taking the accuracy too small will interfere with exact arithmetic.
Critical weaknesses
- The proposed approach seems to require serious tuning of the accuracy , equivalently the constraint C in (16). The authors do not seem to discuss this much.
- The 17% improvement against a very well optimized architecture feels a bit too good.
Questions for authors
- How do you choose the constraint in practice?
- How much extra local work is added by decoding and encoding compared to the vanilla ring-based algorithm?
Suggestion: The abstract is a bit too long and technical. Would be nicer if you transmit the high-level idea without all this math so early on.
Overall, despite that the implementation part can produce many questions, I think that the authors demonstrate a novel proof-of-concept successfully and I'm leaning towards acceptance.
5 comments
Response to Critical Weakness 2: Training Time Improvement
The reported 17% improvement is a reduction in training time over the same 1,800 optimizer steps on four A100 PCIe GPUs.
At each training step, we averaged the gradient-reduction times measured on the four GPUs. Averaged over all 1,800 steps, the result was 6.238 s per step for NCCL and 4.863 s for CERAR. The measured time ratio, , is close to the ratio of the communication volumes for standard Ring All-Reduce and CERAR, . Thus, CERAR saved about 1.37 s per step on gradient reduction, and these savings accumulated over the run. The total training time decreased from 13,647.7 s to 11,287.1 s, a 17.3% reduction, with similar validation losses at step 1,800 (1.4218 for NCCL and 1.4213 for CERAR).
Response to Question 1: Choosing the Constraint C
We choose to balance approximation accuracy and numerical stability. If is too small, the condition-number constraint is strong and the optimization may not produce a sufficiently small approximation error. If is too large, the optimization can obtain a smaller approximation error, but the resulting matrices may be more sensitive to floating-point roundoff errors. Thus, we choose large enough to obtain a small approximation error while avoiding excessive numerical sensitivity. This tradeoff also follows from our theoretical results. In particular,
whereas
\qquad r^\star=\left\lceil\frac{c}{N}\right\rceil-1.$$ Therefore, decreasing $\epsilon$ reduces the approximation error but increases the condition number. For $c=3N$, as in our $N=4,c=12$ experiment, $r^\star=2$, and hence $$\Phi(U,R)=O(\epsilon^2), \qquad \kappa_2(M_i)=O\left(\sqrt{N}\ \epsilon^{-2}\right).$$ In the optimization, we set $C=10^6$. The resulting matrices satisfied $$\Phi(U,R)=8.95\times10^{-5}, \qquad \max_i\kappa_2(M_i)=5.72\times10^5.$$ Small rounding errors can become larger during decoding. The FP32 unit roundoff is approximately $5.96\times10^{-8}$. Multiplying it by the largest condition number gives $$\left(5.96\times10^{-8}\right) \left(5.72\times10^5\right) \approx 3.4\times10^{-2}.$$ This suggests that small rounding errors could become larger during decoding. This calculation is only a conservative estimate and does not directly predict the resulting gradient error. In our training experiment, the measured relative gradient error was approximately 1.6%–2.9% at the three evaluated steps, while the final validation loss remained essentially unchanged.
Response to Critical Weakness 1: Parameter Selection
Our construction gives an approximation error of Φ(U,R)=O(ϵ2) and a condition-number bound of κ2(Mi)=O(N ϵ−r⋆), where r⋆=⌈c/N⌉−1. Thus, decreasing ϵ reduces the approximation error bound but increases the condition-number bound.
We chose c≈3N as a heuristic. The choice c=3N gives r⋆=2, so the condition-number bound grows as O(N ϵ−2). This choice reduces the communication volume while keeping the exponent at two. Choosing c>3N would reduce the communication volume further, but would raise the exponent to at least three. We used c=12 for N=4 and c=20 for N=8, both of which give r⋆=2.
For the N=4, c=12 experiment, we used C=106 in the matrix optimization. The resulting matrices gave Φ(U,R)=8.95×10−5≈(10−3)2 and a maximum condition number of 5.72×105≈(10−3)−2. The numerical results are thus consistent with the theoretical predictions.