  Many fundamental machine learning tasks can be formulated as a problem of
learning with vector-valued functions, where we learn multiple scalar-valued
functions together. Although there is some generalization analysis on different
specific algorithms under the empirical risk minimization principle, a unifying
analysis of vector-valued learning under a regularization framework is still
lacking. In this paper, we initiate the generalization analysis of regularized
vector-valued learning algorithms by presenting bounds with a mild dependency
on the output dimension and a fast rate on the sample size. Our discussions
relax the existing assumptions on the restrictive constraint of hypothesis
spaces, smoothness of loss functions and low-noise condition. To understand the
interaction between optimization and learning, we further use our results to
derive the first generalization bounds for stochastic gradient descent with
vector-valued functions. We apply our general results to multi-class
classification and multi-label classification, which yield the first bounds
with a logarithmic dependency on the output dimension for extreme multi-label
classification with the Frobenius regularization. As a byproduct, we derive a
Rademacher complexity bound for loss function classes defined in terms of a
general strongly convex function.
