SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions
Authors: Ilias Diakonikolas, Daniel Kane, Lisheng Ren, Yuxin Sun
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | 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 ilias@cs.wisc.edu Daniel M. Kane University of California, San Diego dakane@cs.ucsd.edu Lisheng Ren University of Wisconsin-Madison lren29@wisc.edu Yuxin Sun University of Wisconsin-Madison yxsun@cs.wisc.edu |
| 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. |