在噪声中学习高维单纯形，揭示了样本复杂度的极限。
Fundamental Limits of Learning High-dimensional Simplices in Noisy Regimes
- 用压缩样本和傅里叶方法设计新算法，提升噪声下估计精度。
- 当信噪比≥√K时，噪声与无噪情形的样本需求量级相同。
- 适用于高维几何结构学习，尤其适合信号处理与统计推断研究者。
本文研究从噪声数据中学习高维单纯形的样本复杂度。考虑n个独立同分布样本，均匀来自ℝᴷ中未知单纯形，每个样本受均值为0、方差未知的高斯噪声污染。我们证明：存在一种算法，在高概率下输出的单纯形与真实单纯形的ℓ₂或总变差（TV）距离不超过ε，只要n ≥ (K²/ε²)·exp(𝒪(K/SNR²))，其中SNR为信噪比。扩展先前工作，我们推导出新的信息论下界：以TV距离ε估计单纯形至少需要n ≥ Ω(K³σ²/ε² + K/ε)个样本，σ²为噪声方差。在无噪情况下，下界n ≥ Ω(K/ε)与已知上界仅差常数因子。我们解决一个开放问题：当SNR ≥ Ω(√K)时，噪声情形的复杂度与无噪情形一致。分析中采用样本压缩技术（Ashtiani et al., 2018），并提出一种新颖的基于傅里叶的分布恢复方法，可能适用于更广泛的单纯形学习任务。
原文摘要 · Abstract (English)
In this paper, we establish sample complexity bounds for learning high-dimensional simplices in $\mathbb{R}^K$ from noisy data. Specifically, we consider $n$ i.i.d. samples uniformly drawn from an unknown simplex in $\mathbb{R}^K$, each corrupted by additive Gaussian noise of unknown variance. We prove an algorithm exists that, with high probability, outputs a simplex within $\ell_2$ or total variation (TV) distance at most $\varepsilon$ from the true simplex, provided $n \ge (K^2/\varepsilon^2) e^{\mathcal{O}(K/\mathrm{SNR}^2)}$, where $\mathrm{SNR}$ is the signal-to-noise ratio. Extending our prior work~\citep{saberi2023sample}, we derive new information-theoretic lower bounds, showing that simplex estimation within TV distance $\varepsilon$ requires at least $n \ge Ω(K^3 σ^2/\varepsilon^2 + K/\varepsilon)$ samples, where $σ^2$ denotes the noise variance. In the noiseless scenario, our lower bound $n \ge Ω(K/\varepsilon)$ matches known upper bounds up to constant factors. We resolve an open question by demonstrating that when $\mathrm{SNR} \ge Ω(K^{1/2})$, noisy-case complexity aligns with the noiseless case. Our analysis leverages sample compression techniques (Ashtiani et al., 2018) and introduces a novel Fourier-based method for recovering distributions from noisy observations, potentially applicable beyond simplex learning.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。