On the Lower Bound of Minimax Error for Crowdsourcing

We consider a binary crowdsourcing problem in which independent tasks, such as fake-news detection or binary classification tasks, are assigned to n imperfect agents, each of which may misclassify/mislabel the tasks with some unknown probability. We revisit a result in [1], presented at NeurIPS 2017, regarding a lower bound for the minimax error of this problem, and then investigate a more general lower bound under a broader parameter set. We demonstrate that for any estimator using a sufficiently large number of independent observations T of the labeling results, the probability of having an estimation error of at least 1 / √T is bounded away from zero by a constant that depends on a structural feature of the parameter set. Additionally, we derive a local version of this result, which essentially asserts that for any r-ball around any parameter point and any estimator based on T ≥ 4 / r² samples, there always exists a point in that ball that cannot be estimated accurately to within o(1 / √T).