Source-linked AI summary
Being Robust (in High Dimensions) Can Be Practical
Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart
TL;DR
High-dimensional robust estimation has faced a trade-off between computational practicality, sample complexity, and corruption tolerance. This paper refines filtering-based estimators to obtain near-optimal sample bounds, improve empirical corruption tolerance, and retain guarantees across broader distributions. Experiments show strong performance, including error close to that of uncorrupted empirical means and scalability to hundreds of dimensions.
Problem
High-dimensional robust estimation is difficult because existing methods are often computationally intractable or require prohibitively large sample and running-time complexity.
Method
The paper refines filtering-based robust estimators with near-optimal sample-complexity analysis and empirically tuned thresholds for removing corrupted points.
Results
The estimators achieve eO(d/ε2) samples for mean estimation with known covariance and eO(d2/ε2) for covariance estimation, with bounds optimal up to logarithmic factors.
Takeaways & Limitations
The algorithms provide practical high-dimensional robust estimation, with sub-Gaussian guarantees and empirical error nearly indistinguishable from uncorrupted sample noise across hundreds of dimensions.
Takeaways & Limitations
On semi-synthetic data, the filter removed some true points from sparsely represented regions, such as Turkey, treating them as outliers.
Abstract
from arXiv · showhide
Robust estimation is much more challenging in high dimensions than it is in one dimension: Most techniques either lead to intractable optimization problems or estimators that can tolerate only a tiny fraction of errors. Recent work in theoretical computer science has shown that, in appropriate distributional models, it is possible to robustly estimate the mean and covariance with polynomial time algorithms that can tolerate a constant fraction of corruptions, independent of the dimension. However, the sample and time complexity of these algorithms is prohibitively large for high-dimensional applications. In this work, we address both of these issues by establishing sample complexity bounds that are optimal, up to logarithmic factors, as well as giving various refinements that allow the algorithms to tolerate a much larger fraction of corruptions. Finally, we show on both synthetic and real data that our algorithms have state-of-the-art performance and suddenly make high-dimensional robust estimation a realistic possibility.
1 Introduction
High-dimensional robust estimation faces a tension between robustness and computational efficiency. This paper develops practical, provably robust estimators with near-optimal sample complexity, improved corruption tolerance, broader distributional guarantees, and strong empirical performance.
- 1 Introduction: In high dimensions, robust estimators such as the Tukey median and minimum volume ellipsoid are difficult to compute, while computational heuristics degrade as dimension grows.The paper contrasts these methods with the one-dimensional setting, where robust alternatives are straightforward to compute.
- 1 Introduction: The paper targets practical, provably robust mean and covariance estimators that work in high dimensions.The stated goal is to make robust statistics’ promise of protection from substantial bias by noisy samples closer to reality.
- 1.2 Our Results: Existing efficient robust algorithms have prohibitively large sample complexity and running time for high-dimensional applications.The paper notes that the required samples could be too numerous to store while still obtaining accurate estimates.
- 1.2 Our Results: eO(d/ε2) samples suffice for mean estimation with known covariance, while covariance estimation requires eO(d2/ε2) samples; both bounds are optimal up to logarithmic factors.These are sample-complexity bounds for the filtering-based algorithm.
- 1.2 Our Results: The paper increases the tolerable fraction of adversarial corruptions by empirically tuning point-removal thresholds, addressing conservative behavior in earlier algorithms.The refinements are motivated by cases where a naive implementation removed no outliers in realistic scenarios.
- 1.2 Our Results: The same error guarantees extend to sub-Gaussian distributions, and experiments show algorithms scaling to hundreds of dimensions with error nearly indistinguishable from sample noise.The paper also reports strong performance across synthetic and real-world data.
2 Formal Framework
The framework models robust estimation under an adaptive contamination process and evaluates mean and covariance recovery with Euclidean and affine-invariant Mahalanobis distances.
- 2 Formal Framework: The notation distinguishes Euclidean norm for vectors from spectral and Frobenius norms for matrices, and represents uniform sampling from an empirical distribution.These conventions support the formal definitions and guarantees that follow.
- 2 Formal Framework: The robust-estimation model allows an adversary to inspect generated samples, remove some, and replace them with arbitrary corruptions.The number of corrupted samples is governed marginally by a Bin(ε, m) distribution, while the adversary may depend on the observed sample set.
- 2 Formal Framework: Unlike Huber’s contamination model, this adversary may both add corrupted points and delete uncorrupted points after inspecting the samples.The framework therefore permits sample-dependent contamination rather than only oblivious additions.
- 2 Formal Framework: Mean error is measured by Euclidean distance, while covariance error uses the affine-invariant Mahalanobis distance ∥Σ^-1/2Σ̂Σ^-1/2 − I∥F.The covariance metric is strong and implies corresponding total-variation bounds.
- 2 Formal Framework: A sample set is called ε-corrupted when it is generated by the contamination process specified in Definition 2.1.This terminology identifies the input condition used by the formal guarantees.
3 Nearly Sample-Optimal Efficient Robust Learning
The paper develops efficient filtering-based estimators for high-dimensional means and covariances with near sample-optimal guarantees under several distributional assumptions. The results retain robustness while extending beyond Gaussian models, including bounded-second-moment settings.
- Contributions: Filtering yields sample-optimal bounds up to logarithmic factors for both robust mean and covariance estimation.The approach uses spectral methods and tail violations rather than the convex programming methods that hinder practical implementation.
- Sub-gaussian mean estimation: Ω((d/ε2) poly log(d/ε)) samples suffice for sub-gaussian mean estimation with error O(ε).The efficient algorithm succeeds with probability at least 9/10 for identity covariance and ν = Θ(1).
- Bounded second moments: Θ((d/ε) log d) samples suffice under bounded second moments, achieving mean error O(√εσ).The guarantee applies when the unknown covariance satisfies ΣP ⪯ σ2I and succeeds with probability 9/10.
- Distributional robustness: The same error bounds continue to hold for sub-Gaussian distributions, and filtering extends to weaker assumptions while retaining near-optimal sample and error guarantees.The paper also identifies the bounded-second-moment mean result as optimal up to a logarithmic factor in sample size and up to a constant factor in error.
- Covariance estimation: For Gaussian covariance estimation, Ω((d2/ε2) poly log(d/ε)) samples yield Mahalanobis error O(ε log(1/ε)) with probability at least 9/10.The estimator returns a Gaussian covariance estimate under ε-corruption.
4 Filtering
The filtering framework iteratively detects anomalous projections or higher-moment deviations and removes points violating suitable tail bounds. Practical refinements replace vulnerable univariate centering and adapt tail strictness to dimension and observed rejection rates.
- Filter components: Thres(ε) terminates filtering when the covariance spectral norm is sufficiently bounded, while Tail identifies projected deviations that indicate corrupted points.The slack function δ(ε, s) is included for technical reasons.
- Filter template: The filter computes empirical covariance, checks its spectral norm, and either returns the empirical mean or removes points violating a projected tail bound.When the covariance norm is too large, filtering proceeds along its top eigenvector.
- Covariance filtering: For robust covariance estimation, the filter detects excessive empirical variance of a normalized degree-2 polynomial using fourth-moment information.This generalizes the use of degree-2 information for detecting outliers in mean estimation.
- Better Univariate Tests: Replacing projected empirical-mean centering with the median reduces constant-factor degradation and improves error in practice.The median is robust for symmetric distributions and can be optimal under certain models.
- Tail-bound tuning: In empirical covariance experiments, the dominant tail term was C1 exp(−C2T), so optimization focused on that term rather than Tail2.The tail bound is written as C1 exp(−C2T) + Tail2(T, d, ε, δ, τ).
- Adaptive Tail Bounding: The adaptive tail-bounding heuristic binary-searches C2 until filtering rejects roughly an ε-fraction of points, using ε/2 to 3ε/2 as the stopping range.The authors report that this substantially improves accuracy and scales smoothly from low to high dimensions.
5 Experiments
Experiments on synthetic, semi-synthetic, and real-derived data show that the filtering algorithm achieves the strongest statistical accuracy among tested methods, often approaching the uncorrupted-data benchmark. The results also suggest near-optimal sample complexity, while the covariance experiments were limited by memory and sample size.
- Synthetic Data: Our algorithm consistently achieved the smallest error across the synthetic trials.The evaluation prioritized statistical accuracy rather than time efficiency.
- Synthetic Data: 4 orders of magnitude smaller excess error was achieved by our covariance estimator than LRVCov’s in high dimensions.The comparison used excess Mahalanobis error relative to the noiseless sample covariance benchmark.
- Synthetic Data: Our algorithm’s mean-estimation error remained nearly identical to the empirical mean of the uncorrupted samples as dimension increased.Other methods’ errors diverged with dimension across the tested nontrivial noise distributions.
- Synthetic Data: The covariance experiments used lower dimensions and fewer samples because fourth-moment objects caused memory limitations.This limits direct comparison with the higher-dimensional unknown-mean experiments.
- Discussion: The experiments suggest that the algorithm’s near-zero excess error and agreement with noiseless rates make its sample complexity close to optimal.The discussion attributes the small gap to often-small or absent constants and logarithmic factors in the recovery guarantee.
- Semi-synthetic Data: The semi-synthetic genetic-data experiment mostly recovered Europe despite added noise, whereas naive methods did not.The data were projected to 20 dimensions before noise was added.
A.1 Robust Mean Estimation for Sub-Gaussian Distributions
This section extends filtering-based robust mean estimation to sub-Gaussian distributions and establishes near sample-optimal guarantees. The proof uses a modified good-sample definition, concentration of uncorrupted samples, and an iterative filtering procedure.
- A.1 Robust Mean Estimation for Sub-Gaussian Distributions: The filter technique yields a near sample-optimal, computationally efficient estimator for the mean of a sub-Gaussian density with known covariance.This establishes Theorem 3.1.
- Proof Strategy: The analysis reuses the Gaussian filtering proof with a weaker good-set definition and a concentration argument for sub-Gaussian samples.The resulting procedure iteratively reduces the corruption measure until termination.
- Good Samples: Independent samples from the sub-Gaussian distribution form an (ε, τ)-good set with probability at least 1 −τ using Ω((d/ε2) poly log(d/ετ)) samples.The good-set condition is the probabilistic foundation for the filtering analysis.
A.1.1 Algorithm Filter-Sub-Gaussian-Unknown-Mean: Proof of Proposition A.7
The procedure computes empirical moments and uses unusually large covariance directions to identify filtering directions; otherwise, it returns the empirical mean.
- Algorithm: The algorithm returns the empirical mean when the empirical covariance has no large eigenvalues.Otherwise, it selects the maximum-magnitude eigenvector and uses it with the empirical mean to define a filter.
A.1.2 Proof of Correctness of Filter-Sub-Gaussian-Unknown-Mean
The filter algorithm either returns the empirical mean when covariance deviation is small or removes points along a direction revealed by a large covariance eigenvalue. Its correctness follows by relating the observed covariance and mean shifts to the error set and showing filtering preferentially removes errors.
- Filtering step: The filter retains points satisfying |v∗·(x − µS′)| ≤ T + δ, where v∗ is the leading eigenvector and T is the selected threshold.
- Algorithm: The algorithm computes the sample mean and covariance, then returns the mean when ∥Σ − I∥2 ≤ O(ε log(1/ε)).
- Structural bounds: Σ − I is approximately (|E|/|S′|)ME, so large covariance eigenvalues identify directions in which error points deviate from the empirical mean.
- Filtering guarantee: The proof bounds removals from the good set using concentration and shows that the filter removes sufficiently many corrupted points relative to good points.
- Large spectral norm: When the covariance deviation is large, the proof shows that a threshold T satisfying the filtering condition must exist.
A.1.3 Proof of Lemma A.5
Lemma A.5 establishes uniform tail bounds for projections of samples from a good set. The proof combines sub-Gaussian concentration, exponential-moment bounds, covering nets, and union bounds over directions and thresholds.
- Good-set conditions: The sample-size argument also controls coordinate magnitudes and supplies the concentration properties required for the good-set definition.
- Fixed-direction bound: For any fixed unit vector v and threshold T, the good set satisfies PrX∈uS[|v · (X − µG)| > T] ≤ δ/(C T^2).The result uses C = 8.
- Moment argument: Sub-Gaussianity bounds the corresponding tail under G by exp(−T^2/(2ν)), which is converted into a bound on the sample tail probability.
- Uniformization: A 1/2-cover of the unit sphere and a union bound extend the fixed-direction estimate to all directions and dyadic thresholds.
- Uniformization: The resulting uniform bound holds simultaneously for all unit vectors v and all 0 ≤ T ≤ R with probability at least 1 − τ/3.
A.2 Robust Mean Estimation Under Second Moment Assumptions
This section develops a filtering estimator for robust mean estimation under only a bounded second-moment assumption. The algorithm iteratively removes points along high-variance directions and achieves an O(√ε) mean error with near sample-optimal complexity.
- Guarantee: Theorem A.16 uses Θ((d/ε) log d) samples and outputs bµ with ∥bµ − µP∥2 ≤ O(√ε) in time poly(d/ε).The guarantee holds with probability 2/3.
- Good sets: An ε-good set has mean error at most √ε and spectral covariance norm at most 2 relative to the target distribution.
- Algorithm: The algorithm computes the sample mean and covariance, returns the mean when the top covariance eigenvalue is at most 9, and otherwise filters along its leading eigenvector.
- Stopping condition: If λ∗ ≤ 9, the empirical mean already satisfies ∥µG − µS∥2 = O(√ε).
- Overall result: The iterative analysis yields the final O(√ε) estimate with probability at least 2/3, while the algorithm runs in polynomial time.
A.3 Robust Covariance Estimation
This section adapts filtering to robust covariance estimation for a zero-mean Gaussian. It weakens the good-set requirements and uses polynomial decompositions and covers to obtain near sample-optimal concentration for quadratic forms.
- Setup: The covariance estimator uses the filtering algorithm for a mean-zero Gaussian with unknown covariance.
- Good-set definition: The weaker good-set definition controls quadratic-polynomial variances and tails rather than requiring the stronger prior conditions.
- Filtering consequence: Under the weaker definition, the existing filtering analysis recovers the Gaussian to ˜O(ε) error from an ε-corrupted good set.
- Sample complexity: A sufficiently large sample of N = Θ(d^2 log^5(d/ε)/ε^2) independent Gaussian observations is ε-good with high probability.
- Polynomial decomposition: Every normalized even degree-2 polynomial decomposes into O(log d) low-rank components plus a polynomial with L2 norm at most ε/d.
B.1 Full description of the distributions for experiments
The experiments use synthetic and semi-synthetic distributions designed to make noise points non-obvious while testing robust mean, covariance, and geographic reconstruction.
- Experiment design: Noise distributions were chosen so corrupted points were not obvious pointwise outliers, while still creating difficulty for the tested algorithms.
- Synthetic mean: Synthetic mean experiments use uncorrupted samples from N(µ, I), with µ equal to the all-ones vector.
- Synthetic mean: The synthetic mean noise distribution combines a hypercube product distribution with a product distribution having nonzero variation in its first two coordinates.
- Synthetic covariance: Synthetic covariance experiments include isotropic data from N(0, I) with zero noise and skewed data from N(0, I + 100e1eT_1) with rotated product-distribution noise.
- Semi-synthetic geographic experiment: The geographic experiment diagonalizes and randomly rotates 20-dimensional data from, then adds product-distribution noise with coordinate-specific integer ranges scaled by 1/24.
B.2 Comparison with other robust PCA methods on semi-synthetic data
The study compares the authors’ method with several robust PCA approaches on Europe semi-synthetic data. The comparison includes visual reconstructions produced by each method.
- Compared methods: The comparison includes RANSAC, LRVCov, two subsampled SDP methods, and the ADMM method of.
- Results: Across most tested noise patterns, only the authors’ algorithm and LRVCov reasonably reconstruct Europe in the presence of noise.
- Figure 4: Figure 4 orders the visualizations as the original projection, the authors’ recovery, RANSAC, LRVCov, [CLMW11] ADMM, [XCS10] SDP, and [CLMW11] SDP.