When Will Gradient Methods Converge to Max-margin Classifier under ReLU Models?

Abstract

We study the implicit bias of gradient descent methods in solving a binary classification problem over a linearly separable dataset. The classifier is described by a nonlinear ReLU model and the objective function adopts the exponential loss function. We first characterize the landscape of the loss function and show that there can exist spurious asymptotic local minima besides asymptotic global minima. We then show that gradient descent (GD) can converge to either a global or a local max-margin direction, or may diverge from the desired max-margin direction in a general context. For stochastic gradient descent (SGD), we show that it converges in expectation to either the global or the local max-margin direction if SGD converges. We further explore the implicit bias of these algorithms in learning a multi-neuron network under certain stationary conditions, and show that the learned classifier maximizes the margins of each sample pattern partition under the ReLU activation.

References in corpus (7)

• Characterizing Implicit Bias in Terms of Optimization Geometry
• Risk and parameter convergence of logistic regression
• SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data
• Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Rate
• Margins, Shrinkage, and Boosting
• Convergence of Gradient Descent on Separable Data
• The Implicit Bias of Gradient Descent on Separable Data

Cited by in corpus (8)

• Learning ReLU Networks on Linearly Separable Data: Algorithm, Optimality, and Generalization
• Convergence of Gradient Descent on Separable Data
• Lexicographic and Depth-Sensitive Margins in Homogeneous and Non-Homogeneous Deep Models
• Implicit Regularization in ReLU Networks with the Square Loss
• The Implicit Bias for Adaptive Optimization Algorithms on Homogeneous Neural Networks
• Bilevel Optimization for Machine Learning: Algorithm Design and Convergence Analysis
• Sampling Bias in Deep Active Classification: An Empirical Study
• Trap of Feature Diversity in the Learning of MLPs