Title: Crowdsourcing with Sparsely Interacting Workers,
Abstract: We consider estimation of worker skills from worker-task interaction data
(with unknown labels) for the single-coin crowd-sourcing binary classification
model in symmetric noise. We define the (worker) interaction graph whose nodes
are workers and an edge between two nodes indicates whether or not the two
workers participated in a common task. We show that skills are asymptotically
identifiable if and only if an appropriate limiting version of the interaction
graph is irreducible and has odd-cycles. We then formulate a weighted rank-one
optimization problem to estimate skills based on observations on an
irreducible, aperiodic interaction graph. We propose a gradient descent scheme
and show that for such interaction graphs estimates converge asymptotically to
the global minimum. We characterize noise robustness of the gradient scheme in
terms of spectral properties of signless Laplacians of the interaction graph.
We then demonstrate that a plug-in estimator based on the estimated skills
achieves state-of-art performance on a number of real-world datasets. Our
results have implications for rank-one matrix completion problem in that
gradient descent can provably recover $W \times W$ rank-one matrices based on
$W+1$ off-diagonal observations of a connected graph with a single odd-cycle.