Reproduce “Discrete Flow Matching: Convergence Guarantees Under Minimal Assumptions” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Le-Tuyet-Nhi Pham, Giovanni Conforti, Zhenjie Ren, Alain Durmus
The authors analyze a learned-rate, time-discretized sampler for discrete flow matching, using nearest-neighbor and uniform reference walks. Under M1, an integrated approximation-loss bound, they prove an O(ε²) KL guarantee to the early-stopped target and a total-variation guarantee to the true target. Iteration bounds are Õ(d²/ε²) for uniform walks and Õ(d²m²/ε²) for nearest-neighbor walks; these are not empirical speed claims.
Key insights
- Non-asymptotic convergence guarantees for DFM can be achieved under a minimal 'approximation error' assumption on the learned score, relaxing previous restrictive conditions on score boundedness.
- The choice of reference dynamics significantly influences convergence rates and scalability, with URW dynamics demonstrating improved dependence on vocabulary size (m) compared to NNRW.
- The DFM score function is uniformly bounded on $[0, 1-\eta]$, which is crucial for controlling logarithmic terms in divergence calculations and enabling rigorous analysis of discretization errors.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.