Gradient Descent Maximizes the Margin of Homogeneous Neural Networks

By Kaifeng Lyu, Jian Li. 2019

417 citations recorded by the source corpus.

In this paper, we study the implicit regularization of the gradient descent algorithm in homogeneous neural networks, including fully-connected and convolutional neural networks with ReLU or LeakyReLU activations. In particular, we study the gradient descent or gradient flow (i.e., gradient descent with infinitesimal step size) optimizing the logistic loss or cross-entropy loss of any homogeneous model (possibly non-smooth), and show that if the training loss decreases below a certain threshold, then we can define a smoothed version of the normalized margin which increases over time. We also formulate a natural constrained optimization problem related to margin maximization, and prove that both the normalized margin and its smoothed version converge to the objective value at a KKT point of the optimization problem. Our results generalize the previous results for logistic regression with one-layer or multi-layer linear networks, and provide more quantitative convergence results with weaker assumptions than previous results for homogeneous smooth neural networks. We conduct several experiments to justify our theoretical finding on MNIST and CIFAR-10 datasets. Finally, as margin is closely related to robustness, we discuss potential benefits of training longer for improving the robustness of the model.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Tengyu Ma
2. Jason D. Lee
3. Zeyuan Allen-Zhu
4. Colin Wei
5. Wei Hu
6. Yuanzhi Li
7. Percy Liang
8. Simon Shaolei Du

In Computer Vision and Pattern Recognition

1. Tengyu Ma
2. Jason D. Lee
3. Luc Van Gool
4. Colin Wei
5. Dacheng Tao
6. Francis R. Bach
7. Andrew Zisserman
8. Wei Hu

In Optimization & Training

1. Jason D. Lee
2. Tengyu Ma
3. Nati Srebro
4. Wei Hu
5. Colin Wei
6. Zeyuan Allen-Zhu
7. Yuanzhi Li
8. Francis R. Bach

Citations in the corpus

• The Surprising Simplicity of the Early-Time Learning Dynamics of Neural Networks (2020, background): “…has also been studied in various settings, suggesting a bias towards large-margin, low-norm, or low-rank solutions [Gunasekar et al., 2017, 2018, Soudry et al., 2018, Li et al., 2018, Ji and Telgarsky, 2019a,b, Arora et al., 2019a, Lyu and Li, 2019, Chizat and Bach, 2020, Razin and Cohen, 2020].”
• Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margin (2019, background): “Soudry et al. [2018], Ji and Telgarsky [2018] show that gradient descent implicitly maximizes the margin for linearly separable data, and Lyu and Li [2019] prove gradient descent converges to a stationary point of the max-margin formulation for deep homogeneous networks.”
• Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss (2020, positive): “Closer to the present paper, Lyu and Li (2019) show that for homogeneous neural networks the training trajectory converges in direction to a critical point of some nonconvex max-margin problem.”
• Adaptive Gradient Methods at the Edge of Stability (2022, background): “[40] proved that rmsprop on homogenous neural networks is, like gradient descent [30], implicitly biased towards maximum margin solutions.”
• Implicit Regularization in Deep Learning May Not Be Explainable by Norms (2020, background): “Works along this line have treated: linear (single-layer) predictors ([67, 31, 40, 2]); normalized linear models ([71]); certain polynomially parameterized linear models ([70]); homogeneous (and sum of homogeneous) models ([53, 49]); ultra-wide neural networks ([38, 51, 14, 58]); linear neural netwo”
• Kernel and Rich Regimes in Overparametrized Models (2019, background): “sagreeswithwhatwouldbeobtainedwithexplicitregularization (regularizing kwk 2is equivalent to kk =D regularization), nor implicitly on with the logistic loss (which againcorrespondstokk 2=D,see,e.g.,[12,18]). AlthoughthetwoextremesdonotchangeaswegobeyondD= 2,whatdoeschangeistheintermediate regime,par”
• A modified Adam algorithm for deep neural network optimization (2023, neutral): “When compared to the SGD algorithm, adaptive gradient methods like Adam typically converge quickly in the early training phases, but they still have poor generalization performance [31, 32].”
• Improved OOD Generalization via Adversarial Training and Pre-training (2021, background): “To satisfy the condition sup (Soudry et al., 2018; Lyu & Li, 2019).”
• AdaBelief Optimizer: Adapting Stepsizes by the Belief in Observed Gradients (2020, methodology): “21 Compared to the SGD family, adaptive methods typically converge fast in the early training phases, 22 but have poor generalization performance [9, 10].”