Margin in Abstract Spaces

Yair Ashlagi, Roi Livni, Shay Moran, Tom Waknine

TL;DR

This paper investigates the fundamental mathematical requirements for margin-based learning. The authors discover that sufficiently large margins allow for learnability in any metric space using only the triangle inequality, but they also prove that "kernel-style" embeddings into linear spaces are not a universal explanation for margin-based generalization.

What Problem Does This Paper Address?

In machine learning, "margin" is a classic trick for achieving generalization that doesn't depend on the number of parameters. We see this most famously in Support Vector Machines (SVMs) and kernel methods, where we assume data points are separated by a clear gap from the decision boundary.

However, most existing theory relies on "nice" geometric structures like Euclidean or Hilbert spaces. This paper asks a deeper foundational question: What is the absolute minimum mathematical structure needed for margin-based learning to work? Does it require linear algebra and dot products, or can we get away with something much simpler, like a basic metric space where we only know the distances between points? Furthermore, can every learnable margin problem be "explained away" by embedding it into a linear space (the core idea behind kernel methods)?

Methods

The authors use theoretical analysis to bridge the gap between abstract metric spaces and structured Banach (normed linear) spaces. Their approach includes:

  • Metric Space Analysis: They define a "distance-based" concept class where points are classified based on their distance from a center point.
  • Shattering Characterization: They introduce a new geometric characterization of "shattering" (a key concept in VC dimension theory) that works for abstract margin spaces. This tool allows them to move between geometric, linear, and functional concepts seamlessly.
  • Banach Space Taxonomy: They apply deep results from functional analysis (like Dvoretzky’s theorem and the Maurey–Pisier theorem) to categorize how sample complexity scales with the margin parameter $\gamma$ in different types of linear spaces.
  • Counter-example Construction: To test the universality of linear embeddings, they construct a specific, learnable concept class that grows "too fast" to ever fit inside a standard Banach space.

Datasets

As this is a theoretical paper focused on proving mathematical theorems, no empirical datasets were used for training or evaluation. The authors instead use abstract mathematical constructions (such as specific metric spaces and sequences in $\ell_p$ spaces) to prove their bounds.

Key Insights and Ideas

  • The Power of the Triangle Inequality: For a simple distance-based classifier (positive if distance $\le r$, negative if distance $> R$), the class is learnable in any metric space as long as $R > 3r$. In this regime, the VC dimension is exactly 1. This means you don't need a coordinate system or a dot product; the triangle inequality alone guarantees learnability.
  • The $1/3$ Threshold: There is a sharp "dichotomy." If the normalized margin is above $1/3$, it's always learnable. Below $1/3$, learnability becomes "space-dependent"—it might be learnable in some spaces but completely impossible in others.
  • Total Boundedness is Key: For more complex Lipschitz functions, the authors show that learnability is equivalent to the space being "totally bounded" (meaning it can be covered by a finite number of small balls).
  • The "Polynomial Speed Limit" of Banach Spaces: In any infinite-dimensional Banach space, if a problem is learnable for one margin, it's learnable for all. However, the sample complexity must scale polynomially (specifically at least $1/\gamma^2$).
  • Kernel Methods are Not Universal: The most surprising insight is that there exist concept classes that are perfectly learnable for any margin $\gamma > 0$, but which cannot be embedded into any Banach space. This proves that the "kernel trick" is not the only way nature achieves margin-based learning.

Key Results

  • Theorem 3.1 (Dichotomy): Established the universal learnability threshold at $\gamma = 1/3$ for distance-based functions.
  • Theorem 3.3 (Taxonomy): Proved that in Banach spaces, the $\gamma$-VC dimension scales as $(1/\gamma)^p$ for some $p \ge 2$. They also showed that for any $p \ge 2$, there exists a Banach space that hits that specific rate.
  • Theorem 3.6 (Non-embeddability): Demonstrated the existence of a symmetric, convex set of functions that is learnable for all $\gamma$ but admits no embedding into a learnable Banach space. This is because its sample complexity grows faster than any polynomial, violating the "speed limit" of linear spaces.

Limitations and Future Work

The paper is primarily a work of "pure" learning theory. While it provides a beautiful map of the mathematical landscape of margins, it does not provide:

  • Practical Algorithms: The proofs are existential. Translating these abstract metric space results into efficient, scalable algorithms for real-world data remains an open challenge.
  • Tight Constants: While the authors found the polynomial rates for $\ell_p$ spaces, they note that finding the exact constants (the dependence on $p$) is still an interesting open problem.
  • Broader Concept Classes: The work focuses on distance-based and Lipschitz functions. Extending this "abstract margin" framework to other types of non-linear hypotheses could yield further insights into modern deep learning.

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