# Complexity of Vector-valued Prediction: From Linear Models to Stochastic Convex Optimization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 19 references that are in the map.
- First posted on arXiv 5 Dec 2024.

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

- [The Sample Complexity of One-Hidden-Layer Neural Networks](https://mlsanity.com/paper/2202.06233/) (2022)
- [The Sample Complexity Of ERMs In Stochastic Convex Optimization](https://mlsanity.com/paper/2311.05398/) (2023)
- [The Dimension Strikes Back with Gradients: Generalization of Gradient Methods in Stochastic Convex Optimization](https://mlsanity.com/paper/2401.12058/) (2024)
- [The Sample Complexity of Gradient Descent in Stochastic Convex Optimization](https://mlsanity.com/paper/2404.04931/) (2024)
- [On the Sample Complexity of Two-Layer Networks: Lipschitz vs. Element-Wise Lipschitz Activation](https://mlsanity.com/paper/2211.09634/) (2022)
- [Initialization-Dependent Sample Complexity of Linear Predictors and Neural Networks](https://mlsanity.com/paper/2305.16475/) (2023)

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

- [Multiclass Loss Geometry Matters for Generalization of Gradient Descent in Separable Classification](https://mlsanity.com/paper/2505.22359/) (2025)

## Abstract (arXiv)

We study the problem of learning vector-valued linear predictors: these are prediction rules parameterized by a matrix that maps an m-dimensional feature vector to a k-dimensional target. We focus on the fundamental case with a convex and Lipschitz loss function, and show several new theoretical results that shed light on the complexity of this problem and its connection to related learning models. First, we give a tight characterization of the sample complexity of Empirical Risk Minimization (ERM) in this setting, establishing that smashwidetildeOmega(k/ε2) examples are necessary for ERM to reach ε excess (population) risk; this provides for an exponential improvement over recent results by Magen and Shamir (2023) in terms of the dependence on the target dimension k, and matches a classical upper bound due to Maurer (2016). Second, we present a black-box conversion from general d-dimensional Stochastic Convex Optimization (SCO) to vector-valued linear prediction, showing that any SCO problem can be embedded as a prediction problem with k=Theta(d) outputs. These results portray the setting of vector-valued linear prediction as bridging between two extensively studied yet disparate learning models: linear models (corresponds to k=1) and general d-dimensional SCO (with k=Theta(d)).