Research map / Probabilistic and scientific modeling / Differential equations and PDEs
Generalization Bounds for Heavy-Tailed SDEs through the Fractional Fokker-Planck Equation
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 computable high-probability generalization bounds for heavy-tailed (alpha-stable) SDEs by bounding the KL divergence via entropy flow of the fractional Fokker-Planck equation, and identifies a dimension-dependent phase transition in the tail index.
Problem
Generalization error of heavy-tailed stochastic optimization modeled by Levy-driven SDEs; prior bounds were only expected or contained non-computable information-theoretic terms and had poor dimension dependence.
Approach
Uses the fractional Fokker-Planck equation and entropy-flow decomposition to bound the KL divergence between the SDE's law and a heavy-tailed stationary prior, yielding high-probability PAC-Bayesian bounds with explicit constants, a better dimension dependence, and a heavy-tail phase transition controlled by sigma_1 sqrt(d/R^2).
Key results
- Bound is high-probability and computable, with K_{alpha,d} having dimension dependence d^{1-alpha/2} versus the prior R_{alpha,d}=O(d^{(1+alpha)/2}).
- Phase transition predicted at sigma_1 sqrt(d_0) = 1 (heavy regime below, light regime above); empirical sign change of Kendall's tau between tail index and accuracy gap occurs near d ~ 8e4 on MNIST FCN2.
- Estimated bound with R=15 gives near-perfect correlation with the accuracy gap in FCN2 MNIST experiments; the bound over-estimates the gap because it grows with T.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| increase tail heaviness (lower α) | FCN2 · MNIST accuracy gap; heavy regime (d below the transition near 8 · 10^4) | accuracy gap | Helped |
| increase tail heaviness (lower α) | FCN2 · MNIST accuracy gap; light regime (d above the transition near 8 · 10^4) | accuracy gap | Hurt |
| use R values estimated from the phase-transition experiment instead of the default R=1 | FCN2 generalization-bound estimate · MNIST | correlation with accuracy gap | Helped |
| set R=15 rather than R=1 | FCN2 generalization-bound estimate · MNIST | correlation with accuracy gap | Helped |
| estimate α from the dimension-scaling regression of the accuracy gap | FCN2 · MNIST | tail-index estimate correlation with ground-truth α | Helped |
| estimate α from the dimension-scaling regression of the accuracy gap | FCN2 · MNIST | tail-index estimate bias | Hurt |
Surprising findings
- Heavy tails can be beneficial or harmful for generalization depending on the regime (dimension and noise scale), i.e. a phase transition.
- The bound is time-dependent and over-estimates the accuracy gap, since it increases with the horizon T.
Limitations
- Bound grows with time horizon T (not time-uniform); time-uniform variant involves hard-to-compute terms.
- Constant R must be assumed positive and not too small, and is not formally estimated.
- Assumes full-batch dynamics; the effect of small batches and SGD-induced heavy tails is not covered.
Experimental setup
Datasets: MNIST FashionMNIST CIFAR10
Benchmarks: MNIST FashionMNIST CIFAR10
Metrics: accuracy gap Kendall's tau correlation Pearson correlation estimated tail index
Baselines: Raj et al. heavy-tailed SDE stability bound
Builds on: PAC-Bayesian bounds Langevin dynamics generalization bounds (Rotskoff/Chen-type entropy flow) Euler-Maruyama discretization generalized log-Sobolev inequalities for infinitely divisible distributions
Closest papers by meaning
- Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.89)
- Emergence of heavy tails in homogenized stochastic gradient descent (NeurIPS 2024 · similarity 0.88)
- Non-Asymptotic and Non-Lipschitzian Bounds on Optimal Values in Stochastic Optimization Under Heavy Tails (ICML 2025 · similarity 0.88)
- Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions (NeurIPS 2024 · similarity 0.88)
- High-Probability Bound for Non-Smooth Non-Convex Stochastic Optimization with Heavy Tails (ICML 2024 · similarity 0.87)
- Error Analysis Affected by Heavy-Tailed Gradients for Non-Convex Pairwise Stochastic Gradient Descent (AAAI 2025 · similarity 0.87)
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.