Robust SGD under Dataset-Level Corruption: A Batch-Size Rule and an Estimator Separation

We study the effect of dataset-level corruption on robust stochastic gradient descent: an adversary inspects an i.i.d. sample, replaces an $\epsilon$-fraction of its points before training, and makes no further interventions. In each iteration of training, a robust gradient estimator aggregates gradients from various data minibatches. In this model, the dataset-level corruption as well as sampling without replacement induces dependent minibatch corruptions. Still, under reasonable per-iterate sampling budget, we derive a minibatch-size-selecting rule with certified mean-squared error bound for general robust gradient estimators with so-called majority-ball property, which is then connected to the algorithmic convergence behavior by an inexact-gradient analysis. We also establish a population separation theorem between two robust aggregators, the geometric-median and the so-called radius-based estimator: For a centrally symmetric population, the geometric median converges to the clean population median under vanishing Huber-type contamination, whereas a contamination-dependent family keeps the population radius estimator a fixed positive distance from the clean center. The theorem arguably explains our MNIST experiments --- empirically, geometric median consistently outperforms radius for relatively small minibatch sizes like $b=8$. As $b$ gets larger, such phenomenon vanishes.