This NeurIPS 2020 paper by Qianqian Ma and Alex Olshevsky addresses a critical vulnerability in crowdsourcing: the presence of malicious or "adversarial" workers. By framing worker reliability as a robust rank-one matrix completion problem, the authors introduce a new algorithm capable of filtering out extreme perturbations. This approach accurately reconstructs data even when nearly half the workers are actively trying to subvert the system.
The Challenge of Adversarial Workers
In crowdsourcing platforms like Amazon Mechanical Turk or Yelp, algorithms often rely on the "wisdom of the crowd" to label data or provide ratings. Most standard approaches assume the Dawid-Skene (D&S) model, where workers are generally honest but make independent, random mistakes.
However, this model breaks down in the face of adversaries—workers who might collude, provide fake reviews for profit, or intentionally submit incorrect answers to trick the algorithm. Technically, estimating worker reliability in the D&S model can be viewed as a rank-one matrix completion problem. The challenge is that traditional matrix completion assumes noise is small or sparse. Adversarial noise, by contrast, can be arbitrarily large and concentrated in specific rows or columns (representing specific malicious workers), causing standard methods to fail.
The M-MSR Algorithm
To counter this, the authors propose the Matrix-Mean-Subsequence-Reduced (M-MSR) algorithm. Its core logic is built on two pillars:
- Alternating Minimization: A standard technique that iteratively updates two vectors ($u$ and $v$) to approximate a matrix $X \approx uv^T$.
- Extreme-Value Filtering: This is the algorithm's "secret sauce." In each iteration, before calculating the average to update a worker's skill level, the algorithm identifies the $F$ largest and $F$ smallest values in the neighborhood and ignores them. This prevents a single extreme adversarial value from pulling the average away from the truth.
The paper introduces the concept of $2F+1$ robustness for graphs. The authors prove that if the graph of worker-task assignments is sufficiently robust—meaning it has enough redundant connections to bypass corrupted nodes—M-MSR is guaranteed to recover the true worker reliabilities.
Key Insights and Robustness
M-MSR provides the first optimal recovery guarantees for random graphs in this setting.
- Optimality on Random Graphs: M-MSR is essentially optimal for Erdős-Rényi graphs. If the graph is dense enough to satisfy their condition, M-MSR works; if it is any sparser, no algorithm that preserves the "skew" of the initial data can succeed.
- The "Slow Decay" of Complexity: While the theoretical fraction of adversaries the algorithm can handle decreases as the population ($n$) grows, it decays very slowly (log-logarithmically). For a population the size of Earth (10 billion), the algorithm could still tolerate a healthy ~16% of malicious actors.
- Skew-Nonamplification: A key property of M-MSR is that it doesn't let the "skew" (the ratio of error) grow between iterations. This stability allows it to converge to the correct solution despite massive perturbations.
Datasets and Key Results
The authors evaluated M-MSR against 12 baseline methods using both synthetic Erdős-Rényi random graphs and 17 publicly available crowdsourcing benchmarks (including RTE, Temp, Web, Dog, TREC, and others). Because original real-world datasets lack clear adversaries, the authors manually introduced corrupted workers to test how well each algorithm could handle a "poisoned" environment.
- Dominance in Crowdsourcing: M-MSR was the top performer on 16 out of 17 real-world datasets.
- Handling High Corruption: On large datasets like TREC, M-MSR was the only method capable of handling cases where nearly 50% of the workers were corrupted. As the number of corrupted workers increased, M-MSR consistently maintained a low prediction error compared to baselines.
- Computational Efficiency: M-MSR is significantly faster than Robust Principal Component Analysis (RPCA). For a $1000 \times 1000$ matrix, M-MSR took ~0.42 seconds, while RPCA took over 80 seconds.
- Exact Recovery: In pure matrix completion tests, M-MSR showed a much higher "recovery rate" (the probability of finding the exact original matrix) compared to standard PCA and RPCA under high noise.
Limitations and Future Work
While highly effective, M-MSR has a few limitations:
- Unreliable "Normal" Workers: The algorithm struggled on the "Surprise" dataset. If even the "honest" workers are highly unreliable or provide near-random data, the filtering mechanism cannot find a stable ground-truth to converge upon.
- Graph Sparsity: On very sparse assignment graphs, a few well-placed adversaries can still "disconnect" the graph's robustness. Future work could involve "strategic edge addition"—purposefully assigning certain tasks to specific workers to boost the graph's $2F+1$ robustness.
- Partially Random Graphs: The current optimality proofs rely on Erdős-Rényi (random) structures. Real-world assignment graphs (like Yelp) are often non-random, and extending these proofs to power-law or other graph types remains an open challenge.
Summary updated