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.
Figures & tables
Figure 1: Translation-invariant mutual covering. Following an arrow applies a horizontal circular shift. For simplicity, we only include three horizontal translations, in general the division would be more granular and include vertical translations. Condition ( 2 ) on the radii in Theorem 3 lets the components of the covering adapt to the mutual positioning of the classes by allowing them to grow (almost) as far as the optimal decision boundary. At the same time, each component consists of multiple sub-components, one for each possible translation. A component being a union of sub-components makes it translation-invariant.
Figure 2: Activation regions on the XOR data set. Red and blue points have labels +1 and −1 , respectively. For each class we have drawn 250 samples from a mixture of two Gaussian distributions with covariance matrices 0.35⋅I2 . The associated reference samples which the algorithm picked at random are marked with stars of the same color as its neuron’s activation region. On the left, the network is invariant under 180° rotations, while on the right, there is no invariance.
Figure 3: MNIST: size of the second layer. Depending on the number of filters (or neurons) in the first layer we report the number of filters (or neurons) in the second layer for three different levels of α . We report the average over five runs with 95% percentile intervals.
Figure 4: MNIST: number of parameters. Depending on the number of filters (or neurons) in the first layer we report the total number of parameters of each network for three different levels of α . We report the average over ten runs with 95% percentile intervals. In both cases, decreasing the size of the first layer by one more step leads to a failed interpolation attempt in at least one of the ten random runs.
Figure 5: CIFAR-10: size of the second layer. Depending on the number of filters (or neurons) in the first layer we report the number of filters (or neurons) in the second layer for three different levels of α . We report the average over five runs with 95% percentile intervals.
Figure 6: CIFAR-10: number of parameters. Depending on the number of filters (or neurons) in the first layer we report the number of total parameters of each network for three different levels of α . We report the average over ten runs with 95% percentile intervals. In both cases, decreasing the size of the first layer by one more step leads to a failed interpolation attempt in at least one of the ten random runs.
Figure 7: Influence of the interpolation fraction hyperparameter. We report the number of filters and neurons in the second layer, respectively, in terms of the interpolation fraction α . In each case, we picked the largest values of K from Figures 3 and 5 . We report the average over five runs with 95% percentile intervals, which are very narrow and thus hard to see.
data set
G
∣G∣
MFC/MConvNet
XOR
{I2,−I2}
2
2.07
MNIST
{\T0,0↑,\T0,7↑,\T0,14↑,\T0,21↑}
4
3.98
CIFAR-10
{\T0,0↑,\T0,8↑,\T0,16↑,\T0,24↑}
4
3.92
XOR ∗
{I2,−I2}
2
1.61
Table 1: Difference in covering numbers on invariant data sets. Ratio of the average number of neurons in the second layer of the fully-connected network MFC and average number of filters in the second layer of the convolutional network MConvNet compared to the group size. In any case we use KConvNet=5000 and KFC=∣G∣⋅KConvNet , similar to Section 3.2 . For XOR and XOR ∗ we used λ=2 and did 50 random trials, for MNIST and CIFAR-10 we used λ=0 and did 5 random trials. XOR ∗ uses only the plain data set.
Neural network memorization studies how models store and retrieve training examples, how this differs from generalization, and how memory can be measured or controlled.
Center for Data Science New York University · Center for Computational Neuroscience Flatiron Institute · Work done while partially affiliated with Center for Data Science, New York University.
School of Mathematics (Zhuhai), Sun Yat-sen University, Zhuhai, China. · School of Mathematics (Zhuhai) and Guangdong Province Key Laboratory of Computational Science, Sun Yat-sen University, Zhuhai, China.