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..
Learning from A Single Markovian Trajectory: Optimality and Variance Reduction
Authors: Zhenyu Sun, Ermin Wei
NeurIPS 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we consider the general stochastic non-convex optimization problem when the sampling process follows a Markov chain... We first provide algorithm-independent lower bounds with Ω(̈ 3) (and Ω(̈ 4)) samples... Then, we propose Markov Chain SPIDER (Ma C-SPIDER), which leverages variance-reduced techniques, to achieve a O(̈ 3) upper bound for mean-squared smooth objective functions... The paper is purely theoretical and has no empirical result. |
| Researcher Affiliation | Academia | Zhenyu Sun , Ermin Wei Department of Electrical & Computer Engineering, Northwestern University Department of Industrial Engineering & Management Sciences, Northwestern University EMAIL |
| Pseudocode | Yes | Algorithm 1 Markov-Chain SPIDER (Ma C-SPIDER) 1: Input: initial point x0, N0 = 0, batch size M1 and M2, integers T and r, stepsizes {ͷt}T 1 t=0 2: for t = 0, 1, . . . , T 1 do 3: if t mod r = 0 then 4: Draw M1 samples and compute vt = 1 M1 PM1 i=1 g(xt; s Nt+i). 5: Nt+1 = Nt + M1. 6: else 7: Draw M2 samples and compute vt = vt 1 + 1 M2 PM2 i=1(g(xt; s Nt+i 1) g(xt 1; s Nt+i)). 8: Nt+1 = Nt + M2. 9: end if 10: Set the learning rate ͷt = min n 1 8L, ̈ 4L vt o . 11: xt+1 = xt ͷtvt. 12: end for 13: Output: x T sampled uniformly from {xt}T 1 t=0 . |
| Open Source Code | No | The paper is purely theoretical and has no experiment. (From NeurIPS Paper Checklist) |
| Open Datasets | No | The paper is purely theoretical and has no experiment. (From NeurIPS Paper Checklist) |
| Dataset Splits | No | The paper is purely theoretical and has no experiment. (From NeurIPS Paper Checklist) |
| Hardware Specification | No | The paper is purely theoretical and has no experiment. (From NeurIPS Paper Checklist) |
| Software Dependencies | No | The paper is purely theoretical and has no experiment. (From NeurIPS Paper Checklist) |
| Experiment Setup | No | The paper is purely theoretical and does not have experiments. (From NeurIPS Paper Checklist) |