Tight Asymptotics of Extreme Order Statistics
Authors: Jose Correa
Frederik Mallmann-Trenn
Matias Romero
Venue: NeurIPS 2025 poster ()
Keywords: Order statistics
Asymptotic analysis
Primary area: theory
TL;DR: We provide tight asymptotic bounds for the expected top-ℓ order statistics under minimal moment assumptions, revealing a sharp separation between the maximum and second-largest values.

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.

Tight Asymptotics of Extreme Order Statisties
José R. Correa Universidad Chile correa@uchile..l
Frederik Mallmann-Trent Trenn King's College London frederik.ma
.uk
Matías Romero
Columbia University
mer22220columbii edu
Abstract
A classic statistical problem 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 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-sensitic statistics used in out-of-distribution detection.
The research question we tackle in this paper is: How large can the expectation the Ê-th maximum the n samples be? For & 1, i.e., the maximum, this expectation is known to grow o(n), which can be shown to be tight. We show that there a sharp contrast when considering any fixed this case, the largest possible growth rate for all fixed é 1 is O log(n) log log(n) and S2( [og (o) Our result is actually finer than the latter and provides a sharp characterization of the largest achievable growth rate for the expectation the f-th maximum of i.i.d. samples.
1. Surprisingly,
Beyond theoretical analysis, we support our findings with extensive simulations. These empirical results highlight notable phenomenon: although the multiplica- tive gap between the maximum and the second maximum grows quickly with 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.
Introduction
fundamental problem in applied probability and statistics is to estimate the distribution of the maxima and minima of a set of independent and identically distributed random variables. Specifically, the setting we study in this paper is the following. Let and identically distributed (i.i.d.) random variables drawn from distribution F. The corresponding order statistics are:
be non-negative independent
min X; [r(
X1.0 S X2. < Xpen
max X,. sE[n]
Our object of interest is Mn(n) Mf (n) E E 1t Our goal is study the asymptotics of Mz(n). particular, we are interested in the largest possible rate which Mc(n) can grow.
When clear from context we will drop the dependence on F.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

104
10a
Main)
Main)
10a
Myin)
Main)
10a
Expectation
2000
4000
6000
8000
10000
Sample size n
Figure Simulation of expected extremes for a distribution with finite expectation but infinite variance Ssctionn 5 for more details).
Interestingly, while the expectation of the maximum sample, M1 (n), has been widely studied, the situation is radically different for Mn(n) with & > 1. The first obvious bound follows since the maximum is upper bounded by the sum and thus Mj (n) n. nEE [X1], so that, if we have finite expectation distribution, we get that M1 = (n). Furthermore, tighter bounds have long been studied assuming more constraints of the distribution such finite moments (e.g.. s..33 and 5 The bound of Mi (n) = O(n) is actually achievable the distribution F can depend on n, however when F is fixed and only n grows, stronger bound can be obtained: Furthermore, Downey proves that this bound is essentially the best possible in the sense that for all > 0 there exists a distribution F, such that M1 (n) [2nn 2nn Recently, [8] strengthened the lower bound by showing that for any sublinear function (n),, there exists finite expectation distribution F such that M1 (m) (gg()) This completes the picture for the asymptotic behaviour of M1 (n)) it holds that (n) o(n), but for any function (nn) E o(n) there exists finite expectation distribution such that Mf (n) 2 g(m).
[TO] established that (n) = o(n).
In this paper, we explore the asymptotic behavior of the second maximum of n i.i.d. samples and, more generally, Me(n) for fixed 1. The natural reaction here is that the asymptotic behavior of M2(n) should be essentially the same as that of Mn.n). However, we show a surprisingly stark difference and that the comparison between the first and second maxima is more delicate (seeFFigure I). On the one hand, we note that for any sublinear function g(n), there exists distribution F with finite expectation such that Mf" f (n) 2 g(2) for infinitely many values n. other words, we show that lim sup, M (n)) m) > 0. On the flip side, if we want to have the inequality for all then we prove that no such distribution exists. This involves studying the lim inf, (2))/g()) which positive if and only if the Mn)n) {(g(n)) Perhaps surprisingly, our results imply that if we take g(n) = log(n) log (n] then for any distribution lim inf, M2 M2(n)/g(m) = O, whereas for g(n) = [og log(() 1o) there exists finite expectation distribution such that lim inf,, M2(n)/9(1) > 0. More precisely. in Theorem we obtain tight characterization that generalizes to the f-th largest sample for any fixed E. Our necessary condition to have M (n) = ((g(n)) generalizes easily for
distributions with higher moments: if F has finite variance, in particular, Mf" (n) = (v impossible.
log is
1.1 Additional Related Work
In the asymptotic case of order statistics the goal to study the properties of X as n tends to infinity. A plethora of results are known for asymptotic distributions, theory of extremes and even extremal processes, which have been developed at length [TT. Their results depend on
p limm- k/n [0, 1] and they study three categories (19); (1) Central quantile case: If p E 1), (2) Extreme case: p E (0. 1}. for fixed k. X and Xn-k+1mn are usually called the th lower and upper extremes, respectively, (3) Intermediate case: If p E {0, with k k(n) oo. The scope of our work lies in the second case.
Innterestingly, lim limsup, (2(n))9(n1) and lim inf, M2(re/9((n) may well be different.

---

Results that study the asymptotic behavior of the expected maximum have been further stud- ied in 12, who show that if [ oc, then the expected maximum Mi(n) S E [X]
n E X E [X]] = O(n²), and for each the bound is achievable by an extremal distribu- tion F... S give bounds on the expected k-th order statistic (i.e., kem] Mn (1)) using
information about the first and second moment improving the work of 4 and of [7]. When F is fixed
and does not depend on n much stronger and general bound can be obtained. Indeed, [10] shows
that Mf (n) onn) I An alternative and simpler proof of Downey's ' result was recently given by [8]
They also prove an impossibility result showing that the o(z) bound cannot be improved. Specifically,
they showed that for any function 9 with sublinear growth, namely such that g(n) = o(n), there is finite expectation distribution F such that Mf (n) = (2((n))..
Applications
While our primary motivation is theoretical, the asymptotic behavior of extreme order statistics plays a fundamental role in several areas of machine learning and economics. Below, we highlight key settings where our results yield insights.
1. Robust Learning and Adversarial Risk. In robust learning, models are often evaluated under worst-case scenarios, such adversarial examples or corrupted data. Rather than minimizing the average loss, some approaches focus on the largest or top-& losses across training examples. Our tight bounds on the ε-th largest sample provide a principled under- standing of how such tail-sensitive objectives scale with the number of examples, especially when the underlying distribution has heavy tails [14]
2. Best-Arm Identification in Bandits. In stochastic multi-armed bandit problems, particularly in pure exploration settings, identifying the top-performing arms often involves analyzing the largest observed rewards. The expectation of the b-th maximum is directly tied evaluating near-optimal arms [33.
3. Second-Price Auctions. In recond-price (Vickrey) auctions, the seller's 's revenue is deter- mined by the second-highest bid. When the distribution of bidders' values is unknown or adversarially chosen, our results provide tight upper bounds on the expected revenue a seller can achieve. This supports worst-case analysis in auction design and recent approaches for detecting collusion setting reserve prices in data-agnostic ways M
4. Out-of-Distributiio (OOD) Detection. Tail-sensitive scoring functions- such maximum softmax scores or energy-based confidence measures- are widely used for detecting out- of-distribution inputs in classification models 15] While work does not propose new detection methods, it offers theoretical insights into how the extreme scores behave as the sample size grows. For example, if the second larges value appears grow faster than //log log n), then it's likely an outlier. This may aid in understanding failure modes and calibrating thresholds in high-dimensional or heavy-tailed settings.
5. Stability of Random Forests. The sensitivity of the output of a machine learning algorithm to the removal of single training point- commonyyy referred to as algorithmic stability-
widely studied in the machine learning literature 6 18 Recent work by 19 establishes the stability of random forest predictors in regression tasks by showing that it follows from the sublinear growth of the expected maximum of the squared response, a condition satisfied under finite variance. Our bounds on the f-th largest order statistic may support the analysis of stability guarantees for heavy-tailed responses, where clipping the prediction outcome to some data-dependent range, defined by extreme order statistics, can help control the scale of the model's 's outputs [8].
1.2 Overview of our Results
Our main result is to obtain tight characterization of the lim inf,, MF (n)/g(n) for any finite expec- tation distribution F. Recall that for any F, .M (n) = o(n). so that we have lim inf, M (n)/n and we also know that for any sublinear g(n), there are F's for which lim inf, M (n)/g(n) > 0
10
g
Mooe generally Downey establishes that if E [X]] < co, then Mf (n) (())..
3

---

One would expect that the situation for the second, or third maximum would be the same. However, we show that the behavior changes radically. While easy to observe that for any sublinear g(n) = o(n), there exists finite expectation F such that Mf (n) 2 g(n) infinitely often for any constant + when looking at the actual growth rate (given by the lim inf,, (2) (n)/g(n)) this threshold function g(n) changes dramatically.
In Theorem 2] we show that for 2 2, there exists a finite expectation distribution F such that g(x)
Mf(n) = (n)(()) if and only if Σ>, n² 00. This means that if g(n) satisfies the previous condition f then there are finite expectation distribution F for which lim inf, M (n))/(n) > However, if, on the contrary, Σ,, 2(m) xo then lim inf, M (n)/g(n) = 0 for any finite expectation distribution F. As resuit, the growth rate of the L-th maximum cannot be larger than n/ (log n log no) (see Section for precise bounds).
nd
A key feature of our analysis is simple transformation of any finite expectation distribution F into a distribution F+ which takes the form of escalator. This done in Section 2 Then, our analysis consists of two keys parts. First, in Theorem 1] [Section 3) we prove asymptotically tight bounds on the growth rate of M (nz) for any distribution with finite expectation. Then, in Theorem 2 presented establish the aforementioned condition by using the bounds of Theorem and an
in Section averaging argument over all values n.
Empirical Validation and Observations. We complement our theoretical findings with extensive numerical experiments. While our analysis centers on the true expected order statisties M2(n), our empirical simulations shed light on the behavior of their empirical estimates across repeated trials (2).). and support the theoretical results in several ways.
As anticipated, for some distributions, the ratio M, (n)/Mz(1) increases quickly function of Even with a large number of trials and high values of n, the ratio exhibits significant variability an expected consequence of the infinite variance of the distribution used. Interestingly, this heavy-tailed behavior appears to predominantly impact M, (n), while M2(n) and lower order statistics remain concentrated.
An interesting phenomenon emerges when we censor the most extreme values: after removing the top 1 % of trials with the largest maxima, the ratio M, (n)/M2(n) stabilizes and remains nearly constant across values of n. This same near-constant behavior of the ratio observed when using distributions with finite variance, suggesting that the instability of the ratio is largely driven by rare but extreme deviations in the maximum.
2 Reducing to Escalator Distributions
Given n samples X1, X2...., Xn drawn independently (i.i.d) from a distribution F, we let M, (n) for é E {I,...,,) n denote the expected value of the (-th largest sample.
Given a general distribution F, goal in this section is show that the asymptotic behavior of M. (n) is unchanged if we consider a distribution related to F, with convenient structural properties which we call escalator distribution. The family of escalator distributions only take values 1 1/k for integer k. An example is the following. For all natural numbers k fix the interval T = [k: 1, k)) in which the distribution (CDF) F takes value 1 1/k. This defines discrete random variable X on the natural numbers such that P(X = k] = F(k: + 1) - F(k) = /k=(k + 1)).
In order to formally define escalator probability distributions, let us consider the indicator function of a subset of real numbers defined as
1x {
if x ET otherwise
Definition 1. We say distribution F over non-negative reals is escalator distribution if for all x 2 0, (x) E {(1 - 1/k) k E N). For any distribution F' (not necessarily an escalator
'That is, lim sup,, Mf (n)/o(n) 0.
5 "A is the case for g(n) = n2(log nlog log 1.00)
6 As is the case for g(n) n/(log n log n).

---

distribution), we define the two associated escalator distributions F as follows: For k 2 1 define 2y in F F(x) 2 1/k), and
x (+)===
1 1 (x)) FT)x)
1
s0 Σ (1 k=1
(sL-1,aw)
We define the step sizes 0g 1k+1 FR 2 O. In this case, if X is drawn from F then E. [X] Ex 6 k. If drawn from F-, then E. [X] Σx 6
Note that F+ F (2) are CDFs since they are monotonically increasing and converge tends to infinity, It is clear that F+ F S F and therefore
M (m) S M, (m) - M, (n).
(1)
Therefore, instead of studying F, we can study the associated escalator distribution F+ in order to upper bound M (n), since (n) < M (n). We may simply study the asymptotic growth of F* so long as it has finite expectation. Next we establish that if F has finite expectation, then so has F+.
Proposition 1 (Proof in Appendix A.I]. Let F be any distribution with finite expectation, then its associated escalator distribution F has finite expectation!
3 Asymptotic Behavior of Mf(1)
In this section, we analyse the asymptotic behavior of the expectation of the f-th maximum of i.i.d. samples from distribution F on the non-negative real numbers. Note that this quantity equals:
{-1
M (n) / (1 - (1-P P ( S <x))dx
/
Fm (m) (1- (L-((2))) dz.
x
Our main result in this section is the following.
Theorem (Proof in Appendix A.5). For any distribution F, Foror any integer &. 2 1, we have that
n
(m)
(n) =
8k
Ōk Ret
where 0g is defined in Definition
We prove this theorem in four steps. First, consider the associated escalator distribution F+ and transform M. (n) into weighted-sum of the ōμs (Proposition 2p. Second, we derive asymptotically tight (up to constant) bounds (Lemma 3), for h S n. Third, in Lemma 4] we derive bounds for the case & > n. Finally, in the proof of the theorem, we combine all of the above and show that
M. (n) e (MF (n) θ -m=1
5R Σi=n 5/02).
Proposition 2 (Proof in Appendix A.2 Let Yv BINOMIAL 1/k), we have that
M (n) Σ PY M (n)
Σ
P P 2 1)
Intuitively, the binomials YN appear here for the following reason. In order for Xn- be in the interval Ig it is necessary that at least l variables are in the intervals Z, Ix+1 1---.... where I; are the intervals associated with the (see Detinition I). With Proposition 2 Zequipped, we are ready to prove the following lemma.
This is straight-forward extension of (16) who prove that if 1 < F then M (n) S Mf (n). As an example, consider the exponential distribution with parameter A. F(x) 1 - e e- A2 Then, F is defined by the intervals Ia- = (In(k)/A) X, In(k + 1)/Aj, and defines a discrete random variable Y such that E [Y] 1 E. In(1 + 1/b))k
5

---

Lemma 3 (Proof in Appendix A.3). Ler Y BINOMIAL Let e be a fixed constant. For 2el! + 1 and k S we have that,
1 2e é!
P 2
We now prove the following lemma, which bounds the partial sum of Theorem 1 for n. Lemma (Proof in Appendix A.4). Let YE ~ BINOMIAL 1/k). Let be a fixed constant. Then, for 2 e / 1/e) and >> n we have that,
P P 2
n1
11 E
1
k
1
4 Main Result
In this section we study the largest possible asymptotic behavior of M ( (n) using the results of the previous section. As know from (10), MM (n) is sublinear, but can grow as fast as any sublinear function ((8). In general for any l. it is clear that M,"" (n) is sublinear since M," (n) S M, (12) A natural conjecture is that this is still true that the second (or 2-th) maximum grows as fast any sublinear function.
Our first observation here says that the answer this question is more subtle. First, in Proposition 5 we show that for any sublinear function, there are distributions that Mt (n) surpasses it infinitely often. On the other hand, in our main result Theorem 2, we show that M," (n)) cannot be consistently above any sublinear function. More precisely, prove that in order to have finite expectation
distribution with Mf (n) = (g)(n)) is necessary and sufficient to have En. g(x))
n² o0.
Proposition (Proof in Appendix A.6). For any non-negative, non-decreasing function with sublinear growth, i.e. g(n) o(n), there exists an escalator distribution with finite expectation such that for infinitely many n
Mf (n) gg)
In other words, the last proposition establish that if g(n) = o(n), then there exists distribution F such that lim sup, Mf (n) >> 0. This result implies that, although Mf (n) has sublinear growth for any finite expectation F, is impossible to find a specific sublinear function g such that Mf (n: o(g(n)) for all distributions F' with finite expectation.
sup One might hope that our previous lim sup result could be strengthened to lim inf since for f 1, Correa and Romero g show that lim inf,, Mf (n))/(n) > 0, which translates to Mf (n) = ((g())).
However, we show in Theorem that one cannot hope to extend this result to 2 for any sublinear function g. In particular, [Theorem 2 implies that for any finite expectation distribution there infinitely many values of n for which Mf (n) < n log (for 2 2).
Theorem 2 (Proof in Appendix A.7 Fix an integer > 2. Let g(n) be a monotonically increasing non-negative functioo. Then, there exists distribution F with finite expectation such that M (n)
Ω (g(n) and only if n²
g(m)
3c.
The above theorem can also be stated as follows. Consider an increasing function g(n) such that
> 1
g(x) n
< oc, then there is a finite expectation distribution F, such that lim inf, M (m) > 0.
g(m)
Conversely, -m g(n) n oc, then for each distribution F, we have that lim inf, Mr (m)
(nn)
Therefore, the big picture the following. We can always find probability distributions to make M (n) match any sublinear function infinitely often. (for infinitely many n)). However, if one seeks to find a distribution for which Mt"" (n) is large for all n, then the threshold lies at n/L, where t, - (f) (n), where for all i N and n E R+
log(log (e-()))
for i 2 2 and log
log (1))(n) 22
log (gg() (n)
for i 2 2 and (i-) <
(2)
log(n)
for 1.

---

In particular,
Mf (n) = O log n log log
12
with 0 is achievable, whereas M (n)
Ing n. log log is not.
The construction of finite expectation distributions with large growth rate of M (n) intuitively depends the tail being heavy enough. If higher moments exist, order statistics grow much slowly. This idea has been established in the literature when deriving upper bounds for the expected maximum (100.(5).(8) Similarly, one implication from Theorem 2 can be extended the same way follows. Suppose E [X*] < co for > 1. Since power functions are convex and non-decreasing. Jensen's inequality imply
(Mf (n))²= (E 1= < X
x a- EE [Zn [Zn-etim] M (n))
where Z4 X non-negative i.i.d. random variables with distribution F. Thus. Theorem 2 states oo, then for l f2 2
that if g(n) satisfies Σn. g(m)
n²
Mf (n)
Mf (n) O. g(n)
lim inf
lim inf
(g())
In particular, Mff (n)
Togn is not achievable by any F with finite variance. We establish
this generalization in the following corollary.
Corollary 1. Fix p and an integer E. Let g(n) be monotonically increasing non-
negative function such that En a(n)² = 00. Then, any distribution F with E [XP] < oo satisfy liminf, (n))g(n) = O.
5
Experiments
We complement our theoretical results with simulation experiments that illustrate how the separation between M1 (n) and M2(n) manifests itself in practice. Our goal is twofold: (i) to empirically validate our results even for moderate values of n, and (ii) to explore whether this gap comes from
many observations where the maximum sample consistently larger than the second-highest sample, or from rare events where the separation is extremely large.
5.1 Experimental Setup
We focus on heavy-tailed distributions with finite expectation, considering two cases: one with infinite-variance tail behavior and another with finite-variance tail behavior.
We construct each distribution by defining its tuil-quantile function T(y) inf : F(x) >
1 - 1/2}. Both distributions were sampled efficiently via inverse transform sampling using PARETO(1) auxiliary variable. For each distribution, we generate 1,000,000 independent trials for values of n ranging from 10 to 10,000. In each trial, we computed the top order statistics X Naam:Xn-ae Xn-1:n: Xn-2:n: Xn-3:n and averaged across trials to estimate Me. We focus in particular the ratio MI/M as proxy for the separation between the top two samples.
All experiments were conducted on the Columbia Business School (CBS) Research Grid, a high- performance computing cluster running Linux environment (Debian 4.1)). We fixed the random seed to 42 using Python's 's default pseudo-random number generator to ensure reproducibility. The code is included in the supplementary material.
5.2 Separation between M, (n) and (2( under Heavy-Tailed Distributions
consider g(n) = n/ log(n) as the benchmark growth rate, since Theorem implies that no distribution with finite expectation F can achieve Mf (n) Q(n/ log(n)). We consider heavy- tailed distribution defined by the tail-quantile function
T
2/
log(y)1.01

---

- Mytol
- Mytel
Myin]/M_(n)
Mytnl
t M.inl
login)
15000
16
14
12500
10000
7500
5000
2
0
2000
4000
6000
BO00
10000
2000
4000
6000
8000
10000
Sample
Sample
Expected order statistics under infinite- variance distribution. report the average and standard erorr over 1,000,000 trials.
(b) Ratios between consecutive expected order statisties (point exti- mates).
Figure 2: Empirical behavior under T(y) - y/ log(y) 1001, [nn)) grows rapidly with large variance; (2(n) and lower order statistics grow more slowly and are tightly concentrated.
which has finite mean but infinite variance. We observe that the ratio MZ (n1) (M))))M2(m) increases rapidly with n. While (n) grows nearly linearly, M2(n) remains close to the benchmark growth rate n/ logn. Figure 2a shows the estimated expectations of (n) for - 2, 4. Notably, Mi is highly variable even across 106 trials, due its infinite variance. In contrast, M2 and lower order statistics are sharply concentrated. This is explained by the fact that the second moment X is infinite under this distribution. Indeed, if X; T(V)) with IID samples V; PARETO(1). )), then
T y²
E
X
dy
T Twy)
1
n-1
2
1
dy
1
71
100
T(y)²
dy
2n-1
y²
1
1+6 dy = 00.
(3)
2n-1
log(y)
This divergence explains the persistent noise in estimating M, (n). even with large trial counts. Figure 2b shows the ratios between consecutive order statistics. We observe a clear upward trend in M2 (n)/ MM))), in line with the theoretical expectation that the first and second maxima diverge under infinite variance. Ratios M2(n)/ MM(()) and Ma(n)/ MM)()) remain nearly constant.
5.3 Effects of Censoring Extremes
We repeat the comparison after removing the top % of trials with the largest maxima. This censoring stabilizes the results dramatically. As shown in Figure 3). the estimates become less noisy, and the ratio M, (n)/ M2(n) flattens across This illustrates that the growth in the ratio is largely driven by rare extreme values of M, (n).
5.4 Variane Comparisons
To test whether this behavior is specific to infinite-varianee distributions, we repeat the experiments with finite- variance distribution defined by
V
T(v)
V 1.01

---

- Mytol
-
Mytnl
Mytnl
4 M.inl
MalmiMsinn
leg(m)
10000
8
8000
6000
0
2000
4000
6000
BO00
10000
2000
4000
6000
8000
10000
Sample
(a) Expected order statistics after censoring.
Ratios after censoring.
Figure 3: Empirical behavior after removing top 1% extreme maxima. The ratio M1(n)/M2(0 becomes stable, suggesting that typical-case gaps are modest.
Matm) Malmhnnsim
MstriMatn)
Miln)
Mgin)
v'o
Mstri
+ M.tn)
vlogin)
100
2.5
2.0
1.0
0
2000
4000
6000
8000
10000
2000
4000
6000
8000
10000
Sample size
Sample size
(a) Expocted order statisties under finite-variance distribation.
(b) Ratios between conscutive expected order statistics.
Figure 4: Results under Tςy) = V log(y) 1.1
All order statistics are well-behaved and
(n) remains stable across n.
As expected, the results are markedly more stable. We can verify the finite second moment of the maximum:
T
(1 (1-1) n-1 000
T(y) y² dy
E
X
dy
y Log dy
y2 y
Hence, the estimates of M, (n) are far less noisy, and the ratio (n (2)) remains stable across all tested values of
6 Conclusion and Future Work
In this paper, we have presented asymptotically tight results (up to constants) for Mz(n) for any constant é. The regime where É is linear in n, comprising the median is well-understood here, have that Mn O(1) for any finite expectation distribution. Therefore, natural open question is what happens the regime where (1),), o(n)]. Further enticing open questions are understand the distribution of Xm.n/Xn-12x and to obtain bounds on higher moments of Xn-ét1sn- Finally, it assuming that higher
would be interesting to understand the distribution of the second-maximun moments of F are finite. Numerical experiments confirm our theoretical predictions: under heavy tails with infinite variance, the ratio Mf (n)/M3 (n) can grow with n but does so due to rare extremes. In the typical case- after censoring under finite variance- the ratio is stable and bounded.

---

Acknowledgments and Disclosure of Funding
The work was in part supported by the EPSRC Grant EP/W005573/1 well as the Center for Mathematical Modeling (grant ANID Chile FB210005).
References
[1] Aminc Allouah and Omar Besbes. Prior-independent optimal auctions. Management Science, 66(10); 4417-4432, 2020.
[2] Barry Amold, Narayanaswamy Balakrishnan, and Haikady Navada Nagaraja. A first course in order statistics. STAM, 2008
[3] Barry C Arold. p-norm bounds the expectation of the maximum of possibly dependent sample. Journal multivariate amalysis, 17(3):31-332, 1985.
[4] Barry C. Amold and Richard A. Groeneveld. Bounds on Expectations of Linear Systematic Statistics Based Dependent Samples. The Annals Staristics,, 7(1):220 223, 1979. doi: 10.1214/aos/| 176344567. URL httpps//://// org/10. 1214/aos/1176344567
Dimitris Bertsimas, Karthik Natarajan, and Chung-Piaw Teo. Tight bounds expected order statistics. Probability in Engineering and Informational Sciences, 20(4):667-686, 2006. doi: 10. 00110777580226694666666611114
[6] Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of machine learning research, 29Mr))499--52, 2002.
[7] Sylvain Chassang, Kei Kawai, Jun Nakahayashi, and Juan Ortner. Robust screens for noncompetitive bidding in procurement auctions. Econometrica, 90(1):315-346, 2022.
[8] José Correa and Matias Romero. On asymptotic behavior the expectation the maximum iid random variables. Operations Research Letters, 49(5):785-786, 2021.
[9] Herbert David and Haikady Nagaraja. Order statistics. John Wiley & Sons, 2004.
[10] Peter Downey. Distribution free bounds on the expectation the maximum with scheduling applications. Operations Research Letters, 93):189-201, 1990.
[11] Janos Galambos. The asymptotic theory of extreme order statistics. Technical report, 1978.
[12] Dan Hendrycks and Kevin Gimpel. A baseline for detecting misclassified and In International Conference on Learning Representations, 2017.
examples.
[13] Emilie Kaufmann, Nathaniel Korda, and Rémi Munos. On the complexity of best-arm identification in multi armed bandit models. In Conference Learning Theory, 2016.
[14] Daniel Levy, Yair Carmon, John C. Duchi, and Aaron Sidford. Large-scale methods for distributionally robust optimization. 2020. [ttt::::: http:/aawawa.rrra////a/////// 2080/
[15] Weitang Liu, Xiaoyun Wang, John Owens, and Yixuan Zhong. Energy-base based distrritiitiiin detection. In Advances in Neural Information Processing Systems, 2020.
[16] Chunsheng Ma. A note stochastic ordering of order statistics. Journal of Applied Probubility, 34(3): 785-789, 1997.
[17] Isaac Meilijson and Arthur Nádas. Convex majorization with application the length of critical paths. Journal of Applied Probability, 166)7671-677, 1979. ISSN 00219002. http:///:w/ww. org/
stable/ stable/3213097
[18] Jake A Soloff, Rina Foygel Barber, and Rehecca Willett. Bagging provides assumption-free stability. Journal of Machine Learning Research, 25(131):1 1-11111)1335..1111 2024.
[19] Yan Wang, Huaiqing Wu, Dan Nettleton. Stability random forests and coverage of random-forest prediction intervals. Advances in Neural Information Processing Systems, 36:31558-3156,, 2023.
10

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The claims match our results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
The paper discusses the assumptions we make and hence the limitations as well numerous open problems that mark the limitations of our results.
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]

---

Justification:
All proofs can be found in Appendix A
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: Yes]
The experiments with this paper are numerical simulations. No datasets are being used. We provide all relevant details.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
12

---

Answer:
[Yes]
Justification:
The code is included in the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
httppp/lllccpgideeeeeeeeeeebeaia /
/ntps.cccppulic//guu
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
The experiments with this paper are numerical simulations. No datasets are being used. We provide all relevant details.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The results in Figures 2a 1,000,000 random trials.
3a and 4a report the mean and standard error over
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by eπror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (c.g., Normally distributed errors).
13

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative emror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Ys]]
Justification: All experiments were conducted on the Columbia Business School (CBS) Research Grid, high-performance computing cluster rumning a Linux environment (Debian 4.19). The code and notebooks are included in the supplementary material. We fixed the random seed 42 using Python's 's default pseudo-random number generator to ensure reproducibility.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't iidn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics tattts://neurigee http///urr....c......../ttttttta
Answer: [Yes]
Justification: Our research conform, every respect, with the NeurIPS Code of Ethics https://eeuiis.ccpppppii/hhhhehe
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification:
We unaware of any direct path that leads negative societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
14

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
15

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
16

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM for what should or should not be described.
(https: /attaa///aarrpppe.cc///offeerees
17

---

A Technical Appendix
A.1 Proof of Proposition
Proof. Since F(x) S x-1 for all (R+1), have that
J (F(x) F+ (x)) dr Σ
2
#E+1
[((x)
(1-0)-(11))) dx
k=1
22
1
(Ix+1 - xxk)
k: k
1
(IR++1 xx)
kik + 1)
1
(xR+1 IKk)
(k +
1++1
1
dx
(k +++1) 1)
k= 22
(1 F(x)) dr
[X1].
Thus,
E [xxt] - [/00//100 (-FF(x)) de = 1 000
10 00
(1 F(x)) dot
(F)) do 2F 2E [xi] < oo,
00
and F+ has finite expectation.
A.2 Proof of Proposition 2
Proof. Recall that if F+ is an escalator distribution and ..... non-negative support, then
X X, are drawn from F+ with
00
1 ))) dk.
MP (n) 10000111000 (1-F+"
(x) dx Σ
Similarly, using the fact that the distribution of 1n- is F+ mF++=11 F+), get that
M2 # (n)
1 - F+a F+((2) nF nF- 1FF--1((>)(
(z) - -F+())) (x)(1-F+()))
dr
1 k
1 n-1
1 - 1
(1
1 1
k
k
In general, we get, that X,, X4 is distributed Ei=1 (+) nー (x) - (1 (-F+()))+ Thus.
18

---

M F+ (n)
(x) (1 1- (x)))²
dx
n-i
(1
h+ 6₁
PP [Y =i] 6x
==
P [Y& 2 8 dz.
concluding the proof for F+. The result for F- is anologous since its definition only involves shifting 5%'s 's indices by one.
A.3 Proof of Lemma 3
Proof. The upper bound holds trivially, since PP [Y& 2 2 S 1. For the lower bound, we have, by
Lemma 6 for k 2 2
8-1
P < 8 =
Σ
12
(1
1/k)a
1
8
==
6-1 Σ
(1 1/b)a
(k- 1)i
(n 1)
Note that for = 1, we have P [Yi < =0. 0. Thus, for all k 2 1, we have
n1
Pl < $
i nn 11
Then, since l is much smaller than n,
f-1 Σ(
n
1=0
Σ 11
1
n1
1
<
11
1
<e-
13 +
Thus, Pl 4 1- P. <
1
6
+
n-
a-1
>
2ef!:
for n
>
2ell +1.
19

---

A.4 Proof of Lemma 4
Proof. Let Zg be the Poisson distribution with mean n/k. Using that k 2 n + 1, we get,
P PLa = =
n1
1
(1 1/k))=
1
kz
Tt. 1
i! ki (1 - 1 1/k)) (
(n/k)²
i! e -m/0
122 = 1) 1
I P 45 = i] c²/
Thus, using that Σist
1 A S e, we get,
(n/k)'
Σ S etnf/ (m)
P|
m/k
S se nn/k, (nn/k²
x= i!
For the lower bound, we use (1 - 1/1))* 2 (1 - 1/kk)/e e. We first bound,
(1 - 11-//))- 2 (1 11/b) k(n-
(4)
(n-2)/k
1 1/kb)
e/k
n1
-1
1
n/k
k2a
e/k
1
1
en/k
n1
Thus, since 22 - -
v1-1/e] 1/e). and using that P [Z f
(n/k)/--n/ get,
P 1 =
12
R (1 1/k)me
(n L + 1)e-
Ke (1 1/k)==
E
(n -e++ 1)c
P [Z+ = 9
(1-1/k) nL m/
n2
1
(1
P(Z = 1
e/kk
n
n
> PlA = {
(1-
2
1
1
e/k
2 P [Z = 4 (1-
(2 2
2 1Z = 1 (1 11-1/7 1/e).
Hence, since e n/kk 2 1/e we get,
11 n e
P P 2 = - Z = (1 1/0)
e
l!
k
Establishing the claimed bounds.
20

---

A.5 Proof of Theorem Proof.
From Lemma
we get,
8% S
Σ
P
Y 2 0 -
Ōk-
2e E! k=1
1=1
k=1
From Lemma we get,
11 8 (6) 5x
E k=n+1
Se
Σ
8
(m)), ōk.
e² E
k=n+1
k=n+1
Thus, by Proposition 2
for the escalator F+ using that Ek=z 8x + >k==+1
8x
Ek=n gr 6R. have
カ-
00
n'
Mf (n) =
Σ
6k
6%
(5)
ke
k=1
k=
Similarly, we obtain
n111
20
n
Mf
(n) =
6%
+
86
(6)
(k + 1)
k=n
We claim that if and ( (1), then
+ 1)c
2
K
From Eq. (7) together with Eq. (5) and Eq. (6) the claim in the statement of the theorem follows immedhately, since for some large enough,
ne
n
8x
6k
S Mf
(n) S Mf (n) S M (n) Sc
Σ 8
6%
ke
ke
where we used that F+ SFSF yielding M (n) S Mf(m) (m) S Mf (n).
It remains to prove Eq. (7) Clearly (K+TT) < 1 E.. For the lower bound, we assume without loss of
generality that 2 2 since, otherwise, I+I 2 2K
We have (K+FTy² 2 2h since k²t (1 + +1) 2 1/2. Thus, Eq. (7) holds completing the
(1+
proof.
A.6 Proof of Proposition
Proof. For any E N. define n(i) min 2 1 g S 2-1). Note that n(i) is well-defined, ie. is positive integer, since g(n) = o(n). Moreover, since g(-) is non-decreasing, nuii - oo as
i + co. Let (n(i) i E NJ and 11 Consider an escalator distribution defined by
((k)
if in otherwise
8u
0
Therefore, such escalator distribution has finite expectation. Indeed,
g(k)
1
00
1
00.
ck
c
c
KEI.
On the other hand, from Proposition 2 we have Mf > PlY, 2 f6 Moreover, by Lemma 3 for large enough n, PlY, 2 2 c. Thus, since n(i) as i - xc, for all large enough i.
Mf (n(i)) 2 cdn(s) = g(n(i))
21

---

A.7 Proof of Theorem 2
Proof. We start by proving that if M (n) = (gg(n)) for some distribution F with finite expectation. then necessarily Σn, na Therefore, assume that for all n we have,
gfu] < co. Since Mf (n) - M2 ( (n), it is enough to show the claim for & = 2.
M (n) 2 g(n).
(8)
By Theorem there exists a constant >>> 0 such that
n
M (n) c
5% + e
6% =: f(n).
12
k=1
kmn
From Eq. (8) it follows that [(n) 2 Má (n) g()). Thus,
n 6% [(n) 2 g(n)
min
n k22
A=
Therefore, dividing by n again and summing over all values of n it must hold that
1 n
g(n)
Oz
12
n
Switching indices yields
g(n) n
I e
min
n22
122
72
n=
20
1
c
min
n13
122
8n
n=
8
min
71
n
k2
n
n
n1
n
R2
k=n+1
0
S 3e
n
n=1
Here we used that n Ek=n41 E
n (1, < 2, where Li is the polygamma function. Recall from Proposition that if F has finite expectation, then Σn en < co. Therefore, Σ 12
gim) < 00.
We now prove the other direction: assuming Σn, g(n) co, construct escalator distribution F 7²
with finite expectation such that Mf (n) 2 g(n). Recall that for any distribution F, by Theorem 1
there exists universal constant e such that M,"" (n) 2 < < dn + Exen Ke
of Sx. We define
(n))= = (n) and construct F by defining
6 ke 1
1
1C-T/((k)
(k + 1) hkk
6-1
Indeed, if X is drawn by F, using that
(1-
k+I
1
2 1 - 8-1
k+1
we get,
E
k
A=
1
1
h(k)
k k+
hik 1)
1
e-1 (k+ 1)h(k 11)
T((k)
1ikk
+ 1)
km
22

---

The first term evaluates to 11) since it is telescopic sum and 1/h(k)) - - oc, by the assumption that Σ g(n)/n² co. Similarly, the second sum finite by hypothesis. Therefore E. [X] < xo, so that the constructed distribution F has finite expectation.
On the other hand, by Theorem we get
(n) 2
6%
+
ke
k=n
12
he (((k)
(k 1 1ik + 1)
km
g(1).
n (())
h(n)
As before, the telescopic sum results only in the first term, because =(k)) g(k)/k /k= - as -> co. The above implies the existence of a finite expectation distribution succh that M (n) 22 (n))).
A.8 Auxiliary Lemma
The following technical lemma used to prove Lemma 3
Lemma 6. For any positive integer 8 S 1, the function
É-1
f(x) = (1 - 1/x))
11
8
(x
1)
0=
for S n is non-decreasing.
Proof. The derivative w.r.t. x of this function f(x) is
(1-) 1 Σ i
n
f()) = n 1 x
1
1
(9)
(x - 1)²
(a
1)
Equation 3 can be rewritten as
f'(x) (
11
1)² x :)
n
(x
Note that all terms in the sum are non-negative for if < n/(l sum and consider the case that 2 n/(e 1). Since (0) 4/4
1).
In the remainder we rewrite the we can rewrite the second sum
(-=)
in equation (9p as
n
n 1)
1)² 1-1 (x - 1)
(x
1)3
i
(x
1)
1=0
and then the derivative can be factorized as follows
n ( ( 11 z(r - 1)
(1- n-1
6-2
12
1 -
n 1
1)¹
i
i
where all the terms are non-negative if:
(n 1)
2[ - 2)
i
ml
n
Which holds if and only if 1 > which in turn is equivalent to x > 2. The latter is true since we assume x 2 n/(ef - 1). Thus, the derivative is non-negative and the claim follows.
23


Reviews:
[{"review_id": "7smkg6gdF2", "reviewer": "Reviewer_W6kr", "summary": "This paper studies the worst-case asymptotics of extreme order statistics, e.g. $M_{\\ell}(n)$  the $\\ell$-th greatest value among $n$ i.i.d. positive random variables, for a fixed $\\ell$ as $n$ goes to infinity. For $M_1(n)$, is has been previously shown that $M_1(n)=o(n)$, and $\\liminf M_1(n)/g(n)>0$ for any $g(n)$ sublinear in $n$ tightly characterizing the worst-case asymptotics. Contrasting with this previous result, this papers shows that while $\\limsup M_{\\ell}(n)/g(n) >0$ remains true for all sublinear functions $g(n)$, it does not necessarily hold anymore for $\\liminf$. In particular, it is shown that $M_{\\ell}$ consistently dominates $g(n)$ if and only if $\\sum_n g(n)/n^2<\\infty$, providing a complete picture on the case $\\ell>1$. Additional results are provided when additional moments are finite.", "questions": "- By the fact that the threshold $g(n)$ does not depend on $\\ell$, does this suggest that all of the $M_{\\ell}$ for $\\ell>1$ have all the exact same worst-case asymptotic behavior? Why is that the case?\n- If we have that $\\sum_n g(n)/n^{\\ell} <\\infty$, can we say anything more about $M_{\\ell}$? \n- What can we say about the asymptotics of order statistics gaps $M_{\\ell}-M_{\\ell+k}$?\n- line 679, why can we upper bound $1/(k-1)^i$ by $1/(n-1)^i$ given that $k\\leq n$? I must have missed something obvious.\n\nThere are some small typos to correct:\n- line 55 Conditions for to have\n- line 221 There exists infinite ... sublinear functions. (confusing sentence)", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths \n\n- It provides a comprehensive theoretical analysis of the extreme order statistics, and highlights a very non-intuitive subtle difference in asymptotic behavior between $M_1$ and $M_{\\ell}$ for $\\ell>1$. \n- The paper is clearly written and the related works are precisely presented.\n\n## Weaknesses \n\n- Given that this paper is based on a quite technical aspect of limit behavior of order statistics, it would be better to be as unambiguous as possible on the meaning of the $\\Omega(g(n))$ and other Landau notations. In some fields, these notations sometimes implicitly assume that the ratio $f(n)/g(n)$ converges, which is clearly not the case here as $\\limsup$ and $\\liminf$ are distinct. \n- The paper is lacking a bit in terms of intuition in why there is such a difference between $M_1$ and $M_2$, and why there is a difference in terms of $\\limsup$ and $\\liminf$. Why does this phenomena not appear at $\\ell=4$ for instance?\n- The paper mentions potential applications, and while I really appreciate the result, I still struggle to see how this would concretely impact existing bounds or results in other topics. It would be great to highlight on a small example possible consequences, for instance to detail how the the main result concretely affects BAI (being one of the example suggested).\n- This paper would benefit from additional visual aids, such as plotting the escalator transformations and the worst case distributions. It might be a good use of the additional space to add these plots.", "was_revised": true, "final_justification": "This is a technically solid paper, with novel contributions, and while I was not convinced by the broader applications mentioned, this problem is still well motivated by itself.", "rebuttal": "We thank Reviewer W6kr for the valuable feedback and suggestions. Below, we respond to each specific question.\n\n**1. Threshold $g(n)$ and dependence on $\\ell$.**\n\nWe think of $g(n)$ as an exogenous benchmark, and then analyze if $M_\\ell^F(n)$ can achieve such asymptotic growth rate under some distribution $F$, and whether this answer depends on $\\ell$. Indeed, the answer is the same for any constant (w.r.t. $n$) $\\ell \\ge 2$ (Theorem 2). The main technical reasons for this result can be summarized as follows. If we fix $g(n)$ satisfying $\\sum_n g(n)/n^2<\\infty$, then for any constant (w.r.t $n$) $\\ell \\ge 1$, we can construct a tailored distribution $F$ to achieve $M_\\ell(n) = \\Omega(g(n))$, and of course $M_1(n) \\ge M_2(n) \\ge \\ldots \\ge M_\\ell(n)$. For the other direction, we show that if $M_\\ell(n) = \\Omega(g(n))$, then $\\sum_n g(n)/n^2 \\le A (1+\\sum_{k>n}\\frac{n^{\\ell-1}}{k^\\ell})$, where $A$ is close to the distribution mean (finite). If $\\ell=1$, this upper bound is infinite (uninformative), but for any $\\ell \\ge 2$, the infinite sum is bounded by a constant.\n\n**2. Condition $\\sum_n g(n)/n^\\ell < \\infty$.**\n\nAside from the special case $\\ell=2$, this condition is not very informative: the sum diverges for $\\ell=1$, and converges for $\\ell\\ge3$. The case $\\ell=2$ is the only one where more nuanced behavior arises.\n\n**3. Asymptotics of order statistic gaps $M_\\ell - M_{\\ell+k}$.**\n\nFor $\\ell = 1$, our results imply that the gap can be very large, growing almost linearly in $n$ (even if $k=1$). For $\\ell\\ge1$, we performed additional simulations and find that the gap is significantly smaller than the $\\ell=1$ case.\n\n**4. Line 679: upper bound justification.**\n\nThe bound applies to the entire sum, which Lemma 6 (Appendix A.8) shows to be non‑decreasing in $k$.\n\n**5. Typos.**\n\nThank you for pointing them out. All typos have been corrected."}, {"review_id": "lAJ21y5VvX", "reviewer": "Reviewer_91W4", "summary": "The paper answers a basic question in the asymptotic behaviour of the expectation of the second, and more generally $\\ell$’th maximum of i.i.d. random variables.\n\nWhile the case of the max ($\\ell=1$), it is known that the growth rate can be up to $o(n)$ - in the sense that there is a linear upper bound known, but there exists a finite expectation  distribution $F$ such that $M_{1}(n)=\\Omega(g(n))$ - the growth rate for $\\ell>1$ is tightly characterised as both $O(\\frac{n}{\\log(n)\\log\\log(n)})$ and $\\Omega(\\frac{n}{\\log(n)(\\log\\log(n))^{1.01}})$. \n\nThe authors also introduce a reduction to what is referred to as an escalator distribution; a convenient measure discretisation of a a cumulative distribution $F$, the order statistics of which both upper and lower bound the corresponding order statistics of F. \n\nTheory is supplemented with extensive experiments  and characterising behaviour of empirical vs. worst-case separations.", "questions": "Questions:\n* The escalator distribution reduction is elegant. Is there a possibility of extending this technique to dependent sample scenarios, or is independence fundamentally required for the escalator arguments to hold?\n* Given the broad applicability, could you clarify practical guidelines for using your results in robust risk or OOD detection pipelines? Specifically, how might practitioners identify whether their system is in a “regime” where your bounds meaningfully constrain the top $\\ell$ scaling - is it as simple as characterising the maximal degree of finite moments?", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n* The paper offers a surprising perspective on the behaviour of the $\\ell$’th order statistic for $\\ell > 1 $ with extremely general and tight results (up to a minuscule $\\log\\log(n)^{0.01}$ factor), applying to all distributions with finite expectation.\n* The techniques, notably the escalator distribution reduction, are elegant and provide a clean path to bounding asymptotics of order statistics rigorously.\n* The applicability of the results is broad, including value-at-risk estimation, option pricing, auction theory, load balancing in compute, and - as noted in Section 1.1 - several high-impact areas in machine learning theory (e.g., adversarial risk, best-arm bandits, OOD detection).\n* The paper zeroes in on concrete cases (finite variance, higher moments), illustrating how growth rates degrade systematically under additional distributional constraints.\n* Results fill a natural and under-explored gap in the literature between known results for the maximum and the poorly understood behaviour of lower extreme order statistics.\n\nWeaknesses:\n- Presentation is somewhat notation-heavy, and highly technical, which may limit accessibility for non-theoretical or applied ML audiences. Considering the theoretical interest of results, this is a rather minor weakness.\n* The paper could do more to explicitly connect theoretical findings to practical thresholds, and provide concrete examples like those elaborated in Section 1.1.", "was_revised": true, "final_justification": "While it may have been the case, given the other reviewers' identification of typos and points of clarification in the proof, that my assessment was on the generous side initially, I find that against criteria of technical novelty, clarity of exposition (modulo typos), strength of results and breadth of possible applicability, this work still has quite an advantage. The authors' responses to my questions helped elaborate on the breadth of applicability as well as possible extensions of the methods developed. In addition, the extra clarification due to the diligence of reviewers 6S2N and L83L has been instrumental in clarifying its correctness. I recommend acceptance.", "rebuttal": "We thank Reviewer 91W4 for the thoughtful and supportive review. Below, we respond to the questions raised and provide clarifications where requested.\n\n**1. Escalator distribution and independence assumption.**\n\nThis is an excellent question. Our current argument relies critically on independence (e.g. Proposition 2) and does not generalize directly to dependent sample scenarios. Extending the escalator reduction to dependent settings would require fundamentally new ideas and is an interesting avenue for future research.\n\n**2. Practical guidelines for robust risk and OOD detection.**\n\nAt a high level, our results highlight that practitioners should be especially cautious about the behavior of the maximum vs other aggregation methods. In OOD detection, for example, it is common practice to detect outliers through thresholds on the maximum of confidence scores. In the heavy‑tailed regimes we study, the maximum sample can be orders of magnitude larger than the second maximum, a phenomenon our bounds characterize and which, importantly, can occur even when all samples are drawn from the same distribution (with finite mean). Our results also relate to the use of top-$\\ell$ aggregate loss in robust learning (see e.g. Fan et al., NeurIPS 2017). Indeed, under heavy-tailed distributions, the largest individual loss might dominate the average top-$\\ell$ aggregate loss when the number of training examples is large, potentially undermining its intended robustness.\n\nReferences:\n\nY. Fan, S. Lyu, Y. Ying, and B. Hu. Learning with average top-k loss. In Advances in Neural Information Processing Systems 30, pages 497–505, 2017."}, {"review_id": "6aE1KU9t2E", "reviewer": "Reviewer_L83L", "summary": "The authors consider n iid random variables drawn from a distribution F and are concerned with the problem of the asymptotic (largest possible) grow of extreme order statistics (in the following, I denote with $M_1$ with the max, and $M_n$ with the minimum).\nFor the maximum it is well-known that $M_1 \\in o(n)$ and for any sub-linear function $g(n)$ there exists a distribution $F$ such that $M_1(n) \\ge g(n)$.\nThe authors thus focus on the case $l > 1$. Specifically, they show that for all $l$, the largest possible grow is $O(n/(log(n) log(logn))) and there exists a distribution such that the growth is $n/(log(n) log(logn)))^(1.01)$.\nThe authors also run experiments which shows how the although the multiplicative gap between the maximum and the second maximum grows quickly with n, the ratio remains approximately constant in 99% of trials.", "questions": "Can you comment more on the experiments of Figure 3 and Corollary 1? It seems that the growth of M_2 is approximately $(n/log(n))^{1/2}$ (which contradicts the theory). Is this because the simulated values of n are too small?", "limitations": "Theoretical work. I do not foresee a direct path to potential negative societal aspects.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "# Strengths \n- This paper fills a well-motivated theoretical problem (see the applications subsection in Section 1)\n- The resulting characterization of the extreme order statistics is tight and interesting\n- The main text is overall well-written and clear\n\n# Weaknesses\n- Not much. Apart from the question below, and some (probably) **errors** that I have found in a proof (which I believe can be fixed without impacting the results). Below, I provide some detailed comments on the proofs together with the details on those errors. **Please, fix them (or correct me) during the rebuttal. For the moment, my score is Borderline Accept, but it is a placeholder. (I will increase it / decrease it based on the output of the rebuttal).**\n\n# Clarity of the appendix\nOverall, given the few pages in the appendix, I suggest the authors to provide more explicit steps while deriving their results. While proof-reading the results, I needed to spend some time verifying some (actually many) algebraic steps. Even a small tag near an inequality to justify a step would help with the workload on the review process a lot. I would also encourage the authors to provide more intuition on how the results were derived (i.e., more details on the main intuition behind the proofs). \n\n# Comments on the proofs\n### On Lemma 3 \n- Not really clear to me the comment on line 680\n  \n### On Lemma 4\n- In the proof of the upper bound, it seems that it is missing an $e^{n/k}$. Indeed, you are only reporting the upper bound on the Poisson. So maybe the result should involve an $e^2$? \n- For the LB, it is not clear how you use \"for $i$ small enough relative to $n$\" (line 688). It seems to me that it might be in the last step to assume that everything is positive, so that you can further proceed by lower bounding the binomial. Also, that last step is not clear to me. Please justify.\n- Related to the above. Given the statement of the Lemma, it is not clear that $n$ should be large enough wrt $l$.  \n- It might be nice to comment a bit in the paper on why a non-trivial UB is needed in Lemma 4, while a trivial UB can be used in Lemma 3\n\n### On Theorem 5\n- In the proof of Theorem 5, it seems that the authors are applying Proposition 2 for $F^{-}$. The result, however, is stated and proved only for $F^+$.  Although the upper bound holds, it is not clear how the authors are proceeding for the LB. (p.s., I can see that $F^+$ and $F^-$ are naturally close to each other in shape, and so that similar arguments could hold, in this sense I believe that the result is probably correct, but can you provide a formal argument for this?)\n- In Eq. 7, the upper bound does not seem to be needed in the rest of the proof. Right?\n\n### On Lemma 6 \n- Is there an extra n/x in the equation below line 740?\n- The equality after the \"Since...\" does not hold (line 742). There is an $i$ missing at the numerator so that we have n chooses i * i/n = (n - 1) chooses (i-1).\n- I feel that this should not be a problem for the statement, but can you please provide a corrected proof of the statement? \n\n# Other Comments\n- Typos: below line 156 \"escalatorprobability\"\n- Line 210, reference missing\n- Lines 708, 709 \"escalatordistribution\"\n- Suggestion: In the introduction, stress slightly more that $l$ fixed implies that we have no guarantees, e.g., for the min, as $l$ needs to be constant and hence cannot grow with $n$\n- Suggestion: A table somewhere would probably help the reader to maintain a clear big picture, i.e., the existing results + the new results with reference to the various theorems/proposition and their implications\n- Sentence at lines 220-221 not clear to me\n- Appendix A.9 is never mentioned in the main text\n- Proposition 5 states that for any sublinear $g(n)$, there exists a distribution $F$ such that $M^F_l(n) \\ge g(n)$ for infinitely many $n$'s. Could you comment more on why this implies the comment on lines 206-208? i.e., the fact that for a fixed $F$ one cannot find a specific sublinear function such that $M^F_l(n) \\in o(n)$ (e.g., maybe specifying with words that $g$ cannot depend on $F$ would help the reader)\n- Also, for the sake of clarity, it might be useful for the reader to write somewhere the implications of liminf and limsup and how they relate to the asymptotic notation", "was_revised": true, "final_justification": "The authors addressed my concerns on some (minor) aspects of the technical proofs.", "rebuttal": "We thank Reviewer L83L for their careful and constructive review. We greatly appreciate the time and effort spent in closely reading our technical proofs and providing concrete suggestions for clarity and completeness. Below, we respond to each technical point in turn. \n\n**1. Comments on Lemma 3 (line 680).**\n\nThe comment refers to the fact that the inequality derived so far uses $k\\ge 2$, but it is also true for $k=1$.\n\n**2. Comments on Lemma 4 (upper bound).**\n\nThanks for the correct observation. Indeed, there is an extra $e^{n/k}$ term missing, which should cancel out with the $e^{-n/k}$ from the Poisson distribution, leading to the same upper bound (no extra $e$ term). We apologize for the error, and sincerely thank you for pointing this out.\n\n**3. Lemma 4 (lower bound, line 688).**\n\nApologies for the confusion. First, note that we substitute $ i=\\ell $ in the last step of the proof. Secondly, it is true that we use that $\\ell$ is constant (independent of $n,k$), and $n$ is large enough with respect to $\\ell$, e.g. $n = \\Omega(\\ell^2)$. We will add this to the statement of the Lemma as per your suggestion. Indeed, if $n \\ge c\\ell^2$, then $(1-i^2/n)(1-1/n) \\ge (1-1/c)(1-1/(c\\ell^2)) \\ge (1-1/c)^2$. Note that the term $e^{i/k}$ is at least 1.  Substituting $c=1/(1-\\sqrt{1-1/e})$ yields the desired lower bound. \n\n**4. Comment on why a non‑trivial UB is needed in Lemma 4 vs Lemma 3.**\n\nThanks for the suggestion. The bounds on Lemmas 3 and 4 are related to Theorem 1. Given Proposition 2, for $k<n$ (as in Lemma 3), the Theorem needs only constant bounds on $P(Y_k \\ge \\ell)$. For $k \\ge n$, the Theorem needs tighter bounds, depending on $(n/k)^\\ell$, to control the infinite sum.\n\n**5. Theorem 1 (Proposition 2 for $F^-$).**\n\nThanks again for the suggestion. The result for $F^{-}$ is indeed analogous, and we will add this to the revised version. The main observation is that the definition of $F^{-}$ is the same as in $F^{+}$ but with $\\delta_k$’s shifted in their index by one. As a consequence, by shifting indices, the analogous result of Proposition 2 applied to $F^{-}$ yields $M_\\ell^{F^{-}} = \\sum_{k=1}^{\\infty} P(Y_{k+1} \\ge \\ell) \\delta_k$. Applying Lemmas 3 and 4 yields Equation (6) (line 696).\n\n**6. Theorem 1 (Unused upper bound in Eq. (7)).**\n\nCorrect. We will avoid this additional fact in the revised version.\n\n**7. Lemma 6 (equation below line 740).**\n\nThe equation is correct. After factorizing $(1-1/x)^{n-1}1/x$, the first sum in Equation (9) (with $ i = 0,\\ldots,\\ell-1 $) is multiplied by $n/x$. In the next equation, we separate the 0-th term, which is $n/x \\times 1$, and then factorize the remaining sum (with $ i = 1,\\ldots,\\ell-1 $) with the second sum in Equation (9), yielding a factor $ n/x - i $.\n\n**8. Lemma 6 (binomial coefficient equality in line 742).**\n\nApologies for the typo. In fact, the LHS of the equality below that has also the same typo, since the $i$ in the numerator inside the sum should be a 1, following the correct equality. Having this corrected, the RHS follows from an index shift (and is indeed true). The remainder of the proof holds as is. Thanks for the observation.\n\n**9. Typos and missing references in lines 156, 210, 708, 709.**\n\nThank you for pointing them out. All typos have been corrected in the revised version.\n\n**10. Suggestions for the introduction.**\n\nVery much appreciated suggestions. We will consider them for the revised version.\n\n**11. Sentence at lines 220-221.**\n\nThank you for the feedback, and apologies for the confusion. We will clarify in the revised version as follows. We can always find probability distributions to make $M_\\ell^F(n)$ match any sublinear function infinitely often (for infinitely many $n$). However, if one seeks to find a distribution for which $M_\\ell^F(n)$ is large for all $n$, then the threshold lies at [...].\n\n**12. Appendix A.9 is never mentioned in the main text.**\n\nThanks for the observation. We will correct this in the revised version.\n\n**13. Proposition 5 (lines 206-208).**\n\nThank you for the suggestion. The (now corrected) comment should specify that one cannot find a specific sublinear function $g$ such that: $M_\\ell^F(n) \\in o(g(n))$ **for all distributions $F$ with finite expectation**. This follows from Proposition 5, since whenever we fix $g$,  then we can find a distribution $F$ with finite expectation for which the statement $M_\\ell^F(n) \\in o(g(n))$ is false.\n\n**14. Relation between $\\liminf$, $\\limsup$ and asymptotic notation.**\n\nThanks for the observation. We will correct this in the revised version.\n\n**15. Comment on Figure 4 and Corollary 1.**\n\nCorollary 1 states that under finite variance, $M_2$ cannot achieve $\\Omega((n/log(n))^{1/2})$. However, this result does not rule out $\\Omega(g(n))$ for $g(n)=(n/log(n)^{1+\\epsilon})^{1/2}$ with arbitrarily small \\epsilon>0. Indeed, the infinite sum $\\sum_n g(n)^2/n^2$ can be shown to converge via Cauchy condensation test. If this is the case, the gap can be imperceptible in Figure 4."}, {"review_id": "8IQRkmw8tx", "reviewer": "Reviewer_WsQo", "summary": "This paper studies the behavior of order statistics, and specifically, the expectation of order statistics beyond the maximum. Previous work shows that for all constant distributions the expected maximum of n samples is $o(n)$, and this is tight. This paper studies the growth rate for the \\ell-th order statistic. The picture is rather subtle: there exist infinitely many distributions and infinitely many n such that the \\ell-th order statistic is an arbitrary sublinear function. However, there are limits to what can be done for a fixed distribution and all n. Specifically, $\\Omega(n/(log(n) loglog(n) )$ is not possible for all n, but $\\Omega(n/(log(n) loglog^{1+eps}(n) )$ is, for all $\\eps > 0$.", "questions": "N/A", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "This is a nice, well-written paper that studies a fundamental problem in probability. The paper completely answers the question it sets out to solve: get bounds on the growth rate of the expected value of the \\ell-th order statistic. The only weakness is that the scope might be a bit narrow. I.e., this problem is of interest to a small sub-community of NeurIPS, e.g., statisticians, or researchers in auction theory (the expected k-th order statistic is the revenue of a k-position auction). Still, I think that asking that a NeurIPS paper is of interest to everyone who attends NeurIPS is impossible, so I am in support of accepting this work.\n\n\n======\n\nHere are some typos (not sure where else I should point them out):\nTypo in line 54: “ℓ-the” should be “ℓ-th”\nTypo in line 55: “Our necessary condition for to have”\nTypo in line 156: “escalatorprobability”", "was_revised": true, "final_justification": "I am still in support of accepting this paper after looking at the other reviews (there was not much discussion, since all reviewers are overall supportive).", "rebuttal": "We appreciate Reviewer WsQo’s positive assessment. We will emphasize the broader applicability of our results and fix the typos noted (lines 54, 55, and 156) in the revised version."}, {"review_id": "Dssmu0uOxA", "reviewer": "Reviewer_6S2N", "summary": "This paper studies the behavior of the expected $\\ell$-th largest order statistics from $n$ i.i.d. samples (i.e., $(n-\\ell+1)$-th order statistic),  focusing on the case $\\ell \\ge 2$.\nThe authors show that, for all fixed $\\ell \\ge 2$, the growth rate of this expected value should be $O(\\frac{n}{\\log(n)\\log\\log(n)})$.\nFurthermore, they establish a characterization: for a distribution with finite mean, the condition $M_\\ell(n) = \\Omega(g(n))$ holds if and only if the monotonically increasing sublinear function $g(n)$ satisfies $g(n)$ satisfies$\\sum_n g(n)/n^2 < \\infty$, where $M_\\ell(n)$ denotes the expected $\\ell$-th largest order statistics.", "questions": "1. If there are any misunderstandings in my assessment of the Strengths and Weaknesses, I would greatly appreciate it if you could point them out. It would be helpful to receive further explanation or clarification where appropriate.\n2. Could you elaborate on the distinctions among the three regimes of interest:\n(i) the central/quantile case (e.g., the median or fixed-rank quantiles),\n(ii) the extreme case (as in this paper, dealing with the largest or near-largest order statistics), and\n(iii) the intermediate case?\nFor example, the different motivations for studying each regime and how results from each are applied or interpreted in practice.\n\n3. I would also appreciate further insight into the contribution of this paper, especially in terms of why the results are theoretically or practically significant. For example, how such tight asymptotics for extreme order statistics (rather than just sample mean) particularly beneficial in best-arm identification examples? \n\n--- \n### Typos\n1. Subsection title 1.2. : overivew -> overview\n2. Citation [14]: Daniel Levy and et al. -> need to be revised.\n3. In the proof of Proposition 6, missing spaces in Lines 708 and 709: escalatordistribution -> escalator distribution.", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "### Strength\n\n* New theoretical insight for all fixed $\\ell\\geq 2$.\n\nThe paper illustrates how the expected $\\ell$-th largest order statistic, $M_\\ell(n)$ behaves fundamentally differently from the maximum order statistic. For distribution with the finite expectation, it was shown that $M_1=\\Omega(g(n))$ holds for any sublinear $g(n)$ [8], but the authors show that $M_{\\ell \\geq 2} = \\Omega(g(n))$ can hold iff $\\sum_n g(n)/n^2 <\\infty$. \n\n* Validation of theoretical results by numerical experiments: Simulations cover both finite-variance and infinite-variance cases and track the empirical rate against the theoretical upper– and lower–bound results, giving concrete support to the asymptotic claims.\n\n### Weakness\n\n1. The paper establishes the theoretical behavior of $M_\\ell$ that is distinct to $M_1$, but it largely leaves readers on their own to understand what these results mean for concrete examples or for practical tasks. (although there are general applications in Section 1)\nTherefore, it would be beneficial to have some discussions on the obtained results.\n\nFor example, while the authors explained that it is impossible to derive a specific sublinear function $g(n)$ satisfying $M_\\ell^F(n)=o(g(n))$ for given distribution $F$, one may wonder what $M_\\ell^F(n)$ looks like for familiar distributions that could be written in the closed formulation beyond $\\delta_k$ expression.\nIn this context it would be useful to illustrate the results with Fréchet-type heavy-tailed distributions, those whose tail quantile function is regularly varying with index $a>0$, i.e. $x_k = a k^a o(k^{\\epsilon})$ for any $\\epsilon>0$  (see Charras-Garrido & Lezaud, 2013 for more details).\nA classical example is the Pareto distribution with shape parameter $b>0$, for which $a=1/b$.\nFor such tails one can compute explicitly the sublinear order of $M_\\ell^F(n)$ making the sub-linear growth far more transparent than the abstract $\\delta_k$ expression.\nIncluding such examples would let readers grasp the sub-linear growth rate of $M_\\ell^F$ at a glance.\n\n2. The theorem is phrased “for every integer $\\ell\\geq 1$\", but the proof of Lemma 4 (Line 688) assumes $i$ is small enough relative to $n$ to ensure\n$$ \n\\left(1-\\frac{i^2}{n} \\right)\\left(1-\\frac{1}{n} \\right) e^{i/k} \\geq (1-1/e), \\quad k \\geq n+1.\n $$\nFor example, $i=7, n=122, k=123$ violates the inequality, so we need $n\\geq 123$ for fixed $i=7$.\nFor this reason, I think the statement of Theorem should be restated with an explicit range such as $n \\geq n_0(\\ell)$ for fixed $\\ell$ or for integer $\\ell$ small enough relative to $n$.\n\n---\nMyriam Charras-Garrido and Pascal Lezaud. Extreme value analysis: an introduction. Journal de la\nSoci´et´e Franc¸aise de Statistique, 154(2):66–97, 2013.", "was_revised": true, "final_justification": "My main concerns were the proof of Lemma 4 and the significance of the contribution.\n\nThe first point was clarified after reading the authors’ response.\n\nAs for the significance, my evaluation is primarily informed by the assessments of the other reviewers, many of whom seem satisfied with the results. However, since I am not familiar with this topic, I remain uncertain about my own evaluation.", "rebuttal": "We thank Reviewer 6S2N for the detailed feedback and questions. Below, we address the concerns raised, clarify points of misunderstanding, and provide additional examples and context where requested.\n\n**1. Concrete examples and practical tasks.**\n\nWe appreciate the suggestion to illustrate our results using familiar heavy‑tailed distributions. Indeed, it is instructive to examine the Pareto distribution as a standard example. For Pareto$(1,b)$ with shape parameter $b=1+\\epsilon$, the distribution has finite expectation, and it can be shown that $M_1 = \\Theta(n^{1/b})$ (see e.g. Downey, ORL 1990). A similar argument shows that $M_2=\\Theta(n^{1/b})$. Our work complements such examples by characterizing necessary and sufficient conditions under which the asymptotic behavior of $M_1$ and $M_2$ diverge. Addressing this question required constructing specific distribution families that go beyond well‑known examples, but we agree that further exploring these connections is a natural next step in extending the theoretical boundary of our results.\n\n**2. Assumptions in Lemma 4 and Theorem 1.**\n\nWe apologize for the confusion. In Lemma 4, we substitute $ i=\\ell $ and do assume that $\\ell$ is constant (independent of $n,k$) and that $n$ is large enough with respect to $\\ell$, e.g. $n = \\Omega(\\ell^2)$. We will make this explicit in the statement of Lemma 4 and Theorem 1, consistent with your suggestion. \n\n**3. Distinctions among the three regimes.**\n\nWe appreciate the opportunity to clarify the distinction between the three regimes in the asymptotic analysis of order statistics. The central/quantile case is widely used in practice, for example, in risk management to measure the losses in the worst $p$% of scenarios (Value-at-Risk). Theoretically, the asymptotics for $X_{ \\lfloor pn \\rfloor }$ are well understood since CLT-like results apply under mild assumptions. The extreme case appears naturally in several applications (as mentioned in the paper). Technically, this case differs from the previous one in that the asymptotic distribution is not Gaussian, and additional assumptions need to be made to understand the overall asymptotic behavior (Extreme Value Theory). The fundamental question we address differs from the classic extreme value theory, in that we study the transient behavior as $n$ increases even if a limit distribution may not exist. Finally, the intermediate case is technically more complex than the extreme regime, and we fail to see additional practical motivations for research.\n\n**4. Significance of the contribution.**\n\nWe appreciate the opportunity to clarify why the results are impactful. Our paper addresses a simple yet fundamental theoretical question regarding the possible growth rates achievable by extreme order statistics under any distribution with finite expectation. These objects appear naturally in many applications, such as comparing first- or second-price auctions, and our results can be useful in worst-case analysis when the underlying distribution of interest is unknown. The same high-level idea can be potentially used in robust learning, where objectives such as average top‑$\\ell$ losses are considered to adapt to imbalanced and/or multi-modal data distributions better than the average loss (Fan et al. NeurIPS 2017). Although further applications remain to be fully explored, our results could be applied more broadly in learning settings where the data‑generating distribution may be adversarially chosen.\n\nReferences:\n\nPeter J Downey. Distribution-free bounds on the expectation of the maximum with scheduling applications.\nOperations Research Letters, 9(3):189–201, 1990.\n\nY. Fan, S. Lyu, Y. Ying, and B. Hu. Learning with average top-k loss. In Advances in Neural Information Processing Systems 30, pages 497–505, 2017."}]

Author rebuttal:

Meta-review: This paper studies the growth rate of the expectation of general $\ell$-th order statistics with respect to the number of i.i.d. samples. This paper derives a tight characterization of the growth rate, which demonstrates the significant difference from the case of the maximum ($\ell=1$). The findings are also validated through numerical simulations.

The reviewers agreed in the opinion that the paper studies a very fundamental problem and the derived result is significant. Though various technical concerns are raised from L83L and 6S2N, they are clearly solved by the rebuttal. I expect that these points and other comments on the presentation are carefully addressed in the final version.  

Remaining concern is that the result may be of limited interest for NeurIPS community and the practical usage is somewhat unclear. I also agree with this point. In fact, the distribution giving the bound in this paper has extremely heavy tails, and I'm not sure how it is relevant for practical scenarios. For example, I don't think that such distribution appears in the reasonably-designed second-price auction. While the reviewers and I agree that this point is not serious, this is part of the reason why I do not recommend spotlight presentation even though I personally highly enjoyed the paper.
Decision: Accept (poster)