# Fine-grained Generalization Analysis of Vector-valued Learning

arXiv: https://arxiv.org/abs/2104.14173 · HTML: https://mlsanity.com/paper/2104.14173/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 60 references that are in the map.
- First posted on arXiv 29 Apr 2021.

## Builds on (most cited first, 19 of 19)

- [A Survey on Multi-Task Learning](https://mlsanity.com/paper/1707.08114/) (2017)
- [A vector-contraction inequality for Rademacher complexities](https://mlsanity.com/paper/1605.00251/) (2016)
- [Tight Analyses for Non-Smooth Stochastic Gradient Descent](https://mlsanity.com/paper/1812.05217/) (2018)
- [Bonsai -- Diverse and Shallow Trees for Extreme Multi-label Classification](https://mlsanity.com/paper/1904.08249/) (2019)
- [Large-scale Multi-label Learning with Missing Labels](https://mlsanity.com/paper/1307.5101/) (2013)
- [Theoretical Insights Into Multiclass Classification: A High-dimensional Asymptotic View](https://mlsanity.com/paper/2011.07729/) (2020)
- [Stochastic Negative Mining for Learning with Large Output Spaces](https://mlsanity.com/paper/1810.07076/) (2018)
- [Top-k Multiclass SVM](https://mlsanity.com/paper/1511.06683/) (2015)
- [A Generalization Error Bound for Multi-class Domain Generalization](https://mlsanity.com/paper/1905.10392/) (2019)
- [Structured Prediction Theory Based on Factor Graph Complexity](https://mlsanity.com/paper/1605.06443/) (2016)
- [Local Rademacher Complexity-based Learning Guarantees for Multi-Task Learning](https://mlsanity.com/paper/1602.05916/) (2016)
- [Rademacher Complexity Bounds for a Penalized Multiclass Semi-Supervised Algorithm](https://mlsanity.com/paper/1607.00567/) (2016)
- [Multi-class SVMs: From Tighter Data-Dependent Generalization Bounds to Novel Algorithms](https://mlsanity.com/paper/1506.04359/) (2015)
- [Multi-label classification: do Hamming loss and subset accuracy really conflict with each other?](https://mlsanity.com/paper/2011.07805/) (2020)
- [Consistent Multitask Learning with Nonlinear Output Relations](https://mlsanity.com/paper/1705.08118/) (2017)
- [Local Rademacher Complexity for Multi-label Learning](https://mlsanity.com/paper/1410.6990/) (2014)
- [Optimistic bounds for multi-output prediction](https://mlsanity.com/paper/2002.09769/) (2020)
- [Rademacher Complexity and Generalization Performance of Multi-category Margin Classifiers](https://mlsanity.com/paper/1812.00584/) (2018)
- [Bounds for Vector-Valued Function Estimation](https://mlsanity.com/paper/1606.01487/) (2016)

## Built on by (most cited first, 5 of 5)

- [Fine-grained Generalization Analysis of Structured Output Prediction](https://mlsanity.com/paper/2106.00115/) (2021)
- [Generalization Analysis for Supervised Contrastive Representation Learning under Non-IID Settings](https://mlsanity.com/paper/2505.04937/) (2025)
- [Multiclass Loss Geometry Matters for Generalization of Gradient Descent in Separable Classification](https://mlsanity.com/paper/2505.22359/) (2025)
- [Conv4Rec: A 1-by-1 Convolutional AutoEncoder for User Profiling through Joint Analysis of Implicit and Explicit Feedbacks](https://mlsanity.com/paper/2509.07499/) (2025)
- [Explainable Neural Networks with Guarantees: A Sparse Estimation Approach](https://mlsanity.com/paper/2501.02010/) (2025)

## Abstract (arXiv)

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.