Loss landscapes and optimization in over-parameterized non-linear systems and neural networks

Introduction

A singular feature of modern machine learning is a large number of trainable model parameters. Just in the last few years we have seen state-of-the-art models grow from tens or hundreds of millions parameters to much larger systems with hundreds billions or even trillions parameters . Invariably these models are trained by gradient descent based methods, such as Stochastic Gradient Descent (SGD) or Adam . Why are these local gradient methods so effective in optimizing complex highly non-convex systems? In the past few years an emerging understanding of gradient-based methods have started to focus on the insight that optimization dynamics of “modern” over-parameterized models with more parameters than constraints are very different from those of “classical” models when the number of constraints exceeds the number of parameters.

The goal of this paper is to provide a modern view of the optimization landscapes, isolating key mathematical and conceptual elements that are essential for an optimization theory of over-parameterized models.

We start by characterizing a key difference between under-parameterized and over-parameterized landscapes. While both are generally non-convex, the nature of the non-convexity is rather different: under-parameterized landscapes are (generically) locally convex in a sufficiently small neighborhood of a local minimum. Thus classical analyses apply, if only locally, sufficiently close to a minimum. In contrast, over-parameterized systems are “essentially” non-convex systems, not even in arbitrarily small neighbourhoods around global minima.

Thus, we cannot expect the extensive theory of convexity-based analyses to apply to such over-parameterized problems. In contrast, we argue that these systems typically satisfy the Polyak-Łojasiewicz condition, or more precisely, its slightly modified variant – PL∗ condition, on most (but not all) of the parameter space. This condition ensures existence of solutions and convergence of GD and SGD, if it holds in a ball of sufficient radius. Importantly, we show that sufficiently wide neural networks satisfy the PL∗ condition around their initialization point, thus guaranteeing convergence. In addition, we show how the PL∗ condition can be relaxed without significantly changing the analysis. We conjecture that many large systems behave as if the were over-parameterized along the stretch of their optimization path from initialization to the early stopping point.

Mathematically, it is equivalent to solving, exactly or approximately, a system of $n$ equationsThe same setup works for multiple outputs. For examples for multi-class classification problems both the prediction $f({\mathbf{w}};{\mathbf{x}}_{i})$ and labels ${\mathbf{y}}_{i}$ (one-hot vector) are $c$-dimensional vectors, where $c$ is the number of classes. In this case, we are in fact solving $n\times c$ equations. Similarly, for multi-output regression with $c$ outputs, we have $n\times c$ equations. . Aggregating them in a single map (and suppressing the dependence on the training data in the notation) we write:

Here $({\mathcal{F}}({\mathbf{w}}))_{i}:=f({\mathbf{w}};{\mathbf{x}}_{i})$.

The system in Eq.(2) is solved through minimizing a certain loss function ${\mathcal{L}}({\mathbf{w}})$, e.g., the square loss

constructed so that the solutions of Eq.(2) are global minimizers of ${\mathcal{L}}({\mathbf{w}})$. This is a non-linear least squares problem, which is well-studied under classical under-parameterized settings (see , Chapter 10). An exact solution of Eq.(2) corresponds to interpolation, where a predictor fits the data exactly.

As we discuss below, for over-parameterized systems ($m>n$), we expect exact solutions to exist.

Our starting point, discussed in detail in Section 3, is the observation that the loss landscape of an over-parameterized system is generally not convex in any neighborhood of any global minimizer. This is different from the case of under-parameterized systems, where the loss landscape is globally not convex, but still typically locally convex, in a sufficiently small neighbourhood of a (locally unique) minimizer. In contrast, the set of solutions of over-parameterized systems is generically a manifold of positive dimension (and indeed, systems large enough have no non-global minima ). Unless the solution manifold is linear (which is not generally the case) the landscape cannot be locally convex. The contrast between over and under-parametrization illustrated pictorially in Fig 1.

The non-zero curvature of the curve of global minimizers at the bottom of the valley in Fig 1(b) indicates the essential non-convexity of the landscape. In contrast, an under-parameterized landscape generally has multiple isolated local minima with positive definite Hessian of the loss, where the function is locally convex. Thus we conclude that

Convexity is not the right framework for analysis of over-parameterized systems, even locally.

Without assistance from local convexity, what alternative mathematical framework can be used to analyze loss landscapes and optimization behavior of non-linear over-parameterized systems?

We will now outline some key reasons why PL∗ condition provides a general framework for analyzing over-parameterized systems. In particular, we show how it is satisfied by the loss functions of sufficiently wide neural networks, although which are certainly non-convex.

PL∗ condition ⟹\implies existence of solutions and exponential convergence of (S)GD.

The first key point (see Section 5), is that if ${\mathcal{L}}$ satisfies the $\mu$-PL∗ condition in a ball of radius $O(1/\mu)$ then ${\mathcal{L}}$ has a global minimum in that ball (corresponding to a solution of Eq.(2)). Furthermore, (S)GD initialized at the center of such a ballThe constant in $O(1/\mu)$ is different for GD and SGD. converges exponentially to a global minimum of ${\mathcal{L}}$. Thus to establish both existence of solutions to Eq.(2) and efficient optimization, it is sufficient to verify the PL∗ condition in a ball of a certain radius.

Analytic form of PL∗ condition via the spectrum of the tangent kernel.

Let $D{\mathcal{F}}({\mathbf{w}})$ be the differential of the map ${\mathcal{F}}$ at ${\mathbf{w}}$, viewed as a $n\times m$ matrix. The tangent kernel of ${\mathcal{F}}$ is defined as an $n\times n$ matrix

It is clear that $K({\mathbf{w}})$ is a positive semi-definite matrix. It can be seen (Section 4) that square loss ${\mathcal{L}}$ is $\mu$-PL∗ at ${\mathbf{w}}$, where

is the smallest eigenvalue of the kernel matrix. Thus verification of the PL∗ condition reduces to analyzing the spectrum of the tangent kernel matrix associated to ${\mathcal{F}}$.

It is worthwhile to compare this to the standard analytical condition for convexity, requiring that the Hessian of the loss function, $H_{{\mathcal{L}}}$, is positive definite. While these spectral conditions appear to be similar, the similarity is superficial as $K({\mathbf{w}})$ contains first order derivatives, while the Hessian is a second order operator. Hence, as we discuss below, the tangent kernel and the Hessian have very different properties under coordinate transformations and in other settings.

Why PL∗ holds across most of the parameter space for over-parameterized systems.

Note that under-parameterized systems are always rank deficient and have $\lambda_{min}(K({\mathbf{w}}))\equiv 0$. Hence such systems never satisfy PL∗.

Wide neural networks satisfy PL∗ condition.

We show that wide neural networks, as special cases of over-parameterized models, are PL∗, using the technical tools developed in Section 4. This property of the neural networks is a key step to understand the success of the gradient descent based optimization, as seen in Section 5. To show the PL∗ condition for wide neural networks, a powerful, if somewhat crude, tool is provided by the remarkable recent discovery that tangent kernels (so-called NTK) of wide neural networks with linear output layer are nearly constant in a ball ${\mathcal{B}}$ of a certain radius around the ball with a random center. More precisely, it can be shown that the norm of the Hessian tensor $\|{\mathbf{H}}_{\mathcal{F}}({\mathbf{w}})\|=O^{*}(1/\sqrt{m})$, where $m$ is the width of the neural network and ${\mathbf{w}}\in{\mathcal{B}}$ .

Bounding the kernel eigenvalue at the initialization point $\lambda_{min}(K({\mathbf{w}}_{0}))$ from below (using the results from ) completes the analysis.

To prove the result for general neural networks (note that the Hessian norm is typically large for such networks ) we observe that they can be decomposed as a composition of a network with a linear output layer and a coordinate-wise non-linear transformation of the output. The PL∗ condition is preserved under well-behaved non-linear transformations which yields the result.

Relaxing the PL∗ condition: when the systems are almost over-parameterized.

Finally, a framework for understanding large systems cannot be complete without addressing the question of transition between under-parameterized and over-parameterized systems. While neural network models such as those in have billions or trillions on parameters, they are often trained on very large datasets and thus have comparable number of constraints. Thus in the process of optimization they may initially appear over-parameterized, while no truly interpolating solution may exist. Such an optimization landscape is shown in Fig. 3. While an in-depth analysis of this question is beyond the scope of this work, we propose a version of the PL∗ condition that can account for such behavior by postulating that the PL∗ condition is satisfied for values of ${\mathcal{L}}({\mathbf{w}})$ above a certain threshold and that the optimization path from the initialization to the early stopping point lies in the PL∗ domain. Approximate convergence of (S)GD can be shown under this condition, see Section 6.

1 Related work

Loss landscapes of over-parameterized machine learning models, especially deep neural networks, have recently been studied in a number of papers including . The work suggests that the solutions of an over-parameterized system typically are not discrete and form a lower dimensional manifold in the parameter space. In particular show that sufficiently over-parameterized neural networks have no strict local minima under certain mild assumptions. Furthermore in it is proved that, for sufficiently over-parameterized neural networks, each local minimum (if it exists) is “path connected” to a global minimum where the loss value on the path is non-increasing. While the above works mostly focus on the properties of the minima of the loss landscape, in this paper we on the landscape within neighborhoods of these minima, which can often cover the whole optimization path of gradient-based methods.

There has also been a rich literature that particularly focuses on the optimization of wide neural networks using gradient descent , and SGD , especially after the discovery of the constancy of neural tangent kernels (NTK) for certain neural networks . Many of these analyses are based on the observation that the constancy of the tangent kernel implies that the training dynamic of these networks is approximately that of a linear model . This type of analysis can be viewed within our framework of Hessian norm control.

The Polyak-Łojasiewicz (PL) condition has attracted interest in connection with convergence of neural networks and other non-linear systems as it allows to prove some key properties of convexity with respect to the optimization in non-convex settings. For example, the work proved that a composition of strongly convex function with a one-layer leaky ReLU network satisfies the PL condition. The paper proved fast convergence of stochastic gradient descent with constant step size for over-parameterized models, while refined this result showing SGD convergence within a ball with a certain radius. In related work shows that the optimization path length can be upper bounded.

Finally, it is interesting to point out the connections with the contraction theory for differential equations explored in .

Notation and standard definitions

In this paper, we consider the problem of solving a system of equations of the form Eq.(2), i.e. finding ${\mathbf{w}}$, such that ${\mathcal{F}}({\mathbf{w}})={\mathbf{y}}$. This problem is solved by minimizing a loss function ${\mathcal{L}}({\mathcal{F}}({\mathbf{w}}),{\mathbf{y}})$, such as the square loss ${\mathcal{L}}({\mathbf{w}})=\frac{1}{2}\|{\mathcal{F}}({\mathbf{w}})-{\mathbf{y}}\|^{2}$, with gradient-based algorithms. Specifically, the gradient descent method starts from the initialization point ${\mathbf{w}}_{0}$ and updates the parameters as follows:

We call the set $\{{\mathbf{w}}_{t}\}_{t=0}^{\infty}$ the optimization path, and put ${\mathbf{w}}_{\infty}=\lim_{t\to\infty}{\mathbf{w}}_{t}$ (assuming the limit exists).

Throughout this paper, we assume the map ${\mathcal{F}}$ is Lipschitz continuous and smooth. See the definition below:

In supervised learning cases, $({\mathcal{F}}({\mathbf{w}}))_{i}=f({\mathbf{w}};{\mathbf{x}}_{i})$. If we denote $L_{f}$ as the Lipschitz continuity of the machine learning model $f({\mathbf{w}};{\mathbf{x}})$ w.r.t. the parameters ${\mathbf{w}}$, then $\|{\mathcal{F}}({\mathbf{w}})-{\mathcal{F}}({\mathbf{v}})\|^{2}=\sum_{i}(f({\mathbf{w}};{\mathbf{x}}_{i})-f({\mathbf{v}};{\mathbf{x}}_{i}))^{2}\leq nL_{f}^{2}\|{\mathbf{w}}-{\mathbf{v}}\|^{2}.$ One has $L_{\mathcal{F}}\leq\sqrt{n}L_{f}$.

If map ${\mathcal{F}}$ is $L_{\mathcal{F}}$-Lipschitz, then $\|K({\mathbf{w}})\|_{2}\leq L_{\mathcal{F}}^{2}$.

Essential non-convexity of loss landscapes of over-parameterized non-linear systems

In this section we discuss the observation that over-parameterized systems give rise to landscapes that are essentially non-convex – there typically exists no neighborhood around any global minimizer where the loss landscape is convex. This is in contrast to under-parameterized systems where such a neighborhood typically exists, although it can be small.

For over-parameterized system of equations, the number of parameters $m$ is larger than the number of constraints $n$. In this case, the system of equations generically has exact solutions, which form a continuous manifold (or several continuous manifolds), typically of dimension $m-n>0$ so that none of the solutions are isolated. A specific result for wide neural networks, showing non-existence of isolated global minima of the loss function is given in Proposition 6 (Appendix A).

Let ${\mathbf{w}}^{*}$ be a solution to Eq.(2). Since ${\mathbf{w}}^{*}$ is a global minimizer of ${\mathcal{L}}$, $B({\mathbf{w}}^{*})=0$. We note that $A({\mathbf{w}}^{*})$ is a positive semi-definite matrix of rank at most $n$ with at least $m-n$ zero eigenvalues.

Let ${\mathbf{w}}^{*}$ be a solution, ${\mathcal{F}}({\mathbf{w}}^{*})=y$ and suppose that $D{\mathcal{F}}({\mathbf{w}}^{*})$ does not vanish. In the neighborhood of ${\mathbf{w}}^{*}$, there exist arbitrarily close points ${\mathbf{w}}^{*}+\boldsymbol{\delta}$ and ${\mathbf{w}}^{*}-\boldsymbol{\delta}$, such that ${\mathcal{F}}({\mathbf{w}}^{*}+\boldsymbol{\delta})-y>0$ and ${\mathcal{F}}({\mathbf{w}}^{*}-\boldsymbol{\delta})-y<0$. Assuming that the rank of $H_{{\mathcal{F}}_{i}}({\mathbf{w}}^{*})$ is greater than one, and noting that the rank of $D{\mathcal{F}}({\mathbf{w}})^{T}D{\mathcal{F}}({\mathbf{w}})$ is at most one, it is easy to see that either $H_{\mathcal{L}}({\mathbf{w}}^{*}+\boldsymbol{\delta})$ or $H_{\mathcal{L}}({\mathbf{w}}^{*}-\boldsymbol{\delta})$ must have negative eigenvalues, which rules out local convexity at ${\mathbf{w}}^{*}$. A more general version of this argument is given in the following:

Note that in general we do not expect $D{\mathcal{F}}$ to vanish at ${\mathbf{w}}^{*}$ as there is no reason why a solution to Eq.(2) should be a critical point of ${\mathcal{F}}$. For a general loss ${\mathcal{L}}({\mathbf{w}})$, the assumption in Proposition 2 that $D{\mathcal{F}}({\mathbf{w}}^{*})\neq 0$ is replaced by $\left(\frac{d}{d{\mathbf{w}}}\frac{\partial{\mathcal{L}}}{\partial{\mathcal{F}}}\right)({\mathbf{w}}^{*})\neq 0$.

A full proof of Prop. 2 for a general loss function can be found in Appendix B.

For under-parameterized systems, local minima are generally isolated, as illustrated in Figure 1(a). Since $H_{\mathcal{L}}({\mathbf{w}}^{*})$ is generically positive definite when ${\mathbf{w}}^{*}$ is an isolated local minimizer, by the continuity of $H_{\mathcal{L}}(\cdot)$, positive definiteness holds in the neighborhood of ${\mathbf{w}}^{*}$. Therefore, ${\mathcal{L}}({\mathbf{w}})$ is locally convex around ${\mathbf{w}}^{*}$.

Over-parameterized non-linear systems are PL∗ on most of the parameter space

In this section we argue that loss landscapes of over-parameterized systems satisfy the PL∗ condition across most of their parameter space.

We begin with a sufficient analytical condition uniform conditioning of a system closely related to PL∗.

The following important connection shows that uniform conditioning of the system is sufficient for the corresponding square loss landscape to satisfy the PL∗ condition.

We will now provide some intuition for why we expect $\lambda_{min}(K({\mathbf{w}}))$ to be separated from zero over most but not all of the optimization landscape. The key observation is that

Note that kernel $K({\mathbf{w}})$ is an $n\times n$ positive semi-definite matrix by definition. Hence the singular set ${\mathcal{S}}_{sing}$, where the tangent kernel is degenerate, can be written as

If $\lambda_{min}(K({\mathbf{w}}_{0}))=0$ then the system ${\mathcal{F}}({\mathbf{w}})={\mathbf{y}}$ cannot satisfy PL∗ condition for all ${\mathbf{y}}$ on any set ${\mathcal{S}}$ containing ${\mathbf{w}}_{0}$.

Since $\lambda_{min}(K({\mathbf{w}}_{0}))=0$, the matrix $K({\mathbf{w}}_{0})$ has a non-trivial null-space. Therefore we can choose ${\mathbf{y}}$ so that $K({\mathbf{w}}_{0})({\mathcal{F}}({\mathbf{w}}_{0})-{\mathbf{y}})=0$ and ${\mathcal{F}}({\mathbf{w}}_{0})-{\mathbf{y}}\neq 0$. We have

and hence the PL∗ condition cannot be satisfied at ${\mathbf{w}}_{0}$. ∎

Thus we see that only over-parameterized systems can be PL∗, if we want that condition to hold for any label vector ${\mathbf{y}}$.

To see a particularly simple example of this phenomenon, consider the case when $D{\mathcal{F}}({\mathbf{w}})$ is a random matrix with Gaussian entriesIn this the matrix “$D{\mathcal{F}}({\mathbf{w}})$” does not have to correspond to an actual map ${\mathcal{F}}$, rather the intention is to illustrate how over-parameterization leads to better conditioning.. Denote by

the condition number of $K({\mathbf{w}})$. Note that by definition $\kappa\geq 1$. It is shown in that (assuming $m>n$)

We see that as the amount of over-parameterization increases $\kappa$ converges in expectation (and also can be shown with high probability) to a small constant. While this example is rather special, it is representative of the concept that over-parameterization helps with conditioning. In particular, as we discuss below in Section 4.2, wide neural networks satisfy the PL∗ with high probability within a random ball of a constant radius.

We will now provide techniques for proving that the PL∗ condition holds for specific systems and later in Section 4.2 we will show how these techniques apply to wide neural networks, demonstrating that they are PL∗. In Section 5 we discuss the implications of the PL∗ condition for the existence of solutions and convergence of (S)GD, in particular for deep neural networks.

While we expect typical over-parameterized systems to satisfy the PL∗ condition at most points, directly analyzing the smallest eigenvalue of the corresponding kernel matrix is often difficult. Below we describe two methods for demonstrating the PL∗ condition holds in a ball of a certain radius. First method is based on the observation that is well-conditioned in a ball provided it is well-conditioned at its center and the Hessian norm is not large compared to the radius of the ball. Interestingly, this “Hessian control” condition holds for a broad class of non-linear systems. In particular, as discussed in Sec 4.2, wide neural networks with linear output layer have small Hessian norm. For some intuition on why this appears to be a feature of many large systems see Appendix C.

The second approach to demonstrating conditioning is by noticing that it is preserved under well-behaved transformations of the input or output or when composing certain models.

Combining these methods yields a general result on PL∗ condition for wide neural networks in Section 4.2.

We will now show that controlling the norm of the Hessian tensor for the map ${\mathcal{F}}$ leads to well-conditioned systems. The idea of the analysis is that the change of the tangent kernel of ${\mathcal{F}}({\mathbf{w}})$ can be bounded in terms of the norm of the Hessian of ${\mathcal{F}}({\mathbf{w}})$. Intuitively, this is analogous to the mean value theorem, bounding the first derivative of ${\mathcal{F}}$ by its second derivative. If the Hessian norm is sufficiently small, the change of the tangent kernel and hence its conditioning can be controlled in a ball $B({\mathbf{w}}_{0},R)$ with a finite radius, as long as the tangent kernel matrix at the center point $K({\mathbf{w}}_{0})$ is well-conditioned.

First, let’s consider the difference between the tangent kernel matrices at ${\mathbf{w}}\in B({\mathbf{w}}_{0},R)$ and at ${\mathbf{w}}_{0}$.

By the assumption, we have, for all ${\mathbf{v}}\in B({\mathbf{w}}_{0},R)$, $\|{\mathbf{H}}_{\mathcal{F}}({\mathbf{v}})\|<\frac{\lambda_{0}-\mu}{2L_{\mathcal{F}}\sqrt{n}R}$. Hence, for each $i\in[n]$, $\|H_{{\mathcal{F}}_{i}}({\mathbf{w}})\|_{2}<\frac{\lambda_{0}-\mu}{2L_{\mathcal{F}}\sqrt{n}R}$. Now, consider an arbitrary point ${\mathbf{w}}\in B({\mathbf{w}}_{0},R)$. For all $i\in[n]$, we have:

Since $\tau$ is in $$,${\mathbf{w}}_{0}+\tau({\mathbf{w}}-{\mathbf{w}}_{0})$is on the line segment$S({\mathbf{w}}_{0},{\mathbf{w}})$between${\mathbf{w}}_{0}$and${\mathbf{w}}$, which is inside of the ball$B({\mathbf{w}}_{0},R)$. Hence,

In the second inequality above, we used the fact that $\|H_{{\mathcal{F}}_{i}}\|_{2}<\frac{\lambda_{0}-\mu}{2L_{\mathcal{F}}\sqrt{n}R}$ in the ball $B({\mathbf{w}}_{0},R)$. Hence,

Then, the spectral norm of the tangent kernel change is bounded by

In the second inequality above, we used the $L_{\mathcal{F}}$-Lipschitz continuity of ${\mathcal{F}}$ and the fact that $\|A\|_{2}\leq\|A\|_{F}$ for a matrix $A$.

By triangular inequality, we have, at any point ${\mathbf{w}}\in B({\mathbf{w}}_{0},R)$,

Hence, the tangent kernel is $\mu$-uniformly conditioned in the ball $B({\mathbf{w}}_{0},R)$.

By Theorem 1, we immediately have that the square loss ${\mathcal{L}}({\mathbf{w}})$ satisfies $\mu$-PL∗ condition in the ball $B({\mathbf{w}}_{0},R)$. ∎

Below in Section 4.2, we will see that wide neural networks with linear output layer have small Hessian norm (Theorem 2). An illustration for a class of large models is given in Appendix C.

Conditioning of transformed systems.

We now discuss why the conditioning of a system ${\mathcal{F}}({\mathbf{w}})={\mathbf{y}}$ is preserved under a transformations of the domain or range of ${\mathcal{F}}$, as long as the original system is well-conditioned and the transformation has a bounded inverse.

Note that the even if the original system had a small Hessian norm, there is no such guarantee for the transformed system.

where $J_{\Phi}({\mathbf{w}}):=J_{\Phi}({\mathcal{F}}({\mathbf{w}}))$ is the Jacobian of $\Phi$ evaluated at ${\mathcal{F}}(w)$. We will assume that $\rho>0$.

If a system ${\mathcal{F}}$ is $\mu$-uniformly conditioned in a ball $B({\mathbf{w}}_{0},R)$ with $R>0$, then the transformed system $\Phi\circ{\mathcal{F}}({\mathbf{w}})$ is $\mu\rho^{2}$-uniformly conditioned in $B({\mathbf{w}}_{0},R)$. Hence, the square loss function $\frac{1}{2}\|\Phi\circ{\mathcal{F}}({\mathbf{w}})-{\mathbf{y}}\|^{2}$ satisfies $\mu\rho^{2}$-PL∗ condition in $B({\mathbf{w}}_{0},R)$.

Applying Theorem 1, we immediately obtain that $\frac{1}{2}\|\Phi\circ{\mathcal{F}}({\mathbf{w}})-{\mathbf{y}}\|^{2}$ satisfies $\mu\rho^{2}$-PL∗ condition in $B({\mathbf{w}}_{0},R)$. ∎

If ${\mathcal{F}}$ is $\mu$-uniformly conditioned with respect to $\Psi({\mathbf{w}})$ in $B({\mathbf{w}}_{0},R)$, then an analysis similar to Theorem 3 shows that ${\mathcal{F}}\circ\Psi$ is also $\mu\rho^{2}$-uniformly conditioned in $B({\mathbf{w}}_{0},R)$.

Conditioning of composition models.

Let’s denote the tangent kernel matrices of models $g$ and $f$ by $K_{g}({\mathbf{w}}_{g};\mathcal{Z})$ and $K_{f}({\mathbf{w}}_{f};\mathcal{X})$ respectively, where the second arguments, $\mathcal{Z}$ and $\mathcal{X}$, are the datasets that the tangent kernel matrices are evaluated on. Given a dataset $\mathcal{D}=\{({\mathbf{x}}_{i},y_{i})\}_{i=1}^{n}$, denote $f(\mathcal{D})$ as $\{(f({\mathbf{x}}_{i}),y_{i})\}_{i=1}^{n}$.

Consider the composition model $h=g\circ f$ with parameters ${\mathbf{w}}=({\mathbf{w}}_{g},{\mathbf{w}}_{f})$. Given a dataset $\mathcal{D}$, the tangent kernel matrix of $h$ takes the form:

From the above proposition, we see that the tangent kernel of the composition model $h$ can be decomposed into the sum of two positive semi-definite matrices, hence the minimum eigenvalue of $K_{h}$ can be lower bounded by

We note that $g$ takes the outputs of $f$ as inputs which depends on ${\mathbf{w}}_{f}$, while for the model $f$ the inputs are fixed. Hence, if the model $g$ is uniformly conditioned at all the inputs provided by the model $f$, we can expect the uniform conditioning of the composition model $h$.

We provide a simple illustrative example for a “bottleneck” neural network in Appendix D.

2 Wide neural networks satisfy PL∗ condition

In this subsection, we show that wide neural networks satisfy the PL∗ condition, using the techniques we developed in the last subsection.

A $L$-layer (feedforward) neural network $f({\mathbf{W}};{\mathbf{x}})$, with parameters ${\mathbf{W}}$ and input ${\mathbf{x}}$, is defined as follow:

The above definition of neural networks does not include convolutional (CNN) and residual (ResNet) neural networks. In Appendix E, we show that both CNN and ResNet also satisfy the PL∗ condition. Please see the definitions and analysis there.

We study the loss landscape of wide neural networks in regions around randomly chosen points in parameter space. Specifically, we consider the ball $B({\mathbf{W}}_{0},R)$, which has a fixed radius $R>0$ (we will see later, in Section 5, that $R$ can be chosen to cover the whole optimization path) and is around a random parameter point ${\mathbf{W}}_{0}$, i.e., $W_{0}^{(l)}\sim\mathcal{N}(0,I_{m_{l}\times m_{l-1}})$ for $l\in[L+1]$. Note that such a random parameter point ${\mathbf{W}}_{0}$ is a common choice to initialize a neural network. Importantly, the tangent kernel matrix at ${\mathbf{W}}_{0}$ is generally strictly positive definite, i.e., $\lambda_{min}(K({\mathbf{W}}_{0}))>0$. Indeed, this is proven for infinitely wide networks as long as the training data is not degenerate (see Theorem 3.1 of and Proposition F.1 and F.2 of ). As for finite width networks, with high probability w.r.t. the initialization randomness, its tangent kernel $K({\mathbf{W}}_{0})$ is close to that of the infinite network and the minimum eigenvalue $\lambda_{min}(K({\mathbf{W}}_{0}))=O(1)$.

Using the techniques in Section 4.1, the following theorem shows that neural networks with sufficient width satisfies the PL∗ condition in a ball of any fixed radius around ${\mathbf{W}}_{0}$, as long as the tangent kernel $K({\mathbf{W}}_{0})$ is strictly positive definite.

Consider the neural network $f({\mathbf{W}};{\mathbf{x}})$ in Eq.(4.2), and a random parameter setting ${\mathbf{W}}_{0}$ such that $W_{0}^{(l)}\sim\mathcal{N}(0,I_{m_{l}\times m_{l-1}})$ for $l\in[L+1]$. Suppose that the last layer activation $\sigma_{L+1}$ satisfies $|\sigma^{\prime}_{L+1}(z)|\geq\rho>0$ and that $\lambda_{0}:=\lambda_{min}(K({\mathbf{W}}_{0}))>0$. For any $\mu\in(0,\lambda_{0}\rho^{2})$, if the width of the network

then $\mu$-PL∗ condition holds the square loss function in the ball $B({\mathbf{w}}_{0},R)$.

In fact, it is not necessary to require $|\sigma_{L+1}^{\prime}(z)|$ to be greater than $\rho$ for all $z$. The theorem still holds as long as $|\sigma_{L+1}^{\prime}(z)|>\rho$ is true for all $z$ actually achieved by the output neuron before activation.

This theorem tells that while the loss landscape of wide neural networks is nowhere convex (as seen in Section 3), it can still can be described by the PL∗ condition at most points, in line with our general discussion.

We divide the proof into two distinct steps based on representing an arbitrary neural network as a composition of network with a linear output layer and an output non-linearity $\sigma_{L+1}(\cdot)$. In Step 1 we prove the PL∗ condition for the case of a network with a linear output layer (i.e., $\sigma_{L+1}(z)\equiv z$). The argument relies on the fact that wide neural networks with linear output layer have small Hessian norm in a ball around initialization. In Step 2 for general networks we observe that an arbitrary neural network is simply a neural network with a linear output layer from Step 1 with output transformed by applying $\sigma_{L+1}(z)$ coordinate-wise. We obtain the result by combining Theorem 3 with Step 1.

𝐿1𝑧𝑧\sigma_{L+1}(z)\equiv z. In this case, $\rho=1$ and the output layer of the network has a linear form, i.e., a linear combination of the units from the last hidden layer.

As was shown in , for this type of networks with sufficient width, the model Hessian matrix have arbitrarily small spectral norm (a transition to linearity). This is formulated in the following theorem:

Consider a neural network $f({\mathbf{W}};{\mathbf{x}})$ of the form Eq.(4.2). Let $m$ be the minimum of the hidden layer widths, i.e., $m=\min_{l\in[L]}m_{l}$. Given any fixed $R>0$, and any ${\mathbf{W}}\in B({\mathbf{W}}_{0},R):=\{{\mathbf{W}}:\|{\mathbf{W}}-{\mathbf{W}}_{0}\|\leq R\}$, with high probability over the initialization, the Hessian spectral norm satisfies the following:

In Eq.(19), we explicitly write out the dependence of Hessian norm on the radius $R$, according to the proof in .

Directly plugging Eq.(19) into the condition of Theorem 2, letting $\epsilon=\lambda_{0}-\mu$ and noticing that $\rho=1$, we directly have the expression for the width $m$.

Now we apply our analysis for transformed systems in Theorem 3. In this case, the transformation map $\Phi$ becomes a coordinate-wise transformation of the output given by

and the norm of the inverse Jacobian matrix, $\|J_{\Phi}^{-1}({\mathbf{w}})\|_{2}$ is

PL∗ condition in a ball guarantees existence of solutions and fast convergence of (S)GD

In this section, we show that fast convergence of gradient descent methods is guaranteed by the PL∗ condition in a ball with appropriate size. We assume the system ${\mathcal{F}}({\mathbf{w}})$ is $L_{\mathcal{F}}$-Lipschitz continuous and $\beta_{\mathcal{F}}$-smooth on the local region $\mathcal{S}$ that we considered. In what follows $\mathcal{S}$ will typically be a Euclidean ball $B({\mathbf{w}}_{0},R)$, with an appropriate radius $R$, chosen to cover the optimization path of GD or SGD.

First, we define the (non-linear) condition number, as follows:

In the special case of a linear system ${\mathcal{F}}({\mathbf{w}})=A{\mathbf{w}}$ with square loss $\frac{1}{2}\|A{\mathbf{w}}-{\mathbf{y}}\|^{2}$, both the Hessian $H_{\mathcal{L}}=A^{T}A$ and the tangent kernel $K({\mathbf{w}})=A\,A^{T}$ are constant matrices. As $AA^{T}$ and $A^{T}A$ have the same set of non-zero eigenvalues, the largest eigenvalue $\lambda_{max}(H_{\mathcal{L}})$ is equal to $\lambda_{max}(K)$. In this case, the condition number $\kappa_{{\mathcal{F}}}(\mathcal{S})$ reduces to the standard condition number of the tangent kernel $K$,

Since ${\mathcal{F}}$ is $L_{\mathcal{F}}$-Lipschitz continuous and $\beta_{\mathcal{F}}$ smooth by assumption, we directly get the following by substituting the definition of the square loss function into Eq. (23).

For the square loss function ${\mathcal{L}}$, the condition number is upper bounded by:

It is easy to see that the usual condition number $\kappa({\mathbf{w}})=\lambda_{max}(K({\mathbf{w}}))/\lambda_{min}(K({\mathbf{w}}))$ of the tangent kernel $K({\mathbf{w}})$, is upper bounded by $\kappa_{\mathcal{F}}(\mathcal{S})$.

Now, we are ready to present the optimization theory based on the PL∗ condition. First, let the arbitrary set $\mathcal{S}$ to be a Euclidean ball $B({\mathbf{w}}_{0},R)$ around the initialization ${\mathbf{w}}_{0}$ of gradient descent methods, with a reasonably large but finite radius $R$. The following theorem shows that satisfaction of the PL∗ condition on $B({\mathbf{w}}_{0},R)$ implies the existence of at least one global solution of the system in the same ball $B({\mathbf{w}}_{0},R)$. Moreover, following the original argument from , the PL∗ condition also implies fast convergence of gradient descent to a global solution $w^{*}$ in the ball $B({\mathbf{w}}_{0},R)$.

(a) Existence of a solution: There exists a solution (global minimizer of ${\mathcal{L}}$) ${\mathbf{w}}^{*}\in B({\mathbf{w}}_{0},R)$, such that ${\mathcal{F}}({\mathbf{w}}^{*})={\mathbf{y}}$.

(b) Convergence of GD: Gradient descent with a step size $\eta\leq 1/(L_{\mathcal{F}}^{2}+\beta_{\mathcal{F}}\|{\mathcal{F}}({\mathbf{w}}_{0})-{\mathbf{y}}\|)$ converges to a global solution in $B({\mathbf{w}}_{0},R)$, with an exponential (a.k.a. linear) convergence rate:

where the condition number $\kappa_{{\mathcal{F}}}(B({\mathbf{w}}_{0},R))=\frac{1}{\eta\mu}$.

The proof of the theorem is deferred to Appendix F.

It is interesting to note that the radius $R$ of the ball $B({\mathbf{w}}_{0},R)$ takes a finite value, which means that the optimization path $\{{\mathbf{w}}_{t}\}_{t=0}^{\infty}\subset B({\mathbf{w}}_{0},R)$ stretches at most a finite length and the optimization happens only at a finitely local region around the initialization. Hence, the conditioning of the tangent kernel and the satisfaction of the PL∗ condition outside of this ball are irrelevant to this optimization and are not required.

Indeed, this radius $R$ has to be of order $\Omega(1)$. From the $L_{\mathcal{F}}$-Lipschitz continuity of ${\mathcal{F}}({\mathbf{w}})$, it follows that there is no solution within the distance $\|{\mathcal{F}}({\mathbf{w}}_{0})-{\mathbf{y}}\|/L_{\mathcal{F}}$ from the initialization point. Any solution must have a Euclidean distance away from ${\mathbf{w}}_{0}$ at least $R_{min}=\|{\mathcal{F}}({\mathbf{w}}_{0})-{\mathbf{y}}\|/L_{\mathcal{F}}$, which is finite. This means that the parameter update $\Delta{\mathbf{w}}={\mathbf{w}}^{*}-{\mathbf{w}}_{0}$ must not be too small in terms of Euclidean distance. However, due to the large population $m$ of the model parameters, each individual parameter $w_{i}$ may take a small change during the gradient descent training, i.e., $|w_{i}-w_{0,i}|=O(1/\sqrt{m})$. Indeed, this is what happening for wide neural networks .

Below, we make an extension of the above theory: from (deterministic) gradient descent to stochastic gradient descent (SGD).

In most practical machine learning settings, including typical problems of supervised learning, the loss function ${\mathcal{L}}({\mathbf{w}})$ has the form

We will assume that each element of the set $S$ is chosen uniformly at random at every iteration.

We now show that the PL∗ condition on ${\mathcal{L}}$ also implies exponential convergence of SGD within a ball, an SGD analogue of Theorem 6. Our result can be considered as a local version of Theorem 1 in which showed exponential convergence of SGD, assuming PL condition holds in the entire parameter space. See also for a related result.

1 Convergence for wide neural networks.

Using the optimization theory developed above, we can now show convergence of (S)GD for sufficiently wide neural networks. As we have seen in Section 4.2, the loss landscapes of wide neural networks $f({\mathbf{W}};{\mathbf{x}})$ defined in Eq.(4.2) are $\mu$-PL∗ condition in a ball $B({\mathbf{W}}_{0},R)$ of an arbitrary radius $R$. We will now show convergence of GD for these models.

We further assume $\sigma_{L+1}(\cdot)$ is $L_{\sigma}$-Lipschitz continuous and $\beta_{\sigma}$-smooth.

The result is obtained by combining Theorem 4 and 6, after setting the ball radius $R=2L_{\mathcal{F}}\|{\mathcal{F}}({\mathbf{W}}_{0})-{\mathbf{y}}\|/\mu$ and choosing the step size $0<\eta<\frac{1}{L_{\mathcal{F}}^{2}+\beta_{\mathcal{F}}\|{\mathcal{F}}({\mathbf{W}}_{0})-{\mathbf{y}}\|}$.

It remains to verify that all of the quantities $L_{\mathcal{F}}$, $\beta_{\mathcal{F}}$ and $\|{\mathcal{F}}({\mathbf{W}}_{0})-{\mathbf{y}}\|$ are of order $O(1)$ with respect to the network width $m$. First note that, with the random initialization of ${\mathbf{W}}_{0}$ as in Theorem 4, it is shown in that with high probability, $f({\mathbf{W}}_{0};{\mathbf{x}})=O(1)$ when the width is sufficiently large under mild assumption on the non-linearity functions $\sigma_{l}(\cdot)$, $l=1,...,L+1$. Hence $\|{\mathcal{F}}({\mathbf{W}}_{0})-{\mathbf{y}}\|=O(1)$.

Using the definition of $L_{\mathcal{F}}$, we have

Finally, $\beta_{\mathcal{F}}$ is bounded as follows:

Using the same argument, a result similar to Theorem 8 but with a different convergence rate,

and with difference constants, can be obtained for SGD by applying Theorem 7.

Note that (near) constancy of the tangent kernel is not a necessary condition for exponential convergence of gradient descent or (S)GD.

In certain situations, for example mildly under-parameterized cases, the PL∗ condition may not hold exactly, since an exact solution for system ${\mathcal{F}}({\mathbf{w}})={\mathbf{w}}$ may not exist. Fortunately, in practice, we do not need to run algorithms until exact convergence. Most of the time, early stopping is employed, i.e. we stop the algorithm once it achieves a certain small loss $\epsilon>0$. To account for that case, we define PL${}^{*}_{\epsilon}$ condition, a relaxed variant of PL∗ condition, which still implies a fast convergence of the gradient-based algorithms up to loss $\epsilon$.

Intuitively, the PL${}^{*}_{\epsilon}$ condition is the same as PL∗ condition, except that the loss landscape can be arbitrary wherever the loss is less than $\epsilon$. This is illustrated in Figure 5.

Below, following a similar argument above, we show that a local PL${}^{*}_{\epsilon}$ condition guarantees fast convergence to an approximation of a global minimizer. Basically, the gradient descent terminates when the loss is less than $\epsilon$.

(a) Existence of a point which makes the loss less than $\epsilon$: There exists a point ${\mathbf{w}}^{*}\in B({\mathbf{w}}_{0},R)$, such that ${\mathcal{L}}({\mathbf{w}}^{*})<\epsilon$.

(b) Convergence of GD : Gradient descent with the step size $\eta=1/\sup_{{\mathbf{w}}\in B({\mathbf{w}}_{0},R)}\|H_{\mathcal{L}}({\mathbf{w}})\|_{2}$ after $T=\Omega(\log(1/\epsilon))$ iterations satisfies ${\mathcal{L}}({\mathbf{w}}_{T})<\epsilon$ in the ball $B({\mathbf{w}}_{0},R)$, with an exponential (also known as linear) convergence rate:

where the condition number $\kappa_{{\mathcal{L}},F}(B({\mathbf{w}}_{0},R))=\frac{1}{\eta\mu}$.

If ${\mathcal{L}}({\mathbf{w}}_{0})<\epsilon$, we let ${\mathbf{w}}^{*}={\mathbf{w}}_{0}$ and we are done.

Suppose ${\mathcal{L}}({\mathbf{w}}_{0})\geq\epsilon$. Following the similar analysis to the proof of Theorem 6, as long as ${\mathcal{L}}({\mathbf{w}}_{t})\geq\epsilon$ for $t\geq 0$, we have

Hence there must exist a minimum $T>0$ such that

It’s not hard to see that $\epsilon\leq(1-\eta\mu)^{T}{\mathcal{L}}({\mathbf{w}}_{0})$, from which we get $T=\Omega(\log(1/\epsilon)).$

And obviously, ${\mathbf{w}}_{0},{\mathbf{w}}_{1},...,{\mathbf{w}}_{T}$ are also in the ball $B({\mathbf{w}}_{0},R)$ with $R=\frac{2\sqrt{2\beta{\mathcal{L}}({\mathbf{w}}_{0})}}{\mu}$. ∎

Following similar analysis, when PL${}^{*}_{\epsilon}$ condition holds in the ball, SGD converges exponentially to an approximation of the global solution.

If ${\mathcal{L}}({\mathbf{w}}_{0})<\epsilon$, we let $T=0$ and we are done.

Suppose ${\mathcal{L}}({\mathbf{w}}_{0})\geq\epsilon$. By the similar analysis in the proof of Theorem 7, with the $\mu$-PL${}^{*}_{\epsilon}$ condition, for any mini-batch size $s$, the mini-batch SGD with step size $\eta^{*}(s):=\frac{n\mu}{n\lambda(n^{2}\lambda+\mu(s-1))}$ has an exponential convergence rate:

for all $t$ where ${\mathcal{L}}({\mathbf{w}}_{t})\geq\epsilon$.

And it’s easy to check that with probability $1-\delta$, the optimization path ${\mathbf{w}}_{0},{\mathbf{w}}_{1},...,{\mathbf{w}}_{T}$ is covered by the ball $B({\mathbf{w}}_{0},R)$ with $R=\frac{2n\sqrt{2\gamma}\sqrt{{\mathcal{L}}({\mathbf{w}}_{0})}}{\mu\delta}$. ∎

While the global landscape of the loss function ${\mathcal{L}}({\mathbf{w}})$ can be complex, the conditions above allow us to find solutions within a certain ball around the initialization point ${\mathbf{w}}_{0}$.

Concluding thoughts and comments

In this paper we have proposed a general framework for understanding generically non-convex landscapes and optimization of over-parameterized systems in terms of the PL∗ condition. We have argued that PL* condition generally holds on most but not all of the parameter space, which is sufficient for the existence of solutions and convergence of gradient-base methods to global minimizers. In contrast, it is not possible for loss landscapes of under-parameterized systems $\|{\mathcal{F}}({\mathbf{w}})-{\mathbf{y}}\|^{2}$ to satisfy PL∗ for any ${\mathbf{y}}$. We conclude with a number of comments and observations.

A remarkable property of over-parameterized non-linear systems discussed in this work is their strong resemblance to linear systems with respect to optimization by (S)GD, even as their dynamics remain nonlinear. In particular, optimization by gradient-based methods and proximity to global minimizers is controlled by non-linear condition numbers, similarly to classical analyses of linear systems. The key difference is that while for linear systems the condition number is constant, in the non-linear case we need a uniform bound in a domain containing the optimization path. In contrast, the optimization properties of non-linear systems in the under-parameterized regime appear very different from those of linear systems. Furthermore, increasing the degree of over-parameterization generally improves conditioning just like it does for linear systems (cf. and the discussion in ). In particular, this suggests that the effectiveness of optimization should improve, up to a certain limit, with increased over-parameterization.

Transition over the interpolation threshold.

Recognizing the power of over-parameterization has been a key insight stemming from the practice of deep learning. Transition to over-parameterized models – over the interpolation threshold – leads to a qualitative change in a range of system properties. Statistically, over-parameterized systems enter a new interpolating regime, where increasing the number of parameters, even indefinitely to infinity, can improve generalization . From the optimization point of view, over-parameterized system are generally easier to solve. There has been significant effort (continued in this work) toward understanding effectiveness of local methods in this setting .

In this paper we note another aspect of this transition, to the best of our knowledge not addressed in the existing literature – transition from local convexity to essential non-convexity. This relatively simple observation has significant consequences, indicating the need to depart from the machinery of convex analysis. Interestingly, our analyses suggest that this loss of local convexity is of little consequence for optimization, at least as far as gradient-based methods are concerned.

Transition from over-parameterization to under-parameterization along the optimization path.

As discussed above, transition over the interpolation threshold occurs when the number of parameters in a variably parameterized system exceeds the number of constraints (corresponding to data points in typical ML scenarios). Over-parameterization does not refer to the number of parameters as such but to the difference between the number of parameters and the number of constraints. While some learning models are very large, with billions or even trillions parameters, they are often trained on equally large datasets and are thus not necessarily over-parameterized. Yet, it is still tempting to view these models through the lens of over-parameterization. While precise technical analysis is beyond the scope of this paper, we conjecture that transition between effective over-parameterization to under-parameterization happens along the optimization trajectory. Initially, the system behaves as over-parameterized but as the optimization process continues, it fails to reach zero. Mathematically it can be represented as our PL${}^{*}_{\epsilon}$ condition. We speculate that for many realistic large models trained on big data the full optimization path lies within the PL${}^{*}_{\epsilon}$ domain and hence, functionally, the analyses in this paper apply.

Condition numbers and optimization methods.

In this work we concentrate on optimization by gradient descent and SGD. Yet, for linear systems of equations and in many other settings, the importance of conditioning extends far beyond one specific optimization technique . We expect this to be case in the over-parameterized non-linear setting as well. To give just one example, we expect that accelerated methods, such as the Nesterov’s method and its stochastic gradient extensions in the over-parameterized case to have faster convergence rates for non-linear systems in terms of the condition numbers defined in this work.

Equations on manifolds.

In this paper we consider systems of equations ${\mathcal{F}}({\mathbf{w}})={\mathbf{y}}$ defined on Euclidean spaces and with Euclidean output. A more general setting is to look for solutions of arbitrary systems of equations defined by a map between two Riemannian manifolds ${\mathcal{F}}:{\cal M}\to\cal{N}$. In that case the loss function ${\mathcal{L}}$ needs to be defined on $\cal{N}$. The over-parameterization corresponds to the case when dimension $\dim({\cal M})>\dim({\cal N})$. While analyzing gradient descent requires some care on a manifold, most of the mathematical machinery, including the definitions of the PL∗ condition and the condition number associated to ${\mathcal{F}}$, is still applicable without significant change. In particular, as we discussed above (see Remark 4 in Section 4.1), the condition number is preserved under “well-behaved” coordinate transformations. In contrast, this is not the case for the Hessian and thus manifold optimization analyses based on geodesic convexity require knowledge about specific coordinate charts, such as those given by the exponential map.

We note that manifold and structural assumptions on the weight vector ${\mathbf{w}}$ is a natural setting for addressing many problems in inference. In particular, the important class of convolutional neural networks is an example of such a structural assumption on ${\mathbf{w}}$, which is made invariant to certain parallel transforms. Furthermore, there are many settings, e.g., robot motion planning, where the output of a predictor, ${\mathbf{y}}$, also belongs to a certain manifold.

Acknowledgements

We thank Raef Bassily and Siyuan Ma for many earlier discussions about gradient methods and Polyak-Łojasiewicz conditions and Stephen Wright for insightful comments and corrections. The authors acknowledge support from the NSF, the Simons Foundation and a Google Faculty Research Award.

References

Appendix A Wide neural networks have no isolated local/global minima

In this section, we show that, for feedforward neural networks, if the network width is sufficiently large, there is no isolated local/global minima in the loss landscape.

Consider the following feedforward neural networks:

Consider the feedforward neural network in Eq.(36). If the network width $m\geq 2c(n+1)^{L}$, given a local (global) minimum ${\mathbf{W}}^{*}$ of the loss function Eq.(37), there are always other local (global) minima in any neighborhood of ${\mathbf{W}}^{*}$.

The main idea of this proposition is based on some of the intermediate-level results of the work . Before starting the proof, let’s review some of the important concepts and results therein. To be consistent with the notation in this paper, we modify some of their notations.

Consider two parameters ${\mathbf{W}},{\mathbf{V}}\in\mathcal{M}$. If there is a continuous function $h_{{\mathbf{W}},{\mathbf{V}}}:\to\mathcal{M}$ that satisfies $h_{{\mathbf{W}},{\mathbf{V}}}(0)={\mathbf{W}}$, $h_{{\mathbf{W}},{\mathbf{V}}}(1)={\mathbf{V}}$ and $t\mapsto\mathcal{L}(h_{{\mathbf{W}},{\mathbf{V}}}(t))$ is constant, we say that ${\mathbf{W}}$ and ${\mathbf{V}}$ are path constant and write ${\mathbf{W}}\leftrightarrow{\mathbf{V}}$.

Path constantness means the two parameters ${\mathbf{W}}$ and ${\mathbf{V}}$ are connected by a continuous path of parameters that is contained in a level set of the loss function $\mathcal{L}$.

${\mathbf{W}}\leftrightarrow{\mathbf{V}}$ and ${\mathbf{V}}\leftrightarrow{\mathbf{U}}$ $\Rightarrow$ ${\mathbf{W}}\leftrightarrow{\mathbf{U}}$.

Consider a number $s\in\{0,1,\cdots\}$ and a parameter ${\mathbf{W}}\in\mathcal{M}$. If

we call ${\mathbf{W}}$ an $s$-upper-block parameter of depth $L$.

we call ${\mathbf{W}}$ an $s$-lower-block parameter of depth $L$. We denote the sets of the $s$-upper-block and $s$-lower-block parameters of depth $L$ by $\mathcal{U}_{s,L}$ and $\mathcal{V}_{s,L}$, respectively.

The key result that we use in this paper is that every parameter is path constant to a block parameter, or more formally:

For every parameter ${\mathbf{W}}\in\mathcal{M}$ and $s:=c(n+1)^{L}$ ($n$ is the number of training samples), there are $\overline{{\mathbf{W}}},\underline{{\mathbf{W}}}\in\mathcal{M}$ with $\overline{{\mathbf{W}}}\in\mathcal{U}_{s,L}$ and $\underline{{\mathbf{W}}}\in\mathcal{V}_{s,L}$ such that ${\mathbf{W}}\leftrightarrow\overline{{\mathbf{W}}}$ and ${\mathbf{W}}\leftrightarrow\underline{{\mathbf{W}}}$.

The above proposition says that, if the network width $m$ is large enough, every parameter is path connected to both an upper-block parameter and a lower-block parameter, by continuous paths contained in a level set of the loss function.

Now, let’s present the proof of Proposition 6.

Let ${\mathbf{W}}^{*}\in\mathcal{M}$ be an arbitrary local/global minimum of the loss function $\mathcal{L}({\mathbf{W}})$. According to Proposition 7, there exist an upper-block parameter $\overline{{\mathbf{W}}}\in\mathcal{U}_{s,L}\subset\mathcal{M}$ and $\underline{{\mathbf{W}}}\in\mathcal{V}_{s,L}\subset\mathcal{M}$ such that ${\mathbf{W}}\leftrightarrow\overline{{\mathbf{W}}}$ and ${\mathbf{W}}\leftrightarrow\underline{{\mathbf{W}}}$. Note that $\overline{{\mathbf{W}}}$ and $\underline{{\mathbf{W}}}$ are distinct, because $\mathcal{U}_{s,L}$ and $\mathcal{V}_{s,L}$ do not intersect except at zero due to $m\geq 2s$. This means there must be parameters distinct from ${\mathbf{W}}^{*}$ that is connected to ${\mathbf{W}}^{*}$ via a continuous path contained in a level set of the loss function. Note that all the points (i.e., parameters) along this path have the same loss value as $\mathcal{L}({\mathbf{W}}^{*})$, hence are local/global minima. Therefore, ${\mathbf{W}}^{*}$ is not isolated (i.e, there are other local/global minima in any neighborhood of ${\mathbf{W}}^{*}$). ∎

Appendix B Proof of Proposition 2

The Hessian matrix of a general loss function ${\mathcal{L}}({\mathcal{F}}({\mathbf{w}}))$ takes the form

Recall that $H_{{\mathcal{F}}_{i}}({\mathbf{w}})$ is the Hessian matrix of $i$-th output of ${\mathcal{F}}$ with respect to ${\mathbf{w}}$.

We consider the Hessian matrices of ${\mathcal{L}}$ around a global minimizer ${\mathbf{w}}^{*}$ of the loss function, i.e., solution of the system of equations. Specifically, consider the following two points ${\mathbf{w}}^{*}+\boldsymbol{\delta}$ and ${\mathbf{w}}^{*}-\boldsymbol{\delta}$, which are in a sufficiently small neighborhood of the minimizer ${\mathbf{w}}^{*}$. Then Hessian of loss at these two points are

Note that both the terms $A({\mathbf{w}}^{*}+\boldsymbol{\delta})$ and $A({\mathbf{w}}^{*}-\boldsymbol{\delta})$ are matrices with rank at most $n$, since $D{\mathcal{F}}$ is of the size $n\times m$.

By the assumption, at least one component $H_{{\mathcal{F}}_{k}}$ of the Hessian of ${\mathcal{F}}$ satisfies that the rank of $H_{{\mathcal{F}}_{k}}({\mathbf{w}}^{*})$ is greater than $2n$. By the continuity of the Hessian, we have that, if magnitude of $\boldsymbol{\delta}$ is sufficiently small, then the ranks of $H_{{\mathcal{F}}_{k}}({\mathbf{w}}^{*}+\boldsymbol{\delta})$ and $H_{{\mathcal{F}}_{k}}({\mathbf{w}}^{*}-\boldsymbol{\delta})$ are also greater than $2n$.

Consequently the vector $\langle{\mathbf{v}}^{T}H_{{\mathcal{F}}_{1}}({\mathbf{w}}^{*}+\boldsymbol{\delta}){\mathbf{v}},\ldots,{\mathbf{v}}^{T}H_{{\mathcal{F}}_{n}}({\mathbf{w}}^{*}+\boldsymbol{\delta}){\mathbf{v}}\rangle\neq\mathbf{0}$ and $\langle{\mathbf{v}}^{T}H_{{\mathcal{F}}_{1}}({\mathbf{w}}^{*}-\boldsymbol{\delta}){\mathbf{v}},\ldots,{\mathbf{v}}^{T}H_{{\mathcal{F}}_{n}}({\mathbf{w}}^{*}-\boldsymbol{\delta}){\mathbf{v}}\rangle\neq\mathbf{0}$.

In the following, we show that, for sufficiently small $\boldsymbol{\delta}$, ${\mathbf{v}}^{T}H_{\mathcal{L}}({\mathbf{w}}^{*}+\boldsymbol{\delta}){\mathbf{v}}$ and ${\mathbf{v}}^{T}H_{\mathcal{L}}({\mathbf{w}}^{*}-\boldsymbol{\delta}){\mathbf{v}}$ can not be non-negative simultaneously, which immediately implies that $H_{\mathcal{L}}$ is not positive semi-definite in the close neighborhood of ${\mathbf{w}}^{*}$, hence ${\mathcal{L}}$ is not locally convex at ${\mathbf{w}}^{*}$.

Specifically, with the condition $\frac{d}{d{\mathbf{w}}}\left(\frac{\partial{\mathcal{L}}}{\partial{\mathcal{F}}}({\mathbf{w}}^{*})\right)\neq\mathbf{0}$, for Eq.(40) and Eq.(41) we have the following cases: Case 1 : If $\sum_{i=1}^{n}\left(\frac{d}{d{\mathbf{w}}}\left(\frac{\partial{\mathcal{L}}}{\partial{\mathcal{F}}}({\mathbf{w}}^{*})\right)\boldsymbol{\delta}\right)_{i}{\mathbf{v}}^{T}H_{{\mathcal{F}}_{i}}({\mathbf{w}}^{*}+\boldsymbol{\delta}){\mathbf{v}}<0$, then directly ${\mathbf{v}}^{T}H_{\mathcal{L}}({\mathbf{w}}^{*}+\boldsymbol{\delta}){\mathbf{v}}<0$ if $\boldsymbol{\delta}$ is small enough which completes the proof. Case 2 : Otherwise if $\sum_{i=1}^{n}\left(\frac{d}{d{\mathbf{w}}}\left(\frac{\partial{\mathcal{L}}}{\partial{\mathcal{F}}}({\mathbf{w}}^{*})\right)\boldsymbol{\delta}\right)_{i}{\mathbf{v}}^{T}H_{{\mathcal{F}}_{i}}({\mathbf{w}}^{*}+\boldsymbol{\delta}){\mathbf{v}}>0$, by the continuity of each $H_{{\mathcal{F}}_{i}}(\cdot)$, we have

when $\boldsymbol{\delta}$ is small enough.

If $\sum_{i=1}^{n}\left(\frac{d}{d{\mathbf{w}}}\left(\frac{d{\mathcal{L}}}{d{\mathcal{F}}}({\mathbf{w}}^{*})\right)\boldsymbol{\delta}\right)_{i}{\mathbf{v}}^{T}H_{{\mathcal{F}}_{i}}({\mathbf{w}}^{*}+\boldsymbol{\delta}){\mathbf{v}}=0$, we can always adjust $\boldsymbol{\delta}$ a little so that it turns to case 1 or 2.

In conclusion, with certain $\boldsymbol{\delta}$ which is arbitrarily small, either ${\mathbf{v}}^{T}H_{\mathcal{L}}({\mathbf{w}}^{*}+\boldsymbol{\delta}){\mathbf{v}}$ or ${\mathbf{v}}^{T}H_{\mathcal{L}}({\mathbf{w}}^{*}-\boldsymbol{\delta}){\mathbf{v}}$ has to be negative which means ${\mathcal{L}}({\mathbf{w}})$ has no convex neighborhood around ${\mathbf{w}}^{*}$. ∎

Appendix C Small Hessian is a feature of certain large models

Here, we show that the small Hessian spectral norm is not an strong condition. In fact, it is a mathematical freebie as long as the model has certain structure and is large enough. For example, if a neural network has a linear output layer and is wide enough, its Hessian spectral norm can be arbitrarily small, see .

In the following, let’s consider an illustrative example. Let the model $f$ be a linear combination of $m$ independent sub-models,

For simplicity, we assume that the sub-models $\alpha_{i}({\mathbf{w}}_{i},{\mathbf{x}})$ have the same structure but different initial parameters ${\mathbf{w}}_{i,0}$ due to random initialization. We further assume each sub-model has a $\Theta(1)$ output, and is second-order differentiable and $\beta$-smooth.

Due to the randomness of the sub-model weights $v_{i}$, the scaling factor $\frac{1}{s(m)}=o(1)$ w.r.t. the size $m$ of the model $f$ (e.g, $\frac{1}{s(m)}=\frac{1}{\sqrt{m}}$ for neural networks ).

The following theorem states that, as long as the model size $m$ is sufficiently large, the Hessian spectral norm of the model $f$ is arbitrarily small.

Consider the model $f$ defined in Eq.(42). Under Assumption 1, the spectral norm of the Hessian of model $f$ satisfies:

with $H_{\alpha_{i}}$ being the Hessian matrix of the sub-model $\alpha_{i}$. Because the parameters of $f$ is the concatenation of sub-model parameters and the sub-models share no common parameters, in the summation of Eq.(44), there must be at most one non-zero term (non-zero only when $w_{j}$ and $w_{k}$ belong to the same model $\alpha_{i}$. Thus, the Hessian spectral norm can be bounded by

Appendix D An illustrative example of composition models

By Proposition 4, the tangent kernel matrix of $h$, i.e. $K_{h}$, can be decomposed into the sum of two positive semi-definite matrices, and the uniform conditioning of $K_{h}$ can be guaranteed if one of them is uniformly conditioned, as demonstrated in Eq.(16). In the following, we show $K_{g}$ is uniformly conditioned by making $f$ well separated.

We assume the training data are not degenerated and the parameters ${\mathbf{u}}$ are randomly initialized. This makes sure the initial outputs of $f$, which are the initial inputs of $g$, are not degenerated, with high probability. For example, let $\min_{i\neq j}|x_{i}-x_{j}|\geq\sqrt{2}$ and initialize ${\mathbf{u}}$ by $\mathcal{N}(0,100R^{2})$ with a given number $R>0$. Then, we have

Since $\min_{i\neq j}|x_{i}-x_{j}|\geq\sqrt{2}$, the variance $Var:=200R^{2}-200R^{2}e^{\frac{-|x_{i}-x_{j}|^{2}}{2}}>100R^{2}$. For this Gaussian distribution, we have, with probability at least $0.96$, that

For this model, the partial tangent kernel $K_{g}$ is the Gaussian kernel in the limit of $m\to\infty$, with the following entries:

By the Gershgorin circle theorem, its smallest eigenvalue is lower bounded by:

Within the ball $B(({\mathbf{u}}_{0},{\mathbf{a}}_{0}),R):=\{({\mathbf{u}},{\mathbf{a}}):\|{\mathbf{u}}-{\mathbf{u}}_{0}\|^{2}+\|{\mathbf{a}}-{\mathbf{a}}_{0}\|^{2}\leq R^{2}\}$ with an arbitrary radius $R>0$, the outputs of $f$ are always well separated, given that the initial outputs of $f$ are separated by $2R$ as already discussed above. This is because

Hence, we see that composing large non-linear models may make the tangent kernel no longer constant, but the uniform conditioning of the tangent kernel can remain.

Appendix E Wide CNN and ResNet satisfy PL∗ condition

In this section, we will show that wide Convolutional Neural Networks (CNN) and Residual Neural Networks (ResNet) also satisfy the PL∗ condition.

where $*$ is the convolution operator (see the definition below) and $\langle\cdot,\cdot\rangle$ is the standard matrix inner product.

For the simplicity of the notation, we give the definition of convolution operation for 1-D CNN in the following. We note that it’s not hard to extend to higher dimensional CNNs and one will find that our analysis still applies.

The ResNet is similarly defined as follows:

We see that the ResNet is the same as a fully connected neural network, Eq. (4.2), except that the activations $\alpha^{(l)}$ has an extra additive term $\alpha^{(l-1)}$ from the previous layer, interpreted as skip connection.

This definition of ResNet differs from the standard ResNet architecture in that the skip connections are at every layer, instead of every two layers. One will find that the same analysis can be easily generalized to cases where skip connections are at every two or more layer. The same definition, up to a scaling factor, was also theoretically studied in .

By the following theorem, we have an upper bound for the Hessian spectrum norm of the CNN and ResNet, similar to Theorem 5 for fully-connected neural networks.

Consider a neural network $f({\mathbf{W}};{\mathbf{x}})$ of the form Eq.(E) or Eq.(E). Let $m$ be the minimum of the hidden layer widths, i.e., $m=\min_{l\in[L]}m_{l}$. Given any fixed $R>0$, and any ${\mathbf{W}}\in B({\mathbf{W}}_{0},R):=\{{\mathbf{W}}:\|{\mathbf{W}}-{\mathbf{W}}_{0}\|\leq R\}$, with high probability over the initialization, the Hessian spectral norm satisfies the following:

Using the same analysis in Section 4.2, we can get a similar result with Theorem 4 for CNN and ResNet to show they also satisfy PL∗ condition:

Consider the neural network $f({\mathbf{W}};{\mathbf{x}})$ in Eq.(E) or Eq.(E), and a random parameter setting ${\mathbf{W}}_{0}$ such that each element of $W_{0}^{(l)}$ for $l\in[L+1]$ follows $\mathcal{N}(0,1)$. Suppose that the last layer activation $\sigma_{L+1}$ satisfies $|\sigma^{\prime}_{L+1}(z)|\geq\rho>0$ and that $\lambda_{0}:=\lambda_{min}(K({\mathbf{W}}_{0}))>0$. For any $\mu\in(0,\lambda_{0}\rho^{2})$, if the width of the network

then $\mu$-PL∗ condition holds for square loss in the ball $B({\mathbf{W}}_{0},R)$.

Appendix F Proof for convergence under PL∗ condition

In Theorem 6, the convergence of gradient descent is established in the case of square loss function. In fact, similar results (with a bit modification) hold for general loss functions. In the following theorem, we provide the convergence under PL∗ condition for general loss functions. Then, we prove Theorem 6 and 14 together.

(a) Existence of a solution: There exists a solution (global minimizer of ${\mathcal{L}}$) ${\mathbf{w}}^{*}\in B({\mathbf{w}}_{0},R)$, such that ${\mathcal{F}}({\mathbf{w}}^{*})={\mathbf{y}}$.

(b) Convergence of GD: Gradient descent with a step size $\eta\leq 1/\sup_{{\mathbf{w}}\in B({\mathbf{w}}_{0},R)}\|H_{\mathcal{L}}({\mathbf{w}})\|_{2}$ converges to a global solution in $B({\mathbf{w}}_{0},R)$, with an exponential (also known as linear) convergence rate:

where the condition number $\kappa_{{\mathcal{L}},{\mathcal{F}}}(B({\mathbf{w}}_{0},R))=\frac{1}{\eta\mu}$.

Let’s start with Theorem 14. We prove this theorem by induction. The induction hypothesis is that, for all $t\geq 0$, ${\mathbf{w}}_{t}$ is within the ball $B({\mathbf{w}}_{0},R)$ with $R=\frac{2\sqrt{2\beta{\mathcal{L}}({\mathbf{w}}_{0})}}{\mu}$, and

In the base case, where $t=0$, it is trivial that ${\mathbf{w}}_{0}\in B({\mathbf{w}}_{0},R)$ and that ${\mathcal{L}}({\mathbf{w}}_{t})\leq\left(1-\eta\mu\right)^{0}{\mathcal{L}}({\mathbf{w}}_{0}).$

Suppose that, for a given $t\geq 0$, ${\mathbf{w}}_{t}$ is in the ball $B({\mathbf{w}}_{0},R)$ and Eq.(55) holds. As we show separately below (in Eq.(59) we have ${\mathbf{w}}_{t+1}\in B({\mathbf{w}}_{0},R)$. Hence we see that ${\mathcal{L}}$ is $(\sup_{{\mathbf{w}}\in B({\mathbf{w}}_{0},R)}\|H_{\mathcal{L}}({\mathbf{w}})\|_{2})$-smooth in $B({\mathbf{w}}_{0},R)$. By definition of $\eta=1/\sup_{{\mathbf{w}}\in B({\mathbf{w}}_{0},R)}\|H_{L}({\mathbf{w}})\|_{2}$ and, consequently, ${\mathcal{L}}$ is $1/\eta$-smooth. Using that we obtain the following:

Taking ${\mathbf{w}}_{t+1}-{\mathbf{w}}_{t}=-\eta\nabla{\mathcal{L}}({\mathbf{w}}_{t})$ and by $\mu$-PL∗ condition at point ${\mathbf{w}}_{t}$, we have

To prove ${\mathbf{w}}_{t+1}\in B({\mathbf{w}}_{0},R)$, by the fact that ${\mathcal{L}}$ is $\beta$-smooth, we have

Thus, ${\mathbf{w}}_{t+1}$ resides in the ball $B({\mathbf{w}}_{0},R)$.

By the principle of induction, the hypothesis is true.

Now, we prove Theorem 6, i.e., the particular case of square loss ${\mathcal{L}}({\mathbf{w}})=\frac{1}{2}\|{\mathcal{F}}({\mathbf{w}})-{\mathbf{y}}\|^{2}$. In this case,

Hence, in Eq.(59), we have the following instead:

Also note that, for all $t>0$, $\|H_{\mathcal{L}}({\mathbf{w}}_{t})\|_{2}\leq L_{\mathcal{F}}^{2}+\beta_{\mathcal{F}}\cdot\|{\mathcal{F}}({\mathbf{w}}_{0})-{\mathbf{y}}\|$, since $\|{\mathcal{F}}({\mathbf{w}}_{t})-{\mathbf{y}}\|\leq\|{\mathcal{F}}({\mathbf{w}}_{0})-{\mathbf{y}}\|$. Hence, the step size $\eta=1/L_{F}^{2}+\beta_{\mathcal{F}}\cdot\|{\mathcal{F}}({\mathbf{w}}_{0})-{\mathbf{y}}\|$ is valid. ∎

Appendix G Proof of Theorem 7

Following a similar analysis to the proof of Theorem 1 in , by the $\mu$-PL∗ condition, we can get that for any mini-bath size $s$, the mini-batch SGD with step size $\eta^{*}(s):=\frac{n\mu}{n\lambda(n^{2}\lambda+\mu(s-1))}$ has an exponential convergence rate for all $t>0$:

Moreover, the expected length of each step is bounded by

where we use $\{i_{t}^{(1)},i_{t}^{(2)},...,i_{t}^{(s)}\}$ to denote a random mini-batch of the dataset at step $t$.

Then the expectation of the length of the whole optimization path is bounded by

By Markov’s inequality, we have, with probability at least $1-\delta$, the length of the path is shorter than $R$, i.e.,

This means that, with probability at least $1-\delta$, the whole path is covered by the ball $B({\mathbf{w}}_{0},R)$, namely, for all $t$,

For those events when the whole path is covered by the ball, we can relax the satisfaction of the PL∗ condition from the whole space to the ball. ∎