  The success of machine learning (ML) has been intimately linked with the
availability of large amounts of data, typically collected from heterogeneous
sources and processed on vast networks of computing devices (also called {\em
workers}). Beyond accuracy, the use of ML in critical domains such as
healthcare and autonomous driving calls for robustness against {\em data
poisoning}and some {\em faulty workers}. The problem of {\em Byzantine ML}
formalizes these robustness issues by considering a distributed ML environment
in which workers (storing a portion of the global dataset) can deviate
arbitrarily from the prescribed algorithm. Although the problem has attracted a
lot of attention from a theoretical point of view, its practical importance for
addressing realistic faults (where the behavior of any worker is locally
constrained) remains unclear. It has been argued that the seemingly weaker
threat model where only workers' local datasets get poisoned is more
reasonable. We prove that, while tolerating a wider range of faulty behaviors,
Byzantine ML yields solutions that are, in a precise sense, optimal even under
the weaker data poisoning threat model. Then, we study a generic data poisoning
model wherein some workers have {\em fully-poisonous local data}, i.e., their
datasets are entirely corruptible, and the remainders have {\em
partially-poisonous local data}, i.e., only a fraction of their local datasets
is corruptible. We prove that Byzantine-robust schemes yield optimal solutions
against both these forms of data poisoning, and that the former is more harmful
when workers have {\em heterogeneous} local data.
