Small Resamples, Sharp Guarantees: Convergence Rates for Resampled Studentized Quantile Estimators
Authors: Imon Banerjee
Sayak Chakrabarty
Venue: NeurIPS 2025 poster ()
Keywords: m-out-of-n bootstrap; sample quantiles; central limit theorem; Edgeworth expansion; Berry–Esseen bounds; L-statistics; robust inference
Primary area: probabilistic_methods
TL;DR: We establish the first parameter-free CLT for m-out-of-n bootstrap quantiles, sharpen it with Edgeworth bounds for finite samples, and show gains for different learning tasks.

Abstract: The m-out-of-n bootstrap—proposed by \cite{bickel1992resampling}—approximates the distribution of a statistic by repeatedly drawing $m$ subsamples ($m \ll n$) without replacement from an original sample of size n; it is now routinely used for robust inference with heavy-tailed data, bandwidth selection, and other large-sample applications. Despite this broad applicability across econometrics, biostatistics, and machine-learning workflows, rigorous parameter-free guarantees for the soundness of the m-out-of-n bootstrap when estimating sample quantiles have remained elusive.

This paper establishes such guarantees by analysing the estimator of sample quantiles obtained from m-out-of-n resampling of a dataset of length n. We first prove a central limit theorem for a fully data-driven version of the estimator that holds under a mild moment condition and involves no unknown nuisance parameters. We then show that the moment assumption is essentially tight by constructing a counter-example in which the CLT fails. Strengthening the assumptions slightly, we derive an Edgeworth expansion that delivers exact convergence rates and, as a corollary, a Berry–Esséen bound on the bootstrap approximation error. Finally, we illustrate the scope of our results by obtaining parameter-free asymptotic distributions for practical statistics, including the quantiles for random walk MH, and rewards of ergodic MDP's, thereby demonstrating the usefulness of our theory in modern estimation and learning tasks.

Small Resamples, Sharp Guarantees: Convergence Rates for Resampled Studentized Quantile Estimators
Imon Banerjee
Department of Industrial Engineering and Management Science Northwestern University
Sayak Chakrabarty
Department of Computer Science
Northwestern University
Abstract
The m-out-of-n bootstrap-proposseee by BBickel et al. [1992] approximates the distribution of statistic by repeatedly drawing m subsamples (m < n) without replacement from an original sample of size n; it is now routinely used for robust inference with heavy-tailed data, bandwidth selection, and other large-sample applications. Despite this broad applicability across econometrics, biostatistics, and machine-learning workflows, rigorous parameter-free guarantees for the soundness of the m-out-of-n bootstrap when estimating sample quantiles have remained elusive.
This paper establishes such guarantees by analysing the estimator of sample quan- tiles obtained from m-out-of-n resampling of dataset of length We first prove a central limit theorem for a fully data-driven version of the estimator that holds under mild moment condition and involves no unknown nuisance parameters. We then show that the moment assumption essentially tight by constructing a counter-example in which the CLT fails. Strengthening the assumptions slightly, we derive an Edgeworth expansion that delivers exact convergence rates and, as corollary, Berry-Esséen bound the bootstrap approximation error. Finally, we illustrate the scope of our results by obtaining parameter-fie free asymptotic distri- butions for practical statistics, including the quantiles for random walk MH, and rewards of ergodic MDP's, thereby demonstrating the usefulness of our theory modern estimation and learning tasks.
Introduction
The bootstrap-first proposed by Efron inference. Yet its orthodox form, which repeatedly resamples the full data set of size n, suffers two key respects: (i) resampling the entire dataset lacks computational appeal when is large, and more importantly (ii) is inconsistent for several common statistics under heavy-tailed irregular models (see Ex To alleviate these drawbacks, Bickel et al. [1992 advocated drawing only m < observations each resampling step-the the so-called m-out-of-n bootstrup.
1979
-uicklyy became a cornerstone of non-parametric
To set the stage, we introduce some notation. Let X,,X2. X2,..., X,, be observations from either an univariate distribution F' real-valued Markov chain with stationary distribution F. Assume that F has unique p-th population quantile μ and a density f that is positive and continuous in neighborhood of μ. Let F(t) " 1(X, < f} be the empirical distribution of (X.). For
m < n, draw an i.i.d. sample X X of size from F. Let F (m)) (t) m Σm 1(x < {
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

be the empirical distribution function of these resampled points. The m-out-of-n bootstrap estimator of the p-th quantile is then defined by fim
(boot) inf F (t) 2 p)-
We denote by in the usual sample estimator of μ from the original data, and we write 2 (bboot) for the m-out-of-n bootstrap estimator of f.. Let o,, be an estimator of Var (an(p p)) The Studentized estimator of a then T, vn((pn -)//n.
In order to Studentize the m-out-of-n estimator, we analogously use the conditional variance of (boot
v mm(pm (boot)
(n), given the original sample {Xi}, denoted by dm Consequently, define
Thboot) (w) /m(pmoot (hoot) -Pa)
& (boot)
This the Studentized m-out-of-n bootstrap estimator of the sample quantile. As we remark below, this step is not optional in practice. However, Studentization introduces additional technical challenges. For instance, we show that, without further constraints on F, (boot) tend to infinity even if pm (hoot) itself is consistent estimator of μ.
At this point, we make note that we are looking at non- non-parametric or "model free" bootstrap, and the standard results on maximum likelihood does not apply our case. Instead, the approach we take relies on empirical process theory [Van Der Vaart and Wellner 2023 Therefore, they are generalisable a wide class of distribution functions.
Empirical studies confirmed the practical values of the m-out-of-n bootstrap, but also revealed new pathologies: Andreww and Guggenberger (2010) showed size distortions for subsampling- tests, and Simar and Wilson| [2011] demonstrated that the naive (full-sample) bootstrap is inconsistent for DEA estimators whereas the m-out-of-n variant is not. Despite these successes, the m-out-of-n bootstrap's 's fundamental properties remain only partially understood.
Initially, our work was motivated by the need for bootstrap based distribution free tests for practical tasks on Markov chains like Markov Chain Monte Carlo (MCMC) and Reinforcement Learning (RL). However, we quickly realised that this problem
not satisfactorily studied even when the data was ii.d. We present two out of numerous glaring examples: one significant discrepancy seems to be in Cheung and Lee (005), which gives incorrect variance formula for the m-out-of-n estimator of sample quantiles without derivations or citations. Another work Gribkova and Helmers [2007] derive an Edgeworth expansion for Studentized trimmed means in the non-classical m > n regime, offering theoretical insights but leaving unanswered the setting when m < m, which motivates subsampling.
Our work addresses these practically relevant open questions that were left unanswered in previous studies by supplying corrected rates and Edgeworth expansions tailored to the practically relevant m < regime. More details given in Section 3
Furthermore, we also show that the m-out-of-n bootstrap does not seem to suffer from the usual pitfalls of orthodox bootstrap pointed out in seminal PTRF paper by Hall and Martin [1988b] 1991 (see section 4.2 for full details), thus acquitting bootstrap in practical utility. We now briefly mention our contributions.
Consistent Studentization under minimal moments. We establish that the plug-in variance for both i.i.d (Theorem IT and Markovian (Theorem 3) data. Proposition [ shows the moment condition is essentially sharp: heavy-tailed distributions preclude a central-limit theorem for the Studentized median. We then demonstrate the applicability of our results by deriving parameter free asymptotic distributions for common types of problems such as the median of random walk Metropolis Hastings, the median reward in offline MDP's.
estimator (boot) is consistent whenever ||X < oc for some
Exact Edgeworth expansion at classical scaling. Exploiting binomial representation, we obtain the first correct 0mm-1/2) Edgeworth expansion for the Studentized m-out-of-n quantile (Theorem 2) In constrast to orthodox bootstrap (Hall and Martin 1991], the expansion is symmetric; reflecting the intrinsic "smoothing" induced by subsampling and immediately yields a Berry-Esseen bound (Corollary I].
lg (boot) mm
admits closed form representation; eq. B.2

---

Clarification of prior discrepancies. Lemmas 6 supply corrected variance formula, by correcting the algebraic sourees of error in Cheung and Lee [005]]
The rest of the paper is organized as follows: Section 2 outlines a comprehensive discussion of relevant research works. In section 3, we formally introduce the model and the relevant notations. In section 4, we provide our key theoretical results and the proof sketches for these, while the full proofs have been deferred till the appendix due to lack of space. Section 5 contains various applications for our results, and finally, in Section 6, we conclude by mentioning the limitations and broader impact of our work.
2 Background and Related Research
The bootstrap, introduced by Efron [Efron 1979 1982]. has become a cornerstone of modern statistical learning [Nakkiran et al., 2021 Modayil and Kuipers, 2021]] Han and Liu 2016]. Its intuitive appeal and computational simplicity have led to widespread use across diverse fields such as finance, economics, and biostatistics. In many practical settings, especially those involving complex models or nonstandard error bootstrap often creates better confidence intervals (Hall and Padmanabhan 1992]. For example, in principal component analysis, bootstrap techniques have been employed for sparse PCA and consistency analysis [Rahoma et al. 2021 Baabamoradi et al.)
2013 Datta and Chakrabarty 2024]. Time-series applications appear in Ruiz and Pascual [002]]
whereas econometric and financial analyses are discussed in [Vinod] 1993 Gonçalves et al. 2023]
More recently, bootstrap- based methods have been explored in reinforcement learning [Ramprasad
et al. 2023 Zhang et al. [002 Faradonbeh et al. 2019 Banerjeee 2023 Zhang et al., 2023]. Markoy
and controlled led Markov chains [orrar 1991 Banerjee et al. [025]] Gaussian and non-Gaussian
POMDP's Krishnamurthy 2016 Banerjee and Gurvich| 2025] and in clustering/classifiis
(Jain
and Moreau 1987 Moreau and Jain 1987 Makarychev and Chakrabarty 2024
significant body of work has focused on traditional bootstrap methods for median and quantile estimation. For instance. Ghosh et al. | [1984a] studied the convergence of bootstrap variance estimators for sample medians, while Bickel et al. [199]] employed Edgeworth expansions to obtain optimal rates of convergence. Incorporating density estimates for studentized quantiles was examined in
Hall and Martin 1988a), Hall and Sheather 1988). We refer the reader to various textbooks like
Hall [2013]. Dasgupta [0088 for theoretical treatments, and [Singh and Xie [2008). Davison and Hinkley| 1997], Freedman et al. 2007] for practical insights. Of particular interest is Liu [988].
which can be thought of a variant of our work for the sample mean rather than the median. Iterative self-alignment with implicit rewards from Direct Preference Optimization (DPO) uses "bootstrapped"
preference data to refine model behavior without additional human labels Yuu al. 2023 Wang et al.
2024 Chakkabartyy and Pal 2025 Zhang et al.) 2024 Chakrabarty and Pal 2024 Geigle et al. [203
Banerjee et al. [222]] Within symbolic AI, bootstrapping appears in inductive logic programming
(ILP) and neurosymbolic systems as seen in [Natarajan et al. 2010 Bolonkin et al. 2024
Polikar
2007 Simmons-Dutin 2015). This brings us to the following open question.
Open question. The paper resolves two open questions the theory of the Studentized m-out-of-n bootstrap. (i) Can provide single, parameter-free second-order theory-variant consistency, central-limit theorem, exact O( -1/2) Edgeworth expansion, and matching Berry-Essecd bound for bootstrap quantiles under nothing stronger than a finite-moment assumption? (ii) Can we extend the analysis to regenerative Markov chains and furnish the inaugural bootstrap-based confidence guarantees for sequential data such as MCMC or RL trajectories?
Problem Statement
In order to formalise results, we introduce some notation. Unconditional probability, expectation, and variances are denoted by P, E, Var and their conditional counterparts given the sample are P., En, Var,. o² is the asymptotic variance of the estimator of pm. 0z. and (a! (o(m))) are its empirical and m-out-of-n bootstrap counterpart.
The i-th order statistic is denoted by X We use an c(a) for scaling constants, and 4, 2, a.s. for convergence in distribution, probability, and almost surely, respectively. Bachman-Landau notations [Cormen et al. 2022 for order terms are denoted by O,o, Op. Finally, & and
3

---

the standard normal CDF and PDF, and H2(x) x²² 1 is the 2-nd Hermite polyno- mial. C denotes an universal constant whose meaning changes from line to line. SL(1)) = (f(x) ((==0(20 exists and is Lipschitz in neighborhood of μ} denotes the set of L- Sobolev smooth functions around For any set A, (A) = Nzgas St(x) is the set of all functions which are L-Sobolev at all interior points of A (denoted by A²).
Data-generating process. As before, let XI,..., Xa i.dd be real-valued with unique p-th population quantile f and density f positive and continuous near js. Denote the empirical cdf by =(1)= = -> 1(x; S 1)
and the full-sample quantile estimator by
An inf{t: F(I) 2 p}.
Choose < n and resample . X
iid F.
The resample edf Fl (t)
m E Zi=1 [x7 S {.), and the bootstrap quantile is
(booot) inf t F( (t) 2 p}.
(boot) be the conditional variance of Studentization. Write 0 = Var Var(vi(An 1d) and let oin
vm(aam Sm(pthoot) (boot)
- (n)) given {Xi}. Define the Studentized statisties
Tn Vn(íin - pt) nn
/Tri (mm (im
(Wmoot) jin)
T(boot) (11) n
(boott) O'
Remark. Studentization is not optional in practice. Typically the on-Studentized estimator converges to distribution dependent upon unknown parameters. Studentization is the only viable way derive parameter free tests of sample statistics. Yet, literature regarding its theoretical guarantees is sparse.
3.1
Goals
Our aim is to supply a complete second-order theory for Studentized m-out-of-n bootstrap quantiles under the weakest credible assumptions (finite a-th moment, 0). Four concrete targets guide the paper:
1. Variance consistency and a CLT. Demonstrate that the resampled variance converges to the population counterpart and the Studentized statistic tends to (O 1) whenever o(n).
2. Quantitative error control. Obtain one-term, correctly centred Edgeworth expansion whose remainder is Op(m (m/2),,,,, thereby delivering a uniform Berry-Esseee bound of the same order.
3. Removal of legacy inconsistencies. Correct the variance formula of Cheung and Lee 20055 Furthermore, unlike some previous literature [Gribkova and Helmers (007]. our new proofs o(n)).
work in the practically relevant regime m < (and
4. Beyond i..dd data. Extend variance consistency and the CLT to regenerative Markov chains, giving what appears to be the first bootstrap-based confidence guarantees for dependent sequences such as MCMC reinforcemeentleariing trajectories.
4 Theoretical Results
Recall from the Section 3.1 that our first objective is to provide an asymptotic consistency theorem for the variance of the m-out-of-n bootstrap estimator of the sample quantile. We prove this assuming only the barebones that F S₁ (H4), and that E X |= < oo for some a > 0. Later, we discuss the necessity of the assumption X _ < co. Since the techniques in this proof will be reused multiple times, we also provide a detailed proof sketch.
Theorem 1. Let μ be the unique p-th quantile and F E (p). Furthermore, let E|X, 50 for
some & > 0. Then for any o(n), and mn, +
(
p p) (boot) m
(2

---

Furthermore,
mm (hoot)
(boot) (nx) 4 NO.
Thhooot)
(4)
Sketch of proof: Step I. Because the data have finite a-th moment, values larger than n 1/2 occur only finitely many times (Borel-Cantelli). Consequently, the sample maximum and minimum are shown to be negligible.
[X + (m)))
u.s. O.
n/a
(hoot) Step II. Consider the gap Pm
fln
Medium deviations.
For up to (2 + Vlg m, a Taylor expansion plus Dvoret- zky- KieferiWolffeeeee bound shows (nnvm |ithoot Aml t) Ot
Large deviations, For above that threshold, a Hoeffding- -teyf inequality gives polynomial bound 0(m (1/0+1/2)(2+8))
These tail bounds imply the family m (boot)
(im
pmm)² is uniformly integrable and
a.s. ((1-9) (1))
(o (b(oo)))
f2
Step III. We then derive -tnStttdntteed CLT as follows
(..) - v((0, g(1 (01-9)
m (i (boot)
f²(1)
Step IV. Putting the variance consistency (Step 2) together with the CLT (Step 3) and invoking Slutsky's theorem, we arrive at
v m (jmn (bboo))
pm) d, NO0, 1),
d (boot)
which is the assertion of Theorem
4.1 Importance of the Moment Condition
We briefly discuss the necessity of the condition E|X, a oo in Theorem close observation at the proof indicates that we only really need the condition in eq. (A.I). However, we found such conditions terse and un-illuminating.
On the other hand, the following exnter-example shows that one cannot outright discard tail conditions. Note that this does not imply that the condition [ oc is necessary condition, but rather demonstrates that Theorem cannot be expected to hold for arbitrarily heavy-tailed distributions. Although this phenomenon has been observed via simulation [Sakov] 1998 provide
what is, to our knowledge, the first theoretical justification.
Proposition Let m be fixed. Let F(x) be the following class of distribution functions: For some large C c,
> C,
F(x)
2log
G(x)
1/ C
where is a monotonically increasing function such that G(O) 1/2 and G(x) has a positive derivative in neighborhood 0f O. Then the variance of the m out of bootstrap estimator for the median goes to 20, i.e. E,, (p.0oooooo (boot)
ppn)² a.s.
5

---

As be seen from Proposition (see Ghosh et al. distributions for which the m-out-of-n (and orthodox) bootstrap estimator of the variance of the sample quantile inconsistent. However, there are no current results which concretely characterises this regime (even when m 12). The citations of Ghosh et al. [1984b] are mostly in the form of remarks in either textbooks tangentially related papers. It therefore remains an important open theoretical question, especially in the context of finance where heavy tailed distributions are ubiquitous [bragimov al. [2015). However, is beyond the scope of current work. We now move to establish Edgeworth expansions.
(9844]] there exists regimes of heavy-tailed
4.2 Convergence Rates Via Edgeworth Expansions
The following theorem proves Edgeworth expansion of the Studentized m-out-of-n bootstrapped distribution of the quantile.
Theorem 2. Assume that μs is the unique p-th quantile such that F E Sz(u) and f(u) 0.
Furthermore, let m = o(n>) for some X E (0, 1). Then,
Vm
(boot) jim)
① (t) (la)² $1
(0s(1) (p(1-pp)
1 m
P
vm f'()
Op
(boot)
mm
+ Op(m 1/4n -1/2).
Sketch of Proof: After obtaining correct form for the variance in Lemma 7 the strategy of our proof will be a combination of an Edgeworth expansion of the Binomial distribution (Proposition [2] followed by an appropriate Taylor series expansion of the CDF (Lemma IOp. The proof will then be complete by calculating the rate of decay of the error terms in the Taylor series. See Section C for
full details.
Remark. Observe the assumptions on F, and m, are slightly stronger than those in Theorem 7 It is required get a rate of convergence of the variance. Similar stronger assumptions are standard in literature (Hall and Martin 1997].
We discuss some implications of this theorem. Firstly, one recover Berry-Esseen type bound as an immediate consequence.
Corollary 1. Under the conditions of Theorem
2
(boot)
(nn) 51 31)-000 (1) Op(mm 1/2)
sup xE(-00,00)
Pn
(boot) Fm
Next, by comparing Theorem 2 with the main Theorem of Hall and Martin 1991]. one can see that the (n 1/4 Om- 111111/2//)//) 1/2) term in Theorem replaces the Op(n (n/4))) ) in the main Theorem of Hall and Martin [191] along with an extra (I/m). recovering previous results. If m is sufficiently large, the (m //n-1/11/ 1/2) term dominates, whereas is small, (1/m) becomes the leading term, and we recover the usual form of Edgeworth expansions. However, setting m too small also deteriorates the rate of decay of the error.
Furthermore, observe in the Edgeworth expansion that the second order term is an even polynomial, whereas for the orthodox bootstrap. the polynomial is neither odd nor even (Hall and Martin [991 Van der Vaart 2000]. Therefore, unlike orthodox bootstrap (See Appendix Hall [2013). D), m-out-of-n bootstrap can be used create sided parameter-fin tests of the sample quantiles with extra Op(m error as tradeoff, which is significant development over orthodox bootstrap.
Finally, the optimal choice m seems to be m = O(n n 1/3) which known to be the minimax rate for estimating the sample median (Bickel and Sakov 2008
On the choice of m: We believe setting = en /3 for some universal constant would work well practice. The precise choice of e somewhat ambiguous but
for moderate sample sizes where m > 30, setting e = 1 typically performs well.
For small n, larger constant (i.e., e > 1) may be advisable.
For large n, even < 1 may suffice in achieving desirable performance.

---

4.3 Extensions to Regenerating Markov Chains
We now extend our results from the realm of i.idd data to regenerating Markov chains. Following the theoretical development in the previous sections, let X,...., Xn be sample from Markov chain with initial distribution v, stationary distribution F, and empirical distribution F. Then, xi....,4
said to be m-out-of-n bootstrap sample for Xj... Xn if X iid F. with other terms like F/ and (mmm) defined accordingly. Despite its ubiquitousness in modern statistics, the theory of resampling for Markov chains is sparsely studied and there exists no widely accepted method (see work attempted to study the effects of bootstrapping to create confidence intervals for statistics that are of interest in tasks like reinforcement learning or MCMC. In this section, provide what believe
Bertail and Clémençon (2066] and citations therein). In particular,
some of the first results in this field by extending the results on CLT from Section 4 to the realm of regenerating Markov chains, and then ergodic MDP. To that end, we introduce regenerating Markov chains.
recover confidence interval for the median reward of offline
The Nummelin splitting method [Nummelin] 1978 Athreya and Ney 1978 Meyn and Tweedie 2012] provides a way to recover all the regenerative properties of general Harris Markov chain. In essence, the method enlarges the probability space that one create an artificial atom. To begin, we recall the definition of a regenerative (or atomic) chain [Meyn and Tweedie 2012].
Definition v--irreducible, aperiodic chain X is said to be regenerative (or atomic) if there exists a measurable set A, called an alom, with (A) ) >> 0 such that for every pair (x.y) E A2, the transition kernely coincide, that
-) P(y.)).
Intuitively, an atom a subset of the state space which the transition probabilities are identical. In the special case where the chuin visits only finitely many states, any individual state or subset of states can serve as an atom.
Remark. v and T are commonly used in Markov chain theory to denote vo ii-irreducibility and Q- atoms, respectively [Bertail and Portier 20797. We omit formal definitions and refer the reader to standard references [Meyn and Tweedie 2012 pp. 89, 103]. Intuitively, di-rreducibiiityy generalizes the notion of irreducibility from finile to infinite state spaces, while V-atoms are subsets where transitions behave homogeneously according to measure V V-singletons in the finite-state case. A regenerating Markov chain is vd-irreducible and possesses at least one recurrent & V-atom, with inter-arrival times called regeneration times. The moment conditions these times determine the chain's 's ergodic properties.
One now extends the sample space by introducing sequence (Yr)neN of independent Bernoulli random variables with success probability This construction relies on mixture representation of the transition kernel set S:
P(r, A) = 5 ((A))))))))))))))()) + (1 P(x, A) 5 (AA)
1 5
where the first term is independent of the starting point. This independence is key since it guarantees regeneration when that component is selected. In other words, each time the chain visits S, we randomly reassign the transition probability P as follows:
If Xx E S and Y, 1 (which occurs with probability d E 1)), then the next state X is generated according to the measure V.
If X, S and Y, = 0 (with probability 1 - 8), then Xn+1 is drawn from the probability measure
(1 (1-6)-1(((X,,) -8()).
The resulting bivariate process Z = (X,,, YnNEN, is known as the split chain, and takes values in E x {0, 1} while itself being atomic, with the atom A = S x {1}. We now define the regeneration times by setting
TA = (1) inf (n 2 1 Zn E A), and for 2 2, T (f) inf > Tx(i-1) Zn E A).
well known that the split chain Z inherits the stability and communication properties of the original chain X, such y
and v-irreducibility. In particular, by the recurrence property,
7

---

the regeneration times have finite expectation.
sup 3EA
Ex [TA] < and Eu|Ta| <0.
Regeneration theory [Meyn and Tweedie 2012 shows that, given the sequence (Ta(i))i2 the sample path can divided into blocks (or cycles) defined by
By (Z) . (+))) j21,
corresponding successive visits to the regeneration set A. The strong Markov property then ensures that both the regeneration times and the blocks {By 112 form independent and identically distributed (i.i.)) sequences [Meyn and Tweedie 2012, Chapter 13].
Assumption 1. We impose the following conditions:
1. The chain nNN) is a positive Harris recurrent, aperiodic Markov chain with stationary distribution F, and initial measure compact state space, which will assume to be [0, 1] without losing generality. Furthermore, there exists a --small set S such that the hitling time tg satisfies
sup EE [TS] 00 and Ep[Ts] < co. ESS
2. There exists a constant À > O for which
and Cx = 2Es(exp(ATa))
Exlexp(ATA)] < oc.
A
2
3. Let μ be the p-th quantile. Then, F, E S1(p).
Remark. The assumption of compact state space is technical, and can be replaced with uniform ergodicity with significantly more tedium. Geometrically ergodic chains automatically satisfy the previous assumption (more details in the appendix. See also, Bertail and Portier (2019)).
We now give main theorem of this section.
Theorem 3. Let Xi...., Xn be sample from Markov chain satisfying Assumption 7 Then, for all m on),, , the m-out-of-n bootstrap estimator of μ satisfies,
(booot (1) N(011 m
Sketch of Proof: Using techniques VC dimensions (see E. p. we first establish Dvoret- oky-Kiefer-Wolfowizz (DKW) inequality for regenerating Markov chains. This inequality ap- parently new, and due to wide applicability in variety of other tasks like nonparametric density estimation [Sen (2018). change point detection Zou et al. (2014), etc. we present an informal version below, while relegating the final version Section E With this theorem, the rest of the proof proceeds on strategically similar path to Theorem [] but each step is now technically more intricate and requires careful coupling arguments. See Section for full details.
Proposition 2 (Informal version of Proposition Assumption with stationary distribution F, and define
Let XI...., Xn, be Markov chain satisfying
Z : sup sE(U.1]
[F()) F(t)
Then, for all æ > 0
(- -- log
C(T, A)mz?
P(Z 2) CT,
(4.1)
where, constants C(T, X), (T, depend only on the parameters in Assumption 7 and is explicitly
defined in Section E
Remark. The log n term to ensure mixing and is a common compromise when transitioning to Markov chains Samson 2000

---

5 Applications
We show how our results can used to derive the asymptotic distributions of some popular statistics. The proofs of the results in this section, well more examples can be found in the appendix.
Random Walk MH: Random walk Metropolis- Hastings (MH) algorithms are an important algorithm to sample from posterior density in Bayesian statistics Gelman et al. [1995]. To set the stage, we introduce the random walk Metropolis-Hastingg
(MH) algorithm with target density x IR - Rz0 and proposal (z, dy) q(z y) dy. where q is positive function on IR x R satisfying
f(((z - y) dy = 1. For any (x, y) x IR define
min (1, T(V) gly xx)
if - y) > 0,
p(x, v)
(()) q(I
if y)
The MH chain starts Xo v and moves from Xn to X according to the following rule:
1. Generate
Y ((nn,dd)) and
W ~ Bernoull((p(Xm. Y)).
2. With 1 as the indicator function, set
X, = 0].
We consider the following ball condition the proposal qu associated with the random-walk Metropolis Hastings algorithm which is popular in analysing the drift conditions.
Assumption 2. Let æ S1 (p) be a bounded probability density supported on bounded convex E C I. non-empty interior. Suppose there exist b > O and ε >> O such that Va E IR I. (x))) b (zr) where B(x) is the open ball with center 0 and radius e.
We now have the following corollary,
Corollary 2. Let be the unique median of n, and XI...., Xn be sample from the MCMC rule described above. Then, fnn E μ and for all o(n)
Tobooot (1) 4 (0,
Offfine Ergodic MDP's: Testing for the mean/median rewards offline MDP's is an important problem in reinforcement learning [Sutton and Barto 2018 Let {(X,, rx) } be an offline sample from an MDP on state space [o. 1]2 under a given policy π. We will make the following assumption. The rewards generated by given reward function Formally, r [0, 1] [0. 1] and rą r(X.). We note that the state space can be any compact set other than [o, 1]2, and such compactness restriction common in practice. One can replace this assumption with geometric ergodicity under æ. We will make the following assumption.
Assumption The transition density of X, under the policy n positive and admits two continuously differentiable derivatives. The reward function is one-one and onto and admits an inverse that is twice continuously differentiable.
Under the previous assumptions, we have the following corollary:
Corollary 3. Let y be the median reward, and fún be its estimator. Then the m-out-of-n bootstrap estimator of ü.n satisfies.
(hboot) (p) 4 N0,1).
It follows that with probability 0.95
ün E (boot) + 1.966 (boot) //m.
Corollary to the best of our knowledge, the first parameter free confidence interval for the median rewards for offline MDP's.

---

6 Conclusion
This paper delivers a unified second-order theory for the Studentized m-out-of-n bootstrap. (i) We prove the first parameter-free central limit theorem for the resampled quantile estimator under only a finite- mnite-moment assumption, establishing rigorous guarantees for a tool already ubiquitous in practice. (ii) Leveraging a novel binomial representation, we obtain an exact 0(m-1/2) Edgeworth expansion together with matching Berry-Esseen bound, thereby pinpointing when subsampling genuinely sharpens inference. (iii) We extend these results to regenerative Markov chains, providing the first bootstrap-basee confidence guarantees for sequential data and illustrating the framework through applications such as Metropolis Hastings and offline MDPs. (iv) Throughout, we rectify long-standing enrors in prior variance formulas and Edgeworth analyses, and we give principled guidance on choosing m.
Limitations and outlook. Our guarantees still assume mild smoothness and leave open the precise heavy-tail boundary, non-stationary processes, and adaptive variants remain compelling directions for future study. The question regarding the joint normality of the estimators also remain an important open question. Finally, it would also be nice to have an Edgeworth expansion of the Studentized bootstrap estimator for Markov chains. However, the theory of Edgeworth expansion on lattices for regenerating Markov chains seems to be sparse (in particular, we could not find usable counterpart to Proposition 12 for Markov chains). Deriving such result is out of scope for this (already lengthy) paper, and we plan to study in a future work.
Another important assumption is that of regeneration. We note that the exponential moment condition in Assumption 1 is equivalent to the more classical geometric ergodicity of Markov chains (see Theorem 16.0.2 in Meyn and Tweedie (2012). It is known that a weaker polynomial moment condition is equivalent to arithmatically mixing for Markov chains, and corresponding result in this regime seems plausible, and warrants future investigation.
Finally, natural extension of this work involves applying our framework to other estimators, particularly U- and M-estimators, which are commonly used in bootstrapping. Certain classes of M-estimation problems, such as shrinkage problems (see Chapter in Hall which yields the median) or
loss functions, naturally lead to quantile estimation. In other cases, where the M-estimator depends on function of quantiles. one may appeal to classical tools such as the delta method or CLT for M-estimators (see Theorem 5.21 in Van der Vaart (2000)) to establish asymptotic normality. That said, a comprehensive theory for these broader classes of estimators lies beyond the scope of the current work, but we view it as a compelling direction for future research.
7
Acknowledgment
The first author thanks Jorge Loria, Ksheera Sagar, and Ziwei Su for carefully going over an earlier edition of the draft and providing useful comments. The first author acknowledges the IEMS Alumni Fellowship at Northwestern University for financial support during which this research was conducted. The authors ack acknowledge the five anonymous reviewers for their useful comments and suggestions which significantly improved the readability of the paper.
References
R. Adamczak. A tail inequality for suprema of unbounded empirical processes with applications to Markov chains. Electronic Journal of Probability, 130mome):10000-0044 Jan. 2008 ISSN 1083-6489, 1083-6489. doi: 10.1214/EJRw13-5211 URL wttp://pp////pppeeeeeeeeeeeeeeae
A- #aa.hhheeelllrorerooosseeaeeeeee 10. 10.1221//JP..13--11
/
D. W. Andrews and P. Guggenberger. Asymptotic size and problem with subsampling and with the m out of bootstrap. Econometric Theory, 26(2):426-468, 2010.
K. B. Athreya and Ney. A New Approach to the Limit Theory of Recurrent Markov Chains. Transactions of the American Mathematical Society, 245:493-501, 1978. ISSN 0002-9947. doi: 10.2307/1998882. URL |tt/https:/ //tp://wwww....... www. jstor. wwt. 998882 American Mathematical Society.
Publisher:
10

---

H. Babamoradi, F. den Berg, and Á. Rinnan. Bootstrap based confidence limits in principal component analysis- case study. Chemometrics and Intelligent Laboratory Systems, 120:97-105, 2013.
R. R. Bahadur. Note on Quantiles in Large Samples. The Annals of Mathematical Stafistics, 37(3): 577-580, June 1966. ISSN 0003-4851, 2168 8990. doi: 1aw1122///mm//117777// URL httpst anna
//projecteuclid.com .d..eeeclidd..oo www.ddoooooooooaaooooooooooo
Sollum-37/issee 3/A-Note
Note on Quantiles
Large Samples/10.1211
acms acms/1177699455 Full
I. Banerjee. PROBABLY APPROXIMATEL, CORRECT BOUNDS FOR ESTIMATING MARKOV TRANSITION KERNELS. PhD thesis, Purdue University Graduate School, 2023.
I. Banerjee and I. Gurvich. Goggin's corrected Kalman Filter: Guarantees and Filtering Regimes, Feb. 2025. URL http::tp://arx:
hbtpgg/abb///2///2 14053] arXiv:2502. 14055 [cs].
I. Banerjee, V. A. Rao, and H. Honnappa. Pac-bayes bounds variational tempered posteriors for markov models. Entropy, 23()):313, 2021.
I. Banerjee, H. Honnappa, and V. Rao. Off-line Estimation of Controlled Markov Chains: Minimaxity and Sample Complexity. Operations Research, Feb. 2025. ISSN 0030-364X, doi: 10. 10.122770pre.2000 w0w.:ree..220.000 0046. URL https::/ppbssoniin... wtw.lliiineiiinnnoeee informs. htt.ee/.......o.o.oooo////aaaaa. org//oi/abs/ 10. 15.1228/optt 2023. 0046
P. Bertail and S. Clémençon. Regenerative block bootstrap for markov chains. Bernouli,, 12(4):
689-712, 2006.
P. Bertail and F. Portier. Rademacher complexity for Markov chains: Applica- tions to kernel smoothing and Metropolis Haattoplis-HHattnnss. 3938, Nov. 2019. ISSN 1350-7265.
Bernoulli, 25(4B 25(4B):3912 ):3912
doi: 10.3150/19-BJJ1155 //ter//tttaaaaacooooooo//aaaaaan
URL https:
Rademacher--com Ba
kertol smoothing/
10. 10.3150/19-3RJ111 full
P. J. Bickel and A. Sakov. On the choice of m in the out of bootstrap and confidence bounds
for extrema. Statistica Sinica, 18(3):967-995 985, 2008. ISSN 10170405, 19968507. URL http:
7/www. jstor. org/ stt.saaaba...... 243008525
Bickel, F. Götze, and W. R. van Zwet. Resampling fewer than n observations: gains, losses, and approximations. Statistica Sinica, 2(1):1-31, 1992.
M. Bolonkin, S. Chakrabarty, C. Molinaro, and V. Subrahmanian. Judicial support tool: Finding the k most likely judicial worlds. In International Conference on Scalable Uncertainty Management, pages 53-69. 69. Springer, 2024.
V. S. Borkar. Topics in controlled Markov chains. Longman Scientific & Technical, Harlow, UK. 1991.
R. C. Bradley. Basic Properties of Strong Mixing Conditions. A Survey and Some Open Questions. Probability Surveys, 1:107-144, 2005. doi: 50545555555 100000104. URL "hitps:/ dei. doi.org/10 1214 015e////9557001000010000 Statistics and the Bernoulli Society".
Publisher: "The Institute of Mathematical
S. Chakrabarty and S. Pal. Mm-poe: Multiple choice reasoning via. process of elimination using multi-modal models. arXiv preprint arXiv:2412.07148, 2024.
S. Chakrabarty and S. Pal. Readmeready: Free and customizable code documentation with Ilms-a fine-tuning approach. Journal of Open Source Software, 10(108):7489, 2025.
K. Y. Cheung and S. M. S. Lee. Variance estimation for sample quantiles using them out ofn bootstrap. Annals of the Institute of Statistical Mathematics, 57(2):27--29) June 2005. ISSN 1572-9052. doi: 10. 10.1007//F025070026 URL htw.h:tpp............... /oi org 10. 100000000000000 0F50000226

---

T. H. Cormen, C. E. Leiserson, R. I.. Rivest, and C. Stein. Introduction to Algorithms, fourth edition. MIT Press, Apr. 2022. ISBN 978-00266-366550-9
A. Dasgupta. Asymptotic Theory of Statistics and Probability. Springer Texts in Statis-
tics. Springer, New York, NY, 2008. ISBN 978-0-387-75970--8 978-0-387-75971-5 doi: 101107797500-37-799775 978 0 387- 387-75971-5
URL http://link: springrrie www.nger.commm11111... com/ 1007/
A. Datta and S. Chakrabarty. On the consistency of maximum likelihood estimation of probabilistic principal component analysis. Advances in Neural Information Processing Systems, 36, 2024.
A. C. Davison and D. V. Hinkley, Bootstrap methods and their application. Number 1. Cambridge university press, 1997.
B. Efron. Bootstrap methods: another look at the jackknife. Annals Statistics, 7(1):1-26, 1979.
B. Efron. The Jackknife, the Bootstrap and Other Resampling Plans. SIAM, Philadelphia, PA, 1982.
M. K. Faradonbeh, A. Tewari, and G. Michailidis. On applications of bootstrap in continuous space reinforcement learning. In 2019 IEEE 58th Conference on Decision and Control (CDC), pages 1977-1984. IEEE, 2019.
W. Feller. Introduction to Probability Theory and Its Applications, Volume 2. John Wiley & Sons, Jan. 1991. ISBN 978-0-471-25709-7.
D. Freedman, R. Pisani, and R. Purves. Statisticx: Fourth International Student Edition. W.W. Norton & Company, Feb. 2007. ISBN 978-0-393-93043-6.
G. Geigle, A. Jain, R. Timofte, and G. Glavaš. mblip: Efficient bootstrapping of multilingual vision-llms. arXiv preprint arXiv:2307.0693/ 2023.
A. Gelman, J. B. Carlin, H. S. Stern, and D. B. Rubin. Bayesian data analysis. Chapman and Hall/CRC, 1995.
M. Ghosh, W. C. Parr, and K. Singh. Asymptotic performance of the bootstrap for estimating the distribution of m-estimators. Annals of Staristics, 12(():900-99) 912, 1984a.
M. Ghosh, W. C. Parr, K. Singh, and G. Babu. A Note on Bootstrapping the Sample Median. The Annals of Statistics, ISSN 0090-5364, 2168-8966. doi: 10.1214/ao/111664673111
100:1130-11355
Sept. 1984b.
URL https:
www.uciid.oooo wttp:///teeeciooooo/oooooooooaa Is/anaa 8- of www-ooostttstiicatttaaaaaaa w ume-122 the
1176346731 full
S. Gonçalves, U. Hounyo, A. J. Patton, and K. Sheppard. Bootstrapping two-stage quasi-maximum likelihood estimators of time series models. Journal of Business & Economic Statistics, 41()): 683-694, 2023.
N. V. Gribkova and R. Helmers. On the Edgeworth expansion and the M out N bootstrap accuracy for Studentized trimmed mean. Mathematical Methods of Statistics, 16(2):142-176, June 2007. ISSN 1934-8045. doi: 10.100///166533377000000666 S 61066530707020C555
J. Hajnal and M. S. Bartlett. Weak ergodicity in non-homogeneous Markov chains. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 54, pages 233-246. Cambridge University Press, 1958.
Hall. The bootstrap and Edgeworth expansion. Springer Science & Business Media, 2013.
Hall and A. Martin. Exact convergence rate of bootstrap quantile variance estimator. Probability theory and related fields, 80(2):261-26 1988a.
12

---

Hall and M. A. Martin. Exact convergence rate of bootstrap quantile variance estimator. Probability Theory and Related Fields, 80(2):6112668, Dec. 1988b. ISSN 1432-2064. doi: 10. 10.1007/BF00356005 https:s::///agt
Hall and M. Martin. On the error incurred using the bootstrap variance estimate when constructing confidence intervals for quantiles. Journal of Multivariate Analysis, 38(1):70- 81. July 1991. ISSN 0047-259X. doi: 10100660447229XX000000222222 URL https
www. sciencedirect. com/ http://sssneeeaaatcceeeaaa//////
990022
Hall and A. Padmanabhan. On the bootstrap and the trimmed mean.
Jour-
nal of Multivariate Analysis, 41(1):132-153, Apr. 1992. ISSN 0047-259X. doi:
10.
URL https://www wwwencediieeeeeeeoooocc.. com/ scinncience/
Btt.clle/p110044225X999999
P. Hall and S. Sheather. On the distribution of studentized quantile. Journal of the Royal Statistical Society: Series B (Methodological), 506):381-391, 913 1988.
J. Han and Q. Liu. Bootstrap Model Aggregation for Distributed Statistical Learn- ing. Advances in Neural Information Processing Systems, volume 29. Curran Asso- ciates, Inc., 2016. URL https:
wwu..nn....nnrrrr neurips. httppp.cc..p.p...p. pcc/paper220 /201 6/hash, Abstract html
M. Ibragimov, R. Ibragimov, and J. Walden. Heavy-Tuiled Distributions and Robustness in Economics
and Finance, volume 214 of Lecture Notes in Statistics. Springer International Publishing, Cham,
2015. ISBN 978-3-319-1688778 978-3-319-16877-1
doi: 10. 10.1007/978-331199 16877-7. URL
https:/ springer. com/ 10. 10000....01900000
319 16877-7
A. K. Jain and J. Moreau. Bootstrap technique cluster analysis. 547-568, 1987.
Pattern Recognition, 20(5):
G. L. Jones. On the Markov chain central limit theorem. Probability Surveys, 1:299-320, 2004. Publisher: The Institute of Mathematical Statistics and the Bernoulli Society.
V. Krishnamurthy. Partially Observed Markov Decision Processes: From Filtering to
Controlled Sensing. Cambridge University Press, Cambridge, 2016. ISBN 978-1-107- 13460-7. doi: 1010077CCB09781116477100
URL https: www. www.cambridge ma maarko--deiiee po-oosssssssrsssssssssee
R. Liu. Bootstrap procedures under some non-iid models. The annals of stutistics, pages 1696- 1708, 1988.
K. Makarychev and S. Chakrabarty. Single-pass pivot algorithm for correlation clustering. keep simple! Advances in Neural Information Processing Systems, 36, 2024.
S. P. Meyn and R. L. Tweedie. Markov chains and stochastic stability. Springer Science & Business Media, 2012.
J. Modayil and B. Kuipers. Towards Bootstrap Learning for Object Discovery. 2021.
J. V. Moreau and A. K. Jain. The bootstrap approach to clustering. In Pattern Recognition Theory and Applications, pages 63-71. Springer, 1987.
P. Nakkiran, B. Neyshabur, and H. Sedghi. The Deep Bootstrap Framework: Good Online Learners are Good Offline Generalizers, Feb. 2021.
http:///wwww....r/a/////11/1/ 08127
S. Natarajan, G. Kunapuli, R. Maclin, D. Page, C. O'Reilly, T. Walker, and J. Shavlik. Learning from human teachers: Issues and challenges for ilp in bootstrap learning. In AAMAS Workshop on Agents Learning Interactively from Human Teachers, 2010.
E. Nummelin. A splitting technique for Harris recurrent Markov chains. Zeitschrifi für Wahrschein- lichkeüssteerrie und Verwandte Gebiete, 43(4):309-318, Dec. 1978. ISSN 1432-2064. doi: 10. 10.11077/FF00544764 URL www.httss... http://i..oogg////// 0007000000700007777333303 00534764
13

---

R. Polikar. Bootstrap-inspired techniques in computation intelligence. IEEE signal processing magazine, 24(4):59-72, 2007.
A. Rahoma, S. Imtiaz, and S. Ahmed. Sparse principal component analysis using bootstrap method. Chemical Engineering Science, 246: 16890, 2021.
P. Ramprasad, Y. Li, Z. Yang, Z. Wang, W. W. Sun, and G. Cheng. Online bootstrap inference for policy evaluation in reinforcement learning. Journal of the American Statistical Association, 118 (544):2901-2914 2023.
G. O. Roberts and R. Tweedie. Geometric Convergence and Central Limit Theorems for Multidi- mensional Hastings and Metropolis Algorithms. Biometrika, 83(1):95-110 1996. ISSN 0006-344 3444. URL Uttpttsss: //www. jstor. org/
Publisher: [Oxford University Press,
Biometrika Trust].
E. Ruiz and L. Pascual. Bootstrapping financial time series. Journal of Economic Surveys, 16(3): 271-300, 2002.
A. Sakov. Using the m out of n bootstrap in hypothesis testing. Ph.D., University of California, Berkeley, United States - Californa. 1998. http:t/t::////e/ www....p.......oomm.oooo com/ docvies 304424705 /ttt://ttttt/t55555555555553
ISBN: 9780591993228
P.-M. Samson. Concentration of measure inequalities for Markov chains and |textbackslashhhhi
mixing processes. The Anmals of Probability, 28(1):416-661 Jan. 2000. ISSN 0091- 1798, 2168-894X.
doi: 10. 10.1211/ao//1001116015,, URL http::::://// /
org oot.://nn..aaaacacooooaaaaaaionn
and- mixing/
10. 10.1224/2ag/1011160022 ful1
B. Sen. A Gentle Introduction to Empirical Process Theory and Applications. Lecture Notes, Columbia University, 11, 2018.
R. J. Serfting. Approximation Theorems of Mathematical Statistics. John Wiley & Sons, Sept. 2009. ISBN 978-0-470-31719-8. GooolleBBooks- enUouJ4EHzQQC
J. Shao and D. Tu. The Jackknife and Bootstrap. Springer, New York, 1995.
L. Simar and P. W. Wilson. Inference by the out of n bootstrap in nonparametric frontier models. Journal of Productivity Analysis, 36:33-53, 2011.
D. Dommons-Duffin. A semidefinite program solver for the conformal bootstrap. Journal of High Energy Physics, 2015(6):1-31, 2015.
K. Singh. On the Asymptotic Accuracy of Efron's Bootstrap. The Annals of Statistics,
16):11771115, Nov. 1981. ISSN 0090-5364, 2168-8966. doi: 10.1214400//1173345666 URL /ttp://///////oooooooooooooooooo vol 10. 10.1224/20s/11763388
full
K. Singh and M. Xie. Bootstrap: statistical method. Unpublished manuscript, Rutgers University, USA. Retrieved from http://www. stat. rutgers. 1-14, 2008
pdf, pages
R. Sutton and A. G. Barto. Reinforcement learning: An introduction. MIT press, 2018
A. W. Van der Vaart. Asymptotic statistics, volume 3, Cambridge university press, 2000.
A. W. Van Der Vaart and J. A. Wellner. Weak Convergence and Empirical Processes: With Ap- plications to Statistics. Springer Series in Statistics. Springer International Publishing, Cham, 2023. ISBN http:///ww.....aa.o..o//....////
978-3-031-290400
doi: 10.
URL
https: //ttss//liik... wwppiiingeee wwtpppiww....eeee.eee....
com wt.
H. Vinod. 23 bootstrap methods: applications in econometrics. 1993.
14

---

I. Wang, N. Yang, X. Zhang, X. Huang, and F. Wei. Bootstrap your own context length. arXiv preprint 2412.. 18860, 2024.
L. Yu, W. Jiang, H. Shi, J. Yu, Z. Liu, Y. Zhang, J. T. Kwok, Z. Li, A. Weller, and W. Liu. Meta- math: Bootstrap your own mathematical questions for large language models. arXiv preprint arXiv:2309. 12284, 2023.
Zhang, Q. Wu, Y. Xu, C. Cao, Z. Du, and K. Psounis. Efficient toxic content detection by bootstrapping and distilling large language models. In Proceedings of the AAAI conference artificial intelligence, volume 38, pages 21779-21787, 2024.
Y. Zhang. S. Chakrabarty, R. Liu, A. Pugliese, and V. Subrahmanian. A new dynamically changing attack on review fraud systems and dynamically changing ensemble defense. In 2022 IEEE Indl Conf on Dependable, Autonomic and Secure Computing, Inil Conf Pervasive Intelligence and Computing, Intl Conf on Cloud and Big Data Computing, Intl Conf on Cyber Science and Technology Congress IDDSC/PiCom/CCDCC/////e CCyeeeCCCCCybeeeeeeeeccchhh pages 1-7. IEEE, 2022.
Y. Zhang, S. Chakrabarty, R. Liu, A. Pugliese, and Subrahmanian. Sockdef: A dynamically adaptive defense novel attack review fraud detection engines. IEEE Transactions Computational Social Systems, (14:))2233-56555 2023.
C. Zou, G. Yin, L. Feng, and Z. Wang. Nonparametric maximum likelihood approach to multiple change problems. The Annals of Statistics, 42(3):970-1002, June 2014. ISSN 0090-5364, 2168-8966. doi: 10.1214/1-AOSS2100 URL https::/prooeeteeuuece/
orq/ mon http:///ewe...ooo.oooooooooooooa
10. 10.1224//44A091210
15

---

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:
We provide all necessary validations
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
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 other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
See the conclusions section
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 a 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 low images are taken in low lighting. Or speech-to-text system might 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 faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
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]
16

---

Justification:
The complete (and correct) proof is provided in the supplementary part, and proof sketches are provided the main paper.
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 in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch 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
Question: 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 the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: The contribution of this paper is entirely theoretical and proof-based. No experiments required.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not 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 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 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) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c)
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., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
17

---

Does the paper provide open the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification: The contribution of this paper is entirely theoretical and proof-based. No experiments are required.
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/
wwwsnnoooooooooooooooooooooooooo www.oonooolcyyy olicy) for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is 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 run reproduce the results. See the NeurIPS code and data submission guidelines (https
cttpsccccpbbcciccc //nips cc/ publi c/ iewe///deeeeeeeeee//oo
des CCede/Codbbbm ss i onPol Piooliyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
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 to the paper) 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: [NA]
Justification: The contribution of this paper is entirely theoretical and proof-based. No experiments required.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: The contribution of this paper is entirely theoretical and proof-based. No experiments are present.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
18

---

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 run 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 (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It 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 figures symmetric error bars that would yield results that are out range (c.g. negative error rates).
If error bars 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 to reproduce the experiments?
Question:
Answer: [NA]
Justification: The contribution of this paper is entirely theoretical and proof-based. No experiments are required.
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 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 make 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
Answer: [Yes]
Justification:
The authors have read the NeurIPS Code of Ethics.
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 circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a 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: [NA]
Justification: The contribution of this paper is entirely theoretical and mathematical proof- based. There no societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
19

---

If the authors answer NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deploymentt 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 an 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 a 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 as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 MI).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The contribution of this paper is entirely thcoretical and mathematical proof-
based.
Guidelines:
The answer NA means that the paper poses no 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 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 challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: 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?
Answer: [NA]
Justification: The contribution of this paper is entirely theoretical and mathematical proof- based.
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 or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
20

---

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 of use in the package should be provided. For popular datasets, papprrsw thoode com datasete has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
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:
The contribution of this paper is entirely theoretical and mathematical proof-
based.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an 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 details about compensation (if any)?
Answer: [NA]
Justification: The contribution of this paper is entirely theoretical and mathematical proof- based.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information 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 the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, 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 institution) were obtained?
Answer: [NA]
Justification: The contribution of this paper is entirely theoretical and mathematical proof- based.
Guidelines:
21

---

The answer NA means that the paper does not involve crowdsourcing 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, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if 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:
The core theoretical development this research does not use LLMs.
Guidelines:
The answer NA means that the core method development in this research does involve LLMs as any important, original, or non non-standart components.
Please refer to our LLM policy (https: hutttp::/neuripss. htw.erripppcccc/offeeeneeee////e 2025/ LLM) for what should or should not described.
22

---

A Proof of Theorem 1
Proof. We first show that
(a (o(boot)) m
q(1 q) f2
Without losing generality, let μ be the unique median, very similarly in other cases. Let X1, , Xn be i.idd random variables with their distributions satisfying the hypothesis the theorem.
and let q = 1/2. The proof follows
Step 1. For any E > O, we first observe that
(Ixa) > ///0)) ΣE
[11 >
paa)==
E E oo.
$20
Using Borel-Cantelli lemma, X; / only finitely many times with probability 1. Therefore,
[mm)) (Xax)
a.s. O.
(A.1)
n//a
We next establish that m(
(boot)
) is uniformly integrable. In order to do that, we show
En VmlAm
(boot)
pmn)
2+8
oc. Observe that
2+6 (1 (1+ / p1+6 (Vmlp ((
Ep
Vm((ishoot)
(mm)
(boot)
Prn t) dt.
To complete the proof is now enough that the integral is finite. Consider first the case jum (boot) fly > and observe that
(vm(A!hoon
(nm) >t)
=
(boot)
>
pn +
vm
F(m) (pn + t/vm)
2
2m
F(Am + tl/m)/ > F(m)) (in + tt/mm) F(en + t/ v/mm
2
2m
(A.2)
where we recall from that notations section that F()) = D 1[X; S |//n the empirical CDF. Let
c(a:) = 1/a + 1/2. We divide the proof into two cases.
Step II (t [1, clo) m)): We begin by analysing the left hand side of the event described in eq. A.2
1 F((n) + F(Dx) F(in + 1/ vm
F( 1/vm)
2m
2m
Cm.
=:Am..
F(Rn) - F(An) + F(Pm + +t//m) F(nn + +t/ m/m
Bm.
Using [Bahadur 1966 Lemma 1], we obtain |Bm,rl S 1/Vn almost everywhere. Since m nt, it follows that
1
Bm Bm, <
almost everywhere.
Vm log
23

---

Turning Cm. and using Taylor series expansion, get that
t
Cm,n-
Vm ((m) + olt/mm
Vm f(m) vm (u- ( (n) +o
Vm f(p) + vm - (00
(A.3)
Recall that under the hypothesis of the theorem, f is continuously differentiable around the median. We first show that
Ji 1 S 1/V log
almost everywhere.
follows from the main theorem of section 2.3.2 in Serfling 2009 that
IP (lin - p1] > 8) S 2e 2n8
where 6- min (F(u + +) 1/2, F(μ e)}. Using Taylor series expansion on F, we get
5. = =f()) + O(5))
Now, set E = 1//1 n log and take sum over all n 2 1
Σ
P inn 11 > h//VVllog// n21
S
Σ n21
+ O
<
oc.
n
Now using Borel-Cantelli lemma, follows that Jūnn 14 < 1/ / log infinitely often almost
everywhere. Substituting this in eq. (A.3). get |Cm,o| - (11 /m).
Turning to Am, observe that y is the median. Therefore, F(u) = 1/2. We then get
1
F(Pn)
F(u) ((px)
2 2m
2m
1
(iin 1))(() + F(Na) F( Term
2m
where E ||-- 11-1 1p- Pal: / fnlll. It follows that f(x) < L almost everywhere for all values of n large enough for some non-random constant L.
Furthermore, since
Ain pl S 1/v logn
(A.4)
almost everywhere, it follows that
Term 1 S T./ V n log
almost everywhere for some bounded constant that depends only on and p. Combining,
Ammaa (1/mm)
We move to Term 2.
Observe from Dvoretzky-KKeeer--Woon Woliiiii--oooiiizzzsss theorer (Theorem A in Section 2.1.5 Serfling 20099 that
P
sup F(x) [()) > < Ce 22n2
We can now set E = 1/ n log similarly as before to get
IP sup F(x) - F(x))> Vn
S n
24

---

Using Borel-Cantelli lemma, it now follows that sup² [F(x) (x))
1//n log almost every-
where. This shows that Bm,ol - O (1/Vnlogn)) O (1/ vm log m ((1/v Combining all three steps, we get that
F( + t//mm) =
vm +
(A.5)
2
2m
For the sake of convenience, we denote Pr t//mm by lm- It now follows from eq. (A.2) that
{ym(p
(boot) Pm) > S
to 2 F! (tm) (t
(A.6)
for some finite real positive number & which only depends the sample X1,... Xu. and hence is constant under Pn. We now state the following lemma which is proved in the appendix
Lemma 3. Under the conditions of Theorem 7
Pa
t vm
+
t5
Fn (tm) F(tm))
vm
8a (1 E)
From equation eq.
A.2
Pr (vm(inh (hont)
(in) 1) S Pn
(-/-
t
+
Ff (1m) F((m))
Vm
mm log m
and the rest of the arguments follow.
Step III (t > c(a) m) For t > c(a) m)) and for all large m almost surely, it follows by
using equations A.5 and A.6 that,
P. m (pm (boot)
(n.) > 2)
(A.7)
< Pa (Vm (um (boot) (in) > c(a) (log m)
S Pn m (pm c(a) (log m) 1/2 m 1/2) Ffin c(ar) (log /2 m (2)
< <ccc(a (log (logm) 1/2 m 12).
2. The following lemma provides upper bound of the term in the right hand side of the previous equation.
Choose c(a:) -
Lemma 4. Under the conditions of Theorem 7
Pn ( (((m)) (Øn + c(a) (log 2/2 1/2) F(ān + c(ar (logm) m 11/2)
S -eec(a) (logm)) 1/2 m 112).
<0 (+++) (2+0))
Hence, for large m,
rm 1/441/2
116p (Vm (plboot) Pm)) f)dt O(1)
c(a) (log 1/2
Using the previous fact and eq. A.I from Step 1, we have
P. (Vm (boot) (n.)) m 1/241/a) a.s. for all large n.
Thus, we have proved our result for vm (1m This completes the proof.
(boot) p). Similar arguments handle - -mm (pm
(boot)
1.).
Next, we state the following Lemma which is proved below
Lemma 5. Let be the unique p-th quantile of a distribution F with continuous derivative f around J.. Then,
(boot) (in)) d N (o. pil-p)
v m (ji
25

---

Using this lemma, and the fact that
(6 ((lhoot)
2 a.
9(1 9(1-9) 9)
(2(14)
we have via Slutsky's theorem
m (pmm (hooot)
(ma) N N0,(0,1)
(boot)
O'
This proves our Theorem.
We now prove Lemmas and
A.1 Proof of Lemma
Proof. Recall that is constant given the sample. Using the conditional version of Markov's inequality we get that
En (!!m) (tm) F(mm))
2 ((mm (mm) - F(mm)
P.
+
V m
vm
(1/vm 1E/ mm)
vm [ra (Im) F((m))
En
(A.8)
tE)
Observe that the bootstrapped sample X is an ii.d sample from the empirical distribution F. Therefore, conditioned on the full sample mFF!"((> (x) Binomial(m, ((n)))a((m,F(x)).. Recall that
X Binomial(n. p). B[X npp 3n². Using this fact in eq. (A.8) get
Pr (Vm(ithhatt)
pn)) > 21)
3
11 g)
This completes the proof.
A.2 Proof of Lemma
Proof. Recall that we were required to bound
Pa (1m)) (pn + c(a) (log m) 1/2) F(in + c(a) (log m))/ -1/2)
S - ec((x) (log m) 1/2 m m-1)
Using the Hoeffding type bound in Lemma 3.1 of Singh [988] with
p Fn (Rnn + c(a) (log m/2 m 1/2), == 1, = ( (2 8) log m,
and that
D = ==ec(a (1+e2)) -1 ()gm))/// 1/2 1/2
Pn (((m)) (pn + c(a) (log 1/2 m 1/2) (pn + c(a) (22 m m1122
S <eec(a) (logm)1// m 1122)
< 00 (+++) (2+0)).
The rest of the proof follows.
26

---

A.3
Proof of Lemma 5
Proof. We shorthand fm = fn + t/ Vm. We begin following the steps of eq.
eq.
A.2 to get
{vm((smoot) [1] = (n( (tm) 2 p
P
m vm((F (m)) (Im) F(lm)) [tmm) (tmm)))
v (p(1 1 F(4m))
(t (fm))1 [tmm)))
By continuity correction,
F(lm)) via(a (m) (tm) (tm) [F(tm) -F F(tm)))
mm (p F((m))
Pa
2
F [tmm)(1 - 1/
/m(FFT) F(tm)) [F(tm)(1 1 12
vm (p F (((m)) [tmm)(( F (llm) 1/1
PP,
Observe that given the sample F(l") (x) ~ (mn, F(x)) and let n be large enough. Using a central limit theorem for Binomial random variables, observe that
v Vm((F (tm) F(tm)) d N(O0, 1) + R...
[F(tm)( F(fm))) 1/
where R., is remainder term that decays in probability 0 co. Let m be large enough such that Rm < E. follows that,
Vmi(Fr (m(FFmm (tm) F(tm))
mm (p F(tm))
Pn
Pn (N(0,) > t, -E)
[1 - F(tm))))/2
F F(tm)(1 (tmm)) /)
=ith
2(t E).
We will now show that
f(u)2
p(1
p)
Using method similar to the derivation in eq. (A.5).
we have
F(tm) p 171 t
t
m
p.
Therefore,
[F(L.)(1 [lmm))) m.n Vp(1 p)-
Now we address the numerator. By strong law of large numbers, F(tm) = F(tm) O,p(nn)).
Using first-order Taylor series expansion on F(tm), we have
F Fllm) F(P) (pn + +l//m- un) f(x)
p (pn t//m/mmaa 1-mmmpp 11) f(x),
where
X E (1 - 11 pinl P + 11 Pnll-
Recall from eq. (A.4) that |a pin = (1) Since is continuous around μ,, follows using continuous mapping theorem that
F(tm) 3y p tf/
27

---

and
Vm Fttm)) 3 -t((m).
Therefore.
( -) = - 1 ((-ff())/ - -c)
-p)
and
(tn 5) - ((tf(w(////))))))
+
& is arbitrary. We now use the fact that (11[(H// (LtS(///p(p1
p(1 - p)) is the CDF of a gaussian distribution with mean 0 and variance p(1 - f2) This completes the proof.
B On the Variance of the m-out-of-n Bootstrap Estimator for sample quantiles
This section is dedicated to developing the finite sample theory of the variance of the m m-out-of-n bootstrap estimators of the sample quantiles. We first write the following lemma which provides closed form expression for the variance.
Lemma The m-out-of-n bootstrap estimator for the p-th sample quantile has the closed form solution
- -x-)) Wms
(B.1)
where
pifn
Wm. = 1o m
k (1 - x)m kdx ddx h = [mp] + +1, and r = [mp]] + 1.
k
1-11//1
Therefore,
3 (bboor) m
Var,
(Vm (plhoonl Rnn))
Σ (X x(m)) Wm.
(B.2)
B.1 Proof of Lemma
Proof. Without losing generality, let p = 1/2 so that is the sample median.
Case 2q + 1: We first consider the case when 2q + for some integer q. The median is
therefore X (g+1)- As before, let Xi..... X F. The distribution of the median has the following
closed form solution
(m) [(()) [(x)) -
Ps (Xigtt) <u)
Σ -=9+1
The pdf can be obtained by differentiation. This gives us the following closed form expression for the moments.
E((i(boot))) (2q + 1)!
(q!)2 1 x² ("(F())(1-F(aa F(a))) fx) da.
(B.3)
we let = (x) and write x = F F-1(y) = (ty). then eq. B.3 becomes
E ((A((ooot)))) (2g + 1)!
[(b())] [w[1 y)]" dy.
(q!)²
Estimating the function (y) by the observed order statistics is therefore equivalent to estimating F(x) by (mm) Thus E ((p)) (o(hoo))))) is estimated by
Arm Σ X B
(B.4)
28

---

where
Bj = (2g + +1! 1)!
5//n
10 y) dy.
(g!)²
(j-1)/n
The quantity Var((pn ((ooooot) yr) therefore estimated by
Var( (p(((t) yr) = A2m Apm
Substituting the values Agn and Ain from eq. (B.4 have the given result. The case n 2q handled similarly.
The following lemma establishes the rate of convergence of the variance of the m-out-of-n bootstrap estimator of the sample quantiles.
Lemma 7. Let p be the unique p-th quantile such that F E E2((M), and ('(w) Let o(n^) for some > and E) X1) < cc. Then,
a (boot)) m
2
0² +0p 3/4 10ppm
m
B.2 Proof of Lemma 7
Proof. Let yp denote the standard normal density function,
Yn,5 = (j 1)/n and bmn (m) - k)
mYn..i Yn.))
where k [mp] + 1. The following lemma states useful expansion for the weight W. Wmj and is proved below.
Lemma 8. Assume that m x n for some X E (0, 1). There exists some constant C' > 0 such that
(mm((bma))
W W.j= nV Yn.j)
Put H(x) Fc Using Rényi's representation, let Zi,.... .,, Zn be independent mnit-mean random variables such that for all 1 S <
X H
7x
For any integer r, following a similar procedure in Hall and Martin 1988b] we define
8j sgn (r - j), moj = min(r,2),
mij max(r.j) 1, H'
EE k-1
and set
11
myy
mi1
A₁ = Σ -Zk
By
Σ 1 - k=mos
E(B))
Σ k
k=j
k=may
the latter two quantities being zero if = r.
We first consider the summation over j in eq.
B.I
The summation is divided into two parts.
29

---

Case I: Let, j| > 5n m12+-mm-1 1/2 for some > 0 and some , < A/12.
Then (()) - (r) = D2 + R1g. where
Dj = sjoB,, Rig
R2j Raj.
R2, s, -a),
and
Raj s 1 (A
ts, (A,)) dt.
Thus
(X x(m))= a²bi
- bb) - b,,²
+2, + Rij.
(B.5)
Assuming E|X|" 7 < 0C,
P([X)] S 2/2 for all j s n) = P(|XI> )
2 (1 - n "E| = O(n
Therefore, with probability tending to one as n - 30.
(X() (())) S 4n
i5n
This, combined with Lemma eq. Cym-1/2 -tep//nnteee -Cma((yssspp) C3 > O and any 0,
B.1 implies that, for some constant C2 0, Wm.j < Thus, with probability tending to one, we have that for some constant
Σ
(X
( m. S 4C2m - = =O(
1 1/2
Case II: Recall that under the hypothesis F S2(1) f is Lipschitz in a neighbourhood of so that a = (A,) (p) -1 OOnn(n)) Observe that
Σ(x6) -x(m)) = S S2 Ti + T2+ + T3.
where
S a² Σ, b2Wms m.j
S3 = 2a Σ3 b, - bb;)
Ti a² Σ, bb m.j
T2 = 2 E, D2 D2Rı,1 W m.j.
T3 E, Rig Wm..
B, Lu=may u -
bi E( E(B,)
Dj = s,aB,
R1 Roj + Raj
R2j = s,B, (A,) a.
and Rs, = s, lo (H + tsy - dA,)
Note also that B, by and
by = |j - r/r 1 + 5 2 + - 3/3
Using eq.
B.1 and the above expansion of a,
Σ 6 W m. m pn-''p-111-p) (1- + 3/2),
so that
S m -1m1p(1-- - p)f(m) + Op 3/2).
30

---

For S2, observe that
S2 =a²
u ( 1)
Σ
byWm.
u=r- on +-m-1/2
j=r-ón'-mm m-1122
r+on 1/ 1/2_1
r.66 1+ 1/2
1 (Zu -1) 1)
Σ
bywms
Then, by Lyapunov's 's central limit theorem,
m 1/2 4 NN, 2m 2/2 p))33/2 f(1)
In other words,
S = 1ppmm=//4/)1) 1/22.
We note that using eq. [.I] and for 0.
m -p)
Σ Si--ppl Wmi n2
ly (w-pl"u(111p)) 11/22
dy Op(m n2)) (,22).
p-ônom 1/2
Vv((1 3)
follows by substituting appropriate values for t that
E(Ti) =0 Σ13 li r/r r/r-2 Wm.j
= =0(m -1/2 =02m-112n=))
E|7a| 0 Σ n 2 - -1/4-11121 + (n- +1)5/2+2] Wms
=0(m =0(m-9/An11 -1),
and
B(Ts) O
Σ n ( 2( 10 3/2 (n-'l r|)8] Wm.
=(m 55/2
so that, by Chebyshev's inequality, the terms T2, T3 can be shown to satisfy:
Ti = Op(m -1/2n-), T2 = Op(m Op(m--9/n=1), ,),,, Ta = Op 5/2n )
Combining, we have,
E(x6) - - = S S1 S2 + Ti +2 +
1 p(1 -p)
+ Op(mm 33/4, 11/2) + O, -1/2n
f(1)2
+ Op(m -9/1 + +Op(m 5/2n111
0²
+ +, -3/4n
m
This completes the proof.
31

---

B.3 Proof of Lemma 8
Proof. Note that Wm.j = Li/n (k, k 1) -
m + 1), where
f=otb-1
(u+)
a a b 1
Σ
-1
is the incomplete Beta function. Without loss of generality, consider j = np + with 2 0. When 0 S S Dum (/mm-1/2(log m)1/2, for some D > O, we use Edgeworth expansion for the binomial distribution, and when > Dam 1mmm-1/2(1nn (log m) 1/2, we use Bernstein's inequality. This gives us
vmn((bma)
[k/ m
()-1)// 1)
O(n tem
n Yu (1-Yn.)
from Bernstcin' incquality
Edgeworth expansion
where Yn.j = (j- 1)/n. This completes the proof.
C Proof of Theorem 2
Proof.
The main ingredient of this proof the Edgeworth expansion of the Binomial distribution in The lemma is proved below.
Lemma 9
Lemma 9, Let X be a binomial random variable with parameters m and p. Then,
Vm(XX -P) <1 = +b()) 6v - p) v/(11 - p)
2p) ((1)H[((1 + o
1
P
(C.1)
where O(n can be bounded independently of
We shorthand Im An + to (hoot)
(boot)
To apply Lemma
we represent the event
fin) aal///t f} Binomial probability.
Continuity correction at tm= (boot)
We begin following the steps of eq.
A.2 to get
V Vm(pm (m(pphoot)
(nn)
1
S t
F(m) (tm) 2 2
Fm
(boot)
2m
Vm((F - F(lm))
v m (3 1 -
2m
(tm) - F(tm)))
[F(tm) [t(tm)))
Observe that given the sample F((m)) (x:) ~ Binomial(m, F(x)). Thus, our next step is the following continuity correction.
m (m(Pkm) F(tm))
m m-
F(lm))
Fn
2m
[1(mm) 144
F( (1 F((m 11/2/2
(mi(F!m) F(bm))
Vm ( F((m))
=P.
(C.2)
[F(tm)(1 (1..)))
F(tm) F( (tmm)) 1/122
Using complement, and Lemma
9 we now have
(m((Fm)) F(Im)) th
P.
[1(m))(1 - F((m))))
Vm (Ff [F((t) F(tm)))
F(tmm)
=1-Pa
S t
1- (tm)
H2(() tOp (1)
(1i))
(C.3)
6/m(( F(lm) (1 F(1m) 11/2
B
32

---

where Op is with respect the full sample distribution X1y...; Xa-
Expansion of (1 (F we need to find exact expressions for A and B. We use the following lemma which is proved below.
F( To find the proper Edgeworth expansion,
Lemma 10. Under the hypothesis of Theorem 2
1 to =f(() - (to)²
F(mm)
+
f (2(() + Op (m (m-11/n--1/)
2 V
2m
For convenience of notation, introduce the notation Tm follows.
lo
(lo)² ((()) + Op (m 1m11/1111/2 -12)
Tm == vm
[(1)) +
2m
Let g(x) 2x V (L/4 x² 22/4). Then observe that g(z) admits the following Taylor series expansion.
g(x) = 4x + o(x²).
Using this fact and Lemma 10 expand (1 2FF (F((t)))(((((mmll ((t (ITm) as
(1 (t.))
47m + o
(F(tm) 2)
4lo
2 (lo)² f' Op (m-1/4n-112) + Op(1/m3/2)
f(1)
vm
(C.4)
Observe that (TT) 012/m3/2). Therefore, the leading terms in the expansion arise from Tm.
Expansion of t and Hip (1%, ((())) recover the following expansion for tm
Observe that t. = (m)) Therefore, we immediately
(lo)2
f = 2to f(p)
vm f'(n) Op(m"//n-173
Let (x denote the second derivative of 6, and observe that H₂(x) - r (x)/((x). Equivalently, Hip (x))(z) (x), and di (z))))(z)) (z). Using this fact, and the fact that H2 and á are both even functions, the Taylor series expansion of Ht )ot;;) around 220 (boot) f(4) is given by
Be(-2tof(44)0
(ta)²
+ Op(m 1/4 -1/2) Op m
[1]
(C.5)
Vm"
(to)²
-a(2t (u)(tto (1))
(-2o0)))))))
1133 +pp m
mm
Substitution and Rearrangement:
We now return to eq. C33) substitute the and B.
(to)²
1- --(()))) 1 (2la
f'(n) Op(m 112)
Vm"
= 1 - & (-2to f()) + (to)
vm
2
(2ta
f())) + (mm
m
Next, we write the full expansion of B (T (L) and bound it using the following lemma which is proved below.
33

---

Lemma 11. Under the conditions of Theorem 2
g(Tm Hz2 (m (
1 m
Op
+ Op(m 1/11n1111 (0-m-/14-117
6ym
We can now collect all the terms in eq.
C.3 and use Lemma
to get
(pihhot) (boot)
Pn)
(to) Vm f (2))
Pnn
St
& (2tof(())
(boot)
6m
+ +O,
+ O Op(m 1/441
n 1/2).
Finally, observe that 1/(25(p)) Therefore, 20 (() and have,
(pm
(boot) (nn)
= (t) + (Lo)² (2)
IP,
St
6m
(boot)
m
+ Op
+ Oppmm 11/2).
This completes the proof.
Now we prove lemmas 9 10 and
11
Proof of Lemma 9
Proof. To prove Lemma we briefly introduce polygonal approximants of CDF's.
Feller's Edgeworth expansion on Lattice: To make matters concrete, we first adapt from Feller [199]] the notion of polygonal approximants on lattice. If F is CDF defined on the set of lattice points b ih, with E Z and being the span of F, then the polygonal approximant F# of F is given by
((xx)
if = 6 + (i 2) if = b + ih
F#
Following the terminology of Page 540 in Feller [1991] observe that the empirical m-out-of-n bootstrap CDF F²(m) is an m--fold-convluttinn of (i.c. it is the CDF m i.i.d samples from F). The notation in the following result is self-contained. It is due to Feller [191 (Theorem 2, Chapter XVI, Section 4).
Proposition 12 (Theorem 2 in Feller Page 540). Let X1. Xn be i.i.d. random variables
lattice with finite third moment pa and variance o². Let F be the polygonal approximant of the empirical CDF lattice with span h/ (a /T). and H2(()) (x² 1) be the second order Hermite polynomial. Then,
F# (1)=+(())
6 (1) O (
#3
A key observation is that if X is Binomial random variable with parameters and p. Then, Vm(X pp/vp(1 -p) has lattice distribution with span 1/ h//mp(t p) and
Vml(X p)
(C.6)
an event dependent solely on standardised Binomial distribution. We make two remarks in conclusion:
Theorem in Feller has (1 /n) in the statement. However, inspecting the proof reveals that the actual rate (LL/n).
The ((1/n) is independent of the term I.
The rest of the proof follows.
34

---

Proof of Lemma 10
Proof. Recall that by CLT F(.) = Ei 1[X, < (()00//))))) Let f = F² be the PDF We now have,
F(lm) = F(lm) + +Op
(By Taylor Series) F(1) + (Lin =1](1)) + (Im - -1)
+ (p((1in -1))) + +Op vn
2
(An + tothoat) - (44)
(boot)
2 + (In + (100t) -1) f(H) +
op (( 11) + Op
(C.7)
We now carefully substitute the terms. Observe that ün - - -0 Furthermore, Lemma implies
o²
(boot)
m + + n//nn11//
m
Therefore,
(bboo))
+ Op (m-1/4n-11/
vm
Substituting, we get
Pn (boot)
to
+ Op ( (m-1/4n1112)
11
vm
and
(1o)²
(Rn, + to(boot)
- 14)
+ Op
( (m-3/1n-1/3)
+ +O, (m-1/2
m
(lo)² + Op
m
1n-1//n-112
Substituting this into eq. C.7 we get
F((m)
+ to
fu)
(lx)2
((()) + Op ( (m-1/4n-112)
2 Vm
2m
This completes the proof.
Proof of Lemma
Proof. Recall from eq. C.44 that
9(Tm) (F(1m)(1
(1 2F (tm))
4to
f(())
2 2to))
f'(x) + +0pmm (00mm-3/4n1177
F 11
vm
m
Therefore,
(T... Hz2
4to
2(to) f( O, (m-mm114n-1777 1/22)
f(r) m Vm
(1o)²
(n))) + -222) + +Op (1)
vm
Ato (WHH vm
2 (to)2
(3 (())
4(to)3
O 1122 + op
35

---

Absorbing 0p(m into Op(m-1) terms now have
g m ( H2 (
Op ( m
+ Op(m 11/
6ym
This finishes the proof.
D Supplementary Results and Proofs
The following result is from Shao and Tu 1995
Proposition 13. Suppose a CDF on R and let X1, X2.... be i..dd F. Suppose O(F) is such that (()) and (x) < 1 for all x < 0. Suppose, for some 8 > 0 and for all x.
Pp(n X())) > x} + ($)
Let
Tn = n0 - X()) and T m2 (m))):
and define
(x(x) = PpLTx S < and HBoot HBoor, (x)) = P P-iTmmm S xz
Then,
(a) If = =o(n), then K Boot, m, Hn) - 0.
(b) m o ( (Tost Tog log then K Boot, m.: Hn) "
Example Let F(x) - (x/0))10 1 S 0] be the uniform distribution on [0, 0] and X(s) is the i-th order statistics. Tn = n 0 - ((m)) Orthodox bootstrap is inconsistent and m-out-of-n bootstrap
consistent for any m = o(n).
D.1
Proof of Example L
Proof. It follows from Proposition 13 that m-out-of-n bootstrap is consistent for any = o(n). We include simple proof of the inconsistency of bootstrap. Recall that the survival function of T, given by
F(x) (T, > x) = (p X(mi) > x) = P (X <0
X;
7
7/0
n8
which is the survival function of an exponential distribution with parameter Now we show that orthodox bootstrap estimator of Tú inconsistent. Let X boot be the bootstrapped maximum. Then (n)
Tooot (xpooot X(m.)
and
Ip(+) (Troot S 5x) 2 p()) (Thont 0) =1 =pp() (xbogt X(m)) p(())
(xhage <X(m))
1
a-000 1 6-6
7
D.2 Proof of Proposition I
Proof. We recall the following lemma from Ghosh et al. (984bb
Lemma 14. Let (U4)22 be sequence of random variables such that:
36

---

1. (U1)22 is light.
2. ElU;] + co, but E[U?) < 00 for all
Then,
Var(Un) + oo.
Using this lemma, it is sufficient to show that En (imm conditioned on sample XI,..., Xn can written as
(boot)
pm An)² ase 0o. The distribution of (boot)
X(n)
with probability
m
X(n-1)
2 with probability
(boot) P
m
X(1)
with probability
Observe that
En (bbboo)) - -mn)²² n (X(x) 12n)22
Recall that An -.= 0. Thus 3 3no 2 such that P( 0) 1. Letting no we get
X2 (n) En (ilhooo))) 12,)2 2
almost everywhere
n
is therefore sufficient to show that X² X2n//1 a.s.
Do. Let x > O be any positive real number. Then
X2
(n)
= IPn (X(r) S v
IP,
< x
m
Pn (X1 S mmmm
F(Vanm))
log(an
eep
log
log(anm)
Using the Mclaurin expansion of log(1 x), we get
exp n nlog (
log(an"") ))
exp
n k=1
(log (nn
exp
log(rn"
Therefore,
X2
IPn
S x < 00
n
m=0
and it follows using Borel-Cantelll lemma that X2 / a.e oo. Therefore,
E,, (a(boo)) p2,)2 n
(X(n) - A2.)2 a.e, 0o
which completes the proof.
37

---

D.3
Proof of Corollary |
Proof. For every t E define
Vm(uum (boot) (mn)
Rm (t) == Pn
St) 22 (t). Fm (boot)
The expansion in Theorem gives
(l0)2 vm
l0s(1)
Run (1)
('()) 1
Vp(11 pp) + +Op (m +Op (m nn-11/4n11//
Recall that
Φ ( lo LaI(w)]
Vp((1 (exp)
1 [_022(113²
p(1 p)
Since the function g()) (((t) with 5 = o (())/ vp(1 p) satisfies
sup tER
[9(() < x
(because e bounded for any positive constant c), there exists finite constant Co (free of m, n)) such that
ef?
sup [1)(1)] Co (f'( mi 1/1 Op (m + Op (m-mmm1// (m-1/4n11/2) tER
Because m = o(n^) with E (0, 1), we have m 1/4n 1/2 = o (m (m2). Hence the leading term m 1/2 dominates the remainder terms, and we conclude
sup Rm. Op (m-1/2) tek
which completes the proof.
E Proof of the DKW-inequality for Markov Chains
E.1 On VC-dimensions
The notion of VC class is powerful because it covers many interesting classes of functions and ensures suitable properties on the Rademacher complexity. The function F an envelope for class F if [x)] < F(z) for all E and f E F. For metric space (F, d), the covering number the minimal number of balls of size E needed to cover F. The metric that we use here is the L2(Q)-norm denoted by [|-le,(Q) and given by ( = {ʃ f22
(E, F. d)
Definition A countable class F of measurable functions E - is said to be of VC-rype (or Vapnik- Chervonenkis type) for an envelope F' and admissible characteristic (C, v) (positive constants) such that C > (3)e)" and v 2 1, if for all probability measure on (E,E) with [| < oo and every 0 < <
N' (=](F))ra)Q)) F, (l-l)z(()) S -
Let Fs (1f- < t) 8} be the set of all half-interval functions. Then, we have the following lemma.
Lemma 15. Fi0.1 Q is VC with constant envelope and admissible charactaristic (C, 2) for some universal constant C > 4e.
Next, we introduce some terminology. We define the Orcliz norm of random variable X as
|| argmin(A > 0 E (X/1 < 1). We define т, min [|r(2) and assume that T, x..
We now present the following lemma whose proof can be found in Section E.4
38

---

Lemma 16. Let x1..... Xn be Markov chain with stationary distribution F, and define
Z == sup Σ (f(x.) - Ep [f(x)))
SEFiounn i=1
Then, for some universal constant K > O,
BA[TA]
12
++ (R(FF..1 exp
min
K
To log n
where, for any L EA and C2 2
I VEA(TA]
R(Fo.unno) = 2(EA TA E, [TAI) + L Log
n.All2llog log
VAATT
+ eeexp(LLX/2 Cx.
We now present the following proposition whose proof can be found Section E.3 Proposition 17. Let XI...., be a Markov chain with stationary distribution F, and define
;: sup /EFia
Σ
(f(X)) EF ((()))
Then, for some universal constant K >> 0, and all tl
(- C(T, [.
IP > S CT, exp
(E.1)
logn n
where, constants C(T, A), (T, A) depend only on EA[T2]. [T). Tor and X.
The following corollary will be useful. It follows easily from Proposition 17 by setting t
and simple use of Borel-Cantelli lemma, and is therefore omitted.
Corollary 4. Let Zn == su [F()) P())). Then, Zn > 22/(C(T, A)n) finitely often almost everywhere.
E.2 Proofs
Proof of Lemma 15
Proof. We provide proof for completeness. We begin this proof with some requisite definitions.
Given a class of indicator functions J defined on X. and set ( In} x", we first define
F(1 )) := ((f(x)),......... f(E,),,)),,,()) E :
The growth functionn of the F is then defined as
max (n(F)= (m1.....))
[((2),..., 2n))
The VC-dimension of F is then defined as
VC(F) argmax (n An(F) 2n}
We will now show that VC(F ())) = 1. Let f An be any ordered sample. That is, Ii < T2 <...., < Fn- For any E 00, 1]n observe that (1 [ < 1f, < t]...., 1 [x, < t)) has the form (1, 1, 1, 1,.,,,,.,,, 1,0,0,,....... 0). In particular, the values of Flo.1] (( (.1,..., ).,) }) has to
be within the following set
(0,0, 0, 0).
(1,0,0. 0).
(1,1,0, 0).
(1,1, 1,1,,..... .,,.,)
39

---

Therefore (o + 1. This implies that
VC(Fio.nng) = argmax An (F [o.1 2")
argmax n 1 1=2" )
Now, using standard results of covering number bounds, (Theorem 7.8 of Sen 2018 see also Theorem 2.6.4 Van der Vaart 2000 we have the following result. For some universal constant C>0
. (e||F]l Foonne (l-l)2(()) s SCx CCXCCFFonna( (
2VC(Fo.uno)
where (i) follows by substituting (C This completes the proof.
E.3 Proof of Proposition 17
Proof. Proof of Proposition 17 Since there is always a rational number between any two real numbers, it holds almost everywhere that
sup fET
Σ (J(X.) - Er (((X))
<
sup JeFo no
Σ (J(X)) - EF (/(x)) +
Therefore,
P(nZ > nt. + (R( (R(Flo)n)))) SP
sup nE i=1
Σ
-
> nt + (R(FFRRFFFFFFoo -
t > 3/n by hypothesis. Therefore nt 2 2 1 and it follows using Lemma 16 that the right hand side of the previous equation is bounded above by
ET(TA] min
(nt - 2) (nt 2)
cxp
x
T log
By setting L. = (2/2) (2)() and observing that under Assumption get
1 (EM), 1/(2Cx) < 1 we
B. (TA)) C log(n) log
log((n)
2log(n)/A
R(Fio.un 2((AA(TT] $
nBal72] log
EAlTT
Observe that / A 1. Now, with constant C(T, A) depending and [A((2)) and E. [TA] we have with some standard manipulations
R(Fo.unn)) s C(T, A) log
Then, with Rs = C(T, A) VVllono n, we have
[A(TA] K
(nt - 2) (nt 2)
T logn ))
P(nZ nt KRr)) exp
min
[
Now dividing both sides of by n and trivially upper bounding by 2K, we have for some universal constant K > 0, and for all t 3/n
EA(TA]
(nl - 2)
(nt (nl-2) 2)
(ZZ > t + KR ///n//) /n) < exp
min
(E.2)
K
AEA
T log
40

---

where, for some constant C(T, A) depending only EA([TA) B [T
Rn = C(T, A) logn.
Next, observe that
P F > 1) = (Z BZ BZ)
Since EZ < Rn/nn = O( (olyoogro n n), there exists constant (T, A) > 3/n such that
t 1-EZ---C(T,,
Then,
BA[TA]
(n(t-C' A)) 2) (n(t C'T, AJ)
2 1)
P(Z >) t) S exp
min
K
nEATT.
Tō log
We now make 2 cases.
Case I: When / (T, A), 1- ((T;;))-2/) 1/2 and hence
|EAlTA] K
(nt 2)
To log n 1)
nt/2
P(Z 1) exp
n.R. A [T
Case II: When 0 <t (C'(T, (T, A), there exists a large enough constant C* C*(T, A) such that
EA[TA]
(nt/2)2
T log 1)
nt/2
P(Z > t) S C+ (T, X)
exp
min
K
nBAlTă
therefore follows that, for some large enough constant C(T, A) and for all
C", EA[TA]
(nt/2)²
Jo log n })
nt/2
min
K
nBATTH
follows that
EA(TA]
nEA[T2] TJ log })
(nt//2)²
nt/2
CT exp
min
K
EA[TA] n min(l,
1 EA(T
73 1)
< <C A) exp
min
K
4 logg
Define
EA[TA]
C(T,
min
4K
E
To
It now follows that, for all > 0
C(T, A)n min {2)
P(Z > 1)
C* A) exp
log n
E.4 Proof of Lemma 16
Proof. Proof of Lemma 16 To prove this lemma, use Lemma 15 in conjunction with theorems 5, and 6 Bertai and Portier (009) (see also theorem 7 A'ddmczakk [2008).
Observe from part (ii) of theorem 4 Bertail and Portier (009 that under Assumption 1 the Rademacher complexity R(F (as defined in definition Bertail and Portier (2019) for any
class of VC functions with constant envelope U and characteristic (Ci,v) can be upper bounded
CLUU
CILU
R(Fo..nno) S LLU LLUlog log a' + V uno' log o'
+ nU exp--L\/2)C,
(E.3)
41

---

where (d')² is any number such that
sup
EA
Σ f(xi)
5(09)
and L is any number such that 0 < LU.
Recall from Lemma 15 that the class of all half intervals on rationals Fio.1] are VC with constant
envelope U and characteristic (C, 2) for some universal constant C. Substituting this in eq. EE3), we get
CL
CL + 2no log of + mexpp(112/2CCx
R(Foo.nno)) SC 2L. log of
Next, observe that f()) are indicators of half-intervals. Hence f()) and
2
Σ
TA
S ST¹-
Therefore, choosing (a')² EAlT2l suffices and we get
CL
CL VEATTA
R(Fio.)no)) < C log
2n
EA BA
log
+ =exp(-IX\/)CA.
Finally, substituting this into theorem 5 Bertail and Portier 2019 and trivially substituting log(xCC) Cog((z) for all large enough constant C, we arrive at the required bound
<
L
L
R(Fo.uno) 2(EA|TAl ET(TA]) + L Log
nEAlTāl log
VEATTÄ
VEA(TA)
+ nexx(_LA/22) Cx.
Now, using the exponential tail bound for the suprema additive functions of regenerative Markov chains (theorem 6 in Bertail and Portier [2019), or theorem 7 in Adamczak (2088) ). we arrive at the conclusion.
F
Proof of Theorem 3
Proof. As before, first show that
q(1 q) (²(
( (boot) m
Without losing generality, let be the unique median, let and let 1/2. The proof follows very similarly in other cases. Let X1, X2,..., X, be a sample from a Markov chain satisfying Assumption 1 and recall (for instance from Remark 5 Bertail and Portier (019 that it is equivalent assuming geometric ergodicity of the Markov chain. Furthermore, let {XT be another Markov chain with the same transition density starting from the stationary distribution F.
Next recall the well-known fact (see for instance [Jones] 2004 pg. 304]. See also Meyn and Tweedie (2022) that for geometrically ergodic Markov chain, the coupling time T (formally defined in eq. (ET)) is finite a.e. In other words, almost everywhere,
T = inf {n Xn. =X}} < M.
(F.I)
42

---

Step 1. For any E >> O, we first observe that
(Ixil 2//55)
P (IX 2//08 nT> > 1)+ Σ
P
(
>
11/ no si)
si)
120
P (Ixi) > 8
T si) + P(
-
120
120
Σ
P (IX| > p/1 M nrsi) + Σ
(T
120
120
$
(iI 22/aE) + Σ
PP (T >1)
120
P (xx]i 2
+ Σ
(T i)
120
120
$ Er |X|
+
where (i) follows by coupling property, (it) follows since T < M almost everywhere for some M, and the other inequalities are trivial.
Now, using Borel-Cantelli lemma, X, > f1/0g only finitely many times with probability 1. Therefore,
X ((m) + +X(x))
a.s. O.
(F.2)
2/a
We next establish that m mpm (plloot) have
) uniformly integrable. As in the proof of Theorem
we
220
01) /0² (T (Vmlishon)) Pn 1) dl
En Vm(jithoot) (mx)
(F.3)
with
(Vm(fihhan) -in)) >1}
F(jn + +l/m)) > F(m) (fin + +L/mm) F(pm + 1/ 1/vm)
2m
(F.4)
Let c(a) = 1/0 + 1/2. As before, we divide the proof into two cases.
Step 11 (f E Vlg We begin by analysing the left hand side of the event described in eq.
1 F(ūn) + F(Dn) F(in + 1/ v
F(A, + 1/vmm
2 2m
2m
Cm.
=:Am.n
+ F(An) - F(An) + F(Pm + +t/ F(nn + t/mm)
Bm.
We begin with Bm,,. Using triangle inequality, we have,
Bm,al & P((n)) F(ān)) + F( + +l//m) - Flin + 1//m))-
Using Corollary 4 Awicee, we obtain Bm,il I /8/(C(r, X)n) almost everywhere. Since m S n, follows that
2
B BBm 5
almost everywhere.
/2mCC(TT))
43

---

Turning Cm. and using Taylor series expansion, get that
Cm,nn
vm f(a)) + o(t/m)
f(1) + vm (u Pn) (n) (1)+ +o(t/m).
Vm f()) ( +
(F.5)
Recall that under the hypothesis of the theorem, f is continuously differentiable around the median. Using [Bertail and Portier 2019 Proposition 11], we have that
(v log log
lin - 1l S OO
almost everywhere.
71
Turning to Am,. observe that ja is the median. Therefore, F(N) = 1/2. We get similarly as before,
1
1
F((n))
F(u) F((r))
2 2m
2m
1
(jin 1)J()) + F(An) F(jm)
2m
Temm
Term
where X E [M- 11- Pnl, 11 pmnl]
To upper bound Term observe that from the hypothesis of the Theorem that f is bounded and continuous around Since
x Ia 1 1n-1p--aae Pma, 11 p.ll]
it follows that f(x) < L almost every for all values of n large enough for some non-random constant L. Since [Bertail and Portier
2019, Proposition 11], we have that
(V
log log
iin 14| S Op
almost everywhere
(F.6)
n
it follows that
(V log log n
Term $ OO
almost everywhere. follows from Corollary that Term < O (L/vVn))
Combining,
(V log log n
Am, S SOp
Combining all three steps, we get that
1 F(nn + t/Vm) Vm
(F.7)
2m
For the sake of convenience, denote fin 1/vmi by lm- It now follows from eq. (R4) that
{ [Vm (boot) (mn) >t} C
t
(r(m))(t
(tm))
(F.8)
Vm
Vm
for finite real positive number & which only depends on the sample X1, X,, and hence is constant under P,,- Recall that, X²¹ 1.ddd F. By using Lemma we have from equation eq. F.4
E
IP. (Vm( (in)) > 1) 5 Pr
2 ((m) p(())(tm)) (tm) F(t.n)
+
m
m Imlogg logm m
3
[1( E)
44

---

Substituting this into eq.
have shown that the integral is finite.
Step III (t > y m For t > e(a) (logm)422 and for all large m almost surely, it follows by
using equations F.7 and F8 that,
Pa Pa (u (nn t)
(F.9)
Pa (y (olhoot) pn)) > c(a) (logm)²/2)
< Pn
pfm) ( + c(a) ml)gm)* m 1/2) - F (a. + c(a) (log m2" m 1/-1//3-- $ - -e(aa
log m
m
Choose c(a) = 1/2 the rest follows similarly before. Hence, for large m,
Mut1/a
11+6p (Vm (boot) Pa)) > t)dt = O(1) a.s.
c(a) (log m))
Using the previous fact and eq.
F.2
from Step 1, we have
Fu (vm (1m
(boot)
> m m21/211/a)= a.s. for all large n.
Thus, we have proved our result for vm (Jim This completes the proof.
(boot)
n). Similar arguments handle -mm (um
(boot)
11).
Next, we state the following Lemma which is proved below
Lemma 18. Let be the unique p-th quantile of Markov chuin satisfying Assumption 7 Then,
(p!boot) Vm (ith
(..)) - N (o,
p(l-p) P(N)
Using this lemma, and the fact that
(2(hoot) )
2 a.s. q(1 -9) ②)
(2(1)
have via Slutsky's theorem
vm (boot) (km) N0,10,,)
(boot)
This proves Theorem
We now prove Lemma 18
F11 Proof of Lemma 18
Proof. As before, we shorthand fm = An + t/ /m and begin following the steps of eq. A.2 to get
Vm((F (lm) F(tm)) [F(tm) - F(tm))) Ft
Vm (p F(lm))
P,A Pr(ym(ppho (boot) - (.,)) < t] P.,
(1- (1
(t. 1)
=:t"
Observe that given the sample F((m) (x) ~ Binomial(m, F(x)) and let n be large enough. Using a central limit theorem for Binomial random variables, observe that
Vml F(m)) (Im) F(Lm)) L N/(0, + R.. [F(tm)(1 F(
where R.,. is remainder term that decays in probability to 0 as
45

---

Let m be large enough such that R. 8. It follows that,
/m F( (tmm) F(tm)) FL - F(tm)))l/2
v (p F(bm)) [ [Fmm)(1 (t 1)1
Pn
Pn (V(0,)) > im -
Φ E).
We will now show that
f(1)2
p(1 - p)
Using method similar to the derivation in eq.
F.7
we have
m7
t
Ftmm) = p
mm
Vm
m
p
and,
[F(tm)(1 F(t m.n vp(1 p).
Now we address the numerator. Since a geometrically ergodic Markov chain also ergodic, we have by Birkhoff's ' ergodic theorem (Dasgupta, 2008 Theorem 3.4), that
(tmm) = (tmm) + Op(1/n).
Using first-order Taylor series expansion Fllm), we have
F F( F(u) (1% + tt/m - 14) f(x) -pt (pn t/ym 11) f(x),
where
x [p 11--10 1111p- Rul. p + 1p Anl].
Recall from eq. (F.6) that |ب Pnl (1()). Since f is continuous around μ,, it follows using continuous mapping theorem that
F(tm) 3 p tf(1)
and
vm (p- F(tma) 3 -tf(m)-
Therefore,
(t -) = V(-t -3)
and
1 - (tt 5) = ((tf(4)) //100//p11111 p(1 +
e is arbitrary. We now use the fact that (LI[(H)/ / p(1 1p(1-)) the CDF of a gaussian distribution with mean and variance y(1 f (p)). This completes the proof.
L
G Proof of Corollaries
G.1 Proof of Corollary
We only need to show that the MH algorithm satisfies Assumption 0 The proof analogous to the proof of Proposition 9 in Bertail and Portier 2019). and we provide it for completion.
46

---

Proposition 19 (Uniform minorisation). Let P be Markov transition kernel on (R., B(R4)) and let be a positive measure whose support
E = supp(())
bounded, convex, and has non-emply interior. Assume that there exists & such that for every
E E
P(x, B((e)) Φ(dy).
Then there are conslants C 0 and 2 foror which
(" A) 2 C (A),
Vr B
(G.1)
Proof. The argument is split into four parts.
Fix 1 17. There is constant such that for all 2, E
/ (B(t)((F (B( ((dx)) 2 e clB(a.rr/4))9))
(G.2)
Indeed, if y & B(x, + 7/4) the hight-hand side vanishes, so only the case y E B(x, 7 + 7/4) matters. Since E is convex, can select point the segment connecting and y such that (mm./44) C B(x, m) n Byy y); this yields the bound with c: inf $ (B(m,n// > 0.
Iterating G.2 shows that for each 2 there is C, satisfying
(n(s)(()) (z)) ... () (In-1) In(re) b(dx)) ((dx.)
2 Cn (ann)((t////))))))
Choose large that c(1 + n/4) exceeds u.P. ||u w/|- Then B(x, <(1 + n/4)) contains E for every x E E, and the integral in Step 2 is bounded below by positive constant Cn that does not depend
Combining the minorisation assumption on with the integral lower bound from Step yiclds, for any E and measurable A E,
(Z())) 1BBELLLL - (a()) ((dx)) ((dz)))(dy) 2 C, 4(A).
pd x A) 2
Setting C,, completes the proof.
Applying Proposition to the random-walk Metropolis -asttings (MH) kernel yields exponential moment bounds, summarised below.
Proposition 20. Let be bounded density supported by bounded, convex set F c Rd with non-empty interior. Assume the proposal density q of the random walk MH algorithm satisfies
g(z,y) v) b (()
Vx.yER
for some constants b, O. Then the resulting MH chain aperiodic, π n-irreducible, and enjoys the exponential moment property (EM).
Proof. Because the acceptance probability obeys p(x, v) 2 क (V)) ||T|||/// the MH kernel satisfies
P(x, dy) 2 || [ (v) (v) dy:
E.
Thus every ball of radius e/ 2 is m-amall in the sense of Roberts and Tweedie 1996 which implies aperiodicity. Applying Proposition 19 with (dyy) = - xy)) dy gives minorisation (G.
Theorem 16.0.2 of Meyn and Tweedie 2012) then verifies Assumption
47

---

G.2 Proof of Corollary
Proof. We first show that X; is geometrically ergodic. We will show that it is o-mixing, which implies geometric ergodicity (Bradley 2005
Recall from Bradley 2005 Eq. 1.2] the definition of the a- and d-mixing coefficients os Pi, and
from Bradley 2005 Eq. [.11] that aij S @ij. so suffices to bound Øi.j
Introduce the weak-mixing coefficients
8 =
sup 61.02
P E X; s1) Pr(X, E | =2) llvv
for 1 Si si<j n. By Banerjee et al. 22055 Lemma 1J, Oi.j S 0i.j so bounding 0z, is enough.
Let (.,,,.) be the (time- ) Markov kernel at step and pc(x, its density w.r.t. Lebesgue measure on the state space [0, 1]. The chain is assumed to satisfy a Doeblin minorisation:
inf (z(, () 2 VI E [0, 1], Vi21. 1. =E(O.1]
(G.3)
For Markov kernel P, its Dobrushin coefficient is
inf 8(P) = (0.1) [0.1]
min(p(as t), p(22, 8)} dt.
[0.1]
Hajnal's theorem for products of stochastic matrices
(Hajnal and Bartlett 1958 Theorem 2] gives
j-1
O S [(pp))
p=
Using the minorisation G.3)
min (on(po(a, 1), Pp {)} dt 2 / xedt n,
0.1]
so ((pp) s for every p. Hence
On S (1 -))
Combining the above incqualities yields
0G S Øi S 0.s < (1 (1-x)
Thus, X, geometrically ergodic. Since r is one-one onto, it is invertible. Therefore, r; is also geometrically ergodic. Therefore, this satisfies Assumption T The differentiability assumption can be easily seen to hold. The rest of the proof follows.
H Simulations
We conducted Monte Carlo experiments with sample sizes (10000, 20000, 50000). For each n, examined three block sizes log n, n 1/3 and Vn. Following the procedure described in Section (formula for the bootstrap statistic) and Equation (B.2) (closed-form variance estimate), we repeatedly evaluated the test statistic T to approximate its sampling distribution.
Three data- data- settraagnnaaingg mechanisms were considered:
1. i.i.d. Gaussian observations:
2. Observations obtained by reflecting simple random walk onto the interval [-1, 1]:
3. Markov chain generated by the Random-Wai Hastings (RWMH) algorithm (see Section 5) employing a Laplace proposal distribution on a standard normal target density.
For each configuration, we measured the discrepancy between the empirical distribution of 7 and the standard normal distribution using the Kolmogorov-Smirov (KS) distance.
48

---

Table 1: Results for n = 10,000
m
m value
Case
Mean (
Var(T)
KS
log (n))
9
Gaussian
-0.030959
0.992566
0.033
log m
9
Reflected RW
0.041787
0.784624
0.069
log(n)
9
MH RW
0.005385
0.937350
0.057
n 1/3
21
Gaussian
-0.053800
1.114615
0.028
n 1/3
21
Reflected RW
-0.006052
0.965366
0.040
n 1/3
21
MH RW
-0.045641
0.862029
0.028
Vn
100
Gaussian
-0.037565
1.059072
0.039
100
Reflected RW
0.021268
0.905786
0.069
Vn
100
MH RW
-0.081919
0.978142
0.061
Table 2: Results for 20,000
value
Case
Mean(7")
Var(7"
KS
log m
9
Gaussian
-0.035324
0.975723
0.033
log m
9
Reflected RW
0.015931
0.771220
0.052
log(n)
9
MH RW
-0.003805
0.977506
0.033
n 1/3
27
Gaussian
-0.025948
0.976584
0.028
n 1/3
27
Reflected RW
-0.011587
0.956381
0.027
1/3
27
MH RW
0.006103
0.970455
0.032
Vn
141
Gaussian
0.048491
0.972170
0.049
Vn
141
Reflected RW
0.027213
1.045555
0.032
Vn
141
MH RW
0.025495
0.967099
0.040
Table 3: Results for 50,000
m
YT value
Case
Mean(7))
Var(7"
KS
log
10
Gaussian
0.023658
0.920129
0.039
log(n
10
Reflected RW
0.024419
0.794373
0.044
log(n)
10
MH RW
0.01 1901
0.860669
0.025
n 1/3
36
Gaussian
-0.001047
0.959031
0.028
1/3
36
Reflected RW
0.001399
0.872152
0.027
1/3
36
MH RW
0.007086
0.971482
0.022
Vn
223
Gaussian
-0.051904
1.046060
0,051
223
Reflected RW
-0.028429
0.957545
0.028
223
MH RW
-0.021154
0.967758
0.023
49


Reviews:
[{"review_id": "pJdYNFVi3A", "reviewer": "Reviewer_nMYW", "summary": "The paper derives convergence guarantees for the m-out-of-n bootstrap estimator by developing a second–order theory for Studentized m-out-of-n bootstrap quantiles under relatively weak moment assumptions. Specifically, they prove variance consistency, a central-limit theorem, an exact O(m^{−1/2}) Edgeworth expansion that delivers exact convergence rates, and a matching Berry–Esseen bound on the bootstrap approximation error of bootstrap quantiles. As a by-product, their variance formula correct an error of Cheung and Lee [2005]. Finally, they extend the analysis to regenerative Markov chains.", "questions": "I have no questions for the authors.", "limitations": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: The authors develop the asymptotic theory of the m-out-of-n bootstrap quantile estimator, which is a broadly used method that somehow lacks rigorous soundness guarantees. They also extend beyond the i.i.d. case to regenerative Markov chains and provide useful applications. The presentation is clear and the proof sketches are intuitive and capture the gist of the proofs.\nWeaknesses: There are some mild assumptions and only stationary process are considered, but I don't consider this a problem but an intersting direction for future works.", "was_revised": true, "final_justification": "I have read the authors extensive replies for all the reviewers and feel very confident in keeping my score.", "rebuttal": "We deeply appreciate your positive review and your accurate summarization. We hope that the rigorous theoretical guarantees, the correction of key prior work, and the clear exposition across both i.i.d. and regenerative Markov settings underscore the paper’s strong impact and align with the highest possible recommendation."}, {"review_id": "LeoxbPaSmh", "reviewer": "Reviewer_kcDW", "summary": "The authors provide asymptotic normality, Edgeworth expansion and Berry-Esseen theorems for the studentized m-out-of-n bootstrap estimate of the distribution of the estimate of the q-th quantile of a scalar distribution with either iid data or markov chain data, from a markov chain that satisfies a regenerative condition.\n\nThe results fill a gap in the theoretical literature on understanding the consistency of the m-out-of-n bootstrap for quantiles.", "questions": "1. How do you formally define the hat{sigma}_m^(boot) and how do you compute it in practice?\n2. Why are the main theorem statements only about asymptotic normality of the bootstrap statistic? How does one translate that into a confidence interval for the population quantile mu?  If you only care about the sample quantile, then why do you need the m out of n bootstrap? Why not just compute the sample quantile?\n3. Why do you only analyze the sample quantile and not a broader class of estimands? What is particular to the sample quantile in your theorems (apart from the limit variance characterization)?\n4. In proposition 1, why does the statement that E[(mu_m^boot - mu_n)^2] -> \\infty, imply that \"the bootstrap estimator of the variance of the sample quantile is inconsistent\"?? Here you just show that the bootstrap estimate does not converge to the sample estimate. Why do you mention \"the variance of the sample quantile\"? In this regime of the proposition, how do we know that the variance of the sample quantile does not go to infinity too?\n5. What is the technical difference between your Theorem 2 and the results of Hall and Martin 1991\n6. What do you mean with the jargon \"parameter-free\" throughout the paper. You never spell it out. Please be more specific, as parameter free can mean many different things across sub-communities.\n7. Can you expand a bit more around your comment on the fact that the tsecond order term is an even polynomial on page 6 and hence this leads to parameter free two sided tests? This is a very cryptic comment.\n8. What is technically different between median (for which many more results in prior works exist) and sample quantiles?\n9. Shouldn't corollary 3 be about confidence intervals for mu and not mu_n?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. The authors provide rigorous finite sample guarantees for the m-out-of-n bootstrap for quantiles\n2. The problem is quite fundamental and basic and has a long history. Hence, they are filling missing gaps to a well-established literature.\n3. Their result is extended to non-iid data which has applications in MCMC sampling (of interest to the neurips community)\n\nWeaknesses:\n1. The paper is poorly written and uses a lot of jargon at many places without explanation and for no real reason. For instance:\n1a. It is not even clear as to what you really want to estimate? Do you want to estimate the variance of hat{mu}_n? Do you want a confidence interval for $mu$? Do you want a confidence interval for $\\hat{mu}_n$? (and if the latter then why? why can't you just compute hat{mu}_n)? Do you want to approximate the whole distribution of \\hat{mu}_n?\n1b. You have statements of the form: The studentized estimator of mu is then Tn = sqrt{n} (hat{mu}_n - mu) / hat{sigma}_n. Tn is not an estimator of mu. It even involves mu on the right hand side. So this sentence is just weird. This to the least can be called a studentized statistic (which is an oracle statistic that is not computable). Similarly, you call Tm(mu) the m-out-of-n bootstrap estimator of the sample quantile. But this is not an estimator again of the sample quantile. hat{mu}_m^{boot} is an estimator of the sample quantile and hat{mu}_n is an estimator of the population quantile. \n1c. Just say that hat{mu}_n is the sample quantile and hat{mu} is the population quantile.\n1d. The prior work section is too vague and sometimes irrelevant (e.g. the LLM alignment comment). This paper is solving a very specific problem in a very vast and well established literature. With the current prior work section it is very hard to judge whether the paper makes a novel contribution in the literature and exactly what it is. Why doesn't the quantile fall into the many statistics for which consistency of m-out-of-n bootstrap confidence intervals has been established (e.g. it was not at all clear what the technical comparison is of your work and that of Hall and Martin 1991. Or of the work of Stephen Lee; \"on a class of m-out-of-n bootstrap confidence intervals\" (JRSSB) \"on  m-out-of-n bootstrapping for non-standard m-estimation with nuisance parameters).\n\n2. The method applies only to a very particular estimand, the quantile of a scalar random variable. Typically m-out-of-n bootstrap approaches are used for much more complex objects, such as outputs of an M-estimation or model selection procedure, or other irregular estimands. It is not clear why would one use the m-out-of-n bootstrap for constructing confidence intervals for a quantile? Unless the whole point of the paper is purely computational and about being able to construct the sample quantile among n samples using only sample quantile calculations among m << n samples. If this is the case, the paper is written in a very confusing manner and this point does not come across at all.\n\n3. Even though the authors claim that their analysis has implications for MCMC sampling, no realistic implication was provided and no implementation and experiments on how their results have practical consequences was given.", "was_revised": true, "final_justification": "The authors have addressed my concerns in their rebuttal", "rebuttal": "We thank the reviewer for their careful review and meticulous assessment. We provide responses to their questions and weaknesses as below.\n\n## Weaknesses\n\n1a. We refer to Dasgupta [2008, Ch. 29], which explains the idea of using replicated samples to estimate the distribution of a statistic. Since we typically get only one dataset, bootstrap samples from the empirical CDF serve as proxies for such replicates. Revisiting the paper, we agree the need to make this immediately apparent in the introduction, and believe it can be achieved by rewording line 22 to be more specific, as\n\n> The bootstrap—first proposed by Efron [1979]—quickly became the go-to method for sampling from, and testing about, the distribution of a statistic. \n\n1b.  We will reword  $T_n$ to Studentized ``statistic\" in the revision. \n\n1c. We would like to gently point out that the general consensus in Statistics is Greek alphabets (like $\\mu,\\sigma$ etc.) stand for parameters and their hatted version (like $\\hat \\mu,\\hat\\sigma$ etc.) stand for the estimates.\n\n1d. We respectfully disagree with the assertion that the manuscript is “poorly written”. Nevertheless, we will revise the literature review to remove any residual vague statements. We gently remind the reviewer that the development of the m-out-of-n bootstrap leading to our work is outlined comprehensively in the Introduction (lines 22, 26, 46, 49, 50). The limitations of earlier work, motivating our results in the i.i.d. setting and their subsequent extension to Markov chains are discussed in lines 53–62. Additionally, the shortcomings of the most directly relevant prior work are addressed in lines 63–66 and further elaborated in Section 4.2. We address the limitations in our current work in section 6 (see also the revision according to suggestions of reviewer gjZu). We would like to respectfully highlight the fact that reviewer gHZF highlighted the paper’s clarity as a strength, stating:\n\n>The comparison to previous literature is very precise, and I found it very clear how this work compared with previous papers in this space.\n\nThat said, we would be glad to consider any specific suggestions for improvement during the discussion period. For the other part, please see the response to Question 5.\n\n **On M-estimation:** The benefits of $m$-out-of-$n$ has by now been well studied in the literature, and we would like to point the reviewer towards the citations in line 107 of our paper (particularly highlighting Chapter 22 in Dasgupta [2008]). We divide the rest of our responses up into two distinct parts:\n\nThe M-estimator is indeed an interesting use case for bootstrapping, however we would also like to point out that the full generality of this problem is outside the scope of the current work. That being said, there are many M-estimators which end up producing quantiles when maximised like $L_2$-shrinkage problems [Chapter 1, Hall, 2013] (which leads to the median) or absolute-deviation loss functions. On the other hand, as the reviewer suggests, if the M-estimator depends on some function of the quantiles one would use existing theory (like delta-method, or CLT for M-estimates [Theorem 5.21, Van der Vaart, 1998]) to derive asymptotic normality. While the most general cases are interesting in their own rights, we found that even this basic case (Studentized quantiles) lacked rigorous theoretical guarantees, something which this paper aims to address.\n\nFor the second question, we take this opportunity to gently remind the reviewer that our objective in this paper (as we mentioned in line 116, line 142, etc.) was to attack one specific corner of this problem which lay largely unanswered: the theoretical properties of the **Studentized** bootstrapping of the sample quantiles for IID and regenerative Markov chains. While we agree that it is also interesting in the context of M-estimation, we would like to point out that testing for the quantile is quite prominent even in \"banal\" statistical tasks like MCMC, where one might want to test for the sample median of an MCMC algorithm. But even beyond quantile estimation, $m$-out-of-$n$ bootstrapping is almost ubiquitous in statistical learning and features prominently in tasks bootstrap aggregating typically uses $\\sqrt{n}$ many resamples when training the smaller models (Chapter 8, Hastie et al. [2009]).\n\n      Hastie, T., Tibshirani, R., Friedman, J. H., \\& Friedman, J. H. (2009). The elements of statistical learning: data mining, inference, and prediction (Vol. 2, pp. 1-758). New York: springer.\n      P. Hall. The bootstrap and Edgeworth expansion. Springer Science \\& Business Media, 2013\n\n**Experiments:** Regarding the first point we would like to remind the reviewer that we provide theoretical justifications for resampling of MCMC in section 5, and for the second point we hope that the reviewer finds our response to reviewer gjZu satisfactory. Having said that, we would also like to underline the fact that all our theory is **exact** and free from unknowable constants, in the sense that the asymptotic distributions are free of unknowable parameters, and first order expansions are precise. Furthermore, we theoretically demonstrate the reasonableness of our assumptions with examples in Section 5. Therefore, especially when considering the current length of the paper, we believe that simulations would not be significantly more illuminating.\n\n## Questions \n\n1.  The complete derivation of the closed-form expression is already provided in Supplementary Section B, and its location is explicitly flagged by a footnote on page 2 (line 39). In view of this clear cross-reference, the material should have been readily accessible. Nevertheless, to preempt any further oversight, we will replace the footnote with a prominent remark in the main text, immediately above line 40, in the revised manuscript.\n\n2.  We hope our response to Weakness 1a has already addressed this concern in part. To clarify further, the primary focus of this paper is on the behavior of bootstrap statistics. Under the standard assumption that sample quantiles are consistent for their population counterparts, confidence intervals can be derived as a straightforward consequence of Slutsky’s theorem.\n\n3.  We appreciate the reviewer’s interest in broader estimands and hope our response regarding M-estimation in the weaknesses section was helpful. We also refer the reviewer to our response to Comment 1b by reviewer NAQc for additional context. While we acknowledge the importance of extending the analysis to other settings, we believe such generalizations fall outside the scope of this work, which is already substantial in length and technical depth.\n\n4.  We would like to clarify that the purpose of the counterexample was to justify the moment condition imposed on the random variables. This implication follows directly by definition (see also our response to the first question). Additionally, we note that the counterexample demonstrates divergence of the error variance, a stronger result than simply showing that the bootstrap estimate fails to converge to the sample estimate.\n\n5.  We would like to respond in two parts:\n\n   **(a)** Hall and Martin’s 1991 paper concerns the classical (orthodox) bootstrap, whereas our work focuses on the \\( m \\)-out-of-\\( n \\) bootstrap.\n\n   **(b)** Since \\( m < n \\), we are able to apply a convenient continuity correction. This, in turn, allows us to leverage more modern results on Edgeworth expansions for polygonal approximants (see Lemma 9 at line 1075 and its proof at line 1106), rather than deriving the expansion from first principles as Hall and Martin did through substantial effort. A further implication of this smoothing is that the Studentized \\( m \\)-out-of-\\( n \\) bootstrap estimator of the sample quantiles admits an Edgeworth expansion with an even first polynomial, a property not shared by the classical bootstrap, where the first polynomial is neither even nor odd.\n\n6.  We agree with the reviewer and will revise line 72 to enhance clarity. In the updated draft, we will rephrase the sentence as:\n\n> “... deriving asymptotic distributions free of unknown parameters (parameter-free) for ...”\n\n7.  We hope our response to Question 6 has addressed the first part. Regarding the second part, because the polynomial in our Edgeworth expansion is even, it follows that $\\( P(T_m^{(boot)} > t) \\)$ agrees with $\\( P(T_m^{(boot)} < -t) \\)$ up to a $\\( 1/m \\)$ term. This symmetry does not hold for the classical bootstrap, where the leading polynomial is neither odd nor even. Prior literature (e.g., Hall and Martin, Van der Vaart) has noted the incompatibility of such expansions with two-sided tests, a limitation that the \\( m \\)-out-of-\\( n \\) bootstrap appears to avoid. We also point the reviewer to the technical justification provided in our response to Question 5b.\n\n8.  This is an excellent question. We note that our assumption that $\\( F \\in \\mathbb{S}_1(\\mu) \\)$ implicitly excludes extreme quantiles such as the maximum or minimum. These fall within the so-called “extreme” regime, which is inherently more challenging than the central regime (e.g., the median); see Dasgupta [2008, p. 91] for further discussion. However, we emphasize that no prior work has addressed Studentization for the \\( m \\)-out-of-\\( n \\) bootstrap estimator of sample quantiles in the practical regime $\\( m \\ll n \\)$. Thus, our contributions focus not on extending results from the median to other quantiles, but on developing new theory for Studentized quantiles, specifically including the median. We hope this helps clarify our intent.\n\n9.  Since Corollary 3 establishes the asymptotic distribution of $\\( T_m^{(boot)} \\)$, we believe it is stated correctly as is.\n\nWe would be happy to answer any further questions in the discussions\n\n**_We hope we have addressed all the questions, and kindly request you to revise your score._**"}, {"review_id": "eQfNA3M14j", "reviewer": "Reviewer_NAQc", "summary": "This paper is well written and well presented. It provides sharp consistency and CLT results for m our of n boot strap estimators of the quantile.  The significance is \n1) the results hold in practically motivated setting where the number of bootstrap sample m is large but not as large as the number of samples n; and \n2) the the assumptions on the underlying distribution are minimal (a tail bound and a local smoothness condition). \n\n\nComments: \n\n- Line 51 Please define DEA estimator \n\n- Theorem 1 - It is also required that $m \\to \\infty$ correct?  If so, this condition should be made explicit since $m = o(n)$ includes the case $m  = O(1)$.\n\n- Line 350 - \"join normality\" -> \"joint normality\" \n\n- I recommend more careful language with respect to what has and has not been done previously.  It's not clear to me that analysis of Gribkova and Helmers [2007] in the regime $m \\gg n$ should be called a \"deficiency\". Also, the statement in line 239 that \"no work attempted to study the effects of bootstrapping to create confidence intervals for statistics that are of interest in tasks like reinforcement learning or MCMC.\" is impossible to validate.", "questions": "Is there a reason that the tail conditions cannot be alleviated via truncations techniques?", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- This paper fills in gaps in the literature w.r.t bootstrap. \n- The details analysis of Markov chains goes beyong the standing IID setting in a meaningful way. \n- The paper is well writing and the proofs careful and precise. \n\nWeakness:\n- The results require smoothenss conditions on the distribution (e.g., reward). What happens if these are vioiated? For applications in reinforcement learning, this rules out reward functions that may be of interest. \n- The interest in this topic within the neurips community might be limited.\n- The paper does not make a strong case for the importance of this analysis. There are no empirical results. The authors claim that prior work is impractical because it requires m to large to be computationally practical. But the theoretical results in this paper are valid only in the limit as m goes to infinity, so the same argument would seem to apply here. If one wants to make a convincing argument it would help to mention the computational complexity and typical scalings.", "was_revised": true, "final_justification": "I agree with the weaknesses raised by other reviewers, particularly KcDW\n\nWhile I appreciate the mathematically precise analysis, the practical motivation for this work is still unclear to me. If the main contribution of this paper is that it fills in some missing gaps in the theoretical literature that is perfectly fine (though perhaps a bit narrow). If there are meaningful practical implications (partially for the setting of quantiles covered by the theory), they should be highlighted. Since I am not aware of applications where computing the empirical quantiles is the main bottleneck, the purported gains in this direction are not obvious to me.", "rebuttal": "Thank you for your careful review and meticulous reading and assessment. We will be happy to address the few weaknesses you have pointed out. You have provided us an opportunity to discuss answers to a few very valuable questions.\n\n**Typos pointed out in the summary:** We want to thank the reviewer for pointing out the minor typos, including acronyms where DEA stands for Data Envelopment Analysis, and added clarification that in our context, the convergence in distribution $\\xrightarrow{d}$ is when both $m$ and $n$ is going to infinity. \n\n# Response to Strengths and Weaknesses\n\n**1. Smoothness assumption on reward function in the MDP example:** - We would like to highlight three important aspects of this example.\n\na. We have found that most literature on reinforcement learning theory assumes finite state-action, and rigorous theoretical treatment of RL as a continuous MDP is somewhat rarer. In the finite setting, the reward function can be described as a finite dimensional vector with minimal assumptions. Therefore, while generalising, we made a largely simplifying assumption that serves to illustrate the amenability of the regenerative assumption towards the analysis of the reward function of MDP's. If one looks at the proof, what we really require is the ergodicity of the reward function, which follows as a consequence of this assumption and some calculations. However, we think directly assuming that the rewards are ergodic is somewhat terse and un-illuminating.\n\nb. We agree with the reviewer about the broader need to have theoretical results on resampling of MDP's under weak assumptions, which we believe is possible with considerably more work. However, since this was a corollary to a more general theorem (Theorem 3), it made sense for us to somewhat simplify the problem for the sake of illustration. We are working on one follow up work which builds upon the theory of the current paper to tackle resampling in offline RL under significantly more generality. Given the rapidly rising popularity treating MDP's as ergodic Markov chains (see for example, Fabien and Maillard, [2022]), we think our current work will also be relevant for other prospective authors in this field.\n\n    Pesquerel, Fabien, and Odalric-Ambrym Maillard. \"IMED-RL: Regret optimal learning of ergodic Markov decision processes.\" Advances in Neural Information Processing Systems 35 (2022): 26363-26374.\n\n**2. The interest in this topic within the NeurIPS community might be limited.** - We would like to respectfully point out to the reviewer that some of the *other reviewers explicitly agree on the interest of this paper to the NeurIPS community*. While resampling and empirical process theory for regenerative Markov chains in isolation align more with probability theory, we provide illustrative examples for MCMC and RL, which we think are of strong interest to the NeurIPS community. As you and other reviewers note in the review, this paper extends the theory beyond IID in a meaningful way and is well motivated for machine learning. We hope that our rebuttal also helps convince you of the merits of this paper through the lenses of modern ML tasks.\n\n**3. Importance of this analysis and empirical results** - We address this in several parts.\n\na. **Practicality over prior work:** We would like to take this opportunity to clarify some misunderstanding. What we really meant to say in the paper (line 58-59) was that prior theoretical work assumes $m\\gg n$, which is not only unnecessary (as demonstrated in Theorem 2), but also which defeats the entire practical motivation of resampling fewer than $n$ samples [Bickel et al. 1992], and thus is uncommon in practice (see also the numerical simulations outlined below which uses $m=o(n)$).\n\nb. **Computational complexity:** We agree about the need to clarify the computational complexity of estimating the resampled quantile and we will add the following line as a remark between lines 42 and 43 in the revised manuscript.\n\n> The computational complexity of resampling and of estimating the quantile (via selection algorithm) is $O(m)$.\n\nc. **Asymptotics:** At this point, we would like to gently remind the reviewer that Theorem 2 (which concerns Edgeworth expansion) is *not asymptotic*, but finite sample. One of our goals in this paper (as mentioned in Section 3.1) was to demonstrate theoretically that $m\\ll n$ is actually sufficient to derive an Edgeworth expansion for Studentized quantiles which we felt was an important gap left by Gribkova and Helmers.\n\n    P. J. Bickel, F. Götze, and W. R. van Zwet. Resampling fewer than n observations: gains, losses, and approximations. Statistica Sinica, 2(1):1–31, 1992\n\n**4. Exposition:** As also pointed out in the strengths section your review, our main motivation was to study the practical necessity of $m\\ll n$. However, we completely agree with the reviewer about the need to reword \"deficiency\" to accurately point out the gaps in literature, and **change the lines from 58-61** into \n\n>\"Gribkova and Helmers [2007] derive an Edgeworth expansion for Studentized trimmed means in the non‑classical $m\\gg n$ regime, offering theoretical insights but leaving unanswered the setting when $m\\ll m$ which motivates subsampling. Our work addresses these practically relevant open questions that were left unanswered in previous studies by supplying corrected rates and Edgeworth expansions tailored to the practically relevant $m\\ll m$ regime.\"\n\nWe also agree with the reviewer on the topic regarding line 239 and will remove it from our revised manuscript.\n\n**Empirical Results:**   We would also like to gently underline the fact that all our theory is **exact** and free from unknowable constants, in the sense that the asymptotic distributions are free of unknowable parameters, and first order expansions are precise. Furthermore, we theoretically demonstrate the reasonableness of our assumptions with examples in Section 5. Therefore, especially when considering the current length of the paper, we do not find that simulations to be significantly more illuminating. However, we still agree about the need for some empirical illustrations in the form of simulation, and we hope you find our response to weakness 1. of reviewer gjZu satisfactory.\n\n# Response to Questions\n\n**Is there a reason that the tail conditions cannot be alleviated via truncations techniques?** - We do not think that the tail condition be removed via more sophisticated analysis, and provide a counter-example (Proposition 1) in the paper to address this point. We do agree with the reviewer that the condition can probably be weakened, and discuss this in the paper (see lines 183-185, as well as 194-201). However, the assumption is already mild, and weakening it seems to require new analytical machinery, which makes it beyond the scope of the current work.\n\n\n**_We hope we have addressed all the questions, suggestions and weaknesses listed and kindly request you to revise your score._**"}, {"review_id": "2PtNWF6oj1", "reviewer": "Reviewer_gjZu", "summary": "This work investigates the $m$-out-of-$n$ bootstrap, a resampling method that draws a subsample of size $m\\ll n$ from a dataset of size $n$, focusing on estimating sample statistics. The authors developed a rigorous second-order theory for Studentized versions of the bootstrap quantile estimator under relatively general conditions. They proved variance consistency and the central limit theorem (CLT), derived a parameter-free Edgeworth expansion with an $O(m^{-1/2})$ convergence rate, and established a Berry-Esseen bound. These techniques and results are applicable to both IID and regenerative Markov chain settings. Additionally, they correct errors and inconsistencies in previous variance formulas. The work is complemented by illustrative applications in Random Walk MH and Offline Ergodic MDPs.", "questions": "Please carefully review the points, questions, and suggestions listed in other sections, including the identified strengths, noted weaknesses, and areas for clarification or improvement, as they aim to enhance the paper's technical rigor, practical relevance, and overall presentation.", "limitations": "The work is mainly theoretical and does not pose a direct societal risk. However, practical uses in sensitive areas (such as finance and healthcare) should consider the constraints of the required moment conditions and the potential for variance inflation in extreme, heavy-tailed situations. The authors also included a section on \"limitations and outlook,\" which reads well.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Assessment of strengths:\n1. The paper addresses a well-known but underexplored setup: quantile estimation using the Studentized m-out-of-n bootstrap method. The results are technically sound and seem to fill a genuine gap in second-order theory.\n2. The derivation steps are clear, as shown in the proof sketches of Theorems 1 and 2. The authors also thoroughly explain the implications of the main results and the intuitions behind them.\n3. The assumptions are broad, including finite $\\alpha$-order moments and weak smoothness conditions, making the results applicable to other problems.\n4. The authors extended the approach to Markov chain data, which is well-motivated for RL and MCMC settings, and they corrected previous errors and inconsistencies in the literature.\n\nAssessment of weaknesses:\n1. While the theoretical contributions are non-trivial, the paper lacks detailed empirical validation, although some practical implications (e.g., for RL and MCMC) are discussed. \n2. The counterexample used to justify the necessity of moment conditions (Proposition 1) is insightful but somewhat abrupt. It does not imply that a moment condition is necessary. A broader discussion on the characteristics that heavy-tailed distributions must have for the variance of the bootstrap estimator to approach infinity would be helpful. \n3. Relying on regenerative structure and conditions in Assumption 1 could limit the generality of the Markov chain results. Would it be possible to include a broader discussion on the limitations and restrictiveness of these assumptions?\n 4. I wonder if the authors have some non-heuristic, principled methods to guide the choice of $m$, especially those that are adaptive to practical settings.", "was_revised": true, "final_justification": "My current score of 4 already indicates that I am inclined to accept the paper. The rebuttal helps to improve the paper and provides more clarity, but does not invalidate the claims made in my original review. Hence, I choose to keep my original score. \n\nBelow are recaps of some points made during the author-reviewer discussion.\n\n- **The paper lacks detailed empirical validation.** \nI agree that the paper's results have been proven. And \"validation\" in my original review mainly refers to \"verifying if the theory applies to practical scenarios (e.g., for RL and MCMC),\" where some of the assumptions may not entirely hold, but remain true to some extent.\n\n- **Restrictiveness of assumption 1.**\nI acknowledge the authors' inability to address such \"restrictiveness\" in the current submission. And I look forward to seeing generalized results in the authors' or other researchers' follow-up work.", "rebuttal": "Thank you for your careful review and meticulous reading and assessment. We are very happy that you pointed out a few weaknesses which we would like to address below.\n\n# Response to Strengths and Weaknesses\n\n\n**1. The paper lacks detailed empirical validation** - Regarding the empirical validation, we respectfully note that the principal contribution of this manuscript is theoretical. The core results have been established through rigorous mathematical proofs; therefore, additional numerical experiments are not required to validate their correctness. We are also pleased that you found our attempt demonstrate the practicality of our assumptions in machine learning tasks like RL and MCMC to be useful. Therefore, especially when considering the current length of the paper, we do not find that simulations to be significantly more illuminating. However, we still agree about the need for some empirical illustrations in the form of simulation, and we hope you find our response below satisfactory. \n\nWe conducted Monte Carlo experiments with sample sizes n ∈ {10000,20000,50000}. For each n we examined three block sizes $m = log n, n^{1/3}, and √n$. Following the procedure described in lines 33–39 (formula for the bootstrap statistic), and Equation (B.2) (closed form variance estimate), we repeatedly evaluated the test statistic T to approximate its sampling distribution.\n\nThree data-generating mechanisms were considered:\n\n1. i.i.d. Gaussian observations;\n2. i.i.d. observations obtained by reflecting a simple random walk onto the interval [−1, 1];\n3. a Markov chain generated by the Random-Walk Metropolis–Hastings (RWMH) algorithm (see line 305-312), employing a Laplace proposal distribution on a standard normal target density.\n\nFor each configuration we measured the discrepancy between the empirical distribution of T and the standard normal distribution using the Kolmogorov–Smirnov (KS) distance.\n\nn = 10K  \n\n| m |   m value | Case         | Mean(T)   | Var(T)   | KS   |\n|-------------|-----|--------------|-----------|----------|------|\n| $\\log(n)$   |   9 | Gaussian     | −0.030959 | 0.992566 | 0.033 |\n| $\\log(n)$   |   9 | Reflected RW |  0.041787 | 0.784624 | 0.069 |\n| $\\log(n)$   |   9 | MH RW        |  0.005385 | 0.937350 | 0.057 |\n| $n^{1/3}$   |  21 | Gaussian     | −0.053800 | 1.114615 | 0.028 |\n| $n^{1/3}$   |  21 | Reflected RW | −0.006052 | 0.965366 | 0.040 |\n| $n^{1/3}$   |  21 | MH RW        | −0.045641 | 0.862029 | 0.028 |\n| $\\sqrt{n}$  | 100 | Gaussian     | −0.037565 | 1.059072 | 0.039 |\n| $\\sqrt{n}$  | 100 | Reflected RW |  0.021268 | 0.905786 | 0.069 |\n| $\\sqrt{n}$  | 100 | MH RW        | −0.081919 | 0.978142 | 0.061 |\n---\nn = 20K  \n\n| m |   m value | Case         | Mean(T)   | Var(T)   | KS   |\n|-------------|-----|--------------|-----------|----------|------|\n| $\\log(n)$   |   9 | Gaussian     | −0.035324 | 0.975723 | 0.033 |\n| $\\log(n)$   |   9 | Reflected RW |  0.015931 | 0.771220 | 0.052 |\n| $\\log(n)$   |   9 | MH RW        | −0.003805 | 0.977506 | 0.033 |\n| $n^{1/3}$   |  27 | Gaussian     | −0.025948 | 0.976584 | 0.028 |\n| $n^{1/3}$   |  27 | Reflected RW | −0.011587 | 0.956381 | 0.027 |\n| $n^{1/3}$   |  27 | MH RW        |  0.006103 | 0.970455 | 0.032 |\n| $\\sqrt{n}$  | 141 | Gaussian     |  0.048491 | 0.972170 | 0.049 |\n| $\\sqrt{n}$  | 141 | Reflected RW |  0.027213 | 1.045555 | 0.032 |\n| $\\sqrt{n}$  | 141 | MH RW        |  0.025495 | 0.967099 | 0.040 |\n\nn = 50K  \n\n| m |   m value | Case         | Mean(T)   | Var(T)   | KS   |\n|-------------|-----|--------------|-----------|----------|------|\n| $\\log(n)$   |  10 | Gaussian     |  0.023658 | 0.920129 | 0.039 |\n| $\\log(n)$   |  10 | Reflected RW |  0.024419 | 0.794373 | 0.044 |\n| $\\log(n)$   |  10 | MH RW        |  0.011908 | 0.860669 | 0.025 |\n| $n^{1/3}$   |  36 | Gaussian     | −0.001047 | 0.959031 | 0.028 |\n| $n^{1/3}$   |  36 | Reflected RW |  0.001399 | 0.872152 | 0.027 |\n| $n^{1/3}$   |  36 | MH RW        |  0.007086 | 0.971482 | 0.022 |\n| $\\sqrt{n}$  | 223 | Gaussian     | −0.051904 | 1.046060 | 0.051 |\n| $\\sqrt{n}$  | 223 | Reflected RW | −0.028429 | 0.957545 | 0.028 |\n| $\\sqrt{n}$  | 223 | MH RW        | −0.021154 | 0.967758 | 0.023 |\n---\n\n**2. The counter-example is abrupt** - We agree with the reviewer that the counterexample does not imply that the moment condition is necessary, and this, along with the language in Section 4.1 creates some confusion. We have **revised** the section to more carefully explain the point of the counterexample as can be seen below.\n\n>**Importance of the Moment Condition**\nWe briefly discuss the importance of the condition  $\\mathbb{E}\\bigl[|X_{1}|^{\\alpha}\\bigr] < \\infty$\nin **Theorem&nbsp;1**. A close inspection of the proof indicates that we really only need the condition in eq.&nbsp;(A.1). However, we found such statements terse and un-illuminating.  \n\n>On the other hand, the following counter-example shows that one cannot outright discard all tail conditions. Note that this does **not** imply that the condition $\\mathbb{E}\\bigl[|X_{1}|^{\\alpha}\\bigr] < \\infty$ is a *necessary* condition, but rather demonstrates that Theorem&nbsp;1 cannot be expected to hold for arbitrarily heavy-tailed distributions. Although this phenomenon has been observed via simulation&nbsp;[Sakov, 1998], we provide what is, to our knowledge, the first theoretical justification.\n\n**3. Restrictiveness of assumption 1** - We thank the reviewer for pointing out this important comment and agree on the necessity of discussing the regenerative condition, and we will revise the ``limitations and outlook\" section in the following manner to include it.\n\n>Our guarantees still assume mild smoothness and leave open the precise heavy‐tail boundary and non‐stationary processes, and adaptive variants remain compelling directions for future study. The question regarding the joint normality of the estimators also remains an important open problem. Finally, it would be desirable to derive an Edgeworth expansion of the Studentized bootstrap estimator for Markov chains. However, the theory of Edgeworth expansions on lattices for regenerating Markov chains is sparse (in particular, we could not find a usable counterpart to Proposition 12 for Markov chains). Deriving such a result is out of scope for this (already lengthy) paper, and we plan to investigate it in future work.\n\n>Another important assumption is that of regeneration. We note that the exponential moment condition in Assumption 1 is equivalent to the more classical geometric ergodicity of Markov chains (see Theorem 16.0.2 in Meyn and Tweedie [2009]). It is known that a weaker polynomial moment condition is equivalent to arithmatically mixing for Markov chains (see Bolthausen [1982]), and a corresponding result in this regime seems plausible, and warrants future investigation.\n\n    Bolthausen, E. (1982). On the central limit theorem for stationary mixing random fields. Ann. Probab.\n    10 1047–1050. MR0672305\n    Meyn, S. and Tweedie, R.L. (2009). Markov Chains and Stochastic Stability, 2nd ed. Cambridge: Cambridge Univ. Press. With a prologue by Peter W. Glynn. MR2509253\n\n**4. Non‑heuristic, principled methods to guide the choice of $m$** - We do provide such a guidance (barring a small typo) in line 229 with $m=O(n^{1/3})$ as follows:\n\n> Finally, the optimal choice of m seems to be $m = O(n^{1/3})$ which is known to be the minimax rate for estimating the population median [Bickel and Sakov, 2008].\n\n**Formatting:** We thank the reviewer for raising this point and will include the following summary of Section 4 between lines 160 and 161 for better guiding of the prospective readers\n\n> This section presents Theorem 1 on the asymptotic normality of the Studentized bootstrap statistic under a mild moment condition, with a proof sketch (full details in Appendix A). Proposition 1 provides a counterexample in the absence of this condition. Theorem 2 establishes an Edgeworth expansion for the statistic.\n\nFinally, we cordially thank you again for reading our work in-depth and we very much welcome your further suggestion to improve our final version.\n\n**_We hope we have addressed all the questions, suggestions and weaknesses listed and kindly request you to revise your score._**"}, {"review_id": "praHzat1xz", "reviewer": "Reviewer_gHZF", "summary": "This is a theoretical paper about the n-out-of-m bootstrap (i.e., drawing $m \\ll n$ samples for each bootstrap iteration). The paper specifically considers a model free setting, where nothing is assumed about the data-generating process except for a weak moment condition. The paper points out that despite the over 30 year history of the m-out-of-n bootstrap, no (correct) theory exists proving its limiting behavior. The paper derives a central limit theorem (CLT) for the n-out-of-m bootstrap, giving a correct description of its limiting behavior. The paper goes on to prove a Berry-Esseen bound for the m-out-of-n bootstrap's behavior, showing that the distribution of the estimator converges to normal at a $1/\\sqrt{m}$ rate. The paper then does a significant amount of extra theoretical work to extend these results to derive confidence intervals for the rewards in a Markov decision process, which the paper notes are the first of their type.", "questions": "1. What should a practitioner who is considering using the m-out-of-n bootstrap take away from reading this paper?\n\n2. In Section 5, are the $X_i$ sampled from the MCMC algorithm or from the stationary distribution?\n\n3. What are $\\psi, \\Psi$, and $E$ in Section 5?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "# Strengths\n\nI think this is overall a pretty solid paper. There were a few points that I thought it did especially well:\n\n1. The comparison to previous literature is very precise, and I found it very clear how this work compared with previous papers in this space.\n\n2. Good proof sketches are provided; I really felt like I got a good sense of how each proof was going to proceed from the outline in the main text.\n\n3. Study of necessiry of conditions: a very weak moment condition is assumed (there exists some $\\alpha > 1$ such that $E|X|^\\alpha < \\infty$) to prove the theory. Instead of noting that this is a very standard and mild assumption in the literature, the paper provides a counterexample to the theory when this moment condition does not hold.\n\n4. Overall easy to read: despite being a purely theoretical paper about a typically mathematical topic, I found the paper pretty easy to follow. And I would say that I'm knowledgeable about the bootstrap, but not an expert on its theory by any means.\n\n# Weaknesses\n\nI had two medium-level weaknesses:\n\n1. I think the paper is a little mean towards the previous work of Cheung and Lee (2005) (CL). The paper points out that part of its contribution is to correct a mistake in CL. As part of doing that, of course it needs to say CL is wrong. But I thought the paper crossed the line towards being rude:\n   \"[The] most damning [gap in previous literature] seems to be Cheung and Lee (2005), which which gives an incorrect variance formula\"\n\n   I would be more polite and also just generally avoid using the word \"damning\", especially to describe other people's mistakes.\n\n2. Lack of practical advice. The paper doesn't provide any practical advice about the use of the m-out-of-n bootstrap. I know this is a purely theoretical paper, but I usually think of the goal of theory as providing guidance for practice. I think the paper could dedicate a little space to discussing the takeaways of the results. E.g., should we be spending our time on the m-out-of-n bootstrap? Or should we just use the central limit theorem to derive uncertainty? On the face of it, it seems like the CLT variance shrinks more quickly, as it goes with $1/\\sqrt{n}$, whereas the variance from Theorem 1 goes with $1/\\sqrt{m}$.\n\nI also have a collection of minor-level comments; I don't think these meaningfully contribute to the strength of the paper, with the exception of \\#8 and \\#12, which I was really unclear on.\n\n1. There's some jargon used in the introduction that I don't think was defined: \"DEA estimator\" and \"PTRF paper\" (I had to google what PTRF is -- I'm pretty sure typical NeurIPS attendees will not know this journal by name, and definitely not by abbreviation). Additionally, the paper uses the term \"Bachman–Landau notations\" to refer to big-$O$ and little-$o$ notation, which isn't standard as far as I know for computer science venues.\n\n2. Line 93: \"For example, In\" the capitalization here is a typo.\n\n3. $\\mathcal{C}$ is used to denote a constant. I think it's a little bit of a mistake to use that symbol to represent anything besides the complex numbers.\n\n4. Theorem 1 uses $q$ to denote the quantile of interest, whereas the rest of the paper uses $p$.\n\n5. Step 1 of the  sketch of Theorem 1 uses $i$ without defining it or it being clear from the context what it means.\n\n6. Step 2 of the sketch of Theorem 1 states a Hoeffding bound, but I don't see $t$ on the right hand side of it. Should the $\\delta$ be $t$?\n\n7. Line 234: \"... and empirical distribution $\\bar F$\" -- is this supposed to be \"empirical stationary distribution\"?\n\n8. Section 4.3 on extending to Markov chains has some undefined notation: $\\psi, \\Psi, E$.\n\n9. In section 5, $q$ is a positive function satisfying some conditions. Do these conditions hold for all $x$? Or just some?\n\n10. In Section 5, I don't think $q_0$ was ever defined.\n\n11. At the beginning of Section 5, $x$ is real-valued, but later it takes values in $R \\times R$.\n\n12. Corollary 2 assumes that $X_1, \\dots, X_n$ are sampled from the trajectory of a MCMC algorithm. But at the start of section 5, it's assumed that $X_1, \\dots, X_n$ are sampled from the stationary distribution of some Markov chain. These aren't the same thing, so which are we supposed to be assuming when reading through Section 5?   \n\n13. I think Corollary 3 should state its assumptions within the theorem environment.", "was_revised": true, "final_justification": "The authors' responses to my and other reviewers' comments makes me more confident about the strength of the paper, and I've maintained my vote for an acceptance.", "rebuttal": "We thank the anonymous reviewer for the valuable comments. We are grateful for getting helpful suggestions, and a list of typos. We will address all the feedback we received in the final version of this paper and, of course, fix the typos and add necessary clarifications.\n\n# Response to Strengths and Weaknesses\n\n__Tone towards prior work:__ We completely agree with the reviewer in hindsight that it came out harsher than we intended and thank the reviewer for highlighting this important point. We intend to replace it with ``One significant discrepancy seems to be in Cheung and Lee [2005], which gives an incorrect variance formula for the m-out-of-n estimator of sample quantiles without derivations or citations.\" which we hope will be more acceptable.\n\n**Lack of practical advice:**  We thank the reviewer for this question and would like to take this opportunity to remind them that the practical benefits of bootstrapping has been relatively well studied and we refer to the citations on line 107 of our paper (Singh and Xie [2008], Davison and Hinkley [1997], Freedman et al. [2007], Dasgupta [2008]) for references. As we also point out to reviewer gjZu, we also provide a way to choose $m$ based on our current theory. Our main objective here (as we mentioned in line 116, line 142, etc.) was to attack one specific corner of this problem which lay largely unanswered: the theoretical properties of the studentized bootstrapping of the sample quantiles for IID and regenerative Markov chains. Our work had four primary motivations (as outlined between lines 63-80, section 3.1, and section 4.2)  (1) acquitting the oddities of Studentization in bootstrapping the median, (2) give minimal conditions for asymptotic normality, (3) produce second order Edgeworth expansions, (4) extend bootstrap to Markov chains to align it with modern tasks like RL and MCMC. \n\n**Minor comments and typos:** We thank the reviewer for pointing out the typos and will correct those, as well as provide full names for the acronyms for DEA (Data Envelopment Analysis), and PTRF (Probability Theory and Related Fields) in the revised version of the paper. Now we proceed to answer some of the specific comments pointed out by the reviewer.\n\n**Point 5**, We thank the reviewer for pointing out this typo. $i^{1/\\alpha}$ should be $n^{1/\\alpha}$, and hopefully this clears up the discrepancy.\n\n**Point 8** We thank the reviewer for pointing out this important omission. The definitions are largely technical, and the key objective is to build towards the definition of regeneration, which endows the Markov chain with desirable properties. Therefore, while the context is interesting, including all formal definitions will probably be distracting for our purposes, and we believe that pointing towards classical textbooks is the correct approach. We would  point the readers to the definitions in Meyn and Tweedie  (Markov chains and Stochastic Stability, defined in pages 89 and 103 respectively). That said, there is an intuitive explanation which we include in the revised version, to better illustrate the key concepts to a prospective reader.\n    \n>$\\psi$ and $\\Psi$ are somewhat common in Markov chain literature to denote $\\psi$-irredicibility and $\\Psi$-atoms respectively [Bertail and Portier, 2019]. We will not require the formal definitions, and therefore we refer the interested reader to classical textbooks on Makov chains [pages 89 and 103, Meyn and Tweedie, 2013] for more details. Intuitively, $\\psi$-irredicibility extends the classical notion of irreducibility for finite state Markov chains to infinite state spaces, whereas $\\Psi$-atoms are sets from which the transitions behave homogeneously with some probability measure $\\Psi$. For finite state Markov chains, the atoms are the individual states (i.e. singletons). Informally, a regenerating Markov chain is a $\\psi$-irreducible Markov chain which has at least one $\\Psi$-atom that is repeatedly visited (with the inter-arrival times termed as the regeneration time). Conditions on the moments of the regeneration time charactises the ergodic properties of the Markov chain.\n\n     Citation: P. Bertail and F. Portier. Rademacher complexity for Markov chains: Applications to kernel smoothing and Metropolis–Hastings. Bernoulli, 25(4B):39123938, Nov. 2019. ISSN 1350-7265. doi: 10.3150/19-BEJ1115.\n    \n**Point 10**, The confusion regarding $q_0$ is a result of a typo. $q(\\cdot,\\cdot)$ is a bivariate function, and $q_0$ is an univariate function such that $q(x,y)=q_0(x-y)$. This notation standard in the MCMC literature, and we will correct it in the revised version.\n\n**Point 12**, the reviewer is indeed correct that for this example we have considered a stationary MCMC which is a limitation of our current work. However, this example is primarily a demonstration of the applicability of our assumptions and we believe that the theory can be generalised with significantly more tedium to non-stationary ergodic Markov chains. Considering that bootstrap for Markov chains is sparsely studied (see line 238), this is a good topic for future studies.\n\n# Response to Questions:\n\nRegarding questions 2 and 3, we hope you find our responses to the weaknesses sections satisfactory. As for the first question—what a practitioner should take away—we offer the following 60-second summary:\n\nPractitioners interested in sampling from the distribution of the sample quantiles may continue to rely on the bootstrap with confidence. Our results suggest that standard practice often remains valid even in dependent settings, such as Markov chains encountered in MCMC or offline reinforcement learning. Moreover, the m-out-of-n bootstrap provides a robust alternative when orthodox bootstrap is compromised by lack of symmetry (as we discuss in lines 224-228).\n\n**_Once again, we thank the reviewer for such a great evaluation of our work._**"}]

Author rebuttal:

Meta-review: This paper develops a framework for resampling with small sample sizes, yielding sharp non-asymptotic guarantees. The results are mathematically careful, the presentation is clear, and the reviewers consistently judged the technical quality to be high.

The strengths highlighted were rigor and clarity. The main reservation is that the contribution feels narrow and not especially exciting from the perspective of broader NeurIPS impact. Reviewers nevertheless felt that the contribution was valuable, emphasizing that the sharpness of the guarantees advances the state of the art. In their rebuttal, the authors clarified aspects of positioning and provided further examples, which the reviewers found adequate.

That said, the reviewers were positive, finding the work correct, solid, and of value to the statistical theory community. Given the strength of their assessments, I follow their recommendation to accept.
Decision: Accept (poster)