Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes

• URL: http://arxiv.org/abs/2604.07796v1
• Date: Thu, 09 Apr 2026 04:49:21 GMT
• Title: Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes
• Abstract summary: We propose a novel adaptive mean estimator based solely on randomized threshold queries.<n>Our estimator's sample complexity has an extra multiplicative $O(log(/))$ penalty.<n>For both threshold queries and more general interval queries, the sample complexity of any non-adaptive estimator must scale linearly.
• Score: 32.65125292684608
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we study the problem of mean estimation under strict 1-bit communication constraints. We propose a novel adaptive mean estimator based solely on randomized threshold queries, where each 1-bit outcome indicates whether a given sample exceeds a sequentially chosen threshold. Our estimator is $(ε, δ)$-PAC for any distribution with a bounded mean $μ\in [-λ, λ]$ and a bounded $k$-th central moment $\mathbb{E}[|X-μ|^k] \le σ^k$ for any fixed $k > 1$. Crucially, our sample complexity is order-optimal in all such tail regimes, i.e., for every such $k$ value. For $k \neq 2$, our estimator's sample complexity matches the unquantized minimax lower bounds plus an unavoidable $O(\log(λ/σ))$ localization cost. For the finite-variance case ($k=2$), our estimator's sample complexity has an extra multiplicative $O(\log(σ/ε))$ penalty, and we establish a novel information-theoretic lower bound showing that this penalty is a fundamental limit of 1-bit quantization. We also establish a significant adaptivity gap: for both threshold queries and more general interval queries, the sample complexity of any non-adaptive estimator must scale linearly with the search space parameter $λ/σ$, rendering it vastly less sample efficient than our adaptive approach. Finally, we present algorithmic variants that (i) handle an unknown sampling budget, (ii) adapt to an unknown scale parameter~$σ$ given (possibly loose) bounds, and (iii) require only two stages of adaptivity at the expense of more complicated general 1-bit queries.

Related papers

• Non-Adaptive 1-Bit Mean Estimation: Minimax Rates and the Sample-Interval Tradeoff [32.65125292684608]
  We study one-dimensional mean estimation under a 1-bit communication constraint.<n>We find that for every $k>1$, a non-adaptive protocol attains the adaptive 1-bit minimax rate.
  arXiv  Detail & Related papers  (2026-09-08T10:52:52Z)
• Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions [51.50375419691955]
  Distributionally robust Markov decision processes provide a principled framework for sequential decision making under model uncertainty.<n>We study how many samples are necessary and sufficient to learn an $varepsilon$-optimal robust policy under the average-reward criterion.
  arXiv  Detail & Related papers  (2026-08-06T19:49:48Z)
• Interaction Is Not Necessary for Order-Optimal 1-Bit Mean Estimation [14.106326180143666]
  We consider distributions on $mathbbR$ with mean in $[-,]$ and absolute $k$-th central moment at most $k$, where $k>1$ is fixed.<n>We show that this interaction can be avoided by constructing a randomized fully non-adaptive protocol.
  arXiv  Detail & Related papers  (2026-08-03T17:28:12Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  The Area Under the ROC Curve (AUC) is a pivotal evaluation metric in real-world scenarios with both class imbalance and decision constraints.<n>We present two simple instance-wise minimax reformulations to close the approximation gap of PAUC optimization.<n>The resulting algorithms enjoy a linear per-iteration computational complexity w.r.t. the sample size and a convergence rate of $O(-2/3)$ for typical one-way and two-way PAUCs.
  arXiv  Detail & Related papers  (2025-12-01T02:52:33Z)
• Sequential 1-bit Mean Estimation with Near-Optimal Sample Complexity [32.65125292684608]
  We study the problem of distributed mean estimation with 1-bit communication constraints.<n>Our estimator is $(epsilon, delta)$-PAC for all distributions with bounded mean ($-lambda le mathbbE(X) le lambda $) and variance ($mathrmVar(X) le sigma2$) for some known parameters.
  arXiv  Detail & Related papers  (2025-09-26T06:22:57Z)
• Sample Complexity Bounds for Scalar Parameter Estimation Under Quantum Differential Privacy [9.244521717083696]
  This paper presents tight upper and lower bounds for minimum number of samples required to attain a prescribed accuracy.<n>The best-case (optimal) scenario is considered by minimizing the sample complexity over all differentially-private channels.
  arXiv  Detail & Related papers  (2025-01-24T02:23:51Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  We study the Shortest Path (SSP) problem with a linear mixture transition kernel. An agent repeatedly interacts with a environment and seeks to reach certain goal state while minimizing the cumulative cost. Existing works often assume a strictly positive lower bound of the iteration cost function or an upper bound of the expected length for the optimal policy.
  arXiv  Detail & Related papers  (2024-02-14T07:52:00Z)
• Optimal Sample Complexity for Average Reward Markov Decision Processes [1.0445957451908694]
  We develop an estimator for the optimal policy of average reward MDPs with a sample complexity of $widetilde O(|S||A|t_textmix2 epsilon-2)$. This marks the first algorithm and analysis to reach the literature's lower bound.
  arXiv  Detail & Related papers  (2023-10-13T03:08:59Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
  This paper investigates group distributionally robust optimization (GDRO) with the goal of learning a model that performs well over $m$ different distributions. To reduce the number of samples in each round from $m$ to 1, we cast GDRO as a two-player game, where one player conducts and the other executes an online algorithm for non-oblivious multi-armed bandits. In the second scenario, we propose to optimize the average top-$k$ risk instead of the maximum risk, thereby mitigating the impact of distributions.
  arXiv  Detail & Related papers  (2023-02-18T09:24:15Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  We investigate the problem of best identification in discounted linear Markov+Delta Decision in the fixed confidence setting under a generative model. The lower bound as the solution of an intricate non- optimization program can be used as the starting point to devise such algorithms.
  arXiv  Detail & Related papers  (2022-08-11T04:12:50Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  A novel model-free algorithm is proposed to minimize regret in episodic reinforcement learning. The proposed algorithm employs an em early-settled reference update rule, with the aid of two Q-learning sequences. The design principle of our early-settled variance reduction method might be of independent interest to other RL settings.
  arXiv  Detail & Related papers  (2021-10-09T21:13:48Z)
• Towards Tight Communication Lower Bounds for Distributed Optimisation [30.134447658488057]
  We consider a standard distributed optimisation setting where $N$ machines aim to jointly minimise the sum of the functions $sum_i = 1N f_i (x)$. Our main result provides the first fully unconditional bounds on total number of bits which need to be sent and received by the $N$ machines. We show that $Omega( Nd log d / Nvarepsilon)$ total bits need to be communicated between the machines to find an additive $epsilon$-approximation to the minimum of $sum_i = 1N
  arXiv  Detail & Related papers  (2020-10-16T08:10:02Z)
• Private Mean Estimation of Heavy-Tailed Distributions [10.176795938619417]
  We give new upper and lower bounds on the minimax sample complexity of differentially private mean estimation of distributions with bounded $k$-th moments. We show that $n = Thetaleft(frac1alpha2 + frac1alphafrackk-1varepsilonright)$ samples are necessary and sufficient to estimate the mean to $alpha$-accuracy under $varepsilon$-differential privacy, or any of its common relaxations.
  arXiv  Detail & Related papers  (2020-02-21T18:30:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.