PaperlayerView exact revision on arXiv

Source-linked AI summary

Mixture Models, Robustness, and Sum of Squares Proofs

Samuel B. Hopkins, Jerry Li

arXiv:1711.07454v1cs.DS

TL;DR

The paper addresses efficient high-dimensional learning of separated mixtures and robust means, where prior algorithms faced separation or accuracy barriers. It uses Sum of Squares semidefinite programs to recover structured subsets and obtains improved mixture-learning and robust-estimation guarantees under certifiable moment assumptions.

  • Problem

    Efficient mixture learning faces a k^1/4 separation barrier, while robust mean estimation for general sub-Gaussian distributions was limited to O(ε1/2) error.

  • Method

    The paper uses Sum of Squares algorithms and low-degree certificates of bounded higher moments to identify structured subsets or estimate their empirical means.

  • Results

    The method breaks the k^1/4 mixture-clustering barrier and achieves O(ε1−1/t) robust-mean error in polynomial time for O(t)-explicitly bounded distributions.

  • Takeaways & Limitations

    Higher-moment SoS certificates support efficient learning beyond spherical Gaussians and improve robust estimation toward information-theoretic rates.

  • Takeaways & Limitations

    The robust guarantee requires certifiable moment boundedness, and numerical accuracy may require polynomially bounded SoS coefficients or preliminary centering.

Abstract

from arXiv · show

We use the Sum of Squares method to develop new efficient algorithms for learning well-separated mixtures of Gaussians and robust mean estimation, both in high dimensions, that substantially improve upon the statistical guarantees achieved by previous efficient algorithms. Firstly, we study mixtures of $k$ distributions in $d$ dimensions, where the means of every pair of distributions are separated by at least $k^{\varepsilon}$. In the special case of spherical Gaussian mixtures, we give a $(dk)^{O(1/\varepsilon^2)}$-time algorithm that learns the means assuming separation at least $k^{\varepsilon}$, for any $\varepsilon > 0$. This is the first algorithm to improve on greedy ("single-linkage") and spectral clustering, breaking a long-standing barrier for efficient algorithms at separation $k^{1/4}$. We also study robust estimation. When an unknown $(1-\varepsilon)$-fraction of $X_1,\ldots,X_n$ are chosen from a sub-Gaussian distribution with mean $μ$ but the remaining points are chosen adversarially, we give an algorithm recovering $μ$ to error $\varepsilon^{1-1/t}$ in time $d^{O(t^2)}$, so long as sub-Gaussian-ness up to $O(t)$ moments can be certified by a Sum of Squares proof. This is the first polynomial-time algorithm with guarantees approaching the information-theoretic limit for non-Gaussian distributions. Previous algorithms could not achieve error better than $\varepsilon^{1/2}$. Both of these results are based on a unified technique. Inspired by recent algorithms of Diakonikolas et al. in robust statistics, we devise an SDP based on the Sum of Squares method for the following setting: given $X_1,\ldots,X_n \in \mathbb{R}^d$ for large $d$ and $n = poly(d)$ with the promise that a subset of $X_1,\ldots,X_n$ were sampled from a probability distribution with bounded moments, recover some information about that distribution.

1 Introduction

The paper develops Sum of Squares algorithms for identifying structured subsets in high-dimensional mixtures and robust estimation. It breaks the k^1/4 clustering barrier and improves efficient robust-mean error under certifiable moment bounds.

  • Unified technique: The paper unifies mixture learning and robust estimation as recovering structured subsets of samples using Sum of Squares techniques.Mixture components form multiple structured subsets, while robust estimation has one uncontaminated subset.
  • Mixture models: This breaks the prior k^1/4 single-linkage barrier for efficient clustering of separated spherical Gaussian mixtures.The paper identifies this as the first progress in more than 15 years on this problem.
  • Mixture models: The algorithms use O(1/γ) higher moments rather than only second-order information, with guarantees extending to explicitly bounded non-Gaussian component distributions.The broader class includes symmetric product distributions with bounded moments.
  • Mixture models: For spherical Gaussian mixtures, an algorithm runs in (dk)O(1/γ^2) time when pairwise mean separation exceeds k^γ, for every γ > 0.It estimates each mean to inverse-polynomial accuracy with high probability.
  • Quasipolynomial regimes: Quasipolynomial resources allow stronger rates: mixture means can be recovered at inverse-polynomial error near √log k separation, and robust estimation reaches O(ε log 1/ε) error.These results use dO(log k)2 or dO(log 1/ε)2 time, respectively.
  • Robust mean estimation: For ε-corrupted samples from an O(t)-explicitly bounded distribution, robust mean estimation achieves O(ε1−1/t) error in polynomial time.The stated sample complexity is dO(t)(1/ε)O(1), with running time (dtε)O(t).

2 Techniques

The paper turns low-degree Sum of Squares identifiability proofs into algorithms for recovering structured subsets and distributional parameters. Its core analysis uses certifiable higher-moment constraints to show that any feasible subset has an accurate empirical mean.

  • Unified technique: The method targets structured subsets of samples, encompassing component samples in mixtures and uncorrupted samples in robust estimation.The same subset-identification perspective supports both problem classes.
  • SoS proofs-to-algorithms: SoS-based algorithms replace hard searches over polynomial constraints with SDPs over pseudodistributions, followed by rounding to estimate parameters.The analysis uses low-degree proofs showing that feasible parameters are close to the target.
  • Moment constraints: Moment constraints require every projection centered at a candidate empirical mean to satisfy a sub-Gaussian-type t-th moment bound.These constraints can be enforced using degree-t polynomial inequalities, and the true sampled subset satisfies them with sufficient samples.
  • Robust estimation: For robust estimation, when the valid subset fraction is 1−ε, the SoS proof can show that any feasible subset has mean close to the true mean.This is the central identifiability property used by the robust mean algorithm.
  • Mixture models: For mixtures, each component supplies a valid structured subset, so the proof identifies a mean near one component rather than a single global mean.The component means are then distinguished through separation.
  • Higher-moment identifiability: Higher moments yield the bound 4t^1/2 · k^O(1/t) when the relevant subset fraction satisfies 1/α = poly(k).With component separation k^ε, obtaining a nontrivial estimate requires t = O(1/ε).

3 Preliminaries

The preliminaries define explicitly bounded distributions and the mixture and robust mean estimation problems, then formalize the SoS proof system and its pseudoexpectation dual. These definitions specify the moment-certification assumptions underlying the algorithms.

  • Explicit boundedness: A t-explicitly bounded distribution has certified moment bounds for every even s ≤ t, with the typical variance proxy normalized to σ = 1.The certification is given by degree-s SoS proofs of the corresponding moment inequalities.
  • Explicit boundedness: The class includes Gaussians, products of sub-Gaussian distributions, and rotations of such distributions.The paper also notes that the framework extends to degree-O(s) proofs and weaker sub-exponential-type moment bounds.
  • Problem definitions: The mixture-model problem is to estimate all component means from samples of a k-component t-explicitly bounded mixture with separation Δ.The output is accurate up to a permutation of the component labels with probability at least 0.99.
  • Problem definitions: Robust mean estimation assumes an ε-corrupted sample set from an O(t)-explicitly bounded distribution and seeks error O(ε^1−1/t).The corruption process allows an adversary to alter εn points arbitrarily after independent sampling.
  • SoS proof system: An SoS proof represents a polynomial nonnegativity claim using sums-of-squares polynomials and bounded-degree products of axioms.The paper notes that SoS proofs compose through addition and multiplication.
  • SoS proof system: A degree-d pseudoexpectation is the dual object to SoS proofs and must preserve positivity for squared polynomials within its degree range.Soundness ensures that any inequality proved in the SoS system is also satisfied by the pseudoexpectation.

4 Capturing empirical moments with polynomials

The paper encodes recovery of a structured subset and its empirical mean using low-degree polynomial constraints that capture size, Boolean selection, moment bounds, and averaging. A Sum of Squares proof system then provides satisfiability, solvability, and moment-bound guarantees.

  • Structured subset constraints: The selected subset’s empirical moments are constrained by sub-Gaussian-type bounds in every direction.The intended t-th moment bound is expressed through polynomial inequalities and can avoid unknown component means.
  • Structured subset constraints: The polynomial system selects a subset of approximately αn samples and represents its indicator vector with Boolean variables.The size constraint allows fluctuations controlled by τ.
  • Structured subset constraints: The variable µ is constrained to equal the empirical mean of the selected samples.This constraint is especially used in the robust estimation setting.
  • SoS guarantees: With high probability, genuine iid samples from a bounded-moment distribution make the system satisfiable when the retained sample count is at least d^100t.The satisfying assignment uses the genuine subset’s indicator vector and empirical mean.
  • SoS guarantees: For every C, a degree-Ct pseudodistribution satisfying the system can be found in n^O(Ct) time.The resulting pseudodistribution supports later analyses through SoS implications.
  • Numerical considerations: Approximate SDP solutions remain sufficient for the rounding analyses when the SoS proof polynomials have polynomially bounded coefficients.The paper subsequently ignores numerical issues beyond noting this bounded-coefficient condition.

5 Mixture models: algorithm and analysis

The mixture-learning algorithm uses SoS-based structured-subset recovery, second-moment rounding, and robust mean estimation. Its guarantees improve as separation grows, including inverse-polynomial mean error at separation proportional to sqrt(log k) with quasi-polynomial dependence on d.

  • Guarantees: For separation ∆ = k^γ, choosing t = O(1/γ) yields poly(1/k) ℓ2 mean error with (dk)^O(1) samples and time.This applies to distributions that are O(1/γ)-explicitly bounded.
  • Guarantees: For separation ∆ = C′sqrt(log k), the method achieves 1/poly(k) error using d^O(log k) samples and d^O(log k)^2 time.The component distributions require O(log k)-explicit boundedness.
  • Algorithm: The rounding procedure converts a matrix close to a partition indicator matrix into clusters with few errors.Each recovered cluster contains nearly all of a corresponding true cluster and few points from others.
  • Algorithm: The algorithm first obtains a pseudodistribution minimizing a second-moment objective, rounds it into clusters, and estimates each cluster mean robustly.The pipeline uses semidefinite programming, RoundSecondMoments, and EstimateMean.
  • Numerical considerations: The numerical implementation requires polynomially bounded coefficients, which can be enforced by preliminary single-linkage clustering and centering when means have very large norms.This preprocessing preserves the distributions with high probability under the stated assumptions.
  • Analysis: The analysis shows that the SoS-derived matrix is close enough to the ground-truth partition for rounding to recover clusters with bounded error.The guarantee follows when the empirical moment and mean conditions hold, which occur with high probability for n ≥ d^O(t)k^O(1).

6 Robust estimation: algorithm and analysis

Robust mean estimation applies the same structured-subset SoS framework to samples with an adversarial ε-fraction. The resulting estimator achieves error O(t^1/2 ε^(1−1/t)) in d^O(t) time for explicitly bounded distributions.

  • Algorithm: The algorithm solves an SDP for a degree-O(t) pseudodistribution satisfying structured-subset constraints and outputs its pseudoexpectation of µ.The subset size is set to (1−ε)n, with τ = 0.
  • Guarantee: Theorem 6.1 gives O(t^1/2 ε^(1−1/t)) ℓ2 error in d^O(t) time with n = d^O(t)/ε^2 samples.The guarantee holds for 10t-explicitly bounded distributions and succeeds with probability at least 1−1/d.
  • Guarantee: Setting t = 2 log(1/ε) yields O(ε log(1/ε)) error with d^O(log(1/ε))^2 runtime for explicitly bounded distributions.The sample complexity becomes O(d^O(log(1/ε))/ε^2).
  • Preprocessing: Naive pruning removes distant points to keep SDP input norms polynomially bounded while succeeding with probability at least 1−1/d^10.Its stated runtime is O(εdn^2).
  • Correctness conditions: The structured-subset system remains satisfiable when the selected good samples result from adversarial removal of an ε-fraction of original iid samples.The satisfying Boolean vector indicates the remaining (1−ε)n good samples.
  • Analysis: The analysis separates error from sampling, omitted good points, adversarially removed points, and adversarially chosen vectors.These sources are controlled through separate lemmas before combining them into the final bound.

7 Encoding structured subset recovery with polynomials

The paper represents structured subset properties as low-degree polynomial and matrix-polynomial constraints. Gaussian moment bounds provide a warmup, while positive semidefinite matrix constraints support the general SoS encoding.

  • Matrix-SoS framework: The matrix-SoS proof system reasons about positive semidefiniteness constraints whose entries are polynomials in the variables.Scalar polynomial inequalities are a special case of this matrix-valued formulation.
  • Matrix-SoS framework: Pseudodistributions satisfy matrix constraints through semidefinite conditions applied to products of the constraint matrices and polynomial multipliers.These constraints can be found algorithmically using semidefinite programming.
  • Structured subset axioms: The structured-subset encoding uses Boolean selection, subset size, empirical mean, moment control, auxiliary moment variables, and the positivity constraint M ⪰ 0.The parameters α, t, and τ control subset size, moment order, and empirical fluctuations.
  • Gaussian case: For Gaussian samples, the structured-subset axioms are satisfiable with high probability when a sufficiently large subset is iid from N(µ*, I_d).The proof uses concentration of the empirical mean and standard matrix concentration.
  • Gaussian case: The t-th moment boundedness axiom yields SoS-certifiable moment bounds for polynomial functions of the unknown means.A degree-tℓ proof is obtained for a degree-ℓ polynomial vector f(µ).
  • General encoding: The general construction assigns auxiliary matrix variables to explicit polynomials and imposes equations ensuring that the resulting matrix encodes the bounded-moment condition.The final system combines these equations with positivity and the subset constraints.

A Toolkit for sum of squares proofs

This section develops a toolkit of Sum of Squares inequalities, including Cauchy–Schwarz, Hölder, norm inequalities, moment bounds, and polynomial matrix constructions. These facts support later SoS proofs by establishing polynomial and matrix positivity relations.

  • Norm inequalities: 2(∥x∥2 + ∥y∥2) bounds ∥x + y∥2 through an SoS proof of Cauchy–Schwarz.The argument expands the squared norm and applies the SoS Cauchy–Schwarz relation.
  • Polynomial matrix constructions: A homogeneous polynomial with coefficients bounded in 2-norm admits a positive semidefinite matrix representation built from degree-split monomial blocks.The construction uses blocks indexed by multisets of sizes a and b, where a + b = ℓ.
  • Moment inequalities: ⊢2t E⟨X,u⟩2t ≥−(2t)!·∥u∥2t follows by expanding the polynomial, bounding Gaussian moments, and observing that each term is a square in u.This provides an SoS-certified moment inequality for a sub-Gaussian distribution with variance proxy 1.
  • Core inequalities: SoS Cauchy–Schwarz yields polynomial analogues of standard inner-product inequalities for indeterminates.The section introduces this fact as a foundational proof tool.
  • Core inequalities: SoS Hölder extends these inequalities to powers of 2 and is proved inductively from Cauchy–Schwarz.The proof starts with an even exponent and derives the result by induction.

A.1 Examples of explicitly bounded distributions

The section establishes explicit boundedness for rotations of products of independent t-bounded distributions and derives Gaussian examples as a corollary. The proof uses symmetrization, SoS Cauchy–Schwarz, and coefficient bounds.

  • Definitions: The t-bounded condition controls even centered moments for every even 4 ≤ s ≤ t.The definition is given for a univariate distribution with mean μ and variance proxy σ.
  • Main boundedness result: Any rotation of products of independent t-bounded distributions with variance proxy 1/2 is t-explicitly bounded with variance proxy 1.This is the section’s main result.
  • Proof strategy: Symmetrizing with an independent copy removes odd monomials because the difference distribution is symmetric.The resulting polynomial is then expanded in the monomial basis.
  • Proof strategy: Coefficient bounds from t-boundedness imply that the rotated product distribution is t-explicitly bounded.The argument concludes by applying the coefficient bound after expansion.
  • Corollaries: All Gaussians N(μ,Σ) with Σ ⪯ I are t-explicitly bounded for every t.The results also tolerate constant changes in the variance proxy and apply to rotations of products of t-bounded distributions with loss at most 2.

B Sum of squares proofs for matrix positivity – omitted proofs

This section records omitted SoS proofs for matrix positivity. It shows how positivity constraints are preserved and how vector-valued polynomial quadratic forms can be represented using Kronecker products.

  • Soundness: A degree-2d pseudodistribution satisfying matrix positivity constraints also satisfies an additional matrix positivity constraint under the lemma’s hypotheses.The conclusion preserves the original constraints while adding M ⪰ 0.
  • Soundness: The soundness proof expands products of constraint matrices, applies the pseudodistribution to the resulting polynomial expressions, and concludes by linearity.The proof considers subsets T of constraints and tensor products of their matrices.
  • Polynomial matrix identities: For a vector-valued polynomial f and matrix-valued polynomial M, ⟨f(x),M(x)f(x)⟩ is expressed as a Kronecker-product quadratic form.The representation uses a vector u whose entries select diagonal positions.

C.1 Proof of Lemma 6.4

The proof establishes four high-probability events and then combines concentration, a triangle-inequality decomposition, and Hölder bounds to control the relevant quantity.

  • High-probability events: Each event E1–E4 holds with probability at least 1 − d^-8, which yields the desired guarantee for sufficiently large d.Events E1 and E2 follow from earlier lemmas, while E4 follows from a simpler version of another proof.
  • High-probability events: Basic concentration arguments show that event E3 holds with probability 1 − d^-8 for the chosen sample size n.The proof then conditions on E3 and E4 occurring simultaneously.
  • Bounding the target: Conditioning on E3 and E4, the proof decomposes the target using the triangle inequality and bounds the second term for every unit vector u with Hölder’s inequality.The subsequent bound uses event E4 and the condition δ ≪_t t.
  • Bounding the target: Taking the t-th root and combining the resulting estimate with equation (7) completes the bound.This is the final step of the argument.

D Mixture models with nonuniform weights

The section extends mixture learning to nonuniform component weights bounded below by η, using an SDP-based iterative procedure and more involved rounding to recover component means.

  • The algorithm assumes component weights at least η and pairwise mean separation at least k^γ.
  • Theorem D.1 guarantees recovery of all component means up to permutation with error k^-10 and probability at least 1 − k^-5.
  • The procedure applies single-linkage clustering, then processes each cluster while sweeping thresholds α′ from 1 down to η.
  • At each threshold, it seeks a minimum-Frobenius-norm pseudo-expectation, rounds its second-moment matrix into a cluster, removes that cluster, and continues.
  • Nonuniform weights require a more involved rounding algorithm because components just below α′ may or may not affect the SDP optimum.
  • The analysis simplifies by treating components with weights at least α′ + O(ξ) as removed, while arguing the remaining and mistakenly removed points do not affect calculations.

D.1 Sketch of proof of correctness of Algorithm 4

The proof maintains an invariant linking feasible SDP thresholds to component weights and uses repeated rounding to remove one component cluster at a time.

  • Algorithm 4 first performs naive clustering, processes each resulting cluster separately, and initializes an empty output collection.
  • For each threshold α′, it constructs a degree-t pseudoexpectation satisfying structured subset polynomials with SDP parameters δ,τ = k^-8.
  • While the SDP remains feasible, the algorithm obtains a pseudoexpectation, forms M = E~ ww^T, rounds M into a cluster, and removes that cluster.
  • After all feasible runs and threshold updates, it returns the empirical mean of every output cluster.
  • Lemma D.2 bounds pseudoexpected mass for components whose weights lie below α′ − O(ξ^4), supporting the removal argument.

D.2 Rounding Well-behaved runs

The rounding analysis embeds the SDP second-moment matrix as vectors, shows relevant clusters concentrate in small balls, and uses this geometry to recover a component cluster.

  • Lemma D.3 guarantees a rounding algorithm that outputs a cluster differing from a true component by at most (η/dk)^O(1)n points.
  • The SDP matrix is represented by vectors vi whose pairwise inner products equal the pseudoexpectations of wiwj, enabling geometric rounding.
  • For threshold-near components T, the algorithm selects a random vector with norm at least α′/100 and returns vectors within O(√(dξ)) of it.
  • Lemma D.5 places each relevant vector cluster near a ball of radius O(√(dξ)), up to O(dξ)α′n discrepancies.
  • Lemma D.6 shows balls with sufficiently large combined center norms are disjoint, preventing ambiguous assignments.
  • A large-norm vector lies in an appropriate ball with probability 1 − O(dξ), yielding the rounding guarantee.
Loading 1711.07454v1…