On Sparsity in Overparametrised Shallow ReLU Networks

We consider a shallow neural network with hidden-layer-width $m$ as the following function:

where $\bm{x}\in\Omega\subseteq\mathbb{R}^{d}$ is the feature of the input data, $\phi(\bm{\theta},\bm{x})=c\sigma(a^{\top}\bm{x}+b)$ is the neuron constructed from an activation function $\sigma$, and $\bm{\theta}_{j}=(c_{j},\theta_{j})\in\mathbb{R}\times\mathbb{R}^{d+1}:=\Theta$ with $\theta=(a,b)$ are the parameters for the $j$-th neuron. As observed by several authors [MMN18, CB18b, RVE18, SS18], such a neural network can be equivalently represented in terms of a probability measure over $\Theta$ as $f_{\mu^{(m)}}$, where

and $\mu^{(m)}$ is the empirical measure of the parameters $\{\bm{\theta}_{j}\}_{j=1}^{m}$: $\mu^{(m)}=\frac{1}{m}\sum_{j=1}^{m}\delta_{\bm{\theta}_{j}}~{}.$

Let us denote by $\mathcal{P}(\Theta)$ the space of probability measures over $\Theta$. In the following, we write $\langle\chi,\mu\rangle:=\int_{\Theta}\chi(\bm{\theta})\mu(d\bm{\theta})$ for a Borel-measurable test function $\chi$ and $\phi_{\bm{x}}:=\phi(\cdot,\bm{x})$. Let $V:\Theta\to\mathbb{R}^{+}$ be a non-negative potential function satisfying $\inf_{\alpha,c}V(\alpha a,\alpha b,c)>0$. The set of functions representable as (1) defines a metric space $\mathcal{F}_{V}$ with norm

When $V(\bm{\theta})=|c|\|\theta\|$, the resulting space is the so-called variation-norm space $\mathcal{F}_{1}$ [Bac17]. One can verify [MWE19] that $V(\bm{\theta})=|c|^{q}(\|\theta\|)^{q}$ gives the same functional characterisation for any $q\geq 1$. Moreover, if $\phi$ is 2-homogeneous w.r.t. $\bm{\theta}$ (such as the ReLU $\sigma(t)=\max(0,t)$) ¹¹1$\phi(t\bm{\theta},\bm{x})=t^{2}\phi(\bm{\theta},\bm{x})$, then one can also verify that $V(\bm{\theta})=\|\bm{\theta}\|^{2}$ also defines the same space ²²2By first projecting the measure to the unit sphere $\|\theta\|=1$ and then lifting again as a point mass in the $c$-direction, and using the fact that $\mu$ has mass $1$; see [MWE19], Theorem 1.. Such apparent flexibility is a consequence of the fact that $\mu$, the underlying object parametrising the integral representation (3), is in fact a lifted version of a more ‘fundamental’ object $\nu=\mathrm{P}(\mu)\in\mathcal{M}(\mathbb{S}^{d})$, the space of signed Radon measures over the unit $(d+1)$-dimensional sphere . The measures $\mu$ and $\nu$ are related via the projection

for all continuous test functions $\chi:\mathbb{S}^{d}\to\mathbb{R}$. One can verify [Chi19] that for the previous choice of potential $V$, one has $\|f\|_{V}=\inf\{\|\nu\|_{\mathrm{TV}};\,f(\bm{x})=\int_{\mathbb{S}^{d}}\sigma(\langle\tilde{\theta},\tilde{\bm{x}}\rangle)d\nu(\tilde{\theta})\}$, where $\tilde{\bm{x}}=(\bm{x},1)$ and $\|\nu\|_{\mathrm{TV}}$ is the Total-Variation norm of $\nu$ [Bac17].

This variation-norm space contains any RKHS whose kernel is generated as an expectation over features $k(\bm{x},\bm{x}^{\prime})=\int_{\Theta}\phi(\bm{\theta},\bm{x})\phi(\bm{\theta},\bm{x}^{\prime})\mu_{0}(d\bm{\theta})$ with a base measure $\mu_{0}$, but it provides crucial advantages over these RKHS at approximating certain non-smooth, high-dimensional functions having some ‘hidden’ low-dimensional structure [Bac17]. This motivates the study of overparametrised shallow networks with the scaling as in (1), as opposed to the NTK scaling [JGH18] in $1/\sqrt{m}$.

As we will see in Section 3, other $\mathcal{F}_{V}$ spaces arise naturally when training overparametrised neural networks with noisy dynamics, corresponding to different choice of potential function. In the following, we are going to focus on the ReLU case where $\sigma(t)=(t)_{+}=\max(0,t)$.

Given samples $\{(\bm{x}_{i},y_{i})\in\Omega\times\mathbb{R}\}_{i=1\dots n}$ for a regression task, learning in $\mathcal{F}_{1}$ in the interpolant regime (corresponding to overparametrised models) amounts to the following problem

This problem can be equivalently expressed as an optimization problem in $\mathcal{P}(\Theta)$:

Even though $\mathcal{F}_{1}$ is not a RKHS, its convex structure also provides a Representer Theorem [Zuh48, FJ75, Bac17, BCC⁺19]: the extreme points of the solution set of (6) consist of point masses $\sum_{j=1}^{r}c_{j}\delta_{\bm{\theta}_{j}}$ of support $r$ at most $n$. In other words, there exist minimisers of the variation norm that require at most $n$ neurons to interpolate the data. However, in contrast with the RKHS representer theorem, these neurons are not explicit in terms of the datapoints, and cannot be directly characterised from (6) since this problem generally lacks unicity.

In practice, (6) is typically solved in the penalised form, by introducing the explicit regularised empirical loss

where $\ell$ is convex w.r.t. its first argument, e.g. $\ell(x,y)=\frac{1}{2}|x-y|^{2}$ and $\lambda$ controls the regularisation strength, so (6) can be obtained as the limit $\lambda\to 0^{+}$ in (7).

Notice that for empirical measures $\mu^{(m)}$ corresponding to a $m$-width shallow network, the loss $\mathcal{L}(\mu^{(m)})$ is precisely the loss

with respect to the parameters $\{\bm{\theta}_{j}\}_{j\leq m}$. In that case, the regularisation term corresponds to weight decay for $V(\bm{\theta})=\|\bm{\theta}\|^{2}$, and the so-called path norm [NTS15] for $V(\bm{\theta})=|c|\|\theta\|$. As also argued in [NTS14], these two regularisation terms capture the same implicit bias in the functional space.

Performing gradient descent on $L$ with respect to $\{\bm{\theta}_{j}\}_{j}$ induces gradient dynamics on the functional $\mathcal{L}$ over $\mathcal{P}(\Theta)$, with respect to the Wasserstein metric [MMN18, CB18b, RVE18, SS18], thus mapping an Euclidean non-convex problem (8) to a non-Euclidean convex one (7). The gradient dynamics of overparametrised neural networks in the infinite-width limit can thus be analysed as the mean-field limit of such Wasserstein Gradient flows, leading to global convergence for problems such as (7) under appropriate homogeneity assumptions for $\phi$ [CB18b, Chi19]. However, such convergence results are qualitative and only hold in the limit of $m\to\infty$ without extra structure in the minimisers of $\mathcal{L}(\mu)$ such as being point masses – precisely the structure that our main results from Section 4 provide.

A popular alternative to the explicit variation-norm regularisation is to rely on the particular choice of optimization scheme to provide an implicit regularisation effect. While gradient descent enjoys powerful implicit regularisation for logistic regression [SHN⁺18, CB20] by favoring max-margin solutions, and for linear least-squares regression by choosing solutions of minimal $\ell_{2}$ norm, the situation for non-linear least-squares is less clear.

Indeed, in those cases, the dynamics do not typically forget the initial conditions, making them very sensitive to initialisation and producing substantial qualitative changes, as illustrated by the lazy dynamics [CB18a]. A powerful alternative is thus given by algorithms that inject noise into the dynamics, such as SGD or Langevin Dynamics. The latter was studied in the framework of overparametrised shallow networks in [MMN18]. This dynamics leads to an associated cost of the form:

where $\mathcal{H}$ is the relative entropy of $\mu$. Minimizers to this functional have a smooth density that is solution to the associated elliptic Euler-Lagrange problem. They are therefore not sparse due to the entropic regularisation.

An alternative to Langevin Dynamics and SGD was recently studied in [BGVV19], consisting of adding noise into the targets $y_{i}$ rather than the parameters. As already hinted in [BGVV19], the resulting dynamics capture an implicit bias corresponding to a $V$-space for a data-dependent potential function $V$.

Blanc et al. [BGVV19] propose Algorithm 1 for training a neural network on a data-set $(\bm{x}_{i},y_{i})_{i=1}^{n}$. The algorithm is an SGD-type algorithm with a small, independent perturbation on each label $y_{i}$ sampled independently on each gradient step.

Denote by ${\mathcal{D}}=(\bm{x}_{1},\dots\bm{x}_{n})$ the input data and let ${\mathbb{E}}_{{\mathcal{D}}}$ denote the empirical average over the observed $n$ datapoints. Let $\vec{\bm{\theta}}=(\bm{\theta}_{1},\dots,\bm{\theta}_{m})$. The main result therein [BGVV19, Theorem 2] states that, for large times (depending, amongst others, on the noise size and the number of parameters), the solution concentrates at local minimizers (amongst the zero-error solutions) of the effective regularization loss:

The RHS of (10) is now an integral over the counting measure $\mu=\frac{1}{m}\sum_{j=1}^{m}\delta_{\bm{\theta}_{j}}$, and therefore,

As we have seen in the previous section, the training algorithm with label noise minimizes $\langle\tilde{V}_{b},\mu\rangle$. In the ReLU case we can explicitly write:

The key realization is that in order to minimize the value of 11, the algorithm will exploit the degeneracy $(a,b,c)\sim(\lambda a,\lambda b,\lambda^{-1}c)$ for $\lambda>0$. In other words, we may substitute $\widetilde{V}_{b}$ for $V_{b}(a,b,c)=\min_{\lambda>0}\widetilde{V}_{b}(\lambda a,\lambda b,\lambda^{-1}c)$ without effectively changing the problem. A straightforward computation shows that $V_{b}(a,b,c)$ is equal to:

There are two crucial properties of the potential function $V_{b}$. First, that it is invariant under the $\lambda$ degeneracy described above: If we have a measure $\mu$ and modify it with the method above to obtain $\tilde{\mu}$, both of them will have the same loss. The second is that the function $w$ is convex, and, as long as the neurons can ‘see’ enough of the dataset, essentially convex. To make this precise, we start with two definitions:

With these definitions in hand, we can state the main result of this section, a convexity result for the regularization loss (see the Appendix for a proof):

We will show next how such convexity structure in the potential function can be leveraged to characterise minimisers of (6) and (7).