TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedjudge pass (gpt-6-luna)

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.

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.

Depends on

Used by

Dependency tree · two levels

45 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Peter L. Bartlett, Dylan J. Foster, and Matus Telgarsky, Spectrally-normalized margin bounds for neural networks, Theorem 1.1 and Appendix A.7 (standard reference, not scraped)