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 [1].
Algorithms and matching lower bounds for approximately-convex optimization
Authors: Andrej Risteski, Yuanzhi Li
NeurIPS 2016 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we significantly improve the known lower bound on as a function of ϵ and an algorithm matching this lower bound for a natural class of convex bodies. More precisely, we identify a function T : R+ R+ such that when = O(T(ϵ)), we can give an algorithm that outputs a point x such that f( x) minx f(x) + ϵ within time poly d, 1ϵ . On the other hand, when = Ω(T(ϵ)), we also prove an information theoretic lower bound that any algorithm that outputs such a x must use super polynomial number of evaluations of f. |
| Researcher Affiliation | Academia | Yuanzhi Li Department of Computer Science Princeton University Princeton, NJ, 08450 EMAIL Andrej Risteski Department of Computer Science Princeton University Princeton, NJ, 08450 EMAIL |
| Pseudocode | Yes | Algorithm 1 Noisy Convex Optimization |
| Open Source Code | No | The paper does not provide any links to open-source code or state that the code for the methodology is available. |
| Open Datasets | No | The paper is theoretical and focuses on algorithms and lower bounds for approximately convex optimization. It does not conduct empirical studies, nor does it mention training, validation, or test sets in the context of its own work. While 'training neural networks' is mentioned as an example application, it is not part of the paper's experimental setup. |
| Dataset Splits | No | The paper is theoretical and focuses on algorithms and lower bounds for approximately convex optimization. It does not conduct empirical studies, nor does it mention training, validation, or test sets in the context of its own work. |
| Hardware Specification | No | The paper is theoretical and presents algorithms and lower bounds. It does not describe any experimental setup that would require specific hardware, thus no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and presents algorithms and lower bounds. It does not describe any experimental setup that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithms and lower bounds. While Algorithm 1 defines parameters like r, η, and T, these are part of the algorithm's theoretical formulation and analysis (e.g., convergence rates), not an empirical experimental setup with hyperparameters or training configurations for a real-world system. |