Decoder-Side Refinement for Heavy-Tailed Gradients

1. Integration point: modify the per-worker gradient communication layer in synchronous data-parallel or federated SGD. Treat each gradient coordinate, or a block of coordinates sharing a scale, as a scalar X. Estimate a coarse center c for the server-side mean gradient using logarithmic dyadic threshold bits over the known range [−λ,λ].

2. Non-adaptive encoding pseudocode:

for worker gradient x and scale j:
    for b in {0,1} and bp in {0,1}:
        L = 8*tau*2**j
        f = rho(2*L,bp,x) - rho(L,b,x)
        h = f + L
        U = public_uniform(0, 3*L)
        send B[j,b,bp] = int(U <= h)
server:
    c = decode_coarse_center(localization_bits)
    for j:
        choose safe phases b_j,b_{j+1} from c
        fhat_j = 3*L_j*mean(B[j,b_j,b_{j+1}]) - L_j
    combine fhat_j with the telescoping residue reconstruction
    ghat = c + sum_j fhat_j
    apply AdamW/SGD using ghat

Here rho(L,b,x) is a periodic residue, implemented as a centered modulo map with period L and phase shift bL/2. The two phases differ by half a period, so at least one phase has no boundary near the coarse center. For an MVP, transmit all four phase-pair bits per scale; this preserves the decoder-side selection property at constant-factor communication overhead.

3. The paper supplies the scale choices, phase-selection logic, and moment-dependent error and second-moment targets. Estimate τ online from a robust running median of per-coordinate absolute deviations, such as tau=1.4826*median(|x−median(x)|), and estimate λ from the permitted gradient range or a slowly updated robust bound. If using continuous scales, sample r from a proxy density proportional to 1/r on [r_−,r_+]; compare this with the dyadic version rather than assuming the unspecified density is optimal. Use independent bit groups and median-of-means to amplify confidence.

4. First experiment: train ResNet-18 on CIFAR-10 with 8 or 16 workers and artificially heavy-tailed per-worker gradients using Student-t perturbations or by disabling ordinary gradient clipping. Compare FP32 all-reduce, signSGD, QSGD, and this method at equal transmitted bits. Measure loss descent at equal communication, final accuracy, aggregate-gradient MSE, clipping frequency, and out-of-range update frequency. Success means lower aggregate-gradient MSE and smoother training than signSGD at the same bits, with at least 2x communication reduction versus FP32 all-reduce at matched accuracy.