Limitations on Variance-Reduction and Acceleration Schemes for Finite Sums Optimization
Authors: Yossi Arjevani
NeurIPS 2017 | Conference PDF | Archive PDF | Plain Text | 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 yossi.arjevani@weizmann.ac.il |
| 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. |