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.

Norm and margin generalization for neural networks

1 · Prerequisites

2 · Logical flowchart

3 · Definitions, theorems and proofs

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

Proper Frobenius covering numbers

Definition

Let $n, m \geq 1$ , let $U$ be a nonempty subset of the real matrix space $R^{n \times m}$ , and let $ϵ > 0$ . A proper $ϵ$ -cover of $U$ in Frobenius norm is a finite subset $V \subseteq U$ such that every $X \in U$ has some $Y \in V$ with $∥ X - Y ∥_{F} \leq ϵ$ . The proper Frobenius covering number $N_{F} (U, ϵ)$ is the least cardinality of such a cover when one exists, and is $+ \infty$ otherwise. The cover is proper because its centers belong to $U$ .

Definition references

The Frobenius norm $∥ A ∥_{F} = (\sum_{i, j} ∣ a_{i j} ∣^{2})^{1 / 2}$ on real or complex matrices: defines $∥ X - Y ∥_{F}$ as the Euclidean norm of the full matrix-entry list.

Bartlett, Foster, and Telgarsky, §3.2: defines the covering number using finite centers in the covered set.

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

Spectral network complexity with reference matrices

Definition

Let $L \geq 1$ and let $d_{0}, \dots, d_{L} \geq 1$ be layer widths, with $K : = d_{L} \geq 2$ output classes. For each $i \in {1, \dots, L}$ , fix a matrix $M_{i} \in R^{d_{i} \times d_{i - 1}}$ and a vector activation $σ_{i} : R^{d_{i}} \to R^{d_{i}}$ satisfying $σ_{i} (0) = 0$ and $∥ σ_{i} (u) - σ_{i} (v) ∥_{2} \leq ρ_{i} ∥ u - v ∥_{2} (u, v \in R^{d_{i}})$ for a fixed $ρ_{i} > 0$ . A network has matrices $A_{i} \in R^{d_{i} \times d_{i - 1}}$ , no biases, and is evaluated by $h_{0} (x) = x$ and $h_{i} (x) = σ_{i} (A_{i} h_{i - 1} (x))$ , with score vector $F_{A} (x) = h_{L} (x)$ . For a real matrix $B$ , define $∥ B ∥_{2, 1} : = \sum_{j} ∥ B_{\cdot j} ∥_{2}$ , the sum of the Euclidean norms of its columns. Write $∥ A ∥_{σ}$ for the induced Euclidean operator norm $\max_{∥ u ∥_{2} = 1} ∥ A u ∥_{2}$ and put $W : = \max_{0 \leq i \leq L} d_{i}$ .

For a network whose layer matrices all have nonzero operator norm, its spectral network complexity relative to $(M_{i})$ is $R_{A} : = (\prod_{i = 1}^{L} ρ_{i} ∥ A_{i} ∥_{σ}) {(\sum_{i = 1}^{L} {(\frac{∥ A_{i}^{⊤} - M_{i}^{⊤} ∥_{2, 1}}{∥ A_{i} ∥_{σ}})}^{2 / 3})}^{3 / 2} .$ If some $A_{i} = 0$ , the network is instead handled as the constant-zero score map: the recurrence gives $h_{i} = 0$ and all later hidden vectors are zero. The displayed complexity is not defined in that zero-layer case.

The block diagram is schematic for $L \geq 3$ and depicts the stated recurrence. Each node is the entire vector at one layer; the arrow labelled $A_{i}$ is the zero-bias linear map, followed by the vector activation shown in the next node. The omitted middle layers are represented by the ellipsis, and the widths are those in the definition. For $L = 1$ or $L = 2$ , omit the ellipsis and use the corresponding initial segment of the recurrence. The diagram is illustrative and is not used in any proof.

diagram failed to render:
\begin{tikzpicture}[>=stealth]
  \node[draw,rounded corners] (h0) at (0,0) {$h_0=x\in\mathbb R^{d_0}$};
  \node[draw,rounded corners] (h1) at (3.1,0) {$h_1=\sigma_1(A_1h_0)$};
  \node (dots) at (4.9,0) {$\cdots$};
  \node[draw,rounded corners] (hL) at (6.8,0) {$h_L=\sigma_L(A_Lh_{L-1})=F_A(x)$};
  \draw[->] (h0) -- node[above] {$A_1$} (h1);
  \draw[->] (h1) -- (dots);
  \draw[->] (dots) -- node[above] {$A_L$} (hL);
\end{tikzpicture}

Definition references

Finite feedforward computation graphs and layered MLPs: finite acyclic computation graphs and their layered evaluation provide the broader feedforward-network context; the displayed vector-valued layer convention is defined fully above.

The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||: the induced norm is the maximum Euclidean output norm over unit input vectors.

The operator norm is 0 on the zero domain and otherwise equals the largest singular value, attained at a right-singular vector: the induced Euclidean operator norm equals the largest singular value, including rectangular real matrices.

Bartlett, Foster, and Telgarsky, Definition (1.2): defines the layerwise spectral/reference-matrix complexity used in the margin bound.

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

A truncated covering integral bounds empirical Rademacher complexity

Statement

Let $n \geq 1$ , let $S = (z_{1}, \dots, z_{n})$ be a fixed sample, and let $G$ be a nonempty class of measurable functions into $[0, 1]$ . Write $G ∣ S$ for the set of column vectors $(g (z_{1}), \dots, g (z_{n}))^{⊤}$ as $g$ ranges over $G$ . For $0 < α \leq \sqrt{n}$ , ${\hat{R}}_{S} (G) \leq \frac{4 α}{\sqrt{n}} + \frac{12}{n} \int_{α}^{\sqrt{n}} \sqrt{\log N_{F} (G ∣ S, ϵ)} d ϵ,$ where ${\hat{R}}_{S}$ is the one-sided empirical Rademacher complexity with $1 / n$ normalization and $N_{F}$ is the proper Frobenius covering number of the sample-vector set, identified with $n \times 1$ matrices. The set $G ∣ S$ is totally bounded because it lies in $[0, 1]^{n}$ .

Statement references

One-sided Rademacher complexity: fixes the one-sided empirical sign average and its $1 / n$ normalization.

Proper Frobenius covering numbers: defines $N_{F}$ using finite centers belonging to the covered set.

Facts & Assumptions

Given: $n \geq 1$ , a fixed sample $S$ , a nonempty $[0, 1]$ -valued function class, and the corresponding finite sign space.

[F1]

The one-sided empirical complexity is $E_{ε} \sup_{g \in G} n^{- 1} \sum_{i = 1}^{n} ε_{i} g (z_{i})$ , where the signs are independent and uniform on ${- 1, + 1}$ . One-sided Rademacher complexity

[F2]

$N_{F} (U, ϵ)$ is the least number of centers in a finite proper Frobenius $ϵ$ -cover of $U$ . Proper Frobenius covering numbers

[F3]

$\cosh x > 0$ , $\cosh$ is even, $\cosh^{'} x = \sinh x$ , $\tanh^{'} x = {sech}^{2} x$ , and $\cosh^{2} x - \sinh^{2} x = 1$ . The six hyperbolic functions and their natural domains Addition formulas, identities, parity, and derivatives of the hyperbolic functions

[F4]

For a bounded real random variable $Y$ and convex exponential, $\exp (λ E Y) \leq E \exp (λ Y)$ . Jensen's inequality for expectation

[F5]

$\log$ is the increasing inverse of $\exp$ on positive reals, with $\log (x y) = \log x + \log y$ and $\log 1 = 0$ . The natural logarithm as the inverse of the exponential function Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm

[F6]

If a real function is continuous on $[a, b]$ and differentiable on $(a, b)$ , the mean value theorem gives $f (b) - f (a) = f^{'} (c) (b - a)$ for some $c \in (a, b)$ . 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)$

[F7]

The exponential, chain, and product rules give derivatives of $e^{- x^{2} / 2} \cosh x$ ; the hyperbolic derivatives and identities in [F3] apply. The exponential function is smooth and $(\exp)^{'} = \exp$ The chain rule, in one line from Carathéodory: if $g$ is differentiable at $c$ and $f$ is differentiable at $g (c)$ , then $f \circ g$ is differentiable at $c$ with $(f \circ g)^{'} (c) = f^{'} (g (c)) g^{'} (c)$ Sums, scalar multiples, products and quotients: $(f + g)^{'} (c) = f^{'} (c) + g^{'} (c)$ , $(α f)^{'} (c) = α f^{'} (c)$ , $(f g)^{'} (c) = f^{'} (c) g (c) + f (c) g^{'} (c)$ , and $(f / g)^{'} (c) = (f^{'} (c) g (c) - f (c) g^{'} (c)) / g (c)^{2}$ when $g (c) \neq 0$

[F8]

For vectors $u, v$ in a real or complex inner product space, $∣ ⟨ u, v ⟩ ∣ \leq ∥ u ∥ ∥ v ∥$ . Cauchy–Schwarz: $∣ ⟨ u, v ⟩ ∣ \leq ∥ u ∥ ∥ v ∥$ , with equality exactly for linearly dependent vectors

Proof

1.1F3F6F7algebra

For $x > 0$ , put $r (x) = x - \tanh x$ . By [F3], $r (0) = 0$ and $r^{'} (x) = 1 - {sech}^{2} x = \tanh^{2} x \geq 0$ . The mean value theorem [F6] therefore gives $r (x) \geq 0$ ; at $x = 0$ this is equality. Put $q (x) = e^{- x^{2} / 2} \cosh x$ . The derivative rules in [F3] and [F7] give $q^{'} (x) = e^{- x^{2} / 2} \cosh x (\tanh x - x) \leq 0$ . Applying [F6] on $[0, x]$ for $x > 0$ yields $q (x) \leq q (0) = 1$ , and equality holds at $x = 0$ . Since $q$ is even, $\cosh x \leq e^{x^{2} / 2}$ for every real $x$ .

1.2F1F2givenconstruct

Choose $g_{0} \in G$ and subtract its sample vector $v_{0}$ from every vector in $G ∣ S$ . The empirical Rademacher average is unchanged because $E_{ε} \sum_{i} ε_{i} g_{0} (z_{i}) = 0$ , and translation preserves all Frobenius covering numbers. Write $U : = (G ∣ S) - v_{0}$ ; it contains $0$ , and each vector has norm at most $\sqrt{n}$ . For any $ϵ > 0$ , partition $[- 1, 1]^{n}$ into finitely many boxes of side at most $ϵ / \sqrt{n}$ ; from each box meeting $U$ take one member of that intersection. The resulting finite set is a proper $ϵ$ -cover, since two points in one box differ in Euclidean norm by at most $ϵ$ . Set $ϵ_{j} = \sqrt{n} 2^{- (j - 1)}$ . The singleton $V_{1} = {0}$ is a proper $ϵ_{1}$ -cover of $U$ , so $∣ V_{1} ∣ = N_{F} (U, ϵ_{1}) = 1$ . For each finite truncation $N \geq 2$ and each $2 \leq j \leq N$ , choose a proper $ϵ_{j}$ -cover $V_{j}$ of $U$ with the least possible cardinality, so $∣ V_{j} ∣ = N_{F} (U, ϵ_{j})$ ; such a least cardinality exists because a finite cover exists and cover cardinalities are positive integers. Enumerate each finite cover and map every sample vector to the first center within $ϵ_{j}$ .

2.1F1F4F5step 1.1algebra

Let $V$ be a nonempty finite set of vectors in $R^{n}$ and let $R = \max_{v \in V} ∥ v ∥_{2}$ . For $T_{v} = \sum_{i} ε_{i} v_{i}$ , independence of the signs and step 1.1 give $E e^{λ T_{v}} = \prod_{i} \cosh (λ v_{i}) \leq e^{λ^{2} R^{2} / 2}$ . If $R = 0$ or $∣ V ∣ = 1$ , $E \max_{v \in V} T_{v} = 0$ . Otherwise, for $λ > 0$ , [F4] and $e^{λ \max_{v} T_{v}} \leq \sum_{v \in V} e^{λ T_{v}}$ imply $E \max_{v} T_{v} \leq \log ∣ V ∣ / λ + λ R^{2} / 2$ . Choosing $λ = \sqrt{2 \log ∣ V ∣} / R$ gives $E \max_{v} T_{v} \leq R \sqrt{2 \log ∣ V ∣}$ .

3.1F1F2F8step 2.1step 1.2algebra

For any translated sample vector $v \in U$ , telescope $v = (v - v_{N} [v]) + \sum_{j = 1}^{N - 1} (v_{j + 1} [v] - v_{j} [v])$ , since $v_{1} [v] = 0$ . The absolute residual sign sum is at most $∥ (ε_{i})_{i} ∥_{2} ∥ v - v_{N} [v] ∥_{2} \leq \sqrt{n} ϵ_{N}$ by [F8]. For each $j < N$ , use only the paired-center difference set $D_{j} : = {v_{j + 1} [v] - v_{j} [v] : v \in U}$ . It is a nonempty subset of $V_{j + 1} - V_{j}$ , so its cardinality is at most $∣ V_{j + 1} ∣ ∣ V_{j} ∣ \leq N_{F} (G ∣ S, ϵ_{j + 1})^{2}$ , because covering numbers are nonincreasing with radius. Each paired difference has norm at most $∥ v_{j + 1} [v] - v ∥_{2} + ∥ v - v_{j} [v] ∥_{2} \leq ϵ_{j + 1} + ϵ_{j} = 3 ϵ_{j + 1}$ . Step 2.1 applied to $D_{j}$ therefore bounds its expected maximum sign sum by $6 ϵ_{j + 1} \sqrt{\log N_{F} (G ∣ S, ϵ_{j + 1})}$ . Taking the supremum in the telescoping identity, summing these bounds, and dividing by $n$ gives ${\hat{R}}_{S} (G) \leq ϵ_{N} / \sqrt{n} + (6 / n) \sum_{j = 1}^{N - 1} ϵ_{j + 1} \sqrt{\log N_{F} (G ∣ S, ϵ_{j + 1})}$ .

4.1F2step 3.1algebra

The function $f (ϵ) = \sqrt{\log N_{F} (G ∣ S, ϵ)}$ is nonincreasing in $ϵ$ . Since $ϵ_{j + 2} = ϵ_{j + 1} / 2$ , each summand obeys $ϵ_{j + 1} f (ϵ_{j + 1}) \leq 2 \int_{ϵ_{j + 2}}^{ϵ_{j + 1}} f (ϵ) d ϵ$ . Therefore step 3.1 gives ${\hat{R}}_{S} (G) \leq ϵ_{N} / \sqrt{n} + (12 / n) \int_{ϵ_{N + 1}}^{\sqrt{n}} f (ϵ) d ϵ$ .

5.1F1step 4.1algebra∎

If $\sqrt{n} / 4 \leq α \leq \sqrt{n}$ , each signed average is at most $1$ , so ${\hat{R}}_{S} (G) \leq 1 \leq 4 α / \sqrt{n}$ . If $0 < α < \sqrt{n} / 4$ , choose the largest $N \geq 1$ with $ϵ_{N + 1} > α$ ; such an $N$ exists because $ϵ_{2} = \sqrt{n} / 2 > α$ and $ϵ_{j} \to 0$ . Maximality gives $ϵ_{N + 2} \leq α$ , hence $ϵ_{N} = 4 ϵ_{N + 2} \leq 4 α$ , and $\int_{ϵ_{N + 1}}^{\sqrt{n}} f \leq \int_{α}^{\sqrt{n}} f$ . Substitution into step 4.1 proves the stated inequality for every $0 < α < \sqrt{n} / 4$ . Together, the two cases prove it for every $0 < α \leq \sqrt{n}$ .

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

Multiclass margins, ramp loss, and empirical margin loss

Definition

Let $K \geq 2$ , let $D$ be a Borel probability measure on $R^{d} \times {1, \dots, K}$ , and let $F : R^{d} \to R^{K}$ be a continuous score map. At $(x, y)$ its multiclass margin is $m_{F} (x, y) : = F (x)_{y} - \max_{j \neq y} F (x)_{j} .$ The predicted label is ${\hat{y}}_{F} (x) : = \min {j \in {1, \dots, K} : F (x)_{j} = \max_{1 \leq l \leq K} F (x)_{l}} .$ Its population zero-one error is $L_{0} (F) : = D ({(x, y) : {\hat{y}}_{F} (x) \neq y}) .$ For $γ > 0$ , the ramp loss is $ℓ_{γ} (r) : = {\begin{cases} 0, & r < - γ, \\ 1 + r / γ, & - γ \leq r \leq 0, \\ 1, & r > 0. \end{cases}$ The population ramp risk is $R_{γ} (F) : = \int ℓ_{γ} (- m_{F} (x, y)) D (d (x, y))$ . For a sample $S = ((x_{1}, y_{1}), \dots, (x_{n}, y_{n}))$ of length $n \geq 1$ , the empirical ramp risk and empirical margin loss are ${\hat{R}}_{γ, S} (F) : = \frac{1}{n} \sum_{i = 1}^{n} ℓ_{γ} (- m_{F} (x_{i}, y_{i})), {\hat{L}}_{γ, S} (F) : = \frac{1}{n} \sum_{i = 1}^{n} 1 {m_{F} (x_{i}, y_{i}) \leq γ} .$ The score coordinates are continuous, and finite maxima, comparisons, and the piecewise-linear ramp preserve Borel measurability. Thus the classification event and ramp loss in the displayed integrals are Borel sets or functions, so the risks are well-defined for $D$ .

Definition references

The Borel sigma-algebra of a topological space: Borel subsets are members of the sigma-algebra generated by open sets.

Probability measures and probability spaces: a probability measure is a measure of total mass one.

Supervised prediction problems: fixes measurable instance and label spaces, a joint law, predictors, and measurable losses.

Population and empirical risk: defines population risk as an extended nonnegative integral and empirical risk as a finite sample average.

Bartlett, Foster, and Telgarsky, §3.1 and Appendix A.2: gives the multiclass margin operator and the ramp convention.

Mohri, Lecture 4, pp. 28–31: treats confidence margin, empirical margin loss, and margin-based risk bounds for binary scores.

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

A proper matrix-product cover from the mixed (2,1) norm

Statement

Let $X \in R^{n \times d}$ , $M \in R^{d \times m}$ with $n, d, m \geq 1$ , and let $a, s \geq 0$ . Suppose $C : = {A \in R^{d \times m} : ∥ A - M ∥_{2, 1} \leq a, ∥ A ∥_{σ} \leq s}$ is nonempty. Put $U : = {X A : A \in C}$ . For every $ϵ > 0$ , $\log N_{F} (U, ϵ) \leq 5 \frac{a^{2} ∥ X ∥_{F}^{2}}{ϵ^{2}} \log (2 d m) .$ If $a ∥ X ∥_{F} = 0$ or $ϵ \geq 2 a ∥ X ∥_{F}$ , then $N_{F} (U, ϵ) = 1$ . Here $∥ A - M ∥_{2, 1}$ is the sum of the Euclidean norms of the columns of $A - M$ ; when applying this lemma to a network layer, take $A = A_{i}^{⊤}$ and $M = M_{i}^{⊤}$ , as in the spectral-network-complexity definition. The number $N_{F}$ is the proper Frobenius covering number.

Statement references

Spectral network complexity with reference matrices: defines the column-sum mixed norm and the induced Euclidean operator norm.

Proper Frobenius covering numbers: defines the proper cover whose centers must lie in $U$ .

The Frobenius norm $∥ A ∥_{F} = (\sum_{i, j} ∣ a_{i j} ∣^{2})^{1 / 2}$ on real or complex matrices: defines the Euclidean matrix-entry norm used to measure cover error.

Bartlett, Foster, and Telgarsky, Lemma 3.2 and Appendix A.4: gives the Maurey sparsification route to this matrix-product cover.

Facts & Assumptions

Given: Matrices $X, M$ , dimensions and constants as in the Statement, and the nonempty feasible set $C$ .

[F1]

$∥ Z ∥_{F}^{2}$ is the sum of the squared absolute values of all entries of $Z$ . The Frobenius norm $∥ A ∥_{F} = (\sum_{i, j} ∣ a_{i j} ∣^{2})^{1 / 2}$ on real or complex matrices

[F2]

$∣ ⟨ u, v ⟩ ∣ \leq ∥ u ∥ ∥ v ∥$ in a real or complex inner-product space. Cauchy–Schwarz: $∣ ⟨ u, v ⟩ ∣ \leq ∥ u ∥ ∥ v ∥$ , with equality exactly for linearly dependent vectors

[F3]

The Euclidean inner-product norm is homogeneous and satisfies the triangle inequality. The inner-product norm is definite, homogeneous, and satisfies the triangle inequality

[F4]

$N_{F} (U, ϵ)$ is the least size of a finite proper Frobenius cover of $U$ . Proper Frobenius covering numbers

[F5]

Closed bounded subsets of finite-dimensional real Euclidean space are compact. Heine-Borel in $R^{n}$ : with the Euclidean metric a subset of $R^{n}$ is compact if and only if it is closed and bounded, and the proof by bisection uses no choice principle; the same holds on the real line

[F6]

$\log$ is strictly increasing on positive reals and satisfies $\log (x y) = \log x + \log y$ . The natural logarithm as the inverse of the exponential function Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm

[F7]

The mixed norm is the sum of the Euclidean column norms, and $∥ A ∥_{σ}$ is the induced Euclidean operator norm. Spectral network complexity with reference matrices

[F8]

A continuous map from a compact metric space has compact image. The image of a compact metric space under a continuous map is compact, and so is the image of any compact subset

[F9]

A continuous real-valued function on a nonempty compact metric space attains its minimum. A continuous real-valued function on a nonempty compact metric space is bounded and attains a greatest and a least value

Proof

1.1F1F2F7givenalgebra

For any $B \in R^{d \times m}$ , write its columns as $b_{j}$ and the columns of $X$ as $x_{r}$ . By [F2], $∥ X b_{j} ∥_{2}^{2} = \sum_{i} ∣ \sum_{r} X_{i r} (b_{j})_{r} ∣^{2} \leq ∥ X ∥_{F}^{2} ∥ b_{j} ∥_{2}^{2}$ . Summing over $j$ gives $∥ X B ∥_{F} \leq ∥ X ∥_{F} (\sum_{j} ∥ b_{j} ∥_{2}^{2})^{1 / 2} \leq ∥ X ∥_{F} \sum_{j} ∥ b_{j} ∥_{2} = ∥ X ∥_{F} ∥ B ∥_{2, 1}$ ; the middle inequality follows by squaring, since all column norms are nonnegative. Thus $∥ A - A^{'} ∥_{2, 1} \leq 2 a$ for $A, A^{'} \in C$ , and the diameter of $U$ is at most $2 a ∥ X ∥_{F}$ . If $a ∥ X ∥_{F} = 0$ , $U$ is a singleton; if $ϵ \geq 2 a ∥ X ∥_{F}$ , any one point of nonempty $U$ covers it.

1.2F1F2F7givenconstructalgebra

Assume $a ∥ X ∥_{F} > 0$ and $0 < ϵ < 2 a ∥ X ∥_{F}$ . For each nonzero column $x_{r}$ , each output coordinate $j$ , and each sign $η \in {- 1, + 1}$ , form the rank-one atom $V_{r j η} = η (x_{r} / ∥ x_{r} ∥_{2}) e_{j}^{⊤}$ , where $e_{j}$ is the $j$ th standard basis vector in $R^{m}$ . There are at most $2 d m$ atoms and each has Frobenius norm $1$ . For $B = A - M$ , the expansion $X B = \sum_{r, j} (B)_{r j} x_{r} e_{j}^{⊤}$ has coefficient mass $β : = \sum_{r, j} ∣ B_{r j} ∣ ∥ x_{r} ∥_{2} \leq ∥ B ∥_{2, 1} ∥ X ∥_{F} \leq a ∥ X ∥_{F} = : c$ , by [F2] column by column. Hence $X B / c$ lies in the convex hull of these signed atoms: if $β < c$ , fill the remaining weight with $0$ , which is the midpoint of an atom and its negative. If $β = 0$ , the product is $0$ .

2.1F1step 1.2givenalgebraconstruct

For an integer $k \geq 1$ , sample $k$ atoms independently from the finite convex representation of $X B / c$ constructed in step 1.2. If $V_{1}, \dots, V_{k}$ are these atoms and $E V_{1} = X B / c$ , expansion of the squared Frobenius norm and independence give $E ∥ c k^{- 1} \sum_{t = 1}^{k} V_{t} - X B ∥_{F}^{2} = (c^{2} / k) (E ∥ V_{1} ∥_{F}^{2} - ∥ E V_{1} ∥_{F}^{2}) \leq c^{2} / k$ . Therefore some ordered $k$ -tuple gives a center within $c / \sqrt{k}$ , and all such centers number at most $(2 d m)^{k}$ . Taking $k = ⌈ c^{2} / ϵ^{2} ⌉$ yields an external $ϵ$ -cover of the translated relaxed product set $X M + {X B : ∥ B ∥_{2, 1} \leq a}$ .

3.1F1F2F3F5F7F8F9step 1.1step 2.1givenalgebraconstruct

The mixed-norm constraint set is convex: for $A, A^{'} \in C$ and $0 \leq t \leq 1$ , the column triangle inequality [F3] gives $∥ t (A - M) + (1 - t) (A^{'} - M) ∥_{2, 1} \leq t a + (1 - t) a = a$ . The operator-norm constraint is convex because for each unit vector $v$ , $∥ (t A + (1 - t) A^{'}) v ∥_{2} \leq t ∥ A v ∥_{2} + (1 - t) ∥ A^{'} v ∥_{2} \leq s$ , and taking the supremum over $v$ preserves the bound. The mixed norm is continuous as a finite sum of continuous column norms. From [F7] and the Euclidean triangle inequality, $∣ ∥ A ∥_{σ} - ∥ A^{'} ∥_{σ} ∣ \leq ∥ A - A^{'} ∥_{σ} \leq ∥ A - A^{'} ∥_{F}$ , where the last inequality follows from the rowwise Cauchy estimate in step 1.1; hence the operator norm is continuous and $C$ is closed. Also $∥ A - M ∥_{F} \leq ∥ A - M ∥_{2, 1} \leq a$ , so $C$ is bounded. Identify the real matrix space with $R^{d m}$ by its entries; its Euclidean norm is the Frobenius norm, so [F5] makes $C$ compact. The map $T (A) = X A$ is continuous because step 1.1 and [F2] give $∥ T (A) - T (A^{'}) ∥_{F} \leq ∥ X ∥_{F} ∥ A - A^{'} ∥_{2, 1} \leq \sqrt{m} ∥ X ∥_{F} ∥ A - A^{'} ∥_{F}$ . Hence [F8] makes $U = T (C)$ compact; it is convex because $C$ is convex and $T$ is linear. For each of the finitely many external centers $z$ from step 2.1, the function $u \mapsto ∥ z - u ∥_{F}$ is continuous on the nonempty compact metric space $U$ , since the reverse triangle inequality bounds its change by $∥ u - u^{'} ∥_{F}$ . Thus [F9] gives a nearest point $p \in U$ for each center; enumerate the finite center set and choose these minimizers successively. For any $u \in U$ , convexity gives $p + t (u - p) \in U$ for $0 \leq t \leq 1$ . Put $⟨ P, Q ⟩_{F} : = \sum_{i, j} P_{i j} Q_{i j}$ . Minimality implies $0 \leq ∥ z - p - t (u - p) ∥_{F}^{2} - ∥ z - p ∥_{F}^{2} = - 2 t ⟨ z - p, u - p ⟩_{F} + t^{2} ∥ u - p ∥_{F}^{2}$ for $0 < t \leq 1$ ; division by $t$ and passage to $t ↓ 0$ give $⟨ z - p, u - p ⟩_{F} \leq 0$ . Expanding $∥ z - u ∥_{F}^{2}$ then gives $∥ p - u ∥_{F}^{2} \leq ∥ z - u ∥_{F}^{2}$ . Thus projection does not increase distance to any point of $U$ , and the cover becomes proper without increasing its size.

4.1F4F6step 1.1step 3.1step 2.1algebra∎

Put $q = a^{2} ∥ X ∥_{F}^{2} / ϵ^{2} > 1 / 4$ . Then $k = ⌈ q ⌉ \leq q + 1 \leq 5 q$ , so step 2.1 and [F6] imply $\log N_{F} (U, ϵ) \leq k \log (2 d m) \leq 5 q \log (2 d m)$ . Together with step 1.1 this proves both cases of the Statement.

LemmaStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Uniform margin-risk deviation from empirical Rademacher complexity

Statement

Assume the axiom of choice.

Fix a finite network architecture with $L \geq 1$ , widths $d_{0}, \dots, d_{L} \geq 1$ , output size $K = d_{L} \geq 2$ , and activations as in the spectral-network-complexity definition. Let $s_{i} > 0$ , $b_{i} \geq 0$ , and reference matrices $M_{i}$ be such that the class $F : = {F_{A} : ∥ A_{i} ∥_{σ} \leq s_{i}, ∥ A_{i}^{⊤} - M_{i}^{⊤} ∥_{2, 1} \leq b_{i} for every i}$ is nonempty. Let $D$ be any Borel probability measure on $R^{d_{0}} \times {1, \dots, K}$ , let $S = ((x_{1}, y_{1}), \dots, (x_{n}, y_{n}))$ be an independent identically distributed sample from $D$ with $n \geq 1$ , and fix $γ > 0$ and $0 < δ < 1$ . Define the ramp-loss class $L_{γ} : = {(x, y) \mapsto ℓ_{γ} (- m_{F} (x, y)) : F \in F} .$ With probability at least $1 - δ$ over $S$ , every $F \in F$ satisfies $L_{0} (F) \leq {\hat{L}}_{γ, S} (F) + 2 {\hat{R}}_{S} (L_{γ}) + 3 \sqrt{\frac{\log (2 / δ)}{2 n}},$ where ${\hat{R}}_{S}$ is the one-sided empirical Rademacher complexity with $1 / n$ normalization.

Statement references

Multiclass margins, ramp loss, and empirical margin loss: defines multiclass margin, ramp risk, zero-one risk, and empirical margin loss.

Spectral network complexity with reference matrices: fixes the network family and the layer constraints used to form $F$ .

One-sided Rademacher complexity: fixes the one-sided empirical Rademacher convention and normalization.

Facts & Assumptions

Given: The compactly constrained network class, Borel probability measure, iid sample, fixed margin level, confidence parameter, and ramp-loss class in the Statement.

[F1]

Scores are formed by finite matrix layers and zero-origin Lipschitz activations; the margin is the finite minimum $m_{F} (x, y) = \min_{j \neq y} (F (x)_{y} - F (x)_{j})$ , and the ramp loss takes values in $[0, 1]$ . Spectral network complexity with reference matrices Multiclass margins, ramp loss, and empirical margin loss

[F2]

[F3]

For bounded pointwise-convergent measurable functions, dominated convergence passes the limit through the probability integral. Dominated convergence

[F4]

Independent random elements have the product joint law, and change of variables transfers integrable product-law functions to expectations; these facts justify the independent ghost sample, pairwise swaps, and expectation identities. Identical distribution and IID families The product sigma-algebra and its finite iterates Independent random elements have product joint law Change of variables for expectation

[F5]

The axiom of choice permits choosing one point from every nonempty member of a countable family of sets. The Axiom of Choice

[F6]

If changing one independent coordinate changes a bounded measurable statistic by at most $1 / n$ , McDiarmid's inequality bounds each of its upper and lower tails by $\exp (- 2 n t^{2})$ ; the lower-tail bound follows by applying the upper-tail bound to the negative statistic. McDiarmid bounded-differences inequality

[F7]

The empirical Rademacher complexity is the expectation over independent uniform signs of the supremum of the normalized signed sample averages. One-sided Rademacher complexity

[F8]

The logarithm is increasing and $\log (x y) = \log x + \log y$ . The natural logarithm as the inverse of the exponential function Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm

[F9]

The rationals are dense in the reals: every nonempty open real interval contains a rational. Both $Q$ and $R ∖ Q$ are dense in $R$ , and every nonempty open subset of $R$ is uncountable

Proof

1.1F1F2givenalgebra

Let $Θ$ be the set of all feasible tuples $(A_{1}, \dots, A_{L})$ . The mixed-norm constraints are closed because each is a finite sum of continuous Euclidean column norms. For each layer, $∥ A_{i} ∥_{σ} \leq s_{i}$ is the intersection, over all unit vectors $v$ , of the closed conditions $∥ A_{i} v ∥_{2} \leq s_{i}$ , by the induced-operator-norm definition. Each column $A_{i} e_{j}$ then has norm at most $s_{i}$ , so all matrix entries are bounded. Hence $Θ$ is closed and bounded in finite-dimensional Euclidean space and is compact by [F2].

2.1F1F3step 1.1given

For fixed $x$ , induction over the layers shows that the score vector depends continuously on the matrix tuple: matrix multiplication is jointly continuous and each Lipschitz activation is continuous. Finite maxima, coordinate differences, and the ramp preserve continuity, so for fixed $(x, y)$ the loss $A \mapsto ℓ_{γ} (- m_{F_{A}} (x, y))$ is continuous. If $A^{(r)} \to A$ , these losses converge pointwise in $(x, y)$ and are bounded by one, so [F3] shows that $A \mapsto R_{γ} (F_{A})$ is continuous. Each empirical loss and each finite signed sum of losses is also continuous in $A$ .

3.1F1F5F9step 1.1step 2.1given

Identify the parameter tuples with $R^{p}$ , where $p : = \sum_{i = 1}^{L} d_{i} d_{i - 1}$ . The balls $B (q, r)$ with $q \in Q^{p}$ and $r \in Q_{> 0}$ form a countable family: each rational is a quotient of an integer by a positive integer, the integers have the enumeration $0, 1, - 1, 2, - 2, \dots$ , and finite tuples of natural numbers are enumerated by iterating the diagonal pairing $π (a, b) : = (a + b) (a + b + 1) / 2 + b$ . They form a base because for any open $O \subseteq R^{p}$ and $x \in O$ , choose $η > 0$ with $B (x, η) \subseteq O$ , then use [F9] in each coordinate interval $(x_{j} - η / (4 \sqrt{p}), x_{j} + η / (4 \sqrt{p}))$ to choose $q \in Q^{p}$ with $∥ q - x ∥_{2} < η / 4$ . Use [F9] again to choose a rational $r$ with $∥ q - x ∥_{2} < r < η - ∥ q - x ∥_{2}$ (a nonempty interval with positive upper endpoint); then $x \in B (q, r) \subseteq B (x, η) \subseteq O$ . Intersecting these balls with $Θ$ gives a countable base for its subspace topology. Using [F5], choose one point of $Θ$ from each nonempty basic intersection; the selected countable subset is dense in $Θ$ . By step 2.1, each supremum over $Θ$ defining the uniform deviation or a signed empirical supremum equals the supremum over this countable dense subset. The losses are Borel in $(x, y)$ because the scores are continuous in $x$ , the margin is a finite minimum of continuous score-coordinate differences, and the label set is finite. These countable suprema are therefore measurable.

4.1F4F7step 3.1givenalgebra

Write $Z (S) : = \sup_{F \in F} (R_{γ} (F) - {\hat{R}}_{γ, S} (F))$ . Let $S^{'}$ be an independent ghost sample from $D$ . By the integral identities in [F4] and the inequality $\sup_{F} E_{S^{'}} U_{F} \leq E_{S^{'}} \sup_{F} U_{F}$ , $E Z (S) \leq E_{S, S^{'}} \sup_{F \in F} \frac{1}{n} \sum_{i = 1}^{n} (ℓ_{F} (x_{i}^{'}, y_{i}^{'}) - ℓ_{F} (x_{i}, y_{i})),$ where $ℓ_{F} (x, y) = ℓ_{γ} (- m_{F} (x, y))$ . Swapping each iid pair $(z_{i}, z_{i}^{'})$ leaves its law unchanged; introducing independent uniform signs $ε_{i}$ therefore leaves this expectation unchanged when each difference is multiplied by $ε_{i}$ . The supremum of a sum is at most the sum of the suprema, and symmetry of the signs gives $E Z (S) \leq 2 E_{S} {\hat{R}}_{S} (L_{γ})$ .

5.1F6F7F8step 4.1givenalgebra

Replacing one sample coordinate changes $Z (S)$ by at most $1 / n$ , since every loss lies in $[0, 1]$ ; it also changes ${\hat{R}}_{S} (L_{γ})$ by at most $1 / n$ , by [F7] and the same range bound. Apply the upper-tail bound [F6] to $Z$ and to $- {\hat{R}}_{S} (L_{γ})$ , each with failure probability $δ / 2$ and $t = \sqrt{\log (2 / δ) / (2 n)}$ . Outside a set of probability at most $δ$ , both $Z (S) \leq E Z (S) + t$ and $E {\hat{R}}_{S} (L_{γ}) \leq {\hat{R}}_{S} (L_{γ}) + t$ . Combining with step 4.1 gives $Z (S) \leq E Z (S) + t \leq 2 E {\hat{R}}_{S} (L_{γ}) + t \leq 2 {\hat{R}}_{S} (L_{γ}) + 3 t$ .

6.1F1step 5.1givenalgebra∎

If the predicted label differs from $y$ , some competing score is at least the true-label score, so $m_{F} (x, y) \leq 0$ and $ℓ_{γ} (- m_{F} (x, y)) = 1$ . Hence the zero-one loss is pointwise at most the ramp loss. Also $ℓ_{γ} (- m) \leq 1 {m \leq γ}$ for every real $m$ , so empirical ramp risk is at most empirical margin loss. Apply the definition of $Z (S)$ and step 5.1 to conclude the stated bound for every $F \in F$ simultaneously.

Sources

Bartlett, Foster, and Telgarsky, Spectrally-normalized margin bounds for neural networks, Appendix A.2.

Mohri, Foundations of Machine Learning, Lecture 3, pp. 4–9.

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

Spectral and reference-matrix covering entropy for network outputs

Statement

Fix an architecture and activations as in the spectral-network-complexity definition, with widths $d_{0}, \dots, d_{L}$ and $W : = \max_{0 \leq i \leq L} d_{i}$ . Let $n \geq 1$ and let $X \in R^{n \times d_{0}}$ be any sample matrix. Let $M_{i} \in R^{d_{i} \times d_{i - 1}}$ , and fix $s_{i} > 0$ and $b_{i} \geq 0$ . Suppose each feasible layer set $C_{i} : = {A_{i} : ∥ A_{i} ∥_{σ} \leq s_{i}, ∥ A_{i}^{⊤} - M_{i}^{⊤} ∥_{2, 1} \leq b_{i}}$ is nonempty. Let $H_{X}$ be the set of $n \times d_{L}$ score matrices whose $r$ th row is $F_{A} (x_{r})^{⊤}$ , for $A_{i} \in C_{i}$ and the $r$ th row $x_{r}^{⊤}$ of $X$ . Then for every $ϵ > 0$ , $\log N_{F} (H_{X}, ϵ) \leq 5 \frac{∥ X ∥_{F}^{2}}{ϵ^{2}} \log (2 W^{2}) (\prod_{i = 1}^{L} (ρ_{i} s_{i})^{2}) {(\sum_{i = 1}^{L} (b_{i} / s_{i})^{2 / 3})}^{3} .$ The logarithm is natural, an empty product equals $1$ , and $N_{F}$ uses proper centers in the covered score-matrix set.

Statement references

Spectral network complexity with reference matrices: fixes the network recurrence, zero-origin Lipschitz activations, spectral norm, and mixed column-sum norm.

Proper Frobenius covering numbers: defines proper covers and their Frobenius radius.

A proper matrix-product cover from the mixed (2,1) norm: supplies the proper product cover for a fixed input matrix and one constrained layer.

Facts & Assumptions

Given: The architecture, activations, matrices, positive spectral bounds, nonnegative reference-distance bounds, nonempty layer sets, and sample matrix in the Statement.

[F1]

Each activation fixes zero and is $ρ_{i}$ -Lipschitz in Euclidean norm; each layer matrix has induced Euclidean norm at most $s_{i}$ , and its transpose-difference from the reference has column-sum norm at most $b_{i}$ . Spectral network complexity with reference matrices

[F2]

For a fixed input matrix $Z$ , the one-layer image under a nonempty feasible matrix set has a proper Frobenius cover satisfying the stated matrix-product entropy estimate. A proper matrix-product cover from the mixed (2,1) norm

[F3]

The Frobenius norm is the Euclidean norm of all matrix entries, so rowwise application of a $ρ_{i}$ -Lipschitz map changes Frobenius distances by at most the factor $ρ_{i}$ . The Frobenius norm $∥ A ∥_{F} = (\sum_{i, j} ∣ a_{i j} ∣^{2})^{1 / 2}$ on real or complex matrices Spectral network complexity with reference matrices

[F4]

A proper cover has centers in the covered set, and its covering number is the least size of such a finite cover. Proper Frobenius covering numbers

[F5]

The natural logarithm is increasing and satisfies $\log (x y) = \log x + \log y$ . The natural logarithm as the inverse of the exponential function Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm

[F6]

If $A = \sum_{j = 1}^{r} σ_{j} u_{j} v_{j}^{⊤}$ is a singular-value decomposition with $r > 0$ , then $A^{⊤} = \sum_{j = 1}^{r} σ_{j} v_{j} u_{j}^{⊤}$ has the same positive singular values; the largest-singular-value theorem therefore gives equal operator norms. If $r = 0$ , both matrices are zero and their operator norms are zero by the same theorem. Every linear map between finite-dimensional real or complex inner product spaces admits a singular value decomposition The operator norm is 0 on the zero domain and otherwise equals the largest singular value, attained at a right-singular vector

Proof

1.1F1F3F6giveninductionalgebra

Write $Z_{i} (A)$ for the matrix of rowwise layer- $i$ activations, with $Z_{0} (A) = X$ . Induction gives $∥ Z_{i - 1} (A) ∥_{F} \leq ∥ X ∥_{F} \prod_{j < i} ρ_{j} s_{j}$ : rowwise zero-origin Lipschitzness gives $∥ Z_{i} ∥_{F} \leq ρ_{i} ∥ Z_{i - 1} A_{i}^{⊤} ∥_{F}$ , and [F6] identifies $∥ A_{i}^{⊤} ∥_{σ} = ∥ A_{i} ∥_{σ} \leq s_{i}$ , so the induced norm gives $∥ Z_{i - 1} A_{i}^{⊤} ∥_{F} \leq s_{i} ∥ Z_{i - 1} ∥_{F}$ , row by row.

1.2F1givenalgebra

If every $b_{i} = 0$ , each feasible layer set is the singleton ${M_{i}}$ , so $H_{X}$ is a singleton and the right side is zero. Otherwise set $r_{i} = b_{i} / s_{i}$ , $T : = \sum_{i : r_{i} > 0} r_{i}^{2 / 3}$ , and $α_{i} : = r_{i}^{2 / 3} / T$ for positive $r_{i}$ , with $α_{i} = 0$ when $r_{i} = 0$ . These weights are nonnegative and sum to one over the varying layers.

2.1F1F2F4F6step 1.1step 1.2givenconstruct

Build finite proper covers of the attainable layer outputs successively. At layer $i$ , suppose the previous attainable activation matrices have a proper $η$ -cover with centers $V$ that are themselves attainable prefix outputs. For each such $V$ , [F6] gives $∥ A_{i}^{⊤} ∥_{σ} = ∥ A_{i} ∥_{σ}$ , so apply [F2] to ${V A_{i}^{⊤} : A_{i} \in C_{i}}$ with input $V$ , reference $M_{i}^{⊤}$ , radius $e_{i} / ρ_{i}$ , and $e_{i} : = α_{i} ϵ / \prod_{j > i} ρ_{j} s_{j}$ when $b_{i} > 0$ . Map each product-cover center through the rowwise activation $σ_{i}$ . Every resulting center is attainable by joining the prefix that realizes $V$ to its feasible layer matrix. For any actual prefix $Z$ within $η$ of $V$ and any $A_{i} \in C_{i}$ , the activation output differs from $σ_{i} (V A_{i}^{⊤})$ by at most $ρ_{i} s_{i} η$ ; the layer cover adds at most $e_{i}$ . Thus the next-stage cover radius is at most $ρ_{i} s_{i} η + e_{i}$ . When $b_{i} = 0$ , use the single matrix $M_{i}$ and set $e_{i} = 0$ .

3.1F2F4F5step 1.1step 2.1givenalgebra

Starting with the exact cover ${X}$ , the recurrence in step 2.1 gives final radius at most $\sum_{i} e_{i} \prod_{j > i} ρ_{j} s_{j} = ϵ \sum_{i : r_{i} > 0} α_{i} = ϵ$ . The cover is proper by construction. At each varying layer, [F2] and the bound from step 1.1 show that its cover-number logarithm is at most $5 \frac{∥ X ∥_{F}^{2} \prod_{j < i} (ρ_{j} s_{j})^{2} b_{i}^{2}}{(e_{i} / ρ_{i})^{2}} \log (2 d_{i - 1} d_{i}) .$ For each prior cover center $V$ , the next cover has at most this uniform cardinality bound, so taking the union over the prior centers multiplies cardinalities by at most that factor. Since $d_{i - 1}, d_{i} \leq W$ , the logarithm of the final product cover is at most the sum of the displayed layer bounds.

4.1F5step 1.2step 3.1givenalgebra∎

Substitute $e_{i} = α_{i} ϵ / \prod_{j > i} ρ_{j} s_{j}$ into step 3.1. Each varying-layer term becomes $5 \frac{∥ X ∥_{F}^{2}}{ϵ^{2}} \log (2 W^{2}) (\prod_{j = 1}^{L} (ρ_{j} s_{j})^{2}) \frac{r_{i}^{2}}{α_{i}^{2}} .$ By the choice in step 1.2, $\sum_{i : r_{i} > 0} r_{i}^{2} / α_{i}^{2} = T^{3} = (\sum_{i} (b_{i} / s_{i})^{2 / 3})^{3}$ . The all-zero case was handled in step 1.2, so the displayed bound follows in every case.

Source reference

Bartlett, Foster, and Telgarsky, Spectrally-normalized margin bounds for neural networks, Lemma 3.1 and Appendix A.5.

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

Margin generalization for a bounded spectral-complexity class

Statement

Assume the axiom of choice.

Fix a finite network architecture with $L \geq 1$ , widths $d_{0}, \dots, d_{L} \geq 1$ , output size $K = d_{L} \geq 2$ , activations, and reference matrices as in the spectral-network-complexity definition. Let $s_{i} > 0$ , $b_{i} \geq 0$ , and let $F$ be the nonempty class with layer constraints $∥ A_{i} ∥_{σ} \leq s_{i}$ and $∥ A_{i}^{⊤} - M_{i}^{⊤} ∥_{2, 1} \leq b_{i}$ . Let $S = ((x_{1}, y_{1}), \dots, (x_{n}, y_{n}))$ be an iid sample from any Borel probability measure on $R^{d_{0}} \times {1, \dots, K}$ , let $X$ be its input matrix with rows $x_{i}^{⊤}$ , and fix $n \geq 1$ , $γ > 0$ , and $0 < δ < 1$ . Set $W : = \max_{0 \leq i \leq L} d_{i}$ . With probability at least $1 - δ$ , every $F_{A} \in F$ satisfies $L_{0} (F_{A}) \leq {\hat{L}}_{γ, S} (F_{A}) + \frac{8}{n} + \frac{36 \sqrt{20} ∥ X ∥_{F} \sqrt{\log (2 W^{2})} \log n}{γ n} (\prod_{i = 1}^{L} ρ_{i} s_{i}) {(\sum_{i = 1}^{L} (b_{i} / s_{i})^{2 / 3})}^{3 / 2} + 3 \sqrt{\frac{\log (2 / δ)}{2 n}} .$ All logarithms are natural. The matrix norm on $X$ is the Frobenius norm, and the empirical margin loss uses the threshold convention $m_{F_{A}} (x_{i}, y_{i}) \leq γ$ .

Statement references

Multiclass margins, ramp loss, and empirical margin loss: defines population error, ramp loss, and empirical margin loss.

Spectral network complexity with reference matrices: fixes the architecture and mixed-norm/spectral-norm conventions.

Spectral and reference-matrix covering entropy for network outputs: bounds the proper Frobenius entropy of the sample score matrices.

A truncated covering integral bounds empirical Rademacher complexity: bounds empirical Rademacher complexity by a truncated covering integral.

Uniform margin-risk deviation from empirical Rademacher complexity: converts empirical loss-class complexity to a uniform margin-risk bound.

Facts & Assumptions

Given: The nonempty bounded layer class, iid sample, sample matrix, fixed positive margin, and confidence level in the Statement.

[F1]

For fixed sample inputs, the score matrices form the class covered in the output-entropy lemma, whose logarithmic covering bound has coefficient $5 ∥ X ∥_{F}^{2} \log (2 W^{2}) \prod_{i} (ρ_{i} s_{i})^{2} (\sum_{i} (b_{i} / s_{i})^{2 / 3})^{3}$ . Spectral and reference-matrix covering entropy for network outputs

[F2]

At a fixed example the margin is the true-label score minus the maximum competing score, and the ramp is the stated piecewise-linear function with breakpoints $- γ$ and $0$ . Multiclass margins, ramp loss, and empirical margin loss

[F3]

For any nonempty $[0, 1]$ -valued loss class on the fixed sample and $0 < α \leq \sqrt{n}$ , its one-sided empirical Rademacher complexity is bounded by the truncated proper-covering integral. A truncated covering integral bounds empirical Rademacher complexity

[F4]

Under the axiom of choice, with probability at least $1 - δ$ , the zero-one risk is bounded by the empirical margin loss, twice the loss-class empirical Rademacher complexity, and the stated confidence term. Uniform margin-risk deviation from empirical Rademacher complexity The Axiom of Choice

[F5]

The Frobenius norm is the Euclidean norm of all matrix entries. The Frobenius norm $∥ A ∥_{F} = (\sum_{i, j} ∣ a_{i j} ∣^{2})^{1 / 2}$ on real or complex matrices

[F6]

The natural logarithm is increasing and obeys its product law. The natural logarithm as the inverse of the exponential function Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm

Proof

1.1F2F5givenalgebraconstruct

Fix a realized sample and let $U_{X}$ be its set of score matrices. For score matrices $P, Q$ and example $(x_{i}, y_{i})$ , the true-label coordinate changes by at most $∥ P_{i \cdot} - Q_{i \cdot} ∥_{2}$ , and the maximum competing coordinate changes by at most the same amount, so [F2] gives margin change at most twice this row norm. On each linear piece of the ramp the absolute slope is either $0$ or $1 / γ$ ; the pieces meet continuously at $- γ$ and $0$ , so summing the changes over the at most three pieces between any two inputs proves $∣ ℓ_{γ} (a) - ℓ_{γ} (b) ∣ \leq ∣ a - b ∣ / γ$ . Thus the corresponding loss-vector distance is at most $(2 / γ) ∥ P - Q ∥_{F}$ . Mapping the centers of a proper $γ ϵ / 2$ -cover of $U_{X}$ to their loss vectors therefore gives a proper $ϵ$ -cover of the empirical loss-vector class.

2.1F1step 1.1givenalgebra

Apply [F1] at radius $γ ϵ / 2$ and use step 1.1. For every $ϵ > 0$ , $\log N_{F} (L_{γ} ∣ S, ϵ) \leq \frac{20 ∥ X ∥_{F}^{2} \log (2 W^{2})}{γ^{2} ϵ^{2}} (\prod_{i} (ρ_{i} s_{i})^{2}) {(\sum_{i} (b_{i} / s_{i})^{2 / 3})}^{3} = : \frac{K_{γ}}{ϵ^{2}} .$ Here $L_{γ} ∣ S$ is the set of vectors of ramp-loss values on the fixed sample.

3.1F3F6step 2.1givenalgebra

Use the truncated-integral bound [F3] with $α = 1 / n$ , which satisfies $0 < 1 / n \leq \sqrt{n}$ . From step 2.1, $\sqrt{\log N_{F} (L_{γ} ∣ S, ϵ)} \leq \sqrt{K_{γ}} / ϵ$ . Since $\int_{1 / n}^{\sqrt{n}} d ϵ / ϵ = \log (n \sqrt{n}) = \frac{3}{2} \log n$ , it follows that ${\hat{R}}_{S} (L_{γ}) \leq \frac{4}{n \sqrt{n}} + \frac{18 \sqrt{K_{γ}} \log n}{n} .$ When $n = 1$ the integral is zero and the same expression holds.

4.1F4F5step 3.1givenalgebra∎

Apply [F4] and substitute step 3.1. The term twice $4 / (n \sqrt{n})$ is at most $8 / n$ because $n \geq 1$ . Also $\sqrt{K_{γ}} = \sqrt{20} ∥ X ∥_{F} \sqrt{\log (2 W^{2})} γ^{- 1} (\prod_{i} ρ_{i} s_{i}) (\sum_{i} (b_{i} / s_{i})^{2 / 3})^{3 / 2}$ . This yields exactly the stated inequality.

Source reference

Bartlett, Foster, and Telgarsky, Spectrally-normalized margin bounds for neural networks, Theorem 1.1 and Appendix A.6.

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

A simultaneous spectral margin bound for multiclass networks

Statement

Assume the axiom of choice. Fix a network architecture with $L \geq 1$ , widths $d_{0}, \dots, d_{L} \geq 1$ , $K = d_{L} \geq 2$ , zero-bias recurrence and zero-origin $ρ_{i}$ -Lipschitz activations as in the spectral-network-complexity definition. Fix reference matrices $M_{i} \in R^{d_{i} \times d_{i - 1}}$ . Let $S = ((x_{1}, y_{1}), \dots, (x_{n}, y_{n}))$ be an iid sample of size $n \geq 1$ from any Borel probability measure on $R^{d_{0}} \times {1, \dots, K}$ , and let $X$ be the matrix with rows $x_{r}^{⊤}$ . Fix $0 < δ < 1$ and set $W : = \max_{0 \leq i \leq L} d_{i}$ . With probability at least $1 - δ$ , simultaneously for every network with nonzero layer matrices and every margin $γ > 0$ , $L_{0} (F_{A}) \leq {\hat{L}}_{γ, S} (F_{A}) + \frac{8}{n} + \frac{72 \sqrt{20} (1 + ∥ X ∥_{F}) \sqrt{\log (2 W^{2})} \log n}{γ n} (\prod_{i = 1}^{L} ρ_{i}) {(\sum_{i = 1}^{L} {[(\frac{1}{L} + ∥ A_{i}^{⊤} - M_{i}^{⊤} ∥_{2, 1}) \prod_{r \neq i} (\frac{1}{L} + ∥ A_{r} ∥_{σ})]}^{2 / 3})}^{3 / 2} + 3 \sqrt{\frac{Q (A, X, γ, n, δ)}{2 n}},$ where all logarithms are natural, an empty product equals $1$ , and $\begin{aligned} Q (A, X, γ, n, δ) : = & \log (6 / δ) + \log (2 + n γ) + \log (2 + n / γ) + 2 \log (2 + ∥ X ∥_{F}) \\ + 2 \sum_{i = 1}^{L} \log ⁣ (2 + L ∥ A_{i}^{⊤} - M_{i}^{⊤} ∥_{2, 1}) + 2 \sum_{i = 1}^{L} \log ⁣ (2 + L ∥ A_{i} ∥_{σ}) . \end{aligned}$

Statement references

Spectral network complexity with reference matrices: fixes the network recurrence, reference matrices, zero-origin activations, and layer norm conventions.

Multiclass margins, ramp loss, and empirical margin loss: defines population zero-one error and empirical margin loss.

Margin generalization for a bounded spectral-complexity class: supplies the fixed-margin bound for a class with fixed positive norm caps and reference-distance caps.

Identical distribution and IID families: defines the iid sampling assumption.

Facts & Assumptions

Given: The network architecture, fixed reference matrices, iid sample, confidence parameter, and axiom-of-choice assumption in the Statement.

[F1]

For fixed positive caps $s_{i}$ and nonnegative caps $b_{i}$ , every nonempty constrained network class has the fixed-margin bound with leading factor $36 \sqrt{20}$ and confidence term $3 \sqrt{\log (2 / η) / (2 n)}$ . Margin generalization for a bounded spectral-complexity class

[F2]

The architecture uses zero-origin Lipschitz activations, and the sample matrix Frobenius norm is the Euclidean norm of all its entries. Spectral network complexity with reference matrices The Frobenius norm $∥ A ∥_{F} = (\sum_{i, j} ∣ a_{i j} ∣^{2})^{1 / 2}$ on real or complex matrices

[F3]

The empirical margin loss is nondecreasing as a function of its positive threshold: if $0 < γ_{1} \leq γ_{2}$ , then ${\hat{L}}_{γ_{1}, S} (F) \leq {\hat{L}}_{γ_{2}, S} (F)$ . Multiclass margins, ramp loss, and empirical margin loss

[F4]

The product of finitely many at most countable sets is at most countable, and probability is countably subadditive. A product of two at most countable sets is at most countable Basic identities for a probability measure

[F5]

The natural logarithm is increasing and satisfies its product law. The natural logarithm as the inverse of the exponential function Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm

[F6]

The sample coordinates are independent and have the same distribution, as required by the fixed-margin result. Identical distribution and IID families

[F7]

The fixed-margin result assumes the axiom of choice through its McDiarmid supplier. The Axiom of Choice

Proof

1.1givenalgebra

For each integer $j \in Z$ , put $γ_{j} : = 2^{j} / n$ and $v_{j} : = 2^{- ∣ j ∣} / 3$ . Then $\sum_{j \in Z} v_{j} = (1 + 2 \sum_{m \geq 1} 2^{- m}) / 3 = 1$ , since $\sum_{m = 1}^{N} 2^{- m} = 1 - 2^{- N} \to 1$ . Every $γ > 0$ belongs to exactly one interval $[γ_{j}, 2 γ_{j})$ . For each positive integer $m$ , put $w_{m} : = 1 / (m (m + 1)) = 1 / m - 1 / (m + 1)$ ; the finite partial sum is $\sum_{m = 1}^{N} w_{m} = 1 - 1 / (N + 1)$ , so $\sum_{m \geq 1} w_{m} = 1$ .

2.1F1F4F6F7step 1.1givenconstruct

The integers are countable by the enumeration $0, 1, - 1, 2, - 2, \dots$ ; the other factors are positive integers, so repeated use of [F4] shows that the tuples indexed by $j \in Z$ , a positive integer $q$ , and positive integers $k_{i}, l_{i}$ for $1 \leq i \leq L$ form a countable set. For such a tuple set $η_{j, q, k, l} : = δ v_{j} w_{q} \prod_{i} w_{k_{i}} w_{l_{i}}$ . Let $J_{N} = {- N, \dots, N}$ and $M_{N} = {1, \dots, N}$ . Finite distributivity gives the sum over $J_{N} \times M_{N}^{1 + 2 L}$ as $δ (\sum_{j \in J_{N}} v_{j}) (\sum_{q \in M_{N}} w_{q}) \prod_{i} (\sum_{k_{i} \in M_{N}} w_{k_{i}}) (\sum_{l_{i} \in M_{N}} w_{l_{i}})$ , which tends to $δ$ by step 1.1. These finite boxes increase to the countable index set and contain every finite subset for large enough $N$ ; since all terms are nonnegative, their partial sums establish $\sum_{j, q, k, l} η_{j, q, k, l} = δ$ . For each tuple consider the layer class with caps $s_{i} = l_{i} / L$ and $b_{i} = k_{i} / L$ ; if it is empty its event is vacuous. Otherwise [F1] gives a fixed-margin result at $γ_{j}$ and confidence $η_{j, q, k, l}$ , with its displayed sample-norm term evaluated at the realized $X$ .

3.1F4step 2.1given

Apply countable subadditivity [F4] to the failure events from step 2.1. Their union has probability at most $\sum_{j, q, k, l} η_{j, q, k, l} = δ$ . Thus outside that union, all fixed-margin inequalities for every tuple hold simultaneously.

4.1F2F3step 1.1step 3.1givenconstruct

Fix any realized sample, any network with nonzero layer matrices, and any $γ > 0$ . Choose its unique $j$ from step 1.1 with $γ_{j} \leq γ < 2 γ_{j}$ , and set $q = ⌊ ∥ X ∥_{F} ⌋ + 1, k_{i} = ⌊ L ∥ A_{i}^{⊤} - M_{i}^{⊤} ∥_{2, 1} ⌋ + 1, l_{i} = ⌊ L ∥ A_{i} ∥_{σ} ⌋ + 1.$ These positive integers satisfy $∥ X ∥_{F} < q$ , $∥ A_{i}^{⊤} - M_{i}^{⊤} ∥_{2, 1} < k_{i} / L$ , and $0 < ∥ A_{i} ∥_{σ} < l_{i} / L$ . The network belongs to the corresponding constrained class. Also ${\hat{L}}_{γ_{j}, S} (F_{A}) \leq {\hat{L}}_{γ, S} (F_{A})$ by [F3], and $1 / (γ_{j} n) < 2 / (γ n)$ .

5.1F1F2step 4.1givenalgebra

In the leading term of [F1], the cap expression satisfies $(\prod_{i} s_{i}) {(\sum_{i} (b_{i} / s_{i})^{2 / 3})}^{3 / 2} = {(\sum_{i} {(b_{i} \prod_{r \neq i} s_{r})}^{2 / 3})}^{3 / 2} .$ For the tuple selected in step 4.1, $q \leq 1 + ∥ X ∥_{F}$ , $k_{i} / L \leq ∥ A_{i}^{⊤} - M_{i}^{⊤} ∥_{2, 1} + 1 / L$ , and $l_{i} / L \leq ∥ A_{i} ∥_{σ} + 1 / L$ . Monotonicity of the sums and products therefore bounds [F1]'s leading term by the leading term in the Statement, using $1 / (γ_{j} n) < 2 / (γ n)$ .

5.2F5step 1.1step 4.1givenalgebra

The confidence logarithm for this tuple equals $\log (2 / η_{j, q, k, l}) = \log (6 / δ) + ∣ j ∣ \log 2 + \log (q (q + 1)) + \sum_{i} (\log (k_{i} (k_{i} + 1)) + \log (l_{i} (l_{i} + 1))) .$ Put $t = n γ$ . If $j \geq 0$ , then $2^{j} \leq t$ and $∣ j ∣ \log 2 \leq \log (2 + t)$ . If $j < 0$ , then $t < 2^{j + 1} \leq 1$ , so $\log (2 + t) \geq \log 2$ and $\log (2 + 1 / t) \geq \log (1 / t)$ ; their sum is at least $\log (2 / t) > ∣ j ∣ \log 2$ . For each positive integer bin chosen as $m = ⌊ u ⌋ + 1$ , one has $m \leq u + 1$ and $m + 1 \leq u + 2$ , hence $\log (m (m + 1)) \leq 2 \log (u + 2)$ . Apply this with $u = ∥ X ∥_{F}$ and $u = L ∥ A_{i}^{⊤} - M_{i}^{⊤} ∥_{2, 1}$ or $L ∥ A_{i} ∥_{σ}$ . By [F5], the result is $\log (2 / η_{j, q, k, l}) \leq Q (A, X, γ, n, δ)$ .

6.1F1step 3.1step 4.1step 5.1step 5.2given∎

On the probability- $1 - δ$ event from step 3.1, apply the selected fixed-margin inequality. Steps 4.1–5.2 replace its empirical margin loss, leading term, and confidence term by the respective terms displayed in the Statement. The choices in step 4.1 were arbitrary, so this holds simultaneously for every network with nonzero layer matrices and every $γ > 0$ .

Source reference

Bartlett, Foster, and Telgarsky, Spectrally-normalized margin bounds for neural networks, Theorem 1.1 and Appendix A.7.

4 · Examples, counterexamples and false statements

None yet.