Introduction
In modern deep learning, we frequently train "overparameterized" models—networks equipped with far more parameters than there are data points. Mathematically, this means there are infinitely many ways for the model to fit the training data perfectly. Yet, gradient descent consistently gravitates toward specific solutions that generalize well to unseen data. This phenomenon is known as implicit bias.
While previous research has explored this bias in isolated cases (such as simple linear regression or specific "diagonal" networks), the field has lacked a cohesive, overarching theory. Furthermore, many existing proofs rely heavily on "convergence assumptions"—essentially assuming the optimization algorithm will succeed before proving how it behaves. This paper bridges these gaps by providing a unified mathematical framework that covers multiple architectures, proving both convergence and bias simultaneously without requiring explicit regularization.
Methodology: Linear Tensor Networks
To build a unified theory, the authors introduce a novel abstraction called Linear Tensor Networks. This framework allows them to treat fully-connected, diagonal, and convolutional networks as special cases of the same mathematical object.
- Tensor Formulation: The output of most common linear architectures can be written as a multilinear product involving a "data tensor" $\mathbf{M}(x)$ and weight vectors for each layer.
- Singular Vectors of Tensors: To describe where the weights "land" after training, the authors utilize a generalized definition of singular vectors for higher-order tensors.
- Orthogonal Decomposability: For complex architectures, they introduce a structural assumption that allows them to decompose the network's behavior into independent components, making the analysis of deep convolutional and diagonal networks mathematically tractable.
- Gradient Flow Analysis: The study focuses on "gradient flow"—the continuous-time version of gradient descent with an infinitesimal step size—to characterize the trajectory of parameters from initialization to the global minimum.
Because this is a foundational theoretical paper, the authors validate their theorems using synthetic "toy" datasets, including a simple 2D regression task and a 2D classification task. This simplicity allows them to plot the exact trajectories of linear coefficients in space and compare them against theoretical predictions.
Key Insights and Results
Architecture as a Coordinate Transform
The core insight of this work is that a network's architecture acts as a transformation on the input space. Implicit bias is not merely a property of the optimization algorithm; rather, it is the result of the algorithm interacting with the specific geometry defined by the architecture.
The $L_{2/L}$ Margin in Classification
For classification tasks, the authors show that as networks get deeper (depth $L$), the implicit bias shifts toward maximizing the margin according to an $L_{2/L}$ quasi-norm. For a 2-layer network ($L=2$), this equates to the standard $L_1$ norm, which promotes sparsity. For deeper networks, the bias becomes even more aggressively "sparsity-inducing."
The "Knob" of Initialization in Regression
In regression tasks, the scale of initialization (denoted as $\alpha$) acts as a critical bridge between different types of solutions. Small initializations lead to solutions that minimize a weighted $L_1$ norm (sparse solutions), while large initializations lead to $L_2$ norm solutions (dense solutions).
For underdetermined regression, the authors prove that gradient flow finds a global minimum that minimizes a specific "norm-like" function. This function effectively interpolates between $L_1$ and $L_2$ behaviors based entirely on the initialization scale. Specifically, for deep fully-connected networks, the linear coefficients always converge to the minimum $L_2$ norm solution as the initialization scale approaches zero, regardless of the network's depth.
Removing Convergence Assumptions
Crucially, unlike prior work, these theorems do not assume the loss will naturally go to zero. Instead, they prove that under certain initialization conditions, the loss must go to zero while simultaneously following the biased path.
Limitations and Future Work
While this framework provides a powerful unified view, it is not without limitations:
- Linearity Constraint: The most significant limitation is that the study is restricted to linear networks (omitting non-linear activations like ReLU). While linear networks provide deep insights into the role of architecture, practical deep learning relies heavily on non-linearities.
- Infinite Time vs. Finite Steps: The theory describes the "limit point"—training to zero loss over infinite time. In practice, training is stopped early. The authors note that actual coefficients can remain somewhat dependent on initialization if the loss isn't driven extremely low.
- Complexity of Tensors: Characterizing the singular vectors of high-order tensors is NP-hard in the general case. While the "orthogonally decomposable" assumption bypasses this hurdle, future work could explore ways to relax this constraint to accommodate even more exotic architectures.
Summary updated