Oracle Complexity of Second-Order Methods for Finite-Sum Problems
Authors: Yossi Arjevani, Ohad Shamir
ICML 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we consider the opposite direction, and study lower bounds on the number of iterations required by algorithms using second-order (or possibly even higher-order) information, focusing on finite-sum problems which are strongly-convex and smooth. |
| Researcher Affiliation | Academia | 1Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot, Israel. |
| Pseudocode | No | The paper describes algorithmic concepts and constructions but does not provide any pseudocode or clearly labeled algorithm blocks. |
| Open Source Code | No | The paper does not contain any statement about releasing source code or a link to a code repository for the methodology described. |
| Open Datasets | No | The paper is theoretical, analyzing oracle complexity and lower bounds using constructed functions (e.g., quadratic functions in Theorem 2). It does not use real-world datasets for training or experimentation. |
| Dataset Splits | No | As a theoretical paper, it does not involve empirical evaluation on datasets with training, validation, or test splits. |
| Hardware Specification | No | The paper is theoretical and does not mention any specific hardware used for computations or experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific software dependencies or version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup, including hyperparameters or system-level training settings. |