Research map / Optimization / Optimizers
Ito Diffusion Approximation of Universal Ito Chains for Sampling, Optimization and Boosting
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 W2 diffusion-approximation bounds for a general Ito chain with state-dependent, non-Gaussian isotropic noise and non-dissipative drift, via window coupling, a new Girsanov variant, and KL-to-W2 conversion.
Problem
Diffusion approximation of Markov chains (Euler-Maruyama-like Ito chains) with non-Gaussian, state-dependent noise, biased drift and no convexity/dissipativity assumptions, covering SGLD, SGD, and gradient boosting.
Approach
Introduces a general Ito chain and bounds its W2 distance to an Ito diffusion by coupling the chain with a Gaussian-noise auxiliary chain via CLT batching and a "window coupling" term that emulates dissipativity, then proves a new Girsanov-type KL bound with state-dependent diffusion and converts KL to W2 with exponential integrability.
Key results
- For SGD with Gaussian noise and gamma=1, alpha>=1, the W2 discretization error is O(eta^{3/4}), improving on the prior W1 rate O(eta^{1/8}) for Gaussian SGD.
- For SGD with general non-Gaussian noise, the paper obtains O(eta^{1/2}) in W2, versus O(eta^{1/8}) in W1 from prior work.
- For SGLD with Gaussian noise, the paper matches the best known rate O(eta^{1/4}) and extends it to non-Gaussian noise without dissipativity.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| extend the SGLD approximation guarantee to arbitrary noise rather than Gaussian noise | Ito chain diffusion approximation · SGLD, any noise | W2 discretization error rate: O(η^{1/4}) | Helped |
| use the proposed bound for Gaussian-noise SGLD instead of the prior bound | SGLD · SGLD, Gaussian noise | W2 discretization error rate: O(η^{1/4}) -> O(η^{1/4}) | No clear effect |
| use the proposed Gaussian-noise SGD bound instead of the prior bound | SGD · SGD, Gaussian noise | W2 discretization error rate: O(η^{1/8}) -> O(η^{3/4}) | Helped |
| use the proposed arbitrary-noise SGD result rather than the prior result | SGD · SGD, any noise | W1 discretization error rate: O(η^{1/8}) -> O(η^{1/4}) | Helped |
| apply the diffusion approximation analysis to stochastic gradient boosting with arbitrary noise | SGB · SGB, any noise | W2 discretization error rate: O(η^{1/2}) | Helped |
Surprising findings
- The horizon-dependent constants grow exponentially in T, which the authors argue is unavoidable without dissipativity, limiting applicability to invariant-measure sampling.
Limitations
- Requires the diffusion coefficient to be uniformly elliptic, excluding some cases handled by prior work.
- Constants grow exponentially in the time horizon, so results do not directly give invariant-measure sampling guarantees.
- Gaussian-noise rate for SGD is claimed only in the strong W2 form under extra conditions (alpha >= 1).
Experimental setup
Metrics: W2 distance bound (theoretical order in step size eta)
Baselines: SGLD diffusion approximation (Gaussian noise) SGD diffusion approximation with W1 bounds SGLB
Builds on: Girsanov theorem Gyongy interpolation theorem SGLD SGLB
Closest papers by meaning
- Stochastic Gradient and Langevin Processes (ICML 2020 · similarity 0.87)
- On Markov Chain Gradient Descent (NeurIPS 2018 · similarity 0.87)
- Itô maps for any-step SDEs (NeurIPS 2026 · similarity 0.85)
- An Efficient High-dimensional Gradient Estimator for Stochastic Differential Equations (NeurIPS 2024 · similarity 0.85)
- The Poisson Midpoint Method for Langevin Dynamics: Provably Efficient Discretization for Diffusion Models (NeurIPS 2024 · similarity 0.85)
- Computing the Bias of Constant-step Stochastic Approximation with Markovian Noise (NeurIPS 2024 · similarity 0.85)
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.