acceptodds
Under review as a conference paper at ICLR 2027

Interaction Is Not Necessary for Order-Optimal 1-Bit Mean Estimation

Abstract

This paper is concerned with one-bit mean estimation, where each independent sample is represented by a single binary message. We consider distributions on with mean in and absolute -th central moment at most , where is fixed. For this class, previous work attained the optimal sample complexity for general queries using a two-stage protocol. The first stage localizes the mean. The second-stage queries are chosen after localization and refine the estimate around the decoded center. We show that this interaction can be avoided by constructing a randomized fully non-adaptive protocol that fixes all queries before observing the data and matches the optimal adaptive sample complexity. For target accuracy and confidence , its sample complexity scales as up to constants depending only on . In the range covered by the known lower bound, this rate is minimax optimal even among fully adaptive protocols. This gives a negative answer to the COLT 2026 open problem asking whether interaction is necessary for order-optimal one-bit mean estimation with general queries \citep[Open Problem 1]lau2026open.

Primary area:
learning theory
Keywords:
One-bit mean estimation, non-interactive protocols, optimal sample complexity

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_FJphOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper considers the problem of estimating the mean of a random variable from one-bit queries. The paper follows a two-step procedure by Lau and Scarlett that achieves optimal rate. In this procedure, first, the mean is localized, and second, adaptive queries are used for refinement. It was left open whether the second stage could be made non-adaptive. The main contribution of the paper is a positive answer to this question. Concretely, under nonparametric moment assumptions on the distribution, the optimal sample complexity is determined. The main technical contribution is Lemma 3.2, which provides an unbiased estimator with controlled variance for the estimation error after the first step (localization).

Critical strengths

The paper solves a problem left open and such that was considered challenging in a serious of papers by Lau and Scarlett (which has been concurrently solved by them, and in another paper).

Critical weaknesses
  1. Overall, the paper contribution is limited, in the sense that it has a single result, and most of the steps follow standard procedures.

  2. Given that this is the contribution, I would hope for a much clearer presentation. Currently, it is possible that the paper would be clear to those who have actively worked on this problem, but not to a more general audience. My problem starts with the refinement section on line 151 and onward. At this point, it is very unclear what is a block-sign, what is a replicate that the decoder uses, what is the function Zg(s)Z_g(s), why it is required that the derivative of gg is defined on a complex plane, and so on. In general, the explanations that precedes the formal constructions are unclear, and the constructions themselves are not intuitive to me. The idea of using blocks with different randomized signs and shift is presented as natural (line 230), but the idea is not explained.

Questions for authors
  1. How does blocking allows to obtain a refined error estimate even for a single scale?

  2. In the multiscale reconstruction, the scale parameters sis_i increase. Why this make sense? Moreover, larger scales use more samples, so doesn't it mean that the variance of each scale is equalized? I am looking for an intuitive explanation on why the multiscale reconstruction is necessary.

  3. The rate in Theorem 1.1 is stated up to constants that depend on the moment order kk. Are there any guarantees on their values? For example, that they are not exponential in kk ?

6 comments
AuthorsOpenReview ↗

Response to Reviewer FJph (1/2)

We sincerely thank you for your careful review and constructive feedback. We have revised the paper according to your suggestions (please see the Common Response above for an overview of the revision). Please let us know if you have any further concerns. If our responses address your concerns, we would greatly appreciate it if you could reconsider your rating.

W1. Lack of technical contributions

Overall, the paper contribution is limited, in the sense that it has a single result, and most of the steps follow standard procedures.

Although we follow the localization–refinement framework of prior work, our contribution is a center-independent refinement construction. It combines randomly shifted blocks, sign cancellation, and a centering correction to obtain exactly conditionally unbiased component estimates with tail-dependent variance bounds (Lemma 3.2). These properties enable the optimal fully non-adaptive rate under only a finite-moment assumption, for each fixed k>1k>1.

W2. Clarity of the refinement construction and notation

Given that this is the contribution, I would hope for a much clearer presentation. ... My problem starts with the refinement section on line 151 and onward.

Thank you for raising this issue. We have expanded the refinement discussion beginning at line 151 of the original submission, with the revised explanation marked in red in Section 2.

At this point, it is very unclear what is a block-sign,

A block sign is a public random value in −1,+1\\{-1,+1\\} assigned to a spatial block. The decoded sign A0A_0 equals one when its observation lies in the selected block containing CC, while contributions from other blocks have mean zero over the public signs.

what is a replicate that the decoder uses

A replicate uses two fresh, independent observations and a shared public seed to produce one decoded component estimate.

what is the function Zg(s)Z_g(s)

Zg(s)Z_g(s) (or Zg(C)Z_g(C) used in the paper) is the decoded statistic for a compactly supported component gg, with conditional expectation E[g(X−C)∣Floc]\mathbb E[g(X-C)\mid\mathcal F_{\mathrm{loc}}]. The decoder evaluates it at the recovered center CC and combines the component estimates across scales to form the final estimate.

why it is required that the derivative of gg is defined on a complex plane

The component g:R→Rg:\mathbb R\to\mathbb R is compactly supported and absolutely continuous, and g˙\dot g denotes its ordinary almost-everywhere derivative on the real line, not on a complex plane.

Q1. How does blocking give a refined estimate at a single scale?

Blocking is needed in our construction because the localization center CC is unknown when the refinement queries are fixed. It preassigns local intervals across the possible range of CC, allowing the decoder to select the block containing CC after localization. Random signs cancel contributions from other blocks in expectation, while the within-block threshold identity and safety correction yield an unbiased estimate of the expectation of the local component g(X−C)g(X-C), where gg is supported on [−2s,2s][-2s,2s]. In the adaptive setting, the local interval can instead be chosen after CC is known.

AuthorsOpenReview ↗

Response to Reviewer FJph (2/2)

Q2. Why do the scales increase, and does the allocation equalize their variances?

As explained in Section 2's red “Multiscale reconstruction” paragraph, increasing the terminal scale reduces truncation bias: conditional on successful localization, the single-scale construction for HSH_S, which equals the identity on [−S,S][-S,S] and vanishes outside [−2S,2S][-2S,2S], has a coarse variance bound O(S2)O(S^2) and an absolute bias bound s0κ/Sκ−1s_0^\kappa/S^{\kappa-1}, where κ=min⁡k,3\kappa=\min\\{k,3\\} and s0=64σs_0=64\sigma. For fixed k∈(1,2)k\in(1,2), fixed confidence, and ϵ<σ\epsilon<\sigma, choosing the smallest SS satisfying Sκ−1≥4s0κ/ϵS^{\kappa-1}\geq4s_0^\kappa/\epsilon and applying only this coarse variance bound gives a sufficient sample budget O(S2/ϵ2)=O((σ/ϵ)2k/(k−1))O(S^2/\epsilon^2)=O((\sigma/\epsilon)^{2k/(k-1)}), whose exponent exceeds that of the target rate O((σ/ϵ)k/(k−1))O((\sigma/\epsilon)^{k/(k-1)}).

We therefore write g0=Hs0g_0=H_{s_0} and gi=Hsi−Hsi−1g_i=H_{s_i}-H_{s_{i-1}} with si=2is0s_i=2^is_0, so the components sum to the desired truncation. Since g˙i\dot g_i vanishes near zero for i≥1i\ge1, Lemma 3.2 gives, conditional on successful localization with center cc, a single-replicate variance bound which is at most O(s0κsi2−κ)=O(σ22i(2−κ))O(s_0^\kappa s_i^{2-\kappa})=O(\sigma^2 2^{i(2-\kappa)}). The allocation Ni∝2i(2−κ)N_i\propto2^{i(2-\kappa)} approximately equalizes these coarse bounds after averaging. It increases with scale for 1<k<21<k<2, remains constant at k=2k=2, and decreases for k>2k>2, up to rounding.

Q3. What guarantees are available for the constants depending on kk?

Equation (1.1) now displays the following kk-dependent prefactors, up to a universal multiplicative constant.

For k>2k>2:

Ck=1+1k−2.C_k=1+\frac{1}{k-2}.

For k=2k=2:

Ck=1.C_k=1.

For 1<k<21 < k < 2:

Ck=C0(2−k)/(k−1)2−k.C_k=\frac{C_0^{(2-k)/(k-1)}}{2-k}.

Here C0C_0 is universal. The sample-complexity rates match the adaptive bounds [1] for each fixed kk, with no exponential dependency.

[1] Ivan Lau and Jonathan Scarlett. Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes.

Thanks for the explanations, and the update of the dependence on kk

Reviewer_j4hGOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies one-bit mean estimation. Each of nn i.i.d. samples from an unknown distribution PP on R\mathbb{R} is reduced to one binary message, and the goal is to estimate μP\mu_P. The class is Dk(λ,σ)\mathcal{D}_k(\lambda,\sigma): mean in [−λ,λ][-\lambda,\lambda] and EP∣X−μP∣k≤σk\mathbb{E}_P|X-\mu_P|^k \le \sigma^k for a fixed k>1k>1.

Lau & Scarlett (2026c) reached the optimal sample complexity with a two-stage protocol. The second-stage queries are placed around a center found in the first stage. Lau & Scarlett (2026b) then asked, as an open problem, whether general measurable queries fixed entirely in advance can reach the same rate.

This paper answers yes. It gives a randomized, fully non-adaptive protocol with sample complexity log⁡(λ/σ)+(σ/ϵ)2log⁡(1/δ)\log(\lambda/\sigma) + (\sigma/\epsilon)^2\log(1/\delta) for k>2k>2, log⁡(λ/σ)+(σ/ϵ)2log⁡(σ/ϵ)log⁡(1/δ)\log(\lambda/\sigma) + (\sigma/\epsilon)^2\log(\sigma/\epsilon)\log(1/\delta) for k=2k=2, and log⁡(λ/σ)+(σ/ϵ)k/(k−1)log⁡(1/δ)\log(\lambda/\sigma) + (\sigma/\epsilon)^{k/(k-1)}\log(1/\delta) for 1<k<21<k<2 (Theorem 1.1). This matches the adaptive lower bound when ϵ/σ\epsilon/\sigma and δ\delta are small enough.

The construction has four parts:

  • Localization: the non-adaptive localization step of Lau & Scarlett (2026c) is reused unchanged.
  • Fixed-scale refinement: pairs of queries are built that do not depend on the center. They use a randomly shifted block partition, a uniform threshold inside each block, and pairwise-independent block signs. Once the center is decoded, it selects one block, and the signs cancel the contribution of all other blocks in expectation. The result is an exactly unbiased estimate of E[g(X−C)]\mathbb{E}[g(X-C)], with a second moment controlled by a tail probability (Lemma 3.2).
  • Multiscale reconstruction: Lipschitz truncations at scales si=2is0s_i = 2^i s_0 are combined.
  • Amplification: a median of K=O(log⁡(1/δ))K = O(\log(1/\delta)) base estimators gives the confidence guarantee.

The paper is purely theoretical and has no experiments.

Critical strengths

S1. The paper answers a clearly posed open problem (Lau & Scarlett 2026b, Open Problem 1), and the answer is sharp. The protocol fixes every query before seeing any bit, yet matches the adaptive minimax rate in all three moment regimes. This shows that the adaptivity gap known for threshold and interval queries disappears once general measurable queries are allowed. For me this is a clean and interesting conceptual message about the role of interaction under communication constraints.

S2. The construction is elegant and the proof is complete and easy to check. The key idea is to put a threshold in every block, attach pairwise-independent random signs to the blocks, and add a second query carrying only the sign. With this, the decoder can use the center after all bits are collected and still get an exactly unbiased estimate. Remark 3.1 and Appendix C explain well why the random grid shift is needed, and Appendix D shows that only ⌈log⁡2(2Bs+2)⌉\lceil\log_2(2B_s+2)\rceil public bits are needed for the signs. I checked the main constants in Section 4 and they hold:

  • the variance bound 99840 ϵ2/222<ϵ2/3299840\,\epsilon^2/2^{22} < \epsilon^2/32;
  • the Chebyshev step giving 1/18<1/41/18 < 1/4;
  • the Hoeffding step giving e−K/8≤δ/2e^{-K/8} \le \delta/2.
Critical weaknesses

W1. The paper's place relative to concurrent work and to Lau & Scarlett (2026c) needs to be clearer. The authors say that Miao (2026) and Lau & Scarlett (2026a) independently obtained the same order-optimal non-adaptive rate. So the main contribution of this paper is a different construction, not the resolution of the open problem by itself. The related work gives only two sentences on how the constructions differ. Also, the localization stage is taken entirely from Lau & Scarlett (2026c), and the multiscale truncation idea follows similar steps in the adaptive literature. I would like a more explicit comparison with the two concurrent works: the constants, the amount of public randomness, the decoder complexity, and whether one construction extends more easily (for example to unknown σ\sigma or to higher dimensions). This would show what this construction adds.

W2. The result is only a rate in a narrow setting, with no numerical support, and its relevance to ML is not discussed. The constants are very large, for example Ni=⌈222s022i(2−κ)/ϵ2⌉N_i = \lceil 2^{22} s_0^2 2^{i(2-\kappa)}/\epsilon^2\rceil with s0=64σs_0 = 64\sigma, and a code length of at least 10000log⁡N10000\log N in localization. So the protocol is far from usable as written, and the paper contains no simulation, even a small one, comparing it with the two-stage adaptive protocol or with simple non-adaptive baselines at moderate ϵ\epsilon. The model also assumes:

  • that kk, λ\lambda and σ\sigma are known;
  • one scalar mean;
  • shared public randomness;
  • ϵ≤σ/2\epsilon \le \sigma/2.

The motivation (distributed or federated estimation) is mentioned only briefly, and the paper does not explain what the result means for learning problems that the ICLR audience cares about.

Questions for authors

Q1. This first question is the most important one for my assessment. How exactly does your construction differ from those of Miao (2026) and Lau & Scarlett (2026a)? Does it have better constants, need less public randomness, or have a simpler decoder? Is there something your construction can do that the others cannot?

Q2. The protocol relies on shared public randomness: the grid shift Θ\Theta, the offset WW and the signs η\eta. Can the same rate be reached with private randomness only, or with a fully deterministic protocol? Appendix C says that several precommitted deterministic shifts are not ruled out. Do you expect that to work?

Q3. The constants (2222^{22}, s0=64σs_0 = 64\sigma, 10000log⁡N10000\log N) are very large. Could you give a rough idea of the sample size needed in practice, or a small simulation comparing your protocol with the adaptive two-stage protocol of Lau & Scarlett (2026c)?

Q4. Can the construction be made adaptive to an unknown σ\sigma, or to an unknown moment order kk, without interaction? Cai & Wei (2022) show that interaction helps adaptation to unknown variance in the Gaussian case. Does a similar gap appear here?

Q5. Does the approach extend to dd-dimensional means, for example with one bit per sample for all coordinates, and what rate would you expect?

Q6. For k=2k=2 the rate has an extra log⁡(σ/ϵ)\log(\sigma/\epsilon) factor. Is it known that the adaptive lower bound also contains this factor for general queries, so that the claim of optimality covers k=2k=2 too? Could you state the exact range of (ϵ,δ)(\epsilon, \delta) in which the lower bound applies?

Minor:

  • The AI use statement says generative AI assisted "with some of the theoretical proofs". It would help to say which parts.
  • Proposition 2.1 is stated under the first-moment condition EP∣X−μP∣≤σ\mathbb{E}_P|X-\mu_P| \le \sigma. Please confirm that the cited Theorem 16 of Lau & Scarlett (2026c) holds under this condition, and not only for the class Dk\mathcal{D}_k.
5 comments
AuthorsOpenReview ↗

Response to Reviewer j4hG (1/3)

We sincerely thank you for your careful review and the constructive questions. We have provided a detailed explanation below and revised the paper in responses to your comments (please see the Common Response above for an overview of the revision). Please feel free to let us know if you have any additional concerns or questions.

Q1 / W1

Q1. This first question is the most important one for my assessment. How exactly does your construction differ from those of Miao (2026) and Lau & Scarlett (2026a)? Does it have better constants, need less public randomness, or have a simpler decoder? Is there something your construction can do that the others cannot?

We want to emphasize that our work was developed independently and concurrently with Miao (2026) and Lau and Scarlett (2026a), and that all three works resolve the open problem. We have clarified the technical differences in Appendix A. We do not claim better constants, less public randomness, or a simpler decoder; our distinction lies in the refinement primitive described below.

All three approaches use precollected bits to estimate the residual mean E[X−c]\mathbb E[X-c] for a decoded coarse center cc, where XX denotes a fresh observation. Miao (2026) gives two constructions. One estimates the difference between the within-cell positions of XX and cc and adds corrections between successive grid scales. The other averages signed neighboring-cell contributions over random grid shifts and widths. Lau and Scarlett (2026a) select cells from fixed multiscale grids after localization and sum estimates of each cell’s contribution to the residual mean. Our construction instead uses a multiscale decomposition of a truncated version of the residual X−cX-c. At each fixed scale, Lemma 3.2 provides an exactly conditionally unbiased estimator of E[g(X−c)]\mathbb E[g(X-c)] using one bit from each of two independent samples, where gg is a compactly supported component function satisfying the lemma’s conditions. The query maps depend on neither cc nor gg. Changing gg only changes a derivative weight at the decoder, allowing the same fixed-scale queries to support different admissible functions. For our higher-scale components, the decoded contribution vanishes when both observations are sufficiently close to cc, yielding the tail-dependent second-moment bound needed for the optimal rate.

Q2

Q2. The protocol relies on shared public randomness: the grid shift Θ\Theta, the offset WW and the signs η\eta. Can the same rate be reached with private randomness only, or with a fully deterministic protocol? Appendix C says that several precommitted deterministic shifts are not ruled out. Do you expect that to work?

We thank the reviewer for suggesting this direction. Our current construction relies on public randomness. Two precommitted deterministic shifts can replace the random grid shift, but the construction still requires shared random block signs RmR_m and the within-block threshold offset WW. We leave the question of achieving the same rate without public randomness to future work.

Q3 / W2

Q3. The constants (2222^{22}, s0=64σs_0=64\sigma, 10000log⁡N10000\log N) are very large. Could you give a rough idea of the sample size needed in practice, or a small simulation comparing your protocol with the adaptive two-stage protocol of Lau & Scarlett (2026c)?

According to our current analysis, Eq. (3.15) gives N0=⌈234(σ/ϵ)2⌉N_0=\lceil2^{34}(\sigma/\epsilon)^2\rceil query pairs at scale zero per base estimator. At ϵ=0.1σ\epsilon=0.1\sigma, this amounts to approximately 1.72×10121.72\times10^{12} pairs, or 3.44×10123.44\times10^{12} individual samples, at scale zero alone. However, we want to emphasize that this is a conservative theoretical budget. Our main focus is to establish that the optimal order of sample complexity is achievable in one communication round, without feedback after localization. We believe that more careful calculations and adjustments to the construction could reduce these constants. We leave this, together with an evaluation of practical performance, to future work.

AuthorsOpenReview ↗

Response to Reviewer j4hG (2/3)

Q4

Q4. Can the construction be made adaptive to an unknown σ\sigma, or to an unknown moment order kk, without interaction? Cai & Wei (2022) show that interaction helps adaptation to unknown variance in the Gaussian case. Does a similar gap appear here?

Our theorem assumes that kk and a valid moment bound σ\sigma are known. A conservative bound can be used, but the sample complexity depends on that bound. Cai and Wei (2022) show that interaction reduces the communication cost of adapting to unknown variance in Gaussian mean estimation. Although their communication model differs from ours, for any fixed kk, the kk-th centered-moment scale of a Gaussian distribution is proportional to its standard deviation. Their result therefore provides evidence that interaction can help adaptation to an unknown moment scale. We conjecture that interaction can also reduce the sample complexity of adaptation to an unknown moment scale under one-bit-per-sample communication. We leave a rigorous analysis of adaptation to an unknown moment scale or moment order kk to future work.

We have added the following discussion to the Conclusion:

Several interesting directions remain. Our analysis assumes that the moment order kk and a valid moment bound σ\sigma are known. A natural question is whether interaction remains unnecessary when adapting to unknown moment parameters. Cai and Wei (2022) show that interaction helps adaptation to unknown variance in Gaussian mean estimation. We conjecture that interaction can also reduce the sample complexity of adaptation to an unknown moment scale under one-bit-per-sample communication.

Q5

Q5. Does the approach extend to dd-dimensional means, for example with one bit per sample for all coordinates, and what rate would you expect?

We thank the reviewer for this suggestion. We have added the dd-dimensional result and its full proof in Appendix G (Theorem G.1). Suppose ∥μP∥2≤λ\|\mu_P\|_2\leq\lambda and EP[∥X−μP∥2k]≤σk\mathbb E_P[\|X-\mu_P\|_2^k]\leq\sigma^k. For every k>1k>1, d≥1d\geq1, λ≥σ>0\lambda\geq\sigma>0, 0<ϵ≤σ/20<\epsilon\leq\sigma/2, and 0<δ<1/20<\delta<1/2, our fully non-adaptive protocol uses one bit per vector sample and achieves Euclidean error at most ϵ\epsilon with probability at least 1−δ1-\delta, with the following sample complexity:

For k>2k>2:

Ok(dlog⁡(1+λσ)+d(σϵ)2log⁡1δ).O_k\left(d\log\left(1+\frac{\lambda}{\sigma}\right)+d\left(\frac{\sigma}{\epsilon}\right)^2\log\frac{1}{\delta}\right).

For k=2k=2:

Ok(dlog⁡(1+λσ)+d(σϵ)2log⁡σϵlog⁡1δ).O_k\left(d\log\left(1+\frac{\lambda}{\sigma}\right)+d\left(\frac{\sigma}{\epsilon}\right)^2\log\frac{\sigma}{\epsilon}\log\frac{1}{\delta}\right).

For 1<k<21 < k < 2:

Ok(dlog⁡(1+λσ)+d(σϵ)k/(k−1)log⁡1δ).O_k\left(d\log\left(1+\frac{\lambda}{\sigma}\right)+d\left(\frac{\sigma}{\epsilon}\right)^{k/(k-1)}\log\frac{1}{\delta}\right).

Appendix G also proves a matching lower bound at a fixed universal failure probability for 0<ϵ≤ckσ0<\epsilon\leq c_k\sigma, where ck>0c_k>0 depends only on kk. This lower bound holds even for adaptive protocols, so the dependence on dd and ϵ\epsilon is optimal at this fixed confidence level.

Q6

Q6. For k=2k=2 the rate has an extra log⁡(σ/ϵ)\log(\sigma/\epsilon) factor. Is it known that the adaptive lower bound also contains this factor for general queries, so that the claim of optimality covers k=2k=2 too? Could you state the exact range of (ϵ,δ)(\epsilon,\delta) in which the lower bound applies?

Yes. Theorem 9 of Lau and Scarlett (2026c) establishes the following lower bound for k=2k=2:

\log\frac{\lambda}{\sigma} +\frac{\sigma^2}{\epsilon^2} \log\frac{\sigma}{\epsilon} \log\frac1\delta \right).$$ The bound applies to arbitrary measurable one-bit queries, including randomized adaptive protocols. The proof in Appendix B.1 of Lau and Scarlett (2026c) yields the sufficient range $\lambda\geq\sigma>0$, $0<\epsilon\leq\sigma/100$, and $0<\delta\leq1/16$. Our upper bound matches this lower bound throughout this range. Thus, our optimality claim includes $k=2$, and the additional $\log(\sigma/\epsilon)$ factor is unavoidable even with interaction.
AuthorsOpenReview ↗

Response to Reviewer j4hG (3/3)

Minor point 1

The AI use statement says generative AI assisted "with some of the theoretical proofs". It would help to say which parts.

We have updated the AI use statement to specify that generative AI helped develop the dd-dimensional extension in Appendix G, particularly its lower-bound proof. We also used AI for calculations and checks in individual proof steps, literature searches, language editing, and LaTeX formatting. We independently verified the mathematical arguments and take full responsibility for the paper.

Minor point 2

Proposition 2.1 is stated under the first-moment condition EP∣X−μP∣≤σ\mathbb E_P|X-\mu_P|\leq\sigma. Please confirm that the cited Theorem 16 of Lau & Scarlett (2026c) holds under this condition, and not only for the class Dk\mathcal D_k.

Yes. Theorem 16 of Lau and Scarlett (2026c) is stated for every distribution satisfying μP∈[−λ,λ]\mu_P\in[-\lambda,\lambda] and EP[∣X−μP∣]≤σ\mathbb E_P[|X-\mu_P|]\leq\sigma. It therefore applies directly under the assumptions of Proposition 2.1, without requiring a bounded higher-order moment.

Reviewer_995gOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies distributed mean estimation of 1-dimensional distributions with bounded kk-th order moment with 1 bit per user. The authors established optimal sample complexity bounds using a non-adaptive protocol, improving a prior result that achieved the same rate using interactive protocols.

Critical strengths

The paper designs a new non-interactive protocol for

Critical weaknesses
  1. I find the high-level description of the refinement stage on pages 3 and 4 somewhat vague. It is unclear how the crude estimate in the first stage and a new set of samples turn into a refined estimate. For example, in Step 1, the threshold and block sign queries do not have a definition or high-level description. I read from later sections that these queries are randomly selected, but this important detail is not specified here. Also, MM is not defined in Step 2. The authors should precisely describe the important steps in the protocol.
  2. The paper does not compare with existing non-interactive protocols for mean estimation of specific distribution classes, in particular,

[1] Tony Cai and Hongji Wei. Distributed Gaussian mean estimation under communication constraints: Optimal rates and communication-efficient algorithms, Journal of Machine Learning Research, 2024

[2] Distributed estimation with multiple samples per user: Sharp rates and phase transition J Acharya, C Canonne, Y Liu, Z Sun, H Tyagi - Advances in Neural Information Processing Systems, 2021 Both works use two carefully designed block-sign queries to refine the crude estimate in the first stage, which appears conceptually similar to the strategy used in this work. The authors should discuss the similarities and differences to highlight the key technical novelties.

I am willing to increase the score if these points can be addressed.

Minor point: the paper hides the dependence on kk, which I believe is important. With an appropriately chosen kk, ideally we should recover the sample complexity of Gaussian distributions.

Questions for authors
  1. How does the refinement procedure compare with references [1] and [2] (listed in the Weaknesses section).
  2. Can the sample complexity result in this paper recover that of Gaussian distributions with an appropriately chosen kk?
2 comments
AuthorsOpenReview ↗

Response to Reviewer 995g

We greatly appreciate your constructive comments on our paper. We have revised our paper according to your suggestions (please see the Common Response above for an overview of the revision) and these revisions really help to improve our paper! Please kindly let us know whether you have any further concerns. If our response addresses your concerns, we would greatly appreciate it if you could reconsider the rating.

W1: Vague description of the high-level protocol

I find the high-level description of the refinement stage on pages 3 and 4 somewhat vague.

Thank you for pointing this out. We have expanded the refinement overview in Section 2 (marked in red) to explain how the construction yields an unbiased component estimator with bounded variance and how we establish the final sample-complexity bound.

It is unclear how the crude estimate in the first stage and a new set of samples turn into a refined estimate

The coarse estimate CC is used to decode bits obtained from fresh samples through queries fixed in advance. At each scale, the decoder selects the block containing CC and combines the paired one-bit responses, derivative weight, and safety correction to obtain a conditionally unbiased estimate of the residual X−CX-C. Averaging these estimates, summing across scales, and adding CC gives a refined mean estimate with controlled bias and variance.

the threshold and block sign queries do not have a definition or high-level description

We now explicitly define the signed threshold Λv(x)=1−21[x≥v]\Lambda_v(x)=1-2\mathbf{1}[x\geq v], the random block signs RmR_m, and both binary queries in Section 2. The first query encodes the product of the block sign and the signed threshold, while the second encodes only the block sign and supplies the centering correction needed during decoding.

Also, M is not defined in Step 2

The revised overview now explicitly defines the terminal scale index as M=⌈log⁡2(4s0/ϵ)/(κ−1)⌉M=\left\lceil\log_2(4s_0/\epsilon)/(\kappa-1)\right\rceil under "Multiscale reconstruction" in Section 2. This choice makes the truncation bias at the final scale sM=2Ms0s_M=2^M s_0 at most ϵ/4\epsilon/4.

W2 / Q1. Comparison with Cai and Wei (2024) and Acharya et al. (2021)

Thank you for highlighting these related protocols and we have added a comparison in Appendix A. We study one-bit-per-sample mean estimation for arbitrary real-valued distributions with a bounded kk-th central moment. Cai and Wei [1] focus on Gaussian means with known variance under machine-level communication budgets, whereas Acharya et al. [2] estimate arbitrary distributions over a known finite alphabet in total variation, with mm samples and a bit budget per user. The relevant refinement subroutines share the non-interactive architecture of fixing queries in advance and using a coarse estimate during decoding.

In Cai and Wei (2024), refinement uses two deterministic periodic binary queries with different phases. Localization identifies a Gaussian response function that is monotone on the recovered interval, which the decoder inverts using the empirical response. Our refinement instead combines pairwise-independent block signs, a centering correction, and a threshold-integration identity to obtain exactly conditionally unbiased estimates of compactly supported components, without requiring a known parametric response function.

In Acharya et al. (2021), the count of symbol aa among a user's mm samples follows Bin⁡(m,pa)\operatorname{Bin}(m,p_a), enabling general discrete-distribution estimation through binomial estimation subproblems. The refinement in Section 2.1.2 uses interlaced partitions adapted to binomial variance, together with a boundary query, and inverts the appropriate binomial response after localization. In contrast, our refinement directly estimates functions of real-valued observations through random-sign cancellation and centering, with tail-dependent second-moment bounds for the multiscale increments that enable the optimal rate under only a moment bound.

Minor point / Q2. Recovering the Gaussian rate and dependence on kk

Yes. For X∼N(μ,τ2)X\sim N(\mu,\tau^2), take k=4k=4 and σ=31/4τ\sigma=3^{1/4}\tau, since E∣X−μ∣4=3τ4\mathbb E|X-\mu|^4=3\tau^4. Theorem 1.1 then gives, for small ϵ/τ\epsilon/\tau,

+\frac{\tau^2}{\epsilon^2}\log\frac1\delta\right).$$ This is the Gaussian refinement rate in the one-sample-per-user setting, stated here as a high-probability guarantee. The fixed choice $k=4$ works for every sample size. Because the construction uses $\kappa=\min\{k,3\}$, its constants are uniform for $k\geq3$ with $\sigma$ fixed. For fixed confidence, this matches the sample-complexity scaling obtained from Cai and Wei (2024, Theorem 1, Eq. (13), refinement branch) by setting $n=1$ and $b_i=1$: after rescaling the mean range, their sample complexity bound is also \$ m=O(\log(2\lambda/\tau)+\tau^2/\epsilon^2)\$.
AuthorsOpenReview ↗

Further response to Reviewer 995g

Dear Reviewer,

Thank you again for your thoughtful review. With the discussion deadline on November 18 AoE, we would appreciate knowing whether our clarifications have addressed your concerns. If so, we would be grateful if you could reconsider the assessment. We are also happy to engage in further discussion.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Common Response to All Reviewers

We sincerely thank all reviewers for the time and effort devoted to reviewing our paper. Your constructive comments and suggestions have helped us improve the paper!

We have responded to the concerns and questions of each reviewer in the individual responses. We have also revised the paper according to the reviewers' suggestions. The revisions are marked in red in the revised version. For convenience, we summarize the main changes below.

  1. Multidimensional extension (j4hG Q5). Theorem 1.2 (p. 2) and Appendix G (pp. 19–23) extend the result to dd-dimensional mean estimation under a finite central moment bound, using one bit per vector sample and at most dd times the scalar sample complexity, up to constants depending only on kk.

  2. Refinement overview (995g W1; FJph W2, Q1, Q2). Section 2 (pp. 3–4) now gives a step-by-step explanation of the refinement process, including blocking, random shifts and signs, the paired queries, and the safety correction. It explains how these yield conditionally unbiased component estimates, how the components are combined across scales, and how the terminal scale index MM is chosen.

  3. Related work (995g W2, Q1; j4hG W1, Q1). Appendix A (p. 13) now compares our construction with Cai and Wei (2024) and Acharya et al. (2021), explaining how their model-specific response inversion differs from our distribution-independent identity for component estimation. It also gives a more detailed comparison with the concurrent work of Miao (2026) and Lau and Scarlett (2026a).

  4. Multiscale motivation and constants (FJph Q2, Q3). Appendix F (p. 16) quantifies why applying the coarse variance bound at a single truncation scale does not yield the target sample complexity. Equation (1.1) (p. 2) now states the kk-dependent prefactors in the scalar sample complexity explicitly.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.