Data driven semi-supervised learning
  We consider a novel data driven approach for designing learning algorithms
that can effectively learn with only a small number of labeled examples. This
is crucial for modern machine learning applications where labels are scarce or
expensive to obtain. We focus on graph-based techniques, where the unlabeled
examples are connected in a graph under the implicit assumption that similar
nodes likely have similar labels. Over the past decades, several elegant
graph-based semi-supervised learning algorithms for how to infer the labels of
the unlabeled examples given the graph and a few labeled examples have been
proposed. However, the problem of how to create the graph (which impacts the
practical usefulness of these methods significantly) has been relegated to
domain-specific art and heuristics and no general principles have been
proposed. In this work we present a novel data driven approach for learning the
graph and provide strong formal guarantees in both the distributional and
online learning formalizations.
  We show how to leverage problem instances coming from an underlying problem
domain to learn the graph hyperparameters from commonly used parametric
families of graphs that perform well on new instances coming from the same
domain. We obtain low regret and efficient algorithms in the online setting,
and generalization guarantees in the distributional setting. We also show how
to combine several very different similarity metrics and learn multiple
hyperparameters, providing general techniques to apply to large classes of
problems. We expect some of the tools and techniques we develop along the way
to be of interest beyond semi-supervised learning, for data driven algorithms
for combinatorial problems more generally.
