Research map / Optimization / Nonconvex and smooth optimization
Learning from A Single Markovian Trajectory: Optimality and Variance Reduction
Zhenyu Sun, Ermin Wei
Read the paperCheck your idea against 137,217 papers
AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies stochastic non-convex optimization when samples come from a single Markovian trajectory and proposes a variance-reduced method claimed to be optimal.
Problem
Stochastic non-convex optimization where samples are drawn from a Markov chain along one trajectory, with no prior knowledge or control of the chain, relevant to asynchronous distributed learning and reinforcement learning.
Approach
Treats the worst case where multiple trajectories or i.i.d. sampling are unavailable and the Markov chain cannot be controlled; the abstract indicates the approach achieves optimality and reduces variance for learning from a single Markovian trajectory.
Closest papers by meaning
- Improved Lower Bounds for First-order Stochastic Non-convex Optimization under Markov Sampling (ICML 2025 · similarity 0.94)
- Stochastic Gradient Descent under Markovian Sampling Schemes (ICML 2023 · similarity 0.91)
- Accelerating Distributed Stochastic Optimization via Self-Repellent Random Walks (ICLR 2024 · similarity 0.90)
- Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift (NeurIPS 2026 · similarity 0.88)
- Achieving $\tilde{O}(1/\epsilon)$ Sample Complexity for Constrained Markov Decision Process (NeurIPS 2024 · similarity 0.88)
- Faster Stochastic Optimization with Arbitrary Delays via Adaptive Asynchronous Mini-Batching (ICML 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
