Dimension-Free Iteration Complexity of Finite Sum Optimization Problems
Authors: Yossi Arjevani, Ohad Shamir
NeurIPS 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work, we extend the framework of Arjevani et al. [3, 5] to provide new lower bounds, which are dimension-free, and go beyond the assumptions of current bounds, thereby covering standard finite sum optimization methods, e.g., SAG, SAGA, SVRG, SDCA without duality, as well as stochastic coordinate-descent methods, such as SDCA and accelerated proximal SDCA. |
| Researcher Affiliation | Academia | Yossi Arjevani Weizmann Institute of Science Rehovot 7610001, Israel yossi.arjevani@weizmann.ac.il Ohad Shamir Weizmann Institute of Science Rehovot 7610001, Israel ohad.shamir@weizmann.ac.il |
| Pseudocode | No | The paper does not contain structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described in this paper. |
| Open Datasets | No | The paper is theoretical and does not describe experiments that utilize publicly available datasets for training. It refers to theoretical functions and prior works, such as 'function used by Nesterov in [13, Section 2.1.2]' for illustrative purposes. |
| Dataset Splits | No | The paper does not provide specific dataset split information as it focuses on theoretical analysis rather than empirical experimentation. |
| Hardware Specification | No | The paper does not provide specific hardware details as it is a theoretical work and does not describe empirical experiments requiring such specifications. |
| Software Dependencies | No | The paper does not provide specific ancillary software details, as it is a theoretical work and does not describe an implementation requiring software dependencies. |
| Experiment Setup | No | The paper does not contain specific experimental setup details, hyperparameters, or training configurations, as it is a theoretical work focused on deriving lower bounds. |