All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimation
Authors: jean barbier, Nicolas Macris, Cynthia Rush
NeurIPS 2020 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | For Bernoulli and Bernoulli-Rademacher distributed vectors, and when the sparsity and signal strength satisfy an appropriate scaling relation, we find all-or-nothing phase transitions for the asymptotic minimum and algorithmic mean-square errors. These jump from their maximum possible value to zero, at well defined signal-to-noise thresholds whose asymptotic values we determine exactly. In the asymptotic regime the statistical-to-algorithmic gap diverges indicating that sparse recovery is hard for approximate message passing. ... figures 1 and 2, found in sections 2 and 3, which display, for the Bernoulli prior, the explicit asymptotic values to which the finite n mutual information and MMSE converge. The results are similar for the Bernoulli-Rademacher distribution. In figure 1, we see that as ρn 0+ the (suitably normalized) mutual information approaches the broken line with an angular point at λ/λc(ρn) = 1 where λc(ρn) = 4| ln ρn|/ρn. Moreover the (suitably normalized) MMSE tends to its maximum possible value 1 for λ/λc(ρn) < 1, develops a jump discontinuity at λ/λc(ρn) = 1, and takes the value 0 when λ/λc(ρn) > 1 as ρn 0. In figure 2, we observe the same behavior for MSEAMP as a function of λ/λAMP(ρn), but now the algorithmic threshold is λAMP(ρn) = 1/(eρ2 n), where the constant 1/e is approximated numerically. |
| Researcher Affiliation | Academia | Jean Barbier International Center for Theoretical Physics Strada Costiera 11, 34151 Trieste, Italy EMAIL Nicolas Macris Ecole Polytechnique Fédérale de Lausanne CH 1015 Lausanne, Switzerland EMAIL Cynthia Rush Department of Statistics, Columbia University New York, NY 10025 EMAIL |
| Pseudocode | No | The paper describes the Approximate Message Passing (AMP) algorithm using mathematical equations (e.g., equation 6) and textual descriptions, but it does not provide a formally labeled "Pseudocode" or "Algorithm" block. |
| Open Source Code | No | The paper does not contain any statements about releasing code or links to a code repository. |
| Open Datasets | No | The paper refers to theoretical models and distributions (e.g., "sparse spiked Wigner matrix model", "Bernoulli and Bernoulli-Rademacher distributed vectors") rather than named public datasets. No access information (like links or citations to specific datasets) is provided. |
| Dataset Splits | No | The paper does not discuss standard train/validation/test splits of empirical datasets, as its focus is on theoretical and algorithmic analysis, including numerical demonstrations of theoretical properties. |
| Hardware Specification | No | The paper does not provide any specific details about the hardware used for computations, such as GPU/CPU models, memory, or cloud computing specifications. |
| Software Dependencies | No | The paper does not list any specific software dependencies or their version numbers (e.g., Python, PyTorch, TensorFlow, or specific solvers). |
| Experiment Setup | No | The paper focuses on theoretical analysis and algorithmic properties rather than empirical experimentation. It does not describe a typical experimental setup with hyperparameters, training schedules, or specific system configurations for model training. |