A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points

Daniel Kane, Ilias Diakonikolas
Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:3014-3028, 2023.

Abstract

We prove that for $c>0$ a sufficiently small universal constant that a random set of $c d^2/\log^4(d)$ independent Gaussian random points in $\R^d$ lie on a common ellipsoid with high probability. This nearly establishes a conjecture of \citet{SaundersonCPW12}, within logarithmic factors.The latter conjecture has attracted significant attention over the past decade, dueto its connections to machine learning and sum-of-squares lower bounds for certain statistical problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-v195-kane23a, title = {A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points}, author = {Kane, Daniel and Diakonikolas, Ilias}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {3014--3028}, year = {2023}, editor = {Neu, Gergely and Rosasco, Lorenzo}, volume = {195}, series = {Proceedings of Machine Learning Research}, month = {12--15 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v195/kane23a/kane23a.pdf}, url = {https://proceedings.mlr.press/v195/kane23a.html}, abstract = {We prove that for $c>0$ a sufficiently small universal constant that a random set of $c d^2/\log^4(d)$ independent Gaussian random points in $\R^d$ lie on a common ellipsoid with high probability. This nearly establishes a conjecture of \citet{SaundersonCPW12}, within logarithmic factors.The latter conjecture has attracted significant attention over the past decade, dueto its connections to machine learning and sum-of-squares lower bounds for certain statistical problems.} }
Endnote
%0 Conference Paper %T A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points %A Daniel Kane %A Ilias Diakonikolas %B Proceedings of Thirty Sixth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Gergely Neu %E Lorenzo Rosasco %F pmlr-v195-kane23a %I PMLR %P 3014--3028 %U https://proceedings.mlr.press/v195/kane23a.html %V 195 %X We prove that for $c>0$ a sufficiently small universal constant that a random set of $c d^2/\log^4(d)$ independent Gaussian random points in $\R^d$ lie on a common ellipsoid with high probability. This nearly establishes a conjecture of \citet{SaundersonCPW12}, within logarithmic factors.The latter conjecture has attracted significant attention over the past decade, dueto its connections to machine learning and sum-of-squares lower bounds for certain statistical problems.
APA
Kane, D. & Diakonikolas, I.. (2023). A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points. Proceedings of Thirty Sixth Conference on Learning Theory, in Proceedings of Machine Learning Research 195:3014-3028 Available from https://proceedings.mlr.press/v195/kane23a.html.

Related Material