Research map / Optimization / Nonconvex and smooth optimization
Deep Learning for Computing Convergence Rates of Markov Chains
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.
Proposes DCDC, a neural-network sample-based solver for the Contractive Drift Equation whose solution yields explicit Wasserstein convergence bounds for general state-space Markov chains.
Problem
Bounding the convergence rate to stationarity in Wasserstein distance for general state-space Markov chains, where traditional analytical drift/minorization methods give impractically conservative or closed-form-only bounds.
Approach
Recasts the contractive drift inequality KV <= V - U as an equality (Contractive Drift Equation) whose solution gives an explicit exponential convergence bound, and solves it with a neural network trained by SGD using an unbiased gradient estimator for the squared integrated residual.
Key results
- For regularized SGD logistic regression, DCDC yields W(X_n, X_inf) <= 8.1(1-1.07e-3)^n when X_0=0.
- For the tandem fluid network, DCDC gives the bound W(X_n, X_inf) <= 5.67(1-0.017)^n when X_0=0.
- Sample complexity: N=O(1/(delta eps^2)) samples and M=O(log(1/eps)/(delta eps^d)) grid points for a uniform CDE certificate with probability 1-delta.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| capture the intrinsic contraction contribution in addition to regularization | DCDC on mini-batch SGD for logistic regression · Mini-batch SGD for logistic regression | exponential rate contribution: 7×10^{-5} | Helped |
Surprising findings
- Directly solving KV = rV for a fixed rate r is hard for DCDC even for conservative r close to 1, motivating the CDE with U formulation.
Limitations
- Theory and experiments are restricted to compact state spaces (or chains with compact absorbing sets); non-compact extension is left for future work.
- Convergence bounds rely on the CDE approximately holding; uniform verification requires the sample-based certification with high probability.
- Lower bounds on sample complexity are not established.
Experimental setup
Datasets: synthetic logistic regression data (100 points) simulated tandem fluid network transitions simulated regulated random walk
Benchmarks: mini-batch SGD logistic regression with L2 regularization tandem fluid network two-sided regulated random walk
Metrics: exponential convergence rate pre-multiplier C in Wasserstein bound residual max/mean/std of K V - V
Builds on: contractive drift condition physics-informed neural networks drift and minorization conditions
Closest papers by meaning
- Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift (NeurIPS 2026 · similarity 0.86)
- Improved Lower Bounds for First-order Stochastic Non-convex Optimization under Markov Sampling (ICML 2025 · similarity 0.85)
- Efficient Training of Neural Stochastic Differential Equations by Matching Finite Dimensional Distributions (ICLR 2025 · similarity 0.85)
- The Collusion of Memory and Nonlinearity in Stochastic Approximation With Constant Stepsize (NeurIPS 2024 · similarity 0.85)
- Distances for Markov chains from sample streams (NeurIPS 2025 · similarity 0.84)
- Coupling-based Convergence Diagnostic and Stepsize Scheme for Stochastic Gradient Descent (AAAI 2025 · similarity 0.84)
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.