Reproducibility in Optimization: Theoretical Framework and Limits
Authors: Kwangjun Ahn, Prateek Jain, Ziwei Ji, Satyen Kale, Praneeth Netrapalli, Gil I Shamir
NeurIPS 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We initiate a formal study of reproducibility in optimization. We define a quantitative measure of reproducibility of optimization procedures in the face of noisy or error-prone operations such as inexact or stochastic gradient computations or inexact initialization. We then analyze several convex optimization settings of interest such as smooth, non-smooth, and strongly-convex objective functions and establish tight bounds on the limits of reproducibility in each setting. Our analysis reveals a fundamental trade-off between computation and reproducibility: more computation is necessary (and sufficient) for better reproducibility. The primary contribution of this paper is conceptual: the development of a rigorous theoretical framework to study the fundamental limits of reproducibility in convex optimization. The technical contribution of this paper is the development of lower bounds on the amount of reproducibility, and matching upper bounds via analysis of specific first-order algorithms in all the different settings of convex optimization described above. |
| Researcher Affiliation | Collaboration | Kwangjun Ahn MIT EECS kjahn@mit.edu Prateek Jain Google Research prajain@google.com Ziwei Ji Google Research ziweiji@google.com Satyen Kale Google Research satyenkale@google.com Praneeth Netrapalli Google Research pnetrapalli@google.com Gil I. Shamir Google Research, Brain Team gshamir@google.com |
| Pseudocode | No | The paper describes algorithms like SGD and defines an FOI algorithm formally but does not include any explicit pseudocode blocks or sections labeled 'Algorithm'. |
| Open Source Code | No | The paper does not contain any explicit statements or links indicating that source code for the described methodology is publicly available. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments using specific datasets. It discusses 'training loss' in the context of machine learning problems but does not refer to a specific dataset used for empirical evaluation. |
| Dataset Splits | No | The paper is theoretical and does not report on empirical experiments, therefore no train/validation/test dataset splits are provided. |
| Hardware Specification | No | The paper mentions GPUs as a source of non-deterministic errors in reproducibility but does not specify any hardware used by the authors to conduct experiments. |
| Software Dependencies | No | The paper is theoretical and does not report on empirical experiments, therefore it does not list specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on mathematical analysis and proofs. It does not provide details of an experimental setup, hyperparameters, or training configurations. |