CS Paper Radar

Memorization Capacity of Invariant Convolutional Neural Nets

Sjoerd Dirksen, Patrick Finke, Paul Geuchen

cs.LG stat.MLmath.ST ·submitted 2026-10-28 21:23 UTC · v1
theory

Abstract

Neural networks are powerful memorizers which are often able to interpolate their training data even when the labels have been randomized. While there exists an extensive literature on the memorization capacity of fully connected networks, in practice more specific architectures with problem-dependent properties are preferred, such as convolutional networks for image classification. In this paper we consider convolutional networks which are invariant with respect to a given arbitrary finite group of orthogonal transformations, which may include translations, reflections, and/or rotations of images and invariances of higher order tensors. We prove upper bounds on the size of an invariant convolutional neural network with threshold activations that is required to interpolate a given dataset with two classes. Our bounds are formulated in terms of a complexity measure that takes the invariant structure into account and is instance-specific, i.e., it is related to the mutual arrangement of the classes in the given dataset and their geometric properties rather than the number of samples. Our proof is constructive: for given input data, instances of an interpolating network can be computed via a randomized algorithm with high probability. In numerical experiments we investigate the practical effectiveness of this algorithm.

Closest papers

Nearest neighbours by meaning across the whole index.

On Making $\mathrm{SE}(2)$-Invariant Networks Optimal

cs.LG cs.AI ·2026-10-12 ·Tomas Karella, Emily Shinkle, Alice Elisabeth Anastasia Allen, Pieter J. Swart, Nicholas Lubbers +1 more
top venue similarity 0.64
Abstract · Accepted to the main track of NeurIPS 2026

Respecting a-priori known symmetries of underlying data is a key principle in designing efficient neural architectures. Convolutional neural networks are a canonical example, encoding translation equivariance. Extending this inductive bias to richer symmetry groups such as $\mathrm{SE}(2)$ in the most effective way possible is an ongoing architectural and computational challenge. Building on classical invariant theory, we derive invariant feature maps that are provably optimal: minimal and information-preserving with respect to the symmetry group. Our construction is designed to integrate seamlessly into standard architectures, requiring no modification to nonlinearities or normalization layers. As a concrete implementation, we introduce a plug-and-play module for convolutional neural networks that enforces $\mathrm{SE}(2)$ invariance, capturing both translations and rotations within standard architectures. The resulting models are both efficient and expressive. Experiments show competitive or improved accuracy compared to state-of-the-art equivariant methods at significantly lower computational cost. Finally, we provide a theoretical and empirical analysis of the relationship between equivariance and invariance, offering insight into their roles in controlling robustness and flexibility.

0.34

Memorization in image classification: test set behavior and scaling laws

cs.LG ·2026-10-12 ·Jeevesh Attri, Florentin Guth
publishedposition similarity 0.64
Abstract · 11 Pages, 4 figures, Accepted at the NeurIPS 2026 Workshop on Neural Network Artifacts as a New Data Modality

Deep neural networks are capable of both learning generalizing solutions on natural tasks and memorizing arbitrary mappings. We argue that understanding the former requires understanding the latter, which is much less studied. In what ways do networks that generalize or memorize differ in their behavior or their training dynamics? Do memorizing networks simply function as a lookup table where input-output mappings are stored independently? We investigate these questions in the context of CNNs trained on image classification tasks with randomized labels or pixels. We first study the behavior of such memorizing networks on unseen images. We find that independently initialized networks trained on the same random labels learn different predictive functions: they make different predictions on test examples, in contrast with generalizing networks. We then examine the effect of dataset size on memorization through the required network capacity and training time to interpolate the training set. Counter-intuitively, we find that the number of presentations of a given example required for complete memorization can decrease with dataset size even when input-output pairs share no common structure. Although memorizing networks do not learn a universal solution, they exhibit interesting behaviors which call for further investigations into the underlying mechanisms.

0.40

Symmetry-Aware Feature Learning: A Polynomial Separation for Multi-Index Models

cs.LG math.PRstat.ML ·2026-10-06 ·Jivan Waber, Vanessa Piccolo, Yatin Dandi, Florent Krzakala
theory similarity 0.60
Abstract · 71 pages, 3 figures

We establish a polynomial sample complexity separation between symmetry-aware and symmetry-agnostic feature learning. We study growing-rank multi-index models with high-dimensional Gaussian covariates in $\mathbb{R}^d$ and $r=Θ(d^δ)$ teacher directions forming a cyclic symmetry orbit, where $0<δ<1/2$. We compare three ways of exploiting this structure: architectural weight sharing, data augmentation over the full symmetry group, and learning without access to the symmetry. In particular, we analyze a symmetry-tied convolutional network, an untied network, and the same untied network trained with full-group data augmentation, using spherical online SGD with correlation loss. For a class of polynomial links with information exponent $p\ge3$, we prove matching sample complexity bounds up to logarithmic factors: the tied and augmented learners achieve weak directional recovery in $\widetildeΘ(d^{p-1})$ samples, whereas the symmetry-agnostic learner requires $\widetildeΘ(rd^{p-1})$. For the pure quadratic Hermite link, the same separation holds for weak recovery of the teacher subspace, with sample complexities $\widetildeΘ(d)$ and $\widetildeΘ(rd)$, respectively. Thus, full-group data augmentation matches the sample efficiency of architectural weight sharing, and both provide a polynomial advantage over training without symmetry. For $p\ge3$, the proof reveals a two-stage mechanism: fluctuations at initialization select one direction in the teacher orbit, after which localized growth amplifies its overlap to the weak recovery scale while competing overlaps remain near their initialization scale.

0.56

Constructive Universal Approximation by Infinite-Dimensional Neural Networks via Gaussian-Weighted Ridgelet Transform

cs.LG math.FAstat.ML ·2026-10-16 ·Sho Sonoda, Luca Galimberti, Yuanchao Xu, Isao Ishikawa, Masahiro Ikeda
hot direction similarity 0.59
Abstract

Neural networks whose inputs are functions, as in operator learning, are usually shown to be universal by existence arguments, either by reduction to finite-dimensional networks or by Stone--Weierstrass-type density; these prove that approximants exist but say little about how the parameters depend on the target. We take a constructive route. We extend the ridgelet transform, an integral transform related to the Fourier, Radon, and wavelet transforms, to continuous maps on a separable infinite-dimensional Hilbert space, replacing the Lebesgue measure that is unavailable in infinite dimensions by Gaussian weights with a homogeneous mixture on the direction space. The resulting transform has a Plancherel identity and reconstruction formulas incorporating the frame operator, the correction induced by the weights, and it assigns to each target an explicit coefficient measure, one for every admissible analysis filter. From these representations we obtain uniform approximation on compact sets for all continuous non-polynomial activations of polynomial growth, including ReLU, and, by Monte Carlo sampling of the coefficient, finite-width networks with a dimension-free $O(N^{-1/2})$ error in the width $N$ for globally Lipschitz activations and coefficients with finite variation and second moments. Explicit examples include Gaussian targets and neural-operator layers. A companion Lean~4 formalization provides machine-checked proofs, with its correspondence to the manuscript documented at https://shosonoda.github.io/lean-operator-ridgelet/ .

0.39

Right In-Place (RiP) Convolution: A Simple, General, and Near-Optimal Strategy for Memory-Efficient CNN Inference

cs.LG cs.CV ·2026-09-30 ·Opegbemi Matthias Busoye, Tolulope Matthew Busoye, Eghonghon-aye Eigbe
published similarity 0.59
Abstract · Extended version of a paper accepted at the NeurIPS 2026 Workshop on Global South in AI

Activation memory, not compute, limits CNN inference on constrained hardware such as microcontrollers. Direct in-place convolution removes the dual-buffer cost, but the memory-optimal formulation of Gural and Murmann assumes valid padding, unit stride, unit dilation, and odd square kernels, and needs a non-sequential traversal costing $2\times$ inference time in transposes. We identify two regimes in which their published closed form does not hold: (1) an under-allocation of exactly $(k-1)C_{in} \bmod (C_{out}-C_{in})$ scalars, active on every convolutional layer of their own deployed network and manifesting as a silent corruption of still-live input; (2) an unbounded overestimate, up to $2{,}432\times$, once the critical leg leaves the output grid. We correct both and generalize to arbitrary stride, dilation, padding, and rectangular kernels. We then propose Right In-Place (RiP) convolution, a bit-identical operation in which every layer reads its input right-aligned in a shared workspace and writes its output left-aligned from index zero. The debt is piecewise affine in the output pixel index, so evaluating its breakpoints in $O(1)$ yields the minimum safe gap without enumerating the output grid, with row-major access preserved. Across $10{,}000$ random layers RiP produced no corruption, and across 84 convolutional layers from 25 architectures it matches the herringbone workspace exactly on 58 and within 5% on 81, using 24.8% less memory than dual buffering on average. Written into TinyEngine's kernels and deployed to a Raspberry Pi Pico 1 and Pico 2, it cuts peak activation memory across eleven MCUNet models by 12.5 to 33.3% at unchanged cycle counts and bit-identical outputs, raising the number of models that fit the Pico 1's 256 KB SRAM from six to nine.

0.33

Transferable Graph Metanetworks

cs.LG stat.ML ·2026-09-30 ·Yuxin Ma, Adir Dayan, Yam Eitan, Haggai Maron, Soledad Villar
theory similarity 0.59
Abstract

A weight space network (or metanetwork) takes the weights of another neural network as input and predicts properties of it. Most prior work trains such models on input networks of one or a few fixed sizes and evaluates them in-distribution. The few attempts at out-of-distribution size generalization remain limited in scope and have achieved only modest success. Consequently, the potential efficiency gains of training on small networks and evaluating on much larger ones remain largely unrealized. We propose Transferable Graph Metanetworks, which extend the graph metanetwork paradigm with a set of modifications that make performance transferable across input networks of different widths. The modifications follow two principles: invariance to the ways in which networks of different widths represent the same function, and continuity, such that weights representing similar functions receive similar predictions. We further study whether size generalization is possible for input networks trained independently from random initialization. Empirically, our modifications significantly improve size generalization on every task we consider. Performance is strongest on input networks trained under the maximal-update parameterization ($μ$P), where it remains robust up to $42\times$ the training width. Theoretically, we explain these observations with infinite-width limit theory: we prove size-generalization guarantees for our model on $μ$P-trained inputs, and explain why it can fail under other parameterizations.

0.31

Symmetry Fingerprinting with Geometric Learnable Invariants Transformers

cs.LG ·2026-11-15 ·Bart M. N. Smets, Gijs Bellaard, Pieter Wils
similarity 0.58
Abstract

Geometric deep learning has made available a large variety of structurally equivariant neural network architectures, meaning a particular transformation of their input causes a predictable transformation of their output. But structural equivariance is a very strong inductive bias that can limit performance if chosen poorly. In contrast, choosing an architecture with low geometric bias necessitates data augmentation to obtain correct behavior; extending the training process. We propose a novel neural network architecture that is soft equivariant; we select a set of symmetry groups and during training the network will become equivariant only to those symmetry groups that are appropriate given the training data. After training we can inspect the network to obtain a symmetry fingerprint that will tell us exactly which symmetries ended up being relevant and to what degree. We show how our architecture and the fingerprinting process work in the case of an image classification task.

0.09

Efficient Learning and Symmetry Discovery under Exact Invariances

cs.LG stat.ML ·2026-09-07 ·Ashkan Soleymani, Behrooz Tahmasebi, Patrick Jaillet, Stefanie Jegelka
top venuehighly cited similarity 0.58
Abstract · 29 pages. Published at COLT 2026

Learning with group invariances is central to many scientific and geometric learning problems, yet its computational foundations remain poorly understood. Even for classical supervised regression settings, it has been unclear whether one can efficiently compute a regression function that is exactly invariant to a given group action. Recent work showed that exact invariance can be enforced in polynomial time when the underlying group is finite and known, but left open the cases of infinite groups and unknown symmetries. In this paper, we resolve both challenges. First, we present the first polynomial-time algorithm for learning with exact group invariances that applies uniformly to finite and infinite groups. The runtime is polynomial in the data dimension and sample size, and independent of the group, while achieving strong generalization guarantees. This provides a computational explanation for the empirical success of invariant and equivariant methods in geometric machine learning and partially answers a recent open question in the literature. Second, we study learning in the symmetry discovery setting, where the invariance group is unknown. Focusing on the subgroup lattice of a finite group, we show that exact symmetries can be identified from data and exploited for learning in polynomial time. For regression over finite-dimensional feature spaces, our algorithm provably recovers the underlying symmetry, matches the minimax-optimal sample complexity of the known-symmetry setting, and runs in time polynomial in the data dimension and sample size. Our analysis relies on tools from random Cayley graphs and expander theory, which may be of independent interest.

0.78