Why wide neural networks share the same loss-curve fine structure

We start from a common empirical observation: when two sufficiently wide networks are trained on the same ordered sequence of minibatches, the small rises and falls in their loss curves can align almost step for step, even when their initializations are independent, and attempt to explain this in an elementary manner.

For a smooth two-layer network in the classical mean-field parameterization, trained for a fixed number $T$ of SGD steps, we show that for every fixed data stream $U$, the vector of losses over steps differs from the deterministic infinite-width loss vector associated with $U$ by a vector whose RMS size is $O_T(m^{-1/2})$. The same conclusion holds after applying any fixed linear detrending operator $Q$.

If the examples used at every step are independent and the batch size $b$ is also allowed to vary, we show using another approach that, writing the finite-width loss vector in its two-factor Hoeffding/functional-ANOVA decomposition

$$\mu_{m,b}+D_{m,b}(U)+J_{m,b}(I)+X_{m,b}(I, U),$$

where $D$ is the data-only component, $J$ is the initialization-only component, and $X$ is their interaction, under some smoothness and stability assumptions we get

$$\|D_{m,b}\|_{L^2}=O_T(b^{-1/2}), \qquad \|J_{m,b}\|_{L^2}=O_T(m^{-1/2}), \qquad \|X_{m,b}\|_{L^2}=O_T((mb)^{-1/2}).$$

Effectively, width averages over initialized neurons, batch size averages over examples, and the interaction is averaged over both axes. Consequently, same-data runs synchronize as width grows, while same-initialization runs synchronize as batch size grows.

These are pessimistic finite-horizon upper bounds for a smooth bounded two-layer model. Their constants depend on the training recipe and can grow poorly with the training horizon. Nevertheless, the rates match our empirical observations quite well, including in settings rather far from the one used for the proofs. There are papers using much heavier machinery that strengthen some of these results under different assumptions, but our point is that weaker but empirically useful conclusions already follow from elementary arguments.

In this parameterization the parameter-space learning rate is $m\eta_t$ (while the "function-space" neuron update learning rate is around $\eta$). We keep the finite schedule $(\eta_0,\ldots,\eta_{T-1})$ and the horizon $T$ fixed as width changes. A nonconstant schedule causes no problem, but the constants in the bounds depend on the whole schedule. If the schedule itself changes with width, one needs uniform bounds on the resulting update maps.

The same issue appears when changing batch size. The $b^{-1/2}$ rate below holds with the effective schedule fixed. If one tunes the learning rate as a function of batch size, the theorem can still be applied separately at every $b$, but its constants now change with $b$, so the observed scaling no longer isolates the averaging effect. Holding the schedule fixed is most plausible near or above the critical batch size, and less so in the regime where linear batch-size learning-rate scaling is useful.

Let's write down the smoothness conditions first. Suppose there are constants $M_0, M_1, M_2, K_0, K_1, K_2$ such that $|\phi(z, x)| \le M_0$, $\|\nabla_z \phi(z, x)\| \le M_1$, $\|\nabla_z \phi(z, x) - \nabla_{z'} \phi(z', x)\| \le M_2 \| z - z' \|$, $|\lambda(y, u)| \le K_0$, $|\partial_u \lambda(y, u)| \le K_1$ and $|\partial_u \lambda(y, u) - \partial_{u'} \lambda(y, u')| \le K_2 |u - u'|$, over whatever we observe during the training run.

Also, the particles $Z^0_i = \bar{Z}^0_i$ are sampled i.i.d. independently of the data.

Now, we try to compare the infinite width limit with the finite width limit. To do that, we pick a particle $Z_i$, look at the idealized particle $\bar{Z}_i$ (as done before), and look at their joint evolution.

We have $Z^{t+1}_i = Z^t_i - \eta_t G_{B_t}(Z_i^t, \rho_m^t)$ and $\bar{Z}^{t+1}_i = \bar{Z}^t_i - \eta_t G_{B_t} (\bar{Z}_i^t, \rho^U_t)$.

Conditional on the data stream $U$, the ideal particles are independent and their distribution is $\rho^U_t$.

Let's say the expected discrepancy between the particles at step $t$ (expectation over initialization) is:

$$e_t = \frac{1}{m} \sum_{i = 1}^m \mathbb{E}_I [\|Z_i^t - \bar{Z}_i^t\|^2 | U]$$

We will bound the error using smoothness conditions, and then propagate the prediction error through one step of SGD, which will give us a bound on $e_t$, and then use it to bound the loss error.

For input $x$, we have

$$f_{\rho_m^t}(x) - f_{\rho_t^U}(x) = \frac{1}{m} \sum_i (\phi(Z_i^t, x) - \phi(\bar{Z}_i^t, x)) + \frac{1}{m} \sum_i (\phi(\bar{Z}_i^t, x) - \mathbb{E}[\phi(\bar{Z}_i^t, x) | U])$$

By our second assumption and the mean-value theorem, we have $|\phi(z, x) - \phi(z', x)| \le M_1 \|z - z'\|$.

The expectation of the first term squared, conditioned on $U$, can then be bounded by $M_1^2 e_t$ using Jensen's inequality.

For the conditional expectation of the second term squared, it is a conditional variance (divided by $m$), and hence is upper bounded by the second moment divided by $m$, which is upper bounded by $M_0^2 / m$.

Now, using $(a + b)^2 \le 2a^2 + 2b^2$, we get that

$$\mathbb{E}[|f_{\rho_m^t}(x) - f_{\rho_t^U}(x)|^2 | U] \le 2 M_1^2 e_t + 2 M_0^2 / m$$

Now, we consider the SGD update.

Let's look at $\|G_B(z, \rho) - G_B(z', \rho')\|$. The unscaled term inside the norm, corresponding to $(x, y)$, is $\frac{\partial \lambda(y, f_{\rho}(x))}{\partial f_{\rho}(x)} \nabla_z \phi(z, x) - \frac{\partial \lambda(y, f_{\rho'}(x))}{\partial f_{\rho'}(x)} \nabla_{z'} \phi(z', x)$. Adding and subtracting $\frac{\partial \lambda(y, f_{\rho}(x))}{\partial f_{\rho}(x)} \nabla_{z'} \phi(z', x)$, we get bounds for that term being $K_1 M_2 \|z - z'\| + M_1 K_2 |f_{\rho'}(x) - f_{\rho}(x)|$. By triangle inequality, we get an upper bound of $K_1 M_2 \|z - z'\| + \frac{M_1 K_2}{b} \sum_{(x, y) \in B} |f_{\rho'}(x) - f_{\rho}(x)|$.

Let $\Delta_i^t$ be the difference $Z_i^t - \bar{Z}_i^t$. Then we have $\Delta_i^{t+1} = \Delta_i^{t} - \eta_t (G_{B_t}(Z_i^t, \rho_m^t) - G_{B_t}(\bar{Z}_i^t, \rho_t^U))$.

So we have $\|\Delta_i^{t+1}\| \le \|\Delta_i^{t}\| + \eta_t (K_1 M_2 \|\Delta_i^t\| + \frac{M_1 K_2}{b} \sum_{(x, y) \in B} |f_{\rho_m^t}(x) - f_{\rho_t^U}(x)|)$.

Applying Cauchy-Schwarz to the second term, we get $\|\Delta_i^{t+1}\| \le \|\Delta_i^{t}\|(1 + \eta_t K_1 M_2) + \frac{\eta_t M_1 K_2}{\sqrt{b}} \sqrt{\sum_{(x, y) \in B} |f_{\rho_m^t}(x) - f_{\rho_t^U}(x)|^2}$.

Squaring and using $(a + b)^2 \le 2a^2 + 2b^2$ again, and taking conditional expectation over $I$ given $U$, we get

$$e_{t + 1} \le (2(1 + \eta_* K_1 M_2)^2 + 4 \eta_*^2 M_1^4 K_2^2) e_t + \frac{4 \eta_*^2 M_0^2 M_1^2 K_2^2}{m},$$

where $e_0 = 0$ and $\eta_*=\max_{t<T}\eta_t$. We can then unroll this recursion.

Note two things:

• For a fixed number of steps, even though the bound becomes exponential in $t$, it gives a bound that depends inversely on $m$. The error accumulation that leads to such an issue is also why our analysis may give us useless bounds for long training times.
• Our bounds are quite weak, e.g., one way to strengthen them is to use $(a + b)^2 \le (1 + \delta) a^2 + (1 + \frac{1}{\delta}) b^2$ (and there are other issues such as applying loose global bounds).

Now, we want to see how loss behaves.

The mean value theorem with the loss derivative boundedness assumption gives $|\lambda(y, u) - \lambda(y, v)| \le K_1|u - v|$, so $|L_{m, t} - F_t(U)| \le K_1 \sqrt{\frac{1}{b} \sum_{(x, y) \in B} |f_{\rho_m^t}(x) - f_{\rho_t^U}(x)|^2}$. Squaring and taking the conditional expectation with respect to $I$ given $U$, then using the prediction error bounds in terms of $e_t$ and the $e_t$ bound we have above, we get the desired

$$\mathbb{E}_I [ \|R_m(I, U)\|^2 | U ] \le \frac{C_T}{m}$$

Write one SGD update as

$$Z_i^{t+1}=Z_i^t-\frac{\eta_t}{b}\sum_{r=1}^b g\left(Z_i^t,\xi_{t,r},f_m^t(x_{t,r})\right),$$

where

$$g(z,\xi,u)=\partial_u\lambda(y,u)\nabla_z\phi(z,x),$$

and $\xi=(x,y)$. The prediction at a particle configuration $\mathbf z=(z_1,\ldots,z_m)$ is

$$f_{\mathbf z}(x)=\frac1m\sum_{j=1}^m\phi(z_j,x).$$

The loss before the update is

$$\ell_B^{(m)}(\mathbf z)=\frac1b\sum_{r=1}^b\lambda\left(y_r,f_{\mathbf z}(x_r)\right).$$

Thus, if $B_t=(\xi_{t,1},\ldots,\xi_{t,b})$ is the batch at step $t$, then

$$\mathbf Z^{t+1}=T_{t,B_t}^{(m)}(\mathbf Z^t),$$

where $T_{t,B}^{(m)}$ denotes one SGD step, and

$$L_{m,b,t}=\ell_{B_t}^{(m)}(\mathbf Z^t).$$

The full loss trace is

$$L_{m,b}=(L_{m,b,0},\ldots,L_{m,b,T-1})\in\mathbb R^T,$$

and we use the usual Euclidean norm on traces:

$$\|v\|^2=\sum_{t=0}^{T-1}v_t^2.$$

Let's first write down the assumptions:

• The number of steps $T$ and the effective learning-rate schedule $\eta_0,\ldots,\eta_{T-1}$ are fixed as $m$ and $b$ change, as discussed in the parameterization section above. In particular, increasing $b$ also increases the total number $bT$ of examples used.
• The initialized particles are i.i.d.
• The examples are mutually independent and independent of the initialization. Within step $t$ they are identically distributed according to $P_t$, but $P_t$ may vary with $t$.
• The initialization and data distributions have bounded support.
• There is a fixed compact convex set $K$ containing every particle state reached during the first $T$ steps, including in the coupled runs used below.
• On this region, the first and second derivatives of $\phi$ and $g$ with respect to their numerical arguments are bounded.
• The loss $\lambda(y,u)$, its first derivative with respect to $u$, and its second derivative with respect to $u$ are bounded over the predictions reached during training.

All derivative bounds below are understood to hold on a compact convex set containing the particle states and on a compact interval containing every prediction encountered in the coupled runs. Thus, every line segment used in the mean-value and fundamental-theorem-of-calculus arguments remains inside the region where the derivative bounds hold.

No differentiability with respect to the example $\xi=(x,y)$ is needed.

For convenience, choose constants such that

$$\|\nabla_z\phi(z,x)\|\le M_\phi,$$

$$\|g(z,\xi,u)-g(z',\xi,u')\|\le L_g\left(\|z-z'\|+|u-u'|\right),$$

$$\|g(z,\xi,u)\|\le G,$$

$$|\lambda(y,u)|\le\Lambda,$$

$$|\lambda(y,u)-\lambda(y,u')|\le M_\lambda|u-u'|,$$

and the first derivatives of $\phi$, $g$, and $\lambda$ are Lipschitz, with constants bounded by $H_\phi$, $H_g$, and $H_\lambda$.

We replace one initialized particle $Z_i^0$ by an independent copy and get a new trace $L^{(i)}$. Similarly, we replace one example $\xi_{s,r}$ and get a new trace $L^{(s,r)}$. We then replace both and get a new trace $L^{(i;s,r)}$.

Define

$$\Delta_i^ZL=L-L^{(i)},$$

$$\Delta_{s,r}^{\xi}L=L-L^{(s,r)},$$

and

$$\Delta_i^Z\Delta_{s,r}^{\xi}L=L-L^{(i)}-L^{(s,r)}+L^{(i;s,r)}.$$

We will first prove that there are constants $A_T,B_T,C_T$, independent of $m$, $b$, $i$, $s$, and $r$, such that

$$\|\Delta_i^ZL\|\le\frac{A_T}{m},$$

$$\|\Delta_{s,r}^{\xi}L\|\le\frac{B_T}{b},$$

and

$$\|\Delta_i^Z\Delta_{s,r}^{\xi}L\|\le\frac{C_T}{mb}.$$

For two particle configurations (neural network weights), define

$$\|\mathbf z-\mathbf z'\|_{\mathrm{av}}=\frac1m\sum_{j=1}^m\|z_j-z_j'\|,$$

and

$$\|\mathbf z-\mathbf z'\|_\infty=\max_j\|z_j-z_j'\|.$$

The average norm is useful for a neuron replacement. Replacing one particle can change that particle by an order-one amount, but the average change over all $m$ particles is only $O(1/m)$.

The maximum norm is useful for an example replacement. Replacing one example changes the update of every particle by $O(1/b)$, so the perturbation is $O(1/b)$ even in the maximum norm.

We first derive some basic stability bounds.

By the mean value theorem,

$$|\phi(z,x)-\phi(z',x)|\le M_\phi\|z-z'\|.$$

This gives

$$|f_{\mathbf z}(x)-f_{\mathbf z'}(x)|\le\frac{M_\phi}{m}\sum_{j=1}^m\|z_j-z_j'\|=M_\phi\|\mathbf z-\mathbf z'\|_{\mathrm{av}}.$$

Now consider two configurations $\mathbf z$ and $\mathbf z'$ updated using the same batch $B$. For particle $i$,

$$T_{t,B,i}^{(m)}(\mathbf z)=z_i-\frac{\eta_t}{b}\sum_{r=1}^b g\left(z_i,\xi_r,f_{\mathbf z}(x_r)\right).$$

Using the Lipschitz bound on $g$,

$$\|T_{t,B,i}^{(m)}(\mathbf z)-T_{t,B,i}^{(m)}(\mathbf z')\|\le\|z_i-z_i'\|+\frac{\eta_tL_g}{b}\sum_{r=1}^b\left(\|z_i-z_i'\|+|f_{\mathbf z}(x_r)-f_{\mathbf z'}(x_r)|\right).$$

Using the prediction bound,

$$\|T_{t,B,i}^{(m)}(\mathbf z)-T_{t,B,i}^{(m)}(\mathbf z')\|\le(1+\eta_tL_g)\|z_i-z_i'\|+\eta_tL_gM_\phi\|\mathbf z-\mathbf z'\|_{\mathrm{av}}.$$

Averaging over $i$ gives

$$\|T_{t,B}^{(m)}(\mathbf z)-T_{t,B}^{(m)}(\mathbf z')\|_{\mathrm{av}}\le\kappa_{\mathrm{av}}\|\mathbf z-\mathbf z'\|_{\mathrm{av}},$$

where we may take

$$\kappa_{\mathrm{av}}=1+\eta_*L_g(1+M_\phi),$$

with

$$\eta_*=\max_{t<T}\eta_t.$$

Taking the maximum over $i$ gives

$$\|T_{t,B}^{(m)}(\mathbf z)-T_{t,B}^{(m)}(\mathbf z')\|_\infty\le(1+\eta_*L_g)\|\mathbf z-\mathbf z'\|_\infty+\eta_*L_gM_\phi\|\mathbf z-\mathbf z'\|_{\mathrm{av}}.$$

Both constants are independent of $m$ and $b$. This comes from the two averagings: the prediction is an average over $m$ particles, and the update is an average over $b$ examples.

The corresponding same-minibatch loss bound is

$$|\ell_B^{(m)}(\mathbf z)-\ell_B^{(m)}(\mathbf z')|\le M_\lambda M_\phi\|\mathbf z-\mathbf z'\|_{\mathrm{av}}.$$

Now suppose that batches $B$ and $B'$ differ in exactly one example. Then, only one term in the update changes. Since $\|g\|\le G$,

$$\|T_{t,B}^{(m)}(\mathbf z)-T_{t,B'}^{(m)}(\mathbf z)\|_\infty\le\frac{2\eta_*G}{b}.$$

Similarly, only one term in the loss changes, so:

$$|\ell_B^{(m)}(\mathbf z)-\ell_{B'}^{(m)}(\mathbf z)|\le\frac{2\Lambda}{b}.$$

We also need to know how the effect of replacing an example changes when the particle configuration changes. Suppose again that $B$ and $B'$ differ in one example. Applying the Lipschitz bound on $g$ to the replaced example and to its independent copy gives

$$\left\|[T_{t,B}^{(m)}(\mathbf z)-T_{t,B'}^{(m)}(\mathbf z)]-[T_{t,B}^{(m)}(\mathbf z')-T_{t,B'}^{(m)}(\mathbf z')]\right\|_{\mathrm{av}}\le\frac{C}{b}\|\mathbf z-\mathbf z'\|_{\mathrm{av}},$$

where $C$ depends only on $\eta_*$, $L_g$, and $M_\phi$.

The analogous loss bound is

$$\left|[\ell_B^{(m)}(\mathbf z)-\ell_{B'}^{(m)}(\mathbf z)]-[\ell_B^{(m)}(\mathbf z')-\ell_{B'}^{(m)}(\mathbf z')]\right|\le\frac{C}{b}\|\mathbf z-\mathbf z'\|_{\mathrm{av}}.$$

We can now prove the first two replacement bounds.

First, replace one initialized neuron. Let's couple the original and perturbed runs so that they use the same data stream. Let their particle configurations be $\mathbf Z^t$ and $\widetilde{\mathbf Z}^t$, and define

$$a_t=\|\mathbf Z^t-\widetilde{\mathbf Z}^t\|_{\mathrm{av}}.$$

At initialization, only one of the $m$ particles differs. Since $K$ is bounded, there is a constant $D_K$ such that

$$a_0\le\frac{D_K}{m}.$$

The two runs use the same batch at every step, so

$$a_{t+1}\le\kappa_{\mathrm{av}}a_t.$$

Unrolling the recursion, we get

$$a_t\le\frac{D_K\kappa_{\mathrm{av}}^t}{m}.$$

The loss difference at step $t$ is therefore bounded by

$$|L_{m,b,t}-L_{m,b,t}^{(i)}|\le M_\lambda M_\phi a_t\le\frac{M_\lambda M_\phi D_K\kappa_{\mathrm{av}}^t}{m}.$$

Hence

$$\|\Delta_i^ZL\|^2\le\frac{M_\lambda^2M_\phi^2D_K^2}{m^2}\sum_{t=0}^{T-1}\kappa_{\mathrm{av}}^{2t}.$$

Since $T$ is fixed, the sum is a constant depending only on $T$. Therefore there is a constant $A_T$ such that

$$\|\Delta_i^ZL\|\le\frac{A_T}{m}.$$

Now replace one example $\xi_{s,r}$.

The two runs have identical particle states until step $s$. At the loss recorded at step $s$, one of the $b$ loss summands changes, so

$$|L_{m,b,s}-L_{m,b,s}^{(s,r)}|\le\frac{2\Lambda}{b}.$$

At the update at step $s$, one of the $b$ update summands changes, so

$$\|\mathbf Z^{s+1}-\widetilde{\mathbf Z}^{s+1}\|_\infty\le\frac{2\eta_*G}{b}.$$

The same bound also holds in the average norm.

For $t>s$, define

$$a_t=\|\mathbf Z^t-\widetilde{\mathbf Z}^t\|_{\mathrm{av}},$$

and

$$d_t=\|\mathbf Z^t-\widetilde{\mathbf Z}^t\|_\infty.$$

After step $s$, the two runs again use the same batches. The stability inequalities give

$$a_{t+1}\le\kappa_{\mathrm{av}}a_t,$$

and

$$d_{t+1}\le(1+\eta_*L_g)d_t+\eta_*L_gM_\phi a_t.$$

Therefore there is a constant $\kappa_{\mathrm{ex}}$ such that

$$a_{t+1}+d_{t+1}\le\kappa_{\mathrm{ex}}(a_t+d_t).$$

Since $a_{s+1}+d_{s+1}=O(1/b)$, it follows that for some constant $K_{\mathrm{ex},T}$,

$$a_t+d_t\le\frac{K_{\mathrm{ex},T}}{b}$$

for every $t>s$, by unrolling the recursion.

At later steps, the two runs use the same loss batch, so

$$|L_{m,b,t}-L_{m,b,t}^{(s,r)}|\le M_\lambda M_\phi a_t\le\frac{M_\lambda M_\phi K_{\mathrm{ex},T}}{b}.$$

Combining this with the direct change at step $s$, there is a constant $B_T$ such that

$$\|\Delta_{s,r}^{\xi}L\|\le\frac{B_T}{b}.$$

Now it remains to prove the mixed replacement bound

$$\|\Delta_i^Z\Delta_{s,r}^{\xi}L\| \leq \frac{C_T}{mb}.$$

We first record a deterministic second-order difference lemma.

Rectangle lemma. Let $F:\Omega\to\mathbb R^q$, where $\Omega$ is convex. Suppose

$$\sup_{x\in\Omega}\|DF(x)\|_{\mathrm{op}}\leq M_F$$

and

$$\|DF(x)-DF(y)\|_{\mathrm{op}} \leq H_F\|x-y\|.$$

For four points $q^{ac}\in\Omega$, with $a,c\in\{0,1\}$, define

$$r=q^{00}-q^{10}-q^{01}+q^{11},$$

$$\alpha= \max_{c\in\{0,1\}} \|q^{0c}-q^{1c}\|,$$

and

$$\delta= \max_{a\in\{0,1\}} \|q^{a0}-q^{a1}\|.$$

Then

$$\|F(q^{00})-F(q^{10})-F(q^{01})+F(q^{11})\| \leq C_F\left(\|r\|+\alpha\delta\right),$$

where $C_F$ depends only on the derivative bounds and on the compact domain containing the four points.

To prove this, write

$$h_0=q^{00}-q^{10}, \qquad h_1=q^{01}-q^{11}.$$

Then

$$h_0-h_1=r.$$

By the fundamental theorem of calculus,

$$F(q^{00})-F(q^{10}) = \int_0^1 DF(q^{10}+\theta h_0)h_0\,\mathrm d\theta,$$

and

$$F(q^{01})-F(q^{11}) = \int_0^1 DF(q^{11}+\theta h_1)h_1\,\mathrm d\theta.$$

Subtracting these expressions and adding and subtracting $DF(q^{10}+\theta h_0)h_1$ gives

$$\begin{aligned} &F(q^{00})-F(q^{10})-F(q^{01})+F(q^{11})\\ &= \int_0^1 DF(q^{10}+\theta h_0)r\,\mathrm d\theta\\ &\quad+ \int_0^1 \left[ DF(q^{10}+\theta h_0) - DF(q^{11}+\theta h_1) \right]h_1\,\mathrm d\theta. \end{aligned}$$

The first integral has norm at most $M_F\|r\|$. For the second integral,

$$\begin{aligned} \| (q^{10}+\theta h_0) - (q^{11}+\theta h_1) \| &\leq \|q^{10}-q^{11}\| + \theta\|h_0-h_1\|\\ &\leq \delta+\|r\|. \end{aligned}$$

Since $\|h_1\|\leq\alpha$, the second integral is bounded by

$$H_F\alpha(\delta+\|r\|).$$

The four points lie in a fixed compact set, so $\alpha$ is uniformly bounded. The term $\alpha\|r\|$ can therefore be absorbed into the coefficient of $\|r\|$, which proves the lemma.

We now apply the lemma to four coupled training runs. Write their particle configurations as

$$\mathbf Z^{ac,t} = (Z_1^{ac,t},\ldots,Z_m^{ac,t}), \qquad a,c\in\{0,1\},$$

where $a=1$ means that initialized neuron $i$ was replaced, and $c=1$ means that example $\xi_{s,r}$ was replaced.

For each particle $j$, define its rectangle difference by

$$r_j^t = Z_j^{00,t} - Z_j^{10,t} - Z_j^{01,t} + Z_j^{11,t}.$$

Also define the particlewise one-factor perturbations

$$\alpha_j^t = \max_{c\in\{0,1\}} \|Z_j^{0c,t}-Z_j^{1c,t}\|,$$

and

$$\delta_j^t = \max_{a\in\{0,1\}} \|Z_j^{a0,t}-Z_j^{a1,t}\|.$$

At the configuration level, define

$$a_t = \max_{c\in\{0,1\}} \|\mathbf Z^{0c,t}-\mathbf Z^{1c,t}\|_{\mathrm{av}},$$

$$d_t = \max_{a\in\{0,1\}} \|\mathbf Z^{a0,t}-\mathbf Z^{a1,t}\|_\infty,$$

and

$$R_t = \frac1m\sum_{j=1}^m\|r_j^t\|.$$

The one-neuron and one-example arguments already give, uniformly for $t<T$ and after enlarging $A_T$ and $B_T$ if necessary,

$$a_t\leq\frac{A_T}{m}, \qquad d_t\leq\frac{B_T}{b}.$$

We also have

$$\frac1m\sum_{j=1}^m\alpha_j^t \leq 2a_t,$$

because the maximum of two nonnegative quantities is at most their sum, and

$$\delta_j^t\leq d_t$$

for every particle $j$.

We first control the corresponding rectangle difference of the prediction.

For a fixed input $x$, define

$$\Pi_t(x) = f_{\mathbf Z^{00,t}}(x) - f_{\mathbf Z^{10,t}}(x) - f_{\mathbf Z^{01,t}}(x) + f_{\mathbf Z^{11,t}}(x).$$

Since

$$f_{\mathbf z}(x) = \frac1m\sum_{j=1}^m\phi(z_j,x),$$

applying the rectangle lemma to the map $z\mapsto\phi(z,x)$ particle by particle gives

$$\begin{aligned} |\Pi_t(x)| &\leq \frac{C_\phi}{m} \sum_{j=1}^m ( \|r_j^t\| + \alpha_j^t\delta_j^t)\\ &\leq C_\phi ( R_t + d_t\frac1m\sum_{j=1}^m\alpha_j^t ) \\ &\leq C_\phi(R_t+2a_td_t). \end{aligned}$$

After changing the constant, we may write this as

$$|\Pi_t(x)| \leq C_\phi(R_t+a_td_t).$$