Fast Convergence in Learning Two-Layer Neural Networks with Separable
  Data
Normalized gradient descent has shown substantial success in speeding up the
convergence of exponentially-tailed loss functions (which includes exponential
and logistic losses) on linear classifiers with separable data. In this paper,
we go beyond linear models by studying normalized GD on two-layer neural nets.
We prove for exponentially-tailed losses that using normalized GD leads to
linear rate of convergence of the training loss to the global optimum if the
iterates find an interpolating model. This is made possible by showing certain
gradient self-boundedness conditions and a log-Lipschitzness property. We also
study generalization of normalized GD for convex objectives via an
algorithmic-stability analysis. In particular, we show that normalized GD does
not overfit during training by establishing finite-time generalization bounds.
Hossein Taheri, Christos Thrampoulidis
# Fast Convergence in Learning Two-Layer Neural Networks

###### Abstract

Normalized gradient descent has shown substantial success in speeding up the convergence of exponentially-tailed loss functions (which includes exponential and logistic losses) on linear classifiers with separable data. In this paper, we go beyond linear models by studying normalized GD on two-layer neural nets. We prove for exponentially-tailed losses that using normalized GD leads to linear rate of convergence of the training loss to the global optimum if the iterates find an interpolating model. This is made possible by showing certain gradient self-boundedness conditions and a log-Lipschitzness property. We also study generalization of normalized GD for convex objectives via an algorithmic-stability analysis. In particular, we show that normalized GD does not overfit during training by establishing finite-time generalization bounds.

## 1 Introduction

### Motivation

A wide variety of machine learning algorithms for classification tasks rely on learning a model using monotonically decreasing loss functions such as logistic loss or exponential loss. In modern practice these tasks are often accomplished using over-parameterized models such as large neural networks where the model can interpolate the training data, i.e., it can achieve perfect classification accuracy on the samples. In particular, it is often the case that the training of the model is continued until achieving approximately zero training loss [14].

Over the last decade there has been remarkable progress in understanding or improving the convergence and generalization properties of over-parameterized models trained by various choices of loss functions including logistic loss and quadratic loss. For the quadratic loss it has been shown that over-parameterization can result in significant improvements in the training convergence rate of (stochastic)gradient descent on empirical risk minimization algorithms. Notably, quadratic loss on two-layer ReLU neural networks is shown to satisfy the Polyak-Lojasiewicz(PL) condition [1, 1, 13, 14]. In fact, the PL property is a consequence of the observation that the tangent kernel associated with the model is a non-singular matrix. Moreover, in this case the PL parameter, which specifies the rate of convergence, is the smallest eigenvalue of the tangent kernel[15]. The fact that over-parameterized neural networks trained by quadratic loss satisfy the PL condition, guarantees that the loss convergences exponentially fast to a global optimum. The global optimum in this case is a model which "perfectly" interpolates the data, where we recall that perfect interpolation requires that the model output for every training input is precisely equal to the corresponding label.

On the other hand, gradient descent using un-regularized logistic regression with linear models and separable data is biased toward the max-margin solution. In particular, in this case the parameter converges in direction with the rate \(O(1/\log(t))\) to the solution of hard margin SVM problem, while the training loss converges to zero at the rate \(\tilde{O}(1/t)\)[15, 16]. More recently, normalized gradient descent has been proposed as a promising approach for fast convergence of exponentially tailed losses. In this method, at any iteration the step-size is chosen proportionally to the inverse of value of training loss function [13]. This results in choosing unboundedly increasing step-sizes for the iterates of gradient descent. This choice of step-size leads to significantly faster rates for the parameter's directional convergence. In particular, for linear models with separable data, it is shown that normalized GD with decaying step-size enjoys a rate of \(O(1/\sqrt{t})\) in directional parameter convergence to the max-margin separator [13]. This has been improved to \(O(1/t)\) with normalized GD using fixed step-size [16].

Despite remarkable progress in understanding the behavior of normalized GD with separable data, these results are only applicable to the implicit bias behavior of "linear models". In this paper, we aim to discover for the first time, the dynamics of learning a two-layer neural network with normalized GD trained on separable data. We also wish to realize the iterate-wise test error performance of this procedure. We show that using normalized GD on an exponentially-tailed loss with a two layered neural network leads to exponentially fast convergence of the loss to the global optimum. This is comparable to the convergence rate of \(O(1/t)\) for the global convergence of neural networks trained with exponentially-tailed losses. Compared to the convergence analysis of standard GD which is usually carried out using smoothness of the
loss function, here for normalized GD we use the Taylor's expansion of the loss and use the fact the operator norm of the Hessian is bounded by the loss. Next, we apply a lemma in our proof which shows that exponentially-tailed losses on a two-layered neural network satisfy a log-Lipschitzness condition throughout the iterates of normalized GD. Moreover, crucial to our analysis is showing that the \(\ell_{2}\) norm of the gradient at every point is upper-bounded and lower-bounded by constant factors of the loss under given assumptions on the activation function and the training data. Subsequently, the log-Lipschitzness property together with the bounds on the norm of Gradient and Hessian of the loss function ensures that normalized GD is indeed a descent algorithm. Moreover, it results in the fact that the loss value decreases by a constant factor after each step of normalized GD, resulting in the promised geometric rate of decay for the loss.

### Contributions

In Section 2.1 we introduce conditions -namely log-Lipschitz and self-boundedness assumptions on the gradient and the Hessian- under which the training loss of the normalized GD algorithm converges exponentially fast to the global optimum. More importantly, in Section 2.2 we prove that the aforementioned conditions are indeed satisfied by two-layer neural networks trained with an exponentially-tailed loss function if the iterates lead to an interpolating solution. This yields the first theoretical guarantee on the convergence of normalized GD for non-linear models. We also study a stochastic variant of normalized GD and investigate its training loss convergence in Section 2.4.

In Section 2.3 we study, for the first time, the finite-time test loss and test error performance of normalized GD for convex objectives. In particular, we provide sufficient conditions for the generalization of normalized GD and derive bounds of order \(O(1/n)\) on the expected generalization error, where \(n\) is the training-set size.

### Prior Works

The theoretical study of the optimization landscape of over-parameterized models trained by GD or SGD has been the subject of several recent works. The majority of these works study over-parameterized models with specific choices of loss functions, mainly quadratic or logistic loss functions. For quadratic loss, the exponential convergence rate of over-parameterized neural networks is proved in several recent works e.g., [1, 1, 2, 3, 1, 1, 1, 2]. These results naturally relate to the Neural Tangent Kernel(NTK) regime of infinitely wide or sufficiently large initialized neural networks [1] in which the iterates of gradient descent stay close to the initialization. The NTK approach can not be applied to our setting as the parameters' norm in our setting is growing as \(\Theta(t)\) with the NGD updates.

The majority of the prior results apply to the quadratic loss. However, the state-of-the-art architectures for classification tasks use unregularized ERM with logistic/exponential loss functions. Notably, for these losses over-parameterization leads to infinite norm optimizers. As a result, the objective in this case does not satisfy strong convexity or the PL condition even for linear models. The analysis of loss and parameter convergence of logistic regression on separable data has attracted significant attention in the last five years. Notably, a line of influential works have shown that gradient descent provably converges in direction to the max-margin solution for linear models and two-layer homogenous neural networks. In particular, the study of training loss and implicit bias behavior of GD on logistic/exponential loss was first initiated in the settings of linear classifiers [1, 1, 2, 1, 1]. The implicit bias behavior of GD with logistic loss in two-layer neural networks was later studied by [1, 2, 1]. The loss landscape of logistic loss for over-parameterized neural networks and structured data is analyzed in [1, 2], where it is proved that GD converges to a global optima at the rate \(O(1/t)\). The majority of these results hold for standard GD while we focus on normalized GD.

The generalization properties of GD/SGD with binary and multi-class logistic regression is studied in [1, 1, 2] for linear models and in [1, 2] for neural networks. Recently, [1] studied the generalization error of decentralized logistic regression through a stability analysis. For our generalization analysis we use an algorithmic stability analysis [1, 1, 2]. However, unlike these prior works we consider normalized GD and derive the first generalization analysis for this algorithm.

The benefits of normalized GD for speeding up the directional convergence of GD for linear models was suggested by [1, 1]. Our paper contributes to this line of work. Compared to the prior works which are focused on implicit behavior of linear models, we study non-linear models and derive training loss convergence rates. We also study, the generalization performance of normalized GD for convex objectives.

### Notation

We use \(\|\cdot\|\) to denote the operator norm of a matrix and also to denote the \(\ell_{2}\)-norm of a vector. The Frobenius norm of a matrix \(W\) is shown by \(\|W\|_{F}\). The Gradient and the Hessian of a function \(F:\mathbb{R}^{d}\rightarrow\mathbb{R}\) are denoted by \(\nabla F\) and \(\nabla^{2}F\). Similarly, for a function \(F:\mathbb{R}^{d}\times\mathbb{R}^{d^{\prime}}\rightarrow\mathbb{R}\) that takes two input variables, the Gradient and the Hessian with respect to the \(i\)th variable (where \(i=1,2\)) are denoted by \(\nabla_{i}F\) and \(\nabla_{i}^{2}F\), respectively. For functions \(F,G:\mathbb{R}\rightarrow\mathbb{R}\), we write \(F(t)=O(G(t))\) when \(|F(t)|\leq m\,G(t)\) after \(t\geq t_{0}\) for positive constants \(m,t_{0}\). We write \(F(t)=\tilde{O}(G(t))\) when \(F(t)=O(G(t)H(t))\) for a polylogarithmic function \(H\). Finally, we denote \(F(t)=\Theta(G(t))\) if \(|F(t)|\leq m_{1}G(t)\) and \(|F(t)|\geq m_{2}G(t)\) for all \(t\geq t_{0}\) for some positive constants \(m_{1},m_{2},t_{0}\).
### Problem Setup

We consider unconstrained and unregularized empirical risk minimization (ERM) on \(n\) samples,

\[\min_{w\in\mathbb{R}^{\bar{d}}}F(w):=\frac{1}{n}\sum_{i=1}^{n}f\left(y_{i}\Phi(w, x_{i})\right). \tag{1}\]

The \(i\)th sample \(z_{i}:=(x_{i},y_{i})\) consists of a data point \(x_{i}\in\mathbb{R}^{d}\) and its associated label \(y_{i}\in\{\pm 1\}\). The function \(\Phi:\mathbb{R}^{\bar{d}}\times\mathbb{R}^{d}\rightarrow\mathbb{R}\) represents the model taking the weights vector \(w\) and data point \(x\) to approximate the label. In this section, we take \(\Phi\) as a neural network with one hidden layer and \(m\) neurons,

\[\Phi(w,x):=\sum_{j=1}^{m}a_{j}\sigma(\langle w_{j},x\rangle).\]

Here \(\sigma:\mathbb{R}\rightarrow\mathbb{R}\) is the activation function and \(w_{j}\in\mathbb{R}^{d}\) denotes the input weight vector of the \(j\)th hidden neuron. \(w\in\mathbb{R}^{\bar{d}}\) represents the concatenation of these weights i.e., \(w=[w_{1};w_{2};\ldots;w_{m}]\). In our setting the total number of parameters and hence the dimension of \(w\) is \(\widetilde{d}=md\). We assume that only the first layer weights \(w_{j}\) are updated during training and the second layer weights \(a_{j}\in\mathbb{R}\) are initialized randomly and are maintained fixed during training. The function \(f:\mathbb{R}\rightarrow\mathbb{R}\) is non-negative and monotonically decreases such that \(\lim_{t\rightarrow+\infty}f(t)=0\). In this section, we focus on the exponential loss \(f(t)=\exp(-t)\), but we expect that our results apply to a broader class of loss functions that behave similarly to the exponential loss for large \(t\), such as logistic loss \(f(t)=\log(1+\exp(-t))\).

We consider activation functions with bounded absolute value for the first and second derivatives.

**Assumption 1** (Activation function).: _The activation function \(\sigma:\mathbb{R}\rightarrow\mathbb{R}\) is smooth and for all \(t\in\mathbb{R}\)_

\[|\sigma^{\prime\prime}(t)|\leq L.\]

_Moreover, there are positive constants \(\alpha,\ell\) such that \(\sigma\) satisfies for all \(t\in\mathbb{R}\),_

\[\alpha\leq\sigma^{\prime}(t)\leq\ell.\]

An example satisfying the above condition is the activation function known as smoothed-leaky-ReLU which is a smoothed variant of the leaky-ReLU activation \(\sigma(t)=\ell t\,\mathbb{I}(t\geq 0)+\alpha t\,\mathbb{I}(t\leq 0)\), where \(\mathbb{I}(\cdot)\) denotes the 0-1 indicator function.

Throughout the paper we let \(R\) and \(a\) denote the maximum norm of data points and second layer weights, respectively, i.e.,

\[R:=\max_{i\in[n]}\ \left\|x_{i}\right\|\,,\ \ \ \ \ a:=\max_{j\in[m]}\ \left|a_{j}\right|\,.\]

Throughout the paper we assume \(R=\Theta(1)\) w.r.t. problem parameters and \(a=\frac{1}{m}\).

We also denote the _training loss_ of the model by \(F\), defined in (1) and define the _train error_ as misclassification error over the training data, or formally by \(F_{0-1}(w):=\frac{1}{n}\sum_{i=1}^{n}\mathbb{I}(\textsc{sign}(\Phi(w,x_{i})) \neq y_{i})\).

Normalized GD.We consider the iterates of normalized GD as follows,

\[w_{t+1}=w_{t}-\eta_{t}\nabla F(w_{t}). \tag{2}\]

The step size is chosen inversely proportional to the loss value i.e., \(\eta_{t}=\eta/F(w_{t})\), implying that the step-size is growing unboundedly as the algorithm approaches the optimum solution. Since the gradient norm decays proportionally to the loss, one can equivalently choose \(\eta_{t}=\eta/\|\nabla F(w_{t})\|\).

## 2 Main Results

For convergence analysis in our case study, we introduce a few definitions.

**Definition 1** (log-Lipschitz Objective).: _The training loss \(F:\mathbb{R}^{\bar{d}}\rightarrow\mathbb{R}\) satisfies the log-Lipschitzness property if for all \(w,w^{\prime}\in\mathbb{R}^{\bar{d}}\),_

\[\max_{v\in[w,w^{\prime}]}F(v)\leq F(w)\cdot\tilde{c}_{w,w^{\prime}},\]

_where \([w,w^{\prime}]\) denotes the line between \(w\) and \(w^{\prime}\) and we define \(\tilde{c}_{w,w^{\prime}}:=\exp\left(c(\|w-w^{\prime}\|+\|w-w^{\prime}\|^{2})\right)\) where the positive constant \(c\) is independent of \(w,w^{\prime}\)._

As we will see in the following sections, log-Lipschitzness is a property of neural networks trained with exponentially tailed losses with \(c=\Theta(\frac{1}{\sqrt{m}})\). We also define the property "log-Lipschitzness in the gradient path" if for all \(w_{t},w_{t-1}\) in Eq. (2) there exists a constant \(C\) such that,

\[\max_{v\in[w_{t},w_{t+1}]}F(v)\leq C\,F(w_{t}).\]

**Definition 2** (Self lower-bounded gradient).: _The loss function \(F:\mathbb{R}^{\bar{d}}\rightarrow\mathbb{R}\) satisfies the self-lower bounded Gradient condition for a function, if these exists a constant \(\mu\) such that for all \(w\),_

\[\|\nabla F(w)\|\geq\mu\,F(w).\]

**Definition 3** (Self-boundedness of the gradient).: _The loss function \(F:\mathbb{R}^{\bar{d}}\rightarrow\mathbb{R}\) satisfies the self-boundedness of the gradient condition for a constant \(h\), if for all \(w\)_

\[\|\nabla F(w)\|\leq h\,F(w).\]

The above two conditions on the upper-bound and lower bound of the gradient norm based on loss can be thought as the equivalent properties of smoothness and the PL condition but for our studied case of exponential loss. To see this, note that smoothness and PL condition provide upper and lower bounds for the square norm of gradient. In particular, by \(L\)-smoothness one can deduce that \(\|\nabla F(w)\|^{2}\leq 2L(F(w)-F^{\star})\) (e.g., [11]) and by the definition of \(\mu\)-PL condition \(\|\nabla F(w)\|^{2}\geq 2\mu(F(w)-F^{\star})\)[12, 12].

The next necessary condition is an upper-bound on the operator norm of the Hessian of loss.

**Definition 4** (Self-boundedness of the Hessian).: _The loss function \(F:\mathbb{R}^{\bar{d}}\rightarrow\mathbb{R}\) satisfies the self-boundedness of the Hessian property for a constant \(H\), if for all \(w\),_

\[\|\nabla^{2}F(w)\|\leq H\,F(w),\]

_where \(\|\cdot\|\) denotes the operator norm._
It is worthwhile to mention here that in the next sections of the paper, we prove all the self lower and upper bound in Definitions 3-4 are satisfied for a two-layer neural network under some regularity conditions.

### Convergence Analysis of Training Loss

The following theorem states that under the conditions above, the training loss converges to zero at an exponentially fast rate.

**Theorem 1** (Convergence of Training Loss).: _Consider normalized gradient descent update rule with loss \(F\) and step-size \(\eta_{t}\). Assume \(F\) and the normalized GD algorithm satisfy log-Lipschitzness in the gradient path with parameter \(C\), as well as self-boundedness of the Gradient and the Hessian and the self-lower bounded Gradient properties with parameters \(h,H\) and \(\mu\), respectively. Let \(\eta_{t}=\frac{\eta}{F(w_{t})}\) for all \(t\in[T]\) and for any positive constant \(\eta\) satisfying \(\eta\leq\frac{\mu^{2}}{HCh^{2}}\). Then for the training loss at iteration \(T\) the following bound holds:_

\[F(w_{\tau})\leq(1-\frac{\eta\mu^{2}}{2})^{T}F(w_{0}). \tag{3}\]

_Remark 1_.: The proof of Theorem 1 is provided in Appendix A, where we use a Taylor expansion of the loss and apply the conditions of the theorem. It is worth noting that the rate obtained for normalized GD in Theorem 1 is significantly faster than the rate of \(\widetilde{O}(\frac{1}{T})\) for standard GD with logistic or exponential loss in neural networks (e.g., (Zou et al. 2020, Thm 4.4), and (Taheri and Thrampoulidis 2023a, Thm 2)). Additionally, for a continuous-time perspective on the training convergence of normalized GD, we refer to Proposition 10 in the appendix, which presents a convergence analysis based on _normalized Gradient Flow_. The advantage of this approach is that it does not require the self-bounded Hessian property and can be used to show exponential convergence of normalized Gradient Flow for leaky-ReLU activation.

### Two-Layer Neural Networks

In this section, we prove that the conditions that led to Theorem 1 are in fact satisfied by a two-layer neural network. Consequently, this implies that the training loss bound in Eq.(3) is valid for this class of functions. We choose \(f(t)=\exp(-t)\) for simpler proofs, however an akin result holds for the broader class of exponentially tailed loss functions.

First, we start with verifying the log-Lipschitzness condition (Definition 1). In particular, here we prove a variation of this property for the iterates of normalized GD i.e., where \(w,w^{\prime}\) are chosen as \(w_{t},w_{t+1}\). The proof is included in Appendix B.1.

**Lemma 2** (log-Lipschitzness in the gradient path).: _Let \(F\) be as in (1) for the exponential loss \(f\) and let \(\Phi\) be a two-layer neural network with the activation function satisfying Assumption 1. Consider the iterates of normalized GD with the step-size \(\eta_{t}=\frac{\eta}{F(w_{t})}\). Then for any \(\lambda\in[0,1]\) the following inequality holds:_

\[F(w_{t}+\lambda(w_{t+1}-w_{t}))\leq\exp(\lambda c)\,F(w_{t}), \tag{4}\]

_for a positive constant \(c\) independent of \(\lambda,w_{t}\) and \(w_{t+1}\). As a direct consequence, it follows that,_

\[\max_{v\in[w_{t},w_{t+1}]}F(v)\leq C\,F(w_{t}), \tag{5}\]

_for a numerical constant \(C\)._

The next two lemmas state sufficient conditions for \(F\) to satisfy the self-lower boundedness for its gradient (Definition 2). The proofs are deferred to Appendices B.2-B.3.

**Lemma 3** (Self lower-boundedness of gradient).: _Let \(F\) be as in (1) for the exponential loss \(f\) and let \(\Phi\) be a two-layer neural network with the activation function satisfying Assumption 1. Assume the training data is linearly separable with margin \(\gamma\). Then \(F\) satisfies the self-lower boundedness of gradient with the constant \(\mu=\frac{\alpha\gamma}{\sqrt{m}}\) for all \(w\), i.e., \(\|\nabla F(w)\|\geq\mu F(w)\)._

Next, we aim to show that the condition \(\|\nabla F(w)\|\geq\mu F(w)\), holds for training data separable by a two-layer neural network during gradient descent updates. In particular, we assume the Leaky-ReLU activation function taking the following form,

\[\sigma(t)=\begin{cases}\ell\,t&t\geq 0,\\ \alpha\,t&t<0.\end{cases} \tag{6}\]

for arbitrary non-negative constants \(\alpha,\ell\). This includes the widely-used ReLU activation as a special case. Next lemma shows that when the weights are such that the neural network separates the training data, the self-lower boundedness condition holds.

**Lemma 4**.: _Let \(F\) be in (1) for the exponential loss \(f\) and let \(\Phi\) be a two-layer neural network with activation function in Eq.(6). Assume the first layer weights \(w\in\mathbb{R}^{\overline{d}}\) are such that the neural network separates the training data with margin \(\gamma\). Then \(F\) satisfies the self- lower boundedness of gradient, i.e, \(\|\nabla F(w)\|\geq\mu F(w),\) where \(\mu=\gamma\)._

A few remarks are in place. The result of Lemma 4 is relevant for \(w\) that can separate the training data. Especially, this implies the self lower-boundedness property after GD iterates succeed in finding an interpolator. However, we should also point out that the non-smoothness of leaky-ReLU activation functions precludes the self-bounded Hessian property and it remains an interesting future direction to prove the self lower-boundedness property with general smooth activations. On the other hand, the convergence of normalized "Gradient-flow" does not require the self-bounded Hessian property, as demonstrated in Proposition 10. This suggests that Lemma 4 can be applied to prove the convergence of normalized Gradient-flow with leaky-ReLU activations. It is worth highlighting that we have not imposed any specific initialization conditions in our analysis as the self-lower bounded property is essentially sufficient to ensure global convergence.

Next lemma derives the self-boundedness of the gradient and Hessian (c.f. Definitions 3-4) for our studied case. The proof of Lemma 5 (in Appendix B.4) follows rather straightforwardly from the closed-form expressions of gradient and Hessian and using properties of the activation function.
**Lemma 5** (Self-boundedness of the gradient and Hessian).: _Let \(F\) be in (1) for the exponential loss \(f\) and let \(\Phi\) be a two-layer neural network with the activation function satisfying Assumption 1. Then \(F\) satisfies the self-boundedness of gradient and Hessian with constants \(h=\frac{\ell R}{\sqrt{m}},H:=\frac{LR^{2}}{m^{2}}+\frac{\ell^{2}R^{2}}{m}\) i.e.,_

\[\|\nabla F(w)\|\leq hF(w),\quad\|\nabla^{2}F(w)\|\leq HF(w).\]

We conclude this section by offering a few remarks regarding our training convergence results. We emphasize that combining Theorem 1 and Lemmas 2-5 achieves the convergence of training loss of normalized Gradient Descent for two-layer networks. Moreover, in Appendix D, we refer to Proposition 10 which presents a continuous time convergence analysis of normalized GD based on Gradient Flow. This result is especially relevant in the context of leaky-ReLU activation, where Proposition 10 together with Lemma 4 shows exponential convergence of normalized Gradient-flow. The experiments of the training performance of normalized GD are deferred to Section 3.

### Generalization Error

In this section, we study the generalization performance of normalized GD algorithm. Formally, the _test loss_ for the data distribution \(\mathcal{D}\) is defined as follows,

\[\widetilde{F}(w):=\mathbb{E}_{(x,y)\sim\mathcal{D}}\Big{[}f(y\Phi(w,x))\Big{]}.\]

Depending on the choice of loss \(f\), the test loss might not always represent correctly the classification performance of a model. For this, a more reliable standard is the _test error_ which is based on the \(0-1\) loss,

\[\widetilde{F}_{0-1}(w):=\mathbb{E}_{(x,y)\sim\mathcal{D}}\Big{[}\mathbb{I}(y \neq\textsc{sign}(\Phi(w,x)))\Big{]}.\]

We also define the _generalization loss_ as the gap between training loss and test loss. Likewise, we define the _generalization error_ based on the train and test errors.

With these definitions in place, we are ready to state our results. In particular, in this section we prove that under the normalized GD update rule, the generalization loss at step \(T\) is bounded by \(O(\frac{T}{n})\) where recall that \(n\) is the training sample size. While, the dependence of generalization loss on \(T\) seems unappealing, we show that this is entirely due to the fact that a convex-relaxation of the \(0-1\) loss, i.e. the loss function \(f\), is used for evaluating the generalization loss. In particular, we can deduce that under appropriate conditions on loss function and data (c.f. Corollary 7.1), the test error is related to the test loss through,

\[\widetilde{F}_{0-1}(w_{{}_{T}})=O(\frac{\widetilde{F}(w_{{}_{T}})}{\|w_{{}_{ T}}\|}).\]

As we will see in the proof of Corollary 7.1, for normalized GD with exponentially tailed losses the weights norm \(\|w_{{}_{T}}\|\) grows linearly with \(T\). Thus, this relation implies that the test error satisfies \(\widetilde{F}_{0-1}(w_{{}_{T}})=O(\frac{1}{n})\). Essentially, this bound on the misclassification error signifies the fast convergence of normalized GD on test error and moreover, it shows that normalized GD never overfits during its iterations.

It is worthwhile to mention that our generalization analysis is valid for any model \(\Phi\) such that \(f(y\Phi(\cdot,x))\) is convex for any \((x,y)\sim\mathcal{D}\). This includes linear models i.e., \(\Phi(w,x)=\langle w,x\rangle\) or the Random Features model (Rahimi and Recht 2007), i.e., \(\Phi(w,x)=\langle w,\sigma(Ax)\rangle\) where \(\sigma(\cdot)\) is applied element-wise on its entries and the matrix \(A\in\mathbb{R}^{m\times d}\) is initialized randomly and kept fixed during train and test time. Our results also apply to neural networks in the NTK regime due to the convex-like behavior of optimization landscape in the infinite-width limit.

We study the generalization performance of normalized GD, through a stability analysis (Bousquet and Elisseeff 2002). The existing analyses in the literature for algorithmic stability of \(\tilde{L}-\)smooth losses, rely on the step-size satisfying \(\eta_{t}=O(1/\tilde{L})\). This implies that such analyses can not be employed for studying increasingly large step-sizes as in our case \(\eta_{t}\) is unboundedly growing. In particular, the common approach in the stability analysis (Hardt, Recht, and Singer 2016; Lei and Ying 2020) uses the "non-expansiveness" property of standard GD with smooth and convex losses, by showing that for \(\eta\leq 2/\tilde{L}\) and for any two points \(w,v\in\mathbb{R}^{d}\), it holds that \(\|w-\eta\nabla F(w)-(v-\eta\nabla F(v))\|\leq\|w-v\|\). Central to our stability analysis is showing that under the assumptions of self-boundedness of Gradient and Hessian, the normalized GD update rule satisfies the non-expansiveness condition with any step-size satisfying both \(\eta\lesssim\frac{1}{F(w)}\) and \(\eta\lesssim\frac{1}{F(v)}\). The proof is included in Appendix C.1.

**Lemma 6** (Non-expansiveness of normalized GD).: _Assume the loss \(F\) to satisfy convexity and self-boundedness for the gradient and the Hessian with parameter \(h\leq 1\) (Definitions 3-4). Let \(v,w\in\mathbb{R}^{d}\). If \(\eta\leq\frac{1}{h\cdot\max(F(v),F(w))}\), then_

\[\|w-\eta\nabla F(w)-(v-\eta\nabla F(v))\|\leq\|w-v\|.\]

The next theorem characterizes the test loss for both Lipschitz and smooth objectives. Before stating the theorem, we need to define \(\delta\). For the leave-one-out parameter \(w_{t}^{-i}\) and loss \(F^{\neg i}(\cdot)\) defined as

\[w_{t+1}^{-i}=w_{t}^{-i}-\eta_{t}\nabla F^{\neg i}(w_{t}^{\neg i}),\]

and

\[F^{\neg i}(w):=\frac{1}{n}\sum_{\begin{subarray}{c}j=1\\ j\neq i\end{subarray}}^{n}f(w,z_{j}),\]

we define \(\delta\geq 1\) to be any constant which satisfies for all \(t\in[T],i\in[n]\), the following

\[F^{\neg i}(w_{t}^{\neg i})\leq\delta\,F^{\neg i}(w_{t}).\]

While this condition seems rather restrictive, we prove in Lemma 9 in Appendix C.3 that the condition on \(\delta\) is satisfied by two-layer neural networks with sufficient over-parameterization. With these definitions in place, we are ready to state the main theorem of this section.

**Theorem 7** (Test loss).: _Consider normalized GD update rule with \(\eta_{t}=\frac{\eta}{F(w_{t})}\) where \(\eta\leq\frac{1}{h\delta}\). Assume the loss \(F\) to be convex and to satisfy the self-bounded gradient and
_Hessian property with a parameter \(h\) (Definitions 3-4). Then the following statements hold for the test loss:_

_(i) if the loss_ \(F\) _is_ \(G\)_-Lipschitz, then the generalization loss at step_ \(T\) _satisfies_

\[\mathbb{E}[\widetilde{F}(w_{{}_{T}})-F(w_{{}_{T}})]\leq\frac{2GT}{n}.\]

_(ii) if the loss_ \(F\) _is_ \(\tilde{L}\)_-smooth, then the test loss at step_ \(T\) _satisfies,_

\[\mathbb{E}[\widetilde{F}(w_{{}_{T}})]\leq 4\mathbb{E}[F(w_{{}_{T}})]+\frac{3 \tilde{L}^{2}T}{n},\]

_where all expectations are over training sets._

The proof of Theorem 7 is deferred to Appendix C.2. As discussed earlier in this section, the test loss dependence on \(T\) is due to the rapid growth of the \(\ell_{2}\) norm of \(w_{t}\). As a corollary, we show that the generalization error is bounded by \(O(\frac{1}{n})\). For this, we assume the next condition.

**Assumption 2** (Margin).: _There exists a constant \(\tilde{\gamma}\) such that after sufficient iterations the model satisfies \(|\Phi(w_{t},x)|\geq\tilde{\gamma}\|w_{t}\|\) almost surely over the data distribution \((x,y)\sim\mathcal{D}\)._

Assumption 2 implies that the absolute value of the margin is \(\tilde{\gamma}\) i.e., \(\frac{|\Phi(w_{t},x)|}{\|w_{t}\|}\geq\tilde{\gamma}\) for almost every \(x\) after sufficient iterations. This assumption is rather mild, as intuitively it requires that data distribution is not concentrating around the decision boundaries.

For the loss function, we consider the special case of logistic loss \(f(t)=\log(1+\exp(-t))\) for simplicity of exposition and more importantly due to its Lipschitz property. The use of Lipschitz property is essential in view of Theorem 7.

**Corollary 7.1** (Test error).: _Suppose the assumptions of Theorem 7 hold. Consider the neural network setup under Assumptions 1 and 2 and let the loss function \(f\) be the logistic loss. Then the test error at step \(T\) of normalized GD satisfies the following:_

\[\mathbb{E}[\widetilde{F}_{0-1}(w_{{}_{T}})]=O(\frac{1}{T}\mathbb{E}[F(w_{{}_{ T}})]+\frac{1}{n})\]

The proof of Corollary 7.1 is provided in Appendix C.4. In the proof, we use that \(\|w_{t}\|\) grows linearly with \(t\) as well as Assumption 2 to deduce \(\widetilde{F}_{0-1}(w_{{}_{T}})=O(\frac{\widetilde{F}(w_{{}_{T}})}{T})\). Hence, the statement of the corollary follows from Theorem 7 (i). We note that while we stated the corollary for the neural net setup, the result is still valid for any model \(\Phi\) that satisfies the Lipschitz property in \(w\). We also note that the above result shows the \(\frac{1}{n}\)-rate for expected test loss which is known to be optimal in the realizable setting we consider throughout the paper.

### Stochastic Normalized GD

In this section we consider a stochastic variant of normalized GD algorithm, Assume \(z_{t}\) to be the batch selected randomly from the dataset at iteration \(t\). The stochastic normalized GD takes the form,

\[w_{t+1}=w_{t}-\eta_{t}\nabla F_{z_{t}}(w_{t}), \tag{7}\]

where \(\nabla F_{z_{t}}(w_{t})\) is the gradient of loss at \(w_{t}\) by using the batch of training points \(z_{t}\) at iteration \(t\). We assume \(\eta_{t}\) to be proportional to \(1/F(w_{t})\). Our result in this section states that under the following strong growth condition (Schmidt and Roux 2013; Vaswani, Bach, and Schmidt 2019), the training loss converges at an exponential rate to the global optimum.

**Assumption 3** (Strong Growth Condition).: _The training loss \(F:\mathbb{R}^{\tilde{d}}\rightarrow\mathbb{R}\) satisfies the strong growth condition with a parameter \(\rho\),_

\[\mathbb{E}_{z}[\|\nabla F_{z}(w)\|^{2}]\leq\rho\|\nabla F(w)\|^{2}.\]

Notably, we show in Appendix E.1 that the strong growth condition holds for our studied case under the self-bounded and self-lower bounded gradient property.

The next theorem characterizes the rate of decay for the training loss. The proof and numerical experiments are deferred to Appendices E.2 and F, respectively.

**Theorem 8** (Convergence of Training Loss).: _Consider stochastic normalized GD update rule in Eq.(7). Assume \(F\) satisfies Assumption 3 as well as the log-Lipschitz in the GD path, self-boundedness of the Gradient and the Hessian and the self-lower bounded Gradient properties (Definitions 1-4). Let \(\eta_{t}=\eta/F(w_{t})\) for all \(t\in[T]\) and for any positive constant \(\eta\) satisfying \(\eta\leq\frac{\mu^{2}}{HCP\tilde{\rho}\tilde{\rho}^{2}}\). Then for the training loss at iteration \(T\) the following bound holds:_

\[F(w_{{}_{T}})\leq(1-\frac{\eta\mu^{2}}{2})^{T}F(w_{0}).\]

## 3 Numerical Experiments

In this section, we demonstrate the empirical performance of normalized GD. It is important to highlight that the advantages of normalized GD over standard GD are most pronounced when dealing with well-separated data, such as in high-dimensional datasets. However, in scenarios where the margin is small, the benefits of normalized GD may be negligible. Figure 1 illustrates the training loss (Left), the test error % (middle), and the weight norm (Right) of GD with normalized GD. The experiments are conducted on a two-layer neural network with \(m=50\) hidden neurons with leaky-ReLU activation function in (6) where \(\alpha=0.2\) and \(\ell=1\). The second layer weights are chosen randomly from \(a_{j}\in\{\pm\frac{1}{m}\}\) and kept fixed during training and test time. The first layer weights are initialized from standard Gaussian distribution and then normalized to unit norm. We consider binary classification with exponential loss using digits "\(0\)" and "\(1\)" from the MNIST dataset (\(d=784\)) and we set the sample size to \(n=1000\). The step-size are fine-tuned to \(\eta=30\) and \(5\) for GD and normalized GD, respectively so that each line represents the best of each algorithm. We highlight the significant speed-up in the convergence of normalized GD compared to standard GD. For the training loss, normalized GD decays exponentially fast to zero while GD converges at a remarkably slower rate. We also highlight that \(\|w_{t}\|\) for
normalized GD grows at a rate \(\Theta(t)\) while it remains almost constant for GD. In fact this was predicted by Corollary 7.1 where in the proof we showed that the weight norm grows linearly with the iteration number. In Figure 2, we generate two synthetic dataset according to a realization of a zero-mean Gaussian-mixture model with \(n-40\) and \(d=2\) where the two classes have different covariance matrices (top) and a zero-mean Gaussian-mixture model with \(n=40,d=5\) (only the first two entires are depicted in the figure) where \(\Sigma_{1}=\mathbf{I}\), \(\Sigma_{2}=\frac{1}{4}\mathbf{I}\) (Bottom). Note that none of the datasets is linearly separable. We consider the same settings as in Figure 1 and compared the performance of GD and normalized GD in the right plots. The step-sizes are fine-tuned to \(\eta=80,350\) and \(30,20\) for GD and normalized GD, respectively. Here again the normalized GD algorithm demonstrates a superior rate in convergence to the final solution.

## 4 Conclusions

We presented the first theoretical evidence for the convergence of normalized gradient methods in non-linear models. While previous results on standard GD for two-layer neural networks trained with logistic/exponential loss proved a rate of \(\widetilde{O}(1/t)\) for the training loss, we showed that normalized GD enjoys an exponential rate. We also studied for the first time, the stability of normalized GD and derived bounds on its generalization performance for convex objectives. We also briefly discussed the stochastic normalized GD algorithm. As future directions, we believe extensions of our results to deep neural networks is interesting. Notably, we expect several of our results to be still true for deep neural networks. Extending the self lower-boundedness property in Lemma 4 for smooth activation functions is another important direction. Another promising avenue for future research is the derivation of generalization bounds for non-convex objectives by extending

Figure 1: Comparison of the training loss, test error (in percentage), and weight norm (i.e., \(\|w_{t}\|\)) between gradient descent and normalized gradient descent algorithms. The experiments were conducted on two classes of the MNIST dataset using exponential loss and a two-layer neural network with \(m=50\) hidden neurons. The results demonstrate the performance advantages of normalized gradient descent over traditional gradient descent in terms of both the training loss and test error.

Figure 2: The left plot depicts two synthetic datasets, each consisting of \(n=40\) data points. On the right, we present the training loss results of gradient descent and normalized gradient descent algorithms applied to a two-layer neural network with \(m=50\) (top) and \(100\) (bottom) hidden neurons.
the approach used for GD (in [11]) to normalized GD.

## Acknowledgements

This work was partially supported by NSF under Grant CCF-2009030.
