The data geometry of masking diffusion: Certified-optimal schedules via unmasking growth complexity
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Ω(\sqrt{d})$ improvements achievable with a constant number of adaptively placed blocks.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
CR-UTP: Certified Robustness against Universal Text Perturbations on Large Language Models
It is imperative to ensure the stability of every prediction made by a language model; that is, a language's prediction should remain consistent despite minor input variations, like word substitutions. In this paper, we …
Language ModellingRevisiting Image Classifier Training for Improved Certified Robust Defense against Adversarial Patches
Certifiably robust defenses against adversarial patches for image classifiers ensure correct prediction against any changes to a constrained neighborhood of pixels. PatchCleanser arXiv:2108.09135 [cs.CV], the state-of-th…
Robust classificationGeoComplete: Geometry-Aware Diffusion for Reference-Driven Image Completion
Reference-driven image completion, which restores missing regions in a target view using additional images, is particularly challenging when the target view differs significantly from the references. Existing generative …
Point CloudsLoad--Reserve Wasserstein Propagation for Isotropic Diffusion Samplers
Many Wasserstein analyses of diffusion samplers control reverse-time propagation by global stability summaries of the learned drift. These summaries can hide radial geometry: equal-height expansive regions of different w…
Double Bubble, Toil and Trouble: Enhancing Certified Robustness through Transitivity
In response to subtle adversarial examples flipping classifications of neural network models, recent research has promoted certified robustness as a solution. There, invariance of predictions to all norm-bounded attacks …
Open-Ended Question Answering