All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimation
Authors: jean barbier, Nicolas Macris, Cynthia Rush
NeurIPS 2020 | Conference 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 jbarbier@ictp.it Nicolas Macris Ecole Polytechnique Fédérale de Lausanne CH 1015 Lausanne, Switzerland nicolas.macris@epfl.ch Cynthia Rush Department of Statistics, Columbia University New York, NY 10025 cynthia.rush@columbia.edu |
| 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. |