CS Paper Radar

On Deterministically Computing Total Variation Distance via Zonotope Compression

Yucheng Fu

cs.DS math.PR ·submitted 2026-09-21 07:58 UTC · v1

Abstract

We study deterministic relative approximation of the total variation distance between high-dimensional distributions given by succinct descriptions. We develop an abstract deterministic approximation framework based on representing the total variation distance as a support function of a low-dimensional zonotope. As applications, we obtain FPTASs for several models. Given two mixtures of product distributions over $[q]^n$ with a total of $K$ component distributions, our algorithm approximates their TV-distance within a factor of $1+\varepsilon$ in time $\widetilde O_K(nq(n/\varepsilon)^{2K})$. We also give an FPTAS for mixtures of $n$-step Markov chains over $[q]^n$ with a total of $K$ component distributions, with running time $\widetilde O_K(nq^2(n/\varepsilon)^{2K})$. Finally, for two latent-tree Ising models with the same underlying tree topology, we give an FPTAS for the TV-distance between their leaf marginals in time $O(|V|^{13}\varepsilon^{-12})$.

Closest papers

Nearest neighbours by meaning across the whole index.

Transformer-Based Masked Diffusion Models Provably Learn Distributions with Latent Structure

cs.LG cs.ITmath.STstat.ML ·2026-10-08 ·Jingda Wu, Changxiao Cai
similarity 0.59
Abstract

Masked diffusion models (MDMs) generate discrete data by iteratively unmasking multiple tokens in parallel using a learned mask predictor. Their output carries two errors: parallelization error due to parallel sampling, and estimation error from the mask predictor learned with finite samples. Existing theory treats these errors separately, and the available statistical bounds typically scale with the number $V^L$ of length-$L$ sequences over a vocabulary of size $V$, suffering from the curse of dimensionality. In this work, we establish end-to-end statistical guarantees showing that transformer-based MDMs learn structured distributions with a sample complexity governed by their latent structure. Specifically, we model this structure through mixtures of hidden Markov trees, which capture latent dependencies within components and heterogeneity across components. When the data distribution is well approximated by such a mixture, a transformer-based MDM with parallel unmasking schedules achieves $\varepsilon$-accurate sampling in KL divergence with $\widetilde{O}(LK_{\mathrm{par}}/\varepsilon)$ training samples, where $K_{\mathrm{par}}$ is polynomial in $L$, $V$, the number of hidden states, and the number of mixture components. The transformer network and sampling procedure require no knowledge of the tree topologies or component parameters, thereby adapting to the unknown latent structure automatically. Overall, our results provide theoretical justification for the empirical effectiveness of MDMs on real-world data.

0.42

Polylogarithmic Sparsity of Randomly Reweighted NPMLEs for Gaussian Mixtures

cs.LG stat.MEmath.ST ·2026-10-01 ·Hansheng Jiang
similarity 0.59
Abstract

The nonparametric maximum likelihood estimator (NPMLE) of a Gaussian location mixture maximizes the likelihood over the infinite-dimensional space of mixing distributions. The maximizing mixing distribution can be nonunique, and the classical bound on its number of atoms grows linearly with the sample size $n$. We show that a vanishingly small random perturbation of the likelihood yields exact polylogarithmic sparsity. The resulting randomly reweighted NPMLE maximizes a weighted likelihood whose independent weights, taken to be Gamma in our analysis, concentrate around one as $n$ grows. With high probability, it is unique, has $O\{(\log n/\log\log n)^d+\log n\}$ atoms in dimension $d$, nearly maximizes the ordinary likelihood, and estimates the mixture density at a Hellinger rate that is parametric up to logarithmic factors. This sparsity holds for the estimator itself, not for an approximation of it, and requires no support penalty. The proof rests on an effective-dimension principle for positive kernel mixtures: low-dimensional variation of the fitted values controls the support of every extreme point of the set of maximizers. Numerical illustrations verify that the reweighted NPMLE has Hellinger risk and support size comparable to those of the ordinary NPMLE.

0.47

Spectral partitioning for $k$-block averaging kernels of finite Markov chains

cs.IT stat.MLcs.LGmath.OC+2 ·2026-08-21 ·Michael C. H. Choi, Youjia Wang
similarity 0.57
Abstract · 43 pages, 8 figures

We develop spectral algorithms for selecting state-space partitions that define averaging kernels for finite, ergodic and reversible Markov chains. For a partition $\mathcal O$, the Gibbs kernel $G_{\mathcal O}$ resamples within the current block from the stationary conditional distribution; when this update is tractable, composing or mixing it with a baseline kernel $P$ can accelerate convergence. We select $\mathcal O$ by rounding the bottom nonconstant eigenfunctions of $P^2$, or the algebraically smallest eigenfunctions of $P$ for additive mixtures, using weighted $k$-means. For $F(\mathcal O)=\|G_{\mathcal O}P-Π\|_{F,π}^2$, we derive exact trace and normalized-cut representations and show that $F$ equals the Pearson $χ^2$-mutual information between the initial block label and the state after one transition, giving this matrix objective a natural probabilistic interpretation. In the two-block case, a threshold sweep exactly solves the associated one-dimensional weighted two-means rounding problem. For general $k \geq 2$, weighted $k$-means rounds the bottom $(k-1)$-dimensional embedding, after which candidates are rescored by $F$; the rounding distortion is a distance between subspaces that yields spectral approximation bounds. We extend the framework to additive mixtures, finite-horizon objectives, and discounted infinite-horizon objectives. In contrast to classical normalized spectral clustering, which uses top nonconstant modes to find low-flow persistent clusters, our method uses bottom modes to favor large normalized cross-block flow and rapid loss of block-label information. Experiments on a controlled-spectrum graph, a mean-field Ising model, and Bayesian variable selection show notable per-iteration improvements in convergence and statistical estimation.

0.45

Uniform Discrete Diffusion Models are Minimax Optimal for Estimating Distributions with Small Effective Support Size

cs.LG stat.ML ·2026-10-06 ·Dongsun Yoon, Saptarshi Chakraborty
similarity 0.57
Abstract

Discrete diffusion models have emerged as a practically successful framework for generative modeling on discrete product spaces, yet their statistical generalization properties remain poorly understood. Discrete real-world data such as text or biological sequences often concentrate on a small fraction of the astronomically large ambient space because of semantic or physical constraints, but existing bounds fail to capture this distributional structure and instead scale with the size of the ambient space, giving rise to almost vacuous error bounds. We address this gap for uniform discrete diffusion, one of the two dominant discrete diffusion paradigms alongside masking diffusion, by deriving statistical guarantees governed by the effective support size $s_n(P_0)$, a sample-size-dependent measure of distributional complexity. Given $n$ independent and identically distributed (i.i.d.) samples from an unknown data distribution $P_0$ on $[K]^d$, we show that, with appropriate choices of network size and hyperparameters, the expected total variation (TV) loss scales as $O(\sqrt{s_n(P_0)/n})$, while the expected Kullback--Leibler (KL) divergence is bounded by $O(\frac{1}{n}s_n(P_0)\log(eK^d/s_n(P_0))\log n)$. Furthermore, we show that the TV rate is minimax optimal and that the KL rate is minimax optimal up to a factor of $\log n$. Together, these upper and lower bounds show that uniform discrete diffusion successfully avoids the curse of dimensionality for distributions with small effective support size: the TV error rate depends on the ambient state-space size only through $s_n(P_0)$, while the corresponding KL rate incurs only an additional logarithmic dependence on the ambient state-space size.

0.28

Low-degree polynomials lower bounds for clustering in small dimension

cs.LG stat.ML ·2026-10-27 ·Alexandra Carpentier, Nicolas Verzelen
theory similarity 0.57
Abstract

We study the computational limits of clustering $n$ observations drawn from a mixture of $K$ isotropic distributions in $\mathbb R^d$, in the regime where the number $K$ of groups is much larger than the dimension $d$. In this regime, tensor-based procedures recover the partition with a polylogarithmic separation between the centers, but they require a sample size that is a large and non-explicit polynomial of $dK$, whereas the existing low-degree lower bounds only show that $n$ must be larger than $dK^2$. We introduce a mixture of $2K$ product Bernoulli distributions on $\{0,1\}^d$, with $K=(d+1)^m$, whose centers are built from a dual BCH code. This construction ensures that the moment tensors of the observations coincide with those of the uniform distribution on $\{-1,1\}^d$ up to the order $2m+1$. For any fixed $m$, we establish a low-degree polynomial lower bound showing that clustering is hard as long as the separation $Δ$ satisfies $Δ^2\ll(K^2d^{3/2}/n)^{1/(2m+2)}\wedge\sqrt d$, up to polylogarithmic factors. In particular, with a polylogarithmic separation, low-degree polynomials require $n\gtrsim K^2d^{3/2}$ observations, up to polylogarithmic factors. Through a Gaussianization argument, this hardness carries over, in the sense of reductions, to isotropic Gaussian mixtures. Our proof relies on a family of polynomials of the observations, indexed by bipartite graphs, which is almost orthonormal. The moments of these polynomials are governed by the number of solutions of polynomial systems over the finite field $\mathbb F\_{d+1}$ that are induced by the BCH code, and the crux of our analysis is to connect the combinatorial structure of the bipartite graphs with the structure of the solution sets of these systems.

0.19

Polytope Sampling at the Speed of Isoperimetry

cs.DS math.OCmath.PR ·2026-10-16 ·Anming Gu, Bobby Shi, Kevin Tian, Hubert Yang
similarity 0.56
Abstract · 58 pages

We give faster algorithms for sampling from the uniform distribution over a polytope. Our main result is an algorithm that, when applied to a polytope with $m$ constraints in $n$ dimensions, uses $m \cdot \mathrm{poly}\log(\frac m δ)$ iterations, each running in time $O(mn^{ω- 1})$, to return a sample within total variation distance $δ$ to the uniform distribution. When $m =O(n)$ and $δ= \mathrm{poly}(\frac 1 n)$, our runtime improves upon all prior works by an $Ω(n^{2/3})$ factor. Our sampler is based on the recent \emph{functional stochastic localization} framework of [GST26], and achieves an iteration count nearly matching the Poincaré constant of the uniform distribution with respect to the logarithmic barrier.

0.55

A sampling Lovász Local Lemma

cs.DS math.PR ·2026-09-16 ·Dimitris Achlioptas
similarity 0.56
Abstract · Added asymmetric criterion for sampling from counting and a deterministic approximate counting algorithm under the asymmetric criterion

We give an approximately uniform sampler for satisfying assignments of constraint satisfaction problems that satisfy $4\mathrm e p(Δ+1)^2\le1$, where $p$ is the largest constraint-violation probability under the uniform product distribution, and $Δ$ is the maximum degree of the dependency graph. The algorithm invokes the recent efficient approximate counting algorithm of Liu, Wang, Yin, Zhang, and Zhou~\cite{CountingLLL} as a subroutine and returns a satisfying assignment sampled within total-variation distance $\varepsilon$ of the uniform distribution in $(n+m/\varepsilon)^{O(kΔ\log D)}$ time, where $n$ and $m$ are the numbers of variables and constraints, $D$ is the common domain size, and $k$ bounds the constraint arity. We also give an asymmetric product-form condition under which both counting and sampling are efficient. To supply the counts needed in the additional regime, we extend the marginal-expansion proof of Liu et al.

0.31

On the Pseudo-Mixing of Kac's Walk

cs.CR math.PRcs.LG ·2026-08-18 ·Natesh S. Pillai, Aaron Smith, Vinod Vaikuntanathan
theoryhighly cited similarity 0.56
Abstract · 48 pages

Motivated by a conjecture of Vaikuntanathan and Zamir, we study the pseudo-mixing of Kac's walk on $\mathrm{SO}(n)$: whether short trajectories are indistinguishable from Haar measure by low-complexity tests. We prove that the first $k$ columns mix in Wasserstein distance in $O(n(k+\log n)\log n)$ steps for fixed accuracy, resolving a conjecture of Oliveira. Combining this with a representation-theoretic variance bound, we show that if $T=ω(nk(k+\log n)\log n)$, then every degree-$k$ polynomial normalized to have unit Haar variance has expectation under the $T$-step law within $o(1)$ of its Haar expectation. As an application, we show that this pseudo-mixing estimate can be used to prove the effectiveness of a fast Johnson--Lindenstrauss transform with the usual target dimension.

0.42