Sharper Analysis of Data Echoing and New Communication-Efficient Algorithm for Data Parallelism

1 ) the paper lacks of systematic understanding of how distributed training works and what could be bottleneck. For example, one major contribution in this paper is to reducing cross GPU communication frequency for gradient averaging with probability p^{c}_{t} (detailed in Algorithm2 and section 4). It does not consider how it can be grounded in real world training.

1.1) If every GPU's triggering gradient averaging probability is i.i.d, then it is almost impossible to pre-allocate and pre-form the GPU communication group for each gradient averaging collective. If forming communication groups ad hoc, it means every time before starting communication, we need to initialize a new communication group and ping every involved GPU to build connection, which will be much bigger overhead compared with reduced communication frequency gain.

1.2) If all GPUs communicate at same time but with lower frequency, this kind of techniques already exists as gradient accumulation steps. Further more, comparing with data echoing's reducing data communication frequency with probability and may have model training accuracy loss, gradient accumulation step can mimic identical model training loss curve of pure distributed data parallel (DDP) but communicate gradient at a much lower frequency.

2 ) the paper lacks major results. LLM is a good example for distributed model training. As mentioned in Sec.5, the paper also use wiki text and gpt-2 model training for evaluation. However, I could not find any results in the paper. The only results on cifar-10/100 + small CNN like resnet/mobilenet usually do not need distributed training. Therefore cifar10/100+ small CNN results are not very convincing.

3 ) The paper is lack of novelty. Two major contributions in this paper. First it provides a tighter convergence analysis of previous work of data echoing via formulating stochastic data echoing to markov chain gradient descent. This first contribution is theoretical contribution but does not proposing any new idea. The second contribution is reducing cross-GPU gradient averaging frequency based on data echoing frequency. The idea seems novel in data echoing setting, but there is a much widely adopted and existed approach call gradient accumulation step, which does not hurt model training accuracy at all while reducing gradient averaging communication frequency. One minor novelty is adding cosine diminishing schedule on data echoing, but this novelty contribution is limited, since any diminishing schedule may work in data echoing setting.

minor issues:

all the figures from fig3 to fig7 (especially fig7) in both x and y axis, the texts are too small to see even enlarge to 200%.

As a person who has not been familiar with data echoing before, I find the experimental results counter-intuitive and misleading. In particular, they do not answer the question "if your hardware has a particular data loading speed what level of data echoing you need to use?".

I see the data echoing technique as a way to reduce the idle time that is due to the long waiting for the next loaded samples. So I expect data echoing may decrease the total training time, but as a method that uses a biased gradient estimation, it should require more optimization steps to converge to a minimum compared to a vanilla SGD. In the experimental section we only see experiments with respect to «number of example loads», which creates an impression that data echoing is in general always better than SGD. This paper lacks more figures that are plotted against the number of gradient steps or epochs to see a bigger picture and compare convergences. More thorough experimental section would provide a better intuition whether you need to use data echoing or not if your hardware support a certain data transfer speed.

Moreover, to have a fair comparison of the data echoing algorithm and SGD, we need to choose the best learning rate for each algorithm independently, right now the learning rate is the same for both algorithms. Indeed, if roughly speaking data echoing performs as an SGD that reuses the same batch several times, then the similar effect can be sometimes obtained by increasing the learning rate for SGD, which can be partially observed on some figures.

Concerning the theoretical analysis, the convergence results look reasonable, but the proofs are not easy to follow as some derivation steps are either skipped or not explained, which makes it harder to read and thus verify the correctness of the proofs for a person not familiar with this line of work. Overall, the appendix seems to be written hastly, I suggest the authors to pay more attention to how they explain their derivations and add missing details in the proofs.

Minor remarks:

line 038: parallelism -> parallel

line 237: slow -> slows

line 265: it is stated that $\nabla f(x_t, B_t)$ approximates well $\nabla f(x_{t-\tau})$ and that it follows from Lemma 3.6. Please comment more on this as it is not a straightforward induction

line 307: explain how do you get the minimum burn-in time (a lower bound for T)?

line 363: effect to -> effect on

line 370: $c_{\nu}$ was never introduced before

Use $\times$ or $\cdot$ for multiplication, instead of *

Figure 1 from the main paper contradicts the description in the appendix, as in one place higher i means higher data loading speed, in other place the opposite.

I suggest using separate numbering for Definition, Lemmas and Theorem independent of section number, so that there are Theorem 1 and Theorem 2, instead of Theorem 3.8 and Theorem 4.2

In equation 4, I would use $p_t$ instead of $p$ directly to simplify Algorithm 1 and 2 descriptions (e.g. line 3 of Algorithm 1)

The order of Figures doesn’t follow their order of mentioning in the text

My main concern about the paper is the unusual assumption it uses (line 076). The key difference between standard SGD and data echoing SGD lies in gradient computation. For standard SGD, we can assume unbiased gradients due to i.i.d. sampling of data. However, for data echoing SGD, I strongly suspect this assumption doesn't hold. If we could make the same assumption for data echoing, I don't see how the analysis would differ from standard SGD.

• the reviewer finds the idea of the cosine scheduler for data loading probability particularly interesting. However, the reviewer wishes to see some theoretical/formal arguments on the soundness of this technique/how this impacts convergence/the results developed in the paper. Perhaps this is trivial (admittedly the reviewer is not an expert on this topic). In any case, the reviewer does believe this should be stated/clarified.
• The numerics should be more extensive/have more results. MobileNet-V2 are not SOTA anymore (see MobileNet-V3). Moreover, the application is for the training of neural nets. Hence the reviewer expects that results for more modern/SOTA architectures (transformers....) should be present, regardless of the speed of these architectures at inference time.
• please edit the graphs in figure 4/5 to include the name of the dataset, model and lr (as title for instance....)

I am for now putting a 5/ marginally below acceptance threshold in order to have those few comments addressed. I would be open to increase my score provided those points are properly addressed (especially about the numerics)