# Adaptive Low-Rank Regularization with Damping Sequences to Restrict Lazy
Weights in Deep Networks

Mohammad Mahdi Bejani  Department of Mathematics and Computer Science,
Amirkabir University of Technology (Tehran Polytechnic), Iran, e-mails:
<EMAIL_ADDRESS>Mehdi Ghatee  Department of Mathematics and Computer
Science, Amirkabir University of Technology (Tehran Polytechnic), Iran,
e-mails<EMAIL_ADDRESS>
###### Abstract

Overfitting is one of the critical problems in deep neural networks. Many
regularization schemes try to prevent overfitting blindly. However, they
decrease the convergence speed of training algorithms. Adaptive regularization
schemes can solve overfitting more intelligently. They usually do not affect
the entire network weights. This paper detects a subset of the weighting
layers that cause overfitting. The overfitting recognizes by matrix and tensor
condition numbers. An adaptive regularization scheme entitled Adaptive Low-
Rank (ALR) is proposed that converges a subset of the weighting layers to
their Low-Rank Factorization (LRF). It happens by minimizing a new Tikhonov-
based loss function. ALR also encourages lazy weights to contribute to the
regularization when epochs grow up. It uses a damping sequence to increment
layer selection likelihood in the last generations. Thus before falling the
training accuracy, ALR reduces the lazy weights and regularizes the network
substantially. The experimental results show that ALR regularizes the deep
networks well with high training speed and low resource usage.

###### keywords:

Deep Neural Network, Regularization, Overfitting, Matrix Decomposition,
Damping Coefficients, Lazy Weights.

††journal: Neural Networks

##  1 Introduction

In the supervised machine learning, the complexity of the learning function
$f$ is a critical concept. It can be defined as [1]:

$R(f)=\int\|\frac{\partial f}{\partial x}\|_{2}^{2}dx$ (1)

When the model complexity is high or $R(f)$ is significant, a small noise in
the input causes a substantial change in the output, and the generalization
fails, or overfitting occurs. In deep neural networks, because of their
intrinsic complexity, the model tends to memorize the samples, and the
generalization power reduces [2]. Different regularization methods are defined
to impose a dynamic noise to the model through the training procedure [3]. One
of the most popular techniques is dropout [4], and its family [5, 6, 7, 8, 9,
10]. In these methods, in each iteration, a subset of weights of the neural
network is selected to train. Some of these methods, such as [6, 7], impose
small noise on the model weights. Using noise on the weights does not allow
just memorizing the training data. Some other methods select a subset of loss
functions to regularize the network [11].
However, many regularization techniques impose the noise on all components of
the learning model blindly. They do not note the time and place of the
overfitting occurrence. It is the reason for the slow convergence of their
training process. Abpeikar et al. [12] proposed an expert node in the neural
trees to evaluate the overfitting, and when it was high, they used
regularization. Bejani and Ghatee [13] introduced the adaptive regularization
schemes, including the adaptive dropout and adaptive weight decay to control
overfitting in the deep networks. But their methods add some hyper-parameters
to the learning procedure, and determining these hyper-parameters is not easy.
Therefore, to determine the hyper-parameters concerning the overfitting, they
used matrix decomposition to regularize the learning model [14]. Various
matrix decomposition methods such as spectral decomposition, nonnegative
matrix factorization, and Low-Rank Factorization (LRF) have been proposed to
summarize the data of a matrix (or a tensor) [15]. To apply these methods in
the data mining fields, one can note [16]. They are also good options for
simplifying matrix weights in deep neural networks. In this regard, some
attempts are very effective [17, 18, 19]. In a recent paper, Tai et al. [20]
used low-rank tensor decomposition to remove the redundancy in CNN kernels.
Also, Bejani and Ghatee [14] derived a theory to regularize deep networks
dynamically by using Singular Value Decomposition (SVD). In adaptive version
of this technique, namely ASR, the following loss function was minimized:

$E^{*}(\theta_{t})=E(\theta_{t})+\gamma||W-W_{V}^{*}||_{F}^{2}$ (2)

where $\theta_{t}=\\{W_{t},b_{t}\\}$ show the synaptic weights and the bias
vector, $\gamma$ is a regularization parameter, and $W_{V}^{*}$ is the SVD
decomposition of the best-found weights on validation data. As mentioned by
[14], ASR solves the overfitting substantially.
In continuation of these works, in this paper, we define a new measure based
on the condition number of the matrices to detect when the overfitting occurs.
We also identify the layers of a deep neural network that cause the
overfitting problem. To solve this problem, we decompose the ill-posed
matrices into low-rank matrices. We developed two new regularization schemes,
namely Direct Low-Rank (DLR) and Adaptive Low-Rank (ALR). These methods can
compete with the famous regularization methods in dropout family. These
results will be supported by some experiments on small-size and large-scale
datasets, separately. We also visualize the behavior of DLR on a noisy dataset
to show how LRF solves overfitting. Finally, the results of ALR are compared
with some famous regularization schemes including dropout methods [6, 7, 8, 9,
10], adaptive dropout method [13], weight decay with and without augmentation
methods [21, 22, 23, 24].
In what follows, we present some preliminaries in Section 2. In sections 3 and
4, DLR and ALR are expressed. In Section 5, we present the results of
empirical studies. The final section ends the paper with a brief conclusion.

##  2 Preliminaries

The overfitting of a supervised learning model such as a neural network is
related to the condition number of the following nonlinear system:

$\sum_{i=1}^{T}\|f(x_{i},\\{W^{1},...,W^{L}\\})-y_{i}\|_{F}^{2}=0,$ (3)

where $f$ is the output of the neural network with $L$ layers. $W^{l}$ is the
weight matrix (or tensor) of the layer $l.$ $T$ is the number of training
samples, and $(x_{i},y_{i})$ is the pair of the input and output of the
$i^{th}$ sample. After solving this nonlinear system and finding $w_{i}$s, the
learning model predicts the output for the unseen data. In numerical algebra,
the condition number of a system shows the stability of the solution directly
[25]. When the condition number is great (very greater than 1), the system’s
sensitivity over the noise is very high, so the learning model’s
generalization ability decreases significantly. Thus, it is a good idea to
evaluate the learning model’s complexity by condition number [25]. The
condition number is defined for linear and nonlinear systems. For a linear
system $Ax=b,$ where $A\in\mathbb{R}^{m\times n}$, $x\in\mathbb{R}^{n}$, and
$b\in\mathbb{R}^{m}$, the condition number is defined as
$\kappa(A)=\|A\|\|A^{-1}\|$ [25]. Also, for the non-linear system $f(x)=y$
where $f$ is a non-linear vectorized function, the condition number is [26]:

$\kappa(f(\theta))=\frac{\|J(\theta)\|_{F}\|\theta\|_{F}}{\|f(\theta)\|_{F}},$
(4)

where $\|.\|_{F}$ is Frobenius norm, $\theta$ is parameters of $f$, and
$J(\theta)$ is Jacobian matrix of $f$ concerning $\theta$.

###  2.1 Matrix factorization

In this part, we discuss popular matrix factorization (decomposition) and show
their ability to improve system stability. Consider an arbitrary matrix $A$
that is factorized into $r$ matrices $B_{i}$ and $A=\prod_{i=1}^{r}B_{i}$. In
some instances, LU decomposition, Cholesky decomposition, Singular Value
Decomposition (SVD), nonnegative matrix decomposition, and binary
decomposition can determine the factors [27]. Now, we focus on the Low-Rank
Factorization (LRF) that approximates any matrix $A$ with two lower rank
matrices $V$ and $U$. For a better approximation, the following optimization
problem can be solved:

$\min_{W,H}\|A-VU\|_{F}$ (5)

Thus, when $A\in R^{n,m},$ LRF factorizes $A$ into two matrices $V\in R^{n,k}$
and $U\in R^{k,m}$ and $Rank(U)=Rank(V)=k<Rank(A).$ To find $U$ and $V$ by
optimization model 5, see [28].

###  2.2 Tensor factorization

There are two main approaches to factorize a tensor; explicit and implicit. In
the explicit factorization of any tensor $T$, we try to find $r$ sets of
vectors $a_{i}$, $b_{i}$ and $c_{i}$ such that
$\sum_{i=1}^{r}(a_{i}b_{i}^{T})\odot c_{i}$ approximates $T$, where $\odot$ is
the tensor production. By minimizing $\|T-\sum_{i=1}^{r}(a_{i}b_{i}^{T})\odot
c_{i}\|_{2}^{2},$ we can factorize $T$ into $r$ components [20]. However, the
explicit tensor decomposition is an NP-hard problem[29]. Therefore, this type
of decomposition is not the best way for the regularization of deep networks.
Instead, in implicit factorization, we try to apply the matrix factorization
methods directly. To this aim, any tensor $T$ is sliced into some matrices,
and on every matrix, we apply the matrix factorization. Our results show the
efficiency of this approach for deep learning regularization.

###  2.3 Visualization of factorization effects

To visualize the effect of matrix and tensor factorization as the
regularization method, we designed a test to show how they can improve the
learning models. To this end, we used a perceptron neural network with three
hidden layers to train Iris dataset [30] and Iris data with high-level
artificial noise. Figures 1(a) and 1(b) show two surfaces trained by the
original dataset and noisy dataset, respectively. As one can see, the second
learning model is over-fitted because of noisy data. In the third experiment,
we substitute LRF of the weighting matrices instead of the second learning
model’s matrices for regularization purposes. Fig. 1(c) shows the new surface.
It is trivial that the regularized network is more similar to the original
learning model without overfitting noisy data. Also, the model is simpler.

(a) Trained surface on original data.

(b) Trained surface on noisy data.

(c) Trained surface on noisy data when LRF regularization is used.

Figure 1: The learning model’s surface that is trained by a Perceptron Neural
Network (MLP) on Iris dataset. Figure 2: Visualization of Theorem 1: For each
$k$, the top point shows the error value after exchanging trained weights
$W^{*}$ with $LRF_{k}(W^{*})$, and the low point shows the error value after
one retraining epoch.

##  3 Details of DLR

DLR is a regularization technique that contains the following fundamental
steps:

  1. 1.

Detecting the overfitting in successive steps,

  2. 2.

Identifying the matrices with a significant effect on overfitting and defining
a probability distribution on these matrices,

  3. 3.

Selecting some over-fitted matrices randomly based on the distribution
achieved from the previous step,

  4. 4.

Using LRF to regularize the selected matrices and the tensors.

The DLR details are presented in Algorithm 1. This algorithm evaluates the
overfitting dynamically [13]. When the overfitting is small, the learning
procedure continues; else, the regularization method affects the over-fitted
model. Such a scheme saves the training speed and increases the generalization
ability. The following measures the level of model overfitting dynamically:

$v(t)=\frac{Error_{Validation}(t)}{Error_{Train}(t)},$ (6)

where $t$ is the iteration number. It is worth noting that $v(t)$ has an
oscillatory behavior and iteratively decreases and increases. Therefore, we
get the average of the last three $v(t)$. Instead of three, we can use a
hyper-parameter $p$ as patient of regularization. When the overfitting is
recognized, the learning algorithm identifies the overfitting reason and tries
to resolve this problem. Because of the layered architecture of deep networks,
it is possible to find some of the layers that cause overfitting. We
regularize them by LRF to remove the effects of data noises in the weighting
matrices. However, it keeps the major trend of data. It leads to a softer
surface (as mentioned in Fig.1(c)).

Finding a sub-set of the layers with the highest effect on overfitting is
hard. Instead, we return to the training system 3 and compute the complexity
of each layer by its condition number 4. Denote the condition number of
$l^{th}$ layer with $\kappa(f_{l})$. We are ready to regularize the weighting
matrices with great $\kappa(f_{l}).$ But, the experiments show that
regularization on each over-fitted matrix increases the processing time. Thus,
similar to dropout [4], we sample a random number by
$Bernoulli(\Gamma(f_{l}))$ distribution, that is defined by Eg. (7). When the
produced random number is less than the following normalized parameter, we use
LRF regularization to simplify the weighting matrices:

$\Gamma(f_{l})=\frac{\kappa(f_{l})}{\max_{i}\kappa(f_{i})}.$ (7)

Because the convolution layers are tensors, they are sliced to matrices with
$FS\times FN$, where $FS$ and $FN$ are the filter size and the filter number,
respectively. Then, the algorithm approximates these matrices directly.

Furthermore, LRF can approximate any matrix with its $k-$rank factorization.
The following theorem shows that LRF regularization is independent of the
value of $k$ in linear learning models.

Figure 3: The training and testing errors of a non-linear network by getting
LRF in some epochs of Algorithm 1.

######  Theorem 1.

Assume $f(x;W)=Wx+b$ is a neural network with linear activation function, $W$
is the weights matrix, and $x$ is an input vector with zero and $\sigma^{2}$
as the mean and the variance. Assume all features of $x$ are independent. Let
$W^{*}$ shows the optimal training weights. For any $k<rank(W^{*})$, if
$W_{k}=LRF_{k}(W^{*})$ is substituted instead of $W^{*}$ in the network, after
one epoch of the retraining, the optimal weights converge to $W^{*}$.

Proof. See appendix A
For visualizing the effect of Theorem 1, we trained a linear network on a
dataset with $\mathcal{N}(\vec{0},I)$ distribution and found the optimal
weights $W^{*}$. Now, for any $k\in\\{1,...,20\\}$, we defined
$W_{k}=LRF_{k}(W^{*})$ and substitute $W_{k}$ instead of $W^{*}$. Then, we
retrained the network one epoch and found the loss values again. Fig. 2 shows
that, for all $k$, the loss values converge to the originally trained
network’s loss value.
Besides, some evidence shows the prediction of Theorem 1 meets for non-linear
cases after several retraining epochs. For instance, we trained a network on
the SVHN dataset by Algorithm 1 and got LRF from some weights along the
training epochs. Fig.3 shows the network’s loss values on the training and the
testing datasets. After substituting LRF instead of the weights, the network’s
loss values increase, but after a few epochs, they converged to the error
before LRF getting. But the returning does not happen in one epoch, similar to
the linear models. This evidence supports the following conjecture.

######  Conjecture 1.

Assume $f(x;W)$ is a neural network with non-linear activation function and
$x\sim\mathcal{(}\vec{0},\Sigma)$, where $\vec{0}$ is a zero vector as the
means, and $\Sigma$ is the covariance of features of the training dataset.
Suppose that $f(x;W)$ is trained and the optimal weights are $W^{*}$ with the
optimal error $E(W^{*})$. Assume $W^{*}$ is exchanged by $W_{k}=LRF(W^{*})$
and the network is retrained on the dataset with $O(L\|\Sigma\|_{2})$ epochs.
Then, the network weights $W^{**}$ and the network error $E(W^{**})$ satisfy
the following:

$E(W^{**})\leq E(W^{*})$

.

The preferences of DLR regularization compared with ASR [14] can be summarized
as the following:

  1. 1.

It is independent of the validation dataset, and DLR detects the overfitting
by condition number.

  2. 2.

In each training epoch, some weight matrices (in our experiments, usually 25%
of the weights) are substituted with their LRF. This selection increases the
training speed and decreases resource usage.

  3. 3.

Based on Theorem 1, we set $k=1$ in all experiments. Thus the approximation of
matrices can be computed by two vectors, and the computations become faster
than ASR.

  4. 4.

The vanishing of SVD [14, Theorem 4] does not happen in DLR because the
weights are randomly selected based on a Bernoulli distribution concerning the
condition number.

Algorithm 1 Training Algorithm with DLR

0: $\alpha_{t}$: Step-size

0: $D_{t}$: Improvement Direction

0: $t\leftarrow 0$: Time-step

0: $\theta_{t}\leftarrow\\{W_{t},b_{t}\\}$: Weights and biases of the neural
network.

0: $E(\theta_{t})$: Error function of the network.

0: $W$: number of the weights in the network.

0: $L$: number of the trainable layers in the network.

0: $\epsilon$: an small positive threshold.

1: while $\|\bigtriangledown_{\theta}E(\theta_{t})\|>\epsilon$ do

2: $g_{t+1}\leftarrow\bigtriangledown_{\theta}E(\theta_{t})$

3: $D_{t+1}\leftarrow DescentDirection(g_{t+1},\alpha_{t+1})$ that is a
function that returns an improvement direction based on the inputed gradient
and step-size $\alpha_{t+1}$.

4: $\theta_{t+1}\leftarrow\theta_{t}-D_{t+1}$

5: $v(t)\leftarrow\dfrac{E_{Validation}(t)}{E_{Train}(t)}.$

6: if $v(t)$ increases then

7: for all layers $l\in\\{1,...,L\\}$ and any weights tensor $W^{l}$ and bias
vector $b^{l}$ do

8: Compute the $\kappa(f_{l})$ by Eq. 4.

9: end for

10: for all layers $l\in\\{1,...,L\\}$ and any weights tensor $W_{l}$ do

11: Compute $\Gamma(f_{l})$ based on Eq. 7

12: $r\leftarrow rand(0,1)$

13: if $r\leq\Gamma(f_{l})$ then

14: $W^{l}\leftarrow LRF(W^{l})$.

15: end if

16: end for

17: $b^{l}_{t+1}\leftarrow b^{l}_{t}$

18: end if

19: $t\leftarrow t+1$

20: end while

21: return $\theta_{t}$

##  4 Details of ALR

The experimental results show that DLR prefers the other regularizers for
shallow networks and can compete with other regularization schemes. However,
DLR results in the deep networks are not the best when the model complexity is
high. To solve this problem, the DLR is combined with the Thikonov
regularization scheme presented in Eq. (2). To this end, we minimize the
following new loss function:

$E^{*}(\theta_{t})=E(\theta_{t-1})+\gamma\sum_{l\in\mathcal{W}}\|W_{t-1}^{l}-LRF(W_{t-1}^{l})\|_{F}^{2},$
(8)

where $\mathcal{W}\subseteq\\{1,...,L\\}$ is a sub-set of the layers, $W^{l}$
is the weights of the $l^{th}$ layer, $\theta_{t}$ is the network weights in
epoch $t$, and $\gamma=\frac{1}{|\mathcal{W}|}$ is a fixed parameter. In each
training epoch, a new $\mathcal{W}$ is selected based on
$Bernoulli(\Gamma(f^{l}))_{l\in\\{1,...,L\\}}$. If the condition number of
$l^{th}$ layer is great, its chance for participating in the regularization
term increases.

ALR method found and solved the following three problems:

  * 1.

[14] proved that the effect of matrix approximation in ASR decreases when
training epochs grow up. Then, the regularization term’s effect is scarce at
the end of the training procedure, while the overfitting problem possibly
occurs. The same problem remains in the DLR method.

  * 2.

The matrix approximation in the last training epochs corrupts the learning
model’s performance.

  * 3.

The third problem happens because of lazy weights. It is worth noting that
some of the network weights do not contribute to the regularization process
along the training epochs. Probably, they appear at the last training epochs.
However, the training terminates soon, and they have not enough occasion to
tune-up. We entitled them as lazy weights. We increase their selection
probability when the epochs grow. This approach encourages them to contribute
in more regularization steps. A damping sequence $DS(t)$ is used for epoch $t$
to increase the likelihood of layer selection in the last training epochs:

$\text{Prob($f_{l}$ selection at epoch t)}=\frac{\Gamma(f_{l})}{DS(t)}.$ (9)

The resulted ALR does probably similar to ASR in more training epochs and
restricts lazy weights occurrence. We experimentally show that
$DS(t)=\frac{1}{\log{(t)}}$ is a suitable damping sequence when $t\geq 2$. In
the following, we show the effect of lazy weights on training procedures.

Details of ALR is given in Algorithm 2. To analyze ALR, we study the
following.

Algorithm 2 Training Algorithm with ALR

0: Damping sequence $DS(t)$.

0: Similar to Algorithm 1.

1: while $\|\bigtriangledown_{\theta}E^{*}(\theta_{t})\|>\epsilon$ do

2: $\mathcal{W}\leftarrow\emptyset$

3: for all layers $l\in\\{1,...,L\\}$ and any weights tensor $W^{l}$ do

4: Compute $\Gamma(f_{l})$ based on Eq. 7

5: $r\leftarrow rand(0,1)$

6: if $DS(t)r\leq\Gamma(f_{l})$ then

7: $\mathcal{W}\leftarrow\mathcal{W}\cup\\{l\\}$.

8: end if

9: end for

10:
$g_{t+1}\leftarrow\bigtriangledown_{\theta}\Big{[}E(\theta_{t})+\frac{1}{|\mathcal{W}|}\sum_{l\in\mathcal{W}}\|W^{l}_{t}-LRF(W^{l}_{t})\|_{F}^{2}\Big{]}$

11: Do similar to Steps 3 and 4 of Algorithm 1.

12: $t\leftarrow t+1$

13: end while

14: return $\theta_{t}$

######  Lemma 1.

If $D=\\{x_{i},y_{i}\\}_{i=1}^{T}$ is an arbitrary classification dataset and
$f(x;\tilde{W})=y$ is a linear classifier with trained weights
$\tilde{W}\in\mathbb{R}^{m\times n}$, then rank of $\tilde{W}$ is greater than
one.

Proof. See appendix B

######  Theorem 2.

If a neural network, $f(x;\theta)$, is trained on an arbitrary dataset with
ARL, and $W^{*}$ is a lazy weight that is selected for the ARL regularization
term, then the model accuracy drops in the next training iteration.

Proof. See appendix C

Finally, by considering [31, Theorem 1], we can directly conclude that
Rademacher complexity [32] of the neural networks decreases by using either
DLR or ALR. Actually, in Step 14 of DLR, the LRF of matrices are substituted
as the original weights. Also in Step 10 of ALR, the weights are implicitly
converge to their LRF, because when $g_{t+1}\rightarrow 0$, both
$E(\theta_{t})$ and $\|W^{l}_{t}-LRF(W^{l}_{t})\|_{F}^{2}$ converges to zero
for all layer $l\in\mathcal{W}$. Thus, the results are direct.

##  5 Empirical studies on DLR

In this section, the DLR results are compared with the other regularization
methods. Also, we check its performance to control the overfitting in the
different datasets. DLR is applied on both shallow and deep networks. To use
DLR implementation, one can refer to
Github111https://github.com/mmbejani/MatrixFactorizationRegularization.

###  5.1 Effect of condition number in DLR

To present the effect of condition number expressed in Eq. 7 in the
performance of DLR, consider the following scenarios:

  1. 1.

The first $k$ layers of the network are regularized when the overfitting
occurs. In this scenario, the weight matrices of the first $d$ layers are
factorized by LRF, and their approximations are substituted as the new weights
matrices.

  2. 2.

The last $d$ layers of the network are used for the same regularization plan.

  3. 3.

This scenario is a hybrid of the random selection and standard DLR presented
in Algorithm 1.

VGG-19 network was trained on CIFAR-100 in these experiments. To trace these
scenarios, we define the following criterion, namely summation of normalized
condition number (SNCN):

$SNCN(f)=\sum_{l=1}^{L}\Gamma(f_{l}),$ (10)

where $\Gamma(f_{l})$ is defined in Eq.7 as the condition number of layer $l$.
The smaller this criterion in different iterations, the greater the network’s
stability against overfitting.

In Figures 4 and 5, the performances of the VGG-19 for these scenarios are
presented. As one can see, the third scenario archives the best results based
on SNCN and testing loss values. However, the result of DLR on the training
loss is worse than the others. As one can see, DLF in some epochs imposes a
noise on training loss to prevent overfitting.

Figure 4: SNCN criterion for each epoch of VGG-19 training on CIFAR-100 for
three scenarios.  Figure 5: The training and testing loss values of VGG-19 on
CIFAR-100 in successive epochs for three scenarios.

In another experiment, a snapshot of the training results of DLR on Wide-
Resnet network on CIFAR-10 is presented. It clears that the jumps of the loss
functions in the training and the testing results are different, and DLR
affected some parts of the network, where it is over-fitted. Thus, DLR
simplifies some parts of the over-fitted model and seldom removes the useful
information.

###  5.2 Performance of DLR on Shallow Networks

In this part, we show the results of DLR on the shallow networks applying
different datasets. The used networks contain at most five layers, including
several dense layers and one convolution layer. DLR results for training these
networks are compared with training without regularization and training with
dropout ($p=0.1,0.2,0.3$). Each experiment is repeated five times, and their
average is presented in Table 1. In datasets Arcene, BCWD, and IMDB Reviews,
DLR overcomes others. In the BCWD dataset, whose overfitting is low, DLR is
somewhat weaker than training without regularization.

Table 1: The comparison of the training with DLR and other regularization methods on shallow networks. Dataset Name | Regularization | Train A | Train L | Test A | Test L
---|---|---|---|---|---
Arcene | None | 99.4% | $6.04\times 10^{-3}$ | 74.6% | 0.202
Dropout (0.1) | 60.6% | $3.87\times 10^{-1}$ | 59.2% | 0.406
Dropout (0.2) | 60.0% | $3.80\times 10^{-1}$ | 59.0% | 0.411
Dropout (0.3) | 61.1% | $3.72\times 10^{-1}$ | 58.0% | 0.413
DLR | 97.4% | $6.80\times 10^{-2}$ | 85.8% | 0.125
BCWD | None | 98.7% | $1.03\times 10^{-2}$ | 95.0% | 0.038
Dropout (0.1) | 99.8% | $3.02\times 10^{-3}$ | 95.3% | 0.037
Dropout (0.2) | 93.1% | $4.50\times 10^{-2}$ | 90.4% | 0.068
Dropout (0.3) | 90.8% | $6.60\times 10^{-2}$ | 86.5% | 0.112
DLR | 97.6% | $1.86\times 10^{-2}$ | 95.6% | 0.032
BCWP | None | 98.3% | $1.22\times 10^{-2}$ | 76.4% | 0.205
Dropout (0.1) | 97.1% | $2.73\times 10^{-2}$ | 75.0% | 0.229
Dropout (0.2) | 95.0% | $3.52\times 10^{-2}$ | 71.9% | 0.220
Dropout (0.3) | 88.0% | $8.96\times 10^{-2}$ | 73.2% | 0.211
DLR | 89.2% | $8.63\times 10^{-2}$ | 74.6% | 0.210
IMDB Reviews | None | 100.0% | $7.60\times 10^{-4}$ | 85.3% | 0.396
Dropout (0.1) | 99.7% | $1.14\times 10^{-2}$ | 84.5% | 0.542
Dropout (0.2) | 99.8% | $1.06\times 10^{-2}$ | 83.9% | 0.556
Dropout (0.3) | 99.7% | $1.28\times 10^{-2}$ | 84.1% | 0.538
DLR | 99.4% | $3.54\times 10^{-2}$ | 85.6% | 0.354

###  5.3 Performance of DLR on deep networks

In this part, VGG family is trained with DLR on CIFAR-10 [33] and
CIFAR-100[33]. Table 2 shows the results without augmentation. Since the
functionality of DLR is similar to dropout family schemes, we compare it with
Dropout [4], Dropconnect [5], Shakeout [6], Bridgeout [7], and Spectral
Dropout [10] in this table. When the model complexity decreases, the DLR’s
performance is less than some of these regularization schemes. Therefore, DLR
is useful when the model complexity is high.

Table 2: The performance of the VGG family on CIFAR-10 and CIFAR-100 datasets using different regularization schemes (Boldfaces show the best accuracies) Model Regularization | DLR | [4] | [5] | [6] | [7] | [10]
---|---|---|---|---|---|---
CIFAR-10
VGG-11 | 85.4% | 83.1% | 85.4% | 85.2% | 83.7% | 85.2%
VGG-13 | 84.8% | 84.2% | 84.2% | 86.5% | 85.3% | 85.7%
VGG-16 | 85.1% | 84.1% | 85.7% | 84.6% | 86.3% | 86.4%
VGG-19 | 85.1% | 83.3% | 85.0% | 84.6% | 84.9% | 85.4%
CIFAR-100
VGG-11 | 51.4% | 52.3% | 54.9% | 54.4% | 53.9% | 53.3%
VGG-13 | 52.3% | 52.6% | 53.5% | 55.1% | 54.7% | 54.6%
VGG-16 | 52.5% | 53.4% | 56.3% | 55.5% | 54.4% | 55.3%
VGG-19 | 52.2% | 52.7% | 54.5% | 55.4% | 54.6% | 55.9%

##  6 Empirical studies on ALR

Here, to show the preference of ALR on the other regularizations, we compare
their performance, resource usage, and convergence speed. In the first part,
we experimentally show that $1/\log(t)$ is a suitable damping sequence to
avoid lazy weights. In the second part, ALR is compared with other
regularization schemes with this damping sequence. To see the implementation
of ALR refer to
Github222https://github.com/mmbejani/TikhonovRegularizationTerm.

###  6.1 Damping Sequence

Five scenarios for damping sequences are compared to find a suitable damping
sequence for avoiding lazy weights. For each sequence, four networks on two
different datasets are trained. Table 3 shows the experimental results. As one
can see, sequence $1/\log(t)$ controls the lazy weights well, and in most of
the scenarios, it improves the performance. Thus, we use this damping sequence
for the next experiments.

Besides, Fig. 6 shows the effect of different damping sequences on the
training and testing accuracies of VGG-16 on dataset Caltech-101 [34]. Without
any damping sequence, in $93^{th}$ epoch, some lazy weights are contributed,
and the accuracy drops from $88\%$ to $71\%$. A weak damping sequence such as
$\log(\log(t))$ behaves similarly. However, other damping sequences do not
impose lazy weights, and the model accuracy has not dropped.

(a) Training Accuracy

(b) Testing Accuracy

Figure 6: The performance of ALR with different damping sequences on the VGG-16 network on Caltech-101. Table 3: The VGG performances on CIFAR-10 and CIFAR-100 datasets using different damping sequences (Boldfaces show the best accuracies) Model Regularization | None | $1/\log(\log(t))$ | $1/\log(t)$ | $1/t$ | $1/t^{2}$
---|---|---|---|---|---
CIFAR-10
VGG-11 | 83.5% | 83.4% | 86.7% | 86.5% | 85.5%
VGG-13 | 84.2% | 84.5% | 87.3% | 87.3% | 86.2%
VGG-16 | 82.8% | 84.2% | 88.7% | 88.3% | 86.3%
VGG-19 | 83.1% | 85.3% | 89.0% | 89.1% | 86.7%
CIFAR-100
VGG-11 | 52.5% | 52.4% | 54.3% | 54.2% | 54.5%
VGG-13 | 52.1% | 52.3% | 55.4% | 54.3% | 54.1%
VGG-16 | 52.5% | 52.8% | 55.2% | 54.8% | 54.3%
VGG-19 | 52.9% | 52.5% | 54.9% | 55.0% | 54.7%
Table 4: The comparison between ALR and the different Tikhonov-based
regularization schemes on the VGG family on different datasets (Boldfaces show
the best accuracies)

Model Regularization | ALR | [14] | [35] | [36] | [37] | [38] | [39] | [40] | None
---|---|---|---|---|---|---|---|---|---
CIFAR-10 |
VGG-11 | 86.7% | 85.7% | 85.7% | 85.6% | 85.6% | 84.3% | 84.2% | 84.9% | 81.6%
VGG-13 | 87.3% | 86.4% | 84.1% | 84.0% | 85.3% | 84.1% | 83.7% | 84.5% | 82.1%
VGG-16 | 88.7% | 86.4% | 85.5% | 84.6% | 84.8% | 86.0% | 85.1% | 84.0% | 82.3%
VGG-19 | 89.0% | 87.8% | 83.6% | 85.5% | 83.9% | 85.2% | 86.4% | 84.5% | 82.3%
CIFAR-100 |
VGG-11 | 54.3% | 53.0% | 50.1% | 51.5% | 51.9% | 51.7% | 51.4% | 50.5% | 45.3%
VGG-13 | 55.4% | 53.8% | 52.1% | 51.6% | 52.1% | 53.3% | 51.4% | 52.5% | 47.3%
VGG-16 | 55.2% | 54.6% | 51.2% | 51.9% | 52.3% | 53.1% | 52.3% | 52.3% | 47.6%
VGG-19 | 54.9% | 53.3% | 52.5% | 51.9% | 52.8% | 51.2% | 52.1% | 52.6% | 48.9%
Caltech-101 |
VGG-11 | 65.6% | 64.6% | 62.5% | 64.7% | 65.3% | 63.2% | 64.0% | 64.3% | 60.5%
VGG-13 | 65.9% | 65.1% | 63.7% | 62.9% | 63.1% | 64.2% | 63.2% | 64.4% | 61.0%
VGG-16 | 67.0% | 65.3% | 65.2% | 64.9% | 63.3% | 62.6% | 65.1% | 64.0% | 61.3%
VGG-19 | 66.9% | 65.4% | 64.4% | 64.2% | 63.4% | 64.3% | 62.9% | 65.3% | 61.1%
Caltech-256 |
VGG-11 | 29.4% | 29.4% | 28.8% | 29.2% | 28.3% | 28.2% | 28.6% | 28.9% | 27.8%
VGG-13 | 29.8% | 29.5% | 28.0% | 29.1% | 28.9% | 29.4% | 29.1% | 29.1% | 28.1%
VGG-16 | 30.3% | 30.5% | 28.1% | 27.5% | 29.4% | 29.2% | 30.3% | 29.6% | 28.4%
VGG-19 | 30.8% | 30.7% | 28.5% | 28.7% | 29.0% | 29.9% | 28.9% | 29.2% | 28.3%

###  6.2 Performance of ALR on deep networks

Table 4 compares ALR results with other regularization schemes based on the
different Tikhonov regularization schemes proposed for deep and shallow neural
networks in the recent literature. As one can see, ALR has the best accuracy,
and in some cases, the difference between the ALR’s accuracy and that of the
others is $4\%$.

##  7 Conclusion

This paper studied the effects of adaptive LRF algorithms for neural network
regularization entitled DLR and ALR. DLR can control the overfitting in
shallow neural networks. Although DLR can find a suitable set of trained
weights for a deep neural network, its performance is not perfect. Thus, we
extended DLR to ALR. ALR combines DLR and Tikhonov-based regularization
approaches. Both DLR and ALR do not affect all network weights when
overfitting occurs. They compute condition numbers for the layers of the
learning model. By a probability distribution related to condition numbers,
some matrices are substituted with their low-rank factorization explicitly by
DLR and implicitly by ALR. Selecting a subset of weights for training improves
the training convergence and significantly improves the generalization. The
most critical point in this adaptive regularization is lazy weights. They do
not contribute to the regularization until the last training epochs, so they
have no occasion for tuning-up. We use a damping sequence to increase the
weights selection probability when the number of epochs increases. This
contribution improved ALR significantly because the different layers
contribute to regularization by significant likelihood. We tested DLR and ALR
on the various networks and datasets and showed that DLR controls the
overfitting in shallow networks, and ALR does the same for deep networks.

## References

## References

  * [1] D. Sergey, Regularization methods for neural networks and related models, Ph.D. thesis, Department of Computing and Information Systems, The University of Melbourne (2015).
  * [2] G. C. Cawley, N. L. Talbot, Preventing over-fitting during model selection via bayesian regularisation of the hyper-parameters, Journal of Machine Learning Research 8 (Apr) (2007) 841–861.
  * [3] M. M. Bejani, M. Ghatee, A systematic review on overfitting control in shallow and deep neural networks, Artificial Intelligence Review 2021.
  * [4] N. Srivastava, G. Hinton, A. Krizhevsky, I. Sutskever, R. Salakhutdinov, Dropout: a simple way to prevent neural networks from overfitting, The Journal of Machine Learning Research 15 (1) (2014) 1929–1958.
  * [5] L. Wan, M. Zeiler, S. Zhang, Y. Le Cun, R. Fergus, Regularization of neural networks using dropconnect, in: International Conference on Machine Learning, 2013, pp. 1058–1066.
  * [6] G. Kang, J. Li, D. Tao, Shakeout: A new approach to regularized deep neural network training, IEEE transactions on pattern analysis and machine intelligence 40 (5) (2018) 1245–1258.
  * [7] N. Khan, J. Shah, I. Stavness, Bridgeout: stochastic bridge regularization for deep neural networks, arXiv preprint arXiv:1804.08042.
  * [8] D. Krueger, T. Maharaj, J. Kramár, M. Pezeshki, N. Ballas, N. R. Ke, A. Goyal, Y. Bengio, A. Courville, C. Pal, Zoneout: Regularizing rnns by randomly preserving hidden activations, arXiv preprint arXiv:1606.01305.
  * [9] G. Larsson, M. Maire, G. Shakhnarovich, Fractalnet: Ultra-deep neural networks without residuals, arXiv preprint arXiv:1605.07648.
  * [10] S. H. Khan, M. Hayat, F. Porikli, Regularization of deep neural networks with spectral dropout, Neural Networks 110 (2019) 82–90.
  * [11] M. M. Bejani, M. Ghatee, Least auxiliary loss-functions with impact growth adaptation (laliga) for convolutional neural networks, Neurocomputing (2021) in press.
  * [12] S. Abpeikar, M. Ghatee, G. L. Foresti, C. Micheloni, Adaptive neural tree exploiting expert nodes to classify high-dimensional data, Neural Networks 124 (2020) 20–38.
  * [13] M. M. Bejani, M. Ghatee, Convolutional neural network with adaptive regularization to classify driving styles on smartphones, IEEE Transactions on Intelligent Transportation Systems.
  * [14] M. M. Bejani, M. Ghatee, Theory of adaptive SVD regularization for deep neural networks, Neural Networks 128 (2020) 33–46.
  * [15] P. Symeonidis, A. Zioupos, Matrix and Tensor Factorization Techniques for Recommender Systems, Vol. 1, Springer, 2016.
  * [16] A. Y. Ng, M. I. Jordan, Y. Weiss, On spectral clustering: Analysis and an algorithm, in: Advances in neural information processing systems, 2002, pp. 849–856.
  * [17] E. L. Denton, W. Zaremba, J. Bruna, Y. LeCun, R. Fergus, Exploiting linear structure within convolutional networks for efficient evaluation, in: Advances in neural information processing systems, 2014, pp. 1269–1277.
  * [18] M. Jaderberg, A. Vedaldi, A. Zisserman, Speeding up convolutional neural networks with low rank expansions, arXiv preprint arXiv:1405.3866.
  * [19] V. Lebedev, Y. Ganin, M. Rakhuba, I. Oseledets, V. Lempitsky, Speeding-up convolutional neural networks using fine-tuned cp-decomposition, arXiv preprint arXiv:1412.6553.
  * [20] C. Tai, T. Xiao, Y. Zhang, X. Wang, et al., Convolutional neural networks with low-rank regularization, 4th International Conference on Learning Representations (ICLR).
  * [21] L. Engstrom, B. Tran, D. Tsipras, L. Schmidt, A. Madry, A rotation and a translation suffice: Fooling cnns with simple transformations, arXiv preprint arXiv:1712.02779.
  * [22] A. Kwasigroch, A. Mikołajczyk, M. Grochowski, Deep convolutional neural networks as a decision support tool in medical problems–malignant melanoma case study, in: Polish Control Conference, Springer, 2017, pp. 848–856.
  * [23] M. Wasowicz, M. Grochowski, M. Kulka, A. Mikołajczyk, M. Ficek, K. Karpieńko, M. Cićkiewicz, Computed aided system for separation and classification of the abnormal erythrocytes in human blood, in: Biophotonics—Riga 2017, Vol. 10592, International Society for Optics and Photonics, 2017, p. 105920A.
  * [24] A. Galdran, A. Alvarez-Gila, M. I. Meyer, C. L. Saratxaga, T. Araújo, E. Garrote, G. Aresta, P. Costa, A. M. Mendonça, A. Campilho, Data-driven color augmentation techniques for deep skin image analysis, arXiv preprint arXiv:1703.03702.
  * [25] B. N. Datta, Numerical linear algebra and applications, Vol. 116, Siam, 2010.
  * [26] L. N. Trefethen, D. Bau III, Numerical linear algebra, Vol. 50, Siam, 1997.
  * [27] L. Eldén, Matrix methods in data mining and pattern recognition, Vol. 15, Siam, 2019.
  * [28] Nimfa, https://github.com/mims-harvard/nimfa, accessed: 2020-02-10 (2020).
  * [29] C. J. Hillar, L.-H. Lim, Most tensor problems are np-hard, Journal of the ACM (JACM) 60 (6) (2013) 45.
  * [30] E. Anderson, The species problem in iris, Annals of the Missouri Botanical Garden 23 (3) (1936) 457–509.
  * [31] Z. Lu, C. Xu, B. Du, T. Ishida, L. Zhang, M. Sugiyama, Localdrop: A hybrid regularization for deep neural networks, IEEE Transactions on Pattern Analysis and Machine Intelligence.
  * [32] P. L. Bartlett, S. Mendelson, Rademacher and gaussian complexities: Risk bounds and structural results, in: International Conference on Computational Learning Theory, Springer, 2001, pp. 224–240.
  * [33] A. Krizhevsky, G. Hinton, et al., Learning multiple layers of features from tiny images, Tech Report.
  * [34] L. Fei-Fei, R. Fergus, P. Perona, Learning generative visual models from few training examples: An incremental bayesian approach tested on 101 object categories, in: 2004 conference on computer vision and pattern recognition workshop, IEEE, 2004, pp. 178–178.
  * [35] A. Krogh, J. A. Hertz, A simple weight decay can improve generalization, in: Advances in neural information processing systems, 1992, pp. 950–957.
  * [36] B. O. Ayinde, T. Inanc, J. M. Zurada, Regularizing deep neural networks by enhancing diversity in feature extraction, IEEE transactions on neural networks and learning systems.
  * [37] H. Zou, T. Hastie, Regularization and variable selection via the elastic net, Journal of the royal statistical society: series B (statistical methodology) 67 (2) (2005) 301–320.
  * [38] D. N. Phan, H. A. Le Thi, Group variable selection via $\ell_{p,0}$ regularization and application to optimal scoring, Neural Networks 118 (2019) 220–234.
  * [39] W. Wu, Q. Fan, J. M. Zurada, J. Wang, D. Yang, Y. Liu, Batch gradient method with smoothing l1/2 regularization for training of feedforward neural networks, Neural Networks 50 (2014) 72–78.
  * [40] R. Ma, J. Miao, L. Niu, P. Zhang, Transformed $\ell_{1}$ regularization for learning sparse deep neural networks, arXiv preprint arXiv:1901.01021.
  * [41] H. Flanders, Differentiation under the integral sign, The American Mathematical Monthly 80 (6) (1973) 615–627.

##  Appendix A Proof of Theorem 1

The goal of training is to minimize the distance between the outputs of the
network $f(x;W)=[f(x_{i};W)]_{i=1,...,m}$ and the targets by minimizing the
following mathematical expectation:

$\min_{W}\mathbb{E}(x;W)=\mathbb{E}[\|f(x;W)-f(x;W^{*})\|_{2}^{2}]$

It is direct:

$\mathbb{E}[\|f(x;W)-f(x;W^{*})\|_{F}^{2}]=\mathbb{E}[\|(W-W^{*})x\|_{2}^{2}]$

For any $a,b$ and Leibniz integral rule [41], we have:

$\frac{\partial\mathbb{E}(x,W)}{\partial
W_{a,b}}=2\mathbb{E}[\sum_{j}(W(a,j)-W(a,j)^{*})x(j)x(b)]$ (11)

Then:

$\nabla_{W(a,b)}\mathbb{E}(x,W)=2\sum_{j}(W(a,j)-W(a,j)^{*})\mathbb{E}[x(j)x(b)]$
(12)

Now we have to compute $\mathbb{E}[x(j)x(b)]$ in two cases:

  1. 1.

$j=b$:

$E[x(b)^{2}]=E[x(b)^{2}]-E^{2}[x(b)]=\sigma^{2}$

  2. 2.

$j\neq b$: Since the $x(j)$ and $x(b)$ are independent, then:

$\mathbb{E}[x(j)x(b)]=\mathbb{E}[x(j)]\mathbb{E}[x(b)]=0$

Therefore, Eq.12 can be summarized as following:

$\nabla_{W(a,b)}\mathbb{E}(x,W)=2(W(a,b)-W(a,b)^{*})\sigma^{2}$ (13)

In optimal condition of LRF, we have:

$\nabla_{W(a,b)}\mathbb{E}(x,W)=2\sigma^{2}(U\Sigma
V^{T})(a,b)-(U_{k}\Sigma_{k}V^{T}_{k})(a,b)]$ (14)

We know that $W^{*}=\sum_{i=1}^{n}u_{i}^{T}\sigma_{i}v_{i}$ and
$W_{k}=\sum_{i=1}^{k}u_{i}^{T}\sigma_{i}v_{i}$ then $W^{*}-W_{k}=U\Sigma
V^{T}-U_{k}\Sigma_{k}V_{k}^{T}=\sum_{i=k+1}^{n}u_{i}^{T}\sigma_{i}v_{i}$.
Therefore, from Equ.14, we have:

$\nabla_{W(a,b)}\mathbb{E}(x,W)=2\sigma^{2}\Big{(}\sum_{i=k+1}^{n}(u_{i}^{T}\sigma_{i}v_{i})\Big{)}(a,b)$
(15)

By using gradient descent rule to update $W_{k}$, we have the following where
step-size is $\frac{1}{2\sigma^{2}}$:

$W_{k}=W_{k}+\gamma\nabla_{W}\mathbb{E}_{x}[\|f(x,W)-f(x,W^{*})\|_{F}^{2}]$

Therefore, we have:

$W_{k}=W_{k}+\gamma(2\sigma^{2}(\sum_{i=k+1}^{n}u_{i}^{T}\sigma_{i}v_{i}))=W_{k}+\sum_{i=k+1}^{n}u_{i}^{T}\sigma_{i}v_{i}=W^{*}$

And the proof is completed. ∎

##  Appendix B Proof of Lemma 1

This lemma is proved by contradiction. Assume that the rank of $\tilde{W}$ is
one. Because of linear dependency between the rows, there is an
$i\in\\{1,...,m\\}$, such that:

$\tilde{W}^{i}=\sum_{j\neq i}\alpha_{i,j}\tilde{W}^{j}.$ (16)

where $\tilde{W}^{l}$ shows the $l^{th}$ row of $\tilde{W}$.

Consider the samples of $i^{th}$ class, such as $(x_{k},y_{k})$. It meets
$y_{k}^{i}=1$ and for the others $y_{k}^{j}=0$. To satisfy the linear model,
we have:

$\tilde{W}x_{k}=y_{k}\iff\tilde{W}^{j}x_{k}=y_{k}^{j},\forall j=1,...,m.$

Thus $\tilde{W}^{i}x_{k}=1$ and for $\forall j\neq i,\tilde{W}^{j}x_{k}=0$.
Based on Eq. (16), we have:

$1=\tilde{W}^{i}x_{k}=\Big{(}\sum_{j\neq
i}\alpha_{i,j}\tilde{W}^{j}\Big{)}x_{k}=\sum_{j\neq
i}\alpha_{i,j}(\tilde{W}^{j}x_{k})=0,$

This contradiction proves the theorem and $Rank(\tilde{W})>1$. ∎

##  Appendix C Proof of Theorem 3

Consider the loss function with the LRF regularization term:

$E^{*}(\theta_{t})=E(\theta_{t})+\gamma\|w^{*}-LRF(w^{*})\|_{F}^{2}$

where $\theta_{t}$ is a trained weight and $w^{*}$ is a lazy weight. The
gradient of this function with respect to $\theta$ after appearing the lazy
weight is:

$\nabla_{\theta}E^{*}(\theta_{t})=\nabla_{\theta}E(\theta_{t})+\nabla_{w}\gamma\|w^{*}-LRF(w^{*})\|_{F}^{2}$

Since the network before the lazy weight is trained, we have
$\nabla_{\theta}E(\theta_{t})\approx 0$, then:

$\nabla_{\theta}E^{*}(\theta_{t})=2\gamma\|\sum_{i=1}^{r}u_{i}^{T}\sigma_{i}v_{i}-u_{r}^{T}\sigma_{r}v_{r}\|_{F},$

where $\sum_{i=1}^{r}u_{i}^{T}\sigma_{i}v_{i}$ is the singular decomposition
of $w^{*}$, $\sigma_{i}$ is its singular values and $u_{i}$ and $v_{i}$ are
singular vectors. Without losing of the generality, we assume that the rank of
$w^{*}$ is $r$. Also $LRF(w^{*})$ is defined by 1-rank factorization
$u_{r}^{T}\sigma_{r}v_{r}$. It is obvious that:

$\nabla_{\theta}E^{*}(\theta_{t})=2\gamma\sqrt{\sum_{i=1}^{r-1}\sigma_{i}},$

Because $w^{*}$ is a lazy weight and LRF is not imposed on this weight, based
on Lemma 1, its rank is greater than 1, thus there is at least
$\sigma_{i\in\\{1,...,r-1\\}}>0$. Then, at the extremum point, the value of
the gradient is great and it drops the accuracy atleast by
$\sigma_{i\in\\{1,...,r-1\\}}$. ∎