Concentration bounds for the empirical angular measure with statistical learning applications

Stéphan Clémençon, Hamid Jalalzai, Anne Sabourin, Johan SegersBernoulli 2023 · DOI · arXiv

TL;DR

This paper provides the first finite-sample concentration bounds for the empirical angular measure, a key tool in Extreme Value Theory (EVT) used to describe the dependence structure of rare, large-scale events. By establishing these non-asymptotic guarantees, the authors provide a solid theoretical foundation for applying statistical learning techniques—like anomaly detection and binary classification—specifically to the "tails" of a data distribution.

What Problem Does This Paper Address?

Most machine learning models are designed to perform well on "average" data. However, in fields like finance, insurance, and environmental science, the most important data points are the extremes (e.g., a stock market crash or a 100-year flood).

To model these, researchers use the angular measure, which describes the "direction" in which variables become extreme together. While we have ways to estimate this measure from data (the empirical angular measure), proving exactly how accurate these estimates are with a limited number of samples is notoriously difficult. The challenge is twofold:

  1. Unknown Marginals: We rarely know the underlying distribution of individual variables, so we use "ranks" to standardize data. This introduces complex dependencies that break standard statistical proofs.
  2. Rare Events: By definition, extreme data is scarce. Standard concentration inequalities (which tell us how fast an estimate converges to the truth) don't easily apply to events that happen with near-zero probability.

Methods

The authors bridge the gap between EVT and Statistical Learning Theory using several sophisticated tools:

  • Rank Transformation: They use a non-parametric approach based on data ranks to standardize the marginal distributions. This makes the method robust to outliers and scale-invariant.
  • Framing Sets: To handle the mathematical messiness of rank-based estimators, they "sandwich" random sets between two deterministic sets. This allows them to apply concentration inequalities to the deterministic bounds.
  • VC-Dimension: They use Vapnik-Chervonenkis (VC) theory to control the "combinatorial complexity" of the sets they are measuring. This ensures that the bounds hold uniformly across entire classes of shapes (like rectangles or half-spaces) on the unit sphere.
  • Tail Empirical Processes: They derive a new concentration inequality specifically for rare events, showing that the error scales roughly with $1/\sqrt{k}$, where $k$ is the number of extreme observations used.

Datasets

As a primarily theoretical paper, the authors do not use a massive real-world benchmark. Instead, they evaluate their findings using:

  • Simulated Monte Carlo Experiments: They generate data using Symmetric Dirichlet distributions on a unit simplex. This allows them to precisely control the "strength" of the extreme dependence and verify if their theoretical bounds match empirical observations.
  • Varying Dimensions: They test their results in dimensions $d=2$ through $d=5$ to observe how the "curse of dimensionality" affects the estimation of extreme dependence.

Key Insights and Ideas

  • The Rank Advantage: The paper proves that you can achieve strong theoretical guarantees even when you don't know the marginal distributions of your data, provided you use rank-based standardization.
  • The "Boundary" Constraint: A significant insight is the necessity of the $\tau$ parameter. The authors found that estimation error spikes near the axes of the coordinate system (where only one variable is extreme). To get stable bounds, they focus on the "relative interior" of the sphere.
  • The Logarithmic Mystery: Their bounds include a $\log k$ factor. In the bivariate (2D) case, previous asymptotic work suggested this might not be necessary. The authors leave it as an open question whether this factor is a fundamental property of high-dimensional extremes or an artifact of the current proof technique.

Key Results

  • Theorem 3.1: The "crown jewel" of the paper. It provides a high-probability bound on the difference between the true angular measure and the empirical estimate. It shows the error is proportional to $\sqrt{\frac{d \log(d/\delta)}{k}}$, where $d$ is dimension, $\delta$ is the confidence level, and $k$ is the number of extremes.
  • Anomaly Detection: They demonstrate that their bounds can provide "guarantees" for unsupervised anomaly detection. Specifically, they show how to find a "minimum volume set" on the sphere that contains a fixed proportion of the extreme mass.
  • Extreme Classification: They provide generalization bounds for binary classifiers that only look at the most extreme data points, proving that empirical risk minimization (ERM) is a valid strategy even in the tails.

Limitations and Future Work

  • Boundary Issues: The current theory struggles with sets that touch the boundaries of the positive orthant (where some components are not extreme). Extending the results to the "faces" of the sphere remains a challenge.
  • The $k$ Selection: Like much of EVT, the results depend on choosing the right threshold $k$ (how many points count as "extreme"). The paper doesn't provide an automated way to pick this optimally.
  • Beyond Indicators: The current work focuses on "sets" (indicator functions). The authors suggest that future work could extend this to more general continuous functions, which would be necessary for tasks like extreme regression.

Summary updated

Abstract

The angular measure on the unit sphere characterizes the first-order dependence structure of the components of a random vector in extreme regions and is defined in terms of standardized margins. Its statistical recovery is an important step in learning problems involving observations far away from the center. In the common situation that the components of the vector have different distributions, the rank transformation offers a convenient and robust way of standardizing data in order to build an empirical version of the angular measure based on the most extreme observations. However, the study of the sampling distribution of the resulting empirical angular measure is challenging. It is the purpose of the paper to establish finite-sample bounds for the maximal deviations between the empirical and true angular measures, uniformly over classes of Borel sets of controlled combinatorial complexity. The bounds are valid with high probability and, up to logarithmic factors, scale as the square root of the effective sample size. The bounds are applied to provide performance guarantees for two statistical learning procedures tailored to extreme regions of the input space and built upon the empirical angular measure: binary classification in extreme regions through empirical risk minimization and unsupervised anomaly detection through minimum-volume sets of the sphere.
BibTeX
@inproceedings{clemencon2023concentration,
  author = {Stéphan Clémençon and Hamid Jalalzai and Anne Sabourin and Johan Segers and Johan Segers},
  title = {{Concentration bounds for the empirical angular measure with statistical learning applications}},
  booktitle = {Bernoulli},
  year = {2023},
  doi = {10.3150/22-bej1562},
}
Figure