What to do
Where workers can return arbitrary vectors — hardware faults, silent data
corruption, a bad shard, a bug in one worker’s path, or untrusted
participants — replace the mean in the aggregation step with the
coordinate-wise median. Where the fraction of faulty workers alpha is
known or can be bounded, the coordinate-wise trimmed mean with
beta = c*alpha, c >= 1, achieves better statistical rates.
Prefer the median when alpha is unknown. That is the usual case, and the
trimmed mean’s advantage is contingent on a number the deployer does not have.
Why
The mean’s breakdown point is zero, and cluster size does not help.
LIT-344’s first result is the one that matters more than the algorithm it
proposes: a single Byzantine worker can drive the average to any value it
likes, regardless of n, because the average is unbounded in each
contribution. The intuition that a bad worker is diluted by many good ones is
wrong — dilution works on the direction of a bounded vector and not on an
unbounded one.
The two aggregators differ in what they need to know, not just in rate.
LIT-257 gives order-optimal rates for the trimmed mean under
sub-exponential gradients, and near-optimal rates for the median under the
weaker assumption of bounded skewness — crucially, without knowing alpha.
An aggregator parameterized by a quantity you are trying to detect is not
deployable.
Crash-only tolerance comes free. A crashed or hung worker is a special case of an arbitrary one, so guarantees that hold against adversarial workers hold a fortiori against failures — which is the regime real clusters are in.
What this does not settle
Cost is unmeasured here. A coordinate-wise median is not an all-reduce. Neither paper reports what replacing all-reduce with a robust aggregator does to step time on a large job, and that number is what decides whether this is worth doing when workers are trusted.
Convex and moderate-scale settings. The rates are for the statistical setting these papers analyze; nothing here demonstrates a robust aggregator on a large transformer pretraining run.
It interacts badly with compression. SOTA-214 keeps a local residual and assumes the aggregate is an average. What error feedback means under a median is not addressed by any paper in this record.