Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1]
SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions
Authors: Ilias Diakonikolas, Daniel Kane, Lisheng Ren, Yuxin Sun
NeurIPS 2023 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the complexity of Non-Gaussian Component Analysis (NGCA) in the Statistical Query (SQ) model. Prior work developed a general methodology to prove SQ lower bounds for this task... In this work, we establish that the latter condition is indeed not necessary. In particular, we prove near-optimal SQ lower bounds for NGCA under the moment-matching condition only. |
| Researcher Affiliation | Academia | Ilias Diakonikolas University of Wisconsin-Madison EMAIL Daniel M. Kane University of California, San Diego EMAIL Lisheng Ren University of Wisconsin-Madison EMAIL Yuxin Sun University of Wisconsin-Madison EMAIL |
| Pseudocode | No | The paper consists of mathematical definitions, theorems, lemmas, and proofs. It does not include any sections labeled 'Pseudocode' or 'Algorithm', nor any structured algorithm blocks. |
| Open Source Code | No | The paper is theoretical and focuses on mathematical proofs of lower bounds. It does not describe an implementable software methodology and therefore does not provide any links or statements about releasing source code. |
| Open Datasets | No | The paper is theoretical and does not involve experimental evaluation with datasets. Consequently, there is no mention of dataset availability for training. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical evaluation or dataset splits for validation. Therefore, no information on validation splits is provided. |
| Hardware Specification | No | The paper is purely theoretical and does not describe any computational experiments. Thus, there is no mention of hardware specifications used for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not involve software implementation or computational experiments. Consequently, no software dependencies or their version numbers are mentioned. |
| Experiment Setup | No | The paper is theoretical and focuses on mathematical proofs and analyses. It does not describe any experimental setups, hyperparameters, or training configurations. |