PaperlayerView exact revision on arXiv

Source-linked AI summary

Robust Estimators in High Dimensions without the Computational Intractability

Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, Alistair Stewart

arXiv:1604.06443v2cs.DScs.ITcs.LGmath.STstat.ML

TL;DR

The paper asks whether high-dimensional distribution learning remains algorithmically possible when an adversary corrupts an ε-fraction of samples. It develops efficient robust parameter-estimation methods and applies them to several distribution classes, obtaining dimension-independent error guarantees and nearly linear dependence on ε in many cases.

  • Problem

    High-dimensional agnostic learning is difficult because corruptions can be hard to detect and efficient estimators previously incurred polynomial dimension dependence.

  • Method

    The paper develops efficient robust parameter-estimation methods based on approximate eigenvalue computations or convex programming, with filtering used to detect and correct corruptions.

  • Results

    The algorithms efficiently learn a single Gaussian, binary product distributions, balanced mixtures of two product distributions, and mixtures of spherical Gaussians with dimension-independent error guarantees.

  • Takeaways & Limitations

    The work provides a general recipe for detecting and correcting high-dimensional corruptions that may apply to other distribution-learning problems.

  • Takeaways & Limitations

    An open question is which more general families of distributions admit nearly optimal agnostic learning guarantees.

Abstract

from arXiv · show

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

1 Introduction

The paper asks whether high-dimensional distribution learning remains algorithmically possible under adversarial sample corruptions. It introduces efficient estimators with dimension-independent guarantees for several distribution classes, using robust parameter estimation and filtering or convex programming.

  • Background: The problem is to efficiently learn a distribution P from samples with an adversary corrupting an ε-fraction, while achieving total-variation error f(ε,d).This is formalized as proper agnostic distribution learning.
  • Background: Prior efficient algorithms for the studied classes required error guarantees that depended polynomially on the dimension d.The difficulty is that high-dimensional corruptions can be hard to detect and can bias natural estimators in dimension-dependent ways.
  • Contributions: The paper gives first efficient agnostic-learning algorithms with error independent of d for single Gaussians, hypercube product distributions, and specified mixtures.The mixture cases include two c-balanced binary product distributions and mixtures of k spherical Gaussians.
  • Techniques: The common approach robustly estimates parameters using either a faster filtering method or convex programming, while relating parameter distance to total variation.The same approaches support the concrete learning applications with nearly identical sample complexity and error guarantees.
  • Results: The Gaussian result achieves total-variation error O(ε log3/2(1/ε)) with probability 1−τ.The algorithm applies to arbitrary unknown mean and covariance, with sample complexity improved to an information-theoretically optimal bound up to logarithmic factors.
  • Results: For two c-balanced binary product distributions, the algorithm outputs total-variation error Oc(ε1/6) with probability 1−τ.The paper identifies improving the ε-dependence or removing balancedness as open questions.

2 Preliminaries

The preliminaries formalize total variation, agnostic learning, and oblivious versus full adversaries, then introduce the distribution families and Gaussian distance tools used throughout the paper.

  • Basic notation: Total variation distance dTV(P, Q) measures the distance between two probability distributions on R^d.It is the paper’s primary distributional distance measure.
  • Types of adversaries: In the oblivious model, samples come from P that is ε-close in total variation to an unknown D ∈ D, and the algorithm must output a nearby distribution in D.The adversary fixes the noise model before observing samples.
  • Types of adversaries: The full adversary may inspect samples before removing and replacing a random Bin(m, ε) number of points, making it at least as powerful as the oblivious adversary.The paper’s algorithms are analyzed in this stronger model, often using |E| ≤ 2εm with high probability.
  • Distribution families: The paper studies Gaussians, binary product distributions, and mixtures of these distributions.A binary product distribution on {0, 1}^d has independent coordinates and is determined by its mean vector.
  • Gaussian distance tools: KL divergence has a closed-form expression for Gaussians, while Pinsker’s inequality relates KL divergence to total variation distance.These tools yield bounds connecting Gaussian mean or covariance parameter distances to total variation distance.
  • Gaussian distance tools: For Gaussian distributions, small Euclidean mean differences and Frobenius covariance differences imply correspondingly small total variation distance.The covariance result gives d_KL = O(δ^2) under the stated small-distance condition, followed by Pinsker’s inequality.

3 Some Natural Approaches, and Why They Fail

Several natural estimators fail in high-dimensional agnostic learning because adversarial corruptions create dimension-dependent error or can make the estimate arbitrarily bad. Coordinate-wise estimation accumulates error across dimensions, while geometric medians retain dimension-dependent losses despite being efficiently computable.

  • Coordinate-wise estimation: An ε-fraction of corruptions can shift each coordinate estimate by ε, producing dimension-dependent total error in d dimensions.The coordinate-wise strategy therefore loses the dimension-independent guarantee sought in agnostic learning.
  • Maximum likelihood: The MLE minimizes negative log likelihood, and for N(μ,I) it equals the empirical sample mean.This makes the estimator highly sensitive to corrupted observations placed far from the uncorrupted data.
  • Maximum likelihood: An adversary can place ε-fraction of samples arbitrarily far away, making the MLE arbitrarily bad even though it converges to the closest model in KL-divergence.The KL-nearest distribution after corruption need not be close to the original uncorrupted distribution.
  • High-dimensional medians: The Tukey median generalizes the one-dimensional median but is computationally hard, with best known algorithms taking exponential time in d.The geometric median is faster to compute and often more robust than the mean, but it still incurs dimension-dependent error.
  • High-dimensional medians: geomed(S′) = Ω(ε√d) demonstrates that geometric-median robustness can still carry a √d dimension factor.Thus, replacing the mean with an efficiently computable geometric median does not by itself remove high-dimensional dependence.

4 Agnostically Learning a Gaussian, via Convex Programming

This section develops a polynomial-time convex-programming approach for agnostically learning a single Gaussian. It combines robust mean and covariance estimation through weighted samples, concentration bounds, and approximate separation oracles.

  • Robust weighting: The framework uses the set SN,ε to represent selecting at least (1−2ε)N samples through bounded weights.When at most 2εN points are corrupted, the total weight assigned to bad points is at most 2ε.
  • Unknown mean: For an unknown mean, naive pruning removes no uncorrupted points, after which an approximate separation oracle enables convex optimization over admissible weights.The oracle is complete at the true weights and produces a separating hyperplane when queried outside the target convex set.
  • Convex optimization: The ellipsoid method converts the separation oracle into polynomial-time approximate weight recovery, with coordinate error bounded by ε/(N d log(N/τ)).The optimization procedure runs in polynomial time in N, d, 1/ε, and log 1/τ.
  • Recovery guarantees: The resulting robust mean estimator achieves ∥bµ−µ∥2 ≤ δ with probability 1−τ, for δ = O(ε log 1/ε).The covariance procedure analogously achieves normalized Frobenius error O(δ), and the combined algorithm handles unknown mean and covariance.

5 Agnostically Learning a Gaussian, via Filters

This section develops filter-based algorithms for agnostically learning Gaussians by identifying corrupted samples through empirical moment deviations and iteratively removing them. The resulting procedures efficiently estimate Gaussian means and covariances with dimension-independent error guarantees.

  • Unknown mean: For an identity-covariance Gaussian, the efficient algorithm estimates the unknown mean with Euclidean error O(ε log(1/ε)) using Ω((d/ε^2) poly log(d/ετ)) samples.The guarantee holds with probability at least 1−τ.
  • Good samples: The filter framework first defines “good” uncorrupted samples using concentration, mean accuracy, and covariance accuracy conditions.These conditions include mean error at most ε and spectral covariance error at most ε.
  • Filtering analysis: Each filtering step decreases the corruption measure by ε/α, so repeated filtering must terminate after O(α) iterations or return an accurate mean.The proof uses the decrease in symmetric-difference corruption to establish termination.
  • Filtering algorithm: An iteration either returns the empirical mean when covariance deviations are small or uses a large-eigenvalue direction to filter suspicious points.The algorithm computes the empirical mean and covariance, then filters according to the associated eigenvector when the covariance has a large deviation.
  • Filtering analysis: The analysis shows that covariance deviations approximately reflect the covariance of error points, exposing directions containing many corruptions.A large eigenvalue of the empirical covariance deviation corresponds to a direction in which error points are far from the empirical mean.
  • Unknown covariance: The method extends to unknown covariance and arbitrary Gaussians, including an efficient algorithm with Frobenius covariance error O(ε log(1/ε)).For zero-mean unknown-covariance Gaussians, the sample complexity is Ω((d^2/ε^2) poly log(d/ετ)).

6 Agnostically Learning a Mixture of Spherical Gaussians, via Convex Programming

This section combines robust moment estimation with convex programming and spectral clustering to learn mixtures of spherical Gaussians despite adversarial corruptions. The approach produces candidate mixtures, controls weighted covariance error, and tolerates a small fraction of misclassified good samples.

  • Main guarantee: For constant k, the theorem gives polynomial-time learning of ε-corrupted spherical Gaussian mixtures with running time poly(d,1/ε,log(1/τ))^k^2.The theorem states that the algorithm outputs a distribution M′ with probability 1−τ.
  • Algorithm overview: The algorithm generates a polynomial-sized candidate list containing a mixture within ˜O(poly(k)·√ε) total variation distance of the target, then selects a candidate by tournament.The list size is poly(d,1/ε,log(1/τ))^k^2.
  • Robust estimation: Convex programming finds weights satisfying robust moment constraints, and the resulting weighted empirical covariance is spectrally close to the true covariance.A separation oracle supports the convex feasibility procedure, which terminates in polynomially many iterations.
  • Spectral clustering: The clustering procedure discards at most an ε fraction of good points and misclassifies at most an O(ε) fraction under the stated deterministic condition.For each component, the returned cluster containing the most points from that component is used for comparison.
  • Spectral clustering: Spectral separation partitions components according to the sign of a projection, while the probability of a sample being misclassified is at most O(poly(ε/k)).The partition is defined by whether projected component means are positive or negative.
  • Spectral clustering: Unlike prior methods requiring no misclustered samples, this agnostic algorithm tolerates a poly(ε/k) fraction of misclassified points and continues clustering until γ=O(poly(k)·log(1/ε)).This tolerance avoids paying the cost of enforcing perfect clustering.

7 Agnostically Learning Binary Product Distributions, via Filters

This section develops filter-based polynomial-time algorithms for agnostically learning binary product distributions, first estimating their mean vectors and then converting those estimates into distributional guarantees under balance or correction for biased coordinates.

  • Mean estimation: The filtering approach estimates the coordinate-wise mean vector of an arbitrary binary product distribution within ℓ2-distance eO(ε).The method modifies the empirical covariance by zeroing its diagonal entries before filtering.
  • The general case: Highly biased coordinates require multiplicative accuracy, so the algorithm uses an initial ℓ2 estimate to construct a corrected eigenvalue problem based on χ2-distance.The resulting total variation guarantee is eO(√ε).
  • The general case: For arbitrary binary product distributions, the algorithm returns a product distribution whose mean vector has ℓ2-error O(ε log(1/ε)).This guarantee holds with probability at least 1 −τ using Θ(d4 log(1/τ)/ε2) samples.
  • The balanced case: For c-balanced products, ℓ2-distance between mean vectors serves as a proxy for total variation distance.Balancedness means every coordinate expectation lies in [c, 1 −c].
  • The balanced case: Θ(d4 log(1/τ)/ε2) samples suffice for a polynomial-time algorithm achieving dTV(P′, P) = O(ε) for c-balanced binary product distributions.The guarantee holds with probability at least 1 −τ.
  • Limitations: The O(ε log(1/ε)) bound is tight for this analysis and is a bottleneck for filter-based approaches.The limitation is stated as applying more generally to filter-based methods.

8 Agnostically Learning Mixtures of Two Balanced Binary Products, via Filters

This section extends filtering to mixtures of two balanced binary product distributions by combining conditional-mean, spectral, and line-search strategies. The resulting polynomial-time algorithm outputs a candidate mixture with dimension-polynomial sample and error guarantees.

  • Algorithmic strategies: When only the top absolute covariance eigenvalue is large, both component means lie near a one-dimensional affine subspace, enabling grid search over candidate positions.When the second absolute eigenvalue is also large, the algorithm constructs a filter instead.
  • Overall guarantee: The overall theorem guarantees a polynomial-time algorithm for c-balanced mixtures with dTV-error O(ε1/6/√It succeeds with probability at least 1 −τ using poly(d, 1/ε) log(1/τ) samples.
  • Algorithmic strategies: The mixture algorithm uses two strategies: conditioning on a coordinate with separated component means, or handling cases where the means are close through a modified eigenvalue problem.The first strategy exploits conditional empirical means; the second treats small coordinate-wise separation.
  • Candidate selection: The final procedure runs the strategies in parallel, rounds candidate probabilities and mixing weights, and selects among candidates using a tournament.Rounding contributes at most O(ε) additional error.
  • Separated components: For a component mean separation of at least ε1/6 in some coordinate, the algorithm produces a candidate mixture with dTV-error O(ε1/6/√The theorem assumes balanced components and mixing weights between ε1/6 and 1 −ε1/6.
  • Close components: For mixtures whose component means satisfy ∥p −q∥∞≤δ, polynomial-time learning achieves dTV-error O(δ/√The stated sample complexity is Ω(d4 log(1/τ)/(ε2δ)).

A Deferred Proofs from Section 4

These deferred proofs establish concentration and algebraic facts used by the filtering analyses, including bounds for Gaussian statistics, quadratic forms, and corrupted-sample subsets.

  • Parameter selection: The proof concludes by combining parameter choices with entropy and concentration bounds.One step uses H(ε) = O(ε log 1/ε) as ε approaches zero.
  • Gaussian moments: Isserlis’ theorem supplies Gaussian moment identities for fixed vectors under a standard normal distribution.The theorem expresses moments through sums over matchings.
  • Operator arguments: Symmetry and eigenvalue expansions are used to identify quadratic forms and prove operator claims.The arguments rely on symmetric operators and matrices.
  • Concentration bounds: The deferred arguments use Bernstein-style concentration, union bounds, and fixed-subset events to control statistics uniformly over relevant subsets.The proofs apply these tools across subset sizes and corrupted-sample configurations.

A.1 Proof of Theorem 4.13

The deferred proof of Theorem 4.13 follows immediately from Lemmas 5.17 and 5.20.

  • Theorem 4.13 is obtained directly by invoking Lemmas 5.17 and 5.20.

B.1 Proof of Lemma 5.3

The proof establishes uniform concentration and norm bounds for samples from a sub-Gaussian distribution by combining tail estimates, VC bounds, covers, and union bounds.

  • N = Ω((d/ε^2) poly log(d/ετ)) samples are drawn from G for the lemma’s guarantees.
  • Sub-Gaussian tail bounds control the probability that any fixed projection exceeds threshold T.The proof bounds Pr_G[|v · (X − μ_G)| > T] using exp(−T^2/(2ν)).
  • With sufficiently small δ and sufficiently large C, the exponential-moment and Markov argument gives the desired bound.
  • A 1/2-cover of the unit sphere with size 2^O(d) reduces uniform control over all directions to finitely many projected events.
  • The union-bound argument yields the target projection bound simultaneously for all unit vectors and thresholds 0 ≤ T ≤ R with probability at least 1 − τ/3.

B.2 Proof of Lemma 5.16

The proof transforms a centered quadratic polynomial under a Gaussian distribution into a generalized χ² form, then applies anti-concentration to obtain a deviation bound.

  • A quadratic polynomial under N(0, Σ) is transformed by whitening and eigendecomposition into a sum of weighted squares of independent standard Gaussians.The transformed polynomial follows a generalized χ²-distribution.
  • Pr(|p(X) − E[p(X)]| ≥ T) ≤ 2e^(1/3−2T/3 Var[p(X)]).
  • Theorem B.3 supplies the anti-concentration inequality used for degree-d polynomials of standard Gaussian inputs.

B.3 Proof of Lemma 5.17

The proof controls quadratic polynomials by decomposing them according to eigenvalue scales, constructing finite covers, and combining concentration with union bounds.

  • The proof uses covers over unit vectors and union bounds to establish variance control and uniform tail conditions over the polynomial classes.
  • Every normalized even degree-2 polynomial decomposes into O(log d) components grouped by eigenvalue scale.The decomposition writes p = 2(p_1 + p_2 + . . . + p_2^t + p_d), with each component in the corresponding class P_k.
  • The Hanson-Wright inequality provides sharper tails for polynomials whose associated matrices do not have a single large eigenvalue.The tail exponent depends on both the Frobenius and operator norms of the associated matrix.
  • Each class P_k admits a cover C_k of size 2^O(dk log R) with approximation variance at most 1/R^2d^2.
  • Any normalized polynomial can be expressed as a sum of covered components plus a residual polynomial with variance at most O(1/R^2).

C Deferred Proofs from Section 6

The deferred proofs establish structural bounds for mixtures and covariance-related quantities using cluster connectivity, low-rank subspaces, and Schatten-norm duality.

  • The relevant vectors lie in a subspace of rank at most k, enabling a k-dimensional orthonormal basis to be used in the analysis.
  • If two mixture means share a cluster scale, a connected-chain argument bounds their squared distance by O(kd log(k/ε)).
  • The auxiliary graph on mixture components converts overlapping cluster chains into a path of length at most k between the two means.
  • The top-k Schatten norm is lower-bounded through its dual characterization by the trace over this orthonormal subspace.
  • A covariance lower-bound argument combines nonnegative variance with prior conditions to derive the stated conclusion.

C.1 Proof of Theorem 6.12

The proof establishes completeness by showing that uniform weights on uncorrupted samples are feasible and force the optimization objective to reject corrupted-weight configurations.

  • Objective separation: The proof expands the covariance-related expression using the mean error ∆ = µ − µ̂ and bounds the resulting components for sufficiently large c.Several inequalities combine the expansion with prior bounds to obtain the desired sign condition.
  • Completeness: Uniform weights on uncorrupted points belong to the feasible set because at most 2εN samples are corrupted.This establishes feasibility of the intended weighting vector.
  • Matrix bound: The matrix M is decomposed into mean-error and mixture-separation terms before bounding its Schatten top-k norm.The proof applies triangle inequality, positive semidefiniteness, and auxiliary lemmas to control the resulting terms.
  • Objective separation: The constructed objective satisfies ℓ(w) ≥ 0, while the uncorrupted weighting vector satisfies ℓ(w∗) < 0.The latter inequality is established by separately analyzing the relevant cases.

D Deferred Proofs from Section 7

The deferred proof transfers affine-function accuracy from the underlying product distribution to the empirical sample, then uses an event-restricted affine transformation to complete the argument.

  • Proof of Lemma 7.21: With Ω(d^4 log(1/τ)/ε′^2) samples, the empirical set approximates every affine threshold probability within ε′/d with probability at least 1 − τ.The proof conditions on this uniform approximation event.
  • Event control: The event C_T that all coordinates in T take their most common values has probability at least 3/5 under P and at least 1/2 in the sample.The empirical bound follows by representing the event through an affine count function.
  • Event-restricted transformation: For an affine function L, L_T subtracts a penalty proportional to the number of coordinates in T that differ from their most common values.On the hypercube, L_T(x) > 0 exactly when L(x) > 0 and C_T holds.
  • Conclusion: The transformed threshold probability is compared by expanding its empirical and population probabilities and using the lower bounds on C_T.This yields the claimed approximation and completes Lemma 7.21.

E Deferred Proofs from Section 8

The deferred proofs establish high-probability goodness for mixture components and control covariance discrepancies using zeroed diagonals, while noting that off-diagonal covariance can remain difficult.

  • Component sample control: The component sample sets S_P and S_Q have near-correct proportions and sufficient sizes for applying the product-distribution goodness lemma.Chernoff bounds control the mixture proportion, while the sample-size assumptions provide the required component counts.
  • Component sample control: S_P and S_Q are simultaneously good for their respective distributions across all coordinates with probability at least 1 − τ.The conclusion follows by combining the component guarantees and the proportion bound.
  • Covariance control: Product distributions can have large diagonal covariance entries but small off-diagonal entries, motivating diagonal zeroing in the covariance analysis.The diagonal of Cov(T) is bounded separately through coordinate variances and the squared distance from the mean.
  • Covariance control: Zeroed covariance matrices are compared by the triangle inequality, separating empirical-to-target error from the diagonal-removal error.The proof bounds ∥Cov0(S′) − Cov(T)∥2 through the two terms in the decomposition.
  • Mean control: The mixture mean error is bounded by δ + O(ε) using component mean accuracy, mixture-weight accuracy, and the separation bound ∥p − q∥∞ ≤ δ.The bound combines the component contributions through the triangle inequality.
  • Final condition: The proof assumes δ^2 = Ω(ε log(1/ε)) to complete the final bound.This condition is supplied by the assumption in Theorem 8.17.
Loading 1604.06443v2…