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 Shift Toward Open and Reproducible AI Research," Under Review, 2026. doi: 10.48550/arXiv.2606.16974..
First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities
Authors: Aleksandr Beznosikov, Sergey Samsonov, Marina Sheshukova, Alexander Gasnikov, Alexey Naumov, Eric Moulines
NeurIPS 2023 | Venue PDF | LLM Run Details | Input Tokens: 23,179 Total number of tokens sent to the LLM as input for this paper's analysis. | Output Tokens: 3,247 Total number of tokens produced by the LLM (including reasoning/thinking tokens) for this paper's analysis.
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | This paper delves into stochastic optimization problems that involve Markovian noise. We present a uni๏ฌed approach for the theoretical analysis of ๏ฌrst-order gradient methods for stochastic optimization and variational inequalities. Our approach covers scenarios for both non-convex and strongly convex minimization problems. To achieve an optimal (linear) dependence on the mixing time of the underlying noise sequence, we use the randomized batching scheme, which is based on the multilevel Monte Carlo method. Moreover, our technique allows us to eliminate the limiting assumptions of previous research on Markov noise, such as the need for a bounded domain and uniformly bounded stochastic gradients. Our extension to variational inequalities under Markovian noise is original. Additionally, we provide lower bounds that match the oracle complexity of our method in the case of strongly convex optimization problems. |
| Researcher Affiliation | Collaboration | Aleksandr Beznosikov Innopolis University, Skoltech, MIPT, Yandex Sergey Samsonov HSE University Marina Sheshukova HSE University Alexander Gasnikov MIPT, Skoltech, IITP RAS Alexey Naumov HSE University Eric Moulines Ecole polytechnique |
| Pseudocode | Yes | Algorithm 1 Randomized Accelerated GD; Algorithm 2 Randomized GD; Algorithm 3 Randomized Extra Gradient |
| Open Source Code | No | The paper does not provide any explicit statements or links indicating that source code for the described methodology is available. |
| Open Datasets | No | This is a theoretical paper focused on deriving complexity bounds and algorithmic analysis, not on empirical evaluation using specific datasets. |
| Dataset Splits | No | This is a theoretical paper focused on deriving complexity bounds and algorithmic analysis, not on empirical evaluation using specific datasets. Therefore, it does not provide details on dataset splits for training, validation, or testing. |
| Hardware Specification | No | This is a theoretical paper and does not describe empirical experiments, therefore no hardware specifications are provided. |
| Software Dependencies | No | This is a theoretical paper and does not describe empirical experiments, therefore no specific software dependencies with version numbers are provided. |
| Experiment Setup | No | This is a theoretical paper and does not describe empirical experiments, therefore no specific experimental setup details like hyperparameter values or training configurations are provided. |