Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel

Introduction

In deep learning, over-parametrization refers to the widely-adopted technique of using more parameters than necessary . Over-parametrization is crucial for successful optimization, and a large body of work has been devoted towards understanding why. One line of recent works offers an explanation that invites analogy with kernel methods, proving that with sufficient over-parameterization and a certain initialization scale and learning rate schedule, gradient descent essentially learns a linear classifier on top of the initial random features. For this same setting, Daniely , Du et al. , Jacot et al. , Arora et al. make this connection explicit by establishing that the prediction function found by gradient descent is in the span of the training data in a reproducing kernel Hilbert space (RKHS) induced by the Neural Tangent Kernel (NTK). The generalization error of the resulting network can be analyzed via the Rademacher complexity of the kernel method.

These works provide some of the first algorithmic results for the success of gradient descent in optimizing neural nets; however, the resulting generalization error is only as good as that of fixed kernels . On the other hand, the equivalence of gradient descent and NTK is broken if the loss has an explicit regularizer such as weight decay.

In this paper, we study the effect of an explicit regularizer on neural net generalization via the lens of margin theory. We first construct a simple distribution on which the two-layer network optimizing explicitly regularized logistic loss will achieve a large margin, and therefore, good generalization. On the other hand, any prediction function in the span of the training data in the RKHS induced by the NTK will overfit to noise and therefore achieve poor margin and bad generalization.

Motivated by the provably better generalization of regularized neural nets for our constructed instance, in Section 3 we study their optimization, as the previously cited results only apply when the neural net behaves like a kernel. We show optimization is possible for infinite-width regularized nets.

This improves upon prior works which study optimization in the same infinite-width limit but do not provide polynomial convergence rates. (See more discussions in Section 3.)

Finally, we empirically validate several claims made in this paper in Section 5. First, we confirm on synthetic data that neural networks do generalize better with an explicit regularizer vs. without. Second, we show that for two-layer networks, the test error decreases and margin increases as the hidden layer grows, as predicted by our theory.

Zhang et al. and Neyshabur et al. show that neural network generalization defies conventional explanations and requires new ones. Neyshabur et al. initiate the search for the “inductive bias” of neural networks towards solutions with good generalization. Recent papers study inductive bias through training time and sharpness of local minima. Neyshabur et al. propose a steepest descent algorithm in a geometry invariant to weight rescaling and show this improves generalization. Morcos et al. relate generalization to the number of “directions” in the neurons. Other papers study implicit regularization towards a specific solution. Ma et al. show that implicit regularization helps gradient descent avoid overshooting optima. Rosset et al. study linear logistic regression with weak regularization and show convergence to the max margin. In Section 4, we adopt their techniques and extend their results.

A line of work initiated by Neyshabur et al. has focused on deriving tighter norm-based Rademacher complexity bounds for deep neural networks and new compression based generalization properties . Bartlett et al. highlight the important role of normalized margin in neural net generalization. Wei and Ma prove generalization bounds depending on additional data-dependent properties. Dziugaite and Roy compute non-vacuous generalization bounds from PAC-Bayes bounds. Neyshabur et al. investigate the Rademacher complexity of two-layer networks and propose a bound that is decreasing with the distance to initialization. Liang and Rakhlin and Belkin et al. study the generalization of kernel methods.

For optimization, Soudry and Carmon explain why over-parametrization can remove bad local minima. Safran and Shamir show over-parametrization can improve the quality of a random initialization. Haeffele and Vidal , Nguyen and Hein , and Venturi et al. show that for sufficiently overparametrized networks, all local minima are global, but do not show how to find these minima via gradient descent. Du and Lee show for two-layer networks with quadratic activations, all second-order stationary points are global minimizers. Arora et al. interpret over-parametrization as a means of acceleration. Mei et al. , Chizat and Bach , Sirignano and Spiliopoulos , Dou and Liang , Mei et al. analyze a distributional view of over-parametrized networks. Chizat and Bach show that Wasserstein gradient flow converges to global optimizers under structural assumptions. We extend this to a polynomial-time result.

Finally, many papers have shown convergence of gradient descent on neural nets using analyses which prove the weights do not move far from initialization. These analyses do not apply to the regularized loss, and our experiments in Section F suggest that moving away from the initialization is important for better test performance.

Another line of work takes a Bayesian perspective on neural nets. Under an appropriate choice of prior, they show an equivalence between the random neural net and Gaussian processes in the limit of infinite width or channels . This provides another kernel perspective of neural nets.

Yehudai and Shamir , Chizat and Bach also argue that the kernel perspective of neural nets is not sufficient for understanding the success of deep learning. Chizat and Bach argue that the kernel perspective of gradient descent is caused by a large initialization and does not necessarily explain the empirical successes of over-parametrization. Yehudai and Shamir prove that $\Omega(\exp(d))$ random relu features cannot approximate a single neuron in squared error loss. In comparison, our lower bounds are for the sample complexity rather than width of the NTK prediction function and apply even with infinite over-parametrization for both classification and squared loss.

2 Notation

Generalization of Regularized Neural Net vs. NTK Kernel

We will compare neural net solutions found via regularization and methods involving the NTK and construct a data distribution $\mathcal{D}$ in $d$ dimensions which the neural net optimizer of regularized logistic loss learns with sample complexity $O(d)$. The kernel method will require $\Omega(d^{2})$ samples to learn.

The distribution $\mathcal{D}$ contains all of its signal in the first 2 coordinates, and the remaining $d-2$ coordinates are noise. We visualize its first 2 coordinates in Figure 1.

Let $\Theta_{\lambda}\in\operatorname*{arg\,min}_{\Theta}L_{\lambda}(\Theta)$ be its global optimizer. Define the NTK kernel associated with the architecture (with random weights):

For coefficients $\beta$, we can then define the prediction function $f^{\textup{kernel}}(x;\beta)$ in the RKHS induced by $K$ as $f^{\textup{kernel}}(x;\beta)\triangleq\sum_{i=1}^{n}\beta_{i}K(x_{i},x)$. For example, such a classifier would be attained by running gradient descent on squared loss for a wide network using the appropriate random initialization (see ). We now present our comparison theorem below and fill in its proof in Section B.

Let $\mathcal{D}$ be the distribution defined in equation 2.5. With probability $1-d^{-5}$ over the random draw of $n\lesssim d^{2}$ samples $(x_{1},y_{1}),\ldots,(x_{n},y_{n})$ from $\mathcal{D}$, for all choices of $\beta$, the kernel prediction function $f^{\textup{kernel}}(\cdot;\beta)$ will have at least $\Omega(1)$ error:

Meanwhile, for $\lambda\leq\textup{poly}(n)^{-1}$, the regularized neural net solution $f^{\textup{NN}}(\cdot;\Theta_{\lambda})$ with at least 4 hidden units can have good generalization with $O(d^{2})$ samples because we have the following generalization error bound:

This implies a $\Omega(d)$ sample-complexity gap between the regularized neural net and kernel prediction function.

Our intuition of this gap is that the regularization allows the neural net to find informative features (weight vectors), that are adaptive to the data distribution and easier for the last layers’ weights to separate. For example, the neurons $[e_{1}x]_{+}$, $[-e_{1}x]_{+}$, $[e_{2}x]_{+}$, $[-e_{2}x]_{+}$ are enough to fit our particular distribution. In comparison, the NTK method is unable to change the feature space and is only searching for the coefficients in the kernel space.

Proof techniques for the upper bound: For the upper bound, neural nets with small Euclidean norm will be able to separate $\mathcal{D}$ with large margin (a two-layer net with width 4 can already achieve a large margin). As we show in Section 4, a solution with a max neural-net margin is attained by the global optimizer of the regularized logistic loss — in fact, we show this holds for generally homogeneous networks of any depth and width (Theorem 4.1). Then, by the classical connection between margin and generalization , this optimizer will generalize well.

Proof techniques for the lower bound: On the other hand, the NTK will have a worse margin when fitting samples from $\mathcal{D}$ than the regularized neural networks because NTK operates in a fixed kernel space.There could be some variations of the NTK space depending on the scales of the initialization of the two layers, but our Theorem 2.1 shows that these variations also suffer from a worse sample complexity. However, proving that the NTK has a small margin does not suffice because the generalization error bounds which depend on margin may not be tight.

We develop a new technique to prove lower bounds for kernel methods, which we believe is of independent interest, as there are few prior works that prove lower bounds for kernel methods. (One that does is , but their results require constructing an artificial kernel and data distribution, whereas our lower bounds are for a fixed kernel.) The main intuition is that because NTK uses infinitely many random features, it is difficult for the NTK to focus on a small number of informative features – doing so would require a very high RKHS norm. In fact, we show that with a limited number of examples, any function that in the span of the training examples must heavily use random features rather than informative features. The random features can collectively fit the training data, but will give worse generalization.

Perturbed Wasserstein Gradient Flow Finds Global Optimizers in Polynomial Time

Prior work has shown that as the hidden layer size grows to infinity, gradient descent for a finite neural network approaches the Wasserstein gradient flow over distributions of hidden units (defined in equation 3.1). With the assumption that the gradient flow converges, which is non-trivial since the space of distributions is infinite-dimensional, Chizat and Bach prove that Wasserstein gradient flow converges to a global optimizer but do not specify a rate. Mei et al. add an entropy regularizer to form an objective that is the infinite-neuron limit of stochastic Langevin dynamics. They show global convergence but also do not provide explicit rates. In the worst case, their convergence can be exponential in dimension. In contrast, we provide explicit polynomial convergence rates for a slightly different algorithm, perturbed Wasserstein gradient flow.

$\Phi$ and $V$ are differentiable as well as upper bounded and Lipschitz on the unit sphere. $R$ is Lipschitz and its Hessian has bounded operator norm.

We interpret $\rho$ as a distribution over the parameters of the network. Let $k\triangleq n$ and $\Phi_{i}(\theta)\triangleq w\phi(u^{\top}x_{i})$ for $\theta=(w,u)$. In this case, $\int\Phi d\rho$ is a distributional neural network that computes an output for each of the $n$ training examples (like a standard neural network, it also computes a weighted sum over hidden units). We can compute the distributional version of the regularized logistic loss in equation 2.6 by setting $V(\theta)\triangleq\lambda\|\theta\|_{2}^{2}$ and $R(a_{1},\ldots,a_{n})\triangleq\sum_{i=1}^{n}\log(1+\exp(-y_{i}a_{i}))$.

where $\nabla\cdot$ denotes the divergence of a vector field. For neural networks, these dynamics formally define continuous-time gradient descent when the hidden layer has infinite size (see Theorem 2.6 of , for instance). More generally, equation 3.1 is due to the formula for Wasserstein gradient flow dynamics (see for example ), which are derived via continuous-time steepest descent with respect to Wasserstein distance over the space of probability distributions on the neurons. We propose the following modified dynamics:

Suppose that $\Phi$ and $V$ are 2-homogeneous and the regularity conditions of Assumption 3.1 are satisfied. Also assume that from starting distribution $\rho_{0}$, a solution to the dynamics in equation 3.2 exists. Define $L^{\star}\triangleq\inf_{\rho}L[\rho]$. Let $\epsilon>0$ be a desired error threshold and choose $\sigma\triangleq\exp(-d\log(1/\epsilon)\textup{poly}(k,L[\rho_{0}]-L^{\star}))$ and $t_{\epsilon}\triangleq\frac{d^{2}}{\epsilon^{4}}\textup{poly}(\log(1/\epsilon),k,L[\rho_{0}]-L^{\star})$, where the regularity parameters for $\Phi$, $V$, and $R$ are hidden in the $\textup{poly}(\cdot)$. Then, perturbed Wasserstein gradient flow converges to an ${\epsilon}$-approximate global minimum in $t_{\epsilon}$ time:

As a technical detail, Theorem 3.3 requires that a solution to the dynamics exists. We can remove this assumption by analyzing a discrete-time version of equation 3.2: $\rho_{t+1}\triangleq\rho_{t}+\eta(-\sigma\rho_{t}+\sigma U^{d}-\nabla\cdot(v[\rho_{t}]\rho_{t}))$, and additionally assuming $\Phi$ and $V$ have Lipschitz gradients. In this setting, a polynomial time convergence result also holds. We state the result in Section E.4.

Weak Regularizer Guarantees Max Margin Solutions

In this section, we collect a number of results regarding the margin of a regularized neural net. These results provide the tools for proving generalization of the weakly-regularized NN solution in Theorem 2.1. The key technique is showing that with small regularizer $\lambda\rightarrow 0$, the global optimizer of regularized logistic loss will obtain a maximum margin. It is well-understood that a large neural net margin implies good generalization performance .

In fact, our result applies to a function class much broader than two-layer relu nets: in Theorem 4.1 we show that when we add a weak regularizer to cross-entropy loss with any positive-homogeneous prediction function, the normalized margin of the optimum converges to the max margin. For example, Theorem 4.1 applies to feedforward relu networks of arbitrary depth and width. In Theorem C.2, we bound the approximation error in the maximum margin when we only obtain an approximate optimizer of the regularized loss. In Corollary 4.2, we leverage these results and pre-existing Rademacher complexity bounds to conclude that the optimizer of the weakly-regularized logistic loss will have width-free generalization bound scaling with the inverse of the max margin and network depth. Finally, we note that the maximum possible margin can only increase with the width of the network, which suggests that increasing width can improve generalization of the solution (see Theorem 4.3).

for fixed $r>0$. Let $\Theta_{\lambda}\in\operatorname*{arg\,min}L_{\lambda}(\Theta)$.We formally show that $L_{\lambda}$ has a minimizer in Claim C.3 of Section C. Define the normalized margin $\gamma_{\lambda}$ and max-margin $\gamma^{\star}$ by $\gamma_{\lambda}\triangleq\min_{i}y_{i}f(x_{i};\bar{\Theta}_{\lambda})$ and $\gamma^{\star}\triangleq\max_{\|\Theta\|\leq 1}\min_{i}y_{i}f(x_{i};\Theta)$. Let $\Theta^{\star}$ achieve this maximum.

We show that with sufficiently small regularization level $\lambda$, the normalized margin $\gamma_{\lambda}$ approaches the maximum margin $\gamma^{\star}$. Our theorem and proof are inspired by the result of Rosset et al. , who analyze the special case when $f$ is a linear function. In contrast, our result can be applied to non-linear $f$ as long as $f$ is homogeneous.

Assume the training data is separable by a network $f(\cdot;\Theta^{\star})\in\mathcal{F}$ with an optimal normalized margin $\gamma^{\star}>0$. Then, the normalized margin of the global optimum of the weakly-regularized objective (equation 4.1) converges to $\gamma^{\star}$ as the regularization goes to zero. Mathematically,

An intuitive explanation for our result is as follows: because of the homogeneity, the loss $L(\Theta_{\lambda})$ roughly satisfies the following (for small $\lambda$, and ignoring parameters such as $n$):

Thus, the loss selects parameters with larger margin, while the regularization favors smaller norms. The full proof of the theorem is deferred to Section C.

Though the result in this section is stated for binary classification, it extends to the multi-class setting with cross-entropy loss. We provide formal definitions and results in Section C. In Theorem C.2, we also show that an approximate minimizer of $L_{\lambda}$ can obtain margin that approximates $\gamma^{\star}$.

We consider depth-$q$ networks with 1-Lipschitz, 1-positive-homogeneous activation $\phi$ for $q\geq 2$. Note that the network function is $q$-positive-homogeneous. Suppose that the collection of parameters $\Theta$ is given by matrices $W_{1},\ldots,W_{q}$. For simplicity we work in the binary class setting, so the $q$-layer network computes a real-valued score

Following notation established in this section, we denote the optimizer of $L_{\lambda,\mathcal{M}}$ by $\Theta_{\lambda,\mathcal{M}}$, the normalized margin of $\Theta_{\lambda,\mathcal{M}}$ by $\gamma_{\lambda,\mathcal{M}}$, the max-margin solution by $\Theta^{\star,\mathcal{M}}$, and the max-margin by $\gamma^{\star,\mathcal{M}}$, assumed to be positive. Our notation emphasizes the architecture of the network.

We can define the population 0-1 loss of the network parameterized by $\Theta$ by $L(\Theta)\triangleq\Pr_{(x,y)\sim p_{\rm{data}}}[yf^{\textup{NN}}(x;\Theta)\leq 0]$. We let $\mathcal{X}$ denote the data domain and $C\triangleq\sup_{x\in\mathcal{X}}\|x\|_{2}$ denote the largest possible norm of a single datapoint.

By combining the neural net complexity bounds of Golowich et al. with our Theorem 4.1, we can conclude that optimizing weakly-regularized logistic loss gives generalization bounds that depend on the maximum possible network margin for the given architecture.

Suppose $\phi$ is 1-Lipschitz and 1-positive-homogeneous. With probability at least $1-\delta$ over the draw of $(x_{1},y_{1}),\ldots,(x_{n},y_{n})$ i.i.d. from $p_{\rm{data}}$, we can bound the test error of the optimizer of the regularized loss by

where $\epsilon(\gamma)\triangleq\sqrt{\frac{\log\log_{2}\frac{4C}{\gamma}}{n}}+\sqrt{\frac{\log(1/\delta)}{n}}$. Note that $\epsilon(\gamma^{\star,\mathcal{M}})$ is primarily a smaller order term, so the bound mainly scales with $\frac{C}{\gamma^{\star,\mathcal{M}}q^{(q-1)/2}\sqrt{n}}$. Although the $\frac{1}{q^{(q-1)/2}}$ factor of equation D.1 decreases with depth $q$, the margin $\gamma$ will also tend to decrease as the constraint $\|\bar{\Theta}\|_{F}\leq 1$ becomes more stringent.

Finally, we observe that the maximum normalized margin is non-decreasing with the size of the architecture. Formally, for two depth-$q$ architectures $\mathcal{M}=(m_{1},\ldots,m_{q-1})$ and $\mathcal{M^{\prime}}=(m^{\prime}_{1},\ldots,m^{\prime}_{q-1})$, we say $\mathcal{M}\leq\mathcal{M^{\prime}}$ if $m_{i}\leq m^{\prime}_{i}\ \forall i=1,\ldots q-1$. Theorem 4.3 states if $\mathcal{M}\leq\mathcal{M^{\prime}}$, the max-margin over networks with architecture $\mathcal{M^{\prime}}$ is at least the max-margin over networks with architecture $\mathcal{M}$.

Recall that $\gamma^{\star,\mathcal{M}}$ denotes the maximum normalized margin of a network with architecture $\mathcal{M}$. If $\mathcal{M}\leq\mathcal{M^{\prime}}$, we have

As a important consequence, the generalization error bound of Corollary 4.2 for $\mathcal{M^{\prime}}$ is at least as good as that for $\mathcal{M}$.

This theorem is simple to prove and follows because we can directly implement any network of architecture $\mathcal{M}$ using one of architecture $\mathcal{M^{\prime}}$, if $\mathcal{M}\leq\mathcal{M^{\prime}}$. This highlights one of the benefits of over-parametrization: the margin does not decrease with a larger network size, and therefore Corollary 4.2 gives a better generalization bound. In Section F, we provide empirical evidence that the test error decreases with larger network size while the margin is non-decreasing.

Simulations

We empirically validate our theory with several simulations. First, we train a two-layer net on synthetic data with and without explicit regularization starting from the same initialization in order to demonstrate the effect of an explicit regularizer on generalization. We confirm that the regularized network does indeed generalize better and moves further from its initialization. For this experiment, we use a large initialization scale, so every weight $\sim\mathcal{N}(0,1)$. We average this experiment over 20 trials and plot the test accuracy, normalized margin, and percentage change in activation patterns in Figure 2. We compute the percentage of activation patterns changed over every possible pair of hidden unit and training example. Since a low percentage of activations change when $\lambda=0$, the unregularized neural net learns in the kernel regime. Our simulations demonstrate that an explicit regularizer improves generalization error as well as the margin, as predicted by our theory.

The data comes from a ground truth network with $10$ hidden networks, input dimension $20$, and a ground truth unnormalized margin of at least $0.01$. We use a training set of size $200$ and train for $20000$ steps with learning rate $0.1$, once using regularizer $\lambda=5\times 10^{-4}$ and once using regularization $\lambda=0$. We note that the training error hits 0 extremely quickly (within 50 training iterations). The initial normalized margin is negative because the training error has not yet hit zero.

We also compare the generalization of a regularized neural net and kernel method as the sample size increases. Furthermore, we demonstrate that for two-layer nets, the test error decreases and margin increases as the width of the hidden layer grows, as predicted by our theory. We provide figures and full details in Section F.

Conclusion

Acknowledgments

CW acknowledges the support of a NSF Graduate Research Fellowship. JDL acknowledges support of the ARO under MURI Award W911NF-11-1-0303. This is part of the collaboration between US DOD, UK MOD and UK Engineering and Physical Research Council (EPSRC) under the Multidisciplinary University Research Initiative. We also thank Nati Srebro and Suriya Gunasekar for helpful discussions in various stages of this work.

References

Appendix A Additional Notation

In this section we collect additional notations that will be useful for our proofs.

Appendix B Missing Material from Section 2

Then as the kernel $K(x^{\prime},x)$ is the sum of positive scalings of $\langle\varphi_{\textup{grad}}(x),\varphi_{\textup{grad}}(x^{\prime})\rangle$ and $\langle\varphi_{\textup{relu}}(x),\varphi_{\textup{relu}}(x^{\prime})\rangle$, we can express

For the distribution $\mathcal{D}$ defined in Section 2, if $n\lesssim d^{2}$, with probability $1-\exp(-\Omega(\sqrt{n}))$ over $(x_{1},y_{1}),\ldots,(x_{n},y_{n})$ drawn i.i.d. from $\mathcal{D}$, for all choices of $\beta$, in test time the kernel prediction function $f^{\textup{kernel}}(\cdot;\beta)$ will predict the sign of $y$ wrong $\Omega(1)$ fraction of the time:

Then with probability $1-\exp(-\Omega(d))$, there is some universal constant $c$ such that

As a result, for all choices of $\beta_{1},\ldots,\beta_{n}$, we can lower bound the test error of the kernel prediction function by

For sufficiently small $n\lesssim d^{2}$, with probability $1-\exp(-\Omega(\sqrt{n}))$ over the random draws of $z_{1},\ldots,z_{n}$, the following holds: for all $\beta_{1},\ldots,\beta_{n}$, we will have

where $c$ is the constant defined in Lemma B.2.

This will allow us to complete the proof of Theorem B.1.

By plugging Lemma B.3 into the statement of Lemma B.2, we can conclude that for sufficiently small $n\lesssim d^{2}$, with probability $1-\exp(-\Omega(\sqrt{n}))$ over the random draws of $z_{1},\ldots,z_{n}$, we have

for all choices of $\beta$. This gives precisely Theorem B.1. ∎

It now suffices to prove Lemmas B.2 and B.3.

Let $z\in\{-1,+1\}^{d-2}$ be a uniform random point from the $d-2$-dimensional hypercube and $x\in\text{supp}(\mathcal{D}_{x})$ be given. With probability $1-\exp(-\Omega(d))$ over the choice of $z$, we have

In the same setting as Lemma B.4, with probability $1-\exp(-\Omega(d))$ over the choice of $z$, we have

As it will be clear in the context of this proof, we use $x_{1}$ to denote the first coordinate of $x$ and $x_{2}$ to denote the second coordinate of $x$. We prove the first inequality, as the proof for the second is identical. First, note that if $x_{1}=0$,$|x_{2}|=1$, then we have $K_{1}(x,(1,0,z))+K_{1}(x,(-1,0,z))=2K_{1}((0,1,x_{-2}),(1,0,z))$ so the inequality holds trivially. Thus, we work in the case that $|x_{1}|=1$, $x_{2}=0$.

Note that $\|(1,0,z)\|_{2}=\|(-1,0,z)\|_{2}=\|x\|_{2}=\sqrt{d-1}$. We have:

Now we perform a Taylor expansion of $\arccos$ around $\nu\triangleq x_{-2}^{\top}z/(d-1)$ to get

for any $|\nu|,|\nu+\epsilon|\leq 3/4$. Note that this happens with probability $1-\exp(-\Omega(d))$ by Hoeffding’s inequality. Furthermore, for $|\nu|\leq 3/4$, $\arccos^{\prime}(\nu)=O(1)$, so we get that equation B.4 can be bounded by $O(\frac{1}{d})$. Next, we claim the following:

This follows simply from Taylor expansion around $\nu$ setting $\epsilon$ to $\pm\frac{1}{d-1}$. Substituting this into equation B.5 and using our bound on equation B.4, we get

Now we use the fact that $x_{-2}^{\top}z\left(1-\pi^{-1}\arccos\left(\frac{x_{-2}^{\top}z}{d-1}\right)\right)=K_{1}((0,1,x_{-2}),(1,0,z))$ to complete the proof. ∎

As before, it suffices to prove the first inequality in the case that $|x_{1}|=1$, $x_{2}=0$. We can compute

Now we again perform a Taylor expansion, this time of $g(v)=\sqrt{1-v^{2}}$ around $\nu\triangleq\frac{x_{-2}^{\top}z}{d-1}$. We get

for any $|\nu|,|\nu+\epsilon|\leq 3/4$. Note that $|\nu|,|\nu+\epsilon|\leq 3/4$ with probability $1-\exp(-\Omega(d))$ via straightforward concentration. It follows that

Now plugging this into equation B.6 and using the fact that $\frac{1}{\pi}(d-1)\sqrt{1-\left(\frac{x_{-2}^{\top}z}{d-1}\right)^{2}}=K_{2}((0,1,x_{-2}),(1,0,z))$ gives the desired result. ∎

Now we can complete the proof of Lemma B.2.

Now with applying Lemmas B.4 and B.5 with a union bound over all $i$, we get with probability $1-\exp(-\Omega(d))$ over the choice of $z$ uniform from $\{-1,+1\}^{d-2}$, for all $i$

Now plugging into equation B.7 and applying triangle inequality gives us

with probablity $1-\exp(-\Omega(d))$ over $z$ for some universal constant $c$. An identical argument also gives us

Finally, to lower bound the quantity $\Pr_{(x,y)\sim\mathcal{D}}[f(x;\beta)y\leq 0]$, we note that if

and equation B.2 hold, then $f^{+}(z;\beta)$ and $f^{-}(z;\beta)$ will have the same sign. However, this in turn means that one of the following must hold:

which implies an incorrect predicted sign. As $(1,0,z)$, $(-1,0,z)$, $(0,1,z)$, $(0,-1,z)$ are all equally likely under distribution $\mathcal{D}_{x}$, the probability of drawing one of these examples under $\mathcal{D}_{x}$ is at least

This gives the desired lower bound on $\Pr_{(x,y)\sim\mathcal{D}}[f(x;\beta)y\leq 0]$. ∎

Then for $z\in\{-1,+1\}^{d-2}$ distributed uniformly over the hypercube and some given $z^{\prime}\in\{-1,+1\}^{d-2}$,

where $z\in\{-1,+1\}^{d}$ is a uniform vector from the hypercube.

For the degree-4 polynomial $g$ defined in Lemma B.6, we define

Note that by Cauchy-Schartz, $\sum_{i=1}^{n}{\beta_{i}}^{2}\geq\frac{1}{n}(\sum_{i=1}^{n}|\beta_{i}|)^{2}$. It follows that if $n\leq\frac{c_{2}}{4c^{2}}d^{2}$, we have

Now we can apply Bonami’s Lemma (see Chapter 9 of O’Donnell ) along with the fact that $\hat{f}$ is a degree-4 polynomial in i.i.d. $\pm 1$ variables $z_{1},\ldots,z_{d-2}$ to obtain

Combining this with Proposition 9.4 of O’Donnell lets us conclude that if $\mathcal{E}$ holds, with probability $\Omega(1)$ over the random draw of $z$,

holds with probability $\Omega(1)$ over $z$. This gives the desired result. ∎

with $|h_{1}(x)-g_{1}(x)|\leq O(|x|^{5})$ and $|h_{2}(x)-g_{2}(x)|\leq O(|x|^{5})$ for $|x|\leq 3/4$. )Now we can observe that $g(x)=(\tau_{1}+\tau_{2})(d-1)g_{1}(x)+\tau_{2}(d-1)g_{2}(x)$. Thus,

As $|z^{\top}z^{\prime}|/(d-1)\leq 3/4$ with probability $1-\exp(-\Omega(d))$, the above is bounded in absolute value by $(d-1)(\tau_{1}+\tau_{2})O\left(\left(\frac{|z^{\top}z^{\prime}|}{d-1}\right)^{5}\right)$. Finally, by Hoeffding’s inequality $|z^{\top}z^{\prime}|\leq c\sqrt{d\log d}$ with probability $1-d^{-10}$ for some universal constant $c$. This gives the desired bound. ∎

Now note that all terms in the above sum are nonnegative by Lemma B.9 and the fact that $a_{j_{1}},a_{j_{2}}\geq 0$. Thus, we can lower bound the above by the term corresponding to $j_{1}=j_{2}=2$:

Now letting $M^{\otimes 2}_{S}$ denote $M^{\otimes 2}$ with rows whose indices are not in $S$ zero’ed out, it follows that

Therefore, it suffices to show $\sigma_{\min}({M_{[d^{2}]\setminus S}^{\otimes 2}}^{\top}M_{[d^{2}]\setminus S}^{\otimes 2})\gtrsim d^{2}$ with high probability. To do this, we can simply invoke Proposition 7.9 of Soltanolkotabi et al. using $\eta_{\min}=\eta_{\max}=\sqrt{d^{2}-d}$ and the fact that the columns of $M_{[d^{2}]\setminus S}^{\otimes 2}$ are $O(1)$-sub-exponential (Claim B.8 to get that if $n\leq cd^{2}$ for some universal constant $c$, then $\sigma_{\min}^{2}(M_{[d^{2}]\setminus S}^{\otimes 2})\gtrsim d^{2}$ with probability $1-\exp(O(\sqrt{n}))$.

Finally, combining this with equation B.11 and equation B.10 gives the desired result. ∎

Suppose that $z\sim\{-1,+1\}^{d}$ is a uniform vector on the hypercube. Then there is a universal constant $c$ such that $z^{\otimes{2}}-\vec{1}_{S}$ is $c$-sub-exponential, where $S\triangleq\{(i-1)d+i:i\in[d]\}$ is the set of indices corresponding to squared entries of $z^{\otimes{2}}$.

Now we can apply Theorem 1.1 of Rudelson et al. , using the fact that $e_{i}^{\top}z$ have sub-Gaussian norm $2$ to get

for some universal constant $c^{\prime}$. Since this holds for all $y$, we can conclude the claim statement using Lemma 5.5 of Soltanolkotabi et al. . ∎

The following lemma is useful for proving the lower bound in Lemma B.7.

Let $z_{i}\in\{-1,+1\}^{d}$ for $i\in[n]$, and let $z\in\{-1,+1\}^{d}$ be a vector sampled uniformly from the hypercube. Then for any integers $p,q\geq 0$,

Furthermore, equality holds if exactly one of $p$ or $q$ is odd.

For this proof we will use double indices on the $z_{i}$ vectors, so that $z_{i,j}$ will denote the $j$-th coordinate of $z_{i}$. We will only use the symbols $j$ to index the vectors $z,z_{1},\ldots,z_{n}$. We define the functions $g(z)\triangleq\sum_{i}\beta_{i}(z^{\top}z_{i})^{q}$ and $h(z)\triangleq\sum_{i}\beta_{i}(z^{\top}z_{i})^{p}$, with Fourier coefficients $\hat{g}$, $\hat{h}$, respectively, and $g_{i}(z)=(z^{\top}z_{i})^{q}$, $h_{i}(z)=(z^{\top}z_{i})^{p}$ with Fourier coefficients $\hat{g}_{i}$, $\hat{h}_{i}$. We claim that for any $S\subseteq[d]$, $\hat{g}(S)\hat{h}(S)\geq 0$.

for some positive integer $c_{q,|S|}$ depending only on $q,|S|$. We obtained equation B.13 via symmetry and the fact that $(z^{S})^{2}=1$, $z_{j_{1}}^{a_{1}}\cdots z_{j_{k}}^{a_{k}}z_{i,j_{1}}^{a_{1}}\cdots z_{i,j_{k}}^{a_{k}}=1$, as they are squares of values in $\{-1,+1\}$. Note that $c_{q,|S|}=0$ for $|S|>q$. It follows that $\hat{g}(S)=c_{q,|S|}\sum_{i}\beta_{i}z_{i}^{S}$, and $\hat{h}(S)=c_{p,|S|}\sum_{i}\beta_{i}z^{S}_{i}$. Thus, $\hat{g}(S)\hat{h}(S)\geq 0\forall S$, which means by equation B.12, we get

B.2 Proof of Theorem 2.1

We now complete the proof of Theorem 2.1. Note that the kernel lower bound follows from B.1, so it suffices to upper bound the generalization error of the neural net solution.

We first invoke Theorem C.2 to conclude that with $\lambda=\textup{poly}(n)^{-1}$, the network $f^{\textup{NN}}(\cdot;\Theta_{\lambda})$ will have margin that is a constant factor approximation to the max-margin.

For neural nets with at least 4 hidden units, we now construct a neural net with a good normalized margin:

As this network has constant norm and margin 1, it has normalized margin $\Theta(1)$, and therefore the max neural net margin is $\Omega(1)$. Now we apply the generalization bound of Proposition D.1 to obtain

as desired. Choosing $\delta=n^{-5}$ gives the desired result. Combined with the Theorem B.1 lower bound on the kernel method, this completes the proof. ∎

B.3 Regression Setting

Let $f^{\textup{NN}}(\cdot;\Theta)$ be some two-layer neural network with $m$ hidden units parametrized by $\Theta$, as in Section 2. Define the $\lambda$-regularized squared error loss

with $\Theta_{\lambda,m}\in\operatorname*{arg\,min}_{\Theta}L_{\lambda,m}(\Theta)$. Suppose there exists a width-$m$ network that fits the data $(x_{i},y_{i})$ perfectly. Then as $\lambda\rightarrow 0$, $L_{\lambda,m}(\Theta_{\lambda,m})\rightarrow 0$ and $\|\Theta_{\lambda,m}\|_{2}\rightarrow\|\Theta^{\star,m}\|_{2}^{2}$, where $\Theta^{\star,m}$ is an optimizer of the following problem:

We note that $\lambda\|\Theta_{\lambda,m}\|_{2}^{2}\leq L_{\lambda,m}(\Theta_{\lambda,m})\leq L_{\lambda,m}(\Theta^{\star,m})=\lambda\|\Theta^{\star,m}\|_{2}^{2}$, so as $\lambda\rightarrow 0$, and also $\|\Theta_{\lambda,m}\|_{2}\leq\|\Theta^{\star,m}\|_{2}$. Now assume for the sake of contradiction that $\exists B$ with $\|\Theta_{\lambda,m}\|_{2}\leq B<\|\Theta^{\star,m}\|_{2}$ for arbitrarily small $\lambda$. We define

Note that $r^{\star}>0$ since $\Theta^{\star,m}$ is optimal for equation B.14. However, $L_{\lambda,m}\geq r^{\star}$ for arbitrarily small $\lambda$, a contradiction. Thus, $\lim_{\lambda\rightarrow 0}\|\Theta_{\lambda,m}\|_{2}^{2}=\|\Theta^{\star,m}\|_{2}^{2}$. ∎

This formulation is equivalent to a hard-margin optimization on “convex neural networks” . Bach also study optimization and generalization of convex neural networks. Using results from , our Theorem C.1 implies that optimizing weakly-regularized logistic loss over two-layer networks is equivalent to solving equation B.15 when the size of the hidden layer is at least $n+1$. Proposition B.11 states this deduction.The factor of $\frac{1}{2}$ is due the the relation that every unit-norm parameter $\Theta$ corresponds to an $\mu$ in the lifted space with $\|\mu\|=2$.

Appendix C Missing Material for Section 4

We will first state our analogue of Theorem 4.1 in the multi-class setting, as the proofs for the binary case will follow by reduction to the multi-class case.

We redefine the normalized margin of $\Theta_{\lambda}$ as:

Define the $\|\cdot\|$-max normalized margin as

and let $\Theta^{\star}$ be a parameter achieving this maximum. With these new definitions, our theorem statement for the multi-class setting is identical as the binary setting:

Assume $\gamma^{\star}>0$ in the multi-class setting with cross entropy loss. Then as $\lambda\rightarrow 0$, $\gamma_{\lambda}\rightarrow\gamma^{\star}$.

Since $L_{\lambda}$ is typically hard to optimize exactly for neural nets, we study how accurately we need to optimize $L_{\lambda}$ to obtain a margin that approximates $\gamma^{\star}$ up to a constant. We show that for $\lambda$ polynomial in $n,\gamma^{\star}$, and $l$, it suffices to find $\Theta^{\prime}$ achieving a constant factor $\alpha$ multiplicative approximation of $L_{\lambda}(\Theta_{\lambda})$ in order to have margin $\gamma^{\prime}$ satisfying $\gamma^{\prime}\geq\frac{\gamma^{\star}}{\alpha^{a/r}}$.

In the setting of Theorem C.1, suppose that we choose $\lambda=\exp(-(2^{r/a}-1)^{-a/r})\frac{(\gamma^{\star})^{r/a}}{n^{c}(l-1)^{c}}$ for sufficiently large $c$ (that only depends on $r/a$). For $\alpha\leq 2$, let $\Theta^{\prime}$ denote a $\alpha$-approximate minimizer of $L_{\lambda}$, so $L_{\lambda}(\Theta^{\prime})\leq\alpha L_{\lambda}(\Theta_{\lambda})$. Denote the normalized margin of $\Theta^{\prime}$ by $\gamma^{\prime}$. Then $\gamma^{\prime}\geq\frac{\gamma^{\star}}{10\cdot\alpha^{a/r}}.$

Towards proving Theorem C.1, we first prove that $L_{\lambda}$ does indeed have a global minimizer.

In the setting of Theorems C.1 and 4.1, $\operatorname*{arg\,min}_{\Theta}L_{\lambda}(\Theta)$ exists.

We will argue in the setting of Theorem C.1 where $L_{\lambda}$ is the multi-class cross entropy loss, because the logistic loss case is analogous. We first note that $L_{\lambda}$ is continuous in $\Theta$ because $f$ is continuous in $\Theta$ and the term inside the logarithm is always positive. Next, define $b\triangleq\inf_{\Theta}L_{\lambda}(\Theta)>0$. Then we note that for $\|\Theta\|>(b/\lambda)^{1/r}\triangleq M$, we must have $L_{\lambda}(\Theta)>b$. It follows that $\inf_{\|\Theta\|\leq M}L_{\lambda}(\Theta)=\inf_{\Theta}L_{\lambda}(\Theta)$. However, there must be a value $\Theta_{\lambda}$ which attains $\inf_{\|\Theta\|\leq M}L_{\lambda}(\Theta)$, because $\{\Theta:\|\Theta\|\leq M\}$ is a compact set and $L_{\lambda}$ is continuous. Thus, $\inf_{\Theta}L_{\lambda}(\Theta)$ is attained by some $\Theta_{\lambda}$. ∎

Next we present the following lemma, which says that as we decrease $\lambda$, the norm of the solution $\|\Theta_{\lambda}\|$ grows.

In the setting of Theorem C.1, as $\lambda\rightarrow 0$, we have $\|\Theta_{\lambda}\|\rightarrow\infty$.

To prove Theorem C.1, we rely on the exponential scaling of the cross entropy: $L_{\lambda}$ can be lower bounded roughly by $\exp(-\|\Theta_{\lambda}\|\gamma_{\lambda})$, but also has an upper bound that scales with $\exp(-\|\Theta_{\lambda}\|\gamma^{\star})$. By Lemma C.4, we can take large $\|\Theta_{\lambda}\|$ so the gap $\gamma^{\star}-\gamma_{\lambda}$ vanishes. This proof technique is inspired by that of Rosset et al. .

For any $M>0$ and $\Theta$ with $\gamma_{\Theta}\triangleq\min_{i}\left(f(x_{i};\bar{\Theta})-\max_{j\neq y_{i}}f(x_{i};\bar{\Theta})\right)$,

We can also apply $\sum_{j\neq y_{i}}\exp(M^{a}(f_{j}(x_{i};\Theta)-f_{y_{i}}(x_{i};\Theta)))\geq\max\exp(M^{a}(f_{j}(x_{i};\Theta)-f_{y_{i}}(x_{i};\Theta)))=\exp\gamma_{\Theta}$ in order to lower bound equation C.3 and obtain

Applying equation C.4 with $M=\|\Theta_{\lambda}\|$ and $\Theta=\Theta^{\star}$, noting that $\|\Theta^{\star}\|\leq 1$, we have:

Next we lower bound $L_{\lambda}(\Theta_{\lambda})$ by applying equation C.5,

Combining equation C.6 and equation C.7 with the fact that $L_{\lambda}(\Theta_{\lambda})\leq L_{\lambda}(\Theta^{\star}\|\Theta_{\lambda}\|)$ (by the global optimality of $\Theta_{\lambda}$), we have

Recall that by Lemma C.4, as $\lambda\rightarrow 0$, we have $\|\Theta_{\lambda}\|\rightarrow\infty$. Therefore, $\exp(-\|\Theta_{\lambda}\|^{a}\gamma^{\star}),\exp(-\|\Theta_{\lambda}\|^{a}\gamma_{\lambda})\rightarrow 0$. Thus, we can apply Taylor expansion to the equation above with respect to $\exp(-\|\Theta_{\lambda}\|^{a}\gamma^{\star})$ and $\exp(-\|\Theta_{\lambda}\|^{a}\gamma_{\lambda})$. If $\max\{\exp(-\|\Theta_{\lambda}\|^{a}\gamma^{\star}),\exp(-\|\Theta_{\lambda}\|^{a}\gamma_{\lambda})\}<1$, then we obtain

Finally, we have $\gamma_{\lambda}\leq\gamma^{\star}$ by definition of $\gamma^{\star}$. Hence, $\lim_{\lambda\rightarrow 0}\gamma_{\lambda}$ exists and equals $\gamma^{\star}$. ∎

For the sake of contradiction, we assume that $\exists C>0$ such that for any $\lambda_{0}>0$, there exists $0<\lambda<\lambda_{0}$ with $\|\Theta_{\lambda}\|\leq C$. We will determine the choice of $\lambda_{0}$ later and pick $\lambda$ such that $\|\Theta_{\lambda}\|\leq C$. Then the logits (the prediction $f_{j}(x_{i};\Theta)$ before softmax) are bounded in absolute value by some constant (that depends on $C$), and therefore the loss function $-\log\frac{\exp(f_{y_{i}}(x_{i};\Theta))}{\sum_{j=1}^{l}\exp(f_{j}(x_{i};\Theta))}$for every example is bounded from below by some constant $D>0$ (depending on $C$ but not $\lambda$.)

Taking a sufficiently small $\lambda_{0}$, we obtain a contradiction and complete the proof. ∎

C.2 Missing Proof for Optimization Accuracy

Choose $B\triangleq\left(\frac{1}{\gamma^{\star}}\log\frac{(l-1)(\gamma^{\star})^{r/a}}{\lambda}\right)^{1/a}$. We can upper bound $L_{\lambda}(\Theta^{\prime})$ by computing

Furthermore, it holds that $\|\Theta^{\prime}\|^{r}\leq\frac{L^{(UB)}}{\lambda}$. Now we note that

for sufficiently large $c$ depending only on $a/r$. Now using the fact that $\log(x)\geq\frac{x}{1+x}\ \forall x\geq-1$, we additionally have the lower bound $L_{\lambda}(\Theta^{\prime})\geq\frac{1}{n}\log(1+\exp(-\gamma^{\prime}\|\Theta^{\prime}\|^{a}))\geq\frac{1}{n}\frac{\exp(-\gamma^{\prime}\|\Theta^{\prime}\|^{a})}{1+\exp(-\gamma^{\prime}\|\Theta^{\prime}\|^{a})}$. Since $L^{(UB)}\leq 1$, we can rearrange to get

The middle inequality followed because $\frac{x}{1-x}$ is increasing in $x$ for $0\leq x<1$, and the last because $L^{(UB)}\leq\frac{1}{2n}$. Since $-\log 2nL^{(UB)}>0$ we can also apply the bound $\|\Theta^{\prime}\|^{r}\leq\frac{L^{(UB)}}{\lambda}$ to get

We will first bound $\clubsuit$. First note that

where the last inequality follows from the fact that $\frac{(\gamma^{\star})^{r/a}}{\lambda}\geq n^{c}(l-1)^{c}$ and $\alpha\leq 2$. Next, using the fact that $\log\frac{(\gamma^{\star})^{r/a}}{\lambda}\geq\frac{1}{(2^{r/a}-1)^{a/r}}$, we note that

Combining equation C.8 and equation C.9, we can conclude that

Finally, we note that if $1+\left(\log\frac{(l-1)(\gamma^{\star})^{r/a}}{\lambda}\right)^{r/a}$ is a sufficiently large constant that depends only on $a/r$ (which can be achieved by choosing $c$ sufficiently large) it will follow that $\heartsuit\leq\frac{1}{10}$. Thus, for sufficiently large $c\geq 5$, we can combine our bounds on $\clubsuit$ and $\heartsuit$ to get that

C.3 Proofs of Theorem 4.1

For completeness, we will now prove Theorem 4.1 via reduction to the multi-class cases. Recall that we now fit binary labels $y_{i}\in\{-1,+1\}$ (as opposed to indices in $[l]$) and redefine $f(\cdot;\Theta)$ to assign a single real-valued score (as opposed to a score for each label). We also work with the simpler logistic loss in equation 4.1.

Appendix D Generalization Bounds for Neural Nets

[Straightforward consequence of Golowich et al. [25, Theorem 1]] Suppose $\phi$ is 1-Lipschitz and $1$-positive-homogeneous. With probability at least $1-\delta$ over the draw of $X,Y$, for all depth-$q$ networks $f^{\textup{NN}}(\cdot;\Theta)$ separating the data with normalized margin $\gamma\triangleq\min_{i}y_{i}f^{\textup{NN}}(x_{i};\Theta/\|\Theta\|_{F})>0$,

where $\epsilon(\gamma)\triangleq\sqrt{\frac{\log\log_{2}\frac{4C}{\gamma}}{n}}+\sqrt{\frac{\log(1/\delta)}{n}}$ and $C=\max_{x\in\mathcal{X}}\|x\|_{2}$ is the max norm of the data. Note that $\epsilon(\gamma)$ is typically small, and thus the above bound mainly scales with $\frac{C}{\gamma q^{(q-1)/2}\sqrt{n}}$. Although the $\frac{1}{K^{(K-1)/2}}$ factor of equation D.1 decreases with depth $K$, the margin $\gamma$ will also tend to decrease as the constraint $\|\bar{\Theta}\|_{F}\leq 1$ becomes more stringent.

We note that Proposition D.1 is stated directly in terms of the normalized margin in order to maintain consistency in our notation, whereas prior works state their results using a ratio between unnormalized margin and norms of the weight matrices . We provide the proof in the following section.

We prove the generalization error bounds stated in Proposition D.1 via Rademacher complexity and margin theory.

Assume that our data $X,Y$ are drawn i.i.d. from ground truth distribution $p_{\rm{data}}$ supported on $\mathcal{X}\times\mathcal{Y}$. For some hypothesis class $\mathcal{F}$ of real-valued functions, we define the empirical Rademacher complexity $\hat{\mathfrak{R}}(\mathcal{F})$ as follows:

where $\epsilon_{i}$ are independent Rademacher random variables. For a classifier $f$, following the notation of Section 4.1 we will use $L(f)\triangleq\Pr_{(x,y)\sim p_{\rm{data}}}(yf(x)\leq 0)$ to denote the population 0-1 loss of the classifier $f$. The following classical theorem , bounds generalization error in terms of the Rademacher complexity and margin loss.

Let $(x_{i},y_{i})_{i=1}^{n}$ be drawn iid from $p_{\rm{data}}$. We work in the binary classification setting, so $\mathcal{Y}=\{-1,1\}$. Assume that for all $f\in\mathcal{F}$, we have $\sup_{x\in\mathcal{X}}|f(x)|\leq C$. Then with probability at least $1-\delta$ over the random draws of the data, for every $\gamma>0$ and $f\in\mathcal{F}$,

We will prove Proposition D.1 by applying the Rademacher complexity bounds of Golowich et al. with Theorem D.2.

Define the hypothesis class $\mathcal{F}_{q}$ over depth-$q$ neural networks by

Let $C\triangleq\sup_{x\in\mathcal{X}}\|x\|_{2}$. Recall that $L(\Theta)$ denotes the 0-1 population loss $L(f(\cdot;\Theta))$. Then for any $f(\cdot;\Theta)\in\mathcal{F}_{q}$ classifying the training data correctly with unnormalized margin $\gamma_{\Theta}\triangleq\min_{i}y_{i}f(x_{i};\Theta)>0$, with probability at least $1-\delta$,

Note the dependence on the unnormalized margin rather than the normalized margin.

We first claim that $\sup_{f(\cdot;\Theta)\in\mathcal{F}_{q}}\sup_{x\in\mathcal{X}}f(x;\Theta)\leq C$. To see this, for any $f(\cdot;\Theta)\in\mathcal{F}_{q}$,

Furthermore, by Theorem 1 of Golowich et al. , $\hat{\mathfrak{R}}(\mathcal{F}_{q})$ has upper bound

Thus, we can apply Theorem D.2 to conclude that for all $f(\cdot;\Theta)\in\mathcal{F}_{q}$ and all $\gamma>0$, with probability $1-\delta$,

In particular, by definition choosing $\gamma=\gamma_{\Theta}$ makes the first term on the LHS vanish and gives the statement of the lemma. ∎

To conclude Corollary 4.2, we apply the above on $\Theta_{\lambda,\mathcal{M}}$ and use Theorem 4.1.

Applying the statement of Proposition D.1, with probability $1-\delta$, for all $\lambda>0$,

Now we take the $\limsup$ of both sides as $\lambda\rightarrow 0$:

Appendix E Missing Proofs in Section 3

We first write our regularity assumptions on $\Phi$, $R$, and $V$ in more detail:

$R$ is convex, nonnegative, Lipschitz, and smooth: $\exists M_{R},C_{R}$ such that $\|\nabla^{2}R\|_{op}\leq C_{R}$, and $\|\nabla R\|_{2}\leq M_{R}$.

We state the version of Theorem 3.3 that collects these parameters:

Suppose that $\Phi$ and $V$ are 2-homogeneous and Assumptions E.1, E.2, and E.3 hold. Fix a desired error threshold $\epsilon>0$. Suppose that from a starting distribution $\rho_{0}$, a solution to the dynamics in equation 3.2 exists. Choose

Then it must hold that $\min_{0\leq t\leq t_{\epsilon}}L[\rho_{t}]-\inf_{\rho}L[\rho]\leq 2\epsilon$.

E.2 Proof Outline of Theorem E.4

In this section, we will provide an outline of the proof of Theorem E.4. We will fill in the missing details in Section E.3.

Choose any $t\leq\sigma B_{L}/b_{V}$. For all $0\leq t^{\prime}\leq t$, $W_{t^{\prime}}^{2}\leq\frac{L[\rho_{0}]+\sigma tB_{L}}{b_{V}-t\sigma B_{L}}$. In particular, for all $t\leq t_{\epsilon}$, we have $W_{t}\leq W_{\epsilon}$, where $W_{\epsilon}$ is defined as follows:

where $W_{\epsilon}$ is defined as in equation E.1.

The proof of Lemma E.6 intuitively holds because in order for $L^{\prime}[\rho_{t}](\bar{\theta})$ to change by a large amount, the gradient flow dynamics must have shifted $\rho_{t}$ by some amount, which would have resulted in some decrease of the objective $L[\rho_{t}]$. We will rely on the 2-homogeneity of $\Phi$ to formalize this argument.

Next, we will rely on the convexity of $L$: letting $\rho^{\star}$ be an $\epsilon$-approximate global optimizer of $L$, since $L$ is convex in $\rho$, we have

For the first case, we have the following guarantee that the objective decreases by a large amount:

For any time $t$ with $0\leq t\leq t_{\epsilon}$, we have

Lemma E.7 relies on the 2-homogeneity of $\Phi$ and $R$ and is proven via arguing that the gradient flow dynamics will result in a large shift in $\rho_{t}$ and therefore substantial decrease in loss.

For the second case, we will show that the $\sigma U^{d}$ noise term will cause mass to grow exponentially fast in this descent direction until we make progress in decreasing the objective.

Fix any $\tau>0$. Choose time interval length $l$ by

Here $c_{1}$ is the constant defined in Lemma E.6 and $c_{2}$ is defined by $c_{2}\triangleq\sqrt{k}M_{R}M_{\Phi}+M_{V}$.

Lemma E.8 is proven via the following argument: first, if $L^{\prime}[\rho_{t}](\bar{\theta})$ is close to $-\tau$ for all $t\in[t^{*},t^{*}+l]$, then from the 2-homogeneity of $\Phi$ and $R$, the mass of $\rho_{t}$ in the neighborhood around $\bar{\theta}$ will grow exponentially fast, leading to a violation of Lemma E.5. (Because of the uniform noise injected into the gradient flow dynamics, $\rho_{t}$ will always have some mass in the neighborhood of $\bar{\theta}$ to start with.) Thus, it follows that $L^{\prime}[\rho_{t}](\bar{\theta})$ must change by at least $\tau/4$, allowing us to invoke Lemma E.6 to argue that the objective must drop.