Source-linked AI summary
Total Variation Distance Estimation through Domain Reduction
Arnab Bhattacharyya, Graham Cormode, Yucheng Fu, Kuldeep S. Meel
TL;DR
TV distance is difficult to approximate for succinct high-dimensional distributions, and prior mixture algorithms depended exponentially on the number of components. The paper uses Lewis-weight-based domain reduction to construct polynomial-size weighted subsets preserving linear projections, obtaining an FPRAS for mixtures and extending the approach to structured circuits. Its circuit result applies to smooth, structured-decomposable circuits with a common v-tree.
Problem
TV distance does not decompose coordinatewise even for product distributions, and prior mixture algorithms had exponential dependence on component count.
Source: §1 · p. 1Method
The algorithm incrementally uses Lewis-weight sampling to compress assignment domains into weighted subsets that preserve all relevant linear projections.
Source: §1 · p. 2, §1.1 · p. 3Results
The paper gives a relative-approximation FPRAS for mixtures of product distributions with running time polynomial in dimension, alphabet size, component count, and desired accuracy.
Source: §1 · p. 2Takeaways & Limitations
Domain reduction also yields relative-approximation algorithms for smooth, structured-decomposable probabilistic circuits sharing a common v-tree.
Source: §1 · p. 2The circuit result requires smooth, decomposable inputs; internal subcircuits may be unnormalized, but the root outputs must be normalized probability mass functions.
Source: §1.1 · p. 4, §4 · p. 10
Abstract
from arXiv · showhide
Computing the total variation (TV) distance between succinctly represented high-dimensional distributions is generally intractable. We give an FPRAS for TV distance between mixtures of product distributions and, more generally, for a natural class of structured probabilistic circuits. Our main technique is a novel application of domain reduction: Given a family of feature vectors indexed by assignments, we use Lewis-weight sampling to replace the assignment domain by a polynomial-size weighted subset that simultaneously approximates the sum of absolute values of every linear projection. For mixtures of product distributions, we construct such reduced domains incrementally over the coordinates, obtaining the first FPRAS with running time polynomial in both the dimension and the number of mixture components. We then extend the approach to smooth, structured-decomposable probabilistic circuits with a common structured architecture.
1 Introduction
The paper addresses relative TV approximation for succinct high-dimensional distributions, where TV does not decompose coordinatewise and prior mixture algorithms depend exponentially on the number of components. It uses domain reduction to obtain polynomial-time approximation for mixtures and extends the approach to structured probabilistic circuits and weighted tree automata.
1 Introduction
- TV does not decompose coordinatewise even for product distributions, while exact computation for two product distributions is #P-complete [BGM+23].Prior mixture algorithms had exponential dependence on the total number of components, leaving polynomial dependence on that input parameter open [FFYZ26] [Fu26].Source: §1 · pp. 1–2
- The algorithm gives a relative TV approximation for mixtures of product distributions in time polynomial in dimension, alphabet size, component count, and desired accuracy.Its running time is independent of the numerical value of the distance in the real-arithmetic model.Source: §1 · p. 2
- Domain reduction compresses exponentially many partial assignments into a polynomial-size weighted subset preserving every relevant linear functional via ℓ1 subspace sparsification with Lewis weights.Preserving all linear functionals simultaneously keeps a reduced domain valid under arbitrary future coordinates.Source: §1 · p. 2
1.1 Technical overview
- The approach extends to smooth, structured-decomposable circuits sharing a v-tree, even when their gates and wiring otherwise differ.Smoothness makes sum gates linear on a scope; decomposability gives product gates disjoint scopes, enabling the bottom-up coreset composition.Source: §1 · p. 2, §1.1 · pp. 4–5
1 Introduction
1.1 Technical overview
- At each coordinate, the algorithm extends retained prefixes and uses ℓ1 Lewis-weight row sampling to form a smaller weighted set preserving linear queries.The resulting set size is polynomial in inverse error and feature dimension, independent of the number of represented prefixes.Source: §1.1 · p. 3
- For mixtures, the feature dimension grows with the number of components, and Lewis-weight sampling keeps the retained-prefix count polynomial in that dimension.This removes the exponential dependence on mixture components in earlier approaches.Source: §1.1 · p. 4
1.2 Related work
- The paper targets relative approximation from succinct parameters, preserving very small TV distances multiplicatively rather than using generic additive estimation.It presents domain reduction as a direct TV approximation method for structured circuits, distinct from relying on tractable circuit closure properties.Source: §1.2 · p. 6
2 Preliminaries
The setup represents mixtures through componentwise feature vectors whose weighted projection gives the pointwise difference P(x) − Q(x). Domain coresets then preserve absolute linear projections while compressing assignments.
2.1 Problem Setup
- For mixtures over a discrete product space, each coordinate contributes a feature vector of component probabilities, and the mixture-weight vector projects the accumulated features to P(x) − Q(x).The total variation distance is the sum of the absolute values of these projections over the domain.Source: §2.1 · p. 7
2.2 L1 Subspace Embeddings and Domain Coresets
- At each step, replace the exponentially large exact assignment domain with a small weighted subset preserving all relevant linear tests.The weighted projections are represented as the L1 norm of a matrix-vector product.Source: §2.2 · p. 7
- Lewis-weight sampling yields a reweighted subset of at most m assignments that uniformly preserves every linear projection within relative error 1 ± δ, with probability at least 1 − η.The sample size is m = O(d log d …); the supplied passage truncates the full bound.Source: §2.2 · p. 7
3 Algorithm and Analysis
The algorithm extends retained prefixes one coordinate at a time and sparsifies each candidate domain using Lewis weights. Its guarantees propagate the per-step approximation to an FPRAS whose runtime is polynomial in the natural input parameters.
3.1 The FPRAS Algorithm
- At each coordinate, the algorithm extends every retained prefix by each domain value, then sparsifies the candidate assignments into a weighted coreset.Sparsify uses the feature matrix and L1 Lewis weights; the stepwise error and failure parameters are set from ϵ and η.Source: §3 · p. 8, §3.1 · p. 8
3.2 Analysis
- With probability at least 1 − η, the algorithm returns a relative-accuracy estimate in time polynomial in n, k, 1/ϵ, log(1/η), and the maximum domain size.The proof telescopes the per-step approximation, using δ = ϵ/(3n).Source: §3.2 · pp. 8–9
- Each successful sparsification preserves the weighted absolute projections for all query vectors within relative error 1 ± δ.The guarantee follows by applying the L1 subspace embedding to the candidate feature matrix.Source: §3.2 · p. 8
- The hybrid functional’s error propagates by a factor of 1 ± δ per successful step, and summing over future assignments preserves that bound.A union bound gives overall success probability at least 1 − η; telescoping the n steps yields the final approximation.Source: §3.2 · p. 9
4 Extension to Probabilistic Circuits
The section extends domain-reduction-based TV estimation to smooth, decomposable probabilistic circuits sharing a v-tree. It propagates weighted assignment coresets bottom-up, using linear maps at sum gates and sparsification at product gates.
4.1 Circuit Setup and Domain Coresets
- Each region’s feature vector concatenates evaluations of gates from both circuits, whose gates and wiring may otherwise differ.The circuits use nonnegative univariate lookup-table functions and sum-gate weights; only their root outputs must be normalized probability mass functions.Source: §4 · pp. 9–10, §4.1 · p. 10
- The root coreset estimates TV by applying a query that subtracts the two circuits’ root outputs and summing absolute projections over its weighted assignments.The method’s arithmetic cost depends on the number of circuit gates and wires, the maximum coreset size, and the maximum leaf-domain size.Source: §4.1 · p. 10, §4.3 · p. 11
4.2 Bottom-Up Coreset Construction
- At product regions, the algorithm forms a Cartesian product of child coresets and sparsifies its bilinear features; sum gates apply linear maps to surviving rows.Leaf assignment domains are enumerated exactly, and a sum layer following a product layer adds no further sparsification.Source: §4.2 · pp. 10–11
4.3 Approximation Guarantee and Complexity
- The estimator achieves (1 ± ϵ) relative error with probability at least 1 − η for circuits structured by a common v-tree.The guarantee follows by combining the coreset propagation invariant across product regions and setting the local error to ϵ/(3L).Source: §4.3 · p. 11
5 Application to Weighted Tree Automata
The section applies domain reduction to distributions induced by nonnegative weighted tree automata on a shared binary tree. It represents their bottom-up bilinear computations as structured probabilistic circuits and obtains an FPRAS for their TV distance.
5 Application to Weighted Tree Automata
- Each automaton assigns nonnegative leaf weights and combines child messages through bilinear transitions, yielding a bottom-up tree computation.State dimensions and transition tensors may vary by node.Source: §5 · p. 12
- The two models’ normalization constants are computed exactly by a bottom-up dynamic program, without enumerating the full leaf-labeling space.The normalized root outputs are represented by appending a unary root sum gate with weight Z_R^-1.Source: §5 · pp. 12–13
- Each bilinear transition is expanded into scalar product gates followed by scalar sum gates, preserving the shared tree structure needed for circuit approximation.Product gates use disjoint child scopes, while sum gates have children with the same scope.Source: §5 · pp. 13–14
- An FPRAS estimates TV distance between distributions from two nonnegative weighted tree automata on the same tree, with relative error ϵ and success probability at least 1 − η.The running-time bound depends on the maximum leaf-domain size and joint node-interface dimension, as well as tree and circuit parameters.Source: §5 · pp. 13–14