# Generalization bounds for multiclass learning when the output is vector space?

There are plenty of results for muli-class learning with with fixed discrete labels:
$$\text{Standard multi-class classification:} \begin{cases} f: X \rightarrow Y_{index} = \{1, 2, 3, ..., k \}, \\ s.t. X \subset \mathbb{R}^{d_x} \end{cases}$$

I was wondering if there are any results which study multi-class learning with (countable, possibly finite) vector-valued outputs.

$$\text{Vector-output multi-class classification:} \begin{cases} f: X \rightarrow Y_{vector} = \{y_1, y_2, y_3, ..., y_k \}, \\ s.t. X \subset \mathbb{R}^{d_x}, y_i \in \mathbb{R}^{d_y} \end{cases}$$

One may suggest that this is another problem: metric-learning between $X$ and $Y$ space: $$\text{Standard metric-learning problem:} \begin{cases} f: X, Y \rightarrow [0,1], \\ s.t. X \subset \mathbb{R}^{d_x}, Y \subset \mathbb{R}^{d_y} \end{cases}$$

However all the results I came across in the metric-learning study the functions on one single vector space (as in unsupervised metric learning). In addition, vector-output multi-class classification is much more restricted (easier to learn?) than metric learning, since in what I am asking, the number of possible output vectors is fixed (unlike metric learning).

Sounds like you're trying to learn a map from vector space $X$ to vector space $Y$. The first thing that comes to mind is regression, which is a map from $X$ to $\mathbb{R}$. You can of course perform multiple regressions in parallel -- one for each dimension of $Y$ -- to learn a map from $X$ to $Y$. This has the shortcoming of ignoring any "interaction" or dependencies between the labels. You could first perform PCA on both the inputs in $X$ and the outputs in $Y$, and learn a map from the principal vectors of the input to the principle vectors of the output.
Another idea -- one that I'm particularly fond of -- is to perform Lipschitz extension. This assumes that $X$ and $Y$ are both metric spaces with known metrics. (A much more general setting than vectors spaces!) See the pioneering paper of von Luxburg and Bousquet, for example: http://www.jmlr.org/papers/volume5/luxburg04b/luxburg04b.pdf