The All-or-Nothing Phenomenon in Sparse Tensor PCA
Authors: Jonathan Niles-Weed, Ilias Zadik
NeurIPS 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the statistical problem of estimating a rank-one sparse tensor corrupted by additive gaussian noise, a Gaussian additive model also known as sparse tensor PCA. We show that for Bernoulli and Bernoulli-Rademacher distributed signals and for all sparsity levels which are sublinear in the dimension of the signal, the sparse tensor PCA model exhibits a phase transition called the all-or-nothing phenomenon. This is the property that for some signal-to-noise ratio (SNR) SNRc and any fixed > 0, if the SNR of the model is below (1 ) SNRc, then it is impossible to achieve any arbitrarily small constant correlation with the hidden signal, while if the SNR is above (1 + ) SNRc, then it is possible to achieve almost perfect correlation with the hidden signal. Our results follow from a more general result showing that for any Gaussian additive model with a discrete uniform prior, the all-or-nothing phenomenon follows as a direct outcome of an appropriately defined near-orthogonality property of the support of the prior distribution. |
| Researcher Affiliation | Academia | Jonathan Niles-Weed Courant Insititute of Mathematical Scienes and Center for Data Science New York University jnw@cims.nyu.edu Ilias Zadik Center for Data Science New York University zadik@nyu.edu |
| Pseudocode | No | The paper does not contain structured pseudocode or algorithm blocks. It is a theoretical paper focusing on mathematical proofs. |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. |
| Open Datasets | No | The paper does not use or provide concrete access information for a publicly available or open dataset. It deals with theoretical models and priors (Bernoulli, Bernoulli-Rademacher) rather than empirical datasets. |
| Dataset Splits | No | The paper does not describe dataset splits for reproduction as it does not conduct experiments on empirical datasets. |
| Hardware Specification | No | The paper does not provide specific hardware details as it does not report on computational experiments requiring such specifications. |
| Software Dependencies | No | The paper does not provide specific ancillary software details with version numbers, as it is a theoretical work and does not report on computational experiments requiring such reproducibility. |
| Experiment Setup | No | The paper does not contain specific experimental setup details, such as hyperparameter values or training configurations, as it is a theoretical work and does not report on empirical experiments. |