Combining Explicit and Implicit Regularization for Efficient Learning in Deep Networks
Authors: Dan Zhao
Venue: NeurIPS 2022 Accept (2022)
Keywords: optimization
regularization
deep learning
matrix factorization
neural networks
efficient learning
implicit regularization
explicit regularization
Matrix Completion
Optimization for Deep Networks

Abstract: Works on implicit regularization have studied gradient trajectories during the optimization process to explain why deep networks favor certain kinds of solutions over others. In deep linear networks, it has been shown that gradient descent implicitly regularizes toward low-rank solutions on matrix completion/factorization tasks. Adding depth not only improves performance on these tasks but also acts as an accelerative pre-conditioning that further enhances this bias towards low-rankedness. Inspired by this, we propose an explicit penalty to mirror this implicit bias which only takes effect with certain adaptive gradient optimizers (e.g. Adam). This combination can enable a degenerate single-layer network to achieve low-rank approximations with generalization error comparable to deep linear networks, making depth no longer necessary for learning. The single-layer network also performs competitively or out-performs various approaches for matrix completion over a range of parameter and data regimes despite its simplicity. Together with an optimizer’s inductive bias, our findings suggest that explicit regularization can play a role in designing different, desirable forms of regularization and that a more nuanced understanding of this interplay may be necessary.

Combining Explicit and Implicit Regularization for Efficient Learning in Deep Networks
Dan Zhao New York University dz11580nyu. edu
Abstract
Works on implicit regularization have studied gradient trajectories during the optimization process to explain why deep networks favor certain kinds of solutions over others. In deep linear networks, it has been shown that gradient descent implicitly regularizes toward low-rank solutions matrix completion/factorizatin tasks. Adding depth not only improves performance on these tasks but also acts accelerative pre-conditioning that further enhances this bias towards low- rankedness. Inspired by this, we propose an explicit penalty to mirror this implicit bias which only takes effect with certain adaptive gradient optimizers (e.g. Adam). This combination can enable a degenerate single-layer network to achieve low- rank approximations with generalization error comparable to deep linear networks, making depth no longer necessary for learning. The single-layer network also performs competitively or out-performs various approaches for matrix completion over range of parameter and data regimes despite its simplicity. Together with an optimizer's inductive bias, our findings suggest that explicit regularization can play a role in designing different, desirable forms of regularization and that more nuanced understanding of this interplay may be necessary.
Introduction
Much work has poured into understanding why and how highly over-parameteriiee. deep neural networks with more parameters than training examples generalize so effectively despite long-held notions the contrary [12, 13]. This generalization puzzle has only deepened as deep learning models often generalize well simply by optimizing its training error on an under-determined problem.
To explain this, previous works have focused how gradient-based optimization induces an implicit bias on optimization trajectories, particularly in deep (i.e., peee-parameterized settings, tending towards solutions with certain properties [7, 27] like those that generalize well. In contrast, while explicit regularization has seen wide-spread usage in various settings (e.g. weight decay, dropout [60]), its role in explaining generalization has been less certain given its inability to prevent over-fitting on random labels [70] or its absence in deep models that generalize well on their own.
Some works have focused simple test-bed to formalize and isolate the mechanisms through which implicit regularization operates-namely. matrix completion. Given some observed subset of an unknown, low-rank matrix W*, the task is to recover the unseen entries. A key observation [27] has been how gradient descent on a shallow linear neural network, with sufficiently small learning rate and near-zero initialization, pushes towards low-rank solutions its own. This has led the conjecture [27] that gradient descent induces implicit regularization that minimizes the nuclear norm.
This conjecture has been put into doubt by work [7] showing that gradient descent not only promotes low-rank solutions in the shallow case on matrix completion tasks, but its implicit regularization is further strengthened with increased depth-deep linear neural networks [7]) are able to produce
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

solutions with lower rank and more accurate completion than those from minimizing the nuclear norm. Others [6] have also shown how increased depth or over-vvvannne pwrrpmamttteriiaoonnn can provide an accelerative pre-conditioning to regression problems for faster convergence in deep linear networks.
Contributions Despite these findings, some questions still remain:
Are there explicit norm-based penalties that can mirror the effect of implicit regularization so as to better harness this phenomenon for improved or more efficient learning? Previous work [7] has conjectured that implicit regularization cannot be characterized by explicit norm-based penalties, but whether these penalties can produce similar effects is unclear.
Do implicit and explicit forms of regularization interact in any meaningful way? Can we modify the implicit biases of optimizers with explicit regularizers so as to promote better kinds of performance? Some work [11] has begun to draw inspiration from implicit regularization to create explicit regularizers, but their interactions are less clear.
Previous works [6. 7] have shown that depth can act as a powerful pre-conditioning to accelerate convergence or enhance implicit tendencies towards certain simpler well- generalizing solutions. Can this effect be produced without depth?
To try and shed more light on these questions, we propose an explicit penalty that takes the ratio between the nuclear norm of matrix and its Frobenius norm ([WII,/ ||ll] and study its effects on the task of matrix completion. This penalty can be interpreted as an adaptation of the Hoyer measure [32] to the spectral domain or as particular normalization of the nuelear-norm penalty that is commonly used to proxy for rank in convex relaxations of the problem.
Studying implicit regularization can be difficult as it is not always possible to account for all other sources of implicit regularization. For a more precise study of the implicit biases of optimizers and their interactions with our penalty, yet expressive, and well-understood test-beds that admit a crisp formulation of the mechanism through which implicit regularization operates [7, 28]. In particular, we show the following:
matrix completion and deep linear networks tractable,
1. A depth I linear neural network (i.e., a degenerate network without any depth) trained with this penalty can produce the same rank reduction and deliver comparable. if not better, generalization performance than a deep linear network-al the while converging faster. In short, depth is no longer necessary for learning.
2. The above result only occurs under Adam and, to some extent, its close variants. This sug- gests that different optimizers, each with their own inductive biases, can interact differently with explicit regularizers to modify dynamics and promote certain solutions over others.
3. With the penalty, we achieve comparable or better generalization and rank-reduction per- formance against various other techniques (Fig. 4) even in low data regimes (i.e., fewer observed entries during training) where other approaches may have no recovery guarantees.
4. Furthermore, the penalty under Adam enables linear neural networks of all depth lev- els to produce similar well-generalizing low-rank solutions largely independent of depth, exhibiting degree of depth invariance.
In this specific case, it appears that the learning dynamics which occur through the inductive bias of depth can be compressed or replaced with the right combination of optimization algorithm and explicit penalty. These properties may make deep linear networks more efficient for a variety of related matrix completion, estimation, or factorization tasks, ranging from applications in efficient reinforcement learning [58] to adversarial robustness [68], NLP [1], and others.
Previous conjectures and works [6. 7, 70] have largely dismissed the necessity of explicit regular- ization in understanding generalization in deep learning, leaving its overall role unclear. Similarly, despite its relative popularity, Adam and other adaptive optimizers have received their share of doubt [61, 62] regarding their effectiveness in producing desirable solutions. Our results suggest subtle but perhaps important interplay between the choice of the optimizer, its inductive bias, and the explicit penalty in producing different optimization dynamics and, hence, different kinds of solutions. If so, then in these interactions, explicit regularization may yet have a role to play.
Paper Overview In Section 2, we review previous work. Section 3 details our experiments and findings. In Section 4, we extend our experiments to a common real-world benchmark and compare method with other methods. We conclude in Section 5 with discussion on future work.

---

2 Related Work
Implicit regularization has been studied extensively with recent work focusing on optimization trajectories in deep. aver-parameterized settings [6, 7, 10]. One avenue in particular has focused on linear neural networks (LNNs) [26, 29, 37, 57] given their relative tractability and the similarity of their learning dynamics to those of non-linear networks. In settings with multiple optima, [28] has shown how LNNs trained on separable data can converge with an implicit bias to the max margin solution. Others [7] have demonstrated how gradient flow converges towards low-rank solutions where depth acts as an accelerative pre-conditioning [6]. In [3], for natural and vanilla gradient descent (GD), different kinds of pre-conditioning are shown to impact bias-variance and risk trade-offs in over- pwerpparamteriieed linear regression, but this is less clear for adaptive gradient optimizers.
Building upon notions of acceleration and pre-conditioning dating back to Nesterov [50] and Newton, Adam's [39] effectiveness and its close variants [24, 44, 45]-in optimizing deep networks faster makes clear the importance of adaptive pre-conditioning. Though some [61, 62] have doubted their effectiveness due to potential issues that can harm generalization, others [31, 42, 67, 71] have demonstrated advantages from their adaptive preconditioning: despite speeding up optimization, however, the effect of pre-conditioning on generalization has been less clear as some [2, 23, 65] have argued that the "sharpness" of minima achieved can vary depending on the choice of optimizer. More recent works have characterized pre-conditioning and mechanisms of implicit regularization around "edges of stability" for optimizers where the training regime occurs within certain sharpness threshold, defined as the maximum eigenvalue of the loss Hessian [8, 21, 22].
Matrix completion and factorization have themselves long been an important focus for areas like signal recovery [17] and recommendation systems [14] from theoretical bounds for recovery and convergence [18. 19, 46, 54] to practical algorithms and implementations [34, 47]. We refer to [20] for comprehensive survey. These tasks and related ones have also served test-beds for understanding implicit regularization; [7, 27] use matrix factorization and sensing to study gradient flow's implicit bias towards low-rank solutions, conjecturing that algorithmic regularization may not correspond to minimization of any norm-based penalty. [64] studies the implicit bias of mirror descent on matrix sensing, showing that the solution interpolates between the nuclear and Frobenius norms depending the underlying matrix. In a related thread, [43] has shown that gradient flow with any commuting parameterization is equivalent to continuous mirror descent with a specific Legendre function, generalizing previous results [9, 27, 63] that have characterized the implicit bias of GD.
Interestingly, [11] illustrates how the discrete steps of GD can regularize optimization trajectories away from large gradients towards flatter minima, developing an explicit regularizer to embody and reinforce this implicit effect directly. To our knowledge, our paper the first to propose a ratio penalty in matrix completion to study the interplay between explicit and implicit regularization.
3 Experiments and Findings
3.1 Setup
Formally, we have ground-truth matrix W* E Rmxx whose observed entries are indexed by the set Q. We define the projection Pa("") to be a m x n matrix such that the entries with indices in Z remain while the rest are masked with zeros. We are interested in the following optimization:
min L(W) min [Pa' (w)) AR(W) W
W
where 11- is the Frobenius norm, R(-) is an explicit penalty, and À 2 O is the tuning parameter. While we consider various penalties, our main focus demonstrating the effects of our proposed penalty R(W) = ||W]]+/|[[W] Following earlier works [4], we define a deep linear neural network (DLNN) through the following over preamttttttri,,,,,nn,, or deep factorization, of W:
W WxWN-1... W1
under the loss function in (1) where W, E Rddxd: 1, [1,...,N] .N denotes the weight matrix corresponding to depth i or the i-th layer. Here, N denotes the depth of the netwoorkffactorizztion where N = 2 corresponds to matrix factorization or a shallow network, N 2 3 corresponds to deep matrix or deep network, and N 1 is the degenerate case (no deptth/iactorization)..
3

---

We refer to the matrix W, the product of the N weight matrices in Eq. (2), as the end-product matrix as per [7]. As such, the end end-product matrix W the solution produced in estimating W or, conveniently, the DLNN itself.
In our analyses, focus on rank 5 matrices the ground truth W and parameterize DLNN W with dg = dx = m = n 100 (i.e., weight matrices W; E R 1100x100, Vi) for illustrative purposes, but our results extend other ranks (e.g. see Appendix A.2). We follow previous work [7] and employ the effective rank [56] of matrix to track and quantify the rank of W in our experiments, defined as: e-rank(W) cxp { (p1.- ..... ......)) where H is the Shannon entropy, P: 0,/ / ||||| {o;} are the unsigned singular values of W, and ||-[| is the & norm. The numerical instability of the numeric rank measure known issue [56]. resulting unreliable and unstable rank estimates. We leave detailed discussion of experiment settings to Appendix A.I.
3.2 Depth, without penalty
We first establish baseline by characterizing the inductive biases of un-regularized gradient descent and un-regularized Adam to better understand their dynamics the presence of our penalty.
GD:
singular
N
70
60-
50-
40-
10'4
20
20-
10-
Baratoo Adam: effective rank
Adam: test BITOr
Adam: Singular values
10y
70-
30-
10
40
40
10
20
10
30'1
0.0
1.0
2.0
2.5
0.0
3.0
3.5
2.0
2.5
0.0
3.0
2.5
Farraton
110100 om
Figure 1: Dynamics of un-regularized gradient descent (GD) and Adam. Plots show the performance of GD over networks of depths 2/3/4/5 for rank 5 matrices of size 100 100. Colors correspond to different depth levels and shaded regions correspond error bands. The left column depicts generalization error as function of depth and training iterations. The middle column depicts the change in effective rank across depths and over training iterations. The right column shows the 1s and 5th largest singular values for each depth across training iterations. For singular values, solid line indicates the 1st largest singular value while dotted line indicates the 5th largest within each depth level (colored lines). We omit the remaining singular values avoid clutter.
Gradient Descent Previous work [7] has shown that depth enhances gradient descent's implicit regularization towards low rank, characterized by the following trajectories on the end-produce matrix W and its singular values {a,} (for details, see [6, 7D):
(1)3 "F" U. ZW)(()))) vec (W) - veo (V (WW)(W)
(4) where à; is the time derivative of (1), the i-th singular value of ((), (u, vi} are the left and right singular vectors of W(t) corresponding a,()), N is the network's depth, VwL(W(()) is the loss gradient with respect to the end end-product matrix W at time i, vec(.) denotes (column-first order) vectorization, W dW/dt is the time evolution of the end-product matrix or (equivalently)
the DLNN itself, Pw Σラ- (W WW) N ( /²²,, and denotes the Kronecker product. We suppress the explicit dependency non-degeneracy (non-trive trivial depth, N > 1); otherwise, they reduce to just u, V Cw<((((t) (t)))))..
for simplicity and note that full dynamics in Eq. (3) require
In Eq. (4), Pw can be seen pre-conditioning onto the gradient that, with sufficient depth (N > 2), accelerates movements already taken in the optimization [6]. As popat/oove-parameterizaaaoo increases, this acceleration intensifies while larger singular values and their movements become more

---

pronounced than their smaller counterparts, driving singular value separation and a decrease in rank of the recovered matrix (Fig. 1 top row). The singular values evolve uneven paces depending on the depth; increasing depth increases the gap in the time it takes between the 1st and 5th largest singular values to develop while also taking longer stabilize. These effects are even more pronounced when comparing the five largest singular values to the remaining ones. Only with sufficient depth (N > 2) do solutions produced by un un-penalized gradient descent minimize rank so as to recover the rank of the underlying matrix and produce solutions with low test error.
Adam Analyzing Adam can difficult given its exponentially moving average of gradients: to simplify our analysis, we borrow some assumptions from [5] to approximate Adam's 's dynamics via gradient flow by assuming that the discounted gradients can be well well-approximated by their expectation. (see Appendix A.4 for more details).
Theorem 1. Under the assumptions above and of [7], the trajectory of the singular values a; of the end-product matrix W. be approximately characterized as:
o; vc Pw,cvoc(VV ((W))
(5)
Similarly, the trajectory of the end-product matrix W üself can be approximately characterized as:
vec(W) -we, V L(W))
(6)
where Pw.G = -==((wWW)))) + 2 W) G. is p.s.d. and Gj is diagonal matrix for layers j E (I,...,,N N}. Specifically, G3 = diag(vec( (S,)), [S,lm,n - = [[V,, [[VW,[(W)'' + + ] Vw,f(W) = /LW is layer j's loss gradient, and 8
Proof. See Appendix A.4.
Via this approximation, the pre-conditioning induced by Adam be characterized as a modification of gradient descent's Pw, which now normalizes each layer by the square-root of its squared layer- wise loss gradient (OC(W)/OW) levels. Unlike before, the variance of the loss gradient comes into play. Whereas before the pre- conditioning served purely accelerative effect that intensifies with depth, its normalization by the gradient variance of each layer W, can now either dampen or further accelerate the trajectory.
and the gradient variance s7. before summing across all depth
that depth enhances the implicit bias towards low-rank solutions for both Adam and gradient descent albeit differently (Fig. I, middle column); in deeper regimes (N > 2), Adam minimizes rank to exact/near-exaad rank recovery vs. 10s iterations) and more uniform convergence (Fig. 1, bottom row). With Adam, singular value uniform evolution regardless of depth in contrast gradient
Empirically,
smoothly than gradient descent via faster (10Al
dynamics exhibit significantly descent (Fig. 1, right), leading to different types of trajectories and solutions.
3.3 Depth, with penalty
Gradient Descent We now characterize the dynamics of gradient flow with our penalty.
Theorem 2. Under the assumptions of [6], the evolution of the singular values of the end-produe matrix, under gradient descent with the penalty, can be approximated in the following fashion:
o, = GG
AN
(1
|W||
3N-2
||
[|
where À 2 O is the regularization parameter and GGF denotes the un-regularized singular value trajectory under gradient flow in Eq. (3). Similarly, the evolution of W can be approximated via:
vec(W) - PP (vee (Vw + Vee COUT-UUVV V
(8)
I|
where U, V contain the left and right singular vectors of W, Pw is the pre-conditioning in Eq. (4),
and 5 [
|W]|- Σ. where E contains the singular values of W along its diagonal.
Proof. See Appendix A.4 for details.
5

---

CD:
GD: effective rank
G0: singuler
10"
70
30'1
65-
50
10-2
40
10-
22
singular
degth
teggetute
40
10
22
10
10
0.8
0.5
1.1
2.0
2.5
0.0
0.5
3.0
2.0
2.5
0.0
0.5
3.2
2.0
2.5
Earattoo
1taration om
Figure 2: Dynamics of regularized gradient descent (GD) and regularized Adam with our penalty. Plots above show the performance of GD with our proposed penalty over networks of depths 2/3/4/5 for rank 5 matrix completion. Setup is identical to Fig. 3. Here, À 10 but results hold for range of values À [10 10 1]=
The penalty can seen as an additive component the original trajectory in Eq. (3) that also intensifies with increased depth, making movements in larger singular values more pronounced than those of smaller ones. As a result, it can enable more pronouneed singular value separation than before (2N (2N-1
A. Increasing depth continues to push down rank but, unlike before (Eq. (3), Eq. (4)), the penalty now allows singular value trajectories to depend on their own magnitudes even without depth (Eq. (7) with N 1), providing additional degree of freedom. The penalty also allows each singular value to depend on its relative weight within the distribution of singular values through (1 || /[W])))) rather than just its absolute magnitude.
3N-2), depending
In Eq. (8), we also see that the new term: while the first term can be interpreted as the typical influence of reducing the loss via training and gradient optimization on the network's trajectory, the new term can be interpreted as spectral-based component that can be used by Pw to further enhance the spectral trajectory of W at higher depths, like in Eq. (7). Looking at the diagonals, the new term can be seen as a spectrally re-scaled version of W that influences its trajectory in way that accounts for each singular value's 's weight relative to its entire spectrum: IW v. [W || o.).
accelerative pre-connitioning Pw now acts on
Empirically, comparing the un-regularized case (Fig. 1 top row) to the regularized case (Fig. top row), we see that the penalty helps increase the speed at which rank is reduced, inducing faster rates of rank reduction earlier in training. Unlike in un-regularized gradient descent where deeper networks take longer to exhibit rank reduction, the penalty enables near simultaneous reductions in rank across all depths (Fig. top row, middle), making it less dependent depth.
Adam With Adam, the penalty's s effect differs considerably in terms of the solutions produced. Theorem 3. Under the same assumptions, with the proposed penalty, the evolution of the end-product matrix and its singular values can be approximated via the following:
ô -voc(vv Pw.c vec (VwL(W)) + vec(UVT - -UEVT)
I
(9)
vec(W)) = -wwo vec (VwL(W)) + vec(UVV - -UEVT
I|WI12
Proof. Follows from Eq. (5) and Eq. (6) with our penalty. See Appendix A.4 for details.
Empirically, we note a new development: there a large degree of depth invariance as rank pushed down and low test emor is achieved almost independently of depth (Fig. 2, bottom row), even depth (i.e., a shallow network). Exact rank recovery the underlying matrix now possible at all depths, unlike gradient descent, and the networks converge to solutions faster by an order of magnitude.

---

From a shallow network (N = 2), increasing the depth does not induce any material changes in the solutions produced as the penalized DLNN under Adam produces low-rank solutions that achieve exact rank recovery and low test error faster and better than previous settings.
Moreover, we that this combination of Adam with the penalty also retains some of the acceler- ative effect of Adam. Specifically, we see more favorable generalization properties and smoother development of singular values whose convergence speed is at least an order of magnitude faster than under gradient descent (10* vs. 10 iterations- singular values evolve, we see that their paths are relatively robust to depth, exhibiting near-identical behavior with significantly less dependence on depth than before (Fig. 2, right most column).
effects do not vary much with depth. As the
3.4 No depth, with penalty
Given the beneficial depth- inptr-aivariant effects produced by the penalty under Adam in both deep (N > 2) and shallow (N = 2) networks, we consider its effects in a limiting case: degenerate depth 1 network (i.e., no depth: N = 1). It is known [70] that gradient descent in this setting converges to the minimum Frobenius (fz) norm solution, which does not necessarily induce low-rankedness. As expected, training a depth 1 network with gradient descent fails to produce a well-generalizing or low-rank solution (Fig. 3, top row) as learning is heavily constrained without depth.
GD: test error
CD: effective tank
GD: singuler values
107
145
365
165
test crror
Adam: effective rank
Adam: singular values
107
50
10
60-
0701
10
10
30
5th
351
(th
0.0
10
2.2
2.5
3.0
0.0
0.5
2.0
2.0
3.0
0.5
1.5
2.0
2.5
3.0
Baration
304
Berition
104
106
Figure 3: Performance comparison between choice of optimization and regularizer in a depth network. Top row corresponds to gradient descent and bottom corresponds to Adam. Note that À 0 (red line) corresponds the un-regularized setting. Here, = 10 2 but results hold for values À [10 -6 10 ').
Yet, despite being ineffective under gradient descent, the penalty is again effective under Adam (Fig. 3, bottom row) even without depth, generalizing well as if not better than deep networks (N > 2). We note that replacing our penalty with other proxies of rank or spectral sparsity, like the nuclear norm, does not work (Table 1). As described carlier, under un-regularized gradient flow with no depth, network dynamics collapse as singular value trajectories reduce to u, Vw ((W (1))v, and the depth dependent accelerative pre-conditioning vanishes (Pw = Im.) ). We see this empirically (e.g. Fig. 3 top row and Table 1) as solutions from un-regularized gradient descent generalize poorly and fail at rank recovery. In contrast, depth network trained under Adam with the penalty not only achieves low test error (Fig. 3, bottom-left), but also recovers the underlying rank of the ground truth matrix-behaving qualitatively like deep network. As such, we see that the depth invariance of Adam and the penalty in deeper networks also extends to the case of a depth-less degenerate network.
Without depth, a key component that appears to help the network learn under Adam and the penalty is its variance- weighted gradient term WWW) G. as defined in Eq. (6), along with the term Pw:G ( (ee(UUT-UEV T) which reduces to G (> V -UVVV 1) without depth. Interestingly, [ the variance of the loss gradient and the ratio 1/² var(V W L(W)) V /W/////WWWW formed from V L(W). G resembles inverse signal-to-nois ratio that both have come up in other works as
[W
7

---

important quantities that are strongly predictive of generalization capabilities [35] or are essential to finding optimal variance adaption factors for loss gradients [5].
3.5 Comparison with other penalties and optimizers
Table Results rank matrix completion across various optimizer/pennalyydpphhh combinations in terms of test error (Err) and effective rank (Rk, rounded to nearest integer) of the estimated matrix. Ratio denotes our ratio penalty (ll ||-/I| [|.), Sch p:q denotes the ratio of two Schatten (quasi)norms (II |/s///1 |Is,)) as penalty, Nuc denotes the nuclear norm penalty. None is no penalty, and a denotes a 10". Best results- in terms of both absolute test error (lower the better) and rank reduction (closer to 5 the better) as well as depth invariance in terms of error and rank in bold. For more results, see Appendix A.3.
Ratio
Sch 3:3
Sch f:$
Sch t
Nuc
None
Optimizer
Depth
Eir
Rk
Ei
Rk
Err
Rk
Ei
Rk
Err
Rk
Eir
Rk
Adam [39]
4c-
5
0.72
33
0.80
45
0.81
53
0.36
6
1.00
79
4e-7
3e-6
5
66-6
0.30
1
0.58
31
0.81
60
0.97
32
0.79
60
0.12
8
0.80
70
Adagrad [25]
3e-7
0.05
4e-7
0.76
44
22
0.80
0.05
72
Adamax [39]
3
7
3e-6
5
7
6e-6
0.07
7
0.01
7
2e-4
1.8c+3
0.05
RMSProp
3
0.03
8c-4
5
2e-3
1.9
0.05
6
0.11
14
0.81
67
0.81
62
0.80
47
0.81
60
0.82
59
0.83
72
3 0,51
0.25
5
0,56
3
0.39
0.24
4
1e-5
5
Other Combinations Our results do not preclude the possibility that other optimizers and penalties can produce similar or better effects. For completeness, and inspired by the properties of our penalty (e.g. ratio-like, spectral, non-convex), we experiment with various optimizers and penalties (Table I) to compare their interactions across shallow (N = 1) and deep (N 3) settings. We note that our ratio penalty under Adam and its close variant Adamax, both initially proposed in [39], are the only combinations that largely show depth invariance in test error and rank recovery whereas others require depth reduce rank generalize better. Though the nuclear norm exhibits some depth invariance, it unable to find well-generan gell-generalizing solutions and fails in rank reduction under gradient descent where depth is still necessary. Other combinations also fail in enabling depth network perform well as deeper ones. Due to space constraints, we leave a fuller treatment and characterization of each optimizer's inductive bias and its interaction with different regularizers for future work.
Matrix Completion (Test Error)
Matrix Completion (Effective Rank)
10 1
enor
effective
100
10-5
10-7
1750 2000 2250 2750
sample size
sample size
Figure 4: Comparative performance in test error and rank minimization for rank 5 matrix completion. z-axis stands for the number of observed entries (R 100 out of 100 x 100 10 entries) and shaded regions indicate error bands. Adam:1+R refers to depth network trained with Adam and penalty, CP the minimum nuclear norm solution, GD:3 is depth network trained with gradient descent, OPT is OptSpace [38], and SI is SoftImputs [47]. To reduce clutter, we omit results with similar performance as GD:3 (c.g. GD:4, GD:5).
Comparative Performance We also note our penalty's 's comparative performance (Fig, 4) against other methodologies for matrix completion across various sample sizes (i.e., the amount of observed entries, uniformly sampled, made available for training). A depth network with Adam and the penalty (Fig. 4, Adam: red line) outperforms all other methods including un-regularized
8

---

DLNN in terms of test error and degree of rank compression/recovery across varying sample sizes. Even at lower sample sizes, the depth I network generalizes better than methods such Soft SoftImpute [47], Opt:ppcc [38], the minimum nuclear norm solution [19], and DI.NNs trained with gradient descent (N 2 3) by at least an order of magnitude. also outperforms other methods across various data regimes from small sample sizes to large ones, improving as the sample size grows.
4 Results on real data
Table 2: Performance evaluations on MovieL.ens100K. Results are categorized by model, whether additional data or features (e.g. external/side information, implicit feedback, graph features, etc.) beyond the explicit ratings in the interaction matrix are used, and test error measured by root mean squared error (RMSE, lower is better) different splits in (a) and (b). Since various approaches use different train-test proportions, results [16, 53J on two common splits are included. Results from using Adam with the penalty are bold.
Uses side info, add. features, other info, etc?
Uses side infos add. features, other info, etc?
Model
90%
Model
80%
RMSE
RMSE
Depth LNN
Depth LNN
w. GD
2.814
w. GD
2.797
w. GD+ppenally
2,808
w. GD+ppenally
2.821
Adam
1.844
Adam
1.822
w. Adam-penalty
0.915
w. Adam-penalty
0.921
User
Usem-Item Item Embeeding
No
User Item Embeeding
No
W. GD
2.453
w. GD
2.532
GD+penally
2.535
GD+penalty
2.519
W. Adam
1.282
w. Adam
1.348
Adam-penalty
0,906
Adam-penalty
0.919
NMF [48]
No
0.958
PMF [48)
No
0.952
IMC 66]
Yes
1.653
SVD+ [41]
Yes
0.913
GMC [36]
Yes
0.996
NEM [30]
No
0.110
MC [18]
Yos
0.973
FM [55]
No
0,909
GRALS [52)
Yes
0.945
GraphRec [53]
SRGCNN (SRMGCNN) [49]
AutoSVD++ [59]
Yes
0.904
GC-MC [16]
Yes 0.910
GraphRactsidefeat
Yes
0.899
GC-MC+side feat. [16]
Yes
0.905
GraphRectgrphhiside [eat][33]
Yes
0.883
(a) Performance 90:10 (90%) train-test split
(b) Performance on 80:20 (80%) train-test split
I Lastly, a natural question might be: how well do our results extend to real-world data? To answer this, we consider MovieLens 100K [15]-a common benchmark used to evaluate different approaches for recommendation systems. It consists of ratings from 944 users 1,683 movies, forming an interaction matrix M E 1944x1683 where the goal is to predict the rest of M after observing a subset.
Unlike our carlier experiments, the values here are discrete in the range {1, 3, 4, 5} and M is of high, or near full, rank. Given these differences and more conventional empirical approaches in recommendation systems, apply our penalty in two ways. The first way is as before: training a depth network with Adam and the penalty (Depth 1 LNN, Table 2). The second way to impose our penalty on a classic user-item embedding model (User-Item Embedding, Table 2 [40]) that combines user-specific and item-Specific biases with a dot product between latent user and latent item embedding; we apply our penalty separately on either the item or the user embedding layer. Though approaches solely utilizing explicit ratings have fallen out of favor in lieu of ones incorporating additional information and complex designs (c.g. graph-based, implicit feedback, deep non-linear networks), we nonetheless evaluate the effects of our penalty within this simple framework. We compare the results from these two approaches with variety of approaches that use specialized architectures, deep non-linear networks, additional side information, etc., beyond M.
From Table 2, we see that Adam and the penalty (w. Adam+penalty) can improve performance over the baseline of gradient descent (GD) or Adam alone. Surprisingly, depth 1 network with Adam and the penalty can outperform or come close to other more specialized approaches despite its simplicity; however, in contrast to the other methods, does so without any specialized or additional architectures (c.g. helper models/networkss, external information beyond M (c.g. implicit feedback.

---

side information), construction of new graphs or features, non-linearites, higher-order interactions (e.g. factorization machines), or-for the depth case-even any factorization all. More precise tnning (e.g. better initialization, learning schedules) or usage of other information/feattuee may yield further improvements on this task and others that involve matrix completion or factorization [1, 58, 68). We leave these for fuller evaluation and further study in future work.
Discussion
The dynamics of optimization trajectories- induuce together by the choice optimizer, parameteri- zation, loss function, and architecture-cat play an important role in the solutions produced and their ability to generalize. Depth and gradient descent-like algorithms have been key ingredients to the successes of deep learning. On matrix completion/factorizatii well-generalizing solutions and perfect rank recovery even with a degenerate depth I, or depth-less, network. Does that mean our penalty, together with Adam's own inductive bias, is producing effect similar to implicit regularization under gradient descent with depth, but better?
the proposed penalty helps produce
We suspect not. While concur with the conjecture in 17]-namely, a reductionist view which suggests that implicit regularization can be entirely encapsulated by an explicit norm-based penalty is likely an incorrect over-simplifictionn- we believe that there is merit in studying both implicit and explicit forms of regularization to examine their interplay. Our work suggests that we may able to partially replicate the successes of deep learning by selectively combining optimization methods with explicit penalties via better model design or encoding inductive biases, but this remains unclear.
Many questions remain open from our limited analyses which, due to space considerations, we leave for future work. For instance, how well do lessons from DLNNs translate to their non-linear counterparts other tasks (e.g. classification)? How does this relate to learning regimes with larger learning rates or discrete trajectories (i.e., beyond gradient flow)? A more rigorous analysis of the properties (e.g. convergence) of Adam, adaptive gradient methods, and other optimizers in the presence of explicit regularizers may better our understanding. It remains unclear whether implicit regularization is a bug feature in deep parameterizee networks. Nonetheless, our findings suggest the possibility that can be harnessed and transformed to desirable effect.
Acknowledgments and Disclosure of Funding
We thank Kellin Pelrine for his feedback and Derek Feng for his help with a previous collaboration on which this work builds. We also thank the anonymous reviewers for their valuable comments and feedback throughout the process.
References
[1] Anish Acharya, Rahul Goel, Angeliki Metallinou, and Inderjit Dhillon. Online embedding compression for text classification using low rank matrix factorization. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence, 2019.
[2] Shun-ichi Amari, Jimmy Ba, Roger Grosse, Xuechen Li, Atsushi Nitanda, Taiji Suzuki, Denny Wu, and Ji Xu. On large-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint 1oXiv:609.04455 04836, 2016.
[3] Shun-ichi Amari, Jimmy Ba, Roger Grosse, Xuechen Li, Atsushi Nitanda, Taiji Suzuki, Denny Wu, and Ji Xu. When does preconditioning help or hurt generalization? International Conference on Learning Representations (ICLR), 2021.
[4] Sanjeev Arora, Yingyu Liang, and Tengyu Ma. Why are deep nets reversible: simple theory, with implications for training. CoRR, abs/151 1.05653, 2015.
[5] Sanjeev Arora, Nadav Cohen, and Elad Hazan. Dissecting Adam: the sign, magnitude and variance of stochastic gradients. In Proceedings of the 35th International Conference on Machine Learning (PMLR) 2018, 2018.
10

---

[6] Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameterizatton. In 35th International Conference on Machine Learning (ICML), 2018.
[7] Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. In Advances Neural Information Processing Systems, 2019.
[8] Sanjeev Arora, Zhiyuan Li, and Panigrah Abhishek. Understanding gradient descent on edge of stability in deep learning. arXiv preprint arXiv: 2022.
[9] Moroshko E. Nacson M. S. Woodworth B. Srebro N. Globerson A. Azulay, S. and D. Soudry. On the implicit bias of initialization shape: Beyond infinitesimal mirror descent. In Proceedings of the 38th International Conference on Machine Learning (PMLR), 2021.
[10] Bubacarr Bah, Holger Rauhut, Ulrich Terstiege, and Michael Westdickenberg. Learning deep linear neural networks: Riemannian gradient flows and convergence to global minimizers. arXiv preprint arXiv: 19 19.005505, 2019.
[11] David G.T. Barrett and Benoit Dherin. Implicit gradient regularization. International Conference on Learning Representations (ICLR), 2021.
[12] Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences of the United States of America, vol. 80:201907378, April 2020.
[13] Mikhail Belkin, Alexander Rakhlin, and Alexandre B Tsybakov. Does data interpolation contradict statistical optimality? arXiv.org, 2018.
[14] James Bennett, Stan Lanning, et al. The netflix prize. Citeseer, 2007.
[15] Rianne Van Den Berg, Thomas Kipf, and Max Welling. The movielens datasets: History and context. ACM Transactions on Interactive Intelligent Systems (TiS) Article 19, 2015.
[16] Rianne Van Den Berg, Thomas Kipf, and Max Welling. Graph convolutional matrix completion. KDD'18 18 Deep Learning Day), 2018.
[17] Emmanuel J. Candes and Yaniv Plan. Matrix completion with noise. Proceedings of the IEEE, 98(6):2259936) 2009.
[18) Emmanuel J Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foundations of Computational mathematics, 9(6):717, 2009.
[19] Emmanuel J Candès and Terence Tao. The power of convex relaxation: Near-optimal matrix completion. IEEE Transactions on Information Theory, 56(5): 2080,, 2010.
[20] Yuejie Chi, Yue M Lu, and Yuxin Chen. Non-convex optimization meets low-rank matrix factorization: an overview. IEEE Transactions on Signal Processing, 67(20):5239-557 026999552996099 2019.
[21] Jeremy Cohen, Simran Kaur, Li Yuanzhi, J. Zico Kolter, and Ameet Talwalkar. Gradient descent on networks typically occurs the edge of stability. International Conference on Learning Representations (ICLR), 2021.
[22] Jeremy Cohen, Behrooz Ghorbani, Shankar Krishnan, Naman Agarwal, Sourabh Medapti, Michal Badura, Daniel Suo, David Cardoze, Zachary Nado, George E. Dahl, and Justin Gilmer. Adaptive gradient methods at the edge of stability. arXiv preprint arXiv:2207. 14484, 2022.
[23] Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio. Sharp minima can generalize for deep nets. arXiv preprint arXiv:/703.0449) 2017.
[24] Timothy Dozat. Incorporating nesterov momentum into adam. ICLR Workshop Track.
[25] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 220u)):222122155 201
[26] Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.
11

---

[27] Suriya Gunasekar. Blake Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nathan Srebro. Implicit regularization matrix factorization. In Advances in Neural Information Processing Systems, pages 6152-6160, 2017.
[28] Suriya Gunasekar, Jason D Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. In Advances in Neural Information Processing Systems, pages 9461-9471, 2018.
[29] Moritz Hardt and Tengyu Ma. Identity matters in deep learning. arXiv preprint 1rXiv:1611.04233 2016.
[30] Xiangnan He and Tat-Seng Chua. Neural factorization machines for sparse predictive analytics. In 40th International ACM SIGIR conference on Research and Development in Information Retrieval, pages 355-364, 2017.
[31] Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, and Bernhard Nessler. GANs trained by a two time-scale update rule converge to a local nash equilibrium. In Advances in Neural Information Processing Systems, 2017.
[32] Niall Hurley and Scott Rickard. Comparing measures of sparsity. IEEE Transactions on Information Theory, (5(10))4723-4744 2009.
[33] Prateek Jain and Inderjit S. Dhillon. Provable inductive matrix completion. arXiv:1306.0626 2013.
[34] Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi. Low-rank matrix completion using alternating minimization. Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pages (65-674,22 2013.
[35] Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fan- tastic generalization measures and where to find them. International Conference on Learning Representations (ICLR), 2020.
[36] Vassilis Kalofolias, Xavier Bresson, Michael Bronstein, and Pierre Vandergheynst. Matrix completion on graphs. arXiv preprint arXiv: 2014.
[37] Kenji Kawaguchi. Deep learning without poor local minima. In Advances in Neural Information Processing Systems, pages 586-594, 2016.
[38] Raghunandan Keshavan and Sewoong Oh. A gradient descent algorithm on the grassman manifold for matrix completion. arXiv preprint arXiv:0910.5260, 2009.
[39] Diederik P Kingma and Jimmy Lei Ba. Adam: A method for stochastic optimization. In 3rd International Conference on Learning Representations (ICLR), 2015.
[40] Robert Bell Koren, Yehuda and Chris Volinsky. Matrix factorization techniques for recommender systems.
[41] Yehuda Koren. Factorization meets the neighborhood: a multifaceted collaborative filtering model. In 14th ACM SIGKDD international conference on knowledge discovery and data mining, pages 426-434, 2008
[42] Daniel Levy Levy and John C Duchi. Necessary and sufficient geometries for gradient methods. In Advances in Neural Information Processing Systems, pages 1 11491-1 11501, 2019.
[43] Zhiyuan Li, Tianhao Wang, Jason D. Lee, and Sanjeev Arora. Implicit bias of gradient descent on reparametrized models: On equivalence to mirror descent. arXiv preprint arXiv:2207.04036v/ 2022.
[44] Liyuan Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han. On the variance of the adaptive learning rate and beyond. abs/ hts//908.03226. 2019.
[45] Ilya Loshchilov and Frank Hutter. Fixing weight decay regularization in adam. 2017.
12

---

[46] Cong Ma, Kaizheng Wang, Yuejie Chi, and Yuxin Chen. Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval, matrix completion. and blind deconvolution. Foundations of Computational Mathematics, pages 1-182, 2019.
[47] Rahul Mazumder, Trevor Hastie, and Robert Tibshirani. Spectral regularization algorithms for learning large incomplete matrices. Journal of Machine Learning Research (JMLR), 11: 2287-2322, 2010.
[48] Andriy Mnih and Ruslan R Salakhutdinov. Probabilistic matrix factorization. In Advances in Neural Information Processing Systems, pages 1257-1264, 2008.
[49] Federico Monti, Michael Bronstein, and Xavier Bresson. Geometric matrix completion with recurrent multi graph neural networks. In Advances Neural Information Processing Systems, 2017.
[50] Yu Nesterov. Gradient methods for minimizing composite functions. Mathematical Program- ming, 140(1):125-161, 2013.
[51] Noelie Ramuzat. On the semi-positer definition of the product of a positive diagonal matrix and symmetric semi-positive definite matrix. HAL Open Science, hal-03434195, 2022.
[52] Nikhil Rao, Hsiang-Fu Yu, Pradeep K. Ravikumar, and Inderjit S. Dhillon. Collaborative filtering with graph information: Consistency and scalable methods. In Advances in Neural Information Processing Systems, 2015.
[53] Ahmed Rashed, Josif Grabocka, and Lars Schmidt-Thieme. Attribute-aware non-linear co- embeddings of graph features. In Proceedings of the 13th ACM Conference Recommender Systems, RecSys 11, page 314-321, 2019.
[54] Benjamin Recht. A Simpler Approach to Matrix Completion. 12(104):3413 2011.
[55] Steffen Rendle. Factorization machines. IEEE International Conference on Data Mining, pages 995-1000, 2010.
[56] Olivier Roy and Martin Vetterli. The effective rank: A measure of effective dimensionality. In 15th IEEE European Signal Processing Conference, pages 606-610. IEEE, 2007.
[57] Andrew M Saxe, James L McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynamics of learning deep linear neural networks. arXiv preprint arXiv:1312.6122 2013.
[58] Devavrat Shah, Dogyoon Song. Zhi Xu, and Yuzhe Yang. Sample efficient reinforcement learning via low-rank matrix estimation. In Advances in Neural Information Processing Systems, 2019.
[59] Lina Yao Shuai Zhang and Xiwei Xu. Autosvd++: an efficient hybrid collaborative filtering model via contractive auto-eneoders. In Proceedings of the 40th International ACM SIGIR conference on Research and Development in Information Retrieval, RecSys '19, page 957-960, 2017.
[60] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: A simple way to prevent neural networks from overfitting. Journal of Machine Learning Research (JMLR), 15:1929-1958, 2014.
[61] Neha S Wadia, Daniel Duckworth, Samuel Schoenholz, Ethan Dyer, and Jascha Sohl- Dickstein. Whitening and second order optimization both destroy information about the dataset, and can make generalization impossible. arXiv preprint 2rxiv:2008.07555, 2020.
[62] Ashia Wilson, Rebecca Roelofs, Mitchell Stern, Nati Srebro, and Benjamin Rech. The marginal value of adaptive gradient methods in machine learning. In Advances in Neural Information Processing Systems, pages 4148-4158, 2017.
[63] Gunasekar S. Lee J. D. Moroshko E. Savarese P. Golan I. Soudry D. Woodworth, B. and N. Srebro. Kernel and rich regimes in overparametrized models. In Proceedings of the 33rd Conference Learning Theory (PMLR), 2020.
13

---

[64] Fan Wu and Patrick Rebeschini. Implicit regularization in matrix sensing via mirror descent. In Advances in Neural Information Processing Systems, pages 20558-20570, 2021.
[65] Lei Wu, Chao Ma, and E Weinan. How SGD selects the global minima in pvrr-aarameterized learning: A dynamical stability perspective. In Advances in Neural Information Processing Systems, pages 8279-8288, 2018.
[66] Miao Xu, Rong Jin, and Zhi-Hua Zhou. Speedup matrix completion with side information: Application to multi-label learning. Advances in Neural Information Processing Systems, 2013.
[67] Peng Xu, Fred Roosta, and Michael W Mahoney, Second-order optimization for non-convex ma- chine learning: An empirical study. In Proceedings of the 2020 SIAM International Conference on Data Mining, pages 199-207, 2020.
[68] Yuzhe Yang, Guo Zhang, Dina Katabi, and Zhi Xu. ME-Net: Towards effective adversarial robustness with matrix estimation. In Proceedings of the 36th International Conference Machine Learning, 2019.
[69] Matthew D. Zeiler. ADADELTA: an adaptive learning rate method. abs/1212.5701, 2012.
[70] Chiyuan Zhang, Benjamin Recht, Samy Bengio, Moritz Hardt, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In 5th International Conference on Learning Representations, (ICLR), 2017.
[71] Guodong Zhang, Lala Li, Zachary Nado, James Martens, Sushant Sachdeva, George Dahl, Chris Shallue, and Roger B Gross. Which algorithmic choices matter at which batch sizes? insights from a noisy quadratic model. In Advances in Neural Information Processing Systems, pages 8194 8205, 2019.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 3, Section 5, and Appendix.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Our work does not present any foresecable societal impacts or consequences.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 3 and Appendix.
(b) Did you include complete proofs of all theoretical results? [Yes] See Section 3 and Appendix.
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] See supplemen- tary material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix.
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [N/A] Results under our proposed penalty are valid even across varying degrees of regularization strength (A) and several initial learning rates and across several initializations. Other results that were run with random seeds had negligible standard errors (see implementation details under the Appendix).
14

---

(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix.
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'le 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "XudPiCFayiz", "reviewer": "Reviewer_kNgp", "summary": "This paper proposes a new regularization for deep linear networks. The analyses sections showed theoretical analysis empirical results of this regularizer in the context of 1-layer/deep networks and SGD/Adam optimizer in matrix completion tasks where the ground truth matrix is low-rank. The main experiment was conducted on a recommender system task, showing the proposed regularizer on very simple models could perform complicated methods. \n ", "questions": "1. Line 45: what does \"acceleration\" mean? Please specify or give examples here. Also, I don't think this paper later even partially answers this question, except by deferring it to some sort of preconditioning. \n1. In the main experiments, are the features produced by linear mapping or nonlinear networks? If it's nonlinear networks, how is the regularization applied? \n1. Line 291: what's meant by \"without any factorizations\"? Isn't the model itself a factorized representation of the data matrix?\n1. I see that most derivations aim to express dynamics as preconditioned gradient descent, but could the authors justify why this particular preconditioning is good? Why not any preconditioning?\n2. Buttom line of page 19 (For some reason, the line numbers disappear), I cannot think of why the last equality holds. What's the \"factorization of Kronecker product\"? I did a simple search but could not find any properties related to this line. ", "limitations": "The discussion mentions some limitations and future work, but should also discuss limitations of the experiment design, including full-batch training, a single matrix factorization task and a single dataset. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths:\n1. I quite like the style of studying simple tasks and the way that the authors interleave illustrative examples with theoretical analyses. \n2. The synthetic example is used to compare a wide range of alternative methods/regularizations, clearly showing the advantage of the proposal. \n2. The authors performed extensive parameter sweeps as described in the appendix. \n3. The authors are clearly technical in their analyses. \n\n## Weaknesses:\n1. Writing is unclear to the extent that I cannot clearly see if the authors delivered the promise made in the introduction/contribution paragraph. I'm also not an expert in this field so could just be a background mismatch, but I find that the main message is overcomplicated and partially obscured by very scattered writing. \n2. This method does not seem to be directly applicable to nonlinear networks, but the main experiment might have demonstrated this but the description was not clear. \n3. The main experiment was only conducted in a single setting and dataset, which is somewhat lacking.\n3. The main theoretical advantage seems to be some form of preconditioning, but the authors did not go deep enough to suggest why such preconditioning may be beneficial, apart from being pos-semidef.\n3. Mathematical presentation needs to be thoroughly tidied up. \n4. The synthetic experiments are trained under full-batch, which does not really produce stochastic gradients.\n\n## Details:\n1. Line 54: depth is not necessary compared to deep linear networks, not any networks. I also find this statement and many other statements very strong, and then realize that the authors probably mean in the context of deep linear networks. \n2. Lines 30-31 say the task is to \"recover the unseen entries\", then in 58-62 the author describes that their regularizaton has an effect on the \"rank and generalization\", and the figure clearly does not give errors on how well the model recovers unseen entries. What exactly is the goal of the task? Is it to recover the unseen entries? To get the correct rank? Or test prediction which I assume is generalization? Please be clear here and everywhere.\n3. Lines 120-121: This part describes how the student network weights are set up. The first time I read it, I thought the authors meant that they focused on rank-5 matrices in each layer, but then understood that the rank-5 applies to the teacher matrix $W^*$. \n4. 135: what is singular value separation? This is undefined in the paper but gets mentioned a lot later. I'm a non-expert but I think doesn't take an expert to understand, it must be some trends shown in the figures. \n5. Line 158: \"the trajectory of ... its singular values $\\sigma_i$\" does not appear in the Lemma. Is this in equation (14) of the Appendix?\n6.  I don't think the rates in equations (3) and (6) are ever proved in the appendix. \n7. Line 190, comparing figures 1 & 2, top rows, I don't think this statement is supported by the figures. The curves stabilize at mostly some iteration numbers. Further, the green curve in Test Error actually converges slower.\n8. Section 4: I have no idea what the authors have done for the recommender system. Please use equations or give a reference.\n9. Line 519: the authors should define the rank in the main text explicitly rather than giving a reference in the appendix. If an approximate rank is used, perhaps the authors should also try other possible rank definitions. \n10. Line 211: \"evolves\" -> \"evolve\"", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "E0jAZKL3qI2", "reviewer": "Reviewer_ngkq", "summary": "Deep Linear Neural Networks gradient descent implicitly regularizes towards low-rank solutions in the matrix completion/factorization tasks. This work proposes an explicit penalty term that mimics the rank minimization behavior of deep linear networks. The proposed method is invariant to depth. A depth 1 linear neural network equipped with the proposed penalty produces the same rank reduction with comparable performance as deep matrix factorization. The authors note that their proposed penalty works really well with Adam optimizer but not with Gradient Descent. They speculate that the observed behavior could be due to the interaction of inductive biases inherent to the optimizers with explicit regularizers. They conduct a series of experiments to demonstrate this difference between Adam and Gradient Descent. Finally, they run experiments on real world data - MovieLens100k and show that they perform competitively against the existing methods which often use specialized architecture, parametrization, additional side information, etc. ", "questions": "If the authors could address the following weaknesses, I'd be more than happy to increase the scores -\n* The proposed method is depth invariant. If the authors could list potential areas where this could be useful, it would immensely help the paper.\n* It would be great if the authors could throw some theoretical insight into the reason behind performance discrepancy between various optimizers.", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* This work takes a unique approach towards rank minimization. They propose an explicit penalty that mirrors the implicit rank minimization of deep matrix factorization.\n* The proposed method is depth invariant which is an interesting property. \n* The proposed method achieves better generalization and rank-reduction performance beyond many techniques even in low data regimes.\n*  The authors note that their proposed penalty works really well with Adam optimizer but not with other optimizers such as Gradient Descent. The authors have done sufficient empirical evaluations to demonstrate the differences between the behavior of the penalty term under different optimizers.\n\nWeaknesses:\n* The proposed method is depth invariant. If the authors could list potential areas where this could be useful, it would immensely help the paper.\n* It would be great if the authors could throw some theoretical insight into the reason behind performance discrepancy between various optimizers.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "ClzcxH2gAdk", "reviewer": "Reviewer_LKjw", "summary": "This paper proposes a penalty for gradient descent that consists of the ratio between the nuclear (trace) norm of the weight matrix and its Frobenius norm. The paper shows analytically and empirically, in the task of matrix completion, that linear networks trained with the proposed penalty exhibit a large degree of independence on depth, as long as the models are optimised with Adam (or Adamax), but not with vanilla gradient descent. In particular, the paper presents results that show that in the degenerate case, that is a 1-layer linear network, the model trained with Adam and the proposed penalty achieves generalisation similar to deep networks as well as low rank and spectral sparsity.", "questions": "* Question: While the main claim is that the proposed penalty induces depth invariance with Adam, in Figure 2 we see some differences in the test error dynamics (bottom left) across different depths. In particular, with 2 layers, the dynamics are qualitatively very different and the model achieves lower error than with more layers. What do the authors think this is due to?\n* Suggestion: include repetitions in the experimental setup in order to obtain confidence intervals for the experimental analysis.\n* Suggestion: the actual proposed penalty is only expressed in the middle of a paragraph in Section 1. I think it would be clearer to include the explicit equation of the optimisation (Eq. 1) with the penalty. This would make it easier for future readers.\n* Suggestion: the title of Section 3.5, \"Comparative performance\" seems quite general. I would consider making it more specific, such as \"Comparison with other penalties and optimisers\". \n* Suggestion: same goes for the title of Section 4. How about \"Results on real-world data\"?", "limitations": "As mention above, the authors do briefly but explicitly discuss the limitations of their paper.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is, to the best of my judgement, an overall very good paper. First of all, the paper makes a very concrete contribution: the proposal of a penalty for gradient descent. The authors present a set of experiments that analyse 1) baseline conditions without the penalty, 2) the impact of the penalty on both vanilla gradient descent and models optimised with Adam, with particular attention to 3) the degenerate case (depth 1). Furthermore, the paper extends the empirical analysis by studying other optimisers and penalties, as well as some experiments on a real world data set (movies recommendations). With this experimental setup, the authors find an interesting result, namely that the proposed penalty induces certain degree of depth independence when the models are optimised with Adam but not with natural gradient descent. The paper provides a theoretical analysis of the dynamics under certain common assumptions and shows empirical results that analyse the generalisation performance, the rank of the weight matrix and the dynamics of the 1st and 5th singular values. \n\nIn terms of significance, I believe these are interesting results that can encourage further research into understanding the optimisation dynamics of neural networks and the interplay between implicit and explicit regularisation, which are topics that have attracted significant interest in the last decade. In terms of originality, the authors claim that the proposed penalty is novel and I am myself not aware of previous work proposing it, though I am not sufficiently up to date with the most recent literature on this specific domain.\n\nThe paper is very well written, much better than the average submission I have reviewed at machine learning conferences. The introduction is very clear and it smoothly motivates the problem by summarising the relevant related works and gaps in the literature. Section 2, on related work is easy to follow and concise. Then, the core section of the paper, Section 3, is very reasonably structured, following a logical order (setup, baseline models without penalty, models with the penalty, the degenerate case and other optimisers and penalties. The paper ends with a brief section where the role of the penalty is analysed on a real world data set and a discussion. I would also like to note that I have not identified any typo, which is extremely rare in the papers I have reviewed.\n\nRegarding quality, I think the paper is technically sound, the analyses seem correct to my judgement (though I have not thoroughly reviewed all the supplementary material) and the results support the claims. Furthermore, I would like to highlight that the authors humbly discuss the significance of their paper, in light of what the paper does show and does not show, as well as the limitations and aspects that are left for future work. This is, as well, and unfortunately, rare in machine learning submissions, but I highly appreciate it.\n\nI can identify some weaknesses, but these are minor and most are actually mentioned by the authors in Section 5. These mostly have to do with the limited scope of the experiments and analyses, which leave some open questions, such as: the role of the penalty on non-linear networks, on other tasks and data sets, whether other penalties can achieve the same depth-independence, a more thorough analysis of why the penalty only works with Adam and whether the same dynamics could be induced with a modification of the penalty on vanilla gradient descent. Since it is impossible to address all these questions properly in a single paper and the authors actually mention them, I consider these weaknesses minor, or not at all. \n\nFinally, one aspect that could be improved in the paper is the fact that the results (plots) from the empirical analyses seem to reflect single experiments. I think the conclusions and insights would be stronger if repetitions were carried out (with various initialisation seeds, for instance, and, ideally, choices of $\\Omega$) in order to obtain a measure of the confidence intervals for the dynamics.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "3LmF3znz-tj", "reviewer": "Reviewer_C4mW", "summary": "The authors develop a novel regularization method that improves the performance of shallow linear neural networks on tasks that can be represented as low-rank matrix completion/factorization. They offer theoretical results for analyzing such models under vanilla gradient descent vs. ADAM, and show that an adaptive scheme allows shallower networks to converge to better solutions.", "questions": "Either make each lemma a theorem / corollary, or explicitly state the overarching theorem.\n\nLine 168-9: It would be helpful to characterize the condition under which normalization will dampen or accelerate the trajectory. Why does it accelerate in the case you specified?\n\nLine 230-1: \"This similarly holds for un-regularized Adam\" is confusing after reading the previous sentence, and suggests the opposite of what you want to say. Reword / swap the order.\n\nEqn (6): GD -> GF\n\nI think the appendix should include explicit proofs of Lemmas 2 and 3. Even if they are easy to compute, it will still help some readers follow along more easily.\n\nAdd bolding to Table 1 to highlight that your penalty is superior for all the adaptive optimizers.", "limitations": "The authors acknowledge that the connection between linear and nonlinear networks in this context is not explored, and that the gradient flow regime may not hold in some practical settings. The authors point to good future directions.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\nThe proposed method is simple and effective, supported by thorough theoretical and empirical justification.\nThe experiments are logical and comprehensive (including appendix), with good interesting results that are easy to interpret.\nThe text is clear and well-written. The figures are also clear.\n\n\nWeaknesses\n\nIn general, it would be helpful to be even more explicit about the connection between the forms of the various dynamics equations and the empirical results. For example, it would be nice to plot the predicted trajectories of the singular values against the actual trajectories. I still don't have good intuition for the behavior of the dynamics equations, so highlighting different regimes of behaviors would be helpful. For example, when the authors say that a term may accelerate convergence (line 168-9, 202), it would be helpful to describe (or give intuition for) the conditions under which such acceleration occurs, before jumping to the empirical demonstrations that acceleration is indeed observed. How does the convergence rate or error scale with effective rank of the underlying matrix (Appendix experiment does not really answer this)?\n\nAs the authors acknowledge in limitations, the scope of their findings is fairly narrow. Even though this is a theory paper, perhaps the motivation could be strengthened by noting that shallow networks are extremely fast and lightweight and thus could find use in applications where these attributes are important.\n\nThe title would suggest a very different line of work than what is being examined. Indeed, it is a little misleading in the sense that the paper's main results pertain to depth-1 and depth-2 linear networks, whereas the title writes \"deep networks\". IMO the title should highlight that the authors develop a novel regularization method that is effective for shallow networks. The title also suggests that the authors design a novel implicit regularization scheme, whereas it seems that implicit regularization refers to an existing property of gradient-based methods (the tendency to favor low-norm solutions). It seems that this implicit regularization is innate to both SGD and Adam, but it would be clearer if the authors instead highlight the property of adaptive optimizers that makes them more effective in the regime studied.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept