Robust Estimators in High Dimensions without the Computational Intractability

We study high-dimensional distribution learning in an agnostic setting where\nan adversary is allowed to arbitrarily corrupt an $\\varepsilon$-fraction of the\nsamples. Such questions have a rich history spanning statistics, machine\nlearning and theoretical computer science. Even in the most basic settings, the\nonly known approaches are either computationally inefficient or lose\ndimension-dependent factors in their error guarantees. This raises the\nfollowing question:Is high-dimensional agnostic distribution learning even\npossible, algorithmically?\n In this work, we obtain the first computationally efficient algorithms with\ndimension-independent error guarantees for agnostically learning several\nfundamental classes of high-dimensional distributions: (1) a single Gaussian,\n(2) a product distribution on the hypercube, (3) mixtures of two product\ndistributions (under a natural balancedness condition), and (4) mixtures of\nspherical Gaussians. Our algorithms achieve error that is independent of the\ndimension, and in many cases scales nearly-linearly with the fraction of\nadversarially corrupted samples. Moreover, we develop a general recipe for\ndetecting and correcting corruptions in high-dimensions, that may be applicable\nto many other problems.\n

Paper

Similar papers

© 2026 NYSGPT2525 LLC