Scaling-Up Robust Gradient Descent Techniques

We study a scalable alternative to robust gradient descent (RGD) techniques that can be used when losses and/or gradients can be heavy-tailed, though this will be unknown to the learner. The core technique is simple: instead of trying to robustly aggregate gradients at each step, which is costly and leads to sub-optimal dimension dependence in risk bounds, we choose a candidate which does not diverge too far from the majority of cheap stochastic sub-processes run over partitioned data. This lets us retain the formal strength of RGD methods at a fraction of the cost. Z L(w; z) P(dz), w∈ W. Here we have a loss function L : W ×Z → R + , and random data Z ∼ P takes values in a set Z. At most, any learning algorithm will have access to n data points sampled from P, denoted Z 1 , . . . , Z n . Write (Z 1 , . . . , Z n ) → w n to denote the output of an arbitrary learning algorithm. The usual starting point for analyzing algorithm performance is the estimation error R P ( w n )-R * P , where R * P . . = infR P (w) : w ∈