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 Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Limitations on Variance-Reduction and Acceleration Schemes for Finite Sums Optimization
Authors: Yossi Arjevani
NeurIPS 2017 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | First, we show that, perhaps surprisingly, the finite sum structure by itself, is not sufficient for obtaining a complexity bound of O((n + L/µ) ln(1/ϵ)) for L-smooth and µ-strongly convex individual functions one must also know which individual function is being referred to by the oracle at each iteration. Next, we show that for a broad class of first-order and coordinate-descent finite sum algorithms (including, e.g., SDCA, SVRG, SAG), it is not possible to get an accelerated complexity bound of O((n+ p n L/µ) ln(1/ϵ)), unless the strong convexity parameter is given explicitly. Lastly, we show that when this class of algorithms is used for minimizing L-smooth and convex finite sums, the iteration complexity is bounded from below by Ω(n + L/ϵ), assuming that (on average) the same update rule is used in any iteration, and Ω(n + p n L/ϵ) otherwise. |
| Researcher Affiliation | Academia | Yossi Arjevani Department of Computer Science and Applied Mathematics Weizmann Institute of Science Rehovot 7610001, Israel EMAIL |
| Pseudocode | Yes | SCHEME 1 RESTARTING SCHEME GIVEN AN OPTIMIZATION ALGORITHM A |
| Open Source Code | No | The paper focuses on theoretical derivations and does not mention any associated open-source code release. |
| Open Datasets | No | The paper is theoretical and does not describe the use of any datasets for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not mention training/test/validation dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not specify any hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not list specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup or specific hyperparameters. |