Robust Unsupervised Learning via L-statistic Minimization

Andreas Maurer, Daniela Angela Parletta, Andrea Paudice, Massimiliano PontilICML 2021 · OpenReview

The Vulnerability of Unsupervised Learning

Standard machine learning algorithms, particularly unsupervised methods like K-means clustering or Principal Subspace Analysis (PSA), are notoriously sensitive to outliers. Because these methods typically minimize the average reconstruction error across a dataset, a single extreme data point can disproportionately "pull" the entire model toward it. This results in poor performance on the clean, representative data you actually care about.

While "outlier rejection" is a common pre-processing step, it introduces a catch-22: identifying what constitutes an outlier often requires an accurate model, but building an accurate model requires removing the outliers first. Instead of trying to identify and delete outliers beforehand, this paper proposes designing learning objectives that naturally focus on the "sufficient portion of the data" that fits the hypothesized model.

The L-Statistic Solution

The core innovation of this paper is replacing standard average loss minimization with L-statistic minimization.

In a standard setup, you minimize the mean loss. The L-statistic approach modifies this through a three-step process:

  1. Calculate the losses for all data points given a candidate model.
  2. Rank these losses from smallest to largest.
  3. Weight and average these ranked losses using a non-increasing weight function.

A practical and highly effective version of this is "hard-thresholding." In this setup, the algorithm might only average the smallest 70% or 80% of losses, completely ignoring the largest ones. By doing so, extreme outliers are structurally prevented from dominating the objective function.

Illustration of the target distribution (dark) vs. the perturbing distribution (light) in Principal Subspace Analysis.

To solve this new objective, the authors introduce a general meta-algorithm that alternates between two steps:

  • Sorting: Rank the current losses to find the optimal permutation of data points.
  • Descent: Update the model parameters using a standard "Descent Oracle" (e.g., a modified Lloyd's update for K-means or an eigenvector calculation for PSA) while keeping the weights fixed to their ranked positions.

Key Insights and Theoretical Guarantees

This framework offers several compelling theoretical advantages:

  • Bounded Influence: Unlike the standard mean, which has an unbounded "influence function" (where one point can change the result infinitely), the L-statistic objective with truncated weights has a strictly bounded influence. This is the mathematical foundation of its robustness.
  • Model-Agnostic: This isn't a single algorithm, but a "robustifying" wrapper. It can be applied to any unsupervised task where a descent algorithm exists for the underlying loss.
  • Generalization Bounds: The paper provides rigorous proofs, utilizing advanced tools like Rademacher averages, to show that a model trained to minimize this robust objective on a finite sample will generalize well to the true, underlying "clean" distribution.
  • Handling Misspecification: The method is surprisingly resilient to incorrect hyperparameters. For example, if you ask for $k=2$ clusters but the data contains 3, the robust objective can focus entirely on the two most prominent clusters rather than awkwardly merging them to accommodate the third.

Empirical Results

The authors evaluated their proposed methods—RKM (Robust K-Means) and RPSA (Robust PSA)—on both synthetic 2D data and corrupted versions of the Fashion-MNIST dataset. In the Fashion-MNIST tests, two classes (e.g., sneakers and trousers) were treated as "inliers," while heavy sampling from the other eight classes served as unstructured outliers.

Comprehensive results showing RKM's success on synthetic 2D clustering (top), Fashion-MNIST reconstructions (bottom left), and test error stability across threshold parameter $\zeta$ (bottom right).

The robust methods consistently outperformed standard baselines like K-means++ and Spherical Depth pre-processing:

  • Visual Success: In synthetic tests with high-variance outliers, RKM correctly identified true cluster centers, whereas standard K-means++ failed, placing centers in empty space to minimize outlier penalties.
  • Fashion-MNIST Performance: RKM achieved significantly lower test error on the inlier classes and produced visibly sharper reconstructed cluster centers.
  • Parameter Stability: The method proved highly stable regarding the choice of $\zeta$ (the fraction of data kept). As long as $\zeta$ was roughly in the ballpark of the true inlier fraction, performance remained optimal.

Limitations and Future Work

While powerful, the L-statistic framework has limitations. Because the meta-algorithm is a descent method, it guarantees improvement at each step but can still get stuck in local minima—a common issue in clustering. Additionally, while the method is stable, it still requires the user to estimate the threshold parameter $\zeta$ (the expected fraction of clean data).

Future work may focus on automatically estimating this optimal outlier fraction and extending the L-statistic framework to robustify supervised learning methods, such as Canonical Correlation Analysis (CCA).

Summary updated

Abstract

Designing learning algorithms that are resistant to perturbations of the underlying data distribution is a problem of wide practical and theoretical importance. We present a general approach to thi...
BibTeX
@inproceedings{maurer2021robust,
  author = {Andreas Maurer and Daniela Angela Parletta and Andrea Paudice and Massimiliano Pontil},
  title = {{Robust Unsupervised Learning via L-statistic Minimization}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=SkURbkf0R2N},
}
Figure