Tight Asymptotics of Extreme Order Statistics

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 secondprice 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 ℓ-th maximum of the n samples be? For ℓ = 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 ℓ > 1. Surprisingly, in