TL;DR
The authors introduce FAR-SIGN (Fully Asynchronous Robust optimization via SIGNed directional projections), the first distributed learning algorithm that is simultaneously fully asynchronous and resilient to adversarial (Byzantine) workers. By combining signed directional updates with a two-timescale tracking mechanism, FAR-SIGN achieves optimal convergence rates for both gradient-based (first-order) and gradient-free (zeroth-order) optimization without requiring server-side buffering or a private reference dataset.
What Problem Does This Paper Address?
Modern large-scale machine learning relies heavily on distributed parameter-server-worker architectures. However, scaling up introduces two major headaches: stragglers (workers delayed by network or hardware issues) and Byzantine faults (faulty or malicious workers sending corrupted data to derail training).
To handle Byzantine workers, traditional methods use robust aggregation rules (like coordinate-wise medians or trimmed means), but these require synchronous rounds where the server waits for a quorum of workers. This completely sacrifices the speed benefits of asynchronous execution. Existing asynchronous robust methods attempt to fix this by buffering updates or validating them against a clean reference dataset at the server, which reintroduces bottlenecks and privacy concerns. Furthermore, robust optimization in the zeroth-order (gradient-free) setting remained entirely unexplored in asynchronous networks.
Methods
The authors propose FAR-SIGN, an event-driven framework that updates model parameters immediately upon receiving a single update from any worker. It avoids the pitfalls of standard asynchronous robust methods through three key components:
- Fixed Dictionary Sampling (FDS): Each worker is assigned a fixed dictionary of probing directions. Instead of computing full gradients, workers return directional derivative estimates (or finite-difference approximations in the zeroth-order setting) along these specific directions.
- Signed Directional Updates: The server updates parameters using only the sign of the feedback. This prevents adversarial workers from blowing up the optimization process with arbitrarily large malicious gradients.
- Two-Timescale Tracking: Sign-based stochastic gradient descent (sign-SGD) is notoriously biased under asymmetric noise. FAR-SIGN solves this by introducing a two-timescale stochastic approximation. The server maintains a running average of directional derivatives on a slower timescale, while updating the actual model parameters on a faster timescale. This effectively filters out noise and controls the sign bias.
FAR-SIGN supports both first-order (gradient projections) and zeroth-order (two-point finite differences) feedback.
Datasets
The algorithm was evaluated on the standard MNIST handwritten digit classification dataset. The training data was split near-homogeneously across 51 virtual workers within a parameter-server architecture.
Key Insights and Ideas
- Ditching the Quorum: Traditional Byzantine defense requires a batch of updates to isolate outliers. FAR-SIGN proves that you can safely update on every single arrival if your updates are structurally bounded via signed directional projections.
- Low-Pass Filtering the Sign Bias: Sign-SGD typically requires strict symmetry or unimodality assumptions on noise to guarantee convergence. FAR-SIGN’s two-timescale tracking acts as a low-pass filter, allowing almost-sure convergence under standard zero-mean, bounded-variance noise.
- Plugging the Zeroth-Order Gap: FAR-SIGN provides the first theoretical guarantees and empirical framework for asynchronous, adversary-robust zeroth-order optimization, achieving standard non-convex rates of $O(n^{-1/6+\epsilon})$ under independent noise and $O(n^{-1/2+\epsilon})$ under coupled noise.
Key Results
The authors simulated a network with 24% Byzantine workers executing various malicious attacks (Sign-Flip, Constant, Gaussian Noise, and ALIE).
- Massive Speedups: Because FAR-SIGN is non-buffered and utilizes sparse coordinate-wise operations, it reached 80% test accuracy on MNIST in just 11 to 37 seconds across all attack scenarios. In contrast, the fastest robust-aggregation baseline (CYBER-0 paired with RFA or Median) required 223 to 420 seconds—representing a 6.2× to 35.2× wall-clock speedup.
- High Robustness: FAR-SIGN maintained a final accuracy of 89.0% under constant attack and 89.6% without attacks. Several baselines completely collapsed under identical conditions; for instance, CYBER-0 with a Trimmed Mean aggregation dropped to ~10% accuracy under Gaussian and Constant attacks.
Limitations and Future Work
The primary limitation acknowledged in the paper is the assumption of homogeneous worker objectives, meaning all honest workers are assumed to sample data from the exact same global distribution.
An important direction for future work is extending FAR-SIGN's mathematical framework to heterogeneous objectives, which is vital for real-world Federated Learning setups where data distributions across clients vary significantly. Additionally, testing the algorithm on larger deep learning architectures and more complex vision/NLP benchmarks remains to be done.
Summary updated