Pipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Overparameterized networks and training to interpolation

1 · Prerequisites

2 · Logical flowchart

3 · Definitions, theorems and proofs

LemmaStatement: Literature-sourcedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

The Gaussian activation normalizer is finite and positive

Statement

Assume AC. Let $Z$ have the standard normal law on $R$ . Suppose $σ : R \to R$ is analytic, nonpolynomial, satisfies $∣ σ (0) ∣ \leq B$ for some finite $B$ , and is $L$ -Lipschitz for a finite $L$ . Then $0 < E [σ (Z)^{2}] < \infty$ . Consequently the normalization constant

$c_{σ} : = (E [σ (Z)^{2}])^{- 1}$

is a well-defined positive finite real number.

Statement references

Du et al., Condition 3.1 and equation (2)

Feller, Gaussian distribution and finite second moment

Facts & Assumptions

Given: AC, the activation $σ$ , its constants $B, L$ , and a standard normal random variable $Z$ .

[A1]

AC is assumed by the standard-normal-law and Gaussian-moment suppliers. The Axiom of Choice

[F1]

The standard normal law has second moment $1$ . Standard normal and normal laws Gaussian even moments for Brownian increments

Proof

technique · bound the activation by an affine function of $|Z|$, then use continuity and nonpolynomiality for strict positivity

1.1A1F1givenalgebra

Lipschitz continuity gives $∣ σ (z) ∣ \leq B + L ∣ z ∣$ , hence $σ (z)^{2} \leq 2 B^{2} + 2 L^{2} z^{2}$ . By [F1], $E σ (Z)^{2} \leq 2 B^{2} + 2 L^{2} < \infty$ .

1.2A1F1givenchoose

A nonpolynomial analytic function is not identically zero, so choose $z_{0}$ with $σ (z_{0}) \neq 0$ . Continuity gives an open interval around $z_{0}$ on which $∣ σ ∣ \geq ∣ σ (z_{0}) ∣ / 2$ . The standard normal density is strictly positive on that interval, so its integral of $σ^{2}$ is positive.

2.1step 1.1step 1.2algebra∎

The expectation is both finite and strictly positive by steps 1.1 and 1.2, so its reciprocal exists and is positive and finite.

LemmaStatement: Literature-sourcedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

Gram control and a Taylor remainder imply one-step loss contraction

Statement

Let $r \in R^{n}$ , let $G$ be a real symmetric matrix with eigenvalues in $[λ, Λ]$ for some $0 < λ \leq Λ$ , and suppose $0 < η Λ \leq 1$ . If an update has the form $r^{+} = (I - η G) r + R$ with $∥ R ∥_{2} \leq η λ ∥ r ∥_{2} / 4$ , then for the quadratic loss $L = \frac{1}{2} ∥ r ∥_{2}^{2}$ and $L^{+} = \frac{1}{2} ∥ r^{+} ∥_{2}^{2}$ ,

$L^{+} \leq (1 - η λ / 2) L .$

Statement references

Du et al., empirical loss contraction, Theorems 5.1 and 6.1

Facts & Assumptions

Given: The residual vector, symmetric Gram matrix, eigenvalue bounds, step size, and remainder bound.

[F1]

A real symmetric matrix has an orthonormal eigenbasis. Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis

[F2]

The Euclidean norm satisfies the triangle inequality. Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation

Proof

technique · bound the spectral norm of the linear contraction and then square the residual-norm bound

1.1F1F2givenalgebra

By [F1], the eigenvalues $μ_{j}$ of $G$ lie in $[λ, Λ]$ , so those of $I - η G$ lie in $[1 - η Λ, 1 - η λ] \subseteq [0, 1 - η λ]$ . Expanding $r$ in an orthonormal eigenbasis gives $∥ (I - η G) r ∥_{2}^{2} = \sum_{j} (1 - η μ_{j})^{2} r_{j}^{2} \leq (1 - η λ)^{2} ∥ r ∥_{2}^{2}$ . The norm triangle inequality [F2] with the remainder hypothesis then yields $∥ r^{+} ∥_{2} \leq (1 - 3 η λ / 4) ∥ r ∥_{2}$ .

2.1step 1.1algebra∎

Put $t = η λ \in (0, 1]$ . Then $(1 - 3 t / 4)^{2} \leq 1 - t / 2$ , since $1 - t / 2 - (1 - 3 t / 4)^{2} = t (1 - 9 t / 16) \geq 7 t / 16 > 0$ . Squaring the estimate in step 1.1 and multiplying by $1 / 2$ yields $L^{+} \leq (1 - η λ / 2) L$ .

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Fully connected and residual networks with the Du Gram kernel

Definition

Assume AC, DC and countable choice for the Gaussian probability-law constructions below. The displayed finite real network recurrences and empirical loss are deterministic definitions for fixed parameters. Fix positive integers $d, n, H, m$ , training inputs $x_{1}, \dots, x_{n} \in R^{d}$ with $∥ x_{i} ∥_{2} = 1$ , labels $y_{1}, \dots, y_{n} \in R$ , an analytic nonpolynomial activation $σ$ satisfying $∣ σ (0) ∣ < \infty$ and finite Lipschitz constants for $σ$ and $σ^{'}$ , and the positive finite normalization $c_{σ} = (E_{Z \sim N (0, 1)} [σ (Z)^{2}])^{- 1}$ . A fully connected network of width $m$ and depth $H$ is the finite feedforward recurrence

$x^{(0)} = x, x^{(h)} = \sqrt{c_{σ} / m} σ (W^{(h)} x^{(h - 1)}) (1 \leq h \leq H), f_{f c} (x, θ) = a^{T} x^{(H)},$

where $W^{(1)} \in R^{m \times d}$ , $W^{(h)} \in R^{m \times m}$ for $h \geq 2$ , $a \in R^{m}$ , and $σ$ acts coordinatewise. The residual network uses the same first layer and then

$x^{(1)} = \sqrt{c_{σ} / m} σ (W^{(1)} x), x^{(h)} = x^{(h - 1)} + \frac{c_{r e s}}{H \sqrt{m}} σ (W^{(h)} x^{(h - 1)}) (2 \leq h \leq H), f_{r e s} (x, θ) = a^{T} x^{(H)},$

with $0 < c_{r e s} < 1$ . In either architecture, random initialization means all entries of all matrices $W^{(h)}$ and of $a$ are independent $N (0, 1)$ random variables; all these entries are trained by full-batch gradient descent. The empirical quadratic loss is $L (θ) = \frac{1}{2} \sum_{i = 1}^{n} (f (x_{i}, θ) - y_{i})^{2}$ .

For the fully connected architecture and the same fixed data, define the population matrices by

$K_{i j}^{(0)} = ⟨ x_{i}, x_{j} ⟩ .$

For $1 \leq h < H$ , let $(U_{i j}^{(h)}, V_{i j}^{(h)})$ be a centered bivariate normal vector with covariance

$A_{i j}^{(h)} = (\begin{array}{cc} K_{i i}^{(h - 1)} & K_{i j}^{(h - 1)} \\ K_{j i}^{(h - 1)} & K_{j j}^{(h - 1)} \end{array}),$

and put $K_{i j}^{(h)} = c_{σ} E [σ (U_{i j}^{(h)}) σ (V_{i j}^{(h)})]$ . For $h = H$ , use the same bivariate-normal definition with $A_{i j}^{(H)}$ formed from $K^{(H - 1)}$ , and set

$K_{i j}^{(H)} = c_{σ} K_{i j}^{(H - 1)} E [σ^{'} (U_{i j}^{(H)}) σ^{'} (V_{i j}^{(H)})] .$

When $H = 1$ , this last formula uses $K^{(0)}$ directly and there are no intermediate activation-covariance matrices. For the fully connected theorem, this terminal matrix is denoted $K_{f c}^{(H)}$ .

For the residual architecture with $H \geq 2$ , use a separate sequence $S^{(h)}$ and mean vector $b^{(h)}$ . Set $S^{(0)} = K^{(0)}$ . For $G^{(0)} \sim N_{n} (0, S^{(0)})$ , put

$S_{i j}^{(1)} = c_{σ} E [σ (G_{i}^{(0)}) σ (G_{j}^{(0)})], b_{i}^{(1)} = \sqrt{c_{σ}} E [σ (G_{i}^{(0)})] .$

Write $α = c_{r e s} / H$ . For $2 \leq h < H$ , take a fresh centered Gaussian vector $G^{(h - 1)}$ with covariance $S^{(h - 1)}$ , put $μ_{i}^{(h - 1)} = E [σ (G_{i}^{(h - 1)})]$ , and define

$S_{i j}^{(h)} = S_{i j}^{(h - 1)} + α (b_{i}^{(h - 1)} μ_{j}^{(h - 1)} + b_{j}^{(h - 1)} μ_{i}^{(h - 1)}) + α^{2} E [σ (G_{i}^{(h - 1)}) σ (G_{j}^{(h - 1)})], b_{i}^{(h)} = b_{i}^{(h - 1)} + α μ_{i}^{(h - 1)} .$

For $G \sim N_{n} (0, S^{(H - 1)})$ , define the residual terminal matrix by

$K_{r e s, i j}^{(H)} = \frac{c_{r e s}^{2}}{H^{2}} S_{i j}^{(H - 1)} E [σ^{'} (G_{i}) σ^{'} (G_{j})] .$

The fully connected and residual convergence statements use $K_{f c}^{(H)}$ and $K_{r e s}^{(H)}$ , respectively. At $H = 1$ , the two architectures coincide; define $K_{r e s}^{(1)} = K_{f c}^{(1)}$ . The residual recursion above is the scalar specialization of the source's general mean/second-moment recursion, equation (16); in particular it includes the mean cross terms. Its terminal Gaussian covariance is $S^{(H - 1)}$ , as determined by the finite-width last-layer Gram formula (14).

The residual recurrence has one identity contribution from $x^{(h - 1)}$ and one nonlinear contribution at every layer $2 \leq h \leq H$ ; the arrows below depict that convention for one generic layer and do not enter any proof.

diagram failed to render:
\begin{tikzpicture}[>=stealth,node distance=1.3cm]
  \node (in) {$x^{(h-1)}$};
  \node[draw,rectangle,right=1.7cm of in] (act) {$\frac{c_{\rm res}}{H\sqrt m}\sigma(W^{(h)}x^{(h-1)})$};
  \node[draw,circle,right=2.0cm of act] (sum) {$+$};
  \node[right=1.2cm of sum] (out) {$x^{(h)}$};
  \draw[->] (in) -- (act);
  \draw[->] (act) -- (sum);
  \draw[->] (in) to[bend right=28] (sum);
  \draw[->] (sum) -- (out);
\end{tikzpicture}

Definition references

Du et al., fully connected and residual architectures, equations (2)–(3)

Du et al., population Gram recursions, Definitions 5.1 and 6.1, equations (7) and (8)

Du et al., Appendix C, last-layer Gram formula (14)

Du et al., Appendix E.1, general population mean and second-moment recursion (16)–(17)

Finite feedforward computation graphs and layered perceptrons

Princeton Theory of Deep Learning, Chapter 8, §§8.1–8.5, infinite-width context

LemmaStatement: Literature-sourcedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

The recursively defined population Gram matrices are finite, symmetric, and positive semidefinite

Statement

Assume AC, DC and countable choice. Under the hypotheses and notation defining the Du population Gram recursion, every fully connected matrix $K^{(h)}$ , every residual feature second-moment matrix $S^{(h)}$ , and both terminal matrices are finite, symmetric, and positive semidefinite. The fully connected matrices satisfy $K_{i i}^{(h)} = 1$ for $0 \leq h < H$ . For the residual sequence, $S^{(h)} - b^{(h)} (b^{(h)})^{T}$ is positive semidefinite for $1 \leq h < H$ ; its diagonal is not asserted to equal one.

Statement references

Du et al., Definition 5.1 and Appendix E

Facts & Assumptions

Given: The finite unit-norm data, activation, normalization, Gaussian covariance convention, and matrices from the definition.

[F1]

The architecture and matrices are defined by the stated recurrences, with $c_{σ} > 0$ and finite. Fully connected and residual networks with the Du Gram kernel

[F5]

The normalizer satisfies $c_{σ} E [σ (Z)^{2}] = 1$ for standard normal $Z$ . The Gaussian activation normalizer is finite and positive

[F6]

A property holding at zero and preserved by successor holds for every natural-number index. The principle of mathematical induction

[F2]

A finite-dimensional positive semidefinite covariance matrix defines a possibly singular centered multivariate normal law, with the listed covariance and finite second moments. Multivariate normal law, including singular covariance

[F3]

A real self-adjoint matrix has an orthonormal eigenbasis. Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis

[F4]

Countably many independent copies of a normal vector can be constructed, and expectations of products of integrable independent variables factor. Countably many independent copies of a prescribed law exist Expectations factor over finite products of independent random variables

[A1]

Assume AC as required by the multivariate normal-law supplier. The Axiom of Choice

[A2]

Assume DC and countable choice as required by the independent-copy supplier. The axiom of dependent choice: a relation in which every element is related to something admits an $N$ -indexed chain The Axiom of Countable Choice ( ${A C}_{ω}$ )

[F7]

For two Borel probability laws on finite-dimensional real spaces, their product measure exists, has total mass one and satisfies the rectangle formula. Thus its two coordinate projections have the prescribed laws and are independent. For sigma-finite factors, the product measure exists, has the rectangle formula, is sigma-finite, and is unique

[F8]

If $X, Y$ have finite second moments, then $E ∣ X Y ∣ \leq (E X^{2})^{1 / 2} (E Y^{2})^{1 / 2}$ . This ensures integrability of the Gaussian activation products in steps 2.1 and 4.1 and the terminal-coordinate products in steps 3.1 and 5.1. Cauchy-Schwarz for random variables

Proof

technique · induction on the layer index, using Gaussian feature vectors to express each quadratic form as an expectation of a square

1.1baseF1givenalgebra

The input matrix $K^{(0)}$ is symmetric, and for $v \in R^{n}$ , $v^{T} K^{(0)} v = ∥ \sum_{i} v_{i} x_{i} ∥_{2}^{2} \geq 0$ . Its diagonal entries are $∥ x_{i} ∥_{2}^{2} = 1$ , giving the base case.

2.1ihA1F1F2F3F5F8step 1.1algebra

Assume the induction hypothesis that $K^{(h - 1)}$ is finite, symmetric positive semidefinite, and has diagonal $1$ , for some $1 \leq h < H$ . By [F2]–[F3], take $G \sim N_{n} (0, K^{(h - 1)})$ ; each pair $(G_{i}, G_{j})$ has covariance $A_{i j}^{(h)}$ . The growth bound $∣ σ (z) ∣ \leq ∣ σ (0) ∣ + L ∣ z ∣$ and finite Gaussian second moments put each $σ (G_{i})$ in $L^{2}$ ; [F8] then makes every product $σ (G_{i}) σ (G_{j})$ integrable. Thus $K^{(h)}$ is finite and symmetric, and for every $v$ , $v^{T} K^{(h)} v = c_{σ} E [(\sum_{i} v_{i} σ (G_{i}))^{2}] \geq 0$ . Because $G_{i} \sim N (0, 1)$ , its diagonal is $c_{σ} E [σ (Z)^{2}] = 1$ by [F5]. This establishes the induction step.

3.1A1A2F2F3F4F6step 1.1step 2.1algebradischarge-induction

For the fixed $H$ , let $P (h)$ mean that $K^{(h)}$ is finite, symmetric positive semidefinite, and has diagonal $1$ , for $0 \leq h < H$ . Define $Q (k)$ to mean $P (j)$ for every $j \leq \min (k, H - 1)$ . Step 1.1 gives $Q (0)$ . If $Q (k)$ and $k + 1 < H$ , step 2.1 applied with $h = k + 1$ gives $P (k + 1)$ and hence $Q (k + 1)$ ; if $k + 1 \geq H$ , $Q (k + 1)$ adds no new index. By [F6], $Q (H - 1)$ holds, so $K^{(H - 1)}$ is finite, symmetric positive semidefinite, and has diagonal $1$ ; when $H = 1$ , this is exactly the base matrix $K^{(0)}$ . By [F4], take independent $G, G^{'}$ both distributed as $N_{n} (0, K^{(H - 1)})$ . The vector with coordinates $Y_{i} = \sqrt{c_{σ}} G_{i}^{'} σ^{'} (G_{i})$ has finite second moments; $σ^{'}$ is bounded because it is the derivative of a Lipschitz differentiable function. Factoring expectations of independent variables gives $E [Y_{i} Y_{j}] = c_{σ} K_{i j}^{(H - 1)} E [σ^{'} (G_{i}) σ^{'} (G_{j})] = K_{i j}^{(H)}$ . Therefore $K^{(H)}$ is finite and symmetric, and $v^{T} K^{(H)} v = E [(\sum_{i} v_{i} Y_{i})^{2}] \geq 0$ for every $v$ . This proves the fully connected terminal claim and discharges that induction.

3.2A1F1F2step 2.1constructalgebra

For the residual base layer let $G_{0} \sim N_{n} (0, S^{(0)})$ and $V^{(1)} = \sqrt{c_{σ}} σ (G_{0})$ , with activation applied coordinatewise. Then $E V^{(1)} = b^{(1)}$ and $E [V^{(1)} (V^{(1)})^{T}] = S^{(1)}$ by [F1]. The growth bound used in step 2.1 proves finite second moments. For every $v$ , $v^{T} S^{(1)} v = E [(v^{T} V^{(1)})^{2}] \geq 0$ , while $S^{(1)} - b^{(1)} (b^{(1)})^{T}$ is its covariance and has quadratic form $E [(v^{T} (V^{(1)} - E V^{(1)}))^{2}] \geq 0$ . Thus both matrices are symmetric positive semidefinite.

4.1A1A2F1F2F4F6F7F8step 3.2constructalgebra

Suppose a finite-second-moment vector $V^{(h - 1)}$ has mean $b^{(h - 1)}$ and second-moment matrix $S^{(h - 1)}$ . Let $μ$ be the Borel law of this generally non-Gaussian vector and let $ν = N_{n} (0, S^{(h - 1)})$ , which exists by [F2]. Both are probability measures and hence sigma-finite. By [F7], on $(R^{n} \times R^{n}, μ \times ν)$ the coordinate projections $V$ and $G$ have laws $μ$ and $ν$ and are independent: for Borel sets $A, B$ , the probability of ${V \in A, G \in B}$ is $μ (A) ν (B)$ . Put $V^{(h)} = V + α σ (G)$ . Finite second moments follow from the growth bound and $(u + v)^{2} \leq 2 u^{2} + 2 v^{2}$ . Independence gives $E V^{(h)} = b^{(h - 1)} + α μ^{(h - 1)}$ and $E [V_{i}^{(h)} V_{j}^{(h)}] = S_{i j}^{(h - 1)} + α (b_{i}^{(h - 1)} μ_{j}^{(h - 1)} + b_{j}^{(h - 1)} μ_{i}^{(h - 1)}) + α^{2} E [σ (G_{i}) σ (G_{j})] = S_{i j}^{(h)}$ . For every $v$ , $v^{T} S^{(h)} v = E [(v^{T} V^{(h)})^{2}] \geq 0$ , and $S^{(h)} - b^{(h)} (b^{(h)})^{T}$ is the covariance of $V^{(h)}$ , so its quadratic form is also an expectation of a square. Thus both matrices are finite, symmetric positive semidefinite at this stage, which supplies the covariance hypothesis for the next stage. Iterating through the finitely many layers is justified by [F6].

5.1A1A2F1F2F4step 3.1step 4.1constructalgebradischarge-induction∎

For $H \geq 2$ , take independent $G, G^{'} \sim N_{n} (0, S^{(H - 1)})$ and set $Y_{i} = (c_{r e s} / H) G_{i}^{'} σ^{'} (G_{i})$ . The boundedness $∣ σ^{'} ∣ \leq L$ gives finite second moments, and independence gives $E [Y_{i} Y_{j}] = K_{r e s, i j}^{(H)}$ . Consequently this terminal matrix is symmetric positive semidefinite. At $H = 1$ it equals the already proved fully connected matrix by definition. This proves all residual assertions.

LemmaStatement: Literature-sourcedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

Gradient descent induces an exact output Gram update with a Taylor remainder

Statement

For any fixed finite real network obeying either architecture recurrence defined on the A page, let $u (θ) = (f (x_{i}, θ))_{i = 1}^{n} \in R^{n}$ , let $y = (y_{i})_{i = 1}^{n}$ , let $J (θ) \in R^{n \times p}$ have row $i$ equal to the gradient of $f (x_{i}, θ)$ with respect to the vector of all trainable parameters, and set $G (θ) = J (θ) J (θ)^{T}$ . For the empirical quadratic loss $L (θ) = \frac{1}{2} ∥ u (θ) - y ∥_{2}^{2}$ , one full-batch gradient-descent step with step size $η > 0$ satisfies

$u (θ^{+}) = u (θ) - η G (θ) (u (θ) - y) + R,$

where $θ^{+} = θ - η J (θ)^{T} (u (θ) - y)$ and $R$ is the first-order Taylor remainder of the differentiable map $u$ at $θ$ in direction $- η J (θ)^{T} (u (θ) - y)$ . No size bound on $R$ is asserted here.

Statement references

Du et al., gradient-descent dynamics, §§4 and B.1

Facts & Assumptions

Given: One finite network, its trainable parameter vector, a fixed data set and labels, and a step size $η > 0$ .

[F1]

The network is a finite composition of linear maps and an analytic coordinatewise activation, so its output map is continuously differentiable in all trainable parameters. Fully connected and residual networks with the Du Gram kernel

[F2]

Reverse accumulation through a finite $C^{1}$ parameterized recurrence gives the exact parameter gradient, including all parameter uses. Reverse accumulation sums gradients over shared parameter uses

[F3]

Fixed-step gradient descent updates the parameter by subtracting $η$ times the Euclidean gradient. Gradient descent

[F4]

Differentiability in finite-dimensional real parameter spaces means a linear first-order approximation with a remainder $o (∥ h ∥_{2})$ . The real Frechet derivative on real and complex matrix spaces with the Frobenius norm

Proof

technique · express the loss gradient by the output Jacobian and apply the defining first-order expansion of the output map

1.1F2F3givenalgebra

Write $r = u (θ) - y$ . By the scalar chain rule applied to $\frac{1}{2} \sum_{i} (u_{i} - y_{i})^{2}$ , the parameter gradient is $J (θ)^{T} r$ . By [F3], $h : = θ^{+} - θ = - η J (θ)^{T} r$ .

2.1F1F4step 1.1algebra∎

Since $u$ is differentiable, [F4] gives $u (θ + h) = u (θ) + J (θ) h + R$ , where $R : = u (θ + h) - u (θ) - J (θ) h$ is the first-order remainder. Substitute $h = - η J (θ)^{T} r$ to get $J (θ) h = - η J (θ) J (θ)^{T} r = - η G (θ) r$ , which is the claimed identity.

LemmaStatement: Literature-sourcedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

Gaussian output initialization concentrates conditionally on the hidden features

Statement

Assume AC, DC and countable choice. Fix hidden-layer feature vectors $ϕ_{1}, \dots, ϕ_{n} \in R^{m}$ , form the matrix $Φ \in R^{n \times m}$ with rows $ϕ_{i}^{T}$ , and let the independent output-weight vector $a \sim N_{m} (0, I_{m})$ . Put $u = Φ a$ and $G = Φ Φ^{T}$ . Then for every $0 < δ < 1$ ,

$P {∥ u ∥_{2} \leq \sqrt{tr (G)} + ∥ Φ ∥_{o p} \sqrt{2 \log (1 / δ)}} \geq 1 - δ,$

where $∥ Φ ∥_{o p} = \sup_{∥ v ∥_{2} = 1} ∥ Φ v ∥_{2}$ . The probability is conditional on the fixed hidden-layer features and is over $a$ only.

Statement references

Du et al., random Gaussian output initialization and Appendix B

Facts & Assumptions

Given: AC, DC, countable choice, fixed feature vectors, and an independent standard Gaussian output vector.

[A1]

AC, DC and countable choice are assumed by the Gaussian concentration supplier. The Axiom of Choice The axiom of dependent choice: a relation in which every element is related to something admits an $N$ -indexed chain The Axiom of Countable Choice ( ${A C}_{ω}$ )

[F1]

For a standard Gaussian vector $Z$ and an $L$ -Lipschitz real function $g$ , $P {g (Z) \geq E g (Z) + r} \leq e^{- r^{2} / (2 L^{2})}$ for $L > 0, r > 0$ ; for $L = 0$ the upper-tail event is empty. Lipschitz concentration for standard Gaussian measure

[F2]

A standard multivariate normal vector has covariance identity, and a fixed linear functional has variance given by its covariance quadratic form. Multivariate normal law, including singular covariance

[F3]

Cauchy–Schwarz bounds $E ∣ X Y ∣$ by the product of the $L^{2}$ norms. Cauchy-Schwarz for random variables

[F4]

The Euclidean norm satisfies the triangle inequality and hence the reverse triangle inequality. Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation

Proof

technique · apply one-sided Gaussian concentration to the norm of a fixed linear image and bound its mean by its second moment

1.1F2F3F4givenalgebra

[F4] gives $∣ ∥ Φ a ∥_{2} - ∥ Φ b ∥_{2} ∣ \leq ∥ Φ (a - b) ∥_{2} \leq ∥ Φ ∥_{o p} ∥ a - b ∥_{2}$ , so $a \mapsto ∥ Φ a ∥_{2}$ is $∥ Φ ∥_{o p}$ -Lipschitz. Since $E [a a^{T}] = I_{m}$ by [F2], $E ∥ Φ a ∥_{2}^{2} = tr (Φ Φ^{T}) = tr (G)$ ; [F3] with $X = ∥ Φ a ∥_{2}$ and $Y = 1$ yields $E ∥ Φ a ∥_{2} \leq \sqrt{tr (G)}$ .

2.1A1F1F2step 1.1algebra∎

If $∥ Φ ∥_{o p} = 0$ , then $u = 0$ and the asserted event has probability one. Otherwise apply [F1] to $g (a) = ∥ Φ a ∥_{2}$ with $r = ∥ Φ ∥_{o p} \sqrt{2 \log (1 / δ)} > 0$ . The upper-tail probability is at most $\exp (- \log (1 / δ)) = δ$ , and the mean bound in step 1.1 gives the displayed threshold.

LemmaStatement: AI-adaptedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

Local Gram positivity and loss smoothness give confined gradient descent

Statement

Let $u : R^{p} \to R^{n}$ be $C^{2}$ , $L = \frac{1}{2} ∥ u - y ∥^{2}$ , and $r_{0} = u (θ_{0}) - y$ . On the closed ball $B (θ_{0}, R)$ suppose a block $J_{*}$ of the output Jacobian satisfies $J_{*} J_{*}^{T} ⪰ (λ / 2) I_{n}$ and $∥ \nabla^{2} L ∥ \leq S$ , with $λ, S > 0$ . If $R > 2 \sqrt{2} ∥ r_{0} ∥ / \sqrt{λ}$ and $0 < η \leq 1 / S$ , every fixed-step gradient-descent iterate stays in the ball,

$L (θ_{k}) \leq (1 - η λ / 2)^{k} L (θ_{0}), \sum_{k \geq 0} ∥ θ_{k + 1} - θ_{k} ∥ \leq 2 \sqrt{2} ∥ r_{0} ∥ / \sqrt{λ} .$

The assertion is trivial for $r_{0} = 0$ ; otherwise the hypotheses imply $0 < η λ / 2 \leq 1$ .

Statement references

Du et al., output Gram descent mechanism

Facts & Assumptions

Given: The output map, quadratic loss, ball, spectral and Hessian bounds, and step size.

[F1]

Gradient descent uses $θ^{+} = θ - η \nabla L (θ)$ . Gradient descent

[F2]

For a scalar $C^{2}$ function on a segment, the first-order Taylor remainder is the integral of its second derivative against the linear remainder kernel. Taylor's theorem with an integral remainder

[F3]

The Hessian norm is the induced operator norm on the finite-dimensional Euclidean parameter space. The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||

[F4]

Euclidean Cauchy–Schwarz gives $∣ a^{T} b ∣ \leq ∥ a ∥_{2} ∥ b ∥_{2}$ for all real vectors of the same finite dimension. Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation

Proof

1.1F1F2F3F4givenalgebra

Write $g = \nabla L = J^{T} r$ . Since $J J^{T} ⪰ J_{*} J_{*}^{T}$ , $∥ g ∥^{2} = r^{T} J J^{T} r \geq (λ / 2) ∥ r ∥^{2} = λ L$ in the ball. For any step $θ^{+} = θ - h g$ , $0 < h \leq η$ , whose segment stays in the ball, put $ψ (s) = L (θ - s g)$ for $0 \leq s \leq h$ . Then $ψ^{'} (0) = - ∥ g ∥^{2}$ and $ψ^{''} (s) = g^{T} H_{s} g$ , where $H_{s} = \nabla^{2} L (θ - s g)$ . By Euclidean Cauchy–Schwarz [F4] and the induced norm [F3], $∣ g^{T} H_{s} g ∣ \leq ∥ g ∥ ∥ H_{s} g ∥ \leq ∥ g ∥ ∥ H_{s} ∥ ∥ g ∥ \leq S ∥ g ∥^{2}$ ; for $g = 0$ the same bound is immediate. By [F2], $L^{+} = L - h ∥ g ∥^{2} + \int_{0}^{h} (h - s) ψ^{''} (s) d s \leq L - h (1 - S h / 2) ∥ g ∥^{2} \leq (1 - h λ / 2) L$ . If $L > 0$ , nonnegativity of $L^{+}$ gives $h λ / 2 \leq 1$ .

2.1step 1.1algebra

For such a segment with $L > 0$ , $\sqrt{L} - \sqrt{L^{+}} = (L - L^{+}) / (\sqrt{L} + \sqrt{L^{+}}) \geq h ∥ g ∥^{2} / (4 \sqrt{L}) \geq (\sqrt{λ} / 4) h ∥ g ∥$ . If $L = 0$ , $r = 0$ and hence $g = 0$ , so the step is stationary. Telescoping any finite sequence of admissible full or truncated steps gives total parameter path length at most $4 \sqrt{L_{0}} / \sqrt{λ} = 2 \sqrt{2} ∥ r_{0} ∥ / \sqrt{λ}$ .

3.1step 1.1step 2.1algebra∎

Suppose there is a first proposed full step exiting the ball. Truncate that step at the first intersection with its boundary; this is a segment of length $h ∥ g ∥$ with $h \leq η$ , wholly in the ball. Step 2.1 applies to all previous steps and this truncated step, giving total path length strictly less than $R$ . Reaching the boundary from $θ_{0}$ requires length at least $R$ , a contradiction. Thus no exit occurs. Step 1.1 applied at every full step gives the loss rate, and taking the supremum of finite partial path lengths in step 2.1 gives the asserted series bound.

LemmaStatement: AI-adaptedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

Parameter-ball control of the last-layer Gram and loss Hessian

Statement

Fix finite real parameters obeying either Du architecture recurrence, with all parameters equipped with the Euclidean norm (Frobenius norm on each matrix block). At a fixed initialization assume all hidden feature norms are at most $B_{x}$ , all matrices $W^{(h)} (0)$ with $h \geq 2$ have operator norm at most $B_{w} \sqrt{m}$ , $∥ a (0) ∥_{2} \leq B_{a} \sqrt{m}$ , $∥ a (0) ∥_{4} \leq B_{4} m^{1 / 4}$ , and all backward feature derivatives $b_{i, h} (0) = \nabla_{x_{i}^{(h)}} f_{i}$ have coordinate maxima at most $B_{b} M$ , where $M \geq 1$ . For fully connected networks allow $B_{x}, B_{b} \leq A_{0}^{H}$ for a fixed $A_{0} \geq 2$ , while $B_{w}, B_{a}, B_{4}$ are fixed independent of $H$ . There are $A \geq 2, C \geq 1$ depending only on $A_{0}$ , these fixed bounds and the activation, with the following bounds; write $T = A^{H}$ . In the residual case the constants depend also on fixed $c_{r e s}$ , and every $T$ below is replaced by a fixed $C$ independent of $H$ . Uniformly on any parameter ball $∥ θ - θ_{0} ∥ \leq D$ with $D / \sqrt{m} \leq c / T$ (fully connected) or $D / \sqrt{m} \leq c$ (residual),

$\max_{i, h} ∥ x_{i}^{(h)} (θ) - x_{i}^{(h)} (θ_{0}) ∥ \leq T D / \sqrt{m}, ∥ J (θ) ∥_{o p} \leq T \sqrt{n},$

$\max_{i} ∥ \nabla^{2} f_{i} (θ) ∥_{o p} \leq \frac{T M (1 + D)}{\sqrt{m}}, ∥ J_{H} (θ) J_{H} (θ)^{T} - J_{H} (θ_{0}) J_{H} (θ_{0})^{T} ∥_{o p} \leq \frac{T n D}{\sqrt{m}} .$

In the residual last inequality the upper bound is $C n D / (H^{2} \sqrt{m})$ for $H \geq 2$ . The residual first-layer and output-vector derivatives are bounded without a factor $1 / H$ . Consequently, if $r_{0} = u (θ_{0}) - y$ and $L = \frac{1}{2} ∥ u - y ∥^{2}$ , the loss Hessian on the ball satisfies

$∥ \nabla^{2} L ∥_{o p} \leq T n + \frac{T \sqrt{n} (∥ r_{0} ∥ + T \sqrt{n} D) M (1 + D)}{\sqrt{m}} .$

The constants in this last bound can again be fixed independent of $H$ for residual networks. For any segment from $θ$ to $θ + h$ contained in the ball, its output Taylor remainder satisfies

$∥ u (θ + h) - u (θ) - J (θ) h ∥ \leq \frac{T \sqrt{n} M (1 + D)}{2 \sqrt{m}} ∥ h ∥^{2},$

with $T$ replaced by fixed $C$ in the residual case.

Statement references

Du et al., parameter perturbation and gradient arguments B.3–B.7 and C.3–C.7

Facts & Assumptions

Given: The deterministic initialization bounds, the architecture, the parameter ball, and fixed activation constants $∣ σ (0) ∣ \leq B$ , $∣ σ^{'} ∣ \leq L$ , $∣ σ^{''} ∣ \leq β$ .

[F1]

The architectures and scalings are defined locally. Fully connected and residual networks with the Du Gram kernel

[F2]

The chain rule gives the forward variations and backward feature derivatives of the finite network. Reverse accumulation sums gradients over shared parameter uses

[F3]

Euclidean Cauchy–Schwarz bounds vector inner products, coordinate products, and sums over parameter blocks in the estimates below. Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation

[F4]

Restricting a scalar $C^{2}$ output to a parameter line segment gives the first-order Taylor formula with integral remainder used in step 5.1. Taylor's theorem with an integral remainder

[F5]

A $C^{1}$ vector-valued map whose derivative norm is bounded by $M$ on a segment is $M$ -Lipschitz along that segment. If $f : [a, b] \to R^{m}$ is differentiable with integrable $f^{'}$ then $\int_{a}^{b} f^{'} = f (b) - f (a)$ ; and a bounded derivative makes $f$ Lipschitz

[F6]

Matrix operator norms are the induced norms on finite-dimensional inner-product spaces, and the parameter norm uses the Frobenius norm on matrix blocks. The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv|| The Frobenius norm $∥ A ∥_{F} = (\sum_{i, j} ∣ a_{i j} ∣^{2})^{1 / 2}$ on real or complex matrices

[F7]

For $p = 4$ , $∥ a ∥_{4} = (\sum_{r} ∣ a_{r} ∣^{4})^{1 / 4}$ . The $p$ -norms $∥ x ∥_{p}$ for rational $p \geq 1$ , and $∥ x ∥_{\infty}$

Proof

1.1F1F2givenalgebraF6

Write $z_{h} = W_{h} x_{h - 1}$ and $s_{1} = \sqrt{c_{σ}}$ in both architectures, $s_{h} = \sqrt{c_{σ}}$ for fully connected $h \geq 2$ , and $s_{h} = c_{r e s} / H$ for residual $h \geq 2$ . A layer has feature Jacobian $P_{h} = (s_{h} / \sqrt{m}) diag (σ^{'} (z_{h})) W_{h}$ in the fully connected case, and $P_{h} = I + (s_{h} / \sqrt{m}) diag (σ^{'} (z_{h})) W_{h}$ in residual layers $h \geq 2$ . Within the stated ball, $∥ W_{h} ∥ \leq (B_{w} + D / \sqrt{m}) \sqrt{m}$ . Products of consecutive $P_{h}$ , $h \geq 2$ , therefore have norm at most $A^{H}$ in the fully connected case and $\prod_{h} (1 + C / H) \leq e^{C}$ in the residual case. All estimates below use only $h \geq 2$ for matrix operator norms; the input is fixed.

2.1F1step 1.1algebra

Let $e_{h} = ∥ x_{h} (θ) - x_{h} (θ_{0}) ∥$ . Lipschitz continuity gives $e_{1} \leq \sqrt{c_{σ}} L D / \sqrt{m}$ . For fully connected layers, $e_{h} \leq C e_{h - 1} + C A_{0}^{H} D / \sqrt{m}$ ; for residual layers it gives $e_{h} \leq (1 + C / H) e_{h - 1} + C D / (H \sqrt{m})$ , using the fixed upper feature bound in the residual case and the initial exponential envelope in the fully connected case. Summing the geometric recurrences gives $e_{h} \leq T D / \sqrt{m}$ in the first case and $e_{h} \leq C D / \sqrt{m}$ in the second. The imposed smallness of $D / \sqrt{m}$ keeps all feature norms in the required bounds and justifies the recurrences successively. Also $∥ z_{h} (θ) - z_{h} (θ_{0}) ∥ \leq T D$ or $C D$ , since it is bounded by $∥ W_{h} (θ) ∥ e_{h - 1} + D ∥ x_{h - 1} (θ_{0}) ∥$ for $h \geq 2$ , and by $D$ for $h = 1$ .

3.1F1F2step 1.1step 2.1algebraF3

For a unit parameter direction $v$ , let $ξ_{h} = D x_{h} [v]$ . At the first layer $∥ ξ_{1} ∥ \leq C ∥ v_{W_{1}} ∥ / \sqrt{m}$ . Subsequent layers obey $ξ_{h} = P_{h} ξ_{h - 1} + (s_{h} / \sqrt{m}) diag (σ^{'} (z_{h})) v_{W_{h}} x_{h - 1}$ . The product bounds in step 1.1, the feature bounds in step 2.1, and Cauchy–Schwarz over layer blocks give $\max_{h} ∥ ξ_{h} ∥ \leq T / \sqrt{m}$ or $C / \sqrt{m}$ . For the residual case use $\sum_{h \geq 2} s_{h} ∥ v_{W_{h}} ∥ \leq c_{r e s} (\sum_{h \geq 2} ∥ v_{W_{h}} ∥^{2})^{1 / 2} / \sqrt{H} \leq C$ , retaining the separate first-layer term. Thus $∥ D z_{h} [v] ∥ \leq T$ or $C$ , uniformly in $h$ . Since $D f_{i} [v] = v_{a}^{T} x_{H} + a^{T} ξ_{H}$ and $∥ a ∥ \leq C \sqrt{m}$ , each output gradient has norm at most $T$ or $C$ , proving $∥ J ∥ \leq T \sqrt{n}$ or $C \sqrt{n}$ . This explicitly retains the output and first-layer terms with no $1 / H$ bound.

3.2F2step 1.1step 2.1algebra

Put $d_{h} = b_{h} (θ) - b_{h} (θ_{0})$ . The backward recurrence is $b_{h - 1} = P_{h}^{T} b_{h}$ , with $d_{H} = a - a_{0}$ . Decompose its difference as $P_{h} (θ)^{T} d_{h} + (P_{h} (θ) - P_{h} (θ_{0}))^{T} b_{h} (θ_{0})$ . The latter is the sum of a weight-difference term bounded by $T s_{h} D$ (respectively $C s_{h} D$ ) and a gate-difference term bounded by $C s_{h} B_{b} M ∥ z_{h} (θ) - z_{h} (θ_{0}) ∥$ , because $∥ diag (σ^{'} (z_{h}) - σ^{'} (z_{h, 0})) b_{h, 0} ∥ \leq β B_{b} M ∥ z_{h} - z_{h, 0} ∥$ . Summing the backward recurrence with the product bounds gives $∥ d_{h} ∥ \leq T M D$ or $C M D$ . Hence $∥ b_{h} (θ) ∥_{\infty} \leq T M (1 + D)$ or $C M (1 + D)$ . The crude $ℓ_{2}$ bound $∥ b_{h} (θ) ∥_{2} \leq T \sqrt{m}$ or $C \sqrt{m}$ follows separately from step 1.1 and $∥ a ∥_{2} \leq C \sqrt{m}$ .

3.3F1F2step 2.1algebraF3F7

For the last-hidden-layer Gram, put $X_{i} = x_{i}^{(H - 1)}$ , $Z_{i} = W_{H} X_{i}$ and $γ = c_{σ}$ or $c_{r e s}^{2} / H^{2}$ . Direct differentiation gives $G_{H, i j} = γ ⟨ X_{i}, X_{j} ⟩ m^{- 1} \sum_{r} a_{r}^{2} σ^{'} (Z_{i, r}) σ^{'} (Z_{j, r})$ . Subtract its initialized version in three parts: feature-inner-product change, derivative-gate change with $a_{0}^{2}$ , and output-weight-square change. Step 2.1 bounds the first part by $T D / \sqrt{m}$ or $C D / \sqrt{m}$ before multiplying by $γ$ . For the second part, Cauchy–Schwarz gives $m^{- 1} \sum_{r} a_{0, r}^{2} ∣ Δ Z_{i, r} ∣ \leq m^{- 1} ∥ a_{0} ∥_{4}^{2} ∥ Δ Z_{i} ∥_{2} \leq C ∥ Δ Z_{i} ∥_{2} / \sqrt{m}$ ; multiply by $β L$ , and use step 2.1. For the third part, $m^{- 1} \sum_{r} ∣ a_{r}^{2} - a_{0, r}^{2} ∣ \leq m^{- 1} ∥ a - a_{0} ∥_{2} (∥ a ∥_{2} + ∥ a_{0} ∥_{2}) \leq C D / \sqrt{m}$ . Feature norms and $∣ σ^{'} ∣ \leq L$ bound all remaining factors. The entry error is consequently at most $T D / \sqrt{m}$ or $C D / (H^{2} \sqrt{m})$ . The operator norm is at most $n$ times this entry bound.

4.1F1F2step 3.1step 3.2algebra

For two unit parameter directions $v, w$ , twice differentiating the output gives the mixed output-weight terms $v_{a}^{T} D x_{H} [w] + w_{a}^{T} D x_{H} [v]$ , and the sum over layers of $\frac{s_{h}}{\sqrt{m}} b_{h}^{T} (diag (σ^{''} (z_{h})) (D z_{h} [v] ⊙ D z_{h} [w]) + diag (σ^{'} (z_{h})) (v_{W_{h}} D x_{h - 1} [w] + w_{W_{h}} D x_{h - 1} [v])) .$ This identity follows by differentiating every primitive twice and propagating each resulting second-order term through its downstream Jacobians; the linear skip has zero second derivative. The coordinate-product inequality $∥ p ⊙ q ∥_{1} \leq ∥ p ∥_{2} ∥ q ∥_{2}$ , steps 3.1–3.2, and $\sum_{h} s_{h} \leq C H$ or $C$ bound the first part by $T M (1 + D) / \sqrt{m}$ or $C M (1 + D) / \sqrt{m}$ . The terms involving $v_{W_{h}} D x_{h - 1} [w]$ use the $ℓ_{2}$ backward bound and $∥ D x_{h - 1} [w] ∥ \leq T / \sqrt{m}$ or $C / \sqrt{m}$ ; summing with Cauchy–Schwarz over matrix blocks gives the same bound. The output-weight mixed terms are at most $T / \sqrt{m}$ or $C / \sqrt{m}$ . This proves the output-Hessian bound, with polynomial factors in $H$ absorbed into $A^{H}$ only for the fully connected case.

5.1step 3.1step 4.1algebraF3F4F5∎

The identity $\nabla^{2} L = J^{T} J + \sum_{i} r_{i} \nabla^{2} f_{i}$ gives $∥ \nabla^{2} L ∥ \leq ∥ J ∥^{2} + \sqrt{n} ∥ r ∥ \max_{i} ∥ \nabla^{2} f_{i} ∥$ . Integrating the Jacobian along the straight segment to initialization gives $∥ r ∥ \leq ∥ r_{0} ∥ + T \sqrt{n} D$ or $∥ r_{0} ∥ + C \sqrt{n} D$ . Substitution of steps 3.1 and 4.1 proves the claimed loss-Hessian bound, after enlarging $A, C$ to absorb squares of fixed exponential envelopes. For each coordinate the integral Taylor formula is $f_{i} (θ + h) - f_{i} (θ) - D f_{i} (θ) h = \int_{0}^{1} (1 - t) D^{2} f_{i} (θ + t h) [h, h] d t$ . Step 4.1 bounds its absolute value by $T M (1 + D) ∥ h ∥^{2} / (2 \sqrt{m})$ or the corresponding residual constant. Summing coordinate squares gives the stated vector Taylor bound.

LemmaStatement: AI-adaptedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

Simultaneous initialization estimates for the Du architectures

Statement

Use either of the two architectures, its own terminal population kernel $K$ , and independent Gaussian initialization. Assume AC, DC and countable choice and the activation and bounded-label hypotheses of the convergence theorems. Fix $0 < δ < 1$ . Write $λ = λ_{\min} (K) > 0$ , $q = 1 + \log (16 / δ)$ and $M = \sqrt{1 + \log (16 m n H / δ)}$ . There are constants $A \geq 2$ and $C \geq 1$ , depending only on the fixed activation bounds, its normalizer, the label bound, and, in the residual case, $c_{r e s}$ , with the following property. For the fully connected case put $T = A^{H}$ ; if

$m \geq C \max {T n^{4} / λ^{4}, T n / δ, T n^{2} \log (16 H n / δ) / λ^{2}},$

then with probability at least $1 - δ$ , simultaneously:

$\max_{i, h} ∥ x_{i}^{(h)} (0) ∥ \leq T, \max_{h \geq 2} ∥ W^{(h)} (0) ∥_{o p} \leq C \sqrt{m}, ∥ a (0) ∥_{2} \leq C \sqrt{m}, ∥ a (0) ∥_{4} \leq C m^{1 / 4},$

$\max_{i, h} ∥ b_{i, h} (0) ∥_{\infty} \leq T M, λ_{\min} (J_{H} (0) J_{H} (0)^{T}) \geq 3 λ / 4, ∥ u (0) - y ∥^{2} \leq T n q .$

Here $J_{H}$ is the Jacobian block of the last hidden-layer matrix, and $b_{i, h}$ is the derivative of the scalar output with respect to the hidden feature vector $x_{i}^{(h)}$ , so $b_{i, H} = a$ . In the residual case $H \geq 2$ , the same conclusions hold with $T$ replaced everywhere in the conclusions by $C$ , provided

$m \geq C \max {n^{4} H^{6} / λ^{4}, n^{2} / (λ^{2} H^{2}), n / δ, n^{2} \log (16 H n / δ) / λ^{2}} .$

For residual depth one use the fully connected case. Constants may be enlarged, and $A$ may be increased, simultaneously in these conclusions.

Statement references

Du et al., initialization arguments B.1–B.2, C.1–C.2 and E.1–E.2

Facts & Assumptions

Given: The architecture, its population recursion, the data, Gaussian initialization, width and confidence parameters in the Statement.

[F1]

The architecture-specific population recurrences, including residual means, and their positive semidefiniteness are supplied locally. Fully connected and residual networks with the Du Gram kernel The recursively defined population Gram matrices are finite, symmetric, and positive semidefinite

[F2]

Lipschitz functions of a standard Gaussian vector obey the stated one-sided concentration inequality; applying it to both signs gives a two-sided bound. Lipschitz concentration for standard Gaussian measure

[F3]

Gaussian vectors have the stated covariance and even moments $(2 p - 1)!!$ . Multivariate normal law, including singular covariance Gaussian even moments for Brownian increments

[F4]

Conditional on hidden features, the Gaussian output norm is at most the square root of their total squared norm plus their operator norm times $\sqrt{2 \log (1 / ε)}$ , with failure probability at most $ε$ . Gaussian output initialization concentrates conditionally on the hidden features

[F5]

If $X, Y$ have finite second moments, then $E ∣ X Y ∣ \leq (E X^{2})^{1 / 2} (E Y^{2})^{1 / 2}$ ; expanding a square and applying this bound gives the $L^{2}$ triangle estimate used for residual feature variances. Cauchy-Schwarz for random variables

[F6]

Euclidean Cauchy–Schwarz bounds inner products and the Euclidean norm satisfies the triangle inequality. Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation

[F7]

A nondegenerate bivariate normal vector has its Gaussian Lebesgue density. A positive-definite multivariate normal law has its Gaussian density

[F8]

Differentiation may pass through an integral when parameter derivatives have a common integrable majorant. Differentiation under the integral sign

[F9]

Integration by parts is valid on a compact interval when the derivatives are integrable. If $u, v$ are differentiable on $[a, b]$ with $u^{'}, v^{'}$ integrable, then $\int_{a}^{b} u v^{'} = u (b) v (b) - u (a) v (a) - \int_{a}^{b} u^{'} v$

[F10]

Dominated convergence passes limits through integrals under a common integrable majorant. Dominated convergence

[F11]

For nonnegative $Y$ and $a > 0$ , $P (Y \geq a) \leq E Y / a$ . Markov's inequality for random variables

[F12]

For square-integrable $Y$ and $a > 0$ , $P (∣ Y - E Y ∣ \geq a) \leq Var (Y) / a^{2}$ . Chebyshev's inequality for random variables

[F13]

A real function continuous on a compact interval and differentiable in its interior has some derivative equal to its average rate of change; this turns the bounded $ρ$ -derivatives in step 2.1 into Lipschitz bounds. The mean value theorem, as the case $g (x) = x$ of Cauchy's: for $f$ continuous on $[a, b]$ with $a < b$ and differentiable on $(a, b)$ there is $c \in (a, b)$ with $f (b) - f (a) = f^{'} (c) (b - a)$

[F14]

Analyticity gives $σ^{''}$ , and the $β$ -Lipschitz property of $σ^{'}$ gives $∣ σ^{''} ∣ \leq β$ wherever needed in step 2.1. [given]

[F16]

A $1 / 4$ -net of the Euclidean unit sphere in $R^{m}$ exists with at most $9^{m}$ points. Finite epsilon nets of the Euclidean sphere

[F17]

Matrix operator norms are induced by the Euclidean vector norm. The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||

[F18]

For $p = 4$ , $∥ a ∥_{4} = (\sum_{r} ∣ a_{r} ∣^{4})^{1 / 4}$ . The $p$ -norms $∥ x ∥_{p}$ for rational $p \geq 1$ , and $∥ x ∥_{\infty}$

[F19]

The Frobenius norm is the Euclidean norm of the matrix entry list, $∥ Φ ∥_{F}^{2} = \sum_{i, r} Φ_{i r}^{2}$ ; for any unit $v$ , Euclidean Cauchy–Schwarz gives $∥ Φ v ∥_{2}^{2} = \sum_{i} (\sum_{r} Φ_{i r} v_{r})^{2} \leq \sum_{i, r} Φ_{i r}^{2}$ , hence $∥ Φ ∥_{o p} \leq ∥ Φ ∥_{F}$ . The Frobenius norm $∥ A ∥_{F} = (\sum_{i, j} ∣ a_{i j} ∣^{2})^{1 / 2}$ on real or complex matrices Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation

[F15]

In the residual coupling, the feature vector and fresh Gaussian vector are independent, so $Cov (V + α σ (G)) = Cov (V) + α^{2} Cov (σ (G)) ⪰ Cov (V)$ . This is the construction in The recursively defined population Gram matrices are finite, symmetric, and positive semidefinite and yields the monotone variance lower bound in step 4.1.

[F20]

For finitely many independent real random variables, expectations of products of nonnegative Borel functions factor, including when the expectations are extended nonnegative values. Expectations factor over finite products of independent random variables

[F21]

The probability of a finite union of events is at most the sum of their probabilities. The finite union bound

Proof

1.1F2F3F5F11F20givenalgebra

We give the scalar estimates used below explicitly. If $U, V$ are centered Gaussian variables with variances at most a fixed $Q$ , then $∣ σ (z) ∣ \leq B + L ∣ z ∣$ and [F3] imply $∥ σ (U) ∥_{2 p} \leq C \sqrt{p}$ ; [F5] then gives $∥ σ (U) σ (V) ∥_{p} \leq C p$ for integers $p \geq 2$ . The same last bound holds for $a^{2} σ^{'} (U) σ^{'} (V)$ when $a$ is an independent standard normal, because $∣ σ^{'} ∣ \leq L$ . After centering, each such variable $X$ satisfies $E ∣ X ∣^{p} \leq p! C^{p}$ , enlarging $C$ using $p^{p} \leq e^{p} p!$ . Expanding its exponential series, for $∣ t ∣ \leq 1 / (2 C)$ one has $E e^{t X} \leq 1 + \sum_{p \geq 2} (C ∣ t ∣)^{p} \leq e^{2 C^{2} t^{2}}$ . For $m$ independent copies, [F20] factors the exponential moment of their sum. Applying [F11] to $\exp (t \sum_{r} X_{r})$ with $t = s / (4 C^{2})$ , and then to $\exp (- t \sum_{r} X_{r})$ , to obtain $P (∣ m^{- 1} \sum_{r} X_{r} ∣ > s) \leq 2 e^{- c m s^{2}}$ for $0 < s \leq c$ . All constants are uniform over the covariances with these variance bounds.

2.1F3F5F7F8F9F10step 1.1algebraF13

The Gaussian expectation maps needed in the population recurrences are Lipschitz functions of the three entries of their bivariate covariance on any region $v \leq Q_{i i}, Q_{j j} \leq Q$ , where $v > 0$ is fixed. This applies to $E [g (U) g (V)]$ for $g = σ$ and $g = σ^{'}$ , and to the residual marginal map $s \mapsto E σ (\sqrt{s} Z)$ . At fixed $ρ$ , changing $s, t$ changes these expectations by at most $C (∣ Δ s ∣ + ∣ Δ t ∣)$ : use the Lipschitz constants $L, β$ , $s, t \geq v$ , and [F5] to bound the resulting products. For fixed $s, t$ and $∣ ρ ∣ < 1$ , the covariance matrix is positive definite, so [F7] supplies the density $ϕ_{s, t, ρ}$ . On any compact interval $∣ ρ ∣ \leq r < 1$ , its eigenvalues lie between $v (1 - r)$ and $Q (1 + r)$ . Direct differentiation of the Gaussian density gives $\partial_{ρ} ϕ_{s, t, ρ} = \sqrt{s t} \partial_{u} \partial_{v} ϕ_{s, t, ρ}$ . Uniform eigenvalue bounds imply that $∣ g (u) g (v) \partial_{ρ} ϕ_{s, t, ρ} (u, v) ∣$ is bounded by an integrable polynomial times $e^{- c (u^{2} + v^{2})}$ , uniformly on this interval; $g$ has at most linear growth and $g^{'}$ is bounded. Thus [F8] justifies differentiating the expectation under the integral. On finite rectangles apply [F9] successively in $u$ and $v$ ; the boundary terms tend to zero as the rectangles expand because of Gaussian decay and the growth bound. The same integrable majorant and [F10] pass the rectangle limits, giving $\partial_{ρ} E [g (U) g (V)] = \sqrt{s t} E [g^{'} (U) g^{'} (V)]$ . Its absolute value is at most $Q L^{2}$ for $g = σ$ and $Q β^{2}$ for $g = σ^{'}$ , since $∣ σ^{'} ∣ \leq L$ and $∣ σ^{''} ∣ \leq β$ . At $ρ = \pm 1$ , the representation $U = \sqrt{s} Z$ , $V = \sqrt{t} (ρ Z + \sqrt{1 - ρ^{2}} Z^{'})$ is dominated after multiplication by either pair of activations by $C (1 + ∣ Z ∣ + ∣ Z^{'} ∣)^{2}$ , which is integrable; [F10] gives continuity at both endpoints. Finally $ρ = Q_{i j} / \sqrt{s t}$ is Lipschitz in the covariance entries when $s, t \geq v$ .

3.1F1F3F21step 1.1step 2.1algebra

Write ${\hat{S}}_{i j}^{(h)} = ⟨ x_{i}^{(h)} (0), x_{j}^{(h)} (0) ⟩$ and, for residual layers, ${\hat{b}}_{i}^{(h)} = m^{- 1 / 2} \sum_{r} x_{i, r}^{(h)} (0)$ . Conditional on previous layers, the preactivation pairs in distinct rows are independent centered Gaussians with covariance given by ${\hat{S}}^{(h - 1)}$ . In the fully connected case, step 1.1 bounds each difference of ${\hat{S}}_{i j}^{(h)}$ from its conditional mean by $C t_{0}$ , except with probability $δ / (32 H n^{2})$ , where $t_{0} = \sqrt{\log (64 H n^{2} / δ) / m}$ . Its conditional mean is exactly the fully connected population expectation evaluated at ${\hat{S}}^{(h - 1)}$ . Since the population diagonal is one, step 2.1 gives, while the error is at most a fixed small constant, $e_{h} \leq C e_{h - 1} + C t_{0}$ , where $e_{h} = \max_{i j} ∣ {\hat{S}}_{i j}^{(h)} - K_{i j}^{(h)} ∣$ and $e_{0} = 0$ . If $B > 1$ is a fixed base for this recurrence, then $e_{h} \leq B^{H} t_{0}$ after enlarging its prefactor. Choose the statement constant $A \geq B^{2}$ and enlarge the width constant; its term $T n^{2} \log (16 H n / δ) / λ^{2}$ , with $T = A^{H}$ , then makes this error smaller than both the fixed stopping threshold and $c λ / n$ . Conditional bounds and the finite union bound [F21] over $h, i, j$ therefore justify the estimates through layers $h < H$ ; the last hidden-feature norm is bounded by one further conditional application of the activation moment estimate, without identifying its covariance with the terminal derivative kernel. A first layer crossing the stopping threshold would contradict this recurrence. In particular all feature norms are bounded by a constant, hence by $T$ .

4.1F1F2F3F21step 1.1step 2.1step 3.1algebraF15

In the residual case the population feature variances lie in a fixed compact interval $[v, Q]$ independent of $H$ . Indeed the vector construction in [F1] gives $S^{(h)} - b^{(h)} (b^{(h)})^{T} ⪰ S^{(1)} - b^{(1)} (b^{(1)})^{T}$ , whose diagonal is $v = c_{σ} Var (σ (Z)) > 0$ . Positivity of $v$ follows from nonconstancy, continuity and the positive Gaussian density. Also $\sqrt{S_{i i}^{(h)}} \leq \sqrt{S_{i i}^{(h - 1)}} + α (B + L \sqrt{S_{i i}^{(h - 1)}})$ with $α = c_{r e s} / H$ , so iteration gives a fixed upper bound. The empirical conditional mean satisfies exactly the same residual second-moment/mean recursion with $S, b$ replaced by $\hat{S}, \hat{b}$ . The nonlinear quadratic part has conditional fluctuation at most $C α^{2} t_{0}$ by step 1.1. Each cross part is $α m^{- 1 / 2} \sum_{r} x_{i, r}^{(h - 1)} σ (U_{j, r})$ ; its centered value has absolute size at most $C α t_{0}$ by [F2], since its Lipschitz constant in the independent row Gaussians is at most $C α ∥ x_{i}^{(h - 1)} ∥ / \sqrt{m}$ . The empirical mean has fluctuation at most $C α t_{0}$ by [F2]. Step 2.1 now yields $e_{h} \leq (1 + C / H) e_{h - 1} + C t_{0} / H$ , taking the maximum of the covariance and mean errors. The first layer has $e_{1} \leq C t_{0}$ by step 1.1 and [F2]. Hence $e_{h} \leq C t_{0}$ uniformly in $H$ . The width assumption and the same stopping argument, now in $[v / 2, 2 Q]$ , justify the conditional estimates and give the feature bound through $h < H$ ; the finite union bound [F21] combines their layerwise failure probabilities. One further conditional step gives $∥ x_{i}^{(H)} ∥ \leq C$ , using the same upper-norm recurrence, so $\max_{i, h} ∥ x_{i}^{(h)} ∥ \leq C$ .

5.1F1F3F6F21step 1.1step 2.1step 3.1step 4.1algebra

For either architecture, conditional on layers before the last, the last-hidden-layer Jacobian Gram entries are $s_{H}^{2} {\hat{S}}_{i j}^{(H - 1)} m^{- 1} \sum_{r} a_{r}^{2} σ^{'} (z_{i, r}) σ^{'} (z_{j, r})$ , where $s_{H}^{2} = c_{σ}$ for the fully connected case and $s_{H}^{2} = c_{r e s}^{2} / H^{2}$ for residual $H \geq 2$ . This follows by differentiating the last layer. The summands are independent across $r$ . Steps 1.1–2.1, the feature bounds and errors just proved give entry error at most $B_{2}^{H} t_{0}$ in the fully connected case, for a fixed base $B_{2}$ depending only on the fixed activation bounds, and at most $C t_{0} / H^{2}$ in the residual case. Choose the statement constant $A$ also with $A \geq B_{2}^{2}$ ; the displayed logarithmic width term and a sufficiently large fixed multiplier then make both errors at most $λ / (4 n)$ . A finite union bound [F21] covers the terminal-kernel entry events. If an $n \times n$ matrix $E$ has entries bounded by $ε$ , then for any $z$ , $∥ E z ∥_{2} \leq \sqrt{n} ε \sum_{j} ∣ z_{j} ∣ \leq n ε ∥ z ∥_{2}$ by [F6], hence $∥ E ∥_{o p} \leq n ε$ . Thus $∥ J_{H} J_{H}^{T} - K ∥_{o p} \leq λ / 4$ . Both matrices are symmetric, and for every $z$ , $z^{T} J_{H} J_{H}^{T} z \geq z^{T} K z - ∣ z^{T} E z ∣ \geq (λ - ∥ E ∥_{o p}) ∥ z ∥_{2}^{2} \geq 3 λ ∥ z ∥_{2}^{2} / 4$ , where $E = J_{H} J_{H}^{T} - K$ . The Rayleigh-quotient characterization of the smallest eigenvalue now gives $λ_{\min} (J_{H} J_{H}^{T}) \geq 3 λ / 4$ .

5.2F2F3F6F12F16F21step 3.1step 4.1constructalgebraF17F18

By [F16], choose a $1 / 4$ -net $N$ of the unit sphere with at most $9^{m}$ points. The Euclidean norm duality $∥ z ∥_{2} = \sup_{∥ x ∥_{2} = 1} ∣ x^{T} z ∣$ follows from [F6], so $∥ W ∥_{o p} = \sup_{∥ x ∥ = ∥ y ∥ = 1} ∣ x^{T} W y ∣$ . For unit $x, y$ , choose $v, w \in N$ within $1 / 4$ of them. Then [F6] gives $∣ x^{T} W y - v^{T} W w ∣ \leq ∥ x - v ∥_{2} ∥ W y ∥_{2} + ∥ v ∥_{2} ∥ W (y - w) ∥_{2} \leq \frac{1}{2} ∥ W ∥_{o p}$ . Taking suprema yields $∥ W ∥_{o p} \leq 2 \max_{v, w \in N} ∣ v^{T} W w ∣$ . Each $v^{T} W w$ is standard normal, whose tail is at most $2 e^{- t^{2} / 2}$ by [F2]. The finite union bound [F21] gives $∥ W^{(h)} ∥ \leq C \sqrt{m}$ for all $h \geq 2$ with failure at most $δ / 16$ when $m \geq C \log (16 H / δ)$ , which follows from either displayed width because $λ \leq c_{σ} L^{2}$ in the fully connected case and $λ \leq C / H^{2}$ in the residual case. The latter bound follows by bounding the diagonal of its terminal kernel with step 4.1. Gaussian second and eighth moments and [F12] give $∥ a ∥_{2} \leq C \sqrt{m}$ and $∥ a ∥_{4} \leq C m^{1 / 4}$ with failure at most $δ / 16$ when $m \geq C / δ$ , also implied by the widths. These arguments never bound $∥ W^{(1)} ∥$ on the whole input space, so no input-dimension condition is used.

6.1F2F3F4F21step 3.1step 4.1step 5.1step 5.2F19

Conditional on hidden weights, $b_{i, h} (0) = P_{i, h}^{T} a$ , where $P_{i, h}$ is the product of downstream feature Jacobians. Their operator norms have fixed envelopes $B^{H}$ in the fully connected case and $B$ in the residual case, using $\prod_{l > h} (1 + C / H) \leq e^{C}$ for residual layers. Increase the conclusion constants so these envelopes are at most $T / 2$ and $C / 2$ , respectively. Each coordinate is centered Gaussian of variance at most $(T / 2)^{2}$ or $(C / 2)^{2}$ . Since $M^{2} = 1 + \log (16 m n H / δ)$ , its two-sided tail is at most $2 e^{- 2 M^{2}} \leq δ / (8 m n H)$ ; the finite union bound [F21] over at most $m n H$ coordinates gives the asserted coordinate maxima with failure at most $δ / 8$ . Finally [F4] and $∥ Φ ∥_{o p} \leq ∥ Φ ∥_{F} \leq \sqrt{n} \max_{i} ∥ x_{i}^{(H)} ∥$ give $∥ u (0) ∥ \leq C \sqrt{T n q}$ or $C \sqrt{n q}$ with failure at most $δ / 16$ .

7.1F2F21step 3.1step 4.1step 5.1step 5.2step 6.1algebra∎

By the finite union bound [F21], allocate at most $δ / (32 H n^{2})$ to each fully connected feature-covariance or terminal-feature-norm event in step 3.1; there are at most $2 H n^{2}$ such events. Allocate at most $δ / (128 H n^{2})$ to each residual covariance, cross-term, mean, or terminal-feature-norm event in step 4.1; there are at most $4 H n^{2}$ such events. Allocate at most $δ / (64 n^{2})$ to each terminal-kernel entry event. The weight-matrix and readout norm events in step 5.2 each use $δ / 16$ ; backward coordinates use $δ / 8$ and the output norm uses $δ / 16$ in step 6.1. Even summing both architecture allocations, these budgets total at most $27 δ / 64 < δ$ . The thresholds are constant multiples of $t_{0}$ or $M$ ; increasing the fixed constants in the width and conclusions makes each displayed concentration bound meet its allocation without changing their forms. Adding the deterministic bounded-label contribution proves the simultaneous event.

TheoremStatement: Literature-sourcedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

Wide fully connected networks converge geometrically to zero empirical training loss

Statement

Assume AC, DC and countable choice. Fix positive integers $d, n, H, m$ , training data $x_{1}, \dots, x_{n} \in R^{d}$ and labels $y_{1}, \dots, y_{n} \in R$ with $∥ x_{i} ∥_{2} = 1$ and $∣ y_{i} ∣ \leq C_{y}$ for a fixed finite constant $C_{y}$ . Let the activation satisfy the Lipschitz and smoothness conditions $∣ σ (0) ∣ \leq C_{σ}$ , $∣ σ (z) - σ (z^{'}) ∣ \leq L ∣ z - z^{'} ∣$ , and $∣ σ^{'} (z) - σ^{'} (z^{'}) ∣ \leq β ∣ z - z^{'} ∣$ for finite constants, and also be analytic and nonpolynomial. Use the fully connected architecture and population matrix $K_{f c}^{(H)}$ defined on this page, initialized with independent standard normal entries in all weight matrices and the output vector, and trained in all layers by full-batch gradient descent on $L (θ) = \frac{1}{2} \sum_{i = 1}^{n} (f (x_{i}, θ) - y_{i})^{2}$ . Write $K^{(H)} = K_{f c}^{(H)}$ and put $λ_{0} = λ_{\min} (K^{(H)})$ and assume $λ_{0} > 0$ . For $0 < δ < 1$ , if the width and fixed step size satisfy

$m = Ω ⁣ (2^{O (H)} \max {\frac{n^{4}}{λ_{0}^{4}}, \frac{n}{δ}, \frac{n^{2} \log (H n / δ)}{λ_{0}^{2}}}), 0 < η = O ⁣ (\frac{λ_{0}}{n^{2} 2^{O (H)}}),$

then with probability at least $1 - δ$ over initialization, every gradient-descent iterate $k \geq 1$ satisfies

$L (θ^{(k)}) \leq {(1 - \frac{η λ_{0}}{2})}^{k} L (θ^{(0)}) .$

The constants hidden in $O$ and $Ω$ may depend on the fixed activation and label bounds but not on $n, H, m, δ$ ; the step-size constant is small enough that $0 < η λ_{0} / 2 < 1$ . In particular, $L (θ^{(k)}) \to 0$ geometrically as $k \to \infty$ .

Statement references

Du et al., Theorem 5.1 and §3.3

Du et al., Appendix B, Lemmas B.1–B.7 and proof of Theorem 5.1

Facts & Assumptions

Given: The data, architecture, activation, Gaussian initialization, positive terminal population eigenvalue $λ_{0}$ , width, confidence and step-size hypotheses of the Statement.

[F1]

The architecture-specific population kernel, including residual means and scaling, is defined locally and is positive semidefinite. Fully connected and residual networks with the Du Gram kernel The recursively defined population Gram matrices are finite, symmetric, and positive semidefinite

[F2]

The simultaneous Gaussian initialization event gives feature, parameter, backward-coordinate, last-layer Gram, and initial-residual bounds at the stated width. Simultaneous initialization estimates for the Du architectures

[F3]

On parameter balls, the last-layer Gram perturbation and output/loss Hessian have explicit width-dependent bounds. Parameter-ball control of the last-layer Gram and loss Hessian

[F4]

Local Gram positivity and loss-Hessian control confine all GD iterates by a first-exit argument and give geometric loss contraction. Local Gram positivity and loss smoothness give confined gradient descent

Proof

1.1F1F2givenalgebra

Put $λ = λ_{0}$ and $q = 1 + \log (16 / δ)$ . Fix an exponential envelope $E = A_{0}^{H}$ for all initialization constants in [F2] and another $F = A_{1}^{H}$ for [F3] with those initialization bounds. These bases depend only on the permitted fixed bounds. The source-width form permits $m \geq W \max {n^{4} / λ^{4}, n / δ, n^{2} \log (16 H n / δ) / λ^{2}}$ , where $W = A_{2}^{H}$ is chosen sufficiently large in terms of the fixed bases of $E, F$ ; in particular take $W \geq C E F^{2}$ . All these choices are fixed before selecting the radius. On the event from [F2], of probability at least $1 - δ$ , $r_{0} = u (0) - y$ satisfies $∥ r_{0} ∥^{2} \leq E n q$ , the initialized last-layer Gram is at least $3 λ I / 4$ , and all other hypotheses of [F3] hold. Also $λ \leq c_{σ} L^{2}$ by the diagonal of [F1].

2.1F1F3step 1.1algebra

The displayed width also implies $m \geq C E F^{2} n^{3} q / λ^{3}$ , after fixing $W$ sufficiently large. For the logarithmic term this follows without an extra logarithmic width factor: writing $A_{*} = n^{4} / λ^{4}$ and $B_{*} = n / δ$ , one has $n^{3} λ^{- 3} \log (1 / δ) = n^{- 1 / 4} A_{*}^{3 / 4} B_{*}^{1 / 4} δ^{1 / 4} \log (1 / δ) \leq (4 / e) \max (A_{*}, B_{*})$ , since $t e^{- t / 4} \leq 4 / e$ for $t \geq 0$ . The constant part of $q$ is absorbed by $A_{*}$ using $λ \leq c_{σ} L^{2}$ and $n \geq 1$ . Choose the fixed radius $D = 4 \sqrt{E n q / λ}$ . These inequalities give $D / \sqrt{m} \leq c / F$ and $F n D / \sqrt{m} \leq λ / 4$ . Hence [F3] supplies $J_{H} (θ) J_{H} (θ)^{T} ⪰ λ I / 2$ on the entire ball of radius $D$ .

3.1F3step 1.1step 2.1algebra

The same width implies $m \geq C \max (n, H, 1 / δ)$ , so $M = \sqrt{1 + \log (16 m n H / δ)} \leq C \sqrt{\log (e m)}$ and $q \leq C \log (e m)$ . The loss-Hessian bound in [F3], $D = 4 \sqrt{E n q / λ}$ , and $λ \leq c_{σ} L^{2}$ yield $∥ \nabla^{2} L ∥ \leq T^{'} n^{2} λ^{- 1} (1 + q M / \sqrt{m})$ , where $T^{'} = A^{' H}$ after enlarging its fixed base. Indeed expand $(\sqrt{E n q} + F \sqrt{n} D) (1 + D)$ in that bound; because $n, q \geq 1$ and $λ$ is bounded above, every term is at most an allowed exponential constant times $n^{3 / 2} q / λ$ , before the exterior factor $\sqrt{n} M / \sqrt{m}$ . The function $\log (e m)^{3 / 2} / \sqrt{m}$ is bounded for $m \geq 1$ , so the Hessian is bounded by $S = T^{''} n^{2} / λ$ on the ball, with $T^{''} = A^{'' H}$ . The allowed sufficiently small step-size constant ensures $η \leq 1 / S$ .

4.1F3F4step 1.1step 2.1step 3.1algebra∎

The radius satisfies $D > 2 \sqrt{2} ∥ r_{0} ∥ / \sqrt{λ}$ . Apply [F4] with the last-hidden-layer Jacobian block and the ball and smoothness bounds from steps 2.1 and 3.1. Every iterate stays in that ball, and $L (θ^{(k)}) \leq (1 - η λ / 2)^{k} L (θ^{(0)})$ for all $k$ . Choosing the step-size constant also ensures $0 < η λ / 2 < 1$ , so geometric convergence to zero follows. The initialization event has probability at least $1 - δ$ , proving the claim. The same application bounds the total parameter path by $2 \sqrt{2} ∥ r_{0} ∥ / \sqrt{λ}$ ; [F3] therefore supplies last-layer Gram stability and the displayed output Taylor-remainder bound on every accepted update segment, for all iterates simultaneously.

TheoremStatement: Literature-sourcedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

Wide residual networks converge geometrically to zero empirical loss with polynomial depth dependence

Statement

Assume AC, DC and countable choice. Fix positive integers $d, n, H, m$ , training data $x_{1}, \dots, x_{n} \in R^{d}$ and labels $y_{1}, \dots, y_{n} \in R$ with $∥ x_{i} ∥_{2} = 1$ and $∣ y_{i} ∣ \leq C_{y}$ for a fixed finite constant $C_{y}$ . Let the activation satisfy the Lipschitz and smoothness conditions $∣ σ (0) ∣ \leq C_{σ}$ , $∣ σ (z) - σ (z^{'}) ∣ \leq L ∣ z - z^{'} ∣$ , and $∣ σ^{'} (z) - σ^{'} (z^{'}) ∣ \leq β ∣ z - z^{'} ∣$ for finite constants, and also be analytic and nonpolynomial. Use the residual architecture with fixed $0 < c_{r e s} < 1$ and the population matrix $K_{r e s}^{(H)}$ defined on this page, initialized with independent standard normal entries in all weight matrices and the output vector, and trained in all layers by full-batch gradient descent on $L (θ) = \frac{1}{2} \sum_{i = 1}^{n} (f_{r e s} (x_{i}, θ) - y_{i})^{2}$ . Write $K^{(H)} = K_{r e s}^{(H)}$ and put $λ_{0} = λ_{\min} (K^{(H)})$ and assume $λ_{0} > 0$ . For $0 < δ < 1$ , if

$m = Ω ⁣ (\max {\frac{n^{4} H^{6}}{λ_{0}^{4}}, \frac{n^{2}}{λ_{0}^{2} H^{2}}, \frac{n}{δ}, \frac{n^{2} \log (H n / δ)}{λ_{0}^{2}}}), 0 < η = O ⁣ (\frac{λ_{0} H^{2}}{n^{2}}),$

then with probability at least $1 - δ$ over initialization, every gradient-descent iterate $k \geq 1$ satisfies

$L (θ^{(k)}) \leq {(1 - \frac{η λ_{0}}{2})}^{k} L (θ^{(0)}) .$

The constants hidden in $O$ and $Ω$ may depend on the fixed activation, label, and residual-scaling bounds but not on $n, H, m, δ$ ; the step-size constant is small enough that $0 < η λ_{0} / 2 < 1$ . In particular, $L (θ^{(k)}) \to 0$ geometrically as $k \to \infty$ .

Statement references

Du et al., Theorem 6.1 and §3.3

Du et al., Appendix C, Lemmas C.1–C.7 and proof of Theorem 6.1

Facts & Assumptions

Given: The data, architecture, activation, Gaussian initialization, positive terminal population eigenvalue $λ_{0}$ , width, confidence and step-size hypotheses of the Statement.

[F1]

[F2]

[F3]

On parameter balls, the last-layer Gram perturbation and output/loss Hessian have explicit width-dependent bounds. Parameter-ball control of the last-layer Gram and loss Hessian

[F4]

[F5]

For square-integrable real random variables, $∣ E X ∣ \leq (E X^{2})^{1 / 2}$ . Cauchy-Schwarz for random variables

Proof

1.1F1F2F3F5givenalgebra

First take $H \geq 2$ and put $λ = λ_{0}$ , $q = 1 + \log (16 / δ)$ . At the stated width, [F2] supplies with probability at least $1 - δ$ a simultaneous event with all constants independent of $H$ , on which $∥ r_{0} ∥^{2} \leq C n q$ and $J_{H} (0) J_{H} (0)^{T} ⪰ 3 λ I / 4$ . By [F1], $S_{i i}^{(1)} = 1$ and $S_{i i}^{(h)} - (b_{i}^{(h)})^{2} \geq 0$ . For $2 \leq h < H$ , put $q_{h} = \sqrt{S_{i i}^{(h)}}$ and $Y_{h} = σ (G_{i}^{(h - 1)})$ . The residual recursion gives $q_{h}^{2} = S_{i i}^{(h - 1)} + 2 α b_{i}^{(h - 1)} E Y_{h} + α^{2} E Y_{h}^{2}$ . By [F1] and [F5], $∣ b_{i}^{(h - 1)} ∣ \leq q_{h - 1}$ and $∣ E Y_{h} ∣ \leq (E Y_{h}^{2})^{1 / 2}$ ; Lipschitz growth and [F5] also give $(E Y_{h}^{2})^{1 / 2} \leq C_{σ} + L q_{h - 1}$ . Hence $q_{h} \leq (1 + α L) q_{h - 1} + α C_{σ}$ . Starting from $q_{1} = 1$ and iterating with $α = c_{r e s} / H$ gives $q_{h} \leq e^{L c_{r e s}} (1 + C_{σ} c_{r e s})$ for every $h < H$ , uniformly in $H$ . The terminal diagonal formula and $∣ σ^{'} ∣ \leq L$ now give $K_{i i}^{(H)} \leq C / H^{2}$ ; positive semidefiniteness in [F1] implies $λ \leq K_{i i}^{(H)} \leq C / H^{2}$ . The residual neighborhood bounds [F3] retain separate first-layer and readout gradients without an erroneous $1 / H$ factor.

2.1F1F3step 1.1algebra

Choose $D = 4 \sqrt{C n q / λ}$ , with $C$ fixed sufficiently large for the initial-residual bound. The width implies $m \geq C n^{3} q / (λ^{3} H^{4})$ and $m \geq C D^{2}$ . To see the logarithmic absorption, use $A_{*} = n^{4} / λ^{4}$ , $B_{*} = n / δ$ and $n^{3} λ^{- 3} \log (1 / δ) \leq (4 / e) \max (A_{*}, B_{*})$ , which follows from $δ^{1 / 4} \log (1 / δ) \leq 4 / e$ exactly as in the fully connected argument. Dividing by $H^{4}$ only decreases the requirement, while the approved width contains $H^{6} A_{*}$ and $B_{*}$ . The constant part is absorbed using $λ H^{2} \leq C$ and $n, H \geq 1$ . Consequently $D / \sqrt{m} \leq c$ and $C n D / (H^{2} \sqrt{m}) \leq λ / 4$ , so the last-layer Gram is at least $λ I / 2$ throughout this ball.

3.1F3step 1.1step 2.1algebra

All constants in the residual Hessian estimate are independent of $H$ . Substitution of $D$ and the initial-residual bound in [F3] yields $∥ \nabla^{2} L ∥ \leq C n + C n^{2} q M / (λ \sqrt{m})$ , because $λ \leq C$ and $n, q \geq 1$ . The approved width and $λ \leq C / H^{2}$ imply $m \geq C \max (n, H^{6}, 1 / δ)$ . Thus $M \leq C \sqrt{\log (e m)}$ , $q \leq C \log (e m)$ and $q M / \sqrt{m} \leq C / H^{2}$ : explicitly, $\log (e m)^{3 / 2} \leq C m^{1 / 6}$ for all $m \geq 1$ , so the ratio is at most $C m^{- 1 / 3} \leq C / H^{2}$ . Also $n \leq C n^{2} / (λ H^{2})$ . Therefore $∥ \nabla^{2} L ∥ \leq S = C n^{2} / (λ H^{2})$ on the ball. The permitted sufficiently small fixed step-size constant makes $η \leq 1 / S$ .

4.1F1F2F3F4step 1.1step 2.1step 3.1algebra∎

Since $D > 2 \sqrt{2} ∥ r_{0} ∥ / \sqrt{λ}$ , [F4] confines every iterate to the ball and gives $L (θ^{(k)}) \leq (1 - η λ / 2)^{k} L (θ^{(0)})$ . The step-size constant can ensure $0 < η λ / 2 < 1$ , because $λ H^{2} \leq C$ . This proves geometric convergence on the probability- $1 - δ$ event. For $H = 1$ the architectures and population kernels coincide; the width is exactly the fully connected depth-one restriction up to fixed constants, and its local proof applies with the same contraction and step-size form. The same application bounds the total parameter path by $2 \sqrt{2} ∥ r_{0} ∥ / \sqrt{λ}$ ; [F3] therefore supplies last-layer Gram stability and the displayed output Taylor-remainder bound on every accepted update segment, for all iterates simultaneously.

Remarks

The displayed sufficient width retains the approved stronger depth restriction. The first term in the official Theorem 6.1 is $n^{4} / (λ_{0}^{4} H^{6})$ , whereas the displayed term is $n^{4} H^{6} / λ_{0}^{4}$ . The proof here establishes the displayed approved restriction by a parameter-ball argument, retaining all trainable layers. It does not claim the sharper source width from this argument. The residual population kernel includes its mean cross terms and differs from the fully connected kernel.

4 · Examples, counterexamples and false statements

None yet.

Overparameterized networks and training to interpolation

2 · Logical flowchart

3 · Definitions, theorems and proofs

The Gaussian activation normalizer is finite and positive

Statement

Statement references

Facts & Assumptions

Proof

Gram control and a Taylor remainder imply one-step loss contraction

Statement

Statement references

Facts & Assumptions

Proof

Fully connected and residual networks with the Du Gram kernel

Definition

Definition references

The recursively defined population Gram matrices are finite, symmetric, and positive semidefinite

Statement

Statement references

Facts & Assumptions

Proof

Gradient descent induces an exact output Gram update with a Taylor remainder

Statement

Statement references

Facts & Assumptions

Proof

Gaussian output initialization concentrates conditionally on the hidden features

Statement

Statement references

Facts & Assumptions

Proof

Local Gram positivity and loss smoothness give confined gradient descent

Statement

Statement references

Facts & Assumptions

Proof

Parameter-ball control of the last-layer Gram and loss Hessian

Statement

Statement references

Facts & Assumptions

Proof

Simultaneous initialization estimates for the Du architectures

Statement

Statement references

Facts & Assumptions

Proof

Wide fully connected networks converge geometrically to zero empirical training loss

Statement

Statement references

Facts & Assumptions

Proof

Wide residual networks converge geometrically to zero empirical loss with polynomial depth dependence

Statement

Statement references

Facts & Assumptions

Proof

Remarks

4 · Examples, counterexamples and false statements

Sources