Technical Summary: Finite Sample Complexity of Feedforward Neural Networks in o-Minimal Structures

1. Problem Statement

The paper addresses a fundamental question in statistical learning theory: Do all standard, fixed finite feedforward neural networks possess finite sample complexity in the Probably Approximately Correct (PAC) learning model?

While specific architectural families (e.g., piecewise-linear MLPs, specific GNNs, or transformers) have previously been shown to be learnable via architecture-specific arguments (such as VC dimension bounds for ReLU networks), a unified theoretical guarantee covering the broad spectrum of modern architectures—including those with unbounded parameters—has been lacking. The authors investigate whether the "tame" nature of the mathematical functions composing these networks is sufficient to guarantee learnability without imposing restrictive weight constraints or relying on ad-hoc combinatorial proofs for each new architecture.

2. Methodology and Theoretical Framework

2.1 O-Minimal Structures

The core methodology relies on o-minimal structures, a concept from mathematical logic and model theory. An o-minimal structure $\mathcal{S}$ expanding the real field is a collection of subsets of $\mathbb{R}^n$ that is closed under Boolean operations, projections, and Cartesian products, with the crucial property that every definable subset of $\mathbb{R}$ is a finite union of points and intervals. This "tameness" prevents the pathological oscillations that typically lead to infinite VC dimensions.

The authors utilize the following key logical tools:

• Definability: A map is definable if its graph is a definable set within the structure.
• Joint Definability: The authors establish that if the primitive operations (gates) of a network are definable, the entire network function is jointly definable in its inputs and parameters.
• Cell Decomposition: A fundamental theorem in o-minimal geometry states that any definable set can be decomposed into a finite number of "cells." This implies that the number of connected components of level sets (oscillations) of a definable function is uniformly bounded, regardless of the parameter values.

2.2 Network Formalization

The paper defines a G-Neural Network as a computation organized by a Directed Acyclic Graph (DAG).

• Nodes: Input nodes, computation nodes (gates), and output nodes.
• Gates: Parametrized maps $g: \mathbb{R}^n \times \mathbb{R}^p \to \mathbb{R}^m$ selected from a "gate dictionary" $\mathcal{G}$.
• Composition: The network computes a function $f_\theta(x)$ by propagating states through the DAG, where $\theta$ represents the trainable parameters.

The central technical insight is Proposition 2.5: If every gate in the dictionary $\mathcal{G}$ is definable in an o-minimal structure $\mathcal{S}$, then the resulting G-Neural Network is jointly definable in its inputs and parameters.

3. Key Contributions

3.1 Unified Learnability Theorems

The paper provides two main theorems establishing finite sample complexity for the agnostic PAC setting:

• Theorem 3.1 (Classification): For any fixed finite feedforward architecture with definable layers, the class of classifiers has finite VC dimension. Consequently, the empirical risk converges uniformly to the true risk with a sample complexity bound of $O(K \log(1/\delta) / \epsilon^2)$, where $K$ depends on the architecture but not on the parameter magnitude.
• Theorem 3.2 (Regression): For regression with definable loss functions (e.g., clipped MSE, MAE), the class has finite pseudo-dimension (and fat-shattering dimension), yielding similar uniform convergence guarantees.

Crucial Distinction: These results hold even when the parameter space is unbounded. Traditional covering number arguments often fail here because the metric size of the parameter space diverges as weights grow. The o-minimal approach bypasses this by bounding the geometric complexity (number of oscillations) of the function class rather than the metric size of the parameter space.

3.2 Verification of Definability for Modern Architectures

A significant portion of the work (Section 4) verifies that the "definability assumption" is mild by proving that standard deep learning components are definable in specific o-minimal structures (primarily $\mathbb{R}_{exp}$ and $\mathbb{R}_{an,exp}$):

• Linear/Convolutional Layers: Polynomial maps (semi-algebraic).
• Activation Functions: ReLU, LeakyReLU, Sigmoid, Tanh, Softplus, GELU, Swish, SwiGLU, and Mish are shown to be definable in $\mathbb{R}_{exp}$ or $\mathbb{R}_{an,exp}$.
• Attention Mechanisms: Multi-head self-attention and cross-attention are definable in $\mathbb{R}_{exp}$ due to the definability of the exponential function and softmax.
• Normalization: Batch, Layer, Group, and RMS normalization are semi-algebraic.
• Positional Encodings: Fourier-based encodings are definable provided the position domain is bounded (a standard constraint in practice).
• Advanced Blocks: Residual connections, gating mechanisms, Maxout, and Deep Equilibrium (DEQ) layers are shown to preserve definability.

3.3 Architectural Corollaries

By combining the definability of primitives with the closure properties of o-minimal structures, the authors derive that the following standard architectures have finite sample complexity:

• Multilayer Perceptrons (MLPs)
• Convolutional Neural Networks (CNNs)
• Graph Neural Networks (GNNs)
• Transformers (including those with fixed sequence lengths)

4. Results and Significance

4.1 Main Result

The paper concludes that distribution-free learnability is a universal consequence of tame feedforward computation. Any fixed finite feedforward architecture constructed from definable primitives (which covers the vast majority of modern non-recurrent models) has finite sample complexity in the agnostic PAC setting, regardless of parameter bounds.

4.2 Shift in Perspective

The authors argue that this result repositions finite sample complexity from a "differentiator" to a baseline property.

• Previous View: Learnability was often seen as a fragile property requiring specific architectural constraints or activation functions to prove.
• New View: Learnability is automatic for any "tame" feedforward model. Therefore, the theoretical focus should shift away from proving whether a model learns, and toward understanding how it learns.

4.3 Practical Implications

The paper suggests that architectural comparisons should be guided by finer criteria rather than general learnability:

• Inductive Biases: How well the architecture encodes problem-specific symmetries and geometric priors.
• Optimization Behavior: The landscape of the loss function and convergence properties.
• Scalability: Computational efficiency and ability to handle growing model sizes.

4.4 Limitations

The authors explicitly note the scope and limitations:

• Fixed Architecture: The results apply to fixed depth, width, and graph size. They do not provide uniform bounds for growing model sizes.
• No Recurrence: Genuinely recurrent architectures (RNNs, looped transformers) are not covered unless unrolled to a fixed time horizon.
• Qualitative Nature: The bounds are qualitative (existence of constants) rather than providing sharp, architecture-specific rates.
• Optimization: The paper guarantees learnability (existence of a good hypothesis) but makes no claims about the efficiency of finding it (optimization guarantees).

5. Conclusion

The paper establishes that the mathematical "tame-ness" of modern neural networks, formalized through o-minimal structures, is sufficient to guarantee finite sample complexity. This unifies the learning theory of diverse architectures under a single framework, suggesting that the ability to learn is a generic feature of feedforward computation rather than a special property of specific designs. The authors conclude that future research should focus on the specific inductive biases and optimization dynamics that distinguish architectures, rather than their fundamental capacity to learn.