# Adversarial Crowdsourcing Through Robust Rank-One Matrix Completion

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Oct 2020.

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

- [Out of the BLEU: how should we assess quality of the Code Generation models?](https://mlsanity.com/paper/2208.03133/) (2022)
- [Adaptive Trajectory Prediction via Transferable GNN](https://mlsanity.com/paper/2203.05046/) (2022)
- [If in a Crowdsourced Data Annotation Pipeline, a GPT-4](https://mlsanity.com/paper/2402.16795/) (2024)
- [SCoFT: Self-Contrastive Fine-Tuning for Equitable Image Generation](https://mlsanity.com/paper/2401.08053/) (2024)
- [Transferring Annotator- and Instance-dependent Transition Matrix for Learning from Crowds](https://mlsanity.com/paper/2306.03116/) (2023)
- [Semi-supervised Domain Adaptive Structure Learning](https://mlsanity.com/paper/2112.06161/) (2021)
- [Culture-TRIP: Culturally-Aware Text-to-Image Generation with Iterative Prompt Refinement](https://mlsanity.com/paper/2502.16902/) (2025)
- [Rethinking Noisy Label Models: Labeler-Dependent Noise with Adversarial Awareness](https://mlsanity.com/paper/2105.14083/) (2021)
- [Rank-1 Matrix Completion with Gradient Descent and Small Random Initialization](https://mlsanity.com/paper/2212.09396/) (2022)
- [Cooperative learning of Pl@ntNet's Artificial Intelligence algorithm: how does it work and how can we improve it?](https://mlsanity.com/paper/2406.03356/) (2024)
- [Task Oriented Video Coding: A Survey](https://mlsanity.com/paper/2208.07313/) (2022)
- [Learning From Crowdsourced Noisy Labels: A Signal Processing Perspective](https://mlsanity.com/paper/2407.06902/) (2024)
- [A Worker-Task Specialization Model for Crowdsourcing: Efficient Inference and Fundamental Limits](https://mlsanity.com/paper/2111.12550/) (2021)
- [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)
- [Robust Decision Aggregation with Adversarial Experts](https://mlsanity.com/paper/2403.08222/) (2024)
- [Recovering Top-Two Answers and Confusion Probability in Multi-Choice Crowdsourcing](https://mlsanity.com/paper/2301.00006/) (2022)
- [Entry-Specific Matrix Estimation under Arbitrary Sampling Patterns through the Lens of Network Flows](https://mlsanity.com/paper/2409.03980/) (2024)
- [WISE: Weighted Iterative Society-of-Experts for Robust Multimodal Multi-Agent Debate](https://mlsanity.com/paper/2512.02405/) (2025)
- [Unsupervised Ensemble Learning Through Deep Energy-based Models](https://mlsanity.com/paper/2601.20556/) (2026)
- [StackingNet: Collective Inference Across Independent AI Foundation Models](https://mlsanity.com/paper/2602.13792/) (2026)

## Abstract (arXiv)

We consider the problem of reconstructing a rank-one matrix from a revealed subset of its entries when some of the revealed entries are corrupted with perturbations that are unknown and can be arbitrarily large. It is not known which revealed entries are corrupted. We propose a new algorithm combining alternating minimization with extreme-value filtering and provide sufficient and necessary conditions to recover the original rank-one matrix. In particular, we show that our proposed algorithm is optimal when the set of revealed entries is given by an ErdHos-R'enyi random graph. These results are then applied to the problem of classification from crowdsourced data under the assumption that while the majority of the workers are governed by the standard single-coin David-Skene model (i.e., they output the correct answer with a certain probability), some of the workers can deviate arbitrarily from this model. In particular, the "adversarial" workers could even make decisions designed to make the algorithm output an incorrect answer. Extensive experimental results show our algorithm for this problem, based on rank-one matrix completion with perturbations, outperforms all other state-of-the-art methods in such an adversarial scenario.