---
title: "The Price of List Replicability: Tight Bounds for Bias Estimation"
source: "arXiv AI/CL/LG（论文）"
source_tier: "t2"
url: "https://arxiv.org/abs/2611.04532v1"
permalink: "https://feed.astralor.com/items/itm_df4bb3affa238284a1870ff5"
published: "2026-11-03T08:59:54.000Z"
score: 58
channel: "tech"
tags: ["The Price","List Replicability","Tight Bounds","Bias Estimation","Prior","Together","More"]
---

# The Price of List Replicability: Tight Bounds for Bias Estimation

## 速览

We study the sample complexity of list replicable algorithms for estimating the biases of $d$ coins. An algorithm is $(k,\varepsilon,δ)$-list replicable if for every bias vector $\mathbf{p}\in[0,1]^d$, there is a set of…

## 关键点

- We study the sample complexity of list replicable algorithms for estimating the biases of $d$ coins.
- An algorithm is $(k,\varepsilon,δ)$-list replicable if for every bias vector $\mathbf{p}\in[0,1]^d$, there is a set of outputs $L_{\mathbf{p}}\subseteq \mathbb{R}^d$ of at most $k$ elements such that every $\mathbf{y}\i…
- Prior work gave a $(d+1,\varepsilon,δ)$-list replicable algorithm with sample complexity $\widetilde{O}\left(\frac{d^3}{\varepsilon^2}\right)$, but no nontrivial sample complexity lower bound was known.

## 全文

We study the sample complexity of list replicable algorithms for estimating the biases of $d$ coins. An algorithm is $(k,\varepsilon,δ)$-list replicable if for every bias vector $\mathbf{p}\in[0,1]^d$, there is a set of outputs $L_{\mathbf{p}}\subseteq \mathbb{R}^d$ of at most $k$ elements such that every $\mathbf{y}\in L_{\mathbf{p}}$ satisfies $\lVert\mathbf{y}-\mathbf{p}\rVert_\infty\leq\varepsilon$, and the algorithm output is in $L_{\mathbf{p}}$ with probability at least $1-δ$. Prior work gave a $(d+1,\varepsilon,δ)$-list replicable algorithm with sample complexity $\widetilde{O}\left(\frac{d^3}{\varepsilon^2}\right)$, but no nontrivial sample complexity lower bound was known. We establish the first non-trivial sample complexity lower bound for this problem and give an improved algorithm that matches it up to polylogarithmic factors. Together, these results determine the optimal sample complexity for list size $d+1$ to be $\widetildeΘ\left(\frac{d^2}{\varepsilon^2}\right)$, showing that the quadratic dependence on dimension is inherent up to polylogarithmic factors. More generally, for every $k\in[d+1,2^d]$, we establish matching upper and lower bounds of $\widetildeΘ\left(\frac{d^2}{\varepsilon^2\log k}\right)$ on the total sample complexity.

---

引用前请核对原文;本文由星际流动整理:https://feed.astralor.com/items/itm_df4bb3affa238284a1870ff5