Algorithms and Hardness for Estimating Statistical Similarity
Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, Dimitrios Myrisiotis, A. Pavan, N. V. Vinodchandran · 2025
Read Algorithms and Hardness for Estimating Statistical Similarity by Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, Dimitrios Myrisiotis, A. Pavan, N. V. Vinodchandran (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-10527.txt.
Introduction
Arnab Bhattacharyya and five co-authors study how hard it is to compute the overlap between two probability distributions, in a 2025 paper. The overlap, called statistical similarity, adds up, for each outcome, the smaller of the two chances. It underlies the best possible error in guessing which distribution produced a sample.
Exact computation is known to be very hard even for simple product distributions. That hardness pushes the field toward approximation methods with provable accuracy. The team gives new algorithms for estimating the overlap and new hardness results that bound what any method can do. Their results draw a sharper line between tractable and intractable cases. The measure also matters for testing whether two data sources match.
Catalog record
| CREATOR | Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, Dimitrios Myrisiotis, A. Pavan, N. V. Vinodchandran |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-10527
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Algorithms and Hardness for Estimating Statistical Similarity Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, Dimitrios Myrisiotis, A. Pavan, N. V. Vinodchandran Abstract We introduce and study the computational problem of determining statistical similarity between probability distributions. For distributions P P and Q Q over a finite sample space, their statistical similarity is defined as S stat ( P , Q ) := ∑ x min ( P ( x ) , Q ( x ) ) S_{\mathrm{stat}}(P,Q):=\sum_{x}\min(P(x),Q(x)) . Despite its fundamental nature as a measure of similarity between distributions, capturing essential concepts such as Bayes error in prediction and hypothesis testing, this computational problem has not been previously explored. Recent work on computing statistical distance has established that, somewhat surprisingly, even for the simple class of product distributions, exactly computing statistical similarity is # 𝖯 \#\mathsf{P} -hard. This motivates the question of designing approximation algorithms for statistical similarity. Our first contribution is a Fully Polynomial-Time deterministic Approximation Scheme (FPTAS) for estimating statistical similarity between two product distributions. Furthermore, we also establish a complementary hardness result. In particular, we show that it is 𝖭𝖯 \mathsf{NP} -hard to estimate statistical similarity when P P and Q Q are Bayes net distributions of in-degree 2 2 . 1 Introduction Given two distributions P and Q over a finite sample space, their statistical similarity, denoted S_{\mathrm{stat}}(P,Q) , is defined as \displaystyle S_{\mathrm{stat}}(P,Q):=\sum_{x}\min(P(x),Q(x)). (1) Statistical similarity serves as a fundamental measure in machine learning and statistical inference. We defer a detailed discussion of motivating applications to Section 1.1 . When the sample space is small, computing S_{\mathrm{stat}} is trivial. However, for high-dimensional distributions, this computation presents significant challenges. Surprisingly, recent work BGM+ (23) has established that computing S_{\mathrm{stat}} is \#\mathsf{P} -hard even for the simple class of product distributions. This hardness result is striking given that product distributions represent one of the most basic high-dimensional distribution classes, where each dimension is independent of other dimensions. The hardness of this elementary case raises fundamental questions about the computational nature of statistical similarity: Can we develop efficient approximation algorithms for classes of distributions of interest? In general, what is the boundary between tractable and intractable similarity computation? The primary contribution of this work is to initiate a principled investigation of the computational aspects of statistical similarity, identifying both tractable and intractable scenarios. Our first contribution is a Fully Polynomial-Time deterministic Approximation Scheme (FPTAS) for estimating S_{\mathrm{stat}} between product distributions. To complement this algorithmic result, we establish sharp computational boundaries by proving that approximating S_{\mathrm{stat}} becomes \mathsf{NP} -hard even for slightly more general distributions. Specifically, we show that the problem is \mathsf{NP} -hard to approximate for Bayes net distributions with in-degree 2 . Note that we work in a computational setting, where the algorithms have access to a succinct description of distributions. 1.1 Motivating Applications Statistical similarity plays a central role across multiple domains in machine learning and statistics. We examine three key applications of statistical similarity: Its connection to Bayes error in prediction problems, its role in characterizing optimal decision rules in hypothesis testing, and its interpretation through coupling theory. These applications demonstrate the significance of S_{\mathrm{stat}} . Statistical similarity arises naturally in the analysis of prediction problems through the notion of Bayes error . Consider a binary prediction problem defined by a distribution P over X\times\{0,1\} , where X is a finite feature space. When a classifier g:X\to\{0,1\} attempts to predict the label, it incurs a 0 - 1 prediction error measured as \Prob_{(x,y)\sim P}\!\left[g(x)\neq y\right] . The Bayes optimal classifier , which outputs 1 if and only if P(x|1)>P(x|0) , achieves the minimum possible error R^{*} , known as the Bayes error. This error represents a fundamental lower bound that no classifier can surpass. The connection to statistical similarity manifests through a precise mathematical relationship: For any prediction problem, the Bayes error exactly equals the statistical similarity between its scaled likelihood distributions. Specifically, if we denote the prior probabilities P(0) and P(1) by \alpha_{0} and \alpha_{1} respectively, then R^{*}=S_{\mathrm{stat}}(\alpha_{0}P(0|X),\alpha_{1}P(1|X)) (a proof is given in Appendix A ), where \alpha_{i}P(i|X) represents the sub-distribution obtained by scaling P(i|X) with \alpha_{i} . The relationship between statistical similarity and optimal decision-making extends beyond prediction problems to the domain of hypothesis testing ( LR, 08 ; Nie, 14 ) . This setting is particularly relevant to our computational focus, as it deals with known distributions representing null and alternate hypotheses. A recent result KA (24) establishes how statistical similarity between product distributions determines the optimal error in hypothesis testing PSNK (14) ; BK (15) . To illustrate this connection, consider a hypothesis testing game where a random bit Y\in\{0,1\} is drawn with bias p_{1} (letting p_{0}=1-p_{1} ), followed by an i.i.d. sequence X_{1},\ldots,X_{n} where each X_{i}\in\{0,1\} satisfies \Prob[X_{i}=1|Y=1]=\psi_{i} and \Prob[X_{i}=1|Y=0]=\eta_{i} for parameters \psi,\eta\in(0,1)^{n} . The optimal decision rule f^{\sf OPT}:\{0,1\}^{n}\to\{0,1\} that minimizes \Prob[f^{\sf OPT}(X)\neq Y] achieves an error rate of S_{\mathrm{stat}}(p_{1}\mathrm{Bern}(\psi),p_{0}\mathrm{Bern}(\eta)) , where \mathrm{Bern}(\psi) denotes the product distribution of individual \mathrm{Bern}(\psi_{i}) distributions. These theoretical connections have significant practical implications. Since Bayes error represents the theoretically optimal performance limit, statistical similarity serves as a benchmark for the evaluation of machine learning models. This capability has spurred extensive research in estimating Bayes error and statistical similarity FH (75) ; Dev (85) ; NXH (19) ; TWV+ (21) ; IYC+ (23) . Statistical similarity can be interpreted through coupling theory. For distributions P and Q , a coupling is a distribution (X,Y) where X\sim P and Y\sim Q . It is known that S_{\mathrm{stat}}(P,Q) equals the maximum over all couplings (X,Y) , \Prob(X=Y) . Coupling theory, introduced by Doeblin Doe (38) , has led to important results in computer science and mathematics Lin (02) ; LPW (06) ; MT (12) . Finally, statistical similarity admits a characterization in the form of statistical distance (also known as total variation distance) d_{\mathrm{TV}} , defined as d_{\mathrm{TV}}(P,Q):=\max_{S\subseteq D}(P(S)-Q(S))=\frac{1}{2}\sum_{x\in D}|P(x)-Q(x)| . The identity S_{\mathrm{stat}}(P,Q)=1-d_{\mathrm{TV}}(P,Q) , known as Scheffé’s identity, establishes a duality (see Appendix B ). 1.2 Paper Organization We present some necessary background material in Section 2 . We then present a survey of related work in Section 3 . Section 4 describes our primary contributions. Section 5 is dedicated to our algorithmic result. The proof of \mathsf{NP} -hardness of estimating the statistical similarity between in-degree 2 Bayes net distributions is provided in Section 6 . Section 7 gives some concluding remarks. Appendix A discusses the connections between Bayes error and statistical similarity. Similarly, Appendix B elaborates on the connection between TV distance and statistical similarity. Appendix C contains the proof of Claim 11 , used in the proof of Theorem 5 . 2 Preliminaries We use \left[n\right] to denote the set \left\{1,\dots,n\right\} . We will use \log to denote \log_{2} . The following notion of a deterministic approximation algorithm is important in this work. Definition 1 . A function f:\left\{0,1\right\}^{*}\to\mathbb{R} admits a fully polynomial-time approximation scheme (FPTAS) if there is a deterministic algorithm \mathcal{A} such that for every input x (of length n ) and \varepsilon>0 , the algorithm \mathcal{A} outputs a \left(1+\varepsilon\right) -multiplicative approximation to f(x) , i.e., a value that lies in the interval \left[f(x)/(1+\varepsilon),(1+\varepsilon)f(x)\right] . The running time of \mathcal{A} is \mathrm{poly}\!\left(n,{1/\varepsilon}\right) . Definition 2 . Given