Graph-based Generalization Bounds for Learning Binary Relations
  We investigate the generalizability of learned binary relations: functions
that map pairs of instances to a logical indicator. This problem has
application in numerous areas of machine learning, such as ranking, entity
resolution and link prediction. Our learning framework incorporates an example
labeler that, given a sequence $X$ of $n$ instances and a desired training size
$m$, subsamples $m$ pairs from $X \times X$ without replacement. The challenge
in analyzing this learning scenario is that pairwise combinations of random
variables are inherently dependent, which prevents us from using traditional
learning-theoretic arguments. We present a unified, graph-based analysis, which
allows us to analyze this dependence using well-known graph identities. We are
then able to bound the generalization error of learned binary relations using
Rademacher complexity and algorithmic stability. The rate of uniform
convergence is partially determined by the labeler's subsampling process. We
thus examine how various assumptions about subsampling affect generalization;
under a natural random subsampling process, our bounds guarantee
$\tilde{O}(1/\sqrt{n})$ uniform convergence.
