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 Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Computational Complexity of Learning Neural Networks: Smoothness and Degeneracy
Authors: Amit Daniely, Nati Srebro, Gal Vardi
NeurIPS 2023 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We show that learning depth-3 Re LU networks under the Gaussian input distribution is hard even in the smoothed-analysis framework, where a random noise is added to the network s parameters. It implies that learning depth-3 Re LU networks under the Gaussian distribution is hard even if the weight matrices are non-degenerate. Moreover, we consider depth-2 networks, and show hardness of learning in the smoothed-analysis framework, where both the network parameters and the input distribution are smoothed. Our hardness results are under a well-studied assumption on the existence of local pseudorandom generators. |
| Researcher Affiliation | Collaboration | Amit Daniely Hebrew University and Google EMAIL Nathan Srebro TTI-Chicago EMAIL Gal Vardi TTI-Chicago and Hebrew University EMAIL |
| Pseudocode | No | No pseudocode or algorithm blocks are explicitly presented or labeled in the paper. |
| Open Source Code | No | The paper does not provide any statement or link regarding the availability of open-source code for the methodology described. |
| Open Datasets | No | The paper describes theoretical input distributions (e.g., Gaussian, Bernoulli) within a learning framework but does not mention or provide access information for any publicly available or open dataset used for training. |
| Dataset Splits | No | This paper is theoretical and does not describe experiments with data splits for training, validation, or testing. |
| Hardware Specification | No | The paper does not mention any specific hardware used for running experiments, as it is a theoretical work. |
| Software Dependencies | No | The paper does not specify any software dependencies with version numbers, as it is a theoretical work and does not describe an implementation. |
| Experiment Setup | No | The paper does not provide details on experimental setup, hyperparameters, or training configurations, as it is a theoretical work. |