Robustness and scalability under heavy tails, without strong convexity

Matthew HollandAISTATS 2021

Introduction

In real-world machine learning applications, data is rarely pristine. Outliers and "heavy-tailed" distributions are common, yet standard algorithms like Empirical Risk Minimization (ERM) are notoriously sensitive to these extreme values because they rely on simple sample means. While robust alternatives exist, they often suffer from two major drawbacks: a reliance on the "luxury" of strong convexity and poor computational scalability in high-dimensional settings.

This paper introduces RV-SGDAve, a simple and scalable strategy designed to provide high-confidence performance guarantees without requiring strong convexity. By shifting the focus from per-step robust optimization to a robust validation framework, the proposed method achieves significant efficiency gains while maintaining theoretical sharpness.

The Scalability and Convexity Gap

Existing robust gradient descent (RGD) methods typically require expensive robust sub-routines at every iteration. These sub-routines often scale poorly with the number of dimensions ($d$), creating a "scalability wall" for large-scale problems. Furthermore, many of these strategies assume the loss function is strongly convex, an assumption that rarely holds in complex, high-dimensional models.

Matthew Holland tackles this by asking: Can we build a robust learner that is both computationally efficient and theoretically sound, even when the loss function is just "regular" convex?

The RV-SGDAve Framework: Partition, Train, and Validate

The author proposes a "divide and conquer" approach that moves the heavy lifting of robustification from the $d$-dimensional vector space of gradients to a 1-dimensional scalar space of loss values. The RV-SGDAve process consists of four main steps:

  1. Partition: The training data is split into $k$ independent subsets.
  2. Parallel Training: Standard Stochastic Gradient Descent (SGD) is run on each subset in parallel to generate $k$ candidate models. Because these are standard SGD runs, they are fast and can be executed in parallel.
  3. Robust Validation: Instead of a simple average or sample mean, the algorithm employs a Catoni-type M-estimator to provide a high-precision, robust estimate of the risk for each candidate.
  4. Selection: The model with the lowest robustly-estimated risk is selected.

The core insight is that you only need at least one of the $k$ parallel runs to produce a high-quality candidate. As long as the validation routine is robust enough to identify that candidate amidst heavy-tailed noise, the overall learner succeeds.

Empirical Results and Efficiency

The effectiveness of RV-SGDAve was tested using synthetic noisy convex minimization tasks, comparing well-behaved Normal noise against erratic log-Normal (heavy-tailed) noise.

Performance comparison of RV-SGDAve against baselines under Normal (left) and log-Normal (right) noise conditions. Note how standard cross-validation (dashed lines) fails under heavy tails.

As shown in the experimental results, RV-SGDAve remains stable even under heavy-tailed distributions where naive cross-validation fails spectacularly. Because the robust M-estimator operates on scalar losses rather than gradient vectors, the statistical guarantees are largely independent of dimensionality.

Computation time scaling with respect to dimensionality. RV-SGDAve maintains near-constant overhead compared to methods that scale poorly as dimensions increase.

Computationally, RV-SGDAve offers a massive advantage. While competing RGD methods scale with the number of iterations $T$, the proposed method's cost is $O(dn \log(1/\delta))$. This allows it to match the performance of complex benchmarks in a fraction of the time, especially as the dimensionality of the problem grows.

Conclusion

RV-SGDAve demonstrates that robust machine learning does not have to be computationally prohibitive or reliant on strong convexity. While currently limited to convex loss functions and finite variance scenarios, the "Partition, Train, and Validate" framework provides a powerful blueprint for scaling robust learners to high-dimensional, real-world data. Future work may extend these principles to non-convex landscapes, such as deep neural networks.

Summary updated

BibTeX
@inproceedings{holland2021robustness,
  author = {Matthew Holland},
  title = {{Robustness and scalability under heavy tails, without strong convexity}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
}

Loading related content...

Figure