Sharp Generalization of Transductive Learning: A Transductive Local
  Rademacher Complexity Approach
Yingzhen Yang
We introduce a new tool, Transductive Local Rademacher Complexity (TLRC), to
analyze the generalization performance of transductive learning methods and
motivate new transductive learning algorithms. Our work extends the idea of the
popular Local Rademacher Complexity (LRC) to the transductive setting with
considerable changes compared to the analysis of typical LRC methods in the
inductive setting. We present a localized version of Rademacher complexity
based tool wihch can be applied to various transductive learning problems and
gain sharp bounds under proper conditions. Similar to the development of LRC,
we build TLRC by starting from a sharp concentration inequality for independent
variables with variance information. The prediction function class of a
transductive learning model is then divided into pieces with a sub-root
function being the upper bound for the Rademacher complexity of each piece, and
the variance of all the functions in each piece is limited. A carefully
designed variance operator is used to ensure that the bound for the test loss
on unlabeled test data in the transductive setting enjoys a remarkable
similarity to that of the classical LRC bound in the inductive setting. We use
the new TLRC tool to analyze the Transductive Kernel Learning (TKL) model,
where the labels of test data are generated by a kernel function. The result of
TKL lays the foundation for generalization bounds for two types of transductive
learning tasks, Graph Transductive Learning (GTL) and Transductive
Nonparametric Kernel Regression (TNKR). When the target function is
low-dimensional or approximately low-dimensional, we design low rank methods
for both GTL and TNKR, which enjoy particularly sharper generalization bounds
by TLRC which cannot be achieved by existing learning theory methods, to the
best of our knowledge.