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. It has been observed in various machine learning problems recently that the gradient descent (GD) algorithm and the stochastic gradient descent (SGD) algorithm converge to solutions with certain properties even without explicit regularization in the objective function. Correspondingly, theoretical analysis has been developed to explain such implicit regularization property. For example, it has been shown in Gunasekar et al. (2018; 2017) that GD converges to the solution with the minimum norm under certain initialization for regression problems, even without an explicit norm constraint.Another type of implicit regularization, where GD converges to the max-margin classifier, has been recently studied in Gunasekar et al. (2018) ; Ji & Telgarsky (2018) ; Nacson et al. (2018a) ; Soudry et al. (2017; 2018) for classification problems as we describe below. Given a set of training samples z i = (x i , y i ) for i = 1, . . . , n, where x i denotes a feature vector and y i ∈ {−1, +1} denotes the corresponding label, the goal is to find a desirable linear model (i.e., a classifier) by solving the following empirical risk minimization problem It has been shown in Nacson et al. (2018a) ; Soudry et al. (2017; 2018) that if the loss function (·) is monotonically strictly decreasing and satisfies proper tail conditions (e.g., the exponential loss), and the data are linearly separable, then GD converges to the solution w with infinite norm and the maximum margin direction of the data, although there is no explicit regularization towards the maxmargin direction in the objective function. Such a phenomenon is referred to as the implicit bias of GD, and can help to explain some experimental results. For example, even when the training error achieves zero (i.e., the resulting model enters into the linearly separable region that correctly classifies the data), the testing error continues to decrease, because the direction of the model parameter continues to have an improved margin. Such a study has been further generalized to hold for various other types of gradient-based algorithms Gunasekar et al. (2018) . Moreover, Ji & Telgarsky (2018) analyzed the convergence of GD with no assumption on the data separability, and characterized the implicit regularization to be in a subspace-based form.The focus of this paper is on the following two fundamental issues, which have not been well addressed by existing studies.• Existing studies so far focused only on the linear classifier model. An important question one naturally asks is what happens for the more general nonlinear leaky ReLU and ReLU models. Will GD still converge, and if so will it converge to the max-margin direction? Our study here provides new insights for the ReLU model that have not been observed for the linear model in the previous studies.• Existing studies mainly analyzed the convergence of GD with the only exceptions Ji & Telgarsky (2018) ; Nacson et al. (2018b) on SGD. However, Ji & Telgarsky (2018) did not establish the convergence to the max-margin direction for SGD, and Nacson et al. (2018b) established the convergence to the max-margin solution only epochwisely for cyclic SGD (not iterationwise for SGD under random sampling with replacement). Moreover, both studies considered only the linear model. Here, our interest is to explore the iterationwise convergence of SGD under random sampling with replacement to the max-margin direction, and our result can shed insights for online SGD. Furthermore, our study provides new understanding for the nonlinear ReLU and leaky ReLU models. In this paper, we study the problem of learning a ReLU neural network via gradient descent methods, and establish the corresponding risk and parameter convergence under the exponential loss function.In particular, we show that due to the possible existence of spurious asymptotic local minima, GD and SGD can converge either to the global or local max-margin direction, which in the nature of convergence is very different from that under the linear model in the previous studies. We also discuss the extensions of our analysis to the more general leaky ReLU model and multi-neuron networks. In the future, it is worthy to explore the implicit bias of GD and SGD in learning multilayer neural network models and under more general (not necessarily linearly separable) datasets.
We study the implicit bias of gradient methods in solving a binary classification problem with nonlinear ReLU models.
{"src": "scitldr-AIC_train", "paper_id": "Hygv0sC5F7"}