In structured output prediction tasks, labeling ground-truth training output\nis often expensive. However, for many tasks, even when the true output is\nunknown, we can evaluate predictions using a scalar reward function, which may\nbe easily assembled from human knowledge or non-differentiable pipelines. But\nsearching through the entire output space to find the best output with respect\nto this reward function is typically intractable. In this paper, we instead use\nefficient truncated randomized search in this reward function to train\nstructured prediction energy networks (SPENs), which provide efficient\ntest-time inference using gradient-based search on a smooth, learned\nrepresentation of the score landscape, and have previously yielded\nstate-of-the-art results in structured prediction. In particular, this\ntruncated randomized search in the reward function yields previously unknown\nlocal improvements, providing effective supervision to SPENs, avoiding their\ntraditional need for labeled training data.\n