Sharp bounds on point discrepancy advance online sampling methods
Tusnády's problem and online two-sample thinning
Data Structures and Algorithms
Summary
This paper deals with measuring how unevenly points are spread in space, a problem important for statistics and computer science. The authors find exact rates for how this unevenness grows with more points, solving a longstanding question for multiple dimensions. They then apply these findings to improve ways to choose or discard points from two random groups as data arrives, optimizing how balanced these groups remain over time. The results show different behaviors depending on dimension and how many points can be discarded. They use advanced math tools involving probabilities and random processes to prove their results.
What this means in practice
- •For statistical sampling teams: Design online procedures to select balanced subsets from streaming data while controlling discrepancy under dimension constraints.
- •For machine learning engineers: Improve two-sample tests by better controlling sample discrepancy during data thinning for real-time distribution comparison.
A theory result. No direct application yet.
Authors
Yuhao Lei
Abstract
We determine the sharp order of discrepancy in Tusnády's problem in every fixed dimension $d\ge 2$. The largest combinatorial discrepancy of $N$ points in $\mathbb{R}^d$ with respect to axis-parallel boxes is $Θ_d((\log N)^{d-1/2})$, extending Wei's planar result and matching Nikolov's upper bound. More strongly, with high probability, this lower bound holds simultaneously for every subset obtained by deleting at most a sufficiently small fixed fraction of a uniform $N$-point sample. We apply this geometric estimate to online thinning of two independent samples of size $n$ from an unknown common distribution, where observations must be kept or discarded upon arrival. For every fixed dimension $k\ge 1$ and expected deletion budget $ρn$, with $0<ρ<2$, we prove that the minimax expected prefix discrepancy over lower orthants is $Θ_{k,ρ}((\log n)^{k+1/2})$. In dimension one, the optimal terminal discrepancy is instead $Θ_ρ((\log\log n)^{3/2})$, giving a sharp separation between the prefix and terminal objectives. For $k\ge 2$, we obtain terminal bounds differing by a factor of $\log n$. The lower bounds are based on Gaussian small-ball estimates for box-incidence matrices, while the upper bounds use stationary Metropolis thinning and, in one dimension, a terminal cancellation procedure.