Introduction
From 1987 to 2004, U.S. upper-half wage inequality rose while lower-half inequality contracted [4 ] . Quantile comparisons distinguish these distributional changes that a mean or an isolated percentile can miss. As a data stream grows, a finer percentile grid permits more detailed comparisons. Their uncertainty must be assessed jointly: a collection of pointwise intervals does not control the largest error over an expanding grid. We study this problem when each user privatizes a measurement before sending it to the server and participates only once.
Local differential privacy (LDP) makes this joint inference problem different from classical quantile inference. Sample-quantile representations and cumulative distribution function (CDF) bands connect nonprivate quantile error to a shared empirical process [5 , 13 , 23 , 11 ] . Under LDP, the server receives randomized reports rather than observations [31 , 15 ] . It must learn where the quantiles are while deciding which thresholds to query. Giving each percentile a separate user group loses information as the number of targets grows; using a shared report avoids this split but creates dependent errors at adaptively selected thresholds. Joint calibration must accommodate both that dependence and the error in the learned locations.
Recent work provides online inference for a prespecified scalar quantile. Liu et al. [21 ] use randomized binary inquiries and self-normalization to avoid nuisance-density estimation. Cai et al. [6 ] use dynamically growing parallel stochastic-approximation paths to obtain an asymptotic confidence sequence over time. Other developments address communication-efficient single-quantile estimation, federated scalar inference, and fixed-dimensional quantile-regression contrasts (Aamand et al., 2025; Cai et al., 2026a,b; Liu and Hu, 2026). Our target is joint inference at a terminal horizon fixed before data collection, with the number of probability targets increasing as that horizon grows. Extending scalar inference to this setting requires uniform control of localization and density errors at the scale of a maximum, rather than a separate scalar approximation at every target.
CDF estimation followed by inversion is an important alternative. Liu et al. [22 ] study private CDF estimation on public inspection grids. A simultaneous CDF band supports probability queries selected after release, whereas direct inference learns locations for prespecified probabilities.
For independent observations with CDF F F F , our targets are
0 < τ 1 , n < ⋯ < τ k n , n < 1 , Q j , n = F − 1 ( τ j , n ) , 0 < \tau_{1,n} < \cdots< \tau_{k_n,n} < 1,\qquad Q_{j,n} = F^{-1}(\tau_{j,n}), 0 < τ 1 , n < ⋯ < τ k n , n < 1 , Q j , n = F − 1 ( τ j , n ) ,
where the deterministic number k n k_n k n may diverge. “Infinite” refers to this increasing sequence of finite target grids. With one report per user at privacy budget ε n > 0 \varepsilon_n > 0 ε n > 0 and public queries allowed to depend on past reports, we seek intervals satisfying
P { Q j , n ∈ I n , j for every j ≤ k n } → 1 − α , α ∈ ( 0 , 1 ) . \mathbb{P}\left\{Q_{j,n} \in\mathcal{I}_{n,j}\ \text{for every }j \leq k_n\right\} \to1-\alpha,\qquad\alpha\in(0,1). P { Q j , n ∈ I n , j for every j ≤ k n } → 1 − α , α ∈ ( 0 , 1 ) .
The probability targets are specified before collection; the method learns their spatial locations.
Our first step extracts more information from a shared range-tree report with optimized unary encoding (OUE) [30 , 12 ] . Every threshold has two unbiased CDF scores: a prefix sum and the complement of a suffix sum. Their exact covariance determines a minimum-variance linear fusion at the correct CDF anchor. Fusion remains unbiased for any public anchor, and the variance penalty for an inaccurate anchor is quadratic. Thus the target probability itself supplies an increasingly accurate anchor as localization improves. This gain changes only decoding, with no additional report or privacy expenditure.
Our second step separates adaptive learning from joint calibration. The first cohort averages one projected stochastic-approximation path for each target. The second estimates densities near the learned locations. The third supplies fresh user-level score vectors. A one-step correction cancels first-order localization error, leaving a product of localization and density errors and a local nonlinear remainder. Conditional on the first two cohorts, the fresh vectors are independent and identically distributed; shared Gaussian multipliers retain their cross-quantile dependence. We bound the remainder uniformly and connect it to high-dimensional Gaussian approximation [24 , 9 , 10 ] . At fixed privacy, a sufficient regime permits every polynomial growth rate of k n k_n k n , with only logarithmic grid-size factors in the width bound.
We compare a same-channel fixed-grid inversion procedure with the complete three-cohort method, including the users spent on learning. Fusion reduces error by 21–23% relative to balanced decoding in the matched three-stage experiments. CDF inversion gives smaller errors and narrower, more conservative intervals on the tested public spatial grids. These comparisons distinguish the benefit of extracting complementary information from a report from the cost of learning where to query it.
The paper is organized as follows. Section 2 develops the procedure and its implementation. Section 3 states the assumptions and theoretical guarantees, and Section 4 compares fixed-chain calibration. Sections 5 and 6 present the complete numerical experiments and wage-percentile application. Section 7 concludes. Proofs and their auxiliary lemmas are collected in the appendices.
Shared private scores and quantile inference
Algorithm 1 gives the complete procedure, from public inputs to simultaneous intervals. We first construct the shared private report and then describe the three cohorts and default tuning; Section 2.4 gives the streaming updates.
We suppress the subscript n n n on τ j , n \tau_{j,n} τ j , n and Q j , n Q_{j,n} Q j , n when the sample size is clear. The generalized inverse is
F − 1 ( u ) = inf { x ∈ R : F ( x ) ≥ u } . F^{-1}(u)=\inf\{x\in\mathbb{R}:F(x)\ge u\}. F − 1 ( u ) = inf { x ∈ R : F ( x ) ≥ u } .
The public projection bracket [ L , U ] [L, U] [ L , U ] contains all target quantiles in its interior, while the raw observations may be unbounded. Public scientific range information or an independently privatized range-estimation cohort can supply this bracket. The Stage-1 projection frequency and the distance of final iterates from its endpoints summarize its adequacy. At time i i i , a public query q i q_i q i may be a measurable function of the previous reports Z 1 , … , Z i − 1 Z_1, \ldots, Z_{i-1} Z 1 , … , Z i − 1 . A local randomizer M i \mathcal{M}_i M i is ε n \varepsilon_n ε n -LDP conditional on the public history if, for every pair x , x ′ x, x' x , x ′ , every history, and every measurable report set A A A ,
P { M i ( x ; q i ) ∈ A ∣ Z 1 : i − 1 } ≤ e ε n P { M i ( x ′ ; q i ) ∈ A ∣ Z 1 : i − 1 } . \mathbb{P}\{\mathcal{M}_i(x;q_i) \in A \mid Z_{1:i-1}\} \le e^{\varepsilon_n}\mathbb{P}\{\mathcal{M}_i(x';q_i) \in A \mid Z_{1:i-1}\}. P { M i ( x ; q i ) ∈ A ∣ Z 1 : i − 1 } ≤ e ε n P { M i ( x ′ ; q i ) ∈ A ∣ Z 1 : i − 1 } .
The complete procedure is user-level ε n \varepsilon_n ε n -LDP for every deterministic horizon. Conditional on the past transcript, OUE has this privacy bound and the sampled tree level is independent of the user’s value. History-dependent queries and server-side computations preserve the bound; each person belongs to only one cohort. Section B gives the likelihood-ratio argument for the full sequential transcript.
Complementary scores from one report
For privacy budget ε = ε n \varepsilon= \varepsilon_n ε = ε n , fix d d d ordered public thresholds
x ( 1 ) ≤ ⋯ ≤ x ( d ) . x_{(1)} \le\cdots\le x_{(d)}. x ( 1 ) ≤ ⋯ ≤ x ( d ) .
Stable tags distinguish ties. These thresholds induce d + 1 d+1 d + 1 interval categories
C 0 = ( − ∞ , x ( 1 ) ] , C s = ( x ( s ) , x ( s + 1 ) ] ( 1 ≤ s < d ) , C d = ( x ( d ) , ∞ ) . C_0 = (-\infty, x_{(1)}], \quad C_s = (x_{(s)}, x_{(s+1)}] \ (1 \le s < d), \quad C_d = (x_{(d)}, \infty). C 0 = ( − ∞ , x ( 1 ) ] , C s = ( x ( s ) , x ( s + 1 ) ] ( 1 ≤ s < d ) , C d = ( x ( d ) , ∞ ) .
Let H d = ⌈ log 2 ( d + 1 ) ⌉ H_d = \lceil\log_2(d+1) \rceil H d = ⌈ log 2 ( d + 1 )⌉ and pad the d + 1 d+1 d + 1 real leaves by zero-probability leaves to obtain a complete binary tree with 2 H d 2^{H_d} 2 H d leaves. Levels are numbered 1 , … , H d 1, \ldots, H_d 1 , … , H d , with the root excluded. A user with value X X X determines the leaf C ( X ) C(X) C ( X ) , draws a level L ⋆ L^\star L ⋆ uniformly from { 1 , … , H d } \{1, \ldots, H_d\} { 1 , … , H d } , and finds the unique node on the path to C ( X ) C(X) C ( X ) at that level [12 ] . The node is represented by a unary vector. With p ε = 1 / 2 p_\varepsilon= 1/2 p ε = 1/2 , q ε = 1 / ( e ε + 1 ) q_\varepsilon= 1/(e^\varepsilon+ 1) q ε = 1/ ( e ε + 1 ) , OUE [30 ] independently releases every bit as one with probability p ε p_\varepsilon p ε when its input bit is one and with probability q ε q_\varepsilon q ε when its input bit is zero. The report consists of the sampled level and the privatized unary vector.
For a node v v v at level ℓ ( v ) \ell(v) ℓ ( v ) , let Z v Z_v Z v be its released bit, or zero on an unsampled level, and define
ψ v ( Z ) = H d 1 { L ⋆ = ℓ ( v ) } Z v − q ε p ε − q ε \psi_v(Z) = H_d \mathbf{1}\{L^\star= \ell(v)\}\frac{Z_v - q_\varepsilon}{p_\varepsilon- q_\varepsilon} ψ v ( Z ) = H d 1 { L ⋆ = ℓ ( v )} p ε − q ε Z v − q ε
The privacy-noise constant and a deterministic score envelope are
ν ε = 4 e ε ( e ε − 1 ) 2 , B d , ε = 1 + 2 H d e ε e ε − 1 . (1) \nu_{\varepsilon} = \frac{4e^{\varepsilon}}{(e^{\varepsilon}-1)^2}, \qquad\mathcal{B}_{d,\varepsilon} = 1 + \frac{2H_d e^{\varepsilon}}{e^{\varepsilon}-1}. \tag*{(1)} ν ε = ( e ε − 1 ) 2 4 e ε , B d , ε = 1 + e ε − 1 2 H d e ε . (1)
For threshold rank r ∈ { 1 , … , d } r \in\{1,\ldots,d\} r ∈ { 1 , … , d } , let D r − \mathcal{D}^{-}_{r} D r − be the canonical disjoint-node decomposition of the first r r r leaves and let D r + \mathcal{D}^{+}_{r} D r + be the decomposition of the complementary leaves. Each decomposition consists of the maximal tree nodes whose leaves lie entirely in the required set. Write w r − = ∣ D r − ∣ w^{-}_{r} = |\mathcal{D}^{-}_{r}| w r − = ∣ D r − ∣ and w r + = ∣ D r + ∣ w^{+}_{r} = |\mathcal{D}^{+}_{r}| w r + = ∣ D r + ∣ ; both are between one and H d H_d H d , and each decomposition contains at most one node at any level. Define
A r = ∑ v ∈ D r − ψ v , B r = 1 − ∑ v ∈ D r + ψ v . A_r = \sum_{v\in\mathcal{D}^{-}_{r}} \psi_v, \qquad B_r = 1-\sum_{v\in\mathcal{D}^{+}_{r}} \psi_v. A r = v ∈ D r − ∑ ψ v , B r = 1 − v ∈ D r + ∑ ψ v .
Both estimate F ( x ( r ) ) F(x_{(r)}) F ( x ( r ) ) . We choose the fusion weight by evaluating the variances and covariance of A r A_r A r and B r B_r B r at a public reference value u ∈ ( 0 , 1 ) u \in(0,1) u ∈ ( 0 , 1 ) for F ( x ( r ) ) F(x_{(r)}) F ( x ( r ) ) . For this anchor, set
a r − ( u ) = H d w r − ν ε + ( 2 H d − 1 ) u , a^{-}_{r}(u) = H_d w^{-}_{r}\nu_{\varepsilon} + (2H_d-1)u, a r − ( u ) = H d w r − ν ε + ( 2 H d − 1 ) u ,
a r + ( u ) = H d w r + ν ε + ( 2 H d − 1 ) ( 1 − u ) , a^{+}_{r}(u) = H_d w^{+}_{r}\nu_{\varepsilon} + (2H_d-1)(1-u), a r + ( u ) = H d w r + ν ε + ( 2 H d − 1 ) ( 1 − u ) ,
λ r ∘ ( u ) = a r + ( u ) a r − ( u ) + a r + ( u ) , \lambda^{\circ}_{r}(u) = \frac{a^{+}_{r}(u)}{a^{-}_{r}(u)+a^{+}_{r}(u)}, λ r ∘ ( u ) = a r − ( u ) + a r + ( u ) a r + ( u ) ,
and form the fused score
G r ( u ) = λ r ∘ ( u ) A r + { 1 − λ r ∘ ( u ) } B r . (2) G_r(u) = \lambda^{\circ}_{r}(u)A_r + \{1-\lambda^{\circ}_{r}(u)\}B_r. \tag*{(2)} G r ( u ) = λ r ∘ ( u ) A r + { 1 − λ r ∘ ( u )} B r . (2)
Proposition 2.1 (Exact fused-score moments). Let p r = F ( x ( r ) ) p_r = F(x_{(r)}) p r = F ( x ( r ) ) . Condition on the pre-report public history, including the threshold list and the anchor u u u , so both are fixed. Then
E A r = E B r = p r , Cov ( A r , B r ) = p r ( 1 − p r ) \mathbb{E}A_r = \mathbb{E}B_r = p_r, \qquad\operatorname{Cov}(A_r,B_r) = p_r(1-p_r) E A r = E B r = p r , Cov ( A r , B r ) = p r ( 1 − p r ) Var ( A r ) = H d w r − ν ε + 2 H d p r − p r 2 , \operatorname{Var}(A_r) = H_d w^{-}_{r}\nu_{\varepsilon} + 2H_d p_r - p_r^2, Var ( A r ) = H d w r − ν ε + 2 H d p r − p r 2 , Var ( B r ) = H d w r + ν ε + 2 H d ( 1 − p r ) − ( 1 − p r ) 2 . \operatorname{Var}(B_r) = H_d w^{+}_{r}\nu_{\varepsilon} + 2H_d(1-p_r) - (1-p_r)^2. Var ( B r ) = H d w r + ν ε + 2 H d ( 1 − p r ) − ( 1 − p r ) 2 . Consequently, G r ( u ) G_r(u) G r ( u ) is unbiased for every anchor fixed by this history. At u = p r u=p_r u = p r ,
Var { G r ( p r ) } = p r ( 1 − p r ) + a r − ( p r ) a r + ( p r ) a r − ( p r ) + a r + ( p r ) ≤ min { Var ( A r ) , Var ( B r ) } . (3) \operatorname{Var}\{G_r(p_r)\} = p_r(1-p_r) + \frac{a^{-}_{r}(p_r)a^{+}_{r}(p_r)}{a^{-}_{r}(p_r)+a^{+}_{r}(p_r)} \le\min\{\operatorname{Var}(A_r),\operatorname{Var}(B_r)\}. \tag*{(3)} Var { G r ( p r )} = p r ( 1 − p r ) + a r − ( p r ) + a r + ( p r ) a r − ( p r ) a r + ( p r ) ≤ min { Var ( A r ) , Var ( B r )} . (3) For an arbitrary anchor u u u ,
Var { G r ( u ) } − Var { G r ( p r ) } = { a r − ( p r ) + a r + ( p r ) } { λ r ∘ ( u ) − λ r ∘ ( p r ) } 2 , (4) \operatorname{Var}\{G_r(u)\} - \operatorname{Var}\{G_r(p_r)\} = \{a^{-}_{r}(p_r)+a^{+}_{r}(p_r)\}\{\lambda^{\circ}_{r}(u)-\lambda^{\circ}_{r}(p_r)\}^2, \tag*{(4)} Var { G r ( u )} − Var { G r ( p r )} = { a r − ( p r ) + a r + ( p r )} { λ r ∘ ( u ) − λ r ∘ ( p r ) } 2 , (4)
with the explicit bound
0 ≤ Var { G r ( u ) } − Var { G r ( p r ) } ≤ ( 2 H d − 1 ) ( u − p r ) 2 . (5) 0 \le\operatorname{Var}\{G_r(u)\}-\operatorname{Var}\{G_r(p_r)\} \le(2H_d-1)(u-p_r)^2. \tag*{(5)} 0 ≤ Var { G r ( u )} − Var { G r ( p r )} ≤ ( 2 H d − 1 ) ( u − p r ) 2 . (5)
Moreover, ∣ G r ( u ) ∣ ≤ B d , ε |G_r(u)| \le B_{d,\varepsilon} ∣ G r ( u ) ∣ ≤ B d , ε almost surely.
At the correct anchor, fusion minimizes variance among linear combinations with weights summing to one. The shorter-side balanced decoder instead chooses A r A_r A r or B r B_r B r by node count. All stages use u = τ j u=\tau_j u = τ j for target j j j , including both density-estimation thresholds. Unbiasedness holds throughout adaptation; (5) makes the variance cost vanish quadratically as the queried CDF value approaches τ j \tau_j τ j .
Adaptive localization
The total horizon n n n and stage fractions are fixed before data collection. Set
n 1 = ⌊ ρ 1 n ⌋ , n 2 = ⌊ ρ 2 n ⌋ , n 3 = n − n 1 − n 2 , (6) n_1=\lfloor\rho_1n\rfloor,\qquad n_2=\lfloor\rho_2n\rfloor,\qquad n_3=n-n_1-n_2, \tag*{(6)} n 1 = ⌊ ρ 1 n ⌋ , n 2 = ⌊ ρ 2 n ⌋ , n 3 = n − n 1 − n 2 , (6)
where ρ s > 0 \rho_s>0 ρ s > 0 and ρ 1 + ρ 2 + ρ 3 = 1 \rho_1+\rho_2+\rho_3=1 ρ 1 + ρ 2 + ρ 3 = 1 . Our default is ( ρ 1 , ρ 2 , ρ 3 ) = ( 0.35 , 0.30 , 0.35 ) (\rho_1,\rho_2,\rho_3)=(0.35,0.30,0.35) ( ρ 1 , ρ 2 , ρ 3 ) = ( 0.35 , 0.30 , 0.35 ) . Each person contributes to exactly one stage; the final score vectors are fresh relative to both learning stages.
Initialize deterministic q 0 , j ∈ [ L , U ] q_{0,j}\in[L,U] q 0 , j ∈ [ L , U ] . Choose a ∈ ( 1 / 2 , 1 ) a\in(1/2,1) a ∈ ( 1/2 , 1 ) and γ t = γ 0 t − a \gamma_t=\gamma_0t^{-a} γ t = γ 0 t − a with γ 0 > 0 \gamma_0>0 γ 0 > 0 . At Stage-1 arrival t t t , the server sorts the current thresholds q t − 1 , 1 , … , q t − 1 , k n q_{t-1,1},\ldots,q_{t-1,k_n} q t − 1 , 1 , … , q t − 1 , k n , retains their target labels, and sends the ordered list to the user. The user releases one tree-OUE report. If target j j j has current rank r t ( j ) r_t(j) r t ( j ) , the server decodes using (2.2)
G t , j ( 1 ) = G r t ( j ) ( τ j ) G_{t,j}^{(1)}=G_{r_t(j)}(\tau_j) G t , j ( 1 ) = G r t ( j ) ( τ j )
after which it updates
q t , j = Π [ L , U ] [ q t − 1 , j − γ t { G t , j ( 1 ) − τ j } ] . (7) q_{t,j}=\Pi_{[L,U]}\left[q_{t-1,j}-\gamma_t\{G_{t,j}^{(1)}-\tau_j\}\right]. \tag*{(7)} q t , j = Π [ L , U ] [ q t − 1 , j − γ t { G t , j ( 1 ) − τ j } ] . (7)
Here Π [ L , U ] \Pi_{[L,U]} Π [ L , U ] clips an iterate to the public bracket. The score is conditionally unbiased:
E { G t , j ( 1 ) ∣ F t − 1 } = F ( q t − 1 , j ) , \mathbb{E}\{G_{t,j}^{(1)}\mid\mathcal{F}_{t-1}\}=F(q_{t-1,j}), E { G t , j ( 1 ) ∣ F t − 1 } = F ( q t − 1 , j ) ,
where F t − 1 \mathcal{F}_{t-1} F t − 1 contains the previous private transcript. Stable tags keep each target attached to its CDF score through coordinate crossings.
The preliminary center is the full Polyak–Ruppert average
q j 0 = q ˉ n 1 , j = 1 n 1 ∑ t = 1 n 1 q t , j . (8) q_j^0=\bar q_{n_1,j}=\frac{1}{n_1}\sum_{t=1}^{n_1}q_{t,j}. \tag*{(8)} q j 0 = q ˉ n 1 , j = n 1 1 t = 1 ∑ n 1 q t , j . (8)
Both the iterates and their average are updated in O ( k n ) O(k_n) O ( k n ) memory. All iterates enter the average; the online identity and tail-average comparison are given in § 2.4 .
Density learning and fresh-score calibration
Stage 2 freezes the preliminary centers and queries q j 0 ± h n q_j^0 \pm h_n q j 0 ± h n with deterministic bandwidth h n > 0 h_n > 0 h n > 0 . The 2 k n 2k_n 2 k n tagged thresholds are sorted once. Every Stage-2 user sends one tree-OUE report, from which the server obtains fused scores G i , j , − ( 2 ) G_{i,j,-}^{(2)} G i , j , − ( 2 ) and G i , j , + ( 2 ) G_{i,j,+}^{(2)} G i , j , + ( 2 ) . Let
G ‾ j , ± ( 2 ) = 1 n 2 ∑ i = 1 n 2 G i , j , ± ( 2 ) \overline{G}_{j,\pm}^{(2)} = \frac{1}{n_2}\sum_{i=1}^{n_2}G_{i,j,\pm}^{(2)} G j , ± ( 2 ) = n 2 1 i = 1 ∑ n 2 G i , j , ± ( 2 )
and define
f ~ j = G ‾ j , + ( 2 ) − G ‾ j , − ( 2 ) 2 h n . (9) \widetilde{f}_j = \frac{\overline{G}_{j,+}^{(2)}-\overline{G}_{j,-}^{(2)}}{2h_n}. \tag*{(9)} f j = 2 h n G j , + ( 2 ) − G j , − ( 2 ) . (9)
For a deterministic sequence ϖ n ↓ 0 \varpi_n \downarrow0 ϖ n ↓ 0 , use the vanishing stabilization
f ^ j = min { ϖ n − 1 , max ( ϖ n , f ~ j ) } . (10) \widehat{f}_j = \min\{\varpi_n^{-1},\max(\varpi_n,\widetilde{f}_j)\}. \tag*{(10)} f j = min { ϖ n − 1 , max ( ϖ n , f j )} . (10)
Consistency makes the clipping inactive with probability tending to one.
Stage 3 again freezes the tagged list q 1 0 , … , q k n 0 q_1^0,\ldots,q_{k_n}^0 q 1 0 , … , q k n 0 . From each new user’s single report, the server obtains a vector
G i ( 3 ) = ( G i , 1 ( 3 ) , … , G i , k n ( 3 ) ) ⊤ , G ‾ j ( 3 ) = n 3 − 1 ∑ i = 1 n 3 G i , j ( 3 ) . G_i^{(3)} = (G_{i,1}^{(3)},\ldots,G_{i,k_n}^{(3)})^\top,\qquad\overline{G}_j^{(3)} = n_3^{-1}\sum_{i=1}^{n_3}G_{i,j}^{(3)}. G i ( 3 ) = ( G i , 1 ( 3 ) , … , G i , k n ( 3 ) ) ⊤ , G j ( 3 ) = n 3 − 1 i = 1 ∑ n 3 G i , j ( 3 ) .
The one-step estimator is
Q ~ j = q j 0 + τ j − G ‾ j ( 3 ) f ^ j . (11) \widetilde{Q}_j = q_j^0 + \frac{\tau_j-\overline{G}_j^{(3)}}{\widehat{f}_j}. \tag*{(11)} Q j = q j 0 + f j τ j − G j ( 3 ) . (11)
Conditional on Stages 1 and 2, the Stage-3 vectors are independent and identically distributed. Write
σ ^ G , j 2 = 1 n 3 ∑ i = 1 n 3 ( G i , j ( 3 ) − G ‾ j ( 3 ) ) 2 . \widehat{\sigma}_{G,j}^{2} = \frac{1}{n_3}\sum_{i=1}^{n_3}\left(G_{i,j}^{(3)}-\overline{G}_j^{(3)}\right)^2. σ G , j 2 = n 3 1 i = 1 ∑ n 3 ( G i , j ( 3 ) − G j ( 3 ) ) 2 .
Write J ^ n = { j : σ ^ G , j > 0 } \widehat{\mathcal{J}}_n=\{j:\widehat{\sigma}_{G,j}>0\} J n = { j : σ G , j > 0 } ; a zero-variance coordinate receives [ L , U ] [L,U] [ L , U ] . Take an empty maximum as zero. For each draw b b b , one independent ξ i ( b ) ∼ N ( 0 , 1 ) \xi_i^{(b)}\sim N(0,1) ξ i ( b ) ∼ N ( 0 , 1 ) multiplies all coordinates of user i i i ’s centered score vector. Sharing this multiplier across coordinates preserves their empirical correlation in the simulated vector. For 1 ≤ b ≤ M 1\le b\le M 1 ≤ b ≤ M , define
T b ∗ = max j ∈ J ^ n ∣ n 3 − 1 / 2 ∑ i = 1 n 3 ξ i ( b ) ( G i , j ( 3 ) − G ‾ j ( 3 ) ) σ ^ G , j ∣ . (12) T_b^*=\max_{j\in\widehat{\mathcal{J}}_n}\left|\frac{n_3^{-1/2}\sum_{i=1}^{n_3}\xi_i^{(b)}\left(G_{i,j}^{(3)}-\overline{G}_j^{(3)}\right)}{\widehat{\sigma}_{G,j}}\right|. \tag*{(12)} T b ∗ = j ∈ J n max σ G , j n 3 − 1/2 ∑ i = 1 n 3 ξ i ( b ) ( G i , j ( 3 ) − G j ( 3 ) ) . (12)
Let T ( 1 ) ∗ ≤ ⋯ ≤ T ( M ) ∗ T^{*}_{(1)} \le\cdots\le T^{*}_{(M)} T ( 1 ) ∗ ≤ ⋯ ≤ T ( M ) ∗ be the ordered multiplier statistics and set
r M , α = min { M , ⌈ ( M + 1 ) ( 1 − α ) ⌉ } , c ^ 1 − α ∗ = T ( r M , α ) ∗ . (13) r_{M,\alpha}=\min\{M,\lceil(M+1)(1-\alpha)\rceil\},\qquad\widehat{c}^{*}_{1-\alpha}=T^{*}_{(r_{M,\alpha})}. \tag*{(13)} r M , α = min { M , ⌈( M + 1 ) ( 1 − α )⌉} , c 1 − α ∗ = T ( r M , α ) ∗ . (13)
The simultaneous intervals are
I n , j = [ Q ˘ j − c ^ 1 − α ∗ σ ^ G , j f ^ j n 3 , Q ˘ j + c ^ 1 − α ∗ σ ^ G , j f ^ j n 3 ] ∩ [ L , U ] . (14) \mathcal{I}_{n,j}=\left[\breve{Q}_{j}-\frac{\widehat{c}^{*}_{1-\alpha}\widehat{\sigma}_{G,j}}{\widehat{f}_{j}\sqrt{n_{3}}},\breve{Q}_{j}+\frac{\widehat{c}^{*}_{1-\alpha}\widehat{\sigma}_{G,j}}{\widehat{f}_{j}\sqrt{n_{3}}}\right]\cap[L,U]. \tag*{(14)} I n , j = [ Q ˘ j − f j n 3 c 1 − α ∗ σ G , j , Q ˘ j + f j n 3 c 1 − α ∗ σ G , j ] ∩ [ L , U ] . (14)
The same reporting rule serves all three stages, with k n k_n k n thresholds for localization and inference and 2 k n 2k_n 2 k n for density estimation. Its unary message uses O ( k n ) O(k_n) O ( k n ) bits. Maintaining running score sums and multiplier-weighted sums gives O ( M k n ) O(Mk_n) O ( M k n ) server memory, independent of the horizon; Section 2.4 gives the identities.
For implementation, the default split is ( 0.35 , 0.30 , 0.35 ) (0.35,0.30,0.35) ( 0.35 , 0.30 , 0.35 ) , Stage 1 uses its full average, and the gain is 0.1 ( U − L ) t − 2 / 3 0.1(U-L)t^{-2/3} 0.1 ( U − L ) t − 2/3 . Initial values linearly interpolate the target probabilities across the public bracket. The bandwidth is the mechanism-specific expression in Section 5 with multiplier one, and stabilization is ϖ n = { log ( n + e ) } − 3 / 2 \varpi_n=\{\log(n+e)\}^{-3/2} ϖ n = { log ( n + e ) } − 3/2 . At M = 500 M=500 M = 500 and α = 0.05 \alpha=0.05 α = 0.05 , (2.13) uses rank 476 and the fixed-M M M coverage limit is 476 / 501 ≈ 0.9501 476/501\approx0.9501 476/501 ≈ 0.9501 .
For the normal design, write Φ \Phi Φ and ϕ \phi ϕ for the standard normal CDF and density. For both standard-normal designs, L F = ϕ ( 0 ) = 1 / 2 π L_F=\phi(0)=1/\sqrt{2\pi} L F = ϕ ( 0 ) = 1/ 2 π is admissible, so the main-design gain γ 0 ≈ 0.411 \gamma_0\approx0.411 γ 0 ≈ 0.411 and the CDF-comparison gain γ 0 = 0.6 \gamma_0=0.6 γ 0 = 0.6 satisfy the gain condition in Assumption 3.4.
The algorithm is online in the one-pass sense and uses memory independent of the stream length for fixed ( M , k n ) (M,k_n) ( M , k n ) . Stage 1 adapts to past reports, whereas Stages 2 and 3 use frozen thresholds. The three boundaries and the coverage statement refer to a horizon fixed before data collection. Scalar confidence-sequence constructions use dynamically growing parallel paths for asymptotic time-uniform validity [6 ] ; the present fixed-terminal construction adds simultaneous calibration over a growing quantile grid.
Streaming memory and monotone post-processing
For each Stage-3 coordinate, a memory-bounded implementation maintains
S 1 , j = ∑ i = 1 n 3 G i , j ( 3 ) , S 2 , j = ∑ i = 1 n 3 ( G i , j ( 3 ) ) 2 . S_{1,j}=\sum_{i=1}^{n_3}G_{i,j}^{(3)},\qquad S_{2,j}=\sum_{i=1}^{n_3}(G_{i,j}^{(3)})^2. S 1 , j = i = 1 ∑ n 3 G i , j ( 3 ) , S 2 , j = i = 1 ∑ n 3 ( G i , j ( 3 ) ) 2 .
Then
G ‾ j ( 3 ) = S 1 , j / n 3 , σ ^ G , j 2 = S 2 , j / n 3 − ( S 1 , j / n 3 ) 2 . \overline{G}_{j}^{(3)}=S_{1,j}/n_3,\qquad\widehat{\sigma}_{G,j}^{2}=S_{2,j}/n_3-(S_{1,j}/n_3)^2. G j ( 3 ) = S 1 , j / n 3 , σ G , j 2 = S 2 , j / n 3 − ( S 1 , j / n 3 ) 2 .
For multiplier draw b b b , maintain
R b , j = ∑ i = 1 n 3 ξ i ( b ) G i , j ( 3 ) , r b = ∑ i = 1 n 3 ξ i ( b ) . R_{b,j}=\sum_{i=1}^{n_3}\xi_i^{(b)}G_{i,j}^{(3)},\qquad r_b=\sum_{i=1}^{n_3}\xi_i^{(b)}. R b , j = i = 1 ∑ n 3 ξ i ( b ) G i , j ( 3 ) , r b = i = 1 ∑ n 3 ξ i ( b ) .
Algorithm 1 Fused one-pass LDP inference for a growing quantile grid
Input: horizon n n n ; target probabilities τ 1 < ⋯ < τ k n \tau_1 < \cdots< \tau_{k_n} τ 1 < ⋯ < τ k n ; public bracket [ L , U ] [L,U] [ L , U ] ; privacy level ε n \varepsilon_n ε n ; split ( ρ 1 , ρ 2 , ρ 3 ) (\rho_1,\rho_2,\rho_3) ( ρ 1 , ρ 2 , ρ 3 ) ; gain ( γ 0 , a ) (\gamma_0,a) ( γ 0 , a ) ; bandwidth h n h_n h n ; stabilization ϖ n \varpi_n ϖ n ; level α \alpha α ; multiplier count M ≥ 1 M \ge1 M ≥ 1 .
Process the cohorts consecutively, indexing users from one within each cohort. The public arrival index alone determines an incoming user’s stage.
Compute ( n 1 , n 2 , n 3 ) (n_1,n_2,n_3) ( n 1 , n 2 , n 3 ) from (2.6). Initialize deterministic q 0 , j ∈ [ L , U ] q_{0,j} \in[L,U] q 0 , j ∈ [ L , U ] and q ‾ 0 , j = 0 \overline{q}_{0,j}=0 q 0 , j = 0 .
For arrivals i = 1 , … , n 1 i=1,\ldots,n_1 i = 1 , … , n 1 (Stage 1 ): sort the current tagged thresholds, obtain one ε n \varepsilon_n ε n -LDP tree-OUE report, decode all fused scores with anchors τ j \tau_j τ j , update (2.7), and update the full average by (2.15). Set q j 0 = q ‾ n 1 , j q^0_j=\overline{q}_{n_1,j} q j 0 = q n 1 , j .
For arrivals i = 1 , … , n 2 i=1,\ldots,n_2 i = 1 , … , n 2 (Stage 2 ): use the fixed tagged list q j 0 ± h n q^0_j \pm h_n q j 0 ± h n , obtain one report per user, and update the 2 k n 2k_n 2 k n running score sums. Compute f ~ j \widetilde{f}_j f j and f ^ j \widehat{f}_j f j from (2.9)–(2.10).
Before Stage 3, independently generate multiplier streams { ξ i ( b ) : 1 ≤ i ≤ n 3 , 1 ≤ b ≤ M } \{\xi_i^{(b)}:1\le i\le n_3,1\le b\le M\} { ξ i ( b ) : 1 ≤ i ≤ n 3 , 1 ≤ b ≤ M } from a public random seed.
For arrivals i = 1 , … , n 3 i=1,\ldots,n_3 i = 1 , … , n 3 (Stage 3 ): use the fixed list q j 0 q^0_j q j 0 , obtain one report, and update for every j j j the running sums ∑ i G i , j ( 3 ) \sum_i G_{i,j}^{(3)} ∑ i G i , j ( 3 ) , ∑ i ( G i , j ( 3 ) ) 2 \sum_i(G_{i,j}^{(3)})^2 ∑ i ( G i , j ( 3 ) ) 2 , and ∑ i ξ i ( b ) G i , j ( 3 ) \sum_i\xi_i^{(b)}G_{i,j}^{(3)} ∑ i ξ i ( b ) G i , j ( 3 ) for b ≤ M b\le M b ≤ M , together with ∑ i ξ i ( b ) \sum_i\xi_i^{(b)} ∑ i ξ i ( b ) .
Compute Q ^ j \widehat{Q}_j Q j , σ ^ G , j \widehat{\sigma}_{G,j} σ G , j , T b ∗ T_b^* T b ∗ , and the intervals in (2.11)–(2.14). Take the maximum over J n = { j : σ ^ G , j > 0 } \mathcal{J}_n=\{j:\widehat{\sigma}_{G,j}>0\} J n = { j : σ G , j > 0 } , using zero if this set is empty; return [ L , U ] [L,U] [ L , U ] for excluded coordinates. Optionally apply the monotone interval refinement in Proposition 2.2.
Output: { Q ^ j , I n , j : 1 ≤ j ≤ k n } \{\widehat{Q}_j,I_{n,j}:1\le j\le k_n\} { Q j , I n , j : 1 ≤ j ≤ k n } .
The centered numerator in (2.12) is
n 3 − 1 / 2 ( R b , j − r b S 1 , j / n 3 ) . n_3^{-1/2}\left(R_{b,j}-r_bS_{1,j}/n_3\right). n 3 − 1/2 ( R b , j − r b S 1 , j / n 3 ) .
These identities give O ( M k n ) O(Mk_n) O ( M k n ) server memory, independent of the stream length. Vanilla tree-OUE uses O ( k n ) O(k_n) O ( k n ) report bits. Compact alternatives such as optimized local hashing or Hadamard response require a channel-specific fusion covariance [30 , 2 ] . Floating-point implementations can compute variances with Welford’s stable online recurrence. The simulation code returns [ L , U ] [L,U] [ L , U ] for all coordinates if any estimated score variance is numerically zero or the covariance factorization fails.
Because Q 1 ≤ ⋯ ≤ Q k n Q_1\le\cdots\le Q_{k_n} Q 1 ≤ ⋯ ≤ Q k n , define from raw intervals [ L j I , U j I ] [L^I_j,U^I_j] [ L j I , U j I ]
L ~ j I = max ℓ ≤ j L ℓ I , U ~ j I = min ℓ ≥ j U ℓ I . \widetilde{L}^I_j=\max_{\ell\le j}L^I_\ell,\qquad\widetilde{U}^I_j=\min_{\ell\ge j}U^I_\ell. L j I = ℓ ≤ j max L ℓ I , U j I = ℓ ≥ j min U ℓ I .
Proposition 2.2 (Coverage-preserving monotone refinement). If Q j ∈ [ L j I , U j I ] Q_j\in[L^I_j,U^I_j] Q j ∈ [ L j I , U j I ] for every j j j , then Q j ∈ [ L ~ j I , U ~ j I ] Q_j\in[\widetilde{L}^I_j,\widetilde{U}^I_j] Q j ∈ [ L j I , U j I ] for every j j j .
The full Stage-1 average is maintained without storing the path:
q ‾ t , j = q ‾ t − 1 , j + t − 1 ( q t , j − q ‾ t − 1 , j ) . (15) \overline{q}_{t,j}=\overline{q}_{t-1,j}+t^{-1}(q_{t,j}-\overline{q}_{t-1,j}). \tag*{(15)} q t , j = q t − 1 , j + t − 1 ( q t , j − q t − 1 , j ) . (15)
The full average uses every projected iterate and preserves the entire Stage-1 sample.
Proposition 2.3 (Full versus delayed averaging). For 0 ≤ b < n 1 0 \le b < n_1 0 ≤ b < n 1 , let
q ‾ n 1 , j ( b ) = ( n 1 − b ) − 1 ∑ t = b + 1 n 1 q t , j . \overline{q}^{(b)}_{n_1,j}=(n_1-b)^{-1}\sum_{t=b+1}^{n_1}q_{t,j}. q n 1 , j ( b ) = ( n 1 − b ) − 1 t = b + 1 ∑ n 1 q t , j . Then, deterministically,
max j ≤ k n ∣ q ‾ n 1 , j ( b ) − q ‾ n 1 , j ∣ ≤ ( U − L ) b n 1 . \max_{j\le k_n}\left|\overline{q}^{(b)}_{n_1,j}-\overline{q}_{n_1,j}\right|\le(U-L)\frac{b}{n_1}. j ≤ k n max q n 1 , j ( b ) − q n 1 , j ≤ ( U − L ) n 1 b . Thus full and delayed averages are equivalent at rate r 1 n r_{1n} r 1 n when b / n 1 = o ( r 1 n ) b/n_1=o(r_{1n}) b / n 1 = o ( r 1 n ) .
The active set J ^ n \widehat{\mathcal{J}}_n J n and the zero-variance fallback are defined in § 2.3 . By Lemmas E.1 and E.2,
P { J ^ n = { 1 , … , k n } } ⟶ 1. \mathbb{P}\left\{\widehat{\mathcal{J}}_n=\{1,\ldots,k_n\}\right\}\longrightarrow1. P { J n = { 1 , … , k n } } ⟶ 1.
Theoretical guarantees
We state the regularity and growth conditions, then give the learning rates and simultaneous inference guarantees.
Assumptions
Write ℓ n = log { 2 k n ( n + 1 ) } \ell_n=\log\{2k_n(n+1)\} ℓ n = log { 2 k n ( n + 1 )} . For a threshold list of length d d d , use H d H_d H d , ν ε n \nu_{\varepsilon_n} ν ε n , and B d , ε n B_{d,\varepsilon_n} B d , ε n from (1) . Set B 1 n = B k n , ε n B_{1n}=B_{k_n,\varepsilon_n} B 1 n = B k n , ε n , B 2 n = B 2 k n , ε n B_{2n}=B_{2k_n,\varepsilon_n} B 2 n = B 2 k n , ε n .
Assumption 3.1 (Sampling, targets, and interiority). The observations are i.i.d. with continuous CDF F F F . There are constants δ 0 > 0 \delta_0>0 δ 0 > 0 and 0 < τ − < τ + < 1 0<\tau_-<\tau_+<1 0 < τ − < τ + < 1 such that, for every n n n ,
τ − ≤ τ 1 , n < ⋯ < τ k n , n ≤ τ + , Q j , n ∈ [ L + 3 δ 0 , U − 3 δ 0 ] ( 1 ≤ j ≤ k n ) . \tau_-\le\tau_{1,n}<\cdots<\tau_{k_n,n}\le\tau_+,\qquad Q_{j,n}\in[L+3\delta_0,U-3\delta_0]\quad(1\le j\le k_n). τ − ≤ τ 1 , n < ⋯ < τ k n , n ≤ τ + , Q j , n ∈ [ L + 3 δ 0 , U − 3 δ 0 ] ( 1 ≤ j ≤ k n ) . Every user participates exactly once and uses independent local randomization conditional on the public transcript.
The target spacing may decrease with n n n . Stable tags preserve target identities when close thresholds cross during Stage 1 or coincide after finite-precision rounding, and the score remains unbiased at each tagged threshold. The empirical multiplier incorporates the resulting cross-quantile correlation.
Assumption 3.2 (Local quantile regularity). For some β ∈ ( 0 , 1 ] \beta\in(0,1] β ∈ ( 0 , 1 ] , the CDF is absolutely continuous on
N n = ⋃ j ≤ k n [ Q j , n − 2 δ 0 , Q j , n + 2 δ 0 ] \mathcal{N}_n=\bigcup_{j\le k_n}[Q_{j,n}-2\delta_0,Q_{j,n}+2\delta_0] N n = j ≤ k n ⋃ [ Q j , n − 2 δ 0 , Q j , n + 2 δ 0 ]
with density f f f satisfying, uniformly on N n \mathcal{N}_n N n ,
0 < f − ≤ f ( x ) ≤ f + < ∞ , ∣ f ( x ) − f ( y ) ∣ ≤ L f ∣ x − y ∣ β . 0 < f_- \le f(x) \le f_+ < \infty, \qquad|f(x)-f(y)| \le L_f|x-y|^\beta. 0 < f − ≤ f ( x ) ≤ f + < ∞ , ∣ f ( x ) − f ( y ) ∣ ≤ L f ∣ x − y ∣ β .
The constants do not depend on n n n .
Positivity and local continuity of the density are standard regular-quantile conditions for Bahadur and one-step expansions ([5 , 29 ] ); closely related local conditions are used for online locally private quantile inference in Liu et al. [21 ] . The lower bound f − > 0 f_->0 f − > 0 identifies each quantile locally and converts CDF error into quantile error. The β \beta β -Hölder bound controls both the density bias in (D.1) and the one-step remainder in (D.4), uniformly over the growing grid. A locally Lipschitz density gives β = 1 \beta=1 β = 1 ; a common modulus of continuity can be used in the same arguments when explicit polynomial rates are less important. Extreme targets with vanishing density require the corresponding nonregular quantile normalization.
To control Stage 1 from any initialization in the projection bracket, we use the following secant condition.
Assumption 3.3 (Uniform Stage-1 identification). There are constants 0 < μ ≤ L F < ∞ 0 < \mu\le L_F < \infty 0 < μ ≤ L F < ∞ such that for every n n n , every j ≤ k n j \le k_n j ≤ k n , and every q ∈ [ L , U ] q \in[L,U] q ∈ [ L , U ] ,
μ ∣ q − Q j , n ∣ ≤ ∣ F ( q ) − τ j , n ∣ ≤ L F ∣ q − Q j , n ∣ , ( q − Q j , n ) { F ( q ) − τ j , n } ≥ 0. (16) \mu|q-Q_{j,n}| \le|F(q)-\tau_{j,n}| \le L_F|q-Q_{j,n}|,\qquad(q-Q_{j,n})\{F(q)-\tau_{j,n}\}\ge0. \tag*{(16)} μ ∣ q − Q j , n ∣ ≤ ∣ F ( q ) − τ j , n ∣ ≤ L F ∣ q − Q j , n ∣ , ( q − Q j , n ) { F ( q ) − τ j , n } ≥ 0. (16)
Assumption 3.3 is the monotone root-identification condition for the projected Robbins–Monro step on [ L , U ] [L,U] [ L , U ] . Together with the decreasing gain in Assumption 3.4, it follows the standard stochastic-approximation setup of Robbins and Monro (1951); Polyak and Juditsky (1992); Kushner and Yin (2003). One sufficient condition is absolute continuity on [ L , U ] [L,U] [ L , U ] with 0 < μ ≤ f ( x ) ≤ L F < ∞ 0 < \mu\le f(x) \le L_F < \infty 0 < μ ≤ f ( x ) ≤ L F < ∞ almost everywhere, since
F ( q ) − F ( Q j ) = ∫ Q j q f ( x ) d x F(q)-F(Q_j)=\int_{Q_j}^{q}f(x)\,\mathrm{d}x F ( q ) − F ( Q j ) = ∫ Q j q f ( x ) d x
gives (16) . In fact, local regularity in Assumption 3.2 suffices on the fixed bracket. For ∣ q − Q j ∣ ≤ δ 0 |q-Q_j|\le\delta_0 ∣ q − Q j ∣ ≤ δ 0 , integration gives secant bounds f − f_- f − and f + f_+ f + . If q ≥ Q j + δ 0 q\ge Q_j+\delta_0 q ≥ Q j + δ 0 , monotonicity gives
f − δ 0 U − L ≤ F ( q ) − F ( Q j ) q − Q j ≤ 1 δ 0 , \frac{f_- \delta_0}{U-L}\le\frac{F(q)-F(Q_j)}{q-Q_j}\le\frac{1}{\delta_0}, U − L f − δ 0 ≤ q − Q j F ( q ) − F ( Q j ) ≤ δ 0 1 ,
and the same bounds hold on the left of Q j Q_j Q j . Thus (16) holds with μ = min { f − , f − δ 0 / ( U − L ) } \mu=\min\{f_-,f_-\delta_0/(U-L)\} μ = min { f − , f − δ 0 / ( U − L )} and L F = max { f + , 1 / δ 0 } L_F=\max\{f_+,1/\delta_0\} L F = max { f + , 1/ δ 0 } . The burn-in conditions below then control early private-noise excursions.
The index b n b_n b n below marks entry into the local neighborhood in the analysis; the implemented full average retains every Stage-1 iterate.
Assumption 3.4 (Gain, stage sizes, and localization). The gain is γ t = γ 0 t − a \gamma_t=\gamma_0t^{-a} γ t = γ 0 t − a with a ∈ ( 1 / 2 , 1 ) a\in(1/2,1) a ∈ ( 1/2 , 1 )
and fixed 0 < γ 0 ≤ 1 2 L F 0 < \gamma_0 \le\frac{1}{2L_F} 0 < γ 0 ≤ 2 L F 1 .
The initial values are deterministic in [ L , U ] [L,U] [ L , U ] . There is a deterministic integer b n ∈ { 1 , … , n 1 − 1 } b_n \in\{1,\ldots,n_1-1\} b n ∈ { 1 , … , n 1 − 1 } satisfying
b n n 1 → 0 , (17) \frac{b_n}{n_1} \to0, \tag*{(17)} n 1 b n → 0 , (17)
exp ( − μ 2 ∑ t = 1 b n γ t ) ( U − L ) = o { min ( r 1 n , δ 0 ) } , (18) \exp\left(-\frac{\mu}{2}\sum_{t=1}^{b_n}\gamma_t\right)(U-L)=o\{\min(r_{1n},\delta_0)\}, \tag*{(18)} exp ( − 2 μ t = 1 ∑ b n γ t ) ( U − L ) = o { min ( r 1 n , δ 0 )} , (18)
B 1 n { γ b n ℓ n + γ b n ℓ n } = o ( δ 0 ) , (19) B_{1n}\left\{\sqrt{\gamma_{b_n}\ell_n}+\gamma_{b_n}\ell_n\right\}=o(\delta_0), \tag*{(19)} B 1 n { γ b n ℓ n + γ b n ℓ n } = o ( δ 0 ) , (19)
Here r 1 n r_{1n} r 1 n is defined in (20) below. Together with Assumptions 3.1 and 3.3 , conditions (3.2)–(3.4) give uniform entry into the local neighborhood and eventual inactivity of the projection; a direct choice of b n b_n b n is given in Lemma C.1.
The explicit preliminary rate is
r 1 n = b n n 1 + B 1 n ℓ n n 1 + B 1 n n 1 a / 2 − 1 ℓ n + B 1 n 1 + β n 1 − a ( 1 + β ) / 2 ℓ n ( 1 + β ) / 2 . (20) \begin{aligned}
r_{1n}={}&\frac{b_n}{n_1}+B_{1n}\sqrt{\frac{\ell_n}{n_1}}+B_{1n}n_1^{a/2-1}\sqrt{\ell_n}\\
&+B_{1n}^{1+\beta}n_1^{-a(1+\beta)/2}\ell_n^{(1+\beta)/2}. \tag*{(20)}
\end{aligned} r 1 n = n 1 b n + B 1 n n 1 ℓ n + B 1 n n 1 a /2 − 1 ℓ n + B 1 n 1 + β n 1 − a ( 1 + β ) /2 ℓ n ( 1 + β ) /2 . (20)
The four terms correspond to the initial segment, the averaged martingale, the Abel endpoint, and the nonlinear Hölder remainder.
Assumption 3.5 (Density stage). The bandwidth satisfies h n → 0 h_n \to0 h n → 0 , h n < δ 0 h_n < \delta_0 h n < δ 0 , and
d n = r 1 n β + h n β + B 2 n h n ( ℓ n n 2 + ℓ n n 2 ) → 0. d_n=r_{1n}^{\beta}+h_n^{\beta}+\frac{B_{2n}}{h_n}\left(\sqrt{\frac{\ell_n}{n_2}}+\frac{\ell_n}{n_2}\right)\to0. d n = r 1 n β + h n β + h n B 2 n ( n 2 ℓ n + n 2 ℓ n ) → 0. The deterministic clipping sequence obeys ϖ n ↓ 0 \varpi_n \downarrow0 ϖ n ↓ 0 and ϖ n − 1 → ∞ \varpi_n^{-1}\to\infty ϖ n − 1 → ∞ .
Let p j 0 = F ( q j 0 ) p_j^0=F(q_j^0) p j 0 = F ( q j 0 ) and, for a Stage-3 observation, define
Y i , j = G i , j ( 3 ) − p j 0 , σ j , n 2 = E ( Y i , j 2 ∣ F n 1 + n 2 ) . Y_{i,j}=G_{i,j}^{(3)}-p_j^0,\qquad\sigma_{j,n}^2=\mathbb{E}(Y_{i,j}^2\mid\mathcal{F}_{n_1+n_2}). Y i , j = G i , j ( 3 ) − p j 0 , σ j , n 2 = E ( Y i , j 2 ∣ F n 1 + n 2 ) . Let
σ n = min j ≤ k n σ j , n , K n = 2 B 1 n σ n . \sigma_n=\min_{j\le k_n}\sigma_{j,n},\qquad K_n=\frac{2B_{1n}}{\sigma_n}. σ n = j ≤ k n min σ j , n , K n = σ n 2 B 1 n . By Proposition 2.1 , ∣ Y i , j ∣ / σ j , n ≤ K n |Y_{i,j}|/\sigma_{j,n}\le K_n ∣ Y i , j ∣/ σ j , n ≤ K n almost surely conditional on the first two stages. The resulting support and variance bounds are established in Lemma E.1.
Assumption 3.6 (High-dimensional approximation and one-step remainder). *The following
random rates converge to zero in probability:
( K n 2 ℓ n 7 n 3 ) 1 / 6 = o P ( 1 ) , (21) \left(\frac{K_n^2\ell_n^7}{n_3}\right)^{1/6}=o_{\mathbb{P}}(1), \tag*{(21)} ( n 3 K n 2 ℓ n 7 ) 1/6 = o P ( 1 ) , (21)
n 3 ℓ n σ n { r 1 n d n + r 1 n 1 + β } = o P ( 1 ) . (22) \frac{\sqrt{n_3}\ell_n}{\sigma_n}\left\{r_{1n}d_n+r_{1n}^{1+\beta}\right\}=o_{\mathbb{P}}(1). \tag*{(22)} σ n n 3 ℓ n { r 1 n d n + r 1 n 1 + β } = o P ( 1 ) . (22)
For an empirical multiplier quantile based on M n M_n M n draws, assume M n → ∞ M_n \to\infty M n → ∞ . The exact conditional multiplier quantile is the theoretical reference.
The first condition is the Gaussian approximation condition for bounded high-dimensional vectors in Chernozhukov et al. [10 ] ; the second makes the one-step remainder negligible on the maximum scale. Corollary 3.11 gives a simple growth regime that implies both conditions.
Localization and density rates
The Stage-1 and Stage-2 arguments are collected in Sections C and D. They establish the uniform rates max j ≤ k n ∣ q j 0 − Q j , n ∣ = O P ( r 1 n ) \max_{j\le k_n}|q_j^0-Q_{j,n}|=O_{\mathbb{P}}(r_{1n}) max j ≤ k n ∣ q j 0 − Q j , n ∣ = O P ( r 1 n ) and max j ≤ k n ∣ f ^ j − f ( Q j , n ) ∣ = O P ( d n ) \max_{j\le k_n}|\widehat f_j-f(Q_{j,n})|=O_{\mathbb{P}}(d_n) max j ≤ k n ∣ f j − f ( Q j , n ) ∣ = O P ( d n ) ; see Theorems 3.7 and 3.8 . The term r 1 n β r_{1n}^{\beta} r 1 n β in d n d_n d n accounts for centering the finite difference at the estimated quantile. For β = 1 \beta=1 β = 1 , balancing its bandwidth and stochastic terms gives h n ≍ { B 2 n 2 ℓ n / n 2 } 1 / 4 h_n\asymp\{B_{2n}^2\ell_n/n_2\}^{1/4} h n ≍ { B 2 n 2 ℓ n / n 2 } 1/4 .
Theorem 3.7 (Full-average preliminary rate). Suppose Assumptions 3.1 to 3.4 hold. Then the full online average in (2.8) satisfies
max j ≤ k n ∣ q j 0 − Q j , n ∣ = O P ( r 1 n ) . (23) \max_{j\le k_n}|q_j^0-Q_{j,n}|=O_{\mathbb{P}}(r_{1n}). \tag*{(23)} j ≤ k n max ∣ q j 0 − Q j , n ∣ = O P ( r 1 n ) . (23) On an event with probability tending to one, it also admits the expansion
f ( Q j , n ) ( q j 0 − Q j , n ) = − 1 n 1 ∑ t = b n + 1 n 1 ζ t , j + R 1 n , j , (24) f(Q_{j,n})(q_j^0-Q_{j,n})=-\frac{1}{n_1}\sum_{t=b_n+1}^{n_1}\zeta_{t,j}+R_{1n,j}, \tag*{(24)} f ( Q j , n ) ( q j 0 − Q j , n ) = − n 1 1 t = b n + 1 ∑ n 1 ζ t , j + R 1 n , j , (24) where ζ t , j = G t , j ( 1 ) − F ( q t − 1 , j ) \zeta_{t,j}=G_{t,j}^{(1)}-F(q_{t-1,j}) ζ t , j = G t , j ( 1 ) − F ( q t − 1 , j ) and max j ≤ k n ∣ R 1 n , j ∣ \max_{j\le k_n}|R_{1n,j}| max j ≤ k n ∣ R 1 n , j ∣ has the order given by the early-iterate, Abel-endpoint, and nonlinear terms in (3.5).
Theorem 3.8 (Uniform private density rate). Suppose Assumptions 3.1, 3.2 and 3.5 hold and (3.8) is valid. Then
max j ≤ k n ∣ f ^ j − f ( Q j , n ) ∣ = O P ( d n ) . (25) \max_{j\le k_n}|\widehat f_j-f(Q_{j,n})|=O_{\mathbb{P}}(d_n). \tag*{(25)} j ≤ k n max ∣ f j − f ( Q j , n ) ∣ = O P ( d n ) . (25) With probability tending to one, all q j 0 ± h n q_j^0\pm h_n q j 0 ± h n lie in the interior neighborhood and both clipping operations in (2.10) are inactive.
In applications, the minimum estimated density, the number of active clipping operations, and bandwidth sensitivity help identify quantiles with weak local information.
One-step expansion and simultaneous coverage
Theorem 3.9 (Uniform one-step representation). Suppose Assumptions 3.1, 3.2 and 3.5 hold and (3.8) and (3.10) are valid. Then
max j ≤ k n ∣ f ^ j ( Q ~ j − Q j , n ) + 1 n 3 ∑ i = 1 n 3 Y i , j ∣ = O P ( R n ) , R n = r 1 n d n + r 1 n 1 + β . (26) \max_{j\le k_n}\left|\widehat{f}_j(\widetilde{Q}_j-Q_{j,n})+\frac{1}{n_3}\sum_{i=1}^{n_3}Y_{i,j}\right|=O_{\mathrm{P}}(R_n), \qquad R_n=r_{1n}d_n+r_{1n}^{1+\beta}. \tag*{(26)} j ≤ k n max f j ( Q j − Q j , n ) + n 3 1 i = 1 ∑ n 3 Y i , j = O P ( R n ) , R n = r 1 n d n + r 1 n 1 + β . (26)
The conditional mean of τ j − G ‾ j ( 3 ) \tau_j-\overline{G}_j^{(3)} τ j − G j ( 3 ) is τ j − F ( q j 0 ) \tau_j-F(q_j^0) τ j − F ( q j 0 ) . Dividing by f ^ j \widehat{f}_j f j therefore cancels the linear location error. The remainder R n R_n R n has a direct interpretation: estimating the derivative costs r 1 n d n r_{1n}d_n r 1 n d n , and linearizing F F F costs r 1 n 1 + β r_{1n}^{1+\beta} r 1 n 1 + β . The simultaneous transfer condition above makes these errors small even after taking the maximum over targets.
Let c 1 − α ∗ c_{1-\alpha}^* c 1 − α ∗ denote the exact conditional ( 1 − α ) (1-\alpha) ( 1 − α ) quantile of (2.12) given the observed Stage-3 scores and the first two stages. Let I n , j ∗ \mathcal{I}_{n,j}^* I n , j ∗ denote the interval in (2.14) with c ^ 1 − α ∗ \widehat{c}_{1-\alpha}^* c 1 − α ∗ replaced by c 1 − α ∗ c_{1-\alpha}^* c 1 − α ∗ .
Theorem 3.10 (Growing-grid multiplier validity). Suppose Assumptions 3.1 to 3.6 hold. Define
T n = max j ∈ J n ∣ n 3 f ^ j ( Q ~ j − Q j , n ) σ ^ G , j ∣ . T_n=\max_{j\in\mathcal{J}_n}\left|\frac{\sqrt{n_3}\widehat{f}_j(\widetilde{Q}_j-Q_{j,n})}{\widehat{\sigma}_{G,j}}\right|. T n = j ∈ J n max σ G , j n 3 f j ( Q j − Q j , n ) . Then, for every fixed 0 < α 0 < 1 / 2 0<\alpha_0<1/2 0 < α 0 < 1/2 ,
sup α ∈ [ α 0 , 1 − α 0 ] ∣ P { T n ≤ c 1 − α ∗ } − ( 1 − α ) ∣ ⟶ 0. (27) \sup_{\alpha\in[\alpha_0,1-\alpha_0]}\left|\mathbb{P}\{T_n\le c_{1-\alpha}^*\}-(1-\alpha)\right|\longrightarrow0. \tag*{(27)} α ∈ [ α 0 , 1 − α 0 ] sup P { T n ≤ c 1 − α ∗ } − ( 1 − α ) ⟶ 0. (27) Consequently,
P { Q j , n ∈ I n , j ∗ for all j ≤ k n } ⟶ 1 − α . (28) \mathbb{P}\{Q_{j,n}\in\mathcal{I}_{n,j}^* \text{ for all }j\le k_n\}\longrightarrow1-\alpha. \tag*{(28)} P { Q j , n ∈ I n , j ∗ for all j ≤ k n } ⟶ 1 − α . (28) If the empirical quantile based on M n → ∞ M_n\to\infty M n → ∞ multiplier draws is used, then (3.12) and (3.13) remain valid with c ^ 1 − α ∗ \widehat{c}_{1-\alpha}^* c 1 − α ∗ and I n , j \mathcal{I}_{n,j} I n , j in place of c 1 − α ∗ c_{1-\alpha}^* c 1 − α ∗ and I n , j ∗ \mathcal{I}_{n,j}^* I n , j ∗ , respectively. Here the probability also averages over the independent calibration multipliers. If instead M M M is fixed, then for every fixed α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) ,
P { T n ≤ c ^ 1 − α ∗ } ⟶ r M , α M + 1 , (29) \mathbb{P}\{T_n\le\widehat{c}_{1-\alpha}^*\}\longrightarrow\frac{r_{M,\alpha}}{M+1}, \tag*{(29)} P { T n ≤ c 1 − α ∗ } ⟶ M + 1 r M , α , (29) and the simultaneous coverage probability has the same limit.
The multiplier uses the dependence among neighboring quantiles through each user’s score vector, calibrating their maximum error jointly.
The fixed positive cohort fractions used by the procedure give a simple allocation satisfying the stage-size requirements. More generally, the proofs require n 1 , n 2 , n 3 → ∞ n_1,n_2,n_3\to\infty n 1 , n 2 , n 3 → ∞ together with Assumptions 3.4 to 3.6. In particular, n 2 / n → 0 n_2/n\to0 n 2 / n → 0 is allowed when the density consistency and one-step remainder conditions remain valid, including
B 2 n h n ℓ n n 2 ⟶ 0. \frac{B_{2n}}{h_n}\sqrt{\frac{\ell_n}{n_2}}\longrightarrow0. h n B 2 n n 2 ℓ n ⟶ 0.
Increasing n 3 n_3 n 3 improves first-order precision after Stage 1 has localized the targets and Stage 2 has estimated their densities accurately. This is the tradeoff illustrated by the allocation results in § 5.1 : smaller learning cohorts can increase the remainder even while n 3 n_3 n 3 reduces the leading variance.
Corollary 3.11 (Width and grid growth). Under the assumptions of Theorem 3.10,
max j ≤ k n halfwidth ( I n , j ) = O P { H k n 1 + ν ε n log ( 2 k n ) f − n 3 } . (30) \max_{j \le k_n} \operatorname{halfwidth}(I_{n,j}) = O_{\mathbb{P}}\left\{ \frac{H_{k_n}\sqrt{1+\nu_{\varepsilon_n}}\sqrt{\log(2k_n)}}{f_{-}\sqrt{n_3}} \right\}. \tag*{(30)} j ≤ k n max halfwidth ( I n , j ) = O P { f − n 3 H k n 1 + ν ε n log ( 2 k n ) } . (30) For 0 < ε n ≤ 1 0 < \varepsilon_n \le1 0 < ε n ≤ 1 , this is
O P { H k n log ( 2 k n ) ε n f − n 3 } . (31) O_{\mathbb{P}}\left\{ \frac{H_{k_n}\sqrt{\log(2k_n)}}{\varepsilon_n f_{-}\sqrt{n_3}} \right\}. \tag*{(31)} O P { ε n f − n 3 H k n log ( 2 k n ) } . (31) If ε n \varepsilon_n ε n is bounded away from zero, n s / n → ρ s ∈ ( 0 , 1 ) n_s/n \to\rho_s \in(0,1) n s / n → ρ s ∈ ( 0 , 1 ) , a = 2 / 3 a = 2/3 a = 2/3 , β = 1 \beta= 1 β = 1 , and
log 9 { 2 k n ( n + 1 ) } n ⟶ 0 , (32) \frac{\log^9\{2k_n(n+1)\}}{n} \longrightarrow0, \tag*{(32)} n log 9 { 2 k n ( n + 1 )} ⟶ 0 , (32) then the conditions of Theorem 3.10 hold for the bandwidth
h n ≍ { B 2 n 2 ℓ n n 2 } 1 / 4 h_n \asymp\left\{ \frac{B_{2n}^2\ell_n}{n_2} \right\}^{1/4} h n ≍ { n 2 B 2 n 2 ℓ n } 1/4 provided b n / n = o ( ℓ n 3 / 2 n − 1 / 2 ) b_n/n = o(\ell_n^{3/2}n^{-1/2}) b n / n = o ( ℓ n 3/2 n − 1/2 ) . In particular, every polynomially growing k n k_n k n is allowed.
The width bound in (30) separates the private-score scale H k n 1 + ν ε n H_{k_n}\sqrt{1+\nu_{\varepsilon_n}} H k n 1 + ν ε n from the simultaneous calibration factor log ( 2 k n ) \sqrt{\log(2k_n)} log ( 2 k n ) . The density lower bound converts CDF error into quantile error. Thus, at fixed privacy and density bounds, grid size enters this upper bound only through logarithmic factors, while precision improves at the usual square-root rate in the inference cohort size n 3 n_3 n 3 . The general bound also allows ε n \varepsilon_n ε n to vary through the score variance and envelope. For small ε n \varepsilon_n ε n , ν ε n ≍ ε n − 2 \nu_{\varepsilon_n} \asymp\varepsilon_n^{-2} ν ε n ≍ ε n − 2 and B d , ε n ≍ H d ε n − 1 B_{d,\varepsilon_n} \asymp H_d\varepsilon_n^{-1} B d , ε n ≍ H d ε n − 1 , displaying the effective private sample size in each rate.
Condition (32) combines the tree-score envelope, density estimation, Gaussian approximation, and anti-concentration in one simple rate. It allows k n = exp { o ( n 1 / 9 ) } k_n = \exp\{o(n^{1/9})\} k n = exp { o ( n 1/9 )} , including every polynomially growing grid.
Fixed-chain calibration
Restarted-chain procedures
This subsection defines the blockwise procedures used in the calibration comparison. Let J \mathcal{J} J be the number of blocks and Q ^ b = ( Q ^ b , 1 , … , Q ^ b , k n ) ⊤ \widehat{Q}_b = (\widehat{Q}_{b,1}, \ldots, \widehat{Q}_{b,k_n})^\top Q b = ( Q b , 1 , … , Q b , k n ) ⊤ the averaged private stochastic-approximation output from block b b b . The block aggregate and coordinate scales are
Q ~ = J − 1 ∑ b = 1 J Q ^ b , s j 2 = J − 1 ∑ b = 1 J ( Q ^ b , j − Q ~ j ) 2 . \widetilde{Q}=J^{-1}\sum_{b=1}^{J}\widehat{Q}_b,\qquad s_j^2=J^{-1}\sum_{b=1}^{J}\left(\widehat{Q}_{b,j}-\widetilde{Q}_j\right)^2. Q = J − 1 b = 1 ∑ J Q b , s j 2 = J − 1 b = 1 ∑ J ( Q b , j − Q j ) 2 .
The raw chain multiplier statistic is
T c h a i n ∗ = max j ≤ k n ∣ J − 1 / 2 ∑ b = 1 J ξ b ( Q ^ b , j − Q ~ j ) S j ∣ . T_{\mathrm{chain}}^*=\max_{j\leq k_n}\left|\frac{J^{-1/2}\sum_{b=1}^{J}\xi_b\left(\widehat{Q}_{b,j}-\widetilde{Q}_j\right)}{S_j}\right|. T chain ∗ = j ≤ k n max S j J − 1/2 ∑ b = 1 J ξ b ( Q b , j − Q j ) .
This raw multiplier approximates the large-J J J regime in which block bias is small relative to S j / J S_j/\sqrt{J} S j / J .
Under a multivariate normal block model, the sample mean is independent of the Wishart sample covariance. The fixed-J J J Student–Wishart comparator simulates this pivot using the public balanced tree-OUE score correlation, thereby retaining the random coordinate scales and cross-coordinate dependence. For restarted stochastic-approximation outputs, it gives the corresponding first-order Gaussian calibration.
More explicitly, let k = k n k=k_n k = k n , let R R R be the public score correlation matrix, and put ν = J − 1 \nu=J-1 ν = J − 1 . Let V ∼ Wishart k ( R , ν ) V\sim\operatorname{Wishart}_k(R,\nu) V ∼ Wishart k ( R , ν ) be independent of Z ∼ N k ( 0 , R ) Z\sim N_k(0,R) Z ∼ N k ( 0 , R ) . Orthogonally separating the block mean from the ν \nu ν residual contrasts gives the exact Gaussian-model maximum
max j ≤ k ∣ Z j ∣ V j j / ν . \max_{j\leq k}\frac{|Z_j|}{\sqrt{V_{jj}/\nu}}. j ≤ k max V j j / ν ∣ Z j ∣ .
This representation remains valid for singular R R R . Its critical value depends on R R R : if R = 11 ⊤ R=\mathbf{1}\mathbf{1}^{\top} R = 1 1 ⊤ , all coordinates coincide and the maximum has the ∣ t ν ∣ |t_\nu| ∣ t ν ∣ distribution for every k k k . The polynomial rate in Proposition 4.2 therefore applies to the Student–Bonferroni calibration; the Student–Wishart rate is determined by the correlation matrix R R R .
The marginal Student–Bonferroni safeguard uses
Q ~ j ± t J − 1 , 1 − α / ( 2 k n ) s j J , s j 2 = ( J − 1 ) − 1 ∑ b = 1 J ( Q ^ b , j − Q ~ j ) 2 . \widetilde{Q}_j\pm t_{J-1,1-\alpha/(2k_n)}\frac{s_j}{\sqrt{J}},\qquad s_j^2=(J-1)^{-1}\sum_{b=1}^{J}\left(\widehat{Q}_{b,j}-\widetilde{Q}_j\right)^2. Q j ± t J − 1 , 1 − α / ( 2 k n ) J s j , s j 2 = ( J − 1 ) − 1 b = 1 ∑ J ( Q b , j − Q j ) 2 .
Together with the raw multiplier, these intervals distinguish fixed-J J J tail calibration from blockwise estimation bias. Their polynomial critical-value growth is given in Proposition 4.2 .
The common block bias and fixed-J J J target distribution remain unchanged as the number of multiplier draws increases. Increasing the number of chains with the horizon yields the distinct time-uniform construction of Cai et al. [6 ] .
Calibration with a fixed number of restarted chains
Proposition 4.1 (Fixed-J J J Gaussian-multiplier mismatch). Let W 1 , … , W J W_1,\ldots,W_J W 1 , … , W J be i.i.d. N ( θ , σ 2 ) N(\theta,\sigma^2) N ( θ , σ 2 ) with fixed J ≥ 2 J \ge2 J ≥ 2 , and let
W ‾ = J − 1 ∑ b = 1 J W b , S J 2 = J − 1 ∑ b = 1 J ( W b − W ‾ ) 2 . \overline{W}=J^{-1}\sum_{b=1}^{J}W_b,\qquad S_J^2=J^{-1}\sum_{b=1}^{J}(W_b-\overline{W})^2. W = J − 1 b = 1 ∑ J W b , S J 2 = J − 1 b = 1 ∑ J ( W b − W ) 2 . Then
J − 1 ( W ‾ − θ ) S J ∼ t J − 1 . \frac{\sqrt{J-1}(\overline{W}-\theta)}{S_J}\sim t_{J-1}. S J J − 1 ( W − θ ) ∼ t J − 1 . In contrast, conditional on the observations,
J − 1 / 2 ∑ b = 1 J ξ b ( W b − W ‾ ) S J ∼ N ( 0 , 1 ) . \frac{J^{-1/2}\sum_{b=1}^{J}\xi_b(W_b-\overline{W})}{S_J}\sim N(0,1). S J J − 1/2 ∑ b = 1 J ξ b ( W b − W ) ∼ N ( 0 , 1 ) . The discrepancy persists as the within-block sample size grows whenever J J J remains fixed.
Proposition 4.2 (Polynomial Student–Bonferroni growth). For fixed degrees of freedom ν \nu ν and fixed α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) ,
t ν , 1 − α / ( 2 k ) ≍ k 1 / ν ( k → ∞ ) . (33) t_{\nu,1-\alpha/(2k)}\asymp k^{1/\nu}\qquad(k\to\infty). \tag*{(33)} t ν , 1 − α / ( 2 k ) ≍ k 1/ ν ( k → ∞ ) . (33) Thus a fixed-J J J Student–Bonferroni band has a critical value of polynomial order k 1 / ( J − 1 ) k^{1/(J-1)} k 1/ ( J − 1 ) , and Holm’s [16 ] most stringent step has the same fixed-degree tail. A Gaussian maximum over k k k standardized coordinates has critical value at most of order log k \sqrt{\log k} log k under arbitrary correlation.
The two propositions separate calibration from estimation. Student–Bonferroni has the polynomial critical-value growth in (33) . Student–Wishart instead uses the public first-order score correlation induced by balanced tree OUE, so its critical value depends on that correlation matrix. Both corrected fixed-J J J procedures produce wider intervals in the numerical comparisons, whereas the user-level multiplier uses n 3 n_3 n 3 independent score vectors.
Connections with stochastic-approximation inference
The construction also relates to uncertainty quantification for stochastic approximation. HiGrad creates hierarchically split trajectories and t t t -based contrasts (Su and Zhu (2023)), while Zhu et al. [33 ] analyze high-confidence t t t inference from a small number of independent stochastic-optimization runs. Dette and Graw [14 ] develop block-bootstrap inference for stochastic gradients under pure local differential privacy. Xie et al. [32 ] use locally perturbed gradients with Gaussian differential privacy and derive a functional central limit theorem. Growing-grid inference additionally requires an approximation for the maximum over quantile coordinates. We obtain it by using the first path for localization and an independent cohort of user-level scores for inference. The private channel builds on randomized response, frequency estimation, and range-query mechanisms [31 , 18 , 17 , 30 , 15 , 2 , 12 ] ; the localization proof uses classical stochastic approximation and averaging [25 , 26 , 24 , 19 ] ; and the final calibration invokes high-dimensional Gaussian and multiplier approximations [9 , 10 ] .
Numerical experiments
We distinguish precision gained by decoding the same private report from the performance of complete inferential procedures. Write k = k n k = k_n k = k n . Each setting uses 500 independent Monte Carlo repetitions, 500 Gaussian multiplier draws, and nominal simultaneous coverage 0.95. Probabilities are equally spaced on [ 0.05 , 0.95 ] [0.05, 0.95] [ 0.05 , 0.95 ] . Coverage records whether the entire grid is covered in a repetition; at 95%, its Monte Carlo standard error is about one percentage point. For point estimates Q ^ r , j \widehat{Q}_{r,j} Q r , j in repetition r r r , the pooled root mean squared error is
RMSE = { ( 500 k ) − 1 ∑ r = 1 500 ∑ j = 1 k ( Q ^ r , j − Q j ) 2 } 1 / 2 . \operatorname{RMSE} = \left\{(500k)^{-1}\sum_{r=1}^{500}\sum_{j=1}^{k}\left(\widehat{Q}_{r,j}-Q_j\right)^2\right\}^{1/2}. RMSE = { ( 500 k ) − 1 r = 1 ∑ 500 j = 1 ∑ k ( Q r , j − Q j ) 2 } 1/2 .
Lower RMSE means more accurate point estimates. Average full width measures interval precision and is interpreted together with attained coverage.
Precision from complementary decoding
The matched three-stage comparison uses fused tree-OUE, balanced tree-OUE, and categorical randomized response (kRR) on the interval categories, with identical cohort sizes and privacy budgets. Fused three-cohort inference is the complete procedure in Algorithm 1. The two tree procedures isolate the effect of fusion; kRR replaces the reporting channel inside the same construction. Under N ( 0 , 1 ) N(0,1) N ( 0 , 1 ) , the public bracket is [ F − 1 ( 0.02 ) , F − 1 ( 0.98 ) ] [F^{-1}(0.02), F^{-1}(0.98)] [ F − 1 ( 0.02 ) , F − 1 ( 0.98 )] . Initial values interpolate linearly across that bracket, mapping the smallest and largest target probabilities to its endpoints. The defaults are the full Stage-1 average, a = 2 / 3 a = 2/3 a = 2/3 , γ 0 = 0.1 ( U − L ) \gamma_0 = 0.1(U-L) γ 0 = 0.1 ( U − L ) , split ( 0.35 , 0.30 , 0.35 ) (0.35, 0.30, 0.35) ( 0.35 , 0.30 , 0.35 ) , and ϖ n = { log ( n + e ) } − 3 / 2 \varpi_n = \{\log(n+e)\}^{-3/2} ϖ n = { log ( n + e ) } − 3/2 . For channel m m m with Stage-2 envelope B m , 2 k B_{m,2k} B m , 2 k , the bandwidth is
h m , n = { B m , 2 k 2 log { 2 k ( n + 1 ) } n 2 } 1 / 4 . h_{m,n}=\left\{\frac{B_{m,2k}^{2}\log\{2k(n+1)\}}{n_2}\right\}^{1/4}. h m , n = { n 2 B m , 2 k 2 log { 2 k ( n + 1 )} } 1/4 .
using B 2 n B_{2n} B 2 n for tree-OUE and ( e ε + 2 k ) / ( e ε − 1 ) (e^\varepsilon+2k)/(e^\varepsilon-1) ( e ε + 2 k ) / ( e ε − 1 ) for kRR. § 2.3 relates the normal-design gains to the sufficient gain condition and gives the remaining tuning details.
Table 1 separates grid growth from sample-size gains by doubling n n n at each fixed k k k . Fusion reduces RMSE by 21–23% relative to balanced decoding in all six settings, with coverage 93.2–95.0%. At k = 127 k = 127 k = 127 and n = 1280000 n = 1280000 n = 1280000 , RMSE falls from 0.0494 to 0.0386 at essentially the same coverage (95.2% versus 95.0%). This precision gain uses the same reporting channel, cohort sizes, and privacy budget. At fixed k k k , doubling n n n reduces fused RMSE by 30–33%, consistent with the square-root inference-sample dependence of Corollary 3.11 . The kRR procedure has substantially larger errors and undercovers at the larger grids.
Table 1: End-to-end sample-size scaling at ε = 1 \varepsilon= 1 ε = 1 under N ( 0 , 1 ) N(0,1) N ( 0 , 1 ) . Fused is the complete procedure in Algorithm 1; Balanced changes its tree decoder, and kRR changes its reporting channel. All methods use the same three-cohort allocation and public bracket. Each entry is simultaneous coverage followed by pooled RMSE; lower RMSE is better.
Table 1.
Privacy and distribution comparisons in § 5.2 retain the fusion gain: at ( n , k ) = ( 320000 , 63 ) (n, k) = (320000, 63) ( n , k ) = ( 320000 , 63 ) , fused RMSE decreases from 0.1490 to 0.0326 as ε \varepsilon ε increases from 0.5 to 2, with coverage 94.4–95.6%. Under the contaminated normal design at (640000, 63, 1), fused RMSE is 0.0842, compared with 0.1053 for balanced decoding. Cohort allocation matters separately: increasing the inference share to 0.55 lowers error in regular settings but changes coverage from 0.944 to 0.896 at ε = 0.5 \varepsilon= 0.5 ε = 0.5 and from 0.938 to 0.872 under contamination. This allocation trades a smaller leading variance against larger learning errors.
Privacy and distribution comparisons
These experiments retain the three-stage design, target probabilities, and mechanism-specific tuning in § 5 . Each cell uses 500 repetitions and 500 multipliers. The public bracket is [ F − 1 ( 0.02 ) , F − 1 ( 0.98 ) ] [F^{-1}(0.02), F^{-1}(0.98)] [ F − 1 ( 0.02 ) , F − 1 ( 0.98 )] for the relevant distribution, using population-level range information. Coverage is for the complete target grid, and each table pairs it with pooled RMSE.
At fixed ( n , k ) = ( 320000 , 63 ) (n, k) = (320000, 63) ( n , k ) = ( 320000 , 63 ) under N ( 0 , 1 ) N(0,1) N ( 0 , 1 ) , varying ε \varepsilon ε isolates the privacy effect within each procedure. Table 2 shows a clear precision gain from weaker privacy: fused RMSE falls from 0.1490 to 0.0326, with coverage 94.4–95.6%. Fused RMSE is smaller than balanced RMSE at every privacy level.
Table 2 : End-to-end privacy comparison at n = 320000 n = 320000 n = 320000 and k = 63 k = 63 k = 63 under N ( 0 , 1 ) N(0, 1) N ( 0 , 1 ) . Each method entry is simultaneous coverage followed by pooled RMSE.
Table 2.
At ( n , k , ε ) = ( 640000 , 63 , 1 ) (n, k, \varepsilon) = (640000, 63, 1) ( n , k , ε ) = ( 640000 , 63 , 1 ) , we compare N ( 0 , 1 ) N(0,1) N ( 0 , 1 ) , a variance-standardized t 3 t_3 t 3 distribution, and 0.9 N ( 0 , 1 ) + 0.1 N ( 0 , 4 2 ) 0.9N(0,1) + 0.1N(0,4^2) 0.9 N ( 0 , 1 ) + 0.1 N ( 0 , 4 2 ) . Fused coverage is 93.8–94.8% across the three distributions (Table 3 ). Contamination increases its RMSE to 0.0842, consistent with the importance of local density for quantile precision; fusion still improves on balanced decoding, whose RMSE is 0.1053. kRR has appreciably larger error and lower coverage under both heavy tails and contamination.
Table 3 : End-to-end distribution comparison at n = 640000 n = 640000 n = 640000 , k = 63 k = 63 k = 63 , and ϵ = 1 \epsilon= 1 ϵ = 1 . Each method entry is simultaneous coverage followed by pooled RMSE.
Table 3.
Fused three-cohort inference and CDF-band inversion
A fixed spatial grid can use all n n n reports to estimate CDF values and then invert a joint CDF band. We implement the private CDF route of Liu et al. [22 ] with our fused tree channel and multiplier calibration. The comparison uses N ( 0 , 1 ) N(0, 1) N ( 0 , 1 ) , public bracket [ − 3 , 3 ] [-3, 3] [ − 3 , 3 ] , ϵ = 1 \epsilon= 1 ϵ = 1 , and ( n , k ) = ( 40000 , 31 ) , ( 160000 , 31 ) , ( 320000 , 63 ) (n, k) = (40000, 31), (160000, 31), (320000, 63) ( n , k ) = ( 40000 , 31 ) , ( 160000 , 31 ) , ( 320000 , 63 ) , with 500 repetitions and 500 multiplier draws.
Both procedures use all n n n users and one report per user. Fused three-cohort inference keeps the defaults in § 2.3 and learns query locations and densities from its first two cohorts. The CDF procedure instead uses d = k d = k d = k equally spaced inspection points x r x_r x r and the public anchor u = 1 / 2 u = 1/2 u = 1/2 , which preserves unbiasedness without knowing F ( x r ) F(x_r) F ( x r ) . The target grid consists of k k k equally spaced probabilities on [ 0.05 , 0.95 ] [0.05, 0.95] [ 0.05 , 0.95 ] .
Let [ ℓ r , u r ] [\ell_r, u_r] [ ℓ r , u r ] be the studentized Gaussian-multiplier band for the CDF at the inspection points, clipped to [ 0 , 1 ] [0, 1] [ 0 , 1 ] . We invert it using
L j C D F = max ( { L } ∪ { x r : u r < τ j } ) , U j C D F = min ( { U } ∪ { x r : ℓ r ≥ τ j } ) . L_j^{\mathrm{CDF}} = \max\left(\{L\} \cup\{x_r : u_r < \tau_j\}\right), \qquad U_j^{\mathrm{CDF}} = \min\left(\{U\} \cup\{x_r : \ell_r \ge\tau_j\}\right). L j CDF = max ( { L } ∪ { x r : u r < τ j } ) , U j CDF = min ( { U } ∪ { x r : ℓ r ≥ τ j } ) .
On the simultaneous CDF coverage event, every resulting interval contains its target quantile. The same event gives coverage for every probability whose quantile is inside the bracket, including probabilities selected after collection. The interval endpoints retain the spatial discretization error; point estimates alone invert the piecewise-linear interpolation of the isotonic CDF estimates.
For d d d equally spaced inspection points including L L L and U U U , exact CDF values give a discrete inversion width of ( U − L ) / ( d − 1 ) (U - L)/(d - 1) ( U − L ) / ( d − 1 ) for every target quantile strictly inside the bracket. Indeed, if r r r is the first index with F ( x r ) ≥ τ j F(x_r) \ge\tau_j F ( x r ) ≥ τ j , then F ( x r − 1 ) < τ j F(x_{r-1}) < \tau_j F ( x r − 1 ) < τ j and the endpoints are x r − 1 x_{r-1} x r − 1 and x r x_r x r , including when F ( x r ) = τ j F(x_r) = \tau_j F ( x r ) = τ j . This separates spatial discretization from statistical uncertainty.
Table 4 shows the resulting tradeoff. CDF inversion has smaller RMSE and narrower intervals in every setting, with conservative quantile coverage of 99.2–100%. At (320000, 63), fused three-cohort coverage is 91.8%, with a 95% Wilson interval [89.1, 93.9]% across repetitions. Coverage remains 91.8% among runs without density clipping (Table 5 ). The underlying CDF band covers its spatial grid in 93.2–97.2% of repetitions; discrete inversion contributes the extra quantile conservatism.
Table 4: Complete procedures under N ( 0 , 1 ) N(0,1) N ( 0 , 1 ) on [ − 3 , 3 ] [-3,3] [ − 3 , 3 ] , with one ε = 1 \varepsilon=1 ε = 1 report per user. Each entry is (simultaneous coverage; RMSE; average full width). Both methods use all n n n users; the fused three-cohort method learns quantile locations and densities. Lower RMSE and width are preferable at comparable coverage.
Table 4.
Table 5: Fused three-cohort inference on [ − 3 , 3 ] [-3,3] [ − 3 , 3 ] under N ( 0 , 1 ) N(0,1) N ( 0 , 1 ) at ε = 1 \varepsilon=1 ε = 1 . All-run entries give coverage and its 95% Wilson interval across 500 repetitions. The last two columns give covered repetitions divided by repetitions in that density-clipping group.
Table 5.
For ( n , k ) = ( 40000 , 31 ) , ( 160000 , 31 ) , ( 320000 , 63 ) (n,k)=(40000,31),(160000,31),(320000,63) ( n , k ) = ( 40000 , 31 ) , ( 160000 , 31 ) , ( 320000 , 63 ) , direct density clipping occurs in 26.0%, 4.8%, and 2.0% of repetitions; neither procedure produces fallback or empty intervals. Table 5 gives Wilson intervals for Monte Carlo uncertainty and separates repetitions with and without clipping. At (320000, 63), 40 of the 490 unclipped repetitions miss at least one target, so clipping alone does not explain the coverage deficit. The stratification is descriptive: clipping is an outcome of the same learning stages whose errors enter the one-step remainder.
The choice of spatial resolution also affects communication. For a report with d d d thresholds, the privatized unary vector has expected length ( 2 H d + 1 − 2 ) / H d (2^{H_d+1}-2)/H_d ( 2 H d + 1 − 2 ) / H d bits; the level tag requires another ⌈ log 2 H d ⌉ \lceil\log_2 H_d\rceil ⌈ log 2 H d ⌉ bits. The CDF procedure uses d = k d=k d = k for every user, whereas direct inference uses d = k d=k d = k in Stages 1 and 3 and d = 2 k d=2k d = 2 k in Stage 2. The 0.70/0.30 weighted mean of these two report lengths gives the direct cost under the default allocation. Both fit the same maximum report-length allowance. At k = 31 k=31 k = 31 , direct inference and CDF inversion use 18.0 and 15.4 bits on average; at k = 63 k=63 k = 63 , they use 28.6 and 24.0. These counts include private unary vectors and level tags, excluding public queries and transport framing.
Refining the CDF grid from d = 63 d=63 d = 63 to 127 at ( n , k ) = ( 320000 , 63 ) (n,k)=(320000,63) ( n , k ) = ( 320000 , 63 ) approximately halves its discretization width, but simulated widths remain 0.3556 and 0.3564, while mean report length rises to 39.3 bits. The CDF release supports later probability queries; three-cohort inference learns locations for prespecified percentiles without choosing a spatial endpoint grid. Thus the target list determines the direct method’s reporting dimensions, while the public range and endpoint resolution determine the CDF grid.
Algorithm 1 also updates public thresholds after each Stage-1 report; the Stage-2 and Stage-3 lists are fixed within their cohorts. Sending each user the full list requires k ( n + n 2 ) k(n+n_2) k ( n + n 2 ) threshold values in total, or about 210 MB with 64-bit values at ( n , k ) = ( 320000 , 63 ) (n,k)=(320000,63) ( n , k ) = ( 320000 , 63 ) , in addition to private uploads. Counting each public list publication once gives k ( n 1 + 3 ) k(n_1+3) k ( n 1 + 3 ) values; delivery to individual users depends on the broadcast or retrieval protocol. An equally spaced CDF grid can instead be reconstructed from its endpoints and size.
Streaming multiplier storage is O ( M d ) O(Md) O ( M d ) for CDF inversion and O ( M k ) O(Mk) O ( M k ) for direct inference, using the identities in § 2.4 . In the simulations, both implementations compute the equivalent Gaussian critical value from the empirical covariance and store n k nk nk and n 3 k n_3k n 3 k score doubles, respectively. Reported timings measure these covariance-based implementations with in-memory queries and no network transport. Upload length, query distribution, and computation therefore describe separate deployment costs.
Restarted-block comparisons
The comparison with corrected, fixed-block inference is complementary. With J = 8 J=8 J = 8 restarted blocks, Student–Wishart and Student–Bonferroni attain 93.4–94.8% coverage; the fused three-cohort intervals are shorter, although their point errors are larger at k = 31 k=31 k = 31 and 63. At k = 127 k=127 k = 127 , fused three-cohort and Student–Wishart widths are 0.3574 and 0.5902, a 39% reduction at similar coverage and RMSE. The block design and model-assisted correlation calibration are given in § 5.4 ; the fixed-J J J theory is in § 4 .
The block comparisons use N ( 0 , 1 ) N(0,1) N ( 0 , 1 ) , ϵ = 1 \epsilon=1 ϵ = 1 , and ( n , k ) = ( 160000 , 31 ) (n,k)=(160000,31) ( n , k ) = ( 160000 , 31 ) , ( 320000 , 63 ) (320000,63) ( 320000 , 63 ) , ( 640000 , 127 ) (640000,127) ( 640000 , 127 ) , with 500 repetitions and 500 calibration draws where needed. They divide all users into J = 8 J=8 J = 8 equal blocks and use balanced tree-OUE. Each block initializes by linear interpolation across [ Φ − 1 ( 0.01 ) , Φ − 1 ( 0.99 ) ] [\Phi^{-1}(0.01), \Phi^{-1}(0.99)] [ Φ − 1 ( 0.01 ) , Φ − 1 ( 0.99 )] , restarts the gain 0.1 ( U − L ) t − 2 / 3 0.1(U-L)t^{-2/3} 0.1 ( U − L ) t − 2/3 , and averages its second half. Student–Wishart and Student–Bonferroni share the resulting point estimator; fused three-cohort inference instead uses the main three-cohort design and its [ Φ − 1 ( 0.02 ) , Φ − 1 ( 0.98 ) ] [\Phi^{-1}(0.02), \Phi^{-1}(0.98)] [ Φ − 1 ( 0.02 ) , Φ − 1 ( 0.98 )] bracket. The comparison includes these decoder, bracket, path, and allocation choices.
Student–Wishart uses the public, model-based balanced tree score correlation in the Gaussian block approximation. It is a model-assisted comparator; Student–Bonferroni uses the corresponding marginal t t t tails. § 4 defines both references. Table 6 retains the coverage–error–width tradeoff: fused three-cohort bands are shorter in all settings, while restarted estimates have smaller RMSE at k = 31 k = 31 k = 31 and 63 63 63 and similar RMSE at k = 127 k = 127 k = 127 .
Table 6. Corrected block procedures versus fused three-cohort inference (Algorithm 1) at ϵ = 1 \epsilon=1 ϵ = 1 under N ( 0 , 1 ) N(0,1) N ( 0 , 1 ) . Restarted methods use J = 8 J=8 J = 8 and balanced tree-OUE; the complete designs differ as specified in the text. Width is the mean full interval width.
California wage-percentile comparisons
We illustrate wage-percentile reporting with the 2024 one-year California person file from the American Community Survey Public Use Microdata Sample (ACS PUMS) [28 ] . The 90/50 and 50/10 ratios distinguish dispersion above and below the median [4 ] . Each released record receives an additional local randomization.
We retain respondents aged 25–64 with positive wages, at least 40 weeks worked, and at least 30 usual weekly hours. We adjust annual wages to 2024 dollars and divide by annual hours, obtaining 123531 records. The records are randomly permuted before local randomization and assigned by arrival index to cohorts of sizes 43235, 37059, and 43237, corresponding to the split ( 0.35 , 0.30 , 0.35 ) (0.35, 0.30, 0.35) ( 0.35 , 0.30 , 0.35 ) . We use log hourly wages, 19 probabilities from 0.05 to 0.95, ε = 1 \varepsilon= 1 ε = 1 , and public bracket [ log 2 , log 500 ] [\log2, \log500] [ log 2 , log 500 ] . The gain constant is 0.1 log ( 500 / 2 ) ≈ 0.552 0.1\log(500/2) \approx0.552 0.1 log ( 500/2 ) ≈ 0.552 . The 294 records below this bracket and two above it remain in the outer interval categories.
For calibration, we treat unweighted log wages as independent draws from a continuous working distribution F F F . The target is F − 1 ( τ j ) F^{-1}(\tau_j) F − 1 ( τ j ) ; the nominal 95% level refers to repeated independent streams from F F F , with fresh local randomization and multipliers, under Theorem 3.10 ’s conditions. File quantiles serve as descriptive benchmarks. ACS population inference additionally requires survey weights and the PUMS replicate-weight design.
The released wages have ties: the 123531 log wages take 7260 distinct values, with a largest empirical point mass of 3.2%. Masses at the 19 empirical target quantiles range from less than 0.01% to 2.7%. On the log scale, windows of radius h n ≈ 0.638 h_n \approx0.638 h n ≈ 0.638 around those quantiles contain 1751–3385 distinct values. The 19 estimated densities range from 0.123 to 0.507, with no density clipping or variance fallback. The finite difference therefore averages over many recorded values, while smooth local density remains a working approximation.
We apply the monotone interval refinement in § 2.4 on the log-wage scale and exponentiate its endpoints to obtain wage-quantile intervals. Write [ L ~ j , U ~ j ] [\widetilde{L}_j, \widetilde{U}_j] [ L j , U j ] for the refined log-quantile interval. For j < ℓ j < \ell j < ℓ , the ratio of wage quantiles at τ ℓ \tau_\ell τ ℓ and τ j \tau_j τ j inherits the interval [ exp ( L ~ ℓ − U ~ j ) , exp ( U ~ ℓ − L ~ j ) ] [\exp(\widetilde{L}_\ell-\widetilde{U}_j), \exp(\widetilde{U}_\ell-\widetilde{L}_j)] [ exp ( L ℓ − U j ) , exp ( U ℓ − L j )] . All such ratio intervals cover whenever the log-quantile band covers.
Table 7. Hourly-wage quantiles in 2024 dollars. Intervals use nominal 95% simultaneous calibration under the continuous working model.
The private 90/50 and 50/10 ratios are 3.27 and 2.28, suggesting greater dispersion above the median. Transforming the simultaneous log-quantile band gives intervals [2.17, 4.93] and [1.60, 3.25], respectively; the 90/10 ratio is 7.47 with interval [4.60, 12.13]. This comparison uses the shared median on the log-wage scale. Writing Q τ = F − 1 ( τ ) Q_{\tau}=F^{-1}(\tau) Q τ = F − 1 ( τ ) and [ L τ , U τ ] [L_{\tau}, U_{\tau}] [ L τ , U τ ] for its simultaneous band endpoints, the contrast D = Q 0.90 + Q 0.10 − 2 Q 0.50 D=Q_{0.90}+Q_{0.10}-2Q_{0.50} D = Q 0.90 + Q 0.10 − 2 Q 0.50 inherits the interval
[ L 0.90 + L 0.10 − 2 U 0.50 , U 0.90 + U 0.10 − 2 L 0.50 ] [L_{0.90}+L_{0.10}-2U_{0.50},\ U_{0.90}+U_{0.10}-2L_{0.50}] [ L 0.90 + L 0.10 − 2 U 0.50 , U 0.90 + U 0.10 − 2 L 0.50 ]
It contains zero exactly when the rectangular-band intervals for the two log-ratios overlap; exponentiation preserves this overlap. Thus the reported band does not separate upper- and lower-tail dispersion. Figure 1 shows all 19 intervals: 18 file quantiles, including all five tabulated benchmarks, lie in the realized band. The exception is the 40th-percentile benchmark 28.23, whose interval is [22.41, 27.82].
Figure 1. Private hourly-wage quantiles and nominal 95% simultaneous intervals for the 19-point ACS grid in § 6 . The left panel uses a logarithmic wage axis; the right enlarges the middle quantiles on a linear axis. Black triangles are empirical file benchmarks. At the 40th percentile, the benchmark lies above its interval. Calibration targets the continuous working-model quantiles; the plotted benchmarks describe the fixed released file.
Concluding remarks
This paper develops simultaneous quantile inference from one locally private report per user. The exact covariance of complementary scores yields a variance-minimizing fusion rule without additional privacy cost. Separating adaptive localization, density estimation, and fresh-score calibration gives a uniform one-step representation: first-order localization error is removed, and the remaining errors can be controlled on the scale of the maximum over the grid. This supports multiplier bands for polynomially growing grids under the stated conditions. Fusion improves matched three-stage estimates in the simulations, while comparison with CDF inversion clarifies the sample cost of learning query locations. The wage application shows how the joint band also supports percentile-ratio comparisons.
Two extensions merit further study. First, compact channels such as Hadamard response and local hashing [2 , 30 ] suggest ways to reduce communication. Compression changes the dependence among decoded node scores, so the complementary-score covariance and optimal fusion weights would need to be derived anew. Uniform variance lower bounds and standardized moment bounds would then determine whether the localization rates and Gaussian approximation still permit comparably large grids. Second, continuously updating query locations and density estimates could make fuller use of an incoming stream. Time-uniform private quantile inference [6 ] offers a starting point, but a growing grid requires a one-step expansion uniform in both time and quantile. History-dependent scores would replace the present conditionally independent calibration sample, requiring control of accumulated conditional covariances and a Gaussian strong approximation or martingale confidence boundaries. Combining these bounds with uniform localization control would yield bands valid throughout online updating.
Acknowledgment
Qirui Hu’s research was supported by National Natural Science Foundation of China (NSFC) (Grant Nos.12601520), the Shanghai Engineering Research Center of Finance Intelligence (Grant No. 19DZ2254600) and by TRR 391 Spatio-temporal Statistics for the Transition of Energy and Transport (Project number 520388526) funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation).
Proof organization
The privacy calculation and fused-score moments are specific to the proposed mechanism. The Abel decomposition and one-step algebra are established directly. Lemma C.1 specializes a classical stopped Lyapunov argument for projected stochastic approximation [25 , 26 , 24 , 19 ] . The Gaussian approximation, multiplier bootstrap, and anti-concentration inputs follow Chernozhukov et al. [9 , 10 ] , with their conditional moment and dimension requirements verified in Lemma E.3. The Gaussian mean–sample covariance independence in Proposition 4.1 is standard multivariate analysis [3 ] .
Tree-OUE Moments and Fusion
This appendix proves Proposition 2.1 from the main text. Throughout, the public threshold list, its tree, and the anchor are fixed.
Node moments
Let I v = 1 { C ( X ) is a descendant leaf of v } I_v = 1\{C(X)\text{ is a descendant leaf of }v\} I v = 1 { C ( X ) is a descendant leaf of v } . Condition on L ⋆ = ℓ ( v ) L^\star= \ell(v) L ⋆ = ℓ ( v ) for the following bit moments; the input bit is I v I_v I v . Put
η v = Z v − q ε p ε − q ε \eta_v = \frac{Z_v-q_\varepsilon}{p_\varepsilon-q_\varepsilon} η v = p ε − q ε Z v − q ε
If I v = 0 I_v = 0 I v = 0 , then Z v ∼ Bernoulli ( q ε ) Z_v \sim\operatorname{Bernoulli}(q_\varepsilon) Z v ∼ Bernoulli ( q ε ) and
E ( η v ∣ I v = 0 ) = 0 , \mathbb{E}(\eta_v \mid I_v = 0) = 0, E ( η v ∣ I v = 0 ) = 0 ,
E ( η v 2 ∣ I v = 0 ) = q ε ( 1 − q ε ) ( p ε − q ε ) 2 = 4 e ε ( e ε − 1 ) 2 = ν ε . \mathbb{E}(\eta_v^2 \mid I_v = 0) = \frac{q_\varepsilon(1-q_\varepsilon)}{(p_\varepsilon-q_\varepsilon)^2} = \frac{4e^\varepsilon}{(e^\varepsilon-1)^2} = \nu_\varepsilon. E ( η v 2 ∣ I v = 0 ) = ( p ε − q ε ) 2 q ε ( 1 − q ε ) = ( e ε − 1 ) 2 4 e ε = ν ε .
If I v = 1 I_v = 1 I v = 1 , then Z v ∼ Bernoulli ( p ε ) Z_v \sim\operatorname{Bernoulli}(p_\varepsilon) Z v ∼ Bernoulli ( p ε ) and
E ( η v ∣ I v = 1 ) = 1 , \mathbb{E}(\eta_v \mid I_v = 1) = 1, E ( η v ∣ I v = 1 ) = 1 ,
E ( η v 2 ∣ I v = 1 ) = 1 + p ε ( 1 − p ε ) ( p ε − q ε ) 2 = ν ε + 2. \mathbb{E}(\eta_v^2 \mid I_v = 1) = 1 + \frac{p_\varepsilon(1-p_\varepsilon)}{(p_\varepsilon-q_\varepsilon)^2} = \nu_\varepsilon+ 2. E ( η v 2 ∣ I v = 1 ) = 1 + ( p ε − q ε ) 2 p ε ( 1 − p ε ) = ν ε + 2.
The last identity follows by direct substitution of p ε = 1 / 2 p_\varepsilon= 1/2 p ε = 1/2 and q ε = ( e ε + 1 ) − 1 q_\varepsilon= (e^\varepsilon+ 1)^{-1} q ε = ( e ε + 1 ) − 1 .
Averaging the sampled-level moments over the uniform L ⋆ L^\star L ⋆ gives
E ( ψ v ∣ X ) = H d P { L ⋆ = ℓ ( v ) } E ( η v ∣ X , L ⋆ = ℓ ( v ) ) = I v , (34) \mathbb{E}(\psi_v \mid X) = H_d\mathbb{P}\{L^\star= \ell(v)\}\mathbb{E}(\eta_v \mid X,L^\star= \ell(v)) = I_v, \tag*{(34)} E ( ψ v ∣ X ) = H d P { L ⋆ = ℓ ( v )} E ( η v ∣ X , L ⋆ = ℓ ( v )) = I v , (34)
E ( ψ v 2 ∣ X ) = H d 2 P { L ⋆ = ℓ ( v ) } E ( η v 2 ∣ X , L ⋆ = ℓ ( v ) ) = H d ( ν ε + 2 I v ) . (35) \mathbb{E}(\psi_v^2 \mid X) = H_d^2\mathbb{P}\{L^\star= \ell(v)\}\mathbb{E}(\eta_v^2 \mid X,L^\star= \ell(v)) = H_d(\nu_\varepsilon+ 2I_v). \tag*{(35)} E ( ψ v 2 ∣ X ) = H d 2 P { L ⋆ = ℓ ( v )} E ( η v 2 ∣ X , L ⋆ = ℓ ( v )) = H d ( ν ε + 2 I v ) . (35)
If v ≠ w v \ne w v = w are disjoint tree nodes, then
E ( ψ v ψ w ∣ X ) = 0. (36) \mathbb{E}(\psi_v\psi_w \mid X)=0. \tag*{(36)} E ( ψ v ψ w ∣ X ) = 0. (36)
Indeed, if their levels differ, the two level indicators cannot both equal one. If their levels agree, their unary bits are conditionally independent and at most one input bit equals one. The centered decoder for every zero input has conditional mean zero, so the product has conditional mean zero.
Finally, since ∣ Z v − q ε ∣ ≤ 1 − q ε |Z_v-q_\varepsilon|\le1-q_\varepsilon ∣ Z v − q ε ∣ ≤ 1 − q ε and
1 − q ε p ε − q ε = 2 ε ε ε ε − 1 , \frac{1-q_\varepsilon}{p_\varepsilon-q_\varepsilon}=\frac{2\varepsilon^\varepsilon}{\varepsilon^\varepsilon-1}, p ε − q ε 1 − q ε = ε ε − 1 2 ε ε ,
we have
∣ ψ v ∣ ≤ 2 H d ε ε ε ε − 1 . |\psi_v|\le\frac{2H_d\varepsilon^\varepsilon}{\varepsilon^\varepsilon-1}. ∣ ψ v ∣ ≤ ε ε − 1 2 H d ε ε .
Prefix, suffix, and fusion
Let p r = F ( x ( r ) ) p_r=F(x_{(r)}) p r = F ( x ( r ) ) . Exactly one node in D r − \mathcal{D}_r^{-} D r − contains the realized leaf when X ≤ x ( r ) X\le x_{(r)} X ≤ x ( r ) , and none does otherwise. Summing (A.1) gives
E ( A r ∣ X ) = 1 { X ≤ x ( r ) } , E A r = p r . \mathbb{E}(A_r\mid X)=1\{X\le x_{(r)}\},\qquad\mathbb{E}A_r=p_r. E ( A r ∣ X ) = 1 { X ≤ x ( r ) } , E A r = p r .
Using (A.2) and (A.3),
E A r 2 = ∑ v ∈ D r − E ψ v 2 = H d w ‾ r ν ε + 2 H d ∑ v ∈ D r − P ( I v = 1 ) = H d w ‾ r ν ε + 2 H d p r . \mathbb{E}A_r^2=\sum_{v\in\mathcal{D}_r^{-}}\mathbb{E}\psi_v^2=H_d\overline{w}_r\nu_\varepsilon+2H_d\sum_{v\in\mathcal{D}_r^{-}}\mathbb{P}(I_v=1)
=H_d\overline{w}_r\nu_\varepsilon+2H_dp_r. E A r 2 = v ∈ D r − ∑ E ψ v 2 = H d w r ν ε + 2 H d v ∈ D r − ∑ P ( I v = 1 ) = H d w r ν ε + 2 H d p r .
Therefore
Var ( A r ) = H d w ‾ r ν ε + 2 H d p r − p r 2 . \operatorname{Var}(A_r)=H_d\overline{w}_r\nu_\varepsilon+2H_dp_r-p_r^2. Var ( A r ) = H d w r ν ε + 2 H d p r − p r 2 .
Write S r = ∑ v ∈ D r + ψ v S_r=\sum_{v\in\mathcal{D}_r^{+}}\psi_v S r = ∑ v ∈ D r + ψ v , so B r = 1 − S r B_r=1-S_r B r = 1 − S r . The same argument gives
E S r = 1 − p r , E S r 2 = H d w ‾ r + ν ε + 2 H d ( 1 − p r ) , \mathbb{E}S_r=1-p_r,\qquad\mathbb{E}S_r^2=H_d\overline{w}_r^{+}\nu_\varepsilon+2H_d(1-p_r), E S r = 1 − p r , E S r 2 = H d w r + ν ε + 2 H d ( 1 − p r ) ,
and hence
Var ( B r ) = Var ( S r ) = H d w ‾ r + ν ε + 2 H d ( 1 − p r ) − ( 1 − p r ) 2 . \operatorname{Var}(B_r)=\operatorname{Var}(S_r)=H_d\overline{w}_r^{+}\nu_\varepsilon+2H_d(1-p_r)-(1-p_r)^2. Var ( B r ) = Var ( S r ) = H d w r + ν ε + 2 H d ( 1 − p r ) − ( 1 − p r ) 2 .
Every prefix node is disjoint from every suffix node, so (A.3) yields E ( A r S r ) = 0 \mathbb{E}(A_rS_r)=0 E ( A r S r ) = 0 . It follows that
Cov ( A r , B r ) = Cov ( A r , 1 − S r ) = − { E ( A r S r ) − E A r E S r } = p r ( 1 − p r ) . \operatorname{Cov}(A_r,B_r)=\operatorname{Cov}(A_r,1-S_r)=-\{\mathbb{E}(A_rS_r)-\mathbb{E}A_r\mathbb{E}S_r\}=p_r(1-p_r). Cov ( A r , B r ) = Cov ( A r , 1 − S r ) = − { E ( A r S r ) − E A r E S r } = p r ( 1 − p r ) .
For an arbitrary scalar λ \lambda λ , the estimator λ A r + ( 1 − λ ) B r \lambda A_r + (1-\lambda)B_r λ A r + ( 1 − λ ) B r is unbiased, with variance
Var { λ A r + ( 1 − λ ) B r } = λ 2 Var ( A r ) + ( 1 − λ ) 2 Var ( B r ) + 2 λ ( 1 − λ ) p r ( 1 − p r ) . (37) \operatorname{Var}\{\lambda A_r + (1-\lambda)B_r\} = \lambda^2 \operatorname{Var}(A_r) + (1-\lambda)^2 \operatorname{Var}(B_r) + 2\lambda(1-\lambda)p_r(1-p_r). \tag*{(37)} Var { λ A r + ( 1 − λ ) B r } = λ 2 Var ( A r ) + ( 1 − λ ) 2 Var ( B r ) + 2 λ ( 1 − λ ) p r ( 1 − p r ) . (37)
Set C r = p r ( 1 − p r ) C_r = p_r(1-p_r) C r = p r ( 1 − p r ) and
a = a r − ( p r ) = Var ( A r ) − C r , b = a r + ( p r ) = Var ( B r ) − C r . a = a_r^-(p_r) = \operatorname{Var}(A_r)-C_r,\qquad b = a_r^+(p_r) = \operatorname{Var}(B_r)-C_r. a = a r − ( p r ) = Var ( A r ) − C r , b = a r + ( p r ) = Var ( B r ) − C r .
Completing the square gives
Var { λ A r + ( 1 − λ ) B r } = C r + a λ 2 + b ( 1 − λ ) 2 = C r + a b a + b + ( a + b ) ( λ − b a + b ) 2 . (38) \operatorname{Var}\{\lambda A_r + (1-\lambda)B_r\} = C_r + a\lambda^2 + b(1-\lambda)^2 = C_r + \frac{ab}{a+b} + (a+b)\left(\lambda-\frac{b}{a+b}\right)^2. \tag*{(38)} Var { λ A r + ( 1 − λ ) B r } = C r + a λ 2 + b ( 1 − λ ) 2 = C r + a + b ab + ( a + b ) ( λ − a + b b ) 2 . (38)
Both a a a and b b b are strictly positive. The minimizer is b / ( a + b ) = λ r ∘ ( p r ) b/(a+b)=\lambda_r^\circ(p_r) b / ( a + b ) = λ r ∘ ( p r ) and the minimum is (3) . Since minimizing over [ 0 , 1 ] [0,1] [ 0 , 1 ] cannot be worse than evaluating at zero or one, the variance dominance follows.
The sum D r = a r − ( u ) + a r + ( u ) = H d ( w r − + w r + ) ν ε + 2 H d − 1 D_r = a_r^-(u)+a_r^+(u)=H_d(w_r^-+w_r^+)\nu_\varepsilon+2H_d-1 D r = a r − ( u ) + a r + ( u ) = H d ( w r − + w r + ) ν ε + 2 H d − 1 does not depend on u u u , and
λ r ∘ ( u ) − λ r ∘ ( p r ) = − ( 2 H d − 1 ) ( u − p r ) D r . \lambda_r^\circ(u)-\lambda_r^\circ(p_r)=-\frac{(2H_d-1)(u-p_r)}{D_r}. λ r ∘ ( u ) − λ r ∘ ( p r ) = − D r ( 2 H d − 1 ) ( u − p r ) .
Substitution into (A.5) gives (4) . Since D r ≥ 2 H d − 1 D_r \ge2H_d-1 D r ≥ 2 H d − 1 , it also gives (5) . Finally, at the sampled level each canonical decomposition contributes at most one node score. Hence ∣ A r ∣ ≤ 2 H d e ε / ( e ε − 1 ) |A_r|\le2H_d e^\varepsilon/(e^\varepsilon-1) ∣ A r ∣ ≤ 2 H d e ε / ( e ε − 1 ) and ∣ B r ∣ ≤ 1 + 2 H d e ε / ( e ε − 1 ) |B_r|\le1+2H_d e^\varepsilon/(e^\varepsilon-1) ∣ B r ∣ ≤ 1 + 2 H d e ε / ( e ε − 1 ) . Convexity of the fused score proves the claimed envelope.
Privacy Proof
Sequential privacy guarantee. Fix a public threshold list and a sampled level ℓ \ell ℓ . Two possible interval categories produce unary vectors that are either identical or differ in exactly two coordinates: one coordinate changes from one to zero and another from zero to one. For one changed pair and any released bit pair ( z 1 , z 2 ) (z_1,z_2) ( z 1 , z 2 ) , the largest likelihood ratio is
p ε ( 1 − q ε ) q ε ( 1 − p ε ) = 1 − q ε q ε = e ε . \frac{p_\varepsilon(1-q_\varepsilon)}{q_\varepsilon(1-p_\varepsilon)}
=
\frac{1-q_\varepsilon}{q_\varepsilon}
=
e^\varepsilon. q ε ( 1 − p ε ) p ε ( 1 − q ε ) = q ε 1 − q ε = e ε .
All unchanged bit factors cancel. Thus the conditional OUE release at level ℓ \ell ℓ is ε \varepsilon ε -LDP. The level is sampled independently of the private category, so mixing over levels preserves the same bound.
Now consider the sequential transcript Z 1 : n Z_{1:n} Z 1 : n . Let two data streams differ only at user i i i . For a fixed realized transcript, the chain rule factorizes its likelihood into conditional kernels. The factors before i i i coincide. At i i i , the public query is the same function of the common preceding transcript and the conditional likelihood ratio is at most e ε n e^{\varepsilon_n} e ε n . Conditional on the realized report Z i Z_i Z i and the subsequent common transcript prefix, all later public queries are again the same deterministic functions of that prefix. Because later users’ raw values agree, every later conditional kernel cancels in the likelihood ratio. Hence the complete transcript ratio is at most e ε n e^{\varepsilon_n} e ε n .
All server computations after receipt of the reports—sorting, score decoding, projection, averaging, density estimation, multiplier generation, and interval refinement—are measurable post-processing and cannot increase the privacy loss. Finally, a user belongs to exactly one cohort, so there is no across-stage composition for that user. This proves the privacy guarantee.
Stage-1 Localization and Full-Average Expansion
We first record the filtration and a localization lemma. For Stage 1, let F t \mathcal{F}_t F t contain all observations only through their released reports up to time t t t , together with all public randomization. Put
e t , j = q t , j − Q j , n , ζ t , j = G t , j ( 1 ) − F ( q t − 1 , j ) . e_{t,j}=q_{t,j}-Q_{j,n},\qquad\zeta_{t,j}=G_{t,j}^{(1)}-F(q_{t-1,j}). e t , j = q t , j − Q j , n , ζ t , j = G t , j ( 1 ) − F ( q t − 1 , j ) .
Then
E ( ζ t , j ∣ F t − 1 ) = 0 , ∣ ζ t , j ∣ ≤ 2 B 1 n . (39) \mathbb{E}(\zeta_{t,j}\mid\mathcal{F}_{t-1})=0,\qquad|\zeta_{t,j}|\le2B_{1n}. \tag*{(39)} E ( ζ t , j ∣ F t − 1 ) = 0 , ∣ ζ t , j ∣ ≤ 2 B 1 n . (39)
The bound uses 0 ≤ F ≤ 1 0\le F\le1 0 ≤ F ≤ 1 and ∣ G t , j ( 1 ) ∣ ≤ B 1 n |G_{t,j}^{(1)}|\le B_{1n} ∣ G t , j ( 1 ) ∣ ≤ B 1 n , enlarging an inessential universal constant.
Lemma C.1 (Uniform localization of the projected recursion. ) Under Assumptions 3.1, 3.3 and 3.4, there is a constant C C C depending only on ( μ , L F , γ 0 , a ) (\mu,L_F,\gamma_0,a) ( μ , L F , γ 0 , a ) such that, for a localization index satisfying (3.2)–(3.4), an event E l o c , n \mathcal{E}_{\mathrm{loc},n} E loc , n has probability tending to one and, on this event,
(i) ∣ e t , j ∣ ≤ δ 0 |e_{t,j}|\le\delta_0 ∣ e t , j ∣ ≤ δ 0 for every j ≤ k n j\le k_n j ≤ k n and b n ≤ t ≤ n 1 b_n\le t\le n_1 b n ≤ t ≤ n 1 ;
(ii) the scalar projection in (7) is inactive for b n < t ≤ n 1 b_n<t\le n_1 b n < t ≤ n 1 ;
(iii) uniformly over j ≤ k n j\le k_n j ≤ k n and b n ≤ t ≤ n 1 b_n\le t\le n_1 b n ≤ t ≤ n 1 ,
∣ e t , j ∣ ≤ C [ e − μ 2 ∑ s = b n + 1 t γ s ∣ e b n , j ∣ + B 1 n { γ t ℓ n + γ t ℓ n } ] . (40) |e_{t,j}|\le C\left[e^{-\frac{\mu}{2}\sum_{s=b_n+1}^{t}\gamma_s}|e_{b_n,j}|+B_{1n}\left\{\sqrt{\gamma_t\ell_n}+\gamma_t\ell_n\right\}\right]. \tag*{(40)} ∣ e t , j ∣ ≤ C [ e − 2 μ ∑ s = b n + 1 t γ s ∣ e b n , j ∣ + B 1 n { γ t ℓ n + γ t ℓ n } ] . (40)
A sufficient primitive condition for selecting such a b n b_n b n is
B 1 n 2 ℓ n ω n = o ( n 1 a ) , b n ≲ ( B 1 n 2 ℓ n ω n ) 1 / a + ( log n ) 1 / ( 1 − a ) , b n = o ( n 1 ) , B_{1n}^{2}\ell_n\omega_n=o(n_1^{a}),\qquad b_n\lesssim\left(B_{1n}^{2}\ell_n\omega_n\right)^{1/a}+(\log n)^{1/(1-a)},\qquad b_n=o(n_1), B 1 n 2 ℓ n ω n = o ( n 1 a ) , b n ≲ ( B 1 n 2 ℓ n ω n ) 1/ a + ( log n ) 1/ ( 1 − a ) , b n = o ( n 1 ) ,
where ω n → ∞ \omega_n\to\infty ω n → ∞ may diverge arbitrarily slowly and the multiplicative constants are chosen large enough.
Proof. We use deterministic contraction weights so that every innovation is multiplied by a predictable coefficient.
Step 1: a stopped Lyapunov inequality. Projection onto [ L , U ] [L,U] [ L , U ] is nonexpansive and fixes Q j , n Q_{j,n} Q j , n . With h t − 1 , j = F ( q t − 1 , j ) − τ j , n h_{t-1,j}=F(q_{t-1,j})-\tau_{j,n} h t − 1 , j = F ( q t − 1 , j ) − τ j , n ,
e t , j 2 ≤ [ e t − 1 , j − γ t { h t − 1 , j + ζ t , j } ] 2 . e_{t,j}^{2}\leq\left[e_{t-1,j}-\gamma_t\{h_{t-1,j}+\zeta_{t,j}\}\right]^2. e t , j 2 ≤ [ e t − 1 , j − γ t { h t − 1 , j + ζ t , j } ] 2 .
The signed secant condition gives μ ≤ h t − 1 , j / e t − 1 , j ≤ L F \mu\leq h_{t-1,j}/e_{t-1,j}\leq L_F μ ≤ h t − 1 , j / e t − 1 , j ≤ L F whenever e t − 1 , j ≠ 0 e_{t-1,j}\ne0 e t − 1 , j = 0 . Since γ t L F ≤ 1 / 2 \gamma_tL_F\leq1/2 γ t L F ≤ 1/2 ,
∣ e t − 1 , j − γ t h t − 1 , j ∣ ≤ ( 1 − μ γ t ) ∣ e t − 1 , j ∣ ≤ ∣ e t − 1 , j ∣ . \left|e_{t-1,j}-\gamma_th_{t-1,j}\right|\leq(1-\mu\gamma_t)|e_{t-1,j}|\leq|e_{t-1,j}|. ∣ e t − 1 , j − γ t h t − 1 , j ∣ ≤ ( 1 − μ γ t ) ∣ e t − 1 , j ∣ ≤ ∣ e t − 1 , j ∣.
These inequalities also hold when e t − 1 , j = 0 e_{t-1,j}=0 e t − 1 , j = 0 , since then h t − 1 , j = 0 h_{t-1,j}=0 h t − 1 , j = 0 . Squaring the first inequality and using ( 1 − μ γ t ) 2 ≤ 1 − μ γ t (1-\mu\gamma_t)^2\leq1-\mu\gamma_t ( 1 − μ γ t ) 2 ≤ 1 − μ γ t gives the drift contraction. After expanding the square, define
Δ M t , j = − 2 γ t ( e t − 1 , j − γ t h t − 1 , j ) ζ t , j + γ t 2 { ζ t , j 2 − E ( ζ t , j 2 ∣ F t − 1 ) } . (41) \Delta M_{t,j}=-2\gamma_t(e_{t-1,j}-\gamma_th_{t-1,j})\zeta_{t,j}+\gamma_t^2\{\zeta_{t,j}^2-\mathbb{E}(\zeta_{t,j}^2\mid\mathcal{F}_{t-1})\}. \tag*{(41)} Δ M t , j = − 2 γ t ( e t − 1 , j − γ t h t − 1 , j ) ζ t , j + γ t 2 { ζ t , j 2 − E ( ζ t , j 2 ∣ F t − 1 )} . (41)
Then E ( Δ M t , j ∣ F t − 1 ) = 0 \mathbb{E}(\Delta M_{t,j}\mid\mathcal{F}_{t-1})=0 E ( Δ M t , j ∣ F t − 1 ) = 0 . The secant bounds, the gain restriction, and (C.1) give (C.1)
e t , j 2 ≤ ( 1 − μ γ t ) e t − 1 , j 2 + C γ t 2 B 1 n 2 + Δ M t , j , (42) e_{t,j}^{2}\leq(1-\mu\gamma_t)e_{t-1,j}^{2}+C\gamma_t^2B_{1n}^{2}+\Delta M_{t,j}, \tag*{(42)} e t , j 2 ≤ ( 1 − μ γ t ) e t − 1 , j 2 + C γ t 2 B 1 n 2 + Δ M t , j , (42)
∣ Δ M t , j ∣ ≤ C γ t B 1 n ( ∣ e t − 1 , j ∣ + γ t B 1 n ) , (43) |\Delta M_{t,j}|\leq C\gamma_tB_{1n}(|e_{t-1,j}|+\gamma_tB_{1n}), \tag*{(43)} ∣Δ M t , j ∣ ≤ C γ t B 1 n ( ∣ e t − 1 , j ∣ + γ t B 1 n ) , (43)
E ( Δ M t , j 2 ∣ F t − 1 ) ≤ C γ t 2 B 1 n 2 ( e t − 1 , j 2 + γ t 2 B 1 n 2 ) . (44) \mathbb{E}(\Delta M_{t,j}^{2}\mid\mathcal{F}_{t-1})\leq C\gamma_t^2B_{1n}^{2}(e_{t-1,j}^{2}+\gamma_t^2B_{1n}^{2}). \tag*{(44)} E ( Δ M t , j 2 ∣ F t − 1 ) ≤ C γ t 2 B 1 n 2 ( e t − 1 , j 2 + γ t 2 B 1 n 2 ) . (44)
In particular, taking expectations and iterating (C.4) yields
E e t , j 2 ≤ ( U − L ) 2 exp ( − μ ∑ s = 1 t γ s ) + C B 1 n 2 γ t . \mathbb{E}e_{t,j}^{2}\leq(U-L)^2\exp\left(-\mu\sum_{s=1}^{t}\gamma_s\right)+CB_{1n}^{2}\gamma_t. E e t , j 2 ≤ ( U − L ) 2 exp ( − μ s = 1 ∑ t γ s ) + C B 1 n 2 γ t .
For the uniform probability bound, fix a deterministic r < t r<t r < t . Iterating (C.4) from r r r to t t t involves only the deterministic weights
ρ s , t = ∏ u = s + 1 t ( 1 − μ γ u ) , ρ t , t = 1. \rho_{s,t}=\prod_{u=s+1}^{t}(1-\mu\gamma_u),\qquad\rho_{t,t}=1. ρ s , t = u = s + 1 ∏ t ( 1 − μ γ u ) , ρ t , t = 1.
Because μ γ u ≤ 1 / 2 \mu\gamma_u\leq1/2 μ γ u ≤ 1/2 ,
ρ s , t ≤ exp ( − μ ∑ u = s + 1 t γ u ) . \rho_{s,t}\leq\exp\left(-\mu\sum_{u=s+1}^{t}\gamma_u\right). ρ s , t ≤ exp ( − μ u = s + 1 ∑ t γ u ) .
For every fixed q ≥ 1 q\geq1 q ≥ 1 and m > 1 m>1 m > 1 ,
∑ s = r + 1 t ρ s , t q γ s m ≤ C q , m γ t m − 1 , max r < s ≤ t ρ s , t q γ s m ≤ C q , m γ t m . (45) \sum_{s=r+1}^{t}\rho_{s,t}^{q}\gamma_s^{m}\leq C_{q,m}\gamma_t^{m-1},\qquad\max_{r<s\leq t}\rho_{s,t}^{q}\gamma_s^{m}\leq C_{q,m}\gamma_t^{m}. \tag*{(45)} s = r + 1 ∑ t ρ s , t q γ s m ≤ C q , m γ t m − 1 , r < s ≤ t max ρ s , t q γ s m ≤ C q , m γ t m . (45)
The maximum inequality in (C.7) also holds for every m > 0 m>0 m > 0 .
To verify these bounds, split the index set at t / 2 t/2 t /2 . If s > t / 2 s>t/2 s > t /2 , then γ s ≤ 2 a γ t \gamma_s\le2^a\gamma_t γ s ≤ 2 a γ t and
ρ s , t q ≤ exp { − q μ ( t − s ) γ t } . \rho^q_{s,t}\le\exp\{-q\mu(t-s)\gamma_t\}. ρ s , t q ≤ exp { − q μ ( t − s ) γ t } .
Consequently,
∑ t / 2 < s ≤ t ρ s , t q γ s m ≤ C γ t m ∑ h = 0 ∞ e − q μ h γ t ≤ C γ t m − 1 . \sum_{t/2<s\le t}\rho^q_{s,t}\gamma_s^m\le C\gamma_t^m\sum_{h=0}^{\infty}e^{-q\mu h\gamma_t}\le C\gamma_t^{m-1}. t /2 < s ≤ t ∑ ρ s , t q γ s m ≤ C γ t m h = 0 ∑ ∞ e − q μ h γ t ≤ C γ t m − 1 .
If s ≤ t / 2 s\le t/2 s ≤ t /2 , then
ρ s , t q ≤ exp { − q μ ∑ u = ⌊ t / 2 ⌋ + 1 t γ u } ≤ exp ( − c t 1 − a ) , \rho^q_{s,t}\le\exp\left\{-q\mu\sum_{u=\lfloor t/2\rfloor+1}^{t}\gamma_u\right\}\le\exp(-ct^{1-a}), ρ s , t q ≤ exp ⎩ ⎨ ⎧ − q μ u = ⌊ t /2 ⌋ + 1 ∑ t γ u ⎭ ⎬ ⎫ ≤ exp ( − c t 1 − a ) ,
and hence
∑ r < s ≤ t / 2 ρ s , t q γ s m ≤ C t e − c t 1 − a ≤ C γ t m − 1 . \sum_{r<s\le t/2}\rho^q_{s,t}\gamma_s^m\le Cte^{-ct^{1-a}}\le C\gamma_t^{m-1}. r < s ≤ t /2 ∑ ρ s , t q γ s m ≤ C t e − c t 1 − a ≤ C γ t m − 1 .
The same split proves the maximum bound. In particular,
∑ s = r + 1 t ρ s , t γ s 2 ≤ C γ t , max r < s ≤ t ρ s , t γ s ≤ C γ t . \sum_{s=r+1}^{t}\rho_{s,t}\gamma_s^2\le C\gamma_t,\qquad\max_{r<s\le t}\rho_{s,t}\gamma_s\le C\gamma_t. s = r + 1 ∑ t ρ s , t γ s 2 ≤ C γ t , r < s ≤ t max ρ s , t γ s ≤ C γ t .
For x ≥ 1 x\ge1 x ≥ 1 , define the first crossing time
τ = inf { s ∈ { r + 1 , … , n 1 } : e s , j 2 > C 0 [ ρ r , s e r , j 2 + B 1 n 2 { γ s x + γ s 2 x 2 } ] } , inf ∅ = n 1 + 1. \tau=\inf\left\{s\in\{r+1,\ldots,n_1\}:e_{s,j}^2>C_0\left[\rho_{r,s}e_{r,j}^2+B_{1n}^2\{\gamma_sx+\gamma_s^2x^2\}\right]\right\},\qquad\inf\varnothing=n_1+1. τ = inf { s ∈ { r + 1 , … , n 1 } : e s , j 2 > C 0 [ ρ r , s e r , j 2 + B 1 n 2 { γ s x + γ s 2 x 2 } ] } , inf ∅ = n 1 + 1.
For a fixed candidate terminal time t > r t>r t > r , put
M ~ u , t , j = ∑ s = r + 1 u 1 { τ ≥ s } ρ s , t Δ M s , j , r ≤ u ≤ t . \widetilde{M}_{u,t,j}=\sum_{s=r+1}^{u}\mathbf{1}\{\tau\ge s\}\rho_{s,t}\Delta M_{s,j},\qquad r\le u\le t. M u , t , j = s = r + 1 ∑ u 1 { τ ≥ s } ρ s , t Δ M s , j , r ≤ u ≤ t .
Because { τ ≥ s } ∈ F s − 1 \{\tau\ge s\}\in\mathcal{F}_{s-1} { τ ≥ s } ∈ F s − 1 and ρ s , t \rho_{s,t} ρ s , t is deterministic, ( M ~ u , t , j ) u = r t (\widetilde{M}_{u,t,j})_{u=r}^{t} ( M u , t , j ) u = r t is a martingale. Its predictable quadratic variation and largest increment are
V r , t , j = ∑ s = r + 1 t E [ { 1 ( τ ≥ s ) ρ s , t Δ M s , j } 2 ∣ F s − 1 ] , V_{r,t,j}=\sum_{s=r+1}^{t}\mathbb{E}\left[\{\mathbf{1}(\tau\ge s)\rho_{s,t}\Delta M_{s,j}\}^2\mid\mathcal{F}_{s-1}\right], V r , t , j = s = r + 1 ∑ t E [ { 1 ( τ ≥ s ) ρ s , t Δ M s , j } 2 ∣ F s − 1 ] ,
L r , t , j = max r < s ≤ t ∣ 1 ( τ ≥ s ) ρ s , t Δ M s , j ∣ . L_{r,t,j}=\max_{r<s\le t}\left|\mathbf{1}(\tau\ge s)\rho_{s,t}\Delta M_{s,j}\right|. L r , t , j = r < s ≤ t max ∣ 1 ( τ ≥ s ) ρ s , t Δ M s , j ∣ .
On { τ ≥ s } \{\tau\ge s\} { τ ≥ s } , if s ≥ r + 2 s\ge r+2 s ≥ r + 2 the absence of an earlier crossing gives the boundary at s − 1 s-1 s − 1 ; if s = r + 1 s=r+1 s = r + 1 , the same bound follows directly from e s − 1 , j = e r , j e_{s-1,j}=e_{r,j} e s − 1 , j = e r , j . Thus, in both cases,
e s − 1 , j 2 ≤ C [ ρ r , s − 1 e r , j 2 + B 1 n 2 { γ s x + γ s 2 x 2 } ] . e_{s-1,j}^2\le C\left[\rho_{r,s-1}e_{r,j}^2+B_{1n}^2\{\gamma_sx+\gamma_s^2x^2\}\right]. e s − 1 , j 2 ≤ C [ ρ r , s − 1 e r , j 2 + B 1 n 2 { γ s x + γ s 2 x 2 } ] .
Combining this bound with (C.5)–(C.6) gives
V r , t , j ≤ C [ B 1 n 2 e r , j 2 ρ r , t γ t + B 1 n 4 { γ t 2 x + γ t 3 x 2 } ] . (46) V_{r,t,j} \le C\left[B_{1n}^{2}e_{r,j}^{2}\rho_{r,t}\gamma_t+B_{1n}^{4}\{\gamma_t^{2}x+\gamma_t^{3}x^{2}\}\right]. \tag*{(46)} V r , t , j ≤ C [ B 1 n 2 e r , j 2 ρ r , t γ t + B 1 n 4 { γ t 2 x + γ t 3 x 2 } ] . (46)
L r , t , j ≤ C [ B 1 n ∣ e r , j ∣ ρ r , t 1 / 2 γ t + B 1 n 2 { γ t 3 / 2 x 1 / 2 + γ t 2 x } ] . (47) L_{r,t,j} \le C\left[B_{1n}|e_{r,j}|\rho_{r,t}^{1/2}\gamma_t+B_{1n}^{2}\{\gamma_t^{3/2}x^{1/2}+\gamma_t^{2}x\}\right]. \tag*{(47)} L r , t , j ≤ C [ B 1 n ∣ e r , j ∣ ρ r , t 1/2 γ t + B 1 n 2 { γ t 3/2 x 1/2 + γ t 2 x } ] . (47)
Here are the summations behind these two displays. The product identity and the gain restriction give
ρ s , t ρ r , s − 1 = ρ r , t 1 − μ γ s , ( 1 − μ γ s ) − 1 ≤ 2. \rho_{s,t}\rho_{r,s-1}=\frac{\rho_{r,t}}{1-\mu\gamma_s},\qquad(1-\mu\gamma_s)^{-1}\le2. ρ s , t ρ r , s − 1 = 1 − μ γ s ρ r , t , ( 1 − μ γ s ) − 1 ≤ 2.
Therefore,
∑ s = r + 1 t ρ s , t 2 γ s 2 ρ r , s − 1 ≤ C ρ r , t ∑ s = r + 1 t ρ s , t γ s 2 ≤ C ρ r , t γ t . (48) \sum_{s=r+1}^{t}\rho_{s,t}^{2}\gamma_s^{2}\rho_{r,s-1}\le C\rho_{r,t}\sum_{s=r+1}^{t}\rho_{s,t}\gamma_s^{2}\le C\rho_{r,t}\gamma_t. \tag*{(48)} s = r + 1 ∑ t ρ s , t 2 γ s 2 ρ r , s − 1 ≤ C ρ r , t s = r + 1 ∑ t ρ s , t γ s 2 ≤ C ρ r , t γ t . (48)
∑ s = r + 1 t ρ s , t 2 γ s 3 ≤ C γ t 2 , ∑ s = r + 1 t ρ s , t 2 γ s 4 ≤ C γ t 3 . \sum_{s=r+1}^{t}\rho_{s,t}^{2}\gamma_s^{3}\le C\gamma_t^{2},\qquad
\sum_{s=r+1}^{t}\rho_{s,t}^{2}\gamma_s^{4}\le C\gamma_t^{3}. s = r + 1 ∑ t ρ s , t 2 γ s 3 ≤ C γ t 2 , s = r + 1 ∑ t ρ s , t 2 γ s 4 ≤ C γ t 3 .
The corresponding maximum bounds are
max r < s ≤ t ρ s , t γ s ρ r , s − 1 ≤ C ρ r , t 1 / 2 γ t , (49) \max_{r<s\le t}\rho_{s,t}\gamma_s\rho_{r,s-1}\le C\rho_{r,t}^{1/2}\gamma_t, \tag*{(49)} r < s ≤ t max ρ s , t γ s ρ r , s − 1 ≤ C ρ r , t 1/2 γ t , (49)
max r < s ≤ t ρ s , t γ s 3 / 2 ≤ C γ t 3 / 2 , max r < s ≤ t ρ s , t γ s 2 ≤ C γ t 2 . (50) \max_{r<s\le t}\rho_{s,t}\gamma_s^{3/2}\le C\gamma_t^{3/2},\qquad
\max_{r<s\le t}\rho_{s,t}\gamma_s^{2}\le C\gamma_t^{2}. \tag*{(50)} r < s ≤ t max ρ s , t γ s 3/2 ≤ C γ t 3/2 , r < s ≤ t max ρ s , t γ s 2 ≤ C γ t 2 . (50)
Indeed, the square of the left-hand side of (C.11) is at most
C ρ r , t ρ s , t γ s 2 ≤ C ρ r , t γ t 2 C\rho_{r,t}\rho_{s,t}\gamma_s^{2}\le C\rho_{r,t}\gamma_t^{2} C ρ r , t ρ s , t γ s 2 ≤ C ρ r , t γ t 2
by (C.7). Equations (C.10)–(C.12) prove (C.8)–(C.9).
Let V ‾ r , t , j \overline{V}_{r,t,j} V r , t , j and L ‾ r , t , j \overline{L}_{r,t,j} L r , t , j denote the respective right-hand sides of (C.8) and (C.9). They are F r \mathcal{F}_r F r -measurable upper bounds for the predictable variation and the increment size. Freedman’s inequality now yields
P { M ~ t , t , j > 2 x V ‾ r , t , j + x L ‾ r , t , j 3 | F r } ≤ e − x . \mathbb{P}\left\{\widetilde{M}_{t,t,j}>\sqrt{2x\overline{V}_{r,t,j}}+\frac{x\overline{L}_{r,t,j}}{3}\,\middle|\,\mathcal{F}_r\right\}\le e^{-x}. P { M t , t , j > 2 x V r , t , j + 3 x L r , t , j F r } ≤ e − x .
The initialization terms in the Freedman threshold satisfy, for every fixed η > 0 \eta>0 η > 0 ,
B 1 n ∣ e r , j ∣ ρ r , t γ t x ≤ η ρ r , t e r , j 2 + C η B 1 n 2 γ t x , B_{1n}|e_{r,j}|\sqrt{\rho_{r,t}\gamma_tx}\le\eta\rho_{r,t}e_{r,j}^{2}+C_{\eta}B_{1n}^{2}\gamma_tx, B 1 n ∣ e r , j ∣ ρ r , t γ t x ≤ η ρ r , t e r , j 2 + C η B 1 n 2 γ t x ,
x B 1 n ∣ e r , j ∣ ρ r , t 1 / 2 γ t ≤ η ρ r , t e r , j 2 + C η B 1 n 2 γ t 2 x 2 . xB_{1n}|e_{r,j}|\rho_{r,t}^{1/2}\gamma_t\le\eta\rho_{r,t}e_{r,j}^{2}+C_{\eta}B_{1n}^{2}\gamma_t^{2}x^{2}. x B 1 n ∣ e r , j ∣ ρ r , t 1/2 γ t ≤ η ρ r , t e r , j 2 + C η B 1 n 2 γ t 2 x 2 .
Since ( γ t x ) 3 / 2 ≤ γ t x + ( γ t x ) 2 (\gamma_tx)^{3/2}\le\gamma_tx+(\gamma_tx)^2 ( γ t x ) 3/2 ≤ γ t x + ( γ t x ) 2 ,
2 x V ‾ r , t , j + x L ‾ r , t , j 3 ≤ C [ ρ r , t e r , j 2 + B 1 n 2 { γ t x + γ t 2 x 2 } ] . \sqrt{2x\overline{V}_{r,t,j}}+\frac{x\overline{L}_{r,t,j}}{3}\le C\left[\rho_{r,t}e_{r,j}^{2}+B_{1n}^{2}\{\gamma_tx+\gamma_t^{2}x^{2}\}\right]. 2 x V r , t , j + 3 x L r , t , j ≤ C [ ρ r , t e r , j 2 + B 1 n 2 { γ t x + γ t 2 x 2 } ] .
On { τ = t } \{\tau=t\} { τ = t } all indicators in M ~ t , t , j \widetilde{M}_{t,t,j} M t , t , j equal one, and iteration of (C.4) gives
e t , j 2 ≤ ρ r , t e r , j 2 + C B 1 n 2 γ t + M ~ t , t , j . e_{t,j}^{2}\leq\rho_{r,t}e_{r,j}^{2}+CB_{1n}^{2}\gamma_{t}+\widetilde{M}_{t,t,j}. e t , j 2 ≤ ρ r , t e r , j 2 + C B 1 n 2 γ t + M t , t , j .
Since x ≥ 1 x\geq1 x ≥ 1 , the middle term is absorbed by C B 1 n 2 γ t x CB_{1n}^{2}\gamma_{t}x C B 1 n 2 γ t x . Choosing C 0 C_{0} C 0 larger than the constants above therefore implies
{ τ = t } ⊆ { M ~ t , t , j > 2 x V ‾ r , t , j + x L ‾ r , t , j 3 } . \{\tau=t\}\subseteq\left\{\widetilde{M}_{t,t,j}>\sqrt{2x\overline{V}_{r,t,j}}+\frac{x\overline{L}_{r,t,j}}{3}\right\}. { τ = t } ⊆ { M t , t , j > 2 x V r , t , j + 3 x L r , t , j } .
Summing its probability over the possible first crossing times proves
P ( ∃ t ∈ { r + 1 , … , n 1 } : e t , j 2 > C [ ρ r , t e r , j 2 + B 1 n 2 { γ t x + γ t 2 x 2 } ] ∣ F r ) ≤ 2 ( n 1 − r ) e − x . (51) \mathbb{P}\left(\exists t\in\{r+1,\ldots,n_{1}\}:e_{t,j}^{2}>C\left[\rho_{r,t}e_{r,j}^{2}+B_{1n}^{2}\{\gamma_{t}x+\gamma_{t}^{2}x^{2}\}\right]\mid\mathcal{F}_{r}\right)\leq2(n_{1}-r)e^{-x}. \tag*{(51)} P ( ∃ t ∈ { r + 1 , … , n 1 } : e t , j 2 > C [ ρ r , t e r , j 2 + B 1 n 2 { γ t x + γ t 2 x 2 } ] ∣ F r ) ≤ 2 ( n 1 − r ) e − x . (51)
This argument is the bounded-noise, one-dimensional stopped Lyapunov specialization of the projected stochastic-approximation stability proof; (C.3)–(C.13) display the martingale and its predictable weights explicitly.
Step 2: uniform entry and inactive projection. Apply (C.13) with r = 0 r=0 r = 0 and x = c ℓ n x=c\ell_{n} x = c ℓ n , and take a union bound over j ≤ k n j\leq k_{n} j ≤ k n . Because ρ 0 , t ≤ exp ( − μ ∑ s = 1 t γ s ) \rho_{0,t}\leq\exp\left(-\mu\sum_{s=1}^{t}\gamma_{s}\right) ρ 0 , t ≤ exp ( − μ ∑ s = 1 t γ s ) , conditions (3.3)–(3.4) imply, for all sufficiently large n n n , that ∣ e t , j ∣ ≤ δ 0 \lvert e_{t,j}\rvert\leq\delta_{0} ∣ e t , j ∣ ≤ δ 0 simultaneously for t ≥ b n t\geq b_{n} t ≥ b n and j ≤ k n j\leq k_{n} j ≤ k n . If t > b n t>b_{n} t > b n , the unprojected displacement is bounded by
γ t { ∣ h t − 1 , j ∣ + ∣ ζ t , j ∣ } ≤ C γ b n B 1 n = o ( δ 0 ) . \gamma_{t}\{\lvert h_{t-1,j}\rvert+\lvert\zeta_{t,j}\rvert\}\leq C\gamma_{b_{n}}B_{1n}=o(\delta_{0}). γ t {∣ h t − 1 , j ∣ + ∣ ζ t , j ∣} ≤ C γ b n B 1 n = o ( δ 0 ) .
Since every Q j , n Q_{j,n} Q j , n is at least 3 δ 0 3\delta_{0} 3 δ 0 from the endpoints of the public bracket, the unprojected update remains in [ L , U ] [L,U] [ L , U ] . Projection is therefore inactive after b n b_{n} b n .
Finally apply (C.13) conditionally with r = b n r=b_{n} r = b n . The deterministic weights satisfy
ρ b n , t 1 / 2 ≤ exp ( − μ 2 ∑ s = b n + 1 t γ s ) . \rho_{b_{n},t}^{1/2}\leq\exp\left(-\frac{\mu}{2}\sum_{s=b_{n}+1}^{t}\gamma_{s}\right). ρ b n , t 1/2 ≤ exp ( − 2 μ s = b n + 1 ∑ t γ s ) .
Taking square roots and union bounding over ( t , j ) (t,j) ( t , j ) gives (C.2) and completes the three assertions.
Step 3: a concrete b n b_{n} b n . For γ t = γ 0 t − a \gamma_{t}=\gamma_{0}t^{-a} γ t = γ 0 t − a ,
∑ s = 1 b n γ s ≍ b n 1 − a , γ b n ≍ b n − a . \sum_{s=1}^{b_{n}}\gamma_{s}\asymp b_{n}^{1-a},\qquad\gamma_{b_{n}}\asymp b_{n}^{-a}. s = 1 ∑ b n γ s ≍ b n 1 − a , γ b n ≍ b n − a .
The displayed order for b n b_{n} b n simultaneously makes the initialization factor polynomially small and B 1 n γ b n ℓ n = O ( ω n − 1 / 2 ) = o ( 1 ) B_{1n}\sqrt{\gamma_{b_{n}}\ell_{n}}=O(\omega_{n}^{-1/2})=o(1) B 1 n γ b n ℓ n = O ( ω n − 1/2 ) = o ( 1 ) . The corresponding requirement B 1 n 2 ℓ n ω n = o ( n 1 a ) B_{1n}^{2}\ell_{n}\omega_{n}=o(n_{1}^{a}) B 1 n 2 ℓ n ω n = o ( n 1 a ) permits b n = o ( n 1 ) b_{n}=o(n_{1}) b n = o ( n 1 ) . This completes the proof. □ \square □
Lemma C.2 (Abel decomposition for the full average). Suppose Assumption 3.2 holds. On
E l o c , n \mathcal{E}_{\mathrm{loc},n} E loc , n , for each j j j ,
f ( Q j , n ) 1 n 1 ∑ t = b n + 1 n 1 e t − 1 , j = − 1 n 1 ∑ t = b n + 1 n 1 ζ t , j − 1 n 1 ∑ t = b n + 1 n 1 R t − 1 , j + 1 n 1 { e b n , j γ b n + 1 − e n 1 , j γ n 1 + ∑ t = b n + 1 n 1 − 1 e t , j ( 1 γ t + 1 − 1 γ t ) } . (52) f(Q_{j,n})\frac{1}{n_1}\sum_{t=b_n+1}^{n_1}e_{t-1,j}
= -\frac{1}{n_1}\sum_{t=b_n+1}^{n_1}\zeta_{t,j}
-\frac{1}{n_1}\sum_{t=b_n+1}^{n_1}\mathcal{R}_{t-1,j}
+\frac{1}{n_1}\left\{\frac{e_{b_n,j}}{\gamma_{b_n+1}}-\frac{e_{n_1,j}}{\gamma_{n_1}}+\sum_{t=b_n+1}^{n_1-1}e_{t,j}\left(\frac{1}{\gamma_{t+1}}-\frac{1}{\gamma_t}\right)\right\}. \tag*{(52)} f ( Q j , n ) n 1 1 t = b n + 1 ∑ n 1 e t − 1 , j = − n 1 1 t = b n + 1 ∑ n 1 ζ t , j − n 1 1 t = b n + 1 ∑ n 1 R t − 1 , j + n 1 1 { γ b n + 1 e b n , j − γ n 1 e n 1 , j + t = b n + 1 ∑ n 1 − 1 e t , j ( γ t + 1 1 − γ t 1 ) } . (52)
where
R t − 1 , j = F ( Q j , n + e t − 1 , j ) − F ( Q j , n ) − f ( Q j , n ) e t − 1 , j \mathcal{R}_{t-1,j}=F(Q_{j,n}+e_{t-1,j})-F(Q_{j,n})-f(Q_{j,n})e_{t-1,j} R t − 1 , j = F ( Q j , n + e t − 1 , j ) − F ( Q j , n ) − f ( Q j , n ) e t − 1 , j
satisfies
∣ R t − 1 , j ∣ ≤ L f 1 + β ∣ e t − 1 , j ∣ 1 + β . (53) |\mathcal{R}_{t-1,j}|\leq\frac{L_f}{1+\beta}|e_{t-1,j}|^{1+\beta}. \tag*{(53)} ∣ R t − 1 , j ∣ ≤ 1 + β L f ∣ e t − 1 , j ∣ 1 + β . (53)
Proof. Projection is inactive after b n b_n b n , so
e t , j = e t − 1 , j − γ t { F ( Q j , n + e t − 1 , j ) − F ( Q j , n ) + ζ t , j } . e_{t,j}=e_{t-1,j}-\gamma_t\{F(Q_{j,n}+e_{t-1,j})-F(Q_{j,n})+\zeta_{t,j}\}. e t , j = e t − 1 , j − γ t { F ( Q j , n + e t − 1 , j ) − F ( Q j , n ) + ζ t , j } .
Rearrange this equality to obtain
f ( Q j , n ) e t − 1 , j = e t − 1 , j − e t , j γ t − ζ t , j − R t − 1 , j . f(Q_{j,n})e_{t-1,j}=\frac{e_{t-1,j}-e_{t,j}}{\gamma_t}-\zeta_{t,j}-\mathcal{R}_{t-1,j}. f ( Q j , n ) e t − 1 , j = γ t e t − 1 , j − e t , j − ζ t , j − R t − 1 , j .
Summing from b n + 1 b_n+1 b n + 1 to n 1 n_1 n 1 gives the first two terms in (C.14). For the difference term,
∑ t = b n + 1 n 1 e t − 1 , j − e t , j γ t = e b n , j γ b n + 1 − e n 1 , j γ n 1 + ∑ t = b n + 1 n 1 − 1 e t , j ( 1 γ t + 1 − 1 γ t ) , \sum_{t=b_n+1}^{n_1}\frac{e_{t-1,j}-e_{t,j}}{\gamma_t}
=\frac{e_{b_n,j}}{\gamma_{b_n+1}}-\frac{e_{n_1,j}}{\gamma_{n_1}}+\sum_{t=b_n+1}^{n_1-1}e_{t,j}\left(\frac{1}{\gamma_{t+1}}-\frac{1}{\gamma_t}\right), t = b n + 1 ∑ n 1 γ t e t − 1 , j − e t , j = γ b n + 1 e b n , j − γ n 1 e n 1 , j + t = b n + 1 ∑ n 1 − 1 e t , j ( γ t + 1 1 − γ t 1 ) ,
which is summation by parts. Finally,
R t − 1 , j = e t − 1 , j ∫ 0 1 { f ( Q j , n + s e t − 1 , j ) − f ( Q j , n ) } d s , \mathcal{R}_{t-1,j}=e_{t-1,j}\int_0^1\{f(Q_{j,n}+se_{t-1,j})-f(Q_{j,n})\}\,\mathrm{d}s, R t − 1 , j = e t − 1 , j ∫ 0 1 { f ( Q j , n + s e t − 1 , j ) − f ( Q j , n )} d s ,
so Assumption 3.2 yields (C.15).
Lemma C.3. (Uniform bounds for the terms in (C.14)). Under Assumptions 3.1 to 3.4, on events whose probabilities tend to one,
max j ≤ k n ∣ 1 n 1 ∑ t = b n + 1 n 1 ζ t , j ∣ ≤ C B 1 n ℓ n n 1 , (54) \max_{j\leq k_n}\left|\frac{1}{n_1}\sum_{t=b_n+1}^{n_1}\zeta_{t,j}\right|\leq CB_1n\sqrt{\frac{\ell_n}{n_1}}, \tag*{(54)} j ≤ k n max n 1 1 t = b n + 1 ∑ n 1 ζ t , j ≤ C B 1 n n 1 ℓ n , (54) max j ≤ k n 1 n 1 ∣ e b n , j γ b n + 1 − e n 1 , j γ n 1 + ∑ t = b n + 1 n 1 − 1 e t , j ( 1 γ t + 1 − 1 γ t ) ∣ ≤ C B 1 n n 1 a / 2 − 1 ℓ n + o ( r 1 n ) , (55) \max_{j\leq k_n}\frac{1}{n_1}\left|\frac{e_{b_n,j}}{\gamma_{b_n+1}}-\frac{e_{n_1,j}}{\gamma_{n_1}}+\sum_{t=b_n+1}^{n_1-1}e_{t,j}\left(\frac{1}{\gamma_{t+1}}-\frac{1}{\gamma_t}\right)\right|\leq CB_1n n_1^{a/2-1}\sqrt{\ell_n}+o(r_1n), \tag*{(55)} j ≤ k n max n 1 1 γ b n + 1 e b n , j − γ n 1 e n 1 , j + t = b n + 1 ∑ n 1 − 1 e t , j ( γ t + 1 1 − γ t 1 ) ≤ C B 1 n n 1 a /2 − 1 ℓ n + o ( r 1 n ) , (55) max j ≤ k n 1 n 1 ∑ t = b n + 1 n 1 ∣ R t − 1 , j ∣ ≤ C B 1 1 + β n n 1 − a ( 1 + β ) / 2 ℓ n ( 1 + β ) / 2 + o ( r 1 n ) . (56) \max_{j\leq k_n}\frac{1}{n_1}\sum_{t=b_n+1}^{n_1}|\mathcal{R}_{t-1,j}|\leq CB_1^{1+\beta}n n_1^{-a(1+\beta)/2}\ell_n^{(1+\beta)/2}+o(r_1n). \tag*{(56)} j ≤ k n max n 1 1 t = b n + 1 ∑ n 1 ∣ R t − 1 , j ∣ ≤ C B 1 1 + β n n 1 − a ( 1 + β ) /2 ℓ n ( 1 + β ) /2 + o ( r 1 n ) . (56)
The displayed o ( r 1 n ) o(r_{1n}) o ( r 1 n ) terms collect the exponentially decaying initialization contribution.
Proof. For (C.16), apply Bernstein’s martingale inequality to the bounded differences ζ t , j \zeta_{t,j} ζ t , j and use a union bound over j j j . The resulting bound is
C B 1 n { ℓ n n 1 + ℓ n n 1 } . CB_{1n}\left\{\sqrt{\frac{\ell_n}{n_1}}+\frac{\ell_n}{n_1}\right\}. C B 1 n { n 1 ℓ n + n 1 ℓ n } .
By (3.4), b n < n 1 b_n<n_1 b n < n 1 , and γ b n = γ 0 b n − a \gamma_{b_n}=\gamma_0b_n^{-a} γ b n = γ 0 b n − a , B 1 n 2 ℓ n = o ( b n a ) = o ( n 1 a ) B_{1n}^2\ell_n=o(b_n^a)=o(n_1^a) B 1 n 2 ℓ n = o ( b n a ) = o ( n 1 a ) . Since a < 1 a<1 a < 1 , this implies ℓ n / n 1 = o ( 1 ) \ell_n/n_1=o(1) ℓ n / n 1 = o ( 1 ) , so the second term is dominated by the first.
For (C.17), write b = b n b=b_n b = b n and put
D b , t = exp ( − μ 2 ∑ s = b + 1 t γ s ) , D b , b = 1. D_{b,t}=\exp\left(-\frac{\mu}{2}\sum_{s=b+1}^{t}\gamma_s\right),\qquad D_{b,b}=1. D b , t = exp ( − 2 μ s = b + 1 ∑ t γ s ) , D b , b = 1.
The same near–far split used in (C.7) gives, for every fixed q > 0 q>0 q > 0 ,
sup t ≥ b D b , t ( γ b γ t ) q ≤ C q , (57) \sup_{t\ge b}D_{b,t}\left(\frac{\gamma_b}{\gamma_t}\right)^q\le C_q, \tag*{(57)} t ≥ b sup D b , t ( γ t γ b ) q ≤ C q , (57)
∑ t = b N D b , t q ≤ C q γ b − 1 , (58) \sum_{t=b}^{N}D_{b,t}^q\le C_q\gamma_b^{-1}, \tag*{(58)} t = b ∑ N D b , t q ≤ C q γ b − 1 , (58)
D b , N γ N + ∑ t = b + 1 N − 1 D b , t t a − 1 ≤ C γ b − 1 . (59) \frac{D_{b,N}}{\gamma_N}+\sum_{t=b+1}^{N-1}D_{b,t}t^{a-1}\le C\gamma_b^{-1}. \tag*{(59)} γ N D b , N + t = b + 1 ∑ N − 1 D b , t t a − 1 ≤ C γ b − 1 . (59)
Indeed, when b < t ≤ 2 b b<t\le2b b < t ≤ 2 b ,
∑ s = b + 1 t γ s ≥ c ( t − b ) γ b , \sum_{s=b+1}^{t}\gamma_s\ge c(t-b)\gamma_b, s = b + 1 ∑ t γ s ≥ c ( t − b ) γ b ,
so the corresponding sums are dominated by a geometric series with effective length O ( γ b − 1 ) O(\gamma_b^{-1}) O ( γ b − 1 ) . When t > 2 b t>2b t > 2 b ,
∑ s = b + 1 t γ s ≥ c ( t 1 − a − b 1 − a ) , \sum_{s=b+1}^{t}\gamma_s\ge c\left(t^{1-a}-b^{1-a}\right), s = b + 1 ∑ t γ s ≥ c ( t 1 − a − b 1 − a ) ,
and the remaining tail is exponentially small.
Applying (C.13) with r = 0 r=0 r = 0 and x = c ℓ n x=c\ell_n x = c ℓ n at time b b b gives
∣ e b , j ∣ ≤ d 0 n + C B 1 n { γ b ℓ n + γ b ℓ n } , d 0 n = ( U − L ) e − μ 2 ∑ s = 1 b γ s = o ( r 1 n ) . |e_{b,j}|\le d_{0n}+CB_{1n}\left\{\sqrt{\gamma_b\ell_n}+\gamma_b\ell_n\right\},\qquad d_{0n}=(U-L)e^{-\frac{\mu}{2}\sum_{s=1}^{b}\gamma_s}=o(r_{1n}). ∣ e b , j ∣ ≤ d 0 n + C B 1 n { γ b ℓ n + γ b ℓ n } , d 0 n = ( U − L ) e − 2 μ ∑ s = 1 b γ s = o ( r 1 n ) .
Combining this display with (C.2) and (C.19) yields
∣ e t , j ∣ ≤ C D b , t d 0 n + C B 1 n { γ t ℓ n + γ t ℓ n } . (60) |e_{t,j}|\le CD_{b,t}d_{0n}+CB_{1n}\left\{\sqrt{\gamma_t\ell_n}+\gamma_t\ell_n\right\}. \tag*{(60)} ∣ e t , j ∣ ≤ C D b , t d 0 n + C B 1 n { γ t ℓ n + γ t ℓ n } . (60)
Here we used, respectively, q = 1 / 2 q=1/2 q = 1/2 and q = 1 q=1 q = 1 in (C.19) to propagate the two stochastic terms at time b b b . By (3.4), B 1 n ≥ 1 B_{1n} \ge1 B 1 n ≥ 1 , and monotonicity of the gain, γ t ℓ n ≤ γ b ℓ n = o ( 1 ) \gamma_t \ell_n \le\gamma_b \ell_n = o(1) γ t ℓ n ≤ γ b ℓ n = o ( 1 ) for t ≥ b t \ge b t ≥ b ; hence the second term in (C.22) is bounded by C B 1 n t − a / 2 ℓ n C B_{1n} t^{-a/2}\sqrt{\ell_n} C B 1 n t − a /2 ℓ n .
The contribution of the deterministic initialization to the Abel bracket is, by (C.21),
C d 0 n n 1 [ γ b − 1 + D b , n 1 γ n 1 + ∑ t = b + 1 n 1 − 1 D b , t t a − 1 ] ≤ C d 0 n n 1 γ b = o ( r 1 n ) , \frac{C d_{0n}}{n_1}\left[\gamma_b^{-1}+\frac{D_{b,n_1}}{\gamma_{n_1}}+\sum_{t=b+1}^{n_1-1}D_{b,t}t^{a-1}\right]\le\frac{C d_{0n}}{n_1\gamma_b}=o(r_{1n}), n 1 C d 0 n [ γ b − 1 + γ n 1 D b , n 1 + t = b + 1 ∑ n 1 − 1 D b , t t a − 1 ] ≤ n 1 γ b C d 0 n = o ( r 1 n ) ,
because b = o ( n 1 ) b=o(n_1) b = o ( n 1 ) and a < 1 a<1 a < 1 imply n 1 γ b ≍ n 1 b − a → ∞ n_1\gamma_b\asymp n_1b^{-a}\to\infty n 1 γ b ≍ n 1 b − a → ∞ . For the remaining terms,
1 γ t + 1 − 1 γ t = γ 0 − 1 { ( t + 1 ) a − t a } ≤ C t a − 1 , \frac{1}{\gamma_{t+1}}-\frac{1}{\gamma_t}=\gamma_0^{-1}\{(t+1)^a-t^a\}\le Ct^{a-1}, γ t + 1 1 − γ t 1 = γ 0 − 1 {( t + 1 ) a − t a } ≤ C t a − 1 ,
and therefore
∑ t = b + 1 n 1 − 1 ∣ e t , j ∣ ( 1 γ t + 1 − 1 γ t ) ≤ C B 1 n ℓ n ∑ t ≤ n 1 t a / 2 − 1 + o ( n 1 r 1 n ) ≤ C B 1 n ℓ n n 1 a / 2 + o ( n 1 r 1 n ) . \sum_{t=b+1}^{n_1-1}|e_{t,j}|\left(\frac{1}{\gamma_{t+1}}-\frac{1}{\gamma_t}\right)\le C B_{1n}\sqrt{\ell_n}\sum_{t\le n_1}t^{a/2-1}+o(n_1r_{1n})\le C B_{1n}\sqrt{\ell_n}n_1^{a/2}+o(n_1r_{1n}). t = b + 1 ∑ n 1 − 1 ∣ e t , j ∣ ( γ t + 1 1 − γ t 1 ) ≤ C B 1 n ℓ n t ≤ n 1 ∑ t a /2 − 1 + o ( n 1 r 1 n ) ≤ C B 1 n ℓ n n 1 a /2 + o ( n 1 r 1 n ) .
The two endpoint terms obey the same bound:
∣ e b , j ∣ γ b + 1 + ∣ e n 1 , j ∣ γ n 1 ≤ C B 1 n ℓ n n 1 a / 2 + o ( n 1 r 1 n ) . \frac{|e_{b,j}|}{\gamma_{b+1}}+\frac{|e_{n_1,j}|}{\gamma_{n_1}}\le C B_{1n}\sqrt{\ell_n}n_1^{a/2}+o(n_1r_{1n}). γ b + 1 ∣ e b , j ∣ + γ n 1 ∣ e n 1 , j ∣ ≤ C B 1 n ℓ n n 1 a /2 + o ( n 1 r 1 n ) .
Dividing by n 1 n_1 n 1 proves (C.17).
For (C.18), combine (C.15) and (C.22). Since ( x + y ) 1 + β ≤ 2 β ( x 1 + β + y 1 + β ) (x+y)^{1+\beta}\le2^\beta(x^{1+\beta}+y^{1+\beta}) ( x + y ) 1 + β ≤ 2 β ( x 1 + β + y 1 + β ) ,
∣ e t , j ∣ 1 + β ≤ C D b , t 1 + β d 0 n 1 + β + C B 1 n 1 + β γ t ( 1 + β ) / 2 ℓ n ( 1 + β ) / 2 . |e_{t,j}|^{1+\beta}\le C D_{b,t}^{1+\beta}d_{0n}^{1+\beta}+C B_{1n}^{1+\beta}\gamma_t^{(1+\beta)/2}\ell_n^{(1+\beta)/2}. ∣ e t , j ∣ 1 + β ≤ C D b , t 1 + β d 0 n 1 + β + C B 1 n 1 + β γ t ( 1 + β ) /2 ℓ n ( 1 + β ) /2 .
The stochastic sum is bounded by
B 1 n 1 + β ℓ n ( 1 + β ) / 2 n 1 ∑ t ≤ n 1 t − a ( 1 + β ) / 2 ≤ C B 1 n 1 + β ℓ n ( 1 + β ) / 2 n 1 − a ( 1 + β ) / 2 , \frac{B_{1n}^{1+\beta}\ell_n^{(1+\beta)/2}}{n_1}\sum_{t\le n_1}t^{-a(1+\beta)/2}\le C B_{1n}^{1+\beta}\ell_n^{(1+\beta)/2}n_1^{-a(1+\beta)/2}, n 1 B 1 n 1 + β ℓ n ( 1 + β ) /2 t ≤ n 1 ∑ t − a ( 1 + β ) /2 ≤ C B 1 n 1 + β ℓ n ( 1 + β ) /2 n 1 − a ( 1 + β ) /2 ,
where a ( 1 + β ) / 2 < 1 a(1+\beta)/2<1 a ( 1 + β ) /2 < 1 . By (C.20), the initialization contribution is at most
C d 0 n 1 + β n 1 γ b = o ( r 1 n ) , \frac{C d_{0n}^{1+\beta}}{n_1\gamma_b}=o(r_{1n}), n 1 γ b C d 0 n 1 + β = o ( r 1 n ) ,
because d 0 n = o { min ( r 1 n , 1 ) } d_{0n}=o\{\min(r_{1n},1)\} d 0 n = o { min ( r 1 n , 1 )} and n 1 γ b → ∞ n_1\gamma_b\to\infty n 1 γ b → ∞ . This proves all three bounds.
Proof of Theorem 3.7. Write f j = f ( Q j , n ) f_j=f(Q_{j,n}) f j = f ( Q j , n ) . Since
∑ t = b n + 1 n 1 e t , j = ∑ t = b n + 1 n 1 e t − 1 , j + e n 1 , j − e b n , j , \sum_{t=bn+1}^{n_1}e_{t,j}=\sum_{t=bn+1}^{n_1}e_{t-1,j}+e_{n_1,j}-e_{bn,j}, t = bn + 1 ∑ n 1 e t , j = t = bn + 1 ∑ n 1 e t − 1 , j + e n 1 , j − e bn , j ,
Lemma C.2 gives the exact expansion
f j ( q j 0 − Q j , n ) = − 1 n 1 ∑ t = b n + 1 n 1 ζ t , j + R 1 n , j , f_j(q_j^0-Q_{j,n})=-\frac{1}{n_1}\sum_{t=b_n+1}^{n_1}\zeta_{t,j}+R_{1n,j}, f j ( q j 0 − Q j , n ) = − n 1 1 t = b n + 1 ∑ n 1 ζ t , j + R 1 n , j ,
where
R 1 n , j = f j n 1 ∑ t = 1 b n e t , j + f j n 1 ( e n 1 , j − e b n , j ) − 1 n 1 ∑ t = b n + 1 n 1 R t − 1 , j + 1 n 1 { e b n , j γ b n + 1 − e n 1 , j γ n 1 + ∑ t = b n + 1 n 1 − 1 e t , j ( 1 γ t + 1 − 1 γ t ) } . (61) \begin{aligned}
R_{1n,j}={}&\frac{f_j}{n_1}\sum_{t=1}^{b_n}e_{t,j}+\frac{f_j}{n_1}(e_{n_1,j}-e_{b_n,j})\\
&-\frac{1}{n_1}\sum_{t=b_n+1}^{n_1}\mathcal{R}_{t-1,j}
+\frac{1}{n_1}\left\{\frac{e_{b_n,j}}{\gamma_{b_n+1}}-\frac{e_{n_1,j}}{\gamma_{n_1}}+\sum_{t=b_n+1}^{n_1-1}e_{t,j}\left(\frac{1}{\gamma_{t+1}}-\frac{1}{\gamma_t}\right)\right\}. \tag*{(61)}
\end{aligned} R 1 n , j = n 1 f j t = 1 ∑ b n e t , j + n 1 f j ( e n 1 , j − e b n , j ) − n 1 1 t = b n + 1 ∑ n 1 R t − 1 , j + n 1 1 { γ b n + 1 e b n , j − γ n 1 e n 1 , j + t = b n + 1 ∑ n 1 − 1 e t , j ( γ t + 1 1 − γ t 1 ) } . (61)
The first term is at most f + ( U − L ) b n / n 1 f_+(U-L)b_n/n_1 f + ( U − L ) b n / n 1 . By (C.22),
∣ e n 1 , j ∣ + ∣ e b n , j ∣ n 1 ≤ C d 0 n n 1 + C B 1 n 1 a / 2 − 1 ℓ n = o ( r 1 n ) + O ( B 1 n 1 a / 2 − 1 ℓ n ) . \frac{|e_{n_1,j}|+|e_{b_n,j}|}{n_1}\leq\frac{Cd_0n}{n_1}+CB_1n_1^{a/2-1}\sqrt{\ell_n}=o(r_{1n})+O\left(B_1n_1^{a/2-1}\sqrt{\ell_n}\right). n 1 ∣ e n 1 , j ∣ + ∣ e b n , j ∣ ≤ n 1 C d 0 n + C B 1 n 1 a /2 − 1 ℓ n = o ( r 1 n ) + O ( B 1 n 1 a /2 − 1 ℓ n ) .
The last two terms in (C.23) are bounded by (C.18) and (C.17). Together with (C.16), these are exactly the four orders in (20) . Since f j ≥ f − f_j\geq f_- f j ≥ f − uniformly, this proves (23) and (24) . □
Proof of Proposition 2.3. For b > 0 b>0 b > 0 ,
q ‾ n 1 , j = b n 1 ( 1 b ∑ t = 1 b q t , j ) + n 1 − b n 1 q ‾ n 1 , j ( b ) . \overline{q}_{n_1,j}=\frac{b}{n_1}\left(\frac{1}{b}\sum_{t=1}^{b}q_{t,j}\right)+\frac{n_1-b}{n_1}\overline{q}^{(b)}_{n_1,j}. q n 1 , j = n 1 b ( b 1 t = 1 ∑ b q t , j ) + n 1 n 1 − b q n 1 , j ( b ) .
Therefore
q ‾ n 1 , j ( b ) − q ‾ n 1 , j = b n 1 { q ‾ n 1 , j ( b ) − 1 b ∑ t = 1 b q t , j } . \overline{q}^{(b)}_{n_1,j}-\overline{q}_{n_1,j}
=\frac{b}{n_1}\left\{\overline{q}^{(b)}_{n_1,j}-\frac{1}{b}\sum_{t=1}^{b}q_{t,j}\right\}. q n 1 , j ( b ) − q n 1 , j = n 1 b { q n 1 , j ( b ) − b 1 t = 1 ∑ b q t , j } .
Both terms in braces lie in [ L , U ] [L,U] [ L , U ] , so the absolute difference is at most ( U − L ) b / n 1 (U-L)b/n_1 ( U − L ) b / n 1 . The case b = 0 b=0 b = 0 is immediate. □
Private Density Estimation and the One-Step Expansion
Lemma D.1 (Conditional concentration of Stage-2 CDF scores). Under Assumption 3.1, conditional on Stage 1, with conditional probability tending to one,
max j ≤ k n { ∣ G ‾ j , − ( 2 ) − F ( q j 0 − h n ) ∣ , ∣ G ‾ j , + ( 2 ) − F ( q j 0 + h n ) ∣ } ≤ C B 2 n { ℓ n n 2 + ℓ n n 2 } . \max_{j\leq k_n}\left\{\left|\overline{G}^{(2)}_{j,-}-F(q_j^0-h_n)\right|,\left|\overline{G}^{(2)}_{j,+}-F(q_j^0+h_n)\right|\right\}\leq CB_{2n}\left\{\sqrt{\frac{\ell_n}{n_2}}+\frac{\ell_n}{n_2}\right\}. j ≤ k n max { G j , − ( 2 ) − F ( q j 0 − h n ) , G j , + ( 2 ) − F ( q j 0 + h n ) } ≤ C B 2 n { n 2 ℓ n + n 2 ℓ n } .
Proof. Once Stage 1 is fixed, the 2 k n 2k_n 2 k n thresholds, their ranks, and all anchors are deterministic. The Stage-2 user vectors are conditionally i.i.d. By Proposition 2.1, each coordinate is unbiased and bounded in absolute value by B 2 n B_{2n} B 2 n . Therefore the centered coordinate is bounded by 2 B 2 n 2B_{2n} 2 B 2 n . For either sign, Bernstein’s inequality gives, for any x > 0 x>0 x > 0 ,
P ( ∣ G ‾ j , ± ( 2 ) − F ( q j 0 ± h n ) ∣ > C B 2 n { x / n 2 + x / n 2 } | F n 1 ) ≤ 2 e − x . \mathbb{P}\left(\left|\overline{G}_{j,\pm}^{(2)}-F(q_j^0\pm h_n)\right|>CB_{2n}\left\{\sqrt{x/n_2}+x/n_2\right\}\middle|\mathcal{F}_{n_1}\right)\le2e^{-x}. P ( G j , ± ( 2 ) − F ( q j 0 ± h n ) > C B 2 n { x / n 2 + x / n 2 } F n 1 ) ≤ 2 e − x .
Set x = c ℓ n x=c\ell_n x = c ℓ n and union bound over 2 k n 2k_n 2 k n tagged coordinates. Integration over Stage 1 proves the result.
Proof of Theorem 3.8. By Theorem 3.7, max j ∣ q j 0 − Q j , n ∣ = O P ( r 1 n ) = o P ( δ 0 ) \max_j|q_j^0-Q_{j,n}|=O_{\mathbb{P}}(r_{1n})=o_{\mathbb{P}}(\delta_0) max j ∣ q j 0 − Q j , n ∣ = O P ( r 1 n ) = o P ( δ 0 ) , while h n = o ( δ 0 ) h_n=o(\delta_0) h n = o ( δ 0 ) . Hence, with probability tending to one, q j 0 ± h n q_j^0\pm h_n q j 0 ± h n lie in N n \mathcal{N}_n N n and in the interior of [ L , U ] [L,U] [ L , U ] for every j j j ; endpoint projection is inactive.
Define the conditional population finite difference
f j , h 0 = F ( q j 0 + h n ) − F ( q j 0 − h n ) 2 h n = 1 2 h n ∫ − h n h n f ( q j 0 + u ) d u . f_{j,h}^0=\frac{F(q_j^0+h_n)-F(q_j^0-h_n)}{2h_n}=\frac{1}{2h_n}\int_{-h_n}^{h_n}f(q_j^0+u)\,du. f j , h 0 = 2 h n F ( q j 0 + h n ) − F ( q j 0 − h n ) = 2 h n 1 ∫ − h n h n f ( q j 0 + u ) d u .
For every u ∈ [ − h n , h n ] u\in[-h_n,h_n] u ∈ [ − h n , h n ] , Assumption 3.2 gives
∣ f ( q j 0 + u ) − f ( Q j , n ) ∣ ≤ L f ∣ q j 0 − Q j , n + u ∣ β ≤ L f { ∣ q j 0 − Q j , n ∣ β + ∣ u ∣ β } , \begin{aligned}
|f(q_j^0+u)-f(Q_{j,n})|&\le L_f|q_j^0-Q_{j,n}+u|^\beta\\
&\le L_f\{|q_j^0-Q_{j,n}|^\beta+|u|^\beta\},
\end{aligned} ∣ f ( q j 0 + u ) − f ( Q j , n ) ∣ ≤ L f ∣ q j 0 − Q j , n + u ∣ β ≤ L f { ∣ q j 0 − Q j , n ∣ β + ∣ u ∣ β } ,
where ( x + y ) β ≤ x β + y β (x+y)^\beta\le x^\beta+y^\beta ( x + y ) β ≤ x β + y β for β ≤ 1 \beta\le1 β ≤ 1 . Averaging over u u u yields
max j ∣ f j , h 0 − f ( Q j , n ) ∣ ≤ C { max ℓ ≤ k n ∣ q ℓ 0 − Q ℓ , n ∣ β + h n β } = O P { r 1 n β + h n β } . (62) \max_j|f_{j,h}^0-f(Q_{j,n})|\le C\left\{\max_{\ell\le k_n}|q_\ell^0-Q_{\ell,n}|^\beta+h_n^\beta\right\}=O_{\mathbb{P}}\{r_{1n}^\beta+h_n^\beta\}. \tag*{(62)} j max ∣ f j , h 0 − f ( Q j , n ) ∣ ≤ C { ℓ ≤ k n max ∣ q ℓ 0 − Q ℓ , n ∣ β + h n β } = O P { r 1 n β + h n β } . (62)
By Lemma D.1,
max j ∣ f ~ j − f j , h 0 ∣ ≤ 1 2 h n max j ( ∣ G ‾ j , + ( 2 ) − F ( q j 0 + h n ) ∣ + ∣ G ‾ j , − ( 2 ) − F ( q j 0 − h n ) ∣ ) ≤ C B 2 n h n { ℓ n n 2 + ℓ n n 2 } . (63) \begin{aligned}
\max_j|\widetilde f_j-f_{j,h}^0|\le\frac{1}{2h_n}\max_j\left(|\overline{G}_{j,+}^{(2)}-F(q_j^0+h_n)|+|\overline{G}_{j,-}^{(2)}-F(q_j^0-h_n)|\right) \\
&\le C\frac{B_{2n}}{h_n}\left\{\sqrt{\frac{\ell_n}{n_2}}+\frac{\ell_n}{n_2}\right\}. \tag*{(63)}
\end{aligned} j max ∣ f j − f j , h 0 ∣ ≤ 2 h n 1 j max ( ∣ G j , + ( 2 ) − F ( q j 0 + h n ) ∣ + ∣ G j , − ( 2 ) − F ( q j 0 − h n ) ∣ ) ≤ C h n B 2 n { n 2 ℓ n + n 2 ℓ n } . (63)
Combining (D.1) and (D.2) gives the rate d n d_n d n for f ~ j \widetilde f_j f j . Because d n → 0 d_n\to0 d n → 0 , f ( Q j , n ) ∈ [ f − , f + ] f(Q_{j,n})\in[f_-,f_+] f ( Q j , n ) ∈ [ f − , f + ] , ϖ n → 0 \varpi_n\to0 ϖ n → 0 , and ϖ n − 1 → ∞ \varpi_n^{-1}\to\infty ϖ n − 1 → ∞ , eventually
ϖ n < f − / 2 , ϖ n − 1 > 2 f + , \varpi_n<f_-/2,\qquad\varpi_n^{-1}>2f_+, ϖ n < f − /2 , ϖ n − 1 > 2 f + ,
and the event max j ∣ f ~ j − f ( Q j , n ) ∣ < f − / 2 \max_j|\widetilde f_j-f(Q_{j,n})|<f_-/2 max j ∣ f j − f ( Q j , n ) ∣ < f − /2 has probability tending to one. On that event,
f − 2 ≤ f ~ j ≤ f + + f − 2 ≤ 3 f + 2 < 2 f + < ϖ n − 1 , \frac{f_-}{2}\le\widetilde f_j\le f_++\frac{f_-}{2}\le\frac{3f_+}{2}<2f_+<\varpi_n^{-1}, 2 f − ≤ f j ≤ f + + 2 f − ≤ 2 3 f + < 2 f + < ϖ n − 1 ,
while ϖ n < f − / 2 \varpi_n<f_-/2 ϖ n < f − /2 . Hence ϖ n < f ~ j < ϖ n − 1 \varpi_n<\widetilde f_j<\varpi_n^{-1} ϖ n < f j < ϖ n − 1 for every j j j , so neither clipping boundary is active and f ^ j = f ~ j \widehat f_j=\widetilde f_j f j = f j . This proves (3.10).
Proof of Theorem 3.9. Conditional on the first two stages, write
G ‾ j ( 3 ) = F ( q j 0 ) + Y ‾ j , Y ‾ j = 1 n 3 ∑ i = 1 n 3 Y i , j . \overline{G}^{(3)}_j = F(q^0_j) + \overline{Y}_j,\qquad\overline{Y}_j = \frac{1}{n_3}\sum_{i=1}^{n_3}Y_{i,j}. G j ( 3 ) = F ( q j 0 ) + Y j , Y j = n 3 1 i = 1 ∑ n 3 Y i , j .
Substituting this identity into (2.11) and multiplying by f ^ j \widehat{f}_j f j gives the exact equality
f ^ j ( Q ~ j − Q j , n ) + Y ‾ j = f ^ j ( q j 0 − Q j , n ) − { F ( q j 0 ) − F ( Q j , n ) } . (64) \widehat{f}_j(\widetilde{Q}_j-Q_{j,n})+\overline{Y}_j=\widehat{f}_j(q^0_j-Q_{j,n})-\{F(q^0_j)-F(Q_{j,n})\}. \tag*{(64)} f j ( Q j − Q j , n ) + Y j = f j ( q j 0 − Q j , n ) − { F ( q j 0 ) − F ( Q j , n )} . (64)
Add and subtract f ( Q j , n ) ( q j 0 − Q j , n ) f(Q_{j,n})(q^0_j-Q_{j,n}) f ( Q j , n ) ( q j 0 − Q j , n ) on the right:
(D.3) = { f ^ j − f ( Q j , n ) } ( q j 0 − Q j , n ) − [ F ( q j 0 ) − F ( Q j , n ) − f ( Q j , n ) ( q j 0 − Q j , n ) ] . (65) \begin{aligned}
\text{(D.3)}={}&\{\widehat{f}_j-f(Q_{j,n})\}(q^0_j-Q_{j,n})\\
&-\left[F(q^0_j)-F(Q_{j,n})-f(Q_{j,n})(q^0_j-Q_{j,n})\right]. \tag*{(65)}
\end{aligned} (D.3) = { f j − f ( Q j , n )} ( q j 0 − Q j , n ) − [ F ( q j 0 ) − F ( Q j , n ) − f ( Q j , n ) ( q j 0 − Q j , n ) ] . (65)
The first term is uniformly O P ( d n r 1 n ) O_{\mathbb P}(d_nr_{1n}) O P ( d n r 1 n ) by Theorems 3.7 and 3.8. For the second, the integral argument used in (C.15) gives
∣ F ( q j 0 ) − F ( Q j , n ) − f ( Q j , n ) ( q j 0 − Q j , n ) ∣ ≤ L f 1 + β ∣ q j 0 − Q j , n ∣ 1 + β , \left|F(q^0_j)-F(Q_{j,n})-f(Q_{j,n})(q^0_j-Q_{j,n})\right|
\le\frac{L_f}{1+\beta}|q^0_j-Q_{j,n}|^{1+\beta}, F ( q j 0 ) − F ( Q j , n ) − f ( Q j , n ) ( q j 0 − Q j , n ) ≤ 1 + β L f ∣ q j 0 − Q j , n ∣ 1 + β ,
which is uniformly O P ( r 1 n 1 + β ) O_{\mathbb P}(r_{1n}^{1+\beta}) O P ( r 1 n 1 + β ) . Taking the maximum proves (3.11).
High-Dimensional Gaussian and Multiplier Approximation
Lemma E.1 (Conditional variance and standardized envelope). Suppose Assumptions 3.1 and 3.2 hold and
max j ≤ k n ∣ q j 0 − Q j , n ∣ = o P ( 1 ) . \max_{j\le k_n}|q^0_j-Q_{j,n}|=o_{\mathbb P}(1). j ≤ k n max ∣ q j 0 − Q j , n ∣ = o P ( 1 ) . Then there exists a deterministic sequence η n ↓ 0 \eta_n\downarrow0 η n ↓ 0 such that, with
E 0 , n = { max j ≤ k n ∣ q j 0 − Q j , n ∣ ≤ η n } , P ( E 0 , n ) ⟶ 1 , \mathcal{E}_{0,n}=\left\{\max_{j\le k_n}|q^0_j-Q_{j,n}|\le\eta_n\right\},\qquad\mathbb{P}(\mathcal{E}_{0,n})\longrightarrow1, E 0 , n = { j ≤ k n max ∣ q j 0 − Q j , n ∣ ≤ η n } , P ( E 0 , n ) ⟶ 1 , there are constants 0 < c < C < ∞ 0<c<C<\infty 0 < c < C < ∞ , depending only on ( τ − , τ + ) (\tau_-,\tau_+) ( τ − , τ + ) , for which the following bounds hold on E 0 , n \mathcal{E}_{0,n} E 0 , n for all sufficiently large n n n :
c H k n ( 1 + ν ε n ) ≤ min j ≤ k n σ j , n 2 ≤ max j ≤ k n σ j , n 2 ≤ C H k n 2 ( 1 + ν ε n ) . cH_{k_n}(1+\nu\varepsilon_n)\le\min_{j\le k_n}\sigma^2_{j,n}\le\max_{j\le k_n}\sigma^2_{j,n}\le CH_{k_n}^2(1+\nu\varepsilon_n). c H k n ( 1 + ν ε n ) ≤ j ≤ k n min σ j , n 2 ≤ j ≤ k n max σ j , n 2 ≤ C H k n 2 ( 1 + ν ε n ) . Consequently, on the same event,
K n ≤ C H k n . (66) K_n\le C\sqrt{H_{k_n}}. \tag*{(66)} K n ≤ C H k n . (66)
Proof. Choose η n < δ 0 \eta_n<\delta_0 η n < δ 0 eventually. On E 0 , n \mathcal{E}_{0,n} E 0 , n , the segment joining Q j , n Q_{j,n} Q j , n and q j 0 q^0_j q j 0 lies in N n \mathcal{N}_n N n , and hence
∣ p j 0 − τ j , n ∣ = ∣ F ( q j 0 ) − F ( Q j , n ) ∣ ≤ f + η n . |p_j^0-\tau_{j,n}|=|F(q_j^0)-F(Q_{j,n})|\le f_+ \eta_n. ∣ p j 0 − τ j , n ∣ = ∣ F ( q j 0 ) − F ( Q j , n ) ∣ ≤ f + η n .
Using the target-range part of Assumption 3.1, for all sufficiently large n n n ,
p j 0 = F ( q j 0 ) ∈ [ τ − / 2 , ( 1 + τ + ) / 2 ] p_j^0=F(q_j^0)\in[\tau_-/2,(1+\tau_+)/2] p j 0 = F ( q j 0 ) ∈ [ τ − /2 , ( 1 + τ + ) /2 ]
uniformly in j j j . Thus both p j 0 p_j^0 p j 0 and 1 − p j 0 1-p_j^0 1 − p j 0 are bounded below by a positive constant.
For a threshold rank r r r , define a = a r − ( p j 0 ) a=a_r^-(p_j^0) a = a r − ( p j 0 ) and b = a r + ( p j 0 ) b=a_r^+(p_j^0) b = a r + ( p j 0 ) . Since 1 ≤ w r ± ≤ H k n 1\le w_r^\pm\le H_{k_n} 1 ≤ w r ± ≤ H k n and 2 H k n − 1 ≥ H k n 2H_{k_n}-1\ge H_{k_n} 2 H k n − 1 ≥ H k n ,
a ≥ H k n ν ε n + c H k n , b ≥ H k n ν ε n + c H k n . a\ge H_{k_n}\nu\varepsilon_n+cH_{k_n},\qquad b\ge H_{k_n}\nu\varepsilon_n+cH_{k_n}. a ≥ H k n ν ε n + c H k n , b ≥ H k n ν ε n + c H k n .
The minimum over all fusion weights equals
p j 0 ( 1 − p j 0 ) + a b a + b ≥ c + 1 2 min ( a , b ) ≥ c H k n ( 1 + ν ε n ) . p_j^0(1-p_j^0)+\frac{ab}{a+b}\ge c+\frac{1}{2}\min(a,b)\ge cH_{k_n}(1+\nu\varepsilon_n). p j 0 ( 1 − p j 0 ) + a + b ab ≥ c + 2 1 min ( a , b ) ≥ c H k n ( 1 + ν ε n ) .
The variance at the actual anchor τ j \tau_j τ j is no smaller than this minimum, proving the lower bound.
For the upper bound, a a a and b b b are at most C H k n 2 ( 1 + ν ε n ) CH_{k_n}^2(1+\nu\varepsilon_n) C H k n 2 ( 1 + ν ε n ) , and (A.4) at any λ ∈ [ 0 , 1 ] \lambda\in[0,1] λ ∈ [ 0 , 1 ] is bounded by the same order. Alternatively, the score envelope gives a coarser bound of the same required form. Finally,
1 + ν ε = 1 + 4 e ε ( e ε − 1 ) 2 = ( e ε + 1 e ε − 1 ) 2 , 1+\nu_\varepsilon=1+\frac{4e^\varepsilon}{(e^\varepsilon-1)^2}=\left(\frac{e^\varepsilon+1}{e^\varepsilon-1}\right)^2, 1 + ν ε = 1 + ( e ε − 1 ) 2 4 e ε = ( e ε − 1 e ε + 1 ) 2 ,
so
B 1 n = 1 + 2 H k n e ε n e ε n − 1 ≤ 3 H k n 1 + ν ε n . B_{1n}=1+\frac{2H_{k_n}e^{\varepsilon_n}}{e^{\varepsilon_n}-1}\le3H_{k_n}\sqrt{1+\nu_{\varepsilon_n}}. B 1 n = 1 + e ε n − 1 2 H k n e ε n ≤ 3 H k n 1 + ν ε n .
Therefore
∣ Y i , j ∣ σ j , n ≤ 2 B 1 n { c H k n ( 1 + ν ε n ) } 1 / 2 ≤ C H k n , \frac{|Y_{i,j}|}{\sigma_{j,n}}\le\frac{2B_{1n}}{\{cH_{k_n}(1+\nu_{\varepsilon_n})\}^{1/2}}\le C\sqrt{H_{k_n}}, σ j , n ∣ Y i , j ∣ ≤ { c H k n ( 1 + ν ε n ) } 1/2 2 B 1 n ≤ C H k n ,
which proves (E.1).
Lemma E.2 (Uniform sample-scale consistency). Conditional on the first two stages,
max j ≤ k n ∣ σ ^ G , j 2 σ j , n 2 − 1 ∣ = O P [ K n ℓ n n 3 + K n 2 ℓ n n 3 ] . (67) \max_{j\le k_n}\left|\frac{\widehat{\sigma}_{G,j}^2}{\sigma_{j,n}^2}-1\right|
=O_{\mathbb{P}}\left[K_n\sqrt{\frac{\ell_n}{n_3}}+K_n^2\frac{\ell_n}{n_3}\right]. \tag*{(67)} j ≤ k n max σ j , n 2 σ G , j 2 − 1 = O P [ K n n 3 ℓ n + K n 2 n 3 ℓ n ] . (67) Under (3.6), the right-hand side is o P ( 1 ) o_{\mathbb{P}}(1) o P ( 1 ) .
Proof. Let X i , j = Y i , j / σ j , n X_{i,j}=Y_{i,j}/\sigma_{j,n} X i , j = Y i , j / σ j , n and X i = ( X i , 1 , … , X i , k n ) ⊤ X_i=(X_{i,1},\ldots,X_{i,k_n})^\top X i = ( X i , 1 , … , X i , k n ) ⊤ . Conditional on the first two stages, the vectors are i.i.d., E X i , j = 0 \mathbb{E}X_{i,j}=0 E X i , j = 0 , E X i , j 2 = 1 \mathbb{E}X_{i,j}^2=1 E X i , j 2 = 1 , and ∣ X i , j ∣ ≤ K n |X_{i,j}|\le K_n ∣ X i , j ∣ ≤ K n . In particular, E X i , j 4 ≤ K n 2 \mathbb{E}X_{i,j}^4\le K_n^2 E X i , j 4 ≤ K n 2 . Bernstein’s inequality and a union bound give
max j ∣ n 3 − 1 ∑ i X i , j 2 − 1 ∣ = O P { K n ℓ n / n 3 + K n 2 ℓ n / n 3 } . \max_j\left|n_3^{-1}\sum_i X_{i,j}^2-1\right|
=O_{\mathbb{P}}\left\{K_n\sqrt{\ell_n/n_3}+K_n^2\ell_n/n_3\right\}. j max n 3 − 1 i ∑ X i , j 2 − 1 = O P { K n ℓ n / n 3 + K n 2 ℓ n / n 3 } .
The squared sample means satisfy
max j ∣ n 3 − 1 ∑ i X i , j ∣ 2 = O P ( K n 2 ℓ n / n 3 ) , \max_j \left|n_3^{-1}\sum_i X_{i,j}\right|^2 = O_{\mathbb{P}}(K_n^2\ell_n/n_3), j max n 3 − 1 i ∑ X i , j 2 = O P ( K n 2 ℓ n / n 3 ) ,
again by Bernstein. Since
σ ^ G , j 2 σ j , n 2 = n 3 − 1 ∑ i X i , j 2 − ( n 3 − 1 ∑ i X i , j ) 2 , \frac{\widehat{\sigma}_{G,j}^2}{\sigma_{j,n}^2}=n_3^{-1}\sum_i X_{i,j}^2-\left(n_3^{-1}\sum_i X_{i,j}\right)^2, σ j , n 2 σ G , j 2 = n 3 − 1 i ∑ X i , j 2 − ( n 3 − 1 i ∑ X i , j ) 2 ,
the result follows.
Lemma E.3 (Conditional Gaussian and empirical multiplier approximation). Let
S n † = max j ∈ I n ∣ n 3 − 1 / 2 ∑ i = 1 n 3 Y i , j σ ^ G , j ∣ , Δ σ , n = K n ℓ n n 3 + K n 2 ℓ n n 3 , S_n^\dagger=\max_{j\in\mathcal{I}_n}\left|\frac{n_3^{-1/2}\sum_{i=1}^{n_3}Y_{i,j}}{\widehat{\sigma}_{G,j}}\right|,\qquad\Delta_{\sigma,n}=K_n\sqrt{\frac{\ell_n}{n_3}}+K_n^2\frac{\ell_n}{n_3}, S n † = j ∈ I n max σ G , j n 3 − 1/2 ∑ i = 1 n 3 Y i , j , Δ σ , n = K n n 3 ℓ n + K n 2 n 3 ℓ n , and let S n ∗ S_n^* S n ∗ be the empirical Gaussian multiplier analogue centered by the sample means and divided by the sample standard deviations. Under (3.6), conditional on the first two stages,
sup z ∣ P ( S n † ≤ z ∣ F n 1 + n 2 ) − P ( S n ∗ ≤ z ∣ G 1 ( 3 ) , … , G n 3 ( 3 ) ) ∣ = O P { ( K n 2 ℓ n 7 n 3 ) 1 / 6 + ℓ n Δ σ , n } = o P ( 1 ) . (68) \sup_z\left|\mathbb{P}(S_n^\dagger\le z\mid\mathcal{F}_{n_1+n_2})-\mathbb{P}(S_n^*\le z\mid G_1^{(3)},\ldots,G_{n_3}^{(3)})\right|
=O_{\mathbb{P}}\left\{\left(\frac{K_n^2\ell_n^7}{n_3}\right)^{1/6}+\ell_n\Delta_{\sigma,n}\right\}=o_{\mathbb{P}}(1). \tag*{(68)} z sup P ( S n † ≤ z ∣ F n 1 + n 2 ) − P ( S n ∗ ≤ z ∣ G 1 ( 3 ) , … , G n 3 ( 3 ) ) = O P { ( n 3 K n 2 ℓ n 7 ) 1/6 + ℓ n Δ σ , n } = o P ( 1 ) . (68)
Proof. Work conditionally on F n 1 + n 2 \mathcal{F}_{n_1+n_2} F n 1 + n 2 . Put
X i , j = Y i , j σ j , n , p n = max { 2 k n , 3 } . X_{i,j}=\frac{Y_{i,j}}{\sigma_{j,n}},\qquad p_n=\max\{2k_n,3\}. X i , j = σ j , n Y i , j , p n = max { 2 k n , 3 } .
Define the population-standardized target and multiplier maxima
S n 0 = max j ≤ k n ∣ n 3 − 1 / 2 ∑ i = 1 n 3 X i , j ∣ , S_n^0=\max_{j\le k_n}\left|n_3^{-1/2}\sum_{i=1}^{n_3}X_{i,j}\right|, S n 0 = j ≤ k n max n 3 − 1/2 i = 1 ∑ n 3 X i , j ,
S n ∗ , 0 = max j ≤ k n ∣ n 3 − 1 / 2 ∑ i = 1 n 3 ξ i ( X i , j − n 3 − 1 ∑ ℓ = 1 n 3 X ℓ , j ) ∣ . S_n^{*,0}=\max_{j\le k_n}\left|n_3^{-1/2}\sum_{i=1}^{n_3}\xi_i\left(X_{i,j}-n_3^{-1}\sum_{\ell=1}^{n_3}X_{\ell,j}\right)\right|. S n ∗ , 0 = j ≤ k n max n 3 − 1/2 i = 1 ∑ n 3 ξ i ( X i , j − n 3 − 1 ℓ = 1 ∑ n 3 X ℓ , j ) .
Let Z n Z_n Z n be the maximum of the absolute coordinates of the centered Gaussian vector with the covariance matrix of n 3 − 1 / 2 ∑ i X i n_3^{-1/2}\sum_i X_i n 3 − 1/2 ∑ i X i , and let F n G F_n^G F n G be its conditional CDF.
Embed the absolute maximum into ( X i ⊤ , − X i ⊤ ) ⊤ (X_i^\top,-X_i^\top)^\top ( X i ⊤ , − X i ⊤ ) ⊤ and, if 2 k n < 3 2k_n<3 2 k n < 3 , append a duplicate coordinate. Every coordinate is centered, has variance one, and is bounded by K n K_n K n . Furthermore,
log ( p n n 3 ) ≤ C ℓ n , \log(p_n n_3)\le C\ell_n, log ( p n n 3 ) ≤ C ℓ n ,
and, when k n ≥ 2 k_n \ge2 k n ≥ 2 , log ( p n n 3 ) ≤ ℓ n \log(p_n n_3) \le\ell_n log ( p n n 3 ) ≤ ℓ n . For m = 1 , 2 m = 1, 2 m = 1 , 2 ,
E ( ∣ X i , j ∣ 2 + m ∣ F n 1 + n 2 ) ≤ K n m E ( X i , j 2 ∣ F n 1 + n 2 ) = K n m . \mathbb{E}(|X_{i,j}|^{2+m} \mid\mathcal{F}_{n_1+n_2}) \le K_n^m \mathbb{E}(X_{i,j}^2 \mid\mathcal{F}_{n_1+n_2}) = K_n^m. E ( ∣ X i , j ∣ 2 + m ∣ F n 1 + n 2 ) ≤ K n m E ( X i , j 2 ∣ F n 1 + n 2 ) = K n m .
Also, after replacing K n K_n K n by a universal multiple,
E { exp ( ∣ X i , j ∣ / ( C K n ) ) ∣ F n 1 + n 2 } ≤ 2. \mathbb{E}\{\exp(|X_{i,j}|/(C K_n)) \mid\mathcal{F}_{n_1+n_2}\} \le2. E { exp ( ∣ X i , j ∣/ ( C K n )) ∣ F n 1 + n 2 } ≤ 2.
Hence Proposition 2.1 of Chernozhukov et al. [10 ] gives
sup z ∣ P ( S n 0 ≤ z ∣ F n 1 + n 2 ) − F n G ( z ) ∣ ≤ C ( K n 2 ℓ n 7 n 3 ) 1 / 6 . (69) \sup_z \left|\mathbb{P}(S_n^0 \le z \mid\mathcal{F}_{n_1+n_2}) - F_n^G(z)\right| \le C \left(\frac{K_n^2 \ell_n^7}{n_3}\right)^{1/6}. \tag*{(69)} z sup P ( S n 0 ≤ z ∣ F n 1 + n 2 ) − F n G ( z ) ≤ C ( n 3 K n 2 ℓ n 7 ) 1/6 . (69)
Put m = n 3 m = n_3 m = n 3 and ρ n = K n 2 ℓ n 7 / m \rho_n = K_n^2\ell_n^7/m ρ n = K n 2 ℓ n 7 / m . For the multiplier comparison, apply Corollary 4.2 of Chernozhukov et al. [10 ] with η = ( m + 1 ) − 2 \eta= (m+1)^{-2} η = ( m + 1 ) − 2 . Conditional on the first two stages, with probability at least 1 − ( m + 1 ) − 2 1 - (m+1)^{-2} 1 − ( m + 1 ) − 2 over the Stage-3 sample,
sup z ∣ P ( S n ∗ , 0 ≤ z ∣ X 1 , … , X m ) − F n G ( z ) ∣ ≤ C ρ n 1 / 6 , (70) \sup_z \left|\mathbb{P}(S_n^{*,0} \le z \mid X_1,\ldots,X_m) - F_n^G(z)\right| \le C\rho_n^{1/6}, \tag*{(70)} z sup P ( S n ∗ , 0 ≤ z ∣ X 1 , … , X m ) − F n G ( z ) ≤ C ρ n 1/6 , (70)
because log 5 ( p n m ) log 2 { ( m + 1 ) 2 } ≤ C ℓ n 7 \log^5(p_n m)\log^2\{(m+1)^2\} \le C\ell_n^7 log 5 ( p n m ) log 2 {( m + 1 ) 2 } ≤ C ℓ n 7 .
It remains to replace the population scales by sample scales. Write
δ σ , n = max j ∣ σ ^ G , j 2 σ j , n 2 − 1 ∣ , X ‾ j = m − 1 ∑ i = 1 m X i , j . \delta_{\sigma,n} = \max_j \left|\frac{\widehat{\sigma}_{G,j}^2}{\sigma_{j,n}^2} - 1\right|,\qquad\overline{X}_j = m^{-1}\sum_{i=1}^m X_{i,j}. δ σ , n = j max σ j , n 2 σ G , j 2 − 1 , X j = m − 1 i = 1 ∑ m X i , j .
For each coordinate, ∣ X i , j ∣ ≤ K n |X_{i,j}| \le K_n ∣ X i , j ∣ ≤ K n , E ( X i , j 2 ∣ F n 1 + n 2 ) = 1 \mathbb{E}(X_{i,j}^2 \mid\mathcal{F}_{n_1+n_2}) = 1 E ( X i , j 2 ∣ F n 1 + n 2 ) = 1 , and E ( X i , j 4 ∣ F n 1 + n 2 ) ≤ K n 2 \mathbb{E}(X_{i,j}^4 \mid\mathcal{F}_{n_1+n_2}) \le K_n^2 E ( X i , j 4 ∣ F n 1 + n 2 ) ≤ K n 2 . Conditional Bernstein inequalities and a union bound therefore give
P [ max j ∣ m − 1 ∑ i = 1 m ( X i , j 2 − 1 ) ∣ > C Δ σ , n | F n 1 + n 2 ] ≤ C e − c ℓ n , (71) \mathbb{P}\left[\max_j\left|m^{-1}\sum_{i=1}^m(X_{i,j}^2-1)\right| > C\Delta_{\sigma,n}\,\middle|\,\mathcal{F}_{n_1+n_2}\right] \le C e^{-c\ell_n}, \tag*{(71)} P [ j max m − 1 i = 1 ∑ m ( X i , j 2 − 1 ) > C Δ σ , n F n 1 + n 2 ] ≤ C e − c ℓ n , (71)
P [ max j ∣ X ‾ j ∣ > C { ℓ n m + K n ℓ n m } | F n 1 + n 2 ] ≤ C e − c ℓ n . (72) \mathbb{P}\left[\max_j|\overline{X}_j| > C\left\{\sqrt{\frac{\ell_n}{m}}+K_n\frac{\ell_n}{m}\right\}\,\middle|\,\mathcal{F}_{n_1+n_2}\right] \le C e^{-c\ell_n}. \tag*{(72)} P [ j max ∣ X j ∣ > C { m ℓ n + K n m ℓ n } F n 1 + n 2 ] ≤ C e − c ℓ n . (72)
The constants in the thresholds can be enlarged so that c c c is arbitrarily large. On first-two-stage histories with ρ n \rho_n ρ n smaller than a fixed constant, the square of the threshold in (E.7) is bounded by C Δ σ , n C\Delta_{\sigma,n} C Δ σ , n . Since
σ ^ G , j 2 σ j , n 2 = m − 1 ∑ i = 1 m X i , j 2 − X ‾ j 2 , \frac{\widehat{\sigma}_{G,j}^2}{\sigma_{j,n}^2} = m^{-1}\sum_{i=1}^m X_{i,j}^2 - \overline{X}_j^2, σ j , n 2 σ G , j 2 = m − 1 i = 1 ∑ m X i , j 2 − X j 2 ,
(E.6)–(E.7) imply
P ( δ σ , n > C Δ σ , n ∣ F n 1 + n 2 ) ≤ C e − c ℓ n . (73) \mathbb{P}(\delta_{\sigma,n} > C\Delta_{\sigma,n} \mid\mathcal{F}_{n_1+n_2}) \le C e^{-c\ell_n}. \tag*{(73)} P ( δ σ , n > C Δ σ , n ∣ F n 1 + n 2 ) ≤ C e − c ℓ n . (73)
Moreover, ρ n = o P ( 1 ) \rho_n = o_{\mathbb{P}}(1) ρ n = o P ( 1 ) by (21) , and on these histories
Δ σ , n = ρ n 1 / 2 ℓ n − 3 + ρ n ℓ n − 6 = o ( 1 ) . \Delta_{\sigma,n} = \rho_n^{1/2}\ell_n^{-3} + \rho_n\ell_n^{-6} = o(1). Δ σ , n = ρ n 1/2 ℓ n − 3 + ρ n ℓ n − 6 = o ( 1 ) .
Thus (E.8) also ensures δ σ , n ≤ 1 / 2 \delta_{\sigma,n} \le1/2 δ σ , n ≤ 1/2 with the stated probability. On { δ σ , n ≤ 1 / 2 } \{\delta_{\sigma,n} \le1/2\} { δ σ , n ≤ 1/2 } all sample scales are positive and
∣ S n † − S n 0 ∣ ≤ C δ σ , n S n 0 , \left|S_n^{\dagger} - S_n^0\right| \le C\delta_{\sigma,n}S_n^0, S n † − S n 0 ≤ C δ σ , n S n 0 ,
∣ S n ∗ − S n ∗ , 0 ∣ ≤ C δ σ , n S n ∗ , 0 . \left|S_n^{*} - S_n^{*,0}\right| \le C\delta_{\sigma,n}S_n^{*,0}. S n ∗ − S n ∗ , 0 ≤ C δ σ , n S n ∗ , 0 .
Another conditional Bernstein inequality and union bound give
P ( S n 0 > C ℓ n ∣ F n 1 + n 2 ) ≤ C e − c ℓ n . \mathbb{P}\left(S_n^0 > C\sqrt{\ell_n}\mid\mathcal{F}_{n_1+n_2}\right) \le Ce^{-c\ell_n}. P ( S n 0 > C ℓ n ∣ F n 1 + n 2 ) ≤ C e − c ℓ n .
On the sample-scale event, every coordinate of the conditional Gaussian vector defining S n ∗ , 0 S_n^{*,0} S n ∗ , 0 has variance at most 3 / 2 3/2 3/2 , so a Gaussian union bound gives
P ( S n ∗ , 0 > C ℓ n ∣ X 1 , … , X m ) ≤ C e − c ℓ n . \mathbb{P}\left(S_n^{*,0} > C\sqrt{\ell_n}\mid X_1,\ldots,X_m\right) \le Ce^{-c\ell_n}. P ( S n ∗ , 0 > C ℓ n ∣ X 1 , … , X m ) ≤ C e − c ℓ n .
Consequently, with t n = C Δ σ , n ℓ n t_n = C\Delta_{\sigma,n}\sqrt{\ell_n} t n = C Δ σ , n ℓ n , the two studentization perturbations exceed t n t_n t n only on the explicit exceptional events above. Nazarov’s inequality for the signed Gaussian vector gives
sup z { F n G ( z + t n ) − F n G ( z − t n ) } ≤ C ℓ n Δ σ , n . \sup_z\left\{F_n^G(z+t_n)-F_n^G(z-t_n)\right\} \le C\ell_n\Delta_{\sigma,n}. z sup { F n G ( z + t n ) − F n G ( z − t n ) } ≤ C ℓ n Δ σ , n .
The exponentially small terms can be absorbed into C ρ n 1 / 6 C\rho_n^{1/6} C ρ n 1/6 . K n ≥ 1 K_n \ge1 K n ≥ 1 , m ≤ n m \le n m ≤ n , and the exponent c c c can be chosen sufficiently large. Combining the perturbation sandwiches separately with (E.4) and (E.5) gives
sup z ∣ P ( S n † ≤ z ∣ F n 1 + n 2 ) − F n G ( z ) ∣ = O P { ( K n 2 ℓ n 7 n 3 ) 1 / 6 + ℓ n Δ σ , n } . (74) \sup_z\left|\mathbb{P}\left(S_n^{\dagger}\le z\mid\mathcal{F}_{n_1+n_2}\right)-F_n^G(z)\right|
=O_{\mathbb{P}}\left\{\left(\frac{K_n^2\ell_n^7}{n_3}\right)^{1/6}+\ell_n\Delta_{\sigma,n}\right\}. \tag*{(74)} z sup P ( S n † ≤ z ∣ F n 1 + n 2 ) − F n G ( z ) = O P { ( n 3 K n 2 ℓ n 7 ) 1/6 + ℓ n Δ σ , n } . (74)
sup z ∣ P ( S n ∗ ≤ z ∣ G 1 ( 3 ) , … , G n 3 ( 3 ) ) − F n G ( z ) ∣ = O P { ( K n 2 ℓ n 7 n 3 ) 1 / 6 + ℓ n Δ σ , n } . (75) \sup_z\left|\mathbb{P}\left(S_n^{*}\le z\mid G_1^{(3)},\ldots,G_{n_3}^{(3)}\right)-F_n^G(z)\right|
=O_{\mathbb{P}}\left\{\left(\frac{K_n^2\ell_n^7}{n_3}\right)^{1/6}+\ell_n\Delta_{\sigma,n}\right\}. \tag*{(75)} z sup P ( S n ∗ ≤ z ∣ G 1 ( 3 ) , … , G n 3 ( 3 ) ) − F n G ( z ) = O P { ( n 3 K n 2 ℓ n 7 ) 1/6 + ℓ n Δ σ , n } . (75)
on a set of first-two-stage histories whose probability tends to one; the second display also holds outside a Stage-3 event of conditional probability at most C e − c ℓ n + ( m + 1 ) − 2 Ce^{-c\ell_n}+(m+1)^{-2} C e − c ℓ n + ( m + 1 ) − 2 . The triangle inequality then proves (E.3).
Finally,
ℓ n Δ σ , n = ( K n 2 ℓ n 7 n 3 ) 1 / 2 ℓ n − 2 + K n 2 ℓ n 7 n 3 ℓ n − 5 = o P ( 1 ) , \ell_n\Delta_{\sigma,n}
=\left(\frac{K_n^2\ell_n^7}{n_3}\right)^{1/2}\ell_n^{-2}
+\frac{K_n^2\ell_n^7}{n_3}\ell_n^{-5}
=o_{\mathbb{P}}(1), ℓ n Δ σ , n = ( n 3 K n 2 ℓ n 7 ) 1/2 ℓ n − 2 + n 3 K n 2 ℓ n 7 ℓ n − 5 = o P ( 1 ) ,
which completes the proof.
Lemma E.4 (Transfer of the one-step remainder). Suppose (3.11), (E.2), Δ σ , n = o P ( 1 ) \Delta_{\sigma,n}=o_{\mathrm{P}}(1) Δ σ , n = o P ( 1 ) , and (3.7) hold. Then
∣ T n − S n † ∣ = O P ( n 3 R n σ n ) = o P ( ℓ n − 1 / 2 ) . (76) \left|T_n-S_n^\dagger\right|=O_{\mathrm{P}}\left(\frac{\sqrt{n_3}R_n}{\sigma_n}\right)=o_{\mathrm{P}}\left(\ell_n^{-1/2}\right). \tag*{(76)} T n − S n † = O P ( σ n n 3 R n ) = o P ( ℓ n − 1/2 ) . (76) Proof. By Theorem 3.9, uniformly in j j j ,
∣ n 3 f ^ j ( Q ~ j − Q j , n ) + n 3 − 1 / 2 ∑ i Y i , j ∣ = O P ( n 3 R n ) . \left|\sqrt{n_3}\widehat{f}_j(\widetilde{Q}_j-Q_{j,n})+n_3^{-1/2}\sum_i Y_{i,j}\right|=O_{\mathrm{P}}(\sqrt{n_3}R_n). n 3 f j ( Q j − Q j , n ) + n 3 − 1/2 i ∑ Y i , j = O P ( n 3 R n ) . On the event
max j ∣ σ ^ G , j 2 σ j , n 2 − 1 ∣ ≤ 1 2 , \max_j\left|\frac{\widehat{\sigma}_{G,j}^2}{\sigma_{j,n}^2}-1\right|\leq\frac{1}{2}, j max σ j , n 2 σ G , j 2 − 1 ≤ 2 1 , which has probability tending to one by Lemma E.2, J ^ n = { 1 , … , k n } \widehat{\mathcal{J}}_n=\{1,\ldots,k_n\} J n = { 1 , … , k n } and min j σ ^ G , j ≥ σ n / 2 \min_j\widehat{\sigma}_{G,j}\geq\sigma_n/\sqrt{2} min j σ G , j ≥ σ n / 2 . Divide by the sample scales, maximize, and use the reverse triangle inequality for maxima. Condition (3.7) then proves (E.11).
Proof of Theorem 3.10. Condition on F n 1 + n 2 \mathcal{F}_{n_1+n_2} F n 1 + n 2 . Let Z n Z_n Z n be the maximum of the absolute coordinates Z n , j Z_{n,j} Z n , j of the centered Gaussian vector used in Lemma E.3, let F n G F_n^G F n G be its conditional CDF, and put
q n G ( u ) = inf { z : F n G ( z ) ≥ u } . q_n^G(u)=\inf\{z:F_n^G(z)\geq u\}. q n G ( u ) = inf { z : F n G ( z ) ≥ u } .
The two comparisons in (E.9) and (E.10), together with P ( J ^ n = { 1 , … , k n } ) → 1 \mathbb{P}(\widehat{\mathcal{J}}_n=\{1,\ldots,k_n\})\to1 P ( J n = { 1 , … , k n }) → 1 , imply that there are a deterministic sequence δ G , n ↓ 0 \delta_{G,n}\downarrow0 δ G , n ↓ 0 and events A n \mathcal{A}_n A n with P ( A n c ) = o ( 1 ) \mathbb{P}(\mathcal{A}_n^c)=o(1) P ( A n c ) = o ( 1 ) such that, on A n \mathcal{A}_n A n ,
sup z ∣ P ( S n † ≤ z ∣ F n 1 + n 2 ) − F n G ( z ) ∣ ≤ δ G , n , (77) \sup_z\left|\mathbb{P}(S_n^\dagger\leq z\mid\mathcal{F}_{n_1+n_2})-F_n^G(z)\right|\leq\delta_{G,n}, \tag*{(77)} z sup P ( S n † ≤ z ∣ F n 1 + n 2 ) − F n G ( z ) ≤ δ G , n , (77)
sup z ∣ P ( S n ∗ ≤ z ∣ G 1 ( 3 ) , … , G n 3 ( 3 ) ) − F n G ( z ) ∣ ≤ δ G , n , (78) \sup_z\left|\mathbb{P}(S_n^*\leq z\mid G_1^{(3)},\ldots,G_{n_3}^{(3)})-F_n^G(z)\right|\leq\delta_{G,n}, \tag*{(78)} z sup P ( S n ∗ ≤ z ∣ G 1 ( 3 ) , … , G n 3 ( 3 ) ) − F n G ( z ) ≤ δ G , n , (78)
and all sample variances are positive. This event formulation follows directly from the two O P O_{\mathrm{P}} O P bounds because their common rate tends to zero.
Every coordinate of the Gaussian vector has variance one. Consequently, for every z z z ,
P ( Z n = z ∣ F n 1 + n 2 ) ≤ ∑ j = 1 k n P ( ∣ Z n , j ∣ = z ∣ F n 1 + n 2 ) = 0. \mathbb{P}(Z_n=z\mid\mathcal{F}_{n_1+n_2})\leq\sum_{j=1}^{k_n}\mathbb{P}(|Z_{n,j}|=z\mid\mathcal{F}_{n_1+n_2})=0. P ( Z n = z ∣ F n 1 + n 2 ) ≤ j = 1 ∑ k n P ( ∣ Z n , j ∣ = z ∣ F n 1 + n 2 ) = 0.
Thus F n G F_n^G F n G is continuous even if its correlation matrix is singular, and F n G { q n G ( u ) } = u F_n^G\{q_n^G(u)\}=u F n G { q n G ( u )} = u for u ∈ ( 0 , 1 ) u\in(0,1) u ∈ ( 0 , 1 ) . Write u = 1 − α u=1-\alpha u = 1 − α and c u ∗ = c 1 − α ∗ c_u^*=c_{1-\alpha}^* c u ∗ = c 1 − α ∗ . The second inequality in (E.13) and the definition of a generalized quantile give, on A n \mathcal{A}_n A n ,
q n G ( u − δ G , n ) ≤ c u ∗ ≤ q n G ( u + δ G , n ) . (79) q_n^G(u-\delta_{G,n})\leq c_u^*\leq q_n^G(u+\delta_{G,n}). \tag*{(79)} q n G ( u − δ G , n ) ≤ c u ∗ ≤ q n G ( u + δ G , n ) . (79)
Indeed, at a point below the left endpoint the conditional multiplier CDF is strictly below $u, whereas at the right endpoint it is at least u u u . The sandwich (E.14) implies the pathwise inclusions
A n ∩ { S n † ≤ q n G ( u − δ G , n ) } ⊆ { S n † ≤ c u ∗ } ⊆ A n c ∪ { S n † ≤ q n G ( u + δ G , n ) } . \mathcal{A}_n \cap\{S_n^{\dagger} \le q_n^G(u-\delta_{G,n})\} \subseteq\{S_n^{\dagger} \le c_u^*\} \subseteq\mathcal{A}_n^c \cup\{S_n^{\dagger} \le q_n^G(u+\delta_{G,n})\}. A n ∩ { S n † ≤ q n G ( u − δ G , n )} ⊆ { S n † ≤ c u ∗ } ⊆ A n c ∪ { S n † ≤ q n G ( u + δ G , n )} .
Using (E.12) at the two deterministic, F n 1 + n 2 \mathcal{F}_{n_1+n_2} F n 1 + n 2 -measurable Gaussian quantiles and then removing A n \mathcal{A}_n A n yields, uniformly for u ∈ [ α 0 , 1 − α 0 ] u \in[\alpha_0,1-\alpha_0] u ∈ [ α 0 , 1 − α 0 ] ,
∣ P ( S n † ≤ c u ∗ ) − u ∣ ≤ 2 δ G , n + P ( A n c ) = o ( 1 ) . \left|\mathbb{P}(S_n^{\dagger} \le c_u^*)-u\right| \le2\delta_{G,n}+\mathbb{P}(\mathcal{A}_n^c)=o(1). P ( S n † ≤ c u ∗ ) − u ≤ 2 δ G , n + P ( A n c ) = o ( 1 ) .
By Lemma E.4, choose a deterministic a n = o ( ℓ n − 1 / 2 ) a_n=o(\ell_n^{-1/2}) a n = o ( ℓ n − 1/2 ) such that, for D n = { ∣ T n − S n † ∣ ≤ a n } \mathcal{D}_n=\{|T_n-S_n^{\dagger}|\le a_n\} D n = { ∣ T n − S n † ∣ ≤ a n } , P ( D n c ) = o ( 1 ) \mathbb{P}(\mathcal{D}_n^c)=o(1) P ( D n c ) = o ( 1 ) . On A n ∩ D n \mathcal{A}_n\cap\mathcal{D}_n A n ∩ D n ,
{ S n † ≤ q n G ( u − δ G , n ) − a n } ⊆ { T n ≤ c u ∗ } , \{S_n^{\dagger}\le q_n^G(u-\delta_{G,n})-a_n\}\subseteq\{T_n\le c_u^*\}, { S n † ≤ q n G ( u − δ G , n ) − a n } ⊆ { T n ≤ c u ∗ } ,
{ T n ≤ c u ∗ } ⊆ { S n † ≤ q n G ( u + δ G , n ) + a n } . \{T_n\le c_u^*\}\subseteq\{S_n^{\dagger}\le q_n^G(u+\delta_{G,n})+a_n\}. { T n ≤ c u ∗ } ⊆ { S n † ≤ q n G ( u + δ G , n ) + a n } .
Nazarov’s inequality, applied to the 2 k n 2k_n 2 k n -dimensional signed Gaussian vector, gives
sup z { F n G ( z + a n ) − F n G ( z − a n ) } ≤ C a n ℓ n = o ( 1 ) . \sup_z\{F_n^G(z+a_n)-F_n^G(z-a_n)\}\le Ca_n\sqrt{\ell_n}=o(1). z sup { F n G ( z + a n ) − F n G ( z − a n )} ≤ C a n ℓ n = o ( 1 ) .
Combining this bound with (E.12) proves (27) . On the event that all sample variances are positive, T n ≤ c 1 − α ∗ T_n\le c_{1-\alpha}^* T n ≤ c 1 − α ∗ is algebraically equivalent to simultaneous inclusion in the untruncated intervals I n , j ∗ I_{n,j}^* I n , j ∗ . Intersecting with [ L , U ] [L,U] [ L , U ] preserves inclusion because Q j , n ∈ [ L , U ] Q_{j,n}\in[L,U] Q j , n ∈ [ L , U ] . The zero-variance fallback is [ L , U ] [L,U] [ L , U ] and its probability tends to zero, which proves (28) .
For the Monte Carlo version, let F ^ n ∗ \widehat{F}_n^* F n ∗ be the exact conditional multiplier CDF and F ^ n , M ∗ \widehat{F}_{n,M}^* F n , M ∗ its empirical CDF based on M n M_n M n independent draws. Also write
q n ∗ ( v ) = inf { z : F n ∗ ( z ) ≥ v } . q_n^*(v)=\inf\{z:F_n^*(z)\ge v\}. q n ∗ ( v ) = inf { z : F n ∗ ( z ) ≥ v } .
Conditionally on the data, the Dvoretzky–Kiefer–Wolfowitz (DKW) inequality [23 ] gives
P { sup z ∣ F ^ n , M ( z ) − F n ∗ ( z ) ∣ > η | G 1 ( 3 ) , … , G n 3 ( 3 ) } ≤ 2 e − 2 M n η 2 . (80) \mathbb{P}\left\{\sup_z|\widehat{F}_{n,M}(z)-F_n^*(z)|>\eta\ \middle|\ G_1^{(3)},\ldots,G_{n_3}^{(3)}\right\}\le2e^{-2M_n\eta^2}. \tag*{(80)} P { z sup ∣ F n , M ( z ) − F n ∗ ( z ) ∣ > η G 1 ( 3 ) , … , G n 3 ( 3 ) } ≤ 2 e − 2 M n η 2 . (80)
For u ∈ [ α 0 , 1 − α 0 ] u\in[\alpha_0,1-\alpha_0] u ∈ [ α 0 , 1 − α 0 ] and all sufficiently large M n M_n M n , the cap in r M n , α r_{M_n,\alpha} r M n , α is inactive. At c ^ u ∗ = T n ∗ ( r M n , α ) \widehat{c}_u^*=T_n^*(r_{M_n,\alpha}) c u ∗ = T n ∗ ( r M n , α ) ,
F ^ n , M ( c ^ u ∗ ) ≥ u , F ^ n , M ( c ^ u ∗ − ) < u + M n − 1 . \widehat{F}_{n,M}(\widehat{c}_u^*)\ge u,\qquad\widehat{F}_{n,M}(\widehat{c}_u^*-)<u+M_n^{-1}. F n , M ( c u ∗ ) ≥ u , F n , M ( c u ∗ − ) < u + M n − 1 .
On the DKW event in (E.15), these two inequalities imply
q n ∗ ( u − η ) ≤ c ^ u ∗ ≤ q n ∗ ( u + η + M n − 1 ) . (81) q_n^*(u-\eta)\le\widehat{c}_u^*\le q_n^*(u+\eta+M_n^{-1}). \tag*{(81)} q n ∗ ( u − η ) ≤ c u ∗ ≤ q n ∗ ( u + η + M n − 1 ) . (81)
For the lower bound, a value below q n ∗ ( u − η ) q_n^*(u-\eta) q n ∗ ( u − η ) would have empirical CDF strictly below u u u ; for the upper bound, a value above q n ∗ ( u + η + M n − 1 ) q_n^*(u+\eta+M_n^{-1}) q n ∗ ( u + η + M n − 1 ) would make the empirical left limit at the latter quantile at least u + M n − 1 u+M_n^{-1} u + M n − 1 , contradicting the preceding display. Take η = M n − 1 / 4 \eta=M_n^{-1/4} η = M n − 1/4 in (E.15). Then the DKW failure probability tends to zero, both shifted levels remain in a fixed compact subset of ( 0 , 1 ) (0,1) ( 0 , 1 ) , and (E.16) together with the exact-quantile result proves the two finite-M n M_n M n assertions uniformly in α \alpha α .
Now fix M M M and α \alpha α , and abbreviate r = r M , α r=r_{M,\alpha} r = r M , α . On the event of positive sample variances, F n ∗ F_n^* F n ∗ is continuous because every studentized multiplier coordinate is a nondegenerate Gaussian variable. The preceding Gaussian comparisons and the remainder transfer imply
sup z ∣ P ( T n ≤ z ∣ F n 1 + n 2 ) − F n G ( z ) ∣ = o P ( 1 ) , sup z ∣ F n ∗ ( z ) − F n G ( z ) ∣ = o P ( 1 ) . \sup_z \left|\mathbb{P}(T_n\le z\mid\mathcal{F}_{n_1+n_2})-F_n^G(z)\right|=o_{\mathbb{P}}(1),\qquad\sup_z\left|F_n^*(z)-F_n^G(z)\right|=o_{\mathbb{P}}(1). z sup P ( T n ≤ z ∣ F n 1 + n 2 ) − F n G ( z ) = o P ( 1 ) , z sup F n ∗ ( z ) − F n G ( z ) = o P ( 1 ) .
Since F n G F_n^G F n G is continuous, the conditional probability-integral transform gives
U n : = F n ∗ ( T n ) ⇝ U , U ∼ Uniform ( 0 , 1 ) . U_n:=F_n^*(T_n)\rightsquigarrow U,\qquad U\sim\operatorname{Uniform}(0,1). U n := F n ∗ ( T n ) ⇝ U , U ∼ Uniform ( 0 , 1 ) .
Conditional on the data, T n ≤ T ( r ) ∗ T_n\le T_{(r)}^* T n ≤ T ( r ) ∗ exactly when at most r − 1 r-1 r − 1 of the M M M multiplier maxima are below T n T_n T n . Therefore
P ( T n ≤ T ( r ) ∗ ∣ G 1 ( 3 ) , … , G n 3 ( 3 ) ) = g M , r ( U n ) , \mathbb{P}(T_n\le T_{(r)}^*\mid G_1^{(3)},\ldots,G_{n_3}^{(3)})=g_{M,r}(U_n), P ( T n ≤ T ( r ) ∗ ∣ G 1 ( 3 ) , … , G n 3 ( 3 ) ) = g M , r ( U n ) ,
where
g M , r ( u ) = ∑ s = 0 r − 1 ( M s ) u s ( 1 − u ) M − s . g_{M,r}(u)=\sum_{s=0}^{r-1}\binom{M}{s}u^s(1-u)^{M-s}. g M , r ( u ) = s = 0 ∑ r − 1 ( s M ) u s ( 1 − u ) M − s .
This is a bounded continuous polynomial, and the beta integral gives
∫ 0 1 g M , r ( u ) d u = ∑ s = 0 r − 1 ( M s ) s ! ( M − s ) ! ( M + 1 ) ! = r M + 1 . \int_0^1 g_{M,r}(u)\,\mathrm{d}u=\sum_{s=0}^{r-1}\binom{M}{s}\frac{s!(M-s)!}{(M+1)!}=\frac{r}{M+1}. ∫ 0 1 g M , r ( u ) d u = s = 0 ∑ r − 1 ( s M ) ( M + 1 )! s ! ( M − s )! = M + 1 r .
Taking expectations proves (3.14). The interval equivalence and the vanishing zero-variance fallback then give the same limit for simultaneous coverage. □ \square □
Proof of Corollary 3.11. Conditional on the Stage-3 data, every nondegenerate coordinate of the studentized Gaussian multiplier vector has variance one. Hence
P ( S n ∗ > x ∣ G 1 ( 3 ) , … , G n 3 ( 3 ) ) ≤ 2 k n e − x 2 / 2 . \mathbb{P}(S_n^*>x\mid G_1^{(3)},\ldots,G_{n_3}^{(3)})\le2k_n e^{-x^2/2}. P ( S n ∗ > x ∣ G 1 ( 3 ) , … , G n 3 ( 3 ) ) ≤ 2 k n e − x 2 /2 .
It follows that the exact conditional critical value satisfies
c 1 − α ∗ ≤ 2 log ( 2 k n / α ) = O { log ( 2 k n ) } c_{1-\alpha}^*\le\sqrt{2\log(2k_n/\alpha)}=O\left\{\sqrt{\log(2k_n)}\right\} c 1 − α ∗ ≤ 2 log ( 2 k n / α ) = O { log ( 2 k n ) }
uniformly for α \alpha α bounded away from zero. For the empirical critical value, (E.16) and M n → ∞ M_n\to\infty M n → ∞ give the same order in probability.
By Lemmas E.1 and E.2,
max j σ ^ G , j = O P { H k n 1 + ν ε n } . \max_j \widehat{\sigma}_{G,j} = \mathrm{O}_{\mathbb{P}}\left\{H_{k_n}\sqrt{1+\nu_{\varepsilon_n}}\right\}. j max σ G , j = O P { H k n 1 + ν ε n } .
By Theorem 3.8 , min j f ^ j ≥ f − / 2 \min_j \widehat{f}_j \ge f_-/2 min j f j ≥ f − /2 with probability tending to one. Substitution in (14) proves (30) . For 0 < ε n ≤ 1 0 < \varepsilon_n \le1 0 < ε n ≤ 1 ,
1 + ν ε n = e ε n + 1 e ε n − 1 ≤ C ε n , \sqrt{1+\nu_{\varepsilon_n}} = \frac{e^{\varepsilon_n}+1}{e^{\varepsilon_n}-1} \le\frac{C}{\varepsilon_n}, 1 + ν ε n = e ε n − 1 e ε n + 1 ≤ ε n C ,
which proves (31) .
It remains to verify the transparent regime. Write
H = H k n . H = H_{k_n}. H = H k n .
Since
H 2 k n = ⌈ log 2 ( 2 k n + 1 ) ⌉ ≤ 1 + ⌈ log 2 ( k n + 1 ) ⌉ = H + 1 ≤ 2 H , H_{2k_n} = \left\lceil\log_2(2k_n+1)\right\rceil\le1+\left\lceil\log_2(k_n+1)\right\rceil= H+1 \le2H, H 2 k n = ⌈ log 2 ( 2 k n + 1 ) ⌉ ≤ 1 + ⌈ log 2 ( k n + 1 ) ⌉ = H + 1 ≤ 2 H ,
and ε n \varepsilon_n ε n is bounded away from zero,
B 1 n ≍ B 2 n ≍ H . B_{1n} \asymp B_{2n} \asymp H. B 1 n ≍ B 2 n ≍ H .
Moreover, H ≤ C ℓ n H \le C\ell_n H ≤ C ℓ n . By Lemma E.1,
σ n ≳ H 1 / 2 , K n 2 = O ( H ) . \sigma_n \gtrsim H^{1/2}, \qquad K_n^2 = O(H). σ n ≳ H 1/2 , K n 2 = O ( H ) .
Under a = 2 / 3 a=2/3 a = 2/3 , β = 1 \beta=1 β = 1 , and fixed positive stage fractions, (20) gives
r 1 n = O ( b n n + H ℓ n n + H n − 2 / 3 ℓ n + H 2 n − 2 / 3 ℓ n ) . r_{1n} = O\left(\frac{b_n}{n} + H\sqrt{\frac{\ell_n}{n}} + Hn^{-2/3}\sqrt{\ell_n} + H^2n^{-2/3}\ell_n\right). r 1 n = O ( n b n + H n ℓ n + H n − 2/3 ℓ n + H 2 n − 2/3 ℓ n ) .
Using b n / n = o ( ℓ n 3 / 2 n − 1 / 2 ) b_n/n=o(\ell_n^{3/2}n^{-1/2}) b n / n = o ( ℓ n 3/2 n − 1/2 ) and H ≤ C ℓ n H \le C\ell_n H ≤ C ℓ n ,
r 1 n = O ( ℓ n 3 / 2 n − 1 / 2 + ℓ n 3 n − 2 / 3 ) . r_{1n} = O\left(\ell_n^{3/2}n^{-1/2}+\ell_n^3n^{-2/3}\right). r 1 n = O ( ℓ n 3/2 n − 1/2 + ℓ n 3 n − 2/3 ) .
The ratio of the second term to the first is
ℓ n 3 n − 2 / 3 ℓ n 3 / 2 n − 1 / 2 = ℓ n 3 / 2 n − 1 / 6 = ( ℓ n 9 n ) 1 / 6 = o ( 1 ) . \frac{\ell_n^3n^{-2/3}}{\ell_n^{3/2}n^{-1/2}}=\ell_n^{3/2}n^{-1/6}=\left(\frac{\ell_n^9}{n}\right)^{1/6}=o(1). ℓ n 3/2 n − 1/2 ℓ n 3 n − 2/3 = ℓ n 3/2 n − 1/6 = ( n ℓ n 9 ) 1/6 = o ( 1 ) .
Therefore,
r 1 n = O ( ℓ n 3 / 2 n − 1 / 2 ) . (82) r_{1n}=O\left(\ell_n^{3/2}n^{-1/2}\right). \tag*{(82)} r 1 n = O ( ℓ n 3/2 n − 1/2 ) . (82)
The proposed bandwidth obeys
h n ≍ ( H 2 ℓ n n ) 1 / 4 = H 1 / 2 ℓ n 1 / 4 n − 1 / 4 . h_n \asymp\left(\frac{H^2\ell_n}{n}\right)^{1/4}=H^{1/2}\ell_n^{1/4}n^{-1/4}. h n ≍ ( n H 2 ℓ n ) 1/4 = H 1/2 ℓ n 1/4 n − 1/4 .
Its leading stochastic density term is
B 2 n h n ℓ n n ≲ h n , \frac{B_{2n}}{h_n}\sqrt{\frac{\ell_n}{n}}\lesssim h_n, h n B 2 n n ℓ n ≲ h n ,
whereas
B 2 n ℓ n h n n = O ( h n ℓ n n ) = o ( h n ) . \frac{B_{2n}\ell_n}{h_n n}=O\left(h_n\sqrt{\frac{\ell_n}{n}}\right)=o(h_n). h n n B 2 n ℓ n = O ( h n n ℓ n ) = o ( h n ) .
Also,
r 1 n h n = O ( ℓ n 5 / 4 H 1 / 2 n 1 / 4 ) = o ( 1 ) , \frac{r_{1n}}{h_n}=O\left(\frac{\ell_n^{5/4}}{H^{1/2}n^{1/4}}\right)=o(1), h n r 1 n = O ( H 1/2 n 1/4 ℓ n 5/4 ) = o ( 1 ) ,
because its fourth power is bounded by C ℓ n 5 / n = o ( 1 ) C\ell_n^5/n=o(1) C ℓ n 5 / n = o ( 1 ) . Consequently,
d n = O ( H 1 / 2 ℓ n 1 / 4 n − 1 / 4 ) . (83) d_n=O\left(H^{1/2}\ell_n^{1/4}n^{-1/4}\right). \tag*{(83)} d n = O ( H 1/2 ℓ n 1/4 n − 1/4 ) . (83)
Combining (E.17) and (E.18) gives
r 1 n d n = O ( H 1 / 2 ℓ n 7 / 4 n − 3 / 4 ) . r_{1n}d_n=O\left(H^{1/2}\ell_n^{7/4}n^{-3/4}\right). r 1 n d n = O ( H 1/2 ℓ n 7/4 n − 3/4 ) .
Since d n ≥ h n d_n\ge h_n d n ≥ h n and r 1 n = o ( h n ) r_{1n}=o(h_n) r 1 n = o ( h n ) , we have r 1 n = o ( d n ) r_{1n}=o(d_n) r 1 n = o ( d n ) and hence r 1 n 2 = o ( r 1 n d n ) r_{1n}^2=o(r_{1n}d_n) r 1 n 2 = o ( r 1 n d n ) . Therefore
R n = O ( H 1 / 2 ℓ n 7 / 4 n − 3 / 4 ) . R_n=O\left(H^{1/2}\ell_n^{7/4}n^{-3/4}\right). R n = O ( H 1/2 ℓ n 7/4 n − 3/4 ) .
It follows that
n 3 ℓ n σ n R n = O ( ℓ n 9 / 4 n − 1 / 4 ) = O { ( ℓ n 9 n ) 1 / 4 } = o ( 1 ) . \frac{\sqrt{n^3\ell_n}}{\sigma_n}R_n=O\left(\ell_n^{9/4}n^{-1/4}\right)=O\left\{\left(\frac{\ell_n^9}{n}\right)^{1/4}\right\}=o(1). σ n n 3 ℓ n R n = O ( ℓ n 9/4 n − 1/4 ) = O { ( n ℓ n 9 ) 1/4 } = o ( 1 ) .
The Gaussian approximation condition is
K n 2 ℓ n 7 n 3 = O ( H ℓ n 7 n ) = O ( ℓ n 8 n ) = o ( 1 ) . \frac{K_n^2\ell_n^7}{n_3}=O\left(\frac{H\ell_n^7}{n}\right)=O\left(\frac{\ell_n^8}{n}\right)=o(1). n 3 K n 2 ℓ n 7 = O ( n H ℓ n 7 ) = O ( n ℓ n 8 ) = o ( 1 ) .
Finally, choose ω n = ℓ n \omega_n=\ell_n ω n = ℓ n in the primitive construction of Lemma C.1. Then
B 1 n 2 ℓ n ω n = O ( H 2 ℓ n 2 ) ≤ O ( ℓ n 4 ) = o ( n 2 / 3 ) , B_{1n}^2\ell_n\omega_n=O(H^2\ell_n^2)\le O(\ell_n^4)=o(n^{2/3}), B 1 n 2 ℓ n ω n = O ( H 2 ℓ n 2 ) ≤ O ( ℓ n 4 ) = o ( n 2/3 ) ,
and
b n = O { ( H 2 ℓ n 2 ) 3 / 2 + ( log n ) 3 } = O { H n 3 ℓ n 3 + ( log n ) 3 } = O ( ℓ n 6 ) . \begin{aligned}
b_n=O\left\{(H^2\ell_n^2)^{3/2}+(\log n)^3\right\} \\
&= O\left\{H_n^3\ell_n^3+(\log n)^3\right\}=O(\ell_n^6).
\end{aligned} b n = O { ( H 2 ℓ n 2 ) 3/2 + ( log n ) 3 } = O { H n 3 ℓ n 3 + ( log n ) 3 } = O ( ℓ n 6 ) .
Moreover,
b n / n ℓ n 3 / 2 n − 1 / 2 = O ( ℓ n 9 / 2 n ) = O { ( ℓ n 9 n ) 1 / 2 } = o ( 1 ) . \frac{b_n/n}{\ell_n^{3/2}n^{-1/2}}=O\left(\frac{\ell_n^{9/2}}{\sqrt{n}}\right)=O\left\{\left(\frac{\ell_n^9}{n}\right)^{1/2}\right\}=o(1). ℓ n 3/2 n − 1/2 b n / n = O ( n ℓ n 9/2 ) = O { ( n ℓ n 9 ) 1/2 } = o ( 1 ) .
Thus the primitive construction satisfies all three localization conditions and the additional transient requirement in the corollary.
Because ℓ n = log { 2 k n ( n + 1 ) } \ell_n=\log\{2k_n(n+1)\} ℓ n = log { 2 k n ( n + 1 )} , condition (3.17) is equivalent to
log k n = o ( n 1 / 9 ) . \log k_n=o(n^{1/9}). log k n = o ( n 1/9 ) .
It therefore includes fixed grids, arbitrarily slowly growing grids, all polynomial grids, and more generally k n = exp { o ( n 1 / 9 ) } k_n=\exp\{o(n^{1/9})\} k n = exp { o ( n 1/9 )} .
Proofs for Post-Processing and Fixed-Chain Comparisons
Proof of Proposition 2.2. Fix j j j . On the original simultaneous coverage event, for every ℓ ≤ j \ell\le j ℓ ≤ j ,
L ℓ I ≤ Q ℓ ≤ Q j . L_\ell^I\le Q_\ell\le Q_j. L ℓ I ≤ Q ℓ ≤ Q j .
where the second inequality follows from monotonicity of the quantile function. Therefore L ~ j I = max ℓ ≤ j L ℓ I ≤ Q j \widetilde{L}_j^I=\max_{\ell\le j}L_\ell^I\le Q_j L j I = max ℓ ≤ j L ℓ I ≤ Q j . Similarly, for every ℓ ≥ j \ell\ge j ℓ ≥ j ,
Q j ≤ Q ℓ ≤ U ℓ I , Q_j\le Q_\ell\le U_\ell^I, Q j ≤ Q ℓ ≤ U ℓ I ,
so Q j ≤ min ℓ ≥ j U ℓ I = U ~ j I Q_j\le\min_{\ell\ge j}U_\ell^I=\widetilde{U}_j^I Q j ≤ min ℓ ≥ j U ℓ I = U j I . Both inequalities hold for every j j j on the same event.
Proof of Proposition 4.1. Let
s J 2 = ( J − 1 ) − 1 ∑ b = 1 J ( W b − W ‾ ) 2 . s_J^2=(J-1)^{-1}\sum_{b=1}^{J}(W_b-\overline{W})^2. s J 2 = ( J − 1 ) − 1 b = 1 ∑ J ( W b − W ) 2 .
For a normal sample, J ( W ‾ − θ ) / s J ∼ t J − 1 \sqrt{J}(\overline{W}-\theta)/s_J\sim t_{J-1} J ( W − θ ) / s J ∼ t J − 1 . Because
S J 2 = J − 1 J s J 2 , S_J^2=\frac{J-1}{J}s_J^2, S J 2 = J J − 1 s J 2 ,
we have
J − 1 ( W ‾ − θ ) S J = J ( W ‾ − θ ) s J ∼ t J − 1 . \frac{\sqrt{J-1}(\overline{W}-\theta)}{S_J}
=\frac{\sqrt{J}(\overline{W}-\theta)}{s_J}
\sim t_{J-1}. S J J − 1 ( W − θ ) = s J J ( W − θ ) ∼ t J − 1 .
Conditional on W 1 , … , W J W_1,\ldots,W_J W 1 , … , W J , the multiplier numerator is centered normal with variance
Var ( J − 1 / 2 ∑ b = 1 J ξ b ( W b − W ‾ ) ∣ W 1 , … , W J ) = J − 1 ∑ b = 1 J ( W b − W ‾ ) 2 = S J 2 . \operatorname{Var}\left(J^{-1/2}\sum_{b=1}^{J}\xi_b(W_b-\overline{W})\mid W_1,\ldots,W_J\right)=J^{-1}\sum_{b=1}^{J}(W_b-\overline{W})^2=S_J^2. Var ( J − 1/2 b = 1 ∑ J ξ b ( W b − W ) ∣ W 1 , … , W J ) = J − 1 b = 1 ∑ J ( W b − W ) 2 = S J 2 .
Division by S J S_J S J therefore gives an exact conditional N ( 0 , 1 ) N(0,1) N ( 0 , 1 ) variable. Neither distribution changes when an external within-block sample size increases while J J J remains fixed.
Proof of Proposition 4.2. The upper tail of a t ν t_\nu t ν variable is regularly varying with index − ν -\nu − ν :
P ( t ν > x ) ∼ C ν x − ν ( x → ∞ ) \mathbb{P}(t_\nu>x)\sim C_\nu x^{-\nu}\qquad(x\to\infty) P ( t ν > x ) ∼ C ν x − ν ( x → ∞ )
for a positive constant C ν C_\nu C ν . Setting the tail probability equal to α / ( 2 k ) \alpha/(2k) α / ( 2 k ) and inverting gives
t ν , 1 − α / ( 2 k ) ∼ ( 2 C ν k α ) 1 / ν , t_{\nu,1-\alpha/(2k)}\sim\left(\frac{2C_\nu k}{\alpha}\right)^{1/\nu}, t ν , 1 − α / ( 2 k ) ∼ ( α 2 C ν k ) 1/ ν ,
which proves (4.1). The most stringent Holm step uses the same order of tail probability. For a standardized Gaussian vector ( Z 1 , … , Z k ) (Z_1,\ldots,Z_k) ( Z 1 , … , Z k ) , regardless of dependence,
P ( max j ≤ k ∣ Z j ∣ > x ) ≤ 2 k e − x 2 / 2 . \mathbb{P}\left(\max_{j\le k}|Z_j|>x\right)\le2k e^{-x^2/2}. P ( j ≤ k max ∣ Z j ∣ > x ) ≤ 2 k e − x 2 /2 .
Taking x = 2 log ( 2 k / α ) x=\sqrt{2\log(2k/\alpha)} x = 2 log ( 2 k / α ) proves the O ( log k ) O(\sqrt{\log k}) O ( log k ) upper order for a Gaussian critical value.