# Optimistic bounds for multi-output prediction

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Feb 2020.

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

- [Learning with Multiclass AUC: Theory and Algorithms](https://mlsanity.com/paper/2107.13171/) (2021)
- [Fine-grained Generalization Analysis of Vector-valued Learning](https://mlsanity.com/paper/2104.14173/) (2021)
- [Scalable Distributional Robustness in a Class of Non Convex Optimization with Guarantees](https://mlsanity.com/paper/2205.15624/) (2022)
- [Label Embedding via Low-Coherence Matrices](https://mlsanity.com/paper/2305.19470/) (2023)
- [How Label Imbalance Shapes Geometry: A General Spectral Analysis of Multi-Label Neural Collapse](https://mlsanity.com/paper/2605.01897/) (2026)

## Abstract (arXiv)

We investigate the challenge of multi-output learning, where the goal is to learn a vector-valued function based on a supervised data set. This includes a range of important problems in Machine Learning including multi-target regression, multi-class classification and multi-label classification. We begin our analysis by introducing the self-bounding Lipschitz condition for multi-output loss functions, which interpolates continuously between a classical Lipschitz condition and a multi-dimensional analogue of a smoothness condition. We then show that the self-bounding Lipschitz condition gives rise to optimistic bounds for multi-output learning, which are minimax optimal up to logarithmic factors. The proof exploits local Rademacher complexity combined with a powerful minoration inequality due to Srebro, Sridharan and Tewari. As an application we derive a state-of-the-art generalization bound for multi-class gradient boosting.