Optimal Sub-Gaussian Mean Estimation in Very High Dimensions
summary
Linear time algorithm that is sample optimal up to a 1+o(1) factor for very high dimensions where effective dimension >> (log 1/delta)^2. Main tool is a new vector Bernstein inequality showing bounded independent vectors concentrate on a spherical shell with tail roughly exp(−Ω(gamma^2 · deff)). Algorithm estimates a center by coordinate-wise median of means, throws out O((log 1/delta)^2) farthest samples, returns the mean of the rest, and achieves the claimed bounds with matching lower bounds in large portions of the parameter space.
AI-written summary · about