Nearly Optimal Robust Covariance and Scatter Matrix Estimation Beyond Gaussians

Gleb Novikov

Nearly Optimal Robust Covariance and Scatter Matrix Estimation Beyond Gaussians

T0 review · reviewed 2026-08-08 · deepseek-v4-flash

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

Pith's one-line read An algorithm achieves near-optimal robust covariance and scatter matrix estimation for elliptical distributions in polynomial time with $O(\varepsilon\log(1/\varepsilon))$ error under strong contamination.

desk verdict A genuinely new approach to robust covariance estimation with a repairable but real gap in the tensor contraction; deserves referee time. read the letter →

arxiv 2502.06564 v2 pith:GBGZR2LV submitted 2025-02-10 cs.DS cs.LGmath.STstat.MLstat.TH

Gleb Novikov This is my paper · ORCID

classification cs.DScs.LGmath.STstat.MLstat.TH MSC 62H1262F3562G35

keywords robustcovarianceestimationellipticaldistributionsstrongcontaminationmodelsum-of-squaresrelaxationsspatialsignscattermatrixHanson-Wrightinequalitysub-exponential

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

Robust covariance estimation has until now been solved with near-optimal error mostly for Gaussians, while the same guarantees for other natural distributions were open. This paper establishes that the right generalization is the class of elliptical distributions, that is, affine transformations of spherically symmetric distributions. For any such distribution with effective rank at least $C\log d$, and for an $\varepsilon$-corrupted sample of size $n = \tilde{O}(d^2/\varepsilon^2)$, it gives a polynomial-time algorithm that outputs a scatter matrix estimator with error $O(\varepsilon\log(1/\varepsilon))$ in relative spectral norm, and the same error in relative Frobenius norm once $\varepsilon \gtrsim \log d / \sqrt{d}$. Under Hanson-Wright or sub-exponential tail assumptions the same estimator yields robust covariance estimation at the Gaussian error rate. The reason this is significant is that the result removes moment assumptions entirely for scatter estimation, making high-dimensional robust statistics available for heavy-tailed elliptical families such as multivariate Laplace distributions.

What carries the argument

The load-bearing object is the spatial sign $\mathrm{spsign}(x)=\sqrt{d}\,x/\|x\|$, whose covariance shares the eigenvectors of the scatter matrix and is well behaved when the effective rank is large. The proof introduces a generalized stability condition for multisets of samples, parameterized by two sets $\mathcal{B}_\infty$ and $\mathcal{A}$, and runs a filtering algorithm against it. The novel step is a spectral covariance filter: it optimizes over degree-4 pseudoexpectations of rank-one tensors $\tilde{\mathbb{E}}\,x^{\otimes 4}$ rather than over all $d^2$-dimensional matrices, which makes the relevant fourth-moment comparisons tractable while avoiding hard nonconvex optimization. The transfer from the Gaussian analysis rests on the identity that the fourth-moment tensor of the whitened spatial sign differs from the Gaussian reference $2\,\mathrm{Id}_{d^2}$ by $O(1/d)$ on these pseudoexpectations. A three-stage pipeline uses a sum-of-squares based first estimate, then this spectral filter, then a Frobenius-norm filter, with fresh samples at each stage.

What would settle it

Compute the contraction in Corollary D.2 with the correct combinatorial multiplicities for all index pairings and evaluate $\langle \tilde{\mathbb{E}}\,x^{\otimes 4}, M - 2\,\mathrm{Id}_{d^2}\rangle$ for the whitened spatial sign distribution, where $M$ is the true fourth-moment tensor; if the result is not $O(1/d)$ when $\varepsilon\log(1/\varepsilon)$ is comparable to $1/d$, the spectral filtering stage fails and Theorem 1.4 is not established by this proof.

Watch

Extended reading notes

Core claim

At the center of the paper is Theorem 1.4: for every elliptical distribution whose scatter matrix $\Sigma$ satisfies $\operatorname{erk}(\Sigma):=\operatorname{Tr}\Sigma/\|\Sigma\|\geq C\log d$, given $n \geq C d^2 \log^5 d / \varepsilon^2$ samples of which an $\varepsilon$ fraction may be replaced by an arbitrary adversary, there is a polynomial-time algorithm that with high probability outputs $\hat{\Sigma}$ with $\|\Sigma^{-1/2}\hat{\Sigma}\Sigma^{-1/2}-\mathrm{Id}\| \leq O(\varepsilon\log(1/\varepsilon))$, and the same bound in Frobenius norm when $\varepsilon \geq C\log d/\sqrt{d}$. The construction works by projecting samples to the sphere (the spatial sign), estimating the covariance of that projected distribution, and then iterating: each stage whitens the data with the current estimate, so the next stage sees an elliptical distribution whose scatter matrix is closer to the identity. Because the spatial sign of an elliptical vector depends only on the scatter matrix and has sub-Gaussian behavior even when the original distribution has no moments, the algorithm can estimate the scatter matrix without any moment assumptions on the underlying elliptical family.

Load-bearing premise

The filtering stage rests on the assumption that, after whitening, the fourth-moment tensor of the spatial-sign samples is $O(1/d)$-close to the Gaussian reference $2\,\mathrm{Id}_{d^2}$ on every degree-4 pseudoexpectation (a relaxed expectation in the sum-of-squares proof system) with $\|x\|^2 \leq 1$; the displayed contraction formula supporting this claim currently omits the multiplicity of index pairings, so a corrected counting argument is needed for the proof to close.

Editorial extensions

If this is right

If the theorem is correct, robust scatter matrix estimation is solvable in polynomial time for all elliptical distributions with large effective rank, with no moment assumptions and nearly optimal sample complexity.
For elliptical distributions satisfying the Hanson-Wright inequality, such as Gaussians and uniform distributions over ellipsoids, the full covariance can be estimated with the same $O(\varepsilon\log(1/\varepsilon))$ Frobenius-norm error as in the Gaussian case.
For sub-exponential elliptical distributions such as multivariate Laplace, the covariance admits the same spectral-norm error bound, showing that heavy tails do not degrade the high-dimensional rate.
Robust PCA for elliptical distributions follows directly: the leading eigenvector can be recovered with error $O(\varepsilon\log(1/\varepsilon)/\gamma)$ when the eigenvalue gap is $\gamma$.
The generalized stability framework and the spectral covariance filter are stated as reusable algorithmic tools for future robust estimation problems.

Reading between the lines

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

Editorial extension: the same spatial-sign plus staged-whitening pipeline is a natural template for robust estimation of scale-invariant structure in heavy-tailed elliptical data, and the paper's own conjecture suggests it may extend to location estimation for non-spherical ellipticals.
Editorial extension: the spectral covariance filtering algorithm, which optimizes over degree-4 pseudoexpectations of rank-one tensors, could plausibly transfer to robust tensor PCA or other moment problems where only rank-one directions matter.
Editorial extension: a direct synthetic test on contaminated samples from multivariate Laplace and uniform-on-ellipsoid distributions could verify the predicted $O(\varepsilon\log(1/\varepsilon))$ error and the $\tilde{O}(d^2/\varepsilon^2)$ sample complexity in practice.
Editorial extension: if the missing counting argument in the fourth-moment transfer is repaired, the same proof structure would likely yield the Frobenius-norm bound under the weaker condition $\varepsilon \geq C\log d / \sqrt{d}$ without new ideas; if it cannot be repaired, the spectral bound may still hold with an extra logarithmic factor.

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.

Desk Editor's Note

read the letter

Colleague,

Here is my read of arXiv:2502.06564. The paper claims polynomial-time robust scatter/covariance estimation for general elliptical distributions with O(ε log(1/ε)) error and n = O~(d^2/ε^2) samples. If the proof holds, it's the first efficient nearly optimal result beyond Gaussians, and the applications to robust PCA and covariance estimation for Hanson-Wright/sub-exponential ellipticals are real. The spatial-sign reduction and the multi-stage whitening idea are genuinely new, as is the degree-4 SOS spectral filtering.

The proof as written has a real gap, and the stress-test note is right. Corollary D.2's contraction is missing the multiplicity of the index pairings. Using the entries given in Lemma B.2, the sum over ordered i,j of E[x_i^2 x_j^2] M_{ijij} undercounts by a factor of two relative to the tensor's four permutations (i,j,i,j), (i,j,j,i), (j,i,i,j), (j,i,j,i). The displayed conclusion = 2 is not established; on a deterministic pseudoexpectation at x=(1/√d,...,1/√d) it evaluates to about 1+1/d, not 2. I also agree that the reference tensor J in Section 2 and Lemma B.2 has a centering issue: subtracting I rather than the appropriate mean leaves a nonzero offset.

These are load-bearing because the spectral filtering stage needs the clean sign samples to be stable with respect to the reference tensor. With the wrong reference, even uncorrupted data would trigger filtering. However, the errors look repairable. A correct counting gives = 2 + O(1/d) for the whitened sign tensor, and under the paper's assumption ε log(1/ε) ≳ 1/d that O(1/d) is absorbable. The same fix likely applies to the J definition. So the theorem may well be true at the stated rates.

The rest of the paper is in good shape. The reduction from elliptical scatter to spatial sign covariance is clean, the use of KS17 and DKK+16 is appropriate, and there is no circularity or parameter tuning. The writing is honest about the effective rank and contamination assumptions. The gap is concentrated in the tensor computation, not spread through the argument.

I would send this to a serious referee. The result is important, the approach is novel, and the errors are the kind a careful referee can catch and the authors can fix. For my own work, I would cite the claimed result with a caveat until the proof is patched.

Circularity Check

0 steps flagged · score 0.0 of 10

No material circularity: the main error bound is derived from structural lemmas and external cited tools; the apparent proof gap in Corollary D.2 is a correctness issue, not a circular reduction.

full rationale

The derivation chain is self-contained in the relevant sense. The algorithm's guarantees are proved from structural lemmas about elliptical distributions and the spatial sign (Lemma A.1, Lemma B.2), from a generalized stability framework (Appendix C), and from external, independently established tools ([KS17] for sum-of-squares covariance estimation, [Ada15] for Hanson-Wright properties of Lipschitz functions of Gaussians, [DKK+16] for filtering, and [Fra04] for the symmetrization step). No parameter is fitted to force the target error O(epsilon log(1/epsilon)); all constants are absolute and the sample complexity bounds are stated, not tuned to the conclusion. The self-citations that appear in the paper ([NST23], [dNNS23], [LN24], [DBT+24]) are confined to related work and future directions and are not load-bearing for Theorem 1.4. The only potentially problematic step is Corollary D.2, where the displayed contraction asserts that <E-tilde[x^otimes4], M> = 2 +- O(1/d) using Lemma B.2's entries. As the reader's skeptical note observes, the listed entries M_{ijij}=1+O(1/d) for i != j and M_{iiii}=2+O(1/d) do not by themselves give 2 unless the off-diagonal pairing multiplicity is handled differently; on a feasible pseudoexpectation the value can be 1 + sum_i E[x_i^4]. That is a mathematical correctness gap in the proof, not a circularity: the reference tensor 2I_{d^2} is not fitted from the data, and the desired error bound is not assumed as an input. Accordingly, the circularity score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters are fitted to data. The result is a theorem conditioned on the stated model assumptions. The paper relies on standard SoS machinery and prior robust-estimation black boxes. The central proof additionally depends on a correction to the tensor normalization and contraction identities in Lemma B.2 and Corollary D.2, which are not fully established as written.

assumptions (4)

standard math Sum-of-squares hierarchy and pseudoexpectation facts, including Cauchy-Schwarz for pseudo-distributions and spectral certificates.
Used throughout Appendix D and G to justify the degree-4 SoS relaxation and the adequacy properties of the pseudoexpectation set.
standard math Hanson-Wright inequality for O(1)-Lipschitz functions of standard Gaussians, citing Adamczak.
Used in Lemma E.2 to show the whitened spatial sign satisfies the O(1)-Hanson-Wright property.
standard math Frahm's symmetrization theorem for elliptical distributions.
Used in Appendix A to reduce to location-zero elliptical distributions by pairing and differencing samples.
domain assumption Strong contamination model with known epsilon, and the stated effective rank and sample-size assumptions.
These are explicit assumptions in Theorem 1.4 and are not derived from more basic principles.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Nearly Optimal Robust Covariance and Scatter Matrix Estimation Beyond Gaussians." pith.science (2026). https://pith.science/paper/GBGZR2LV

@misc{pith2026250206564,
  author       = {Pith},
  title        = {Pith review of: Nearly Optimal Robust Covariance and Scatter Matrix Estimation Beyond Gaussians},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GBGZR2LV}},
  note         = {Machine review of arXiv:2502.06564}
}

abstract

We study the problem of computationally efficient robust estimation of the covariance/scatter matrix of elliptical distributions -- that is, affine transformations of spherically symmetric distributions -- under the strong contamination model in the high-dimensional regime $d \gtrsim 1/\varepsilon^2$, where $d$ is the dimension and $\varepsilon$ is the fraction of adversarial corruptions. We propose an algorithm that, under a very mild assumption on the scatter matrix $\Sigma$, and given a nearly optimal number of samples $n = \tilde{O}(d^2/\varepsilon^2)$, computes in polynomial time an estimator $\hat{\Sigma}$ such that, with high probability, \[ \left\| \Sigma^{-1/2} \hat{\Sigma} \Sigma^{-1/2} - Id \right\|_{\text F} \le O(\varepsilon \log(1/\varepsilon))\,. \] As an application of our result, we obtain the first efficiently computable, nearly optimal robust covariance estimators that extend beyond the Gaussian case. Specifically, for elliptical distributions satisfying the Hanson--Wright inequality (such as Gaussians and uniform distributions over ellipsoids), our estimator $\hat{\Sigma}$ of the covariance $\Sigma$ achieves the same error guarantee as in the Gaussian case. Moreover, for elliptical distributions with sub-exponential tails (such as the multivariate Laplace distribution), we construct an estimator $\hat{\Sigma}$ satisfying the spectral norm bound \[ \left\| \Sigma^{-1/2} \hat{\Sigma} \Sigma^{-1/2} - Id \right\| \le O(\varepsilon \log(1/\varepsilon))\,. \] Our approach is based on estimating the covariance of the spatial sign of elliptical distributions. The estimation proceeds in several stages, one of which involves a novel spectral covariance filtering algorithm. This algorithm combines covariance filtering techniques with degree-4 sum-of-squares relaxations, and we believe it may be of independent interest for future applications.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

30 extracted references · 29 canonical work pages

[1]

none, 1 -- 13

Radoslaw Adamczak, A note on the Hanson-Wright inequality for random vectors with dependencies , Electronic Communications in Probability 20 (2015), no. none, 1 -- 13

work page 2015
[2]

Hopkins, Daniel Kane, Sushrut Karmalkar, and Pravesh K

Ainesh Bakshi, Ilias Diakonikolas, Samuel B. Hopkins, Daniel Kane, Sushrut Karmalkar, and Pravesh K. Kothari, Outlier-robust clustering of gaussians and other non-spherical mixtures, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020 (Sandy Irani, ed.), IEEE , 2020, pp. 149--159

work page 2020
[3]

Hopkins, Daniel Kane, Sushrut Karmalkar, and Pravesh K

Ainesh Bakshi, Ilias Diakonikolas, Samuel B. Hopkins, Daniel Kane, Sushrut Karmalkar, and Pravesh K. Kothari, Outlier-robust clustering of gaussians and other non-spherical mixtures, 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), 2020, pp. 149--159

work page 2020
[4]

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 gaussians, Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (New York, NY, USA), STOC 2022, Association for Computing Machinery, 2022, p. 1234–1247

work page 2022
[5]

Ainesh Bakshi, Pravesh K. Kothari, Goutham Rajendran, Madhur Tulsiani, and Aravindan Vijayaraghavan, Efficient certificates of anti-concentration beyond gaussians, 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024, IEEE , 2024, pp. 970--987

work page 2024
[6]

Ainesh Bakshi and Adarsh Prasad, Robust linear regression: optimal rates in polynomial time, Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (New York, NY, USA), STOC 2021, Association for Computing Machinery, 2021, p. 102–115

work page 2021
[7]

Chan, ed.), SIAM , 2019, pp

Yu Cheng, Ilias Diakonikolas, and Rong Ge, High-dimensional robust mean estimation in nearly-linear time, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019 (Timothy M. Chan, ed.), SIAM , 2019, pp. 2755--2771

work page 2019
[8]

Yu Cheng, Ilias Diakonikolas, Rong Ge, and David P. Woodruff, Faster algorithms for high-dimensional robust covariance estimation, Proceedings of the Thirty-Second Conference on Learning Theory (Alina Beygelzimer and Daniel Hsu, eds.), Proceedings of Machine Learning Research, vol. 99, PMLR, 25--28 Jun 2019, pp. 727--757

work page 2019

Show all 30 references

[9]

5, 1932--1960

Mengjie Chen, Chao Gao, and Zhao Ren, Robust covariance and scatter matrix estimation under huber’s contamination model, The Annals of Statistics 46 (2018), no. 5, 1932--1960

2018
[10]

Daniil Dmitriev, Rares-Darius Buhai, Stefan Tiegel, Alexander Wolters, Gleb Novikov, Amartya Sanyal, David Steurer, and Fanny Yang, Robust mixture learning when outliers overwhelm small groups, The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024

2024
[11]

Hopkins, Ankit Pensia, and Stefan Tiegel, Sos certifiability of subgaussian distributions and its algorithmic applications, CoRR abs/2410.21194 (2024)

Ilias Diakonikolas, Samuel B. Hopkins, Ankit Pensia, and Stefan Tiegel, Sos certifiability of subgaussian distributions and its algorithmic applications, CoRR abs/2410.21194 (2024)

2024 arXiv
[12]

Chandler Davis and W. M. Kahan, The rotation of eigenvectors by a perturbation. iii, SIAM Journal on Numerical Analysis 7 (1970), no. 1, 1--46

1970
[13]

Kane, Algorithmic high-dimensional robust statistics, Cambridge University Press, 2023

Ilias Diakonikolas and Daniel M. Kane, Algorithmic high-dimensional robust statistics, Cambridge University Press, 2023

2023
[14]

Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, and Alistair Stewart, Robust estimators in high dimensions without the computational intractability, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Re...

2016
[15]

Ilias Diakonikolas, Sushrut Karmalkar, Daniel Kane, Eric Price, and Alistair Stewart, Outlier-robust high-dimensional sparse estimation via iterative filtering, Curran Associates Inc., Red Hook, NY, USA, 2019

2019
[16]

Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar, Ankit Pensia, and Thanasis Pittas, Robust sparse mean estimation via sum of squares, Proceedings of Thirty Fifth Conference on Learning Theory (Po-Ling Loh and Maxim Raginsky, eds.), Proceedings of Machine Learning Researc...

2022
[17]

Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart, Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017 ...

2017
[18]

3513--3550

Tommaso d'Orsi, Rajai Nasser, Gleb Novikov, and David Steurer, Higher degree sum-of-squares relaxations robust against oblivious outliers, Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2023, pp. 3513--3550

2023
[19]

a t zu K \

Gabriel Frahm, Generalized elliptical distributions: theory and applications, Ph.D. thesis, Universit \"a t zu K \"o ln, 2004

2004
[20]

521, 252--268

Fang Han and Han Liu, Eca: High-dimensional elliptical component analysis in non-gaussian distributions, Journal of the American Statistical Association 113 (2018), no. 521, 252--268

2018
[21]

Samuel B. Hopkins and Jerry Li, Mixture models, robustness, and sum of squares proofs, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (New York, NY, USA), STOC 2018, Association for Computing Machinery, 2018, p. 1021–1034

2018
[22]

1021--1034

Samuel B Hopkins and Jerry Li, Mixture models, robustness, and sum of squares proofs, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018, pp. 1021--1034

2018
[23]

Larochelle, M

Arun Jambulapati, Jerry Li, and Kevin Tian, Robust sub-gaussian principal component analysis and width-independent schatten packing, Advances in Neural Information Processing Systems (H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, eds.), vol. 33, Curran Associ...

2020
[24]

Klivans, Pravesh K

Adam R. Klivans, Pravesh K. Kothari, and Raghu Meka, Efficient algorithms for outlier-robust regression, Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018 (S \' e bastien Bubeck, Vianney Perchet, and Philippe Rigollet, eds.), Proceedings of Machine Lea...

2018
[25]

Pravesh K. Kothari, Peter Manohar, and Brian Hu Zhang, Polynomial-time sum-of-squares can robustly estimate mean and covariance of gaussians optimally, Proceedings of The 33rd International Conference on Algorithmic Learning Theory (Sanjoy Dasgupta and Nika Haghtalab, eds.), P...

2022
[26]

Kothari and David Steurer, Outlier-robust moment-estimation via sum-of-squares, CoRR abs/1711.11581 (2017)

Pravesh K. Kothari and David Steurer, Outlier-robust moment-estimation via sum-of-squares, CoRR abs/1711.11581 (2017)

2017 arXiv
[27]

Chih-Hung Liu and Gleb Novikov, Robust sparse regression with non-isotropic designs, The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024

2024
[28]

Magyar and David E

Andrew F. Magyar and David E. Tyler, The asymptotic inadmissibility of the spatial sign covariance matrix for elliptically symmetric distributions, Biometrika 101 (2014), no. 3, 673--688

2014
[29]

Gleb Novikov, David Steurer, and Stefan Tiegel, Robust mean estimation without moments for symmetric distributions, Advances in Neural Information Processing Systems (A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, eds.), vol. 36, Curran Associates, Inc., ...

2023
[30]

Tyler, Statistical analysis for the angular central gaussian distribution on the sphere, Biometrika 74 (1987), 579--589

David E. Tyler, Statistical analysis for the angular central gaussian distribution on the sphere, Biometrika 74 (1987), 579--589

1987

Pith tools

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

[1] [1]

none, 1 -- 13

Radoslaw Adamczak, A note on the Hanson-Wright inequality for random vectors with dependencies , Electronic Communications in Probability 20 (2015), no. none, 1 -- 13

work page 2015

[2] [2]

Hopkins, Daniel Kane, Sushrut Karmalkar, and Pravesh K

Ainesh Bakshi, Ilias Diakonikolas, Samuel B. Hopkins, Daniel Kane, Sushrut Karmalkar, and Pravesh K. Kothari, Outlier-robust clustering of gaussians and other non-spherical mixtures, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020 (Sandy Irani, ed.), IEEE , 2020, pp. 149--159

work page 2020

[3] [3]

Hopkins, Daniel Kane, Sushrut Karmalkar, and Pravesh K

Ainesh Bakshi, Ilias Diakonikolas, Samuel B. Hopkins, Daniel Kane, Sushrut Karmalkar, and Pravesh K. Kothari, Outlier-robust clustering of gaussians and other non-spherical mixtures, 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), 2020, pp. 149--159

work page 2020

[4] [4]

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 gaussians, Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (New York, NY, USA), STOC 2022, Association for Computing Machinery, 2022, p. 1234–1247

work page 2022

[5] [5]

Ainesh Bakshi, Pravesh K. Kothari, Goutham Rajendran, Madhur Tulsiani, and Aravindan Vijayaraghavan, Efficient certificates of anti-concentration beyond gaussians, 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024, IEEE , 2024, pp. 970--987

work page 2024

[6] [6]

Ainesh Bakshi and Adarsh Prasad, Robust linear regression: optimal rates in polynomial time, Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (New York, NY, USA), STOC 2021, Association for Computing Machinery, 2021, p. 102–115

work page 2021

[7] [7]

Chan, ed.), SIAM , 2019, pp

Yu Cheng, Ilias Diakonikolas, and Rong Ge, High-dimensional robust mean estimation in nearly-linear time, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019 (Timothy M. Chan, ed.), SIAM , 2019, pp. 2755--2771

work page 2019

[8] [8]

Yu Cheng, Ilias Diakonikolas, Rong Ge, and David P. Woodruff, Faster algorithms for high-dimensional robust covariance estimation, Proceedings of the Thirty-Second Conference on Learning Theory (Alina Beygelzimer and Daniel Hsu, eds.), Proceedings of Machine Learning Research, vol. 99, PMLR, 25--28 Jun 2019, pp. 727--757

work page 2019