Ivan Lau, Jonathan Scarlett
7 min
This paper tackles a core challenge in statistics and machine learning: estimating the mean of a distribution when you're stuck with extremely limited feedback—just 1 bit per sample. Imagine you're trying to find the average willingness-to-pay of buyers, but you can only ask 'Is it above this price?' and get a yes/no. Or in sensor networks where raw data can't be sent due to bandwidth limits. The authors, Ivan Lau and Jonathan Scarlett, develop an adaptive estimator using randomized threshold queries that achieves the best possible sample efficiency (order-optimal) across a wide range of distribution 'tail regimes'—from light-tailed (like Gaussians) to heavy-tailed ones with massive outliers.
The key innovation is handling general tail regimes defined by bounded k-th central moments for any k > 1. This covers sub-Gaussian (k≥2), sub-exponential, and even heavy-tailed cases (1<k<2) where traditional methods fail because you can't see outlier magnitudes.
Instead of getting full sample values, the learner picks a threshold γ and gets a 1-bit response: 1 if the sample X ≥ γ, 0 otherwise. This is simpler than interval queries (which need two thresholds) and practical for real-world apps like pricing or bio-assays.
The catch? If you guess the wrong region (e.g., mean μ is in [-λ, λ] but you query far away), you get uninformative all-0s or all-1s. Heavy tails make it worse: rare huge outliers could mislead without magnitude info. The paper's estimator uses adaptivity—thresholds chosen based on prior responses—to efficiently 'search' for the distribution's core.
The algorithm has two phases:
This is ε,δ-PAC: returns ˆμ with |ˆμ - μ| ≤ ε w.p. ≥1-δ. Variants handle unknown budgets, unknown σ (with loose bounds), and even reduce to two-stage adaptivity.
Distributions in family D(k,λ,σ): E|X - μ|≤λ, E|X - μ|^k ≤ σ^k (k>1). Sample complexity Õ(σ^k / ε^2) for k≠2, matching unquantized lower bounds + localization cost. For k=2 (finite variance), extra Õ(log(σ/ε)) factor, proved information-theoretically necessary due to 1-bit limits—your first proof of this penalty.
Adaptivity gap: Non-adaptive needs Θ(λ/σ * σ^2/ε^2), exponentially worse.
Improves prior work: extends to heavy tails (1<k<2), eliminates suboptimal logs, uses simpler thresholds. Bridges theory (minimax optimality) and practice (1-bit comms in federated learning, sensors). Shows 1-bit quantization doesn't ruin mean estimation—if you're adaptive.
| Tail Regime | Unquantized Lower Bound | This Paper (1-bit Adaptive) | Non-Adaptive | |-------------|--------------------------|-----------------------------|--------------| | k ≠ 2 | Θ(σ^k / ε^2) | Õ(σ^k / ε^2) | Θ(λ/σ * ...) | | k = 2 | Θ(σ^2 / ε^2) | Õ(σ^2 / ε^2 log(σ/ε)) | Θ(λ/σ * ...) |
In this paper, we study the problem of mean estimation under strict 1-bit communication constraints. We propose a novel adaptive mean estimator based solely on randomized threshold queries, where each 1-bit outcome indicates whether a given sample exceeds a sequentially chosen threshold. Our estimator is $(ε, δ)$-PAC for any distribution with a bounded mean $μ\in [-λ, λ]$ and a bounded $k$-th central moment $\mathbb{E}[|X-μ|^k] \le σ^k$ for any fixed $k > 1$. Crucially, our sample complexity is order-optimal in all such tail regimes, i.e., for every such $k$ value. For $k \neq 2$, our estimator's sample complexity matches the unquantized minimax lower bounds plus an unavoidable $O(\log(λ/σ))$ localization cost. For the finite-variance case ($k=2$), our estimator's sample complexity has an extra multiplicative $O(\log(σ/ε))$ penalty, and we establish a novel information-theoretic lower bound showing that this penalty is a fundamental limit of 1-bit quantization. We also establish a significant adaptivity gap: for both threshold queries and more general interval queries, the sample complexity of any non-adaptive estimator must scale linearly with the search space parameter $λ/σ$, rendering it vastly less sample efficient than our adaptive approach. Finally, we present algorithmic variants that (i) handle an unknown sampling budget, (ii) adapt to an unknown scale parameter~$σ$ given (possibly loose) bounds, and (iii) require only two stages of adaptivity at the expense of more complicated general 1-bit queries.
Alex: That log penalty seems inevitable from one-bit limits.
Alex: What if sample budget isn't fixed upfront, like in apps with dropping connections?
Sam: They have an "anytime" version. Localize once, then run refinement rounds, each halving target error and adjusting failure odds. Stop anytime; last complete estimate matches fixed-budget up to small log factor, since later rounds dominate samples.
Alex: Like sharpening a sketch progressively until time runs out.
Sam: Exactly. For unknown sigma, guess from max down by halves. Run estimator targeting error proportional to guess, build confidence intervals. Stop at first non-overlapping with prior—total samples log of bound range times base.
Alex: Adapts without true spread knowledge.
Sam: Yes. For fewer rounds, two-stage: non-adaptive localization splits space into equal bins, estimates mean bin bits via Gray code—one bit flip between neighbors, majority vote. Then refine—slightly more samples, simpler.
Alex: And higher dimensions?
Sam: Per coordinate with tighter error; l2 accuracy, but samples scale d squared over epsilon squared—unavoidable under one bit per sample. One bit per coordinate improves. Joint covariance left open.
Alex: Solid extensions.
Alex: How do they ensure reliability across runs?
Sam: Repeat base process log(1/delta) times independently, take median. This median-of-means gives (epsilon, delta)-PAC: close to true mean with probability 1-delta. Base spread controlled by strip samples; each error bounded via tail probabilities from k-moment.
Alex: Sample scaling keeps total wobble small for median to work?
Sam: Yes. Variance per strip is width squared times tail prob over samples. Allocate inversely—more to riskier strips—sums variances to epsilon squared over constant. Chebyshev bounds base error under epsilon/2 with failure under 1/2; median cleans up.
Alex: Matches minimal needs?
Sam: Yes, hits known lower bounds from quantized estimation work. For k not 2, exact minimax; variance cases, log penalty unavoidable with one-bit.
Alex: Precise design tied to limits.
Alex: Why does that specific scaling—more samples outward via 2^i (2-k)—sum errors neatly?
Sam: Total variance is double sum over strips and probs. Inner strips near zero: bound by min samples times sigma squared. Outer: link probs to k-moment; exponential widths and decay control it. n_i proportional to sigma^2/epsilon^2 * 2^i (2-k) makes each contribution epsilon^2 over strips so far—geometric series. Weighted tails yield O(epsilon^2). Samples sum geometric S_k up to log(t/sigma): constant for k>2, log for k=2, (sigma/epsilon)^{k/(k-1)} / (2-k) for 1<k<2—all matching bounds plus logs.
Alex: Fights growing widths and decaying probs perfectly.
Alex: Overall, tight sample use across tails.
Sam: Core advance: matches minimal needs up to unavoidable logs.
Alex: Main limits?
Sam: Assumes known k, sigma, epsilon, lambda. Extensions handle unknown epsilon/sigma via doubling, but fully parameter-free open. Constants grow as k nears 2 from below. High-d quadratic in d under one-bit per sample.
Alex: Assumptions tighten proofs; real data may need extras.
Sam: Yes. Fits IoT or swarm robotics: one-bit federated averages from yes-no, like auctions or sensor drifts, with parameter-free tweaks.
Alex: Meaningful for constrained settings.
Sam: Advances one-bit rigor, proves adaptivity key, delivers matching schemes.
Alex: Well said, Sam. Thanks for breaking it down so clearly. Thanks for listening to ResearchPod.