summaries: This paper proposes a method for assigning values to each datum.  For example, data with incorrect labels, data of low quality, or data from off-the-target distributions should be assigned low values. The main method involves training a neural network to predict the value for each training datum. The reward is based on performance on a small validation set. To make  gradient flow through data sampling, REINFORCE is used. The method is evaluated on multiple datasets. The results show that the proposed method outperforms a number of existing approaches.

summaries: This paper proposes a meta learning approach based on data valuation for reinforcement learning tasks. The core idea is to train a second network (the data value estimator) in conjunction to a regular predictor network. The predictor is then trained with samples chosen via the data value estimation. The authors motivate this construction with the goal to filter out unreliable and corrupted data.

abstractText: Quantifying the value of data is a fundamental problem in machine learning. Data valuation has multiple important use cases: (1) building insights about the learning task, (2) domain adaptation, (3) corrupted sample discovery, and (4) robust learning. To adaptively learn data values jointly with the target task predictor model, we propose a meta learning framework which we name Data Valuation using Reinforcement Learning (DVRL). We employ a data value estimator (modeled by a deep neural network) to learn how likely each datum is used in training of the predictor model. We train the data value estimator using a reinforcement signal of the reward obtained on a small validation set that reflects performance on the target task. We demonstrate that DVRL yields superior data value estimates compared to alternative methods across different types of datasets and in a diverse set of application scenarios. The corrupted sample discovery performance of DVRL is close to optimal in many regimes (i.e. as if the noisy samples were known apriori), and for domain adaptation and robust learning DVRL significantly outperforms state-of-the-art by 14.6% and 10.8%, respectively.

authors:
Tianqi Chen
Carlos Guestrin

title: Xgboost: A scalable tree boosting system

venue: In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,

authors:
Sungjoon Choi
Sanghoon Hong
Sungbin Lim

title: Choicenet: Robust learning by revealing output correlations

venue: arXiv preprint arXiv:1805.06431,

authors:
Hasan Ferdowsi
Sarangapani Jagannathan
Maciej Zawodniok

title: An online outlier identification and removal scheme for improving fault detection performance

venue: IEEE Transactions on Neural Networks and Learning Systems,

authors:
B. Frenay
M. Verleysen

title: Classification in the presence of label noise: A survey

authors:
Yaroslav Ganin
Evgeniya Ustinova
Hana Ajakan
Pascal Germain
Hugo Larochelle
François Laviolette
Mario Marchand
Victor Lempitsky

title: Domain-adversarial training of neural networks

venue: The Journal of Machine Learning Research,

authors:
Amirata Ghorbani
James Zou

title: Data shapley: Equitable valuation of data for machine learning

venue: In International Conference on Machine Learning,

authors:
Xavier Glorot
Antoine Bordes
Yoshua Bengio

title: Domain adaptation for large-scale sentiment classification: A deep learning approach

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

authors:
Dan Hendrycks
Mantas Mazeika
Duncan Wilson
Kevin Gimpel

title: Using trusted data to train deep networks on labels corrupted by severe noise

venue: In Advances in Neural Information Processing Systems,

authors:
Joel Hestness
Sharan Narang
Newsha Ardalani
Gregory F. Diamos
Heewoo Jun
Hassan Kianinejad
Md. Mostofa Ali Patwary
Yang Yang
Yanqi Zhou

title: Deep learning scaling is predictable, empirically

authors:
Eric Jang
Shixiang Gu
Ben Poole

title: Categorical reparameterization with gumbel-softmax

venue: In International Conference on Learning Representations,

authors:
Lu Jiang
Zhengyuan Zhou
Thomas Leung
Li-Jia Li
Li Fei-Fei

title: Mentornet: Learning datadriven curriculum for very deep neural networks on corrupted labels

authors:
Guolin Ke
Qi Meng
Thomas Finley
Taifeng Wang
Wei Chen
Weidong Ma
Qiwei Ye
TieYan Liu

title: Lightgbm: A highly efficient gradient boosting decision tree

authors:
Pang Wei Koh
Percy Liang

title: Understanding black-box predictions via influence functions

authors:
Jan M Köhler
Maximilian Autenrieth
William H Beluch

title: Uncertainty based detection and relabeling of noisy image labels

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops,

authors:
Junnan Li
Yongkang Wong
Qi Zhao
Mohan S Kankanhalli

title: Learning to learn from noisy labeled data

authors:
Scott M Lundberg
Su-In Lee

title: A unified approach to interpreting model predictions

authors:
Sam McCandlish
Jared Kaplan
Dario Amodei
OpenAI Dota Team

title: An empirical model of large-batch training

venue: arXiv preprint arXiv:1812.06162,

authors:
Maryam M Najafabadi
Flavio Villanustre
Taghi M Khoshgoftaar
Naeem Seliya
Randall Wald
Edin Muharemagic

title: Deep learning applications and challenges in big data analytics

venue: Journal of Big Data,

authors:
Jiquan Ngiam
Daiyi Peng
Vijay Vasudevan
Simon Kornblith
Quoc V Le
Ruoming Pang

title: Domain adaptive transfer learning with specialist models

venue: arXiv preprint arXiv:1811.07056,

authors:
Mengye Ren
Wenyuan Zeng
Bin Yang
Raquel Urtasun

title: Learning to reweight examples for robust deep learning

authors:
Danilo Jimenez Rezende
Shakir Mohamed
Daan Wierstra

title: Stochastic backpropagation and approximate inference in deep generative models

title: A value for n-person games

venue: Contributions to the Theory of Games,

authors:
Yanyao Shen
Sujay Sanghavi

title: Learning with bad training data via iterative trimmed loss minimization

authors:
Jun Shu
Qi Xie
Lixuan Yi
Qian Zhao
Sanping Zhou
Zongben Xu
Deyu Meng

title: Meta-weightnet: Learning an explicit mapping for sample weighting

authors:
Christian Szegedy
Vincent Vanhoucke
Sergey Ioffe
Jon Shlens
Zbigniew Wojna

title: Rethinking the inception architecture for computer vision

authors:
Mariya Toneva
Alessandro Sordoni
Remi Tachet des Combes
Adam Trischler
Yoshua Bengio
Geoffrey J. Gordon

title: An empirical study of example forgetting during deep neural network learning

authors:
Eric Tzeng
Judy Hoffman
Kate Saenko
Trevor Darrell

title: Adversarial discriminative domain adaptation

title: Simple statistical gradient-following algorithms for connectionist reinforcement learning

venue: Machine Learning,

authors:
Cheng Xue
Qi Dou
Xueying Shi
Hao Chen
Pheng Ann Heng

title: Robust learning at noisy labeled medical images: Applied to skin lesion classification

authors:
Sergey Zagoruyko
Nikos Komodakis

title: Wide residual networks

venue: arXiv preprint arXiv:1605.07146,

authors:
Linchao Zhu
Sercan O. Arik
Yi Yang
Tomas Pfister

title: Learning to Transfer Learn

venue: arXiv preprint arXiv:1908.11406,

heading: 1 INTRODUCTION

text:
Data is an essential ingredient in machine learning. Machine learning models are well-known to improve when trained on large-scale and high-quality datasets (Hestness et al., 2017; Najafabadi et al., 2015). However, collecting such large-scale and high-quality datasets is costly and challenging. One needs to determine the samples that are most useful for the target task and then label them correctly. Recent work (Toneva et al., 2019) suggests that not all samples are equally useful for training, particularly in the case of deep neural networks. In some cases, similar or even higher test performance can be obtained by removing a significant portion of training data, i.e. low-quality or noisy data may be harmful (Ferdowsi et al., 2013; Frenay & Verleysen, 2014). There are also some scenarios where train-test mismatch cannot be avoided because the training dataset only exists for a different domain. Different methods (Ngiam et al., 2018; Zhu et al., 2019) have demonstrated the importance of carefully selecting the most relevant samples to minimize this mismatch.
Accurately quantifying the value of data has a great potential for improving model performance for real-world training datasets which commonly contain incorrect labels, and where the input samples differ in relatedness, sample quality, and usefulness for the target task. Instead of treating all data samples equally, lower priority can be assigned for a datum to obtain a higher performance model – for example in the following scenarios:
1. Incorrect label (e.g. human labeling errors). 2. Input comes from a different distribution (e.g. different location or time). 3. Input is noisy or low quality (e.g. noisy capturing hardware). 4. Usefulness for target task (label is very common in the training dataset but not as common in the
testing dataset).
In addition to improving performance in such scenarios, data valuation also enables many new use cases. It can suggest better practices for data collection, e.g. what kinds of additional data would the model benefit the most from. For organizations that sell data, it determines the correct value-based pricing of data subsets. Finally, it enables new possibilities for constructing very large-scale training datasets in a much cheaper way, e.g. by searching the Internet using the labels and filtering away less valuable data.
How does one evaluate the value of a single datum? This is a crucial and challenging question. It is straightforward to address at the full dataset granularity: one could naively train a model on the entire dataset and use its prediction performance as the value. However, evaluating the value of each datum is far more difficult, especially for complex models such as deep neural networks that are trained on large-scale datasets. In this paper, we propose a meta learning-based data valuation method which we name Data Valuation using Reinforcement Learning (DVRL). Our method integrates data valuation with the training of the target task predictor model. DVRL determines a reward by quantifying the performance on a small validation set, and uses it as a reinforcement signal to learn the likelihood of each datum being using in training of the predictor model. In a wide range of use cases, including domain adaptation, corrupted sample discovery and robust learning, we demonstrate significant improvements compared to permutation-based strategies (such as Leave-one-out and Influence Function (Koh & Liang, 2017)) and game theory-based strategies (such as Data Shapley (Ghorbani & Zou, 2019)). The main contributions can be summarized as follows:
1. We propose a novel meta learning framework for data valuation that is jointly optimized with the target task predictor model.
2. We demonstrate multiple use cases of the proposed data valuation framework and show DVRL significantly outperforms competing methods on many image, tabular and language datasets.
3. Unlike previous methods, DVRL is scalable to large datasets and complex models, and its computational complexity is not directly dependent on the size of the training set.

heading: 2 RELATED WORK

text:
Data valuation: A commonly-used method for data valuation is leave-one-out (LOO). It quantifies the performance difference when a specific sample is removed and assigns it as that sample’s data value. The computational cost is a major concern for LOO – it scales linearly with the number of training samples which means its cost becomes prohibitively high for large-scale datasets and complex models. In addition, there are fundamental limitations in the approximation. For example, if there are two exactly equivalent samples, LOO underestimates the value of that sample even though that sample may be very important. The method of Influence Function (Koh & Liang, 2017) was proposed to approximate LOO in a computationally-efficient manner. It uses the gradient of the loss function with small perturbations to estimate the data value. In order to compute the gradient, Hessian values are needed; however these are prohibitively expensive to compute for neural networks. Approximations for Hessian computations are possible, although they generally result in performance limitations. From data quality assessment perspective, the method of Influence Function inherits the major limitations of LOO.
Data Shapley (Ghorbani & Zou, 2019) is another relevant work. Shapley values are motivated by game theory (Shapley, 1953) and are commonly used in feature attribution problems such as relating predictions to input features (Lundberg & Lee, 2017). For Data Shapley, the prediction performance of all possible subsets is considered and the marginal performance improvement is used as the data value. The computational complexity for computing the exact Shapley value is exponential with the number of samples. Therefore, Monte Carlo sampling and gradient-based estimation are used to approximate them. However, even with these approximations, the computational complexity still remains high (indeed much higher than LOO) due to re-training for each test combination. In addition, the approximations may result in fundamental limitations in data valuation performance – e.g. with Monte Carlo approximation, the ratio of tested combinations compared to all possible combinations decreases exponentially. Moreover, in all the aforementioned methods data valuation is decoupled from predictor model training, which limits the performance due to lack of joint optimization.
Meta learning-based adaptive learning: There are relevant studies that utilize meta learning for adaptive weight assignment while training for various use cases such as robust learning, domain adaptation, and corrupted sample discovery. ChoiceNet (Choi et al., 2018) explicitly models output distributions and uses the correlations of the output to improve robustness. Xue et al. (2019) estimates uncertainty of predictions to identify the corrupted samples. Li et al. (2019) combines meta learning with standard stochastic gradient update with generated synthetic noise for robust learning. Shen & Sanghavi (2019) alternates the processes of selecting the samples with low loss and model training to improve robustness. Shu et al. (2019) uses neural networks to model the relationship between current loss and the corresponding sample weights, and utilizes a meta-learning
framework for robust weight assignment. Köhler et al. (2019) estimates the uncertainty to discover the noisy labeled data and relabels mislabeled samples to improve the prediction performance of the predictor model. Gold Loss Correction (Hendrycks et al., 2018) uses a clean validation set to recover the label corruption matrix to re-train the predictor model with corrected labels. Learning to Reweight (Ren et al., 2018) proposes a single gradient descent step guided with validation set performance to reweight the training batch. Domain Adaptive Transfer Learning (Ngiam et al., 2018) introduces importance weights (based on the prior label distribution match) to scale the training samples for transfer learning. MentorNet (Jiang et al., 2018) proposes a curriculum learning framework that learns the order of mini-batch for training of the corresponding predictor model. Our method, DVRL, differs from the aforementioned as it directly models the value of the data using learnable neural networks (which we refer to as a data value estimator). To train the data value estimator, we use reinforcement learning with a sampling process. DVRL is model-agnostic and even applicable to non-differentiable target objectives. Learning is jointly performed for the data value estimator and the corresponding predictor model, yielding superior results in all of the use cases we consider.

heading: 3 PROPOSED METHOD

text:
Framework: Let us denote the training dataset asD = {(xi, yi)}Ni=1 ∼ P where xi ∈ X is a feature vector in the d-dimensional feature space X , e.g. Rd, and yi ∈ Y is a corresponding label in the label space Y , e.g. ∆[0, 1]c for classification where c is the number of classes and ∆ is the simplex. We consider a disjoint testing dataset Dt = {(xtj , ytj)}Mj=1 ∼ Pt where the target distribution Pt does not need to be the same with the training distribution P . We assume an availability of a (often small1) validation dataset Dv = {(xvk, yvk)}Lk=1 ∼ Pt that comes from the target distribution Pt. The DVRL method (overview in Fig. 1) consists of two learnable functions: (1) the target task predictor model fθ, (2) data value estimator model hφ. The predictor model fθ : X → Y is trained to minimize a certain weighted loss function Lf (e.g. Mean Squared Error (MSE) for regression or cross entropy for classification) on training set D:
fθ = arg min f̂∈F
1
N N∑ i=1 hφ(xi, yi) · Lf (f̂(xi), yi). (1)
fθ can be any trainable function with parameters θ, such as a neural network. The data value estimator model hφ : X · Y → [0, 1], on the other hand, is optimized to output weights that determine
1We provide empirical results that how small the validation set can be in Section 4.5.
the distribution of selection likelihood of the samples to train the predictor model fθ. We formulate the corresponding optimization problem as:
min hφ
E(xv,yv)∼P t [ Lh(fθ(xv), yv) ] s.t. fθ = arg minf̂∈F E(x,y)∼P [ hφ(x, y) · Lf (f̂(x), y)
] (2) where hφ(x, y) represents value of the training sample (x, y). The data value estimator is also a trainable function, such as a neural network. Similar to Lf , we use MSE or cross entropy for Lh. Training: To encourage exploration based on uncertainty, we model training sample selection stochastically. Let w = hφ(x, y) denote the probability that (x, y) is used to train the predictor model fθ. hφ(D) = {hφ(xi, yi)}Ni=1 is the probability distribution for inclusion of each training sample. s ∈ {0, 1}N is a binary vector that represents the selected samples. If si = 1/0, (xi, yi) is selected/not selected for training the predictor model. πφ(D, s) = ∏N i=1 [ hφ(xi, yi)si · (1 −
hφ(xi, yi))1−si ]
is the probability that certain selection vector s is selected based on hφ(D). We assign the outputs of the data value estimator model, w = hφ(x, y), as the data values. We can use the data values to rank the dataset samples (e.g. to determine a subset of the training dataset) and to do sample-adaptive training (e.g. for domain adaptation).
The predictor model can be trained using standard stochastic gradient descent because it is differentiable with respect to the input. However, gradient descent-based optimization cannot be used for the data value estimator because the sampling process is non-differentiable. There are multiple ways to handle the non-differentiable optimization bottleneck, such as Gumbel-softmax (Jang et al., 2017) or stochastic back-propagation (Rezende et al., 2014). In this paper, we consider reinforcement learning instead, which directly encourages exploration of the policy towards the optimal solution of Eq. (2). We use the REINFORCE algorithm (Williams, 1992) to optimize the policy gradients, with the rewards obtained from a small validation set that approximates performance on the target task. For the loss function l̂(φ):
l̂(φ) = E(xv,yv)∼P t [ Es∼πφ(D,·) [ Lh(fθ(xv), yv) ]] = ∫ P t(xv)
[ ∑ s∈[0,1]N πφ(D, s) · [ Lh(fθ(xv), yv) ]] dxv,
we directly compute the gradient∇φ l̂(φ) as: ∇φ l̂(φ) = ∫ P t(xv) [ ∑ s∈[0,1]N ∇φπφ(D, s) · [ Lh(fθ(xv), yv) ]] dxv
= ∫ P t(xv) [ ∑ s∈[0,1]N ∇φ log(πφ(D, s)) · πφ(D, s) · [ Lh(fθ(xv), yv) ]] dxv
= E(xv,yv)∼P t [ Es∼πφ(D,·) [ Lh(fθ(xv), yv) ] ∇φ log(πφ(D, s)) ] ,
where∇φ log(πφ(D, s)) is
∇φ log(πφ(D, s)) = ∇φ N∑ i=1 log [ hφ(xi, yi)si · (1− hφ(xi, yi))1−si ] =
N∑ i=1 si∇φ log [ hφ(xi, yi) ] + (1− si)∇φ log [ (1− hφ(xi, yi)) ] .
To improve the stability of the training, we use the moving average of the previous loss (δ), with a window size (T ), as the baseline for the current loss. The pseudo-code is shown in Algorithm 1.
Computational complexity: DVRL models the mapping between an input and its value with a learnable function. The training time of DVRL is not directly proportional to the dataset size, but rather dominated by the required number of iterations and per-iteration complexity in Algorithm 1. One way to minimize the computational overhead is to use pre-trained models to initialize the
Algorithm 1 Pseudo-code of DVRL training 1: Inputs: Learning rates α, β > 0, mini-batch size Bp, Bs > 0, inner iteration count NI > 0,
moving average window T > 0, training dataset D, validation dataset Dv = {(xvk, yvk)}Lk=1 2: Initialize parameters θ, φ, moving average δ = 0 3: while until convergence do 4: Sample a mini-batch from the entire training dataset: DB = (xj , yj)Bsj=1 ∼ D 5: for j = 1, ..., Bs do 6: Calculate selection probabilities: wj = hφ(xj , yj) 7: Sample selection vector: sj ∼ Ber(wj) 8: for t = 1, ..., NI do 9: Sample a mini-batch (x̃m, ỹm, s̃m) Bp m=1 ∼ (xj , yj , sj) Bs j=1
10: Update the predictor model network parameters θ
θ ← θ − α 1 Bp Bp∑ m=1 s̃m · ∇θLf (fθ(x̃m), ỹm))
11: Update the data value estimator model network parameters φ
φ← φ− β [ 1 L L∑ k=1 [Lh(fθ(xvk), yvk)]− δ ] ∇φ log πφ(DB , (s1, ..., sBs))
12: Update the moving average baseline (δ): δ ← T−1T δ + 1 LT ∑L k=1[Lh(fθ(xvk), yvk)]
predictor networks at each iteration. Unlike alternative methods like Data Shapley, we demonstrate the scalability of DVRL to large-scale datasets such as CIFAR-100, and complex models such as ResNet-32 (He et al., 2016) and WideResNet-28-10 (Zagoruyko & Komodakis, 2016). Instead of being exponential in terms of the dataset size, the training time overhead DVRL is only twice of conventional training. Please see Appendix D for further analysis on learning dynamics of DVRL and Appendix B for additional computational complexity discussions.

heading: 4 EXPERIMENTS

text:
We evaluate data value estimation quality of DVRL on multiple types of dataset and use cases.
Benchmark methods: We consider the following benchmarks: (1) Randomly-assigned values (Random), (2) Leave-one-out (LOO), (3) Data Shapley Value (Data Shapley) (Ghorbani & Zou, 2019). For some experiments, we also compare with (4) Learning to Reweight (Ren et al., 2018), (5) MentorNet (Jiang et al., 2018), and (6) Influence Function (Koh & Liang, 2017).
Datasets: We consider 12 public datasets (3 public tabular datasets, 7 public image datasets, and 2 public language datasets) to evaluate DVRL in comparison to multiple benchmark methods. 3 public tabular datasets are (1) Blog, (2) Adult, (3) Rossmann; 7 public image datasets are (4) HAM 10000, (5) MNIST, (6) USPS, (7) Flower, (8) Fashion-MNIST, (9) CIFAR-10, (10) CIFAR-100; 2 public language datasets are (11) Email Spam, (12) SMS Spam. Details can be found in the hyper-links.
Baseline predictor models: We consider various machine learning models as the baseline predictor model to highlight the proposed model-agnostic data valuation framework. For Adult and Blog datasets, we use LightGBM (Ke et al., 2017), and for Rossmann dataset, we use XGBoost and multi-layer perceptrons due to their superior performance on the tabular datasets. For Flower, HAM 10000, and CIFAR-10 datasets, we use Inception-v3 with top-layer fine-tuning (pre-trained on ImageNet, (Szegedy et al., 2016)) as the baseline predictor model. For Fashion-MNIST, MNIST, and USPS datasets, we use multinomial logistic regression, and for Email and SMS datasets, we use Naive Bayes model. We also use ResNet-32 (He et al., 2016) and WideResNet-28-10 (Zagoruyko & Komodakis, 2016) as the baseline models for CIFAR-10 and CIFAR-100 datasets in Section 4.3 to demonstrate the scalability of DVRL. For data value estimation network, we use multi-layer perceptrons with ReLU activation as the base architecture. The number of layers and hidden units are optimized with cross-validation.
Experimental details: In all experiments, we use Standard Normalizer to normalize the entire features to have zero mean and one standard deviation. We transform categorical variables into one-hot encoded embeddings. We set the inner iteration count (NI=200) for the predictor network, moving average window (T=20), and mini-batch size (Bp=256) for the predictor network and mini-batch size (Bs=2000) for the DVE network (large batch size often improves the stability of the reinforcement learning model training (McCandlish et al., 2018)). We set the learning rate to 0.01 (β) for the data value estimator (DVE) and 0.001 (α) for the predictor network. As the DVE architecture, for tabular datasets, we use 5-layer perceptrons with 100 hidden units and ReLU; and for image datasets, we use 5-layer perceptrons with 100 hidden units and ReLU on top of the CNN-based architecture used for the predictor network (such as ResNet-32 or WideResNet-28-10 in Table 1). In order to provide further informative signal to DVE, we propose to use an additional input of the difference between the predictions of a separate predictive model (fined-tuned or trained from scratch on the validation set) for the training samples and the original training labels. We simply concatenate this additional input to the hidden states of DVE network. Intuitively, if the training label is corrupted, the additional input would be high; thus, this could be an important signal for DVE to assign low value to this sample. Ablation study for the variants of DVRL can be found in the Appendix C.6.

heading: 4.1 REMOVING HIGH/LOW VALUE SAMPLES

text:
Removing low value samples from the training dataset can improve the predictor model performance, especially in the cases where the training dataset contains corrupted samples. On the other hand, removing high value samples, especially if the dataset is small, would decrease the performance significantly. Overall, the performance after removing high/low value samples is a strong indicator for the quality of data valuation.
Initially, we consider the conventional supervised learning setting, where all training, validation and testing datasets come from the same distribution (without sample corruption or domain mismatch). We use two tabular datasets (Adult and Blog) with 1,000 training samples and one image dataset (Flower) with 2,000 training samples.2 We use 400 validation samples for tabular datasets and 800 validation samples for the image dataset. Then, we report the prediction performance on the disjoint testing set after removing the high/low value samples based on the estimated data values.
As shown in Fig. 2, even in the absence of sample corruption or domain mismatch, DVRL can marginally improve the prediction performance after removing some portion of the least important samples. Using only ∼60%-70% of the training set (the highest valued samples), DVRL can obtain a similar performance compared to training on the entire dataset. After removing a small portion (10%-20%) of the most important samples, the prediction performance significantly degrades which indicates the importance of the high valued samples. Qualitatively looking at these samples, we ob-
2We use the small training dataset in this experiment in order to compare with LOO and Data Shapley which have high computational complexities. DVRL is scalable to larger datasets as shown in Section 4.3.
serve them to typically be representative of the target task which can be insightful. Overall, DVRL shows the fastest performance degradation after removing the most important samples and the slowest performance degradation after removing the least important samples in most cases, underlining the superiority of DVRL in data valuation quality compared to competing methods.
Next, we focus on the setting of removing high/low value samples in the presence of label noise in the training data. We consider three image datasets: Fashion-MNIST, HAM 10000, and CIFAR10. As noisy samples hurt the performance of the predictor model, an optimal data value estimator with a clean validation dataset should assign lowest values to the noisy samples. With the removal of samples with noisy labels (‘Least’ setting), the performance should either increase, or at least decrease much slower, compared to removal of samples with correct labels (‘Most’ setting). In this experiment, we introduce label noise to 20% of the samples by replacing true labels with random labels. As can be seen in Fig. 10, for all data valuation methods the prediction performance tends to first slowly increase and then decrease in the ‘Least’ setting; and tends to rapidly decrease in the ‘Most’ setting. Yet, DVRL achieves the slowest performance decrease in ‘Least’ setting and fastest performance decrease in the ‘Most’ setting, reflecting its superiority in data valuation.

heading: 4.2 CORRUPTED SAMPLE DISCOVERY

text:
There are some scenarios where training samples may contain corrupted samples, e.g. due to cheap label collection methods. An automated corrupted sample discovery method would be highly beneficial for distinguishing samples with clean vs. noisy labels. Data valuation can be used in this setting by having a small clean validation set to assign low data values to the potential samples with noisy labels. With an optimal data value estimator, all noisy labels would get the lowest data values.
We consider the same experimental setting with the previous subsection with 20% noisy label ratio on 6 datasets. Fig. 4 shows that DVRL consistently outperforms all benchmarks (Data Shapley, LOO and Influence Function). The trend of noisy label discovery for DVRL can be very close to optimal (as if we perfectly knew which samples have noisy labels), particularly for the Adult, CIFAR-10 and Flower datasets. To highlight the stability of DVRL, we provide the confidence intervals of DVRL performance on the corrupted sample discovery in Appendix E.

heading: 4.3 ROBUST LEARNING WITH NOISY LABELS

text:
In this section, we consider how reliably DVRL can learn with noisy data in an end-to-end way, without removing the low-value samples as in the previous section. Ideally, noisy samples should get low data values as DVRL converges and a high performance model can be returned. To compare DVRL with two recently-proposed benchmarks: MentorNet (Jiang et al., 2018) and Learning to Reweight (Ren et al., 2018) for this use case, we focus on two complex deep neural networks as the baseline predictor models, ResNet-32 (He et al., 2016) and WideResNet-28-10 (Zagoruyko &
Komodakis, 2016), trained on CIFAR-10 and CIFAR-100 datasets. Additional results on other image datasets are in Appendix C.1, and results on robust learning with noisy features are in Appendix C.2.
We consider the same experimental setting from Ren et al. (2018) on CIFAR-10 and CIFAR-100 datasets. For the first experiment, we use WideResNet-28-10 as the baseline predictor model and apply 40% of label noise uniformly across all classes. We use 1,000 clean (noise-free) samples as the validation set and test the performance on the clean testing set. For the second experiment, we use ResNet-32 as the baseline predictor model and apply 40% background noise (same-class noise to the 40% of the samples). In this case, we only use 10 clean samples per class as the validation set. We consider five additional benchmarks: (1) Validation Set Only – which only uses clean validation set for training, (2) Baseline – which only uses noisy training set for training, (3) Baseline + Finetuning – which is initialized with the trained baseline model on the noisy training set and fine-tuned on the clean validation set, (4) Clean Only (60% data) – which is trained on the clean training set after removing the training samples with flipped labels, (5) Zero Noise – which uses the original noise-free training set for training (100% clean training data). We exclude Data Shapley and LOO in this experiment due to their prohibitively-high computational complexities.
As shown in Table 1, DVRL outperforms other robust learning methods in all cases. The performance improvements with DVRL are larger with Uniform noise. Learning to Reweight loses 7.16% and 13.21% accuracy compared to the optimal case (Zero Noise); on the other hand, DVRL only loses 5.06% and 7.99% accuracy for CIFAR-10 and CIFAR-100 respectively with Uniform noise.

heading: 4.4 DOMAIN ADAPTATION

text:
In this section, we consider the scenario where the training dataset comes from a substantially different distribution from the validation and testing sets. Naive training methods (i.e. equal treatment of all training samples) often fail in this scenario (Ganin et al., 2016; Glorot et al., 2011). Data valuation is expected to be beneficial for this task by selecting the samples from the training dataset that best match the distribution of the validation dataset.
We initially focus on the three cases from Ghorbani & Zou (2019), shown in Table 2. (1) uses Google image search results (cheaply collected dataset) to predict skin lesion classification on HAM 10000 data (clean), (2) uses MNIST data to recognize digit on USPS dataset, (3) uses Email spam data to detect spam in an SMS dataset. The experimental settings are exactly the same with Ghorbani & Zou (2019). Table 2 shows that DVRL significantly outperforms Baseline and Data Shapley in all three tasks. One primary reason is that DVRL jointly optimizes the data value estimator and corresponding predictor model; on the other hand, Data Shapley needs a two step processes to construct the predictor model in domain adaptation setting.
Next, we focus on a real-world tabular data learning problem where the domain differences are significant. We consider the sales forecasting problem with the Rossmann Store Sales dataset, which consists of sales data from four different store types. Simple statistical investigation shows a significant discrepancy between the input feature distributions across different store types, meaning there is a large domain mismatch across store types (see Appendix F). To further illustrate distribution difference across the store types, we show the t-SNE analysis on the final layer of a discriminative neural network trained on the entire dataset in Appendix Fig. 11. We consider three different settings: (1) training on all store types (Train on All), (2) training on store types excluding the store type of interest (Train on Rest), and (3) training only on the store type of interest (Train on Specific). In all cases, we evaluate the performance on each store type separately. For example, to evaluate the performance on store type D, Train on All setting uses all four store type datasets for training, Train on Rest setting uses store types A, B and C for training, and Train on Specific setting only uses the store type D for training. Train on Rest is expected to yield the largest domain mismatch between training and testing sets, and Train on Specific yield the minimal.
We evaluate the performance of Baseline (train the predictor model without data valuation) and DVRL in 3 different settings with 2 different predictor models (XGBoost (Chen & Guestrin, 2016) and Neural Networks (3-layer perceptrons)). As shown in Table 3, DVRL improves the performance in all settings. The improvements are most significant in Train on Rest setting due to the large domain mismatch. For instance, DVRL reduces the error more than 50% for store type B predictions with XGBoost in comparison to Baseline. In Train on All setting, the performance improvement is still significant, showing that DVRL can distinguish the samples from the target distribution. In Appendix G, we demonstrate that DVRL actually prioritizes selection of the samples from the target store type. In Train on Specific setting, the performance improvements are smaller – even without domain mismatch, DVRL can marginally improve the performance by accurately prioritizing the important samples within the same store type. These results further support the conclusions from Fig. 2 in the conventional supervised learning setting that DVRL learns high quality data value scores. Comparison to other domain adaptation benchmarks can be found in Appendix C.5.

heading: 4.5 DISCUSSION: HOW MANY VALIDATION SAMPLES ARE NEEDED?

text:
DVRL requires a validation dataset from the target distribution that the testing dataset comes from. Depending on the task, the requirements for the validation dataset may involve being noise-free in labels, being from the same domain, or being high quality. Acquiring such a dataset can be costly in some scenarios and it is desirable to minimize its size requirements.
We analyze the impact of the size of the validation dataset on DVRL with 3 different datasets: Adult, Blog, and Fashion MNIST for the use case of corrupted sample discovery. Similar to Section 4.2, we add 20% noise to the training samples and try to find the corrupted samples with DVRL. As shown in Fig. 5, DVRL achieves reasonable performance with 100 to 400 validation samples. In the Adult dataset, even 10 validation samples are sufficient to achieve a reasonable data valuation quality. Both of these settings are often realistic in real world scenarios.

heading: 5 CONCLUSIONS

text: In this paper, we propose a meta learning framework, named DVRL, that adaptively learns data values jointly with a target task predictor model. The value of each datum determines how likely it will be used in training of the predictor model. We model this data value estimation task using a deep neural network, which is trained using reinforcement learning with a reward obtained from a small validation set that represents the target task performance. With a small validation set, DVRL can provide computationally highly efficient and high quality ranking of data values for the training dataset that is useful for domain adaptation, corrupted sample discovery and robust learning. We show that DVRL significantly outperforms other techniques for data valuation in various applications on diverse types of datasets.

heading: A BLOCK DIAGRAMS FOR INFERENCE

heading: B COMPUTATIONAL COMPLEXITY

text:
DVRL first trains the baseline model using the entire dataset (without re-weighting). Afterwards, we can use this pre-trained baseline model to initialize the predictor network and apply fine-tuning with DVRL update steps. The convergence of the fine-tuning process is much faster than the convergence of training from the scratch.
We quantify the computational overhead of DVRL on the CIFAR-100 dataset (consisting 50k training samples) with ResNet-32 as a representative example. Overall, DVRL training takes less than 8 hours (given a pre-trained ResNet-32 model on the entire dataset) on a single NVIDIA Tesla V100 GPU without any hardware optimizations. The pre-training time of ResNet-32 on the entire dataset (without re-weighting) is less than 4 hours; thus the total training time of DVRL is less than 12 hours from the scratch. On the other hand, the training time of Data Shapley (the most competitive benchmark) is more than a week on Fashion MNIST (consisting lower dimensional inputs and less number of classes) with a much simpler predictor model architecture (2-layered convolutional neural networks).
At inference, the data value estimator can be used to obtain data value for each sample. The runtime of data valuation is typically much faster (less than 1 ms per sample) than the predictor model (e.g. ResNet-32 model).

heading: C ADDITIONAL RESULTS

text:
C.1 ADDITIONAL RESULTS ON ROBUST LEARNING WITH NOISY LABELS
We evaluate how DVRL can provide robustness for learning with noisy labels. We add various levels of label noise, ranging from 0% to 50%, to the training sets and evaluate how robust the proposed model (DVRL) is for the noisy dataset. In this experiment, we use three image datasets (CIFAR-10, Flower, and HAM 10000). Note that we initialize the predictor model using pre-trained Inception-v3 networks on ImageNet and only fine-tune the top layer (transfer learning setting).
Noisy labels significantly degrade the prediction performance when they are included in the training dataset (see the increasing differences between Baseline and Clean in Table 4). DVRL demonstrates high robustness up to high noisy label ratio (50%). In some cases (even without noisy labels (i.e. 0% noise ratio)), the prediction performance even outperforms the Clean case, as DVRL prioritizes some clean samples more than others. Overall, DVRL framework is promising in maintaining high prediction performance even with a significant increase in the amount of noisy labels.
C.2 ADDITIONAL RESULTS ON ROBUST LEARNING WITH NOISY FEATURES
In this section, we consider training with noisy input features, with a clean validation set. We independently add Gaussian noise with zero mean and a certain standard deviation of σ to each feature in the training set independently. We use two tabular datasets (Adult and Blog) to evaluate the robustness of DVRL on input noise. As can be seen in Table 5, DVRL is robust with noise on the features and the performance gains are higher with larger noise in comparison to Baseline (i.e. treat all the noisy training samples equally), since DVRL can discover the training samples with less corrupted by the additive noise among the entire noisy training samples and provide higher weights on those less noisy samples.
C.3 ADDITIONAL RESULTS ON REMOVING HIGH/LOW VALUE SAMPLES WITH 20% LABEL NOISE
C.4 ADDITIONAL RESULTS ON CORRUPTED SAMPLE DISCOVERY WITH 20% LABEL NOISE
C.5 COMPARISON TO OTHER DOMAIN ADAPTATION BENCHMARKS
In this subsection, we compare DVRL to two established domain adaptation benchmarks: Adversarial Discriminative Domain Adaptation (ADDA) (Tzeng et al., 2017) and Domain Adversarial Neural Networks (DANN) (Ganin et al., 2016). We use the same experimental settings given in Table 3 using Rossmann Store Sales dataset with neural networks as the predictor model. Table 6 represents the domain adaptation results on ‘Train on all’ and ‘Train on Rest’ settings. As can be seen, DVRL yields superior (or similar in a few cases) compared to the two methods, ADDA and DANN, that are specifically designed for domain adaptation.
C.6 ABLATION STUDIES
In this subsection, we analyze the source of gains for three distinct components of DVRL: (1) discrete representations of data value estimator, (2) baseline for stabilizing the RL training, (3) output of the model trained on the clean validation set as the additional input (validation model). We report the corrupted sample discovery results where the experimental settings are same with Section 4.2.
As can be seen in Table 7, each component provides an additional gain in DVRL:
(1) A straightforward idea is to use the raw outputs of DVE to scale the contributions of each sample in the loss term, without using the sampler. Yet, we show the benefit of the discrete representation of DVE for data selection. The sampler encourages exploration of an extremely large action space in a systematic way. This helps DVE and predictor model to converge to a better optimal solution.
(2) Baseline stabilizes the convergence of reinforcement learning; thus, yields higher gains on complex datasets.
(3) The output of the validation model itself has informative signal as it achieves high performance (since it is trained with small-scale but high quality data). We observe that this signal helps DVRL, but even without this signal achieves high performance. We also observe that often a larger DVE model (with more iterations) is needed to estimate the data value in the absence of the informative signal from the validation model.
Note that we propose to use the output of the validation model as an additional input to the data valuation framework; thus, this can also be regarded as another contribution of our work. Also, the
output of the validation model is highly informative in the noisy sample discovery use case but not that significant in other applications such as domain adaptation or performance improvement by low value data removal in standard supervised learning setting.

heading: D LEARNING CURVES OF DVRL

text: Fig. 9 shows the learning curves of DVRL on the noisy data (with 20% label noise) setting in comparison to the validation log loss without DVRL (directly trained on the noisy data without reweighting) on 2 tabular datasets (Adult and Blog) and 4 image datasets (Fashion-MNIST, Flower, HAM 10000, and CIFAR-10).

heading: E CONFIDENCE INTERVALS OF DVRL PERFORMANCE ON CORRUPTED SAMPLE DISCOVERY EXPERIMENTS

heading: F ROSSMANN DATA STATISTICS & T-SNE ANALYSIS

text:
G FURTHER ANALYSIS ON ROSSMANN DATASET IN Train on All SETTING
To further understand the results in Train on All setting, we sorted (in a decreasing order) the training samples by their data values estimated by DVRL and illustrate the distributions of the training samples that come from the target store type. As can be seen in Fig. 12, DVRL prioritizes the training samples which come from the same target store type.


summaries: The paper studies the mean and variance of the gradient norm at each layer for vanilla feedforward, ResNet and DenseNet, respectively, at the initialization step, which is related with Hanin & Ronick 2018 studying the mean and variance of forward activations. They show that ResNet and DenseNet preserve the variance of the layer gradient norm through depths. In comparison, for the vanilla feedforward network, although the mean of the gradient norm is preserved if  is properly initialized, the variance of the layer gradient norm increases over depths, which may explode or decay the gradient at deeper layers.

summaries: This paper studies the effects of residual and dense net type connections on the moments of per-layer gradients at random initialization. In particular, using duality, bounds on the variance of the square norm of Jacobian (with respect to the randomness of random initialization) are derived for vanilla networks. By noticing that connections that bypass a specific layer does not affect the expected square norm of the gradients of a particular layer, the paper continue to characterize the bounds for residual networks and densely connected networks that have special skip connections. In particular, with properly chosen initialization scales for each layer, the architectures with skip connections can be initialized so that the gradient norm does not explode with increasing depth.

abstractText: A critical part of the training process of neural networks takes place in the very first gradient steps post-initialization. In this work, we study the connection between the network’s architecture and initialization parameters, to the statistical properties of the gradient in random fully connected ReLU networks, through the study of the the per layer Jacobian in finite sized networks. We compare three types of architectures: vanilla networks, ResNets and DenseNets. In our analysis, we show that while the variance of Jacobian squared norm is exponential in depth for ResNets, and polynomial for DenseNets, there exists an initialization strategy for both, such that the norm is preserved through arbitrary depths, preventing exploding or decaying gradients in deep networks.We also show that the statistics of the per layer Jacobian norm is a function of the architecture and the layer’s size, but surprisingly, not the layer’s depth.

authors:
Djork-Arné Clevert
Thomas Unterthiner
Sepp Hochreiter

title: Fast and accurate deep network learning by exponential linear units (elus)

venue: arXiv preprint arXiv:1511.07289,

title: Which neural net architectures give rise to exploding and vanishing gradients

venue: Advances in Neural Information Processing Systems

authors:
Boris Hanin
David Rolnick

title: How to start training: The effect of initialization and architecture

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Delving deep into rectifiers: Surpassing human-level performance on imagenet classification

venue: In Proceedings of the IEEE international conference on computer vision,

title: Deep residual learning for image recognition

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
Gao Huang
Zhuang Liu
Kilian Q. Weinberger

title: Densely connected convolutional networks

authors:
Günter Klambauer
Thomas Unterthiner
Andreas Mayr
Sepp Hochreiter

title: Self-normalizing neural networks

authors:
Jeffrey Pennington
Samuel Schoenholz
Surya Ganguli

title: Resurrecting the sigmoid in deep learning through dynamical isometry: theory and practice

authors:
Jeffrey Pennington
Samuel S. Schoenholz
Surya Ganguli

title: The emergence of spectral universality in deep networks

venue: In AISTATS,

authors:
Samuel S Schoenholz
Justin Gilmer
Surya Ganguli
Jascha Sohl-Dickstein

title: Deep information propagation

venue: In ICLR,

authors:
Wenling Shang
Kihyuk Sohn
Diogo Almeida
Honglak Lee

title: Understanding and improving convolutional neural networks via concatenated rectified linear units

venue: In ICML,

authors:
Lechao Xiao
Yasaman Bahri
Jascha Sohl-Dickstein
Samuel Schoenholz
Jeffrey Pennington

title: Dynamical isometry and a mean field theory of CNNs: How to train 10,000-layer vanilla convolutional neural networks

venue: Proceedings of the 35th International Conference on Machine Learning,

authors:
Greg Yang
Sam Schoenholz

title: Mean field residual networks: On the edge of chaos

authors:
Hongyi Zhang
Yann N. Dauphin
Tengyu Ma

title: Fixup initialization: Residual learning without normalization

heading: 1 INTRODUCTION

text:
Understanding the effect of different architectures on the ability to train deep networks has long been a major topic of research. A recent line of work has focused on the statistical properties of both the activations and the gradients of different architectures at the point of initialization, in order to better understand the effect of different architectural choices on the training dynamics.
A well-known hurdle in the ability to train deep networks, is the effect of depth on the magnitude of the gradients. Specifically, the exploding and vanishing gradient phenomena have been observed in various deep architectures. they are considered a main culprit in the failure of training deep networks successfully. A flurry of architectural tricks and initialization techniques have been proposed, in order to mitigate the problem of exploding and vanishing gradients, ranging from residual architectures, different normalization techniques and orthogonal initializations.
In this work, we perform a rigorous analysis of the norm, of both the activations and the gradients of each layer, in fully connected architectures at the point of initialization. Our setting is as follows: we assume a fixed input y0 to an L layer neural network with weights given by W , and intermediate output for any layer l denoted by yl. Denoting by wkij the weights ij of layer k, we are interested in the quantities:
‖yl‖2, ‖Jk‖2 = ∑ ij ‖ ∂y L ∂wkij ‖2 (1)
representing the norm of the activations of layer l and Jacobian with respect to layer k. We consider these quantities random variables at initialization, and, therefore, devote our analysis to deriving expressions for the mean and variance of both ‖yl‖2 and ‖Jk‖2, over the random initializations of the weights. Note that the full gradient requires an additional loss term which is independent of the architecture, and so our attention is focused on Jk. While most initialization techniques are designed to maintain the squared length of intermediate activations through the layers, the multiplication of i.i.d random weights along input-to-output paths in increasingly deep networks might lead to unbounded higher order statistics. In the extreme case, while the mean of activation and gradients remain constant in deep layers, it would be improbable to achieve mean values for any specific realization of the weights, rendering training difficult. Specifically, given some loss function L, the
norm of the gradient with respect to W k is given by:
‖∇WkL‖ = ‖ ∂L ∂yL Jk‖ ≤ ‖ ∂L ∂yL ‖‖Jk‖ (2)
Large fluctuations to the Jacobian norm with respect to small perturbations of the weights will, therefore, cause wildly fluctuating gradients during training, hindering training dynamics.
Our analysis makes use of a duality theorem, which captures an intuitive concept. In residual architectures, there are many alternative paths of varying lengths from input to output. The theorem states that when considering the moments of the gradient at a certain layer, one can change the architecture, so all connections which that skip that layer are removed. This is true, despite the activations of the two networks being very different. See Fig. 1.
Our contributions are as follows: (i) We rigorously study the effect of different architectures, namely vanilla, residual and densely connected architectures, on the mean and variance of ‖yl‖2 and ‖Jk‖2 in finite depth and width networks. (ii) From our forward-backward norm propagation duality theorem, we derive conditions that prevent exploding gradients in each of these architectures. (iii) We prove that for densely connected networks, the commonly used initialization of He et al. (2015) is enough to ensure the boundness of var(‖Jk‖2) and var(‖yl‖2) for arbitrarily deep networks, shedding new light on the apparent advantage of these architectures in practical applications. (iv) We prove that replacing the standard conv-ReLU blocks with blocks of the concatenated ReLU (CR) activation presented by Shang et al. (2016), while maintaining the same parameter budget, significantly reduces the fluctuations of both the activations and gradients at initialization for any ReLU based architecture. We evaluate the applicability of this simple alteration on a large number of UCI datasets, and demonstrate the advantage for CR based networks over their standard counterparts.

heading: 2 RELATED WORK

text:
The effect of architecture and depth on the gradients has been a topic of considerable interest recently, leading to several insightful research directions. A major line of work has been focused on the mean field approach, where the propagation of signals in random networks are analyzed in the regime of infinite width (Yang & Schoenholz (2017),Schoenholz et al. (2017),Xiao et al. (2018)). In that case, the pre-activations in any layer are approximated by a Gaussian distribution with moments depending on the specific layer. For ReLU networks (without residual connections), controlling the exponential explosion or decay of both the activations and gradients with depth is a simple matter of correctly scaling the initialization parameters. Indeed, it is shown in Schoenholz et al. (2017) that classical feed forward networks exhibit exponential behavior on average, when not initialized properly. For the gradients, a recursion relation is derived:
E ( ( ∂yL ∂yli )2 ) = E ( ( ∂yL ∂yl+1i )2 ) σ2w ∫ 1√ 2π e− z2 2 φ′( √ q∗z)dz (3)
where φ′ the derivative of the activation function and σ2w denotes the variance of the weights. By initializing with σ2w = 2 fan−in , and considering that for the ReLU activation function φ
′(z) = 1z>0, we have that
E(( ∂yL
∂yli )2) = E((
∂yL
∂yl+1i )2). (4)
Mean field analysis of residual networks is presented in Yang & Schoenholz (2017), where it is shown that ResNets exhibit sub-exponential, or even polynomial dynamics, depending on the activation function. While mean field theory captures the “average” dynamics of random neural networks, it does not take into account the scale of gradient fluctuations that are crucial to the stability of gradient descent, which is the focus of this work. A more refined analysis presented in Pennington et al. (2017), considers the full spectrum of the input output Jacobian of infinitely wide networks, given by:
JIO = ∂yL
∂y0 (5)
Exploding or vanishing gradients are then prevented by analyzing conditions that give rise to dynamical isometry, a state in which the squared eigenvalues of JIO are all concentrated around 1. In (Pennington et al., 2017) it is shown that fully connected ReLU networks are incapable of reaching dynamical isometry, as apposed to sigmoidal networks, while in (Pennington et al., 2018) it is shown that dynamical isometry is achieved in a universal manner for a variety of activation functions. Dynamical isometry is a much stronger condition than the Jacobian norm, since it requires access to the entire spectrum. However, in previous work, this is done using various forms of infinite width approximations. Instead, this work focuses on finite depth corrections to the statistics of various quantities concerning the squared Frobenius norm of the per-layer Jacobian (derivative of the output with respect to the weights), and can be viewed as a complementary approach to analyzing the dynamics at the start of training. Our results cannot be obtained using large width approximations, since we seek to characterise the effect of both depth and width on the Jacobian.
A recent line of work, more related to the analysis presented in this paper, deals with the statistical properties of the norm of activations and gradients in random finite width networks. Hanin & Rolnick (2018) tackle two failure modes that are caused by exponential explosion or decay of the norm of intermediate layers. It is shown that for random fully connected vanilla ReLU networks, the variance of the squared norm of the activations exponentially increases, even when initializing with the 2fan−in initialization. For ResNets, this failure mode can be overcome by correctly rescaling the residual branches. However, it is not clear how such a rescaling affects the back propagation of gradients. In our work, we prove an equivalence relation between the forward- and back-propagation of norms in most random ReLU networks. In addition, we present an analysis of DenseNets, revealing a surprising norm preservation quality that is independent of depth.
Hanin (2018) explores the conditions at initialization that give rise to the exploding or vanishing gradient problem, by analyzing the individual entries of the input-output Jacobian. In the case of a single output network, the layer k to output Jacobian is given by the row vector:
J(k → L) = (∂y L
∂yli , i = 1...nk) =
∂yL ∂yl (6)
with nk denoting the width of layer k. In our work, we take a more direct approach to analyzing the full expression for the Jacobian of random networks given by:
Jkij = ∂yL ∂yk ∂yk ∂wkij = 〈J(k → L), ∂y k ∂wkij 〉. (7)
Moreover, the analysis presented by Hanin (2018) does not directly carry over to ResNets or DenseNets.

heading: 3 PRELIMINARIES AND NOTATIONS

text:
We make use of the following notations: N denotes a neural network architecture with intermediate outputs yl of layer l for a fixed input y0. yli denotes the i’th component of the vector y
l, and n1...nL denote the width of the corresponding layers, with n the length of the input vector. ‖ · ‖2 is the squared Euclidean norm, and we assume ‖y0‖2 = 1. We denote the weight matrix associated with layer l by W l ∈ Rnl−1×nl , with lower case letters wlij denoting the individual components of W l. Additional superscripts W lk are used, when several weight matrices are associated with layer l, for instance in residual, CR and DenseNet architectures. Throughout the paper, we assume that the weights are sampled i.i.d from some symmetric distribution with moments E((wlij)m) = clm,
such that ∀ijl, ∀l, cl1 = 0, cl2 = 2αnl−1 . We further identify the following property of a distribution ∆ = 2(cl4 − 3(cl2)2)/nl−1 (for Gaussian distributions, ∆ = 0). The derivative of the output unit yL with respect to wlij is given by J l ij = ∂yL
∂wlij = ∂y
L ∂yl ∂yl
∂wlij , with ‖J l‖2 =
∑ ij(J l ij) 2. We will
be concerned in our analysis with the quantities E(‖yl‖2), var(‖yl‖2), E(‖J l‖2) and var(‖J l‖2), where the expectations are taken across the random sampling of the weights, given the fixed input y0.
Multi Pathway Architectures We compare a vanilla fully-connected network to ResNets He et al. (2016) and DenseNets Huang et al. (2016) to a network that is built with CR Shang et al. (2016) layers. For the standard vanilla fully-connected network, the output for of layer l is given by
yl = φ(W l>yl−1), (8) where φ() denotes the ReLU non-linearity.
For residual architectures, we study models with m layer residual branches of the form
yl = yl−1 +Rm(yl−1) (9) where: Rm(yl−1) = W lm>...φ(W l2>φ(W l1>yl−1). (10) We denote the k’th intermediate output of the l’th residual branch by
ỹl−1,k = W lk>...φ(W l2>φ(W l1>yl−1), (11) so that, for example
Rm(yl−1) = W lm>ỹl−1,m−1 = W lm>φ(W lm−1>ỹl−1,m−2). (12) Furthermore, since the last layer of any residual branch W lm does not end with a non-linearity, we assume clm2 = 1 n . DenseNets were recently introduced, demonstrating faster training, as well as improved performance on several popular datasets. The main architectual features introduced by DenseNets include the connection of each layer output to all subsequent layers, using concatenation operations instead of summation, such that the weights of layer l multiply the concatenation of the outputs y0...yl−1, and is of dimensionsW l ∈ Rln×n. For our analysis, we breakW l into l−1 weight matrices W l1...W ll−1 ∈ Rn×n, so that the output of layer l is given by yl = φ( ∑l−1 l′=1W ll′>yl ′ ).

heading: 4 FORWARD-BACKWARD NORM PROPAGATION DUALITY

text:
In this section, we introduce a link between the propagation of the norm of the activations, and the norm of the Jacobian in different layers in random ReLU networks of finite width. This link will then allow us to study the statistical properties of the gradient in general architectures incorporating residual connections and concatenations with relative ease. Specifically, we would like to establish a connection between the first and second moments of the squared norm of the output ‖yL‖2, and those of the Jacobian norm ‖Jk‖2. The family of architectures we consider is restricted, so that the ReLU activations are only applied after multiplication with weights. Using a path-based notation, any unit t of the output yLt can be decomposed to paths that go through weight matrix W
k, denoted by yL,kt (neglecting an additional superscript for ResNets and DenseNets), and paths that skip W
k, denoted by ŷL,kt . Assuming the input ∀j , y0j = 1, we have:
yLt = y L,k t + ŷ L,k t = ∑ k∈γt |γt|∏ l=1 wlγt,lzγt + ∑ k/∈γt |γt|∏ l=1 wlγt,lzγt (13)
where the summation is over paths from input to unit t of the output, indexed by γt, with |γt| denoting the length of the path indexed by γt. In non-residual networks, we have |γt| = L and ∑ γt
sums over∏L−1 l=0 nl paths. The term ∏|γt| l=1 w l γt,l zγt denotes the product of weights along path γt, multiplied by a
binary variable zγt ∈ [0, 1], indicating whether path γt is active. Finally, ∑ k/∈γ indicates summation over all possible paths that do not include a weight from layer k. In all relevant architectures, the squared norm of the Jacobian entry ‖Jkij‖2 is given by:
‖Jkij‖2 = ‖ ∂yL,k
∂wkij ‖2 = nL∑ t=1 ( ∑ ijk∈γt 1 wkij |γt|∏ l=1 wlγt,lzγt )2 (14)
That is, the derivative of output unit t with respect to weight wkij is given by the sum of all paths γ that contain wkij divided by w k ij . In order to link J k with yL, we make the following definition:
Definition 1. Reduced network: the outputs of a reduced network N(k) denoted by y1(k)...y L (k) given input y0 are obtained by removing all connections bypassing weight W k from the network N .
Note that for vanilla networks, it holds that N(k) = N , and ∀0<l≤L, yl(k) = y l. The following Lemma links between the moments of yL(k) and those of y L:
Lemma 1. For any architecture described in Sec. 3, it holds that for m ∈ {2, 4}: E ( ‖yL(k)‖ m ) = E ( ‖yL,k‖m ) (15)
Note that if network N contains connections bypassing layer k, then for a specific realization of the weights, the equality yL(k) = y
L,k does not hold in general, due to different activation patterns in N and N(k) induced by additional residual connections. In other words, paths that are open in N (indicated by the variables zγt ) are not necessarily so inN(k), and vice versa. Lem. 1, however, states that the moments of both are equal in the family of considered ReLU networks. The following theorem relates the moments of ‖Jk‖2 with those of ‖yL(k)‖: Theorem 1. For any architecture described in Sec. 3,the following hold:
E ( ‖Jk‖2 ) = 1 ck2 E ( ‖yL(k)‖ 2 ) , var(‖yL(k)‖ 2) ck4 ≤ var(‖Jk‖2) ≤ var(‖yL(k)‖ 2) (ck2) 2
(16)
where ck2 and c k 4 are the second and fourth moments of the weights in layer k. Thm. 1 indicates that we can compute the moments of the Jacobian norm of layer k, by computing the moments of the output of the reduced network yL(k). Thm. 1 also reveals a surprising property of the gradients in general Relu networks. That is, when the weights are sampled from the same distribution in each layer, the gradient’s magnitude for each layer are equal in expectation, and depend only on the output statistics.

heading: 4.1 VANILLA NETWORKS

text:
In order to compare our results for ResNets and DenseNets, we first derive the moments of yl(k) in our setting for vanilla architectures. Note that for vanilla networks, the reduced network matches the original, and so ∀0<l≤L, yl(k) = y l.
Lemma 2. For a vanilla ReLU neural network, as described in Sec, 3, it holds for α = 1:
C1 exp [ L−1∑ l=1 5− |∆| 2nl ] − C2 ≤ var ( ‖Jk‖2 ) ≤ C3 exp [ L−1∑ l=1 5 + |∆| nl ] − C4 (17)
where C1, C2, C3, C4 are constants that do not depend on L.
By setting α = 1, the variance of the Jacobian squared norm ‖Jk‖2 will increase exponentially with ∑L l=1 5 nl
, as noted by Hanin & Rolnick (2018). This can be mitigated by linearly increasing the width of each layer with depth, so that nl = nl, resulting in constant asymptotic behavior
exp [∑L−1 l=1 1 nl ] ∼ L 1n . This, however, would require significant resources, since the weight
matrices would grow quadratically with depth. For comparison, in DenseNets the variance is maintained with depth, while the number of weights increases linearly.

heading: 4.2 RESIDUAL NETWORKS

text:
Residual networks have reintroduced the concept of bypass connections, allowing the training of deep and narrow models with relative ease. Hanin & Rolnick (2018) showed shown that the fluctuations of the norm of subsequent layers do not exponentially increase, provided that the weights are initialized,
such that the expected norm E(‖yl‖2) is bounded for any layer l. Such an initialization is not constant, and is dependant on the depth of the network L. It is also worth mentioning that the same depth dependent initialization for ResNets was found by Zhang et al. (2019) to be crucial for training convolutional ResNets without applying batchnorm, as introduced in the original formulation of ResNets. Recall that in our analysis, we consider residual branches with m layers with weights W kk ′ , 0 < k ≤ L, 0 < k′ ≤ m,, and so we will analyze the variance of ‖Jkk′‖2 = ∑ ij ( ∂yL
∂wkk ′
ij )2 for k′ < m. Unlike vanilla networks, the outputs of the reduced network yl(k) for l > k are not equal to those of the full network yl, and are given by:
yl(k) = { Rm(yl−1) + yl−1 l 6= k Rm(yl−1) l = k
(18)
The following theorem states our results for ResNets. Theorem 2. For a ResNet as in Sec, 3 with m ≥ 2, it holds that for 0 < k ≤ L, 0 < k′ < m:
C1ρ m − exp
[ 1
2 Lρm−
] − C2µ2 ≤ var ( ‖Jkk ′ ‖2 ) ≤ C3ρm+ exp [ 2Lρ m 2 + ] − C4µ2 (19)
where ρ± = α2(1 + 5±|∆| n ), C1, C2, C3, C4 are constants that do not depend on L,m, and µ = αm ( 1 + αm )L−1 .
The gradients of weights in residual branches are, therefore, sensitive to the depth of each residual branch (large m). However, unlike their vanilla counterparts, by scaling the residual branches, such that Lρm+ is kept constant, ensures that both E(‖J‖2) and var(‖J‖2) remain bounded as the overall depth of the network grows (increasing L). Note that a similar initialization was proposed in Zhang et al. (2019) for training ResNets without batchnorm, albeit for a more restricted class of networks, and without an explicit dependency on width. Our result indicates that for narrow and deep networks with residual connections, training without batchnorm requires scaling in a both depth and width dependent manner.

heading: 4.3 DENSELY CONNECTED NETWORKS

text:
DenseNets have shown improvement over ResNets in terms of accuracy and speed of training on several notable image classification tasks, since their inception. As far as we can ascertain, there have been no theoretical studies on the causes of DenseNets success, or the implications on the training process of its architectural novelties, namely dense connections and feature reuse by concatenation of previous layers. In the following, it is shown that the DenseNet architecture, coupled with the standard, depth independent 2nl−1 initialization, gives rise to well-behaving gradients in any depth. By the definition of DenseNets given in Sec. 3, the reduced architecture outputs yl(k) are given by:
yl(k) = { φ( ∑l−1 l′=1W ll′>yl ′ ) l ≤ k
φ( ∑l−1 l′=kW ll′>yl ′ ) l > k
(20)
The following theorem states our results for DenseNets: Theorem 3. For a DenseNet as described in Sec, 3, it holds that for 0 < k ≤ L:
L(α−1) ( C1 exp
[ −2|∆|L
n
] − C2 ) ≤ var(‖Jk‖2) ≤ L2(α−1) ( C3 exp [ 2|∆|L n ] − C4 ) (21)
where C1, C2, C3, C4 are constants that do not depend on L.
It is worth noting the difference between DenseNets, and both vanilla and ResNet architectures. In vanilla architectures, the mean of the activation norm, as well as the gradient norm are exponential in α. However, the variance of the same quantities is exponential in ∑L l=1 1 nl
. That is, fixing the mean by correctly setting α = 1 does not prevent the gradients and activations from exploding in deep networks. In ResNets, scaling of the residual branches in order to avoid exploding gradients
requires scaling in a depth dependent fashion. However, in DenseNets, the variance of the squared Jacobian norm is in fact polynomial in depth for Gaussian distributions. Constant mean and variance is achieved (at least when ∆ = 0) by setting α = 1, for any depth. Moreover, the constant variance result is achieved with a linear growth rate of the weight complexity, instead of quadratic with vanilla networks.
Empirical support We employed Monte Carlo simulations in order to verify our theoretical findings. As shown in Fig. 2, there is an excellent match between the simulations and our derivations.

heading: 5 THE CURIOUS CASE OF CONCATENATED RELU

text:
Our results stated above demonstrate how different architectures and initialization schemes affect the training process at the start of training, by analyzing the expected norm and variance of the gradients for each layer, and hold for ReLU based architectures. Since a similar analysis can be performed on linear random networks, it is interesting to see the effect of the ReLU non-linearity on the outcome. As it turns out, the ReLU function has a detrimental effect on random networks, as shown in the following lemma, effectively exacerbating the fluctuations of both the activations and the gradients:
Lemma 3. Given a vanilla linear neural network with wlij ∼ N (0, 1nl−1 ), then it holds that:
E ( ‖yL‖2 ) = nL n , var ( ‖yL‖2 ) = n2L n2 ( L∏ l=1 (1 + 2 nL )− 1 ) (22)
Linear networks, of course, have limited capacity, considerably limiting their practical use. Fortunately, we can use the ReLU function to construct computation blocks that behave as linear networks at the initialization stage, while not compromising in terms of capacity. This can be achieved by the use of CR units. In concatenated ReLUs blocks, the input signal x is split into two complementary components x+ and x− such that the output of layer l is parameterized by two weight matrices W l1,W l2, and is given by yl = W l1>φ(yl−1)−W l2>φ(−yl−1). An algebraically equivalent way to write the layer’s computation is yl = W l2>yl−1 + (W l1>+W l2>)φ(yl−1), which can be viewed as a variant of a residual connection. However, it is important to note that this equivalence holds for the forward-pass only, since deriving byW l1 andW l2 during the optimization process is not the same as performing an optimization that is based on a derivation by W l1−W l2 and W l2. The equivalence at initialization between the CR based architectures and random linear networks is depicted in the following Lemma:
Lemma 4. The distribution of the output yl = W l1>φ(yl−1)−W l2>φ(yl−1) conditioned on yl−1, where wl1ij , w l2 ij ∼ N (0, αnl−1 ) equals the distribution of y = W l>yl−1, where the elements of W l are distributed according to an i.i.d normal distribution wlij ∼ N (0, αnl−1 ).
Using CR, therefore, provides initial conditions identical to random linear networks in terms of the output statistics. However, this equivalence also holds for back propagation. Indeed, from the construction of W l in the lemma, it is easy to see that ( ∂y l
∂wlij )2 = ( ∂y
l
∂wl1ij )2 + ( ∂y
l
∂wl2ij )2. A surprising
property emerges. Lem. 4 shows that similar to vanilla ReLU based networks, CR based ReLU networks have exponential behavior in ∑L l=1 2 nl . Since CR employ twice as many parameters, then
for the same budget of parameters (having nl = nl√2 for CR) we have ∑L l=1 2 √ 2 nl < ∑L l=1 5 nl
, hence more efficient than standard ReLU blocks. We can similarly define residual and densely connected architecture comprised of concatenated ReLU blocks. In that case, the conditions of both architectures in terms of output distributions at initialization will be identical to the linear counterparts of both architectures, given by yl = W lk1>φ(ỹl,k−1) + W lk2>φ(−ỹl,k−1) and yl = ∑l−1 l′=0W ll′>yl ′
for ResNets and DenseNets, respectively. Further evidence for the practical effectiveness of CR layers is provided in the appendix, in which we present experiments on the UCI datasets.

heading: 6 CONCLUSIONS

text: The interplay between architecture and initialization determines much of the early dynamics of training deep networks. In this work, we have demonstrated how careful initialization in general residual architectures effects the gradients at the start of training, by a rigorous study of the variance of the per layer gradient norm at the point of initialization. Through the use of the duality principle between forward and backward propagation, we have derived the expression for the variance in three architectures: standard networks, ResNets and DenseNets. We show that DenseNets benefit from a simple variance preserving initialization, which is independent of depth, while a depth dependent initialization exists for ResNet. We have also shown that CR blocks perform better then ReLU blocks, given a fixed budget of weights, when it comes to norm preservation in deep layers. As future work, we would like to extend our analysis to include normalization techniques, such as batchnorm.

heading: 7 PROOFS

text:
We make use of the following propositions and definitions in order to prove lemma 1 and theorem 1. For ResNet, we assume m = 2 for notation simplicity. The results hold for m > 2 as well with no additional arguments.
A path γt from input to output unit t defines a product of weights along the path denoted by
Qγt = |γt|∏ l=1 wγt,lzγt = |γt|∏ l=1 qγt,l (23)
where |γt| is the length of path γt (for vanilla and DenseNets |γt| = L), zγt is a binary variable zγt ∈ {0, 1} indicating if the path is "active" (i.e, all relevant Relu activations along the path are open), and wγt,l are the weights along path γt, and qγt,l = wγt,lzγt .
We generalize the above expression the following way:
Qγt = L∏ l=1 qγt,l (24)
where:
qγt,l = { 1 l /∈ γt w̃γt,lzγt,l else
(25)
where l /∈ γt indicates if layer l is skipped, zγt,l is the activation variable relevant for weight w̃γt,l. That is, if w̃γt,l = w l ij then zγt,l = z l j where z l j ∈ {0, 1} is the activation variable unit j in layer l. w̃γt,l denotes a generalized weight that can take the value of a weight w̃γt,l = wγt,l for vanilla layers, or a product of weights w̃γt,l = wγt,l1wγt,l2 for residual layers (wγt,l1 ∈W l1 and wγt,l2 ∈W l2). proposition 1. Given a random vector w = [w1...wn] such that each component is identically and symmetrically distributed iid random variable with moments E(wmi ) = cm, and random binary variable z such that z|w ∈ {0, 1}, z|w = 1− z| − w, then it holds that for n > l:
E( l∏ i=1 wmi z) =  0 m is odd, l is even (cm) l 2 m is even
E( ∏l i=1 w m i z) else
(26)
Proof. We have:
clm = ∫ w l∏ i=1 wmi p(w)dw = ∫ w|z=1 l∏ i=1 wmi p(w)dw + ∫ w|z=0 l∏ i=1 wmi p(w)dw (27)
= ∫ w|z=1 l∏ i=1 wmi p(w)dw + ∫ w|z=1 l∏ i=1 (−wi)mp(w)dw (28)
= ∫ w l∏ i=1 wmi zp(w)dw + ∫ w l∏ i=1 (−wi)mzp(w)dw (29)
For even m or even l: it follows that:
clm = 2 ∫ w l∏ i=1 wmi zp(w)dw (30)
and so:
E( l∏ i=1 wmi z) = clm 2
(31)
For odd l, since w is symmetrically distributed, we have that clm = 0, and so E( ∏l i=1 w m i z) = clm 2 = 0
proposition 2. For any set of paths γ1t , γ2t , it holds that:
E(Qγ1tQγ2t ) = { 0 γ1t 6= γ2t E(Q2
γ1t ) =
∏L l=1 E ( (qγ1t ,l) 2 ) γ1t = γ 2 t
(32)
Proof. From proposition 2 we have:
E(Qγ1tQγ2t ) = E( L∏ l=1 qγ1t ,lqγ2t ,l) (33)
Since the computations done by all considered architectures form a markov chain, such that the output of layer yl depends only on weights Rl = {W 1...W l}, using conditional expectation,:
E(Qγ1tQγ2t ) = E ( E(Qγ1tQγ2t ∣∣∣RL−1)) = E( L−1∏ l=1 qγ1t ,lqγ2t ,lE(qγ1t ,Lqγ2t ,L ∣∣∣RL−1)) (34) Note that since both are paths leading to output unit t, the following holds:
E(qγLt ,lqγ2t ,L ∣∣∣RL−1) =  E(w̃γ1t ,Lw̃γ2t ,Lz L t ) L ∈ γ1t , L ∈ γ2t E(w̃γ1t ,Lz L t ) L ∈ γ1t , L /∈ γ2t E(w̃γ2t ,Lz L t ) L /∈ γ1t , L ∈ γ2t
1 L /∈ γ1t , L /∈ γ2t
(35)
and so it follows from proposition 1:
E(qγLt ,lqγ2t ,L ∣∣∣RL−1) =  E(w̃2 γ1t ,L zLt ) L ∈ γ1t , L ∈ γ2t , w̃γ1t ,L = w̃γ2t ,L
1 L /∈ γ1t , L /∈ γ2t 0 else
= E ( (qγ1t ,L) 2 ) (36)
Recursively going through l = l − 1...1 completes the proof.
proposition 3. For any set of paths γ1t , γ2t , γ1s , γ2s , from input to output units t and s, it holds that:
E(Qγ1tQγ2tQγ1sQγ2s ) = L∏ l=1 E ( ξγ12st ,l ) (37)
such that:
E ( ξγ12st ,l ) =  E ( q2 γ1t ,l q2γ1s ,l ) qγ1t ,l = qγ2t ,l, qγ1s ,l = qγ2s ,l E ( q2 γ1t ,l q2 γ2t ,l ) qγ1t ,l = qγ1s ,l, qγ2t ,l = qγ2s ,l
0 else
(38)
Proof. The proof is practically identical to proposition 3, and will be omitted.
For notation simplicity,

heading: 7.1 PROOF OF LEMMA 1

text:
The proof of lemma 1 stems from the following observation: Since the computations done by all considered architectures form a markov chain, such that the output of layer yl depend only weights W 1...W l, then for any particular realization of the weights, yL,k and yLk differ only in their activation patterns in layers l ≥ k due to the removal of bypassing connections in yL(k). Using Eq. 23:
E ( ‖yL,k‖m ) = nL∑ t=1 E ( ( ∑
γt|k∈γt
|γt|∏ l=1 wγt,lzγt) m )
(39)
while:
E ( ‖yL(k)‖ m ) = nL∑ t=1 E ( ( ∑
γt|k∈γt
|γt|∏ l=1 wγt,lz ′ γt) m )
(40)
We must therefor prove the expectation is invariant to a switch between zγt and z ′ γt for layers l > k. For m = 2, using proposition 2, the expectation factorizes:
E ( ‖yL,k‖2 ) = nL∑ t=1 ∑ γ1t |k∈γt E(Q2γ1t ) = nL∑ t=1 ∑ γ1t |k∈γt L∏ l=1 E ( (qγ1t ,l) 2 )
(41)
Similarly for m = 4, from proposition 3 the expectation factorizes:
E ( ‖yL,k‖4 ) = nL∑ t=1 ∑ k∈γ1t ,γ2t ,γ1s ,γ2s L∏ l=1 E ( ξγ12st ,l ) (42)
where ξγ12st ,l is defined is Eq. 38. Note that switching the sign of W l for all architectures considered will switch the state of both zlj , 0 < j ≤ nl and z ′l j , 0 < j ≤ nl, and so from proposition 1, the factorized expectations for m = 2 and m = 4 meet the required invariance.

heading: 7.2 PROOF OF THEOREM 1

text:
From the definition of the Jacobian for weights W k, we have using lemma 1 and proposition 2:
E(‖Jkij‖2) = E(‖ ∂yL(k)
∂wkij ‖2) = nL∑ t=1 ∑ ijk∈γ1t ,γ2t E ( 1 (wkij) 2 L∏ l=1 Qγ1tQγ2t )
= nL∑ t=1 ∑ ijk∈γt E ( 1 (wkij) 2 L∏ l=1 Q2γt ) (43)
Since by definition wkij ∈ γ1t , from proposition 2 the term E (
1 (wkij) 2
∏L l=1Q
2 γ1t
) factorizes:
E ( 1
(wkij) 2 L∏ l=1 Q2γt ) = E( q2γt,k (wkij) 2 ) L∏ l 6=k,l=1 E(q2γt,l) = E( (wkij) 2zki (wkij) 2 ) L∏ l 6=k,l=1 E(q2γt,l) (44)
= E(zki ) L∏
l 6=k,l=1
E(q2γt,l) = 1
2 L∏ l 6=k,l=1 E(q2γt,l) = E 1 ck2 ( L∏ l=1 Q2γt )
(45)
where the last transition stems from proposition 1. Plugging back into Eq. 43 and summing over ij completes the proof for m = 2. For m = 4, we have:
E(‖Jk‖4) = E( ∑ ijuv ‖ ∂yL(k) ∂wkij ‖2‖ ∂yL(k) ∂wkuv ‖2)
= nL∑ t=1 nL∑ s=1 ∑ ijk∈γ1t ,γ2t ∑ uvk∈γ1s ,γ2s E ( 1 (wkij) 2(wkuv) 2 L∏ l=1 Qγ1tQγ2tQγ1sQγ2s ) (46)
From proposition 3, for uvk ∈ γ1s , γ2s , ijk ∈ γ1t , γ2t the expectation factorizes:
E ( 1
(wkij) 2(wkuv) 2 L∏ l=1 Qγ1tQγ2tQγ1sQγ2s ) = E ( ξγ12st ,k (wkij) 2(wkuv) 2 ) L∏ l 6=k,l=1 E ( ξγ12st ,l ) (47)
(48)
where from proposition 1 and proposition 3, for uvk ∈ γ1s , γ2s , ijk ∈ γ1t , γ2t :
E ( ξγ12st ,k
(wkij) 2(wkuv) 2
) =  E(ξ γ12st ,k ) (ck2 ) 2 {u, v} 6= {i, j} E(ξ γ12st ,k )
ck4 {u, v} = {i, j}
(49)
Note that since ck4 ≥ (ck2)2, it holds that:
E(ξγ12st ,k) ck4
≤ E ( ξγ12st ,k
(wkij) 2wkuv)
2 ) ) ≤
E(ξγ12st ,k) (ck2) 2 (50)
Plugging into Eq. 46, it follows:
var(‖yL(k)‖ 2)
ck4 ≤ var(‖Jk‖2) = E(‖Jk‖4)− E(‖Jk‖2)2 ≤
var(‖yL(k)‖ 2)
(ck2) 2
(51)
Furthermore, it holds that:
E(‖Jk‖4) = ∑ st ∑ ijk∈γ1t ,γ2t ∑ uvk∈γ1s ,γ2s E ( ξγ12st ,k (wkij) 2(wkuv) 2 ) L∏ l 6=k,l=1 E ( ξγ12st ,l ) (52)
= ∑ st ∑ ijk∈γ1t ,γ2t ∑ uvk∈γ1s ,γ2s E ( ξγ12st ,k (wkij) 2(wkuv) 2 )( 1{u,v}={i,j} + 1{u,v}6={i,j} ) L∏ l 6=k,l=1 E ( ξγ12st ,l ) (53)
Therefor for large width networks:
E(‖Jk‖4) ∼ ∑ st ∑ ijk∈γ1t ,γ2t ∑ uvk∈γ1s ,γ2s E ( ξγ12st ,k (wkij) 2(wkuv) 2 ) 1{u,v}6={i,j} L∏ l 6=k,l=1 E ( ξγ12st ,l ) (54)
= 1
(ck2) 2 ∑ st ∑ ijk∈γ1t ,γ2t ∑ uvk∈γ1s ,γ2s E ( ξγ12st ,k ) 1{u,v}6={i,j} L∏ l 6=k,l=1 E ( ξγ12st ,l ) (55)
∼ 1 (ck2) 2 E(‖yL(k)‖ 4) (56)
and so for large width networks:
var(‖Jk‖2) ∼ var(‖yL(k)‖ 2)
(ck2) 2
(57)

heading: 7.3 PROOF OF LEMMA 2

text:
Denoting by Zl the diagonal matrix holding in its diagonal the activation variables zlj for unit j in layer l, and so we have:
yl = ZlW l>yl−1 (58)
Conditioning on Rl−1 = {W 1...WL−1} and taking expectation: E ( ‖yL‖2|RL−1 ) = yL−1> E ( WLZLWL> ) yL−1 (59)
= nL∑ j=1 nL−1∑ i1,i2=1 yl−1i1 y l−1 i2 E ( wLi1,jw L i2,jz L j |RL−1 ) (60)
From proposition 1, it follows that: E ( ‖yL‖2|RL−1 ) =
nL nL−1
E ( ‖yL−1‖2 ) (61)
Recursing through l = L− 1...1: E ( ‖yL‖2 ) = nL n
(62)
Similarly:
E ( ‖yL‖4|RL−1 ) = E ( (yL−1>WLZLWL>yL−1)2 ) (63)
= ∑
j1,j2,i1,i2,i3,i4
yL−1i1 y L−1 i2 yL−1i3 y L−1 i4 E ( wLi1,j1w L i2,j1w L i3,j2w L i4,j2z L j1z L j2 |R L−1 )
(64)
From proposition 3:
E ( wLi1,j1w L i2,j1w L i3,j2w L i4,j2z L j1z L j2 |R L−1 ) (65)
= E ( wLi1,j1w L i2,j1w L i3,j2w L i4,j2z L j1z L j2 |R L−1 )( 1j1=j2,i1=i2=i3=i4 + 31j1=j2,i1=i2,i3=i4,i1 6=i3 ... (66)
+1j1 6=j2,i1=i2,i3=i4
) (67)
and so: E ( ‖yL‖4 ) = nLc L 4
2 ∑ i=1 E ( (yL−1i ) 4 ) + 6nL n2L−1 ∑ i1 6=i2 E ( (yL−1i1 ) 2(yL−1i2 ) 2 )
(68)
+ nL(nL − 1)
n2L−1
∑ i1,i2 E ( (yL−1i1 ) 2(yL−1i2 ) 2 )
(69)
= nL(c
L 4 − 3(cLc )2)
2
∑ i E ( (yL−1i ) 4 ) + nL(nL + 5) n2L−1 E ( ‖yL−1‖4 ) (70)
= nL∆
n2L−1 ∑ i E ( (yL−1i ) 4 ) + nL(nL + 5) n2L−1 E ( ‖yL−1‖4 ) (71)
finally:
nL(nL + 5 + ∆) n2L−1 E ( ‖yL−1‖4 ) ≤ E ( ‖yL‖4 ) (72)
≤ nL(nL + 5 + |∆|) n2L−1
E ( ‖yL−1‖4 ) (73)
Recursing through L − 1...1, and denoting C1 = nL(nL+5−|∆|)n2 , and C2 = nL(nL+5+|∆|)
n2 and combining with Eq. 62:
C1 L−1∏ l=1 (1 + 5− |∆| nl )− n 2 L n2 ≤ var ( ‖yL‖2 ) ≤ C2 L−1∏ l=1 (1 + 5 + |∆| nl )− n 2 L n2 (74)
Using ∀1≥x≥−1, e0.5x ≤ (1 + x) ≤ ex:
C1 exp [ L∑ l=1 5− |∆| 2nl ] − C2 ≤ var ( ‖yL‖2 ) ≤ C3 exp [ L∑ i=1 5 + |∆| nl ] − C4 (75)
For Gaussian distribution we have that ∆ = 0, and so:
var ( ‖yL‖2 ) = nL(nL + 5)
n2
L−1∏ l=1 (1 + 5 nl )− n 2 L n2 (76)

heading: 7.4 PROOF OF THEOREM 2

text:
In the following proof, for the sake of notation simplicity, we omit the notation k in yl(k), and assume that yl stands for the reduced network yl(k). We have for layer L:
E ( ‖yL‖2 ) = E ( ‖yL−1‖2 ) + E ( ỹL−1,m−1>WLmWLm>ỹL−1,m−1 ) = E ( ‖yL−1‖2 ) + αE ( ‖ỹL−1,m−1‖2 ) = E ( ‖yL−1‖2 )( 1 + αm
) = E ( ‖yk‖2
) L∏ l=k+1 ( 1 + αm ) = E ( ‖yk−1‖2 ) L∏ l=k+1 ( 1 + αm ) αm
= ∏ l 6=k ( 1 + αm ) αm (77)
E ( ‖yL‖4 ) = E ( ‖yL−1‖4 ) + E ( ‖ỹL−1,m‖4 ) + 4E ( (ỹL−1,m>yL−1)2 ) + 2E ( ‖ỹL−1,m‖2‖yL−1‖2 ) (78)
We now handle each term separately: E ( ‖ỹL−1,m‖4 ) = E ( E ( ‖ỹL−1,m‖4|RL−1 )) (79)
Similarly to the vanilla case with a linear weight layer on top, we have:
α2m(1 + 5− |∆| n
)m−1‖yL−1‖4 ≤ E ( ‖ỹL−1,m‖4|RL−1 ) (80)
≤ α2m(1 + 5 + |∆| n )m‖yL−1‖4 (81)
E ( (ỹL−1,m−1>yL−1)2 ) = ∑
j1j2i1i2
E ( ỹL−1,m−1i1 ỹ L−1,m−1 i2 yL−1j1 y L−1 j2 wLmi1,j1w Lm i2,j2 ) (82)
= α n E ( ‖ỹL−1,m−1‖2‖yL−1‖2 ) = αm n E ( ‖yL−1‖4 ) (83)
and: E ( ‖ỹL−1,m‖2‖yL−1‖2 ) = αmE ( ‖yL−1‖4 ) (84)
Plugging it all into Eq. 78, and denoting:
β+l = 1 + 2α m(1 +
2 n ) + α2m(1 + 5 + |∆| n )m (85)
β−l = 1 + 2α m(1 +
2 n ) + α2m(1 + 5− |∆| n )m−1 (86)
we have after recursing through l = L− 1...1:
E ( ‖yk‖4 ) L∏ l=k+1 β−l ≤ E ( ‖yL‖4 ) ≤ E ( ‖yk‖4 ) L∏ l=k+1 β+l (87)
Since for the reduced architecture yL(k), the transformation between y k−1 and yk is given by an m layer fully connected network without any residual connections, we can use the results from the vanilla case:
L∏ l 6=k β−l α 2m(1 + 5− |∆| n )m−1 ≤ E ( ‖yL‖4 ) ≤ L∏ l 6=k β+l α 2m(1 + 5 + |∆| n )m (88)
Denoting ρ± = α2(1 + 5±|∆| n ) it follows:
C1 L∏ l 6=k β−l ρ m − ≤ E ( ‖yL‖4 ) ≤ L∏ l 6=k β+ρm+ (89)
From the definition of β±l , it holds for ρ+ < 1:
β+l ≤ ( 1 + ρ m 2 + )2 ≤ exp [ 2ρ m 2 + ] (90)
and:
β−l ≥ ( 1 + ρm− ) ≥ exp [ 1
2 ρm−
] (91)
and so:
C1ρ m − exp
[ 1
2 Lρm−
] − C2µ2 ≤ var ( ‖yL‖2 ) ≤ C3ρm+ exp [ 2Lρ m 2 + ] − C3µ2 (92)
For Gaussian distributions, using a similar derivation and assigning ∆ = 0 we have:
E ( ‖yL‖4 ) = ρ L∏ l 6=k βl (93)
where:
βl = 1 + 2α m(1 +
2 n ) + α2m(1 + 5 n )m−1(1 + 2 n ) (94)
and:
ρ = a2m(1 + 5
n )m−1(1 +
2 n ) (95)

heading: 7.5 PROOF OF THEOREM 3

text:
In the following proof, for the sake of notation simplicity, we omit the notation k in yl(k), and assume that yl stands for the reduced network yl(k). We have:
E ( ‖yL‖2 ) = µL = E ( ( L−1∑ l=k yl>WLl)ZL( L−1∑ l=k yl>WLl) ) = aL L L−1∑ l=k µl−1 (96)
E ( ‖yL‖4 ) = E (( L−1∑ l=k (yl>WLl)ZL L−1∑ l=k (yl>WLl) )2)
= E (( L−1∑
l1=k (yl1>WLl1)ZL L−1∑ l2=k (yl2>WLl2) L−1∑ l3=k (yl3>WLl3)ZL L−1∑ l4=k (yl4>WLl4) ) (97)
Note that the above is a simple Relu block with concatenated y1...yL − 1 as input. Using the results from the vanilla architecture, and denoting Cl,l′ = E ( ‖yl‖2‖yl′‖2 ) , it then follows:
(n+ 5− |∆|)α2
nL2
L−1∑ l1,l2=k Cl1,l2 ≤ CL,L ≤ (n+ 5 + |∆|)α2 nL2 L−1∑ l1,l2=k Cl1,l2 (98)
From Eq. 98, it holds that:
n(L− 1)2
n+ 5 + |∆| CL−1,L−1 ≤ L−2∑ l1,l2=k Cl1,l2 ≤ n(L− 1)2 n+ 5− |∆| CL−1,L−1 (99)
It then follows:
E(‖yL‖4) = CL,L ≤ α2
L2 (1 + 5 + |∆| n ) L−1∑ l1,l2=k Cl1l2
= α2
L2 (1 + 5 + |∆| n
) ( CL−1,L−1 + L−2∑ l1,l2=k Cl1l2 + 2 L−2∑ l=k CL−1,l )
= α2
L2 (1 + 5 + |∆| n
) ( CL−1,L−1 +
(L− 1)2n a2L−1(n+ 5− |∆|) CL−1,L−1 + 2 L−2∑ l=k CL−1,l ) (100)
(101) The following also holds:
∀l1>l2≥k, Cl1,l2 = E ( ( l1−1∑ l=k yl>W l1,lZl1)2‖yl2‖2 ) = α l1 l1−1∑ l=k Cl,l2 (102)
and so:
CL,L ≤ (n+ 5 + |∆|)α2
nL2
( CL−1,L−1 +
(L− 1)2n α2(n+ 5− |∆|) CL−1,L−1... (103)
+ 2α
L− 1 L−2∑ l1=k L−2∑ l2=k Cl1,l2 ) (104)
= (n+ 5 + |∆|)α2
nL2
( CL−1,L−1 +
(L− 1)2n α2(n+ 5− |∆|) CL−1,L−1 (105)
+ 2n(L− 1)
α(n+ 5− |∆|) CL−1,L−1
) (106)
= (n+ 5 + |∆|)α2
nL2 CL−1,L−1
( 1 +
(L− 1)2n α2(n+ 5− |∆|) + 2n(L− 1) α(n+ 5− |∆|)
) (107)
= CL−1,L−1 (n+ 5 + |∆|) (n+ 5− |∆|) ((α L + α(L− 1) Lα )2 + α2(5− |∆|) nL2 ) (108)
CL,L ≤ CL−1,L−1 ( 1 + 2|∆|
n+ 5− |∆|
)(( 1 +
α− 1 L
)2 + α2(5− |∆|)
nL2
) (109)
= CL−1,L−1
( 1 +
2|∆| n+ 5− |∆|
)( 1 +
α2(5− |∆|) n(L+ α− 1)2
)( 1 +
α− 1 L
)2 (110)
Telescoping through l = L− 1...1:
CL,L ≤ ( 1 + 2|∆|
n+ 5− |∆| )L−k+1 L∏ l 6=k (( 1 + α2(5− |∆|) n(l + α− 1)2 )( 1 + α− 1 l )2) (111)
≤ exp [ 2|∆|(L− 1) n+ 5− |∆| ] exp [∑ l 6=k α2(5− |∆|) n(l + α− 1)2) ] exp [∑ l 6=k 2(α− 1) l ] (112)
∼ exp [ 2|∆|(L− 1) n+ 5− |∆| ] exp [ α2(5− |∆|) nL ] L2(α−1) (113)
∼ C1 exp [ 2|∆|L n ] L2(α−1) (114)
A similar relation holds for the mean:
µL = α
L L−1∑ l=k µl = α L ( µL−1,L−1 + (L− 1) α )µL−1,L−1 ) (115)
µ2L = µ 2 L−1,L−1
( 1 +
α− 1 L
)2 ≤ L2(α−1) (116)
Finally:
var(‖yL‖2) = CL,L − µ2L (117)
≤ L2(α−1) ( C1 exp [ 2|∆|L n ] − 1 )
(118)
A lower bound can easily be derived using Eq. 98, 99, and follow the same derivation by flipping the sign of |∆|:
L(α−1) ( C1 exp
[ −2|∆|L
n
] − C2 ) ≤ var(‖yL‖2) ≤ L2(α−1) ( C3 exp [ 2|∆|L n ] − C4 ) (119)
For Gaussian distributions, using a similar derivation and assigning ∆ = 0 we have:
CL,L = L∏ l 6=k (( 1 +
5α2 n(l + α− 1)2 )( 1 + α− 1 l )2)(n+ 5 nk2 ) a2 (120)
µ2L = L∏ l 6=k ( 1 + α− 1 l )2 a2 k2
(121)
and so: var(‖yL‖2) = ( a2 (n+ 5 nk2 ) L∏ l 6=k ( 1 +
5α2 n(l + α− 1)2 ) − a 2 k2 ) L∏ l 6=k ( 1 + α− 1 l )2 (122)

heading: 7.6 PROOF OF LEMMA 3

text: The proof is identical to the Relu case, removing the activation variables Zl, and hence will be omitted.

heading: 7.7 PROOF OF LEMMA 4

text:
Proof. We construct the matrix W l as follows:
wlij =
{ wl1ij y
l−1 ≥ 0 wl2ij y l−1 < 0 (123)
And so yl = W l>yl−1. Note that the elements of W l are i.i.d Gaussian random variables wlij ∼ N (0, αnl−1 ).

heading: 8 EMPIRICAL SUPPORT FOR CONCATENATIVE RELU

text:
Our theoretical results are verified in Fig. 3. As can be seen, the simulations closely match the predictions. The advantage of CR over conventional ReLU networks is also clearly visible.
CR has fallen out of flavor and was never shown to be effective outside CNNs. We, therefore, provide empirical support for its effectiveness, to which our analysis above points. In our experiments, we evaluate the performance of fully connected networks on the 40 UCI datasets with more than 1000 samples. The train/test splits were provided by Klambauer et al. (2017). In the experiment, we tested three different depths: 8, 16, and 32. Each layer contained n = 256 hidden neurons. Dropout was not employed. A learning rate of either 0.1, 0.01, or 0.001 was used for the first 50 epochs and then a learning rate of one tenth for an additional 50 epochs. All runs were terminated after 100 epochs. Batches were of size N = 50.
Following Klambauer et al. (2017), an averaging operator with a mask size of 5 was applied to the validation error, and the epoch with the best smoothed validation error was selected. This was done separately for each method, each dataset, and each split. Out of the nine options of depth and learning rate for most methods, the mean validation error across the four splits was used to select the option for which we report the results on the test splits. We compared the following activation functions and architectures: vanilla neural networks (single pathway) with either SELU (Klambauer et al., 2017) or ELU (Clevert et al., 2015) activation functions, ResNets, and CR based architecture. The single pathway ReLU networks were not competitive and the experiments with this architecture were terminated to allow for more experiments with the other architectures. The single pathway experiments were done without batchnorm, as is usually done with ELU and SELU. For ResNets, we report results both with batchnorm and without. Batchnorm was applied along the residual pathway, twice, as is typically practiced. The first and last layers of the ResNet and CR architecture, i.e., the layers that project from the input and to the output layer, are conventional projections that do not employ multiple pathways. For the baseline architectures, we also evaluate using double width, i.e.,
each layer had 512 hidden neurons. This was done since CR employs more weights than the baselines due to the dual pathway architecture.
In Fig. 4, we provide the Dolan-More profile of the methods. In this plot, the x-axis is a threshold τ and the y-axis is the ratio, out of all datasets, in which the method has reached an accuracy that is τ times the best accuracy for the dataset. It can be seen that the CR method dominates across all threshold values, except for SELU double width at low values of τ .

heading: 9 UCI RESULTS

text: In Tab. 1 we provide the full numbers of the UCI experiments in the paper.