Research map / Optimization / Nonconvex and smooth optimization

Improved Lower Bounds for First-order Stochastic Non-convex Optimization under Markov Sampling

ICML 2025 · Optimization › Nonconvex and smooth optimization · approach: Stochastic convex optimization complexity

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proves sample-complexity lower bounds for first-order non-convex stochastic optimization under Markovian sampling (Ω(ϵ⁻⁴) for countable-state chains, Ω(ϵ⁻²) for finite-state chains) and proposes MaC-SAGE, a SAG-style algorithm that nearly matches the finite-state bound.

Problem

Sample complexity of finding epsilon-approximate critical points of smooth non-convex stochastic objectives when samples come from a Markov chain rather than i.i.d. draws; prior work had only loose lower bounds in the non-convex Markovian setting.

Approach

Builds hard instances on Markov chains with bounded hitting time (splitting states probabilistically for the countable case) and uses a progress-function argument to lower bound samples; for finite chains, MaC-SAGE tracks state-occurrence frequencies to reweight per-state gradients in a SAG-like estimator, achieving near-matching ~O(max{τ,τmix} ϵ⁻²) complexity.

Key results

• Lower bound Ω(τσ²/ϵ⁴ · min{c1σ², c2 L∆}) type scaling for countable-state stationary Markov chains (Theorem 3.1), i.e., Ω(ϵ⁻⁴) order.
• Finite-state lower bound Ω(τϵ⁻²) (Theorem 4.2) for finite stationary Markov chains.
• MaC-SAGE achieves E[min_t ||∇F(x_t)||²] = O(τL∆/T) + Õ(τ̃σ²/T), i.e., Õ(τ̃ϵ⁻²) sample complexity, nearly matching the finite-state lower bound.

Measured effects reported in the paper

Limitations

• Countable-state lower bound relies on a constructed hard instance and differs in function/oracle class from the finite-state result, leaving a gap in the finite case between Ω(ϵ⁻²) and the countable Ω(ϵ⁻⁴).
• MaC-SAGE is only analyzed for finite-state chains; no experiments are reported.

Experimental setup

Metrics: sample complexity expected gradient norm

Baselines: MC-SGD MAG Randomized ExtraGradient

Builds on: SAG Arjevani et al. 2023 lower bound construction MC-SGD Randomized ExtraGradient

Closest papers by meaning

• The Sample Complexity of Gradient Descent in Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.89)
• Near-Optimal Sample Complexity for MDPs via Anchoring (ICML 2025 · similarity 0.89)
• Sample-and-Bound for Non-convex Optimization (AAAI 2024 · similarity 0.89)
• Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift (NeurIPS 2026 · similarity 0.89)
• Accelerating Distributed Stochastic Optimization via Self-Repellent Random Walks (ICLR 2024 · similarity 0.88)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity (NeurIPS 2024 · similarity 0.88)