Thinning to improve two-sample discrepancy
Gleb Smirnov, Roman Vershynin · 2025
Read Thinning to improve two-sample discrepancy by Gleb Smirnov, Roman Vershynin (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-2506-20932.txt.
Introduction
Gleb Smirnov and Roman Vershynin (2025) show how throwing away a few points makes two samples look more alike. When two samples come from the same distribution, their discrepancy, the largest gap between their counts, typically grows like the square root of the sample size. The authors give an online algorithm that discards a small fraction of points as they arrive. After thinning, the discrepancy drops to a power of a logarithm of the sample size. The result matters for methods that keep small summaries of large datasets.
Catalog record
| CREATOR | Gleb Smirnov, Roman Vershynin |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 18 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-20932
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Thinning to improve two-sample discrepancy Thanks: R.V. is partially supported by NSF Grant DMS 1954233 and NSF+Simons Research Collaborations on the Mathematical and Scientific Foundations of Deep Learning Gleb Smirnov, Roman Vershynin Abstract . The discrepancy between two independent samples X 1 , … , X n X_{1},\dots,X_{n} and Y 1 , … , Y n Y_{1},\dots,Y_{n} drawn from the same distribution on ℝ d \mathbb{R}^{d} typically has order O ( n ) O(\sqrt{n}) even in one dimension. We give a simple online algorithm that reduces the discrepancy to O ( log 2 d n ) O(\log^{2d}n) by discarding a small fraction of the points. Random sampling inevitably brings errors. Classical work in statistics and probability has led to a thorough understanding of sampling errors. Much less is known about how to reduce them with minimal intervention. In this paper, we address the following version of the problem – how to align two independent random samples with each other by discarding a few points? 1. Main results Let X_{1},\dots,X_{n} and Y_{1},\dots,Y_{n} be two independent samples, each consisting of n independent observations drawn from the same Borel probability distribution on \mathbb{R}^{d} . For a Borel set B\subset\mathbb{R}^{d} , we count how many points from each sample fall into B , and define its discrepancy as: \operatorname{disc}(B)\coloneqq\big\lvert\#\{i:\;X_{i}\in B\}-\#\{i:\;Y_{i}\in B\}\big\rvert. Taking the supremum over all axis-aligned, half-infinite 1 1 1 Our main results remain valid if the supremum is taken over all finite boxes B=[a_{1},b_{1}]\times\cdots\times[a_{d},b_{d}] . boxes B=(-\infty,b_{1}]\times\cdots\times(-\infty,b_{d}] , define: (1.1) D_{n,n}\coloneqq\sup_{B}\operatorname{disc}(B). In dimension d=1 , the normalized discrepancy n^{-1}D_{n,n} recovers the Kolmogorov-Smirnov distance. Classical VC theory [ 15 , Theorem 8.3.23] gives: \E D_{n,n}=O_{d}\big(\sqrt{n}\big). This order is optimal for any nontrivial distribution, because we have \E\operatorname{disc}(B)\asymp\sqrt{n} for any set B whose measure is bounded away from 0 and 1 . However, the discrepancy can be drastically reduced by discarding a small fraction of the samples: Theorem 1 (Two-sample discrepancy) . Fix T so that 1\leqslant T\leqslant\sqrt{n} . Let X_{1},\dots,X_{n} and Y_{1},\dots,Y_{n} be i.i.d. samples from the same Borel probability distribution on \mathbb{R}^{d} . There is a randomized online algorithm that discards, on average, at most Cn/T of the X_{i} ’s and Y_{i} ’s, and achieves \E D_{n,n}\leqslant T\log_{2}^{2d}n, where C is an absolute constant. Expectations are over both samples and the algorithm. The algorithm (described in § 3 ) does not need to know the distribution. It is online in the sense that it processes points one by one, with the location of each point revealed only when processed. The decision to keep or discard a point depends only on its value and past decisions, and is final. At each step, the algorithm randomly chooses whether to process the next point from the X - or Y -sample by tossing a fair \pm 1 coin: if +1 , a point from X ; if -1 , from Y . The procedure stops when one sample is exhausted; all remaining points from the other are discarded. On average, O(\sqrt{n}) points are left unprocessed, which is absorbed into the O(n/T) discard budget. Let x_{1},\ldots,x_{k}\in\mathbb{R}^{d} , with k<2n , denote the sequence of processed points. For each i , define \varepsilon_{i}=1 if x_{i} is from the X -sample and \varepsilon_{i}=-1 if x_{i} is from the Y -sample. Then \varepsilon_{1},\ldots,\varepsilon_{k} are i.i.d. Rademacher random variables. For any Borel set B\subset\mathbb{R}^{d} , define the sign discrepancy : (1.2) \disc_{k}(B)=\Big\lvert\sum_{i=1}^{k}\varepsilon_{i}\mathbf{1}_{\{x_{i}\in B\}}\Big\rvert. This reduces Theorem 1 to: Proposition 1 (Sign discrepancy) . Let m be an integer with m\leqslant 2n . Let x_{1},\dots,x_{m} be i.i.d. samples from a Borel probability distribution in \mathbb{R}^{d} , let \varepsilon_{1},\ldots,\varepsilon_{m} be independent Rademacher random variables, and let T>0 . There is an online algorithm that discards, on average, at most n/T of the x_{i} ’s, and achieves \E\sup_{B,1\leqslant k\leqslant m}\disc_{k}(B)\leqslant T\log_{2}^{2d}n+d\ln(dn)+C_{1}d, where the supremum is over all axis-aligned, half-infinite boxes B and all k=1,\ldots,m , and where C_{1} is an absolute constant. Specializing to m=2n recovers Theorem 1 . Remark 1 (Time and memory cost) . The proof shows that each point can be processed in time O(\log_{2}^{d}n) , independent of the parameter T , yielding a total time complexity of O(n\log_{2}^{d}n) . The algorithm also requires O(n\log_{2}^{d}n) memory. Remark 2 (Prior work) . Constructing point sets with low discrepancy (star and two-color) is a classical, well-studied problem; see the monographs [ 13 , 10 , 7 ] . Less is known about how to improve the discrepancy of a given random sample by moving or discarding only a few points. Recent progress appears in [ 12 , 9 , 11 , 8 , 14 ] . Closest to our setting is the work [ 12 ] , which considers the star discrepancy – a stronger notion than the two-sample discrepancy – that compares the empirical measure with the true measure over axis-aligned boxes. The authors provide an online algorithm for points sampled from the uniform distribution on [0,1]^{d} ; their algorithm discards O(n/T) points and achieves star discrepancy O(T\log^{2d}n) . Applied separately to the samples X and Y , and combined via the triangle inequality, this yields a version of Theorem 1 . The proof in [ 12 ] relies on the orthogonality of Haar wavelets and is thus limited to the uniform measure on the cube. Our approach avoids orthogonality and applies to arbitrary Borel distributions on \mathbb{R}^{d} . For results on general measures, we refer to [ 1 , 2 ] , which construct low-discrepancy sequences without assumptions on the underlying distribution. However, these constructions do not rely on thinning random samples and are thus not directly applicable to our setting. Our work also relates to recent advances in online discrepancy minimization [ 3 , 6 , 5 , 4 ] , which consider assigning a stream of 2n points in [0,1]^{d} to two sets X and Y (without discards) to minimize discrepancy ( 1.1 ). A variant of our algorithm may offer another approach to that problem. Conversely, it would be interesting to see if their techniques could sharpen Theorem 1 . Remark 3 (Open question) . It remains open whether the bound O(\log^{2d}n) in Theorem 1 is optimal. It would be interesting to either improve this bound or establish a matching lower bound. 2. Reduction to the case of uniform marginals It suffices to prove Proposition 1 for distributions whose d coordinate marginals are uniform on [0,1] . We now explain why this entails no loss of generality. Let F_{1},\ldots,F_{d} be the marginal cumulative distribution functions. Without loss of generality, we may assume that each F_{i} is strictly increasing. This follows by perturbation: consider a mixture of the original distribution with a Gaussian on \mathbb{R}^{d} . More precisely, flip a biased coin with success probability \theta ; if success, sample from the original distribution; otherwise, sample from the Gaussian. Samples of m points from the original and perturbed distributions coincide with probability \theta^{m} , and so do their sign discrepancies. As \theta\to 1 , the expected discrepancy of the perturbed sample converges to that of the original. We may thus sample from the mixture instead of the original distribution, and the marginals F_{i} of the mixture are strictly increasing. For a real-valued random variable