acceptodds
Under review as a conference paper at ICLR 2027

Finite Sample Complexity Guarantees for Feedforward Neural Networks via o-Minimality

Abstract

We prove that, in a precise sense, a broad class of feedforward neural networks (FFNN) learn (have finite sample complexity) in the PAC model: every fixed finite feedforward architecture whose layers are definable in an o-minimal structure has finite sample complexity in the agnostic PAC setting, even with unbounded parameters. Quantitative versions are obtained for general FFNNs, possibly using multivariate non-linearities, which are Pfaffian arranged in a general computational graph (DAG). This covers standard fixed-size MLPs, CNNs, GNNs, and transformers with fixed sequence length, together with the operations and layers typically used in such architectures, including linear projections, residual connections, attention mechanisms, pooling layers, normalization layers, and admissible positional encodings. Hence, distribution-free learnability for modern non-recurrent architectures is not an exceptional property of particular activations or architecture-specific VC arguments, but a consequence of tame feedforward computation. Our results reposition finite-sample PAC learnability as a baseline rather than a differentiator: they shift the focus of architectural comparison toward inductive biases, symmetries and geometric priors, scalability, and optimization behaviour.

Primary area:
learning theory
Keywords:
o-minimality, logic, learning theory, general results

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_8grrOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper combines / applies classical classical PAC type arguments with / to neural networks via a modular argument. If a (possibly complex) NN forms a DAG (which is a reasonable assumption), then by analyzing the learnability complexity of each type of node, and the connection between them, it should be possible to combine them. For each node, which can be, say, an attention layer, even if unbounded parameters are allowed, there is a limit to the class of functions learned. This pleasingly connects older foundations of learning theory like the VC dimension, to modern architectures. The paper includes specifically attention, pooling, normalization, positional encoding, etc., and at least claims to address GNNs.

Critical strengths
  1. I think the topic is an interesting tie in of classical shattering concepts and theory with more contemporary neural network architecture. I also think that the specific emphasis (attention & related like positional encoding) are interesting.
  2. The modular approach is a good way to approach arbitrary (DAG-like) networks
Critical weaknesses

Overall, the selling point of the paper being a modular approach to a shattering result, the main question is what does it add over other work.

  1. To the best of my understanding, ON SAMPLE COMPLEXITY OF NEURAL NETWORKS (https://arxiv.org/pdf/1910.11080) is uncited, and contains a large part of the selling point of the paper. To quote the abstract: "We consider functions defined by deep neural networks as definable objects in an o-miminal expansion of the real field, and derive an almost linear (in the number of weights) bound on sample complexity of such networks." While there are some added elements, I do think this weakens the incremental value of the paper by a lot.
  2. GNNs: a. They are stated as being "similar" to some proof, but the message passing is not developed. Unfortunately, this falls into one of two directions - either GNNs are fundamentally novel and the paper does not develop them, or they are very similar to MLPs, in which case point number 1 stands. b. The paper, IMHO, misrepresents VC dimension of Graph Neural Networks with. Pfaffian activation functions (https://arxiv.org/pdf/2401.12362). This paper states that this 2025 paper does not bring quantitative results based on depth, but I think it does. Here, too, if GNNs are similar, it begs the question of the added value of this paper.
Questions for authors
  1. Could you please explain the added value over the omitted ON SAMPLE COMPLEXITY OF NEURAL NETWORKS (https://arxiv.org/pdf/1910.11080)? If accepted, I think it should be cited too, but an explanation why not is also OK.
  2. Could you please clarify the two points regarding GNNs? In which way are the quantitative results here stronger than the VC GNN paper, and in what sense are GNNs similar to other architectures, but this paper different than that one?
Reviewer_kijFOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper formalizes a fixed feedforward architecture as a finite computational DAG. If every gate is jointly definable in its inputs and parameters in a common o-minimal structure, the complete network is jointly definable. Existing results about definable families then imply finite VC dimension or finite complexity of the bounded loss class, giving agnostic PAC learnability. A quantitative extension yields a loss pseudo-dimension bound of order P2U2P^2U^2, where PP is the parameter count and UU counts scalar computational outputs.

Critical strengths

The framework is useful for organizing a large collection of architectures. Its treatment of bounded positional encodings, unrestricted trigonometric functions, attention, and normalization makes the general criterion concrete. Specific strengths are:

  1. qualitative universality via o-minimality
  2. Quantitative bounds vis Pfaffian DAGs
  3. The paper systematically verifies that linear/convolutional layers, ReLU, GELU, SwiGLU, Maxout, hard-routed MoEs, Softmax etc are definable
Critical weaknesses

I think the main weakness is that modern architectures often have P>>N which makes VC type bounds completely vacuous

Questions for authors

In the proof of Theorem B.15 (Page 34, lines 1785 and 1789), there are unresolved LaTeX references

Appendix B contains two separate proofs of Theorem B.15: one on Page 26 (lines 1363–1384) and another on Page 33–34 (lines 1758–1801). This looks like an editing oversight from merging drafts

Reviewer_sGhHOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The paper studied hypothesis classes arising as the set of functions that can be computed by any assignment of parameters to a particular feedforward architecture. This is stated to include MLPs, CNNs, Transformers, etc. The paper's primary result is that any such (finite) architecture is learnable with some sample complexity, i.e., does not VC- or fat-shatter infinitely many points.

The precise assumptions underlying the main results revolve around o-minimal structures and definability of functions with respect to such structures. The paper does little to introduce or motivate these structures, making the paper often difficult to read.

Critical strengths

The paper's primary claims are precisely stated and appear to be technically sound.

Critical weaknesses

Writing: I found the paper very difficult to read. Pages 1-2 were more or less tolerable, though written in a very unusual manner. E.g., the last paragraph of page 1 spends 4 lines defining the meaning of "fixed architecture", which the average reader will be fairly familiar with. The paper also constantly uses the phrase "finite sample complexity", rather than the equivalent phrase "learnability" which anyone familiar with (agnostic) PAC learning would likely use. (I.e., a class is learnable precisely when it has a sample complexity.) On Page 3, I lost the thread of the paper and was unable to recover. I found the rest of the paper to often be terse, highly technical, and extremely difficult to read. For instance, line 142: What does it mean for a graph to be "definable in the ambient structure"? What makes a graph definable with respect to a sequence of subsets of R^n?

Significance of results: The paper's primary result seems to be that any particular feedforward architecture AA---subject to some mild assumptions---is learnable with some sample complexity depending on AA. This seems self-evident: any finite architecture only has so much "expressive power" and cannot hope to shatter infinitely many points. (Though perhaps an exponential amount in the depth of AA, for instance.) Thus, simply establishing learnability of finite architecture does not seem worthy of publishing.

Questions for authors
  • I found the paper very difficult to read, particularly beginning with page 3. Are the authors familiar with this technical content? Are they confident in its correctness? Have they attempted to provide exposition/explanation for the average ICLR reader who will be very unfamiliar with these techniques / language?
  • Doesn't learnability of finite architectures follow immediately from existing work such as Goldberg & Jerrum 95?
  • Examples 1 and 2 are inscrutable to me. You've just defined a "structure" as a sequence of subsets of R^n. How should the "real exponential field" be viewed as a sequence of such subsets? Same question when "adding all restricted analytic functions and the global exponential map" to the real exponential field.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.