Research map / Learning theory and algorithms / Sample complexity

Mean Testing under Truncation beyond Gaussian

NeurIPS 2026 · Learning theory and algorithms › Sample complexity · approach: Learning under log-concave distributions · 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.

Characterizes high-dimensional mean testing under unknown arbitrary truncation: a finite-moment bias floor O(nu_p eps^{1-1/p}) with a U-statistic test, and an improved O(eps) bias floor under directional median regularity that yields Theta(d) estimation but sqrt(d)-rate testing.

Problem

Mean testing (H0: mean 0 vs ||mean||>=alpha) from samples of a truncated distribution P(.|S) where S hides up to an eps-fraction of mass, under only finite directional moments or median-regularity assumptions.

Approach

Truncation bias under finite p-th directional moments is O(nu_p eps^{1-1/p}), which sets an information-theoretic detectability floor; a simple order-2 U-statistic of inner products achieves sqrt(d) sample complexity above that floor, and a directional median regularity assumption reduces bias to linear O(eps), enabling testing with Theta(d) samples via a median-based estimator.

Key results

• Mean shift under truncation bounded by 2 nu_{P,p} eps^{1-1/p}; a U-statistic test succeeds with n = O(||Sigma_P|| sqrt(d)/(alpha-2gamma)^2) for alpha > 2gamma.
• Impossibility: for alpha <= C nu_{P,p} eps^{1-1/p} there exist indistinguishable P and P_0 under truncation, even with infinite samples.
• Under directional median regularity, truncation bias is O(eps/c) and a median-based estimator needs n = Theta(d) samples for O(eps) accuracy; testing achieves Theta(d) samples when eps < min(cr, alpha/8c).

Surprising findings

• Median-regular testing needs Theta(d) samples rather than sqrt(d), an intermediate learning-hard regime.
• Under finite p-th moments alone, testing is information-theoretically impossible below the bias floor regardless of sample size.

Limitations

• Results are theoretical; no experiments are reported.
• Median-regular testing sample complexity is Theta(d), not the sqrt(d) rate, for the structural regime.
• Some proof steps are sketchy (e.g., testing amplification proof sketch, inconsistent constants between alpha/2 and 2gamma thresholds).

Experimental setup

Metrics: sample complexity detectability floor

Baselines: Gaussian mean testing under truncation (prior work)

Builds on: U-statistics Efron-Stein inequality Chebyshev inequality

Closest papers by meaning

• Efficient Learning of Truncated Boolean Product Distributions: Influence to the Rescue (NeurIPS 2026 · similarity 0.85)
• Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination (ICML 2025 · similarity 0.84)
• Private Statistical Estimation via Truncation (NeurIPS 2025 · similarity 0.84)
• Sub-Gaussian Confidence Intervals for Heavy-Tailed Data: Characterizing the Limits of Inference (NeurIPS 2026 · similarity 0.83)
• Tolerant Algorithms for Learning with Arbitrary Covariate Shift (NeurIPS 2024 · similarity 0.83)
• A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplers (NeurIPS 2024 · similarity 0.83)