Research map / Learning theory and algorithms / Sample complexity

Asymptotic Anytime-Valid Inference for U-statistics

NeurIPS 2026 · Learning theory and algorithms › Sample complexity · approach: Distributed estimation under communication limits · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Builds asymptotic anytime-valid confidence sequences for degree-two U-statistics, covering nondegenerate (Gaussian boundary via Hoeffding projection plus jackknife variance) and degenerate (Gaussian-chaos SAGE boundary with plug-in spectral estimation) regimes.

Problem

Anytime-valid confidence sequences for U-statistics under continuous monitoring are lacking; the nondegenerate case needs time-uniform CLT-type control and the degenerate case requires calibrating a quadratic Gaussian chaos with unknown signed eigenvalues.

Approach

Reduce nondegenerate U-statistics to a Brownian partial-sum process via Hoeffding projection and a jackknife variance plug-in; for degenerate ones, allocate significance across spectral coordinates of a Gaussian chaos (SAGE boundary) with truncated empirical eigenvalues.

Key results

• Gini mean difference AsympCS under Gaussian, t10, Laplace keeps cumulative miscoverage below alpha=0.05 over horizon up to 10,000 while classical pointwise CIs lose coverage under continuous monitoring (500 replications).
• Degenerate MMD sequential test with SAGE boundaries keeps size near zero under H0 while classical chi-square-quantile rule's rejection rate accumulates beyond nominal alpha.
• Theoretical widths attain sqrt(log log n / n) in the nondegenerate regime and log log n / n in the degenerate regime.

Surprising findings

• The GM boundary (rate sqrt(log n/n)) gives sharper finite-sample intervals than the LIL boundary at moderate sample sizes for GMD.
• The AsympCS-GM miscoverage for sample variance under heavy tails slightly exceeds nominal alpha.

Limitations

• Theory restricted to scalar degree-two U-statistics; no vector/matrix extensions.
• Data-driven weights in simulations are random and lack rigorous time-uniform validity theory; cold-start and local degeneracy remain open.
• Algorithms require repeated eigendecompositions of n x n Gram matrices (O(n^3) per step).

Experimental setup

Metrics: empirical coverage cumulative miscoverage rate average half-width rejection rate / power size

Baselines: classical pointwise CIs classical MMD test with weighted chi-square critical values

Builds on: Hoeffding decomposition stitched LIL boundary Robbins Gaussian mixture boundary asymptotic anytime-valid inference framework

Closest papers by meaning

• How Accurately Can a Gaussian Approximate Stochastic Approximation Iterates? (NeurIPS 2026 · similarity 0.85)
• Statistical inference for Linear Stochastic Approximation with Markovian Noise (NeurIPS 2025 · similarity 0.85)
• Asymptotically Log-Optimal Bayes-Assisted Confidence Sequences for Bounded Means (NeurIPS 2026 · similarity 0.84)
• Non-asymptotic Error Bounds in $\mathcal{W}_2$-Distance with Sqrt(d) Dimension Dependence and First Order Convergence for Langevin Monte Carlo beyond Log-Concavity (ICML 2025 · similarity 0.84)
• The Collusion of Memory and Nonlinearity in Stochastic Approximation With Constant Stepsize (NeurIPS 2024 · similarity 0.84)
• Sub-Gaussian Confidence Intervals for Heavy-Tailed Data: Characterizing the Limits of Inference (NeurIPS 2026 · similarity 0.84)