Search papers, labs, and topics across Lattice.
This paper introduces the unmasking growth complexity (UGC) as a novel measure of data geometry that directly influences Kullback-Leibler (KL) discretization error in masking diffusion for discrete sampling. By analyzing both Bernoulli-subset and fixed-cardinality unmasking schemes, the authors derive optimized sampling schedules that adapt computational effort based on data geometry, leading to certified-optimal samplers with guaranteed KL error bounds. The findings reveal significant dimension-dependent improvements, demonstrating that careful scheduling can yield up to \(\widetilde{\Omega}(\sqrt{d})\) enhancements in sampling efficiency.
Certified-optimal samplers can achieve prescribed KL error with high probability while dramatically improving sampling efficiency through adaptive scheduling based on data geometry.
We study masking diffusion for discrete sampling and introduce a path-resolved measure of data geometry called the \emph{unmasking growth complexity} ({\textsf{UGC}\xspace}). 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 {\textsf{UGC}\xspace} increments can be estimated from samples via KL increments along coupled reveal trajectories. This leads to \emph{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 {\textsf{UGC}\xspace} 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 {\textsf{UGC}\xspace} density determines the sharp leading-order optimal Euler discretization error. Examples exhibit substantial dimension-dependent gains over coarse schedules, including $\widetilde{\Omega}(\sqrt{d})$ improvements achievable with a constant number of adaptively placed blocks.
MIT CSAIL