- 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
-
Overall, the paper contribution is limited, in the sense that it has a single result, and most of the steps follow standard procedures.
-
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 , why it is required that the derivative of 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
-
How does blocking allows to obtain a refined error estimate even for a single scale?
-
In the multiscale reconstruction, the scale parameters 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.
-
The rate in Theorem 1.1 is stated up to constants that depend on the moment order . Are there any guarantees on their values? For example, that they are not exponential in ?
6 comments
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 , which equals the identity on and vanishes outside , has a coarse variance bound and an absolute bias bound , where and . For fixed , fixed confidence, and , choosing the smallest satisfying and applying only this coarse variance bound gives a sufficient sample budget , whose exponent exceeds that of the target rate .
We therefore write and with , so the components sum to the desired truncation. Since vanishes near zero for , Lemma 3.2 gives, conditional on successful localization with center , a single-replicate variance bound which is at most . The allocation approximately equalizes these coarse bounds after averaging. It increases with scale for , remains constant at , and decreases for , up to rounding.
Q3. What guarantees are available for the constants depending on ?
Equation (1.1) now displays the following -dependent prefactors, up to a universal multiplicative constant.
For :
For :
For :
Here is universal. The sample-complexity rates match the adaptive bounds [1] for each fixed , 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
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
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>1.
W2. Clarity of the refinement construction and notation
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.
A block sign is a public random value in −1,+1 assigned to a spatial block. The decoded sign A0 equals one when its observation lies in the selected block containing C, while contributions from other blocks have mean zero over the public signs.
A replicate uses two fresh, independent observations and a shared public seed to produce one decoded component estimate.
Zg(s) (or Zg(C) used in the paper) is the decoded statistic for a compactly supported component g, with conditional expectation E[g(X−C)∣Floc]. The decoder evaluates it at the recovered center C and combines the component estimates across scales to form the final estimate.
The component g:R→R is compactly supported and absolutely continuous, and 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 C is unknown when the refinement queries are fixed. It preassigns local intervals across the possible range of C, allowing the decoder to select the block containing C 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), where g is supported on [−2s,2s]. In the adaptive setting, the local interval can instead be chosen after C is known.