# Plateau in Monotonic Linear Interpolation — A "Biased" View of Loss
Landscape for Deep Networks

Xiang Wang†, Annie N. Wang§, Mo Zhou†, Rong Ge†
Department of Computer Science
Duke University, USA
†{xwang,mozhou,rongge}<EMAIL_ADDRESS>
###### Abstract

Monotonic linear interpolation (MLI) — on the line connecting a random
initialization with the minimizer it converges to, the loss and accuracy are
monotonic — is a phenomenon that is commonly observed in the training of
neural networks. Such a phenomenon may seem to suggest that optimization of
neural networks is easy. In this paper, we show that the MLI property is not
necessarily related to the hardness of optimization problems, and empirical
observations on MLI for deep neural networks depend heavily on the biases. In
particular, we show that interpolating both weights and biases linearly leads
to very different influences on the final output, and when different classes
have different last-layer biases on a deep network, there will be a long
plateau in both the loss and accuracy interpolation (which existing theory of
MLI cannot explain). We also show how the last-layer biases for different
classes can be different even on a perfectly balanced dataset using a simple
model. Empirically we demonstrate that similar intuitions hold on practical
networks and realistic datasets.

##  1 Introduction

Deep neural networks can often be optimized using simple gradient-based
methods, despite the objectives being highly nonconvex. Intuitively, this
suggests that the loss landscape must have nice properties that allow
efficient optimization. To understand the properties of loss landscape,
Goodfellow et al. (2014) studied the linear interpolation between a random
initialization and the local minimum found after training. They observed that
the loss interpolation curve is monotonic and approximately convex (see the
MNIST curve in Figure 1) and concluded that these tasks are easy to optimize.
However, other recent empirical observations, such as Frankle (2020) observed
that for deep neural networks on more complicated datasets, both the loss and
the error curves have a long plateau along the interpolation path, i.e., the
loss and error remain high until close to the optimum (see the CIFAR-10 curve
in Figure 1). Does the long plateau along the linear interpolation suggest
these tasks are harder to optimize? Not necessarily, since the hardness of
optimization problems does not need to be related to the shape of
interpolation curves (see examples in Appendix A).

In this paper we give the first theory that explains the plateau in both loss
and error interpolations. We attribute the plateau to simple reasons as the
bias terms, the network initialization scale and the network depth, which may
not necessarily be related to the difficulty of optimization.

Note that there are many different theories for the optimization of
overparametrized neural networks, in particular the neural tangent kernel
(NTK) analysis (Jacot et al., 2018; Du et al., 2018; Allen-Zhu et al., 2019;
Arora et al., 2019) and mean-field analysis (Chizat & Bach, 2018; Mei et al.,
2018). However they don’t explain the plateau in both loss and error
interpolations. For NTK regime, the network output is nearly linear in the
parameters and the loss interpolation curve is monotonically decreasing and
convex — no plateau in the loss interpolation. Mean-field regime often uses a
smaller initialization on a homogeneous neural network (as considered in
Chizat & Bach (2018); Mei et al. (2018)). In this case, the interpolated
network output is basically a scaled version of the network output at the
minimum and has same label predictions — no plateau in the error interpolation
curve.

Figure 1: Loss interpolation curve and error interpolation curve for a four-
layer fully-connected network (FCN4) on MNIST and for VGG16 on CIFAR-10.

###  1.1 Our results

Our theoretical results consist of two parts. In the first part (see Section
3), we give a plausible explanation for the plateau in both the loss and error
curves.

######  Claim 1 (informal).

If a deep network has a relatively small initialization, and its last-layer
biases are significantly different for different classes, then both the loss
and error curves will have a plateau. The length of the plateau is longer for
a deeper network.

We formalize this claim in Theorem 1. For intuition, consider an $r$-layer
neural network that only has bias on the last layer, and consider Xavier
initialization (Glorot & Bengio, 2010) which typically gives small output and
zero bias. If we consider the $\alpha$-interpolation point (with coefficient
$\alpha$ for the minimum and $(1-\alpha)$ for the initialization), then the
weight “signal” from the minimum scales as $\alpha^{r}$ (as it is the product
of $r$ layers) while the bias scales as $\alpha$. As illustrated in Figure 2
(right), when $r$ is large and there is a difference in biases, the bias will
dominate, which creates a plateau in error. For the loss, one can also show
that the weight signal is near 0 for small $\alpha$, so the network output is
dominated by the biases and the loss cannot beat the random guessing at
initialization. Note that this explanation for the plateau does not have any
implication on the hardness of optimization.

However, why would the last-layer biases be different for different classes,
especially in cases when the biases are initialized as zeros and all classes
are balanced? In the second part (see Section 4), we focus on a simple model
that we call $r$-homogeneous-weight network. This is a two-layer network whose
$i$-th output is $\left\langle W_{i,:},x\right\rangle^{r}+b_{i}$, where
$x\in{\mathbb{R}}^{d}$ is the network input, $W_{i,:}\in{\mathbb{R}}^{d}$ is
the weight vector and $b_{i}\in{\mathbb{R}}$ is the bias (see Figure 2
(left)). Our simple model simulates a depth-$r$ ReLU/linear network with bias
on the output layer, in the sense that the signal is $r$-homogeneous while the
bias is $1$-homogeneous in the parameters. Under this model we can show that:

######  Claim 2 (informal).

For the $r$-homogeneous-weight network on a simple balanced dataset, the class
that is learned last has the largest bias.

Here, a class is learned when all the samples in this class get classified
correctly with good confidence. We basically show that once a class gets
learned, the bias associated with this class starts decreasing and eventually
the class that is learned last has the largest bias. We formalize this claim
in Theorem 2.

In Section 5, we verify these ideas empirically on fully-connected networks
for MNIST (Deng, 2012), Fashion-MNIST (Xiao et al., 2017) and on VGG-16
(Simonyan & Zisserman, 2014) for CIFAR-10, CIFAR-100 (Krizhevsky et al.,
2009). We first show that if we train a neural network without using any bias,
then the error curve has much shorter plateau or no plateau at all. Even for
networks that are trained normally with biases, we design a homogeneous
interpolation scheme for biases to make sure that both biases and weights are
$r$-homogeneous. Such an interpolation indeed significantly shortens the
plateau for the error. We also show that decreasing the initialization scale
or increasing the network depth can produce a longer plateau in both the error
and loss curves. Finally, we show that the bias is correlated with the
ordering in which the classes are being learned for small datasets, which
suggests that even though the model we consider in the convergence analysis is
simple, it captures some of the behavior in practice.

###  1.2 Related works

There are two major lines of work studying interpolation between different
points for neural networks, one on monotonic linear interpolation that
interpolates the initial network and the learned network, and the other on
mode connectivity that connects two learned networks.

Monotonic linear interpolation. Goodfellow et al. (2014) first studied the
linear interpolation between the network at initialization and the network
after training on MNIST. Frankle (2020) extended the experiments to modern
networks on CIFAR-10 and ImageNet and found that though the loss/error is
still monotonically non-increasing along the path, it remains high until close
to the optimum. Lucas et al. (2021) showed that MLI holds when the network
output curve along the interpolation path is close to linear (measured by
Gaussian length). However, the Gaussian length can only be formally controlled
in the NTK regime.

Mode connectivity. Mode connectivity considers the interpolation between two
learned networks (modes) found by SGD. In general, a linear interpolation
between two different local minima crosses regions of high loss (Goodfellow et
al., 2014). Surprisingly, Draxler et al. (2018) and Garipov et al. (2018)
observed that local minima found by SGD from different initializations can be
connected via a piece-wise linear path of low loss. Frankle et al. (2020) and
Fort et al. (2020) observed that local minima trained from the same
initialization can also be connected using a linear path. Freeman & Bruna
(2016); Venturi et al. (2018); Nguyen (2019; 2021); Kuditipudi et al. (2019);
Shevchenko & Mondelli (2020); Nguyen et al. (2021) gave several theoretical
explanations for this phenomenon.

##  2 Preliminaries

Figure 2: (Left) Our $r$-homogeneous-weight model with $f_{i}(x)=\left\langle
W_{i,:},x\right\rangle^{r}+b_{i}$. (Right) The comparison between interpolated
bias $\alpha(b^{(T)}_{k}-b^{(T)}_{i})$ and interpolated weights signal
$\left\langle W^{[\alpha]}_{i,:},x\right\rangle^{r}.$

We first formally define the linear interpolation between the network at
initialization and the network after training. Then we describe the notations
that we will use in the paper.

Linear interpolation: Consider a network with parameters
$\theta\in{\mathbb{R}}^{p}$. Suppose the network is initialized with
parameters $\theta^{(0)}$ and it converges to $\theta^{(T)}.$ A _linear
interpolation_ is constructed by setting the parameters
$\theta^{[\alpha]}=(1-\alpha)\theta^{(0)}+\alpha\theta^{(T)}$ for
$\alpha\in[0,1].$ The _loss interpolation curve_ is defined as
$\gamma_{\text{loss}}(\alpha):[0,1]\rightarrow{\mathbb{R}}$ such that
$\gamma_{\text{loss}}(\alpha)$ is the training loss of the network at
$\theta^{[\alpha]}.$ Similarly, the _error interpolation curve_ is defined as
$\gamma_{\text{error}}(\alpha):[0,1]\rightarrow[0,1]$ with
$\gamma_{\text{error}}(\alpha)$ as the training error of the network at
$\theta^{[\alpha]}.$ Here, the training error is simply the ratio of training
samples that get classified incorrectly by the network.

Notations:  We use $[k]$ to denote the set $\\{1,2,\cdots,k\\}.$ We use
$\mathcal{N}(0,\delta^{2})$ to denote the Gaussian distribution with mean zero
and variance $\delta^{2}.$ We use $\left\|\cdot\right\|$ to denote the
$\ell_{2}$ norm for a vector or the spectral norm for a matrix. For any non-
zero vector $v,$ we use $\bar{v}$ to denote $v/\left\|v\right\|.$ We use
$O(\cdot),\Theta(\cdot),\Omega(\cdot)$ to hide the dependency on constant
factors and use
$\widetilde{O}(\cdot),\widetilde{\Theta}(\cdot),\widetilde{\Omega}(\cdot)$ to
hide the dependency on poly-logarithmic factors.

For any time $t$, we use $\theta^{(t)},f^{(t)}$ to denote the parameters and
the network at time $t$. For any $\alpha\in[0,1],$ we use
$\theta^{[\alpha]},f^{[\alpha]}$ to denote the $\alpha$ interpolation point,
which means $\theta^{[\alpha]}:=(1-\alpha)\theta^{[0]}+\alpha\theta^{[T]}$ and
$f^{[\alpha]}$ is the network with parameters $\theta^{[\alpha]}.$

##  3 Plateau for loss and error interpolations

We prove that the long plateau exists in the loss and error curves when the
initialization is small and the network is deep on fully-connected networks.
The detailed proof can be found in Appendix B.3.

We consider an $r$-layer fully-connected neural network with $r$ at least
three. Given input $x\in{\mathbb{R}}^{n_{0}},$ the network output is

$\displaystyle
g(x):=V_{r}\sigma\left(V_{r-1}\cdots\sigma(V_{1}x)\cdots\right)+b,$ (1)

where $V_{i}\in{\mathbb{R}}^{n_{r}\times n_{r-1}}$ for each layer $i\in[r]$
and $b\in{\mathbb{R}}^{n_{r}}.$ Here the activation function
$\sigma\left(\cdot\right)$ can be either identity function or ReLU function.
The output layer width equals to the number of classes, i.e., $n_{r}=k.$ We
use $L\left(\left\\{V_{i}\right\\},b\right)$ to denote the sum of cross
entropy loss over all samples.

For the biases, we initialize them as zeros and assume after training there
exists a gap between the largest bias and the second largest, which also holds
empirically (see Figure 8). Note this bias gap is essential for the plateau in
the error interpolation. If all the biases are equal in the trained network,
the logits for different classes only differ by the weights signal and the
interpolated network has same label predictions as the trained network.

######  Assumption 1 (Bias Gap).

Choosing $i^{*}\in\arg\max_{i\in[k]}b_{i}^{(T)},$ we have
$b_{i^{*}}^{(T)}-\max_{i\neq i^{*}}b_{i}^{(T)}>0.$ Without loss of generality,
we assume that $b^{(T)}_{k}>\max_{i\in[k-1]}b^{(T)}_{i}$. We denote
$\Delta_{\min}:=b^{(T)}_{k}-\max_{i\in[k-1]}b_{i}^{(T)}$ and
$\Delta_{\max}:=b^{(T)}_{k}-\min_{i\in[k-1]}b_{i}^{(T)}.$

Then, we show both the loss and error interpolation curves have a long plateau
in Theorem 1.

######  Theorem 1.

Suppose the network is defined as in Equation (1) and suppose the weights
satisfy $\left\|V^{(0)}_{i}\right\|\leq\delta,\left\|V^{(T)}_{i}\right\|\leq
V_{\max}\ $ for all layers $i\in[r].$ On a $k$-class balanced dataset whose
inputs have $\ell_{2}$ norm at most $1$, if Assumption 1 holds, for any
$\epsilon>0,$ as long as
$\delta<\min\left(\frac{\epsilon^{1/r}}{r},\frac{1}{r^{2}},\left(\frac{1}{2e}\right)^{\frac{2}{r-2}}\right)$,
there exist
$\alpha_{1}=\frac{\delta}{\Delta_{\min}},\alpha_{2}=\left(\frac{1}{1+\sqrt{\delta}}\right)^{\frac{r}{r-1}}\left(\frac{\Delta_{\min}}{2V_{\max}^{r}}\right)^{\frac{1}{r-1}}$
and $\alpha_{3}=\frac{\epsilon^{1/r}}{V_{\max}}$ such that

  1. 1.

for all $\alpha\in[\alpha_{1},\alpha_{2}],$ the error is $1-1/k$;

  2. 2.

for all $\alpha\in[0,\alpha_{3}],$ we have $\log
k-2e\epsilon\leq\frac{1}{N}L\left(\left\\{V^{[\alpha]}_{i}\right\\},b^{[\alpha]}\right)\leq\log
k+\alpha\Delta_{\max}+2e\epsilon,$ where $N$ is the number of training
examples.

The above theorem shows that for all $\alpha\in[\alpha_{1},\alpha_{2}],$ the
error remains at $1-1/k$ that is the same as random guessing. We skip the very
short initial region $[0,\frac{\delta}{\Delta_{\min}}]$ since the bias is very
small and the error can be unpredictable due to the randomness in initial
weights. When initialization scale $\delta$ is small, this error plateau
region is roughly $[0,(\frac{\Delta_{\min}}{2V_{\max}^{r}})^{\frac{1}{r-1}}]$.
Empirically, $\frac{\Delta_{\min}}{2V_{\max}^{r}}$ is smaller than $1$ and
does not change much when depth increases. So the plateau becomes longer in a
deeper network.

Intuitively, the plateau in error curve is there because for a small
initialization, the output is close to
$\alpha^{r}V_{r}^{(T)}\sigma\left(V_{r-1}^{(T)}\cdots\sigma(V_{1}^{(T)}x)\cdots\right)+\alpha
b^{(T)}$. When $\alpha$ is not large enough $\alpha^{r}$ is much smaller than
$\alpha$, so for every class $i\neq k,$ the first term (signal part) cannot
overcome the bias gap $\alpha(b^{(T)}_{k}-b^{(T)}_{i})$. This implies that all
samples are predicted as class $k$ and the error is $1-1/k.$

We also show that the average loss cannot be lower than $\log k-2e\epsilon$
when $\alpha\leq\frac{\epsilon^{1/r}}{V_{\max}}.$ Note a small random
initialization can achieve a loss of approximately $\log k$. Usually the bias
gap $\Delta_{\max}$ in practice is not very large, so the loss curve remains
nearly flat during this interpolation region. Again, the loss plateau is
becoming longer when depth $r$ increases. This is because the weights signal
remains near 0 for a larger range of $\alpha$.

##  4 Training dynamics for creating a bias gap

In this section, we explain how the gradient flow dynamics generates a bias
gap on a balanced dataset by analyzing a simple model. Below, we first define
the network model, training dataset and optimization procedure for our
analysis.

$r$-homogeneous-weight network: We consider a two-layer and $k$-output neural
network with activation function $\sigma(z):=z^{r},$ where $r$ is a positive
constant that is at least three. As illustrated in Figure 2 (left), under
input $x\in{\mathbb{R}}^{d},$ the $i$-th output $f_{i}(x)$ is $\left\langle
W_{i,:},x\right\rangle^{r}+b_{i},$ where the weight vector
$W_{i,:}\in{\mathbb{R}}^{d}$ is the $i$-th row of weight matrix
$W\in{\mathbb{R}}^{k\times d}$ and $b_{i}\in{\mathbb{R}}$ is the $i$-th entry
of vector $b\in{\mathbb{R}}^{k}.$ In output $f_{i}(x)$, we call $\left\langle
W_{i,:},x\right\rangle^{r}$ the signal since it is input-dependent and call
$b_{i}$ the bias.

Dataset: We consider a $k$-class balanced dataset, with $k$ as a constant. We
denote the whole dataset as $\mathcal{S}$ and denote the subset for each class
$i\in[k]$ as $\mathcal{S}_{i}$. Each subset $\mathcal{S}_{i}$ has exactly
$N/k$ samples and each sample $x\in{\mathbb{R}}^{d}$ is independently sampled
as $v_{i}+\xi,$ where the noise $\xi\sim\mathcal{N}(0,\frac{\sigma^{2}}{d}I).$
To differentiate the noise terms among different samples, we denote the noise
associated with sample $x$ as $\xi_{x}.$ We assume all $v_{i}$’s are
orthonormal; without loss of generality, we assume $v_{i}=e_{i}$ for each
class $i.$ Here, we assume the orthogonal features to facilitate the
convergence analysis beyond the NTK regime, following previous works (Allen-
Zhu & Li, 2020; Ge et al., 2021).

Optimization: We initialize each entry in weight matrix $W$ by independently
sampling from Gaussian distribution $\mathcal{N}(0,\delta^{2})$ and then
taking the absolute value 111In the Xavier initialization, each entry in
weight matrix $W$ is sampled from $\mathcal{N}(0,1/d),$ so we can think of
$\delta^{2}=1/d$ that is small when input dimension $d$ is large.. Our
analysis can be trivially generalized to standard Gaussian initialization
(without taking absolute value) when $r$ is an even integer. We initialize all
bias terms as zeros. We use cross-entropy loss
$L(W,b)=\sum_{i\in[k]}\sum_{x\in\mathcal{S}_{i}}-\log\left(\frac{\exp\left(f_{i}(x)\right)}{\sum_{j\in[k]}\exp\left({f_{j}(x)}\right)}\right),$
and run gradient flow on $\frac{k}{N}L(W,b)$ for time $T.$ Our analysis can
also be extended to gradient descent with a small step size.

Next we show that running gradient flow from a small initialization can
converge to a model with zero error and constant bias gap.

######  Theorem 2.

Suppose the neural network, dataset and optimization procedure are as defined
in Section 4. Suppose initialization scale $\delta\leq\Theta(1)$, noise level
$\sigma\leq\widetilde{\Theta}(1)$, dimension
$d\geq\widetilde{\Theta}(1/\delta^{2r-2})$ and number of samples
$N\geq\widetilde{\Theta}(1/\delta^{r-1})$, with probability at least $0.99$ in
the initialization, there exists time $T=\Theta(\log(1/\delta)/\delta^{r-2})$
such that we have

  1. 1.

zero error: for all different $i,j\in[k]$ and for all $x\in\mathcal{S}_{i}$,
$f^{(T)}_{i}(x)\geq f^{(T)}_{j}(x)+\Omega(1);$

  2. 2.

bias gap: $b_{i^{*}}^{(T)}-\max_{i\neq i^{*}}b_{i}^{(T)}\geq\Omega(1)\text{
with }i^{*}=\arg\max_{i\in[k]}b^{(T)}_{i}.$

Due to space limit, we only give a proof sketch here and leave the detailed
proof in Appendix C. Since our dataset is perfectly balanced, it might seem
surprising that gradient flow learns diverse biases. We can compute the time
derivative on the bias,
$\dot{b}_{i}=1-\frac{k}{N}\sum_{x\in\mathcal{S}}u_{i}(x)$, where $u_{i}(x)$ is
the softmax output for class $i,$ that is
$\frac{\exp(f_{i}(x))}{\sum_{i^{\prime}\in[k]}\exp(f_{i^{\prime}}(x))}.$ At
the beginning, all logits are small, we have $u_{i}(x)\approx 1/k$ and
$\dot{b}_{i}\approx 0.$ If all the samples are learned at the same time, we
have $u_{i}(x)\approx 1,u_{i}(x^{\prime})\approx 0$ for
$x\in\mathcal{S}_{i},x^{\prime}\in\mathcal{S}\setminus\mathcal{S}_{i}$, which
again leads to $\dot{b}_{i}\approx 0.$

On the other hand, we can consider what happens if all samples in one class
(e.g., class $i$) are learned before any sample in any other class (e.g.,
class $j$) is learned 222This is indeed possible since all samples of one
class only differ in the noise terms in our setting. In the analysis, we can
show that the noise term has negligible contribution to the network output and
all samples in one class are learned almost at the same time.. In this case we
have

$\displaystyle\dot{b}_{i}=1-\frac{k}{N}\sum_{x\in\mathcal{S}_{i}}u_{i}(x)-\frac{k}{N}\sum_{x\in\mathcal{S}\setminus\mathcal{S}_{i}}u_{i}(x)\approx
1-\frac{k}{N}\cdot\frac{N}{k}\cdot
1-\frac{k}{N}\cdot\frac{N(k-1)}{k}\cdot\frac{1}{k}=-\frac{k-1}{k},$
$\displaystyle\dot{b}_{j}=1-\frac{k}{N}\sum_{x\in\mathcal{S}_{i}}u_{j}(x)-\frac{k}{N}\sum_{x\in\mathcal{S}\setminus\mathcal{S}_{i}}u_{j}(x)\approx
1-\frac{k}{N}\cdot\frac{N}{k}\cdot
0-\frac{k}{N}\cdot\frac{N(k-1)}{k}\cdot\frac{1}{k}=\frac{1}{k},$

where for any learned sample $x\in\mathcal{S}_{i},$ we have $u_{i}(x)\approx
1,u_{j}(x)\approx 0$; for any not yet learned sample
$x\in\mathcal{S}\setminus\mathcal{S}_{i},$ we have $u_{i}(x),u_{j}(x)\approx
1/k.$ The above calculation shows that $b_{i}$ starts to decrease and all the
other bias terms increase. Generalizing this intuition, we show that
$b_{i^{\prime}}$ starts to decrease whenever class $i^{\prime}$ is learned,
and the class that is learned last will have the largest bias.

As the weights are initialized randomly, by standard anti-concentration, one
can argue that there is a gap between $W^{(0)}_{i,i}$’s. Without loss of
generality, we assume $W^{(0)}_{1,1}>W^{(0)}_{2,2}>\cdots>W^{(0)}_{k,k}$. The
initial difference in the weights will lead to different classes being learned
at different time. We show that by doing induction on the following hypothesis
through training:

Figure 3:  The training dynamics of $W$ and $b$ in a four-class example.

######  Proposition 1 (Induction Hypothesis).

In the same setting of Theorem 2, with probability at least 0.99 in
initialization, there exist time points
$0=:s_{1}<t_{1}<s_{2}<t_{2}<\cdots<s_{k-1}<t_{k-1}<s_{k}:=T$ with
$t_{i}-s_{i}=\Theta(\log(1/\delta)/\delta^{r-2})$ and
$s_{i+1}-t_{i}=\Theta(1)$ for $i\in[k-1]$ such that for any
$t\in[s_{i},s_{i+1}],$

  1. 1.

(classes not yet learned) for any class $j,j^{\prime}\geq i+1,$ we have (1)
$b^{(t)}_{j}\geq\max_{i^{\prime}\in[k]}b^{(t)}_{i^{\prime}}-O(\delta^{r})$,
(2) $\left|b^{(t)}_{j}-b^{(t)}_{j^{\prime}}\right|\leq O(\delta^{r})$ and (3)
$W^{(t)}_{j,j}\leq O(\delta)$;

  2. 2.

(classes already learned) for any class $j\leq i-1$, we have (1)
$b^{(t)}_{j}\leq\max_{i^{\prime}\in[k]}b^{(t)}_{i^{\prime}}-\Omega(1)$, (2)
$f^{(t)}_{j}\left(x\right)\geq
f^{(t)}_{i^{\prime}}\left(x\right)+\Omega(1)\text{ for }i^{\prime}\neq
j,x\in\mathcal{S}_{j}$ and (3) $W^{(t)}_{j,j}\geq\Omega(1)$;

  3. 3.

(parameters movement) (1) for any
$j\in[k],\Theta(\delta)=W^{(0)}_{j,j}<W^{(t)}_{j,j},$ (2) for any distinct
$j,j^{\prime}\in[k],0<W^{(t)}_{j,j^{\prime}}\leq O(\delta)$ and (3) for any
$j,j^{\prime}\in[k]$ and any $x\in\mathcal{S}_{j^{\prime}},\left|\left\langle
W^{(t)}_{j,:},\xi_{x}\right\rangle\right|\leq\min\left(O(\delta),W^{(t)}_{j,j^{\prime}}\right).$

This proposition shows that gradient flow learns $k$ classes one by one, from
class $1$ to class $k$. More precisely, each class $i$ is learned during time
$[s_{i},s_{i+1}].$ All the not yet learned classes $j\geq i+1$ have close to
maximum biases and their weights $W^{(t)}_{j,j}$’s are small. All the already
learned classes $j\leq i-1$ have small biases and large weights
$W^{(t)}_{j,j}$’s. For the parameters movement, we know that all the diagonal
entries $W^{(t)}_{j,j}$’s are larger than the initialization and all the off-
diagonal entries $W^{(t)}_{j,j^{\prime}}$’s are only $O(\delta).$ The
correlation between the weights and noise terms also remains small.

When learning class $i$ during time $[s_{i},s_{i+1}],$ the weight
$W^{(t)}_{i,i}$ slowly grows to a small constant in $[s_{i},t_{i}]$ and then
quickly grows large in $[t_{i},s_{i+1}.]$ As a result, all
$x\in\mathcal{S}_{i}$ become classified correctly. During the same time,
$b^{(t)}_{i}$ decreases and becomes smaller than the largest bias by at least
a constant. At the end time $T=s_{k}$, although $W^{(T)}_{k,k}$ remains small,
all $x\in\mathcal{S}_{k}$ are also classified correctly because $b^{(T)}_{k}$
is the largest bias. See an illustration of this learning process in Figure 3.

Although we consider a simple neural network and data distribution, the
analysis for the training dynamics is still non-trivial. There are three major
challenges in our proof: (1) How to ensure that class $i+1$ is learned much
later than class $i$? (2) For any class $j$ that has not been learned, how to
maintain that its bias is close to the maximum? (3) For any learned class $j,$
how to maintain the large bias gap from the top bias? Next, we give the proof
ideas for these questions. Since all the off-diagonal entries and correlations
with noise terms in $W^{(t)}$ are negligible, in our proof we can essentially
focus on the movement of $W^{(t)}_{i,i}$’s and $b^{(t)}_{i}$’s.

Lower bounding $s_{i+1}-s_{i}$. During time $[s_{i},t_{i}]$, the dynamics of
$W^{(t)}_{i,i}$ is similar as in the tensor power method (Allen-Zhu & Li,
2020; Ge et al., 2021). The initial gap between $W^{(0)}_{i,i}$ and
$W^{(0)}_{j,j}$ ensures that when $W^{(t_{i})}_{i,i}$ rises to a small
constant, $W^{(t_{i})}_{j,j}$ is still $O(\delta)$ for all $j\geq i+1.$ Then
after constant time $s_{i+1}-t_{i},$ $W^{s_{i+1}}_{j,j}$ is still $O(\delta)$
since the increasing rate of $W^{(t)}_{j,j}$ is merely $O(\delta^{r-1}).$

Bias for classes that are not learned. For $j\geq i+1,$ we maintain that
$b^{(t)}_{j}\geq\max_{i^{\prime}\in[k]}b^{(t)}_{i^{\prime}}-O(\delta^{r})$.
First, we use the below lemma to show biases for any two classes
$j,j^{\prime}\geq i+1$ remain close.

######  Lemma 1 (Coupling Biases).

Assuming $W_{j^{\prime},j^{\prime}},W_{j,j}\leq O(\delta)$ and
$b_{j^{\prime}},b_{j}\geq\max_{i^{\prime}\in[k]}b_{i^{\prime}}-O(\delta^{r})$,
we have $\dot{b}_{j^{\prime}}-\dot{b}_{j}>0\text{ if
}b_{j^{\prime}}-b_{j}\leq-\mu\delta^{r}$, and
$\dot{b}_{j^{\prime}}-\dot{b}_{j}<0\text{ if
}b_{j^{\prime}}-b_{j}\geq+\mu\delta^{r}$ for some positive constant $\mu.$

Second we show that any already learned or being learned class $j^{\prime}\leq
i$ cannot have bias much larger than any class $j\geq i+1$ not yet learned.

######  Lemma 2 (Bias Gap Control I).

For any different $j^{\prime},j\in[k]$, if $W_{j^{\prime},j^{\prime}}\geq
W_{j,j},W_{j,j}\leq O(\delta)$ and $b_{j^{\prime}}-b_{j}\geq
O(\delta^{r}),b_{j}\geq\max_{i^{\prime}\in[k]}b_{i^{\prime}}-O(\delta^{r}),$
we have $\dot{b}_{j^{\prime}}-\dot{b}_{j}<0.$

Bias for learned classes. At time $s_{j+1},$ we can prove that
$1-u_{j}^{(s_{j+1})}(x)\leq C_{1}$ for all $x\in\mathcal{S}_{j}$ and
$b_{j}^{(s_{j+1})}-b_{k}^{(s_{j+1})}\leq-C_{2}$. According to the below lemma,
we can ensure that $b^{(t)}_{j}-b^{(t)}_{k}\leq-C_{2}$ for any $t\geq
s_{j+1}.$

######  Lemma 3 (Bias Gap Control II).

There exist small positive constants $C_{1},C_{2}$ such that for any
$j\in[k-1]$ and any $x\in\mathcal{S}_{j}$, if $1-u_{j}(x)\leq
C_{1},W_{k,k}\leq O(\delta)$ and $b_{j}-b_{k}\geq-C_{2},$ we have
$\dot{b}_{j}-\dot{b}_{k}<-\Omega(1).$

###  4.1 Plateau and monotonicity for $r$-homogeneous-weight network

Now assuming the network at initialization and after training satisfies the
properties described in Theorem 2 and Proposition 1, we can prove a tighter
bound on the plateau region and also show the monotonicity in error and loss
curve. See the complete proofs in Appendix B.1 and Appendix B.2.

Same as in Assumption 1, we use $\Delta_{i}$ to denote the bias gap
$b^{(T)}_{k}-b^{(T)}_{i}$ for $i\in[k-1]$ and denote
$\Delta_{\min}:=\min_{i\in[k-1]}\Delta_{i}$ and
$\Delta_{\max}=\max_{i\in[k-1]}\Delta_{i}$. For the weights, we denote
$W_{\min}=\min_{i\in[k-1]}W^{(T)}_{i,i}$ and
$W_{\max}=\max_{i\in[k]}W^{(T)}_{i,i}.$ We denote
$R_{\min}=\min_{i\in[k-1]}\Delta_{i}/[W^{(T)}_{i,i}]^{r}$,
$R_{\max}=\max_{i\in[k-1]}\Delta_{i}/[W^{(T)}_{i,i}]^{r}.$ Below, we show the
plateau and monotonicity of loss and error interpolations in Theorem 3.

######  Theorem 3.

Suppose the neural network, dataset and optimization procedure are as defined
in Section 4. Suppose the network at initialization and after training
satisfies the properties described in Theorem 2 and Proposition 1. For any
$\epsilon\in(0,1),$ suppose
$\delta\leq\min(\Theta(\epsilon^{1/r}),\Theta(R_{\min}^{\frac{1}{r-1}}\Delta_{\min}^{1/r}),\Theta((\frac{W_{\min}}{W_{\max}})^{\frac{2r}{r-2}})).$
There exist
$\alpha_{1}=\frac{\delta}{\Delta_{\min}},\alpha_{2}=(\frac{1}{1+O(\sqrt{\delta})})^{\frac{r}{r-1}}R_{\min}^{\frac{1}{r-1}},\alpha_{3}=\frac{\epsilon^{1/r}}{W_{\max}}$
and
$\alpha_{4}=\left(1+O(\delta)\right)^{\frac{1}{r-1}}\left(\frac{R_{\max}}{r}\right)^{\frac{1}{r-1}}$
such that

  1. 1.

for all $\alpha\in[\alpha_{1},\alpha_{2}],$ the error is $1-1/k;$ for all
$\alpha\in[\alpha_{1},1],$ the error is non-increasing;

  2. 2.

for all $\alpha\in[0,\alpha_{3}]$, we have $\log
k-e\epsilon\leq\frac{1}{N}L(W^{[\alpha]},b^{[\alpha]})\leq\log
k+\alpha\Delta_{\max}+e\epsilon;$ for all $\alpha\in[\alpha_{4},1]$, the loss
is strictly monotonically decreasing.

The analysis for the plateau is very similar as in Theorem 1 since a
$r$-homogeneous-weight network is similar to a depth-$r$ fully connected
neural network with only last-layer biases in the sense that the weights are
$r$-homogeneous while the (last-layer) bias is $1$-homogeneous. For the error
plateau, we prove a tighter bound on the right boundary $\alpha_{2}$ than in
Theorem 1. We also show the error is non-increasing for
$\alpha\in\left[\delta/\Delta_{\min},1\right]$ by arguing that once a sample
is correctly classified at interpolated point
$\alpha^{\prime}\geq\delta/\Delta_{\min}$, it will remain so for any
$\alpha\geq\alpha^{\prime}$. Similar as in Theorem 1, we can show that the
loss is no smaller than $\log k-e\epsilon$ when
$\alpha\leq\frac{\epsilon^{1/r}}{W_{\max}}.$ To show the monotonicity of loss
after $\alpha_{4},$ we show that $f^{[\alpha]}_{i}(x)-f^{[\alpha]}_{j}(x)$ is
increasing in $\alpha$ for $i\neq j$ and $x\in\mathcal{S}_{i}.$

In summary, for $\alpha\in[\alpha_{1},\alpha_{2}],$ the signal is smaller than
the bias gap and the error remains at $1-1/k$. Before $\alpha_{3},$ the signal
is very small and the loss remains large; after $\alpha_{4},$ the signal
starts to overcome the bias gap and the loss is decreasing. See an
illustration in Figure 2 (right).

##  5 Experiments

In this section we empirically show that intuitions from our simple
theoretical model can also be applied to more realistic datasets and
architectures. First, we show that bias plays an important role in creating
the plateau in the error interpolation, as predicted by Theorem 1. We then
demonstrate the influence of initialization size and network depth (also see
Theorem 1). Finally, we show that similar to Proposition 1 the class that is
learned last often has larger bias. Due to space constraint, we only show the
results on MNIST and CIFAR-100 in this section, while similar results also
hold on Fashion-MNIST and CIFAR-10 (see Appendix D).

Unless specified otherwise, we use a depth-10 and width-1024 fully-connected
ReLU neural network (FCN10) for MNIST and use VGG-16 (without batch
normalization) for CIFAR-100. We use Kaiming initialization (He et al., 2015)
for the weights and set all bias terms as zeros. For FCN10 on MNIST, we use a
small initialization by scaling the weights of each layer by $(0.001)^{1/10}$
so the output is scaled by $0.001.$ We train each network using SGD for $100$
epochs. See more experiment settings in Appendix D.

We linearly interpolate using $50$ evenly spaced points between the network at
initialization and the network at the end of training. We evaluate error and
loss on the train set. For each setting, we repeat the experiments three times
from different random seeds and plot the mean and deviation.

Figure 4: Loss and error curves across networks with all bias, last bias and
no bias.

#### Role of bias in creating plateau.

We demonstrate the importance of bias using two experiments. In the first
experiment, we compare the loss/error interpolation curves between networks
equipped with bias for all the layers (_all bias_), with bias only for the
output layer (_last bias_), and with no bias at all (_no bias_). Figure 4
shows that networks with all bias and last bias have a much longer error
plateau than networks without bias. Three bias settings have similar loss
interpolation curves.

Figure 5: Loss and error curves across networks with normal and homogeneous
interpolation on bias.

By our theory, the bias dominates the signal at the beginning of the
interpolation because the bias term scales as $\alpha$ while the signal scales
as $\alpha^{r}.$ In the second experiment, to correct this discrepancy, we
interpolate the bias at the $h$-th layer (input is at the $0$-th layer) as
$b^{[\alpha]}_{h}=\left(1-\alpha\right)^{h}b^{(0)}_{h}+\alpha^{h}b^{(T)}_{h}=\alpha^{h}b^{(T)}_{h}.$
We call this the homogeneous interpolation as now terms involving bias and
weights all have $\alpha^{r}$ coefficients. We compare this with the _normal
interpolation_ that linearly interpolates the bias terms. Figure 5 shows that
for networks with all bias or last bias, using homogeneous interpolation can
significantly reduce the plateau in the error interpolation, but does not
affect the loss interpolation.

Figure 6: Loss and error curves across networks with different initialization
scales.

#### Role of initialization scale and network depth.

Our theory suggests that with a smaller initialization, the signal magnitude
at the initial interpolation is smaller, which can create longer plateau in
both loss interpolation and error interpolation. We compare networks under
initialization scales $1,0.1,0.01$ and $0.001,$ where scale $1$ corresponds to
the standard Kaiming initialization. For other initialization $\beta,$ we
rescale each layer by the same factor so the output is rescaled by $\beta.$
According to Figure 6, smaller initialization does create longer plateau in
loss and error interpolation.

Figure 7: Loss and error curves across networks with different depths.

With a deeper network, the signal grows slower at the initial interpolation
phase, which can potentially create a longer plateau in both loss
interpolation and error interpolation. We compare FCN4, FCN6, FCN8, FCN10 on
MNIST and compare VGG11, VGG13, VGG16, VGG19 on CIFAR-100. According to Figure
7, deeper networks do have longer plateau in loss and error interpolation.

Figure 8: Train loss for each class and bias term dynamics on 2-class MNIST
and 3-class MNIST.

#### Bias learning dynamics.

Our dynamics analysis in Section 4 shows that gradient descent can learn
diverse biases on a balanced dataset by learning different classes at
different time points. In particular, the last learned class should have the
highest bias term. We verify this theory by studying FCN10 with only output
bias on balanced 2-class or 3-class MNIST. To separate the learning of
different classes, we compute the per-class loss by only considering the
examples in that particular class. According to Figure 8, in the 2-class
MNIST, number 1 is learned last and its bias is larger, which fits our theory.
Also in the 3-class MNIST, class 2 is learned first, class 3 the second and
class 1 the last; for the learned bias, class 2 bias is smallest, class 3 bias
in the middle and class 1 bias the highest.

##  6 Conclusion

Our theory suggests that the plateau in loss/error interpolation curves may be
attributed to simple reasons, and it’s unclear if these reasons are related to
the difficulty/easiness of optimization. In our experiments although the
training succeeds in all the settings, the loss and error interpolation curves
can be easily manipulated by changing the initialization size, network depth
and bias terms. Therefore, we believe one needs to look at structures more
complicated than linear interpolation to understand why optimization succeeds
for deep neural networks.

Though our theory requires a small initialization, we also observe plateau in
CIFAR-100 with standard initialization, which suggests that the useful signal
is still a high order term in $\alpha.$ We also observe that sometimes the
ordering of the biases does not exactly follow the ordering of the learning.
We believe this is partially due to the correlation between different-class
features and offer a preliminary explanation in Appendix D.5. We leave the
thorough study of these problems in the future work.

## Acknowledgement

This work is supported by NSF Award DMS-2031849, CCF-1845171 (CAREER),
CCF-1934964 (Tripods) and a Sloan Research Fellowship.

## Reproducibility Statement

For our theoretical results, we listed all the assumptions and stated the
theorems in the main text and we left the complete proof for all the claims in
the Appendix. For our experimental results, we defined the detailed experiment
settings in the Appendix and also uploaded the source code as supplementary
material.

## References

  * Allen-Zhu & Li (2020) Zeyuan Allen-Zhu and Yuanzhi Li.  Towards understanding ensemble, knowledge distillation and self-distillation in deep learning.  _arXiv preprint arXiv:2012.09816_ , 2020.
  * Allen-Zhu et al. (2019) Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song.  A convergence theory for deep learning via over-parameterization.  In _International Conference on Machine Learning_ , pp. 242–252. PMLR, 2019.
  * Arora et al. (2019) Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang.  Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks.  In _International Conference on Machine Learning_ , pp. 322–332. PMLR, 2019.
  * Chizat & Bach (2018) Lenaic Chizat and Francis Bach.  On the global convergence of gradient descent for over-parameterized models using optimal transport.  _Advances in neural information processing systems_ , 31, 2018.
  * Deng (2012) Li Deng.  The mnist database of handwritten digit images for machine learning research.  _IEEE Signal Processing Magazine_ , 29(6):141–142, 2012.
  * Draxler et al. (2018) Felix Draxler, Kambis Veschgini, Manfred Salmhofer, and Fred Hamprecht.  Essentially no barriers in neural network energy landscape.  In _International conference on machine learning_ , pp. 1309–1318. PMLR, 2018.
  * Du et al. (2018) Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh.  Gradient descent provably optimizes over-parameterized neural networks.  _arXiv preprint arXiv:1810.02054_ , 2018.
  * Fort et al. (2020) Stanislav Fort, Gintare Karolina Dziugaite, Mansheej Paul, Sepideh Kharaghani, Daniel M Roy, and Surya Ganguli.  Deep learning versus kernel learning: an empirical study of loss landscape geometry and the time evolution of the neural tangent kernel.  _Advances in Neural Information Processing Systems_ , 33:5850–5861, 2020.
  * Frankle (2020) Jonathan Frankle.  Revisiting" qualitatively characterizing neural network optimization problems".  _arXiv preprint arXiv:2012.06898_ , 2020.
  * Frankle et al. (2020) Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin.  Linear mode connectivity and the lottery ticket hypothesis.  In _International Conference on Machine Learning_ , pp. 3259–3269. PMLR, 2020.
  * Freeman & Bruna (2016) C Daniel Freeman and Joan Bruna.  Topology and geometry of half-rectified network optimization.  _arXiv preprint arXiv:1611.01540_ , 2016.
  * Garipov et al. (2018) Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry P Vetrov, and Andrew G Wilson.  Loss surfaces, mode connectivity, and fast ensembling of dnns.  _Advances in neural information processing systems_ , 31, 2018.
  * Ge et al. (2021) Rong Ge, Yunwei Ren, Xiang Wang, and Mo Zhou.  Understanding deflation process in over-parametrized tensor decomposition.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Glorot & Bengio (2010) Xavier Glorot and Yoshua Bengio.  Understanding the difficulty of training deep feedforward neural networks.  In _Proceedings of the thirteenth international conference on artificial intelligence and statistics_ , pp. 249–256. JMLR Workshop and Conference Proceedings, 2010.
  * Goodfellow et al. (2014) Ian J Goodfellow, Oriol Vinyals, and Andrew M Saxe.  Qualitatively characterizing neural network optimization problems.  _arXiv preprint arXiv:1412.6544_ , 2014.
  * He et al. (2015) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Delving deep into rectifiers: Surpassing human-level performance on imagenet classification.  In _Proceedings of the IEEE international conference on computer vision_ , pp. 1026–1034, 2015.
  * Hillar & Lim (2013) Christopher J Hillar and Lek-Heng Lim.  Most tensor problems are np-hard.  _Journal of the ACM (JACM)_ , 60(6):1–39, 2013\.
  * Jacot et al. (2018) Arthur Jacot, Franck Gabriel, and Clément Hongler.  Neural tangent kernel: Convergence and generalization in neural networks.  _Advances in neural information processing systems_ , 31, 2018.
  * Krizhevsky et al. (2009) Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * Kuditipudi et al. (2019) Rohith Kuditipudi, Xiang Wang, Holden Lee, Yi Zhang, Zhiyuan Li, Wei Hu, Rong Ge, and Sanjeev Arora.  Explaining landscape connectivity of low-cost solutions for multilayer nets.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Lucas et al. (2021) James Lucas, Juhan Bae, Michael R Zhang, Stanislav Fort, Richard Zemel, and Roger Grosse.  Analyzing monotonic linear interpolation in neural network loss landscapes.  _arXiv preprint arXiv:2104.11044_ , 2021.
  * Mei et al. (2018) Song Mei, Andrea Montanari, and Phan-Minh Nguyen.  A mean field view of the landscape of two-layer neural networks.  _Proceedings of the National Academy of Sciences_ , 115(33):E7665–E7671, 2018.
  * Nguyen (2019) Quynh Nguyen.  On connected sublevel sets in deep learning.  In _International Conference on Machine Learning_ , pp. 4790–4799. PMLR, 2019.
  * Nguyen (2021) Quynh Nguyen.  A note on connectivity of sublevel sets in deep learning.  _arXiv preprint arXiv:2101.08576_ , 2021.
  * Nguyen et al. (2021) Quynh N Nguyen, Pierre Bréchet, and Marco Mondelli.  When are solutions connected in deep networks?  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Shevchenko & Mondelli (2020) Alexander Shevchenko and Marco Mondelli.  Landscape connectivity and dropout stability of sgd solutions for over-parameterized neural networks.  In _International Conference on Machine Learning_ , pp. 8773–8784. PMLR, 2020.
  * Simonyan & Zisserman (2014) Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  _arXiv preprint arXiv:1409.1556_ , 2014.
  * Venturi et al. (2018) Luca Venturi, Afonso S Bandeira, and Joan Bruna.  Spurious valleys in two-layer neural network optimization landscapes.  _arXiv preprint arXiv:1802.06384_ , 2018.
  * Xiao et al. (2017) Han Xiao, Kashif Rasul, and Roland Vollgraf.  Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms.  _arXiv preprint arXiv:1708.07747_ , 2017.

##  Appendix A Examples for the disconnection between linear interpolation
shape and optimization difficulty

We give two examples that illustrate the disconnection between the linear
interpolation shape and the optimization difficulty. In Section A.1, we show a
function that is NP-hard to optimize, but has a convex and monotonically
decreasing loss interpolation. Then in Section A.2, we give a function that is
easy to optimize, but has a non-monotonic loss interpolation.

###  A.1 Hard function with convex loss interpolation

For any symmetric third-order tensor $T\in{\mathbb{R}}^{d\times d\times d},$
our goal is to minimize

$f(x,z)=-T(x,x,x)+\left\|x\right\|^{4}+z^{4}$ (2)

where $x\in{\mathbb{R}}^{d}$ and $z\in{\mathbb{R}}.$

It’s known that finding the spectral norm of a symmetric third-order tensor
(that is, $\max_{v\in{\mathbb{R}}^{d},\left\|v\right\|=1}T(v,v,v)$) is NP-hard
(Hillar & Lim, 2013). We prove that minimizing $f(x,z)$ is also NP-hard by
reducing the tensor spectral norm problem to it.

######  Proposition 2.

Minimizing $f(x,z)$ as defined in Eqn. 2 is NP-hard.

###### Proof.

For any non-zero tensor $T,$ let $(x^{*},z^{*})$ be one minimizer of $f(x,z),$
it’s easy to verify that $T(x^{*},x^{*},x^{*})>0.$ We show that
$\bar{x}^{*}:=x^{*}/\left\|x^{*}\right\|$ must be a solution to
$\max_{v\in{\mathbb{R}}^{d},\left\|v\right\|=1}T(v,v,v)$.

For the sake of contradiction, assume there exists $v^{*}$ with unit norm such
that $T(v^{*},v^{*},v^{*})>T(\bar{x}^{*},\bar{x}^{*},\bar{x}^{*}).$ It’s easy
to verify that $f(\left\|x^{*}\right\|v^{*},z^{*})<f(x^{*},z^{*}),$ which
however contradicts the optimality of $(x^{*},z^{*})$. ∎

Next, we prove that start from certain initialization, the loss along the
linear interpolation path is convex and monotonically decreasing. Note that
assuming the unit Frobenius norm of $T$ does not hurt the NP-hardness of the
problem. And our initialization is oblivious of the tensor $T.$

######  Proposition 3.

Assume $\left\|T\right\|_{F}=1.$ Suppose we start from initialization
$(x_{0},z_{0})$ with $x_{0}=0$ and $\left|z_{0}\right|>\frac{3\sqrt{2}}{4}.$
Let $(x^{*},z^{*})$ be a minimizer of $f(x,z)$ as defined in Eqn. 2. We know
the loss interpolation curve $\gamma(\alpha):=f\left((1-\alpha)x_{0}+\alpha
x^{*},(1-\alpha)z_{0}+\alpha z^{*}\right)$ is convex and monotonically
decreasing for $\alpha\in[0,1].$

###### Proof.

We first prove that at any minimizer $(x^{*},z^{*})$, we must have $z^{*}=0.$
Otherwise, we can set $z$ as zero to further decrease the loss. Starting from
an initialization $(x^{(0)},z^{(0)})$ with $x^{(0)}=0$, we know at each
interpolation point $x^{[\alpha]}=\alpha
x^{*},z^{[\alpha]}=(1-\alpha)z^{(0)}.$ Therefore, we have

$\displaystyle\gamma(\alpha)=f(x^{[\alpha]},z^{[\alpha]})=$
$\displaystyle-T(x^{[\alpha]},x^{[\alpha]},x^{[\alpha]})+\left\|x^{[\alpha]}\right\|^{4}+\left[z^{[\alpha]}\right]^{4}$
$\displaystyle=$ $\displaystyle-T(\alpha x^{*},\alpha x^{*},\alpha
x^{*})+\left\|\alpha x^{*}\right\|^{4}+\left[(1-\alpha)z^{(0)}\right]^{4}$
$\displaystyle=$
$\displaystyle-\alpha^{3}T(x^{*},x^{*},x^{*})+\alpha^{4}\left\|x^{*}\right\|^{4}+(1-\alpha)^{4}\left[z^{(0)}\right]^{4}.$

To prove the convexity of $\gamma(\alpha)$ for $\alpha\in[0,1],$ we only need
to prove $\gamma^{\prime\prime}(\alpha)>0$ for $\alpha\in[0,1]$. We have

$\displaystyle\gamma^{\prime\prime}(\alpha)=$ $\displaystyle-6\alpha
T(x^{*},x^{*},x^{*})+12\alpha^{2}\left\|x^{*}\right\|^{4}+12(1-\alpha)^{2}\left[z^{(0)}\right]^{4}$
$\displaystyle=$
$\displaystyle-6\alpha\left\|x^{*}\right\|^{3}T(\bar{x}^{*},\bar{x}^{*},\bar{x}^{*})+12\alpha^{2}\left\|x^{*}\right\|^{4}+12(1-\alpha)^{2}\left[z^{(0)}\right]^{4}.$

Since the formula for $\gamma^{\prime\prime}(\alpha)$ involves both
$T(\bar{x}^{*},\bar{x}^{*},\bar{x}^{*})$ and $\left\|x^{*}\right\|,$ we first
figure out the relation between these two quantities. Suppose
$T(\bar{x}^{*},\bar{x}^{*},\bar{x}^{*})=p>0,$ it’s not hard to find
$\left\|x^{*}\right\|$ must be equal to $\frac{3p}{4}$. This is because
$-\left\|x^{*}\right\|^{3}p+\left\|x^{*}\right\|^{4}$ is minimized when
$\left\|x^{*}\right\|=\frac{3p}{4}$. Next, we prove
$\gamma^{\prime\prime}(\alpha)>0$ for $\alpha\in(2/3,1]$ and
$\alpha\in[0,2/3]$ separetely.

When $\alpha\in(2/3,1],$ we have

$\displaystyle
12\alpha^{2}\left\|x^{*}\right\|^{4}>6p\alpha\left\|x^{*}\right\|^{3}=6\alpha\left\|x^{*}\right\|^{3}T(\bar{x}^{*},\bar{x}^{*},\bar{x}^{*}).$

Therefore, we know $\gamma^{\prime\prime}(\alpha)>0.$

When $\alpha\in[0,2/3],$ we know

$\displaystyle
12(1-\alpha)^{2}\left[z^{(0)}\right]^{4}\geq\frac{4}{3}\left[z^{(0)}\right]^{4}.$

Since $\left\|T\right\|_{F}=1,$ we know
$T(\bar{x}^{*},\bar{x}^{*},\bar{x}^{*})\leq 1$ and $\left\|x^{*}\right\|\leq
3/4.$ Therefore, we have

$\displaystyle
6\alpha\left\|x^{*}\right\|^{3}T(\bar{x}^{*},\bar{x}^{*},\bar{x}^{*})\leq
6\cdot\frac{2}{3}\cdot\left(\frac{3}{4}\right)^{3}\cdot 1=\frac{27}{16}.$

Then, we know that if $\left|z^{(0)}\right|>\frac{3\sqrt{2}}{4},$ we have
$\gamma^{\prime\prime}(\alpha)>0.$ ∎

###  A.2 Easy function with non-monotonic loss interpolation

In this section, we give an easy-to-optimize function that however has a non-
monotonic loss interpolation curve. We consider the following loss function

$f(x,y)=\begin{cases}0&\text{if $x=y=0$}\\\
\left(1-\frac{y}{3\sqrt{x^{2}+y^{2}}}\right)\left(\left(x^{2}+y^{2}\right)^{2}-2\left(x^{2}+y^{2}\right)\right)&\text{otherwise},\end{cases}$
(3)

where $x,y\in{\mathbb{R}}$. We can also re-parameterize $f(x,y)$ using angle
$\theta\in[0,2\pi)$ and length $r\in[0,\infty)$ as
$h(\theta,r)=\left(1-\frac{\sin(\theta)}{3}\right)\left(r^{4}-2r^{2}\right).$

Next, we prove that starting from any non-zero point, gradient flow converges
to the global minimizer.

######  Proposition 4.

Starting from any non-zero initialization, gradient flow on $f(x,y)$ as
defined in Eqn. 3 converges to the global minimizer $(0,-1).$

###### Proof.

We know the unique minimizer of $f(x,y)$ is $(0,-1)$ by considering its
equivalent form $h(\theta,r).$ For
$h(\theta,r)=\left(1-\frac{\sin(\theta)}{3}\right)\left(r^{4}-2r^{2}\right),$
we know $\left(r^{4}-2r^{2}\right)$ is minimized at $r=1$ and
$\left(1-\frac{\sin(\theta)}{3}\right)$ is maximized at
$\theta=\frac{3\pi}{2}.$

Besides the minimizer $(0,-1)$, the other stationary point is at $(0,0).$ For
any point $(x,y)$ different from $(0,-1)$ and $(0,0),$ if $x^{2}+y^{2}\neq 1,$
the gradient along the radial direction is non-zero; if
$\frac{y}{\sqrt{x^{2}+y^{2}}}\neq-1,$ the gradient along the tangent direction
is non-zero. It’s also easy to verify that starting from a non-zero point,
gradient flow does not converge to $(0,0),$ so it must converge to $(0,-1)$ ∎

It’s also very easy to prove that gradient descent with appropriate step size
converges to an $\epsilon$-neighborhood of the global minimizer within
${\text{poly}}(1/\epsilon)$ number of iterations. This is because the gradient
is at least ${\text{poly}}(\epsilon)$ for any non-zero point outside of the
$\epsilon$-neighborhood of the global minimizer. Starting from an
initialization $(x,y)$ with $x^{2}+y^{2}=\Theta(1),$ the smoothness along the
training is also bounded by a constant.

Next, we prove that starting from certain initialization 333Note the
initialization condition in Prop. 5 is satisfied with constant probability for
a reasonable initialization scheme. For example, if we uniformly sample
$(x,y)$ from the set $S=\\{(x,y)\in{\mathbb{R}}^{2}|x^{2}+y^{2}\leq R\\}$ with
$R\geq 2,$ the condition is satisfied with constant probability., the loss
interpolation between the initialization and the global minimizer is non-
monotonic. We prove this by identifying two points along the interpolation
path such that the point closer to minimizer has a higher loss compared with
the point further to the minimizer.

######  Proposition 5.

Suppose we start from an initialization
$(x_{0},y_{0})=(r\sin(\beta),r\cos(\beta))$ with $r\geq 1$ and
$\beta\in[-\pi/3,\pi/3]$. Consider the loss interpolation curve
$\gamma(\alpha)=f((1-\alpha)x_{0}+\alpha x^{*},(1-\alpha)y_{0}+\alpha y^{*})$
with $(x^{*},y^{*})=(0,-1)$ and $f(\cdot,\cdot)$ defined in Eqn. 3. We know
there exist $0\leq\alpha_{1}<\alpha_{2}\leq 1$ such that

$\gamma(\alpha_{2})-\gamma(\alpha_{1})\geq\frac{5}{32}.$

###### Proof.

We prove for any $\beta\in[-\pi/3,\pi/3]$ and any $r\geq 1,$ the loss
interpolation between $(r\sin(\beta),r\cos(\beta))$ to $(0,-1)$ is non-
monotonic. In particular, we show there are two points along the linear
interpolation satisfying

$f\left(\sin\left(\beta/2\right)\cos\left(\beta/2\right),-\sin\left(\beta/2\right)\sin\left(\beta/2\right)\right)-f\left(\sin(\beta),\cos(\beta)\right)\geq
1/12,$

where
$\left(\sin\left(\beta/2\right)\cos\left(\beta/2\right),-\sin\left(\beta/2\right)\sin\left(\beta/2\right)\right)$
is the middle point between $\left(\sin(\beta),\cos(\beta)\right)$ and
$(0,-1).$

Next, we separately upper bound $f\left(\sin(\beta),\cos(\beta)\right)$ and
lower bound
$f\left(\sin\left(\beta/2\right)\cos\left(\beta/2\right),-\sin\left(\beta/2\right)\sin\left(\beta/2\right)\right)$.
We have

$\displaystyle\max_{\beta\in[-\pi/3,\pi/3]}f\left(\sin(\beta),\cos(\beta)\right)\leq
f(0,1)=-\frac{2}{3}$

and

$\displaystyle\min_{\beta\in[-\pi/3,\pi/3]}f\left(\sin\left(\beta/2\right)\cos\left(\beta/2\right),-\sin\left(\beta/2\right)\sin\left(\beta/2\right)\right)$
$\displaystyle\geq$ $\displaystyle
f\left(\sin\left(\pi/6\right)\cos\left(\pi/6\right),-\sin\left(\pi/6\right)\sin\left(\pi/6\right)\right)$
$\displaystyle=$
$\displaystyle\left(1+\frac{1}{2}\cdot\frac{1}{3}\right)\left(\left(\frac{1}{2}\right)^{4}-2\left(\frac{1}{2}\right)^{2}\right)$
$\displaystyle=$ $\displaystyle-\frac{49}{96}.$

Therefore, we have
$f\left(\sin\left(\beta/2\right)\cos\left(\beta/2\right),-\sin\left(\beta/2\right)\sin\left(\beta/2\right)\right)-f\left(\sin(\beta),\cos(\beta)\right)\geq\frac{5}{32}.$
∎

##  Appendix B Proof for plateau and monotonicity

We first consider the $r$-homogeneous-weight model. We prove the plateau and
monotonicity properties for the error interpolation (Theorem 4) in Section
B.1. We then prove the plateau and monotonicity properties for the loss
interpolation (Theorem 5) in Section B.2. Theorem 3 is a simple combination of
Theorem 4 and Theorem 5. Finally, we give the plateau analysis for the fully-
connected neural networks (Theorem 1) in Section B.3.

###  B.1 Error interpolation for $r$-homogeneous-weight model

######  Theorem 4 (Error Interpolation).

Suppose the network at initialization and after training satisfy the
properties described in Theorem 2 and Induction Hypothesis 1. Suppose
$\delta\leq\min(O(1),O(R_{\min}^{\frac{1}{r-1}}\Delta_{\min}^{1/r}),O((\frac{W_{\min}}{W_{\max}})^{\frac{2r}{r-2}})).$
There exist $\alpha_{1}=\frac{\delta}{\Delta_{\min}}$ and
$\alpha_{2}=(\frac{1}{1+O(\sqrt{\delta})})^{\frac{r}{r-1}}R_{\min}^{\frac{1}{r-1}}$,
such that

  1. 1.

for all $\alpha\in[\alpha_{1},\alpha_{2}],$ the error is $1-1/k;$

  2. 2.

for all $\alpha\in[\alpha_{1},1],$ the error is non-increasing.

Proof of Theorem 4. This theorem directly follows from Lemma 4 and Lemma 5.
$\Box$

Next, we separately prove the initial plateau in Lemma 4 and the monotonicity
in Lemma 5.

######  Lemma 4 (Error Plateau).

In the same setting as in Theorem 4, there exists
$\alpha_{1}=\frac{\delta}{\Delta_{\min}}$ and
$\alpha_{2}=\left(\frac{1}{1+O(\sqrt{\delta})}\right)^{\frac{r}{r-1}}R_{\min}^{\frac{1}{r-1}}$,
such that for any interpolation point with $\alpha\in[\alpha_{1},\alpha_{2}],$
the error is $1-1/k.$ Moreover, we have
$f^{[\alpha]}_{i}(e_{j})<f^{[\alpha]}_{k}(e_{j})$ for all $j\in[k]$ and all
$i\neq k$.

In the proof of Lemma 4, we show that for interpolation point
$\alpha\in[\alpha_{1},\alpha_{2}],$ the bias term dominates and all samples
are classified as class $k$ that has the largest bias.

Proof of Lemma 4. We only need to show that for all
$\alpha\in[\alpha_{1},\alpha_{2}],$ we have

$\displaystyle f^{[\alpha]}_{i}(x)<f^{[\alpha]}_{k}(x)$

for all $x\in\mathcal{S}$ and all $i\neq k,$ which immediately implies the
error is $1-1/k.$ Without loss of generality, assume $x\in\mathcal{S}_{j}$
where $j$ may equal $i$ or $k.$

#### For $\alpha\in\left[\alpha_{1},\frac{\sqrt{\delta}}{W_{\min}}\right)$.

If
$\alpha_{1}=\frac{\delta}{\Delta_{\min}}\geq\frac{\sqrt{\delta}}{W_{\min}}$,
we only need to consider the case when
$\alpha\in\left[\frac{\sqrt{\delta}}{W_{\min}},\alpha_{2}\right].$ So here we
assume $\frac{\delta}{\Delta_{\min}}<\frac{\sqrt{\delta}}{W_{\min}}.$ We can
lower bound $f^{[\alpha]}_{k}(x)-f^{[\alpha]}_{i}(x)$ as

$\displaystyle f^{[\alpha]}_{k}(x)-f^{[\alpha]}_{i}(x)$ $\displaystyle=$
$\displaystyle\left[\left\langle
W^{[\alpha]}_{k,:},x\right\rangle\right]^{r}+b^{[\alpha]}_{k}-\left[\left\langle
W^{[\alpha]}_{i,:},x\right\rangle\right]^{r}-b^{[\alpha]}_{i}$
$\displaystyle=$ $\displaystyle\left[\left\langle
W^{[\alpha]}_{k,:},x\right\rangle\right]^{r}+b^{[\alpha]}_{k}-\left[W^{[\alpha]}_{i,j}\pm
O(\delta)\right]^{r}-b^{[\alpha]}_{i}$ $\displaystyle\geq$
$\displaystyle\alpha\Delta_{i}-\left[W^{(0)}_{i,j}+\alpha
W^{(T)}_{i,j}+O(\delta)\right]^{r},$

where the second equality uses $\left|\left\langle
W^{[\alpha]}_{i,:},\xi_{x}\right\rangle\right|\leq O(\delta)$ and the
inequality uses $\left\langle W^{[\alpha]}_{k,:},x\right\rangle\geq 0.$

To prove $f^{[\alpha]}_{k}(x)-f^{[\alpha]}_{i}(x)>0$ for
$\alpha\in\left[\frac{\delta}{\Delta_{\min}},\frac{\sqrt{\delta}}{W_{\min}}\right]$,
we only need to prove
$\frac{\delta}{\Delta_{\min}}\Delta_{i}-\left[W^{(0)}_{i,j}+\frac{\sqrt{\delta}}{W_{\min}}W^{(T)}_{i,j}+O(\delta)\right]^{r}>0.$
Since $\Delta_{i}\geq\Delta_{\min},$ we know
$\frac{\delta}{\Delta_{\min}}\Delta_{i}\geq\delta.$ Due to full accuracy, we
know $\left\langle W^{(T)}_{i,:},x\right\rangle\geq\Delta_{i}^{1/r}$ for
$x\in\mathcal{S}_{i},$ which then implies
$W^{(T)}_{i,i}\geq\Omega\left(\Delta_{i}^{1/r}\right)$ because
$\Delta_{i}\geq\Omega(1)$ and $\left\langle
W^{(T)}_{i,:},\xi_{x}\right\rangle\leq O(\delta)\leq O(1).$ Since
$W^{(T)}_{i,i}\geq\Omega\left(\Delta_{i}^{1/r}\right)$ and $W^{(T)}_{i,j}\leq
O(\delta)$ for $i\neq j,$ so we have $W^{(T)}_{i,j}\leq W^{(T)}_{i,i}\leq
W_{\max}$ as long as $\delta\leq O(\Delta_{\min}^{1/r}).$ So we can upper
bound
$\left[W^{(0)}_{i,j}+\frac{\sqrt{\delta}}{W_{\min}}W^{(T)}_{i,j}+O(\delta)\right]^{r}$
as follows,

$\displaystyle\left[W^{(0)}_{i,j}+\frac{\sqrt{\delta}}{W_{\min}}W^{(T)}_{i,j}+O(\delta)\right]^{r}\leq$
$\displaystyle\left[O(\delta)+\frac{\sqrt{\delta}W_{\max}}{W_{\min}}\right]^{r}$
$\displaystyle\leq$
$\displaystyle\left[\frac{\sqrt{\delta}W_{\max}}{rW_{\min}}+\frac{\sqrt{\delta}W_{\max}}{W_{\min}}\right]^{r}$
$\displaystyle\leq$ $\displaystyle
e\left(\frac{\sqrt{\delta}W_{\max}}{W_{\min}}\right)^{r},$

where the second inequality assumes $\delta\leq
O\left(\frac{W_{\max}^{2}}{W_{\min}^{2}}\right).$ Therefore, to prove
$\frac{\delta}{\Delta_{\min}}\Delta_{i}-\left[W^{(0)}_{i,j}+\frac{\sqrt{\delta}}{W_{\min}}W^{(T)}_{i,j}+O(\delta)\right]^{r}>0$
we only need

$\displaystyle\delta-e\left(\frac{\sqrt{\delta}W_{\max}}{W_{\min}}\right)^{r}>0,$

which holds as long as
$\delta<\left[\frac{1}{e}\left(\frac{W_{\min}}{W_{\max}}\right)^{r}\right]^{\frac{2}{r-2}}.$

#### For $\alpha\in\left[\frac{\sqrt{\delta}}{W_{\min}},\alpha_{2}\right]$.

Similar as above, we only need to show that
$\alpha\Delta_{i}-\left[W^{(0)}_{i,j}+\alpha
W^{(T)}_{i,j}+O(\delta)\right]^{r}>0$ for $i\neq k$ and $j\in[k].$ Since
$W^{(0)}_{i,j}\leq O(\delta)$ and $\alpha\geq\sqrt{\delta}/W_{\min},$ we have
$W^{(0)}_{i,j}\leq O(\sqrt{\delta}\alpha W_{\min})$. Therefore, we have
$W^{(0)}_{i,j}+\alpha
W^{(T)}_{i,j}+O(\delta)\leq\left(1+O(\sqrt{\delta})\right)\alpha
W^{(T)}_{i,i}.$ Therefore, we have

$\displaystyle\alpha\Delta_{i}-\left[W^{(0)}_{i,j}+\alpha
W^{(T)}_{i,j}+O(\delta)\right]^{r}\geq\alpha\Delta_{i}-\left(1+O(\sqrt{\delta})\right)^{r}\alpha^{r}\left[W^{(T)}_{i,i}\right]^{r}>0,$

where the last inequality assumes
$\alpha\leq\alpha_{2}:=\left(\frac{1}{1+O(\sqrt{\delta})}\right)^{\frac{r}{r-1}}R_{\min}^{\frac{1}{r-1}}$
where $R_{\min}=\min_{i\in[k-1]}\Delta_{i}/[W^{(T)}_{i,i}]^{r}.$ $\Box$

Next, we show that the error is non-increasing for $\alpha\in[\alpha_{1},1]$
by proving that once a sample is classified correctly it will remain so.

######  Lemma 5 (Error Monotonicity).

In the same setting as in Theorem 4, there exists
$\delta_{1}=\frac{\delta}{\Delta_{\min}}$ such that the error is non-
increasing for $\alpha\in[\alpha_{1},1].$

Proof of Lemma 5. We first show that sample $e_{k}$ is correctly classified
for the whole range $[\alpha_{1},1]$. Second, we show for any other sample
once it become classified right it will remain so. Combining these two cases,
we prove the monotonicity of the error rate.

#### Class k.

We first show that every $x\in\mathcal{S}_{k}$ is classified correctly for any
$\alpha\in[\alpha_{1},1].$ According to Lemma 4, we know that

$\displaystyle f^{[\alpha_{1}]}_{k}(x)>f^{[\alpha_{1}]}_{i}(x)$

for any $i\neq k.$ We only need to prove that
$f^{[\alpha]}_{k}(x)-f^{[\alpha]}_{i}(x)$ is increasing for
$\alpha\in[\alpha_{1},1].$ Expanding
$f^{[\alpha]}_{k}(x)-f^{[\alpha]}_{i}(x)$, we have

$\displaystyle f^{[\alpha]}_{k}(x)-f^{[\alpha]}_{i}(x)$ $\displaystyle=$
$\displaystyle\left[(1-\alpha)\left\langle
W^{(0)}_{k,:},x\right\rangle+\alpha\left(\left\langle
W^{(T)}_{k,:},x\right\rangle\right)\right]^{r}-\left[(1-\alpha)\left\langle
W^{(0)}_{i,:},x\right\rangle+\alpha\left\langle
W^{(T)}_{i,:},x\right\rangle\right]^{r}+\alpha\left(b^{(T)}_{k}-b^{(T)}_{i}\right),$

which is increasing since $\left|\left\langle
W^{(T)}_{k,:},x\right\rangle\right|,\left|\left\langle
W^{(0)}_{k,:},x\right\rangle\right|,\left|\left\langle
W^{(T)}_{i,:},x\right\rangle\right|,\left|\left\langle
W^{(0)}_{i,:},x\right\rangle\right|\leq O(\delta)$ and
$b^{(T)}_{k}-b^{(T)}_{i}>\Omega(1).$

#### Other classes.

For any class $i\neq k,$ from Lemma 4, we know that it is classified
incorrectly for $\alpha\in[\alpha_{1},\alpha_{2}].$ We prove that once it
become classified correctly at some $\alpha^{\prime}\in(\alpha_{2},1]$, it
remains so for $\alpha\in[\alpha^{\prime},1].$

We show that at $\alpha,$ for any $x\in\mathcal{S}_{i}$, if
$f^{[\alpha]}_{i}(x)>f^{[\alpha]}_{j}(x)$ for all $j\neq i$, we have
$\frac{\partial}{\partial\alpha}\left(f^{[\alpha]}_{i}(x)-f^{[\alpha]}_{j}(x)\right)>0.$
Expanding $f^{[\alpha]}_{i}(x)-f^{[\alpha]}_{j}(x),$ we have

$\displaystyle f^{[\alpha]}_{i}(x)-f^{[\alpha]}_{j}(x)$ $\displaystyle=$
$\displaystyle\left[\left\langle
W^{[\alpha]}_{i,:},x\right\rangle\right]^{r}+b^{[\alpha]}_{i}-\left[\left\langle
W^{[\alpha]}_{j,:},x\right\rangle\right]^{r}-b^{[\alpha]}_{j}$
$\displaystyle=$ $\displaystyle\left[\left\langle
W^{[\alpha]}_{i,:},x\right\rangle\right]^{r}-\left[\left\langle
W^{[\alpha]}_{j,:},x\right\rangle\right]^{r}-\alpha\left(b^{(T)}_{j}-b^{(T)}_{i}\right).$

Since $f^{[\alpha]}_{i}(x)-f^{[\alpha]}_{j}(x)>0,$ we have

$\displaystyle\left[\left\langle
W^{[\alpha]}_{i,:},x\right\rangle\right]^{r}>\alpha\left(b^{(T)}_{j}-b^{(T)}_{i}\right),$

where we use $\left\langle W^{[\alpha]}_{j,:},x\right\rangle\geq 0.$ Computing
$\frac{\partial}{\partial\alpha}\left(f^{[\alpha]}_{i}(x)-f^{[\alpha]}_{j}(x)\right),$
we have

$\displaystyle\frac{\partial}{\partial\alpha}\left(f^{[\alpha]}_{i}(x)-f^{[\alpha]}_{j}(x)\right)$
$\displaystyle=$
$\displaystyle\frac{\partial}{\partial\alpha}\left(\left[(1-\alpha)\left\langle
W^{(0)}_{i,:},x\right\rangle+\alpha\left\langle
W^{(T)}_{i,:},x\right\rangle\right]^{r}-\left[(1-\alpha)\left\langle
W^{(0)}_{j,:},x\right\rangle+\alpha\left\langle
W^{(T)}_{j,:},x\right\rangle\right]^{r}+\alpha\left(b^{(T)}_{i}-b^{(T)}_{j}\right)\right)$
$\displaystyle\geq$ $\displaystyle r\left[\left\langle
W^{(0)}_{i,:},x\right\rangle+\alpha\left(\left\langle
W^{(T)}_{i,:},x\right\rangle-\left\langle
W^{(0)}_{i,:},x\right\rangle\right)\right]^{r-1}\left(\left\langle
W^{(T)}_{i,:},x\right\rangle-\left\langle
W^{(0)}_{i,:},x\right\rangle\right)-\left(b^{(T)}_{j}-b^{(T)}_{i}\right)-O(\delta^{r}),$

where the inequality uses $\left|\left\langle
W^{(0)}_{j,:},x\right\rangle\right|,\left|\left\langle
W^{(T)}_{j,:},x\right\rangle\right|\leq O(\delta).$

If $b^{(T)}_{j}-b^{(T)}_{i}\leq 0,$ we only need to prove

$r\left[\left\langle W^{(0)}_{i,:},x\right\rangle+\alpha\left(\left\langle
W^{(T)}_{i,:},x\right\rangle-\left\langle
W^{(0)}_{i,:},x\right\rangle\right)\right]^{r-1}\left(\left\langle
W^{(T)}_{i,:},x\right\rangle-\left\langle
W^{(0)}_{i,:},x\right\rangle\right)-O(\delta^{r})>0,$

which holds since $\left(\left\langle
W^{(T)}_{i,:},x\right\rangle-\left\langle
W^{(0)}_{i,:},x\right\rangle\right),\left\langle
W^{[\alpha]}_{i,:},x\right\rangle\geq\Omega(1).$

If $b^{(T)}_{j}-b^{(T)}_{i}>0,$ we have

$\displaystyle\frac{\partial}{\partial\alpha}\left(f^{[\alpha]}_{i}(x)-f^{[\alpha]}_{j}(x)\right)$
$\displaystyle=$ $\displaystyle r\left[\left\langle
W^{(0)}_{i,:},x\right\rangle+\alpha\left(\left\langle
W^{(T)}_{i,:},x\right\rangle-\left\langle
W^{(0)}_{i,:},x\right\rangle\right)\right]^{r-1}\left(\left\langle
W^{(T)}_{i,:},x\right\rangle-\left\langle
W^{(0)}_{i,:},x\right\rangle\right)-\left(b^{(T)}_{j}-b^{(T)}_{i}\right)-O(\delta^{r})$
$\displaystyle>$
$\displaystyle\frac{\left(1-O(\delta^{r})\right)r\left(\left\langle
W^{(T)}_{i,:},x\right\rangle-\left\langle
W^{(0)}_{i,:},x\right\rangle\right)}{\left[\left\langle
W^{(0)}_{i,:},x\right\rangle+\alpha\left(\left\langle
W^{(T)}_{i,:},x\right\rangle-\left\langle
W^{(0)}_{i,:},x\right\rangle\right)\right]}\cdot\alpha\left(b^{(T)}_{j}-b^{(T)}_{i}\right)-\left(b^{(T)}_{j}-b^{(T)}_{i}\right),$

where the last inequality uses $\left[\left\langle
W^{[\alpha]}_{i,:},x\right\rangle\right]^{r}>\alpha\left(b^{(T)}_{j}-b^{(T)}_{i}\right).$
Therefore, to prove
$\frac{\partial}{\partial\alpha}\left(f^{[\alpha]}_{i}(e_{i})-f^{[\alpha]}_{j}(e_{i})\right)>0,$
we only need to prove $\frac{\left(1-O(\delta^{r})\right)r\left(\left\langle
W^{(T)}_{i,:},x\right\rangle-\left\langle
W^{(0)}_{i,:},x\right\rangle\right)}{\left[\left\langle
W^{(0)}_{i,:},x\right\rangle+\alpha\left(\left\langle
W^{(T)}_{i,:},x\right\rangle-\left\langle
W^{(0)}_{i,:},x\right\rangle\right)\right]}\geq\frac{1}{\alpha}.$ We have

$\displaystyle\frac{\left(1-O(\delta^{r})\right)r\left(\left\langle
W^{(T)}_{i,:},x\right\rangle-\left\langle
W^{(0)}_{i,:},x\right\rangle\right)}{\left[\left\langle
W^{(0)}_{i,:},x\right\rangle+\alpha\left(\left\langle
W^{(T)}_{i,:},x\right\rangle-\left\langle
W^{(0)}_{i,:},x\right\rangle\right)\right]}\geq\frac{\left(1-O(\delta^{r})\right)r\left(\left\langle
W^{(T)}_{i,:},x\right\rangle-\left\langle
W^{(0)}_{i,:},x\right\rangle\right)}{2\alpha\left(\left\langle
W^{(T)}_{i,:},x\right\rangle-\left\langle
W^{(0)}_{i,:},x\right\rangle\right)}\geq\frac{1}{\alpha}.$

The first inequality requires $\left\langle
W^{(0)}_{i,:},x\right\rangle\leq\alpha\left(\left\langle
W^{(T)}_{i,:},x\right\rangle-\left\langle W^{(0)}_{i,:},x\right\rangle\right)$
and the second inequality uses $r\geq 3,\left(1-O(\delta^{r})\right)\geq 2/3.$
To prove $\left\langle
W^{(0)}_{i,:},x\right\rangle\leq\alpha\left(\left\langle
W^{(T)}_{i,:},x\right\rangle-\left\langle
W^{(0)}_{i,:},x\right\rangle\right)$, it’s equivalent to show $\left\langle
W^{(0)}_{i,:},x\right\rangle\leq\frac{\alpha}{1+\alpha}\left\langle
W^{(T)}_{i,:},x\right\rangle.$ Since
$\alpha\geq\alpha_{2}=\left(\frac{1}{1+O(\sqrt{\delta})}\right)^{\frac{r}{r-1}}R_{\min}^{\frac{1}{r-1}}$,
we can lower bound $\frac{\alpha}{1+\alpha}$ as follows,

$\displaystyle\frac{\alpha}{1+\alpha}\geq$
$\displaystyle\frac{1}{2}\left(\frac{1}{1+O(\sqrt{\delta})}\right)^{\frac{r}{r-1}}R_{\min}^{\frac{1}{r-1}}$
$\displaystyle\geq$ $\displaystyle\frac{1}{8}R_{\min}^{\frac{1}{r-1}},$

where the first inequality uses $\alpha\leq 1$ and the second inequality uses
$1+O(\sqrt{\delta})\leq 2,r\geq 2.$ So we have
$\frac{\alpha}{1+\alpha}\left\langle
W^{(T)}_{i,:},x\right\rangle\geq\frac{1}{8}R_{\min}^{\frac{1}{r-1}}\Delta_{\min}^{1/r}.$
Therefore, we only need $\delta\leq
O\left(R_{\min}^{\frac{1}{r-1}}\Delta_{\min}^{1/r}\right)$ to ensure that
$\left\langle W^{(0)}_{i,:},x\right\rangle\leq\alpha\left(\left\langle
W^{(T)}_{i,:},x\right\rangle-\left\langle
W^{(0)}_{i,:},x\right\rangle\right)$. $\Box$

###  B.2 Loss interpolation for $r$-homogeneous-weight model

In this section, we give a proof of Theorem 5.

######  Theorem 5 (Loss Interpolation).

Suppose the network at initialization and after training satisfy the
properties described in Theorem 2 and Induction Hypothesis 1. For any
$\epsilon\in(0,1),$ suppose $\delta\leq O(\epsilon^{1/r}),$ there exist
$\alpha_{3}=\frac{\epsilon^{1/r}}{W_{\max}}$ and
$\alpha_{4}=\left(1+O(\delta)\right)^{\frac{1}{r-1}}\left(\frac{R_{\max}}{r}\right)^{\frac{1}{r-1}}$
such that

  1. 1.

for all $\alpha\in[0,\alpha_{3}]$, we have $\log
k-e\epsilon\leq\frac{1}{N}L(W^{[\alpha]},b^{[\alpha]})\leq\log
k+\alpha\Delta_{\max}+e\epsilon;$

  2. 2.

for all $\alpha\in[\alpha_{4},1]$, the loss is monotonically decreasing.

Proof of Theorem 5. This theorem directly follows from Lemma 6 and Lemma 7.
$\Box$

Next, we prove the initial loss plateau in Lemma 6 and the monotonicity in
Lemma 7.

######  Lemma 6 (Loss Plateau).

In the same setting as in Theorem 5, for any $\epsilon>0,$ there exists
$\alpha_{3}=\frac{\epsilon^{1/r}}{W_{\max}}$ such that for all
$\alpha\in[0,\alpha_{3}]$

$\displaystyle N\left(\log k-e\epsilon\right)\leq
L(W^{[\alpha]},b^{[\alpha]})\leq N\left(\log
k+\alpha\Delta_{\max}+e\epsilon\right).$

We show that for $\alpha\in[0,\alpha_{3}],$ the weights $W^{[\alpha]}$ is
negligible and the bias dominates, which then gives a lower bound and an upper
bound of the loss.

Proof of Lemma 6. Since $\alpha\leq\alpha_{3}=\frac{\epsilon^{1/r}}{W_{\max}}$
and $\delta\leq O\left(\epsilon^{1/r}\right),$ we have

$\displaystyle\left[\left\langle
W^{[\alpha]}_{i,:},x\right\rangle\right]^{r}=\left[\left\langle
W^{(0)}_{i,:},x\right\rangle+\alpha(\left\langle
W^{(T)}_{i,:},x\right\rangle-\left\langle
W^{(0)}_{i,:},x\right\rangle)\right]^{r}\leq\left[\left(1+\frac{1}{r}\right)\epsilon^{1/r}\right]^{r}\leq
e\epsilon,$

for all $i\in[k],x\in\mathcal{S}.$

We can divide the dataset $\mathcal{S}$ into $N/k$ disjoint subsets
$\\{P_{l}\\}_{l=1}^{N/k}$ where each $P_{l}$ contains exactly one sample from
each class. Next, we bound the total loss of each subset $P_{l}.$ Without loss
of generality, let’s consider subset $P_{1}$ and suppose $x^{(i)}$ is the
$i$-th class sample in this subset. For convenience, we denote the total loss
of samples in $P_{1}$ as $L_{1}(W^{[\alpha]},b^{[\alpha]}).$

#### Lower bounding $L_{1}(W^{[\alpha]},b^{[\alpha]}).$

We have

$\displaystyle L_{1}(W^{[\alpha]},b^{[\alpha]})=$
$\displaystyle\sum_{i\in[k]}\log\left(\frac{\sum_{j\in[k]}\exp\left(f^{[\alpha]}_{j}(x^{(i)})\right)}{\exp\left(f^{[\alpha]}_{i}(x^{(i)})\right)}\right)$
$\displaystyle=$
$\displaystyle\log\left(\prod_{i\in[k]}\frac{\sum_{j\in[k]}\exp\left(f^{[\alpha]}_{j}(x^{(i)})\right)}{\exp\left(f^{[\alpha]}_{i}(x^{(i)})\right)}\right)$
$\displaystyle\geq$
$\displaystyle\log\left(\left(\frac{k}{\sum_{i\in[k]}\frac{\exp\left(f^{[\alpha]}_{i}(x^{(i)})\right)}{\sum_{j\in[k]}\exp\left(f^{[\alpha]}_{j}(x^{(i)})\right)}}\right)^{k}\right),$

where the last inequality uses the HM-GM inequality. We can then upper bound
$\sum_{i\in[k]}\frac{\exp\left(f^{[\alpha]}_{i}(x^{(i)})\right)}{\sum_{j\in[k]}\exp\left(f^{[\alpha]}_{j}(x^{(i)})\right)}$
as follows,

$\displaystyle\sum_{i\in[k]}\frac{\exp\left(f^{[\alpha]}_{i}(x^{(i)})\right)}{\sum_{j\in[k]}\exp\left(f^{[\alpha]}_{j}(x^{(i)})\right)}=$
$\displaystyle\sum_{i\in[k]}\frac{\exp\left(\left[\left\langle
W^{[\alpha]}_{i,:},x^{(i)}\right\rangle\right]^{r}+\alpha
b_{i}\right)}{\sum_{j\in[k]}\exp\left(\left[\left\langle
W^{[\alpha]}_{j,:},x^{(i)}\right\rangle\right]^{r}+\alpha b_{j}\right)}$
$\displaystyle\leq$ $\displaystyle\sum_{i\in[k]}\frac{\exp\left(\alpha
b_{i}+e\epsilon\right)}{\sum_{j\in[k]}\exp\left(\alpha b_{j}\right)}$
$\displaystyle=$ $\displaystyle\frac{\sum_{i\in[k]}\exp\left(\alpha
b_{i}\right)}{\sum_{j\in[k]}\exp\left(\alpha
b_{j}\right)}\exp\left(e\epsilon\right)$ $\displaystyle=$
$\displaystyle\exp\left(e\epsilon\right).$

Plugging back to the lower bound of $L_{1}(W^{[\alpha]},b^{[\alpha]}),$ we
have

$\displaystyle L_{1}(W^{[\alpha]},b^{[\alpha]})\geq
k\log\left(\frac{k}{\exp\left(e\epsilon\right)}\right)=k\left(\log
k-e\epsilon\right).$

#### Upper bounding $L_{1}(W^{[\alpha]},b^{[\alpha]}).$

We have

$\displaystyle L_{1}(W^{[\alpha]},b^{[\alpha]})=$
$\displaystyle\sum_{i\in[k]}\log\left(\frac{\sum_{j\in[k]}\exp\left(f^{[\alpha]}_{j}(x^{(i)})\right)}{\exp\left(f^{[\alpha]}_{i}(x^{(i)})\right)}\right)$
$\displaystyle\leq$
$\displaystyle\sum_{i\in[k]}\log\left(\frac{\sum_{j\in[k]}\exp\left(\alpha
b_{j}+e\epsilon\right)}{\exp\left(\alpha b_{i}\right)}\right)$
$\displaystyle\leq$ $\displaystyle
k\log\left(k\exp\left(\alpha\Delta_{\max}+e\epsilon\right)\right)$
$\displaystyle\leq$ $\displaystyle k\left(\log
k+\alpha\Delta_{\max}+e\epsilon\right)$

The above analysis applies for every subset $P_{l},$ so we have

$\displaystyle N\left(\log k-e\epsilon\right)\leq
L(W^{[\alpha]},b^{[\alpha]})\leq N\left(\log
k+\alpha\Delta_{\max}+e\epsilon\right).$

$\Box$

Next we show that when $\alpha$ is reasonably large, we have
$f^{[\alpha]}_{i}(e_{i})-f^{[\alpha]}_{j}(e_{i})$ increasing for all $i\neq
j$, which then implies that the loss is decreasing.

######  Lemma 7 (Loss Monotonicity).

In the same setting as in Theorem 5, there exists
$\alpha_{4}=\left(1+O(\delta)\right)^{\frac{1}{r-1}}\left(\frac{R_{\max}}{r}\right)^{\frac{1}{r-1}}$
such that the loss is monotonically decreasing for $\alpha\in[\alpha_{4},1].$

Proof of Lemma 7. To prove that the loss is monotonically decreasing, we only
need to show that for any $i\in[k]$ and any $x\in\mathcal{S}_{i}$,
$f^{[\alpha]}_{i}(x)-f^{[\alpha]}_{j}(x)$ is monotonically increasing for
$j\neq i.$

Same as in Lemma 5, it’s easy to prove that for $x\in\mathcal{S}_{k},$
$f_{k}(x)-f_{j}(x)$ with $j\neq k$ monotonically increases for
$\alpha\in[0,1].$ So we focus on other classes.

For $i\neq k,$ we show that
$\frac{\partial}{\partial\alpha}\left(f^{[\alpha]}_{i}(x)-f^{[\alpha]}_{j}(x)\right)>0$
for $x\in\mathcal{S}_{i}$ when $\alpha\geq\alpha_{4},$

$\displaystyle\frac{\partial}{\partial\alpha}\left(f^{[\alpha]}_{i}(e_{i})-f^{[\alpha]}_{j}(e_{i})\right)$
$\displaystyle=$
$\displaystyle\frac{\partial}{\partial\alpha}\left(\left[(1-\alpha)\left\langle
W^{(0)}_{i,:},x\right\rangle+\alpha\left\langle
W^{(T)}_{i,:},x\right\rangle\right]^{r}-\left[(1-\alpha)\left\langle
W^{(0)}_{j,:},x\right\rangle+\alpha\left\langle
W^{(T)}_{j,:},x\right\rangle\right]^{r}+\alpha\left(b^{(T)}_{i}-b^{(T)}_{j}\right)\right)$
$\displaystyle\geq$ $\displaystyle r\left[(1-\alpha)\left\langle
W^{(0)}_{i,:},x\right\rangle+\alpha\left\langle
W^{(T)}_{i,:},x\right\rangle\right]^{r-1}\left(\left\langle
W^{(T)}_{i,:},x\right\rangle-\left\langle
W^{(0)}_{i,:},x\right\rangle\right)-\left(b^{(T)}_{k}-b^{(T)}_{i}\right)-O(\delta^{r})$
$\displaystyle\geq$ $\displaystyle r\alpha^{r-1}\left[\left\langle
W^{(T)}_{i,:},x\right\rangle\right]^{r-1}\left(\left\langle
W^{(T)}_{i,:},x\right\rangle-\left\langle
W^{(0)}_{i,:},x\right\rangle\right)-\left(b^{(T)}_{k}-b^{(T)}_{i}\right)-O(\delta^{r})$
$\displaystyle\geq$ $\displaystyle
r\alpha^{r-1}\left(1-O\left(\frac{\delta}{\Delta_{\min}^{1/r}}\right)\right)\left[\left\langle
W^{(T)}_{i,:},x\right\rangle\right]^{r}-\left(b^{(T)}_{k}-b^{(T)}_{i}\right)(1+O(\delta^{r}))$
$\displaystyle>$ $\displaystyle 0,$

where the second last inequality uses $\left\langle
W^{(0)}_{i,:},x\right\rangle/\left\langle W^{(T)}_{i,:},x\right\rangle\leq
O\left(\delta/\Delta_{\min}^{1/r}\right)$. The last inequality requires

$\displaystyle
r\alpha^{r-1}\geq\left(1+O(\delta)\right)\frac{b^{(T)}_{k}-b^{(T)}_{i}}{\left[W^{(T)}_{i,i}\right]^{r}}$

which is satisfied as long as
$\alpha\geq\left(1+O(\delta)\right)^{\frac{1}{r-1}}\left(\frac{R_{\max}}{r}\right)^{\frac{1}{r-1}}$
where $R_{\max}=\max_{i\in[k-1]}\Delta_{i}/[W^{(T)}_{i,i}]^{r}.$. $\Box$

###  B.3 Plateau for deep fully-connected networks

In this section, we consider fully-connected neural networks as defined in
Section 3 and prove that both the error and loss curves have plateau. We
restate Theorem 1 as follows. See 1 Proof of Theorem 1. This theorem directly
follows from Lemma 8 and Lemma 9. $\Box$

We separately prove the plateau of error interpolation in Lemma 8 and the
plateau of loss interpolation in Lemma 9. Then, Theorem 1 is simply a
combination of Lemma 8 and Lemma 9. For convenience, we denote
$h(x):=V_{r}\sigma\left(V_{r-1}\cdots\sigma(V_{1}x)\cdots\right)$ in the
proof.

######  Lemma 8.

In the setting of Theorem 1, there exist
$\alpha_{1}=\frac{\delta}{\Delta_{\min}}$ and
$\alpha_{2}=\left(\frac{1}{1+\sqrt{\delta}}\right)^{\frac{r}{r-1}}\left(\frac{\Delta_{\min}}{2V_{\max}^{r}}\right)^{\frac{1}{r-1}}$
such that the error is $1-1/k$ for any interpolation point
$\alpha\in[\alpha_{1},\alpha_{2}].$

Proof of Lemma 8. Recall that the network output under input $x$ is
$g(x):=V_{r}\sigma\left(V_{r-1}\cdots\sigma(V_{1}x)\cdots\right)+b$. Similar
as in the proof of Lemma 4, we only need to show that for all
$\alpha\in[\alpha_{1},\alpha_{2}],$ we have

$\displaystyle g^{[\alpha]}_{i}(x)<g^{[\alpha]}_{k}(x)$

for all $i\neq k$ and all samples $x$, which immediately implies the error is
$1-1/k.$

#### For $\alpha\in\left[\alpha_{1},\frac{\sqrt{\delta}}{V_{\max}}\right)$.

If
$\alpha_{1}=\frac{\delta}{\Delta_{\min}}\geq\frac{\sqrt{\delta}}{V_{\max}}$,
we only need to consider the case when
$\alpha\in\left[\frac{\sqrt{\delta}}{V_{\max}},\alpha_{2}\right].$ So here we
assume $\frac{\delta}{\Delta_{\min}}<\frac{\sqrt{\delta}}{V_{\max}}.$ We can
lower bound $g^{[\alpha]}_{k}(x)-g^{[\alpha]}_{i}(x)$ as

$\displaystyle g^{[\alpha]}_{k}(x)-g^{[\alpha]}_{i}(x)$
$\displaystyle=h^{[\alpha]}_{k}(x)+b^{[\alpha]}_{k}-h^{[\alpha]}_{i}(x)-b^{[\alpha]}_{i}$
$\displaystyle\geq\alpha\Delta_{\min}-2\prod_{j\in[r]}\left\|(1-\alpha)V^{(0)}_{j}+\alpha
V^{(T)}_{j}\right\|$
$\displaystyle\geq\alpha\Delta_{\min}-2\left(\delta+\alpha
V_{\max}\right)^{r},$

where the first inequality holds because
$b^{[\alpha]}_{k}-b^{[\alpha]}_{i}\geq\alpha\Delta_{\min}$ and
$\left|h^{[\alpha]}_{k}(x)\right|,\left|h^{[\alpha]}_{i}(x)\right|\leq\prod_{j\in[r]}\left\|(1-\alpha)V^{(0)}_{j}+\alpha
V^{(T)}_{j}\right\|.$ The second inequality uses
$\left\|(1-\alpha)V^{(0)}_{j}+\alpha
V^{(T)}_{j}\right\|\leq(1-\alpha)\left\|V^{(0)}_{j}\right\|+\alpha\left\|V^{(T)}_{j}\right\|\leq\delta+\alpha
V_{\max}.$

Since
$\alpha\in\left[\frac{\delta}{\Delta_{\min}},\frac{\sqrt{\delta}}{V_{\max}}\right),$
we have

$\displaystyle g^{[\alpha]}_{k}(x)-g^{[\alpha]}_{i}(x)\geq$
$\displaystyle\frac{\delta}{\Delta_{\min}}\Delta_{\min}-2\left(\delta+\frac{\sqrt{\delta}}{V_{\max}}V_{\max}\right)^{r},$
$\displaystyle\geq$
$\displaystyle\delta-2\left(\left(1+\frac{1}{r}\right)\sqrt{\delta}\right)^{r},$
$\displaystyle\geq$ $\displaystyle\delta-2e\delta^{r/2}$ $\displaystyle>$
$\displaystyle 0,$

where the second inequality assumes $\delta\leq 1/r^{2}$ and the last
inequality assumes $\delta<\left(\frac{1}{2e}\right)^{\frac{2}{r-2}}.$

#### For $\alpha\in\left[\frac{\sqrt{\delta}}{V_{\max}},\alpha_{2}\right]$.

Similar as above, we only need to show that
$\alpha\Delta_{\min}-2\left(\delta+\alpha V_{\max}\right)^{r}>0$. Since
$\alpha\geq\frac{\sqrt{\delta}}{V_{\max}},$ we have
$\delta\leq\sqrt{\delta}\alpha V_{\max}.$ Therefore, we have

$\displaystyle\alpha\Delta_{\min}-2\left(\delta+\alpha
V_{\max}\right)^{r}\geq\alpha\Delta_{\min}-2\left(\left(1+\sqrt{\delta}\right)\alpha
V_{\max}\right)^{r}>0,$

where the second inequality holds as long as
$\alpha\leq\alpha_{2}:=\left(\frac{1}{2}\right)^{\frac{1}{r-1}}\left(\frac{1}{1+\sqrt{\delta}}\right)^{\frac{r}{r-1}}\left(\frac{\Delta_{\min}}{V_{\max}^{r}}\right)^{\frac{1}{r-1}}.$
$\Box$

Next, we show that for $\alpha\in[0,\frac{\epsilon^{1/r}}{V_{\max}}],$ the
loss cannot decrease by much. Similar as in Lemma 6, we prove that the signal
is very small and the logit is dominated by the bias term. This then gives a
lower and upper bounds for the loss.

######  Lemma 9.

In the setting of Theorem 1, there exists
$\alpha_{3}=\frac{\epsilon^{1/r}}{V_{\max}}$ such that for all
$\alpha\in[0,\alpha_{3}]$

$\displaystyle\log
k-2e\epsilon\leq\frac{1}{N}L\left(\left\\{V^{[\alpha]}_{i}\right\\},b^{[\alpha]}\right)\leq\log
k+\alpha\Delta_{\max}+2e\epsilon,$

where $N$ is the number of samples.

Proof of Lemma 9. Since $\alpha\leq\alpha_{3}=\frac{\epsilon^{1/r}}{V_{\max}}$
and $\delta\leq\frac{\epsilon^{1/r}}{r},$ we have

$\displaystyle\left\|h^{[\alpha]}(x)\right\|\leq\left(\delta+\alpha
V_{\max}\right)^{r}\leq e\epsilon$

for all input $x.$

Similar as in the proof of Lemma 6, we can show that

$\displaystyle\log
k-2e\epsilon\leq\frac{1}{N}L\left(\left\\{V^{[\alpha]}_{i}\right\\},b^{[\alpha]}\right)\leq\log
k+\alpha\Delta_{\max}+2e\epsilon,$

where we have an additional factor of $2$ before $e\epsilon$ because now the
signal can be positive or negative. Here $N$ is the number of samples. $\Box$

##  Appendix C Proof of training dynamics

In this section, we give the complete proof of Theorem 2. See 2 Proof of
Theorem 2. This theorem directly follows from Proposition 1. $\Box$

We consider the $r$-homogeneous-weight network as defined in Section 4. Our
simple model simulates a depth-$r$ ReLU/linear network with bias on the output
layer, in the sense that the weights signal is $r$-homogeneous while the bias
is $1$-homogeneous in the parameters.

Next, we prove Proposition 1 while leaving the proof of supporting lemmas into
Section C.1. Through the proof of Proposition 1, we restate the lemmas when we
use it for the convenience of readers.

See 1 Proof of Proposition 1. Through the proof, we assume the conditions in
Theorem 2 hold in all the lemmas without explicitly stated. At the
initialization, we have the following properties with probability at least
$0.99$.

######  Lemma 10 (Initialization).

With probability at least $0.99$ in the initialization, we have

  1. 1.

for all $j,j^{\prime}\in[k]$, $W^{(0)}_{j,j^{\prime}}=\Theta(\delta)$;

  2. 2.

for all distinct $j,j^{\prime}\in[k]$,
$\left|W^{(0)}_{j,j}-W^{(0)}_{j^{\prime},j^{\prime}}\right|=\Theta(\delta);$

  3. 3.

for all $x\in\mathcal{S},$ $\left\|\xi_{x}\right\|\leq O(\sigma);$

  4. 4.

for all distinct $x,x^{\prime}\in\mathcal{S},$
$\left|\left\langle\bar{\xi}_{x},\bar{\xi}_{x^{\prime}}\right\rangle\right|\leq
O\left(\frac{\sqrt{\log(N)}}{\sqrt{d}}\right).$

  5. 5.

for all $j\in[k]$ and all $x\in\mathcal{S},$
$\left|\left\langle\bar{\xi}_{x},e_{j}\right\rangle\right|,\left|\left\langle\bar{\xi}_{x},\bar{W}_{j,:}^{(0)}\right\rangle\right|\leq
O\left(\frac{\sqrt{\log(N)}}{\sqrt{d}}\right).$

Without loss of generality, we assume
$W^{(0)}_{1,1}>W^{(0)}_{2,2}>\cdots>W^{(0)}_{k,k}.$

It’s not hard to verify that the induction hypothesis holds at the
initialization 444We will maintain a stronger bound on $\left|\left\langle
W^{(t)}_{j,:},\xi_{x}\right\rangle\right|$ by proving $\left|\left\langle
W^{(t)}_{j,:},\xi_{x}\right\rangle\right|\leq O(\sqrt{\log N}\sigma\delta)$,
which implies $\left|\left\langle
W^{(t)}_{j,:},\xi_{x}\right\rangle\right|\leq O(\delta)$ as long as
$\sigma\leq O(1/\sqrt{\log N}).$. For any $i\in[k-1],$ assuming the induction
hypothesis holds for time $[0,s_{i}],$ now we prove that it continues to hold
in $[s_{i},s_{i+1}].$ Next, we first prove the first two properties in the
Proposition 1 and leave the last one at the end.

The learning of $x\in\mathcal{S}_{i}$ can be divided into four stages:

  1. 1.

Stage 0 for $t\in[s_{i},t_{i}]$ with
$t_{i}-s_{i}=O(\log(1/\delta)/\delta^{r-2}).$ During this stage,
$W^{(t)}_{i,i}$ grows to a small constant $\mu_{0}$.

  2. 2.

Stage 1 for $t\in[t_{i},t_{i}^{(w)}]$ with $t_{i}^{(w)}-t_{i}=O(1).$ In this
stage, $W^{(t)}_{i,i}$ grows from $\mu_{0}$ to a large constant $\mu_{1}$.

  3. 3.

Stage 2 for $t\in[t_{i}^{(w)},t_{i}^{(u)}]$ with
$t_{i}^{(u)}-t_{i}^{(w)}=O(1).$ At the end of this stage, we have
$\min_{x\in\mathcal{S}_{i}}u^{(t)}_{i}(x)\geq 1-\mu_{2}$ for a small constant
$\mu_{2}$.

  4. 4.

Stage 3 for $t\in[t_{i}^{(u)},t_{i}^{(b)}]$ with
$t_{i}^{(b)}-t_{i}^{(u)}=O(1)$, where $t_{i}^{(b)}=s_{i+1}$. During this
stage, we have $b^{(t)}_{i}-b^{(t)}_{k}$ decreases to $-\mu_{3}$ with
$\mu_{3}$ a positive constant.

Next, we consider these four stages one by one.

#### Stage 0.

We show that $W^{(t)}_{i,i}$ increases faster than $W^{(t)}_{i+1,i+1}$ so that
$W^{(t)}_{i,i}$ reaches a constant while $W^{(t)}_{i+1,i+1}$ is still
$O(\delta).$ We use the following lemma to characterize the increasing rate of
$W^{(t)}_{i+1,i+1}$ and $W^{(t)}_{i,i}$.

######  Lemma 11.

For any $j\in[k],$ we have

$\frac{\partial W^{(t)}_{j,j}}{\partial
t}\geq-O\left(\frac{\delta^{r-1}\sqrt{\log N}\sigma}{\sqrt{d}}\right).$

If $\min_{x\in\mathcal{S}_{j}}\left(1-u_{j}(x)\right)\geq\Omega(1)$, we
further have

$\left(1-O(\sqrt{\log
N}\sigma)\right)\frac{k}{N}\sum_{x\in\mathcal{S}_{j}}\left(1-u_{j}(x)\right)rW_{j,j}^{r-1}\leq\frac{\partial
W^{(t)}_{j,j}}{\partial t}\leq\left(1+O(\sqrt{\log
N}\sigma)\right)\frac{k}{N}\sum_{x\in\mathcal{S}_{j}}\left(1-u_{j}(x)\right)rW_{j,j}^{r-1}.$

It’s not hard to verify that
$\min_{x\in\mathcal{S}_{i}}\left(1-u^{(t)}_{i}(x)\right),\min_{x\in\mathcal{S}_{i+1}}\left(1-u^{(t)}_{i+1}(x)\right)\geq\Omega(1)$,
so we have

$\displaystyle\frac{\partial W^{(t)}_{i,i}}{\partial t}$
$\displaystyle\geq\left(1-O(\sqrt{\log
N}\sigma)\right)\frac{k}{N}\sum_{x\in\mathcal{S}_{i}}\left(1-u^{(t)}_{i}(x)\right)r\left[W^{(t)}_{i,i}\right]^{r-1},$
$\displaystyle\frac{\partial W^{(t)}_{i+1,i+1}}{\partial t}$
$\displaystyle\leq\left(1+O(\sqrt{\log
N}\sigma)\right)\frac{k}{N}\sum_{x\in\mathcal{S}_{i+1}}\left(1-u^{(t)}_{i+1}(x)\right)r\left[W^{(t)}_{i+1,i+1}\right]^{r-1}.$

We can upper bound $1-u^{(t)}_{i+1}(x)$ for any $x\in\mathcal{S}_{i+1}$ as
follows,

$\displaystyle 1-u^{(t)}_{i+1}(x)=$
$\displaystyle\frac{\sum_{i^{\prime}\in[k]}\exp\left(f^{(t)}_{i^{\prime}}(x)\right)-\exp\left(f^{(t)}_{i+1}(x)\right)}{\sum_{i^{\prime}\in[k]}\exp\left(f^{(t)}_{i^{\prime}}(x)\right)}$
$\displaystyle\leq$
$\displaystyle\frac{\sum_{i^{\prime}\in[k]}\exp\left(b^{(t)}_{i^{\prime}}\right)-\exp\left(b^{(t)}_{i+1}\right)}{\sum_{i^{\prime}\in[k]}\exp\left(b^{(t)}_{i^{\prime}}\right)}\left(1+O(\delta^{r})\right),$

where the inequality uses $\left|\left\langle
W^{(t)}_{i^{\prime},:},x\right\rangle\right|\leq O(\delta)$ for every
$i^{\prime}\in[k].$

We can lower bound $1-u^{(t)}_{i}(x)$ for $x\in\mathcal{S}_{i}$ as follows,

$\displaystyle 1-u^{(t)}_{i}(x)=$
$\displaystyle\frac{\sum_{i^{\prime}\in[k]}\exp\left(f^{(t)}_{i^{\prime}}(x)\right)-\exp\left(f^{(t)}_{i}(x)\right)}{\sum_{i^{\prime}\in[k]}\exp\left(f^{(t)}_{i^{\prime}}(x)\right)}$
$\displaystyle\geq$
$\displaystyle\frac{\sum_{i^{\prime}\in[k]}\exp\left(b^{(t)}_{i^{\prime}}\right)-\exp\left(b^{(t)}_{i}\right)}{\sum_{i^{\prime}\in[k]}\exp\left(b^{(t)}_{i^{\prime}}\right)}\left(1-O(\mu_{0}^{r})\right)$
$\displaystyle\geq$
$\displaystyle\frac{\sum_{i^{\prime}\in[k]}\exp\left(b^{(t)}_{i^{\prime}}\right)-\exp\left(b^{(t)}_{i+1}\right)}{\sum_{i^{\prime}\in[k]}\exp\left(b^{(t)}_{i^{\prime}}\right)}\left(1-O(\mu_{0}^{r})-O(\delta^{r})\right).$

The first inequality uses $\left|\left\langle
W^{(t)}_{i^{\prime},:},x\right\rangle\right|\leq O(\mu_{0})$ for every
$i^{\prime}\in[k].$ The second inequality uses $b^{(t)}_{i}\leq
b^{(t)}_{i+1}+O(\delta^{r})$, which is guaranteed by the following lemma. See
2

According to Lemma 10, we know there exists constant $C>1$ such that
$W^{(0)}_{i,i}\geq CW^{(0)}_{i+1,i+1}.$ Choose constant $S$ such that
$S^{\frac{1}{r-2}}=\sqrt{C}$ and $W^{(0)}_{i,i}\geq
S^{\frac{1}{r-2}}\sqrt{C}W^{(0)}_{i+1,i+1}.$ Choosing $\mu_{0}$ as small
constants and $\sigma\leq O(1/\sqrt{\log N}),\delta\leq O(1)$, we have

$\displaystyle\left(1+O(\sqrt{\log
N}\sigma)\right)\max_{x\in\mathcal{S}_{i+1}}\left(1-u^{(t)}_{i+1}(x)\right)\leq
S\left(1-O(\sqrt{\log
N}\sigma)\right)\min_{x\in\mathcal{S}_{i}}\left(1-u^{(t)}_{i}(x)\right).$

We can also lower bound $1-u^{(t)}_{i}(x)$ for $x\in\mathcal{S}_{i}$ by a
constant,

$\displaystyle 1-u^{(t)}_{i}(x)\geq$
$\displaystyle\frac{\sum_{i^{\prime}\in[k]}\exp\left(b^{(t)}_{i^{\prime}}\right)-\exp\left(b^{(t)}_{i}\right)}{\sum_{i^{\prime}\in[k]}\exp\left(b^{(t)}_{i^{\prime}}\right)}\left(1-O(\mu_{0}^{r})\right)$
$\displaystyle\geq$
$\displaystyle\frac{\exp\left(b^{(t)}_{i+1}\right)}{\sum_{i^{\prime}\in[k]}\exp\left(b^{(t)}_{i^{\prime}}\right)}\left(1-O(\mu_{0}^{r})\right)$
$\displaystyle\geq$ $\displaystyle\Omega(1),$

where the last inequality holds because $\mu_{0}$ is a small constant and
$b^{(t)}_{i+1}\geq\max_{i^{\prime}\in[k]}b^{(t)}_{i^{\prime}}-O(\delta^{r}).$

######  Lemma 12 (Adapted from Lemma C.19 in Allen-Zhu & Li (2020)).

Let $r\geq 3$ be a constant and let $\\{W^{(t)}_{i,i},W^{(t)}_{j,j}\\}_{t\geq
0}$ be two positive sequences updated as

$\displaystyle\frac{\partial W^{(t)}_{i,i}}{\partial t}\geq
C_{t}\left[W^{(t)}_{i,i}\right]^{r-1}\text{ for some }C_{t}=\Theta(1),$
$\displaystyle\frac{\partial W^{(t)}_{j,j}}{\partial t}\leq
SC_{t}\left[W^{(t)}_{j,j}\right]^{r-1}\text{ for some }S=\Theta(1).$

Suppose $W^{(0)}_{i,i}\geq
W^{(0)}_{j,j}S^{\frac{1}{r-2}}\left(1+\Omega(1)\right),$ then we must have for
every $A=O(1),$ let $t_{i}$ be the first time such that $W^{(t_{i})}_{i,i}\geq
A,$ then

$\displaystyle W^{(t_{i})}_{j,j}\leq O(W^{(0)}_{j,j}).$

Then, according to Lemma 12, we know that there exists
$t_{i}=O(\log(1/\delta)/\delta^{r-2})$ such that $W^{(t_{i})}_{i,i}=\mu_{0}$
and $W^{(t_{i})}_{i+1,i+1}\leq O(\delta).$ By similar argument, we also know
$W^{(t_{i})}_{j,j}\leq O(\delta)$ for any $j\geq i+1.$

#### Stage 1.

In this stage, we show that $W^{(t)}_{i,i}$ grows to a large constant
$\mu_{1}$ within constant time. Since $W^{(t)}_{i,i}\leq\mu_{1}$ and
$b^{(t)}_{i,i}\leq b^{(t)}_{i+1,i+1}+O(\delta^{r}),$ we have

$\displaystyle 1-u^{(t)}_{i}\left(x\right)\geq\Omega(1),$

for all $x\in\mathcal{S}_{i}.$ This further implies,

$\displaystyle\frac{\partial W^{(t)}_{i,i}}{\partial t}\geq$
$\displaystyle\left(1-O(\sqrt{\log
N}\sigma)\right)\frac{k}{N}\sum_{x\in\mathcal{S}_{i}}\left(1-u^{(t)}_{i}(x)\right)r\left[W^{(t)}_{i,i}\right]^{r-1}$
$\displaystyle\geq$ $\displaystyle\Omega(1),$

where the inequality also uses $W^{(t)}_{i,i}\geq\mu_{0}.$ Since the
increasing rate is at least a constant, we know $W^{(t)}_{i,i}$ grows to
$\mu_{1}$ in constant time. For any $j\geq i+1,$ since the increasing rate of
$W^{(t)}_{j,j}$ is merely $O(\delta^{r-1}),$ we know $W^{(t)}_{j,j}$ remains
as $O(\delta)$ through Stage 1.

#### Stage 2.

In this stage, we prove that $u^{(t)}_{i}(x)$ for any $x\in\mathcal{S}_{i}$
grows to $1-\mu_{2}$ with $\mu_{2}$ a small constant. We use the following
lemma to characterize the increasing rate of $f^{(t)}_{i}(x)-f^{(t)}_{j}(x)$.

######  Lemma 13.

For any $x\in\mathcal{S}_{i}$ and any $j\neq i,$ if $1-u_{i}(x)\geq\Omega(1)$,
we have

$\displaystyle\frac{\partial}{\partial
t}\left(f_{i}(x)-f_{j}(x)\right)\geq\Omega(W_{i,i}^{2r-2})-O(1).$

Since $u^{(t)}_{i}(x)\leq 1-\mu_{2},$ we know $1-u^{(t)}_{i}(x)\geq\Omega(1)$.
For any $j\neq i,$ we have

$\displaystyle\frac{\partial}{\partial
t}\left(f^{(t)}_{i}(x)-f^{(t)}_{j}(x)\right)\geq$
$\displaystyle\Omega\left(\left[W^{(t)}_{i,i}\right]^{2r-2}\right)-O(1)$
$\displaystyle\geq$ $\displaystyle\Omega(1),$

where the last inequality holds because $W^{(t)}_{i,i}\geq\mu_{1}$ with
$\mu_{1}$ a large enough constant.

The next lemma guarantees that at the beginning of Stage 2, we have
$b^{(t)}_{i}-b^{(t)}_{j}\geq-O(1),$ which then implies
$f^{(t)}_{i}(x)-f^{(t)}_{j}(x)\geq-O(1).$

######  Lemma 14 (Bias Gap Control III).

For any different $i,j\in[k]$, if $W_{i,i}\leq O(1),W_{j,j}\leq O(\delta)$ and
$b_{i}-b_{j}\leq-O(1),$ we have

$\displaystyle\dot{b}_{i}-\dot{b}_{j}>0.$

Let $C$ be a constant such that $f^{(t)}_{i}(x)-f^{(t)}_{j}(x)\geq C$ for
every $j\neq i$ implies $u_{i}(x)\geq 1-\mu_{2}.$ Since at the at the
beginning of Stage 2, we have $f^{(t)}_{i}(x)-f^{(t)}_{j}(x)\geq-O(1),$ within
constant time, we have $f^{(t)}_{i}(x)-f^{(t)}_{j}(x)\geq C$ for every $j\neq
i$ and $u_{i}(x)\geq 1-\mu_{2}.$

######  Lemma 15 (Accuracy Monotonicity).

Given any positive constant $C_{2},$ there exists positive constant $C_{1}$
such that for all different $i,j\in[k],$ as long as $W_{i,i}\geq C_{1}$ and
$f_{i}(x)-f_{j}(x)\leq C_{2}$ for any $x\in\mathcal{S}_{i},$ we have
$\frac{\partial\left(f_{i}(x)-f_{j}(x)\right)}{\partial t}>0.$

According to Lemma 15, by choosing large enough $\mu_{1},$ we can ensure that
$f^{(t)}_{i}(e_{i})-f^{(t)}_{j}(e_{i})\geq C$ and $u_{i}(e_{i})\geq 1-\mu_{2}$
throughout the training. Note that once $W^{(t)}_{i,i}$ rises to $\mu_{1}$, it
will stay at least $\mu_{1}-O(\delta)$ throughout the training, according to
the gradient lower bound in Lemma 11.

#### Stage 3.

In this stage, we prove that within constant time we have
$b^{(t)}_{i}-b^{(t)}_{k}\leq-\mu_{3}.$ The following lemma shows that
$b^{(t)}_{i}-b^{(t)}_{k}$ decreases in at least a constant rate. See 3
Choosing $\mu_{2}=C_{1},\mu_{3}=C_{2}$ where $C_{1},C_{2}$ are from Lemma 3,
so we know that $b^{(t)}_{i}-b^{(t)}_{k}$ decreases at a constant rate until
$b^{(t)}_{i}-b^{(t)}_{k}\leq-\mu_{3}.$ At time $t_{i}^{(u)},$ we know that
$b^{t_{i}^{(u)}}_{i}-b^{t_{i}^{(u)}}_{k}\leq O(\delta^{r}).$ So within
constant time, we have $b^{s_{i+1}}_{i}-b^{s_{i+1}}_{k}=-\mu_{3}.$ By Lemma 3,
we also know that for any $t\geq s_{i+1},$ we have
$b^{(t)}_{i}-b^{(t)}_{k}\leq-\mu_{3}.$

The following lemma shows that $b^{(t)}_{k}$ is close to the maximum bias. See
1 Combining Lemma 1 and Lemma 2, we know that throughout the training
$b^{(t)}_{k}\geq\max_{i^{\prime}\in[k]}b^{(t)}_{i^{\prime}}-O(\delta^{r}).$
Therefore, we have
$b^{(t)}_{i}-\max_{i^{\prime}\in[k]}b^{(t)}_{i^{\prime}}\leq-\Omega(1)$ for
$t\geq s_{i+1}.$

Finally, let’s bound the movement of different parameters.

Monotonicity of diagonal terms: For $j\in[k-1],$ according to Lemma 11 we know
$W^{(t)}_{j,j}$ can only start decreasing when it exceeds a large constant and
can only decrease by at most $O(\delta)$ through the algorithm. By choosing
$\delta\leq O(1),$ we can ensure that $W^{(0)}_{j,j}<W^{(t)}_{j,j}$ for any
$t.$ For $W^{(t)}_{k,k},$ we know it monotonically increases since we always
have $1-u^{(t)}_{k}(x)\geq\Omega(1)$ for $x\in\mathcal{S}_{k}.$ This is
because $W^{(t)}_{k,k}$ remains as small as $O(\delta)$ through the algorithm
and $b^{(t)}_{k}-b^{(t)}_{k-1}\leq O(1).$

Bounding non-diagonal terms: We use the following lemma to prove that
$\widetilde{\Omega}(\delta)<W^{(t)}_{j,j^{\prime}}\leq O(\delta)$ for $j\neq
j^{\prime}.$

######  Lemma 16.

For any $j\neq j^{\prime}$, we have $T\dot{W}_{j,j^{\prime}}\leq O(\delta).$
Furthermore, there exists absolute constant $\mu>0$ such that if
$0<W_{j,j^{\prime}}<\frac{\mu\delta}{\log^{\frac{1}{r-2}}(1/\delta)},$ we have
$T\dot{W}_{j,j^{\prime}}\geq-\frac{\mu\delta}{2\log^{\frac{1}{r-2}}(1/\delta)}.$

The first property in Lemma 16 guarantees that the increasing rate is so small
that that the total increase within $T$ time is only $O(\delta)$, which then
implies that $W^{(t)}_{j,j^{\prime}}\leq O(\delta)$ through the training. The
second property in Lemma 16 guarantees that once $W^{(t)}_{j,j^{\prime}}$
falls below $\frac{\mu\delta}{\log^{\frac{1}{r-2}}(1/\delta)},$ its decreasing
rate is so small that that the total decrease within $T$ time is only
$\frac{\mu\delta}{2\log^{\frac{1}{r-2}}(1/\delta)}$, which then implies that
$W^{(t)}_{j,j^{\prime}}>\widetilde{\Omega}(\delta)$ through the training.

Bounding noise correlations: The following lemma shows that the total change
of $\left\langle W^{(t)}_{j,:},\xi_{x}\right\rangle$ within $T$ time is only
$O(\sqrt{\log N}\sigma\delta).$ Since at initialization, we know
$\left|\left\langle W^{(0)}_{j,:},\xi_{x}\right\rangle\right|\leq O(\sqrt{\log
N}\sigma\delta),$ we conclude that $\left|\left\langle
W^{(t)}_{j,:},\xi_{x}\right\rangle\right|\leq O(\sqrt{\log N}\sigma\delta)$
throughout the training. Since
$W^{(t)}_{j,j^{\prime}}\geq\widetilde{\Omega}(\delta),$ as long as
$\sigma\leq\widetilde{O}(1),$ we also have $\left|\left\langle
W^{(t)}_{j,:},\xi_{x}\right\rangle\right|\leq W_{j,j^{\prime}}$ for
$x\in\mathcal{S}_{j^{\prime}}.$

######  Lemma 17.

For every $j\in[k]$ and every $x\in\mathcal{S},$ we have

$\left|\left\langle\dot{W}_{j,:},\xi_{x}\right\rangle\right|\cdot T\leq
O\left(\sqrt{\log N}\sigma\delta\right)$

$\Box$

###  C.1 Proof of lemmas

See 10 Proof of Lemma 10. Recall that each $W^{(0)}_{j,j^{\prime}}$ is
independently sampled from $\mathcal{N}(0,\delta^{2})$ before taking the
absolute value. By standard Gaussian concentration inequality, we know for any
$j,j^{\prime}\in[k],$ with probability at least $1-\frac{1}{1000k^{2}},$

$\displaystyle W^{(0)}_{j,j^{\prime}}\leq O(\delta).$

By anti-concentration inequality of Gaussian polynomials, we know for any
$j,j^{\prime}\in[k],$ with probability at least $1-\frac{1}{1000k^{2}},$

$\displaystyle W^{(0)}_{j,j^{\prime}}\geq\Omega(\delta).$

Also by anti-concentration inequality of Gaussian polynomials, we know for any
distinct $j,j^{\prime}\in[k],$ with probability at least
$1-\frac{1}{1000k^{2}},$

$\displaystyle\left|\left[W^{(0)}_{j,j}\right]^{2}-\left[W^{(0)}_{j^{\prime},j^{\prime}}\right]^{2}\right|\geq\Omega(\delta^{2}),$

which implies
$\left|W^{(0)}_{j,j}-W^{(0)}_{j^{\prime},j^{\prime}}\right|\geq\Omega(\delta)$
assuming $W^{(0)}_{j,j},W^{(0)}_{j^{\prime},j^{\prime}}=\Theta(\delta).$

By the norm concentration of random vectors with independent Gaussian entries,
for each $x\in\mathcal{S},$ we have with probability at least
$1-\frac{1}{1000N^{2}},$

$\displaystyle\left\|\xi_{x}\right\|\leq O(\sigma)$

as long as $d\geq O(\log N).$

By the concentration of standard Gaussian variable, for any distinct
$x,x^{\prime}\in\mathcal{S},$ we have with probability at least
$1-\frac{1}{1000N^{2}},$

$\displaystyle\left|\left\langle\bar{\xi}_{x},\bar{\xi}_{x^{\prime}}\right\rangle\right|\leq
O\left(\frac{\sqrt{\log N}}{\sqrt{d}}\right).$

Similarly, for any $x$ and any $e_{j}$, we have with probability at least
$1-\frac{1}{1000kN},$

$\displaystyle\left|\left\langle\bar{\xi}_{x},e_{j}\right\rangle\right|\leq
O\left(\frac{\sqrt{\log N}}{\sqrt{d}}\right);$

for any $x$ and any $\bar{W}^{(0)}_{j,:}$, we have with probability at least
$1-\frac{1}{1000kN},$

$\displaystyle\left|\left\langle\bar{\xi}_{x},\bar{W}^{(0)}_{j,:}\right\rangle\right|\leq
O\left(\frac{\sqrt{\log N}}{\sqrt{d}}\right);$

Taking a union bound over all these events, we know with probability at least
$0.99$ in the initialization, we have

  1. 1.

for all $j,j^{\prime}\in[k]$, $W^{(0)}_{i,j}=\Theta(\delta)$;

  2. 2.

for all distinct $j,j^{\prime}\in[k]$,
$\left|W^{(0)}_{j,j}-W^{(0)}_{j^{\prime},j^{\prime}}\right|=\Theta(\delta);$

  3. 3.

for all $x\in\mathcal{S},$ $\left\|\xi_{x}\right\|\leq O(\sigma);$

  4. 4.

for all distinct $x,x^{\prime}\in\mathcal{S},$
$\left|\left\langle\bar{\xi}_{x},\bar{\xi}_{x^{\prime}}\right\rangle\right|\leq
O\left(\frac{\sqrt{\log(N)}}{\sqrt{d}}\right).$

  5. 5.

for all $j\in[k]$ and all $x\in\mathcal{S},$
$\left|\left\langle\bar{\xi}_{x},e_{j}\right\rangle\right|,\left|\left\langle\bar{\xi}_{x},\bar{W}^{(0)}_{j,:}\right\rangle\right|\leq
O\left(\frac{\sqrt{\log(N)}}{\sqrt{d}}\right).$

$\Box$

See 12 Proof of Lemma 12. This lemma directly follows from Lemma C.19 in
Allen-Zhu & Li (2020) by taking the continuous time limit and setting $k$ as a
constant. $\Box$

See 1 Proof of Lemma 1. Let’s first write down the time derivative on
$b_{j^{\prime}},$

$\displaystyle\dot{b}_{j^{\prime}}=$ $\displaystyle
1-\frac{k}{N}\sum_{x\in\mathcal{S}}u_{j^{\prime}}(x)$ $\displaystyle=$
$\displaystyle 1-\frac{k}{N}\sum_{x\in\mathcal{S}}\frac{\exp\left(\left\langle
W_{j^{\prime},:},x\right\rangle^{r}+b_{j^{\prime}}\right)}{\sum_{i^{\prime}\in[k]}\exp\left(\left\langle
W_{i^{\prime},:},x\right\rangle^{r}+b_{i^{\prime}}\right)}$

For any $x\in\mathcal{S},$ we can bound $\frac{\exp\left(\left\langle
W_{j^{\prime},:},x\right\rangle^{r}+b_{j^{\prime}}\right)}{\sum_{i^{\prime}\in[k]}\exp\left(\left\langle
W_{i^{\prime},:},x\right\rangle^{r}+b_{i^{\prime}}\right)}$ as follows,

$\displaystyle\left|\frac{\exp\left(\left\langle
W_{j^{\prime},:},x\right\rangle^{r}+b_{j^{\prime}}\right)}{\sum_{i^{\prime}\in[k]}\exp\left(\left\langle
W_{i^{\prime},:},x\right\rangle^{r}+b_{i^{\prime}}\right)}-\frac{\exp\left(b_{j^{\prime}}\right)}{\sum_{i^{\prime}\in[k]}\exp\left(\left\langle
W_{i^{\prime},:},x\right\rangle^{r}+b_{i^{\prime}}\right)}\right|\leq
O(\delta^{r}),$

where we uses $\left|\left\langle W_{j^{\prime},:},x\right\rangle\right|\leq
O(\delta)+O(\sqrt{\log N}\sigma\delta)\leq O(\delta)$ assuming $\sigma\leq
1/\sqrt{\log N}.$ The similar bound also holds for
$\frac{\exp\left(\left\langle
W_{j,:},x\right\rangle^{r}+b_{j}\right)}{\sum_{i^{\prime}\in[k]}\exp\left(\left\langle
W_{i^{\prime},:},x\right\rangle^{r}+b_{i^{\prime}}\right)}$

If $b_{j^{\prime}}-b_{j}\geq\mu\delta^{r},$ we can now upper bound
$\dot{b}_{j^{\prime}}-\dot{b}_{j}$ as follows,

$\displaystyle\dot{b}_{j^{\prime}}-\dot{b}_{j}\leq$
$\displaystyle\frac{k}{N}\sum_{x\in\mathcal{S}}\frac{\exp\left(b_{j}\right)-\exp\left(b_{j^{\prime}}\right)}{\sum_{i^{\prime}\in[k]}\exp\left(\left\langle
W_{i^{\prime},:},x\right\rangle^{r}+b_{i^{\prime}}\right)}+O(\delta^{r})$
$\displaystyle\leq$
$\displaystyle\frac{k}{N}\sum_{x\in\mathcal{S}_{j}\cup\mathcal{S}_{j^{\prime}}}\frac{\exp\left(b_{j}\right)-\exp\left(b_{j^{\prime}}\right)}{\sum_{i^{\prime}\in[k]}\exp\left(\left\langle
W_{i^{\prime},:},x\right\rangle^{r}+b_{i^{\prime}}\right)}+O(\delta^{r})$
$\displaystyle\leq$
$\displaystyle-\Omega(\mu\delta^{r})\cdot\frac{k}{N}\sum_{x\in\mathcal{S}_{j}\cup\mathcal{S}_{j^{\prime}}}\frac{\exp\left(b_{j}\right)}{\sum_{i^{\prime}\in[k]}\exp\left(\left\langle
W_{i^{\prime},:},x\right\rangle^{r}+b_{i^{\prime}}\right)}+O(\delta^{r})$

When $x\in\mathcal{S}_{j}\cup\mathcal{S}_{j^{\prime}},$ we can lower bound
$\frac{\exp\left(b_{j}\right)}{\sum_{i^{\prime}\in[k]}\exp\left(\left\langle
W_{i^{\prime},:},x\right\rangle^{r}+b_{i^{\prime}}\right)}$ as follows,

$\displaystyle\frac{\exp\left(b_{j}\right)}{\sum_{i^{\prime}\in[k]}\exp\left(\left\langle
W_{i^{\prime},:},x\right\rangle^{r}+b_{i^{\prime}}\right)}=$
$\displaystyle\frac{\exp\left(b_{j}\right)}{\sum_{i^{\prime}\in[k]}\exp\left(b_{i^{\prime}}\right)\exp\left(\left\langle
W_{i^{\prime},:},x\right\rangle^{r}\right)}$ $\displaystyle\geq$
$\displaystyle\frac{\exp\left(b_{j}\right)}{\sum_{i^{\prime}\in[k]}\exp\left(b_{i^{\prime}}\right)}\cdot\frac{1}{1+O(\delta^{r})}$
$\displaystyle\geq$ $\displaystyle\Omega(1),$

where the first inequality uses $\left|\left\langle
W_{i^{\prime},:},x\right\rangle\right|\leq\delta$ and the second inequality
assumes $b_{j}\geq\max_{i^{\prime}\in[k]}b_{i^{\prime}}-O(\delta^{r})$ and
$\delta$ is at most some small constant.

Therefore, if $b_{j^{\prime}}-b_{j}\geq\mu\delta^{r},$ we have

$\displaystyle\dot{b}_{j^{\prime}}-\dot{b}_{j}\leq-\Omega(\mu\delta^{r})+O(\delta^{r})<0,$

where the second inequality chooses $\mu$ as a large enough constant.
Similarly, we can prove that if $b_{j^{\prime}}-b_{j}\leq-\mu\delta^{r},$ we
have

$\displaystyle\dot{b}_{j^{\prime}}-\dot{b}_{j}\geq\Omega(\mu\delta^{r})-O(\delta^{r})>0.$

$\Box$

See 2 Proof of Lemma 2. We can write down $\dot{b}_{j^{\prime}}-\dot{b}_{j}$
as follows,

$\displaystyle\dot{b}_{j^{\prime}}-\dot{b}_{j}=$
$\displaystyle\left(1-\frac{k}{N}\sum_{x\in\mathcal{S}}u_{j^{\prime}}(x)\right)-\left(1-\frac{k}{N}\sum_{x\in\mathcal{S}}u_{j}(x)\right)$
$\displaystyle=$
$\displaystyle\frac{k}{N}\sum_{x\in\mathcal{S}_{j^{\prime}}}\left(u_{j}(x)-u_{j^{\prime}}(x)\right)+\frac{k}{N}\sum_{x\in\mathcal{S}\setminus\mathcal{S}_{j^{\prime}}}\left(u_{j}(x)-u_{j^{\prime}}(x)\right).$

We first prove that for any $x\in\mathcal{S}_{j^{\prime}},$ we have
$u_{j}(x)-u_{j^{\prime}}(x)\leq 0.$ We can upper bound $f_{j}(x)$ and lower
bound $f_{j^{\prime}}(x)$ as follows,

$\displaystyle f_{j}(x)=$ $\displaystyle\left\langle
W_{j,:},x\right\rangle^{r}+b_{j}\leq O(\delta^{r})+b_{j}$ $\displaystyle
f_{j^{\prime}}(x)=$ $\displaystyle\left\langle
W_{j^{\prime},:},x\right\rangle^{r}+b_{j^{\prime}}\geq b_{j}.$

The bound on $f_{j}(x)$ holds because $\left\langle
W_{j,:},x\right\rangle=W_{j,j^{\prime}}+\left\langle
W_{j,:},\xi_{x}\right\rangle\leq O(\delta)+O(\sqrt{\log N}\sigma\delta)\leq
O(\delta).$ The bound on $f_{j^{\prime}}(x)$ holds because $\left\langle
W_{j^{\prime},:},x\right\rangle=W_{j^{\prime},j^{\prime}}+\left\langle
W_{j^{\prime},:},\xi_{x}\right\rangle\geq\Omega(\delta)-O(\sqrt{\log
N}\sigma\delta)>0.$ With the above two bounds, we know that
$u_{j}(x)-u_{j^{\prime}}(x)\leq 0$ as long as $b_{j^{\prime}}-b_{j}\geq
O(\delta^{r}).$

Same as in the proof of Lemma 1, for each
$x\in\mathcal{S}\setminus\mathcal{S}_{j^{\prime}},$ we can bound
$u_{j^{\prime}}(x),u_{j}(x)$ as follows,

$\displaystyle\frac{\exp\left(b_{j^{\prime}}\right)}{\sum_{i^{\prime}\in[k]}\exp\left(f_{i^{\prime}}(x)\right)}-O(\delta^{r})\leq
u_{j^{\prime}}(x)\leq\frac{\exp\left(b_{j^{\prime}}\right)}{\sum_{i^{\prime}\in[k]}\exp\left(f_{i^{\prime}}(x)\right)}+O(\delta^{r}),$
$\displaystyle\frac{\exp\left(b_{j}\right)}{\sum_{i^{\prime}\in[k]}\exp\left(f_{i^{\prime}}(x)\right)}-O(\delta^{r})\leq
u_{j}(x)\leq\frac{\exp\left(b_{j}\right)}{\sum_{i^{\prime}\in[k]}\exp\left(f_{i^{\prime}}(x)\right)}+O(\delta^{r}).$

Therefore, if $b_{j^{\prime}}-b_{j}\geq\mu\delta^{r},$ we can further upper
bound $\dot{b}_{j^{\prime}}-\dot{b}_{j}$ as follows,

$\displaystyle\dot{b}_{j^{\prime}}-\dot{b}_{j}\leq$
$\displaystyle\frac{k}{N}\sum_{x\in\mathcal{S}\setminus\mathcal{S}_{j^{\prime}}}\left(u_{j}(x)-u_{j^{\prime}}(x)\right).$
$\displaystyle\leq$
$\displaystyle\frac{k}{N}\sum_{x\in\mathcal{S}\setminus\mathcal{S}_{j^{\prime}}}\frac{\exp\left(b_{j}\right)-\exp\left(b_{j^{\prime}}\right)}{\sum_{i^{\prime}\in[k]}\exp\left(f_{i^{\prime}}(x)\right)}+O(\delta^{r})$
$\displaystyle\leq$
$\displaystyle\frac{k}{N}\sum_{x\in\mathcal{S}_{j}}\frac{\exp\left(b_{j}\right)-\exp\left(b_{j^{\prime}}\right)}{\sum_{i^{\prime}\in[k]}\exp\left(f_{i^{\prime}}(x)\right)}+O(\delta^{r})$
$\displaystyle\leq$
$\displaystyle-\Omega(\mu\delta^{r})\frac{k}{N}\sum_{x\in\mathcal{S}_{j}}\frac{\exp\left(b_{j}\right)}{\sum_{i^{\prime}\in[k]}\exp\left(f_{i^{\prime}}(x)\right)}+O(\delta^{r}).$

Similar as in Lemma 1, we can show that
$\frac{\exp\left(b_{j}\right)}{\sum_{i^{\prime}\in[k]}\exp\left(f_{i^{\prime}}(x)\right)}\geq\Omega(1)$
due to $W_{j,j}\leq O(\delta)$ and
$b_{j}\geq\max_{i^{\prime}\in[k]}b_{i^{\prime}}-O(\delta^{r})$. So, finally we
have

$\displaystyle\dot{b}_{j^{\prime}}-\dot{b}_{j}\leq-\Omega(\mu\delta^{r})+O(\delta^{r})<0,$

where the last inequality chooses $\mu$ as a large enough constant. $\Box$

See 15 Proof of Lemma 15. Since $f_{i}(x)-f_{j}(x)\leq C_{2},$ we know
$1-u_{i}(x)\geq\Omega(1).$ This immediately implies
$\min_{x^{\prime}\in\mathcal{S}_{i}}\left(1-u_{i}(x^{\prime})\right)\geq\Omega(1)$
since $\left|u_{i}(x)-u_{i}(x^{\prime})\right|\leq O(\delta).$ According to
Lemma 13, we can bound
$\frac{\partial\left(f_{i}(e_{i})-f_{j}(e_{i})\right)}{\partial t}$ as
follows,

$\displaystyle\frac{\partial\left(f_{i}(x)-f_{j}(x)\right)}{\partial
t}\geq\Omega(W_{i,i}^{2r-2})-O(1)>0$

where the second inequality holds because $W_{i,i}\geq C_{1}$ with $C_{1}$ a
large enough constant. $\Box$

See 3 Proof of Lemma 3. Since $1-u_{j}(x)\leq C_{1}$ for some
$x\in\mathcal{S}_{j}$, we know $1-u_{j}(x^{\prime})\leq C_{1}+O(\delta)$ for
every $x^{\prime}\in\mathcal{S}_{j}.$ We can write down
$\dot{b}_{j}-\dot{b}_{k}$ as follows,

$\displaystyle\dot{b}_{j}-\dot{b}_{k}=$
$\displaystyle\left(1-\frac{k}{N}\sum_{x^{\prime}\in\mathcal{S}}u_{j}(x^{\prime})\right)-\left(1-\frac{k}{N}\sum_{x^{\prime}\in\mathcal{S}}u_{k}(x^{\prime})\right)$
$\displaystyle=$
$\displaystyle\frac{k}{N}\sum_{x^{\prime}\in\mathcal{S}_{j}}\left(u_{k}(x^{\prime})-u_{j}(x^{\prime})\right)+\frac{k}{N}\sum_{x^{\prime}\in\mathcal{S}\setminus\mathcal{S}_{j}}\left(u_{k}(x^{\prime})-u_{j}(x^{\prime})\right).$

First, we upper bound $u_{k}(x^{\prime})-u_{j}(x^{\prime})$ for every
$x^{\prime}\in\mathcal{S}_{j}$ as follows,

$\displaystyle u_{k}(x^{\prime})-u_{j}(x^{\prime})\leq
1-u_{j}(x^{\prime})-u_{j}(x^{\prime})=-1+2\left(1-u_{j}(x^{\prime})\right)\leq
2C_{1}-1+O(\delta).$

Same as in the proof of Lemma 1, for each
$x^{\prime}\in\mathcal{S}\setminus\mathcal{S}_{j},$ we can bound
$u_{j}(x^{\prime}),u_{k}(x^{\prime})$ as follows,

$\displaystyle\frac{\exp\left(b_{j}\right)}{\sum_{i^{\prime}\in[k]}\exp\left(f_{i^{\prime}}(x^{\prime})\right)}-O(\delta^{r})\leq
u_{j}(x^{\prime})\leq\frac{\exp\left(b_{j}\right)}{\sum_{i^{\prime}\in[k]}\exp\left(f_{i^{\prime}}(x^{\prime})\right)}+O(\delta^{r}),$
$\displaystyle\frac{\exp\left(b_{k}\right)}{\sum_{i^{\prime}\in[k]}\exp\left(f_{i^{\prime}}(x^{\prime})\right)}-O(\delta^{r})\leq
u_{k}(x^{\prime})\leq\frac{\exp\left(b_{k}\right)}{\sum_{i^{\prime}\in[k]}\exp\left(f_{i^{\prime}}(x^{\prime})\right)}+O(\delta^{r}).$

Therefore, we can upper bound $u_{k}(x^{\prime})-u_{j}(x^{\prime})$ as
follows,

$\displaystyle u_{k}(x^{\prime})-u_{j}(x^{\prime})\leq$
$\displaystyle\frac{\exp\left(b_{k}\right)-\exp\left(b_{j}\right)}{\sum_{i^{\prime}\in[k]}\exp\left(f_{i^{\prime}}(x^{\prime})\right)}+O(\delta)$
$\displaystyle=$
$\displaystyle\frac{\exp\left(b_{j}\right)}{\sum_{i^{\prime}\in[k]}\exp\left(f_{i^{\prime}}(x^{\prime})\right)}\cdot\left(\exp(b_{k}-b_{j})-1\right)+O(\delta^{r})$
$\displaystyle\leq$ $\displaystyle O(C_{2})+O(\delta^{r}),$

where the last inequality uses $b_{k}-b_{j}\leq C_{2}.$

Above all, we can upper bound $\dot{b}_{j}-\dot{b}_{k}$ as follows,

$\displaystyle\dot{b}_{j}-\dot{b}_{k}\leq$
$\displaystyle-1+2C_{1}+O(C_{2})+O(\delta^{r})$ $\displaystyle<$
$\displaystyle-\Omega(1),$

where the second inequality holds as long as $C_{1},C_{2},\delta$ are at most
some small constants. $\Box$

See 14 Proof of Lemma 14. We can write down $\dot{b}_{i}-\dot{b}_{j}$ as
follows,

$\displaystyle\dot{b}_{i}-\dot{b}_{j}=$
$\displaystyle\left(1-\frac{k}{N}\sum_{x\in\mathcal{S}}u_{i}(x)\right)-\left(1-\frac{k}{N}\sum_{x\in\mathcal{S}}u_{j}(x)\right)$
$\displaystyle=$
$\displaystyle\frac{k}{N}\sum_{x\in\mathcal{S}}\left(u_{j}(x)-u_{i}(x)\right)$

Next, we lower bound $u_{j}(x)-u_{i}(x)$ for every $x\in\mathcal{S},$

$\displaystyle u_{j}(x)-u_{i}(x)=$ $\displaystyle\frac{\exp\left(\left\langle
W_{j,:},x\right\rangle^{r}+b_{j}\right)-\exp\left(\left\langle
W_{i,:},x\right\rangle^{r}+b_{i}\right)}{\sum_{i^{\prime}\in[k]}f_{i^{\prime}}(x)}$
$\displaystyle\geq$
$\displaystyle\frac{\exp\left(O(\delta^{r})+b_{j}\right)-\exp\left(O(1)+b_{i}\right)}{\sum_{i^{\prime}\in[k]}f_{i^{\prime}}(x)}$

So as long as $b_{j}-b_{i}>O(1),$ we have $u_{j}(x)-u_{i}(x)>0$ for all
$x\in\mathcal{S},$ which then implies $\dot{b}_{i}-\dot{b}_{j}>0.$ $\Box$

See 17 Proof of Lemma 17. For each $j\in[k],$ we have

$\displaystyle\dot{W}_{j,:}=\frac{k}{N}\left(\sum_{x^{\prime}\in\mathcal{S}_{j}}\left(1-u_{j}(x^{\prime})\right)r\left\langle
W_{j,:},x^{\prime}\right\rangle^{r-1}x^{\prime}-\sum_{x^{\prime}\in\mathcal{S}\setminus\mathcal{S}_{j}}u_{j}(x^{\prime})r\left\langle
W_{j,:},x^{\prime}\right\rangle^{r-1}x^{\prime}\right)$

and

$\displaystyle\left\langle\dot{W}_{j,:},\bar{\xi}_{x}\right\rangle$
$\displaystyle=$
$\displaystyle\frac{k}{N}\left(\sum_{x^{\prime}\in\mathcal{S}_{j}}\left(1-u_{j}(x^{\prime})\right)r\left\langle
W_{j,:},x^{\prime}\right\rangle^{r-1}\left\langle
x^{\prime},\bar{\xi}_{x}\right\rangle-\sum_{x^{\prime}\in\mathcal{S}\setminus\mathcal{S}_{j}}u_{j}(x^{\prime})r\left\langle
W_{j,:},x^{\prime}\right\rangle^{r-1}\left\langle
x^{\prime},\bar{\xi}_{x}\right\rangle\right)$

We know that $\left|\left\langle x,\bar{\xi}_{x}\right\rangle\right|\leq
O(\sigma+\sqrt{\log N}/\sqrt{d})$. For any $x^{\prime}\neq x,$ we have
$\left|\left\langle x^{\prime},\bar{\xi}_{x}\right\rangle\right|\leq
O((\sigma\sqrt{\log N})/\sqrt{d}+\sqrt{\log N}/\sqrt{d})\leq O(\sqrt{\log
N}/\sqrt{d})$ as long as $\sigma\leq 1.$

According to Lemma 18, we know that for $x^{\prime}\in\mathcal{S}_{j},$ we
have $\left|\left(1-u_{j}(x^{\prime})\right)\left\langle
W_{j,:},x^{\prime}\right\rangle^{r-1}\right|\leq O(1).$ For
$x^{\prime}\in\mathcal{S}\setminus\mathcal{S}_{i}$, we have
$\left|u_{i}(x^{\prime})\left\langle
W_{j,:},x^{\prime}\right\rangle^{r-1}\right|\leq O(\delta^{r-1})$ since
$\left|\left\langle W_{j,:},x^{\prime}\right\rangle\right|\leq
O(\delta)+O(\sqrt{\log N}\delta\sigma)\leq O(\delta)$ assuming $\sigma\leq
1/\sqrt{\log N}.$

Therefore, we can bound
$\left|\left\langle\dot{W}_{j,:},\bar{\xi}_{x}\right\rangle\right|$ as
follows,

$\displaystyle\left|\left\langle\dot{W}_{j,:},\bar{\xi}_{x}\right\rangle\right|\leq
O\left(\frac{\sigma}{N}+\frac{\sqrt{\log N}}{\sqrt{d}}\right)$

Since $T\leq O(\log(1/\delta)/\delta^{r-2}),N\geq\log(1/\delta)/\delta^{r-1}$
and $d\geq\log^{2}(1/\delta)/\delta^{2r-2},$ we know

$\displaystyle\left|\left\langle\dot{W}_{j,:},\bar{\xi}_{x}\right\rangle\right|\cdot
T\leq O(\sqrt{\log N}\delta).$

$\Box$

######  Lemma 18.

For any $i\in[k]$ and $x\in\mathcal{S}_{i},$ if $(1-u_{i}(x))\left\langle
W_{i,:},x\right\rangle^{r-1}\geq\Theta(1),$ we have

$\displaystyle\frac{d}{dt}\left((1-u_{i}(x))\left\langle
W_{i,:},x\right\rangle^{r-1}\right)<0.$

Proof of Lemma 18. We can write $1-u_{i}(x)$ as $\frac{\sum_{j\in[k],j\neq
i}\exp\left(f_{j}(x)\right)}{\sum_{j\in[k],j\neq
i}\exp\left(f_{j}(x)\right)+\exp\left(f_{i}(x)\right)}.$ Next, we prove that
for any $j^{\prime}\neq i,$ we have

$\frac{d}{dt}\left(\frac{\exp\left(f_{j^{\prime}}(x)\right)}{\sum_{j\in[k],j\neq
i}\exp\left(f_{j}(x)\right)+\exp\left(f_{i}(x)\right)}\left\langle
W_{i,:},x\right\rangle^{r-1}\right)<0.$

This derivative can be written the sum of two terms:

$\displaystyle\frac{d}{dt}\left(\frac{\exp\left(f_{j^{\prime}}(x)\right)}{\sum_{j\in[k],j\neq
i}\exp\left(f_{j}(x)\right)+\exp\left(f_{i}(x)\right)}\left\langle
W_{i,:},x\right\rangle^{r-1}\right)$ $\displaystyle=$
$\displaystyle\frac{1}{\sum_{j\in[k],j\neq
i}\exp\left(f_{j}(x)-f_{j^{\prime}}(x)\right)+\exp\left(f_{i}(x)-f_{j^{\prime}}(x)\right)}\frac{d}{dt}\left(\left\langle
W_{i,:},x\right\rangle^{r-1}\right)$
$\displaystyle+\frac{d}{dt}\left(\frac{1}{\sum_{j\in[k],j\neq
i}\exp\left(f_{j}(x)-f_{j^{\prime}}(x)\right)+\exp\left(f_{i}(x)-f_{j^{\prime}}(x)\right)}\right)\left\langle
W_{i,:},x\right\rangle^{r-1}.$

For the first term, we have

$\displaystyle\frac{1}{\sum_{j\in[k],j\neq
i}\exp\left(f_{j}(x)-f_{j^{\prime}}(x)\right)+\exp\left(f_{i}(x)-f_{j^{\prime}}(x)\right)}\frac{d}{dt}\left(\left\langle
W_{i,:},x\right\rangle^{r-1}\right)$ $\displaystyle=$
$\displaystyle\frac{1}{\sum_{j\in[k],j\neq
i}\exp\left(f_{j}(x)-f_{j^{\prime}}(x)\right)+\exp\left(f_{i}(x)-f_{j^{\prime}}(x)\right)}(r-1)\left\langle
W_{i,:},x\right\rangle^{r-2}\left\langle\dot{W}_{i,:},x\right\rangle$
$\displaystyle\leq$
$\displaystyle\frac{1}{\exp\left(f_{i}(x)-f_{j^{\prime}}(x)\right)}(r-1)\left\langle
W_{i,:},x\right\rangle^{r-2}\left\langle\dot{W}_{i,:},x\right\rangle.$

For the second term, we have

$\displaystyle\frac{d}{dt}\left(\frac{1}{\sum_{j\in[k],j\neq
i}\exp\left(f_{j}(x)-f_{j^{\prime}}(x)\right)+\exp\left(f_{i}(x)-f_{j^{\prime}}(x)\right)}\right)\left\langle
W_{i,:},x\right\rangle^{r-1}$ $\displaystyle=$
$\displaystyle-\frac{\sum_{j\in[k],j\neq
i}\exp\left(f_{j}(x)-f_{j^{\prime}}(x)\right)\left(\dot{f}_{j}(x)-\dot{f}_{j^{\prime}}(x)\right)+\exp\left(f_{i}(x)-f_{j^{\prime}}(x)\right)\left(\dot{f}_{i}(x)-\dot{f}_{j^{\prime}}(x)\right)}{\left(\sum_{j\in[k],j\neq
i}\exp\left(f_{j}(x)-f_{j^{\prime}}(x)\right)+\exp\left(f_{i}(x)-f_{j^{\prime}}(x)\right)\right)^{2}}\left\langle
W_{i,:},x\right\rangle^{r-1}$ $\displaystyle\leq$
$\displaystyle-\frac{1}{2}\cdot\frac{r\left\langle
W_{i,:},x\right\rangle^{r-1}\left\langle\dot{W}_{i,:},x\right\rangle}{\exp\left(f_{i}(x)-f_{j^{\prime}}(x)\right)}\left\langle
W_{i,:},x\right\rangle^{r-1},$

where the last inequality uses
$f_{i}(x)-f_{j}(x)\geq\Omega(1),\left|\dot{f}_{j}(x)-\dot{f}_{j^{\prime}}(x)\right|\leq
O(1)$ and $\dot{f}_{i}(x)-\dot{f}_{j^{\prime}}(x)\geq r\left\langle
W_{i,:},x\right\rangle^{r-1}\left\langle\dot{W}_{i,:},x\right\rangle-O(1)\geq\Omega(1).$

Combining the bounds on both terms, as long as $\left\langle
W_{i,:},x\right\rangle$ is larger than certain constant (which is guaranteed
by $(1-u_{i}(x))\left\langle W_{i,:},x\right\rangle^{r-1}\geq\Theta(1)$), we
know $\frac{d}{dt}\left((1-u_{i}(x))\left\langle
W_{i,:},x\right\rangle^{r-1}\right)<0$. $\Box$

See 16 Proof of Lemma 16. We can write down the derivative of
$W_{j,j^{\prime}}$ as follows,

$\displaystyle\dot{W}_{j,j^{\prime}}$ $\displaystyle=$
$\displaystyle\frac{k}{N}\sum_{x\in\mathcal{S}_{j}}\left(1-u_{j}(x)\right)r\left\langle
W_{j,:},x\right\rangle^{r-1}\left\langle e_{j^{\prime}},x\right\rangle$
$\displaystyle-\frac{k}{N}\sum_{x\in\mathcal{S}_{j^{\prime}}}u_{j}(x)r\left\langle
W_{j,:},x\right\rangle^{r-1}\left\langle e_{j^{\prime}},x\right\rangle$
$\displaystyle-\frac{k}{N}\sum_{x\in\mathcal{S}\setminus(\mathcal{S}_{j}\cup\mathcal{S}_{j^{\prime}})}u_{j}(x)r\left\langle
W_{j,:},x\right\rangle^{r-1}\left\langle e_{j^{\prime}},x\right\rangle$
$\displaystyle=$ $\displaystyle\pm O\left(\frac{\sigma\sqrt{\log
N}}{\sqrt{d}}\right)-O\left(\left(W_{j,j^{\prime}}\pm O\left(\sqrt{\log
N}\delta\sigma\right)\right)^{r-1}\right)\pm
O\left(\delta^{r-1}\frac{\sigma\sqrt{\log N}}{\sqrt{d}}\right).$

The bound on the first term relies on $\left(1-u_{j}(x)\right)\left\langle
W_{j,:},x\right\rangle^{r-1}\leq O(1)$ and $\left\langle
e_{j^{\prime}},x\right\rangle=\pm O\left(\frac{\sigma\sqrt{\log
N}}{\sqrt{d}}\right)$ for $x\in\mathcal{S}_{j},$ where
$\left(1-u_{j}(x)\right)\left\langle W_{j,:},x\right\rangle^{r-1}\leq O(1)$ is
guaranteed by Lemma 18. The bound on the second term uses $\left\langle
W_{j,:},x\right\rangle=W_{j,j^{\prime}}\pm O\left(\sqrt{\log
N}\delta\sigma\right)$ and $\left\langle e_{j^{\prime}},x\right\rangle=1\pm
O\left(\frac{\sigma\sqrt{\log N}}{\sqrt{d}}\right)$ for
$x\in\mathcal{S}_{j^{\prime}}.$ The bound on the third term uses $\left\langle
W_{j,:},x\right\rangle=O(\delta)$ and $\left\langle
e_{j^{\prime}},x\right\rangle=\pm O\left(\frac{\sigma\sqrt{\log
N}}{\sqrt{d}}\right)$ for
$x\in\mathcal{S}\setminus(\mathcal{S}_{j}\cup\mathcal{S}_{j^{\prime}}).$

To prove the upper bound of the derivative, we have

$\displaystyle\dot{W}_{j,j^{\prime}}\leq$ $\displaystyle
O(\frac{\sigma\sqrt{\log N}}{\sqrt{d}})$

where we use $W_{j,j^{\prime}}\pm O\left(\sqrt{\log N}\delta\sigma\right)\geq
0$. Since $T=O(\log(1/\delta)/\delta^{r-2}),$ we have

$T\dot{W}_{j,j^{\prime}}\leq O(\delta),$

as long as $d\geq O(\frac{\log N\log^{2}(1/\delta)}{\delta^{2r-2}}).$

We show that there exists absolute constant $\mu>0$ such that if
$0<W_{j,j^{\prime}}<\frac{\mu\delta}{\log^{\frac{1}{r-2}}(1/\delta)},$ we have
$T\dot{W}_{j,j^{\prime}}\geq-\frac{\mu\delta}{2\log^{\frac{1}{r-2}}(1/\delta)},$
which holds as long as
$\dot{W}_{j,j^{\prime}}\geq-O\left(\frac{\mu\delta^{r-1}}{\log^{\frac{r-1}{r-2}}(1/\delta)}\right).$
We have

$\displaystyle\dot{W}_{j,j^{\prime}}$ $\displaystyle=$ $\displaystyle\pm
O(\frac{\sigma\sqrt{\log N}}{\sqrt{d}})-O\left(\left(W_{j,j^{\prime}}\pm
O\left(\sqrt{\log N}\delta\sigma\right)\right)^{r-1}\right)$
$\displaystyle\geq$ $\displaystyle-O(\frac{\sigma\sqrt{\log
N}}{\sqrt{d}})-O\left(\frac{\mu^{r-1}\delta^{r-1}}{\log^{\frac{r-1}{r-2}}(1/\delta)}\right)$
$\displaystyle\geq$
$\displaystyle-O\left(\frac{\mu^{r-1}\delta^{r-1}}{\log^{\frac{r-1}{r-2}}(1/\delta)}\right)$
$\displaystyle\geq$
$\displaystyle-O\left(\frac{\mu\delta^{r-1}}{\log^{\frac{r-1}{r-2}}(1/\delta)}\right).$

The first inequality assumes $\sigma\leq O\left(\frac{\mu}{\sqrt{\log
N}\log^{\frac{1}{r-2}}(1/\delta)}\right).$ The second inequality assumes
$d\geq O(\frac{\log
N\log^{\frac{2r-2}{r-2}}(1/\delta)}{\mu^{2r-2}\delta^{2r-2}}).$ The third
inequality chooses $\mu$ as a small enough constant. $\Box$

See 11 Proof of Lemma 11. We have

$\displaystyle\dot{W}_{j,j}=$
$\displaystyle\frac{k}{N}\sum_{x\in\mathcal{S}_{j}}\left(1-u_{j}(x)\right)r\left\langle
W_{j,:},x\right\rangle^{r-1}\left\langle
x,e_{j}\right\rangle-\frac{k}{N}\sum_{x\in\mathcal{S}\setminus\mathcal{S}_{j}}u_{j}(x)r\left\langle
W_{j,:},x\right\rangle^{r-1}\left\langle x,e_{j}\right\rangle$
$\displaystyle=$
$\displaystyle\frac{k}{N}\sum_{x\in\mathcal{S}_{j}}\left(1-u_{j}(x)\right)r\left(W_{j,j}\pm
O\left(\sqrt{\log N}\delta\sigma\right)\right)^{r-1}\left(1\pm
O\left(\frac{\sqrt{\log N}\sigma}{\sqrt{d}}\right)\right)$
$\displaystyle-\frac{k}{N}\sum_{x\in\mathcal{S}\setminus\mathcal{S}_{j}}u_{j}(x)r\left(O(\delta)\pm
O\left(\sqrt{\log N}\delta\sigma\right)\right)^{r-1}\left(\pm
O\left(\frac{\sqrt{\log N}\sigma}{\sqrt{d}}\right)\right)$ $\displaystyle=$
$\displaystyle\left(1\pm O(\sqrt{\log
N}\sigma)\right)\frac{k}{N}\sum_{x\in\mathcal{S}_{j}}\left(1-u_{j}(x)\right)rW_{j,j}^{r-1}\pm
O\left(\frac{\delta^{r-1}\sqrt{\log N}\sigma}{\sqrt{d}}\right),$

where the second equality uses $\left|\left\langle
W_{j,:},\xi_{x}\right\rangle\right|\leq O(\sqrt{\log
N}\delta\sigma),\left|\left\langle\xi_{x},e_{j}\right\rangle\right|\leq
O\left(\frac{\sqrt{\log N}\sigma}{\sqrt{d}}\right)$ and $W_{j,j^{\prime}}\leq
O(\delta)$ for $j\neq j^{\prime}.$

Therefore, if
$\min_{x\in\mathcal{S}_{j}}\left(1-u_{j}(x)\right)\geq\Omega(1)$, we know

$\left(1-O(\sqrt{\log
N}\sigma)\right)\frac{k}{N}\sum_{x\in\mathcal{S}_{j}}\left(1-u_{j}(x)\right)rW_{j,j}^{r-1}\leq\dot{W}_{j,j}\leq\left(1+O(\sqrt{\log
N}\sigma)\right)\frac{k}{N}\sum_{x\in\mathcal{S}_{j}}\left(1-u_{j}(x)\right)rW_{j,j}^{r-1}.$

And we always have

$\dot{W}_{j,j}\geq-O\left(\frac{\delta^{r-1}\sqrt{\log
N}\sigma}{\sqrt{d}}\right).$

$\Box$

See 13 Proof of Lemma 13. Recall that $f_{i}(x)=\left\langle
W_{i,:},x\right\rangle^{r}+b_{i},$ so we have

$\displaystyle\dot{f}_{i}(x)=$ $\displaystyle r\left\langle
W_{i,:},x\right\rangle^{r-1}\left\langle\dot{W}_{i,:},x\right\rangle+\dot{b}_{i}$
$\displaystyle=$ $\displaystyle r\left(W_{i,i}\pm\sqrt{\log
N}\sigma\delta\right)^{r-1}\left(\dot{W}_{i,i}+\left\langle\dot{W}_{i,:},\xi_{x}\right\rangle\right)+\dot{b}_{i}$
$\displaystyle\geq$ $\displaystyle\Omega(W_{i,i}^{2r-2})-O(1),$

where in the last inequality we uses
$\dot{W}_{i,i}\geq\Omega(W_{i,i}^{r-1})\geq\Omega(\delta^{r})$ and
$\left|\left\langle\dot{W}_{i,:},\xi_{x}\right\rangle\right|\leq\frac{\sigma\sqrt{\log
N}\delta^{r-1}}{\log(1/\delta)}\leq O(\delta^{r-1}).$

We also have

$\displaystyle\dot{f}_{j}(x)=$ $\displaystyle r\left\langle
W_{j,:},x\right\rangle^{r-1}\left\langle\dot{W}_{j,:},x\right\rangle+\dot{b}_{j}$
$\displaystyle=$ $\displaystyle r\left(W_{j,i}+\sqrt{\log
N}\sigma\delta\right)^{r-1}\left(\dot{W}_{j,i}\pm\left\langle\dot{W}_{j,:},\xi_{x}\right\rangle\right)+\dot{b}_{j}$
$\displaystyle\leq$ $\displaystyle O(1),$

where we uses $\left|W_{j,i}\right|\leq
O(\delta),\left|\dot{W}_{j,i}\right|\leq O(\delta^{r-1})$ and
$\left|\left\langle\dot{W}_{j,:},\xi_{x}\right\rangle\right|\leq
O(\delta^{r-1}).$

Therefore, we have

$\displaystyle\frac{dt}{d}\left(f_{i}(x)-f_{j}(x)\right)\geq\Omega(W_{i,i}^{2r-2})-O(1).$

$\Box$

##  Appendix D Additional experiments

In this section, we describe the detailed setting of our experiments and also
include additional experiment results.

#### MNIST & Fashion-MNIST.

Unless specified otherwise, we use a depth-10 and width-1024 fully-connected
ReLU neural network (FCN10) for MNIST and Fashion-MNIST. We use Kaiming
initialization for the weights and set all bias terms as zero. We use a small
initialization by scaling the weights of each layer by $(0.001)^{1/h}$ so the
output is scaled by $0.001,$ where $h$ is the network depth. We train the
network using SGD with learning rate $0.01$ and momentum $0.9$ for $100$
epochs.

#### CIFAR-10 & CIFAR-100

We use VGG-16 (without batch normalization) for CIFAR-10 and CIFAR-100. We use
Kaiming initialization for the weights and set all bias terms as zero. We run
SGD with momentum $0.9$ and weight decay $1\mathrm{e}{-4}$ for $100$ epochs.
For the learning rate, we start from $0.01$ and reduce it by a factor of $0.1$
at the $60$-th epoch and $90$-th epoch.

We linearly interpolate using $50$ evenly spaced points between the network at
initialization and the network at the end of training. We evaluate error and
loss on the train set. For each setting, we repeat the experiments three times
from different random seeds and plot the mean and deviation.

Note in Figure 1, to contrast the convex curve and plateau curve, we have used
FCN4 with standard initialization on MNIST, and VGG-16 with $0.001$
initialization on CIFAR-10.

Our code is based on the implementation from Lucas et al. (2021). Each trial
of our experiment can be finished on an Nvidia Tesla P100 within one hour.

###  D.1 All bias v.s. last bias v.s. no bias

Figure 9: Comparison between networks with all bias, last bias and no bias on
Fashion-MNIST and CIFAR-10.

Figure 9 shows that on both Fashion-MNIST and CIFAR-10, having bias on the
last layer or on all layers can create longer plateau in error curve, while
does not significantly affect the loss curve.

###  D.2 Normal interpolation v.s. homogeneous interpolation.

Figure 10: Comparison between networks with normal interpolation and
homogeneous interpolation on bias on Fashion-MNIST and CIFAR-10.

Figure 10 shows that on both Fashion-MNIST and CIFAR-10, applying homogeneous
interpolation on biases can significantly reduce the plateau on error
interpolation curve.

###  D.3 Different initializations

Figure 11: Comparison between networks with different initialization scales on
MNIST and CIFAR-100 with last bias.

Figure 12: Comparison between networks with different initialization scales on
Fashion-MNIST and CIFAR-10 with all bias.

Figure 13: Comparison between networks with different initialization scales on
Fashion-MNIST and CIFAR-10 with last bias.

Smaller initialization creates longer plateau in both error and loss curves.
See Figure 11 for MNIST, CIFAR-100 with last bias; see Figure 12 for Fashion-
MNIST, CIFAR-10 with all bias; see Figure 13 for Fashion-MNIST, CIFAR-10 with
last bias.

###  D.4 Different depths

Figure 14: Comparison between networks with different depth on MNIST and
CIFAR-100 with last bias.

Figure 15: Comparison between networks with different depth on Fashion-MNIST
and CIFAR-10 with all bias. We use 0.001 initialization scale for VGG-16 on
CIFAR-10.

Figure 16: Comparison between networks with different depth on Fashion-MNIST
and CIFAR-10 with last bias. We use 0.001 initialization scale for VGG-16 on
CIFAR-10.

Deeper networks create longer plateau in both error and loss curves. See
Figure 14 for MNIST, CIFAR-100 with last bias; see Figure 15 for Fashion-
MNIST, CIFAR-10 with all bias; see Figure 16 for Fashion-MNIST, CIFAR-10 with
last bias.

###  D.5 Bias dynamics

Figure 17: Train loss for each class and bias term dynamics on
MNIST$\left\\{1,2\right\\}$ and MNIST$\left\\{2,3\right\\}$.

In Figure 17, we give two more examples on two-class MNIST in which the later
learned class has larger bias.

Figure 18: Train loss for each class and bias term dynamics on
MNIST$\left\\{7,8,9\right\\}$.

In Figure 18, although class 9 is learned last, class 7 gets the largest bias
after training. Let $S$ be the set of all samples for number 7,8,9 and let
$S_{7},S_{9},S_{9}$ be the set of samples for each class. For convenience, we
use $u_{i,j}$ to denote $\frac{1}{\left|S\right|}\sum_{x\in S_{j}}u_{i}(x),$
where $u_{i}(x)$ is the softmax output for class $i$ under input $x.$ Then, we
can write down the derivative on three bias terms:

$\displaystyle\dot{b}_{7}=\frac{1}{3}-u_{7,7}-u_{7,8}-u_{7,9}$
$\displaystyle\dot{b}_{8}=\frac{1}{3}-u_{8,7}-u_{8,8}-u_{8,9}$
$\displaystyle\dot{b}_{9}=\frac{1}{3}-u_{9,7}-u_{9,8}-u_{9,9}.$