Memorization Capacity of Invariant Convolutional Neural Nets

Introduction

The memorization capacity of a neural network architecture quantifies the number of parameters and neurons needed for the architecture to be able to interpolate any $N$ data points for any assignment of labels (for a suitable setting of the weights). The study of this capacity has a long history—dating back all the way to the 1960s—and its importance experienced a recent revival due to the double descent phenomenon [4]. According to the long-standing bias-variance trade-off [46, 20], the complexity of a machine learning model needs to balance underfitting and overfitting to achieve good generalization performance. It should be rich enough to express the underlying patterns in the data but still be simple enough to avoid picking up any spurious patterns. This classical viewpoint is at odds with modern practice in deep learning, where highly over-parameterized neural networks are trained to achieve a (nearly) perfect fit on the training data (see, e.g., Canziani et al., 2016; Zhang et al., 2017). In spite of this apparent overfitting, however, these models perform well on test data. This behavior is described by the double descent curve, where increasing the models complexity beyond the interpolation threshold—where the model is just complex enough to interpolate its training data—results in a second descent of the test error. This behavior is well documented for deep neural networks as well as a wide variety of other machine learning models, see, e.g., [4, 3, 39, 37, 21]. As was argued by Dirksen et al. [15], in practical applications the model size is tailored to a given data set. Memorization capacity, however, studies the reverse situation, requiring a model of fixed size to interpolate any dataset of $N$ samples. This results in bounds that necessarily grow with the number of samples. However, for a problem with a ‘nice’ structure, such as linearly separable classes in the simplest case, this should certainly not be necessary.

Present works on memorization capacity typically only consider fully-connected neural networks. However, these are only rarely used in practice and more specific architectures are preferred. A prominent example are convolutional neural networks for the processing of sequential or image data. Additionally, those models are frequently endowed with special problem-dependent properties such as translation-invariance, e.g., through data augmentation in the training process or the use of global pooling operations, see, e.g., [5, 6]. This leads to the question:

What is the memorization capacity of a translation-invariant neural architecture?

We recall that memorization capacity requires an architecture to be able to interpolate any $N$ samples for any assignment of labels. When two samples are the same up to translation, interpolating any label assignment simply becomes impossible. At the very least, one would need to identify these samples and assign them the same label. At the same time, instead of the total number of samples one should then consider only the number of unique samples up to translation, as any translated copies are correctly classified automatically.

In this paper, we remedy the above issues via an instance-specific approach which additionally respects the translation-invariant property of the model. Specifically, we build upon the prior work of Dirksen et al. [15] who derived an instance-specific result for fully-connected networks. Our main contributions are the following:

1. Memorization capacity of translation-invariant neural nets. In § 2, given a binary classification data set, we prove upper bounds on the required number of parameters and neurons for a translation-invariant convolutional neural network to be able to interpolate the data. The bounds are linked to a new complexity measure that respects both the translation-invariant property of the model, as well as the mutual arrangement of the two classes and their geometric properties.

2. Randomized interpolation algorithm for convolutional neural nets. Our proof is constructive: we introduce a randomized algorithm that, given a binary classification data set, with high probability, outputs a translation-invariant convolutional neural network which interpolates the data and has at most the asserted size. In numerical experiments, we investigate the effectiveness of our algorithm both in controlled experiments and on real image data, and compare its performance to previous work.

3. Beyond just translations. In Appendix A, we prove our results in a more general framework, which supports invariance with respect to a given, arbitrary finite group of orthogonal transformations. Apart from translations, this also includes, for example, reflections and rotations of image data, and invariances of higher order tensor data. We have chosen to present our results first in the special setting of translation-invariant neural nets to keep the exposition accessible.

We develop our results for networks with threshold activations, as this is a challenging setting in memorization theory. We expect that our results can be extended to other activations that zero out negative inputs and assign positive values to positive inputs, such as the ReLU.

Notation. We denote scalars $c, C \in\mathbb{R}$ with plain letters. We denote vectors $\boldsymbol{x} \in\mathbb{R}^{d}$ with bold lowercase letters, and their $i$-th entries by $x_i$ or $[\boldsymbol{x}]_i$. We denote matrices $\boldsymbol{A} \in\mathbb{R}^{m \times n}$ with bold uppercase letters, their $i$-th rows by $\boldsymbol{A}_i$ or $[\boldsymbol{A}]_i$, and their $(i,j)$-th entries by $A_{i,j}$ or $[A]_{i,j}$. $\mathbb{B}_2^d$ denotes the unit Euclidean ball in $\mathbb{R}^d$. For two disjoints sets $\mathcal{A}$ and $\mathcal{B}$ we denote their union by $\mathcal{A} \cup\mathcal{B}$. For $n \in\mathbb{N}$, denote $[n] := \{1,\ldots,n\}$. We write $A \gtrsim B$, or alternatively $B = O(A)$, if $C \cdot A \ge B$ for an absolute constant $C > 0$. When we do not only hide constants but logarithmic terms as well, we write $B = \widetilde{O}(A)$ instead. We denote the threshold activation and sign function by

respectively. For $\boldsymbol{a}, \boldsymbol{b} \in\mathbb{R}^{d}$, we define $\mathbf{1}[\boldsymbol{a} = \boldsymbol{b}] \in\{0,1\}^{d}$ element-wise by

Moreover, we define the global max pooling operation by $\operatorname{GMP}(\boldsymbol{x}) = \max_{i \in[d]} x_i$. We denote by $\boldsymbol{0}, \boldsymbol{1} \in\mathbb{R}^{d}$ the vectors with entries all equal to $0$ and $1$, respectively. We denote the standard multivariate normal distribution in $d$ dimensions by $\mathcal{N}(\boldsymbol{0}, I_d)$ and the uniform distribution on $\mathcal{A} \subset\mathbb{R}^{d}$ by $\operatorname{Unif}(\mathcal{A})$.

Related work

There is a rich literature on the memorization capacity of neural network architectures, especially for fully-connected architectures. If a model is able to interpolate any $N$ samples in $\mathbb{R}^{d}$ with any assignment of labels, we say that it can memorize $N$ samples. Memorization capacity quantifies how large a model needs to be in order to memorize $N$ samples.

Fully-connected networks. Earlier works on the memorization capacity of neural networks with threshold activations date back to the 1960s and studied shallow architectures, see, e.g., Cover [12]; Nilsson [41]; Minsky and Papert [38]; Baum [2]; Huang and Huang [24]. More recent results consider deeper networks. In particular, Vershynin [49] assumed samples on the unit sphere with at least a Euclidean distance of $\delta$ between them, and proved that a deep threshold (or ReLU) network can memorize $N$ samples with binary labels using $\widetilde{O}(e^{1/\delta^{2}}+\sqrt{N})$ neurons and $\widetilde{O}(e^{1/\delta^{2}}(d+\sqrt{N})+N)$ parameters. Later, Rajput et al. [44] removed the exponential dependence on $\delta$, showing that only $\widetilde{O}(1/\delta+\sqrt{N})$ neurons and $\widetilde{O}(d/\delta+N)$ parameters are sufficient while further only requiring bounded norm instead of unit norm. Interestingly, while the earlier results are deterministic constructions, Vershynin [49] and Rajput et al. [44] used a probabilistic approach. Recently, Dirksen et al. [15] presented an instance-specific approach to memorization capacity. For a given finite binary classification dataset, their bound on the required number of neurons and parameters depends not on the number of samples but is instead linked to the geometric properties of the data classes and their mutual arrangement. For benign data arrangements, their result can overcome the worst-case estimates of memorization capacity.

Among other activations, the ReLU stands out in particular due to its widespread use in practice. Some earlier works include the one of Bubeck et al. [7] who extended the result of Baum [2] to real-valued labels, and Zhang et al. [50] who used weight-sharing. More recently, Park et al. [42] used deep ReLU networks to achieve the first result with a sublinear number of parameters. Assuming that the points are separated, they showed that a ReLU (or hard-Tanh) network can memorize multi-class labels using a constant number of neurons, $\widetilde{O}(N^{2/3})$ layers and $\widetilde{O}(d+N^{2/3})$ parameters. Vardi et al. [47] improved the above dependence on $N$. For separated samples with bounded norm they showed that a ReLU network with a constant number of neurons, $\widetilde{O}(\sqrt{N})$ layers and $\widetilde{O}(d+\sqrt{N})$ parameters can memorize $N$ samples with multi-class labels. Lee et al. [33] derived bounds on the required size of an interpolating fully-connected ReLU network which they link to the polytope structure of a given data set and further connect to other manifold shapes.

For results with activations other than threshold or ReLU see, e.g., Huang and Babri [23]; Huang [22]; Park et al. [42]; Madden and Thrampoulidis [34]. The works we cite above make assumptions on the samples such as general position, separation, or bounded norm. For results for randomized samples or samples drawn from a random distribution, see, e.g., Ge et al. [17]; Daniely [13]; Zhang et al. [51].

Convolutional neural networks. Convolutional neural networks (LeCun et al. [29, 30]) are a cornerstone of modern machine learning. They have brought breakthroughs in the processing of images, video, speech, and audio (Goodfellow et al. [18]; LeCun et al. [32]) and have been a driving force for the resurgence of deep learning (Krizhevsky et al. [28]). However, in contrast to fully-connected networks, their memorization capacity does not yet seem to be very well studied.

A few empirical investigations have addressed this topic. Notably, Zhang et al. [50] observed that popular convolutional architectures can easily interpolate a random labeling of their training data. Arpit et al. [1] expanded on this observation and argued in particular that the network’s capacity depends on the considered data set. On an image data set with randomized labels, Sablabrolles et al. [45] gradually increased the number of training samples for convolutional networks of different sizes and observed at which point the training accuracy drops.

While the universality of convolutional neural networks (with max pooling) was shown by Cohen and Shashua [9], to our knowledge the only existing result on their memorization capacity is due to Nguyen and Hein [40]. They showed that a convolutional neural network can memorize $N$ samples with real-valued labels, assuming that the patches of the samples are distinct and that the convolutional layer before the fully-connected output layer has output dimension at least $N$. However, their results require an activation function which is at least continuous, unlike the threshold activation which we use here. Moreover, their network size depends on the number of samples, which is not the case in our result.

As a natural extension to convolutional neural networks, Cohen and Welling [10] introduced group equivariant neural networks (G-CNNs). They developed group convolutions which generalize standard convolutions to be equivariant under various group transformations, such as translations, rotations, and reflections. There is a growing body of work on G-CNNs, see, e.g., Cohen et al. [11] and the references therein. In Appendix § 7 we use group convolutional layers to prove our results in a generalized setting.

Other architectures. There is research on the memorization capacity of other architectures, such as residual networks [19], fully-connected and convolutional autoencoders [43], networks with conditional computation [26], and, more recently, transformer models [25, 36] (Madden et al. 2024).

Translation-invariant memorization algorithm

In this section, we present our results on translation-invariant convolutional neural networks. These follow from a more general framework where invariance under an arbitrary group of orthogonal transformations can be captured, including reflections and rotations of image data. We refer to Appendix § 7 for the technical details. For simplicity, we focus on the binary classification setting. Our method is extendable to multiple classes via a one-vs-many approach, see Appendix § 8 for this straightforward extension.

In the following, let \mathcal{X} = \mathcal{X}^{+} \mathbin{\mathaccent\cdot\cup} \mathcal{X}^{-} \subset\mathbb{R}^{L \times H \times W} denote a given finite data set, where $\mathcal{X}^{+}$ and $\mathcal{X}^{-}$ are disjoint sets containing the samples with label $+1$ and $-1$, respectively. We assume that these are images which are $H$ pixels high, $W$ pixels wide, and have $L$ color channels. Our goal is the construction of a translation-invariant convolutional neural network which interpolates this data set.

To state this goal formally, denote by $T_{h,w}$ the circular translation in pixel-space by $h$ pixels vertically and $w$ pixels horizontally, see the examples in Figure 1 for an illustration. Formally, for a single color channel $z \in\mathbb{R}^{H \times W}$,

and we can use the lifting

to translate all color channels at once.

In their instance-specific result on memorization capacity for fully-connected threshold neural networks, Dirksen et al. [15] utilize a mutual covering of Euclidean balls to quantify the difficulty of interpolating a given data set. When a model is translation-invariant it identifies any sample and its translated copies to one another. Hence, as a natural extension of the Euclidean distance to our setting, we define the pseudo-distance

It is easy to see that this pseudo-distance is translation-invariant and has the property that $d(x,y)=0$ if and only if $x$ and $y$ are translates of each other. For sets $A,B\subset\mathbb{R}^{L\times H\times W}$ and $a\in\mathbb{R}^{L\times H\times W}$, we define

Employing this pseudo-distance we define the following translation-invariant adaptation of the notion of mutual covering from Dirksen et al. [15].

Figure 1 illustrates the prototypical shape of a translation-invariant mutual covering. The condition (2) on the radii in Theorem 3 below allows the components to grow as far as the ideal decision boundary between the data classes—up to a logarithmic factor. Consequently, parts of the data far away from the decision boundary can be covered with only a few larger components while smaller components are only required in more complex areas close to the decision boundary. This data-adaptive behavior is similar to the covering of Dirksen et al. (2024). However, in contrast to their approach, our adapted distance measure allows every component to break up into multiple sub-components, each contained inside an Euclidean ball around a translated copy of the components center. In this way, one component not only groups together samples that have close proximity to one another but also those samples that are in close proximity up to translation.

We now state the version of our theoretical result for translation-invariant convolutional neural networks, followed by a short proof sketch. The result for more general group invariances is proved later, in Appendix § 7.§ 3. Below, we denote the Gaussian width, for $\mathcal{T}\subset\mathbb{R}^{d}$, by

where $g\sim\mathcal{N}(0,I_{d})$ denotes a standard Gaussian random vector. We refer to Vershynin (2018, Section 7.5) for a detailed discussion and examples.

for $k \in[M^{+}]$ and $\ell\in[M^{-}]$. Set $\omega:= \max\{\omega^{+},\omega^{-}\}$ where

Suppose $\lambda\gtrsim R_{\mathrm{rad}}$ and

Then, with probability at least $1-\eta$, Algorithm 1 outputs a translation-invariant convolutional neural network $F : \mathbb{R}^{L \times H \times W} \to\{\pm1\}$ which interpolates $\mathcal{X}$, that is, for at least a fraction of $\alpha$ samples $x^{+} \in\mathcal{X}^{+}$ and all samples $x^{-} \in\mathcal{X}^{-}$,

Moreover, it uses $K$ filters in its first convolutional layer and no more than $M^{+}$ filters in its second convolutional layer. In particular, it has no more than $O((L+M^{+})HWK)$ parameters.

Proof [Proof sketch] As the predictions of the model outside $\mathcal{X}$ are not important for the interpolation task, we only explicitly encode $\mathcal{X}^{+}$ with label $+1$ into the network and the complement is assigned label $-1$. This explains the asymmetry between the two classes in the result. In more detail, the algorithm proceeds as follows.

In the first loop of the algorithm (lines 1 to 4), we sample a random convolution layer $\Phi$. Under our assumptions, we may condition on the high probability event of Lemma 13—the key ingredient of the proof—under which the following holds. After transforming the data set with $\Phi$, for any sample $x^{+}_{*} \in\mathcal{X}^{+}$, the neuron $\hat{\varphi}_{x^{+}_{*}}$ defined in line 11 (followed by a global max pooling operation) activates on the whole component of the mutual covering of $\mathcal{X}^{+}$ that this sample resides in. On the other hand, it does not activate on any sample from $\mathcal{X}^{-}$. Crucially, this holds for any sample within any of the components, which allows us to simply select candidate samples at random (line 8). Hence, in the second loop (lines 5 to 17) we select a random candidate sample $x^{+}_{*} \in C^{+}$ and, after computing the activation region $\mathcal{V}_{x^{+}_{*}}$ of the neuron $\hat{\varphi}_{x^{+}_{*}}$, we remove the entire activation region from $C^{+}$. This eliminates at least one component of this mutual covering. Thus, in the next step, a candidate sample outside the just eliminated component is picked at random, eliminating another component by the same principle. By induction, the loop terminates after at most $M^{+}$ steps, producing a second convolutional layer with at most $M^{+}$ filters. At this point the network already fully interpolates $\mathcal{X}$. To see this, notice that the activation regions $\mathcal{V}_{x^{+}_{*}}$ of the second layer neurons (together with the global max pooling operation) cover $\mathcal{X}^{+}$. The last linear layer simply sums over the output of the global max pooling layer and outputs $+1$ if the input of the network is in any of the activation regions, and $-1$ otherwise. At this point we can already count the number of parameters.

The third loop (lines 18 to 22) uses a heuristic rule to successively prune the neurons in the second layer which contribute the least to the interpolation of $\mathcal{X}^{+}$. It stops exactly when pruning the next neuron would lead to interpolating less than a fraction of $\alpha$ samples. Notice that $\alpha$ is not reflected in the bound on the size of the network. Nevertheless, we observe its beneficial effects in the experiments, where it reduces the size of the network.

Algorithm 1 translation-invariant memorization

Input: $\mathcal{X}=\mathcal{X}^{+}\cup\mathcal{X}^{-}\subset\mathbb{R}^{L\times H\times W}$ finite with $N^{+}:=|\mathcal{X}^{+}|$ and $N^{-}:=|\mathcal{X}^{-}|$, number of random filters $K\in\mathbb{N}$, maximal bias $\lambda\geq0$, interpolation fraction $\alpha\in(0,1]$

Output: translation-invariant convolutional neural net $F:\mathbb{R}^{L\times H\times W}\to\{\pm1\}$

1. for $k\in[K]$ do

2. $\boldsymbol{g}_{k}\leftarrow$ independent sample from $\mathcal{N}(\boldsymbol{0},I_{L\times H\times W})$

3. $\tau_{k}\leftarrow$ independent sample from $\operatorname{Unif}([-\lambda,\lambda])$

4. end for \hspace{1em}$\triangleright\ \Phi(x)=\left[\sigma\left(\sum_{\ell\in[L]}x_{\ell}\ast[g_{k}]_{\ell}+\tau_{k}\right)\right]_{k\in[K]}$

5. $\mathcal{A}^{+}\leftarrow\varnothing$

6. $\mathcal{C}^{+}\leftarrow\mathcal{X}^{+}$

7. while $|\mathcal{C}^{+}|>0$ do

8. $x_{*}^{+}\leftarrow$ random sample from $\mathcal{C}^{+}$

9. $\mathcal{C}^{+}\leftarrow\mathcal{C}^{+}\setminus\{x_{*}^{+}\}$

10. $u_{x_{*}^{+}}\leftarrow\mathbf{1}[\Phi(x_{*}^{+})=0]$

11. $m_{x_{*}^{+}}\leftarrow\min_{x^{-}\in\mathcal{X}^{-}}\langle\langle\Phi(x^{-}),u_{x_{*}^{+}}\rangle\rangle$ \hspace{1em}$\triangleright\ \hat{\varphi}_{x_{*}^{+}}(z)=\sigma\left(\sum_{k\in[K]}z_{k}\ast[-u_{x_{*}^{+}}]_{k}+m_{x_{*}^{+}}\right)$

12. $\mathcal{V}_{x_{*}^{+}}^{+}\leftarrow\left\{x^{+}\in\mathcal{X}^{+}:\operatorname{GMP}\left(\hat{\varphi}_{x_{*}^{+}}(\Phi(x^{+}))\right)>0\right\}$

13. if $|\mathcal{V}_{x_{*}^{+}}^{+}|>0$ then

14. $\mathcal{A}^{+}\leftarrow\mathcal{A}^{+}\cup\{x_{*}^{+}\}$

15. $\mathcal{C}^{+}\leftarrow\mathcal{C}^{+}\setminus\mathcal{V}_{x_{*}^{+}}^{+}$

16. end if

17. end while

18. while $\left|\bigcup_{x_{*}^{+}\in\mathcal{A}^{+}}\mathcal{V}_{x_{*}^{+}}^{+}\right|\geq\alpha N^{+}$ do

19. $x_{*}^{+}\leftarrow\arg\min_{x_{*}^{+}\in\mathcal{A}^{+}}\left|\mathcal{V}_{x_{*}^{+}}^{+}\setminus\bigcup_{x_{*}^{+}\in\mathcal{A}^{+}\setminus\{x_{*}^{+}\}}\mathcal{V}_{x_{*}^{+}}^{+}\right|$

20. $\mathcal{A}^{+}\leftarrow\mathcal{A}^{+}\setminus\{x_{*}^{+}\}$

21. end while

22. $\mathcal{A}^{+}\leftarrow\mathcal{A}^{+}\cup\{x_{*}^{+}\}$ \hspace{1em}$\triangleright\ \hat{\Phi}(z)=\left[\sigma\left(\sum_{k\in[K]}z_{k}\ast[-u_{x_{*}^{+}}]_{k}+m_{x_{*}^{+}}\right)\right]_{x_{*}^{+}\in\mathcal{A}^{+}}$

23. return $F(x)=\operatorname{sign}\left(\langle\mathbf{1},(\operatorname{GMP}^{\uparrow}\circ\hat{\Phi}\circ\Phi)(x)\rangle\right)$ \hspace{1em}$\triangleright\ \mathbf{1}=(1,\ldots,1)\in\mathbb{R}^{\mathcal{A}^{+}}$

The translation invariance is built into the architecture. The convolutional layers are translation-equivariant. Hence, when inputting a translated sample into the network, these layers simply pass on the translation. The global max pooling layer, on the other hand, is translation-invariant. Thus, any translation that was passed through the network until this point has no effect after this layer.

Experimental results

In this section, we present a series of experiments² in which we evaluate the performance of our algorithm and compare it to the previous work of Dirksen et al. [15]. In the previous section, we presented our translation-invariant construction. To model translation-invariance with a stride greater than one or other groups of transformations altogether we use our generalized Algorithm 3 which we introduce in full detail in Appendix § 7. For multi-class problems, we employ an extension which is similar to common one-vs-rest methods, see Appendix § 8. To reproduce the fully-connected construction of Dirksen et al. [15], we employ the generalized algorithm and simply choose the trivial group. In the following, the ‘fully-connected network’ refers to this construction and the ‘convolutional network’ refers to our invariant construction.

In § 3.1, we begin with a two-dimensional example. This provides some visual intuition on the structure of the networks that our method produces. In § 3.2, we evaluate the performance of our algorithm on both MNIST (LeCun et al., [31]) and CIFAR-10 (Krizhevsky et al., [27]). In § 3.3, this is followed up by examining the influence of the interpolation fraction hyperparameter $\alpha$. This yields some understanding of how well-conditioned MNIST and CIFAR-10 are with respect to our method. Up until this point, any invariance in the data originated from the distributions. § 3.4 features a more controlled setting, where we augment the data sets to be perfectly invariant by including all possible transformations of the samples.

Illustrative two-dimensional example

In order to gain some geometric intuition, let us briefly step away from the high-dimensional image setting in favor of a two-dimensional toy example. In such a setting, we can easily visualize the activation regions of the individual neurons just before the last linear layer. This offers a detailed look at the decision boundary of the network, as the union of these regions is exactly the region where the network outputs a positive label.

Figure 2 shows an instance of the XOR data set. Evidently, a classifier for this problem can benefit from a built-in invariance with respect to $180^\circ$ rotations around the origin. In Appendix § 7, we model a general invariance with respect to a finite group of orthogonal transformations. In Figure 2a, we choose $\mathcal{G} = \{I_2, -I_2\}$ which represents the aforementioned rotational invariance. We see that the algorithm produces neurons with activation regions consisting of two parts which, together, reflect that invariance. We can compare this behavior to the fully-connected construction of Dirksen et al. [15], which we recover via the trivial group $G = \{I_2\}$, in Figure 2b. As this does not model the invariance of the problem, their method has to cover both quadrants of the positive class individually.

Performance on real-world image data

In this section, we evaluate and compare the performance of our algorithm on the MNIST and CIFAR-10 data sets. Inspired by the experiments of Dirksen et al. [15], we pick the maximal bias $\lambda= 0$ as this choice provided the best results in their experiments, among $\lambda\in[0, 3/2]$. For $K$, we first choose values $K_{\mathrm{ConvNet}}$ for the convolutional network in a large enough range such that the number of filters in the second layer converges. In a convolutional layer, depending on the data dimension and the stride of the convolution, each filter is shifted to $\hat{d}$ different positions. To produce a comparable result in which the first layers of both networks have the same output dimension, for the fully-connected network we choose $K_{\mathrm{FC}} = K_{\mathrm{ConvNet}} \cdot\hat{d}$.

A stride larger than one for the random convolution layer is modeled using our generalized theory from Appendix § 7. This slightly weakens the translation-invariant property of the network. For example, for a stride of two, the network is only invariant to translations of two pixels at a time. However, there are benefits to this, e.g., the required number of parameters is lower, as we discuss below.

MNIST. In this experiment, we pick a stride of one for the random convolution layer. On the left of Figure 3, we see that for the convolutional network increasing the number of filters $K_{\mathrm{ConvNet}}$ in the random convolutional layer decreases the number of filters for the second layer, until there are diminishing returns at around $K_{\mathrm{ConvNet}} = 60$. The fully-connected network behaves similarly, as shown on the right side of the same figure, where increasing the number of neurons $K_{\mathrm{FC}}$ in the random fully-connected layer decreases the number of neurons in the second layer with diminishing returns somewhere around $K_{\mathrm{FC}} = 30\,000$. Recall that for large $K$ the number of filters and neurons in the second layer, respectively, roughly corresponds to the mutual covering number. Therefore, the results indicate that the translation-invariant mutual covering has less components than its non-invariant counterpart, which means it captures the structure of the data set more concisely. Moreover, the convolutional network converges more efficiently, as both networks (due to weight sharing in the convolutional net) require $K \cdot d$ parameters in their first layers, where $d = 28 \cdot28$ is the dimension of MNIST.

In Figure 4, to reduce the number of total parameters, we see that for both networks it is beneficial to choose $K$ as small as possible (under the condition that the method still interpolates). From the algorithms we can deduce that the fully-connected network requires $K_{\mathrm{FC}}+1$ parameters per neuron (including the bias) in the second layer while the convolutional network requires $K_{\mathrm{ConvNet}} \cdot d + 1$ parameters per filter in the second layer. Thus, in order for the convolutional network to require a lower total number of parameters, the lower possible value of $K_{\mathrm{ConvNet}}$ and the corresponding lower number of filters in the second layer would need to undercut the influence of the factor $d$. However, as we can infer from the figures, this is not the case.

Finally, in all figures we can observe the influence of the interpolation fraction $\alpha$. We see that reducing $\alpha$ to 95% cuts the sizes of the second layers roughly in half. We discuss this further in § 3.3.

CIFAR-10. In this experiment, we pick a stride of two for the random convolution layer. In Figure 5 we again observe that an increase in $K$ leads to a decrease in the number of filters and neurons in the second layer, respectively. There are diminishing returns in both cases, around $K_{\mathrm{ConvNet}} = 250$ and $K_{\mathrm{FC}} = 40\,000$. As in the case of MNIST, both networks require $K \cdot d$ parameters in the first layer, where $d = 3 \cdot32 \cdot32$ is the dimension of CIFAR-10. Again, the second layer of the convolutional network converges more efficiently in this sense. However, the convolutional network requires slightly more second layer filters than the fully-connected network requires neurons in its second layer. Recall again that these roughly correspond to the mutual covering numbers. As we can see in Definition 2, while the components for the convolutional network consist of a union of multiple sub-components, their individual radii can become smaller compared to the fully-connected counterpart. This interplay might have a non-trivial effect on the covering number and we suspect that exactly this can be observed here.

Due to the stride of two we only have $\hat{d} = 16 \cdot16$. However, as in the case of MNIST, we still observe more parameters for the convolutional network in Figure 6.

Again, we can see that reducing $\alpha$ reduces the sizes of the second layers, but the effect is not as pronounced as for MNIST. We analyze this further in § 3.3 below.

Estimating how well a data set is conditioned

The idea behind the mutual covering is that it can adapt to the structure of a given problem by covering many samples far away from the decision boundary with only a few large components, while requiring smaller components only in more challenging areas to cover the remaining samples. One could say that such a mutual covering is ‘good’ while, e.g., a trivial covering where every sample is covered by its own dedicated component is certainly ‘bad’. In the same way, we might think of a data set as well-conditioned for our interpolation algorithm if it has a ‘good’ covering and as ill-condition if it only has ‘bad’ coverings.

Recall once again that, for large values of $K$, the number of filters in the second layer of the convolutional network and the number of neurons in the second layer of the fully-connected network roughly correspond to the respective covering number. Hence, observing how many filters or neurons are needed by our algorithm to interpolate a fraction $\alpha$ of samples can give an empirical hint of the size of the components and thus on how well-conditioned a data set is. In the most ill-conditioned case, our method will require one filter (respectively neuron) per sample, corresponding to a linear increase in terms of $\alpha$.

Let us observe beforehand, in Figure 7, that both the convolutional network and the fully-connected network behave very similarly regarding the interpolation fraction $\alpha$. A likely explanation is that both MNIST and CIFAR-10 have been preprocessed such that its subjects are centered, hence there are no samples that are translated away from the origin. In this case, we cannot expect the convolutional network to be more efficient at interpolating these samples than the fully-connected network. Note, however, that the convolutional network is still more expressive as it extrapolates to any unseen translates of samples in the data set via the built-in translation-invariance.

In Figure 7a, for MNIST we see a gradual increase in the required number of filters up until around $\alpha= 90\%$ at which point the behavior becomes trivial, where the incline matches that of a network which represents only one sample per neuron. On the other hand, in Figure 7b, for CIFAR-10 the trivial behavior already starts at around $\alpha= 40\%$, hinting that CIFAR-10 is less well-conditioned than MNIST and harder to interpolate for our method.

Invariant data sets

In the previous subsections we observed that that the non-invariant covering number and our translation-invariant covering number (approximated by the number of neurons and filters in the second layer of the respective network) behave very similarly. We conjectured that this might be due to missing translation-invariance in the data sets due to preprocessing of the images.

What happens if there is enough invariance in the data set? Let $\mathcal{G}$ be a finite group of orthogonal transformations, such as image-space translations in the case of MNIST and CIFAR-10 or rotations in the case of XOR. Each of the components of the $\mathcal{G}$-invariant covering possess $|\mathcal{G}|$ sub-components. If the data is invariant, these cover transformed copies of the same samples, all of which the non-invariant covering needs to cover, too. Hence, one might hope that the invariant covering number is by a factor $|\mathcal{G}|$ smaller than its non-invariant counterpart. However, due to the adaptive nature of the component radii, this is not obvious and could be dataset-dependent.

To test this intuition, for a given data set $\mathcal{X}$, we compare both methods on

which contains all possible transformations of the original samples. Note that for our method with built-in invariance simply using $\mathcal{X}$ is equivalent.

The results in Table 1 show that our initial intuition seems largely correct. The ratio of the average number of neurons in the second layer of the fully-connected network $\overline{M}_{\mathrm{FC}}$ and the average number of filters in the second layer of the convolutional network $\overline{M}_{\mathrm{ConvNet}}$ tracks $|\mathcal{G}|$ closely over all tested data sets. Additionally, in the last row, we consider the plain XOR data set. Here, the invariance is already naturally encoded in the data distribution. We execute both methods on the unaugmented data set $\mathcal{X}$ while still encoding $\mathcal{G}$ into the convolutional model. We notice a clear improvement over the non-invariant covering, but it is not as large as when considering the ‘perfectly invariant’ data set $\mathcal{X}_{\mathcal{G}}$. This makes sense, as the invariance is in the distribution only and hence ‘noisy’.

data set	$\mathcal{G}$	$|\mathcal{G}|$	$\overline{M}_{\mathrm{FC}}/\overline{M}_{\mathrm{ConvNet}}$
XOR	$\{I_{2},-I_{2}\}$	2	2.07
MNIST	$\{T^{\dagger}_{0,0},T^{\dagger}_{0,7},T^{\dagger}_{0,14},T^{\dagger}_{0,21}\}$	4	3.98
CIFAR-10	$\{T^{\dagger}_{0,0},T^{\dagger}_{0,8},T^{\dagger}_{0,16},T^{\dagger}_{0,24}\}$	4	3.92
XOR*	$\{I_{2},-I_{2}\}$	2	1.61

Conclusion

In this paper, we presented an instance-specific analysis of the memorization capacity of translation-invariant convolutional neural networks with threshold activations. For a data set of two classes, we derived bounds on the required number of neurons and parameters for such a network to be able to interpolate the data. These bounds are linked to a new notion of translation-invariant mutual covering which respects the translation-invariant property of the network and takes both the mutual arrangement of the two classes and their geometric properties into account.

We derived these results as a special case of a general framework, where we considered invariance with respect to an arbitrary finite group of orthogonal transformations. This includes multi-dimensional convolutions, reflections, and rotations. We gave a constructive proof by introducing a randomized algorithm which for given input data computes instances of such networks, with high probability. We conducted numerical experiments where we investigate the empirical performance of our algorithm and compare it to previous work. While the produced networks were not smaller than previous non-translation invariant networks they are more expressive due to their built-in invariance.

Use of AI tools

The authors used AI solely to improve the wording and grammar of self-written prose. AI was not used for any other purpose, including research, proofs and other mathematics, figures, or code. A preliminary version of the results was announced in the PhD thesis of the second-named author [16].

Acknowledgments and Disclosure of Funding

PG is grateful for the hospitality of Utrecht University, where he worked on this project as a guest researcher. PG acknowledges support by the German Science Foundation (DFG) in the context of the Emmy Noether junior research group VO 2594/1–1.

Generalized theory

In this section, we introduce our theoretical result in its full generality. To this end, we use a form of group equivariant convolution which was first introduced by Cohen and Welling [10], although with a different notation. We reprove all the properties of this generalized convolution that are needed for our analysis.

In what follows, $\mathcal{G} \le\mathcal{O}(d)$ denotes a finite subgroup of the orthogonal group. We aim to produce a model $F : \mathbb{R}^{d} \to\{\pm1\}$ that is invariant under the transformations contained in $\mathcal{G}$, that is, for all $x \in\mathbb{R}^{d}$,

In the main part, we consider the special case of a translation-invariant convolutional neural network which is applied to 2D images with $L$ color channels, each of size $H \times W$. This corresponds to the choice

where, as in the main part, $T_{h,w}$ denotes the circular translation in pixel-space by $h$ pixels vertically and $w$ pixel horizontally, and the translation is applied for each color channel via the lifting $T^{\uparrow}_{h,w}$, defined in (1). Clearly, these transformations are orthogonal as they are permutations, that is, a reordering of the elements of a vector. The same holds true for horizontal and vertical flips, 90° rotations for square 2D images or translations in higher dimensions. Over the course of this section, we highlight the special case of $\mathcal{G}_{\mathrm{T}}$. The result from the main part follows from this discussion.

Notation

We introduce an extended vector notation, which is similar to the notation used for tensors or multidimensional arrays. In the following, let $\mathcal{I}$, $\mathcal{J}$, and $\mathcal{K}$ denote finite index sets.

We denote by $\mathbb{R}^{\mathcal{I}}$ the space of vectors with entries in $\mathbb{R}$ that are indexed by the elements of $\mathcal{I}$. Evidently, this space is isomorphic to $\mathbb{R}^{|\mathcal{I}|}$. Let $x,y \in\mathbb{R}^{\mathcal{I}}$. We denote by $x_i$ the $i$-th entry of the vector $x$. We denote the $\ell_p$-norm, for $1 \le p < \infty$, and the Euclidean inner product by

respectively. In case of a double index, for $v \in\mathbb{R}^{\mathcal{I} \times\mathcal{J}}$, we select subsets of entries via

where we fixed the first and second index, respectively. For $f : \mathbb{R}^{\mathcal{J}} \to\mathbb{R}^{\mathcal{K}}$ we define the lifting

as the repeated application of $f$ over the first index. The set of indices $\mathcal{I}$ over which we lift will in each case be clear from the context. Moreover, we slightly abuse the above notation by identifying $n \in\mathbb{N}$ with $[n] = \{1,\ldots,n\}$. Hence, we might write $\mathbb{R}^{n \times\mathcal{I}} := \mathbb{R}^{[n] \times\mathcal{I}}$ for the space of vectors indexed by the elements of $[n] \times\mathcal{I}$.

A double index will be helpful when working with convolution layers where we want to group entries that have been manipulated by the same filter. In general we do not need more than two indices, for example, any color channel of a 2D image with $H \times W$ pixels can be simply identified with a vector of dimension $d = H \cdot W$.

Let us conclude with a short example of the above notation. Let $K \in\mathbb{N}$ and $f : \mathbb{R}^{G} \to\mathbb{R}^{G}$. For $v,u \in\mathbb{R}^{K \times G}$, we may write

where we first make the summation over $k \in[K]$ explicit and then resolve the lifting.

Generalized memorization algorithm

In this section, we introduce Algorithm 2, which—with high probability—produces a model that interpolates a given data set while being invariant under the transformations contained in $\mathcal{G}$. We make some necessary definitions to state Algorithm 2 and, along the way, we highlight how Algorithm 2 reduces to Algorithm 1 in the special case of $\mathcal{G}_{T}$.

First, we generalize the notion of circular convolution.

In the case of $\mathcal{G}_{T}$ the above corresponds to the regular 2D multi-channel circular convolution.⁴ To see this, we identify $(h,w) \in[H] \times[W]$ with $T_{h,w}^{\mathsf{T}} \in\mathcal{G}_{T}$, so that $\mathbb{R}^{H \times W} \simeq\mathbb{R}^{\mathcal{G}_{T}}$. Then, for $x,g \in\mathbb{R}^{L \times H \times W}$ and each entry $(h,w) \in[H] \times[W]$,

Hence, we have $[x \circledast g] = \sum_{\ell\in[L]} x_{\ell} \ast g_{\ell}$, which shows that the computation of the first layer in Algorithms 1 and 2 is identical.

Throughout we will use the elementary properties

for all $R,U \in\mathcal{G}$ and $v \in\mathbb{R}^{\mathcal{G}}$. These properties clearly transfer to the lifting $\widehat{S}_R$.

The last piece of notation needed to state Algorithm 2 is the following. For $\boldsymbol{v},\boldsymbol{u} \in\mathbb{R}^{K\times\mathcal{G}}$, we define the kernel

Let us conclude by showing how, in the case of $\mathcal{G}_{T}$, the computation of the second layer in Algorithm 1 and 2 is identical. With the same identification as before, for each entry $(h',w')\in[H]\times[W]$ and $\boldsymbol{v}\in\mathbb{R}^{\mathcal{G}}$,

Hence, we have $\widehat{S}_{T_{h,w}}^{\mathsf{T}}\mathrel{:=}T_{h,w}$. Moreover, for $\boldsymbol{z},\boldsymbol{u}\in\mathbb{R}^{K\times\mathcal{G}_{T}}$,

which further yields

Hence, the neurons computed in Algorithm 2 are

Finally, notice that in the formulation of Algorithm 1 we detached GMP from the second layer in favor of a separate global max pooling layer.

Proof of the main result

To state the generalization of Theorem 3, for $\boldsymbol{x},\boldsymbol{y}\in\mathbb{R}^{d}$, we define the pseudo-metric

Again, we extend this notation as in the main part: for sets $\mathcal{A},\mathcal{B}\subset\mathbb{R}^{d}$ and $\boldsymbol{a}\in\mathbb{R}^{d}$, we write

The following definition generalizes the translation-invariant mutual covering from the main part to instead be invariant to the transformations contained in $\mathcal{G}$. Notice that the case of $\mathcal{G}_{T}$ recovers Definition 2.

Algorithm 2 $G$-invariant memorization

Input: $G \leq O(d)$ finite, $\mathcal{X} = \mathcal{X}^{+} \cup\mathcal{X}^{-} \subset\mathbb{R}^{d}$ finite with $N^{+} := |\mathcal{X}^{+}|$ and $N^{-} := |\mathcal{X}^{-}|$, number of random filters $K \in\mathbb{N}$, maximal bias $\lambda\geq0$, interpolation fraction $\alpha\in(0,1]$

Output: $G$-invariant (generalized) convolutional neural net $F:\mathbb{R}^{d} \to\{\pm1\}$

1. for $k \in[K]$ do

2. $g_k \leftarrow$ independent sample from $\mathcal{N}(0,I_d)$

3. $\tau_k \leftarrow$ independent sample from $\operatorname{Unif}([-\lambda,\lambda])$

4. end for $\triangleright\Phi(x) = [\sigma(x \circledast g_k + \tau_k)]_{k\in[K]}$

5. $\mathcal{A}^{+} \leftarrow\varnothing$

6. $\mathcal{C}^{+} \leftarrow\mathcal{X}^{+}$

7. while $|\mathcal{C}^{+}| > 0$ do

8. $x_{*}^{+} \leftarrow$ random sample from $\mathcal{C}^{+}$

9. $\mathcal{C}^{+} \leftarrow\mathcal{C}^{+} \setminus\{x_{*}^{+}\}$

10. $u_{x_{*}^{+}} \leftarrow\mathbf{1}[\Phi(x_{*}^{+}) = 0]$

11. $m_{x_{*}^{+}} \leftarrow\min_{x^{-}\in\mathcal{X}^{-}} \langle\langle\Phi(x^{-}),u_{x_{*}^{+}}\rangle\rangle\triangleright\widehat{\varphi}_{x_{*}^{+}}(z) = \sigma(m_{x_{*}^{+}} - \langle\langle z,u_{x_{*}^{+}}\rangle\rangle)$

12. $\mathcal{V}_{x_{*}^{+}} \leftarrow\{x^{+}\in\mathcal{X}^{+}:\widehat{\varphi}_{x_{*}^{+}}(\Phi(x^{+})) > 0\}$

13. if $|\mathcal{V}_{x_{*}^{+}}| > 0$ then

14. $\mathcal{A}^{+} \leftarrow\mathcal{A}^{+} \cup\{x_{*}^{+}\}$

15. $\mathcal{C}^{+} \leftarrow\mathcal{C}^{+} \setminus\mathcal{V}_{x_{*}^{+}}$

16. end if

17. end while

18. while $\left|\bigcup_{x_{*}^{+}\in\mathcal{A}^{+}}\mathcal{V}_{x_{*}^{+}}\right| \geq\alpha N^{+}$ do

19. $x_{*}^{+} \leftarrow\arg\min_{x_{*}^{+}\in\mathcal{A}^{+}} \left|\mathcal{V}_{x_{*}^{+}} \cup\bigcup_{\widetilde{x}_{*}^{+}\in\mathcal{A}^{+}\setminus\{x_{*}^{+}\}}\mathcal{V}_{\widetilde{x}_{*}^{+}}\right|$

20. $\mathcal{A}^{+} \leftarrow\mathcal{A}^{+} \setminus\{x_{*}^{+}\}$

21. end while

22. $\mathcal{A}^{+} \leftarrow\mathcal{A}^{+} \cup\{x_{*}^{+}\} \triangleright\widehat{\Phi}(z) = [\sigma(m_{x_{*}^{+}} - \langle\langle z,u_{x_{*}^{+}}\rangle\rangle)]_{x_{*}^{+}\in\mathcal{A}^{+}}$

23. return $F(x) = \operatorname{sign}(\langle\mathbf{1},\widehat{\Phi}(\Phi(x))\rangle) \triangleright\mathbf{1} = (1,\ldots,1) \in\mathbb{R}^{\mathcal{A}^{+}}$

The following is the generalization of Theorem 3. It states conditions under which Algorithm 2 succeeds to produce an invariant network that interpolates the input data with high probability and, moreover, gives estimates on the size of this network.

In the remainder of this section, we prove Theorem 7. First, we make some simple but helpful observations. Then, we prove lower and upper bounds on quantities of interest in Lemma 10 and 12, respectively. We connect these bounds in Lemma 13 which serves as the key ingredient of our proof of Theorem 7, stated at the very end of this section.

Let us formally define the first layer, which is constructed within the first loop of Algorithm 2. For the number of filters $K \in\mathbb{N}$ and the maximal bias $\lambda\ge0$, let

be all independent of each other. We define the random convolution layer by

where the addition of the biases $\tau_k$ is element-wise.

The proofs of Lemmas 10 and 12 below relate our more general setting to a setting with a fully-connected first layer. We define the random fully-connected layer $\Psi$ associated to $\Phi$ by

where $G$ has rows $\boldsymbol{g}_1,\ldots,\boldsymbol{g}_K$ and $\boldsymbol{\tau}=(\tau_1,\ldots,\tau_K)$.

The following lemma states two helpful observations which we use throughout the following proofs. The first is that transforming an input of the convolution layer is the same as shifting its output. The second is that only observing the output of the convolution layer for a fixed transformation is the same as applying the associated fully-connected layer to an appropriately transformed input.

Proof For $R \in\mathcal{G}$ and $\boldsymbol{x},\boldsymbol{g}\in\mathbb{R}^d$, we observe

Indeed, for $Q \in\mathcal{G}$,

Let $k \in[K]$. Using the above and due to the element-wise application of $\tau_k$ and $\sigma$,

which proves the first statement. For the second statement, note that

■

In the case of the random fully-connected layer, Dirksen et al. [15] prove the following. To state the result, for $\mathcal{A},\mathcal{B}\subset\mathbb{R}^d$, we denote

We generalize the above result to the random convolution layer.

Proof Let $E\in\mathcal{G}$ denote the identity element. Then, for all $x^{+}\in\mathcal{X}^{+}$, by definition,

This proves the first claim. For the second claim, consider the event $A$ where, for all $x^{+}\in\mathcal{X}^{+}$, $x^{-}\in\mathcal{X}^{-}$ and $R,Q\in\mathcal{G}$,

By Lemma 9 applied to the sets $Q^{\mathsf{T}}\mathcal{X}^{-}$ and $Q^{\mathsf{T}}R\mathcal{X}^{+}$, followed by a union bound over $Q,R\in\mathcal{G}$, we obtain $\mathbb{P}(A)\ge1-\eta$ under our assumptions.

On $A$, for all $x^{+}\in\mathcal{X}^{+}$, $x^{-}\in\mathcal{X}^{-}$ and $R\in\mathcal{G}$,

where we used Lemma 8 and, in particular,

This immediately implies, for all $x^{+}\in\mathcal{X}^{+}$ and $x^{-}\in\mathcal{X}^{-}$,

where, again, we used Lemma 8 and, in particular,

The following observation again considers a random fully-connected layer and was stated by Dirksen et al. [15] as a direct consequence of Theorem 2.9 of Dirksen and Mendelson [14].⁵

We derive an analogue for the random convolution layer.

Proof. Let $A$ denote the event where, for all $m \in[M]$, $Q,R \in\mathcal{G}$ and $x \in\mathcal{X}_{m,Q}$,

By Lemma 11, applied to the sets $R^{\mathsf{T}}\mathcal{X}_{m,Q} \subset B_2^d\left(R^{\mathsf{T}}Q\boldsymbol{c}_m,r_m\right) \subset R_{\mathrm{rad}}B_2^d$ for $m \in[M]$ and $R,Q \in\mathcal{G}$, $\mathbb{P}(A) \ge1-\eta$ under our assumptions. Here, we used that $w\left(R^{\mathsf{T}}\mathcal{X}_{m,Q}\right)=w\left(\mathcal{X}_{m,Q}\right)$ by rotation invariance of the Gaussian width.

Let $m \in[M]$. On $A$, for $Q \in\mathcal{G}$ and $x \in\mathcal{X}_{m,Q}$,

where we used Lemma 8. By (4), for $x \in\mathcal{X}_m$ there exists $Q^* \in\mathcal{G}$ with $x \in\mathcal{X}_{m,Q^*}$ and thus

The following lemma is the key ingredient for the proof of Theorem 7. It states that under our assumptions, with high probability, a neuron

associated to a sample $x^* \in\mathcal{X}^{+}$, activates on the (image of the) whole component that this sample resides in. At the same time, it does not activate on (the image of) any sample of the other class. This lemma is the analogue to Lemma 19 from Dirksen et al. [15].

Proof. Clearly, the choice of $m_{x_k^+}$ ensures the second property. For the first property, it remains to show that, with probability at least $1-\eta$, for any $k \in[M^+]$ and all $x_k^+,x^+ \in\mathcal{X}_k^+$,

Let $A$ denote the event where, for $k \in[M^+]$ and $\ell\in[M^-]$,

By Lemma 10 applied to $\mathcal{C}^{+}$ and $\mathcal{C}^{-}$, $\mathbb{P}(A)\ge1-\eta/2$ under our assumptions. Let $B$ denote the event where, for $k \in[M^{+}]$ and $x^{+} \in\mathcal{X}^{+}_{k}$,

and, for $\ell\in[M^{-}]$ and $x^{-} \in\mathcal{X}^{-}_{\ell}$,

where

By Lemma 12 and a union bound, $\mathbb{P}(B)\geq1-\eta/2$ under our assumptions. Hence, $\mathbb{P}(A\cap B)\geq1-\eta$ and for the remainder of the proof we condition on this event.

Let $k\in[M^{+}]$ and $x^{+}_{\ast},x^{+}\in\mathcal{X}^{+}_{k}$. For $Q,R\in\mathcal{G}$,

where we used $\langle S_{Q}^{\dagger}\Phi(x^{+}_{\ast}),S_{Q}^{\dagger}u_{x^{+}_{\ast}}\rangle=\langle\Phi(x^{+}_{\ast}),u_{x^{+}_{\ast}}\rangle=0$, Hölder’s inequality and (3). Minimizing successively over $Q$ and $R$ yields

Using $B$, we find the upper bound

Let $x^{-}\in\mathcal{X}^{-}$ and pick $\ell\in[M^{-}]$ such that $x^{-}\in\mathcal{X}^{-}_{\ell}$. For $Q,R,U\in\mathcal{G}$,

where, again, we used Hölder’s inequality and the properties (3) of (lifted) circular shift operators. Minimizing over $Q$ and maximizing over $R$ and $U$ yields

Using both $A$ and $B$, we find the lower bound

Combining the upper and lower bounds (5) and (6), we find

for all $k \in[M^{+}]$, $x_{*}^{+},x^{+} \in\mathcal{X}_{k}^{+}$ and $x^{-} \in\mathcal{X}^{-}$, where we used that

Proof [Theorem 7] We use the notation from Algorithm 2. In the following we condition on the event of Lemma 13, which occurs with probability at least $1-\eta$ under the stated assumptions.

Termination and number of neurons. The first loop constructs the random convolution layer

For the second loop we claim that, after the $i$-th iteration, $A^{+}=\{x_1^{+},\ldots,x_i^{+}\}$ and

where each $x_{k_j}^{+}$ is part of some component $\mathcal{X}_{k_j}^{+}$ for pairwise distinct $k_1,\ldots,k_j\in[M^{+}]$.

For $i=0$, we have $A^{+}=\varnothing$ and $C^{+}=\mathcal{X}^{+}$, and hence the claim is trivially satisfied. Suppose that the claim holds for the $i$-th iteration. In the $(i+1)$-th iteration, the algorithm selects a random candidate sample $x_{i+1}^{+}\in C^{+}$ which is part of at least one new component $\mathcal{X}_{k_{i+1}}^{+}$ for some $k_{i+1}\in[M^{+}]\setminus\{k_1,\ldots,k_i\}$. By Lemma 13, we have $\varnothing\ne\mathcal{X}_{k_{i+1}}^{+}\subset\mathcal{V}_{x_{i+1}^{+}}$ and the condition of the if-statement in line 13 is true. Hence, $A^{+}=\{x_1^{+},\ldots,x_{i+1}^{+}\}$ and

and the claim follows by induction. In particular, after at most $M^{+}$ steps, the loop terminates due to $C^{+}=\varnothing$ and $A^{+}$ contains no more than $M^{+}$ samples. Moreover, $\mathcal{X}^{+}=\bigcup_{x_{*}^{+}\in A^{+}}\mathcal{V}_{x_{*}^{+}}$. Finally, we examine the last loop. As long as

we remove samples from $A^{+}$. The selection rule in line 19 is not important here. If removing a sample leads to a violation of this condition, the loop terminates and we add the last removed sample back to $A^{+}$ in line 22 so that the condition (7) is satisfied again. Interpolation. By Lemma 13, for all $x^{-} \in\mathcal{X}^{-}$, we have $\hat{\Phi}(\Phi(x^{-})) = 0$ and hence $F(x^{-}) = -1$. On the other hand, consider $x^{+} \in\bigcup_{x_{*}^{+}\in A^{+}} V_{x_{*}^{+}}$, which includes at least a fraction of $\alpha$ of the samples from $\mathcal{X}^{+}$ as we recall from above. Then, there exists $x_{*}^{+} \in A^{+}$ with $x^{+} \in V_{x_{*}^{+}}$, and hence $[\hat{\Phi}(\Phi(x^{+}))]_{x_{*}^{+}} > 0$. Consequently, $F(x^{+}) = +1$.

Invariance. Let $Q \in\mathcal{G}$. Observe, for $z,u \in\mathbb{R}^{K \times G}$,

and hence $\hat{\Phi}(S_{Q}^{\uparrow}z) = \hat{\Phi}(z)$. Combining this with Lemma 8, we find for any $x \in\mathbb{R}^{d}$ that

Number of parameters. The first layer $\Phi$ has weights $g_k \in\mathbb{R}^{d}$ and biases $\tau_k \in\mathbb{R}$ for $k \in[K]$, which is $(d+1)K$ parameters. The second layer $\hat{\Phi}$ has weights $u_{x_{*}^{+}} \in\mathbb{R}^{K\times G}$ and biases $m_{x_{*}^{+}} \in\mathbb{R}$ for $x_{*}^{+} \in A^{+}$ with $|A^{+}| \le M^{+}$, which is at most $(KG+1)M^{+}$ parameters. The last, linear layer, has weights $1 \in\mathbb{R}^{A^{+}}$, which is at most $M^{+}$ parameters. Hence, the total is no more than

Multi-class interpolation algorithm

In Appendix A we introduced Algorithm 2 in the context of a binary classification problem. Its approach can be easily generalized to multiple classes, see Algorithm 3. In this section, we outline how this generalization works but omit a full proof as it would be very similar to the proof of Theorem 7. The approach is similar to the one of Dirksen et al. [15].

A common approach to extend a binary classification method to multiple classes is the one-vs-rest method, where for each class a binary classifier is trained to distinguish it from all other classes. At inference time, the class label corresponding to the classifier with the highest confidence score is returned. We extend Algorithm 2 in a similar, yet not exactly the same manner. In the first loop (lines 1 to 4) we sample weights and biases of a random convolution layer which will be reused for each one-vs-rest subproblem. In the second loop (lines 5 to 7) we solve each of the one-vs-rest subproblems, utilizing a procedure (lines 14 to 29) which is the same as the second loop in Algorithm 2. Already at this point, one can use a simple union bound to prove a high success probability for the algorithm. What remains is the modified pruning loop (lines 8 to 12) which works similarly to before. However, instead of selecting the neuron with the least contribution for one class alone, we consider neurons over all classes. That at least a fraction of $\alpha$ of the samples of $\mathcal{X}$ are interpolated after this step can be derived analogously to the corresponding part of the proof of Theorem 7. In the end, we return the network (line 13), which reuses the first random layer and stacks the second layer for each of the one-vs-rest subproblems.

Algorithm 3 G-invariant multi-class memorization

Input: $G \le \mathcal{O}(d)$ finite, $\mathcal{X} = \mathcal{X}^{(1)} \cup \cdots \cup \mathcal{X}^{(L)} \subset \mathbb{R}^{d}$ finite with $N := |\mathcal{X}|$, number of random filters $K \in \mathbb{N}$, maximal bias $\lambda \ge 0$, interpolation fraction $\alpha \in (0,1]$

Output: $G$-invariant (generalized) convolutional neural net $F : \mathbb{R}^{d} \to \{0,1\}^{L}$

1: for $k \in [K]$ do
2:     $g_k \leftarrow$ independent sample from $\mathcal{N}(\mathbf{0},I_d)$
3:     $\tau_k \leftarrow$ independent sample from $\operatorname{Unif}([-\lambda,\lambda])$
4: end for                                      ▷ $\mathbf{g}=(g_1,\ldots,g_K),\ \boldsymbol{\tau}=(\tau_1,\ldots,\tau_K)$
5: for $\ell \in [L]$ do
6:     $\mathcal{A}^{(\ell)} \leftarrow \operatorname{Interpolate}(\mathcal{X}^{(\ell)},\mathcal{X}\setminus\mathcal{X}^{(\ell)},\mathbf{g},\boldsymbol{\tau})$
7: end for                                      ▷ $\mathcal{A}=\mathcal{A}^{(1)}\cup\cdots\cup\mathcal{A}^{(L)}$
8: while $\left|\bigcup_{x_\ast\in\mathcal{A}}\mathcal{V}_{x_\ast}\right| \ge \alpha N$ do
9:     $\ell,x_\ast \leftarrow \underset{\ell\in[L],x_\ast\in\mathcal{A}^{(\ell)}}{\arg\min}\left|\mathcal{V}_{x_\ast}\setminus\bigcup_{\tilde{x}_\ast\in\mathcal{A}\setminus\{x_\ast\}}\mathcal{V}_{\tilde{x}_\ast}\right|$
10:    $\mathcal{A}^{(\ell)} \leftarrow \mathcal{A}^{(\ell)}\setminus\{x_\ast\}$
11: end while
12: $\mathcal{A}^{(\ell)} \leftarrow \mathcal{A}^{(\ell)}\cup\{x_\ast\}$       ▷ $\widehat{\Phi}^{(\ell)}(z)=\left[\sigma\left(m_{x_\ast}-\langle\langle z,u_{x_\ast}\rangle\rangle\right)\right]_{x_\ast\in\mathcal{A}^{(\ell)}}$
13: return $F(x)=\left(F^{(1)}(x),\ldots,F^{(L)}(x)\right)$                  ▷ $F^{(\ell)}(x)=\sigma\left(\langle\mathbf{1},\widehat{\Phi}^{(\ell)}(\Phi(x))\rangle\right)$
14: procedure $\operatorname{Interpolate}(\mathcal{X}^{+},\mathcal{X}^{-},\mathbf{g},\boldsymbol{\tau})$
15:     $\mathcal{A}^{+}\leftarrow\varnothing$                                      ▷ $\Phi(x)=\left[\sigma(x\circledast g_k+\tau_k)\right]_{k\in[K]}$
16:     $\mathcal{C}^{+}\leftarrow\mathcal{X}^{+}$
17:     while $|\mathcal{C}^{+}|>0$ do
18:         $x_\ast^{+}\leftarrow$ random sample from $\mathcal{C}^{+}$
19:         $\mathcal{C}^{+}\leftarrow\mathcal{C}^{+}\setminus\{x_\ast^{+}\}$
20:         $u_{x_\ast^{+}}\leftarrow\mathbf{1}[\Phi(x_\ast^{+})=0]$
21:         $m_{x_\ast^{+}}\leftarrow\min_{x^{-}\in\mathcal{X}^{-}}\langle\langle\Phi(x^{-}),u_{x_\ast^{+}}\rangle\rangle$       ▷ $\widehat{\varphi}_{x_\ast^{+}}(z)=\sigma\left(m_{x_\ast^{+}}-\langle\langle z,u_{x_\ast^{+}}\rangle\rangle\right)$
22:         $\mathcal{V}_{x_\ast^{+}}\leftarrow\{x^{+}\in\mathcal{X}^{+}:\widehat{\varphi}_{x_\ast^{+}}(\Phi(x^{+}))>0\}$
23:         if $|\mathcal{V}_{x_\ast^{+}}|>0$ then
24:             $\mathcal{A}^{+}\leftarrow\mathcal{A}^{+}\cup\{x_\ast^{+}\}$
25:             $\mathcal{C}^{+}\leftarrow\mathcal{C}^{+}\setminus\mathcal{V}_{x_\ast^{+}}$
26:         end if
27:     end while
28:     return $\mathcal{A}^{+}$
29: end procedure