acceptodds
Under review as a conference paper at ICLR 2027

Martingalized U-statistics-based sequential inference: a blessing of degeneracy

Abstract

Degenerate degree-two U-statistics have non-Gaussian limits, making sequential inference substantially more difficult than in the nondegenerate case. However, row normalization preserves the target parameter and makes the centered numerator a martingale on a harmonic variance clock, at the cost of logarithmic variance inflation. We establish a strong Gaussian approximation for this process and consistently estimate its variance through online updates, allowing spectrum-free calibration. Combining this strong approximation with Gaussian-mixture (GM) and stitched law-of-the-iterated-logarithm (LIL) boundaries yields confidence sequences with asymptotic time-uniform coverage and corresponding sequential tests for null hypotheses under which the kernel is degenerate. We further extend the framework to multi-dimensional vector-valued kernels, yielding Mahalanobis confidence ellipsoids based on consistent covariance estimation. Numerical experiments illustrate sequential type-I error control and favorable detection power in two-sample and independence testing against spectral baselines, and in three-sample homogeneity testing using vector confidence ellipsoids.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Degeneracy, Martingale, Sequential test, U-statistics

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_44GjOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies sequential inference for degenerate degree-2 U-statistics, which generally have Gaussian chaos limits that depend on the spectrum of the underlying kernel operator and are therefore difficult to calibrate sequentially. To address this problem, the authors replace the ordinary U-statistic by a row-normalized version that admits a martingale representation on a harmonic variance clock and yields a strong Gaussian approximation at the cost of only logarithmic variance inflation. This gives spectrum-free, asymptotically time-uniform confidence sequences and sequential tests, and extends to fixed-dimensional vector-valued kernels. The benefits of the proposed method are illustrated with toy experiments on sequential kernel two-sample and independence testing, and compared against spectral calibration of the Gaussian chaos limit.

Critical strengths
  • Technical elegance. The basic idea of the paper, using row normalization to turn a degenerate U-statistic into a martingale and thereby replacing Gaussian chaos calibration by ordinary Gaussian calibration at only logarithmic increase in variance, is elegant and a strong technical contribution. The benefits of the significantly simpler calibration compared to SAGE, which the paper views as the main baseline, are clear and convincing.
  • Rigor and generality. Despite its mathematical rigor, the paper is clearly written. The fact that the argument applies to general symmetric degree-2 U-statistics is nice and the assumptions (i.i.d., finite fourth moments, fixed kernel) do not take away too much from the theory.
Critical weaknesses
  • Unclear finite-sample convergence. The guarantees of the proposed procedure are asymptotic. That, by itself, is fair and appropriately signposted. However, the harmonic clock of the Gaussian approximation makes the speed of convergence a particularly salient issue for this paper. Even though the slow clock does not necessarily imply slow convergence of the test, the absence of either a discussion of this issue or an empirical study across increasing monitoring starts currently leaves an important practical question unresolved.
  • Experimental scope and significance. The experiments are limited to synthetic toy settings and compare only against the spectrally-calibrated SAGE method of Cai et al. (2026). While the experiments provide illustrative evidence that the proposed martingalized calibration results in higher power than more cumbersome and computationally expensive spectral calibration, it does not establish a broad advantage over competing sequential inference procedures at the application level. This is consistent with how the contributions are framed, but limits the demonstrated significance of the contributions. Similarly, the related work section does a good job at motivating the proposed method against SAGE specifically and surveying alternative sequential testing procedures, but then, rather unsatisfyingly, leaves unclear why one should prefer the proposed method over existing methods beyond SAGE. The paper could do a better job at making clear the significance of its contributions, both in the related work section and through its experiments.

Overall, while the proposed method is elegant, rigorous, and well-presented, I hesitantly lean towards rejection because the paper positions itself in a somewhat narrow niche and currently does not convincingly establish a clear advantage against competing sequential inference procedures at the application level. I therefore suspect that the broader impact of the proposed method may be limited, though I acknowledge that this perception may stem partly from my own background being outside sequential testing specifically. I therefore encourage the authors to use the rebuttal to explicitly highlight the significance and practical value of their contributions.

Questions for authors
  • Does your proof yield any quantitative insight into the speed of convergence, even through rough rates under stronger assumptions or in special cases? Is there reason to expect the resulting tests to be systematically conservative or anti-conservative for small monitoring starts mm?
  • Can you clarify when a practitioner should choose your proposed method over, say, the sequential two-sample test of Shekhar and Ramdas (2024) or the sequential independence test of Podkopaev et al. (2023), and why?
9 comments

We are grateful to the reviewer for their time and valuable questions and suggestions.

Q1. We now strengthen the original asymptotic error-control results with explicit infinite-horizon error bounds for both scalar and vector procedures, under the same canonical-kernel and fourth-moment assumptions.

For the centered kernels h0=h−θh_0=h-\theta and h0=h−θ\boldsymbol h_0=\boldsymbol h-\boldsymbol\theta, let τ2=Eh02\tau^2=\mathbb{E}h_0^2 and Ω=E(h0h0T)\boldsymbol\Omega=\mathbb{E}(\boldsymbol h_0\boldsymbol h_0^{\mathsf T}). Write Tn=∑j=1n−1j−1T_n=\sum_{j=1}^{n-1}j^{-1}, K=E∣h0(X1,X2)∣4/τ4K=\mathbb{E}|h_0(X_1,X_2)|^4/\tau^4 and Kd=E∣Ω−1/2h0(X1,X2)∣24K_d=\mathbb{E}\\|\boldsymbol\Omega^{-1/2}\boldsymbol h_0(X_1,X_2)\\|_2^4. For a deterministic proof tolerance 0<δ≤1/20 < \delta\le1/2, define

pms(δ)=1408Kδ2Tm+80Kδ2Tm2,pmv(δ)=1408Kdδ2Tm+12Kdδ2Tm2.p_m^{\rm s}(\delta)=\frac{1408K}{\delta^2T_m}+\frac{80K}{\delta^2T_m^2},\qquad p_m^{\rm v}(\delta)=\frac{1408K_d}{\delta^2T_m}+\frac{12K_d}{\delta^2T_m^2}.

Table 1 summarizes the bounds and each deterministic correction Δm\Delta_m is defined in the corresponding theorem below.

Table 1. Bounds on the probability of any error at n≥mn\ge m. Each right-hand side is truncated at one.

ProcedureFull-horizon error boundMoment input
Scalar GMpms(δ)+F(c2−ΔmsGM(δ))p_m^{\rm s}(\delta)+F(\sqrt{c^2-\Delta_m^{\rm sGM}(\delta)})KK
Scalar LILpms(δ)+αeΔmsLIL(δ)p_m^{\rm s}(\delta)+\alpha e^{\Delta_m^{\rm sLIL}(\delta)}KK
VEC-GMpmv(δ)+αeΔmVGM(δ)p_m^{\rm v}(\delta)+\alpha e^{\Delta_m^{\rm VGM}(\delta)}KdK_d
VEC-LILpmv(δ)+αeΔmVLIL(δ)p_m^{\rm v}(\delta)+\alpha e^{\Delta_m^{\rm VLIL}(\delta)}KdK_d

For scalar GM, c=F−1(α)c=F^{-1}(\alpha) and the displayed bound requires ΔmsGM(δ)<c2\Delta_m^{\rm sGM}(\delta) < c^2. Here F(c)=21−Φ(c)+cϕ(c)F(c)=2\\{1-\Phi(c)+c\phi(c)\\} for two-sided inference and F(c)=1−Φ(c)+cϕ(c)+ϕ(c)2/Φ(c)F(c)=1-\Phi(c)+c\phi(c)+\phi(c)^2/\Phi(c) for upper-tail inference, where Φ\Phi and ϕ\phi are the standard normal distribution and density. For every row, Δm(δ)=O(δ+(m−1)−1)\Delta_m(\delta)=O(\delta+(m-1)^{-1}) with dimension, nominal level and boundary parameters fixed. Balancing this correction with K\*/(δ2Tm)K_\*/(\delta^2T_m) by taking δ≍(K\*/Tm)1/3\delta\asymp(K_\*/T_m)^{1/3} gives the common rate

Pan error at some n≥m≤α+O((K\*/Tm)1/3),K\*=KorKd.\mathbb{P}\\{\text{an error at some }n\ge m\\}\le\alpha+O\bigl((K_\*/T_m)^{1/3}\bigr),\qquad K_\*=K\\ \text{or}\\ K_d.

For each fixed admissible law this is O((log⁡m)−1/3)O((\log m)^{-1/3}) excess error. These quantitative bounds directly imply the original scalar and vector asymptotic time-uniform coverage guarantees as m→∞m\to\infty.

We state the three theorems below using the notation of the manuscript. Due to space constraints, each theorem is followed by a proof sketch. Assumption (A1) requires E∣h0∣4<∞\mathbb{E}|h_0|^4 < \infty and τ2>0\tau^2 > 0; (A2) requires E∣h0∣24<∞\mathbb{E}\\|\boldsymbol h_0\\|_2^4 < \infty and Ω≻0\boldsymbol\Omega\succ0. For scalar inference, the centered rows are Yi=(i−1)−1∑j<ih0(Xi,Xj)Y_i=(i-1)^{-1}\sum_{j < i}h_0(X_i,X_j), Mn=∑i=2nYiM_n=\sum_{i=2}^nY_i, and τ^n\widehat\tau_n is the original centered row-scale estimate. The sets Cm,nell(α)C_{m,n}^{\rm ell}(\alpha) are the original confidence ellipsoids for θ=Eh(X1,X2)\boldsymbol\theta=\mathbb{E}\boldsymbol h(X_1,X_2).

Common scalar proof ingredients. Since τ>0\tau > 0, replacing h0h_0 by h0/τh_0/\tau scales both MnM_n and τ^n\widehat\tau_n by 1/τ1/\tau, preserving all crossing events. K=E∣h0∣4/τ4K=\mathbb{E}|h_0|^4/\tau^4 refers to the original kernel, and the procedure still estimates the unknown scale. Write [M]n=∑i=2nYi2[M]_n=\sum_{i=2}^nY_i^2. The manuscript’s original Skorokhod embedding (Lemma 1) gives Mn=B(Rn)M_n=B(R_n), where BB is standard Brownian motion and RnR_n are increasing stopping times with R1=0R_1=0. Its moment condition permits Itô’s formula and isometry, which yield

sup⁡n≥2ERn−[M]n2=23∑i=2∞EYi4≤2K.\sup_{n\ge2}\mathbb{E}\\{R_n-[M]_n\\}^2=\frac23\sum_{i=2}^{\infty}\mathbb{E}Y_i^4\le2K.

Combining this with the explicit clock estimates in the proof of manuscript Theorem 1 and the maximal inequality gives P((Ems)c)≤pms(δ)\mathbb{P}((\mathcal E_m^{\rm s})^c)\le p_m^{\rm s}(\delta), where Ems=⋂n≥m∣Rn/Tn−1∣≤δ,∣Rn−[M]n∣≤δTm/4\mathcal E_m^{\rm s}=\bigcap_{n\ge m}\\{|R_n/T_n-1|\le\delta,\\ |R_n-[M]_n|\le\delta T_m/4\\}. Both scalar proofs use this event and the existing Brownian boundary calibrations (manuscript Lemmas 3 and 4), comparing boundaries at RnR_n directly.

Theorem 1 (Scalar GM). Under (A1), take 0<α<10 < \alpha < 1 for two-sided inference or 0<α<1/2+1/π0 < \alpha < 1/2+1/\pi for upper-tail testing, and let c=F−1(α)c=F^{-1}(\alpha) with the corresponding calibration function defined above. For γ>0\gamma > 0, put

Hγ(c)=sup⁡r≥1r−γ(c2+log⁡r)={c2,γc2≥1,γ−1eγc2−1,γc2<1.\mathcal H_\gamma(c)=\sup_{r\ge1}r^{-\gamma}(c^2+\log r)=\begin{cases}c^2,&\gamma c^2\ge1,\\\\\gamma^{-1}e^{\gamma c^2-1},&\gamma c^2 < 1.\end{cases}

For 0<δ≤1/20 < \delta\le1/2, define

ΔmsGM(δ)=log⁡1+δ1−δ+δH1(c)4(1−δ)+H1/2(c)2m−1.\Delta_m^{\rm sGM}(\delta)=\log\frac{1+\delta}{1-\delta}+\frac{\delta\mathcal H_1(c)}{4(1-\delta)}+\frac{\mathcal H_{1/2}(c)^2}{m-1}.

If ΔmsGM(δ)<c2\Delta_m^{\rm sGM}(\delta) < c^2, then

\mathbb{P}\\{\text{an error at some }n\ge m\\}\le\min\left\\{1,\\ p_m^{\rm s}(\delta)+F\\!\left(\sqrt{c^2-\Delta_m^{\rm sGM}(\delta)}\right)\right\\}.

Here the error event is Mn>τ^nbc(Tn;Tm)M_n > \widehat\tau_nb_c(T_n;T_m) for upper-tail testing, or ∣Mn∣>τ^nbc(Tn;Tm)|M_n| > \widehat\tau_nb_c(T_n;T_m) for two-sided noncoverage, where bc(t;t0)=t[c2+log⁡(t/t0)]1/2b_c(t;t_0)=\\{t[c^2+\log(t/t_0)]\\}^{1/2}.

Proof sketch. Use the common scalar preparation above. Write r=Tn/Tmr=T_n/T_m. The centered-scale identity in the proof of manuscript Theorem 1, Tnτ^n2=[M]n−Mn2/(n−1)T_n\widehat\tau_n^2=[M]_n-M_n^2/(n-1), gives

∣Mn∣>τ^nbc(Tn;Tm)⟺Mn2>[M]n(c2+log⁡r)1+(c2+log⁡r)/(n−1).|M_n| > \widehat\tau_nb_c(T_n;T_m)\quad\Longleftrightarrow\quad M_n^2 > \frac{[M]_n(c^2+\log r)}{1+(c^2+\log r)/(n-1)}.

On Ems\mathcal E_m^{\rm s}, the bounds defining Hγ(c)\mathcal H_\gamma(c) and r≤(n−1)/(m−1)r\le(n-1)/(m-1) show that this implies

∣B(Rn)∣>bc2−ΔmsGM(δ)(Rn;(1−δ)Tm).|B(R_n)| > b_{\sqrt{c^2-\Delta_m^{\rm sGM}(\delta)}}\bigl(R_n;(1-\delta)T_m\bigr).

For upper-tail rejection, Mn>0M_n > 0 gives the same inclusion without absolute values. The manuscript’s Brownian calibration results (Lemmas 3 and 4) bound this crossing probability by F(c2−ΔmsGM(δ))F\bigl(\sqrt{c^2-\Delta_m^{\rm sGM}(\delta)}\bigr). Adding P((Ems)c)\mathbb{P}((\mathcal E_m^{\rm s})^c) proves the claim.

Theorem 2 (Scalar LIL). Under (A1), fix 0<α<10 < \alpha < 1, η>1\eta > 1 and s>1s > 1. Let J=1J=1 for upper-tail testing and J=2J=2 for two-sided inference, and write cη=(η1/4+η−1/4)2/2c_\eta=(\eta^{1/4}+\eta^{-1/4})^2/2 and ℓη=1/max⁡1,log⁡η\ell_\eta=1/\max\\{1,\log\eta\\}.

For 0<δ≤1/20 < \delta\le1/2, put

\begin{aligned}\Delta_m^{\rm sLIL}(\delta)={}&s\ell_\eta\log\frac{1+\delta}{1-\delta}\\\\&+\frac{\delta}{4(1-\delta)}\left\\{\log\frac{J\zeta(s)}{\alpha}+s\log\frac{\max\\{1,\log\eta\\}}{\log\eta}+\frac{s\ell_\eta}{e}\right\\}\\\\&+\frac{c_\eta}{m-1}\left\\{\log\frac{J\zeta(s)}{\alpha}+s\log\frac{\max\\{1,\log\eta\\}}{\log\eta}+\frac{2s\ell_\eta}{e}\right\\}^2.\end{aligned}

Then the original scalar LIL procedure satisfies

\mathbb{P}\\{\text{an error at some }n\ge m\\}\le\min\left\\{1,\\ p_m^{\rm s}(\delta)+\alpha e^{\Delta_m^{\rm sLIL}(\delta)}\right\\}.

Proof sketch. Use the common scalar preparation above. Write the squared LIL boundary as Tncηwα(Tn/Tm)T_nc_\eta w_\alpha(T_n/T_m), where

wα(r)=slog⁡log⁡max⁡ηr,e+log⁡Jζ(s)α(log⁡η)s,r≥1.w_\alpha(r)=s\log\log\max\\{\eta r,e\\}+\log\frac{J\zeta(s)}{\alpha(\log\eta)^s},\qquad r\ge1.

For r′≥r≥1r'\ge r\ge1 and γ>0\gamma > 0,

wα(r′)−wα(r)≤sℓηlog⁡(r′/r),sup⁡r≥1r−γwα(r)≤log⁡Jζ(s)α+slog⁡max⁡1,log⁡ηlog⁡η+sℓηeγ.\begin{aligned}w_\alpha(r')-w_\alpha(r)&\le s\ell_\eta\log(r'/r),\\\\\sup_{r\ge1}r^{-\gamma}w_\alpha(r)&\le\log\frac{J\zeta(s)}{\alpha}+s\log\frac{\max\\{1,\log\eta\\}}{\log\eta}+\frac{s\ell_\eta}{e\gamma}.\end{aligned}

With r=Tn/Tmr=T_n/T_m, the same centered-scale identity makes the squared error condition

Mn2>[M]ncηwα(r)1+cηwα(r)/(n−1).M_n^2 > \frac{[M]_nc_\eta w_\alpha(r)}{1+c_\eta w_\alpha(r)/(n-1)}.

Set α′=αeΔmsLIL(δ)\alpha'=\alpha e^{\Delta_m^{\rm sLIL}(\delta)}. On Ems\mathcal E_m^{\rm s}, the preceding bounds and r≤(n−1)/(m−1)r\le(n-1)/(m-1) imply

Mn2Rn>cηwα′!(Rn(1−δ)Tm).\frac{M_n^2}{R_n} > c_\eta w_{\alpha'}\\!\left(\frac{R_n}{(1-\delta)T_m}\right).

For J=1J=1, rejection also requires Mn>0M_n > 0. The manuscript’s Brownian calibration lemmas (Lemmas 3 and 4) bound this one- or two-sided crossing probability by α′\alpha' when α′<1\alpha' < 1. Adding P((Ems)c)\mathbb{P}((\mathcal E_m^{\rm s})^c) proves the claim. And if α′≥1\alpha'\ge1, the bound truncated at one is immediate.

Theorem 3 (Vector GM and LIL). Under (A2), fix 0<α<10 < \alpha < 1 and 0<δ≤1/20 < \delta\le1/2. For VEC-GM, define

ΔmVGM(δ)=d2log⁡1+δ1−δ+δdlog⁡2+2log⁡(1/α)+d/e6(1−δ)+dlog⁡2+2log⁡(1/α)+2d/e2m−1.\begin{aligned}\Delta_m^{\rm VGM}(\delta)={}&\frac d2\log\frac{1+\delta}{1-\delta}+\frac{\delta\\{d\log2+2\log(1/\alpha)+d/e\\}}{6(1-\delta)}\\\\&+\frac{\\{d\log2+2\log(1/\alpha)+2d/e\\}^2}{m-1}.\end{aligned}

For VEC-LIL, retain the original parameters a>1a > 1, β>1\beta > 1, ε∈(0,1)\varepsilon\in(0,1) and q>1q > 1, and define

\begin{aligned}\Delta_m^{\rm VLIL}(\delta)={}&q\log\left(1+\frac{\log\\{(1+\delta)/(1-\delta)\\}}{\log a}\right)+\frac{d+1}{2}\log\frac{1+\delta}{1-\delta}\\\\&+\frac{\delta}{3(1-\delta)}\left\\{\log\frac{\zeta(q)\beta}{\alpha(1-\beta^{-1})}+d\log\frac{3\beta}{\varepsilon}+\frac{q}{e\log a}\right\\}\\\\&+\frac{2a}{(1-\varepsilon)^2(m-1)}\left\\{\log\frac{\zeta(q)\beta}{\alpha(1-\beta^{-1})}+d\log\frac{3\beta}{\varepsilon}+\frac{2q}{e\log a}\right\\}^2.\end{aligned}

For either procedure, use the corresponding Δm(δ)\Delta_m(\delta). Then

P∃n≥m:θ∉Cm,nell(α)≤min⁡1,pmv(δ)+αeΔm(δ).\mathbb{P}\\{\exists n\ge m:\boldsymbol\theta\notin C_{m,n}^{\rm ell}(\alpha)\\}\le\min\\{1,\\ p_m^{\rm v}(\delta)+\alpha e^{\Delta_m(\delta)}\\}.

The original centered covariance estimator is used, with Cm,nell(α)=RdC_{m,n}^{\rm ell}(\alpha)=\mathbb{R}^d whenever that estimator is singular.

Proof sketch. As in the scalar case, multiplication by Ω−1/2\boldsymbol\Omega^{-1/2} preserves noncoverage and reduces the covariance to IdI_d, with its original dependence retained in KdK_d. For the normalized rows Yi=(i−1)−1∑j<ih0(Xi,Xj)\boldsymbol Y_i=(i-1)^{-1}\sum_{j < i}\boldsymbol h_0(X_i,X_j), let Mn=∑i=2nYi\boldsymbol M_n=\sum_{i=2}^n\boldsymbol Y_i and define

Qn=∑i=2nYiYiT,Pn=Qn+2⟨M⟩n3,\boldsymbol Q_n=\sum_{i=2}^n\boldsymbol Y_i\boldsymbol Y_i^{\mathsf T},\qquad\boldsymbol P_n=\frac{\boldsymbol Q_n+2\langle\boldsymbol M\rangle_n}{3},

where ⟨M⟩n\langle\boldsymbol M\rangle_n is the predictable quadratic variation. Every scalar projection is square-integrable, so Howard et al. (2020, Lemma 3(f)) gives the nonnegative supermartingales

\exp\left\\{\boldsymbol\lambda^{\mathsf T}\boldsymbol M_n-\tfrac12\boldsymbol\lambda^{\mathsf T}\boldsymbol P_n\boldsymbol\lambda\right\\},\qquad\boldsymbol\lambda\in\mathbb{R}^d,

starting at one. This verifies the conditions for the vector boundary results.

Define the common event

\mathcal E_m^{\rm v}=\left\\{\sup_{n\ge m}\\|\langle\boldsymbol M\rangle_n/T_n-I_d\\|_F\le\delta/2,\\ \sup_{n\ge m}\\|\boldsymbol Q_n-\langle\boldsymbol M\rangle_n\\|_F\le\delta T_m/2\right\\},

where IdI_d is the identity matrix and ∣⋅∣F\\|\cdot\\|_F is the Frobenius norm. A quantitative refinement of the covariance-clock argument in manuscript Lemma 5 gives P((Emv)c)≤pmv(δ)\mathbb{P}((\mathcal E_m^{\rm v})^c)\le p_m^{\rm v}(\delta). On Emv\mathcal E_m^{\rm v}, simultaneously for n≥mn\ge m,

(1−δ)TnId⪯Qn,Pn⪯(1+δ)TnId,∣Pn−Qn∣op≤δTm/3,(1-\delta)T_nI_d\preceq\boldsymbol Q_n,\boldsymbol P_n\preceq(1+\delta)T_nI_d,\qquad\\|\boldsymbol P_n-\boldsymbol Q_n\\|_{\rm op}\le\delta T_m/3,

where ∣⋅∣op\\|\cdot\\|_{\rm op} is the operator norm. Apply the Gaussian-mixture bound of Howard et al. (2021, Section 3.2) for GM and the self-normalized bound of Whitehouse et al. (2026, Theorem 4.1) for LIL, as in manuscript Lemma 7. Use Gaussian regularization and a LIL variance floor of (1−δ)Tm(1-\delta)T_m, with LIL epoch weights ζ(q)(1+j)q\zeta(q)(1+j)^q, j=0,1,…j=0,1,\ldots.

As in the scalar proofs, the remaining step transfers these boundaries to the original centered estimator. In the normalized coordinates, manuscript Lemma 5 gives

TnΩ^n=Qn−MnMnTn−1.T_n\widehat{\boldsymbol\Omega}_n=\boldsymbol Q_n-\frac{\boldsymbol M_n\boldsymbol M_n^{\mathsf T}}{n-1}.

On Emv\mathcal E_m^{\rm v}, apply Sherman–Morrison and the displayed covariance bounds. Using Tn/Tm≤(n−1)/(m−1)T_n/T_m\le(n-1)/(m-1) and the same logarithm estimates bounds the covariance perturbation and centering losses by the corresponding Δm(δ)\Delta_m(\delta). Hence noncoverage on Emv\mathcal E_m^{\rm v} implies crossing the cited boundary at level αeΔm(δ)\alpha e^{\Delta_m(\delta)}, which bounds its probability when below one. Adding P((Emv)c)≤pmv(δ)\mathbb{P}((\mathcal E_m^{\rm v})^c)\le p_m^{\rm v}(\delta) and truncating at one proves the result.

For each of the four procedures, a known upper bound on the corresponding moment KK or KdK_d gives a sufficient large start to choose mm such that the applicable explicit error bound is at most α+ϵ\alpha+\epsilon, for a prescribed tolerance ϵ>0\epsilon > 0. We will include the three theorems and their complete proofs in the appendix to the revision.

Reviewer_4T2wOpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper contributes tools and results for sequential inference based on degenerate degree-two U-statistics, building on previous work by Chatterjee and Ramdas (2026). The authors establish a strong Gaussian approximation and a method for consistent online variance estimation, enabling confidence sequences with asymptotic time-uniform coverage and corresponding sequential hypothesis tests, not requiring any form of spectral estimation. Several testing experiments demonstrate good computational efficiency and detection power compared with spectral baselines.

Critical strengths

The main strength of the paper is its clear motivation and presentation. The authors identify a well-defined and relevant problem, explain the challenges of existing approaches, and provide sufficient context to make the proposed method easy to follow. The results are technically sound, the methods are clearly motivated, and both are certainly non-trivial.

Critical weaknesses

No major weaknesses.

Questions for authors

I have two minor questions regarding the practical calibration of the proposed procedures:

  1. Conservativeness of the vector LIL boundary: In Table 3, VEC-WWR-LIL achieves 100% empirical coverage across all considered monitoring starts, accompanied by substantially lower detection power than VEC-GM. While the authors acknowledge this behavior, I would be interested in whether alternative boundary parameters or other calibration choices could reduce this conservativeness and improve practical performance.
  2. Choice of monitoring start: Since the theoretical guarantees are asymptotic as the monitoring start (m) tends to infinity, could the authors provide further guidance on choosing (m) in practice? For example via a sensitivity analysis of coverage and power across different monitoring starts.
3 comments

We appreciate the reviewer’s time and thoughtful feedback, as well as their positive assessment of our work.

Q1. This conservativeness mainly comes from the large radial-boundary constants, which can be reduced by deterministic tuning.

With d=3d=3, m=30m=30 and N=2000N=2000, the submitted parameters (a,β,ε,q)=(2,2,0.5,1.4)(a,\beta,\varepsilon,q)=(2,2,0.5,1.4) give a boundary of 42.7642.76, whereas the GM boundary is 10.6510.65. Holding aa, ε\varepsilon and qq fixed, minimizing the squared LIL boundary over β>1\beta > 1 reduces to minimizing (d+2)log⁡β−log⁡(β−1)(d+2)\log\beta-\log(\beta-1). Its unique minimizer is β=(d+2)/(d+1)=1.25\beta=(d+2)/(d+1)=1.25 for d=3d=3. We then fixed β=1.25\beta=1.25 and considered every combination of

a∈1.1,1.25,1.5,2,ε∈0.05,0.1,0.2,0.5,q∈1.2,1.4,2,3.a\in\\{1.1,1.25,1.5,2\\},\qquad\varepsilon\in\\{0.05,0.1,0.2,0.5\\},\qquad q\in\\{1.2,1.4,2,3\\}.

We also included the original choice (2,2,0.5,1.4)(2,2,0.5,1.4). For each start m∈20,30,40,100,400m\in\\{20,30,40,100,400\\}, we evaluated the maximum LIL/GM boundary ratio over all integers m≤n≤2000m\le n\le2000 for each candidate and selected the one with the smallest maximum ratio. Selection uses only the boundary formulas and fixed design quantities d=3d=3, α=0.05\alpha=0.05, mm and N=2000N=2000, before generating any outcomes.

For each tested start, this rule selects (a,β,ε,q)=(1.1,1.25,0.05,1.4)(a,\beta,\varepsilon,q)=(1.1,1.25,0.05,1.4). At m=30,N=2000m=30,N=2000 its boundary is 20.9120.91. Thus deterministic tuning substantially reduces the original constant, while the tuned LIL boundary is still larger than GM at this endpoint. Table 1 gives representative starts and effects. We can notice that tuning improves power, although LIL remains conservative and less powerful than GM in this setting. We will summarize this tuning improvement in the revision.

Table 1. Additional three-sample testing results through N=2000N=2000.

MethodmmNull coveragePower (0.10)Power (0.20)Power (0.40)Capped time (0.20)
VEC-GM200.9630.1980.9681.000881.6
VEC-GM300.9770.1860.9681.000908.4
VEC-GM4000.9980.1360.9561.0001010.5
VEC-WWR-LIL201.0000.0000.0000.0522001.0
VEC-WWR-LIL301.0000.0000.0000.0582001.0
VEC-WWR-LIL4001.0000.0000.0000.1022001.0
VEC-LIL (tuned)201.0000.0000.1001.0001969.0
VEC-LIL (tuned)301.0000.0000.1021.0001967.7
VEC-LIL (tuned)4001.0000.0000.1561.0001946.7

Q2. The sensitivity analysis shows broadly similar null coverage and power for MG-GM across the tested monitoring starts in the Gaussian MMD and HSIC experiments. This stability supports viewing mm as a monitoring start specified in advance based on knowledge of the data-generating mechanism and study context, rather than a parameter requiring tuning.

We examined sensitivity to the monitoring start across m∈20,100,200,400,800m\in\\{20,100,200,400,800\\} in the Gaussian MMD and HSIC experiments, with α=0.05\alpha=0.05, N=2000N=2000. Tables 2 and 3 report null coverage probabilities, power and capped rejection times for representative starts.

For MG-GM, all tested starts give empirical null coverage above the nominal target, while power varies relatively little. Later starts increase coverage but can delay detection. The vector experiment shows a similar tradeoff: VEC-GM null coverage increases across the tested starts, while power at the intermediate signal decreases slightly and capped rejection times become longer (Table 1).

We will summarize this interpretation of mm and the sensitivity results in the revision.

Table 2. Monitoring-start sensitivity of MG in Gaussian MMD testing at α=0.05\alpha=0.05 through N=2000N=2000.

MethodmmNull coveragePower (0.10)Power (0.15)Power (0.20)Capped time (0.15)
MG-GM200.9640.3140.7280.9681271.7
MG-GM4000.9920.3320.7620.9741274.5
MG-GM8000.9940.3460.7700.9761358.5
MG-LIL200.9890.1480.5440.9241545.3
MG-LIL4000.9970.1940.6180.9441507.3
MG-LIL8000.9980.1900.6180.9441558.7

Table 3. Monitoring-start sensitivity of MG in Gaussian HSIC testing with known Gaussian marginal centering at α=0.05\alpha=0.05 through N=2000N=2000.

MethodmmNull coveragePower (0.10)Power (0.15)Power (0.20)Capped time (0.15)
MG-GM200.9630.5100.9360.998895.0
MG-GM4000.9890.5380.9520.998914.0
MG-GM8000.9920.5440.9540.9981052.2
MG-LIL200.9910.2700.8720.9961157.9
MG-LIL4000.9980.3180.8880.9981118.5
MG-LIL8000.9990.3160.8880.9981203.0

We thank the reviewer again for the helpful comments. We hope these responses clarify the points raised and would be happy to discuss any remaining questions.

Thanks for the clarifying experiments. I keep my (positive) score.

Thank you very much for your encouraging feedback and positive assessment. We are pleased that our responses have addressed your concerns.

Reviewer_ZczTOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies degenerate degree-two U-statistics, which do not have classical Gaussian asymptotics. Through a row-reweighting construction, the authors approximate the resulting martingale by Brownian motion and estimate its variance online. This allows asymptotically valid sequential inference without estimating the kernel spectrum.

Critical strengths
  1. The proposed sequential method is interesting.
  2. The theory is carefully developed.
  3. The implementation is simple.
Critical weaknesses
  1. No real data is used to demonstrate the strength of the theory.
  2. In Section 5, the only competitor is SAGE. The authors need to compare with additional methods to support the claims.
Questions for authors

Can the authors provide additional numerical evidence to demonstrate the advantages of the new theoretical results?

4 comments

We thank the reviewer for their time, careful reading, and valuable comments.

W1. We analyzed Kevin Hillstrom’s public MineThatData email experiment, with 64000 customers randomly assigned to a men’s email campaign, a women’s email campaign or a no-email control. Visits, purchases and spending were recorded over the following two weeks. We used the public CSV mirror from scikit-uplift’s fetch_hillstrom loader. (Dataset description: TensorFlow Datasets, Hillstrom.) We test whether the campaigns yield the same response distribution. Visits and purchases can occur at different times during follow-up. In campaigns with staggered follow-up, monitoring completed customer records as they arrive allows detection before all outcomes have been collected. We illustrate this use retrospectively with the released two-week summaries. For each customer, let VV indicate a website visit, AA a purchase, and B=0,1,2,3B=0,1,2,3 denote spending of 00, (0,50](0,50], (50,100](50,100] or more than 100100 dollars. We use the fixed response category C=8V+4A+BC=8V+4A+B, with category 16 reserved for missing outcomes (none occurs). Write PaP_a for the law of CC in group a∈0,M,Wa\in\\{0,M,W\\} (control, men’s email, women’s email), and pa=(Pa(C=c))c=016\boldsymbol p_a=(P_a(C=c))_{c=0}^{16} for its category-probability vector. The null hypothesis is H0:P0=PM=PWH_0:P_0=P_M=P_W. Under this null, p=p0=pM=pW\boldsymbol p=\boldsymbol p_0=\boldsymbol p_M=\boldsymbol p_W is the common probability vector.

Fixing one outcome-independent ordering and matching equal positions gives triples Zi=(C0i,CMi,CWi)T\boldsymbol Z_i=(C_{0i},C_{Mi},C_{Wi})^{\mathsf T}. With k(c,c′)=1c=c′k(c,c')=\mathbf1\\{c=c'\\}, we use h=(h0M,h0W,hMW)T\boldsymbol h=(h_{0M},h_{0W},h_{MW})^{\mathsf T}, where

hab(z,z′)=k(ca,ca′)+k(cb,cb′)−k(ca,cb′)−k(cb,ca′).h_{ab}(\boldsymbol z,\boldsymbol z')=k(c_a,c'_a)+k(c_b,c'_b)-k(c_a,c'_b)-k(c_b,c'_a).

Each coordinate targets ∣pa−pb∣22\\|\boldsymbol p_a-\boldsymbol p_b\\|_2^2. Under H0H_0, the kernel is exactly canonical, its fourth moment is bounded, and its covariance is Ω=v(3I3+11T)\boldsymbol\Omega=v(3\boldsymbol I_3+\boldsymbol1\boldsymbol1^{\mathsf T}), where v=tr⁡(diag⁡(p)−ppT)2>0v=\operatorname{tr}\\{(\operatorname{diag}(\boldsymbol p)-\boldsymbol p\boldsymbol p^{\mathsf T})^2\\} > 0 whenever p\boldsymbol p is not a point mass. We treat customers as independent.

Following the vector construction in Section 4, define the row averages Yi=(i−1)−1∑j<ih(Zi,Zj)\boldsymbol Y_i=(i-1)^{-1}\sum_{j < i}\boldsymbol h(\boldsymbol Z_i,\boldsymbol Z_j) and

U~n=1n−1∑i=2nYi,Ω^n=1Tn∑i=2n(Yi−U~n)(Yi−U~n)T,Tn=∑j=1n−11j.\widetilde{\boldsymbol U}_n=\frac1{n-1}\sum_{i=2}^n\boldsymbol Y_i,\qquad\widehat{\boldsymbol\Omega}_n=\frac1{T_n}\sum_{i=2}^n(\boldsymbol Y_i-\widetilde{\boldsymbol U}_n)(\boldsymbol Y_i-\widetilde{\boldsymbol U}_n)^{\mathsf T},\qquad T_n=\sum_{j=1}^{n-1}\frac1j.

VEC-GM rejects at the first n≥mn\ge m for which

(n−1)2U~nTΩ^n−1U~n>(Tn+Tm)3log⁡(1+Tn/Tm)+2log⁡(1/α),(n-1)^2\widetilde{\boldsymbol U}_n^{\mathsf T}\widehat{\boldsymbol\Omega}_n^{-1}\widetilde{\boldsymbol U}_n > (T_n+T_m)\\{3\log(1+T_n/T_m)+2\log(1/\alpha)\\},

with no rejection when Ω^n\widehat{\boldsymbol\Omega}_n is singular.

We analyze 18000 distinct customers per group in the prespecified ordering, with monitoring start m=100m=100. At α=0.05\alpha=0.05, VEC-GM rejects at n=1258n=1258 customers per group, using 3774 customers in total (Table 1). Thus we detect different response distributions well before exhausting the sample. We will add the Hillstrom application and its detection result to the revision.

Table 1. Hillstrom VEC-GM result for the single prespecified analysis sequence.

MethodStart mmLevelFirst rejection nnTotal customers used
VEC-GM1000.0512583774

W2. We compare our method with the quadratic multiplier bootstrap of Liu et al. (2026) (Boot-AVT and Boot-AVT-Multi), followed by the betting two-sample tests of Shekhar and Ramdas (2024) (SR) and the sequential independence test of Podkopaev et al. (2023) (SKIT). We will add these comparisons to Section 5 of the revision, with implementation details in the appendix.

Quadratic multiplier bootstrap We compare MG with Boot-AVT and Boot-AVT-Multi using B=500B=500 multipliers, c=0.01c=0.01 and the same standardized component kernels. Boot-AVT-Multi’s empirical type-I error exceeds the nominal level across the tested vector null models and monitoring starts (Table 2). Boot-AVT also requires more computation than MG-GM in the MMD, HSIC and three-sample experiments (Table 3). Timings use ten paths per model (five null and five alternative), all prefixes through N=2000N=2000.

Table 2. Empirical type-I error (%) of Boot-AVT-Multi at nominal level 5%, monitoring through N=2000N=2000.

Modelm=20m=20m=30m=30m=40m=40
Three-sample12.5010.208.75
Gaussian product12.9511.059.35
t5t_5 product13.4011.459.95

Table 3. Mean computation time in seconds for all prefixes through N=2000N=2000.

ModelMG-GMBoot-AVTBoot-AVT/MG-GM
MMD0.2750.7262.64
HSIC0.2530.7132.81
Three-sample1.0352.9592.86

The SR and SKIT experiments use α=0.05\alpha=0.05, N=2000N=2000 and shared observation streams, with m=400m=400 for the main comparisons. SR-ERM-ONS uses the normalized empirical witness and online Newton step (ONS) bets; SR-tanh-ONS uses historical-maximum normalization and a tanh⁡\tanh payoff.

Energy-distance two-sample tests: MG versus SR. We use the unbounded canonical kernel h((x,y),(x′,y′))=∣x−y′∣+∣x′−y∣−∣x−x′∣−∣y−y′∣h\bigl((x,y),(x',y')\bigr)=|x-y'|+|x'-y|-|x-x'|-|y-y'| under H0:PX=PYH_0:P_X=P_Y. The settings are Gamma mean changes (X∼Gamma⁡(2,0.5)X\sim\operatorname{Gamma}(2,0.5), Y∼Gamma⁡(2,μ/2)Y\sim\operatorname{Gamma}(2,\mu/2)), equal-mean Gamma shape changes (Y∼Gamma⁡(k,1/k)Y\sim\operatorname{Gamma}(k,1/k)), and t6t_6 location changes (X∼t6X\sim t_6, Y∼t6+δY\sim t_6+\delta). All parameters were fixed before simulation. Alongside SR-tanh-ONS, SR-mix-ONS averages three ONS wealth processes with payoffs tanh⁡(ai/s)\tanh(a_i/s), s∈0.25,1,4s\in\\{0.25,1,4\\}, where aia_i is the current kernel row average. This mixture checks normalization sensitivity within the same SR framework. Both SR implementations preserve their finite-sample null guarantee under equality of the two laws.

MG has higher power and shorter capped stopping times for moderate mean and location changes. For shape changes, SR-mix can match or exceed MG’s power even when MG stops sooner (Table 4).

Table 4. Representative energy-distance comparison at α=0.05\alpha=0.05, m=400m=400 and N=2000N=2000 pairs. Rows with μ=1\mu=1 or δ=0\delta=0 report null rejection rather than power.

SettingMG rejectionSR-tanh rejectionSR-mix rejectionMG time (pairs)SR-tanh time (pairs)SR-mix time (pairs)
Gamma mean change: μ=1\mu=10.01130.00700.00401986.71992.41996.3
Gamma mean change: μ=1.05\mu=1.050.15440.08760.07081869.01929.61945.8
Gamma mean change: μ=1.1\mu=1.10.75280.63260.61321287.21479.41514.6
Gamma mean change: μ=1.15\mu=1.150.99040.97000.9814701.3851.2852.9
Gamma shape change at equal means: k=1.5k=1.50.67180.56620.67621480.51607.51541.8
Gamma shape change at equal means: k=3k=30.98660.94280.9954849.21011.8885.9
Student t6t_6 location change: δ=0\delta=00.01130.00400.00441986.71996.11995.4
Student t6t_6 location change: δ=0.1\delta=0.10.30660.19900.18561737.71846.71858.5
Student t6t_6 location change: δ=0.2\delta=0.20.97680.93700.9548816.5977.6962.1

Binary-response two-sample tests: MG versus SR. For independent X∼Bernoulli⁡(0.5)X\sim\operatorname{Bernoulli}(0.5) and Y∼Bernoulli⁡(q)Y\sim\operatorname{Bernoulli}(q), both methods use k(x,y)=1x=yk(x,y)=\mathbf1\\{x=y\\}, giving the bounded canonical MMD kernel h((x,y),(x′,y′))=2(x−y)(x′−y′)h((x,y),(x',y'))=2(x-y)(x'-y'). We fixed q∈0.50,0.52,0.53,…,0.60q\in\\{0.50,0.52,0.53,\ldots,0.60\\}.

MG and SR-ERM-ONS have comparable power, with modest MG gains at intermediate signals. MG also has a lower empirical null rejection rate in this experiment (Table 5). Together with the energy-distance comparison, these results show that the ranking depends on the distribution and signal.

Table 5. Binary-response comparison with the same monitoring start m=400m=400

qqMG powerSR powerMG timeSR time
0.520.04440.04721958.21951.9
0.540.25050.23601785.51792.9
0.560.67990.65761368.01385.2
0.580.94960.9450916.9930.7
0.600.99790.9978633.6634.6

Gaussian independence tests: MG versus SKIT. MG-GM has higher power and shorter capped stopping time than mean-witness HSIC-SKIT-ONS in this setting. Both methods have empirical null rejection rates below the nominal level (Table 6).

Table 6. Additional population-centered HSIC results through N=2000N=2000.

MethodmmNull coveragePower (0.10)Power (0.15)Power (0.20)Capped time (0.15)
MG-GM200.9630.5100.9360.998895.0
MG-GM4000.9890.5380.9520.998914.0
MG-GM8000.9920.5440.9540.9981052.2
HSIC-SKIT-ONS200.9870.4040.8600.9901176.1
HSIC-SKIT-ONS4000.9880.4040.8600.9901180.2
HSIC-SKIT-ONS8000.9890.4000.8600.9901257.3

Thank you again for your valuable feedback. We hope our responses address your concerns and welcome any further questions or discussion.

References

Jixuan Liu, Long Feng, Liuhua Peng, and Zhaojun Wang. Boot-AVT: Asymptotically anytime-valid testing with degenerate U-statistics via bootstrap. arXiv preprint arXiv:2610.28931v1, 2026. arXiv:2610.28931v1.

Shubhanshu Shekhar and Aaditya Ramdas. Nonparametric two-sample testing by betting. IEEE Transactions on Information Theory, 70(2):1178–1203, 2024. doi:10.1109/TIT.2023.3305867.

Aleksandr Podkopaev, Patrick Blöbaum, Shiva Kasiviswanathan, and Aaditya Ramdas. Sequential kernelized independence testing. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 27957–27993. PMLR, 2023.

Thanks for the clarifications and new numerical studies. I will keep my score.

Thank you for your time and consideration. We appreciate your careful evaluation of our clarifications and additional numerical results.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response and Summary of Revisions

We thank all reviewers for their careful reading and constructive comments. Your feedback has helped us clarify the scope of our theoretical guarantees, strengthen the empirical comparisons, and improve the presentation. In addition to the point-by-point responses, we have incorporated the clarifications and new results into the newly uploaded revision, with complete proofs and implementation details in the appendix. New material addressing the reviewers' concerns is highlighted in blue.

Quantitative guarantees. We derive explicit infinite-horizon error bounds for the scalar and vector GM and LIL procedures under the original assumptions. These bounds quantify the asymptotic error and also imply the original time-uniform coverage guarantees. However, obtaining sharp error bounds that are informative at practical monitoring starts remains an open problem.

Application and method comparisons. We add a Hillstrom email experiment illustrating joint vector inference, together with comparisons against quadratic multiplier bootstrap, SR and SKIT. The results show lower computation time than the tested bootstrap and differing power advantages across settings. We clarify the methods’ respective scope and the distinction between our asymptotic guarantees and the nonasymptotic guarantees of SR and SKIT.

Boundary calibration and monitoring start. Deterministic tuning improves vector LIL power, although it remains conservative in the tested setting. Sensitivity analysis shows broadly similar MG-GM coverage and power across the tested starts in the Gaussian experiments, supporting the interpretation of mm as a prespecified design choice informed by the data-generating mechanism and study context.

We hope that these revisions, together with our detailed responses, address the reviewers' concerns and improve the clarity and completeness of the paper. Thank you again for your time and valuable feedback.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.