One-Bit Distributed Mean Estimation with Unknown Variance
Ritesh Kumar [email protected], Shashank Vatedka [email protected] · 2025
Read One-Bit Distributed Mean Estimation with Unknown Variance by Ritesh Kumar [email protected], Shashank Vatedka [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-18502.txt.
Introduction
Ritesh Kumar and Shashank Vatedka study one-bit distributed mean estimation when the variance is unknown, in work from 2025. Each user holds one sample from a location-scale distribution and may send just a single bit to a central server that must estimate the mean. They propose simple non-adaptive and adaptive protocols for this tight communication limit.
Both protocols reach asymptotic normality, and the authors bound their mean squared error as the user count grows. For symmetric log-concave data, matching lower bounds prove the adaptive scheme optimal. A sharper lower bound for non-adaptive rules shows a real gap: extra bits help adaptive schemes only a little, while adaptivity itself pays off.
Catalog record
| CREATOR | Ritesh Kumar [email protected], Shashank Vatedka [email protected] |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 117 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-18502
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
One-Bit Distributed Mean Estimation with Unknown Variance Ritesh Kumar [email protected], Shashank Vatedka [email protected] Abstract In this work, we study the problem of distributed mean estimation with 1 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 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. Reviewed on OpenReview: https://openreview.net/forum?id=g95C4zIEPg 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 in such scenarios, motivating advances in distributed learning and estimation ( McMahan et al., 2017 ; Chen et al., 2021 ; Kairouz et al., 2021 ) . In many problems such as distributed optimization and federated learning, communication often emerges as the main bottleneck, creating the need to develop communication-efficient 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 communication efficiency is also crucial in many signal processing applications, including IoT and sensor networks, where we typically have tens to hundreds of low-power devices that make noisy measurements which must be communicated to a fusion center for subsequent decisions or estimation. In such scenarios, severe power and bandwidth constraints have motivated substantial recent work on understanding 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 et 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, resource-constrained devices. There is a 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 parametric estimation in location families—particularly Gaussian ( Cai & Wei, 2022b ; Cai & Wei, 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 ; Acharya et al., 2020b ; Acharya et al., 2021 ; Koltchinskii et al., 2023 ) , while lower bounds on minimax risk for distributed statistical estimation ( Zhang et al., 2013 ) and communication-efficient 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 ; Deisenroth & Ng, 2015 ) . The distributed setting with one-bit information sharing is particularly challenging and has been extensively studied ( Venkitasubramaniam et al., 2007 ; Chen & Varshney, 2009 ) . More recently, ( Han et al., 2021 ; Barnes et al., 2020 ; Rahmani et al., 2024 ; Shah et al., 2025 ) derived lower bounds for distribution learning in parametric and nonparametric settings. The framework applies to both fixed and sequential message-passing protocols for various problems including communication-constrained mean and covariance 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 communication constraints. Location-scale models have been widely studied in statistics, economics, and sociology. In economics, 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 arbitrage-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, including 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-Hesketh (2019) . In many of these problems, data is often generated across heterogeneous, geographically dispersed, or privacy-sensitive sources-retail outlets, financial exchanges, or survey respondents—where transmitting full-resolution observations is impractical due to bandwidth, latency, or confidentiality constraints Suresh et al. (2017) ; Konečný et al. (2016) ; Duchi et al. (2018) . In such settings, one-bit and low-bit communication primitives could provide an attractive alternative by reducing communication, provide privacy (with additional differentially 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 areas 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 scale-location families, where both the mean and variance are unknown, and the variance is treated as a nuisance parameter. We design simple non-adaptive and adaptive protocols for this problem, and derive