Does Heavy-Tailed Gradient Noise Explain the CIFAR-10 Gap in Byzantine-Robust, Differentially Private Federated Learning? An Empirical Stress Test of Byz-Clip21-SGD2M

Abstract

Byz-Clip21-SGD2M (Islamov et al., 2026) provides high-probability convergence guarantees for federated learning under simultaneous Byzantine adversaries and differential-privacy (DP) noise, relaxing the bounded-gradient assumption behind the tight privacy-robustness-utility trade-off of Allouah et al. (2023b) to standard L-smoothness and σ-sub-Gaussian gradient noise. Its own empirical validation is MNIST-only, and its Conclusion lists heavy-tailed gradient noise as future work; we stress-test both the algorithm and its sub-Gaussian premise at CIFAR-10 scale. Using the established Hill-estimator/kurtosis tail-index methodology of Şimşekli et al. (2019) and follow-ons — applied here, not proposed as new — we find CIFAR-10's gradient noise consistently heavier-tailed than MNIST's across every statistic and configuration checked. Isolating ablations show the Byzantine-robustness mechanism itself performs comparably on both datasets, so the degradation is not robustness-specific; a dedicated DP-aware search over the clipping threshold τ, spanning the source paper's own privacy-budget grid, fails to recover non-degenerate CIFAR-10 accuracy even as DP noise is driven toward zero. This rules out both "DP noise alone explains the gap" and "the fixed-τ protocol was miscalibrated"; the evidence instead points to CIFAR-10's own clean-training convergence difficulty, plausibly linked to its heavier tail, as the dominant factor. A seed scale-up (CIFAR-10 sweep to n=10/cell, ablation to n=10/arm) with paired Wilcoxon testing confirms this: no CIFAR-10 condition differs significantly from any other, and the ablation's recovery to CIFAR-10's clean ceiling is statistically indistinguishable (p=1.000), not a small-sample artifact. An independent, unpaired Mann-Whitney U test further corroborates the hyperparameter-transfer gap under matched hyperparameters and round budget (U=100, p=0.000183). We also close this paper's previously most significant open limitation: we implement and unit-test the source paper's two external baselines, Safe-DSHB (Allouah et al., 2023b) and Byz-Clip-SGD (Islamov et al., 2026), from its appendix pseudocode, and run both under the identical protocol used for Byz-Clip21-SGD2M throughout. Under shared, non-independently-tuned hyperparameters, both baselines match or nominally exceed Byz-Clip21-SGD2M on several MNIST conditions — an exploratory finding, not confirmatory (the source paper's own independently-tuned comparison reaches the opposite conclusion, and none of these comparisons survive multiple-comparison correction). We then ran the independently-tuned comparison this gap called for (30-point (γ, τ) grid per baseline, matching the source paper's own tuning range): it erases the MNIST advantage seen under shared hyperparameters entirely (all 12 comparisons now p ≥ 0.06) without producing a Byz-Clip21-SGD2M advantage either, since our tuning remains a simplified, single-condition probe rather than the source paper's per-ε, DP-aware protocol — so whether Byz-Clip21-SGD2M has a genuine MNIST edge under equally careful tuning stays open. On CIFAR-10, all three algorithms are statistically indistinguishable and collapse to chance together, a more direct finding independent of any tuning caveat: the CIFAR-10 gap is not specific to Byz-Clip21-SGD2M. We report every known gap in our replication honestly, including a corrected theoretical positioning relative to Allouah et al.'s tight dimension-dependent lower bound and two corrections to our own earlier internal pilot analysis.