Near-Optimal Entrywise Anomaly Detection for Low-Rank Matrices with Sub-Exponential Noise

Vivek F. Farias, Andrew A. Li, Tianyi PengICML 2021 · OpenReview

This paper tackles the challenge of finding "needles in a haystack"—specifically, identifying anomalies in low-rank matrices when the data is obscured by significant, non-vanishing noise.

TL;DR

The authors introduce a new "Entrywise (EW) Algorithm" for anomaly detection that succeeds where traditional convex optimization methods fail: in high-noise environments like retail inventory management. By moving beyond aggregate error bounds to entrywise guarantees, they achieve the first min-max optimal detection rate for matrices with sub-exponential noise.

What Problem Does This Paper Address?

Many real-world datasets can be modeled as low-rank matrices (e.g., a table of sales across different stores and products). In these settings, we often look for three things: the underlying signal ($M^*$), random noise ($E$), and specific anomalies ($A$).

The "phantom inventory" problem in retail is a perfect example. A system might think a product is in stock, but it’s actually missing or misplaced. This shows up as an anomaly in sales data.

Existing state-of-the-art methods, like Stable Principal Component Pursuit (PCP), generally require the noise to be vanishingly small as the matrix grows. However, in retail, sales often follow a Poisson distribution where the noise scales with the signal. In these "noisy" regimes, standard methods struggle to distinguish between random fluctuations and actual anomalies.

Methods

The authors depart from the standard approach of solving a single, massive optimization problem to decompose the matrix. Instead, they propose a conceptually simpler two-step "Entrywise" approach:

  1. De-noising & Completion: They use a Singular Value Decomposition (SVD) based approach to estimate the low-rank structure. Crucially, they provide a new theoretical proof for entrywise error guarantees under sub-exponential noise. This means they can bound the error for every single cell in the matrix, not just the average error across the whole thing.
  2. Moment Matching & Inference: Because anomalies shift the mean of the data, the first step only recovers the signal up to an unknown scale. The algorithm uses a "moment matching" estimator (comparing empirical data distributions to theoretical ones) to identify the anomaly parameters.
  3. Classification: Finally, they treat anomaly detection as a classification task, using the estimated signal and noise parameters to calculate the probability that any given entry is an anomaly.

Datasets

The researchers evaluated their algorithm using:

  • Synthetic Data: $100 \times 100$ matrices where they controlled the rank, noise levels (Poisson and Exponential), and the frequency of anomalies.
  • Real-World Retail Data: A massive dataset from a consumer goods retailer consisting of weekly sales for 290 products across 2,481 stores. Since ground truth for anomalies is rarely labeled in the wild, they used the real sales data as a base and injected artificial anomalies to test the algorithm's recovery power.

Key Insights and Ideas

  • The Power of Entrywise Bounds: Most matrix completion theory focuses on the Frobenius norm (total aggregate error). This paper argues that for anomaly detection, aggregate error isn't enough—you need to know exactly how much you can trust the estimate of each specific entry to decide if it's an outlier.
  • Sub-Exponential is the New Black: While most researchers assume "Sub-Gaussian" noise (like the Bell Curve), this paper handles "Sub-Exponential" noise. This is a much broader class that includes Poisson and Exponential distributions, which are far more common in business and physical sciences.
  • Decoupling Works: The paper shows that trying to find the low-rank structure and the anomalies simultaneously (the standard convex approach) can be counterproductive when noise is high. Separating these tasks leads to better performance and faster computation.

Key Results

  • Theoretical Optimality: The authors prove that their algorithm achieves the min-max optimal detection rate (the best possible rate mathematically achievable) up to logarithmic factors.
  • Superior Accuracy: In synthetic tests, the EW algorithm significantly outperformed Stable PCP. On the real-world retail dataset, the EW algorithm achieved 19% higher accuracy (measured by Area Under the ROC Curve) than the best convex optimization benchmarks.
Scatter plot comparing the AUC of the EW algorithm against Stable PCP.
ROC curve demonstrating the True Positive Rate vs. False Positive Rate for the EW algorithm compared to Stable PCP.
  • Computational Efficiency: The main cost of the algorithm is a standard SVD and a sorting step, making it much faster and more scalable than iterative convex solvers. They estimate a $70,000 \times 10,000$ matrix could be processed in minutes.

Limitations and Future Work

  • Uniform Sampling Assumption: The current theory assumes that entries are observed at random (uniform sampling). The authors note that extending this to deterministic or non-uniform missing data patterns is a key next step.
  • Parameter Sensitivity: The performance currently depends on constants ($K$ and $L$) related to the noise distribution. A more refined analysis might reduce this dependency.
  • Real-World Ground Truth: While the retail data test was successful, it relied on injected anomalies. The authors highlight the need to test the algorithm on datasets where anomalies are naturally occurring and manually verified.

Summary updated

Abstract

We study the problem of identifying anomalies in a low-rank matrix observed with sub-exponential noise, motivated by applications in retail and inventory management. State of the art approaches to ...
BibTeX
@inproceedings{farias2021near,
  author = {Vivek F. Farias and Andrew A. Li and Tianyi Peng},
  title = {{Near-Optimal Entrywise Anomaly Detection for Low-Rank Matrices with Sub-Exponential Noise}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=zKhGkFh5KEw},
}
Figure