Spectral network complexity with reference matrices

Let $L\ge 1$ and let $d_0,\dots ,d_L\ge 1$ be layer widths, with $K:=d_L\ge 2$ output classes. For each $i\in \{1,\dots ,L\}$, fix a matrix $M_i\in {\mathbb{R}}^{d_i\times d_{i-1}}$ and a vector activation ${\sigma }_i:{\mathbb{R}}^{d_i}\to {\mathbb{R}}^{d_i}$ satisfying ${\sigma }_i(0)=0$ and $\parallel {\sigma }_i(u)-{\sigma }_i(v){\parallel }_2\le {\rho }_i\parallel u-v{\parallel }_2(u,v\in {\mathbb{R}}^{d_i})$ for a fixed ${\rho }_i>0$. A network has matrices $A_i\in {\mathbb{R}}^{d_i\times d_{i-1}}$, no biases, and is evaluated by $h_0(x)=x$ and $h_i(x)={\sigma }_i(A_i{h}_{i-1}(x))$, with score vector $F_A(x)=h_L(x)$. For a real matrix $B$, define $\parallel B{\parallel }_{2,1}:={\sum }_j\parallel B_{\cdot j}{\parallel }_2$, the sum of the Euclidean norms of its columns. Write $\parallel A{\parallel }_{\sigma }$ for the induced Euclidean operator norm ${\max }_{\parallel u{\parallel }_2=1}\parallel Au{\parallel }_2$ and put $W:={\max }_{0\le i\le 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{\rho }_i\parallel A_i{\parallel }_{\sigma }){\left({\sum }_{i=1}^L{\left(\frac{\parallel A_i^{\mathrm{\top }}-M_i^{\mathrm{\top }}{\parallel }_{2,1}}{\parallel A_i{\parallel }_{\sigma }}\right)}^{2\mathrm{/}3}\right)}^{3\mathrm{/}2}\mathrm{.}$ 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\ge 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.

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.