When data is spread across $k$ machines and a central server must estimate counts over the union, there are two very different ways to make each machine's summary cheap. The first is random sampling. Each machine's error is noisy but averages to zero, so errors from different machines partly cancel and the total grows only like $\sqrt{k}$. This is the idea behind the $\sqrt{k}$ communication savings in distributed tracking. The second is discrepancy-based compression. It repeatedly splits a point set into two halves that agree on every query of interest, then throws one half away. This gives per-machine errors far smaller than sampling, but the errors are systematic, so across machines they add up linearly in $k$. This proposal combines the two. Each machine builds a low-discrepancy split and then flips a single fair coin to decide which half to keep. The resulting summary is still nearly as accurate as the deterministic one, but its error now has mean zero, so errors from different machines cancel the way sampling errors do.
The setting where this matters is multi-attribute frequency estimation. The server needs counts not for single items but for whole families of sets defined jointly by two or more attributes, such as all two-dimensional dominance ranges ("how many records have age ≤ a and income ≤ b") or all halfplanes. For single-item frequencies or one-dimensional ranks, simple rounding or random-offset compaction already achieves this. In two or more dimensions, the gap between sampling error and discrepancy error is large: for 2D dominance ranges the hereditary discrepancy is polylogarithmic, while sampling error is polynomial. Nobody has shown how to make that advantage survive aggregation over many sites.
Core Claim
Take a query class $\mathcal{Q}$ of sets, and let $D(s)$ be the worst-case hereditary discrepancy of $s$ points with respect to $\mathcal{Q}$. Hereditary discrepancy is the best achievable imbalance between two halves of any subset; for 2D corners it is $O(\log^{2.5} s)$, as recorded in Fast Discrepancy Minimization with Hereditary Guarantees.
Site $i$ holds $n_i$ points. It compresses them to $s_i$ points by repeated halving. At each halving it computes a low-discrepancy $\pm 1$ coloring $x$, flips a fair coin to use $x$ or $-x$, keeps the $+1$ side, and doubles its weight.
Because $x$ and $-x$ are equally likely, the kept half is an unbiased estimate of every query count. The error introduced at each level is bounded in magnitude by the scaled discrepancy. The levels therefore form a martingale with bounded increments, and the sites are independent. A standard bounded-differences argument then bounds the server's error on every query $R \in \mathcal{Q}$, with high probability, by
$$ |\hat{c}(R) - c(R)| \;\lesssim\; \sqrt{\textstyle\sum_{i=1}^k n_i^2}\;\frac{D(s)}{s}\,\sqrt{\log|\mathcal{Q}|}, $$
where $c(R)$ is the true count, $\hat c(R)$ the server's estimate, and $s$ the per-site summary size.
With balanced sites ($n_i = N/k$), reaching error $\varepsilon N$ costs a total of about $\sqrt{k}\,D/\varepsilon$ points (up to the $\sqrt{\log|\mathcal{Q}|}$ factor), compared with three alternatives:
- Deterministic discrepancy compression costs about $k D/\varepsilon$, because its errors add linearly.
- Pooled random sampling costs about $\log|\mathcal{Q}|/\varepsilon^2$.
- The proposed method is therefore cheaper than sampling exactly when $k \lesssim 1/(\varepsilon D)^2$.
This mirrors the operating regime in which the randomized count-tracking protocol of Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks beats sampling ($k \le 1/\varepsilon^2$). It extends that $\sqrt{k}/\varepsilon$ behavior from scalar counts to any query class with polylogarithmic hereditary discrepancy.
The key ingredient is almost trivially cheap: one coin per halving, so about $\log n_i$ random bits per site. The proposal's claim is that this coin, not the discrepancy algorithm itself, is what converts centralized discrepancy gains into distributed communication gains.
Relation to Prior Work
Three centralized lines of work supply the compression step.
- Near-optimal Herding iterates the partial coloring lemma (which signs a constant fraction of points at a time while keeping all set imbalances small) to order a static dataset so that every prefix average is near-optimal.
- Streaming Covariate Balancing via Discrepancy-Based Feature Coresets uses greedy signing inside merge-and-reduce to keep a small, mergeable coreset of a single stream.
- Streaming Attention Approximation via Discrepancy Theory uses a self-balancing walk to halve transformer key-value caches.
All three operate on one stream and never ask how errors from independently compressed parts combine. That combination is exactly where the $k$ versus $\sqrt{k}$ distinction lives.
Fast Discrepancy Minimization with Hereditary Guarantees supplies the coloring algorithm we reuse. It runs in $O(mn^2\lg(2+m/n)+n^3)$ time and was demonstrated on $4000\times4000$ corner and halfspace matrices, which fixes a realistic per-site buffer size.
The distributed side motivates the proposal. Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks showed that zero-mean independent site errors let each site tolerate error $\varepsilon N/\sqrt{k}$ instead of $\varepsilon N/k$. Simple and Optimal Algorithms for Heavy Hitters and Frequency Moments in Distributed Models pushed sampling to $\ell_p$ heavy hitters and moments. Both rely on raw sampling noise as the per-site error. We keep their cancellation argument but replace that noise with discrepancy-scale noise.
The adversarial-robustness work constrains the design. A Simple and Robust Protocol for Distributed Counting and Adversarially Robust Distributed Count Tracking via Partial Differential Privacy show that hidden randomness can be extracted by an adaptive data source. The file's Gap 3 suggests deterministic discrepancy walks, as in Spectral Sparsification by Deterministic Discrepancy Walk, as a remedy. Our analysis says that remedy costs a factor $\sqrt{k}$, because deterministic errors cannot cancel. We take the opposite side of that trade-off and test the resulting vulnerability rather than assume it away.
Finally, the edge-coloring nibble algorithms rely on synchronized rounds to detect conflicts, for example Near-Optimal, Distributed Edge Colouring via the Nibble Method. Our partial-coloring stages run entirely inside one site, so no cross-site synchronization is needed.
Research Program
Stage 1: one-round model. Every site sends one message and the server answers all queries in $\mathcal{Q}$. We will prove the bound above for any coloring routine whose output imbalance on every subset is at most $D$. We will instantiate it with:
- the hereditary minimizer of Fast Discrepancy Minimization with Hereditary Guarantees;
- a cheaper greedy signing rule in the style of FCore;
- a self-balancing walk in the style of BalanceKV.
We will also handle unequal site sizes. Minimizing $\sum_i s_i$ subject to $\sum_i n_i^2 D^2/s_i^2 \le \varepsilon^2N^2$ gives $s_i \propto n_i^{2/3}$, which costs one extra scalar message per site. The analysis also predicts that the benefit vanishes when a single site holds most of the data, since then $\sqrt{\sum n_i^2}\approx N$. That prediction is tested directly below.
Stage 2: continuous tracking. We will embed the halving inside the round structure of the randomized tracking protocol. The difficulty is the not-yet-shipped buffer at each site, whose error is systematic unless it too is randomized. A first calculation suggests the obvious construction, in which the recent buffer is sampled and older buffers are compressed by sign-flipped halving, loses a polynomial factor relative to $\sqrt{k}/\varepsilon$. Finding a buffer rule that does not lose this factor is the main open theoretical question. We present it as such and do not claim the bound in advance.
Stage 3: robustness probe. We will measure how much an adaptive data source can learn from the $O(\log n)$ coins per site. We will also test whether making the server's output symmetric across sites, the idea behind the robust counting protocol, extends to weighted multi-attribute summaries.
Baselines
Naive reference. Every site ships its raw points. This costs $N$ points and has zero error. Every method is reported as a fraction of this communication.
Pooled independent sampling. This is the one-round analogue of Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks: each site keeps each point independently with a common probability and scales by its inverse. It is the strongest competitor in theory because its total cost does not grow with $k$, so it must win once $k$ exceeds $1/(\varepsilon D)^2$. It gets the same total communication budget as our method and is averaged over the same random partitions. Beating it means lower maximum query error at equal total points, over a range of $k$ whose upper end matches the predicted crossover.
Deterministic discrepancy halving. This is the key ablation. It is identical to our method, including the same coloring routine, buffer sizes and running time, except that the coin flip is removed. It is also the natural distributed version of FCore or herding-style compression. It isolates the single ingredient we claim matters. The win condition is that, at fixed per-site budget and fixed $N$, its error stays flat as $k$ grows while the sign-flipped version's error falls roughly like $1/\sqrt{k}$.
Linear sketch. We use a mergeable RACE-style sketch from One-Pass Distribution Sketch for Measuring Data Heterogeneity in Federated Learning, with its $R\times B$ table sized to the same number of transmitted words. We tune it on a held-out partition, with a grid search equal in cost to our method's choice of coloring routine.
Per-axis random compaction. Each attribute is summarized separately with one-dimensional random-offset halving, which is the known quantile trick. This shows what is lost by ignoring joint structure.
Reported numbers. No reported result was found on Lacuna for multi-site estimation of two-dimensional range counts under any of these methods. The closest reported number is centralized: on $4000\times4000$ corner and halfspace matrices, the hereditary minimizer gave colorings "roughly 10 times smaller than a single random sample and 4 times smaller than multiple random samples run for the same duration" (Fast Discrepancy Minimization with Hereditary Guarantees). Our first check is whether a gap of that order survives after aggregation over $k$ sites.
Why not just…?
Why not just use independent sampling, which is already optimal for counts? For a single count it is, and our method offers nothing there because one number has trivial discrepancy. For a class of joint range queries, sampling pays about $1/\varepsilon^2$ total regardless of how structured the queries are. The centralized gap reported in Fast Discrepancy Minimization with Hereditary Guarantees indicates structure is being left unused. Sampling remains a real threat at large $k$, and our own bound says it wins past $k\approx 1/(\varepsilon D)^2$. The $k$ sweep in the experiments is designed to locate that crossover empirically rather than hide it.
Why not just run the deterministic discrepancy compressor at each site, which is more accurate per site and harder to attack? Its per-site errors have a fixed sign pattern determined by the data. When sites hold similar data, those patterns align and the server's error is the sum, not the root-sum-of-squares. The ablation measures exactly this. If deterministic halving matched the sign-flipped version on real non-IID partitions, for example because heterogeneous sites happen to produce uncorrelated errors, the coin would be unnecessary. We would then report that and reframe the work around Gap 3.
Why not just use a mergeable linear sketch? Sketches merge exactly and cost constant time per item. However, one sketch answers range families only through hierarchical constructions whose size grows with the domain. Benchmarking Data Heterogeneity Evaluation Approaches for Personalized Federated Learning also reports that sketch-based methods degrade when several skews coexist. We include RACE at matched words rather than argue the point.
Why not just apply the known one-dimensional random compactor to each attribute? In one dimension our method essentially is that compactor, so there is no novelty there. A product of per-axis summaries cannot answer joint dominance or halfplane queries accurately, and the per-axis baseline quantifies how badly.
Proposed Experiments
Synthetic structured sets. We use the synthetic corner and halfspace point sets from Fast Discrepancy Minimization with Hereditary Guarantees, with $N$ up to $10^6$. Points are split across $k\in\{4,16,64,256,1024\}$ sites, either uniformly or with Dirichlet-skewed proportions. The metric is maximum and mean absolute error, divided by $N$, over all dominance ranges (or all halfplanes, by a sampled net), plotted against total transmitted points.
Real tabular data. We use pairs of numeric attributes from adult and covtype, partitioned with the label, feature and quantity skews of DH-Benchmark. Quantity skew directly tests the $\sqrt{\sum n_i^2}$ prediction and the $s_i\propto n_i^{2/3}$ allocation.
One-dimensional negative control. Single-word frequencies on Reddit comments and Sentiment140, partitioned as in Privacy-Preserving Federated Heavy Hitter Analytics for Non-IID Data, serve as a negative control. Here the sign-flipped method should coincide with randomized rounding, and any apparent gain would signal a bug.
Decisive checks. Three outcomes would settle the claims:
- Slope test. At fixed $N$ and fixed per-site budget $s$, a log-log plot of error against $k$ should show the deterministic ablation flat, the sign-flipped method with slope near $-1/2$, and sampling at a level set by $1/\sqrt{ks}$. If the sign-flipped slope is flat, the central claim is false.
- Crossover test. The measured crossover with sampling should track $k\approx 1/(\varepsilon D)^2$ as $\varepsilon$ varies.
- Robustness test (Stage 3). We run the uniform and adaptive-attack streams of A Simple and Robust Protocol for Distributed Counting against a tracking prototype and report whether error grows under attack, as it does for the randomized counting protocol there. We expect some leakage and treat its size, not its absence, as the result.
References
- Fast Discrepancy Minimization with Hereditary Guarantees
- Randomized algorithms for tracking distributed count, frequencies, and ranks
- Near-optimal Herding
- Streaming Covariate Balancing via Discrepancy-Based Feature Coresets
- Streaming Attention Approximation via Discrepancy Theory
- Simple and Optimal Algorithms for Heavy Hitters and Frequency Moments in Distributed Models
- A Simple and Robust Protocol for Distributed Counting
- Adversarially Robust Distributed Count Tracking via Partial Differential Privacy
- Spectral Sparsification by Deterministic Discrepancy Walk
- Near-Optimal, Distributed Edge Colouring via the Nibble Method
- One-Pass Distribution Sketch for Measuring Data Heterogeneity in Federated Learning
- Benchmarking Data Heterogeneity Evaluation Approaches for Personalized Federated Learning
- Privacy-Preserving Federated Heavy Hitter Analytics for Non-IID Data