Improved Bounds on Neural Complexity for Representing Piecewise Linear Functions
Authors: Kuan-Lin Chen, Harinath Garudadri, Bhaskar D Rao
NeurIPS 2022 | Conference 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 kuc029@ucsd.edu Harinath Garudadri Qualcomm Institute University of California, San Diego La Jolla, CA 92093, USA hgarudadri@ucsd.edu Bhaskar D. Rao Department of Electrical and Computer Engineering University of California, San Diego La Jolla, CA 92093, USA brao@ucsd.edu |
| 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. |