Zeno++: Robust Fully Asynchronous SGD

Cong Xie, Sanmi Koyejo, Indranil Gupta

Introduction

In large-scale distributed machine learning, practitioners typically choose between synchronous training (which is stable but slow, as the server must wait for the slowest "straggler") and asynchronous training (which is fast but messy). While asynchrony is often preferred for its speed, it introduces a massive security vulnerability: Byzantine failures.

A Byzantine worker can behave arbitrarily—sending random values, "poisoned" gradients, or even zeroed-out updates to prevent the model from converging. Most existing defenses assume a "majority honest" rule or require synchronous steps to compare workers against each other. In a truly asynchronous, heterogeneous environment, these assumptions fall apart. "Fast" malicious workers can overwhelm the server with garbage before a "slow" honest worker can even respond.

Zeno++ is a robust asynchronous Stochastic Gradient Descent (SGD) algorithm designed to keep distributed machine learning on track even when workers are malicious or failing. By using a small validation set on the server to "score" incoming updates, it can tolerate an unbounded number of Byzantine workers and arbitrary communication delays without needing to verify worker identities.

Methodology: The Stochastic Descent Score

The core innovation of Zeno++ is the Stochastic Descent Score. Instead of comparing workers to one another, the server evaluates each incoming gradient against a small, trusted validation dataset kept on the server.

  1. Zeno+ (The Prototype): The server calculates how much the loss would decrease if the candidate gradient were applied. It uses a score based on the difference between the loss before and after the update, minus a penalty for excessively large gradients. If the score is above a certain threshold, the update is accepted.
  2. Zeno++ (The Optimized Version): Calculating the full loss for every single incoming update is too computationally expensive for a high-performance server. Zeno++ approximates the descent score using a first-order Taylor expansion. This turns the check into a simple, efficient inner product between the candidate gradient and a "stale" validation gradient already computed on the server.
  3. Lazy Updates: To further save on computation, the server doesn't recompute its validation gradient for every worker update. It does so "lazily" in the background or every set number of iterations.

Crucially, Zeno++ does not require knowing who sent the gradient. This makes it naturally resistant to "Sybil attacks," where a single attacker creates many fake identities to subvert majority-voting schemes.

Key Insights

  • Quality over Identity: By focusing on the effect of an update on the loss function rather than the source of the update, Zeno++ bypasses the need for complex identity management or trust scores.
  • Staleness is a Feature: In asynchronous systems, gradients are often "stale" (based on an old version of the model). Zeno++ handles this by ensuring that even a stale update must demonstrate "optimization progress" on the server's current model to be accepted.
  • The Power of a Small Validation Set: You don't need a massive dataset on the server to filter out bad actors. A small, representative sample is enough to distinguish a helpful gradient from a malicious one.

Experimental Results

The authors evaluated Zeno++ on two standard benchmarks: CIFAR-10 (an image classification task using a CNN) and WikiText-2 (a language modeling task using an LSTM). They simulated Byzantine behavior using "sign-flipping" attacks, where malicious workers multiply the correct gradient by a large negative constant to actively push the model away from the optimum.

Zeno++ significantly outperformed the state-of-the-art baseline, Kardam, especially as the environment became more hostile.

Performance on CIFAR-10 under sign-flipping attacks.

Under severe sign-flipping attacks, Zeno++ maintained high Top-1 accuracy and low loss. In contrast, the baseline Kardam was effectively neutralized, performing no better than a model trained only on the tiny server validation set. Furthermore, Zeno++ proved much more robust to worker delay, maintaining a steady convergence rate where other methods slowed down or failed.

Test perplexity on the WikiText-2 dataset.

This robust performance extended to language modeling tasks as well, with Zeno++ achieving significantly lower test perplexity on WikiText-2 compared to vulnerable baselines.

Limitations and Future Work

  • The Trusted Dataset: Zeno++ relies on the server having access to a small, clean validation dataset. While usually feasible, this might be a hurdle in some privacy-sensitive or highly specialized domains.
  • Hyperparameter Sensitivity: The algorithm introduces new parameters like the gradient norm penalty and the acceptance threshold, which may require tuning for specific tasks.
  • Future Directions: The authors suggest exploring Zeno++ in the context of Federated Learning, where data privacy is paramount and the number of potentially unreliable participants is massive.

Summary updated

Abstract

We propose Zeno++, a new robust asynchronous Stochastic Gradient Descent(SGD) procedure, intended to tolerate Byzantine failures of workers. In contrast to previous work, Zeno++ removes several unr...
BibTeX
@inproceedings{xie2020zeno,
  author = {Cong Xie and Sanmi Koyejo and Indranil Gupta},
  title = {{Zeno++: Robust Fully Asynchronous SGD}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=eA04lPJZA4T},
}
Figure