Efficiency Calibration of Implicit Regularization in Deep Networks via Self-paced Curriculum-Driven Singular Value Selection

1 Introduction

In deep learning, the number of parameters in a network is often significantly larger than the amount of available training data. This phenomenon is known as overparameterization. Despite this, stochastic gradient descent can still yield satisfactory generalization results on test data without the need for explicit regularization constraints [Zhang et al., 2021; Hardt et al., 2016]. This is often attributed to the implicit regularization [Neyshabur et al., 2017; Neyshabur et al., 2015; Vardi, 2023; Li et al., 2023] inherent in deep networks, which guides them towards solutions with strong generalization properties. However, there is currently no consensus on the exact reasons behind the effectiveness of this implicit regularization and how it can be further enhanced to improve the representation capabilities of networks.

∗Correpsonding Author

Significant progress has been made in the study of implicit regularization in nonlinear networks [Zhang et al., 2021; Belkin et al., 2019; Williams et al., 2019; Smith et al., 2021]. However, the complexity of these networks makes it challenging to describe them in a formulaic manner. To facilitate research and eliminate the impact of changes in network expressive power due to increasing depth [Raghu et al., 2017; Arora et al., 2018a], the focus has shifted to exploring linear neural networks (LNN) for traditional machine learning tasks such as matrix completion and factorization. In particular, [Gunasekar et al., 2017] proposes the hypothesis of implicit regularization based on experimental results on matrix factorization. According to this hypothesis, under sufficiently small initialization and learning rates, gradient descent will converge to low-rank solutions, and the implicit regularization can be interpreted as minimizing the nuclear norm (the sum of singular values of a matrix). Further investigation into LNN [Arora et al., 2018b] has revealed that depth could be viewed as a preprocessor, accelerating network convergence.

However, doubts are raised by [Arora et al., 2019; Razin and Cohen, 2020; Li et al., 2021] regarding the theoretical conclusions of [Gunasekar et al., 2017]. Based on experimental reasoning, it has been pointed out that simple mathematical formulas may not accurately describe implicit regularization. Furthermore, [Arora et al., 2019] deduces that increased depth accelerates network convergence by hastening the separation of large and small singular values, enhancing the low-rank properties of deep networks. Building upon [Arora et al., 2019], [Zhao, 2022] proposes a ratio penalty term that improves and utilizes implicit regularization more effectively, achieving stronger low-rank constraints. This penalty term ensures network convergence even in 1-layer networks. Additionally, other researchers [Wu and Su, 2023; Wang et al., 2022; Orvieto et al., 2022; Wu et al., 2022] have explored the dynamic stability, momentum, and noise of networks, offering diverse perspectives for comprehending and studying implicit regularization.

Current research has shown that explicit regularization can improve the performance of neural networks. However, most studies have focused on implicit regularization or adding penalty terms to strengthen constraints, without considering

(a)

(b)

the impact of network depth. Network depth is a crucial factor in designing neural networks, as there needs to be a balance between depth and performance. Additionally, as network depth increases, adding penalty terms can lead to a higher computational burden. Therefore, further research is necessary to determine if implicit regularization is already strong enough to yield adequate low-rank constraints at different network depths and if there are more efficient methods related to explicit regularization to calibrate implicit regularization toward desired properties. The answers to these questions will greatly impact the design and optimization of deep neural networks. To this end, we conduct research using LNN on matrix completion tasks, making the following specific contributions:

• This paper explores the connections between network depth with implicit and explicit regularization. It is observed that as the network depth increases, the addition of explicit regularization does not always bring about performance improvements. This phenomenon helps us design more efficient networks.
• We propose an effective regularizer that takes advantage of self-paced learning and the nuclear norm, resulting in a more precise restoration of matrix information. To our knowledge, this is the first instance of applying selfpaced learning to the selection of singular values.
• We theoretically analyze the rationality of our approach. Meanwhile, a series of experiments are conducted on simulated data with varying ranks and real-world data to further validate the reliability of our model.

2 RelatedWork

Regularization. During the training of neural networks, regularization terms are usually added to the loss function [Zaremba et al., 2014; Krizhevsky et al., 2017] to improve network generalization and prevent overfitting. However, explicit regularization is not always necessary. Studies have shown that implicit regularization [Vardi, 2023] can be obtained by employing optimization algorithms [Hardt et al., 2016; Wu and Su, 2023; Wang et al., 2022] or adjusting the network structure [Li et al., 2023], resulting in strong generalization abilities. In practice, implicit regularization often produces impressive results, making it crucial to analyze its role. This paper investigates the relationship between the proposed penalty term and implicit regularization, as well as the impact of network depth on this interaction.

Matrix Completion. Matrix completion and matrix sensing are essential techniques for research in recommendation systems, information retrieval, and related applications. The commonly used approaches can be categorized into three types: nuclear norm minimization, low-rank factorization [Yan et al., 2013], and minimal rank approximation [Wang et al., 2015]. Traditional algorithms often use nuclear norm minimization to reconstruct matrices. However, the standard nuclear norm, which is one of the earliest methods used [Cai et al., 2010; Candes and Recht, 2012], does not always adequately resolve issues by minimizing all singular values. Subsequent research [Hu et al., 2012] introduced the truncated nuclear norm based on matrix properties, imposing constraints solely on smaller singular values. However, this approach neglects the constraints on larger singular values and applies the same penalization to smaller ones, thus failing to adequately constrain the matrix. [Gu et al., 2014] introduced the Weighted Nuclear Norm (WNN), which assigns different weights to singular values based on their magnitudes for more flexible constraints. Following this, [Kim et al., 2015; Peng et al., 2015; Yang et al., 2018] introduced various adaptations of weighted nuclear norms. Compared with previous methods, the penalty terms we introduce not only impose flexible constraints on singular values but also show superior performance in coping with matrix noise. Additionally, our approach considers the relative magnitudes of the singular values rather than their absolute values when imposing constraints on the matrix.

Self-Paced Learning. The design philosophy behind selfpaced learning [Kumar et al., 2010] emulates the human tendency to learn knowledge from simple to complex concepts, representing a branch of curriculum learning [Zhou et al., 2020]. During training, self-paced learning selects the subset with the lowest loss as the easiest part to train. As the number of iterations increases, it gradually expands to cover the entire dataset. Self-paced regularization involves varying weights and can be categorized into three types: Hard [Kumar et al., 2010], Linear [Jiang et al., 2014], and Mixture [Zhao et al., 2015]. Each type is suitable for different scenarios, and incorporating prior knowledge [Zhang et al., 2017; Zhang et al., 2019; Jiang et al., 2015] may enhance performance. Research [Meng et al., 2017; Gong et al., 2016] has shown that self-paced learning can lead to convergence to flatter minima and reduce the impact of noise. In this paper, a new penalty term is proposed based on self-paced learning to impose stronger low-rank constraints, and the matrix completion task is used to examine the effects of implicit and explicit regularization at different depths.

3 Methodology

In this section, we will provide a detailed explanation of our motivation, methodology, and theoretical justification.

Setup. In the experimental setup, we use an LNN with parameters that can be interpreted as a matrix factorization. Specifically, an N-layer LNN can be formulated as M = MNMN-1 . . . M2M1, where M represents the predicted values, and Mi refers to the parameters of the i-th layer of the network. In matrix completion tasks, for a true matrix ˆM ∈ Rm×n , we use PΩ( ˆM) ∈ Rm×n represents the projection of ˆM on the observed dataset Ω, this notation means that the values of the data in the Ω set remain unchanged, while the rest are set to zero. And ∥ · ∥F denotes the Frobenius norm. Without loss of generality, we assume the matrix dimensions satisfy n ≤ m. The optimization objective for matrix completion can be written as:

Motivation. There is a prior assumption in matrices that the magnitude of the singular values represents the amount of information they contain, with larger singular values encompassing the primary information of the matrix, while smaller ones often correspond to noise signals. For example, in movie rating datasets, inaccurate ratings by individuals might introduce a certain degree of noise into the data matrix. Table 1 illustrates the commonly used low-rank norms in matrix completion tasks, where σi(i = 1, 2, . . . , n) is the singular value of M. Although these methods are somewhat effective, they do not manage to flexibly constrain the singular values while effectively dealing with the matrix noise. To address these issues, we propose a new low-rank regularizer.

According to the definition of self-paced learning [Zhao et al., 2015], at the beginning stages of the training process, parts of the data that contribute to larger losses (i.e., noisy data) are suppressed to minimize their detrimental impact on training. As the training progresses, noisy data is gradually introduced, but due to the initial suppression, the overall convergence direction of the network has been largely determined. At this point, the noise is unlikely to have a substantial effect. The entire training process is continuously guided by useful priors, mitigating the likelihood of falling into unreasonable local optima and enhancing the model's robustness to noise. Utilizing this characteristic, we have adapted its training strategy to the constraint of singular values, suppressing the impact of smaller singular values. In Figure 2, we compared the effects of various penalty terms on handling singular values of different magnitudes. The results show that while other methods shrink singular values to varying extents, our method precisely restores any singular value, thus better preserving the properties of the matrix. For visual comprehension, we exhibit the manifolds of different norm spheres with respect to a 2 × 2 matrix in Figure 1.

Self-Paced Weighted Nuclear Norm. Building on the aforementioned analysis, we propose a novel regularization method, namely the Self-Paced Weighted Nuclear Norm (SPWNN), which can impose more effective low-rank constraints on the network. Here, the definition of the self-paced regularizer of SPWNN is given as follows, and for ease of notation, ri(M): = wiσi/∥M∥F .

Definition 1. The function g(ci, λ) is referred to as the selfpaced regularizer of SPWNN, satisfying the conditions:

1. g(ci, λ) is a convex function, ci ∈ [0, 1].
2. The self-paced learning weight ci(ri(M), λ) is monotonically decreasing with respect to ri, and limri→∞ ci(ri(M), λ) = 0, limri→0 ci(ri(M), λ) = 1.
3. The self-paced learning weight ci(ri(M), λ) is monotonically increasing with respect to λ, and limλ→0 ci(ri(M), λ) = 0, limλ→∞ ci(ri(M), λ) ≤ 1.

where

The specific form of SPWNN is as follows:

where λ > 0 represents the growth factor of self-paced regularization. σi represents the i-th singular value arranged in descending order. wi denotes the weight of the singular value σi, where wi = 1/σi p and p ∈ (0, 1). The term ci(ri (M) , λ) indicates the weight of self-paced learning. The function g (ci(ri (M) , λ), λ) = -λ ∑ni=1 ci(ri (M) , λ) acts as the self-paced regularizer.

Specifically, guided by the prior of progressing from easier to more challenging tasks from self-paced learning, we gradually incorporate smaller singular values into the training process to restore the characteristics of the matrix M. Since the larger singular values often contain the primary information of a matrix, we prioritize the restoration of larger singular values before moving on to the smaller ones. Meanwhile, we employ the weighted nuclear norm that applies different weight constraints based on the magnitude of the singular values, offering flexible control over the importance of each direction. In practical applications, this allows for assigning greater weight to factors representing user preferences. The normalization by ∥M∥F ensures that the importance of each direction in the matrix is dependent not on the absolute magnitude of the singular values but on their relative magnitude.

Upon incorporating the penalty term, the final optimization target is expressed as follows:

where the penalty term R(M) is our SPWNN and µ > 0 is the balance parameter.

4 Theoretical Analysis

Efficiency Calibration of Implicit Regularization. We analyze the trajectory of singular values and the matrix M to show how the proposed SPWNN calibrates the implicit regularization. The following theorem elucidates the changes in singular values and matrix trajectories without the inclusion of any explicit regularizers:

Lemma 1 (Theorem 1 from [Zhao, 2022]). Under the assumptions specified in [Arora et al., 2019], without any explicit regularization, for a depth greater than 2 and when using the Adam optimizer, the trajectory of singular values and the matrix can be described as follows:

where

In the above, QM,G is positive semi-definite, ˙M denotes the derivative of M with respect to time t, and ˙σ represents the derivative of the singular values σ with respect to time t. The Kronecker product is symbolized by ⊗, j indexes the network layers, and vec denotes the vectorization of a matrix by column order. Gj = diag(vec(Sj)) defines a matrix with the elements of vec(Sj) on the diagonal, and zeros elsewhere.

Here, Sj is a matrix with values (∇Mj L(M)2 + s2j )-1/2 , where ∇Mj L(M) = ∂L(M)/∂Mj represents the derivative of the loss function with respect to the parameters of the j-th layer, s2j = var(∇Mj L(M)), ui and vi respectively represent the left and right singular value vectors, corresponding to the i-th singular value σi of the matrix M.

The function QM,G is the result of the combined effect of the Adam optimizer and the depth. When the depth is greater than or equal to 2, QM,G acts as a preprocessor that facilitates the separation of large and small singular values, thereby accelerating network convergence and promoting low-rank representation within the network. Based on the expression (3) for QM,G, It is evident that the magnitude of QM,G is related to the depth N, indicating that this implicit regularization increases with the depth, showcasing the effect of implicit regularization in the network. Comparing the trajectories of gradient singular values with matrix changes [Arora et al., 2018b], we observe that this preprocessor benefits from an additional term Gj . The Adam optimizer utilizes information on gradient variance and past momentum to facilitate a fast and precise convergence of the network during the optimization process.

For the convenience, let C = [c1, c2, . . . , cn]T and W = [w1, w2, . . . , wn]T ∈ Rn . For the matrix M, we perform singular value decomposition as M = USV T . The following theorem describes the trajectories of singular values and matrix changes:

Theorem 1. In the case of incorporating SPWNN and using the Adam optimizer, the trajectories of singular values and matrix changes are as follows:

where

We give complete proof in Appendix A. Comparing the trajectory expression in Lemma 1, the inclusion of an additional term U ˆ SV T offers supplementary acceleration toward low rank for matrix M during the training process.

When the depth is set to 1, QM,G degenerates to G, resulting in the loss of the acceleration effect on the network. Despite this loss, the additional penalty term still serves its purpose in separating large and small singular values, allowing for convergence even with a depth of 1. Our experiments also show that without explicit regularization, an LNN cannot converge. However, the introduction of explicit regularization leads to significant improvement in the results, highlighting its dominant role in this scenario.

When the depth is within an appropriate range, the effect of QM,G allows for convergence with just a LNN. Additionally, the convergence speed increases as the depth increases, indicating the start of implicit regularization. When explicit regularization is incorporated, it interacts with implicit regularization, resulting in faster convergence and stronger low-rank constraints compared to the original scenario. The penalty term provided by QM,G also enhances the acceleration effect as the depth increases. By observing the trajectory after adding the penalty term, it can be seen that ˆ S acts as a scaling factor on the spectrum of S, affecting the entire evolution trajectory from a frequency domain perspective. Looking at the singular values, the self-paced regularization guides the training process by selectively incorporating singular values based on their magnitudes, allowing for less noise interference and convergence in the correct direction. Furthermore, by assigning different weights to each singular value, more flexible constraints can be imposed on the matrix. The introduction of ∥M∥F modifies the effect of singular values on training by considering their relative magnitudes instead of just their absolute magnitudes. This strengthens the impact of larger singular values on optimization while reducing the influence of smaller singular values, further promoting lowrank constraints. At this point, the implicit and explicit regularization work together to promote low-rank properties in the network, achieving a balanced state.

When the depth is deep enough and the rank is high, we have noticed a trend in experiments where using only a LNN yields better results than incorporating a regularization term. This suggests that the implicit regularization is strong enough to serve as an effective regularizer, achieving satisfactory low-rank constraints without the need for extra regularization terms. This highlights the fact that explicit and implicit regularization do not always have a mutually beneficial impact. In this case, the implicit regularization of the network takes on a dominant role.

Convergence analysis. We will analyze the convergence of our method from the view of Majorization Minimization (MM) Algorithm [Sun et al., 2017]. For the convenience, let's define f (r (M)) := ∫ r(M) 0 cdr (M). First, we present the following theorem to establish an upper bound for the function f (r (M)).

Theorem 2. Given a parameter M ∗ , the function f (r (M)) and the self-paced weight c have the following relationship:

The proof is given in Appendix A. Let's assume that the optimization objective has reached the k-th iteration and use M k to represent the parameters at the k-th iteration.

Majorization: The objective of this stage is to obtain an upper bound for the optimization objective. According to Theorem 1, we can derive the upper bound for f (ri (M)):

Furthermore, it can be established that:

The computation of hi (M|M k ) can be obtained at each iteration using equations (4) and (1).

Minimization: The objective of this stage is to optimize the upper bound function h (M|M k ) for f (r (M)) and obtain the optimized parameters. Based on (2), (4) and (5), we can derive the optimization objective as follows:

Observing that this optimization objective (6) is consistent with the original objective (2), it indicates that our proposed algorithm is equivalent to the MM Algorithm. This proves that our algorithm has reliable convergence properties.

Complexity Analysis. In this section, we will analyze the time complexity of the algorithm. To simplify our discussion, we will assume that the matrix completion uses a matrix with dimensions of n × n and that the depth of the network is denoted as h.

For the LNN, each layer has n inputs and n outputs. With a depth of h, the corresponding time complexity is O(hn2 ). Regarding the penalty term R(M), during each training process, the matrix needs to undergo singular value decomposition, which has a time complexity of O(2n3 ). Computing the Frobenius norm of the matrix requires a time complexity of O(n2 ). Similarly, calculating the self-paced regularizer g(ci(ri(M), λ), λ) and the weight wi corresponding to the singular values both have a time complexity of O(n). Therefore, the overall time complexity of the algorithm is O(hn2 + 2n3 + n2 + 2n). Since the dimension of the matrix is typically much larger than the depth of the network, the dominant time complexity is O(n3 ). Similarly, for the ratio penalty term, since it also involves computing the singular values, its corresponding time complexity is also O(n3 ).

Through the analysis of time complexity, it can be observed that the SPWNN algorithm improves network performance without significantly increasing computational complexity compared to other methods, highlighting the superiority of our algorithm.

5 Experiments

In this section, we will compare our method with other methods listed in Table 1, using both synthetic and real datasets. The evaluation criterion will be the root mean square error (RMSE) of the test data, with a lower RMSE indicating better results. All experiments will be conducted using the Adam optimizer. Furthermore, we will utilize the effective rank (denoted by e rank(·)) [Arora et al., 2019] to track and measure the rank of the matrix. Specifically, e rank(M) = exp{H(a1, . . . , an)}, where ai = σi/||σ||1, H is the Shannon entropy, and ∥·∥1 denotes the L1 norm. More experiments are found in the supplementary materials.

5.1 Implementations

The results of the experiments are obtained by taking the average of multiple runs. The stopping condition for the experiment is when the iteration reaches 4 × 105 or when the test results remain unchanged after 2×104 iterations. For the experimental parameter settings, the networks used in this study do not include bias terms. The network initialization method is the same as [Arora et al., 2019], where the weights are initialized to 10-3 . In the case of simulated data with a depth greater than or equal to 2, the learning rate is set to 10-5 , while for a depth of 1, the learning rate is set to 10-3 . The penalty coefficient µ is set to 10-5 , and its impact on the experiments is depicted in Figure 3a. In the case of real data with a depth greater than or equal to 2, the learning rate is set to 10-4 , and for a depth of 1, the learning rate is set to

10-2 . Due to significant differences in data structures, the penalty coefficient µ varies with different real data. The initial value of the threshold for self-regularization is set to 1, and the growth factor for the threshold is set to 1.08.

5.2 Experiments on the Simulated Data

Simulated data are generated using a Gaussian distribution. Specifically, a matrix W of a designated rank is first constructed, followed by computation of WW T to obtain the true data matrix ˆW. In the experiments, the chosen matrix dimensions are 100 × 100, with tests carried out at various depths and ranks. The specific results are provided in Table 2. Furthermore, robustness tests were conducted on matrices of different dimensions and diverse proportions of observed data, with detailed results presented in Appendix B.

The experiments conducted on synthetic data consistently demonstrate the same outcome: our penalty term shows a significant improvement over previous methods at any depth. This results in better restoration of the intrinsic properties of the matrices, as shown in Figure 4. Additionally, we visualize the experimental outcomes in Figure 5, where the data restored by our approach more closely matches the distribution of the original data. Furthermore, at a depth of 1, the network only converges after the inclusion of the penalty term. In the case of a depth of 2, the network can still converge to satisfactory results even without explicit regularization, due to the effect of implicit regularization. However, the performance of the network is significantly enhanced with the addition of explicit regularization. These findings suggest that at an appropriate depth, the interplay between explicit and implicit regularization leads to a stronger low-rank constraint, thus confirming the validity of our theory.

However, as the rank increases and the depth grows, even with explicit regularization, the performance of matrix completion may not surpass that of a LNN. This phenomenon varies depending on the required depth, which is influenced by the structure of the data set. As shown in Figure 3b, the change in effective rank indicates that as the depth increases, the implicit regularization becomes more effective in constraining the rank, eventually achieving results comparable to or even better than those with explicit regularization. The figure also demonstrates that our proposed method maintains a consistently strong low-rank constraint at any depth.

The phenomena described above suggest that at shallower depths, the implicit regularization provided by the network itself may not serve as an effective regularizer, necessitating explicit regularization for constraint. However, as the depth increases, the implicit regularization of the network becomes stronger and can lead to excellent results without the need for explicit regularization. However, a deeper network structure will lead to higher computational complexity, which is obviously impractical in the real world. Thus, compared with those methods that only have implicit regularization, our method may be a better choice for practical applications.

5.3 Experiments on the Real-World Data

The real datasets employed are ML100K [Harper and Konstan, 2016], ML1M, and FilmTrust [Guo et al., 2013]. Unlike simulated data, real data consists of discrete values, and they tend to have a high rank close to full rank. Specifically, the ML100K dataset contains 100,000 ratings from 943 users for 1,682 movies, while the ML1M dataset is composed of ratings from 6,400 users for 3,900 movies, totaling one million ratings. In the MovieLens series, rating values range from 1 to 5 and are integer values. The FilmTrust dataset includes 35,497 ratings from 1,508 users for 2,071 movies, with a rating scale of 0.5 to 4, and increments in multiples of 0.5. We conducted similar experiments on the real datasets. The specific results are presented in Table 3.

The experiments demonstrate that the results are consistent for both real and simulated data sets. However, at a depth of 1, the explicit regularization is necessary for convergence. On the other hand, when the depth is optimal, explicit regularization significantly improves network performance. Interestingly, when the depth is large enough, the results with explicit regularization and those with only an LNN show minimal differences, with a slight advantage for the latter. While there may be slight deviations from the simulated data results, this also highlights the power of the network's implicit regularization at sufficient depths and with higher ranks, rendering explicit regularization unnecessary. Additionally, our introduced regularization term remains superior to the current best regularizer across all depths.

6 Conclusion

This paper introduces the SPWNN, which not only enables more flexible constraints on singular values compared to previous methods but also exhibits stronger robustness to noise. We have validated its effectiveness and convergence through experiments and theoretical analysis. Moreover, we have investigated the relationship between explicit and implicit regularization as a function of depth. Our results show that at shallow depths, the addition of explicit regularization significantly promotes network convergence. However, at greater depths with higher rank, the inclusion of explicit regularization does not contribute to performance enhancement.

Acknowledgments

This work was supported in part by the National Science Fund of China under Grant 62276135 and Grant 62361166670.