cs.LGNov 3, 2026

The Price of List Replicability: Tight Bounds for Bias Estimation

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

Organizations: Iowa State University · University of Nebraska-Lincoln

Abstract

We study the sample complexity of list replicable algorithms for estimating the biases of dd coins. An algorithm is (k,ε,δ)(k,\varepsilon,δ)-list replicable if for every bias vector p∈[0,1]d\mathbf{p}\in[0,1]^d, there is a set of outputs Lp⊆RdL_{\mathbf{p}}\subseteq \mathbb{R}^d of at most kk elements such that every y∈Lp\mathbf{y}\in L_{\mathbf{p}} satisfies ∥y−p∥∞≤ε\lVert\mathbf{y}-\mathbf{p}\rVert_\infty\leq\varepsilon, and the algorithm output is in LpL_{\mathbf{p}} with probability at least 1−δ1-δ. Prior work gave a (d+1,ε,δ)(d+1,\varepsilon,δ)-list replicable algorithm with sample complexity O~(d3ε2)\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+1d+1 to be Θ~(d2ε2)\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∈[d+1,2d]k\in[d+1,2^d], we establish matching upper and lower bounds of Θ~(d2ε2log⁡k)\widetildeΘ\left(\frac{d^2}{\varepsilon^2\log k}\right) on the total sample complexity.

Figures & tables

Explore similar work

CardsList
  1. Tight list replicability bounds via a novel sphere covering theorem

    Jun 4, 2026Ari Blondal, Hamed Hatami, Pooya Hatami +2ML ReproducibilityStatistical Learning Theory

  2. Near-Optimal List Replicability from Littlestone Dimension

    Oct 23, 2026Ari Blondal, Pooya Hatami, Chavdar Lalov +1PAC Learning