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

Daniel Kane; Ilias Diakonikolas

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

Download PDF