Abstract
In the study of deep learning generalization, the "implicit bias" of gradient-based optimization is a central mystery. While classical theory suggests that overparameterized models should overfit, neural networks often generalize well due to an inherent tendency of gradient descent to find high-margin solutions. This paper, presented at ICML 2019, extends the theoretical understanding of this phenomenon from simple homogeneous models to more complex, non-homogeneous architectures. The authors demonstrate that optimization naturally favors deeper components in ensembles and converges to a "lexicographic" max-margin solution that sequentially maximizes distances to all training points.
Introduction
One of the most significant challenges in modern machine learning is explaining why deep neural networks generalize so effectively. Despite having far more parameters than training examples—a regime where classical statistics predicts severe overfitting—these models consistently perform well on unseen data. The prevailing hypothesis is that the optimization process itself (Gradient Descent without explicit regularization) acts as an implicit regularizer, steering the model toward "simpler" or "smoother" solutions.
Previous research primarily focused on homogeneous models, where scaling the weights by a factor $\alpha$ results in the output being scaled by $\alpha^d$. However, real-world architectures are often non-homogeneous. This paper bridges that gap, analyzing how gradient descent behaves in non-homogeneous settings, such as ensembles of networks with varying depths, and introduces a more nuanced view of margin maximization.
Theoretical Framework: The Three Paths
To analyze the implicit bias, the authors examine the relationship between three distinct mathematical trajectories:
- The Optimization Path: The actual trajectory of weights during unconstrained gradient descent.
- The Constrained Path: The set of solutions found by minimizing loss while gradually increasing a hard constraint on the norm of the weights.
- The Regularization Path: The solutions found by minimizing loss with a vanishingly small weight-decay penalty ($L_2$ regularization).
The study focuses on exponentially tailed loss functions (such as exponential or logistic loss). By characterizing the limits of these paths as weight norms grow toward infinity, the authors provide a rigorous framework for understanding the final state of a trained model.
Lexicographic Max-Margins
A key contribution of this work is the concept of lexicographic max-margins. In traditional Support Vector Machines (SVMs), the "max-margin" solution is defined solely by the distance to the closest data point (the support vectors).
The authors prove that for homogeneous models, the optimization path converges to a solution that is far more refined. It doesn't just maximize the minimum margin; it sequentially maximizes the margins to all data points. Once the distance to the closest point is maximized, the optimization process (among all equivalent solutions) maximizes the distance to the second closest point, and so on. This lexicographic ordering provides a much more comprehensive description of the implicit bias than a single margin value.
Depth-Sensitive Bias in Ensembles
Perhaps the most striking finding of the paper is the "depth-sensitive" bias observed in non-homogeneous ensembles. When a model consists of a sum of sub-models with different depths (e.g., an ensemble of a 2-layer, 3-layer, and 5-layer network), the optimization process exhibits a clear preference.
Theorem 1 states that for a sum of homogeneous sub-models, the solution converges to a state where the weights of the shallower, "unnecessary" sub-models vanish. If a deeper network is capable of satisfying the classification constraints, the gradient descent dynamics will effectively discard the shallower components to maximize the margin. This is counter-intuitive, as deeper networks are often perceived as more difficult to optimize, yet the mathematical bias of the margin inherently favors them over their shallower counterparts.
Correcting the SVM Bias
The paper also resolves a lingering issue in optimization theory regarding SVMs. Previous attempts to explain SVM behavior using unregularized bias terms failed to align with the standard $L_2$ max-margin solution. By treating the bias as a component of a non-homogeneous model, the authors' theory correctly predicts the $L_2$ max-margin solution, unifying the theory of implicit bias with classical results.
Conclusion and Future Directions
This research provides a rigorous foundation for understanding how depth and non-homogeneity influence the solutions found by gradient descent. By proving that optimization favors deeper models and follows a lexicographic margin maximization path, the authors offer a clearer picture of why complex networks generalize.
However, several challenges remain. The current analysis assumes sub-models in an ensemble are independent. In modern architectures like ResNets, skip connections mean that variables are shared across different effective depths, complicating the mathematical analysis. Furthermore, while the authors prove convergence to stationary points, the question of whether gradient descent consistently finds the global maximum margin in non-convex landscapes remains a fertile ground for future research.
Summary updated