Pith. sign in

REVIEW 4 major objections 3 minor 38 references

Dimension Reduction via Sum-of-Squares and Improved Clustering Algorithms for Non-Spherical Mixtures

T0 review · 4 major / 3 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Non-spherical GMM clustering can avoid the $d^{\Omega(k)}$ barrier for centered and identical-covariance mixtures, this paper argues.

desk verdict The paper genuinely breaks the d^{Omega(k)} barrier for non-spherical GMM clustering in two important regimes, and the main proofs hold up under scrutiny; only minor defects need fixing. read the letter →

arxiv 2411.12438 v2 pith:LJCGXXBQ submitted 2024-11-19 cs.DS cs.LGstat.ML

Prashanti Anderson , Mitali Bafna , Rares-Darius Buhai , Pravesh K. Kothari , David Steurer This is my paper · ORCID
classification cs.DScs.LGstat.ML MSC 68Q2568W2062H30
keywords Gaussianmixturemodelsnon-sphericalmixturesclusteringsum-of-squaresdimensionreductionoutlierrobustnesscenteredGaussiansidenticalcovariance
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to establish that the long-standing $d^{\Omega(k)}$ cost for clustering non-spherical Gaussian mixtures is not inevitable for two natural families: centered components and components that share a single unknown covariance. It gives algorithms whose sample and running-time dependence on the dimension $d$ is a fixed polynomial for centered mixtures, and a polynomial in $d^{\log w_{\min}^{-1}}$ for identical-covariance mixtures, under total-variation separation and with tolerance to a dimension-independent fraction of arbitrary outliers. If correct, this removes the main computational barrier for clustering zero-mean and same-covariance mixtures, and it supplies a new dimension-reduction primitive: a sum-of-squares projection that preserves separation between at least one pair of components while dropping to a dimension depending only on $k$ and $w_{\min}$. A sympathetic reader would care because the previous state of the art needed $d^{O(k)}$ even for equiweighted centered components, and the paper shows that known statistical-query and cryptographic-style lower bounds do not apply to these structured families.

What carries the argument

The central object is a system of polynomial constraints $A(v,\varepsilon)$ built from estimated moments, whose feasible unit vectors $v$ are forced by low-degree sum-of-squares proofs to be nearly orthogonal to all non-spherical eigenspaces of the component covariances. For centered mixtures the key identity is $\frac{1}{3}m_4(v)-1 = \frac{1}{k}\sum_i (v^\top\Sigma_i v - 1)^2$, so the fourth moment detects spherical directions, and the Hessian condition $\nabla^2 m_4(v) = 12\,\mathrm{Id} + 24vv^\top$ forces $\Sigma_i v \approx v$ for every $i$; for identical-covariance mixtures, matching the first $O(\log w_{\min}^{-1})$ directional moments to those of a standard Gaussian forces $v^\top\Sigma v \approx 1$. The rounding theorems (Theorems 4.1 and 4.2) convert the existence of these low-degree sum-of-squares proofs into an algorithm that recovers a low-dimensional projection containing all relevant separation directions, and the iteration of partial clustering follows from that projection.

What would settle it

A direct check is to run the constant-degree sum-of-squares relaxation of the constraint system on the hard example $\frac{1}{k}\sum_i N(0, I - v_i v_i^\top)$ for $k$ distinct unit vectors, and test whether every pseudo-distribution obeying the constraints assigns small mass to non-spherical directions; finding one that does not would falsify Lemma 5.10 and with it Theorem 5.2. Independently, mechanically checking the claimed proof degrees of Lemmas 5.10\textendash 5.12 and 6.7\textendash 6.9 would settle whether the degree truly stays independent of $k$.

Watch

Extended reading notes

Core claim

The paper claims that a well-separated mixture of $k$ centered Gaussians can be clustered with $d^{O(1)} f(w_{\min}^{-1})$ samples and $\operatorname{poly}(n)$ time, and that a well-separated mixture of $k$ Gaussians with identical but arbitrary unknown covariance can be clustered with $d^{O(\log w_{\min}^{-1})} f(w_{\min}^{-1})$ samples and $d^{O(\log^2 w_{\min}^{-1})} f(w_{\min}^{-1})$ time, both robust to a dimension-independent fraction of adversarial outliers. The algorithmic engine is a sum-of-squares-based dimension-reduction subroutine that finds a low-dimensional projection of the data preserving the total-variation separation between at least one pair of components. Once such a projection is found, the algorithm partially clusters along a direction of spectral or mean separation, refines the partial clustering, and iterates until all $k$ components are separated. The paper also derives an immediate corollary for Gaussian subspace clustering with arbitrary-dimensional subspaces, obtaining the first $d^{O(1)}$-cost algorithm for that task in the general regime.

Load-bearing premise

The whole speedup hangs on the claim that the paper's system of moment constraints really forces every feasible direction to point away from all non-spherical covariance eigenspaces, and that this forcing is witnessed by a low-complexity algebraic argument whose size does not grow with $k$; if that fails, the dimension exponent grows with $k$ and the main theorems collapse.

Editorial extensions

If this is right

  • Gaussian subspace clustering with arbitrary-dimensional subspaces becomes solvable in $d^{O(1)} f(w_{\min}^{-1})$ time and samples, including with a dimension-independent fraction of outliers.
  • For identical-covariance mixtures, the algorithm turns the weak, non-laminar partial clustering of prior work into a full iterative clustering, closing the gap between partial and full clustering in that setting.
  • The results imply that the $d^{\Omega(k)}$ lower bounds for non-spherical clustering are circumvented for centered and identical-covariance mixtures, so hardness must come from mixtures that have both nonzero means and exponentially small mixing weights.
  • Both main algorithms tolerate an $\varepsilon \ll w_{\min}$ fraction of arbitrary corruptions without changing the dimension exponent.
  • The paper's low-dimensional separation-preserving projection is presented as a general subroutine that may benefit other statistical estimation tasks on non-spherical mixtures.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural testable extension is whether the fourth-moment/Hessian machinery extends to mixtures with small but nonzero means; the centered assumption rules out moment matching, so pushing to means of size $1/\operatorname{poly}(d)$ likely needs an additional constraint.
  • Because the constant-degree sum-of-squares derivations are the load-bearing part, an independent formalization or machine-checked verification of the claimed proof degrees would settle the main computational claim; the paper states these derivations but does not provide machine-checked certificates.
  • The dimension-reduction primitive may give a route to improving other moment-method algorithms that currently pay $d^{\Omega(k)}$ for anti-concentration certificates, especially list-decodable mean and covariance estimation for structured mixtures.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 3 minor

Summary. The paper develops a sum-of-squares based dimension-reduction subroutine for non-spherical Gaussian mixtures and applies it to clustering. The main results are: (1) an algorithm that clusters any well-separated mixture of k centered Gaussians using d^{O(1)} f(1/w_min) samples and time, with robustness to a constant fraction of outliers, and (2) an algorithm for well-separated identical-covariance mixtures using d^{O(log 1/w_min)} samples and d^{O(log^2 1/w_min)} time. A corollary is a d^{O(1)}-time algorithm for Gaussian subspace clustering. The paper argues that these results circumvent the d^{Ω(k)} lower bounds for non-spherical mixtures because the hard instances in those lower bounds have non-centered components and exponentially small weights.

Significance. If the proofs are correct, the centered-mixture result is a substantial breakthrough: it gives the first d^{O(1)} algorithm for well-separated centered non-spherical GMMs and for Gaussian subspace clustering, and it introduces a reusable SoS-based technique for finding low-dimensional separation-preserving projections. The paper is also careful and honest about the scope of its results: it does not claim to contradict the known lower bounds, and it identifies the exact structural features of the hard instances that are avoided. The proof structure is largely coherent: the centered case rests on constant-degree SoS proofs that are checked in detail, and the algorithmic pipeline (partial clustering, iteration, hypothesis selection) is standard and well documented. However, the identical-covariance section contains a load-bearing quantitative gap in the SoS feasibility lemma and in the moment lower bound used by the identifiability lemma; the current text does not justify the parameter dependencies that the final theorems claim.

major comments (4)
  1. [§6.1.1, Lemma 6.9 and §6.1.3, Lemma 6.14] The proof of Lemma 6.9 establishes only the bound (E⟨x,v⟩^{2t}−(2t−1)!!‖v‖^{2t})² ≤ w_min^{−4t}δ²‖v‖^{4t}, so it proves A(v, ε) with ε = O((w_min^{−1})^{40 log w_min^{−1}} δ²), not the lemma's stated ε = O((w_min^{−1})^{40 log w_min^{−1}} δ^{20 log w_min^{−1}}). The stronger δ^{20 log} form is used in the second item of Lemma 6.14: through the square root in Lemma 6.12, it is what allows the chain to terminate with the final parameter ε. If the weaker δ² bound is substituted, the chain gives the requirement δ ≤ w_min^{30 log w_min^{−1}} ε, while the first item of Lemma 6.14 requires δ ≥ w_min^{−4} ε^{1/(5 log w_min^{−1})}. For ε as small as Ω(w_min^{160 log w_min^{−1}}), these two bounds on δ are incompatible for w_min < 1. The authors need to provide a proof of the stronger δ^{20 log} dependence, or revise the parameterization of Lemma 6.14 and Theorem 6.4 accordingly.
  2. [§6.1.1, Proof of Lemma 6.7] Equation (2) of the proof uses the inequality (20t−1)!! ≥ (10t)^{10t}. This inequality is false: for t = 1, (20t−1)!! = 19!! ≈ 6.5 × 10^8, while (10t)^{10t} = 10^{10}. The displayed lower bound on Σ_i w_i⟨µ_i,v⟩^{20t} is therefore not justified, and the subsequent cancellation argument that yields v^T(I−Σ)v ≤ O((log w_min^{−1}) ε^{1/(20 log w_min^{−1})}) needs to be reworked, e.g., by using a correct Stirling-type lower bound on the double factorial and then rechecking the range of w_min for which the cancellation holds.
  3. [§5.2, Algorithm 3 line 4 versus Lemma 5.23] The pseudocode in Algorithm 3 invokes Fact 3.22 with parameters t = 4 and β = ε, while the proof of Lemma 5.23 invokes it with t = 1 and β = ε^{1/4}. The two choices give the same dependence in the Frobenius lower-bound condition (because β^{2/t} matches), but the error term in Fact 3.22 is O(β + ε/α⁴), so the numerical error rates and the success-probability parameters differ. The proof and the pseudocode should be reconciled, and the stated error bound in Lemma 5.23 should be checked against the parameters actually used.
  4. [§5.1.1, last line of Lemma 5.12] The last displayed expression in Lemma 5.12 is (u^T(p''(v) − 2‖v‖²I − 4v^{⊗2})u)², but Definition 5.8 and the preceding calculation require the expression p''(v) − 4‖v‖²I − 8v^{⊗2}. The proof text uses the correct expression earlier, so this appears to be a typo, but it should be corrected to avoid confusion about the claimed degree and the polynomial that is proved to be bounded.
minor comments (3)
  1. [§5.2.1, Lemma 5.23] The proof states that Ω(k² w_min^{−4} ε^{−1/2}) is smaller than ε^{−1} for the chosen parameters, but this requires an explicit condition such as ε ≤ O(w_min^8 k^{−4}); the lemma statement only says ε ≤ w_min^{O(1)}. This is likely absorbable into the existing assumptions, but it should be stated.
  2. [§6.1.3, Lemma 6.14, first item] The algebra that converts the bound from Lemma 6.8 into the claimed bound O(w_min^{−1} ε^{1/(80 log w_min^{−1})}) appears to lose a factor of w_min^{1/4} when using the intermediate simplification δ^{1/16} ≥ (ε')^{1/(40 log w_min^{−1})}. The extra factor is probably harmless because the theorem allows arbitrary functions of w_min, but the displayed derivation should be checked and, if needed, the O(·) should be stated with the precise w_min dependence.
  3. [Abstract and Theorem 1.1] The abstract says the centered-mixture algorithm uses n ≥ poly(d) f(w_min^{−1}) samples, while Theorem 5.2 states n ≥ poly(d, w_min^{−1}, Δ). Since Δ can be as large as f(w_min^{−1}), the statements are consistent, but the abstract should either mention the Δ dependence or clarify that Δ is absorbed into f.

Circularity Check

0 steps flagged · score 1.0 of 10

No load-bearing circularity: the dimension-reduction theorems are derived from explicit in-paper SoS proofs over moment constraints, not from fitted parameters or self-referential definitions.

full rationale

The paper's central claims follow from explicit sum-of-squares proofs over moment tensors: the subspace-finding theorems (5.5 and 6.4) are consequences of Lemmas 5.10–5.12 and 6.7–6.9, each proven in the paper from constant-degree (or O(log 1/w_min)-degree) SoS facts such as Cauchy-Schwarz, power means, and spectral norm bounds. The rounding machinery in Theorems 4.1/4.2 is analyzed directly from the system A and the assumed SoS proofs A ⊢ ||P_i v||^2 ≤ ε plus the converse feasibility lemma; both directions are proven in-paper. No parameter is fitted to the target clustering and then renamed a prediction: the algorithm enumerates thresholds and nets, and the final clustering is selected by an independent tournament (Fact 3.23). The self-citations [KS17b], [BDJ+22], and [BS23] provide moment-estimation, isotropic-position, and Frobenius-clustering subroutines whose stated assumptions do not include the target result; they are prior theorems with independent proofs, so they are real evidence rather than circular support. The only concerns are non-circularity risks: the constant-degree SoS derivations are dense and not machine-checked, and Lemma 5.12 contains a typographical slip in its final displayed line (2||v||^2/I and 4v^⊗2 instead of 4||v||^2/I and 8v^⊗2), which does not affect the preceding correct calculation. These are correctness-verification issues, not circularity.

Assumptions & free parameters 2 free parameters · 6 assumptions · 0 invented entities

The central claims rest on a chain of prior algorithmic facts and hand-chosen analysis thresholds, but no new physical or latent entities are introduced; the projection Q is an output, not an extra assumption.

free parameters (2)
  • gamma (approximate isotropic position slack) = Omega(w_min^4 epsilon^2) for centered; Omega(w_min^{40 log 1/wmin} epsilon) for identical covariance
    The whitening step must place the mixture in gamma-approximate isotropic position with gamma bounded by these hand-chosen thresholds; the entire subspace recovery analysis depends on this slack.
  • delta (eigenspace threshold) = ~ w_min^3 epsilon^2 for centered; ~ w_min^3 epsilon^{1/(10 log 1/wmin)} for identical covariance
    Defines which eigenspaces count as non-spherical; chosen to balance rank bounds and SoS error terms. These are analysis thresholds, not fitted to data.
assumptions (6)
  • standard math SoS proof-system facts (Facts 3.7-3.16)
    Used throughout for SoS derivations.
  • domain assumption TV separation implies parameter-distance separation (Fact 3.17, from [BK20])
    Translates the clustering separation condition into mean, spectral, or Frobenius separation; load-bearing for the parameter Delta in all theorems.
  • domain assumption Robust whitening algorithm (Fact 3.21, from [BDJ+22])
    Produces gamma-approximate isotropic position with SoS guarantees; invoked in Algorithm 3 and 5.
  • domain assumption Frobenius partial clustering subroutine (Fact 3.22, from [BDJ+22])
    Used to split mixtures that are Frobenius-separated; handles one of the two separation modes.
  • domain assumption Robust SoS-certifiable moment estimation (Fact 5.13 / Theorem 6.10, from [KS17b])
    Provides approximate moments with SoS proofs; the empirical constraint system A_hat is built from these estimates.
  • domain assumption Gaussian mixture identifiability, recovery, robust Gaussian learning, hypothesis selection (Facts 3.18-3.20, 3.23)
    Used in the final clustering selection step to choose a good candidate from the list.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Dimension Reduction via Sum-of-Squares and Improved Clustering Algorithms for Non-Spherical Mixtures." pith.science (2026). https://pith.science/paper/LJCGXXBQ

@misc{pith2026241112438,
  author       = {Pith},
  title        = {Pith review of: Dimension Reduction via Sum-of-Squares and Improved Clustering Algorithms for Non-Spherical Mixtures},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LJCGXXBQ}},
  note         = {Machine review of arXiv:2411.12438}
}
abstract

We develop a new approach for clustering non-spherical (i.e., arbitrary component covariances) Gaussian mixture models via a subroutine, based on the sum-of-squares method, that finds a low-dimensional separation-preserving projection of the input data. Our method gives a non-spherical analog of the classical dimension reduction, based on singular value decomposition, that, among several other applications, forms a key component of the celebrated spherical clustering algorithm of Vempala and Wang [VW04]. As applications, we obtain an algorithm to (1) cluster an arbitrary total-variation separated mixture of $k$ centered (i.e., zero-mean) Gaussians with $n\geq \operatorname{poly}(d) f(w_{\min}^{-1})$ samples and $\operatorname{poly}(n)$ time, and (2) cluster an arbitrary total-variation separated mixture of $k$ Gaussians with identical but arbitrary unknown covariance with $n \geq d^{O(\log w_{\min}^{-1})} f(w_{\min}^{-1})$ samples and $n^{O(\log w_{\min}^{-1})}$ time. Here, $w_{\min}$ is the minimum mixing weight of the input mixture, and $f$ does not depend on the dimension $d$. Our algorithms naturally extend to tolerating a dimension-independent fraction of arbitrary outliers. Before this work, the techniques in the state-of-the-art non-spherical clustering algorithms needed $d^{O(k)} f(w_{\min}^{-1})$ samples and time for clustering such mixtures. Our results may come as a surprise in the context of the $d^{\Omega(k)}$ statistical query and sum-of-squares lower bounds [DKS17, DKPP24] for clustering non-spherical Gaussian mixtures. While these results are usually thought to rule out $d^{o(k)}$ cost algorithms for the problem, our results show that the lower bounds can in fact be circumvented for a remarkably general class of Gaussian mixtures.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

38 extracted references · 35 canonical work pages

  1. [1]

    On spectral learning of mixtures of distributions

    Dimitris Achlioptas and Frank McSherry. On spectral learning of mixtures of distributions. In Learning theory , volume 3559 of Lecture Notes in Comput. Sci. , pages 458--469. Springer, Berlin, 2005

    work page 2005

  2. [2]

    Kane, Pravesh K

    Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, and Santosh S. Vempala. Robustly learning mixtures of k arbitrary G aussians. In S TOC '22--- P roceedings of the 54th A nnual ACM SIGACT S ymposium on T heory of C omputing , pages 1234--1247. ACM, New York, [2022] 2022

    work page 2022

  3. [3]

    Outlier-Robust Clustering of Non-Spherical Mixtures

    Ainesh Bakshi and Pravesh Kothari. Outlier-robust clustering of non-spherical mixtures. arXiv preprint arXiv:2005.02970 , 2020

    work page Pith review arXiv 2005

  4. [4]

    Ainesh Bakshi and Pravesh K. Kothari. List-decodable subspace recovery: dimension independent error in polynomial time. In Proceedings of the 2021 ACM - SIAM S ymposium on D iscrete A lgorithms ( SODA ) , pages 1279--1297. [Society for Industrial and Applied Mathematics (SIAM)], Philadelphia, PA, 2021

    work page 2021

  5. [5]

    Efficient Certificates of Anti-Concentration Beyond Gaussians

    Ainesh Bakshi, Pravesh Kothari, Goutham Rajendran, Madhur Tulsiani, and Aravindan Vijayaraghavan. Efficient certificates of anti-concentration beyond gaussians. arXiv preprint arXiv:2405.15084 , 2024

    work page Pith review arXiv 2024

  6. [6]

    Kelner, and David Steurer

    Boaz Barak, Jonathan A. Kelner, and David Steurer. Dictionary learning and tensor decomposition via the sum-of-squares method [extended abstract]. In S TOC '15--- P roceedings of the 2015 ACM S ymposium on T heory of C omputing , pages 143--151. ACM, New York, 2015

    work page 2015

  7. [7]

    Continuous LWE

    Joan Bruna, Oded Regev, Min Jae Song, and Yi Tang. Continuous LWE . In S TOC '21--- P roceedings of the 53rd A nnual ACM SIGACT S ymposium on T heory of C omputing , pages 694--707. ACM, New York, [2021] 2021

    work page 2021

  8. [8]

    Polynomial learning of distribution families

    Mikhail Belkin and Kaushik Sinha. Polynomial learning of distribution families. In 2010 IEEE 51st A nnual S ymposium on F oundations of C omputer S cience--- FOCS 2010 , pages 103--112. IEEE Computer Soc., Los Alamitos, CA, 2010

    work page 2010

Show all 38 references
  1. [9]

    Proofs, beliefs, and algorithms through the lens of sum-of-squares

    Boaz Barak and David Steurer. Proofs, beliefs, and algorithms through the lens of sum-of-squares. Course notes: http://www. sumofsquares. org/public/index. html , 1:3, 2016

    2016

  2. [10]

    Beyond parallel pancakes: Quasi-polynomial time guarantees for non-spherical gaussian mixtures

    Rares-Darius Buhai and David Steurer. Beyond parallel pancakes: Quasi-polynomial time guarantees for non-spherical gaussian mixtures. In The Thirty Sixth Annual Conference on Learning Theory , pages 548--611. PMLR, 2023

    2023

  3. [11]

    Learning mixtures of linear regressions in subexponential time via F ourier moments

    Sitan Chen, Jerry Li, and Zhao Song. Learning mixtures of linear regressions in subexponential time via F ourier moments. In S TOC '20--- P roceedings of the 52nd A nnual ACM SIGACT S ymposium on T heory of C omputing , pages 587--600. ACM, New York, [2020] 2020

    2020

  4. [12]

    Learning mixtures of G aussians

    Sanjoy Dasgupta. Learning mixtures of G aussians. In 40th A nnual S ymposium on F oundations of C omputer S cience ( N ew Y ork, 1999) , pages 634--644. IEEE Computer Soc., Los Alamitos, CA, 1999

    1999

  5. [13]

    Hopkins, Daniel Kane, and Sushrut Karmalkar

    Ilias Diakonikolas, Samuel B. Hopkins, Daniel Kane, and Sushrut Karmalkar. Robustly learning any clusterable mixture of gaussians. CoRR , abs/2005.06417, 2020

    2005 arXiv

  6. [14]

    Ilias Diakonikolas and Daniel M. Kane. Small covers for near-zero sets of polynomials and learning latent variable models. In 2020 IEEE 61st A nnual S ymposium on F oundations of C omputer S cience , pages 184--195. IEEE Computer Soc., Los Alamitos, CA, [2020] 2020

    2020

  7. [15]

    Robust estimators in high-dimensions without the computational intractability

    Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high-dimensions without the computational intractability. SIAM J. Comput. , 48(2):742--864, 2019

    2019

  8. [16]

    A spectral algorithm for list-decodable covariance estimation in relative frobenius norm

    Ilias Diakonikolas, Daniel Kane, Jasper Lee, Ankit Pensia, and Thanasis Pittas. A spectral algorithm for list-decodable covariance estimation in relative frobenius norm. Advances in Neural Information Processing Systems , 36:48819--48854, 2023

    2023

  9. [17]

    Kane, and Alistair Stewart

    Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. Statistical query lower bounds for robust estimation of high-dimensional G aussians and G aussian mixtures (extended abstract). In 58th A nnual IEEE S ymposium on F oundations of C omputer S cience--- FOCS 2017 , pages ...

    2017

  10. [18]

    Kane, and Alistair Stewart

    Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. List-decodable robust mean estimation and learning mixtures of spherical G aussians. In S TOC '18--- P roceedings of the 50th A nnual ACM SIGACT S ymposium on T heory of C omputing , pages 1047--1060. ACM, New York, 2018

    2018

  11. [19]

    Semialgebraic proofs and efficient algorithm design

    Noah Fleming, Pravesh Kothari, and Toniann Pitassi. Semialgebraic proofs and efficient algorithm design. Found. Trends Theor. Comput. Sci. , 14(1-2):front matter, 1--221, 2019

    2019

  12. [20]

    Rong Ge, Qingqing Huang, and Sham M. Kakade. Learning mixtures of G aussians in high dimensions [extended abstract]. In S TOC '15--- P roceedings of the 2015 ACM S ymposium on T heory of C omputing , pages 761--770. ACM, New York, 2015

    2015

  13. [21]

    Continuous LWE is as hard as LWE & applications to learning G aussian mixtures

    Aparna Gupte, Neekon Vafa, and Vinod Vaikuntanathan. Continuous LWE is as hard as LWE & applications to learning G aussian mixtures. In 2022 IEEE 63rd A nnual S ymposium on F oundations of C omputer S cience--- FOCS 2022 , pages 1162--1173. IEEE Computer Soc., Los Alamitos, CA...

    2022

  14. [22]

    Daniel Hsu and Sham M. Kakade. Learning mixtures of spherical G aussians: moment methods and spectral decompositions. In I TCS '13--- P roceedings of the 2013 ACM C onference on I nnovations in T heoretical C omputer S cience , pages 11--19. ACM, New York, 2013

    2013

  15. [23]

    Hopkins and Jerry Li

    Samuel B. Hopkins and Jerry Li. Mixture models, robustness, and sum of squares proofs. In S TOC '18--- P roceedings of the 50th A nnual ACM SIGACT S ymposium on T heory of C omputing , pages 1021--1034. ACM, New York, 2018

    2018

  16. [24]

    Misha Ivkov and Pravesh K. Kothari. List-decodable covariance estimation. In S TOC '22--- P roceedings of the 54th A nnual ACM SIGACT S ymposium on T heory of C omputing , pages 1276--1283. ACM, New York, [2022] 2022

    2022

  17. [25]

    Daniel M. Kane. Robust learning of mixtures of G aussians. In Proceedings of the 2021 ACM - SIAM S ymposium on D iscrete A lgorithms ( SODA ) , pages 1246--1258. [Society for Industrial and Applied Mathematics (SIAM)], Philadelphia, PA, 2021

    2021

  18. [26]

    List-decodable linear regression

    Sushrut Karmalkar, Adam Klivans, and Pravesh Kothari. List-decodable linear regression. Advances in neural information processing systems , 32, 2019

    2019

  19. [27]

    Efficiently learning mixtures of two G aussians

    Adam Tauman Kalai, Ankur Moitra, and Gregory Valiant. Efficiently learning mixtures of two G aussians. In S TOC '10--- P roceedings of the 2010 ACM I nternational S ymposium on T heory of C omputing , pages 553--562. ACM, New York, 2010

    2010

  20. [28]

    Kothari and Jacob Steinhardt

    Pravesh K. Kothari and Jacob Steinhardt. Better agnostic clustering via relaxed tensor norms. CoRR , abs/1711.07465, 2017

    2017 arXiv

  21. [29]

    Outlier-robust moment-estimation via sum-of-squares

    Pravesh K Kothari and David Steurer. Outlier-robust moment-estimation via sum-of-squares. arXiv preprint arXiv:1711.11581 , 2017

    2017 arXiv

  22. [30]

    Clustering mixtures with almost optimal separation in polynomial time

    Allen Liu and Jerry Li. Clustering mixtures with almost optimal separation in polynomial time. In S TOC '22--- P roceedings of the 54th A nnual ACM SIGACT S ymposium on T heory of C omputing , pages 1248--1261. ACM, New York, [2022] 2022

    2022

  23. [31]

    Learning gmms with nearly optimal robustness guarantees

    Allen Liu and Ankur Moitra. Learning gmms with nearly optimal robustness guarantees. In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory , volume 178 of Proceedings of Machine Learning Research , pages 2815--2895. PMLR, 02--05 Jul 2022

    2022

  24. [32]

    Lai, Anup B

    Kevin A. Lai, Anup B. Rao, and Santosh Vempala. Agnostic estimation of mean and covariance. In 57th A nnual IEEE S ymposium on F oundations of C omputer S cience--- FOCS 2016 , pages 665--674. IEEE Computer Soc., Los Alamitos, CA, 2016

    2016

  25. [33]

    Polynomial-time tensor decompositions with sum-of-squares

    Tengyu Ma, Jonathan Shi, and David Steurer. Polynomial-time tensor decompositions with sum-of-squares. In 57th A nnual IEEE S ymposium on F oundations of C omputer S cience--- FOCS 2016 , pages 438--446. IEEE Computer Soc., Los Alamitos, CA, 2016

    2016

  26. [34]

    Settling the polynomial learnability of mixtures of G aussians

    Ankur Moitra and Gregory Valiant. Settling the polynomial learnability of mixtures of G aussians. In 2010 IEEE 51st A nnual S ymposium on F oundations of C omputer S cience--- FOCS 2010 , pages 93--102. IEEE Computer Soc., Los Alamitos, CA, 2010

    2010

  27. [35]

    Contributions to the mathematical theory of evolution

    Karl Pearson. Contributions to the mathematical theory of evolution. Philosophical Transactions of the Royal Society of London. A , 185:71--110, 1894

  28. [36]

    List decodable learning via sum of squares

    Prasad Raghavendra and Morris Yau. List decodable learning via sum of squares. In Proceedings of the 2020 ACM - SIAM S ymposium on D iscrete A lgorithms , pages 161--180. SIAM, Philadelphia, PA, 2020

    2020

  29. [37]

    Learning mixtures of arbitrary G aussians

    Arora Sanjeev and Ravi Kannan. Learning mixtures of arbitrary G aussians. In Proceedings of the T hirty- T hird A nnual ACM S ymposium on T heory of C omputing , pages 247--257. ACM, New York, 2001

    2001

  30. [38]

    A spectral algorithm for learning mixture models

    Santosh Vempala and Grant Wang. A spectral algorithm for learning mixture models. J. Comput. System Sci. , 68(4):841--860, 2004

    2004

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.