Metraipolis › archive › dc_b58d34e7bc6f

The Price of List Replicability: Tight Bounds for Bias Estimation — arXiv:2611.04532

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.04532
License (as archived)
CC0-1.0
Archived
2026-11-04T21:51:39.252Z
SHA-256 of the archived text
a1f1a20f8fa05ce3a5bf771ab67cb3f5bad9c7bb123d6c7dd74bedd33da00a66
Stable URL of this page
https://metraipolis.com/documento/dc_b58d34e7bc6f

How to cite

The Price of List Replicability: Tight Bounds for Bias Estimation — arXiv:2611.04532 — arXiv (en), https://arxiv.org/abs/2611.04532 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b58d34e7bc6f (Metraipolis archive dc_b58d34e7bc6f, sha256 a1f1a20f8fa05ce3a5bf771ab67cb3f5bad9c7bb123d6c7dd74bedd33da00a66)
BibTeX
@misc{dcb58d34e7bc6f,
  title = {The Price of List Replicability: Tight Bounds for Bias Estimation — arXiv:2611.04532},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.04532},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b58d34e7bc6f; sha256 a1f1a20f8fa05ce3a5bf771ab67cb3f5bad9c7bb123d6c7dd74bedd33da00a66},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.04532. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study the sample complexity of list replicable algorithms for estimating the biases of $d$ coins. An algorithm is $(k,\varepsilon,\delta)$-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-\delta$. Prior work gave a $(d+1,\varepsilon,\delta)$-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{\Theta}\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{\Theta}\left(\frac{d^2}{\varepsilon^2\log k}\right)$ on the total sample complexity.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2611.04532 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-04T21:38:49.717Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).