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

Efficient high-dimensional learning of separated mixtures and robust means remains limited, especially for spherical Gaussian clustering and general sub-Gaussian distributions. This paper uses Sum of Squares algorithms to recover structured subsets, achieving improved separation and robust-mean error guarantees.

  • Problem

    Prior efficient methods required separation at least O(k^1/4) for spherical Gaussian mixtures and achieved only O(ε^1/2) error for general sub-Gaussian robust estimation.

    Source: §1 · p. 3, §1.1 · p. 6

  • Method

    The paper uses Sum of Squares semidefinite programs and higher-moment certificates to identify structured subsets or estimate their empirical means.

    Source: §1 · pp. 3–4

  • Results

    The algorithms learn spherical Gaussian means in (dk)^{O(1/γ^2)} time and robustly estimate means with error O(ε^{1−1/t}) under explicit boundedness.

    Source: §1 · p. 3, §1.1 · pp. 5–6

  • Takeaways & Limitations

    Mixture learning and robust estimation can be addressed through a unified structured-subset recovery technique based on higher moments and Sum of Squares.

    Source: §1 · pp. 3–4

    The robust-estimation guarantee applies when bounded-moment conditions have low-degree Sum of Squares certificates, a restriction that excludes some distributions.

    Source: §1.1 · p. 6, §3 · p. 12

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 separated mixture learning and robust mean estimation by identifying structured subsets with certified higher-moment information. It breaks the k^1/4 clustering barrier and improves efficient robust mean estimation beyond O(ε^1/2) under explicit moment-boundedness conditions.

1 Introduction

  • The unified technique identifies structured sample subsets or their empirical means using higher moments and Sum of Squares semidefinite programs with simple low-degree identifiability proofs.The mixture setting contains one structured subset per component, whereas robust estimation contains the uncorrupted (1−ε)n samples.Source: §1 · pp. 3–4

1.1 Results

  • For spherical Gaussian mixtures, the algorithm estimates all means to 1/poly(k) error with high probability when pairwise separation is k^γ, in (dk)^O(1/γ^2) time.The guarantee holds for every γ > 0 and uses at most k^O(1)d^O(1/γ) samples.Source: §1.1 · p. 5
  • The mixture guarantees extend beyond Gaussians to component distributions with O(1/γ)-explicitly bounded moments, including symmetric product distributions with bounded moments.The method uses O(1/γ) moments rather than only second moments.Source: §1.1 · p. 5
  • For ε-corrupted samples from an O(t)-explicitly bounded distribution, robust mean estimation achieves O(ε^(1−1/t)) error with polynomial-time and d^O(t)(1/ε)^O(1) sample complexity.Explicit boundedness requires low-degree Sum of Squares certificates for the relevant moment bounds, and the theorem assumes t ≥ 4.Source: §1.1 · p. 6

1.2 Related work

  • Related work reaches a k^1/4 separation barrier, whereas this paper avoids non-degeneracy assumptions and uses only component moment information, making its clustering approach more robust to modelling errors.The paper contrasts its method with tensor decompositions that exploit exact higher-moment structure of the full mixture.Source: §1.2 · pp. 6–7

1.3 Organization

  • The paper proceeds from high-level algorithmic ideas and Sum of Squares background to shared polynomial inequalities, formal algorithms, analyses, and detailed inequalities.Sections 2–7 cover these topics in that order.Source: §1.3 · p. 8

2 Techniques

The section develops a unified SoS framework that turns low-degree identifiability proofs into SDP-based algorithms for mixture learning and robust estimation. Its core argument uses higher-moment constraints and Hölder’s inequality to control candidate empirical means.

2.1 Proofs to algorithms for machine learning: the SoS method

  • Low-degree SoS identifiability proofs become algorithms by encoding sample constraints, finding a satisfying pseudodistribution through an SDP, and rounding it to estimate the parameters.The method replaces potentially NP-hard search over polynomial-system solutions with convex optimization over pseudodistributions, whose guarantees follow from the corresponding SoS proof.Source: §2.1 · p. 9

2.2 H¨older’s inequality and identifiability from higher moments

  • The identifiability argument models candidate sample subsets with 0/1 indicators and imposes projection-wise t-th moment bounds that hold for the true Gaussian subset when αn ≫ d^t.These constraints certify sub-Gaussian empirical moments in every direction, enabling low-degree SoS reasoning about candidate means.Source: §2.2 · p. 10

2.3 From identifiability to algorithms

  • Mixture algorithms extract component information by finding a pseudodistribution over moment-valid subsets with SDP and applying standard rounding, avoiding direct search for such subsets.A subset of roughly n/k points would suffice statistically, but pseudodistributions provide the efficiently computable low-degree surrogate used by the algorithm.Source: §2.3 · pp. 11–12

3 Preliminaries

The paper assumes distributions whose bounded moments admit low-degree Sum of Squares proofs, then formulates separated-mixture learning and robust-mean problems under these assumptions. It introduces SoS proofs and pseudoexpectations as the proof-system framework and notes that rotations of suitable product distributions, including Gaussians, satisfy the boundedness condition.

3 Preliminaries

  • A distribution is t-explicitly bounded when every even moment up to t has a corresponding degree-s SoS proof, typically with variance proxy σ = 1.The condition is equivalent to requiring the associated moment polynomial to be a sum of squares; the framework also tolerates degree O(s) proofs and weaker sub-exponential bounds.Source: §3 · p. 12

3.1 The SoS proof system

  • Rotations of product distributions with bounded coordinate moments are t-explicitly bounded, including Gaussians and other natural distribution classes.The paper states that product distributions and rotations thereof with bounded t-th moments satisfy the explicit-boundedness condition.Source: §3 · p. 13, §3.1 · p. 14

3 Preliminaries

  • The mixture-learning problem estimates all k component means within δ, up to permutation, from samples of a t-explicitly bounded mixture whose means are pairwise separated by more than Δ.The components have means μ1, …, μk, mixture weights summing to one, and the required success probability is at least 0.99.Source: §3 · p. 13
  • Robust mean estimation starts from an ε-corrupted sample, formed by arbitrarily changing εn points from n independent draws, and targets error O(ε^(1−1/t)) for an O(t)-explicitly bounded distribution.The distribution has mean μ, and the task is to output an estimate μ̂ satisfying the stated norm error bound.Source: §3 · p. 13

3.1 The SoS proof system

  • The SoS proof system represents polynomial nonnegativity through sums of squares and axioms, with proofs classified by degree; pseudoexpectations provide the dual objects.SoS proofs compose through addition and multiplication, while soundness ensures any satisfying pseudoexpectation also satisfies inequalities possessing SoS proofs.Source: §3.1 · pp. 13–14
  • Pseudoexpectations satisfy positivity and the given polynomial inequalities and equalities, and SoS soundness transfers every proved inequality to any pseudoexpectation satisfying the axioms.This establishes the proof-system relationship used by the paper’s later SoS-based arguments.Source: §3.1 · p. 14

4 Capturing empirical moments with polynomials

This section formulates empirical moment capture as a polynomial constraint system for selecting a large subset with bounded moments. Lemma 4.1 provides a computable SoS relaxation that is satisfiable on clean samples, supports pseudodistributions, and preserves the needed moment implications despite approximate numerical solutions.

Polynomial formulation

  • The polynomial system encodes a nearly αn-sized subset through Boolean indicators, its empirical mean, and directional t-th moment bounds.The selected indicators satisfy w_i^2 = w_i, the subset size is approximately αn, and μ represents the empirical mean of selected samples.Source: §4 · p. 15
  • Because the target means are unknown, the algorithm replaces mean-dependent inequalities with sub-Gaussian-type bounds in every direction.These universal bounds imply the desired directional moment inequalities without requiring the unknown μ_j parameters in the written system.Source: §4 · p. 15

Lemma 4.1

  • Lemma 4.1 constructs degree-O(t) polynomial constraints that are satisfiable with high probability on a sufficiently large iid clean subset and solvable via degree-Ct pseudodistributions in n^O(Ct) time.Satisfiability holds with probability at least 1 − d^-8 when the clean subset and sample-size conditions are met; solvability returns an approximate pseudodistribution.Source: §4 · p. 15
  • The constructed system gives degree-tℓ SoS-certifiable moment bounds for every degree-ℓ polynomial vector of the unknown means and implies the original constraints with degree O(t).The implication from the constructed system to the original system is explicitly stated as b A ⊢O(t) A.Source: §4 · p. 15

Numerical accuracy

  • Approximate semidefinite-programming pseudodistributions remain sufficient because bounded SoS coefficients transfer error η = 2^-n to η′ ≤ 2^-Ω(n), adequate for rounding analyses.The paper subsequently ignores numerical issues after establishing this transfer, while referring to [O’D17, BS17, RW17] for further discussion.Source: §4 · p. 16

5 Mixture models: algorithm and analysis

This section develops and analyzes an SoS-based algorithm for learning mixture components by clustering samples through second-moment rounding and robustly estimating their means. It proves recovery guarantees under explicit moment, separation, and empirical concentration conditions, including that the rounding iterations recover distinct components while controlling bad indices.

5 Mixture models: algorithm and analysis

  • For separation Δ = k^γ, choosing t = O(1/γ) yields poly(1/k) mean-estimation error with (dk)^O(1) samples and time.The guarantee applies to O(1/γ)-explicitly bounded component distributions and matches Theorem 1.1.Source: §5 · p. 16
  • For Δ = C′√log k, choosing t = O(log k) yields 1/poly(k) error using d^O(log k) samples and d^O(log k)2 time.This regime applies to O(log k)-explicitly bounded distributions.Source: §5 · p. 16

5.1 Algorithm and main analysis

  • The algorithm minimizes a pseudoexpectation’s second-moment matrix by semidefinite programming, rounds that matrix into clusters, and applies robust mean estimation to each cluster.The implementation uses degree-O(t) pseudoexpectations, RoundSecondMoments, and EstimateMean.Source: §5.1 · p. 17

5.2 Proof of main theorem

  • With n ≥ d^O(t)k^O(1) and Δ ≥ 1, the empirical moment and mean conditions hold simultaneously with probability at least 1 − 1/d^15.These conditions support the main theorem’s high-probability analysis for uniform mixtures.Source: Deterministic Conditions · p. 18

5.3 Identifiability

  • The identifiability proof combines SoS moment bounds, an SoS triangle inequality for separated means, and pseudodistribution manipulations to distinguish components.The separation inequality lower-bounds the combined t-th-power distances by 2^-tΔ^t.Source: §5.3 · pp. 19–20

5.4 Proof of Lemma 5.5

  • The proof of Lemma 5.5 controls contaminated-cluster errors and empirical t-th-moment deviations using Hölder’s inequality and the moment inequalities encoded in the SoS system.These bounds connect incorrectly assigned samples and empirical moment errors to the pseudoexpectation analysis.Source: §5.4 · pp. 20–21

5.5 Proof of Lemma 5.7

  • The proof of Lemma 5.7 derives cross-cluster bounds through pseudoexpectation Cauchy–Schwarz, Hölder’s inequality, symmetry, and degree-O(t) SoS reasoning.Fact 5.10 supplies the pseudoexpectation Hölder inequality used in the argument.Source: §5.5 · pp. 21–22

5.6 Rounding

  • If a matrix is within εn in Frobenius norm of a balanced partition indicator matrix, RoundSecondMoments returns a partition with at most ε^2mn missing and added points per cluster.The guarantee holds with probability at least 1 − ε^2m^3, up to a global permutation of clusters.Source: §5.6 · p. 23
  • Each rounding cluster has the form C_a = I_g,j_a ∪ B_a, where j_a is a distinct component and B_a contains only bad indices.The inductive argument establishes this structure whenever the algorithm selects good indices in successive iterations.Source: §5.6 · p. 24
  • At most ε^2 E n indices are E-bad.This bound is given directly by Lemma 5.13.Source: §5.6 · p. 24
  • With probability at least 1−ε^2 m^3, RoundSecondMoments chooses good indices in all k iterations.Setting E = m yields the bound by combining the per-iteration bad-selection probability with the chain rule.Source: §5.6 · p. 24

6 Robust estimation: algorithm and analysis

The section presents EstimateMean, an SoS-based robust mean estimator for ε-corrupted samples from explicitly bounded distributions, and proves its accuracy, runtime, and high-probability guarantees. Its analysis combines pruning, satisfiability, concentration, identifiability, and pseudoexpectation rounding.

6 Robust estimation: algorithm and analysis

  • The algorithm solves an SDP for a degree O(t) pseudodistribution satisfying the structured subset system with α = 1 − ε and τ = 0, then outputs its pseudoexpectation of µ.The input contains at least (1 − ε)n samples from the target distribution and εn adversarially chosen points.Source: §6 · p. 24
  • ∥µ − µ∗∥2 ≤ O(t^1/2ε^1−1/t) with probability at least 1 − 1/d for n = d^O(t)/ε2, while EstimateMean runs in time d^O(t).The guarantee assumes sufficiently small ε, t ∈ N, and a 10t-explicitly bounded distribution; the algorithm outputs a degree O(t) pseudoexpectation estimate.Source: §6 · p. 25

6.1 Additional Preliminaries

  • NaivePrune removes distant points to ensure polynomially bounded norms for SDP bit complexity, and Lemma 6.3 establishes satisfiability despite adversarially removed good samples.NaivePrune runs in O(εdn2) time and succeeds with probability 1 − 1/d10 under the theorem’s conditions.Source: §6.1 · p. 25

6.2 Formal Algorithm Specification

  • Algorithm 3 preprocesses the data with NaivePrune, centers it by the empirical mean, finds a degree O(t) pseudoexpectation satisfying Lemma 6.3’s equations, and returns the recentered estimate.The preprocessing and centering steps are also used to address finite-precision SDP computation.Source: §6.1 · p. 26, §6.2 · p. 26

6.3 Deterministic conditions

  • Conditions (E1)–(E4)—including pruning, satisfiability, and concentration of uncorrupted points and empirical moments—hold simultaneously with probability at least 1 − 1/d5.The subsequent deterministic analysis conditions on these events.Source: §6.3 · p. 26

6.4 Identifiability

  • The identifiability analysis bounds four error sources: sampling error, omitted good samples, adversarially removed good samples, and adversarially chosen vectors.It combines these bounds through SoS inequalities to derive a polynomial constraint on ∥µ − µ∗∥2, which supports the final estimator guarantee.Source: §6.4 · pp. 27–28

6.5 Rounding

  • Pseudoexpectation Cauchy–Schwarz converts the identifiability inequality into a bound on ∥˜E µ − µ∗∥, completing the rounding analysis.The rounding phase itself is therefore straightforward once the SDP solution satisfies the constraint system.Source: §6.5 · p. 29

7 Encoding structured subset recovery with polynomials

This section encodes structured subset recovery as low-degree polynomial and matrix-polynomial constraints for Sum of Squares reasoning. It establishes satisfiability and moment bounds for Gaussian and explicitly bounded distributions, then adapts the encoding to robust estimation.

7.1 Matrix SoS proofs

  • Matrix SoS proofs extend polynomial reasoning to inequalities M(x) ⪰ 0, with scalar SoS proofs as the 1 × 1 special case.Pseudodistributions satisfying matrix constraints can be found using convex semidefinite constraints analogous to the scalar case.Source: §7.1 · pp. 31–32

7.2 Warmup: Gaussian moment matrix-polynomials

  • Gaussian structured-subset axioms encode Boolean selection, subset size, empirical moments, and the selected samples’ empirical mean using polynomial constraints.The moment constraint has a simple Gaussian encoding, while the general bounded-distribution encoding is deferred to the next subsection; the empirical-mean constraint is mainly needed for robust statistics.Source: §7.2 · pp. 32–33
  • With (1 −τ)αn ≥ d^100t and iid N(µ*, I_d) samples in a subset of size at least (1 −τ)αn, the Gaussian axioms are satisfiable with probability at least 1 − d^-8.The assignment uses the subset indicator and its empirical mean; satisfiability follows from empirical-mean and matrix concentration.Source: §7.2 · p. 33

7.3 Moment polynomials for general distributions

  • For general distributions, auxiliary variables M_γ,ρ form a moment matrix constrained by polynomial equations and M ⪰ 0, with α controlling subset size and t controlling moments.The construction supplies the general moment-polynomial encoding needed for Lemma 4.1; concentration for m ≥ d^100t samples and 10t-explicitly bounded distributions establishes its required conditions.Source: §7.3 · pp. 33–36

7.4 Modifications for robust estimation

  • In the robust setting, the encoding selects the uncorrupted good samples, and with high probability its empirical mean differs from the original good-sample mean by O(t · ε^(1−1/t)).The modification accounts for replacing the full original sample mean with the mean of the remaining good samples after adversarial deletion.Source: §7.4 · p. 37

A Toolkit for sum of squares proofs

This section develops a toolkit of sum-of-squares facts, including SoS versions of Cauchy–Schwarz and Hölder, polynomial-to-matrix constructions, and sub-Gaussian moment inequalities. The accompanying proofs derive these statements through SOS expansions, block-matrix arguments, and repeated applications of the axioms.

Polynomial SOS constructions

  • A homogeneous degree-ℓ polynomial with suitably bounded coefficient 2-norm can be represented through a positive semidefinite block matrix indexed by multisets of variables.The construction places coefficient-matching matrices in off-diagonal blocks and completes the argument by verifying positive semidefiniteness.Source: A Toolkit for sum of squares proofs · p. 42

Sub-Gaussian moment bounds

  • For a sub-Gaussian variable with variance proxy 1, the toolkit supplies an SOS lower bound for even moments of linear forms, derived by expanding the polynomial and bounding Gaussian moments.The expansion uses that each resulting term is a square in the indeterminates.Source: A Toolkit for sum of squares proofs · p. 42

Basic SoS inequalities

  • SoS Cauchy–Schwarz provides a foundational inequality for indeterminates and is explicitly attributed to.The proof uses the SOS form of Cauchy–Schwarz and algebraic expansion.Source: A Toolkit for sum of squares proofs · pp. 42–43
  • SoS Hölder extends these inequalities to weights and exponents that are powers of 2, with the proof proceeding by induction and repeated SOS Cauchy–Schwarz.The second inequality is obtained from the first using the axioms and identities involving w_i^2.Source: A Toolkit for sum of squares proofs · p. 43

A.1 Examples of explicitly bounded distributions

The section establishes that rotations of products of independent t-bounded distributions are t-explicitly bounded, extending explicit boundedness to broad high-dimensional families. It also derives Gaussian and constant-variance-proxy corollaries.

A.1 Examples of explicitly bounded distributions

  • Rotations of products of independent t-bounded distributions with variance proxy 1/2 are t-explicitly bounded with variance proxy 1.This is formalized in Lemma A.7 for distributions whose coordinates are t-bounded univariate distributions.Source: §A.1 · p. 44
  • The proof reduces by rotation invariance to the product distribution, applies SoS Cauchy-Schwarz, and uses symmetry to eliminate odd monomials.The remaining coefficients are controlled by t-boundedness, yielding the explicit-boundedness condition.Source: §A.1 · p. 44
  • All Gaussians N(µ, Σ) with Σ ⪯ I are t-explicitly bounded for every t.This follows as a direct corollary of the product-distribution result.Source: §A.1 · p. 44
  • The results tolerate constant changes in the variance proxy and apply to rotations of products of t-bounded distributions with loss at most 2.The variance-proxy adjustment is obtained by scaling down.Source: §A.1 · p. 44

B Sum of squares proofs for matrix positivity – omitted proofs

This section records omitted proofs for matrix-positivity results in the Sum of Squares framework, including a soundness lemma and an auxiliary polynomial identity.

Lemma B.1

  • Lemma B.1 establishes soundness: a degree-2d pseudodistribution satisfying M1 ⪰ 0, ..., Mm ⪰ 0 also satisfies M ⪰ 0.The proof derives the additional positivity constraint from the assumed matrix-positivity constraints and concludes by linearity.Source: B Sum of squares proofs for matrix… · pp. 44–45
  • The soundness proof applies the pseudodistribution to tensor products of the constrained matrices and suitable polynomials, then uses the hypotheses to preserve nonnegativity.The argument explicitly considers T ⊆ [m], M′ = ⊗i∈T Mi, and a polynomial p before invoking linearity.Source: B Sum of squares proofs for matrix… · p. 45

Lemma B.2

  • Lemma B.2 relates a vector-valued polynomial f(x) and a matrix-valued polynomial M(x) through a tensor-product quadratic-form representation.The proof introduces the vector u encoding the identity matrix and writes ⟨f(x), M(x)f(x)⟩ as u⊤(M(x) ⊗ f(x)f(x)⊤)u.Source: B Sum of squares proofs for matrix… · p. 45

C Omitted Proofs from Section 6 · C.1 Proof of Lemma 6.4

The proof of Lemma 6.4 establishes that events (E1)–(E4) each hold with probability at least 1 − d^-8. Conditioning on (E3) and (E4), it bounds the relevant terms using concentration, the triangle inequality, Hölder’s inequality, and the stated conditions.

C.1 Proof of Lemma 6.4

  • Each of events (E1)–(E4) holds with probability at least 1 − d^-8, yielding the desired guarantee for sufficiently large d.Events (E1) and (E2) follow from Lemmas 6.2 and 6.3, while (E4) follows from the proof of Lemma 4.1.Source: §C.1 · p. 45
  • Event (E3) holds with probability 1 − d^-8 by basic concentration arguments and the chosen sample size n.The passage cites for these concentration arguments.Source: §C.1 · p. 45
  • Conditioning on the simultaneous occurrence of the concentration event and (E4), the proof uses that the Y_i are iid and equal X_i for i ∈ S_g.This setup enables the subsequent comparison via the triangle inequality.Source: §C.1 · p. 46
  • The first term in the resulting bound is controlled using inequality (6).The proof explicitly identifies this step as justification (a).Source: §C.1 · p. 46
  • For every unit vector u ∈ R^d, the second term is bounded using Hölder’s inequality.This establishes the auxiliary estimate needed for the final bound.Source: §C.1 · p. 46
  • The second-term estimate uses event (E4) and the condition δ ≪_t t.These are the two stated justifications for the corresponding inequalities.Source: §C.1 · p. 46
  • Taking the t-th root and combining the result with inequality (7) completes the proof’s final estimate.This is the last algebraic step described in the omitted proof.Source: §C.1 · p. 46

D Mixture models with nonuniform weights

The section adapts the mixture-learning algorithm to nonuniform component weights bounded below by η, while retaining k^γ mean separation. It achieves highly accurate mean recovery through iterative SDP-based clustering and a specialized rounding procedure.

Algorithm

  • The algorithm first applies single-linkage clustering, then repeatedly solves an SDP at decreasing weight thresholds and rounds each feasible solution to extract and remove clusters.Thresholds range from 1 down to η in increments ξ = poly(η/k), with τ and δ set to k^-10.Source: D Mixture models with nonuniform weights · pp. 46–47

Guarantee

  • With mixing weights at least η and pairwise mean separation k^γ, LearnNonUniformMixtureModel recovers all component means within k^-10 up to permutation with probability at least 1 − k^-5.The guarantee applies to O(1/γ)-explicitly bounded component distributions and requires n ≥ η(dk)O(1/γ) samples; the algorithm runs in O(n1/t) time.Source: D Mixture models with nonuniform weights · p. 47

Rounding

  • Because components just below a threshold may or may not affect the SDP optimum, the method uses the more involved RoundSecondMomentsNonuniform procedure instead of naive rounding.The uncertainty prevents tight upper and lower bounds on the optimal solution’s Frobenius norm.Source: D Mixture models with nonuniform weights · p. 47

Correctness invariant

  • Whenever the SDP is feasible, the algorithm removes at least one cluster, and each recovered cluster approximates a true component whose weight is sufficiently above the current threshold.For threshold α′, feasible solutions correspond to some λj within O(ξ), while every component with λj ≥ α′ + O(ξ) has exactly one recovered cluster within k^-10 poly(η) · n points of its sample set.Source: D Mixture models with nonuniform weights · p. 47

D.1 Sketch of proof of correctness of Algorithm 4

The proof sketch establishes Algorithm 4’s correctness by maintaining an invariant across feasible SDP iterations and applying concentration and SoS bounds to justify cluster removal. It follows the proof strategy of Algorithm 1 while omitting details.

Invariant preservation

  • The correctness argument shows that the key invariant holds initially and is preserved at each subsequent feasible SDP iteration.The induction fixes a feasible α′ and uses the assumption that almost all points from sufficiently large components have been removed.Source: §D.1 · pp. 47–48

Algorithm 4

  • The procedure runs RoundSecondMomentsNonuniform on M to obtain a cluster C, removes all points in C from Xr, and returns the empirical mean of every cluster in C.Source: §D.1 · p. 48

Concentration

  • Concentration permits treating component counts as their expected sizes, with |λ_jn − |S_j|| = o(n) except with negligible probability.The proof assumes λ_jn = |S_j| for simplicity and states that this does not affect the calculations.Source: §D.1 · p. 48

Cluster removal

  • Lemma D.2 bounds the SoS-certified overlap ⟨a_i, w⟩ by O(ξ^2)·α′n whenever λ_jn ≤ (α′ − O(ξ^4))n, enabling a cluster-removal step.The bound is established for any α′ well-behaved run and is then used to show that an algorithm can remove a cluster.Source: §D.1 · pp. 48–49

D.2 Rounding Well-behaved runs

The rounding procedure embeds points into vectors using the pseudoexpectation matrix, then selects a large-norm vector and returns its nearby vectors as a cluster. Under the theorem’s conditions, this recovers a cluster with small symmetric-difference error and high probability.

Rounding guarantee

  • The algorithm outputs a cluster C with |C△S_j| ≤ (η/dk)^O(1)n with probability 1 − (η/dk)^O(1).This holds when the constraints are satisfiable, the algorithm is α′ well-behaved, and condition (8) holds.Source: §D.2 · p. 49

Rounding procedure

  • It represents each point by v_i satisfying ⟨v_i,v_j⟩ = Ẽ[w_iw_j], then samples a vector with norm at least α′/100 and outputs vectors within O(√(dξ)).The representation is efficiently obtained from the positive semidefinite pseudoexpectation matrix via spectral methods.Source: §D.2 · p. 49

Cluster geometry

  • For clusters with |λ_j − α′| ≤ O(ξ^4), the corresponding vectors lie within O(√(dξ)) of a ball up to O(dξ)α′n exceptions.This geometric concentration is established by Lemmas D.4 and D.5.Source: §D.2 · pp. 49–50
  • Any two such balls whose centers have combined squared norm at least Ω(α′) are disjoint.This separation prevents the local search around a selected vector from mixing the relevant clusters.Source: §D.2 · p. 50

Rounding guarantee

  • A uniformly random vector with norm at least α′/100 lies in one of these balls with probability 1 − O(dξ), yielding the rounding guarantee.The selected ball has center norm Ω(α′), and its O(√(dξ))-neighborhood contains all but O(dξ)α′n points of the corresponding cluster.Source: §D.2 · p. 51

Related papers

Loading 1711.07454v1…