Semi-supervised Vector-valued Learning: From Theory to Algorithm
  Vector-valued learning, where the output space admits a vector-valued
structure, is an important problem that covers a broad family of important
domains, e.g. multi-label learning and multi-class classification. Using local
Rademacher complexity and unlabeled data, we derive novel data-dependent excess
risk bounds for learning vector-valued functions in both the kernel space and
linear space. The derived bounds are much sharper than existing ones, where
convergence rates are improved from $\mathcal{O}(1/\sqrt{n})$ to
$\mathcal{O}(1/\sqrt{n+u}),$ and $\mathcal{O}(1/n)$ in special cases. Motivated
by our theoretical analysis, we propose a unified framework for learning
vector-valued functions, incorporating both local Rademacher complexity and
Laplacian regularization. Empirical results on a wide number of benchmark
datasets show that the proposed algorithm significantly outperforms baseline
methods, which coincides with our theoretical findings.
