[edit]
Sample Complexity Bounds for Learning High-dimensional Simplices in Noisy Regimes
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:29514-29541, 2023.
Abstract
In this paper, we propose sample complexity bounds for learning a simplex from noisy samples. A dataset of size n is given which includes i.i.d. samples drawn from a uniform distribution over an unknown arbitrary simplex in RK, where samples are assumed to be corrupted by a multi-variate additive Gaussian noise of an arbitrary magnitude. We prove the existence of an algorithm that with high probability outputs a simplex having a ℓ2 distance of at most ε from the true simplex (for any ε>0). Also, we theoretically show that in order to achieve this bound, it is sufficient to have n≥˜Ω(K2/ε2)eΩ(K/SNR2) samples, where SNR stands for the signal-to-noise ratio and is defined as the ratio of the maximum component-wise standard deviation of the simplex (signal) to that of the noise vector. This result solves an important open problem in this area of research, and shows as long as SNR≥Ω(√K) the sample complexity of the noisy regime has the same order to that of the noiseless case. Our proofs are a combination of the so-called sample compression technique in (Ashtiani et al., 2018), mathematical tools from high-dimensional geometry, and Fourier analysis. In particular, we have proposed a general Fourier-based technique for recovery of a more general class of distribution families from additive Gaussian noise, which can be further used in a variety of other related problems.