Revisiting Distributed Sign-Based Variance Reduction

TL;DR

The paper identifies a fundamental flaw in sign-based communication methods under data heterogeneity, where majority voting fails to converge to stationary points even with perfect local gradients. It introduces a new approach that tracks the global gradient via unbiased compression of recursive gradient updates, achieving convergence rates that match centralized settings. For finite-sum problems, periodic exact gradient refreshes combined with compressed differences yield sample complexities on par with centralized methods.

Why It Matters

This work enables more efficient distributed optimization in real-world scenarios with non-uniform data, where communication cost is a bottleneck. By eliminating bias in sign-based methods, it allows for faster training with reduced bandwidth usage without sacrificing convergence quality. The results are directly applicable to large-scale machine learning systems using federated or parallel computing.

Key Findings

• Majority voting in sign-based methods can fail to converge to stationary points due to bias from data heterogeneity, even with exact local gradients.
• The proposed method uses unbiased compression of recursive gradient increments to track the global gradient, enabling optimal convergence rates for nonconvex stochastic and finite-sum problems.