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