---
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

## At a glance

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…

## Key points

- 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.

## Full text

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.

---

Verify against the original before citing; curated by Astral Feed: https://feed.astralor.com/items/itm_df4bb3affa238284a1870ff5