# The Foes of Neural Network’s Data Efficiency Among Unnecessary Input
Dimensions

Vanessa D’Amario  Sanjana Srivastava  Tomotake Sasaki  Xavier Boix  Center for
Brains, Minds & Machines
Department of Brain and Cognitive Science,
Massachusetts Institute of Technology
Cambridge, MA 02139, USA  Stanford University
Stanford, CA 94305, USA  Artificial Intelligence Laboratory
Fujitsu Limited
Kawasaki, Kanagawa 211-8588, Japan

###### Abstract

Datasets often contain input dimensions that are unnecessary to predict the
output label, _e.g.,_ background in object recognition, which lead to more
trainable parameters. Deep Neural Networks (DNNs) are robust to increasing the
number of parameters in the hidden layers, but it is unclear whether this
holds true for the input layer. In this letter, we investigate the impact of
unnecessary input dimensions on a central issue of DNNs: their data
efficiency, _ie.,_ the amount of examples needed to achieve certain
generalization performance. Our results show that unnecessary input dimensions
that are task-unrelated substantially degrade data efficiency. This highlights
the need for mechanisms that remove task-unrelated dimensions to enable data
efficiency gains.

###### keywords:

Data Efficiency, Overparameterization, Object Background.

##  1 Introduction

The success of Deep Neural Networks (DNNs) contrasts with the still distant
goal of learning with few training examples as in biological systems,  _ie.,_
in a data efficient manner [1]. Little is known about what aspects could
improve the DNN’s data efficiency.

DNNs are usually trained on high dimensional datasets (_e.g.,_ images and
text), and many input dimensions of the DNN may be unnecessary to predict the
ground-truth label as they are unrelated and/or redundant to the task at hand.
Classic machine learning theory predicts that unnecessary input dimensions may
degrade the DNN’s data efficiency [2], as the classifier may overfit to the
unnecessary input dimensions if not enough training examples are provided to
learn to discard them.

However, DNNs have challenged classic machine learning theories as they can
achieve high test accuracy despite having a number of trainable parameters
much larger than the number of training examples, _ie.,_ DNNs are
overparameterized [3, 4]. Since unnecessary input dimensions lead to more
overparameterization, it is unclear in what way DNNs suffer from unnecessary
input dimensions and whether more data is needed to learn to discard them. In
this letter, we show that the DNNs’ data efficiency depends on whether the
unnecessary dimensions are _task-unrelated_ or _task-related_ (redundant with
respect to other input dimensions). Namely, increasing the number of _task-
unrelated_ dimensions leads to a substantial drop of data efficiency, while
increasing the number of _task-related_ dimensions that are linear
combinations of other _task-related_ dimensions, helps to alleviate the
negative impact of the _task-unrelated_ dimensions.

##  2 Related Works

We now relate this work with the effect of background on the generalization
abilities of DNNs in object recognition, and also with the DNNs generalization
abilities depending on the number of parameters of the network.

###  2.1 Object’s Background and DNN Generalization

Previous works have shown that DNNs for image recognition fail to classify
objects in novel and uncommon backgrounds [5, 6, 7]. Remarkably, popular
object recognition datasets are biased to such an extent that DNNs can predict
the object category even when the objects are removed from the image [8, 9].

Barbu  _et al._[10] introduced a new benchmark which addresses the biased co-
occurrence of objects and background, among other types of bias. DNNs exhibit
large performance drops in this benchmark compared to ImageNet [11]. Recently,
Borji has shown that a large portion of the performance drop comes from the
bias in object’s background, as classifying the object in isolation
substantially alleviates the performance drop [12].

In contrast to previous works, we analyse the impact of the object’s
background to the DNN’s generalization performance when the dataset is
unbiased,  _ie.,_ the statistics of the object’s background are the same
between training and testing and there is no bias in the co-occurrence of
object and background. To the best of our knowledge, our work is the first to
investigate the effects of object’s background on DNNs when the object’s
background is unbiased.

###  2.2 Overparameterization and Data Dimensionality

A remarkable characteristic of DNNs is that the test error follows a double-
descend when the DNN’s width is increased by adding more hidden units. Thus,
the test error decreases as the network’s width is increased in both the
underparameterized and overparameterized regimes, except in a critical region
between these two where a substantial error increase can take place [13, 14,
4]. This phenomenon relates to unnecessary input dimensions because these also
increase the width of the network, albeit in the input layer rather than in
the intermediate layers. As we show in the sequel, increasing the number of
unnecessary input dimensions can have the opposite effect of increasing the
number of hidden units in the test error.

Another strand of research relates the structure of the dataset with the
generalization ability of the network. Several works in statistical learning
theory for kernel machines relate the spectrum of the dataset with the
generalization performance [15]. For neural networks, [16, 17] define the
intrinsic dimensionality based on the dimension of the data manifold. These
works analyze how the network reduces the intrinsic dimension across layers.
Yet, these metrics based on manifolds do not provide insights about how
specific aspects of the dataset,  _e.g.,_ unnecessary dimensions, contribute
to the intrinsic dimensionality.

##  3 Unnecessary Input Dimensions and Data Efficiency

We aim at analyzing the effect of unnecessary input dimensions on the data
efficiency of DNNs. Let $\mathbf{x}$ be a vector representing a data sample,
and let $\mathbf{y}$ be the ground-truth label of $\mathbf{x}$. We define
$f(\mathbf{x})=\mathbf{y}$ as the target function of the learning problem.
Also, we use $[\mathbf{x};\mathbf{u}]$ to denote the data sample $\mathbf{x}$
with unnecessary input dimensions appended to it. The unnecessary dimensions
do not affect the target function of the learning problem,  _ie.,_
$g([\mathbf{x};\mathbf{u}])=f(\mathbf{x})=\mathbf{y}$, where $g$ is the target
function of the learning problem with unnecessary input dimensions. Each
sample can have a different set of dimensions that are unnecessary,  _e.g.,_
one sample could be $[\mathbf{x}_{1};\mathbf{u}_{1}]$ and another be
$[\mathbf{u}_{2};\mathbf{x}_{2}]$. Note that this variability is present in
object recognition because the dimensions representing the object’s background
are unnecessary and vary across data samples, as the object can be in
different image locations.

We define two types of unnecessary input dimensions: _task-unrelated_ and
_task-related_. Unnecessary input dimensions are _task-unrelated_ when they
are independent of $\mathbf{x}$,  _ie.,_ they can not be predicted from
$\mathbf{x}$, as in unbiased object’s background. Otherwise, the unnecessary
dimensions are _task-related_ , which are equivalent to redundant dimensions.
An example that leads to more _task-related_ unnecessary dimensions is
upscaling the image.

To study the effect of unnecessary input dimensions, we measure the test
accuracy of DNNs trained with different amounts of unnecessary input
dimensions and training examples. Given a DNN architecture and a dataset with
a fixed amount of unnecessary dimensions, we define the _data efficiency_ of
the DNN as the Area Under the Test Curve (AUTC) for the DNN trained with
different number of training examples. The curve is monotonically increasing,
as more training examples lead to higher test accuracy, and the AUTC measures
the area under it. We normalize the AUTC to be between $0$ and $1$, where $1$
is the maximum achievable, and it corresponds to $100\%$ test accuracy for all
number of training examples. In the experiments where the number of training
examples spans several orders of magnitude, we calculate the AUTC by
converting the number of training examples in logarithmic scale, such that all
orders of magnitude are equally taken into account.

##  4 Datasets and Networks

We now introduce the datasets and networks we use in the experiments (refer to
A and B for additional details).

###  4.1 Linearly Separable Dataset

We use a linearly separable dataset for binary classification, as it
facilitates relating results of classic machine learning and DNNs. We generate
a binary classification dataset of $30$ input dimensions, which follow a
Gaussian distribution with $(\mu=0,\sigma=1)$. The ground-truth label is the
output of a linear classifier, such that the dataset is linearly separable
with a hyperplane randomly chosen. Unnecessary input dimensions are appended
to the data samples. _Task-unrelated_ dimensions follow a Gaussian
distribution with $(\mu=0,\sigma=0.1)$. The _task-related_ dimensions are
linear combinations of the dimensions of the original dataset samples.

We evaluate the following linear and Multi-Layer Perceptron (MLP) networks:
linear network trained with square loss (pseudo-inverse solution), MLP with
linear activation functions trained with either square loss or cross entropy
loss, and MLP with ReLU trained with cross entropy loss.

###  4.2 Object Recognition Datasets

We evaluate object recognition datasets based on extensions of the MNIST
dataset and the Stanford dogs dataset [18].

#### Synthetic and Natural MNIST

We generate two datasets based on MNIST: the synthetic MNIST and the natural
MNIST, which have synthetic and natural background, respectively. In both
datasets, the MNIST digit is always at the center of the image and normalized
between $0$ and $1$.

In the synthetic MNIST dataset, the _task-unrelated_ dimensions are sampled
from a Gaussian distribution with $(\mu=0,\sigma=0.2)$ and the _task-related_
dimensions are the result of upscaling the MNIST digit. We also combine _task-
related_ and _unrelated_ dimensions by fixing the size of the image and
changing the ratio of _task-related_ and _unrelated_ dimensions by upscaling
the MNIST digit.

In the natural MNIST dataset, the background is taken from the Places dataset
[19], as in [7]. The size of the image is constant across experiments
($256\times 256$ pixels), and the size of the MNIST digits determines the
amount of _task-related_ and _unrelated_ dimensions.

We use the MLP with ReLU and cross entropy loss, and also Convolutional Neural
Networks (CNNs). The architecture of the CNN consists of three convolutional
layers each with max-pooling, followed by two fully connected layers. Since
the receptive field size of the CNN neurons may have an impact on the data
efficiency, we evaluate different receptive field sizes. We use a factor $r$
to scale the receptive field size, such that the convolution filter size is
$(r\cdot 3)\times(r\cdot 3)$ and the pooling region size is $(r\cdot
2)\times(r\cdot 2)$. We experiment by either fixing $r$ to a constant value or
adapting $r$ to the scale of the MNIST digit, such that the receptive fields
of the neurons capture the same object region independently of the scale of
the digit.

#### Stanford Dogs

Recall our analysis focuses on unnecessary input dimensions that are unbiased.
We use the Stanford dogs dataset [18] as it is reasonable to assume that the
bias between breeds of dogs and background is negligible. This dataset
contains natural images ($227\times 227$ pixels) of dogs at different image
positions. The amount of _task-unrelated_ dimensions is determined by the dog
size, which is different for each image. To evaluate the effect of unnecessary
input dimensions, we introduce the following five versions of the dataset.
Case 1 corresponds to the original image. In case 2, we multiply by zero the
pixels of the background, which reduces the variability of the _task-
unrelated_ dimensions. In case 3, the dog is centered in the image. In case 4,
we fix the ratio of _task-related/unrelated_ dimensions by centering the dog
and scaling it to half of the image size. In case 5, we remove the background
by cropping and scaling the dog.

We use a ResNet-18 [20], following the standard pre-processing of the image
used in ImageNet.

##  5 Results

---
Figure 1: Results of DNNs’ data efficiency for different amount of unnecessary
input dimensions, tasks and networks. Error bars indicate standard deviation
across experiment repetitions.

All results are reported in Figure 1.

###  5.1 Linearly Separable Dataset

Figure 1A shows the test accuracy of the pseudo-inverse solution for different
number of training examples and unnecessary input dimensions. Figure 1B
reports the data efficiency of all networks tested for different number of
unnecessary input dimensions. Recall that the data efficiency is measured with
the AUTC and summarizes the test accuracy as a function of the amount of
training examples,  _e.g.,_ for the pseudo-inverse solution, the curves in
Figure 1A are summarized by the AUTC in Figure 1B. We observe that increasing
the amount of _task-unrelated_ dimensions harms the data efficiency,  _ie.,_
the AUTC drops. Also, the _task-related_ dimensions alone do not harm data
efficiency, and they alleviate the effect of the _task-unrelated_ dimensions.

These results clarify the difference between robustness to
overparameterization in intermediate layers and unnecessary input dimensions.
Note that the effect on the test accuracy of increasing the number of hidden
units is the opposite of increasing the number of _task-unrelated_ input
dimensions,  _ie.,_ DNNs are not robust to all kinds of overparameterization.

Thus, the results on _task-unrelated_ dimensions can be predicted with classic
machine learning results. In C.1, we outline such results for the pseudo-
inverse solution with _task-unrelated_ dimensions that are Gaussian-
distributed. There, we show that _task-unrelated_ dimensions leads to the
pseudo-inverse, Tihkonov-regularized solution calculated in the dataset
without _task-unrelated_ dimensions. Since in this case the regularization can
not be tuned or switched off as it is fixed by the number of _task-unrelated_
dimensions, it is likely to harm the test accuracy, as we have observed.

The regularizer is beneficial in some specific cases. C.2 highlights a
regression problem in which certain amounts of _task-unrelated_ dimensions
help to improve generalization. In Figure 1A, we can also see that for a given
number of training examples, increasing the number of _task-unrelated_
dimensions improves the test accuracy in some cases. This specific trends
relate to the aforementioned double descend of DNNs [13, 14]. As shown in [4],
the location of the critical region is affected by the number of training
examples and the complexity of the model. Here, the complexity of the model is
affected by the number of _task-unrelated_ dimensions due to its
regularization effect.

Finally, in D.1 we show that the same conclusions are obtained for non-
linearly separable datasets and other types of noise.

###  5.2 Object Recognition Datasets

Figure 1C shows the log-AUTC for the MLP and the CNN for different amount of
unnecessary dimensions (an increasing amount as we move left to right), for
the synthetic MNIST dataset. In D.2, we also report the test accuracy for
different number of unnecessary dimensions. Conclusions are consistent with
the previous results in the linearly separable dataset. Also, we observe that
CNNs are overall much more data efficient than MLPs, which is expected because
of their more adequate inductive bias given by the weight sharing of the
convolutions.

Figure 1D shows results in natural MNIST dataset for different ratios of
_task-related/unrelated_ dimensions. The plots compare CNNs with different
receptive field sizes, represented by the factor $r$ (see section 4.2). Since
the CNN achieves high accuracy with few examples, the mean and standard
deviation of the log-AUTC (left plot) hardly shows any variation when computed
on more than $20$ training examples per class. Yet, the gap of the testing
accuracy is considerable for $20$ training examples per class (right plot).
These results confirm that _task-unrelated_ dimensions degrades data
efficiency independently of the receptive field sizes (see D.3 for additional
results further supporting these conclusions).

Figure 1E shows results on the Stanford dogs dataset, namely the AUTC score
across the five cases of unnecessary dimensions that we evaluate. This dataset
serves to assess a more realistic scenario, where the objects can appear at
different positions and scales. We observe that the _task-unrelated_
dimensions, which come from the background, harm the data efficiency (cases 1
to 4 versus case 5). Putting to zero the unnecessary dimensions improves the
data efficiency of models trained on the original dataset (cases 2 to 4 versus
case 1). This is expected as the _task-unrelated_ dimensions become redundant
as they all take the same value in all images. We also observe that removing
the variability of the position and scale of the object hardly affects the
data efficiency (case 2 to 4). Thus, learning to discard the background
requires more training examples than learning to handle the variability in
scale and position of the object.

##  6 Conclusions

We have analyzed the effect of unnecessary input dimensions (_e.g.,_ object’s
background). We found that _task-unrelated_ dimensions harm the data
efficiency, while increasing the number of _task-related_ dimensions that are
linear combinations of other _task-related_ dimensions help to alleviate the
negative effect of _task-unrelated_ dimensions. These results demonstrate that
the robustness of DNNs to overparameterization is limited, as increasing the
number of _task-unrelated_ input dimensions is a form of overparameterization
that degrades the accuracy. Also, our results add to the growing body of works
in object recognition that shows that bias in the object’s background can
undermine the reliability of DNNs. Here we have shown that the problem runs
far deeper, as the object’s background negatively affects the network even
when there is no bias.

Overall, these results suggest that data efficiency gains could be enabled by
mechanisms that remove _task-unrelated_ dimensions, such as foveation for
image classification [21, 22], or by adapting to DNNs regularization
techniques that encourage predictions from a sparse subset of input dimensions
(_e.g.,_ $\ell_{1}$ regularization for linear regression [23]).

## Acknowledgment

We would like to thank Pawan Sinha and Tomaso Poggio for useful discussions
and insightful advice provided during this project. This work has been
supported by the Center for Brains, Minds and Machines (funded by NSF STC
award CCF-1231216), XB by the R01EY020517 grant from the National Eye
Institute (NIH) and XB and VD by Fujitsu Laboratories Ltd. (Contract No.
40008819) and the MIT-Sensetime Alliance on Artificial Intelligence.

## References

  * [1] D. Hassabis, D. Kumaran, C. Summerfield, M. Botvinick, Neuroscience-inspired artificial intelligence, Neuron 95 (2) (2017) 245–258.
  * [2] T. Hastie, R. Tibshirani, J. Friedman, The elements of statistical learning: data mining, inference, and prediction, Springer Science & Business Media, 2009\.
  * [3] C. Zhang, S. Bengio, M. Hardt, B. Recht, O. Vinyals, Understanding deep learning requires rethinking generalization, in: Proceedings of the International Conference on Learning Representations (ICLR), 2017.
URL https://openreview.net/forum?id=Sy8gdB9xx

  * [4] P. Nakkiran, G. Kaplun, Y. Bansal, T. Yang, B. Barak, I. Sutskever, Deep double descent: Where bigger models and more data hurt, in: Proceedings of the International Conference on Learning Representations (ICLR), 2020.
  * [5] M. J. Choi, A. Torralba, A. S. Willsky, Context models and out-of-context objects, Pattern Recognition Letters 33 (7) (2012) 853–862.
  * [6] S. Beery, G. Van Horn, P. Perona, Recognition in terra incognita, in: Proceedings of the European Conference on Computer Vision (ECCV), 2018, pp. 456–473.
  * [7] A. Volokitin, G. Roig, T. A. Poggio, Do deep neural networks suffer from crowding?, in: Advances in Neural Information Processing Systems (NIPS), 2017, pp. 5628–5638.
  * [8] Z. Zhu, L. Xie, A. L. Yuille, Object recognition with and without objects, in: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2017, pp. 3609–3615.
  * [9] K. Y. Xiao, L. Engstrom, A. Ilyas, A. Madry, Noise or signal: The role of image backgrounds in object recognition, in: Proceedings of the International Conference on Learning Representations (ICLR), 2021.
URL https://openreview.net/forum?id=gl3D-xY7wLq

  * [10] A. Barbu, D. Mayo, J. Alverio, W. Luo, C. Wang, D. Gutfreund, J. Tenenbaum, B. Katz, ObjectNet: A large-scale bias-controlled dataset for pushing the limits of object recognition models, in: Advances in Neural Information Processing Systems (NeurIPS), 2019, pp. 9448–9458.
  * [11] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, L. Fei-Fei, ImageNet: A large-scale hierarchical image database, in: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2009, pp. 248–255.
  * [12] A. Borji, Contemplating real-world object classification, in: Proceedings of the International Conference on Learning Representations (ICLR), 2021.
URL https://openreview.net/forum?id=Q4EUywJIkqr

  * [13] M. S. Advani, A. M. Saxe, H. Sompolinsky, High-dimensional dynamics of generalization error in neural networks, Neural Networks 132 (2020) 428–446.
  * [14] M. Belkin, D. Hsu, S. Ma, S. Mandal, Reconciling modern machine-learning practice and the classical bias–variance trade-off, Proceedings of the National Academy of Sciences 116 (32) (2019) 15849–15854.
  * [15] T. Zhang, Learning bounds for kernel regression using effective data dimensionality, Neural Computation 17 (9) (2005) 2077–2098.
  * [16] S. Recanatesi, M. Farrell, M. Advani, T. Moore, G. Lajoie, E. Shea-Brown, Dimensionality compression and expansion in deep neural networks, arXiv preprint arXiv:1906.00443.
  * [17] A. Ansuini, A. Laio, J. H. Macke, D. Zoccolan, Intrinsic dimension of data representations in deep neural networks, in: Advances in Neural Information Processing Systems (NeurIPS), 2019, pp. 6109–6119.
  * [18] A. Khosla, N. Jayadevaprakash, B. Yao, L. Fei-Fei, Novel dataset for fine-grained image categorization, in: First Workshop on Fine-Grained Visual Categorization, IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2011, the dataset is available at http://vision.stanford.edu/aditya86/ImageNetDogs/ (Last access: Oct. 1, 2020).
  * [19] B. Zhou, A. Lapedriza, J. Xiao, A. Torralba, A. Oliva, Learning deep features for scene recognition using Places database, in: Advances in Neural Information Processing Systems (NIPS), 2014, pp. 487–495, the dataset is available at http://places.csail.mit.edu/ (Last access: Oct. 1, 2020).
  * [20] K. He, X. Zhang, S. Ren, J. Sun, Deep residual learning for image recognition, in: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016, pp. 770–778.
  * [21] Y. Luo, X. Boix, G. Roig, T. Poggio, Q. Zhao, Foveation-based mechanisms alleviate adversarial examples, Tech. Rep. CBMM Memo No. 44, Center for Brains, Minds and Machines (2016).
  * [22] E. Akbas, M. P. Eckstein, Object detection through search with a foveated visual system, PLOS Computational Biology 13 (10) (2017) e1005743.
  * [23] T. Hastie, R. Tibshirani, M. Wainwright, Statistical learning with sparsity: the lasso and generalizations, Chapman and Hall/CRC, 2019.
  * [24] B. Schölkopf, R. Herbrich, A. J. Smola, A generalized representer theorem, in: Proceedings of the International Conference on Computational Learning Theory (COLT), 2001, pp. 416–426.
  * [25] I. Daubechies, Ten lectures on wavelets, SIAM, 1992.

##  Appendix A Data Generation Details

We provide further details about the data generation. In A.1, we discuss the
linearly separable dataset, and A.2 divides in three parts, where we introduce
the synthetic MNIST, the natural MNIST, and the Stanford dogs datasets.

###  A.1 Linearly Separable Dataset

For the binary classification datasets, we generate the samples using a linear
teacher network $\mathbf{y}_{i}={W}^{*}\mathbf{x}_{i}$, with
${W}^{*}\in\mathbb{R}^{2\times 30}$ (_ie.,_ $o=2$, $p=30$) components,
generated from a standard Gaussian distribution $(\mu=0,\sigma=1)$. Each input
sample dimension is also drawn from a standard Gaussian distribution. To
generate the labels, we quantize the output to two categories. The _task-
unrelated_ dimensions have $\sigma=0.1$, while _task-related_ dimensions are
linear combinations of the $p$ (= 30) dimensions of the dataset, where the
weights of the combinations are selected from a standard Gaussian
distribution.

###  A.2 Object Recognition Datasets

#### Synthetic MNIST

In Figure 1C, we show the different experiments on the Synthetic MNIST
datasets. In all of these, the MNIST digit is normalized to have values
between $0$ and $1$. For the experiments with _task-unrelated_ dimensions, the
image size increases as we add pixels with random values at the edge, which
constitute the _task-unrelated_ dimensions. These random values are the
absolute value of numbers extracted from a zero-mean Gaussian distribution
with $\sigma=0.2$. The MNIST digit edge has size $28$ across all the _task-
unrelated_ versions for this dataset, while the image edge is equal to
$[40,56,80,120,160,188,200]$. For the experiment with _task-related_
dimensions, we upscale the MNIST digit using bi-cubic interpolation. After the
upscale, the image size is equal to $[28,36,40,56,80,120,160]$. For the
experiment with _task-related/unrelated_ dimensions, we use the same
aforementioned procedure to generate the _task-unrelated_ and _task-related_
dimensions. We fix the image size to $200\times 200$ pixels, while the
upscaled MNIST digit edge is equal to $[28,36,40,56,80,120,160]$. The amount
of training examples per class for all the experiments is equivalent to
$n_{tr}=[1,2,5,10,20,50,100,300,500,1000]$.

#### Natural MNIST

We embed the MNIST digits on a natural background from the PLACES dataset
[19], as in [7]. We generate the _task-related/unrelated_ by sampling without
replacement a normalized natural image of size $256\times 256$ pixels. We
superimpose at its center an upscaled and normalized digit from MNIST. The
upscaled MNIST digit assumes sizes $[200,150,80,28]$ as shown in Figure 1D.
The number of examples per class corresponds to
$n_{tr}=[20,50,100,200,300,500,1000]$.

#### Stanford Dogs

All the images from the Stanford Dogs dataset, for all the five cases
considered in Figure 1E, are resized to $227\times 227$ pixels. We subtract to
the RGB channels the values $R_{\text{mean}}=123.68$,
$G_{\text{mean}}=116.78$, and $B_{\text{mean}}=103.94$, as done for
recentering the ImageNet dataset. We split the original training set into a
training and a validation set, the former consisting of $90$ examples per
class (breed), the latter consisting of $10$ examples per class. The amount of
training examples per class used to compute the AUTC is $n_{tr}=[23,45,90]$.

##  Appendix B Architecture and Optimization Details

In B.1, we report the optimization details of the solution to the linear
problem, using the pseudo-inverse. Architectures and optimization protocols of
networks used on the linearly separable classes and the MNIST datasets are
respectively in B.2 and B.3. B.4 contains the optimization procedure used on
the Stanford Dogs dataset.

###  B.1 Linear classifier (pseudo-inverse)

We repeat the classification experiments $10$ times. We use the pseudo-inverse
solution as described in (C.1) below.

###  B.2 MLP

#### Architectures

We consider MLPs with one hidden layer consisting of 128 nodes and a soft-max
operation preceding the output.

#### Optimization Protocol

MLPs trained on the linearly separable binary classification task share the
same optimization protocol. We fix the maximum number of epochs at 100. The
convergence criterion is based on early stopping, with tolerance value
$10^{-4}$ on the validation loss and patience of 8 epochs. Optimal batch size
and learning rate are selected through a grid search procedure, respectively,
over the arrays $[2,10,32,50]$ and $[10^{-5},10^{-4},10^{-3},10^{-2}]$. We
eliminate batch size values from the hyper-parameters search anytime those are
equal to or larger than the number of training examples. We apply a reduction
factor $1/10$ on the learning rate as the validation loss shows variations
smaller than $10^{-4}$ over five epochs. The initialization of the weights
adopted across networks and layers is the Glorot uniform,  _ie.,_ uniform
distribution in the interval $[-u,u]$, where $u=\sqrt{{6}/(\text{fan}_{\rm
in}+\text{fan}_{\rm out})}$, with $\text{fan}_{\rm in}$ and $\text{fan}_{\rm
out}$ respectively number of input and output units. We report mean and
standard deviation of the AUTC values across three repetitions of each
experiment. The optimization protocol of MLP for MNIST is the same as the CNN
detailed next.

###  B.3 CNNs on synthetic MNIST and natural MNIST

#### Architectures

The CNNs consist of three convolutional layers (iC-iiiC) followed by a flatten
operation and two fully connected layers (iL and iiL). In Table 1 we report:
at the first row the number of filters or nodes, depending on the layer; at
the second row, the size of filters and max-pooling operations; and at the
last row, the non-linearity used, if any. The filters and max-pool operations
have square dimensions, and their sizes at the first layers vary across
experiments.

Table 1: CNN for object recognition. From the top: number of filters *C or nodes *L at each hidden layer, filters size and max pooling sizes for *C; activation functions following *C or *L.  |  iC |  iiC |  iiiC |  iL |  iiL
---|---|---|---|---|---
#filters/#nodes |  32 |  64 |  64 |  64 |  10
filter, pooling |  var, var |  3, 2 |  3, none |  none |  none
act. function |  ReLU |  ReLU |  None |  ReLU |  soft-max

In Table 2, we report filter and max-pooling sizes corresponding to different
receptive fields at the first layer. The AUTC and test accuracy for these
filter/max-pooling configurations are evaluated on natural MNIST, in Figure
1D.

Table 2: Filters and max-Pooling sizes at the first layer for CNNs trained on Natural MNIST. |  Adapt |  $r=9$ |  $r=4.5$ |  $r=2.3$ |  $r=1$
---|---|---|---|---|---
filter |  $r\cdot 3$ |  27 |  14 |  7 |  3
pooling |  $r\cdot 2$ |  18 |  9 |  5 |  2

#### Optimization Protocols

CNNs on synthetic MNIST share the same optimization protocol of MLPs. MLPs are
provided with a vectorized version of the image. Models are optimized using
stochastic gradient descent with null momentum. Batch size and learning rate
are selected using a grid search procedure. The learning rate array has values
$[1,8\cdot 10^{-1},5\cdot 10^{-1},2\cdot
10^{-1},10^{-1},10^{-2},10^{-3},10^{-4},10^{-5},5\cdot 10^{-6},10^{-6}]$, the
batch size array is $[10,32,50,100]$. We eliminate batch size values from the
hyper-parameters search anytime those are equal to or larger than the number
of training examples. The convergence criterion is based on early stopping,
convergence is reached when the validation loss shows across 10 repetitions
variations smaller than $10^{-6}$. The maximum amount of epochs is fixed at
$500$. We reduce the learning rate by a factor $1/10$ when variations of the
validation loss are smaller than $10^{-4}$ across $5$ epochs. The
initialization of the weights values across architectures is based on the
Glorot uniform distribution, or uniform distribution in the interval $[-u,u]$,
where $u=\sqrt{{6}/(\text{fan}_{\rm in}+\text{fan}_{\rm out})}$, with
$\text{fan}_{\rm in}$ and $\text{fan}_{\rm out}$ respectively number of input
and output units.

The natural MNIST optimization protocol shares most of its hyper-parameters
with the synthetic MNIST case. The main variation is a different grid of
learning rates, fixed at $[5\cdot 10^{-1},2\cdot
10^{-1},10^{-1},10^{-2},10^{-3},10^{-4}]$.

We report mean and standard deviation of log-AUTC and test accuracy across two
repetitions of the experiments of synthetic MNIST, and three repetitions on
natural MNIST.

###  B.4 ResNet-18 on Stanford Dogs

#### Optimization

Across all the experiments, the learning rate is equal to $1.28\cdot 10^{-1}$
at the first iteration. We then divide it by a factor of $10$ every time we
reach a plateau of the validation accuracy. All the models are trained until
we reach the plateau for the smallest learning rate considered, which is
$1.28\cdot 10^{-3}$. In all experiments, we observed no improvement of the
validation accuracy after the plateau at learning rate $1.28\cdot 10^{-2}$.

##  Appendix C Theoretical Analysis of Linear Models with Unnecessary Input
Dimensions

In this section, we analyze linear, shallow networks trained with the square
loss. In C.1, we introduce the theoretical analysis and in C.2, we report
experiments to illustrate the theoretical results.

###  C.1 Pseudo-inverse solution for linear, shallow networks

We use $(X,Y)$ to denote a dataset where
$X=[\mathbf{x}_{1}\cdots\mathbf{x}_{n}]\in\mathbb{R}^{p\times n}$ contains $n$
independent observations of $p$ uncorrelated features, and
$Y=[\mathbf{y}_{1}\cdots\mathbf{y}_{n}]\in\mathbb{R}^{o\times n}$ denotes the
respective ground-truth output. We define $p$ as the minimal dimensionality.
We aim at estimating the function $f$, such that, for every example
$(\mathbf{x}_{i},\mathbf{y}_{i})$, $\mathbf{y}_{i}=f(\mathbf{{x}}_{i})$ holds
approximately. The choice of a linear network
$\hat{f}(\mathbf{x})=W\mathbf{x}$, with $W\in\mathbb{R}^{o\times p}$ and the
square loss as cost function assures that, even for $p>n$ (overparameterized
case), optimization through gradient descent leads to a unique solution that
corresponds, among all, to the one with minimum norm, namely the pseudo-
inverse [24]:

$W^{+}=Y(X^{\top}X)^{-1}X^{\top},\text{ with }p>n.$ (1)

In the following, we introduce the theoretical solution to the linear model
when the dataset contains _task-related_ , _task-unrelated_ and _task-
related/unrelated_ dimensions. We assume that the model operates in the
overparameterized regime, $p>n$, which is the most common in practice.

#### Task-related dimensions

We assume that the unnecessary _task-related_ dimensions come from a linear
transformation $T\in\mathbb{R}^{d\times p}$ of the vector of $p$ minimal
dimensions. Thus, the dataset with unnecessary dimensions is the result of the
transformation $F=[\mathbb{I}_{p}^{\top}\ \
T^{\top}]^{\top}\in\mathbb{R}^{(p+d)\times p}$, where $\mathbb{I}_{p}$ denotes
the identity matrix of size $p$. The pseudo-inverse solution of the linear
model in Eq. (1) becomes the following:

${W}^{+}=Y(X^{\top}F^{\top}FX)^{-1}X^{\top}F^{\top}.$ (2)

We further assume $F$ to be a tight frame [25],  _ie.,_ there is a unique
scaling factor $a>0$ such that $\|F\mathbf{v}\|^{2}=a\|\mathbf{v}\|^{2}$ holds
for any vector $\mathbf{v}\in\mathbb{R}^{p}$. Then, Eq. (2) corresponds to
${W}^{+}=a^{-1}Y(X^{\top}X)^{-1}X^{\top}F^{\top}$, which is the same as the
linear model learned without _task-related_ dimensions in Eq. (1) (the scaling
constant $a$ compensates with the term at the numerator at prediction). Thus,
_task-related_ dimensions do not affect the linear model if these are based on
a tight frame, otherwise, _task-related_ dimensions may change the solution of
the linear model.

#### Task-unrelated dimensions

For each example $i$, we denote $\mathbf{n}_{i}\in\mathbb{R}^{d}$ a vector of
$d$ _task-unrelated_ dimension independent from
$\mathbf{x}_{i}\in\mathbb{R}^{p}$. Thus, the new input vector to the linear
model is $[\mathbf{x}_{i}^{\top}\ \mathbf{n}_{i}^{\top}]^{\top}$. Intuitively,
if $\mathbf{n}_{i}^{\top}$ is randomly generated, it is expected that as the
number of _task-unrelated_ dimensions increase there will be more overfitting.
Yet, we will show several exceptions to this intuition. To illustrate the
effect of these unnecessary input dimensions, we consider _task-unrelated_
dimensions distributed as a Gaussian, with zero mean, diagonal covariance and
same variance $\sigma^{2}$,  _ie.,_
$(\mathbf{n}_{i})_{\ell}\sim\mathcal{N}(0,\sigma^{2})$,
$\ell=1,\dots,d,i=1,\dots,n$.

We assume that $p+d>n$ (_ie.,_ overparameterization), and then, the pseudo-
inverse solution of the linear model in Eq. (1) becomes the following:

$W^{+}=Y(X^{\top}X+N^{\top}N)^{-1}[X^{\top}\ N^{\top}].$ (3)

From this solution, we can compute the output of the linear model for a given
test sample $[\mathbf{x}_{\rm ts}^{\top}\ \mathbf{n}_{\rm ts}^{\top}]^{\top}$
as in the following:

$\displaystyle W^{+}[\mathbf{x}_{\rm ts}^{\top}\ \mathbf{n}_{\rm
ts}^{\top}]^{\top}$ $\displaystyle=Y(X^{\top}X+N^{\top}N)^{-1}[X^{\top}\
N^{\top}][\mathbf{x}_{\rm ts}^{\top}\ \mathbf{n}_{\rm ts}^{\top}]^{\top}$
$\displaystyle=Y(X^{\top}X+N^{\top}N)^{-1}(X^{\top}\mathbf{x}_{\rm
ts}+N^{\top}\mathbf{n}_{\rm ts})$
$\displaystyle=Y(X^{\top}X+N^{\top}N)^{-1}X^{\top}\mathbf{x}_{\text{ts}}+Y(X^{\top}X+N^{\top}N)^{-1}N^{\top}\mathbf{n}_{\text{ts}}.$
(4)

Note that the first term contains the minimal dimensions and the second term
the _task-unrelated_ dimensions. In the following, we approximate this
expression to a more interpretable one.

First, we develop the last product of the second term,  _ie.,_
$N^{\top}\mathbf{n}_{\rm ts}$, which we write in a more explicit form:

$\displaystyle N^{\top}\mathbf{n}_{\rm ts}$
$\displaystyle=\left[\mathbf{n}_{1}^{\top}\mathbf{n}_{\rm ts}\ \cdots\
\mathbf{n}_{n}^{\top}\mathbf{n}_{\rm ts}\right]^{\top}$ (5)
$\displaystyle=\left[\sum_{\ell=1}^{d}(\mathbf{n}_{1})_{\ell}(\mathbf{n}_{\rm
ts})_{\ell}\ \cdots\ \sum_{\ell=1}^{d}(\mathbf{n}_{n})_{\ell}(\mathbf{n}_{\rm
ts})_{\ell}\right]^{\top}.$ (6)

Recall the assumption that all $(\mathbf{n}_{i})_{\ell}$ and $(\mathbf{n}_{\rm
ts})_{\ell}$ are samples of two independent zero-mean Gaussian random
variables with the same variance $\sigma^{2}$. For very large $d$ values, we
can approximate the average realization of a random variable through its
expected value (law of large numbers). Thus, each sum in Eq. (6) approximates
the expectation value of the product of two independent random variables,
multiplied by a $d$ factor. This can be written as the product of their
expectation values, which is null for zero-mean Gaussian variables,  _ie.,_

$\sum_{\ell=1}^{d}(\mathbf{n}_{i})_{\ell}(\mathbf{n}_{\rm ts})_{\ell}\simeq
0.$ (7)

Therefore, for any test sample, we obtain the following approximation:

$\displaystyle N^{\top}\mathbf{n}_{\rm ts}\simeq{\bf 0}$ (8)

Similarly, for the term $N^{\top}N$ in Eq. (C.1), related to _task-unrelated_
dimensions, for $i\neq j$, we have:

$\displaystyle\mathbf{n}_{i}^{\top}\mathbf{n}_{j}=\sum_{\ell=1}^{d}(\mathbf{n}_{i})_{\ell}(\mathbf{n}_{j})_{\ell}$
$\displaystyle\simeq 0.$ (9)

When $i=j$, the following approximation holds:

$\displaystyle\mathbf{n}_{i}^{\top}\mathbf{n}_{i}=\sum_{\ell=1}^{d}(\mathbf{n}_{i})_{\ell}^{2}$
$\displaystyle\simeq d\sigma^{2}.$ (10)

This is because the expectation value coincides with the variance of the zero-
mean Gaussian variable. Given Eqs. (9) and (10), we obtain the following
approximation:

$\displaystyle N^{\top}N\simeq d\sigma^{2}\mathbb{I}_{n}.$ (11)

Finally, the approximations in Eqs. (8) and (11) lead to the following
approximation of the prediction of the linear network for large $d$:

$W^{+}[\mathbf{x}_{\rm ts}^{\top}\ \mathbf{n}_{\rm ts}^{\top}]^{\top}\simeq
Y(X^{\top}X+d\sigma^{2}\mathbb{I}_{n})^{-1}X^{\top}\mathbf{x}_{\rm ts},$ (12)

where $[\mathbf{x}_{\rm ts}^{\top}\ \mathbf{n}_{\rm ts}^{\top}]^{\top}$ is an
arbitrary test sample.

We can observe by analysing Eq. (12) that $d\sigma^{2}\mathbb{I}_{n}$
corresponds to the Tikhonov regularization term, with regularization parameter
$\lambda=d\sigma^{2}$. Thus, a large number of _task-unrelated_ dimensions
following a Gaussian distribution leads to a network trained on the dataset
without _task-unrelated_ dimensions, biased towards small $\ell_{2}$ norm
weights. This intrinsic regularization term usually will not have a positive
effect in the test accuracy, as we do not have control to adjust the strength
of the regularizer  _ie.,_ $d\sigma^{2}$ is given by the dataset. It may lead
to underfitting with respect to the minimal dimensions of the dataset, or
equivalently, to overfitting to the dataset with the unnecessary dimensions.
Yet, this regularizer may have positive effects in some situations. In C.2, we
introduce a regression problem with corrupted labels,  _ie.,_
$y_{i}=f(x_{i})+\varepsilon_{i}$, that can benefit from the regularization
effect of _task-unrelated_ dimensions.

#### Combining task-related and task-unrelated dimensions

We now assume that a percentage $\nu\in[0,1]$ of unnecessary input dimensions
are _task-related_ and the rest are _task-unrelated_. We borrow the results
introduced above for each of these two types of unnecessary dimensions, and
combine them.

Let $N=[\mathbf{n}_{1}\cdots\mathbf{n}_{n}]\in\mathbb{R}^{d(1-\nu)\times n}$
be the matrix of _task-unrelated_ dimensions, and $TX=[T\mathbf{x}_{i}\cdots
T\mathbf{x}_{n}]\in\mathbb{R}^{d\nu\times n}$ be the _task-related_
dimensions, in which $T\in\mathbb{R}^{d\nu\times p}$ is a generic linear
transformation. Thus, the input samples of the training set in matrix form is
equal to $[X^{\top}\ N^{\top}\ (TX)^{\top}]^{\top}$, which is equivalent to
the concatenation of these terms.

We can express the input matrix using the frame formalism as

$\begin{pmatrix}\begin{array}[]{c}X\\\ N\\\ TX\\\
\end{array}\end{pmatrix}=F\begin{pmatrix}\begin{array}[]{c}X\\\ N\\\
\end{array}\end{pmatrix},$ (13)

$\text{ where
}F=\begin{pmatrix}\begin{array}[]{cc}\mathbb{I}_{p}&\mathbf{0}_{p\times
d(1-\nu)}\\\ \mathbf{0}_{d(1-\nu)\times p}&\mathbb{I}_{d(1-\nu)}\\\
T&\mathbf{0}_{d\nu\times d(1-\nu)}\\\ \end{array}\end{pmatrix},$ (14)

and $\mathbf{0}$ denotes the matrix with null entries and dimensions as
specified in the subscripts. Recall that Eq. (2) introduced the solution of a
linear model when the input is multiplied by a frame. Thus, we develop Eq. (2)
in order to obtain a more interpretable approximation that provides insights
about the effect of _task-related_ and _unrelated_ dimensions.

We first evaluate the term $F^{\top}F$ from Eq. (2) with the frame in Eq. 14,
which yields the following:

$F^{\top}F=\begin{pmatrix}\begin{array}[]{c|c}\mathbb{I}_{p}+T^{\top}T&\mathbf{0}_{p\times
d(1-\nu)}\\\ \hline\cr\mathbf{0}_{d(1-\nu)\times
p}&\mathbb{I}_{d(1-\nu)}\end{array}\end{pmatrix},$ (15)

and it is invertible. By substituting this term in the pseudo-inverse solution
of Eq. (2), we obtain

$\displaystyle W^{+}$ $\displaystyle=Y\left(\left[X^{\top}\
N^{\top}\right]F^{\top}F\begin{bmatrix}X\\\
N\end{bmatrix}\right)^{-1}\left[X^{\top}N^{\top}\right]F^{\top}$
$\displaystyle=Y\left(X^{\top}\left(\mathbb{I}_{p}+T^{\top}T\right)X+N^{\top}N\right)^{-1}\left[X^{\top}\left[\mathbb{I}_{p}\
T^{\top}\right]\ N^{\top}\right].$ (16)

This result does not rely on any assumption on the distribution of the _task-
unrelated_ dimensions, neither on a specific form of the linear transformation
$T$. To get a clearer picture of the effect of unnecessary input dimensions,
in the following we make three assumptions: (i) the _task-related_ dimensions
are generated by repeating $k$ times the minimal set of dimensions, such that
$k=(\nu d)/p$; (ii) the vector components for the _task-unrelated_ dimensions
are drawn from zero-mean Gaussian distributions sharing the same variance
value; and (iii) $d(1-\nu)$ number of _task-unrelated_ dimensions is large.

Given assumption (i), $T$ is a tight frame and the quantity $T^{\top}T$
corresponds to the identity in $\mathbb{R}^{p}$. Also, the term
$\mathbb{I}_{p}+T^{\top}T$ is equivalent to $(k+1)\mathbb{I}_{p}$ because the
minimal set of dimensions are repeated $k$ times.

The solution in Eq. (C.1) applied on a new test sample $\left[\mathbf{x}_{\rm
ts}^{\top}\ \mathbf{n}_{\rm ts}^{\top}\ (T\mathbf{x}_{\rm
ts})^{\top}\right]^{\top}$, becomes to the following expression:

$\displaystyle W^{+}$ $\displaystyle\left[\mathbf{x}_{\rm ts}^{\top}\
\mathbf{n}_{\rm ts}^{\top}\ (T\mathbf{x}_{\rm ts})^{\top}\right]^{\top}=$
$\displaystyle
Y\left((k+1)X^{\top}X+N^{\top}N\right)^{-1}\left((k+1)X^{\top}\mathbf{x}_{\rm
ts}+N^{\top}\mathbf{n}_{\rm ts}\right).$ (17)

Using assumptions (ii) and (iii), we leverage on the law of large numbers as
in the _task-unrelated_ case introduced before. Here, the sum over the _task-
unrelated_ components consists of $d(1-\nu)$ terms, and the following two
approximations holds: $N^{\top}\mathbf{n}_{\rm ts}\simeq{\bf 0}$ and
$N^{\top}N\simeq d(1-\nu)\sigma^{2}\mathbb{I}_{n}$. Thus, the prediction for a
test sample corresponds to

$\displaystyle W^{+}$ $\displaystyle\left[\mathbf{x}_{\rm ts}^{\top}\
\mathbf{n}_{\rm ts}^{\top}\ (T\mathbf{x}_{\rm ts})^{\top}\right]^{\top}\simeq$
$\displaystyle
Y\left((k+1)X^{\top}X+d(1-\nu)\sigma^{2}\mathbb{I}_{n}\right)^{-1}X^{\top}\mathbf{x}_{\rm
ts}(k+1)=$ $\displaystyle
Y\left(X^{\top}X+\frac{pd(1-\nu)}{d\nu+p}\sigma^{2}\mathbb{I}_{n}\right)^{-1}X^{\top}\mathbf{x}_{\rm
ts}.$ (18)

Observe that this expression is again the pseudo-inverse solution with
Tikhonov regularization as for the _task-unrelated_ dimensions in Eq. (12),
except that here regularization parameter is equal to
$\frac{pd(1-\nu)}{d\nu+p}\sigma^{2}$. The regularizer term depends on the
ratio between the number of _task-unrelated_ and _task-related_ dimensions,
$\nu$. Note that as the number of _task-related_ dimensions increases, in the
limit of $\nu$ tending to 1, the problem is equivalent to the one formulated
for the minimal dimensions, with null contribution from the unnecessary input
dimensions as the regularizer parameter would tend to $0$. Thus, the number of
_task-related_ dimensions help to adjust the regularization effect of the
_task-unrelated_ dimensions, and hence, it can alleviate its negative effects.

###  C.2 Regression with corrupted output

We now analyze a problem in practice that follows up from the theoretical
analysis in the previous section, and that serves to show that the
regularization effect of the unnecessary input dimensions can be helpful in
some cases.

We generate an overparameterized regression dataset, with $p=10$ minimal
dimensions, $o=4$ output dimensions, and $d=500$ unnecessary _task-unrelated_
dimensions. The $p$ minimal input dimensions are drawn from
$\mathcal{N}(0,\sigma_{\text{input}}^{2})$, zero-mean Gaussian distribution
with a shared variance value. The number of training examples across
experiments is $n=7$. The corrupted output for sample $i$ is

$\mathbf{y}_{i}={W}^{*}\mathbf{x}_{i}+\varepsilon,$ (19)

with zero-mean Gaussian distributed random variable
$\varepsilon\sim\mathcal{N}(0,\sigma_{\rm output}^{2})$.

We compare three different baselines. We refer to the “ _with task-unrelated_
solution” as the solution computed from the samples with _task-unrelated_
input dimensions,  _ie.,_ $\left[\mathbf{x}_{i}^{\top}\
\mathbf{n}_{i}^{\top}\right]^{\top}$, using Eq. (12). When there is no _task-
unrelated_ dimensions, we refer to the “ _without task-unrelated_ solution”,
as in Eq. (1). Finally, we also compute the _Tikhonov_ regularized solution
with $\lambda=d\sigma_{\rm input}^{2}$ regularization parameter, on the
dataset without unnecessary input dimensions. The prediction errors for the
three baselines correspond respectively to the following:

$\displaystyle\text{Error({with task-unrelated})}=$
$\displaystyle\left\langle\left\|Y(X^{\top}X+N^{\top}N)^{-1}[X^{\top}\
N^{\top}][\mathbf{x}_{\rm ts}^{\top}\ \mathbf{n}_{\rm
ts}^{\top}]^{\top}-\mathbf{y}_{\rm ts}\right\|^{2}_{2}\right\rangle,$ (20)
$\displaystyle\text{Error({w/o task-unrelated})}=$
$\displaystyle\left\langle\left\|Y(X^{\top}X)^{-1}X^{\top}\mathbf{x}_{\rm
ts}-\mathbf{y}_{\rm ts}\right\|^{2}_{2}\right\rangle,$ (21)
$\displaystyle\text{Error({Tikhonov})}=$
$\displaystyle\left\langle\left\|Y(X^{\top}X+\lambda\mathbb{I}_{n})^{-1}X^{\top}\mathbf{x}_{\rm
ts}-\mathbf{y}_{\rm ts}\right\|^{2}_{2}\right\rangle,$ (22)

where the sample average $\langle\ \cdot\ \rangle$ is computed on the test
examples.

Figure 2: Regression with corrupted output. Left: prediction error when there
are no unnecessary dimensions, as function of the output corruption. Right:
analysis of prediction error as function of the variance of the _task-
unrelated_ dimensions/ regularization (with regularization value
$\lambda=d\sigma_{input}^{2}$). On the $y$-axis, difference between test
errors of either the solution “ _with task-unrelated_ ” or regularized, and “
_without task-unrelated_ solution”.

In Fig. 2 on the left, we report the test error computed as in Eq. 21. As
expected, as the corruption in the ground-truth output increases, we observe
consistently higher test errors. On the right of Fig. 2, we quantify the
difference between Eq. (20) and Eq.(21), as the variance of _task-unrelated_
dimensions increases. Each blue curve is related to a different level of
output corruption. For small values of $\sigma_{\text{input}}$, _task-
unrelated_ dimensions do not have any effect on the test error. As
$\sigma_{\rm input}$ increases, _task-unrelated_ dimensions harm the solution
for very small output corruption, while gradually benefiting the prediction as
the output corruption increases due to its regularization effect.

The white triangles on the left of Fig. 2 correspond to the difference between
Eq. (20) and Eq. (22). These points follow each of the blue curves, showing
that the assumptions and approximations we made are reasonable.

Overall, these results depict the effect of _task-unrelated_ dimensions, which
can effectively help to improve the test accuracy when the ground-truth output
is corrupted.

##  Appendix D Supplemental Results

###  D.1 MLP on Different Distributions of Noise

#### Dataset and Network

To further test the generality of previous results on data distributions that
are not linearly separable, we use a mixture of Gaussians to generate non-
linearly separable datasets for binary classification. Each class consists of
three multivariate Gaussians of dimensions $p=30$. As we fix a class, we
generate a sample by randomly selecting, among the three, one distribution
from which we draw the minimal dimensions. We evaluate the MLP with ReLU and
soft-max with cross-entropy loss because among the different variants it is
the only well suited to fit non-linearly separable data. We evaluate the
effect of the variance of the Gaussian distribution to generate the
unnecessary dimensions, and we also evaluate two other noise distributions,
namely, Gaussian noise with $\Sigma_{ii}=1,\ \forall i$, with
$\Sigma_{ij}=0.5$, $\forall i\neq j$, and salt and pepper noise, where each
vector component can assume value (0, or $u$), based on a Bernoullian
distribution on $\\{-1,1\\}$.

#### Results

Figure 3: MLP with ReLU trained with cross entropy loss on non-linearly
separable binary classification dataset. The _task-unrelated_ dimensions are
extracted from different distributions.

In Figure 3, we show the data efficiency of MLP with ReLU trained with cross
entropy loss on non-linearly separable datasets. On the left of the quadrant,
we report different distributions of the _task-unrelated_ dimensions: Gaussian
noise with different $\boldsymbol{\sigma}$ (corresponding to multiplicative
factor applied on the identical covariance matrix), Gaussian noise with non-
diagonal covariance matrix and salt and pepper noise. The amount of _task-
unrelated_ dimensions is reported through the colored bar (with gradient). We
observe that, similarly to previous results in the linearly separable dataset
(Figure 1B), _task-unrelated_ dimensions harm data efficiency. Also, as
expected, data efficiency deteriorates as the variance of Gaussian noise
increases. The combinations of _task-related/unrelated_ dimensions alleviates
the detrimental effect of _task-unrelated_ dimensions.

###  D.2 Supplementary Results on synthetic MNIST

Figure 4: Test accuracy for different number of training examples for the MLP
with ReLU trained with cross entropy loss (top row) and CNNs (bottom row)
across the three scenarios on synthetic MNIST.

In Figure 4, we report the test accuracy of the MLP and CNN, trained on
synthetic MNIST, for the three types of unnecessary dimensions and the
different amount of dimensions. These curves are used to compute the log-AUTC
in Figure 1C.

###  D.3 Supplemental Results on natural MNIST

Figure 5: Top left: Test accuracy for the highest amount of _task-unrelated_
dimensions, with the largest amount of training examples. Bottom left: log
AUTC with architectures with global average pooling. On the right, normalized
maximum activations for the two networks $r=4.5$ and $r=1$ in Figure 1D.

On the top left of Figure 5, we report the CNN’s test accuracy obtained with
different filters sizes and max-pooling sizes when the amount of unnecessary
dimensions, as the amount of training examples per class ($n_{tr}=1000$) are
the largest we tested. All the versions of the CNN achieve almost perfect
generalization, emphasizing that data efficiency’s gaps due to unnecessary
input dimensions are hard to observe when abundant amounts of examples are
available.

On the bottom left of Figure 5, we show the log AUTC values for networks
trained on Natural MNIST with a global average pooling before the fully
connected layers. The global average pooling yields fully connected layers
that have the same amount of trainable parameters independently of the
receptive field sizes. Results show that the CNN with the largest receptive
fields size, $r=9$, leads to the highest data efficiency among all the
different $r$ we tested. CNNs with the smallest receptive field size, $r=1$,
heavily suffer from the unnecessary input dimensions. Despite the reduction of
free parameters caused by the global pooling, depending on the receptive field
size, the data efficiency of the network could dramatically drop due to _task-
unrelated_ input dimensions.

#### Neural Mechanisms to Discard Object’s Background in CNNs

We investigate the networks’ mechanisms that facilitate discarding the
unnecessary dimensions. To do so, we provide evidence that supports the
hypothesis that efficient CNNs have kernels tuned to discard the object’s
background.

To compute the activations of a network, we extract at each layer the neural
activity of $1000$ test samples after the non-linearity and the max-pooling
(if present). For each image and at every layer, we compute the maximum
activation across spatial dimensions and filters, which we use to normalize
the representation of the image at that layer. We grouped the representation
values at each layer in five sets, depending on their distance from the center
(regions). We store the maximum normalized value for each region.

In Figure 5, we report the distribution of the maximum normalized values for
the five regions (left to right corresponds to the furthest to the closest
region to the center). We report results for the most (in orange) and least
(in green) data efficient networks without global average pooling
(respectively $r=4.5$ and $r=1$). Also, we compare the activations of the two
networks when trained on the smallest $n_{tr}=20$ (dark) and largest
$n_{tr}=1000$ (light) sets, for edge digit / edge image $=11\%$.

When the network is trained with more examples (light violin plots), the
neurons respond more to the object compared to the background. Yet, when the
networks are trained with few examples (dark violin plots), the differences in
terms of neural activity are minor between the object and its background. Note
that this phenomenon is much more pronounced for the most data efficient
architecture ($r=4.5$). These results suggest that the data efficiency of the
network is driven by the emergence of kernels that can detect the object while
not responding to the background.