Gradient Descent Maximizes the Margin of Homogeneous Neural Networks

Abstract

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.

arXiv comment52 pages, 9 figures; Published in ICLR 2020; Corrected typos and added a few references

References in corpus (20)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• On Exact Computation with an Infinitely Wide Neural Net
• A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks
• Robust Large Margin Deep Neural Networks
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Characterizing Implicit Bias in Terms of Optimization Geometry
• Path-SGD: Path-Normalized Optimization in Deep Neural Networks
• On the Power of Over-parametrization in Neural Networks with Quadratic Activation
• Recovery Guarantees for One-hidden-layer Neural Networks
• Gradient descent aligns the layers of deep linear networks
• Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel
• Risk and parameter convergence of logistic regression
• Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Rate
• Margins, Shrinkage, and Boosting
• Implicit Regularization of Discrete Gradient Dynamics in Linear Neural Networks
• Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process
• Towards A Deeper Geometric, Analytic and Algorithmic Understanding of Margins
• Theory III: Dynamics and Generalization in Deep Networks

Cited by in corpus (46)

• The Modern Mathematics of Deep Learning
• AdaBelief Optimizer: Adapting Stepsizes by the Belief in Observed Gradients
• Implicit Regularization in Deep Learning May Not Be Explainable by Norms
• Kernel and Rich Regimes in Overparametrized Models
• A Geometric Analysis of Neural Collapse with Unconstrained Features
• Interpolated Adversarial Training: Achieving Robust Neural Networks without Sacrificing Too Much Accuracy
• How to decay your learning rate
• Directional convergence and alignment in deep learning
• Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learning
• Understanding the role of importance weighting for deep learning
• A Unifying View on Implicit Bias in Training Linear Neural Networks
• Directional Pruning of Deep Neural Networks
• An Unconstrained Layer-Peeled Perspective on Neural Collapse
• Improved OOD Generalization via Adversarial Training and Pre-training
• Implicit Bias in Deep Linear Classification: Initialization Scale vs Training Accuracy
• On the Implicit Bias of Initialization Shape: Beyond Infinitesimal Mirror Descent
• When does gradient descent with logistic loss interpolate using deep networks with smoothed ReLU activations?
• Inductive Bias of Multi-Channel Linear Convolutional Networks with Bounded Weight Norm
• Theory III: Dynamics and Generalization in Deep Networks
• A Theoretical Analysis of Fine-tuning with Linear Teachers
• A Bayes-Optimal View on Adversarial Examples
• Reward Tweaking: Maximizing the Total Reward While Planning for Short Horizons
• Continuous vs. Discrete Optimization of Deep Neural Networks
• When does gradient descent with logistic loss find interpolating two-layer networks?
• Gradient descent follows the regularization path for general losses
• An Optimization and Generalization Analysis for Max-Pooling Networks
• What Happens after SGD Reaches Zero Loss? --A Mathematical Framework
• Implicit Bias of SGD for Diagonal Linear Networks: a Provable Benefit of Stochasticity
• The Implicit Bias for Adaptive Optimization Algorithms on Homogeneous Neural Networks
• Bridging the Gap Between Adversarial Robustness and Optimization Bias
• The Convex Geometry of Backpropagation: Neural Network Gradient Flows Converge to Extreme Points of the Dual Convex Program
• Interpolation can hurt robust generalization even when there is no noise
• On Margin Maximization in Linear and ReLU Networks
• Properties of the After Kernel
• Unique Properties of Flat Minima in Deep Networks
• Logit Attenuating Weight Normalization
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• Implicit bias of any algorithm: bounding bias via margin
• Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noise
• Towards Understanding Learning in Neural Networks with Linear Teachers
• Implicitly Maximizing Margins with the Hinge Loss
• Directional Convergence Analysis under Spherically Symmetric Distribution
• Training Efficiency and Robustness in Deep Learning
• Generalization by Recognizing Confusion
• Tighter Sparse Approximation Bounds for ReLU Neural Networks
• A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network