Algorithms and matching lower bounds for approximately-convex optimization
Authors: Andrej Risteski, Yuanzhi Li
NeurIPS 2016 | Conference PDF | Archive PDF | Plain Text | 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 yuanzhil@cs.princeton.edu Andrej Risteski Department of Computer Science Princeton University Princeton, NJ, 08450 risteski@cs.princeton.edu |
| 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. |