Better scalability under potentially heavy-tailed feedback
This work addresses the scalability limitations of robust gradient descent for large learning problems, particularly when dealing with heavy-tailed feedback, which is a common challenge in real-world machine learning applications.
This paper proposes a scalable alternative to robust gradient descent (RGD) for scenarios with potentially heavy-tailed losses or gradients. Instead of robustly aggregating gradients at each step, their method focuses on robustly selecting or constructing a strong candidate from parallel stochastic sub-processes, leading to better scalability for large learning problems while maintaining RGD's formal merits.
We study scalable alternatives to robust gradient descent (RGD) techniques that can be used when the 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 instead focus computational effort on robustly choosing (or newly constructing) a strong candidate based on a collection of cheap stochastic sub-processes which can be run in parallel. The exact selection process depends on the convexity of the underlying objective, but in all cases, our selection technique amounts to a robust form of boosting the confidence of weak learners. In addition to formal guarantees, we also provide empirical analysis of robustness to perturbations to experimental conditions, under both sub-Gaussian and heavy-tailed data, along with applications to a variety of benchmark datasets. The overall take-away is an extensible procedure that is simple to implement, trivial to parallelize, which keeps the formal merits of RGD methods but scales much better to large learning problems.