Paper deep dive
The data geometry of masking diffusion: Certified-optimal schedules via unmasking growth complexity
Martin J. Wainwright
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 8/16/2026, 2:37:09 AM
Summary
This paper introduces Unmasking Growth Complexity (UGC), a path-resolved measure of data geometry for discrete masking diffusion sampling. UGC local increments control Kullback-Leibler (KL) discretization error, enabling the design of certified-optimal single-block and multi-block sampling schedules. The authors demonstrate that UGC can be estimated from samples via KL increments, allowing for adaptive computational effort allocation. This approach yields significant dimension-dependent improvements over coarse schedules, achieving \(\widetilde{\Omega}(\sqrt{d})\) gains.
Entities (7)
Relation Signals (5)
Martin J. Wainwright → authored → The data geometry of masking diffusion: Certified-optimal schedules via unmasking growth complexity
confidence 99% · The data geometry of masking diffusion: Certified-optimal schedules via unmasking growth complexity Martin J. Wainwright
Unmasking Growth Complexity → controls → Kullback-Leibler Discretization Error
confidence 95% · Its local increments directly control Kullback--Leibler (KL) discretization error
Unmasking Growth Complexity → enables → Certified-optimal Schedules
confidence 92% · This leads to certified-optimal samplers that achieve a prescribed KL error with high probability
Unmasking Growth Complexity → unifies → Bernoulli-subset Unmasking
confidence 90% · yielding a unified analysis of Bernoulli-subset and fixed-cardinality unmasking schemes.
Unmasking Growth Complexity → unifies → Fixed-Cardinality Unmasking
confidence 90% · yielding a unified analysis of Bernoulli-subset and fixed-cardinality unmasking schemes.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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.
Tags
Links
- Source: https://arxiv.org/abs/2608.13520v1
- Canonical: https://arxiv.org/abs/2608.13520v1
Trouble viewing inline? Open PDF directly →
Full Text
295,546 characters extracted from source content.
Expand or collapse full text
The data geometry of masking diffusion: Certified-optimal schedules via unmasking growth complexity Martin J. Wainwright mjwain@mit.edu Lab for Information and Decision Systems Statistics and Data Science Center EECS and Mathematics, Massachusetts Institute of Technology August 13, 2026 Abstract 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) ( d) improvements achievable with a constant number of adaptively placed blocks. 1 Introduction The problem of sampling from a high-dimensional distribution is fundamental in nature, and has a wide range of applications. Efficient sampling algorithms underpin the utility of Monte Carlo approximation [39, 42]; support uncertainty quantification in Bayesian models [18, 6]; and lie at the heart of generative AI [40, 16, 54, 13]. Recent years have witnessed tremendous practical and theoretical advances in the use of diffusion11 1 In full generality, the diffusion terminology is a misnomer, since not all such models involve a diffusion process in the formal probabilistic sense; this includes the unmasking models studied in this paper. Nonetheless, we adopt the conventional terminology. sampling algorithms, which generate samples via a sequence of “denoising” operations [45, 46, 23, 47, 14, 12, 5]. Initial work in the area focused on sampling from continuous distributions in d, in which case the denoising step corresponds to estimating a signal embedded in Gaussian noise [23, 47]. A more recent line of work, and the general focus of this paper, has focused on sampling from discrete distributions, using various kinds of denoising processes [24, 3, 9, 31, 44, 43, 15, 17]. In this paper, we study the problem of sampling a random vector Z∈()dZ∈(A)^d, where A is a discrete alphabet, and d is the ambient dimension. While various samplers have been devised, we focus on unmasking samplers, which traverse a path from a fully unobserved vector, denoted by Z∗=(⋆,…,⋆)Z^*=( ,…, ) with ⋆ meaning masked or unobserved, back to a sample Z∼ℙZ _Z from the target distribution. The path is traversed via a sequence of unmasking operations, in which a subset of the masked coordinates are revealed. Unmasking algorithms differ in the form and sequence by which these unmasking steps take place. Unmasking and closely related mask-based generative samplers have proven effective across a range of applications, including machine translation [19], image and video synthesis [11, 55], text-to-image generation [10], speech synthesis [52], language modeling [43, 33], and protein design [51]. 1.1 Overview This paper is motivated by two broad questions associated with diffusion samplers, as articulated in our companion paper on Gaussian diffusion [50], which we paraphrase here: Q1: Can the performance of masked diffusion sampling be explained and quantified, in some generality, by a measure tied to data geometry? Q2: Is it possible to exploit a masked-diffusion measure of data geometry to design, optimize and certify practical sampling schemes? Recent work has made substantial progress on both questions. Chen et al. [15] analyze fixed-cardinality unmasking and derive an exact information-profile representation of its expected KL discretization error, with consequences for schedule design and bounds based on total and dual total correlation. Lavenant and Zanella [25] derive an information-profile representation of the factorization error for random-order unmasking, and study optimal schedules in asymptotic scaling regimes. From a different direction, Dmitriev et al. [17] analyze discrete diffusion via a continuous-time Markov chain (CTMC) formulation; for masking diffusion, their modified τ-leaping guarantees are governed by an effective total correlation that can be substantially smaller than the classical worst-case measures. Collectively, these results provide important answers to Q1 and partial answers to Q2, but fall short of finite-sample guarantees for learning and certifying geometry-adaptive schedules from data. Our answer to Q1 is based on the unmasking growth complexity or UGC for short. It is a path-resolved measure of data dependence along the reveal process. We show that its local increments directly control KL discretization error, thereby obtaining a common analysis of both fixed-cardinality unmasking and a natural Bernoulli-subset variant. When collapsed over the full reveal path, the UGC complexity reduces to a coarse measure that closely connected to classical multivariate dependence measures [53, 21, 22, 48], as well as to the effective total correlation appearing in the CTMC analysis [17]. Consequently, the resulting single-block guarantees sharpen existing fixed-cardinality bounds while giving Bernoulli unmasking guarantees comparable to those available for CTMC samplers. The main contributions of our paper are in the context of Q2, and in particular, our use of the full UGC complexity path to design and analyze sampling algorithms that are certified-optimal. More precisely, we show that UGC complexity has a natural additive structure along the reveal path, so that its local increments can be estimated from samples and used to allocate computational effort where the target distribution is most difficult to unmask. We exploit this structure to derive and optimize blockwise schedules, construct data-dependent samplers with high-probability KL certificates, and finally, to optimize the block boundaries themselves. In the fine-partition limit, the log-reveal-odds UGC density emerges as the intrinsic local geometry: its square-root integral governs the limiting partition complexity and the sharp leading-order optimal Euler discretization error. 1.2 Related work So as to put our results in context, we now provide a broader discussion of related work. There are various types of discrete diffusion models, all of which replace the additive Gaussian noise for continuous-space diffusions by stochastic corruption kernels on discrete state spaces. Early work developed multinomial and more general structured discrete diffusion processes [24, 3], among them the absorbing-state corruption that underlies a masking diffusion process. Other work [9] formulated discrete diffusion models using the formalism of continuous-time Markov chains, with subsequent work developing discrete analogues of score-based modeling in which the reverse CTMC is parameterized through learned probability ratios [31]. Masked diffusion is a particularly important subclass, in which coordinates are corrupted by replacement with a distinguished mask symbol and generation proceeds by progressively reconstructing masked coordinates [44, 43]. As described above, recent work has made progress on characterizing the accuracy–parallelism trade-off in random-order unmasking with fixed-cardinality subsets. In particular, Li and Cai [26] established information-theoretic convergence guarantees for parallel masked-diffusion sampling. Chen et al. [15] derived an exact characterization of the expected KL divergence in terms of a one-dimensional information profile; they also gave explicit sampling guarantees involving classical multivariate dependence measures [53, 21, 22], namely the total correlation ( TC) and dual total correlation ( DTC). A portion of our analysis exploits their exact KL representation. Lavenant and Zanella [25] derived an information-profile representation for the factorization error of random-order unmasking, and then studied optimal scheduling via a continuum scaling limit. We compare their asymptotic schedule analysis more closely with our fine-partition and Euler results following Theorem 3. The τ-leaping method for continuous-time Markov chains (CTMC) originates in stochastic chemical kinetics, where its consistency and approximation errors have been studied extensively [20, 36, 27, 2]. For discrete diffusion, recent work has developed convergence guarantees for τ-leaping under both standard and absorbing corruption processes [37, 28, 29, 17], as well as higher-order variants of CTMC discretization [38]. Among CTMC analyses, most related to our work is the paper of Dmitriev et al. [17], who analyze a modified τ-leaping sampler for a general class of CTMC discrete diffusion models. For masking diffusion, they give guarantees in terms of a measure that they call effective total correlation, which turns out to be closely related to the coarse UGC complexity that we introduce. In contrast to CTMC-based analyses, we study Bernoulli and fixed-cardinality unmasking; our coarse UGC bounds yield matching guarantees for these direct schemes. The coarse UGC complexity is also connected to several multivariate dependence measures, including TC, DTC, and the finer-grained measure of Tononi et al. [48]. We develop these connections in Appendix A. Finally, in our companion paper [50] on Gaussian diffusion sampling, we introduced the denoising growth complexity (DGC), a pathwise complexity that controls KL discretization error, and whose log-scale DGC density specifies optimal sampling schedules. Despite the substantial differences between Gaussian and masking diffusion, the two theories exhibit a remarkable degree of parallelism, suggesting a common underlying principle linking denoising growth, KL discretization error, and optimal scheduling. 2 Overview: unmasking growth complexity and sampling So as to orient the reader, we begin by providing a high-level overview of the main ideas and quantities underlying our analysis. We first describe the canonical unmasking process. Using it, we define the unmasking growth complexity (UGC), which measures how informational difficulty is distributed along the reveal path. We then pass to log-reveal-odds coordinates, where this complexity is represented by a density whose geometry determines how sampling effort should be allocated along the path. Our goal here is primarily conceptual: to explain the distinction between coarse and geometry-aware schedules, to illustrate the data geometry of the UGC density on several examples, and to preview how data-driven adaptive partitioning can exploit this geometry. Precise forms of our guarantees for samplers, estimation procedures, and supporting technical results are developed in the subsequent sections. 2.1 Unmasking reveal process Given a discrete alphabet A, our goal is to sample a d-dimensional random vector Z∈dZ ^d with distribution ℙZP_Z. Underlying the sampling algorithms that we analyze is an unmasking stochastic process Xt,t∈[0,1]\X_t,t∈[0,1]\, where Xt∈(∪⋆)dX_t∈ (A∪\ \ )^d and the new symbol ⋆ denotes a masked or unobserved entry. At time t=0t=0, we have X0=(⋆,…,⋆)X_0=( ,…, ) almost surely, whereas at time t=1t=1, we have X1∼ℙZX_1 _Z, where ℙZP_Z is the target distribution from which we would like to sample. The evolution of XtX_t along the path is controlled by a sequence Uii=1d\U_i\_i=1^d of i.i.d. Unif[0,1]Unif[0,1] random variables, independent of Z. These variables define the reveal subset sequence, indexed by t∈[0,1]t∈[0,1], via Rt R_t ≔i∈[d]∣Ui≤t,and its complementRtc≔[d]∖Rt. \i∈[d] U_i≤ t \, and its complement R_t^c [d] R_t. (1a) The subset RtR_t corresponds to the subset of coordinates i for which the hidden value ZiZ_i has been revealed by time t. More formally, the unmasking process at time t is given by Xt X_t ≔(ZRt,ZRtc⋆)∈(∪⋆)dfor t∈[0,1], (Z_R_t,\;Z _R^c_t )\;∈\; (A∪\ \ )^d for $t∈[0,1]$, (1b) where ZRt=(Zi,i∈Rt)Z_R_t=(Z_i,i∈ R_t) are the variables revealed by time t, and ZRtc⋆=(⋆,…,⋆)Z _R^c_t=( ,…, ) is a sub-vector of missing values in positions indexed by RtcR_t^c. By construction, the unmasking process (1b) defines a family of probability distributions ℙt,t∈[0,1]\P_t,t∈[0,1]\, where ℙ0P_0 denotes a degenerate distribution with all its mass on the masked sequence, whereas ℙ1≡ℙZP_1 _Z is the probability distribution of the target variable Z. 2.2 Unmasking growth complexity and its geometry For a reveal time t∈[0,1]t∈[0,1], we define the Bernoulli unmasking gain (t) h(t) ≔∑i=1dInfo(Zi;Xt∣i∈ℳ(Xt)), \; _i=1^dInfo (Z_i;X_t i (X_t) ), (2a) where ℳ(Xt)⊆1,…,dM(X_t) \1,…,d\ is the subset of indices that are masked at reveal time t, and InfoInfo denotes the (conditional) mutual information. The function h has a denoising interpretation, since when i∈ℳ(Xt)i (X_t), all other coordinates in XtX_t are revealed independently with probability t; the conditional mutual information term for the ithi^th coordinate measures how much these revealed variables reduce uncertainty about ZiZ_i. Moreover, the derivative ′ h turns out to have a simple information-theoretic representation: in particular, it corresponds to the second derivative ′(t) h (t) =−d2dt2Info(Z;Xt), =- d^2dt^2Info(Z;X_t), (2b) where Info(Z,Xt)Info(Z;X_t) denotes the mutual information between the target vector Z∈dZ ^d and the partially unmasked vector Xt∈(∪⋆)dX_t∈ (A∪\ \ )^d at reveal time t∈(0,1)t∈(0,1). See equation (51a) in the proof of Theorem 1 for the underlying details. In terms of this mutual information derivative, the unmasking growth complexity assigns a non-negative number to any sub-interval [p,q][p,q] of the unit interval [0,1][0,1] via (p,q) H(p,q) ≔∫pqt(1−t)′(t)dtfor any 0≤p<q≤1. _p^qt(1-t) h (t)\,dt for any $0≤ p<q≤ 1$. (2c) Based on the identity (2b), we see that (p,q) H(p,q) is a weighted integral of the information curvature. The essential feature of this complexity measure is that it is a path-resolved quantity: rather than assigning a single complexity to the target distribution ℙZP_Z, it assigns a complexity to every interval of the reveal path. Our analysis shows how these local increments directly control the associated KL discretization error. Moreover, for any triple 0≤p<q<r≤10≤ p<q<r≤ 1, we have the additivity property (p,r) H(p,r) =(p,q)+(q,r). = H(p,q)+ H(q,r). (3) This additivity allows the global sampling problem to be decomposed into local pieces, whose complexities can be estimated and controlled separately, and is what ultimately enables geometry-adaptive refinement of the sampling schedule. By collapsing the path-resolved complexity to the full interval [0,1][0,1], we obtain the aggregate UGC mass given by (0,1)=∫01t(1−t)′(t)t H(0,1)= _0^1t(1-t) h (t)dt. Interestingly, this aggregate quantity has several connections to classical measures of multivariate dependence. By a non-trivial argument (see the proof of Proposition 3), it turns out to be equivalent to a multivariate dependence measure, first introduced by Tononi, Sporns and Edelman [48] in 1994, which spawned a rich line of work (e.g., [7, 8, 34, 4, 41, 49]). A separate argument shows its close relation to the effective total correlation introduced by Dmitriev et al. [17] in their study of CTMC unmasking algorithms. Moreover, the value (0,1) H(0,1) can be upper bounded by classical measures of multivariate dependence [53, 21, 22], known as total correlation and dual total correlation. We elaborate upon these and other connections in Appendix A. Role of the log-reveal-odds density: The natural coordinate for progress along the unmasking path is not reveal time t nor its logarithm, but rather the log-reveal-odds λ=φ(t)≔log(t/(1−t))λ= (t) (t/(1-t)). Our analysis gives one-step KL bounds governed by the multiplicative change in reveal odds; consequently, equal increments in λ correspond to equal multiplicative changes in reveal odds, and place the early and late stages of unmasking on a common scale. Expressing the UGC complexity in this coordinate yields a density q that localizes the informational difficulty of sampling along the path. As our results show, regions where (λ) q(λ) is large require finer resolution. More precisely, the log-reveal-odds UGC density function is given by (λ) q(λ) ≔r2(1−r)2′(r)where r=φ−1(λ)≔eλ1+eλ. r^2(1-r)^2 h (r) where $r= ^-1(λ) e^λ1+e^λ$. (4) By construction, the UGC increment is given by (p,q)=∫φ(p)φ(q)(λ)λ H(p,q)= _ (p) (q) q(λ)\,dλ. The high-level conclusions of this paper take a particularly simple form in terms of q. We focus on the canonical reveal interval [1d, 1−1d] [ 1d,\;1- 1d ], which corresponds under the log-reveal-odds transformation to the symmetric interval [−ℓd,ℓd][- _d, _d] with ℓd≔log(d−1) _d (d-1). • Single-block unmasking schemes use a single multiplier across the reveal path and hence ignore the location of the UGC mass. Their iteration complexity is governed by the coarse or aggregate UGC complexity UGC C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$ ≔2ℓd∫−ℓdℓd(λ)λ. 2 _d _- _d _d q(λ)\,dλ. (5a) The measure UGC C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$ depends only on the total UGC mass over the relevant portion of the path, and not on how this mass is distributed. This coarse measure connects directly to past work: it enables us to show that a single-block Bernoulli unmasking sampler matches the guarantees given for CTMC unmasking [17], while sharpening guarantees from past work on fixed-cardinality sampling [15]. See Corollary 1 and Proposition 3 for details. • Geometry-aware schemes exploit the local UGC geometry, taking finer steps where q is large and coarser steps where it is small. Crucially, we show that UGC increments can be estimated from samples, and use these estimates to choose the partition adaptively from data (see Proposition 2). Under progressive refinement, the resulting complexity converges from above to the fine-partition complexity UGC P_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$ ≔(∫−ℓdℓd(λ)λ)2, ( _- _d _d q(λ)dλ )^2, (5b) We establish non-asymptotic convergence rates and high-probability finite-sample guarantees for the resulting samplers; see Theorems 2 and 3 for details. A related square-root structure for an information profile appears in the asymptotic analysis of fixed-cardinality schedules by Lavenant and Zanella [25]; we discuss this connection in more detail following Theorem 3. In summary, the potential gain from data-dependent optimization of the sampling schedule is governed by the ratio Ratio(ℙZ) (P_Z) ≔UGCUGC=2ℓd∫−ℓdℓd(λ)λ(∫−ℓdℓd(λ)λ)2≥(i) 1, C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$ P_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$\;=\; 2 _d _- _d _d q(λ)\,dλ ( _- _d _d q(λ)dλ )^2\; (i)≥\;1, (6) where the lower bound (i) follows from the Cauchy–Schwarz inequality. Equality holds if and only if q is constant, whereas larger values of Ratio(ℙZ)Ratio(P_Z) arise when the UGC mass is unevenly distributed or sharply concentrated along the path. 2.2.1 Geometric behavior of UGC density Since the UGC density q captures the essential structure of the problem, it is useful to compute and plot it for three different ensembles, each chosen to illustrate a qualitative aspect of our theory. Noisy repeated bit: We begin with a very simple example. For any p∈[0,1]p∈[0,1], we use V∼Ber(p)V Ber(p) to denote a Bernoulli random variable with ℙ(V=1)=pP(V=1)=p and ℙ(V=0)=1−pP(V=0)=1-p. In this ensemble, we construct a binary random vector Z=(Z1,…,Zd)∈0,1dZ=(Z_1,…,Z_d)∈\0,1\^d by first drawing U∼Ber(1/2)U Ber(1/2), and then setting Zi Z_i =U⊕Wifor each i=1,…,d, =U W_i for each $i=1,…,d$, where each WiW_i is an independent Ber(η) Ber(η)-variable for some η∈[0,1/2]η∈[0,1/2], and ⊕ denotes addition modulo two. By construction, we have ℙ(Zi=U)=1−ηP(Z_i=U)=1-η, hence our use of the term “noisy repeated bit”. (a) (b) (c) Figure 1: Plots of the log-reveal-odds UGC density q for the noisy repeated-bit ensemble for η∈0.01,0.30,0.45η∈\0.01,0.30,0.45\. The density has a sharp peak for η=0.01η=0.01, and then flattens out and shifts to the right as η→0.5η→ 0.5. Up to two digits of accuracy, we have Ratio(ℙZ)∈4.51,2.16,1.65Ratio(P_Z)∈\4.51,2.16,1.65\ in panels (a), (b), and (c), respectively. For this example, we have Ratio(ℙZ)≍log(d)Ratio(P_Z) (d) as the dimension grows. Figure 1 gives plots of the UGC density (4) in dimension d=128d=128, and flip probabilities η∈0.01,0.30,0.45η∈\0.01,0.30,0.45\. For η=0.01η=0.01, the density has a sharp peak at a low value of the log-reveal-odds parameter λ. As η increases, the dependence among the coordinates of the multivariate random vector Z∈0,1dZ∈\0,1\^d decreases; it takes a higher reveal level before information about the hidden bit U is revealed, as reflected by the rightward shift in the mode of the UGC density. In parallel with this rightward shift, the entire density collapses towards zero, so that (0,1)→0 H(0,1)→ 0 as η→1/2η→ 1/2. Discrete mixture models: Our second ensemble corresponds to the discrete analog of a mixture model. More precisely, given a fixed set of M cluster centers, say C1,…,CM∈0,1dC^1,…,C^M∈\0,1\^d, we generate a binary random vector Z=(Z1,…,Zd)∈0,1dZ=(Z_1,…,Z_d)∈\0,1\^d with components Zi=CiJ⊕ξiZ_i=C^J_i _i for i=1,…,di=1,…,d, where the random cluster index J is drawn uniformly at random from 1,…,M\1,…,M\ and the ξi∼Ber(η) _i Ber(η) are drawn i.i.d., and independently of the cluster index. This procedure generates an M-component mixture distribution with uniform weight 1/M1/M on each component. (a) (b) (c) Figure 2: Plots of the log-reveal-odds UGC density q for the discrete mixture model. For each dimension d, the latent vector Z∈0,1dZ∈\0,1\^d is generated by selecting uniformly from M=2d/4M=2^d/4 cluster centers, and then flipping each coordinate independently with probability η=0.02η=0.02. Panels (a)–(c) correspond to d∈32,48,64d∈\32,48,64\, and hence M∈256,4096,65536M∈\256,4096,65536\, respectively. Increasing the dimension produces a progressively sharper and taller spike. Up to two digits of accuracy, we have Ratio(ℙZ)∈2.19,3.13,3.85Ratio(P_Z)∈\2.19,3.13,3.85\ in panels (a), (b), and (c), respectively. For this example, it can be shown that Ratio(ℙZ)=Θ~(d)Ratio(P_Z)= ( d) as the dimension grows. We studied this family for varying dimensions d divisible by four, number of mixture components M=2d/4M=2^d/4, and cluster centers sampled independently and uniformly from the Boolean hypercube 0,1d\0,1\^d. Figure 2 shows a sequence of UGC densities for this family, with the dimension d and the number M=2d/4M=2^d/4 of mixture components increasing as we move from left to right. The density is unimodal in all cases; as the dimension increases, the peak location remains fixed but its height increases. It can be shown that the ratio (6) scales as Ratio(ℙZ)=Θ~(d)Ratio(P_Z)= ( d), so that there are significant gains from using geometry-aware stepsizes. Moreover, since the UGC density is concentrated around a single increasingly narrow transition window, a partition with only K=3K=3 blocks—one covering this transition and two covering its tails—achieves the fine-partition complexity up to logarithmic factors. See Section 2.2.2 and Figure 2 for further discussion of these factors. Hierarchical mixture model: The previous examples, being quite simple in nature, all led to unimodal UGC densities. We now consider a hierarchical model in which multiple peaks emerge, and the peaks have interesting meanings in terms of the underlying data geometry. (a) (b) (c) (d) Figure 3: Hierarchical binary-prototype mixtures and their log-reveal-odds UGC densities. The rows correspond to hierarchy depths L=2L=2 and L=4L=4. Left column panels (a) and (c) show the leaf prototypes, while right column panels (b) and (d) show the corresponding UGC densities q. For an integer L≥2L≥ 2, we construct a model that places mass on exactly 2L2^L prototypes in the Boolean hypercube 0,1d\0,1\^d, say V1,…,VM\V^1,…,V^M\, where M=2LM=2^L. Each prototype is defined by a path down a binary tree of depth L; see the left column of Figure 3 for some examples. The geometry of the prototypes is related to the tree structure in the following way: for any tree level ℓ∈1,…,L ∈\1,…,L\, a pair of prototypes VaV^a and VbV^b whose corresponding tree paths first diverge at level ℓ of the tree are separated by Hamming distance Δℓ _ , for some pre-specified set of distances Δℓ=1L\ _ \_ =1^L, and total dimension d=∑ℓ=1LΔℓd= _ =1^L _ . Panel (a) of Figure 3 shows a toy example with L=2L=2, (Δ1,Δ2)=(12,2)( _1, _2)=(12,2), and dimension d=12+2=14d=12+2=14. It has M=2L=4M=2^L=4 prototype vectors in 0,114\0,1\^14, assigned the index labels 00,01,10,11\00,01,10,11\, plotted as rows in the corresponding black-white matrix. Consider the pair of prototypes indexed by 0000 and 1111 respectively; they diverge at level ℓ=1 =1 of the tree, and their Hamming distance is equal to Δ1=12 _1=12. Similarly, the prototypes indexed by 0000 and 0101 diverge at level ℓ=2 =2 of the tree, and have Hamming distance Δ2=2 _2=2. Panel (c) illustrates a larger construction with L=4L=4, still in a toy dimension d=34d=34 for illustrative purposes. Panels (b) and (d) show the UGC densities for the L=2L=2 and L=4L=4 models, using larger separations and dimensions: the L=2L=2 model has dimension d=32776d=32776 and (Δ1,Δ2)=(32768,8)( _1, _2)=(32768,8), whereas the L=4L=4 model has dimension d=34952d=34952 and (Δ1,Δ2,Δ3,Δ4)=(32768,2048,128,8)( _1, _2, _3, _4)=(32768,2048,128,8). Note how the UGC density for the L=2L=2 model has two distinct peaks in log-reveal odds. The level ℓ=1 =1 ambiguity is resolved at an earlier reveal time, since the corresponding prototypes differ by Hamming distance Δ1=32768 _1=32768; the second peak corresponds to the later reveal time at which the level ℓ=2 =2 ambiguity, corresponding to Hamming separation Δ2=8 _2=8, is resolved. Similar comments apply to the L=4L=4 peaks for the UGC density in panel (d). 2.2.2 From coarse to fine geometry Let us describe how we exploit finer-grained UGC geometry for algorithmic purposes. A single-block scheme uses one geometric multiplier across the full log-reveal-odds interval, and its performance is governed by the coarse complexity UGC C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$. In order to exploit local UGC geometry, we instead partition the interval [−ℓd,ℓd][- _d, _d] into K blocks and allow a different geometric multiplier on each block. For a partition =[λk,λk+1]k=0K−1P=\[ _k, _k+1]\_k=0^K-1, define the block lengths k=λk+1−λk S_k= _k+1- _k and the associated UGC increments k=∫λkλk+1(λ)λ H_k= _ _k _k+1 q(λ)\,dλ. Optimizing the geometric multipliers over these blocks leads to the partition complexity () C(P) ≔(∑k=0K−1kk)2. ( _k=0^K-1 S_k H_k )^2. (7a) Proposition 1 shows that this quantity governs the iteration complexity of the resulting K-block sampler. Although the optimal multipliers depend on the unknown increments k H_k, these increments can be estimated from clean samples. We use these estimates to choose the partition and its multipliers from data, leading to the certified guarantees; see Proposition 2 and Theorem 2. Progressive refinement interpolates between the coarse single-block complexity and the fine-partition limit (5b). In particular, in Theorem 3, we prove that inf()=(∫−ℓdℓd(λ)λ)2where the infimum is over partitions of [−ℓd,ℓd]. _P C(P)\;=\; ( _- _d _d q(λ)dλ )^2 where the infimum is over partitions of $[- _d, _d]$. (7b) Thus, increasing the number of blocks allows the sampler to exploit increasingly fine features of the local UGC geometry, and ultimately achieve the fine-grained complexity based on q. Illustrative example: Figure 4 illustrates this coarse-to-fine interpolation for the discrete-mixture model underlying Figure 2. For d=64d=64, the single-block scheme has complexity UGC≈65.0 C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$≈ 65.0. A three-block partition that allocates finer resolution around the narrow high-density region reduces the partition complexity to approximately 23.523.5, compared with the fine-partition value UGC≈16.9 P_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$≈ 16.9. (a) (b) Figure 4: Block geometry for the d=64d=64 random discrete mixture with M=2d/4M=2^d/4 and η=0.02η=0.02. Both panels show the square-root UGC density q versus the log-reveal-odds λ. Panel (a) uses a single geometric multiplier, yielding UGC≈65.0 C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$≈ 65.0. Panel (b) uses the illustrated K=3K=3 block partition, yielding ()≈23.5 C(P)≈ 23.5. The fine-partition complexity for this example is UGC≈16.9 P_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$≈ 16.9. The three-block scheme devotes more iterations to the narrow high-UGC region and fewer to the flatter tails. Even this coarse adaptation captures most of the available improvement: the complexity drops from approximately 65.065.0 to 23.523.5, substantially closing the gap to the fine-partition value 16.916.9. This example illustrates the basic role of adaptive partitioning: computation is allocated according to where the UGC mass is concentrated, rather than uniformly across the reveal path. 3 Unmasking samplers and KL discretization error We now turn to the description and analysis of some simple unmasking samplers. At a high level, they are based on discretized approximations to the unmasking reveal process Xt,t∈[0,1]\X_t,t∈[0,1]\ from equation (1b). Recalling that ℳ(x)M(x) denotes the set of masked coordinates in the vector x, their updates involve the single-site posterior distributions μi(a,x) _i(a,x) ≔ℙ(Zi=a∣Zj=xjfor all j∉ℳ(x)),defined for each i∈ℳ(x), (Z_i=a Z_j=x_j for all $j (x)$ ), defined for each $i (x)$, (8) where a∈a and x∈(∪⋆)dx∈ (A∪\ \ )^d. We use μ to denote the full collection of these distributions, and often refer to it as the denoiser. It summarizes residual uncertainty in Z given the observation x. In practice, the denoiser μ is estimated based on samples from ℙZP_Z as follows. Given a clean sample Z∼ℙZ _Z, we can generate training examples by independently masking random subsets of coordinates. We then predict the original value of each masked coordinate from the resulting partially observed sample using cross-entropy loss. With this set-up, the population-optimal predictors are given by the posterior distributions μi(⋅,x) _i( ·,x), and the training procedure generates estimates μ^i μ_i for each i=1,…,di=1,…,d. For simplicity, we describe the algorithms using the exact denoiser μ. Using a learned denoiser μ μ contributes an additional term to the KL error bound in a standard way; see equation (18) following the statement of Theorem 1 for details. 3.1 Bernoulli and fixed-cardinality unmasking We now describe the two standard unmasking samplers that we analyze in this paper. At a high level, they involve two basic operations: choosing a subset of indices and then, conditional on this subset, making a random choice of values for the revealed variables using the denoiser μ. The samplers that we analyze differ only in how the random subset is chosen: the Bernoulli sampler uses coin flips, thereby generating a set with a random cardinality, whereas the fixed-cardinality sampler chooses a random subset with fixed cardinality. Both samplers are used in practice, and our theory gives a unified analysis of both in terms of UGC functions. Given a subset A⊆[d]A [d] of coordinates, both samplers make use of the conditional distribution ℙumask(X′∣X,A) _ 0.0pt 1204822262143 0.0pt$ $ 0.0pt 1204822262143 0.0pt$ $ 0.0pt 1061162262144 0.0pt$ $ 0.0pt 1061165262144 0.0pt$ $(X X,A) ≔(⨂i∉ℳ(X)δXi)⊗(⨂i∈Aμi(⋅,X))⊗(⨂i∈ℳ(X)∖Aδ⋆),for A⊆ℳ(X), ( _i (X) _X_i ) ( _i∈ A _i( ·,X) ) ( _i (X) A _ ), for $A (X)$, (9a) which fixes all observed variables (i.e., indices i∉ℳ(X)i (X)); fixes all missing variables not in A; and makes a random update to variables in A. Moreover, for an iteration count N≥1N≥ 1, both samplers are based on a reveal-time grid 0<t0<t1<⋯<tN<1. 0<t_0<t_1<·s<t_N<1. (9b) The samplers are initialized with a random choice X^0∼ℚt0 X^0 _t_0, and then generate a sequence X^jj=0N\ X^j\_j=0^N moving forward in time across the grid (9b). 3.1.1 Bernoulli unmasking sampler We begin by describing the Bernoulli unmasking sampler. It chooses subsets according to the binomial distribution ℙBer(A∣X,β) _ 0.0pt 672488262144 0.0pt$ $ 0.0pt 672488262144 0.0pt$ $ 0.0pt 592490262144 0.0pt$ $ 0.0pt 592489262144 0.0pt$ $(A X,β) ≔βcard(A)(1−β)card(ℳ(X)∖A)with support A⊆ℳ(X), β^card(A)(1-β)^card(M(X) A) with support $A (X)$, (10) and then updates entries according to the conditional distribution (9a). More precisely, given the initialization X^0 X^0 and reveal-time grid (9b), it generates the sequence Draw random binomial subset: Aj∼ℙBer(⋅∣X^j,βj),where βj≔tj+1−tj1−tj, A^j _ 0.0pt 672488262144 0.0pt$ $ 0.0pt 672488262144 0.0pt$ $ 0.0pt 592490262144 0.0pt$ $ 0.0pt 592489262144 0.0pt$ $ ( · X^j, _j ), where _j t_j+1-t_j1-t_j, (11a) Random unmasking: X^j+1∼ℙumask(⋅∣X^j,Aj), X^j+1 _ 0.0pt 1204822262143 0.0pt$ $ 0.0pt 1204822262143 0.0pt$ $ 0.0pt 1061162262144 0.0pt$ $ 0.0pt 1061165262144 0.0pt$ $ ( · X^j,A^j ), (11b) for iterations j=0,1,…,N−1j=0,1,…,N-1. 3.1.2 Fixed-cardinality unmasking sampler The fixed-cardinality sampler is very similar, except that it replaces the binomial subset choice (10) with a black-box that draws a uniformly random subset of a specified size. More precisely, the fixed-cardinality sampler only admits iteration counts N<d−1N<d-1, and it requires that each reveal time be d-aligned, meaning that tj=sj/dt_j=s_j/d for integers 1≤s0<⋯<sN≤d−11≤ s_0<·s<s_N≤ d-1. It initializes X^0 X^0 with exactly d−s0d-s_0 masked coordinates. Then, at iteration j=0,…,N−1j=0,…,N-1, the current state X^j X^j has exactly d−sjd-s_j masked coordinates. Draw fixed-cardinality subset: Aj∼UnifA⊆ℳ(X^j)|card(A)=sj+1−sj. A^j \A ( X^j)\, |\,card(A)=s_j+1-s_j \. (12a) Random unmasking: X^j+1∼ℙumask(⋅∣X^j,Aj), X^j+1 _ 0.0pt 1204822262143 0.0pt$ $ 0.0pt 1204822262143 0.0pt$ $ 0.0pt 1061162262144 0.0pt$ $ 0.0pt 1061165262144 0.0pt$ $ ( · X^j,A^j ), (12b) For future reference, we note that underlying the fixed-cardinality sampler is a de-Poissonized version of the unmasking process Xt,t∈[0,1]\X_t,t∈[0,1]\. It is defined only at d-aligned times t=s/dt=s/d, and the associated variable Xt∼ℙthas exactly s revealed coordinates, X_t _t has exactly $s$ revealed coordinates, (13) for a subset of cardinality s chosen uniformly at random. Note that we are overloading our notation here, but the specific version of ℙtP_t being used will be clear from context. 3.1.3 Initialization and completion steps Both samplers involve initialization and completion steps. In our analysis, the initialization cost is measured by the KL divergence DKL(ℙt0∥ℚt0)where Xt0∼ℙt0 and X^0∼ℚt0. D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $(P_t_0\|Q_t_0) where $X_t_0 _t_0$ and $ X^0 _t_0$. (14a) Here Xt0X_t_0 is generated by the standard reveal process for the Bernoulli sampler (1b), and from its de-Poissonized analogue (13) for the fixed-cardinality sampler. Moreover, both samplers involve a final completion step, based on a completion kernel T(⋅∣x) C_T( · x) that maps each partially revealed terminal state x∈(∪⋆)dx∈ (A∪\ \ )^d to a probability law on fully specified vectors in dA^d. We denote the resulting completed output by Z Z and its law by ℙZ^P_ Z. The defect of any completion kernel is measured by Γ(T) _ C(T) ≔XT[DKL(ℒ(Z∣XT)∥T(⋅∣XT))]. _X_T [D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ (L(Z X_T)\, \|\, C_T( · X_T) ) ]. (14b) While these terms appear in our bounds, they are not dominant terms. For example, the following completion kernel C has defect equal to zero, and uses only card(ℳ(XT))card(M(X_T)) serial updates. Fix an ordering of the indices in ℳ(XT)M(X_T), and then sample from the conditional distributions μi _i in sequence to fill in the missing entries. With the endpoint T=d−1dT= d-1d, we have card(ℳ(XT))=1card(M(X_T))=1 for the exact cardinality sampler and [card(ℳ(XT))]=1E[card(M(X_T))]=1 for the Bernoulli sampler, so that the computational cost of implementing this completion kernel is minimal. Similarly, for initialization, it is easy to initialize the fixed-cardinality sampler with exactly one unmasked entry, so that the initialization cost vanishes for t0=1/dt_0=1/d. The bounds below are stated for a general interval [t0,T][t_0,T] and arbitrary initialization-completion choices, but we later specialize to the interval [1d, 1−1d] [ 1d,\>1- 1d ], which we refer to as the canonical reveal time interval. 3.2 Unified analysis We are now set up to state a single theorem that provides a unified analysis of both the Bernoulli and fixed-cardinality unmasking samplers. Our original definition (2a) of the Bernoulli denoising gain h emphasizes the connection to the reveal process. Here, in order to make transparent the connections with fixed-cardinality sampling, we make use of the following equivalent representation: (t) h(t) =∑i=1dAi,t[Info(Zi;ZAi,t)], = _i=1^dE_A_i,t [Info(Z_i;Z_A_i,t) ], (15a) where Ai,t⊆[d]∖iA_i,t [d] \i\ is a random subset obtained by including each coordinate of [d]∖i[d] \i\ independently with probability t. See Appendix B for the proof of this alternative representation. The analogue for the fixed-cardinality sampler is given by the fixed-cardinality unmasking gain coefficients jcard h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j ≔∑i=1dBi,j[Info(Zi;ZBi,j)]where Bi,j is uniform over j-cardinality subsets of [d]∖i. _i=1^dE_B_i,j [Info(Z_i;Z_B_i,j) ] where $B_i,j$ is uniform over $j$-cardinality subsets of $[d] \i\$. (15b) These coefficients are defined for j=1,…,d−1j=1,…,d-1, with 0card≔0 h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_0 0. These two notions lead to the two versions of UGC growth complexity, given by Bernoulli:(p,q) @text@underlineBernoulli: H(p,q) ≔∫pqt(1−t)′(t)dtfor pairs 0≤p<q≤1, and _p^qt(1-t) h (t)\,dt for pairs $0≤ p<q≤ 1$, and (16a) Exact cardinality:card(a,b) @text@underlineExact cardinality: H^card(a,b) ≔∑j=a+1b−1(jd)(1−jd)jcard−j−1card,0≤a<b≤d. _j=a+1^b-1 ( jd ) (1- jd ) \ h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j- h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j-1 \, 0≤ a<b≤ d. (16b) Our main theorem bounds the KL error of both the Bernoulli and fixed-cardinality unmasking samplers in terms of increments of these respective UGC functions. It applies to any reveal-time grid (9b), and the analysis shows why the reveal odds function ψ(t)≔t1−tψ(t) t1-t is natural. Theorem 1. For any grid (9b), the Ber-unmasking sampler produces output Z Z such that DKL(ℙZ∥ℙZ^) D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ (P_Z\, \|\,P_ Z ) ≤∑j=0N−1ψ(tj+1)ψ(tj)−1(tj,tj+1)+DKL(ℙt0∥ℚt0)+Γ(T). ≤ _j=0^N-1 \ ψ(t_j+1)ψ(t_j)-1 \ H(t_j,t_j+1)+D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $(P_t_0\|Q_t_0)+ _ C(T). (17a) Moreover, for any d-aligned grid tj=ajdt_j= a_jd, the Card-unmasking sampler produces output Z^card Z^card such that DKL(ℙZ∥ℙZ^card) D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ (P_Z\, \|\,P_ Z^card ) ≤∑j=0N−1ψ(tj+1)ψ(tj+1d)−1card(aj,aj+1)+DKL(ℙt0∥ℚt0)+Γ(T). ≤ _j=0^N-1 \ ψ(t_j+1)ψ (t_j+ 1d )-1 \ H^card(a_j,a_j+1)+D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $(P_t_0\|Q_t_0)+ _ C(T). (17b) We prove these two claims in Sections 6.1 and 6.2, respectively. The proofs are relatively short, and follow the same template of starting from an exact representation of the KL discretization error over the interval, and then bounding it in terms of H or card H^card respectively. For the Bernoulli sampler, we first derive the exact KL representation, from which the upper bound (17a) follows from an elementary argument. On the other hand, the fixed-cardinality guarantee (17b) makes use of the exact representation of the KL discretization error, derived by Chen et al. [15]; in particular, the coefficients jcard h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j are rescaled versions of their information coefficients. In contrast to our upper bounds, neither form of the exact KL error has simple additive structure in terms of the log-reveal odds. This structure in our upper bounds turns out to be very useful: as we discuss in the sequel (see Corollary 1 and Appendix A), a simple stepsize choice in the bound (17b) gives an immediate sharpening of the fixed-cardinality sampling guarantees given in the paper [15]. More generally, these upper bounds lend themselves naturally to developing and analyzing K-block sampling schemes (see Section 4). Estimated denoisers: If the sampler replaces each exact single-site posterior μi(⋅,x) _i( ·,x) by an estimate μ^i(⋅,x) μ_i( ·,x), while leaving the random-subset law and reveal probabilities unchanged, then the right-hand side of equation (17a) acquires the additional additive term den(μ^) E_ 0.0pt 501073196608 0.0pt$ $ 0.0pt 501073196608 0.0pt$ $ 0.0pt 440403196608 0.0pt$ $ 0.0pt 440404196608 0.0pt$ $( μ) ≔∑j=0N−1βj[∑i∈ℳ(Xtj)DKL(μi(⋅,Xtj)∥μ^i(⋅,Xtj))]where βj≔tj+1−tj1−tj. _j=0^N-1 _jE [ _i (X_t_j)D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ ( _i( ·,X_t_j)\, \|\, μ_i( ·,X_t_j) ) ] where $ _j t_j+1-t_j1-t_j$. (18) Here the expectation is under the true reveal-process law of XtjX_t_j. A similar comment applies to the Card-unmasking sampler. We establish this fact as part of the proof in Section 6.1. Relation between UGC functions: By inspection, it is clear that the Ber-UGC and Card-UGC functions, as defined in equation (2c) and equation (16b) respectively, are closely related. This intuition can be formalized as follows. For any 0≤p<q≤10≤ p<q≤ 1, define the multinomial triple (U0,U1,U2)∼Multinomial(d+1,p,q−p, 1−q)(U_0,U_1,U_2) (d+1;\,p,\,q-p,\,1-q ). We then have the equivalence (p,q) H(p,q) =d+1[card(AU,BU)], = dd+1E [ H^card(A_U,B_U) ], (19) where AU≔maxU0−1,0A_U \U_0-1,0\, and BU≔minU0+U1,dB_U \U_0+U_1,d\, and we set card(a,b)=0 H^card(a,b)=0 whenever a≥ba≥ b. Thus, the Ber-UGC over [p,q][p,q] is the average of Card-UGC quantities over randomized cardinality endpoints. See Section C.1.2 for the proof of the identity (19). 3.3 A single-block guarantee and its consequences By inspection, the bounds (17a) and (17b) are very well-suited to unmasking-time grid points tjj=0N−1\t_j\_j=0^N-1 for which the reveal odds ψ(tj)=tj/(1−tj)ψ(t_j)=t_j/(1-t_j) evolve in a geometric way. In this section, we use Theorem 1 to derive guarantees for this particularly simple choice of stepsizes. 3.3.1 Guarantees for a single geometric block For a parameter ρ>0ρ>0, consider the sequence ():ψ(tj+1) [70.0001pt][l]$ Geo(ρ):$ψ(t_j+1) =min(1+ρ)ψ(tj),ψ(T). = \(1+ρ)ψ(t_j),ψ(T) \. (20) When the unmasking algorithm is run with this geometric sequence, we refer to it as the Geo(ρ)Geo(ρ)-unmasking algorithm. Corollary 1 (Single-block guarantee for a reveal-odds geometric scheme). Given an iteration budget N≥log(ψ(T)ψ(t0))N≥ ( ψ(T)ψ(t_0) ), the Geo(ρ)Geo(ρ)-unmasking sampler with multiplier ρ≔exp1Nlog(ψ(T)/ψ(t0))−1ρ \ 1N (ψ(T)/ψ(t_0)) \-1 produces completed output Z Z such that DKL(ℙZ∥ℙZ^) D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $(P_Z\|P_ Z) ≤2(t0,T)Nlog(ψ(T)ψ(t0))+DKL(ℙt0∥ℚt0)+Γ(T). ≤ 2 H(t_0,T)N ( ψ(T)ψ(t_0) )+D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $(P_t_0\|Q_t_0)+ _ C(T). (21) This result is an immediate consequence of Theorem 1, and we include the proof here. It makes essential use of the additivity property (3) of H. Proof. By construction, the schedule traverses the interval [t0,T][t_0,T] in exactly N steps, and moreover, we have ψ(tj+1)ψ(tj)−1≤ρ ψ(t_j+1)ψ(t_j)-1≤ρ at each round. Applying the bound (17a) from Theorem 1 yields DKL(ℙZ∥ℙZ^) D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $(P_Z\|P_ Z) ≤ρ∑j=0N−1(tj,tj+1)⏟=(i)ρ(t0,T)+DKL(ℙt0∥ℚt0)+Γ(T) ≤ ρ _j=0^N-1 H(t_j,t_j+1)_ (i)=ρ H(t_0,T)+D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $(P_t_0\|Q_t_0)+ _ C(T) ≤(ii)2(t0,T)Nlog(ψ(T)ψ(t0))+DKL(ℙt0∥ℚt0)+Γ(T), (i)≤ 2 H(t_0,T)N\; ( ψ(T)ψ(t_0) )+D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $(P_t_0\|Q_t_0)+ _ C(T), where step (i) uses the additivity property (3), and step (i) follows since exp(u)−1≤2u (u)-1≤ 2u for u∈[0,1]u∈[0,1], applied with u=1Nlog(ψ(T)ψ(t0))u= 1N ( ψ(T)ψ(t_0) ). ∎ Exact cardinality sampler: An analogous result holds for the fixed-cardinality uniform sampler, using a slightly different geometric schedule. Given a pair of integers a0<Aa_0<A between 11 and d−1d-1, we define t0=a0dt_0= a_0d and T=AdT= Ad. Given an iteration budget N≥log(ψ(T)ψ(t0+1d))N≥ ( ψ(T)ψ(t_0+ 1d) ), starting from a0a_0, we recursively choose aj+1a_j+1 as the largest integer in aj+1,…,A\a_j+1,…,A\ such that ψ(aj+1d)≤(1+ρ)ψ(aj+1d)where ρ≔exp1Nlog(ψ(T)ψ(t0+1d))−1. ψ ( a_j+1d )≤(1+ρ)ψ ( a_j+1d ) where $ρ \ 1N ( ψ(T)ψ(t_0+ 1d) ) \-1$. With these choices, running the fixed-cardinality sampler yields completed output Z^card Z^card such that DKL(ℙZ∥ℙZ^card) D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ (P_Z\, \|\,P_ Z^card ) ≤2card(a0,A)Nlog(ψ(T)ψ(t0+1d))+DKL(ℙt0∥ℚt0)+Γ(T). ≤ 2 H^card(a_0,A)N ( ψ(T)ψ(t_0+ 1d) )+D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $(P_t_0\|Q_t_0)+ _ C(T). The proof uses the bound (17b) from Theorem 1, and then applies the same reasoning as the proof of Corollary 1. 3.3.2 Some consequences At a high level, Corollary 1 and its analogue for fixed-cardinality sampling show that the iteration complexity when using a single geometric multiplier protocol is governed by the aggregate UGC mass functionals (0,1) H(0,1) and card(0,d) H^card(0,d), respectively, for the Bernoulli and fixed-cardinality versions. These relations allow us to recover and sharpen several existing results on unmasking samplers. As we show in Appendix A, the aggregate UGC complexities associated with Bernoulli and fixed-cardinality unmasking are equivalent up to universal constants, and they are closely related to the complexity governing the CTMC guarantees of Dmitriev et al. [17]. Consequently, the single-block guarantee in Corollary 1 yields comparable guarantees for these different unmasking mechanisms, while sharpening bounds based only on total correlation and dual total correlation. We defer these comparisons, together with further information-theoretic aspects of aggregate UGC, to Appendix A. 3.4 Why the UGC path matters The aggregate UGC complexity is a coarse measure, relative to the full log-reveal-odds density that captures the full UGC path. It is useful to consider a stylized pair of distributions, based on some primitives analyzed in the paper [17], that makes this discrepancy very explicit: while their aggregate complexities are identical, the UGC path structure is extremely different, and as we will see in the next section, the resulting optimal algorithms are very different. Recall that the log-reveal-odds UGC density is given by (λ) q(λ) =r2(1−r)2′(r)where r=φ−1(λ)=eλ1+eλ. =r^2(1-r)^2 h (r) where $r= ^-1(λ)= e^λ1+e^λ$. (23) (a) (b) Figure 5: Log-reveal-odds UGC densities for the repeated-common-bit model in panel (a) and the global-parity model in panel (b), both with d=64d=64. The two densities are reflections of one another about λ=0λ=0 in log-reveal-odds coordinates: their information is concentrated near opposite ends of the reveal path even though their full-path UGC values agree. Repeated bit: First, suppose that we draw a hidden V∼Ber(1/2)V Ber(1/2), and then generate the random vector Z∈0,1dZ∈\0,1\^d by setting Z1=⋯=Zd=VZ_1=·s=Z_d=V. This construction is simply the noiseless (η=0η=0) instance of the noisy-repeated-bit example discussed previously in Section 2.2.1, and moreover, we can compute its UGC density function explicitly. From equation (23), it suffices to compute h and then its derivative. Conditional on coordinate i remaining masked, its mutual-information contribution equals Ent(V)=log2Ent(V)= 2 once at least one of the other d−1d-1 coordinates is revealed; it is equal to zero otherwise. It follows that rep(r)=dlog21−(1−r)d−1 h_rep(r)=d 2 \1-(1-r)^d-1 \. Taking derivatives and combining with the formula (23) yields rep(λ) q_rep(λ) =d(d−1)log2r2(1−r)d. = \d(d-1) 2 \\;r^2(1-r)^d. (24a) Global-parity model: In the global-parity model, draw Z1,…,Zd−1Z_1,…,Z_d-1 independently from Ber(1/2) Ber(1/2) and set Zd=Z1⊕⋯⊕Zd−1Z_d=Z_1 ·s Z_d-1. Calculations similar to those in the previous example show that par(λ) q_par(λ) =d(d−1)log2(1−r)2rd. = \d(d-1) 2 \\;(1-r)^2\;r^d. (24b) We plot these two UGC densities in Figure 5. Comparing equation (24a) and equation (24b) reveals the relation22 2 This follows from the identity φ−1(−λ)=1−φ−1(λ) ^-1(-λ)=1- ^-1(λ), which interchanges r and 1−r1-r under reflection. par(λ)=rep(−λ) q_par(λ)= q_rep(-λ), which corresponds to reflection across λ=0λ=0 in log-reveal-odds. This reflection can be seen by comparing the two panels. As can be verified via a straightforward calculation, both models have (0,1)=(d−1)(d+1)log2 H(0,1)= (d-1)(d+1) 2, so that they have matched aggregate UGC mass. However, the full UGC path reveals the differences in their distributional structure: the repeated-bit dependence is resolved near the beginning of the path, whereas parity dependence persists until the end. Moreover, as we develop in the next section, this path difference has important consequences for designing optimal algorithms. 4 Certified-optimal bounds for the UGC path Thus far, we have considered the single-block consequence of Theorem 1, based on one geometric multiplier over the full reveal interval. The additivity (3) of the UGC function allows a more refined approach. We first partition the reveal interval into K blocks, and then optimize the stepsizes within each block. Doing so leads to a UGC partition complexity that refines the coarse UGC bound. We then show how the required UGC increments can be estimated from samples, yielding certified data-dependent samplers and allowing the block boundaries themselves to be optimized. Finally, by refining the partition, we recover the fine-partition complexity UGC P_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$ in equation (5b), which characterizes the optimal discretization error up to a factor of two. 4.1 An optimal K-block guarantee For some 0<t0<T<10<t_0<T<1, we begin with a prescribed K-block partition of the interval [t0,T][t_0,T], say of the form ≔[bk,bk+1]∣k=0,…,K−1P \[b_k,b_k+1] k=0,…,K-1 \, where b0=t0b_0=t_0 and bK=Tb_K=T. For each block, define its log-reveal-odds length and UGC mass by k S_k ≔φ(bk+1)−φ(bk),andk≔(bk,bk+1), (b_k+1)- (b_k), and H_k H(b_k,b_k+1), (25) where we recall that φ(r)≔log(r/(1−r)) (r) (r/(1-r)). Given a total iteration budget N, suppose that we allocate positive integers NkN_k with ∑k=0K−1Nk=N _k=0^K-1N_k=N. We then run the Geo(ρ)Geo(ρ)-sampler to traverse the kthk^th-block in NkN_k iterations. Applying Theorem 1 blockwise yields DKL(ℙZ∥ℙZ^) D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $(P_Z\|P_ Z) ≤∑k=0K−1[expk/Nk−1]k+DKL(ℙt0∥ℚt0)+Γ(T). ≤ _k=0^K-1 [ \ S_k/N_k \-1 ] H_k+D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $(P_t_0\|Q_t_0)+ _ C(T). (26a) Here we have again used the additivity property (3) to bound the error of each block by the scalar multiple of its UGC mass. Hence, for the prescribed partition, the best guarantee furnished by Theorem 1 is obtained from the integer program minN0,…,NK−1>0 _N_0,…,N_K-1>0 ∑k=0K−1[expk/Nk−1]ksubject to∑k=0K−1Nk=N. _k=0^K-1 [ \ S_k/N_k \-1 ] H_k subject to _k=0^K-1N_k=N. (26b) It is easy to see that this integer program can be solved efficiently by dynamic programming. 4.2 Guarantees for an explicit procedure Rather than solving the dynamic program directly, we seek an explicit allocation that exposes the structure of its solution. Doing so leads to the UGC-based partition complexity UGC() C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(P) ≔(∑k=0K−1kk)2, ( _k=0^K-1 S_k H_k )^2, (27) which interpolates between the single-block complexity (5a) and the fine-partition limit (5b). Proposition 1 (Near-optimal geometric schedules for a K-block partition). Given any K-block partition P of [t0,T][t_0,T] and an iteration budget N≥2K+2log(ψ(T)ψ(t0))N≥ 2 \K+2 ( ψ(T)ψ(t_0) ) \, define the geometric multipliers ρk _k ≔min1, 4UGC()Nkk,k=0,1,…,K−1. \1,\,4 C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(P)N S_k H_k \, k=0,1,…,K-1. (28a) Then the K-block Ber-unmasking procedure based on P uses at most N score evaluations and yields an output Z Z satisfying DKL(ℙZ∥ℙZ^) D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $(P_Z\|P_ Z) ≤4UGC()N+DKL(ℙt0∥ℚt0)+Γ(T). ≤ 4 C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(P)N+D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $(P_t_0\|Q_t_0)+ _ C(T). (28b) Moreover, if (N0⋆,…,NK−1⋆)(N _0,…,N _K-1) denotes the optimal solution of the dynamic program (26b) with iteration budget N, then ∑k=0K−1ρ(Nk⋆)k _k=0^K-1ρ(N _k) H_k ≥UGC()Nwhere ρ(Nk⋆)≔exp(k/Nk⋆)−1. ≥ C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(P)N where $ρ(N _k) ( S_k/N _k)-1$. (28c) The proof is an unmasking analogue of the argument used for Gaussian diffusion in our companion paper [50]. The principal changes are the log-reveal-odds clock, the corresponding UGC block masses, and the boundary terms; the remainder follows mutatis mutandis. This parallelism reflects a common geometric structure underlying Gaussian diffusion and discrete unmasking, despite their different noise mechanisms and natural path coordinates. The upper and lower bounds in Proposition 1 show that, apart from the initial and terminal cost, the explicit allocation is within a factor of 44 of the optimal value of the dynamic program (26b). It also always improves upon the single-block complexity. Indeed, by Cauchy–Schwarz and the additivity (3) of the UGC complexity, we have UGC() C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(P) =(∑k=0K−1kk)2≤(∑k=0K−1k)(∑k=0K−1k)=φ(T)−φ(t0)(t0,T)=UGC([t0,T]). = ( _k=0^K-1 S_k H_k )^2≤ ( _k=0^K-1 S_k ) ( _k=0^K-1 H_k )= \ (T)- (t_0) \ H(t_0,T)= C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$([t_0,T]). (29) Equality holds if and only if there is a scalar c>0c>0 such that k=ck S_k=c H_k for every block. Thus, partitioning provides a strict improvement whenever the UGC mass is distributed non-uniformly relative to log-reveal-odds length. 4.3 Sandwich-UGC estimators from KL increments While the bounds in Proposition 1 are attractive, the geometric multipliers ρk _k depend on knowledge of the UGC increments k H_k for each block k. In this section, we describe how it is possible to estimate these increments, assuming that we have available a collection of i.i.d. samples Z(ℓ)ℓ=1m\Z^( )\_ =1^m from the original distribution ℙZP_Z. This estimator forms the basis for the certified-optimal sampling schemes described in Section 4.4. 4.3.1 Kullback–Leibler unmasking increments From the definition (2a), the Bernoulli unmasking gain h is defined in terms of the original reveal process XpX_p with additional conditioning on the event i∈ℳ(Xp)\i (X_p)\. Consequently, it is useful to introduce the forced-mask reveal-time process that explicitly encodes this conditioning. Recalling the uniform random variables that underlie the masking process (1a), we define Mt|i≔i∪ℓ∈[d]∖i∣Uℓ>t,andXt|i≔(Mt|i,Z(Mt|i)c). M_t i \i\∪ \ ∈[d] \i\ U_ >t \, and X_t i (M_t i,Z_(M_t i)^c ). (30a) Due to the shared set of uniform random variables, the process satisfies a natural coupling: for q>pq>p, the variable Xq|iX_q i can be obtained from Xp|iX_p i by revealing each variable in ℳ(Xp|i)∖iM(X_p i) \i\ independently with probability q−p1−p q-p1-p. Moreover, by construction, the random variable Xt|iX_t i has the law of the original reveal process XtX_t conditional on i∈ℳ(Xt)i (X_t). For 0≤p<q≤10≤ p<q≤ 1, we define the KL unmasking increment (p,q) D(p,q) ≔(q−p)∑i=1d[DKL(πi,q∥πi,p)]where πi,t(⋅)≡μi(⋅,Xt|i) for each t∈[0,1], (q-p) _i=1^dE [D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ ( _i,q\, \|\, _i,p ) ] where $ _i,t(·)≡ _i ( ·,X_t i )$ for each $t∈[0,1]$, (30b) and the expectation is taken with respect to the joint forced-mask coupling (Xp|i,Xq|i)(X_p i,X_q i) for each i=1,…,di=1,…,d. With this set-up, we have the following guarantee: Lemma 1. For every 0≤p<q<10≤ p<q<1, we have the exact relation (p,q)q−p D(p,q)q-p =(q)−(p). = h(q)- h(p). (31a) For every 0<p<q<10<p<q<1, we also have the sandwich relation 1cp,q(p,q)≤(p,q)≤1+cp,qcp,q(p,q)where cp,q≔ψ(q)ψ(p)−1>0. 1c_p,q D(p,q)\;≤\; H(p,q)\;≤\; 1+c_p,qc_p,q D(p,q)\, where $c_p,q ψ(q)ψ(p)-1>0$. (31b) See Section 6.3.1 for the proof. Observe that the sandwich relation (31b) is particularly well-suited to intervals [p,q][p,q] for which the ratio of the reveal odds ψ(r)=r/(1−r)ψ(r)=r/(1-r) is well-controlled. Concretely, for a dyadic interval with ψ(q)/ψ(p)=2ψ(q)/ψ(p)=2, the relation provides a factor two sandwich. We now exploit this fact to design an estimator for a partition of arbitrary length. 4.3.2 A tail-robust estimate of the UGC increment We now specify and analyze a tail-robust estimate of the UGC increment. For an arbitrary pair 0<p<q<10<p<q<1, consider the reveal-odds-dyadic partition vjj=0J\v_j\_j=0^J given by ψ(vj) ψ(v_j) ≔min2jψ(p),ψ(q)where ψ(r)≔r/(1−r) and J≔⌈log2(ψ(q)ψ(p))⌉. \2^jψ(p),ψ(q)\ where $ψ(r) r/(1-r)$ and $J _2 ( ψ(q)ψ(p) ) $. (32a) For each interval [vj,vj+1][v_j,v_j+1], Lemma 1 guarantees that (vj,vj+1)≤(vj,vj+1)≤ 2(vj,vj+1) D(v_j,v_j+1)\;≤\; H(v_j,v_j+1)\;≤\;2 D(v_j,v_j+1), and hence that ∑j=0J−1(vj,vj+1)≤(p,q)≤ 2∑j=0J−1(vj,vj+1) _j=0^J-1 D(v_j,v_j+1)\;≤\; H(p,q)\;≤\;2 _j=0^J-1 D(v_j,v_j+1), where we have used the additivity property (3) of H. Given a clean sample Z(ℓ)Z^( ), we can simulate the forced-mask reveal process Xt|i(ℓ)X_t i^( ) over the interval t∈[0,1]t∈[0,1], for each coordinate i=1,…,di=1,…,d, and using these trajectories, we can construct the trajectory statistic Q(ℓ) Q^( ) ≔∑i=1d∑j=0J−1(vj+1−vj)DKL(μi(⋅,Xvj+1|i(ℓ))∥μi(⋅,Xvj|i(ℓ))). _i=1^d \ _j=0^J-1(v_j+1-v_j)D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ ( _i(·,X_v_j+1 i^( ))\| _i(·,X_v_j i^( )) ) \. (32b) By construction, we have [Q(ℓ)]=∑j=0J−1(vj,vj+1)E[Q^( )]= _j=0^J-1 D(v_j,v_j+1), where the expectation is taken over the sample Z(ℓ)Z^( ), along with the forced-mask trajectory randomness. Combined with the factor two sandwich property, we have constructed a statistic such that [Q(ℓ)]≤(p,q)≤ 2[Q(ℓ)]. [Q^( )]\;≤\; H(p,q)\;≤\;2E[Q^( )]. (32c) A tail-robust estimator: Given the statistic Q(ℓ)Q^( ) from equation (32b), the standard Monte Carlo estimate is given by 1m∑ℓ=1mQ(ℓ) 1m _ =1^mQ^( ). It is unbiased and can be analyzed, but can be overly sensitive to the tail behavior of the underlying KL divergences in the estimate. To introduce tail robustness, we instead analyze a truncated version of this estimator. It requires a moment bound, but provides exponential Bernstein-type tail control. More precisely, suppose that, for some moment order α≥4α≥ 4, the changes in the one-coordinate denoisers satisfy the aggregate moment bound maxj=0,…,J−1[∑i=1dDKL(μi(⋅,Xvj+1|i(ℓ))∥μi(⋅,Xvj|i(ℓ)))α/2]2/α _j=0,…,J-1 \E [ \ _i=1^dD_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ ( _i ( ·,X_v_j+1 i^( ) )\, \|\, _i ( ·,X_v_j i^( ) ) ) \^α/2 ] \^2/α ≤Bαfor some known Bα>0. ≤ B_α for some known $B_α>0$. (33a) Under this condition, we define the τ-truncated estimator ^m(p,q) H_m(p,q) ≔2m∑ℓ=1mminQ(ℓ),τwhere τ≔(q−p)Bα3(m−1)7log(4/η)2/α. 2m _ =1^m \Q^( ),τ\ where $τ (q-p)B_α \ 3(m-1)7 (4/η) \^2/α$. (33b) Here η∈(0,1)η∈(0,1) is a user-chosen failure probability and Q(ℓ)ℓ=1m\Q^( )\_ =1^m are i.i.d. copies of the trajectory statistic Q(ℓ)Q^( ) from equation (32b). We also define the (unbiased) empirical variance of our truncated estimator as V V ≔1m−1∑ℓ=1m(2minQ(ℓ),τ−^m(p,q))2. 1m-1 _ =1^m (2 \Q^( ),τ\- H_m(p,q) )^2. (33c) Proposition 2 (Factor-two data-dependent sandwich on UGC). Given the estimate ^m(p,q) H_m(p,q), the UGC increment (p,q) H(p,q) can be sandwiched as (p,q) H(p,q) ≤(A)^m(p,q)+r^m(η)≤(B)2(p,q)+r^m(η)with probability at least 1−η, (A)≤ H_m(p,q)+ r_m(η) (B)≤2 \ H(p,q)+ r_m(η) \ with probability at least $1-η$, (34a) where the upper confidence correction takes the form r^m(η) r_m(η) ≔2V^log(4/η)m+4(q−p)Bα7log(4/η)3(m−1)1−2/α. 2 V (4/η)m+4(q-p)B_α \ 7 (4/η)3(m-1) \^1-2/α. (34b) See Section 6.3.2 for the proof. Interpretation of the tail condition: Condition (33a) controls the tails of the aggregate change in the one-coordinate denoisers over each reveal-odds-dyadic interval. This choice is important: it measures the same posterior changes that enter the trajectory statistic (32b), rather than the absolute uncertainty of the individual denoisers. A condition on the true-symbol log loss, for instance, could be large even when revealing additional coordinates produces no change in any posterior. As a basic example, suppose that the coordinates of Z are independent. For the exact Bayes denoisers considered here, the forced-mask observation Xt|iX_t i reveals only masking variables and a subset of the coordinates Z−iZ_-i. Consequently, ZiZ_i is independent of Xt|iX_t i, and hence μi(⋅,Xt|i) _i ( ·,X_t i ) =ℒ(Zi)for every t∈[0,1]. =L(Z_i) for every $t∈[0,1]$. All of the KL increments in equation (33a) therefore vanish, so that the condition holds with any positive BαB_α, in agreement with the fact that the corresponding UGC increment is zero. 4.4 Sampling schemes that are certified-optimal In this section, we turn to the key problem of designing samplers that are certified-optimal, meaning that their iteration complexity meets the optimum specified by the partition complexity functional, up to data-dependent residual terms, and that for any target accuracy ε>0 >0 and failure probability η∈(0,1)η∈(0,1), there are data-dependent parameter choices for the sampler guaranteeing that its output Z Z satisfies the accuracy bound DKL(ℙZ∥ℙZ^) D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ (P_Z\|P_ Z ) ≤εwith probability at least 1−η. ≤ with probability at least $1-η$. (35) In Section 4.4.1, we specify and analyze a certified procedure for a given K-block partition, whereas in Section 4.4.2, we describe certified procedures based on dynamic programming for choosing the block boundaries. 4.4.1 Certified-optimal sampling using K-blocks Suppose that we are given a K-block partition of the interval [t0,T][t_0,T], based on blocks of the form [bk,bk+1][b_k,b_k+1]. Our goal is to design a sampler that achieves the optimal K-bound from Proposition 1, but using a choice of geometric multipliers that can be estimated based on samples Z(ℓ)ℓ=1m\Z^( )\_ =1^m. Here we describe a simple way of doing so, one which exploits the guarantees from Proposition 1 as well as the UGC increment estimator analyzed in Proposition 2. Suppose that, for each block [bk,bk+1][b_k,b_k+1], we apply the tail-robust estimator from Proposition 2 with failure probability η/Kη/K. We then obtain a tail bound with the upper confidence limit r^k,m(η/K)⏟≡r^k r_k,m(η/K)_≡ r_k ≔2V^klog(4K/η)m+4(bk+1−bk)Bα(7log(4K/η)3(m−1))1−2/α, 2 V_k (4K/η)m+4(b_k+1-b_k)B_α ( 7 (4K/η)3(m-1) )^1-2/α, (36a) where V^k V_k is the empirical variance estimate for the block. Finally, we define the surrogate partition complexity ^UGC() C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(P) ≔(∑k=0K−1k^k,m+r^k)2. ( _k=0^K-1 S_k H_k,m+ r_k )^2. (36b) With this set-up, we have the following certified analogue for the Ber-unmasking sampler with geometric multipliers, or the Geo(ρ)Geo(ρ)-scheme for short. Theorem 2 (Data-certified guarantees for multi-block scheme). Given a failure probability η∈(0,1)η∈(0,1), and a K-block partition of the interval [t0,T][t_0,T], consider any iteration budget N≥2K+2φ(T)−φ(t0)N≥ 2 \K+2 \ (T)- (t_0) \ \. Then running the K-block Geo(ρ)Geo(ρ)-unmasking scheme with the geometric multipliers ρ^k ρ_k ≔min1,4^UGC()Nk^k,m+r^kfor k=0,1,…,K−1. \1, 4 C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(P)N S_k H_k,m+ r_k \ for $k=0,1,…,K-1$. (37a) yields a completed output Z Z such that DKL(ℙZ∥ℙZ^) D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $(P_Z\|P_ Z) ≤4^UGC()N+DKL(ℙt0∥ℚt0)+Γ(T)with probability at least 1−η, ≤ 4 C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(P)N+D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $(P_t_0\|Q_t_0)+ _ C(T) with probability at least $1-η$, (37b) and does so with at most N unmasking rounds. See Section 6.4 for the proof. Certified-optimal: Let us now clarify why the guarantee of Theorem 2 is both certified and optimal (up to constant factors). Suppose that our goal is to design a sampler that achieves a prescribed KL error ε>0 >0. As discussed in Section 3.1.3, it is straightforward to ensure that the initialization and terminal contribution satisfies DKL(ℙt0∥ℚt0)+Γ(T)≤ε/2D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $(P_t_0\|Q_t_0)+ _ C(T)≤ /2. From Theorem 2, it can be seen that choosing an iteration number N≥8^UGC()/εN≥ 8 C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(P)/ guarantees that the resulting sampler has output Z Z such that DKL(ℙZ∥ℙZ^) D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $(P_Z\|P_ Z) ≤εwith probability at least 1−η. ≤ with probability at least $1-η$. (38) Thus, the estimated partition complexity provides both a data-dependent schedule and an end-to-end certificate of its sampling accuracy. For this reason, we refer to it as a certified guarantee. It is also near-optimal in a precise sense. In particular, recall that the procedure in Proposition 1 achieves the DP optimum up to a constant factor of 44. Under the same initialization conditions, doing so requires an iteration number N≥8UGC()/εN≥ 8 C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(P)/ . As shown in the proof of Theorem 2, on the simultaneous high-probability event from Proposition 2, we have ^UGC() C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(P) ≤2UGC()+∑k=0K−1kr^k. ≤ 2 \ C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(P)+ _k=0^K-1 S_k r_k \. Thus, the increase in computational complexity incurred by replacing the oracle UGC increments by their data-dependent estimates is captured explicitly by the confidence radii r^k r_k, together with the factor of 2 2 in the sandwich bound. 4.4.2 Certified-optimal boundary selection Our analysis thus far has focused on optimal schemes for a fixed set of K blocks. In this section, we formulate the problem of optimizing the split points that define a (near)-optimal set of K blocks via a simple dynamic program. More precisely, for an integer J>KJ>K that defines the resolution, suppose that we fix a fine deterministic grid of candidate reveal times τ0=t0<τ1<⋯<τJ=T _0=t_0< _1<·s< _J=T. Our goal is to select indices ikk=1K−1\i_k\_k=1^K-1 from the set 1,…,J−1\1,…,J-1\, and use the corresponding reveal times tk=τikt_k= _i_k, together with the endpoints t0=t0t_0=t_0 and tK=Tt_K=T, to define a K-block partition. We seek to minimize the square root of the partition complexity UGC() C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(P) =∑k=0K−1kk,where k≔φ(tk+1)−φ(tk), and k≔(tk,tk+1). = _k=0^K-1 S_k H_k, where $ S_k (t_k+1)- (t_k)$, and $ H_k H(t_k,t_k+1)$. Given the naturally sequential structure, this optimization problem can be solved by dynamic programming, as we now formalize. For candidate intervals 0≤i<j≤J0≤ i<j≤ J, define the edge cost e(i,j) e(i,j) ≔(τi,τj)(τi,τj),where (a,b)≔φ(b)−φ(a). S( _i, _j) H( _i, _j), where $ S(a,b) (b)- (a)$. (39a) With this notation, our ultimate goal is to compute K(J) V_K(J) ≔min∑k=0K−10=j0<j1<⋯<jK=Je(jk,jk+1). _0=j_0<j_1<·s<j_K=J _k=0^K-1e(j_k,j_k+1). (39b) This quantity is the minimum cost of a K-block partition of the interval [τ0,τJ]=[t0,T][ _0, _J]=[t_0,T]. It is easy to see that it can be computed via dynamic programming, where we introduce intermediate quantities k(j) V_k(j), defined for each k∈0,…,Kk∈\0,…,K\ and j∈0,…,Jj∈\0,…,J\ as the minimum cost of a k-block partition of the subinterval [τ0,τj][ _0, _j], with value +∞+∞ when no such partition exists. Finally, we observe that the edge costs in equation (39a) depend on the UGC increments (τi,τj) H( _i, _j). As in the previous section, we can obtain confidence bounds for increments of this type using the estimator from Proposition 2, thereby obtaining a data-dependent version of the dynamic program. 5 Fine partition limit and optimal Euler discretization In the preceding section, we developed and analyzed sampling methods based on finite K-block partitions, and showed how their performance depends on the local UGC mass of the chosen partition. We now characterize the limit under arbitrarily fine refinement and connect it to the optimal KL error of Euler discretization. This analysis highlights the central role of the log-reveal-odds UGC density q defined in equation (4). 5.1 Fine partition limit and its Euler optimality We specialize to the canonical reveal interval ℐfull≔[1/d,1−1/d]I_ 0.0pt 616043262143 0.0pt$ $ 0.0pt 616043262143 0.0pt$ $ 0.0pt 534775262144 0.0pt$ $ 0.0pt 534774262144 0.0pt$ $ [1/d,1-1/d]. Its image under the log-reveal-odds map is [−ℓd,ℓd][- _d, _d], where ℓd≔log(d−1) _d (d-1). For a partition =[bk,bk+1]k=0K−1P=\[b_k,b_k+1]\_k=0^K-1 of ℐfullI_ 0.0pt 616043262143 0.0pt$ $ 0.0pt 616043262143 0.0pt$ $ 0.0pt 534775262144 0.0pt$ $ 0.0pt 534774262144 0.0pt$ $, define the corresponding log-reveal-odds blocks ℐk≔[φ(bk),φ(bk+1)]I_k [ (b_k), (b_k+1)] and their lengths k≔Len(ℐk) S_k (I_k). Our previously defined partition complexity can then be written directly in terms of q as UGC() C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(P) ≔(∑k=0K−1k∫ℐk(λ)λ)2. ( _k=0^K-1 S_k _I_k q(λ)\,dλ )^2. (40a) Observe that refinement can only decrease this complexity: whenever ′P is a refinement of P, we have UGC(′)≤UGC() C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(P )≤ C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(P). This fact motivates the fine-partition limit UGC(ℐfull) P_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(I_ 0.0pt 616043262143 0.0pt$ $ 0.0pt 616043262143 0.0pt$ $ 0.0pt 534775262144 0.0pt$ $ 0.0pt 534774262144 0.0pt$ $) ≔infUGC(), _P C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(P), (40b) where the infimum is over all finite partitions of ℐfullI_ 0.0pt 616043262143 0.0pt$ $ 0.0pt 616043262143 0.0pt$ $ 0.0pt 534775262144 0.0pt$ $ 0.0pt 534774262144 0.0pt$ $. We now characterize this infimum explicitly in terms of q, and show that the same quantity governs the sharp leading-order KL error of optimal Euler discretization. Theorem 3 (Fine-partition limit and Euler optimality). Suppose that q is continuous and strictly positive on [−ℓd,ℓd][- _d, _d]. Then the fine-partition limit (40b) is given by UGC(ℐfull) P_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(I_ 0.0pt 616043262143 0.0pt$ $ 0.0pt 616043262143 0.0pt$ $ 0.0pt 534775262144 0.0pt$ $ 0.0pt 534774262144 0.0pt$ $) =(∫−ℓdℓd(λ)λ)2. = ( _- _d _d q(λ)\,dλ )^2. (41a) Moreover, the optimal N-step KL discretization error satisfies inf1d=t0<⋯<tN=d−1d∑j=0N−1Γumask(tj,tj+1)⏟KL discretization error _ 1d=t_0<·s<t_N= d-1d _j=0^N-1 _ 0.0pt 1204822262143 0.0pt$ $ 0.0pt 1204822262143 0.0pt$ $ 0.0pt 1061162262144 0.0pt$ $ 0.0pt 1061165262144 0.0pt$ $(t_j,t_j+1)_ KL discretization error =UGC(ℐfull)2N+o(N−1), = P_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(I_ 0.0pt 616043262143 0.0pt$ $ 0.0pt 616043262143 0.0pt$ $ 0.0pt 534775262144 0.0pt$ $ 0.0pt 534774262144 0.0pt$ $)2N+o(N^-1), (41b) where the infimum is over all N-step discretizations of the canonical interval [1d,d−1d][ 1d, d-1d]. See Section 6.5 for the proof. Taken together, the two claims in Theorem 3 show that the fine-partition complexity is precisely twice the leading-order constant governing the optimal Euler KL error, and that it can be approached arbitrarily closely by the K-block schemes analyzed in Proposition 1 and Theorem 2. Related work: A related square-root principle appears in the analysis of Lavenant and Zanella [25], who study random-order fixed-cardinality unmasking and express its factorization error in terms of a cardinality-indexed information profile. They then consider a high-dimensional continuum limit in which, using our notation, both the ambient dimension d and the number of sampling rounds N diverge. In the regime d/N→+∞d/N→+∞, optimization of the resulting limiting functional yields a square-root information-profile rule. Our results differ in both formulation and scope. The UGC density q is defined directly from the finite-dimensional reveal path, with log-reveal odds providing the natural path coordinate, and our finite-step bounds apply at fixed dimension and for arbitrary finite partitions. Moreover, rather than optimizing only a limiting variational problem, we optimize blockwise schedules at finite dimension, and use estimated UGC increments to construct data-dependent partitions with certified guarantees. Finally, equation (41b) gives the sharp leading-order optimal Euler error at fixed dimension d as the number of discretization steps N grows. 5.2 Gains and convergence to the fine-partition limit We first ask how much can be gained by exploiting the local UGC geometry, and then how many blocks are needed to realize this gain. The maximal improvement over a single-block scheme is measured by Ratio(ℙZ) (P_Z) ≔UGC([ℐfull])UGC(ℐfull)≥1. C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$([I_ 0.0pt 616043262143 0.0pt$ $ 0.0pt 616043262143 0.0pt$ $ 0.0pt 534775262144 0.0pt$ $ 0.0pt 534774262144 0.0pt$ $]) P_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(I_ 0.0pt 616043262143 0.0pt$ $ 0.0pt 616043262143 0.0pt$ $ 0.0pt 534775262144 0.0pt$ $ 0.0pt 534774262144 0.0pt$ $)≥ 1. (42) For the repeated-bit and parity models (see Figure 5), we have Ratio(ℙZ)≍log(d)Ratio(P_Z) (d), yielding a growing but relatively modest separation. Much larger gains are possible when the UGC density becomes increasingly concentrated with dimension. For example, the discrete mixture model in Figure 2 satisfies Ratio(ℙZ)=Ω~(d)Ratio(P_Z)= ( d) with high probability over the cluster centers. We next exhibit the same phenomenon in a simpler random XORSAT model, for which the scaling can be analyzed via an easier argument. 5.2.1 An example with Ω~(d) ( d) gains To obtain a tractable example with the same Ω~(d) ( d) separation, consider a dense random XORSAT ensemble. For ambient dimension d and latent dimension k, draw ∈0,1d×kA∈\0,1\^d× k with i.i.d. Ber(1/2) Ber(1/2) entries, draw U∈0,1kU∈\0,1\^k with i.i.d. Ber(1/2) Ber(1/2) entries, and set Z=UZ=AU modulo two. Thus, Z is supported on a random Boolean subspace. We parameterize the ensemble by the ratio α≔k/dα k/d. Figure 6 plots the UGC density for d=64d=64 and α∈0.2,0.5,0.8α∈\0.2,0.5,0.8\. The density is unimodal, with its peak moving from right to left as α increases. To quantify the resulting gain, we focus on the symmetric case α=0.5α=0.5. (a) (b) (c) Figure 6: Plots of the log-odds UGC density q for the random XORSAT ensemble with d=64d=64 and parameter α∈0.2,0.5,0.8α∈\0.2,0.5,0.8\ in panels (a)–(c), respectively. Panel (b) marks the pre-transition, transition, and post-transition regions used in the three-block construction. Lemma 2. For the random XORSAT model with α=0.5α=0.5, for each even dimension d above a universal constant, there is a distribution ℙZP_Z such that Ratio(ℙZ) (P_Z) ≥cdlogdfor a universal constant c>0, ≥ c\, d d for a universal constant $c>0$, (43) and this gain is achieved, up to constants, by a K=3K=3 block scheme. See Appendix D for the proof. Our analysis uses the probabilistic method [1] to show that, for each sufficiently large dimension, there exists a realization of A, inducing a “good” distribution ℙZP_Z, that satisfies the following properties. First, its coarse complexity satisfies UGC([ℐfull])=Θ(dlogd) C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$([I_ 0.0pt 616043262143 0.0pt$ $ 0.0pt 616043262143 0.0pt$ $ 0.0pt 534775262144 0.0pt$ $ 0.0pt 534774262144 0.0pt$ $])= (d d). As a consequence, it suffices to construct a three-block partition with complexity (dlogd)O( d d). Set δd=c1logd/d _d=c_1 d/d for a sufficiently large constant c1>0c_1>0, and define the reveal time intervals ℐpre _ -1.35483pt 723920196608 1.3611pt$ $ -1.35483pt 723920196608 1.3611pt$ $ -1.35483pt 635492196608 0.95277pt$ $ -1.35481pt 635488196608 0.68054pt$ $ ≔[1/d,1/2−δd], [1/d,1/2- _d ], ℐtrans _ 0.0pt 813770196608 0.0pt$ $ 0.0pt 813770196608 0.0pt$ $ 0.0pt 712989196608 0.0pt$ $ 0.0pt 712991196608 0.0pt$ $ ≔[1/2−δd,1/2+δd], [1/2- _d,1/2+ _d ], ℐpost _ -0.94836pt 680901196608 1.3611pt$ $ -0.94836pt 680901196608 1.3611pt$ $ -0.94838pt 595042196608 0.95277pt$ $ -0.94836pt 595406196608 0.68054pt$ $ ≔[1/2+δd,1−1/d]. [1/2+ _d,1-1/d ]. Our proof shows that the “good” ℙZP_Z has UGC masses (ℐpre)=(d−10),(ℐtrans)=Θ(d),and(ℐpost) H(I_ -1.35483pt 723920196608 1.3611pt$ $ -1.35483pt 723920196608 1.3611pt$ $ -1.35483pt 635492196608 0.95277pt$ $ -1.35481pt 635488196608 0.68054pt$ $)=O(d^-10), H(I_ 0.0pt 813770196608 0.0pt$ $ 0.0pt 813770196608 0.0pt$ $ 0.0pt 712989196608 0.0pt$ $ 0.0pt 712991196608 0.0pt$ $)= (d), and H(I_ -0.94836pt 680901196608 1.3611pt$ $ -0.94836pt 680901196608 1.3611pt$ $ -0.94838pt 595042196608 0.95277pt$ $ -0.94836pt 595406196608 0.68054pt$ $) =(d−10). =O(d^-10). (44) Thus, consistent with the behavior shown in Figure 6, essentially all of the UGC mass lies in the transition interval ℐtransI_ 0.0pt 813770196608 0.0pt$ $ 0.0pt 813770196608 0.0pt$ $ 0.0pt 712989196608 0.0pt$ $ 0.0pt 712991196608 0.0pt$ $, which has log-reveal-odds width (logd/d)O( d/d). This combination leads to the claimed scaling (dlogd)O( d d) for the 33-block partition. 5.2.2 Uniform partitions: a generic convergence bound The XORSAT example shows that a small number of well-placed blocks can already be near-optimal. For comparison, let KU_K denote the uniform K-block partition of [−ℓd,ℓd][- _d, _d], which ignores local geometry when choosing the block boundaries. Here we quantify its convergence to the fine-partition limit under a simple global regularity condition. In particular, suppose that ≔ f q is continuous on [−ℓd,ℓd][- _d, _d], and define its modulus of continuity by ω(h) _ f(h) ≔supλ,λ′|(λ)−(λ′)|where the sup ranges over pairs λ,λ′∈[−ℓd,ℓd] with |λ−λ′|≤h. _λ,λ | f(λ)- f(λ )| where the sup ranges over pairs $λ,λ ∈[- _d, _d]$ with $|λ-λ |≤ h$. (45) Lemma 3 (Accuracy of uniform K-block approximations). For the uniform partition KU_K, we have UGC(K) C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(U_K) ≤UGC(ℐfull)+ℓdω(2ℓdK). ≤ P_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(I_ 0.0pt 616043262143 0.0pt$ $ 0.0pt 616043262143 0.0pt$ $ 0.0pt 534775262144 0.0pt$ $ 0.0pt 534774262144 0.0pt$ $)+ _d\, _ f ( 2 _dK ). (46) The proof is the same modulus-of-continuity argument used for Gaussian diffusion in our companion paper (Lemma 4, [50]). As a particular consequence, if f is Lipschitz with constant Lip()Lip( f), then UGC(K) C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(U_K) ≤UGC(ℐfull)+2Lip()ℓd2K. ≤ P_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(I_ 0.0pt 616043262143 0.0pt$ $ 0.0pt 616043262143 0.0pt$ $ 0.0pt 534775262144 0.0pt$ $ 0.0pt 534774262144 0.0pt$ $)+ 2Lip( f) _d^2K. (47) This generic bound can be conservative because it depends on a global regularity constant and fixes the block boundaries in advance. For the XORSAT example, the Lipschitz constant Lip()Lip( f) grows with dimension even though K=3K=3 adaptively placed blocks are near-optimal. When samples are available, the data-dependent DP procedure in Section 4.4.2 instead optimizes the block boundaries directly. 6 Proofs In this section, we collect the proofs of a subset of our results, including the proof of Theorem 1, with the Bernoulli and fixed-cardinality versions given in Section 6.1 and Section 6.2, respectively; the proof of our data-certification procedures, including Lemma 1 and Proposition 2 in Section 6.3; the proof of Theorem 2 in Section 6.4; and finally, the proof of Theorem 3 in Section 6.5. We defer the proofs of other results in the paper to the appendices. 6.1 Proof of Theorem 1: Bernoulli version We begin by proving the bound (17a) for the Bernoulli unmasking sampler. 6.1.1 Main argument Recall from equation (1b) the reveal process Xt,t∈[0,1]\X_t,t∈[0,1]\. For any pair 0<p<q<10<p<q<1, we let p,qK_p,q denote the transition kernel of the reveal process in moving from XpX_p to XqX_q. On the other hand, the unmasking sampler is based on the updates in equation (11a) and equation (11b), and we let ^p,q K_p,q denote the associated transition kernel that moves from X^p X_p to X^q X_q. We introduce the shorthand notation Γumask(p,q) _ 0.0pt 1204822262143 0.0pt$ $ 0.0pt 1204822262143 0.0pt$ $ 0.0pt 1061162262144 0.0pt$ $ 0.0pt 1061165262144 0.0pt$ $(p,q) ≔Xp[DKL(p,q(⋅∣Xp)∥^p,q(⋅∣Xp))], _X_p [D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ (K_p,q( · X_p)\, \|\, K_p,q( · X_p) ) ], (48) corresponding to the averaged Kullback–Leibler (KL) discrepancy between the two transition kernels over the interval [p,q][p,q]. Here the expectation is taken over the marginal distribution of the reveal process variable XpX_p. The core technical result at the heart of Theorem 1 is the following bound: Lemma 4 (Multiplicative control of the one-step unmasking defect). For every 0<p<q<10<p<q<1, we have Γumask(p,q) _ 0.0pt 1204822262143 0.0pt$ $ 0.0pt 1204822262143 0.0pt$ $ 0.0pt 1061162262144 0.0pt$ $ 0.0pt 1061165262144 0.0pt$ $(p,q) ≤ψ(q)ψ(p)−1(p,q)where ψ(r)≔r1−r. ≤ \ ψ(q)ψ(p)-1 \ H(p,q) where $ψ(r) r1-r$. (49) See Section 6.1.2 for the proof. Given this lemma, the proof of Theorem 1 is very simple. Recalling the definition (14b) of the completion defect Γ(T) _ C(T), we have DKL(ℙZ∥ℙZ^) D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ (P_Z\, \|\,P_ Z ) ≤(i)DKL(ℙt0∥ℚt0)+∑j=0N−1Γumask(tj,tj+1)+Γ(T) (i)≤D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $(P_t_0\|Q_t_0)+ _j=0^N-1 _ 0.0pt 1204822262143 0.0pt$ $ 0.0pt 1204822262143 0.0pt$ $ 0.0pt 1061162262144 0.0pt$ $ 0.0pt 1061165262144 0.0pt$ $(t_j,t_j+1)+ _ C(T) ≤(ii)DKL(ℙt0∥ℚt0)+∑j=0N−1ψ(tj+1)ψ(tj)−1(tj,tj+1)+Γ(T), (i)≤D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $(P_t_0\|Q_t_0)+ _j=0^N-1 \ ψ(t_j+1)ψ(t_j)-1 \ H(t_j,t_j+1)+ _ C(T), where step (i) follows from the KL chain rule, combined with the data processing inequality, whereas step (i) follows by applying the bound (49) repeatedly to each of the KL increments. Extension to estimated denoisers: Fix a state x at step j=0,…,N−1j=0,…,N-1. In the existing kernel notation, tj,tj+1(⋅∣x)K_t_j,t_j+1( · x) is the exact block transition, ^tj,tj+1(⋅∣x) K_t_j,t_j+1( · x) is the frozen product transition formed from the exact one-site posteriors, and ^tj,tj+1[μ^](⋅∣x) K_t_j,t_j+1[ μ]( · x) is the frozen product transition formed from the estimated posteriors. The two frozen kernels have the same reveal probability βj≔tj+1−tj1−tj _j t_j+1-t_j1-t_j. Since the exact block transition and ^tj,tj+1(⋅∣x) K_t_j,t_j+1( · x) have the same one-coordinate marginals, splitting the log-likelihood ratio through the product of these marginals gives DKL(tj,tj+1(⋅∣x)∥^tj,tj+1[μ^](⋅∣x)) D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ (K_t_j,t_j+1( · x)\, \|\, K_t_j,t_j+1[ μ]( · x) ) =DKL(tj,tj+1(⋅∣x)∥^tj,tj+1(⋅∣x))+βj∑i∈ℳ(x)DKL(μi(⋅,x)∥μ^i(⋅,x)). =D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ (K_t_j,t_j+1( · x)\, \|\, K_t_j,t_j+1( · x) )+ _j _i (x)D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ ( _i( ·,x)\, \|\, μ_i( ·,x) ). Indeed, for each i∈ℳ(x)i (x), both one-coordinate kernels leave the coordinate masked with probability 1−βj1- _j. Conditional on revealing it, they use μi(⋅,x) _i( ·,x) and μ^i(⋅,x) μ_i( ·,x), respectively. Their one-coordinate KL divergence is given by βjDKL(μi(⋅,x)∥μ^i(⋅,x)) _jD_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ ( _i( ·,x)\, \|\, μ_i( ·,x) ). Averaging the first KL term over x=Xtjx=X_t_j under the exact reveal-process law gives exactly Γumask(tj,tj+1) _ 0.0pt 1204822262143 0.0pt$ $ 0.0pt 1204822262143 0.0pt$ $ 0.0pt 1061162262144 0.0pt$ $ 0.0pt 1061165262144 0.0pt$ $(t_j,t_j+1). Averaging the decomposition and summing over j=0,…,N−1j=0,…,N-1 in the same KL chain-rule argument adds the term displayed after equation (17a), which completes the proof. 6.1.2 Proof of Lemma 4 Our proof is based on the exact one-step representation Γumask(p,q) _ 0.0pt 1204822262143 0.0pt$ $ 0.0pt 1204822262143 0.0pt$ $ 0.0pt 1061162262144 0.0pt$ $ 0.0pt 1061165262144 0.0pt$ $(p,q) =∫pq(q−u)′(u)u, = _p^q(q-u) h (u)\,du, (50a) which we return to prove below. Taking this claim as given, let us prove the bound (49). Introduce the shorthand f(u)=u(1−u)f(u)=u\,(1-u), and observe that f(u)≥0f(u)≥ 0 for u∈[0,1]u∈[0,1]. Note that for every u∈[p,q]u∈[p,q], we have (q−u)≤(q−p)(q-u)≤(q-p), and f(u)≥p(1−q)f(u)≥ p(1-q), so that q−u≤q−p(1−q)f(u) q-u\;≤\; q-pp(1-q)f(u) =(i)q(1−p)p(1−q)−1f(u)=(ii)ψ(q)ψ(p)−1f(u) (i)= \ q(1-p)p(1-q)-1 \f(u)\; (i)=\; \ ψ(q)ψ(p)-1 \f(u) (50b) where step (i) follows from simple algebra; and step (i) uses the definition ψ(r)=r/(1−r)ψ(r)=r/(1-r). Thus, we can write Γumask(p,q) _ 0.0pt 1204822262143 0.0pt$ $ 0.0pt 1204822262143 0.0pt$ $ 0.0pt 1061162262144 0.0pt$ $ 0.0pt 1061165262144 0.0pt$ $(p,q) =(iii)∫pq(q−u)′(u)u≤(iv)ψ(q)ψ(p)−1∫pqf(u)′(u)u=(v)ψ(q)ψ(p)−1(p,q), (i)= _p^q(q-u) h (u)\,du (iv)≤ \ ψ(q)ψ(p)-1 \ _p^qf(u)\; h (u)du\; (v)=\; \ ψ(q)ψ(p)-1 \ H(p,q), where step (i) follows from the exact representation (50a); step (iv) follows from the inequality (50b) along with the fact that ′(t)≥0 h (t)≥ 0 for all t∈[0,1]t∈[0,1]; and step (v) follows from the definition (2c) of the UGC function. Thus, we have established the claim (49). Proof of the exact representation (50a): We first claim that h satisfies the relation (u) h(u) =S(Z)−duInfo(Z;Xu), =S(Z)- dduInfo (Z;X_u ), (51a) where we have introduced the shorthand S(Z)≔∑i=1dEnt(Zi)S(Z) _i=1^dEnt(Z_i) for the entropy sum. To verify the claim (51a), fix some δ>0δ>0 sufficiently small. Conditional on XuX_u, each coordinate i∈ℳ(Xu)i (X_u) is revealed by time u+δu+δ with probability δ/(1−u)δ/(1-u). Revealing two or more coordinates has probability O(δ2)O(δ^2), while revealing only coordinate i contributes its current posterior entropy. Thus, dividing the first-order expansion of the information increment by δ and letting δ↓0δ 0 gives duInfo(Z,Xu) dduInfo (Z;X_u ) =11−u∑i=1d[i∈ℳ(Xu)Ent(Zi∣Xu)]=∑i=1dEnt(Zi∣Xu,i∈ℳ(Xu)). = 11-u _i=1^dE [1 \i (X_u) \Ent (Z_i X_u ) ]\;=\; _i=1^dEnt (Z_i X_u,\,i (X_u) ). Since the event i∈ℳ(Xu)i (X_u) is independent of ZiZ_i, we have the equivalence Ent(Zi∣Xu,i∈ℳ(Xu))=Ent(Zi)−Info(Zi;Xu∣i∈ℳ(Xu)). (Z_i X_u,\,i (X_u) )=Ent(Z_i)-Info (Z_i;X_u i (X_u) ). Summing over i and using the definitions of S(Z)S(Z) and (u) h(u) proves the claim (51a). We now prove the exact representation. Conditional on Xp=xX_p=x, let A⊆ℳ(x)A (x) be the set of coordinates revealed between p and q. The exact and frozen-product kernels induce the same law for the random subset A. Conditional on A, they unmask coordinates using, respectively, the joint posterior of ZAZ_A and the product of its one-site posterior marginals. Consequently, we can decompose the KL divergence as DKL(p,q(⋅∣x)∥^p,q(⋅∣x)) D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ (K_p,q( · x)\, \|\, K_p,q( · x) ) =[∑i∈AEnt(Zi∣Xp=x)|Xp=x]⏟T1−[Ent(ZA∣Xp=x,A)|Xp=x]⏟T2. = E [ _i∈ AEnt (Z_i X_p=x )\, |\,X_p=x ]_T_1- E [Ent (Z_A X_p=x,A )\, |\,X_p=x ]_T_2. Note that each coordinate still masked at time p is included in A with probability βp,q≔q−p1−p _p,q q-p1-p. Averaging over XpX_p and using the definition (2a) of h, we find that [T1] [T_1] =βp,q(1−p)S(Z)−(p)=(q−p)S(Z)−(p). = _p,q(1-p) \S(Z)- h(p) \\;=\;(q-p) \S(Z)- h(p) \. Moreover, conditional on XpX_p, the new part of XqX_q is (A,ZA)(A,Z_A). Since A is conditionally independent of Z and the random sub-vector ZAZ_A is a function of (Z,A)(Z,A), we have [T2] [T_2] =Info(Z;A,ZA∣Xp)=Info(Z;Xq∣Xp). =Info (Z;A,Z_A X_p )\;=\;Info (Z;X_q X_p ). Combining these two identities yields Γumask(p,q) _ 0.0pt 1204822262143 0.0pt$ $ 0.0pt 1204822262143 0.0pt$ $ 0.0pt 1061162262144 0.0pt$ $ 0.0pt 1061165262144 0.0pt$ $(p,q) =(q−p)S(Z)−(p)−Info(Z;Xq∣Xp). =(q-p) \S(Z)- h(p) \-Info (Z;X_q X_p ). (51b) It remains to analyze the trailing mutual information term. We have Info(Z;Xq∣Xp) (Z;X_q X_p ) =(i)Info(Z;Xq)−Info(Z;Xp)=(ii)∫pqdduInfo(Z;Xu)u=(iii)∫pqS(Z)−(u)u, (i)=Info (Z;X_q )-Info (Z;X_p )\; (i)=\; _p^q dduInfo (Z;X_u )du\; (i)=\; _p^q \S(Z)- h(u) \\,du, (51c) where step (i) follows because Z⟶Xq⟶XpZ X_q X_p is a Markov chain; step (i) follows from the fundamental theorem of calculus; and step (i) follows from the identity (51a). Finally, we have Γumask(p,q) _ 0.0pt 1204822262143 0.0pt$ $ 0.0pt 1204822262143 0.0pt$ $ 0.0pt 1061162262144 0.0pt$ $ 0.0pt 1061165262144 0.0pt$ $(p,q) =(iv)∫pq(u)−(p)u=(v)∫pq∫pu′(v)vu=(vi)∫pq(q−v)′(v)v, (iv)= _p^q \ h(u)- h(p) \\,du\; (v)=\; _p^q _p^u h (v)\,dv\,du\; (vi)=\; _p^q(q-v) h (v)\,dv, where equality (iv) follows by substituting the representation (51c) into equation (51b) and simplifying terms; step (v) follows from the fundamental theorem of calculus; and step (vi) follows from Fubini’s theorem. This proves the exact representation (50a). 6.2 Proof of Theorem 1: Exact cardinality sampling For integers 0≤a<b≤d−10≤ a<b≤ d-1, let A be a uniformly random a-subset of [d][d], independent of Z, and define X[a] X^[a] ≔(ZA,ZAc⋆)where A∼UnifS⊆[d]|card(S)=a, (Z_A,Z _A^c ) where $A \S [d]\, |\,card(S)=a \$, where A is a subset of cardinality a, chosen uniformly at random, and independently of Z. Conditional on A, we choose (B∣A)∼UnifS⊆Ac|card(S)=b−a(B A) \S A^c\, |\,card(S)=b-a \, corresponding to the uniform-subset rule (12a) that defines the exact cardinality sampler. Write a,bcardK_a,b^card for the exact transition from X[a]X^[a] to cardinality b, and ^a,bcard K_a,b^card for the transition generated by the Card-unmasking sampler. In analogy with the Bernoulli defect (48), define the one-step KL defect Γcard(a,b) _ 0.0pt 610050196608 0.0pt$ $ 0.0pt 610050196608 0.0pt$ $ 0.0pt 535562196608 0.0pt$ $ 0.0pt 535563196608 0.0pt$ $(a,b) ≔X[a][DKL(a,bcard(⋅∣X[a])∥^a,bcard(⋅∣X[a]))]. _X^[a] [D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ (K_a,b^card( · X^[a])\, \|\, K_a,b^card( · X^[a]) ) ]. (52a) The kernels use the same conditional law for B. Conditional on (X[a],B)(X^[a],B), the exact kernel samples from ℒ(ZB∣ZA)L(Z_B Z_A), whereas the sampler uses ⨂i∈Bℒ(Zi∣ZA) _i∈ BL(Z_i Z_A), corresponding to the product update (9a). We now apply the one-block specialization of the exact error representation of Chen et al. [15, Theorem 3.3]. After translation33 3 To be clear, their information curve at index j+1j+1 is jcard/d h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j/d, and their previous cardinality and block size are a and b−ab-a. Since B is recoverable from the input and output mask patterns, retaining the subset partition does not change this transition KL divergence. to our normalization and notation, it guarantees that Γcard(a,b) _ 0.0pt 610050196608 0.0pt$ $ 0.0pt 610050196608 0.0pt$ $ 0.0pt 535562196608 0.0pt$ $ 0.0pt 535563196608 0.0pt$ $(a,b) =1d∑j=a+1b−1(b−j)jcard−j−1card. = 1d _j=a+1^b-1(b-j) \ h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j- h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j-1 \. (52b) We claim that this exact representation admits the following upper bound: Lemma 5 (Fixed-cardinality one-step unmasking defect). For all integers 0≤a<b≤d−10≤ a<b≤ d-1, we have Γcard(a,b) _ 0.0pt 610050196608 0.0pt$ $ 0.0pt 610050196608 0.0pt$ $ 0.0pt 535562196608 0.0pt$ $ 0.0pt 535563196608 0.0pt$ $(a,b) ≤ψ(b/d)ψ((a+1)/d)−1card(a,b). ≤ \ ψ(b/d)ψ ((a+1)/d )-1 \ H^card(a,b). (53) Proof. If b=a+1b=a+1, both sums are empty. Otherwise, we introduce the shorthand ρa,b≔ψ(b/d)ψ((a+1)/d)−1=d(b−a−1)(a+1)(d−b), _a,b ψ(b/d)ψ ((a+1)/d )-1\;=\; d(b-a-1)(a+1)(d-b), and make note of the upper bound d(b−j)j(d−j)≤ρa,b d(b-j)j(d-j)≤ _a,b, valid for every a+1≤j≤b−1a+1≤ j≤ b-1. Since jcard h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j is non-decreasing, the increments jcard−j−1card h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j- h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j-1 are nonnegative. Putting together the pieces, we arrive at the upper bound Γcard(a,b) _ 0.0pt 610050196608 0.0pt$ $ 0.0pt 610050196608 0.0pt$ $ 0.0pt 535562196608 0.0pt$ $ 0.0pt 535563196608 0.0pt$ $(a,b) =1d∑j=a+1b−1(b−j)jcard−j−1card≤ρa,b1d2∑j=a+1b−1j(d−j)jcard−j−1card=ρa,bcard(a,b), = 1d _j=a+1^b-1(b-j) \ h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j- h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j-1 \\;≤\; _a,b 1d^2 _j=a+1^b-1j(d-j) \ h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j- h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j-1 \\;=\; _a,b H^card(a,b), where the last equality follows from the definition (16b) of card H^card. This completes the proof of the upper bound (53). ∎ Note that Lemma 5 is the fixed-cardinality analogue of the Bernoulli sampler bound given in Lemma 4. Consequently, the KL bound (17b) for the fixed-cardinality sampler follows from the same argument, instead using Lemma 5 to bound the one-step errors. 6.3 Proof of data-certification results In this section, we provide proofs of our data-based certification results, including that of Lemma 1 in Section 6.3.1; as well as that of Proposition 2 in Section 6.3.2. 6.3.1 Proof of Lemma 1 We break our proof into parts, one for each claim in the statement. Proof of the claim (31a): We first prove the exact expression (31a). For each coordinate i, let Xp|iX_p i and Xq|iX_q i denote the coupled observations at times p and q, with coordinate i kept masked. Note that the observation Xp|iX_p i is obtained from Xq|iX_q i by a random remasking operation independent of ZiZ_i conditional on Xq|iX_q i. Consequently, the triple Zi⟶Xq|i⟶Xp|iZ_i X_q i X_p i forms a Markov chain, so that we can write Info(Zi;Xq|i∣Xp|i) (Z_i;X_q i X_p i) =Info(Zi;Xq|i)−Info(Zi;Xp|i). =Info (Z_i;X_q i )-Info (Z_i;X_p i ). (54a) At the same time, by the conditional KL representation of conditional mutual information, we have Info(Zi;Xq|i∣Xp|i) (Z_i;X_q i X_p i) =(Xp|i,Xq|i)[DKL(ℒ(Zi∣Xq|i,Xp|i)∥ℒ(Zi∣Xp|i))] =E_(X_p i,X_q i) [D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ (L(Z_i X_q i,X_p i)\, \|\,L(Z_i X_p i) ) ] =(Xp|i,Xq|i)[DKL(ℒ(Zi∣Xq|i)∥ℒ(Zi∣Xp|i))], =E_(X_p i,X_q i) [D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ (L(Z_i X_q i)\, \|\,L(Z_i X_p i) ) ], (54b) where the second equality follows from the Markov relation Zi⟶Xq|i⟶Xp|iZ_i X_q i X_p i, which implies ℒ(Zi∣Xq|i,Xp|i) (Z_i X_q i,X_p i) =ℒ(Zi∣Xq|i). =L(Z_i X_q i). Combining equations (54a) and (54b) yields the identity [DKL(ℒ(Zi∣Xq|i)∥ℒ(Zi∣Xp|i))]=Info(Zi;Xq|i)−Info(Zi;Xp|i). [D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ (L(Z_i X_q i)\, \|\,L(Z_i X_p i) ) ]\;=\;Info (Z_i;X_q i )-Info (Z_i;X_p i ). Summing both sides of this identity over the indices i=1,…,di=1,…,d, and using the definitions of D and h in equation (30b) and equation (2a), respectively, we find that (p,q)q−p D(p,q)q-p =(q)−(p), = h(q)- h(p), (54c) as claimed in equation (31a). Proof of the sandwich relation (31b): Turning to the claim (31b), for any pair 0<p<q<10<p<q<1, we have p(1−q)≤t(1−t)≤q(1−p)for all t∈[p,q]. p(1-q)\;≤\;t(1-t)\;≤\;q(1-p) for all $t∈[p,q]$. Multiplying both sides by ′(t)≥0 h (t)≥ 0 and integrating yields p(1−q)(q)−(p)≤∫pqt(1−t)′(t)t≤q(1−p)(q)−(p). p(1-q) \ h(q)- h(p) \\;≤\; _p^qt(1-t) h (t)\,dt\;≤\;q(1-p) \ h(q)- h(p) \. Using the definition (2c) of (p,q) H(p,q) and the exact identity (54c), we have proved that p(1−q)q−p(p,q)≤(p,q)≤q(1−p)q−p(p,q). p(1-q)q-p D(p,q)\;≤\; H(p,q)\;≤\; q(1-p)q-p D(p,q). (54d) Finally, an elementary calculation gives cp,q≔ψ(q)ψ(p)−1=q−p(1−q)c_p,q ψ(q)ψ(p)-1= q-pp(1-q), so that we have p(1−q)q−p p(1-q)q-p =1cp,q,andq(1−p)q−p=1+cp,qcp,q. = 1c_p,q, and q(1-p)q-p= 1+c_p,qc_p,q. Combining with equation (54d) proves the claim (31b). 6.3.2 Proof of Proposition 2 Introduce the shorthand μ(p,q)≔[Q(ℓ)]=∑j=0J−1(vj,vj+1)μ(p,q) [Q^( )]= _j=0^J-1 D(v_j,v_j+1) for the expected value of Q(ℓ)Q^( ). Note that we have μ(p,q) μ(p,q) ≤(p,q)≤2μ(p,q), ≤ H(p,q)≤ 2μ(p,q), (55a) as previously stated in equation (32c). We first derive the required moment bound for the trajectory statistic from the denoiser condition (33a). Set r≔α/2r α/2, so that r≥2r≥ 2. Introducing the shorthand notation Kj K_j ≔∑i=1dDKL(μi(⋅,Xvj+1|i(ℓ))∥μi(⋅,Xvj|i(ℓ))),for j=0,…,J−1, _i=1^dD_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ ( _i ( ·,X_v_j+1 i^( ) )\, \|\, _i ( ·,X_v_j i^( ) ) ), for $j=0,…,J-1$, our statistic Q(ℓ)Q^( ) can be written as Q(ℓ)=∑j=0J−1(vj+1−vj)KjQ^( )= _j=0^J-1(v_j+1-v_j)K_j. We then apply Minkowski’s inequality and make use of the moment condition (33a), thereby obtaining the moment bound [(Q(ℓ))r]1/r \E [(Q^( ))^r ] \^1/r ≤∑j=0J−1(vj+1−vj)[Kjr]1/r≤∑j=0J−1(vj+1−vj)Bα=(q−p)Bα⏟≡Mα. ≤ _j=0^J-1(v_j+1-v_j) \E [K_j^r ] \^1/r\;≤\; _j=0^J-1(v_j+1-v_j)B_α= (q-p)B_α_≡ M_α. In terms of the shorthand Y(ℓ)≔2minQ(ℓ),τY^( ) 2 \Q^( ),τ\, we can write ^m(p,q)=1m∑ℓ=1mY(ℓ) H_m(p,q)= 1m _ =1^mY^( ). We first bound the truncation bias. Since r>1r>1, we have 0≤2μ(p,q)−[Y(ℓ)] 0≤ 2μ(p,q)-E[Y^( )] =2[(Q(ℓ)−τ)+]≤2[(Q(ℓ))r]τr−1≤2Mαrτr−1. =2E [(Q^( )-τ)_+ ]\;≤\; 2E [(Q^( ))^r ]τ^r-1≤ 2M_α^rτ^r-1. (55b) We are now set up to apply the empirical Bernstein inequality of Maurer and Pontil [32, Theorem 4]. We apply it to both the i.i.d. variables Y(ℓ)/(2τ)∈[0,1]Y^( )/(2τ)∈[0,1], and then separately to the i.i.d. variables 1−Y(ℓ)/(2τ)1-Y^( )/(2τ). Observe that the two collections have the same empirical variance. We apply a failure probability of η/2η/2 to each application, so that a union bound over both tail bounds has failure probability at most η. Via this argument, we are guaranteed to have the two-sided tail bound |[Y(ℓ)]−^m(p,q)| |E[Y^( )]- H_m(p,q) | ≤2V^log(4/η)m+14τlog(4/η)3(m−1) ≤ 2 V (4/η)m+ 14τ (4/η)3(m-1) (55c) with probability at least 1−η1-η. Combining the truncation bias (55b) with the tail bound (55c), we find that |2μ(p,q)−^m(p,q)| |2μ(p,q)- H_m(p,q) | ≤2V^log(4/η)m+14τlog(4/η)3(m−1)+2Mαrτr−1 ≤ 2 V (4/η)m+ 14τ (4/η)3(m-1)+ 2M_α^rτ^r-1 with probability at least 1−η1-η. We claim that the right-hand side of this bound is precisely r^m(η) r_m(η). In particular, we can express the truncation level (33b) as τ=Mαcη−1/rτ=M_αc_η^-1/r, where cη≔7log(4/η)3(m−1)c_η 7 (4/η)3(m-1). In terms of this shorthand, we have 14τlog(4/η)3(m−1)=2Mαcη1−1/r 14τ (4/η)3(m-1)=2M_αc_η^1-1/r and 2Mαrτr−1=2Mαcη1−1/r 2M_α^rτ^r-1=2M_αc_η^1-1/r. Since 1/r=2/α1/r=2/α, the claimed equivalence follows, and we conclude that |2μ(p,q)−^m(p,q)| |2μ(p,q)- H_m(p,q) | ≤r^m(η) ≤ r_m(η) (55d) with probability at least 1−η1-η. It remains to prove the sandwich (34a) claimed in the statement. Conditioned on the event (55d), the upper inequality in equation (55a) gives (p,q) H(p,q) ≤2μ(p,q)≤^m(p,q)+r^m(η). ≤ 2μ(p,q)≤ H_m(p,q)+ r_m(η). For the other side, the same concentration event and the lower inequality in equation (55a) give ^m(p,q)+r^m(η) H_m(p,q)+ r_m(η) ≤2μ(p,q)+2r^m(η)≤2(p,q)+r^m(η). ≤ 2μ(p,q)+2 r_m(η)≤ 2 \ H(p,q)+ r_m(η) \. Combining the last two displays proves the claim (34a). 6.4 Proof of Theorem 2 We need to verify two separate claims: the stated bound (37b) on the KL divergence, and the fact that the procedure terminates in at most N unmasking rounds. Throughout the proof, we make use of the shorthand ak≔4^UGC()Nk^k,m+r^kso that ρ^k=min1,ak. a_k 4 C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(P)N S_k H_k,m+ r_k so that $ ρ_k= \1,a_k\$. (56) 6.4.1 Verifying the KL bound (37b) Our first step is to apply Proposition 2 with failure probability η/K∈(0,1)η/K∈(0,1) to each block [bk,bk+1][b_k,b_k+1]. The estimator in this proposition gives us an estimate ^k,m≥0 H_k,m≥ 0 along with the upper confidence correction r^k>0 r_k>0. By the union bound over all K blocks, with probability at least 1−η1-η, we are guaranteed to have k H_k ≤^k,m+r^kfor all k=0,…,K−1, ≤ H_k,m+ r_k for all $k=0,…,K-1$, (57) where we have used inequality (A) in equation (34a). We condition on this “good event” throughout the remainder of the proof. For each block, we define the iteration count N^k≔⌈klog(1+ρ^k)⌉ N_k S_k (1+ ρ_k) , using the stepsizes ρ^k ρ_k specified in the theorem statement. Observe that from our choice of ρ^k ρ_k and the definition (20) of the geometric schedule, it takes at most N^k N_k iterations to traverse the block, and every step inside this block has reveal-odds multiplier at most 1+ρ^k1+ ρ_k. We now apply Theorem 1 to this concatenated multi-block schedule. By the additivity (3) of H, the contribution from block k takes the form ρ^kk ρ_k H_k. Summing up these terms, along with the boundary correction, yields DKL(ℙZ∥ℙZ^) D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $(P_Z\|P_ Z) ≤∑k=0K−1ρ^k+DKL(ℙt0∥ℚt0)+Γ(T) ≤ _k=0^K-1 ρ_k H_k+D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $(P_t_0\|Q_t_0)+ _ C(T) ≤(i)∑k=0K−1ρ^k(^k,m+r^k)+DKL(ℙt0∥ℚt0)+Γ(T) (i)≤ _k=0^K-1 ρ_k( H_k,m+ r_k)+D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $(P_t_0\|Q_t_0)+ _ C(T) ≤(ii)∑k=0K−14^UGC()Nk^k,m+r^k⏟=ak(^k,m+r^k)+DKL(ℙt0∥ℚt0)+Γ(T) (i)≤ _k=0^K-1\;\; 4 C_ 0.0pt 752356262144 0.0pt$ UGC$ 0.0pt 752356262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$ 0.0pt 752357262144 0.0pt$ UGC$(P)N S_k H_k,m+ r_k_=a_k\;( H_k,m+ r_k)+D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $(P_t_0\|Q_t_0)+ _ C(T) =4^UGC()N∑k=0K−1k(^k,m+r^k)+DKL(ℙt0∥ℚt0)+Γ(T) = 4 C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(P)N _k=0^K-1 S_k( H_k,m+ r_k)+D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $(P_t_0\|Q_t_0)+ _ C(T) =(iii)4^UGC()N+DKL(ℙt0∥ℚt0)+Γ(T), (i)= 4 C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(P)N+D_ 0.0pt 606267262144 0.0pt$ $ 0.0pt 606267262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $ 0.0pt 538142262144 0.0pt$ $(P_t_0\|Q_t_0)+ _ C(T), where step (i) uses the good event bound (57); step (i) uses the fact that ρ^k≤ak ρ_k≤ a_k, along with the definition of aka_k; and equality (i) follows from the definition of ^UGC() C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(P). 6.4.2 Verifying the score-evaluation budget It remains to verify that the procedure terminates in at most N unmasking rounds, so that it satisfies the prescribed score evaluation budget. Since ρ^k∈[0,1] ρ_k∈[0,1] and log(1+u)≥u/2 (1+u)≥ u/2 for u∈[0,1]u∈[0,1], we have N^k≤ 1+klog(1+ρ^k)≤ 1+2kρ^k N_k\;≤\;1+ S_k (1+ ρ_k)\;≤\;1+ 2 S_k ρ_k =1+2kmax1,1ak =1+2 S_k \1, 1a_k\ ≤1+2k+N2^UGC()k(^k,m+r^k). ≤ 1+2 S_k+ N2 C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(P) S_k( H_k,m+ r_k). We now sum over blocks, using the definition (25) of k S_k, and the definition of ^UGC() C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(P). Doing so yields ∑k=0K−1N^k _k=0^K-1 N_k ≤K+2∑k=0K−1k+N2^UGC()∑k=0K−1k(^k,m+r^k) ≤ K+2 _k=0^K-1 S_k+ N2 C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(P) _k=0^K-1 S_k( H_k,m+ r_k) =K+2φ(T)−φ(t0)+N2 =K+2 \ (T)- (t_0) \+ N2 ≤N, ≤ N, where the final inequality follows from the assumed lower bound N≥2K+4φ(T)−φ(t0)N≥ 2K+4 \ (T)- (t_0) \. 6.5 Proof of Theorem 3 We split our proof into two parts, corresponding to the two claims in the theorem. 6.5.1 Proof of the claim (41a) Introducing the shorthand (λ)≔(λ) f(λ) q(λ) and F⋆≔∫−ℓdℓd(λ)λF_ _- _d _d f(λ)\,dλ, we need to prove that infUGC()=F⋆2 _P C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(P)=F_ ^2. By the definition (40b), for a partition of [−ℓd,ℓd][- _d, _d] into intervals LkL_k with length |Lk||L_k|, applying the Cauchy–Schwarz inequality on each interval gives UGC() C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(P) =∑k|Lk|∫Lk(λ)λ≥∑k∫Lk(λ)λ=F⋆. = _k |L_k| _L_k q(λ)\,dλ≥ _k _L_k f(λ)\,dλ=F_ . (58) Conversely, let KU_K be a uniform K-block partition with blocks Lk\L_k\. By the integral form of the mean-value theorem, we can write ∫Lk(λ)λ=|Lk|(ξk) _L_k q(λ)dλ\;=\;|L_k| q( _k) for some ξk∈Lk _k∈ L_k, and consequently, we obtain infUGC()≤UGC(K) _P C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(P)≤ C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(U_K) =∑k|Lk|∫Lk(λ)λ=∑k(ξk)|Lk|. = _k |L_k| _L_k q(λ)\,dλ\;= _k f( _k)|L_k|. The quantity on the right-hand side is a Riemann sum for f; taking the limit as K→+∞K→+∞ shrinks the intervals to zero, and so it converges to F⋆F_ . We have thus shown that infUGC()≤F⋆2 _P C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(P)≤ F_ ^2. Combined with the lower bound (58), the proof is complete. 6.5.2 Proof of the claim (41b) Recall our shorthand = f= q and F⋆=∫−ℓdℓd(λ)λF_ = _- _d _d f(λ)\,dλ. For a pair −ℓd≤x<y≤ℓd- _d≤ x<y≤ _d, introduce the shorthand γ(x,y)≔Γumask(R(x),R(y))γ(x,y) _ 0.0pt 1204822262143 0.0pt$ $ 0.0pt 1204822262143 0.0pt$ $ 0.0pt 1061162262144 0.0pt$ $ 0.0pt 1061165262144 0.0pt$ $ (R(x),R(y) ) where R(λ)=eλ1+eλR(λ)= e^λ1+e^λ. By changing variables in equation (50a), and using the derivative R′(t)=R(t)1−R(t)R (t)=R(t)\1-R(t)\, we obtain γ(x,y)=∫xy(t)R(y)−R(t)R′(t)t. γ(x,y)= _x^y q(t) R(y)-R(t)R (t)\,dt. (59a) Define the constants m≔min[−ℓd,ℓd]R′>0m _[- _d, _d]R >0, M≔maxλ∈[−ℓd,ℓd]R′(λ)<∞M _λ∈[- _d, _d]R (λ)<∞, and qmin≔minλ∈[−ℓd,ℓd](λ)>0q_ _λ∈[- _d, _d] q(λ)>0. We then have R(y)−R(t)≥m(y−t)R(y)-R(t)≥ m(y-t) and R′(t)≤MR (t)≤ M, from which equation (59a) implies that γ(x,y)≥c0(y−x)2where c0≔qminm2M. γ(x,y)≥ c_0(y-x)^2 where $c_0 q_ m2M$. (59b) In addition, we claim that γ(x,x+δ)=12(x)δ2+o(δ2)uniformly in x. γ(x,x+δ)= 12 q(x)δ^2+o(δ^2) uniformly in $x$. (59c) Writing t=x+st=x+s, uniform continuity of R′R on [−ℓd,ℓd][- _d, _d], together with the fact that it is bounded away from zero over this interval, imply that R(x+δ)−R(x+s)R′(x+s) R(x+δ)-R(x+s)R (x+s) =(δ−s)1+o(1) =(δ-s)\1+o(1)\ uniformly in x and 0≤s≤δ0≤ s≤δ. Similarly, the continuity of q gives (x+s)=(x)+o(1) q(x+s)= q(x)+o(1) uniformly. Substituting these two estimates into equation (59a) and integrating over s∈[0,δ]s∈[0,δ] yields the local expansion bound (59c). Upper bound: For the upper bound, we choose the grid λk,Nk=0N\ _k,N\_k=0^N to have equal f-mass, so that ∫λk,Nλk+1,N(λ)λ=F⋆N _ _k,N _k+1,N f(λ)\,dλ= F_ N. Since f is continuous and bounded away from zero, this mesh has width O(N−1)O(N^-1), and hence we have (λk,N)(λk+1,N−λk,N)2=F⋆2N2+o(N−2) q( _k,N)( _k+1,N- _k,N)^2= F_ ^2N^2+o(N^-2) uniformly in k. Equation (59c) therefore gives ∑k=0N−1γ(λk,N,λk+1,N)=F⋆22N+o(N−1). _k=0^N-1γ( _k,N, _k+1,N)= F_ ^22N+o(N^-1). (59d) Lower bound: For the lower bound, we take a grid μk,Nk=0N\ _k,N\_k=0^N whose cost is within N−2N^-2 of the infimum, and write δk,N=μk+1,N−μk,N _k,N= _k+1,N- _k,N. The preceding upper bound shows that the infimum is O(N−1)O(N^-1), so the near-optimal grid μk,N\ _k,N\ also has total cost O(N−1)O(N^-1). Consequently, the quadratic lower bound (59b) gives c0∑k=0N−1δk,N2 c_0 _k=0^N-1 _k,N^2 ≤∑k=0N−1γ(μk,N,μk+1,N)=O(N−1), ≤ _k=0^N-1γ( _k,N, _k+1,N)=O(N^-1), and hence ∑kδk,N2=O(N−1) _k _k,N^2=O(N^-1). Since maxkδk,N2≤∑kδk,N2=O(N−1) _k _k,N^2≤ _k _k,N^2=O(N^-1), the mesh tends to zero, so the uniform local expansion may be summed over the grid with total remainder o(∑kδk,N2)=o(N−1)o ( _k _k,N^2 )=o(N^-1). Doing so yields ∑k=0N−1γ(μk,N,μk+1,N)=12∑k=0N−1(μk,N)δk,N2+o(N−1) _k=0^N-1γ( _k,N, _k+1,N)= 12 _k=0^N-1 q( _k,N) _k,N^2+o(N^-1) ≥(i)12N∑k=0N−1(μk,N)δk,N2+o(N−1) (i)≥ 12N \ _k=0^N-1 f( _k,N) _k,N \^2+o(N^-1) =(ii)F⋆22N+o(N−1), (i)= F_ ^22N+o(N^-1), where step (i) follows from the Cauchy–Schwarz inequality and =2 q= f^2; and the last step follows from the Riemann-sum limit ∑k(μk,N)δk,N=F⋆+o(1) _k f( _k,N) _k,N=F_ +o(1). Finally, combining this lower bound with the upper bound (59d) yields the claim. 7 Discussion In this paper, we have shown that the unmasking growth complexity (UGC) controls the performance of random subset unmasking schemes, and reveals the structure required to optimize their performance. It is a path-based measure with additive local increments that bound the corresponding KL discretization errors. The reveal odds determine the natural multiplicative scale for a finite unmasking step, making log-reveal-odds the appropriate path coordinate. The log-reveal-odds UGC density gives a local description of sampling difficulty: regions carrying little UGC mass can be traversed rapidly with large stepsizes, whereas regions of concentrated mass require smaller stepsizes. We formalized this resource-allocation principle via a notion of partition complexity. At one extreme, it reduces to a (coarse) single-block complexity; under progressive refinement, it converges to a functional of the square root of the UGC density, which also determines the sharp leading-order complexity of optimally scheduled Euler discretization. Notably, this paper moves beyond treating the underlying geometry as an oracle quantity. We show how the UGC increments can be reliably estimated using KL increments along a coupled reveal trajectory. By doing so, we obtain sampling methods that are certified-optimal, meaning that they are certified (with high probability) to achieve a pre-specified KL error, and their iteration complexity is within a constant factor of the optimal iteration complexity. Thus, our analysis connects three core tasks in diffusion sampling: characterizing the geometry of the target distribution, designing a sampling schedule, and certifying the accuracy of the resulting sampler. Let us make note of some important qualifications to this conclusion. Our strongest data-dependent guarantees rely on access to Bayes denoisers and on moment control for their KL increments. With learned denoisers, approximation error contributes an additional term to the KL guarantee, and it needs to be estimated for a fully certified guarantee. Moreover, our notion of optimality is relative to frozen-poster Euler discretizations. It is possible that higher-order discretizations and other more sophisticated procedures could admit different local geometries, and hence potentially different optimal clocks for stepsize allocation. This paper has focused exclusively on the utility of UGC complexity for designing and optimizing unmasking samplers. However, thinking beyond the context of sampling, the view of data geometry afforded by the UGC density is of independent interest for statistical analysis. As a notable example, Figure 3 shows the UGC density q for a discrete mixture model with a hierarchical structure, where the q-modes correspond to reveal times at which successive levels of the hierarchy are resolved. Our methods allow us to reliably estimate increments of the UGC density, and it would be interesting to do so for real-world discrete datasets. In our companion paper [50] on Gaussian diffusion sampling, we introduced the denoising growth complexity (DGC), and provided analogous results on sampling performance and stepsize optimization, again culminating in a characterization via the DGC density. Despite the substantial differences between Gaussian diffusion and discrete masking, the two theories exhibit a striking parallel. The natural path coordinates differ (log-heat-time versus log-reveal-odds), but both the UGC and DGC densities capture a form of information curvature along the noising path, and their shape dictates how computational effort should be allocated. Acknowledgements This work was partially supported by a Guggenheim Fellowship, an NSF grant (DMS-2311072), and the Ford Professorship at MIT. We thank Yuting Wei for her inspiring talk during the MIT Statistics and Data Science conference in spring 2026. References [1] N. Alon and J. H. Spencer (2016) The probabilistic method. 4 edition, John Wiley & Sons. External Links: ISBN 978-1-119-06195-3 Cited by: §5.2.1. [2] D. F. Anderson, A. Ganguly, and T. G. Kurtz (2011) Error analysis of tau-leap simulation methods. The Annals of Applied Probability 21 (6), p. 2226–2262. External Links: Document Cited by: §1.2. [3] J. Austin, D. D. Johnson, J. Ho, D. Tarlow, and R. van den Berg (2021) Structured denoising diffusion models in discrete state-spaces. In Advances in Neural Information Processing Systems, Vol. 34. Cited by: §1.2, §1. [4] L. Barnett, C. L. Buckley, and S. Bullock (2009) Neural complexity and structural connectivity. Physical Review E 79 (5), p. 051914. External Links: Document Cited by: Appendix A, §2.2. [5] J. Benton, V. De Bortoli, A. Doucet, and G. Deligiannidis (2024) Nearly d-linear convergence bounds for diffusion models via stochastic localization. In International Conference on Learning Representations (ICLR) 2024, External Links: Link Cited by: §1. [6] S. Brooks, A. Gelman, G. L. Jones, and X. L. Meng (2011) Handbook of Markov chain Monte Carlo. CRC Press. Cited by: §1. [7] J. Buzzi and L. Zambotti (2012) Approximate maximizers of intricacy functionals. Probability Theory and Related Fields 153 (3–4), p. 421–440. External Links: Document Cited by: Appendix A, §2.2. [8] J. Buzzi and L. Zambotti (2012) Mean mutual information and symmetry breaking for finite random fields. Annales de l’Institut Henri Poincaré, Probabilités et Statistiques 48 (2), p. 343–367. External Links: Document Cited by: Appendix A, §2.2. [9] A. Campbell, J. Benton, V. D. Bortoli, T. Rainforth, G. Deligiannidis, and A. Doucet (2022) A continuous time framework for discrete denoising models. In Advances in Neural Information Processing Systems, Vol. 35. External Links: Document Cited by: §1.2, §1. [10] H. Chang, H. Zhang, J. Barber, A. Maschinot, J. Lezama, L. Jiang, M. Yang, K. P. Murphy, W. T. Freeman, M. Rubinstein, Y. Li, and D. Krishnan (2023) Muse: text-to-image generation via masked generative transformers. In Proceedings of the 40th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 202, p. 4055–4075. Cited by: §1. [11] H. Chang, H. Zhang, L. Jiang, C. Liu, and W. T. Freeman (2022) MaskGIT: masked generative image transformer. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), p. 11315–11325. Cited by: §1. [12] H. Chen, H. Lee, and J. Lu (2023) Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptions. In International Conference on Machine Learning, External Links: 2211.01916 Cited by: §1. [13] M. Chen, S. Mei, J. Fan, and M. Wang (2024) An overview of diffusion models: applications, guided generation, statistical rates and optimization. arXiv preprint arXiv:2404.07771. External Links: Link Cited by: §1. [14] S. Chen, S. Chewi, J. Li, Y. Li, A. Salim, and A. R. Zhang (2023) Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. In International Conference on Learning Representations, External Links: 2209.11215 Cited by: §1. [15] S. Chen, K. Cong, and J. Li (2025) Optimal inference schedules for masked diffusion models. arXiv preprint arXiv:2511.04647. External Links: 2511.04647, Link Cited by: Appendix A, Appendix A, Appendix A, §1.1, §1.2, §1, 1st item, §3.2, §6.2. [16] F.-A. Croitoru, V. Hondru, R. T. Ionescu, and M. Shah (2023) Diffusion models in vision: a survey. IEEE Transactions on Pattern Analysis and Machine Intelligence 45 (9), p. 10850–10869. External Links: Document Cited by: §1. [17] D. Dmitriev, Z. Huang, and Y. Wei (2026) Efficient sampling with discrete diffusion models: sharp and adaptive guarantees. arXiv preprint arXiv:2602.15008. External Links: 2602.15008, Link Cited by: Appendix A, Appendix A, §C.1.3, §C.2, §C.2, §1.1, §1.1, §1.2, §1, 1st item, §2.2, §3.3.2, §3.4. [18] A. Gelman, J. Carlin, H. S. Stern, D. B. Dunson, A. Vehtari, and D. K. Salomon (2013) Bayesian data analysis. CRC Press. Cited by: §1. [19] M. Ghazvininejad, O. Levy, Y. Liu, and L. Zettlemoyer (2019) Mask-Predict: parallel decoding of conditional masked language models. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), p. 6112–6121. External Links: Document Cited by: §1. [20] D. T. Gillespie (2001) Approximate accelerated stochastic simulation of chemically reacting systems. The Journal of Chemical Physics 115 (4), p. 1716–1733. External Links: Document Cited by: Appendix A, §1.2. [21] T. S. Han (1975) Linear dependence structure of the entropy space. Information and Control 29 (4), p. 337–368. External Links: Document Cited by: Appendix A, §1.1, §1.2, §2.2. [22] T. S. Han (1978) Nonnegative entropy measures of multivariate symmetric correlations. Information and Control 36 (2), p. 133–156. External Links: Document Cited by: Appendix A, §1.1, §1.2, §2.2. [23] J. Ho, A. Jain, and P. Abbeel (2020) Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems (NeurIPS) 33, p. 6840–6851. Cited by: §1. [24] E. Hoogeboom, D. Nielsen, P. Jaini, P. Forré, and M. Welling (2021) Argmax flows and multinomial diffusion: learning categorical distributions. In Advances in Neural Information Processing Systems, Vol. 34. Cited by: §1.2, §1. [25] H. Lavenant and G. Zanella (2025) Error bounds and optimal schedules for masked diffusions with factorized approximations. arXiv preprint arXiv:2510.25544. External Links: 2510.25544, Link Cited by: Appendix A, §1.1, §1.2, 2nd item, §5.1. [26] G. Li and C. Cai (2025) Breaking AR’s sampling bottleneck: provable acceleration via diffusion language models. In Advances in Neural Information Processing Systems, Vol. 38. External Links: 2505.21400, Link Cited by: §1.2. [27] T. Li (2007) Analysis of explicit tau-leaping schemes for simulating chemically reacting systems. Multiscale Modeling & Simulation 6 (2), p. 417–436. External Links: Document Cited by: §1.2. [28] Y. Liang, R. Huang, L. Lai, N. Shroff, and Y. Liang (2025) Absorb and converge: provable convergence guarantee for absorbing discrete diffusion models. In Advances in Neural Information Processing Systems, Vol. 38. External Links: 2506.02318, Link Cited by: §1.2. [29] Y. Liang, Y. Liang, L. Lai, and N. Shroff (2025) Discrete diffusion models: novel analysis and new sampler guarantees. In Advances in Neural Information Processing Systems, Vol. 38. External Links: 2509.16756, Link Cited by: §1.2. [30] G. G. Lorentz (1986) Bernstein Polynomials. Second edition, Chelsea Publishing Company, New York. Cited by: §B.2. [31] A. Lou, C. Meng, and S. Ermon (2024) Discrete diffusion modeling by estimating the ratios of the data distribution. In Proceedings of the 41st International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 235, p. 32819–32848. External Links: Link Cited by: §1.2, §1. [32] A. Maurer and M. Pontil (2009) Empirical Bernstein bounds and sample variance penalization. In Proceedings of the 22nd Conference on Learning Theory, External Links: 0907.3740 Cited by: §6.3.2. [33] S. Nie, F. Zhu, Z. You, X. Zhang, J. Ou, J. Hu, J. Zhou, Y. Lin, J. Wen, and C. Li (2025) Large language diffusion models. In Advances in Neural Information Processing Systems, Vol. 38. Cited by: §1. [34] E. Olbrich, N. Bertschinger, N. Ay, and J. Jost (2008) How should complexity scale with system size?. The European Physical Journal B 63 (3), p. 407–415. External Links: Document Cited by: Appendix A, §2.2. [35] G. M. Phillips (2003) Interpolation and Approximation by Polynomials. Springer-Verlag, New York. Cited by: §B.2. [36] M. Rathinam, L. R. Petzold, Y. Cao, and D. T. Gillespie (2005) Consistency and stability of tau-leaping schemes for chemical reaction systems. Multiscale Modeling & Simulation 4 (3), p. 867–895. External Links: Document Cited by: §1.2. [37] Y. Ren, H. Chen, G. M. Rotskoff, and L. Ying (2025) How discrete and continuous diffusion meet: comprehensive analysis of discrete diffusion models via a stochastic integral framework. In International Conference on Learning Representations, External Links: 2410.03601, Link Cited by: §1.2. [38] Y. Ren, H. Chen, Y. Zhu, W. Guo, Y. Chen, G. M. Rotskoff, M. Tao, and L. Ying (2025) Fast solvers for discrete diffusion models: theory and applications of high-order algorithms. In Advances in Neural Information Processing Systems, Vol. 38. External Links: 2502.00234, Link Cited by: §1.2. [39] C. P. Robert and G. Casella (2004) Monte carlo statistical methods. 2 edition, Springer Texts in Statistics, Springer, New York. External Links: Document, ISBN 978-0-387-21239-5 Cited by: §1. [40] R. Rombach, E. Blattmann, S. L. Dhariwal, A. M. D. M. L., and P. E. S. (2022) High-resolution image synthesis with latent diffusion models. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), p. 10684–10694. Cited by: §1. [41] F. E. Rosas, P. A. M. Mediano, M. Gastpar, and H. J. Jensen (2019) Quantifying high-order interdependencies via multivariate extensions of the mutual information. Physical Review E 100 (3), p. 032305. External Links: Document Cited by: Appendix A, §2.2. [42] R. Y. Rubinstein and D. P. Kroese (2008) Simulation and the monte carlo method. 2nd edition, John Wiley and Sons, Hoboken, NJ. Cited by: §1. [43] S. S. Sahoo, M. Arriola, Y. Schiff, A. Gokaslan, E. Marroquin, J. T. Chiu, A. Rush, and V. Kuleshov (2024) Simple and effective masked diffusion language models. In Advances in Neural Information Processing Systems, Vol. 37. Cited by: §1.2, §1, §1. [44] J. Shi, K. Han, Z. Wang, A. Doucet, and M. K. Titsias (2024) Simplified and generalized masked diffusion for discrete data. In Advances in Neural Information Processing Systems, Vol. 37. Cited by: §1.2, §1. [45] J. Sohl‑Dickstein, E. Weiss, N. Maheswaranathan, and S. Ganguli (2015) Deep unsupervised learning using nonequilibrium thermodynamics. In Proceedings of the 32nd International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 37, p. 2256–2265. External Links: Link Cited by: §1. [46] Y. Song and S. Ermon (2019) Generative modeling by estimating gradients of the data distribution. In Advances in Neural Information Processing Systems (NeurIPS), p. 11895–11907. Cited by: §1. [47] Y. Song, J. Sohl-Dickstein, D. P. Kingma, A. Kumar, S. Ermon, and B. Poole (2021) Score-based generative modeling through stochastic differential equations. In International Conference on Learning Representations, Cited by: §1. [48] G. Tononi, O. Sporns, and G. M. Edelman (1994) A measure for brain complexity: relating functional segregation and integration in the nervous system. Proceedings of the National Academy of Sciences of the United States of America 91 (11), p. 5033–5037. External Links: Document Cited by: Appendix A, §1.1, §1.2, §2.2. [49] T. F. Varley, M. Pope, J. Faskowitz, and O. Sporns (2023) Multivariate information theory uncovers synergistic subsystems of the human cerebral cortex. Communications Biology 6, p. 451. External Links: Document Cited by: Appendix A, §2.2. [50] M. J. Wainwright (2026) Denoising growth complexity: Data geometry and certified schedules for diffusion sampling. Technical report Technical Report arXiv:2607.26285, Massachusetts Institute of Technology. External Links: 2607.26285, Link Cited by: §1.1, §1.2, §4.2, §5.2.2, §7. [51] X. Wang, Z. Zheng, F. Ye, D. Xue, S. Huang, and Q. Gu (2024) Diffusion language models are versatile protein learners. In Proceedings of the 41st International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 235, p. 52309–52333. Cited by: §1. [52] Y. Wang, H. Zhan, L. Liu, R. Zeng, H. Guo, J. Zheng, Q. Zhang, X. Zhang, S. Zhang, and Z. Wu (2025) MaskGCT: zero-shot text-to-speech with masked generative codec transformer. In International Conference on Learning Representations, Cited by: §1. [53] S. Watanabe (1960) Information theoretical analysis of multivariate correlation. IBM Journal of Research and Development 4 (1), p. 66–82. External Links: Document Cited by: Appendix A, §1.1, §1.2, §2.2. [54] L. Yang, Z. Zhang, Y. Song, and et al. (2025) Diffusion models: a comprehensive survey of methods and applications. ACM Computing Surveys (to appear). Note: arXiv:2209.00796 Cited by: §1. [55] L. Yu, Y. Cheng, K. Sohn, J. Lezama, H. Zhang, H. Chang, A. G. Hauptmann, M. Yang, Y. Hao, I. Essa, and L. Jiang (2023) MAGVIT: masked generative video transformer. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), p. 10459–10469. Cited by: §1. Appendix A Consequences of single-block theory In this appendix, we discuss some consequences of Corollary 1, which gives single-block stepsize schedules with iteration complexity depending on the aggregate UGC masses (0,1) H(0,1) and card(0,d) H^card(0,d), for the Bernoulli and fixed-cardinality samplers, respectively. For this reason, it is interesting to relate the aggregate UGC mass to other complexity measures, and thereby to relate these complexity measures to the sampling guarantees in the papers [15, 17]. We begin by observing that the aggregate UGC mass (0,1) H(0,1) turns out to be equivalent to a measure of multivariate dependence first introduced by Tononi, Sporns, and Edelman [48] for modeling brain function. This complexity measure, hereafter referred to as TSE, has since been studied by various authors [34, 4, 41, 49], and also extended to a more general notion of intricacy [7, 8]. The TSE complexity is given by (ℙZ) TSE(P_Z) ≔∑k=1d(ek−kded)where ek≔[Ent(ZAk)], _k=1^d (e_k- kde_d ) where $e_k [Ent(Z_A_k) ]$, (60) with AkA_k being a uniformly random subset of [d][d] with k elements. We establish its equivalence to the aggregate UGC mass as part of Proposition 3 below. Turning to sampling connections, the paper [15] analyzed the fixed-cardinality sampler, and gave guarantees in terms of the minimum of two classical measures of multivariate dependence [53, 21, 22], known as the total correlation and dual total correlation, defined by (ℙZ)≔∑i=1dEnt(Zi)−Ent(Z)and(ℙZ)≔Ent(Z)−∑i=1dEnt(Zi∣Z−i). TC(P_Z) _i=1^dEnt(Z_i)-Ent(Z) and DTC(P_Z) (Z)- _i=1^dEnt(Z_i Z_-i). (61a) Here EntEnt denotes the Shannon entropy, whereas Z−iZ_-i denotes the (d−1)(d-1)-dimensional subvector of all coordinates except the ithi^th. The single-block sampling guarantee in terms of card(0,d) H^card(0,d), or equivalently (0,1) H(0,1), sharpens these guarantees for the fixed-cardinality sampler. As we show in Section B.2, in particular via a Bernstein polynomial representation, the total and dual total correlation measures have the simple representations (ℙZ)=∫01(1−t)′(t)tand(ℙZ)=∫01t′(t)t. TC(P_Z)= _0^1(1-t) h (t)dt and DTC(P_Z)= _0^1t h (t)dt. (61b) Since (0,1)=∫01t(1−t)′(t)t H(0,1)= _0^1t\,(1-t) h (t)dt, we see immediately that (0,1) H(0,1) ≤min(ℙZ),(ℙZ). ≤ \ TC(P_Z), DTC(P_Z)\. (61c) In their work on continuous-time Markov chain (CTMC) sampling, Dmitriev et al. [17] gave a CTMC unmasking sampler with iteration complexity controlled by a functional (ℙZ) DHW(P_Z), which they refer to as effective total correlation, that is also upper bounded by the minimum of the TC and DTC complexities. We also show as part of Proposition 3 that this functional is lower bounded by (0,1) H(0,1), and can be upper bounded by a constant multiple of it. Thus, both the Bernoulli and fixed-cardinality samplers, in their single-block instantiation, inherit the guarantees of the DHW analysis. In particular, their paper studies various interesting examples, including stochastic block models and quantized versions of low-dimensional structure, for which (ℙZ) DHW(P_Z), and hence (0,1) H(0,1) and card(0,d) H^card(0,d), are relatively small. Notably, they construct an instance with min(ℙZ),(ℙZ)=Θ(d) \ TC(P_Z), DTC(P_Z)\= (d), whereas their complexity has constant scaling. Our analysis shows that the guarantees on CTMC-based unmasking [17] have analogues for both fixed-cardinality unmasking [15, 25] and Bernoulli unmasking. With this context, we now formally state the complexity relations: Proposition 3 (Connections between aggregate complexity measures). For the full interval [0,1][0,1], the Bernoulli aggregate-UGC complexity is related to TSE complexity via the relation (0,1) H(0,1) =2d+1(ℙZ). = 2d+1 TSE(P_Z). (62a) Moreover, the fixed-cardinality complexity card(0,d) H^card(0,d) is sandwiched by the Bernoulli version (0,1)≤card(0,d)≤ 2(0,1). H(0,1)\;≤\; H^card(0,d)\;≤\;2 H(0,1). (62b) Finally, the DHW complexity satisfies the sandwich relation (0,1)≤(iii)(ℙZ)≤(iv)e−1(0,1). H(0,1)\; (i)≤\; DHW(P_Z)\; (iv)≤\; ee-1 H(0,1). (62c) We prove these claims in Section C.1; let us highlight a few interesting features here. The proofs of both claims (62a) and (62b) make use of a Bernstein polynomial representation of h, a result of independent interest. In particular, we show in Section B.2 that (t) h(t) =∑j=0d−1(d−1j)tj(1−t)d−1−jjcard, = _j=0^d-1 d-1jt^j(1-t)^d-1-j h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j, (63) so that h is a polynomial of degree at most d−1d-1. In proving the sandwich (62c), we show that the DHW complexity functional has the explicit representation (ℙZ)=∫01tmin1,log(1/t)′(t)t DHW(P_Z)= _0^1t \1, (1/t)\ h (t)dt, from which the estimates (62c) follow from simple algebra. The analysis leading to this representation reveals an interesting algorithmic connection to Bernoulli unmasking: the DHW unmasking algorithm, while described and analyzed as a form of τ-leaping [20] in a continuous-time Markov chain, is closely related to the Bernoulli unmasking sampler. See Section C.2 for details of this relation. Appendix B Alternative representations of h In this section, we develop and explore some alternative representations of h and its derivative ′ h that provide useful insight for subsequent proofs. B.1 Proof of the identity (15a) In this appendix, we prove the random subset identity (15a), namely that we can write (t)=∑i=1dAi,t[Info(Zi;ZAi,t)], h(t)= _i=1^dE_A_i,t [Info(Z_i;Z_A_i,t) ], where Ai,t⊆[d]∖iA_i,t [d] \i\ is a random subset obtained by including each coordinate of [d]∖i[d] \i\ independently with probability t. To prove this representation, for each i∈[d]i∈[d], let EiE_i denote the event that coordinate i remains masked at reveal time t, and let A≡Ai,t⊆[d]∖iA≡ A_i,t [d] \i\ denote the set of revealed coordinates. Conditional on EiE_i, the observation XtX_t is equivalent to the pair (A,ZA)(A,Z_A). Consequently, we have the mutual information identity Info(Zi;Xt∣Ei)=Info(Zi,A,ZA)Info(Z_i;X_t E_i)=Info (Z_i;A,Z_A ). By the chain rule for mutual information, we have Info(Zi,A,ZA) (Z_i;A,Z_A ) =Info(Zi,A)⏟=0+Info(Zi;ZA∣A), = Info(Z_i;A)_=0+Info (Z_i;Z_A A ), using the fact that ZiZ_i and A≡Ai,tA≡ A_i,t are independent. Conditioning on A=aA=a does not change the joint law of (Zi,ZA)(Z_i,Z_A), so that we have shown that Info(Zi;Xt∣Ei)=Info(Zi;ZA∣A) (Z_i;X_t E_i)\;=\;Info(Z_i;Z_A A) =∑aℙ(A=a)Info(Zi;Za)=A[Info(Zi;ZA)]for each i=1,…,d. = _aP(A=a)Info(Z_i;Z_a)=E_A [Info(Z_i;Z_A) ] for each $i=1,…,d$. Summing this identity over the coordinate index i yields the claim (15a). B.2 Representation via Bernstein polynomials In this section, we develop representations of both h and ′ h as Bernstein polynomials in terms of the coefficients jcard h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j. These representations have some useful immediate consequences, and are used in the proofs in Appendix C. Recall the definition of the coefficients jcard h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j ≔∑i=1dBi,j[Info(Zi;ZBi,j)]where Bi,j is uniform over j-cardinality subsets of [d]∖i. _i=1^dE_B_i,j [Info(Z_i;Z_B_i,j) ] where $B_i,j$ is uniform over $j$-cardinality subsets of $[d] \i\$. (64) Letting Ai,tA_i,t be a Bernoulli random subset of [d]∖i[d] \i\ with inclusion probability t, we can write jcard h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j =∑i=1d[Info(Zi;ZAi,t)∣card(Ai,t)=j]. = _i=1^dE [Info(Z_i;Z_A_i,t) (A_i,t)=j ]. Since ℙ[card(Ai,t)=j]=(d−1j)tj(1−t)d−1−jP[card(A_i,t)=j]= d-1jt^j(1-t)^d-1-j, it follows by combining the tower property with the representation (15a) that (t) h(t) =∑j=0d−1(d−1j)tj(1−t)d−1−jjcard. = _j=0^d-1 d-1jt^j(1-t)^d-1-j h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j. (65a) Moreover, by differentiating equation (65a), we obtain ′(t) h (t) =(d−1)∑j=0d−2(d−2j)tj(1−t)d−2−jj+1card−jcard. =(d-1) _j=0^d-2 d-2jt^j(1-t)^d-2-j \ h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j+1- h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j \. (65b) This calculation uses standard properties of derivatives of Bernstein polynomials [30, 35]. (In particular, differentiation transforms coefficients into their first differences.) As one immediate consequence, from equation (65a), we see that h is a polynomial of degree at most d−1d-1. It follows immediately that the derivative ′ h exists. Let us develop two additional consequences. B.2.1 Proof of h-monotonicity We now prove that h is monotone by showing that ′(t)≥0 h (t)≥ 0. The Bernstein polynomial representation (65b) of ′ h shows that it suffices to prove that j+1card≥jcard h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j+1≥ h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j. For 0≤j≤d−20≤ j≤ d-2 and a fixed coordinate i, let AjA_j be a random subset, chosen uniformly from all the j-element subsets of [d]∖i[d] \i\, and, conditionally on AjA_j, let J be uniform over its complement inside [d]∖i[d] \i\. This defines a coupling between the subsets. Then the random set Aj∪JA_j∪\J\ is uniform over the (j+1)(j+1)-element subsets, while the chain rule for mutual information gives the decomposition Info(Zi;ZAj∪J)−Info(Zi;ZAj)=Info(Zi;ZJ∣ZAj)≥0Info(Z_i;Z_A_j∪\J\)-Info(Z_i;Z_A_j)=Info(Z_i;Z_J Z_A_j)≥ 0. Averaging first over the coupling and then over i shows that j+1card−jcard≥0 h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j+1- h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j≥ 0, as claimed. B.2.2 Proof of the total-correlation representations (61b) Now let us prove the representations of the total correlation TC and dual total correlation DTC given in equation (61b). From the random subset representation (15a) of h, we have (1) h(1) =∑i=1dInfo(Zi;Z−i)=∑i=1dEnt(Zi)−Ent(Zi∣Z−i), = _i=1^dInfo(Z_i;Z_-i)\;=\; _i=1^d \Ent(Z_i)-Ent(Z_i Z_-i) \, where the second equality expands the definition of mutual information. By comparing with the definitions (61a), we see immediately that (1)=(ℙZ)+(ℙZ) h(1)= TC(P_Z)+ DTC(P_Z). Since (1)=∫01′(t)t h(1)= _0^1 h (t)dt, using the fact that (0)=0 h(0)=0, if we can prove the identity (ℙZ)=∫01(1−t)′(t)t TC(P_Z)= _0^1(1-t) h (t)dt, then it follows that (ℙZ)=∫01t′(t)t DTC(P_Z)= _0^1t h (t)dt. Accordingly, the remainder of our analysis focuses on the TC representation. For j=1,…,dj=1,…,d, let eje_j be the entropy coefficient defined in equation (60), along with e0=0e_0=0. Note that we have e1=1d∑i=1dEnt(Zi)e_1= 1d _i=1^dEnt(Z_i), and ed=Ent(Z)e_d=Ent(Z). For any i∈[d]i∈[d] and A⊆[d]∖iA [d] \i\, we have the mutual information identity Info(Zi;ZA)=Ent(Zi)+Ent(ZA)−Ent(ZA∪i)Info(Z_i;Z_A)=Ent(Z_i)+Ent(Z_A)-Ent(Z_A∪\i\). It can be averaged over i and over uniform j-cardinality subsets A. Doing so and using the definition (15b) of the jcard h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j coefficients, we find that jcard=d(e1+ej−ej+1). h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j=d (e_1+e_j-e_j+1 ). (66) Substituting this identity into the Bernstein representation (65a) and integrating over the interval [0,1][0,1] yields ∫01(t)t _0^1 h(t)\,dt =∑j=0d−1(d−1j)jcard∫01tj(1−t)d−1−jt=(i)1d∑j=0d−1jcard=(ii)de1−ed=(iii)(ℙZ), = _j=0^d-1 d-1j h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j \ _0^1t^j(1-t)^d-1-jdt\\; (i)= 1d _j=0^d-1 h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j (i)=de_1-e_d\; (i)= TC(P_Z), where step (i) uses the beta-integral identity ∫01(d−1j)tj(1−t)d−1−jt=1d _0^1 d-1jt^j(1-t)^d-1-j\,dt= 1d; step (i) uses the identity (66) along with some algebra; and step (i) follows from the definition (61a) of the total correlation, combined with the definition (60) of the entropy coefficients. Finally, integrating by parts shows that ∫01(t)t=∫01(1−t)′(t)t _0^1 h(t)dt= _0^1(1-t) h (t)dt, where the boundary term vanishes since (0)=0 h(0)=0. This completes the proof of the TC representation in equation (61b). Appendix C Proofs of connecting results In this section, we prove various results that connect the UGC aggregate complexity to other complexity notions (Section C.1), and compare the DHW τ-leaping unmasking algorithm with the Bernoulli unmasking procedure (Section C.2). C.1 Proof of Proposition 3 The proposition consists of three claims, and we prove each of them in turn. C.1.1 Proof of TSE identity (62a) Beginning with the definition (2c), integration by parts yields (0,1)=∫01(2t−1)(t)t H(0,1)= _0^1(2t-1) h(t)\,dt, where the boundary term vanishes since t(1−t)=0t(1-t)=0 at the endpoints. Substituting the Bernstein representation (65a) of h into this equation yields (0,1) H(0,1) =∑j=0d−1jcard(d−1j)∫01(2t−1)tj(1−t)d−1−jt=1d(d+1)∑j=0d−1(2j−d+1)jcard, = _j=0^d-1 h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j d-1j \ _0^1(2t-1)t^j(1-t)^d-1-jdt \\;=\; 1d(d+1) _j=0^d-1(2j-d+1)\; h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j, (67) where the second step follows from a standard beta-integral identity. To complete the proof, we need to relate the entropy coefficients ej=[Ent(ZAj)]e_j=E[Ent(Z_A_j)], where AjA_j is a uniformly random subset of cardinality j, to the jcard h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j coefficients. For each j=0,…,d−1j=0,…,d-1, we can write the mutual information as Info(Zi;ZA)=Ent(Zi)+Ent(ZA)−Ent(ZA∪i)Info(Z_i;Z_A)=Ent(Z_i)+Ent(Z_A)-Ent(Z_A∪\i\). Averaging this identity over i and the j-element subsets A⊆[d]∖iA [d] \i\ yields the relation jcard=d(e1+ej−ej+1) h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j=d (e_1+e_j-e_j+1 ). Substituting this identity into the expression (67) yields (0,1)=1d+1e1∑j=0d−1(2j−d+1)⏟=0+∑j=0d−1(2j−d+1)(ej−ej+1) H(0,1)= 1d+1 \e_1 _j=0^d-1(2j-d+1)_=0+ _j=0^d-1(2j-d+1)(e_j-e_j+1) =1d+12∑j=1d−1ej−(d−1)ed = 1d+1 \2 _j=1^d-1e_j-(d-1)e_d \ =2d+1∑j=1d(ej−jded)=2d+1(ℙZ), = 2d+1 _j=1^d (e_j- jde_d )= 2d+1 TSE(P_Z), which establishes the claim (62a). C.1.2 Proof of the bound (62b) For any 0≤p<q≤10≤ p<q≤ 1, define the multinomial triple (U0,U1,U2)∼Multinomial(d+1,p,q−p, 1−q)(U_0,U_1,U_2) (d+1;\,p,\,q-p,\,1-q ). As claimed previously, we have the identity (p,q) H(p,q) =d+1[card(AU,BU)], = dd+1E [ H^card(A_U,B_U) ], (68) where AU≔maxU0−1,0A_U \U_0-1,0\, and BU≔minU0+U1,dB_U \U_0+U_1,d\. The claims (62b) follow as a special case. For (p,q)=(0,1)(p,q)=(0,1), we have (AU,BU)=(0,d)(A_U,B_U)=(0,d) almost surely, and hence (0,1)=d+1card(0,d) H(0,1)= dd+1 H^card(0,d), from which it follows that (0,1)≤card(0,d)≤2(0,1) H(0,1)≤ H^card(0,d)≤ 2 H(0,1), as claimed. We now prove the claim (68). Introduce the shorthand notation Δj≔jcard−j−1card _j h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j- h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_j-1 and cj≔jd(1−jd)c_j jd (1- jd ), and observe that card(a,b)=∑j=a+1b−1cjΔj. H^card(a,b)= _j=a+1^b-1c_j _j. (69a) Moreover, using the representation (65b) of ′ h as a Bernstein polynomial, we can write t(1−t)′(t) t(1-t) h (t) =∑j=1d−1cjΔjd(dj)tj(1−t)d−j. = _j=1^d-1c_j _j\,d djt^j(1-t)^d-j. (69b) Generate d+1d+1 i.i.d. Unif[0,1]Unif[0,1] random variables YiY_i, and let Y(j+1)Y_(j+1) denote the (j+1)(j+1)-st order statistic. Its density is given by (d+1)(dj)tj(1−t)d−j(d+1) djt^j(1-t)^d-j. Consequently, by integrating the Bernstein expansion (69b) over [p,q][p,q], we obtain (p,q) H(p,q) =d+1∑j=1d−1cjΔjℙ(Y(j+1)∈(p,q)). = dd+1 _j=1^d-1c_j _jP (Y_(j+1)∈(p,q) ). (69c) Now recalling our i.i.d. uniform samples Yii=1d+1\Y_i\_i=1^d+1, define the multinomial count vector U=(U0,U1,U2)U=(U_0,U_1,U_2) via U0≔cardℓ∣Yℓ∈[0,p],U1≔cardℓ∣Yℓ∈(p,q)andU2≔cardℓ∣Yℓ∈[q,1]. U_0 \ Y_ ∈[0,p]\, U_1 \ Y_ ∈(p,q)\ and U_2 \ Y_ ∈[q,1]\. By construction, we have Y(j+1)∈(p,q)Y_(j+1)∈(p,q) if and only if AU<j<BUA_U<j<B_U. Thus, we can rewrite the expression (69c) as (p,q)=d+1[∑j=1d−1cjΔjAU<j<BU] H(p,q)= dd+1E [ _j=1^d-1c_j _j1\A_U<j<B_U\ ] =d+1[∑j=AU+1BU−1cjΔj] = dd+1E [ _j=A_U+1^B_U-1c_j _j ] =d+1[card(AU,BU)], = dd+1E [ H^card(A_U,B_U) ], where the last step uses the representation (69a). This completes the proof of equation (68). C.1.3 Proof of the DHW sandwich (62c) For u≥0u≥ 0, we define a reveal time r=e−ur=e^-u, so that u=log(1/r)u= (1/r) is the log-inverse-reveal time. The analysis of Dmitriev et al. [17] involves a forward masked vector YuY_u; it is related to our reveal process XrX_r via the relation Yu=lawXe−uY_u law=X_e^-u. In the process YuY_u, each coordinate YuiY_u^i equals ZiZ_i with probability r=e−ur=e^-u and equals ⋆ otherwise, and they define the conditional-information density ℐ(u) (u) ≔∑i≠jInfo(Yui;Yuj∣Yu−(i,j)), _i≠ jInfo(Y_u^i;Y_u^j Y_u^-(i,j)), where Yu−(i,j)Y_u^-(i,j) denotes the collection of unmasked coordinates other than i and j. They define the effective total correlation by (ℙZ)≔∫0∞min1,uℐ(u)u DHW(P_Z) _0^∞ \1,u\I(u)\,du. In order to prove the sandwich relation, it suffices to prove the identity ℐ(u) (u) =e−2u′(e−u)for all u≥0. =e^-2u h (e^-u) for all $u≥ 0$. (70a) Indeed, when this identity holds, the change of variables t=e−ut=e^-u guarantees that (ℙZ) DHW(P_Z) =∫01w(t)′(t)t,where w(t)≔tmin1,−logt. = _0^1w(t) h (t)\,dt, where $w(t) t \1,- t\$. (70b) In terms of the shorthand v(t)≔t(1−t)v(t) t\,(1-t), it is straightforward to verify that v(t)≤w(t)≤e−1v(t)for all t∈[0,1], v(t)\;≤\;w(t)\;≤\; ee-1v(t) for all $t∈[0,1]$, from which the sandwich (62c) follows. Proof of the identity (70a): We begin by relating their definitions to equivalent objects in our notation. Fix an ordered pair of indices i≠ji≠ j and let Ari,jA_r^i,j be the random subset of [d]∖i,j[d] \i,j\ obtained by retaining each coordinate independently with probability r. If either i or j is masked, one of the first two arguments in the conditional mutual information is deterministic, and its contribution is zero. The probability that both coordinates are retained is r2r^2. Conditional on this event and on Ari,j=A_r^i,j=A, the three arguments reduce to ZiZ_i, ZjZ_j, and ZAZ_A, respectively. Since the masking pattern is independent of Z, the law of total expectation gives Info(Yui;Yuj∣Yu−(i,j)) (Y_u^i;Y_u^j Y_u^-(i,j)) =r2[Info(Zi;Zj∣ZAri,j)]. =r^2E [Info(Z_i;Z_j Z_A_r^i,j) ]. Moreover, ℙ(Ari,j=A)=rcard(A)(1−r)d−2−card(A)P(A_r^i,j=A)=r^card(A)(1-r)^d-2-card(A). Expanding the expectation and summing over the ordered pairs therefore yields ℐ(u) (u) ≔r2∑i≠j∑A⊆[d]∖i,jrcard(A)(1−r)d−2−card(A)Info(Zi;Zj∣ZA)with r=e−u. r^2 _i≠ j _A [d] \i,j\r^card(A)(1-r)^d-2-card(A)Info(Z_i;Z_j Z_A) with $r=e^-u$. (71a) In order to complete the proof, it suffices to show that ′ h satisfies the identity ′(r) h (r) =∑i≠j∑A⊆[d]∖i,jrcard(A)(1−r)d−2−card(A)Info(Zi;Zj∣ZA). = _i≠ j _A [d] \i,j\r^card(A)(1-r)^d-2-card(A)Info(Z_i;Z_j Z_A). (71b) Our claim (70a) then follows by comparing the two representations (71b) and (71a). To prove the identity (71b), fix an integer k∈0,…,d−2k∈\0,…,d-2\. Beginning with the definition (15b) of kcard h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_k and averaging over the choice of the additional coordinate, we find that (d−1)(d−2k)k+1card−kcard (d-1) d-2k \ h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_k+1- h 0.0pt 813401262143 0.0pt$ $ 0.0pt 813401262143 0.0pt$ $ 0.0pt 714082262144 0.0pt$ $ 0.0pt 714084262144 0.0pt$ $_k \ =∑i≠j∑A⊆[d]∖i,jcard(A)=kInfo(Zi;ZA∪j)−Info(Zi;ZA)⏟Info(Zi;Zj∣ZA), = _i≠ j _ subarraycA [d] \i,j\\\ card(A)=k subarray \Info(Z_i;Z_A∪\j\)-Info(Z_i;Z_A) \_Info(Z_i;Z_j Z_A), where the underbrace relation follows from the chain rule for mutual information. Substituting this identity into our Bernstein representation (65b) for ′ h , and then summing over k yields equation (71b). C.2 Relation with the DHW τ-leaping masking sampler In this section, we formalize the exact relationship between Algorithm 1 of Dmitriev et al. [17] and the Bernoulli unmasking sampler (11). Any DHW grid of the form 0=u0<⋯<uN=U0=u_0<·s<u_N=U can be used to define a sequence of reveal times tj≔e−(U−uj)t_j e^-(U-u_j), and the corresponding inverse transformation U−uj=log(1/tj)U-u_j= (1/t_j). In terms of the shorthand βk≔(tk+1−tk)/(1−tk) _k (t_k+1-t_k)/(1-t_k), for the Bernoulli unmasking update with estimated denoiser μ^i(⋅,x) μ_i( ·,x), the corresponding transition kernel is given by k,iBer(⋆∣x)=1−βk,andk,iBer(a∣x)=βkμ^i(a,x)for each a∈. _k,i Ber( x)=1- _k, and _k,i Ber(a x)= _k μ_i(a,x) for each $a $. (72a) On the other hand, for a current state x and masked coordinate i∈ℳ(x)i (x), write the DHW estimated score as qk,i(a,x)≔^log(1/tk)(xi→a,x)q_k,i DHW(a,x) s_ (1/t_k)(x^i→ a,x). Assuming its total mass is positive, define its normalized shape and relative mass by πk,i(a,x)≔qk,i(a,x)∑b∈qk,i(b,x),andck,i(x)≔1−tktk∑b∈qk,i(b,x). _k,i(a,x) q_k,i DHW(a,x) _b q_k,i DHW(b,x), and c_k,i(x) 1-t_kt_k _b q_k,i DHW(b,x). (72b) These ingredients along with the DHW stepsize yield the kernel k,i(⋆∣x)=(1−βk)ck,i(x),andk,i(a∣x)=1−(1−βk)ck,i(x)πk,i(a,x). _k,i DHW( x)=(1- _k)^c_k,i(x), and _k,i DHW(a x)= \1-(1- _k)^c_k,i(x) \ _k,i(a,x). (72c) Taking the differences between the expressions (72a) and (72c), we obtain the kernel differences k,i(⋆∣x)−k,iBer(⋆∣x) _k,i DHW( x)-K_k,i Ber( x) =(1−βk)ck,i(x)−(1−βk), =(1- _k)^c_k,i(x)-(1- _k), (72d) k,i(a∣x)−k,iBer(a∣x) _k,i DHW(a x)-K_k,i Ber(a x) =1−(1−βk)ck,i(x)πk,i(a,x)−βkμ^i(a,x). = \1-(1- _k)^c_k,i(x) \ _k,i(a,x)- _k μ_i(a,x). (72e) Thus, the two kernels are very closely related, but not identical in general. We claim that when there is no score error, so that qk,i=qk,i⋆q_k,i DHW=q_k,i and μ^i=μi μ_i= _i, then the two kernels coincide. First of all, we claim that Proposition 6 of Dmitriev et al. [17], when translated into our notation, shows that qk,i⋆(a,x) q_k,i (a,x) =(i)tk1−tkμi(a,x),and∑a∈qk,i⋆(a,x)=(ii)tk1−tk. (i)= t_k1-t_k _i(a,x), and _a q_k,i (a,x) (i)= t_k1-t_k. (72f) Equation (i) follows from equation (i), since the denoiser μi _i is a conditional probability distribution. To establish equation (i), if x has coordinate i masked and y is obtained by filling that coordinate with a, then the marginal convention in Proposition 6 gives q0(y)/q0(x)=ℙ(Zi=a∣x)=μi(a,x)q_0(y)/q_0(x)=P(Z_i=a x)= _i(a,x). Moreover, their CTMC time u is related to our reveal probability by the transformation tk=e−ut_k=e^-u, so that (eu−1)−1=tk/(1−tk)(e^u-1)^-1=t_k/(1-t_k). Using equation (72f) we see that the exact score has total mass tk/(1−tk)t_k/(1-t_k), so that ck,i(x)=1c_k,i(x)=1 in equation (72b). Moreover, normalizing qk,i⋆(a,x)q_k,i (a,x) by this total mass cancels the common factor tk/(1−tk)t_k/(1-t_k), so that πk,i(a,x)=μi(a,x) _k,i(a,x)= _i(a,x). Thus, the right-hand side of equation (72d) is (1−βk)−(1−βk)=0(1- _k)-(1- _k)=0, while the right-hand side of equation (72e) is βkμi(a,x)−βkμi(a,x)=0 _k _i(a,x)- _k _i(a,x)=0. For learned scores, the mask-probability gap is caused by the non-unit score mass ck,i(x)c_k,i(x). The important difference is that rescaling the DHW score changes its kernel, whereas the Bernoulli reveal probability remains fixed by the grid. Appendix D Proof of Lemma 2: XORSAT scaling Let us first complete the proof, taking the bounds (44) as given. Note that the outer blocks have log-reveal-odds length (logd)O( d), whereas Len(ℐtrans)=(logd/d)Len(I_ 0.0pt 813770196608 0.0pt$ $ 0.0pt 813770196608 0.0pt$ $ 0.0pt 712989196608 0.0pt$ $ 0.0pt 712991196608 0.0pt$ $)=O( d/d). Hence, we can compute UGC() C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$(P) =(Len(ℐpre)(ℐpre)+Len(ℐtrans)(ℐtrans)+Len(ℐpost)(ℐpost))2 = ( Len(I_ -1.35483pt 723920196608 1.3611pt$ $ -1.35483pt 723920196608 1.3611pt$ $ -1.35483pt 635492196608 0.95277pt$ $ -1.35481pt 635488196608 0.68054pt$ $) H(I_ -1.35483pt 723920196608 1.3611pt$ $ -1.35483pt 723920196608 1.3611pt$ $ -1.35483pt 635492196608 0.95277pt$ $ -1.35481pt 635488196608 0.68054pt$ $)+ Len(I_ 0.0pt 813770196608 0.0pt$ $ 0.0pt 813770196608 0.0pt$ $ 0.0pt 712989196608 0.0pt$ $ 0.0pt 712991196608 0.0pt$ $) H(I_ 0.0pt 813770196608 0.0pt$ $ 0.0pt 813770196608 0.0pt$ $ 0.0pt 712989196608 0.0pt$ $ 0.0pt 712991196608 0.0pt$ $)+ Len(I_ -0.94836pt 680901196608 1.3611pt$ $ -0.94836pt 680901196608 1.3611pt$ $ -0.94838pt 595042196608 0.95277pt$ $ -0.94836pt 595406196608 0.68054pt$ $) H(I_ -0.94836pt 680901196608 1.3611pt$ $ -0.94836pt 680901196608 1.3611pt$ $ -0.94838pt 595042196608 0.95277pt$ $ -0.94836pt 595406196608 0.68054pt$ $) )^2 =([logd10+(logd)1/4d]2) =O ( [ dd^10+ ( dd )^1/4 d ]^2 ) =(dlogd), =O ( d d ), where we have used the claimed bound (44). Combining this bound with the scaling UGC([ℐfull])=Θ(dlogd) C_ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752357262143 0.0pt$ UGC$ 0.0pt 752355262144 0.0pt$ UGC$ 0.0pt 752358262144 0.0pt$ UGC$([I_ 0.0pt 616043262143 0.0pt$ $ 0.0pt 616043262143 0.0pt$ $ 0.0pt 534775262144 0.0pt$ $ 0.0pt 534774262144 0.0pt$ $])= (d d) establishes the claim (43). We now return to prove the bounds (44). With the shorthand ℐtrans=[sleft,sright]I_ 0.0pt 813770196608 0.0pt$ $ 0.0pt 813770196608 0.0pt$ $ 0.0pt 712989196608 0.0pt$ $ 0.0pt 712991196608 0.0pt$ $=[s_ 0.0pt 462032196608 0.0pt$ $ 0.0pt 462032196608 0.0pt$ $ 0.0pt 401081196608 0.0pt$ $ 0.0pt 401082196608 0.0pt$ $,s_ -0.83998pt 675493196608 1.3611pt$ $ -0.83998pt 675493196608 1.3611pt$ $ -0.84pt 592056196608 0.95277pt$ $ -0.83998pt 591735196608 0.68054pt$ $] and c′=minsleft(1−sleft),sright(1−sright)c = \s_ 0.0pt 462032196608 0.0pt$ $ 0.0pt 462032196608 0.0pt$ $ 0.0pt 401081196608 0.0pt$ $ 0.0pt 401082196608 0.0pt$ $(1-s_ 0.0pt 462032196608 0.0pt$ $ 0.0pt 462032196608 0.0pt$ $ 0.0pt 401081196608 0.0pt$ $ 0.0pt 401082196608 0.0pt$ $),s_ -0.83998pt 675493196608 1.3611pt$ $ -0.83998pt 675493196608 1.3611pt$ $ -0.84pt 592056196608 0.95277pt$ $ -0.83998pt 591735196608 0.68054pt$ $(1-s_ -0.83998pt 675493196608 1.3611pt$ $ -0.83998pt 675493196608 1.3611pt$ $ -0.84pt 592056196608 0.95277pt$ $ -0.83998pt 591735196608 0.68054pt$ $)\, it follows from the definition (2c) of H that c′(sright)−(sleft)≤(ℐtrans)≤(1)−(0)4,as well as c \ h(s_ -0.83998pt 675493196608 1.3611pt$ $ -0.83998pt 675493196608 1.3611pt$ $ -0.84pt 592056196608 0.95277pt$ $ -0.83998pt 591735196608 0.68054pt$ $)- h(s_ 0.0pt 462032196608 0.0pt$ $ 0.0pt 462032196608 0.0pt$ $ 0.0pt 401081196608 0.0pt$ $ 0.0pt 401082196608 0.0pt$ $)\≤ H(I_ 0.0pt 813770196608 0.0pt$ $ 0.0pt 813770196608 0.0pt$ $ 0.0pt 712989196608 0.0pt$ $ 0.0pt 712991196608 0.0pt$ $)≤ h(1)- h(0)4, as well as (73a) (ℐpre)≤(sleft)−(0)4and(ℐpost)≤(1)−(sright)4. H(I_ -1.35483pt 723920196608 1.3611pt$ $ -1.35483pt 723920196608 1.3611pt$ $ -1.35483pt 635492196608 0.95277pt$ $ -1.35481pt 635488196608 0.68054pt$ $)≤ h(s_ 0.0pt 462032196608 0.0pt$ $ 0.0pt 462032196608 0.0pt$ $ 0.0pt 401081196608 0.0pt$ $ 0.0pt 401082196608 0.0pt$ $)- h(0)4 and H(I_ -0.94836pt 680901196608 1.3611pt$ $ -0.94836pt 680901196608 1.3611pt$ $ -0.94838pt 595042196608 0.95277pt$ $ -0.94836pt 595406196608 0.68054pt$ $)≤ h(1)- h(s_ -0.83998pt 675493196608 1.3611pt$ $ -0.83998pt 675493196608 1.3611pt$ $ -0.84pt 592056196608 0.95277pt$ $ -0.83998pt 591735196608 0.68054pt$ $)4. (73b) Consequently, we can control the UGC increments by controlling the differences in h. From the definition (1)=∑i=1dInfo(Zi;Z−i) h(1)= _i=1^dInfo(Z_i;Z_-i) and the binary nature of each ZiZ_i, it follows that (1)≤dlog2 h(1)≤ d 2, and hence that (1)−(0)=(d) h(1)- h(0)=O(d). For controlling the other increments, we study averages of h over the random choice of ∈0,1d×kA∈\0,1\^d× k. The increments of the averaged h take a simple form. For a positive integer m≤km≤ k, let m∈0,1m×kB_m∈\0,1\^m× k be a Boolean random matrix with m independent uniform rows in 0,1k\0,1\^k, and let b be a fresh independent uniform row. Defining the function (m) g(m) ≔ℙb∉rowspan(m) \b (B_m)\ (74a) we claim that [(s)−(t)]dlog2 E_A[ h(s)- h(t)]d\, 2 =[(Mt)−(Ms)],where Mr∼Bin(d−1,r) is a binomial RV, =E [ g(M_t)- g(M_s) ], where $M_r (d-1,r)$ is a binomial RV, (74b) and also [(Msleft)]=1−O(d−11)and[(Msright)]=O(d−11). [ g(M_s_ 0.0pt 564272196608 0.0pt$ $ 0.0pt 564272196608 0.0pt$ $ 0.0pt 401082196608 0.0pt$ $ 0.0pt 401080196608 0.0pt$ $)]=1-O(d^-11) and [ g(M_s_ -0.83998pt 815935196608 0.97221pt$ $ -0.83998pt 815935196608 0.97221pt$ $ -0.83998pt 591735196608 0.68054pt$ $ -0.83998pt 592184196608 0.4861pt$ $)]=O(d^-11). (74c) Taking these two claims as given for the moment, let us complete the proof of the bounds (44). Transition interval: Equation (74c) gives [(Msleft)−(Msright)]=1−O(d−11)=Θ(1)E [ g(M_s_ 0.0pt 564272196608 0.0pt$ $ 0.0pt 564272196608 0.0pt$ $ 0.0pt 401082196608 0.0pt$ $ 0.0pt 401080196608 0.0pt$ $)- g(M_s_ -0.83998pt 815935196608 0.97221pt$ $ -0.83998pt 815935196608 0.97221pt$ $ -0.83998pt 591735196608 0.68054pt$ $ -0.83998pt 592184196608 0.4861pt$ $) ]=1-O(d^-11)= (1). Consequently, equation (74b) gives [(sright)−(sleft)]=Θ(d)E_A[ h(s_ -0.83998pt 675493196608 1.3611pt$ $ -0.83998pt 675493196608 1.3611pt$ $ -0.84pt 592056196608 0.95277pt$ $ -0.83998pt 591735196608 0.68054pt$ $)- h(s_ 0.0pt 462032196608 0.0pt$ $ 0.0pt 462032196608 0.0pt$ $ 0.0pt 401081196608 0.0pt$ $ 0.0pt 401082196608 0.0pt$ $)]= (d), and combining with inequality (73a), this yields [(ℐtrans)]=Θ(d)E[ H(I_ 0.0pt 813770196608 0.0pt$ $ 0.0pt 813770196608 0.0pt$ $ 0.0pt 712989196608 0.0pt$ $ 0.0pt 712991196608 0.0pt$ $)]= (d). Pre- and post-transition intervals: For the pre-transition interval, M0=0M_0=0 deterministically, so that equation (74b) gives [(sleft)]−[(0)]=d(log2)(0)−[(Msleft)]E_A[ h(s_ 0.0pt 462032196608 0.0pt$ $ 0.0pt 462032196608 0.0pt$ $ 0.0pt 401081196608 0.0pt$ $ 0.0pt 401082196608 0.0pt$ $)]-E_A[ h(0)]=d( 2) \ g(0)-E[ g(M_s_ 0.0pt 564272196608 0.0pt$ $ 0.0pt 564272196608 0.0pt$ $ 0.0pt 401082196608 0.0pt$ $ 0.0pt 401080196608 0.0pt$ $)] \. Since g is non-increasing and 0≤10≤ g≤ 1, it follows that 0 0 ≤(0)−[(Msleft)]≤ 1−[(Msleft)]=O(d−11), ≤ g(0)-E[ g(M_s_ 0.0pt 564272196608 0.0pt$ $ 0.0pt 564272196608 0.0pt$ $ 0.0pt 401082196608 0.0pt$ $ 0.0pt 401080196608 0.0pt$ $)]\;≤\;1-E[ g(M_s_ 0.0pt 564272196608 0.0pt$ $ 0.0pt 564272196608 0.0pt$ $ 0.0pt 401082196608 0.0pt$ $ 0.0pt 401080196608 0.0pt$ $)]=O(d^-11), and hence [(sleft)]−[(0)]=O(d−10)E_A[ h(s_ 0.0pt 462032196608 0.0pt$ $ 0.0pt 462032196608 0.0pt$ $ 0.0pt 401081196608 0.0pt$ $ 0.0pt 401082196608 0.0pt$ $)]-E_A[ h(0)]=O(d^-10). Similarly, we have M1=d−1M_1=d-1 deterministically, and equation (74b) gives [(1)]−[(sright)]=d(log2)[(Msright)]−(d−1)E_A[ h(1)]-E_A[ h(s_ -0.83998pt 675493196608 1.3611pt$ $ -0.83998pt 675493196608 1.3611pt$ $ -0.84pt 592056196608 0.95277pt$ $ -0.83998pt 591735196608 0.68054pt$ $)]=d( 2) \E[ g(M_s_ -0.83998pt 815935196608 0.97221pt$ $ -0.83998pt 815935196608 0.97221pt$ $ -0.83998pt 591735196608 0.68054pt$ $ -0.83998pt 592184196608 0.4861pt$ $)]- g(d-1) \. Using monotonicity and non-negativity, 0 0 ≤[(Msright)]−(d−1)≤[(Msright)]=O(d−11), [ g(M_s_ -0.83998pt 815935196608 0.97221pt$ $ -0.83998pt 815935196608 0.97221pt$ $ -0.83998pt 591735196608 0.68054pt$ $ -0.83998pt 592184196608 0.4861pt$ $)]- g(d-1)\;≤\;E[ g(M_s_ -0.83998pt 815935196608 0.97221pt$ $ -0.83998pt 815935196608 0.97221pt$ $ -0.83998pt 591735196608 0.68054pt$ $ -0.83998pt 592184196608 0.4861pt$ $)]=O(d^-11), and hence [(1)]−[(sright)]=O(d−10)E_A[ h(1)]-E_A[ h(s_ -0.83998pt 675493196608 1.3611pt$ $ -0.83998pt 675493196608 1.3611pt$ $ -0.84pt 592056196608 0.95277pt$ $ -0.83998pt 591735196608 0.68054pt$ $)]=O(d^-10). Combining these two estimates with inequalities (73b), we conclude that [(ℐpre)]=(d−10)E[ H(I_ -1.35483pt 723920196608 1.3611pt$ $ -1.35483pt 723920196608 1.3611pt$ $ -1.35483pt 635492196608 0.95277pt$ $ -1.35481pt 635488196608 0.68054pt$ $)]=O(d^-10) and [(ℐpost)]=(d−10)E[ H(I_ -0.94836pt 680901196608 1.3611pt$ $ -0.94836pt 680901196608 1.3611pt$ $ -0.94838pt 595042196608 0.95277pt$ $ -0.94836pt 595406196608 0.68054pt$ $)]=O(d^-10). To pass from these averaged bounds to a single realization of A, first note that the two outer H terms are nonnegative. Hence, by Markov’s inequality and the preceding expectation bounds, with probability bounded below by a positive constant, both (ℐpre) H(I_ -1.35483pt 723920196608 1.3611pt$ $ -1.35483pt 723920196608 1.3611pt$ $ -1.35483pt 635492196608 0.95277pt$ $ -1.35481pt 635488196608 0.68054pt$ $) and (ℐpost) H(I_ -0.94836pt 680901196608 1.3611pt$ $ -0.94836pt 680901196608 1.3611pt$ $ -0.94838pt 595042196608 0.95277pt$ $ -0.94836pt 595406196608 0.68054pt$ $) are (d−10)O(d^-10). For the middle interval, the endpoint estimates (74c) and identity (74b) give [(sright)−(sleft)]=d(log2)1−O(d−11)E_A [ h(s_ -0.83998pt 675493196608 1.3611pt$ $ -0.83998pt 675493196608 1.3611pt$ $ -0.84pt 592056196608 0.95277pt$ $ -0.83998pt 591735196608 0.68054pt$ $)- h(s_ 0.0pt 462032196608 0.0pt$ $ 0.0pt 462032196608 0.0pt$ $ 0.0pt 401081196608 0.0pt$ $ 0.0pt 401082196608 0.0pt$ $) ]=d( 2) \1-O(d^-11) \. Since 0≤(sright)−(sleft)≤dlog20≤ h(s_ -0.83998pt 675493196608 1.3611pt$ $ -0.83998pt 675493196608 1.3611pt$ $ -0.84pt 592056196608 0.95277pt$ $ -0.83998pt 591735196608 0.68054pt$ $)- h(s_ 0.0pt 462032196608 0.0pt$ $ 0.0pt 462032196608 0.0pt$ $ 0.0pt 401081196608 0.0pt$ $ 0.0pt 401082196608 0.0pt$ $)≤ d 2, Markov’s inequality applied to the nonnegative deficit dlog2−(sright)−(sleft)d 2-\ h(s_ -0.83998pt 675493196608 1.3611pt$ $ -0.83998pt 675493196608 1.3611pt$ $ -0.84pt 592056196608 0.95277pt$ $ -0.83998pt 591735196608 0.68054pt$ $)- h(s_ 0.0pt 462032196608 0.0pt$ $ 0.0pt 462032196608 0.0pt$ $ 0.0pt 401081196608 0.0pt$ $ 0.0pt 401082196608 0.0pt$ $)\ shows that ℙ(sright)−(sleft)<dlog22 _A \ h(s_ -0.83998pt 675493196608 1.3611pt$ $ -0.83998pt 675493196608 1.3611pt$ $ -0.84pt 592056196608 0.95277pt$ $ -0.83998pt 591735196608 0.68054pt$ $)- h(s_ 0.0pt 462032196608 0.0pt$ $ 0.0pt 462032196608 0.0pt$ $ 0.0pt 401081196608 0.0pt$ $ 0.0pt 401082196608 0.0pt$ $)< d 22 \ =O(d−11). =O(d^-11). Thus, by a union bound, for all sufficiently large d there exists a realization of A for which the two outer bounds hold and (sright)−(sleft)=Ω(d) h(s_ -0.83998pt 675493196608 1.3611pt$ $ -0.83998pt 675493196608 1.3611pt$ $ -0.84pt 592056196608 0.95277pt$ $ -0.83998pt 591735196608 0.68054pt$ $)- h(s_ 0.0pt 462032196608 0.0pt$ $ 0.0pt 462032196608 0.0pt$ $ 0.0pt 401081196608 0.0pt$ $ 0.0pt 401082196608 0.0pt$ $)= (d) simultaneously. Inequality (73a) then gives (ℐtrans)=Θ(d) H(I_ 0.0pt 813770196608 0.0pt$ $ 0.0pt 813770196608 0.0pt$ $ 0.0pt 712989196608 0.0pt$ $ 0.0pt 712991196608 0.0pt$ $)= (d) for this same realization. Proof of the identity (74b): Fix a coordinate i, and condition on coordinate i being masked at reveal probability r. Let R⊆[d]∖iR [d] \i\ denote the set of revealed coordinates among the remaining coordinates. Then |R|=Mr∼Bin(d−1,r)|R|=M_r (d-1,r). Coordinate i is associated with the ithi^th row aia_i of A, and we use RA_R to denote the matrix formed by the rows indexed by R. All of the following linear-algebraic statements are over the Boolean field 2F_2. Conditional on A and the revealed values ZRZ_R, there are two possibilities. If ai∈rowspan(R)a_i (A_R), then ZiZ_i is a linear combination of the revealed coordinates ZRZ_R, and hence is determined by them. On the other hand, if ai∉rowspan(R)a_i (A_R), then the linear functional defined by aia_i is nonzero on the nullspace of RA_R. Consequently, among the latent assignments compatible with ZRZ_R, exactly half give Zi=0Z_i=0 and half give Zi=1Z_i=1. By this reasoning, the conditional entropy takes the simple form Ent(Zi∣ZR,) (Z_i Z_R,A) =(log2) 1ai∉rowspan(R). =( 2)\,1 \a_i (A_R) \. (75) Now condition on the event |R|=m|R|=m. By independence and permutation invariance of the rows, the submatrix RA_R has the same law as mB_m, while aia_i is a fresh independent uniform row. From the definition (74a) of g, it follows that [Ent(Zi∣ZR,)||R|=m]=(log2)(m)E_A [Ent(Z_i Z_R,A)\, |\,|R|=m ]=( 2) g(m). Averaging this identity over the binomial random variable yields [Ent(Zi∣ZR,)]=(log2)[(Mr)]E_A [Ent(Z_i Z_R,A) ]=( 2)E [ g(M_r) ]. The same argument with no revealed coordinates gives [Ent(Zi∣)]=(log2)(0)E_A [Ent(Z_i ) ]=( 2) g(0). Combining the pieces, the ithi^th term in the sum (2a) that defines h has expectation [Ent(Zi∣)−Ent(Zi∣ZR,)]=(log2)(0)−[(Mr)]. _A [Ent(Z_i )-Ent(Z_i Z_R,A) ]=( 2) \ g(0)-E[ g(M_r)] \. Summing over the d exchangeable coordinates yields the identity [(r)]=d(log2)(0)−[(Mr)]E_A[ h(r)]=d( 2) \ g(0)-E[ g(M_r)] \. Taking the difference between r=sr=s and r=tr=t in this identity yields the claim (74b). Proof of equation (74c): We first claim that g satisfies the bounds 1−(m)≤(a)2m−kfor m≤k, and(m)≤(b)2k−mfor m>k. 1- g(m)\; (a)≤2^m-k for $m≤ k$, $ $ and g(m) (b)≤2^k-m for $m>k$. (76) To prove the first bound (76)(a), we observe that conditional on mB_m, its row span contains 2rank(m)2^rank(B_m) vectors out of the 2k2^k possible rows in 0,1k\0,1\^k. Hence a fresh uniform row lies in this span with probability at most 2rank(m)−k≤2m−k2^rank(B_m)-k≤ 2^m-k. Combining with the definition of g yields the claim. As for the bound (76)(b), when m>km>k, the event that the fresh row lies outside the row span requires rank(m)<krank(B_m)<k. Union-bounding over nonzero right-null vectors therefore gives (m)≤ℙ[rank(m)<k]≤(2k−1)2−m<2k−m g(m) [rank(B_m)<k ]≤(2^k-1)2^-m<2^k-m, as claimed. We now show that [(Msleft)]=1−(d−11)E[ g(M_s_ 0.0pt 564272196608 0.0pt$ $ 0.0pt 564272196608 0.0pt$ $ 0.0pt 401082196608 0.0pt$ $ 0.0pt 401080196608 0.0pt$ $)]=1-O(d^-11). Recalling that Msleft∼Bin(d−1,sleft)M_s_ 0.0pt 564272196608 0.0pt$ $ 0.0pt 564272196608 0.0pt$ $ 0.0pt 401082196608 0.0pt$ $ 0.0pt 401080196608 0.0pt$ $ (d-1,s_ 0.0pt 462032196608 0.0pt$ $ 0.0pt 462032196608 0.0pt$ $ 0.0pt 401081196608 0.0pt$ $ 0.0pt 401082196608 0.0pt$ $), its mean is μ−≔[Msleft] _- [M_s_ 0.0pt 564272196608 0.0pt$ $ 0.0pt 564272196608 0.0pt$ $ 0.0pt 401082196608 0.0pt$ $ 0.0pt 401080196608 0.0pt$ $] =(d−1)sleft=k−kd−c1dlogd+c1logd. =(d-1)s_ 0.0pt 462032196608 0.0pt$ $ 0.0pt 462032196608 0.0pt$ $ 0.0pt 401081196608 0.0pt$ $ 0.0pt 401082196608 0.0pt$ $=k- kd-c_1 d d+c_1 dd. For the threshold T−≔k−(c1/4)dlogdT_- k-(c_1/4) d d, we therefore have T−μ− T_-- _- =3c14dlogd+kd−c1logd≥c12dlogd = 3c_14 d d+ kd-c_1 dd≥ c_12 d d for all sufficiently large d. Defining the bad event ℰ=Msleft>T−E=\M_s_ 0.0pt 564272196608 0.0pt$ $ 0.0pt 564272196608 0.0pt$ $ 0.0pt 401082196608 0.0pt$ $ 0.0pt 401080196608 0.0pt$ $>T_-\, Hoeffding’s inequality gives ℙ(ℰ)≤exp−2(T−μ−)2d−1≤d−c12/2, (E)≤ \- 2(T_-- _-)^2d-1 \≤ d^-c_1^2/2, so that ℙ(ℰ)=(d−11)P(E)=O(d^-11) for c1c_1 sufficiently large. On the complement ℰcE^c, the bound (76)(a) guarantees that 1−(Msleft)≤2Msleft−k≤2−(c1/4)dlogd1- g(M_s_ 0.0pt 564272196608 0.0pt$ $ 0.0pt 564272196608 0.0pt$ $ 0.0pt 401082196608 0.0pt$ $ 0.0pt 401080196608 0.0pt$ $)≤ 2^M_s_ 0.0pt 564272196608 0.0pt$ $ 0.0pt 564272196608 0.0pt$ $ 0.0pt 401082196608 0.0pt$ $ 0.0pt 401080196608 0.0pt$ $-k≤ 2^-(c_1/4) d d. Since 0≤(m)≤10≤ g(m)≤ 1, it follows that 1−[(Msleft)] 1-E[ g(M_s_ 0.0pt 564272196608 0.0pt$ $ 0.0pt 564272196608 0.0pt$ $ 0.0pt 401082196608 0.0pt$ $ 0.0pt 401080196608 0.0pt$ $)] ≤ℙ(ℰ)+2−(c1/4)dlogd=(d−11), (E)+2^-(c_1/4) d d=O(d^-11), which proves the claim. A similar argument applies at the right endpoint srights_ -0.83998pt 675493196608 1.3611pt$ $ -0.83998pt 675493196608 1.3611pt$ $ -0.84pt 592056196608 0.95277pt$ $ -0.83998pt 591735196608 0.68054pt$ $. The same Hoeffding bound guarantees that ℙ[Msright<k+(c1/4)dlogd]=O(d−11)P [M_s_ -0.83998pt 815935196608 0.97221pt$ $ -0.83998pt 815935196608 0.97221pt$ $ -0.83998pt 591735196608 0.68054pt$ $ -0.83998pt 592184196608 0.4861pt$ $<k+(c_1/4) d d ]=O(d^-11), while on the complementary event, we have the bound (Msright)≤2k−Msright≤2−(c1/4)dlogd. g(M_s_ -0.83998pt 815935196608 0.97221pt$ $ -0.83998pt 815935196608 0.97221pt$ $ -0.83998pt 591735196608 0.68054pt$ $ -0.83998pt 592184196608 0.4861pt$ $)≤ 2^k-M_s_ -0.83998pt 815935196608 0.97221pt$ $ -0.83998pt 815935196608 0.97221pt$ $ -0.83998pt 591735196608 0.68054pt$ $ -0.83998pt 592184196608 0.4861pt$ $≤ 2^-(c_1/4) d d. Taking expectations gives [(Msright)]=O(d−11)E[ g(M_s_ -0.83998pt 815935196608 0.97221pt$ $ -0.83998pt 815935196608 0.97221pt$ $ -0.83998pt 591735196608 0.68054pt$ $ -0.83998pt 592184196608 0.4861pt$ $)]=O(d^-11). Combining the two pieces completes the proof of the claimed bounds (74c).