Learning Combinatorial Functions from Pairwise Comparisons
  A large body of work in machine learning has focused on the problem of
learning a close approximation to an underlying combinatorial function, given a
small set of labeled examples. However, for real-valued functions, cardinal
labels might not be accessible, or it may be difficult for an expert to
consistently assign real-valued labels over the entire set of examples. For
instance, it is notoriously hard for consumers to reliably assign values to
bundles of merchandise. Instead, it might be much easier for a consumer to
report which of two bundles she likes better. With this motivation in mind, we
consider an alternative learning model, wherein the algorithm must learn the
underlying function up to pairwise comparisons, from pairwise comparisons. In
this model, we present a series of novel algorithms that learn over a wide
variety of combinatorial function classes. These range from graph functions to
broad classes of valuation functions that are fundamentally important in
microeconomic theory, the analysis of social networks, and machine learning,
such as coverage, submodular, XOS, and subadditive functions, as well as
functions with sparse Fourier support.
