Implicit Regularization in Deep Learning May Not Be Explainable by Norms

Noam Razin; Nadav Cohen

Source-linked AI summary

Implicit Regularization in Deep Learning May Not Be Explainable by Norms

Noam Razin, Nadav Cohen

arXiv:2005.06398v2May 13, 2020cs.LGcs.NEstat.ML

TL;DR

The paper asks whether implicit regularization in matrix factorization can be characterized by norm minimization. It analyzes gradient-based optimization and proves that natural problems can instead send every norm and quasi-norm to infinity while favoring low rank, with empirical extension to tensor factorization.

Problem
The open question is whether the implicit regularization induced by gradient-based optimization in matrix factorization is explained by minimizing norms or quasi-norms.
Method
The paper analyzes gradient flow for depth-L matrix factorization with balanced initialization and corroborates the theory through matrix- and tensor-factorization experiments.
Results
For natural matrix-completion problems, gradient-based optimization can drive all norms and quasi-norms toward infinity while the product matrix’s rank essentially decreases toward its minimum.
Takeaways & Limitations
The findings support interpreting implicit regularization as rank minimization rather than norm minimization, with analogous low-rank behavior observed for tensor factorization.
Takeaways & Limitations
The tensor-factorization extension is shallow; investigating hierarchical factorizations corresponding to deep convolutional arithmetic circuits remains future work.

Abstract

from arXiv · show

Mathematically characterizing the implicit regularization induced by gradient-based optimization is a longstanding pursuit in the theory of deep learning. A widespread hope is that a characterization based on minimization of norms may apply, and a standard test-bed for studying this prospect is matrix factorization (matrix completion via linear neural networks). It is an open question whether norms can explain the implicit regularization in matrix factorization. The current paper resolves this open question in the negative, by proving that there exist natural matrix factorization problems on which the implicit regularization drives all norms (and quasi-norms) towards infinity. Our results suggest that, rather than perceiving the implicit regularization via norms, a potentially more useful interpretation is minimization of rank. We demonstrate empirically that this interpretation extends to a certain class of non-linear neural networks, and hypothesize that it may be key to explaining generalization in deep learning.

1 Introduction

The paper studies whether gradient-based implicit regularization in matrix factorization can be characterized by minimizing norms or quasi-norms. It proves that some natural problems instead drive all such quantities to infinity while favoring low rank, and reports analogous empirical behavior for tensor factorization.

Motivation: The central open question is whether implicit regularization in matrix factorization can be explained by minimizing a norm or quasi-norm.Linear regression provides precedent through convergence to a minimum-ℓ2-norm solution.
Motivation: Matrix completion uses observed entries to recover unseen entries and serves as a test-bed for studying implicit regularization and generalization.Observed entries form the training set, while reconstruction error on unobserved entries measures test error.
Main result: Gradient descent on certain depth-L≥2 matrix factorizations drives all norms and quasi-norms toward infinity while rank essentially decreases toward its minimum.This occurs with probability at least 0.5 over arbitrarily small random initializations.
Main result: The result jointly disqualifies all norms and quasi-norms on the same problems, strengthening the conjecture that norms need not explain implicit regularization.It goes beyond showing that each norm can fail on a different setting.
Interpretation: The paper proposes minimization of rank as a potentially more useful interpretation of implicit regularization in matrix factorization.This contrasts with the nuclear-norm approach, which treats nuclear norm as a convex relaxation of rank.
Extension: Tensor-factorization experiments similarly find low-rank solutions and connect tensor factorization to convolutional arithmetic circuits, a class of nonlinear neural networks.The paper presents this as a second neural-network exemplar whose input-output mapping tends toward lower rank.

2 Related work

Prior work has extensively studied implicit regularization through norms and low-rank recovery, but theoretical support for norm failure in matrix factorization was previously absent. The paper adds such support and reports evidence for unregularized tensor recovery.

Implicit regularization: Implicit-regularization research has characterized optimization dynamics, curvature, frequency spectra, invariants, data statistics, and norm or margin minimization.Norm-based characterizations span many model classes, including linear and neural-network settings.
Matrix factorization: Matrix factorization is a major model for studying non-convex implicit regularization and recovering low-rank linear mappings without explicit regularization.Several works prove successful low-rank recovery, while prior conjectures offered opposing views about nuclear-norm minimization.
Open gap: Before this paper, no theoretical support was known for the conjecture that matrix-factorization implicit regularization cannot generally be described by norm or quasi-norm minimization.The paper’s proof relies on technical results from earlier work.
Tensor factorization: Tensor factorization is widely studied for low-rank tensor recovery, but these experiments provide the first reported evidence of successful unregularized gradient-based recovery without imposing low rank.The claim concerns the authors’ awareness of prior evidence.

3 Deep matrix factorization

The paper models matrix factorization as a depth-L linear network and studies the product matrix selected by gradient flow in an unconstrained, overparameterized setting. The analysis uses near-zero balanced initialization as a surrogate for practical gradient descent.

Model: A depth-L matrix factorization parameterizes the product matrix as W=WLWL−1⋯W1 and optimizes an overparameterized fitting objective.The hidden dimensions are chosen so the product rank is unconstrained.
Objective: The framework examines which product matrices gradient-based optimization selects among multiple solutions fitting the observations.This selection is the paper’s object of implicit-regularization analysis.
Optimization: The analysis focuses on gradient flow, treating it as a theoretical surrogate for gradient descent with infinitesimal learning rate and near-zero initialization.This follows prior analyses of linear neural networks.
Initialization: Balanced initialization imposes equality between adjacent layer Gram matrices at initialization and supports a differential-equation analysis of the product matrix.The condition holds exactly in residual identity initialization and approximately with high probability for Xavier and He initialization.
Initialization: Theoretical predictions under balanced gradient flow closely match practical gradient descent with small learning rates and near-zero initialization.The paper also reports support for extending the theory to approximately unbalanced initialization.
Conjectures: Conjecture 1 concerns depth-2 convergence to a minimum nuclear-norm solution, whereas Conjecture 2 allows norm or quasi-norm failure for any depth L≥2.Technical differences mean the conjectures are not formally contradictory despite opposing stances.

4 Implicit regularization can drive all norms to infinity

For a natural 2-by-2 matrix completion problem, deep matrix factorization can reduce loss while driving every norm and quasi-norm to infinity and effective rank toward its minimum. This resolves the norm-based interpretation negatively in the constructed setting and supports rank minimization as the more useful interpretation.

4.1 A simple matrix completion problem: The construction uses a 2-by-2 completion problem with observed entries b1,2 = 1, b2,1 = 1, and b2,2 = 0.The analysis considers depth L ≥ 2 matrix factorization trained by gradient flow on this problem.
4.1 A simple matrix completion problem: Every norm or quasi-norm has bounded near-minimizers along the solution set, while Schatten-p norm minimizers occur only at W1,1 = 0.This includes the nuclear, Frobenius, and spectral norms as p = 1, 2, and infinity, respectively.
4.1 A simple matrix completion problem: All solutions have rank 2, but taking |W1,1| toward infinity can essentially reduce the rank to 1.Effective rank decreases monotonically toward 1, and distance from the infimal rank decreases toward 0 as |W1,1| grows.
4.2 Decreasing loss increases norms: With positive determinant at initialization, lowering loss increases all norms and quasi-norms while effective rank decreases toward its infimum.Theorem 1 applies to depth L ≥ 2 matrix factorization under gradient flow.
4.2 Decreasing loss increases norms: When loss converges to zero, all norms and quasi-norms diverge while rank is essentially minimized, contradicting norm minimization in this setting.The positive-determinant condition holds with probability 0.5 for the specified symmetric random initialization distributions.
4.4 Robustness to perturbations: The result extends to arbitrary nonzero off-diagonal observations and arbitrary diagonal observations when the initialization determinant has the same sign as their product.The generalized sign condition also occurs with probability 0.5 under the covered random distributions, and the phenomenon persists across unobserved-entry locations.
4.2 Decreasing loss increases norms: Thus, in the constructed finite matrix-completion setting, implicit regularization abandons norm or quasi-norm minimization in favor of essentially minimizing rank.The paper establishes this by lower bounds that diverge as training loss approaches zero.

5 Experiments

The experiments test the theoretical matrix-factorization phenomenon and extend the investigation to tensor factorization. Matrix experiments examine norm growth as loss decreases, while tensor experiments assess whether gradient-based optimization favors low-rank solutions and its connection to nonlinear networks.

Experimental design: The experiments evaluate deep matrix factorization in the settings analyzed theoretically, then extend the study to tensor factorization.The tensor experiments are intended to assess how broadly the rank-based interpretation extends.
Matrix factorization: Matrix-factorization runs track the absolute value of an unobserved entry against loss across depths, learning rates, and initialization scales.Both balanced and unbalanced random initializations are evaluated.
Matrix factorization: The matrix experiments are designed to show unobserved-entry magnitude increasing as observations are fit and loss decreases, corresponding to increasing norms and quasi-norms.The plots vary depth, learning rate, initialization, and balancedness.
Tensor factorization: Tensor factorization minimizes a tensor-completion loss by gradient descent over a CP-style parameterization with R terms, where R is large enough to express any tensor.The comparison baseline directly optimizes tensor entries from zero initialization while leaving unobserved locations at zero.
Tensor factorization: Tensor experiments compare reconstruction error and numerically estimated rank against the number of observations for low-rank ground-truth tensors.The reported examples use rank-1 tensors of sizes 8-by-8-by-8 and 8-by-8-by-8-by-8.
Tensor factorization: Tensor factorization exhibits an implicit tendency toward low tensor rank, with accurate reconstruction of low-rank tensors and a stronger tendency under smaller initialization.This extends the observed interpretation beyond matrix factorization.
Nonlinear-network connection: The tensor factorization corresponds to a shallow convolutional arithmetic circuit whose output is the factorized tensor entry for each one-hot input tuple.The network uses R channels, locally connected linear operators, global pooling, and summation.
Nonlinear-network connection: The studied convolutional arithmetic circuit is shallow; hierarchical factorization would correspond to deep convolutional arithmetic circuits and remains future work.The paper identifies investigation of implicit regularization in those deeper models as a promising direction.

6 Summary

The paper concludes that norms and quasi-norms do not generally explain implicit regularization in matrix factorization. Its constructed problem instead supports interpreting the phenomenon as rank minimization, with empirical evidence extending this interpretation to tensor factorization and a class of nonlinear networks.

Norm-based explanation: The paper addresses whether gradient-based implicit regularization in matrix factorization can be characterized by minimizing a norm or quasi-norm.Matrix completion serves as the standard test-bed because observed entries form training data and unobserved entries measure generalization.
Main conclusion: In a natural matrix-completion setting, gradient descent drives all norms and quasi-norms toward infinity with probability at least 0.5 while essentially minimizing rank.The result holds over random initialization in the stated setting.
Rank interpretation: The construction creates a direct conflict between norm minimization and rank minimization, and gradient descent favors rank over norms.This motivates viewing implicit regularization through rank rather than norm minimization.
Broader interpretation: The paper presents rank minimization as a potentially more useful interpretation of implicit regularization and empirically explores its generality through tensor factorization.The supported empirical extension concerns tensor factorization and corresponding nonlinear networks.

Broader Impact

The paper situates its contribution within efforts to make deep learning more principled, while the appendix studies how theoretical results extend beyond perfectly balanced initialization. These extensions rely on closeness to balanced initialization and continuity of optimization trajectories, but one approach incurs time-growing error terms.

Broader impact: The paper aims to strengthen theoretical foundations for deep learning, which may support more principled use and help address practical concerns such as safety, privacy, and fairness.The paper frames this work as one step toward that broader goal.
Initialization assumptions: Unbalancedness measures deviation from the balanced-initialization condition used in the main theory.The appendix defines unbalancedness magnitude for the factor matrices and studies small initial values.
Extension strategy: Small unbalancedness implies proximity to a perfectly balanced initialization, enabling the main theorems to be transferred through controlled trajectory differences.The transfer adds error terms to bounds on norms, effective rank, and distance from infimal rank.
Trajectory continuity: Gradient-flow trajectories for smooth objectives are Lipschitz continuous with respect to initialization over finite time.This continuity is the general ingredient used to compare trajectories from balanced and unbalanced initializations.
Scope and limitation: The appendix extends theorems for arbitrary matrix-completion tasks by comparing two gradient-flow trajectories from different initializations.The specialized proposition is applied to overparameterized depth-L matrix factorizations.
Scope and limitation: The continuity-based extension has a drawback: bounds on trajectory distance and induced error terms grow exponentially with time.A second approach uses properties specific to deep matrix factorization to overcome this growth for depth L ≥3.

A.2 Second approach: conservation of unbalancedness magnitude

The analysis uses conservation of unbalancedness magnitude to relate unbalanced gradient-flow trajectories to nearby balanced ones. This yields bounds that persist for a guaranteed period or until terminal norm and rank-related bounds are reached.

Unbalancedness magnitude remains constant throughout gradient flow over deep matrix factorization.
Gradient-flow dynamics preserve a layerwise balance relation, obtained by integrating the evolution of adjacent factors.
Small initial unbalancedness ensures every optimization point lies near a balanced factorization, enabling balanced-trajectory arguments.
Theorem 3 extends Theorem 1 to unbalanced initialization, under square-factorization and additional initialization and loss assumptions.
Theorem 1 bounds on norms, effective rank, and distance from infimal rank hold until a time threshold or jointly satisfied terminal bounds.
As initialization unbalancedness ϵ approaches zero, the guaranteed period tends to infinity and the terminal bounds approach Theorem 1’s zero-loss limits.

B Extension to different matrix dimensions

The construction extends from 2-by-2 completion to arbitrary square and rectangular matrix dimensions. Its block structure preserves the original two-dimensional mechanism while fixing additional singular values at one.

Appendix B extends the construction and analysis to matrix completion beyond 2-by-2 dimensions.
For square matrices, the construction observes all entries except the top-left entry, using a structured pattern of values.
The higher-dimensional solution set has a 2-by-2 top-left block containing the original construction and an identity bottom-right block.
This structure fixes d −2 singular values at one while leaving the remaining two equal to those of the original solution set.
For arbitrary dimensions, decreasing loss can increase the absolute unobserved entry, thereby increasing norms and quasi-norms.
The same construction extends to rectangular matrices by adding zero observations so only the (1,1) entry remains unobserved.

C.1 Further experiments

Further experiments test the predicted divergence and low-rank behavior beyond the core 2-by-2 setting. They examine arbitrary dimensions, perturbations, tensor rank, and implementation choices supporting reproducibility.

Figures 4 and 5 test whether norm divergence extends across dimensions and remains robust to perturbed observations.
The experiments use fixed learning-rate gradient descent until loss falls below 10^-4 or 5 · 10^6 iterations elapse.
Deep matrix factorization experiments use minimal hidden dimensions that preserve an unconstrained search space.
Initialization varies between independently sampled unbalanced factors and a balanced procedure based on Gaussian factors.
Figure 6 tests tensor factorization on ground-truth tensors of rank 3 and reports implicit regularization toward low tensor rank.
Tensor experiments choose the number of terms to ensure an unconstrained search space and estimate tensor rank using ALS error below 10^-6.

D.3 Proof of Proposition 1

The proof shows that norm minimizers over the constructed solution set are confined near the unobserved entry’s zero value. For Schatten quasi-norms, the minimum occurs exactly at that value.

For any quasi-norm, sufficiently large absolute unobserved entries exceed the minimum norm by more than ϵ, so ϵ-minimizers form a bounded set.
For Schatten-p quasi-norms, the solution matrix is a minimizer if and only if its unobserved entry equals zero.
The spectral norm at the zero-entry solution is 1, whereas any positive or negative unobserved entry makes it strictly larger.
For positive x, Schatten-p quasi-norms increase with x, while for negative x they decrease as x approaches zero.

D.4 Proof of Proposition 2

The proof shows that along the solution family, singular values separate as |x| grows: one diverges while the other vanishes. Consequently, effective rank approaches 1 and distance to the minimum rank approaches 0.

Singular-value behavior: σ1(Wx) increases and σ2(Wx) decreases for x > 0, with the two singular values even in x.Thus, σ1(Wx) decreases and σ2(Wx) increases for x < 0; as |x| grows, σ1 diverges while σ2 vanishes.
Technical condition: The argument relies on continuity of the Schatten-p quasi-norm of Wx in x for every p ∈(0, ∞).This continuity claim does not assert that quasi-norms are generally continuous.
Effective rank: The effective rank of Wx is bounded by 2 and attains its maximum at x = 0.The bound follows from the binary entropy function being at most ln(2).
Effective rank: As |x| →∞, the effective rank monotonically decreases toward 1.The normalized leading singular value approaches 1, concentrating the effective-rank distribution on one component.
Infimal rank: The infimal rank of S is 1, and D(Wx, M1) = σ2(Wx) tends monotonically to 0 as |x| →∞.The distance is maximized at x = 0 and vanishes in the limit.

D.5 Proof of Theorem 1

The proof establishes that decreasing the loss forces a product-matrix entry, and therefore every norm and quasi-norm, to diverge. At the same time, singular-value bounds show that effective rank and distance to rank one approach their minima.

Divergence of norms: Decreasing the loss toward zero drives |w1,1| toward infinity.This follows from the loss-dependent lower bound on |w1,1|.
Singular-value bounds: The singular values of WL:1 are bounded in terms of the loss, enabling the effective-rank and rank-distance conclusions.The proof first derives loss-dependent bounds on σ1(WL:1) and σ2(WL:1).
Quasi-norm lower bound: For any quasi-norm satisfying the weakened triangle inequality, the proof lower-bounds its value using homogeneity and the diverging entry |w1,1|.The initial assumption ℓ(WL:1) < 1/2 is later removed because the resulting bound is vacuous but valid for larger losses.
Quasi-norm lower bound: The quasi-norm bound holds for all loss values after observing that it is trivially valid when ℓ(WL:1) ≥ 1/2.For those losses, the right-hand side is non-positive.
Effective rank: The normalized second singular value satisfies ρ2(WL:1) ≤ 12ℓ(WL:1), yielding an effective-rank bound that approaches 1 as the loss vanishes.The proof uses the binary entropy representation of effective rank and removes the temporary assumption ℓ(WL:1) < 1/32 because the bound is then trivial.
Distance to rank one: Because the infimal rank of S is 1, the distance D(WL:1(t), M1) equals σ2(WL:1(t)) and is controlled by the loss.Thus, convergence of the loss controls distance to the minimum-rank set.
Initialization probability: The product determinant is positive or negative with probability 0.5 under independent random factor initialization.The argument uses symmetry under row sign reversal, absence of zero determinants, determinant multiplicativity, and total probability.

D.7 Proof of Proposition 4

For positive-definite product initialization, gradient flow preserves the relevant structure while driving the loss downward. The dynamics force selected entries toward limiting values, which yields convergence to zero loss.

Positive definiteness: With initial product WL:1(0) = α · I for α ∈(0, 1], gradient flow keeps WL:1(t) positive definite.This invariant is the starting point for the subsequent entrywise analysis.
Global loss convergence: For every ϵ > 0, there exists tϵ such that the loss is below ϵ, so limt→∞ℓ(WL:1(t)) = 0.The proof combines w1,2(t) → 1 with a time at which w2,2(t) is sufficiently small.
Entrywise invariants: Throughout the dynamics, w1,1 remains positive and monotonically non-decreasing, while 0 < w2,2 ≤ 1.These bounds follow from positive definiteness and the entrywise differential equations.
Loss dynamics: The loss is monotonically non-increasing throughout time.The derivative analysis bounds d/dt ℓ(WL:1) by a non-positive quantity.
Entrywise convergence: The off-diagonal entry w1,2 converges to 1 as t tends to infinity.Defining g(t) := (1 − w1,2(t))^4 and bounding its derivative establishes the convergence.

D.7.1 Proof of Lemma 20

The proof shows that symmetric factorizations preserve symmetry under gradient flow. Balanced initializations can be replaced by symmetric balanced ones with the same product, transferring this invariant to the original trajectory; positive definiteness is then preserved as well.

Preservation under flow: The inductive argument shows every time derivative of the product remains symmetric, so WL:1(t) is symmetric throughout optimization.Higher-order product-rule terms are paired with their reverse-index counterparts to form symmetric sums.
Symmetric factorization: A symmetric factorization is one in which the factors are paired by transposition, and it implies that the product matrix is symmetric.The latter implication is stated directly for matrices with a symmetric factorization.
Preservation under flow: Under symmetric-factorization initialization, the factor pairing Wl(t) = WL−l+1(t)⊤ persists for all t ≥ 0.The proof establishes this by induction over time derivatives and the gradient-flow dynamics.
Transfer to balanced initialization: A balanced initialization can be transformed into a balanced symmetric factorization with the same initial product matrix.The modified factors therefore induce a symmetric product trajectory.
Transfer to balanced initialization: Because balanced product trajectories depend only on the initial product, the original and modified factorizations produce identical product trajectories.Thus, symmetry proved for the modified initialization transfers to the original one.
Positive definiteness: Positive definiteness is preserved because the determinant remains positive and continuous eigenvalues cannot change sign.The argument uses the absence of zero eigenvalues along the analytic trajectory.

D.8 Proof of Theorem 2

The proof bounds the product matrix’s singular values and shows that gradient descent approaches solutions with infimal rank 1, while certain norms can grow without bound.

The proof derives loss-dependent bounds for entries and singular values of the product matrix W_L:1.It first treats sufficiently small loss and then extends the bounds to all loss values.
When the loss is small, the determinant sign constrains matrix-entry signs and forces the relevant entry w_1,1 to grow as the loss decreases.The argument uses the preserved determinant sign together with sign relations among the observed and unobserved entries.
As |ϵ| becomes smaller relative to |z · z′|, minimizing the loss drives |w_1,1| higher and yields a lower bound on the largest singular value.
The resulting norm bounds apply to any norm or quasi-norm satisfying the weakened triangle inequality, and can grow with |w_1,1| as the loss is minimized.The proof removes the small-loss assumption because the bound is otherwise trivially non-positive.
The solution set has infimal rank 1, including when ϵ = 0, because sending the free entry to infinity drives the smallest singular value toward zero.For ϵ ≠ 0, a rank-1 solution exists directly; for ϵ = 0, rank 1 is approached arbitrarily closely.
The same bounds remain valid when the observed entry locations change, so the conclusions do not depend on one specific missing-entry position.

D.13.1 Proof of Equation (21) (if weight matrices are bounded by R)

This proof establishes a lower bound on the time required for a product matrix to become singular while all factor matrices remain bounded by R, using continuity, singular-value control, and balanced factorizations.

Assuming factor Frobenius norms stay at most R, monotonic loss decrease bounds the product’s observed entries and supports control of its singular values.
The proof identifies the first time a singular value reaches the threshold needed to approach a zero determinant, then analyzes the interval preceding that time.Continuity ensures the relevant starting time is well defined and the minimal singular value remains positive before the endpoint.
Balanced factor matrices with the same product provide a comparison path whose singular values match those of the original factors.
The singular-value argument requires care because analytic singular values can change order, although the proof excludes order changes on the relevant interval.
For L = 2 and L ≥ 3, the argument combines these estimates with the determinant condition to obtain explicit lower bounds on the singularity time.
Perturbation bounds, triangle inequalities, and Frobenius-norm estimates control the movement of the product and its singular values along this comparison.