# Gradient Descent for Sparse Rank-One Matrix Completion for Crowd-Sourced Aggregation of Sparsely Interacting Workers

arXiv: https://arxiv.org/abs/1904.11608 · HTML: https://mlsanity.com/paper/1904.11608/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Apr 2019.

## Built on by (most cited first, 11 of 11)

- [Crowdsourcing via Annotator Co-occurrence Imputation and Provable Symmetric Nonnegative Matrix Factorization](https://mlsanity.com/paper/2106.07193/) (2021)
- [Factorization Approach for Low-complexity Matrix Completion Problems: Exponential Number of Spurious Solutions and Failure of Gradient Methods](https://mlsanity.com/paper/2110.10279/) (2021)
- [Rank-1 Matrix Completion with Gradient Descent and Small Random Initialization](https://mlsanity.com/paper/2212.09396/) (2022)
- [A Worker-Task Specialization Model for Crowdsourcing: Efficient Inference and Fundamental Limits](https://mlsanity.com/paper/2111.12550/) (2021)
- [A Light-weight, Effective and Efficient Model for Label Aggregation in Crowdsourcing](https://mlsanity.com/paper/2212.00007/) (2022)
- [Crowd-Certain: Label Aggregation in Crowdsourced and Ensemble Learning Classification](https://mlsanity.com/paper/2310.16293/) (2023)
- [Detecting adversaries in Crowdsourcing](https://mlsanity.com/paper/2110.04117/) (2021)
- [Identify ambiguous tasks combining crowdsourced labels by weighting Areas Under the Margin](https://mlsanity.com/paper/2209.15380/) (2022)
- [Recovering Top-Two Answers and Confusion Probability in Multi-Choice Crowdsourcing](https://mlsanity.com/paper/2301.00006/) (2022)
- [Spectral Clustering for Crowdsourcing with Inherently Distinct Task Types](https://mlsanity.com/paper/2302.07393/) (2023)
- [Entry-Specific Matrix Estimation under Arbitrary Sampling Patterns through the Lens of Network Flows](https://mlsanity.com/paper/2409.03980/) (2024)

## Abstract (arXiv)

We consider worker skill estimation for the single-coin 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 correlations between workers. We show that the correlation matrix can be successfully recovered and skills are identifiable if and only if the sampling matrix (observed components) does not have a bipartite connected component. We then propose a projected gradient descent scheme and show that skill estimates converge 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 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.