  We propose a novel setting for learning, where the input domain is the image
of a map defined on the product of two sets, one of which completely determines
the labels. We derive a new risk bound for this setting that decomposes into a
bias and an error term, and exhibits a surprisingly weak dependence on the true
labels. Inspired by these results, we present an algorithm aimed at minimizing
the bias term by exploiting the ability to sample from each set independently.
We apply our setting to visual classification tasks, where our approach enables
us to train classifiers on datasets that consist entirely of a single synthetic
example of each class. On several standard benchmarks for real-world image
classification, we achieve robust performance in the context-agnostic setting,
with good generalization to real world domains, whereas training directly on
real world data without our techniques yields classifiers that are brittle to
perturbations of the background.
