Research map / Optimization / Nonconvex and smooth optimization

High-probability Convergence of Gradient Methods under Markovian Stochasticity

NeurIPS 2026 · Optimization › Nonconvex and smooth optimization · approach: Stochastic gradient last-iterate analysis

Read the paperCheck your idea against 108,967 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.

Provides the first high-probability convergence guarantees for gradient-based methods under Markovian (dependent) stochastic gradient noise.

Problem

Convergence of stochastic gradient methods under Markovian stochasticity (dependent data streams, reinforcement learning) has been studied in expectation, but high-probability guarantees remain largely unexplored.

Approach

Derives high-probability convergence bounds for gradient methods driven by Markovian samples, moving beyond expectation-only analyses of dependent-data SGD.

Closest papers by meaning

• First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities (NeurIPS 2023 · similarity 0.93)
• Stochastic Gradient Descent under Markovian Sampling Schemes (ICML 2023 · similarity 0.93)
• On Markov Chain Gradient Descent (NeurIPS 2018 · similarity 0.92)
• Improved Lower Bounds for First-order Stochastic Non-convex Optimization under Markov Sampling (ICML 2025 · similarity 0.91)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems (NeurIPS 2020 · similarity 0.91)
• Statistical Guarantees for High-Dimensional Stochastic Gradient Descent (NeurIPS 2025 · similarity 0.90)