Recent Advances in Algorithmic High-Dimensional Robust Statistics

Ilias Diakonikolas; Daniel M. Kane

Source-linked AI summary

Recent Advances in Algorithmic High-Dimensional Robust Statistics

Ilias Diakonikolas, Daniel M. Kane

arXiv:1911.05911v1Nov 14, 2019cs.DScs.CCmath.STstat.ML

TL;DR

High-dimensional robust estimation must withstand contamination that defeats classical estimators, yet efficient methods were long unavailable. The survey unifies filtering and related algorithmic ideas around robust mean estimation and reviews broader robust-learning advances. It presents efficient robust estimators, while identifying computational limits and remaining scope boundaries.

Problem
High-dimensional robust estimation needs efficient methods because classical estimators can be highly sensitive to outliers, while many robust alternatives are computationally hard.
Method
The survey develops a unified presentation of robust mean-estimation techniques, including covariance-based filtering, and overviews approaches for broader statistical tasks.
Results
The surveyed developments include efficient robust estimators for high-dimensional mean and covariance estimation, including an O(ǫ)-error Gaussian mean estimator with polynomial-in-n and 2^d runtime.
Takeaways & Limitations
The article frames algorithmic robust statistics as an emerging area with core techniques applicable across high-dimensional estimation tasks.
Takeaways & Limitations
The filtering algorithm can require Ω(d) iterations on constructed instances, despite often running in a small constant number of iterations in practice.

Abstract

from arXiv · show

Learning in the presence of outliers is a fundamental problem in statistics. Until recently, all known efficient unsupervised learning algorithms were very sensitive to outliers in high dimensions. In particular, even for the task of robust mean estimation under natural distributional assumptions, no efficient algorithm was known. Recent work in theoretical computer science gave the first efficient robust estimators for a number of fundamental statistical tasks, including mean and covariance estimation. Since then, there has been a flurry of research activity on algorithmic high-dimensional robust estimation in a range of settings. In this survey article, we introduce the core ideas and algorithmic techniques in the emerging area of algorithmic high-dimensional robust statistics with a focus on robust mean estimation. We also provide an overview of the approaches that have led to computationally efficient robust estimators for a range of broader statistical tasks and discuss new directions and opportunities for future work.

1 Introduction

High-dimensional robust estimation addresses contamination that can arbitrarily damage classical estimators, while recent work has produced efficient algorithms with near-optimal guarantees under several distributional assumptions.

Motivation: The empirical mean is optimal for clean spherical Gaussian samples but can be arbitrarily compromised by even one outlier.For n samples from N(µ, I), its ℓ2-error is O(√(d/n)) with high probability.
Motivation: Robust estimation matters because natural data contamination and poisoning attacks can substantially degrade downstream analyses and learned models.
Computational challenge: Classical robust estimators achieve statistical guarantees, but many are computationally intractable or degrade as dimension grows.The Tukey median is NP-hard to compute in general, and similar hardness results apply to essentially all known classical estimators.
Recent progress: Recent work gave the first polynomial-time robust estimators for high-dimensional mean and covariance estimation with dimension-independent error guarantees.These developments initiated efficient algorithmic approaches to high-dimensional robust statistics.
Statistical limits: Contamination imposes an information-theoretic error floor, including Ω(ǫ) for Gaussian mean estimation and larger bounds for broader distribution classes.For subgaussian identity-covariance distributions and bounded-covariance distributions, the supported lower bounds scale with ǫ√log(1/ǫ) and √ǫ, respectively.
Statistical limits: For spherical Gaussian mean estimation, an algorithm achieves O(ǫ) ℓ2-error using n = Ω((d + log(1/τ))/ǫ2) samples with probability at least 1 −τ.The stated runtime is polynomial in n and 2^d.

2 High-Dimensional Robust Mean Estimation

This section presents a unified, intuition-focused treatment of algorithmic techniques for robust mean estimation, emphasizing polynomial-time methods and their shared structure.

Scope: The section explains the main insights and connections behind recent robust high-dimensional learning algorithms through robust mean estimation.The presentation is simplified and unified rather than a full complexity optimization.
Problem: Robust mean estimation seeks a small ℓ2-error approximation to the mean from an ǫ-corrupted sample set drawn from a suitably well-behaved distribution family.Typical assumptions constrain moments or concentration properties.
Structure: The section is organized around intuition, stability conditions, convex programming, and iterative filtering.

2.1 Key Difficulties and High-Level Intuition

High-dimensional outliers may be indistinguishable individually yet collectively shift the mean, so robust algorithms target consequential outliers through anomalous variance directions.

Key difficulty: Individual outliers cannot generally be identified without risking removal of inliers, even when they significantly move the mean.Naive pruning of only visibly extreme points therefore need not provide non-trivial error guarantees.
Key difficulty: An ǫ-fraction of outliers placed in one direction can shift the empirical mean substantially, whereas random-direction effects may cancel.
High-level intuition: Robust estimation need only detect consequential outliers that significantly affect the estimate, rather than identify every outlier.
High-level intuition: If outliers shift the mean by δ along a direction v, they contribute at least δ2/ǫ to the variance in that direction.The top eigenvector of the sample covariance efficiently detects such abnormally large variance.
Algorithmic template: The algorithmic template computes the largest covariance eigenvalue: bounded variance certifies a close empirical mean, while excess variance identifies a direction for outlier handling.

2.2 Good Sets and Stability

Stability formalizes when large subsets of clean samples retain accurate means and controlled directional variances, enabling covariance-based certificates and robust algorithms.

Stability condition: A stable clean sample set must support correctness after any ǫ-fraction corruption, and such sets occur with high probability at sufficient sample sizes.
Stability condition: Stability requires every sufficiently large subset of clean samples to have mean near the population mean and variance near the nominal value in every direction.For identity covariance, the directional variance is constrained to 1 ± δ2/ǫ.
Examples: For identity-covariance subgaussian distributions, Ω(d/ǫ2) samples suffice for (ǫ, O(ǫ))-stability with high probability.
Examples: Subgaussian tail control yields stability because removing an ǫ-tail changes a projection mean by O(ǫ√log(1/ǫ)) and tail-square mass by O(ǫ log(1/ǫ)).A covering argument extends the fixed-direction analysis to all directions.
Algorithmic role: Filtering and related algorithms exploit stability, while some methods require additional conditions beyond it.A weighted analogue shows that a distribution close to the clean uniform distribution with bounded covariance has a mean close to the target.
Certificate: If a corrupted sample has largest covariance eigenvalue at most 1 + λ, its empirical mean is close to the true mean by Lemma 2.4.The certificate applies to an ǫ-corrupted version of an (ǫ, δ)-stable set.

2.3 The Unknown Convex Programming Method

The unknown convex programming method searches for a distribution in a convex set whose covariance has no large eigenvalues, using separation oracles when variance is excessive. The resulting ellipsoid-based algorithm gives efficient robust mean estimation under stability, with applications to several covariance and concentration settings.

Convex-programming formulation: A distribution with bounded covariance can be found by treating excessive directional variance as a separating hyperplane against the target distribution.Although variance is not linear in the distribution, a high-variance direction yields a linear separation oracle.
General guarantee: Theorem 2.7 gives a polynomial-time estimator with ℓ2-error O(δ) for an ǫ-corrupted version of a (3ǫ, δ)-stable set.
Concrete applications: For identity-covariance sub-gaussian distributions, the method uses ˜Ω(d/ǫ2) samples and achieves robust mean error O(ǫ).
Concrete applications: Under identity covariance and sub-exponential directional concentration, the robust mean error is O(ǫ log(1/ǫ)), while bounded k-th central moments yield O(ǫ1−1/k).Both bounds are information-theoretically optimal within constant factors.
Concrete applications: For unknown covariance bounded by σ2I, the method extends through Proposition 2.3 to corrupted samples requiring ˜Ω(d/ǫ) observations.

2.4 The Filtering Method

Filtering repeatedly removes points exposed by a large-variance direction, using concentration or randomized weighting to make progress toward a low-covariance inlier set. Basic filtering needs tail control, while universal randomized filtering works under stability alone.

Basic filtering: Filtering either accepts the weighted empirical mean when covariance is bounded or identifies a high-variance direction whose projections distinguish outliers from inliers.The method removes points far from the sample mean in that direction, with implementation choices affecting the analysis.
Basic filtering: Basic filtering is efficient for identity or known-covariance distributions with suitable univariate tail bounds and extends beyond Gaussian concentration.The stated extensions include sub-exponential and inverse-polynomial concentration.
Basic filtering: Tail-bound-goodness is an additional condition ensuring that filtering removes more outliers than inliers; sufficiently large i.i.d. Gaussian samples satisfy it with high probability.
Basic filtering: When variance is excessive, an efficient filtering step can remove a subset containing fewer than one-third inliers, and iterating this produces a less noisy sample set.
Randomized filtering: Randomized filtering uses a nonnegative function to remove points probabilistically, and its progress analysis yields a 2/3-probability robust mean guarantee.The progress measure is a sub-martingale, and bounded progress preserves enough inliers for the final low-variance estimate.
Randomized filtering: Randomized filtering can have occasional worse outcomes while also producing correspondingly better outcomes, and experiments found typically few iterations on poisoned real datasets.
Universal filtering: Universal randomized filtering constructs an efficient filter under stability alone, without the basic filter’s tail-bound condition.Proposition 2.13 applies when the covariance’s largest eigenvalue exceeds 1+8δ2/ǫ.

2.5 Bibliographic Notes

The survey places convex programming and filtering within the broader development of algorithmic robust statistics, tracing their origins, related techniques, and extensions beyond robust mean estimation. It also contrasts their guarantees across contamination models and records applications to other statistical tasks.

Origins: Convex programming and filtering appeared in earlier work, while top-eigenvector outlier removal traces back to learning linear separators with malicious noise.
Related approaches: A recursive dimension-halving method achieved Gaussian robust mean error O(ǫ log d) in Huber’s contamination model.
Broader tasks: Robust estimation techniques were extended to density estimation, independent component analysis, singular value decomposition, and Bayesian-network parameter estimation.
Contamination models: For spherical Gaussians, filtering gives O(ǫ log(1/ǫ)) error under strong contamination, whereas additive contamination admits the optimal O(ǫ) error via a more sophisticated filter.
Computational limits: Improving the O(ǫ log(1/ǫ)) strong-contamination error was shown to require super-polynomial time in the Statistical Query model.

3 Beyond Robust Mean Estimation

Robust mean estimation techniques serve as primitives for efficient robust stochastic optimization and broader estimation tasks. The survey describes filtering-based extensions to covariance, Gaussian, sparse, and list-decodable mean estimation, while identifying computational and sample-complexity trade-offs.

Robust stochastic optimization: Any efficient robust mean estimator can serve as a black-box primitive for efficient robust machine-learning tasks expressed as stochastic optimization.The section presents robust mean estimation as a reusable algorithmic component.
Robust stochastic optimization: An alternative robust optimization method combines approximate empirical risk minimization with filtering and invokes filtering only near an approximate critical point.This approach requires only black-box access to an approximate ERM.
Robust covariance estimation: Robust covariance estimation reduces centered covariance estimation to robust mean estimation of Y = XXT and filters points using the empirical fourth moment tensor.For Gaussian data, the described algorithm achieves Mahalanobis error O(ǫ log(1/ǫ)), within a logarithmic factor of the Θ(ǫ) information-theoretic optimum.
Robust covariance estimation: Iterating the covariance-filtering technique yields Mahalanobis error O(ǫ log(1/ǫ)) and enables robust learning of an unknown-mean, unknown-covariance Gaussian within total variation distance O(ǫ log(1/ǫ)).The Gaussian-learning procedure first estimates covariance, then estimates the mean using the approximately known covariance.
Open problems and trade-offs: The survey also highlights trade-offs: sparse filtering can require Ω(k2 log(d)/ǫ2) samples, while faster robust covariance algorithms and optimal-error methods remain active challenges.A faster general robust stochastic-optimization algorithm with optimal sample complexity and minimal ERM-oracle queries is posed as an open problem.
List-decodable learning: List-decodable filtering outputs polynomially many hypotheses with at least one near the true mean, using multi-filters unless the projected variance is small.The procedure addresses settings where the clean samples are a minority and a single outlier-removal decision cannot identify the correct cluster.

4 Conclusions

The article surveys recent algorithmic advances in high-dimensional robust statistics while arguing that substantial progress still leaves broad opportunities for a general theory of robust estimation.

4 Conclusions: The survey reviews recent developments in algorithmic high-dimensional robust statistics and identifies general algorithmic theory as a major goal.Future work includes efficient estimators for broader models and tasks, deeper computational-limit analysis, connections to non-convex optimization and privacy, and applications.
4 Conclusions: Classical robust statistics challenged traditional assumptions about data generation and developed methods stable to deviations from those assumptions.The precise form of deviation depends on the setting and produces different robustness models.