Overparameterization from Computational Constraints
Authors: Sanjam Garg, Somesh Jha, Saeed Mahloujifar, Mohammad Mahmoody, Mingyuan Wang
NeurIPS 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In summary, we prove that under the computational assumption that one-way functions exist, the answer to all three of our main questions above is positive. Indeed, we show that the computational efficiency of the learner could be the cause of having overparametarized models. Furthermore, the computational efficiency of the adversary could reduce the size of the models. In particular, we prove the following theorem, in which a learning task is parameterized by λ, a hypothesis class H and a class of input distributions D (see Section 2.1 for formal definitions). Theorem 1 (Main results, informal). |
| Researcher Affiliation | Collaboration | Sanjam Garg UC Berkeley and NTT Research sanjamg@berkeley.edu University of Wisconsin, Madison jha@cs.wisc.edu Princeton University sfar@princeton.edu University of Virginia mohammad@virginia.edu UC Berkeley mingyuan@berkeley.edu |
| Pseudocode | No | The paper does not contain any structured pseudocode or algorithm blocks. The methods and constructions (e.g., Construction 12, Construction 16) are described in prose. |
| Open Source Code | No | The paper does not provide any concrete access to source code, such as repository links or explicit statements about code release for the methodology described. |
| Open Datasets | No | The paper is theoretical and focuses on mathematical proofs and constructions of learning tasks (e.g., Construction 12, Construction 16) rather than empirical studies on publicly available datasets. Therefore, it does not provide concrete access information for a publicly available or open dataset used for training. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with data splits. Therefore, it does not provide specific dataset split information (e.g., percentages, sample counts, or citations to predefined splits) for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not conduct experiments that would require specific hardware. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and focuses on mathematical proofs and constructions. It does not mention any specific software dependencies with version numbers needed to replicate the work. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experiments with specific setup details, hyperparameters, or training configurations. It focuses on theoretical proofs and abstract constructions of learning problems. |