  Labeling training data is a key bottleneck in the modern machine learning
pipeline. Recent weak supervision approaches combine labels from multiple noisy
sources by estimating their accuracies without access to ground truth labels;
however, estimating the dependencies among these sources is a critical
challenge. We focus on a robust PCA-based algorithm for learning these
dependency structures, establish improved theoretical recovery rates, and
outperform existing methods on various real-world tasks. Under certain
conditions, we show that the amount of unlabeled data needed can scale
sublinearly or even logarithmically with the number of sources $m$, improving
over previous efforts that ignore the sparsity pattern in the dependency
structure and scale linearly in $m$. We provide an information-theoretic lower
bound on the minimum sample complexity of the weak supervision setting. Our
method outperforms weak supervision approaches that assume
conditionally-independent sources by up to 4.64 F1 points and previous
structure learning approaches by up to 4.41 F1 points on real-world relation
extraction and image classification tasks.
