Gradient descent for sparse rank-one matrix completion for crowd-sourced aggregation of sparsely interacting workers
Files
Published version
Date
2018-07-10
DOI
Authors
Ma, Yao
Olshevsky, Alexander
Saligrama, Venkatesh
Czepesvari, Csaba
Version
Published version
OA Version
Citation
Yao Ma, Alexander Olshevsky, Venkatesh Saligrama, Csaba Czepesvari. 2018. "Gradient Descent for Sparse Rank-One Matrix Completion for Crowd-Sourced Aggregation of Sparsely Interacting Workers." International Conference on Machine Learning (ICML)
Abstract
We consider worker skill estimation for the singlecoin
Dawid-Skene crowdsourcing model. In
practice skill-estimation is challenging because
worker assignments are sparse and irregular due
to the arbitrary, and uncontrolled availability of
workers. We formulate skill estimation as a
rank-one correlation-matrix completion problem,
where the observed components correspond to
observed label correlation between workers. We
show that the correlation matrix can be successfully
recovered and skills identifiable if and only
if the sampling matrix (observed components) is
irreducible and aperiodic. We then propose an
efficient gradient descent scheme and show that
skill estimates converges to the desired global optima
for such sampling matrices. Our proof is
original and the results are surprising in light of
the fact that even the weighted rank-one matrix
factorization problem is NP hard in general. Next
we derive sample complexity bounds for the noisy
case in terms of spectral properties of the signless
Laplacian of the sampling matrix. Our proposed
scheme achieves state-of-art performance on a
number of real-world datasets.