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