Improving discrepancy by moving a few points

Gleb Smirnov, Roman Vershynin · 2025

Read Improving discrepancy by moving a few points 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-2503-04100.txt.

Introduction

Gleb Smirnov and Roman Vershynin show in a 2025 paper how to improve the discrepancy of a random sample by moving just a few of its points. Discrepancy here means the gap between the sample and the true population distribution, read by the Kolmogorov-Smirnov distance.

The sample points are drawn on their own, from the same distribution. Left alone, such a sample can sit at a clear distance from the truth by chance. The result says that to change just a small set of points, on average, drops that distance to a much smaller scale. The gain comes at a low cost in moved points.

Catalog record

CREATORGleb Smirnov, Roman Vershynin
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE19 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-04100

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Improving discrepancy by moving a few points 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 . We show how to improve the discrepancy of an iid sample by moving only a few points. Specifically, modifying O ⁡ ( m ) O(m) sample points on average reduces the Kolmogorov–Smirnov distance to the population distribution to 1 / m 1/m . 1. Main results Let X_{1},\dots,X_{n} be an iid sample from a distribution on \mathbb{R} with cumulative distribution function F(x) . The empirical distribution function of the sample is defined as F_{n}(x)=\frac{1}{n}\sum_{i=1}^{n}\mathbf{1}_{\{X_{i}\leqslant x\}},\quad x\in\mathbb{R} Define the sample discrepancy D_{n} as the Kolmogorov-Smirnov distance between the empirical and population distributions: D_{n}=\sup_{x}\lvert F_{n}(x)-F(x)\rvert. Dvoretzky–Kiefer–Wolfowitz inequality (DKW) implies that D_{n}=O(1/\sqrt{n}) with high probability [ 2 , 3 ] . Our first result shows that the discrepancy can be significantly reduced by carefully changing a small fraction of the sample: Theorem 1 (One-sample discrepancy) . Given iid observations X_{1},\dots,X_{n} from a distribution with cumulative distribution function F(x) and a number m\in(0,n] , one can replace at most Cm observations on average so that (1.1) D_{n}=\sup_{x}\lvert F_{n}(x)-F(x)\rvert\leqslant\frac{1}{m}, where C>0 is an absolute constant. Note that the replacements are done via a constructive procedure (Algorithm 1) that has an explicit time complexity of O\bigl(n\ln(n)\ln(m)\bigr) . See § 5 . Next, let X_{1},\dots,X_{n} and Y_{1},\dots,Y_{n} be two independent samples from the same distribution, each consisting of n independent observations. Define their empirical distribution functions as: F_{n}(x)=\frac{1}{n}\sum_{i=1}^{n}\mathbf{1}_{\{X_{i}\leqslant x\}},\quad G_{n}(x)=\frac{1}{n}\sum_{i=1}^{n}\mathbf{1}_{\{Y_{i}\leqslant x\}}, and consider the two-sample discrepancy D_{n,n}=\sup_{x}\lvert F_{n}(x)-G_{n}(x)\rvert. Our second result shows that the discrepancy can be significantly reduced by changing a small fraction of observations in one sample: Theorem 2 (Two-sample discrepancy) . Given iid observations X_{1},\dots,X_{n} and Y_{1},\dots,Y_{n} from the same distribution and a number m>0 , one can replace at most Cm observations on average in X_{1},\dots,X_{n} so that \sup_{x}\lvert F_{n}(x)-G_{n}(x)\rvert\leqslant\frac{1}{m}, where C>0 is an absolute constant. Our results above are sharp, as the following matching lower bound shows: Proposition 1 (Lower bound) . Given iid observations X_{1},\dots,X_{n} from the uniform distribution on [0,1] and a number m\geqslant\sqrt{n} , achieving a discrepancy of c/m requires replacing at least cm observations on average. Here c>0 is an absolute constant. The constraint m\geqslant\sqrt{n} is explained by the fact that the discrepancy is always O(1/\sqrt{n}) with high probabillity by the DKW inequality, even without replacing any points. Remark 1 (Removing instead of replacing) . Our work was inspired by the recent result of D. Bilyk and S. Steinerberger [ 1 ] , which achieves a discrepancy of O(\ln(n)/m) by removing at most m points from the original sample. As shown in [ 1 ] , this result is optimal in terms of the number of removed points. 2. Proof of Theorem 1 Our argument will be based on DKW inequality [ 2 ] : (2.1) \mathbb{P}\left\{D_{n}>\dfrac{t}{\sqrt{n}}\right\}\leqslant 2e^{-2t^{2}},\quad t\geqslant 0 where the optimal constant 2 in front of the exponent was obtained by P. Massart [ 3 ] . To begin with, let us show that it suffices to consider the case where X_{1},\dots,X_{n} follow the uniform distribution on [0,1] . This step is standard: Lemma 1 . If Theorem 1 holds for the uniform distribution \mathrm{Unif}[0,1] , then it holds for all distributions. Proof. Let X be a random variable with cumulative distribution function F(x) , which may not be continuous or strictly increasing. Consider the generalized inverse of F : F^{-1}(u)=\inf\left\{x\,:\,F(x)\geqslant u\right\}. For all x\in\mathbb{R} and u\in[0,1] , we have (2.2) \{F^{-1}(u)\leqslant x\}\quad\text{iff}\quad\{u\leqslant F(x)\}. If X is F -distrbuted, then so is F^{-1}(U) for a uniform random variable U , as follows from ( 2.2 ): \mathbb{P}\{F^{-1}(U)\leqslant x\}=\mathbb{P}\{U\leqslant F(x)\}=F(x). Thus, we may assume without loss of generality that X_{i}=F^{-1}(U_{i}) , where U_{i} are independent uniform random variables. By ( 2.2 ), for each x , \#\{X_{i}\leqslant x\}=\#\{U_{i}\leqslant F(x)\}. Setting u=F(x) , we find: \left\lvert\frac{\#\{X_{i}\leqslant x\}}{n}-F(x)\right\rvert=\left\lvert\frac{\#\{U_{i}\leqslant u\}}{n}-u\right\rvert, and the lemma follows. ∎ Throughout, let us assume that the sample X_{1},\dots,X_{n} is drawn from the uniform distribution \mathrm{Unif}[0,1] . For convenience, let us also assume that n is odd. If n is even, one may simply discard one observation and reintroduce it later; since a single point contributes negligibly to the discrepancy, this does not affect the overall result. Our goal is to modify the sample by replacing, on average, only O(m) observations so that the new sample has discrepancy O(1/m) . Introduce a uniform grid: Y_{k}=\frac{k}{n},\quad k=0,1,\dots,n-1. Let us use the following measure of discrepancy. For each (closed) interval I\subset[0,1] , define: d_{Y}(I)=\sup_{J}\left\lvert\frac{\#\{X_{i}\in J\}}{n}-\frac{\#\{Y_{k}\in J\}}{n}\right\rvert, where the supremum is taken over all intervals J\subset I sharing the left endpoint with I . Note that for each J , \left\lvert\frac{\#\{X_{i}\in J\}}{n}-\lvert J\rvert\right\rvert\leqslant\left\lvert\frac{\#\{X_{i}\in J\}}{n}-\frac{\#\{Y_{k}\in J\}}{n}\right\rvert+\frac{1}{n}, where \lvert J\rvert denotes the length of J . We shall say that an interval I is acceptable if d_{Y}(I)\leqslant\dfrac{1}{m}. We shall say that an interval I is equalized if \#\{X_{i}\in I\}=\#\{Y_{i}\in I\}. Our goal to arrange that [0,1] is acceptable so that D_{n}\leqslant d_{Y}([0,1])+\frac{1}{n}\leqslant\frac{1}{m}+\frac{1}{n}\leqslant\frac{2}{m}, while keeping the number of replaced points O(m) on average. To do so, let us arrange the replacements as follows. Algorithm 1: • Start with I=[0,1] . • If the current interval I is not acceptable , divide it into two equal halves, I_{1} and I_{2} . Then randomly and independently select the appropriate number of sample points in one half and relocate them to random positions in the other half (chosen independently and uniformly) so that the two halves become equalized. • Apply the same procedure recursively to I_{1} and I_{2} . Since we begin with I=[0,1] , the endpoints of all intervals produced in this recursion are dyadic (i.e., of the form 2^{-j} ). Moreover, with n odd, no grid point Y_{k} lies in more than one such interval, and almost surely none of the sample points X_{i} equals one of these dyadic endpoints. It is clear that Algorithm 1 terminates after a finite number of steps. Let us now verify that the final outcome makes [0,1] acceptable. Lemma 2 . At the end of Algorithm 1, the interval [0,1] is acceptable. Proof. When the algorithm stops, it generates a partition of [0,1] into equalized, acceptable intervals. For any x\in[0,1] , let I be the unique interval (generated during the algorithm) that contains x , and let y denote the left endpoint of I . We calculate: \left|\frac{\#\{X_{i}\leqslant x\}}{n}-\frac{\#\{Y_{i}\leqslant x\}}{n}\right|\leqslant\left|\frac{\#\{X_{i}\leqslant y\}}{n}-\frac{\#\{Y_{i}\leqslant y\}}{n}\right|+\left|\frac{\#\{X_{i}\in[y,x]\}}{n}-\frac{\#\{Y_{i}\leqslant[y,x]\}}{n}\right| Since [0,y] is a disjoint union of back-to-back equalized intervals, it tself is equalized, so the first term on the right hand side is zero. Since I is acceptable, the second term is at most 1/m . Consequently, \left|\frac{\#\{X_{i}\leqslant x\}}{n}-\frac{\#\{Y_{i}\leqslant x\}}{n}\right|\leqslant 0+\frac{1}{m}\leqslant\frac{1}{m}, and the lemma follows. ∎ Let M_{1} denote the total number of points moved by Algorithm 1. We shall show that M_{1} is O(m) on average. To bound the expected total number of replaced points, we compare Algorithm 1 to the following alternative algorithm: Algorithm 2: • Start with I=[0,1] . • Divide I into two equal halves, I_{1} and I_{2} . Then randomly and independently select the appropriate number of sample points in one half and relocate them to random positions in the other half (chosen

Read the complete text