Non-Adaptive 1-Bit Mean Estimation: Minimax Rates and the Sample-Interval Tradeoff

1 Introduction

• Lau and Scarlett's two-stage adaptive estimator first localizes the mean, then uses the resulting center to choose refinement queries; whether this interaction was necessary remained open.The paper answers that question negatively by fixing localization and refinement queries before observing responses.Source: §1 · p. 1

1.1 Problem Setup

• The learner estimates the mean from one bit per independent sample, with queries chosen using known model parameters and target accuracy.The distribution class requires no density, symmetry, or bounded-support assumption.Source: §1.1 · pp. 2–3

1.2 Summary of Contributions

• For every k > 1, i.i.d. non-adaptive queries match the adaptive 1-bit minimax sample complexity, and each realized one-set is a finite union of intervals.The construction retains localization–refinement but moves the center's role from query selection to decoding.Source: §1.2 · p. 3
• Matching upper and lower bounds characterize non-adaptive minimax sample complexity for every interval budget s; Corollary 3 gives the minimum budget preserving the unrestricted rate.The interval restriction adds a sample-complexity term, and the upper bound can be attained with i.i.d. queries.Source: §1.2 · p. 3

1.3 Prior and Concurrent Work

• Concurrent work also answered the non-adaptivity question; the paper's decoder follows Lau and Scarlett's centered refinement strategy, while the concurrent approaches use different refinements.As formulated, concurrent refinement constructions may have infinitely many interval components, unlike this construction's finite unions.Source: §1.3 · p. 4

2 A Minimax-Optimal Non-Adaptive Estimator

• Across all three parameter regimes, the non-adaptive estimator matches the adaptive 1-bit minimax sample complexity up to k-dependent constants and uses O(λ/σ) intervals per query one-set.Theorem 1 gives an (ε, δ)-PAC estimator over P(k, λ, σ); its queries are i.i.d., and all are fixed before responses are observed.Source: §2 · p. 5

2.1 Localization

• Localization returns a center within 8σ of the mean with probability at least 1−δloc using O(log(λ/σ) + log(1/δloc)) non-adaptive i.i.d. queries, each with O(λ/σ) intervals.The k-th central-moment assumption implies the first-moment bound needed for localization.Source: §2.1 · p. 6

2.2 Known-Center Refinement of Lau and Scarlett (2026b)

• The known-center refinement estimates dyadic cell contributions without bias, while its variance decreases with the probability that an observation reaches the cell’s distance from c.This tail-local variance, together with the first-moment identity, enables the order-optimal sample allocation of Lau and Scarlett (2026b).Source: §2.2 · p. 7

2.3 Three Obstacles for Non-Adaptive Queries

• Non-adaptive refinement must account for unknown cells, interference among bank-wide query responses, and near-center intervals that can destroy tail-local variance.The construction banks every potentially selected cell, uses independent Rademacher signs to isolate selected-cell contributions in expectation, and filters and reweights responses to restore tail-local variance while preserving the first-moment identity.Source: §2.3 · pp. 7–8

2.4 The Fixed Refinement Queries

• Fixed nested dyadic grids and finite cell banks cover every potentially selected refinement cell, keeping each query one-set to O(λ/σ) intervals.A query uses a shared random split and includes candidate subintervals from bank cells with positive signs; the finite bank preserves the statistical identities while bounding interval complexity.Source: §2.4 · pp. 8–9

2.5 Decoding After Localization

• After localization, the decoder selects a disjoint cover of the truncation window from prequeried banks, isolates selected-cell estimates using stored signs, and filters near-center responses.These decoder-only operations recover unbiased selected-cell contributions and restore tail-local variance without changing any query.Source: §2.5 · pp. 10–11
• For scales i≥2, the decoder discards responses whose queries include a candidate interval within ℓi of the center, then inverse-probability reweights retained responses to preserve the first moment and restore tail locality.The retention probability is at least 1/8; filtering is decoder-side, so the queries remain non-adaptive, and the finest scale needs no filter.Source: §2.5 · p. 13

2.6 Performance Guarantee and Sample Complexity

• For each scale, repetition, and orientation, the decoded variables satisfy a first-moment identity and tail-local variance bound, with τ1(c)=1 and τi(c)=Pr(|X−c|≥ℓi) for i≥2.These per-scale properties underpin the multiscale analysis yielding the theorem’s sample bound.Source: §2.6 · p. 13
• Median amplification of independently repeated base estimates combines localization and refinement failure probabilities to give a final (ε, δ)-PAC estimate.The protocol sets δloc=δref=δ/2 and uses O(log(1/δref)) repetitions.Source: §2.6 · p. 15
• For k>2, k=2, and 1<k<2, refinement queries are dominated by the finest scale, shared across O(log(σ/ε)) scales, and dominated by the coarsest scale, respectively.Median amplification multiplies the refinement terms by O(log(1/δ)); localization adds O(log(λ/σ) + log(1/δ)) queries, whose confidence term is absorbed because ε < σ.Source: §2.6 · p. 15

The Sample–Interval Tradeoff

• (λσ/(sε^2)) log(1/δ) is the additional sample cost of the s-interval restriction, up to k-dependent constants.The unrestricted terms are the localization and refinement costs; increasing s reduces the additional cost until it is absorbed by the unrestricted rate.Source: §3 · p. 16
• Corollary 3 identifies, up to k-dependent constants, the minimum interval budget needed to retain the unrestricted 1-bit sample rate.The corollary defines the unrestricted minimax sample complexity and compares it with non-adaptive estimators whose queries have bounded interval complexity.Source: §3 · p. 16
• An s-interval query can separate at most 2s pairs in the hard family, yielding the interval-dependent lower-bound argument.The family places point-mass pairs at locations with disjoint support segments, and separating each pair requires a boundary point in its segment.Source: §3 · p. 16
• For refinement, grouping cells into groups of at most s produces s-interval queries while preserving the original first-moment target and tail-local variance analysis.The resulting refinement sample cost is O_k(R_k(σ/ε, δ) + (λσ/(sε^2)) log(1/δ)).Source: §3 · p. 17
• For localization, the construction uses block-index and within-block offset queries across three shifted partitions to avoid instability near block boundaries.The decoder combines the recovered block index and offset, then takes the median of three reconstructions; at least two shifts place each mean safely inside a block.Source: §3 · p. 17

Conclusion

• For every k > 1, a non-adaptive estimator with i.i.d. queries attains the adaptive 1-bit minimax sample rate in the relevant parameter regimes.All queries are fixed before responses arrive; only the decoder waits for localization output before interpreting refinement bits.Source: §4 · p. 17
• The interval constraint adds (λσ/(sε^2)) log(1/δ) samples relative to unrestricted non-adaptive querying, up to stated constants, and Corollary 3 gives the interval budget that preserves the unrestricted rate.Fully sequential querying attains the unrestricted rate with threshold queries; the stated penalty comes from combining non-adaptivity with a limited interval budget.Source: §4 · p. 17
• Open problems include unknown (σ, ε), multivariate settings, and a more general tradeoff among samples, intervals, and rounds of adaptivity.The paper also identifies understanding when adaptivity helps under quantization in other statistical problems as a broader direction.Source: §4 · p. 17

Declaration of AI Usage

• AI models assisted with exploring mathematical arguments, drafting intermediate proof sketches, and planning and drafting exposition; the authors checked and revised the output and take responsibility for the manuscript.The authors report that some final-analysis ideas, including Rademacher-sign averaging, arose from this exploration.Source: Declaration of AI Usage · p. 18

A Finite-Union Localization (Lemma 1)

• Sampling code coordinates independently with replacement makes the localization queries i.i.d., and expressing coordinate queries as unions of bins makes their interval structure explicit.Using bins of width 5σ, the decoded bin is the true bin or a neighbor with probability at least 1 − δ_loc, giving error below 8σ.Source: A Finite-Union Localization (Lemma 1) · p. 21

A.1 Nearly Equidistant Codebook

• For K codewords and fixed ξ, a binary codebook with d_code = O_ξ(log K) coordinates exists with the stated near-equidistance property.The proof draws codewords independently and uniformly, then uses Hoeffding’s inequality and a union bound to establish existence.Source: §A.1 · p. 21

A.2 Finite-Union Localization with an 8σ Guarantee

• The construction’s boundary guard keeps the true bin and its two neighbors interior bins, including when μ is at an endpoint.The guard adds only O(1) bins.Source: §A.2 · p. 22
• A true-bin neighbor has a lower population disagreement score than every bin outside the true bin and its two neighbors.The decoder chooses the candidate with the smallest empirical disagreement score.Source: §A.2 · pp. 21, 23
• With probability at least 1 − δloc, decoding selects one of the true bin’s neighbors, yielding a center within 8σ of μ.The decoder returns the selected bin’s midpoint, projected onto [−λ, λ].Source: §A.2 · p. 23

B Geometry and Moment Identities for the Refinement Construction (Section 2)

• The refinement construction combines interval bounds, cover and filter geometry, and stochastic-quantization and random-sign identities to establish first-moment and tail-local variance properties.Source: B Geometry and Moment Identities for… · p. 24

B.1 Interval Bound for Refinement Queries

• Every refinement query’s one-set is a union of O(λ/σ) intervals.The bound follows from the number of cells in each refinement query bank.Source: §B.1 · p. 24

B.2 Geometry of the Decoder-Chosen Cover (Lemma 2)

• The decoder-selected cover has at most nine cells per scale, and its distinct cells are disjoint.The cover also covers the interval [c − r, c + r].Source: §B.2 · pp. 24–25

B.3 Properties of the Near-Center Filter

• The near-center filter contains at most three cells, is disjoint from the selected cover, and a retained positive response at scales i ≥ 2 certifies a tail event.Its retention probability is at least 1/8.Source: §B.3 · pp. 25–26

• Filtered random-sign decoding preserves the provisional decoder’s expectation over signs and makes the final decoder zero on filter cells.The construction applies the identity with the decoder-selected cover and near-center filter.Source: §B.4 · pp. 26–27
• Combining the quantization identity, filtered decoding, and cover and filter geometry yields the per-scale first-moment identity and tail-local variance bound.Source: §B.4 · pp. 26, 29, 31
• Cell-wise stochastic quantization recovers the contribution of a cell in expectation when the split points are uniform and independent of the observation.The identity applies to each interval cell and then integrates over the observation.Source: §B.4 · p. 27

C Proof of the Minimax Upper Bound (Theorem 1)

• The proof assumes a localization output c with |c − μ| ≤ 8σ and bounds refinement uniformly over such centers.Localization and refinement use disjoint samples and independent randomness.Source: C Proof of the Minimax Upper Bound… · p. 31

C.1 Conditional Mean and Truncation Bias

• The conditional-mean analysis compares the base refinement estimate with the residual μ − c using the first-moment identity and the transferred moment bound.Source: §C.1 · p. 32

C.2 Variance Aggregation Across Scales

• The scale allocation reduces the variance bound to a dyadic tail sum, which the transferred k-th moment bound controls.The resulting variance is at most a constant multiple of ε^2 when C1 is sufficiently large.Source: §C.2 · pp. 32–33

C.3 Accuracy and Confidence Amplification

• A base refinement block succeeds with constant probability; taking the median of independent blocks amplifies this to the target confidence.The proof then combines refinement and localization failure probabilities.Source: §C.3 · p. 34

C.4 Sample Complexity

• For 1 < k < 2, the final scale dominates the geometric refinement-sample sum.The first scale dominates when k > 2, while all scales contribute equally when k = 2.Source: §C.4 · p. 35
• The localization-confidence term is absorbed by every refinement term because σ/ε > 1, giving the total order stated in Theorem 1.Source: §C.4 · p. 35
• The protocol uses independent queries with type-dependent laws, and an i.i.d. query law can be obtained without changing the sample order or interval bound.Every query one-set is a union of O(λ/σ) intervals.Source: §C.4 · p. 35

D Proof of the Sample–Interval Tradeoff (Theorem 2)

• The lower bound combines the unrestricted lower bound with an extension of the adaptivity-gap argument from one interval to s intervals per query.The extension is developed in Appendix D.1.Source: D Proof of the Sample–Interval… · p. 35
• The upper bound groups refinement query banks into sets of at most s cells and redesigns localization to respect the same interval restriction.Appendix D.4 combines the resulting sample counts.Source: D Proof of the Sample–Interval… · p. 36
• Appendix E converts the prescribed localization and refinement families into a single i.i.d. query law.The proof uses the convention that logarithmic factors in upper-bound rates are at least one.Source: D Proof of the Sample–Interval… · pp. 35–36

D.1 Interval-Dependent Lower Bound

• For any fixed s-interval query, its one-set has at most 2s finite boundary points, so it is informative for at most 2s hard locations among pairwise-disjoint segments.Source: §D.1 · p. 36
• For δ bounded away from zero, the testing argument gives n = Ω(Nσ^2/(sε^2)); the unrestricted lower bound supplies the localization and refinement terms.Combining these bounds proves the lower side of the sample-complexity result.Source: §D.1 · pp. 36–37

D.2 Grouped Refinement under the Interval Budget

• The refinement construction partitions each scale's fixed query bank into groups of at most s cells and uses independent query randomness and observations across groups.After localization, the decoder restricts the selected cover and filter to each group.Source: §D.2 · pp. 37–38
• The only sample-count change is that each scale replicate uses one observation per group and orientation.The group count therefore enters the query budget without changing the required moment bounds.Source: §D.2 · pp. 38, 40
• Grouping preserves the per-scale first-moment identity and tail-local variance bound, so the original bias, variance, scale-allocation, and amplification analyses still apply.The first-moment targets partition the original target, and independent group variances add.Source: §D.2 · pp. 37, 40

D.3 s-Interval Localization

• Directly grouping the coding localizer would multiply its additive log(λ/σ) coding cost by the number of groups, so the block-and-offset construction avoids that dependence.The direct grouping factor is G = O(max{1, λ/(sσ)}).Source: §D.3 · p. 41
• For s ≤ 8, independent uniform-threshold queries localize the mean using O((λ/σ)·log(1/δloc)) samples.The threshold responses agree with the ideal comparison with probability at least 3/4 outside a 4σ margin.Source: §D.3 · p. 41
• For s > 8, three shifted partitions use block width L = Θ(max{σ, λ/s}); each estimates the mean by recovering its block and within-block offset.Offset queries reuse one random threshold across the retained blocks, while block-index queries use sampled code coordinates.Source: §D.3 · p. 41, Figure 4 · p. 42
• Because the three boundary phases are separated by L/3, at least two partitions are safe for every mean.A safe partition places the mean at least L/6 from every block boundary.Source: §D.3 · pp. 41, 44
• For each safe partition, offset recovery is accurate within 8σ and block-index recovery identifies the true block; taking the median of the shifted estimates preserves the 8σ error bound.The protocol unions the failure probabilities across recovery procedures to obtain the localization guarantee.Source: §D.3 · pp. 44, 46
• The localizer returns a center c within 8σ of μ with probability at least 1 − δloc, while every realized query one-set has at most s interval components.The guarantee holds uniformly over distributions with μ ∈ [−λ, λ] and E[|X − μ|] ≤ σ.Source: §D.3 · pp. 40, 46

D.4 Sample Complexity and Completion of Theorem 2

• The proof sums the grouped-refinement budget across scales and adds the s-interval localization cost.It applies median amplification to independent grouped base blocks.Source: §D.4 · pp. 47–48
• Grouping changes only the refinement query count: at scale i, the cost is multiplied by the number of groups Gi.The grouped first-moment and tail-local second-moment bounds allow the bias, variance, and amplification arguments to apply unchanged.Source: §D.4 · p. 47
• Converting the prescribed independent query families to a single i.i.d. query law preserves the sample order and the s-interval constraint, completing the upper bound and Theorem 2.Together with the established lower bound, this proves the stated minimax result.Source: §D.4 · p. 48

D.5 Proof of the Random-Threshold Localization (Lemma 10)

• Candidates beyond u+2h disagree more often than u+h with high probability, because the comparison interval contains a length-h region with expected nh/L sampled thresholds.The analogous comparison with u−h rules out candidates below u−2h.Source: §D.5 · p. 49

E i.i.d. Query Conversion (Theorems 1 and 2)

• The query-allocation conversion mixes refinement and localization laws, then mixes both branches in proportion to their sample budgets.For s>8, localization uses up to six query families; for s≤8 it uses a single random-threshold law.Source: E i.i.d. Query Conversion (Theorems 1… · p. 52

E.1 Randomizing Additive Refinement Roles

• Randomized refinement types are reweighted by their type probabilities, preserving the prescribed block’s mean and variance bound without requiring realized type counts to match prescribed counts.The result applies conditionally on a transcript and to ungrouped or grouped refinement types.Source: §E.1 · pp. 52–54

E.2 i.i.d. Conversion of the s-Interval Localizer

• For s>8, mixing the localization-family laws and retaining each family’s required responses yields an i.i.d. s-interval localizer.Its decoder returns c with |c−µ|≤8σ with probability at least 1−δloc; the s≤8 construction already uses i.i.d. random-threshold queries.Source: §E.2 · pp. 54–55

E.3 The Global i.i.d. Query Law

• The i.i.d. conversion preserves Btot’s order and O(λ/σ) interval components per refinement or localization query, proving Theorem 1’s i.i.d. assertion; the construction also proves Theorem 2’s i.i.d. assertion and Corollary 3’s achievability.Source: §E.3 · pp. 57–58

F Further Related Work

• The related-work discussion compares refinement constructions and VALG theorem candidates by how they recover the residual mean and obtain scale-wise tail-dependent second-moment bounds.It retains cited papers’ terminology only when it marks a substantive difference.Source: F Further Related Work · p. 58

F.1 Prior Work

• Prior work spans finite-moment high-probability mean estimation, communication-constrained estimation, interaction, and distributed empirical-mean estimation, which targets a different quantity from the population mean.The empirical-mean literature measures error against the fixed vectors’ arithmetic average.Source: §F.1 · p. 59

F.2 Summary of Comparisons with Concurrent Work

• All four non-adaptive protocols share the outer architecture and coding-based localization strategy, so their main methodological differences lie in refinement.The paper says its closer conceptual connection to Lau and Scarlett’s cell-contribution strategy is not necessarily an advantage.Source: §F.2 · pp. 59–60, Table 2 · p. 60

F.3 Comparison with Miao (2026)

• Miao’s dyadic-offset construction telescopes changes in within-cell offsets, while its signed-grid construction averages neighboring-cell contributions over random shifts and widths.Both filter and reweight advance-collected refinement responses after decoding c, but reconstruct different quantities from this paper’s cell-based estimates.Source: §F.3 · p. 61

F.4 Comparison with Hu and Zhong (2026)

• Hu and Zhong estimate E[gi(X−c)] at each scale using the block containing c, then sum across scales; this paper instead estimates contributions from decoder-selected cells.Their boundary filtering supports both reconstruction and the second-moment bound, whereas this paper’s candidate-interval filtering is used for second-moment control.Source: §F.4 · pp. 61–62