Transformed Low-Rank Parameterization Can Help Robust Generalization for
  Tensor Neural Networks
Achieving efficient and robust multi-channel data learning is a challenging
task in data science. By exploiting low-rankness in the transformed domain,
i.e., transformed low-rankness, tensor Singular Value Decomposition (t-SVD) has
achieved extensive success in multi-channel data representation and has
recently been extended to function representation such as Neural Networks with
t-product layers (t-NNs). However, it still remains unclear how t-SVD
theoretically affects the learning behavior of t-NNs. This paper is the first
to answer this question by deriving the upper bounds of the generalization
error of both standard and adversarially trained t-NNs. It reveals that the
t-NNs compressed by exact transformed low-rank parameterization can achieve a
sharper adversarial generalization bound. In practice, although t-NNs rarely
have exactly transformed low-rank weights, our analysis further shows that by
adversarial training with gradient flow (GF), the over-parameterized t-NNs with
ReLU activations are trained with implicit regularization towards transformed
low-rank parameterization under certain conditions. We also establish
adversarial generalization bounds for t-NNs with approximately transformed
low-rank weights. Our analysis indicates that the transformed low-rank
parameterization can promisingly enhance robust generalization for t-NNs.
Andong Wang, Chao Li, Mingyuan Bai, Zhong Jin, Guoxu Zhou, Qibin Zhao
# Transformed Low-Rank Parameterization Can Help Robust Generalization for Tensor Neural Networks

###### Abstract

Achieving efficient and robust multi-channel data learning is a challenging task in data science. By exploiting low-rankness in the transformed domain, _i.e., transformed low-rankness_, tensor Singular Value Decomposition (t-SVD) has achieved extensive success in multi-channel data representation and has recently been extended to function representation such as Neural Networks with t-product layers (t-NNs). However, it still remains unclear how t-SVD theoretically affects the learning behavior of t-NNs. This paper is the first to answer this question by deriving the upper bounds of the generalization error of both standard and adversarially trained t-NNs. It reveals that the t-NNs compressed by exact transformed low-rank parameterization can achieve a sharper adversarial generalization bound. In practice, although t-NNs rarely have exactly transformed low-rank weights, our analysis further shows that by adversarial training with gradient flow (GF), the over-parameterized t-NNs with ReLU activations are trained with implicit regularization towards transformed low-rank parameterization under certain conditions. We also establish adversarial generalization bounds for t-NNs with approximately transformed low-rank weights. Our analysis indicates that the transformed low-rank parameterization can promisingly enhance robust generalization for t-NNs.

T 1-55, 2023 Under Review

Tensor SVD, deep neural networks, adversarial generalization error, implicit bias

## 1 Introduction

_Multi-channel learning_ (MCL) is a task to extract representations from the data with multiple channels, such as multispectral images, time series, and multi-view videos, in an efficient and robust manner (Liu et al., 2020; Hou et al., 2021; Zhang and Ng, 2021, 2022). Among methods tackling this task, _tensor neural networks_ (t-NNs) came to stage recently (Newman et al., 2018; Malik et al., 2021; Wu et al., 2022). Their t-product (Kilmer et al., 2013) layers distinguish them from the other networks. Compared with other methods, t-NNs demonstrate effectiveness and robustness when handling multi-channel learning tasks (Newman et al., 2018; Malik et al., 2021; Wu et al., 2022). The intuition is that, as each channel of the data has a different physical attribute (like multispectral
data), one usually needs to extract a few features for each channel individually. The t-product-based layers give a fixed channel number, which is equal to the number of the input channel, in different layers, such that changes in individual channels can be explicitly captured in the representation learning phase.

In substance, the key of t-product layers is tensor decomposition, especially tensor singular value decomposition (_t-SVD_) (Liu et al., 2020; Lu et al., 2019; Hou et al., 2021; Zhang and Ng, 2021, 2022; Qiu et al., 2022). For t-SVD, a tensor can be decomposed into a t-product of factors following a linear transformation. Unlike the classic tensor decomposition methods, t-SVD explores the low-rank structure of a tensor in the transformed domain, _i.e._, the _transformed low-rankness_. The imposed transformation is preserved in the t-product layers, providing additional expressivity for the neural networks. Meanwhile, the controllable transformed low-rank structure gives us more flexibility for balancing the model accuracy and adversarial robustness (Wu et al., 2022). However, the learning behavior of t-NN (the stack of t-product layers) remains lacking in the systematically theoretical analysis. More importantly, the additional transformation in the model makes the theoretical analysis more technically challenging compared to the existing work on general neural networks (Neyshabur et al., 2015; Xiao et al., 2022; Lv and Zhu, 2022; Suzuki et al., 2020).

To this end, we conduct a thorough investigation on the learning behavior of t-NN, addressing the following fundamentally important questions:

* _Q1:Can we theoretically characterize the generalization behavior of t-NNs?_ Yes. We derive the upper bound of the generalization gaps for t-NNs under both standard training and adversarial training in Sec. 3, and achieve sharp bounds on the adversarial generalization gap in Sec. 4.1.
* _Q2: How does transformed low-rankness theoretically influence the efficiency of adversarial learning for t-NN?_ We analyze the adversarial generalization gap of t-NNs whose weight tensors are of transformed low-rankness in Sec. 4.1.
* _Q3: How does adversarial learning of t-NNs affect transformed rank of their weight tensors?_ In Sec. 4.2, we deduce that weight tensors tend to be approximately of transformed low-rankness in adversarially trained highly over-parameterized t-NNs with ReLU activations, using GF.
* _Q4: How is adversarial generalization impacted by approximately transformed low-rank weight tensor in t-NNs?_ In Sec. 4.3, we derive adversarial generalization bounds for t-NNs with approximately transformed low-rank weight tensors in both general cases and a special case where weight tensors have certain patterns of spectral decay in the transformed domain.

## 2 Notations and Preliminaries

In this section, we introduce the notations and give a quick review of t-SVD which plays a central role in the following analysis.

### Notations

We use lowercase, lowercase boldface, and uppercase boldface letters to denote scalars, _e.g._, \(a\in\mathbb{R}\), vectors _e.g._, \(\mathbf{a}\in\mathbb{R}^{m}\), and matrices, _e.g._, \(\mathbf{A}\in\mathbb{R}^{m\times n}\), respectively. Following the standard notations
in (Kilmer et al., 2013), a 3-way tensor of size \(d\times 1\times\mathsf{c}\) is also called a _t-vector_ and denoted by underlined lowercase, _e.g._, \(\underline{\mathbf{x}}\), whereas a 3-way tensor of size \(m\times n\times\mathsf{c}\) is also called a _t-matrix_ and denoted by underlined uppercase, _e.g._, \(\underline{\mathbf{X}}\). We use a t-vector \(\underline{\mathbf{x}}\in\mathbb{R}^{d\times 1\times\mathsf{c}}\) to represent a multi-channel example, where \(\mathsf{c}\) denotes the number of channels and \(d\) is the number of features for each channel.

Given a matrix \(\mathbf{\Lambda}\in\mathbb{R}^{m\times n}\), its Frobenius norm (F-norm) and spectral norm are defined as \(\left\|\mathbf{A}\right\|_{\mathrm{F}}:=\sqrt{\sum_{i=1}^{\min\{m,n\}}\sigma_{ i}^{2}}\) and \(\left\|\mathbf{A}\right\|:=\max_{i}\sigma_{i}\), respectively, where \(\sigma_{i},\,i=1,\cdots,\min\{m,n\}\) are its singular values. The _stable rank_ of a non-zero matrix \(\mathbf{A}\) is defined as the squared ratio of its F-norm and spectral norm \(r_{\mathsf{stb}}(\mathbf{A}):=\left\|\mathbf{A}\right\|_{\mathrm{F}}^{2}/ \left\|\mathbf{A}\right\|^{2}\). Given a tensor \(\underline{\mathbf{T}}\), define its \(l_{p}\)-norm and F-norm respectively as \(\left\|\underline{\mathbf{T}}\right\|_{l_{p}}:=\left\|\mathtt{vec}( \underline{\mathbf{T}})\right\|_{l_{p}}\), and \(\left\|\underline{\mathbf{T}}\right\|_{\mathrm{F}}:=\left\|\mathtt{vec}( \underline{\mathbf{T}})\right\|_{2}\), where \(\mathtt{vec}(\cdot)\) denotes the vectorization operation of a tensor (Kolda and Bader, 2009). Given \(\underline{\mathbf{T}}\in\mathbb{R}^{m\times n\times\mathsf{c}}\), let \(\underline{\mathbf{T}}_{\cdot,i}\) denotes its \(i\)th frontal slice. The inner product between two tensors \(\underline{\mathbf{\Lambda}},\underline{\mathbf{B}}\) is defined as \(\left\langle\underline{\mathbf{\Lambda}},\underline{\mathbf{B}}\right\rangle: =\mathtt{vec}(\underline{\mathbf{\Lambda}})^{\top}\mathtt{vec}(\underline{ \mathbf{B}}).\) The frontal-slice-wise product of two tensors \(\underline{\mathbf{\Lambda}},\underline{\mathbf{B}}\), denoted by \(\underline{\mathbf{\Lambda}}\odot\underline{\mathbf{B}}\), equals a tensor \(\underline{\mathbf{T}}\) such that \(\underline{\mathbf{T}}_{\cdot,i}=\underline{\mathbf{\Lambda}}_{\cdot,i} \underline{\mathbf{B}}_{\cdot,i},\,\,\forall i=1,\cdots,\mathsf{c}\)(Kilmer et al., 2013). We use \(|\cdot|\) as the absolute value for a scalar and cardinality for a set. Other notations are introduced at their first appearance.

### Tensor Singular Value Decomposition

The framework of tensor singular value decomposition (t-SVD) is based on the t-product under an invertible linear transform \(M\)(Kernfeld et al., 2015). In recent studies, the transformation matrix \(\mathbf{M}\) defining the transform \(M\) is _restricted to be orthogonal_(Wang et al., 2021) for better properties, which is also followed in this paper. Given any _orthogonal matrix1\(\mathbf{M}\in\mathbb{R}^{\mathsf{c}\times\mathsf{c}}\)_, define the associated linear transform \(M(\cdot)\) with its inverse \(M^{-1}(\cdot)\) on any \(\underline{\mathbf{T}}\in\mathbb{R}^{m\times n\times\mathsf{c}}\) as

Footnote 1: Following (Newman et al., 2018), we restrict \(\mathbf{M}\) to be orthogonal for simplicity.

\[M(\underline{\mathbf{T}}):=\underline{\mathbf{T}}\times_{3}\mathbf{M},\,\,\, \text{and}\,\,\,\,\,\,M^{-1}(\underline{\mathbf{T}}):=\underline{\mathbf{T}} \times_{3}\mathbf{M}^{-1}, \tag{1}\]

where \(\times_{3}\) denotes the tensor matrix product on mode-\(3\)(Kernfeld et al., 2015).

**Definition 1** (t-product (Kernfeld et al., 2015)): _The t-product of any \(\underline{\mathbf{\Lambda}}\in\mathbb{R}^{m\times n\times\mathsf{c}}\) and \(\underline{\mathbf{B}}\in\mathbb{R}^{n\times k\times\mathsf{c}}\) under the invertible linear transform \(M\) in Eq. (1) is denoted and defined as \(\underline{\mathbf{\Lambda}}*_{M}\underline{\mathbf{B}}=\underline{\mathbf{C} }\in\mathbb{R}^{m\times k\times\mathsf{c}}\) such that \(M(\underline{\mathbf{C}})=M(\underline{\mathbf{\Lambda}})\odot M(\underline{ \mathbf{B}})\)._

**Definition 2** (\(M\)-block-diagonal matrix): _The \(M\)-block-diagonal matrix of any \(\underline{\mathbf{T}}\in\mathbb{R}^{m\times n\times\mathsf{c}}\), denoted by \(\widetilde{\mathbf{T}}_{M}\), is the block diagonal matrix whose diagonal blocks are the frontal slices of \(M(\underline{\mathbf{T}})\):_

\[\widetilde{\mathbf{T}}_{M}:=\mathtt{bdiag}(M(\underline{\mathbf{T}})):= \begin{bmatrix}M(\underline{\mathbf{T}})_{\cdot,\cdot,1}&&\\ &M(\underline{\mathbf{T}})_{\cdot,\cdot,2}&&\\ &&\ddots&\\ &&M(\underline{\mathbf{T}})_{\cdot,\cdot,\mathsf{c}}\end{bmatrix}\in\mathbb{R}^{m \mathsf{c}\times n\mathsf{c}}.\]

In this paper, we also follow the definition of t-transpose, t-identity tensor, t-orthogonal tensor, and f-diagonal tensor given by Kernfeld et al. (2015), and thus the t-SVD is introduced as follows.

**Definition 3** (t-SVD, tubal rank (Kernfeld et al., 2015)): _Tensor Singular Value Decomposition (t-SVD) of \(\underline{\mathbf{T}}\in\mathbb{R}^{m\times n\times\mathsf{c}}\) under the invertible linear transform \(M\) in Eq. (1) is given as follows_

\[\underline{\mathbf{T}}=\underline{\mathbf{U}}*_{M}\underline{\mathbf{S}}*_{M} \underline{\mathbf{V}}^{\top}, \tag{2}\]
_where \(\underline{\mathbf{U}}\in\mathbb{R}^{m\times m\times\mathsf{c}}\) and \(\underline{\mathbf{V}}\in\mathbb{R}^{n\times n\times\mathsf{c}}\) are t-orthogonal, and \(\underline{\mathbf{S}}\in\mathbb{R}^{m\times n\times\mathsf{c}}\) is f-diagonal._

_The tubal rank of \(\underline{\mathbf{T}}\in\mathbb{R}^{m\times n\times\mathsf{c}}\) is defined as the number of non-zero tubes of \(\underline{\mathbf{S}}\) in its t-SVD in Eq. (2), i.e., \(r_{\text{t}}(\underline{\mathbf{T}}):=|\{i\mid\underline{\mathbf{S}}(i,i,:) \neq\mathbf{0},i\leq\min\{m,n\}\}|\)._

For any \(\underline{\mathbf{T}}\in\mathbb{R}^{m\times n\times\mathsf{c}}\) with the tubal rank \(r_{\text{t}}(\underline{\mathbf{T}})\), we have following relationship between its t-SVD and the matrix SVD of its \(M\)-block-diagonal matrix (Wang et al., 2021; Lu, 2021):

\[\underline{\mathbf{T}}=\underline{\mathbf{U}}*_{M}\underline{\mathbf{S}}*_{M }\underline{\mathbf{V}}^{\top}\;\Leftrightarrow\;\widetilde{\mathbf{T}}_{M}= \widetilde{\mathbf{U}}_{M}\cdot\widetilde{\mathbf{S}}_{M}\cdot\widetilde{ \mathbf{V}}_{M}^{\top},\quad\text{and}\qquad\mathsf{cr}_{\text{t}}(\underline {\mathbf{T}})\geq\text{rank}(\widetilde{\mathbf{T}}_{M}). \tag{3}\]

As the \(M\)-block-diagonal matrix \(\widetilde{\mathbf{T}}_{M}\) is defined after transforming tensor \(\underline{\mathbf{T}}\) from the original domain to the transformed domain, the relationship \(\mathsf{cr}_{\text{t}}(\underline{\mathbf{T}})\geq\text{rank}(\widetilde{ \mathbf{T}}_{M})\) indicates that the tubal rank can be chosen as a measure of transformed low-rankness (Wang et al., 2021; Lu, 2021).

## 3 Neural Networks with t-Product Layer

In this section, we formulate the t-product layer used in t-NNs, and then rigorously prove the standard and adversarial generalization bound for t-NNs.

### Multi-Channel Feature Learning via t-Product

Suppose a multi-channel example as a t-vector \(\underline{\mathbf{x}}\in\mathbb{R}^{d\times 1\times\mathsf{c}}\) where \(\mathsf{c}\) is the number of channels, and \(d\) is the number of features. An \(L\)-layer t-NN feature extractor \(\mathbf{f}(\underline{\mathbf{x}})\) extracts \(d_{L}\) features for each channel of \(\underline{\mathbf{x}}\) as follows

\[\mathbf{f}(\underline{\mathbf{x}})=\mathbf{f}^{(L)}(\underline{\mathbf{x}}); \quad\mathbf{f}^{(l)}(\underline{\mathbf{x}})=\sigma(\underline{\mathbf{W}}^ {(l)}*_{M}\mathbf{f}^{(l-1)}(\underline{\mathbf{x}})),\;\forall l=1,\cdots,L; \quad\mathbf{f}^{(0)}(\underline{\mathbf{x}})=\underline{\mathbf{x}} \tag{4}\]

where the \(l\)-th layer \(\mathbf{f}^{(l)}\) first conduct t-product with weight tensor (t-matrix) \(\underline{\mathbf{W}}^{(l)}\in\mathbb{R}^{d_{l}\times d_{l-1}\times\mathsf{c}}\) on the output of the \((l-1)\)-th layer as multi-channel features2\(\mathbf{f}^{(l-1)}(\underline{\mathbf{x}})\in\mathbb{R}^{d_{l-1}\times 1\times \mathsf{c}}\) to obtain a (\(d_{l}\times 1\times\mathsf{c}\))-dimensional representation and then use the entry-wisely ReLU3 the activation \(\sigma(x)=\max\{x,0\}\) for nonlinearity.

Footnote 2: For simplicity, let \(d_{0}=d\) by treating the input example \(\underline{\mathbf{x}}\) as the \(0\)-th layer \(\mathbf{f}^{(0)}\).

Footnote 3: Although we consider ReLU activation in this paper, most of the main theoretical results (e.g., Theorems 7, 9, 11, 19 and 21) can be generalized to general Lipschitz activations with slight modifications in the proof.

**Remark 4**: _Unlike Newman et al. (2018), Malik et al. (2021) and Wu et al. (2022) whose nonlinear activation is performed in the transformed domain, the t-NN model in Eq. (4) considers the nonlinear activation in the original domain and hence is consistent with traditional neural networks._

By adding a linear classification module of weight \(\mathbf{w}\in\mathbb{R}^{cd_{L}}\) after the feature reaction module in Eq. (4), we consider the following t-NN predictor whose sign can be utilized for binary classification:

\[f(\underline{\mathbf{x}};\underline{\mathbf{W}}):=\mathbf{w}^{\top}\mbox{ \tt vec}(\mathbf{f}^{(L)}(\underline{\mathbf{x}}))\in\mathbb{R}. \tag{5}\]

Let \(\underline{\mathbf{W}}:=\{\underline{\mathbf{W}}^{(1)},\cdots,\underline{ \mathbf{W}}^{(L)},\mathbf{w}\}^{4}\) denote the collection of all the weights. With a slight abuse of notations, let \(\left\|\underline{\mathbf{W}}\right\|_{\text{F}}:=\sqrt{\left\|\mathbf{w} \right\|_{2}^{2}+\sum_{l=1}^{L}\left\|\underline{\mathbf{W}}^{(l)}\right\|_{ \text{F}}^{2}}\) denote the sum of Euclidean norms of all the weights.
The function class of t-NNs whose weights are bounded in the Euclidean norm is defined as

\[\mathfrak{F}:=\bigg{\{}f(\mathbf{x};\underline{\mathbf{W}})\ \ \ \Big{|}\ \| \mathbf{w}\|_{2}\leq B_{w},\quad\Big{\|}\underline{\mathbf{W}}^{(l)}\Big{\|}_{ \mathbf{F}}\leq B_{l},\quad\forall l=1,\cdots,L\bigg{\}}. \tag{6}\]

Let \(B_{\underline{\mathbf{W}}}:=B_{w}\prod_{j=1}^{L}B_{j}\) for simplicity. The goal is to train a t-NN predictor \(f\in\mathfrak{F}\) on the training sample set \(S\) to achieve high classification accuracy for any new multi-channel example \(\underline{\mathbf{x}}\) drawn from the unknown data distribution \(P_{\underline{\mathbf{x}}}\).

### Generalization Bounds for t-NNs

Suppose we are given a training multi-channel dataset \(S\) consisting of \(N\) example-label pairs \((\underline{\mathbf{x}}_{i},y_{i})\in\mathbb{R}^{d\times 1\times c}\times\{\pm 1\}\), \(i=1,\cdots,N\), which are _i.i.d._ drawn from an underlying data distribution \(P_{\underline{\mathbf{x}},y}\). The following assumption is made on the input multi-channel data.

**Assumption 5**: _All the input example \(\underline{\mathbf{x}}\in\mathbb{R}^{d\times 1\times c}\) has the upper bounded F-norm, i.e., \(\|\underline{\mathbf{x}}\|_{\mathbf{F}}\leq B_{x}\)._

When a loss function \(\ell(f(\underline{\mathbf{x}}_{i}),y_{i})\) is considered as the measure of classification quality, we define the empirical and population risk for any predictor \(f\in\mathfrak{F}\)

\[\hat{\mathcal{L}}(f):=\frac{1}{N}\sum_{i=1}^{N}\ell(f(\underline{\mathbf{x}}_ {i}),y_{i}),\quad\mathcal{L}(f):=\mathbb{E}_{P(\underline{\mathbf{x}},y)}\left[ \ell(f(\underline{\mathbf{x}}),y)\right], \tag{7}\]

respectively. Similar to (Lyu and Li, 2020), we also make additional assumptions as follows on the loss function.

**Assumption 6**: _For any t-NN predictor \(h\in\mathfrak{F}\), the loss function \(\ell(h(\underline{\mathbf{x}}),y)\) can be expressed as \(\ell(h(\underline{\mathbf{x}}),y)=\exp(-\mathfrak{f}(yh(\underline{\mathbf{x }}))\) such that: **(A.1)** The range of loss \(\ell(\cdot,\cdot)\) is \([0,B]\). **(A.2) \(\mathfrak{f}:\mathbb{R}\to\mathbb{R}\)** is \(C^{1}\)-smooth; **(A.3) \(\mathfrak{f}^{\prime}(x)\geq 0\)** for all \(x\in\mathbb{R}\); **(A.4)** there exists \(b_{\mathfrak{f}}\geq 0\) such that \(x\mathfrak{f}^{\prime}(x)\) is non-decreasing for \(x\in(b_{\mathfrak{f}},+\infty)\), and the derivative \(x\mathfrak{f}^{\prime}(x)\to+\infty\) as \(x\to+\infty\); **(A.5)** let \(\mathfrak{g}:[\mathfrak{f}(b_{\mathfrak{f}}),+\infty)\to[b_{\mathfrak{f}},+\infty)\) be the inverse function of \(\mathfrak{f}\) on the domain \([b_{\mathfrak{f}},+\infty)\). There exist \(b_{\mathfrak{g}}\geq\max\{2\mathfrak{f}(b_{\mathfrak{f}},\mathfrak{f}(2b_{ \mathfrak{f}}))\}\) and \(K\geq 1\), such that \(\mathfrak{g}^{\prime}(x)\leq K\mathfrak{g}^{\prime}(\theta x)\) and \(\mathfrak{f}^{\prime}(y)\leq K\mathfrak{f}^{\prime}(\theta y)\) for all \(x\in(b_{\mathfrak{g}},+\infty),y\in(\mathfrak{g}(b_{\mathfrak{g}}),+\infty)\) and \(\theta\in[1/2,1)\)._

Assumption **(A.1)** is a natural assumption in generalization analysis (Yin et al., 2019; Awasthi et al., 2020), and Assumptions **(A.2)-(A.5)** are the same as Assumption (B3) in Lyu and Li (2020). According to Assumption **(A.2)**, the loss function \(\ell(\cdot,\cdot)\) satisfies the \(L_{\ell}\)-Lipschitz continuity

\[|\ell(h(\underline{\mathbf{x}}_{1}),y_{1})-\ell(h(\underline{\mathbf{x}}_{2}),y_{2})|\leq L_{\ell}|y_{1}h(\underline{\mathbf{x}}_{1})-y_{2}(\underline{ \mathbf{x}}_{2})|,\quad\text{with }L_{\ell}=\sup_{|q|\leq B_{\tilde{f}}} \mathfrak{f}^{\prime}(q)e^{-\mathfrak{f}(q)}, \tag{8}\]

where \(B_{\tilde{f}}\) is an upper bound on the output of any t-NN \(h\in\mathfrak{F}\). The Lipschitz continuity is also widely assumed for generalization analysis of DNNs (Yin et al., 2019; Xiao et al., 2022). Assumption 6 is satisfied by commonly used loss functions such as the logistic loss and the exponential loss.

The generalization gap \(\mathcal{L}(f)-\hat{\mathcal{L}}(f)\) of any functions \(f\in\mathfrak{F}\) can be bounded as follows.

**Lemma 7** (Generalization bound for t-NNs): _Under Assumptions 5 and 6, it holds with probability at least \(1-2e^{-t}\) for any \(t>0\) that for any \(f\in\mathfrak{F}\), its generalization error satisfies_

\[\mathcal{L}(f)-\hat{\mathcal{L}}(f)\leq\frac{L_{\ell}B_{x}B_{\underline{\mathbf{ W}}}}{\sqrt{N}}(\sqrt{2\log(2)d}+1)+3B\sqrt{\frac{t}{2N}}. \tag{9}\]
### Adversarial Generalization Bounds for t-NNs

We consider the adversarial generalization behavior of t-NNs in this subsection. We first make the following assumption on the adversarial perturbations.

**Assumption 8**: _Given an input example \(\underline{\mathbf{x}}\), the adversarial perturbation is chosen within a radius-\(\xi\) ball of norm \(R_{\mathsf{a}}(\cdot)\) whose compatibility constant with the Euclidean norm is given as \(\mathsf{C}_{R_{\mathsf{a}}}=\sup_{\underline{\mathbf{x}}\neq\bullet}R_{\mathsf{ a}}(\underline{\mathbf{x}})/\left\|\underline{\mathbf{x}}\right\|_{\mathrm{F}}\)._

The assumption allows for much broader adversary classes than the commonly considered \(l_{p}\)-attacks (Xia and Yuan, 2017; Xiao et al., 2022). For example, if one treats the multi-channel data \(\underline{\mathbf{x}}\in\mathbb{R}^{d\times 1\times\mathsf{c}}\) as a matrix of dimensionality \(d\times\mathsf{c}\) and attacks it with nuclear norm attacks (Kazemi et al., 2020), then the constant \(\mathsf{C}_{R_{\mathsf{a}}}=\sqrt{\min\{d,\mathsf{c}\}}\).

Given an example-label pair \((\underline{\mathbf{x}},y)\), the adversarial loss function for any predictor \(f\) is defined as \(\tilde{\ell}(f(\underline{\mathbf{x}}),y)=\max_{R_{\mathsf{a}}(\underline{ \mathbf{x}}^{\prime}-\underline{\mathbf{x}})\leq\epsilon}\ell(f(\underline{ \mathbf{x}}^{\prime}),y)\). The empirical and population adversarial risks are thus defined as

\[\hat{\mathcal{L}}^{\mathrm{adv}}(f)=\frac{1}{N}\sum_{i=1}^{N}\tilde{\ell}(f( \underline{\mathbf{x}}_{i}),y_{i}),\quad\mathcal{L}^{\mathrm{adv}}(f)=\mathbb{ E}_{(\underline{\mathbf{x}},y)}\left[\tilde{\ell}(f(\underline{\mathbf{x}}),y) \right],\]

respectively. The adversarial generalization performance is measured by the adversarial generalization gap (AGP) defined as \(\mathcal{L}^{\mathrm{adv}}(f)-\hat{\mathcal{L}}^{\mathrm{adv}}(f)\). Let \(B_{\tilde{f}}:=(B_{x}+\xi\mathsf{C}_{R_{\mathsf{a}}})B_{\underline{\mathbf{W} }}\) for simplicity. For any t-NN \(f\in\mathfrak{F}\), its AGP is bounded as follows.

**Theorem 9** (Adversarial generalization bound for t-NNs): _Under Assumptions 5 and 6, it holds with probability at least \(1-2e^{-t}\)\((\forall t>0)\), that for any \(f\in\mathfrak{F}\), its adversarial generalization gap satisfies_

\[\mathcal{L}^{\mathrm{adv}}(f)-\hat{\mathcal{L}}^{\mathrm{adv}}(f)\leq \frac{CL_{\ell}B_{\tilde{f}}}{\sqrt{N}}\sqrt{\mathsf{c}\sum_{l=1} ^{L}d_{l-1}d_{l}\log(3(L+1))}+3B\sqrt{\frac{t}{2N}}. \tag{10}\]

**Remark 10**: _When the input example has channel number \(\mathsf{c}=1\) and the attacker uses \(l_{p}\)-attack, the adversarial generalization bound in Theorem 9 denegerates to Theorem 4 in Xiao et al. (2022)._

## 4 Transformed Low-rank Parameterization for t-NNs

### Generalization Bound under Exact Transformed Low-rank Parameterization

According to the adversarial generalization error bound for t-NNs in Theorem 9, one can find that the bound scales like \(O(\sqrt{\mathsf{c}(\sum_{l=1}^{L}d_{l-1}d_{l})/N})\) in the square root of the parameter complexity which may require a large number of training examples \(N\) to achieve an expected adversarial accuracy. In addition, high parameter complexity results in the high energy/storage/timing costs when deploying the modern large-scale DNN models in the field, especially on resource-constrained embedded and mobile devices.

To this end, we propose a transformed low-rank parameterization scheme to compress the original hypothesis set. Specifically, given a vector of pre-set ranks \(\mathbf{r}=(r_{1},\cdots,r_{L})^{\top}\in\mathbb{R}^{L}\) where \(r_{l}\leq\{d_{l},d_{l-1}\}\), we consider the following subset of the original t-NNs:

\[\mathfrak{F}_{\mathbf{r}}:=\bigg{\{}f\biggm{|}f\in\mathfrak{F},\text{and }r_{t}(\underline{\mathbf{W}}^{(l)})\leq r_{l},\forall l=1,\cdots,L\bigg{\}}. \tag{11}\]
In the function set \(\mathfrak{F}_{\mathbf{r}}\), the weight tensor \(\underline{\mathbf{W}}^{(l)}\) of the \(l\)-th layer has upper bounded tubal rank, which means low-rankness in the transformed domain5. We bound the adversarial behavior for any function \(f\in\mathfrak{F}_{\mathbf{r}}\) as follows.

Footnote 5: For real implementations, one can adopt similar rank learning straregety to (Idelbayev and Carreira-Perpinan, 2020) to select a suitable rank parameter \(\mathbf{r}\). Due to the scope of this paper, we leave this for future work.

**Theorem 11** (Adversarial generalization bound for t-NNs with transformed low-rank weights): _Under Assumptions 5 and 6, it holds with probability at least \(1-2e^{-t},\,\forall t>0\), that for any \(f_{\mathbf{r}}\in\mathfrak{F}_{\mathbf{r}}\), its adversarial generalization error satisfies_

\[\mathcal{L}^{\text{adv}}(f_{\mathbf{r}})-\hat{\mathcal{L}}^{\text{adv}}(f_{ \mathbf{r}})\leq\frac{C^{\prime}L_{\ell}B_{\tilde{f}}}{\sqrt{N}}\sqrt{\text{ c}\sum_{l=1}^{L}r_{l}(d_{l-1}+d_{l})\log(9(L+1))}+3B\sqrt{\frac{t}{2N}}. \tag{12}\]

Comparing Theorem 11 with Theorem 9, it can be seen that the adversarial generalization bound under transformed low-rank parameterization has a better scaling \(O(\sqrt{\text{c}\sum_{l=1}^{L}r_{l}(d_{l-1}+d_{l})/N})\), which indicates a smaller number of training examples are needed and a more efficient adversarial training process can be achieved.

### Implicit Bias of Gradient Flow in Adversarial Learning of t-NNs

Although Theorem 11 shows exactly transformed low-rank parameterization leads to lower bounds, the well trained t-NNs on real dataset rarely have exactly transformed low-rank weights. In this section, we will prove that the highly overparameterized t-NNs, trained by adversarial training with gradient flow (GF), are of approximate transformed low-rank parameterized under certain conditions.

The proposed t-NN \(f(\underline{\mathbf{x}};\underline{\mathbf{W}})\) is said to satisfy the (positively) _homogeneous_ as the following condition holds: \(f(\underline{\mathbf{x}};a\underline{\mathbf{W}})=a^{L+1}f(\underline{ \mathbf{x}};\underline{\mathbf{W}})\) for any positive constant \(a\). Motivated by (Lv and Zhu, 2022), we focus on the scale invariant adversarial perturbations defined as follows.

**Definition 12** (Scale invariant adversarial perturbation, Lv and Zhu 2022): _An adversarial perturbation is said to be a scale invariant adversarial perturbation for \(f(\underline{\mathbf{x}};a\underline{\mathbf{W}})\) if it satisfies \(\underline{\boldsymbol{\delta}}_{i}(a\underline{\mathbf{W}})=\underline{ \boldsymbol{\delta}}_{i}(\underline{\mathbf{W}}),\) for any positive constant \(a\)._

**Lemma 13**: _The \(l_{2}\)-FGM (Miyato et al., 2017), FGSM (Goodfellow et al., 2015), \(l_{2}\)-PGD and \(l_{\infty}\)-PGD (Madry et al., 2018) perturbations for the t-NNs are all scale invariant._

Gradient flow can be seen as gradient descent with infinitesimal step size. For gradient flow, the ReLU t-NNs are locally Lipschitz, and thus we can use GF to train ReLU t-NNs. When using GF for the ReLU t-NNs, \(\underline{\mathbf{W}}\) changes continuously with time, and the trajectory of parameter \(\underline{\mathbf{W}}\) during training is an arc \(\underline{\mathbf{W}}:[0,\infty)\rightarrow\mathbb{R}^{\text{dim}( \underline{\mathbf{W}})},t\mapsto\underline{\mathbf{W}}(t)\) that satisfies the differential inclusion (Dutta et al., 2013; Lyu and Li, 2020)

\[\frac{\text{d}\underline{\mathbf{W}}(t)}{\text{d}t}\in-\partial^{\circ}\hat{ \mathcal{L}}^{\text{adv}}(\underline{\mathbf{W}}(t)) \tag{13}\]

for _a. e._\(t\geq 0\), where \(\partial^{\circ}\hat{\mathcal{L}}^{\text{adv}}\) denotes the Clarke's subdifferential (Dutta et al., 2013), with respect to \(\underline{\mathbf{W}}(t)\). If \(\hat{\mathcal{L}}^{\text{adv}}(\underline{\mathbf{W}})\) is actually a \(C^{1}\)-smooth function, the above differential inclusion reduces to

\[\frac{\text{d}\underline{\mathbf{W}}(t)}{\text{d}t}\in-\frac{\partial\hat{ \mathcal{L}}^{\text{adv}}(\underline{\mathbf{W}}(t))}{\partial\underline{ \mathbf{W}}(t)} \tag{14}\]
for all \(t\geq 0\), which corresponds to the gradient flow with differential in the usual sense. However, for simplicity, we follow Vardi and Shamir (2021); Timor et al. (2023) that we still use Eq. (14) to denote Eq. (13) with a slight abuse of notations, even if \(\hat{\mathcal{L}}^{\text{adv}}\) does not satisfy differentiability but only locally Lipschitz. Note that the ReLU function is not differentiable at \(0\). Practical implementations of gradient methods define the derivative \(\sigma^{\prime}(0)\) to be some constant in \([0,1]\). In this work we assume for convenience that \(\sigma^{\prime}(0)=0\).

**Assumption 14** (Existence of a separability of adversarial examples during training): _There exists a time \(t_{0}\) such that \(N\hat{\mathcal{L}}^{\text{adv}}(t_{0})\leq\exp(\mathfrak{f}(b_{\mathfrak{f}}) )=\ell(b_{\mathfrak{f}})\)._

This assumption is a generalization of the separability condition in (Lyu and Li, 2020; Lv and Zhu, 2022). Adversarial training can typically achieve this separability in practice, _i.e._, the model can fit adversarial examples of the training dataset, which makes the above assumption a reasonable one.

**Lemma 15** (Convergence to the direction of a KKT point): _Consider the hypothesis class \(\mathfrak{F}\) in Eq. (6). Under Assumptions 6 and 14, the limit point of normalized weights \(\{\underline{\mathbf{W}}(t)/\left\|\underline{\mathbf{W}}(t)\right\|_{ \mathbb{F}}:t\geq 0\}\) of the gradient flow for Eq. (14), i.e., the empirical adversarial risk with scale invariant adversarial perturbations \(\underline{\boldsymbol{\delta}}_{i}(\underline{\mathbf{W}})\), is aligned with the direction of a KKT point of the minimization problem:_

\[\min_{\underline{\mathbf{W}}}\frac{1}{2}\left\|\underline{\mathbf{W}}\right\| _{\mathbb{F}}^{2},\qquad\text{s.t. }y_{i}f(\underline{\mathbf{x}}_{i}+\underline{ \boldsymbol{\delta}}_{i}(\underline{\mathbf{W}});\underline{\mathbf{W}})\geq 1, \forall i=1,\cdots,N. \tag{15}\]

**Theorem 16** (Implicit low-rankness induced by GF for t-NNs): _Suppose that there is an example \(\underline{\mathbf{x}}_{i}\) satisfying \(\left\|\underline{\mathbf{x}}_{i}\right\|_{\mathbb{F}}\leq 1\) in the training set \(S=\{(\underline{\mathbf{x}}_{i},y_{i})\}_{i=1}^{N}\subseteq\mathbb{R}^{d\times 1 \times\mathbf{c}}\times\{\pm 1\}\). Assume that there is a \((J+1)\)-layer (\(J\geq 2\)) ReLU t-NN, denoted by \(g(\underline{\mathbf{x}};\underline{\mathbf{V}})\) with parameterization \(\underline{\mathbf{V}}=(\underline{\mathbf{V}}^{(1)},\cdots,\underline{ \mathbf{V}}^{(J)},\mathbf{v})\), satisfying the following conditions:_

1. _the dimensionality of the weight tensor_ \(\underline{\mathbf{V}}^{(j)}\in\mathbb{R}^{m_{j}\times m_{j-1}\times\mathbf{ c}}\) _of the_ \(j\)_-th t-product layer satisfies_ \(m_{j}\geq 2\)_,_ \(\forall j=1,\cdots,J\)_;_
2. _there is a constant_ \(B>0\)_, such that the Euclidean norm of the weights_ \(\underline{\mathbf{V}}=(\underline{\mathbf{V}}^{(1)},\cdots,\underline{ \mathbf{V}}^{(L)},\mathbf{v})\) _satisfy_ \(\left\|\underline{\mathbf{V}}^{(j)}\right\|_{\mathbb{F}}\leq B\) _for all_ \(j=1,\cdots,J\) _and_ \(\left\|\mathbf{v}\right\|_{2}\leq B\)_; and_
3. _for all_ \(i\in\{1,\cdots,N\}\)_, we have_ \(y_{i}g(\underline{\mathbf{x}}_{i}+\underline{\boldsymbol{\delta}}_{i}( \underline{\mathbf{V}});\underline{\mathbf{V}})\geq 1\)_, i.e., all the perturbed training samples are correctly classified._

_Then, we consider the class of over-parameterized t-NNs \(\mathfrak{F}=\{f(\underline{\mathbf{x}};\underline{\mathbf{W}})\}\) defined in Eq. (5) satisfies_

1. _the number_ \(L\) _of t-product layers is much greater than_ \(J\)_, and_
2. _the dimensionality of weight_ \(\underline{\mathbf{W}}^{(l)}\in\mathbb{R}^{d_{l}\times d_{l-1}\times\mathbf{ c}}\) _satisfies_ \(d_{l}\gg\max_{j\leq J}\{m_{j}\}\) _for all_ \(l=1,\cdots,L\)_._

_Let \(\underline{\mathbf{W}}^{*}=(\underline{\mathbf{W}}^{*(1)},\cdots,\underline{ \mathbf{W}}^{*(L)},\mathbf{w}^{*})\) be a global optimum of Problem (15). Namely, \(\underline{\mathbf{W}}^{*}\) parameterizes a minimum-norm t-NN \(f(\underline{\mathbf{x}};\underline{\mathbf{W}}^{*})\in\mathfrak{F}\) that labels the perturbated datasets correctly with margin 1 under homogeneous adversarial perturbation. Then, we have_

\[\frac{L}{\sum_{l=1}^{L}\left(r_{\text{stb}}(\widetilde{\mathbf{W}}_{M}^{*(l)}) \right)^{-1/2}}\leq\frac{1}{\left(1+\frac{1}{L}\right)\left(\frac{1}{B} \right)^{\frac{J+1}{L+1}}\sqrt{\frac{L+1}{(J+1)+(cm_{J})(L-J)}}-\frac{1}{L}} \tag{16}\]

_where \(\widetilde{\mathbf{W}}_{M}^{*(l)}\) denotes the \(M\)-block-diagonal matrix of weight tensor \(\underline{\mathbf{W}}^{*(l)}\) for all \(l=1,\cdots,L\)._
By the above theorem, when \(L\) is sufficiently large, the harmonic mean of the square root of the stable rank of \(\widehat{\mathbf{W}}_{M}^{*(l)}\), i.e., the \(M\)-block-diagonal matrix of weight tensor \(\underline{\mathbf{W}}^{*(l)}\), is roughly \(1/\sqrt{cm_{J}}\), which is significantly smaller than the squared root of the dimensionality \(\sqrt{\min\{cd_{l},cd_{l-1}\}}\) according to condition \((c.5)\) in Theorem 16. Thus, \(f(\underline{\mathbf{x}};\underline{\mathbf{W}}^{*})\) has an nearly low-rank parameterization in the transformed domain. In our case, the weights \(\underline{\mathbf{W}}(t)\) generated by the GF tend to have an infinite norm and to converge in direction to a transformed low-rank solution. Moreover, note that the ratio between the spectral and the Frobenius norms is invariant to scaling, and hence it suggests that after a sufficiently long time, GF tends to reach a network with transformed low-rank weight tensors. There are also experimental supports of this phenomenon (Langenberg et al., 2019) that adversarial training leads to low-rank weights.

### Adversarial Generalization Bounds for Approximate Low-Tubal-Rank t-NNs

Theorem 16 shows that for highly over-parameterized adversarial training with GF, the well trained t-NNs have approximately transformed low-rank parameters under certain conditions. In this section, we will characterize the adversarial generalization behavior of the approximately transformed low-rank6 parameterized t-NNs.

Footnote 6: We use the tensor tubal rank as a measure of low-rankness in the transformed domain for notation simplicity. One can also consider the average rank (Wang et al., 2021) or multi-rank (Wang et al., 2021) for more refined bounds with quite similar techniques.

An approximately low-tubal-rank parameterized t-NN \(f\) can be compressed with an exactly low-tubal-rank parameterized t-NN \(g\in\mathfrak{F}_{\mathbf{r}}\), and we can ensure that the compressed function \(g\) has a small distance to the original function \(f\) in their parameter space. _Then, can the small parameter distance between \(f\) and \(g\) also indicate a small difference in their adversarial generalization behaviors?_ To answer the questions, we first define the \((\delta,\mathbf{r})\)-approximate low-tubal-rank parameterized functions.

**Definition 17** (\((\delta,\mathbf{r})\)-approximate low-tubal-rank parameterization): _A t-NN \(f(\underline{\mathbf{x}};\underline{\mathbf{W}})\in\mathfrak{F}\) with weights \(\underline{\mathbf{W}}=(\mathbf{w},\underline{\mathbf{W}}^{(1)},\cdots, \underline{\mathbf{W}}^{(L)})\) is said to satisfy the \((\delta,\mathbf{r})\)-approximate low-tubal parameterization of tolerance \(\delta>0\) and rank \(\mathbf{r}=(r_{1},\cdots,r_{L})^{\top}\in\mathbb{N}^{L}\), if there is a t-NN \(g(\underline{\mathbf{x}};\underline{\mathbf{W}}_{\mathbf{r}})\in\mathfrak{F}_ {\mathbf{r}}\) whose weights \(\underline{\mathbf{W}}_{g}=(\mathbf{w},\underline{\mathbf{W}}_{r_{1}}^{(1)}, \cdots,\underline{\mathbf{W}}_{r_{L}}^{(L)})\) satisfy \(\left\|\underline{\mathbf{W}}_{r_{1}}^{(l)}-\underline{\mathbf{W}}^{(l)} \right\|_{\mathrm{F}}\leq\delta,\forall l\in\{1,\cdots,L\}\)._

Consider the adversarially trained t-NNs with approximately low-tubal-rank weights in the set

\[\mathfrak{F}_{\delta,\mathbf{r}}:=\{f\in\mathfrak{F}|f\text{ satisfies the }(\delta,\mathbf{r})\text{-approximate low-tubal parameterization}\}\,. \tag{17}\]

Our idea of bounding the adversarial generalization gap for any \(f\in\mathfrak{F}_{\delta,\mathbf{r}}\) in terms of its low-tubal-rank compression \(g\in\mathfrak{F}_{\mathbf{r}}\) is motivated by the work of compressed bounds for non-compressed but compressable models (Suzuki et al., 2020) which is originally developed for generalization analysis of standard training.

Under Assumption 6, we define the adversarial version of \(\mathfrak{F}_{\delta,\mathbf{r}}\) as \(\mathfrak{F}_{\delta,\mathbf{r}}^{\mathrm{adv}}:=\{\tilde{f}:(\underline{ \mathbf{x}},y)\mapsto\min_{R_{\mathbf{z}}(\mathbf{z}^{\prime}-\underline{ \mathbf{x}})\leq\xi}yf(\underline{\mathbf{x}}^{\prime})\mid f\in\mathfrak{F}_ {\delta,\mathbf{r}}\}\). To analyze adversarial generalization gap of function \(f\) in \(\mathfrak{F}_{\delta,\mathbf{r}}\) through \(g\in\mathfrak{F}_{\mathbf{r}}\), we consider their adversarial counterparts \(\tilde{f}\in\mathfrak{F}_{\delta,\mathbf{r}}^{\mathrm{adv}}\) and \(\tilde{g}\in\mathfrak{F}_{\mathbf{r}}^{\mathrm{adv}}\), where \(\mathfrak{F}_{\mathbf{r}}^{\mathrm{adv}}\) is defined as \(\mathfrak{F}_{\mathbf{r}}^{\mathrm{adv}}:=\{\tilde{f}:(\underline{\mathbf{x} },y)\mapsto\min_{R_{\mathbf{z}}(\underline{\mathbf{x}}-\underline{\mathbf{x}}^ {\prime})\leq\xi}yf(\underline{\mathbf{x}}^{\prime})\mid f\in\mathfrak{F}_{ \mathbf{r}}\}\). The Minkowski difference of set \(\mathfrak{F}_{\delta,\mathbf{r}}^{\mathrm{adv}}\) and \(\mathfrak{F}_{\mathbf{r}}^{\mathrm{adv}}\) is given by \(\mathfrak{F}_{\delta,\mathbf{r}}^{\mathrm{adv}}-\mathfrak{F}_{\mathbf{r}}^{ \mathrm{adv}}:=\{\tilde{f}-\tilde{g}\mid\tilde{f}\in\mathfrak{F}_{\delta, \mathbf{r}}^{\mathrm{adv}},\,\tilde{g}\in\mathfrak{F}_{\mathbf{r}}^{\mathrm{adv}}\}\).

The empirical \(L_{2}\)-norm of a t-NN \(h\in\mathfrak{F}\) on a training sample \(S=(\underline{\mathbf{x}}_{i},y_{i})_{i=1}^{N}\) is defined as \(\left\|h\right\|_{S}:=\sqrt{N^{-1}\sum_{i=1}^{N}h^{2}(\underline{\mathbf{x}}_ {i},y_{i})}\), and the population \(L_{2}\)-norm is \(\left\|h\right\|_{L_{2}}:=\sqrt{\mathbb{E}_{P(\underline{\mathbf{x}},y)}[h^{2}( \underline{\mathbf{x}},y)]}\). In
the coming Theorem 19, we show that the small distance in the parameter space of \(f\) and \(g\) results in a small empirical \(L_{2}\)-distance in the adversarial output space. Specifically, for any \(f(\underline{\mathbf{x}};\underline{\mathbf{W}})\in\mathfrak{F}_{\delta, \mathbf{r}}\) with compressed version \(g(\underline{\mathbf{x}};\underline{\mathbf{W}}_{\mathbf{r}})\), the adversarial empirical \(L_{2}\)-norm \(\left\|\tilde{f}(\underline{\mathbf{x}};\underline{\mathbf{W}})-\tilde{g}( \underline{\mathbf{x}};\underline{\mathbf{W}}_{\mathbf{r}})\right\|_{S}\) can be upper bounded by a small constant \(\hat{\mathfrak{r}}>0\) in linearity of \(\delta\). Define the local Rademacher complexity of \(\mathfrak{F}_{\delta,\mathbf{r}}^{\text{adv}}-\mathfrak{F}_{\mathbf{r}}^{ \text{adv}}\) of radius \(\mathfrak{r}>0\) (in population \(L_{2}\)-norm) as \(\hat{R}_{\mathbf{r}}(\mathfrak{F}_{\delta,\mathbf{r}}^{\text{adv}}- \mathfrak{F}_{\mathbf{r}}^{\text{adv}}):=\bar{R}_{N}(\{h\in\mathfrak{F}_{ \delta,\mathbf{r}}^{\text{adv}}-\mathfrak{F}_{\mathbf{r}}^{\text{adv}}\mid \left\|h\right\|_{L_{2}}\leq\mathfrak{r}\}),\) where \(\bar{R}_{N}(\mathcal{H})\) denotes the average Rademacher complexity of a function class \(\mathcal{H}\)(Bartlett et al., 2002). We assume the local Rademacher complexity of \(\mathfrak{F}_{\delta,\mathbf{r}}^{\text{adv}}-\mathfrak{F}_{\mathbf{r}}^{ \text{adv}}\) can be upper bounded by a concave funtion of \(\mathfrak{r}\) which is a common assumption for analyzing localized Redemacher complexity (Bartlett et al., 2002; Suzuki et al., 2020).

**Assumption 18**: _Suppose their exists a function \(\phi:[0,\infty)\rightarrow[0,\infty)\) such that \(\dot{R}_{\mathfrak{r}}(\mathfrak{F}_{\delta,\mathbf{r}}^{\text{adv}}- \mathfrak{F}_{\mathbf{r}}^{\text{adv}})\leq\phi(\mathfrak{r})\ \ \text{and}\ \ \phi(2 \mathfrak{r})\leq 2\phi(\mathfrak{r}),\ (\forall\mathfrak{r}>0).\)_

We further define \(\mathfrak{r}_{*}=\mathfrak{r}_{*}(t):=\inf\left\{\mathfrak{r}>0\ \big{|}16B_{f}\mathfrak{r}^{-2}\phi(\mathfrak{r})+B_{f}\mathfrak{r}^{-1} \sqrt{2t/N}+2tB_{f}^{2}\mathfrak{r}^{-2}/N\leq 1/2\right\}\) for any \(t>0\), to bound the ratio of the empirical and population \(L_{2}\)-norm of any function \(h\in\mathfrak{F}_{\delta,\mathbf{r}}^{\text{adv}}-\mathfrak{F}_{\mathbf{r}}^{ \text{adv}}\) by \(\left\|h\right\|_{L_{2}}^{2}\leq 2(\left\|h\right\|_{S}^{2}+\mathfrak{r}_{*}^{2})\) with high probability via peeling argument (Steinwart and Christmann, 2008, Theorem 7.7).

Then, we establish an adversarial generalization bound for approximately low-tubal-rank t-NNs.

**Theorem 19** (**Adversarial generalization bound for general approximately low-tubal-rank t-NNs**): _For any \((\delta,\mathbf{r})\)-approximately low-tubal-rank parameterized \(f\in\mathfrak{F}_{\delta,\mathbf{r}}\) with adversarial proxy \(\tilde{f}\in\mathfrak{F}_{\delta,\mathbf{r}}^{\text{adv}}\), there is a \(g\in\mathfrak{F}_{\mathbf{r}}\) with adversarial proxy \(\tilde{g}\in\mathfrak{F}_{\mathbf{r}}^{\text{adv}}\) such that \(\left\|\tilde{f}-\tilde{g}\right\|_{S}\leq\delta B_{\tilde{f}}\sum_{l=1}^{L}B_{ l}^{-1}=:\hat{\mathfrak{r}}\). Let \(\dot{\mathfrak{r}}=\sqrt{2(\hat{\mathfrak{r}}^{2}+\mathfrak{r}_{*}^{2})}\). Then, under Assumptions 5, 6, 18, there exist constants \(C_{1},C_{2}>0\) such that_

\[\begin{split}\mathcal{L}^{\text{adv}}(f)-\hat{\mathcal{L}}^{ \text{adv}}(f)\leq&\underbrace{\frac{C_{1}L_{\ell}B_{\tilde{f}}}{ \sqrt{N}}\sqrt{\mathfrak{c}\sum_{l=1}^{L}r_{l}(d_{l-1}+d_{l})\log(9(L+1))}+B \sqrt{\frac{t}{2N}}}_{\text{main term}}\\ &+\underbrace{C_{2}\left(\Phi(\dot{\mathfrak{r}})+L_{\ell}\dot{ \mathfrak{r}}\sqrt{\frac{t}{N}}+\frac{tL_{\ell}B_{\tilde{f}}}{N}\right)}_{ \text{bias term}}\end{split} \tag{18}\]

_for all \(f\in\mathfrak{F}_{\delta,\mathbf{r}}\) with probability at least \(1-4e^{-t}\) for all \(t>0\), where \(\Phi(\mathfrak{r})\) is defined as_

\[\Phi(\mathfrak{r}):=\bar{R}_{N}\left(\left\{\ell\circ\tilde{f}-\ell\circ \tilde{g}\ \big{|}\ \tilde{f}\in\mathfrak{F}_{\delta,\mathbf{r}}^{\text{adv}},\tilde{g}\in \mathfrak{F}_{\mathbf{r}}^{\text{adv}},\ \left\|\tilde{f}-\tilde{g}\right\|_{L_{2}}\leq\mathfrak{r}\right\} \right).\]

_Here, \(\circ\) denotes the function composition operation._

The main term measures the complexity of functions \(\mathfrak{F}_{\mathbf{r}}\) with exact low-tubal-rank parameterization in adversarial settings which could be much smaller than \(\mathfrak{F}_{\delta,\mathbf{r}}\). The bias term represents a sample complexity to bridge the approximately low-tubal-rank parameterized \(\mathfrak{F}_{\delta,\mathbf{r}}\) and exactly low-tubal-rank parameterized \(\mathfrak{F}_{\mathbf{r}}\). Typically we have \(\mathfrak{r}_{*}^{2}=o(1/\sqrt{N})\), and if we set \(\hat{\mathfrak{r}}=o_{p}(1)\), then the bias term can be faster than the main term which is \(O(1/\sqrt{N})\).
We further demonstrate how small the obtained bound can be in a special setting where the weights of t-product layers have singular values satisfying a polynomial decay in the transformed domain.

**Assumption 20**: _Consider the setting where any \(t\)-NN \(f(\underline{\mathbf{x}};\underline{\mathbf{W}})\in\mathfrak{F}_{\delta,\mathbf{ r}}\) has tensor weights \(\underline{\mathbf{W}}^{(l)}\)\((l=1,\cdots,L)\) whose singular values in the transformed domain satisfy \(\sigma_{j}(M(\underline{\mathbf{W}}^{(l)})_{:,:,k})\leq V_{0}\cdot j^{-\alpha}\), where \(V_{0}>0\) is a constant, and \(\sigma_{j}(\cdot)\) is the \(j\)-th largest singular value of a matrix._

In this setting, we can see that for any \(1\leq r_{l}\leq\min\{d_{l},d_{l-1}\}\), we can approximate \(\underline{\mathbf{W}}^{(l)}\) with its optimal tubal-rank-\(r_{l}\) approximation tensor \(\underline{\mathbf{W}}_{r_{l}}^{(l)}\) as \(\left\|\underline{\mathbf{W}}^{(l)}-\underline{\mathbf{W}}_{r_{l}}^{(l)} \right\|_{\mathbf{F}}=\left\|M(\underline{\mathbf{W}}^{(l)})-M(\underline{ \mathbf{W}}_{r_{l}}^{(l)})\right\|_{\mathbf{F}}\leq\sqrt{c/(2\alpha-1)}V_{0} (r_{l}-1)^{(1-2\alpha)/2},\) which can be much smaller than \(\left\|\underline{\mathbf{W}}_{r_{l}}^{(l)}\right\|_{\mathbf{F}}\) when \(\alpha>1/2\) is sufficiently large. Thus, we can always find an exactly low-tubal-rank parameterized \(g\in\mathfrak{F}_{\mathbf{r}}\) for any \(f\in\mathfrak{F}_{\delta,\mathbf{r}}\) with approximately low-tubal-rank weights, such that the distance between \(g\) and \(f\) in the parameter space is quite small. The following theorem shows that the small distance in parameter space also leads to small adversarial generalization gaps.

**Theorem 21**: _Under Assumptions 5, 6 and 20, if we let \(\hat{\mathbf{r}}=V_{0}B_{\tilde{f}}\sum_{l=1}^{L}(r_{l}+1)^{-\alpha}B_{l}^{-1},\) then for any \(t\)-NN \(f\in\mathfrak{F}_{\delta,\mathbf{r}}\) there is always a function \(g\in\mathfrak{F}_{\mathbf{r}}\) whose t-product layer weights have tubal-rank exactly no greater than \(r_{l}\), satisfies \(\left\|\tilde{f}-\tilde{g}\right\|_{S}\leq\hat{\mathbf{r}}\). Then, there is a constant \(C_{\alpha}\) only depending on \(\alpha\) such that for any function \(f\in\mathfrak{F}_{\delta,\mathbf{r}}\), its adversarial generalization gap holds for any \(t>0\)_

\[\mathcal{L}^{\text{adv}}(f)-\hat{\mathcal{L}}^{\text{adv}}(f) \tag{19}\] \[\leq C_{\alpha}L_{\ell}\bigg{\{}B_{\tilde{f}}E_{1}+\hat{\mathbf{ r}}\sqrt{E_{1}}+E_{2}^{\frac{2\alpha}{2\alpha+1}}\left(B_{\tilde{f}}^{\frac{2 \alpha-1}{2\alpha+1}}+1\right)+\hat{\mathbf{r}}^{\frac{2\alpha}{2\alpha+1}} \sqrt{E_{2}}+(\hat{\mathbf{r}}+\frac{B}{L_{\ell}})\sqrt{\frac{t}{N}}+\frac{1+ tB_{\tilde{f}}}{N}\bigg{\}}\]

_with probability at least \(1-4e^{-t}\), where \(E_{1}=N^{-1}\mathbf{c}\sum_{l=1}^{L}r_{l}(d_{l}+d_{l-1})\log(9NLB_{\tilde{f}} /\sqrt{\mathbf{c}})\) and \(E_{2}=N^{-1}\mathbf{c}\sum_{l=1}^{L}\left(LV_{0}B_{\tilde{f}}B_{l}^{-1} \right)^{1/\alpha}(d_{l}+d_{l-1})\log(9NLB_{\tilde{f}}/\sqrt{\mathbf{c}}).\)_

This indicates that, if \(\alpha>1/2\) is large (in other words, each weight matrix is close to rank \(1\)), then we have a better generalization error bound. Note that the rank \(r_{l}\) can be arbitrary chosen and \(\hat{\mathbf{r}}\) and \(E_{1}\) are in a trade-off relation. Hence, by selecting the rank appropriately so that this trade-off is balanced, then we obtain the optimal upper bound as in the following corollary.

**Corollary 22**: _Under the same assumption to Theorem 21, if we choose the parameter \(\mathbf{r}\) of tubal ranks in \(\mathfrak{F}_{\mathbf{r}}\) by \(r_{l}=\min\{\lceil\left(LV_{0}B_{\tilde{f}}B_{l}^{-1}\right)^{1/\alpha}\rceil,d _{l},d_{l-1}\}\), then there is a constant \(C_{\alpha}\) only depending on \(\alpha\) such that for any function \(f\in\mathfrak{F}_{\delta,\mathbf{r}}\), its adversarial generalization gap_

\[\mathcal{L}^{\text{adv}}(f)-\hat{\mathcal{L}}^{\text{adv}}(f) \leq C_{\alpha}L_{\ell}\bigg{\{}B_{\tilde{f}}^{1-1/(2\alpha)}\sqrt{ \frac{\mathbf{c}\sum_{l=1}^{L}\left(LV_{0}B_{l}^{-1}\right)^{1/\alpha}(d_{l}+d _{l-1})\log(9NLB_{\tilde{f}}/\sqrt{\mathbf{c}})}{N}} \tag{20}\] \[\qquad\qquad+E_{2}^{\frac{2\alpha}{2\alpha+1}}\left(B_{\tilde{f}} ^{\frac{2\alpha-1}{2\alpha+1}}+1\right)+\sqrt{E_{2}}+\frac{B}{L_{\ell}}\sqrt{ \frac{t}{N}}+\frac{1+tB_{\tilde{f}}}{N}\bigg{\}}\]

_holds with probability at least \(1-4e^{-t}\) for any \(t>0\)._
Note that the bound has linear dependency on all the number of neurons of t-product layers in the square root, i.e., \(O\left(\sqrt{\frac{\zeta\sum_{i}(d_{i}+d_{i-1})}{N}}\right)\), while the Theorem 9 shows dependency on the number of total parameters, i.e., \(O\left(\sqrt{\frac{\zeta\sum_{i}d_{i}d_{i-1}}{N}}\right)\). This result implies that the low-tubal-rank parameterization of t-NNs might achieve much better adversarial generalization for multi-channel data learning.

## 5 Related Works

**T-SVD-based data and function representation:** What most significantly distinguishes t-SVD-based data representation from the classical low-rank decomposition methods, is the low-rankness defined in the transformed domain. This low-rankness is vital to real multi-channel data modeling with both smoothness and low-rankness (Wang et al., 2020; Liu et al., 2020; Wang et al., 2021). Utilized in t-product layers in DNNs (Newman et al., 2018; Malik et al., 2021; Wu et al., 2022), t-SVD has also been a workhorse for function representation and achieves impressive empirical performance. In terms of theoretical studies, extensive past research on t-SVD-based signal processing models were conducted (Zhang and Ng, 2022; Liu et al., 2020; Qiu et al., 2022; Wang et al., 2021). However, t-SVD-based learning model has never been theoretically scrutinized. To the best of our knowledge, this paper is the first for theoretical analysis of t-SVD-based learning models.

**Theoretical analysis methods:** The related theoretical analysis methods are norm-based generalization analysis (Neyshabur et al., 2015) and implicit regularization of gradient descent based learning (Vardi and Shamir, 2021). Norm-based generalization analysis is important to theoretical analysis in standard generalization analysis of DNNs (Golowich et al., 2018), compressed models (Arora et al., 2018) and non-compressed models (Suzuki et al., 2020). Note that in compressed models, the standard generalization bound may be driven by intrinsic parameters (Arora et al., 2018). It also plays an important role in adversarial generalization analysis (Yin et al., 2019; Awasthi et al., 2020; Xiao et al., 2022). All aforementioned works are for models using matrix products. Instead we adopt norm-based tools in standard and adversarial generalization analysis on t-NNs. For implicit regularization of gradient descent based learning, extensive past research has been conducted on implicit bias of GF for both standard and adversarial training of homogeneous networks building on matrix product layers, respectively (Lyu and Li, 2020; Ji and Telgarsky, 2020). For different networks, Gunasekar et al. (2018) and Yun et al. (2021) proved biases towards sparse linear predictors for linear diagonal networks and linear convolution networks, respectively, whereas Timor et al. (2023) derived the bias towards low-rank solutions for ReLU networks with sufficient depth. Our analysis extends them to adversarial training of t-NN with scale-invariant adversarial perturbations, and demonstrates that GF for overparameterized t-NN with ReLU activations produces nearly transformed low-rank weights.

## 6 Concluding Remarks

This paper explores how t-SVD influences the learning behavior of t-NNs. We first derive the upper bounds of generalization gaps of both standard and adversarially trained t-NNs. For more efficient adversarial learning, t-NNs are then compressed by imposing the transformed low-rank structure
into the weight tensors, which achieves sharper bounds on the adversarial generalization gap. Although weights of well trained models are rarely exactly transformed low-rank, our analysis further shows that for adversarial training with gradient flow in highly over-parameterized settings, the learnt t-NNs tend to have approximately transformed low-rank weights. We also establish adversarial generalization bounds for t-NNs with approximately transformed low-rank weights in both general cases and a special case where the weight tensors have certain patterns of spectral decay in the transformed domain.
