Sample Complexity Bounds for Learning High-dimensional Simplices in Noisy Regimes
Jul 24, 2023
Speakers
Amir H. Saberi
Speaker · 0 followers
Amir Najafi
Speaker · 0 followers
Sayed Abolfazi Motahari
Speaker · 0 followers
Babak H. Khalaj
Speaker · 0 followers
About
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 ℝ^K, 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>Ω̃(K^2/ε^2)e^Ω(K/SNR^2) 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 <cit.>, 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.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 ℝ^K, 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).…
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
TGRL: An Algorithm for Teacher Guided Reinforcement Learning
Watch later
FLEX: an Adaptive Exploration Algorithm for Nonlinear Systems
Watch later
On the Convergence of SARSA with Linear Function Approximation
Watch later
A nonparametric extension of randomized response for private confidence sets
Watch later
Multi-Agent Learning from Learners
Watch later
