acceptodds
Under review as a conference paper at ICLR 2027

Revisiting Data Sharding for Distributed Training with Periodic Synchronization

Abstract

In datacenter distributed training, periodic model synchronization can mitigate communication bottlenecks and accelerate training. However, longer synchronization intervals exacerbate convergence slowdowns induced by data heterogeneity across nodes. To improve convergence efficiency without increasing model synchronization, we revisit data sharding and propose a weighted stratified sharding algorithm. Our algorithm exploits objective values observed during training to construct weighted shards that reduce objective discrepancies across nodes. We establish theoretical guarantees for the induced weighted objectives and derive a convergence bound in terms of the objective approximation error. The experiments span various distributed setups and training tasks, from image classification to math continual pretraining. Compared with widely used random partitioning, our sharding algorithm introduces negligible runtime overhead and converges up to 1.45 times faster in training steps. It achieves both lower training loss and improved test accuracy, and these gains persist even when using nearly 80% fewer synchronization rounds.

Primary area:
optimization
Keywords:
Distributed training, Data partitioning, Coresets, Communication-efficient training

Reviews

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

This paper studies data assignment for distributed training with periodic model synchronization. It proposes weighted stratified sharding, which groups examples using cached training losses and constructs weighted subsets for individual workers. Sampling weights preserve the full-data objective in expectation, while coordinated assignment reduces sample overlap across workers when possible. The theoretical analysis connects local objective approximation to gradient heterogeneity and gives a convergence bound for momentum Local SGD within a fixed reconstruction interval. Experiments cover image classification and mathematical continual pretraining of TinyLlama-1.1B. The reported results show improvements over random partitioning in training loss, downstream accuracy, and iterations required to reach a specified loss or perplexity.

Critical strengths

The paper addresses a relevant problem through a practical modification to data assignment. It reuses losses collected during training and integrates the construction into the data sampler without changing the model architecture. The construction also avoids duplicate assignments across workers whenever the stratum size permits. Table 5 reports an overhead of approximately 0.4% relative to random partitioning for the CIFAR-10 experiment with ResNet-18 and a synchronization interval of 10.

The empirical support extends beyond a single task or configuration. The vision experiments examine multiple synchronization intervals, and the appendix includes comparisons involving node counts, optimizers, synchronization strategies, sample overlap, and proportional stratification. In mathematical continual pretraining, Table 1 reports improvements on all nine evaluated benchmarks relative to random partitioning for both datasets. The average scores increase from 16.6 to 17.9 on OpenWebMath-Pro and from 35.1 to 37.4 on Jiuzhang3.0. These results support the practical value of the overall method.

Critical weaknesses

The handling of cached losses needs clarification. Appendix C explains that losses are recorded during training and initialized to zero. Appendix D also considers using only a fraction of the dataset between shard reconstructions. I could not find a clear description of how cached values are maintained for examples that are not selected during an interval. Figure 3b provides a useful comparison between cached and freshly evaluated loss rankings, but does not explain this update rule. This makes it difficult to assess how current the information used for sharding remains throughout training.

The ablations provide useful evidence for the overall method, but leave some uncertainty about the source of its improvements. Table 7 compares proportional unweighted stratification with the proposed allocation and weighting together. It therefore does not separately establish how much benefit comes from selecting and weighting examples versus assigning those examples across workers. Figure 3c reports variation in local loss values, which provides an indirect check of the proposed reduction in worker heterogeneity. A comparison that preserves the selected examples and their weights while changing their assignment across workers would help clarify this

Questions for authors

How are cached losses handled for examples that are not selected between consecutive shard reconstructions? Are their previous values retained, and is there any refresh procedure? When using partial-data reconstruction intervals, is there an initial pass over the full dataset before loss-based stratification begins?

Do you have a comparison that preserves the selected examples, their weights, and the per-worker sample budgets, but randomizes their assignment across workers? If available, measurements of gradient disagreement evaluated at a common model parameter would also help clarify whether the improvement is associated with reduced worker heterogeneity.

4 comments
AuthorsOpenReview ↗

Response to Reviewer V1Dw

We thank the reviewer for the constructive feedback. We address your concerns below and have incorporated the corresponding clarifications and additional results into the revised manuscript, with changes highlighted in blue.

W1&Q1 [The handling of cached losses]

A. Samples not processed between reconstructions retain their cached losses. These samples remain eligible for subsequent shard assignments, and their cached losses are refreshed using newly observed losses when they are sampled. For processed samples, we account for multiple observations across workers, as Algorithm 1 permits overlap in small strata to ensure the approximation guarantee. No initial pass over the full dataset is required before weighted stratified sharding, including the case for using partial data during reconstruction intervals. All cached losses are initially zero, so the first reconstruction contains only one stratum as detailed in Appendix C. As training proceeds, more samples acquire observed losses, allowing subsequent reconstructions to exploit increasingly informative stratification. The weighting rule in Section 3 preserves the unbiasedness of each weighted local objective F~k\widetilde F^k with respect to FF. Remark 3.2 further analyzes the approximation error caused by stale observed losses.

Here, we provide the technical details for cached losses maintenance. Let ℓi\ell_i denote the cached loss of sample ziz_i, following the notation in the analysis of Remark 3.2. Define Vi\mathcal V_i as the set of worker-step pairs (k,t)(k,t) at which ziz_i is processed between consecutive shard reconstructions, where θtk\theta_t^k denotes the parameter of worker kk at step tt, as defined in Section 2. At each reconstruction, if ∣Vi∣>0|\mathcal V_i|>0, we update the cached loss as ℓi←1∣Vi∣∑(k,t)∈Vifi(θtk)\ell_i \leftarrow \frac{1}{|\mathcal V_i|}\sum_{(k,t)\in\mathcal V_i} f_i(\theta_t^k). Otherwise, ℓi\ell_i retains its previous value, including zero for samples never observed. This update averages newly observed, unweighted sample losses. As described in Appendix C, per-sample losses are collected during ordinary training forward passes and synchronized through All-Gather. After All-Gather, each worker applies this averaging rule to the collected observations and updates its local loss cache.

W2&Q2 [Ablation on worker assignment and measurement of gradient disagreement]

A. Ablation on Worker Assignment. Table 7 evaluates sampling and weighting, while the following comparison examines worker assignment with the selected sample-weight pairs held fixed. We consider the reviewer's suggested variant as "Random Assignment", which preserves the selected samples, their weights, and the per-worker sample budgets, but randomly redistributes the selected sample-weight pairs across workers. Unlike Algorithm 1, Random Assignment may assign worker kk a different number s^jk\widehat{s}_j^k of sample-weight pairs from stratum ZjZ_j than the prescribed ∣Sjk∣|S_j^k|, while retaining the original weight ∣Zj∣/∣Sjk∣|Z_j|/|S_j^k| for each pair. Consequently, the total weight assigned to this stratum becomes ∣Zj∣s^jk/∣Sjk∣|Z_j|\widehat{s}_j^k/|S_j^k| instead of ∣Zj∣|Z_j|. Although this reassignment preserves the consensus weighted objective F~\widetilde F, it changes the worker-specific objectives F~k\widetilde F^k and can thus alter the local optimization between synchronizations. Accordingly, the per-worker approximation guarantee of Lemma 3.1 no longer directly applies for this variant.

Table R6. Ablation on data sampling and worker assignment on Tiny-ImageNet with ResNet-50 (K=8K=8, H=10H=10). Random uses uniform sampling, Stratified Random uses proportional stratification without reweighting, and Coreset (ours) follows Algorithm 1. Random Assignment preserves the selected samples, weights, and per-worker sample budgets, but randomly reassigns the sample-weight pairs across workers. Results are averaged over three runs. Accuracy gain and iteration speedup are relative to Random.

MethodTest Acc. (%)Final LossAcc. Gain (%)Iteration Speedup
Random61.9 ±\pm 0.10.77 ±\pm 0.02+0.01.00 ×\times
Stratified Random62.1 ±\pm 0.10.73 ±\pm 0.01+0.21.06 ×\times
Random Assignment60.6 ±\pm 0.20.83 ±\pm 0.03-1.30.94 ×\times
Coreset62.9 ±\pm 0.20.61 ±\pm 0.01+1.01.18 ×\times

Measurement of Gradient Heterogeneity. Beyond the cross-node loss variation in Figure 3c, we directly assess the gradient heterogeneity bounded in Lemma 3.3 by measuring the mean squared deviations of individual local objective gradients from the original global objective gradient. Both Coreset and Random use the same original global objective FF as the reference. For Coreset, the mean squared disagreement with the consensus gradient ∇F~\nabla\tilde F is no larger than this measure, as shown in the proof of Theorem 3.4. Specifically, at the first local step tt after each synchronization, all KK workers (k∈[K]k\in[K]) share the consensus parameter θˉt\bar{\theta} _ {t}. We compute $D _ {t}=\frac{1}{K} \sum _ {k=1}^{K} \left | \nabla \tilde F^k(\bar{\theta} _ {t}) - \nabla F(\bar{\theta} _ {t}) \right | ^2 $ and report its average within each 10% training interval.

Table R7. Mean squared deviations of local objective gradients from the original global objective gradient during ResNet-50 training on Tiny-ImageNet (K=8K=8, H=20H=20). Each entry reports the average over the corresponding 10% training interval. The final column reports the relative change in the mean across all ten intervals, using Random as the reference. Lower values indicate lower gradient heterogeneity.

Method0-10%10-20%20-30%30-40%40-50%50-60%60-70%70-80%80-90%90-100%Avg. Relative Change (%) ↓\downarrow
Random0.5700.9420.9280.7280.6500.5360.5060.4690.4720.4500.0
Coreset0.5440.9350.8510.7110.6470.5240.4580.4350.3860.379-6.1

Table R7 shows consistently lower gradient heterogeneity for Coreset across all ten training intervals, with a 6.1% reduction in average heterogeneity compared with Random. These results provide direct empirical evidence that our weighted stratified sharding reduces discrepancies between local objective gradients and the original global objective gradient at a common model parameter.

Thank you.

Dear Reviewer V1Dw,

Thank you for taking the time to review our paper and provide valuable feedback. As the discussion phase is nearing its conclusion, we would like to confirm if our responses have effectively addressed your concerns. If you have any additional comments, we will do our best to address them.

Best regards,

The authors of Submission 30496.

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

The paper studies data assignment for distributed training with periodic synchronization. It proposes weighted stratified sharding based on per-example losses. The analysis bounds the approximation error of the local objectives and their gradient heterogeneity, then applies a momentum LocalSGD convergence result during a phase with fixed shards. Experiments on image classification and TinyLlama math continual pretraining report improved test performance and fewer iterations to reach a given training loss compared with random sharding.

Critical strengths

The paper studies an important question: whether better data assignments can improve training with infrequent synchronization. Its strongest evidence is empirical, with improvements over random sharding across both vision tasks and language-model continual pretraining.

Critical weaknesses

1. The practical case for repeatedly constructing local shards is unclear.

If every worker can cheaply access the full dataset, a natural baseline is LocalSGD with fresh IID minibatches drawn from the full dataset at each step. All workers then optimize the same expected objective FF, without restricting them to different local subsets.

If workers instead store separate data shards, changing assignments may require transferring data between machines. These transfers can offset the savings from less frequent model synchronization. The runtime measurements on one physical server with CIFAR-10 do not establish this cost. Since Random also reassigns data each epoch, the small overhead relative to Random is insufficient: a comparison with fixed-shard LocalSGD should include data-transfer and loss-synchronization costs.

The experiments also change data selection, weighting, and worker assignment together. Randomly assigning the same selected examples and weights across workers would help identify whether better assignments are responsible for the gains. The Stratified Random ablation changes allocation and weighting, so it does not provide this control.

2. The theory does not show a clear advantage over random sharding.

Theorem 3.4 gives a guarantee for the weighted objective F~\tilde F, which generally differs from the original objective FF. Using Lemma 3.3 to obtain a guarantee for FF adds an O(mϵL)O(m\epsilon L) error term. At a fixed sampling budget, this term need not decrease with more training steps. In comparison, splitting the full dataset into disjoint random shards preserves FF exactly.

The theorem also only covers the steps between two shard reconstructions. It does not give a convergence guarantee for the full training run, where the shards and weights repeatedly change.

Using the average loss hˉ\bar h instead of the largest loss hmax⁡h_{\max} improves their approximation bound. But the paper does not show that this leads to a better overall convergence guarantee on FF than random sharding. The O(1/KT)O(1/\sqrt{KT}) rate is already known from Yu et al. (2019). The comparison needs to account for both the extra approximation error and the gradient noise after reweighting.

Questions for authors

see weaknesses.

4 comments
AuthorsOpenReview ↗

Response to Reviewer tvrm

We thank the reviewer for the constructive feedback. We address your concerns below and have incorporated the corresponding clarifications and additional results into the revised manuscript, with changes highlighted in blue.

W1 [Practical case for repeatedly constructing local shards]

A. Repeatedly sharding and reassignment of sample indices at the beginning of each epoch are standard practices in distributed data-parallel (DDP) training [1]. Our method builds on conventional random sharding by introducing weighted stratified sharding. In the considered datacenter training setting, each worker optimizes the empirical local objective F~k\widetilde F^k induced by the samples it actually processes. Accordingly, stochastic gradient variance is defined relative to ∇F~k\nabla\widetilde F^k, while Lemma 3.3 separately bounds the discrepancy between ∇F~k\nabla\widetilde F^k and the global gradient ∇F\nabla F.

LocalSGD with IID minibatch sampling. We extend Table 6 (Appendix D) with IID minibatch sampling, where each worker independently samples with replacement from the full dataset at each step, while Random (Independent) samples without replacement within each worker [2]. Compared with random partitioning, IID minibatch sampling reduces unique data coverage from 100.0% to 86.4%, decreases test accuracy from 61.9% to 60.7%, and achieves only 0.92 ×\times the baseline iteration speedup. In the same setting, our Coreset weighted sharding achieves 62.9% accuracy and 1.18 ×\times iteration speedup.

Table R3. Ablation on sample overlap across nodes on Tiny-ImageNet with ResNet-50 (K=8K=8, H=10H=10), extending Table 6 (Appendix D) with the IID minibatch baseline. Unique coverage is the percentage of distinct samples among all samples assigned across nodes (averaged over epochs). The reported results are averaged over three runs. Accuracy gain and iteration speedup are relative to Random with partition assignment.

MethodAssignmentUnique Cov. (%)Test Acc. (%)Final LossAcc. Gain (%)Iteration Speedup
RandomIID minibatches86.460.7 ±\pm 0.20.84 ±\pm 0.02-1.20.92 ×\times
RandomIndependent87.861.2 ±\pm 0.20.81 ±\pm 0.01-0.70.93 ×\times
RandomPartition100.061.9 ±\pm 0.10.77 ±\pm 0.02+0.01.00 ×\times
CoresetIndependent78.562.4 ±\pm 0.20.64 ±\pm 0.02+0.51.12 ×\times
CoresetQuasi non-overlap88.262.9 ±\pm 0.20.61 ±\pm 0.01+1.01.18 ×\times

Comparison with fixed-shard LocalSGD. We reassign data shards at the beginning of each epoch for Random and Coreset, following standard distributed sampling practice [1]. To address the reviewer's concern, we additionally compare against fixed-shard LocalSGD, where the full dataset is randomly partitioned once across workers and each worker samples stochastic minibatches within its fixed shard across epochs. We evaluate Coreset under two settings. Coreset (matched iterations) uses the same 150 training epochs and iterations as Random and Fixed Shard, while Coreset (matched time) uses the same total wall-clock budget as Fixed Shard. Table R4 reports test accuracy and runtime, including the costs of network-based shard transfers and cached-loss synchronization.

Table R4. Runtime breakdown and test accuracy on CIFAR-10 with ResNet-18 under Local SGD across two physical servers with four GPUs per server, where each GPU serves as one logical node (K=8K=8, H=10H=10). Network communication uses the host TCP/IP stack with 40 Gbps bandwidth. Random and Coreset reassign shards each epoch, whereas Fixed Shard retains its initial random partition. All methods train using stochastic minibatches sampled from their assigned shards. Shard transfer and loss synchronization are included in total runtime. Percentages indicate their shares of total runtime, while total runtime differences are relative to the runtime of Random.

MethodShard transfer (s; % total)Loss synchronization (s; % total)Total (s; vs. Random)Test accuracy (%)
Random6.17 (0.31%)—1972 (+0.00%)94.0
Fixed Shard0.04 (0.002%)—1966 (-0.30%)88.3
Coreset (matched iterations)7.28 (0.37%)2.21 (0.11%)1977 (+0.25%)95.0
Coreset (matched time)7.24 (0.37%)2.17 (0.11%)1966 (-0.30%)94.9

Ablation on Worker Assignment. Table 7 evaluates sampling and weighting, while the following comparison examines worker assignment with the selected sample-weight pairs held fixed. We consider the reviewer's suggested variant as "Random Assignment", which preserves the selected samples, their weights, and the per-worker sample budgets, but randomly redistributes the selected sample-weight pairs across workers. Unlike Algorithm 1, Random Assignment may assign worker kk a different number s^jk\widehat{s}_j^k of sample-weight pairs from stratum ZjZ_j than the prescribed ∣Sjk∣|S_j^k|, while retaining the original weight ∣Zj∣/∣Sjk∣|Z_j|/|S_j^k| for each pair. Consequently, the total weight assigned to this stratum becomes ∣Zj∣s^jk/∣Sjk∣|Z_j|\widehat{s}_j^k/|S_j^k| instead of ∣Zj∣|Z_j|. Although this reassignment preserves the consensus weighted objective F~\widetilde F, it changes the worker-specific objectives F~k\widetilde F^k and can thus alter the local optimization between synchronizations. Accordingly, the per-worker approximation guarantee of Lemma 3.1 no longer directly applies for this variant.

Table R5. Ablation on data sampling and worker assignment on Tiny-ImageNet with ResNet-50 (K=8K=8, H=10H=10). Random uses uniform sampling, Stratified Random uses proportional stratification without reweighting, and Coreset (ours) follows Algorithm 1. Random Assignment preserves the selected samples, weights, and per-worker sample budgets, but randomly reassigns the sample-weight pairs across workers. Results are averaged over three runs. Accuracy gain and iteration speedup are relative to Random.

MethodTest Acc. (%)Final LossAcc. Gain (%)Iteration Speedup
Random61.9 ±\pm 0.10.77 ±\pm 0.02+0.01.00 ×\times
Stratified Random62.1 ±\pm 0.10.73 ±\pm 0.01+0.21.06 ×\times
Random Assignment60.6 ±\pm 0.20.83 ±\pm 0.03-1.30.94 ×\times
Coreset62.9 ±\pm 0.20.61 ±\pm 0.01+1.01.18 ×\times

With the selected samples, their weights, and per-worker sample budgets held fixed, Random Assignment achieves only 60.6% test accuracy and 0.94 ×\times iteration speedup. Under the same setting, Coreset achieves 62.9% test accuracy and 1.18 ×\times iteration speedup, suggesting the importance of aligning worker assignment with our theoretically derived stratum-wise sampling budgets.

[1] Goyal, Priya, et al. "Accurate, large minibatch sgd: Training imagenet in 1 hour." arXiv preprint arXiv:1706.02677 (2017).

[2] Chulhee Yun, Shashank Rajput, Suvrit Sra: Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond. ICLR 2022

W2 [Theoretical advantage over random sharding]

A. Under random sharding, each worker optimizes an unweighted empirical local objective FkF^k determined by the samples it actually processes, which generally differs from the global objective FF. Between synchronization rounds, workers generally evaluate gradients at different local parameters, so 1K∑k=1K∇Fk(θtk)≠∇F(θˉt)\frac{1}{K}\sum_{k=1}^K\nabla F^k(\theta_t^k)\neq\nabla F(\bar\theta_t) in general, even in the case where the consensus gradient equals ∇F\nabla F at a synchronized parameter. Consequently, preserving the consensus objective alone does not control the drift caused by local updates, for which Lemma 3.3 bounds the associated gradient heterogeneity through our weighted local objective approximation. Since the workers optimize the constructed weighted local objectives in our method, Theorem 3.4 establishes the corresponding convergence guarantees for the consensus weighted objective F~\widetilde F, while Lemma 3.1 guarantees that each weighted local objective F~k\widetilde F^k uniformly approximates FF. Specifically, Lemma 3.3 bounds squared local gradient deviations from ∇F\nabla F by O(mϵL)O(m\epsilon L), which also bounds the mean squared disagreement with the consensus gradient. This yields an O(η2H2mϵL)O(\eta^2H^2m\epsilon L) heterogeneity penalty in Theorem 3.4, scaling as O(η2H2K1/4hˉ)O(\eta^2H^2K^{1/4}\bar h) up to logarithmic factors under the local region condition in Section 3.2. Moreover, Theorem 3.4 separately accounts for gradient noise after reweighting, whose contribution scales at most linearly with the synchronization interval HH, whereas the gradient heterogeneity penalty scales quadratically with HH. Our weighted sharding method controls the gradient heterogeneity term, making its advantage particularly important at longer synchronization intervals.

Theoretical comparison with random sharding. Under periodic synchronization, workers perform multiple updates on their local objectives before averaging. As established in Section 3.1, the local objective approximation bound for random sharding depends on the worst-case loss scale hmaxh_{max}, whereas ours depends on the averaged loss scale hˉ\bar{h}. The advantage is particularly pronounced when the gap between hˉ\bar{h} and hmaxh_{max} is substantial, as is often the case when training proceeds [1]. Lemma 3.3 further translates this improvement into a smaller first-order gradient heterogeneity bound. This improvement further reduces the heterogeneity penalty in Theorem 3.4, supporting faster convergence and allowing longer synchronization intervals HH while retaining the O(1/KT)O(1/\sqrt{KT}) linear speedup rate. Table R7 in our response to Reviewer V1Dw provides direct theory validation of the gradient heterogeneity in Lemma 3.3, showing a 6.1% reduction in mean squared local gradient deviations from the original global gradient ∇F\nabla F.

Convergence with changing shards and weights. Theorem 3.4 establishes a convergence guarantee for the consensus weighted objective within each reconstruction phase. To account for repeated reconstruction, we additionally bound the change in each worker's weighted local objective at reconstruction boundaries. Together, these results characterize convergence within each phase and establish our theoretical advantage in bounding local objective variation between phases, while the experiments below demonstrate faster convergence over complete training runs with repeated reconstruction. Let ee index successive reconstruction phases and define hˉe=F(θref,e)\bar h_e=F(\theta_{\mathrm{ref},e}). For consecutive reconstruction phases with the next reference parameter lying within the preceding local region, LL-smoothness and the local region condition in Section 3.2 imply $ \bar{h} _ {e+1} \leq \bar{h} _ e + M_e R_e + \frac{L}{2} R_e ^2 = O(\bar{h} _ e) $. At θref,e+1\theta_{\mathrm{ref},e+1}, applying Lemma 3.1 to each worker's local objectives before and after reconstruction gives ∣F~e+1k(θref,e+1)−F~ek(θref,e+1)∣≤meϵe+me+1ϵe+1=O~((Kde/(ρ(n+de)))1/4hˉe)|\widetilde F_{e+1}^k(\theta_{\mathrm{ref},e+1})-\widetilde F_e^k(\theta_{\mathrm{ref},e+1})|\leq m_e\epsilon_e+m_{e+1}\epsilon_{e+1}=\widetilde O((Kd_{\mathtt e}/(\rho(n+d_{\mathtt e})))^{1/4}\bar h_e). Thus, the change in each weighted local objective induced by reconstruction is controlled by our approximation guarantee. Under these conditions, the corresponding bound for random sharding depends on the worst-case loss scale, whereas ours depends on the averaged loss scale. With repeated shard reconstructions, Figures 5 and 7 demonstrate 1.20 ×\times - 1.45 ×\times iteration speedups across vision tasks, 1.28 ×\times and 1.26 ×\times speedups in LLM continual pretraining, respectively. Table 1 further shows improvements in average downstream scores from 16.6 to 17.9 and from 35.1 to 37.4.

[1] Lin, Zhenghao, et al. "Not all tokens are what you need for pretraining." Advances in Neural Information Processing Systems 37 (2024): 29029-29063.

Dear Reviewer tvrm,

Thank you for taking the time to review our paper and provide valuable feedback. As the discussion phase is nearing its conclusion, we would like to confirm if our responses from a few days ago have effectively addressed your concerns. If you have any additional comments, we will do our best to address them.

Best regards,

The authors of Submission 30496.

Reviewer_vu2BOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper revisits data sharding for distributed training with periodic synchronization. It uses cached per-sample losses to build weighted, loss-stratified shards, so that each worker's local objective better approximates the full-data objective. The analysis bounds objective approximation error and connects it to gradient heterogeneity. It also analyzes momentum Local SGD for the mean weighted objective within a fixed-shard phase. Experiments cover vision tasks and TinyLlama-1.1B math continual pretraining, with comparisons against random partitioning and additional sharding and synchronization variants.

Critical strengths
  1. An interesting way to reduce local drift. Using historical loss to make each shard a better weighted miniature of the full dataset is a useful perspective. The method changes data assignment without requiring more frequent model synchronization. The reported TinyLlama results include a 1.26–1.28× iteration speedup at matched perplexity.

  2. The theory offers useful insight. The approximation bound depends on average loss rather than maximum loss. This can improve the guarantee when losses are uneven (Section 3.1). For fixed data size and other quantities, the analysis also exposes two competing effects of adding workers: a noise term decreases as 1/K1/K, while smaller shards increase the O(η2H2mϵL)O(\eta^2 H^2 m\epsilon L) heterogeneity penalty. These connections help explain why data assignment can matter more at long synchronization intervals. The comparison concerns approximation bounds under the stated assumptions. It does not guarantee faster training in every instance.

Critical weaknesses
  1. The practical regime is still unclear. For industrial language-model training with very large, well-shuffled datasets, how much benefit remains? The paper does compare against epoch-wise random repartitioning. The issue is when further balancing of local objectives matters. The two stated approximation bounds have the form

    \epsilon_{\mathrm{ours}}&=\widetilde O\!\left(\frac{\bar h+C_{\mathrm{Lip}}}{m}\,Q\right),\\ \epsilon_{\mathrm{rnd}}&=\widetilde O\!\left(\frac{h_{\max}+C_{\mathrm{Lip}}}{m}\,Q\right). \end{aligned}$$ Here $Q=(K d_e/[\rho(n+d_e)])^{1/4}$, which scales as $(K d_e/[\rho n])^{1/4}$ when $n\gg d_e$. Holding the loss scales and other analysis quantities fixed, both upper bounds decrease with $n$. This does not prove that measured speedup vanishes, but it leaves the practical size of the remaining sharding error unclear. Data reuse is another part of this concern. Historical losses guide later assignments, so a sample used only once cannot benefit from its own cached loss in a later pass. The TinyLlama runs use a total token budget twice each corpus's unique-token count, with 20 shard reconstructions (Section 5.3; Appendix D). This does not settle the single-pass case.
  2. The language-model evidence leaves important questions open. The main experiments use local AdamW with simple parameter averaging. Appendix D does test momentum and Nesterov outer updates, so the concern is not that DiLoCo-style synchronization is absent. Those tests are on Tiny-ImageNet, however. It remains unclear whether the language-model gains persist with the corresponding outer optimizer. The paper also tests heterogeneous compute capacity, but this does not answer the reviewer's question about heterogeneous data. A multilingual or mixed-domain analysis could help identify when loss-based sharding is useful beyond ordinary shuffling.

Questions for authors
  1. How do the gains change as n/Kn/K increases under a matched training budget? Which dataset or loss-distribution properties predict a useful advantage over well-shuffled random partitioning?
  2. Is the intended use mainly repeated-data training? How would the method work if each sample were used only once, and how are cached losses maintained for samples omitted from a reconstruction?
  3. Why use simple parameter averaging for TinyLlama? Do the gains persist with a DiLoCo-style Nesterov outer optimizer under matched tuning and token budgets?
  4. Are there results with heterogeneous data, such as multilingual or mixed-domain language-model training? This is distinct from the compute heterogeneity evaluated in the appendix.
  5. Why does the language-model evaluation omit pretraining from scratch? Would the gains hold from random initialization of weight?
4 comments
AuthorsOpenReview ↗

Response to Reviewer vu2B

We thank the reviewer for the constructive feedback. We address your concerns below and have incorporated the corresponding clarifications and additional results into the revised manuscript, with changes highlighted in blue.

W1&Q1 [Practical regime when further balancing of local objectives matters]

A. Our proposed Coreset sharding method enables faster training convergence for distributed training with periodic synchronization, achieving 1.26-1.28 ×\times iteration speedup for TinyLlama at matched perplexity, together with synchronization at only 1/500 the frequency of fully synchronized data parallelism. Such training acceleration comes from weighted stratified sharding that reduces discrepancies among local objectives. Specifically, $\epsilon_{ours} = \tilde O (\frac{\bar h + C_{Lip}}{m} Q) $, $\epsilon_{rnd} = \tilde O (\frac{h_{max} + C_{Lip}}{m} Q) $, where $Q=\sqrt[4]{\frac{K d_{\mathtt e}}{\rho (n+d_{\mathtt e})}} $ and the averaged loss $\bar h \leq h_{max} $. Both approximation bounds decrease as nn grows, while the advantage of our dependence on the average loss scale becomes more pronounced whenever there is a substantial gap between hˉ\bar{h} and hmaxh_{max}. Theorem 3.4 further translates this advantage into a smaller heterogeneity penalty and an improved convergence bound. This property is particularly relevant when most samples attain low losses while a small subset retains high losses as training proceeds [1]. Figure 3c demonstrates smaller variation in local objective losses across workers, particularly in later training stages. We provide empirical evidence of training curves for vision tasks in Figure 5 and 12, and for LLM continual pretraining in Figure 7. These results demonstrate an increasingly pronounced training loss advantage over Random sharding as training proceeds.

About data reuse. Our weighted stratified sharding exploits historical losses to guide subsequent assignments, naturally benefiting training scenarios with data reuse. Prior studies have demonstrated the benefits of careful data curation [2] and data reuse [3] for LLM pretraining under constrained data availability. Our method improves data utilization in distributed training with periodic synchronization through weighted stratified sharding. Our TinyLlama experiments (Table 1, Figure 7) show that, under a total token budget of only twice the corpus size, Coreset sharding achieves better downstream generalization than Random sharding, improving the average score from 16.6 to 17.9 on OpenWebMath-Pro and from 35.1 to 37.4 on Jiuzhang3.0.

Scaling with n/Kn/K. Appendix D (Figure 8) evaluates K∈{2,4,8}K\in\{2,4,8\} on Tiny-ImageNet, keeping the dataset, total number of GPUs, batch size on each GPU, and training iteration budget fixed. As KK decreases from 8 to 2, the iteration speedup remains stable at 1.14 ×\times-1.17 ×\times, with test accuracy gains of 0.36-0.82 percentage points over Random. These results demonstrate that our convergence advantage is robust to the number of distributed nodes under a fixed training budget.

[1] Lin, Zhenghao, et al. "Not all tokens are what you need for pretraining." Advances in Neural Information Processing Systems 37 (2024): 29029-29063.

[2] Tirumala, Kushal, et al. "D4: Improving llm pretraining via document de-duplication and diversification." Advances in Neural Information Processing Systems 36 (2023): 53983-53995.

[3] Muennighoff, Niklas, et al. "Scaling data-constrained language models." Advances in Neural Information Processing Systems 36 (2023): 50358-50376.

Q2 [Single-pass training and cached loss maintenance]

A. Our weighted stratified sharding can exploit historical losses even within a training budget equivalent to a single pass over the dataset. With ρ<1\rho<1, multiple shard reconstructions allow observed losses to guide subsequent assignments before this budget is exhausted. As specified in Appendix C, all cached losses are initially zero, so the first reconstruction contains only one stratum. As training proceeds, more samples acquire observed losses, allowing subsequent reconstructions to exploit increasingly informative stratification. The weighting rule in Section 3 preserves the unbiasedness of each weighted local objective F~k\widetilde F^k with respect to FF. Remark 3.2 further analyzes the approximation error caused by stale observed losses.

Cached loss maintenance. Samples not processed between reconstructions retain their cached losses. These samples remain eligible for subsequent shard assignments, and their cached losses are refreshed using newly observed losses when they are sampled again. For processed samples, we account for multiple observations across workers, as Algorithm 1 permits overlap in small strata to ensure the approximation guarantee. Let ℓi\ell_i denote the cached loss of sample ziz_i, following the notation in the analysis of Remark 3.2. Define Vi\mathcal V_i as the set of worker-step pairs (k,t)(k,t) at which ziz_i is processed between consecutive shard reconstructions, where θtk\theta_t^k denotes the parameter of worker kk at step tt, as defined in Section 2. At each reconstruction, if ∣Vi∣>0|\mathcal V_i|>0, we update the cached loss as ℓi←1∣Vi∣∑(k,t)∈Vifi(θtk)\ell_i \leftarrow \frac{1}{|\mathcal V_i|}\sum_{(k,t)\in\mathcal V_i} f_i(\theta_t^k). Otherwise, ℓi\ell_i retains its previous value, including zero for samples never observed. This update averages newly observed, unweighted sample losses. As described in Appendix C, per-sample losses are collected during ordinary training forward passes and synchronized through All-Gather. After All-Gather, each worker applies this averaging rule to the collected observations and updates its local loss cache.

W2&Q3&Q4&Q5 [LLM pretraining with mixed-domain corpus and DiLoCo-style Nesterov outer optimizer]

A. Our original TinyLlama experiments focus on mathematical continual pretraining, evaluating convergence efficiency and generalization across nine downstream benchmarks. We adopt simple parameter averaging to demonstrate the effectiveness of weighted stratified sharding under periodic synchronization, even without introducing sophisticated outer optimizers. As shown in Figure 4, Coreset with H∈{2,5}H\in\{2,5\} outperforms fully synchronized Random (H=1H=1) on CIFAR-10 and ImageNet-1K. Appendix D further demonstrates its compatibility with SGD with momentum and Nesterov outer updates on Tiny-ImageNet.

Additional LLM pretraining experiment. We extend the evaluation to pretraining from scratch with a Nesterov outer optimizer, using OpenDiLoCo's 150M Llama architecture on SlimPajama-6B, a sampled subset of approximately 6 billion tokens from SlimPajama [1], spanning web text, code, books, scientific papers, Wikipedia, and question-answer forums. We use ρ=0.2\rho=0.2 and H=500H=500, with 15 shard reconstructions under a training budget equivalent to three corpus passes. Both methods use matched token budgets and differ only in their data sharding strategies. We evaluate validation perplexity, iteration speedup at matched training loss, and total node-hours. To assess generalization beyond perplexity, we additionally report zero-shot accuracy on five standard benchmarks covering commonsense reasoning (HellaSwag and PIQA), science question answering (ARC-Easy and SciQ), and context-dependent word prediction (LAMBADA).

Table R1. Validation perplexity (PPL, ↓\downarrow) at the end of reconstruction epochs 3, 6, 9, 12, and 15 on SlimPajama-6B. Iteration speedup (↑\uparrow) is measured at the final training loss achieved by Random. Total node-hours (↓\downarrow) is the sum of training time across all nodes, including data sharding and synchronization overhead.

MethodE3E6E9E12E15 (final)Total node-hours ↓\downarrowIteration speedup ↑\uparrow
Random19.4917.3216.0615.4014.99149.44 (100%)1.00 ×\times
Coreset21.5617.5815.7714.4513.84150.09 (100.44%)1.41 ×\times

Table R2. Zero-shot downstream accuracy (%, ↑\uparrow) on the final pretraining checkpoints. HellaSwag, PIQA, ARC-Easy, and SciQ use length-normalized accuracy, while LAMBADA uses accuracy. Average denotes the unweighted mean across the five benchmarks.

MethodHellaSwagPIQAARC-EasySciQLAMBADAAverage
Random31.1460.5937.8867.2027.8444.93
Coreset33.1261.8637.5868.4030.1346.22

Under matched token budgets, Table R1 shows that Coreset achieves a 1.41 ×\times iteration speedup and reduces final validation perplexity from 14.99 to 13.84, with only 0.44% additional total node-hours. Coreset has higher validation perplexity than Random at E3, where the increase in the Lipschitz term due to staleness, as analyzed in Remark 3.2, may offset the initial advantage from the gap between hˉ\bar h and hmaxh_{max}. The two methods achieve similar perplexity at E6, while Coreset achieves lower perplexity from E9 onward, with an increasing advantage through E15. A similar trend is observed in math continual pretraining in Figure 7, suggesting that the benefit of weighted stratified sharding becomes more pronounced as training proceeds. Moreover, Table R2 shows that Coreset improves the average score across five downstream benchmarks from 44.93% to 46.22%. These results indicate the effectiveness of weighted stratified sharding for LLM pretraining from scratch on data from multiple domains and its compatibility with a Nesterov outer optimizer.

[1] Soboleva, Daria, et al. "SlimPajama: A 627B token cleaned and deduplicated version of RedPajama." Jun. 2023.

Dear Reviewer vu2B,

Thank you for taking the time to review our paper and provide valuable feedback. As the discussion phase is nearing its conclusion, we would like to confirm if our responses from a few days ago have effectively addressed your concerns. If you have any additional comments, we will do our best to address them.

Best regards,

The authors of Submission 30496.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Responses

Dear Area Chair and Reviewers,

We sincerely thank you for your thoughtful reviews and constructive feedback. To facilitate the Area Chair's assessment, we summarize the reviewers' feedback and our responses below.

We are pleased that the reviewers recognized the following strengths of our work:

  • The importance and practical value of improving distributed training through data sharding.
  • The effectiveness of our method across vision and LLM training, together with the theoretical insights connecting local objective approximation, gradient heterogeneity, and convergence.

We have addressed all reviewer comments in our detailed responses and further strengthened the manuscript. The major improvements are summarized below:

  • We demonstrate the effectiveness and practical regime of Coreset including LLM pretraining from scratch on mixed-domain data with a Nesterov outer optimizer, achieving 1.41 ×\times iteration speedup, lower validation perplexity, and higher downstream accuracy (Reviewer vu2B, Tables R1–R2).
  • We establish an improved gradient heterogeneity bound relative to Random through local objective approximation, reducing the corresponding convergence penalty and allowing longer synchronization intervals while retaining linear speedup (Reviewer tvrm).
  • We further characterize weighted stratified sharding through ablations and direct gradient measurements, demonstrating 6.1% lower average gradient heterogeneity than Random, with lower values across all ten training intervals (Reviewers tvrm, V1Dw, Tables R5–R7).
  • We further analyze repeated shard reconstructions, establishing an advantage over Random in bounding local objective variation at each reconstruction through dependence on the average rather than worst-case loss scale (Reviewer tvrm).
  • We demonstrate the practical value of repeated sharding through comparisons with IID minibatch sampling and fixed-shard LocalSGD, with only 0.25% additional total runtime over Random when accounting for data transfer and loss synchronization in two-server experiments (Reviewer tvrm, Tables R3–R4).
  • We clarify cached loss maintenance and training within a single-pass budget and demonstrate consistent speedups across different node counts (Reviewers vu2B, V1Dw).

All corresponding revisions are highlighted in blue in the manuscript.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.