In many applications of machine learning, labeled data is scarce and obtaining additional labels is expensive. We introduce a new approach to supervising learning algorithms without labels by enforcing a small number of domain-specific constraints over the algorithms' outputs. The constraints can be provided explicitly based on prior knowledge -- e.g. we may require that objects detected in videos satisfy the laws of physics -- or implicitly extracted from data using a novel framework inspired by adversarial training. We demonstrate the effectiveness of constraint-based learning on a variety of tasks -- including tracking, object detection, and human pose estimation -- and we find that algorithms supervised with constraints achieve high accuracies with only a small amount of labels, or with no labels at all in some cases.