2024/10/24 by Mendelson, Shahar, Paouris, Grigoris, Vershynin, Roman · 1 citation
#60D05 #62G10 #FOS: Mathematics #G.3 #I.5.1 #Probability (math.PR) #Statistics Theory (math.ST)
paper · doi:10.48550/arxiv.2410.18880
The problem of detecting fake data inspires the following seemingly simple mathematical question. Sample a data point X from the standard normal distribution in ℝn. An adversary observes X and corrupts it by adding a vector rt, where they can choose any vector t from a fixed set T of the adversary's "tricks", and where r>0 is a fixed radius. The adversary's choice of t=t(X) may depend on the true data X. The adversary wants to hide the corruption by making the fake data X+rt statistically indistinguishable from the real data X. What is the largest radius r=r(T) for which the adversary can create an undetectable fake? We show that for highly symmetric sets T, the detectability radius r(T) is approximately twice the scaled Gaussian width of T. The upper bound actually holds for arbitrary sets T and generalizes to arbitrary, non-Gaussian distributions of real data X. The lower bound may fail for not highly symmetric T, but we conjecture that this problem can be solved by considering the focused version of the Gaussian width of T, which focuses on the most important directions of T.