The Price of List Replicability: Tight Bounds for Bias Estimation
Organizations: Iowa State University · University of Nebraska-Lincoln
Abstract
We study the sample complexity of list replicable algorithms for estimating the biases of coins. An algorithm is -list replicable if for every bias vector , there is a set of outputs of at most elements such that every satisfies , and the algorithm output is in with probability at least . Prior work gave a -list replicable algorithm with sample complexity , 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 to be , showing that the quadratic dependence on dimension is inherent up to polylogarithmic factors. More generally, for every , we establish matching upper and lower bounds of on the total sample complexity.
Figures & tables
| Reference | Lower bound on | Upper bound on |
|---|---|---|
| [ 10 ] | — | |
| This work |
| Reference | Lower bound on | Upper bound on |
|---|---|---|
| [ 30 ] | — | |
| This work |
Sample Complexity
Sample complexity studies how many data points, queries, or observations are needed to learn, estimate, test, or sample to a target accuracy.
See all 110 papers