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 and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks
Authors: Sitan Chen, Aravind Gollakota, Adam Klivans, Raghu Meka
NeurIPS 2022 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We give superpolynomial statistical query (SQ) lower bounds for learning twohidden-layer Re LU networks with respect to Gaussian inputs in the standard (noise-free) model. No general SQ lower bounds were known for learning Re LU networks of any depth in this setting: previous SQ lower bounds held only for adversarial noise models (agnostic learning) [KK14, GGK20, DKZ20] or restricted models such as correlational SQ [GGJ+20, DKKZ20]. Prior work hinted at the impossibility of our result: Vempala and Wilmes [VW19] showed that general SQ lower bounds cannot apply to any real-valued family of functions that satisfies a simple non-degeneracy condition. To circumvent their result, we refine a lifting procedure due to Daniely and Vardi [DV21] that reduces Boolean PAC learning problems to Gaussian ones. We show how to extend their technique to other learning models and, in many well-studied cases, obtain a more efficient reduction. As such, we also prove new cryptographic hardness results for PAC learning twohidden-layer Re LU networks, as well as new lower bounds for learning constantdepth Re LU networks from label queries. (...) 2. If you are including theoretical results... (a) Did you state the full set of assumptions of all theoretical results? [Yes] (b) Did you include complete proofs of all theoretical results? [Yes] All proofs are present in either the main body or the forthcoming supplement. 3. If you ran experiments... (a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [N/A] |
| Researcher Affiliation | Academia | Sitan Chen UC Berkeley EMAIL Aravind Gollakota UT Austin EMAIL Adam R. Klivans UT Austin EMAIL Raghu Meka UCLA EMAIL |
| Pseudocode | No | The paper does not contain any clearly labeled pseudocode or algorithm blocks. It presents mathematical theorems, lemmas, and proofs. |
| Open Source Code | No | Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [N/A] |
| Open Datasets | No | The paper is theoretical and does not report experimental results. Therefore, it does not use datasets for training. The ethics checklist states 'N/A' for experimental questions. |
| Dataset Splits | No | The paper is theoretical and does not report experimental results. Therefore, it does not specify dataset splits. The ethics checklist states 'N/A' for experimental questions. |
| Hardware Specification | No | The paper is theoretical and does not report experimental results. Therefore, it does not specify hardware used. The ethics checklist states 'N/A' for experimental questions. |
| Software Dependencies | No | The paper is theoretical and does not report experimental results. Therefore, it does not list software dependencies with version numbers. The ethics checklist states 'N/A' for experimental questions. |
| Experiment Setup | No | The paper is theoretical and does not report experimental results. Therefore, it does not describe experimental setup details like hyperparameters or training settings. The ethics checklist states 'N/A' for experimental questions. |