One-Bit Distributed Mean Estimation with Unknown Variance
Authors: Ritesh Kumar
Shashank Vatedka
Venue: Accepted by TMLR ()

Abstract: In this work, we study the problem of distributed mean estimation with $1$-bit communication constraints when the variance is unknown. We focus on the setting where each user has access to one i.i.d. sample drawn from a distribution belonging to a \emph{location–scale family}, and is limited to sending just a single bit of information to a central server whose goal is to estimate the mean. We propose simple non-adaptive and adaptive protocols and show that both achieve asymptotic normality. We derive bounds on the asymptotic (in the number of users) Mean Squared Error (MSE) achieved by these protocols. For a class of symmetric log-concave distributions, we derive matching lower bounds for the MSE of adaptive protocols, establishing the optimality of our scheme. Furthermore, we develop a lower bound on the MSE for non-adaptive protocols that applies to any symmetric strictly log-concave distribution, using a refined squared Hellinger distance analysis. Through this, we show that for many common distributions, including a subclass of the generalized Gaussian family, the asymptotic minimax MSE achieved by the best non-adaptive protocol is strictly larger than that achieved by our simple adaptive protocol. We also demonstrate that increasing the number of bits per user can only marginally reduce the asymptotic MSE of adaptive protocols. Our simulation results confirm a positive gap between the adaptive and non-adaptive settings, aligning with the theoretical bounds.

Published in Transactions on Machine Learning Research (Jan/2026)
One-Bit Distributed Variance
Mean Estimation
with
Unknown
Ritesh Kumar
ritesharyon6222@maa.. com
Deportment of Electrical Engineering Indian Institute of Technology Hyderabad, India
Shashank Vatedka
skashankvutedkaa@eer... with
Department Electrical Engineering Indian Institute of Technology Hyderobad, India
Reviewed on OpenReview: https: // openreview. formm? id- g95C4xIEPg
Abstract
In this work, study the problem of distributed mean estimation with 1-bit communication constraints when the variance is unknown. We focus the setting where each user has access to one i.idd. sample drawn from distribution belonging to location-scale family, and is limited to sending just a single bit of information to central server whose goal is to estimate the mean. We propose simple non-adaptive and adaptive protocols and show that both achieve asymptotic normality. We derive bounds on the asymptotic (in the number of users) Mean Squared Error (MSE) achieved by these protocols. For class of symmetric log- concave distributions, we derive matching lower bounds for the MSE of adaptive protocols, establishing the optimality of our scheme. Furthermore, we develop lower bound the MSE for non-adaptive protocols that applics to any symmetric strictly log-concave distribution, using a refined squared Hellinger distance analysis. Through this, we show that for many common distributions, including a subclass of the generalized Gaussian family, the asymptotic minimax MSE achieved by the best non-adaptive protocol is strictly larger than that achieved by our simple adaptive protocol. We also demonstrate that increasing the number of bits per user can only marginally reduce the asymptotic MSF of adaptíve protocols. Our simulation results confirm positive gap between the adaptive and non- adaptive setlings, aligning with the theoretical bounds.
1 Introduction
The rise of big data has made distributed data analysis essential, as large datasets are often spread across multiple locations. Traditional data processing and learning techniques are often insufficient such scenarios, motivating advances in distributed lcarning and estimation (McMahan al., 2017; Chen al., 2021; Kairouz et al., 2021). In many problems such as distributed optimization and federated learning, communication often emerges the main bottleneck, creating the need to develop communication--ffiienn algorithms for distributed learning, estimation, and optimization (Alistarh et al., 2017; Chen et al., 2021; Li et al., 2020; Bernstein et al., 2018; Kairouz et al., 2021; Chen et al., 2018; Wang et al., 2018).
Extreme communccation efficiency is also crucial in many signal processing applications, including ToT and sensor networks, where we typically have tens to hundreds of low-power devices that make noisy measure- ments which must be communicated scenarios, severe power and bandwidth constraints have motivated substantial recent work on understand-
fusion center for subsequent decisions or estimation. In such
*The work of Shashank Vatedka was supported a Core Research Grant (CRG/2022/004464) from the Anusandhan National Research Foundation (ANRF).

---

Published in Transactions on Machine Learning Research (Jan/2026)
ing the trade-off between communication cost and estimation accuracy (Heinzelman et al. 2000; Ribeiro & Giannakis, 2006; Luo, 2005; Ben-Basat et al., 2024).
In particular, there has been growing interest in distributed algorithms for machine learning, optimization, and statistical inference when each of a large number of users is allowed to communicate only one bit per sample (Seide et al., 2014; Zhu al., 2021; Fan et al., 2022; Tang et al., 2021). While such requirements may seem extreme, they offer significant benefits in terms of system design, particularly when using low-cost, resoucc-consttrannct devices.
There is large body of recent work on distributed mean estimation (DME) under such communication constraints. DME in the high-dimensional setting forms a basic building block for several distributed learning and optimization algorithms (Suresh et. al., 2017; Amiraz et al., 2022; Liu et al., 2023).
On a similar vein, there has been significant progress in understanding the fundamental limits of para- metric estimation in location familics partiils-pat Gaussian (Cai & Wei, 2022b; 2024) and symmetric log-concave (Kipnis & Duchi, 2022; Kumar & Vatedka, 2023) location families as well as non-parametric density (Acharya et al., 2023) and mean (Lau & Scarlett, 2025) estimation under communication constraints, Estimation with more general information constraints has been studied in (Acharya et al., 2020a;b; 2021; Koltchinskii et al., 2023), while lower bounds on minimax risk for distributed statistical estimation (Zhang et al., 2013) and communication-effiieent algorithms for distributed optimization on large-scale data (Zhang et al., 2012) have been established. Practical algorithms have been proposed in (Battey et al., 2018; Deisen- roth & Ng, 2015). The distributed setting with one-bit information sharing is particularly challenging and has been extensively studied (Venkitasubramaniaa et al., 2007; Chen & Varshney, 2009). More recently, (Han et al., 2021; Barnes ct al., 2020; Rahmani et al,, 2024; Shah et al., 2025) derived lower bounds for distribu- tion learning in parametric and nonparametric settings. The framework applies to both fixed and sequential pressage-passing protocols for various problems including communication-constaaa estimation for Gaussian distributions. Understanding the parametric setting can yield new insights and aid the design of algorithms for problems such as distributed optimization and federated learning with commu- nication constraints.
mean and covariance
Location-scale models have been widely studied in statistics, cconomics, and sociology. In cconomics, such models form the basis of price, demand, and welfare estimation, from classical discrete-choice models Deaton & Muellbauer (1980); McFadden (1974) to more recent work addressing ar urbitrage-free forecasting and heavy- tailed market behavior Carvalho & Hahn (2018); Guggenberger & Jansson (2022). In quantitative finance, location-scale assumptions underpin models of returns and volatility, inchuding ARCH/ /GARCH and their modern Bayesian and data-driven extensions Bollerslev (1987); Campbell et al. (1997); Yu & Meyer (2019); Sirignano Cont (2019). Similarly, in sociology and psychometrics, latent-trait models such as the Rasch and logistic item-response formulations depends on scale location structures Rasch (1960); Birnbaum (1968); Jeon& & Rabe-Heskedt (2019).
In many of these problems, data is often generated across heterogencous, goographically dispersed, privacy- sensitive sources-retail outlets, financial exchanges, or survey respondents where transmitting full-resolution observations impractical due to bandwidth, latency, or confidentialityy constraints Suresh et al. (2017); Konečný et al. (2016); Duchi et al. (2018). In such settings, one-bit and low-bit communicttio primitives could provide an attractive alternative by reducing communication, provide privacy (with additional differ- entially private mechanisms), and enable lightweight protocols that aggregate information without requiring centralized raw data access Zhang et al. (2013); Braverman et al. (2016); Dana & Duchi (2022). Thus, the one-bit estimators developed in this work could potentially have applications in many of these arcas as well.
1.1 Contributions
In this paper, we consider distributed mean estimation in a setting where each user has a single i.i.d. sample and is allowed to share only one bit of information with a central server. Many of the existing works on DME, including (Kipnis & Duchi, 2022; Cai & Wei, 2024; Kumar Vatedka, 2023), assume that the mean is the only unknown parameter, which may not hold in practice. We consider scalo-location families, where both the mean and variance are unknown, and the variance is treated nuisance parameter. We design
2

---

Published in Transactions on Machine Learning Research (Jan/2026)
simple non-adaptive and adaptive protocols for this problem, and derive bounds on the asymptotic mean squared error (MSF) achieved by our protocols.
Despite the recent surge of interest in such problems, much less is known about the performance gap be- tween adaptive and non-adaptive protocols when both the mean and variance are unknown. For many communiatioon-constriinni estimation/testee /testtiting problems, it an interesting open question as to whether non-adaptive protocols are strictly suboptimal compared to adaptive protocols.
The main contribution of our work is to show that for a broad class of distributions, inchuding the hyperbolic secant and generalized Gaussian with shape parameter 3 < 1.85, the asymptotic minimax MSE achieved by the best non-adaptive estimator is provably higher than that achieved by our simple 2-round adaptive protocol. We do so by deriving a general lower bound on the minimax MSE of non-adaptive estimators for arbitrary symmetric strictly log-concavy distributions. We then compare this against the MSE achieved by our adaptive protocol. We also derive a lower bound on the MSE achieved by adaptive estimators and prove that for broad class of distributions, our simple 2-round protocol in fact optimal. We also also compare our results with lower bound on asymptotic MSE for the case where communication constraints are imposed on the users, and observe that for many distributions our adaptive protocol achieves an MSE that is close to this lower bound.
Although we mainly study this problem through the lens of parametric estimation, the algorithms and insights derived here could aid the design of improved algorithms for distributed optimization and federated learning when there are severe communication constraints.
A short recorded video is provided as supplementary material here Kumar & Vatedka. (2026a).
2 Problem Setup and Summary of Results
2.1 Problem Setup
Definition 2.1. Let fx a probability density function (pdf) on I with zero mean and unit variance, and let Fx be the corresponding cumulative distribution function (cdf).
The location family associated with fx is defined as:
f(xx) (xx,(x)=
p MER)
(1)
The scale-location family associated with fx is defined as:
(s((fx) (fxmolo) = o - (==²) MER, 020
(2)
Throughout the paper, assume that fx is non-zero, Fx is invertible, and Fx is differentiable at all points in RR.
The main goal of this paper is to establish fundamental bounds on the achievable mean squared error (MSE) for estimating E R in a distributed setting when o > O is unknown and treated as a nuisance parameter.
Let us formally describe the problem. Suppose X1, X2...., X,, are i.i.d. samples drawn from a distribution with density function fx,ma belonging to (fx). We consider a central server and users, where user has access to only one sample X, (also called the i'th input/souree and is allowed to send single bit of information Y, (0, 1} to the server.
We assume that fx is exactly known to the server, while (μ, E R x R are unknown. The goal is to design a communication protocol that enables the server to reliably estimate from Y,,..,, Y,.
Designing II amounts to specifying n encoders (one for each user) that map X, Y,, and a decoder (at the server) that maps (Y,...., Yn) to an estimate á of μ. Importantly, we do not restrict the encoders to be identical, iee, can design a different map for each user if required.
3

---

for Published in Transactions on Machine Learning Research (Jan/2026)
Ôc Pac
Server
Y1
Y2
Y=1
Y Y11t1
Ymitng
ENC
ENC
ENC
ENC
ENC
X1
X2
X
X Xn1+1
X Xm1+n3
Figure Illustration of our non-adaptive protocol. partition the n users into subsets nu and ni users. Each user independently encodes their sample using 1-bit quantizer, with threshold 0 for the first users and 02 for the remaining n2 users.
We call a protocol non-adaptive if each Y, depends only on X5 it is adoptive if Y can depend on X; as well as Y.- The performance of protocol is quantified via the asymptotic mean squared error:
lim MSE(A) lim n [lp - [
(3)
n
7-000
which may, in general, depend on μ and
In this work, we consider both adaptive and non-adaptive protocols for scale-location families with symmetric log-concave base density fx- We derive bounds on the optimal asymptotic MSE in these settings and show that for many distributions of interest, there is a positive and quantifiable gap between the optimal adaptive and non-adaptive protocols.
2.1.1 Notation
For sequence of random variables X2, and random variable X all defined over the same probability space, we denote X, a.s. X if the sequence of random variables converges almost surely to X. Likewise,
X, A X the sequence converges in distribution X.
We say that protocol is strongly consistent if the final estimate ft من μ as oc for every μ, a. Similarly, say that jt is asymptotically normal if Vn(A μ)) converges in distribution to Gaussian every p.a.
2.2 Summary of Results
We first study a simple threshold-based 1-bit non-adaptive protocol that yields strongly consistent and asymptotically normal estimates for jointly estimating both and a. In Theorem 3.1, we derive the achievable MSE for estimating and using this scheme.
We then derive a lower bound on the asymptotic MSE for non-adaptive protocols, and this one the main contributions of this work. Specifically, we show that if log 1 is strictly convex, then for any non-adaptive protocol,
Tx
lim sup (n. MSE(A) >
0.1034
(4)
T(Jx)
where T(fx) is a parameter that depends on fx. See Thcorem 3.2 for more details.
We also study an intuitive multi-threshold non-adaptive protocol, where each user is assigned a different threshold. In Theorem 3.3, we establish bounds on the bias and variance of the resulting estimator.
We then design simple adaptive protocol for estimating p. This requires minimal adaptation and can be summarized at high level follows: We first run our non-adaptive protocol using only the first n' o(n)
4

---

Published in Transactions on Machine Learning Research (Jan/2026)
users, and the server produces coarse estimates (fc. of the mean and variance respectively. The estimate Pe is broadcast to the remaining - n²' users. These users then independently encode their samples to produce ,I, Yn, which are used by the server to produce the final estimate P. In Theorem 4.1, we show that this simple adaptive schome is strongly consistent, asymptotically normal, and achieves
o²
lim n MSE(A) 4f2
(5)
We then show that this is optimal for a large subclass of symmetric, strictly log-concave distributions, by proving a matching lower bound on the MSE of any adaptive protocol (Theorem 4.3). As a consequence of our results, we are able to show the strict suboptimality of non-adaptive protocols compared to adaptive protocols. For several important examples including generalized Gaussian distributions (GGD):
fx(x)=
B exp (-(1=l/a))) (1I((
a
T(1/3) T(3/3)
(6)
with 1 < 3 < 1.85, and the hyperbolic secant we show that the lower bound in equation 4 is strictly larger than the o² (0) achieved by our simple adaptive protocol, thereby establishing a positive and quantifiable gap between the optimal adaptive and non-adaptive performance.
We compare these bounds with one obtained using the Fisher information, corresponding to the centralized setting (equivalently, where there are no commmiccttin constraints). For many distributions, our simple adaptive protocol achieves an asymptotic MSE that is close to this lower bound, which shows that increasing the number of bits communicated per user can only marginally improve the performance.
We finally conclude with some comments and open questions.
2.3 Related Work
Perhaps the closest work to this paper is (Kipnis & Duchi, 2022), which studied 1-bit DME for location families, where the mean is the only unknown parameter. Our protocols are inspired by their schemes for location families, and we also borrow some high-level ideas in calculating the asymptotic MSE. However, their work assumes that the mean is the only unknown parameter, and their results and techniques do not directly extend to the case where the variance is unknown. The analysis of our adaptive protocol is also significantly more challenging than theirs, as must also obtain a coarse estimate of the variance, which introduces additional dependencies in the MSE derivation. Moreover, we take a lotally different approach towards lower bounding the minimax MSE for non-adaptive protocols.
The works (Cai & Wei, 2022a; 2024) studied DME of Gaussian distributions under more general multi-bit communication constraints, and derived bounds on the minimax MSE for finite (but large) n. However, both works assume that the range of μ is bounded (e.g., μ E []), and the results do not extend if this assumption is relaxed. While (Cai & Wei, 2024) assumes that the variance is known exactly, (Cai & Wei, 2022a) assumes that the variance is unknown but requires the protocol to know a lower bound on in advance (with the achievable MSE depending on this bound). In fact, (Cai & Wei, 2022a) prove gap between non- adaptive and adaptive protocols for Gaussian scale-location families. However, their approaches are tailored specifically to the Gaussian setting with restrictions on the range of μu, a, their protocols require more than one bit per user, and their methods do not extend easily to more general distributions. In contrast, we make no boundedness assumptions on i or 0, and our results hold for a broad class of symmetric, strictly log-concave distributions.
It is worth noting that (Kipnis & Duchi, 2022) claimed strict suboptimality of non-adaptive protocols when the mean is the only unknown paramcter. However, their lower bound for non-adaptive protocols relies on restrictive assumptions (see (Kipnis & Duchi, 2022, Assumption A2)), and it is possible to design schemes that violate these. Indeed, (Cai & Wei, 2024) provide such a ada-aivet protocol for the Gaussian location family that achieves order-optimal MSE even under communication constraints. In our work, we prove strict suboptimality of non-adaptive protocols in the o-unknown setting for a broad class of symmetric, strictly log-concave distributions, thereby generalizing the Gaussian-speciffe results of (Cai & Wei, 2022a).
5

---

Published in Transactions on Machine Learning Research (Jan/2026)
Very recently, (Shah et al., 2025) analyzed properties of the maximum likelihood (ML) estimator ing threshold-based non-adaptive protocols for parametric estimation of a class of exponential families. Specifically, they study protocols where Y, 1xx,3T,), where 1.) denotes the indicator function and for = 1.2..... n, Tj E R is a prodefined threshold. The authors show that the ML estimator is consistent and asymplotically normal. Using this, they are able to compute the asymptotic mean squared error for Gaussian scale-location families as a function of 71, T2,..., but further optimization of the thresholds and deriving simple closed-form upper/lower bounds was left for future work. In comparison, we design non- adaptive and adaptive protocols for mean estimation over general scale-location families, derive closed-form achievable and converse bounds, and prove matching lower bounds for adaptive protocols over symmetric, strictly log-concave distributions. Our lower bound for non-adaptive protocols holds in the broadest sense (subsuming threshold-based protocols).
More recently, (Lau Scarlett, 2025) studied nouparametric estimation of the mean with 1-bit communi- cation constraints, but under probably approximately correct (PAC) framework. They derived upper and lower bounds on the sample complexity, and notably showed that a two-stage adaptive protocol is order optimal. In contrast, we derive bounds the asymptotic minimax MSE, with aim to characterize the exact constants.
A number of works have derived lower bounds for varions estimation problems with communication con- straints (Han et al., 2021; Zhang et al., 2012), (Zhang et al., 2013), (Barnes et al., 2019; 2020). However, these results do not directly yield lower bounds for our problem. Many of these works employ either the Van Trees inequality or Le Cam's method (Van Trees, 2004; Gill & Levit, 1995; Le Cam, 2012; Polyanskiy & Wu, 2024), and use both approaches in deriving our bounds. Our adaptive lower bound uses the Van Trees inequality, similar to (Kipnis & Duchi, 2022), while our non-adaptive lower bound is obtained by upper-bounding the squared Hellinger distance between transcripts under two different mean values, followed by an application of Le Cam's method (Le Cam, 1973; Polyanskiy & Wu, 2024).
A parallel line of work (e.g., (Konečný & Richtárik, 2018; Mayekar et al., 2021; Ben-Basat et al., 2024; Babu et al., 2025)) studied distributed empérical mean eslimation for high-dimensional vectors, with applications distributed optimization and federated learning. Unlike our work where the samples are assumed to be i..dd, here the samples are fixed but arbitrarily chosen (typically to be of unit norm). The goal is to design conumnncatiion-eliciee compressors and sketches and study accuracy communication tradeoffs. While the setup is slightly different, many high-level ideas between these works and ours (e.g., randomized quantizers and sketching ideas) are conceptually related.
Along similar lines, Vardhan Mazumnar (2025) have recently investigated communication-eflcceett dis- tributed mean estimation with collaborative one-bit compressors, in which clients use private and shared randomness to compress their source. Their basic scheme operates by deliberately perturbing the source with independent gaussian noise, and the server uses mean estimator that looks similar to the one described in Section 3.1. The authors also extend this to high-dimensional sources and derive bounds on the worst-case MSE assuming that the input samples lic within a (known) bounded set.
3 Non-Adaptive Protocols
3.1 A Consistent Protocol for Location Families
To provide some intuition for the design of our protocols, let us begin with the simple non-adaptive protocol considered in (Kipnis & Duchi, 2022) for estimating location families. For now, assume that each X; is an i..d. sample drawn according to fx, = fx(x - p),, where E R is the only unknown parameter.
User i transmits
Y, = [(x,00)
6

---

Published in Transactions on Machine Learning Research (Jan/2026)
where A E IR is pre-set threshold and 1g is the indicator of event E. At the server, compute Y, follows:
Y,
Fx - 1))
(7)
where convergence follows from the strong law of large numbers. Using this, the server can estimate by inverting the quantile (Kipnis & Duchi, 2022; Lehmann & Casella, 2006) as follows
(P,))
From the continuous mapping theorem (Casella & Berger, 2002), P u.s. l as o0, and hence f is a strongly consistent protocol of μ.
As discussed in (Kipnis & Duchi, 2022), vT((,, - Fx -a) converges in distribution to a Gaussian with zero mean and variance Fx - (1 - Fx(0 - 1)) as n - co. Using the delta method, they show that vn(ā- 1 μ1) is asymptotically normal with
lim n MSE(A) Fx (1) (1 Fx (0 4)) R-
fx 1)
3.2 A Consistent Non-Adaptive Protocol for Scale-Location Families
As a warmup, let us extend the ideas above to design a 1-bit non-adaptive protocol for estimating μ4, a. We partition the users into two subsets of size nı and ng respoctively. Here' n1 = Kin and n2 K2n, where Ki and K2 are constants independent of n, and Ki + K₂ 1. We select two different thresholds 0n and O2. and the encoders operate follows: For & i n1,
1 if X, 11, otherwise.
Y
For n + +liign n,
1 if X; < 02, otherwise.
y
0
The users share the encoded samples with server.
The server first computes
F
Y,
F2
Σ
Y
11
n2 (=
and then
0n (F)) and 02 Fx (F))
(Fi)
(8)
By the strong law of large numbers, Fi and F3 almost surely converge to Fx ((==)) and Fx (De=t) respectively. Now, we define the estimates of a and μ follows:
0
02 a.s.
0102
a20)
6e
and Aa
a.s.
14
(9)
02
01
0:2
where convergence follows from the continuous mapping theorem (Casella & Berger, 2002, Sec. 5.5). With this setup, the MSE achieved by this protocol is presented below.
TTo keep the calculations simple, we assume that Kjn, Kyn are integers. However, the results do change chonse m1. mg be the closest integers Kin, Kan respectively.

---

Published in Transactions on Machine Learning Research (Jan/2026)
Theorem 3.1. For every R and o 0, the protocol in Sec. 3 is strongly consistent, asymptotically normal, and salisfies
02
Kiol
K203
lim n MSE(A() = (81 - 02)2 n-20
(02
11)
+
(01
142
f
f
82-14
04
K20
lim n MSE(0.) = (81 Bz)2
f3
11=1
f3 0
a
where for i 1,2,
0, 11-
11 1
0 - 11 )) Fx
("= (b=1))
o; Fx
0
See Appendix A for the proof.
We do not claim that the above protocol is optimal. A carcful observation reveals that the asymptotic value of n MSE( and n MSE((.) depend on and that for fixed 0,, 02, this grows unbounded as dc or μ - -00 However, we will use this as a basic building block for our adaptive scheme. While it yields strongly consistent estimates for both μ and a, its performance can be significantly improved when a small amount of feedback can be provided subset of the users.
3.3 Lower Bound for Con-Adaptive Protocols
We now present a general lower bound on the performance of non-adaptive one-bit protocols. Theorem 3.2. Assume that fx(x) e éd()) where d(x) symmetric, differentiable, strictly convex, and is upper bounded by a polynomiaP. Then, for every 1-bit non-adaptive protocol,
a²0²
sup lim n ( p) n
(10)
T(fx)
where
1 T(fx)
((hh (()
h(x) + fxx
h* + ma),
are quantities that only depend on fx, and h- [0, h01 RR Here
( 11-
max 130
0.1034.
Proof. We use Le Cam's two-point method by identifying a suitable hypothesis testing problem and lower bounding the MSE in terms of the total variation distance between distributions of the transcript corre- sponding to the two hypotheses for any non-adaptive protocol.
Specifically, fix a IR and > O, choose > 0 (possibly depending on n), and define the symmetric alternatives
== p co, M4 co.
(11)
Each user obtains an i.i.d. sample X; drawn according to one of two distributions based on the true hypothesis:
H : X, ~ (x)), H4 X ~ fx,ay (-).
Let Py.. and Pt. be the distributions of the encoded sequence y [Yi,..., Yal for any given non-adaptive protocol corresponding to the two hypotheses.
We only require that the degree of the polynomial be constant, independent
8

---

Published in Transactions on Machine Learning Research (Jan/2026)
Using Le Cam's method (Wu, 2020, Theorem 10.2),
E [[ u)]] > (1+ -m_)? (1-)(1--VV (1-TV(Ppm: yn: P(.))
sup ne pE(p-
(12)
4
2202 (1 PL..
(13)
where TV denotes the total variation distance between the two joint distributions.
Let
Σ (VPth.or-- Pr (Vm)
PP(Pp..PPT... 2
("E(0,1)"
denote the squared Hellinger distance between the two distributions.
For a non-adaptive protocol, ,,,..,,y, are independent (but need not be identically distributed). Hence the Bhattacharyya coefficients factorize (Wright Tang, 2024, Proposition 1.4):
11
p(Prn, Pyn) (PE, PT).
1=1
From Theorem B.1, for each we have
HP Pv.) & (T(x))
+ +1)),
p p Pr. 3 - (T(xx) ( +())
Therefore,
Py.) PP. (1- (1-) 20
By the standard inequality relating total variation and the Bhattacharyya coefficient (see, e.g., (Tsybakov, 2009, cf. Lemma 2.6); also the derivation of the Bretagnolle-Hubbee bound (Bretagnolle & Huber, 1979)),
we have
IV(PY.,PPt) v p(p P...2 VI - 20+0))
where Tfxx) Therefore,
sup E[ 1) x T(xx (1--11-022) + o(1))
a²
re pelu 3
Maximizing the right-hand side over / > 0 yields the constant a", which is approximately 0.10340 and o(1) - as n - ao. This completes the proof.
3.4
Multi- Threshold Non- Non-Adaptive Protocol for Non-Parametric Mean Estimation
We now provide a natural multi- threshold protocol that works for general distributions (not just scale- location families), yielding a non parammmmeteiic estimator for the mean.
Assuming B[X[] co, the expectation of X be written
< P(X 2) dz - | P(X < 2)
B
(14)
J
Define partition of IR
0 9mm < 8-m+1 < < < 8g < 0 < 9ms
Note that have factor of 1/2 definition of the squared Hellinger distance, which absent many standard

---

Published in Transactions on Machine Learning Research (Jan/2020)
with 8u 0, and
0-- A for all j E {-m + m....,m)
for some parameter 0. In particular, we choose the parameters so that Om = -0 - 00 and A -
as
Define the midpoints
0, 0 01+1
jE (-m......
2
and
0 8g +
jE (1...,m),
2
A natural idea to approximate equation 14 by Riemann
- Σ P(X < 11)10)+1--8) -B)) j--m
E R pe
P(X > -
(15)
3.4.1 The Multi-Threshola Protocol
Our protocol can be described follows: We partition the n users into groups of K = n/(2m) users each. For convenience, let us index the users by (i,j), where i E (1,2,..., K} labels the group and j e --, m} indexes user within the group.
The (i,j)'h 'th user sends
(xx,5003) <fj
Yı.
[(x,5203)
if 0
and the server forms empirical averages
1 =
Yig 1=1
for j (-m,..., m)
K
The server outputs
PMT = Σ 7 Σ
4A
(3)
-=
Theorem 3.3. Let X be any random variable with X] < 00, distribution function Fx, and bounded density fx & L. Consider the multi-threshold protocol defined above. For every μ R and or > 0,
Lmn=
[[AMT]] -[XX] &
0
If we choose the parameters such that A + 0 and 6m = -0-m - 00, then
Var(Aurr) = K ( Ex(x) - -x o(1)
A
provided that the above integral crists.
The proof is provided in Appendix E. Observe that
(0m +
(0m 0 0_m)
K
2mK
2n
Therefore, we require 0m 8- 00, then we cannot have the variance of furT O(/n)) However, the careful reader may note that if X is bounded, then this requirement is waived, and can indeed obtain MSE that decays O(1/n).
10

---

Published in Transactions on Machine Learning Research (Jan/2026)
X Xaytng+
Y
ENCa
X1 ENC1
X tngt
Y2
ENC₂
X
ENC,
X
Y
Ôc
Y 42
X 1
ENC
Server
ENC₃
Server
f
faoe
Y n
X x11+1 +1
E
X
nn t22
Yn
X -n
E
ENC₁
Figure 2: Our bwo-round adaptive protocol: The first + users use the non-adaptive scheme to produce coarse estimates P. oe The value of Ae is broadcast the remaining ng users, who then send 1-bit messages using Ae as their quantization threshold.
This illustrates that nonparametric estimation of the mean can be more challenging. From Theorem 3.1, we see that for scale-location family, we can do significantly better than the above even with just two thresholds. However, the above theorem holds even when the mean and variance not the only unknown parameters.
Please note that Section 3.4 develops a multi-threshold non-adaptive estimator as general-purpose, non- parametric construction. As discussed in that,, such estimators may not achieve an O(1/n) MSE unless additional conditions (such as boundedness of X) are imposed, because the variance term scales with the range of the threshold grid. In contrast, for location-scale families, Theorem 3.1 shows that the two-threshold estimator of Section 3.2 already achieves significantly better performance using only pair of carefully chosen thresholds. For this reason, the adaptive scheme in Section 4 builds exclusively the two-threshold protocol of Section 3.2, while the multi-threshold estimator of Section 3.4 is included only general extension and is not used in the adaptive procedure. All references to the non-adaptive protocol in what follows should therefore be understood as referring to the method of Section 3.2.
4 Adaptive Protocol
4.1 Simple Two-Round Adaptive Protocol
We now describe a simple adaptive schome that can be implemented with two rounds of communication We will subsequently show that for many common distributions, this outperforms the best non-adaptive estimator.
We partition the users into three disjoint subsets of sizes n1, n22 and ng, where n, n2 na/ /lo/loo na) and n1 n2 + ny The first n1 ne users participate in the first round, while the remaining ny users participate in the second round. The protocol is illustrated in Fig. 2.
First round: We run the non-adaptive protocol of Sec. 3.2 using the first ni + n2 users to obtain coarse estimates Pee and &.. The estimate de is then broadcast to the remaining ny users.
Second round: Each user with n1 + n2 & i transmits
I if X, < Pe: otherwise.
Y
'Here, round of communication consists of bits sent from subset of the the server, followed broadcast. message sent the server the remaining
STf the protacol sequential and user has access Yi,..., Yi-1, then fre can directly computed the ni observing the first ny + ni transmissions.
11

---

Published in Transactions on Machine Learning Research (Jan/2026)
The server computes
(he (
F3
Σ
Y
Fx
ns (-
+22+1
where almost sure convergence follows from the strong law of large numbers, conditional on Aes as ng - 00.
Let
03 (Fa).
The final estimate of j is then
As Pe Fx (Fz) oc.
(16)
which converges almost surely to μ as n by the continuous mapping theorem. Theorem 4.1. Consider the adaptive protocol of Sec. 4 with n1 = = log ns for all E R and o > 0,
and n1 + 12 + = n. Then,
o² (āg - p)) 1 N (0,
)
4fx(
and the asymptotic MSE satisfies
a²
lim MSE((2)) n-00
(17)
4fx
See Appendix for the proof.
Remark 4.2. It may seem that the above protocol is not making full use of the power of adaptive protocols, as the last ny users are not making use of each others' transmissions. Similar to the observation made in (Kipnis & Duchi, 2022) for location families, we can show that increasing the number of rounds does not give us a lower asymptotic mean squared error. Moreover, for large subelass of distributions, we derive matching lower bound, thereby establishing the optimality of our simple two-round protocol.
4.2 Lower Bounds for Adaptive Protocols
The following theorem gives lower bound for adaptive protocols and is proved in Appendix D. Theorem 4.3. Let fx be a symmetric log-concave distribution for which
fx(x)
(18)
Fx(x))
is non-increasing in |z] and is uniquely maximized at x = Consider any prior density 9 on μ such that E (d((w)))(()) bounded, where g' denotes the derivative of g. Then, any 1-bit adaptive protocol must salisfy
lim n El - 1) (0) n
(19)
for every 0. The expectation is taken with respect to the joint density ((p) (H,
It should also be noted that the above result assumes that the protocol is sequential where Y, is allowed to depend only on X, and Yı,..., Vi, and does not hold for more complicated (e.g., blackboard) protocols.
Our lower bound in the adaptive case (equation 19) holds for symmetric, log-concave distributions such Gaussian, logistic, hyperbolic secant, and generalized Gaussian. Several distributions satisfy the assumption in Theorem 4.3, including generalized normal (generalized Gaussian) distributions with shape parameter 1 1< 3 & (this includes, in particular, the Laplace distribution (8 = 1 a limiting case) and the normal distribution (3 2)). Symmetric log-concave distributions that fail this assumption include the uniform distribution and the generalized normal distribution with shape parameter 3 B> 2. Theorem 4.3 requires the shape condition (defined equation 18) to be non-increasing |a| and uniquely maximized at 0. This ensures that the Fisher information from one-bit messages is maximized when the quantization threshold is placed at the true mean.
12

---

Published in Transactions on Machine Learning Research (Jan/2026)
Zutd
(0)
x²'
h²
T(xx
0.8665
0.4246
0.4854
0.4607
0.0246
Table 1: Numerical evaluation of the normalizing constant Z the density at the origin fx (0). the maximizer x* of h(z), the corresponding value h", and the distribation-deeendeet constant T(fx) for the example equation 20
Distribution
Cnon
Cudapt
Cuon/ Cadapt
Generalized Gaussian (3 1.5)
2.5806
1.1035
2.3385
Logistic
1.1619
1.2159
0.9556
Hyperbolic secant
1.1239
1.0000
1.1239
Sin2 (custom example equation 20)
4.1982
1.3868
3.0272
Table 2: Adaptive vs. non-adaptive constants for unit-variance distributions.
Generalized Gaussian uses , 1.5.
Values computed using Cnon = 0.1034/T(fxx) and Cadaps 1/(4fx(0)².
4.3 Suboptimality of Non-Adaptive Protocols
For any symmetric strictly log-concave fx satisfying equation 18, the benchmark upper bound on the asymptotic value of nMSE(a)/o² for adaptive protocols
Cadapt
(
and this can be achieved by our simple two-round protocol. The corresponding lower bound for non-adaptive protocols is
0.1034
Cnon T(fx)*
These correspond to the normalized (by 1/0²) upper and lower bounds derived in Theorem 4.3 and Theo- rem 3.2 respectively. Although the term T(fx) does not have a simple dlosed-form expression, this depends only on fx and hence can be evaluated numerically.
We show that for many distributions of interest, Cadapt Cnous implying that non-adaptive protocols are strictly suboptimal compared to adaptive protocols.
As toy example, consider the following strictly log-concave distribution,
fx(x)
v((r)
(20)
Zoed
where
[
1.5
0.0675 sin (4 2.023007
(xx) 1.48
+ 0.5
+ 1,
2.023076
2.023076
and
Zaud
exp (
1.48
220223066 + 0.5 ( 2,223076 )² 0.0675 sin" (4 2,022000 + dr.
[x]
1.5
Here, the constants are chosen so that fx is a valid density and has unit variance.
Substituting for and N., we numerically evaluate these integrals, and the results are listed in Table For this distribution, we find that Cadapt 1.3868 whereas Cnon 4.1982, thereby demonstrating that in this the best non-adaptive protocol has strictly larger asymptotic MSE than adaptive protocols.
13

---

Published in Transactions on Machine Learning Research (Jan/2026)
6.1334/7'xx)
Cam/Caiapt
Catya 1/(45x(0P)
Hatio = 1
Asymptotic MSE 0
Crossing 57 1.85
10
Crossing (9-50 1.85
Craa Calgt
10-
5-
100-
0
1.2
1.5
1.8
2.1
2.4
1.2
1.5
1.8
2.1
2.4
Shape parameter (3)
Shape parameter (3)
Illustration of bounds on Ja lime--o MSE(A) for the generalized Gaussian family parameterized by 8 > 1. Here, Cnon denoles the lower bound this quantity for non-adaptive protocols, whereas Cudape denotes the corresponding upper bound for our simple adaptive protocol. As 3 increases, Cnon decreases while Cadapt increases. The curves intersect at 8 1.8488. This allows us to conclude that non-adaptive protocols are provably suboptimal compared adaptive protocols for 3 < 1.8488.
Figure 3:
Figure 4: Ratio of constants Caan/Cadaa /adapt for the unit-variance Generalized Gaussian Distribution (GGD) as a function of the shape parameter 8 E [1.1, 1.85.. We compute Cnon 0.1034 TUx)
(non-adaplive
lower-bound constant) and Cadaps 4/x(0)a (adap- Live constant) from the unit-variance densily fx. The curves cross al 3 1.85. For 3 < 8" the non- adaptive lower bound exceeds the adaptive constant (ratio 1), while for B > 3 the adaptive constant. is larger (ratio < 1).
For the Generalized Gaussian family of distributions (GGD)
B 2aT(1/B) exp (-(1=://a))),
fx(x)
+
r(/s) F(3/3)
(21)
the density has zero mean and unit variance for all O, and is strictly log-concave for Note that 3 gives the standard normal. For this family, we find that the non-adaptive asymptotie constant is guaranteed to be larger than the adaptive constant throughout the range < B < 1.85. For taibter-tailed shapes with / > 1. 1.85, this incquality no longer holds, and the adaptive constant becomes smaller. See Fig. 3 and Fig. 4. We conjecture that the lower bound is weak for 8 > 1.85 and there is scope for improvement.
Note that Theorem 3.2 explicitly requires strict log-conoos cog-ooiaaiity. The Laplace distribution is log-concave but not strictly log-concave. Therefore, the adaptive lower bound remains valid for this distribution, while the non-adaptive lower bound does not apply since it requires strict log-concavity.
4.4 Communication and computational complexity
Both the non-adaptive and adaptive protocols require only one bit of communication per user, yiclding a total communccatio cost of bits. The adaptive protocol involves two rounds. In the first round, ni + n2 users transmit one-bit. messages based on local thresholding operations. The last ng users require access to the estimate Ae formed from the earlier transmissions. This can be implemented in several standard ways. Under sequential model, the last ny users may view the previously posted one-bit messages and compute de directly. In settings without such shared access, the server may broadcast. a single real nunber to these users, which incurs only a constant amount of additional communication (assuming a broadcast model of communication). The computational cost also minimal. Each user performs an O(1) thresholding step, and the server aggregates O(n) one-bit messages and then performs a constant mumber of real-valued operations. Hence the overall computational complexity is O(1) for each user and (n)) for the server.
4.5 Increasing bit budgets provide marginal gains
While the main focus of our work on one-bit compressors, it helpful compare our bounds on the asymptotic MSE with corresponding lower bound under the centralized selling, the case where
14

---

Published in Transactions on Machine Learning Research (Jan/2026)
communication constroints are imposed the users. This helps assess whether allowing more than bit per sample can yield substantial reduction in MSE.
The Fisher information for the location in the location-scale family for a given >> 0 is
1 J [[ de. T=(x;;)) σ² JR fx(2)
For any regular estimator based on iid. samples, the Cramér Rao bound implics that the MSE of any unbiased estimator is
[fx(2)13 dz.
MSE(Pn) n (fx)) J(fx)
fx(x)
Equivalently, the Van- Trees inequality (Gill & Levit, 1995) yields an asymptotic lower bound for any (po- tentially biased) estimator
lim nMSE(Pp) & J(fx)'
where the expectation taken with respect to fx.uo for any prior density on So for which the above exists.
Thus 1/x(xx can be thought of as the best 1/n constant achievable in the absence of quantization.
Fisher Bound (No Quantization)
Bound (No Quantization
aduptive
Non-adaptive
Aduptive
10
Adapeive
Lower bound on MSB
Lower bound on MSE
10
10
2500
5000
7500
10000
12500
15000
17500
2000D
2500
5000
7500
10000
12500
15000
17500
20000
Number
Number of
(a) Generalized Gaussian ( = 1.5)
(b) Logistic
10
Fisher Bound (No Quantizztion)
Fisher Bound (No Quantization
Non-adsptive
Non-adaptive LB
1
Adaptive
Aduptive LB
Lower bound on MSE
Lower bound MSB
10
10-3
10-3
10
2500
5000
7500
10000
12500
15000
17500
20000
2500
5000
7500
10000
12500
15000
17500 20000
Number
(c) Hypsecant
(d) SIN2
Figure Fisher-information lower bound (no quantization) compared with the adaptive and non-adaptive one-bit. lower bounds for four distributions. All curves decay 1/n; differences arise only through the proportionality constants. The adaptive lower bound is tight, which implies that increasing the number bits per user can only provide minor improvement in the asymptotic MSE.
15

---

Published in Transactions on Machine Learning Research (Jan/2026)
Distribution
CF1
Cadp
Cnon
Gaussian (GGD, 8 1.5)
0.9126
1.1035
2.5806
Logistic
0.9119
1.2159
1.1619
Hypersccant
0.8106
1.0000
1.1239
SIN2
0.9534
1.3868
4.1982
Table 3: Normalized constants (n MSE)/o² for the Fisher-information bound, the adaptive one-bit bound, and the non-adaptive bound, evaluated using standardized densities with ja 0 and
Figure 5 illustrates the Fisher-information bound (centralized setting) together with the adaptive and non- adaptive one-bit lower bounds derived. All bounds exhibit the same dependence n, The adaptive one-bit curve remains close to the centralized benchmark. We also report
OFI = J(fx)
Cadp = (0)
Conn
T(xx)
in Table 3.
The results exhibit consistent pattern across all distributions. The adaptive one-bit. method altains a constant close the Fisher-ifoormation limit, which represents the best performance achievable without quantization. Consequently, the potential gain from transmitting more than one bit per sample limited in this setting.
The behavior of the non-adaptive bound is determined by the functional T(fx), and we do not claim optimality of this bound. As seen in Table 3, the constant Cnon may be either larger or smaller than the adaptive constant, depending on the underlying distribution. The comparison with the Fisher information bound should therefore be understood a consoquence of the particular form of our non-adaptive bound, rather than as fundamental limitation of non-adaptive schemes.
5 Simulation Results
We validate our theoretical bounds by empirically evaluating the worst-case and average (over μ) MSE for four representative symmetric, strictly log-concave source distributions: generalized Gaussian with 8 = 1.5, Logistic, Hyperbolic secant, and the custom density in equation 20. Each experiment averages over Nirials = 2000 trials. The unknown mean j is varied over the interval [-2.5, 2.5] increments of 0.5, while the standard deviation is fixed
2.
Quantization thresholds 01 and 0g are precomputed from the known range (Amin Mmax) to ensure consistency across trials. Specifically, we adopt the equal-thirds rule:
82 = Mmin 3/ (Pmax Pmii))
0 Umin + (Mmax Mminn,
Among all possible choices of two thresholds, this rule minimizes the maximum distance from any μ e [Mmins [max]] to its nearest threshold, expressed by
max min 1p 0z). 0 palmmm (E(1)
min
In addition, for symmetric strictly log-concave scale-location densities, placing thresholds symmetrically around the mid-range (Mmin M/mx)/22 prevents saturation of the empirical c.d.f. estimates F1, F2 and keeps the Bernoulli variances F5 - F,) bounded away from zero. This yields stable estimation of both y and a, Finally, precomputing thresholds from the range guarantees fairness across trials and enforces strict non-adaptivity, which is essential when contrasting ing against adaptive protocols. Our implementation code publicly available on GitHub and can be accessed at Kumar Vatedka (2026b)
while remaining distribution-agnostii
The simulation curves in Fig. demonstrate the superiority of adaptive protocols over non-adaptive proto- cols. Although the lower bounds that derive asymptotic and are not actually valid for small n, we
16

---

Published in Transactions on Machine Learning Research (Jan/2026)
10
Worst- (Adaptive)
10
Worst-Case (Adaptive)
Mean Squared Error (MSE)
Average-Gass (Adaptive)
Mean Squared Error (MSE)
Averago-Case (Adaptive)
10
Worst- Case (Non-adaptive))
100
Warst-Case (Non-adaptive)
w... Average Case (Non-adaptive))
Average Case (Non-adaptive)
10-1
Asymptotic (Non-aéaptive)
10
Asymptotic (Non-adaptive)
Bound (Adaptive)
Lower Bound (Adaptive)
1
Lower Bound (Non-adaptive)
10-2
Lower Bound (Non-adaptive)
10
10-4
10"
10-4
8000
16000
24000
32000
40000
0
8000
16000
21000
32000
40000
Total Number Users (x)
Total Number of Users (1)
(a)
Generalized Gaussian with B 1.5
(b) Logistic
10a
10
Worse- Case (Adaptivv)
Werst- Case (Adaptive)
Mean Squared Error (MSE)
Average-Casn (Adaptive)
Mean Squared Error (MSE)
Average Case (Adaptive)
Worst: Case (Non (Non-adaptive)
109
Worst-Case (Non-adaptive)
10
Average- (Non-adaptive)
Averago-Cas (Non-adaptive)
Asymptotic (Non-adaptive)
10-1
Asymptotic (Non-adaptive)
10
Lower Bound (Adaptive)
Lower Bound (Adaptive)
Lower Bound (Non-ackaptive)
10-2
Lower Bound (Non (Non-adaptive)
10-2
10-3
10-3
10-4
10-1
SU00
16000
24000
32000
40000
8000
16000
24000
32000
40000
Total Number of Users (n)
Total Number of Users (n)
(c) Hypsecant
(d) Sin2
Figure 6: Worst-case and average (over μ4) MSE across four source distributions under one-bit protocols. Benchmarks are computed using fx (0) for each family; adaptive and non-adaptive curves are shown according to the legend. The curve labeled Asymptotic (Non-adoptive) represents the asymptotic value of MSE predicted by Theorem 3.1.
nevertheless plot these and can be interpreted as the first-order approximations of the lower bounds. We also observe that in the case of the generalized Gaussian, the plot for empirical worst-case MSE intersects the lower bound for the asymptotic MSE for non-adaptive estimators. It should be noted that the lower bound for non-adaptive estimators could potentially be loose, which illustrates that our simple adaptive estimator beats the best non-adaptive estimator even for finite n.
In the non-adaptive protocol, the total number of users n is split into two disjoint groups n. Kin and n2 Kgn with K1 + K₂ 1. Since the protocol remains consistent for any fixed (K1, K2), we explored a range of allocations to study the effect of the split on finite-sample performance. In particular, (K1, 100110, 0.90), (0.20, 0.80), (0.30, 0.70), (0.40, 0.60), (0.50, 0.50)). The resulting curves show that different splits slightly shift the MSE at moderate sample sizes, but the overall asymptotic behavior is unchanged, and in all cases the non-adaptive MSE remains strictly above the adaptive benchmark. This confirms that the suboptimality of non-adaptive protocols is inherent and not due to a particular choice of partition.
considered
In the adaptive protocol, users are divided into three groups of sizes ni, n2, na with ni + 122 + nia n. The first two groups provide coarse estimates (R), which are then refined using the remain- ing users. To check robustnoss, we considered small fixed first-stage allocations with (K1, K2) e {(0.05, 0.05), 10, 0.10), (0.15, 0.15)), showing that even a small initial budget is sufficient for effective re- finement. We also evaluated the theoretically motivated split n = n2 = na/ log ny from Theorem 4.1, which achieves the asymptotic MSE. Together, these experiments suggest that the adaptive scheme is both practical (performing well with small first-stage budgets) and enformationthhoocticalll optimal.
We also compute asymptotic constants Gnon and Cadapt for the four families, and are tabulated in Table 2.
17

---

Published in Transactions on Machine Learning Research (Jan/2026)
10a
10a
(K- 0.10, Kg 0.30)
Worst NA (Ki 0.10, K; 0.90)
Mean Squared Error (MSE)
10
Worst NA (K; 0.20, 0.80)
Mean Squared Error (MSE)
104
Worst NA (K. 0.20, K3 0.80)
Worst NA [K] = 0.30 K. = 0.70)
Worst NA (K: 0.30, K; 0.70)
10"
Werst NA (K) 0.40, 0.80)
109
Worst (K:
K2 0.60)
Werst NA (K₃ 0.30,
Worst NA (K) 0.50, K2 0.50)
10
(Non-adaptive)
10
Lower Round (Non-adaptive)
10-2
10-2
10-3
10
10
8000
16000
24000
32000
40000
0
8000
16000
21000
32000
40000
Total Number Users (x)
Total Number of Users (m)
(a)
Generalized Gaussian with 1.5
(b) Logistic
108
10a
Worst NA (K₃ - 0.10, K2- 0.90)
---
Worst NA (Ki 0.10, Ks 0.90)
Mean Squared Error (MSC)
Worst NA (K, 0.20, Kg 0.80)
Mean Squared Error (MSE)
Worst NA (K) 0.20, K; 0.80)
10
Werst NA (K) 0.30, 0.70)
Worst NA (K; 0.30, K; 0.70)
(Ki 0.40, 0.60)
Worst (Ki 0.40, Ks 0.60)
10a
109
Worst NA (K₃ 0.30, K2 = 0.50)
Worst NA (K) 0.50, Ks 0.50)
Lower Bound (Non-adaptive)
Lower Bound (Non-adappivv)
10
10-1
10-2
10-2
10-3
10-3
10
SU00
16000
24000
32000
40000
8000
16000
24000
32000
40000
Total Number of Users (n)
Total Number of Users (n)
(c) Hypsecant
(d) Sin2
Figure 7: Non-adaptive MSE for symmetric, strictly log-concave distributions with different Ki, K2 allocations. Each subfigure shows worst-case MSE alongside the lower bound TUx) cases.
a², A consistent positive gap is observed across all
Finally, Figs. 7 and 8 analyze the effect varying (n1, n2). The eight combined plots show worst-case MSE on a log scale across all four distributions. In the non-adaptive case, we fix (01, as described earlier but vary K1 = ni/n and K₂ = ng/n.
Fig. 9 illustrates the performance of the allocation strategy from Theorem 4.1, where n1 n2 n2/ log ng. Here, both worst-case and average MSE curves gradually approach the lower bound. This confirms that the theorem-based allocation achieves optimality, and that even with alternative user splits, the asymptotic behavior of the adaptive scheme remains essentially unchanged.
For the generalized Gaussian source with 1.50 and unit variance, Fig. 10 illustrates the worst-case MSE as μ E 2-2,5, 2.5] with 40000. Thresholds are fixed once using the equal-thirds rule (0, 0.8333, O2 0.8333). The MSE achieved by the adaptive protocol is lower the non-adaptive lower bound for large enough n, providing clear empirical validation of our results.
We also examine the standard normal, which corresponds to the special case of the generalized Gaussian distribution with 3 = 2. As shown in Fig. 11, using the same experimental setup as Fig. 6, the non-adaptive lower bound is observed to lie below the adaptive bound. However, we conjecture that the lower bound for non-adaptive protocols can be improved.
Remark 5.1. These experiments also show how the asymptotic behavior appears in the finite-user setting, Our results identify the leading term
C
MSE(n) + o(1/n).
with C determined by the choice of protocol and the underlying source distribution. Although this ex- pression does not capture higher-order corrections, the simulations indicate that the C/n approximation
18

---

Published in Transactions on Machine Learning Research (Jan/2026)
AD (K; 0.05, 0.05)
10
Worst (K: K; 0.05)
Mean Squared Error (MSE)
[K- - 0.10, 0.10)
Mean Squared Error (MSE)
(K, 0.10, K; 0.10)
Warst AD [K] - 0.15, Kg 0.15)
Worst AD [K] 0.15, K3 0.15)
109
10e
Worst AD (a: = ma/ log ma)
Worst AD (t) No ma/ log Ra)
Lower Bound (Adaptive)
Lower Bound (Adaptive)
10-1
10
10-2
10-2
10-3
10-3
10-4
10-1
8000
16000
24000
32000
40000
0
8000
16000
21000
32000
40000
Total Number Users (x)
Total Number of Users (m)
(a)
Generalized Gaussian with 1.5
(b) Logistic
10a
Worst AD [K2 0005, K2- - 0.35)
10
Worst AD [K] 0.05, K; 0.06)
Mean Squared Error (MSL)
10a
Worst AD (K, 0. 10, Kg 0.10)
Mean Squared Error (MSE)
Worst AD (K] 0.10, K3 0.10)
Worst AD (K) 0.15, 0.15)
109
Worst AD (K) 0.15, Iss 0.15)
109
my! log ma)
Worst (m) may Rd)
Lower Bound (Adaptive)
Lower Bound (Adaptive)
10-1
10-1
10-2
1
10-3
10-4
10-4
10-4
SU00
16000
24000
32000
40000
8000
16000
24000
32000
40000
Total Number of Users (n)
Total Number of Users (n)
(c) Hypsecant
(d) Sin2
Figure 8: Adaptive MSE across four symmetric, strictly log-concave distributions. Worst-case closely follow the 2
benchmark 4xx () confirming asymptotic optimality.
remains accurate for moderately large values of n. Across all distributions considered, the empirical curves follow the 1/n behavior, indicating that the asymptotic constants closely describe the observed finite-sample performance.
6 Conclusion and Future Work
In this work, we derived the asymptotic mean squared error (MSE) for estimating the location parameter of distributions from the scale-location family under one-bit communication constraints, with primary focus the case where the variance is unknown. Our main contribution is the design and analysis of both non-adaptive and adaptive protocols for mean estimation. As byproduct, we also proposed simple non- adaptive protocol for the standard deviation and derived its asymptotic MSE. We note, however, that our results for variance estimation apply only to the non-adaptive setting, and we do not claim optimality for this estimator. We also derived a non- non-parametric 1-bit estimator for the mean, but observed that the MSE scales only as w1/n),, which worse than our simple non-adaptive estimator.
For broad class of symmetric strictly log-concave distributions, we proved that one-bit adaptive protocol achieve asymptotic MSE smaller than presented in Theorem 4.3, and designed adaptive scheme that attains this bound, thereby establishing its information-theorctia optimality. In contrast, we showed that one-bit non-adaptive protocols necessarily incur strictly larger MSE for many such distributions, and we quantified the exact performance gap between optimal non-adaptive and adaptive schemes in terms of a distributionn-deeendeett constant T(fx).
Our numerical comparison with the unquantized informaifoo bound shows that the adaptive one-bit scheme already operates close to the best performance achievable without communication constraints. This
19

---

Published in Transactions on Machine Learning Research (Jan/2026)
10a
10
Worst AD (1y no/ (g)
Worst /a/ log ma)
Mean Squared Error (MSSE)
Aug (fq Ni ma/ mt)
Mean Squared Error (MSE)
Aug (f) 12 my/ log 96)
10"
Lower Bound (Adaptive)
100
Lownr Bound (Adaptive)
10-1
10
10-3
10-2
10
10-3
10
10-1
8000
16000
24000
32000
40000
0
8000
16000
21000
32000
40000
Total Number Users (x)
Total Number Users (1))
(a)
Generalized Gaussian with 1.5
(b) Logistic
10a
Wonst AD (s1 R2 ni/ log
10
Worst AD (o) log
Mean Squared Error (MSC)
Aug AD (fo si/ (g))
Mean Squared Error (MSE)
AD ing my/ log ms)
10a
Lover Bound (Adaptive)
109
Bound (Adaptive)
109
10-1
10
10-2
10-2
10-3
10-3
10-4
10-4
SU00
16000
24000
32000
40000
8000
16000
24000
32000
40000
Total Number of Users (n)
Total Number of Users (n)
(c) Hypsecant
(d) Sin2
Figure Adaptive MSE four symmetric, strictly log-concave distributions with the special split ny n2 na/ log ny used in Theorem 4.1. Both worst-case and average MSE approach the benchmark ( asymptotically.
o²
Non-adaptive
10
(Adaptive)
Maan Squared Enor (MSE)
0y-333333
Adaptive
Mean Squared Error (MSE)
109
Averago-Case (Adaptive)
Worst Case (Non (Noo-adappiee)
0,8333333
Average Case (Non-adaptive)
10
10
Asymptotic (Non-adaptive)
Lower Bound [Adaptive)
Lower Bound (Non-adaptive)
10-2
10-4
10-4
2
8000
16000
24000
32000
40000
Total Number of Users (n)
Figure 10: MSE versus the mean js for the generalized Gaussian source with shape parameter 1.50 and unit variance, using 40000 users. Thresholds are fixed at 0, -0.8333 and 0.8333, and μ varied over [-2.5, 2.5].
Figure 11: Worst-case and average MSE for the standard normal (GGD with $ 2) under one-bit protocols. The Asymptotic
curve is the asymptotic MSE predicted by Theorem 3.1. Although the lower bound for non-adaptive protocols is lower than that for adaptive protocols, we conjecture that lower bound in fact loose and can be improved.
suggests that, within the strictly log-concave family, the improvement in MSE obtained by transmitting more than one bit per sample is limited.
20

---

Published in Transactions on Machine Learning Research (Jan/2026)
We believe that the lower bound for non-adaptive protocols is not tight, and can be improved. We conjecture that for all symmetric log-concave distributions fx(x) e- where & is upper bounded by some fixed polynomial, the asymptotic minimax for non-adaptive estimators is strietly higher than that achieved by our adaptive estimator.
While our analysis addresses the scalar mean estimation problem, several extensions remain open. In partic- ular, extending the lower bound techniques to high-dimensional vectors, exploring protocols under multi-bit communication budgets (e.g., b bits per sample), and developing adaptive strategies for optimal variance (or scale) estimation promising directions for future work. Our techniques could potentially also be used to derive upper and lower bounds for ostimation of higher-order moments or more general exponential families. Even in the context of mean estimation, deriving tight bounds on the minimax MSE for general log-concave distributions that hold for finite n remains an open question.
References
Jayadev Acharya et al. Inference under Information Constraints Lower Bounds from Chi-Square Contrac- tion, 2020a.
Jayadev Acharya et al. Inference under Information Constraints II: Communication Constraints and Shared Sandomness. IEEE Transactions on Information Theory, 66(12):7856 7877, 2020b.
Jayadev Acharya et al. Inference under Information Constraints III: Local Privacy Constraints. 1EEE Journal on Selected Areas in Information Theory, 2(1))253-267, 2021.
Jayadev Acharya al. Optimal rates for nonparametric density estimation under communication constraints. IEEE Transoctions on Information Theory, 70(3):1939-1961, 2023.
Dan Alistarh et al. QSGD: Commuicattion Efficient SGD via Gradient Quantization and Encoding, Advances in Neural Information Processing Systems, 30, 2017.
Chen Amiraz, Robert Krauthgamer, and Boaz Nadler. Distributed sparse normal means estimation with sublinear communication. Information and Inference: Journal of the IMA, 11(3):1109 1142 2022.
Nithish Suresh Babu et al. Unbiased quantization of the L1 ball for communiattion-cffiienn distributed mean estimation. In Proceedings of The 28th International Conference on Arlificial Intelligence and Stalislics, volume 258 Proceedings of Machine Learning Research, pp. 2270-1275 PMLR, 2025.
Leighton P. Barnes et al. Fisher information for distributed estimation under a blackboard communication protocol. In Proceedings of the IEEE International Symposium on Information Theory (ISIT), pp. 2704 2708. IEEE, 2019.
Leighton P. Barnes et al. Lower bounds for learning distributions under communication constraints via fisher information. Journal of Machine Learning Research, 21(26)):1330, 2020.
Heather Battey et al. Distributed Testing and Estimation Under Sparse High Dimensional Models. Annals Of Statistics, 46(3):1352, 2018.
Ran Ben-Basat et al. Accelcrating federated learning with quick distributed mean estimation. Proceedings of the 41st International Conference on Machine Learning, volume 235, pp. 2369 2394. PMLR, 2024.
Jeremy Bernstein et al. signSGD: Compressed Optimisation for Non-convex Problems. In International Conference on Machine Learning, pp. 560-560000 569. PMTR, 2018.
Allan Birnbaum. Statistical theory for logistic mental test models. ETS Research Bulletin Series, 1968.
Tim Bollerslev. A conditionally hetcroskedastic time series model for speculative prices and rates. Review of Economics and Statistics, 09(3):542-541) 1987.
Mark Braverman, Ankit Garg, Jieming Mao, and David P Woodruff. Communication constraints in dis- tributed statistical estimation. In STOC, 2016.
21

---

Published in Transactions on Machine Learning Research (Jan/2026)
Jean Bretagnolle and Catherine Huber. Estimation des densités: risque minimax. Zeitschrift für Wahrschein- lichkeitstheorie und Verwandle Gebiele, 47(2):119-1377 1979.
T. Tony Cai and Hongji Wei. Distributed adaptive gaussian mean estimation with unknown variance: Interactive protocol helps adaptation. Annals of Statistics, 50(4):1992 2020, 2022a.
T Tony Cai and Hongji Wei. Distributed Nonparametrie Function Estimation: Optimal Rate of Convergence and Cost of Adaptation. The Annals Of Slatistics, 50(2):698-72) 725, 2022b.
T. Tony Cai and Hongji Wei. Distributed gaussian mean estimation under communication constraints: Optimal rates and communicttion-effiieett algorithms. Journal of Machine Learning Research, (3(3
1 1-63, 2024.
John Y Campbell, Andrew W Lo, and A Craig MacKinlay. The Econometrics of Financial Markets. Prince- ton University Press, 1997.
Carlos M Carvalho and Woonghee Hahn. Arbitrage-free forecasting with nonparametric bayesian models.
Journal of Econometrics, 2018.
George Casella and Roger Bergor. Statistical Inference. Duxbury Press, 2002.
Hao Chen and Pramod K Varshney. Performance Limit for Distributed Estimation Systems With Identical One-Bit Quantizers. JEEE Transactions On Signal Processing, 58(1):466-477) 2009.
Mingzhe Chen et al. Distributed Learning in Wireless Networks: Recent Progress and Future Challenges. IEEE Journal on Selected Areas in Communications, 39(12):3579 3605, 2021.
Tianyi Chen et al. LAG: lazily aggregated gradient for communccttion-effcceet distributed learning. vol- ume 31, pp. 5050-5060, 2018.
Mazen Dana and John C Duchi. One-bit distributed mean estimation: Sharp rates under general distribu- tions. IEEE Transactions on Information Theory, 2022.
Angus Deaton and John Muellbauer. Economics and Consumer Behavior. Cambridge University Press, 1980.
Mare Deisenroth and Jun Wei Ng. Distributed Gaussian Processes. In International Conference on Machine Learning, pp. 1481 1490. PMLR, 2015.
John C Duchi, Michael Jordan, and Martin Wainwright, Minimax optimal procedures for locally private statistical estimation. Journal of the Americon Statistical Association, 2018.
Rick Durrett. Probability: theory and examples, volume 49. Cambridge university press, 2019.
Xin Fan, Yue Wang, Yan Huo, and Zhi Tian. 1-Bit. compressive sensing for efficient federated learning over the air. IEEE transactions on wireless communications, 22(3):2139 2155, 2022.
Richard D. Gill and Boris Y. Levit. Applications of the trees inequality: bayesian cramér rao bound. volume 1, pp. 59-79, 1995.
Patrik Guggenberger and Michael Jansson. Robust inference for heavy-tailed economic data. Econometricn, 2022.
Yanjun Han et al. Geometric lower bounds for distributed parameter estimation under communication constraints. volume 67, pp. 8248 1188-8263, 2021.
Sariel Har-Peled. Geometric Approzimation Algorithms, volume 173 of Mathematical Surveys and Mono- graphs. American Mathematical Society, 2011.
Wendi Rabiner Heinzelman et al. Energy-efficient communication protocol for wireless microsensor networks.
In Proceedings of the 33rd Annual Hawaii International Conference on System Sciences, volume 2, pp. 10. TEFF, 2000.
22

---

Published in Transactions on Machine Learning Research (Jan/2026)
Minjeong Jeon and Sophia Rabe-Hesketh. Bayesian analysis of multiddimensional item response models. Psychomelrika, 2019.
Peter Kairouz et al. Advances and open problems in federated learning. volume 14, pp. 1 1-010 2021.
Alon Kipnis and John C. Duchi. Mean cstimation from onc-bit measurements. IEEE Transactions on Information Theory, 68(9))6276 6296, 2022.
Vladimir Koltchinskii et al. Functional estimation in log-concave location families. In High Dimensional Probability IX, pp. 393-440, 2023.
Jakub Koncčný and Peter Richtárik. Randomized distributed mean estimation: Accuracy vs. communication. Frontiers Applied Mathemalics and Stalistics, 4:62, 2018.
Jakub Konečný, H Brendan McMahan, Daniel Ramage, and Peter Richtárik. Federated optimization: Dis- tributed optimization beyond the datacenter. arXiv preprint 1.1:v:551..08575, 2016.
Ritesh Kumar and Shashank Vatedka. Communicaiion-cnsstenae concave distributions. In 2023 National Conference on Communications (NCC), pp. 1-6, 2023.
distributed mean estimation of log-
Ritesh Kumar and Shashank Vatedka. Recorded video. http:///ttve..oogl.....o///v////
1XPKRcyTaptgpl2X KSeCTwkru7-Srkto 2026a.
Ritesh Kumar and Shashank Vatedka. Github repository. 2026b.
httpas//gtttaab.cc//ttthehz
Ivan Lau and Jonathan Scarleu. Sequential 1-bit mean estimation with near-optimal sample complexity. arXiv preprint arXit:2509.2194/ 2025.
Lucien Le Cam. Convergence of estimates under dimensionality restrictions. The Annals of Statistics, pp. 38 38-53, 1973.
Lucien Le Cam. Asymplotic Methods in Statisticnl Decision Theory. Springer Series in Statistics. Springer, 2012.
Erich L. Lehmann and George Casella. Theory of Point Estimation. Springer Texts in Statistics. Springer, 2006.
Tian Li et al. Federated Learning: Challenges, Methods, and Future Directions. IEFE signal processing magazine, 37(3):50 60, 2020.
Zhan Liu et al. Communication Effiiiii Efficient Distributed Estimation for High- Dimennoimaliooal Large-Scale Linear
Regression. Metrika, 86(4):455-485, 2023.
Zhi-Quan Luo. Universal Decentralized Estimation in a Bandwidth Constrained Sensor Network. IEEE
Transactions on information theory, 51(6):2210 2219, 2005.
Prathamesh Mayekar et al. Wyner-ziv estimators: Efficient distributed mean estimation with side- information. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Reseurch, pp. 3502 33100. PMLR, 2021.
Daniel McFadden. Conditional logit analysis of qualitative choice behavior. Frontiers in Econometrics, pp. 105-142, 1974.
Brendan McMahan et al. Communiattion-Efftiii Efficiien Learning of Deep Networks from Decentralized Data. In Arlificial Intelligence and Slatistics, pp. 1273 1282. PMLR, 2017.
Coustantin Niculescu and Lars-Erik Erik Persson. Conver Punctions and Their Applications. CMS Books in Mathematics. Springer, 2006.
Yury Polyanskiy and Yihong Wu. Information Theory: From Coding to Learning. Cambridge University Press, 2024.
23

---

Published in Transactions on Machine Learning Research (Jan/2026)
Mohammad Reza Rahmani et al. Fundamental limits of distributed covariance matrix estimation under communication constraints. In Proceedings of the 41st International Conference on Machine Learning, pp. 41927 41958, 2024.
Georg Rasch. Probabilistic Models for Some Intelligence and Attainment Tests. Danmarks Paedagogiske Institut, 1960.
Alejandro Ribeiro and Georgios B Giannakis. Bandwidth- Distributed Estimation for Wireless Sensor part II: Unknown Probability Density Function. IEEE Transactions Signal Processing, 54(7))2784 2796, 2006.
Frank Seide et al. 1-bit stochastic gradient descent and its application to data- titta-prraalel distributed training of speech dnns. In Interspeech, pp. 1058-1062. Singapore, 2014.
Jaimin Shah et al. Generalized linear models with 1-bit measurements: Asymptotics of the maximum likelihood estimator. In ICASSP 2025 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 1-5. IEEE, 2025.
Justin Sirignano and Rama Cont. Universal features of price formation in financial markets. In Proceedings of the National Academy of Sciences, 2019.
Ananda Theertha Suresh et al. Distributed mean estimation with limited communication. In Proceedings of the 34th International Conference Machine Learning, volume 70, pp. 3329-3337, 2017.
Hanlin Tang et al. 1-bit Adam: communication efficient large-scale training with adam's convergence speed. International Conference on Machine Learning, pp. 10118-10121 PMLR, 2021.
Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer Scries in Statistics. Springer, 2009.
Harry L. Van Trees. Delection, Estimationn, and Modulation Theory, Part I. John Wiley & Sons, 2004.
Harsh Vardhan and Arya Mazundar. Collaborative compressors in distributed mean estimation with limited communication budge, 2025. URL http:////ppprreveeeeeefffrrrrmm wttp://foooumiddddh11000..
Parvathinathan Venkitasubramanian et al. Quantization for maximin are in distributed estimation. 1EEE Transactions on Signal Processing, 55(7):3596-3000 2007.
Roman Vershynin. High-Dimensionns Probability: An Introduction with Applications in Data Science, Cam-
bridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
Hongyi Wang et al. Atomo: Communicaiion-ellciend learning via atomic sparsification. In Advances in Neurul Information Processing Systems, volume 31, pp. 9872-988999 9883, 2018.
John Wright and Yu-Lung Tang. Lecture 5: Quantum fidelity. Berkeley CS294 course lecture notes, 2024. Available at https: httpsss////ppplpe// eecs. berkeley. berkeley.edu/-jjsseeeeeeeeeeeeee wwwssrgghhgggattullleamiingeeeeo scribbt//0motes///cctee000,, pdf.
Yihong Wu. Information--heorrlicc methods for high-dimensionall statistics. Lecture notes, Yale University, 2020. Available at https://www.sttt
httb///yw552/eeaccnn/////
Yue Yu and Renate Meyer. Bayesian dynamic models for heavy-tailed financial returns. Bayesian Analysis, 2019.
Ram Zamir. A proof of the fisher information inequality via a data processing argument. JEEE Transactions on Information Theory, 4433) 1998.
Yuchen Zhang al. Communicttion-effiieee algorithms for statistical optimization. In Advances in Neural Information. Processing Systems, volume 25, pp. 3321 23213, 2012.
24

---

Published in Transactions on Machine Learning Research (Jan/2026)
Yuchen Zhang al. Information-theoreti lower bounds for distributed statistical estimation with commu- nication constraints. In Aduances in Newral Informalion Processing Systems, volume 26, pp- 2328-2336 2013.
Guangxu Zhu et al. One-bit over-the-air aggregation for communication-elfiieent federated edge learning: Design and convergence analysis. IEEE Transactions on Wireless Communications, 20(3):2120 2135, 2021.
A Proof of Theorem 3.1
We use the delta method (Casella & Berger, 2002, Theorem 5.5.24) and standard limit thcorems to prove this result. Using the central limit theorem (Casella & Berger, 2002, Theorem 5.5.14), we can write:
/n1
Fi
Fx
01
4 N (0,0)).
0
v
n2
F2
Fx
82 02-H4
4 N (0,
Using the delta method (Casella & Berger, 2002, Theorem 5.5.24), we can write:
81 11
4
dF (2)
n1
01
W1:
0
dz
Fx (L-P)
(22)
(6)-
02
11
d
dFx (2)
222
a1
W2:
dz
Fx
22
where w, o7) for i 1,2. After solving equation 22 we get:
m
(1 -
01
11
4
N
0,
fx H1)
of
(23)
0 p1
v 122
Q1
4
0,
f
62
Let us define a function & as:
0n62 - -022
E(a),
(24)
(1
012
Using the delta method (Casella & Berger, 2002, Theorem 5.5.24), we can write:
Vn [(()))0)) -
0 11-P 02 -4 -
)) 4 N Vo.
where n = n2 + n2. Now we have
a (02 - 11) (01 (1)
T
VE
01 02
0 0
0 #
0 p
0g
25

---

Published in Transactions on Machine Learning Research (Jan/2026)
and
Ki f21
(2("1-))
=
K2 121 "
0
Recall that n1 = Kin and n2 = Kzn, where K₁ and K2 are constants independent of n, and K + K2 = Now
o²
Kio
K20
(02 - u)²
2 +
(0, 14²
(01 02)
1 91
12
02
Since we have
81 1
82 p
p4
0
we can write
Vnlu Pc) $ N
0,
o²
(02 u)²
Kio
2 + (0) u12
K202
(0,
0z)2
82
12( (2-
Therefore, scheme will attain asymptotic Mean Squared Error (MSE) of:
o²
Kiož
K202
lim n. MSE(A.) (01 02) 8
(02 11)
+(01
11)²
1 (
12( 2ー
This concludes the proof of the first part.
We now prove the second part. Using the continuous mapping theorem (Casella & Berger, 2002) in equa- tion 23, we can write
01 -00--))
)) 4 N
Ki0
K202
Vn (al (al- 02)
+
(25)
P2
1
Now we define a function
((x) 02
Then, its derivative
01
02
- 02
v/
0 02
Applying the delta method (Casella & Berger, 2002), we can write
Vn v(ai- (vlai- -22) - 8 (
02 )) 4 N (0(1),-000))
ot
(
Kio
K202
))
(0, (1,
+
(20))
(26)
This gives us
Vnlo - dc) SN N (1,,0)-0 02)3 )
at
Kio
K2o
f (1-24)
f7( (22=1))
Therefore
)
Ki0?
K203
lim n MSE(G.)
(10, - 02)z
13
(1-#4)
1R (2-=
This concludes the proof of the second part of the theorem.
26

---

Published in Transactions on Machine Learning Research (Jan/2026)
B Upper Bound on Squared Hellinger Distance
= e- be a symmetric log-concave distribution, with o being strictly convex, difserentiable, and upper bounded by a polymomial.. Let fx a and Jxx,, a be the distributions corresponding to the two hypotheses, where p+, are defined in equation 11.
Theorem B.1. Let =
Let Ti be any randomized function from {0, 13 that chosen independently of Xi, and PV. Py, be the distribulions corresponding to Y, (X,) when X₃ drawn according to f' and Jx respeclively.
Then,
HP Pv,) & 2 [[ Φ (0)
where as O. Here, h(x) - 2 26' fx)) and h* max h(x).
To prove this theorem, we first introduce auxiliary functions that will be used in the analysis. Our construc- tion partly follows (Cai & Wei, 2022a).
We define the maximum pointwise density difference
a
+ x)
(27)
DeR
For 0 < a < 0: let
A.(a) fxe |fx + - -x]=- > a}.
(28)
and
za(c)= = sup Ac(a).
(29)
Let
(x(e)
O, [x(x+e) [x-
af
9+ (x,
fx (mtt)
Ac(a),
0,
otherwise,
(x(e)
of
9 ax)
fx
(m-c)
x Ar)a), otherwise.
(30)
0.
A direct calculation shows
9 = fx(x
9 (x. da = fx(x+(),
Thus,
1
p
a 1
x
f
fx
g+
da,
30
and
1
14
1
H
fx
9
da.
0
0
J0
0
σ
Define the likelihood ratio
sup fx(x c) Ra
(31)
zEA,(a) fx(x - c)
The next results show how R₂ can be used to bound the squared Hellinger distance.
6Te value of the degree is particularly important here. We only require the degree be finite.
27

---

Published in Transactions on Machine Learning Research (Jan/2026)
Lemma B.2. Let IT; R RR, be any (possibly randomized) non-adaptive encoder, and let (o.(--))gg((111 be in equation 30. Then, for [0,a*) and any R. O, the induced distributions Py, and py; satisfy
RR, RR
H HP
Fa(e) da.
(32)
The proof can be found in Appendix G.
We split the integral above into two parts, and then further upper bound this using the following lemma. Lemma B.3. Let fx(x) e- edd(m) where ø is even, differentiable, and strictly conver. For 0,
v Ra -1 1 )(xa(c),c) & c +c) v Ra $
(33)
2
where
((xa(c), o(x + c) 6(1--(1) -). c).
See Appendix G for the details (G.2).
Splitting equation 32 into two regions and then applying the two bounds from Lemma B.3, we have,
1
() da (n ('(xa() + c) (c) da.
HP Pr.
J
I 12
(34)
First region & & 2:3): Here the integrand is small; Taylor expansion near 0 shows the contribution is o( negligible in the asymptotics.
Second region (c25 & a & ):): This term O(e?), and we compute the underlying constant, which eventually yields the upper bound on MSE.
First Region:
0 a & 2.5
Define
1 2.
I =
4 J
(() da.
Note that
a fx(aae() - - fx(xx(() - fx(ea(()- -c)
and since (x(x)) ed0(()) we have
Ia(e) & 0-1 [lg 2 te,
where o Rg IR is guaranteed to exist as ø restricted to Rzo is strictly convex, smooth and incrcasing: hence invertible. Under these assumptions on é, the inverse Φ-1 is concave and smooth; see, e.g., (Niculescu & Persson, 2006, Prop. 1.1.7). Using first-order property of concave functions,
1
za(c) & (0) z(0) log
(35)
where z(0) is the derivative of -- evaluated at O. Hence, (e(e) behaves O(log(1/a) in this regime.
28

---

Published in Transactions on Machine Learning Research (Jan/2026)
Let us now bound the integrand. Suppose that o(x) is upper bounded by polynomial of degree k, for some fixed & (as assumed in the theorem). We have,
8(za(c) c) (o(za(c) +c) ((ra()) - c))xa(() max (((za()) ((x((()(())))))))))))))))))))()) xa((6)
d(xa(c) + c)xa(()
< <clog 1
(36)
for some universal constant c, long as & 22.5 In the last step, made use of equation 35 and the fact that & 2.6 and that ø is upper bounded by polynomial of degree k. In this regime, log 1 = O(log(1/c) c as 0, which is the dominant term.
Therefore, for some universal constants d,d,,
11 < d log"
$ 2o [1og] !
$ x
(37)
where in the penultimate step, we have used the fact that the integral of log" is z'poly(logz), x). Second Region: 2.5 & a < a
Now
aat 1 d'(xa(e) + xa(e) da.
2 22s
From Taylors approximation, we have
c) -
Therefore,
a E 2xssupf(())d(
zz0
Define
h(z) (x)x
and
h* - (())
220
Then, for a E [62.5 ]
xa(e)= - -1 (4. + 0(2))
Using this representation, we can bound Ig as
2ch 12 o (h- ( 0(+)) +c) カ- ( +0(?)) da. Applying the change of variable t =
.23
2 gives
1g < e
o (1+ + ( dt.
Je1
As 0,
1/* -
12 5
8' (1)=
(38)
29

---

Published in Transactions on Machine Learning Research (Jan/2026)
Combined Bound
Combining equation 37 and equation 38,
th
(PP, & o( +
Jasop o' (t) (- (t) (t)) o(1)
and hence,
IP P7.) E ?
0' (1=1()))=(()+++
(39)
where o11) - 0 as c- 0. This completes the proof.
C Proof of Theorem 4.1
In equation 16, we observe that As depends on Ae and δc. As DS and o are not constants but random variables, the procedure used to derive the results for the non-adaptive scheme cannot be directly applied here.
Let define:
Tna Vns v Var [Yn +n Pc
Σ
(Yi- - Ans)
(40)
113 immi =n
where
Pe Pe-H4
Ang # B[ mi + P[ & &cd
Fx
The conditional variance
Var [Y 4n2+ [cc] Ans - And)
and
E [ [ Ang 13 Ac] & (1 Ang)
From the Berry-Esscen thoorem (Vershynin, 2018, Theorem 2.1.3) there exists universal constant such that:
C
sup RER
FT., lec (x) - (2)- < /1 Ana))nn
(41)
where Fragle is the conditional edf of Tng given fie, and ((x) is the standard normal cumulative distribution function.
Now we can rewrite equation 40 as:
The /Ts V Ang Ang)
[(Fx(as) Ans)]
(42)
Rearranging the terms,
Tag (VAns (1 Ans))
ce /b
[ (No-W)
03
Fx1
Ang
(43)
n23
0
Let us define
Ar
H
/ns
03
(44)
0
30

---

Published in Transactions on Machine Learning Research (Jan/2026)
For any he E I,,
Ae
h
Pe
H < h
VT3
a3
h
ag
113
Using equation 42,
v
133
Fx
h vn3
P1-
Fx
PO-R
(H & h1
Tna
$
0
(45)
v Anng (1
Ans)
Using the Taylor series, we can write,
Ao
11
Pe -
fee - μ
h2
Fx
+
Fx
= fx
+
0
σ
v V
12/
Henco, equation 45 bocomes
fx
+
h2
(H & h)
Tag z
vnn
(46)
V Ang (1
Ang)
Therefore
T13
fx Ra=z
O
vis
F (h) = Frng Pente
Ans (1
Ana)
Now from equation 41
Vnn fx
Ae-u
+ O
h?
C
sup heiR
F F (h) Φ
V Ang (1 - Ang)
M2y 7 -1- Ang Ans
(47)
Now, recall the expression for pa from equation 16
p = f F (Fa) 6c.
Since 033- (Fss
H + (B0TH) ) can write /ng
H
fec Pe- 11
ß P
ge
113
and
(0 - δo) (μ - Po)
My vnalu us)) HH. + vna
(48)
Let /ng
(a ( pa)
and My Vnslu fty)) so that
My HG. 3.
31

---

Published in Transactions on Machine Learning Research (Jan/2026)
The event
m 3
[My & m]
H &
(49)
Using this and equation 47, we obtain
sup mel
M $
fx Pi-
m m=
O
(m (m- 3)2
nzz @
-
C
(50)
Ans (1
Ans)
n3y (1
Ang)Ans
Now, we define ç
1x ( )
0
(m--0)²) )
For any fixed m E R, equation 50 can be written as:
dey Ang (1 (ng)
1 fx
C
Fayy Pe (m) -
Ang - c
&
(51)
δov Ansl
v 113 /
Ang) Ang
Using the triangle inequality
fx D-= m
(m) 4 (fx(0)m
a/2 -
< (m)-
-
5)
δov Ang(
Ans)
(52)
fx (0= m
(Ix(0)m
-
,ov Ang (1 - Ang)
0/2
Since (xx) is Lipschitz continuous, we can write
dev Ang(1 Ana) -s + ( (0))
fx
Pa-p m
1
fx Re-H m
fx (0)
(1 Anc) 6
(53)
0/2
22
0/2
Using equation 53 and equation 51 in equation 52, we write
fx Ao-u m
[xx(0)m
C
fx (0)m
F FMylhcno (m) Φb
5
(54)
0/2
T1av (I Ang)
Ang
2n
,ov Ang (1 Ang)
0/2
where
fx Po-H
ni ((0 b.) (y (p-)))
0 ( ((m- (mm-3)² 3)2
5 =
Ov / Ang
Ang)
nz
We apply the Jensen's inequality:
IE Pe, (Piesleade.mm - & [[x(0)m)
-0(1x(00))
))
(
(Ix(0)m
0/2
E Ac. &e
(FM)
(m)
0/22
Therefore
[x (0)m
(F5x(00m)
{xx(0)
E Φb
FMylec.s
> (m) $
Pe: dc
a/2
a/2
32

---

Published in Transactions on Machine Learning Research (Jan/2026)
Now, equation 54 becomes
(m) - ① ( ( (2))))))
C
fx
A-
m
fx (0)m
E Be, de
Voav Ang)
22T
σo Ang!
Ans)
0/2
(55)
Now our goal to show that the R.H.S. of equation 55 converges to zero as n - cc. To achieve this, we first establish the convergence of vnz ((u- (o oe)). The following lemma provides this convergence result.
Lemma C.1. Let De and oe be estimates of μ and using the non-adaptive protocol described in Sec. 3. Then
P Vnslo del Il Pel 81p0 ///3///1
4xp - log ni
1 [ exp
1) log ng
}
(1 2(log nz)/ vna)
3
Where C₁ is constant that depends Fx, Oi, o, and μ, but independent of As 00,
Vns (H - Po) (o d.) 2.
Please note that c0, we have v Ang Ang) Ths ((A - Pe) (o - 8z)) P. O. Consoquently,
a.s. 1/2, fac
a.s. ,e Oe a.3. 0r and from Lemma C.1,
S 0,
and
fx ش=
fx(0)
3.8.
dev Ang (1 Ans)
a/2
Thus, the R.H.S. of equation 55 converges to zero as n - 00, and we can write:
My (n p) S N N 4fx(0)2
Finally, this gives us
o²
lim n MSE(A,) = 4fx( n
This concludes the proof
D Proof of Theorem 4.3
To establish a lower bound on the mean-squared error (MSE) of our estimator, we employ the Van Trees inequality (Gill& Levit, 1995; Van Trees, 2004), which states that for any estimator,
E [ m)²]
(56)
E. I
where g(-) any prior density over the parameter i that satisfics the regularity conditions. The expecta- tion on the left hand side is with respect the joint density expectation with respect to s(p). Also, Io and I, are defined as:
(x) on (n,x), while Egl-] denotes
((0(x0) 27 )
( log P(Y (2) 27
Io Eg
and I, =
((())
respectively. Here g' g() is the the derivative of g(4) with respect to μ and Y [Y Y2, ...., Y,], where each Y, is the 1-bit output of user Morcover, P(Y p) denotes the joint distribution of Y..... Y, given μ. To keep notation simple, we have explicitly mentioned the dependence a.
33

---

Published in Transactions on Machine Learning Research (Jan/2026)
Using the chain rule of Fisher information (Zamir, 1998),
11 1 Σ Jus
(57)
where the Fisher information
4 E ( log P(Y: Mi...., (....,,,..,,)) '.
By definition an adaptive protocol, Y can depend only on X, and ,,...., Y--1 Morcover, X, is indepen- dent of ,,,,.., Y--1- Therefore, we can write
1,
X Ai
Y
0, otherwise.
where each A, is a Borel measurable set that can depend only on Y,....,,, Y2-1 and therefore independent of X₁.
Lemma D.1. Let S be Borel measurable set independent of Xi, and define Y; as:
Y; = {
if e
otherwise.
Then, for any 8= > 0, the Fisher information Jui of Y, with respect to is upper bounded by:
Lu & 2fx(0)
248
Using the fact that equation 58 holds for every 5 > 0, and equation 57,
I 22)x
Substituting this upper bound into the Van Trees inequality equation 56 provides the final lower bound on the MSE:
E [(A - [[]] >
(0)
+ To
(2fx(0) (0)
As 00, the term la n approaches zero (since lo is assumed to be bounded). Consequently, we obtain:
lim n E - [+?]= > (0'
(58)
n m20
This concludes the proof.
E Proof of Theorem 3.3
We analyze bias and variance separately.
34

---

Published in Transactions on Machine Learning Research (Jan/2026)
E.0.1 Bias
Clearly,
B[ANT]] Pe..
We now bound the term [ [[AMT]]-
Recall that
0j + 0
0j+1
2h
0g + jAo
2
m
Using the representation of PMT and separating the negative and positive intervals, we write
(
[X] [[
Σ
Fx(=)d=-Fx(B))
+
Σ
(1-Fx(=)) dz (1 (1000-1111xxx)) -1-FF(())))
(1- Fx(x))
FX(8))A)
j-1
J8
8,41
Σ
(Fx(2) Fx(())) de
m
08,
((1-Fx(2)) -x(xx)) -(1- Fx(()))) de
(59)
1-1
m ΣS" [Fx - Fx(x)) dz.
Σ
[Fx(2) Ex(0,) dz + Σ
(60)
1-
Since fx(t) & L for all t, the CDF Fx is L-Lipschitz in its argument:
[Fx()) - (x) & Llu - vl.
In our estimator, the argument of Fx is the normalized variable (2 - p)/o. Thus,
11
0 - p1
= 0g
Fx
Fx
x L
σ
For E 0011l we have
0 0j+1
0
Ao
|a
03l
Substituting into the Lipschitz bound gives Therefore,
0
LA
Fx
Fx
0
0
2
95+1
LA² 2
[Fx(2) - Fx(e))
and the same bound holds for the positive intervals. Summing over all 2m bins yields
[[[] [[(Ar]] T
35

---

Published in Transactions on Machine Learning Research (Jan/2020
E.0.2 Variance
For every j E {-m........ -1, I,...,m, m),
(x Fx(O,))
Var(T, (2)
K
Thercfore,
A 2
Var(fur)
A Var(T))
Σ
(1 -x((0))
(61)
K
j=-m m 1+0
j=
j40
Since 0g = + jāo, the term
(1) - Fx (x())
is evaluated at points forming uniform grid of spacing Ao. Hence
m
(1
$40
is Riemann sum for the integral
x (1 - Fx(x)) dr,
If we choose the parameters such that A 0 and On -0 - 0b, then
Var(āMT) = K ( Fx(x) - (x(x)(1-Fx(x))
de + +(1))
This completes the proof.
F Bounding the Total Variation Distance using the Squared Hellinger Distance
Lemma F.1. For any pair of discrete distributions? py; Py defined common alphabet,
TV(Py,Pt) & (I-
Proof. The following relationship between the squared Hellinger distance and the Bhattacharyya cocfficient is standard, but we nevertheless provide a proof for completeness. For discrete distributions we have
(P) = _ (Pr(v) vP((3))
=l-p(py,
(62)
where
plpy P+) + Σ (F)))
is the Bhattacharyya coefficient..
Let u(y) = v (v) and v(y) = (xt()) Then
((u(x) (()))((()) v())),
7 An identical approach works for continuous distrihutions as well.
36

---

Published in Transactions on Machine Learning Research (Jan/2026)
and by the Cauchy-Schwarz Schwarz inqquality
- pt(1)] -pt()) -(m(v)-m(o)) ((2))))(/)) (E(u()) + =(v)))) 1/2
Simplifying,
(v) -b(1 & (2(11 (P).PP)))) 1/2 (2(1 + p(Py
2 1 ppp Pt3.
(63)
Therefore,
TV(PV,P7) & V 1- 1P.,
Finally, using equation 62 yields
TV) & / 1- (1-(1-PPPp)PP3)
which gives us the lemma.
G Proofs of Lemmas Appearing in the Proof of Theorem B.1
G.1 Proof of lemma B.2
We now define generalized squared Hellinger distance. Let Z be finite set, R 2 (possibly randomized) function, and f1, f2 be non-negative functions. Then
(()) + Σ (VI Pr(,()) = 2 X æ]dæ
VI e f2(2) PIT,()) = = X x]dr
2
ZEZ
which reduces to the usual squared Hellinger distance when fi, are valid densities.
Similarly, if n, is a function with output alphabet Z = {0, 1}, the generalized total variation distance is
5 (x) = z X = r]dr [
0 f2(x) Pr(T:(X) = = = x æ0dx
(()) Σ
Now we recall our definitions:
fx(x + cx)
da and fx(x - c) =
g- da.
J0
Therefore,
=1_
1
(n-60) 60)
x 1b
( x
11
fx
fx
-fx fx
+
a
da
(64)
0
σ
and likewise,
r
1++
(xx (μ + co)
#
1
fx
fx
g g-
a
da.
(65)
Using equation 64, equation 65, and (Cai & Wei, 2022a, Lemma 2),
37

---

Published in Transactions on Machine Learning Research (Jan/2026)
1
(PP) H²
[T(2);
fx
fx
0
112
(T(x));
1
9+
60
1
9
x
60
a
da
VRa -1
1
)
Vuu +
TV
(I(;));
9+
- 9-
.a) da.
(66)
Now for any Rs 3 that satisfies
1
9+ (z)
Ra
for all such that g-(x) 0.
Ra
9-(x) (x)
9
We can write,
TV (z):
-
1
x 11
a
1
9-
x H
a
σ
0
1
I 1
1 g-
z -T 1 a
(I[
= x|X = x
-
a
1 | dr
2
o
1
1 --H a
r -
H a
2
U+
1 ( dx
0
1
10+ (t, 9- at] dt
2 (E).(a)
1 2 Ae(aa) & (2xa) = Te.
1
Where the third step follows from change of variable, and the penultimate step uses the definition of Fa- Now using this bound on TV in equation 66, we have,
& "² RRa 1 J0 (Ra +
IP(P::
Ba
da.
(67)
This completes the proof.
G.2 Proof of Lemma B.3
Since fx(x) = e ((r), we have
(x(x+e) -oott))+0(-- -((,,e) (x
where
6(2, + 6(x + c) 6(x c).
Therefore,
R₂ sup (e).(e
b((,,c) 6 infreac(a) 8(x,))
From the strict convexity of o and the definition of 6:
8(xr E) is strictly increasing on [0, 00),
Evenness of & implies ((x,e) is odd: 8(-xxe) -(xx e).
38

---

Published in Transactions on Machine Learning Research (Jan/2026)
Thus e(2,e) changes sign exactly once at O, being negative for < 0 and positive for 0. Since Ac(a) is symmetric, the smallest value of 8(x, 6) over Ac(a) occurs at the left endpoint, which equals c)) where za (e) sup (a).
Consequently,
inf 0( c) = -1((xa((),))) (a)
and
Ra = = inf ò(a,c) (1)())(0))))
Ra ((aat))))) so
RRg- -1
tanh (8(za(e),e)
v R. +
Since tanh(t) t for all 0,
v Ra +1 Fc(e) 6(xa(c). xc(e).
v Ra 1
(68)
Since o is convex and differentiable, we can use the first-order condition for convexity to get
2e o' - (x & oll + - 6lx - c) & 2e 6'xx + +c).
Therefore,
)(za(E),e) & 2e d' + te).
which yields
((xa(1),)) zalc) & cd((xa()+ + xa((()
4
2
Therefore, equation 68 can be written as,
Rha -
VR, +1 za(() & ('(xa(() + Ic().
Substituting this pointwise bound into the integral directly yields the result.
Proofs of Lemmas C.1 and D.1
H.1 Proof of Lemma C.1
To prove the convergence of vTz( (o) tc), we first state two key Lemmas that show the convergence of (Ae - p)) and (ō. - o), respectively.
Lemma H.1. Let f.e be the estimate of using the non-adaptive scheme described in Sec. 3. Then,
Pr Pr Pr(18o- m|> |m|
(viz 2 log )
4 log n3
- log
[1+exp
17 log 133
}.
2 exp
(69)
Here, En and depend only on the underlying distribution class and are independent of n4, n22 ng.
Lemma H.2. Let de be the estimate of using the non-adaptive scheme described in Sec. 8. Then,
del 20|>|0| (>
2 log n3
)
(-01 log m1
)
[ 1 [1+ exp
( log 1i3 ]
Pr 1
& 2exp
(70)
/n3
2log nus
3
As before, the constants Or and n depend only the distribution and not on n1, n2, na-
39

---

Published in Transactions on Machine Learning Research (Jan/2026)
Since the right-hand sides in Lemmas H.1 and H.2 converge zero as ny oo, both Pe and 8e are consistent in probability under the non-adaptive scheme. The proof of these two lemmas is given in Appendix I.
Now we begin with some definitions. Let us define the events:
2 log T2
Ej a o del 2 |o|
Vg 2 log ng
4 log 1g
E2 d |1 Pel
x |l|
ny 2 2log n33
If A, B, C, and D are random variables with A < B and C < D, then AC < BD. Thus,
(AC> BD) c (A > B) u (C> D).
and by the union bound,
P(AC> BD) P(A> B) P(C D).
Using this, we obtain
Pr Vna l dellu 1111 Acl (log /
& P[E.] + P[E2].
(1 2(log n/)/ vns)²
Using the bounds for P(Ex) and P(22) from Lemmas H.1 and H.2, we obtain:
8 || na) // / & exp - log n3
-11 lnglog ng
Pr Vnslo dellu- - Pel >
|+ exp
2(log na)/ /n3)
3
As ng 0, this probability approaches zero, implying convergence in probability for the non-adaptive scheme.
H.2 Proof of Lemma D.1
Let S a Borel measurable set, and define Y, as:
{
E
Y x-
otherwise.
Now the Fisher information for a parameter y is defined as:
( 0 Ōp
1 E
(
log P(Y.)))
The probability that Y; = 1 is:
P(Y, = 1/m) = (z)
By regularity of the Lebesgue measure, approximate any Borel measurable set S using finite number of disjoint intervals:
C = alj
with
aj < at aj ax ax w
40

---

Published in Transactions on Machine Learning Research (Jan/2026)
such that
Jsac dx E''
where A denotes symmetric difference.
Therefore,
& Σ fx fx
x (-=-) dx + ga(e),
P(Y: 111)
j=1
where gk((') is a quantity that can be made arbitrarily close to 0 by choosing k large enough. Using the substitution u = x = ou + n, and dæ = odu, the integral becomes
P(Y, = 11w) = Σ - fx(u)du+ + gu(e').
Recall that Fx as the CDF corresponding to fx. Then
P(Y, 1/1) =
Σ
Fx
q v
- Fx
a - 11
)
+ ()))))
2-1
Similarly,
P(Y, = 0/p) = - P(Y, = 1/p).
Taking the derivative of P(Y; = 1114) w.r.t. μ, we obtain
P(Y, = 11
Σ
0
Fx
a
12
Fx
(")
+ gk(c).
0μ
1-1
Using the chain rule,
1
a )
Fx
j
=
fx
Thus:
a
-
(
fx (-=-²) + ge(e))
P(Y: 11p) =
fx
Since Y, is binary random variable, the Fisher information expands as:
In, = P(Y, = 1/w) ( log P(Y, - Pox
11)) 2 P(Y; = 0/μ) (gl log P(Y; p(y; 0w0) - + hale').
log
for some hg((e) that can be made arbitrarily close by choosing & large enough. By substituting the probabilities and derivatives, and then assuming:
[j -
M)
AF5(N) = Fx
Fx
(1) 1
a 11
"j -))))
fx
fx
we write
k
P(Y, 1/p) Σ
AF,(1) + (x(c),
P(Y 01p)=1 =1 Σ AF)(1) gh(d))
41

---

Published in Transactions on Machine Learning Research (Jan/2026)
Therefore
- Af((M)
à
log P(Y =1/x)
+ se(ee)
Σj-1 (F((W)
and
1 - (1)(m)
log P(Y, - 01p)
+ (g((d).
pp
1 Σ/-1 AF)(H)
Substituting these into Lnsr we obtain:
E A
+ hx(e'))
(71)
E) AFz(m)) (1- APj(u)
We now make use of the following result, which is a corollary of (Kipnis & Duchi, 2022, Lemma 11): Lemma H.3. Assume the hypotheses of Theorem 4.3. For every 0,
E Afs(1))
246
148 & &T(()).
Σ AFF(W)) 141 (1-Σ)- (1)())))F(())
Using this in equation 71 completes the proof of Lemma D.1
Proof of Lemmas H.1 and H.2.
The proofs of Lemmas H.1 and H.2 rely on the following lemma, which we prove first.
Lemma I.l. For 1,2, with 0g R, 6, 0, and as defined in equation 8, the following bound holds:
0, 3 o
(-13
P a
<
2cxp
3
Here, Üz is constant that depends only Fx, bi 0, and ,e but is independent of nı, T2z, nas
Proof. For i = 1,2, want to show that
0,
0--1
1
0,
11)
P
0
3
6
2exp
3
We recall the definition of a from equation 8 and write
ar Fx (E(F)) Gt),
where G₁ + F. IE(F) is random variable.
Note that
]
0
(BFF) Fr1
Σ
Yg
j=
where we have assumed no 0. Hence we can write
0
0 P 11
0 -
P
0
P
BR
G.)
42

---

Published in Transactions on Machine Learning Research (Jan/2026)
Using the Taylor series expansion
(B(P) G.) (IB()))
G. O
(72)
[x(Fx
Thus equation 72 becomes
0 11
8 - 14
G,
11)
8 1
P
04
3 Ci
=
+ O(G)) 3 (x((F)(EP))
(73)
For sufficiently large ni, G. is small, and the term O is at most becomes
G. (x [x(Fx((((A)) (B[F])
and hence equation 73
G. P (IEE)E)((EE)) (EF)) + O(G?) 3
0 11 ) & P
Ei -1-1 fx (x((x'(EF))
G
(74)
2
Using the Chernoff bound for Bernoulli random variables form (Har-Peled, 2011, Theorem 27.17)), for all 1, we have:
1[FF-E(RR > (E(F)) 2 exp
(75)
Therefore, applying this bound to equation 74, we obtain:
0g
P F.
B(FF))
fx(FF (x(F)
2
0
$ 2exp
Tlg
0. - p1
2
1 (F
2exp
-nie7Ca
3(EF,)
4
3
where C = a((Pa)
0:=44
f (Fx
(BF)))
0:-44
fx
0:=4
1 Fxx (xx))=
Finally we can write:
8 p
0 - 11
-n;e7Cis
P
a
> E
< 2exp
0
3
This completes the proof.
1.1 Proof of Lemma H.1
From Lemma 1.1, for i 1, and E, > 0, the following inequality holds:
02 - p &
0;
1 )
-niEfC
< 1 2exp
3
This implies that 00, ag becomes arbitrarily close to P-- within margin proportional to &,. For some > 0, if we have
0 P
0; - 41
04
& él
(76)
σ
for == 1,2, then
((1--1)
82 11
41)
(1 261), 21+2))) ))
01 022 E
43

---

Published in Transactions on Machine Learning Research (Jan/2026)
and
1
(0) (0)) <
(77)
[ 11=
11
(1 2c1)
((522)
(1 - 2c
a
or equivalently,
(1-=
82
02-11
81 (1 (12))
[ai02 - 0221
(1--1 ((0
02
02-
81) (1+ 261)
1 &
μ.
( 01-pp
0--H
(1 + 2c1)
(1)
0/2
01-
(1 261)
7
(78)
Simplifying, conclude that if equation 76 holds, then
461 1 $ Pc - 11 -
4c1
p.
(79)
+1+ + 2&1)
(1 - 221)
This implies that for all sufficiently small E1
4e1
0
1
01 11
02 #
02 11
Il Pel > 1
< P
3 61
+ P
02
7 el
261
Then, applying Lemmaa 1.1, we can write:
4E1
-nieiO
=2
P l Pol |u| (1 261
$ 2 exp
eexp
3
(80)
-
= 2 exp
+ exp
3
Let 11 = 122
and 61
log ng Ving
Then, we have:
log
P [1
4 log ng
)
- log
logn3 n3
)
lnn n13
}
Pcl > |l|
& 2exp
+ exp
1
(81)
Vig
2 log
3
Now from equation 81, we conclude that μ converges probability to μ as n3 + ao. This completes the proof.
1.2 Proof of Lemma H.2
Now we recall the definition of â. and write
(ō. o) = (
01 -1-82 02 ( a2))
1).
(82)
The approach is very similar to that of the Lemma H.l and we omit minor calculations. If we have
$ g9 0.-11 11
a
for él and 1,2, then
-210
2010
$ G. - - &
(1 + 2c1)
(1 2c1)
We apply the same union bound approach used in proving Lemma H.1, yielding:
44

---

Published in Transactions on Machine Learning Research (Jan/2026)
2E1 |o|
01
0 p
0g p
(
02
P o
del
$ P
01
3 61
P
02
(1 2c1)
Using the value of log and following a similar approach as in Lemma H.l, we apply Lemmaa 1.1 to vns
obtain the following:
2 log ng
(- log na
{[ [1+ [1+ex exp
- log
]
P o del
2 |ol
$ 2xxp
n3 2 log fi
3
3
Where Ćj and 77 are the constants defined in Lemma H.1. Hence, as n 00, &e converges in probability to This concludes the proof of the Lemma.
]
Remark T.2. In the proofs of Lemmas H.1 and H.2 we only require that Pe and ô, converge in probability to μ and o, respectively. This is ensured as soon as the product njeî tends to infinity, since the deviation probabilities then go zero for every fixed threshold. In particular, our choice
T1g
log f23
log n2
/n3
yields nie log nz oo and is therefore sufficient for the consistency in probability established in Lem- H.l and H.2. One may also consider the more general allocation
n33
n2
(log n2)
1-6
0 0<0< <
with the same choice Ej
ng Vng
this case
11 (log 12y)16 1-8
(logna)²
(log n3) 1+8
nh
so the deviation probabilitics P(Ang) satisfy
P(Ans) & exp( - (xp(-=Clognaa)+
C C>0 0.
The series
exp( C(log 24))
is then finite, and the Borel-Cantelle lemma (see, e.g., (Durrett, 2019, Theorem 2.3.7)) implies that the events Ang occur only finitely many times almost surely. Under this alternative scaling, the deviation probabilities decay fast enough to yield stronger conclusion for Lemmas H.l and H.2, namely almost sure convergence instead of convergence in probability. Since none of our results require this stronger mode of convergence, we work with the simpler choice п1 = n2 = nt// log rig, which already ensures the consistency guarantees established Lemmas H.1 and H.2.
45


Reviews:
[{"review_id": "GDA9xaa7NM", "reviewer": "Reviewer_iCZe", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers the problem of distributed mean estimation, whereby a central server is tasked with estimating the mean of samples when each user has access to one i.i.d. sample and is restricted to sending only a single bit. The paper distinguishes between two types of protocols (adaptive and non-adaptive) and analyzes the mean estimation problem by bounding the mean squared error as the number of users goes to infinity.\n\n**Strengths**\n\n* The paper is very well written. The problem is clearly presented, and the authors make their contributions explicit.\n* The problem is interesting and potentially useful in resource-constrained environments. The analysis is thorough and provides meaningful insight into the quality of the proposed protocols.\n* In addition to theory, the numerical results illustrate how the estimators behave in practice.\n\n**Weaknesses**\n\n* It would be beneficial to comment on how the problem changes if users are allowed to send 2 bits per sample. Although a variant of this is briefly mentioned in the future-work section, a more explicit discussion of the marginal or qualitative benefits (if any) of the 2-bit case would help justify the focus on the 1-bit regime.\n* How do the analytical asymptotic results inform performance in the finite-user setting? Based on the numerical experiments, the protocols appear to achieve relatively small MSE even for moderate numbers of users. A discussion connecting the asymptotic theory to finite-sample behavior is currently missing.\n* There should also be some discussion of the communication or computation cost associated with the adaptive protocol.", "claims_and_evidence_yn": "Yes", "claims_explanation": "To my reading, all the theorems are based on solid mathematical proofs.", "audience_yn": "Yes", "audience_explanation": "The problem is related to similar problems in federated learning, privacy-preserving statistics, and sensor networks, and would be of interest to those interested in these topics.", "requested_changes": "Please address the weaknesses that I highlighted above. I believe that the paper presents an interesting problem and develops nice analysis. I would recommend acceptance if the authors can address the weaknesses.", "broader_impact_concerns": "No direct ethical or societal risks are anticipated.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "vs955il9uK", "reviewer": "Reviewer_6jTy", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This is a very technical paper, studying the problem of distributed mean estimation in the case where clients communicate only a bit to the server doing the estimation, derived from a pre-decided threshold. The authors specifically study the case in which both mean and variance are unknown. The authors study both the non-adaptive case (a single fixed threshold,no coordination), and the adaptive case (for them, 2 thresholds and 2 rounds, with the 2 thresholds participating in only one round each respectively), and show that the lower bound for the non-adaptive case is strictly higher than the adaptive case for a range of symmetric, log-concave distributions, including generalized gaussians with  $1 < β < 1.85$. The authors are able to quantify the gap, which neat.\n\nAs a byproduct the authors also derive a non-adaptive protocol for the standard deviation and derived its asymptotic MSE, but explicitly do not claim optimality.", "claims_and_evidence_yn": "Yes", "claims_explanation": "I went throught he proofs and while I am not an expert in this type of analysis, I think I could follow them and did not find any major mistakes, except one nit (unless I made a mistake):\n\nIn appendix I.1, I think you need to have $\\frac{\\tilde{C}_1}{3}​​>1$ to hold in order to claim strong consistency/almost sure convergence, but I don't think there's an assumption placed on $\\tilde{C}$ anywhere? It doesn't change the main point of the paper, but I think either you need to e.g. choose $n_1=\\frac{n_3}{(\\log n_3) ^{1-\\delta}}$ with $\\delta >0$  to ensure that it remains controlled, or change the claim to weak convergence.", "audience_yn": "Yes", "audience_explanation": "I think there's a technical subset of the TMLR audience which can either directly use the technique or can use the proof techniques demonstrated.", "requested_changes": "Non, except maybe the nit.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "oMtoOoE3Hb", "reviewer": "Reviewer_LzHk", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper provides several algorithms to solve estimation of the mean in location scale families in distributed context. The key constraint is that the distributed observers of samples can send only one bit to the central server. \n\nThe algorithms naturally split into the simpler non-adaptive and more complex adaptive classes. It turns out that the proposed algorithms send the bits just based on a simple comparisons with a threshold.\n\nThe problems considered are non-trivial. The authors achieved substantial progress in advancing state-of-the-art. Asymptotic results included are proved using advanced statistical techniques. The review of the state-of-the-art is up-to-date. The quality of presentation is excellent.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The new results in the paper are of several kinds. \n\n- new algorithms,\n- study of  their asymptotic behavior\n- simulations of algorithms in finite samples.\n\nSince the authors opted to put proofs into the appendixes, it seems that the simulations are the key part of the paper. The authors provided the code to reproduce their experiments in the supporting material.", "audience_yn": "Yes", "audience_explanation": "Estimation of the mean in various contexts is a foundational problem of estimation theory. One can find an example of a paper with similar topic in this year's TMLR:\n\nVardhan, Mazumdar: Collaborative Compressors in Distributed Mean Estimation with Limited Communication Budget\nhttps://openreview.net/pdf?id=AtCKHCoMA7", "requested_changes": "CRITICAL:\n\n1. I do not understand the series of inequalities below equation (60) on page 31. If $F_X$ is indeed $L$-Lipschitz, then there should be no $\\sigma$ in the middle term. For the last inequality to hold, one presumably assumes that $z$ belongs to the interval $[\\theta_{j-1}, \\theta_j]$ or something similar. \n\nTO STRENGTHEN WORK:\n\n2. I would like to ask the authors, whether there could be applications beyond distributed computing, e.g. for price estimation in economics, finance, or even sociology, since these fields often uses location-scale families. If so, then the authors could sketch further interdisciplinary applications. \n\n3. References to the algorithms could be more polished. As an example on page 10 the authors refer to the non-adaptive protocol of Section 3. However, there are 2 non-adaptive protocols in Section 3 - see pages 6 and 9. \n\n4. It may be a good idea to include location-scale family as part of the paper's title.\n\n5. I would myself choose another name for $Y_i$. For me, $Y_i$ would a real-valued random variable, whereas the underlying random variable is Boolean. Maybe $B_i$ or $M_i$ would be a (admittedly marginally) better choice, if one insists on random variables being capitalized? This is however more a suggestion for future work, as large-scale paper changes like this tend to lead to omissions.", "broader_impact_concerns": "I can see no ethical implications of this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)