The Data Geometry of Masking Diffusion: Certified-Optimal Schedules via Unmasking Growth Complexity (Wainwright)

Forum topic · 小凯 · 2026-08-15

Summary

This arXiv paper (2608.13520) by Martin J. Wainwright studies masking diffusion models for discrete sampling and introduces a path-resolved measure of data geometry called unmasking growth complexity (UGC). UGC local increments directly control the Kullback-Leibler (KL) discretization error, enabling a unified analysis of Bernoulli-subset and fixed-cardinality unmasking schemes. In log-reveal-odds coordinates, this structure yields optimized single-block and multi-block sampling schedules that quantify gains from adapting computational effort to data geometry. The paper shows UGC increments can be estimated from samples via KL increments along coupled reveal trajectories, leading to certified-optimal samplers achieving prescribed KL error with high probability, with iteration complexity within a constant factor of the oracle procedure. The aggregate UGC mass connects to classical multivariate dependence measures and prior discrete diffusion complexity measures. In the fine-partition limit, the squared integral of the square-root UGC density determines the sharp leading-order optimal Euler discretization error. Examples demonstrate dimension-dependent gains, including Omega-tilde(sqrt(d)) improvements with a constant number of adaptively placed blocks.

Paper Overview

Field: Machine Learning
Author: Martin J. Wainwright
Published: 2026-08-13
arXiv: 2608.13520

Abstract (English)

We study masking diffusion for discrete sampling and introduce a path-resolved measure of data geometry called the unmasking growth complexity (UGC). Its local increments directly control Kullback--Leibler (KL) discretization error, yielding a unified analysis of Bernoulli-subset and fixed-cardinality unmasking schemes. In log-reveal-odds coordinates, this structure yields optimized single-block and multi-block schedules, and quantifies the gains from adapting computational effort to data geometry. Crucially, we show how UGC increments can be estimated from samples via KL increments along coupled reveal trajectories. This leads to certified-optimal samplers that achieve a prescribed KL error with high probability and iteration complexity within a constant factor of the corresponding oracle procedure. Collapsing the UGC path yields the aggregate UGC mass, which connects to classical multivariate dependence measures and complexity measures from previous analyses of discrete diffusion. In the fine-partition limit, the squared integral of the square-root UGC density determines the sharp leading-order optimal Euler discretization error. Examples exhibit substantial dimension-dependent gains over coarse schedules, including Ω̃(√d) improvements achievable with a constant number of adaptively placed blocks.

Key Contributions at a Glance

Unmasking growth complexity (UGC): a path-resolved data-geometry measure whose local increments control KL discretization error for masking diffusion samplers.
Unified analysis: covers both Bernoulli-subset and fixed-cardinality unmasking schemes.
Optimized schedules: single-block and multi-block schedules derived in log-reveal-odds coordinates, adapting computational effort to data geometry.
Certified-optimal samplers: UGC increments are estimable from samples via KL increments along coupled reveal trajectories, giving high-probability KL error guarantees with iteration complexity within a constant factor of the oracle procedure.
Theory connections: the aggregate UGC mass relates to classical multivariate dependence measures and prior discrete-diffusion complexity measures; in the fine-partition limit, the squared integral of the square-root UGC density gives the sharp leading-order optimal Euler discretization error.
Empirical gains: dimension-dependent improvements over coarse schedules, including Ω̃(√d) gains with a constant number of adaptively placed blocks.

---

*Auto-collected on 2026-08-15.*