# On Reductions and Representations of Learning Problems in Euclidean Spaces

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 25 references that are in the map.
- First posted on arXiv 16 Nov 2024.

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

- [Approximate is Good Enough: Probabilistic Variants of Dimensional and Margin Complexity](https://mlsanity.com/paper/2003.04180/) (2020)
- [Local Borsuk-Ulam, Stability, and Replicability](https://mlsanity.com/paper/2311.01599/) (2023)
- [Metalearning with Very Few Samples Per Task](https://mlsanity.com/paper/2312.13978/) (2023)

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

- [Spherical dimension](https://mlsanity.com/paper/2503.10240/) (2025)

## Abstract (arXiv)

Many practical prediction algorithms represent inputs in Euclidean space and replace the discrete 0/1 classification loss with a real-valued surrogate loss, effectively reducing classification tasks to stochastic optimization. In this paper, we investigate the expressivity of such reductions in terms of key resources, including dimension and the role of randomness. We establish bounds on the minimum Euclidean dimension D needed to reduce a concept class with VC dimension d to a Stochastic Convex Optimization (SCO) problem in ℝD, formally addressing the intuitive interpretation of the VC dimension as the number of parameters needed to learn the class. To achieve this, we develop a generalization of the Borsuk-Ulam Theorem that combines the classical topological approach with convexity considerations. Perhaps surprisingly, we show that, in some cases, the number of parameters D must be exponentially larger than the VC dimension d, even if the reduction is only slightly non-trivial. We also present natural classification tasks that can be represented in much smaller dimensions by leveraging randomness, as seen in techniques like random initialization. This result resolves an open question posed by Kamath, Montasser, and Srebro (COLT 2020). Our findings introduce new variants of dimension complexity (also known as sign-rank), a well-studied parameter in learning and complexity theory. Specifically, we define an approximate version of sign-rank and another variant that captures the minimum dimension required for a reduction to SCO. We also propose several open questions and directions for future research.