arXiv:2611.04532v1 cs.LG

The Price of List Replicability: Tight Bounds for Bias Estimation

Michael Chen, Atieh Bastan, A. Pavan, N. V. Vinodchandran

제출 2026-11-04

원문 초록

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.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2611.04532v1제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.