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

Jun 4, 2026

Tight list replicability bounds via a novel sphere covering theorem

In recent years, list replicability has emerged as a framework for formalizing reproducibility in learning theory. A central question is how the required list size relates to the accuracy parameter and natural complexity measures of the hypothesis class. To achieve sharp bounds on list replicability, we prove a novel topological sphere covering theorem, derived from the Borsuk-Ulam theorem. Specifically, if the dd-sphere is covered by open sets, each of which lies in an open hemisphere, then d+1d+1 of these sets must have a common intersection. Using this result, we obtain a sharp bound on the relationship between list size and accuracy for VC classes. We also show that for large-margin half-spaces, provided the margin is not too large, the optimal list size equals the ambient dimension. However, when the margin is taken to be very large, we devise a replicable algorithm achieving the minimal list size of ⌈d/2⌉+1\lceil d/2 \rceil + 1.
Oct 23, 2026

Near-Optimal List Replicability from Littlestone Dimension

We study the list replicability number in the realizable PAC learning framework and prove that every concept class HH over a countable domain with Littlestone dimension dd and dual VC dimension v∗v^* satisfies LR(H)≤2O(dmin⁡{log⁡d,v∗}).\mathrm{LR}(H)\leq 2^{O(d\min\{\log d,v^*\})}. This matches the worst-case lower bound of 2Ω(d)2^{Ω(d)} up to a logarithmic factor in the exponent and exponentially improves the previous best upper bound LR(H)≤22O(d)\mathrm{LR}(H)\le 2^{2^{O(d)}} of Bun, Livni, and Moran [FOCS 2020]. Unlike earlier bounds of 2Oε(d2)2^{O_ε(d^2)} for fixed accuracy ε>0ε>0 implied by the work of Ghazi, Golowich, Kumar, and Manurangsi [STOC 2021] and Lyu [STOC 2026], our bound is independent of εε. The 2O(dlog⁡d)2^{O(d\log d)} bound follows from a new inductive framework for bounding list replicability that builds on the recent notion of irreducibility from differentially private learning. The 2O(dv∗)2^{O(dv^*)} bound follows from a simple globally stable learner that takes the majority vote of multiple empirical risk minimizers, with stability established using tools from stable regularity.
Nov 7, 2026

Sharp Logarithmic-Product Bounds for List Replicability of Sign Matrices

List replicability measures how many accurate hypotheses suffice to contain the output of a learning rule with arbitrarily high confidence. We prove that every nonempty class of mm binary concepts on nn domain points has list replicability at most 805ln⁡(2m)ln⁡(2n)805\ln(2m)\ln(2n). This resolves the logarithmic-product conjecture of Blondal, Hatami, Hatami, Lalov, and Tretiak. Hanner matrices give lower bounds of the same order, for square matrices and for explicit families with unequal logarithmic aspect ratios. The upper bound is obtained by constructing nested acyclic sets in the faces of a cube. A critical-point estimate supplies highly connected regions, weighted cell attachments keep the sets compatible across faces, and a cubical carrier theorem converts them into accurate finite covers and learning rules. Appending one constant coordinate turns list replicability into an exact geometric quantity, the face width, and graph-orientation classes satisfy exact product formulas. In particular, there are explicit classes with list replicability 4k+14k+1 and equivariant index 3k3k, so the additive gap between the two is unbounded. We also develop entropy-tilting and two-sided Gibbs constructions, give combinatorial upper bounds adapted to structured matrices, compute exact values on classical families, and study the index of Paley matrices.