Improved Bounds on Neural Complexity for Representing Piecewise Linear Functions
Authors: Kuan-Lin Chen, Harinath Garudadri, Bhaskar D Rao
NeurIPS 2022 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we propose much tighter bounds and establish a polynomial time algorithm to find a network satisfying these bounds for any given CPWL function. We prove that the number of hidden neurons required to exactly represent any CPWL function is at most a quadratic function of the number of pieces. |
| Researcher Affiliation | Academia | Kuan-Lin Chen Department of Electrical and Computer Engineering University of California, San Diego La Jolla, CA 92093, USA EMAIL Harinath Garudadri Qualcomm Institute University of California, San Diego La Jolla, CA 92093, USA EMAIL Bhaskar D. Rao Department of Electrical and Computer Engineering University of California, San Diego La Jolla, CA 92093, USA EMAIL |
| Pseudocode | Yes | Algorithm 1 Find a Re LU network that computes a given continuous piecewise linear function |
| Open Source Code | No | The paper states that an implementation is provided in the supplementary material for runtime measurement but does not explicitly state that the code is open-source or publicly available, nor does it provide a direct link to a public repository. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments requiring a dataset, thus no dataset availability information is provided. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper mentions measuring algorithm runtime 'on a computer' in the supplementary material, but it does not specify any details regarding the hardware used (e.g., CPU, GPU model). |
| Software Dependencies | No | The paper discusses mathematical methods for linear programming, but it does not list any specific software dependencies or versions used for an implementation. |
| Experiment Setup | No | The paper is theoretical and does not involve empirical experiments, therefore no experimental setup details like hyperparameters or training settings are provided. |