Nonadaptive multiscale one-bit gradient sketch

Integrate the method at the client-to-server gradient communication boundary, before error-feedback accumulation and before the server optimizer update. For each coordinate g[d] of a client gradient, assign the client-coordinate pair to a fixed public scale j from a schedule; generate a threshold U[d,j] from a shared pseudorandom seed, and transmit only b[d]=1{g[d]>=U[d,j]}. The server reconstructs z[d]=B_j(2b[d]-1). Maintain a separate sum and count for every coordinate and scale. Pseudocode: choose B_j=sigma_hat*2^j for j=0,...,J; set j=hash(round,client,d) mod (J+1); draw U uniformly from [-B_j,B_j]; send b; accumulate S_j[d]+=B_j*(2*b-1) and n_j[d]+=1; compute m_j[d]=S_j[d]/n_j[d]. Select the smallest scale j for which |m_j[d]-m_{j+1}[d]| is below tau_j=B_j*sqrt(2*log(2*D*(J+1)/delta)/n_j[d]); if none qualifies, use the largest scale. Feed the selected decoded vector to SGD, momentum, or AdamW, optionally with standard residual error feedback. The paper supplies the geometric scale count, threshold-unbiased clipped estimator, and moment-based clipping control. Estimate sigma_hat during a short warm-up using coordinatewise median absolute deviation or a clipped second moment; estimate tau_j from the known threshold range and sample count. First test CIFAR-10 with ResNet-18, eight simulated non-IID clients, and full participation. Compare FP32 all-reduce, signSGD, QSGD, and this sketch at equal transmitted bits. Record test accuracy versus communication bits, loss versus communication rounds, gradient cosine similarity, and saturation rates. A useful result would be 16-32x lower communication than FP32 with at most a one-percentage-point final-accuracy loss and better stability under synthetic heavy-tailed client gradients.