Spectrally normalized margin bounds

Theorem 3.4 (lower bound). With ReLU activations, scalar output and hidden widths at least 2, the Rademacher complexity of $\{F_A:\prod_i\|A_i\|_\sigma\le r\}$ on the sample is at least $c\,r\|X\|_2/n$. So the product of spectral norms cannot be removed, and the lower bound matches the scaling of the upper bound; the $(2,1)$ correction is left untested.

Reduce to covering the matrix of network outputs, with no cost in $k$. The Rademacher bound for the ramp loss gives $\Pr[\text{error}]\le\hat R_\gamma(f)+2\mathfrak R(\mathcal F_\gamma|_S)+3\sqrt{\ln(2/\delta)/(2n)}$, with $\mathcal F_\gamma$ the class of margin losses. The margin operator is 2-Lipschitz in $\ell_2$ and the ramp is $1/\gamma$-Lipschitz, so a Frobenius-norm cover of the $k\times n$ output matrix at scale $\gamma\epsilon/2$ covers that class at scale $\epsilon$. One cover of the whole output vector adds no factor of $k$, where bounding each output coordinate separately adds a factor $\sqrt k$.

One layer is covered by Maurey sparsification, at a cost free of dimension. For a data matrix $X\in\mathbb R^{n\times d}$ and weights $A\in\mathbb R^{d\times m}$, $$\ln\mathcal N\big(\{XA:\|A\|_{2,1}\le a\},\epsilon,\|\cdot\|_2\big)\le\Big\lceil\frac{a^2\|X\|_2^2}{\epsilon^2}\Big\rceil\ln(2dm).$$ After normalizing columns, $XA$ is $a\|X\|_2$ times a point in the convex hull of $2dm$ rank-one atoms of Frobenius norm at most 1. Maurey's lemma replaces that point by the average of $k=a^2\|X\|_2^2/\epsilon^2$ atoms sampled from its weights, and there are at most $(2dm)^k$ such averages, so $d$ and $m$ appear only inside the log. A Frobenius bound on $A$ would bring in an extra dimension factor, even for $X=I$.

Push an empirical cover through the layers, so errors grow by the spectral norms and log covers add. Covering the image of the sample instead of the parameters keeps the parameter count out. Let $X_i$ be layer $i$'s outputs on the sample and $\hat X_i$ a cover element. Cover $A_{i+1}\hat X_i$ with Step 2 and apply $\sigma_{i+1}$; the triangle inequality and the Lipschitz bounds give $$\|X_{i+1}-\hat X_{i+1}\|\le\rho_{i+1}\|A_{i+1}\|_\sigma\|X_i-\hat X_i\|+\rho_{i+1}\epsilon_{i+1},$$ so the output error is $\sum_j\epsilon_j\rho_j\prod_{l>j}\rho_l\|A_l\|_\sigma$, and since each layer's cover is chosen given the earlier ones, log covers add. Step 2 needs a norm bound on its input: because $\sigma_j(0)=0$ and the covers are proper (each cover element is itself the image of the sample under admissible weights), it is at most $\|X\|_2\prod_{j\lt i}\rho_j\|A_j\|_\sigma$. Centering the cover at $M_i$ does not change these bounds.

Budgeting the error across layers produces the spectral complexity. With $\|A_i\|_\sigma\le s_i$ and $\|A_i^\top-M_i^\top\|_{2,1}\le b_i$, layer $i$ costs a log cover of order $c_i/\epsilon_i^2$ while its error is amplified by the later spectral norms. Minimizing $\sum_ic_i/\epsilon_i^2$ under the linear error budget makes layer $i$'s share of the output error proportional to $(b_i/s_i)^{2/3}$, and the minimum is $$\ln\mathcal N\big(\{F_A(X^\top)\},\epsilon,\|\cdot\|_2\big)\le\frac{\|X\|_2^2\ln(2W^2)}{\epsilon^2}\Big(\prod_j\rho_j^2s_j^2\Big)\Big(\sum_i\Big(\frac{b_i}{s_i}\Big)^{2/3}\Big)^3,$$ that is $(\|X\|_2R_A/\epsilon)^2\ln(2W^2)$. The exponents $2/3$ and $3/2$ come from the solution of this allocation problem, and the product of spectral norms is how much an error at any layer can be amplified on the way to the output.

Dudley's entropy integral turns the cover into a Rademacher bound with one extra log factor. After the margin loss, $\ln\mathcal N(\epsilon)\le\mathcal R/\epsilon^2$ with $\sqrt{\mathcal R}=2\|X\|_2R_A\sqrt{\ln(2W^2)}/\gamma$, and the entropy integral, for the unnormalized $\ell_2$ data metric, gives $$\mathfrak R(\mathcal F_\gamma|_S)\le\inf_{\alpha\gt0}\Big(\frac{4\alpha}{\sqrt n}+\frac{12}{n}\int_\alpha^{\sqrt n}\frac{\sqrt{\mathcal R}}{\epsilon}\,d\epsilon\Big)=\inf_{\alpha\gt0}\Big(\frac{4\alpha}{\sqrt n}+\frac{12\sqrt{\mathcal R}}{n}\ln\frac{\sqrt n}\alpha\Big).$$ Entropy of order $1/\epsilon^2$ is Dudley's borderline case, where the integral diverges only logarithmically at 0, so $\alpha=1/n$ costs just a factor $\ln n$. This proves the bound for norm bounds and a margin fixed in advance.

A union bound over a grid makes it hold for every network and margin at once. The norms of the weights SGD returns depend on the sample. Divide the space of margins and norms into grid cells, apply Step 5 in each with failure probabilities summing to $\delta$, and use the smallest cell containing the network. The cost is logarithms of the norms and of $n/\gamma$, absorbed by the $\tilde O$.

The lower bound, by embedding linear predictors. Any linear function $x\mapsto\langle a,x\rangle$ with $\|a\|_2\le r$ is a ReLU network of the given depth with $\prod_i\|A_i\|_\sigma=2r$: split $\langle a,x\rangle$ into its positive and negative parts in the first layer, carry them through identity blocks, and output their difference. The linear class has Rademacher complexity at least $c\,r\|X\|_2/n$ by Khintchine-Kahane. (A separate remark explains why the product of norms appears instead of the norm of the product: with ReLUs, $\prod_iA_i=0$ need not give the zero function.)

On real and random labels, the normalized margins order problems by difficulty. The experiments plot the distribution of normalized margins $\mathcal M(F_A(x),y)/(R_A\|X\|_2/n)$, which controls the bound up to logs, for an AlexNet-like network trained with plain SGD and no regularization, with the same settings on every dataset (the figures use $\ell_1$ in place of $(2,1)$, a difference the paper reports as negligible). Raw margins look alike for true and random CIFAR10 labels; normalized, the random-label distribution sits far to the left, and MNIST far to the right of CIFAR10. Over training the product of spectral norms keeps growing after the excess risk levels off, while the margin-normalized version stays flat. These are qualitative comparisons: the paper reports no value of the bound, and Nagarajan and Kolter's evaluation on MNIST networks puts it far above 1.