Tight Asymptotics of Extreme Order Statistics

Jose Correa, Frederik Mallmann-Trenn, Matias RomeroNeurIPS 2025 · OpenReview

Introduction

In fields ranging from auction theory—where revenue often depends on the second-highest bid—to machine learning, where robust loss functions might ignore top-$\ell$ outliers, understanding the behavior of "extreme order statistics" is crucial. A classic statistical result states that for any distribution with a finite mean, the expected maximum of $n$ independent samples, $M_1(n)$, grows strictly slower than $n$ (i.e., $o(n)$).

However, it was previously unclear if the second, third, or $\ell$-th maximum followed similar asymptotic rules. Intuitively, one might expect the second maximum to stay relatively "close" to the first. This paper proves that intuition wrong: there is a surprisingly stark difference between the growth potential of the absolute maximum and every other extreme value below it. While the maximum can grow almost linearly, the "runner-up" is subject to a much stricter speed limit.

Theoretical Framework

The authors employ a mix of rigorous probabilistic proofs and numerical simulations, relying on two primary theoretical innovations:

  1. Escalator Distributions: The researchers introduce a method to transform any distribution with a finite expectation into a simplified "escalator" form—a discrete distribution taking values on a specific sequence of points. They prove that the asymptotic behavior of the $\ell$-th maximum remains unchanged under this transformation, making the mathematics significantly more tractable.
  2. Summation Criterion: They establish a necessary and sufficient condition for growth. A growth rate $g(n)$ is achievable for the $\ell$-th maximum if and only if the infinite series $\sum_{n=1}^{\infty} \frac{g(n)}{n^2}$ converges. This criterion precisely pins down the "speed limit" of these statistics.

Key Insights and Results

The theoretical bounds derived in the paper reveal a sharp phase transition in how extreme order statistics behave.

The "Loner" Maximum: The first maximum is an outlier. While $M_1(n)$ can grow at a rate nearly $O(n)$, the authors prove that for any fixed $\ell > 1$, the largest possible growth rate is bounded by $O(\frac{n}{\log(n) \log \log(n)})$ and $\Omega(\frac{n}{\log(n) (\log \log(n))^{1.01}})$. If a distribution has finite variance, the $\ell$-th maximum cannot grow faster than $\Omega(\sqrt{n / \log n})$.

Growth of extreme order statistics

Stability in the Chaos: To validate these bounds, the authors simulated synthetic heavy-tailed distributions (e.g., using tail-quantile functions like $T(y) = \frac{y}{\log(y)^{1.01}}$ for infinite variance) across 1,000,000 independent trials for sample sizes up to $n=10,000$.

Perhaps the most surprising empirical finding is the behavior of the ratios between these statistics. Even when the variance is infinite—making the maximum extremely volatile—the ratio between the first and second maximum is remarkably stable in 99% of typical cases. The wild, worst-case growth of the maximum is driven almost entirely by the rarest 1% of events.

Ratios of consecutive order statistics

Limitations and Future Work

  • Fixed vs. Scaling $\ell$: The current proofs focus on a fixed $\ell$ (e.g., the 2nd or 3rd maximum). An open question remains for the "intermediate" regime where $\ell$ grows with $n$ (such as analyzing the top $\sqrt{n}$ elements).
  • Distribution of Ratios: While the stability of the ratio $M_1/M_2$ was observed empirically, a formal theoretical characterization of the full distribution of this ratio is left for future research.
  • Finite Moments: Further work is needed to fully understand the behavior of the second maximum when assuming specific higher-order moments are finite.

Summary updated

Abstract

A classic statistical problem is to study the asymptotic behavior of the order statistics of a large number of independent samples taken from a distribution with finite expectation. This behavior has implications for several core problems in machine learning and economics—including robust learning under adversarial noise, best-arm identification in bandit algorithms, revenue estimation in second- price auctions, and the analysis of tail-sensitive statistics used in out-of-distribution detection. The research question we tackle in this paper is: How large can the expectation of the $\ell$-th maximum of the $n$ samples be? For $\ell=1$, i.e., the maximum, this expectation is known to grow as $o(n)$, which can be shown to be tight. We show that there is a sharp contrast when considering any fixed $\ell>1$. Surprisingly, in this case, the largest possible growth rate for all fixed $\ell>1$ is $O(\frac{n}{\log(n)\log\log(n)})$ and $\Omega(\frac{n}{\log(n)(\log\log(n))^{1.01}})$. Our result is actually finer than the latter and provides a sharp characterization of the largest achievable growth rate for the expectation of the $\ell$-th maximum of $n$ i.i.d. samples. Beyond the theoretical analysis, we support our findings with extensive simulations. These empirical results highlight a notable phenomenon: although the multiplicative gap between the maximum and the second maximum grows quickly with $n$, the ratio remains approximately constant in 99\% of trials. This suggests that while worst-case growth is sharp and meaningful, typical-case behavior may be significantly more stable.
BibTeX
@inproceedings{correa2025tight,
  author = {Jose Correa and Frederik Mallmann-Trenn and Matias Romero},
  title = {{Tight Asymptotics of Extreme Order Statistics}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=padrqCRyCP},
}
Figure