Margin in Abstract Spaces

Yair Ashlagi, Roi Livni, Shay Moran, Tom Waknine

Abstract

Margin-based learning, exemplified by linear and kernel methods, is one of the few classical settings where generalization guarantees are independent of the number of parameters. This makes it a central case study in modern highly over-parameterized learning. We ask what minimal mathematical structure underlies this phenomenon. We begin with a simple margin-based problem in arbitrary metric spaces: concepts are defined by a center point and classify points according to whether their distance lies below $r$ or above $R$. We show that whenever $R>3r$, this class is learnable in \emph{any} metric space. Thus, sufficiently large margins make learnability depend only on the triangle inequality, without any linear or analytic structure. Our first main result extends this phenomenon to concepts defined by bounded linear combinations of distance functions, and reveals a sharp threshold: there exists a universal constant $\gamma>0$ such that above this margin the class is learnable in every metric space, while below it there exist metric spaces where it is not learnable at all. We then ask whether margin-based learnability can always be explained via an embedding into a linear space -- that is, reduced to linear classification in some Banach space through a kernel-type construction. We answer this negatively by developing a structural taxonomy of Banach spaces: if a Banach space is learnable for some margin parameter $\gamma\geq 0$, then it is learnable for all such $\gamma$, and in infinite-dimensional spaces the sample complexity must scale polynomially in $1/\gamma$. Specifically, it must grow as $(1/\gamma)^p$ for some $p\ge 2$, and every such rate is attainable.

Introduction

Margin-based learning is a cornerstone of statistical learning theory, providing generalization guarantees that are remarkably independent of the number of parameters. This property is central to understanding why over-parameterized models, like deep neural networks or Support Vector Machines (SVMs), generalize well. Traditionally, these guarantees are derived within the context of linear or kernel methods in Euclidean or Hilbert spaces. This research investigates the fundamental mathematical requirements for margin-based learning, asking: what is the absolute minimum structure needed? Does it require linear algebra and dot products, or can the triangle inequality alone suffice?

Theoretical Framework and Methods

The study shifts the focus from structured linear spaces to abstract metric spaces. The authors define a "distance-based" concept class where a concept is defined by a center point $x$ and a radius. Points are classified as positive if their distance to $x$ is $\le r$ and negative if their distance is $\ge R$.

A distance-based concept class in a metric space. Points $x_1$ and $x_2$ are classified based on their distances $r$ and $R$ from a center point $x$.

To analyze these classes, the authors introduce a geometric characterization of "shattering" suitable for abstract margin spaces. This allows for a rigorous treatment of VC dimension without relying on linear structure. This tool enables moving between geometric, linear, and functional concepts seamlessly by mapping relationships between sets of points.

A geometric construction illustrating the shattering characterization in abstract margin spaces.

The authors also employ tools from functional analysis, such as Dvoretzky’s theorem and the Maurey–Pisier theorem, to categorize how sample complexity scales with the margin parameter $\gamma$ in Banach (normed linear) spaces. To test the universality of linear embeddings, they construct specific, learnable concept classes that grow "too fast" to ever fit inside a standard Banach space.

Key Results and Insights

The research yields several fundamental insights into the nature of margins:

  • The 1/3 Threshold (Theorem 3.1): A sharp "dichotomy" exists for universal learnability. If the normalized margin is above $1/3$ (specifically $R > 3r$), the concept class is learnable in any metric space using only the triangle inequality. In this regime, the VC dimension is exactly 1. Below $1/3$, learnability becomes space-dependent—it might be possible in some spaces but impossible in others.
  • Total Boundedness: For more complex Lipschitz functions, learnability is shown to be equivalent to the space being "totally bounded," meaning it can be covered by a finite number of small balls.
  • The Polynomial Speed Limit (Theorem 3.3): In any infinite-dimensional Banach space, if a problem is learnable for one margin, it is learnable for all. However, the sample complexity must scale polynomially with the inverse margin (specifically at least $1/\gamma^2$). The authors show that for any $p \ge 2$, there exists a Banach space that hits that specific rate.
  • Non-universality of Kernels (Theorem 3.6): Perhaps most significantly, the authors prove that the "kernel trick" is not a universal explanation for margin-based learning. They demonstrate the existence of a symmetric, convex set of functions that is learnable for all $\gamma$ but admits no embedding into any learnable Banach space. This is because its sample complexity grows faster than any polynomial, violating the "speed limit" of linear spaces.

Conclusion and Future Work

This work reveals that while margins often imply linear structure, they can also operate purely through the triangle inequality in abstract spaces. The discovery of learnable classes that defy linear embedding suggests that there are mechanisms for generalization beyond the reach of traditional kernel methods.

While this provides a new map of the mathematical landscape of margins, several challenges remain. The proofs are primarily existential, and translating these abstract metric space results into efficient, scalable algorithms for real-world data is an open problem. Additionally, extending this "abstract margin" framework to broader, non-linear hypothesis classes could yield further insights into the generalization properties of modern deep learning architectures.

Summary updated

Abstract

Margin-based learning, exemplified by linear and kernel methods, is one of the few classical settings where generalization guarantees are independent of the number of parameters. This makes it a central case study in modern highly over-parameterized learning. We ask what minimal mathematical structure underlies this phenomenon. We begin with a simple margin-based problem in arbitrary metric spaces: concepts are defined by a center point and classify points according to whether their distance lies below $r$ or above $R$. We show that whenever $R>3r$, this class is learnable in \emph{any} metric space. Thus, sufficiently large margins make learnability depend only on the triangle inequality, without any linear or analytic structure. Our first main result extends this phenomenon to concepts defined by bounded linear combinations of distance functions, and reveals a sharp threshold: there exists a universal constant $γ>0$ such that above this margin the class is learnable in every metric space, while below it there exist metric spaces where it is not learnable at all. We then ask whether margin-based learnability can always be explained via an embedding into a linear space -- that is, reduced to linear classification in some Banach space through a kernel-type construction. We answer this negatively by developing a structural taxonomy of Banach spaces: if a Banach space is learnable for some margin parameter $γ\geq 0$, then it is learnable for all such $γ$, and in infinite-dimensional spaces the sample complexity must scale polynomially in $1/γ$. Specifically, it must grow as $(1/γ)^p$ for some $p\ge 2$, and every such rate is attainable.
BibTeX
@inproceedings{ashlagi2026margin,
  author = {Yair Ashlagi and Roi Livni and Shay Moran and Tom Waknine},
  title = {{Margin in Abstract Spaces}},
  booktitle = {Conference on Learning Theory},
  year = {2026},
}

Loading related content...

Figure